BSHA3  0.17.99
P2P Blockchain, based on Bitcoin
field_5x52_int128_impl.h
Go to the documentation of this file.
1 /**********************************************************************
2  * Copyright (c) 2013, 2014 Pieter Wuille *
3  * Distributed under the MIT software license, see the accompanying *
4  * file COPYING or http://www.opensource.org/licenses/mit-license.php.*
5  **********************************************************************/
6 
7 #ifndef SECP256K1_FIELD_INNER5X52_IMPL_H
8 #define SECP256K1_FIELD_INNER5X52_IMPL_H
9 
10 #include <stdint.h>
11 
12 #ifdef VERIFY
13 #define VERIFY_BITS(x, n) VERIFY_CHECK(((x) >> (n)) == 0)
14 #else
15 #define VERIFY_BITS(x, n) do { } while(0)
16 #endif
17 
18 SECP256K1_INLINE static void secp256k1_fe_mul_inner(uint64_t *r, const uint64_t *a, const uint64_t * SECP256K1_RESTRICT b) {
19  uint128_t c, d;
20  uint64_t t3, t4, tx, u0;
21  uint64_t a0 = a[0], a1 = a[1], a2 = a[2], a3 = a[3], a4 = a[4];
22  const uint64_t M = 0xFFFFFFFFFFFFFULL, R = 0x1000003D10ULL;
23 
24  VERIFY_BITS(a[0], 56);
25  VERIFY_BITS(a[1], 56);
26  VERIFY_BITS(a[2], 56);
27  VERIFY_BITS(a[3], 56);
28  VERIFY_BITS(a[4], 52);
29  VERIFY_BITS(b[0], 56);
30  VERIFY_BITS(b[1], 56);
31  VERIFY_BITS(b[2], 56);
32  VERIFY_BITS(b[3], 56);
33  VERIFY_BITS(b[4], 52);
34  VERIFY_CHECK(r != b);
35 
36  /* [... a b c] is a shorthand for ... + a<<104 + b<<52 + c<<0 mod n.
37  * px is a shorthand for sum(a[i]*b[x-i], i=0..x).
38  * Note that [x 0 0 0 0 0] = [x*R].
39  */
40 
41  d = (uint128_t)a0 * b[3]
42  + (uint128_t)a1 * b[2]
43  + (uint128_t)a2 * b[1]
44  + (uint128_t)a3 * b[0];
45  VERIFY_BITS(d, 114);
46  /* [d 0 0 0] = [p3 0 0 0] */
47  c = (uint128_t)a4 * b[4];
48  VERIFY_BITS(c, 112);
49  /* [c 0 0 0 0 d 0 0 0] = [p8 0 0 0 0 p3 0 0 0] */
50  d += (c & M) * R; c >>= 52;
51  VERIFY_BITS(d, 115);
52  VERIFY_BITS(c, 60);
53  /* [c 0 0 0 0 0 d 0 0 0] = [p8 0 0 0 0 p3 0 0 0] */
54  t3 = d & M; d >>= 52;
55  VERIFY_BITS(t3, 52);
56  VERIFY_BITS(d, 63);
57  /* [c 0 0 0 0 d t3 0 0 0] = [p8 0 0 0 0 p3 0 0 0] */
58 
59  d += (uint128_t)a0 * b[4]
60  + (uint128_t)a1 * b[3]
61  + (uint128_t)a2 * b[2]
62  + (uint128_t)a3 * b[1]
63  + (uint128_t)a4 * b[0];
64  VERIFY_BITS(d, 115);
65  /* [c 0 0 0 0 d t3 0 0 0] = [p8 0 0 0 p4 p3 0 0 0] */
66  d += c * R;
67  VERIFY_BITS(d, 116);
68  /* [d t3 0 0 0] = [p8 0 0 0 p4 p3 0 0 0] */
69  t4 = d & M; d >>= 52;
70  VERIFY_BITS(t4, 52);
71  VERIFY_BITS(d, 64);
72  /* [d t4 t3 0 0 0] = [p8 0 0 0 p4 p3 0 0 0] */
73  tx = (t4 >> 48); t4 &= (M >> 4);
74  VERIFY_BITS(tx, 4);
75  VERIFY_BITS(t4, 48);
76  /* [d t4+(tx<<48) t3 0 0 0] = [p8 0 0 0 p4 p3 0 0 0] */
77 
78  c = (uint128_t)a0 * b[0];
79  VERIFY_BITS(c, 112);
80  /* [d t4+(tx<<48) t3 0 0 c] = [p8 0 0 0 p4 p3 0 0 p0] */
81  d += (uint128_t)a1 * b[4]
82  + (uint128_t)a2 * b[3]
83  + (uint128_t)a3 * b[2]
84  + (uint128_t)a4 * b[1];
85  VERIFY_BITS(d, 115);
86  /* [d t4+(tx<<48) t3 0 0 c] = [p8 0 0 p5 p4 p3 0 0 p0] */
87  u0 = d & M; d >>= 52;
88  VERIFY_BITS(u0, 52);
89  VERIFY_BITS(d, 63);
90  /* [d u0 t4+(tx<<48) t3 0 0 c] = [p8 0 0 p5 p4 p3 0 0 p0] */
91  /* [d 0 t4+(tx<<48)+(u0<<52) t3 0 0 c] = [p8 0 0 p5 p4 p3 0 0 p0] */
92  u0 = (u0 << 4) | tx;
93  VERIFY_BITS(u0, 56);
94  /* [d 0 t4+(u0<<48) t3 0 0 c] = [p8 0 0 p5 p4 p3 0 0 p0] */
95  c += (uint128_t)u0 * (R >> 4);
96  VERIFY_BITS(c, 115);
97  /* [d 0 t4 t3 0 0 c] = [p8 0 0 p5 p4 p3 0 0 p0] */
98  r[0] = c & M; c >>= 52;
99  VERIFY_BITS(r[0], 52);
100  VERIFY_BITS(c, 61);
101  /* [d 0 t4 t3 0 c r0] = [p8 0 0 p5 p4 p3 0 0 p0] */
102 
103  c += (uint128_t)a0 * b[1]
104  + (uint128_t)a1 * b[0];
105  VERIFY_BITS(c, 114);
106  /* [d 0 t4 t3 0 c r0] = [p8 0 0 p5 p4 p3 0 p1 p0] */
107  d += (uint128_t)a2 * b[4]
108  + (uint128_t)a3 * b[3]
109  + (uint128_t)a4 * b[2];
110  VERIFY_BITS(d, 114);
111  /* [d 0 t4 t3 0 c r0] = [p8 0 p6 p5 p4 p3 0 p1 p0] */
112  c += (d & M) * R; d >>= 52;
113  VERIFY_BITS(c, 115);
114  VERIFY_BITS(d, 62);
115  /* [d 0 0 t4 t3 0 c r0] = [p8 0 p6 p5 p4 p3 0 p1 p0] */
116  r[1] = c & M; c >>= 52;
117  VERIFY_BITS(r[1], 52);
118  VERIFY_BITS(c, 63);
119  /* [d 0 0 t4 t3 c r1 r0] = [p8 0 p6 p5 p4 p3 0 p1 p0] */
120 
121  c += (uint128_t)a0 * b[2]
122  + (uint128_t)a1 * b[1]
123  + (uint128_t)a2 * b[0];
124  VERIFY_BITS(c, 114);
125  /* [d 0 0 t4 t3 c r1 r0] = [p8 0 p6 p5 p4 p3 p2 p1 p0] */
126  d += (uint128_t)a3 * b[4]
127  + (uint128_t)a4 * b[3];
128  VERIFY_BITS(d, 114);
129  /* [d 0 0 t4 t3 c t1 r0] = [p8 p7 p6 p5 p4 p3 p2 p1 p0] */
130  c += (d & M) * R; d >>= 52;
131  VERIFY_BITS(c, 115);
132  VERIFY_BITS(d, 62);
133  /* [d 0 0 0 t4 t3 c r1 r0] = [p8 p7 p6 p5 p4 p3 p2 p1 p0] */
134 
135  /* [d 0 0 0 t4 t3 c r1 r0] = [p8 p7 p6 p5 p4 p3 p2 p1 p0] */
136  r[2] = c & M; c >>= 52;
137  VERIFY_BITS(r[2], 52);
138  VERIFY_BITS(c, 63);
139  /* [d 0 0 0 t4 t3+c r2 r1 r0] = [p8 p7 p6 p5 p4 p3 p2 p1 p0] */
140  c += d * R + t3;
141  VERIFY_BITS(c, 100);
142  /* [t4 c r2 r1 r0] = [p8 p7 p6 p5 p4 p3 p2 p1 p0] */
143  r[3] = c & M; c >>= 52;
144  VERIFY_BITS(r[3], 52);
145  VERIFY_BITS(c, 48);
146  /* [t4+c r3 r2 r1 r0] = [p8 p7 p6 p5 p4 p3 p2 p1 p0] */
147  c += t4;
148  VERIFY_BITS(c, 49);
149  /* [c r3 r2 r1 r0] = [p8 p7 p6 p5 p4 p3 p2 p1 p0] */
150  r[4] = c;
151  VERIFY_BITS(r[4], 49);
152  /* [r4 r3 r2 r1 r0] = [p8 p7 p6 p5 p4 p3 p2 p1 p0] */
153 }
154 
155 SECP256K1_INLINE static void secp256k1_fe_sqr_inner(uint64_t *r, const uint64_t *a) {
156  uint128_t c, d;
157  uint64_t a0 = a[0], a1 = a[1], a2 = a[2], a3 = a[3], a4 = a[4];
158  int64_t t3, t4, tx, u0;
159  const uint64_t M = 0xFFFFFFFFFFFFFULL, R = 0x1000003D10ULL;
160 
161  VERIFY_BITS(a[0], 56);
162  VERIFY_BITS(a[1], 56);
163  VERIFY_BITS(a[2], 56);
164  VERIFY_BITS(a[3], 56);
165  VERIFY_BITS(a[4], 52);
166 
172  d = (uint128_t)(a0*2) * a3
173  + (uint128_t)(a1*2) * a2;
174  VERIFY_BITS(d, 114);
175  /* [d 0 0 0] = [p3 0 0 0] */
176  c = (uint128_t)a4 * a4;
177  VERIFY_BITS(c, 112);
178  /* [c 0 0 0 0 d 0 0 0] = [p8 0 0 0 0 p3 0 0 0] */
179  d += (c & M) * R; c >>= 52;
180  VERIFY_BITS(d, 115);
181  VERIFY_BITS(c, 60);
182  /* [c 0 0 0 0 0 d 0 0 0] = [p8 0 0 0 0 p3 0 0 0] */
183  t3 = d & M; d >>= 52;
184  VERIFY_BITS(t3, 52);
185  VERIFY_BITS(d, 63);
186  /* [c 0 0 0 0 d t3 0 0 0] = [p8 0 0 0 0 p3 0 0 0] */
187 
188  a4 *= 2;
189  d += (uint128_t)a0 * a4
190  + (uint128_t)(a1*2) * a3
191  + (uint128_t)a2 * a2;
192  VERIFY_BITS(d, 115);
193  /* [c 0 0 0 0 d t3 0 0 0] = [p8 0 0 0 p4 p3 0 0 0] */
194  d += c * R;
195  VERIFY_BITS(d, 116);
196  /* [d t3 0 0 0] = [p8 0 0 0 p4 p3 0 0 0] */
197  t4 = d & M; d >>= 52;
198  VERIFY_BITS(t4, 52);
199  VERIFY_BITS(d, 64);
200  /* [d t4 t3 0 0 0] = [p8 0 0 0 p4 p3 0 0 0] */
201  tx = (t4 >> 48); t4 &= (M >> 4);
202  VERIFY_BITS(tx, 4);
203  VERIFY_BITS(t4, 48);
204  /* [d t4+(tx<<48) t3 0 0 0] = [p8 0 0 0 p4 p3 0 0 0] */
205 
206  c = (uint128_t)a0 * a0;
207  VERIFY_BITS(c, 112);
208  /* [d t4+(tx<<48) t3 0 0 c] = [p8 0 0 0 p4 p3 0 0 p0] */
209  d += (uint128_t)a1 * a4
210  + (uint128_t)(a2*2) * a3;
211  VERIFY_BITS(d, 114);
212  /* [d t4+(tx<<48) t3 0 0 c] = [p8 0 0 p5 p4 p3 0 0 p0] */
213  u0 = d & M; d >>= 52;
214  VERIFY_BITS(u0, 52);
215  VERIFY_BITS(d, 62);
216  /* [d u0 t4+(tx<<48) t3 0 0 c] = [p8 0 0 p5 p4 p3 0 0 p0] */
217  /* [d 0 t4+(tx<<48)+(u0<<52) t3 0 0 c] = [p8 0 0 p5 p4 p3 0 0 p0] */
218  u0 = (u0 << 4) | tx;
219  VERIFY_BITS(u0, 56);
220  /* [d 0 t4+(u0<<48) t3 0 0 c] = [p8 0 0 p5 p4 p3 0 0 p0] */
221  c += (uint128_t)u0 * (R >> 4);
222  VERIFY_BITS(c, 113);
223  /* [d 0 t4 t3 0 0 c] = [p8 0 0 p5 p4 p3 0 0 p0] */
224  r[0] = c & M; c >>= 52;
225  VERIFY_BITS(r[0], 52);
226  VERIFY_BITS(c, 61);
227  /* [d 0 t4 t3 0 c r0] = [p8 0 0 p5 p4 p3 0 0 p0] */
228 
229  a0 *= 2;
230  c += (uint128_t)a0 * a1;
231  VERIFY_BITS(c, 114);
232  /* [d 0 t4 t3 0 c r0] = [p8 0 0 p5 p4 p3 0 p1 p0] */
233  d += (uint128_t)a2 * a4
234  + (uint128_t)a3 * a3;
235  VERIFY_BITS(d, 114);
236  /* [d 0 t4 t3 0 c r0] = [p8 0 p6 p5 p4 p3 0 p1 p0] */
237  c += (d & M) * R; d >>= 52;
238  VERIFY_BITS(c, 115);
239  VERIFY_BITS(d, 62);
240  /* [d 0 0 t4 t3 0 c r0] = [p8 0 p6 p5 p4 p3 0 p1 p0] */
241  r[1] = c & M; c >>= 52;
242  VERIFY_BITS(r[1], 52);
243  VERIFY_BITS(c, 63);
244  /* [d 0 0 t4 t3 c r1 r0] = [p8 0 p6 p5 p4 p3 0 p1 p0] */
245 
246  c += (uint128_t)a0 * a2
247  + (uint128_t)a1 * a1;
248  VERIFY_BITS(c, 114);
249  /* [d 0 0 t4 t3 c r1 r0] = [p8 0 p6 p5 p4 p3 p2 p1 p0] */
250  d += (uint128_t)a3 * a4;
251  VERIFY_BITS(d, 114);
252  /* [d 0 0 t4 t3 c r1 r0] = [p8 p7 p6 p5 p4 p3 p2 p1 p0] */
253  c += (d & M) * R; d >>= 52;
254  VERIFY_BITS(c, 115);
255  VERIFY_BITS(d, 62);
256  /* [d 0 0 0 t4 t3 c r1 r0] = [p8 p7 p6 p5 p4 p3 p2 p1 p0] */
257  r[2] = c & M; c >>= 52;
258  VERIFY_BITS(r[2], 52);
259  VERIFY_BITS(c, 63);
260  /* [d 0 0 0 t4 t3+c r2 r1 r0] = [p8 p7 p6 p5 p4 p3 p2 p1 p0] */
261 
262  c += d * R + t3;
263  VERIFY_BITS(c, 100);
264  /* [t4 c r2 r1 r0] = [p8 p7 p6 p5 p4 p3 p2 p1 p0] */
265  r[3] = c & M; c >>= 52;
266  VERIFY_BITS(r[3], 52);
267  VERIFY_BITS(c, 48);
268  /* [t4+c r3 r2 r1 r0] = [p8 p7 p6 p5 p4 p3 p2 p1 p0] */
269  c += t4;
270  VERIFY_BITS(c, 49);
271  /* [c r3 r2 r1 r0] = [p8 p7 p6 p5 p4 p3 p2 p1 p0] */
272  r[4] = c;
273  VERIFY_BITS(r[4], 49);
274  /* [r4 r3 r2 r1 r0] = [p8 p7 p6 p5 p4 p3 p2 p1 p0] */
275 }
276 
277 #endif /* SECP256K1_FIELD_INNER5X52_IMPL_H */
VERIFY_CHECK
#define VERIFY_CHECK(cond)
Definition: util.h:67
SECP256K1_INLINE
#define SECP256K1_INLINE
Definition: secp256k1.h:110
SECP256K1_RESTRICT
#define SECP256K1_RESTRICT
Definition: util.h:89
VERIFY_BITS
#define VERIFY_BITS(x, n)
Definition: field_5x52_int128_impl.h:15
Generated on Wed Nov 28 2018 15:30:29 for BSHA3 by   doxygen 1.8.14