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