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(deUint32 val,deUint32 count)36 static deUint32 leftRotate (deUint32 val, deUint32 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(deUint32));
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(stream->data[ndx - 3]
68 ^ stream->data[ndx - 8]
69 ^ stream->data[ndx - 14]
70 ^ stream->data[ndx - 16], 1);
71 }
72 }
73
74 {
75 deUint32 a = stream->hash[0];
76 deUint32 b = stream->hash[1];
77 deUint32 c = stream->hash[2];
78 deUint32 d = stream->hash[3];
79 deUint32 e = stream->hash[4];
80 size_t ndx;
81
82 for (ndx = 0; ndx < DE_LENGTH_OF_ARRAY(stream->data); ndx++)
83 {
84 deUint32 f;
85 deUint32 k;
86
87 if (ndx < 20)
88 {
89 f = (b & c) | ((~b) & d);
90 k = 0x5A827999u;
91 }
92 else if (ndx < 40)
93 {
94 f = b ^ c ^ d;
95 k = 0x6ED9EBA1u;
96 }
97 else if (ndx < 60)
98 {
99 f = (b & c) | (b & d) | (c & d);
100 k = 0x8F1BBCDCu;
101 }
102 else
103 {
104 f = b ^ c ^ d;
105 k = 0xCA62C1D6u;
106 }
107
108 {
109 const deUint32 tmp = leftRotate(a, 5) + f + e + k + stream->data[ndx];
110
111 e = d;
112 d = c;
113 c = leftRotate(b, 30);
114 b = a;
115 a = tmp;
116 }
117 }
118
119 stream->hash[0] += a;
120 stream->hash[1] += b;
121 stream->hash[2] += c;
122 stream->hash[3] += d;
123 stream->hash[4] += e;
124
125 /* Set the initial 16 deUint32s that contain the real data to zeros. */
126 deMemset(stream->data, 0, 16 * sizeof(deUint32));
127 }
128 }
129
deSha1Stream_process(deSha1Stream * stream,size_t size,const void * data_)130 void deSha1Stream_process (deSha1Stream* stream, size_t size, const void* data_)
131 {
132 const deUint8* const data = (const deUint8*)data_;
133 size_t bytesProcessed = 0;
134
135 while (bytesProcessed < size)
136 {
137 do
138 {
139 const size_t bitOffset = (size_t)(8 * (4 - (1 + (stream->size % 4))));
140
141 stream->data[(stream->size / 4) % 16] |= ((deUint32)data[bytesProcessed]) << (deUint32)bitOffset;
142
143 stream->size++;
144 bytesProcessed++;
145 }
146 while (stream->size % CHUNK_BYTE_SIZE != 0 && bytesProcessed < size);
147
148 if (stream->size % CHUNK_BYTE_SIZE == 0)
149 deSha1Stream_flushChunk(stream);
150 }
151
152 DE_ASSERT(bytesProcessed == size);
153 }
154
deSha1Stream_finalize(deSha1Stream * stream,deSha1 * hash)155 void deSha1Stream_finalize (deSha1Stream* stream, deSha1* hash)
156 {
157 /* \note First element is initialized to 0x80u and rest to 0x0. */
158 static const deUint8 padding[CHUNK_BYTE_SIZE] = { 0x80u };
159 const deUint64 length = stream->size * 8;
160 deUint8 lengthData[sizeof(deUint64)];
161 size_t ndx;
162
163 DE_ASSERT(padding[0] == 0x80u);
164 DE_ASSERT(padding[1] == 0x0u);
165
166 for (ndx = 0; ndx < sizeof(deUint64); ndx++)
167 lengthData[ndx] = (deUint8)(0xffu & (length >> (8 * (sizeof(deUint64) - 1 - ndx))));
168
169 {
170 const deUint64 spaceLeftInChunk = CHUNK_BYTE_SIZE - (stream->size % CHUNK_BYTE_SIZE);
171
172 /* The stream must be a multiple of 512 bits (CHUNK_BYTE_SIZE) and is terminated by a single bit set to 1,
173 * then 7 or more 0 bits, then finally the last 64 bits are the message length. */
174
175 if (spaceLeftInChunk >= 1 + sizeof(lengthData))
176 {
177 /* There's room for a 0x80 byte and zero or more 0x0 padding bytes. */
178 deSha1Stream_process(stream, (size_t)(spaceLeftInChunk - sizeof(lengthData)), padding);
179 }
180 else
181 {
182 /* 0x80 and the message length won't fit in this chunk, we need to add a whole new chunk of zero padding,
183 * which will include the message length at the end. */
184 deSha1Stream_process(stream, (size_t)(spaceLeftInChunk), padding);
185 deSha1Stream_process(stream, (size_t)(CHUNK_BYTE_SIZE - sizeof(lengthData)), padding + spaceLeftInChunk);
186 }
187 }
188
189 deSha1Stream_process(stream, sizeof(lengthData), lengthData);
190 DE_ASSERT(stream->size % CHUNK_BYTE_SIZE == 0);
191
192 deMemcpy(hash->hash, stream->hash, sizeof(hash->hash));
193 }
194
deSha1_compute(deSha1 * hash,size_t size,const void * data)195 void deSha1_compute (deSha1* hash, size_t size, const void* data)
196 {
197 deSha1Stream stream;
198
199 deSha1Stream_init(&stream);
200 deSha1Stream_process(&stream, size, data);
201 deSha1Stream_finalize(&stream, hash);
202 }
203
deSha1_render(const deSha1 * hash,char * buffer)204 void deSha1_render (const deSha1* hash, char* buffer)
205 {
206 size_t charNdx;
207
208 for (charNdx = 0; charNdx < 40; charNdx++)
209 {
210 const deUint32 val32 = hash->hash[charNdx / 8];
211 const deUint8 val8 = (deUint8)(0x0fu & (val32 >> (4 * (8 - 1 - (charNdx % 8)))));
212
213 if (val8 < 10)
214 buffer[charNdx] = (char)('0' + val8);
215 else
216 buffer[charNdx] = (char)('a' + val8 - 10);
217 }
218 }
219
deSha1_parse(deSha1 * hash,const char * buffer)220 deBool deSha1_parse (deSha1* hash, const char* buffer)
221 {
222 size_t charNdx;
223
224 deMemset(hash->hash, 0, sizeof(hash->hash));
225
226 for (charNdx = 0; charNdx < 40; charNdx++)
227 {
228 deUint8 val4;
229
230 if (buffer[charNdx] >= '0' && buffer[charNdx] <= '9')
231 val4 = (deUint8)(buffer[charNdx] - '0');
232 else if (buffer[charNdx] >= 'a' && buffer[charNdx] <= 'f')
233 val4 = (deUint8)(10 + (buffer[charNdx] - 'a'));
234 else if (buffer[charNdx] >= 'A' && buffer[charNdx] <= 'F')
235 val4 = (deUint8)(10 + (buffer[charNdx] - 'A'));
236 else
237 return DE_FALSE;
238
239 hash->hash[charNdx / 8] |= ((deUint32)val4) << (4 * (8u - 1u - (charNdx % 8u)));
240 }
241
242 return DE_TRUE;
243 }
244
deSha1_equal(const deSha1 * a,const deSha1 * b)245 deBool deSha1_equal (const deSha1* a, const deSha1* b)
246 {
247 /* \note deMemcmp() can only be used for equality. It doesn't provide correct ordering between hashes. */
248 return deMemCmp(a->hash, b->hash, sizeof(b->hash)) == 0;
249 }
250
deSha1_selfTest(void)251 void deSha1_selfTest (void)
252 {
253 const char* const validHashStrings[] =
254 {
255 "ac890cfca05717c05dc831996b2289251da2984e",
256 "0f87ba807acb3e6effe617249f30453a524a2ea3",
257 "6f483cc3fa820e58ed9f83c83bdf8d213293b3ad"
258 };
259
260 const char* const invalidHashStrings[] =
261 {
262 " c890cfca05717c05dc831996b2289251da2984e",
263 "0f87ba807acb3e6 ffe617249f30453a524a2ea3",
264 "6f483cc3fa820e58ed9f83c83bdf8d213293b3a ",
265
266 "mc890cfca05717c05dc831996b2289251da2984e",
267 "0f87ba807acb3e6effe617249fm0453a524a2ea3",
268 "6f483cc3fa820e58ed9f83c83bdf8d213293b3an",
269
270 "ac890cfca05717c05dc83\n996b2289251da2984e",
271 "0f87ba807acb3e6effe617\t49f30453a524a2ea3",
272 "ac890cfca05717c05dc831\096b2289251da2984e",
273 "6f483cc3fa{20e58ed9f83c83bdf8d213293b3ad"
274 };
275
276 const struct
277 {
278 const char* const hash;
279 const char* const data;
280 } stringHashPairs[] =
281 {
282 /* Generated using sha1sum. */
283 { "da39a3ee5e6b4b0d3255bfef95601890afd80709", "" },
284 { "aaf4c61ddcc5e8a2dabede0f3b482cd9aea9434d", "hello" },
285 { "ec1919e856540f42bd0e6f6c1ffe2fbd73419975",
286 "Cherry is a browser-based GUI for controlling deqp test runs and analysing the test results."
287 },
288 { "27a4485e4fe6dff5bcc1cc3093639e27c65c55c0",
289 "This message has exactly 56 characters and that's tricky"
290 }
291 };
292
293 const int garbage = 0xde;
294
295 /* Test parsing valid sha1 strings. */
296 {
297 size_t stringNdx;
298
299 for (stringNdx = 0; stringNdx < DE_LENGTH_OF_ARRAY(validHashStrings); stringNdx++)
300 {
301 deSha1 hash;
302 deMemset(&hash, garbage, sizeof(deSha1));
303 DE_TEST_ASSERT(deSha1_parse(&hash, validHashStrings[stringNdx]));
304 }
305 }
306
307 /* Test parsing invalid sha1 strings. */
308 {
309 size_t stringNdx;
310
311 for (stringNdx = 0; stringNdx < DE_LENGTH_OF_ARRAY(invalidHashStrings); stringNdx++)
312 {
313 deSha1 hash;
314 deMemset(&hash, garbage, sizeof(deSha1));
315 DE_TEST_ASSERT(!deSha1_parse(&hash, invalidHashStrings[stringNdx]));
316 }
317 }
318
319 /* Compare valid hash strings for equality. */
320 {
321 size_t stringNdx;
322
323 for (stringNdx = 0; stringNdx < DE_LENGTH_OF_ARRAY(validHashStrings); stringNdx++)
324 {
325 deSha1 hashA;
326 deSha1 hashB;
327
328 deMemset(&hashA, garbage, sizeof(deSha1));
329 deMemset(&hashB, garbage, sizeof(deSha1));
330
331 DE_TEST_ASSERT(deSha1_parse(&hashA, validHashStrings[stringNdx]));
332 DE_TEST_ASSERT(deSha1_parse(&hashB, validHashStrings[stringNdx]));
333
334 DE_TEST_ASSERT(deSha1_equal(&hashA, &hashA));
335 DE_TEST_ASSERT(deSha1_equal(&hashA, &hashB));
336 DE_TEST_ASSERT(deSha1_equal(&hashB, &hashA));
337 }
338 }
339
340 /* Compare valid different hash strings for equality. */
341 {
342 size_t stringANdx;
343 size_t stringBNdx;
344
345 for (stringANdx = 0; stringANdx < DE_LENGTH_OF_ARRAY(validHashStrings); stringANdx++)
346 for (stringBNdx = 0; stringBNdx < DE_LENGTH_OF_ARRAY(validHashStrings); stringBNdx++)
347 {
348 deSha1 hashA;
349 deSha1 hashB;
350
351 if (stringANdx == stringBNdx)
352 continue;
353
354 deMemset(&hashA, garbage, sizeof(deSha1));
355 deMemset(&hashB, garbage, sizeof(deSha1));
356
357 DE_TEST_ASSERT(deSha1_parse(&hashA, validHashStrings[stringANdx]));
358 DE_TEST_ASSERT(deSha1_parse(&hashB, validHashStrings[stringBNdx]));
359
360 DE_TEST_ASSERT(!deSha1_equal(&hashA, &hashB));
361 DE_TEST_ASSERT(!deSha1_equal(&hashB, &hashA));
362 }
363 }
364
365 /* Test rendering hash as string. */
366 {
367 size_t stringNdx;
368
369 for (stringNdx = 0; stringNdx < DE_LENGTH_OF_ARRAY(validHashStrings); stringNdx++)
370 {
371 char result[40];
372 deSha1 hash;
373
374 deMemset(&hash, garbage, sizeof(hash));
375 deMemset(&result, garbage, sizeof(result));
376
377 DE_TEST_ASSERT(deSha1_parse(&hash, validHashStrings[stringNdx]));
378 deSha1_render(&hash, result);
379
380 DE_TEST_ASSERT(strncmp(result, validHashStrings[stringNdx], 40) == 0);
381 }
382 }
383
384 /* Test hash against few pre-computed cases. */
385 {
386 size_t ndx;
387
388 for (ndx = 0; ndx < DE_LENGTH_OF_ARRAY(stringHashPairs); ndx++)
389 {
390 deSha1 result;
391 deSha1 reference;
392
393 deSha1_compute(&result, strlen(stringHashPairs[ndx].data), stringHashPairs[ndx].data);
394 DE_TEST_ASSERT(deSha1_parse(&reference, stringHashPairs[ndx].hash));
395
396 DE_TEST_ASSERT(deSha1_equal(&reference, &result));
397 }
398 }
399
400 /* Test hash stream against few pre-computed cases. */
401 {
402 size_t ndx;
403
404 for (ndx = 0; ndx < DE_LENGTH_OF_ARRAY(stringHashPairs); ndx++)
405 {
406 const char* const data = stringHashPairs[ndx].data;
407 const size_t size = strlen(data);
408
409 deSha1Stream stream;
410 deSha1 result;
411 deSha1 reference;
412
413 deSha1Stream_init(&stream);
414
415 deSha1Stream_process(&stream, size/2, data);
416 deSha1Stream_process(&stream, size - (size/2), data + size/2);
417
418 deSha1Stream_finalize(&stream, &result);
419
420 deSha1_compute(&result, strlen(stringHashPairs[ndx].data), stringHashPairs[ndx].data);
421 DE_TEST_ASSERT(deSha1_parse(&reference, stringHashPairs[ndx].hash));
422
423 DE_TEST_ASSERT(deSha1_equal(&reference, &result));
424 }
425 }
426 }
427
428 DE_END_EXTERN_C
429