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