File Coverage

highwayhash/c/highwayhash.c
Criterion Covered Total %
statement 123 166 74.1
branch 18 40 45.0
condition n/a
subroutine n/a
pod n/a
total 141 206 68.4


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           }