lavu: Add RIPEMD hashing
[ffmpeg.git] / libavutil / ripemd.c
1 /*
2  * Copyright (C) 2007 Michael Niedermayer <michaelni@gmx.at>
3  * Copyright (C) 2013 James Almer
4  *
5  * This file is part of FFmpeg.
6  *
7  * FFmpeg is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU Lesser General Public
9  * License as published by the Free Software Foundation; either
10  * version 2.1 of the License, or (at your option) any later version.
11  *
12  * FFmpeg is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
15  * Lesser General Public License for more details.
16  *
17  * You should have received a copy of the GNU Lesser General Public
18  * License along with FFmpeg; if not, write to the Free Software
19  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
20  */
21
22 #include <string.h>
23
24 #include "attributes.h"
25 #include "avutil.h"
26 #include "bswap.h"
27 #include "intreadwrite.h"
28 #include "ripemd.h"
29 #include "mem.h"
30
31 /** hash context */
32 typedef struct AVRIPEMD {
33     uint8_t  digest_len;  ///< digest length in 32-bit words
34     uint64_t count;       ///< number of bytes in buffer
35     uint8_t  buffer[64];  ///< 512-bit buffer of input values used in hash updating
36     uint32_t state[10];   ///< current hash value
37     uint8_t  ext;         ///< extension (0 for 128 and 160, 1 for 256 and 320)
38     /** function used to update hash for 512-bit input block */
39     void     (*transform)(uint32_t *state, const uint8_t buffer[64], int ext);
40 } AVRIPEMD;
41
42 const int av_ripemd_size = sizeof(AVRIPEMD);
43
44 struct AVRIPEMD *av_ripemd_alloc(void)
45 {
46     return av_mallocz(sizeof(struct AVRIPEMD));
47 }
48
49 static const uint32_t KA[4] = {
50     0x5a827999, 0x6ed9eba1, 0x8f1bbcdc, 0xa953fd4e
51 };
52
53 static const uint32_t KB[4] = {
54     0x50a28be6, 0x5c4dd124, 0x6d703ef3, 0x7a6d76e9
55 };
56
57 static const int ROTA[80] = {
58     11, 14, 15, 12,  5,  8,  7 , 9, 11, 13, 14, 15,  6,  7,  9,  8,
59      7 , 6,  8, 13, 11,  9,  7, 15,  7, 12, 15,  9, 11,  7, 13, 12,
60     11, 13,  6,  7, 14,  9, 13, 15, 14,  8, 13,  6,  5, 12,  7,  5,
61     11, 12, 14, 15, 14, 15,  9,  8,  9, 14,  5,  6,  8,  6,  5, 12,
62      9, 15,  5, 11,  6,  8, 13, 12,  5, 12, 13, 14, 11,  8,  5,  6
63 };
64
65 static const int ROTB[80] = {
66      8,  9,  9, 11, 13, 15, 15,  5,  7,  7,  8, 11, 14, 14, 12,  6,
67      9, 13, 15,  7, 12,  8,  9, 11,  7,  7, 12,  7,  6, 15, 13, 11,
68      9,  7, 15, 11,  8,  6,  6, 14, 12, 13,  5, 14, 13, 13,  7,  5,
69     15,  5,  8, 11, 14, 14,  6, 14,  6,  9, 12,  9, 12,  5, 15,  8,
70      8,  5, 12,  9, 12,  5, 14,  6,  8, 13,  6,  5, 15, 13, 11, 11
71 };
72
73 static const int WA[80] = {
74      0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14, 15,
75      7,  4, 13,  1, 10,  6, 15,  3, 12,  0,  9,  5,  2, 14, 11,  8,
76      3, 10, 14,  4,  9, 15,  8,  1,  2,  7,  0,  6, 13, 11,  5, 12,
77      1,  9, 11, 10,  0,  8, 12,  4, 13,  3,  7, 15, 14,  5,  6,  2,
78      4,  0,  5,  9,  7, 12,  2, 10, 14,  1,  3,  8, 11,  6, 15, 13
79 };
80
81 static const int WB[80] = {
82      5, 14,  7,  0,  9,  2, 11,  4, 13,  6, 15,  8,  1, 10,  3, 12,
83      6, 11,  3,  7,  0, 13,  5, 10, 14, 15,  8, 12,  4,  9,  1,  2,
84     15,  5,  1,  3,  7, 14,  6,  9, 11,  8, 12,  2, 10,  0,  4, 13,
85      8,  6,  4,  1,  3, 11, 15,  0,  5, 12,  2, 13,  9,  7, 10, 14,
86     12, 15, 10,  4,  1,  5,  8,  7,  6,  2, 13, 14,  0,  3,  9, 11
87 };
88
89 #define rol(value, bits) ((value << bits) | (value >> (32 - bits)))
90
91 #define SWAP(a,b) if (ext) { int t = a; a = b; b = t; }
92
93 #define ROUND128_0_TO_15(a,b,c,d,e,f,g,h)                               \
94     a = rol(a + ((  b ^ c  ^ d)      + block[WA[n]]),         ROTA[n]); \
95     e = rol(e + ((((f ^ g) & h) ^ g) + block[WB[n]] + KB[0]), ROTB[n]); \
96     n++
97
98 #define ROUND128_16_TO_31(a,b,c,d,e,f,g,h)                              \
99     a = rol(a + ((((c ^ d) & b) ^ d) + block[WA[n]] + KA[0]), ROTA[n]); \
100     e = rol(e + (((~g | f) ^ h)      + block[WB[n]] + KB[1]), ROTB[n]); \
101     n++
102
103 #define ROUND128_32_TO_47(a,b,c,d,e,f,g,h)                              \
104     a = rol(a + (((~c | b) ^ d)      + block[WA[n]] + KA[1]), ROTA[n]); \
105     e = rol(e + ((((g ^ h) & f) ^ h) + block[WB[n]] + KB[2]), ROTB[n]); \
106     n++
107
108 #define ROUND128_48_TO_63(a,b,c,d,e,f,g,h)                              \
109     a = rol(a + ((((b ^ c) & d) ^ c) + block[WA[n]] + KA[2]), ROTA[n]); \
110     e = rol(e + ((  f ^ g  ^ h)      + block[WB[n]]),         ROTB[n]); \
111     n++
112
113 static void ripemd128_transform(uint32_t *state, const uint8_t buffer[64], int ext)
114 {
115     uint32_t a, b, c, d, e, f, g, h;
116     uint32_t block[16];
117     int n;
118
119     if (ext) {
120         a = state[0]; b = state[1]; c = state[2]; d = state[3];
121         e = state[4]; f = state[5]; g = state[6]; h = state[7];
122     } else {
123         a = e = state[0];
124         b = f = state[1];
125         c = g = state[2];
126         d = h = state[3];
127     }
128
129     for (n = 0; n < 16; n++)
130         block[n] = AV_RL32(buffer + 4 * n);
131
132     for (n = 0; n < 16;) {
133         ROUND128_0_TO_15(a,b,c,d,e,f,g,h);
134         ROUND128_0_TO_15(d,a,b,c,h,e,f,g);
135         ROUND128_0_TO_15(c,d,a,b,g,h,e,f);
136         ROUND128_0_TO_15(b,c,d,a,f,g,h,e);
137     }
138     SWAP(a,e)
139
140     for (; n < 32;) {
141         ROUND128_16_TO_31(a,b,c,d,e,f,g,h);
142         ROUND128_16_TO_31(d,a,b,c,h,e,f,g);
143         ROUND128_16_TO_31(c,d,a,b,g,h,e,f);
144         ROUND128_16_TO_31(b,c,d,a,f,g,h,e);
145     }
146     SWAP(b,f)
147
148     for (; n < 48;) {
149         ROUND128_32_TO_47(a,b,c,d,e,f,g,h);
150         ROUND128_32_TO_47(d,a,b,c,h,e,f,g);
151         ROUND128_32_TO_47(c,d,a,b,g,h,e,f);
152         ROUND128_32_TO_47(b,c,d,a,f,g,h,e);
153     }
154     SWAP(c,g)
155
156     for (; n < 64;) {
157         ROUND128_48_TO_63(a,b,c,d,e,f,g,h);
158         ROUND128_48_TO_63(d,a,b,c,h,e,f,g);
159         ROUND128_48_TO_63(c,d,a,b,g,h,e,f);
160         ROUND128_48_TO_63(b,c,d,a,f,g,h,e);
161     }
162     SWAP(d,h)
163
164     if (ext) {
165         state[0] += a; state[1] += b; state[2] += c; state[3] += d;
166         state[4] += e; state[5] += f; state[6] += g; state[7] += h;
167     } else {
168         h += c + state[1];
169         state[1] = state[2] + d + e;
170         state[2] = state[3] + a + f;
171         state[3] = state[0] + b + g;
172         state[0] = h;
173     }
174 }
175
176 #define ROTATE(x,y) \
177     x = rol(x, 10); \
178     y = rol(y, 10); \
179     n++
180
181 #define ROUND160_0_TO_15(a,b,c,d,e,f,g,h,i,j)                               \
182     a = rol(a + ((  b ^ c  ^ d)      + block[WA[n]]),         ROTA[n]) + e; \
183     f = rol(f + (((~i | h) ^ g)      + block[WB[n]] + KB[0]), ROTB[n]) + j; \
184     ROTATE(c,h)
185
186 #define ROUND160_16_TO_31(a,b,c,d,e,f,g,h,i,j)                              \
187     a = rol(a + ((((c ^ d) & b) ^ d) + block[WA[n]] + KA[0]), ROTA[n]) + e; \
188     f = rol(f + ((((g ^ h) & i) ^ h) + block[WB[n]] + KB[1]), ROTB[n]) + j; \
189     ROTATE(c,h)
190
191 #define ROUND160_32_TO_47(a,b,c,d,e,f,g,h,i,j)                              \
192     a = rol(a + (((~c | b) ^ d)      + block[WA[n]] + KA[1]), ROTA[n]) + e; \
193     f = rol(f + (((~h | g) ^ i)      + block[WB[n]] + KB[2]), ROTB[n]) + j; \
194     ROTATE(c,h)
195
196 #define ROUND160_48_TO_63(a,b,c,d,e,f,g,h,i,j)                              \
197     a = rol(a + ((((b ^ c) & d) ^ c) + block[WA[n]] + KA[2]), ROTA[n]) + e; \
198     f = rol(f + ((((h ^ i) & g) ^ i) + block[WB[n]] + KB[3]), ROTB[n]) + j; \
199     ROTATE(c,h)
200
201 #define ROUND160_64_TO_79(a,b,c,d,e,f,g,h,i,j)                              \
202     a = rol(a + (((~d | c) ^ b)      + block[WA[n]] + KA[3]), ROTA[n]) + e; \
203     f = rol(f + ((  g ^ h  ^ i)      + block[WB[n]]),         ROTB[n]) + j; \
204     ROTATE(c,h)
205
206 static void ripemd160_transform(uint32_t *state, const uint8_t buffer[64], int ext)
207 {
208     uint32_t a, b, c, d, e, f, g, h, i, j;
209     uint32_t block[16];
210     int n;
211
212     if (ext) {
213         a = state[0]; b = state[1]; c = state[2]; d = state[3]; e = state[4];
214         f = state[5]; g = state[6]; h = state[7]; i = state[8]; j = state[9];
215     } else {
216         a = f = state[0];
217         b = g = state[1];
218         c = h = state[2];
219         d = i = state[3];
220         e = j = state[4];
221     }
222
223     for (n = 0; n < 16; n++)
224         block[n] = AV_RL32(buffer + 4 * n);
225
226     for (n = 0; n < 16 - 1;) {
227         ROUND160_0_TO_15(a,b,c,d,e,f,g,h,i,j);
228         ROUND160_0_TO_15(e,a,b,c,d,j,f,g,h,i);
229         ROUND160_0_TO_15(d,e,a,b,c,i,j,f,g,h);
230         ROUND160_0_TO_15(c,d,e,a,b,h,i,j,f,g);
231         ROUND160_0_TO_15(b,c,d,e,a,g,h,i,j,f);
232     }
233     ROUND160_0_TO_15(a,b,c,d,e,f,g,h,i,j);
234     SWAP(a,f)
235
236     for (; n < 32 - 1;) {
237         ROUND160_16_TO_31(e,a,b,c,d,j,f,g,h,i);
238         ROUND160_16_TO_31(d,e,a,b,c,i,j,f,g,h);
239         ROUND160_16_TO_31(c,d,e,a,b,h,i,j,f,g);
240         ROUND160_16_TO_31(b,c,d,e,a,g,h,i,j,f);
241         ROUND160_16_TO_31(a,b,c,d,e,f,g,h,i,j);
242     }
243     ROUND160_16_TO_31(e,a,b,c,d,j,f,g,h,i);
244     SWAP(b,g)
245
246     for (; n < 48 - 1;) {
247         ROUND160_32_TO_47(d,e,a,b,c,i,j,f,g,h);
248         ROUND160_32_TO_47(c,d,e,a,b,h,i,j,f,g);
249         ROUND160_32_TO_47(b,c,d,e,a,g,h,i,j,f);
250         ROUND160_32_TO_47(a,b,c,d,e,f,g,h,i,j);
251         ROUND160_32_TO_47(e,a,b,c,d,j,f,g,h,i);
252     }
253     ROUND160_32_TO_47(d,e,a,b,c,i,j,f,g,h);
254     SWAP(c,h)
255
256     for (; n < 64 - 1;) {
257         ROUND160_48_TO_63(c,d,e,a,b,h,i,j,f,g);
258         ROUND160_48_TO_63(b,c,d,e,a,g,h,i,j,f);
259         ROUND160_48_TO_63(a,b,c,d,e,f,g,h,i,j);
260         ROUND160_48_TO_63(e,a,b,c,d,j,f,g,h,i);
261         ROUND160_48_TO_63(d,e,a,b,c,i,j,f,g,h);
262     }
263     ROUND160_48_TO_63(c,d,e,a,b,h,i,j,f,g);
264     SWAP(d,i)
265
266     for (; n < 80 - 1;) {
267         ROUND160_64_TO_79(b,c,d,e,a,g,h,i,j,f);
268         ROUND160_64_TO_79(a,b,c,d,e,f,g,h,i,j);
269         ROUND160_64_TO_79(e,a,b,c,d,j,f,g,h,i);
270         ROUND160_64_TO_79(d,e,a,b,c,i,j,f,g,h);
271         ROUND160_64_TO_79(c,d,e,a,b,h,i,j,f,g);
272     }
273     ROUND160_64_TO_79(b,c,d,e,a,g,h,i,j,f);
274     SWAP(e,j)
275
276     if (ext) {
277         state[0] += a; state[1] += b; state[2] += c; state[3] += d; state[4] += e;
278         state[5] += f; state[6] += g; state[7] += h; state[8] += i; state[9] += j;
279     } else {
280         i += c + state[1];
281         state[1] = state[2] + d + j;
282         state[2] = state[3] + e + f;
283         state[3] = state[4] + a + g;
284         state[4] = state[0] + b + h;
285         state[0] = i;
286     }
287 }
288
289 av_cold int av_ripemd_init(AVRIPEMD *ctx, int bits)
290 {
291     ctx->digest_len = bits >> 5;
292     switch (bits) {
293     case 128: // RIPEMD-128
294         ctx->state[0] = 0x67452301;
295         ctx->state[1] = 0xEFCDAB89;
296         ctx->state[2] = 0x98BADCFE;
297         ctx->state[3] = 0x10325476;
298         ctx->transform = ripemd128_transform;
299         ctx->ext = 0;
300         break;
301     case 160: // RIPEMD-160
302         ctx->state[0] = 0x67452301;
303         ctx->state[1] = 0xEFCDAB89;
304         ctx->state[2] = 0x98BADCFE;
305         ctx->state[3] = 0x10325476;
306         ctx->state[4] = 0xC3D2E1F0;
307         ctx->transform = ripemd160_transform;
308         ctx->ext = 0;
309         break;
310     case 256: // RIPEMD-256
311         ctx->state[0] = 0x67452301;
312         ctx->state[1] = 0xEFCDAB89;
313         ctx->state[2] = 0x98BADCFE;
314         ctx->state[3] = 0x10325476;
315         ctx->state[4] = 0x76543210;
316         ctx->state[5] = 0xFEDCBA98;
317         ctx->state[6] = 0x89ABCDEF;
318         ctx->state[7] = 0x01234567;
319         ctx->transform = ripemd128_transform;
320         ctx->ext = 1;
321         break;
322     case 320: // RIPEMD-320
323         ctx->state[0] = 0x67452301;
324         ctx->state[1] = 0xEFCDAB89;
325         ctx->state[2] = 0x98BADCFE;
326         ctx->state[3] = 0x10325476;
327         ctx->state[4] = 0xC3D2E1F0;
328         ctx->state[5] = 0x76543210;
329         ctx->state[6] = 0xFEDCBA98;
330         ctx->state[7] = 0x89ABCDEF;
331         ctx->state[8] = 0x01234567;
332         ctx->state[9] = 0x3C2D1E0F;
333         ctx->transform = ripemd160_transform;
334         ctx->ext = 1;
335         break;
336     default:
337         return -1;
338     }
339     ctx->count = 0;
340     return 0;
341 }
342
343 void av_ripemd_update(AVRIPEMD* ctx, const uint8_t* data, unsigned int len)
344 {
345     unsigned int i, j;
346
347     j = ctx->count & 63;
348     ctx->count += len;
349 #if CONFIG_SMALL
350     for (i = 0; i < len; i++) {
351         ctx->buffer[j++] = data[i];
352         if (64 == j) {
353             ctx->transform(ctx->state, ctx->buffer, ctx->ext);
354             j = 0;
355         }
356     }
357 #else
358     if ((j + len) > 63) {
359         memcpy(&ctx->buffer[j], data, (i = 64 - j));
360         ctx->transform(ctx->state, ctx->buffer, ctx->ext);
361         for (; i + 63 < len; i += 64)
362             ctx->transform(ctx->state, &data[i], ctx->ext);
363         j = 0;
364     } else
365         i = 0;
366     memcpy(&ctx->buffer[j], &data[i], len - i);
367 #endif
368 }
369
370 void av_ripemd_final(AVRIPEMD* ctx, uint8_t *digest)
371 {
372     int i;
373     uint64_t finalcount = av_le2ne64(ctx->count << 3);
374
375     av_ripemd_update(ctx, "\200", 1);
376     while ((ctx->count & 63) != 56)
377         av_ripemd_update(ctx, "", 1);
378     av_ripemd_update(ctx, (uint8_t *)&finalcount, 8); /* Should cause a transform() */
379     for (i = 0; i < ctx->digest_len; i++)
380         AV_WL32(digest + i*4, ctx->state[i]);
381 }
382
383 #ifdef TEST
384 #include <stdio.h>
385
386 int main(void)
387 {
388     int i, j, k;
389     AVRIPEMD ctx;
390     unsigned char digest[40];
391     const int lengths[4] = { 128, 160, 256, 320 };
392
393     for (j = 0; j < 4; j++) {
394         printf("Testing RIPEMD-%d\n", lengths[j]);
395         for (k = 0; k < 3; k++) {
396             av_ripemd_init(&ctx, lengths[j]);
397             if (k == 0)
398                 av_ripemd_update(&ctx, "abc", 3);
399             else if (k == 1)
400                 av_ripemd_update(&ctx, "abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq", 56);
401             else
402                 for (i = 0; i < 1000*1000; i++)
403                     av_ripemd_update(&ctx, "a", 1);
404             av_ripemd_final(&ctx, digest);
405             for (i = 0; i < lengths[j] >> 3; i++)
406                 printf("%02X", digest[i]);
407             putchar('\n');
408         }
409         switch (j) { //test vectors (from ISO:IEC 10118-3 (2004) and http://homes.esat.kuleuven.be/~bosselae/ripemd160.html)
410         case 0:
411             printf("c14a1219 9c66e4ba 84636b0f 69144c77\n"
412                    "a1aa0689 d0fafa2d dc22e88b 49133a06\n"
413                    "4a7f5723 f954eba1 216c9d8f 6320431f\n");
414             break;
415         case 1:
416             printf("8eb208f7 e05d987a 9b044a8e 98c6b087 f15a0bfc\n"
417                    "12a05338 4a9c0c88 e405a06c 27dcf49a da62eb2b\n"
418                    "52783243 c1697bdb e16d37f9 7f68f083 25dc1528\n");
419             break;
420         case 2:
421             printf("afbd6e22 8b9d8cbb cef5ca2d 03e6dba1 0ac0bc7d cbe4680e 1e42d2e9 75459b65\n"
422                    "38430455 83aac6c8 c8d91285 73e7a980 9afb2a0f 34ccc36e a9e72f16 f6368e3f\n"
423                    "ac953744 e10e3151 4c150d4d 8d7b6773 42e33399 788296e4 3ae4850c e4f97978\n");
424             break;
425         case 3:
426             printf("de4c01b3 054f8930 a79d09ae 738e9230 1e5a1708 5beffdc1 b8d11671 3e74f82f a942d64c dbc4682d\n"
427                    "d034a795 0cf72202 1ba4b84d f769a5de 2060e259 df4c9bb4 a4268c0e 935bbc74 70a969c9 d072a1ac\n"
428                    "bdee37f4 371e2064 6b8b0d86 2dda1629 2ae36f40 965e8c85 09e63d1d bddecc50 3e2b63eb 9245bb66\n");
429             break;
430         }
431     }
432
433     return 0;
434 }
435 #endif