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