compute out = (a*b) mod m; if b=NULL, treat b=1; if m=NULL, treat m=infinity. * * Out is a 512-bit number (represented as 32 uint16_t's in LE order). The other * arguments are 256-bit numbers (represented as 16 uint16_t's in LE order). */
| 920 | * Out is a 512-bit number (represented as 32 uint16_t's in LE order). The other |
| 921 | * arguments are 256-bit numbers (represented as 16 uint16_t's in LE order). */ |
| 922 | static void mulmod256(uint16_t* out, const uint16_t* a, const uint16_t* b, const uint16_t* m) { |
| 923 | uint16_t mul[32]; |
| 924 | uint64_t c = 0; |
| 925 | int i, j; |
| 926 | int m_bitlen = 0; |
| 927 | int mul_bitlen = 0; |
| 928 | |
| 929 | if (b != NULL) { |
| 930 | /* Compute the product of a and b, and put it in mul. */ |
| 931 | for (i = 0; i < 32; ++i) { |
| 932 | for (j = i <= 15 ? 0 : i - 15; j <= i && j <= 15; j++) { |
| 933 | c += (uint64_t)a[j] * b[i - j]; |
| 934 | } |
| 935 | mul[i] = c & 0xFFFF; |
| 936 | c >>= 16; |
| 937 | } |
| 938 | CHECK(c == 0); |
| 939 | |
| 940 | /* compute the highest set bit in mul */ |
| 941 | for (i = 511; i >= 0; --i) { |
| 942 | if ((mul[i >> 4] >> (i & 15)) & 1) { |
| 943 | mul_bitlen = i; |
| 944 | break; |
| 945 | } |
| 946 | } |
| 947 | } else { |
| 948 | /* if b==NULL, set mul=a. */ |
| 949 | memcpy(mul, a, 32); |
| 950 | memset(mul + 16, 0, 32); |
| 951 | /* compute the highest set bit in mul */ |
| 952 | for (i = 255; i >= 0; --i) { |
| 953 | if ((mul[i >> 4] >> (i & 15)) & 1) { |
| 954 | mul_bitlen = i; |
| 955 | break; |
| 956 | } |
| 957 | } |
| 958 | } |
| 959 | |
| 960 | if (m) { |
| 961 | /* Compute the highest set bit in m. */ |
| 962 | for (i = 255; i >= 0; --i) { |
| 963 | if ((m[i >> 4] >> (i & 15)) & 1) { |
| 964 | m_bitlen = i; |
| 965 | break; |
| 966 | } |
| 967 | } |
| 968 | |
| 969 | /* Try do mul -= m<<i, for i going down to 0, whenever the result is not negative */ |
| 970 | for (i = mul_bitlen - m_bitlen; i >= 0; --i) { |
| 971 | uint16_t mul2[32]; |
| 972 | int64_t cs; |
| 973 | |
| 974 | /* Compute mul2 = mul - m<<i. */ |
| 975 | cs = 0; /* accumulator */ |
| 976 | for (j = 0; j < 32; ++j) { /* j loops over the output limbs in mul2. */ |
| 977 | /* Compute sub: the 16 bits in m that will be subtracted from mul2[j]. */ |
| 978 | uint16_t sub = 0; |
| 979 | int p; |
no outgoing calls
no test coverage detected