tudocomp
– The TU Dortmund Compression Framework
rank_64bit.hpp
Go to the documentation of this file.
1 #pragma once
2 
3 #include <cstdint>
4 #include <tudocomp/util.hpp>
5 
6 namespace tdc {
7 
12  constexpr uint8_t rank1_8bit[] = {
13  0, 1, 1, 2, 1, 2, 2, 3,
14  1, 2, 2, 3, 2, 3, 3, 4,
15  1, 2, 2, 3, 2, 3, 3, 4,
16  2, 3, 3, 4, 3, 4, 4, 5,
17  1, 2, 2, 3, 2, 3, 3, 4,
18  2, 3, 3, 4, 3, 4, 4, 5,
19  2, 3, 3, 4, 3, 4, 4, 5,
20  3, 4, 4, 5, 4, 5, 5, 6,
21  1, 2, 2, 3, 2, 3, 3, 4,
22  2, 3, 3, 4, 3, 4, 4, 5,
23  2, 3, 3, 4, 3, 4, 4, 5,
24  3, 4, 4, 5, 4, 5, 5, 6,
25  2, 3, 3, 4, 3, 4, 4, 5,
26  3, 4, 4, 5, 4, 5, 5, 6,
27  3, 4, 4, 5, 4, 5, 5, 6,
28  4, 5, 5, 6, 5, 6, 6, 7,
29  1, 2, 2, 3, 2, 3, 3, 4,
30  2, 3, 3, 4, 3, 4, 4, 5,
31  2, 3, 3, 4, 3, 4, 4, 5,
32  3, 4, 4, 5, 4, 5, 5, 6,
33  2, 3, 3, 4, 3, 4, 4, 5,
34  3, 4, 4, 5, 4, 5, 5, 6,
35  3, 4, 4, 5, 4, 5, 5, 6,
36  4, 5, 5, 6, 5, 6, 6, 7,
37  2, 3, 3, 4, 3, 4, 4, 5,
38  3, 4, 4, 5, 4, 5, 5, 6,
39  3, 4, 4, 5, 4, 5, 5, 6,
40  4, 5, 5, 6, 5, 6, 6, 7,
41  3, 4, 4, 5, 4, 5, 5, 6,
42  4, 5, 5, 6, 5, 6, 6, 7,
43  4, 5, 5, 6, 5, 6, 6, 7,
44  5, 6, 6, 7, 6, 7, 7, 8
45  };
46 
51  inline constexpr uint8_t rank1(uint8_t v) {
52  return rank1_8bit[v];
53  }
54 
59  inline constexpr uint8_t rank1(uint16_t v) {
60  return __builtin_popcount(v);
61  }
62 
67  inline constexpr uint8_t rank1(uint32_t v) {
68  return __builtin_popcount(v);
69  }
70 
75  inline constexpr uint8_t rank1(uint64_t v) {
76  return __builtin_popcountll(v);
77  }
78 
89  template<typename uint_t>
90  inline constexpr uint8_t rank1(uint_t v, uint8_t m) {
91  DCHECK(m <= msbf<uint_t>::pos) << "m=" << m;
92  const uint_t mask =
93  std::numeric_limits<uint_t>::max() >> (msbf<uint_t>::pos-m);
94  return rank1(uint_t(v & mask));
95  }
96 
108  template<typename uint_t>
109  inline constexpr uint8_t rank1(uint_t v, uint8_t l, uint8_t m) {
110  DCHECK(l <= msbf<uint_t>::pos &&
111  m <= msbf<uint_t>::pos &&
112  l <= m) << "l=" << l << ",m=" << m;
113 
114  const uint_t mask_m =
115  std::numeric_limits<uint_t>::max() >> (msbf<uint_t>::pos-m);
116  const uint_t mask_l =
117  std::numeric_limits<uint_t>::max() << l;
118  return rank1(uint_t(v & mask_m & mask_l));
119  }
120 
121  template<typename uint_t>
122  inline constexpr uint8_t rank0(uint_t v) {
123  return msbf<uint_t>::pos + 1 - rank1(v);
124  }
125 
126  template<typename uint_t>
127  inline constexpr uint8_t rank0(uint_t v, uint8_t m) {
128  return (m + 1) - rank1(v, m);
129  }
130 
131  template<typename uint_t>
132  inline constexpr uint8_t rank0(uint_t v, uint8_t l, uint8_t m) {
133  return (m - l + 1) - rank1(v, l, m);
134  }
135 
136 } //ns
Contains the text compression and encoding framework.
Definition: namespaces.hpp:11
Yields the position of the most significant bit for the template integer type.
constexpr uint8_t rank0(uint_t v)
Definition: rank_64bit.hpp:122
typename uint_dispatch_t< N >::type uint_t
Definition: uint_t.hpp:165
constexpr uint8_t rank1_8bit[]
Lookup table for the rank operation on 8-bit values.
Definition: rank_64bit.hpp:12
constexpr uint8_t rank1(uint8_t v)
Computes the amount of 1-bits in the binary representation of the given 8-bit value.
Definition: rank_64bit.hpp:51