Line data    Source code

       1             : 
       2             : // Source originally from https://github.com/BLAKE3-team/BLAKE3
       3             : // From commit: 2dd4e57f68d85f3983b1880b66250fc7bdf0b7c8
       4             : 
       5             : #include "blake3_impl.h"
       6             : 
       7             : #include <immintrin.h>
       8             : 
       9             : #pragma GCC diagnostic ignored "-Wsign-conversion"
      10             : 
      11     3306596 : #define DEGREE 4
      12             : 
      13             : #define _mm_shuffle_ps2(a, b, c)                                               \
      14   831599360 :   (_mm_castps_si128(                                                           \
      15   831599360 :       _mm_shuffle_ps(_mm_castsi128_ps(a), _mm_castsi128_ps(b), (c))))
      16             : 
      17   381788192 : INLINE __m128i loadu(const uint8_t src[16]) {
      18   381788192 :   return _mm_loadu_si128((const __m128i *)src);
      19   381788192 : }
      20             : 
      21   139996608 : INLINE void storeu(__m128i src, uint8_t dest[16]) {
      22   139996608 :   _mm_storeu_si128((__m128i *)dest, src);
      23   139996608 : }
      24             : 
      25  5122094208 : INLINE __m128i addv(__m128i a, __m128i b) { return _mm_add_epi32(a, b); }
      26             : 
      27             : // Note that clang-format doesn't like the name "xor" for some reason.
      28  5277977856 : INLINE __m128i xorv(__m128i a, __m128i b) { return _mm_xor_si128(a, b); }
      29             : 
      30    15621192 : INLINE __m128i set1(uint32_t x) { return _mm_set1_epi32((int32_t)x); }
      31             : 
      32   103949920 : INLINE __m128i set4(uint32_t a, uint32_t b, uint32_t c, uint32_t d) {
      33   103949920 :   return _mm_setr_epi32((int32_t)a, (int32_t)b, (int32_t)c, (int32_t)d);
      34   103949920 : }
      35             : 
      36   853682368 : INLINE __m128i rot16(__m128i x) {
      37   853682368 :   return _mm_shuffle_epi8(
      38   853682368 :       x, _mm_set_epi8(13, 12, 15, 14, 9, 8, 11, 10, 5, 4, 7, 6, 1, 0, 3, 2));
      39   853682368 : }
      40             : 
      41   853682368 : INLINE __m128i rot12(__m128i x) {
      42   853682368 :   return xorv(_mm_srli_epi32(x, 12), _mm_slli_epi32(x, 32 - 12));
      43   853682368 : }
      44             : 
      45   853682368 : INLINE __m128i rot8(__m128i x) {
      46   853682368 :   return _mm_shuffle_epi8(
      47   853682368 :       x, _mm_set_epi8(12, 15, 14, 13, 8, 11, 10, 9, 4, 7, 6, 5, 0, 3, 2, 1));
      48   853682368 : }
      49             : 
      50   853682368 : INLINE __m128i rot7(__m128i x) {
      51   853682368 :   return xorv(_mm_srli_epi32(x, 7), _mm_slli_epi32(x, 32 - 7));
      52   853682368 : }
      53             : 
      54             : INLINE void g1(__m128i *row0, __m128i *row1, __m128i *row2, __m128i *row3,
      55   727649440 :                __m128i m) {
      56   727649440 :   *row0 = addv(addv(*row0, m), *row1);
      57   727649440 :   *row3 = xorv(*row3, *row0);
      58   727649440 :   *row3 = rot16(*row3);
      59   727649440 :   *row2 = addv(*row2, *row3);
      60   727649440 :   *row1 = xorv(*row1, *row2);
      61   727649440 :   *row1 = rot12(*row1);
      62   727649440 : }
      63             : 
      64             : INLINE void g2(__m128i *row0, __m128i *row1, __m128i *row2, __m128i *row3,
      65   727649440 :                __m128i m) {
      66   727649440 :   *row0 = addv(addv(*row0, m), *row1);
      67   727649440 :   *row3 = xorv(*row3, *row0);
      68   727649440 :   *row3 = rot8(*row3);
      69   727649440 :   *row2 = addv(*row2, *row3);
      70   727649440 :   *row1 = xorv(*row1, *row2);
      71   727649440 :   *row1 = rot7(*row1);
      72   727649440 : }
      73             : 
      74             : // Note the optimization here of leaving row1 as the unrotated row, rather than
      75             : // row0. All the message loads below are adjusted to compensate for this. See
      76             : // discussion at https://github.com/sneves/blake2-avx2/pull/4
      77   363824720 : INLINE void diagonalize(__m128i *row0, __m128i *row2, __m128i *row3) {
      78   363824720 :   *row0 = _mm_shuffle_epi32(*row0, _MM_SHUFFLE(2, 1, 0, 3));
      79   363824720 :   *row3 = _mm_shuffle_epi32(*row3, _MM_SHUFFLE(1, 0, 3, 2));
      80   363824720 :   *row2 = _mm_shuffle_epi32(*row2, _MM_SHUFFLE(0, 3, 2, 1));
      81   363824720 : }
      82             : 
      83   363824720 : INLINE void undiagonalize(__m128i *row0, __m128i *row2, __m128i *row3) {
      84   363824720 :   *row0 = _mm_shuffle_epi32(*row0, _MM_SHUFFLE(0, 3, 2, 1));
      85   363824720 :   *row3 = _mm_shuffle_epi32(*row3, _MM_SHUFFLE(1, 0, 3, 2));
      86   363824720 :   *row2 = _mm_shuffle_epi32(*row2, _MM_SHUFFLE(2, 1, 0, 3));
      87   363824720 : }
      88             : 
      89             : INLINE void compress_pre(__m128i rows[4], const uint32_t cv[8],
      90             :                          const uint8_t block[BLAKE3_BLOCK_LEN],
      91    51974960 :                          uint8_t block_len, uint64_t counter, uint8_t flags) {
      92    51974960 :   rows[0] = loadu((uint8_t *)&cv[0]);
      93    51974960 :   rows[1] = loadu((uint8_t *)&cv[4]);
      94    51974960 :   rows[2] = set4(IV[0], IV[1], IV[2], IV[3]);
      95    51974960 :   rows[3] = set4(counter_low(counter), counter_high(counter),
      96    51974960 :                  (uint32_t)block_len, (uint32_t)flags);
      97             : 
      98    51974960 :   __m128i m0 = loadu(&block[sizeof(__m128i) * 0]);
      99    51974960 :   __m128i m1 = loadu(&block[sizeof(__m128i) * 1]);
     100    51974960 :   __m128i m2 = loadu(&block[sizeof(__m128i) * 2]);
     101    51974960 :   __m128i m3 = loadu(&block[sizeof(__m128i) * 3]);
     102             : 
     103    51974960 :   __m128i t0, t1, t2, t3, tt;
     104             : 
     105             :   // Round 1. The first round permutes the message words from the original
     106             :   // input order, into the groups that get mixed in parallel.
     107    51974960 :   t0 = _mm_shuffle_ps2(m0, m1, _MM_SHUFFLE(2, 0, 2, 0)); //  6  4  2  0
     108    51974960 :   g1(&rows[0], &rows[1], &rows[2], &rows[3], t0);
     109    51974960 :   t1 = _mm_shuffle_ps2(m0, m1, _MM_SHUFFLE(3, 1, 3, 1)); //  7  5  3  1
     110    51974960 :   g2(&rows[0], &rows[1], &rows[2], &rows[3], t1);
     111    51974960 :   diagonalize(&rows[0], &rows[2], &rows[3]);
     112    51974960 :   t2 = _mm_shuffle_ps2(m2, m3, _MM_SHUFFLE(2, 0, 2, 0)); // 14 12 10  8
     113    51974960 :   t2 = _mm_shuffle_epi32(t2, _MM_SHUFFLE(2, 1, 0, 3));   // 12 10  8 14
     114    51974960 :   g1(&rows[0], &rows[1], &rows[2], &rows[3], t2);
     115    51974960 :   t3 = _mm_shuffle_ps2(m2, m3, _MM_SHUFFLE(3, 1, 3, 1)); // 15 13 11  9
     116    51974960 :   t3 = _mm_shuffle_epi32(t3, _MM_SHUFFLE(2, 1, 0, 3));   // 13 11  9 15
     117    51974960 :   g2(&rows[0], &rows[1], &rows[2], &rows[3], t3);
     118    51974960 :   undiagonalize(&rows[0], &rows[2], &rows[3]);
     119    51974960 :   m0 = t0;
     120    51974960 :   m1 = t1;
     121    51974960 :   m2 = t2;
     122    51974960 :   m3 = t3;
     123             : 
     124             :   // Round 2. This round and all following rounds apply a fixed permutation
     125             :   // to the message words from the round before.
     126    51974960 :   t0 = _mm_shuffle_ps2(m0, m1, _MM_SHUFFLE(3, 1, 1, 2));
     127    51974960 :   t0 = _mm_shuffle_epi32(t0, _MM_SHUFFLE(0, 3, 2, 1));
     128    51974960 :   g1(&rows[0], &rows[1], &rows[2], &rows[3], t0);
     129    51974960 :   t1 = _mm_shuffle_ps2(m2, m3, _MM_SHUFFLE(3, 3, 2, 2));
     130    51974960 :   tt = _mm_shuffle_epi32(m0, _MM_SHUFFLE(0, 0, 3, 3));
     131    51974960 :   t1 = _mm_blend_epi16(tt, t1, 0xCC);
     132    51974960 :   g2(&rows[0], &rows[1], &rows[2], &rows[3], t1);
     133    51974960 :   diagonalize(&rows[0], &rows[2], &rows[3]);
     134    51974960 :   t2 = _mm_unpacklo_epi64(m3, m1);
     135    51974960 :   tt = _mm_blend_epi16(t2, m2, 0xC0);
     136    51974960 :   t2 = _mm_shuffle_epi32(tt, _MM_SHUFFLE(1, 3, 2, 0));
     137    51974960 :   g1(&rows[0], &rows[1], &rows[2], &rows[3], t2);
     138    51974960 :   t3 = _mm_unpackhi_epi32(m1, m3);
     139    51974960 :   tt = _mm_unpacklo_epi32(m2, t3);
     140    51974960 :   t3 = _mm_shuffle_epi32(tt, _MM_SHUFFLE(0, 1, 3, 2));
     141    51974960 :   g2(&rows[0], &rows[1], &rows[2], &rows[3], t3);
     142    51974960 :   undiagonalize(&rows[0], &rows[2], &rows[3]);
     143    51974960 :   m0 = t0;
     144    51974960 :   m1 = t1;
     145    51974960 :   m2 = t2;
     146    51974960 :   m3 = t3;
     147             : 
     148             :   // Round 3
     149    51974960 :   t0 = _mm_shuffle_ps2(m0, m1, _MM_SHUFFLE(3, 1, 1, 2));
     150    51974960 :   t0 = _mm_shuffle_epi32(t0, _MM_SHUFFLE(0, 3, 2, 1));
     151    51974960 :   g1(&rows[0], &rows[1], &rows[2], &rows[3], t0);
     152    51974960 :   t1 = _mm_shuffle_ps2(m2, m3, _MM_SHUFFLE(3, 3, 2, 2));
     153    51974960 :   tt = _mm_shuffle_epi32(m0, _MM_SHUFFLE(0, 0, 3, 3));
     154    51974960 :   t1 = _mm_blend_epi16(tt, t1, 0xCC);
     155    51974960 :   g2(&rows[0], &rows[1], &rows[2], &rows[3], t1);
     156    51974960 :   diagonalize(&rows[0], &rows[2], &rows[3]);
     157    51974960 :   t2 = _mm_unpacklo_epi64(m3, m1);
     158    51974960 :   tt = _mm_blend_epi16(t2, m2, 0xC0);
     159    51974960 :   t2 = _mm_shuffle_epi32(tt, _MM_SHUFFLE(1, 3, 2, 0));
     160    51974960 :   g1(&rows[0], &rows[1], &rows[2], &rows[3], t2);
     161    51974960 :   t3 = _mm_unpackhi_epi32(m1, m3);
     162    51974960 :   tt = _mm_unpacklo_epi32(m2, t3);
     163    51974960 :   t3 = _mm_shuffle_epi32(tt, _MM_SHUFFLE(0, 1, 3, 2));
     164    51974960 :   g2(&rows[0], &rows[1], &rows[2], &rows[3], t3);
     165    51974960 :   undiagonalize(&rows[0], &rows[2], &rows[3]);
     166    51974960 :   m0 = t0;
     167    51974960 :   m1 = t1;
     168    51974960 :   m2 = t2;
     169    51974960 :   m3 = t3;
     170             : 
     171             :   // Round 4
     172    51974960 :   t0 = _mm_shuffle_ps2(m0, m1, _MM_SHUFFLE(3, 1, 1, 2));
     173    51974960 :   t0 = _mm_shuffle_epi32(t0, _MM_SHUFFLE(0, 3, 2, 1));
     174    51974960 :   g1(&rows[0], &rows[1], &rows[2], &rows[3], t0);
     175    51974960 :   t1 = _mm_shuffle_ps2(m2, m3, _MM_SHUFFLE(3, 3, 2, 2));
     176    51974960 :   tt = _mm_shuffle_epi32(m0, _MM_SHUFFLE(0, 0, 3, 3));
     177    51974960 :   t1 = _mm_blend_epi16(tt, t1, 0xCC);
     178    51974960 :   g2(&rows[0], &rows[1], &rows[2], &rows[3], t1);
     179    51974960 :   diagonalize(&rows[0], &rows[2], &rows[3]);
     180    51974960 :   t2 = _mm_unpacklo_epi64(m3, m1);
     181    51974960 :   tt = _mm_blend_epi16(t2, m2, 0xC0);
     182    51974960 :   t2 = _mm_shuffle_epi32(tt, _MM_SHUFFLE(1, 3, 2, 0));
     183    51974960 :   g1(&rows[0], &rows[1], &rows[2], &rows[3], t2);
     184    51974960 :   t3 = _mm_unpackhi_epi32(m1, m3);
     185    51974960 :   tt = _mm_unpacklo_epi32(m2, t3);
     186    51974960 :   t3 = _mm_shuffle_epi32(tt, _MM_SHUFFLE(0, 1, 3, 2));
     187    51974960 :   g2(&rows[0], &rows[1], &rows[2], &rows[3], t3);
     188    51974960 :   undiagonalize(&rows[0], &rows[2], &rows[3]);
     189    51974960 :   m0 = t0;
     190    51974960 :   m1 = t1;
     191    51974960 :   m2 = t2;
     192    51974960 :   m3 = t3;
     193             : 
     194             :   // Round 5
     195    51974960 :   t0 = _mm_shuffle_ps2(m0, m1, _MM_SHUFFLE(3, 1, 1, 2));
     196    51974960 :   t0 = _mm_shuffle_epi32(t0, _MM_SHUFFLE(0, 3, 2, 1));
     197    51974960 :   g1(&rows[0], &rows[1], &rows[2], &rows[3], t0);
     198    51974960 :   t1 = _mm_shuffle_ps2(m2, m3, _MM_SHUFFLE(3, 3, 2, 2));
     199    51974960 :   tt = _mm_shuffle_epi32(m0, _MM_SHUFFLE(0, 0, 3, 3));
     200    51974960 :   t1 = _mm_blend_epi16(tt, t1, 0xCC);
     201    51974960 :   g2(&rows[0], &rows[1], &rows[2], &rows[3], t1);
     202    51974960 :   diagonalize(&rows[0], &rows[2], &rows[3]);
     203    51974960 :   t2 = _mm_unpacklo_epi64(m3, m1);
     204    51974960 :   tt = _mm_blend_epi16(t2, m2, 0xC0);
     205    51974960 :   t2 = _mm_shuffle_epi32(tt, _MM_SHUFFLE(1, 3, 2, 0));
     206    51974960 :   g1(&rows[0], &rows[1], &rows[2], &rows[3], t2);
     207    51974960 :   t3 = _mm_unpackhi_epi32(m1, m3);
     208    51974960 :   tt = _mm_unpacklo_epi32(m2, t3);
     209    51974960 :   t3 = _mm_shuffle_epi32(tt, _MM_SHUFFLE(0, 1, 3, 2));
     210    51974960 :   g2(&rows[0], &rows[1], &rows[2], &rows[3], t3);
     211    51974960 :   undiagonalize(&rows[0], &rows[2], &rows[3]);
     212    51974960 :   m0 = t0;
     213    51974960 :   m1 = t1;
     214    51974960 :   m2 = t2;
     215    51974960 :   m3 = t3;
     216             : 
     217             :   // Round 6
     218    51974960 :   t0 = _mm_shuffle_ps2(m0, m1, _MM_SHUFFLE(3, 1, 1, 2));
     219    51974960 :   t0 = _mm_shuffle_epi32(t0, _MM_SHUFFLE(0, 3, 2, 1));
     220    51974960 :   g1(&rows[0], &rows[1], &rows[2], &rows[3], t0);
     221    51974960 :   t1 = _mm_shuffle_ps2(m2, m3, _MM_SHUFFLE(3, 3, 2, 2));
     222    51974960 :   tt = _mm_shuffle_epi32(m0, _MM_SHUFFLE(0, 0, 3, 3));
     223    51974960 :   t1 = _mm_blend_epi16(tt, t1, 0xCC);
     224    51974960 :   g2(&rows[0], &rows[1], &rows[2], &rows[3], t1);
     225    51974960 :   diagonalize(&rows[0], &rows[2], &rows[3]);
     226    51974960 :   t2 = _mm_unpacklo_epi64(m3, m1);
     227    51974960 :   tt = _mm_blend_epi16(t2, m2, 0xC0);
     228    51974960 :   t2 = _mm_shuffle_epi32(tt, _MM_SHUFFLE(1, 3, 2, 0));
     229    51974960 :   g1(&rows[0], &rows[1], &rows[2], &rows[3], t2);
     230    51974960 :   t3 = _mm_unpackhi_epi32(m1, m3);
     231    51974960 :   tt = _mm_unpacklo_epi32(m2, t3);
     232    51974960 :   t3 = _mm_shuffle_epi32(tt, _MM_SHUFFLE(0, 1, 3, 2));
     233    51974960 :   g2(&rows[0], &rows[1], &rows[2], &rows[3], t3);
     234    51974960 :   undiagonalize(&rows[0], &rows[2], &rows[3]);
     235    51974960 :   m0 = t0;
     236    51974960 :   m1 = t1;
     237    51974960 :   m2 = t2;
     238    51974960 :   m3 = t3;
     239             : 
     240             :   // Round 7
     241    51974960 :   t0 = _mm_shuffle_ps2(m0, m1, _MM_SHUFFLE(3, 1, 1, 2));
     242    51974960 :   t0 = _mm_shuffle_epi32(t0, _MM_SHUFFLE(0, 3, 2, 1));
     243    51974960 :   g1(&rows[0], &rows[1], &rows[2], &rows[3], t0);
     244    51974960 :   t1 = _mm_shuffle_ps2(m2, m3, _MM_SHUFFLE(3, 3, 2, 2));
     245    51974960 :   tt = _mm_shuffle_epi32(m0, _MM_SHUFFLE(0, 0, 3, 3));
     246    51974960 :   t1 = _mm_blend_epi16(tt, t1, 0xCC);
     247    51974960 :   g2(&rows[0], &rows[1], &rows[2], &rows[3], t1);
     248    51974960 :   diagonalize(&rows[0], &rows[2], &rows[3]);
     249    51974960 :   t2 = _mm_unpacklo_epi64(m3, m1);
     250    51974960 :   tt = _mm_blend_epi16(t2, m2, 0xC0);
     251    51974960 :   t2 = _mm_shuffle_epi32(tt, _MM_SHUFFLE(1, 3, 2, 0));
     252    51974960 :   g1(&rows[0], &rows[1], &rows[2], &rows[3], t2);
     253    51974960 :   t3 = _mm_unpackhi_epi32(m1, m3);
     254    51974960 :   tt = _mm_unpacklo_epi32(m2, t3);
     255    51974960 :   t3 = _mm_shuffle_epi32(tt, _MM_SHUFFLE(0, 1, 3, 2));
     256    51974960 :   g2(&rows[0], &rows[1], &rows[2], &rows[3], t3);
     257    51974960 :   undiagonalize(&rows[0], &rows[2], &rows[3]);
     258    51974960 : }
     259             : 
     260             : void blake3_compress_in_place_sse41(uint32_t cv[8],
     261             :                                     const uint8_t block[BLAKE3_BLOCK_LEN],
     262             :                                     uint8_t block_len, uint64_t counter,
     263    35010448 :                                     uint8_t flags) {
     264    35010448 :   __m128i rows[4];
     265    35010448 :   compress_pre(rows, cv, block, block_len, counter, flags);
     266    35010448 :   storeu(xorv(rows[0], rows[2]), (uint8_t *)&cv[0]);
     267    35010448 :   storeu(xorv(rows[1], rows[3]), (uint8_t *)&cv[4]);
     268    35010448 : }
     269             : 
     270             : void blake3_compress_xof_sse41(const uint32_t cv[8],
     271             :                                const uint8_t block[BLAKE3_BLOCK_LEN],
     272             :                                uint8_t block_len, uint64_t counter,
     273    16964512 :                                uint8_t flags, uint8_t out[64]) {
     274    16964512 :   __m128i rows[4];
     275    16964512 :   compress_pre(rows, cv, block, block_len, counter, flags);
     276    16964512 :   storeu(xorv(rows[0], rows[2]), &out[0]);
     277    16964512 :   storeu(xorv(rows[1], rows[3]), &out[16]);
     278    16964512 :   storeu(xorv(rows[2], loadu((uint8_t *)&cv[0])), &out[32]);
     279    16964512 :   storeu(xorv(rows[3], loadu((uint8_t *)&cv[4])), &out[48]);
     280    16964512 : }
     281             : 
     282    15754116 : INLINE void round_fn(__m128i v[16], __m128i m[16], size_t r) {
     283    15754116 :   v[0] = addv(v[0], m[(size_t)MSG_SCHEDULE[r][0]]);
     284    15754116 :   v[1] = addv(v[1], m[(size_t)MSG_SCHEDULE[r][2]]);
     285    15754116 :   v[2] = addv(v[2], m[(size_t)MSG_SCHEDULE[r][4]]);
     286    15754116 :   v[3] = addv(v[3], m[(size_t)MSG_SCHEDULE[r][6]]);
     287    15754116 :   v[0] = addv(v[0], v[4]);
     288    15754116 :   v[1] = addv(v[1], v[5]);
     289    15754116 :   v[2] = addv(v[2], v[6]);
     290    15754116 :   v[3] = addv(v[3], v[7]);
     291    15754116 :   v[12] = xorv(v[12], v[0]);
     292    15754116 :   v[13] = xorv(v[13], v[1]);
     293    15754116 :   v[14] = xorv(v[14], v[2]);
     294    15754116 :   v[15] = xorv(v[15], v[3]);
     295    15754116 :   v[12] = rot16(v[12]);
     296    15754116 :   v[13] = rot16(v[13]);
     297    15754116 :   v[14] = rot16(v[14]);
     298    15754116 :   v[15] = rot16(v[15]);
     299    15754116 :   v[8] = addv(v[8], v[12]);
     300    15754116 :   v[9] = addv(v[9], v[13]);
     301    15754116 :   v[10] = addv(v[10], v[14]);
     302    15754116 :   v[11] = addv(v[11], v[15]);
     303    15754116 :   v[4] = xorv(v[4], v[8]);
     304    15754116 :   v[5] = xorv(v[5], v[9]);
     305    15754116 :   v[6] = xorv(v[6], v[10]);
     306    15754116 :   v[7] = xorv(v[7], v[11]);
     307    15754116 :   v[4] = rot12(v[4]);
     308    15754116 :   v[5] = rot12(v[5]);
     309    15754116 :   v[6] = rot12(v[6]);
     310    15754116 :   v[7] = rot12(v[7]);
     311    15754116 :   v[0] = addv(v[0], m[(size_t)MSG_SCHEDULE[r][1]]);
     312    15754116 :   v[1] = addv(v[1], m[(size_t)MSG_SCHEDULE[r][3]]);
     313    15754116 :   v[2] = addv(v[2], m[(size_t)MSG_SCHEDULE[r][5]]);
     314    15754116 :   v[3] = addv(v[3], m[(size_t)MSG_SCHEDULE[r][7]]);
     315    15754116 :   v[0] = addv(v[0], v[4]);
     316    15754116 :   v[1] = addv(v[1], v[5]);
     317    15754116 :   v[2] = addv(v[2], v[6]);
     318    15754116 :   v[3] = addv(v[3], v[7]);
     319    15754116 :   v[12] = xorv(v[12], v[0]);
     320    15754116 :   v[13] = xorv(v[13], v[1]);
     321    15754116 :   v[14] = xorv(v[14], v[2]);
     322    15754116 :   v[15] = xorv(v[15], v[3]);
     323    15754116 :   v[12] = rot8(v[12]);
     324    15754116 :   v[13] = rot8(v[13]);
     325    15754116 :   v[14] = rot8(v[14]);
     326    15754116 :   v[15] = rot8(v[15]);
     327    15754116 :   v[8] = addv(v[8], v[12]);
     328    15754116 :   v[9] = addv(v[9], v[13]);
     329    15754116 :   v[10] = addv(v[10], v[14]);
     330    15754116 :   v[11] = addv(v[11], v[15]);
     331    15754116 :   v[4] = xorv(v[4], v[8]);
     332    15754116 :   v[5] = xorv(v[5], v[9]);
     333    15754116 :   v[6] = xorv(v[6], v[10]);
     334    15754116 :   v[7] = xorv(v[7], v[11]);
     335    15754116 :   v[4] = rot7(v[4]);
     336    15754116 :   v[5] = rot7(v[5]);
     337    15754116 :   v[6] = rot7(v[6]);
     338    15754116 :   v[7] = rot7(v[7]);
     339             : 
     340    15754116 :   v[0] = addv(v[0], m[(size_t)MSG_SCHEDULE[r][8]]);
     341    15754116 :   v[1] = addv(v[1], m[(size_t)MSG_SCHEDULE[r][10]]);
     342    15754116 :   v[2] = addv(v[2], m[(size_t)MSG_SCHEDULE[r][12]]);
     343    15754116 :   v[3] = addv(v[3], m[(size_t)MSG_SCHEDULE[r][14]]);
     344    15754116 :   v[0] = addv(v[0], v[5]);
     345    15754116 :   v[1] = addv(v[1], v[6]);
     346    15754116 :   v[2] = addv(v[2], v[7]);
     347    15754116 :   v[3] = addv(v[3], v[4]);
     348    15754116 :   v[15] = xorv(v[15], v[0]);
     349    15754116 :   v[12] = xorv(v[12], v[1]);
     350    15754116 :   v[13] = xorv(v[13], v[2]);
     351    15754116 :   v[14] = xorv(v[14], v[3]);
     352    15754116 :   v[15] = rot16(v[15]);
     353    15754116 :   v[12] = rot16(v[12]);
     354    15754116 :   v[13] = rot16(v[13]);
     355    15754116 :   v[14] = rot16(v[14]);
     356    15754116 :   v[10] = addv(v[10], v[15]);
     357    15754116 :   v[11] = addv(v[11], v[12]);
     358    15754116 :   v[8] = addv(v[8], v[13]);
     359    15754116 :   v[9] = addv(v[9], v[14]);
     360    15754116 :   v[5] = xorv(v[5], v[10]);
     361    15754116 :   v[6] = xorv(v[6], v[11]);
     362    15754116 :   v[7] = xorv(v[7], v[8]);
     363    15754116 :   v[4] = xorv(v[4], v[9]);
     364    15754116 :   v[5] = rot12(v[5]);
     365    15754116 :   v[6] = rot12(v[6]);
     366    15754116 :   v[7] = rot12(v[7]);
     367    15754116 :   v[4] = rot12(v[4]);
     368    15754116 :   v[0] = addv(v[0], m[(size_t)MSG_SCHEDULE[r][9]]);
     369    15754116 :   v[1] = addv(v[1], m[(size_t)MSG_SCHEDULE[r][11]]);
     370    15754116 :   v[2] = addv(v[2], m[(size_t)MSG_SCHEDULE[r][13]]);
     371    15754116 :   v[3] = addv(v[3], m[(size_t)MSG_SCHEDULE[r][15]]);
     372    15754116 :   v[0] = addv(v[0], v[5]);
     373    15754116 :   v[1] = addv(v[1], v[6]);
     374    15754116 :   v[2] = addv(v[2], v[7]);
     375    15754116 :   v[3] = addv(v[3], v[4]);
     376    15754116 :   v[15] = xorv(v[15], v[0]);
     377    15754116 :   v[12] = xorv(v[12], v[1]);
     378    15754116 :   v[13] = xorv(v[13], v[2]);
     379    15754116 :   v[14] = xorv(v[14], v[3]);
     380    15754116 :   v[15] = rot8(v[15]);
     381    15754116 :   v[12] = rot8(v[12]);
     382    15754116 :   v[13] = rot8(v[13]);
     383    15754116 :   v[14] = rot8(v[14]);
     384    15754116 :   v[10] = addv(v[10], v[15]);
     385    15754116 :   v[11] = addv(v[11], v[12]);
     386    15754116 :   v[8] = addv(v[8], v[13]);
     387    15754116 :   v[9] = addv(v[9], v[14]);
     388    15754116 :   v[5] = xorv(v[5], v[10]);
     389    15754116 :   v[6] = xorv(v[6], v[11]);
     390    15754116 :   v[7] = xorv(v[7], v[8]);
     391    15754116 :   v[4] = xorv(v[4], v[9]);
     392    15754116 :   v[5] = rot7(v[5]);
     393    15754116 :   v[6] = rot7(v[6]);
     394    15754116 :   v[7] = rot7(v[7]);
     395    15754116 :   v[4] = rot7(v[4]);
     396    15754116 : }
     397             : 
     398     9531768 : INLINE void transpose_vecs(__m128i vecs[DEGREE]) {
     399             :   // Interleave 32-bit lanes. The low unpack is lanes 00/11 and the high is
     400             :   // 22/33. Note that this doesn't split the vector into two lanes, as the
     401             :   // AVX2 counterparts do.
     402     9531768 :   __m128i ab_01 = _mm_unpacklo_epi32(vecs[0], vecs[1]);
     403     9531768 :   __m128i ab_23 = _mm_unpackhi_epi32(vecs[0], vecs[1]);
     404     9531768 :   __m128i cd_01 = _mm_unpacklo_epi32(vecs[2], vecs[3]);
     405     9531768 :   __m128i cd_23 = _mm_unpackhi_epi32(vecs[2], vecs[3]);
     406             : 
     407             :   // Interleave 64-bit lanes.
     408     9531768 :   __m128i abcd_0 = _mm_unpacklo_epi64(ab_01, cd_01);
     409     9531768 :   __m128i abcd_1 = _mm_unpackhi_epi64(ab_01, cd_01);
     410     9531768 :   __m128i abcd_2 = _mm_unpacklo_epi64(ab_23, cd_23);
     411     9531768 :   __m128i abcd_3 = _mm_unpackhi_epi64(ab_23, cd_23);
     412             : 
     413     9531768 :   vecs[0] = abcd_0;
     414     9531768 :   vecs[1] = abcd_1;
     415     9531768 :   vecs[2] = abcd_2;
     416     9531768 :   vecs[3] = abcd_3;
     417     9531768 : }
     418             : 
     419             : INLINE void transpose_msg_vecs(const uint8_t *const *inputs,
     420     2250588 :                                size_t block_offset, __m128i out[16]) {
     421     2250588 :   out[0] = loadu(&inputs[0][block_offset + 0 * sizeof(__m128i)]);
     422     2250588 :   out[1] = loadu(&inputs[1][block_offset + 0 * sizeof(__m128i)]);
     423     2250588 :   out[2] = loadu(&inputs[2][block_offset + 0 * sizeof(__m128i)]);
     424     2250588 :   out[3] = loadu(&inputs[3][block_offset + 0 * sizeof(__m128i)]);
     425     2250588 :   out[4] = loadu(&inputs[0][block_offset + 1 * sizeof(__m128i)]);
     426     2250588 :   out[5] = loadu(&inputs[1][block_offset + 1 * sizeof(__m128i)]);
     427     2250588 :   out[6] = loadu(&inputs[2][block_offset + 1 * sizeof(__m128i)]);
     428     2250588 :   out[7] = loadu(&inputs[3][block_offset + 1 * sizeof(__m128i)]);
     429     2250588 :   out[8] = loadu(&inputs[0][block_offset + 2 * sizeof(__m128i)]);
     430     2250588 :   out[9] = loadu(&inputs[1][block_offset + 2 * sizeof(__m128i)]);
     431     2250588 :   out[10] = loadu(&inputs[2][block_offset + 2 * sizeof(__m128i)]);
     432     2250588 :   out[11] = loadu(&inputs[3][block_offset + 2 * sizeof(__m128i)]);
     433     2250588 :   out[12] = loadu(&inputs[0][block_offset + 3 * sizeof(__m128i)]);
     434     2250588 :   out[13] = loadu(&inputs[1][block_offset + 3 * sizeof(__m128i)]);
     435     2250588 :   out[14] = loadu(&inputs[2][block_offset + 3 * sizeof(__m128i)]);
     436     2250588 :   out[15] = loadu(&inputs[3][block_offset + 3 * sizeof(__m128i)]);
     437    11252940 :   for (size_t i = 0; i < 4; ++i) {
     438     9002352 :     _mm_prefetch((const void *)&inputs[i][block_offset + 256], _MM_HINT_T0);
     439     9002352 :   }
     440     2250588 :   transpose_vecs(&out[0]);
     441     2250588 :   transpose_vecs(&out[4]);
     442     2250588 :   transpose_vecs(&out[8]);
     443     2250588 :   transpose_vecs(&out[12]);
     444     2250588 : }
     445             : 
     446             : INLINE void load_counters(uint64_t counter, bool increment_counter,
     447      264708 :                           __m128i *out_lo, __m128i *out_hi) {
     448      264708 :   const __m128i mask = _mm_set1_epi32(-(int32_t)increment_counter);
     449      264708 :   const __m128i add0 = _mm_set_epi32(3, 2, 1, 0);
     450      264708 :   const __m128i add1 = _mm_and_si128(mask, add0);
     451      264708 :   __m128i l = _mm_add_epi32(_mm_set1_epi32((int32_t)counter), add1);
     452      264708 :   __m128i carry = _mm_cmpgt_epi32(_mm_xor_si128(add1, _mm_set1_epi32(0x80000000)),
     453      264708 :                                   _mm_xor_si128(   l, _mm_set1_epi32(0x80000000)));
     454      264708 :   __m128i h = _mm_sub_epi32(_mm_set1_epi32((int32_t)(counter >> 32)), carry);
     455      264708 :   *out_lo = l;
     456      264708 :   *out_hi = h;
     457      264708 : }
     458             : 
     459             : static
     460             : void blake3_hash4_sse41(const uint8_t *const *inputs, size_t blocks,
     461             :                         const uint32_t key[8], uint64_t counter,
     462             :                         bool increment_counter, uint8_t flags,
     463      264708 :                         uint8_t flags_start, uint8_t flags_end, uint8_t *out) {
     464      264708 :   __m128i h_vecs[8] = {
     465      264708 :       set1(key[0]), set1(key[1]), set1(key[2]), set1(key[3]),
     466      264708 :       set1(key[4]), set1(key[5]), set1(key[6]), set1(key[7]),
     467      264708 :   };
     468      264708 :   __m128i counter_low_vec, counter_high_vec;
     469      264708 :   load_counters(counter, increment_counter, &counter_low_vec,
     470      264708 :                 &counter_high_vec);
     471      264708 :   uint8_t block_flags = flags | flags_start;
     472             : 
     473     2515296 :   for (size_t block = 0; block < blocks; block++) {
     474     2250588 :     if (block + 1 == blocks) {
     475      264708 :       block_flags |= flags_end;
     476      264708 :     }
     477     2250588 :     __m128i block_len_vec = set1(BLAKE3_BLOCK_LEN);
     478     2250588 :     __m128i block_flags_vec = set1(block_flags);
     479     2250588 :     __m128i msg_vecs[16];
     480     2250588 :     transpose_msg_vecs(inputs, block * BLAKE3_BLOCK_LEN, msg_vecs);
     481             : 
     482     2250588 :     __m128i v[16] = {
     483     2250588 :         h_vecs[0],       h_vecs[1],        h_vecs[2],     h_vecs[3],
     484     2250588 :         h_vecs[4],       h_vecs[5],        h_vecs[6],     h_vecs[7],
     485     2250588 :         set1(IV[0]),     set1(IV[1]),      set1(IV[2]),   set1(IV[3]),
     486     2250588 :         counter_low_vec, counter_high_vec, block_len_vec, block_flags_vec,
     487     2250588 :     };
     488     2250588 :     round_fn(v, msg_vecs, 0);
     489     2250588 :     round_fn(v, msg_vecs, 1);
     490     2250588 :     round_fn(v, msg_vecs, 2);
     491     2250588 :     round_fn(v, msg_vecs, 3);
     492     2250588 :     round_fn(v, msg_vecs, 4);
     493     2250588 :     round_fn(v, msg_vecs, 5);
     494     2250588 :     round_fn(v, msg_vecs, 6);
     495     2250588 :     h_vecs[0] = xorv(v[0], v[8]);
     496     2250588 :     h_vecs[1] = xorv(v[1], v[9]);
     497     2250588 :     h_vecs[2] = xorv(v[2], v[10]);
     498     2250588 :     h_vecs[3] = xorv(v[3], v[11]);
     499     2250588 :     h_vecs[4] = xorv(v[4], v[12]);
     500     2250588 :     h_vecs[5] = xorv(v[5], v[13]);
     501     2250588 :     h_vecs[6] = xorv(v[6], v[14]);
     502     2250588 :     h_vecs[7] = xorv(v[7], v[15]);
     503             : 
     504     2250588 :     block_flags = flags;
     505     2250588 :   }
     506             : 
     507      264708 :   transpose_vecs(&h_vecs[0]);
     508      264708 :   transpose_vecs(&h_vecs[4]);
     509             :   // The first four vecs now contain the first half of each output, and the
     510             :   // second four vecs contain the second half of each output.
     511      264708 :   storeu(h_vecs[0], &out[0 * sizeof(__m128i)]);
     512      264708 :   storeu(h_vecs[4], &out[1 * sizeof(__m128i)]);
     513      264708 :   storeu(h_vecs[1], &out[2 * sizeof(__m128i)]);
     514      264708 :   storeu(h_vecs[5], &out[3 * sizeof(__m128i)]);
     515      264708 :   storeu(h_vecs[2], &out[4 * sizeof(__m128i)]);
     516      264708 :   storeu(h_vecs[6], &out[5 * sizeof(__m128i)]);
     517      264708 :   storeu(h_vecs[3], &out[6 * sizeof(__m128i)]);
     518      264708 :   storeu(h_vecs[7], &out[7 * sizeof(__m128i)]);
     519      264708 : }
     520             : 
     521             : INLINE void hash_one_sse41(const uint8_t *input, size_t blocks,
     522             :                            const uint32_t key[8], uint64_t counter,
     523             :                            uint8_t flags, uint8_t flags_start,
     524     1060184 :                            uint8_t flags_end, uint8_t out[BLAKE3_OUT_LEN]) {
     525     1060184 :   uint32_t cv[8];
     526     1060184 :   memcpy(cv, key, BLAKE3_KEY_LEN);
     527     1060184 :   uint8_t block_flags = flags | flags_start;
     528    10081888 :   while (blocks > 0) {
     529     9021704 :     if (blocks == 1) {
     530     1060184 :       block_flags |= flags_end;
     531     1060184 :     }
     532     9021704 :     blake3_compress_in_place_sse41(cv, input, BLAKE3_BLOCK_LEN, counter,
     533     9021704 :                                    block_flags);
     534     9021704 :     input = &input[BLAKE3_BLOCK_LEN];
     535     9021704 :     blocks -= 1;
     536     9021704 :     block_flags = flags;
     537     9021704 :   }
     538     1060184 :   memcpy(out, cv, BLAKE3_OUT_LEN);
     539     1060184 : }
     540             : 
     541             : void blake3_hash_many_sse41(const uint8_t *const *inputs, size_t num_inputs,
     542             :                             size_t blocks, const uint32_t key[8],
     543             :                             uint64_t counter, bool increment_counter,
     544             :                             uint8_t flags, uint8_t flags_start,
     545     2115372 :                             uint8_t flags_end, uint8_t *out) {
     546     2380080 :   while (num_inputs >= DEGREE) {
     547      264708 :     blake3_hash4_sse41(inputs, blocks, key, counter, increment_counter, flags,
     548      264708 :                        flags_start, flags_end, out);
     549      264708 :     if (increment_counter) {
     550      132392 :       counter += DEGREE;
     551      132392 :     }
     552      264708 :     inputs += DEGREE;
     553      264708 :     num_inputs -= DEGREE;
     554      264708 :     out = &out[DEGREE * BLAKE3_OUT_LEN];
     555      264708 :   }
     556     3175556 :   while (num_inputs > 0) {
     557     1060184 :     hash_one_sse41(inputs[0], blocks, key, counter, flags, flags_start,
     558     1060184 :                    flags_end, out);
     559     1060184 :     if (increment_counter) {
     560      530768 :       counter += 1;
     561      530768 :     }
     562     1060184 :     inputs += 1;
     563     1060184 :     num_inputs -= 1;
     564     1060184 :     out = &out[BLAKE3_OUT_LEN];
     565     1060184 :   }
     566     2115372 : }