1package org.bouncycastle.math.raw;
2
3import java.math.BigInteger;
4
5import org.bouncycastle.util.Pack;
6
7public abstract class Nat
8{
9    private static final long M = 0xFFFFFFFFL;
10
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
204    public static void copy(int len, int[] x, int[] z)
205    {
206        System.arraycopy(x, 0, z, 0, len);
207    }
208
209    public static int[] create(int len)
210    {
211        return new int[len];
212    }
213
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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