ac_context.h (6292B)
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_CONTEXT_H_ 7 #define LIB_JXL_AC_CONTEXT_H_ 8 9 #include <algorithm> 10 #include <vector> 11 12 #include "lib/jxl/base/bits.h" 13 #include "lib/jxl/base/status.h" 14 #include "lib/jxl/coeff_order_fwd.h" 15 16 namespace jxl { 17 18 // Block context used for scanning order, number of non-zeros, AC coefficients. 19 // Equal to the channel. 20 constexpr uint32_t kDCTOrderContextStart = 0; 21 22 // The number of predicted nonzeros goes from 0 to 1008. We use 23 // ceil(log2(predicted+1)) as a context for the number of nonzeros, so from 0 to 24 // 10, inclusive. 25 constexpr uint32_t kNonZeroBuckets = 37; 26 27 static const uint16_t kCoeffFreqContext[64] = { 28 0xBAD, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 29 15, 15, 16, 16, 17, 17, 18, 18, 19, 19, 20, 20, 21, 21, 22, 22, 30 23, 23, 23, 23, 24, 24, 24, 24, 25, 25, 25, 25, 26, 26, 26, 26, 31 27, 27, 27, 27, 28, 28, 28, 28, 29, 29, 29, 29, 30, 30, 30, 30, 32 }; 33 34 static const uint16_t kCoeffNumNonzeroContext[64] = { 35 0xBAD, 0, 31, 62, 62, 93, 93, 93, 93, 123, 123, 123, 123, 36 152, 152, 152, 152, 152, 152, 152, 152, 180, 180, 180, 180, 180, 37 180, 180, 180, 180, 180, 180, 180, 206, 206, 206, 206, 206, 206, 38 206, 206, 206, 206, 206, 206, 206, 206, 206, 206, 206, 206, 206, 39 206, 206, 206, 206, 206, 206, 206, 206, 206, 206, 206, 206, 40 }; 41 42 // Supremum of ZeroDensityContext(x, y) + 1, when x + y < 64. 43 constexpr int kZeroDensityContextCount = 458; 44 // Supremum of ZeroDensityContext(x, y) + 1. 45 constexpr int kZeroDensityContextLimit = 474; 46 47 /* This function is used for entropy-sources pre-clustering. 48 * 49 * Ideally, each combination of |nonzeros_left| and |k| should go to its own 50 * bucket; but it implies (64 * 63 / 2) == 2016 buckets. If there is other 51 * dimension (e.g. block context), then number of primary clusters becomes too 52 * big. 53 * 54 * To solve this problem, |nonzeros_left| and |k| values are clustered. It is 55 * known that their sum is at most 64, consequently, the total number buckets 56 * is at most A(64) * B(64). 57 */ 58 // TODO(user): investigate, why disabling pre-clustering makes entropy code 59 // less dense. Perhaps we would need to add HQ clustering algorithm that would 60 // be able to squeeze better by spending more CPU cycles. 61 static JXL_INLINE size_t ZeroDensityContext(size_t nonzeros_left, size_t k, 62 size_t covered_blocks, 63 size_t log2_covered_blocks, 64 size_t prev) { 65 JXL_DASSERT((static_cast<size_t>(1) << log2_covered_blocks) == 66 covered_blocks); 67 nonzeros_left = (nonzeros_left + covered_blocks - 1) >> log2_covered_blocks; 68 k >>= log2_covered_blocks; 69 JXL_DASSERT(k > 0); 70 JXL_DASSERT(k < 64); 71 JXL_DASSERT(nonzeros_left > 0); 72 // Asserting nonzeros_left + k < 65 here causes crashes in debug mode with 73 // invalid input, since the (hot) decoding loop does not check this condition. 74 // As no out-of-bound memory reads are issued even if that condition is 75 // broken, we check this simpler condition which holds anyway. The decoder 76 // will still mark a file in which that condition happens as not valid at the 77 // end of the decoding loop, as `nzeros` will not be `0`. 78 JXL_DASSERT(nonzeros_left < 64); 79 return (kCoeffNumNonzeroContext[nonzeros_left] + kCoeffFreqContext[k]) * 2 + 80 prev; 81 } 82 83 struct BlockCtxMap { 84 std::vector<int> dc_thresholds[3]; 85 std::vector<uint32_t> qf_thresholds; 86 std::vector<uint8_t> ctx_map; 87 size_t num_ctxs, num_dc_ctxs; 88 89 static constexpr uint8_t kDefaultCtxMap[] = { 90 // Default ctx map clusters all the large transforms together. 91 0, 1, 2, 2, 3, 3, 4, 5, 6, 6, 6, 6, 6, // 92 7, 8, 9, 9, 10, 11, 12, 13, 14, 14, 14, 14, 14, // 93 7, 8, 9, 9, 10, 11, 12, 13, 14, 14, 14, 14, 14, // 94 }; 95 static_assert(3 * kNumOrders == 96 sizeof(kDefaultCtxMap) / sizeof *kDefaultCtxMap, 97 "Update default context map"); 98 99 size_t Context(int dc_idx, uint32_t qf, size_t ord, size_t c) const { 100 size_t qf_idx = 0; 101 for (uint32_t t : qf_thresholds) { 102 if (qf > t) qf_idx++; 103 } 104 size_t idx = c < 2 ? c ^ 1 : 2; 105 idx = idx * kNumOrders + ord; 106 idx = idx * (qf_thresholds.size() + 1) + qf_idx; 107 idx = idx * num_dc_ctxs + dc_idx; 108 return ctx_map[idx]; 109 } 110 // Non-zero context is based on number of non-zeros and block context. 111 // For better clustering, contexts with same number of non-zeros are grouped. 112 constexpr uint32_t ZeroDensityContextsOffset(uint32_t block_ctx) const { 113 return static_cast<uint32_t>(num_ctxs * kNonZeroBuckets + 114 kZeroDensityContextCount * block_ctx); 115 } 116 117 // Context map for AC coefficients consists of 2 blocks: 118 // |num_ctxs x : context for number of non-zeros in the block 119 // kNonZeroBuckets| computed from block context and predicted 120 // value (based top and left values) 121 // |num_ctxs x : context for AC coefficient symbols, 122 // kZeroDensityContextCount| computed from block context, 123 // number of non-zeros left and 124 // index in scan order 125 constexpr uint32_t NumACContexts() const { 126 return static_cast<uint32_t>(num_ctxs * 127 (kNonZeroBuckets + kZeroDensityContextCount)); 128 } 129 130 // Non-zero context is based on number of non-zeros and block context. 131 // For better clustering, contexts with same number of non-zeros are grouped. 132 inline uint32_t NonZeroContext(uint32_t non_zeros, uint32_t block_ctx) const { 133 uint32_t ctx; 134 if (non_zeros >= 64) non_zeros = 64; 135 if (non_zeros < 8) { 136 ctx = non_zeros; 137 } else { 138 ctx = 4 + non_zeros / 2; 139 } 140 return static_cast<uint32_t>(ctx * num_ctxs + block_ctx); 141 } 142 143 BlockCtxMap() { 144 ctx_map.assign(std::begin(kDefaultCtxMap), std::end(kDefaultCtxMap)); 145 num_ctxs = *std::max_element(ctx_map.begin(), ctx_map.end()) + 1; 146 num_dc_ctxs = 1; 147 } 148 }; 149 150 } // namespace jxl 151 152 #endif // LIB_JXL_AC_CONTEXT_H_