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                 EXPECT_EQ( splitter.cut( 4 ), 0x0F - i );
 187             }
 188             ASSERT_TRUE( splitter.eos());
 189             ASSERT_TRUE( !splitter );
 190             EXPECT_EQ( splitter.safe_cut( 8 ), 0u );
 191             EXPECT_EQ( *splitter.source(), src );
 192             EXPECT_EQ( splitter.rest_count(), 0u );
 193             EXPECT_EQ( splitter.bit_offset(), sizeof( src ) * 8 );
 194
 195             // by one bit
 196             {
 197                 splitter.reset();
 198                 EXPECT_EQ( *splitter.source(), src );
 199                 EXPECT_EQ( splitter.rest_count(), sizeof( src ) * 8 );
 200                 EXPECT_EQ( splitter.bit_offset(), 0u );
 201
 202                 res = 0;
 203                 for ( size_t i = 0; i < sizeof(size_t) * 8; ++i ) {
 204                     ASSERT_FALSE( splitter.eos());
 205                     ASSERT_FALSE( !splitter );
 206                     res = ( res << 1 ) | ( splitter.cut( 1 ) );
 207                 }
 208                 ASSERT_TRUE( splitter.eos());
 209                 ASSERT_TRUE( !splitter );
 210                 EXPECT_EQ( res, src );
 211
 212                 EXPECT_EQ( splitter.safe_cut( 8 ), 0u );
 213                 EXPECT_EQ( *splitter.source(), src );
 214                 EXPECT_EQ( splitter.rest_count(), 0u );
 215                 EXPECT_EQ( splitter.bit_offset(), sizeof( src ) * 8 );
 216             }
 217
 218             // random cut
 219             {
 220                 for ( size_t k = 0; k < 100; ++k ) {
 221                     splitter.reset();
 222                     EXPECT_EQ( *splitter.source(), src );
 223                     EXPECT_EQ( splitter.rest_count(), sizeof( src ) * 8 );
 224                     EXPECT_EQ( splitter.bit_offset(), 0u );
 225
 226                     res = 0;
 227                     while ( splitter ) {
 228                         ASSERT_FALSE( splitter.eos());
 229                         ASSERT_FALSE( !splitter );
 230                         unsigned bits = std::rand() % 16;
 231                         size_t shift = splitter.rest_count();
 232                         if ( shift > bits )
 233                             shift = bits;
 234                         res = (res << shift) | splitter.safe_cut( bits );
 235                     }
 236                     ASSERT_TRUE( splitter.eos());
 237                     ASSERT_TRUE( !splitter );
 238                     EXPECT_EQ( res, src );
 239
 240                     EXPECT_EQ( splitter.safe_cut( 8 ), 0u );
 241                     EXPECT_EQ( *splitter.source(), src );
 242                     EXPECT_EQ( splitter.rest_count(), 0u );
 243                     EXPECT_EQ( splitter.bit_offset(), sizeof( src ) * 8 );
 244                 }
 245             }
 246         }
 247
 248         template <typename PartUInt>
 249         void cut_small_le()
 250         {
 251             typedef PartUInt part_uint;
 252
 253             typedef cds::algo::split_bitstring< uint64_t, 0, part_uint > split_bitstring;
 254
 255             uint64_t src = 0xFEDCBA9876543210;
 256             split_bitstring splitter(src);
 257             uint64_t res;
 258
 259             EXPECT_EQ( *splitter.source(), src );
 260             EXPECT_EQ( splitter.rest_count(), sizeof( src ) * 8 );
 261             EXPECT_EQ( splitter.bit_offset(), 0u );
 262
 263             // Cut each hex digit
 264             splitter.reset();
 265             for ( size_t i = 0; i < sizeof(src) * 2; ++i ) {
 266                 ASSERT_FALSE( splitter.eos());
 267                 ASSERT_FALSE( !splitter );
 268                 EXPECT_EQ( static_cast<size_t>(splitter.cut( 4 )), i );
 269             }
 270             ASSERT_TRUE( splitter.eos());
 271             ASSERT_TRUE( !splitter );
 272             EXPECT_EQ( splitter.safe_cut( 8 ), 0u );
 273             EXPECT_EQ( *splitter.source(), src );
 274             EXPECT_EQ( splitter.rest_count(), 0u );
 275             EXPECT_EQ( splitter.bit_offset(), sizeof( src ) * 8 );
 276
 277             // by one bit
 278             {
 279                 splitter.reset();
 280                 EXPECT_EQ( *splitter.source(), src );
 281                 EXPECT_EQ( splitter.rest_count(), sizeof( src ) * 8 );
 282                 EXPECT_EQ( splitter.bit_offset(), 0u );
 283
 284                 res = 0;
 285                 for ( size_t i = 0; i < sizeof(src) * 8; ++i ) {
 286                     ASSERT_FALSE( splitter.eos());
 287                     ASSERT_FALSE( !splitter );
 288                     res += static_cast<uint64_t>(splitter.cut( 1 )) << i;
 289                 }
 290                 ASSERT_TRUE( splitter.eos());
 291                 ASSERT_TRUE( !splitter );
 292                 EXPECT_EQ( res, src );
 293                 EXPECT_EQ( splitter.safe_cut( 8 ), 0u );
 294                 EXPECT_EQ( *splitter.source(), src );
 295                 EXPECT_EQ( splitter.rest_count(), 0u );
 296                 EXPECT_EQ( splitter.bit_offset(), sizeof( src ) * 8 );
 297             }
 298
 299             // random cut
 300             {
 301                 for ( size_t k = 0; k < 100; ++k ) {
 302                     splitter.reset();
 303                     EXPECT_EQ( *splitter.source(), src );
 304                     EXPECT_EQ( splitter.rest_count(), sizeof( src ) * 8 );
 305                     EXPECT_EQ( splitter.bit_offset(), 0u );
 306
 307                     res = 0;
 308                     size_t shift = 0;
 309                     while ( splitter ) {
 310                         ASSERT_FALSE( splitter.eos());
 311                         ASSERT_FALSE( !splitter );
 312                         int bits = std::rand() % 16;
 313                         res += static_cast<uint64_t>(splitter.safe_cut( bits )) << shift;
 314                         shift += bits;
 315                     }
 316                     ASSERT_TRUE( splitter.eos());
 317                     ASSERT_TRUE( !splitter );
 318                     EXPECT_EQ( res, src );
 319                     EXPECT_EQ( splitter.safe_cut( 8 ), 0u );
 320                     EXPECT_EQ( *splitter.source(), src );
 321                     EXPECT_EQ( splitter.rest_count(), 0u );
 322                     EXPECT_EQ( splitter.bit_offset(), sizeof( src ) * 8 );
 323                 }
 324             }
 325         }
 326
 327         template <typename PartUInt>
 328         void cut_small_be()
 329         {
 330             typedef PartUInt part_uint;
 331
 332             typedef cds::algo::split_bitstring< uint64_t, 0, part_uint > split_bitstring;
 333
 334             uint64_t src = 0xFEDCBA9876543210;
 335             split_bitstring splitter(src);
 336             uint64_t res;
 337
 338             EXPECT_EQ( *splitter.source(), src );
 339             EXPECT_EQ( splitter.rest_count(), sizeof( src ) * 8 );
 340             EXPECT_EQ( splitter.bit_offset(), 0u );
 341
 342             // Cut each hex digit
 343             splitter.reset();
 344             for ( size_t i = 0; i < sizeof(size_t) * 2; ++i ) {
 345                 ASSERT_FALSE( splitter.eos());
 346                 ASSERT_FALSE( !splitter );
 347                 EXPECT_EQ( splitter.cut( 4 ), 0x0F - i );
 348             }
 349             ASSERT_TRUE( splitter.eos());
 350             ASSERT_TRUE( !splitter );
 351
 352             // by one bit
 353             {
 354                 splitter.reset();
 355                 EXPECT_EQ( *splitter.source(), src );
 356                 EXPECT_EQ( splitter.rest_count(), sizeof( src ) * 8 );
 357                 EXPECT_EQ( splitter.bit_offset(), 0u );
 358
 359                 res = 0;
 360                 for ( size_t i = 0; i < sizeof(size_t) * 8; ++i ) {
 361                     ASSERT_FALSE( splitter.eos());
 362                     ASSERT_FALSE( !splitter );
 363                     res = (res << 1) + splitter.cut( 1 );
 364                 }
 365                 ASSERT_TRUE( splitter.eos());
 366                 ASSERT_TRUE( !splitter );
 367                 EXPECT_EQ( res, src );
 368                 EXPECT_EQ( splitter.safe_cut( 8 ), 0u );
 369                 EXPECT_EQ( *splitter.source(), src );
 370                 EXPECT_EQ( splitter.rest_count(), 0u );
 371                 EXPECT_EQ( splitter.bit_offset(), sizeof( src ) * 8 );
 372             }
 373
 374             // random cut
 375             {
 376                 for ( size_t k = 0; k < 100; ++k ) {
 377                     splitter.reset();
 378                     EXPECT_EQ( *splitter.source(), src );
 379                     EXPECT_EQ( splitter.rest_count(), sizeof( src ) * 8 );
 380                     EXPECT_EQ( splitter.bit_offset(), 0u );
 381
 382                     res = 0;
 383                     while ( splitter ) {
 384                         ASSERT_FALSE( splitter.eos());
 385                         ASSERT_FALSE( !splitter );
 386                         unsigned bits = std::rand() % 16;
 387                         size_t shift = splitter.rest_count();
 388                         if ( shift > bits )
 389                             shift = bits;
 390                         res = ( res << shift ) | splitter.safe_cut( bits );
 391                     }
 392                     ASSERT_TRUE( splitter.eos());
 393                     ASSERT_TRUE( !splitter );
 394                     EXPECT_EQ( res, src );
 395                     EXPECT_EQ( splitter.safe_cut( 8 ), 0u );
 396                     EXPECT_EQ( *splitter.source(), src );
 397                     EXPECT_EQ( splitter.rest_count(), 0u );
 398                     EXPECT_EQ( splitter.bit_offset(), sizeof( src ) * 8 );
 399                 }
 400             }
 401         }
 402
 403         struct int48 {
 404             uint32_t    n32;
 405             uint16_t    n16;
 406
 407             friend bool operator ==( int48 lhs, int48 rhs )
 408             {
 409                 return lhs.n32 == rhs.n32 && lhs.n16 == rhs.n16;
 410             }
 411
 412             uint64_t to64() const
 413             {
 414 #       ifdef CDS_ARCH_LITTLE_ENDIAN
 415                 return ( static_cast<uint64_t>( n16 ) << 32 ) + n32;
 416 #       else
 417                 return ( static_cast<uint64_t>( n32 ) << 16 ) + n16;
 418 #       endif
 419             }
 420         };
 421         static constexpr size_t int48_size = 6;
 422
 423         void cut_int48_le()
 424         {
 425             int48 src;
 426             src.n32 = 0x76543210;
 427             src.n16 = 0xBA98;
 428
 429             uint64_t res;
 430
 431 #if CDS_BUILD_BITS == 64
 432             {
 433                 typedef cds::algo::split_bitstring< int48, int48_size, size_t > split_bitstring;
 434                 split_bitstring splitter( src );
 435
 436                 // Trivial case
 437                 ASSERT_FALSE( splitter.eos() );
 438                 ASSERT_FALSE( !splitter );
 439                 res = splitter.cut( int48_size * 8 );
 440                 EXPECT_EQ( res, src.to64() );
 441                 ASSERT_TRUE( splitter.eos() );
 442                 ASSERT_TRUE( !splitter );
 443                 EXPECT_EQ( splitter.safe_cut( int48_size * 8 ), 0u );
 444                 ASSERT_TRUE( splitter.eos() );
 445                 ASSERT_TRUE( !splitter );
 446                 splitter.reset();
 447                 ASSERT_FALSE( splitter.eos() );
 448                 ASSERT_FALSE( !splitter );
 449                 res = splitter.cut( int48_size * 8 );
 450                 EXPECT_EQ( res, src.to64() );
 451                 ASSERT_TRUE( splitter.eos() );
 452                 ASSERT_TRUE( !splitter );
 453                 EXPECT_EQ( splitter.safe_cut( int48_size * 8 ), 0u );
 454                 ASSERT_TRUE( splitter.eos() );
 455                 ASSERT_TRUE( !splitter );
 456             }
 457 #endif
 458
 459             typedef cds::algo::split_bitstring< int48, int48_size, size_t > split_bitstring;
 460             split_bitstring splitter( src );
 461
 462             EXPECT_EQ( splitter.source()->to64(), src.to64() );
 463             EXPECT_EQ( splitter.rest_count(), int48_size * 8 );
 464             EXPECT_EQ( splitter.bit_offset(), 0u );
 465
 466             // Cut each hex digit
 467             splitter.reset();
 468             for ( size_t i = 0; i < int48_size * 2; ++i ) {
 469                 ASSERT_FALSE( splitter.eos() );
 470                 ASSERT_FALSE( !splitter );
 471                 ASSERT_EQ( splitter.cut( 4 ), i );
 472             }
 473             ASSERT_TRUE( splitter.eos() );
 474             ASSERT_FALSE( splitter );
 475             EXPECT_EQ( splitter.safe_cut( 8 ), 0u );
 476             EXPECT_EQ( splitter.source()->to64(), src.to64() );
 477             EXPECT_EQ( splitter.rest_count(), 0u );
 478             EXPECT_EQ( splitter.bit_offset(), int48_size * 8 );
 479
 480             // by one bit
 481             {
 482                 splitter.reset();
 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                 res = 0;
 488                 for ( size_t i = 0; i < int48_size * 8; ++i ) {
 489                     ASSERT_FALSE( splitter.eos() );
 490                     ASSERT_FALSE( !splitter );
 491 #if CDS_BUILD_BITS == 64
 492                     res |= splitter.cut( 1 ) << i;
 493 #else
 494                     res |= static_cast<decltype(res)>( splitter.cut( 1 )) << i;
 495 #endif
 496                 }
 497                 ASSERT_TRUE( splitter.eos() );
 498                 ASSERT_TRUE( !splitter );
 499                 EXPECT_EQ( res, src.to64() );
 500                 EXPECT_EQ( splitter.safe_cut( 8 ), 0u );
 501                 EXPECT_EQ( splitter.source()->to64(), src.to64() );
 502                 EXPECT_EQ( splitter.rest_count(), 0u );
 503                 EXPECT_EQ( splitter.bit_offset(), int48_size * 8 );
 504             }
 505
 506             // random cut
 507             {
 508                 for ( size_t k = 0; k < 100; ++k ) {
 509                     splitter.reset();
 510                     EXPECT_EQ( splitter.source()->to64(), src.to64() );
 511                     EXPECT_EQ( splitter.rest_count(), int48_size * 8 );
 512                     EXPECT_EQ( splitter.bit_offset(), 0u );
 513
 514                     res = 0;
 515                     size_t shift = 0;
 516                     while ( splitter ) {
 517                         ASSERT_FALSE( splitter.eos() );
 518                         ASSERT_FALSE( !splitter );
 519                         int bits = std::rand() % 16;
 520 #if CDS_BUILD_BITS == 64
 521                         res |= splitter.safe_cut( bits ) << shift;
 522 #else
 523                         res |= static_cast<decltype(res)>( splitter.safe_cut( bits )) << shift;
 524 #endif
 525                         shift += bits;
 526                     }
 527                     ASSERT_TRUE( splitter.eos() );
 528                     ASSERT_TRUE( !splitter );
 529                     EXPECT_EQ( res, src.to64() );
 530                     EXPECT_EQ( splitter.safe_cut( 8 ), 0u );
 531                     EXPECT_EQ( splitter.source()->to64(), src.to64() );
 532                     EXPECT_EQ( splitter.rest_count(), 0u );
 533                     EXPECT_EQ( splitter.bit_offset(), int48_size * 8 );
 534                 }
 535             }
 536         }
 537
 538         void cut_int48_be()
 539         {
 540             int48 src;
 541             src.n32 = 0xBA987654;
 542             src.n16 = 0x3210;
 543
 544             uint64_t res;
 545
 546 #if CDS_BUILD_BITS == 64
 547             {
 548                 typedef cds::algo::split_bitstring< int48, int48_size, size_t > split_bitstring;
 549                 split_bitstring splitter( src );
 550
 551                 // Trivial case
 552                 ASSERT_FALSE( splitter.eos() );
 553                 ASSERT_FALSE( !splitter );
 554                 res = splitter.cut( int48_size * 8 );
 555                 ASSERT_EQ( res, src.to64() );
 556                 ASSERT_TRUE( splitter.eos() );
 557                 ASSERT_TRUE( !splitter );
 558                 EXPECT_EQ( splitter.safe_cut( int48_size * 8 ), 0u );
 559                 ASSERT_TRUE( splitter.eos() );
 560                 ASSERT_TRUE( !splitter );
 561                 splitter.reset();
 562                 ASSERT_FALSE( splitter.eos() );
 563                 ASSERT_FALSE( !splitter );
 564                 res = splitter.cut( int48_size * 8 );
 565                 EXPECT_EQ( res, src.to64() );
 566                 ASSERT_TRUE( splitter.eos() );
 567                 ASSERT_TRUE( !splitter );
 568                 EXPECT_EQ( splitter.safe_cut( int48_size * 8 ), 0u );
 569                 ASSERT_TRUE( splitter.eos() );
 570                 ASSERT_TRUE( !splitter );
 571             }
 572 #endif
 573
 574             typedef cds::algo::split_bitstring< int48, int48_size, size_t > split_bitstring;
 575             split_bitstring splitter( src );
 576
 577             EXPECT_EQ( splitter.source()->to64(), src.to64() );
 578             EXPECT_EQ( splitter.rest_count(), int48_size * 8 );
 579             EXPECT_EQ( splitter.bit_offset(), 0u );
 580
 581             // Cut each hex digit
 582             splitter.reset();
 583             for ( size_t i = 0; i < int48_size * 2; ++i ) {
 584                 ASSERT_FALSE( splitter.eos() );
 585                 ASSERT_FALSE( !splitter );
 586                 EXPECT_EQ( splitter.cut( 4 ), 0x0B - i );
 587             }
 588             ASSERT_TRUE( splitter.eos() );
 589             ASSERT_TRUE( !splitter );
 590             EXPECT_EQ( splitter.safe_cut( 8 ), 0u );
 591             EXPECT_EQ( splitter.source()->to64(), src.to64() );
 592             EXPECT_EQ( splitter.rest_count(), 0u );
 593             EXPECT_EQ( splitter.bit_offset(), int48_size * 8 );
 594
 595             // by one bit
 596             {
 597                 splitter.reset();
 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                 res = 0;
 603                 for ( size_t i = 0; i < int48_size * 8; ++i ) {
 604                     ASSERT_FALSE( splitter.eos() );
 605                     ASSERT_FALSE( !splitter );
 606 #if CDS_BUILD_BITS == 64
 607                     res = ( res << 1 ) | ( splitter.cut( 1 ) );
 608 #else
 609                     res = ( res << 1 ) | static_cast<decltype(res)>( splitter.cut( 1 ) );
 610 #endif
 611                 }
 612                 ASSERT_TRUE( splitter.eos() );
 613                 ASSERT_TRUE( !splitter );
 614                 EXPECT_EQ( res, src.to64() );
 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
 621             // random cut
 622             {
 623                 for ( size_t k = 0; k < 100; ++k ) {
 624                     splitter.reset();
 625                     EXPECT_EQ( splitter.source()->to64(), src.to64() );
 626                     EXPECT_EQ( splitter.rest_count(), int48_size * 8 );
 627                     EXPECT_EQ( splitter.bit_offset(), 0u );
 628
 629                     res = 0;
 630                     while ( splitter ) {
 631                         ASSERT_FALSE( splitter.eos() );
 632                         ASSERT_FALSE( !splitter );
 633                         unsigned bits = std::rand() % 16;
 634                         size_t shift = splitter.rest_count();
 635                         if ( shift > bits )
 636                             shift = bits;
 637 #if CDS_BUILD_BITS == 64
 638                         res = ( res << shift ) | splitter.safe_cut( bits );
 639 #else
 640                         res = ( res << shift ) | static_cast<decltype(res)>( splitter.safe_cut( bits ));
 641 #endif
 642                     }
 643                     ASSERT_TRUE( splitter.eos() );
 644                     ASSERT_TRUE( !splitter );
 645                     EXPECT_EQ( res, src.to64() );
 646                     EXPECT_EQ( splitter.safe_cut( 8 ), 0u );
 647                     EXPECT_EQ( splitter.source()->to64(), src.to64() );
 648                     EXPECT_EQ( splitter.rest_count(), 0u );
 649                     EXPECT_EQ( splitter.bit_offset(), int48_size * 8 );
 650                 }
 651             }
 652         }
 653
 654         void cut_byte_le()
 655         {
 656             size_t src = sizeof( src ) == 8 ? 0xFEDCBA9876543210 : 0x76543210;
 657
 658             typedef cds::algo::byte_splitter< size_t > splitter_type;
 659             splitter_type splitter( src );
 660
 661             ASSERT_TRUE( !splitter.eos() );
 662             EXPECT_EQ( *splitter.source(), src );
 663             EXPECT_EQ( splitter.rest_count(), sizeof( src ) * 8 );
 664             EXPECT_EQ( splitter.bit_offset(), 0u );
 665             EXPECT_TRUE( splitter.is_correct( 8 ) );
 666             EXPECT_FALSE( splitter.is_correct( 4 ) );
 667
 668             unsigned expected = 0x10;
 669             for ( unsigned i = 0; i < splitter_type::c_bitstring_size; ++i ) {
 670                 auto part = splitter.cut( 8 );
 671                 EXPECT_EQ( part, expected );
 672                 expected += 0x22;
 673             }
 674
 675             ASSERT_TRUE( splitter.eos() );
 676             EXPECT_EQ( splitter.safe_cut( 8 ), 0u );
 677             EXPECT_EQ( *splitter.source(), src );
 678             EXPECT_EQ( splitter.rest_count(), 0u );
 679             EXPECT_EQ( splitter.bit_offset(), sizeof( src ) * 8 );
 680         }
 681
 682         void cut_byte_be()
 683         {
 684             size_t src = sizeof( src ) == 8 ? 0xFEDCBA9876543210 : 0x76543210;
 685
 686             typedef cds::algo::byte_splitter< size_t > splitter_type;
 687             splitter_type splitter( src );
 688
 689             ASSERT_TRUE( !splitter.eos() );
 690             EXPECT_EQ( *splitter.source(), src );
 691             EXPECT_EQ( splitter.rest_count(), sizeof( src ) * 8 );
 692             EXPECT_EQ( splitter.bit_offset(), 0u );
 693             EXPECT_TRUE( splitter.is_correct( 8 ) );
 694             EXPECT_FALSE( splitter.is_correct( 4 ) );
 695
 696             unsigned expected = 0xFE;
 697             for ( unsigned i = 0; i < splitter_type::c_bitstring_size; ++i ) {
 698                 auto part = splitter.cut( 8 );
 699                 EXPECT_EQ( part, expected );
 700                 expected -= 0x22;
 701             }
 702
 703             ASSERT_TRUE( splitter.eos() );
 704             EXPECT_EQ( splitter.safe_cut( 8 ), 0u );
 705             EXPECT_EQ( *splitter.source(), src );
 706             EXPECT_EQ( splitter.rest_count(), 0u );
 707             EXPECT_EQ( splitter.bit_offset(), sizeof( src ) * 8 );
 708         }
 709     };
 710
 711     class Split_number: public ::testing::Test
 712     {
 713     protected:
 714         template <typename Int>
 715         void split( Int const n )
 716         {
 717             cds::algo::number_splitter< Int > splitter( n );
 718
 719             // split by hex digit
 720             for ( unsigned count = 4; count < sizeof( Int ) * 8; count += 4 ) {
 721                 EXPECT_EQ( splitter.cut( 4 ), static_cast<Int>( count / 4 - 1 ));
 722             }
 723
 724             // random cut
 725             for ( int i = 0; i < 100; ++i ) {
 726                 splitter.reset();
 727                 EXPECT_EQ( splitter.source(), n );
 728                 EXPECT_EQ( splitter.bit_offset(), 0u );
 729                 EXPECT_EQ( splitter.rest_count(), sizeof( Int ) * 8 );
 730
 731                 unsigned total = 0;
 732                 Int result = 0;
 733
 734                 while ( total < sizeof( Int ) * 8 ) {
 735                     unsigned count = std::rand() % 16;
 736
 737                     unsigned shift = count;
 738                     if ( total + count > sizeof( Int ) * 8 )
 739                         shift = sizeof( Int ) * 8 - total;
 740
 741                     result += splitter.safe_cut( count ) << total;
 742                     total += shift;
 743                 }
 744
 745                 EXPECT_EQ( result, n );
 746
 747                 EXPECT_EQ( splitter.bit_offset(), sizeof( Int ) * 8 );
 748                 EXPECT_EQ( splitter.rest_count(), 0u );
 749             }
 750         }
 751     };
 752
 753
 754     TEST_F( Split_bitstrig, cut_uint )
 755     {
 756         if ( is_big_endian())
 757             cut_uint_be();
 758         else
 759             cut_uint_le();
 760     }
 761
 762     TEST_F( Split_bitstrig, cut_uint16 )
 763     {
 764         if ( is_big_endian())
 765             cut_small_be<uint16_t>();
 766         else
 767             cut_small_le<uint16_t>();
 768     }
 769
 770     TEST_F( Split_bitstrig, cut_int48 )
 771     {
 772         if ( is_big_endian() )
 773             cut_int48_be();
 774         else
 775             cut_int48_le();
 776     }
 777
 778     TEST_F( Split_bitstrig, cut_byte )
 779     {
 780         if ( is_big_endian() )
 781             cut_byte_be();
 782         else
 783             cut_byte_le();
 784     }
 785
 786     TEST_F( Split_number, split_int )
 787     {
 788         split( (int)0x76543210 );
 789     }
 790
 791     TEST_F( Split_number, split_uint )
 792     {
 793         split( (unsigned)0x76543210 );
 794     }
 795
 796     TEST_F( Split_number, split_short )
 797     {
 798         split( (short int)0x3210 );
 799     }
 800
 801     TEST_F( Split_number, split_ushort )
 802     {
 803         split( (unsigned short)0x3210 );
 804     }
 805
 806     TEST_F( Split_number, split_long )
 807     {
 808         if ( sizeof( long ) == 8 )
 809             split( (long)0xFEDCBA9876543210 );
 810         else
 811             split( (long)0x76543210 );
 812     }
 813
 814     TEST_F( Split_number, split_ulong )
 815     {
 816         if ( sizeof( long ) == 8 )
 817             split( (unsigned long)0xFEDCBA9876543210 );
 818         else
 819             split( (unsigned long)0x76543210 );
 820     }
 821
 822     TEST_F( Split_number, split_int64 )
 823     {
 824         split( (int64_t)0xFEDCBA9876543210 );
 825     }
 826
 827     TEST_F( Split_number, split_uint64 )
 828     {
 829         split( (uint64_t)0xFEDCBA9876543210 );
 830     }
 831
 832 } // namespace