| 1 |
|
| #include "highwayhash.h" |
| 2 |
|
| |
| 3 |
|
| #include <stdint.h> |
| 4 |
|
| #include <stdlib.h> |
| 5 |
|
| #include <string.h> |
| 6 |
|
| |
| 7 |
|
| /* |
| 8 |
|
| This code is compatible with C90 with the additional requirement of |
| 9 |
|
| supporting uint64_t. |
| 10 |
|
| */ |
| 11 |
|
| |
| 12 |
|
| /*////////////////////////////////////////////////////////////////////////////*/ |
| 13 |
|
| /* Internal implementation */ |
| 14 |
|
| /*////////////////////////////////////////////////////////////////////////////*/ |
| 15 |
|
| |
| 16 |
3 |
| void HighwayHashReset(const uint64_t key[4], HighwayHashState* state) { |
| 17 |
3 |
| state->mul0[0] = 0xdbe6d5d5fe4cce2full; |
| 18 |
3 |
| state->mul0[1] = 0xa4093822299f31d0ull; |
| 19 |
3 |
| state->mul0[2] = 0x13198a2e03707344ull; |
| 20 |
3 |
| state->mul0[3] = 0x243f6a8885a308d3ull; |
| 21 |
3 |
| state->mul1[0] = 0x3bd39e10cb0ef593ull; |
| 22 |
3 |
| state->mul1[1] = 0xc0acf169b5f18a8cull; |
| 23 |
3 |
| state->mul1[2] = 0xbe5466cf34e90c6cull; |
| 24 |
3 |
| state->mul1[3] = 0x452821e638d01377ull; |
| 25 |
3 |
| state->v0[0] = state->mul0[0] ^ key[0]; |
| 26 |
3 |
| state->v0[1] = state->mul0[1] ^ key[1]; |
| 27 |
3 |
| state->v0[2] = state->mul0[2] ^ key[2]; |
| 28 |
3 |
| state->v0[3] = state->mul0[3] ^ key[3]; |
| 29 |
3 |
| state->v1[0] = state->mul1[0] ^ ((key[0] >> 32) | (key[0] << 32)); |
| 30 |
3 |
| state->v1[1] = state->mul1[1] ^ ((key[1] >> 32) | (key[1] << 32)); |
| 31 |
3 |
| state->v1[2] = state->mul1[2] ^ ((key[2] >> 32) | (key[2] << 32)); |
| 32 |
3 |
| state->v1[3] = state->mul1[3] ^ ((key[3] >> 32) | (key[3] << 32)); |
| 33 |
3 |
| } |
| 34 |
|
| |
| 35 |
92 |
| static void ZipperMergeAndAdd(const uint64_t v1, const uint64_t v0, |
| 36 |
|
| uint64_t* add1, uint64_t* add0) { |
| 37 |
92 |
| *add0 += (((v0 & 0xff000000ull) | (v1 & 0xff00000000ull)) >> 24) | |
| 38 |
92 |
| (((v0 & 0xff0000000000ull) | (v1 & 0xff000000000000ull)) >> 16) | |
| 39 |
92 |
| (v0 & 0xff0000ull) | ((v0 & 0xff00ull) << 32) | |
| 40 |
92 |
| ((v1 & 0xff00000000000000ull) >> 8) | (v0 << 56); |
| 41 |
92 |
| *add1 += (((v1 & 0xff000000ull) | (v0 & 0xff00000000ull)) >> 24) | |
| 42 |
92 |
| (v1 & 0xff0000ull) | ((v1 & 0xff0000000000ull) >> 16) | |
| 43 |
92 |
| ((v1 & 0xff00ull) << 24) | ((v0 & 0xff000000000000ull) >> 8) | |
| 44 |
92 |
| ((v1 & 0xffull) << 48) | (v0 & 0xff00000000000000ull); |
| 45 |
92 |
| } |
| 46 |
|
| |
| 47 |
23 |
| static void Update(const uint64_t lanes[4], HighwayHashState* state) { |
| 48 |
|
| int i; |
| 49 |
115 |
▶ | for (i = 0; i < 4; ++i) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < 4; ++i) { |
92 |
23 |
115 |
|
| 50 |
92 |
| state->v1[i] += state->mul0[i] + lanes[i]; |
| 51 |
92 |
| state->mul0[i] ^= (state->v1[i] & 0xffffffff) * (state->v0[i] >> 32); |
| 52 |
92 |
| state->v0[i] += state->mul1[i]; |
| 53 |
92 |
| state->mul1[i] ^= (state->v0[i] & 0xffffffff) * (state->v1[i] >> 32); |
| 54 |
|
| } |
| 55 |
23 |
| ZipperMergeAndAdd(state->v1[1], state->v1[0], &state->v0[1], &state->v0[0]); |
| 56 |
23 |
| ZipperMergeAndAdd(state->v1[3], state->v1[2], &state->v0[3], &state->v0[2]); |
| 57 |
23 |
| ZipperMergeAndAdd(state->v0[1], state->v0[0], &state->v1[1], &state->v1[0]); |
| 58 |
23 |
| ZipperMergeAndAdd(state->v0[3], state->v0[2], &state->v1[3], &state->v1[2]); |
| 59 |
23 |
| } |
| 60 |
|
| |
| 61 |
12 |
| static uint64_t Read64(const uint8_t* src) { |
| 62 |
12 |
| return (uint64_t)src[0] | ((uint64_t)src[1] << 8) | |
| 63 |
12 |
| ((uint64_t)src[2] << 16) | ((uint64_t)src[3] << 24) | |
| 64 |
12 |
| ((uint64_t)src[4] << 32) | ((uint64_t)src[5] << 40) | |
| 65 |
12 |
| ((uint64_t)src[6] << 48) | ((uint64_t)src[7] << 56); |
| 66 |
|
| } |
| 67 |
|
| |
| 68 |
3 |
| void HighwayHashUpdatePacket(const uint8_t* packet, HighwayHashState* state) { |
| 69 |
|
| uint64_t lanes[4]; |
| 70 |
3 |
| lanes[0] = Read64(packet + 0); |
| 71 |
3 |
| lanes[1] = Read64(packet + 8); |
| 72 |
3 |
| lanes[2] = Read64(packet + 16); |
| 73 |
3 |
| lanes[3] = Read64(packet + 24); |
| 74 |
3 |
| Update(lanes, state); |
| 75 |
3 |
| } |
| 76 |
|
| |
| 77 |
3 |
| static void Rotate32By(uint64_t count, uint64_t lanes[4]) { |
| 78 |
|
| int i; |
| 79 |
15 |
▶ | for (i = 0; i < 4; ++i) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < 4; ++i) { |
12 |
3 |
15 |
|
| 80 |
12 |
| uint32_t half0 = lanes[i] & 0xffffffff; |
| 81 |
12 |
| uint32_t half1 = (lanes[i] >> 32); |
| 82 |
12 |
| lanes[i] = (half0 << count) | (half0 >> (32 - count)); |
| 83 |
12 |
| lanes[i] |= (uint64_t)((half1 << count) | (half1 >> (32 - count))) << 32; |
| 84 |
|
| } |
| 85 |
3 |
| } |
| 86 |
|
| |
| 87 |
3 |
| void HighwayHashUpdateRemainder(const uint8_t* bytes, const size_t size_mod32, |
| 88 |
|
| HighwayHashState* state) { |
| 89 |
|
| int i; |
| 90 |
3 |
| const size_t size_mod4 = size_mod32 & 3; |
| 91 |
3 |
| const uint8_t* remainder = bytes + (size_mod32 & ~3); |
| 92 |
3 |
| uint8_t packet[32] = {0}; |
| 93 |
15 |
▶ | for (i = 0; i < 4; ++i) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < 4; ++i) { |
12 |
3 |
15 |
|
| 94 |
12 |
| state->v0[i] += ((uint64_t)size_mod32 << 32) + size_mod32; |
| 95 |
|
| } |
| 96 |
3 |
| Rotate32By(size_mod32, state->v1); |
| 97 |
15 |
▶ | for (i = 0; i < remainder - bytes; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < remainder - bytes; i++) { |
12 |
3 |
15 |
|
| 98 |
12 |
| packet[i] = bytes[i]; |
| 99 |
|
| } |
| 100 |
3 |
▶ | if (size_mod32 & 16) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (size_mod32 & 16) { |
0 |
3 |
3 |
|
| 101 |
0 |
▶ | for (i = 0; i < 4; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < 4; i++) { |
0 |
0 |
0 |
|
| 102 |
0 |
| packet[28 + i] = remainder[i + size_mod4 - 4]; |
| 103 |
|
| } |
| 104 |
|
| } else { |
| 105 |
3 |
▶ | if (size_mod4) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (size_mod4) { |
3 |
0 |
3 |
|
| 106 |
3 |
| packet[16 + 0] = remainder[0]; |
| 107 |
3 |
| packet[16 + 1] = remainder[size_mod4 >> 1]; |
| 108 |
3 |
| packet[16 + 2] = remainder[size_mod4 - 1]; |
| 109 |
|
| } |
| 110 |
|
| } |
| 111 |
3 |
| HighwayHashUpdatePacket(packet, state); |
| 112 |
3 |
| } |
| 113 |
|
| |
| 114 |
20 |
| static void Permute(const uint64_t v[4], uint64_t* permuted) { |
| 115 |
20 |
| permuted[0] = (v[2] >> 32) | (v[2] << 32); |
| 116 |
20 |
| permuted[1] = (v[3] >> 32) | (v[3] << 32); |
| 117 |
20 |
| permuted[2] = (v[0] >> 32) | (v[0] << 32); |
| 118 |
20 |
| permuted[3] = (v[1] >> 32) | (v[1] << 32); |
| 119 |
20 |
| } |
| 120 |
|
| |
| 121 |
20 |
| void PermuteAndUpdate(HighwayHashState* state) { |
| 122 |
|
| uint64_t permuted[4]; |
| 123 |
20 |
| Permute(state->v0, permuted); |
| 124 |
20 |
| Update(permuted, state); |
| 125 |
20 |
| } |
| 126 |
|
| |
| 127 |
2 |
| static void ModularReduction(uint64_t a3_unmasked, uint64_t a2, uint64_t a1, |
| 128 |
|
| uint64_t a0, uint64_t* m1, uint64_t* m0) { |
| 129 |
2 |
| uint64_t a3 = a3_unmasked & 0x3FFFFFFFFFFFFFFFull; |
| 130 |
2 |
| *m1 = a1 ^ ((a3 << 1) | (a2 >> 63)) ^ ((a3 << 2) | (a2 >> 62)); |
| 131 |
2 |
| *m0 = a0 ^ (a2 << 1) ^ (a2 << 2); |
| 132 |
2 |
| } |
| 133 |
|
| |
| 134 |
1 |
| static uint64_t HighwayHashFinalize64(HighwayHashState* state) { |
| 135 |
|
| int i; |
| 136 |
5 |
▶ | for (i = 0; i < 4; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < 4; i++) { |
4 |
1 |
5 |
|
| 137 |
4 |
| PermuteAndUpdate(state); |
| 138 |
|
| } |
| 139 |
1 |
| return state->v0[0] + state->v1[0] + state->mul0[0] + state->mul1[0]; |
| 140 |
|
| } |
| 141 |
|
| |
| 142 |
1 |
| static void HighwayHashFinalize128(HighwayHashState* state, uint64_t hash[2]) { |
| 143 |
|
| int i; |
| 144 |
7 |
▶ | for (i = 0; i < 6; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < 6; i++) { |
6 |
1 |
7 |
|
| 145 |
6 |
| PermuteAndUpdate(state); |
| 146 |
|
| } |
| 147 |
1 |
| hash[0] = state->v0[0] + state->mul0[0] + state->v1[2] + state->mul1[2]; |
| 148 |
1 |
| hash[1] = state->v0[1] + state->mul0[1] + state->v1[3] + state->mul1[3]; |
| 149 |
1 |
| } |
| 150 |
|
| |
| 151 |
1 |
| static void HighwayHashFinalize256(HighwayHashState* state, uint64_t hash[4]) { |
| 152 |
|
| int i; |
| 153 |
|
| /* We anticipate that 256-bit hashing will be mostly used with long messages |
| 154 |
|
| because storing and using the 256-bit hash (in contrast to 128-bit) |
| 155 |
|
| carries a larger additional constant cost by itself. Doing extra rounds |
| 156 |
|
| here hardly increases the per-byte cost of long messages. */ |
| 157 |
11 |
▶ | for (i = 0; i < 10; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < 10; i++) { |
10 |
1 |
11 |
|
| 158 |
10 |
| PermuteAndUpdate(state); |
| 159 |
|
| } |
| 160 |
1 |
| ModularReduction(state->v1[1] + state->mul1[1], state->v1[0] + state->mul1[0], |
| 161 |
1 |
| state->v0[1] + state->mul0[1], state->v0[0] + state->mul0[0], |
| 162 |
|
| &hash[1], &hash[0]); |
| 163 |
1 |
| ModularReduction(state->v1[3] + state->mul1[3], state->v1[2] + state->mul1[2], |
| 164 |
1 |
| state->v0[3] + state->mul0[3], state->v0[2] + state->mul0[2], |
| 165 |
|
| &hash[3], &hash[2]); |
| 166 |
1 |
| } |
| 167 |
|
| |
| 168 |
|
| /*////////////////////////////////////////////////////////////////////////////*/ |
| 169 |
|
| /* Non-cat API: single call on full data */ |
| 170 |
|
| /*////////////////////////////////////////////////////////////////////////////*/ |
| 171 |
|
| |
| 172 |
3 |
| static void ProcessAll(const uint8_t* data, size_t size, const uint64_t key[4], |
| 173 |
|
| HighwayHashState* state) { |
| 174 |
|
| size_t i; |
| 175 |
3 |
| HighwayHashReset(key, state); |
| 176 |
3 |
▶ | for (i = 0; i + 32 <= size; i += 32) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i + 32 <= size; i += 32) { |
0 |
3 |
3 |
|
| 177 |
0 |
| HighwayHashUpdatePacket(data + i, state); |
| 178 |
|
| } |
| 179 |
3 |
▶ | if ((size & 31) != 0) HighwayHashUpdateRemainder(data + i, size & 31, state); |
Branch: 1 branch
| Branch | True | False | Total |
| if ((size & 31) != 0) HighwayHashUpdateRemainder(data + i, size & 31, state); |
3 |
0 |
3 |
|
| 180 |
3 |
| } |
| 181 |
|
| |
| 182 |
1 |
| uint64_t HighwayHash64(const uint8_t* data, size_t size, |
| 183 |
|
| const uint64_t key[4]) { |
| 184 |
|
| HighwayHashState state; |
| 185 |
1 |
| ProcessAll(data, size, key, &state); |
| 186 |
1 |
| return HighwayHashFinalize64(&state); |
| 187 |
|
| } |
| 188 |
|
| |
| 189 |
1 |
| void HighwayHash128(const uint8_t* data, size_t size, |
| 190 |
|
| const uint64_t key[4], uint64_t hash[2]) { |
| 191 |
|
| HighwayHashState state; |
| 192 |
1 |
| ProcessAll(data, size, key, &state); |
| 193 |
1 |
| HighwayHashFinalize128(&state, hash); |
| 194 |
1 |
| } |
| 195 |
|
| |
| 196 |
1 |
| void HighwayHash256(const uint8_t* data, size_t size, |
| 197 |
|
| const uint64_t key[4], uint64_t hash[4]) { |
| 198 |
|
| HighwayHashState state; |
| 199 |
1 |
| ProcessAll(data, size, key, &state); |
| 200 |
1 |
| HighwayHashFinalize256(&state, hash); |
| 201 |
1 |
| } |
| 202 |
|
| |
| 203 |
|
| /*////////////////////////////////////////////////////////////////////////////*/ |
| 204 |
|
| /* Cat API: allows appending with multiple calls */ |
| 205 |
|
| /*////////////////////////////////////////////////////////////////////////////*/ |
| 206 |
|
| |
| 207 |
0 |
| void HighwayHashCatStart(const uint64_t key[4], HighwayHashCat* state) { |
| 208 |
0 |
| HighwayHashReset(key, &state->state); |
| 209 |
0 |
| state->num = 0; |
| 210 |
0 |
| } |
| 211 |
|
| |
| 212 |
0 |
| void HighwayHashCatAppend(const uint8_t* bytes, size_t num, |
| 213 |
|
| HighwayHashCat* state) { |
| 214 |
|
| size_t i; |
| 215 |
0 |
▶ | if (state->num != 0) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (state->num != 0) { |
0 |
0 |
0 |
|
| 216 |
0 |
| size_t num_add = num > (32u - state->num) ? (32u - state->num) : num; |
| 217 |
0 |
▶ | for (i = 0; i < num_add; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < num_add; i++) { |
0 |
0 |
0 |
|
| 218 |
0 |
| state->packet[state->num + i] = bytes[i]; |
| 219 |
|
| } |
| 220 |
0 |
| state->num += num_add; |
| 221 |
0 |
| num -= num_add; |
| 222 |
0 |
| bytes += num_add; |
| 223 |
0 |
▶ | if (state->num == 32) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (state->num == 32) { |
0 |
0 |
0 |
|
| 224 |
0 |
| HighwayHashUpdatePacket(state->packet, &state->state); |
| 225 |
0 |
| state->num = 0; |
| 226 |
|
| } |
| 227 |
|
| } |
| 228 |
0 |
▶ | while (num >= 32) { |
Branch: 1 branch
| Branch | True | False | Total |
| while (num >= 32) { |
0 |
0 |
0 |
|
| 229 |
0 |
| HighwayHashUpdatePacket(bytes, &state->state); |
| 230 |
0 |
| num -= 32; |
| 231 |
0 |
| bytes += 32; |
| 232 |
|
| } |
| 233 |
0 |
▶ | for (i = 0; i < num; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < num; i++) { |
0 |
0 |
0 |
|
| 234 |
0 |
| state->packet[state->num] = bytes[i]; |
| 235 |
0 |
| state->num++; |
| 236 |
|
| } |
| 237 |
0 |
| } |
| 238 |
|
| |
| 239 |
0 |
| uint64_t HighwayHashCatFinish64(const HighwayHashCat* state) { |
| 240 |
0 |
| HighwayHashState copy = state->state; |
| 241 |
0 |
▶ | if (state->num) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (state->num) { |
0 |
0 |
0 |
|
| 242 |
0 |
| HighwayHashUpdateRemainder(state->packet, state->num, ©); |
| 243 |
|
| } |
| 244 |
0 |
| return HighwayHashFinalize64(©); |
| 245 |
|
| } |
| 246 |
|
| |
| 247 |
0 |
| void HighwayHashCatFinish128(const HighwayHashCat* state, uint64_t hash[2]) { |
| 248 |
0 |
| HighwayHashState copy = state->state; |
| 249 |
0 |
▶ | if (state->num) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (state->num) { |
0 |
0 |
0 |
|
| 250 |
0 |
| HighwayHashUpdateRemainder(state->packet, state->num, ©); |
| 251 |
|
| } |
| 252 |
0 |
| HighwayHashFinalize128(©, hash); |
| 253 |
0 |
| } |
| 254 |
|
| |
| 255 |
0 |
| void HighwayHashCatFinish256(const HighwayHashCat* state, uint64_t hash[4]) { |
| 256 |
0 |
| HighwayHashState copy = state->state; |
| 257 |
0 |
▶ | if (state->num) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (state->num) { |
0 |
0 |
0 |
|
| 258 |
0 |
| HighwayHashUpdateRemainder(state->packet, state->num, ©); |
| 259 |
|
| } |
| 260 |
0 |
| HighwayHashFinalize256(©, hash); |
| 261 |
0 |
| } |