1 /*
2  * Copyright (c) 2013, Oracle and/or its affiliates. All rights reserved.
3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4  *
5  * This code is free software; you can redistribute it and/or modify it
6  * under the terms of the GNU General Public License version 2 only, as
7  * published by the Free Software Foundation.
8  *
9  * This code is distributed in the hope that it will be useful, but WITHOUT
10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
12  * version 2 for more details (a copy is included in the LICENSE file that
13  * accompanied this code).
14  *
15  * You should have received a copy of the GNU General Public License version
16  * 2 along with this work; if not, write to the Free Software Foundation,
17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18  *
19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20  * or visit www.oracle.com if you need additional information or have any
21  * questions.
22  */
23 
24 import java.math.BigInteger;
25 import java.util.Random;
26 import jdk.internal.math.FDBigInteger;
27 
28 /**
29  * @test
30  * @bug 7032154
31  * @summary unit testys of FDBigInteger
32  * @modules java.base/jdk.internal.math
33  * @author Dmitry Nadezhin
34  */
35 public class TestFDBigInteger {
36 
37     private static final int MAX_P5 = 413;
38     private static final int MAX_P2 = 65;
39     private static final long LONG_SIGN_MASK = (1L << 63);
40     private static final BigInteger FIVE = BigInteger.valueOf(5);
41     private static final FDBigInteger MUTABLE_ZERO = FDBigInteger.valueOfPow52(0, 0).leftInplaceSub(FDBigInteger.valueOfPow52(0, 0));
42     private static final FDBigInteger IMMUTABLE_ZERO = FDBigInteger.valueOfPow52(0, 0).leftInplaceSub(FDBigInteger.valueOfPow52(0, 0));
43     private static final FDBigInteger IMMUTABLE_MILLION = genMillion1();
44     private static final FDBigInteger IMMUTABLE_BILLION = genBillion1();
45     private static final FDBigInteger IMMUTABLE_TEN18 = genTen18();
46 
47     static {
IMMUTABLE_ZERO.makeImmutable()48         IMMUTABLE_ZERO.makeImmutable();
IMMUTABLE_MILLION.makeImmutable()49         IMMUTABLE_MILLION.makeImmutable();
IMMUTABLE_BILLION.makeImmutable()50         IMMUTABLE_BILLION.makeImmutable();
IMMUTABLE_TEN18.makeImmutable()51         IMMUTABLE_TEN18.makeImmutable();
52     }
53 
mutable(String hex, int offset)54     private static FDBigInteger mutable(String hex, int offset) {
55         char[] chars = new BigInteger(hex, 16).toString().toCharArray();
56         return new FDBigInteger(0, chars, 0, chars.length).multByPow52(0, offset * 32);
57     }
58 
immutable(String hex, int offset)59     private static FDBigInteger immutable(String hex, int offset) {
60         FDBigInteger fd = mutable(hex, offset);
61         fd.makeImmutable();
62         return fd;
63     }
64 
biPow52(int p5, int p2)65     private static BigInteger biPow52(int p5, int p2) {
66         return FIVE.pow(p5).shiftLeft(p2);
67     }
68 
69     // data.length == 1, nWords == 1, offset == 0
genMillion1()70     private static FDBigInteger genMillion1() {
71         return FDBigInteger.valueOfPow52(6, 0).leftShift(6);
72     }
73 
74     // data.length == 2, nWords == 1, offset == 0
genMillion2()75     private static FDBigInteger genMillion2() {
76         return FDBigInteger.valueOfMulPow52(1000000L, 0, 0);
77     }
78 
79     // data.length == 1, nWords == 1, offset == 0
genBillion1()80     private static FDBigInteger genBillion1() {
81         return FDBigInteger.valueOfPow52(9, 0).leftShift(9);
82     }
83 
84     // data.length == 2, nWords == 2, offset == 0
genTen18()85     private static FDBigInteger genTen18() {
86         return FDBigInteger.valueOfPow52(18, 0).leftShift(18);
87     }
88 
check(BigInteger expected, FDBigInteger actual, String message)89     private static void check(BigInteger expected, FDBigInteger actual, String message) throws Exception {
90         if (!expected.equals(actual.toBigInteger())) {
91             throw new Exception(message + " result " + actual.toHexString() + " expected " + expected.toString(16));
92         }
93     }
94 
testValueOfPow52(int p5, int p2)95     private static void testValueOfPow52(int p5, int p2) throws Exception {
96         check(biPow52(p5, p2), FDBigInteger.valueOfPow52(p5, p2),
97                 "valueOfPow52(" + p5 + "," + p2 + ")");
98     }
99 
testValueOfPow52()100     private static void testValueOfPow52() throws Exception {
101         for (int p5 = 0; p5 <= MAX_P5; p5++) {
102             for (int p2 = 0; p2 <= MAX_P2; p2++) {
103                 testValueOfPow52(p5, p2);
104             }
105         }
106     }
107 
testValueOfMulPow52(long value, int p5, int p2)108     private static void testValueOfMulPow52(long value, int p5, int p2) throws Exception {
109         BigInteger bi = BigInteger.valueOf(value & ~LONG_SIGN_MASK);
110         if (value < 0) {
111             bi = bi.setBit(63);
112         }
113         check(biPow52(p5, p2).multiply(bi), FDBigInteger.valueOfMulPow52(value, p5, p2),
114                 "valueOfMulPow52(" + Long.toHexString(value) + "." + p5 + "," + p2 + ")");
115     }
116 
testValueOfMulPow52(long value, int p5)117     private static void testValueOfMulPow52(long value, int p5) throws Exception {
118         testValueOfMulPow52(value, p5, 0);
119         testValueOfMulPow52(value, p5, 1);
120         testValueOfMulPow52(value, p5, 30);
121         testValueOfMulPow52(value, p5, 31);
122         testValueOfMulPow52(value, p5, 33);
123         testValueOfMulPow52(value, p5, 63);
124     }
125 
testValueOfMulPow52()126     private static void testValueOfMulPow52() throws Exception {
127         for (int p5 = 0; p5 <= MAX_P5; p5++) {
128             testValueOfMulPow52(0xFFFFFFFFL, p5);
129             testValueOfMulPow52(0x123456789AL, p5);
130             testValueOfMulPow52(0x7FFFFFFFFFFFFFFFL, p5);
131             testValueOfMulPow52(0xFFFFFFFFFFF54321L, p5);
132         }
133     }
134 
testLeftShift(FDBigInteger t, int shift, boolean isImmutable)135     private static void testLeftShift(FDBigInteger t, int shift, boolean isImmutable) throws Exception {
136         BigInteger bt = t.toBigInteger();
137         FDBigInteger r = t.leftShift(shift);
138         if ((bt.signum() == 0 || shift == 0 || !isImmutable) && r != t) {
139             throw new Exception("leftShift doesn't reuse its argument");
140         }
141         if (isImmutable) {
142             check(bt, t, "leftShift corrupts its argument");
143         }
144         check(bt.shiftLeft(shift), r, "leftShift returns wrong result");
145     }
146 
testLeftShift()147     private static void testLeftShift() throws Exception {
148         testLeftShift(IMMUTABLE_ZERO, 0, true);
149         testLeftShift(IMMUTABLE_ZERO, 10, true);
150         testLeftShift(MUTABLE_ZERO, 0, false);
151         testLeftShift(MUTABLE_ZERO, 10, false);
152 
153         testLeftShift(IMMUTABLE_MILLION, 0, true);
154         testLeftShift(IMMUTABLE_MILLION, 1, true);
155         testLeftShift(IMMUTABLE_MILLION, 12, true);
156         testLeftShift(IMMUTABLE_MILLION, 13, true);
157         testLeftShift(IMMUTABLE_MILLION, 32, true);
158         testLeftShift(IMMUTABLE_MILLION, 33, true);
159         testLeftShift(IMMUTABLE_MILLION, 44, true);
160         testLeftShift(IMMUTABLE_MILLION, 45, true);
161 
162         testLeftShift(genMillion1(), 0, false);
163         testLeftShift(genMillion1(), 1, false);
164         testLeftShift(genMillion1(), 12, false);
165         testLeftShift(genMillion1(), 13, false);
166         testLeftShift(genMillion1(), 25, false);
167         testLeftShift(genMillion1(), 26, false);
168         testLeftShift(genMillion1(), 32, false);
169         testLeftShift(genMillion1(), 33, false);
170         testLeftShift(genMillion1(), 44, false);
171         testLeftShift(genMillion1(), 45, false);
172 
173         testLeftShift(genMillion2(), 0, false);
174         testLeftShift(genMillion2(), 1, false);
175         testLeftShift(genMillion2(), 12, false);
176         testLeftShift(genMillion2(), 13, false);
177         testLeftShift(genMillion2(), 25, false);
178         testLeftShift(genMillion2(), 26, false);
179         testLeftShift(genMillion2(), 32, false);
180         testLeftShift(genMillion2(), 33, false);
181         testLeftShift(genMillion2(), 44, false);
182         testLeftShift(genMillion2(), 45, false);
183     }
184 
testQuoRemIteration(FDBigInteger t, FDBigInteger s)185     private static void testQuoRemIteration(FDBigInteger t, FDBigInteger s) throws Exception {
186         BigInteger bt = t.toBigInteger();
187         BigInteger bs = s.toBigInteger();
188         int q = t.quoRemIteration(s);
189         BigInteger[] qr = bt.divideAndRemainder(bs);
190         if (!BigInteger.valueOf(q).equals(qr[0])) {
191             throw new Exception("quoRemIteration returns incorrect quo");
192         }
193         check(qr[1].multiply(BigInteger.TEN), t, "quoRemIteration returns incorrect rem");
194     }
195 
testQuoRemIteration()196     private static void testQuoRemIteration() throws Exception {
197         // IMMUTABLE_TEN18 == 0de0b6b3a7640000
198         // q = 0
199         testQuoRemIteration(mutable("00000001", 0), IMMUTABLE_TEN18);
200         testQuoRemIteration(mutable("00000001", 1), IMMUTABLE_TEN18);
201         testQuoRemIteration(mutable("0de0b6b2", 1), IMMUTABLE_TEN18);
202         // q = 1 -> q = 0
203         testQuoRemIteration(mutable("0de0b6b3", 1), IMMUTABLE_TEN18);
204         testQuoRemIteration(mutable("0de0b6b3a763FFFF", 0), IMMUTABLE_TEN18);
205         // q = 1
206         testQuoRemIteration(mutable("0de0b6b3a7640000", 0), IMMUTABLE_TEN18);
207         testQuoRemIteration(mutable("0de0b6b3FFFFFFFF", 0), IMMUTABLE_TEN18);
208         testQuoRemIteration(mutable("8ac72304", 1), IMMUTABLE_TEN18);
209         testQuoRemIteration(mutable("0de0b6b400000000", 0), IMMUTABLE_TEN18);
210         testQuoRemIteration(mutable("8ac72305", 1), IMMUTABLE_TEN18);
211         // q = 18
212         testQuoRemIteration(mutable("FFFFFFFF", 1), IMMUTABLE_TEN18);
213     }
214 
testCmp(FDBigInteger t, FDBigInteger o)215     private static void testCmp(FDBigInteger t, FDBigInteger o) throws Exception {
216         BigInteger bt = t.toBigInteger();
217         BigInteger bo = o.toBigInteger();
218         int cmp = t.cmp(o);
219         int bcmp = bt.compareTo(bo);
220         if (bcmp != cmp) {
221             throw new Exception("cmp returns " + cmp + " expected " + bcmp);
222         }
223         check(bt, t, "cmp corrupts this");
224         check(bo, o, "cmp corrupts other");
225         if (o.cmp(t) != -cmp) {
226             throw new Exception("asymmetrical cmp");
227         }
228         check(bt, t, "cmp corrupts this");
229         check(bo, o, "cmp corrupts other");
230     }
231 
testCmp()232     private static void testCmp() throws Exception {
233         testCmp(mutable("FFFFFFFF", 0), mutable("100000000", 0));
234         testCmp(mutable("FFFFFFFF", 0), mutable("1", 1));
235         testCmp(mutable("5", 0), mutable("6", 0));
236         testCmp(mutable("5", 0), mutable("5", 0));
237         testCmp(mutable("5000000001", 0), mutable("500000001", 0));
238         testCmp(mutable("5000000001", 0), mutable("6", 1));
239         testCmp(mutable("5000000001", 0), mutable("5", 1));
240         testCmp(mutable("5000000000", 0), mutable("5", 1));
241     }
242 
testCmpPow52(FDBigInteger t, int p5, int p2)243     private static void testCmpPow52(FDBigInteger t, int p5, int p2) throws Exception {
244         FDBigInteger o = FDBigInteger.valueOfPow52(p5, p2);
245         BigInteger bt = t.toBigInteger();
246         BigInteger bo = biPow52(p5, p2);
247         int cmp = t.cmp(o);
248         int bcmp = bt.compareTo(bo);
249         if (bcmp != cmp) {
250             throw new Exception("cmpPow52 returns " + cmp + " expected " + bcmp);
251         }
252         check(bt, t, "cmpPow52 corrupts this");
253         check(bo, o, "cmpPow5 corrupts other");
254     }
255 
testCmpPow52()256     private static void testCmpPow52() throws Exception {
257         testCmpPow52(mutable("00000002", 1), 0, 31);
258         testCmpPow52(mutable("00000002", 1), 0, 32);
259         testCmpPow52(mutable("00000002", 1), 0, 33);
260         testCmpPow52(mutable("00000002", 1), 0, 34);
261         testCmpPow52(mutable("00000002", 1), 0, 64);
262         testCmpPow52(mutable("00000003", 1), 0, 32);
263         testCmpPow52(mutable("00000003", 1), 0, 33);
264         testCmpPow52(mutable("00000003", 1), 0, 34);
265     }
266 
testAddAndCmp(FDBigInteger t, FDBigInteger x, FDBigInteger y)267     private static void testAddAndCmp(FDBigInteger t, FDBigInteger x, FDBigInteger y) throws Exception {
268         BigInteger bt = t.toBigInteger();
269         BigInteger bx = x.toBigInteger();
270         BigInteger by = y.toBigInteger();
271         int cmp = t.addAndCmp(x, y);
272         int bcmp = bt.compareTo(bx.add(by));
273         if (bcmp != cmp) {
274             throw new Exception("addAndCmp returns " + cmp + " expected " + bcmp);
275         }
276         check(bt, t, "addAndCmp corrupts this");
277         check(bx, x, "addAndCmp corrupts x");
278         check(by, y, "addAndCmp corrupts y");
279     }
280 
testAddAndCmp()281     private static void testAddAndCmp() throws Exception {
282         testAddAndCmp(MUTABLE_ZERO, MUTABLE_ZERO, MUTABLE_ZERO);
283         testAddAndCmp(mutable("00000001", 0), MUTABLE_ZERO, MUTABLE_ZERO);
284         testAddAndCmp(mutable("00000001", 0), mutable("00000001", 0), MUTABLE_ZERO);
285         testAddAndCmp(mutable("00000001", 0), MUTABLE_ZERO, mutable("00000001", 0));
286         testAddAndCmp(mutable("00000001", 0), mutable("00000002", 0), MUTABLE_ZERO);
287         testAddAndCmp(mutable("00000001", 0), MUTABLE_ZERO, mutable("00000002", 0));
288         testAddAndCmp(mutable("00000001", 2), mutable("FFFFFFFF", 0), mutable("FFFFFFFF", 0));
289         testAddAndCmp(mutable("00000001", 0), mutable("00000001", 1), mutable("00000001", 0));
290 
291         testAddAndCmp(mutable("00000001", 2), mutable("0F0F0F0F80000000", 1), mutable("F0F0F0F080000000", 1));
292         testAddAndCmp(mutable("00000001", 2), mutable("0F0F0F0E80000000", 1), mutable("F0F0F0F080000000", 1));
293 
294         testAddAndCmp(mutable("00000002", 1), mutable("0000000180000000", 1), mutable("0000000280000000", 1));
295         testAddAndCmp(mutable("00000003", 1), mutable("0000000180000000", 1), mutable("0000000280000000", 1));
296         testAddAndCmp(mutable("00000004", 1), mutable("0000000180000000", 1), mutable("0000000280000000", 1));
297         testAddAndCmp(mutable("00000005", 1), mutable("0000000180000000", 1), mutable("0000000280000000", 1));
298 
299         testAddAndCmp(mutable("00000001", 2), mutable("8000000000000000", 0), mutable("8000000000000000", 0));
300         testAddAndCmp(mutable("00000001", 2), mutable("8000000000000000", 0), mutable("8000000000000001", 0));
301         testAddAndCmp(mutable("00000002", 2), mutable("8000000000000000", 0), mutable("8000000000000000", 0));
302         testAddAndCmp(mutable("00000003", 2), mutable("8000000000000000", 0), mutable("8000000000000000", 0));
303     }
304 
testMultBy10(FDBigInteger t, boolean isImmutable)305     private static void testMultBy10(FDBigInteger t, boolean isImmutable) throws Exception {
306         BigInteger bt = t.toBigInteger();
307         FDBigInteger r = t.multBy10();
308         if ((bt.signum() == 0 || !isImmutable) && r != t) {
309             throw new Exception("multBy10 of doesn't reuse its argument");
310         }
311         if (isImmutable) {
312             check(bt, t, "multBy10 corrupts its argument");
313         }
314         check(bt.multiply(BigInteger.TEN), r, "multBy10 returns wrong result");
315     }
316 
testMultBy10()317     private static void testMultBy10() throws Exception {
318         for (int p5 = 0; p5 <= MAX_P5; p5++) {
319             for (int p2 = 0; p2 <= MAX_P2; p2++) {
320                 // This strange way of creating a value ensures that it is mutable.
321                 FDBigInteger value = FDBigInteger.valueOfPow52(0, 0).multByPow52(p5, p2);
322                 testMultBy10(value, false);
323                 value.makeImmutable();
324                 testMultBy10(value, true);
325             }
326         }
327     }
328 
testMultByPow52(FDBigInteger t, int p5, int p2)329     private static void testMultByPow52(FDBigInteger t, int p5, int p2) throws Exception {
330         BigInteger bt = t.toBigInteger();
331         FDBigInteger r = t.multByPow52(p5, p2);
332         if (bt.signum() == 0 && r != t) {
333             throw new Exception("multByPow52 of doesn't reuse its argument");
334         }
335         check(bt.multiply(biPow52(p5, p2)), r, "multByPow52 returns wrong result");
336     }
337 
testMultByPow52()338     private static void testMultByPow52() throws Exception {
339         for (int p5 = 0; p5 <= MAX_P5; p5++) {
340             for (int p2 = 0; p2 <= MAX_P2; p2++) {
341                 // This strange way of creating a value ensures that it is mutable.
342                 FDBigInteger value = FDBigInteger.valueOfPow52(0, 0).multByPow52(p5, p2);
343                 testMultByPow52(value, p5, p2);
344             }
345         }
346     }
347 
testLeftInplaceSub(FDBigInteger left, FDBigInteger right, boolean isImmutable)348     private static void testLeftInplaceSub(FDBigInteger left, FDBigInteger right, boolean isImmutable) throws Exception {
349         BigInteger biLeft = left.toBigInteger();
350         BigInteger biRight = right.toBigInteger();
351         FDBigInteger diff = left.leftInplaceSub(right);
352         if (!isImmutable && diff != left) {
353             throw new Exception("leftInplaceSub of doesn't reuse its argument");
354         }
355         if (isImmutable) {
356             check(biLeft, left, "leftInplaceSub corrupts its left immutable argument");
357         }
358         check(biRight, right, "leftInplaceSub corrupts its right argument");
359         check(biLeft.subtract(biRight), diff, "leftInplaceSub returns wrong result");
360     }
361 
testLeftInplaceSub()362     private static void testLeftInplaceSub() throws Exception {
363         for (int p5 = 0; p5 <= MAX_P5; p5++) {
364             for (int p2 = 0; p2 <= MAX_P2; p2++) {
365 //                for (int p5r = 0; p5r <= p5; p5r += 10) {
366 //                    for (int p2r = 0; p2r <= p2; p2r += 10) {
367                 for (int p5r = 0; p5r <= p5; p5r++) {
368                     for (int p2r = 0; p2r <= p2; p2r++) {
369                         // This strange way of creating a value ensures that it is mutable.
370                         FDBigInteger left = FDBigInteger.valueOfPow52(0, 0).multByPow52(p5, p2);
371                         FDBigInteger right = FDBigInteger.valueOfPow52(0, 0).multByPow52(p5r, p2r);
372                         testLeftInplaceSub(left, right, false);
373                         left = FDBigInteger.valueOfPow52(0, 0).multByPow52(p5, p2);
374                         left.makeImmutable();
375                         testLeftInplaceSub(left, right, true);
376                     }
377                 }
378             }
379         }
380     }
381 
testRightInplaceSub(FDBigInteger left, FDBigInteger right, boolean isImmutable)382     private static void testRightInplaceSub(FDBigInteger left, FDBigInteger right, boolean isImmutable) throws Exception {
383         BigInteger biLeft = left.toBigInteger();
384         BigInteger biRight = right.toBigInteger();
385         FDBigInteger diff = left.rightInplaceSub(right);
386         if (!isImmutable && diff != right) {
387             throw new Exception("rightInplaceSub of doesn't reuse its argument");
388         }
389         check(biLeft, left, "leftInplaceSub corrupts its left argument");
390         if (isImmutable) {
391             check(biRight, right, "leftInplaceSub corrupts its right immutable argument");
392         }
393         try {
394             check(biLeft.subtract(biRight), diff, "rightInplaceSub returns wrong result");
395         } catch (Exception e) {
396             System.out.println(biLeft+" - "+biRight+" = "+biLeft.subtract(biRight));
397             throw e;
398         }
399     }
400 
testRightInplaceSub()401     private static void testRightInplaceSub() throws Exception {
402         for (int p5 = 0; p5 <= MAX_P5; p5++) {
403             for (int p2 = 0; p2 <= MAX_P2; p2++) {
404 //                for (int p5r = 0; p5r <= p5; p5r += 10) {
405 //                    for (int p2r = 0; p2r <= p2; p2r += 10) {
406                 for (int p5r = 0; p5r <= p5; p5r++) {
407                     for (int p2r = 0; p2r <= p2; p2r++) {
408                         // This strange way of creating a value ensures that it is mutable.
409                         FDBigInteger left = FDBigInteger.valueOfPow52(0, 0).multByPow52(p5, p2);
410                         FDBigInteger right = FDBigInteger.valueOfPow52(0, 0).multByPow52(p5r, p2r);
411                         testRightInplaceSub(left, right, false);
412                         right = FDBigInteger.valueOfPow52(0, 0).multByPow52(p5r, p2r);
413                         right.makeImmutable();
414                         testRightInplaceSub(left, right, true);
415                     }
416                 }
417             }
418         }
419     }
420 
main(String[] args)421     public static void main(String[] args) throws Exception {
422         testValueOfPow52();
423         testValueOfMulPow52();
424         testLeftShift();
425         testQuoRemIteration();
426         testCmp();
427         testCmpPow52();
428         testAddAndCmp();
429         // Uncomment the following for more comprehensize but slow testing.
430         // testLeftInplaceSub();
431         // testMultBy10();
432         // testMultByPow52();
433         // testRightInplaceSub();
434     }
435 }
436