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/coeff_order.h"
7
8 #include <stdio.h>
9
10 #include <algorithm>
11 #include <numeric> // iota
12 #include <random>
13 #include <utility>
14 #include <vector>
15
16 #include "gtest/gtest.h"
17 #include "lib/jxl/base/span.h"
18 #include "lib/jxl/coeff_order_fwd.h"
19 #include "lib/jxl/dec_bit_reader.h"
20 #include "lib/jxl/enc_coeff_order.h"
21
22 namespace jxl {
23 namespace {
24
RoundtripPermutation(coeff_order_t * perm,coeff_order_t * out,size_t len,size_t * size)25 void RoundtripPermutation(coeff_order_t* perm, coeff_order_t* out, size_t len,
26 size_t* size) {
27 BitWriter writer;
28 EncodePermutation(perm, 0, len, &writer, 0, nullptr);
29 writer.ZeroPadToByte();
30 Status status = true;
31 {
32 BitReader reader(writer.GetSpan());
33 BitReaderScopedCloser closer(&reader, &status);
34 ASSERT_TRUE(DecodePermutation(0, len, out, &reader));
35 }
36 ASSERT_TRUE(status);
37 *size = writer.GetSpan().size();
38 }
39
40 enum Permutation { kIdentity, kFewSwaps, kFewSlides, kRandom };
41
42 constexpr size_t kNumReps = 128;
43 constexpr size_t kSwaps = 32;
44
TestPermutation(Permutation kind,size_t len)45 void TestPermutation(Permutation kind, size_t len) {
46 std::vector<coeff_order_t> perm(len);
47 std::iota(perm.begin(), perm.end(), 0);
48 std::mt19937 rng;
49 if (kind == kFewSwaps) {
50 std::uniform_int_distribution<size_t> dist(0, len - 1);
51 for (size_t i = 0; i < kSwaps; i++) {
52 size_t a = dist(rng);
53 size_t b = dist(rng);
54 std::swap(perm[a], perm[b]);
55 }
56 }
57 if (kind == kFewSlides) {
58 std::uniform_int_distribution<size_t> dist(0, len - 1);
59 for (size_t i = 0; i < kSwaps; i++) {
60 size_t a = dist(rng);
61 size_t b = dist(rng);
62 size_t from = std::min(a, b);
63 size_t to = std::max(a, b);
64 size_t start = perm[from];
65 for (size_t j = from; j < to; j++) {
66 perm[j] = perm[j + 1];
67 }
68 perm[to] = start;
69 }
70 }
71 if (kind == kRandom) {
72 std::shuffle(perm.begin(), perm.end(), rng);
73 }
74 std::vector<coeff_order_t> out(len);
75 size_t size = 0;
76 for (size_t i = 0; i < kNumReps; i++) {
77 RoundtripPermutation(perm.data(), out.data(), len, &size);
78 for (size_t idx = 0; idx < len; idx++) {
79 EXPECT_EQ(perm[idx], out[idx]);
80 }
81 }
82 printf("Encoded size: %zu\n", size);
83 }
84
TEST(CoeffOrderTest,IdentitySmall)85 TEST(CoeffOrderTest, IdentitySmall) { TestPermutation(kIdentity, 256); }
TEST(CoeffOrderTest,FewSlidesSmall)86 TEST(CoeffOrderTest, FewSlidesSmall) { TestPermutation(kFewSlides, 256); }
TEST(CoeffOrderTest,FewSwapsSmall)87 TEST(CoeffOrderTest, FewSwapsSmall) { TestPermutation(kFewSwaps, 256); }
TEST(CoeffOrderTest,RandomSmall)88 TEST(CoeffOrderTest, RandomSmall) { TestPermutation(kRandom, 256); }
89
TEST(CoeffOrderTest,IdentityMedium)90 TEST(CoeffOrderTest, IdentityMedium) { TestPermutation(kIdentity, 1 << 12); }
TEST(CoeffOrderTest,FewSlidesMedium)91 TEST(CoeffOrderTest, FewSlidesMedium) { TestPermutation(kFewSlides, 1 << 12); }
TEST(CoeffOrderTest,FewSwapsMedium)92 TEST(CoeffOrderTest, FewSwapsMedium) { TestPermutation(kFewSwaps, 1 << 12); }
TEST(CoeffOrderTest,RandomMedium)93 TEST(CoeffOrderTest, RandomMedium) { TestPermutation(kRandom, 1 << 12); }
94
TEST(CoeffOrderTest,IdentityBig)95 TEST(CoeffOrderTest, IdentityBig) { TestPermutation(kIdentity, 1 << 16); }
TEST(CoeffOrderTest,FewSlidesBig)96 TEST(CoeffOrderTest, FewSlidesBig) { TestPermutation(kFewSlides, 1 << 16); }
TEST(CoeffOrderTest,FewSwapsBig)97 TEST(CoeffOrderTest, FewSwapsBig) { TestPermutation(kFewSwaps, 1 << 16); }
TEST(CoeffOrderTest,RandomBig)98 TEST(CoeffOrderTest, RandomBig) { TestPermutation(kRandom, 1 << 16); }
99
100 } // namespace
101 } // namespace jxl
102