1 /*-------------------------------------------------------------------------
2 * drawElements Base Portability Library
3 * -------------------------------------
4 *
5 * Copyright 2015 The Android Open Source Project
6 *
7 * Licensed under the Apache License, Version 2.0 (the "License");
8 * you may not use this file except in compliance with the License.
9 * You may obtain a copy of the License at
10 *
11 * http://www.apache.org/licenses/LICENSE-2.0
12 *
13 * Unless required by applicable law or agreed to in writing, software
14 * distributed under the License is distributed on an "AS IS" BASIS,
15 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16 * See the License for the specific language governing permissions and
17 * limitations under the License.
18 *
19 *//*!
20 * \file
21 * \brief SHA1 hash functions.
22 *//*--------------------------------------------------------------------*/
23
24 #include "deSha1.h"
25
26 #include "deMemory.h"
27
28 DE_BEGIN_EXTERN_C
29
30 enum
31 {
32 CHUNK_BIT_SIZE = 512,
33 CHUNK_BYTE_SIZE = CHUNK_BIT_SIZE / 8
34 };
35
leftRotate(uint32_t val,uint32_t count)36 static uint32_t leftRotate(uint32_t val, uint32_t count)
37 {
38 DE_ASSERT(count < 32);
39
40 return (val << count) | (val >> (32 - count));
41 }
42
deSha1Stream_init(deSha1Stream * stream)43 void deSha1Stream_init(deSha1Stream *stream)
44 {
45 stream->size = 0;
46
47 /* Set the initial 16 deUint32s that contain real data to zeros. */
48 deMemset(stream->data, 0, 16 * sizeof(uint32_t));
49
50 stream->hash[0] = 0x67452301u;
51 stream->hash[1] = 0xEFCDAB89u;
52 stream->hash[2] = 0x98BADCFEu;
53 stream->hash[3] = 0x10325476u;
54 stream->hash[4] = 0xC3D2E1F0u;
55 }
56
deSha1Stream_flushChunk(deSha1Stream * stream)57 static void deSha1Stream_flushChunk(deSha1Stream *stream)
58 {
59 DE_ASSERT(stream->size % CHUNK_BYTE_SIZE == 0 && stream->size > 0);
60
61 {
62 size_t ndx;
63
64 /* Expand the 16 uint32s that contain the data to 80. */
65 for (ndx = 16; ndx < DE_LENGTH_OF_ARRAY(stream->data); ndx++)
66 {
67 stream->data[ndx] = leftRotate(
68 stream->data[ndx - 3] ^ stream->data[ndx - 8] ^ stream->data[ndx - 14] ^ stream->data[ndx - 16], 1);
69 }
70 }
71
72 {
73 uint32_t a = stream->hash[0];
74 uint32_t b = stream->hash[1];
75 uint32_t c = stream->hash[2];
76 uint32_t d = stream->hash[3];
77 uint32_t e = stream->hash[4];
78 size_t ndx;
79
80 for (ndx = 0; ndx < DE_LENGTH_OF_ARRAY(stream->data); ndx++)
81 {
82 uint32_t f;
83 uint32_t k;
84
85 if (ndx < 20)
86 {
87 f = (b & c) | ((~b) & d);
88 k = 0x5A827999u;
89 }
90 else if (ndx < 40)
91 {
92 f = b ^ c ^ d;
93 k = 0x6ED9EBA1u;
94 }
95 else if (ndx < 60)
96 {
97 f = (b & c) | (b & d) | (c & d);
98 k = 0x8F1BBCDCu;
99 }
100 else
101 {
102 f = b ^ c ^ d;
103 k = 0xCA62C1D6u;
104 }
105
106 {
107 const uint32_t tmp = leftRotate(a, 5) + f + e + k + stream->data[ndx];
108
109 e = d;
110 d = c;
111 c = leftRotate(b, 30);
112 b = a;
113 a = tmp;
114 }
115 }
116
117 stream->hash[0] += a;
118 stream->hash[1] += b;
119 stream->hash[2] += c;
120 stream->hash[3] += d;
121 stream->hash[4] += e;
122
123 /* Set the initial 16 deUint32s that contain the real data to zeros. */
124 deMemset(stream->data, 0, 16 * sizeof(uint32_t));
125 }
126 }
127
deSha1Stream_process(deSha1Stream * stream,size_t size,const void * data_)128 void deSha1Stream_process(deSha1Stream *stream, size_t size, const void *data_)
129 {
130 const uint8_t *const data = (const uint8_t *)data_;
131 size_t bytesProcessed = 0;
132
133 while (bytesProcessed < size)
134 {
135 do
136 {
137 const size_t bitOffset = (size_t)(8 * (4 - (1 + (stream->size % 4))));
138
139 stream->data[(stream->size / 4) % 16] |= ((uint32_t)data[bytesProcessed]) << (uint32_t)bitOffset;
140
141 stream->size++;
142 bytesProcessed++;
143 } while (stream->size % CHUNK_BYTE_SIZE != 0 && bytesProcessed < size);
144
145 if (stream->size % CHUNK_BYTE_SIZE == 0)
146 deSha1Stream_flushChunk(stream);
147 }
148
149 DE_ASSERT(bytesProcessed == size);
150 }
151
deSha1Stream_finalize(deSha1Stream * stream,deSha1 * hash)152 void deSha1Stream_finalize(deSha1Stream *stream, deSha1 *hash)
153 {
154 /* \note First element is initialized to 0x80u and rest to 0x0. */
155 static const uint8_t padding[CHUNK_BYTE_SIZE] = {0x80u};
156 const uint64_t length = stream->size * 8;
157 uint8_t lengthData[sizeof(uint64_t)];
158 size_t ndx;
159
160 DE_ASSERT(padding[0] == 0x80u);
161 DE_ASSERT(padding[1] == 0x0u);
162
163 for (ndx = 0; ndx < sizeof(uint64_t); ndx++)
164 lengthData[ndx] = (uint8_t)(0xffu & (length >> (8 * (sizeof(uint64_t) - 1 - ndx))));
165
166 {
167 const uint64_t spaceLeftInChunk = CHUNK_BYTE_SIZE - (stream->size % CHUNK_BYTE_SIZE);
168
169 /* The stream must be a multiple of 512 bits (CHUNK_BYTE_SIZE) and is terminated by a single bit set to 1,
170 * then 7 or more 0 bits, then finally the last 64 bits are the message length. */
171
172 if (spaceLeftInChunk >= 1 + sizeof(lengthData))
173 {
174 /* There's room for a 0x80 byte and zero or more 0x0 padding bytes. */
175 deSha1Stream_process(stream, (size_t)(spaceLeftInChunk - sizeof(lengthData)), padding);
176 }
177 else
178 {
179 /* 0x80 and the message length won't fit in this chunk, we need to add a whole new chunk of zero padding,
180 * which will include the message length at the end. */
181 deSha1Stream_process(stream, (size_t)(spaceLeftInChunk), padding);
182 deSha1Stream_process(stream, (size_t)(CHUNK_BYTE_SIZE - sizeof(lengthData)), padding + spaceLeftInChunk);
183 }
184 }
185
186 deSha1Stream_process(stream, sizeof(lengthData), lengthData);
187 DE_ASSERT(stream->size % CHUNK_BYTE_SIZE == 0);
188
189 deMemcpy(hash->hash, stream->hash, sizeof(hash->hash));
190 }
191
deSha1_compute(deSha1 * hash,size_t size,const void * data)192 void deSha1_compute(deSha1 *hash, size_t size, const void *data)
193 {
194 deSha1Stream stream;
195
196 deSha1Stream_init(&stream);
197 deSha1Stream_process(&stream, size, data);
198 deSha1Stream_finalize(&stream, hash);
199 }
200
deSha1_render(const deSha1 * hash,char * buffer)201 void deSha1_render(const deSha1 *hash, char *buffer)
202 {
203 size_t charNdx;
204
205 for (charNdx = 0; charNdx < 40; charNdx++)
206 {
207 const uint32_t val32 = hash->hash[charNdx / 8];
208 const uint8_t val8 = (uint8_t)(0x0fu & (val32 >> (4 * (8 - 1 - (charNdx % 8)))));
209
210 if (val8 < 10)
211 buffer[charNdx] = (char)('0' + val8);
212 else
213 buffer[charNdx] = (char)('a' + val8 - 10);
214 }
215 }
216
deSha1_parse(deSha1 * hash,const char * buffer)217 bool deSha1_parse(deSha1 *hash, const char *buffer)
218 {
219 size_t charNdx;
220
221 deMemset(hash->hash, 0, sizeof(hash->hash));
222
223 for (charNdx = 0; charNdx < 40; charNdx++)
224 {
225 uint8_t val4;
226
227 if (buffer[charNdx] >= '0' && buffer[charNdx] <= '9')
228 val4 = (uint8_t)(buffer[charNdx] - '0');
229 else if (buffer[charNdx] >= 'a' && buffer[charNdx] <= 'f')
230 val4 = (uint8_t)(10 + (buffer[charNdx] - 'a'));
231 else if (buffer[charNdx] >= 'A' && buffer[charNdx] <= 'F')
232 val4 = (uint8_t)(10 + (buffer[charNdx] - 'A'));
233 else
234 return false;
235
236 hash->hash[charNdx / 8] |= ((uint32_t)val4) << (4 * (8u - 1u - (charNdx % 8u)));
237 }
238
239 return true;
240 }
241
deSha1_equal(const deSha1 * a,const deSha1 * b)242 bool deSha1_equal(const deSha1 *a, const deSha1 *b)
243 {
244 /* \note deMemcmp() can only be used for equality. It doesn't provide correct ordering between hashes. */
245 return deMemCmp(a->hash, b->hash, sizeof(b->hash)) == 0;
246 }
247
deSha1_selfTest(void)248 void deSha1_selfTest(void)
249 {
250 const char *const validHashStrings[] = {"ac890cfca05717c05dc831996b2289251da2984e",
251 "0f87ba807acb3e6effe617249f30453a524a2ea3",
252 "6f483cc3fa820e58ed9f83c83bdf8d213293b3ad"};
253
254 const char *const invalidHashStrings[] = {
255 " c890cfca05717c05dc831996b2289251da2984e", "0f87ba807acb3e6 ffe617249f30453a524a2ea3",
256 "6f483cc3fa820e58ed9f83c83bdf8d213293b3a ",
257
258 "mc890cfca05717c05dc831996b2289251da2984e", "0f87ba807acb3e6effe617249fm0453a524a2ea3",
259 "6f483cc3fa820e58ed9f83c83bdf8d213293b3an",
260
261 "ac890cfca05717c05dc83\n996b2289251da2984e", "0f87ba807acb3e6effe617\t49f30453a524a2ea3",
262 "ac890cfca05717c05dc831\096b2289251da2984e", "6f483cc3fa{20e58ed9f83c83bdf8d213293b3ad"};
263
264 const struct
265 {
266 const char *const hash;
267 const char *const data;
268 } stringHashPairs[] = {
269 /* Generated using sha1sum. */
270 {"da39a3ee5e6b4b0d3255bfef95601890afd80709", ""},
271 {"aaf4c61ddcc5e8a2dabede0f3b482cd9aea9434d", "hello"},
272 {"ec1919e856540f42bd0e6f6c1ffe2fbd73419975",
273 "Cherry is a browser-based GUI for controlling deqp test runs and analysing the test results."},
274 {"27a4485e4fe6dff5bcc1cc3093639e27c65c55c0", "This message has exactly 56 characters and that's tricky"}};
275
276 const int garbage = 0xde;
277
278 /* Test parsing valid sha1 strings. */
279 {
280 size_t stringNdx;
281
282 for (stringNdx = 0; stringNdx < DE_LENGTH_OF_ARRAY(validHashStrings); stringNdx++)
283 {
284 deSha1 hash;
285 deMemset(&hash, garbage, sizeof(deSha1));
286 DE_TEST_ASSERT(deSha1_parse(&hash, validHashStrings[stringNdx]));
287 }
288 }
289
290 /* Test parsing invalid sha1 strings. */
291 {
292 size_t stringNdx;
293
294 for (stringNdx = 0; stringNdx < DE_LENGTH_OF_ARRAY(invalidHashStrings); stringNdx++)
295 {
296 deSha1 hash;
297 deMemset(&hash, garbage, sizeof(deSha1));
298 DE_TEST_ASSERT(!deSha1_parse(&hash, invalidHashStrings[stringNdx]));
299 }
300 }
301
302 /* Compare valid hash strings for equality. */
303 {
304 size_t stringNdx;
305
306 for (stringNdx = 0; stringNdx < DE_LENGTH_OF_ARRAY(validHashStrings); stringNdx++)
307 {
308 deSha1 hashA;
309 deSha1 hashB;
310
311 deMemset(&hashA, garbage, sizeof(deSha1));
312 deMemset(&hashB, garbage, sizeof(deSha1));
313
314 DE_TEST_ASSERT(deSha1_parse(&hashA, validHashStrings[stringNdx]));
315 DE_TEST_ASSERT(deSha1_parse(&hashB, validHashStrings[stringNdx]));
316
317 DE_TEST_ASSERT(deSha1_equal(&hashA, &hashA));
318 DE_TEST_ASSERT(deSha1_equal(&hashA, &hashB));
319 DE_TEST_ASSERT(deSha1_equal(&hashB, &hashA));
320 }
321 }
322
323 /* Compare valid different hash strings for equality. */
324 {
325 size_t stringANdx;
326 size_t stringBNdx;
327
328 for (stringANdx = 0; stringANdx < DE_LENGTH_OF_ARRAY(validHashStrings); stringANdx++)
329 for (stringBNdx = 0; stringBNdx < DE_LENGTH_OF_ARRAY(validHashStrings); stringBNdx++)
330 {
331 deSha1 hashA;
332 deSha1 hashB;
333
334 if (stringANdx == stringBNdx)
335 continue;
336
337 deMemset(&hashA, garbage, sizeof(deSha1));
338 deMemset(&hashB, garbage, sizeof(deSha1));
339
340 DE_TEST_ASSERT(deSha1_parse(&hashA, validHashStrings[stringANdx]));
341 DE_TEST_ASSERT(deSha1_parse(&hashB, validHashStrings[stringBNdx]));
342
343 DE_TEST_ASSERT(!deSha1_equal(&hashA, &hashB));
344 DE_TEST_ASSERT(!deSha1_equal(&hashB, &hashA));
345 }
346 }
347
348 /* Test rendering hash as string. */
349 {
350 size_t stringNdx;
351
352 for (stringNdx = 0; stringNdx < DE_LENGTH_OF_ARRAY(validHashStrings); stringNdx++)
353 {
354 char result[40];
355 deSha1 hash;
356
357 deMemset(&hash, garbage, sizeof(hash));
358 deMemset(&result, garbage, sizeof(result));
359
360 DE_TEST_ASSERT(deSha1_parse(&hash, validHashStrings[stringNdx]));
361 deSha1_render(&hash, result);
362
363 DE_TEST_ASSERT(strncmp(result, validHashStrings[stringNdx], 40) == 0);
364 }
365 }
366
367 /* Test hash against few pre-computed cases. */
368 {
369 size_t ndx;
370
371 for (ndx = 0; ndx < DE_LENGTH_OF_ARRAY(stringHashPairs); ndx++)
372 {
373 deSha1 result;
374 deSha1 reference;
375
376 deSha1_compute(&result, strlen(stringHashPairs[ndx].data), stringHashPairs[ndx].data);
377 DE_TEST_ASSERT(deSha1_parse(&reference, stringHashPairs[ndx].hash));
378
379 DE_TEST_ASSERT(deSha1_equal(&reference, &result));
380 }
381 }
382
383 /* Test hash stream against few pre-computed cases. */
384 {
385 size_t ndx;
386
387 for (ndx = 0; ndx < DE_LENGTH_OF_ARRAY(stringHashPairs); ndx++)
388 {
389 const char *const data = stringHashPairs[ndx].data;
390 const size_t size = strlen(data);
391
392 deSha1Stream stream;
393 deSha1 result;
394 deSha1 reference;
395
396 deSha1Stream_init(&stream);
397
398 deSha1Stream_process(&stream, size / 2, data);
399 deSha1Stream_process(&stream, size - (size / 2), data + size / 2);
400
401 deSha1Stream_finalize(&stream, &result);
402
403 deSha1_compute(&result, strlen(stringHashPairs[ndx].data), stringHashPairs[ndx].data);
404 DE_TEST_ASSERT(deSha1_parse(&reference, stringHashPairs[ndx].hash));
405
406 DE_TEST_ASSERT(deSha1_equal(&reference, &result));
407 }
408 }
409 }
410
411 DE_END_EXTERN_C
412