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_HAS_160_H 13 #define CHOCOBO1_HAS_160_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 // HAS_160(); 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 HAS160_NS 169 { 170 class HAS_160 171 { 172 // https://www.tta.or.kr/eng/new/standardization/eng_ttastddesc.jsp?stdno=TTAS.KO-12.0011/R2 173 174 public: 175 using Byte = uint8_t; 176 using ResultArrayType = std::array<Byte, 20>; 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 HAS_160(); 188 189 constexpr void reset(); 190 HAS_160& 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 HAS_160& addData(const Span<const Byte> inData); 197 HAS_160& addData(const void *ptr, const std::size_t length); 198 template <std::size_t N> 199 HAS_160& addData(const Byte (&array)[N]); 200 template <typename T, std::size_t N> 201 HAS_160& addData(const T (&array)[N]); 202 template <typename T> 203 HAS_160& addData(const Span<T> inSpan); 204 205 private: 206 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_h[5] = {}; 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 // HAS_160()263 constexpr HAS_160::HAS_160() 264 { 265 static_assert((CHAR_BIT == 8), "Sorry, we don't support exotic CPUs"); 266 reset(); 267 } 268 reset()269 constexpr void HAS_160::reset() 270 { 271 m_buffer.clear(); 272 m_sizeCounter = 0; 273 274 m_h[0] = 0x67452301; 275 m_h[1] = 0xEFCDAB89; 276 m_h[2] = 0x98BADCFE; 277 m_h[3] = 0x10325476; 278 m_h[4] = 0xC3D2E1F0; 279 } 280 finalize()281 HAS_160& HAS_160::finalize() 282 { 283 m_sizeCounter += m_buffer.size(); 284 285 // append 1 bit 286 m_buffer.fill(1 << 7); 287 288 // append paddings 289 const size_t len = BLOCK_SIZE - ((m_buffer.size() + 8) % BLOCK_SIZE); 290 m_buffer.fill(0, (len + 8)); 291 292 // append size in bits 293 const uint64_t sizeCounterBits = m_sizeCounter * 8; 294 const uint32_t sizeCounterBitsL = ror<uint32_t>(sizeCounterBits, 0); 295 const uint32_t sizeCounterBitsH = ror<uint32_t>(sizeCounterBits, 32); 296 for (int i = 0; i < 4; ++i) 297 { 298 m_buffer[m_buffer.size() - 8 + i] = ror<Byte>(sizeCounterBitsL, (8 * i)); 299 m_buffer[m_buffer.size() - 4 + i] = ror<Byte>(sizeCounterBitsH, (8 * i)); 300 } 301 302 addDataImpl({m_buffer.data(), m_buffer.size()}); 303 m_buffer.clear(); 304 305 return (*this); 306 } 307 toString()308 std::string HAS_160::toString() const 309 { 310 const auto a = toArray(); 311 std::string ret; 312 ret.resize(2 * a.size()); 313 314 auto retPtr = &ret.front(); 315 for (const auto c : a) 316 { 317 const Byte upper = ror<Byte>(c, 4); 318 *(retPtr++) = static_cast<char>((upper < 10) ? (upper + '0') : (upper - 10 + 'a')); 319 320 const Byte lower = c & 0xf; 321 *(retPtr++) = static_cast<char>((lower < 10) ? (lower + '0') : (lower - 10 + 'a')); 322 } 323 324 return ret; 325 } 326 toVector()327 std::vector<HAS_160::Byte> HAS_160::toVector() const 328 { 329 const auto a = toArray(); 330 return {a.begin(), a.end()}; 331 } 332 toArray()333 CONSTEXPR_CPP17_CHOCOBO1_HASH HAS_160::ResultArrayType HAS_160::toArray() const 334 { 335 const Span<const uint32_t> state(m_h); 336 const int dataSize = sizeof(decltype(state)::value_type); 337 338 ResultArrayType ret {}; 339 auto retPtr = ret.data(); 340 for (const auto i : state) 341 { 342 for (int j = 0; j < dataSize; ++j) 343 *(retPtr++) = ror<Byte>(i, (j * 8)); 344 } 345 346 return ret; 347 } 348 addData(const Span<const Byte> inData)349 HAS_160& HAS_160::addData(const Span<const Byte> inData) 350 { 351 Span<const Byte> data = inData; 352 353 if (!m_buffer.empty()) 354 { 355 const size_t len = std::min<size_t>((BLOCK_SIZE - m_buffer.size()), data.size()); // try fill to BLOCK_SIZE bytes 356 m_buffer.push_back(data.begin(), (data.begin() + len)); 357 358 if (m_buffer.size() < BLOCK_SIZE) // still doesn't fill the buffer 359 return (*this); 360 361 addDataImpl({m_buffer.data(), m_buffer.size()}); 362 m_buffer.clear(); 363 364 data = data.subspan(len); 365 } 366 367 const size_t dataSize = data.size(); 368 if (dataSize < BLOCK_SIZE) 369 { 370 m_buffer = {data.begin(), data.end()}; 371 return (*this); 372 } 373 374 const size_t len = dataSize - (dataSize % BLOCK_SIZE); // align on BLOCK_SIZE bytes 375 addDataImpl(data.first(len)); 376 377 if (len < dataSize) // didn't consume all data 378 m_buffer = {(data.begin() + len), data.end()}; 379 380 return (*this); 381 } 382 addData(const void * ptr,const std::size_t length)383 HAS_160& HAS_160::addData(const void *ptr, const std::size_t length) 384 { 385 // Span::size_type = std::size_t 386 return addData({static_cast<const Byte*>(ptr), length}); 387 } 388 389 template <std::size_t N> addData(const Byte (& array)[N])390 HAS_160& HAS_160::addData(const Byte (&array)[N]) 391 { 392 return addData({array, N}); 393 } 394 395 template <typename T, std::size_t N> addData(const T (& array)[N])396 HAS_160& HAS_160::addData(const T (&array)[N]) 397 { 398 return addData({reinterpret_cast<const Byte*>(array), (sizeof(T) * N)}); 399 } 400 401 template <typename T> addData(const Span<T> inSpan)402 HAS_160& HAS_160::addData(const Span<T> inSpan) 403 { 404 return addData({reinterpret_cast<const Byte*>(inSpan.data()), inSpan.size_bytes()}); 405 } 406 addDataImpl(const Span<const Byte> data)407 void HAS_160::addDataImpl(const Span<const Byte> data) 408 { 409 assert((data.size() % BLOCK_SIZE) == 0); 410 411 m_sizeCounter += data.size(); 412 413 for (size_t i = 0, iend = static_cast<size_t>(data.size() / BLOCK_SIZE); i < iend; ++i) 414 { 415 const Loader<uint32_t> x(static_cast<const Byte *>(data.data() + (i * BLOCK_SIZE))); 416 417 static const unsigned int lTable[80] = 418 { 419 18, 0, 1, 2, 3, 19, 4, 5, 6, 7, 16, 8, 9, 10, 11, 17, 12, 13, 14, 15, 420 18, 3, 6, 9, 12, 19, 15, 2, 5, 8, 16, 11, 14, 1, 4, 17, 7, 10, 13, 0, 421 18, 12, 5, 14, 7, 19, 0, 9, 2, 11, 16, 4, 13, 6, 15, 17, 8, 1, 10, 3, 422 18, 7, 2, 13, 8, 19, 3, 14, 9, 4, 16, 15, 10, 5, 0, 17, 11, 6, 1, 12 423 }; 424 425 uint32_t xTable[20]; 426 for (int j = 0; j < 16; ++j) 427 xTable[j] = x[j]; 428 429 const auto extendXTable = [&xTable](const unsigned int round) -> void 430 { 431 xTable[16] = xTable[lTable[round + 1]] ^ xTable[lTable[round + 2]] ^ xTable[lTable[round + 3]] ^ xTable[lTable[round + 4]]; 432 xTable[17] = xTable[lTable[round + 6]] ^ xTable[lTable[round + 7]] ^ xTable[lTable[round + 8]] ^ xTable[lTable[round + 9]]; 433 xTable[18] = xTable[lTable[round + 11]] ^ xTable[lTable[round + 12]] ^ xTable[lTable[round + 13]] ^ xTable[lTable[round + 14]]; 434 xTable[19] = xTable[lTable[round + 16]] ^ xTable[lTable[round + 17]] ^ xTable[lTable[round + 18]] ^ xTable[lTable[round + 19]]; 435 }; 436 437 uint32_t a = m_h[0]; 438 uint32_t b = m_h[1]; 439 uint32_t c = m_h[2]; 440 uint32_t d = m_h[3]; 441 uint32_t e = m_h[4]; 442 443 const auto round1 = [&xTable](uint32_t &a, uint32_t &b, uint32_t &c, uint32_t &d, uint32_t &e, const unsigned int s1, const int t) -> void 444 { 445 const uint32_t f = ((b & (c ^ d)) ^ d); // alternative 446 e = rotl(a, s1) + f + e + xTable[lTable[t]] + 0x00000000; 447 b = rotl(b, 10); 448 }; 449 extendXTable(0); 450 round1(a, b, c, d, e, 5, 0); 451 round1(e, a, b, c, d, 11, 1); 452 round1(d, e, a, b, c, 7, 2); 453 round1(c, d, e, a, b, 15, 3); 454 round1(b, c, d, e, a, 6, 4); 455 round1(a, b, c, d, e, 13, 5); 456 round1(e, a, b, c, d, 8, 6); 457 round1(d, e, a, b, c, 14, 7); 458 round1(c, d, e, a, b, 7, 8); 459 round1(b, c, d, e, a, 12, 9); 460 round1(a, b, c, d, e, 9, 10); 461 round1(e, a, b, c, d, 11, 11); 462 round1(d, e, a, b, c, 8, 12); 463 round1(c, d, e, a, b, 15, 13); 464 round1(b, c, d, e, a, 6, 14); 465 round1(a, b, c, d, e, 12, 15); 466 round1(e, a, b, c, d, 9, 16); 467 round1(d, e, a, b, c, 14, 17); 468 round1(c, d, e, a, b, 5, 18); 469 round1(b, c, d, e, a, 13, 19); 470 471 const auto round2 = [&xTable](uint32_t &a, uint32_t &b, uint32_t &c, uint32_t &d, uint32_t &e, const unsigned int s1, const int t) -> void 472 { 473 const uint32_t f = (b ^ c ^ d); 474 e = rotl(a, s1) + f + e + xTable[lTable[t]] + 0x5A827999; 475 b = rotl(b, 17); 476 }; 477 extendXTable(20); 478 round2(a, b, c, d, e, 5, 20); 479 round2(e, a, b, c, d, 11, 21); 480 round2(d, e, a, b, c, 7, 22); 481 round2(c, d, e, a, b, 15, 23); 482 round2(b, c, d, e, a, 6, 24); 483 round2(a, b, c, d, e, 13, 25); 484 round2(e, a, b, c, d, 8, 26); 485 round2(d, e, a, b, c, 14, 27); 486 round2(c, d, e, a, b, 7, 28); 487 round2(b, c, d, e, a, 12, 29); 488 round2(a, b, c, d, e, 9, 30); 489 round2(e, a, b, c, d, 11, 31); 490 round2(d, e, a, b, c, 8, 32); 491 round2(c, d, e, a, b, 15, 33); 492 round2(b, c, d, e, a, 6, 34); 493 round2(a, b, c, d, e, 12, 35); 494 round2(e, a, b, c, d, 9, 36); 495 round2(d, e, a, b, c, 14, 37); 496 round2(c, d, e, a, b, 5, 38); 497 round2(b, c, d, e, a, 13, 39); 498 499 const auto round3 = [&xTable](uint32_t &a, uint32_t &b, uint32_t &c, uint32_t &d, uint32_t &e, const unsigned int s1, const int t) -> void 500 { 501 const uint32_t f = (c ^ (b | (~d))); 502 e = rotl(a, s1) + f + e + xTable[lTable[t]] + 0x6ED9EBA1; 503 b = rotl(b, 25); 504 }; 505 extendXTable(40); 506 round3(a, b, c, d, e, 5, 40); 507 round3(e, a, b, c, d, 11, 41); 508 round3(d, e, a, b, c, 7, 42); 509 round3(c, d, e, a, b, 15, 43); 510 round3(b, c, d, e, a, 6, 44); 511 round3(a, b, c, d, e, 13, 45); 512 round3(e, a, b, c, d, 8, 46); 513 round3(d, e, a, b, c, 14, 47); 514 round3(c, d, e, a, b, 7, 48); 515 round3(b, c, d, e, a, 12, 49); 516 round3(a, b, c, d, e, 9, 50); 517 round3(e, a, b, c, d, 11, 51); 518 round3(d, e, a, b, c, 8, 52); 519 round3(c, d, e, a, b, 15, 53); 520 round3(b, c, d, e, a, 6, 54); 521 round3(a, b, c, d, e, 12, 55); 522 round3(e, a, b, c, d, 9, 56); 523 round3(d, e, a, b, c, 14, 57); 524 round3(c, d, e, a, b, 5, 58); 525 round3(b, c, d, e, a, 13, 59); 526 527 const auto round4 = [&xTable](uint32_t &a, uint32_t &b, uint32_t &c, uint32_t &d, uint32_t &e, const unsigned int s1, const int t) -> void 528 { 529 const uint32_t f = (b ^ c ^ d); 530 e = rotl(a, s1) + f + e + xTable[lTable[t]] + 0x8F1BBCDC; 531 b = rotl(b, 30); 532 }; 533 extendXTable(60); 534 round4(a, b, c, d, e, 5, 60); 535 round4(e, a, b, c, d, 11, 61); 536 round4(d, e, a, b, c, 7, 62); 537 round4(c, d, e, a, b, 15, 63); 538 round4(b, c, d, e, a, 6, 64); 539 round4(a, b, c, d, e, 13, 65); 540 round4(e, a, b, c, d, 8, 66); 541 round4(d, e, a, b, c, 14, 67); 542 round4(c, d, e, a, b, 7, 68); 543 round4(b, c, d, e, a, 12, 69); 544 round4(a, b, c, d, e, 9, 70); 545 round4(e, a, b, c, d, 11, 71); 546 round4(d, e, a, b, c, 8, 72); 547 round4(c, d, e, a, b, 15, 73); 548 round4(b, c, d, e, a, 6, 74); 549 round4(a, b, c, d, e, 12, 75); 550 round4(e, a, b, c, d, 9, 76); 551 round4(d, e, a, b, c, 14, 77); 552 round4(c, d, e, a, b, 5, 78); 553 round4(b, c, d, e, a, 13, 79); 554 555 m_h[0] += a; 556 m_h[1] += b; 557 m_h[2] += c; 558 m_h[3] += d; 559 m_h[4] += e; 560 } 561 } 562 } 563 } 564 using HAS_160 = Hash::HAS160_NS::HAS_160; 565 } 566 #endif // CHOCOBO1_HAS_160_H 567