/src/libjxl/lib/jxl/ac_strategy.cc
Line | Count | Source (jump to first uncovered line) |
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/ac_strategy.h" |
7 | | |
8 | | #include <jxl/memory_manager.h> |
9 | | |
10 | | #include <algorithm> |
11 | | #include <cstring> |
12 | | #include <utility> |
13 | | |
14 | | #include "lib/jxl/base/bits.h" |
15 | | |
16 | | namespace jxl { |
17 | | |
18 | | // Tries to generalize zig-zag order to non-square blocks. Surprisingly, in |
19 | | // square block frequency along the (i + j == const) diagonals is roughly the |
20 | | // same. For historical reasons, consecutive diagonals are traversed |
21 | | // in alternating directions - so called "zig-zag" (or "snake") order. |
22 | | template <bool is_lut> |
23 | 52 | static void CoeffOrderAndLut(AcStrategy acs, coeff_order_t* out) { |
24 | 52 | size_t cx = acs.covered_blocks_x(); |
25 | 52 | size_t cy = acs.covered_blocks_y(); |
26 | 52 | CoefficientLayout(&cy, &cx); |
27 | | |
28 | | // CoefficientLayout ensures cx >= cy. |
29 | | // We compute the zigzag order for a cx x cx block, then discard all the |
30 | | // lines that are not multiple of the ratio between cx and cy. |
31 | 52 | size_t xs = cx / cy; |
32 | 52 | size_t xsm = xs - 1; |
33 | 52 | size_t xss = CeilLog2Nonzero(xs); |
34 | | // First half of the block |
35 | 52 | size_t cur = cx * cy; |
36 | 468 | for (size_t i = 0; i < cx * kBlockDim; i++) { |
37 | 2.28k | for (size_t j = 0; j <= i; j++) { |
38 | 1.87k | size_t x = j; |
39 | 1.87k | size_t y = i - j; |
40 | 1.87k | if (i % 2) std::swap(x, y); |
41 | 1.87k | if ((y & xsm) != 0) continue; |
42 | 1.87k | y >>= xss; |
43 | 1.87k | size_t val = 0; |
44 | 1.87k | if (x < cx && y < cy) { |
45 | 52 | val = y * cx + x; |
46 | 1.82k | } else { |
47 | 1.82k | val = cur++; |
48 | 1.82k | } |
49 | 1.87k | if (is_lut) { |
50 | 0 | out[y * cx * kBlockDim + x] = val; |
51 | 1.87k | } else { |
52 | 1.87k | out[val] = y * cx * kBlockDim + x; |
53 | 1.87k | } |
54 | 1.87k | } |
55 | 416 | } |
56 | | // Second half |
57 | 416 | for (size_t ip = cx * kBlockDim - 1; ip > 0; ip--) { |
58 | 364 | size_t i = ip - 1; |
59 | 1.82k | for (size_t j = 0; j <= i; j++) { |
60 | 1.45k | size_t x = cx * kBlockDim - 1 - (i - j); |
61 | 1.45k | size_t y = cx * kBlockDim - 1 - j; |
62 | 1.45k | if (i % 2) std::swap(x, y); |
63 | 1.45k | if ((y & xsm) != 0) continue; |
64 | 1.45k | y >>= xss; |
65 | 1.45k | size_t val = cur++; |
66 | 1.45k | if (is_lut) { |
67 | 0 | out[y * cx * kBlockDim + x] = val; |
68 | 1.45k | } else { |
69 | 1.45k | out[val] = y * cx * kBlockDim + x; |
70 | 1.45k | } |
71 | 1.45k | } |
72 | 364 | } |
73 | 52 | } ac_strategy.cc:void jxl::CoeffOrderAndLut<false>(jxl::AcStrategy, unsigned int*) Line | Count | Source | 23 | 52 | static void CoeffOrderAndLut(AcStrategy acs, coeff_order_t* out) { | 24 | 52 | size_t cx = acs.covered_blocks_x(); | 25 | 52 | size_t cy = acs.covered_blocks_y(); | 26 | 52 | CoefficientLayout(&cy, &cx); | 27 | | | 28 | | // CoefficientLayout ensures cx >= cy. | 29 | | // We compute the zigzag order for a cx x cx block, then discard all the | 30 | | // lines that are not multiple of the ratio between cx and cy. | 31 | 52 | size_t xs = cx / cy; | 32 | 52 | size_t xsm = xs - 1; | 33 | 52 | size_t xss = CeilLog2Nonzero(xs); | 34 | | // First half of the block | 35 | 52 | size_t cur = cx * cy; | 36 | 468 | for (size_t i = 0; i < cx * kBlockDim; i++) { | 37 | 2.28k | for (size_t j = 0; j <= i; j++) { | 38 | 1.87k | size_t x = j; | 39 | 1.87k | size_t y = i - j; | 40 | 1.87k | if (i % 2) std::swap(x, y); | 41 | 1.87k | if ((y & xsm) != 0) continue; | 42 | 1.87k | y >>= xss; | 43 | 1.87k | size_t val = 0; | 44 | 1.87k | if (x < cx && y < cy) { | 45 | 52 | val = y * cx + x; | 46 | 1.82k | } else { | 47 | 1.82k | val = cur++; | 48 | 1.82k | } | 49 | 1.87k | if (is_lut) { | 50 | 0 | out[y * cx * kBlockDim + x] = val; | 51 | 1.87k | } else { | 52 | 1.87k | out[val] = y * cx * kBlockDim + x; | 53 | 1.87k | } | 54 | 1.87k | } | 55 | 416 | } | 56 | | // Second half | 57 | 416 | for (size_t ip = cx * kBlockDim - 1; ip > 0; ip--) { | 58 | 364 | size_t i = ip - 1; | 59 | 1.82k | for (size_t j = 0; j <= i; j++) { | 60 | 1.45k | size_t x = cx * kBlockDim - 1 - (i - j); | 61 | 1.45k | size_t y = cx * kBlockDim - 1 - j; | 62 | 1.45k | if (i % 2) std::swap(x, y); | 63 | 1.45k | if ((y & xsm) != 0) continue; | 64 | 1.45k | y >>= xss; | 65 | 1.45k | size_t val = cur++; | 66 | 1.45k | if (is_lut) { | 67 | 0 | out[y * cx * kBlockDim + x] = val; | 68 | 1.45k | } else { | 69 | 1.45k | out[val] = y * cx * kBlockDim + x; | 70 | 1.45k | } | 71 | 1.45k | } | 72 | 364 | } | 73 | 52 | } |
Unexecuted instantiation: ac_strategy.cc:void jxl::CoeffOrderAndLut<true>(jxl::AcStrategy, unsigned int*) |
74 | | |
75 | 52 | void AcStrategy::ComputeNaturalCoeffOrder(coeff_order_t* order) const { |
76 | 52 | CoeffOrderAndLut</*is_lut=*/false>(*this, order); |
77 | 52 | } |
78 | 0 | void AcStrategy::ComputeNaturalCoeffOrderLut(coeff_order_t* lut) const { |
79 | 0 | CoeffOrderAndLut</*is_lut=*/true>(*this, lut); |
80 | 0 | } |
81 | | |
82 | | // These definitions are needed before C++17. |
83 | | constexpr size_t AcStrategy::kMaxCoeffBlocks; |
84 | | constexpr size_t AcStrategy::kMaxBlockDim; |
85 | | constexpr size_t AcStrategy::kMaxCoeffArea; |
86 | | |
87 | | StatusOr<AcStrategyImage> AcStrategyImage::Create( |
88 | 52 | JxlMemoryManager* memory_manager, size_t xsize, size_t ysize) { |
89 | 52 | AcStrategyImage img; |
90 | 52 | JXL_ASSIGN_OR_RETURN(img.layers_, |
91 | 52 | ImageB::Create(memory_manager, xsize, ysize)); |
92 | 52 | img.row_ = img.layers_.Row(0); |
93 | 52 | img.stride_ = img.layers_.PixelsPerRow(); |
94 | 52 | return img; |
95 | 52 | } |
96 | | |
97 | 0 | size_t AcStrategyImage::CountBlocks(AcStrategy::Type type) const { |
98 | 0 | size_t ret = 0; |
99 | 0 | for (size_t y = 0; y < layers_.ysize(); y++) { |
100 | 0 | const uint8_t* JXL_RESTRICT row = layers_.ConstRow(y); |
101 | 0 | for (size_t x = 0; x < layers_.xsize(); x++) { |
102 | 0 | if (row[x] == ((static_cast<uint8_t>(type) << 1) | 1)) ret++; |
103 | 0 | } |
104 | 0 | } |
105 | 0 | return ret; |
106 | 0 | } |
107 | | |
108 | | } // namespace jxl |