src/nt/mod/montgomery/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../../util/alias/num/lib.hpp" | ||
| 4 | |||
| 5 | namespace tifa_libs { | ||
| 6 | |||
| 7 | template <u32 MOD> | ||
| 8 | struct montgomery { | ||
| 9 | static CEXP u32 MOD2 = MOD << 1, R2 = -(u64)(MOD) % MOD, R = [] { | ||
| 10 | u32 iv = MOD * (2 - MOD * MOD); | ||
| 11 | iv *= 2 - MOD * iv, iv *= 2 - MOD * iv; | ||
| 12 | return iv * (MOD * iv - 2); | ||
| 13 | }(); | ||
| 14 | static_assert(MOD & 1); | ||
| 15 | static_assert(-R * MOD == 1); | ||
| 16 | static_assert((MOD >> 30) == 0); | ||
| 17 | static_assert(MOD != 1); | ||
| 18 | 797574406432 | static CEXP u32 reduce(u64 x) NE { return u32((x + u64((u32)x * R) * MOD) >> 32); } | |
| 19 | 23232383239 | static CEXP u32 norm(u32 x) NE { return x - (MOD & -((MOD - 1 - x) >> 31)); } | |
| 20 | }; | ||
| 21 | template <> // dynamic | ||
| 22 | struct montgomery<0> { | ||
| 23 | u32 R, R2, MOD, MOD_ODD, OFFSET, MASK; | ||
| 24 | CEXP montgomery() NE = default; | ||
| 25 | CEXPE montgomery(u32 m) NE { reset(m); } | ||
| 26 | 5380 | CEXP void reset(u32 m) NE { | |
| 27 |
4/6✓ Branch 0 taken 5380 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 5380 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 83 times.
✓ Branch 6 taken 5380 times.
|
5463 | for (assert(!(m == 1 || m >> 31)), MOD = MOD_ODD = m, OFFSET = 0; (MOD_ODD & 1) == 0; ++OFFSET, MOD_ODD /= 2); |
| 28 | 5380 | MASK = (1_u32 << OFFSET) - 1_u32; | |
| 29 | 5380 | u32 iv = MOD_ODD * (2 - MOD_ODD * MOD_ODD); | |
| 30 | 5380 | iv *= 2 - MOD_ODD * iv, iv *= 2 - MOD_ODD * iv, R = iv * (MOD_ODD * iv - 2), R2 = u32(-u64(MOD_ODD) % MOD_ODD); | |
| 31 | 5380 | } | |
| 32 | 9136 | ND CEXP u32 norm(i32 x) CNE { return u32(x + (-(x < 0) & (i32)MOD)); } | |
| 33 | 150736400745 | ND CEXP u32 reduce(u64 x) CNE { | |
| 34 | 150736400745 | cu32 t = u32((x + u64((u32)x * R) * MOD_ODD) >> 32); | |
| 35 | 150736400745 | return t - (MOD_ODD & -((MOD_ODD - 1 - t) >> 31)); | |
| 36 | } | ||
| 37 |
2/2✓ Branch 0 taken 46704484002 times.
✓ Branch 1 taken 16581821 times.
|
46721065823 | ND CEXP u32 tsf(u32 x) CNE { retif_((!OFFSET) [[likely]], reduce(u64(x) * R2), reduce(u64(x % MOD_ODD) * R2) << OFFSET | (x & MASK)); } |
| 38 | }; | ||
| 39 | |||
| 40 | } // namespace tifa_libs | ||
| 41 |