1/* Functions to compute SHA1 message digest of files or memory blocks.
2   according to the definition of SHA1 in FIPS 180-1 from April 1997.
3   Copyright (C) 2008 Red Hat, Inc.
4   This file is part of Red Hat elfutils.
5   Written by Ulrich Drepper <drepper@redhat.com>, 2008.
6
7   Red Hat elfutils is free software; you can redistribute it and/or modify
8   it under the terms of the GNU General Public License as published by the
9   Free Software Foundation; version 2 of the License.
10
11   Red Hat elfutils is distributed in the hope that it will be useful, but
12   WITHOUT ANY WARRANTY; without even the implied warranty of
13   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14   General Public License for more details.
15
16   You should have received a copy of the GNU General Public License along
17   with Red Hat elfutils; if not, write to the Free Software Foundation,
18   Inc., 51 Franklin Street, Fifth Floor, Boston MA 02110-1301 USA.
19
20   Red Hat elfutils is an included package of the Open Invention Network.
21   An included package of the Open Invention Network is a package for which
22   Open Invention Network licensees cross-license their patents.  No patent
23   license is granted, either expressly or impliedly, by designation as an
24   included package.  Should you wish to participate in the Open Invention
25   Network licensing program, please visit www.openinventionnetwork.com
26   <http://www.openinventionnetwork.com>.  */
27
28#ifdef HAVE_CONFIG_H
29# include <config.h>
30#endif
31
32#include <endian.h>
33#include <stdlib.h>
34#include <string.h>
35#include <sys/types.h>
36
37#include "sha1.h"
38
39#if __BYTE_ORDER == __LITTLE_ENDIAN
40# include <byteswap.h>
41# define SWAP(n) bswap_32 (n)
42#else
43# define SWAP(n) (n)
44#endif
45
46
47/* This array contains the bytes used to pad the buffer to the next
48   64-byte boundary.  */
49static const unsigned char fillbuf[64] = { 0x80, 0 /* , 0, 0, ...  */ };
50
51
52/* Initialize structure containing state of computation.  */
53void
54sha1_init_ctx (ctx)
55     struct sha1_ctx *ctx;
56{
57  ctx->A = 0x67452301;
58  ctx->B = 0xefcdab89;
59  ctx->C = 0x98badcfe;
60  ctx->D = 0x10325476;
61  ctx->E = 0xc3d2e1f0;
62
63  ctx->total[0] = ctx->total[1] = 0;
64  ctx->buflen = 0;
65}
66
67/* Put result from CTX in first 20 bytes following RESBUF.  The result
68   must be in little endian byte order.
69
70   IMPORTANT: On some systems it is required that RESBUF is correctly
71   aligned for a 32 bits value.  */
72void *
73sha1_read_ctx (ctx, resbuf)
74     const struct sha1_ctx *ctx;
75     void *resbuf;
76{
77  ((sha1_uint32 *) resbuf)[0] = SWAP (ctx->A);
78  ((sha1_uint32 *) resbuf)[1] = SWAP (ctx->B);
79  ((sha1_uint32 *) resbuf)[2] = SWAP (ctx->C);
80  ((sha1_uint32 *) resbuf)[3] = SWAP (ctx->D);
81  ((sha1_uint32 *) resbuf)[4] = SWAP (ctx->E);
82
83  return resbuf;
84}
85
86/* Process the remaining bytes in the internal buffer and the usual
87   prolog according to the standard and write the result to RESBUF.
88
89   IMPORTANT: On some systems it is required that RESBUF is correctly
90   aligned for a 32 bits value.  */
91void *
92sha1_finish_ctx (ctx, resbuf)
93     struct sha1_ctx *ctx;
94     void *resbuf;
95{
96  /* Take yet unprocessed bytes into account.  */
97  sha1_uint32 bytes = ctx->buflen;
98  size_t pad;
99
100  /* Now count remaining bytes.  */
101  ctx->total[0] += bytes;
102  if (ctx->total[0] < bytes)
103    ++ctx->total[1];
104
105  pad = bytes >= 56 ? 64 + 56 - bytes : 56 - bytes;
106  memcpy (&ctx->buffer[bytes], fillbuf, pad);
107
108  /* Put the 64-bit file length in *bits* at the end of the buffer.  */
109  *(sha1_uint32 *) &ctx->buffer[bytes + pad] = SWAP ((ctx->total[1] << 3) |
110						     (ctx->total[0] >> 29));
111  *(sha1_uint32 *) &ctx->buffer[bytes + pad + 4] = SWAP (ctx->total[0] << 3);
112
113  /* Process last bytes.  */
114  sha1_process_block (ctx->buffer, bytes + pad + 8, ctx);
115
116  return sha1_read_ctx (ctx, resbuf);
117}
118
119
120void
121sha1_process_bytes (buffer, len, ctx)
122     const void *buffer;
123     size_t len;
124     struct sha1_ctx *ctx;
125{
126  /* When we already have some bits in our internal buffer concatenate
127     both inputs first.  */
128  if (ctx->buflen != 0)
129    {
130      size_t left_over = ctx->buflen;
131      size_t add = 128 - left_over > len ? len : 128 - left_over;
132
133      memcpy (&ctx->buffer[left_over], buffer, add);
134      ctx->buflen += add;
135
136      if (ctx->buflen > 64)
137	{
138	  sha1_process_block (ctx->buffer, ctx->buflen & ~63, ctx);
139
140	  ctx->buflen &= 63;
141	  /* The regions in the following copy operation cannot overlap.  */
142	  memcpy (ctx->buffer, &ctx->buffer[(left_over + add) & ~63],
143		  ctx->buflen);
144	}
145
146      buffer = (const char *) buffer + add;
147      len -= add;
148    }
149
150  /* Process available complete blocks.  */
151  if (len >= 64)
152    {
153#if !_STRING_ARCH_unaligned
154/* To check alignment gcc has an appropriate operator.  Other
155   compilers don't.  */
156# if __GNUC__ >= 2
157#  define UNALIGNED_P(p) (((sha1_uintptr) p) % __alignof__ (sha1_uint32) != 0)
158# else
159#  define UNALIGNED_P(p) (((sha1_uintptr) p) % sizeof (sha1_uint32) != 0)
160# endif
161      if (UNALIGNED_P (buffer))
162	while (len > 64)
163	  {
164	    sha1_process_block (memcpy (ctx->buffer, buffer, 64), 64, ctx);
165	    buffer = (const char *) buffer + 64;
166	    len -= 64;
167	  }
168      else
169#endif
170	{
171	  sha1_process_block (buffer, len & ~63, ctx);
172	  buffer = (const char *) buffer + (len & ~63);
173	  len &= 63;
174	}
175    }
176
177  /* Move remaining bytes in internal buffer.  */
178  if (len > 0)
179    {
180      size_t left_over = ctx->buflen;
181
182      memcpy (&ctx->buffer[left_over], buffer, len);
183      left_over += len;
184      if (left_over >= 64)
185	{
186	  sha1_process_block (ctx->buffer, 64, ctx);
187	  left_over -= 64;
188	  memcpy (ctx->buffer, &ctx->buffer[64], left_over);
189	}
190      ctx->buflen = left_over;
191    }
192}
193
194
195/* These are the four functions used in the four steps of the SHA1 algorithm
196   and defined in the FIPS 180-1.  */
197/* #define FF(b, c, d) ((b & c) | (~b & d)) */
198#define FF(b, c, d) (d ^ (b & (c ^ d)))
199#define FG(b, c, d) (b ^ c ^ d)
200/* define FH(b, c, d) ((b & c) | (b & d) | (c & d)) */
201#define FH(b, c, d) (((b | c) & d) | (b & c))
202
203/* It is unfortunate that C does not provide an operator for cyclic
204   rotation.  Hope the C compiler is smart enough.  */
205#define CYCLIC(w, s) (((w) << s) | ((w) >> (32 - s)))
206
207/* Magic constants.  */
208#define K0 0x5a827999
209#define K1 0x6ed9eba1
210#define K2 0x8f1bbcdc
211#define K3 0xca62c1d6
212
213
214/* Process LEN bytes of BUFFER, accumulating context into CTX.
215   It is assumed that LEN % 64 == 0.  */
216
217void
218sha1_process_block (buffer, len, ctx)
219     const void *buffer;
220     size_t len;
221     struct sha1_ctx *ctx;
222{
223  sha1_uint32 computed_words[16];
224#define W(i) computed_words[(i) % 16]
225  const sha1_uint32 *words = buffer;
226  size_t nwords = len / sizeof (sha1_uint32);
227  const sha1_uint32 *endp = words + nwords;
228  sha1_uint32 A = ctx->A;
229  sha1_uint32 B = ctx->B;
230  sha1_uint32 C = ctx->C;
231  sha1_uint32 D = ctx->D;
232  sha1_uint32 E = ctx->E;
233
234  /* First increment the byte count.  FIPS 180-1 specifies the possible
235     length of the file up to 2^64 bits.  Here we only compute the
236     number of bytes.  Do a double word increment.  */
237  ctx->total[0] += len;
238  if (ctx->total[0] < len)
239    ++ctx->total[1];
240
241  /* Process all bytes in the buffer with 64 bytes in each round of
242     the loop.  */
243  while (words < endp)
244    {
245      sha1_uint32 A_save = A;
246      sha1_uint32 B_save = B;
247      sha1_uint32 C_save = C;
248      sha1_uint32 D_save = D;
249      sha1_uint32 E_save = E;
250
251      /* First round: using the given function, the context and a constant
252	 the next context is computed.  Because the algorithms processing
253	 unit is a 32-bit word and it is determined to work on words in
254	 little endian byte order we perhaps have to change the byte order
255	 before the computation.  */
256
257#define OP(i, a, b, c, d, e)						\
258      do								\
259        {								\
260	  W (i) = SWAP (*words);					\
261	  e = CYCLIC (a, 5) + FF (b, c, d) + e + W (i) + K0;		\
262	  ++words;							\
263	  b = CYCLIC (b, 30);						\
264        }								\
265      while (0)
266
267      /* Steps 0 to 15.  */
268      OP (0, A, B, C, D, E);
269      OP (1, E, A, B, C, D);
270      OP (2, D, E, A, B, C);
271      OP (3, C, D, E, A, B);
272      OP (4, B, C, D, E, A);
273      OP (5, A, B, C, D, E);
274      OP (6, E, A, B, C, D);
275      OP (7, D, E, A, B, C);
276      OP (8, C, D, E, A, B);
277      OP (9, B, C, D, E, A);
278      OP (10, A, B, C, D, E);
279      OP (11, E, A, B, C, D);
280      OP (12, D, E, A, B, C);
281      OP (13, C, D, E, A, B);
282      OP (14, B, C, D, E, A);
283      OP (15, A, B, C, D, E);
284
285      /* For the remaining 64 steps we have a more complicated
286	 computation of the input data-derived values.  Redefine the
287	 macro to take an additional second argument specifying the
288	 function to use and a new last parameter for the magic
289	 constant.  */
290#undef OP
291#define OP(i, f, a, b, c, d, e, K) \
292      do								\
293        {								\
294	  W (i) = CYCLIC (W (i - 3) ^ W (i - 8) ^ W (i - 14) ^ W (i - 16), 1);\
295	  e = CYCLIC (a, 5) + f (b, c, d) + e + W (i) + K;		\
296	  b = CYCLIC (b, 30);						\
297        }								\
298      while (0)
299
300      /* Steps 16 to 19.  */
301      OP (16, FF, E, A, B, C, D, K0);
302      OP (17, FF, D, E, A, B, C, K0);
303      OP (18, FF, C, D, E, A, B, K0);
304      OP (19, FF, B, C, D, E, A, K0);
305
306      /* Steps 20 to 39.  */
307      OP (20, FG, A, B, C, D, E, K1);
308      OP (21, FG, E, A, B, C, D, K1);
309      OP (22, FG, D, E, A, B, C, K1);
310      OP (23, FG, C, D, E, A, B, K1);
311      OP (24, FG, B, C, D, E, A, K1);
312      OP (25, FG, A, B, C, D, E, K1);
313      OP (26, FG, E, A, B, C, D, K1);
314      OP (27, FG, D, E, A, B, C, K1);
315      OP (28, FG, C, D, E, A, B, K1);
316      OP (29, FG, B, C, D, E, A, K1);
317      OP (30, FG, A, B, C, D, E, K1);
318      OP (31, FG, E, A, B, C, D, K1);
319      OP (32, FG, D, E, A, B, C, K1);
320      OP (33, FG, C, D, E, A, B, K1);
321      OP (34, FG, B, C, D, E, A, K1);
322      OP (35, FG, A, B, C, D, E, K1);
323      OP (36, FG, E, A, B, C, D, K1);
324      OP (37, FG, D, E, A, B, C, K1);
325      OP (38, FG, C, D, E, A, B, K1);
326      OP (39, FG, B, C, D, E, A, K1);
327
328      /* Steps 40 to 59.  */
329      OP (40, FH, A, B, C, D, E, K2);
330      OP (41, FH, E, A, B, C, D, K2);
331      OP (42, FH, D, E, A, B, C, K2);
332      OP (43, FH, C, D, E, A, B, K2);
333      OP (44, FH, B, C, D, E, A, K2);
334      OP (45, FH, A, B, C, D, E, K2);
335      OP (46, FH, E, A, B, C, D, K2);
336      OP (47, FH, D, E, A, B, C, K2);
337      OP (48, FH, C, D, E, A, B, K2);
338      OP (49, FH, B, C, D, E, A, K2);
339      OP (50, FH, A, B, C, D, E, K2);
340      OP (51, FH, E, A, B, C, D, K2);
341      OP (52, FH, D, E, A, B, C, K2);
342      OP (53, FH, C, D, E, A, B, K2);
343      OP (54, FH, B, C, D, E, A, K2);
344      OP (55, FH, A, B, C, D, E, K2);
345      OP (56, FH, E, A, B, C, D, K2);
346      OP (57, FH, D, E, A, B, C, K2);
347      OP (58, FH, C, D, E, A, B, K2);
348      OP (59, FH, B, C, D, E, A, K2);
349
350      /* Steps 60 to 79.  */
351      OP (60, FG, A, B, C, D, E, K3);
352      OP (61, FG, E, A, B, C, D, K3);
353      OP (62, FG, D, E, A, B, C, K3);
354      OP (63, FG, C, D, E, A, B, K3);
355      OP (64, FG, B, C, D, E, A, K3);
356      OP (65, FG, A, B, C, D, E, K3);
357      OP (66, FG, E, A, B, C, D, K3);
358      OP (67, FG, D, E, A, B, C, K3);
359      OP (68, FG, C, D, E, A, B, K3);
360      OP (69, FG, B, C, D, E, A, K3);
361      OP (70, FG, A, B, C, D, E, K3);
362      OP (71, FG, E, A, B, C, D, K3);
363      OP (72, FG, D, E, A, B, C, K3);
364      OP (73, FG, C, D, E, A, B, K3);
365      OP (74, FG, B, C, D, E, A, K3);
366      OP (75, FG, A, B, C, D, E, K3);
367      OP (76, FG, E, A, B, C, D, K3);
368      OP (77, FG, D, E, A, B, C, K3);
369      OP (78, FG, C, D, E, A, B, K3);
370      OP (79, FG, B, C, D, E, A, K3);
371
372      /* Add the starting values of the context.  */
373      A += A_save;
374      B += B_save;
375      C += C_save;
376      D += D_save;
377      E += E_save;
378    }
379
380  /* Put checksum in context given as argument.  */
381  ctx->A = A;
382  ctx->B = B;
383  ctx->C = C;
384  ctx->D = D;
385  ctx->E = E;
386}
387