1259698Sdim/* 2259698Sdim * This code is derived from (original license follows): 3259698Sdim * 4259698Sdim * This is an OpenSSL-compatible implementation of the RSA Data Security, Inc. 5259698Sdim * MD5 Message-Digest Algorithm (RFC 1321). 6259698Sdim * 7259698Sdim * Homepage: 8259698Sdim * http://openwall.info/wiki/people/solar/software/public-domain-source-code/md5 9259698Sdim * 10259698Sdim * Author: 11259698Sdim * Alexander Peslyak, better known as Solar Designer <solar at openwall.com> 12259698Sdim * 13259698Sdim * This software was written by Alexander Peslyak in 2001. No copyright is 14259698Sdim * claimed, and the software is hereby placed in the public domain. 15259698Sdim * In case this attempt to disclaim copyright and place the software in the 16259698Sdim * public domain is deemed null and void, then the software is 17259698Sdim * Copyright (c) 2001 Alexander Peslyak and it is hereby released to the 18259698Sdim * general public under the following terms: 19259698Sdim * 20259698Sdim * Redistribution and use in source and binary forms, with or without 21259698Sdim * modification, are permitted. 22259698Sdim * 23259698Sdim * There's ABSOLUTELY NO WARRANTY, express or implied. 24259698Sdim * 25259698Sdim * (This is a heavily cut-down "BSD license".) 26259698Sdim * 27259698Sdim * This differs from Colin Plumb's older public domain implementation in that 28259698Sdim * no exactly 32-bit integer data type is required (any 32-bit or wider 29259698Sdim * unsigned integer data type will do), there's no compile-time endianness 30259698Sdim * configuration, and the function prototypes match OpenSSL's. No code from 31259698Sdim * Colin Plumb's implementation has been reused; this comment merely compares 32259698Sdim * the properties of the two independent implementations. 33259698Sdim * 34259698Sdim * The primary goals of this implementation are portability and ease of use. 35259698Sdim * It is meant to be fast, but not as fast as possible. Some known 36259698Sdim * optimizations are not included to reduce source code size and avoid 37259698Sdim * compile-time configuration. 38259698Sdim */ 39259698Sdim 40259698Sdim#include "llvm/ADT/ArrayRef.h" 41259698Sdim#include "llvm/Support/Format.h" 42259698Sdim#include "llvm/Support/MD5.h" 43259698Sdim#include "llvm/Support/raw_ostream.h" 44259698Sdim#include <cstring> 45259698Sdim 46259698Sdim// The basic MD5 functions. 47259698Sdim 48259698Sdim// F and G are optimized compared to their RFC 1321 definitions for 49259698Sdim// architectures that lack an AND-NOT instruction, just like in Colin Plumb's 50259698Sdim// implementation. 51259698Sdim#define F(x, y, z) ((z) ^ ((x) & ((y) ^ (z)))) 52259698Sdim#define G(x, y, z) ((y) ^ ((z) & ((x) ^ (y)))) 53259698Sdim#define H(x, y, z) ((x) ^ (y) ^ (z)) 54259698Sdim#define I(x, y, z) ((y) ^ ((x) | ~(z))) 55259698Sdim 56259698Sdim// The MD5 transformation for all four rounds. 57259698Sdim#define STEP(f, a, b, c, d, x, t, s) \ 58259698Sdim (a) += f((b), (c), (d)) + (x) + (t); \ 59259698Sdim (a) = (((a) << (s)) | (((a) & 0xffffffff) >> (32 - (s)))); \ 60259698Sdim (a) += (b); 61259698Sdim 62259698Sdim// SET reads 4 input bytes in little-endian byte order and stores them 63259698Sdim// in a properly aligned word in host byte order. 64259698Sdim#define SET(n) \ 65259698Sdim (block[(n)] = \ 66259698Sdim (MD5_u32plus) ptr[(n) * 4] | ((MD5_u32plus) ptr[(n) * 4 + 1] << 8) | \ 67259698Sdim ((MD5_u32plus) ptr[(n) * 4 + 2] << 16) | \ 68259698Sdim ((MD5_u32plus) ptr[(n) * 4 + 3] << 24)) 69259698Sdim#define GET(n) (block[(n)]) 70259698Sdim 71259698Sdimnamespace llvm { 72259698Sdim 73259698Sdim/// \brief This processes one or more 64-byte data blocks, but does NOT update 74259698Sdim///the bit counters. There are no alignment requirements. 75259698Sdimconst uint8_t *MD5::body(ArrayRef<uint8_t> Data) { 76259698Sdim const uint8_t *ptr; 77259698Sdim MD5_u32plus a, b, c, d; 78259698Sdim MD5_u32plus saved_a, saved_b, saved_c, saved_d; 79259698Sdim unsigned long Size = Data.size(); 80259698Sdim 81259698Sdim ptr = Data.data(); 82259698Sdim 83259698Sdim a = this->a; 84259698Sdim b = this->b; 85259698Sdim c = this->c; 86259698Sdim d = this->d; 87259698Sdim 88259698Sdim do { 89259698Sdim saved_a = a; 90259698Sdim saved_b = b; 91259698Sdim saved_c = c; 92259698Sdim saved_d = d; 93259698Sdim 94259698Sdim // Round 1 95259698Sdim STEP(F, a, b, c, d, SET(0), 0xd76aa478, 7) 96259698Sdim STEP(F, d, a, b, c, SET(1), 0xe8c7b756, 12) 97259698Sdim STEP(F, c, d, a, b, SET(2), 0x242070db, 17) 98259698Sdim STEP(F, b, c, d, a, SET(3), 0xc1bdceee, 22) 99259698Sdim STEP(F, a, b, c, d, SET(4), 0xf57c0faf, 7) 100259698Sdim STEP(F, d, a, b, c, SET(5), 0x4787c62a, 12) 101259698Sdim STEP(F, c, d, a, b, SET(6), 0xa8304613, 17) 102259698Sdim STEP(F, b, c, d, a, SET(7), 0xfd469501, 22) 103259698Sdim STEP(F, a, b, c, d, SET(8), 0x698098d8, 7) 104259698Sdim STEP(F, d, a, b, c, SET(9), 0x8b44f7af, 12) 105259698Sdim STEP(F, c, d, a, b, SET(10), 0xffff5bb1, 17) 106259698Sdim STEP(F, b, c, d, a, SET(11), 0x895cd7be, 22) 107259698Sdim STEP(F, a, b, c, d, SET(12), 0x6b901122, 7) 108259698Sdim STEP(F, d, a, b, c, SET(13), 0xfd987193, 12) 109259698Sdim STEP(F, c, d, a, b, SET(14), 0xa679438e, 17) 110259698Sdim STEP(F, b, c, d, a, SET(15), 0x49b40821, 22) 111259698Sdim 112259698Sdim // Round 2 113259698Sdim STEP(G, a, b, c, d, GET(1), 0xf61e2562, 5) 114259698Sdim STEP(G, d, a, b, c, GET(6), 0xc040b340, 9) 115259698Sdim STEP(G, c, d, a, b, GET(11), 0x265e5a51, 14) 116259698Sdim STEP(G, b, c, d, a, GET(0), 0xe9b6c7aa, 20) 117259698Sdim STEP(G, a, b, c, d, GET(5), 0xd62f105d, 5) 118259698Sdim STEP(G, d, a, b, c, GET(10), 0x02441453, 9) 119259698Sdim STEP(G, c, d, a, b, GET(15), 0xd8a1e681, 14) 120259698Sdim STEP(G, b, c, d, a, GET(4), 0xe7d3fbc8, 20) 121259698Sdim STEP(G, a, b, c, d, GET(9), 0x21e1cde6, 5) 122259698Sdim STEP(G, d, a, b, c, GET(14), 0xc33707d6, 9) 123259698Sdim STEP(G, c, d, a, b, GET(3), 0xf4d50d87, 14) 124259698Sdim STEP(G, b, c, d, a, GET(8), 0x455a14ed, 20) 125259698Sdim STEP(G, a, b, c, d, GET(13), 0xa9e3e905, 5) 126259698Sdim STEP(G, d, a, b, c, GET(2), 0xfcefa3f8, 9) 127259698Sdim STEP(G, c, d, a, b, GET(7), 0x676f02d9, 14) 128259698Sdim STEP(G, b, c, d, a, GET(12), 0x8d2a4c8a, 20) 129259698Sdim 130259698Sdim // Round 3 131259698Sdim STEP(H, a, b, c, d, GET(5), 0xfffa3942, 4) 132259698Sdim STEP(H, d, a, b, c, GET(8), 0x8771f681, 11) 133259698Sdim STEP(H, c, d, a, b, GET(11), 0x6d9d6122, 16) 134259698Sdim STEP(H, b, c, d, a, GET(14), 0xfde5380c, 23) 135259698Sdim STEP(H, a, b, c, d, GET(1), 0xa4beea44, 4) 136259698Sdim STEP(H, d, a, b, c, GET(4), 0x4bdecfa9, 11) 137259698Sdim STEP(H, c, d, a, b, GET(7), 0xf6bb4b60, 16) 138259698Sdim STEP(H, b, c, d, a, GET(10), 0xbebfbc70, 23) 139259698Sdim STEP(H, a, b, c, d, GET(13), 0x289b7ec6, 4) 140259698Sdim STEP(H, d, a, b, c, GET(0), 0xeaa127fa, 11) 141259698Sdim STEP(H, c, d, a, b, GET(3), 0xd4ef3085, 16) 142259698Sdim STEP(H, b, c, d, a, GET(6), 0x04881d05, 23) 143259698Sdim STEP(H, a, b, c, d, GET(9), 0xd9d4d039, 4) 144259698Sdim STEP(H, d, a, b, c, GET(12), 0xe6db99e5, 11) 145259698Sdim STEP(H, c, d, a, b, GET(15), 0x1fa27cf8, 16) 146259698Sdim STEP(H, b, c, d, a, GET(2), 0xc4ac5665, 23) 147259698Sdim 148259698Sdim // Round 4 149259698Sdim STEP(I, a, b, c, d, GET(0), 0xf4292244, 6) 150259698Sdim STEP(I, d, a, b, c, GET(7), 0x432aff97, 10) 151259698Sdim STEP(I, c, d, a, b, GET(14), 0xab9423a7, 15) 152259698Sdim STEP(I, b, c, d, a, GET(5), 0xfc93a039, 21) 153259698Sdim STEP(I, a, b, c, d, GET(12), 0x655b59c3, 6) 154259698Sdim STEP(I, d, a, b, c, GET(3), 0x8f0ccc92, 10) 155259698Sdim STEP(I, c, d, a, b, GET(10), 0xffeff47d, 15) 156259698Sdim STEP(I, b, c, d, a, GET(1), 0x85845dd1, 21) 157259698Sdim STEP(I, a, b, c, d, GET(8), 0x6fa87e4f, 6) 158259698Sdim STEP(I, d, a, b, c, GET(15), 0xfe2ce6e0, 10) 159259698Sdim STEP(I, c, d, a, b, GET(6), 0xa3014314, 15) 160259698Sdim STEP(I, b, c, d, a, GET(13), 0x4e0811a1, 21) 161259698Sdim STEP(I, a, b, c, d, GET(4), 0xf7537e82, 6) 162259698Sdim STEP(I, d, a, b, c, GET(11), 0xbd3af235, 10) 163259698Sdim STEP(I, c, d, a, b, GET(2), 0x2ad7d2bb, 15) 164259698Sdim STEP(I, b, c, d, a, GET(9), 0xeb86d391, 21) 165259698Sdim 166259698Sdim a += saved_a; 167259698Sdim b += saved_b; 168259698Sdim c += saved_c; 169259698Sdim d += saved_d; 170259698Sdim 171259698Sdim ptr += 64; 172259698Sdim } while (Size -= 64); 173259698Sdim 174259698Sdim this->a = a; 175259698Sdim this->b = b; 176259698Sdim this->c = c; 177259698Sdim this->d = d; 178259698Sdim 179259698Sdim return ptr; 180259698Sdim} 181259698Sdim 182259698SdimMD5::MD5() 183259698Sdim : a(0x67452301), b(0xefcdab89), c(0x98badcfe), d(0x10325476), hi(0), lo(0) { 184259698Sdim} 185259698Sdim 186259698Sdim/// Incrementally add the bytes in \p Data to the hash. 187259698Sdimvoid MD5::update(ArrayRef<uint8_t> Data) { 188259698Sdim MD5_u32plus saved_lo; 189259698Sdim unsigned long used, free; 190259698Sdim const uint8_t *Ptr = Data.data(); 191259698Sdim unsigned long Size = Data.size(); 192259698Sdim 193259698Sdim saved_lo = lo; 194259698Sdim if ((lo = (saved_lo + Size) & 0x1fffffff) < saved_lo) 195259698Sdim hi++; 196259698Sdim hi += Size >> 29; 197259698Sdim 198259698Sdim used = saved_lo & 0x3f; 199259698Sdim 200259698Sdim if (used) { 201259698Sdim free = 64 - used; 202259698Sdim 203259698Sdim if (Size < free) { 204259698Sdim memcpy(&buffer[used], Ptr, Size); 205259698Sdim return; 206259698Sdim } 207259698Sdim 208259698Sdim memcpy(&buffer[used], Ptr, free); 209259698Sdim Ptr = Ptr + free; 210259698Sdim Size -= free; 211259698Sdim body(ArrayRef<uint8_t>(buffer, 64)); 212259698Sdim } 213259698Sdim 214259698Sdim if (Size >= 64) { 215259698Sdim Ptr = body(ArrayRef<uint8_t>(Ptr, Size & ~(unsigned long) 0x3f)); 216259698Sdim Size &= 0x3f; 217259698Sdim } 218259698Sdim 219259698Sdim memcpy(buffer, Ptr, Size); 220259698Sdim} 221259698Sdim 222259698Sdim/// Add the bytes in the StringRef \p Str to the hash. 223259698Sdim// Note that this isn't a string and so this won't include any trailing NULL 224259698Sdim// bytes. 225259698Sdimvoid MD5::update(StringRef Str) { 226259698Sdim ArrayRef<uint8_t> SVal((const uint8_t *)Str.data(), Str.size()); 227259698Sdim update(SVal); 228259698Sdim} 229259698Sdim 230259698Sdim/// \brief Finish the hash and place the resulting hash into \p result. 231259698Sdim/// \param result is assumed to be a minimum of 16-bytes in size. 232259698Sdimvoid MD5::final(MD5Result &result) { 233259698Sdim unsigned long used, free; 234259698Sdim 235259698Sdim used = lo & 0x3f; 236259698Sdim 237259698Sdim buffer[used++] = 0x80; 238259698Sdim 239259698Sdim free = 64 - used; 240259698Sdim 241259698Sdim if (free < 8) { 242259698Sdim memset(&buffer[used], 0, free); 243259698Sdim body(ArrayRef<uint8_t>(buffer, 64)); 244259698Sdim used = 0; 245259698Sdim free = 64; 246259698Sdim } 247259698Sdim 248259698Sdim memset(&buffer[used], 0, free - 8); 249259698Sdim 250259698Sdim lo <<= 3; 251259698Sdim buffer[56] = lo; 252259698Sdim buffer[57] = lo >> 8; 253259698Sdim buffer[58] = lo >> 16; 254259698Sdim buffer[59] = lo >> 24; 255259698Sdim buffer[60] = hi; 256259698Sdim buffer[61] = hi >> 8; 257259698Sdim buffer[62] = hi >> 16; 258259698Sdim buffer[63] = hi >> 24; 259259698Sdim 260259698Sdim body(ArrayRef<uint8_t>(buffer, 64)); 261259698Sdim 262259698Sdim result[0] = a; 263259698Sdim result[1] = a >> 8; 264259698Sdim result[2] = a >> 16; 265259698Sdim result[3] = a >> 24; 266259698Sdim result[4] = b; 267259698Sdim result[5] = b >> 8; 268259698Sdim result[6] = b >> 16; 269259698Sdim result[7] = b >> 24; 270259698Sdim result[8] = c; 271259698Sdim result[9] = c >> 8; 272259698Sdim result[10] = c >> 16; 273259698Sdim result[11] = c >> 24; 274259698Sdim result[12] = d; 275259698Sdim result[13] = d >> 8; 276259698Sdim result[14] = d >> 16; 277259698Sdim result[15] = d >> 24; 278259698Sdim} 279259698Sdim 280259698Sdimvoid MD5::stringifyResult(MD5Result &result, SmallString<32> &Str) { 281259698Sdim raw_svector_ostream Res(Str); 282259698Sdim for (int i = 0; i < 16; ++i) 283259698Sdim Res << format("%.2x", result[i]); 284259698Sdim} 285259698Sdim 286259698Sdim} 287