1 #include <string.h> 2 3 #include "private/common.h" 4 #include "utils.h" 5 6 /* 7 h = 0 8 */ 9 10 static inline void 11 fe25519_0(fe25519 h) 12 { 13 memset(&h[0], 0, 10 * sizeof h[0]); 14 } 15 16 /* 17 h = 1 18 */ 19 20 static inline void 21 fe25519_1(fe25519 h) 22 { 23 h[0] = 1; 24 h[1] = 0; 25 memset(&h[2], 0, 8 * sizeof h[0]); 26 } 27 28 /* 29 h = f + g 30 Can overlap h with f or g. 31 * 32 Preconditions: 33 |f| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc. 34 |g| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc. 35 * 36 Postconditions: 37 |h| bounded by 1.1*2^26,1.1*2^25,1.1*2^26,1.1*2^25,etc. 38 */ 39 40 static inline void 41 fe25519_add(fe25519 h, const fe25519 f, const fe25519 g) 42 { 43 int32_t h0 = f[0] + g[0]; 44 int32_t h1 = f[1] + g[1]; 45 int32_t h2 = f[2] + g[2]; 46 int32_t h3 = f[3] + g[3]; 47 int32_t h4 = f[4] + g[4]; 48 int32_t h5 = f[5] + g[5]; 49 int32_t h6 = f[6] + g[6]; 50 int32_t h7 = f[7] + g[7]; 51 int32_t h8 = f[8] + g[8]; 52 int32_t h9 = f[9] + g[9]; 53 54 h[0] = h0; 55 h[1] = h1; 56 h[2] = h2; 57 h[3] = h3; 58 h[4] = h4; 59 h[5] = h5; 60 h[6] = h6; 61 h[7] = h7; 62 h[8] = h8; 63 h[9] = h9; 64 } 65 66 /* 67 h = f - g 68 Can overlap h with f or g. 69 * 70 Preconditions: 71 |f| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc. 72 |g| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc. 73 * 74 Postconditions: 75 |h| bounded by 1.1*2^26,1.1*2^25,1.1*2^26,1.1*2^25,etc. 76 */ 77 78 static void 79 fe25519_sub(fe25519 h, const fe25519 f, const fe25519 g) 80 { 81 int32_t h0 = f[0] - g[0]; 82 int32_t h1 = f[1] - g[1]; 83 int32_t h2 = f[2] - g[2]; 84 int32_t h3 = f[3] - g[3]; 85 int32_t h4 = f[4] - g[4]; 86 int32_t h5 = f[5] - g[5]; 87 int32_t h6 = f[6] - g[6]; 88 int32_t h7 = f[7] - g[7]; 89 int32_t h8 = f[8] - g[8]; 90 int32_t h9 = f[9] - g[9]; 91 92 h[0] = h0; 93 h[1] = h1; 94 h[2] = h2; 95 h[3] = h3; 96 h[4] = h4; 97 h[5] = h5; 98 h[6] = h6; 99 h[7] = h7; 100 h[8] = h8; 101 h[9] = h9; 102 } 103 104 /* 105 h = -f 106 * 107 Preconditions: 108 |f| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc. 109 * 110 Postconditions: 111 |h| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc. 112 */ 113 114 static inline void 115 fe25519_neg(fe25519 h, const fe25519 f) 116 { 117 int32_t h0 = -f[0]; 118 int32_t h1 = -f[1]; 119 int32_t h2 = -f[2]; 120 int32_t h3 = -f[3]; 121 int32_t h4 = -f[4]; 122 int32_t h5 = -f[5]; 123 int32_t h6 = -f[6]; 124 int32_t h7 = -f[7]; 125 int32_t h8 = -f[8]; 126 int32_t h9 = -f[9]; 127 128 h[0] = h0; 129 h[1] = h1; 130 h[2] = h2; 131 h[3] = h3; 132 h[4] = h4; 133 h[5] = h5; 134 h[6] = h6; 135 h[7] = h7; 136 h[8] = h8; 137 h[9] = h9; 138 } 139 140 /* 141 Replace (f,g) with (g,g) if b == 1; 142 replace (f,g) with (f,g) if b == 0. 143 * 144 Preconditions: b in {0,1}. 145 */ 146 147 static void 148 fe25519_cmov(fe25519 f, const fe25519 g, unsigned int b) 149 { 150 const uint32_t mask = (uint32_t) (-(int32_t) b); 151 152 int32_t f0 = f[0]; 153 int32_t f1 = f[1]; 154 int32_t f2 = f[2]; 155 int32_t f3 = f[3]; 156 int32_t f4 = f[4]; 157 int32_t f5 = f[5]; 158 int32_t f6 = f[6]; 159 int32_t f7 = f[7]; 160 int32_t f8 = f[8]; 161 int32_t f9 = f[9]; 162 163 int32_t x0 = f0 ^ g[0]; 164 int32_t x1 = f1 ^ g[1]; 165 int32_t x2 = f2 ^ g[2]; 166 int32_t x3 = f3 ^ g[3]; 167 int32_t x4 = f4 ^ g[4]; 168 int32_t x5 = f5 ^ g[5]; 169 int32_t x6 = f6 ^ g[6]; 170 int32_t x7 = f7 ^ g[7]; 171 int32_t x8 = f8 ^ g[8]; 172 int32_t x9 = f9 ^ g[9]; 173 174 x0 &= mask; 175 x1 &= mask; 176 x2 &= mask; 177 x3 &= mask; 178 x4 &= mask; 179 x5 &= mask; 180 x6 &= mask; 181 x7 &= mask; 182 x8 &= mask; 183 x9 &= mask; 184 185 f[0] = f0 ^ x0; 186 f[1] = f1 ^ x1; 187 f[2] = f2 ^ x2; 188 f[3] = f3 ^ x3; 189 f[4] = f4 ^ x4; 190 f[5] = f5 ^ x5; 191 f[6] = f6 ^ x6; 192 f[7] = f7 ^ x7; 193 f[8] = f8 ^ x8; 194 f[9] = f9 ^ x9; 195 } 196 197 static void 198 fe25519_cswap(fe25519 f, fe25519 g, unsigned int b) 199 { 200 const uint32_t mask = (uint32_t) (-(int64_t) b); 201 202 int32_t f0 = f[0]; 203 int32_t f1 = f[1]; 204 int32_t f2 = f[2]; 205 int32_t f3 = f[3]; 206 int32_t f4 = f[4]; 207 int32_t f5 = f[5]; 208 int32_t f6 = f[6]; 209 int32_t f7 = f[7]; 210 int32_t f8 = f[8]; 211 int32_t f9 = f[9]; 212 213 int32_t g0 = g[0]; 214 int32_t g1 = g[1]; 215 int32_t g2 = g[2]; 216 int32_t g3 = g[3]; 217 int32_t g4 = g[4]; 218 int32_t g5 = g[5]; 219 int32_t g6 = g[6]; 220 int32_t g7 = g[7]; 221 int32_t g8 = g[8]; 222 int32_t g9 = g[9]; 223 224 int32_t x0 = f0 ^ g0; 225 int32_t x1 = f1 ^ g1; 226 int32_t x2 = f2 ^ g2; 227 int32_t x3 = f3 ^ g3; 228 int32_t x4 = f4 ^ g4; 229 int32_t x5 = f5 ^ g5; 230 int32_t x6 = f6 ^ g6; 231 int32_t x7 = f7 ^ g7; 232 int32_t x8 = f8 ^ g8; 233 int32_t x9 = f9 ^ g9; 234 235 x0 &= mask; 236 x1 &= mask; 237 x2 &= mask; 238 x3 &= mask; 239 x4 &= mask; 240 x5 &= mask; 241 x6 &= mask; 242 x7 &= mask; 243 x8 &= mask; 244 x9 &= mask; 245 246 f[0] = f0 ^ x0; 247 f[1] = f1 ^ x1; 248 f[2] = f2 ^ x2; 249 f[3] = f3 ^ x3; 250 f[4] = f4 ^ x4; 251 f[5] = f5 ^ x5; 252 f[6] = f6 ^ x6; 253 f[7] = f7 ^ x7; 254 f[8] = f8 ^ x8; 255 f[9] = f9 ^ x9; 256 257 g[0] = g0 ^ x0; 258 g[1] = g1 ^ x1; 259 g[2] = g2 ^ x2; 260 g[3] = g3 ^ x3; 261 g[4] = g4 ^ x4; 262 g[5] = g5 ^ x5; 263 g[6] = g6 ^ x6; 264 g[7] = g7 ^ x7; 265 g[8] = g8 ^ x8; 266 g[9] = g9 ^ x9; 267 } 268 269 /* 270 h = f 271 */ 272 273 static inline void 274 fe25519_copy(fe25519 h, const fe25519 f) 275 { 276 int32_t f0 = f[0]; 277 int32_t f1 = f[1]; 278 int32_t f2 = f[2]; 279 int32_t f3 = f[3]; 280 int32_t f4 = f[4]; 281 int32_t f5 = f[5]; 282 int32_t f6 = f[6]; 283 int32_t f7 = f[7]; 284 int32_t f8 = f[8]; 285 int32_t f9 = f[9]; 286 287 h[0] = f0; 288 h[1] = f1; 289 h[2] = f2; 290 h[3] = f3; 291 h[4] = f4; 292 h[5] = f5; 293 h[6] = f6; 294 h[7] = f7; 295 h[8] = f8; 296 h[9] = f9; 297 } 298 299 /* 300 return 1 if f is in {1,3,5,...,q-2} 301 return 0 if f is in {0,2,4,...,q-1} 302 303 Preconditions: 304 |f| bounded by 1.1*2^26,1.1*2^25,1.1*2^26,1.1*2^25,etc. 305 */ 306 307 static inline int 308 fe25519_isnegative(const fe25519 f) 309 { 310 unsigned char s[32]; 311 312 fe25519_tobytes(s, f); 313 314 return s[0] & 1; 315 } 316 317 /* 318 return 1 if f == 0 319 return 0 if f != 0 320 321 Preconditions: 322 |f| bounded by 1.1*2^26,1.1*2^25,1.1*2^26,1.1*2^25,etc. 323 */ 324 325 static inline int 326 fe25519_iszero(const fe25519 f) 327 { 328 unsigned char s[32]; 329 330 fe25519_tobytes(s, f); 331 332 return sodium_is_zero(s, 32); 333 } 334 335 /* 336 h = f * g 337 Can overlap h with f or g. 338 * 339 Preconditions: 340 |f| bounded by 1.65*2^26,1.65*2^25,1.65*2^26,1.65*2^25,etc. 341 |g| bounded by 1.65*2^26,1.65*2^25,1.65*2^26,1.65*2^25,etc. 342 * 343 Postconditions: 344 |h| bounded by 1.01*2^25,1.01*2^24,1.01*2^25,1.01*2^24,etc. 345 */ 346 347 /* 348 Notes on implementation strategy: 349 * 350 Using schoolbook multiplication. 351 Karatsuba would save a little in some cost models. 352 * 353 Most multiplications by 2 and 19 are 32-bit precomputations; 354 cheaper than 64-bit postcomputations. 355 * 356 There is one remaining multiplication by 19 in the carry chain; 357 one *19 precomputation can be merged into this, 358 but the resulting data flow is considerably less clean. 359 * 360 There are 12 carries below. 361 10 of them are 2-way parallelizable and vectorizable. 362 Can get away with 11 carries, but then data flow is much deeper. 363 * 364 With tighter constraints on inputs can squeeze carries into int32. 365 */ 366 367 static void 368 fe25519_mul(fe25519 h, const fe25519 f, const fe25519 g) 369 { 370 int32_t f0 = f[0]; 371 int32_t f1 = f[1]; 372 int32_t f2 = f[2]; 373 int32_t f3 = f[3]; 374 int32_t f4 = f[4]; 375 int32_t f5 = f[5]; 376 int32_t f6 = f[6]; 377 int32_t f7 = f[7]; 378 int32_t f8 = f[8]; 379 int32_t f9 = f[9]; 380 381 int32_t g0 = g[0]; 382 int32_t g1 = g[1]; 383 int32_t g2 = g[2]; 384 int32_t g3 = g[3]; 385 int32_t g4 = g[4]; 386 int32_t g5 = g[5]; 387 int32_t g6 = g[6]; 388 int32_t g7 = g[7]; 389 int32_t g8 = g[8]; 390 int32_t g9 = g[9]; 391 392 int32_t g1_19 = 19 * g1; /* 1.959375*2^29 */ 393 int32_t g2_19 = 19 * g2; /* 1.959375*2^30; still ok */ 394 int32_t g3_19 = 19 * g3; 395 int32_t g4_19 = 19 * g4; 396 int32_t g5_19 = 19 * g5; 397 int32_t g6_19 = 19 * g6; 398 int32_t g7_19 = 19 * g7; 399 int32_t g8_19 = 19 * g8; 400 int32_t g9_19 = 19 * g9; 401 int32_t f1_2 = 2 * f1; 402 int32_t f3_2 = 2 * f3; 403 int32_t f5_2 = 2 * f5; 404 int32_t f7_2 = 2 * f7; 405 int32_t f9_2 = 2 * f9; 406 407 int64_t f0g0 = f0 * (int64_t) g0; 408 int64_t f0g1 = f0 * (int64_t) g1; 409 int64_t f0g2 = f0 * (int64_t) g2; 410 int64_t f0g3 = f0 * (int64_t) g3; 411 int64_t f0g4 = f0 * (int64_t) g4; 412 int64_t f0g5 = f0 * (int64_t) g5; 413 int64_t f0g6 = f0 * (int64_t) g6; 414 int64_t f0g7 = f0 * (int64_t) g7; 415 int64_t f0g8 = f0 * (int64_t) g8; 416 int64_t f0g9 = f0 * (int64_t) g9; 417 int64_t f1g0 = f1 * (int64_t) g0; 418 int64_t f1g1_2 = f1_2 * (int64_t) g1; 419 int64_t f1g2 = f1 * (int64_t) g2; 420 int64_t f1g3_2 = f1_2 * (int64_t) g3; 421 int64_t f1g4 = f1 * (int64_t) g4; 422 int64_t f1g5_2 = f1_2 * (int64_t) g5; 423 int64_t f1g6 = f1 * (int64_t) g6; 424 int64_t f1g7_2 = f1_2 * (int64_t) g7; 425 int64_t f1g8 = f1 * (int64_t) g8; 426 int64_t f1g9_38 = f1_2 * (int64_t) g9_19; 427 int64_t f2g0 = f2 * (int64_t) g0; 428 int64_t f2g1 = f2 * (int64_t) g1; 429 int64_t f2g2 = f2 * (int64_t) g2; 430 int64_t f2g3 = f2 * (int64_t) g3; 431 int64_t f2g4 = f2 * (int64_t) g4; 432 int64_t f2g5 = f2 * (int64_t) g5; 433 int64_t f2g6 = f2 * (int64_t) g6; 434 int64_t f2g7 = f2 * (int64_t) g7; 435 int64_t f2g8_19 = f2 * (int64_t) g8_19; 436 int64_t f2g9_19 = f2 * (int64_t) g9_19; 437 int64_t f3g0 = f3 * (int64_t) g0; 438 int64_t f3g1_2 = f3_2 * (int64_t) g1; 439 int64_t f3g2 = f3 * (int64_t) g2; 440 int64_t f3g3_2 = f3_2 * (int64_t) g3; 441 int64_t f3g4 = f3 * (int64_t) g4; 442 int64_t f3g5_2 = f3_2 * (int64_t) g5; 443 int64_t f3g6 = f3 * (int64_t) g6; 444 int64_t f3g7_38 = f3_2 * (int64_t) g7_19; 445 int64_t f3g8_19 = f3 * (int64_t) g8_19; 446 int64_t f3g9_38 = f3_2 * (int64_t) g9_19; 447 int64_t f4g0 = f4 * (int64_t) g0; 448 int64_t f4g1 = f4 * (int64_t) g1; 449 int64_t f4g2 = f4 * (int64_t) g2; 450 int64_t f4g3 = f4 * (int64_t) g3; 451 int64_t f4g4 = f4 * (int64_t) g4; 452 int64_t f4g5 = f4 * (int64_t) g5; 453 int64_t f4g6_19 = f4 * (int64_t) g6_19; 454 int64_t f4g7_19 = f4 * (int64_t) g7_19; 455 int64_t f4g8_19 = f4 * (int64_t) g8_19; 456 int64_t f4g9_19 = f4 * (int64_t) g9_19; 457 int64_t f5g0 = f5 * (int64_t) g0; 458 int64_t f5g1_2 = f5_2 * (int64_t) g1; 459 int64_t f5g2 = f5 * (int64_t) g2; 460 int64_t f5g3_2 = f5_2 * (int64_t) g3; 461 int64_t f5g4 = f5 * (int64_t) g4; 462 int64_t f5g5_38 = f5_2 * (int64_t) g5_19; 463 int64_t f5g6_19 = f5 * (int64_t) g6_19; 464 int64_t f5g7_38 = f5_2 * (int64_t) g7_19; 465 int64_t f5g8_19 = f5 * (int64_t) g8_19; 466 int64_t f5g9_38 = f5_2 * (int64_t) g9_19; 467 int64_t f6g0 = f6 * (int64_t) g0; 468 int64_t f6g1 = f6 * (int64_t) g1; 469 int64_t f6g2 = f6 * (int64_t) g2; 470 int64_t f6g3 = f6 * (int64_t) g3; 471 int64_t f6g4_19 = f6 * (int64_t) g4_19; 472 int64_t f6g5_19 = f6 * (int64_t) g5_19; 473 int64_t f6g6_19 = f6 * (int64_t) g6_19; 474 int64_t f6g7_19 = f6 * (int64_t) g7_19; 475 int64_t f6g8_19 = f6 * (int64_t) g8_19; 476 int64_t f6g9_19 = f6 * (int64_t) g9_19; 477 int64_t f7g0 = f7 * (int64_t) g0; 478 int64_t f7g1_2 = f7_2 * (int64_t) g1; 479 int64_t f7g2 = f7 * (int64_t) g2; 480 int64_t f7g3_38 = f7_2 * (int64_t) g3_19; 481 int64_t f7g4_19 = f7 * (int64_t) g4_19; 482 int64_t f7g5_38 = f7_2 * (int64_t) g5_19; 483 int64_t f7g6_19 = f7 * (int64_t) g6_19; 484 int64_t f7g7_38 = f7_2 * (int64_t) g7_19; 485 int64_t f7g8_19 = f7 * (int64_t) g8_19; 486 int64_t f7g9_38 = f7_2 * (int64_t) g9_19; 487 int64_t f8g0 = f8 * (int64_t) g0; 488 int64_t f8g1 = f8 * (int64_t) g1; 489 int64_t f8g2_19 = f8 * (int64_t) g2_19; 490 int64_t f8g3_19 = f8 * (int64_t) g3_19; 491 int64_t f8g4_19 = f8 * (int64_t) g4_19; 492 int64_t f8g5_19 = f8 * (int64_t) g5_19; 493 int64_t f8g6_19 = f8 * (int64_t) g6_19; 494 int64_t f8g7_19 = f8 * (int64_t) g7_19; 495 int64_t f8g8_19 = f8 * (int64_t) g8_19; 496 int64_t f8g9_19 = f8 * (int64_t) g9_19; 497 int64_t f9g0 = f9 * (int64_t) g0; 498 int64_t f9g1_38 = f9_2 * (int64_t) g1_19; 499 int64_t f9g2_19 = f9 * (int64_t) g2_19; 500 int64_t f9g3_38 = f9_2 * (int64_t) g3_19; 501 int64_t f9g4_19 = f9 * (int64_t) g4_19; 502 int64_t f9g5_38 = f9_2 * (int64_t) g5_19; 503 int64_t f9g6_19 = f9 * (int64_t) g6_19; 504 int64_t f9g7_38 = f9_2 * (int64_t) g7_19; 505 int64_t f9g8_19 = f9 * (int64_t) g8_19; 506 int64_t f9g9_38 = f9_2 * (int64_t) g9_19; 507 508 int64_t h0 = f0g0 + f1g9_38 + f2g8_19 + f3g7_38 + f4g6_19 + f5g5_38 + 509 f6g4_19 + f7g3_38 + f8g2_19 + f9g1_38; 510 int64_t h1 = f0g1 + f1g0 + f2g9_19 + f3g8_19 + f4g7_19 + f5g6_19 + f6g5_19 + 511 f7g4_19 + f8g3_19 + f9g2_19; 512 int64_t h2 = f0g2 + f1g1_2 + f2g0 + f3g9_38 + f4g8_19 + f5g7_38 + f6g6_19 + 513 f7g5_38 + f8g4_19 + f9g3_38; 514 int64_t h3 = f0g3 + f1g2 + f2g1 + f3g0 + f4g9_19 + f5g8_19 + f6g7_19 + 515 f7g6_19 + f8g5_19 + f9g4_19; 516 int64_t h4 = f0g4 + f1g3_2 + f2g2 + f3g1_2 + f4g0 + f5g9_38 + f6g8_19 + 517 f7g7_38 + f8g6_19 + f9g5_38; 518 int64_t h5 = f0g5 + f1g4 + f2g3 + f3g2 + f4g1 + f5g0 + f6g9_19 + f7g8_19 + 519 f8g7_19 + f9g6_19; 520 int64_t h6 = f0g6 + f1g5_2 + f2g4 + f3g3_2 + f4g2 + f5g1_2 + f6g0 + 521 f7g9_38 + f8g8_19 + f9g7_38; 522 int64_t h7 = f0g7 + f1g6 + f2g5 + f3g4 + f4g3 + f5g2 + f6g1 + f7g0 + 523 f8g9_19 + f9g8_19; 524 int64_t h8 = f0g8 + f1g7_2 + f2g6 + f3g5_2 + f4g4 + f5g3_2 + f6g2 + f7g1_2 + 525 f8g0 + f9g9_38; 526 int64_t h9 = 527 f0g9 + f1g8 + f2g7 + f3g6 + f4g5 + f5g4 + f6g3 + f7g2 + f8g1 + f9g0; 528 529 int64_t carry0; 530 int64_t carry1; 531 int64_t carry2; 532 int64_t carry3; 533 int64_t carry4; 534 int64_t carry5; 535 int64_t carry6; 536 int64_t carry7; 537 int64_t carry8; 538 int64_t carry9; 539 540 /* 541 |h0| <= (1.65*1.65*2^52*(1+19+19+19+19)+1.65*1.65*2^50*(38+38+38+38+38)) 542 i.e. |h0| <= 1.4*2^60; narrower ranges for h2, h4, h6, h8 543 |h1| <= (1.65*1.65*2^51*(1+1+19+19+19+19+19+19+19+19)) 544 i.e. |h1| <= 1.7*2^59; narrower ranges for h3, h5, h7, h9 545 */ 546 547 carry0 = (h0 + (int64_t)(1L << 25)) >> 26; 548 h1 += carry0; 549 h0 -= carry0 * ((uint64_t) 1L << 26); 550 carry4 = (h4 + (int64_t)(1L << 25)) >> 26; 551 h5 += carry4; 552 h4 -= carry4 * ((uint64_t) 1L << 26); 553 /* |h0| <= 2^25 */ 554 /* |h4| <= 2^25 */ 555 /* |h1| <= 1.71*2^59 */ 556 /* |h5| <= 1.71*2^59 */ 557 558 carry1 = (h1 + (int64_t)(1L << 24)) >> 25; 559 h2 += carry1; 560 h1 -= carry1 * ((uint64_t) 1L << 25); 561 carry5 = (h5 + (int64_t)(1L << 24)) >> 25; 562 h6 += carry5; 563 h5 -= carry5 * ((uint64_t) 1L << 25); 564 /* |h1| <= 2^24; from now on fits into int32 */ 565 /* |h5| <= 2^24; from now on fits into int32 */ 566 /* |h2| <= 1.41*2^60 */ 567 /* |h6| <= 1.41*2^60 */ 568 569 carry2 = (h2 + (int64_t)(1L << 25)) >> 26; 570 h3 += carry2; 571 h2 -= carry2 * ((uint64_t) 1L << 26); 572 carry6 = (h6 + (int64_t)(1L << 25)) >> 26; 573 h7 += carry6; 574 h6 -= carry6 * ((uint64_t) 1L << 26); 575 /* |h2| <= 2^25; from now on fits into int32 unchanged */ 576 /* |h6| <= 2^25; from now on fits into int32 unchanged */ 577 /* |h3| <= 1.71*2^59 */ 578 /* |h7| <= 1.71*2^59 */ 579 580 carry3 = (h3 + (int64_t)(1L << 24)) >> 25; 581 h4 += carry3; 582 h3 -= carry3 * ((uint64_t) 1L << 25); 583 carry7 = (h7 + (int64_t)(1L << 24)) >> 25; 584 h8 += carry7; 585 h7 -= carry7 * ((uint64_t) 1L << 25); 586 /* |h3| <= 2^24; from now on fits into int32 unchanged */ 587 /* |h7| <= 2^24; from now on fits into int32 unchanged */ 588 /* |h4| <= 1.72*2^34 */ 589 /* |h8| <= 1.41*2^60 */ 590 591 carry4 = (h4 + (int64_t)(1L << 25)) >> 26; 592 h5 += carry4; 593 h4 -= carry4 * ((uint64_t) 1L << 26); 594 carry8 = (h8 + (int64_t)(1L << 25)) >> 26; 595 h9 += carry8; 596 h8 -= carry8 * ((uint64_t) 1L << 26); 597 /* |h4| <= 2^25; from now on fits into int32 unchanged */ 598 /* |h8| <= 2^25; from now on fits into int32 unchanged */ 599 /* |h5| <= 1.01*2^24 */ 600 /* |h9| <= 1.71*2^59 */ 601 602 carry9 = (h9 + (int64_t)(1L << 24)) >> 25; 603 h0 += carry9 * 19; 604 h9 -= carry9 * ((uint64_t) 1L << 25); 605 /* |h9| <= 2^24; from now on fits into int32 unchanged */ 606 /* |h0| <= 1.1*2^39 */ 607 608 carry0 = (h0 + (int64_t)(1L << 25)) >> 26; 609 h1 += carry0; 610 h0 -= carry0 * ((uint64_t) 1L << 26); 611 /* |h0| <= 2^25; from now on fits into int32 unchanged */ 612 /* |h1| <= 1.01*2^24 */ 613 614 h[0] = (int32_t) h0; 615 h[1] = (int32_t) h1; 616 h[2] = (int32_t) h2; 617 h[3] = (int32_t) h3; 618 h[4] = (int32_t) h4; 619 h[5] = (int32_t) h5; 620 h[6] = (int32_t) h6; 621 h[7] = (int32_t) h7; 622 h[8] = (int32_t) h8; 623 h[9] = (int32_t) h9; 624 } 625 626 /* 627 h = f * f 628 Can overlap h with f. 629 * 630 Preconditions: 631 |f| bounded by 1.65*2^26,1.65*2^25,1.65*2^26,1.65*2^25,etc. 632 * 633 Postconditions: 634 |h| bounded by 1.01*2^25,1.01*2^24,1.01*2^25,1.01*2^24,etc. 635 */ 636 637 static void 638 fe25519_sq(fe25519 h, const fe25519 f) 639 { 640 int32_t f0 = f[0]; 641 int32_t f1 = f[1]; 642 int32_t f2 = f[2]; 643 int32_t f3 = f[3]; 644 int32_t f4 = f[4]; 645 int32_t f5 = f[5]; 646 int32_t f6 = f[6]; 647 int32_t f7 = f[7]; 648 int32_t f8 = f[8]; 649 int32_t f9 = f[9]; 650 651 int32_t f0_2 = 2 * f0; 652 int32_t f1_2 = 2 * f1; 653 int32_t f2_2 = 2 * f2; 654 int32_t f3_2 = 2 * f3; 655 int32_t f4_2 = 2 * f4; 656 int32_t f5_2 = 2 * f5; 657 int32_t f6_2 = 2 * f6; 658 int32_t f7_2 = 2 * f7; 659 int32_t f5_38 = 38 * f5; /* 1.959375*2^30 */ 660 int32_t f6_19 = 19 * f6; /* 1.959375*2^30 */ 661 int32_t f7_38 = 38 * f7; /* 1.959375*2^30 */ 662 int32_t f8_19 = 19 * f8; /* 1.959375*2^30 */ 663 int32_t f9_38 = 38 * f9; /* 1.959375*2^30 */ 664 665 int64_t f0f0 = f0 * (int64_t) f0; 666 int64_t f0f1_2 = f0_2 * (int64_t) f1; 667 int64_t f0f2_2 = f0_2 * (int64_t) f2; 668 int64_t f0f3_2 = f0_2 * (int64_t) f3; 669 int64_t f0f4_2 = f0_2 * (int64_t) f4; 670 int64_t f0f5_2 = f0_2 * (int64_t) f5; 671 int64_t f0f6_2 = f0_2 * (int64_t) f6; 672 int64_t f0f7_2 = f0_2 * (int64_t) f7; 673 int64_t f0f8_2 = f0_2 * (int64_t) f8; 674 int64_t f0f9_2 = f0_2 * (int64_t) f9; 675 int64_t f1f1_2 = f1_2 * (int64_t) f1; 676 int64_t f1f2_2 = f1_2 * (int64_t) f2; 677 int64_t f1f3_4 = f1_2 * (int64_t) f3_2; 678 int64_t f1f4_2 = f1_2 * (int64_t) f4; 679 int64_t f1f5_4 = f1_2 * (int64_t) f5_2; 680 int64_t f1f6_2 = f1_2 * (int64_t) f6; 681 int64_t f1f7_4 = f1_2 * (int64_t) f7_2; 682 int64_t f1f8_2 = f1_2 * (int64_t) f8; 683 int64_t f1f9_76 = f1_2 * (int64_t) f9_38; 684 int64_t f2f2 = f2 * (int64_t) f2; 685 int64_t f2f3_2 = f2_2 * (int64_t) f3; 686 int64_t f2f4_2 = f2_2 * (int64_t) f4; 687 int64_t f2f5_2 = f2_2 * (int64_t) f5; 688 int64_t f2f6_2 = f2_2 * (int64_t) f6; 689 int64_t f2f7_2 = f2_2 * (int64_t) f7; 690 int64_t f2f8_38 = f2_2 * (int64_t) f8_19; 691 int64_t f2f9_38 = f2 * (int64_t) f9_38; 692 int64_t f3f3_2 = f3_2 * (int64_t) f3; 693 int64_t f3f4_2 = f3_2 * (int64_t) f4; 694 int64_t f3f5_4 = f3_2 * (int64_t) f5_2; 695 int64_t f3f6_2 = f3_2 * (int64_t) f6; 696 int64_t f3f7_76 = f3_2 * (int64_t) f7_38; 697 int64_t f3f8_38 = f3_2 * (int64_t) f8_19; 698 int64_t f3f9_76 = f3_2 * (int64_t) f9_38; 699 int64_t f4f4 = f4 * (int64_t) f4; 700 int64_t f4f5_2 = f4_2 * (int64_t) f5; 701 int64_t f4f6_38 = f4_2 * (int64_t) f6_19; 702 int64_t f4f7_38 = f4 * (int64_t) f7_38; 703 int64_t f4f8_38 = f4_2 * (int64_t) f8_19; 704 int64_t f4f9_38 = f4 * (int64_t) f9_38; 705 int64_t f5f5_38 = f5 * (int64_t) f5_38; 706 int64_t f5f6_38 = f5_2 * (int64_t) f6_19; 707 int64_t f5f7_76 = f5_2 * (int64_t) f7_38; 708 int64_t f5f8_38 = f5_2 * (int64_t) f8_19; 709 int64_t f5f9_76 = f5_2 * (int64_t) f9_38; 710 int64_t f6f6_19 = f6 * (int64_t) f6_19; 711 int64_t f6f7_38 = f6 * (int64_t) f7_38; 712 int64_t f6f8_38 = f6_2 * (int64_t) f8_19; 713 int64_t f6f9_38 = f6 * (int64_t) f9_38; 714 int64_t f7f7_38 = f7 * (int64_t) f7_38; 715 int64_t f7f8_38 = f7_2 * (int64_t) f8_19; 716 int64_t f7f9_76 = f7_2 * (int64_t) f9_38; 717 int64_t f8f8_19 = f8 * (int64_t) f8_19; 718 int64_t f8f9_38 = f8 * (int64_t) f9_38; 719 int64_t f9f9_38 = f9 * (int64_t) f9_38; 720 721 int64_t h0 = f0f0 + f1f9_76 + f2f8_38 + f3f7_76 + f4f6_38 + f5f5_38; 722 int64_t h1 = f0f1_2 + f2f9_38 + f3f8_38 + f4f7_38 + f5f6_38; 723 int64_t h2 = f0f2_2 + f1f1_2 + f3f9_76 + f4f8_38 + f5f7_76 + f6f6_19; 724 int64_t h3 = f0f3_2 + f1f2_2 + f4f9_38 + f5f8_38 + f6f7_38; 725 int64_t h4 = f0f4_2 + f1f3_4 + f2f2 + f5f9_76 + f6f8_38 + f7f7_38; 726 int64_t h5 = f0f5_2 + f1f4_2 + f2f3_2 + f6f9_38 + f7f8_38; 727 int64_t h6 = f0f6_2 + f1f5_4 + f2f4_2 + f3f3_2 + f7f9_76 + f8f8_19; 728 int64_t h7 = f0f7_2 + f1f6_2 + f2f5_2 + f3f4_2 + f8f9_38; 729 int64_t h8 = f0f8_2 + f1f7_4 + f2f6_2 + f3f5_4 + f4f4 + f9f9_38; 730 int64_t h9 = f0f9_2 + f1f8_2 + f2f7_2 + f3f6_2 + f4f5_2; 731 732 int64_t carry0; 733 int64_t carry1; 734 int64_t carry2; 735 int64_t carry3; 736 int64_t carry4; 737 int64_t carry5; 738 int64_t carry6; 739 int64_t carry7; 740 int64_t carry8; 741 int64_t carry9; 742 743 carry0 = (h0 + (int64_t)(1L << 25)) >> 26; 744 h1 += carry0; 745 h0 -= carry0 * ((uint64_t) 1L << 26); 746 carry4 = (h4 + (int64_t)(1L << 25)) >> 26; 747 h5 += carry4; 748 h4 -= carry4 * ((uint64_t) 1L << 26); 749 750 carry1 = (h1 + (int64_t)(1L << 24)) >> 25; 751 h2 += carry1; 752 h1 -= carry1 * ((uint64_t) 1L << 25); 753 carry5 = (h5 + (int64_t)(1L << 24)) >> 25; 754 h6 += carry5; 755 h5 -= carry5 * ((uint64_t) 1L << 25); 756 757 carry2 = (h2 + (int64_t)(1L << 25)) >> 26; 758 h3 += carry2; 759 h2 -= carry2 * ((uint64_t) 1L << 26); 760 carry6 = (h6 + (int64_t)(1L << 25)) >> 26; 761 h7 += carry6; 762 h6 -= carry6 * ((uint64_t) 1L << 26); 763 764 carry3 = (h3 + (int64_t)(1L << 24)) >> 25; 765 h4 += carry3; 766 h3 -= carry3 * ((uint64_t) 1L << 25); 767 carry7 = (h7 + (int64_t)(1L << 24)) >> 25; 768 h8 += carry7; 769 h7 -= carry7 * ((uint64_t) 1L << 25); 770 771 carry4 = (h4 + (int64_t)(1L << 25)) >> 26; 772 h5 += carry4; 773 h4 -= carry4 * ((uint64_t) 1L << 26); 774 carry8 = (h8 + (int64_t)(1L << 25)) >> 26; 775 h9 += carry8; 776 h8 -= carry8 * ((uint64_t) 1L << 26); 777 778 carry9 = (h9 + (int64_t)(1L << 24)) >> 25; 779 h0 += carry9 * 19; 780 h9 -= carry9 * ((uint64_t) 1L << 25); 781 782 carry0 = (h0 + (int64_t)(1L << 25)) >> 26; 783 h1 += carry0; 784 h0 -= carry0 * ((uint64_t) 1L << 26); 785 786 h[0] = (int32_t) h0; 787 h[1] = (int32_t) h1; 788 h[2] = (int32_t) h2; 789 h[3] = (int32_t) h3; 790 h[4] = (int32_t) h4; 791 h[5] = (int32_t) h5; 792 h[6] = (int32_t) h6; 793 h[7] = (int32_t) h7; 794 h[8] = (int32_t) h8; 795 h[9] = (int32_t) h9; 796 } 797 798 /* 799 h = 2 * f * f 800 Can overlap h with f. 801 * 802 Preconditions: 803 |f| bounded by 1.65*2^26,1.65*2^25,1.65*2^26,1.65*2^25,etc. 804 * 805 Postconditions: 806 |h| bounded by 1.01*2^25,1.01*2^24,1.01*2^25,1.01*2^24,etc. 807 */ 808 809 static void 810 fe25519_sq2(fe25519 h, const fe25519 f) 811 { 812 int32_t f0 = f[0]; 813 int32_t f1 = f[1]; 814 int32_t f2 = f[2]; 815 int32_t f3 = f[3]; 816 int32_t f4 = f[4]; 817 int32_t f5 = f[5]; 818 int32_t f6 = f[6]; 819 int32_t f7 = f[7]; 820 int32_t f8 = f[8]; 821 int32_t f9 = f[9]; 822 823 int32_t f0_2 = 2 * f0; 824 int32_t f1_2 = 2 * f1; 825 int32_t f2_2 = 2 * f2; 826 int32_t f3_2 = 2 * f3; 827 int32_t f4_2 = 2 * f4; 828 int32_t f5_2 = 2 * f5; 829 int32_t f6_2 = 2 * f6; 830 int32_t f7_2 = 2 * f7; 831 int32_t f5_38 = 38 * f5; /* 1.959375*2^30 */ 832 int32_t f6_19 = 19 * f6; /* 1.959375*2^30 */ 833 int32_t f7_38 = 38 * f7; /* 1.959375*2^30 */ 834 int32_t f8_19 = 19 * f8; /* 1.959375*2^30 */ 835 int32_t f9_38 = 38 * f9; /* 1.959375*2^30 */ 836 837 int64_t f0f0 = f0 * (int64_t) f0; 838 int64_t f0f1_2 = f0_2 * (int64_t) f1; 839 int64_t f0f2_2 = f0_2 * (int64_t) f2; 840 int64_t f0f3_2 = f0_2 * (int64_t) f3; 841 int64_t f0f4_2 = f0_2 * (int64_t) f4; 842 int64_t f0f5_2 = f0_2 * (int64_t) f5; 843 int64_t f0f6_2 = f0_2 * (int64_t) f6; 844 int64_t f0f7_2 = f0_2 * (int64_t) f7; 845 int64_t f0f8_2 = f0_2 * (int64_t) f8; 846 int64_t f0f9_2 = f0_2 * (int64_t) f9; 847 int64_t f1f1_2 = f1_2 * (int64_t) f1; 848 int64_t f1f2_2 = f1_2 * (int64_t) f2; 849 int64_t f1f3_4 = f1_2 * (int64_t) f3_2; 850 int64_t f1f4_2 = f1_2 * (int64_t) f4; 851 int64_t f1f5_4 = f1_2 * (int64_t) f5_2; 852 int64_t f1f6_2 = f1_2 * (int64_t) f6; 853 int64_t f1f7_4 = f1_2 * (int64_t) f7_2; 854 int64_t f1f8_2 = f1_2 * (int64_t) f8; 855 int64_t f1f9_76 = f1_2 * (int64_t) f9_38; 856 int64_t f2f2 = f2 * (int64_t) f2; 857 int64_t f2f3_2 = f2_2 * (int64_t) f3; 858 int64_t f2f4_2 = f2_2 * (int64_t) f4; 859 int64_t f2f5_2 = f2_2 * (int64_t) f5; 860 int64_t f2f6_2 = f2_2 * (int64_t) f6; 861 int64_t f2f7_2 = f2_2 * (int64_t) f7; 862 int64_t f2f8_38 = f2_2 * (int64_t) f8_19; 863 int64_t f2f9_38 = f2 * (int64_t) f9_38; 864 int64_t f3f3_2 = f3_2 * (int64_t) f3; 865 int64_t f3f4_2 = f3_2 * (int64_t) f4; 866 int64_t f3f5_4 = f3_2 * (int64_t) f5_2; 867 int64_t f3f6_2 = f3_2 * (int64_t) f6; 868 int64_t f3f7_76 = f3_2 * (int64_t) f7_38; 869 int64_t f3f8_38 = f3_2 * (int64_t) f8_19; 870 int64_t f3f9_76 = f3_2 * (int64_t) f9_38; 871 int64_t f4f4 = f4 * (int64_t) f4; 872 int64_t f4f5_2 = f4_2 * (int64_t) f5; 873 int64_t f4f6_38 = f4_2 * (int64_t) f6_19; 874 int64_t f4f7_38 = f4 * (int64_t) f7_38; 875 int64_t f4f8_38 = f4_2 * (int64_t) f8_19; 876 int64_t f4f9_38 = f4 * (int64_t) f9_38; 877 int64_t f5f5_38 = f5 * (int64_t) f5_38; 878 int64_t f5f6_38 = f5_2 * (int64_t) f6_19; 879 int64_t f5f7_76 = f5_2 * (int64_t) f7_38; 880 int64_t f5f8_38 = f5_2 * (int64_t) f8_19; 881 int64_t f5f9_76 = f5_2 * (int64_t) f9_38; 882 int64_t f6f6_19 = f6 * (int64_t) f6_19; 883 int64_t f6f7_38 = f6 * (int64_t) f7_38; 884 int64_t f6f8_38 = f6_2 * (int64_t) f8_19; 885 int64_t f6f9_38 = f6 * (int64_t) f9_38; 886 int64_t f7f7_38 = f7 * (int64_t) f7_38; 887 int64_t f7f8_38 = f7_2 * (int64_t) f8_19; 888 int64_t f7f9_76 = f7_2 * (int64_t) f9_38; 889 int64_t f8f8_19 = f8 * (int64_t) f8_19; 890 int64_t f8f9_38 = f8 * (int64_t) f9_38; 891 int64_t f9f9_38 = f9 * (int64_t) f9_38; 892 893 int64_t h0 = f0f0 + f1f9_76 + f2f8_38 + f3f7_76 + f4f6_38 + f5f5_38; 894 int64_t h1 = f0f1_2 + f2f9_38 + f3f8_38 + f4f7_38 + f5f6_38; 895 int64_t h2 = f0f2_2 + f1f1_2 + f3f9_76 + f4f8_38 + f5f7_76 + f6f6_19; 896 int64_t h3 = f0f3_2 + f1f2_2 + f4f9_38 + f5f8_38 + f6f7_38; 897 int64_t h4 = f0f4_2 + f1f3_4 + f2f2 + f5f9_76 + f6f8_38 + f7f7_38; 898 int64_t h5 = f0f5_2 + f1f4_2 + f2f3_2 + f6f9_38 + f7f8_38; 899 int64_t h6 = f0f6_2 + f1f5_4 + f2f4_2 + f3f3_2 + f7f9_76 + f8f8_19; 900 int64_t h7 = f0f7_2 + f1f6_2 + f2f5_2 + f3f4_2 + f8f9_38; 901 int64_t h8 = f0f8_2 + f1f7_4 + f2f6_2 + f3f5_4 + f4f4 + f9f9_38; 902 int64_t h9 = f0f9_2 + f1f8_2 + f2f7_2 + f3f6_2 + f4f5_2; 903 904 int64_t carry0; 905 int64_t carry1; 906 int64_t carry2; 907 int64_t carry3; 908 int64_t carry4; 909 int64_t carry5; 910 int64_t carry6; 911 int64_t carry7; 912 int64_t carry8; 913 int64_t carry9; 914 915 h0 += h0; 916 h1 += h1; 917 h2 += h2; 918 h3 += h3; 919 h4 += h4; 920 h5 += h5; 921 h6 += h6; 922 h7 += h7; 923 h8 += h8; 924 h9 += h9; 925 926 carry0 = (h0 + (int64_t)(1L << 25)) >> 26; 927 h1 += carry0; 928 h0 -= carry0 * ((uint64_t) 1L << 26); 929 carry4 = (h4 + (int64_t)(1L << 25)) >> 26; 930 h5 += carry4; 931 h4 -= carry4 * ((uint64_t) 1L << 26); 932 933 carry1 = (h1 + (int64_t)(1L << 24)) >> 25; 934 h2 += carry1; 935 h1 -= carry1 * ((uint64_t) 1L << 25); 936 carry5 = (h5 + (int64_t)(1L << 24)) >> 25; 937 h6 += carry5; 938 h5 -= carry5 * ((uint64_t) 1L << 25); 939 940 carry2 = (h2 + (int64_t)(1L << 25)) >> 26; 941 h3 += carry2; 942 h2 -= carry2 * ((uint64_t) 1L << 26); 943 carry6 = (h6 + (int64_t)(1L << 25)) >> 26; 944 h7 += carry6; 945 h6 -= carry6 * ((uint64_t) 1L << 26); 946 947 carry3 = (h3 + (int64_t)(1L << 24)) >> 25; 948 h4 += carry3; 949 h3 -= carry3 * ((uint64_t) 1L << 25); 950 carry7 = (h7 + (int64_t)(1L << 24)) >> 25; 951 h8 += carry7; 952 h7 -= carry7 * ((uint64_t) 1L << 25); 953 954 carry4 = (h4 + (int64_t)(1L << 25)) >> 26; 955 h5 += carry4; 956 h4 -= carry4 * ((uint64_t) 1L << 26); 957 carry8 = (h8 + (int64_t)(1L << 25)) >> 26; 958 h9 += carry8; 959 h8 -= carry8 * ((uint64_t) 1L << 26); 960 961 carry9 = (h9 + (int64_t)(1L << 24)) >> 25; 962 h0 += carry9 * 19; 963 h9 -= carry9 * ((uint64_t) 1L << 25); 964 965 carry0 = (h0 + (int64_t)(1L << 25)) >> 26; 966 h1 += carry0; 967 h0 -= carry0 * ((uint64_t) 1L << 26); 968 969 h[0] = (int32_t) h0; 970 h[1] = (int32_t) h1; 971 h[2] = (int32_t) h2; 972 h[3] = (int32_t) h3; 973 h[4] = (int32_t) h4; 974 h[5] = (int32_t) h5; 975 h[6] = (int32_t) h6; 976 h[7] = (int32_t) h7; 977 h[8] = (int32_t) h8; 978 h[9] = (int32_t) h9; 979 } 980 981 static void 982 fe25519_scalar_product(fe25519 h, const fe25519 f, uint32_t n) 983 { 984 int64_t sn = (int64_t) n; 985 int32_t f0 = f[0]; 986 int32_t f1 = f[1]; 987 int32_t f2 = f[2]; 988 int32_t f3 = f[3]; 989 int32_t f4 = f[4]; 990 int32_t f5 = f[5]; 991 int32_t f6 = f[6]; 992 int32_t f7 = f[7]; 993 int32_t f8 = f[8]; 994 int32_t f9 = f[9]; 995 int64_t h0 = f0 * sn; 996 int64_t h1 = f1 * sn; 997 int64_t h2 = f2 * sn; 998 int64_t h3 = f3 * sn; 999 int64_t h4 = f4 * sn; 1000 int64_t h5 = f5 * sn; 1001 int64_t h6 = f6 * sn; 1002 int64_t h7 = f7 * sn; 1003 int64_t h8 = f8 * sn; 1004 int64_t h9 = f9 * sn; 1005 int64_t carry0, carry1, carry2, carry3, carry4, carry5, carry6, carry7, 1006 carry8, carry9; 1007 1008 carry9 = (h9 + ((int64_t) 1 << 24)) >> 25; 1009 h0 += carry9 * 19; 1010 h9 -= carry9 * ((int64_t) 1 << 25); 1011 carry1 = (h1 + ((int64_t) 1 << 24)) >> 25; 1012 h2 += carry1; 1013 h1 -= carry1 * ((int64_t) 1 << 25); 1014 carry3 = (h3 + ((int64_t) 1 << 24)) >> 25; 1015 h4 += carry3; 1016 h3 -= carry3 * ((int64_t) 1 << 25); 1017 carry5 = (h5 + ((int64_t) 1 << 24)) >> 25; 1018 h6 += carry5; 1019 h5 -= carry5 * ((int64_t) 1 << 25); 1020 carry7 = (h7 + ((int64_t) 1 << 24)) >> 25; 1021 h8 += carry7; 1022 h7 -= carry7 * ((int64_t) 1 << 25); 1023 1024 carry0 = (h0 + ((int64_t) 1 << 25)) >> 26; 1025 h1 += carry0; 1026 h0 -= carry0 * ((int64_t) 1 << 26); 1027 carry2 = (h2 + ((int64_t) 1 << 25)) >> 26; 1028 h3 += carry2; 1029 h2 -= carry2 * ((int64_t) 1 << 26); 1030 carry4 = (h4 + ((int64_t) 1 << 25)) >> 26; 1031 h5 += carry4; 1032 h4 -= carry4 * ((int64_t) 1 << 26); 1033 carry6 = (h6 + ((int64_t) 1 << 25)) >> 26; 1034 h7 += carry6; 1035 h6 -= carry6 * ((int64_t) 1 << 26); 1036 carry8 = (h8 + ((int64_t) 1 << 25)) >> 26; 1037 h9 += carry8; 1038 h8 -= carry8 * ((int64_t) 1 << 26); 1039 1040 h[0] = (int32_t) h0; 1041 h[1] = (int32_t) h1; 1042 h[2] = (int32_t) h2; 1043 h[3] = (int32_t) h3; 1044 h[4] = (int32_t) h4; 1045 h[5] = (int32_t) h5; 1046 h[6] = (int32_t) h6; 1047 h[7] = (int32_t) h7; 1048 h[8] = (int32_t) h8; 1049 h[9] = (int32_t) h9; 1050 } 1051