1 /* 2 * Chocobo1/Hash 3 * 4 * Copyright 2017-2020 by Mike Tzou (Chocobo1) 5 * https://github.com/Chocobo1/Hash 6 * 7 * Licensed under GNU General Public License 3 or later. 8 * 9 * @license GPL3 <https://www.gnu.org/licenses/gpl-3.0-standalone.html> 10 */ 11 12 #ifndef CHOCOBO1_MD4_H 13 #define CHOCOBO1_MD4_H 14 15 #include <array> 16 #include <cassert> 17 #include <climits> 18 #include <cmath> 19 #include <cstdint> 20 #include <initializer_list> 21 #include <string> 22 #include <type_traits> 23 #include <vector> 24 25 #if (__cplusplus > 201703L) 26 #include <version> 27 #endif 28 29 #ifndef USE_STD_SPAN_CHOCOBO1_HASH 30 #if (__cpp_lib_span >= 202002L) 31 #define USE_STD_SPAN_CHOCOBO1_HASH 1 32 #else 33 #define USE_STD_SPAN_CHOCOBO1_HASH 0 34 #endif 35 #endif 36 37 #if (USE_STD_SPAN_CHOCOBO1_HASH == 1) 38 #include <span> 39 #else 40 #include "gsl/span" 41 #endif 42 43 44 namespace Chocobo1 45 { 46 // Use these!! 47 // MD4(); 48 } 49 50 51 namespace Chocobo1 52 { 53 // users should ignore things in this namespace 54 55 namespace Hash 56 { 57 #ifndef CONSTEXPR_CPP17_CHOCOBO1_HASH 58 #if __cplusplus >= 201703L 59 #define CONSTEXPR_CPP17_CHOCOBO1_HASH constexpr 60 #else 61 #define CONSTEXPR_CPP17_CHOCOBO1_HASH 62 #endif 63 #endif 64 65 #if (USE_STD_SPAN_CHOCOBO1_HASH == 1) 66 using IndexType = std::size_t; 67 #else 68 using IndexType = gsl::index; 69 #endif 70 71 #ifndef CHOCOBO1_HASH_BUFFER_IMPL 72 #define CHOCOBO1_HASH_BUFFER_IMPL 73 template <typename T, IndexType N> 74 class Buffer 75 { 76 public: 77 using value_type = T; 78 using index_type = IndexType; 79 using size_type = std::size_t; 80 81 constexpr Buffer() = default; 82 constexpr Buffer(const Buffer &) = default; 83 Buffer(const std::initializer_list<T> initList)84 CONSTEXPR_CPP17_CHOCOBO1_HASH Buffer(const std::initializer_list<T> initList) 85 { 86 #if !defined(NDEBUG) 87 // check if out-of-bounds 88 static_cast<void>(m_array.at(m_dataEndIdx + initList.size() - 1)); 89 #endif 90 91 for (const auto &i : initList) 92 { 93 m_array[m_dataEndIdx] = i; 94 ++m_dataEndIdx; 95 } 96 } 97 98 template <typename InputIt> Buffer(const InputIt first,const InputIt last)99 constexpr Buffer(const InputIt first, const InputIt last) 100 { 101 for (InputIt iter = first; iter != last; ++iter) 102 { 103 this->fill(*iter); 104 } 105 } 106 107 constexpr T& operator[](const index_type pos) 108 { 109 return m_array[pos]; 110 } 111 112 constexpr T operator[](const index_type pos) const 113 { 114 return m_array[pos]; 115 } 116 117 CONSTEXPR_CPP17_CHOCOBO1_HASH void fill(const T &value, const index_type count = 1) 118 { 119 #if !defined(NDEBUG) 120 // check if out-of-bounds 121 static_cast<void>(m_array.at(m_dataEndIdx + count - 1)); 122 #endif 123 124 for (index_type i = 0; i < count; ++i) 125 { 126 m_array[m_dataEndIdx] = value; 127 ++m_dataEndIdx; 128 } 129 } 130 131 template <typename InputIt> push_back(const InputIt first,const InputIt last)132 constexpr void push_back(const InputIt first, const InputIt last) 133 { 134 for (InputIt iter = first; iter != last; ++iter) 135 { 136 this->fill(*iter); 137 } 138 } 139 clear()140 constexpr void clear() 141 { 142 m_array = {}; 143 m_dataEndIdx = 0; 144 } 145 empty()146 constexpr bool empty() const 147 { 148 return (m_dataEndIdx == 0); 149 } 150 size()151 constexpr size_type size() const 152 { 153 return m_dataEndIdx; 154 } 155 data()156 constexpr const T* data() const 157 { 158 return m_array.data(); 159 } 160 161 private: 162 std::array<T, N> m_array {}; 163 index_type m_dataEndIdx = 0; 164 }; 165 #endif 166 167 168 namespace MD4_NS 169 { 170 class MD4 171 { 172 // https://tools.ietf.org/html/rfc1320 173 174 public: 175 using Byte = uint8_t; 176 using ResultArrayType = std::array<Byte, 16>; 177 178 #if (USE_STD_SPAN_CHOCOBO1_HASH == 1) 179 template <typename T, std::size_t Extent = std::dynamic_extent> 180 using Span = std::span<T, Extent>; 181 #else 182 template <typename T, std::size_t Extent = gsl::dynamic_extent> 183 using Span = gsl::span<T, Extent>; 184 #endif 185 186 187 constexpr MD4(); 188 189 constexpr void reset(); 190 CONSTEXPR_CPP17_CHOCOBO1_HASH MD4& finalize(); // after this, only `toArray()`, `toString()`, `toVector()`, `reset()` are available 191 192 std::string toString() const; 193 std::vector<Byte> toVector() const; 194 CONSTEXPR_CPP17_CHOCOBO1_HASH ResultArrayType toArray() const; 195 196 CONSTEXPR_CPP17_CHOCOBO1_HASH MD4& addData(const Span<const Byte> inData); 197 CONSTEXPR_CPP17_CHOCOBO1_HASH MD4& addData(const void *ptr, const std::size_t length); 198 template <std::size_t N> 199 CONSTEXPR_CPP17_CHOCOBO1_HASH MD4& addData(const Byte (&array)[N]); 200 template <typename T, std::size_t N> 201 MD4& addData(const T (&array)[N]); 202 template <typename T> 203 MD4& addData(const Span<T> inSpan); 204 205 private: 206 CONSTEXPR_CPP17_CHOCOBO1_HASH void addDataImpl(const Span<const Byte> data); 207 208 static constexpr int BLOCK_SIZE = 64; 209 210 Buffer<Byte, (BLOCK_SIZE * 2)> m_buffer; // x2 for paddings 211 uint64_t m_sizeCounter = 0; 212 213 uint32_t m_state[4] = {}; 214 }; 215 216 217 // helpers 218 template <typename T> 219 class Loader 220 { 221 // this class workaround loading data from unaligned memory boundaries 222 // also eliminate endianness issues 223 public: Loader(const uint8_t * ptr)224 explicit constexpr Loader(const uint8_t *ptr) 225 : m_ptr(ptr) 226 { 227 } 228 229 constexpr T operator[](const IndexType idx) const 230 { 231 static_assert(std::is_same<T, uint32_t>::value, ""); 232 // handle specific endianness here 233 const uint8_t *ptr = m_ptr + (sizeof(T) * idx); 234 return ( (static_cast<T>(*(ptr + 0)) << 0) 235 | (static_cast<T>(*(ptr + 1)) << 8) 236 | (static_cast<T>(*(ptr + 2)) << 16) 237 | (static_cast<T>(*(ptr + 3)) << 24)); 238 } 239 240 private: 241 const uint8_t *m_ptr; 242 }; 243 244 template <typename R, typename T> ror(const T x,const unsigned int s)245 constexpr R ror(const T x, const unsigned int s) 246 { 247 static_assert(std::is_unsigned<R>::value, ""); 248 static_assert(std::is_unsigned<T>::value, ""); 249 return static_cast<R>(x >> s); 250 } 251 252 template <typename T> rotl(const T x,const unsigned int s)253 constexpr T rotl(const T x, const unsigned int s) 254 { 255 static_assert(std::is_unsigned<T>::value, ""); 256 if (s == 0) 257 return x; 258 return ((x << s) | (x >> ((sizeof(T) * 8) - s))); 259 } 260 261 262 // MD4()263 constexpr MD4::MD4() 264 { 265 static_assert((CHAR_BIT == 8), "Sorry, we don't support exotic CPUs"); 266 reset(); 267 } 268 reset()269 constexpr void MD4::reset() 270 { 271 m_buffer.clear(); 272 m_sizeCounter = 0; 273 274 m_state[0] = 0x67452301; 275 m_state[1] = 0xefcdab89; 276 m_state[2] = 0x98badcfe; 277 m_state[3] = 0x10325476; 278 } 279 finalize()280 CONSTEXPR_CPP17_CHOCOBO1_HASH MD4& MD4::finalize() 281 { 282 m_sizeCounter += m_buffer.size(); 283 284 // append 1 bit 285 m_buffer.fill(1 << 7); 286 287 // append paddings 288 const size_t len = BLOCK_SIZE - ((m_buffer.size() + 8) % BLOCK_SIZE); 289 m_buffer.fill(0, (len + 8)); 290 291 // append size in bits 292 const uint64_t sizeCounterBits = m_sizeCounter * 8; 293 const uint32_t sizeCounterBitsL = ror<uint32_t>(sizeCounterBits, 0); 294 const uint32_t sizeCounterBitsH = ror<uint32_t>(sizeCounterBits, 32); 295 for (int i = 0; i < 4; ++i) 296 { 297 m_buffer[m_buffer.size() - 8 + i] = ror<Byte>(sizeCounterBitsL, (8 * i)); 298 m_buffer[m_buffer.size() - 4 + i] = ror<Byte>(sizeCounterBitsH, (8 * i)); 299 } 300 301 addDataImpl({m_buffer.data(), m_buffer.size()}); 302 m_buffer.clear(); 303 304 return (*this); 305 } 306 toString()307 std::string MD4::toString() const 308 { 309 const auto a = toArray(); 310 std::string ret; 311 ret.resize(2 * a.size()); 312 313 auto retPtr = &ret.front(); 314 for (const auto c : a) 315 { 316 const Byte upper = ror<Byte>(c, 4); 317 *(retPtr++) = static_cast<char>((upper < 10) ? (upper + '0') : (upper - 10 + 'a')); 318 319 const Byte lower = c & 0xf; 320 *(retPtr++) = static_cast<char>((lower < 10) ? (lower + '0') : (lower - 10 + 'a')); 321 } 322 323 return ret; 324 } 325 toVector()326 std::vector<MD4::Byte> MD4::toVector() const 327 { 328 const auto a = toArray(); 329 return {a.begin(), a.end()}; 330 } 331 toArray()332 CONSTEXPR_CPP17_CHOCOBO1_HASH MD4::ResultArrayType MD4::toArray() const 333 { 334 const Span<const uint32_t> state(m_state); 335 const int dataSize = sizeof(decltype(state)::value_type); 336 337 ResultArrayType ret {}; 338 auto retPtr = ret.data(); 339 for (const auto i : state) 340 { 341 for (int j = 0; j < dataSize; ++j) 342 *(retPtr++) = ror<Byte>(i, (j * 8)); 343 } 344 345 return ret; 346 } 347 addData(const Span<const Byte> inData)348 CONSTEXPR_CPP17_CHOCOBO1_HASH MD4& MD4::addData(const Span<const Byte> inData) 349 { 350 Span<const Byte> data = inData; 351 352 if (!m_buffer.empty()) 353 { 354 const size_t len = std::min<size_t>((BLOCK_SIZE - m_buffer.size()), data.size()); // try fill to BLOCK_SIZE bytes 355 m_buffer.push_back(data.begin(), (data.begin() + len)); 356 357 if (m_buffer.size() < BLOCK_SIZE) // still doesn't fill the buffer 358 return (*this); 359 360 addDataImpl({m_buffer.data(), m_buffer.size()}); 361 m_buffer.clear(); 362 363 data = data.subspan(len); 364 } 365 366 const size_t dataSize = data.size(); 367 if (dataSize < BLOCK_SIZE) 368 { 369 m_buffer = {data.begin(), data.end()}; 370 return (*this); 371 } 372 373 const size_t len = dataSize - (dataSize % BLOCK_SIZE); // align on BLOCK_SIZE bytes 374 addDataImpl(data.first(len)); 375 376 if (len < dataSize) // didn't consume all data 377 m_buffer = {(data.begin() + len), data.end()}; 378 379 return (*this); 380 } 381 addData(const void * ptr,const std::size_t length)382 CONSTEXPR_CPP17_CHOCOBO1_HASH MD4& MD4::addData(const void *ptr, const std::size_t length) 383 { 384 // Span::size_type = std::size_t 385 return addData({static_cast<const Byte*>(ptr), length}); 386 } 387 388 template <std::size_t N> addData(const Byte (& array)[N])389 CONSTEXPR_CPP17_CHOCOBO1_HASH MD4& MD4::addData(const Byte (&array)[N]) 390 { 391 return addData({array, N}); 392 } 393 394 template <typename T, std::size_t N> addData(const T (& array)[N])395 MD4& MD4::addData(const T (&array)[N]) 396 { 397 return addData({reinterpret_cast<const Byte*>(array), (sizeof(T) * N)}); 398 } 399 400 template <typename T> addData(const Span<T> inSpan)401 MD4& MD4::addData(const Span<T> inSpan) 402 { 403 return addData({reinterpret_cast<const Byte*>(inSpan.data()), inSpan.size_bytes()}); 404 } 405 addDataImpl(const Span<const Byte> data)406 CONSTEXPR_CPP17_CHOCOBO1_HASH void MD4::addDataImpl(const Span<const Byte> data) 407 { 408 assert((data.size() % BLOCK_SIZE) == 0); 409 410 m_sizeCounter += data.size(); 411 412 for (size_t i = 0, iend = static_cast<size_t>(data.size() / BLOCK_SIZE); i < iend; ++i) 413 { 414 const Loader<uint32_t> x(static_cast<const Byte *>(data.data() + (i * BLOCK_SIZE))); 415 416 uint32_t aa = m_state[0]; 417 uint32_t bb = m_state[1]; 418 uint32_t cc = m_state[2]; 419 uint32_t dd = m_state[3]; 420 421 const auto round1 = [x](uint32_t &a, uint32_t &b, uint32_t &c, uint32_t &d, const int k, const unsigned int s) -> void 422 { 423 const uint32_t f = ((b & (c ^ d)) ^ d); // alternative 424 a = rotl((a + f + x[k]), s); 425 }; 426 round1(aa, bb, cc, dd, 0, 3); 427 round1(dd, aa, bb, cc, 1, 7); 428 round1(cc, dd, aa, bb, 2, 11); 429 round1(bb, cc, dd, aa, 3, 19); 430 round1(aa, bb, cc, dd, 4, 3); 431 round1(dd, aa, bb, cc, 5, 7); 432 round1(cc, dd, aa, bb, 6, 11); 433 round1(bb, cc, dd, aa, 7, 19); 434 round1(aa, bb, cc, dd, 8, 3); 435 round1(dd, aa, bb, cc, 9, 7); 436 round1(cc, dd, aa, bb, 10, 11); 437 round1(bb, cc, dd, aa, 11, 19); 438 round1(aa, bb, cc, dd, 12, 3); 439 round1(dd, aa, bb, cc, 13, 7); 440 round1(cc, dd, aa, bb, 14, 11); 441 round1(bb, cc, dd, aa, 15, 19); 442 443 const auto round2 = [x](uint32_t &a, uint32_t &b, uint32_t &c, uint32_t &d, const int k, const unsigned int s) -> void 444 { 445 const uint32_t g = ((b & c) | ((b | c) & d)); // alternative 446 a = rotl((a + g + x[k] + 0x5A827999), s); 447 }; 448 round2(aa, bb, cc, dd, 0, 3); 449 round2(dd, aa, bb, cc, 4, 5); 450 round2(cc, dd, aa, bb, 8, 9); 451 round2(bb, cc, dd, aa, 12, 13); 452 round2(aa, bb, cc, dd, 1, 3); 453 round2(dd, aa, bb, cc, 5, 5); 454 round2(cc, dd, aa, bb, 9, 9); 455 round2(bb, cc, dd, aa, 13, 13); 456 round2(aa, bb, cc, dd, 2, 3); 457 round2(dd, aa, bb, cc, 6, 5); 458 round2(cc, dd, aa, bb, 10, 9); 459 round2(bb, cc, dd, aa, 14, 13); 460 round2(aa, bb, cc, dd, 3, 3); 461 round2(dd, aa, bb, cc, 7, 5); 462 round2(cc, dd, aa, bb, 11, 9); 463 round2(bb, cc, dd, aa, 15, 13); 464 465 const auto round3 = [x](uint32_t &a, uint32_t &b, uint32_t &c, uint32_t &d, const int k, const unsigned int s) -> void 466 { 467 const uint32_t h = (b ^ c ^ d); 468 a = rotl((a + h + x[k] + 0x6ED9EBA1), s); 469 }; 470 round3(aa, bb, cc, dd, 0, 3); 471 round3(dd, aa, bb, cc, 8, 9); 472 round3(cc, dd, aa, bb, 4, 11); 473 round3(bb, cc, dd, aa, 12, 15); 474 round3(aa, bb, cc, dd, 2, 3); 475 round3(dd, aa, bb, cc, 10, 9); 476 round3(cc, dd, aa, bb, 6, 11); 477 round3(bb, cc, dd, aa, 14, 15); 478 round3(aa, bb, cc, dd, 1, 3); 479 round3(dd, aa, bb, cc, 9, 9); 480 round3(cc, dd, aa, bb, 5, 11); 481 round3(bb, cc, dd, aa, 13, 15); 482 round3(aa, bb, cc, dd, 3, 3); 483 round3(dd, aa, bb, cc, 11, 9); 484 round3(cc, dd, aa, bb, 7, 11); 485 round3(bb, cc, dd, aa, 15, 15); 486 487 m_state[0] += aa; 488 m_state[1] += bb; 489 m_state[2] += cc; 490 m_state[3] += dd; 491 } 492 } 493 } 494 } 495 using MD4 = Hash::MD4_NS::MD4; 496 } 497 498 #endif // CHOCOBO1_MD4_H 499