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 |