compiler-rt/lib/sanitizer_common/tests/sanitizer_lzw_test.cpp

   1 //===-- sanitizer_lzw_test.cpp ----------------------------------*- C++ -*-===//
   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 #include "sanitizer_common/sanitizer_lzw.h"
   9
  10 #include <algorithm>
  11 #include <iterator>
  12
  13 #include "gtest/gtest.h"
  14 #include "sanitizer_hash.h"
  15
  16 namespace __sanitizer {
  17
  18 template <typename T>
  19 struct LzwTest : public ::testing::Test {
  20   template <typename Generator>
  21   void Run(size_t n, Generator gen) {
  22     std::vector<T> data(n);
  23     std::generate(data.begin(), data.end(), gen);
  24
  25     std::vector<u64> lzw;
  26     LzwEncode<T>(data.begin(), data.end(), std::back_inserter(lzw));
  27
  28     std::vector<T> unlzw(data.size() * 2);
  29     auto unlzw_end = LzwDecode<T>(lzw.begin(), lzw.end(), unlzw.data());
  30     unlzw.resize(unlzw_end - unlzw.data());
  31
  32     EXPECT_EQ(data, unlzw);
  33   }
  34 };
  35
  36 static constexpr size_t kSizes[] = {0, 1, 2, 7, 13, 32, 129, 10000};
  37
  38 using LzwTestTypes = ::testing::Types<u8, u16, u32, u64>;
  39 TYPED_TEST_SUITE(LzwTest, LzwTestTypes, );
  40
  41 TYPED_TEST(LzwTest, Same) {
  42   MurMur2Hash64Builder h(0);
  43   for (size_t sz : kSizes) {
  44     u64 v = 0;
  45     for (size_t i = 0; i < 100 && !this->HasFailure(); ++i) {
  46       this->Run(sz, [&] { return v; });
  47       h.add(i);
  48       v = h.get();
  49     }
  50   }
  51 }
  52
  53 TYPED_TEST(LzwTest, Increment) {
  54   MurMur2Hash64Builder h(0);
  55   for (size_t sz : kSizes) {
  56     u64 v = 0;
  57     for (size_t i = 0; i < 100 && !this->HasFailure(); ++i) {
  58       this->Run(sz, [&v] { return v++; });
  59       h.add(i);
  60       v = h.get();
  61     }
  62   }
  63 }
  64
  65 TYPED_TEST(LzwTest, IncrementMod) {
  66   MurMur2Hash64Builder h(0);
  67   for (size_t sz : kSizes) {
  68     u64 v = 0;
  69     for (size_t i = 1; i < 16 && !this->HasFailure(); ++i) {
  70       this->Run(sz, [&] { return v++ % i; });
  71       h.add(i);
  72       v = h.get();
  73     }
  74   }
  75 }
  76
  77 TYPED_TEST(LzwTest, RandomLimited) {
  78   for (size_t sz : kSizes) {
  79     for (size_t i = 1; i < 1000 && !this->HasFailure(); i *= 2) {
  80       u64 v = 0;
  81       this->Run(sz, [&] {
  82         MurMur2Hash64Builder h(v % i /* Keep unique set limited */);
  83         v = h.get();
  84         return v;
  85       });
  86     }
  87   }
  88 }
  89
  90 }  // namespace __sanitizer