Coverage Report

Created: 2023-12-13 14:58

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 <vector>
7
#include <type_traits>
8
9
#include "zserio/Types.h"
10
#include "zserio/HashCodeUtil.h"
11
#include "zserio/CppRuntimeException.h"
12
#include "zserio/Vector.h"
13
#include "zserio/Span.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.56k
    ~BasicBitBuffer() = default;
122
123
407
    BasicBitBuffer(const BasicBitBuffer<ALLOC>&) = default;
124
    BasicBitBuffer(const BasicBitBuffer<ALLOC>& other, const ALLOC& allocator);
125
10
    BasicBitBuffer& operator=(const BasicBitBuffer<ALLOC>&) = default;
126
127
209
    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()), m_bitSize(0)
220
30
{
221
30
}
222
223
template <typename ALLOC>
224
BasicBitBuffer<ALLOC>::BasicBitBuffer(const ALLOC& allocator) :
225
        m_buffer(allocator), m_bitSize(0)
226
56
{
227
56
}
228
229
template <typename ALLOC>
230
BasicBitBuffer<ALLOC>::BasicBitBuffer(size_t bitSize, const ALLOC& allocator) :
231
        m_buffer((bitSize + 7) / 8, 0, allocator), m_bitSize(bitSize)
232
662
{
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), m_bitSize(8 * buffer.size())
238
7
{
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), m_bitSize(bitSize)
244
31
{
245
31
    const size_t byteSize = (bitSize + 7) / 8;
246
31
    if (buffer.size() < byteSize)
247
1
    {
248
1
        throw CppRuntimeException("BitBuffer: Bit size ") << bitSize <<
249
1
                " out of range for given span byte size " << buffer.size() << "!";
250
1
    }
251
31
}
252
253
template <typename ALLOC>
254
BasicBitBuffer<ALLOC>::BasicBitBuffer(vector<uint8_t, ALLOC>&& buffer) :
255
        m_buffer(std::move(buffer)), m_bitSize(8 * m_buffer.size())
256
4
{
257
4
}
258
259
template <typename ALLOC>
260
BasicBitBuffer<ALLOC>::BasicBitBuffer(vector<uint8_t, ALLOC>&& buffer, size_t bitSize) :
261
        m_buffer(std::move(buffer)), m_bitSize(bitSize)
262
48
{
263
48
    const size_t byteSize = (bitSize + 7) / 8;
264
48
    if (m_buffer.size() < byteSize)
265
1
    {
266
1
        throw CppRuntimeException("BitBuffer: Bit size ") << bitSize <<
267
1
                " out of range for given vector byte size " << m_buffer.size() << "!";
268
1
    }
269
48
}
270
271
template <typename ALLOC>
272
BasicBitBuffer<ALLOC>::BasicBitBuffer(const uint8_t* buffer, size_t bitSize, const ALLOC& allocator) :
273
        m_buffer(buffer, buffer + (bitSize + 7) / 8, allocator), m_bitSize(bitSize)
274
15
{
275
15
}
276
277
template<typename ALLOC>
278
inline BasicBitBuffer<ALLOC>::BasicBitBuffer(const BasicBitBuffer<ALLOC>& other, const ALLOC& allocator) :
279
        m_buffer(other.m_buffer, allocator), m_bitSize(other.m_bitSize)
280
97
{
281
97
}
282
283
template<typename ALLOC>
284
inline BasicBitBuffer<ALLOC>::BasicBitBuffer(const BasicBitBuffer<ALLOC>&& other, const ALLOC& allocator) :
285
        m_buffer(std::move(other.m_buffer), allocator), m_bitSize(other.m_bitSize)
286
1
{
287
1
}
288
289
template <typename ALLOC>
290
bool BasicBitBuffer<ALLOC>::operator==(const BasicBitBuffer<ALLOC>& other) const
291
1.11k
{
292
1.11k
    if (this != &other)
293
1.10k
    {
294
1.10k
        if (m_bitSize != other.m_bitSize)
295
3
            return false;
296
297
1.09k
        const size_t byteSize = getByteSize();
298
1.09k
        if (byteSize > 0)
299
1.09k
        {
300
1.09k
            if (byteSize > 1)
301
1.09k
            {
302
1.09k
                if (memcmp(getBuffer(), other.getBuffer(), byteSize - 1) != 0)
303
1
                    return false;
304
1.09k
            }
305
306
1.09k
            if (getMaskedLastByte() != other.getMaskedLastByte())
307
1
                return false;
308
1.09k
        }
309
1.09k
    }
310
311
1.11k
    return true;
312
1.11k
}
313
314
template <typename ALLOC>
315
bool BasicBitBuffer<ALLOC>::operator<(const BasicBitBuffer<ALLOC>& other) const
316
402
{
317
402
    const size_t byteSize1 = getByteSize();
318
402
    const size_t byteSize2 = other.getByteSize();
319
320
402
    if (byteSize1 == 0)
321
3
        return byteSize2 != 0;
322
399
    if (byteSize2 == 0)
323
1
        return false;
324
325
398
    using difference_type = typename vector<uint8_t, ALLOC>::iterator::difference_type;
326
327
398
    auto first1 = m_buffer.begin();
328
398
    const auto last1 = first1 + static_cast<difference_type>(byteSize1 - 1);
329
398
    auto first2 = other.m_buffer.begin();
330
398
    const auto last2 = first2 + static_cast<difference_type>(byteSize2 - 1);
331
790
    for (; (first1 != last1) && 
(first2 != last2)396
;
++first1, ++first2392
)
332
394
    {
333
394
        if (*first1 < *first2)
334
1
            return true;
335
393
        if (*first2 < *first1)
336
1
            return false;
337
393
    }
338
339
396
    const auto lastValue1 = first1 != last1 ? 
*first12
:
getMaskedLastByte()394
;
340
396
    const auto lastValue2 = first2 != last2 ? 
*first22
:
other.getMaskedLastByte()394
;
341
396
    if (lastValue1 < lastValue2)
342
2
        return true;
343
394
    if (lastValue2 < lastValue1)
344
2
        return false;
345
346
392
    return (first1 == last1) && 
(first2 != last2)390
;
347
394
}
348
349
template <typename ALLOC>
350
uint32_t BasicBitBuffer<ALLOC>::hashCode() const
351
14
{
352
14
    uint32_t result = ::zserio::HASH_SEED;
353
14
    const size_t byteSize = getByteSize();
354
14
    if (byteSize > 0)
355
11
    {
356
11
        if (byteSize > 1)
357
10
        {
358
10
            auto lastIt = m_buffer.begin() + static_cast<int>(byteSize) - 1;
359
20
            for (auto it = m_buffer.begin(); it != lastIt; 
++it10
)
360
10
                result = calcHashCode(result, *it);
361
10
        }
362
11
        result = ::zserio::calcHashCode(result, getMaskedLastByte());
363
11
    }
364
365
14
    return result;
366
14
}
367
368
template <typename ALLOC>
369
const uint8_t* BasicBitBuffer<ALLOC>::getBuffer() const
370
2.18k
{
371
2.18k
    return m_buffer.data();
372
2.18k
}
373
374
template <typename ALLOC>
375
uint8_t* BasicBitBuffer<ALLOC>::getBuffer()
376
75
{
377
75
    return m_buffer.data();
378
75
}
379
380
template <typename ALLOC>
381
size_t BasicBitBuffer<ALLOC>::getBitSize() const
382
1.28k
{
383
1.28k
    return m_bitSize;
384
1.28k
}
385
386
template <typename ALLOC>
387
size_t BasicBitBuffer<ALLOC>::getByteSize() const
388
2.00k
{
389
2.00k
    return (m_bitSize + 7) / 8;
390
2.00k
}
391
392
template <typename ALLOC>
393
const vector<uint8_t, ALLOC>& BasicBitBuffer<ALLOC>::getBytes() const
394
10
{
395
10
    return m_buffer;
396
10
}
397
398
template <typename ALLOC>
399
Span<const uint8_t> BasicBitBuffer<ALLOC>::getData() const
400
566
{
401
566
    return Span<const uint8_t>(m_buffer);
402
566
}
403
404
template <typename ALLOC>
405
Span<uint8_t> BasicBitBuffer<ALLOC>::getData()
406
850
{
407
850
    return Span<uint8_t>(m_buffer);
408
850
}
409
410
template <typename ALLOC>
411
uint8_t BasicBitBuffer<ALLOC>::getMaskedLastByte() const
412
2.99k
{
413
2.99k
    const size_t roundedByteSize = m_bitSize / 8;
414
2.99k
    const uint8_t lastByteBits = static_cast<uint8_t>(m_bitSize - 8 * roundedByteSize);
415
416
2.99k
    return (lastByteBits == 0) ? 
m_buffer[roundedByteSize - 1]23
:
417
2.99k
            
(m_buffer[roundedByteSize] & (0xFFU << (8U - lastByteBits)))2.96k
;
418
2.99k
}
419
420
/** Typedef to BitBuffer provided for convenience - using std::allocator<uint8_t>. */
421
using BitBuffer = BasicBitBuffer<>;
422
423
/**
424
 * Allows to append BitBuffer to CppRuntimeException.
425
 *
426
 * \param exception Exception to modify.
427
 * \param bitBuffer Bit buffer value.
428
 *
429
 * \return Reference to the exception to allow operator chaining.
430
 */
431
template <typename ALLOC>
432
CppRuntimeException& operator<<(CppRuntimeException& exception, const BasicBitBuffer<ALLOC>& bitBuffer)
433
12
{
434
12
    return exception << "BitBuffer([...], " << bitBuffer.getBitSize() << ")";
435
12
}
436
437
} // namespace zserio
438
439
#endif // ifndef ZSERIO_BIT_BUFFER_H_INC