// 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 <jxl/memory_manager.h>

#include <algorithm>

#include <cstring>

#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;

      }

    }

  }

}

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*)

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(

    JxlMemoryManager* memory_manager, size_t xsize, size_t ysize) {

  AcStrategyImage img;

  JXL_ASSIGN_OR_RETURN(img.layers_,

                       ImageB::Create(memory_manager, 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