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 40321369Sdim#include "llvm/Support/MD5.h" 41259698Sdim#include "llvm/ADT/ArrayRef.h" 42321369Sdim#include "llvm/ADT/StringRef.h" 43321369Sdim#include "llvm/Support/Endian.h" 44259698Sdim#include "llvm/Support/Format.h" 45259698Sdim#include "llvm/Support/raw_ostream.h" 46321369Sdim#include <array> 47321369Sdim#include <cstdint> 48259698Sdim#include <cstring> 49259698Sdim 50259698Sdim// The basic MD5 functions. 51259698Sdim 52259698Sdim// F and G are optimized compared to their RFC 1321 definitions for 53259698Sdim// architectures that lack an AND-NOT instruction, just like in Colin Plumb's 54259698Sdim// implementation. 55259698Sdim#define F(x, y, z) ((z) ^ ((x) & ((y) ^ (z)))) 56259698Sdim#define G(x, y, z) ((y) ^ ((z) & ((x) ^ (y)))) 57259698Sdim#define H(x, y, z) ((x) ^ (y) ^ (z)) 58259698Sdim#define I(x, y, z) ((y) ^ ((x) | ~(z))) 59259698Sdim 60259698Sdim// The MD5 transformation for all four rounds. 61259698Sdim#define STEP(f, a, b, c, d, x, t, s) \ 62259698Sdim (a) += f((b), (c), (d)) + (x) + (t); \ 63259698Sdim (a) = (((a) << (s)) | (((a) & 0xffffffff) >> (32 - (s)))); \ 64259698Sdim (a) += (b); 65259698Sdim 66259698Sdim// SET reads 4 input bytes in little-endian byte order and stores them 67259698Sdim// in a properly aligned word in host byte order. 68259698Sdim#define SET(n) \ 69259698Sdim (block[(n)] = \ 70259698Sdim (MD5_u32plus) ptr[(n) * 4] | ((MD5_u32plus) ptr[(n) * 4 + 1] << 8) | \ 71259698Sdim ((MD5_u32plus) ptr[(n) * 4 + 2] << 16) | \ 72259698Sdim ((MD5_u32plus) ptr[(n) * 4 + 3] << 24)) 73259698Sdim#define GET(n) (block[(n)]) 74259698Sdim 75321369Sdimusing namespace llvm; 76259698Sdim 77341825Sdim/// This processes one or more 64-byte data blocks, but does NOT update 78259698Sdim///the bit counters. There are no alignment requirements. 79259698Sdimconst uint8_t *MD5::body(ArrayRef<uint8_t> Data) { 80259698Sdim const uint8_t *ptr; 81259698Sdim MD5_u32plus a, b, c, d; 82259698Sdim MD5_u32plus saved_a, saved_b, saved_c, saved_d; 83259698Sdim unsigned long Size = Data.size(); 84259698Sdim 85259698Sdim ptr = Data.data(); 86259698Sdim 87259698Sdim a = this->a; 88259698Sdim b = this->b; 89259698Sdim c = this->c; 90259698Sdim d = this->d; 91259698Sdim 92259698Sdim do { 93259698Sdim saved_a = a; 94259698Sdim saved_b = b; 95259698Sdim saved_c = c; 96259698Sdim saved_d = d; 97259698Sdim 98259698Sdim // Round 1 99259698Sdim STEP(F, a, b, c, d, SET(0), 0xd76aa478, 7) 100259698Sdim STEP(F, d, a, b, c, SET(1), 0xe8c7b756, 12) 101259698Sdim STEP(F, c, d, a, b, SET(2), 0x242070db, 17) 102259698Sdim STEP(F, b, c, d, a, SET(3), 0xc1bdceee, 22) 103259698Sdim STEP(F, a, b, c, d, SET(4), 0xf57c0faf, 7) 104259698Sdim STEP(F, d, a, b, c, SET(5), 0x4787c62a, 12) 105259698Sdim STEP(F, c, d, a, b, SET(6), 0xa8304613, 17) 106259698Sdim STEP(F, b, c, d, a, SET(7), 0xfd469501, 22) 107259698Sdim STEP(F, a, b, c, d, SET(8), 0x698098d8, 7) 108259698Sdim STEP(F, d, a, b, c, SET(9), 0x8b44f7af, 12) 109259698Sdim STEP(F, c, d, a, b, SET(10), 0xffff5bb1, 17) 110259698Sdim STEP(F, b, c, d, a, SET(11), 0x895cd7be, 22) 111259698Sdim STEP(F, a, b, c, d, SET(12), 0x6b901122, 7) 112259698Sdim STEP(F, d, a, b, c, SET(13), 0xfd987193, 12) 113259698Sdim STEP(F, c, d, a, b, SET(14), 0xa679438e, 17) 114259698Sdim STEP(F, b, c, d, a, SET(15), 0x49b40821, 22) 115259698Sdim 116259698Sdim // Round 2 117259698Sdim STEP(G, a, b, c, d, GET(1), 0xf61e2562, 5) 118259698Sdim STEP(G, d, a, b, c, GET(6), 0xc040b340, 9) 119259698Sdim STEP(G, c, d, a, b, GET(11), 0x265e5a51, 14) 120259698Sdim STEP(G, b, c, d, a, GET(0), 0xe9b6c7aa, 20) 121259698Sdim STEP(G, a, b, c, d, GET(5), 0xd62f105d, 5) 122259698Sdim STEP(G, d, a, b, c, GET(10), 0x02441453, 9) 123259698Sdim STEP(G, c, d, a, b, GET(15), 0xd8a1e681, 14) 124259698Sdim STEP(G, b, c, d, a, GET(4), 0xe7d3fbc8, 20) 125259698Sdim STEP(G, a, b, c, d, GET(9), 0x21e1cde6, 5) 126259698Sdim STEP(G, d, a, b, c, GET(14), 0xc33707d6, 9) 127259698Sdim STEP(G, c, d, a, b, GET(3), 0xf4d50d87, 14) 128259698Sdim STEP(G, b, c, d, a, GET(8), 0x455a14ed, 20) 129259698Sdim STEP(G, a, b, c, d, GET(13), 0xa9e3e905, 5) 130259698Sdim STEP(G, d, a, b, c, GET(2), 0xfcefa3f8, 9) 131259698Sdim STEP(G, c, d, a, b, GET(7), 0x676f02d9, 14) 132259698Sdim STEP(G, b, c, d, a, GET(12), 0x8d2a4c8a, 20) 133259698Sdim 134259698Sdim // Round 3 135259698Sdim STEP(H, a, b, c, d, GET(5), 0xfffa3942, 4) 136259698Sdim STEP(H, d, a, b, c, GET(8), 0x8771f681, 11) 137259698Sdim STEP(H, c, d, a, b, GET(11), 0x6d9d6122, 16) 138259698Sdim STEP(H, b, c, d, a, GET(14), 0xfde5380c, 23) 139259698Sdim STEP(H, a, b, c, d, GET(1), 0xa4beea44, 4) 140259698Sdim STEP(H, d, a, b, c, GET(4), 0x4bdecfa9, 11) 141259698Sdim STEP(H, c, d, a, b, GET(7), 0xf6bb4b60, 16) 142259698Sdim STEP(H, b, c, d, a, GET(10), 0xbebfbc70, 23) 143259698Sdim STEP(H, a, b, c, d, GET(13), 0x289b7ec6, 4) 144259698Sdim STEP(H, d, a, b, c, GET(0), 0xeaa127fa, 11) 145259698Sdim STEP(H, c, d, a, b, GET(3), 0xd4ef3085, 16) 146259698Sdim STEP(H, b, c, d, a, GET(6), 0x04881d05, 23) 147259698Sdim STEP(H, a, b, c, d, GET(9), 0xd9d4d039, 4) 148259698Sdim STEP(H, d, a, b, c, GET(12), 0xe6db99e5, 11) 149259698Sdim STEP(H, c, d, a, b, GET(15), 0x1fa27cf8, 16) 150259698Sdim STEP(H, b, c, d, a, GET(2), 0xc4ac5665, 23) 151259698Sdim 152259698Sdim // Round 4 153259698Sdim STEP(I, a, b, c, d, GET(0), 0xf4292244, 6) 154259698Sdim STEP(I, d, a, b, c, GET(7), 0x432aff97, 10) 155259698Sdim STEP(I, c, d, a, b, GET(14), 0xab9423a7, 15) 156259698Sdim STEP(I, b, c, d, a, GET(5), 0xfc93a039, 21) 157259698Sdim STEP(I, a, b, c, d, GET(12), 0x655b59c3, 6) 158259698Sdim STEP(I, d, a, b, c, GET(3), 0x8f0ccc92, 10) 159259698Sdim STEP(I, c, d, a, b, GET(10), 0xffeff47d, 15) 160259698Sdim STEP(I, b, c, d, a, GET(1), 0x85845dd1, 21) 161259698Sdim STEP(I, a, b, c, d, GET(8), 0x6fa87e4f, 6) 162259698Sdim STEP(I, d, a, b, c, GET(15), 0xfe2ce6e0, 10) 163259698Sdim STEP(I, c, d, a, b, GET(6), 0xa3014314, 15) 164259698Sdim STEP(I, b, c, d, a, GET(13), 0x4e0811a1, 21) 165259698Sdim STEP(I, a, b, c, d, GET(4), 0xf7537e82, 6) 166259698Sdim STEP(I, d, a, b, c, GET(11), 0xbd3af235, 10) 167259698Sdim STEP(I, c, d, a, b, GET(2), 0x2ad7d2bb, 15) 168259698Sdim STEP(I, b, c, d, a, GET(9), 0xeb86d391, 21) 169259698Sdim 170259698Sdim a += saved_a; 171259698Sdim b += saved_b; 172259698Sdim c += saved_c; 173259698Sdim d += saved_d; 174259698Sdim 175259698Sdim ptr += 64; 176259698Sdim } while (Size -= 64); 177259698Sdim 178259698Sdim this->a = a; 179259698Sdim this->b = b; 180259698Sdim this->c = c; 181259698Sdim this->d = d; 182259698Sdim 183259698Sdim return ptr; 184259698Sdim} 185259698Sdim 186321369SdimMD5::MD5() = default; 187259698Sdim 188259698Sdim/// Incrementally add the bytes in \p Data to the hash. 189259698Sdimvoid MD5::update(ArrayRef<uint8_t> Data) { 190259698Sdim MD5_u32plus saved_lo; 191259698Sdim unsigned long used, free; 192259698Sdim const uint8_t *Ptr = Data.data(); 193259698Sdim unsigned long Size = Data.size(); 194259698Sdim 195259698Sdim saved_lo = lo; 196259698Sdim if ((lo = (saved_lo + Size) & 0x1fffffff) < saved_lo) 197259698Sdim hi++; 198259698Sdim hi += Size >> 29; 199259698Sdim 200259698Sdim used = saved_lo & 0x3f; 201259698Sdim 202259698Sdim if (used) { 203259698Sdim free = 64 - used; 204259698Sdim 205259698Sdim if (Size < free) { 206259698Sdim memcpy(&buffer[used], Ptr, Size); 207259698Sdim return; 208259698Sdim } 209259698Sdim 210259698Sdim memcpy(&buffer[used], Ptr, free); 211259698Sdim Ptr = Ptr + free; 212259698Sdim Size -= free; 213280031Sdim body(makeArrayRef(buffer, 64)); 214259698Sdim } 215259698Sdim 216259698Sdim if (Size >= 64) { 217280031Sdim Ptr = body(makeArrayRef(Ptr, Size & ~(unsigned long) 0x3f)); 218259698Sdim Size &= 0x3f; 219259698Sdim } 220259698Sdim 221259698Sdim memcpy(buffer, Ptr, Size); 222259698Sdim} 223259698Sdim 224259698Sdim/// Add the bytes in the StringRef \p Str to the hash. 225259698Sdim// Note that this isn't a string and so this won't include any trailing NULL 226259698Sdim// bytes. 227259698Sdimvoid MD5::update(StringRef Str) { 228259698Sdim ArrayRef<uint8_t> SVal((const uint8_t *)Str.data(), Str.size()); 229259698Sdim update(SVal); 230259698Sdim} 231259698Sdim 232341825Sdim/// Finish the hash and place the resulting hash into \p result. 233327952Sdim/// \param Result is assumed to be a minimum of 16-bytes in size. 234280031Sdimvoid MD5::final(MD5Result &Result) { 235259698Sdim unsigned long used, free; 236259698Sdim 237259698Sdim used = lo & 0x3f; 238259698Sdim 239259698Sdim buffer[used++] = 0x80; 240259698Sdim 241259698Sdim free = 64 - used; 242259698Sdim 243259698Sdim if (free < 8) { 244259698Sdim memset(&buffer[used], 0, free); 245280031Sdim body(makeArrayRef(buffer, 64)); 246259698Sdim used = 0; 247259698Sdim free = 64; 248259698Sdim } 249259698Sdim 250259698Sdim memset(&buffer[used], 0, free - 8); 251259698Sdim 252259698Sdim lo <<= 3; 253314564Sdim support::endian::write32le(&buffer[56], lo); 254314564Sdim support::endian::write32le(&buffer[60], hi); 255259698Sdim 256280031Sdim body(makeArrayRef(buffer, 64)); 257259698Sdim 258314564Sdim support::endian::write32le(&Result[0], a); 259314564Sdim support::endian::write32le(&Result[4], b); 260314564Sdim support::endian::write32le(&Result[8], c); 261314564Sdim support::endian::write32le(&Result[12], d); 262259698Sdim} 263259698Sdim 264321369SdimSmallString<32> MD5::MD5Result::digest() const { 265321369Sdim SmallString<32> Str; 266259698Sdim raw_svector_ostream Res(Str); 267259698Sdim for (int i = 0; i < 16; ++i) 268321369Sdim Res << format("%.2x", Bytes[i]); 269321369Sdim return Str; 270259698Sdim} 271259698Sdim 272321369Sdimvoid MD5::stringifyResult(MD5Result &Result, SmallString<32> &Str) { 273321369Sdim Str = Result.digest(); 274321369Sdim} 275321369Sdim 276314564Sdimstd::array<uint8_t, 16> MD5::hash(ArrayRef<uint8_t> Data) { 277314564Sdim MD5 Hash; 278314564Sdim Hash.update(Data); 279314564Sdim MD5::MD5Result Res; 280314564Sdim Hash.final(Res); 281314564Sdim 282321369Sdim return Res; 283259698Sdim} 284