Import binutils-2.20
[dragonfly.git] / contrib / binutils-2.20 / libiberty / 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, 2004, 2005, 2006, 2008 Free Software
5    Foundation, Inc.
6
7    This program is free software; you can redistribute it and/or modify it
8    under the terms of the GNU General Public License as published by the
9    Free Software Foundation; either version 2, or (at your option) any
10    later version.
11
12    This program is distributed in the hope that it will be useful,
13    but WITHOUT ANY WARRANTY; without even the implied warranty of
14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15    GNU General Public License for more details.
16
17    You should have received a copy of the GNU General Public License
18    along with this program; if not, write to the Free Software Foundation,
19    Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
20
21 /* Written by Scott G. Miller
22    Credits:
23       Robert Klep <robert@ilse.nl>  -- Expansion function fix
24 */
25
26 #include <config.h>
27
28 #include "sha1.h"
29
30 #include <stddef.h>
31 #include <string.h>
32
33 #if USE_UNLOCKED_IO
34 # include "unlocked-io.h"
35 #endif
36
37 #ifdef WORDS_BIGENDIAN
38 # define SWAP(n) (n)
39 #else
40 # define SWAP(n) \
41     (((n) << 24) | (((n) & 0xff00) << 8) | (((n) >> 8) & 0xff00) | ((n) >> 24))
42 #endif
43
44 #define BLOCKSIZE 4096
45 #if BLOCKSIZE % 64 != 0
46 # error "invalid BLOCKSIZE"
47 #endif
48
49 /* This array contains the bytes used to pad the buffer to the next
50    64-byte boundary.  (RFC 1321, 3.1: Step 1)  */
51 static const unsigned char fillbuf[64] = { 0x80, 0 /* , 0, 0, ...  */ };
52
53
54 /* Take a pointer to a 160 bit block of data (five 32 bit ints) and
55    initialize it to the start constants of the SHA1 algorithm.  This
56    must be called before using hash in the call to sha1_hash.  */
57 void
58 sha1_init_ctx (struct sha1_ctx *ctx)
59 {
60   ctx->A = 0x67452301;
61   ctx->B = 0xefcdab89;
62   ctx->C = 0x98badcfe;
63   ctx->D = 0x10325476;
64   ctx->E = 0xc3d2e1f0;
65
66   ctx->total[0] = ctx->total[1] = 0;
67   ctx->buflen = 0;
68 }
69
70 /* Put result from CTX in first 20 bytes following RESBUF.  The result
71    must be in little endian byte order.
72
73    IMPORTANT: On some systems it is required that RESBUF is correctly
74    aligned for a 32-bit value.  */
75 void *
76 sha1_read_ctx (const struct sha1_ctx *ctx, void *resbuf)
77 {
78   ((sha1_uint32 *) resbuf)[0] = SWAP (ctx->A);
79   ((sha1_uint32 *) resbuf)[1] = SWAP (ctx->B);
80   ((sha1_uint32 *) resbuf)[2] = SWAP (ctx->C);
81   ((sha1_uint32 *) resbuf)[3] = SWAP (ctx->D);
82   ((sha1_uint32 *) resbuf)[4] = SWAP (ctx->E);
83
84   return resbuf;
85 }
86
87 /* Process the remaining bytes in the internal buffer and the usual
88    prolog according to the standard and write the result to RESBUF.
89
90    IMPORTANT: On some systems it is required that RESBUF is correctly
91    aligned for a 32-bit value.  */
92 void *
93 sha1_finish_ctx (struct sha1_ctx *ctx, void *resbuf)
94 {
95   /* Take yet unprocessed bytes into account.  */
96   sha1_uint32 bytes = ctx->buflen;
97   size_t size = (bytes < 56) ? 64 / 4 : 64 * 2 / 4;
98
99   /* Now count remaining bytes.  */
100   ctx->total[0] += bytes;
101   if (ctx->total[0] < bytes)
102     ++ctx->total[1];
103
104   /* Put the 64-bit file length in *bits* at the end of the buffer.  */
105   ctx->buffer[size - 2] = SWAP ((ctx->total[1] << 3) | (ctx->total[0] >> 29));
106   ctx->buffer[size - 1] = SWAP (ctx->total[0] << 3);
107
108   memcpy (&((char *) ctx->buffer)[bytes], fillbuf, (size - 2) * 4 - bytes);
109
110   /* Process last bytes.  */
111   sha1_process_block (ctx->buffer, size * 4, ctx);
112
113   return sha1_read_ctx (ctx, resbuf);
114 }
115
116 /* Compute SHA1 message digest for bytes read from STREAM.  The
117    resulting message digest number will be written into the 16 bytes
118    beginning at RESBLOCK.  */
119 int
120 sha1_stream (FILE *stream, void *resblock)
121 {
122   struct sha1_ctx ctx;
123   char buffer[BLOCKSIZE + 72];
124   size_t sum;
125
126   /* Initialize the computation context.  */
127   sha1_init_ctx (&ctx);
128
129   /* Iterate over full file contents.  */
130   while (1)
131     {
132       /* We read the file in blocks of BLOCKSIZE bytes.  One call of the
133          computation function processes the whole buffer so that with the
134          next round of the loop another block can be read.  */
135       size_t n;
136       sum = 0;
137
138       /* Read block.  Take care for partial reads.  */
139       while (1)
140         {
141           n = fread (buffer + sum, 1, BLOCKSIZE - sum, stream);
142
143           sum += n;
144
145           if (sum == BLOCKSIZE)
146             break;
147
148           if (n == 0)
149             {
150               /* Check for the error flag IFF N == 0, so that we don't
151                  exit the loop after a partial read due to e.g., EAGAIN
152                  or EWOULDBLOCK.  */
153               if (ferror (stream))
154                 return 1;
155               goto process_partial_block;
156             }
157
158           /* We've read at least one byte, so ignore errors.  But always
159              check for EOF, since feof may be true even though N > 0.
160              Otherwise, we could end up calling fread after EOF.  */
161           if (feof (stream))
162             goto process_partial_block;
163         }
164
165       /* Process buffer with BLOCKSIZE bytes.  Note that
166                         BLOCKSIZE % 64 == 0
167        */
168       sha1_process_block (buffer, BLOCKSIZE, &ctx);
169     }
170
171  process_partial_block:;
172
173   /* Process any remaining bytes.  */
174   if (sum > 0)
175     sha1_process_bytes (buffer, sum, &ctx);
176
177   /* Construct result in desired memory.  */
178   sha1_finish_ctx (&ctx, resblock);
179   return 0;
180 }
181
182 /* Compute SHA1 message digest for LEN bytes beginning at BUFFER.  The
183    result is always in little endian byte order, so that a byte-wise
184    output yields to the wanted ASCII representation of the message
185    digest.  */
186 void *
187 sha1_buffer (const char *buffer, size_t len, void *resblock)
188 {
189   struct sha1_ctx ctx;
190
191   /* Initialize the computation context.  */
192   sha1_init_ctx (&ctx);
193
194   /* Process whole buffer but last len % 64 bytes.  */
195   sha1_process_bytes (buffer, len, &ctx);
196
197   /* Put result in desired memory area.  */
198   return sha1_finish_ctx (&ctx, resblock);
199 }
200
201 void
202 sha1_process_bytes (const void *buffer, size_t len, struct sha1_ctx *ctx)
203 {
204   /* When we already have some bits in our internal buffer concatenate
205      both inputs first.  */
206   if (ctx->buflen != 0)
207     {
208       size_t left_over = ctx->buflen;
209       size_t add = 128 - left_over > len ? len : 128 - left_over;
210
211       memcpy (&((char *) ctx->buffer)[left_over], buffer, add);
212       ctx->buflen += add;
213
214       if (ctx->buflen > 64)
215         {
216           sha1_process_block (ctx->buffer, ctx->buflen & ~63, ctx);
217
218           ctx->buflen &= 63;
219           /* The regions in the following copy operation cannot overlap.  */
220           memcpy (ctx->buffer,
221                   &((char *) ctx->buffer)[(left_over + add) & ~63],
222                   ctx->buflen);
223         }
224
225       buffer = (const char *) buffer + add;
226       len -= add;
227     }
228
229   /* Process available complete blocks.  */
230   if (len >= 64)
231     {
232 #if !_STRING_ARCH_unaligned
233 # define alignof(type) offsetof (struct { char c; type x; }, x)
234 # define UNALIGNED_P(p) (((size_t) p) % alignof (sha1_uint32) != 0)
235       if (UNALIGNED_P (buffer))
236         while (len > 64)
237           {
238             sha1_process_block (memcpy (ctx->buffer, buffer, 64), 64, ctx);
239             buffer = (const char *) buffer + 64;
240             len -= 64;
241           }
242       else
243 #endif
244         {
245           sha1_process_block (buffer, len & ~63, ctx);
246           buffer = (const char *) buffer + (len & ~63);
247           len &= 63;
248         }
249     }
250
251   /* Move remaining bytes in internal buffer.  */
252   if (len > 0)
253     {
254       size_t left_over = ctx->buflen;
255
256       memcpy (&((char *) ctx->buffer)[left_over], buffer, len);
257       left_over += len;
258       if (left_over >= 64)
259         {
260           sha1_process_block (ctx->buffer, 64, ctx);
261           left_over -= 64;
262           memcpy (ctx->buffer, &ctx->buffer[16], left_over);
263         }
264       ctx->buflen = left_over;
265     }
266 }
267
268 /* --- Code below is the primary difference between md5.c and sha1.c --- */
269
270 /* SHA1 round constants */
271 #define K1 0x5a827999
272 #define K2 0x6ed9eba1
273 #define K3 0x8f1bbcdc
274 #define K4 0xca62c1d6
275
276 /* Round functions.  Note that F2 is the same as F4.  */
277 #define F1(B,C,D) ( D ^ ( B & ( C ^ D ) ) )
278 #define F2(B,C,D) (B ^ C ^ D)
279 #define F3(B,C,D) ( ( B & C ) | ( D & ( B | C ) ) )
280 #define F4(B,C,D) (B ^ C ^ D)
281
282 /* Process LEN bytes of BUFFER, accumulating context into CTX.
283    It is assumed that LEN % 64 == 0.
284    Most of this code comes from GnuPG's cipher/sha1.c.  */
285
286 void
287 sha1_process_block (const void *buffer, size_t len, struct sha1_ctx *ctx)
288 {
289   const sha1_uint32 *words = (const sha1_uint32*) buffer;
290   size_t nwords = len / sizeof (sha1_uint32);
291   const sha1_uint32 *endp = words + nwords;
292   sha1_uint32 x[16];
293   sha1_uint32 a = ctx->A;
294   sha1_uint32 b = ctx->B;
295   sha1_uint32 c = ctx->C;
296   sha1_uint32 d = ctx->D;
297   sha1_uint32 e = ctx->E;
298
299   /* First increment the byte count.  RFC 1321 specifies the possible
300      length of the file up to 2^64 bits.  Here we only compute the
301      number of bytes.  Do a double word increment.  */
302   ctx->total[0] += len;
303   if (ctx->total[0] < len)
304     ++ctx->total[1];
305
306 #define rol(x, n) (((x) << (n)) | ((sha1_uint32) (x) >> (32 - (n))))
307
308 #define M(I) ( tm =   x[I&0x0f] ^ x[(I-14)&0x0f] \
309                     ^ x[(I-8)&0x0f] ^ x[(I-3)&0x0f] \
310                , (x[I&0x0f] = rol(tm, 1)) )
311
312 #define R(A,B,C,D,E,F,K,M)  do { E += rol( A, 5 )     \
313                                       + F( B, C, D )  \
314                                       + K             \
315                                       + M;            \
316                                  B = rol( B, 30 );    \
317                                } while(0)
318
319   while (words < endp)
320     {
321       sha1_uint32 tm;
322       int t;
323       for (t = 0; t < 16; t++)
324         {
325           x[t] = SWAP (*words);
326           words++;
327         }
328
329       R( a, b, c, d, e, F1, K1, x[ 0] );
330       R( e, a, b, c, d, F1, K1, x[ 1] );
331       R( d, e, a, b, c, F1, K1, x[ 2] );
332       R( c, d, e, a, b, F1, K1, x[ 3] );
333       R( b, c, d, e, a, F1, K1, x[ 4] );
334       R( a, b, c, d, e, F1, K1, x[ 5] );
335       R( e, a, b, c, d, F1, K1, x[ 6] );
336       R( d, e, a, b, c, F1, K1, x[ 7] );
337       R( c, d, e, a, b, F1, K1, x[ 8] );
338       R( b, c, d, e, a, F1, K1, x[ 9] );
339       R( a, b, c, d, e, F1, K1, x[10] );
340       R( e, a, b, c, d, F1, K1, x[11] );
341       R( d, e, a, b, c, F1, K1, x[12] );
342       R( c, d, e, a, b, F1, K1, x[13] );
343       R( b, c, d, e, a, F1, K1, x[14] );
344       R( a, b, c, d, e, F1, K1, x[15] );
345       R( e, a, b, c, d, F1, K1, M(16) );
346       R( d, e, a, b, c, F1, K1, M(17) );
347       R( c, d, e, a, b, F1, K1, M(18) );
348       R( b, c, d, e, a, F1, K1, M(19) );
349       R( a, b, c, d, e, F2, K2, M(20) );
350       R( e, a, b, c, d, F2, K2, M(21) );
351       R( d, e, a, b, c, F2, K2, M(22) );
352       R( c, d, e, a, b, F2, K2, M(23) );
353       R( b, c, d, e, a, F2, K2, M(24) );
354       R( a, b, c, d, e, F2, K2, M(25) );
355       R( e, a, b, c, d, F2, K2, M(26) );
356       R( d, e, a, b, c, F2, K2, M(27) );
357       R( c, d, e, a, b, F2, K2, M(28) );
358       R( b, c, d, e, a, F2, K2, M(29) );
359       R( a, b, c, d, e, F2, K2, M(30) );
360       R( e, a, b, c, d, F2, K2, M(31) );
361       R( d, e, a, b, c, F2, K2, M(32) );
362       R( c, d, e, a, b, F2, K2, M(33) );
363       R( b, c, d, e, a, F2, K2, M(34) );
364       R( a, b, c, d, e, F2, K2, M(35) );
365       R( e, a, b, c, d, F2, K2, M(36) );
366       R( d, e, a, b, c, F2, K2, M(37) );
367       R( c, d, e, a, b, F2, K2, M(38) );
368       R( b, c, d, e, a, F2, K2, M(39) );
369       R( a, b, c, d, e, F3, K3, M(40) );
370       R( e, a, b, c, d, F3, K3, M(41) );
371       R( d, e, a, b, c, F3, K3, M(42) );
372       R( c, d, e, a, b, F3, K3, M(43) );
373       R( b, c, d, e, a, F3, K3, M(44) );
374       R( a, b, c, d, e, F3, K3, M(45) );
375       R( e, a, b, c, d, F3, K3, M(46) );
376       R( d, e, a, b, c, F3, K3, M(47) );
377       R( c, d, e, a, b, F3, K3, M(48) );
378       R( b, c, d, e, a, F3, K3, M(49) );
379       R( a, b, c, d, e, F3, K3, M(50) );
380       R( e, a, b, c, d, F3, K3, M(51) );
381       R( d, e, a, b, c, F3, K3, M(52) );
382       R( c, d, e, a, b, F3, K3, M(53) );
383       R( b, c, d, e, a, F3, K3, M(54) );
384       R( a, b, c, d, e, F3, K3, M(55) );
385       R( e, a, b, c, d, F3, K3, M(56) );
386       R( d, e, a, b, c, F3, K3, M(57) );
387       R( c, d, e, a, b, F3, K3, M(58) );
388       R( b, c, d, e, a, F3, K3, M(59) );
389       R( a, b, c, d, e, F4, K4, M(60) );
390       R( e, a, b, c, d, F4, K4, M(61) );
391       R( d, e, a, b, c, F4, K4, M(62) );
392       R( c, d, e, a, b, F4, K4, M(63) );
393       R( b, c, d, e, a, F4, K4, M(64) );
394       R( a, b, c, d, e, F4, K4, M(65) );
395       R( e, a, b, c, d, F4, K4, M(66) );
396       R( d, e, a, b, c, F4, K4, M(67) );
397       R( c, d, e, a, b, F4, K4, M(68) );
398       R( b, c, d, e, a, F4, K4, M(69) );
399       R( a, b, c, d, e, F4, K4, M(70) );
400       R( e, a, b, c, d, F4, K4, M(71) );
401       R( d, e, a, b, c, F4, K4, M(72) );
402       R( c, d, e, a, b, F4, K4, M(73) );
403       R( b, c, d, e, a, F4, K4, M(74) );
404       R( a, b, c, d, e, F4, K4, M(75) );
405       R( e, a, b, c, d, F4, K4, M(76) );
406       R( d, e, a, b, c, F4, K4, M(77) );
407       R( c, d, e, a, b, F4, K4, M(78) );
408       R( b, c, d, e, a, F4, K4, M(79) );
409
410       a = ctx->A += a;
411       b = ctx->B += b;
412       c = ctx->C += c;
413       d = ctx->D += d;
414       e = ctx->E += e;
415     }
416 }