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