1 package org.bouncycastle.math.raw;
2 
3 import java.math.BigInteger;
4 
5 import org.bouncycastle.util.Pack;
6 
7 public abstract class Nat
8 {
9     private static final long M = 0xFFFFFFFFL;
10 
add(int len, int[] x, int[] y, int[] z)11     public static int add(int len, int[] x, int[] y, int[] z)
12     {
13         long c = 0;
14         for (int i = 0; i < len; ++i)
15         {
16             c += (x[i] & M) + (y[i] & M);
17             z[i] = (int)c;
18             c >>>= 32;
19         }
20         return (int)c;
21     }
22 
add33At(int len, int x, int[] z, int zPos)23     public static int add33At(int len, int x, int[] z, int zPos)
24     {
25         // assert zPos <= (len - 2);
26         long c = (z[zPos + 0] & M) + (x & M);
27         z[zPos + 0] = (int)c;
28         c >>>= 32;
29         c += (z[zPos + 1] & M) + 1L;
30         z[zPos + 1] = (int)c;
31         c >>>= 32;
32         return c == 0 ? 0 : incAt(len, z, zPos + 2);
33     }
34 
add33At(int len, int x, int[] z, int zOff, int zPos)35     public static int add33At(int len, int x, int[] z, int zOff, int zPos)
36     {
37         // assert zPos <= (len - 2);
38         long c = (z[zOff + zPos] & M) + (x & M);
39         z[zOff + zPos] = (int)c;
40         c >>>= 32;
41         c += (z[zOff + zPos + 1] & M) + 1L;
42         z[zOff + zPos + 1] = (int)c;
43         c >>>= 32;
44         return c == 0 ? 0 : incAt(len, z, zOff, zPos + 2);
45     }
46 
add33To(int len, int x, int[] z)47     public static int add33To(int len, int x, int[] z)
48     {
49         long c = (z[0] & M) + (x & M);
50         z[0] = (int)c;
51         c >>>= 32;
52         c += (z[1] & M) + 1L;
53         z[1] = (int)c;
54         c >>>= 32;
55         return c == 0 ? 0 : incAt(len, z, 2);
56     }
57 
add33To(int len, int x, int[] z, int zOff)58     public static int add33To(int len, int x, int[] z, int zOff)
59     {
60         long c = (z[zOff + 0] & M) + (x & M);
61         z[zOff + 0] = (int)c;
62         c >>>= 32;
63         c += (z[zOff + 1] & M) + 1L;
64         z[zOff + 1] = (int)c;
65         c >>>= 32;
66         return c == 0 ? 0 : incAt(len, z, zOff, 2);
67     }
68 
addBothTo(int len, int[] x, int[] y, int[] z)69     public static int addBothTo(int len, int[] x, int[] y, int[] z)
70     {
71         long c = 0;
72         for (int i = 0; i < len; ++i)
73         {
74             c += (x[i] & M) + (y[i] & M) + (z[i] & M);
75             z[i] = (int)c;
76             c >>>= 32;
77         }
78         return (int)c;
79     }
80 
addBothTo(int len, int[] x, int xOff, int[] y, int yOff, int[] z, int zOff)81     public static int addBothTo(int len, int[] x, int xOff, int[] y, int yOff, int[] z, int zOff)
82     {
83         long c = 0;
84         for (int i = 0; i < len; ++i)
85         {
86             c += (x[xOff + i] & M) + (y[yOff + i] & M) + (z[zOff + i] & M);
87             z[zOff + i] = (int)c;
88             c >>>= 32;
89         }
90         return (int)c;
91     }
92 
addDWordAt(int len, long x, int[] z, int zPos)93     public static int addDWordAt(int len, long x, int[] z, int zPos)
94     {
95         // assert zPos <= (len - 2);
96         long c = (z[zPos + 0] & M) + (x & M);
97         z[zPos + 0] = (int)c;
98         c >>>= 32;
99         c += (z[zPos + 1] & M) + (x >>> 32);
100         z[zPos + 1] = (int)c;
101         c >>>= 32;
102         return c == 0 ? 0 : incAt(len, z, zPos + 2);
103     }
104 
addDWordAt(int len, long x, int[] z, int zOff, int zPos)105     public static int addDWordAt(int len, long x, int[] z, int zOff, int zPos)
106     {
107         // assert zPos <= (len - 2);
108         long c = (z[zOff + zPos] & M) + (x & M);
109         z[zOff + zPos] = (int)c;
110         c >>>= 32;
111         c += (z[zOff + zPos + 1] & M) + (x >>> 32);
112         z[zOff + zPos + 1] = (int)c;
113         c >>>= 32;
114         return c == 0 ? 0 : incAt(len, z, zOff, zPos + 2);
115     }
116 
addDWordTo(int len, long x, int[] z)117     public static int addDWordTo(int len, long x, int[] z)
118     {
119         long c = (z[0] & M) + (x & M);
120         z[0] = (int)c;
121         c >>>= 32;
122         c += (z[1] & M) + (x >>> 32);
123         z[1] = (int)c;
124         c >>>= 32;
125         return c == 0 ? 0 : incAt(len, z, 2);
126     }
127 
addDWordTo(int len, long x, int[] z, int zOff)128     public static int addDWordTo(int len, long x, int[] z, int zOff)
129     {
130         long c = (z[zOff + 0] & M) + (x & M);
131         z[zOff + 0] = (int)c;
132         c >>>= 32;
133         c += (z[zOff + 1] & M) + (x >>> 32);
134         z[zOff + 1] = (int)c;
135         c >>>= 32;
136         return c == 0 ? 0 : incAt(len, z, zOff, 2);
137     }
138 
addTo(int len, int[] x, int[] z)139     public static int addTo(int len, int[] x, int[] z)
140     {
141         long c = 0;
142         for (int i = 0; i < len; ++i)
143         {
144             c += (x[i] & M) + (z[i] & M);
145             z[i] = (int)c;
146             c >>>= 32;
147         }
148         return (int)c;
149     }
150 
addTo(int len, int[] x, int xOff, int[] z, int zOff)151     public static int addTo(int len, int[] x, int xOff, int[] z, int zOff)
152     {
153         long c = 0;
154         for (int i = 0; i < len; ++i)
155         {
156             c += (x[xOff + i] & M) + (z[zOff + i] & M);
157             z[zOff + i] = (int)c;
158             c >>>= 32;
159         }
160         return (int)c;
161     }
162 
addWordAt(int len, int x, int[] z, int zPos)163     public static int addWordAt(int len, int x, int[] z, int zPos)
164     {
165         // assert zPos <= (len - 1);
166         long c = (x & M) + (z[zPos] & M);
167         z[zPos] = (int)c;
168         c >>>= 32;
169         return c == 0 ? 0 : incAt(len, z, zPos + 1);
170     }
171 
addWordAt(int len, int x, int[] z, int zOff, int zPos)172     public static int addWordAt(int len, int x, int[] z, int zOff, int zPos)
173     {
174         // assert zPos <= (len - 1);
175         long c = (x & M) + (z[zOff + zPos] & M);
176         z[zOff + zPos] = (int)c;
177         c >>>= 32;
178         return c == 0 ? 0 : incAt(len, z, zOff, zPos + 1);
179     }
180 
addWordTo(int len, int x, int[] z)181     public static int addWordTo(int len, int x, int[] z)
182     {
183         long c = (x & M) + (z[0] & M);
184         z[0] = (int)c;
185         c >>>= 32;
186         return c == 0 ? 0 : incAt(len, z, 1);
187     }
188 
addWordTo(int len, int x, int[] z, int zOff)189     public static int addWordTo(int len, int x, int[] z, int zOff)
190     {
191         long c = (x & M) + (z[zOff] & M);
192         z[zOff] = (int)c;
193         c >>>= 32;
194         return c == 0 ? 0 : incAt(len, z, zOff, 1);
195     }
196 
copy(int len, int[] x)197     public static int[] copy(int len, int[] x)
198     {
199         int[] z = new int[len];
200         System.arraycopy(x, 0, z, 0, len);
201         return z;
202     }
203 
copy(int len, int[] x, int[] z)204     public static void copy(int len, int[] x, int[] z)
205     {
206         System.arraycopy(x, 0, z, 0, len);
207     }
208 
create(int len)209     public static int[] create(int len)
210     {
211         return new int[len];
212     }
213 
dec(int len, int[] z)214     public static int dec(int len, int[] z)
215     {
216         for (int i = 0; i < len; ++i)
217         {
218             if (--z[i] != -1)
219             {
220                 return 0;
221             }
222         }
223         return -1;
224     }
225 
dec(int len, int[] x, int[] z)226     public static int dec(int len, int[] x, int[] z)
227     {
228         int i = 0;
229         while (i < len)
230         {
231             int c = x[i] - 1;
232             z[i] = c;
233             ++i;
234             if (c != -1)
235             {
236                 while (i < len)
237                 {
238                     z[i] = x[i];
239                     ++i;
240                 }
241                 return 0;
242             }
243         }
244         return -1;
245     }
246 
decAt(int len, int[] z, int zPos)247     public static int decAt(int len, int[] z, int zPos)
248     {
249         // assert zPos <= len;
250         for (int i = zPos; i < len; ++i)
251         {
252             if (--z[i] != -1)
253             {
254                 return 0;
255             }
256         }
257         return -1;
258     }
259 
decAt(int len, int[] z, int zOff, int zPos)260     public static int decAt(int len, int[] z, int zOff, int zPos)
261     {
262         // assert zPos <= len;
263         for (int i = zPos; i < len; ++i)
264         {
265             if (--z[zOff + i] != -1)
266             {
267                 return 0;
268             }
269         }
270         return -1;
271     }
272 
eq(int len, int[] x, int[] y)273     public static boolean eq(int len, int[] x, int[] y)
274     {
275         for (int i = len - 1; i >= 0; --i)
276         {
277             if (x[i] != y[i])
278             {
279                 return false;
280             }
281         }
282         return true;
283     }
284 
fromBigInteger(int bits, BigInteger x)285     public static int[] fromBigInteger(int bits, BigInteger x)
286     {
287         if (x.signum() < 0 || x.bitLength() > bits)
288         {
289             throw new IllegalArgumentException();
290         }
291 
292         int len = (bits + 31) >> 5;
293         int[] z = create(len);
294         int i = 0;
295         while (x.signum() != 0)
296         {
297             z[i++] = x.intValue();
298             x = x.shiftRight(32);
299         }
300         return z;
301     }
302 
getBit(int[] x, int bit)303     public static int getBit(int[] x, int bit)
304     {
305         if (bit == 0)
306         {
307             return x[0] & 1;
308         }
309         int w = bit >> 5;
310         if (w < 0 || w >= x.length)
311         {
312             return 0;
313         }
314         int b = bit & 31;
315         return (x[w] >>> b) & 1;
316     }
317 
gte(int len, int[] x, int[] y)318     public static boolean gte(int len, int[] x, int[] y)
319     {
320         for (int i = len - 1; i >= 0; --i)
321         {
322             int x_i = x[i] ^ Integer.MIN_VALUE;
323             int y_i = y[i] ^ Integer.MIN_VALUE;
324             if (x_i < y_i)
325                 return false;
326             if (x_i > y_i)
327                 return true;
328         }
329         return true;
330     }
331 
inc(int len, int[] z)332     public static int inc(int len, int[] z)
333     {
334         for (int i = 0; i < len; ++i)
335         {
336             if (++z[i] != 0)
337             {
338                 return 0;
339             }
340         }
341         return 1;
342     }
343 
inc(int len, int[] x, int[] z)344     public static int inc(int len, int[] x, int[] z)
345     {
346         int i = 0;
347         while (i < len)
348         {
349             int c = x[i] + 1;
350             z[i] = c;
351             ++i;
352             if (c != 0)
353             {
354                 while (i < len)
355                 {
356                     z[i] = x[i];
357                     ++i;
358                 }
359                 return 0;
360             }
361         }
362         return 1;
363     }
364 
incAt(int len, int[] z, int zPos)365     public static int incAt(int len, int[] z, int zPos)
366     {
367         // assert zPos <= len;
368         for (int i = zPos; i < len; ++i)
369         {
370             if (++z[i] != 0)
371             {
372                 return 0;
373             }
374         }
375         return 1;
376     }
377 
incAt(int len, int[] z, int zOff, int zPos)378     public static int incAt(int len, int[] z, int zOff, int zPos)
379     {
380         // assert zPos <= len;
381         for (int i = zPos; i < len; ++i)
382         {
383             if (++z[zOff + i] != 0)
384             {
385                 return 0;
386             }
387         }
388         return 1;
389     }
390 
isOne(int len, int[] x)391     public static boolean isOne(int len, int[] x)
392     {
393         if (x[0] != 1)
394         {
395             return false;
396         }
397         for (int i = 1; i < len; ++i)
398         {
399             if (x[i] != 0)
400             {
401                 return false;
402             }
403         }
404         return true;
405     }
406 
isZero(int len, int[] x)407     public static boolean isZero(int len, int[] x)
408     {
409         for (int i = 0; i < len; ++i)
410         {
411             if (x[i] != 0)
412             {
413                 return false;
414             }
415         }
416         return true;
417     }
418 
mul(int len, int[] x, int[] y, int[] zz)419     public static void mul(int len, int[] x, int[] y, int[] zz)
420     {
421         zz[len] = mulWord(len, x[0], y, zz);
422 
423         for (int i = 1; i < len; ++i)
424         {
425             zz[i + len] = mulWordAddTo(len, x[i], y, 0, zz, i);
426         }
427     }
428 
mul(int len, int[] x, int xOff, int[] y, int yOff, int[] zz, int zzOff)429     public static void mul(int len, int[] x, int xOff, int[] y, int yOff, int[] zz, int zzOff)
430     {
431         zz[zzOff + len] = mulWord(len, x[xOff], y, yOff, zz, zzOff);
432 
433         for (int i = 1; i < len; ++i)
434         {
435             zz[zzOff + i + len] = mulWordAddTo(len, x[xOff + i], y, yOff, zz, zzOff + i);
436         }
437     }
438 
mulAddTo(int len, int[] x, int[] y, int[] zz)439     public static int mulAddTo(int len, int[] x, int[] y, int[] zz)
440     {
441         long zc = 0;
442         for (int i = 0; i < len; ++i)
443         {
444             long c = mulWordAddTo(len, x[i], y, 0, zz, i) & M;
445             c += zc + (zz[i + len] & M);
446             zz[i + len] = (int)c;
447             zc = c >>> 32;
448         }
449         return (int)zc;
450     }
451 
mulAddTo(int len, int[] x, int xOff, int[] y, int yOff, int[] zz, int zzOff)452     public static int mulAddTo(int len, int[] x, int xOff, int[] y, int yOff, int[] zz, int zzOff)
453     {
454         long zc = 0;
455         for (int i = 0; i < len; ++i)
456         {
457             long c = mulWordAddTo(len, x[xOff + i], y, yOff, zz, zzOff) & M;
458             c += zc + (zz[zzOff + len] & M);
459             zz[zzOff + len] = (int)c;
460             zc = c >>> 32;
461             ++zzOff;
462         }
463         return (int)zc;
464     }
465 
mul31BothAdd(int len, int a, int[] x, int b, int[] y, int[] z, int zOff)466     public static int mul31BothAdd(int len, int a, int[] x, int b, int[] y, int[] z, int zOff)
467     {
468         long c = 0, aVal = a & M, bVal = b & M;
469         int i = 0;
470         do
471         {
472             c += aVal * (x[i] & M) + bVal * (y[i] & M) + (z[zOff + i] & M);
473             z[zOff + i] = (int)c;
474             c >>>= 32;
475         }
476         while (++i < len);
477         return (int)c;
478     }
479 
mulWord(int len, int x, int[] y, int[] z)480     public static int mulWord(int len, int x, int[] y, int[] z)
481     {
482         long c = 0, xVal = x & M;
483         int i = 0;
484         do
485         {
486             c += xVal * (y[i] & M);
487             z[i] = (int)c;
488             c >>>= 32;
489         }
490         while (++i < len);
491         return (int)c;
492     }
493 
mulWord(int len, int x, int[] y, int yOff, int[] z, int zOff)494     public static int mulWord(int len, int x, int[] y, int yOff, int[] z, int zOff)
495     {
496         long c = 0, xVal = x & M;
497         int i = 0;
498         do
499         {
500             c += xVal * (y[yOff + i] & M);
501             z[zOff + i] = (int)c;
502             c >>>= 32;
503         }
504         while (++i < len);
505         return (int)c;
506     }
507 
mulWordAddTo(int len, int x, int[] y, int yOff, int[] z, int zOff)508     public static int mulWordAddTo(int len, int x, int[] y, int yOff, int[] z, int zOff)
509     {
510         long c = 0, xVal = x & M;
511         int i = 0;
512         do
513         {
514             c += xVal * (y[yOff + i] & M) + (z[zOff + i] & M);
515             z[zOff + i] = (int)c;
516             c >>>= 32;
517         }
518         while (++i < len);
519         return (int)c;
520     }
521 
mulWordDwordAddAt(int len, int x, long y, int[] z, int zPos)522     public static int mulWordDwordAddAt(int len, int x, long y, int[] z, int zPos)
523     {
524         // assert zPos <= (len - 3);
525         long c = 0, xVal = x & M;
526         c += xVal * (y & M) + (z[zPos + 0] & M);
527         z[zPos + 0] = (int)c;
528         c >>>= 32;
529         c += xVal * (y >>> 32) + (z[zPos + 1] & M);
530         z[zPos + 1] = (int)c;
531         c >>>= 32;
532         c += (z[zPos + 2] & M);
533         z[zPos + 2] = (int)c;
534         c >>>= 32;
535         return c == 0 ? 0 : incAt(len, z, zPos + 3);
536     }
537 
shiftDownBit(int len, int[] z, int c)538     public static int shiftDownBit(int len, int[] z, int c)
539     {
540         int i = len;
541         while (--i >= 0)
542         {
543             int next = z[i];
544             z[i] = (next >>> 1) | (c << 31);
545             c = next;
546         }
547         return c << 31;
548     }
549 
shiftDownBit(int len, int[] z, int zOff, int c)550     public static int shiftDownBit(int len, int[] z, int zOff, int c)
551     {
552         int i = len;
553         while (--i >= 0)
554         {
555             int next = z[zOff + i];
556             z[zOff + i] = (next >>> 1) | (c << 31);
557             c = next;
558         }
559         return c << 31;
560     }
561 
shiftDownBit(int len, int[] x, int c, int[] z)562     public static int shiftDownBit(int len, int[] x, int c, int[] z)
563     {
564         int i = len;
565         while (--i >= 0)
566         {
567             int next = x[i];
568             z[i] = (next >>> 1) | (c << 31);
569             c = next;
570         }
571         return c << 31;
572     }
573 
shiftDownBit(int len, int[] x, int xOff, int c, int[] z, int zOff)574     public static int shiftDownBit(int len, int[] x, int xOff, int c, int[] z, int zOff)
575     {
576         int i = len;
577         while (--i >= 0)
578         {
579             int next = x[xOff + i];
580             z[zOff + i] = (next >>> 1) | (c << 31);
581             c = next;
582         }
583         return c << 31;
584     }
585 
shiftDownBits(int len, int[] z, int bits, int c)586     public static int shiftDownBits(int len, int[] z, int bits, int c)
587     {
588 //        assert bits > 0 && bits < 32;
589         int i = len;
590         while (--i >= 0)
591         {
592             int next = z[i];
593             z[i] = (next >>> bits) | (c << -bits);
594             c = next;
595         }
596         return c << -bits;
597     }
598 
shiftDownBits(int len, int[] z, int zOff, int bits, int c)599     public static int shiftDownBits(int len, int[] z, int zOff, int bits, int c)
600     {
601 //        assert bits > 0 && bits < 32;
602         int i = len;
603         while (--i >= 0)
604         {
605             int next = z[zOff + i];
606             z[zOff + i] = (next >>> bits) | (c << -bits);
607             c = next;
608         }
609         return c << -bits;
610     }
611 
shiftDownBits(int len, int[] x, int bits, int c, int[] z)612     public static int shiftDownBits(int len, int[] x, int bits, int c, int[] z)
613     {
614 //        assert bits > 0 && bits < 32;
615         int i = len;
616         while (--i >= 0)
617         {
618             int next = x[i];
619             z[i] = (next >>> bits) | (c << -bits);
620             c = next;
621         }
622         return c << -bits;
623     }
624 
shiftDownBits(int len, int[] x, int xOff, int bits, int c, int[] z, int zOff)625     public static int shiftDownBits(int len, int[] x, int xOff, int bits, int c, int[] z, int zOff)
626     {
627 //        assert bits > 0 && bits < 32;
628         int i = len;
629         while (--i >= 0)
630         {
631             int next = x[xOff + i];
632             z[zOff + i] = (next >>> bits) | (c << -bits);
633             c = next;
634         }
635         return c << -bits;
636     }
637 
shiftDownWord(int len, int[] z, int c)638     public static int shiftDownWord(int len, int[] z, int c)
639     {
640         int i = len;
641         while (--i >= 0)
642         {
643             int next = z[i];
644             z[i] = c;
645             c = next;
646         }
647         return c;
648     }
649 
shiftUpBit(int len, int[] z, int c)650     public static int shiftUpBit(int len, int[] z, int c)
651     {
652         for (int i = 0; i < len; ++i)
653         {
654             int next = z[i];
655             z[i] = (next << 1) | (c >>> 31);
656             c = next;
657         }
658         return c >>> 31;
659     }
660 
shiftUpBit(int len, int[] z, int zOff, int c)661     public static int shiftUpBit(int len, int[] z, int zOff, int c)
662     {
663         for (int i = 0; i < len; ++i)
664         {
665             int next = z[zOff + i];
666             z[zOff + i] = (next << 1) | (c >>> 31);
667             c = next;
668         }
669         return c >>> 31;
670     }
671 
shiftUpBit(int len, int[] x, int c, int[] z)672     public static int shiftUpBit(int len, int[] x, int c, int[] z)
673     {
674         for (int i = 0; i < len; ++i)
675         {
676             int next = x[i];
677             z[i] = (next << 1) | (c >>> 31);
678             c = next;
679         }
680         return c >>> 31;
681     }
682 
shiftUpBit(int len, int[] x, int xOff, int c, int[] z, int zOff)683     public static int shiftUpBit(int len, int[] x, int xOff, int c, int[] z, int zOff)
684     {
685         for (int i = 0; i < len; ++i)
686         {
687             int next = x[xOff + i];
688             z[zOff + i] = (next << 1) | (c >>> 31);
689             c = next;
690         }
691         return c >>> 31;
692     }
693 
shiftUpBits(int len, int[] z, int bits, int c)694     public static int shiftUpBits(int len, int[] z, int bits, int c)
695     {
696 //        assert bits > 0 && bits < 32;
697         for (int i = 0; i < len; ++i)
698         {
699             int next = z[i];
700             z[i] = (next << bits) | (c >>> -bits);
701             c = next;
702         }
703         return c >>> -bits;
704     }
705 
shiftUpBits(int len, int[] z, int zOff, int bits, int c)706     public static int shiftUpBits(int len, int[] z, int zOff, int bits, int c)
707     {
708 //        assert bits > 0 && bits < 32;
709         for (int i = 0; i < len; ++i)
710         {
711             int next = z[zOff + i];
712             z[zOff + i] = (next << bits) | (c >>> -bits);
713             c = next;
714         }
715         return c >>> -bits;
716     }
717 
shiftUpBits(int len, int[] x, int bits, int c, int[] z)718     public static int shiftUpBits(int len, int[] x, int bits, int c, int[] z)
719     {
720 //        assert bits > 0 && bits < 32;
721         for (int i = 0; i < len; ++i)
722         {
723             int next = x[i];
724             z[i] = (next << bits) | (c >>> -bits);
725             c = next;
726         }
727         return c >>> -bits;
728     }
729 
shiftUpBits(int len, int[] x, int xOff, int bits, int c, int[] z, int zOff)730     public static int shiftUpBits(int len, int[] x, int xOff, int bits, int c, int[] z, int zOff)
731     {
732 //        assert bits > 0 && bits < 32;
733         for (int i = 0; i < len; ++i)
734         {
735             int next = x[xOff + i];
736             z[zOff + i] = (next << bits) | (c >>> -bits);
737             c = next;
738         }
739         return c >>> -bits;
740     }
741 
square(int len, int[] x, int[] zz)742     public static void square(int len, int[] x, int[] zz)
743     {
744         int extLen = len << 1;
745         int c = 0;
746         int j = len, k = extLen;
747         do
748         {
749             long xVal = (x[--j] & M);
750             long p = xVal * xVal;
751             zz[--k] = (c << 31) | (int)(p >>> 33);
752             zz[--k] = (int)(p >>> 1);
753             c = (int)p;
754         }
755         while (j > 0);
756 
757         for (int i = 1; i < len; ++i)
758         {
759             c = squareWordAdd(x, i, zz);
760             addWordAt(extLen, c, zz, i << 1);
761         }
762 
763         shiftUpBit(extLen, zz, x[0] << 31);
764     }
765 
square(int len, int[] x, int xOff, int[] zz, int zzOff)766     public static void square(int len, int[] x, int xOff, int[] zz, int zzOff)
767     {
768         int extLen = len << 1;
769         int c = 0;
770         int j = len, k = extLen;
771         do
772         {
773             long xVal = (x[xOff + --j] & M);
774             long p = xVal * xVal;
775             zz[zzOff + --k] = (c << 31) | (int)(p >>> 33);
776             zz[zzOff + --k] = (int)(p >>> 1);
777             c = (int)p;
778         }
779         while (j > 0);
780 
781         for (int i = 1; i < len; ++i)
782         {
783             c = squareWordAdd(x, xOff, i, zz, zzOff);
784             addWordAt(extLen, c, zz, zzOff, i << 1);
785         }
786 
787         shiftUpBit(extLen, zz, zzOff, x[xOff] << 31);
788     }
789 
squareWordAdd(int[] x, int xPos, int[] z)790     public static int squareWordAdd(int[] x, int xPos, int[] z)
791     {
792         long c = 0, xVal = x[xPos] & M;
793         int i = 0;
794         do
795         {
796             c += xVal * (x[i] & M) + (z[xPos + i] & M);
797             z[xPos + i] = (int)c;
798             c >>>= 32;
799         }
800         while (++i < xPos);
801         return (int)c;
802     }
803 
squareWordAdd(int[] x, int xOff, int xPos, int[] z, int zOff)804     public static int squareWordAdd(int[] x, int xOff, int xPos, int[] z, int zOff)
805     {
806         long c = 0, xVal = x[xOff + xPos] & M;
807         int i = 0;
808         do
809         {
810             c += xVal * (x[xOff + i] & M) + (z[xPos + zOff] & M);
811             z[xPos + zOff] = (int)c;
812             c >>>= 32;
813             ++zOff;
814         }
815         while (++i < xPos);
816         return (int)c;
817     }
818 
sub(int len, int[] x, int[] y, int[] z)819     public static int sub(int len, int[] x, int[] y, int[] z)
820     {
821         long c = 0;
822         for (int i = 0; i < len; ++i)
823         {
824             c += (x[i] & M) - (y[i] & M);
825             z[i] = (int)c;
826             c >>= 32;
827         }
828         return (int)c;
829     }
830 
sub(int len, int[] x, int xOff, int[] y, int yOff, int[] z, int zOff)831     public static int sub(int len, int[] x, int xOff, int[] y, int yOff, int[] z, int zOff)
832     {
833         long c = 0;
834         for (int i = 0; i < len; ++i)
835         {
836             c += (x[xOff + i] & M) - (y[yOff + i] & M);
837             z[zOff + i] = (int)c;
838             c >>= 32;
839         }
840         return (int)c;
841     }
842 
sub33At(int len, int x, int[] z, int zPos)843     public static int sub33At(int len, int x, int[] z, int zPos)
844     {
845         // assert zPos <= (len - 2);
846         long c = (z[zPos + 0] & M) - (x & M);
847         z[zPos + 0] = (int)c;
848         c >>= 32;
849         c += (z[zPos + 1] & M) - 1;
850         z[zPos + 1] = (int)c;
851         c >>= 32;
852         return c == 0 ? 0 : decAt(len, z, zPos + 2);
853     }
854 
sub33At(int len, int x, int[] z, int zOff, int zPos)855     public static int sub33At(int len, int x, int[] z, int zOff, int zPos)
856     {
857         // assert zPos <= (len - 2);
858         long c = (z[zOff + zPos] & M) - (x & M);
859         z[zOff + zPos] = (int)c;
860         c >>= 32;
861         c += (z[zOff + zPos + 1] & M) - 1;
862         z[zOff + zPos + 1] = (int)c;
863         c >>= 32;
864         return c == 0 ? 0 : decAt(len, z, zOff, zPos + 2);
865     }
866 
sub33From(int len, int x, int[] z)867     public static int sub33From(int len, int x, int[] z)
868     {
869         long c = (z[0] & M) - (x & M);
870         z[0] = (int)c;
871         c >>= 32;
872         c += (z[1] & M) - 1;
873         z[1] = (int)c;
874         c >>= 32;
875         return c == 0 ? 0 : decAt(len, z, 2);
876     }
877 
sub33From(int len, int x, int[] z, int zOff)878     public static int sub33From(int len, int x, int[] z, int zOff)
879     {
880         long c = (z[zOff + 0] & M) - (x & M);
881         z[zOff + 0] = (int)c;
882         c >>= 32;
883         c += (z[zOff + 1] & M) - 1;
884         z[zOff + 1] = (int)c;
885         c >>= 32;
886         return c == 0 ? 0 : decAt(len, z, zOff, 2);
887     }
888 
subBothFrom(int len, int[] x, int[] y, int[] z)889     public static int subBothFrom(int len, int[] x, int[] y, int[] z)
890     {
891         long c = 0;
892         for (int i = 0; i < len; ++i)
893         {
894             c += (z[i] & M) - (x[i] & M) - (y[i] & M);
895             z[i] = (int)c;
896             c >>= 32;
897         }
898         return (int)c;
899     }
900 
subBothFrom(int len, int[] x, int xOff, int[] y, int yOff, int[] z, int zOff)901     public static int subBothFrom(int len, int[] x, int xOff, int[] y, int yOff, int[] z, int zOff)
902     {
903         long c = 0;
904         for (int i = 0; i < len; ++i)
905         {
906             c += (z[zOff + i] & M) - (x[xOff + i] & M) - (y[yOff + i] & M);
907             z[zOff + i] = (int)c;
908             c >>= 32;
909         }
910         return (int)c;
911     }
912 
subDWordAt(int len, long x, int[] z, int zPos)913     public static int subDWordAt(int len, long x, int[] z, int zPos)
914     {
915         // assert zPos <= (len - 2);
916         long c = (z[zPos + 0] & M) - (x & M);
917         z[zPos + 0] = (int)c;
918         c >>= 32;
919         c += (z[zPos + 1] & M) - (x >>> 32);
920         z[zPos + 1] = (int)c;
921         c >>= 32;
922         return c == 0 ? 0 : decAt(len, z, zPos + 2);
923     }
924 
subDWordAt(int len, long x, int[] z, int zOff, int zPos)925     public static int subDWordAt(int len, long x, int[] z, int zOff, int zPos)
926     {
927         // assert zPos <= (len - 2);
928         long c = (z[zOff + zPos] & M) - (x & M);
929         z[zOff + zPos] = (int)c;
930         c >>= 32;
931         c += (z[zOff + zPos + 1] & M) - (x >>> 32);
932         z[zOff + zPos + 1] = (int)c;
933         c >>= 32;
934         return c == 0 ? 0 : decAt(len, z,  zOff, zPos + 2);
935     }
936 
subDWordFrom(int len, long x, int[] z)937     public static int subDWordFrom(int len, long x, int[] z)
938     {
939         long c = (z[0] & M) - (x & M);
940         z[0] = (int)c;
941         c >>= 32;
942         c += (z[1] & M) - (x >>> 32);
943         z[1] = (int)c;
944         c >>= 32;
945         return c == 0 ? 0 : decAt(len, z, 2);
946     }
947 
subDWordFrom(int len, long x, int[] z, int zOff)948     public static int subDWordFrom(int len, long x, int[] z, int zOff)
949     {
950         long c = (z[zOff + 0] & M) - (x & M);
951         z[zOff + 0] = (int)c;
952         c >>= 32;
953         c += (z[zOff + 1] & M) - (x >>> 32);
954         z[zOff + 1] = (int)c;
955         c >>= 32;
956         return c == 0 ? 0 : decAt(len, z, zOff, 2);
957     }
958 
subFrom(int len, int[] x, int[] z)959     public static int subFrom(int len, int[] x, int[] z)
960     {
961         long c = 0;
962         for (int i = 0; i < len; ++i)
963         {
964             c += (z[i] & M) - (x[i] & M);
965             z[i] = (int)c;
966             c >>= 32;
967         }
968         return (int)c;
969     }
970 
subFrom(int len, int[] x, int xOff, int[] z, int zOff)971     public static int subFrom(int len, int[] x, int xOff, int[] z, int zOff)
972     {
973         long c = 0;
974         for (int i = 0; i < len; ++i)
975         {
976             c += (z[zOff + i] & M) - (x[xOff + i] & M);
977             z[zOff + i] = (int)c;
978             c >>= 32;
979         }
980         return (int)c;
981     }
982 
subWordAt(int len, int x, int[] z, int zPos)983     public static int subWordAt(int len, int x, int[] z, int zPos)
984     {
985         // assert zPos <= (len - 1);
986         long c = (z[zPos] & M) - (x & M);
987         z[zPos] = (int)c;
988         c >>= 32;
989         return c == 0 ? 0 : decAt(len, z, zPos + 1);
990     }
991 
subWordAt(int len, int x, int[] z, int zOff, int zPos)992     public static int subWordAt(int len, int x, int[] z, int zOff, int zPos)
993     {
994         // assert zPos <= (len - 1);
995         long c = (z[zOff + zPos] & M) - (x & M);
996         z[zOff + zPos] = (int)c;
997         c >>= 32;
998         return c == 0 ? 0 : decAt(len, z, zOff, zPos + 1);
999     }
1000 
subWordFrom(int len, int x, int[] z)1001     public static int subWordFrom(int len, int x, int[] z)
1002     {
1003         long c = (z[0] & M) - (x & M);
1004         z[0] = (int)c;
1005         c >>= 32;
1006         return c == 0 ? 0 : decAt(len, z, 1);
1007     }
1008 
subWordFrom(int len, int x, int[] z, int zOff)1009     public static int subWordFrom(int len, int x, int[] z, int zOff)
1010     {
1011         long c = (z[zOff + 0] & M) - (x & M);
1012         z[zOff + 0] = (int)c;
1013         c >>= 32;
1014         return c == 0 ? 0 : decAt(len, z, zOff, 1);
1015     }
1016 
toBigInteger(int len, int[] x)1017     public static BigInteger toBigInteger(int len, int[] x)
1018     {
1019         byte[] bs = new byte[len << 2];
1020         for (int i = 0; i < len; ++i)
1021         {
1022             int x_i = x[i];
1023             if (x_i != 0)
1024             {
1025                 Pack.intToBigEndian(x_i, bs, (len - 1 - i) << 2);
1026             }
1027         }
1028         return new BigInteger(1, bs);
1029     }
1030 
zero(int len, int[] z)1031     public static void zero(int len, int[] z)
1032     {
1033         for (int i = 0; i < len; ++i)
1034         {
1035             z[i] = 0;
1036         }
1037     }
1038 }
1039