Zserio C++ runtime library  1.0.1
Built for Zserio 2.14.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>(m_previousElement);
104  const uint8_t maxBitNumber = detail::calcBitLength(element, previousElement);
105  if (maxBitNumber > m_maxBitNumber)
106  {
107  m_maxBitNumber = maxBitNumber;
108  if (m_maxBitNumber > MAX_BIT_NUMBER_LIMIT)
109  resetFlag(IS_PACKED_FLAG);
110  }
111  m_previousElement = static_cast<uint64_t>(element);
112  }
113  }
114  }
115 
124  template <typename ARRAY_TRAITS, typename OWNER_TYPE>
125  size_t bitSizeOf(const OWNER_TYPE& owner, typename ARRAY_TRAITS::ElementType element)
126  {
127  if (!isFlagSet(PROCESSING_STARTED_FLAG))
128  {
129  setFlag(PROCESSING_STARTED_FLAG);
130  finishInit();
131 
132  return bitSizeOfDescriptor() + bitSizeOfUnpacked<ARRAY_TRAITS>(owner, element);
133  }
134  else if (!isFlagSet(IS_PACKED_FLAG))
135  {
136  return bitSizeOfUnpacked<ARRAY_TRAITS>(owner, element);
137  }
138  else
139  {
140  return m_maxBitNumber + (m_maxBitNumber > 0 ? 1 : 0);
141  }
142  }
143 
152  template <typename ARRAY_TRAITS, typename OWNER_TYPE>
153  typename ARRAY_TRAITS::ElementType read(const OWNER_TYPE& owner, BitStreamReader& in)
154  {
155  if (!isFlagSet(PROCESSING_STARTED_FLAG))
156  {
157  setFlag(PROCESSING_STARTED_FLAG);
158  readDescriptor(in);
159 
160  return readUnpacked<ARRAY_TRAITS>(owner, in);
161  }
162  else if (!isFlagSet(IS_PACKED_FLAG))
163  {
164  return readUnpacked<ARRAY_TRAITS>(owner, in);
165  }
166  else
167  {
168  if (m_maxBitNumber > 0)
169  {
170  const int64_t delta = in.readSignedBits64(static_cast<uint8_t>(m_maxBitNumber + 1));
171  const typename ARRAY_TRAITS::ElementType element =
172  static_cast<typename ARRAY_TRAITS::ElementType>(
173  m_previousElement + static_cast<uint64_t>(delta));
174  m_previousElement = static_cast<uint64_t>(element);
175  }
176 
177  return static_cast<typename ARRAY_TRAITS::ElementType>(m_previousElement);
178  }
179  }
180 
188  template <typename ARRAY_TRAITS, typename OWNER_TYPE>
189  void write(const OWNER_TYPE& owner, BitStreamWriter& out, typename ARRAY_TRAITS::ElementType element)
190  {
191  if (!isFlagSet(PROCESSING_STARTED_FLAG))
192  {
193  setFlag(PROCESSING_STARTED_FLAG);
194  finishInit();
195  writeDescriptor(out);
196 
197  writeUnpacked<ARRAY_TRAITS>(owner, out, element);
198  }
199  else if (!isFlagSet(IS_PACKED_FLAG))
200  {
201  writeUnpacked<ARRAY_TRAITS>(owner, out, element);
202  }
203  else
204  {
205  if (m_maxBitNumber > 0)
206  {
207  // it's already checked in the init phase that the delta will fit into int64_t
208  const int64_t delta = detail::calcUncheckedDelta(element, m_previousElement);
209  out.writeSignedBits64(delta, static_cast<uint8_t>(m_maxBitNumber + 1));
210  m_previousElement = static_cast<uint64_t>(element);
211  }
212  }
213  }
214 
215  // overloads with dummy owner
216 
222  template <typename ARRAY_TRAITS>
223  void init(typename ARRAY_TRAITS::ElementType element)
224  {
225  init<ARRAY_TRAITS>(DummyOwner(), element);
226  }
227 
235  template <typename ARRAY_TRAITS>
236  size_t bitSizeOf(typename ARRAY_TRAITS::ElementType element)
237  {
238  return bitSizeOf<ARRAY_TRAITS>(DummyOwner(), element);
239  }
240 
248  template <typename ARRAY_TRAITS>
249  typename ARRAY_TRAITS::ElementType read(BitStreamReader& in)
250  {
251  return read<ARRAY_TRAITS>(DummyOwner(), in);
252  }
253 
260  template <typename ARRAY_TRAITS>
261  void write(BitStreamWriter& out, typename ARRAY_TRAITS::ElementType element)
262  {
263  write<ARRAY_TRAITS>(DummyOwner(), out, element);
264  }
265 
266 private:
267  struct DummyOwner
268  {};
269 
270  void finishInit()
271  {
272  if (isFlagSet(IS_PACKED_FLAG))
273  {
274  const size_t deltaBitSize = m_maxBitNumber + (m_maxBitNumber > 0 ? 1 : 0);
275  const size_t packedBitSizeWithDescriptor = 1 + MAX_BIT_NUMBER_BITS + // descriptor
276  m_firstElementBitSize + (m_numElements - 1) * deltaBitSize;
277  const size_t unpackedBitSizeWithDescriptor = 1 + m_unpackedBitSize;
278  if (packedBitSizeWithDescriptor >= unpackedBitSizeWithDescriptor)
279  resetFlag(IS_PACKED_FLAG);
280  }
281  }
282 
283  size_t bitSizeOfDescriptor() const
284  {
285  if (isFlagSet(IS_PACKED_FLAG))
286  return 1 + MAX_BIT_NUMBER_BITS;
287  else
288  return 1;
289  }
290 
291  template <typename ARRAY_TRAITS,
292  typename std::enable_if<has_owner_type<ARRAY_TRAITS>::value, int>::type = 0>
293  static size_t bitSizeOfUnpacked(
294  const typename ARRAY_TRAITS::OwnerType& owner, typename ARRAY_TRAITS::ElementType element)
295  {
296  return ARRAY_TRAITS::bitSizeOf(owner, element);
297  }
298 
299  template <typename ARRAY_TRAITS,
300  typename std::enable_if<!has_owner_type<ARRAY_TRAITS>::value, int>::type = 0>
301  static size_t bitSizeOfUnpacked(const DummyOwner&, typename ARRAY_TRAITS::ElementType element)
302  {
303  return ARRAY_TRAITS::bitSizeOf(element);
304  }
305 
306  void readDescriptor(BitStreamReader& in)
307  {
308  if (in.readBool())
309  {
310  setFlag(IS_PACKED_FLAG);
311  m_maxBitNumber = static_cast<uint8_t>(in.readBits(MAX_BIT_NUMBER_BITS));
312  }
313  else
314  {
315  resetFlag(IS_PACKED_FLAG);
316  }
317  }
318 
319  template <typename ARRAY_TRAITS,
320  typename std::enable_if<has_owner_type<ARRAY_TRAITS>::value, int>::type = 0>
321  typename ARRAY_TRAITS::ElementType readUnpacked(
322  const typename ARRAY_TRAITS::OwnerType& owner, BitStreamReader& in)
323  {
324  const auto element = ARRAY_TRAITS::read(owner, in);
325  m_previousElement = static_cast<uint64_t>(element);
326  return element;
327  }
328 
329  template <typename ARRAY_TRAITS,
330  typename std::enable_if<!has_owner_type<ARRAY_TRAITS>::value, int>::type = 0>
331  typename ARRAY_TRAITS::ElementType readUnpacked(const DummyOwner&, BitStreamReader& in)
332  {
333  const auto element = ARRAY_TRAITS::read(in);
334  m_previousElement = static_cast<uint64_t>(element);
335  return element;
336  }
337 
338  void writeDescriptor(BitStreamWriter& out) const
339  {
340  const bool isPacked = isFlagSet(IS_PACKED_FLAG);
341  out.writeBool(isPacked);
342  if (isPacked)
343  out.writeBits(m_maxBitNumber, MAX_BIT_NUMBER_BITS);
344  }
345 
346  template <typename ARRAY_TRAITS,
347  typename std::enable_if<has_owner_type<ARRAY_TRAITS>::value, int>::type = 0>
348  void writeUnpacked(const typename ARRAY_TRAITS::OwnerType& owner, BitStreamWriter& out,
349  typename ARRAY_TRAITS::ElementType element)
350  {
351  m_previousElement = static_cast<uint64_t>(element);
352  ARRAY_TRAITS::write(owner, out, element);
353  }
354 
355  template <typename ARRAY_TRAITS,
356  typename std::enable_if<!has_owner_type<ARRAY_TRAITS>::value, int>::type = 0>
357  void writeUnpacked(const DummyOwner&, BitStreamWriter& out, typename ARRAY_TRAITS::ElementType element)
358  {
359  m_previousElement = static_cast<uint64_t>(element);
360  ARRAY_TRAITS::write(out, element);
361  }
362 
363  void setFlag(uint8_t flagMask)
364  {
365  m_flags |= flagMask;
366  }
367 
368  void resetFlag(uint8_t flagMask)
369  {
370  m_flags &= static_cast<uint8_t>(~flagMask);
371  }
372 
373  bool isFlagSet(uint8_t flagMask) const
374  {
375  return ((m_flags & flagMask) != 0);
376  }
377 
378  static const uint8_t MAX_BIT_NUMBER_BITS = 6;
379  static const uint8_t MAX_BIT_NUMBER_LIMIT = 62;
380 
381  static const uint8_t INIT_STARTED_FLAG = 0x01;
382  static const uint8_t IS_PACKED_FLAG = 0x02;
383  static const uint8_t PROCESSING_STARTED_FLAG = 0x04;
384 
385  uint64_t m_previousElement = 0;
386  uint8_t m_maxBitNumber = 0;
387  uint8_t m_flags = 0x00;
388 
389  uint8_t m_firstElementBitSize = 0;
390  uint32_t m_numElements = 0;
391  size_t m_unpackedBitSize = 0;
392 };
393 
394 } // namespace zserio
395 
396 #endif // ZSERIO_DELTA_CONTEXT_H_INC
int64_t readSignedBits64(uint8_t numBits=64)
void writeSignedBits64(int64_t data, uint8_t numBits=64)
void init(const OWNER_TYPE &owner, typename ARRAY_TRAITS::ElementType element)
Definition: DeltaContext.h:87
void write(const OWNER_TYPE &owner, BitStreamWriter &out, typename ARRAY_TRAITS::ElementType element)
Definition: DeltaContext.h:189
ARRAY_TRAITS::ElementType read(const OWNER_TYPE &owner, BitStreamReader &in)
Definition: DeltaContext.h:153
ARRAY_TRAITS::ElementType read(BitStreamReader &in)
Definition: DeltaContext.h:249
DeltaContext & operator=(const DeltaContext &other)=default
void init(typename ARRAY_TRAITS::ElementType element)
Definition: DeltaContext.h:223
size_t bitSizeOf(const OWNER_TYPE &owner, typename ARRAY_TRAITS::ElementType element)
Definition: DeltaContext.h:125
void write(BitStreamWriter &out, typename ARRAY_TRAITS::ElementType element)
Definition: DeltaContext.h:261
size_t bitSizeOf(typename ARRAY_TRAITS::ElementType element)
Definition: DeltaContext.h:236
DeltaContext(const DeltaContext &other)=default
DeltaContext & operator=(DeltaContext &&other)=default
DeltaContext(DeltaContext &&other)=default
T read(BitStreamReader &in)
void write(BitStreamWriter &out, T value)
size_t bitSizeOf(T value)