ed25519/sc.c

   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 }