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