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