ViewVC Help
View File | Revision Log | Show Annotations | Download File
/cvs/Crypt-Ed25519/ed25519/src/sc.c
Revision: 1.1
Committed: Fri Mar 27 20:23:12 2015 UTC (11 years, 7 months ago) by root
Content type: text/plain
Branch: MAIN
CVS Tags: rel-0_1, rel-1_0, rel-1_02, rel-1_03, rel-1_01, rel-1_04, rel-1_05, rel-0_9, HEAD
Log Message: 
*** empty log message ***

File Contents

# User Rev Content
1 root 1.1 #include "fixedint.h"
2     #include "sc.h"
3    
4     static uint64_t load_3(const unsigned char *in) {
5     uint64_t result;
6    
7     result = (uint64_t) in[0];
8     result |= ((uint64_t) in[1]) << 8;
9     result |= ((uint64_t) in[2]) << 16;
10    
11     return result;
12     }
13    
14     static uint64_t load_4(const unsigned char *in) {
15     uint64_t result;
16    
17     result = (uint64_t) in[0];
18     result |= ((uint64_t) in[1]) << 8;
19     result |= ((uint64_t) in[2]) << 16;
20     result |= ((uint64_t) in[3]) << 24;
21    
22     return result;
23     }
24    
25     /*
26     Input:
27     s[0]+256*s[1]+...+256^63*s[63] = s
28    
29     Output:
30     s[0]+256*s[1]+...+256^31*s[31] = s mod l
31     where l = 2^252 + 27742317777372353535851937790883648493.
32     Overwrites s in place.
33     */
34    
35     void sc_reduce(unsigned char *s) {
36     int64_t s0 = 2097151 & load_3(s);
37     int64_t s1 = 2097151 & (load_4(s + 2) >> 5);
38     int64_t s2 = 2097151 & (load_3(s + 5) >> 2);
39     int64_t s3 = 2097151 & (load_4(s + 7) >> 7);
40     int64_t s4 = 2097151 & (load_4(s + 10) >> 4);
41     int64_t s5 = 2097151 & (load_3(s + 13) >> 1);
42     int64_t s6 = 2097151 & (load_4(s + 15) >> 6);
43     int64_t s7 = 2097151 & (load_3(s + 18) >> 3);
44     int64_t s8 = 2097151 & load_3(s + 21);
45     int64_t s9 = 2097151 & (load_4(s + 23) >> 5);
46     int64_t s10 = 2097151 & (load_3(s + 26) >> 2);
47     int64_t s11 = 2097151 & (load_4(s + 28) >> 7);
48     int64_t s12 = 2097151 & (load_4(s + 31) >> 4);
49     int64_t s13 = 2097151 & (load_3(s + 34) >> 1);
50     int64_t s14 = 2097151 & (load_4(s + 36) >> 6);
51     int64_t s15 = 2097151 & (load_3(s + 39) >> 3);
52     int64_t s16 = 2097151 & load_3(s + 42);
53     int64_t s17 = 2097151 & (load_4(s + 44) >> 5);
54     int64_t s18 = 2097151 & (load_3(s + 47) >> 2);
55     int64_t s19 = 2097151 & (load_4(s + 49) >> 7);
56     int64_t s20 = 2097151 & (load_4(s + 52) >> 4);
57     int64_t s21 = 2097151 & (load_3(s + 55) >> 1);
58     int64_t s22 = 2097151 & (load_4(s + 57) >> 6);
59     int64_t s23 = (load_4(s + 60) >> 3);
60     int64_t carry0;
61     int64_t carry1;
62     int64_t carry2;
63     int64_t carry3;
64     int64_t carry4;
65     int64_t carry5;
66     int64_t carry6;
67     int64_t carry7;
68     int64_t carry8;
69     int64_t carry9;
70     int64_t carry10;
71     int64_t carry11;
72     int64_t carry12;
73     int64_t carry13;
74     int64_t carry14;
75     int64_t carry15;
76     int64_t carry16;
77    
78     s11 += s23 * 666643;
79     s12 += s23 * 470296;
80     s13 += s23 * 654183;
81     s14 -= s23 * 997805;
82     s15 += s23 * 136657;
83     s16 -= s23 * 683901;
84     s23 = 0;
85     s10 += s22 * 666643;
86     s11 += s22 * 470296;
87     s12 += s22 * 654183;
88     s13 -= s22 * 997805;
89     s14 += s22 * 136657;
90     s15 -= s22 * 683901;
91     s22 = 0;
92     s9 += s21 * 666643;
93     s10 += s21 * 470296;
94     s11 += s21 * 654183;
95     s12 -= s21 * 997805;
96     s13 += s21 * 136657;
97     s14 -= s21 * 683901;
98     s21 = 0;
99     s8 += s20 * 666643;
100     s9 += s20 * 470296;
101     s10 += s20 * 654183;
102     s11 -= s20 * 997805;
103     s12 += s20 * 136657;
104     s13 -= s20 * 683901;
105     s20 = 0;
106     s7 += s19 * 666643;
107     s8 += s19 * 470296;
108     s9 += s19 * 654183;
109     s10 -= s19 * 997805;
110     s11 += s19 * 136657;
111     s12 -= s19 * 683901;
112     s19 = 0;
113     s6 += s18 * 666643;
114     s7 += s18 * 470296;
115     s8 += s18 * 654183;
116     s9 -= s18 * 997805;
117     s10 += s18 * 136657;
118     s11 -= s18 * 683901;
119     s18 = 0;
120     carry6 = (s6 + (1 << 20)) >> 21;
121     s7 += carry6;
122     s6 -= carry6 << 21;
123     carry8 = (s8 + (1 << 20)) >> 21;
124     s9 += carry8;
125     s8 -= carry8 << 21;
126     carry10 = (s10 + (1 << 20)) >> 21;
127     s11 += carry10;
128     s10 -= carry10 << 21;
129     carry12 = (s12 + (1 << 20)) >> 21;
130     s13 += carry12;
131     s12 -= carry12 << 21;
132     carry14 = (s14 + (1 << 20)) >> 21;
133     s15 += carry14;
134     s14 -= carry14 << 21;
135     carry16 = (s16 + (1 << 20)) >> 21;
136     s17 += carry16;
137     s16 -= carry16 << 21;
138     carry7 = (s7 + (1 << 20)) >> 21;
139     s8 += carry7;
140     s7 -= carry7 << 21;
141     carry9 = (s9 + (1 << 20)) >> 21;
142     s10 += carry9;
143     s9 -= carry9 << 21;
144     carry11 = (s11 + (1 << 20)) >> 21;
145     s12 += carry11;
146     s11 -= carry11 << 21;
147     carry13 = (s13 + (1 << 20)) >> 21;
148     s14 += carry13;
149     s13 -= carry13 << 21;
150     carry15 = (s15 + (1 << 20)) >> 21;
151     s16 += carry15;
152     s15 -= carry15 << 21;
153     s5 += s17 * 666643;
154     s6 += s17 * 470296;
155     s7 += s17 * 654183;
156     s8 -= s17 * 997805;
157     s9 += s17 * 136657;
158     s10 -= s17 * 683901;
159     s17 = 0;
160     s4 += s16 * 666643;
161     s5 += s16 * 470296;
162     s6 += s16 * 654183;
163     s7 -= s16 * 997805;
164     s8 += s16 * 136657;
165     s9 -= s16 * 683901;
166     s16 = 0;
167     s3 += s15 * 666643;
168     s4 += s15 * 470296;
169     s5 += s15 * 654183;
170     s6 -= s15 * 997805;
171     s7 += s15 * 136657;
172     s8 -= s15 * 683901;
173     s15 = 0;
174     s2 += s14 * 666643;
175     s3 += s14 * 470296;
176     s4 += s14 * 654183;
177     s5 -= s14 * 997805;
178     s6 += s14 * 136657;
179     s7 -= s14 * 683901;
180     s14 = 0;
181     s1 += s13 * 666643;
182     s2 += s13 * 470296;
183     s3 += s13 * 654183;
184     s4 -= s13 * 997805;
185     s5 += s13 * 136657;
186     s6 -= s13 * 683901;
187     s13 = 0;
188     s0 += s12 * 666643;
189     s1 += s12 * 470296;
190     s2 += s12 * 654183;
191     s3 -= s12 * 997805;
192     s4 += s12 * 136657;
193     s5 -= s12 * 683901;
194     s12 = 0;
195     carry0 = (s0 + (1 << 20)) >> 21;
196     s1 += carry0;
197     s0 -= carry0 << 21;
198     carry2 = (s2 + (1 << 20)) >> 21;
199     s3 += carry2;
200     s2 -= carry2 << 21;
201     carry4 = (s4 + (1 << 20)) >> 21;
202     s5 += carry4;
203     s4 -= carry4 << 21;
204     carry6 = (s6 + (1 << 20)) >> 21;
205     s7 += carry6;
206     s6 -= carry6 << 21;
207     carry8 = (s8 + (1 << 20)) >> 21;
208     s9 += carry8;
209     s8 -= carry8 << 21;
210     carry10 = (s10 + (1 << 20)) >> 21;
211     s11 += carry10;
212     s10 -= carry10 << 21;
213     carry1 = (s1 + (1 << 20)) >> 21;
214     s2 += carry1;
215     s1 -= carry1 << 21;
216     carry3 = (s3 + (1 << 20)) >> 21;
217     s4 += carry3;
218     s3 -= carry3 << 21;
219     carry5 = (s5 + (1 << 20)) >> 21;
220     s6 += carry5;
221     s5 -= carry5 << 21;
222     carry7 = (s7 + (1 << 20)) >> 21;
223     s8 += carry7;
224     s7 -= carry7 << 21;
225     carry9 = (s9 + (1 << 20)) >> 21;
226     s10 += carry9;
227     s9 -= carry9 << 21;
228     carry11 = (s11 + (1 << 20)) >> 21;
229     s12 += carry11;
230     s11 -= carry11 << 21;
231     s0 += s12 * 666643;
232     s1 += s12 * 470296;
233     s2 += s12 * 654183;
234     s3 -= s12 * 997805;
235     s4 += s12 * 136657;
236     s5 -= s12 * 683901;
237     s12 = 0;
238     carry0 = s0 >> 21;
239     s1 += carry0;
240     s0 -= carry0 << 21;
241     carry1 = s1 >> 21;
242     s2 += carry1;
243     s1 -= carry1 << 21;
244     carry2 = s2 >> 21;
245     s3 += carry2;
246     s2 -= carry2 << 21;
247     carry3 = s3 >> 21;
248     s4 += carry3;
249     s3 -= carry3 << 21;
250     carry4 = s4 >> 21;
251     s5 += carry4;
252     s4 -= carry4 << 21;
253     carry5 = s5 >> 21;
254     s6 += carry5;
255     s5 -= carry5 << 21;
256     carry6 = s6 >> 21;
257     s7 += carry6;
258     s6 -= carry6 << 21;
259     carry7 = s7 >> 21;
260     s8 += carry7;
261     s7 -= carry7 << 21;
262     carry8 = s8 >> 21;
263     s9 += carry8;
264     s8 -= carry8 << 21;
265     carry9 = s9 >> 21;
266     s10 += carry9;
267     s9 -= carry9 << 21;
268     carry10 = s10 >> 21;
269     s11 += carry10;
270     s10 -= carry10 << 21;
271     carry11 = s11 >> 21;
272     s12 += carry11;
273     s11 -= carry11 << 21;
274     s0 += s12 * 666643;
275     s1 += s12 * 470296;
276     s2 += s12 * 654183;
277     s3 -= s12 * 997805;
278     s4 += s12 * 136657;
279     s5 -= s12 * 683901;
280     s12 = 0;
281     carry0 = s0 >> 21;
282     s1 += carry0;
283     s0 -= carry0 << 21;
284     carry1 = s1 >> 21;
285     s2 += carry1;
286     s1 -= carry1 << 21;
287     carry2 = s2 >> 21;
288     s3 += carry2;
289     s2 -= carry2 << 21;
290     carry3 = s3 >> 21;
291     s4 += carry3;
292     s3 -= carry3 << 21;
293     carry4 = s4 >> 21;
294     s5 += carry4;
295     s4 -= carry4 << 21;
296     carry5 = s5 >> 21;
297     s6 += carry5;
298     s5 -= carry5 << 21;
299     carry6 = s6 >> 21;
300     s7 += carry6;
301     s6 -= carry6 << 21;
302     carry7 = s7 >> 21;
303     s8 += carry7;
304     s7 -= carry7 << 21;
305     carry8 = s8 >> 21;
306     s9 += carry8;
307     s8 -= carry8 << 21;
308     carry9 = s9 >> 21;
309     s10 += carry9;
310     s9 -= carry9 << 21;
311     carry10 = s10 >> 21;
312     s11 += carry10;
313     s10 -= carry10 << 21;
314    
315     s[0] = (unsigned char) (s0 >> 0);
316     s[1] = (unsigned char) (s0 >> 8);
317     s[2] = (unsigned char) ((s0 >> 16) | (s1 << 5));
318     s[3] = (unsigned char) (s1 >> 3);
319     s[4] = (unsigned char) (s1 >> 11);
320     s[5] = (unsigned char) ((s1 >> 19) | (s2 << 2));
321     s[6] = (unsigned char) (s2 >> 6);
322     s[7] = (unsigned char) ((s2 >> 14) | (s3 << 7));
323     s[8] = (unsigned char) (s3 >> 1);
324     s[9] = (unsigned char) (s3 >> 9);
325     s[10] = (unsigned char) ((s3 >> 17) | (s4 << 4));
326     s[11] = (unsigned char) (s4 >> 4);
327     s[12] = (unsigned char) (s4 >> 12);
328     s[13] = (unsigned char) ((s4 >> 20) | (s5 << 1));
329     s[14] = (unsigned char) (s5 >> 7);
330     s[15] = (unsigned char) ((s5 >> 15) | (s6 << 6));
331     s[16] = (unsigned char) (s6 >> 2);
332     s[17] = (unsigned char) (s6 >> 10);
333     s[18] = (unsigned char) ((s6 >> 18) | (s7 << 3));
334     s[19] = (unsigned char) (s7 >> 5);
335     s[20] = (unsigned char) (s7 >> 13);
336     s[21] = (unsigned char) (s8 >> 0);
337     s[22] = (unsigned char) (s8 >> 8);
338     s[23] = (unsigned char) ((s8 >> 16) | (s9 << 5));
339     s[24] = (unsigned char) (s9 >> 3);
340     s[25] = (unsigned char) (s9 >> 11);
341     s[26] = (unsigned char) ((s9 >> 19) | (s10 << 2));
342     s[27] = (unsigned char) (s10 >> 6);
343     s[28] = (unsigned char) ((s10 >> 14) | (s11 << 7));
344     s[29] = (unsigned char) (s11 >> 1);
345     s[30] = (unsigned char) (s11 >> 9);
346     s[31] = (unsigned char) (s11 >> 17);
347     }
348    
349    
350    
351     /*
352     Input:
353     a[0]+256*a[1]+...+256^31*a[31] = a
354     b[0]+256*b[1]+...+256^31*b[31] = b
355     c[0]+256*c[1]+...+256^31*c[31] = c
356    
357     Output:
358     s[0]+256*s[1]+...+256^31*s[31] = (ab+c) mod l
359     where l = 2^252 + 27742317777372353535851937790883648493.
360     */
361    
362     void sc_muladd(unsigned char *s, const unsigned char *a, const unsigned char *b, const unsigned char *c) {
363     int64_t a0 = 2097151 & load_3(a);
364     int64_t a1 = 2097151 & (load_4(a + 2) >> 5);
365     int64_t a2 = 2097151 & (load_3(a + 5) >> 2);
366     int64_t a3 = 2097151 & (load_4(a + 7) >> 7);
367     int64_t a4 = 2097151 & (load_4(a + 10) >> 4);
368     int64_t a5 = 2097151 & (load_3(a + 13) >> 1);
369     int64_t a6 = 2097151 & (load_4(a + 15) >> 6);
370     int64_t a7 = 2097151 & (load_3(a + 18) >> 3);
371     int64_t a8 = 2097151 & load_3(a + 21);
372     int64_t a9 = 2097151 & (load_4(a + 23) >> 5);
373     int64_t a10 = 2097151 & (load_3(a + 26) >> 2);
374     int64_t a11 = (load_4(a + 28) >> 7);
375     int64_t b0 = 2097151 & load_3(b);
376     int64_t b1 = 2097151 & (load_4(b + 2) >> 5);
377     int64_t b2 = 2097151 & (load_3(b + 5) >> 2);
378     int64_t b3 = 2097151 & (load_4(b + 7) >> 7);
379     int64_t b4 = 2097151 & (load_4(b + 10) >> 4);
380     int64_t b5 = 2097151 & (load_3(b + 13) >> 1);
381     int64_t b6 = 2097151 & (load_4(b + 15) >> 6);
382     int64_t b7 = 2097151 & (load_3(b + 18) >> 3);
383     int64_t b8 = 2097151 & load_3(b + 21);
384     int64_t b9 = 2097151 & (load_4(b + 23) >> 5);
385     int64_t b10 = 2097151 & (load_3(b + 26) >> 2);
386     int64_t b11 = (load_4(b + 28) >> 7);
387     int64_t c0 = 2097151 & load_3(c);
388     int64_t c1 = 2097151 & (load_4(c + 2) >> 5);
389     int64_t c2 = 2097151 & (load_3(c + 5) >> 2);
390     int64_t c3 = 2097151 & (load_4(c + 7) >> 7);
391     int64_t c4 = 2097151 & (load_4(c + 10) >> 4);
392     int64_t c5 = 2097151 & (load_3(c + 13) >> 1);
393     int64_t c6 = 2097151 & (load_4(c + 15) >> 6);
394     int64_t c7 = 2097151 & (load_3(c + 18) >> 3);
395     int64_t c8 = 2097151 & load_3(c + 21);
396     int64_t c9 = 2097151 & (load_4(c + 23) >> 5);
397     int64_t c10 = 2097151 & (load_3(c + 26) >> 2);
398     int64_t c11 = (load_4(c + 28) >> 7);
399     int64_t s0;
400     int64_t s1;
401     int64_t s2;
402     int64_t s3;
403     int64_t s4;
404     int64_t s5;
405     int64_t s6;
406     int64_t s7;
407     int64_t s8;
408     int64_t s9;
409     int64_t s10;
410     int64_t s11;
411     int64_t s12;
412     int64_t s13;
413     int64_t s14;
414     int64_t s15;
415     int64_t s16;
416     int64_t s17;
417     int64_t s18;
418     int64_t s19;
419     int64_t s20;
420     int64_t s21;
421     int64_t s22;
422     int64_t s23;
423     int64_t carry0;
424     int64_t carry1;
425     int64_t carry2;
426     int64_t carry3;
427     int64_t carry4;
428     int64_t carry5;
429     int64_t carry6;
430     int64_t carry7;
431     int64_t carry8;
432     int64_t carry9;
433     int64_t carry10;
434     int64_t carry11;
435     int64_t carry12;
436     int64_t carry13;
437     int64_t carry14;
438     int64_t carry15;
439     int64_t carry16;
440     int64_t carry17;
441     int64_t carry18;
442     int64_t carry19;
443     int64_t carry20;
444     int64_t carry21;
445     int64_t carry22;
446    
447     s0 = c0 + a0 * b0;
448     s1 = c1 + a0 * b1 + a1 * b0;
449     s2 = c2 + a0 * b2 + a1 * b1 + a2 * b0;
450     s3 = c3 + a0 * b3 + a1 * b2 + a2 * b1 + a3 * b0;
451     s4 = c4 + a0 * b4 + a1 * b3 + a2 * b2 + a3 * b1 + a4 * b0;
452     s5 = c5 + a0 * b5 + a1 * b4 + a2 * b3 + a3 * b2 + a4 * b1 + a5 * b0;
453     s6 = c6 + a0 * b6 + a1 * b5 + a2 * b4 + a3 * b3 + a4 * b2 + a5 * b1 + a6 * b0;
454     s7 = c7 + a0 * b7 + a1 * b6 + a2 * b5 + a3 * b4 + a4 * b3 + a5 * b2 + a6 * b1 + a7 * b0;
455     s8 = c8 + a0 * b8 + a1 * b7 + a2 * b6 + a3 * b5 + a4 * b4 + a5 * b3 + a6 * b2 + a7 * b1 + a8 * b0;
456     s9 = c9 + a0 * b9 + a1 * b8 + a2 * b7 + a3 * b6 + a4 * b5 + a5 * b4 + a6 * b3 + a7 * b2 + a8 * b1 + a9 * b0;
457     s10 = c10 + a0 * b10 + a1 * b9 + a2 * b8 + a3 * b7 + a4 * b6 + a5 * b5 + a6 * b4 + a7 * b3 + a8 * b2 + a9 * b1 + a10 * b0;
458     s11 = c11 + a0 * b11 + a1 * b10 + a2 * b9 + a3 * b8 + a4 * b7 + a5 * b6 + a6 * b5 + a7 * b4 + a8 * b3 + a9 * b2 + a10 * b1 + a11 * b0;
459     s12 = a1 * b11 + a2 * b10 + a3 * b9 + a4 * b8 + a5 * b7 + a6 * b6 + a7 * b5 + a8 * b4 + a9 * b3 + a10 * b2 + a11 * b1;
460     s13 = a2 * b11 + a3 * b10 + a4 * b9 + a5 * b8 + a6 * b7 + a7 * b6 + a8 * b5 + a9 * b4 + a10 * b3 + a11 * b2;
461     s14 = a3 * b11 + a4 * b10 + a5 * b9 + a6 * b8 + a7 * b7 + a8 * b6 + a9 * b5 + a10 * b4 + a11 * b3;
462     s15 = a4 * b11 + a5 * b10 + a6 * b9 + a7 * b8 + a8 * b7 + a9 * b6 + a10 * b5 + a11 * b4;
463     s16 = a5 * b11 + a6 * b10 + a7 * b9 + a8 * b8 + a9 * b7 + a10 * b6 + a11 * b5;
464     s17 = a6 * b11 + a7 * b10 + a8 * b9 + a9 * b8 + a10 * b7 + a11 * b6;
465     s18 = a7 * b11 + a8 * b10 + a9 * b9 + a10 * b8 + a11 * b7;
466     s19 = a8 * b11 + a9 * b10 + a10 * b9 + a11 * b8;
467     s20 = a9 * b11 + a10 * b10 + a11 * b9;
468     s21 = a10 * b11 + a11 * b10;
469     s22 = a11 * b11;
470     s23 = 0;
471     carry0 = (s0 + (1 << 20)) >> 21;
472     s1 += carry0;
473     s0 -= carry0 << 21;
474     carry2 = (s2 + (1 << 20)) >> 21;
475     s3 += carry2;
476     s2 -= carry2 << 21;
477     carry4 = (s4 + (1 << 20)) >> 21;
478     s5 += carry4;
479     s4 -= carry4 << 21;
480     carry6 = (s6 + (1 << 20)) >> 21;
481     s7 += carry6;
482     s6 -= carry6 << 21;
483     carry8 = (s8 + (1 << 20)) >> 21;
484     s9 += carry8;
485     s8 -= carry8 << 21;
486     carry10 = (s10 + (1 << 20)) >> 21;
487     s11 += carry10;
488     s10 -= carry10 << 21;
489     carry12 = (s12 + (1 << 20)) >> 21;
490     s13 += carry12;
491     s12 -= carry12 << 21;
492     carry14 = (s14 + (1 << 20)) >> 21;
493     s15 += carry14;
494     s14 -= carry14 << 21;
495     carry16 = (s16 + (1 << 20)) >> 21;
496     s17 += carry16;
497     s16 -= carry16 << 21;
498     carry18 = (s18 + (1 << 20)) >> 21;
499     s19 += carry18;
500     s18 -= carry18 << 21;
501     carry20 = (s20 + (1 << 20)) >> 21;
502     s21 += carry20;
503     s20 -= carry20 << 21;
504     carry22 = (s22 + (1 << 20)) >> 21;
505     s23 += carry22;
506     s22 -= carry22 << 21;
507     carry1 = (s1 + (1 << 20)) >> 21;
508     s2 += carry1;
509     s1 -= carry1 << 21;
510     carry3 = (s3 + (1 << 20)) >> 21;
511     s4 += carry3;
512     s3 -= carry3 << 21;
513     carry5 = (s5 + (1 << 20)) >> 21;
514     s6 += carry5;
515     s5 -= carry5 << 21;
516     carry7 = (s7 + (1 << 20)) >> 21;
517     s8 += carry7;
518     s7 -= carry7 << 21;
519     carry9 = (s9 + (1 << 20)) >> 21;
520     s10 += carry9;
521     s9 -= carry9 << 21;
522     carry11 = (s11 + (1 << 20)) >> 21;
523     s12 += carry11;
524     s11 -= carry11 << 21;
525     carry13 = (s13 + (1 << 20)) >> 21;
526     s14 += carry13;
527     s13 -= carry13 << 21;
528     carry15 = (s15 + (1 << 20)) >> 21;
529     s16 += carry15;
530     s15 -= carry15 << 21;
531     carry17 = (s17 + (1 << 20)) >> 21;
532     s18 += carry17;
533     s17 -= carry17 << 21;
534     carry19 = (s19 + (1 << 20)) >> 21;
535     s20 += carry19;
536     s19 -= carry19 << 21;
537     carry21 = (s21 + (1 << 20)) >> 21;
538     s22 += carry21;
539     s21 -= carry21 << 21;
540     s11 += s23 * 666643;
541     s12 += s23 * 470296;
542     s13 += s23 * 654183;
543     s14 -= s23 * 997805;
544     s15 += s23 * 136657;
545     s16 -= s23 * 683901;
546     s23 = 0;
547     s10 += s22 * 666643;
548     s11 += s22 * 470296;
549     s12 += s22 * 654183;
550     s13 -= s22 * 997805;
551     s14 += s22 * 136657;
552     s15 -= s22 * 683901;
553     s22 = 0;
554     s9 += s21 * 666643;
555     s10 += s21 * 470296;
556     s11 += s21 * 654183;
557     s12 -= s21 * 997805;
558     s13 += s21 * 136657;
559     s14 -= s21 * 683901;
560     s21 = 0;
561     s8 += s20 * 666643;
562     s9 += s20 * 470296;
563     s10 += s20 * 654183;
564     s11 -= s20 * 997805;
565     s12 += s20 * 136657;
566     s13 -= s20 * 683901;
567     s20 = 0;
568     s7 += s19 * 666643;
569     s8 += s19 * 470296;
570     s9 += s19 * 654183;
571     s10 -= s19 * 997805;
572     s11 += s19 * 136657;
573     s12 -= s19 * 683901;
574     s19 = 0;
575     s6 += s18 * 666643;
576     s7 += s18 * 470296;
577     s8 += s18 * 654183;
578     s9 -= s18 * 997805;
579     s10 += s18 * 136657;
580     s11 -= s18 * 683901;
581     s18 = 0;
582     carry6 = (s6 + (1 << 20)) >> 21;
583     s7 += carry6;
584     s6 -= carry6 << 21;
585     carry8 = (s8 + (1 << 20)) >> 21;
586     s9 += carry8;
587     s8 -= carry8 << 21;
588     carry10 = (s10 + (1 << 20)) >> 21;
589     s11 += carry10;
590     s10 -= carry10 << 21;
591     carry12 = (s12 + (1 << 20)) >> 21;
592     s13 += carry12;
593     s12 -= carry12 << 21;
594     carry14 = (s14 + (1 << 20)) >> 21;
595     s15 += carry14;
596     s14 -= carry14 << 21;
597     carry16 = (s16 + (1 << 20)) >> 21;
598     s17 += carry16;
599     s16 -= carry16 << 21;
600     carry7 = (s7 + (1 << 20)) >> 21;
601     s8 += carry7;
602     s7 -= carry7 << 21;
603     carry9 = (s9 + (1 << 20)) >> 21;
604     s10 += carry9;
605     s9 -= carry9 << 21;
606     carry11 = (s11 + (1 << 20)) >> 21;
607     s12 += carry11;
608     s11 -= carry11 << 21;
609     carry13 = (s13 + (1 << 20)) >> 21;
610     s14 += carry13;
611     s13 -= carry13 << 21;
612     carry15 = (s15 + (1 << 20)) >> 21;
613     s16 += carry15;
614     s15 -= carry15 << 21;
615     s5 += s17 * 666643;
616     s6 += s17 * 470296;
617     s7 += s17 * 654183;
618     s8 -= s17 * 997805;
619     s9 += s17 * 136657;
620     s10 -= s17 * 683901;
621     s17 = 0;
622     s4 += s16 * 666643;
623     s5 += s16 * 470296;
624     s6 += s16 * 654183;
625     s7 -= s16 * 997805;
626     s8 += s16 * 136657;
627     s9 -= s16 * 683901;
628     s16 = 0;
629     s3 += s15 * 666643;
630     s4 += s15 * 470296;
631     s5 += s15 * 654183;
632     s6 -= s15 * 997805;
633     s7 += s15 * 136657;
634     s8 -= s15 * 683901;
635     s15 = 0;
636     s2 += s14 * 666643;
637     s3 += s14 * 470296;
638     s4 += s14 * 654183;
639     s5 -= s14 * 997805;
640     s6 += s14 * 136657;
641     s7 -= s14 * 683901;
642     s14 = 0;
643     s1 += s13 * 666643;
644     s2 += s13 * 470296;
645     s3 += s13 * 654183;
646     s4 -= s13 * 997805;
647     s5 += s13 * 136657;
648     s6 -= s13 * 683901;
649     s13 = 0;
650     s0 += s12 * 666643;
651     s1 += s12 * 470296;
652     s2 += s12 * 654183;
653     s3 -= s12 * 997805;
654     s4 += s12 * 136657;
655     s5 -= s12 * 683901;
656     s12 = 0;
657     carry0 = (s0 + (1 << 20)) >> 21;
658     s1 += carry0;
659     s0 -= carry0 << 21;
660     carry2 = (s2 + (1 << 20)) >> 21;
661     s3 += carry2;
662     s2 -= carry2 << 21;
663     carry4 = (s4 + (1 << 20)) >> 21;
664     s5 += carry4;
665     s4 -= carry4 << 21;
666     carry6 = (s6 + (1 << 20)) >> 21;
667     s7 += carry6;
668     s6 -= carry6 << 21;
669     carry8 = (s8 + (1 << 20)) >> 21;
670     s9 += carry8;
671     s8 -= carry8 << 21;
672     carry10 = (s10 + (1 << 20)) >> 21;
673     s11 += carry10;
674     s10 -= carry10 << 21;
675     carry1 = (s1 + (1 << 20)) >> 21;
676     s2 += carry1;
677     s1 -= carry1 << 21;
678     carry3 = (s3 + (1 << 20)) >> 21;
679     s4 += carry3;
680     s3 -= carry3 << 21;
681     carry5 = (s5 + (1 << 20)) >> 21;
682     s6 += carry5;
683     s5 -= carry5 << 21;
684     carry7 = (s7 + (1 << 20)) >> 21;
685     s8 += carry7;
686     s7 -= carry7 << 21;
687     carry9 = (s9 + (1 << 20)) >> 21;
688     s10 += carry9;
689     s9 -= carry9 << 21;
690     carry11 = (s11 + (1 << 20)) >> 21;
691     s12 += carry11;
692     s11 -= carry11 << 21;
693     s0 += s12 * 666643;
694     s1 += s12 * 470296;
695     s2 += s12 * 654183;
696     s3 -= s12 * 997805;
697     s4 += s12 * 136657;
698     s5 -= s12 * 683901;
699     s12 = 0;
700     carry0 = s0 >> 21;
701     s1 += carry0;
702     s0 -= carry0 << 21;
703     carry1 = s1 >> 21;
704     s2 += carry1;
705     s1 -= carry1 << 21;
706     carry2 = s2 >> 21;
707     s3 += carry2;
708     s2 -= carry2 << 21;
709     carry3 = s3 >> 21;
710     s4 += carry3;
711     s3 -= carry3 << 21;
712     carry4 = s4 >> 21;
713     s5 += carry4;
714     s4 -= carry4 << 21;
715     carry5 = s5 >> 21;
716     s6 += carry5;
717     s5 -= carry5 << 21;
718     carry6 = s6 >> 21;
719     s7 += carry6;
720     s6 -= carry6 << 21;
721     carry7 = s7 >> 21;
722     s8 += carry7;
723     s7 -= carry7 << 21;
724     carry8 = s8 >> 21;
725     s9 += carry8;
726     s8 -= carry8 << 21;
727     carry9 = s9 >> 21;
728     s10 += carry9;
729     s9 -= carry9 << 21;
730     carry10 = s10 >> 21;
731     s11 += carry10;
732     s10 -= carry10 << 21;
733     carry11 = s11 >> 21;
734     s12 += carry11;
735     s11 -= carry11 << 21;
736     s0 += s12 * 666643;
737     s1 += s12 * 470296;
738     s2 += s12 * 654183;
739     s3 -= s12 * 997805;
740     s4 += s12 * 136657;
741     s5 -= s12 * 683901;
742     s12 = 0;
743     carry0 = s0 >> 21;
744     s1 += carry0;
745     s0 -= carry0 << 21;
746     carry1 = s1 >> 21;
747     s2 += carry1;
748     s1 -= carry1 << 21;
749     carry2 = s2 >> 21;
750     s3 += carry2;
751     s2 -= carry2 << 21;
752     carry3 = s3 >> 21;
753     s4 += carry3;
754     s3 -= carry3 << 21;
755     carry4 = s4 >> 21;
756     s5 += carry4;
757     s4 -= carry4 << 21;
758     carry5 = s5 >> 21;
759     s6 += carry5;
760     s5 -= carry5 << 21;
761     carry6 = s6 >> 21;
762     s7 += carry6;
763     s6 -= carry6 << 21;
764     carry7 = s7 >> 21;
765     s8 += carry7;
766     s7 -= carry7 << 21;
767     carry8 = s8 >> 21;
768     s9 += carry8;
769     s8 -= carry8 << 21;
770     carry9 = s9 >> 21;
771     s10 += carry9;
772     s9 -= carry9 << 21;
773     carry10 = s10 >> 21;
774     s11 += carry10;
775     s10 -= carry10 << 21;
776    
777     s[0] = (unsigned char) (s0 >> 0);
778     s[1] = (unsigned char) (s0 >> 8);
779     s[2] = (unsigned char) ((s0 >> 16) | (s1 << 5));
780     s[3] = (unsigned char) (s1 >> 3);
781     s[4] = (unsigned char) (s1 >> 11);
782     s[5] = (unsigned char) ((s1 >> 19) | (s2 << 2));
783     s[6] = (unsigned char) (s2 >> 6);
784     s[7] = (unsigned char) ((s2 >> 14) | (s3 << 7));
785     s[8] = (unsigned char) (s3 >> 1);
786     s[9] = (unsigned char) (s3 >> 9);
787     s[10] = (unsigned char) ((s3 >> 17) | (s4 << 4));
788     s[11] = (unsigned char) (s4 >> 4);
789     s[12] = (unsigned char) (s4 >> 12);
790     s[13] = (unsigned char) ((s4 >> 20) | (s5 << 1));
791     s[14] = (unsigned char) (s5 >> 7);
792     s[15] = (unsigned char) ((s5 >> 15) | (s6 << 6));
793     s[16] = (unsigned char) (s6 >> 2);
794     s[17] = (unsigned char) (s6 >> 10);
795     s[18] = (unsigned char) ((s6 >> 18) | (s7 << 3));
796     s[19] = (unsigned char) (s7 >> 5);
797     s[20] = (unsigned char) (s7 >> 13);
798     s[21] = (unsigned char) (s8 >> 0);
799     s[22] = (unsigned char) (s8 >> 8);
800     s[23] = (unsigned char) ((s8 >> 16) | (s9 << 5));
801     s[24] = (unsigned char) (s9 >> 3);
802     s[25] = (unsigned char) (s9 >> 11);
803     s[26] = (unsigned char) ((s9 >> 19) | (s10 << 2));
804     s[27] = (unsigned char) (s10 >> 6);
805     s[28] = (unsigned char) ((s10 >> 14) | (s11 << 7));
806     s[29] = (unsigned char) (s11 >> 1);
807     s[30] = (unsigned char) (s11 >> 9);
808     s[31] = (unsigned char) (s11 >> 17);
809     }