highwayhash/c/highwayhash.c

filter: Statementstmt 74.1% 123 / 166 Branchbran 45.0% 18 / 40 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 68.4% 141 / 206 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« perl_math_int64.c ↑ Summary HighwayHash.xs »
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
if (size_mod32 & 16) { 0 3 3
101 0 ▶ for (i = 0; i < 4; i++) {
Branch: 1 branch
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
if (state->num) { 0 0 0
242 0 HighwayHashUpdateRemainder(state->packet, state->num, &copy);
243 }
244 0 return HighwayHashFinalize64(&copy);
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
BranchTrueFalseTotal
if (state->num) { 0 0 0
250 0 HighwayHashUpdateRemainder(state->packet, state->num, &copy);
251 }
252 0 HighwayHashFinalize128(&copy, 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
BranchTrueFalseTotal
if (state->num) { 0 0 0
258 0 HighwayHashUpdateRemainder(state->packet, state->num, &copy);
259 }
260 0 HighwayHashFinalize256(&copy, hash);
261 0 }
« perl_math_int64.c ↑ Summary HighwayHash.xs »