Coverage Report

Created: 2025-06-13 06:51

/src/libjxl/lib/jxl/lehmer_code.h
Line
Count
Source
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_LEHMER_CODE_H_
7
#define LIB_JXL_LEHMER_CODE_H_
8
9
#include <stddef.h>
10
#include <stdint.h>
11
12
#include "lib/jxl/base/bits.h"
13
#include "lib/jxl/base/compiler_specific.h"
14
#include "lib/jxl/base/status.h"
15
16
namespace jxl {
17
18
// Permutation <=> factorial base representation (Lehmer code).
19
20
using LehmerT = uint32_t;
21
22
template <typename T>
23
57.6M
constexpr T ValueOfLowest1Bit(T t) {
24
57.6M
  return t & -t;
25
57.6M
}
int jxl::ValueOfLowest1Bit<int>(int)
Line
Count
Source
23
8.02M
constexpr T ValueOfLowest1Bit(T t) {
24
8.02M
  return t & -t;
25
8.02M
}
unsigned long jxl::ValueOfLowest1Bit<unsigned long>(unsigned long)
Line
Count
Source
23
49.6M
constexpr T ValueOfLowest1Bit(T t) {
24
49.6M
  return t & -t;
25
49.6M
}
Unexecuted instantiation: unsigned int jxl::ValueOfLowest1Bit<unsigned int>(unsigned int)
26
27
// Computes the Lehmer (factorial basis) code of permutation, an array of n
28
// unique indices in [0..n), and stores it in code[0..len). N*logN time.
29
// temp must have n + 1 elements but need not be initialized.
30
template <typename PermutationT>
31
Status ComputeLehmerCode(const PermutationT* JXL_RESTRICT permutation,
32
                         uint32_t* JXL_RESTRICT temp, const size_t n,
33
                         LehmerT* JXL_RESTRICT code) {
34
  for (size_t idx = 0; idx < n + 1; ++idx) temp[idx] = 0;
35
36
  for (size_t idx = 0; idx < n; ++idx) {
37
    const PermutationT s = permutation[idx];
38
39
    // Compute sum in Fenwick tree
40
    uint32_t penalty = 0;
41
    uint32_t i = s + 1;
42
    while (i != 0) {
43
      penalty += temp[i];
44
      i &= i - 1;  // clear lowest bit
45
    }
46
    JXL_ENSURE(s >= penalty);
47
    code[idx] = s - penalty;
48
    i = s + 1;
49
    // Add operation in Fenwick tree
50
    while (i < n + 1) {
51
      temp[i] += 1;
52
      i += ValueOfLowest1Bit(i);
53
    }
54
  }
55
  return true;
56
}
57
58
// Decodes the Lehmer code in code[0..n) into permutation[0..n).
59
// temp must have 1 << CeilLog2(n) elements but need not be initialized.
60
template <typename PermutationT>
61
Status DecodeLehmerCode(const LehmerT* JXL_RESTRICT code,
62
                        uint32_t* JXL_RESTRICT temp, size_t n,
63
26.4k
                        PermutationT* JXL_RESTRICT permutation) {
64
26.4k
  JXL_ENSURE(n != 0);
65
26.4k
  const size_t log2n = CeilLog2Nonzero(n);
66
26.4k
  const size_t padded_n = 1ull << log2n;
67
68
8.04M
  for (size_t i = 0; i < padded_n; i++) {
69
8.02M
    const int32_t i1 = static_cast<int32_t>(i + 1);
70
8.02M
    temp[i] = static_cast<uint32_t>(ValueOfLowest1Bit(i1));
71
8.02M
  }
72
73
6.06M
  for (size_t i = 0; i < n; i++) {
74
6.04M
    JXL_ENSURE(code[i] + i < n);
75
6.04M
    uint32_t rank = code[i] + 1;
76
77
    // Extract i-th unused element via implicit order-statistics tree.
78
6.04M
    size_t bit = padded_n;
79
6.04M
    size_t next = 0;
80
95.3M
    for (size_t b = 0; b <= log2n; b++) {
81
89.2M
      const size_t cand = next + bit;
82
89.2M
      JXL_ENSURE(cand >= 1);
83
89.2M
      bit >>= 1;
84
89.2M
      if (temp[cand - 1] < rank) {
85
39.6M
        next = cand;
86
39.6M
        rank -= temp[cand - 1];
87
39.6M
      }
88
89.2M
    }
89
90
6.04M
    permutation[i] = next;
91
92
    // Mark as used
93
6.04M
    next += 1;
94
55.6M
    while (next <= padded_n) {
95
49.6M
      temp[next - 1] -= 1;
96
49.6M
      next += ValueOfLowest1Bit(next);
97
49.6M
    }
98
6.04M
  }
99
26.4k
  return true;
100
26.4k
}
101
102
}  // namespace jxl
103
104
#endif  // LIB_JXL_LEHMER_CODE_H_