test/unit/misc/split_bitstring.cpp

   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 #include <cds/algo/split_bitstring.h>
  32 #include <gtest/gtest.h>
  33
  34 namespace {
  35     bool is_big_endian()
  36     {
  37         union {
  38             uint32_t ui;
  39             uint8_t  ch;
  40         } byte_order;
  41         byte_order.ui = 0xFF000001;
  42
  43         return byte_order.ch != 0x01;
  44     }
  45
  46     class Split_bitstrig : public ::testing::Test
  47     {
  48     protected:
  49         void cut_uint_le()
  50         {
  51             typedef cds::algo::split_bitstring< size_t, 0, size_t > split_bitstring;
  52
  53             size_t src = sizeof(src) == 8 ? 0xFEDCBA9876543210 : 0x76543210;
  54             split_bitstring splitter( src );
  55             size_t res;
  56
  57             // Trivial case
  58             ASSERT_FALSE( splitter.eos() );
  59             ASSERT_FALSE( !splitter );
  60             res = splitter.cut( sizeof( src ) * 8 );
  61             EXPECT_EQ( res, src );
  62             ASSERT_TRUE( splitter.eos() );
  63             ASSERT_TRUE( !splitter );
  64             EXPECT_EQ( splitter.safe_cut( sizeof( src ) * 8 ), 0u );
  65             ASSERT_TRUE( splitter.eos() );
  66             ASSERT_TRUE( !splitter );
  67             splitter.reset();
  68             ASSERT_FALSE( splitter.eos() );
  69             ASSERT_FALSE( !splitter );
  70             res = splitter.cut( sizeof( src ) * 8 );
  71             EXPECT_EQ( res, src );
  72             ASSERT_TRUE( splitter.eos() );
  73             ASSERT_TRUE( !splitter );
  74             EXPECT_EQ( splitter.safe_cut( sizeof( src ) * 8 ), 0u );
  75             ASSERT_TRUE( splitter.eos() );
  76             ASSERT_TRUE( !splitter );
  77
  78             EXPECT_EQ( *splitter.source(), src );
  79             EXPECT_EQ( splitter.rest_count(), 0u );
  80             EXPECT_EQ( splitter.bit_offset(), sizeof( src ) * 8 );
  81
  82             // Cut each hex digit
  83             splitter.reset();
  84             for ( size_t i = 0; i < sizeof(size_t) * 2; ++i ) {
  85                 ASSERT_FALSE( splitter.eos());
  86                 ASSERT_FALSE( !splitter );
  87                 ASSERT_EQ( splitter.cut( 4 ), i );
  88             }
  89             ASSERT_TRUE( splitter.eos());
  90             ASSERT_FALSE( splitter );
  91             EXPECT_EQ( splitter.safe_cut( 8 ), 0u );
  92             EXPECT_EQ( *splitter.source(), src );
  93             EXPECT_EQ( splitter.rest_count(), 0u );
  94             EXPECT_EQ( splitter.bit_offset(), sizeof( src ) * 8 );
  95
  96             // by one bit
  97             {
  98                 splitter.reset();
  99                 EXPECT_EQ( *splitter.source(), src );
 100                 EXPECT_EQ( splitter.rest_count(), sizeof( src ) * 8 );
 101                 EXPECT_EQ( splitter.bit_offset(), 0u );
 102
 103                 res = 0;
 104                 for ( size_t i = 0; i < sizeof(size_t) * 8; ++i ) {
 105                     ASSERT_FALSE( splitter.eos());
 106                     ASSERT_FALSE( !splitter );
 107                     res |= splitter.cut( 1 ) << i;
 108                 }
 109                 ASSERT_TRUE( splitter.eos());
 110                 ASSERT_TRUE( !splitter );
 111                 EXPECT_EQ( res, src );
 112
 113                 EXPECT_EQ( splitter.safe_cut( 8 ), 0u );
 114                 EXPECT_EQ( *splitter.source(), src );
 115                 EXPECT_EQ( splitter.rest_count(), 0u );
 116                 EXPECT_EQ( splitter.bit_offset(), sizeof( src ) * 8 );
 117             }
 118
 119             // random cut
 120             {
 121                 for ( size_t k = 0; k < 100; ++k ) {
 122                     splitter.reset();
 123                     EXPECT_EQ( *splitter.source(), src );
 124                     EXPECT_EQ( splitter.rest_count(), sizeof( src ) * 8 );
 125                     EXPECT_EQ( splitter.bit_offset(), 0u );
 126
 127                     res = 0;
 128                     size_t shift = 0;
 129                     while ( splitter ) {
 130                         ASSERT_FALSE( splitter.eos());
 131                         ASSERT_FALSE( !splitter );
 132                         int bits = std::rand() % 16;
 133                         res |= splitter.safe_cut( bits ) << shift;
 134                         shift += bits;
 135                     }
 136                     ASSERT_TRUE( splitter.eos());
 137                     ASSERT_TRUE( !splitter );
 138                     EXPECT_EQ( res, src );
 139
 140                     EXPECT_EQ( splitter.safe_cut( 8 ), 0u );
 141                     EXPECT_EQ( *splitter.source(), src );
 142                     EXPECT_EQ( splitter.rest_count(), 0u );
 143                     EXPECT_EQ( splitter.bit_offset(), sizeof( src ) * 8 );
 144                 }
 145             }
 146         }
 147
 148         void cut_uint_be()
 149         {
 150             typedef cds::algo::split_bitstring< size_t, 0, size_t > split_bitstring;
 151
 152             size_t src = sizeof(src) == 8 ? 0xFEDCBA9876543210 : 0x76543210;
 153             split_bitstring splitter( src );
 154             size_t res;
 155
 156             // Trivial case
 157             ASSERT_FALSE( splitter.eos() );
 158             ASSERT_FALSE( !splitter );
 159             res = splitter.cut( sizeof( src ) * 8 );
 160             ASSERT_EQ( res, src );
 161             ASSERT_TRUE( splitter.eos() );
 162             ASSERT_TRUE( !splitter );
 163             EXPECT_EQ( splitter.safe_cut( sizeof( src ) * 8 ), 0u );
 164             ASSERT_TRUE( splitter.eos() );
 165             ASSERT_TRUE( !splitter );
 166             splitter.reset();
 167             ASSERT_FALSE( splitter.eos() );
 168             ASSERT_FALSE( !splitter );
 169             res = splitter.cut( sizeof( src ) * 8 );
 170             EXPECT_EQ( res, src );
 171             ASSERT_TRUE( splitter.eos() );
 172             ASSERT_TRUE( !splitter );
 173             EXPECT_EQ( splitter.safe_cut( sizeof( src ) * 8 ), 0u );
 174             ASSERT_TRUE( splitter.eos() );
 175             ASSERT_TRUE( !splitter );
 176
 177             EXPECT_EQ( *splitter.source(), src );
 178             EXPECT_EQ( splitter.rest_count(), 0u );
 179             EXPECT_EQ( splitter.bit_offset(), sizeof( src ) * 8 );
 180
 181             // Cut each hex digit
 182             splitter.reset();
 183             for ( size_t i = 0; i < sizeof(size_t) * 2; ++i ) {
 184                 ASSERT_FALSE( splitter.eos());
 185                 ASSERT_FALSE( !splitter );
 186                 if ( i % 2 == 0 ) {
 187                     // even - least half-byte
 188                     EXPECT_EQ( splitter.cut( 4 ), 0x0E - i ) << "i=" << i;
 189                 }
 190                 else {
 191                     // odd - most half-byte
 192                     EXPECT_EQ( splitter.cut( 4 ), 0x0F - i + 1 ) << "i=" << i;
 193                 }
 194             }
 195             ASSERT_TRUE( splitter.eos());
 196             ASSERT_TRUE( !splitter );
 197             EXPECT_EQ( splitter.safe_cut( 8 ), 0u );
 198             EXPECT_EQ( *splitter.source(), src );
 199             EXPECT_EQ( splitter.rest_count(), 0u );
 200             EXPECT_EQ( splitter.bit_offset(), sizeof( src ) * 8 );
 201
 202             // by one bit
 203             {
 204                 splitter.reset();
 205                 EXPECT_EQ( *splitter.source(), src );
 206                 EXPECT_EQ( splitter.rest_count(), sizeof( src ) * 8 );
 207                 EXPECT_EQ( splitter.bit_offset(), 0u );
 208
 209                 res = 0;
 210                 for ( size_t i = 0; i < sizeof(size_t) * 8; ++i ) {
 211                     ASSERT_FALSE( splitter.eos());
 212                     ASSERT_FALSE( !splitter );
 213                     if ( i % 8 == 0 )
 214                         res = res << 8;
 215                     res |= ( splitter.cut( 1 ) ) << ( i % 8 );
 216                 }
 217                 ASSERT_TRUE( splitter.eos());
 218                 ASSERT_TRUE( !splitter );
 219                 EXPECT_EQ( res, src );
 220
 221                 EXPECT_EQ( splitter.safe_cut( 8 ), 0u );
 222                 EXPECT_EQ( *splitter.source(), src );
 223                 EXPECT_EQ( splitter.rest_count(), 0u );
 224                 EXPECT_EQ( splitter.bit_offset(), sizeof( src ) * 8 );
 225             }
 226
 227             // random cut
 228             /*
 229             {
 230                 for ( size_t k = 0; k < 100; ++k ) {
 231                     splitter.reset();
 232                     EXPECT_EQ( *splitter.source(), src );
 233                     EXPECT_EQ( splitter.rest_count(), sizeof( src ) * 8 );
 234                     EXPECT_EQ( splitter.bit_offset(), 0u );
 235
 236                     res = 0;
 237                     while ( splitter ) {
 238                         ASSERT_FALSE( splitter.eos());
 239                         ASSERT_FALSE( !splitter );
 240                         unsigned bits = std::rand() % 16;
 241                         size_t shift = splitter.rest_count();
 242                         if ( shift > bits )
 243                             shift = bits;
 244                         res = (res << shift) | splitter.safe_cut( bits );
 245                     }
 246                     ASSERT_TRUE( splitter.eos());
 247                     ASSERT_TRUE( !splitter );
 248                     EXPECT_EQ( res, src );
 249
 250                     EXPECT_EQ( splitter.safe_cut( 8 ), 0u );
 251                     EXPECT_EQ( *splitter.source(), src );
 252                     EXPECT_EQ( splitter.rest_count(), 0u );
 253                     EXPECT_EQ( splitter.bit_offset(), sizeof( src ) * 8 );
 254                 }
 255             }
 256             */
 257         }
 258
 259         template <typename PartUInt>
 260         void cut_small_le()
 261         {
 262             typedef PartUInt part_uint;
 263
 264             typedef cds::algo::split_bitstring< uint64_t, 0, part_uint > split_bitstring;
 265
 266             uint64_t src = 0xFEDCBA9876543210;
 267             split_bitstring splitter(src);
 268             uint64_t res;
 269
 270             EXPECT_EQ( *splitter.source(), src );
 271             EXPECT_EQ( splitter.rest_count(), sizeof( src ) * 8 );
 272             EXPECT_EQ( splitter.bit_offset(), 0u );
 273
 274             // Cut each hex digit
 275             splitter.reset();
 276             for ( size_t i = 0; i < sizeof(src) * 2; ++i ) {
 277                 ASSERT_FALSE( splitter.eos());
 278                 ASSERT_FALSE( !splitter );
 279                 EXPECT_EQ( static_cast<size_t>(splitter.cut( 4 )), i );
 280             }
 281             ASSERT_TRUE( splitter.eos());
 282             ASSERT_TRUE( !splitter );
 283             EXPECT_EQ( splitter.safe_cut( 8 ), 0u );
 284             EXPECT_EQ( *splitter.source(), src );
 285             EXPECT_EQ( splitter.rest_count(), 0u );
 286             EXPECT_EQ( splitter.bit_offset(), sizeof( src ) * 8 );
 287
 288             // by one bit
 289             {
 290                 splitter.reset();
 291                 EXPECT_EQ( *splitter.source(), src );
 292                 EXPECT_EQ( splitter.rest_count(), sizeof( src ) * 8 );
 293                 EXPECT_EQ( splitter.bit_offset(), 0u );
 294
 295                 res = 0;
 296                 for ( size_t i = 0; i < sizeof(src) * 8; ++i ) {
 297                     ASSERT_FALSE( splitter.eos());
 298                     ASSERT_FALSE( !splitter );
 299                     res += static_cast<uint64_t>(splitter.cut( 1 )) << i;
 300                 }
 301                 ASSERT_TRUE( splitter.eos());
 302                 ASSERT_TRUE( !splitter );
 303                 EXPECT_EQ( res, src );
 304                 EXPECT_EQ( splitter.safe_cut( 8 ), 0u );
 305                 EXPECT_EQ( *splitter.source(), src );
 306                 EXPECT_EQ( splitter.rest_count(), 0u );
 307                 EXPECT_EQ( splitter.bit_offset(), sizeof( src ) * 8 );
 308             }
 309
 310             // random cut
 311             {
 312                 for ( size_t k = 0; k < 100; ++k ) {
 313                     splitter.reset();
 314                     EXPECT_EQ( *splitter.source(), src );
 315                     EXPECT_EQ( splitter.rest_count(), sizeof( src ) * 8 );
 316                     EXPECT_EQ( splitter.bit_offset(), 0u );
 317
 318                     res = 0;
 319                     size_t shift = 0;
 320                     while ( splitter ) {
 321                         ASSERT_FALSE( splitter.eos());
 322                         ASSERT_FALSE( !splitter );
 323                         int bits = std::rand() % 16;
 324                         res += static_cast<uint64_t>(splitter.safe_cut( bits )) << shift;
 325                         shift += bits;
 326                     }
 327                     ASSERT_TRUE( splitter.eos());
 328                     ASSERT_TRUE( !splitter );
 329                     EXPECT_EQ( res, src );
 330                     EXPECT_EQ( splitter.safe_cut( 8 ), 0u );
 331                     EXPECT_EQ( *splitter.source(), src );
 332                     EXPECT_EQ( splitter.rest_count(), 0u );
 333                     EXPECT_EQ( splitter.bit_offset(), sizeof( src ) * 8 );
 334                 }
 335             }
 336         }
 337
 338         template <typename PartUInt>
 339         void cut_small_be()
 340         {
 341             typedef PartUInt part_uint;
 342
 343             typedef cds::algo::split_bitstring< uint64_t, 0, part_uint > split_bitstring;
 344
 345             uint64_t src = 0xFEDCBA9876543210;
 346             split_bitstring splitter(src);
 347             uint64_t res;
 348
 349             EXPECT_EQ( *splitter.source(), src );
 350             EXPECT_EQ( splitter.rest_count(), sizeof( src ) * 8 );
 351             EXPECT_EQ( splitter.bit_offset(), 0u );
 352
 353             // Cut each hex digit
 354             splitter.reset();
 355             for ( size_t i = 0; i < sizeof(size_t) * 2; ++i ) {
 356                 ASSERT_FALSE( splitter.eos());
 357                 ASSERT_FALSE( !splitter );
 358                 if ( i % 2 == 0 ) {
 359                     EXPECT_EQ( splitter.cut( 4 ), 0x0E - i );
 360                 }
 361                 else {
 362                     EXPECT_EQ( splitter.cut( 4 ), 0x0F - i + 1 );
 363                 }
 364             }
 365             ASSERT_TRUE( splitter.eos());
 366             ASSERT_TRUE( !splitter );
 367
 368             // by one bit
 369             {
 370                 splitter.reset();
 371                 EXPECT_EQ( *splitter.source(), src );
 372                 EXPECT_EQ( splitter.rest_count(), sizeof( src ) * 8 );
 373                 EXPECT_EQ( splitter.bit_offset(), 0u );
 374
 375                 res = 0;
 376                 for ( size_t i = 0; i < sizeof(size_t) * 8; ++i ) {
 377                     ASSERT_FALSE( splitter.eos());
 378                     ASSERT_FALSE( !splitter );
 379                     if ( i % 8 == 0 )
 380                         res = res << 8;
 381                     res |= ( splitter.cut( 1 ) ) << ( i % 8 );
 382                 }
 383                 ASSERT_TRUE( splitter.eos());
 384                 ASSERT_TRUE( !splitter );
 385                 EXPECT_EQ( res, src );
 386                 EXPECT_EQ( splitter.safe_cut( 8 ), 0u );
 387                 EXPECT_EQ( *splitter.source(), src );
 388                 EXPECT_EQ( splitter.rest_count(), 0u );
 389                 EXPECT_EQ( splitter.bit_offset(), sizeof( src ) * 8 );
 390             }
 391
 392             // random cut
 393             /*
 394             {
 395                 for ( size_t k = 0; k < 100; ++k ) {
 396                     splitter.reset();
 397                     EXPECT_EQ( *splitter.source(), src );
 398                     EXPECT_EQ( splitter.rest_count(), sizeof( src ) * 8 );
 399                     EXPECT_EQ( splitter.bit_offset(), 0u );
 400
 401                     res = 0;
 402                     while ( splitter ) {
 403                         ASSERT_FALSE( splitter.eos());
 404                         ASSERT_FALSE( !splitter );
 405                         unsigned bits = std::rand() % 16;
 406                         size_t shift = splitter.rest_count();
 407                         if ( shift > bits )
 408                             shift = bits;
 409                         res = ( res << shift ) | splitter.safe_cut( bits );
 410                     }
 411                     ASSERT_TRUE( splitter.eos());
 412                     ASSERT_TRUE( !splitter );
 413                     EXPECT_EQ( res, src );
 414                     EXPECT_EQ( splitter.safe_cut( 8 ), 0u );
 415                     EXPECT_EQ( *splitter.source(), src );
 416                     EXPECT_EQ( splitter.rest_count(), 0u );
 417                     EXPECT_EQ( splitter.bit_offset(), sizeof( src ) * 8 );
 418                 }
 419             }
 420             */
 421         }
 422
 423         struct int48 {
 424             uint32_t    n32;
 425             uint16_t    n16;
 426
 427             friend bool operator ==( int48 lhs, int48 rhs )
 428             {
 429                 return lhs.n32 == rhs.n32 && lhs.n16 == rhs.n16;
 430             }
 431
 432             uint64_t to64() const
 433             {
 434 #       ifdef CDS_ARCH_LITTLE_ENDIAN
 435                 return ( static_cast<uint64_t>( n16 ) << 32 ) + n32;
 436 #       else
 437                 return ( static_cast<uint64_t>( n32 ) << 16 ) + n16;
 438 #       endif
 439             }
 440         };
 441         static constexpr size_t int48_size = 6;
 442
 443         void cut_int48_le()
 444         {
 445             int48 src;
 446             src.n32 = 0x76543210;
 447             src.n16 = 0xBA98;
 448
 449             uint64_t res;
 450
 451 #if CDS_BUILD_BITS == 64
 452             {
 453                 typedef cds::algo::split_bitstring< int48, int48_size, size_t > split_bitstring;
 454                 split_bitstring splitter( src );
 455
 456                 // Trivial case
 457                 ASSERT_FALSE( splitter.eos() );
 458                 ASSERT_FALSE( !splitter );
 459                 res = splitter.cut( int48_size * 8 );
 460                 EXPECT_EQ( res, src.to64() );
 461                 ASSERT_TRUE( splitter.eos() );
 462                 ASSERT_TRUE( !splitter );
 463                 EXPECT_EQ( splitter.safe_cut( int48_size * 8 ), 0u );
 464                 ASSERT_TRUE( splitter.eos() );
 465                 ASSERT_TRUE( !splitter );
 466                 splitter.reset();
 467                 ASSERT_FALSE( splitter.eos() );
 468                 ASSERT_FALSE( !splitter );
 469                 res = splitter.cut( int48_size * 8 );
 470                 EXPECT_EQ( res, src.to64() );
 471                 ASSERT_TRUE( splitter.eos() );
 472                 ASSERT_TRUE( !splitter );
 473                 EXPECT_EQ( splitter.safe_cut( int48_size * 8 ), 0u );
 474                 ASSERT_TRUE( splitter.eos() );
 475                 ASSERT_TRUE( !splitter );
 476             }
 477 #endif
 478
 479             typedef cds::algo::split_bitstring< int48, int48_size, size_t > split_bitstring;
 480             split_bitstring splitter( src );
 481
 482             EXPECT_EQ( splitter.source()->to64(), src.to64() );
 483             EXPECT_EQ( splitter.rest_count(), int48_size * 8 );
 484             EXPECT_EQ( splitter.bit_offset(), 0u );
 485
 486             // Cut each hex digit
 487             splitter.reset();
 488             for ( size_t i = 0; i < int48_size * 2; ++i ) {
 489                 ASSERT_FALSE( splitter.eos() );
 490                 ASSERT_FALSE( !splitter );
 491                 ASSERT_EQ( splitter.cut( 4 ), i );
 492             }
 493             ASSERT_TRUE( splitter.eos() );
 494             ASSERT_FALSE( splitter );
 495             EXPECT_EQ( splitter.safe_cut( 8 ), 0u );
 496             EXPECT_EQ( splitter.source()->to64(), src.to64() );
 497             EXPECT_EQ( splitter.rest_count(), 0u );
 498             EXPECT_EQ( splitter.bit_offset(), int48_size * 8 );
 499
 500             // by one bit
 501             {
 502                 splitter.reset();
 503                 EXPECT_EQ( splitter.source()->to64(), src.to64() );
 504                 EXPECT_EQ( splitter.rest_count(), int48_size * 8 );
 505                 EXPECT_EQ( splitter.bit_offset(), 0u );
 506
 507                 res = 0;
 508                 for ( size_t i = 0; i < int48_size * 8; ++i ) {
 509                     ASSERT_FALSE( splitter.eos() );
 510                     ASSERT_FALSE( !splitter );
 511 #if CDS_BUILD_BITS == 64
 512                     res |= splitter.cut( 1 ) << i;
 513 #else
 514                     res |= static_cast<decltype(res)>( splitter.cut( 1 )) << i;
 515 #endif
 516                 }
 517                 ASSERT_TRUE( splitter.eos() );
 518                 ASSERT_TRUE( !splitter );
 519                 EXPECT_EQ( res, src.to64() );
 520                 EXPECT_EQ( splitter.safe_cut( 8 ), 0u );
 521                 EXPECT_EQ( splitter.source()->to64(), src.to64() );
 522                 EXPECT_EQ( splitter.rest_count(), 0u );
 523                 EXPECT_EQ( splitter.bit_offset(), int48_size * 8 );
 524             }
 525
 526             // random cut
 527             {
 528                 for ( size_t k = 0; k < 100; ++k ) {
 529                     splitter.reset();
 530                     EXPECT_EQ( splitter.source()->to64(), src.to64() );
 531                     EXPECT_EQ( splitter.rest_count(), int48_size * 8 );
 532                     EXPECT_EQ( splitter.bit_offset(), 0u );
 533
 534                     res = 0;
 535                     size_t shift = 0;
 536                     while ( splitter ) {
 537                         ASSERT_FALSE( splitter.eos() );
 538                         ASSERT_FALSE( !splitter );
 539                         int bits = std::rand() % 16;
 540 #if CDS_BUILD_BITS == 64
 541                         res |= splitter.safe_cut( bits ) << shift;
 542 #else
 543                         res |= static_cast<decltype(res)>( splitter.safe_cut( bits )) << shift;
 544 #endif
 545                         shift += bits;
 546                     }
 547                     ASSERT_TRUE( splitter.eos() );
 548                     ASSERT_TRUE( !splitter );
 549                     EXPECT_EQ( res, src.to64() );
 550                     EXPECT_EQ( splitter.safe_cut( 8 ), 0u );
 551                     EXPECT_EQ( splitter.source()->to64(), src.to64() );
 552                     EXPECT_EQ( splitter.rest_count(), 0u );
 553                     EXPECT_EQ( splitter.bit_offset(), int48_size * 8 );
 554                 }
 555             }
 556         }
 557
 558         void cut_int48_be()
 559         {
 560             int48 src;
 561             src.n32 = 0xBA987654;
 562             src.n16 = 0x3210;
 563
 564             uint64_t res;
 565
 566 #if CDS_BUILD_BITS == 64
 567             {
 568                 typedef cds::algo::split_bitstring< int48, int48_size, size_t > split_bitstring;
 569                 split_bitstring splitter( src );
 570
 571                 // Trivial case
 572                 ASSERT_FALSE( splitter.eos() );
 573                 ASSERT_FALSE( !splitter );
 574                 res = splitter.cut( int48_size * 8 );
 575                 ASSERT_EQ( res, src.to64() );
 576                 ASSERT_TRUE( splitter.eos() );
 577                 ASSERT_TRUE( !splitter );
 578                 EXPECT_EQ( splitter.safe_cut( int48_size * 8 ), 0u );
 579                 ASSERT_TRUE( splitter.eos() );
 580                 ASSERT_TRUE( !splitter );
 581                 splitter.reset();
 582                 ASSERT_FALSE( splitter.eos() );
 583                 ASSERT_FALSE( !splitter );
 584                 res = splitter.cut( int48_size * 8 );
 585                 EXPECT_EQ( res, src.to64() );
 586                 ASSERT_TRUE( splitter.eos() );
 587                 ASSERT_TRUE( !splitter );
 588                 EXPECT_EQ( splitter.safe_cut( int48_size * 8 ), 0u );
 589                 ASSERT_TRUE( splitter.eos() );
 590                 ASSERT_TRUE( !splitter );
 591             }
 592 #endif
 593
 594             typedef cds::algo::split_bitstring< int48, int48_size, size_t > split_bitstring;
 595             split_bitstring splitter( src );
 596
 597             EXPECT_EQ( splitter.source()->to64(), src.to64() );
 598             EXPECT_EQ( splitter.rest_count(), int48_size * 8 );
 599             EXPECT_EQ( splitter.bit_offset(), 0u );
 600
 601             // Cut each hex digit
 602             splitter.reset();
 603             for ( size_t i = 0; i < int48_size * 2; ++i ) {
 604                 ASSERT_FALSE( splitter.eos() );
 605                 ASSERT_FALSE( !splitter );
 606                 if ( i % 2 == 0 ) {
 607                     EXPECT_EQ( splitter.cut( 4 ), 0x0A - i );
 608                 }
 609                 else {
 610                     EXPECT_EQ( splitter.cut( 4 ), 0x0B - i + 1 );
 611                 }
 612             }
 613             ASSERT_TRUE( splitter.eos() );
 614             ASSERT_TRUE( !splitter );
 615             EXPECT_EQ( splitter.safe_cut( 8 ), 0u );
 616             EXPECT_EQ( splitter.source()->to64(), src.to64() );
 617             EXPECT_EQ( splitter.rest_count(), 0u );
 618             EXPECT_EQ( splitter.bit_offset(), int48_size * 8 );
 619
 620             // by one bit
 621             {
 622                 splitter.reset();
 623                 EXPECT_EQ( splitter.source()->to64(), src.to64() );
 624                 EXPECT_EQ( splitter.rest_count(), int48_size * 8 );
 625                 EXPECT_EQ( splitter.bit_offset(), 0u );
 626
 627                 res = 0;
 628                 for ( size_t i = 0; i < int48_size * 8; ++i ) {
 629                     ASSERT_FALSE( splitter.eos() );
 630                     ASSERT_FALSE( !splitter );
 631 #if CDS_BUILD_BITS == 64
 632                     if ( i % 8 == 0 )
 633                         res = res << 8;
 634                     res |= ( splitter.cut( 1 ) ) << ( i % 8 );
 635 #else
 636                     res = ( res << 1 ) | static_cast<decltype(res)>( splitter.cut( 1 ) );
 637 #endif
 638                 }
 639                 ASSERT_TRUE( splitter.eos() );
 640                 ASSERT_TRUE( !splitter );
 641                 EXPECT_EQ( res, src.to64() );
 642                 EXPECT_EQ( splitter.safe_cut( 8 ), 0u );
 643                 EXPECT_EQ( splitter.source()->to64(), src.to64() );
 644                 EXPECT_EQ( splitter.rest_count(), 0u );
 645                 EXPECT_EQ( splitter.bit_offset(), int48_size * 8 );
 646             }
 647
 648             // random cut
 649             /*
 650             {
 651                 for ( size_t k = 0; k < 100; ++k ) {
 652                     splitter.reset();
 653                     EXPECT_EQ( splitter.source()->to64(), src.to64() );
 654                     EXPECT_EQ( splitter.rest_count(), int48_size * 8 );
 655                     EXPECT_EQ( splitter.bit_offset(), 0u );
 656
 657                     res = 0;
 658                     while ( splitter ) {
 659                         ASSERT_FALSE( splitter.eos() );
 660                         ASSERT_FALSE( !splitter );
 661                         unsigned bits = std::rand() % 16;
 662                         size_t shift = splitter.rest_count();
 663                         if ( shift > bits )
 664                             shift = bits;
 665 #if CDS_BUILD_BITS == 64
 666                         res = ( res << shift ) | splitter.safe_cut( bits );
 667 #else
 668                         res = ( res << shift ) | static_cast<decltype(res)>( splitter.safe_cut( bits ));
 669 #endif
 670                     }
 671                     ASSERT_TRUE( splitter.eos() );
 672                     ASSERT_TRUE( !splitter );
 673                     EXPECT_EQ( res, src.to64() );
 674                     EXPECT_EQ( splitter.safe_cut( 8 ), 0u );
 675                     EXPECT_EQ( splitter.source()->to64(), src.to64() );
 676                     EXPECT_EQ( splitter.rest_count(), 0u );
 677                     EXPECT_EQ( splitter.bit_offset(), int48_size * 8 );
 678                 }
 679             }
 680             */
 681         }
 682
 683         void cut_byte_le()
 684         {
 685             size_t src = sizeof( src ) == 8 ? 0xFEDCBA9876543210 : 0x76543210;
 686
 687             typedef cds::algo::byte_splitter< size_t > splitter_type;
 688             splitter_type splitter( src );
 689
 690             ASSERT_TRUE( !splitter.eos() );
 691             EXPECT_EQ( *splitter.source(), src );
 692             EXPECT_EQ( splitter.rest_count(), sizeof( src ) * 8 );
 693             EXPECT_EQ( splitter.bit_offset(), 0u );
 694             EXPECT_TRUE( splitter.is_correct( 8 ) );
 695             EXPECT_FALSE( splitter.is_correct( 4 ) );
 696
 697             unsigned expected = 0x10;
 698             for ( unsigned i = 0; i < splitter_type::c_bitstring_size; ++i ) {
 699                 auto part = splitter.cut( 8 );
 700                 EXPECT_EQ( part, expected );
 701                 expected += 0x22;
 702             }
 703
 704             ASSERT_TRUE( splitter.eos() );
 705             EXPECT_EQ( splitter.safe_cut( 8 ), 0u );
 706             EXPECT_EQ( *splitter.source(), src );
 707             EXPECT_EQ( splitter.rest_count(), 0u );
 708             EXPECT_EQ( splitter.bit_offset(), sizeof( src ) * 8 );
 709         }
 710
 711         void cut_byte_be()
 712         {
 713             size_t src = sizeof( src ) == 8 ? 0xFEDCBA9876543210 : 0x76543210;
 714
 715             typedef cds::algo::byte_splitter< size_t > splitter_type;
 716             splitter_type splitter( src );
 717
 718             ASSERT_TRUE( !splitter.eos() );
 719             EXPECT_EQ( *splitter.source(), src );
 720             EXPECT_EQ( splitter.rest_count(), sizeof( src ) * 8 );
 721             EXPECT_EQ( splitter.bit_offset(), 0u );
 722             EXPECT_TRUE( splitter.is_correct( 8 ) );
 723             EXPECT_FALSE( splitter.is_correct( 4 ) );
 724
 725             unsigned expected = 0xFE;
 726             for ( unsigned i = 0; i < splitter_type::c_bitstring_size; ++i ) {
 727                 auto part = splitter.cut( 8 );
 728                 EXPECT_EQ( part, expected );
 729                 expected -= 0x22;
 730             }
 731
 732             ASSERT_TRUE( splitter.eos() );
 733             EXPECT_EQ( splitter.safe_cut( 8 ), 0u );
 734             EXPECT_EQ( *splitter.source(), src );
 735             EXPECT_EQ( splitter.rest_count(), 0u );
 736             EXPECT_EQ( splitter.bit_offset(), sizeof( src ) * 8 );
 737         }
 738     };
 739
 740     class Split_number: public ::testing::Test
 741     {
 742     protected:
 743         template <typename Int>
 744         void split( Int const n )
 745         {
 746             cds::algo::number_splitter< Int > splitter( n );
 747
 748             // split by hex digit
 749             for ( unsigned count = 4; count < sizeof( Int ) * 8; count += 4 ) {
 750                 EXPECT_EQ( splitter.cut( 4 ), static_cast<Int>( count / 4 - 1 ));
 751             }
 752
 753             // random cut
 754             for ( int i = 0; i < 100; ++i ) {
 755                 splitter.reset();
 756                 EXPECT_EQ( splitter.source(), n );
 757                 EXPECT_EQ( splitter.bit_offset(), 0u );
 758                 EXPECT_EQ( splitter.rest_count(), sizeof( Int ) * 8 );
 759
 760                 unsigned total = 0;
 761                 Int result = 0;
 762
 763                 while ( total < sizeof( Int ) * 8 ) {
 764                     unsigned count = std::rand() % 16;
 765
 766                     unsigned shift = count;
 767                     if ( total + count > sizeof( Int ) * 8 )
 768                         shift = sizeof( Int ) * 8 - total;
 769
 770                     result += splitter.safe_cut( count ) << total;
 771                     total += shift;
 772                 }
 773
 774                 EXPECT_EQ( result, n );
 775
 776                 EXPECT_EQ( splitter.bit_offset(), sizeof( Int ) * 8 );
 777                 EXPECT_EQ( splitter.rest_count(), 0u );
 778             }
 779         }
 780     };
 781
 782
 783     TEST_F( Split_bitstrig, cut_uint )
 784     {
 785         if ( is_big_endian())
 786             cut_uint_be();
 787         else
 788             cut_uint_le();
 789     }
 790
 791     TEST_F( Split_bitstrig, cut_uint16 )
 792     {
 793         if ( is_big_endian())
 794             cut_small_be<uint16_t>();
 795         else
 796             cut_small_le<uint16_t>();
 797     }
 798
 799     TEST_F( Split_bitstrig, cut_int48 )
 800     {
 801         if ( is_big_endian() )
 802             cut_int48_be();
 803         else
 804             cut_int48_le();
 805     }
 806
 807     TEST_F( Split_bitstrig, cut_byte )
 808     {
 809         if ( is_big_endian() )
 810             cut_byte_be();
 811         else
 812             cut_byte_le();
 813     }
 814
 815     TEST_F( Split_number, split_int )
 816     {
 817         split( (int)0x76543210 );
 818     }
 819
 820     TEST_F( Split_number, split_uint )
 821     {
 822         split( (unsigned)0x76543210 );
 823     }
 824
 825     TEST_F( Split_number, split_short )
 826     {
 827         split( (short int)0x3210 );
 828     }
 829
 830     TEST_F( Split_number, split_ushort )
 831     {
 832         split( (unsigned short)0x3210 );
 833     }
 834
 835     TEST_F( Split_number, split_long )
 836     {
 837         if ( sizeof( long ) == 8 )
 838             split( (long)0xFEDCBA9876543210 );
 839         else
 840             split( (long)0x76543210 );
 841     }
 842
 843     TEST_F( Split_number, split_ulong )
 844     {
 845         if ( sizeof( long ) == 8 )
 846             split( (unsigned long)0xFEDCBA9876543210 );
 847         else
 848             split( (unsigned long)0x76543210 );
 849     }
 850
 851     TEST_F( Split_number, split_int64 )
 852     {
 853         split( (int64_t)0xFEDCBA9876543210 );
 854     }
 855
 856     TEST_F( Split_number, split_uint64 )
 857     {
 858         split( (uint64_t)0xFEDCBA9876543210 );
 859     }
 860
 861 } // namespace