src/include/xxhash.hpp

   1 #pragma once
   2 #include <cstdint>
   3 #include <cstring>
   4 #include <array>
   5 #include <type_traits>
   6 #include <cstdint>
   7 #include <vector>
   8 #include <string>
   9
  10 #include <iostream>
  11
  12 /*
  13 xxHash - Extremely Fast Hash algorithm
  14 Header File
  15 Copyright (C) 2012-2018, Yann Collet.
  16 Copyright (C) 2017-2018, Piotr Pliszka.
  17 All rights reserved.
  18
  19 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
  20 Redistribution and use in source and binary forms, with or without
  21 modification, are permitted provided that the following conditions are
  22 met:
  23 * Redistributions of source code must retain the above copyright
  24 notice, this list of conditions and the following disclaimer.
  25 * Redistributions in binary form must reproduce the above
  26 copyright notice, this list of conditions and the following disclaimer
  27 in the documentation and/or other materials provided with the
  28 distribution.
  29 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  30 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  31 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  32 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  33 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  34 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  35 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  36 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  37 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  38 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  39 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  40 You can contact the author at :
  41 - xxHash source repository : https://github.com/Cyan4973/xxHash
  42 - xxHash C++ port repository : https://github.com/RedSpah/xxhash_cpp
  43 */
  44
  45 /* *************************************
  46 *  Tuning parameters
  47 ***************************************/
  48 /*!XXH_FORCE_MEMORY_ACCESS :
  49 * By default, access to unaligned memory is controlled by `memcpy()`, which is safe and portable.
  50 * Unfortunately, on some target/compiler combinations, the generated assembly is sub-optimal.
  51 * The below switch allow to select different access method for improved performance.
  52 * Method 0 (default) : use `memcpy()`. Safe and portable.
  53 * Method 1 : `__packed` statement. It depends on compiler extension (ie, not portable).
  54 *            This method is safe if your compiler supports it, and *generally* as fast or faster than `memcpy`.
  55 * Method 2 : direct access. This method doesn't depend on compiler but violate C standard.
  56 *            It can generate buggy code on targets which do not support unaligned memory accesses.
  57 *            But in some circumstances, it's the only known way to get the most performance (ie GCC + ARMv6)
  58 * See http://stackoverflow.com/a/32095106/646947 for details.
  59 * Prefer these methods in priority order (0 > 1 > 2)
  60 */
  61 #ifndef XXH_FORCE_MEMORY_ACCESS   /* can be defined externally, on command line for example */
  62 #  if defined(__GNUC__) && ( defined(__ARM_ARCH_6__) || defined(__ARM_ARCH_6J__) || defined(__ARM_ARCH_6K__) || defined(__ARM_ARCH_6Z__) || defined(__ARM_ARCH_6ZK__) || defined(__ARM_ARCH_6T2__) )
  63 #    define XXH_FORCE_MEMORY_ACCESS 2
  64 #  elif defined(__INTEL_COMPILER) || (defined(__GNUC__) && ( defined(__ARM_ARCH_7__) || defined(__ARM_ARCH_7A__) || defined(__ARM_ARCH_7R__) || defined(__ARM_ARCH_7M__) || defined(__ARM_ARCH_7S__) ))
  65 #    define XXH_FORCE_MEMORY_ACCESS 1
  66 #  endif
  67 #endif
  68
  69
  70 /*!XXH_FORCE_NATIVE_FORMAT :
  71 * By default, xxHash library provides endian-independent Hash values, based on little-endian convention.
  72 * Results are therefore identical for little-endian and big-endian CPU.
  73 * This comes at a performance cost for big-endian CPU, since some swapping is required to emulate little-endian format.
  74 * Should endian-independence be of no importance for your application, you may set the #define below to 1,
  75 * to improve speed for Big-endian CPU.
  76 * This option has no impact on Little_Endian CPU.
  77 */
  78 #if !defined(XXH_FORCE_NATIVE_FORMAT) || (XXH_FORCE_NATIVE_FORMAT == 0)  /* can be defined externally */
  79 #       define XXH_FORCE_NATIVE_FORMAT 0
  80 #       define XXH_CPU_LITTLE_ENDIAN 1
  81 #endif
  82
  83
  84 /*!XXH_FORCE_ALIGN_CHECK :
  85 * This is a minor performance trick, only useful with lots of very small keys.
  86 * It means : check for aligned/unaligned input.
  87 * The check costs one initial branch per hash;
  88 * set it to 0 when the input is guaranteed to be aligned,
  89 * or when alignment doesn't matter for performance.
  90 */
  91 #ifndef XXH_FORCE_ALIGN_CHECK /* can be defined externally */
  92 #       if defined(__i386) || defined(_M_IX86) || defined(__x86_64__) || defined(_M_X64)
  93 #               define XXH_FORCE_ALIGN_CHECK 0
  94 #       else
  95 #               define XXH_FORCE_ALIGN_CHECK 1
  96 #       endif
  97 #endif
  98
  99 /*!XXH_CPU_LITTLE_ENDIAN :
 100 * This is a CPU endian detection macro, will be
 101 * automatically set to 1 (little endian) if XXH_FORCE_NATIVE_FORMAT
 102 * is left undefined, XXH_FORCE_NATIVE_FORMAT is defined to 0, or if an x86/x86_64 compiler macro is defined.
 103 * If left undefined, endianness will be determined at runtime, at the cost of a slight one-time overhead
 104 * and a larger overhead due to get_endian() not being constexpr.
 105 */
 106 #ifndef XXH_CPU_LITTLE_ENDIAN
 107 #       if defined(__i386) || defined(_M_IX86) || defined(__x86_64__) || defined(_M_X64)
 108 #               define XXH_CPU_LITTLE_ENDIAN 1
 109 #       endif
 110 #endif
 111
 112 /* *************************************
 113 *  Compiler Specific Options
 114 ***************************************/
 115 #define XXH_GCC_VERSION (__GNUC__ * 100 + __GNUC_MINOR__)
 116
 117 namespace xxh
 118 {
 119         /* *************************************
 120         *  Version
 121         ***************************************/
 122         constexpr int cpp_version_major = 0;
 123         constexpr int cpp_version_minor = 6;
 124         constexpr int cpp_version_release = 5;
 125         constexpr uint32_t version_number() { return cpp_version_major * 10000 + cpp_version_minor * 100 + cpp_version_release; }
 126
 127         namespace hash_t_impl
 128         {
 129                 /* *************************************
 130                 *  Basic Types - Detail
 131                 ***************************************/
 132
 133                 using _hash32_underlying = uint32_t;
 134                 using _hash64_underlying = uint64_t;
 135
 136                 template <size_t N>
 137                 struct hash_type { using type = void; };
 138                 template <>
 139                 struct hash_type<32> { using type = _hash32_underlying; };
 140                 template <>
 141                 struct hash_type<64> { using type = _hash64_underlying; };
 142         }
 143
 144         /* *************************************
 145         *  Basic Types - Public
 146         ***************************************/
 147
 148         template <size_t N>
 149         using hash_t = typename hash_t_impl::hash_type<N>::type;
 150         using hash32_t = hash_t<32>;
 151         using hash64_t = hash_t<64>;
 152
 153         /* *************************************
 154         *  Bit Functions - Public
 155         ***************************************/
 156
 157         namespace bit_ops
 158         {
 159                 /* ****************************************
 160                 *  Intrinsics and Bit Operations
 161                 ******************************************/
 162
 163 #if defined(_MSC_VER)
 164                 inline uint32_t rotl32(uint32_t x, int32_t r) { return _rotl(x, r); }
 165                 inline uint64_t rotl64(uint64_t x, int32_t r) { return _rotl64(x, r); }
 166 #else
 167                 inline uint32_t rotl32(uint32_t x, int32_t r) { return ((x << r) | (x >> (32 - r))); }
 168                 inline uint64_t rotl64(uint64_t x, int32_t r) { return ((x << r) | (x >> (64 - r))); }
 169 #endif
 170
 171 #if defined(_MSC_VER)     /* Visual Studio */
 172                 inline uint32_t swap32(uint32_t x) { return _byteswap_ulong(x); }
 173                 inline uint64_t swap64(uint64_t x) { return _byteswap_uint64(x); }
 174 #elif XXH_GCC_VERSION >= 403
 175                 inline uint32_t swap32(uint32_t x) { return __builtin_bswap32(x); }
 176                 inline uint64_t swap64(uint64_t x) { return __builtin_bswap64(x); }
 177 #else
 178                 inline uint32_t swap32(uint32_t x) { return ((x << 24) & 0xff000000) | ((x << 8) & 0x00ff0000) | ((x >> 8) & 0x0000ff00) | ((x >> 24) & 0x000000ff); }
 179                 inline uint64_t swap64(uint64_t x) { return ((x << 56) & 0xff00000000000000ULL) | ((x << 40) & 0x00ff000000000000ULL) | ((x << 24) & 0x0000ff0000000000ULL) | ((x << 8) & 0x000000ff00000000ULL) | ((x >> 8) & 0x00000000ff000000ULL) | ((x >> 24) & 0x0000000000ff0000ULL) | ((x >> 40) & 0x000000000000ff00ULL) | ((x >> 56) & 0x00000000000000ffULL); }
 180 #endif
 181                 template <size_t N>
 182                 inline hash_t<N> rotl(hash_t<N> n, int32_t r) {};
 183
 184                 template <>
 185                 inline hash_t<32> rotl<32>(hash_t<32> n, int32_t r)
 186                 {
 187                         return rotl32(n, r);
 188                 };
 189
 190                 template <>
 191                 inline hash_t<64> rotl<64>(hash_t<64> n, int32_t r)
 192                 {
 193                         return rotl64(n, r);
 194                 };
 195
 196                 template <size_t N>
 197                 inline hash_t<N> swap(hash_t<N> n) {};
 198
 199                 template <>
 200                 inline hash_t<32> swap<32>(hash_t<32> n)
 201                 {
 202                         return swap32(n);
 203                 };
 204
 205                 template <>
 206                 inline hash_t<64> swap<64>(hash_t<64> n)
 207                 {
 208                         return swap64(n);
 209                 };
 210         }
 211
 212         /* *************************************
 213         *  Memory Functions - Public
 214         ***************************************/
 215
 216         enum class alignment : uint8_t { aligned, unaligned };
 217         enum class endianness : uint8_t { big_endian = 0, little_endian = 1, unspecified = 2 };
 218
 219         namespace mem_ops
 220         {
 221                 /* *************************************
 222                 *  Memory Access
 223                 ***************************************/
 224 #if (defined(XXH_FORCE_MEMORY_ACCESS) && (XXH_FORCE_MEMORY_ACCESS==2))
 225
 226                 /* Force direct memory access. Only works on CPU which support unaligned memory access in hardware */
 227                 template <size_t N>
 228                 inline hash_t<N> read_unaligned(const void* memPtr) { return *(const hash_t<N>*)memPtr; }
 229
 230 #elif (defined(XXH_FORCE_MEMORY_ACCESS) && (XXH_FORCE_MEMORY_ACCESS==1))
 231
 232                 /* __pack instructions are safer, but compiler specific, hence potentially problematic for some compilers */
 233                 /* currently only defined for gcc and icc */
 234                 template <size_t N>
 235                 using unalign = union { hash_t<N> uval; } __attribute((packed));
 236
 237                 template <size_t N>
 238                 inline hash_t<N> read_unaligned(const void* memPtr) { return ((const unalign*)memPtr)->uval; }
 239 #else
 240
 241                 /* portable and safe solution. Generally efficient.
 242                 * see : http://stackoverflow.com/a/32095106/646947
 243                 */
 244                 template <size_t N>
 245                 inline hash_t<N> read_unaligned(const void* memPtr)
 246                 {
 247                         hash_t<N> val;
 248                         memcpy(&val, memPtr, sizeof(val));
 249                         return val;
 250                 }
 251
 252 #endif   /* XXH_FORCE_DIRECT_MEMORY_ACCESS */
 253
 254                 inline hash_t<32> read32(const void* memPtr) { return read_unaligned<32>(memPtr); }
 255                 inline hash_t<64> read64(const void* memPtr) { return read_unaligned<64>(memPtr); }
 256
 257                 /* *************************************
 258                 *  Architecture Macros
 259                 ***************************************/
 260
 261                 /* XXH_CPU_LITTLE_ENDIAN can be defined externally, for example on the compiler command line */
 262
 263 #ifndef XXH_CPU_LITTLE_ENDIAN
 264
 265                 inline endianness get_endian(endianness endian)
 266                 {
 267                         static struct _dummy_t
 268                         {
 269                                 std::array<endianness, 3> endian_lookup = { endianness::big_endian, endianness::little_endian, endianness::unspecified };
 270                                 const int g_one = 1;
 271                                 _dummy_t()
 272                                 {
 273                                         endian_lookup[2] = static_cast<endianness>(*(const char*)(&g_one));
 274                                 }
 275                         } _dummy;
 276
 277                         return _dummy.endian_lookup[(uint8_t)endian];
 278                 }
 279
 280                 inline bool is_little_endian()
 281                 {
 282                         return get_endian(endianness::unspecified) == endianness::little_endian;
 283                 }
 284
 285 #else
 286                 constexpr endianness get_endian(endianness endian)
 287                 {
 288                         constexpr std::array<endianness, 3> endian_lookup = {{ endianness::big_endian, endianness::little_endian, (XXH_CPU_LITTLE_ENDIAN) ? endianness::little_endian : endianness::big_endian }};
 289                         return endian_lookup[static_cast<uint8_t>(endian)];
 290                 }
 291
 292                 constexpr bool is_little_endian()
 293                 {
 294                         return get_endian(endianness::unspecified) == endianness::little_endian;
 295                 }
 296
 297 #endif
 298
 299
 300
 301                 /* ***************************
 302                 *  Memory reads
 303                 *****************************/
 304
 305
 306                 template <size_t N>
 307                 inline hash_t<N> readLE_align(const void* ptr, endianness endian, alignment align)
 308                 {
 309                         if (align == alignment::unaligned)
 310                         {
 311                                 return endian == endianness::little_endian ? read_unaligned<N>(ptr) : bit_ops::swap<N>(read_unaligned<N>(ptr));
 312                         }
 313                         else
 314                         {
 315                                 return endian == endianness::little_endian ? *reinterpret_cast<const hash_t<N>*>(ptr) : bit_ops::swap<N>(*reinterpret_cast<const hash_t<N>*>(ptr));
 316                         }
 317                 }
 318
 319                 template <size_t N>
 320                 inline hash_t<N> readLE(const void* ptr, endianness endian)
 321                 {
 322                         return readLE_align<N>(ptr, endian, alignment::unaligned);
 323                 }
 324
 325                 template <size_t N>
 326                 inline hash_t<N> readBE(const void* ptr)
 327                 {
 328                         return is_little_endian() ? bit_ops::swap<N>(read_unaligned<N>(ptr)) : read_unaligned<N>(ptr);
 329                 }
 330
 331                 template <size_t N>
 332                 inline alignment get_alignment(const void* input)
 333                 {
 334                         return ((XXH_FORCE_ALIGN_CHECK) && ((reinterpret_cast<uintptr_t>(input) & ((N / 8) - 1)) == 0)) ? xxh::alignment::aligned : xxh::alignment::unaligned;
 335                 }
 336         }
 337
 338         /* *******************************************************************
 339         *  Hash functions
 340         *********************************************************************/
 341
 342         namespace detail
 343         {
 344                 /* *******************************************************************
 345                 *  Hash functions - Implementation
 346                 *********************************************************************/
 347
 348                 constexpr static std::array<hash32_t, 5> primes32 = {{ 2654435761U, 2246822519U, 3266489917U, 668265263U, 374761393U }};
 349                 constexpr static std::array<hash64_t, 5> primes64 = {{ 11400714785074694791ULL, 14029467366897019727ULL, 1609587929392839161ULL, 9650029242287828579ULL, 2870177450012600261ULL }};
 350
 351                 template <size_t N>
 352                 constexpr hash_t<N> PRIME(int32_t n) {};
 353
 354                 template <>
 355                 constexpr hash32_t PRIME<32>(int32_t n)
 356                 {
 357                         return primes32[n - 1];
 358                 }
 359
 360                 template <>
 361                 constexpr hash64_t PRIME<64>(int32_t n)
 362                 {
 363                         return primes64[n - 1];
 364                 }
 365
 366                 template <size_t N>
 367                 inline hash_t<N> round(hash_t<N> seed, hash_t<N> input)
 368                 {
 369                         seed += input * PRIME<N>(2);
 370                         seed = bit_ops::rotl<N>(seed, ((N == 32) ? 13 : 31));
 371                         seed *= PRIME<N>(1);
 372                         return seed;
 373                 }
 374
 375                 inline hash64_t mergeRound64(hash64_t acc, hash64_t val)
 376                 {
 377                         val = round<64>(0, val);
 378                         acc ^= val;
 379                         acc = acc * PRIME<64>(1) + PRIME<64>(4);
 380                         return acc;
 381                 }
 382
 383                 template <size_t N>
 384                 inline void endian_align_sub_mergeround(
 385 #if __cplusplus < 201703L
 386                   __attribute__((unused))
 387 #else
 388                   [[maybe_unused]]
 389 #endif
 390                   hash_t<N>& hash_ret, hash_t<N> v1, hash_t<N> v2, hash_t<N> v3, hash_t<N> v4) {};
 391
 392                 template <>
 393                 inline void endian_align_sub_mergeround<64>(hash_t<64>& hash_ret, hash_t<64> v1, hash_t<64> v2, hash_t<64> v3, hash_t<64> v4)
 394                 {
 395                         hash_ret = mergeRound64(hash_ret, v1);
 396                         hash_ret = mergeRound64(hash_ret, v2);
 397                         hash_ret = mergeRound64(hash_ret, v3);
 398                         hash_ret = mergeRound64(hash_ret, v4);
 399                 }
 400
 401                 template <size_t N>
 402                 inline hash_t<N> endian_align_sub_ending(hash_t<N> hash_ret, const uint8_t* p, const uint8_t* bEnd, xxh::endianness endian, xxh::alignment align) {};
 403
 404                 template <>
 405                 inline hash_t<32> endian_align_sub_ending<32>(hash_t<32> hash_ret, const uint8_t* p, const uint8_t* bEnd, xxh::endianness endian, xxh::alignment align)
 406                 {
 407                         while ((p + 4) <= bEnd)
 408                         {
 409                                 hash_ret += mem_ops::readLE_align<32>(p, endian, align) * PRIME<32>(3);
 410                                 hash_ret = bit_ops::rotl<32>(hash_ret, 17) * PRIME<32>(4);
 411                                 p += 4;
 412                         }
 413
 414                         while (p < bEnd)
 415                         {
 416                                 hash_ret += (*p) * PRIME<32>(5);
 417                                 hash_ret = bit_ops::rotl<32>(hash_ret, 11) * PRIME<32>(1);
 418                                 p++;
 419                         }
 420
 421                         hash_ret ^= hash_ret >> 15;
 422                         hash_ret *= PRIME<32>(2);
 423                         hash_ret ^= hash_ret >> 13;
 424                         hash_ret *= PRIME<32>(3);
 425                         hash_ret ^= hash_ret >> 16;
 426
 427                         return hash_ret;
 428                 }
 429
 430                 template <>
 431                 inline hash_t<64> endian_align_sub_ending<64>(hash_t<64> hash_ret, const uint8_t* p, const uint8_t* bEnd, xxh::endianness endian, xxh::alignment align)
 432                 {
 433                         while (p + 8 <= bEnd)
 434                         {
 435                                 const hash64_t k1 = round<64>(0, mem_ops::readLE_align<64>(p, endian, align));
 436                                 hash_ret ^= k1;
 437                                 hash_ret = bit_ops::rotl<64>(hash_ret, 27) * PRIME<64>(1) + PRIME<64>(4);
 438                                 p += 8;
 439                         }
 440
 441                         if (p + 4 <= bEnd)
 442                         {
 443                                 hash_ret ^= static_cast<hash64_t>(mem_ops::readLE_align<32>(p, endian, align)) * PRIME<64>(1);
 444                                 hash_ret = bit_ops::rotl<64>(hash_ret, 23) * PRIME<64>(2) + PRIME<64>(3);
 445                                 p += 4;
 446                         }
 447
 448                         while (p < bEnd)
 449                         {
 450                                 hash_ret ^= (*p) * PRIME<64>(5);
 451                                 hash_ret = bit_ops::rotl<64>(hash_ret, 11) * PRIME<64>(1);
 452                                 p++;
 453                         }
 454
 455                         hash_ret ^= hash_ret >> 33;
 456                         hash_ret *= PRIME<64>(2);
 457                         hash_ret ^= hash_ret >> 29;
 458                         hash_ret *= PRIME<64>(3);
 459                         hash_ret ^= hash_ret >> 32;
 460
 461                         return hash_ret;
 462                 }
 463
 464                 template <size_t N>
 465                 inline hash_t<N> endian_align(const void* input, size_t len, hash_t<N> seed, xxh::endianness endian, xxh::alignment align)
 466                 {
 467                         static_assert(!(N != 32 && N != 64), "You can only call endian_align in 32 or 64 bit mode.");
 468
 469                         const uint8_t* p = static_cast<const uint8_t*>(input);
 470                         const uint8_t* bEnd = p + len;
 471                         hash_t<N> hash_ret;
 472
 473                         if (len >= (N / 2))
 474                         {
 475                                 const uint8_t* const limit = bEnd - (N / 2);
 476                                 hash_t<N> v1 = seed + PRIME<N>(1) + PRIME<N>(2);
 477                                 hash_t<N> v2 = seed + PRIME<N>(2);
 478                                 hash_t<N> v3 = seed + 0;
 479                                 hash_t<N> v4 = seed - PRIME<N>(1);
 480
 481                                 do
 482                                 {
 483                                         v1 = round<N>(v1, mem_ops::readLE_align<N>(p, endian, align)); p += (N / 8);
 484                                         v2 = round<N>(v2, mem_ops::readLE_align<N>(p, endian, align)); p += (N / 8);
 485                                         v3 = round<N>(v3, mem_ops::readLE_align<N>(p, endian, align)); p += (N / 8);
 486                                         v4 = round<N>(v4, mem_ops::readLE_align<N>(p, endian, align)); p += (N / 8);
 487                                 } while (p <= limit);
 488
 489                                 hash_ret = bit_ops::rotl<N>(v1, 1) + bit_ops::rotl<N>(v2, 7) + bit_ops::rotl<N>(v3, 12) + bit_ops::rotl<N>(v4, 18);
 490
 491                                 endian_align_sub_mergeround<N>(hash_ret, v1, v2, v3, v4);
 492                         }
 493                         else { hash_ret = seed + PRIME<N>(5); }
 494
 495                         hash_ret += static_cast<hash_t<N>>(len);
 496
 497                         return endian_align_sub_ending<N>(hash_ret, p, bEnd, endian, align);
 498                 }
 499         }
 500
 501         template <size_t N>
 502         hash_t<N> xxhash(const void* input, size_t len, hash_t<N> seed = 0, endianness endian = endianness::unspecified)
 503         {
 504                 static_assert(!(N != 32 && N != 64), "You can only call xxhash in 32 or 64 bit mode.");
 505                 return detail::endian_align<N>(input, len, seed, mem_ops::get_endian(endian), mem_ops::get_alignment<N>(input));
 506         }
 507
 508         template <size_t N, typename T>
 509         hash_t<N> xxhash(const std::basic_string<T>& input, hash_t<N> seed = 0, endianness endian = endianness::unspecified)
 510         {
 511                 static_assert(!(N != 32 && N != 64), "You can only call xxhash in 32 or 64 bit mode.");
 512                 return detail::endian_align<N>(static_cast<const void*>(input.data()), input.length() * sizeof(T), seed, mem_ops::get_endian(endian), mem_ops::get_alignment<N>(static_cast<const void*>(input.data())));
 513         }
 514
 515         template <size_t N, typename ContiguousIterator>
 516         hash_t<N> xxhash(ContiguousIterator begin, ContiguousIterator end, hash_t<N> seed = 0, endianness endian = endianness::unspecified)
 517         {
 518                 static_assert(!(N != 32 && N != 64), "You can only call xxhash in 32 or 64 bit mode.");
 519                 using T = typename std::decay_t<decltype(*end)>;
 520                 return detail::endian_align<N>(static_cast<const void*>(&*begin), (end - begin) * sizeof(T), seed, mem_ops::get_endian(endian), mem_ops::get_alignment<N>(static_cast<const void*>(&*begin)));
 521         }
 522
 523         template <size_t N, typename T>
 524         hash_t<N> xxhash(const std::vector<T>& input, hash_t<N> seed = 0, endianness endian = endianness::unspecified)
 525         {
 526                 static_assert(!(N != 32 && N != 64), "You can only call xxhash in 32 or 64 bit mode.");
 527                 return detail::endian_align<N>(static_cast<const void*>(input.data()), input.size() * sizeof(T), seed, mem_ops::get_endian(endian), mem_ops::get_alignment<N>(static_cast<const void*>(input.data())));
 528         }
 529
 530         template <size_t N, typename T, size_t AN>
 531         hash_t<N> xxhash(const std::array<T, AN>& input, hash_t<N> seed = 0, endianness endian = endianness::unspecified)
 532         {
 533                 static_assert(!(N != 32 && N != 64), "You can only call xxhash in 32 or 64 bit mode.");
 534                 return detail::endian_align<N>(static_cast<const void*>(input.data()), AN * sizeof(T), seed, mem_ops::get_endian(endian), mem_ops::get_alignment<N>(static_cast<const void*>(input.data())));
 535         }
 536
 537         template <size_t N, typename T>
 538         hash_t<N> xxhash(const std::initializer_list<T>& input, hash_t<N> seed = 0, endianness endian = endianness::unspecified)
 539         {
 540                 static_assert(!(N != 32 && N != 64), "You can only call xxhash in 32 or 64 bit mode.");
 541                 return detail::endian_align<N>(static_cast<const void*>(input.begin()), input.size() * sizeof(T), seed, mem_ops::get_endian(endian), mem_ops::get_alignment<N>(static_cast<const void*>(input.begin())));
 542         }
 543
 544
 545         /* *******************************************************************
 546         *  Hash streaming
 547         *********************************************************************/
 548         enum class error_code : uint8_t { ok = 0, error };
 549
 550         template <size_t N>
 551         class hash_state_t
 552         {
 553                 uint64_t total_len = 0;
 554                 hash_t<N> v1 = 0, v2 = 0, v3 = 0, v4 = 0;
 555                 std::array<hash_t<N>, 4> mem = {{ 0,0,0,0 }};
 556                 uint32_t memsize = 0;
 557
 558                 inline error_code _update_impl(const void* input, size_t length, endianness endian)
 559                 {
 560                         const uint8_t* p = reinterpret_cast<const uint8_t*>(input);
 561                         const uint8_t* const bEnd = p + length;
 562
 563                         if (!input) { return xxh::error_code::error; }
 564
 565                         total_len += length;
 566
 567                         if (memsize + length < (N / 2))
 568                         {   /* fill in tmp buffer */
 569                                 memcpy(reinterpret_cast<uint8_t*>(mem.data()) + memsize, input, length);
 570                                 memsize += static_cast<uint32_t>(length);
 571                                 return error_code::ok;
 572                         }
 573
 574                         if (memsize)
 575                         {   /* some data left from previous update */
 576                                 memcpy(reinterpret_cast<uint8_t*>(mem.data()) + memsize, input, (N / 2) - memsize);
 577
 578                                 const hash_t<N>* ptr = mem.data();
 579                                 v1 = detail::round<N>(v1, mem_ops::readLE<N>(ptr, endian)); ptr++;
 580                                 v2 = detail::round<N>(v2, mem_ops::readLE<N>(ptr, endian)); ptr++;
 581                                 v3 = detail::round<N>(v3, mem_ops::readLE<N>(ptr, endian)); ptr++;
 582                                 v4 = detail::round<N>(v4, mem_ops::readLE<N>(ptr, endian));
 583
 584                                 p += (N / 2) - memsize;
 585                                 memsize = 0;
 586                         }
 587
 588                         if (p <= bEnd - (N / 2))
 589                         {
 590                                 const uint8_t* const limit = bEnd - (N / 2);
 591
 592                                 do
 593                                 {
 594                                         v1 = detail::round<N>(v1, mem_ops::readLE<N>(p, endian)); p += (N / 8);
 595                                         v2 = detail::round<N>(v2, mem_ops::readLE<N>(p, endian)); p += (N / 8);
 596                                         v3 = detail::round<N>(v3, mem_ops::readLE<N>(p, endian)); p += (N / 8);
 597                                         v4 = detail::round<N>(v4, mem_ops::readLE<N>(p, endian)); p += (N / 8);
 598                                 } while (p <= limit);
 599                         }
 600
 601                         if (p < bEnd)
 602                         {
 603                                 memcpy(mem.data(), p, static_cast<size_t>(bEnd - p));
 604                                 memsize = static_cast<uint32_t>(bEnd - p);
 605                         }
 606
 607                         return error_code::ok;
 608                 }
 609
 610                 inline hash_t<N> _digest_impl(endianness endian) const
 611                 {
 612                         const uint8_t* p = reinterpret_cast<const uint8_t*>(mem.data());
 613                         const uint8_t* const bEnd = reinterpret_cast<const uint8_t*>(mem.data()) + memsize;
 614                         hash_t<N> hash_ret;
 615
 616                         if (total_len > (N / 2))
 617                         {
 618                                 hash_ret = bit_ops::rotl<N>(v1, 1) + bit_ops::rotl<N>(v2, 7) + bit_ops::rotl<N>(v3, 12) + bit_ops::rotl<N>(v4, 18);
 619
 620                                 detail::endian_align_sub_mergeround<N>(hash_ret, v1, v2, v3, v4);
 621                         }
 622                         else { hash_ret = v3 + detail::PRIME<N>(5); }
 623
 624                         hash_ret += static_cast<hash_t<N>>(total_len);
 625
 626                         return detail::endian_align_sub_ending<N>(hash_ret, p, bEnd, endian, alignment::unaligned);
 627                 }
 628
 629         public:
 630                 hash_state_t(hash_t<N> seed = 0)
 631                 {
 632                         static_assert(!(N != 32 && N != 64), "You can only stream hashing in 32 or 64 bit mode.");
 633                         v1 = seed + detail::PRIME<N>(1) + detail::PRIME<N>(2);
 634                         v2 = seed + detail::PRIME<N>(2);
 635                         v3 = seed + 0;
 636                         v4 = seed - detail::PRIME<N>(1);
 637                 };
 638
 639                 hash_state_t operator=(hash_state_t<N>& other)
 640                 {
 641                         memcpy(this, other, sizeof(hash_state_t<N>));
 642                 }
 643
 644                 error_code reset(hash_t<N> seed = 0)
 645                 {
 646                         memset(this, 0, sizeof(hash_state_t<N>));
 647                         v1 = seed + detail::PRIME<N>(1) + detail::PRIME<N>(2);
 648                         v2 = seed + detail::PRIME<N>(2);
 649                         v3 = seed + 0;
 650                         v4 = seed - detail::PRIME<N>(1);
 651                         return error_code::ok;
 652                 }
 653
 654                 error_code update(const void* input, size_t length, endianness endian = endianness::unspecified)
 655                 {
 656                         return _update_impl(input, length, mem_ops::get_endian(endian));
 657                 }
 658
 659                 template <typename T>
 660                 error_code update(const std::basic_string<T>& input, endianness endian = endianness::unspecified)
 661                 {
 662                         return _update_impl(static_cast<const void*>(input.data()), input.length() * sizeof(T), mem_ops::get_endian(endian));
 663                 }
 664
 665                 template <typename ContiguousIterator>
 666                 error_code update(ContiguousIterator begin, ContiguousIterator end, endianness endian = endianness::unspecified)
 667                 {
 668                         using T = typename std::decay_t<decltype(*end)>;
 669                         return _update_impl(static_cast<const void*>(&*begin), (end - begin) * sizeof(T), mem_ops::get_endian(endian));
 670                 }
 671
 672                 template <typename T>
 673                 error_code update(const std::vector<T>& input, endianness endian = endianness::unspecified)
 674                 {
 675                         return _update_impl(static_cast<const void*>(input.data()), input.size() * sizeof(T), mem_ops::get_endian(endian));
 676                 }
 677
 678                 template <typename T, size_t AN>
 679                 error_code update(const std::array<T, AN>& input, endianness endian = endianness::unspecified)
 680                 {
 681                         return _update_impl(static_cast<const void*>(input.data()), AN * sizeof(T), mem_ops::get_endian(endian));
 682                 }
 683
 684                 template <typename T>
 685                 error_code update(const std::initializer_list<T>& input, endianness endian = endianness::unspecified)
 686                 {
 687                         return _update_impl(static_cast<const void*>(input.begin()), input.size() * sizeof(T), mem_ops::get_endian(endian));
 688                 }
 689
 690                 hash_t<N> digest(endianness endian = endianness::unspecified)
 691                 {
 692                         return _digest_impl(mem_ops::get_endian(endian));
 693                 }
 694         };
 695
 696         using hash_state32_t = hash_state_t<32>;
 697         using hash_state64_t = hash_state_t<64>;
 698
 699
 700         /* *******************************************************************
 701         *  Canonical
 702         *********************************************************************/
 703
 704         template <size_t N>
 705         struct canonical_t
 706         {
 707                 std::array<uint8_t, N / 8> digest;\
 708
 709
 710
 711                 canonical_t(hash_t<N> hash)
 712                 {
 713                         if (mem_ops::is_little_endian()) { hash = bit_ops::swap<N>(hash); }
 714                         memcpy(digest.data(), &hash, sizeof(canonical_t<N>));
 715                 }
 716
 717                 hash_t<N> get_hash() const
 718                 {
 719                         return mem_ops::readBE<N>(&digest);
 720                 }
 721         };
 722
 723         using canonical32_t = canonical_t<32>;
 724         using canonical64_t = canonical_t<64>;
 725 }