1 /*
2 * Copyright (c) 2016 Thomas Pornin <pornin@bolet.org>
3 *
4 * Permission is hereby granted, free of charge, to any person obtaining
5 * a copy of this software and associated documentation files (the
6 * "Software"), to deal in the Software without restriction, including
7 * without limitation the rights to use, copy, modify, merge, publish,
8 * distribute, sublicense, and/or sell copies of the Software, and to
9 * permit persons to whom the Software is furnished to do so, subject to
10 * the following conditions:
11 *
12 * The above copyright notice and this permission notice shall be
13 * included in all copies or substantial portions of the Software.
14 *
15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
16 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
17 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
18 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
19 * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
20 * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
21 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
22 * SOFTWARE.
23 */
25 #include "inner.h"
27 /*
28 * We compute "carryless multiplications" through normal integer
29 * multiplications, masking out enough bits to create "holes" in which
30 * carries may expand without altering our bits; we really use 8 data
31 * bits per 32-bit word, spaced every fourth bit. Accumulated carries
32 * may not exceed 8 in total, which fits in 4 bits.
33 *
34 * It would be possible to use a 3-bit spacing, allowing two operands,
35 * one with 7 non-zero data bits, the other one with 10 or 11 non-zero
36 * data bits; this asymmetric splitting makes the overall code more
37 * complex with thresholds and exceptions, and does not appear to be
38 * worth the effort.
39 */
41 /*
42 * We cannot really autodetect whether multiplications are "slow" or
43 * not. A typical example is the ARM Cortex M0+, which exists in two
44 * versions: one with a 1-cycle multiplication opcode, the other with
45 * a 32-cycle multiplication opcode. They both use exactly the same
46 * architecture and ABI, and cannot be distinguished from each other
47 * at compile-time.
48 *
49 * Since most modern CPU (even embedded CPU) still have fast
50 * multiplications, we use the "fast mul" code by default.
51 */
53 #if BR_SLOW_MUL
55 /*
56 * This implementation uses Karatsuba-like reduction to make fewer
57 * integer multiplications (9 instead of 16), at the expense of extra
58 * logical operations (XOR, shifts...). On modern x86 CPU that offer
59 * fast, pipelined multiplications, this code is about twice slower than
60 * the simpler code with 16 multiplications. This tendency may be
61 * reversed on low-end platforms with expensive multiplications.
62 */
64 #define MUL32(h, l, x, y) do { \
65 uint64_t mul32tmp = MUL(x, y); \
66 (h) = (uint32_t)(mul32tmp >> 32); \
67 (l) = (uint32_t)mul32tmp; \
68 } while (0)
70 static inline void
71 bmul(uint32_t *hi, uint32_t *lo, uint32_t x, uint32_t y)
72 {
73 uint32_t x0, x1, x2, x3;
74 uint32_t y0, y1, y2, y3;
75 uint32_t a0, a1, a2, a3, a4, a5, a6, a7, a8;
76 uint32_t b0, b1, b2, b3, b4, b5, b6, b7, b8;
78 x0 = x & (uint32_t)0x11111111;
79 x1 = x & (uint32_t)0x22222222;
80 x2 = x & (uint32_t)0x44444444;
81 x3 = x & (uint32_t)0x88888888;
82 y0 = y & (uint32_t)0x11111111;
83 y1 = y & (uint32_t)0x22222222;
84 y2 = y & (uint32_t)0x44444444;
85 y3 = y & (uint32_t)0x88888888;
87 /*
88 * (x0+W*x1)*(y0+W*y1) -> a0:b0
89 * (x2+W*x3)*(y2+W*y3) -> a3:b3
90 * ((x0+x2)+W*(x1+x3))*((y0+y2)+W*(y1+y3)) -> a6:b6
91 */
92 a0 = x0;
93 b0 = y0;
94 a1 = x1 >> 1;
95 b1 = y1 >> 1;
96 a2 = a0 ^ a1;
97 b2 = b0 ^ b1;
98 a3 = x2 >> 2;
99 b3 = y2 >> 2;
100 a4 = x3 >> 3;
101 b4 = y3 >> 3;
102 a5 = a3 ^ a4;
103 b5 = b3 ^ b4;
104 a6 = a0 ^ a3;
105 b6 = b0 ^ b3;
106 a7 = a1 ^ a4;
107 b7 = b1 ^ b4;
108 a8 = a6 ^ a7;
109 b8 = b6 ^ b7;
111 MUL32(b0, a0, b0, a0);
112 MUL32(b1, a1, b1, a1);
113 MUL32(b2, a2, b2, a2);
114 MUL32(b3, a3, b3, a3);
115 MUL32(b4, a4, b4, a4);
116 MUL32(b5, a5, b5, a5);
117 MUL32(b6, a6, b6, a6);
118 MUL32(b7, a7, b7, a7);
119 MUL32(b8, a8, b8, a8);
121 a0 &= (uint32_t)0x11111111;
122 a1 &= (uint32_t)0x11111111;
123 a2 &= (uint32_t)0x11111111;
124 a3 &= (uint32_t)0x11111111;
125 a4 &= (uint32_t)0x11111111;
126 a5 &= (uint32_t)0x11111111;
127 a6 &= (uint32_t)0x11111111;
128 a7 &= (uint32_t)0x11111111;
129 a8 &= (uint32_t)0x11111111;
130 b0 &= (uint32_t)0x11111111;
131 b1 &= (uint32_t)0x11111111;
132 b2 &= (uint32_t)0x11111111;
133 b3 &= (uint32_t)0x11111111;
134 b4 &= (uint32_t)0x11111111;
135 b5 &= (uint32_t)0x11111111;
136 b6 &= (uint32_t)0x11111111;
137 b7 &= (uint32_t)0x11111111;
138 b8 &= (uint32_t)0x11111111;
140 a2 ^= a0 ^ a1;
141 b2 ^= b0 ^ b1;
142 a0 ^= (a2 << 1) ^ (a1 << 2);
143 b0 ^= (b2 << 1) ^ (b1 << 2);
144 a5 ^= a3 ^ a4;
145 b5 ^= b3 ^ b4;
146 a3 ^= (a5 << 1) ^ (a4 << 2);
147 b3 ^= (b5 << 1) ^ (b4 << 2);
148 a8 ^= a6 ^ a7;
149 b8 ^= b6 ^ b7;
150 a6 ^= (a8 << 1) ^ (a7 << 2);
151 b6 ^= (b8 << 1) ^ (b7 << 2);
152 a6 ^= a0 ^ a3;
153 b6 ^= b0 ^ b3;
154 *lo = a0 ^ (a6 << 2) ^ (a3 << 4);
155 *hi = b0 ^ (b6 << 2) ^ (b3 << 4) ^ (a6 >> 30) ^ (a3 >> 28);
156 }
158 #else
160 /*
161 * Simple multiplication in GF(2)[X], using 16 integer multiplications.
162 */
164 static inline void
165 bmul(uint32_t *hi, uint32_t *lo, uint32_t x, uint32_t y)
166 {
167 uint32_t x0, x1, x2, x3;
168 uint32_t y0, y1, y2, y3;
169 uint64_t z0, z1, z2, z3;
170 uint64_t z;
172 x0 = x & (uint32_t)0x11111111;
173 x1 = x & (uint32_t)0x22222222;
174 x2 = x & (uint32_t)0x44444444;
175 x3 = x & (uint32_t)0x88888888;
176 y0 = y & (uint32_t)0x11111111;
177 y1 = y & (uint32_t)0x22222222;
178 y2 = y & (uint32_t)0x44444444;
179 y3 = y & (uint32_t)0x88888888;
180 z0 = MUL(x0, y0) ^ MUL(x1, y3) ^ MUL(x2, y2) ^ MUL(x3, y1);
181 z1 = MUL(x0, y1) ^ MUL(x1, y0) ^ MUL(x2, y3) ^ MUL(x3, y2);
182 z2 = MUL(x0, y2) ^ MUL(x1, y1) ^ MUL(x2, y0) ^ MUL(x3, y3);
183 z3 = MUL(x0, y3) ^ MUL(x1, y2) ^ MUL(x2, y1) ^ MUL(x3, y0);
184 z0 &= (uint64_t)0x1111111111111111;
185 z1 &= (uint64_t)0x2222222222222222;
186 z2 &= (uint64_t)0x4444444444444444;
187 z3 &= (uint64_t)0x8888888888888888;
188 z = z0 | z1 | z2 | z3;
189 *lo = (uint32_t)z;
190 *hi = (uint32_t)(z >> 32);
191 }
193 #endif
196 void
197 br_ghash_ctmul(void *y, const void *h, const void *data, size_t len)
198 {
199 const unsigned char *buf, *hb;
200 unsigned char *yb;
201 uint32_t yw;
202 uint32_t hw;
204 /*
205 * Throughout the loop we handle the y and h values as arrays
206 * of 32-bit words.
207 */
208 buf = data;
209 yb = y;
210 hb = h;
211 yw = br_dec32be(yb);
212 yw = br_dec32be(yb + 4);
213 yw = br_dec32be(yb + 8);
214 yw = br_dec32be(yb + 12);
215 hw = br_dec32be(hb);
216 hw = br_dec32be(hb + 4);
217 hw = br_dec32be(hb + 8);
218 hw = br_dec32be(hb + 12);
219 while (len > 0) {
220 const unsigned char *src;
221 unsigned char tmp;
222 int i;
223 uint32_t a, b, zw;
224 uint32_t c0, c1, c2, c3, d0, d1, d2, d3, e0, e1, e2, e3;
226 /*
227 * Get the next 16-byte block (using zero-padding if
228 * necessary).
229 */
230 if (len >= 16) {
231 src = buf;
232 buf += 16;
233 len -= 16;
234 } else {
235 memcpy(tmp, buf, len);
236 memset(tmp + len, 0, (sizeof tmp) - len);
237 src = tmp;
238 len = 0;
239 }
241 /*
242 * Decode the block. The GHASH standard mandates
243 * big-endian encoding.
244 */
245 yw ^= br_dec32be(src);
246 yw ^= br_dec32be(src + 4);
247 yw ^= br_dec32be(src + 8);
248 yw ^= br_dec32be(src + 12);
250 /*
251 * We multiply two 128-bit field elements. We use
252 * Karatsuba to turn that into three 64-bit
253 * multiplications, which are themselves done with a
254 * total of nine 32-bit multiplications.
255 */
257 /*
258 * y[0,1]*h[0,1] -> 0..2
259 * y[2,3]*h[2,3] -> 3..5
260 * (y[0,1]+y[2,3])*(h[0,1]+h[2,3]) -> 6..8
261 */
262 a = yw;
263 b = hw;
264 a = yw;
265 b = hw;
266 a = a ^ a;
267 b = b ^ b;
269 a = yw;
270 b = hw;
271 a = yw;
272 b = hw;
273 a = a ^ a;
274 b = b ^ b;
276 a = a ^ a;
277 b = b ^ b;
278 a = a ^ a;
279 b = b ^ b;
280 a = a ^ a;
281 b = b ^ b;
283 for (i = 0; i < 9; i ++) {
284 bmul(&b[i], &a[i], b[i], a[i]);
285 }
287 c0 = a;
288 c1 = b ^ a ^ a ^ a;
289 c2 = a ^ b ^ b ^ b;
290 c3 = b;
291 d0 = a;
292 d1 = b ^ a ^ a ^ a;
293 d2 = a ^ b ^ b ^ b;
294 d3 = b;
295 e0 = a;
296 e1 = b ^ a ^ a ^ a;
297 e2 = a ^ b ^ b ^ b;
298 e3 = b;
300 e0 ^= c0 ^ d0;
301 e1 ^= c1 ^ d1;
302 e2 ^= c2 ^ d2;
303 e3 ^= c3 ^ d3;
304 c2 ^= e0;
305 c3 ^= e1;
306 d0 ^= e2;
307 d1 ^= e3;
309 /*
310 * GHASH specification has the bits "reversed" (most
311 * significant is in fact least significant), which does
312 * not matter for a carryless multiplication, except that
313 * the 255-bit result must be shifted by 1 bit.
314 */
315 zw = c0 << 1;
316 zw = (c1 << 1) | (c0 >> 31);
317 zw = (c2 << 1) | (c1 >> 31);
318 zw = (c3 << 1) | (c2 >> 31);
319 zw = (d0 << 1) | (c3 >> 31);
320 zw = (d1 << 1) | (d0 >> 31);
321 zw = (d2 << 1) | (d1 >> 31);
322 zw = (d3 << 1) | (d2 >> 31);
324 /*
325 * We now do the reduction modulo the field polynomial
326 * to get back to 128 bits.
327 */
328 for (i = 0; i < 4; i ++) {
329 uint32_t lw;
331 lw = zw[i];
332 zw[i + 4] ^= lw ^ (lw >> 1) ^ (lw >> 2) ^ (lw >> 7);
333 zw[i + 3] ^= (lw << 31) ^ (lw << 30) ^ (lw << 25);
334 }
335 memcpy(yw, zw + 4, sizeof yw);
336 }
338 /*
339 * Encode back the result.
340 */
341 br_enc32be(yb, yw);
342 br_enc32be(yb + 4, yw);
343 br_enc32be(yb + 8, yw);
344 br_enc32be(yb + 12, yw);
345 }
{"ft_lang_label":"__label__en","ft_lang_prob":0.5393496,"math_prob":0.9983445,"size":8143,"snap":"2020-10-2020-16","text_gpt3_token_len":3511,"char_repetition_ratio":0.17913748,"word_repetition_ratio":0.03323442,"special_character_ratio":0.54353434,"punctuation_ratio":0.18287711,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9921373,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2020-02-24T05:29:20Z\",\"WARC-Record-ID\":\"<urn:uuid:1ce99bfe-6fd9-4231-a748-15e93f6b5bb4>\",\"Content-Length\":\"98754\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:34cf21bd-8a35-4223-9567-0a7f9a492900>\",\"WARC-Concurrent-To\":\"<urn:uuid:6e62ec9c-5798-4585-b156-85e2183e8555>\",\"WARC-IP-Address\":\"158.69.204.153\",\"WARC-Target-URI\":\"https://www.bearssl.org/gitweb/?p=BearSSL;a=blob;f=src/hash/ghash_ctmul.c;hb=HEAD\",\"WARC-Payload-Digest\":\"sha1:XNGR26CRUAPZLLQEQHROYLYNUV3VHNKL\",\"WARC-Block-Digest\":\"sha1:5CCZOQD7QV3XQT4QDYW6TPIFY4Z3QFMM\",\"WARC-Identified-Payload-Type\":\"application/xhtml+xml\",\"warc_filename\":\"/cc_download/warc_2020/CC-MAIN-2020-10/CC-MAIN-2020-10_segments_1581875145897.19_warc_CC-MAIN-20200224040929-20200224070929-00527.warc.gz\"}"}