| 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/modular/encoding/enc_ma.h" |
| 7 |
|
| 8 |
#include <algorithm> |
| 9 |
#include <cstdlib> |
| 10 |
#include <limits> |
| 11 |
#include <numeric> |
| 12 |
#include <queue> |
| 13 |
#include <vector> |
| 14 |
|
| 15 |
#include "lib/jxl/modular/encoding/ma_common.h" |
| 16 |
|
| 17 |
#undef HWY_TARGET_INCLUDE |
| 18 |
#define HWY_TARGET_INCLUDE "lib/jxl/modular/encoding/enc_ma.cc" |
| 19 |
#include <hwy/foreach_target.h> |
| 20 |
#include <hwy/highway.h> |
| 21 |
|
| 22 |
#include "lib/jxl/base/fast_math-inl.h" |
| 23 |
#include "lib/jxl/base/random.h" |
| 24 |
#include "lib/jxl/enc_ans.h" |
| 25 |
#include "lib/jxl/modular/encoding/context_predict.h" |
| 26 |
#include "lib/jxl/modular/options.h" |
| 27 |
#include "lib/jxl/pack_signed.h" |
| 28 |
HWY_BEFORE_NAMESPACE(); |
| 29 |
namespace jxl { |
| 30 |
namespace HWY_NAMESPACE { |
| 31 |
|
| 32 |
// These templates are not found via ADL. |
| 33 |
using hwy::HWY_NAMESPACE::Eq; |
| 34 |
using hwy::HWY_NAMESPACE::IfThenElse; |
| 35 |
using hwy::HWY_NAMESPACE::Lt; |
| 36 |
using hwy::HWY_NAMESPACE::Max; |
| 37 |
|
| 38 |
const HWY_FULL(float) df; |
| 39 |
const HWY_FULL(int32_t) di; |
| 40 |
size_t Padded(size_t x) { return RoundUpTo(x, Lanes(df)); } |
| 41 |
|
| 42 |
// Compute entropy of the histogram, taking into account the minimum probability |
| 43 |
// for symbols with non-zero counts. |
| 44 |
float EstimateBits(const int32_t *counts, size_t num_symbols) { |
| 45 |
int32_t total = std::accumulate(counts, counts + num_symbols, 0); |
| 46 |
const auto zero = Zero(df); |
| 47 |
const auto minprob = Set(df, 1.0f / ANS_TAB_SIZE); |
| 48 |
const auto inv_total = Set(df, 1.0f / total); |
| 49 |
auto bits_lanes = Zero(df); |
| 50 |
auto total_v = Set(di, total); |
| 51 |
for (size_t i = 0; i < num_symbols; i += Lanes(df)) { |
| 52 |
const auto counts_iv = LoadU(di, &counts[i]); |
| 53 |
const auto counts_fv = ConvertTo(df, counts_iv); |
| 54 |
const auto probs = Mul(counts_fv, inv_total); |
| 55 |
const auto mprobs = Max(probs, minprob); |
| 56 |
const auto nbps = IfThenElse(Eq(counts_iv, total_v), BitCast(di, zero), |
| 57 |
BitCast(di, FastLog2f(df, mprobs))); |
| 58 |
bits_lanes = Sub(bits_lanes, Mul(counts_fv, BitCast(df, nbps))); |
| 59 |
} |
| 60 |
return GetLane(SumOfLanes(df, bits_lanes)); |
| 61 |
} |
| 62 |
|
| 63 |
void MakeSplitNode(size_t pos, int property, int splitval, Predictor lpred, |
| 64 |
int64_t loff, Predictor rpred, int64_t roff, Tree *tree) { |
| 65 |
// Note that the tree splits on *strictly greater*. |
| 66 |
(*tree)[pos].lchild = tree->size(); |
| 67 |
(*tree)[pos].rchild = tree->size() + 1; |
| 68 |
(*tree)[pos].splitval = splitval; |
| 69 |
(*tree)[pos].property = property; |
| 70 |
tree->emplace_back(); |
| 71 |
tree->back().property = -1; |
| 72 |
tree->back().predictor = rpred; |
| 73 |
tree->back().predictor_offset = roff; |
| 74 |
tree->back().multiplier = 1; |
| 75 |
tree->emplace_back(); |
| 76 |
tree->back().property = -1; |
| 77 |
tree->back().predictor = lpred; |
| 78 |
tree->back().predictor_offset = loff; |
| 79 |
tree->back().multiplier = 1; |
| 80 |
} |
| 81 |
|
| 82 |
enum class IntersectionType { kNone, kPartial, kInside }; |
| 83 |
IntersectionType BoxIntersects(StaticPropRange needle, StaticPropRange haystack, |
| 84 |
uint32_t &partial_axis, uint32_t &partial_val) { |
| 85 |
bool partial = false; |
| 86 |
for (size_t i = 0; i < kNumStaticProperties; i++) { |
| 87 |
if (haystack[i][0] >= needle[i][1]) { |
| 88 |
return IntersectionType::kNone; |
| 89 |
} |
| 90 |
if (haystack[i][1] <= needle[i][0]) { |
| 91 |
return IntersectionType::kNone; |
| 92 |
} |
| 93 |
if (haystack[i][0] <= needle[i][0] && haystack[i][1] >= needle[i][1]) { |
| 94 |
continue; |
| 95 |
} |
| 96 |
partial = true; |
| 97 |
partial_axis = i; |
| 98 |
if (haystack[i][0] > needle[i][0] && haystack[i][0] < needle[i][1]) { |
| 99 |
partial_val = haystack[i][0] - 1; |
| 100 |
} else { |
| 101 |
JXL_DASSERT(haystack[i][1] > needle[i][0] && |
| 102 |
haystack[i][1] < needle[i][1]); |
| 103 |
partial_val = haystack[i][1] - 1; |
| 104 |
} |
| 105 |
} |
| 106 |
return partial ? IntersectionType::kPartial : IntersectionType::kInside; |
| 107 |
} |
| 108 |
|
| 109 |
void SplitTreeSamples(TreeSamples &tree_samples, size_t begin, size_t pos, |
| 110 |
size_t end, size_t prop) { |
| 111 |
auto cmp = [&](size_t a, size_t b) { |
| 112 |
return static_cast<int32_t>(tree_samples.Property(prop, a)) - |
| 113 |
static_cast<int32_t>(tree_samples.Property(prop, b)); |
| 114 |
}; |
| 115 |
Rng rng(0); |
| 116 |
while (end > begin + 1) { |
| 117 |
{ |
| 118 |
size_t pivot = rng.UniformU(begin, end); |
| 119 |
tree_samples.Swap(begin, pivot); |
| 120 |
} |
| 121 |
size_t pivot_begin = begin; |
| 122 |
size_t pivot_end = pivot_begin + 1; |
| 123 |
for (size_t i = begin + 1; i < end; i++) { |
| 124 |
JXL_DASSERT(i >= pivot_end); |
| 125 |
JXL_DASSERT(pivot_end > pivot_begin); |
| 126 |
int32_t cmp_result = cmp(i, pivot_begin); |
| 127 |
if (cmp_result < 0) { // i < pivot, move pivot forward and put i before |
| 128 |
// the pivot. |
| 129 |
tree_samples.ThreeShuffle(pivot_begin, pivot_end, i); |
| 130 |
pivot_begin++; |
| 131 |
pivot_end++; |
| 132 |
} else if (cmp_result == 0) { |
| 133 |
tree_samples.Swap(pivot_end, i); |
| 134 |
pivot_end++; |
| 135 |
} |
| 136 |
} |
| 137 |
JXL_DASSERT(pivot_begin >= begin); |
| 138 |
JXL_DASSERT(pivot_end > pivot_begin); |
| 139 |
JXL_DASSERT(pivot_end <= end); |
| 140 |
for (size_t i = begin; i < pivot_begin; i++) { |
| 141 |
JXL_DASSERT(cmp(i, pivot_begin) < 0); |
| 142 |
} |
| 143 |
for (size_t i = pivot_end; i < end; i++) { |
| 144 |
JXL_DASSERT(cmp(i, pivot_begin) > 0); |
| 145 |
} |
| 146 |
for (size_t i = pivot_begin; i < pivot_end; i++) { |
| 147 |
JXL_DASSERT(cmp(i, pivot_begin) == 0); |
| 148 |
} |
| 149 |
// We now have that [begin, pivot_begin) is < pivot, [pivot_begin, |
| 150 |
// pivot_end) is = pivot, and [pivot_end, end) is > pivot. |
| 151 |
// If pos falls in the first or the last interval, we continue in that |
| 152 |
// interval; otherwise, we are done. |
| 153 |
if (pivot_begin > pos) { |
| 154 |
end = pivot_begin; |
| 155 |
} else if (pivot_end < pos) { |
| 156 |
begin = pivot_end; |
| 157 |
} else { |
| 158 |
break; |
| 159 |
} |
| 160 |
} |
| 161 |
} |
| 162 |
|
| 163 |
void FindBestSplit(TreeSamples &tree_samples, float threshold, |
| 164 |
const std::vector<ModularMultiplierInfo> &mul_info, |
| 165 |
StaticPropRange initial_static_prop_range, |
| 166 |
float fast_decode_multiplier, Tree *tree) { |
| 167 |
struct NodeInfo { |
| 168 |
size_t pos; |
| 169 |
size_t begin; |
| 170 |
size_t end; |
| 171 |
uint64_t used_properties; |
| 172 |
StaticPropRange static_prop_range; |
| 173 |
}; |
| 174 |
std::vector<NodeInfo> nodes; |
| 175 |
nodes.push_back(NodeInfo{0, 0, tree_samples.NumDistinctSamples(), 0, |
| 176 |
initial_static_prop_range}); |
| 177 |
|
| 178 |
size_t num_predictors = tree_samples.NumPredictors(); |
| 179 |
size_t num_properties = tree_samples.NumProperties(); |
| 180 |
|
| 181 |
// TODO(veluca): consider parallelizing the search (processing multiple nodes |
| 182 |
// at a time). |
| 183 |
while (!nodes.empty()) { |
| 184 |
size_t pos = nodes.back().pos; |
| 185 |
size_t begin = nodes.back().begin; |
| 186 |
size_t end = nodes.back().end; |
| 187 |
uint64_t used_properties = nodes.back().used_properties; |
| 188 |
StaticPropRange static_prop_range = nodes.back().static_prop_range; |
| 189 |
nodes.pop_back(); |
| 190 |
if (begin == end) continue; |
| 191 |
|
| 192 |
struct SplitInfo { |
| 193 |
size_t prop = 0; |
| 194 |
uint32_t val = 0; |
| 195 |
size_t pos = 0; |
| 196 |
float lcost = std::numeric_limits<float>::max(); |
| 197 |
float rcost = std::numeric_limits<float>::max(); |
| 198 |
Predictor lpred = Predictor::Zero; |
| 199 |
Predictor rpred = Predictor::Zero; |
| 200 |
float Cost() const { return lcost + rcost; } |
| 201 |
}; |
| 202 |
|
| 203 |
SplitInfo best_split_static_constant; |
| 204 |
SplitInfo best_split_static; |
| 205 |
SplitInfo best_split_nonstatic; |
| 206 |
SplitInfo best_split_nowp; |
| 207 |
|
| 208 |
JXL_DASSERT(begin <= end); |
| 209 |
JXL_DASSERT(end <= tree_samples.NumDistinctSamples()); |
| 210 |
|
| 211 |
// Compute the maximum token in the range. |
| 212 |
size_t max_symbols = 0; |
| 213 |
for (size_t pred = 0; pred < num_predictors; pred++) { |
| 214 |
for (size_t i = begin; i < end; i++) { |
| 215 |
uint32_t tok = tree_samples.Token(pred, i); |
| 216 |
max_symbols = max_symbols > tok + 1 ? max_symbols : tok + 1; |
| 217 |
} |
| 218 |
} |
| 219 |
max_symbols = Padded(max_symbols); |
| 220 |
std::vector<int32_t> counts(max_symbols * num_predictors); |
| 221 |
std::vector<uint32_t> tot_extra_bits(num_predictors); |
| 222 |
for (size_t pred = 0; pred < num_predictors; pred++) { |
| 223 |
for (size_t i = begin; i < end; i++) { |
| 224 |
counts[pred * max_symbols + tree_samples.Token(pred, i)] += |
| 225 |
tree_samples.Count(i); |
| 226 |
tot_extra_bits[pred] += |
| 227 |
tree_samples.NBits(pred, i) * tree_samples.Count(i); |
| 228 |
} |
| 229 |
} |
| 230 |
|
| 231 |
float base_bits; |
| 232 |
{ |
| 233 |
size_t pred = tree_samples.PredictorIndex((*tree)[pos].predictor); |
| 234 |
base_bits = |
| 235 |
EstimateBits(counts.data() + pred * max_symbols, max_symbols) + |
| 236 |
tot_extra_bits[pred]; |
| 237 |
} |
| 238 |
|
| 239 |
SplitInfo *best = &best_split_nonstatic; |
| 240 |
|
| 241 |
SplitInfo forced_split; |
| 242 |
// The multiplier ranges cut halfway through the current ranges of static |
| 243 |
// properties. We do this even if the current node is not a leaf, to |
| 244 |
// minimize the number of nodes in the resulting tree. |
| 245 |
for (const auto &mmi : mul_info) { |
| 246 |
uint32_t axis; |
| 247 |
uint32_t val; |
| 248 |
IntersectionType t = |
| 249 |
BoxIntersects(static_prop_range, mmi.range, axis, val); |
| 250 |
if (t == IntersectionType::kNone) continue; |
| 251 |
if (t == IntersectionType::kInside) { |
| 252 |
(*tree)[pos].multiplier = mmi.multiplier; |
| 253 |
break; |
| 254 |
} |
| 255 |
if (t == IntersectionType::kPartial) { |
| 256 |
forced_split.val = tree_samples.QuantizeProperty(axis, val); |
| 257 |
forced_split.prop = axis; |
| 258 |
forced_split.lcost = forced_split.rcost = base_bits / 2 - threshold; |
| 259 |
forced_split.lpred = forced_split.rpred = (*tree)[pos].predictor; |
| 260 |
best = &forced_split; |
| 261 |
best->pos = begin; |
| 262 |
JXL_DASSERT(best->prop == tree_samples.PropertyFromIndex(best->prop)); |
| 263 |
for (size_t x = begin; x < end; x++) { |
| 264 |
if (tree_samples.Property(best->prop, x) <= best->val) { |
| 265 |
best->pos++; |
| 266 |
} |
| 267 |
} |
| 268 |
break; |
| 269 |
} |
| 270 |
} |
| 271 |
|
| 272 |
if (best != &forced_split) { |
| 273 |
std::vector<int> prop_value_used_count; |
| 274 |
std::vector<int> count_increase; |
| 275 |
std::vector<size_t> extra_bits_increase; |
| 276 |
// For each property, compute which of its values are used, and what |
| 277 |
// tokens correspond to those usages. Then, iterate through the values, |
| 278 |
// and compute the entropy of each side of the split (of the form `prop > |
| 279 |
// threshold`). Finally, find the split that minimizes the cost. |
| 280 |
struct CostInfo { |
| 281 |
float cost = std::numeric_limits<float>::max(); |
| 282 |
float extra_cost = 0; |
| 283 |
float Cost() const { return cost + extra_cost; } |
| 284 |
Predictor pred; // will be uninitialized in some cases, but never used. |
| 285 |
}; |
| 286 |
std::vector<CostInfo> costs_l; |
| 287 |
std::vector<CostInfo> costs_r; |
| 288 |
|
| 289 |
std::vector<int32_t> counts_above(max_symbols); |
| 290 |
std::vector<int32_t> counts_below(max_symbols); |
| 291 |
|
| 292 |
// The lower the threshold, the higher the expected noisiness of the |
| 293 |
// estimate. Thus, discourage changing predictors. |
| 294 |
float change_pred_penalty = 800.0f / (100.0f + threshold); |
| 295 |
for (size_t prop = 0; prop < num_properties && base_bits > threshold; |
| 296 |
prop++) { |
| 297 |
costs_l.clear(); |
| 298 |
costs_r.clear(); |
| 299 |
size_t prop_size = tree_samples.NumPropertyValues(prop); |
| 300 |
if (extra_bits_increase.size() < prop_size) { |
| 301 |
count_increase.resize(prop_size * max_symbols); |
| 302 |
extra_bits_increase.resize(prop_size); |
| 303 |
} |
| 304 |
// Clear prop_value_used_count (which cannot be cleared "on the go") |
| 305 |
prop_value_used_count.clear(); |
| 306 |
prop_value_used_count.resize(prop_size); |
| 307 |
|
| 308 |
size_t first_used = prop_size; |
| 309 |
size_t last_used = 0; |
| 310 |
|
| 311 |
// TODO(veluca): consider finding multiple splits along a single |
| 312 |
// property at the same time, possibly with a bottom-up approach. |
| 313 |
for (size_t i = begin; i < end; i++) { |
| 314 |
size_t p = tree_samples.Property(prop, i); |
| 315 |
prop_value_used_count[p]++; |
| 316 |
last_used = std::max(last_used, p); |
| 317 |
first_used = std::min(first_used, p); |
| 318 |
} |
| 319 |
costs_l.resize(last_used - first_used); |
| 320 |
costs_r.resize(last_used - first_used); |
| 321 |
// For all predictors, compute the right and left costs of each split. |
| 322 |
for (size_t pred = 0; pred < num_predictors; pred++) { |
| 323 |
// Compute cost and histogram increments for each property value. |
| 324 |
for (size_t i = begin; i < end; i++) { |
| 325 |
size_t p = tree_samples.Property(prop, i); |
| 326 |
size_t cnt = tree_samples.Count(i); |
| 327 |
size_t sym = tree_samples.Token(pred, i); |
| 328 |
count_increase[p * max_symbols + sym] += cnt; |
| 329 |
extra_bits_increase[p] += tree_samples.NBits(pred, i) * cnt; |
| 330 |
} |
| 331 |
memcpy(counts_above.data(), counts.data() + pred * max_symbols, |
| 332 |
max_symbols * sizeof counts_above[0]); |
| 333 |
memset(counts_below.data(), 0, max_symbols * sizeof counts_below[0]); |
| 334 |
size_t extra_bits_below = 0; |
| 335 |
// Exclude last used: this ensures neither counts_above nor |
| 336 |
// counts_below is empty. |
| 337 |
for (size_t i = first_used; i < last_used; i++) { |
| 338 |
if (!prop_value_used_count[i]) continue; |
| 339 |
extra_bits_below += extra_bits_increase[i]; |
| 340 |
// The increase for this property value has been used, and will not |
| 341 |
// be used again: clear it. Also below. |
| 342 |
extra_bits_increase[i] = 0; |
| 343 |
for (size_t sym = 0; sym < max_symbols; sym++) { |
| 344 |
counts_above[sym] -= count_increase[i * max_symbols + sym]; |
| 345 |
counts_below[sym] += count_increase[i * max_symbols + sym]; |
| 346 |
count_increase[i * max_symbols + sym] = 0; |
| 347 |
} |
| 348 |
float rcost = EstimateBits(counts_above.data(), max_symbols) + |
| 349 |
tot_extra_bits[pred] - extra_bits_below; |
| 350 |
float lcost = EstimateBits(counts_below.data(), max_symbols) + |
| 351 |
extra_bits_below; |
| 352 |
JXL_DASSERT(extra_bits_below <= tot_extra_bits[pred]); |
| 353 |
float penalty = 0; |
| 354 |
// Never discourage moving away from the Weighted predictor. |
| 355 |
if (tree_samples.PredictorFromIndex(pred) != |
| 356 |
(*tree)[pos].predictor && |
| 357 |
(*tree)[pos].predictor != Predictor::Weighted) { |
| 358 |
penalty = change_pred_penalty; |
| 359 |
} |
| 360 |
// If everything else is equal, disfavour Weighted (slower) and |
| 361 |
// favour Zero (faster if it's the only predictor used in a |
| 362 |
// group+channel combination) |
| 363 |
if (tree_samples.PredictorFromIndex(pred) == Predictor::Weighted) { |
| 364 |
penalty += 1e-8; |
| 365 |
} |
| 366 |
if (tree_samples.PredictorFromIndex(pred) == Predictor::Zero) { |
| 367 |
penalty -= 1e-8; |
| 368 |
} |
| 369 |
if (rcost + penalty < costs_r[i - first_used].Cost()) { |
| 370 |
costs_r[i - first_used].cost = rcost; |
| 371 |
costs_r[i - first_used].extra_cost = penalty; |
| 372 |
costs_r[i - first_used].pred = |
| 373 |
tree_samples.PredictorFromIndex(pred); |
| 374 |
} |
| 375 |
if (lcost + penalty < costs_l[i - first_used].Cost()) { |
| 376 |
costs_l[i - first_used].cost = lcost; |
| 377 |
costs_l[i - first_used].extra_cost = penalty; |
| 378 |
costs_l[i - first_used].pred = |
| 379 |
tree_samples.PredictorFromIndex(pred); |
| 380 |
} |
| 381 |
} |
| 382 |
} |
| 383 |
// Iterate through the possible splits and find the one with minimum sum |
| 384 |
// of costs of the two sides. |
| 385 |
size_t split = begin; |
| 386 |
for (size_t i = first_used; i < last_used; i++) { |
| 387 |
if (!prop_value_used_count[i]) continue; |
| 388 |
split += prop_value_used_count[i]; |
| 389 |
float rcost = costs_r[i - first_used].cost; |
| 390 |
float lcost = costs_l[i - first_used].cost; |
| 391 |
// WP was not used + we would use the WP property or predictor |
| 392 |
bool adds_wp = |
| 393 |
(tree_samples.PropertyFromIndex(prop) == kWPProp && |
| 394 |
(used_properties & (1LU << prop)) == 0) || |
| 395 |
((costs_l[i - first_used].pred == Predictor::Weighted || |
| 396 |
costs_r[i - first_used].pred == Predictor::Weighted) && |
| 397 |
(*tree)[pos].predictor != Predictor::Weighted); |
| 398 |
bool zero_entropy_side = rcost == 0 || lcost == 0; |
| 399 |
|
| 400 |
SplitInfo &best = |
| 401 |
prop < kNumStaticProperties |
| 402 |
? (zero_entropy_side ? best_split_static_constant |
| 403 |
: best_split_static) |
| 404 |
: (adds_wp ? best_split_nonstatic : best_split_nowp); |
| 405 |
if (lcost + rcost < best.Cost()) { |
| 406 |
best.prop = prop; |
| 407 |
best.val = i; |
| 408 |
best.pos = split; |
| 409 |
best.lcost = lcost; |
| 410 |
best.lpred = costs_l[i - first_used].pred; |
| 411 |
best.rcost = rcost; |
| 412 |
best.rpred = costs_r[i - first_used].pred; |
| 413 |
} |
| 414 |
} |
| 415 |
// Clear extra_bits_increase and cost_increase for last_used. |
| 416 |
extra_bits_increase[last_used] = 0; |
| 417 |
for (size_t sym = 0; sym < max_symbols; sym++) { |
| 418 |
count_increase[last_used * max_symbols + sym] = 0; |
| 419 |
} |
| 420 |
} |
| 421 |
|
| 422 |
// Try to avoid introducing WP. |
| 423 |
if (best_split_nowp.Cost() + threshold < base_bits && |
| 424 |
best_split_nowp.Cost() <= fast_decode_multiplier * best->Cost()) { |
| 425 |
best = &best_split_nowp; |
| 426 |
} |
| 427 |
// Split along static props if possible and not significantly more |
| 428 |
// expensive. |
| 429 |
if (best_split_static.Cost() + threshold < base_bits && |
| 430 |
best_split_static.Cost() <= fast_decode_multiplier * best->Cost()) { |
| 431 |
best = &best_split_static; |
| 432 |
} |
| 433 |
// Split along static props to create constant nodes if possible. |
| 434 |
if (best_split_static_constant.Cost() + threshold < base_bits) { |
| 435 |
best = &best_split_static_constant; |
| 436 |
} |
| 437 |
} |
| 438 |
|
| 439 |
if (best->Cost() + threshold < base_bits) { |
| 440 |
uint32_t p = tree_samples.PropertyFromIndex(best->prop); |
| 441 |
pixel_type dequant = |
| 442 |
tree_samples.UnquantizeProperty(best->prop, best->val); |
| 443 |
// Split node and try to split children. |
| 444 |
MakeSplitNode(pos, p, dequant, best->lpred, 0, best->rpred, 0, tree); |
| 445 |
// "Sort" according to winning property |
| 446 |
SplitTreeSamples(tree_samples, begin, best->pos, end, best->prop); |
| 447 |
if (p >= kNumStaticProperties) { |
| 448 |
used_properties |= 1 << best->prop; |
| 449 |
} |
| 450 |
auto new_sp_range = static_prop_range; |
| 451 |
if (p < kNumStaticProperties) { |
| 452 |
JXL_DASSERT(static_cast<uint32_t>(dequant + 1) <= new_sp_range[p][1]); |
| 453 |
new_sp_range[p][1] = dequant + 1; |
| 454 |
JXL_DASSERT(new_sp_range[p][0] < new_sp_range[p][1]); |
| 455 |
} |
| 456 |
nodes.push_back(NodeInfo{(*tree)[pos].rchild, begin, best->pos, |
| 457 |
used_properties, new_sp_range}); |
| 458 |
new_sp_range = static_prop_range; |
| 459 |
if (p < kNumStaticProperties) { |
| 460 |
JXL_DASSERT(new_sp_range[p][0] <= static_cast<uint32_t>(dequant + 1)); |
| 461 |
new_sp_range[p][0] = dequant + 1; |
| 462 |
JXL_DASSERT(new_sp_range[p][0] < new_sp_range[p][1]); |
| 463 |
} |
| 464 |
nodes.push_back(NodeInfo{(*tree)[pos].lchild, best->pos, end, |
| 465 |
used_properties, new_sp_range}); |
| 466 |
} |
| 467 |
} |
| 468 |
} |
| 469 |
|
| 470 |
// NOLINTNEXTLINE(google-readability-namespace-comments) |
| 471 |
} // namespace HWY_NAMESPACE |
| 472 |
} // namespace jxl |
| 473 |
HWY_AFTER_NAMESPACE(); |
| 474 |
|
| 475 |
#if HWY_ONCE |
| 476 |
namespace jxl { |
| 477 |
|
| 478 |
HWY_EXPORT(FindBestSplit); // Local function. |
| 479 |
|
| 480 |
Status ComputeBestTree(TreeSamples &tree_samples, float threshold, |
| 481 |
const std::vector<ModularMultiplierInfo> &mul_info, |
| 482 |
StaticPropRange static_prop_range, |
| 483 |
float fast_decode_multiplier, Tree *tree) { |
| 484 |
// TODO(veluca): take into account that different contexts can have different |
| 485 |
// uint configs. |
| 486 |
// |
| 487 |
// Initialize tree. |
| 488 |
tree->emplace_back(); |
| 489 |
tree->back().property = -1; |
| 490 |
tree->back().predictor = tree_samples.PredictorFromIndex(0); |
| 491 |
tree->back().predictor_offset = 0; |
| 492 |
tree->back().multiplier = 1; |
| 493 |
JXL_ENSURE(tree_samples.NumProperties() < 64); |
| 494 |
|
| 495 |
JXL_ENSURE(tree_samples.NumDistinctSamples() <= |
| 496 |
std::numeric_limits<uint32_t>::max()); |
| 497 |
HWY_DYNAMIC_DISPATCH(FindBestSplit) |
| 498 |
(tree_samples, threshold, mul_info, static_prop_range, fast_decode_multiplier, |
| 499 |
tree); |
| 500 |
return true; |
| 501 |
} |
| 502 |
|
| 503 |
#if JXL_CXX_LANG < JXL_CXX_17 |
| 504 |
constexpr int32_t TreeSamples::kPropertyRange; |
| 505 |
constexpr uint32_t TreeSamples::kDedupEntryUnused; |
| 506 |
#endif |
| 507 |
|
| 508 |
Status TreeSamples::SetPredictor(Predictor predictor, |
| 509 |
ModularOptions::TreeMode wp_tree_mode) { |
| 510 |
if (wp_tree_mode == ModularOptions::TreeMode::kWPOnly) { |
| 511 |
predictors = {Predictor::Weighted}; |
| 512 |
residuals.resize(1); |
| 513 |
return true; |
| 514 |
} |
| 515 |
if (wp_tree_mode == ModularOptions::TreeMode::kNoWP && |
| 516 |
predictor == Predictor::Weighted) { |
| 517 |
return JXL_FAILURE("Invalid predictor settings"); |
| 518 |
} |
| 519 |
if (predictor == Predictor::Variable) { |
| 520 |
for (size_t i = 0; i < kNumModularPredictors; i++) { |
| 521 |
predictors.push_back(static_cast<Predictor>(i)); |
| 522 |
} |
| 523 |
std::swap(predictors[0], predictors[static_cast<int>(Predictor::Weighted)]); |
| 524 |
std::swap(predictors[1], predictors[static_cast<int>(Predictor::Gradient)]); |
| 525 |
} else if (predictor == Predictor::Best) { |
| 526 |
predictors = {Predictor::Weighted, Predictor::Gradient}; |
| 527 |
} else { |
| 528 |
predictors = {predictor}; |
| 529 |
} |
| 530 |
if (wp_tree_mode == ModularOptions::TreeMode::kNoWP) { |
| 531 |
auto wp_it = |
| 532 |
std::find(predictors.begin(), predictors.end(), Predictor::Weighted); |
| 533 |
if (wp_it != predictors.end()) { |
| 534 |
predictors.erase(wp_it); |
| 535 |
} |
| 536 |
} |
| 537 |
residuals.resize(predictors.size()); |
| 538 |
return true; |
| 539 |
} |
| 540 |
|
| 541 |
Status TreeSamples::SetProperties(const std::vector<uint32_t> &properties, |
| 542 |
ModularOptions::TreeMode wp_tree_mode) { |
| 543 |
props_to_use = properties; |
| 544 |
if (wp_tree_mode == ModularOptions::TreeMode::kWPOnly) { |
| 545 |
props_to_use = {static_cast<uint32_t>(kWPProp)}; |
| 546 |
} |
| 547 |
if (wp_tree_mode == ModularOptions::TreeMode::kGradientOnly) { |
| 548 |
props_to_use = {static_cast<uint32_t>(kGradientProp)}; |
| 549 |
} |
| 550 |
if (wp_tree_mode == ModularOptions::TreeMode::kNoWP) { |
| 551 |
auto it = std::find(props_to_use.begin(), props_to_use.end(), kWPProp); |
| 552 |
if (it != props_to_use.end()) { |
| 553 |
props_to_use.erase(it); |
| 554 |
} |
| 555 |
} |
| 556 |
if (props_to_use.empty()) { |
| 557 |
return JXL_FAILURE("Invalid property set configuration"); |
| 558 |
} |
| 559 |
props.resize(props_to_use.size()); |
| 560 |
return true; |
| 561 |
} |
| 562 |
|
| 563 |
void TreeSamples::InitTable(size_t log_size) { |
| 564 |
size_t size = 1ULL << log_size; |
| 565 |
if (dedup_table_.size() == size) return; |
| 566 |
dedup_table_.resize(size, kDedupEntryUnused); |
| 567 |
for (size_t i = 0; i < NumDistinctSamples(); i++) { |
| 568 |
if (sample_counts[i] != std::numeric_limits<uint16_t>::max()) { |
| 569 |
AddToTable(i); |
| 570 |
} |
| 571 |
} |
| 572 |
} |
| 573 |
|
| 574 |
bool TreeSamples::AddToTableAndMerge(size_t a) { |
| 575 |
size_t pos1 = Hash1(a); |
| 576 |
size_t pos2 = Hash2(a); |
| 577 |
if (dedup_table_[pos1] != kDedupEntryUnused && |
| 578 |
IsSameSample(a, dedup_table_[pos1])) { |
| 579 |
JXL_DASSERT(sample_counts[a] == 1); |
| 580 |
sample_counts[dedup_table_[pos1]]++; |
| 581 |
// Remove from hash table samples that are saturated. |
| 582 |
if (sample_counts[dedup_table_[pos1]] == |
| 583 |
std::numeric_limits<uint16_t>::max()) { |
| 584 |
dedup_table_[pos1] = kDedupEntryUnused; |
| 585 |
} |
| 586 |
return true; |
| 587 |
} |
| 588 |
if (dedup_table_[pos2] != kDedupEntryUnused && |
| 589 |
IsSameSample(a, dedup_table_[pos2])) { |
| 590 |
JXL_DASSERT(sample_counts[a] == 1); |
| 591 |
sample_counts[dedup_table_[pos2]]++; |
| 592 |
// Remove from hash table samples that are saturated. |
| 593 |
if (sample_counts[dedup_table_[pos2]] == |
| 594 |
std::numeric_limits<uint16_t>::max()) { |
| 595 |
dedup_table_[pos2] = kDedupEntryUnused; |
| 596 |
} |
| 597 |
return true; |
| 598 |
} |
| 599 |
AddToTable(a); |
| 600 |
return false; |
| 601 |
} |
| 602 |
|
| 603 |
void TreeSamples::AddToTable(size_t a) { |
| 604 |
size_t pos1 = Hash1(a); |
| 605 |
size_t pos2 = Hash2(a); |
| 606 |
if (dedup_table_[pos1] == kDedupEntryUnused) { |
| 607 |
dedup_table_[pos1] = a; |
| 608 |
} else if (dedup_table_[pos2] == kDedupEntryUnused) { |
| 609 |
dedup_table_[pos2] = a; |
| 610 |
} |
| 611 |
} |
| 612 |
|
| 613 |
void TreeSamples::PrepareForSamples(size_t num_samples) { |
| 614 |
for (auto &res : residuals) { |
| 615 |
res.reserve(res.size() + num_samples); |
| 616 |
} |
| 617 |
for (auto &p : props) { |
| 618 |
p.reserve(p.size() + num_samples); |
| 619 |
} |
| 620 |
size_t total_num_samples = num_samples + sample_counts.size(); |
| 621 |
size_t next_size = CeilLog2Nonzero(total_num_samples * 3 / 2); |
| 622 |
InitTable(next_size); |
| 623 |
} |
| 624 |
|
| 625 |
size_t TreeSamples::Hash1(size_t a) const { |
| 626 |
constexpr uint64_t constant = 0x1e35a7bd; |
| 627 |
uint64_t h = constant; |
| 628 |
for (const auto &r : residuals) { |
| 629 |
h = h * constant + r[a].tok; |
| 630 |
h = h * constant + r[a].nbits; |
| 631 |
} |
| 632 |
for (const auto &p : props) { |
| 633 |
h = h * constant + p[a]; |
| 634 |
} |
| 635 |
return (h >> 16) & (dedup_table_.size() - 1); |
| 636 |
} |
| 637 |
size_t TreeSamples::Hash2(size_t a) const { |
| 638 |
constexpr uint64_t constant = 0x1e35a7bd1e35a7bd; |
| 639 |
uint64_t h = constant; |
| 640 |
for (const auto &p : props) { |
| 641 |
h = h * constant ^ p[a]; |
| 642 |
} |
| 643 |
for (const auto &r : residuals) { |
| 644 |
h = h * constant ^ r[a].tok; |
| 645 |
h = h * constant ^ r[a].nbits; |
| 646 |
} |
| 647 |
return (h >> 16) & (dedup_table_.size() - 1); |
| 648 |
} |
| 649 |
|
| 650 |
bool TreeSamples::IsSameSample(size_t a, size_t b) const { |
| 651 |
bool ret = true; |
| 652 |
for (const auto &r : residuals) { |
| 653 |
if (r[a].tok != r[b].tok) { |
| 654 |
ret = false; |
| 655 |
} |
| 656 |
if (r[a].nbits != r[b].nbits) { |
| 657 |
ret = false; |
| 658 |
} |
| 659 |
} |
| 660 |
for (const auto &p : props) { |
| 661 |
if (p[a] != p[b]) { |
| 662 |
ret = false; |
| 663 |
} |
| 664 |
} |
| 665 |
return ret; |
| 666 |
} |
| 667 |
|
| 668 |
void TreeSamples::AddSample(pixel_type_w pixel, const Properties &properties, |
| 669 |
const pixel_type_w *predictions) { |
| 670 |
for (size_t i = 0; i < predictors.size(); i++) { |
| 671 |
pixel_type v = pixel - predictions[static_cast<int>(predictors[i])]; |
| 672 |
uint32_t tok, nbits, bits; |
| 673 |
HybridUintConfig(4, 1, 2).Encode(PackSigned(v), &tok, &nbits, &bits); |
| 674 |
JXL_DASSERT(tok < 256); |
| 675 |
JXL_DASSERT(nbits < 256); |
| 676 |
residuals[i].emplace_back( |
| 677 |
ResidualToken{static_cast<uint8_t>(tok), static_cast<uint8_t>(nbits)}); |
| 678 |
} |
| 679 |
for (size_t i = 0; i < props_to_use.size(); i++) { |
| 680 |
props[i].push_back(QuantizeProperty(i, properties[props_to_use[i]])); |
| 681 |
} |
| 682 |
sample_counts.push_back(1); |
| 683 |
num_samples++; |
| 684 |
if (AddToTableAndMerge(sample_counts.size() - 1)) { |
| 685 |
for (auto &r : residuals) r.pop_back(); |
| 686 |
for (auto &p : props) p.pop_back(); |
| 687 |
sample_counts.pop_back(); |
| 688 |
} |
| 689 |
} |
| 690 |
|
| 691 |
void TreeSamples::Swap(size_t a, size_t b) { |
| 692 |
if (a == b) return; |
| 693 |
for (auto &r : residuals) { |
| 694 |
std::swap(r[a], r[b]); |
| 695 |
} |
| 696 |
for (auto &p : props) { |
| 697 |
std::swap(p[a], p[b]); |
| 698 |
} |
| 699 |
std::swap(sample_counts[a], sample_counts[b]); |
| 700 |
} |
| 701 |
|
| 702 |
void TreeSamples::ThreeShuffle(size_t a, size_t b, size_t c) { |
| 703 |
if (b == c) { |
| 704 |
Swap(a, b); |
| 705 |
return; |
| 706 |
} |
| 707 |
|
| 708 |
for (auto &r : residuals) { |
| 709 |
auto tmp = r[a]; |
| 710 |
r[a] = r[c]; |
| 711 |
r[c] = r[b]; |
| 712 |
r[b] = tmp; |
| 713 |
} |
| 714 |
for (auto &p : props) { |
| 715 |
auto tmp = p[a]; |
| 716 |
p[a] = p[c]; |
| 717 |
p[c] = p[b]; |
| 718 |
p[b] = tmp; |
| 719 |
} |
| 720 |
auto tmp = sample_counts[a]; |
| 721 |
sample_counts[a] = sample_counts[c]; |
| 722 |
sample_counts[c] = sample_counts[b]; |
| 723 |
sample_counts[b] = tmp; |
| 724 |
} |
| 725 |
|
| 726 |
namespace { |
| 727 |
std::vector<int32_t> QuantizeHistogram(const std::vector<uint32_t> &histogram, |
| 728 |
size_t num_chunks) { |
| 729 |
if (histogram.empty()) return {}; |
| 730 |
// TODO(veluca): selecting distinct quantiles is likely not the best |
| 731 |
// way to go about this. |
| 732 |
std::vector<int32_t> thresholds; |
| 733 |
uint64_t sum = std::accumulate(histogram.begin(), histogram.end(), 0LU); |
| 734 |
uint64_t cumsum = 0; |
| 735 |
uint64_t threshold = 1; |
| 736 |
for (size_t i = 0; i + 1 < histogram.size(); i++) { |
| 737 |
cumsum += histogram[i]; |
| 738 |
if (cumsum >= threshold * sum / num_chunks) { |
| 739 |
thresholds.push_back(i); |
| 740 |
while (cumsum > threshold * sum / num_chunks) threshold++; |
| 741 |
} |
| 742 |
} |
| 743 |
return thresholds; |
| 744 |
} |
| 745 |
|
| 746 |
std::vector<int32_t> QuantizeSamples(const std::vector<int32_t> &samples, |
| 747 |
size_t num_chunks) { |
| 748 |
if (samples.empty()) return {}; |
| 749 |
int min = *std::min_element(samples.begin(), samples.end()); |
| 750 |
constexpr int kRange = 512; |
| 751 |
min = std::min(std::max(min, -kRange), kRange); |
| 752 |
std::vector<uint32_t> counts(2 * kRange + 1); |
| 753 |
for (int s : samples) { |
| 754 |
uint32_t sample_offset = std::min(std::max(s, -kRange), kRange) - min; |
| 755 |
counts[sample_offset]++; |
| 756 |
} |
| 757 |
std::vector<int32_t> thresholds = QuantizeHistogram(counts, num_chunks); |
| 758 |
for (auto &v : thresholds) v += min; |
| 759 |
return thresholds; |
| 760 |
} |
| 761 |
} // namespace |
| 762 |
|
| 763 |
void TreeSamples::PreQuantizeProperties( |
| 764 |
const StaticPropRange &range, |
| 765 |
const std::vector<ModularMultiplierInfo> &multiplier_info, |
| 766 |
const std::vector<uint32_t> &group_pixel_count, |
| 767 |
const std::vector<uint32_t> &channel_pixel_count, |
| 768 |
std::vector<pixel_type> &pixel_samples, |
| 769 |
std::vector<pixel_type> &diff_samples, size_t max_property_values) { |
| 770 |
// If we have forced splits because of multipliers, choose channel and group |
| 771 |
// thresholds accordingly. |
| 772 |
std::vector<int32_t> group_multiplier_thresholds; |
| 773 |
std::vector<int32_t> channel_multiplier_thresholds; |
| 774 |
for (const auto &v : multiplier_info) { |
| 775 |
if (v.range[0][0] != range[0][0]) { |
| 776 |
channel_multiplier_thresholds.push_back(v.range[0][0] - 1); |
| 777 |
} |
| 778 |
if (v.range[0][1] != range[0][1]) { |
| 779 |
channel_multiplier_thresholds.push_back(v.range[0][1] - 1); |
| 780 |
} |
| 781 |
if (v.range[1][0] != range[1][0]) { |
| 782 |
group_multiplier_thresholds.push_back(v.range[1][0] - 1); |
| 783 |
} |
| 784 |
if (v.range[1][1] != range[1][1]) { |
| 785 |
group_multiplier_thresholds.push_back(v.range[1][1] - 1); |
| 786 |
} |
| 787 |
} |
| 788 |
std::sort(channel_multiplier_thresholds.begin(), |
| 789 |
channel_multiplier_thresholds.end()); |
| 790 |
channel_multiplier_thresholds.resize( |
| 791 |
std::unique(channel_multiplier_thresholds.begin(), |
| 792 |
channel_multiplier_thresholds.end()) - |
| 793 |
channel_multiplier_thresholds.begin()); |
| 794 |
std::sort(group_multiplier_thresholds.begin(), |
| 795 |
group_multiplier_thresholds.end()); |
| 796 |
group_multiplier_thresholds.resize( |
| 797 |
std::unique(group_multiplier_thresholds.begin(), |
| 798 |
group_multiplier_thresholds.end()) - |
| 799 |
group_multiplier_thresholds.begin()); |
| 800 |
|
| 801 |
compact_properties.resize(props_to_use.size()); |
| 802 |
auto quantize_channel = [&]() { |
| 803 |
if (!channel_multiplier_thresholds.empty()) { |
| 804 |
return channel_multiplier_thresholds; |
| 805 |
} |
| 806 |
return QuantizeHistogram(channel_pixel_count, max_property_values); |
| 807 |
}; |
| 808 |
auto quantize_group_id = [&]() { |
| 809 |
if (!group_multiplier_thresholds.empty()) { |
| 810 |
return group_multiplier_thresholds; |
| 811 |
} |
| 812 |
return QuantizeHistogram(group_pixel_count, max_property_values); |
| 813 |
}; |
| 814 |
auto quantize_coordinate = [&]() { |
| 815 |
std::vector<int32_t> quantized; |
| 816 |
quantized.reserve(max_property_values - 1); |
| 817 |
for (size_t i = 0; i + 1 < max_property_values; i++) { |
| 818 |
quantized.push_back((i + 1) * 256 / max_property_values - 1); |
| 819 |
} |
| 820 |
return quantized; |
| 821 |
}; |
| 822 |
std::vector<int32_t> abs_pixel_thresholds; |
| 823 |
std::vector<int32_t> pixel_thresholds; |
| 824 |
auto quantize_pixel_property = [&]() { |
| 825 |
if (pixel_thresholds.empty()) { |
| 826 |
pixel_thresholds = QuantizeSamples(pixel_samples, max_property_values); |
| 827 |
} |
| 828 |
return pixel_thresholds; |
| 829 |
}; |
| 830 |
auto quantize_abs_pixel_property = [&]() { |
| 831 |
if (abs_pixel_thresholds.empty()) { |
| 832 |
quantize_pixel_property(); // Compute the non-abs thresholds. |
| 833 |
for (auto &v : pixel_samples) v = std::abs(v); |
| 834 |
abs_pixel_thresholds = |
| 835 |
QuantizeSamples(pixel_samples, max_property_values); |
| 836 |
} |
| 837 |
return abs_pixel_thresholds; |
| 838 |
}; |
| 839 |
std::vector<int32_t> abs_diff_thresholds; |
| 840 |
std::vector<int32_t> diff_thresholds; |
| 841 |
auto quantize_diff_property = [&]() { |
| 842 |
if (diff_thresholds.empty()) { |
| 843 |
diff_thresholds = QuantizeSamples(diff_samples, max_property_values); |
| 844 |
} |
| 845 |
return diff_thresholds; |
| 846 |
}; |
| 847 |
auto quantize_abs_diff_property = [&]() { |
| 848 |
if (abs_diff_thresholds.empty()) { |
| 849 |
quantize_diff_property(); // Compute the non-abs thresholds. |
| 850 |
for (auto &v : diff_samples) v = std::abs(v); |
| 851 |
abs_diff_thresholds = QuantizeSamples(diff_samples, max_property_values); |
| 852 |
} |
| 853 |
return abs_diff_thresholds; |
| 854 |
}; |
| 855 |
auto quantize_wp = [&]() { |
| 856 |
if (max_property_values < 32) { |
| 857 |
return std::vector<int32_t>{-127, -63, -31, -15, -7, -3, -1, 0, |
| 858 |
1, 3, 7, 15, 31, 63, 127}; |
| 859 |
} |
| 860 |
if (max_property_values < 64) { |
| 861 |
return std::vector<int32_t>{-255, -191, -127, -95, -63, -47, -31, -23, |
| 862 |
-15, -11, -7, -5, -3, -1, 0, 1, |
| 863 |
3, 5, 7, 11, 15, 23, 31, 47, |
| 864 |
63, 95, 127, 191, 255}; |
| 865 |
} |
| 866 |
return std::vector<int32_t>{ |
| 867 |
-255, -223, -191, -159, -127, -111, -95, -79, -63, -55, -47, |
| 868 |
-39, -31, -27, -23, -19, -15, -13, -11, -9, -7, -6, |
| 869 |
-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, |
| 870 |
6, 7, 9, 11, 13, 15, 19, 23, 27, 31, 39, |
| 871 |
47, 55, 63, 79, 95, 111, 127, 159, 191, 223, 255}; |
| 872 |
}; |
| 873 |
|
| 874 |
property_mapping.resize(props_to_use.size()); |
| 875 |
for (size_t i = 0; i < props_to_use.size(); i++) { |
| 876 |
if (props_to_use[i] == 0) { |
| 877 |
compact_properties[i] = quantize_channel(); |
| 878 |
} else if (props_to_use[i] == 1) { |
| 879 |
compact_properties[i] = quantize_group_id(); |
| 880 |
} else if (props_to_use[i] == 2 || props_to_use[i] == 3) { |
| 881 |
compact_properties[i] = quantize_coordinate(); |
| 882 |
} else if (props_to_use[i] == 6 || props_to_use[i] == 7 || |
| 883 |
props_to_use[i] == 8 || |
| 884 |
(props_to_use[i] >= kNumNonrefProperties && |
| 885 |
(props_to_use[i] - kNumNonrefProperties) % 4 == 1)) { |
| 886 |
compact_properties[i] = quantize_pixel_property(); |
| 887 |
} else if (props_to_use[i] == 4 || props_to_use[i] == 5 || |
| 888 |
(props_to_use[i] >= kNumNonrefProperties && |
| 889 |
(props_to_use[i] - kNumNonrefProperties) % 4 == 0)) { |
| 890 |
compact_properties[i] = quantize_abs_pixel_property(); |
| 891 |
} else if (props_to_use[i] >= kNumNonrefProperties && |
| 892 |
(props_to_use[i] - kNumNonrefProperties) % 4 == 2) { |
| 893 |
compact_properties[i] = quantize_abs_diff_property(); |
| 894 |
} else if (props_to_use[i] == kWPProp) { |
| 895 |
compact_properties[i] = quantize_wp(); |
| 896 |
} else { |
| 897 |
compact_properties[i] = quantize_diff_property(); |
| 898 |
} |
| 899 |
property_mapping[i].resize(kPropertyRange * 2 + 1); |
| 900 |
size_t mapped = 0; |
| 901 |
for (size_t j = 0; j < property_mapping[i].size(); j++) { |
| 902 |
while (mapped < compact_properties[i].size() && |
| 903 |
static_cast<int>(j) - kPropertyRange > |
| 904 |
compact_properties[i][mapped]) { |
| 905 |
mapped++; |
| 906 |
} |
| 907 |
// property_mapping[i] of a value V is `mapped` if |
| 908 |
// compact_properties[i][mapped] <= j and |
| 909 |
// compact_properties[i][mapped-1] > j |
| 910 |
// This is because the decision node in the tree splits on (property) > j, |
| 911 |
// hence everything that is not > of a threshold should be clustered |
| 912 |
// together. |
| 913 |
property_mapping[i][j] = mapped; |
| 914 |
} |
| 915 |
} |
| 916 |
} |
| 917 |
|
| 918 |
void CollectPixelSamples(const Image &image, const ModularOptions &options, |
| 919 |
uint32_t group_id, |
| 920 |
std::vector<uint32_t> &group_pixel_count, |
| 921 |
std::vector<uint32_t> &channel_pixel_count, |
| 922 |
std::vector<pixel_type> &pixel_samples, |
| 923 |
std::vector<pixel_type> &diff_samples) { |
| 924 |
if (options.nb_repeats == 0) return; |
| 925 |
if (group_pixel_count.size() <= group_id) { |
| 926 |
group_pixel_count.resize(group_id + 1); |
| 927 |
} |
| 928 |
if (channel_pixel_count.size() < image.channel.size()) { |
| 929 |
channel_pixel_count.resize(image.channel.size()); |
| 930 |
} |
| 931 |
Rng rng(group_id); |
| 932 |
// Sample 10% of the final number of samples for property quantization. |
| 933 |
float fraction = std::min(options.nb_repeats * 0.1, 0.99); |
| 934 |
Rng::GeometricDistribution dist = Rng::MakeGeometric(fraction); |
| 935 |
size_t total_pixels = 0; |
| 936 |
std::vector<size_t> channel_ids; |
| 937 |
for (size_t i = 0; i < image.channel.size(); i++) { |
| 938 |
if (image.channel[i].w <= 1 || image.channel[i].h == 0) { |
| 939 |
continue; // skip empty or width-1 channels. |
| 940 |
} |
| 941 |
if (i >= image.nb_meta_channels && |
| 942 |
(image.channel[i].w > options.max_chan_size || |
| 943 |
image.channel[i].h > options.max_chan_size)) { |
| 944 |
break; |
| 945 |
} |
| 946 |
channel_ids.push_back(i); |
| 947 |
group_pixel_count[group_id] += image.channel[i].w * image.channel[i].h; |
| 948 |
channel_pixel_count[i] += image.channel[i].w * image.channel[i].h; |
| 949 |
total_pixels += image.channel[i].w * image.channel[i].h; |
| 950 |
} |
| 951 |
if (channel_ids.empty()) return; |
| 952 |
pixel_samples.reserve(pixel_samples.size() + fraction * total_pixels); |
| 953 |
diff_samples.reserve(diff_samples.size() + fraction * total_pixels); |
| 954 |
size_t i = 0; |
| 955 |
size_t y = 0; |
| 956 |
size_t x = 0; |
| 957 |
auto advance = [&](size_t amount) { |
| 958 |
x += amount; |
| 959 |
// Detect row overflow (rare). |
| 960 |
while (x >= image.channel[channel_ids[i]].w) { |
| 961 |
x -= image.channel[channel_ids[i]].w; |
| 962 |
y++; |
| 963 |
// Detect end-of-channel (even rarer). |
| 964 |
if (y == image.channel[channel_ids[i]].h) { |
| 965 |
i++; |
| 966 |
y = 0; |
| 967 |
if (i >= channel_ids.size()) { |
| 968 |
return; |
| 969 |
} |
| 970 |
} |
| 971 |
} |
| 972 |
}; |
| 973 |
advance(rng.Geometric(dist)); |
| 974 |
for (; i < channel_ids.size(); advance(rng.Geometric(dist) + 1)) { |
| 975 |
const pixel_type *row = image.channel[channel_ids[i]].Row(y); |
| 976 |
pixel_samples.push_back(row[x]); |
| 977 |
size_t xp = x == 0 ? 1 : x - 1; |
| 978 |
diff_samples.push_back(static_cast<int64_t>(row[x]) - row[xp]); |
| 979 |
} |
| 980 |
} |
| 981 |
|
| 982 |
// TODO(veluca): very simple encoding scheme. This should be improved. |
| 983 |
Status TokenizeTree(const Tree &tree, std::vector<Token> *tokens, |
| 984 |
Tree *decoder_tree) { |
| 985 |
JXL_ENSURE(tree.size() <= kMaxTreeSize); |
| 986 |
std::queue<int> q; |
| 987 |
q.push(0); |
| 988 |
size_t leaf_id = 0; |
| 989 |
decoder_tree->clear(); |
| 990 |
while (!q.empty()) { |
| 991 |
int cur = q.front(); |
| 992 |
q.pop(); |
| 993 |
JXL_ENSURE(tree[cur].property >= -1); |
| 994 |
tokens->emplace_back(kPropertyContext, tree[cur].property + 1); |
| 995 |
if (tree[cur].property == -1) { |
| 996 |
tokens->emplace_back(kPredictorContext, |
| 997 |
static_cast<int>(tree[cur].predictor)); |
| 998 |
tokens->emplace_back(kOffsetContext, |
| 999 |
PackSigned(tree[cur].predictor_offset)); |
| 1000 |
uint32_t mul_log = Num0BitsBelowLS1Bit_Nonzero(tree[cur].multiplier); |
| 1001 |
uint32_t mul_bits = (tree[cur].multiplier >> mul_log) - 1; |
| 1002 |
tokens->emplace_back(kMultiplierLogContext, mul_log); |
| 1003 |
tokens->emplace_back(kMultiplierBitsContext, mul_bits); |
| 1004 |
JXL_ENSURE(tree[cur].predictor < Predictor::Best); |
| 1005 |
decoder_tree->emplace_back(-1, 0, leaf_id++, 0, tree[cur].predictor, |
| 1006 |
tree[cur].predictor_offset, |
| 1007 |
tree[cur].multiplier); |
| 1008 |
continue; |
| 1009 |
} |
| 1010 |
decoder_tree->emplace_back(tree[cur].property, tree[cur].splitval, |
| 1011 |
decoder_tree->size() + q.size() + 1, |
| 1012 |
decoder_tree->size() + q.size() + 2, |
| 1013 |
Predictor::Zero, 0, 1); |
| 1014 |
q.push(tree[cur].lchild); |
| 1015 |
q.push(tree[cur].rchild); |
| 1016 |
tokens->emplace_back(kSplitValContext, PackSigned(tree[cur].splitval)); |
| 1017 |
} |
| 1018 |
return true; |
| 1019 |
} |
| 1020 |
|
| 1021 |
} // namespace jxl |
| 1022 |
#endif // HWY_ONCE |