| 2313 | // U[N] --- multiplicative inverse of M mod 2**(WORD_BITS*N) |
| 2314 | |
| 2315 | void MontgomeryReduce(word *R, word *T, word *X, const word *M, const word *U, size_t N) |
| 2316 | { |
| 2317 | #if 1 |
| 2318 | MultiplyBottom(R, T, X, U, N); |
| 2319 | MultiplyTop(T, T+N, X, R, M, N); |
| 2320 | word borrow = Subtract(T, X+N, T, N); |
| 2321 | // defend against timing attack by doing this Add even when not needed |
| 2322 | word carry = Add(T+N, T, M, N); |
| 2323 | assert(carry | !borrow); |
| 2324 | CopyWords(R, T + ((0-borrow) & N), N); |
| 2325 | #elif 0 |
| 2326 | const word u = 0-U[0]; |
| 2327 | Declare2Words(p) |
| 2328 | for (size_t i=0; i<N; i++) |
| 2329 | { |
| 2330 | const word t = u * X[i]; |
| 2331 | word c = 0; |
| 2332 | for (size_t j=0; j<N; j+=2) |
| 2333 | { |
| 2334 | MultiplyWords(p, t, M[j]); |
| 2335 | Acc2WordsBy1(p, X[i+j]); |
| 2336 | Acc2WordsBy1(p, c); |
| 2337 | X[i+j] = LowWord(p); |
| 2338 | c = HighWord(p); |
| 2339 | MultiplyWords(p, t, M[j+1]); |
| 2340 | Acc2WordsBy1(p, X[i+j+1]); |
| 2341 | Acc2WordsBy1(p, c); |
| 2342 | X[i+j+1] = LowWord(p); |
| 2343 | c = HighWord(p); |
| 2344 | } |
| 2345 | |
| 2346 | if (Increment(X+N+i, N-i, c)) |
| 2347 | while (!Subtract(X+N, X+N, M, N)) {} |
| 2348 | } |
| 2349 | |
| 2350 | memcpy(R, X+N, N*WORD_SIZE); |
| 2351 | #else |
| 2352 | __m64 u = _mm_cvtsi32_si64(0-U[0]), p; |
| 2353 | for (size_t i=0; i<N; i++) |
| 2354 | { |
| 2355 | __m64 t = _mm_cvtsi32_si64(X[i]); |
| 2356 | t = _mm_mul_su32(t, u); |
| 2357 | __m64 c = _mm_setzero_si64(); |
| 2358 | for (size_t j=0; j<N; j+=2) |
| 2359 | { |
| 2360 | p = _mm_mul_su32(t, _mm_cvtsi32_si64(M[j])); |
| 2361 | p = _mm_add_si64(p, _mm_cvtsi32_si64(X[i+j])); |
| 2362 | c = _mm_add_si64(c, p); |
| 2363 | X[i+j] = _mm_cvtsi64_si32(c); |
| 2364 | c = _mm_srli_si64(c, 32); |
| 2365 | p = _mm_mul_su32(t, _mm_cvtsi32_si64(M[j+1])); |
| 2366 | p = _mm_add_si64(p, _mm_cvtsi32_si64(X[i+j+1])); |
| 2367 | c = _mm_add_si64(c, p); |
| 2368 | X[i+j+1] = _mm_cvtsi64_si32(c); |
| 2369 | c = _mm_srli_si64(c, 32); |
| 2370 | } |
| 2371 | |
| 2372 | if (Increment(X+N+i, N-i, _mm_cvtsi64_si32(c))) |
no test coverage detected