lehmer_code_test.cc (2688B)
1 // Copyright (c) the JPEG XL Project Authors. All rights reserved. 2 // 3 // Use of this source code is governed by a BSD-style 4 // license that can be found in the LICENSE file. 5 6 #include "lib/jxl/lehmer_code.h" 7 8 #include <stdint.h> 9 #include <string.h> 10 11 #include <algorithm> 12 #include <numeric> 13 #include <vector> 14 15 #include "lib/jxl/base/bits.h" 16 #include "lib/jxl/base/data_parallel.h" 17 #include "lib/jxl/base/random.h" 18 #include "lib/jxl/test_utils.h" 19 #include "lib/jxl/testing.h" 20 21 namespace jxl { 22 namespace { 23 24 template <typename PermutationT> 25 struct WorkingSet { 26 explicit WorkingSet(size_t max_n) 27 : padded_n(1ull << CeilLog2Nonzero(max_n + 1)), 28 permutation(max_n), 29 temp(padded_n), 30 lehmer(max_n), 31 decoded(max_n) {} 32 33 size_t padded_n; 34 std::vector<PermutationT> permutation; 35 std::vector<uint32_t> temp; 36 std::vector<LehmerT> lehmer; 37 std::vector<PermutationT> decoded; 38 }; 39 40 template <typename PermutationT> 41 void Roundtrip(size_t n, WorkingSet<PermutationT>* ws) { 42 JXL_ASSERT(n != 0); 43 const size_t padded_n = 1ull << CeilLog2Nonzero(n); 44 45 Rng rng(n * 65537 + 13); 46 47 // Ensure indices fit into PermutationT 48 EXPECT_LE(n, 1ULL << (sizeof(PermutationT) * 8)); 49 50 std::iota(ws->permutation.begin(), ws->permutation.begin() + n, 0); 51 52 // For various random permutations: 53 for (size_t rep = 0; rep < 3; ++rep) { 54 rng.Shuffle(ws->permutation.data(), n); 55 56 // Must decode to the same permutation 57 ComputeLehmerCode(ws->permutation.data(), ws->temp.data(), n, 58 ws->lehmer.data()); 59 memset(ws->temp.data(), 0, padded_n * 4); 60 DecodeLehmerCode(ws->lehmer.data(), ws->temp.data(), n, ws->decoded.data()); 61 62 for (size_t i = 0; i < n; ++i) { 63 EXPECT_EQ(ws->permutation[i], ws->decoded[i]); 64 } 65 } 66 } 67 68 // Preallocates arrays and tests n = [begin, end). 69 template <typename PermutationT> 70 void RoundtripSizeRange(ThreadPool* pool, uint32_t begin, uint32_t end) { 71 ASSERT_NE(0u, begin); // n = 0 not allowed. 72 std::vector<WorkingSet<PermutationT>> working_sets; 73 74 JXL_CHECK(RunOnPool( 75 pool, begin, end, 76 [&working_sets, end](const size_t num_threads) { 77 for (size_t i = 0; i < num_threads; i++) { 78 working_sets.emplace_back(end - 1); 79 } 80 return true; 81 }, 82 [&working_sets](const uint32_t n, const size_t thread) { 83 Roundtrip(n, &working_sets[thread]); 84 }, 85 "lehmer test")); 86 } 87 88 TEST(LehmerCodeTest, TestRoundtrips) { 89 test::ThreadPoolForTests pool(8); 90 91 RoundtripSizeRange<uint16_t>(&pool, 1, 1026); 92 93 // Ensures PermutationT can fit > 16 bit values. 94 RoundtripSizeRange<uint32_t>(&pool, 65536, 65540); 95 } 96 97 } // namespace 98 } // namespace jxl