/src/libjxl/lib/jxl/lehmer_code.h
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 | | #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 | 0 | constexpr T ValueOfLowest1Bit(T t) { |
24 | 0 | return t & -t; |
25 | 0 | } Unexecuted instantiation: unsigned int jxl::ValueOfLowest1Bit<unsigned int>(unsigned int) Unexecuted instantiation: int jxl::ValueOfLowest1Bit<int>(int) Unexecuted instantiation: unsigned long jxl::ValueOfLowest1Bit<unsigned long>(unsigned long) |
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 | 0 | LehmerT* JXL_RESTRICT code) { |
34 | 0 | for (size_t idx = 0; idx < n + 1; ++idx) temp[idx] = 0; |
35 | |
|
36 | 0 | for (size_t idx = 0; idx < n; ++idx) { |
37 | 0 | const PermutationT s = permutation[idx]; |
38 | | |
39 | | // Compute sum in Fenwick tree |
40 | 0 | uint32_t penalty = 0; |
41 | 0 | uint32_t i = s + 1; |
42 | 0 | while (i != 0) { |
43 | 0 | penalty += temp[i]; |
44 | 0 | i &= i - 1; // clear lowest bit |
45 | 0 | } |
46 | 0 | JXL_ENSURE(s >= penalty); |
47 | 0 | code[idx] = s - penalty; |
48 | 0 | i = s + 1; |
49 | | // Add operation in Fenwick tree |
50 | 0 | while (i < n + 1) { |
51 | 0 | temp[i] += 1; |
52 | 0 | i += ValueOfLowest1Bit(i); |
53 | 0 | } |
54 | 0 | } |
55 | 0 | return true; |
56 | 0 | } |
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 | 0 | PermutationT* JXL_RESTRICT permutation) { |
64 | 0 | JXL_ENSURE(n != 0); |
65 | 0 | const size_t log2n = CeilLog2Nonzero(n); |
66 | 0 | const size_t padded_n = 1ull << log2n; |
67 | |
|
68 | 0 | for (size_t i = 0; i < padded_n; i++) { |
69 | 0 | const int32_t i1 = static_cast<int32_t>(i + 1); |
70 | 0 | temp[i] = static_cast<uint32_t>(ValueOfLowest1Bit(i1)); |
71 | 0 | } |
72 | |
|
73 | 0 | for (size_t i = 0; i < n; i++) { |
74 | 0 | JXL_ENSURE(code[i] + i < n); |
75 | 0 | uint32_t rank = code[i] + 1; |
76 | | |
77 | | // Extract i-th unused element via implicit order-statistics tree. |
78 | 0 | size_t bit = padded_n; |
79 | 0 | size_t next = 0; |
80 | 0 | for (size_t b = 0; b <= log2n; b++) { |
81 | 0 | const size_t cand = next + bit; |
82 | 0 | JXL_ENSURE(cand >= 1); |
83 | 0 | bit >>= 1; |
84 | 0 | if (temp[cand - 1] < rank) { |
85 | 0 | next = cand; |
86 | 0 | rank -= temp[cand - 1]; |
87 | 0 | } |
88 | 0 | } |
89 | | |
90 | 0 | permutation[i] = next; |
91 | | |
92 | | // Mark as used |
93 | 0 | next += 1; |
94 | 0 | while (next <= padded_n) { |
95 | 0 | temp[next - 1] -= 1; |
96 | 0 | next += ValueOfLowest1Bit(next); |
97 | 0 | } |
98 | 0 | } |
99 | 0 | return true; |
100 | 0 | } |
101 | | |
102 | | } // namespace jxl |
103 | | |
104 | | #endif // LIB_JXL_LEHMER_CODE_H_ |