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>( |
104 | 8.54k | m_previousElement); |
105 | 8.54k | const uint8_t maxBitNumber = detail::calcBitLength(element, previousElement); |
106 | 8.54k | if (maxBitNumber > m_maxBitNumber) |
107 | 3.07k | { |
108 | 3.07k | m_maxBitNumber = maxBitNumber; |
109 | 3.07k | if (m_maxBitNumber > MAX_BIT_NUMBER_LIMIT) |
110 | 480 | resetFlag(IS_PACKED_FLAG); |
111 | 3.07k | } |
112 | 8.54k | m_previousElement = static_cast<uint64_t>(element); |
113 | 8.54k | } |
114 | 8.92k | } |
115 | 11.4k | } |
116 | | |
117 | | /** |
118 | | * Returns length of the packed element stored in the bit stream in bits. |
119 | | * |
120 | | * \param owner Owner of the packed element. |
121 | | * \param element Value of the current element. |
122 | | * |
123 | | * \return Length of the packed element stored in the bit stream in bits. |
124 | | */ |
125 | | template <typename ARRAY_TRAITS, typename OWNER_TYPE> |
126 | | size_t bitSizeOf(const OWNER_TYPE& owner, typename ARRAY_TRAITS::ElementType element) |
127 | 7.61k | { |
128 | 7.61k | if (!isFlagSet(PROCESSING_STARTED_FLAG)) |
129 | 1.66k | { |
130 | 1.66k | setFlag(PROCESSING_STARTED_FLAG); |
131 | 1.66k | finishInit(); |
132 | | |
133 | 1.66k | return bitSizeOfDescriptor() + bitSizeOfUnpacked<ARRAY_TRAITS>(owner, element); |
134 | 1.66k | } |
135 | 5.95k | else if (!isFlagSet(IS_PACKED_FLAG)) |
136 | 3.26k | { |
137 | 3.26k | return bitSizeOfUnpacked<ARRAY_TRAITS>(owner, element); |
138 | 3.26k | } |
139 | 2.68k | else |
140 | 2.68k | { |
141 | 2.68k | return m_maxBitNumber + (m_maxBitNumber > 0 ? 12.43k : 0256 ); |
142 | 2.68k | } |
143 | 7.61k | } |
144 | | |
145 | | /** |
146 | | * Reads a packed element from the bit stream. |
147 | | * |
148 | | * \param owner Owner of the packed element. |
149 | | * \param in Bit stream reader. |
150 | | * |
151 | | * \return Value of the packed element. |
152 | | */ |
153 | | template <typename ARRAY_TRAITS, typename OWNER_TYPE> |
154 | | typename ARRAY_TRAITS::ElementType read(const OWNER_TYPE& owner, BitStreamReader& in) |
155 | 3.80k | { |
156 | 3.80k | if (!isFlagSet(PROCESSING_STARTED_FLAG)) |
157 | 832 | { |
158 | 832 | setFlag(PROCESSING_STARTED_FLAG); |
159 | 832 | readDescriptor(in); |
160 | | |
161 | 832 | return readUnpacked<ARRAY_TRAITS>(owner, in); |
162 | 832 | } |
163 | 2.97k | else if (!isFlagSet(IS_PACKED_FLAG)) |
164 | 1.63k | { |
165 | 1.63k | return readUnpacked<ARRAY_TRAITS>(owner, in); |
166 | 1.63k | } |
167 | 1.34k | else |
168 | 1.34k | { |
169 | 1.34k | if (m_maxBitNumber > 0) |
170 | 1.21k | { |
171 | 1.21k | const int64_t delta = in.readSignedBits64(m_maxBitNumber + 1); |
172 | 1.21k | const typename ARRAY_TRAITS::ElementType element = |
173 | 1.21k | static_cast<typename ARRAY_TRAITS::ElementType>( |
174 | 1.21k | m_previousElement + static_cast<uint64_t>(delta)); |
175 | 1.21k | m_previousElement = static_cast<uint64_t>(element); |
176 | 1.21k | } |
177 | | |
178 | 1.34k | return static_cast<typename ARRAY_TRAITS::ElementType>(m_previousElement); |
179 | 1.34k | } |
180 | 3.80k | } |
181 | | |
182 | | /** |
183 | | * Writes the packed element to the bit stream. |
184 | | * |
185 | | * \param owner Owner of the packed element. |
186 | | * \param out Bit stream writer. |
187 | | * \param element Value of the current element. |
188 | | */ |
189 | | template <typename ARRAY_TRAITS, typename OWNER_TYPE> |
190 | | void write(const OWNER_TYPE& owner, BitStreamWriter& out, typename ARRAY_TRAITS::ElementType element) |
191 | 3.80k | { |
192 | 3.80k | if (!isFlagSet(PROCESSING_STARTED_FLAG)) |
193 | 832 | { |
194 | 832 | setFlag(PROCESSING_STARTED_FLAG); |
195 | 832 | finishInit(); |
196 | 832 | writeDescriptor(out); |
197 | | |
198 | 832 | writeUnpacked<ARRAY_TRAITS>(owner, out, element); |
199 | 832 | } |
200 | 2.97k | else if (!isFlagSet(IS_PACKED_FLAG)) |
201 | 1.63k | { |
202 | 1.63k | writeUnpacked<ARRAY_TRAITS>(owner, out, element); |
203 | 1.63k | } |
204 | 1.34k | else |
205 | 1.34k | { |
206 | 1.34k | if (m_maxBitNumber > 0) |
207 | 1.21k | { |
208 | | // it's already checked in the init phase that the delta will fit into int64_t |
209 | 1.21k | const int64_t delta = detail::calcUncheckedDelta(element, m_previousElement); |
210 | 1.21k | out.writeSignedBits64(delta, m_maxBitNumber + 1); |
211 | 1.21k | m_previousElement = static_cast<uint64_t>(element); |
212 | 1.21k | } |
213 | 1.34k | } |
214 | 3.80k | } |
215 | | |
216 | | // overloads with dummy owner |
217 | | |
218 | | /** |
219 | | * Calls the initialization step for a single element. |
220 | | * |
221 | | * \param element Current element. |
222 | | */ |
223 | | template <typename ARRAY_TRAITS> |
224 | | void init(typename ARRAY_TRAITS::ElementType element) |
225 | 10.8k | { |
226 | 10.8k | init<ARRAY_TRAITS>(DummyOwner(), element); |
227 | 10.8k | } |
228 | | |
229 | | /** |
230 | | * Returns length of the packed element stored in the bit stream in bits. |
231 | | * |
232 | | * \param element Value of the current element. |
233 | | * |
234 | | * \return Length of the packed element stored in the bit stream in bits. |
235 | | */ |
236 | | template <typename ARRAY_TRAITS> |
237 | | size_t bitSizeOf(typename ARRAY_TRAITS::ElementType element) |
238 | 7.23k | { |
239 | 7.23k | return bitSizeOf<ARRAY_TRAITS>(DummyOwner(), element); |
240 | 7.23k | } |
241 | | |
242 | | /** |
243 | | * Reads a packed element from the bit stream. |
244 | | * |
245 | | * \param in Bit stream reader. |
246 | | * |
247 | | * \return Value of the packed element. |
248 | | */ |
249 | | template <typename ARRAY_TRAITS> |
250 | | typename ARRAY_TRAITS::ElementType read(BitStreamReader& in) |
251 | 3.61k | { |
252 | 3.61k | return read<ARRAY_TRAITS>(DummyOwner(), in); |
253 | 3.61k | } |
254 | | |
255 | | /** |
256 | | * Writes the packed element to the bit stream. |
257 | | * |
258 | | * \param out Bit stream writer. |
259 | | * \param element Value of the current element. |
260 | | */ |
261 | | template <typename ARRAY_TRAITS> |
262 | | void write(BitStreamWriter& out, typename ARRAY_TRAITS::ElementType element) |
263 | 3.61k | { |
264 | 3.61k | write<ARRAY_TRAITS>(DummyOwner(), out, element); |
265 | 3.61k | } |
266 | | |
267 | | private: |
268 | | struct DummyOwner |
269 | | {}; |
270 | | |
271 | | void finishInit() |
272 | 2.49k | { |
273 | 2.49k | if (isFlagSet(IS_PACKED_FLAG)) |
274 | 1.82k | { |
275 | 1.82k | const size_t deltaBitSize = m_maxBitNumber + (m_maxBitNumber > 0 ? 11.63k : 0192 ); |
276 | 1.82k | const size_t packedBitSizeWithDescriptor = 1 + MAX_BIT_NUMBER_BITS + // descriptor |
277 | 1.82k | m_firstElementBitSize + (m_numElements - 1) * deltaBitSize; |
278 | 1.82k | const size_t unpackedBitSizeWithDescriptor = 1 + m_unpackedBitSize; |
279 | 1.82k | if (packedBitSizeWithDescriptor >= unpackedBitSizeWithDescriptor) |
280 | 768 | resetFlag(IS_PACKED_FLAG); |
281 | 1.82k | } |
282 | 2.49k | } |
283 | | |
284 | | size_t bitSizeOfDescriptor() const |
285 | 1.66k | { |
286 | 1.66k | if (isFlagSet(IS_PACKED_FLAG)) |
287 | 704 | return 1 + MAX_BIT_NUMBER_BITS; |
288 | 960 | else |
289 | 960 | return 1; |
290 | 1.66k | } |
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 | 960 | { |
297 | 960 | return ARRAY_TRAITS::bitSizeOf(owner, element); |
298 | 960 | } |
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 | 15.3k | { |
305 | 15.3k | return ARRAY_TRAITS::bitSizeOf(element); |
306 | 15.3k | } |
307 | | |
308 | | void readDescriptor(BitStreamReader& in) |
309 | 832 | { |
310 | 832 | if (in.readBool()) |
311 | 352 | { |
312 | 352 | setFlag(IS_PACKED_FLAG); |
313 | 352 | m_maxBitNumber = static_cast<uint8_t>(in.readBits(MAX_BIT_NUMBER_BITS)); |
314 | 352 | } |
315 | 480 | else |
316 | 480 | { |
317 | 480 | resetFlag(IS_PACKED_FLAG); |
318 | 480 | } |
319 | 832 | } |
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 | 192 | { |
326 | 192 | const auto element = ARRAY_TRAITS::read(owner, in); |
327 | 192 | m_previousElement = static_cast<uint64_t>(element); |
328 | 192 | return element; |
329 | 192 | } |
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 | 2.27k | { |
335 | 2.27k | const auto element = ARRAY_TRAITS::read(in); |
336 | 2.27k | m_previousElement = static_cast<uint64_t>(element); |
337 | 2.27k | return element; |
338 | 2.27k | } |
339 | | |
340 | | void writeDescriptor(BitStreamWriter& out) const |
341 | 832 | { |
342 | 832 | const bool isPacked = isFlagSet(IS_PACKED_FLAG); |
343 | 832 | out.writeBool(isPacked); |
344 | 832 | if (isPacked) |
345 | 352 | out.writeBits(m_maxBitNumber, MAX_BIT_NUMBER_BITS); |
346 | 832 | } |
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 | 192 | { |
353 | 192 | m_previousElement = static_cast<uint64_t>(element); |
354 | 192 | ARRAY_TRAITS::write(owner, out, element); |
355 | 192 | } |
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 | 2.27k | { |
361 | 2.27k | m_previousElement = static_cast<uint64_t>(element); |
362 | 2.27k | ARRAY_TRAITS::write(out, element); |
363 | 2.27k | } |
364 | | |
365 | | void setFlag(uint8_t flagMask) |
366 | 14.7k | { |
367 | 14.7k | m_flags |= flagMask; |
368 | 14.7k | } |
369 | | |
370 | | void resetFlag(uint8_t flagMask) |
371 | 1.72k | { |
372 | 1.72k | m_flags &= static_cast<uint8_t>(~flagMask); |
373 | 1.72k | } |
374 | | |
375 | | bool isFlagSet(uint8_t flagMask) const |
376 | 43.5k | { |
377 | 43.5k | return ((m_flags & flagMask) != 0); |
378 | 43.5k | } |
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 |