Coverage Report

Created: 2024-07-18 11:41

src/zserio/BitBuffer.h
Line
Count
Source
1
#ifndef ZSERIO_BIT_BUFFER_H_INC
2
#define ZSERIO_BIT_BUFFER_H_INC
3
4
#include <cstddef>
5
#include <cstring>
6
#include <type_traits>
7
#include <vector>
8
9
#include "zserio/CppRuntimeException.h"
10
#include "zserio/HashCodeUtil.h"
11
#include "zserio/Span.h"
12
#include "zserio/Types.h"
13
#include "zserio/Vector.h"
14
15
namespace zserio
16
{
17
18
/**
19
 * Bits helper structure used as a tag in BitStreamReader and BitStreamWriter constructor to pass number of bits
20
 * instead of number of bytes.
21
 */
22
struct BitsTag
23
{};
24
25
/**
26
 * Class which holds any bit sequence.
27
 *
28
 * Because bit buffer size does not have to be byte aligned (divisible by 8), it's possible that not all bits
29
 * of the last byte are used. In this case, only most significant bits of the corresponded size are used.
30
 */
31
template <typename ALLOC = std::allocator<uint8_t>>
32
class BasicBitBuffer
33
{
34
public:
35
    static_assert(std::is_same<uint8_t, typename ALLOC::value_type>::value,
36
            "Allocator with uint8_t value_type is required!");
37
38
    using allocator_type = ALLOC;
39
40
    /**
41
     * Get copy of the allocator used for dynamic memory allocations.
42
     *
43
     * \return Allocator used for dynamic memory allocations.
44
     */
45
    allocator_type get_allocator() const
46
    {
47
        return m_buffer.get_allocator();
48
    }
49
50
    /**
51
     * Empty constructor.
52
     *
53
     * \param allocator Allocator to use for internal vector allocation.
54
     */
55
    BasicBitBuffer();
56
57
    /**
58
     * Constructor from given allocator.
59
     *
60
     * \param allocator Allocator to use for internal vector allocation.
61
     */
62
    explicit BasicBitBuffer(const ALLOC& allocator);
63
64
    /**
65
     * Constructor from bit size.
66
     *
67
     * \param bitSize Size in bits of created bit buffer.
68
     * \param allocator Allocator to use for internal vector allocation.
69
     */
70
    explicit BasicBitBuffer(size_t bitSize, const ALLOC& allocator = ALLOC());
71
72
    /**
73
     * Constructor from span.
74
     *
75
     * \param buffer Span of bytes from which the bit buffer should be created.
76
     * \param allocator Allocator to use for internal vector allocation.
77
     */
78
    explicit BasicBitBuffer(Span<const uint8_t> buffer, const ALLOC& allocator = ALLOC());
79
80
    /**
81
     * Constructor from span and bit size.
82
     *
83
     * \param buffer Span of bytes from which the bit buffer should be created.
84
     * \param bitSize Number of bits stored in buffer to use.
85
     * \param allocator Allocator to use for internal vector allocation.
86
     *
87
     * \throw CppRuntimeException If given bit size is out of range for given Span.
88
     */
89
    explicit BasicBitBuffer(Span<const uint8_t> buffer, size_t bitSize, const ALLOC& allocator = ALLOC());
90
91
    /**
92
     * Constructor from moved STL vector.
93
     *
94
     * \param buffer STL vector of bytes from which the bit buffer should be created.
95
     */
96
    explicit BasicBitBuffer(vector<uint8_t, ALLOC>&& buffer);
97
98
    /**
99
     * Constructor from moved STL vector and bit size.
100
     *
101
     * \param buffer STL vector of bytes from which the bit buffer should be created.
102
     * \param bitSize Number of bits stored in buffer to use.
103
     *
104
     * \throw CppRuntimeException If given bit size is out of range for given vector.
105
     */
106
    explicit BasicBitBuffer(vector<uint8_t, ALLOC>&& buffer, size_t bitSize);
107
108
    /**
109
     * Constructor from raw pointer.
110
     *
111
     * \param buffer Raw pointer to all bytes from which the bit buffer should be created.
112
     * \param bitSize Number of bits stored in buffer to use.
113
     * \param allocator Allocator to use for internal vector allocation.
114
     */
115
    explicit BasicBitBuffer(const uint8_t* buffer, size_t bitSize, const ALLOC& allocator = ALLOC());
116
117
    /**
118
     * Method generated by default.
119
     * \{
120
     */
121
1.57k
    ~BasicBitBuffer() = default;
122
123
407
    BasicBitBuffer(const BasicBitBuffer<ALLOC>&) = default;
124
    BasicBitBuffer(const BasicBitBuffer<ALLOC>& other, const ALLOC& allocator);
125
12
    BasicBitBuffer& operator=(const BasicBitBuffer<ALLOC>&) = default;
126
127
211
    BasicBitBuffer(BasicBitBuffer<ALLOC>&&) = default;
128
    BasicBitBuffer(const BasicBitBuffer<ALLOC>&& other, const ALLOC& allocator);
129
1
    BasicBitBuffer& operator=(BasicBitBuffer<ALLOC>&&) = default;
130
    /**
131
     * \}
132
     */
133
134
    /**
135
     * Equal operator.
136
     *
137
     * \param other The another instance of bit buffer to which compare this bit buffer.
138
     *
139
     * \return True when the bit buffers have same contents, false otherwise.
140
     */
141
    bool operator==(const BasicBitBuffer<ALLOC>& other) const;
142
143
    /**
144
     * Operator less than.
145
     *
146
     * \param other The another instance of bit buffer to which compare this bit buffer.
147
     *
148
     * \return True when this bit buffer is less than the other (using lexicographical compare).
149
     */
150
    bool operator<(const BasicBitBuffer<ALLOC>& other) const;
151
152
    /**
153
     * Calculates hash code of the bit buffer.
154
     *
155
     * \return Calculated hash code.
156
     */
157
    uint32_t hashCode() const;
158
159
    /**
160
     * Gets the underlying buffer.
161
     *
162
     * \return Pointer to the constant underlying buffer.
163
     */
164
    const uint8_t* getBuffer() const;
165
166
    /**
167
     * Gets the underlying buffer.
168
     *
169
     * \return Pointer to the underlying buffer.
170
     */
171
    uint8_t* getBuffer();
172
173
    /**
174
     * Gets the number of bits stored in the bit buffer.
175
     *
176
     * \return Bit buffer size in bits.
177
     */
178
    size_t getBitSize() const;
179
180
    /**
181
     * Gets the number of bytes stored in the bit buffer.
182
     *
183
     * Not all bits of the last byte must be used. Unused bits of the last byte are set to zero.
184
     *
185
     * \return Bit buffer size in bytes.
186
     */
187
    size_t getByteSize() const;
188
189
    /**
190
     * Convenience getter for the underlying buffer.
191
     *
192
     * \return Reference to the underlying vector of bytes.
193
     */
194
    const vector<uint8_t, ALLOC>& getBytes() const;
195
196
    /**
197
     * Convenience getter for the underlying buffer.
198
     *
199
     * \return The span to the underlying vector of bytes.
200
     */
201
    Span<const uint8_t> getData() const;
202
203
    /**
204
     * Convenience getter for the underlying buffer.
205
     *
206
     * \return The span to the underlying vector of bytes.
207
     */
208
    Span<uint8_t> getData();
209
210
private:
211
    uint8_t getMaskedLastByte() const;
212
213
    vector<uint8_t, ALLOC> m_buffer;
214
    size_t m_bitSize;
215
};
216
217
template <typename ALLOC>
218
BasicBitBuffer<ALLOC>::BasicBitBuffer() :
219
        m_buffer(ALLOC()),
220
        m_bitSize(0)
221
32
{}
222
223
template <typename ALLOC>
224
BasicBitBuffer<ALLOC>::BasicBitBuffer(const ALLOC& allocator) :
225
        m_buffer(allocator),
226
        m_bitSize(0)
227
58
{}
228
229
template <typename ALLOC>
230
BasicBitBuffer<ALLOC>::BasicBitBuffer(size_t bitSize, const ALLOC& allocator) :
231
        m_buffer((bitSize + 7) / 8, 0, allocator),
232
        m_bitSize(bitSize)
233
662
{}
234
235
template <typename ALLOC>
236
BasicBitBuffer<ALLOC>::BasicBitBuffer(Span<const uint8_t> buffer, const ALLOC& allocator) :
237
        m_buffer(buffer.begin(), buffer.end(), allocator),
238
        m_bitSize(8 * buffer.size())
239
7
{}
240
241
template <typename ALLOC>
242
BasicBitBuffer<ALLOC>::BasicBitBuffer(Span<const uint8_t> buffer, size_t bitSize, const ALLOC& allocator) :
243
        m_buffer(buffer.begin(), buffer.end(), allocator),
244
        m_bitSize(bitSize)
245
33
{
246
33
    const size_t byteSize = (bitSize + 7) / 8;
247
33
    if (buffer.size() < byteSize)
248
1
    {
249
1
        throw CppRuntimeException("BitBuffer: Bit size ")
250
1
                << bitSize << " out of range for given span byte size " << buffer.size() << "!";
251
1
    }
252
33
}
253
254
template <typename ALLOC>
255
BasicBitBuffer<ALLOC>::BasicBitBuffer(vector<uint8_t, ALLOC>&& buffer) :
256
        m_buffer(std::move(buffer)),
257
        m_bitSize(8 * m_buffer.size())
258
4
{}
259
260
template <typename ALLOC>
261
BasicBitBuffer<ALLOC>::BasicBitBuffer(vector<uint8_t, ALLOC>&& buffer, size_t bitSize) :
262
        m_buffer(std::move(buffer)),
263
        m_bitSize(bitSize)
264
48
{
265
48
    const size_t byteSize = (bitSize + 7) / 8;
266
48
    if (m_buffer.size() < byteSize)
267
1
    {
268
1
        throw CppRuntimeException("BitBuffer: Bit size ")
269
1
                << bitSize << " out of range for given vector byte size " << m_buffer.size() << "!";
270
1
    }
271
48
}
272
273
template <typename ALLOC>
274
BasicBitBuffer<ALLOC>::BasicBitBuffer(const uint8_t* buffer, size_t bitSize, const ALLOC& allocator) :
275
        m_buffer(buffer, buffer + (bitSize + 7) / 8, allocator),
276
        m_bitSize(bitSize)
277
15
{}
278
279
template <typename ALLOC>
280
inline BasicBitBuffer<ALLOC>::BasicBitBuffer(const BasicBitBuffer<ALLOC>& other, const ALLOC& allocator) :
281
        m_buffer(other.m_buffer, allocator),
282
        m_bitSize(other.m_bitSize)
283
97
{}
284
285
template <typename ALLOC>
286
inline BasicBitBuffer<ALLOC>::BasicBitBuffer(const BasicBitBuffer<ALLOC>&& other, const ALLOC& allocator) :
287
        m_buffer(std::move(other.m_buffer), allocator),
288
        m_bitSize(other.m_bitSize)
289
1
{}
290
291
template <typename ALLOC>
292
bool BasicBitBuffer<ALLOC>::operator==(const BasicBitBuffer<ALLOC>& other) const
293
1.11k
{
294
1.11k
    if (this != &other)
295
1.10k
    {
296
1.10k
        if (m_bitSize != other.m_bitSize)
297
3
        {
298
3
            return false;
299
3
        }
300
301
1.10k
        const size_t byteSize = getByteSize();
302
1.10k
        if (byteSize > 0)
303
1.09k
        {
304
1.09k
            if (byteSize > 1)
305
1.09k
            {
306
1.09k
                if (memcmp(getBuffer(), other.getBuffer(), byteSize - 1) != 0)
307
1
                {
308
1
                    return false;
309
1
                }
310
1.09k
            }
311
312
1.09k
            if (getMaskedLastByte() != other.getMaskedLastByte())
313
1
            {
314
1
                return false;
315
1
            }
316
1.09k
        }
317
1.10k
    }
318
319
1.11k
    return true;
320
1.11k
}
321
322
template <typename ALLOC>
323
bool BasicBitBuffer<ALLOC>::operator<(const BasicBitBuffer<ALLOC>& other) const
324
402
{
325
402
    const size_t byteSize1 = getByteSize();
326
402
    const size_t byteSize2 = other.getByteSize();
327
328
402
    if (byteSize1 == 0)
329
3
    {
330
3
        return byteSize2 != 0;
331
3
    }
332
399
    if (byteSize2 == 0)
333
1
    {
334
1
        return false;
335
1
    }
336
337
398
    using difference_type = typename vector<uint8_t, ALLOC>::iterator::difference_type;
338
339
398
    auto first1 = m_buffer.begin();
340
398
    const auto last1 = first1 + static_cast<difference_type>(byteSize1 - 1);
341
398
    auto first2 = other.m_buffer.begin();
342
398
    const auto last2 = first2 + static_cast<difference_type>(byteSize2 - 1);
343
790
    for (; (first1 != last1) && 
(first2 != last2)396
;
++first1, ++first2392
)
344
394
    {
345
394
        if (*first1 < *first2)
346
1
        {
347
1
            return true;
348
1
        }
349
393
        if (*first2 < *first1)
350
1
        {
351
1
            return false;
352
1
        }
353
393
    }
354
355
396
    const auto lastValue1 = first1 != last1 ? 
*first12
:
getMaskedLastByte()394
;
356
396
    const auto lastValue2 = first2 != last2 ? 
*first22
:
other.getMaskedLastByte()394
;
357
396
    if (lastValue1 < lastValue2)
358
2
    {
359
2
        return true;
360
2
    }
361
394
    if (lastValue2 < lastValue1)
362
2
    {
363
2
        return false;
364
2
    }
365
366
392
    return (first1 == last1) && 
(first2 != last2)390
;
367
394
}
368
369
template <typename ALLOC>
370
uint32_t BasicBitBuffer<ALLOC>::hashCode() const
371
14
{
372
14
    uint32_t result = ::zserio::HASH_SEED;
373
14
    const size_t byteSize = getByteSize();
374
14
    if (byteSize > 0)
375
11
    {
376
11
        if (byteSize > 1)
377
10
        {
378
10
            auto lastIt = m_buffer.begin() + static_cast<int>(byteSize) - 1;
379
20
            for (auto it = m_buffer.begin(); it != lastIt; 
++it10
)
380
10
            {
381
10
                result = calcHashCode(result, *it);
382
10
            }
383
10
        }
384
11
        result = ::zserio::calcHashCode(result, getMaskedLastByte());
385
11
    }
386
387
14
    return result;
388
14
}
389
390
template <typename ALLOC>
391
const uint8_t* BasicBitBuffer<ALLOC>::getBuffer() const
392
2.18k
{
393
2.18k
    return m_buffer.data();
394
2.18k
}
395
396
template <typename ALLOC>
397
uint8_t* BasicBitBuffer<ALLOC>::getBuffer()
398
75
{
399
75
    return m_buffer.data();
400
75
}
401
402
template <typename ALLOC>
403
size_t BasicBitBuffer<ALLOC>::getBitSize() const
404
1.28k
{
405
1.28k
    return m_bitSize;
406
1.28k
}
407
408
template <typename ALLOC>
409
size_t BasicBitBuffer<ALLOC>::getByteSize() const
410
2.00k
{
411
2.00k
    return (m_bitSize + 7) / 8;
412
2.00k
}
413
414
template <typename ALLOC>
415
const vector<uint8_t, ALLOC>& BasicBitBuffer<ALLOC>::getBytes() const
416
10
{
417
10
    return m_buffer;
418
10
}
419
420
template <typename ALLOC>
421
Span<const uint8_t> BasicBitBuffer<ALLOC>::getData() const
422
566
{
423
566
    return Span<const uint8_t>(m_buffer);
424
566
}
425
426
template <typename ALLOC>
427
Span<uint8_t> BasicBitBuffer<ALLOC>::getData()
428
971
{
429
971
    return Span<uint8_t>(m_buffer);
430
971
}
431
432
template <typename ALLOC>
433
uint8_t BasicBitBuffer<ALLOC>::getMaskedLastByte() const
434
2.99k
{
435
2.99k
    const size_t roundedByteSize = m_bitSize / 8;
436
2.99k
    const uint8_t lastByteBits = static_cast<uint8_t>(m_bitSize - 8 * roundedByteSize);
437
438
2.99k
    return (lastByteBits == 0)
439
2.99k
            ? 
m_buffer[roundedByteSize - 1]23
440
2.99k
            : 
static_cast<uint8_t>(m_buffer[roundedByteSize] & (0xFFU << (8U - lastByteBits)))2.96k
;
441
2.99k
}
442
443
/** Typedef to BitBuffer provided for convenience - using std::allocator<uint8_t>. */
444
using BitBuffer = BasicBitBuffer<>;
445
446
/**
447
 * Allows to append BitBuffer to CppRuntimeException.
448
 *
449
 * \param exception Exception to modify.
450
 * \param bitBuffer Bit buffer value.
451
 *
452
 * \return Reference to the exception to allow operator chaining.
453
 */
454
template <typename ALLOC>
455
CppRuntimeException& operator<<(CppRuntimeException& exception, const BasicBitBuffer<ALLOC>& bitBuffer)
456
12
{
457
12
    return exception << "BitBuffer([...], " << bitBuffer.getBitSize() << ")";
458
12
}
459
460
} // namespace zserio
461
462
#endif // ifndef ZSERIO_BIT_BUFFER_H_INC