1 #include "fixedint.h" 2 #include "sc.h" 3 load_3(const unsigned char * in)4static 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 load_4(const unsigned char * in)14static 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 sc_reduce(unsigned char * s)35void 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 sc_muladd(unsigned char * s,const unsigned char * a,const unsigned char * b,const unsigned char * c)362void 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 } 810