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 <cds_test/ext_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 #if 0
 427             friend bool operator ==( int48 lhs, int48 rhs )
 428             {
 429                 return lhs.n32 == rhs.n32 && lhs.n16 == rhs.n16;
 430             }
 431 #endif
 432
 433             uint64_t to64() const
 434             {
 435 #       ifdef CDS_ARCH_LITTLE_ENDIAN
 436                 return ( static_cast<uint64_t>( n16 ) << 32 ) + n32;
 437 #       else
 438                 return ( static_cast<uint64_t>( n32 ) << 16 ) + n16;
 439 #       endif
 440             }
 441         };
 442         static constexpr size_t int48_size = 6;
 443
 444         void cut_int48_le()
 445         {
 446             int48 src;
 447             src.n32 = 0x76543210;
 448             src.n16 = 0xBA98;
 449
 450             uint64_t res;
 451
 452 #if CDS_BUILD_BITS == 64
 453             {
 454                 typedef cds::algo::split_bitstring< int48, int48_size, size_t > split_bitstring;
 455                 split_bitstring splitter( src );
 456
 457                 // Trivial case
 458                 ASSERT_FALSE( splitter.eos());
 459                 ASSERT_FALSE( !splitter );
 460                 res = splitter.cut( int48_size * 8 );
 461                 EXPECT_EQ( res, src.to64());
 462                 ASSERT_TRUE( splitter.eos());
 463                 ASSERT_TRUE( !splitter );
 464                 EXPECT_EQ( splitter.safe_cut( int48_size * 8 ), 0u );
 465                 ASSERT_TRUE( splitter.eos());
 466                 ASSERT_TRUE( !splitter );
 467                 splitter.reset();
 468                 ASSERT_FALSE( splitter.eos());
 469                 ASSERT_FALSE( !splitter );
 470                 res = splitter.cut( int48_size * 8 );
 471                 EXPECT_EQ( res, src.to64());
 472                 ASSERT_TRUE( splitter.eos());
 473                 ASSERT_TRUE( !splitter );
 474                 EXPECT_EQ( splitter.safe_cut( int48_size * 8 ), 0u );
 475                 ASSERT_TRUE( splitter.eos());
 476                 ASSERT_TRUE( !splitter );
 477             }
 478 #endif
 479
 480             typedef cds::algo::split_bitstring< int48, int48_size, size_t > split_bitstring;
 481             split_bitstring splitter( src );
 482
 483             EXPECT_EQ( splitter.source()->to64(), src.to64());
 484             EXPECT_EQ( splitter.rest_count(), int48_size * 8 );
 485             EXPECT_EQ( splitter.bit_offset(), 0u );
 486
 487             // Cut each hex digit
 488             splitter.reset();
 489             for ( size_t i = 0; i < int48_size * 2; ++i ) {
 490                 ASSERT_FALSE( splitter.eos());
 491                 ASSERT_FALSE( !splitter );
 492                 ASSERT_EQ( splitter.cut( 4 ), i );
 493             }
 494             ASSERT_TRUE( splitter.eos());
 495             ASSERT_FALSE( splitter );
 496             EXPECT_EQ( splitter.safe_cut( 8 ), 0u );
 497             EXPECT_EQ( splitter.source()->to64(), src.to64());
 498             EXPECT_EQ( splitter.rest_count(), 0u );
 499             EXPECT_EQ( splitter.bit_offset(), int48_size * 8 );
 500
 501             // by one bit
 502             {
 503                 splitter.reset();
 504                 EXPECT_EQ( splitter.source()->to64(), src.to64());
 505                 EXPECT_EQ( splitter.rest_count(), int48_size * 8 );
 506                 EXPECT_EQ( splitter.bit_offset(), 0u );
 507
 508                 res = 0;
 509                 for ( size_t i = 0; i < int48_size * 8; ++i ) {
 510                     ASSERT_FALSE( splitter.eos());
 511                     ASSERT_FALSE( !splitter );
 512 #if CDS_BUILD_BITS == 64
 513                     res |= splitter.cut( 1 ) << i;
 514 #else
 515                     res |= static_cast<decltype(res)>( splitter.cut( 1 )) << i;
 516 #endif
 517                 }
 518                 ASSERT_TRUE( splitter.eos());
 519                 ASSERT_TRUE( !splitter );
 520                 EXPECT_EQ( res, src.to64());
 521                 EXPECT_EQ( splitter.safe_cut( 8 ), 0u );
 522                 EXPECT_EQ( splitter.source()->to64(), src.to64());
 523                 EXPECT_EQ( splitter.rest_count(), 0u );
 524                 EXPECT_EQ( splitter.bit_offset(), int48_size * 8 );
 525             }
 526
 527             // random cut
 528             {
 529                 for ( size_t k = 0; k < 100; ++k ) {
 530                     splitter.reset();
 531                     EXPECT_EQ( splitter.source()->to64(), src.to64());
 532                     EXPECT_EQ( splitter.rest_count(), int48_size * 8 );
 533                     EXPECT_EQ( splitter.bit_offset(), 0u );
 534
 535                     res = 0;
 536                     size_t shift = 0;
 537                     while ( splitter ) {
 538                         ASSERT_FALSE( splitter.eos());
 539                         ASSERT_FALSE( !splitter );
 540                         int bits = std::rand() % 16;
 541 #if CDS_BUILD_BITS == 64
 542                         res |= splitter.safe_cut( bits ) << shift;
 543 #else
 544                         res |= static_cast<decltype(res)>( splitter.safe_cut( bits )) << shift;
 545 #endif
 546                         shift += bits;
 547                     }
 548                     ASSERT_TRUE( splitter.eos());
 549                     ASSERT_TRUE( !splitter );
 550                     EXPECT_EQ( res, src.to64());
 551                     EXPECT_EQ( splitter.safe_cut( 8 ), 0u );
 552                     EXPECT_EQ( splitter.source()->to64(), src.to64());
 553                     EXPECT_EQ( splitter.rest_count(), 0u );
 554                     EXPECT_EQ( splitter.bit_offset(), int48_size * 8 );
 555                 }
 556             }
 557         }
 558
 559         void cut_int48_be()
 560         {
 561             int48 src;
 562             src.n32 = 0xBA987654;
 563             src.n16 = 0x3210;
 564
 565             uint64_t res;
 566
 567 #if CDS_BUILD_BITS == 64
 568             {
 569                 typedef cds::algo::split_bitstring< int48, int48_size, size_t > split_bitstring;
 570                 split_bitstring splitter( src );
 571
 572                 // Trivial case
 573                 ASSERT_FALSE( splitter.eos());
 574                 ASSERT_FALSE( !splitter );
 575                 res = splitter.cut( int48_size * 8 );
 576                 ASSERT_EQ( res, src.to64());
 577                 ASSERT_TRUE( splitter.eos());
 578                 ASSERT_TRUE( !splitter );
 579                 EXPECT_EQ( splitter.safe_cut( int48_size * 8 ), 0u );
 580                 ASSERT_TRUE( splitter.eos());
 581                 ASSERT_TRUE( !splitter );
 582                 splitter.reset();
 583                 ASSERT_FALSE( splitter.eos());
 584                 ASSERT_FALSE( !splitter );
 585                 res = splitter.cut( int48_size * 8 );
 586                 EXPECT_EQ( res, src.to64());
 587                 ASSERT_TRUE( splitter.eos());
 588                 ASSERT_TRUE( !splitter );
 589                 EXPECT_EQ( splitter.safe_cut( int48_size * 8 ), 0u );
 590                 ASSERT_TRUE( splitter.eos());
 591                 ASSERT_TRUE( !splitter );
 592             }
 593 #endif
 594
 595             typedef cds::algo::split_bitstring< int48, int48_size, size_t > split_bitstring;
 596             split_bitstring splitter( src );
 597
 598             EXPECT_EQ( splitter.source()->to64(), src.to64());
 599             EXPECT_EQ( splitter.rest_count(), int48_size * 8 );
 600             EXPECT_EQ( splitter.bit_offset(), 0u );
 601
 602             // Cut each hex digit
 603             splitter.reset();
 604             for ( size_t i = 0; i < int48_size * 2; ++i ) {
 605                 ASSERT_FALSE( splitter.eos());
 606                 ASSERT_FALSE( !splitter );
 607                 if ( i % 2 == 0 ) {
 608                     EXPECT_EQ( splitter.cut( 4 ), 0x0A - i );
 609                 }
 610                 else {
 611                     EXPECT_EQ( splitter.cut( 4 ), 0x0B - i + 1 );
 612                 }
 613             }
 614             ASSERT_TRUE( splitter.eos());
 615             ASSERT_TRUE( !splitter );
 616             EXPECT_EQ( splitter.safe_cut( 8 ), 0u );
 617             EXPECT_EQ( splitter.source()->to64(), src.to64());
 618             EXPECT_EQ( splitter.rest_count(), 0u );
 619             EXPECT_EQ( splitter.bit_offset(), int48_size * 8 );
 620
 621             // by one bit
 622             {
 623                 splitter.reset();
 624                 EXPECT_EQ( splitter.source()->to64(), src.to64());
 625                 EXPECT_EQ( splitter.rest_count(), int48_size * 8 );
 626                 EXPECT_EQ( splitter.bit_offset(), 0u );
 627
 628                 res = 0;
 629                 for ( size_t i = 0; i < int48_size * 8; ++i ) {
 630                     ASSERT_FALSE( splitter.eos());
 631                     ASSERT_FALSE( !splitter );
 632 #if CDS_BUILD_BITS == 64
 633                     if ( i % 8 == 0 )
 634                         res = res << 8;
 635                     res |= ( splitter.cut( 1 )) << ( i % 8 );
 636 #else
 637                     res = ( res << 1 ) | static_cast<decltype(res)>( splitter.cut( 1 ));
 638 #endif
 639                 }
 640                 ASSERT_TRUE( splitter.eos());
 641                 ASSERT_TRUE( !splitter );
 642                 EXPECT_EQ( res, src.to64());
 643                 EXPECT_EQ( splitter.safe_cut( 8 ), 0u );
 644                 EXPECT_EQ( splitter.source()->to64(), src.to64());
 645                 EXPECT_EQ( splitter.rest_count(), 0u );
 646                 EXPECT_EQ( splitter.bit_offset(), int48_size * 8 );
 647             }
 648
 649             // random cut
 650             /*
 651             {
 652                 for ( size_t k = 0; k < 100; ++k ) {
 653                     splitter.reset();
 654                     EXPECT_EQ( splitter.source()->to64(), src.to64());
 655                     EXPECT_EQ( splitter.rest_count(), int48_size * 8 );
 656                     EXPECT_EQ( splitter.bit_offset(), 0u );
 657
 658                     res = 0;
 659                     while ( splitter ) {
 660                         ASSERT_FALSE( splitter.eos());
 661                         ASSERT_FALSE( !splitter );
 662                         unsigned bits = std::rand() % 16;
 663                         size_t shift = splitter.rest_count();
 664                         if ( shift > bits )
 665                             shift = bits;
 666 #if CDS_BUILD_BITS == 64
 667                         res = ( res << shift ) | splitter.safe_cut( bits );
 668 #else
 669                         res = ( res << shift ) | static_cast<decltype(res)>( splitter.safe_cut( bits ));
 670 #endif
 671                     }
 672                     ASSERT_TRUE( splitter.eos());
 673                     ASSERT_TRUE( !splitter );
 674                     EXPECT_EQ( res, src.to64());
 675                     EXPECT_EQ( splitter.safe_cut( 8 ), 0u );
 676                     EXPECT_EQ( splitter.source()->to64(), src.to64());
 677                     EXPECT_EQ( splitter.rest_count(), 0u );
 678                     EXPECT_EQ( splitter.bit_offset(), int48_size * 8 );
 679                 }
 680             }
 681             */
 682         }
 683
 684         void cut_byte_le()
 685         {
 686             size_t src = sizeof( src ) == 8 ? 0xFEDCBA9876543210 : 0x76543210;
 687
 688             typedef cds::algo::byte_splitter< size_t > splitter_type;
 689             splitter_type splitter( src );
 690
 691             ASSERT_TRUE( !splitter.eos());
 692             EXPECT_EQ( *splitter.source(), src );
 693             EXPECT_EQ( splitter.rest_count(), sizeof( src ) * 8 );
 694             EXPECT_EQ( splitter.bit_offset(), 0u );
 695             EXPECT_TRUE( splitter.is_correct( 8 ));
 696             EXPECT_FALSE( splitter.is_correct( 4 ));
 697
 698             unsigned expected = 0x10;
 699             for ( unsigned i = 0; i < splitter_type::c_bitstring_size; ++i ) {
 700                 auto part = splitter.cut( 8 );
 701                 EXPECT_EQ( part, expected );
 702                 expected += 0x22;
 703             }
 704
 705             ASSERT_TRUE( splitter.eos());
 706             EXPECT_EQ( splitter.safe_cut( 8 ), 0u );
 707             EXPECT_EQ( *splitter.source(), src );
 708             EXPECT_EQ( splitter.rest_count(), 0u );
 709             EXPECT_EQ( splitter.bit_offset(), sizeof( src ) * 8 );
 710         }
 711
 712         void cut_byte_be()
 713         {
 714             size_t src = sizeof( src ) == 8 ? 0xFEDCBA9876543210 : 0x76543210;
 715
 716             typedef cds::algo::byte_splitter< size_t > splitter_type;
 717             splitter_type splitter( src );
 718
 719             ASSERT_TRUE( !splitter.eos());
 720             EXPECT_EQ( *splitter.source(), src );
 721             EXPECT_EQ( splitter.rest_count(), sizeof( src ) * 8 );
 722             EXPECT_EQ( splitter.bit_offset(), 0u );
 723             EXPECT_TRUE( splitter.is_correct( 8 ));
 724             EXPECT_FALSE( splitter.is_correct( 4 ));
 725
 726             unsigned expected = 0xFE;
 727             for ( unsigned i = 0; i < splitter_type::c_bitstring_size; ++i ) {
 728                 auto part = splitter.cut( 8 );
 729                 EXPECT_EQ( part, expected );
 730                 expected -= 0x22;
 731             }
 732
 733             ASSERT_TRUE( splitter.eos());
 734             EXPECT_EQ( splitter.safe_cut( 8 ), 0u );
 735             EXPECT_EQ( *splitter.source(), src );
 736             EXPECT_EQ( splitter.rest_count(), 0u );
 737             EXPECT_EQ( splitter.bit_offset(), sizeof( src ) * 8 );
 738         }
 739     };
 740
 741     class Split_number: public ::testing::Test
 742     {
 743     protected:
 744         template <typename Int>
 745         void split( Int const n )
 746         {
 747             cds::algo::number_splitter< Int > splitter( n );
 748
 749             // split by hex digit
 750             for ( unsigned count = 4; count < sizeof( Int ) * 8; count += 4 ) {
 751                 EXPECT_EQ( splitter.cut( 4 ), static_cast<Int>( count / 4 - 1 ));
 752             }
 753
 754             // random cut
 755             for ( int i = 0; i < 100; ++i ) {
 756                 splitter.reset();
 757                 EXPECT_EQ( splitter.source(), n );
 758                 EXPECT_EQ( splitter.bit_offset(), 0u );
 759                 EXPECT_EQ( splitter.rest_count(), sizeof( Int ) * 8 );
 760
 761                 unsigned total = 0;
 762                 Int result = 0;
 763
 764                 while ( total < sizeof( Int ) * 8 ) {
 765                     unsigned count = std::rand() % 16;
 766
 767                     unsigned shift = count;
 768                     if ( total + count > sizeof( Int ) * 8 )
 769                         shift = sizeof( Int ) * 8 - total;
 770
 771                     result += splitter.safe_cut( count ) << total;
 772                     total += shift;
 773                 }
 774
 775                 EXPECT_EQ( result, n );
 776
 777                 EXPECT_EQ( splitter.bit_offset(), sizeof( Int ) * 8 );
 778                 EXPECT_EQ( splitter.rest_count(), 0u );
 779             }
 780         }
 781     };
 782
 783
 784     TEST_F( Split_bitstrig, cut_uint )
 785     {
 786         if ( is_big_endian())
 787             cut_uint_be();
 788         else
 789             cut_uint_le();
 790     }
 791
 792     TEST_F( Split_bitstrig, cut_uint16 )
 793     {
 794         if ( is_big_endian())
 795             cut_small_be<uint16_t>();
 796         else
 797             cut_small_le<uint16_t>();
 798     }
 799
 800     TEST_F( Split_bitstrig, cut_int48 )
 801     {
 802         if ( is_big_endian())
 803             cut_int48_be();
 804         else
 805             cut_int48_le();
 806     }
 807
 808     TEST_F( Split_bitstrig, cut_byte )
 809     {
 810         if ( is_big_endian())
 811             cut_byte_be();
 812         else
 813             cut_byte_le();
 814     }
 815
 816     TEST_F( Split_number, split_int )
 817     {
 818         split( (int)0x76543210 );
 819     }
 820
 821     TEST_F( Split_number, split_uint )
 822     {
 823         split( (unsigned)0x76543210 );
 824     }
 825
 826     TEST_F( Split_number, split_short )
 827     {
 828         split( (short int)0x3210 );
 829     }
 830
 831     TEST_F( Split_number, split_ushort )
 832     {
 833         split( (unsigned short)0x3210 );
 834     }
 835
 836     TEST_F( Split_number, split_long )
 837     {
 838         if ( sizeof( long ) == 8 )
 839             split( (long)0xFEDCBA9876543210 );
 840         else
 841             split( (long)0x76543210 );
 842     }
 843
 844     TEST_F( Split_number, split_ulong )
 845     {
 846         if ( sizeof( long ) == 8 )
 847             split( (unsigned long)0xFEDCBA9876543210 );
 848         else
 849             split( (unsigned long)0x76543210 );
 850     }
 851
 852     TEST_F( Split_number, split_int64 )
 853     {
 854         split( (int64_t)0xFEDCBA9876543210 );
 855     }
 856
 857     TEST_F( Split_number, split_uint64 )
 858     {
 859         split( (uint64_t)0xFEDCBA9876543210 );
 860     }
 861
 862 } // namespace