line |
stmt |
bran |
cond |
sub |
pod |
time |
code |
1
|
|
|
|
|
|
|
#include "highwayhash.h" |
2
|
|
|
|
|
|
|
|
3
|
|
|
|
|
|
|
#include |
4
|
|
|
|
|
|
|
#include |
5
|
|
|
|
|
|
|
#include |
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
|
276
|
|
|
|
|
|
*add0 += (((v0 & 0xff000000ull) | (v1 & 0xff00000000ull)) >> 24) | |
38
|
184
|
|
|
|
|
|
(((v0 & 0xff0000000000ull) | (v1 & 0xff000000000000ull)) >> 16) | |
39
|
276
|
|
|
|
|
|
(v0 & 0xff0000ull) | ((v0 & 0xff00ull) << 32) | |
40
|
184
|
|
|
|
|
|
((v1 & 0xff00000000000000ull) >> 8) | (v0 << 56); |
41
|
276
|
|
|
|
|
|
*add1 += (((v1 & 0xff000000ull) | (v0 & 0xff00000000ull)) >> 24) | |
42
|
276
|
|
|
|
|
|
(v1 & 0xff0000ull) | ((v1 & 0xff0000000000ull) >> 16) | |
43
|
276
|
|
|
|
|
|
((v1 & 0xff00ull) << 24) | ((v0 & 0xff000000000000ull) >> 8) | |
44
|
184
|
|
|
|
|
|
((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
|
100
|
|
|
|
|
for (i = 0; i < 4; ++i) { |
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
|
36
|
|
|
|
|
|
((uint64_t)src[2] << 16) | ((uint64_t)src[3] << 24) | |
64
|
36
|
|
|
|
|
|
((uint64_t)src[4] << 32) | ((uint64_t)src[5] << 40) | |
65
|
24
|
|
|
|
|
|
((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
|
100
|
|
|
|
|
for (i = 0; i < 4; ++i) { |
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
|
100
|
|
|
|
|
for (i = 0; i < 4; ++i) { |
94
|
12
|
|
|
|
|
|
state->v0[i] += ((uint64_t)size_mod32 << 32) + size_mod32; |
95
|
|
|
|
|
|
|
} |
96
|
3
|
|
|
|
|
|
Rotate32By(size_mod32, state->v1); |
97
|
15
|
100
|
|
|
|
|
for (i = 0; i < remainder - bytes; i++) { |
98
|
12
|
|
|
|
|
|
packet[i] = bytes[i]; |
99
|
|
|
|
|
|
|
} |
100
|
3
|
50
|
|
|
|
|
if (size_mod32 & 16) { |
101
|
0
|
0
|
|
|
|
|
for (i = 0; i < 4; i++) { |
102
|
0
|
|
|
|
|
|
packet[28 + i] = remainder[i + size_mod4 - 4]; |
103
|
|
|
|
|
|
|
} |
104
|
|
|
|
|
|
|
} else { |
105
|
3
|
50
|
|
|
|
|
if (size_mod4) { |
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
|
100
|
|
|
|
|
for (i = 0; i < 4; i++) { |
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
|
100
|
|
|
|
|
for (i = 0; i < 6; i++) { |
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
|
100
|
|
|
|
|
for (i = 0; i < 10; i++) { |
158
|
10
|
|
|
|
|
|
PermuteAndUpdate(state); |
159
|
|
|
|
|
|
|
} |
160
|
1
|
|
|
|
|
|
ModularReduction(state->v1[1] + state->mul1[1], state->v1[0] + state->mul1[0], |
161
|
2
|
|
|
|
|
|
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
|
2
|
|
|
|
|
|
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
|
50
|
|
|
|
|
for (i = 0; i + 32 <= size; i += 32) { |
177
|
0
|
|
|
|
|
|
HighwayHashUpdatePacket(data + i, state); |
178
|
|
|
|
|
|
|
} |
179
|
3
|
50
|
|
|
|
|
if ((size & 31) != 0) HighwayHashUpdateRemainder(data + i, size & 31, state); |
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
|
0
|
|
|
|
|
if (state->num != 0) { |
216
|
0
|
|
|
|
|
|
size_t num_add = num > (32u - state->num) ? (32u - state->num) : num; |
217
|
0
|
0
|
|
|
|
|
for (i = 0; i < num_add; i++) { |
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
|
0
|
|
|
|
|
if (state->num == 32) { |
224
|
0
|
|
|
|
|
|
HighwayHashUpdatePacket(state->packet, &state->state); |
225
|
0
|
|
|
|
|
|
state->num = 0; |
226
|
|
|
|
|
|
|
} |
227
|
|
|
|
|
|
|
} |
228
|
0
|
0
|
|
|
|
|
while (num >= 32) { |
229
|
0
|
|
|
|
|
|
HighwayHashUpdatePacket(bytes, &state->state); |
230
|
0
|
|
|
|
|
|
num -= 32; |
231
|
0
|
|
|
|
|
|
bytes += 32; |
232
|
|
|
|
|
|
|
} |
233
|
0
|
0
|
|
|
|
|
for (i = 0; i < num; i++) { |
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
|
0
|
|
|
|
|
if (state->num) { |
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
|
0
|
|
|
|
|
if (state->num) { |
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
|
0
|
|
|
|
|
if (state->num) { |
258
|
0
|
|
|
|
|
|
HighwayHashUpdateRemainder(state->packet, state->num, ©); |
259
|
|
|
|
|
|
|
} |
260
|
0
|
|
|
|
|
|
HighwayHashFinalize256(©, hash); |
261
|
0
|
|
|
|
|
|
} |