improved load balancing algorithm.
[l2tpns.git] / md5.c
1 /*
2 * This is an OpenSSL-compatible implementation of the RSA Data Security,
3 * Inc. MD5 Message-Digest Algorithm.
4 *
5 * Written by Solar Designer <solar at openwall.com> in 2001, and placed
6 * in the public domain. There's absolutely no warranty.
7 *
8 * This differs from Colin Plumb's older public domain implementation in
9 * that no 32-bit integer data type is required, there's no compile-time
10 * endianness configuration, and the function prototypes match OpenSSL's.
11 * The primary goals are portability and ease of use.
12 *
13 * This implementation is meant to be fast, but not as fast as possible.
14 * Some known optimizations are not included to reduce source code size
15 * and avoid compile-time configuration.
16 */
17
18 #include <string.h>
19 #include "md5.h"
20
21 /*
22 * The basic MD5 functions.
23 *
24 * F is optimized compared to its RFC 1321 definition just like in Colin
25 * Plumb's implementation.
26 */
27 #define F(x, y, z) ((z) ^ ((x) & ((y) ^ (z))))
28 #define G(x, y, z) ((y) ^ ((z) & ((x) ^ (y))))
29 #define H(x, y, z) ((x) ^ (y) ^ (z))
30 #define I(x, y, z) ((y) ^ ((x) | ~(z)))
31
32 /*
33 * The MD5 transformation for all four rounds.
34 */
35 #define STEP(f, a, b, c, d, x, t, s) \
36 (a) += f((b), (c), (d)) + (x) + (t); \
37 (a) = (((a) << (s)) | (((a) & 0xffffffff) >> (32 - (s)))); \
38 (a) += (b);
39
40 /*
41 * SET reads 4 input bytes in little-endian byte order and stores them
42 * in a properly aligned word in host byte order.
43 *
44 * The check for little-endian architectures which tolerate unaligned
45 * memory accesses is just an optimization. Nothing will break if it
46 * doesn't work.
47 */
48 #if defined(__i386__) || defined(__vax__)
49 # define SET(n) (*(MD5_u32plus *)&ptr[(n) * 4])
50 # define GET(n) SET(n)
51 #else
52 # define SET(n) \
53 (ctx->block[(n)] = \
54 (MD5_u32plus)ptr[(n) * 4] | \
55 ((MD5_u32plus)ptr[(n) * 4 + 1] << 8) | \
56 ((MD5_u32plus)ptr[(n) * 4 + 2] << 16) | \
57 ((MD5_u32plus)ptr[(n) * 4 + 3] << 24))
58 # define GET(n) \
59 (ctx->block[(n)])
60 #endif
61
62 /*
63 * This processes one or more 64-byte data blocks, but does NOT update
64 * the bit counters. There're no alignment requirements.
65 */
66 static void *body(MD5_CTX *ctx, void *data, unsigned long size)
67 {
68 unsigned char *ptr;
69 MD5_u32plus a, b, c, d;
70 MD5_u32plus saved_a, saved_b, saved_c, saved_d;
71
72 ptr = data;
73
74 a = ctx->a;
75 b = ctx->b;
76 c = ctx->c;
77 d = ctx->d;
78
79 do {
80 saved_a = a;
81 saved_b = b;
82 saved_c = c;
83 saved_d = d;
84
85 /* Round 1 */
86 STEP(F, a, b, c, d, SET(0), 0xd76aa478, 7)
87 STEP(F, d, a, b, c, SET(1), 0xe8c7b756, 12)
88 STEP(F, c, d, a, b, SET(2), 0x242070db, 17)
89 STEP(F, b, c, d, a, SET(3), 0xc1bdceee, 22)
90 STEP(F, a, b, c, d, SET(4), 0xf57c0faf, 7)
91 STEP(F, d, a, b, c, SET(5), 0x4787c62a, 12)
92 STEP(F, c, d, a, b, SET(6), 0xa8304613, 17)
93 STEP(F, b, c, d, a, SET(7), 0xfd469501, 22)
94 STEP(F, a, b, c, d, SET(8), 0x698098d8, 7)
95 STEP(F, d, a, b, c, SET(9), 0x8b44f7af, 12)
96 STEP(F, c, d, a, b, SET(10), 0xffff5bb1, 17)
97 STEP(F, b, c, d, a, SET(11), 0x895cd7be, 22)
98 STEP(F, a, b, c, d, SET(12), 0x6b901122, 7)
99 STEP(F, d, a, b, c, SET(13), 0xfd987193, 12)
100 STEP(F, c, d, a, b, SET(14), 0xa679438e, 17)
101 STEP(F, b, c, d, a, SET(15), 0x49b40821, 22)
102
103 /* Round 2 */
104 STEP(G, a, b, c, d, GET(1), 0xf61e2562, 5)
105 STEP(G, d, a, b, c, GET(6), 0xc040b340, 9)
106 STEP(G, c, d, a, b, GET(11), 0x265e5a51, 14)
107 STEP(G, b, c, d, a, GET(0), 0xe9b6c7aa, 20)
108 STEP(G, a, b, c, d, GET(5), 0xd62f105d, 5)
109 STEP(G, d, a, b, c, GET(10), 0x02441453, 9)
110 STEP(G, c, d, a, b, GET(15), 0xd8a1e681, 14)
111 STEP(G, b, c, d, a, GET(4), 0xe7d3fbc8, 20)
112 STEP(G, a, b, c, d, GET(9), 0x21e1cde6, 5)
113 STEP(G, d, a, b, c, GET(14), 0xc33707d6, 9)
114 STEP(G, c, d, a, b, GET(3), 0xf4d50d87, 14)
115 STEP(G, b, c, d, a, GET(8), 0x455a14ed, 20)
116 STEP(G, a, b, c, d, GET(13), 0xa9e3e905, 5)
117 STEP(G, d, a, b, c, GET(2), 0xfcefa3f8, 9)
118 STEP(G, c, d, a, b, GET(7), 0x676f02d9, 14)
119 STEP(G, b, c, d, a, GET(12), 0x8d2a4c8a, 20)
120
121 /* Round 3 */
122 STEP(H, a, b, c, d, GET(5), 0xfffa3942, 4)
123 STEP(H, d, a, b, c, GET(8), 0x8771f681, 11)
124 STEP(H, c, d, a, b, GET(11), 0x6d9d6122, 16)
125 STEP(H, b, c, d, a, GET(14), 0xfde5380c, 23)
126 STEP(H, a, b, c, d, GET(1), 0xa4beea44, 4)
127 STEP(H, d, a, b, c, GET(4), 0x4bdecfa9, 11)
128 STEP(H, c, d, a, b, GET(7), 0xf6bb4b60, 16)
129 STEP(H, b, c, d, a, GET(10), 0xbebfbc70, 23)
130 STEP(H, a, b, c, d, GET(13), 0x289b7ec6, 4)
131 STEP(H, d, a, b, c, GET(0), 0xeaa127fa, 11)
132 STEP(H, c, d, a, b, GET(3), 0xd4ef3085, 16)
133 STEP(H, b, c, d, a, GET(6), 0x04881d05, 23)
134 STEP(H, a, b, c, d, GET(9), 0xd9d4d039, 4)
135 STEP(H, d, a, b, c, GET(12), 0xe6db99e5, 11)
136 STEP(H, c, d, a, b, GET(15), 0x1fa27cf8, 16)
137 STEP(H, b, c, d, a, GET(2), 0xc4ac5665, 23)
138
139 /* Round 4 */
140 STEP(I, a, b, c, d, GET(0), 0xf4292244, 6)
141 STEP(I, d, a, b, c, GET(7), 0x432aff97, 10)
142 STEP(I, c, d, a, b, GET(14), 0xab9423a7, 15)
143 STEP(I, b, c, d, a, GET(5), 0xfc93a039, 21)
144 STEP(I, a, b, c, d, GET(12), 0x655b59c3, 6)
145 STEP(I, d, a, b, c, GET(3), 0x8f0ccc92, 10)
146 STEP(I, c, d, a, b, GET(10), 0xffeff47d, 15)
147 STEP(I, b, c, d, a, GET(1), 0x85845dd1, 21)
148 STEP(I, a, b, c, d, GET(8), 0x6fa87e4f, 6)
149 STEP(I, d, a, b, c, GET(15), 0xfe2ce6e0, 10)
150 STEP(I, c, d, a, b, GET(6), 0xa3014314, 15)
151 STEP(I, b, c, d, a, GET(13), 0x4e0811a1, 21)
152 STEP(I, a, b, c, d, GET(4), 0xf7537e82, 6)
153 STEP(I, d, a, b, c, GET(11), 0xbd3af235, 10)
154 STEP(I, c, d, a, b, GET(2), 0x2ad7d2bb, 15)
155 STEP(I, b, c, d, a, GET(9), 0xeb86d391, 21)
156
157 a += saved_a;
158 b += saved_b;
159 c += saved_c;
160 d += saved_d;
161
162 ptr += MD5_BLOCK_SZ;
163 } while (size -= MD5_BLOCK_SZ);
164
165 ctx->a = a;
166 ctx->b = b;
167 ctx->c = c;
168 ctx->d = d;
169
170 return ptr;
171 }
172
173 void MD5_Init(MD5_CTX *ctx)
174 {
175 ctx->a = 0x67452301;
176 ctx->b = 0xefcdab89;
177 ctx->c = 0x98badcfe;
178 ctx->d = 0x10325476;
179
180 ctx->lo = 0;
181 ctx->hi = 0;
182 }
183
184 void MD5_Update(MD5_CTX *ctx, void *data, unsigned long size)
185 {
186 MD5_u32plus saved_lo;
187 unsigned long used, free;
188
189 saved_lo = ctx->lo;
190 if ((ctx->lo = (saved_lo + size) & 0x1fffffff) < saved_lo)
191 ctx->hi++;
192
193 ctx->hi += size >> 29;
194
195 used = saved_lo & 0x3f;
196
197 if (used)
198 {
199 free = MD5_BLOCK_SZ - used;
200
201 if (size < free)
202 {
203 memcpy(&ctx->buffer[used], data, size);
204 return;
205 }
206
207 memcpy(&ctx->buffer[used], data, free);
208 data = (unsigned char *)data + free;
209 size -= free;
210 body(ctx, ctx->buffer, MD5_BLOCK_SZ);
211 }
212
213 if (size >= MD5_BLOCK_SZ)
214 {
215 data = body(ctx, data, size & ~(unsigned long)0x3f);
216 size &= 0x3f;
217 }
218
219 memcpy(ctx->buffer, data, size);
220 }
221
222 void MD5_Final(unsigned char *result, MD5_CTX *ctx)
223 {
224 unsigned long used, free;
225
226 used = ctx->lo & 0x3f;
227
228 ctx->buffer[used++] = 0x80;
229
230 free = MD5_BLOCK_SZ - used;
231
232 if (free < 8)
233 {
234 memset(&ctx->buffer[used], 0, free);
235 body(ctx, ctx->buffer, MD5_BLOCK_SZ);
236 used = 0;
237 free = MD5_BLOCK_SZ;
238 }
239
240 memset(&ctx->buffer[used], 0, free - 8);
241
242 ctx->lo <<= 3;
243 ctx->buffer[56] = ctx->lo;
244 ctx->buffer[57] = ctx->lo >> 8;
245 ctx->buffer[58] = ctx->lo >> 16;
246 ctx->buffer[59] = ctx->lo >> 24;
247 ctx->buffer[60] = ctx->hi;
248 ctx->buffer[61] = ctx->hi >> 8;
249 ctx->buffer[62] = ctx->hi >> 16;
250 ctx->buffer[63] = ctx->hi >> 24;
251
252 body(ctx, ctx->buffer, MD5_BLOCK_SZ);
253
254 result[0] = ctx->a;
255 result[1] = ctx->a >> 8;
256 result[2] = ctx->a >> 16;
257 result[3] = ctx->a >> 24;
258 result[4] = ctx->b;
259 result[5] = ctx->b >> 8;
260 result[6] = ctx->b >> 16;
261 result[7] = ctx->b >> 24;
262 result[8] = ctx->c;
263 result[9] = ctx->c >> 8;
264 result[10] = ctx->c >> 16;
265 result[11] = ctx->c >> 24;
266 result[12] = ctx->d;
267 result[13] = ctx->d >> 8;
268 result[14] = ctx->d >> 16;
269 result[15] = ctx->d >> 24;
270
271 memset(ctx, 0, sizeof(*ctx));
272 }