ff582ed9da50ccaa2429b3ae6a6e2ce145ccc284
[wimlib] / src / sha1.c
1 /* sha1.c - Functions to compute SHA1 message digest of files or
2    memory blocks according to the NIST specification FIPS-180-1.
3
4    Copyright (C) 2000-2001, 2003-2006, 2008-2011 Free Software Foundation, Inc.
5
6    This program is free software; you can redistribute it and/or modify it
7    under the terms of the GNU General Public License as published by the
8    Free Software Foundation; either version 3, or (at your option) any
9    later version.
10
11    This program is distributed in the hope that it will be useful,
12    but WITHOUT ANY WARRANTY; without even the implied warranty of
13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14    GNU General Public License for more details.
15
16    You should have received a copy of the GNU General Public License
17    along with this program; if not, write to the Free Software Foundation,
18    Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
19
20 /* Written by Scott G. Miller
21    Credits:
22       Robert Klep <robert@ilse.nl>  -- Expansion function fix
23
24    Modified by Eric Biggers for wimlib:  Conditionally compile in the use of
25    OpenSSL or Intel's assembly code for SHA1 block updates
26 */
27
28 #include "util.h"
29 #include "wimlib.h"
30 #include "sha1.h"
31 #include "endianness.h"
32 #include <string.h>
33
34 #define SWAP(n) to_be32(n)
35
36 #define BLOCKSIZE 32768
37 #if BLOCKSIZE % 64 != 0
38 #error "invalid BLOCKSIZE"
39 #endif
40
41 const u8 empty_file_sha1sum[SHA1_HASH_SIZE] = {
42         0xda, 0x39, 0xa3, 0xee, 0x5e, 0x6b, 0x4b, 0x0d, 0x32, 0x55, 
43         0xbf, 0xef, 0x95, 0x60, 0x18, 0x90, 0xaf, 0xd8, 0x07, 0x09,
44 };
45
46
47 #ifdef WITH_LIBCRYPTO
48
49 static inline void sha1_init_ctx(SHA_CTX *ctx)
50 {
51         SHA1_Init(ctx);
52 }
53
54 static inline void sha1_process_block(const void *buffer, size_t len, 
55                                       SHA_CTX *ctx)
56 {
57         SHA1_Update(ctx, buffer, len);
58 }
59
60 static inline void sha1_process_bytes(const void *buffer, size_t len, 
61                                       SHA_CTX *ctx)
62 {
63         SHA1_Update(ctx, buffer, len);
64 }
65
66
67 static inline void *sha1_finish_ctx(SHA_CTX *ctx, void *resbuf)
68 {
69         SHA1_Final(resbuf, ctx);
70 }
71 #else /* WITH_LIBCRYPTO */
72
73 /* Structure to save state of computation between the single steps.  */
74 struct sha1_ctx {
75         uint32_t A;
76         uint32_t B;
77         uint32_t C;
78         uint32_t D;
79         uint32_t E;
80
81         uint32_t total[2];
82         uint32_t buflen;
83         uint32_t buffer[32];
84 };
85
86 typedef struct sha1_ctx SHA_CTX;
87
88 #ifdef ENABLE_SSSE3_SHA1
89 extern void sha1_update_intel(int *hash, const char* input, size_t num_blocks);
90
91 static inline void sha1_process_block(const void *buffer, size_t len, 
92                                       SHA_CTX *ctx)
93 {
94         sha1_update_intel((int*)ctx, buffer, len / 64);
95         ctx->total[0] += len;
96         if (ctx->total[0] < len)
97                 ++ctx->total[1];
98 }
99
100 #include <stdlib.h>
101 void ssse3_not_found()
102 {
103         fprintf(stderr, 
104 "Cannot calculate SHA1 message digest: CPU does not support SSSE3\n"
105 "instructions!  Recompile wimlib without the --enable-ssse3-sha1 flag\n"
106 "to use wimlib on this CPU.\n");
107         abort();
108 }
109 #else /* ENABLE_SSSE3_SHA1 */
110
111 static void sha1_process_block(const void *buffer, size_t len,
112                                SHA_CTX *ctx);
113
114 #endif /* ENABLE_SSSE3_SHA1 */
115
116
117 /* This array contains the bytes used to pad the buffer to the next
118    64-byte boundary.  (RFC 1321, 3.1: Step 1)  */
119 static const u8 fillbuf[64] = { 0x80, 0 /* , 0, 0, ...  */  };
120
121 /* Initialize structure containing state of computation. */
122 static void sha1_init_ctx(SHA_CTX *ctx);
123
124 /* Starting with the result of former calls of this function (or the
125    initialization function update the context for the next LEN bytes
126    starting at BUFFER.
127    It is NOT required that LEN is a multiple of 64.  */
128 static void sha1_process_bytes(const void *buffer, size_t len,
129                                SHA_CTX *ctx);
130
131 /* Process the remaining bytes in the buffer and put result from CTX
132    in first 20 bytes following RESBUF.  The result is always in little
133    endian byte order, so that a byte-wise output yields to the wanted
134    ASCII representation of the message digest.  */
135 static void *sha1_finish_ctx(SHA_CTX *ctx, void *resbuf);
136
137 /* Put result from CTX in first 20 bytes following RESBUF.  The result is
138    always in little endian byte order, so that a byte-wise output yields
139    to the wanted ASCII representation of the message digest.  */
140 static void *sha1_read_ctx(const SHA_CTX *ctx, void *resbuf);
141
142 #endif /* WITH_LIBCRYPTO */
143
144
145
146 /* Compute SHA1 message digest for bytes read from STREAM.  The resulting
147  * message digest number will be written into the 20 bytes beginning at
148  * RESBLOCK.  */
149 int sha1_stream(FILE * stream, void *resblock)
150 {
151         SHA_CTX ctx;
152
153         size_t sum;
154
155         char *buffer = MALLOC(BLOCKSIZE + 72);
156         if (!buffer) {
157                 ERROR("Out of memory!\n");
158                 return WIMLIB_ERR_NOMEM;
159         }
160
161         /* Initialize the computation context.  */
162         sha1_init_ctx(&ctx);
163
164         /* Iterate over full file contents.  */
165         while (1) {
166                 /* We read the file in blocks of BLOCKSIZE bytes.  One call of the
167                    computation function processes the whole buffer so that with the
168                    next round of the loop another block can be read.  */
169                 size_t n;
170                 sum = 0;
171
172                 /* Read block.  Take care for partial reads.  */
173                 while (1) {
174                         n = fread(buffer + sum, 1, BLOCKSIZE - sum, stream);
175
176                         sum += n;
177
178                         if (sum == BLOCKSIZE)
179                                 break;
180
181                         if (n == 0) {
182                                 /* Check for the error flag IFF N == 0, so that
183                                  * we don't exit the loop after a partial read
184                                  * due to e.g., EAGAIN or EWOULDBLOCK.  */
185                                 if (ferror(stream)) {
186                                         FREE(buffer);
187                                         ERROR("Read error while calculating "
188                                                 "SHA1 message digest: %m\n");
189                                         return WIMLIB_ERR_READ;
190                                 }
191                                 goto process_partial_block;
192                         }
193
194                         /* We've read at least one byte, so ignore errors.  But always
195                            check for EOF, since feof may be true even though N > 0.
196                            Otherwise, we could end up calling fread after EOF.  */
197                         if (feof(stream))
198                                 goto process_partial_block;
199                 }
200
201                 /* Process buffer with BLOCKSIZE bytes.  Note that
202                    BLOCKSIZE % 64 == 0
203                  */
204                 sha1_process_block(buffer, BLOCKSIZE, &ctx);
205         }
206
207  process_partial_block:;
208
209         /* Process any remaining bytes.  */
210         if (sum > 0)
211                 sha1_process_bytes(buffer, sum, &ctx);
212
213         /* Construct result in desired memory.  */
214         sha1_finish_ctx(&ctx, resblock);
215         FREE(buffer);
216         return 0;
217 }
218
219 #ifndef WITH_LIBCRYPTO
220 /* Compute SHA1 message digest for LEN bytes beginning at BUFFER.  The
221    result is always in little endian byte order, so that a byte-wise
222    output yields to the wanted ASCII representation of the message
223    digest.  */
224 void *sha1_buffer(const char *buffer, size_t len, void *resblock)
225 {
226         SHA_CTX ctx;
227
228         /* Initialize the computation context.  */
229         sha1_init_ctx(&ctx);
230
231         /* Process whole buffer but last len % 64 bytes.  */
232         sha1_process_bytes(buffer, len, &ctx);
233
234         /* Put result in desired memory area.  */
235         return sha1_finish_ctx(&ctx, resblock);
236 }
237
238 /* Take a pointer to a 160 bit block of data (five 32 bit ints) and
239    initialize it to the start constants of the SHA1 algorithm.  This
240    must be called before using hash in the call to sha1_hash.  */
241 static void sha1_init_ctx(SHA_CTX *ctx)
242 {
243         ctx->A = 0x67452301;
244         ctx->B = 0xefcdab89;
245         ctx->C = 0x98badcfe;
246         ctx->D = 0x10325476;
247         ctx->E = 0xc3d2e1f0;
248
249         ctx->total[0] = ctx->total[1] = 0;
250         ctx->buflen = 0;
251 }
252
253 /* Copy the 4 byte value from v into the memory location pointed to by *cp,
254    If your architecture allows unaligned access this is equivalent to
255    * (uint32_t *) cp = v  */
256 static inline void set_uint32(char *cp, uint32_t v)
257 {
258         memcpy(cp, &v, sizeof v);
259 }
260
261 /* Put result from CTX in first 20 bytes following RESBUF.  The result
262    must be in little endian byte order.  */
263 static void *sha1_read_ctx(const SHA_CTX *ctx, void *resbuf)
264 {
265         char *r = resbuf;
266         set_uint32(r + 0 * sizeof ctx->A, SWAP(ctx->A));
267         set_uint32(r + 1 * sizeof ctx->B, SWAP(ctx->B));
268         set_uint32(r + 2 * sizeof ctx->C, SWAP(ctx->C));
269         set_uint32(r + 3 * sizeof ctx->D, SWAP(ctx->D));
270         set_uint32(r + 4 * sizeof ctx->E, SWAP(ctx->E));
271
272         return resbuf;
273 }
274
275 /* Process the remaining bytes in the internal buffer and the usual
276    prolog according to the standard and write the result to RESBUF.  */
277 static void *sha1_finish_ctx(SHA_CTX *ctx, void *resbuf)
278 {
279         /* Take yet unprocessed bytes into account.  */
280         uint32_t bytes = ctx->buflen;
281         size_t size = (bytes < 56) ? 64 / 4 : 64 * 2 / 4;
282
283         /* Now count remaining bytes.  */
284         ctx->total[0] += bytes;
285         if (ctx->total[0] < bytes)
286                 ++ctx->total[1];
287
288         /* Put the 64-bit file length in *bits* at the end of the buffer.  */
289         ctx->buffer[size - 2] =
290             SWAP((ctx->total[1] << 3) | (ctx->total[0] >> 29));
291         ctx->buffer[size - 1] = SWAP(ctx->total[0] << 3);
292
293         memcpy(&((char *)ctx->buffer)[bytes], fillbuf, (size - 2) * 4 - bytes);
294
295         /* Process last bytes.  */
296         sha1_process_block(ctx->buffer, size * 4, ctx);
297
298         return sha1_read_ctx(ctx, resbuf);
299 }
300
301
302 static void sha1_process_bytes(const void *buffer, size_t len, SHA_CTX *ctx)
303 {
304         /* When we already have some bits in our internal buffer concatenate
305            both inputs first.  */
306         if (ctx->buflen != 0) {
307                 size_t left_over = ctx->buflen;
308                 size_t add = 128 - left_over > len ? len : 128 - left_over;
309
310                 memcpy(&((char *)ctx->buffer)[left_over], buffer, add);
311                 ctx->buflen += add;
312
313                 if (ctx->buflen > 64) {
314                         sha1_process_block(ctx->buffer, ctx->buflen & ~63, ctx);
315
316                         ctx->buflen &= 63;
317                         /* The regions in the following copy operation cannot overlap.  */
318                         memcpy(ctx->buffer,
319                                &((char *)ctx->buffer)[(left_over + add) & ~63],
320                                ctx->buflen);
321                 }
322
323                 buffer = (const char *)buffer + add;
324                 len -= add;
325         }
326
327         /* Process available complete blocks.  */
328         if (len >= 64) {
329 #if !_STRING_ARCH_unaligned
330 #define alignof(type) offsetof (struct { char c; type x; }, x)
331 #define UNALIGNED_P(p) (((size_t) p) % alignof (uint32_t) != 0)
332                 if (UNALIGNED_P(buffer))
333                         while (len > 64) {
334                                 sha1_process_block(memcpy
335                                                    (ctx->buffer, buffer, 64),
336                                                    64, ctx);
337                                 buffer = (const char *)buffer + 64;
338                                 len -= 64;
339                 } else
340 #endif
341                 {
342                         sha1_process_block(buffer, len & ~63, ctx);
343                         buffer = (const char *)buffer + (len & ~63);
344                         len &= 63;
345                 }
346         }
347
348         /* Move remaining bytes in internal buffer.  */
349         if (len > 0) {
350                 size_t left_over = ctx->buflen;
351
352                 memcpy(&((char *)ctx->buffer)[left_over], buffer, len);
353                 left_over += len;
354                 if (left_over >= 64) {
355                         sha1_process_block(ctx->buffer, 64, ctx);
356                         left_over -= 64;
357                         memcpy(ctx->buffer, &ctx->buffer[16], left_over);
358                 }
359                 ctx->buflen = left_over;
360         }
361 }
362
363 /* --- Code below is the primary difference between md5.c and sha1.c --- */
364
365 /* SHA1 round constants */
366 #define K1 0x5a827999
367 #define K2 0x6ed9eba1
368 #define K3 0x8f1bbcdc
369 #define K4 0xca62c1d6
370
371 /* Round functions.  Note that F2 is the same as F4.  */
372 #define F1(B,C,D) ( D ^ ( B & ( C ^ D ) ) )
373 #define F2(B,C,D) (B ^ C ^ D)
374 #define F3(B,C,D) ( ( B & C ) | ( D & ( B | C ) ) )
375 #define F4(B,C,D) (B ^ C ^ D)
376
377 /* Process LEN bytes of BUFFER, accumulating context into CTX.
378    It is assumed that LEN % 64 == 0.
379    Most of this code comes from GnuPG's cipher/sha1.c.  */
380
381 #ifndef ENABLE_SSSE3_SHA1
382 static void sha1_process_block(const void *buffer, size_t len, SHA_CTX *ctx)
383 {
384         const uint32_t *words = buffer;
385         size_t nwords = len / sizeof(uint32_t);
386         const uint32_t *endp = words + nwords;
387         uint32_t x[16];
388         uint32_t a = ctx->A;
389         uint32_t b = ctx->B;
390         uint32_t c = ctx->C;
391         uint32_t d = ctx->D;
392         uint32_t e = ctx->E;
393
394         /* First increment the byte count.  RFC 1321 specifies the possible
395            length of the file up to 2^64 bits.  Here we only compute the
396            number of bytes.  Do a double word increment.  */
397         ctx->total[0] += len;
398         if (ctx->total[0] < len)
399                 ++ctx->total[1];
400
401 #define rol(x, n) (((x) << (n)) | ((uint32_t) (x) >> (32 - (n))))
402
403 #define M(I) ( tm =   x[I&0x0f] ^ x[(I-14)&0x0f] \
404                     ^ x[(I-8)&0x0f] ^ x[(I-3)&0x0f] \
405                , (x[I&0x0f] = rol(tm, 1)) )
406
407 #define R(A,B,C,D,E,F,K,M)  do { E += rol( A, 5 )     \
408                                       + F( B, C, D )  \
409                                       + K             \
410                                       + M;            \
411                                  B = rol( B, 30 );    \
412                                } while(0)
413
414         while (words < endp) {
415                 uint32_t tm;
416                 int t;
417                 for (t = 0; t < 16; t++) {
418                         x[t] = SWAP(*words);
419                         words++;
420                 }
421
422                 R(a, b, c, d, e, F1, K1, x[0]);
423                 R(e, a, b, c, d, F1, K1, x[1]);
424                 R(d, e, a, b, c, F1, K1, x[2]);
425                 R(c, d, e, a, b, F1, K1, x[3]);
426                 R(b, c, d, e, a, F1, K1, x[4]);
427                 R(a, b, c, d, e, F1, K1, x[5]);
428                 R(e, a, b, c, d, F1, K1, x[6]);
429                 R(d, e, a, b, c, F1, K1, x[7]);
430                 R(c, d, e, a, b, F1, K1, x[8]);
431                 R(b, c, d, e, a, F1, K1, x[9]);
432                 R(a, b, c, d, e, F1, K1, x[10]);
433                 R(e, a, b, c, d, F1, K1, x[11]);
434                 R(d, e, a, b, c, F1, K1, x[12]);
435                 R(c, d, e, a, b, F1, K1, x[13]);
436                 R(b, c, d, e, a, F1, K1, x[14]);
437                 R(a, b, c, d, e, F1, K1, x[15]);
438                 R(e, a, b, c, d, F1, K1, M(16));
439                 R(d, e, a, b, c, F1, K1, M(17));
440                 R(c, d, e, a, b, F1, K1, M(18));
441                 R(b, c, d, e, a, F1, K1, M(19));
442                 R(a, b, c, d, e, F2, K2, M(20));
443                 R(e, a, b, c, d, F2, K2, M(21));
444                 R(d, e, a, b, c, F2, K2, M(22));
445                 R(c, d, e, a, b, F2, K2, M(23));
446                 R(b, c, d, e, a, F2, K2, M(24));
447                 R(a, b, c, d, e, F2, K2, M(25));
448                 R(e, a, b, c, d, F2, K2, M(26));
449                 R(d, e, a, b, c, F2, K2, M(27));
450                 R(c, d, e, a, b, F2, K2, M(28));
451                 R(b, c, d, e, a, F2, K2, M(29));
452                 R(a, b, c, d, e, F2, K2, M(30));
453                 R(e, a, b, c, d, F2, K2, M(31));
454                 R(d, e, a, b, c, F2, K2, M(32));
455                 R(c, d, e, a, b, F2, K2, M(33));
456                 R(b, c, d, e, a, F2, K2, M(34));
457                 R(a, b, c, d, e, F2, K2, M(35));
458                 R(e, a, b, c, d, F2, K2, M(36));
459                 R(d, e, a, b, c, F2, K2, M(37));
460                 R(c, d, e, a, b, F2, K2, M(38));
461                 R(b, c, d, e, a, F2, K2, M(39));
462                 R(a, b, c, d, e, F3, K3, M(40));
463                 R(e, a, b, c, d, F3, K3, M(41));
464                 R(d, e, a, b, c, F3, K3, M(42));
465                 R(c, d, e, a, b, F3, K3, M(43));
466                 R(b, c, d, e, a, F3, K3, M(44));
467                 R(a, b, c, d, e, F3, K3, M(45));
468                 R(e, a, b, c, d, F3, K3, M(46));
469                 R(d, e, a, b, c, F3, K3, M(47));
470                 R(c, d, e, a, b, F3, K3, M(48));
471                 R(b, c, d, e, a, F3, K3, M(49));
472                 R(a, b, c, d, e, F3, K3, M(50));
473                 R(e, a, b, c, d, F3, K3, M(51));
474                 R(d, e, a, b, c, F3, K3, M(52));
475                 R(c, d, e, a, b, F3, K3, M(53));
476                 R(b, c, d, e, a, F3, K3, M(54));
477                 R(a, b, c, d, e, F3, K3, M(55));
478                 R(e, a, b, c, d, F3, K3, M(56));
479                 R(d, e, a, b, c, F3, K3, M(57));
480                 R(c, d, e, a, b, F3, K3, M(58));
481                 R(b, c, d, e, a, F3, K3, M(59));
482                 R(a, b, c, d, e, F4, K4, M(60));
483                 R(e, a, b, c, d, F4, K4, M(61));
484                 R(d, e, a, b, c, F4, K4, M(62));
485                 R(c, d, e, a, b, F4, K4, M(63));
486                 R(b, c, d, e, a, F4, K4, M(64));
487                 R(a, b, c, d, e, F4, K4, M(65));
488                 R(e, a, b, c, d, F4, K4, M(66));
489                 R(d, e, a, b, c, F4, K4, M(67));
490                 R(c, d, e, a, b, F4, K4, M(68));
491                 R(b, c, d, e, a, F4, K4, M(69));
492                 R(a, b, c, d, e, F4, K4, M(70));
493                 R(e, a, b, c, d, F4, K4, M(71));
494                 R(d, e, a, b, c, F4, K4, M(72));
495                 R(c, d, e, a, b, F4, K4, M(73));
496                 R(b, c, d, e, a, F4, K4, M(74));
497                 R(a, b, c, d, e, F4, K4, M(75));
498                 R(e, a, b, c, d, F4, K4, M(76));
499                 R(d, e, a, b, c, F4, K4, M(77));
500                 R(c, d, e, a, b, F4, K4, M(78));
501                 R(b, c, d, e, a, F4, K4, M(79));
502
503                 a = ctx->A += a;
504                 b = ctx->B += b;
505                 c = ctx->C += c;
506                 d = ctx->D += d;
507                 e = ctx->E += e;
508         }
509 }
510 #endif /* ENABLE_SSSE3_SHA1 */
511
512 #endif /* WITH_LIBCRYPTO */