/*
* Simple MD5 implementation
*
* Compile with: gcc -o md5 md5.c
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <time.h>
#define N 100000
// leftrotate function definition
#define F(x, y, z) (z ^ ( x & (y ^ z) ))
#define G(x, y, z) (y ^ ( z & (y ^ x) ))
#define H(x, y, z) ((x) ^ (y) ^ (z))
#define I(x, y, z) ((y) ^ ((x) | (~z)))
#define LEFTROTATE(x, c) (((x) << (c)) | ((x) >> (32 - (c))))
#define FF(a, b, c, d, x, s, ac) { \
(a) += F((b), (c), (d)) + (x) + (uint32_t)(ac); \
(a) = LEFTROTATE((a), (s)); \
(a) += (b); \
}
#define GG(a, b, c, d, x, s, ac) { \
(a) += G((b), (c), (d)) + (x) + (uint32_t)(ac); \
(a) = LEFTROTATE((a), (s)); \
(a) += (b); \
}
#define HH(a, b, c, d, x, s, ac) { \
(a) += H((b), (c), (d)) + (x) + (uint32_t)(ac); \
(a) = LEFTROTATE((a), (s)); \
(a) += (b); \
}
#define II(a, b, c, d, x, s, ac) { \
(a) += I((b), (c), (d)) + (x) + (uint32_t)(ac); \
(a) = LEFTROTATE((a), (s)); \
(a) += (b); \
}
void to_bytes(uint32_t val, uint8_t *bytes)
{
bytes[0] = (uint8_t) val;
bytes[1] = (uint8_t) (val >> 8);
bytes[2] = (uint8_t) (val >> 16);
bytes[3] = (uint8_t) (val >> 24);
}
uint32_t to_int32(const uint8_t *bytes)
{
return (uint32_t) bytes[0]
| ((uint32_t) bytes[1] << 8)
| ((uint32_t) bytes[2] << 16)
| ((uint32_t) bytes[3] << 24);
}
void md5(const uint8_t *initial_msg, size_t initial_len, uint8_t *digest) {
// These vars will contain the hash
register uint32_t h0, h1, h2, h3;
// Message (to prepare)
uint8_t *msg = NULL;
size_t new_len, offset;
uint32_t w[16];
register uint32_t a, b, c, d, i, f, temp;
// Initialize variables - simple count in nibbles:
h0 = 0x67452301;
h1 = 0xefcdab89;
h2 = 0x98badcfe;
h3 = 0x10325476;
//Pre-processing:
//append "1" bit to message
//append "0" bits until message length in bits is 448 (mod 512)
//append length mod (2^64) to message
new_len = initial_len + 1;
int mod = new_len & 0x3F;
if(mod > 56) new_len += 120 - mod;
else if(mod < 56) new_len += 56 - mod;
// allocate a msg with new length
msg = (uint8_t*)malloc(new_len + 8);
// copy the original msg to the new one
memcpy(msg, initial_msg, initial_len);
// append "1" bit. Note that for a computer, 8bit is the minimum length of a datatype
msg[initial_len] = 0x80;
if(initial_len + 1 < new_len)
memset(&msg[initial_len + 1], 0, sizeof(uint8_t) * (new_len - 1 - initial_len));
for (offset = initial_len + 1; offset < new_len; ++offset)
msg[offset] = 0; // append "0" bits
// append the lower 32 bits of len in bits at the end of the buffer.
to_bytes(initial_len<<3, msg + new_len);
// append the higher 32 bits of len in bits at the end of the buffer.
to_bytes(initial_len >> 29, msg + new_len + 4);
// Process the message in successive 512-bit chunks:
//for each 512-bit chunk of message:
for(offset=0; offset<new_len; offset += 64) {
// break chunk into sixteen 32-bit words w[j], from 0 to 15
for (i = 0; i < 16; ++i)
w[i] = *((uint32_t*)(msg + offset + (i<<2)));
// Initialize hash value for this chunk:
a = h0;
b = h1;
c = h2;
d = h3;
FF(a, b, c, d, w[ 0], 7, 0xD76AA478);
FF(d, a, b, c, w[ 1], 12, 0xE8C7B756);
FF(c, d, a, b, w[ 2], 17, 0x242070DB);
FF(b, c, d, a, w[ 3], 22, 0xC1BDCEEE);
FF(a, b, c, d, w[ 4], 7, 0xF57C0FAF);
FF(d, a, b, c, w[ 5], 12, 0x4787C62A);
FF(c, d, a, b, w[ 6], 17, 0xA8304613);
FF(b, c, d, a, w[ 7], 22, 0xFD469501);
FF(a, b, c, d, w[ 8], 7, 0x698098D8);
FF(d, a, b, c, w[ 9], 12, 0x8B44F7AF);
FF(c, d, a, b, w[10], 17, 0xFFFF5BB1);
FF(b, c, d, a, w[11], 22, 0x895CD7BE);
FF(a, b, c, d, w[12], 7, 0x6B901122);
FF(d, a, b, c, w[13], 12, 0xFD987193);
FF(c, d, a, b, w[14], 17, 0xA679438E);
FF(b, c, d, a, w[15], 22, 0x49B40821);
GG(a, b, c, d, w[ 1], 5, 0xF61E2562);
GG(d, a, b, c, w[ 6], 9, 0xC040B340);
GG(c, d, a, b, w[11], 14, 0x265E5A51);
GG(b, c, d, a, w[ 0], 20, 0xE9B6C7AA);
GG(a, b, c, d, w[ 5], 5, 0xD62F105D);
GG(d, a, b, c, w[10], 9, 0x02441453);
GG(c, d, a, b, w[15], 14, 0xD8A1E681);
GG(b, c, d, a, w[ 4], 20, 0xE7D3FBC8);
GG(a, b, c, d, w[ 9], 5, 0x21E1CDE6);
GG(d, a, b, c, w[14], 9, 0xC33707D6);
GG(c, d, a, b, w[ 3], 14, 0xF4D50D87);
GG(b, c, d, a, w[ 8], 20, 0x455A14ED);
GG(a, b, c, d, w[13], 5, 0xA9E3E905);
GG(d, a, b, c, w[ 2], 9, 0xFCEFA3F8);
GG(c, d, a, b, w[ 7], 14, 0x676F02D9);
GG(b, c, d, a, w[12], 20, 0x8D2A4C8A);
HH(a, b, c, d, w[ 5], 4, 0xFFFA3942);
HH(d, a, b, c, w[ 8], 11, 0x8771F681);
HH(c, d, a, b, w[11], 16, 0x6D9D6122);
HH(b, c, d, a, w[14], 23, 0xFDE5380C);
HH(a, b, c, d, w[ 1], 4, 0xA4BEEA44);
HH(d, a, b, c, w[ 4], 11, 0x4BDECFA9);
HH(c, d, a, b, w[ 7], 16, 0xF6BB4B60);
HH(b, c, d, a, w[10], 23, 0xBEBFBC70);
HH(a, b, c, d, w[13], 4, 0x289B7EC6);
HH(d, a, b, c, w[ 0], 11, 0xEAA127FA);
HH(c, d, a, b, w[ 3], 16, 0xD4EF3085);
HH(b, c, d, a, w[ 6], 23, 0x04881D05);
HH(a, b, c, d, w[ 9], 4, 0xD9D4D039);
HH(d, a, b, c, w[12], 11, 0xE6DB99E5);
HH(c, d, a, b, w[15], 16, 0x1FA27CF8);
HH(b, c, d, a, w[ 2], 23, 0xC4AC5665);
II(a, b, c, d, w[ 0], 6, 0xF4292244);
II(d, a, b, c, w[ 7], 10, 0x432AFF97);
II(c, d, a, b, w[14], 15, 0xAB9423A7);
II(b, c, d, a, w[ 5], 21, 0xFC93A039);
II(a, b, c, d, w[12], 6, 0x655B59C3);
II(d, a, b, c, w[ 3], 10, 0x8F0CCC92);
II(c, d, a, b, w[10], 15, 0xFFEFF47D);
II(b, c, d, a, w[ 1], 21, 0x85845DD1);
II(a, b, c, d, w[ 8], 6, 0x6FA87E4F);
II(d, a, b, c, w[15], 10, 0xFE2CE6E0);
II(c, d, a, b, w[ 6], 15, 0xA3014314);
II(b, c, d, a, w[13], 21, 0x4E0811A1);
II(a, b, c, d, w[ 4], 6, 0xF7537E82);
II(d, a, b, c, w[11], 10, 0xBD3AF235);
II(c, d, a, b, w[ 2], 15, 0x2AD7D2BB);
II(b, c, d, a, w[ 9], 21, 0xEB86D391);
// Add this chunk's hash to result so far:
h0 += a;
h1 += b;
h2 += c;
h3 += d;
}
// cleanup
free(msg);
//var char digest[16] := h0 append h1 append h2 append h3 //(Output is in little-endian)
*((uint32_t*)digest) = h0;
*((uint32_t*)(digest + 4)) = h1;
*((uint32_t*)(digest + 8)) = h2;
*((uint32_t*)(digest + 12)) = h3;
}
int main(int argc, char **argv) {
char *msg = argv[1];
size_t len;
int i;
uint8_t result[16];
if (argc < 2) {
printf("usage: %s 'string'\n", argv[0]);
return 1;
}
len = strlen(msg);
clock_t start_time = clock();
// benchmark
for (i = 0; i < N; i++) {
md5((uint8_t*)msg, len, result);
}
// display result
for (i = 0; i < 16; i++)
printf("%2.2x", result[i]);
puts("");
return 0;
}
LyoKICogU2ltcGxlIE1ENSBpbXBsZW1lbnRhdGlvbgogKgogKiBDb21waWxlIHdpdGg6IGdjYyAtbyBtZDUgbWQ1LmMKICovCiNpbmNsdWRlIDxzdGRpby5oPgojaW5jbHVkZSA8c3RkbGliLmg+CiNpbmNsdWRlIDxzdHJpbmcuaD4KI2luY2x1ZGUgPHN0ZGludC5oPgojaW5jbHVkZSA8dGltZS5oPgogCiNkZWZpbmUgTiAxMDAwMDAKCi8vIGxlZnRyb3RhdGUgZnVuY3Rpb24gZGVmaW5pdGlvbgoKI2RlZmluZSBGKHgsIHksIHopICh6IF4gKCB4ICYgKHkgXiB6KSApKQojZGVmaW5lIEcoeCwgeSwgeikgKHkgXiAoIHogJiAoeSBeIHgpICkpCiNkZWZpbmUgSCh4LCB5LCB6KSAoKHgpIF4gKHkpIF4gKHopKQojZGVmaW5lIEkoeCwgeSwgeikgKCh5KSBeICgoeCkgfCAofnopKSkKCiNkZWZpbmUgTEVGVFJPVEFURSh4LCBjKSAoKCh4KSA8PCAoYykpIHwgKCh4KSA+PiAoMzIgLSAoYykpKSkKCiNkZWZpbmUgRkYoYSwgYiwgYywgZCwgeCwgcywgYWMpIHsgXAoJKGEpICs9IEYoKGIpLCAoYyksIChkKSkgKyAoeCkgKyAodWludDMyX3QpKGFjKTsgXAoJKGEpID0gTEVGVFJPVEFURSgoYSksIChzKSk7IFwKCShhKSArPSAoYik7IFwKfQogCiNkZWZpbmUgR0coYSwgYiwgYywgZCwgeCwgcywgYWMpIHsgXAoJKGEpICs9IEcoKGIpLCAoYyksIChkKSkgKyAoeCkgKyAodWludDMyX3QpKGFjKTsgXAoJKGEpID0gTEVGVFJPVEFURSgoYSksIChzKSk7IFwKCShhKSArPSAoYik7IFwKfQoKI2RlZmluZSBISChhLCBiLCBjLCBkLCB4LCBzLCBhYykgeyBcCgkoYSkgKz0gSCgoYiksIChjKSwgKGQpKSArICh4KSArICh1aW50MzJfdCkoYWMpOyBcCgkoYSkgPSBMRUZUUk9UQVRFKChhKSwgKHMpKTsgXAoJKGEpICs9IChiKTsgXAp9CgojZGVmaW5lIElJKGEsIGIsIGMsIGQsIHgsIHMsIGFjKSB7IFwKCShhKSArPSBJKChiKSwgKGMpLCAoZCkpICsgKHgpICsgKHVpbnQzMl90KShhYyk7IFwKCShhKSA9IExFRlRST1RBVEUoKGEpLCAocykpOyBcCgkoYSkgKz0gKGIpOyBcCn0KCnZvaWQgdG9fYnl0ZXModWludDMyX3QgdmFsLCB1aW50OF90ICpieXRlcykKewogICAgYnl0ZXNbMF0gPSAodWludDhfdCkgdmFsOwogICAgYnl0ZXNbMV0gPSAodWludDhfdCkgKHZhbCA+PiA4KTsKICAgIGJ5dGVzWzJdID0gKHVpbnQ4X3QpICh2YWwgPj4gMTYpOwogICAgYnl0ZXNbM10gPSAodWludDhfdCkgKHZhbCA+PiAyNCk7Cn0KIAp1aW50MzJfdCB0b19pbnQzMihjb25zdCB1aW50OF90ICpieXRlcykKewogICAgcmV0dXJuICh1aW50MzJfdCkgYnl0ZXNbMF0KICAgICAgICB8ICgodWludDMyX3QpIGJ5dGVzWzFdIDw8IDgpCiAgICAgICAgfCAoKHVpbnQzMl90KSBieXRlc1syXSA8PCAxNikKICAgICAgICB8ICgodWludDMyX3QpIGJ5dGVzWzNdIDw8IDI0KTsKfQogCnZvaWQgbWQ1KGNvbnN0IHVpbnQ4X3QgKmluaXRpYWxfbXNnLCBzaXplX3QgaW5pdGlhbF9sZW4sIHVpbnQ4X3QgKmRpZ2VzdCkgewogCiAgICAvLyBUaGVzZSB2YXJzIHdpbGwgY29udGFpbiB0aGUgaGFzaAogICAgcmVnaXN0ZXIgdWludDMyX3QgaDAsIGgxLCBoMiwgaDM7CiAKICAgIC8vIE1lc3NhZ2UgKHRvIHByZXBhcmUpCiAgICB1aW50OF90ICptc2cgPSBOVUxMOwogCiAgICBzaXplX3QgbmV3X2xlbiwgb2Zmc2V0OwogICAgdWludDMyX3Qgd1sxNl07CiAgICByZWdpc3RlciB1aW50MzJfdCBhLCBiLCBjLCBkLCBpLCBmLCB0ZW1wOwogCiAgICAvLyBJbml0aWFsaXplIHZhcmlhYmxlcyAtIHNpbXBsZSBjb3VudCBpbiBuaWJibGVzOgogICAgaDAgPSAweDY3NDUyMzAxOwogICAgaDEgPSAweGVmY2RhYjg5OwogICAgaDIgPSAweDk4YmFkY2ZlOwogICAgaDMgPSAweDEwMzI1NDc2OwogCiAgICAvL1ByZS1wcm9jZXNzaW5nOgogICAgLy9hcHBlbmQgIjEiIGJpdCB0byBtZXNzYWdlICAKICAgIC8vYXBwZW5kICIwIiBiaXRzIHVudGlsIG1lc3NhZ2UgbGVuZ3RoIGluIGJpdHMgaXMgNDQ4IChtb2QgNTEyKQogICAgLy9hcHBlbmQgbGVuZ3RoIG1vZCAoMl42NCkgdG8gbWVzc2FnZQogCgoJbmV3X2xlbiA9IGluaXRpYWxfbGVuICsgMTsKCglpbnQgbW9kID0gbmV3X2xlbiAmIDB4M0Y7CgoJaWYobW9kID4gNTYpIG5ld19sZW4gKz0gMTIwIC0gbW9kOwoJZWxzZSBpZihtb2QgPCA1NikgbmV3X2xlbiArPSA1NiAtIG1vZDsKCiAKCS8vIGFsbG9jYXRlIGEgbXNnIHdpdGggbmV3IGxlbmd0aAogICAgbXNnID0gKHVpbnQ4X3QqKW1hbGxvYyhuZXdfbGVuICsgOCk7CgkvLyBjb3B5IHRoZSBvcmlnaW5hbCBtc2cgdG8gdGhlIG5ldyBvbmUKICAgIG1lbWNweShtc2csIGluaXRpYWxfbXNnLCBpbml0aWFsX2xlbik7CgkvLyBhcHBlbmQgIjEiIGJpdC4gTm90ZSB0aGF0IGZvciBhIGNvbXB1dGVyLCA4Yml0IGlzIHRoZSBtaW5pbXVtIGxlbmd0aCBvZiBhIGRhdGF0eXBlCiAgICBtc2dbaW5pdGlhbF9sZW5dID0gMHg4MDsgCgoJaWYoaW5pdGlhbF9sZW4gKyAxIDwgbmV3X2xlbikKCQltZW1zZXQoJm1zZ1tpbml0aWFsX2xlbiArIDFdLCAwLCBzaXplb2YodWludDhfdCkgKiAobmV3X2xlbiAtIDEgLSBpbml0aWFsX2xlbikpOwoKICAgIGZvciAob2Zmc2V0ID0gaW5pdGlhbF9sZW4gKyAxOyBvZmZzZXQgPCBuZXdfbGVuOyArK29mZnNldCkKICAgICAgICBtc2dbb2Zmc2V0XSA9IDA7IC8vIGFwcGVuZCAiMCIgYml0cwogCiAgICAvLyBhcHBlbmQgdGhlIGxvd2VyIDMyIGJpdHMgb2YgbGVuIGluIGJpdHMgYXQgdGhlIGVuZCBvZiB0aGUgYnVmZmVyLgogICAgdG9fYnl0ZXMoaW5pdGlhbF9sZW48PDMsIG1zZyArIG5ld19sZW4pOwogICAgLy8gYXBwZW5kIHRoZSBoaWdoZXIgMzIgYml0cyBvZiBsZW4gaW4gYml0cyBhdCB0aGUgZW5kIG9mIHRoZSBidWZmZXIuCiAgICB0b19ieXRlcyhpbml0aWFsX2xlbiA+PiAyOSwgbXNnICsgbmV3X2xlbiArIDQpOwogCiAgICAvLyBQcm9jZXNzIHRoZSBtZXNzYWdlIGluIHN1Y2Nlc3NpdmUgNTEyLWJpdCBjaHVua3M6CiAgICAvL2ZvciBlYWNoIDUxMi1iaXQgY2h1bmsgb2YgbWVzc2FnZToKICAgIGZvcihvZmZzZXQ9MDsgb2Zmc2V0PG5ld19sZW47IG9mZnNldCArPSA2NCkgewogCiAgICAgICAgLy8gYnJlYWsgY2h1bmsgaW50byBzaXh0ZWVuIDMyLWJpdCB3b3JkcyB3W2pdLCBmcm9tIDAgdG8gMTUKICAgICAgICBmb3IgKGkgPSAwOyBpIDwgMTY7ICsraSkKICAgICAgICAgICAgd1tpXSA9ICooKHVpbnQzMl90KikobXNnICsgb2Zmc2V0ICsgKGk8PDIpKSk7CiAKICAgICAgICAvLyBJbml0aWFsaXplIGhhc2ggdmFsdWUgZm9yIHRoaXMgY2h1bms6CiAgICAgICAgYSA9IGgwOwogICAgICAgIGIgPSBoMTsKICAgICAgICBjID0gaDI7CiAgICAgICAgZCA9IGgzOwogCgkJRkYoYSwgYiwgYywgZCwgd1sgMF0sICA3LCAweEQ3NkFBNDc4KTsKCQlGRihkLCBhLCBiLCBjLCB3WyAxXSwgMTIsIDB4RThDN0I3NTYpOwoJCUZGKGMsIGQsIGEsIGIsIHdbIDJdLCAxNywgMHgyNDIwNzBEQik7CgkJRkYoYiwgYywgZCwgYSwgd1sgM10sIDIyLCAweEMxQkRDRUVFKTsKCQlGRihhLCBiLCBjLCBkLCB3WyA0XSwgIDcsIDB4RjU3QzBGQUYpOwoJCUZGKGQsIGEsIGIsIGMsIHdbIDVdLCAxMiwgMHg0Nzg3QzYyQSk7CgkJRkYoYywgZCwgYSwgYiwgd1sgNl0sIDE3LCAweEE4MzA0NjEzKTsKCQlGRihiLCBjLCBkLCBhLCB3WyA3XSwgMjIsIDB4RkQ0Njk1MDEpOwoJCUZGKGEsIGIsIGMsIGQsIHdbIDhdLCAgNywgMHg2OTgwOThEOCk7CgkJRkYoZCwgYSwgYiwgYywgd1sgOV0sIDEyLCAweDhCNDRGN0FGKTsKCQlGRihjLCBkLCBhLCBiLCB3WzEwXSwgMTcsIDB4RkZGRjVCQjEpOwoJCUZGKGIsIGMsIGQsIGEsIHdbMTFdLCAyMiwgMHg4OTVDRDdCRSk7CgkJRkYoYSwgYiwgYywgZCwgd1sxMl0sICA3LCAweDZCOTAxMTIyKTsKCQlGRihkLCBhLCBiLCBjLCB3WzEzXSwgMTIsIDB4RkQ5ODcxOTMpOwoJCUZGKGMsIGQsIGEsIGIsIHdbMTRdLCAxNywgMHhBNjc5NDM4RSk7CgkJRkYoYiwgYywgZCwgYSwgd1sxNV0sIDIyLCAweDQ5QjQwODIxKTsKCQlHRyhhLCBiLCBjLCBkLCB3WyAxXSwgIDUsIDB4RjYxRTI1NjIpOwoJCUdHKGQsIGEsIGIsIGMsIHdbIDZdLCAgOSwgMHhDMDQwQjM0MCk7CgkJR0coYywgZCwgYSwgYiwgd1sxMV0sIDE0LCAweDI2NUU1QTUxKTsKCQlHRyhiLCBjLCBkLCBhLCB3WyAwXSwgMjAsIDB4RTlCNkM3QUEpOwoJCUdHKGEsIGIsIGMsIGQsIHdbIDVdLCAgNSwgMHhENjJGMTA1RCk7CgkJR0coZCwgYSwgYiwgYywgd1sxMF0sICA5LCAweDAyNDQxNDUzKTsKCQlHRyhjLCBkLCBhLCBiLCB3WzE1XSwgMTQsIDB4RDhBMUU2ODEpOwoJCUdHKGIsIGMsIGQsIGEsIHdbIDRdLCAyMCwgMHhFN0QzRkJDOCk7CgkJR0coYSwgYiwgYywgZCwgd1sgOV0sICA1LCAweDIxRTFDREU2KTsKCQlHRyhkLCBhLCBiLCBjLCB3WzE0XSwgIDksIDB4QzMzNzA3RDYpOwoJCUdHKGMsIGQsIGEsIGIsIHdbIDNdLCAxNCwgMHhGNEQ1MEQ4Nyk7CgkJR0coYiwgYywgZCwgYSwgd1sgOF0sIDIwLCAweDQ1NUExNEVEKTsKCQlHRyhhLCBiLCBjLCBkLCB3WzEzXSwgIDUsIDB4QTlFM0U5MDUpOwoJCUdHKGQsIGEsIGIsIGMsIHdbIDJdLCAgOSwgMHhGQ0VGQTNGOCk7CgkJR0coYywgZCwgYSwgYiwgd1sgN10sIDE0LCAweDY3NkYwMkQ5KTsKCQlHRyhiLCBjLCBkLCBhLCB3WzEyXSwgMjAsIDB4OEQyQTRDOEEpOwoJCUhIKGEsIGIsIGMsIGQsIHdbIDVdLCAgNCwgMHhGRkZBMzk0Mik7CgkJSEgoZCwgYSwgYiwgYywgd1sgOF0sIDExLCAweDg3NzFGNjgxKTsKCQlISChjLCBkLCBhLCBiLCB3WzExXSwgMTYsIDB4NkQ5RDYxMjIpOwoJCUhIKGIsIGMsIGQsIGEsIHdbMTRdLCAyMywgMHhGREU1MzgwQyk7CgkJSEgoYSwgYiwgYywgZCwgd1sgMV0sICA0LCAweEE0QkVFQTQ0KTsKCQlISChkLCBhLCBiLCBjLCB3WyA0XSwgMTEsIDB4NEJERUNGQTkpOwoJCUhIKGMsIGQsIGEsIGIsIHdbIDddLCAxNiwgMHhGNkJCNEI2MCk7CgkJSEgoYiwgYywgZCwgYSwgd1sxMF0sIDIzLCAweEJFQkZCQzcwKTsKCQlISChhLCBiLCBjLCBkLCB3WzEzXSwgIDQsIDB4Mjg5QjdFQzYpOwoJCUhIKGQsIGEsIGIsIGMsIHdbIDBdLCAxMSwgMHhFQUExMjdGQSk7CgkJSEgoYywgZCwgYSwgYiwgd1sgM10sIDE2LCAweEQ0RUYzMDg1KTsKCQlISChiLCBjLCBkLCBhLCB3WyA2XSwgMjMsIDB4MDQ4ODFEMDUpOwoJCUhIKGEsIGIsIGMsIGQsIHdbIDldLCAgNCwgMHhEOUQ0RDAzOSk7CgkJSEgoZCwgYSwgYiwgYywgd1sxMl0sIDExLCAweEU2REI5OUU1KTsKCQlISChjLCBkLCBhLCBiLCB3WzE1XSwgMTYsIDB4MUZBMjdDRjgpOwoJCUhIKGIsIGMsIGQsIGEsIHdbIDJdLCAyMywgMHhDNEFDNTY2NSk7CgkJSUkoYSwgYiwgYywgZCwgd1sgMF0sICA2LCAweEY0MjkyMjQ0KTsKCQlJSShkLCBhLCBiLCBjLCB3WyA3XSwgMTAsIDB4NDMyQUZGOTcpOwoJCUlJKGMsIGQsIGEsIGIsIHdbMTRdLCAxNSwgMHhBQjk0MjNBNyk7CgkJSUkoYiwgYywgZCwgYSwgd1sgNV0sIDIxLCAweEZDOTNBMDM5KTsKCQlJSShhLCBiLCBjLCBkLCB3WzEyXSwgIDYsIDB4NjU1QjU5QzMpOwoJCUlJKGQsIGEsIGIsIGMsIHdbIDNdLCAxMCwgMHg4RjBDQ0M5Mik7CgkJSUkoYywgZCwgYSwgYiwgd1sxMF0sIDE1LCAweEZGRUZGNDdEKTsKCQlJSShiLCBjLCBkLCBhLCB3WyAxXSwgMjEsIDB4ODU4NDVERDEpOwoJCUlJKGEsIGIsIGMsIGQsIHdbIDhdLCAgNiwgMHg2RkE4N0U0Rik7CgkJSUkoZCwgYSwgYiwgYywgd1sxNV0sIDEwLCAweEZFMkNFNkUwKTsKCQlJSShjLCBkLCBhLCBiLCB3WyA2XSwgMTUsIDB4QTMwMTQzMTQpOwoJCUlJKGIsIGMsIGQsIGEsIHdbMTNdLCAyMSwgMHg0RTA4MTFBMSk7CgkJSUkoYSwgYiwgYywgZCwgd1sgNF0sICA2LCAweEY3NTM3RTgyKTsKCQlJSShkLCBhLCBiLCBjLCB3WzExXSwgMTAsIDB4QkQzQUYyMzUpOwoJCUlJKGMsIGQsIGEsIGIsIHdbIDJdLCAxNSwgMHgyQUQ3RDJCQik7CgkJSUkoYiwgYywgZCwgYSwgd1sgOV0sIDIxLCAweEVCODZEMzkxKTsKIAogICAgICAgIC8vIEFkZCB0aGlzIGNodW5rJ3MgaGFzaCB0byByZXN1bHQgc28gZmFyOgogICAgICAgIGgwICs9IGE7CiAgICAgICAgaDEgKz0gYjsKICAgICAgICBoMiArPSBjOwogICAgICAgIGgzICs9IGQ7CiAKICAgIH0KIAogICAgLy8gY2xlYW51cAogICAgZnJlZShtc2cpOwogCiAgICAvL3ZhciBjaGFyIGRpZ2VzdFsxNl0gOj0gaDAgYXBwZW5kIGgxIGFwcGVuZCBoMiBhcHBlbmQgaDMgLy8oT3V0cHV0IGlzIGluIGxpdHRsZS1lbmRpYW4pCgkqKCh1aW50MzJfdCopZGlnZXN0KSA9IGgwOwoJKigodWludDMyX3QqKShkaWdlc3QgKyA0KSkgPSBoMTsKCSooKHVpbnQzMl90KikoZGlnZXN0ICsgOCkpID0gaDI7CgkqKCh1aW50MzJfdCopKGRpZ2VzdCArIDEyKSkgPSBoMzsKfQogCmludCBtYWluKGludCBhcmdjLCBjaGFyICoqYXJndikgewogICAgY2hhciAqbXNnID0gYXJndlsxXTsKICAgIHNpemVfdCBsZW47CiAgICBpbnQgaTsKICAgIHVpbnQ4X3QgcmVzdWx0WzE2XTsKIAogICAgaWYgKGFyZ2MgPCAyKSB7CiAgICAgICAgcHJpbnRmKCJ1c2FnZTogJXMgJ3N0cmluZydcbiIsIGFyZ3ZbMF0pOwogICAgICAgIHJldHVybiAxOwogICAgfQogCiAgICBsZW4gPSBzdHJsZW4obXNnKTsKCgljbG9ja190IHN0YXJ0X3RpbWUgPSBjbG9jaygpOwogCiAgICAvLyBiZW5jaG1hcmsKICAgIGZvciAoaSA9IDA7IGkgPCBOOyBpKyspIHsKICAgICAgICBtZDUoKHVpbnQ4X3QqKW1zZywgbGVuLCByZXN1bHQpOwogICAgfQogCiAgICAvLyBkaXNwbGF5IHJlc3VsdAogICAgZm9yIChpID0gMDsgaSA8IDE2OyBpKyspCiAgICAgICAgcHJpbnRmKCIlMi4yeCIsIHJlc3VsdFtpXSk7CiAgICBwdXRzKCIiKTsKIAogICAgcmV0dXJuIDA7Cn0=