Coverage Report

Created: 2024-07-18 11:41

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