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