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>
Run__sanitizer::LzwTest20 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
TYPED_TEST(LzwTest,Same)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
TYPED_TEST(LzwTest,Increment)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
TYPED_TEST(LzwTest,IncrementMod)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
TYPED_TEST(LzwTest,RandomLimited)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