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