lehmer_code.h (2834B)
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 constexpr T ValueOfLowest1Bit(T t) { 24 return t & -t; 25 } 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 void 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_DASSERT(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 } 56 57 // Decodes the Lehmer code in code[0..n) into permutation[0..n). 58 // temp must have 1 << CeilLog2(n) elements but need not be initialized. 59 template <typename PermutationT> 60 void DecodeLehmerCode(const LehmerT* JXL_RESTRICT code, 61 uint32_t* JXL_RESTRICT temp, size_t n, 62 PermutationT* JXL_RESTRICT permutation) { 63 JXL_DASSERT(n != 0); 64 const size_t log2n = CeilLog2Nonzero(n); 65 const size_t padded_n = 1ull << log2n; 66 67 for (size_t i = 0; i < padded_n; i++) { 68 const int32_t i1 = static_cast<int32_t>(i + 1); 69 temp[i] = static_cast<uint32_t>(ValueOfLowest1Bit(i1)); 70 } 71 72 for (size_t i = 0; i < n; i++) { 73 JXL_DASSERT(code[i] + i < n); 74 uint32_t rank = code[i] + 1; 75 76 // Extract i-th unused element via implicit order-statistics tree. 77 size_t bit = padded_n; 78 size_t next = 0; 79 for (size_t i = 0; i <= log2n; i++) { 80 const size_t cand = next + bit; 81 JXL_DASSERT(cand >= 1); 82 bit >>= 1; 83 if (temp[cand - 1] < rank) { 84 next = cand; 85 rank -= temp[cand - 1]; 86 } 87 } 88 89 permutation[i] = next; 90 91 // Mark as used 92 next += 1; 93 while (next <= padded_n) { 94 temp[next - 1] -= 1; 95 next += ValueOfLowest1Bit(next); 96 } 97 } 98 } 99 100 } // namespace jxl 101 102 #endif // LIB_JXL_LEHMER_CODE_H_