lehmer_code.h (2872B)
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 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 PermutationT* JXL_RESTRICT permutation) { 64 JXL_ENSURE(n != 0); 65 const size_t log2n = CeilLog2Nonzero(n); 66 const size_t padded_n = 1ull << log2n; 67 68 for (size_t i = 0; i < padded_n; i++) { 69 const int32_t i1 = static_cast<int32_t>(i + 1); 70 temp[i] = static_cast<uint32_t>(ValueOfLowest1Bit(i1)); 71 } 72 73 for (size_t i = 0; i < n; i++) { 74 JXL_ENSURE(code[i] + i < n); 75 uint32_t rank = code[i] + 1; 76 77 // Extract i-th unused element via implicit order-statistics tree. 78 size_t bit = padded_n; 79 size_t next = 0; 80 for (size_t i = 0; i <= log2n; i++) { 81 const size_t cand = next + bit; 82 JXL_ENSURE(cand >= 1); 83 bit >>= 1; 84 if (temp[cand - 1] < rank) { 85 next = cand; 86 rank -= temp[cand - 1]; 87 } 88 } 89 90 permutation[i] = next; 91 92 // Mark as used 93 next += 1; 94 while (next <= padded_n) { 95 temp[next - 1] -= 1; 96 next += ValueOfLowest1Bit(next); 97 } 98 } 99 return true; 100 } 101 102 } // namespace jxl 103 104 #endif // LIB_JXL_LEHMER_CODE_H_