cds/algo/split_bitstring.h

   1 /*
   2     This file is a part of libcds - Concurrent Data Structures library
   3
   4     (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
   5
   6     Source code repo: http://github.com/khizmax/libcds/
   7     Download: http://sourceforge.net/projects/libcds/files/
   8
   9     Redistribution and use in source and binary forms, with or without
  10     modification, are permitted provided that the following conditions are met:
  11
  12     * Redistributions of source code must retain the above copyright notice, this
  13       list of conditions and the following disclaimer.
  14
  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.
  18
  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.
  29 */
  30
  31 #ifndef CDSLIB_ALGO_SPLIT_BITSTRING_H
  32 #define CDSLIB_ALGO_SPLIT_BITSTRING_H
  33
  34 #include <cds/algo/base.h>
  35
  36 namespace cds { namespace algo {
  37
  38     /// Cuts a bit sequence from fixed-size bit-string
  39     /**
  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.
  43
  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>
  46
  47         The splitter keeps byte order.
  48
  49         Template parameters:
  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
  54
  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
  58     */
  59     template <typename BitString, size_t BitStringSize = sizeof( BitString ), typename UInt = unsigned >
  60     class split_bitstring
  61     {
  62     public:
  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
  66
  67         //@cond
  68         static CDS_CONSTEXPR unsigned const c_nBitPerByte = 8;
  69         //@endcond
  70
  71     public:
  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 ) )
  75             , offset_( 0 )
  76             , first_( cur_ )
  77             , last_( cur_ + c_bitstring_size )
  78         {}
  79
  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 )
  86         {}
  87
  88         /// Returns \p true if end-of-string is not reached yet
  89         explicit operator bool() const
  90         {
  91             return !eos();
  92         }
  93
  94         /// Returns \p true if end-of-stream encountered
  95         bool eos() const
  96         {
  97             return cur_ >= last_;
  98         }
  99
 100         /// Cuts next \p count bits from bit-string
 101         /**
 102             For performance reason, the function does not manage out-of-bound condition.
 103             To control that use \p safe_cut().
 104         */
 105         uint_type cut( unsigned count )
 106         {
 107             assert( !eos() );
 108
 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_;
 116
 117                 result |= static_cast<uint_type>(( *cur_ >> offset_ ) & (( 1 << bits ) - 1 )) << done;
 118
 119                 offset_ += bits;
 120                 assert( offset_ <= c_nBitPerByte );
 121                 if ( offset_ == c_nBitPerByte ) {
 122                     offset_ = 0;
 123                     ++cur_;
 124                 }
 125                 done += bits;
 126             }
 127 #       else
 128             while ( count ) {
 129                 assert( cur_ < last_ );
 130
 131                 unsigned bits = count <= ( c_nBitPerByte - offset_ ) ? count : c_nBitPerByte - offset_;
 132
 133                 result = ( result << bits ) | (( *cur_ >> offset_ ) & ( ( 1 << bits ) - 1 ));
 134
 135                 offset_ += bits;
 136                 assert( offset_ <= c_nBitPerByte );
 137                 if ( offset_ == c_nBitPerByte ) {
 138                     offset_ = 0;
 139                     ++cur_;
 140                 }
 141                 count -= bits;
 142             }
 143 #       endif
 144
 145             return result;
 146         }
 147
 148         /// Cuts up to \p count from the bit-string
 149         /**
 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.
 153         */
 154         uint_type safe_cut( unsigned count )
 155         {
 156             if ( eos())
 157                 return 0;
 158
 159             unsigned const rest = static_cast<unsigned>( last_ - cur_ - 1 ) * c_nBitPerByte + ( c_nBitPerByte - offset_ );
 160             if ( rest < count )
 161                 count = rest;
 162             return count ? cut( count ) : 0;
 163         }
 164
 165         /// Resets the splitter
 166         void reset() CDS_NOEXCEPT
 167         {
 168             cur_ = first_;
 169             offset_ = 0;
 170         }
 171
 172         /// Returns pointer to source bitstring
 173         bitstring const * source() const
 174         {
 175             return reinterpret_cast<bitstring const *>( first_ );
 176         }
 177
 178         /// Returns current bit offset from beginning of bit-string
 179         size_t bit_offset() const
 180         {
 181             return offset_ + (cur_ - first_) * c_nBitPerByte;
 182         }
 183
 184         /// Returns how many bits remain
 185         size_t rest_count() const
 186         {
 187             return c_bitstring_size * c_nBitPerByte - bit_offset();
 188         }
 189
 190         /// Returns \p true for any argument
 191         static CDS_CONSTEXPR bool is_correct( unsigned /*count*/ )
 192         {
 193             return true;
 194         }
 195
 196     private:
 197         //@cond
 198         uint8_t const*  cur_;
 199         unsigned        offset_;
 200         uint8_t const* const    first_;
 201         uint8_t const* const    last_;
 202         //@endcond
 203     };
 204
 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 >
 207     class byte_splitter
 208     {
 209     public:
 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
 213
 214         //@cond
 215         static CDS_CONSTEXPR unsigned const c_nBitPerByte = 8;
 216         //@endcond
 217
 218     public:
 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 ) )
 222             , first_( cur_ )
 223             , last_( cur_ + c_bitstring_size )
 224         {}
 225
 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 )
 231         {
 232             assert( is_correct( static_cast<unsigned>( nBitOffset )));
 233             assert( !eos());
 234         }
 235
 236         /// Returns \p true if end-of-string is not reached yet
 237         explicit operator bool() const
 238         {
 239             return !eos();
 240         }
 241
 242         /// Returns \p true if end-of-stream encountered
 243         bool eos() const
 244         {
 245             return cur_ >= last_;
 246         }
 247
 248         /// Cuts next \p count bits (must be multiplier of 8) from bit-string
 249         /**
 250             For performance reason, the function does not manage out-of-bound condition.
 251             To control that use \p safe_cut().
 252         */
 253         uint_type cut( unsigned count )
 254         {
 255             assert( !eos() );
 256             assert( is_correct( count ) );
 257
 258             uint_type result = 0;
 259
 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;
 263                 ++cur_;
 264             }
 265 #       else
 266             for ( ; count; count -= c_nBitPerByte ) {
 267                 result = ( result << c_nBitPerByte ) | *cur_;
 268                 ++cur_;
 269             }
 270 #       endif
 271
 272             return result;
 273         }
 274
 275         /// Cuts up to \p count from the bit-string
 276         /**
 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.
 280         */
 281         uint_type safe_cut( unsigned count )
 282         {
 283             if ( eos())
 284                 return 0;
 285
 286             unsigned const rest = static_cast<unsigned>( last_ - cur_ - 1 ) * c_nBitPerByte;
 287             if ( rest < count )
 288                 count = rest;
 289             return count ? cut( count ) : 0;
 290         }
 291
 292         /// Resets the splitter
 293         void reset() CDS_NOEXCEPT
 294         {
 295             cur_ = first_;
 296         }
 297
 298         /// Returns pointer to source bitstring
 299         bitstring const* source() const
 300         {
 301             return reinterpret_cast<bitstring const *>( first_ );
 302         }
 303
 304         /// Returns current bit offset from beginning of bit-string
 305         size_t bit_offset() const
 306         {
 307             return (cur_ - first_) * c_nBitPerByte;
 308         }
 309
 310         /// Returns how many bits remain
 311         size_t rest_count() const
 312         {
 313             return c_bitstring_size * c_nBitPerByte - bit_offset();
 314         }
 315
 316         /// Checks if \p count is multiple of 8
 317         static CDS_CONSTEXPR bool is_correct( unsigned count )
 318         {
 319             return count % 8 == 0;
 320         }
 321
 322     private:
 323         //@cond
 324         uint8_t const*  cur_;
 325         uint8_t const* const    first_;
 326         uint8_t const* const    last_;
 327         //@endcond
 328     };
 329
 330
 331     /// Cuts a bit sequence from a number
 332     /**
 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.
 336     */
 337     template <typename Int>
 338     class number_splitter
 339     {
 340     public:
 341         typedef Int       int_type;     ///< Number type
 342         typedef Int       uint_type;    ///< Result type of \p cut() function
 343
 344         //@cond
 345         static CDS_CONSTEXPR unsigned const c_nBitPerByte = 8;
 346         //@endcond
 347
 348     public:
 349         /// Initalizes the splitter with nymber \p n and initial bit offset 0
 350         explicit number_splitter( int_type n )
 351             : number_( n )
 352             , shift_( 0 )
 353         {}
 354
 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 )
 357             : number_( n )
 358             , shift_( static_cast<unsigned>( initial_offset ))
 359         {
 360             assert( initial_offset < sizeof( int_type ) * c_nBitPerByte );
 361         }
 362
 363         /// Returns \p true if end-of-string is not reached yet
 364         explicit operator bool() const
 365         {
 366             return !eos();
 367         }
 368
 369         /// Returns \p true if end-of-stream encountered
 370         bool eos() const
 371         {
 372             return shift_ >= sizeof( int_type ) * c_nBitPerByte;
 373         }
 374
 375         /// Cuts next \p count bits (must be multiplier of 8) from the number
 376         /**
 377             For performance reason, the function does not manage out-of-bound condition.
 378             To control that use \p safe_cut().
 379         */
 380         int_type cut( unsigned count )
 381         {
 382             assert( !eos() );
 383             assert( is_correct( count ));
 384
 385             int_type result = ( number_ >> shift_ ) & (( 1 << count ) - 1 );
 386             shift_ += count;
 387
 388             return result;
 389         }
 390
 391         /// Cuts up to \p count from the bit-string
 392         /**
 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.
 396         */
 397         int_type safe_cut( unsigned count )
 398         {
 399             if ( eos() )
 400                 return 0;
 401
 402             unsigned rest = static_cast<unsigned>( rest_count() );
 403             if ( rest < count )
 404                 count = rest;
 405             return count ? cut( count ) : 0;
 406         }
 407
 408         /// Resets the splitter
 409         void reset() CDS_NOEXCEPT
 410         {
 411             shift_ = 0;
 412         }
 413
 414         /// Returns initial number
 415         int_type source() const
 416         {
 417             return number_;
 418         }
 419
 420         /// Returns current bit offset from beginning of the number
 421         size_t bit_offset() const
 422         {
 423             return shift_;
 424         }
 425
 426         /// Returns how many bits remain
 427         size_t rest_count() const
 428         {
 429             return sizeof( int_type ) * c_nBitPerByte - shift_;
 430         }
 431
 432         /// Checks if \p count is multiple of 8
 433         static CDS_CONSTEXPR bool is_correct( unsigned count )
 434         {
 435             return count < sizeof( int_type ) * c_nBitPerByte;
 436         }
 437
 438     private:
 439         //@cond
 440         int_type const  number_;
 441         unsigned        shift_;
 442         //@endcond
 443     };
 444
 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
 448     {
 449         typedef split_bitstring< BitString, BitStringSize > type; ///< metafunction result
 450     };
 451
 452     //@cond
 453 #   define CDS_SELECT_NUMBER_SPLITTER( num_type ) \
 454         template <> struct select_splitter<num_type, sizeof(num_type)> { typedef number_splitter<num_type> type; }
 455
 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 );
 464
 465 #   undef CDS_SELECT_NUMBER_SPLITTER
 466     //@endcond
 467
 468 }} // namespace cds::algo
 469
 470 #endif // #ifndef CDSLIB_ALGO_SPLIT_BITSTRING_H