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