GCC Code Coverage Report
Directory: ./ Exec Total Coverage
File: src/zserio/DeltaContext.h Lines: 124 124 100.0 %
Date: 2023-12-13 14:51:09 Branches: 238 392 60.7 %

Line Branch Exec 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
8544
inline uint8_t absDeltaBitLength(uint64_t absDelta)
22
{
23
8544
    uint8_t result = 0;
24
237024
    while (absDelta > 0)
25
    {
26
114240
        result++;
27
114240
        absDelta >>= 1U;
28
    }
29
30
8544
    return result;
31
}
32
33
// calculates bit length, emulates Python bit_length to keep same logic
34
template <typename T>
35
8544
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



8544
            : static_cast<uint64_t>(rhs) - static_cast<uint64_t>(lhs);
40
41
8544
    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
1216
int64_t calcUncheckedDelta(T lhs, uint64_t rhs)
48
{
49
1216
    return static_cast<int64_t>(static_cast<uint64_t>(lhs) - rhs);
50
}
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
    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
11424
    void init(const OWNER_TYPE& owner, typename ARRAY_TRAITS::ElementType element)
88
    {
89
11424
        m_numElements++;
90
11424
        m_unpackedBitSize += bitSizeOfUnpacked<ARRAY_TRAITS>(owner, element);
91
92





11424
        if (!isFlagSet(INIT_STARTED_FLAG))
93
        {
94
2496
            setFlag(INIT_STARTED_FLAG);
95
2496
            m_previousElement = static_cast<uint64_t>(element);
96
2496
            m_firstElementBitSize = static_cast<uint8_t>(m_unpackedBitSize);
97
        }
98
        else
99
        {
100





8928
            if (m_maxBitNumber <= MAX_BIT_NUMBER_LIMIT)
101
            {
102
8544
                setFlag(IS_PACKED_FLAG);
103
                const auto previousElement = static_cast<typename ARRAY_TRAITS::ElementType>(
104
8544
                        m_previousElement);
105
8544
                const uint8_t maxBitNumber = detail::calcBitLength(element, previousElement);
106





8544
                if (maxBitNumber > m_maxBitNumber)
107
                {
108
3072
                    m_maxBitNumber = maxBitNumber;
109





3072
                    if (m_maxBitNumber > MAX_BIT_NUMBER_LIMIT)
110
480
                        resetFlag(IS_PACKED_FLAG);
111
                }
112
8544
                m_previousElement = static_cast<uint64_t>(element);
113
            }
114
        }
115
11424
    }
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
7616
    size_t bitSizeOf(const OWNER_TYPE& owner, typename ARRAY_TRAITS::ElementType element)
127
    {
128





7616
        if (!isFlagSet(PROCESSING_STARTED_FLAG))
129
        {
130
1664
            setFlag(PROCESSING_STARTED_FLAG);
131
1664
            finishInit();
132
133
1664
            return bitSizeOfDescriptor() + bitSizeOfUnpacked<ARRAY_TRAITS>(owner, element);
134
        }
135





5952
        else if (!isFlagSet(IS_PACKED_FLAG))
136
        {
137
3264
            return bitSizeOfUnpacked<ARRAY_TRAITS>(owner, element);
138
        }
139
        else
140
        {
141





2688
            return m_maxBitNumber + (m_maxBitNumber > 0 ? 1 : 0);
142
        }
143
    }
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
3808
    typename ARRAY_TRAITS::ElementType read(const OWNER_TYPE& owner, BitStreamReader& in)
155
    {
156





3808
        if (!isFlagSet(PROCESSING_STARTED_FLAG))
157
        {
158
832
            setFlag(PROCESSING_STARTED_FLAG);
159
832
            readDescriptor(in);
160
161
832
            return readUnpacked<ARRAY_TRAITS>(owner, in);
162
        }
163





2976
        else if (!isFlagSet(IS_PACKED_FLAG))
164
        {
165
1632
            return readUnpacked<ARRAY_TRAITS>(owner, in);
166
        }
167
        else
168
        {
169





1344
            if (m_maxBitNumber > 0)
170
            {
171
1216
                const int64_t delta = in.readSignedBits64(m_maxBitNumber + 1);
172
                const typename ARRAY_TRAITS::ElementType element =
173
                        static_cast<typename ARRAY_TRAITS::ElementType>(
174
1216
                                m_previousElement + static_cast<uint64_t>(delta));
175
1216
                m_previousElement = static_cast<uint64_t>(element);
176
            }
177
178
1344
            return static_cast<typename ARRAY_TRAITS::ElementType>(m_previousElement);
179
        }
180
    }
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
3808
    void write(const OWNER_TYPE& owner, BitStreamWriter& out, typename ARRAY_TRAITS::ElementType element)
191
    {
192





3808
        if (!isFlagSet(PROCESSING_STARTED_FLAG))
193
        {
194
832
            setFlag(PROCESSING_STARTED_FLAG);
195
832
            finishInit();
196
832
            writeDescriptor(out);
197
198
832
            writeUnpacked<ARRAY_TRAITS>(owner, out, element);
199
        }
200





2976
        else if (!isFlagSet(IS_PACKED_FLAG))
201
        {
202
1632
            writeUnpacked<ARRAY_TRAITS>(owner, out, element);
203
        }
204
        else
205
        {
206





1344
            if (m_maxBitNumber > 0)
207
            {
208
                // it's already checked in the init phase that the delta will fit into int64_t
209
1216
                const int64_t delta = detail::calcUncheckedDelta(element, m_previousElement);
210
1216
                out.writeSignedBits64(delta, m_maxBitNumber + 1);
211
1216
                m_previousElement = static_cast<uint64_t>(element);
212
            }
213
        }
214
3808
    }
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
10848
    void init(typename ARRAY_TRAITS::ElementType element)
225
    {
226





10848
        init<ARRAY_TRAITS>(DummyOwner(), element);
227
10848
    }
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
7232
    size_t bitSizeOf(typename ARRAY_TRAITS::ElementType element)
238
    {
239





7232
        return bitSizeOf<ARRAY_TRAITS>(DummyOwner(), element);
240
    }
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
3616
    typename ARRAY_TRAITS::ElementType read(BitStreamReader& in)
251
    {
252





3616
        return read<ARRAY_TRAITS>(DummyOwner(), in);
253
    }
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
3616
    void write(BitStreamWriter& out, typename ARRAY_TRAITS::ElementType element)
263
    {
264





3616
        write<ARRAY_TRAITS>(DummyOwner(), out, element);
265
3616
    }
266
267
private:
268
    struct DummyOwner
269
    {};
270
271
2496
    void finishInit()
272
    {
273
2496
        if (isFlagSet(IS_PACKED_FLAG))
274
        {
275
1824
            const size_t deltaBitSize = m_maxBitNumber + (m_maxBitNumber > 0 ? 1 : 0);
276
1824
            const size_t packedBitSizeWithDescriptor = 1 + MAX_BIT_NUMBER_BITS + // descriptor
277
3648
                    m_firstElementBitSize + (m_numElements - 1) * deltaBitSize;
278
1824
            const size_t unpackedBitSizeWithDescriptor = 1 + m_unpackedBitSize;
279
1824
            if (packedBitSizeWithDescriptor >= unpackedBitSizeWithDescriptor)
280
768
                resetFlag(IS_PACKED_FLAG);
281
        }
282
2496
    }
283
284
1664
    size_t bitSizeOfDescriptor() const
285
    {
286
1664
        if (isFlagSet(IS_PACKED_FLAG))
287
704
            return 1 + MAX_BIT_NUMBER_BITS;
288
        else
289
960
            return 1;
290
    }
291
292
    template <typename ARRAY_TRAITS,
293
            typename std::enable_if<has_owner_type<ARRAY_TRAITS>::value, int>::type = 0>
294
960
    static size_t bitSizeOfUnpacked(const typename ARRAY_TRAITS::OwnerType& owner,
295
            typename ARRAY_TRAITS::ElementType element)
296
    {
297
960
        return ARRAY_TRAITS::bitSizeOf(owner, element);
298
    }
299
300
    template <typename ARRAY_TRAITS,
301
            typename std::enable_if<!has_owner_type<ARRAY_TRAITS>::value, int>::type = 0>
302
15392
    static size_t bitSizeOfUnpacked(const DummyOwner&,
303
            typename ARRAY_TRAITS::ElementType element)
304
    {
305
15392
        return ARRAY_TRAITS::bitSizeOf(element);
306
    }
307
308
832
    void readDescriptor(BitStreamReader& in)
309
    {
310
832
        if (in.readBool())
311
        {
312
352
            setFlag(IS_PACKED_FLAG);
313
352
            m_maxBitNumber = static_cast<uint8_t>(in.readBits(MAX_BIT_NUMBER_BITS));
314
        }
315
        else
316
        {
317
480
            resetFlag(IS_PACKED_FLAG);
318
        }
319
832
    }
320
321
    template <typename ARRAY_TRAITS,
322
            typename std::enable_if<has_owner_type<ARRAY_TRAITS>::value, int>::type = 0>
323
192
    typename ARRAY_TRAITS::ElementType readUnpacked(const typename ARRAY_TRAITS::OwnerType& owner,
324
            BitStreamReader& in)
325
    {
326
192
        const auto element = ARRAY_TRAITS::read(owner, in);
327
192
        m_previousElement = static_cast<uint64_t>(element);
328
192
        return element;
329
    }
330
331
    template <typename ARRAY_TRAITS,
332
            typename std::enable_if<!has_owner_type<ARRAY_TRAITS>::value, int>::type = 0>
333
2272
    typename ARRAY_TRAITS::ElementType readUnpacked(const DummyOwner&, BitStreamReader& in)
334
    {
335
2272
        const auto element = ARRAY_TRAITS::read(in);
336
2272
        m_previousElement = static_cast<uint64_t>(element);
337
2272
        return element;
338
    }
339
340
832
    void writeDescriptor(BitStreamWriter& out) const
341
    {
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
192
    void writeUnpacked(const typename ARRAY_TRAITS::OwnerType& owner,
351
            BitStreamWriter& out, typename ARRAY_TRAITS::ElementType element)
352
    {
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
2272
    void writeUnpacked(const DummyOwner&, BitStreamWriter& out, typename ARRAY_TRAITS::ElementType element)
360
    {
361
2272
        m_previousElement = static_cast<uint64_t>(element);
362
2272
        ARRAY_TRAITS::write(out, element);
363
2272
    }
364
365
14720
    void setFlag(uint8_t flagMask)
366
    {
367
14720
        m_flags |= flagMask;
368
14720
    }
369
370
1728
    void resetFlag(uint8_t flagMask)
371
    {
372
1728
        m_flags &= static_cast<uint8_t>(~flagMask);
373
1728
    }
374
375
43552
    bool isFlagSet(uint8_t flagMask) const
376
    {
377
43552
        return ((m_flags & flagMask) != 0);
378
    }
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