Zserio C++ runtime library  1.0.0
Built for Zserio 2.13.0
DeltaContext.h
Go to the documentation of this file.
1 #ifndef ZSERIO_DELTA_CONTEXT_H_INC
2 #define ZSERIO_DELTA_CONTEXT_H_INC
3 
4 #include <type_traits>
5 
8 #include "zserio/RebindAlloc.h"
9 #include "zserio/Traits.h"
10 #include "zserio/Types.h"
11 #include "zserio/UniquePtr.h"
12 #include "zserio/Vector.h"
13 
14 namespace zserio
15 {
16 
17 namespace detail
18 {
19 
20 // calculates bit length on delta provided as an absolute number
21 inline uint8_t absDeltaBitLength(uint64_t absDelta)
22 {
23  uint8_t result = 0;
24  while (absDelta > 0)
25  {
26  result++;
27  absDelta >>= 1U;
28  }
29 
30  return result;
31 }
32 
33 // calculates bit length, emulates Python bit_length to keep same logic
34 template <typename T>
35 uint8_t calcBitLength(T lhs, T rhs)
36 {
37  const uint64_t absDelta = lhs > rhs
38  ? static_cast<uint64_t>(lhs) - static_cast<uint64_t>(rhs)
39  : static_cast<uint64_t>(rhs) - static_cast<uint64_t>(lhs);
40 
41  return absDeltaBitLength(absDelta);
42 }
43 
44 // calculates delta, doesn't check for possible int64_t overflow since it's used only in cases where it's
45 // already known that overflow cannot occur
46 template <typename T>
47 int64_t calcUncheckedDelta(T lhs, uint64_t rhs)
48 {
49  return static_cast<int64_t>(static_cast<uint64_t>(lhs) - rhs);
50 }
51 
52 } // namespace detail
53 
63 {
64 public:
69  DeltaContext() = default;
70  ~DeltaContext() = default;
71 
72  DeltaContext(DeltaContext&& other) = default;
73  DeltaContext& operator=(DeltaContext&& other) = default;
74  DeltaContext(const DeltaContext& other) = default;
75  DeltaContext& operator=(const DeltaContext& other) = default;
86  template <typename ARRAY_TRAITS, typename OWNER_TYPE>
87  void init(const OWNER_TYPE& owner, typename ARRAY_TRAITS::ElementType element)
88  {
89  m_numElements++;
90  m_unpackedBitSize += bitSizeOfUnpacked<ARRAY_TRAITS>(owner, element);
91 
92  if (!isFlagSet(INIT_STARTED_FLAG))
93  {
94  setFlag(INIT_STARTED_FLAG);
95  m_previousElement = static_cast<uint64_t>(element);
96  m_firstElementBitSize = static_cast<uint8_t>(m_unpackedBitSize);
97  }
98  else
99  {
100  if (m_maxBitNumber <= MAX_BIT_NUMBER_LIMIT)
101  {
102  setFlag(IS_PACKED_FLAG);
103  const auto previousElement = static_cast<typename ARRAY_TRAITS::ElementType>(
104  m_previousElement);
105  const uint8_t maxBitNumber = detail::calcBitLength(element, previousElement);
106  if (maxBitNumber > m_maxBitNumber)
107  {
108  m_maxBitNumber = maxBitNumber;
109  if (m_maxBitNumber > MAX_BIT_NUMBER_LIMIT)
110  resetFlag(IS_PACKED_FLAG);
111  }
112  m_previousElement = static_cast<uint64_t>(element);
113  }
114  }
115  }
116 
125  template <typename ARRAY_TRAITS, typename OWNER_TYPE>
126  size_t bitSizeOf(const OWNER_TYPE& owner, typename ARRAY_TRAITS::ElementType element)
127  {
128  if (!isFlagSet(PROCESSING_STARTED_FLAG))
129  {
130  setFlag(PROCESSING_STARTED_FLAG);
131  finishInit();
132 
133  return bitSizeOfDescriptor() + bitSizeOfUnpacked<ARRAY_TRAITS>(owner, element);
134  }
135  else if (!isFlagSet(IS_PACKED_FLAG))
136  {
137  return bitSizeOfUnpacked<ARRAY_TRAITS>(owner, element);
138  }
139  else
140  {
141  return m_maxBitNumber + (m_maxBitNumber > 0 ? 1 : 0);
142  }
143  }
144 
153  template <typename ARRAY_TRAITS, typename OWNER_TYPE>
154  typename ARRAY_TRAITS::ElementType read(const OWNER_TYPE& owner, BitStreamReader& in)
155  {
156  if (!isFlagSet(PROCESSING_STARTED_FLAG))
157  {
158  setFlag(PROCESSING_STARTED_FLAG);
159  readDescriptor(in);
160 
161  return readUnpacked<ARRAY_TRAITS>(owner, in);
162  }
163  else if (!isFlagSet(IS_PACKED_FLAG))
164  {
165  return readUnpacked<ARRAY_TRAITS>(owner, in);
166  }
167  else
168  {
169  if (m_maxBitNumber > 0)
170  {
171  const int64_t delta = in.readSignedBits64(m_maxBitNumber + 1);
172  const typename ARRAY_TRAITS::ElementType element =
173  static_cast<typename ARRAY_TRAITS::ElementType>(
174  m_previousElement + static_cast<uint64_t>(delta));
175  m_previousElement = static_cast<uint64_t>(element);
176  }
177 
178  return static_cast<typename ARRAY_TRAITS::ElementType>(m_previousElement);
179  }
180  }
181 
189  template <typename ARRAY_TRAITS, typename OWNER_TYPE>
190  void write(const OWNER_TYPE& owner, BitStreamWriter& out, typename ARRAY_TRAITS::ElementType element)
191  {
192  if (!isFlagSet(PROCESSING_STARTED_FLAG))
193  {
194  setFlag(PROCESSING_STARTED_FLAG);
195  finishInit();
196  writeDescriptor(out);
197 
198  writeUnpacked<ARRAY_TRAITS>(owner, out, element);
199  }
200  else if (!isFlagSet(IS_PACKED_FLAG))
201  {
202  writeUnpacked<ARRAY_TRAITS>(owner, out, element);
203  }
204  else
205  {
206  if (m_maxBitNumber > 0)
207  {
208  // it's already checked in the init phase that the delta will fit into int64_t
209  const int64_t delta = detail::calcUncheckedDelta(element, m_previousElement);
210  out.writeSignedBits64(delta, m_maxBitNumber + 1);
211  m_previousElement = static_cast<uint64_t>(element);
212  }
213  }
214  }
215 
216  // overloads with dummy owner
217 
223  template <typename ARRAY_TRAITS>
224  void init(typename ARRAY_TRAITS::ElementType element)
225  {
226  init<ARRAY_TRAITS>(DummyOwner(), element);
227  }
228 
236  template <typename ARRAY_TRAITS>
237  size_t bitSizeOf(typename ARRAY_TRAITS::ElementType element)
238  {
239  return bitSizeOf<ARRAY_TRAITS>(DummyOwner(), element);
240  }
241 
249  template <typename ARRAY_TRAITS>
250  typename ARRAY_TRAITS::ElementType read(BitStreamReader& in)
251  {
252  return read<ARRAY_TRAITS>(DummyOwner(), in);
253  }
254 
261  template <typename ARRAY_TRAITS>
262  void write(BitStreamWriter& out, typename ARRAY_TRAITS::ElementType element)
263  {
264  write<ARRAY_TRAITS>(DummyOwner(), out, element);
265  }
266 
267 private:
268  struct DummyOwner
269  {};
270 
271  void finishInit()
272  {
273  if (isFlagSet(IS_PACKED_FLAG))
274  {
275  const size_t deltaBitSize = m_maxBitNumber + (m_maxBitNumber > 0 ? 1 : 0);
276  const size_t packedBitSizeWithDescriptor = 1 + MAX_BIT_NUMBER_BITS + // descriptor
277  m_firstElementBitSize + (m_numElements - 1) * deltaBitSize;
278  const size_t unpackedBitSizeWithDescriptor = 1 + m_unpackedBitSize;
279  if (packedBitSizeWithDescriptor >= unpackedBitSizeWithDescriptor)
280  resetFlag(IS_PACKED_FLAG);
281  }
282  }
283 
284  size_t bitSizeOfDescriptor() const
285  {
286  if (isFlagSet(IS_PACKED_FLAG))
287  return 1 + MAX_BIT_NUMBER_BITS;
288  else
289  return 1;
290  }
291 
292  template <typename ARRAY_TRAITS,
293  typename std::enable_if<has_owner_type<ARRAY_TRAITS>::value, int>::type = 0>
294  static size_t bitSizeOfUnpacked(const typename ARRAY_TRAITS::OwnerType& owner,
295  typename ARRAY_TRAITS::ElementType element)
296  {
297  return ARRAY_TRAITS::bitSizeOf(owner, element);
298  }
299 
300  template <typename ARRAY_TRAITS,
301  typename std::enable_if<!has_owner_type<ARRAY_TRAITS>::value, int>::type = 0>
302  static size_t bitSizeOfUnpacked(const DummyOwner&,
303  typename ARRAY_TRAITS::ElementType element)
304  {
305  return ARRAY_TRAITS::bitSizeOf(element);
306  }
307 
308  void readDescriptor(BitStreamReader& in)
309  {
310  if (in.readBool())
311  {
312  setFlag(IS_PACKED_FLAG);
313  m_maxBitNumber = static_cast<uint8_t>(in.readBits(MAX_BIT_NUMBER_BITS));
314  }
315  else
316  {
317  resetFlag(IS_PACKED_FLAG);
318  }
319  }
320 
321  template <typename ARRAY_TRAITS,
322  typename std::enable_if<has_owner_type<ARRAY_TRAITS>::value, int>::type = 0>
323  typename ARRAY_TRAITS::ElementType readUnpacked(const typename ARRAY_TRAITS::OwnerType& owner,
324  BitStreamReader& in)
325  {
326  const auto element = ARRAY_TRAITS::read(owner, in);
327  m_previousElement = static_cast<uint64_t>(element);
328  return element;
329  }
330 
331  template <typename ARRAY_TRAITS,
332  typename std::enable_if<!has_owner_type<ARRAY_TRAITS>::value, int>::type = 0>
333  typename ARRAY_TRAITS::ElementType readUnpacked(const DummyOwner&, BitStreamReader& in)
334  {
335  const auto element = ARRAY_TRAITS::read(in);
336  m_previousElement = static_cast<uint64_t>(element);
337  return element;
338  }
339 
340  void writeDescriptor(BitStreamWriter& out) const
341  {
342  const bool isPacked = isFlagSet(IS_PACKED_FLAG);
343  out.writeBool(isPacked);
344  if (isPacked)
345  out.writeBits(m_maxBitNumber, MAX_BIT_NUMBER_BITS);
346  }
347 
348  template <typename ARRAY_TRAITS,
349  typename std::enable_if<has_owner_type<ARRAY_TRAITS>::value, int>::type = 0>
350  void writeUnpacked(const typename ARRAY_TRAITS::OwnerType& owner,
351  BitStreamWriter& out, typename ARRAY_TRAITS::ElementType element)
352  {
353  m_previousElement = static_cast<uint64_t>(element);
354  ARRAY_TRAITS::write(owner, out, element);
355  }
356 
357  template <typename ARRAY_TRAITS,
358  typename std::enable_if<!has_owner_type<ARRAY_TRAITS>::value, int>::type = 0>
359  void writeUnpacked(const DummyOwner&, BitStreamWriter& out, typename ARRAY_TRAITS::ElementType element)
360  {
361  m_previousElement = static_cast<uint64_t>(element);
362  ARRAY_TRAITS::write(out, element);
363  }
364 
365  void setFlag(uint8_t flagMask)
366  {
367  m_flags |= flagMask;
368  }
369 
370  void resetFlag(uint8_t flagMask)
371  {
372  m_flags &= static_cast<uint8_t>(~flagMask);
373  }
374 
375  bool isFlagSet(uint8_t flagMask) const
376  {
377  return ((m_flags & flagMask) != 0);
378  }
379 
380  static const uint8_t MAX_BIT_NUMBER_BITS = 6;
381  static const uint8_t MAX_BIT_NUMBER_LIMIT = 62;
382 
383  static const uint8_t INIT_STARTED_FLAG = 0x01;
384  static const uint8_t IS_PACKED_FLAG = 0x02;
385  static const uint8_t PROCESSING_STARTED_FLAG = 0x04;
386 
387  uint64_t m_previousElement = 0;
388  uint8_t m_maxBitNumber = 0;
389  uint8_t m_flags = 0x00;
390 
391  uint8_t m_firstElementBitSize = 0;
392  uint32_t m_numElements = 0;
393  size_t m_unpackedBitSize = 0;
394 };
395 
396 } // namespace zserio
397 
398 #endif // ZSERIO_DELTA_CONTEXT_H_INC
ARRAY_TRAITS::ElementType read(BitStreamReader &in)
Definition: DeltaContext.h:250
uint32_t readBits(uint8_t numBits=32)
void init(const OWNER_TYPE &owner, typename ARRAY_TRAITS::ElementType element)
Definition: DeltaContext.h:87
size_t bitSizeOf(typename ARRAY_TRAITS::ElementType element)
Definition: DeltaContext.h:237
T read(BitStreamReader &in)
void write(BitStreamWriter &out, T value)
int64_t readSignedBits64(uint8_t numBits=64)
void writeBits(uint32_t data, uint8_t numBits=32)
ARRAY_TRAITS::ElementType read(const OWNER_TYPE &owner, BitStreamReader &in)
Definition: DeltaContext.h:154
void write(BitStreamWriter &out, typename ARRAY_TRAITS::ElementType element)
Definition: DeltaContext.h:262
void write(const OWNER_TYPE &owner, BitStreamWriter &out, typename ARRAY_TRAITS::ElementType element)
Definition: DeltaContext.h:190
void init(typename ARRAY_TRAITS::ElementType element)
Definition: DeltaContext.h:224
size_t bitSizeOf(const OWNER_TYPE &owner, typename ARRAY_TRAITS::ElementType element)
Definition: DeltaContext.h:126
void writeSignedBits64(int64_t data, uint8_t numBits=64)
size_t bitSizeOf(T value)