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 |