src/zserio/DeltaContext.h
Line | Count | Source |
1 | | #ifndef ZSERIO_DELTA_CONTEXT_H_INC |
2 | | #define ZSERIO_DELTA_CONTEXT_H_INC |
3 | | |
4 | | #include <type_traits> |
5 | | |
6 | | #include "zserio/BitStreamReader.h" |
7 | | #include "zserio/BitStreamWriter.h" |
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 | 8.54k | { |
23 | 8.54k | uint8_t result = 0; |
24 | 122k | while (absDelta > 0) |
25 | 114k | { |
26 | 114k | result++; |
27 | 114k | absDelta >>= 1U; |
28 | 114k | } |
29 | | |
30 | 8.54k | return result; |
31 | 8.54k | } |
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 | 8.54k | { |
37 | 8.54k | const uint64_t absDelta = lhs > rhs |
38 | 8.54k | ? static_cast<uint64_t>(lhs) - static_cast<uint64_t>(rhs)6.43k |
39 | 8.54k | : static_cast<uint64_t>(rhs) - static_cast<uint64_t>(lhs)2.11k ; |
40 | | |
41 | 8.54k | return absDeltaBitLength(absDelta); |
42 | 8.54k | } |
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 | 1.21k | { |
49 | 1.21k | return static_cast<int64_t>(static_cast<uint64_t>(lhs) - rhs); |
50 | 1.21k | } |
51 | | |
52 | | } // namespace detail |
53 | | |
54 | | /** |
55 | | * Context for delta packing created for each packable field. |
56 | | * |
57 | | * Contexts are always newly created for each array operation (bitSizeOfPacked, initializeOffsetsPacked, |
58 | | * readPacked, writePacked). They must be initialized at first via calling the init method for each packable |
59 | | * element present in the array. After the full initialization, only a single method (bitSizeOf, read, write) |
60 | | * can be repeatedly called for exactly the same sequence of packable elements. |
61 | | */ |
62 | | class DeltaContext |
63 | | { |
64 | | public: |
65 | | /** |
66 | | * Method generated by default. |
67 | | * \{ |
68 | | */ |
69 | 3.32k | 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; |
76 | | /** |
77 | | * \} |
78 | | */ |
79 | | |
80 | | /** |
81 | | * Calls the initialization step for a single element. |
82 | | * |
83 | | * \param owner Owner of the packed element. |
84 | | * \param element Current element. |
85 | | */ |
86 | | template <typename ARRAY_TRAITS, typename OWNER_TYPE> |
87 | | void init(const OWNER_TYPE& owner, typename ARRAY_TRAITS::ElementType element) |
88 | 11.4k | { |
89 | 11.4k | m_numElements++; |
90 | 11.4k | m_unpackedBitSize += bitSizeOfUnpacked<ARRAY_TRAITS>(owner, element); |
91 | | |
92 | 11.4k | if (!isFlagSet(INIT_STARTED_FLAG)) |
93 | 2.49k | { |
94 | 2.49k | setFlag(INIT_STARTED_FLAG); |
95 | 2.49k | m_previousElement = static_cast<uint64_t>(element); |
96 | 2.49k | m_firstElementBitSize = static_cast<uint8_t>(m_unpackedBitSize); |
97 | 2.49k | } |
98 | 8.92k | else |
99 | 8.92k | { |
100 | 8.92k | if (m_maxBitNumber <= MAX_BIT_NUMBER_LIMIT) |
101 | 8.54k | { |
102 | 8.54k | setFlag(IS_PACKED_FLAG); |
103 | 8.54k | const auto previousElement = static_cast<typename ARRAY_TRAITS::ElementType>(m_previousElement); |
104 | 8.54k | const uint8_t maxBitNumber = detail::calcBitLength(element, previousElement); |
105 | 8.54k | if (maxBitNumber > m_maxBitNumber) |
106 | 3.07k | { |
107 | 3.07k | m_maxBitNumber = maxBitNumber; |
108 | 3.07k | if (m_maxBitNumber > MAX_BIT_NUMBER_LIMIT) |
109 | 480 | { |
110 | 480 | resetFlag(IS_PACKED_FLAG); |
111 | 480 | } |
112 | 3.07k | } |
113 | 8.54k | m_previousElement = static_cast<uint64_t>(element); |
114 | 8.54k | } |
115 | 8.92k | } |
116 | 11.4k | } |
117 | | |
118 | | /** |
119 | | * Returns length of the packed element stored in the bit stream in bits. |
120 | | * |
121 | | * \param owner Owner of the packed element. |
122 | | * \param element Value of the current element. |
123 | | * |
124 | | * \return Length of the packed element stored in the bit stream in bits. |
125 | | */ |
126 | | template <typename ARRAY_TRAITS, typename OWNER_TYPE> |
127 | | size_t bitSizeOf(const OWNER_TYPE& owner, typename ARRAY_TRAITS::ElementType element) |
128 | 7.61k | { |
129 | 7.61k | if (!isFlagSet(PROCESSING_STARTED_FLAG)) |
130 | 1.66k | { |
131 | 1.66k | setFlag(PROCESSING_STARTED_FLAG); |
132 | 1.66k | finishInit(); |
133 | | |
134 | 1.66k | return bitSizeOfDescriptor() + bitSizeOfUnpacked<ARRAY_TRAITS>(owner, element); |
135 | 1.66k | } |
136 | 5.95k | else if (!isFlagSet(IS_PACKED_FLAG)) |
137 | 3.26k | { |
138 | 3.26k | return bitSizeOfUnpacked<ARRAY_TRAITS>(owner, element); |
139 | 3.26k | } |
140 | 2.68k | else |
141 | 2.68k | { |
142 | 2.68k | return static_cast<size_t>(m_maxBitNumber) + (m_maxBitNumber > 0 ? 12.43k : 0256 ); |
143 | 2.68k | } |
144 | 7.61k | } |
145 | | |
146 | | /** |
147 | | * Reads a packed element from the bit stream. |
148 | | * |
149 | | * \param owner Owner of the packed element. |
150 | | * \param in Bit stream reader. |
151 | | * |
152 | | * \return Value of the packed element. |
153 | | */ |
154 | | template <typename ARRAY_TRAITS, typename OWNER_TYPE> |
155 | | typename ARRAY_TRAITS::ElementType read(const OWNER_TYPE& owner, BitStreamReader& in) |
156 | 3.80k | { |
157 | 3.80k | if (!isFlagSet(PROCESSING_STARTED_FLAG)) |
158 | 832 | { |
159 | 832 | setFlag(PROCESSING_STARTED_FLAG); |
160 | 832 | readDescriptor(in); |
161 | | |
162 | 832 | return readUnpacked<ARRAY_TRAITS>(owner, in); |
163 | 832 | } |
164 | 2.97k | else if (!isFlagSet(IS_PACKED_FLAG)) |
165 | 1.63k | { |
166 | 1.63k | return readUnpacked<ARRAY_TRAITS>(owner, in); |
167 | 1.63k | } |
168 | 1.34k | else |
169 | 1.34k | { |
170 | 1.34k | if (m_maxBitNumber > 0) |
171 | 1.21k | { |
172 | 1.21k | const int64_t delta = in.readSignedBits64(static_cast<uint8_t>(m_maxBitNumber + 1)); |
173 | 1.21k | const typename ARRAY_TRAITS::ElementType element = |
174 | 1.21k | static_cast<typename ARRAY_TRAITS::ElementType>( |
175 | 1.21k | m_previousElement + static_cast<uint64_t>(delta)); |
176 | 1.21k | m_previousElement = static_cast<uint64_t>(element); |
177 | 1.21k | } |
178 | | |
179 | 1.34k | return static_cast<typename ARRAY_TRAITS::ElementType>(m_previousElement); |
180 | 1.34k | } |
181 | 3.80k | } |
182 | | |
183 | | /** |
184 | | * Writes the packed element to the bit stream. |
185 | | * |
186 | | * \param owner Owner of the packed element. |
187 | | * \param out Bit stream writer. |
188 | | * \param element Value of the current element. |
189 | | */ |
190 | | template <typename ARRAY_TRAITS, typename OWNER_TYPE> |
191 | | void write(const OWNER_TYPE& owner, BitStreamWriter& out, typename ARRAY_TRAITS::ElementType element) |
192 | 3.80k | { |
193 | 3.80k | if (!isFlagSet(PROCESSING_STARTED_FLAG)) |
194 | 832 | { |
195 | 832 | setFlag(PROCESSING_STARTED_FLAG); |
196 | 832 | finishInit(); |
197 | 832 | writeDescriptor(out); |
198 | | |
199 | 832 | writeUnpacked<ARRAY_TRAITS>(owner, out, element); |
200 | 832 | } |
201 | 2.97k | else if (!isFlagSet(IS_PACKED_FLAG)) |
202 | 1.63k | { |
203 | 1.63k | writeUnpacked<ARRAY_TRAITS>(owner, out, element); |
204 | 1.63k | } |
205 | 1.34k | else |
206 | 1.34k | { |
207 | 1.34k | if (m_maxBitNumber > 0) |
208 | 1.21k | { |
209 | | // it's already checked in the init phase that the delta will fit into int64_t |
210 | 1.21k | const int64_t delta = detail::calcUncheckedDelta(element, m_previousElement); |
211 | 1.21k | out.writeSignedBits64(delta, static_cast<uint8_t>(m_maxBitNumber + 1)); |
212 | 1.21k | m_previousElement = static_cast<uint64_t>(element); |
213 | 1.21k | } |
214 | 1.34k | } |
215 | 3.80k | } |
216 | | |
217 | | // overloads with dummy owner |
218 | | |
219 | | /** |
220 | | * Calls the initialization step for a single element. |
221 | | * |
222 | | * \param element Current element. |
223 | | */ |
224 | | template <typename ARRAY_TRAITS> |
225 | | void init(typename ARRAY_TRAITS::ElementType element) |
226 | 10.8k | { |
227 | 10.8k | init<ARRAY_TRAITS>(DummyOwner(), element); |
228 | 10.8k | } |
229 | | |
230 | | /** |
231 | | * Returns length of the packed element stored in the bit stream in bits. |
232 | | * |
233 | | * \param element Value of the current element. |
234 | | * |
235 | | * \return Length of the packed element stored in the bit stream in bits. |
236 | | */ |
237 | | template <typename ARRAY_TRAITS> |
238 | | size_t bitSizeOf(typename ARRAY_TRAITS::ElementType element) |
239 | 7.23k | { |
240 | 7.23k | return bitSizeOf<ARRAY_TRAITS>(DummyOwner(), element); |
241 | 7.23k | } |
242 | | |
243 | | /** |
244 | | * Reads a packed element from the bit stream. |
245 | | * |
246 | | * \param in Bit stream reader. |
247 | | * |
248 | | * \return Value of the packed element. |
249 | | */ |
250 | | template <typename ARRAY_TRAITS> |
251 | | typename ARRAY_TRAITS::ElementType read(BitStreamReader& in) |
252 | 3.61k | { |
253 | 3.61k | return read<ARRAY_TRAITS>(DummyOwner(), in); |
254 | 3.61k | } |
255 | | |
256 | | /** |
257 | | * Writes the packed element to the bit stream. |
258 | | * |
259 | | * \param out Bit stream writer. |
260 | | * \param element Value of the current element. |
261 | | */ |
262 | | template <typename ARRAY_TRAITS> |
263 | | void write(BitStreamWriter& out, typename ARRAY_TRAITS::ElementType element) |
264 | 3.61k | { |
265 | 3.61k | write<ARRAY_TRAITS>(DummyOwner(), out, element); |
266 | 3.61k | } |
267 | | |
268 | | private: |
269 | | struct DummyOwner |
270 | | {}; |
271 | | |
272 | | void finishInit() |
273 | 2.49k | { |
274 | 2.49k | if (isFlagSet(IS_PACKED_FLAG)) |
275 | 1.82k | { |
276 | 1.82k | const size_t deltaBitSize = static_cast<size_t>(m_maxBitNumber) + (m_maxBitNumber > 0 ? 11.63k : 0192 ); |
277 | 1.82k | const size_t packedBitSizeWithDescriptor = 1U + MAX_BIT_NUMBER_BITS + // descriptor |
278 | 1.82k | m_firstElementBitSize + (m_numElements - 1) * deltaBitSize; |
279 | 1.82k | const size_t unpackedBitSizeWithDescriptor = 1 + m_unpackedBitSize; |
280 | 1.82k | if (packedBitSizeWithDescriptor >= unpackedBitSizeWithDescriptor) |
281 | 768 | { |
282 | 768 | resetFlag(IS_PACKED_FLAG); |
283 | 768 | } |
284 | 1.82k | } |
285 | 2.49k | } |
286 | | |
287 | | size_t bitSizeOfDescriptor() const |
288 | 1.66k | { |
289 | 1.66k | if (isFlagSet(IS_PACKED_FLAG)) |
290 | 704 | { |
291 | 704 | return 1 + MAX_BIT_NUMBER_BITS; |
292 | 704 | } |
293 | 960 | else |
294 | 960 | { |
295 | 960 | return 1; |
296 | 960 | } |
297 | 1.66k | } |
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( |
302 | | const typename ARRAY_TRAITS::OwnerType& owner, typename ARRAY_TRAITS::ElementType element) |
303 | 960 | { |
304 | 960 | return ARRAY_TRAITS::bitSizeOf(owner, element); |
305 | 960 | } |
306 | | |
307 | | template <typename ARRAY_TRAITS, |
308 | | typename std::enable_if<!has_owner_type<ARRAY_TRAITS>::value, int>::type = 0> |
309 | | static size_t bitSizeOfUnpacked(const DummyOwner&, typename ARRAY_TRAITS::ElementType element) |
310 | 15.3k | { |
311 | 15.3k | return ARRAY_TRAITS::bitSizeOf(element); |
312 | 15.3k | } |
313 | | |
314 | | void readDescriptor(BitStreamReader& in) |
315 | 832 | { |
316 | 832 | if (in.readBool()) |
317 | 352 | { |
318 | 352 | setFlag(IS_PACKED_FLAG); |
319 | 352 | m_maxBitNumber = static_cast<uint8_t>(in.readBits(MAX_BIT_NUMBER_BITS)); |
320 | 352 | } |
321 | 480 | else |
322 | 480 | { |
323 | 480 | resetFlag(IS_PACKED_FLAG); |
324 | 480 | } |
325 | 832 | } |
326 | | |
327 | | template <typename ARRAY_TRAITS, |
328 | | typename std::enable_if<has_owner_type<ARRAY_TRAITS>::value, int>::type = 0> |
329 | | typename ARRAY_TRAITS::ElementType readUnpacked( |
330 | | const typename ARRAY_TRAITS::OwnerType& owner, BitStreamReader& in) |
331 | 192 | { |
332 | 192 | const auto element = ARRAY_TRAITS::read(owner, in); |
333 | 192 | m_previousElement = static_cast<uint64_t>(element); |
334 | 192 | return element; |
335 | 192 | } |
336 | | |
337 | | template <typename ARRAY_TRAITS, |
338 | | typename std::enable_if<!has_owner_type<ARRAY_TRAITS>::value, int>::type = 0> |
339 | | typename ARRAY_TRAITS::ElementType readUnpacked(const DummyOwner&, BitStreamReader& in) |
340 | 2.27k | { |
341 | 2.27k | const auto element = ARRAY_TRAITS::read(in); |
342 | 2.27k | m_previousElement = static_cast<uint64_t>(element); |
343 | 2.27k | return element; |
344 | 2.27k | } |
345 | | |
346 | | void writeDescriptor(BitStreamWriter& out) const |
347 | 832 | { |
348 | 832 | const bool isPacked = isFlagSet(IS_PACKED_FLAG); |
349 | 832 | out.writeBool(isPacked); |
350 | 832 | if (isPacked) |
351 | 352 | { |
352 | 352 | out.writeBits(m_maxBitNumber, MAX_BIT_NUMBER_BITS); |
353 | 352 | } |
354 | 832 | } |
355 | | |
356 | | template <typename ARRAY_TRAITS, |
357 | | typename std::enable_if<has_owner_type<ARRAY_TRAITS>::value, int>::type = 0> |
358 | | void writeUnpacked(const typename ARRAY_TRAITS::OwnerType& owner, BitStreamWriter& out, |
359 | | typename ARRAY_TRAITS::ElementType element) |
360 | 192 | { |
361 | 192 | m_previousElement = static_cast<uint64_t>(element); |
362 | 192 | ARRAY_TRAITS::write(owner, out, element); |
363 | 192 | } |
364 | | |
365 | | template <typename ARRAY_TRAITS, |
366 | | typename std::enable_if<!has_owner_type<ARRAY_TRAITS>::value, int>::type = 0> |
367 | | void writeUnpacked(const DummyOwner&, BitStreamWriter& out, typename ARRAY_TRAITS::ElementType element) |
368 | 2.27k | { |
369 | 2.27k | m_previousElement = static_cast<uint64_t>(element); |
370 | 2.27k | ARRAY_TRAITS::write(out, element); |
371 | 2.27k | } |
372 | | |
373 | | void setFlag(uint8_t flagMask) |
374 | 14.7k | { |
375 | 14.7k | m_flags |= flagMask; |
376 | 14.7k | } |
377 | | |
378 | | void resetFlag(uint8_t flagMask) |
379 | 1.72k | { |
380 | 1.72k | m_flags &= static_cast<uint8_t>(~flagMask); |
381 | 1.72k | } |
382 | | |
383 | | bool isFlagSet(uint8_t flagMask) const |
384 | 43.5k | { |
385 | 43.5k | return ((m_flags & flagMask) != 0); |
386 | 43.5k | } |
387 | | |
388 | | static const uint8_t MAX_BIT_NUMBER_BITS = 6; |
389 | | static const uint8_t MAX_BIT_NUMBER_LIMIT = 62; |
390 | | |
391 | | static const uint8_t INIT_STARTED_FLAG = 0x01; |
392 | | static const uint8_t IS_PACKED_FLAG = 0x02; |
393 | | static const uint8_t PROCESSING_STARTED_FLAG = 0x04; |
394 | | |
395 | | uint64_t m_previousElement = 0; |
396 | | uint8_t m_maxBitNumber = 0; |
397 | | uint8_t m_flags = 0x00; |
398 | | |
399 | | uint8_t m_firstElementBitSize = 0; |
400 | | uint32_t m_numElements = 0; |
401 | | size_t m_unpackedBitSize = 0; |
402 | | }; |
403 | | |
404 | | } // namespace zserio |
405 | | |
406 | | #endif // ZSERIO_DELTA_CONTEXT_H_INC |