Coverage Report

Created: 2024-04-30 09:35

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
            return false;
298
299
1.10k
        const size_t byteSize = getByteSize();
300
1.10k
        if (byteSize > 0)
301
1.09k
        {
302
1.09k
            if (byteSize > 1)
303
1.09k
            {
304
1.09k
                if (memcmp(getBuffer(), other.getBuffer(), byteSize - 1) != 0)
305
1
                    return false;
306
1.09k
            }
307
308
1.09k
            if (getMaskedLastByte() != other.getMaskedLastByte())
309
1
                return false;
310
1.09k
        }
311
1.10k
    }
312
313
1.11k
    return true;
314
1.11k
}
315
316
template <typename ALLOC>
317
bool BasicBitBuffer<ALLOC>::operator<(const BasicBitBuffer<ALLOC>& other) const
318
402
{
319
402
    const size_t byteSize1 = getByteSize();
320
402
    const size_t byteSize2 = other.getByteSize();
321
322
402
    if (byteSize1 == 0)
323
3
        return byteSize2 != 0;
324
399
    if (byteSize2 == 0)
325
1
        return false;
326
327
398
    using difference_type = typename vector<uint8_t, ALLOC>::iterator::difference_type;
328
329
398
    auto first1 = m_buffer.begin();
330
398
    const auto last1 = first1 + static_cast<difference_type>(byteSize1 - 1);
331
398
    auto first2 = other.m_buffer.begin();
332
398
    const auto last2 = first2 + static_cast<difference_type>(byteSize2 - 1);
333
790
    for (; (first1 != last1) && 
(first2 != last2)396
;
++first1, ++first2392
)
334
394
    {
335
394
        if (*first1 < *first2)
336
1
            return true;
337
393
        if (*first2 < *first1)
338
1
            return false;
339
393
    }
340
341
396
    const auto lastValue1 = first1 != last1 ? 
*first12
:
getMaskedLastByte()394
;
342
396
    const auto lastValue2 = first2 != last2 ? 
*first22
:
other.getMaskedLastByte()394
;
343
396
    if (lastValue1 < lastValue2)
344
2
        return true;
345
394
    if (lastValue2 < lastValue1)
346
2
        return false;
347
348
392
    return (first1 == last1) && 
(first2 != last2)390
;
349
394
}
350
351
template <typename ALLOC>
352
uint32_t BasicBitBuffer<ALLOC>::hashCode() const
353
14
{
354
14
    uint32_t result = ::zserio::HASH_SEED;
355
14
    const size_t byteSize = getByteSize();
356
14
    if (byteSize > 0)
357
11
    {
358
11
        if (byteSize > 1)
359
10
        {
360
10
            auto lastIt = m_buffer.begin() + static_cast<int>(byteSize) - 1;
361
20
            for (auto it = m_buffer.begin(); it != lastIt; 
++it10
)
362
10
                result = calcHashCode(result, *it);
363
10
        }
364
11
        result = ::zserio::calcHashCode(result, getMaskedLastByte());
365
11
    }
366
367
14
    return result;
368
14
}
369
370
template <typename ALLOC>
371
const uint8_t* BasicBitBuffer<ALLOC>::getBuffer() const
372
2.18k
{
373
2.18k
    return m_buffer.data();
374
2.18k
}
375
376
template <typename ALLOC>
377
uint8_t* BasicBitBuffer<ALLOC>::getBuffer()
378
75
{
379
75
    return m_buffer.data();
380
75
}
381
382
template <typename ALLOC>
383
size_t BasicBitBuffer<ALLOC>::getBitSize() const
384
1.28k
{
385
1.28k
    return m_bitSize;
386
1.28k
}
387
388
template <typename ALLOC>
389
size_t BasicBitBuffer<ALLOC>::getByteSize() const
390
2.00k
{
391
2.00k
    return (m_bitSize + 7) / 8;
392
2.00k
}
393
394
template <typename ALLOC>
395
const vector<uint8_t, ALLOC>& BasicBitBuffer<ALLOC>::getBytes() const
396
10
{
397
10
    return m_buffer;
398
10
}
399
400
template <typename ALLOC>
401
Span<const uint8_t> BasicBitBuffer<ALLOC>::getData() const
402
566
{
403
566
    return Span<const uint8_t>(m_buffer);
404
566
}
405
406
template <typename ALLOC>
407
Span<uint8_t> BasicBitBuffer<ALLOC>::getData()
408
971
{
409
971
    return Span<uint8_t>(m_buffer);
410
971
}
411
412
template <typename ALLOC>
413
uint8_t BasicBitBuffer<ALLOC>::getMaskedLastByte() const
414
2.99k
{
415
2.99k
    const size_t roundedByteSize = m_bitSize / 8;
416
2.99k
    const uint8_t lastByteBits = static_cast<uint8_t>(m_bitSize - 8 * roundedByteSize);
417
418
2.99k
    return (lastByteBits == 0)
419
2.99k
            ? 
m_buffer[roundedByteSize - 1]23
420
2.99k
            : 
static_cast<uint8_t>(m_buffer[roundedByteSize] & (0xFFU << (8U - lastByteBits)))2.96k
;
421
2.99k
}
422
423
/** Typedef to BitBuffer provided for convenience - using std::allocator<uint8_t>. */
424
using BitBuffer = BasicBitBuffer<>;
425
426
/**
427
 * Allows to append BitBuffer to CppRuntimeException.
428
 *
429
 * \param exception Exception to modify.
430
 * \param bitBuffer Bit buffer value.
431
 *
432
 * \return Reference to the exception to allow operator chaining.
433
 */
434
template <typename ALLOC>
435
CppRuntimeException& operator<<(CppRuntimeException& exception, const BasicBitBuffer<ALLOC>& bitBuffer)
436
12
{
437
12
    return exception << "BitBuffer([...], " << bitBuffer.getBitSize() << ")";
438
12
}
439
440
} // namespace zserio
441
442
#endif // ifndef ZSERIO_BIT_BUFFER_H_INC