2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
6 Source code repo: http://github.com/khizmax/libcds/
7 Download: http://sourceforge.net/projects/libcds/files/
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are met:
12 * Redistributions of source code must retain the above copyright notice, this
13 list of conditions and the following disclaimer.
15 * Redistributions in binary form must reproduce the above copyright notice,
16 this list of conditions and the following disclaimer in the documentation
17 and/or other materials provided with the distribution.
19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
23 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
27 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 #ifndef CDSLIB_ALGO_SPLIT_BITSTRING_H
32 #define CDSLIB_ALGO_SPLIT_BITSTRING_H
34 #include <cds/algo/base.h>
36 namespace cds { namespace algo {
38 /// Cuts a bit sequence from fixed-size bit-string
40 The splitter can be used as an iterator over bit-string.
41 Each call of \p cut() or \p safe_cut() cuts the bit count specified
42 and keeps the position inside bit-string for the next call.
44 The splitter stores a const reference to bit-string, not a copy.
45 The maximum count of bits that can be cut in a single call is <tt> sizeof(UInt) * 8 </tt>
47 The splitter keeps byte order.
50 - \p BitString - a fixed-sized type that interprets as bit string
51 - \p BitStringSize - the size of \p BitString in bytes, default is <tt>sizeof( BitString )</tt>.
52 You can specify 0 for default.
53 - \p UInt - an unsigned integer, return type for \p cut(), default is \p unsigned
55 There are specialized splitters:
56 - a simplified \p byte_splitter algorithm that is suitable when count is multiple of 8.
57 - \p number_splitter algorithm is suitable for a number
59 template <typename BitString, size_t BitStringSize = sizeof( BitString ), typename UInt = unsigned >
63 typedef BitString bitstring; ///< Bit-string type
64 typedef UInt uint_type; ///< Result type of \p cut() function
65 static CDS_CONSTEXPR size_t const c_bitstring_size = BitStringSize ? BitStringSize : sizeof( BitString ); ///< size of \p BitString in bytes
68 static CDS_CONSTEXPR unsigned const c_nBitPerByte = 8;
72 /// Initializises the splitter with reference to \p h and zero start bit offset
73 explicit split_bitstring( bitstring const& h )
74 : cur_( reinterpret_cast<uint8_t const*>( &h ) )
77 , last_( cur_ + c_bitstring_size )
80 /// Initializises the splitter with reference to \p h and start bit offset \p nBitOffset
81 split_bitstring( bitstring const& h, size_t nBitOffset )
82 : cur_( reinterpret_cast<uint8_t const*>( &h ) + nBitOffset / c_nBitPerByte )
83 , offset_( nBitOffset % c_nBitPerByte )
84 , first_( reinterpret_cast<uint8_t const*>( &h ) )
85 , last_( first_ + c_bitstring_size )
88 /// Returns \p true if end-of-string is not reached yet
89 explicit operator bool() const
94 /// Returns \p true if end-of-stream encountered
100 /// Cuts next \p count bits from bit-string
102 For performance reason, the function does not manage out-of-bound condition.
103 To control that use \p safe_cut().
105 uint_type cut( unsigned count )
109 uint_type result = 0;
110 # if defined( CDS_ARCH_LITTLE_ENDIAN )
111 for ( unsigned done = 0; done < count; ) {
112 assert( cur_ < last_ );
113 unsigned bits = count - done;
114 if ( bits > c_nBitPerByte - offset_ )
115 bits = c_nBitPerByte - offset_;
117 result |= static_cast<uint_type>(( *cur_ >> offset_ ) & (( 1 << bits ) - 1 )) << done;
120 assert( offset_ <= c_nBitPerByte );
121 if ( offset_ == c_nBitPerByte ) {
129 assert( cur_ < last_ );
131 unsigned bits = count <= ( c_nBitPerByte - offset_ ) ? count : c_nBitPerByte - offset_;
133 result = ( result << bits ) | (( *cur_ >> offset_ ) & ( ( 1 << bits ) - 1 ));
136 assert( offset_ <= c_nBitPerByte );
137 if ( offset_ == c_nBitPerByte ) {
148 /// Cuts up to \p count from the bit-string
150 Safe analog of \p cut() but if \p count is more than the rest of bit-string,
151 only the rest is returned.
152 When \p eos() condition is met the function returns 0.
154 uint_type safe_cut( unsigned count )
159 unsigned const rest = static_cast<unsigned>( last_ - cur_ - 1 ) * c_nBitPerByte + ( c_nBitPerByte - offset_ );
162 return count ? cut( count ) : 0;
165 /// Resets the splitter
166 void reset() CDS_NOEXCEPT
172 /// Returns pointer to source bitstring
173 bitstring const * source() const
175 return reinterpret_cast<bitstring const *>( first_ );
178 /// Returns current bit offset from beginning of bit-string
179 size_t bit_offset() const
181 return offset_ + (cur_ - first_) * c_nBitPerByte;
184 /// Returns how many bits remain
185 size_t rest_count() const
187 return c_bitstring_size * c_nBitPerByte - bit_offset();
190 /// Returns \p true for any argument
191 static CDS_CONSTEXPR bool is_correct( unsigned /*count*/ )
200 uint8_t const* const first_;
201 uint8_t const* const last_;
205 /// Simplified \p split_bitstring algorithm when \p count is multiple of 8
206 template <typename BitString, size_t BitStringSize = sizeof( BitString ), typename UInt = unsigned >
210 typedef BitString bitstring; ///< Bit-string type
211 typedef UInt uint_type; ///< Result type of \p cut() function
212 static CDS_CONSTEXPR size_t const c_bitstring_size = BitStringSize ? BitStringSize : sizeof( BitString ); ///< size of \p BitString in bytes
215 static CDS_CONSTEXPR unsigned const c_nBitPerByte = 8;
219 /// Initializises the splitter with reference to \p h and zero start bit offset
220 explicit byte_splitter( bitstring const& h )
221 : cur_( reinterpret_cast<uint8_t const*>( &h ) )
223 , last_( cur_ + c_bitstring_size )
226 /// Initializises the splitter with reference to \p h and start bit offset \p nBitOffset
227 byte_splitter( bitstring const& h, size_t nBitOffset )
228 : cur_( reinterpret_cast<uint8_t const*>( &h ) + nBitOffset / c_nBitPerByte )
229 , first_( reinterpret_cast<uint8_t const*>( &h ) )
230 , last_( first_ + c_bitstring_size )
232 assert( is_correct( static_cast<unsigned>( nBitOffset )));
236 /// Returns \p true if end-of-string is not reached yet
237 explicit operator bool() const
242 /// Returns \p true if end-of-stream encountered
245 return cur_ >= last_;
248 /// Cuts next \p count bits (must be multiplier of 8) from bit-string
250 For performance reason, the function does not manage out-of-bound condition.
251 To control that use \p safe_cut().
253 uint_type cut( unsigned count )
256 assert( is_correct( count ) );
258 uint_type result = 0;
260 # if defined( CDS_ARCH_LITTLE_ENDIAN )
261 for ( unsigned i = 0; i < count; i += c_nBitPerByte ) {
262 result |= static_cast<uint_type>( *cur_ ) << i;
266 for ( ; count; count -= c_nBitPerByte ) {
267 result = ( result << c_nBitPerByte ) | *cur_;
275 /// Cuts up to \p count from the bit-string
277 Safe analog of \p cut(): if \p count is more than the rest of bit-string,
278 only the rest is returned.
279 When \p eos() condition is met the function returns 0.
281 uint_type safe_cut( unsigned count )
286 unsigned const rest = static_cast<unsigned>( last_ - cur_ - 1 ) * c_nBitPerByte;
289 return count ? cut( count ) : 0;
292 /// Resets the splitter
293 void reset() CDS_NOEXCEPT
298 /// Returns pointer to source bitstring
299 bitstring const* source() const
301 return reinterpret_cast<bitstring const *>( first_ );
304 /// Returns current bit offset from beginning of bit-string
305 size_t bit_offset() const
307 return (cur_ - first_) * c_nBitPerByte;
310 /// Returns how many bits remain
311 size_t rest_count() const
313 return c_bitstring_size * c_nBitPerByte - bit_offset();
316 /// Checks if \p count is multiple of 8
317 static CDS_CONSTEXPR bool is_correct( unsigned count )
319 return count % 8 == 0;
325 uint8_t const* const first_;
326 uint8_t const* const last_;
331 /// Cuts a bit sequence from a number
333 The splitter can be used as an iterator over bit representation of the number of type \p Int.
334 Each call of \p cut() or \p safe_cut() cuts the bit count specified
335 and keeps the position inside the number for the next call.
337 template <typename Int>
338 class number_splitter
341 typedef Int int_type; ///< Number type
342 typedef Int uint_type; ///< Result type of \p cut() function
345 static CDS_CONSTEXPR unsigned const c_nBitPerByte = 8;
349 /// Initalizes the splitter with nymber \p n and initial bit offset 0
350 explicit number_splitter( int_type n )
355 /// Initalizes the splitter with nymber \p n and initial bit offset \p initial_offset
356 number_splitter( int_type n, size_t initial_offset )
358 , shift_( static_cast<unsigned>( initial_offset ))
360 assert( initial_offset < sizeof( int_type ) * c_nBitPerByte );
363 /// Returns \p true if end-of-string is not reached yet
364 explicit operator bool() const
369 /// Returns \p true if end-of-stream encountered
372 return shift_ >= sizeof( int_type ) * c_nBitPerByte;
375 /// Cuts next \p count bits (must be multiplier of 8) from the number
377 For performance reason, the function does not manage out-of-bound condition.
378 To control that use \p safe_cut().
380 int_type cut( unsigned count )
383 assert( is_correct( count ));
385 int_type result = ( number_ >> shift_ ) & (( 1 << count ) - 1 );
391 /// Cuts up to \p count from the bit-string
393 Safe analog of \p cut(): if \p count is more than the rest of \p int_type,
394 only the rest is returned.
395 When \p eos() condition is met the function returns 0.
397 int_type safe_cut( unsigned count )
402 unsigned rest = static_cast<unsigned>( rest_count() );
405 return count ? cut( count ) : 0;
408 /// Resets the splitter
409 void reset() CDS_NOEXCEPT
414 /// Returns initial number
415 int_type source() const
420 /// Returns current bit offset from beginning of the number
421 size_t bit_offset() const
426 /// Returns how many bits remain
427 size_t rest_count() const
429 return sizeof( int_type ) * c_nBitPerByte - shift_;
432 /// Checks if \p count is multiple of 8
433 static CDS_CONSTEXPR bool is_correct( unsigned count )
435 return count < sizeof( int_type ) * c_nBitPerByte;
440 int_type const number_;
445 /// Metafunctin to select a most suitable splitter for type \p BitString of size \p BitStringSize
446 template <typename BitString, size_t BitStringSize >
447 struct select_splitter
449 typedef split_bitstring< BitString, BitStringSize > type; ///< metafunction result
453 # define CDS_SELECT_NUMBER_SPLITTER( num_type ) \
454 template <> struct select_splitter<num_type, sizeof(num_type)> { typedef number_splitter<num_type> type; }
456 CDS_SELECT_NUMBER_SPLITTER( int );
457 CDS_SELECT_NUMBER_SPLITTER( unsigned );
458 CDS_SELECT_NUMBER_SPLITTER( short );
459 CDS_SELECT_NUMBER_SPLITTER( unsigned short );
460 CDS_SELECT_NUMBER_SPLITTER( long );
461 CDS_SELECT_NUMBER_SPLITTER( unsigned long );
462 CDS_SELECT_NUMBER_SPLITTER( long long );
463 CDS_SELECT_NUMBER_SPLITTER( unsigned long long );
465 # undef CDS_SELECT_NUMBER_SPLITTER
468 }} // namespace cds::algo
470 #endif // #ifndef CDSLIB_ALGO_SPLIT_BITSTRING_H