ac_strategy.h (8961B)
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 #ifndef LIB_JXL_AC_STRATEGY_H_ 7 #define LIB_JXL_AC_STRATEGY_H_ 8 9 #include <stddef.h> 10 #include <stdint.h> 11 12 #include <hwy/base.h> // kMaxVectorSize 13 14 #include "lib/jxl/base/status.h" 15 #include "lib/jxl/coeff_order_fwd.h" 16 #include "lib/jxl/frame_dimensions.h" 17 #include "lib/jxl/image_ops.h" 18 19 // Defines the different kinds of transforms, and heuristics to choose between 20 // them. 21 // `AcStrategy` represents what transform should be used, and which sub-block of 22 // that transform we are currently in. Note that DCT4x4 is applied on all four 23 // 4x4 sub-blocks of an 8x8 block. 24 // `AcStrategyImage` defines which strategy should be used for each 8x8 block 25 // of the image. The highest 4 bits represent the strategy to be used, the 26 // lowest 4 represent the index of the block inside that strategy. 27 28 namespace jxl { 29 30 class AcStrategy { 31 public: 32 // Extremal values for the number of blocks/coefficients of a single strategy. 33 static constexpr size_t kMaxCoeffBlocks = 32; 34 static constexpr size_t kMaxBlockDim = kBlockDim * kMaxCoeffBlocks; 35 // Maximum number of coefficients in a block. Guaranteed to be a multiple of 36 // the vector size. 37 static constexpr size_t kMaxCoeffArea = kMaxBlockDim * kMaxBlockDim; 38 static_assert((kMaxCoeffArea * sizeof(float)) % hwy::kMaxVectorSize == 0, 39 "Coefficient area is not a multiple of vector size"); 40 41 // Raw strategy types. 42 enum Type : uint32_t { 43 // Regular block size DCT 44 DCT = 0, 45 // Encode pixels without transforming 46 IDENTITY = 1, 47 // Use 2-by-2 DCT 48 DCT2X2 = 2, 49 // Use 4-by-4 DCT 50 DCT4X4 = 3, 51 // Use 16-by-16 DCT 52 DCT16X16 = 4, 53 // Use 32-by-32 DCT 54 DCT32X32 = 5, 55 // Use 16-by-8 DCT 56 DCT16X8 = 6, 57 // Use 8-by-16 DCT 58 DCT8X16 = 7, 59 // Use 32-by-8 DCT 60 DCT32X8 = 8, 61 // Use 8-by-32 DCT 62 DCT8X32 = 9, 63 // Use 32-by-16 DCT 64 DCT32X16 = 10, 65 // Use 16-by-32 DCT 66 DCT16X32 = 11, 67 // 4x8 and 8x4 DCT 68 DCT4X8 = 12, 69 DCT8X4 = 13, 70 // Corner-DCT. 71 AFV0 = 14, 72 AFV1 = 15, 73 AFV2 = 16, 74 AFV3 = 17, 75 // Larger DCTs 76 DCT64X64 = 18, 77 DCT64X32 = 19, 78 DCT32X64 = 20, 79 DCT128X128 = 21, 80 DCT128X64 = 22, 81 DCT64X128 = 23, 82 DCT256X256 = 24, 83 DCT256X128 = 25, 84 DCT128X256 = 26, 85 // Marker for num of valid strategies. 86 kNumValidStrategies 87 }; 88 89 static constexpr uint32_t TypeBit(const Type type) { 90 return 1u << static_cast<uint32_t>(type); 91 } 92 93 // Returns true if this block is the first 8x8 block (i.e. top-left) of a 94 // possibly multi-block strategy. 95 JXL_INLINE bool IsFirstBlock() const { return is_first_; } 96 97 JXL_INLINE bool IsMultiblock() const { 98 constexpr uint32_t bits = 99 TypeBit(Type::DCT16X16) | TypeBit(Type::DCT32X32) | 100 TypeBit(Type::DCT16X8) | TypeBit(Type::DCT8X16) | 101 TypeBit(Type::DCT32X8) | TypeBit(Type::DCT8X32) | 102 TypeBit(Type::DCT16X32) | TypeBit(Type::DCT32X16) | 103 TypeBit(Type::DCT32X64) | TypeBit(Type::DCT64X32) | 104 TypeBit(Type::DCT64X64) | TypeBit(DCT64X128) | TypeBit(DCT128X64) | 105 TypeBit(DCT128X128) | TypeBit(DCT128X256) | TypeBit(DCT256X128) | 106 TypeBit(DCT256X256); 107 JXL_DASSERT(Strategy() < kNumValidStrategies); 108 return ((1u << static_cast<uint32_t>(Strategy())) & bits) != 0; 109 } 110 111 // Returns the raw strategy value. Should only be used for tokenization. 112 JXL_INLINE uint8_t RawStrategy() const { 113 return static_cast<uint8_t>(strategy_); 114 } 115 116 JXL_INLINE Type Strategy() const { return strategy_; } 117 118 // Inverse check 119 static JXL_INLINE constexpr bool IsRawStrategyValid(int raw_strategy) { 120 return raw_strategy < static_cast<int32_t>(kNumValidStrategies) && 121 raw_strategy >= 0; 122 } 123 static JXL_INLINE AcStrategy FromRawStrategy(uint8_t raw_strategy) { 124 return FromRawStrategy(static_cast<Type>(raw_strategy)); 125 } 126 static JXL_INLINE AcStrategy FromRawStrategy(Type raw_strategy) { 127 JXL_DASSERT(IsRawStrategyValid(static_cast<uint32_t>(raw_strategy))); 128 return AcStrategy(raw_strategy, /*is_first=*/true); 129 } 130 131 // "Natural order" means the order of increasing of "anisotropic" frequency of 132 // continuous version of DCT basis. 133 // Round-trip, for any given strategy s: 134 // X = NaturalCoeffOrder(s)[NaturalCoeffOrderLutN(s)[X]] 135 // X = NaturalCoeffOrderLut(s)[NaturalCoeffOrderN(s)[X]] 136 void ComputeNaturalCoeffOrder(coeff_order_t* order) const; 137 void ComputeNaturalCoeffOrderLut(coeff_order_t* lut) const; 138 139 // Number of 8x8 blocks that this strategy will cover. 0 for non-top-left 140 // blocks inside a multi-block transform. 141 JXL_INLINE size_t covered_blocks_x() const { 142 static constexpr uint8_t kLut[] = {1, 1, 1, 1, 2, 4, 1, 2, 1, 143 4, 2, 4, 1, 1, 1, 1, 1, 1, 144 8, 4, 8, 16, 8, 16, 32, 16, 32}; 145 static_assert(sizeof(kLut) / sizeof(*kLut) == kNumValidStrategies, 146 "Update LUT"); 147 return kLut[static_cast<size_t>(strategy_)]; 148 } 149 150 JXL_INLINE size_t covered_blocks_y() const { 151 static constexpr uint8_t kLut[] = {1, 1, 1, 1, 2, 4, 2, 1, 4, 152 1, 4, 2, 1, 1, 1, 1, 1, 1, 153 8, 8, 4, 16, 16, 8, 32, 32, 16}; 154 static_assert(sizeof(kLut) / sizeof(*kLut) == kNumValidStrategies, 155 "Update LUT"); 156 return kLut[static_cast<size_t>(strategy_)]; 157 } 158 159 JXL_INLINE size_t log2_covered_blocks() const { 160 static constexpr uint8_t kLut[] = {0, 0, 0, 0, 2, 4, 1, 1, 2, 161 2, 3, 3, 0, 0, 0, 0, 0, 0, 162 6, 5, 5, 8, 7, 7, 10, 9, 9}; 163 static_assert(sizeof(kLut) / sizeof(*kLut) == kNumValidStrategies, 164 "Update LUT"); 165 return kLut[static_cast<size_t>(strategy_)]; 166 } 167 168 private: 169 friend class AcStrategyRow; 170 JXL_INLINE AcStrategy(Type strategy, bool is_first) 171 : strategy_(strategy), is_first_(is_first) { 172 JXL_DASSERT(IsMultiblock() || is_first == true); 173 } 174 175 Type strategy_; 176 bool is_first_; 177 }; 178 179 // Class to use a certain row of the AC strategy. 180 class AcStrategyRow { 181 public: 182 explicit AcStrategyRow(const uint8_t* row) : row_(row) {} 183 AcStrategy operator[](size_t x) const { 184 AcStrategy::Type strategy = static_cast<AcStrategy::Type>(row_[x] >> 1); 185 bool is_first = static_cast<bool>(row_[x] & 1); 186 return AcStrategy(strategy, is_first); 187 } 188 189 private: 190 const uint8_t* JXL_RESTRICT row_; 191 }; 192 193 class AcStrategyImage { 194 public: 195 AcStrategyImage() = default; 196 static StatusOr<AcStrategyImage> Create(size_t xsize, size_t ysize); 197 198 AcStrategyImage(AcStrategyImage&&) = default; 199 AcStrategyImage& operator=(AcStrategyImage&&) = default; 200 201 void FillDCT8(const Rect& rect) { 202 FillPlane<uint8_t>((static_cast<uint8_t>(AcStrategy::Type::DCT) << 1) | 1, 203 &layers_, rect); 204 } 205 void FillDCT8() { FillDCT8(Rect(layers_)); } 206 207 void FillInvalid() { FillImage(INVALID, &layers_); } 208 209 void Set(size_t x, size_t y, AcStrategy::Type type) { 210 #if JXL_ENABLE_ASSERT 211 AcStrategy acs = AcStrategy::FromRawStrategy(type); 212 #endif // JXL_ENABLE_ASSERT 213 JXL_ASSERT(y + acs.covered_blocks_y() <= layers_.ysize()); 214 JXL_ASSERT(x + acs.covered_blocks_x() <= layers_.xsize()); 215 JXL_CHECK(SetNoBoundsCheck(x, y, type, /*check=*/false)); 216 } 217 218 Status SetNoBoundsCheck(size_t x, size_t y, AcStrategy::Type type, 219 bool check = true) { 220 AcStrategy acs = AcStrategy::FromRawStrategy(type); 221 for (size_t iy = 0; iy < acs.covered_blocks_y(); iy++) { 222 for (size_t ix = 0; ix < acs.covered_blocks_x(); ix++) { 223 size_t pos = (y + iy) * stride_ + x + ix; 224 if (check && row_[pos] != INVALID) { 225 return JXL_FAILURE("Invalid AC strategy: block overlap"); 226 } 227 row_[pos] = 228 (static_cast<uint8_t>(type) << 1) | ((iy | ix) == 0 ? 1 : 0); 229 } 230 } 231 return true; 232 } 233 234 bool IsValid(size_t x, size_t y) { return row_[y * stride_ + x] != INVALID; } 235 236 AcStrategyRow ConstRow(size_t y, size_t x_prefix = 0) const { 237 return AcStrategyRow(layers_.ConstRow(y) + x_prefix); 238 } 239 240 AcStrategyRow ConstRow(const Rect& rect, size_t y) const { 241 return ConstRow(rect.y0() + y, rect.x0()); 242 } 243 244 size_t PixelsPerRow() const { return layers_.PixelsPerRow(); } 245 246 size_t xsize() const { return layers_.xsize(); } 247 size_t ysize() const { return layers_.ysize(); } 248 249 // Count the number of blocks of a given type. 250 size_t CountBlocks(AcStrategy::Type type) const; 251 252 private: 253 ImageB layers_; 254 uint8_t* JXL_RESTRICT row_; 255 size_t stride_; 256 257 // A value that does not represent a valid combined AC strategy 258 // value. Used as a sentinel. 259 static constexpr uint8_t INVALID = 0xFF; 260 }; 261 262 } // namespace jxl 263 264 #endif // LIB_JXL_AC_STRATEGY_H_