librsync  2.0.1
mdfour.c
1 /*= -*- c-basic-offset: 4; indent-tabs-mode: nil; -*-
2  *
3  * librsync -- the library for network deltas
4  *
5  * Copyright (C) 2000, 2001 by Martin Pool <mbp@sourcefrog.net>
6  * Copyright (C) 1997-1999 by Andrew Tridgell
7  * Copyright (C) 2002, 2003 by Donovan Baarda <abo@minkirri.apana.org.au>
8  *
9  * This program is free software; you can redistribute it and/or modify
10  * it under the terms of the GNU Lesser General Public License as published by
11  * the Free Software Foundation; either version 2.1 of the License, or
12  * (at your option) any later version.
13  *
14  * This program is distributed in the hope that it will be useful,
15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17  * GNU Lesser General Public License for more details.
18  *
19  * You should have received a copy of the GNU Lesser General Public License
20  * along with this program; if not, write to the Free Software
21  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
22  */
23 
24 /* MD4 message digest algorithm.
25  *
26  * TODO: Perhaps use the MD4 routine from OpenSSL if it's installed.
27  * It's probably not worth the trouble.
28  *
29  * This was originally written by Andrew Tridgell for use in Samba.
30  * It was then modified by;
31  *
32  * 2002-06-xx: Robert Weber <robert.weber@Colorado.edu>
33  * optimisations and fixed >512M support.
34  *
35  * 2002-06-27: Donovan Baarda <abo@minkirri.apana.org.au>
36  * further optimisations and cleanups.
37  *
38  * 2004-09-09: Simon Law <sfllaw@debian.org>
39  * handle little-endian machines that can't do unaligned access
40  * (e.g. ia64, pa-risc).
41  */
42 
43 #include "config.h"
44 
45 #include <stdlib.h>
46 #include <string.h>
47 #include <stdio.h>
48 
49 #include "librsync.h"
50 #include "trace.h"
51 #include "mdfour.h"
52 
53 
54 #define F(X,Y,Z) (((X)&(Y)) | ((~(X))&(Z)))
55 #define G(X,Y,Z) (((X)&(Y)) | ((X)&(Z)) | ((Y)&(Z)))
56 #define H(X,Y,Z) ((X)^(Y)^(Z))
57 #define lshift(x,s) (((x)<<(s)) | ((x)>>(32-(s))))
58 
59 #define ROUND1(a,b,c,d,k,s) a = lshift(a + F(b,c,d) + X[k], s)
60 #define ROUND2(a,b,c,d,k,s) a = lshift(a + G(b,c,d) + X[k] + 0x5A827999,s)
61 #define ROUND3(a,b,c,d,k,s) a = lshift(a + H(b,c,d) + X[k] + 0x6ED9EBA1,s)
62 
63 /** padding data used for finalising */
64 static unsigned char PADDING[64] = {
65  0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
66  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
67  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
68 };
69 
70 
71 static void
72 rs_mdfour_block(rs_mdfour_t *md, void const *p);
73 
74 
75 
76 /**
77  * Update an MD4 accumulator from a 64-byte chunk.
78  *
79  * This cannot be used for the last chunk of the file, which must be
80  * padded and contain the file length. rs_mdfour_tail() is used for
81  * that.
82  *
83  * \todo Recode to be fast, and to use system integer types. Perhaps
84  * if we can find an mdfour implementation already on the system
85  * (e.g. in OpenSSL) then we should use it instead of our own?
86  *
87  * \param X A series of integer, read little-endian from the file.
88  */
89 static void
90 rs_mdfour64(rs_mdfour_t * m, const void *p)
91 {
92  uint32_t AA, BB, CC, DD;
93  uint32_t A, B, C, D;
94  const uint32_t *X = (const uint32_t *) p;
95 
96  A = m->A;
97  B = m->B;
98  C = m->C;
99  D = m->D;
100  AA = A;
101  BB = B;
102  CC = C;
103  DD = D;
104 
105  ROUND1(A, B, C, D, 0, 3);
106  ROUND1(D, A, B, C, 1, 7);
107  ROUND1(C, D, A, B, 2, 11);
108  ROUND1(B, C, D, A, 3, 19);
109  ROUND1(A, B, C, D, 4, 3);
110  ROUND1(D, A, B, C, 5, 7);
111  ROUND1(C, D, A, B, 6, 11);
112  ROUND1(B, C, D, A, 7, 19);
113  ROUND1(A, B, C, D, 8, 3);
114  ROUND1(D, A, B, C, 9, 7);
115  ROUND1(C, D, A, B, 10, 11);
116  ROUND1(B, C, D, A, 11, 19);
117  ROUND1(A, B, C, D, 12, 3);
118  ROUND1(D, A, B, C, 13, 7);
119  ROUND1(C, D, A, B, 14, 11);
120  ROUND1(B, C, D, A, 15, 19);
121 
122  ROUND2(A, B, C, D, 0, 3);
123  ROUND2(D, A, B, C, 4, 5);
124  ROUND2(C, D, A, B, 8, 9);
125  ROUND2(B, C, D, A, 12, 13);
126  ROUND2(A, B, C, D, 1, 3);
127  ROUND2(D, A, B, C, 5, 5);
128  ROUND2(C, D, A, B, 9, 9);
129  ROUND2(B, C, D, A, 13, 13);
130  ROUND2(A, B, C, D, 2, 3);
131  ROUND2(D, A, B, C, 6, 5);
132  ROUND2(C, D, A, B, 10, 9);
133  ROUND2(B, C, D, A, 14, 13);
134  ROUND2(A, B, C, D, 3, 3);
135  ROUND2(D, A, B, C, 7, 5);
136  ROUND2(C, D, A, B, 11, 9);
137  ROUND2(B, C, D, A, 15, 13);
138 
139  ROUND3(A, B, C, D, 0, 3);
140  ROUND3(D, A, B, C, 8, 9);
141  ROUND3(C, D, A, B, 4, 11);
142  ROUND3(B, C, D, A, 12, 15);
143  ROUND3(A, B, C, D, 2, 3);
144  ROUND3(D, A, B, C, 10, 9);
145  ROUND3(C, D, A, B, 6, 11);
146  ROUND3(B, C, D, A, 14, 15);
147  ROUND3(A, B, C, D, 1, 3);
148  ROUND3(D, A, B, C, 9, 9);
149  ROUND3(C, D, A, B, 5, 11);
150  ROUND3(B, C, D, A, 13, 15);
151  ROUND3(A, B, C, D, 3, 3);
152  ROUND3(D, A, B, C, 11, 9);
153  ROUND3(C, D, A, B, 7, 11);
154  ROUND3(B, C, D, A, 15, 15);
155 
156  A += AA;
157  B += BB;
158  C += CC;
159  D += DD;
160 
161  m->A = A;
162  m->B = B;
163  m->C = C;
164  m->D = D;
165 }
166 
167 
168 /**
169  * These next routines are necessary because MD4 is specified in terms of
170  * little-endian int32s, but we have a byte buffer. On little-endian
171  * platforms, I think we can just use the buffer pointer directly.
172  *
173  * There are some nice endianness routines in glib, including assembler
174  * variants. If we ever depended on glib, then it could be good to use them
175  * instead. */
176 inline static void
177 copy4( /* @out@ */ unsigned char *out, uint32_t const x)
178 {
179  out[0] = x;
180  out[1] = x >> 8;
181  out[2] = x >> 16;
182  out[3] = x >> 24;
183 }
184 
185 
186 /* We need this if there is a uint64 */
187 /* --robert.weber@Colorado.edu */
188 #ifdef HAVE_UINT64
189 inline static void
190 copy8( /* @out@ */ unsigned char *out, uint64_t const x)
191 {
192  out[0] = x;
193  out[1] = x >> 8;
194  out[2] = x >> 16;
195  out[3] = x >> 24;
196  out[4] = x >> 32;
197  out[5] = x >> 40;
198  out[6] = x >> 48;
199  out[7] = x >> 56;
200 }
201 #endif /* HAVE_UINT64 */
202 
203 
204 /* We only need this if we are big-endian */
205 #ifdef WORDS_BIGENDIAN
206 inline static void
207 copy64( /* @out@ */ uint32_t * M, unsigned char const *in)
208 {
209  int i=16;
210 
211  while (i--) {
212  *M++ = (in[3] << 24) | (in[2] << 16) | (in[1] << 8) | in[0];
213  in += 4;
214  }
215 }
216 
217 
218 /**
219  * Accumulate a block, making appropriate conversions for bigendian
220  * machines.
221  */
222 inline static void
223 rs_mdfour_block(rs_mdfour_t *md, void const *p)
224 {
225  uint32_t M[16];
226 
227  copy64(M, p);
228  rs_mdfour64(md, M);
229 }
230 
231 
232 #else /* WORDS_BIGENDIAN */
233 
234 # ifdef __i386__
235 
236 /* If we are on an IA-32 machine, we can process directly. */
237 inline static void
238 rs_mdfour_block(rs_mdfour_t *md, void const *p)
239 {
240  rs_mdfour64(md,p);
241 }
242 
243 # else /* !WORDS_BIGENDIAN && !__i386__ */
244 
245 /* We are little-endian, but not on i386 and therefore may not be able
246  * to do unaligned access safely/quickly.
247  *
248  * So if the input is not already aligned correctly, copy it to an
249  * aligned buffer first. */
250 inline static void
251 rs_mdfour_block(rs_mdfour_t *md, void const *p)
252 {
253  unsigned long ptrval = (unsigned long) p;
254 
255  if (ptrval & 3) {
256  uint32_t M[16];
257 
258  memcpy(M, p, 16 * sizeof(uint32_t));
259  rs_mdfour64(md, M);
260  } else {
261  rs_mdfour64(md, (const uint32_t *) p);
262  }
263 }
264 
265 # endif /* ! __i386__ */
266 #endif /* WORDS_BIGENDIAN */
267 
268 
269 void
270 rs_mdfour_begin(rs_mdfour_t * md)
271 {
272  memset(md, 0, sizeof(*md));
273  md->A = 0x67452301;
274  md->B = 0xefcdab89;
275  md->C = 0x98badcfe;
276  md->D = 0x10325476;
277 #if HAVE_UINT64
278  md->totalN = 0;
279 #else
280  md->totalN_hi = md->totalN_lo = 0;
281 #endif
282 }
283 
284 
285 /**
286  * Handle special behaviour for processing the last block of a file
287  * when calculating its MD4 checksum.
288  *
289  * This must be called exactly once per file.
290  *
291  * Modified by Robert Weber to use uint64 in order that we can sum files
292  * > 2^29 = 512 MB.
293  * --Robert.Weber@colorado.edu
294  */
295 static void
296 rs_mdfour_tail(rs_mdfour_t * m)
297 {
298 #ifdef HAVE_UINT64
299  uint64_t b;
300 #else /* HAVE_UINT64 */
301  uint32_t b[2];
302 #endif /* HAVE_UINT64 */
303  unsigned char buf[8];
304  size_t pad_len;
305 
306  /* convert the totalN byte count into a bit count buffer */
307 #ifdef HAVE_UINT64
308  b = m->totalN << 3;
309  copy8(buf, b);
310 #else /* HAVE_UINT64 */
311  b[0] = m->totalN_lo << 3;
312  b[1] = ((m->totalN_hi << 3) | (m->totalN_lo >> 29));
313  copy4(buf, b[0]);
314  copy4(buf + 4, b[1]);
315 #endif /* HAVE_UINT64 */
316 
317  /* calculate length and process the padding data */
318  pad_len=(m->tail_len <56) ? (56 - m->tail_len) : (120 - m->tail_len);
319  rs_mdfour_update(m,PADDING,pad_len);
320  /* process the bit count */
321  rs_mdfour_update(m,buf,8);
322 }
323 
324 
325 void
326 rs_mdfour_update(rs_mdfour_t * md, void const *in_void, size_t n)
327 {
328  unsigned char const *in = (unsigned char const *) in_void;
329 
330  /* increment totalN */
331 #ifdef HAVE_UINT64
332  md->totalN+=n;
333 #else /* HAVE_UINT64 */
334  if ((md->totalN_lo += n) < n)
335  md->totalN_hi++;
336 #endif /* HAVE_UINT64 */
337 
338  /* If there's any leftover data in the tail buffer, then first we have
339  * to make it up to a whole block to process it. */
340  if (md->tail_len) {
341  size_t tail_gap = 64 - md->tail_len;
342  if (tail_gap <= n) {
343  memcpy(&md->tail[md->tail_len], in, tail_gap);
344  rs_mdfour_block(md, md->tail);
345  in += tail_gap;
346  n -= tail_gap;
347  md->tail_len = 0;
348  }
349  }
350  /* process complete blocks of input */
351  while (n >= 64) {
352  rs_mdfour_block(md, in);
353  in += 64;
354  n -= 64;
355  }
356  /* Put remaining bytes onto tail*/
357  if (n) {
358  memcpy(&md->tail[md->tail_len], in, n);
359  md->tail_len += n;
360  }
361 }
362 
363 
364 void
365 rs_mdfour_result(rs_mdfour_t * md, unsigned char *out)
366 {
367  rs_mdfour_tail(md);
368 
369  copy4(out, md->A);
370  copy4(out + 4, md->B);
371  copy4(out + 8, md->C);
372  copy4(out + 12, md->D);
373 }
374 
375 
376 void
377 rs_mdfour(unsigned char *out, void const *in, size_t n)
378 {
379  rs_mdfour_t md;
380 
381  rs_mdfour_begin(&md);
382  rs_mdfour_update(&md, in, n);
383  rs_mdfour_result(&md, out);
384 }
Public header for librsync.
void rs_mdfour_update(rs_mdfour_t *md, void const *in_void, size_t n)
Feed some data into the MD4 accumulator.
Definition: mdfour.c:326
struct rs_mdfour rs_mdfour_t
MD4 message-digest accumulator.
Definition: librsync.h:267