8000 Implement jl.Math.{multiplyFull, multiplyHigh, unsignedMultiplyHigh}. · scala-js/scala-js@87e5ed7 · GitHub
[go: up one dir, main page]
Skip to content

Commit 87e5ed7

Browse files
sjrdsjrd
committed
Implement jl.Math.{multiplyFull, multiplyHigh, unsignedMultiplyHigh}.
1 parent 352df74 commit 87e5ed7

File tree

3 files changed

+242
-0
lines changed

3 files changed

+242
-0
lines changed

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

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -462,6 +462,42 @@ object Math {
462462
if (a >= Integer.MIN_VALUE && a <= Integer.MAX_VALUE) a.toInt
463463
else throw new ArithmeticException("Integer overflow")
464464

465+
@inline
466+
def multiplyFull(x: scala.Int, y: scala.Int): scala.Long =
467+
x.toLong * y.toLong
468+
469+
@inline
470+
def multiplyHigh(x: scala.Long, y: scala.Long): scala.Long = {
471+
/* Hacker's Delight, Section 8-2, Figure 8-2,
472+
* where we have "inlined" all the variables used only once to help our
473+
* optimizer perform simplifications.
474+
*/
475+
476+
val x0 = x & 0xffffffffL
477+
val x1 = x >> 32
478+
val y0 = y & 0xffffffffL
479+
val y1 = y >> 32
480+
481+
val t = x1 * y0 + ((x0 * y0) >>> 32)
482+
x1 * y1 + (t >> 32) + (((t & 0xffffffffL) + x0 * y1) >> 32)
483+
}
484+
485+
@inline
486+
def unsignedMultiplyHigh(x: scala.Long, y: scala.Long): scala.Long = {
487+
/* Hacker's Delight, Section 8-2:
488+
* > For an unsigned version, simply change all the int declarations to unsigned.
489+
* In Scala, that means changing all the >> into >>>.
490+
*/
491+
492+
val x0 = x & 0xffffffffL
493+
val x1 = x >>> 32
494+
val y0 = y & 0xffffffffL
495+
val y1 = y >>> 32
496+
497+
val t = x1 * y0 + ((x0 * y0) >>> 32)
498+
x1 * y1 + (t >>> 32) + (((t & 0xffffffffL) + x0 * y1) >>> 32)
499+
}
500+
465501
def floorDiv(a: scala.Int, b: scala.Int): scala.Int = {
466502
val quot = a / b
467503
if ((a < 0) == (b < 0) || quot * b == a) quot

‎test-suite/shared/src/test/require-jdk11/org/scalajs/testsuite/javalib/lang/MathTestOnJDK11.scala

Lines changed: 152 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,152 @@
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 java.math.BigInteger
16+
import java.util.SplittableRandom
17+
18+
import org.junit.Test
19+
import org.junit.Assert._
20+
21+
class MathTestOnJDK11 {
22+
23+
@Test def testMultiplyFull(): Unit = {
24+
assertEquals(2641928036408725662L, Math.multiplyFull(1942041231, 1360387202))
25+
assertEquals(54843908448922272L, Math.multiplyFull(1565939409, 35023008))
26+
assertEquals(510471553407128558L, Math.multiplyFull(1283300489, 397780222))
27+
assertEquals(-1211162085735907941L, Math.multiplyFull(-1990140693, 608581137))
28+
assertEquals(-1197265696701533712L, Math.multiplyFull(-584098468, 2049766884))
29+
assertEquals(203152587796496856L, Math.multiplyFull(-1809591416, -112264341))
30+
assertEquals(-1869763755321108598L, Math.multiplyFull(1235591906, -1513253483))
31+
assertEquals(-737954189546644064L, Math.multiplyFull(675415792, -1092592442))
32+
assertEquals(-2570904460570261986L, Math.multiplyFull(1639253754, -1568338309))
33+
assertEquals(1106623967126000400L, Math.multiplyFull(2088029790, 529984760))
34+
assertEquals(1407516248272451352L, Math.multiplyFull(-869881054, -1618055988))
35+
assertEquals(-2120367337662071940L, Math.multiplyFull(-1558894530, 1360173698))
36+
assertEquals(-1464086284066637244L, Math.multiplyFull(-1417313902, 1033000722))
37+
assertEquals(36729253163312334L, Math.multiplyFull(-1673852034, -21942951))
38+
assertEquals(-3197007331876781046L, Math.multiplyFull(1876799847, -1703435418))
39+
assertEquals(461794994386945009L, Math.multiplyFull(-246001091, -1877207099))
40+
assertEquals(-1206231192496917804L, Math.multiplyFull(867896526, -1389832954))
41+
assertEquals(-1739671893103255929L, Math.multiplyFull(-1083992841, 1604873969))
42+
assertEquals(-409626127116780624L, Math.multiplyFull(240101424, -1706054551))
43+
assertEquals(-3083566560548370936L, Math.multiplyFull(-1568530113, 1965895672))
44+
assertEquals(-1205028798380605000L, Math.multiplyFull(-1201743532, 1002733750))
45+
assertEquals(-1328689065035027168L, Math.multiplyFull(929349664, -1429697687))
46+
assertEquals(-124212693522020684L, Math.multiplyFull(80893862, -1535502082))
47+
assertEquals(-82341860111074830L, Math.multiplyFull(-243230690, 338534007))
48+
assertEquals(-846837059701860202L, Math.multiplyFull(1959770926, -432110227))
49+
assertEquals(335728245390354432L, Math.multiplyFull(506816728, 662425344))
50+
assertEquals(745294755971022170L, Math.multiplyFull(1521993302, 489683335))
51+
assertEquals(-2370525755201631608L, Math.multiplyFull(2023520366, -1171485988))
52+
assertEquals(-1039854583047715776L, Math.multiplyFull(593162592, -1753068378))
53+
assertEquals(-152985384388127808L, Math.multiplyFull(-635946432, 240563319))
54+
assertEquals(-678107568956539050L, Math.multiplyFull(649113254, -1044667575))
55+
assertEquals(-3064094283703186444L, Math.multiplyFull(-1890896836, 1620444979))
56+
assertEquals(1240687269228318870L, Math.multiplyFull(-1080325230, -1148438669))
57+
assertEquals(-46551523496333580L, Math.multiplyFull(27167878, -1713476610))
58+
assertEquals(-2500430606368427103L, Math.multiplyFull(2023288183, -1235825241))
59+
assertEquals(92963399778762084L, Math.multiplyFull(896198732, 103730787))
60+
assertEquals(2469065794894324667L, Math.multiplyFull(2105111101, 1172890967))
61+
assertEquals(172558569988357136L, Math.multiplyFull(-142945148, -1207166332))
62+
assertEquals(335684786634110970L, Math.multiplyFull(-1647598405, -203741874))
63+
assertEquals(2406859843746696240L, Math.multiplyFull(2049365815, 1174441296))
64+
assertEquals(3100973294006114952L, Math.multiplyFull(1991928152, 1556769651))
65+
assertEquals(-335912134649077352L, Math.multiplyFull(866240524, -387781598))
66+
assertEquals(84303320581066207L, Math.multiplyFull(75666091, 1114149277))
67+
assertEquals(-2623126349572207976L, Math.multiplyFull(1426933667, -1838295928))
68+
assertEquals(59139945163750590L, Math.multiplyFull(149344270, 395997417))
69+
assertEquals(-105764175098643999L, Math.multiplyFull(68726447, -1538915217))
70+
assertEquals(8595303129864000L, Math.multiplyFull(726092025, 11837760))
71+
assertEquals(-2958527843471399088L, Math.multiplyFull(1536412078, -1925608296))
72+
assertEquals(1532625839159904477L, Math.multiplyFull(867021537, 1767690621))
73+
assertEquals(384402376484481316L, Math.multiplyFull(1207235521, 318415396))
74+
assertEquals(-219376614576542698L, Math.multiplyFull(1816299166, -120782203))
75+
assertEquals(-672138807810988440L, Math.multiplyFull(531516745, -1264567512))
76+
assertEquals(-193351903065245331L, Math.multiplyFull(170858169, -1131651499))
77+
assertEquals(71263251057597648L, Math.multiplyFull(51058196, 1395725988))
78+
assertEquals(-774312974742971385L, Math.multiplyFull(1958551603, -395349795))
79+
assertEquals(-1846593638370672048L, Math.multiplyFull(1190143097, -1551572784))
80+
assertEquals(240083094242536384L, Math.multiplyFull(1404614968, 170924488))
81+
assertEquals(-130950827889833280L, Math.multiplyFull(-115480554, 1133964320))
82+
assertEquals(128954457719585228L, Math.multiplyFull(735993884, 175211317))
83+
assertEquals(364779990580792000L, Math.multiplyFull(-668489125, -545678272))
84+
assertEquals(107252402494512045L, Math.multiplyFull(759517757, 141211185))
85+
assertEquals(3038084150893069044L, Math.multiplyFull(-1924640913, -1578519988))
86+
assertEquals(760804294233336624L, Math.multiplyFull(-728394552, -1044494762))
87+
assertEquals(1171051779605774913L, Math.multiplyFull(848233701, 1380576813))
88+
assertEquals(-1805862307837393080L, Math.multiplyFull(-1385644986, 1303264780))
89+
assertEquals(172227703288618734L, Math.multiplyFull(-104999826, -1640266559))
90+
assertEquals(150448013961014407L, Math.multiplyFull(163398103, 920745169))
91+
assertEquals(-671469201380991232L, Math.multiplyFull(650262784, -1032612073))
92+
assertEquals(-1325861126942924945L, Math.multiplyFull(-1773644581, 747534845))
93+
assertEquals(987406376890116568L, Math.multiplyFull(-1626507773, -607071416))
94+
assertEquals(2918138947401192144L, Math.multiplyFull(1695881208, 1720721318))
95+
assertEquals(-2590993826910153940L, Math.multiplyFull(-1397240042, 1854365570))
96+
assertEquals(954644624447419276L, Math.multiplyFull(-1516139806, -629654746))
97+
assertEquals(407510452326678620L, Math.multiplyFull(-384747652, -1059162935))
98+
assertEquals(149866317537821404L, Math.multiplyFull(1530355444, 97929091))
99+
assertEquals(922044716091910632L, Math.multiplyFull(968149268, 952378674))
100+
assertEquals(-3508732521573808284L, Math.multiplyFull(1825364562, -1922209182))
101+
assertEquals(1701723136959404304L, Math.multiplyFull(894776752, 1901841027))
102+
assertEquals(-2435876799625512705L, Math.multiplyFull(-1276062909, 1908900245))
103+
assertEquals(-516933170985379201L, Math.multiplyFull(657063047, -786732983))
104+
assertEquals(123334479976750576L, Math.multiplyFull(313765817, 393078128))
105+
assertEquals(-1072624004420456775L, Math.multiplyFull(-894199299, 1199535725))
106+
assertEquals(301682711612188737L, Math.multiplyFull(330918981, 911651277))
107+
assertEquals(1790992996470651507L, Math.multiplyFull(-1115945231, -1604911197))
108+
assertEquals(-2750453268538140155L, Math.multiplyFull(1878389719, -1464261245))
 EED3
109+
assertEquals(758285757353272504L, Math.multiplyFull(1259684942, 601964612))
110+
assertEquals(-218581674312137400L, Math.multiplyFull(-161533394, 1353167100))
111+
assertEquals(-1824007072461951836L, Math.multiplyFull(-1244277844, 1465916219))
112+
assertEquals(-92753167730460334L, Math.multiplyFull(-65368843, 1418920138))
113+
assertEquals(-2326636630979491248L, Math.multiplyFull(1124395877, -2069232624))
114+
assertEquals(-7380586257943446L, Math.multiplyFull(29715454, -248375349))
115+
assertEquals(31319707234597638L, Math.multiplyFull(491995506, 63658523))
116+
assertEquals(-1196559502630778250L, Math.multiplyFull(-1752963990, 682592175))
117+
assertEquals(166065559841839548L, Math.multiplyFull(-911521074, -182185102))
118+
assertEquals(-1222260378510810100L, Math.multiplyFull(1071539812, -1140657925))
119+
assertEquals(57800571165871464L, Math.multiplyFull(-257569032, -224408077))
120+
assertEquals(332444627169725608L, Math.multiplyFull(1247224172, 266547614))
121+
assertEquals(217903869180130650L, Math.multiplyFull(1069161915, 203808110))
122+
assertEquals(920425054266935850L, Math.multiplyFull(-901689546, -1020778225))
123+
assertEquals(-507632632656614388L, Math.multiplyFull(864632142, -587108214))
124+
}
125+
126+
@Test def testMultiplyHigh(): Unit = {
127+
/* We fuzz-test by comparing to the "obvious" implementations based on
128+
* BigIntegers. We use a SplittableRandom generator, because Random cannot
129+
* generate all Long values.
130+
*/
131+
132+
val Seed = 909209754851418882L
133+
val Rounds = 1024
134+
135+
val gen = new SplittableRandom(Seed)
136+
137+
for (round <- 1 to Rounds) {
138+
val x = gen.nextLong()
139+
val y = gen.nextLong()
140+
141+
val expected = {
142+
BigInteger.valueOf(x)
143+
.multiply(BigInteger.valueOf(y))
144+
.shiftRight(64)
145+
.longValue()
146+
}
147+
148+
assertEquals(s"round $round, x = $x, y = $y", expected, Math.multiplyHigh(x, y))
149+
}
150+
}
151+
152+
}

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

Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
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 java.math.BigInteger
16+
import java.util.SplittableRandom
17+
18+
import org.junit.Test
19+
import org.junit.Assert._
20+
21+
class MathTestOnJDK21 {
22+
23+
@Test def testUnsignedMultiplyHigh(): Unit = {
24+
/* We fuzz-test by comparing to the "obvious" implementations based on
25+
* BigIntegers. We use a SplittableRandom generator, because Random cannot
26+
* generate all Long values.
27+
*/
28+
29+
val Seed = 909209754851418882L
30+
val Rounds = 1024
31+
32+
val gen = new SplittableRandom(Seed)
33+
34+
val mask = BigInteger.ONE.shiftLeft(64).subtract(BigInteger.ONE)
35+
36+
def ulongToBigInteger(a: Long): BigInteger =
37+
BigInteger.valueOf(a).and(mask)
38+
39+
for (round <- 1 to Rounds) {
40+
val x = gen.nextLong()
41+
val y = gen.nextLong()
42+
43+
val expected = {
44+
ulongToBigInteger(x)
45+
.multiply(ulongToBigInteger(y))
46+
.shiftRight(64)
47+
.longValue()
48+
}
49+
50+
assertEquals(s"round $round, x = $x, y = $y", expected, Math.unsignedMultiplyHigh(x, y))
51+
}
52+
}
53+
54+
}

0 commit comments

Comments
 (0)
0