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-2016
   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     class Split_bitstrig : public ::testing::Test
  36     {
  37     protected:
  38         bool is_big_endian()
  39         {
  40             union {
  41                 uint32_t ui;
  42                 uint8_t  ch;
  43             } byte_order;
  44             byte_order.ui = 0xFF000001;
  45
  46             return byte_order.ch != 0x01;
  47         }
  48
  49         void cut_uint_le()
  50         {
  51             typedef cds::algo::split_bitstring< 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), 0 );
  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), 0 );
  75             ASSERT_TRUE( splitter.eos() );
  76             ASSERT_TRUE( !splitter );
  77
  78             // Cut each hex digit
  79             splitter.reset();
  80             for ( size_t i = 0; i < sizeof(size_t) * 2; ++i ) {
  81                 ASSERT_FALSE( splitter.eos() );
  82                 ASSERT_FALSE( !splitter );
  83                 ASSERT_EQ( splitter.cut( 4 ), i );
  84             }
  85             ASSERT_TRUE( splitter.eos() );
  86             ASSERT_FALSE( splitter );
  87
  88             // by one bit
  89             {
  90                 splitter.reset();
  91                 res = 0;
  92                 for ( size_t i = 0; i < sizeof(size_t) * 8; ++i ) {
  93                     ASSERT_FALSE( splitter.eos() );
  94                     ASSERT_FALSE( !splitter );
  95                     res = res + (splitter.cut( 1 ) << i);
  96                 }
  97                 ASSERT_TRUE( splitter.eos() );
  98                 ASSERT_TRUE( !splitter );
  99                 EXPECT_EQ( res, src );
 100             }
 101
 102             // random cut
 103             {
 104                 for ( size_t k = 0; k < 100; ++k ) {
 105                     splitter.reset();
 106                     res = 0;
 107                     size_t shift = 0;
 108                     while ( splitter ) {
 109                         ASSERT_FALSE( splitter.eos() );
 110                         ASSERT_FALSE( !splitter );
 111                         int bits = std::rand() % 16;
 112                         res = res + ( splitter.safe_cut( bits ) << shift );
 113                         shift += bits;
 114                     }
 115                     ASSERT_TRUE( splitter.eos() );
 116                     ASSERT_TRUE( !splitter );
 117                     EXPECT_EQ( res, src );
 118                 }
 119             }
 120         }
 121
 122         void cut_uint_be()
 123         {
 124             typedef cds::algo::split_bitstring< size_t > split_bitstring;
 125
 126             size_t src = sizeof(src) == 8 ? 0xFEDCBA9876543210 : 0x76543210;
 127             split_bitstring splitter(src);
 128             size_t res;
 129
 130             // Trivial case
 131             ASSERT_FALSE( splitter.eos() );
 132             ASSERT_FALSE( !splitter );
 133             res = splitter.cut(sizeof(src) * 8);
 134             ASSERT_EQ( res, src );
 135             ASSERT_TRUE( splitter.eos() );
 136             ASSERT_TRUE( !splitter );
 137             EXPECT_EQ(splitter.safe_cut(sizeof(src) * 8), 0 );
 138             ASSERT_TRUE( splitter.eos() );
 139             ASSERT_TRUE( !splitter );
 140             splitter.reset();
 141             ASSERT_FALSE( splitter.eos() );
 142             ASSERT_FALSE( !splitter );
 143             res = splitter.cut(sizeof(src) * 8);
 144             EXPECT_EQ( res, src );
 145             ASSERT_TRUE( splitter.eos() );
 146             ASSERT_TRUE( !splitter );
 147             EXPECT_EQ(splitter.safe_cut(sizeof(src) * 8), 0 );
 148             ASSERT_TRUE( splitter.eos() );
 149             ASSERT_TRUE( !splitter );
 150
 151             // Cut each hex digit
 152             splitter.reset();
 153             for ( size_t i = 0; i < sizeof(size_t) * 2; ++i ) {
 154                 ASSERT_FALSE( splitter.eos() );
 155                 ASSERT_FALSE( !splitter );
 156                 EXPECT_EQ( splitter.cut( 4 ), 0x0F - i );
 157             }
 158             ASSERT_TRUE( splitter.eos() );
 159             ASSERT_TRUE( !splitter );
 160
 161             // by one bit
 162             {
 163                 splitter.reset();
 164                 res = 0;
 165                 for ( size_t i = 0; i < sizeof(size_t) * 8; ++i ) {
 166                     ASSERT_FALSE( splitter.eos() );
 167                     ASSERT_FALSE( !splitter );
 168                     res = (res << 1) + splitter.cut( 1 );
 169                 }
 170                 ASSERT_TRUE( splitter.eos() );
 171                 ASSERT_TRUE( !splitter );
 172                 EXPECT_EQ( res, src );
 173             }
 174
 175             // random cut
 176             {
 177                 for ( size_t k = 0; k < 100; ++k ) {
 178                     splitter.reset();
 179                     res = 0;
 180                     while ( splitter ) {
 181                         ASSERT_FALSE( splitter.eos() );
 182                         ASSERT_FALSE( !splitter );
 183                         int bits = std::rand() % 16;
 184                         res = (res << bits) + splitter.safe_cut( bits );
 185                     }
 186                     ASSERT_TRUE( splitter.eos() );
 187                     ASSERT_TRUE( !splitter );
 188                     EXPECT_EQ( res, src );
 189                 }
 190             }
 191         }
 192
 193         template <typename PartUInt>
 194         void cut_small_le()
 195         {
 196             typedef PartUInt part_uint;
 197
 198             typedef cds::algo::split_bitstring< uint64_t, part_uint > split_bitstring;
 199
 200             uint64_t src = 0xFEDCBA9876543210;
 201             split_bitstring splitter(src);
 202             uint64_t res;
 203
 204             // Cut each hex digit
 205             splitter.reset();
 206             for ( size_t i = 0; i < sizeof(size_t) * 2; ++i ) {
 207                 ASSERT_FALSE( splitter.eos() );
 208                 ASSERT_FALSE( !splitter );
 209                 EXPECT_EQ( static_cast<size_t>(splitter.cut( 4 )), i );
 210             }
 211             ASSERT_TRUE( splitter.eos() );
 212             ASSERT_TRUE( !splitter );
 213
 214             // by one bit
 215             {
 216                 splitter.reset();
 217                 res = 0;
 218                 for ( size_t i = 0; i < sizeof(size_t) * 8; ++i ) {
 219                     ASSERT_FALSE( splitter.eos() );
 220                     ASSERT_FALSE( !splitter );
 221                     res = res + ( static_cast<uint64_t>(splitter.cut( 1 )) << i);
 222                 }
 223                 ASSERT_TRUE( splitter.eos() );
 224                 ASSERT_TRUE( !splitter );
 225                 EXPECT_EQ( res, src );
 226             }
 227
 228             // random cut
 229             {
 230                 for ( size_t k = 0; k < 100; ++k ) {
 231                     splitter.reset();
 232                     res = 0;
 233                     size_t shift = 0;
 234                     while ( splitter ) {
 235                         ASSERT_FALSE( splitter.eos() );
 236                         ASSERT_FALSE( !splitter );
 237                         int bits = std::rand() % 16;
 238                         res = res + ( static_cast<uint64_t>(splitter.safe_cut( bits )) << shift );
 239                         shift += bits;
 240                     }
 241                     ASSERT_TRUE( splitter.eos() );
 242                     ASSERT_TRUE( !splitter );
 243                     EXPECT_EQ( res, src );
 244                 }
 245             }
 246         }
 247
 248         template <typename PartUInt>
 249         void cut_small_be()
 250         {
 251             typedef PartUInt part_uint;
 252
 253             typedef cds::algo::split_bitstring< uint64_t, part_uint > split_bitstring;
 254
 255             uint64_t src = 0xFEDCBA9876543210;
 256             split_bitstring splitter(src);
 257             uint64_t res;
 258
 259             // Cut each hex digit
 260             splitter.reset();
 261             for ( size_t i = 0; i < sizeof(size_t) * 2; ++i ) {
 262                 ASSERT_FALSE( splitter.eos() );
 263                 ASSERT_FALSE( !splitter );
 264                 EXPECT_EQ( splitter.cut( 4 ), 0x0F - i );
 265             }
 266             ASSERT_TRUE( splitter.eos() );
 267             ASSERT_TRUE( !splitter );
 268
 269             // by one bit
 270             {
 271                 splitter.reset();
 272                 res = 0;
 273                 for ( size_t i = 0; i < sizeof(size_t) * 8; ++i ) {
 274                     ASSERT_FALSE( splitter.eos() );
 275                     ASSERT_FALSE( !splitter );
 276                     res = (res << 1) + splitter.cut( 1 );
 277                 }
 278                 ASSERT_TRUE( splitter.eos() );
 279                 ASSERT_TRUE( !splitter );
 280                 EXPECT_EQ( res, src );
 281             }
 282
 283             // random cut
 284             {
 285                 for ( size_t k = 0; k < 100; ++k ) {
 286                     splitter.reset();
 287                     res = 0;
 288                     while ( splitter ) {
 289                         ASSERT_FALSE( splitter.eos() );
 290                         ASSERT_FALSE( !splitter );
 291                         int bits = std::rand() % 16;
 292                         res = (res << bits) + splitter.safe_cut( bits );
 293                     }
 294                     ASSERT_TRUE( splitter.eos() );
 295                     ASSERT_TRUE( !splitter );
 296                     EXPECT_EQ( res, src );
 297                 }
 298             }
 299         }
 300     };
 301
 302     TEST_F( Split_bitstrig, cut_uint )
 303     {
 304         if ( is_big_endian() )
 305             cut_uint_be();
 306         else
 307             cut_uint_le();
 308     }
 309
 310     TEST_F( Split_bitstrig, cut_uint16 )
 311     {
 312         if ( is_big_endian() )
 313             cut_small_be<uint16_t>();
 314         else
 315             cut_small_le<uint16_t>();
 316     }
 317
 318 } // namespace