poly1305_native.c (19359B)
1 #include <stddef.h> 2 #include <stdint.h> 3 #include <string.h> 4 5 #if defined(__aarch64__) 6 #include <arm_neon.h> 7 #elif defined(__x86_64__) 8 #include <cpuid.h> 9 #include <immintrin.h> 10 #endif 11 12 #if defined(__aarch64__) || defined(__x86_64__) 13 14 /* 15 * Poly1305 (RFC 8439), via two paths: 16 * 17 * 1. A portable scalar 26-bit-limb kernel using 64-bit native 18 * arithmetic for the limb multiplications, compiled on both 19 * aarch64 and x86_64. Used for setup (precomputing r^k), 20 * for messages shorter than 64 bytes, and for the < 4-block tail 21 * of longer messages. Also serves as the stage-1 reference; the 22 * NEON kernel below was added in a separate commit. 23 * 24 * 2. A 4-way parallel kernel (when at least 4 full blocks remain). 25 * On aarch64 it uses NEON: 5 'uint32x4_t' limb vectors hold one 26 * limb position each across 4 message blocks; matching r-power 27 * vectors hold (r^4, r^3, r^2, r^1) at the same limb position. 28 * For each output position d_j we accumulate 5 partial products 29 * across both vector halves with 'vmull'/'vmlal', then 30 * horizontally sum the 4 lanes with 'vaddvq_u64'. The same 31 * carry-propagation pattern as the scalar path reduces back to 32 * 26-bit limbs. 33 * 34 * On x86_64 it uses AVX2, where the CPU supports it, with the 35 * same structure: one '__m256i' per limb position, one 64-bit 36 * lane per block, and '_mm256_mul_epu32' in place of 37 * 'vmull'/'vmlal'. 38 * 39 * Reduction rule (used in both paths): 2^130 = 5 (mod 2^130 - 5), 40 * so any partial product whose 'position' exceeds 4 folds back as 41 * (5 * value) into position (pos - 5). 42 */ 43 44 #define MASK26 0x3ffffffu 45 46 /* 47 * Multiply two 130-bit values mod (2^130 - 5). Inputs in 5x 26-bit 48 * limb form, output in 5x 26-bit limb form (each output limb < 2^26 49 * except possibly limb 1, which may carry a small excess absorbed 50 * by the next 'mul_mod_p' or by 'normalize'). 51 */ 52 static void mul_mod_p(const uint32_t a[5], const uint32_t b[5], 53 uint32_t out[5]) { 54 uint64_t d0, d1, d2, d3, d4, c; 55 56 d0 = (uint64_t)a[0]*b[0] 57 + 5 * ((uint64_t)a[4]*b[1] + (uint64_t)a[3]*b[2] 58 + (uint64_t)a[2]*b[3] + (uint64_t)a[1]*b[4]); 59 d1 = (uint64_t)a[0]*b[1] + (uint64_t)a[1]*b[0] 60 + 5 * ((uint64_t)a[4]*b[2] + (uint64_t)a[3]*b[3] 61 + (uint64_t)a[2]*b[4]); 62 d2 = (uint64_t)a[0]*b[2] + (uint64_t)a[1]*b[1] 63 + (uint64_t)a[2]*b[0] 64 + 5 * ((uint64_t)a[4]*b[3] + (uint64_t)a[3]*b[4]); 65 d3 = (uint64_t)a[0]*b[3] + (uint64_t)a[1]*b[2] 66 + (uint64_t)a[2]*b[1] + (uint64_t)a[3]*b[0] 67 + 5 * ((uint64_t)a[4]*b[4]); 68 d4 = (uint64_t)a[0]*b[4] + (uint64_t)a[1]*b[3] 69 + (uint64_t)a[2]*b[2] + (uint64_t)a[3]*b[1] 70 + (uint64_t)a[4]*b[0]; 71 72 c = d0 >> 26; d0 &= MASK26; d1 += c; 73 c = d1 >> 26; d1 &= MASK26; d2 += c; 74 c = d2 >> 26; d2 &= MASK26; d3 += c; 75 c = d3 >> 26; d3 &= MASK26; d4 += c; 76 c = d4 >> 26; d4 &= MASK26; d0 += c * 5; 77 c = d0 >> 26; d0 &= MASK26; d1 += c; 78 79 out[0] = (uint32_t)d0; 80 out[1] = (uint32_t)d1; 81 out[2] = (uint32_t)d2; 82 out[3] = (uint32_t)d3; 83 out[4] = (uint32_t)d4; 84 } 85 86 /* 87 * Parse 16 little-endian bytes plus a 'hibit' value (0 or 1) at bit 88 * 128 into 5 26-bit limbs. 89 */ 90 static inline void blk2limbs(const uint8_t m[16], uint32_t hibit, 91 uint32_t l[5]) { 92 uint32_t t0, t1, t2, t3; 93 memcpy(&t0, m, 4); 94 memcpy(&t1, m + 4, 4); 95 memcpy(&t2, m + 8, 4); 96 memcpy(&t3, m + 12, 4); 97 l[0] = t0 & MASK26; 98 l[1] = ((t0 >> 26) | (t1 << 6)) & MASK26; 99 l[2] = ((t1 >> 20) | (t2 << 12)) & MASK26; 100 l[3] = ((t2 >> 14) | (t3 << 18)) & MASK26; 101 l[4] = (t3 >> 8) | (hibit << 24); 102 } 103 104 /* 105 * Process one full 16-byte block: h := (h + m) * r mod p, scalar 106 * implementation. 107 */ 108 static inline void scalar_block(uint32_t h[5], const uint32_t r[5], 109 const uint8_t m[16], uint32_t hibit) { 110 uint32_t blk[5]; 111 blk2limbs(m, hibit, blk); 112 113 uint32_t hl[5]; 114 hl[0] = h[0] + blk[0]; 115 hl[1] = h[1] + blk[1]; 116 hl[2] = h[2] + blk[2]; 117 hl[3] = h[3] + blk[3]; 118 hl[4] = h[4] + blk[4]; 119 120 mul_mod_p(hl, r, h); 121 } 122 123 #if defined(__aarch64__) 124 125 /* 126 * 4-block NEON update. Computes: 127 * h := (h + m_0)*r^4 + m_1*r^3 + m_2*r^2 + m_3*r^1 mod p 128 * 129 * where m_0..m_3 are four consecutive 16-byte input blocks (so the 130 * function consumes 64 bytes). The polynomial identity is the 131 * standard Horner expansion of 4 sequential block updates. 132 */ 133 static void neon4_block(uint32_t h[5], 134 const uint32_t r1[5], const uint32_t r2[5], 135 const uint32_t r3[5], const uint32_t r4[5], 136 const uint8_t m[64]) { 137 /* Limbify the four blocks. */ 138 uint32_t b0[5], b1[5], b2[5], b3[5]; 139 blk2limbs(m, 1, b0); 140 blk2limbs(m + 16, 1, b1); 141 blk2limbs(m + 32, 1, b2); 142 blk2limbs(m + 48, 1, b3); 143 144 /* Fold the running accumulator into the first block. */ 145 b0[0] += h[0]; b0[1] += h[1]; b0[2] += h[2]; 146 b0[3] += h[3]; b0[4] += h[4]; 147 148 /* Pack messages: mv[i] = (b0[i], b1[i], b2[i], b3[i]). */ 149 uint32x4_t mv0 = { b0[0], b1[0], b2[0], b3[0] }; 150 uint32x4_t mv1 = { b0[1], b1[1], b2[1], b3[1] }; 151 uint32x4_t mv2 = { b0[2], b1[2], b2[2], b3[2] }; 152 uint32x4_t mv3 = { b0[3], b1[3], b2[3], b3[3] }; 153 uint32x4_t mv4 = { b0[4], b1[4], b2[4], b3[4] }; 154 155 /* Pack r-powers: rv[i] = (r^4[i], r^3[i], r^2[i], r^1[i]). */ 156 uint32x4_t rv0 = { r4[0], r3[0], r2[0], r1[0] }; 157 uint32x4_t rv1 = { r4[1], r3[1], r2[1], r1[1] }; 158 uint32x4_t rv2 = { r4[2], r3[2], r2[2], r1[2] }; 159 uint32x4_t rv3 = { r4[3], r3[3], r2[3], r1[3] }; 160 uint32x4_t rv4 = { r4[4], r3[4], r2[4], r1[4] }; 161 162 /* 5 * r-powers, for partial products whose position wraps past 163 * 4 (mod 2^130 - 5 = 5). */ 164 uint32x4_t rv1_5 = vaddq_u32(vshlq_n_u32(rv1, 2), rv1); 165 uint32x4_t rv2_5 = vaddq_u32(vshlq_n_u32(rv2, 2), rv2); 166 uint32x4_t rv3_5 = vaddq_u32(vshlq_n_u32(rv3, 2), rv3); 167 uint32x4_t rv4_5 = vaddq_u32(vshlq_n_u32(rv4, 2), rv4); 168 169 /* 170 * Output limb j = sum_i (mv[i] * appropriate r-power for shift j-i, 171 * with 5x multiplier when j - i is negative). Per output we sum 172 * across the 4 lanes ('vaddvq_u64') after collecting both vmull 173 * halves. 174 */ 175 #define MUL5_LO(m_, r_) vmull_u32(vget_low_u32(m_), vget_low_u32(r_)) 176 #define MUL5_HI(m_, r_) vmull_high_u32(m_, r_) 177 #define MLA_LO(acc, m_, r_) \ 178 vmlal_u32(acc, vget_low_u32(m_), vget_low_u32(r_)) 179 #define MLA_HI(acc, m_, r_) vmlal_high_u32(acc, m_, r_) 180 181 uint64x2_t l0 = MUL5_LO(mv0, rv0); 182 uint64x2_t h0 = MUL5_HI(mv0, rv0); 183 l0 = MLA_LO(l0, mv1, rv4_5); h0 = MLA_HI(h0, mv1, rv4_5); 184 l0 = MLA_LO(l0, mv2, rv3_5); h0 = MLA_HI(h0, mv2, rv3_5); 185 l0 = MLA_LO(l0, mv3, rv2_5); h0 = MLA_HI(h0, mv3, rv2_5); 186 l0 = MLA_LO(l0, mv4, rv1_5); h0 = MLA_HI(h0, mv4, rv1_5); 187 uint64_t d0 = vaddvq_u64(l0) + vaddvq_u64(h0); 188 189 uint64x2_t l1 = MUL5_LO(mv0, rv1); 190 uint64x2_t h1 = MUL5_HI(mv0, rv1); 191 l1 = MLA_LO(l1, mv1, rv0 ); h1 = MLA_HI(h1, mv1, rv0 ); 192 l1 = MLA_LO(l1, mv2, rv4_5); h1 = MLA_HI(h1, mv2, rv4_5); 193 l1 = MLA_LO(l1, mv3, rv3_5); h1 = MLA_HI(h1, mv3, rv3_5); 194 l1 = MLA_LO(l1, mv4, rv2_5); h1 = MLA_HI(h1, mv4, rv2_5); 195 uint64_t d1 = vaddvq_u64(l1) + vaddvq_u64(h1); 196 197 uint64x2_t l2 = MUL5_LO(mv0, rv2); 198 uint64x2_t h2 = MUL5_HI(mv0, rv2); 199 l2 = MLA_LO(l2, mv1, rv1 ); h2 = MLA_HI(h2, mv1, rv1 ); 200 l2 = MLA_LO(l2, mv2, rv0 ); h2 = MLA_HI(h2, mv2, rv0 ); 201 l2 = MLA_LO(l2, mv3, rv4_5); h2 = MLA_HI(h2, mv3, rv4_5); 202 l2 = MLA_LO(l2, mv4, rv3_5); h2 = MLA_HI(h2, mv4, rv3_5); 203 uint64_t d2 = vaddvq_u64(l2) + vaddvq_u64(h2); 204 205 uint64x2_t l3 = MUL5_LO(mv0, rv3); 206 uint64x2_t h3 = MUL5_HI(mv0, rv3); 207 l3 = MLA_LO(l3, mv1, rv2 ); h3 = MLA_HI(h3, mv1, rv2 ); 208 l3 = MLA_LO(l3, mv2, rv1 ); h3 = MLA_HI(h3, mv2, rv1 ); 209 l3 = MLA_LO(l3, mv3, rv0 ); h3 = MLA_HI(h3, mv3, rv0 ); 210 l3 = MLA_LO(l3, mv4, rv4_5); h3 = MLA_HI(h3, mv4, rv4_5); 211 uint64_t d3 = vaddvq_u64(l3) + vaddvq_u64(h3); 212 213 uint64x2_t l4 = MUL5_LO(mv0, rv4); 214 uint64x2_t h4 = MUL5_HI(mv0, rv4); 215 l4 = MLA_LO(l4, mv1, rv3); h4 = MLA_HI(h4, mv1, rv3); 216 l4 = MLA_LO(l4, mv2, rv2); h4 = MLA_HI(h4, mv2, rv2); 217 l4 = MLA_LO(l4, mv3, rv1); h4 = MLA_HI(h4, mv3, rv1); 218 l4 = MLA_LO(l4, mv4, rv0); h4 = MLA_HI(h4, mv4, rv0); 219 uint64_t d4 = vaddvq_u64(l4) + vaddvq_u64(h4); 220 221 #undef MUL5_LO 222 #undef MUL5_HI 223 #undef MLA_LO 224 #undef MLA_HI 225 226 /* Carry propagation, same shape as 'mul_mod_p'. */ 227 uint64_t c; 228 c = d0 >> 26; d0 &= MASK26; d1 += c; 229 c = d1 >> 26; d1 &= MASK26; d2 += c; 230 c = d2 >> 26; d2 &= MASK26; d3 += c; 231 c = d3 >> 26; d3 &= MASK26; d4 += c; 232 c = d4 >> 26; d4 &= MASK26; d0 += c * 5; 233 c = d0 >> 26; d0 &= MASK26; d1 += c; 234 235 h[0] = (uint32_t)d0; 236 h[1] = (uint32_t)d1; 237 h[2] = (uint32_t)d2; 238 h[3] = (uint32_t)d3; 239 h[4] = (uint32_t)d4; 240 } 241 242 #elif defined(__x86_64__) 243 244 /* 245 * Return 1 if the CPU implements AVX2 and the OS preserves the YMM 246 * registers across context switches, 0 otherwise. 247 */ 248 static int avx2_supported(void) { 249 unsigned int eax, ebx, ecx, edx, xcr0_lo, xcr0_hi; 250 if (!__get_cpuid(1, &eax, &ebx, &ecx, &edx)) 251 return 0; 252 if (!(ecx & bit_OSXSAVE) || !(ecx & bit_AVX)) 253 return 0; 254 /* XCR0 bits 1 and 2: XMM and YMM state enabled by the OS */ 255 __asm__("xgetbv" : "=a"(xcr0_lo), "=d"(xcr0_hi) : "c"(0)); 256 if ((xcr0_lo & 6) != 6) 257 return 0; 258 if (!__get_cpuid_count(7, 0, &eax, &ebx, &ecx, &edx)) 259 return 0; 260 return (ebx & bit_AVX2) != 0; 261 } 262 263 /* 264 * 'avx2_supported', computed once. CPUID is slow, and may trap to 265 * the hypervisor under virtualisation. Racing first calls store the 266 * same value, so relaxed atomics suffice. 267 */ 268 static int have_avx2(void) { 269 static int cached = -1; 270 int v = __atomic_load_n(&cached, __ATOMIC_RELAXED); 271 if (v < 0) { 272 v = avx2_supported(); 273 __atomic_store_n(&cached, v, __ATOMIC_RELAXED); 274 } 275 return v; 276 } 277 278 /* Sum the four 64-bit lanes of 'v'. */ 279 __attribute__((target("avx2"))) 280 static inline uint64_t hsum4(__m256i v) { 281 __m128i s = _mm_add_epi64(_mm256_castsi256_si128(v), 282 _mm256_extracti128_si256(v, 1)); 283 s = _mm_add_epi64(s, _mm_unpackhi_epi64(s, s)); 284 return (uint64_t)_mm_cvtsi128_si64(s); 285 } 286 287 /* 288 * AVX2 4-block update, computing the same thing as the NEON kernel: 289 * 290 * h := (h + m_0)*r^4 + m_1*r^3 + m_2*r^2 + m_3*r^1 mod p 291 * 292 * for each successive 64-byte group of 'msg', while 'msglen' allows. 293 * Returns the number of bytes consumed. 294 * 295 * Each '__m256i' holds one limb position across four blocks, one limb 296 * per 64-bit lane. '_mm256_mul_epu32' multiplies the low 32 bits of 297 * each lane into a 64-bit product, so it plays the role of NEON's 298 * 'vmull'/'vmlal' pairs, with a single vector covering all 4 lanes. 299 * 300 * Compiled for AVX2 only; callers must first check 'have_avx2'. 301 */ 302 __attribute__((target("avx2"))) 303 static size_t avx2_blocks(uint32_t h[5], 304 const uint32_t r1[5], const uint32_t r2[5], 305 const uint32_t r3[5], const uint32_t r4[5], 306 const uint8_t *msg, size_t msglen) { 307 /* rv[i] = (r^4[i], r^3[i], r^2[i], r^1[i]), lowest lane first. */ 308 __m256i rv0 = _mm256_setr_epi64x(r4[0], r3[0], r2[0], r1[0]); 309 __m256i rv1 = _mm256_setr_epi64x(r4[1], r3[1], r2[1], r1[1]); 310 __m256i rv2 = _mm256_setr_epi64x(r4[2], r3[2], r2[2], r1[2]); 311 __m256i rv3 = _mm256_setr_epi64x(r4[3], r3[3], r2[3], r1[3]); 312 __m256i rv4 = _mm256_setr_epi64x(r4[4], r3[4], r2[4], r1[4]); 313 314 /* 5 * r-powers, for partial products whose position wraps past 315 * 4 (mod 2^130 - 5 = 5). */ 316 __m256i rv1_5 = _mm256_add_epi64(_mm256_slli_epi64(rv1, 2), rv1); 317 __m256i rv2_5 = _mm256_add_epi64(_mm256_slli_epi64(rv2, 2), rv2); 318 __m256i rv3_5 = _mm256_add_epi64(_mm256_slli_epi64(rv3, 2), rv3); 319 __m256i rv4_5 = _mm256_add_epi64(_mm256_slli_epi64(rv4, 2), rv4); 320 321 size_t pos = 0; 322 while (pos + 64 <= msglen) { 323 const uint8_t *m = msg + pos; 324 325 /* Limbify the four blocks. */ 326 uint32_t b0[5], b1[5], b2[5], b3[5]; 327 blk2limbs(m, 1, b0); 328 blk2limbs(m + 16, 1, b1); 329 blk2limbs(m + 32, 1, b2); 330 blk2limbs(m + 48, 1, b3); 331 332 /* Fold the running accumulator into the first block. */ 333 b0[0] += h[0]; b0[1] += h[1]; b0[2] += h[2]; 334 b0[3] += h[3]; b0[4] += h[4]; 335 336 /* mv[i] = (b0[i], b1[i], b2[i], b3[i]), lowest lane first. */ 337 __m256i mv0 = _mm256_setr_epi64x(b0[0], b1[0], b2[0], b3[0]); 338 __m256i mv1 = _mm256_setr_epi64x(b0[1], b1[1], b2[1], b3[1]); 339 __m256i mv2 = _mm256_setr_epi64x(b0[2], b1[2], b2[2], b3[2]); 340 __m256i mv3 = _mm256_setr_epi64x(b0[3], b1[3], b2[3], b3[3]); 341 __m256i mv4 = _mm256_setr_epi64x(b0[4], b1[4], b2[4], b3[4]); 342 343 #define MUL(m_, r_) _mm256_mul_epu32(m_, r_) 344 #define MLA(acc, m_, r_) _mm256_add_epi64(acc, _mm256_mul_epu32(m_, r_)) 345 346 __m256i t; 347 348 t = MUL(mv0, rv0); 349 t = MLA(t, mv1, rv4_5); 350 t = MLA(t, mv2, rv3_5); 351 t = MLA(t, mv3, rv2_5); 352 t = MLA(t, mv4, rv1_5); 353 uint64_t d0 = hsum4(t); 354 355 t = MUL(mv0, rv1); 356 t = MLA(t, mv1, rv0); 357 t = MLA(t, mv2, rv4_5); 358 t = MLA(t, mv3, rv3_5); 359 t = MLA(t, mv4, rv2_5); 360 uint64_t d1 = hsum4(t); 361 362 t = MUL(mv0, rv2); 363 t = MLA(t, mv1, rv1); 364 t = MLA(t, mv2, rv0); 365 t = MLA(t, mv3, rv4_5); 366 t = MLA(t, mv4, rv3_5); 367 uint64_t d2 = hsum4(t); 368 369 t = MUL(mv0, rv3); 370 t = MLA(t, mv1, rv2); 371 t = MLA(t, mv2, rv1); 372 t = MLA(t, mv3, rv0); 373 t = MLA(t, mv4, rv4_5); 374 uint64_t d3 = hsum4(t); 375 376 t = MUL(mv0, rv4); 377 t = MLA(t, mv1, rv3); 378 t = MLA(t, mv2, rv2); 379 t = MLA(t, mv3, rv1); 380 t = MLA(t, mv4, rv0); 381 uint64_t d4 = hsum4(t); 382 383 #undef MUL 384 #undef MLA 385 386 /* Carry propagation, same shape as 'mul_mod_p'. */ 387 uint64_t c; 388 c = d0 >> 26; d0 &= MASK26; d1 += c; 389 c = d1 >> 26; d1 &= MASK26; d2 += c; 390 c = d2 >> 26; d2 &= MASK26; d3 += c; 391 c = d3 >> 26; d3 &= MASK26; d4 += c; 392 c = d4 >> 26; d4 &= MASK26; d0 += c * 5; 393 c = d0 >> 26; d0 &= MASK26; d1 += c; 394 395 h[0] = (uint32_t)d0; 396 h[1] = (uint32_t)d1; 397 h[2] = (uint32_t)d2; 398 h[3] = (uint32_t)d3; 399 h[4] = (uint32_t)d4; 400 401 pos += 64; 402 } 403 return pos; 404 } 405 406 #endif 407 408 /* 409 * Compute a 16-byte Poly1305 MAC over 'msg' (length 'msglen') using 410 * the 32-byte 'key'. Writes the tag to 'mac_out'. 411 */ 412 void poly1305_mac_native(const uint8_t key[32], const uint8_t *msg, 413 size_t msglen, uint8_t mac_out[16]) { 414 /* clamp r */ 415 uint32_t t0, t1, t2, t3; 416 memcpy(&t0, key, 4); 417 memcpy(&t1, key + 4, 4); 418 memcpy(&t2, key + 8, 4); 419 memcpy(&t3, key + 12, 4); 420 t0 &= 0x0fffffffu; 421 t1 &= 0x0ffffffcu; 422 t2 &= 0x0ffffffcu; 423 t3 &= 0x0ffffffcu; 424 425 uint32_t r[5]; 426 r[0] = t0 & MASK26; 427 r[1] = ((t0 >> 26) | (t1 << 6)) & MASK26; 428 r[2] = ((t1 >> 20) | (t2 << 12)) & MASK26; 429 r[3] = ((t2 >> 14) | (t3 << 18)) & MASK26; 430 r[4] = (t3 >> 8); 431 432 uint32_t h[5] = { 0, 0, 0, 0, 0 }; 433 434 size_t pos = 0; 435 436 #if defined(__aarch64__) 437 /* NEON 4-way path: amortizing the r^2/r^3/r^4 precomputation 438 * (3 scalar mul_mod_p calls) needs about 4 NEON iterations to 439 * break even versus the scalar block loop, so only engage it 440 * when we have at least 16 full blocks (256 bytes). */ 441 if (msglen >= 256) { 442 uint32_t r2[5], r3[5], r4[5]; 443 mul_mod_p(r, r, r2); 444 mul_mod_p(r2, r, r3); 445 mul_mod_p(r3, r, r4); 446 447 while (pos + 64 <= msglen) { 448 neon4_block(h, r, r2, r3, r4, msg + pos); 449 pos += 64; 450 } 451 } 452 #elif defined(__x86_64__) 453 /* AVX2 4-way path, where the CPU supports it. The scalar kernel 454 * is slower here relative to the r^2/r^3/r^4 precomputation than 455 * on aarch64, so two AVX2 iterations (128 bytes) already break 456 * even. */ 457 if (msglen >= 128 && have_avx2()) { 458 uint32_t r2[5], r3[5], r4[5]; 459 mul_mod_p(r, r, r2); 460 mul_mod_p(r2, r, r3); 461 mul_mod_p(r3, r, r4); 462 463 pos = avx2_blocks(h, r, r2, r3, r4, msg, msglen); 464 } 465 #endif 466 467 /* Scalar tail: any remaining full blocks (< 4 of them). */ 468 while (pos + 16 <= msglen) { 469 scalar_block(h, r, msg + pos, 1); 470 pos += 16; 471 } 472 473 /* Final partial block (1..15 trailing bytes), if any. */ 474 if (pos < msglen) { 475 size_t rem = msglen - pos; 476 uint8_t pad[16] = { 0 }; 477 memcpy(pad, msg + pos, rem); 478 pad[rem] = 1; 479 scalar_block(h, r, pad, 0); 480 } 481 482 /* normalize h (mul_mod_p may leave a small excess in h[1]) */ 483 { 484 uint32_t c; 485 c = h[1] >> 26; h[1] &= MASK26; h[2] += c; 486 c = h[2] >> 26; h[2] &= MASK26; h[3] += c; 487 c = h[3] >> 26; h[3] &= MASK26; h[4] += c; 488 c = h[4] >> 26; h[4] &= MASK26; h[0] += c * 5; 489 c = h[0] >> 26; h[0] &= MASK26; h[1] += c; 490 } 491 492 /* full reduction to [0, p) via constant-time conditional 493 * subtraction of p */ 494 uint32_t g[5]; 495 uint32_t c = 5; 496 g[0] = h[0] + c; c = g[0] >> 26; g[0] &= MASK26; 497 g[1] = h[1] + c; c = g[1] >> 26; g[1] &= MASK26; 498 g[2] = h[2] + c; c = g[2] >> 26; g[2] &= MASK26; 499 g[3] = h[3] + c; c = g[3] >> 26; g[3] &= MASK26; 500 g[4] = h[4] + c; 501 uint32_t carry = g[4] >> 26; 502 g[4] &= MASK26; 503 uint32_t mask = (uint32_t)0 - carry; 504 h[0] = (h[0] & ~mask) | (g[0] & mask); 505 h[1] = (h[1] & ~mask) | (g[1] & mask); 506 h[2] = (h[2] & ~mask) | (g[2] & mask); 507 h[3] = (h[3] & ~mask) | (g[3] & mask); 508 h[4] = (h[4] & ~mask) | (g[4] & mask); 509 510 /* repack 5x 26-bit limbs into 4x 32-bit limbs */ 511 uint32_t h0 = h[0] | (h[1] << 26); 512 uint32_t h1 = (h[1] >> 6) | (h[2] << 20); 513 uint32_t h2 = (h[2] >> 12) | (h[3] << 14); 514 uint32_t h3 = (h[3] >> 18) | (h[4] << 8); 515 516 /* add s (high 16 bytes of key), mod 2^128 */ 517 uint32_t s0, s1, s2, s3; 518 memcpy(&s0, key + 16, 4); 519 memcpy(&s1, key + 20, 4); 520 memcpy(&s2, key + 24, 4); 521 memcpy(&s3, key + 28, 4); 522 523 uint64_t a0 = (uint64_t)h0 + s0; 524 uint64_t a1 = (uint64_t)h1 + s1 + (a0 >> 32); 525 uint64_t a2 = (uint64_t)h2 + s2 + (a1 >> 32); 526 uint64_t a3 = (uint64_t)h3 + s3 + (a2 >> 32); 527 528 uint32_t o0 = (uint32_t)a0; 529 uint32_t o1 = (uint32_t)a1; 530 uint32_t o2 = (uint32_t)a2; 531 uint32_t o3 = (uint32_t)a3; 532 533 memcpy(mac_out + 0, &o0, 4); 534 memcpy(mac_out + 4, &o1, 4); 535 memcpy(mac_out + 8, &o2, 4); 536 memcpy(mac_out + 12, &o3, 4); 537 } 538 539 int poly1305_native_available(void) { 540 return 1; 541 } 542 543 #else 544 545 void poly1305_mac_native(const uint8_t *key, const uint8_t *msg, 546 size_t msglen, uint8_t *mac_out) { 547 (void)key; (void)msg; (void)msglen; (void)mac_out; 548 } 549 550 int poly1305_native_available(void) { 551 return 0; 552 } 553 554 #endif