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 */
59static 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
65static 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. */
79static 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. */
163inline 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
174inline 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
189inline 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 */
203inline 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. */
216inline 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. */
228inline 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
243void 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
292void 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
329void 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
339void 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