llvm/unittests/Support/xxhashTest.cpp

   1 //===- llvm/unittest/Support/xxhashTest.cpp -------------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "llvm/Support/xxhash.h"
  10 #include "gtest/gtest.h"
  11
  12 using namespace llvm;
  13
  14 /* use #define to make them constant, required for initialization */
  15 #define PRIME32 2654435761U
  16 #define PRIME64 11400714785074694797ULL
  17
  18 /*
  19  * Fills a test buffer with pseudorandom data.
  20  *
  21  * This is used in the sanity check - its values must not be changed.
  22  */
  23 static void fillTestBuffer(uint8_t *buffer, size_t len) {
  24   uint64_t byteGen = PRIME32;
  25
  26   assert(buffer != NULL);
  27
  28   for (size_t i = 0; i < len; i++) {
  29     buffer[i] = (uint8_t)(byteGen >> 56);
  30     byteGen *= PRIME64;
  31   }
  32 }
  33
  34 TEST(xxhashTest, Basic) {
  35   EXPECT_EQ(0xef46db3751d8e999U, xxHash64(StringRef()));
  36   EXPECT_EQ(0x33bf00a859c4ba3fU, xxHash64("foo"));
  37   EXPECT_EQ(0x48a37c90ad27a659U, xxHash64("bar"));
  38   EXPECT_EQ(0x69196c1b3af0bff9U,
  39             xxHash64("0123456789abcdefghijklmnopqrstuvwxyz"));
  40 }
  41
  42 TEST(xxhashTest, xxh3) {
  43   constexpr size_t size = 2243;
  44   uint8_t a[size];
  45   uint64_t x = 1;
  46   for (size_t i = 0; i < size; ++i) {
  47     x ^= x << 13;
  48     x ^= x >> 7;
  49     x ^= x << 17;
  50     a[i] = uint8_t(x);
  51   }
  52
  53 #define F(len, expected)                                                       \
  54   EXPECT_EQ(uint64_t(expected), xxh3_64bits(ArrayRef(a, size_t(len))))
  55   F(0, 0x2d06800538d394c2);
  56   F(1, 0xd0d496e05c553485);
  57   F(2, 0x84d625edb7055eac);
  58   F(3, 0x6ea2d59aca5c3778);
  59   F(4, 0xbf65290914e80242);
  60   F(5, 0xc01fd099ad4fc8e4);
  61   F(6, 0x9e3ea8187399caa5);
  62   F(7, 0x9da8b60540644f5a);
  63   F(8, 0xabc1413da6cd0209);
  64   F(9, 0x8bc89400bfed51f6);
  65   F(16, 0x7e46916754d7c9b8);
  66   F(17, 0xed4be912ba5f836d);
  67   F(32, 0xf59b59b58c304fd1);
  68   F(33, 0x9013fb74ca603e0c);
  69   F(64, 0xfa5271fcce0db1c3);
  70   F(65, 0x79c42431727f1012);
  71   F(96, 0x591ee0ddf9c9ccd1);
  72   F(97, 0x8ffc6a3111fe19da);
  73   F(128, 0x06a146ee9a2da378);
  74   F(129, 0xbc7138129bf065da);
  75   F(403, 0xcefeb3ffa532ad8c);
  76   F(512, 0xcdfa6b6268e3650f);
  77   F(513, 0x4bb5d42742f9765f);
  78   F(2048, 0x330ce110cbb79eae);
  79   F(2049, 0x3ba6afa0249fef9a);
  80   F(2240, 0xd61d4d2a94e926a8);
  81   F(2243, 0x0979f786a24edde7);
  82 #undef F
  83 }
  84
  85 TEST(xxhashTest, xxh3_128bits) {
  86 #define SANITY_BUFFER_SIZE 2367
  87   uint8_t sanityBuffer[SANITY_BUFFER_SIZE];
  88
  89   fillTestBuffer(sanityBuffer, sizeof(sanityBuffer));
  90
  91 #define F(len, expected)                                                       \
  92   EXPECT_EQ(XXH128_hash_t(expected),                                           \
  93             xxh3_128bits(ArrayRef(sanityBuffer, size_t(len))))
  94
  95   F(0, (XXH128_hash_t{0x6001C324468D497FULL,
  96                       0x99AA06D3014798D8ULL})); /* empty string */
  97   F(1, (XXH128_hash_t{0xC44BDFF4074EECDBULL,
  98                       0xA6CD5E9392000F6AULL})); /*  1 -  3 */
  99   F(6, (XXH128_hash_t{0x3E7039BDDA43CFC6ULL,
 100                       0x082AFE0B8162D12AULL})); /*  4 -  8 */
 101   F(12, (XXH128_hash_t{0x061A192713F69AD9ULL,
 102                        0x6E3EFD8FC7802B18ULL})); /*  9 - 16 */
 103   F(24, (XXH128_hash_t{0x1E7044D28B1B901DULL,
 104                        0x0CE966E4678D3761ULL})); /* 17 - 32 */
 105   F(48, (XXH128_hash_t{0xF942219AED80F67BULL,
 106                        0xA002AC4E5478227EULL})); /* 33 - 64 */
 107   F(81, (XXH128_hash_t{0x5E8BAFB9F95FB803ULL,
 108                        0x4952F58181AB0042ULL})); /* 65 - 96 */
 109   F(222, (XXH128_hash_t{0xF1AEBD597CEC6B3AULL,
 110                         0x337E09641B948717ULL})); /* 129-240 */
 111   F(403,
 112     (XXH128_hash_t{
 113         0xCDEB804D65C6DEA4ULL,
 114         0x1B6DE21E332DD73DULL})); /* one block, last stripe is overlapping */
 115   F(512,
 116     (XXH128_hash_t{
 117         0x617E49599013CB6BULL,
 118         0x18D2D110DCC9BCA1ULL})); /* one block, finishing at stripe boundary */
 119   F(2048,
 120     (XXH128_hash_t{
 121         0xDD59E2C3A5F038E0ULL,
 122         0xF736557FD47073A5ULL})); /* 2 blocks, finishing at block boundary */
 123   F(2240,
 124     (XXH128_hash_t{
 125         0x6E73A90539CF2948ULL,
 126         0xCCB134FBFA7CE49DULL})); /* 3 blocks, finishing at stripe boundary */
 127   F(2367,
 128     (XXH128_hash_t{
 129         0xCB37AEB9E5D361EDULL,
 130         0xE89C0F6FF369B427ULL})); /* 3 blocks, last stripe is overlapping */
 131 #undef F
 132 }