README updates: explain restores in more detail.
[cumulus.git] / sha1.cc
1 /* sha1.cc - Functions to compute SHA1 message digest of data streams
2  * according to the NIST specification FIPS-180-1.
3  * part of Cumulus: Smart Filesystem Backup to Dumb Servers
4  *
5  * Copyright (C) 2000, 2001, 2003, 2004, 2005 Free Software Foundation, Inc.
6  * Copyright (C) 2006-2007  The Regents of the University of California
7  * Written by Scott G. Miller
8  * Additional Credits:
9  *    Robert Klep <robert@ilse.nl>  -- Expansion function fix
10  * Modifications by Michael Vrable <mvrable@cs.ucsd.edu> to integrate into
11  * Cumulus.
12  *
13  * Original code (in C) is taken from GNU coreutils (Debian package 5.97-5).
14  *
15  * This program is free software; you can redistribute it and/or modify
16  * it under the terms of the GNU General Public License as published by
17  * the Free Software Foundation; either version 2 of the License, or
18  * (at your option) any later version.
19  *
20  * This program is distributed in the hope that it will be useful,
21  * but WITHOUT ANY WARRANTY; without even the implied warranty of
22  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
23  * GNU General Public License for more details.
24  *
25  * You should have received a copy of the GNU General Public License along
26  * with this program; if not, write to the Free Software Foundation, Inc.,
27  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
28  */
29
30 #include "sha1.h"
31
32 #include <stddef.h>
33 #include <stdio.h>
34 #include <string.h>
35 #include <arpa/inet.h>
36
37 #include <string.h>
38
39 using std::string;
40
41 /* SWAP does an endian swap on architectures that are little-endian,
42    as SHA1 needs some data in a big-endian form.  */
43 #define SWAP(n) htonl(n)
44
45 #define BLOCKSIZE 4096
46 #if BLOCKSIZE % 64 != 0
47 # error "invalid BLOCKSIZE"
48 #endif
49
50 /* This array contains the bytes used to pad the buffer to the next
51    64-byte boundary.  (RFC 1321, 3.1: Step 1)  */
52 static const unsigned char fillbuf[64] = { 0x80, 0 /* , 0, 0, ...  */ };
53
54
55 /*
56   Takes a pointer to a 160 bit block of data (five 32 bit ints) and
57   intializes it to the start constants of the SHA1 algorithm.  This
58   must be called before using hash in the call to sha1_hash.
59 */
60 void
61 sha1_init_ctx (struct sha1_ctx *ctx)
62 {
63   ctx->A = 0x67452301;
64   ctx->B = 0xefcdab89;
65   ctx->C = 0x98badcfe;
66   ctx->D = 0x10325476;
67   ctx->E = 0xc3d2e1f0;
68
69   ctx->total[0] = ctx->total[1] = 0;
70   ctx->buflen = 0;
71 }
72
73 /* Put result from CTX in first 20 bytes following RESBUF.  The result
74    must be in little endian byte order.
75
76    IMPORTANT: On some systems it is required that RESBUF is correctly
77    aligned for a 32 bits value.  */
78 void *
79 sha1_read_ctx (const struct sha1_ctx *ctx, void *resbuf)
80 {
81   ((md5_uint32 *) resbuf)[0] = SWAP (ctx->A);
82   ((md5_uint32 *) resbuf)[1] = SWAP (ctx->B);
83   ((md5_uint32 *) resbuf)[2] = SWAP (ctx->C);
84   ((md5_uint32 *) resbuf)[3] = SWAP (ctx->D);
85   ((md5_uint32 *) resbuf)[4] = SWAP (ctx->E);
86
87   return resbuf;
88 }
89
90 /* Process the remaining bytes in the internal buffer and the usual
91    prolog according to the standard and write the result to RESBUF.
92
93    IMPORTANT: On some systems it is required that RESBUF is correctly
94    aligned for a 32 bits value.  */
95 void *
96 sha1_finish_ctx (struct sha1_ctx *ctx, void *resbuf)
97 {
98   /* Take yet unprocessed bytes into account.  */
99   md5_uint32 bytes = ctx->buflen;
100   size_t pad;
101
102   /* Now count remaining bytes.  */
103   ctx->total[0] += bytes;
104   if (ctx->total[0] < bytes)
105     ++ctx->total[1];
106
107   pad = bytes >= 56 ? 64 + 56 - bytes : 56 - bytes;
108   memcpy (&ctx->buffer[bytes], fillbuf, pad);
109
110   /* Put the 64-bit file length in *bits* at the end of the buffer.  */
111   *(md5_uint32 *) &ctx->buffer[bytes + pad + 4] = SWAP (ctx->total[0] << 3);
112   *(md5_uint32 *) &ctx->buffer[bytes + pad] = SWAP ((ctx->total[1] << 3) |
113                                                     (ctx->total[0] >> 29));
114
115   /* Process last bytes.  */
116   sha1_process_block (ctx->buffer, bytes + pad + 8, ctx);
117
118   return sha1_read_ctx (ctx, resbuf);
119 }
120
121 void
122 sha1_process_bytes (const void *buffer, size_t len, struct sha1_ctx *ctx)
123 {
124   /* When we already have some bits in our internal buffer concatenate
125      both inputs first.  */
126   if (ctx->buflen != 0)
127     {
128       size_t left_over = ctx->buflen;
129       size_t add = 128 - left_over > len ? len : 128 - left_over;
130
131       memcpy (&ctx->buffer[left_over], buffer, add);
132       ctx->buflen += add;
133
134       if (ctx->buflen > 64)
135         {
136           sha1_process_block (ctx->buffer, ctx->buflen & ~63, ctx);
137
138           ctx->buflen &= 63;
139           /* The regions in the following copy operation cannot overlap.  */
140           memcpy (ctx->buffer, &ctx->buffer[(left_over + add) & ~63],
141                   ctx->buflen);
142         }
143
144       buffer = (const char *) buffer + add;
145       len -= add;
146     }
147
148   /* Process available complete blocks.  */
149   if (len >= 64)
150     {
151 #if !_STRING_ARCH_unaligned
152 # define alignof(type) offsetof (struct { char c; type x; }, x)
153 # define UNALIGNED_P(p) (((size_t) p) % alignof (md5_uint32) != 0)
154       if (UNALIGNED_P (buffer))
155         while (len > 64)
156           {
157             sha1_process_block (memcpy (ctx->buffer, buffer, 64), 64, ctx);
158             buffer = (const char *) buffer + 64;
159             len -= 64;
160           }
161       else
162 #endif
163         {
164           sha1_process_block (buffer, len & ~63, ctx);
165           buffer = (const char *) buffer + (len & ~63);
166           len &= 63;
167         }
168     }
169
170   /* Move remaining bytes in internal buffer.  */
171   if (len > 0)
172     {
173       size_t left_over = ctx->buflen;
174
175       memcpy (&ctx->buffer[left_over], buffer, len);
176       left_over += len;
177       if (left_over >= 64)
178         {
179           sha1_process_block (ctx->buffer, 64, ctx);
180           left_over -= 64;
181           memcpy (ctx->buffer, &ctx->buffer[64], left_over);
182         }
183       ctx->buflen = left_over;
184     }
185 }
186
187 /* --- Code below is the primary difference between md5.c and sha1.c --- */
188
189 /* SHA1 round constants */
190 #define K1 0x5a827999L
191 #define K2 0x6ed9eba1L
192 #define K3 0x8f1bbcdcL
193 #define K4 0xca62c1d6L
194
195 /* Round functions.  Note that F2 is the same as F4.  */
196 #define F1(B,C,D) ( D ^ ( B & ( C ^ D ) ) )
197 #define F2(B,C,D) (B ^ C ^ D)
198 #define F3(B,C,D) ( ( B & C ) | ( D & ( B | C ) ) )
199 #define F4(B,C,D) (B ^ C ^ D)
200
201 /* Process LEN bytes of BUFFER, accumulating context into CTX.
202    It is assumed that LEN % 64 == 0.
203    Most of this code comes from GnuPG's cipher/sha1.c.  */
204
205 void
206 sha1_process_block (const void *buffer, size_t len, struct sha1_ctx *ctx)
207 {
208   const md5_uint32 *words = (const md5_uint32 *)buffer;
209   size_t nwords = len / sizeof (md5_uint32);
210   const md5_uint32 *endp = words + nwords;
211   md5_uint32 x[16];
212   md5_uint32 a = ctx->A;
213   md5_uint32 b = ctx->B;
214   md5_uint32 c = ctx->C;
215   md5_uint32 d = ctx->D;
216   md5_uint32 e = ctx->E;
217
218   /* First increment the byte count.  RFC 1321 specifies the possible
219      length of the file up to 2^64 bits.  Here we only compute the
220      number of bytes.  Do a double word increment.  */
221   ctx->total[0] += len;
222   if (ctx->total[0] < len)
223     ++ctx->total[1];
224
225 #define rol(x, n) (((x) << (n)) | ((x) >> (32 - (n))))
226
227 #define M(I) ( tm =   x[I&0x0f] ^ x[(I-14)&0x0f] \
228                     ^ x[(I-8)&0x0f] ^ x[(I-3)&0x0f] \
229                , (x[I&0x0f] = rol(tm, 1)) )
230
231 #define R(A,B,C,D,E,F,K,M)  do { E += rol( A, 5 )     \
232                                       + F( B, C, D )  \
233                                       + K             \
234                                       + M;            \
235                                  B = rol( B, 30 );    \
236                                } while(0)
237
238   while (words < endp)
239     {
240       md5_uint32 tm;
241       int t;
242       for (t = 0; t < 16; t++)
243         {
244           x[t] = SWAP (*words);
245           words++;
246         }
247
248       R( a, b, c, d, e, F1, K1, x[ 0] );
249       R( e, a, b, c, d, F1, K1, x[ 1] );
250       R( d, e, a, b, c, F1, K1, x[ 2] );
251       R( c, d, e, a, b, F1, K1, x[ 3] );
252       R( b, c, d, e, a, F1, K1, x[ 4] );
253       R( a, b, c, d, e, F1, K1, x[ 5] );
254       R( e, a, b, c, d, F1, K1, x[ 6] );
255       R( d, e, a, b, c, F1, K1, x[ 7] );
256       R( c, d, e, a, b, F1, K1, x[ 8] );
257       R( b, c, d, e, a, F1, K1, x[ 9] );
258       R( a, b, c, d, e, F1, K1, x[10] );
259       R( e, a, b, c, d, F1, K1, x[11] );
260       R( d, e, a, b, c, F1, K1, x[12] );
261       R( c, d, e, a, b, F1, K1, x[13] );
262       R( b, c, d, e, a, F1, K1, x[14] );
263       R( a, b, c, d, e, F1, K1, x[15] );
264       R( e, a, b, c, d, F1, K1, M(16) );
265       R( d, e, a, b, c, F1, K1, M(17) );
266       R( c, d, e, a, b, F1, K1, M(18) );
267       R( b, c, d, e, a, F1, K1, M(19) );
268       R( a, b, c, d, e, F2, K2, M(20) );
269       R( e, a, b, c, d, F2, K2, M(21) );
270       R( d, e, a, b, c, F2, K2, M(22) );
271       R( c, d, e, a, b, F2, K2, M(23) );
272       R( b, c, d, e, a, F2, K2, M(24) );
273       R( a, b, c, d, e, F2, K2, M(25) );
274       R( e, a, b, c, d, F2, K2, M(26) );
275       R( d, e, a, b, c, F2, K2, M(27) );
276       R( c, d, e, a, b, F2, K2, M(28) );
277       R( b, c, d, e, a, F2, K2, M(29) );
278       R( a, b, c, d, e, F2, K2, M(30) );
279       R( e, a, b, c, d, F2, K2, M(31) );
280       R( d, e, a, b, c, F2, K2, M(32) );
281       R( c, d, e, a, b, F2, K2, M(33) );
282       R( b, c, d, e, a, F2, K2, M(34) );
283       R( a, b, c, d, e, F2, K2, M(35) );
284       R( e, a, b, c, d, F2, K2, M(36) );
285       R( d, e, a, b, c, F2, K2, M(37) );
286       R( c, d, e, a, b, F2, K2, M(38) );
287       R( b, c, d, e, a, F2, K2, M(39) );
288       R( a, b, c, d, e, F3, K3, M(40) );
289       R( e, a, b, c, d, F3, K3, M(41) );
290       R( d, e, a, b, c, F3, K3, M(42) );
291       R( c, d, e, a, b, F3, K3, M(43) );
292       R( b, c, d, e, a, F3, K3, M(44) );
293       R( a, b, c, d, e, F3, K3, M(45) );
294       R( e, a, b, c, d, F3, K3, M(46) );
295       R( d, e, a, b, c, F3, K3, M(47) );
296       R( c, d, e, a, b, F3, K3, M(48) );
297       R( b, c, d, e, a, F3, K3, M(49) );
298       R( a, b, c, d, e, F3, K3, M(50) );
299       R( e, a, b, c, d, F3, K3, M(51) );
300       R( d, e, a, b, c, F3, K3, M(52) );
301       R( c, d, e, a, b, F3, K3, M(53) );
302       R( b, c, d, e, a, F3, K3, M(54) );
303       R( a, b, c, d, e, F3, K3, M(55) );
304       R( e, a, b, c, d, F3, K3, M(56) );
305       R( d, e, a, b, c, F3, K3, M(57) );
306       R( c, d, e, a, b, F3, K3, M(58) );
307       R( b, c, d, e, a, F3, K3, M(59) );
308       R( a, b, c, d, e, F4, K4, M(60) );
309       R( e, a, b, c, d, F4, K4, M(61) );
310       R( d, e, a, b, c, F4, K4, M(62) );
311       R( c, d, e, a, b, F4, K4, M(63) );
312       R( b, c, d, e, a, F4, K4, M(64) );
313       R( a, b, c, d, e, F4, K4, M(65) );
314       R( e, a, b, c, d, F4, K4, M(66) );
315       R( d, e, a, b, c, F4, K4, M(67) );
316       R( c, d, e, a, b, F4, K4, M(68) );
317       R( b, c, d, e, a, F4, K4, M(69) );
318       R( a, b, c, d, e, F4, K4, M(70) );
319       R( e, a, b, c, d, F4, K4, M(71) );
320       R( d, e, a, b, c, F4, K4, M(72) );
321       R( c, d, e, a, b, F4, K4, M(73) );
322       R( b, c, d, e, a, F4, K4, M(74) );
323       R( a, b, c, d, e, F4, K4, M(75) );
324       R( e, a, b, c, d, F4, K4, M(76) );
325       R( d, e, a, b, c, F4, K4, M(77) );
326       R( c, d, e, a, b, F4, K4, M(78) );
327       R( b, c, d, e, a, F4, K4, M(79) );
328
329       a = ctx->A += a;
330       b = ctx->B += b;
331       c = ctx->C += c;
332       d = ctx->D += d;
333       e = ctx->E += e;
334     }
335 }
336
337 /* ---- Object-Oriented Wrapper */
338 SHA1Checksum::SHA1Checksum()
339 {
340     sha1_init_ctx(&ctx);
341 }
342
343 SHA1Checksum::~SHA1Checksum()
344 {
345 }
346
347 void SHA1Checksum::process(const void *data, size_t len)
348 {
349     sha1_process_bytes(data, len, &ctx);
350 }
351
352 bool SHA1Checksum::process_file(const char *filename)
353 {
354     FILE *f = fopen(filename, "rb");
355     if (f == NULL)
356         return false;
357
358     while (!feof(f)) {
359         char buf[4096];
360         size_t bytes = fread(buf, 1, sizeof(buf), f);
361
362         if (ferror(f)) {
363             fclose(f);
364             return false;
365         }
366
367         process(buf, bytes);
368     }
369
370     fclose(f);
371     return true;
372 }
373
374 const uint8_t *SHA1Checksum::checksum()
375 {
376     sha1_finish_ctx(&ctx, resbuf);
377     return (const uint8_t *)resbuf;
378 }
379
380 string SHA1Checksum::checksum_str()
381 {
382     uint8_t resbuf[20];
383     char hexbuf[4];
384     string result = "sha1=";
385
386     sha1_finish_ctx(&ctx, resbuf);
387
388     for (int i = 0; i < 20; i++) {
389         sprintf(hexbuf, "%02x", resbuf[i]);
390         result += hexbuf;
391     }
392
393     return result;
394 }