summaryrefslogtreecommitdiffstats
path: root/third_party/jpeg-xl/lib/jxl/ac_strategy.cc
blob: e7a72f5a33243d837428197e28ec31af9d6276e3 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
// Copyright (c) the JPEG XL Project Authors. All rights reserved.
//
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

#include "lib/jxl/ac_strategy.h"

#include <string.h>

#include <algorithm>
#include <utility>

#include "lib/jxl/base/bits.h"

namespace jxl {

// Tries to generalize zig-zag order to non-square blocks. Surprisingly, in
// square block frequency along the (i + j == const) diagonals is roughly the
// same. For historical reasons, consecutive diagonals are traversed
// in alternating directions - so called "zig-zag" (or "snake") order.
template <bool is_lut>
static void CoeffOrderAndLut(AcStrategy acs, coeff_order_t* out) {
  size_t cx = acs.covered_blocks_x();
  size_t cy = acs.covered_blocks_y();
  CoefficientLayout(&cy, &cx);

  // CoefficientLayout ensures cx >= cy.
  // We compute the zigzag order for a cx x cx block, then discard all the
  // lines that are not multiple of the ratio between cx and cy.
  size_t xs = cx / cy;
  size_t xsm = xs - 1;
  size_t xss = CeilLog2Nonzero(xs);
  // First half of the block
  size_t cur = cx * cy;
  for (size_t i = 0; i < cx * kBlockDim; i++) {
    for (size_t j = 0; j <= i; j++) {
      size_t x = j;
      size_t y = i - j;
      if (i % 2) std::swap(x, y);
      if ((y & xsm) != 0) continue;
      y >>= xss;
      size_t val = 0;
      if (x < cx && y < cy) {
        val = y * cx + x;
      } else {
        val = cur++;
      }
      if (is_lut) {
        out[y * cx * kBlockDim + x] = val;
      } else {
        out[val] = y * cx * kBlockDim + x;
      }
    }
  }
  // Second half
  for (size_t ip = cx * kBlockDim - 1; ip > 0; ip--) {
    size_t i = ip - 1;
    for (size_t j = 0; j <= i; j++) {
      size_t x = cx * kBlockDim - 1 - (i - j);
      size_t y = cx * kBlockDim - 1 - j;
      if (i % 2) std::swap(x, y);
      if ((y & xsm) != 0) continue;
      y >>= xss;
      size_t val = cur++;
      if (is_lut) {
        out[y * cx * kBlockDim + x] = val;
      } else {
        out[val] = y * cx * kBlockDim + x;
      }
    }
  }
}

void AcStrategy::ComputeNaturalCoeffOrder(coeff_order_t* order) const {
  CoeffOrderAndLut</*is_lut=*/false>(*this, order);
}
void AcStrategy::ComputeNaturalCoeffOrderLut(coeff_order_t* lut) const {
  CoeffOrderAndLut</*is_lut=*/true>(*this, lut);
}

// These definitions are needed before C++17.
constexpr size_t AcStrategy::kMaxCoeffBlocks;
constexpr size_t AcStrategy::kMaxBlockDim;
constexpr size_t AcStrategy::kMaxCoeffArea;

StatusOr<AcStrategyImage> AcStrategyImage::Create(size_t xsize, size_t ysize) {
  AcStrategyImage img;
  JXL_ASSIGN_OR_RETURN(img.layers_, ImageB::Create(xsize, ysize));
  img.row_ = img.layers_.Row(0);
  img.stride_ = img.layers_.PixelsPerRow();
  return img;
}

size_t AcStrategyImage::CountBlocks(AcStrategy::Type type) const {
  size_t ret = 0;
  for (size_t y = 0; y < layers_.ysize(); y++) {
    const uint8_t* JXL_RESTRICT row = layers_.ConstRow(y);
    for (size_t x = 0; x < layers_.xsize(); x++) {
      if (row[x] == ((static_cast<uint8_t>(type) << 1) | 1)) ret++;
    }
  }
  return ret;
}

}  // namespace jxl