tudocomp
– The TU Dortmund Compression Framework
IntRepr.hpp
Go to the documentation of this file.
1 #pragma once
2 
3 #include <type_traits>
4 
5 #include <sdsl/bits.hpp>
6 
7 #include <tudocomp/ds/uint_t.hpp>
9 
10 namespace tdc {namespace int_vector {
11  enum class ElementStorageMode {
12  Direct,
13  BitPacked
14  };
15 
17  using DynamicIntValueType = uint64_t;
18 
19  struct DynamicWidthMemRw {
20  inline static void write_int(uint64_t* word, uint64_t x, uint8_t offset, const uint8_t len) {
21  sdsl::bits::write_int(word, x, offset, len);
22  }
23  inline static uint64_t read_int(const uint64_t* word, uint8_t offset, const uint8_t len) {
24  return sdsl::bits::read_int(word, offset, len);
25  }
26  };
27  struct BitWidthMemRw {
28  inline static void write_int(uint64_t* word, uint64_t v, uint8_t o, const uint8_t) {
29  auto& p = *word;
30  const auto mask = uint64_t(1) << o;
31 
32  v &= 1;
33  p &= (~mask);
34  p |= (uint64_t(v) << o);
35  }
36  inline static uint64_t read_int(const uint64_t* word, uint8_t o, const uint8_t) {
37  const auto p = *word;
38  const auto mask = uint64_t(1) << o;
39 
40  return (p & mask) != 0;
41  }
42  };
43  template<class MB, class MemRw>
44  struct RefDispatch {
45  typedef MB SelfMaxBit;
46 
47  template<class Ref, class V>
48  inline static void assign(Ref& self, V v) {
49  MemRw::write_int(
50  self.m_ptr.m_ptr,
51  v,
52  self.m_ptr.m_bit_offset,
53  self.m_ptr.data_bit_size()
54  );
55  }
56 
57  template<class Ref, class R>
58  inline static R cast_for_op(const Ref& self) {
59  return MemRw::read_int(
60  self.m_ptr.m_ptr,
61  self.m_ptr.m_bit_offset,
62  self.m_ptr.data_bit_size()
63  );
64  }
65  };
66  template<typename const_qual_ptr_t, size_t N>
67  class IntPtrFixedWidthRepr {
68  public:
69  const_qual_ptr_t m_ptr;
70  uint8_t m_bit_offset;
71  private:
72  //const uint8_t m_bit_size;
73  public:
74  IntPtrFixedWidthRepr(const_qual_ptr_t ptr, uint8_t offset, uint8_t /*size*/):
75  m_ptr(ptr), m_bit_offset(offset) /*, m_bit_size(size)*/ {}
76  inline uint8_t data_bit_size() const { return N; }
77  inline void set_data_bit_size(uint8_t x) { }
78  inline IntPtrFixedWidthRepr data_offset_to(const_qual_ptr_t ptr, uint8_t offset) const {
79  return IntPtrFixedWidthRepr(ptr, offset, this->data_bit_size());
80  }
81  };
82  template<typename const_qual_ptr_t>
83  class IntPtrDynamicWidthRepr {
84  public:
85  const_qual_ptr_t m_ptr;
86  uint8_t m_bit_offset;
87  private:
88  uint8_t m_bit_size;
89  public:
90  IntPtrDynamicWidthRepr(const_qual_ptr_t ptr, uint8_t offset, uint8_t size):
91  m_ptr(ptr), m_bit_offset(offset), m_bit_size(size) {}
92  inline uint8_t data_bit_size() const { return m_bit_size; }
93  inline void set_data_bit_size(uint8_t x) { m_bit_size = x; }
94  inline IntPtrDynamicWidthRepr data_offset_to(const_qual_ptr_t ptr, uint8_t offset) const {
95  return IntPtrDynamicWidthRepr(ptr, offset, this->data_bit_size());
96  }
97  };
98  template<size_t N>
99  struct FixedBitPackingVectorRepr {
100  using internal_data_type = DynamicIntValueType;
101 
102  std::vector<internal_data_type> m_vec;
103  uint64_t m_real_size;
104 
105  inline FixedBitPackingVectorRepr():
106  m_vec(), m_real_size(0) {}
107  inline FixedBitPackingVectorRepr(const FixedBitPackingVectorRepr& other):
108  m_vec(other.m_vec), m_real_size(other.m_real_size) {}
109  inline FixedBitPackingVectorRepr(FixedBitPackingVectorRepr&& other):
110  m_vec(std::move(other.m_vec)), m_real_size(other.m_real_size) {}
111 
112  inline uint8_t raw_width() const { return N; }
113  inline void set_width_raw(uint8_t) { }
114  };
115  struct DynamicBitPackingVectorRepr {
116  using internal_data_type = DynamicIntValueType;
117 
118  std::vector<internal_data_type> m_vec;
119  uint64_t m_real_size;
120  uint8_t m_width;
121 
122  inline DynamicBitPackingVectorRepr():
123  m_vec(), m_real_size(0), m_width(64) {}
124  inline DynamicBitPackingVectorRepr(const DynamicBitPackingVectorRepr& other):
125  m_vec(other.m_vec), m_real_size(other.m_real_size), m_width(other.m_width) {}
126  inline DynamicBitPackingVectorRepr(DynamicBitPackingVectorRepr&& other):
127  m_vec(std::move(other.m_vec)), m_real_size(other.m_real_size), m_width(other.m_width) {}
128 
129  inline uint8_t raw_width() const { return m_width; }
130  inline void set_width_raw(uint8_t width) { m_width = width; }
131  };
132 
133  template<typename T, typename X = void>
134  struct IntRepr {};
135 
136  template<size_t N>
137  struct IntRepr<uint_impl_t<N>, typename std::enable_if_t<(N > 1) && (N <= 32)>> {
138  using value_type = uint_impl_t<N>;
139  using mem_rw = DynamicWidthMemRw;
140  using IntOpDispatch = RefDispatch<uint32_t, mem_rw>;
141 
142  using ConstIntPtrBase = IntPtrFixedWidthRepr<DynamicIntValueType const*, N>;
143  using IntPtrBase = IntPtrFixedWidthRepr<DynamicIntValueType*, N>;
144 
145  using BitPackingVectorRepr = FixedBitPackingVectorRepr<N>;
146  };
147 
148  template<size_t N>
149  struct IntRepr<uint_impl_t<N>, typename std::enable_if_t<(N > 32) && (N <= 64)>> {
150  using value_type = uint_impl_t<N>;
151  using mem_rw = DynamicWidthMemRw;
152  using IntOpDispatch = RefDispatch<uint64_t, mem_rw>;
153 
154  using ConstIntPtrBase = IntPtrFixedWidthRepr<DynamicIntValueType const*, N>;
155  using IntPtrBase = IntPtrFixedWidthRepr<DynamicIntValueType*, N>;
156 
157  using BitPackingVectorRepr = FixedBitPackingVectorRepr<N>;
158  };
159 
160  template<>
161  struct IntRepr<bool> {
162  using value_type = bool;
163  using mem_rw = BitWidthMemRw;
164  using IntOpDispatch = RefDispatch<uint32_t, mem_rw>;
165 
166  using ConstIntPtrBase = IntPtrFixedWidthRepr<DynamicIntValueType const*, 1>;
167  using IntPtrBase = IntPtrFixedWidthRepr<DynamicIntValueType*, 1>;
168 
169  using BitPackingVectorRepr = FixedBitPackingVectorRepr<1>;
170  };
171 
172  template<>
173  struct IntRepr<dynamic_t> {
174  using value_type = uint64_t;
175  using mem_rw = DynamicWidthMemRw;
176  using IntOpDispatch = RefDispatch<uint64_t, mem_rw>;
177 
178  using ConstIntPtrBase = IntPtrDynamicWidthRepr<DynamicIntValueType const*>;
179  using IntPtrBase = IntPtrDynamicWidthRepr<DynamicIntValueType*>;
180 
181  using BitPackingVectorRepr = DynamicBitPackingVectorRepr;
182  };
183 
184  template<size_t N>
185  struct IntRepr<uint_impl_t<N>, typename std::enable_if_t<(N <= 1)>>; // Unused
186 
187  template<size_t N>
188  struct IntRepr<uint_impl_t<N>, typename std::enable_if_t<(N > 64)>>; // Invalid
189 
191 }}
Contains the text compression and encoding framework.
Definition: namespaces.hpp:11
len_compact_t len
Definition: LZSSFactors.hpp:38
Custom integer type for storing values of arbitrary bit size bits.
Definition: uint_t.hpp:11