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