7 #ifndef SECP256K1_SCALAR_REPR_IMPL_H
8 #define SECP256K1_SCALAR_REPR_IMPL_H
11 #define SECP256K1_N_0 ((uint32_t)0xD0364141UL)
12 #define SECP256K1_N_1 ((uint32_t)0xBFD25E8CUL)
13 #define SECP256K1_N_2 ((uint32_t)0xAF48A03BUL)
14 #define SECP256K1_N_3 ((uint32_t)0xBAAEDCE6UL)
15 #define SECP256K1_N_4 ((uint32_t)0xFFFFFFFEUL)
16 #define SECP256K1_N_5 ((uint32_t)0xFFFFFFFFUL)
17 #define SECP256K1_N_6 ((uint32_t)0xFFFFFFFFUL)
18 #define SECP256K1_N_7 ((uint32_t)0xFFFFFFFFUL)
21 #define SECP256K1_N_C_0 (~SECP256K1_N_0 + 1)
22 #define SECP256K1_N_C_1 (~SECP256K1_N_1)
23 #define SECP256K1_N_C_2 (~SECP256K1_N_2)
24 #define SECP256K1_N_C_3 (~SECP256K1_N_3)
25 #define SECP256K1_N_C_4 (1)
28 #define SECP256K1_N_H_0 ((uint32_t)0x681B20A0UL)
29 #define SECP256K1_N_H_1 ((uint32_t)0xDFE92F46UL)
30 #define SECP256K1_N_H_2 ((uint32_t)0x57A4501DUL)
31 #define SECP256K1_N_H_3 ((uint32_t)0x5D576E73UL)
32 #define SECP256K1_N_H_4 ((uint32_t)0xFFFFFFFFUL)
33 #define SECP256K1_N_H_5 ((uint32_t)0xFFFFFFFFUL)
34 #define SECP256K1_N_H_6 ((uint32_t)0xFFFFFFFFUL)
35 #define SECP256K1_N_H_7 ((uint32_t)0x7FFFFFFFUL)
61 return (a->
d[offset >> 5] >> (offset & 0x1F)) & ((1 <<
count) - 1);
67 if ((offset +
count - 1) >> 5 == offset >> 5) {
71 return ((a->
d[offset >> 5] >> (offset & 0x1F)) | (a->
d[(offset >> 5) + 1] << (32 - (offset & 0x1F)))) & ((((uint32_t)1) <<
count) - 1);
97 r->
d[0] = t & 0xFFFFFFFFUL; t >>= 32;
99 r->
d[1] = t & 0xFFFFFFFFUL; t >>= 32;
101 r->
d[2] = t & 0xFFFFFFFFUL; t >>= 32;
103 r->
d[3] = t & 0xFFFFFFFFUL; t >>= 32;
105 r->
d[4] = t & 0xFFFFFFFFUL; t >>= 32;
106 t += (uint64_t)r->
d[5];
107 r->
d[5] = t & 0xFFFFFFFFUL; t >>= 32;
108 t += (uint64_t)r->
d[6];
109 r->
d[6] = t & 0xFFFFFFFFUL; t >>= 32;
110 t += (uint64_t)r->
d[7];
111 r->
d[7] = t & 0xFFFFFFFFUL;
117 uint64_t t = (uint64_t)a->
d[0] + b->
d[0];
118 r->
d[0] = t & 0xFFFFFFFFULL; t >>= 32;
119 t += (uint64_t)a->
d[1] + b->
d[1];
120 r->
d[1] = t & 0xFFFFFFFFULL; t >>= 32;
121 t += (uint64_t)a->
d[2] + b->
d[2];
122 r->
d[2] = t & 0xFFFFFFFFULL; t >>= 32;
123 t += (uint64_t)a->
d[3] + b->
d[3];
124 r->
d[3] = t & 0xFFFFFFFFULL; t >>= 32;
125 t += (uint64_t)a->
d[4] + b->
d[4];
126 r->
d[4] = t & 0xFFFFFFFFULL; t >>= 32;
127 t += (uint64_t)a->
d[5] + b->
d[5];
128 r->
d[5] = t & 0xFFFFFFFFULL; t >>= 32;
129 t += (uint64_t)a->
d[6] + b->
d[6];
130 r->
d[6] = t & 0xFFFFFFFFULL; t >>= 32;
131 t += (uint64_t)a->
d[7] + b->
d[7];
132 r->
d[7] = t & 0xFFFFFFFFULL; t >>= 32;
142 bit += ((uint32_t) flag - 1) & 0x100;
143 t = (uint64_t)r->
d[0] + (((uint32_t)((bit >> 5) == 0)) << (bit & 0x1F));
144 r->
d[0] = t & 0xFFFFFFFFULL; t >>= 32;
145 t += (uint64_t)r->
d[1] + (((uint32_t)((bit >> 5) == 1)) << (bit & 0x1F));
146 r->
d[1] = t & 0xFFFFFFFFULL; t >>= 32;
147 t += (uint64_t)r->
d[2] + (((uint32_t)((bit >> 5) == 2)) << (bit & 0x1F));
148 r->
d[2] = t & 0xFFFFFFFFULL; t >>= 32;
149 t += (uint64_t)r->
d[3] + (((uint32_t)((bit >> 5) == 3)) << (bit & 0x1F));
150 r->
d[3] = t & 0xFFFFFFFFULL; t >>= 32;
151 t += (uint64_t)r->
d[4] + (((uint32_t)((bit >> 5) == 4)) << (bit & 0x1F));
152 r->
d[4] = t & 0xFFFFFFFFULL; t >>= 32;
153 t += (uint64_t)r->
d[5] + (((uint32_t)((bit >> 5) == 5)) << (bit & 0x1F));
154 r->
d[5] = t & 0xFFFFFFFFULL; t >>= 32;
155 t += (uint64_t)r->
d[6] + (((uint32_t)((bit >> 5) == 6)) << (bit & 0x1F));
156 r->
d[6] = t & 0xFFFFFFFFULL; t >>= 32;
157 t += (uint64_t)r->
d[7] + (((uint32_t)((bit >> 5) == 7)) << (bit & 0x1F));
158 r->
d[7] = t & 0xFFFFFFFFULL;
167 r->
d[0] = (uint32_t)b32[31] | (uint32_t)b32[30] << 8 | (uint32_t)b32[29] << 16 | (uint32_t)b32[28] << 24;
168 r->
d[1] = (uint32_t)b32[27] | (uint32_t)b32[26] << 8 | (uint32_t)b32[25] << 16 | (uint32_t)b32[24] << 24;
169 r->
d[2] = (uint32_t)b32[23] | (uint32_t)b32[22] << 8 | (uint32_t)b32[21] << 16 | (uint32_t)b32[20] << 24;
170 r->
d[3] = (uint32_t)b32[19] | (uint32_t)b32[18] << 8 | (uint32_t)b32[17] << 16 | (uint32_t)b32[16] << 24;
171 r->
d[4] = (uint32_t)b32[15] | (uint32_t)b32[14] << 8 | (uint32_t)b32[13] << 16 | (uint32_t)b32[12] << 24;
172 r->
d[5] = (uint32_t)b32[11] | (uint32_t)b32[10] << 8 | (uint32_t)b32[9] << 16 | (uint32_t)b32[8] << 24;
173 r->
d[6] = (uint32_t)b32[7] | (uint32_t)b32[6] << 8 | (uint32_t)b32[5] << 16 | (uint32_t)b32[4] << 24;
174 r->
d[7] = (uint32_t)b32[3] | (uint32_t)b32[2] << 8 | (uint32_t)b32[1] << 16 | (uint32_t)b32[0] << 24;
182 bin[0] = a->
d[7] >> 24; bin[1] = a->
d[7] >> 16; bin[2] = a->
d[7] >> 8; bin[3] = a->
d[7];
183 bin[4] = a->
d[6] >> 24; bin[5] = a->
d[6] >> 16; bin[6] = a->
d[6] >> 8; bin[7] = a->
d[6];
184 bin[8] = a->
d[5] >> 24; bin[9] = a->
d[5] >> 16; bin[10] = a->
d[5] >> 8; bin[11] = a->
d[5];
185 bin[12] = a->
d[4] >> 24; bin[13] = a->
d[4] >> 16; bin[14] = a->
d[4] >> 8; bin[15] = a->
d[4];
186 bin[16] = a->
d[3] >> 24; bin[17] = a->
d[3] >> 16; bin[18] = a->
d[3] >> 8; bin[19] = a->
d[3];
187 bin[20] = a->
d[2] >> 24; bin[21] = a->
d[2] >> 16; bin[22] = a->
d[2] >> 8; bin[23] = a->
d[2];
188 bin[24] = a->
d[1] >> 24; bin[25] = a->
d[1] >> 16; bin[26] = a->
d[1] >> 8; bin[27] = a->
d[1];
189 bin[28] = a->
d[0] >> 24; bin[29] = a->
d[0] >> 16; bin[30] = a->
d[0] >> 8; bin[31] = a->
d[0];
193 return (a->
d[0] | a->
d[1] | a->
d[2] | a->
d[3] | a->
d[4] | a->
d[5] | a->
d[6] | a->
d[7]) == 0;
199 r->
d[0] = t & nonzero; t >>= 32;
201 r->
d[1] = t & nonzero; t >>= 32;
203 r->
d[2] = t & nonzero; t >>= 32;
205 r->
d[3] = t & nonzero; t >>= 32;
207 r->
d[4] = t & nonzero; t >>= 32;
209 r->
d[5] = t & nonzero; t >>= 32;
211 r->
d[6] = t & nonzero; t >>= 32;
213 r->
d[7] = t & nonzero;
217 return ((a->
d[0] ^ 1) | a->
d[1] | a->
d[2] | a->
d[3] | a->
d[4] | a->
d[5] | a->
d[6] | a->
d[7]) == 0;
241 uint32_t mask = !flag - 1;
243 uint64_t t = (uint64_t)(r->
d[0] ^ mask) + ((
SECP256K1_N_0 + 1) & mask);
244 r->
d[0] = t & nonzero; t >>= 32;
246 r->
d[1] = t & nonzero; t >>= 32;
248 r->
d[2] = t & nonzero; t >>= 32;
250 r->
d[3] = t & nonzero; t >>= 32;
252 r->
d[4] = t & nonzero; t >>= 32;
254 r->
d[5] = t & nonzero; t >>= 32;
256 r->
d[6] = t & nonzero; t >>= 32;
258 r->
d[7] = t & nonzero;
259 return 2 * (mask == 0) - 1;
266 #define muladd(a,b) { \
269 uint64_t t = (uint64_t)a * b; \
277 VERIFY_CHECK((c1 >= th) || (c2 != 0)); \
281 #define muladd_fast(a,b) { \
284 uint64_t t = (uint64_t)a * b; \
291 VERIFY_CHECK(c1 >= th); \
295 #define muladd2(a,b) { \
296 uint32_t tl, th, th2, tl2; \
298 uint64_t t = (uint64_t)a * b; \
304 VERIFY_CHECK((th2 >= th) || (c2 != 0)); \
309 c2 += (c0 < tl2) & (th2 == 0); \
310 VERIFY_CHECK((c0 >= tl2) || (th2 != 0) || (c2 != 0)); \
313 VERIFY_CHECK((c1 >= th2) || (c2 != 0)); \
317 #define sumadd(a) { \
326 #define sumadd_fast(a) { \
329 VERIFY_CHECK((c1 != 0) | (c0 >= (a))); \
330 VERIFY_CHECK(c2 == 0); \
334 #define extract(n) { \
342 #define extract_fast(n) { \
346 VERIFY_CHECK(c2 == 0); \
351 uint32_t n0 = l[8], n1 = l[9], n2 = l[10], n3 = l[11], n4 = l[12], n5 = l[13], n6 = l[14], n7 = l[15];
352 uint32_t m0, m1, m2, m3, m4, m5, m6, m7, m8, m9, m10, m11, m12;
353 uint32_t p0, p1, p2, p3, p4, p5, p6, p7, p8;
360 c0 = l[0]; c1 = 0; c2 = 0;
425 c0 = m0; c1 = 0; c2 = 0;
471 r->
d[0] = c & 0xFFFFFFFFUL; c >>= 32;
473 r->
d[1] = c & 0xFFFFFFFFUL; c >>= 32;
475 r->
d[2] = c & 0xFFFFFFFFUL; c >>= 32;
477 r->
d[3] = c & 0xFFFFFFFFUL; c >>= 32;
478 c += p4 + (uint64_t)p8;
479 r->
d[4] = c & 0xFFFFFFFFUL; c >>= 32;
481 r->
d[5] = c & 0xFFFFFFFFUL; c >>= 32;
483 r->
d[6] = c & 0xFFFFFFFFUL; c >>= 32;
485 r->
d[7] = c & 0xFFFFFFFFUL; c >>= 32;
493 uint32_t c0 = 0, c1 = 0, c2 = 0;
581 uint32_t c0 = 0, c1 = 0, c2 = 0;
657 ret = r->
d[0] & ((1 << n) - 1);
658 r->
d[0] = (r->
d[0] >> n) + (r->
d[1] << (32 - n));
659 r->
d[1] = (r->
d[1] >> n) + (r->
d[2] << (32 - n));
660 r->
d[2] = (r->
d[2] >> n) + (r->
d[3] << (32 - n));
661 r->
d[3] = (r->
d[3] >> n) + (r->
d[4] << (32 - n));
662 r->
d[4] = (r->
d[4] >> n) + (r->
d[5] << (32 - n));
663 r->
d[5] = (r->
d[5] >> n) + (r->
d[6] << (32 - n));
664 r->
d[6] = (r->
d[6] >> n) + (r->
d[7] << (32 - n));
665 r->
d[7] = (r->
d[7] >> n);
695 return ((a->
d[0] ^ b->
d[0]) | (a->
d[1] ^ b->
d[1]) | (a->
d[2] ^ b->
d[2]) | (a->
d[3] ^ b->
d[3]) | (a->
d[4] ^ b->
d[4]) | (a->
d[5] ^ b->
d[5]) | (a->
d[6] ^ b->
d[6]) | (a->
d[7] ^ b->
d[7])) == 0;
700 unsigned int shiftlimbs;
701 unsigned int shiftlow;
702 unsigned int shifthigh;
705 shiftlimbs = shift >> 5;
706 shiftlow = shift & 0x1F;
707 shifthigh = 32 - shiftlow;
708 r->
d[0] = shift < 512 ? (l[0 + shiftlimbs] >> shiftlow | (shift < 480 && shiftlow ? (l[1 + shiftlimbs] << shifthigh) : 0)) : 0;
709 r->
d[1] = shift < 480 ? (l[1 + shiftlimbs] >> shiftlow | (shift < 448 && shiftlow ? (l[2 + shiftlimbs] << shifthigh) : 0)) : 0;
710 r->
d[2] = shift < 448 ? (l[2 + shiftlimbs] >> shiftlow | (shift < 416 && shiftlow ? (l[3 + shiftlimbs] << shifthigh) : 0)) : 0;
711 r->
d[3] = shift < 416 ? (l[3 + shiftlimbs] >> shiftlow | (shift < 384 && shiftlow ? (l[4 + shiftlimbs] << shifthigh) : 0)) : 0;
712 r->
d[4] = shift < 384 ? (l[4 + shiftlimbs] >> shiftlow | (shift < 352 && shiftlow ? (l[5 + shiftlimbs] << shifthigh) : 0)) : 0;
713 r->
d[5] = shift < 352 ? (l[5 + shiftlimbs] >> shiftlow | (shift < 320 && shiftlow ? (l[6 + shiftlimbs] << shifthigh) : 0)) : 0;
714 r->
d[6] = shift < 320 ? (l[6 + shiftlimbs] >> shiftlow | (shift < 288 && shiftlow ? (l[7 + shiftlimbs] << shifthigh) : 0)) : 0;
715 r->
d[7] = shift < 288 ? (l[7 + shiftlimbs] >> shiftlow) : 0;
720 uint32_t mask0, mask1;
722 mask0 = flag + ~((uint32_t)0);
724 r->
d[0] = (r->
d[0] & mask0) | (a->
d[0] & mask1);
725 r->
d[1] = (r->
d[1] & mask0) | (a->
d[1] & mask1);
726 r->
d[2] = (r->
d[2] & mask0) | (a->
d[2] & mask1);
727 r->
d[3] = (r->
d[3] & mask0) | (a->
d[3] & mask1);
728 r->
d[4] = (r->
d[4] & mask0) | (a->
d[4] & mask1);
729 r->
d[5] = (r->
d[5] & mask0) | (a->
d[5] & mask1);
730 r->
d[6] = (r->
d[6] & mask0) | (a->
d[6] & mask1);
731 r->
d[7] = (r->
d[7] & mask0) | (a->
d[7] & mask1);