Skip to content

Commit 341860f

Browse files
gzm0gzm0
authored
Merge pull request #5203 from sjrd/compress-expand
Implement {Integer,Long}.{compress,expand}.
2 parents 63e75bf + f335260 commit 341860f

File tree

4 files changed

+423
-0
lines changed

4 files changed

+423
-0
lines changed

‎javalib/src/main/scala/java/lang/Integer.scala

Lines changed: 76 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -373,6 +373,82 @@ object Integer {
373373
@inline def rotateRight(i: scala.Int, distance: scala.Int): scala.Int =
374374
(i >>> distance) | (i << -distance)
375375

376+
def compress(i: scala.Int, mask: scala.Int): scala.Int = {
377+
// Hacker's Delight, Section 7-4, Figure 7-10
378+
379+
val LogBitSize = 5 // log_2(32)
380+
381+
// !!! Verbatim copy-paste of Long.compress
382+
383+
var m = mask
384+
var x = i & mask // clear irrelevant bits
385+
var mk = ~m << 1 // we will count 0's to right
386+
387+
var j = 0 // i in Hacker's Delight, but we already have an i
388+
while (j < LogBitSize) {
389+
val mp = parallelSuffix(mk)
390+
val mv = mp & m // bits to move
391+
m = (m ^ mv) | (mv >>> (1 << j)) // compress m
392+
val t = x & mv
393+
x = (x ^ t) | (t >>> (1 << j)) // compress x
394+
mk = mk & ~mp
395+
j += 1
396+
}
397+
398+
x
399+
}
400+
401+
def expand(i: scala.Int, mask: scala.Int): scala.Int = {
402+
// Hacker's Delight, Section 7-5, Figure 7-12
403+
404+
val LogBitSize = 5 // log_2(32)
405+
406+
val array = new Array[scala.Int](LogBitSize)
407+
408+
// !!! Verbatim copy-paste of Long.expand
409+
410+
var m = mask
411+
var x = i
412+
var mk = ~m << 1 // we will count 0's to right
413+
414+
var j = 0 // i in Hacker's Delight, but we already have an i
415+
while (j < LogBitSize) {
416+
val mp = parallelSuffix(mk)
417+
val mv = mp & m // bits to move
418+
array(j) = mv
419+
m = (m ^ mv) | (mv >>> (1 << j)) // compress m
420+
mk = mk & ~mp
421+
j += 1
422+
}
423+
424+
j = LogBitSize - 1
425+
while (j >= 0) {
426+
val mv = array(j)
427+
val t = x << (1 << j)
428+
429+
/* See the last line of the section text, but there is a mistake in the
430+
* book: y should be t. There is no y in this algorithm, so it doesn't
431+
* make sense. Plugging t instead matches the formula (c) of "Exchanging
432+
* Corresponding Fields of Registers" in Section 2-20.
433+
*/
434+
x = ((x ^ t) & mv) ^ x
435+
436+
j -= 1
437+
}
438+
439+
x & mask // clear out extraneous bits
440+
}
441+
442+
@inline
443+
private def parallelSuffix(x: Int): Int = {
444+
// Hacker's Delight, Section 5-2
445+
var y = x ^ (x << 1)
446+
y = y ^ (y << 2)
447+
y = y ^ (y << 4)
448+
y = y ^ (y << 8)
449+
y ^ (y << 16)
450+
}
451+
376452
@inline def signum(i: scala.Int): scala.Int =
377453
if (i == 0) 0 else if (i < 0) -1 else 1
378454

‎javalib/src/main/scala/java/lang/Long.scala

Lines changed: 77 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -451,6 +451,83 @@ object Long {
451451
def rotateRight(i: scala.Long, distance: scala.Int): scala.Long =
452452
(i >>> distance) | (i << -distance)
453453

454+
def compress(i: scala.Long, mask: scala.Long): scala.Long = {
455+
// Hacker's Delight, Section 7-4, Figure 7-10
456+
457+
val LogBitSize = 6 // log_2(64)
458+
459+
// !!! Verbatim copy-paste of Integer.compress
460+
461+
var m = mask
462+
var x = i & mask // clear irrelevant bits
463+
var mk = ~m << 1 // we will count 0's to right
464+
465+
var j = 0 // i in Hacker's Delight, but we already have an i
466+
while (j < LogBitSize) {
467+
val mp = parallelSuffix(mk)
468+
val mv = mp & m // bits to move
469+
m = (m ^ mv) | (mv >>> (1 << j)) // compress m
470+
val t = x & mv
471+
x = (x ^ t) | (t >>> (1 << j)) // compress x
472+
mk = mk & ~mp
473+
j += 1
474+
}
475+
476+
x
477+
}
478+
479+
def expand(i: scala.Long, mask: scala.Long): scala.Long = {
480+
// Hacker's Delight, Section 7-5, Figure 7-12
481+
482+
val LogBitSize = 6 // log_2(64)
483+
484+
val array = new Array[scala.Long](LogBitSize)
485+
486+
// !!! Verbatim copy-paste of Integer.expand
487+
488+
var m = mask
489+
var x = i
490+
var mk = ~m << 1 // we will count 0's to right
491+
492+
var j = 0 // i in Hacker's Delight, but we already have an i
493+
while (j < LogBitSize) {
494+
val mp = parallelSuffix(mk)
495+
val mv = mp & m // bits to move
496+
array(j) = mv
497+
m = (m ^ mv) | (mv >>> (1 << j)) // compress m
498+
mk = mk & ~mp
499+
j += 1
500+
}
501+
502+
j = LogBitSize - 1
503+
while (j >= 0) {
504+
val mv = array(j)
505+
val t = x << (1 << j)
506+
507+
/* See the last line of the section text, but there is a mistake in the
508+
* book: y should be t. There is no y in this algorithm, so it doesn't
509+
* make sense. Plugging t instead matches the formula (c) of "Exchanging
510+
* Corresponding Fields of Registers" in Section 2-20.
511+
*/
512+
x = ((x ^ t) & mv) ^ x
513+
514+
j -= 1
515+
}
516+
517+
x & mask // clear out extraneous bits
518+
}
519+
520+
@inline
521+
private def parallelSuffix(x: scala.Long): scala.Long = {
522+
// Hacker's Delight, Section 5-2
523+
var y = x ^ (x << 1)
524+
y = y ^ (y << 2)
525+
y = y ^ (y << 4)
526+
y = y ^ (y << 8)
527+
y = y ^ (y << 16)
528+
y ^ (y << 32)
529+
}
530+
454531
@inline
455532
def signum(i: scala.Long): Int = {
456533
val hi = (i >>> 32).toInt

‎test-suite/shared/src/test/require-jdk21/org/scalajs/testsuite/javalib/lang/IntegerTestOnJDK21.scala

Lines changed: 134 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,134 @@
1+
/*
2+
* Scala.js (https://www.scala-js.org/)
3+
*
4+
* Copyright EPFL.
5+
*
6+
* Licensed under Apache License 2.0
7+
* (https://www.apache.org/licenses/LICENSE-2.0).
8+
*
9+
* See the NOTICE file distributed with this work for
10+
* additional information regarding copyright ownership.
11+
*/
12+
13+
package org.scalajs.testsuite.javalib.lang
14+
15+
import org.junit.Test
16+
import org.junit.Assert._
17+
18+
class IntegerTestOnJDK21 {
19+
20+
@Test def compress(): Unit = {
21+
// Example from the doc
22+
assertEquals(0x000cabab, Integer.compress(0xcafebabe, 0xff00fff0))
23+
24+
// Random test cases
25+
assertEquals(0x00000106, Integer.compress(0x89709d4b, 0x7a865060))
26+
assertEquals(0x000000ab, Integer.compress(0x99933665, 0x0b505400))
27+
assertEquals(0x00000014, Integer.compress(0x01d4851c, 0x101c1040))
28+
assertEquals(0x0000020a, Integer.compress(0xd09d94a0, 0x1742a082))
29+
assertEquals(0x00000032, Integer.compress(0x45ca9572, 0x1ac04203))
30+
assertEquals(0x00000136, Integer.compress(0xf53bb659, 0x20ee0402))
31+
assertEquals(0x0000003e, Integer.compress(0x3aca6e68, 0x00304e44))
32+
assertEquals(0x00000007, Integer.compress(0x80e5df8f, 0x00028500))
33+
assertEquals(0x0000000e, Integer.compress(0x6ec079f2, 0x10002091))
34+
assertEquals(0x000007b7, Integer.compress(0xfc8242fc, 0x5e828288))
35+
assertEquals(0x00000101, Integer.compress(0xccc51aaa, 0xa2184460))
36+
assertEquals(0x0000001b, Integer.compress(0x8f673f64, 0x04520200))
37+
assertEquals(0x0000001b, Integer.compress(0xbf6fd8b3, 0x480420a0))
38+
assertEquals(0x000000ee, Integer.compress(0x3be5a94a, 0x8580e980))
39+
assertEquals(0x0000001e, Integer.compress(0xb03e6c68, 0x41282810))
40+
assertEquals(0x00000043, Integer.compress(0x2020edaf, 0x20c30180))
41+
assertEquals(0x00000001, Integer.compress(0xb385d407, 0x00000001))
42+
assertEquals(0x00000017, Integer.compress(0x416158fa, 0x12504060))
43+
assertEquals(0x00000006, Integer.compress(0x857ee772, 0x48806800))
44+
assertEquals(0x00000057, Integer.compress(0xb7803dee, 0xe001000e))
45+
assertEquals(0x00000030, Integer.compress(0xb815b083, 0x002c8c44))
46+
assertEquals(0x00000001, Integer.compress(0x3587593b, 0x00000008))
47+
assertEquals(0x00000144, Integer.compress(0xb5a433fa, 0xd8004905))
48+
assertEquals(0x00000007, Integer.compress(0x8b7e53b5, 0x00000031))
49+
assertEquals(0x0000006a, Integer.compress(0x2f8a5041, 0x12023148))
50+
assertEquals(0x0000004b, Integer.compress(0x34d1dd9f, 0x620400c9))
51+
assertEquals(0x00000001, Integer.compress(0x9d6feff4, 0x00800100))
52+
assertEquals(0x00000000, Integer.compress(0x943fb671, 0x00000000))
53+
assertEquals(0x00000176, Integer.compress(0x978edc70, 0x044c4232))
54+
assertEquals(0x00000000, Integer.compress(0x20162f69, 0x00000002))
55+
assertEquals(0x000000c8, Integer.compress(0x4be28cf0, 0x0040c24e))
56+
assertEquals(0x00000009, Integer.compress(0xfa162c33, 0x00005a50))
57+
assertEquals(0x000000f7, Integer.compress(0xc7f24ff6, 0x80905c80))
58+
assertEquals(0x00000006, Integer.compress(0x2c0da46a, 0x11108003))
59+
assertEquals(0x00000004, Integer.compress(0x01e9c326, 0x00002681))
60+
assertEquals(0x00000017, Integer.compress(0xa5978785, 0x00209601))
61+
assertEquals(0x0000002a, Integer.compress(0xfd14e766, 0x80089003))
62+
assertEquals(0x00000009, Integer.compress(0xbd1ea1b2, 0x0000c820))
63+
assertEquals(0x00000002, Integer.compress(0xa07002e3, 0x00002928))
64+
assertEquals(0x0000000a, Integer.compress(0x81eb15c0, 0x06200841))
65+
assertEquals(0x0000001e, Integer.compress(0x79d37ad6, 0x02406808))
66+
assertEquals(0x000001e2, Integer.compress(0xf555014c, 0x110590d0))
67+
assertEquals(0x0000009a, Integer.compress(0xf7e3e446, 0x02186085))
68+
assertEquals(0x000000ef, Integer.compress(0xbe25b6b9, 0x94081488))
69+
assertEquals(0x00000033, Integer.compress(0xc9c80a95, 0x40810490))
70+
assertEquals(0x0000004c, Integer.compress(0xf8fbd5c8, 0x13208204))
71+
assertEquals(0x000000b7, Integer.compress(0xba67e36f, 0x08a04528))
72+
assertEquals(0x0000005d, Integer.compress(0xbd49dddb, 0x00403505))
73+
assertEquals(0x00000008, Integer.compress(0x40c7f608, 0x00001821))
74+
assertEquals(0x00000004, Integer.compress(0xc663e6f4, 0x28008102))
75+
}
76+
77+
@Test def expand(): Unit = {
78+
// Example from the doc
79+
assertEquals(0xca00bab0, Integer.expand(0x000cabab, 0xff00fff0))
80+
81+
// Random test cases
82+
assertEquals(0x68804060, Integer.expand(0x89709d4b, 0x7a865060))
83+
assertEquals(0x03004400, Integer.expand(0x99933665, 0x0b505400))
84+
assertEquals(0x001c0000, Integer.expand(0x01d4851c, 0x101c1040))
85+
assertEquals(0x02400000, Integer.expand(0xd09d94a0, 0x1742a082))
86+
assertEquals(0x12c00002, Integer.expand(0x45ca9572, 0x1ac04203))
87+
assertEquals(0x004c0002, Integer.expand(0xf53bb659, 0x20ee0402))
88+
assertEquals(0x00104400, Integer.expand(0x3aca6e68, 0x00304e44))
89+
assertEquals(0x00028500, Integer.expand(0x80e5df8f, 0x00028500))
90+
assertEquals(0x10000010, Integer.expand(0x6ec079f2, 0x10002091))
91+
assertEquals(0x16828200, Integer.expand(0xfc8242fc, 0x5e828288))
92+
assertEquals(0x20104040, Integer.expand(0xccc51aaa, 0xa2184460))
93+
assertEquals(0x00100000, Integer.expand(0x8f673f64, 0x04520200))
94+
assertEquals(0x480000a0, Integer.expand(0xbf6fd8b3, 0x480420a0))
95+
assertEquals(0x04802100, Integer.expand(0x3be5a94a, 0x8580e980))
96+
assertEquals(0x41080000, Integer.expand(0xb03e6c68, 0x41282810))
97+
assertEquals(0x00830180, Integer.expand(0x2020edaf, 0x20c30180))
98+
assertEquals(0x00000001, Integer.expand(0xb385d407, 0x00000001))
99+
assertEquals(0x12500040, Integer.expand(0x416158fa, 0x12504060))
100+
assertEquals(0x48002000, Integer.expand(0x857ee772, 0x48806800))
101+
assertEquals(0xc001000c, Integer.expand(0xb7803dee, 0xe001000e))
102+
assertEquals(0x00200044, Integer.expand(0xb815b083, 0x002c8c44))
103+
assertEquals(0x00000008, Integer.expand(0x3587593b, 0x00000008))
104+
assertEquals(0xd8004804, Integer.expand(0xb5a433fa, 0xd8004905))
105+
assertEquals(0x00000021, Integer.expand(0x8b7e53b5, 0x00000031))
106+
assertEquals(0x02000008, Integer.expand(0x2f8a5041, 0x12023148))
107+
assertEquals(0x400400c9, Integer.expand(0x34d1dd9f, 0x620400c9))
108+
assertEquals(0x00000000, Integer.expand(0x9d6feff4, 0x00800100))
109+
assertEquals(0x00000000, Integer.expand(0x943fb671, 0x00000000))
110+
assertEquals(0x000c4000, Integer.expand(0x978edc70, 0x044c4232))
111+
assertEquals(0x00000002, Integer.expand(0x20162f69, 0x00000002))
112+
assertEquals(0x0040c200, Integer.expand(0x4be28cf0, 0x0040c24e))
113+
assertEquals(0x00005050, Integer.expand(0xfa162c33, 0x00005a50))
114+
assertEquals(0x80904c00, Integer.expand(0xc7f24ff6, 0x80905c80))
115+
assertEquals(0x10100002, Integer.expand(0x2c0da46a, 0x11108003))
116+
assertEquals(0x00000280, Integer.expand(0x01e9c326, 0x00002681))
117+
assertEquals(0x00000401, Integer.expand(0xa5978785, 0x00209601))
118+
assertEquals(0x80001002, Integer.expand(0xfd14e766, 0x80089003))
119+
assertEquals(0x00000800, Integer.expand(0xbd1ea1b2, 0x0000c820))
120+
assertEquals(0x00000028, Integer.expand(0xa07002e3, 0x00002928))
121+
assertEquals(0x00000000, Integer.expand(0x81eb15c0, 0x06200841))
122+
assertEquals(0x00402800, Integer.expand(0x79d37ad6, 0x02406808))
123+
assertEquals(0x10041080, Integer.expand(0xf555014c, 0x110590d0))
124+
assertEquals(0x00100084, Integer.expand(0xf7e3e446, 0x02186085))
125+
assertEquals(0x84081008, Integer.expand(0xbe25b6b9, 0x94081488))
126+
assertEquals(0x00800410, Integer.expand(0xc9c80a95, 0x40810490))
127+
assertEquals(0x10200000, Integer.expand(0xf8fbd5c8, 0x13208204))
128+
assertEquals(0x00a00528, Integer.expand(0xba67e36f, 0x08a04528))
129+
assertEquals(0x00401405, Integer.expand(0xbd49dddb, 0x00403505))
130+
assertEquals(0x00001000, Integer.expand(0x40c7f608, 0x00001821))
131+
assertEquals(0x20008000, Integer.expand(0xc663e6f4, 0x28008102))
132+
}
133+
134+
}

0 commit comments

Comments
 (0)