tudocomp
– The TU Dortmund Compression Framework
select_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 
8 // thiss linear shifting approach is indeed the fastest, compared with
9 // a binary search approach and one using __builtin_ffs / __builtin_ctz
10 
13 constexpr uint8_t SELECT_FAIL = 0xFF;
14 
25 template<typename uint_t>
26 inline constexpr uint8_t select1(uint_t v, uint8_t k) {
27  DCHECK(k > 0) << "order must be at least one";
28  uint8_t pos = 0;
29  while(v) {
30  if(v&1) {
31  if(!--k) return pos;
32  }
33  ++pos;
34  v >>= 1;
35  }
36  return SELECT_FAIL; //TODO: throw error?
37 }
38 
48 template<typename uint_t>
49 inline constexpr uint8_t select1(uint_t v, uint8_t l, uint8_t k) {
50  uint8_t pos = select1(v >> l, k);
51  return (pos != SELECT_FAIL) ? (l + pos) : SELECT_FAIL;
52 }
53 
64 template<typename uint_t>
65 inline constexpr uint8_t select0(uint_t v, uint8_t k) {
66  DCHECK(k > 0) << "order must be at least one";
67  uint8_t pos = 0;
68  while(v) {
69  if(!(v&1)) {
70  if(!--k) return pos;
71  }
72  ++pos;
73  v >>= 1;
74  }
75  pos += k-1;
76  return (pos <= msbf<uint_t>::pos) ? pos : SELECT_FAIL; //TODO: throw error?
77 }
78 
88 template<typename uint_t>
89 inline constexpr uint8_t select0(uint_t v, uint8_t l, uint8_t k) {
90  uint8_t pos = select0(v >> l, k);
91  if(pos != SELECT_FAIL) {
92  pos += l;
93  return (pos <= msbf<uint_t>::pos) ? pos : SELECT_FAIL; //TODO: throw error?
94  } else {
95  return SELECT_FAIL; //TODO: throw error?
96  }
97 }
98 
99 }
Contains the text compression and encoding framework.
Definition: namespaces.hpp:11
constexpr uint8_t select1(uint_t v, uint8_t k)
Finds the position of the k-th 1-bit in the binary representation of the given value.
Yields the position of the most significant bit for the template integer type.
constexpr uint8_t SELECT_FAIL
Returned by select0 and select1 in case the searched bit does not exist in the given input value...
typename uint_dispatch_t< N >::type uint_t
Definition: uint_t.hpp:165
constexpr uint8_t select0(uint_t v, uint8_t k)
Finds the position of the k-th 0-bit in the binary representation of the given value.
len_compact_t pos
Definition: LZSSFactors.hpp:38