1 /* ====================================================================
2 * Copyright (c) 2011-2013 The OpenSSL Project. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 *
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 *
11 * 2. Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in
13 * the documentation and/or other materials provided with the
14 * distribution.
15 *
16 * 3. All advertising materials mentioning features or use of this
17 * software must display the following acknowledgment:
18 * "This product includes software developed by the OpenSSL Project
19 * for use in the OpenSSL Toolkit. (http://www.OpenSSL.org/)"
20 *
21 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
22 * endorse or promote products derived from this software without
23 * prior written permission. For written permission, please contact
24 * licensing@OpenSSL.org.
25 *
26 * 5. Products derived from this software may not be called "OpenSSL"
27 * nor may "OpenSSL" appear in their names without prior written
28 * permission of the OpenSSL Project.
29 *
30 * 6. Redistributions of any form whatsoever must retain the following
31 * acknowledgment:
32 * "This product includes software developed by the OpenSSL Project
33 * for use in the OpenSSL Toolkit (http://www.OpenSSL.org/)"
34 *
35 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
36 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
37 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
38 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR
39 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
40 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
41 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
42 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
43 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
44 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
45 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
46 * OF THE POSSIBILITY OF SUCH DAMAGE.
47 * ====================================================================
48 */
49
50 /* This implementation of poly1305 is by Andrew Moon
51 * (https://github.com/floodyberry/poly1305-donna) and released as public
52 * domain. It implements SIMD vectorization based on the algorithm described in
53 * http://cr.yp.to/papers.html#neoncrypto. Unrolled to 2 powers, i.e. 64 byte
54 * block size
55 */
56
57 #include <emmintrin.h>
58 #include <stdint.h>
59 #include <openssl/opensslconf.h>
60
61 #if !defined(OPENSSL_NO_POLY1305)
62
63 #include <openssl/poly1305.h>
64
65 #define ALIGN(x) __attribute__((aligned(x)))
66 #define INLINE inline
67 #define U8TO64_LE(m) (*(uint64_t*)(m))
68 #define U8TO32_LE(m) (*(uint32_t*)(m))
69 #define U64TO8_LE(m,v) (*(uint64_t*)(m)) = v
70
71 typedef __m128i xmmi;
72 typedef unsigned __int128 uint128_t;
73
74 static const uint32_t ALIGN(16) poly1305_x64_sse2_message_mask[4] =
75 {(1 << 26) - 1, 0, (1 << 26) - 1, 0};
76 static const uint32_t ALIGN(16) poly1305_x64_sse2_5[4] = {5, 0, 5, 0};
77 static const uint32_t ALIGN(16) poly1305_x64_sse2_1shl128[4] =
78 {(1 << 24), 0, (1 << 24), 0};
79
80 static uint128_t INLINE
add128(uint128_t a,uint128_t b)81 add128(uint128_t a, uint128_t b)
82 {
83 return a + b;
84 }
85
86 static uint128_t INLINE
add128_64(uint128_t a,uint64_t b)87 add128_64(uint128_t a, uint64_t b)
88 {
89 return a + b;
90 }
91
92 static uint128_t INLINE
mul64x64_128(uint64_t a,uint64_t b)93 mul64x64_128(uint64_t a, uint64_t b)
94 {
95 return (uint128_t)a * b;
96 }
97
98 static uint64_t INLINE
lo128(uint128_t a)99 lo128(uint128_t a)
100 {
101 return (uint64_t)a;
102 }
103
104 static uint64_t INLINE
shr128(uint128_t v,const int shift)105 shr128(uint128_t v, const int shift)
106 {
107 return (uint64_t)(v >> shift);
108 }
109
110 static uint64_t INLINE
shr128_pair(uint64_t hi,uint64_t lo,const int shift)111 shr128_pair(uint64_t hi, uint64_t lo, const int shift)
112 {
113 return (uint64_t)((((uint128_t)hi << 64) | lo) >> shift);
114 }
115
116 typedef struct poly1305_power_t
117 {
118 union
119 {
120 xmmi v;
121 uint64_t u[2];
122 uint32_t d[4];
123 } R20,R21,R22,R23,R24,S21,S22,S23,S24;
124 } poly1305_power;
125
126 typedef struct poly1305_state_internal_t
127 {
128 poly1305_power P[2]; /* 288 bytes, top 32 bit halves unused = 144
129 bytes of free storage */
130 union
131 {
132 xmmi H[5]; /* 80 bytes */
133 uint64_t HH[10];
134 };
135 /* uint64_t r0,r1,r2; [24 bytes] */
136 /* uint64_t pad0,pad1; [16 bytes] */
137 uint64_t started; /* 8 bytes */
138 uint64_t leftover; /* 8 bytes */
139 uint8_t buffer[64]; /* 64 bytes */
140 } poly1305_state_internal; /* 448 bytes total + 63 bytes for
141 alignment = 511 bytes raw */
142
143 static poly1305_state_internal INLINE
poly1305_aligned_state(poly1305_state * state)144 *poly1305_aligned_state(poly1305_state *state)
145 {
146 return (poly1305_state_internal *)(((uint64_t)state + 63) & ~63);
147 }
148
149 /* copy 0-63 bytes */
150 static void INLINE
poly1305_block_copy(uint8_t * dst,const uint8_t * src,size_t bytes)151 poly1305_block_copy(uint8_t *dst, const uint8_t *src, size_t bytes)
152 {
153 size_t offset = src - dst;
154 if (bytes & 32)
155 {
156 _mm_storeu_si128((xmmi *)(dst + 0), _mm_loadu_si128((xmmi *)(dst + offset + 0)));
157 _mm_storeu_si128((xmmi *)(dst + 16), _mm_loadu_si128((xmmi *)(dst + offset + 16)));
158 dst += 32;
159 }
160 if (bytes & 16)
161 {
162 _mm_storeu_si128((xmmi *)dst,
163 _mm_loadu_si128((xmmi *)(dst + offset)));
164 dst += 16;
165 }
166 if (bytes & 8)
167 {
168 *(uint64_t *)dst = *(uint64_t *)(dst + offset);
169 dst += 8;
170 }
171 if (bytes & 4)
172 {
173 *(uint32_t *)dst = *(uint32_t *)(dst + offset);
174 dst += 4;
175 }
176 if (bytes & 2)
177 {
178 *(uint16_t *)dst = *(uint16_t *)(dst + offset);
179 dst += 2;
180 }
181 if (bytes & 1)
182 {
183 *( uint8_t *)dst = *( uint8_t *)(dst + offset);
184 }
185 }
186
187 /* zero 0-15 bytes */
188 static void INLINE
poly1305_block_zero(uint8_t * dst,size_t bytes)189 poly1305_block_zero(uint8_t *dst, size_t bytes)
190 {
191 if (bytes & 8) { *(uint64_t *)dst = 0; dst += 8; }
192 if (bytes & 4) { *(uint32_t *)dst = 0; dst += 4; }
193 if (bytes & 2) { *(uint16_t *)dst = 0; dst += 2; }
194 if (bytes & 1) { *( uint8_t *)dst = 0; }
195 }
196
197 static size_t INLINE
poly1305_min(size_t a,size_t b)198 poly1305_min(size_t a, size_t b)
199 {
200 return (a < b) ? a : b;
201 }
202
203 void
CRYPTO_poly1305_init(poly1305_state * state,const unsigned char key[32])204 CRYPTO_poly1305_init(poly1305_state *state, const unsigned char key[32])
205 {
206 poly1305_state_internal *st = poly1305_aligned_state(state);
207 poly1305_power *p;
208 uint64_t r0,r1,r2;
209 uint64_t t0,t1;
210
211 /* clamp key */
212 t0 = U8TO64_LE(key + 0);
213 t1 = U8TO64_LE(key + 8);
214 r0 = t0 & 0xffc0fffffff; t0 >>= 44; t0 |= t1 << 20;
215 r1 = t0 & 0xfffffc0ffff; t1 >>= 24;
216 r2 = t1 & 0x00ffffffc0f;
217
218 /* store r in un-used space of st->P[1] */
219 p = &st->P[1];
220 p->R20.d[1] = (uint32_t)(r0 );
221 p->R20.d[3] = (uint32_t)(r0 >> 32);
222 p->R21.d[1] = (uint32_t)(r1 );
223 p->R21.d[3] = (uint32_t)(r1 >> 32);
224 p->R22.d[1] = (uint32_t)(r2 );
225 p->R22.d[3] = (uint32_t)(r2 >> 32);
226
227 /* store pad */
228 p->R23.d[1] = U8TO32_LE(key + 16);
229 p->R23.d[3] = U8TO32_LE(key + 20);
230 p->R24.d[1] = U8TO32_LE(key + 24);
231 p->R24.d[3] = U8TO32_LE(key + 28);
232
233 /* H = 0 */
234 st->H[0] = _mm_setzero_si128();
235 st->H[1] = _mm_setzero_si128();
236 st->H[2] = _mm_setzero_si128();
237 st->H[3] = _mm_setzero_si128();
238 st->H[4] = _mm_setzero_si128();
239
240 st->started = 0;
241 st->leftover = 0;
242 }
243
244 static void
poly1305_first_block(poly1305_state_internal * st,const uint8_t * m)245 poly1305_first_block(poly1305_state_internal *st, const uint8_t *m)
246 {
247 const xmmi MMASK =
248 _mm_load_si128((xmmi *)poly1305_x64_sse2_message_mask);
249 const xmmi FIVE = _mm_load_si128((xmmi*)poly1305_x64_sse2_5);
250 const xmmi HIBIT = _mm_load_si128((xmmi*)poly1305_x64_sse2_1shl128);
251 xmmi T5,T6;
252 poly1305_power *p;
253 uint128_t d[3];
254 uint64_t r0,r1,r2;
255 uint64_t r20,r21,r22,s22;
256 uint64_t pad0,pad1;
257 uint64_t c;
258 uint64_t i;
259
260 /* pull out stored info */
261 p = &st->P[1];
262
263 r0 = ((uint64_t)p->R20.d[3] << 32) | (uint64_t)p->R20.d[1];
264 r1 = ((uint64_t)p->R21.d[3] << 32) | (uint64_t)p->R21.d[1];
265 r2 = ((uint64_t)p->R22.d[3] << 32) | (uint64_t)p->R22.d[1];
266 pad0 = ((uint64_t)p->R23.d[3] << 32) | (uint64_t)p->R23.d[1];
267 pad1 = ((uint64_t)p->R24.d[3] << 32) | (uint64_t)p->R24.d[1];
268
269 /* compute powers r^2,r^4 */
270 r20 = r0;
271 r21 = r1;
272 r22 = r2;
273 for (i = 0; i < 2; i++)
274 {
275 s22 = r22 * (5 << 2);
276
277 d[0] = add128(mul64x64_128(r20, r20), mul64x64_128(r21 * 2, s22));
278 d[1] = add128(mul64x64_128(r22, s22), mul64x64_128(r20 * 2, r21));
279 d[2] = add128(mul64x64_128(r21, r21), mul64x64_128(r22 * 2, r20));
280
281 r20 = lo128(d[0]) & 0xfffffffffff; c = shr128(d[0], 44);
282 d[1] = add128_64(d[1], c); r21 = lo128(d[1]) & 0xfffffffffff; c = shr128(d[1], 44);
283 d[2] = add128_64(d[2], c); r22 = lo128(d[2]) & 0x3ffffffffff; c = shr128(d[2], 42);
284 r20 += c * 5; c = (r20 >> 44); r20 = r20 & 0xfffffffffff;
285 r21 += c;
286
287 p->R20.v = _mm_shuffle_epi32(_mm_cvtsi32_si128((uint32_t)( r20 ) & 0x3ffffff), _MM_SHUFFLE(1,0,1,0));
288 p->R21.v = _mm_shuffle_epi32(_mm_cvtsi32_si128((uint32_t)((r20 >> 26) | (r21 << 18)) & 0x3ffffff), _MM_SHUFFLE(1,0,1,0));
289 p->R22.v = _mm_shuffle_epi32(_mm_cvtsi32_si128((uint32_t)((r21 >> 8) ) & 0x3ffffff), _MM_SHUFFLE(1,0,1,0));
290 p->R23.v = _mm_shuffle_epi32(_mm_cvtsi32_si128((uint32_t)((r21 >> 34) | (r22 << 10)) & 0x3ffffff), _MM_SHUFFLE(1,0,1,0));
291 p->R24.v = _mm_shuffle_epi32(_mm_cvtsi32_si128((uint32_t)((r22 >> 16) ) ), _MM_SHUFFLE(1,0,1,0));
292 p->S21.v = _mm_mul_epu32(p->R21.v, FIVE);
293 p->S22.v = _mm_mul_epu32(p->R22.v, FIVE);
294 p->S23.v = _mm_mul_epu32(p->R23.v, FIVE);
295 p->S24.v = _mm_mul_epu32(p->R24.v, FIVE);
296 p--;
297 }
298
299 /* put saved info back */
300 p = &st->P[1];
301 p->R20.d[1] = (uint32_t)(r0 );
302 p->R20.d[3] = (uint32_t)(r0 >> 32);
303 p->R21.d[1] = (uint32_t)(r1 );
304 p->R21.d[3] = (uint32_t)(r1 >> 32);
305 p->R22.d[1] = (uint32_t)(r2 );
306 p->R22.d[3] = (uint32_t)(r2 >> 32);
307 p->R23.d[1] = (uint32_t)(pad0 );
308 p->R23.d[3] = (uint32_t)(pad0 >> 32);
309 p->R24.d[1] = (uint32_t)(pad1 );
310 p->R24.d[3] = (uint32_t)(pad1 >> 32);
311
312 /* H = [Mx,My] */
313 T5 = _mm_unpacklo_epi64(_mm_loadl_epi64((xmmi *)(m + 0)), _mm_loadl_epi64((xmmi *)(m + 16)));
314 T6 = _mm_unpacklo_epi64(_mm_loadl_epi64((xmmi *)(m + 8)), _mm_loadl_epi64((xmmi *)(m + 24)));
315 st->H[0] = _mm_and_si128(MMASK, T5);
316 st->H[1] = _mm_and_si128(MMASK, _mm_srli_epi64(T5, 26));
317 T5 = _mm_or_si128(_mm_srli_epi64(T5, 52), _mm_slli_epi64(T6, 12));
318 st->H[2] = _mm_and_si128(MMASK, T5);
319 st->H[3] = _mm_and_si128(MMASK, _mm_srli_epi64(T5, 26));
320 st->H[4] = _mm_or_si128(_mm_srli_epi64(T6, 40), HIBIT);
321 }
322
323 static void
poly1305_blocks(poly1305_state_internal * st,const uint8_t * m,size_t bytes)324 poly1305_blocks(poly1305_state_internal *st, const uint8_t *m, size_t bytes)
325 {
326 const xmmi MMASK = _mm_load_si128((xmmi *)poly1305_x64_sse2_message_mask);
327 const xmmi FIVE = _mm_load_si128((xmmi*)poly1305_x64_sse2_5);
328 const xmmi HIBIT = _mm_load_si128((xmmi*)poly1305_x64_sse2_1shl128);
329
330 poly1305_power *p;
331 xmmi H0,H1,H2,H3,H4;
332 xmmi T0,T1,T2,T3,T4,T5,T6;
333 xmmi M0,M1,M2,M3,M4;
334 xmmi C1,C2;
335
336 H0 = st->H[0];
337 H1 = st->H[1];
338 H2 = st->H[2];
339 H3 = st->H[3];
340 H4 = st->H[4];
341
342 while (bytes >= 64)
343 {
344 /* H *= [r^4,r^4] */
345 p = &st->P[0];
346 T0 = _mm_mul_epu32(H0, p->R20.v);
347 T1 = _mm_mul_epu32(H0, p->R21.v);
348 T2 = _mm_mul_epu32(H0, p->R22.v);
349 T3 = _mm_mul_epu32(H0, p->R23.v);
350 T4 = _mm_mul_epu32(H0, p->R24.v);
351 T5 = _mm_mul_epu32(H1, p->S24.v); T6 = _mm_mul_epu32(H1, p->R20.v); T0 = _mm_add_epi64(T0, T5); T1 = _mm_add_epi64(T1, T6);
352 T5 = _mm_mul_epu32(H2, p->S23.v); T6 = _mm_mul_epu32(H2, p->S24.v); T0 = _mm_add_epi64(T0, T5); T1 = _mm_add_epi64(T1, T6);
353 T5 = _mm_mul_epu32(H3, p->S22.v); T6 = _mm_mul_epu32(H3, p->S23.v); T0 = _mm_add_epi64(T0, T5); T1 = _mm_add_epi64(T1, T6);
354 T5 = _mm_mul_epu32(H4, p->S21.v); T6 = _mm_mul_epu32(H4, p->S22.v); T0 = _mm_add_epi64(T0, T5); T1 = _mm_add_epi64(T1, T6);
355 T5 = _mm_mul_epu32(H1, p->R21.v); T6 = _mm_mul_epu32(H1, p->R22.v); T2 = _mm_add_epi64(T2, T5); T3 = _mm_add_epi64(T3, T6);
356 T5 = _mm_mul_epu32(H2, p->R20.v); T6 = _mm_mul_epu32(H2, p->R21.v); T2 = _mm_add_epi64(T2, T5); T3 = _mm_add_epi64(T3, T6);
357 T5 = _mm_mul_epu32(H3, p->S24.v); T6 = _mm_mul_epu32(H3, p->R20.v); T2 = _mm_add_epi64(T2, T5); T3 = _mm_add_epi64(T3, T6);
358 T5 = _mm_mul_epu32(H4, p->S23.v); T6 = _mm_mul_epu32(H4, p->S24.v); T2 = _mm_add_epi64(T2, T5); T3 = _mm_add_epi64(T3, T6);
359 T5 = _mm_mul_epu32(H1, p->R23.v); T4 = _mm_add_epi64(T4, T5);
360 T5 = _mm_mul_epu32(H2, p->R22.v); T4 = _mm_add_epi64(T4, T5);
361 T5 = _mm_mul_epu32(H3, p->R21.v); T4 = _mm_add_epi64(T4, T5);
362 T5 = _mm_mul_epu32(H4, p->R20.v); T4 = _mm_add_epi64(T4, T5);
363
364 /* H += [Mx,My]*[r^2,r^2] */
365 T5 = _mm_unpacklo_epi64(_mm_loadl_epi64((xmmi *)(m + 0)), _mm_loadl_epi64((xmmi *)(m + 16)));
366 T6 = _mm_unpacklo_epi64(_mm_loadl_epi64((xmmi *)(m + 8)), _mm_loadl_epi64((xmmi *)(m + 24)));
367 M0 = _mm_and_si128(MMASK, T5);
368 M1 = _mm_and_si128(MMASK, _mm_srli_epi64(T5, 26));
369 T5 = _mm_or_si128(_mm_srli_epi64(T5, 52), _mm_slli_epi64(T6, 12));
370 M2 = _mm_and_si128(MMASK, T5);
371 M3 = _mm_and_si128(MMASK, _mm_srli_epi64(T5, 26));
372 M4 = _mm_or_si128(_mm_srli_epi64(T6, 40), HIBIT);
373
374 p = &st->P[1];
375 T5 = _mm_mul_epu32(M0, p->R20.v); T6 = _mm_mul_epu32(M0, p->R21.v); T0 = _mm_add_epi64(T0, T5); T1 = _mm_add_epi64(T1, T6);
376 T5 = _mm_mul_epu32(M1, p->S24.v); T6 = _mm_mul_epu32(M1, p->R20.v); T0 = _mm_add_epi64(T0, T5); T1 = _mm_add_epi64(T1, T6);
377 T5 = _mm_mul_epu32(M2, p->S23.v); T6 = _mm_mul_epu32(M2, p->S24.v); T0 = _mm_add_epi64(T0, T5); T1 = _mm_add_epi64(T1, T6);
378 T5 = _mm_mul_epu32(M3, p->S22.v); T6 = _mm_mul_epu32(M3, p->S23.v); T0 = _mm_add_epi64(T0, T5); T1 = _mm_add_epi64(T1, T6);
379 T5 = _mm_mul_epu32(M4, p->S21.v); T6 = _mm_mul_epu32(M4, p->S22.v); T0 = _mm_add_epi64(T0, T5); T1 = _mm_add_epi64(T1, T6);
380 T5 = _mm_mul_epu32(M0, p->R22.v); T6 = _mm_mul_epu32(M0, p->R23.v); T2 = _mm_add_epi64(T2, T5); T3 = _mm_add_epi64(T3, T6);
381 T5 = _mm_mul_epu32(M1, p->R21.v); T6 = _mm_mul_epu32(M1, p->R22.v); T2 = _mm_add_epi64(T2, T5); T3 = _mm_add_epi64(T3, T6);
382 T5 = _mm_mul_epu32(M2, p->R20.v); T6 = _mm_mul_epu32(M2, p->R21.v); T2 = _mm_add_epi64(T2, T5); T3 = _mm_add_epi64(T3, T6);
383 T5 = _mm_mul_epu32(M3, p->S24.v); T6 = _mm_mul_epu32(M3, p->R20.v); T2 = _mm_add_epi64(T2, T5); T3 = _mm_add_epi64(T3, T6);
384 T5 = _mm_mul_epu32(M4, p->S23.v); T6 = _mm_mul_epu32(M4, p->S24.v); T2 = _mm_add_epi64(T2, T5); T3 = _mm_add_epi64(T3, T6);
385 T5 = _mm_mul_epu32(M0, p->R24.v); T4 = _mm_add_epi64(T4, T5);
386 T5 = _mm_mul_epu32(M1, p->R23.v); T4 = _mm_add_epi64(T4, T5);
387 T5 = _mm_mul_epu32(M2, p->R22.v); T4 = _mm_add_epi64(T4, T5);
388 T5 = _mm_mul_epu32(M3, p->R21.v); T4 = _mm_add_epi64(T4, T5);
389 T5 = _mm_mul_epu32(M4, p->R20.v); T4 = _mm_add_epi64(T4, T5);
390
391 /* H += [Mx,My] */
392 T5 = _mm_unpacklo_epi64(_mm_loadl_epi64((xmmi *)(m + 32)), _mm_loadl_epi64((xmmi *)(m + 48)));
393 T6 = _mm_unpacklo_epi64(_mm_loadl_epi64((xmmi *)(m + 40)), _mm_loadl_epi64((xmmi *)(m + 56)));
394 M0 = _mm_and_si128(MMASK, T5);
395 M1 = _mm_and_si128(MMASK, _mm_srli_epi64(T5, 26));
396 T5 = _mm_or_si128(_mm_srli_epi64(T5, 52), _mm_slli_epi64(T6, 12));
397 M2 = _mm_and_si128(MMASK, T5);
398 M3 = _mm_and_si128(MMASK, _mm_srli_epi64(T5, 26));
399 M4 = _mm_or_si128(_mm_srli_epi64(T6, 40), HIBIT);
400
401 T0 = _mm_add_epi64(T0, M0);
402 T1 = _mm_add_epi64(T1, M1);
403 T2 = _mm_add_epi64(T2, M2);
404 T3 = _mm_add_epi64(T3, M3);
405 T4 = _mm_add_epi64(T4, M4);
406
407 /* reduce */
408 C1 = _mm_srli_epi64(T0, 26); C2 = _mm_srli_epi64(T3, 26); T0 = _mm_and_si128(T0, MMASK); T3 = _mm_and_si128(T3, MMASK); T1 = _mm_add_epi64(T1, C1); T4 = _mm_add_epi64(T4, C2);
409 C1 = _mm_srli_epi64(T1, 26); C2 = _mm_srli_epi64(T4, 26); T1 = _mm_and_si128(T1, MMASK); T4 = _mm_and_si128(T4, MMASK); T2 = _mm_add_epi64(T2, C1); T0 = _mm_add_epi64(T0, _mm_mul_epu32(C2, FIVE));
410 C1 = _mm_srli_epi64(T2, 26); C2 = _mm_srli_epi64(T0, 26); T2 = _mm_and_si128(T2, MMASK); T0 = _mm_and_si128(T0, MMASK); T3 = _mm_add_epi64(T3, C1); T1 = _mm_add_epi64(T1, C2);
411 C1 = _mm_srli_epi64(T3, 26); T3 = _mm_and_si128(T3, MMASK); T4 = _mm_add_epi64(T4, C1);
412
413 /* H = (H*[r^4,r^4] + [Mx,My]*[r^2,r^2] + [Mx,My]) */
414 H0 = T0;
415 H1 = T1;
416 H2 = T2;
417 H3 = T3;
418 H4 = T4;
419
420 m += 64;
421 bytes -= 64;
422 }
423
424 st->H[0] = H0;
425 st->H[1] = H1;
426 st->H[2] = H2;
427 st->H[3] = H3;
428 st->H[4] = H4;
429 }
430
431 static size_t
poly1305_combine(poly1305_state_internal * st,const uint8_t * m,size_t bytes)432 poly1305_combine(poly1305_state_internal *st, const uint8_t *m, size_t bytes)
433 {
434 const xmmi MMASK =
435 _mm_load_si128((xmmi *)poly1305_x64_sse2_message_mask);
436 const xmmi HIBIT = _mm_load_si128((xmmi*)poly1305_x64_sse2_1shl128);
437 const xmmi FIVE = _mm_load_si128((xmmi*)poly1305_x64_sse2_5);
438
439 poly1305_power *p;
440 xmmi H0,H1,H2,H3,H4;
441 xmmi M0,M1,M2,M3,M4;
442 xmmi T0,T1,T2,T3,T4,T5,T6;
443 xmmi C1,C2;
444
445 uint64_t r0,r1,r2;
446 uint64_t t0,t1,t2,t3,t4;
447 uint64_t c;
448 size_t consumed = 0;
449
450 H0 = st->H[0];
451 H1 = st->H[1];
452 H2 = st->H[2];
453 H3 = st->H[3];
454 H4 = st->H[4];
455
456 /* p = [r^2,r^2] */
457 p = &st->P[1];
458
459 if (bytes >= 32)
460 {
461 /* H *= [r^2,r^2] */
462 T0 = _mm_mul_epu32(H0, p->R20.v);
463 T1 = _mm_mul_epu32(H0, p->R21.v);
464 T2 = _mm_mul_epu32(H0, p->R22.v);
465 T3 = _mm_mul_epu32(H0, p->R23.v);
466 T4 = _mm_mul_epu32(H0, p->R24.v);
467 T5 = _mm_mul_epu32(H1, p->S24.v); T6 = _mm_mul_epu32(H1, p->R20.v); T0 = _mm_add_epi64(T0, T5); T1 = _mm_add_epi64(T1, T6);
468 T5 = _mm_mul_epu32(H2, p->S23.v); T6 = _mm_mul_epu32(H2, p->S24.v); T0 = _mm_add_epi64(T0, T5); T1 = _mm_add_epi64(T1, T6);
469 T5 = _mm_mul_epu32(H3, p->S22.v); T6 = _mm_mul_epu32(H3, p->S23.v); T0 = _mm_add_epi64(T0, T5); T1 = _mm_add_epi64(T1, T6);
470 T5 = _mm_mul_epu32(H4, p->S21.v); T6 = _mm_mul_epu32(H4, p->S22.v); T0 = _mm_add_epi64(T0, T5); T1 = _mm_add_epi64(T1, T6);
471 T5 = _mm_mul_epu32(H1, p->R21.v); T6 = _mm_mul_epu32(H1, p->R22.v); T2 = _mm_add_epi64(T2, T5); T3 = _mm_add_epi64(T3, T6);
472 T5 = _mm_mul_epu32(H2, p->R20.v); T6 = _mm_mul_epu32(H2, p->R21.v); T2 = _mm_add_epi64(T2, T5); T3 = _mm_add_epi64(T3, T6);
473 T5 = _mm_mul_epu32(H3, p->S24.v); T6 = _mm_mul_epu32(H3, p->R20.v); T2 = _mm_add_epi64(T2, T5); T3 = _mm_add_epi64(T3, T6);
474 T5 = _mm_mul_epu32(H4, p->S23.v); T6 = _mm_mul_epu32(H4, p->S24.v); T2 = _mm_add_epi64(T2, T5); T3 = _mm_add_epi64(T3, T6);
475 T5 = _mm_mul_epu32(H1, p->R23.v); T4 = _mm_add_epi64(T4, T5);
476 T5 = _mm_mul_epu32(H2, p->R22.v); T4 = _mm_add_epi64(T4, T5);
477 T5 = _mm_mul_epu32(H3, p->R21.v); T4 = _mm_add_epi64(T4, T5);
478 T5 = _mm_mul_epu32(H4, p->R20.v); T4 = _mm_add_epi64(T4, T5);
479
480 /* H += [Mx,My] */
481 T5 = _mm_unpacklo_epi64(_mm_loadl_epi64((xmmi *)(m + 0)), _mm_loadl_epi64((xmmi *)(m + 16)));
482 T6 = _mm_unpacklo_epi64(_mm_loadl_epi64((xmmi *)(m + 8)), _mm_loadl_epi64((xmmi *)(m + 24)));
483 M0 = _mm_and_si128(MMASK, T5);
484 M1 = _mm_and_si128(MMASK, _mm_srli_epi64(T5, 26));
485 T5 = _mm_or_si128(_mm_srli_epi64(T5, 52), _mm_slli_epi64(T6, 12));
486 M2 = _mm_and_si128(MMASK, T5);
487 M3 = _mm_and_si128(MMASK, _mm_srli_epi64(T5, 26));
488 M4 = _mm_or_si128(_mm_srli_epi64(T6, 40), HIBIT);
489
490 T0 = _mm_add_epi64(T0, M0);
491 T1 = _mm_add_epi64(T1, M1);
492 T2 = _mm_add_epi64(T2, M2);
493 T3 = _mm_add_epi64(T3, M3);
494 T4 = _mm_add_epi64(T4, M4);
495
496 /* reduce */
497 C1 = _mm_srli_epi64(T0, 26); C2 = _mm_srli_epi64(T3, 26); T0 = _mm_and_si128(T0, MMASK); T3 = _mm_and_si128(T3, MMASK); T1 = _mm_add_epi64(T1, C1); T4 = _mm_add_epi64(T4, C2);
498 C1 = _mm_srli_epi64(T1, 26); C2 = _mm_srli_epi64(T4, 26); T1 = _mm_and_si128(T1, MMASK); T4 = _mm_and_si128(T4, MMASK); T2 = _mm_add_epi64(T2, C1); T0 = _mm_add_epi64(T0, _mm_mul_epu32(C2, FIVE));
499 C1 = _mm_srli_epi64(T2, 26); C2 = _mm_srli_epi64(T0, 26); T2 = _mm_and_si128(T2, MMASK); T0 = _mm_and_si128(T0, MMASK); T3 = _mm_add_epi64(T3, C1); T1 = _mm_add_epi64(T1, C2);
500 C1 = _mm_srli_epi64(T3, 26); T3 = _mm_and_si128(T3, MMASK); T4 = _mm_add_epi64(T4, C1);
501
502 /* H = (H*[r^2,r^2] + [Mx,My]) */
503 H0 = T0;
504 H1 = T1;
505 H2 = T2;
506 H3 = T3;
507 H4 = T4;
508
509 consumed = 32;
510 }
511
512 /* finalize, H *= [r^2,r] */
513 r0 = ((uint64_t)p->R20.d[3] << 32) | (uint64_t)p->R20.d[1];
514 r1 = ((uint64_t)p->R21.d[3] << 32) | (uint64_t)p->R21.d[1];
515 r2 = ((uint64_t)p->R22.d[3] << 32) | (uint64_t)p->R22.d[1];
516
517 p->R20.d[2] = (uint32_t)( r0 ) & 0x3ffffff;
518 p->R21.d[2] = (uint32_t)((r0 >> 26) | (r1 << 18)) & 0x3ffffff;
519 p->R22.d[2] = (uint32_t)((r1 >> 8) ) & 0x3ffffff;
520 p->R23.d[2] = (uint32_t)((r1 >> 34) | (r2 << 10)) & 0x3ffffff;
521 p->R24.d[2] = (uint32_t)((r2 >> 16) ) ;
522 p->S21.d[2] = p->R21.d[2] * 5;
523 p->S22.d[2] = p->R22.d[2] * 5;
524 p->S23.d[2] = p->R23.d[2] * 5;
525 p->S24.d[2] = p->R24.d[2] * 5;
526
527 /* H *= [r^2,r] */
528 T0 = _mm_mul_epu32(H0, p->R20.v);
529 T1 = _mm_mul_epu32(H0, p->R21.v);
530 T2 = _mm_mul_epu32(H0, p->R22.v);
531 T3 = _mm_mul_epu32(H0, p->R23.v);
532 T4 = _mm_mul_epu32(H0, p->R24.v);
533 T5 = _mm_mul_epu32(H1, p->S24.v); T6 = _mm_mul_epu32(H1, p->R20.v); T0 = _mm_add_epi64(T0, T5); T1 = _mm_add_epi64(T1, T6);
534 T5 = _mm_mul_epu32(H2, p->S23.v); T6 = _mm_mul_epu32(H2, p->S24.v); T0 = _mm_add_epi64(T0, T5); T1 = _mm_add_epi64(T1, T6);
535 T5 = _mm_mul_epu32(H3, p->S22.v); T6 = _mm_mul_epu32(H3, p->S23.v); T0 = _mm_add_epi64(T0, T5); T1 = _mm_add_epi64(T1, T6);
536 T5 = _mm_mul_epu32(H4, p->S21.v); T6 = _mm_mul_epu32(H4, p->S22.v); T0 = _mm_add_epi64(T0, T5); T1 = _mm_add_epi64(T1, T6);
537 T5 = _mm_mul_epu32(H1, p->R21.v); T6 = _mm_mul_epu32(H1, p->R22.v); T2 = _mm_add_epi64(T2, T5); T3 = _mm_add_epi64(T3, T6);
538 T5 = _mm_mul_epu32(H2, p->R20.v); T6 = _mm_mul_epu32(H2, p->R21.v); T2 = _mm_add_epi64(T2, T5); T3 = _mm_add_epi64(T3, T6);
539 T5 = _mm_mul_epu32(H3, p->S24.v); T6 = _mm_mul_epu32(H3, p->R20.v); T2 = _mm_add_epi64(T2, T5); T3 = _mm_add_epi64(T3, T6);
540 T5 = _mm_mul_epu32(H4, p->S23.v); T6 = _mm_mul_epu32(H4, p->S24.v); T2 = _mm_add_epi64(T2, T5); T3 = _mm_add_epi64(T3, T6);
541 T5 = _mm_mul_epu32(H1, p->R23.v); T4 = _mm_add_epi64(T4, T5);
542 T5 = _mm_mul_epu32(H2, p->R22.v); T4 = _mm_add_epi64(T4, T5);
543 T5 = _mm_mul_epu32(H3, p->R21.v); T4 = _mm_add_epi64(T4, T5);
544 T5 = _mm_mul_epu32(H4, p->R20.v); T4 = _mm_add_epi64(T4, T5);
545
546 C1 = _mm_srli_epi64(T0, 26); C2 = _mm_srli_epi64(T3, 26); T0 = _mm_and_si128(T0, MMASK); T3 = _mm_and_si128(T3, MMASK); T1 = _mm_add_epi64(T1, C1); T4 = _mm_add_epi64(T4, C2);
547 C1 = _mm_srli_epi64(T1, 26); C2 = _mm_srli_epi64(T4, 26); T1 = _mm_and_si128(T1, MMASK); T4 = _mm_and_si128(T4, MMASK); T2 = _mm_add_epi64(T2, C1); T0 = _mm_add_epi64(T0, _mm_mul_epu32(C2, FIVE));
548 C1 = _mm_srli_epi64(T2, 26); C2 = _mm_srli_epi64(T0, 26); T2 = _mm_and_si128(T2, MMASK); T0 = _mm_and_si128(T0, MMASK); T3 = _mm_add_epi64(T3, C1); T1 = _mm_add_epi64(T1, C2);
549 C1 = _mm_srli_epi64(T3, 26); T3 = _mm_and_si128(T3, MMASK); T4 = _mm_add_epi64(T4, C1);
550
551 /* H = H[0]+H[1] */
552 H0 = _mm_add_epi64(T0, _mm_srli_si128(T0, 8));
553 H1 = _mm_add_epi64(T1, _mm_srli_si128(T1, 8));
554 H2 = _mm_add_epi64(T2, _mm_srli_si128(T2, 8));
555 H3 = _mm_add_epi64(T3, _mm_srli_si128(T3, 8));
556 H4 = _mm_add_epi64(T4, _mm_srli_si128(T4, 8));
557
558 t0 = _mm_cvtsi128_si32(H0) ; c = (t0 >> 26); t0 &= 0x3ffffff;
559 t1 = _mm_cvtsi128_si32(H1) + c; c = (t1 >> 26); t1 &= 0x3ffffff;
560 t2 = _mm_cvtsi128_si32(H2) + c; c = (t2 >> 26); t2 &= 0x3ffffff;
561 t3 = _mm_cvtsi128_si32(H3) + c; c = (t3 >> 26); t3 &= 0x3ffffff;
562 t4 = _mm_cvtsi128_si32(H4) + c; c = (t4 >> 26); t4 &= 0x3ffffff;
563 t0 = t0 + (c * 5); c = (t0 >> 26); t0 &= 0x3ffffff;
564 t1 = t1 + c;
565
566 st->HH[0] = ((t0 ) | (t1 << 26) ) & 0xfffffffffffull;
567 st->HH[1] = ((t1 >> 18) | (t2 << 8) | (t3 << 34)) & 0xfffffffffffull;
568 st->HH[2] = ((t3 >> 10) | (t4 << 16) ) & 0x3ffffffffffull;
569
570 return consumed;
571 }
572
573 void
CRYPTO_poly1305_update(poly1305_state * state,const unsigned char * m,size_t bytes)574 CRYPTO_poly1305_update(poly1305_state *state, const unsigned char *m,
575 size_t bytes)
576 {
577 poly1305_state_internal *st = poly1305_aligned_state(state);
578 size_t want;
579
580 /* need at least 32 initial bytes to start the accelerated branch */
581 if (!st->started)
582 {
583 if ((st->leftover == 0) && (bytes > 32))
584 {
585 poly1305_first_block(st, m);
586 m += 32;
587 bytes -= 32;
588 }
589 else
590 {
591 want = poly1305_min(32 - st->leftover, bytes);
592 poly1305_block_copy(st->buffer + st->leftover, m, want);
593 bytes -= want;
594 m += want;
595 st->leftover += want;
596 if ((st->leftover < 32) || (bytes == 0))
597 return;
598 poly1305_first_block(st, st->buffer);
599 st->leftover = 0;
600 }
601 st->started = 1;
602 }
603
604 /* handle leftover */
605 if (st->leftover)
606 {
607 want = poly1305_min(64 - st->leftover, bytes);
608 poly1305_block_copy(st->buffer + st->leftover, m, want);
609 bytes -= want;
610 m += want;
611 st->leftover += want;
612 if (st->leftover < 64)
613 return;
614 poly1305_blocks(st, st->buffer, 64);
615 st->leftover = 0;
616 }
617
618 /* process 64 byte blocks */
619 if (bytes >= 64)
620 {
621 want = (bytes & ~63);
622 poly1305_blocks(st, m, want);
623 m += want;
624 bytes -= want;
625 }
626
627 if (bytes)
628 {
629 poly1305_block_copy(st->buffer + st->leftover, m, bytes);
630 st->leftover += bytes;
631 }
632 }
633
634 void
CRYPTO_poly1305_finish(poly1305_state * state,unsigned char mac[16])635 CRYPTO_poly1305_finish(poly1305_state *state, unsigned char mac[16])
636 {
637 poly1305_state_internal *st = poly1305_aligned_state(state);
638 size_t leftover = st->leftover;
639 uint8_t *m = st->buffer;
640 uint128_t d[3];
641 uint64_t h0,h1,h2;
642 uint64_t t0,t1;
643 uint64_t g0,g1,g2,c,nc;
644 uint64_t r0,r1,r2,s1,s2;
645 poly1305_power *p;
646
647 if (st->started)
648 {
649 size_t consumed = poly1305_combine(st, m, leftover);
650 leftover -= consumed;
651 m += consumed;
652 }
653
654 /* st->HH will either be 0 or have the combined result */
655 h0 = st->HH[0];
656 h1 = st->HH[1];
657 h2 = st->HH[2];
658
659 p = &st->P[1];
660 r0 = ((uint64_t)p->R20.d[3] << 32) | (uint64_t)p->R20.d[1];
661 r1 = ((uint64_t)p->R21.d[3] << 32) | (uint64_t)p->R21.d[1];
662 r2 = ((uint64_t)p->R22.d[3] << 32) | (uint64_t)p->R22.d[1];
663 s1 = r1 * (5 << 2);
664 s2 = r2 * (5 << 2);
665
666 if (leftover < 16)
667 goto poly1305_donna_atmost15bytes;
668
669 poly1305_donna_atleast16bytes:
670 t0 = U8TO64_LE(m + 0);
671 t1 = U8TO64_LE(m + 8);
672 h0 += t0 & 0xfffffffffff;
673 t0 = shr128_pair(t1, t0, 44);
674 h1 += t0 & 0xfffffffffff;
675 h2 += (t1 >> 24) | ((uint64_t)1 << 40);
676
677 poly1305_donna_mul:
678 d[0] = add128(add128(mul64x64_128(h0, r0), mul64x64_128(h1, s2)), mul64x64_128(h2, s1));
679 d[1] = add128(add128(mul64x64_128(h0, r1), mul64x64_128(h1, r0)), mul64x64_128(h2, s2));
680 d[2] = add128(add128(mul64x64_128(h0, r2), mul64x64_128(h1, r1)), mul64x64_128(h2, r0));
681 h0 = lo128(d[0]) & 0xfffffffffff; c = shr128(d[0], 44);
682 d[1] = add128_64(d[1], c); h1 = lo128(d[1]) & 0xfffffffffff; c = shr128(d[1], 44);
683 d[2] = add128_64(d[2], c); h2 = lo128(d[2]) & 0x3ffffffffff; c = shr128(d[2], 42);
684 h0 += c * 5;
685
686 m += 16;
687 leftover -= 16;
688 if (leftover >= 16) goto poly1305_donna_atleast16bytes;
689
690 /* final bytes */
691 poly1305_donna_atmost15bytes:
692 if (!leftover) goto poly1305_donna_finish;
693
694 m[leftover++] = 1;
695 poly1305_block_zero(m + leftover, 16 - leftover);
696 leftover = 16;
697
698 t0 = U8TO64_LE(m+0);
699 t1 = U8TO64_LE(m+8);
700 h0 += t0 & 0xfffffffffff; t0 = shr128_pair(t1, t0, 44);
701 h1 += t0 & 0xfffffffffff;
702 h2 += (t1 >> 24);
703
704 goto poly1305_donna_mul;
705
706 poly1305_donna_finish:
707 c = (h0 >> 44); h0 &= 0xfffffffffff;
708 h1 += c; c = (h1 >> 44); h1 &= 0xfffffffffff;
709 h2 += c; c = (h2 >> 42); h2 &= 0x3ffffffffff;
710 h0 += c * 5;
711
712 g0 = h0 + 5; c = (g0 >> 44); g0 &= 0xfffffffffff;
713 g1 = h1 + c; c = (g1 >> 44); g1 &= 0xfffffffffff;
714 g2 = h2 + c - ((uint64_t)1 << 42);
715
716 c = (g2 >> 63) - 1;
717 nc = ~c;
718 h0 = (h0 & nc) | (g0 & c);
719 h1 = (h1 & nc) | (g1 & c);
720 h2 = (h2 & nc) | (g2 & c);
721
722 /* pad */
723 t0 = ((uint64_t)p->R23.d[3] << 32) | (uint64_t)p->R23.d[1];
724 t1 = ((uint64_t)p->R24.d[3] << 32) | (uint64_t)p->R24.d[1];
725 h0 += (t0 & 0xfffffffffff) ; c = (h0 >> 44); h0 &= 0xfffffffffff; t0 = shr128_pair(t1, t0, 44);
726 h1 += (t0 & 0xfffffffffff) + c; c = (h1 >> 44); h1 &= 0xfffffffffff; t1 = (t1 >> 24);
727 h2 += (t1 ) + c;
728
729 U64TO8_LE(mac + 0, ((h0 ) | (h1 << 44)));
730 U64TO8_LE(mac + 8, ((h1 >> 20) | (h2 << 24)));
731 }
732
733 #endif /* !OPENSSL_NO_POLY1305 */
734