Coverage Report

Created: 2024-05-21 06:24

/src/libjxl/lib/jxl/ac_strategy.cc
Line
Count
Source (jump to first uncovered line)
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/ac_strategy.h"
7
8
#include <jxl/memory_manager.h>
9
10
#include <algorithm>
11
#include <cstring>
12
#include <utility>
13
14
#include "lib/jxl/base/bits.h"
15
16
namespace jxl {
17
18
// Tries to generalize zig-zag order to non-square blocks. Surprisingly, in
19
// square block frequency along the (i + j == const) diagonals is roughly the
20
// same. For historical reasons, consecutive diagonals are traversed
21
// in alternating directions - so called "zig-zag" (or "snake") order.
22
template <bool is_lut>
23
52
static void CoeffOrderAndLut(AcStrategy acs, coeff_order_t* out) {
24
52
  size_t cx = acs.covered_blocks_x();
25
52
  size_t cy = acs.covered_blocks_y();
26
52
  CoefficientLayout(&cy, &cx);
27
28
  // CoefficientLayout ensures cx >= cy.
29
  // We compute the zigzag order for a cx x cx block, then discard all the
30
  // lines that are not multiple of the ratio between cx and cy.
31
52
  size_t xs = cx / cy;
32
52
  size_t xsm = xs - 1;
33
52
  size_t xss = CeilLog2Nonzero(xs);
34
  // First half of the block
35
52
  size_t cur = cx * cy;
36
468
  for (size_t i = 0; i < cx * kBlockDim; i++) {
37
2.28k
    for (size_t j = 0; j <= i; j++) {
38
1.87k
      size_t x = j;
39
1.87k
      size_t y = i - j;
40
1.87k
      if (i % 2) std::swap(x, y);
41
1.87k
      if ((y & xsm) != 0) continue;
42
1.87k
      y >>= xss;
43
1.87k
      size_t val = 0;
44
1.87k
      if (x < cx && y < cy) {
45
52
        val = y * cx + x;
46
1.82k
      } else {
47
1.82k
        val = cur++;
48
1.82k
      }
49
1.87k
      if (is_lut) {
50
0
        out[y * cx * kBlockDim + x] = val;
51
1.87k
      } else {
52
1.87k
        out[val] = y * cx * kBlockDim + x;
53
1.87k
      }
54
1.87k
    }
55
416
  }
56
  // Second half
57
416
  for (size_t ip = cx * kBlockDim - 1; ip > 0; ip--) {
58
364
    size_t i = ip - 1;
59
1.82k
    for (size_t j = 0; j <= i; j++) {
60
1.45k
      size_t x = cx * kBlockDim - 1 - (i - j);
61
1.45k
      size_t y = cx * kBlockDim - 1 - j;
62
1.45k
      if (i % 2) std::swap(x, y);
63
1.45k
      if ((y & xsm) != 0) continue;
64
1.45k
      y >>= xss;
65
1.45k
      size_t val = cur++;
66
1.45k
      if (is_lut) {
67
0
        out[y * cx * kBlockDim + x] = val;
68
1.45k
      } else {
69
1.45k
        out[val] = y * cx * kBlockDim + x;
70
1.45k
      }
71
1.45k
    }
72
364
  }
73
52
}
ac_strategy.cc:void jxl::CoeffOrderAndLut<false>(jxl::AcStrategy, unsigned int*)
Line
Count
Source
23
52
static void CoeffOrderAndLut(AcStrategy acs, coeff_order_t* out) {
24
52
  size_t cx = acs.covered_blocks_x();
25
52
  size_t cy = acs.covered_blocks_y();
26
52
  CoefficientLayout(&cy, &cx);
27
28
  // CoefficientLayout ensures cx >= cy.
29
  // We compute the zigzag order for a cx x cx block, then discard all the
30
  // lines that are not multiple of the ratio between cx and cy.
31
52
  size_t xs = cx / cy;
32
52
  size_t xsm = xs - 1;
33
52
  size_t xss = CeilLog2Nonzero(xs);
34
  // First half of the block
35
52
  size_t cur = cx * cy;
36
468
  for (size_t i = 0; i < cx * kBlockDim; i++) {
37
2.28k
    for (size_t j = 0; j <= i; j++) {
38
1.87k
      size_t x = j;
39
1.87k
      size_t y = i - j;
40
1.87k
      if (i % 2) std::swap(x, y);
41
1.87k
      if ((y & xsm) != 0) continue;
42
1.87k
      y >>= xss;
43
1.87k
      size_t val = 0;
44
1.87k
      if (x < cx && y < cy) {
45
52
        val = y * cx + x;
46
1.82k
      } else {
47
1.82k
        val = cur++;
48
1.82k
      }
49
1.87k
      if (is_lut) {
50
0
        out[y * cx * kBlockDim + x] = val;
51
1.87k
      } else {
52
1.87k
        out[val] = y * cx * kBlockDim + x;
53
1.87k
      }
54
1.87k
    }
55
416
  }
56
  // Second half
57
416
  for (size_t ip = cx * kBlockDim - 1; ip > 0; ip--) {
58
364
    size_t i = ip - 1;
59
1.82k
    for (size_t j = 0; j <= i; j++) {
60
1.45k
      size_t x = cx * kBlockDim - 1 - (i - j);
61
1.45k
      size_t y = cx * kBlockDim - 1 - j;
62
1.45k
      if (i % 2) std::swap(x, y);
63
1.45k
      if ((y & xsm) != 0) continue;
64
1.45k
      y >>= xss;
65
1.45k
      size_t val = cur++;
66
1.45k
      if (is_lut) {
67
0
        out[y * cx * kBlockDim + x] = val;
68
1.45k
      } else {
69
1.45k
        out[val] = y * cx * kBlockDim + x;
70
1.45k
      }
71
1.45k
    }
72
364
  }
73
52
}
Unexecuted instantiation: ac_strategy.cc:void jxl::CoeffOrderAndLut<true>(jxl::AcStrategy, unsigned int*)
74
75
52
void AcStrategy::ComputeNaturalCoeffOrder(coeff_order_t* order) const {
76
52
  CoeffOrderAndLut</*is_lut=*/false>(*this, order);
77
52
}
78
0
void AcStrategy::ComputeNaturalCoeffOrderLut(coeff_order_t* lut) const {
79
0
  CoeffOrderAndLut</*is_lut=*/true>(*this, lut);
80
0
}
81
82
// These definitions are needed before C++17.
83
constexpr size_t AcStrategy::kMaxCoeffBlocks;
84
constexpr size_t AcStrategy::kMaxBlockDim;
85
constexpr size_t AcStrategy::kMaxCoeffArea;
86
87
StatusOr<AcStrategyImage> AcStrategyImage::Create(
88
52
    JxlMemoryManager* memory_manager, size_t xsize, size_t ysize) {
89
52
  AcStrategyImage img;
90
52
  JXL_ASSIGN_OR_RETURN(img.layers_,
91
52
                       ImageB::Create(memory_manager, xsize, ysize));
92
52
  img.row_ = img.layers_.Row(0);
93
52
  img.stride_ = img.layers_.PixelsPerRow();
94
52
  return img;
95
52
}
96
97
0
size_t AcStrategyImage::CountBlocks(AcStrategy::Type type) const {
98
0
  size_t ret = 0;
99
0
  for (size_t y = 0; y < layers_.ysize(); y++) {
100
0
    const uint8_t* JXL_RESTRICT row = layers_.ConstRow(y);
101
0
    for (size_t x = 0; x < layers_.xsize(); x++) {
102
0
      if (row[x] == ((static_cast<uint8_t>(type) << 1) | 1)) ret++;
103
0
    }
104
0
  }
105
0
  return ret;
106
0
}
107
108
}  // namespace jxl