src/util/bitset.cpp

   1 /*
   2  * Copyright 2017 Jacob Lifshay
   3  *
   4  * Permission is hereby granted, free of charge, to any person obtaining a copy
   5  * of this software and associated documentation files (the "Software"), to deal
   6  * in the Software without restriction, including without limitation the rights
   7  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
   8  * copies of the Software, and to permit persons to whom the Software is
   9  * furnished to do so, subject to the following conditions:
  10  *
  11  * The above copyright notice and this permission notice shall be included in all
  12  * copies or substantial portions of the Software.
  13  *
  14  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  15  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  16  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  17  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  18  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  19  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  20  * SOFTWARE.
  21  *
  22  */
  23 // derived from
  24 // https://github.com/programmerjake/hashlife-voxels/blob/0dd91021a5b9caeffb7849b2114dca89204876bd/util/bitset.cpp
  25
  26 #include "bitset.h"
  27 #include <cassert>
  28 #include <cstdlib>
  29 #include <iostream>
  30 #include <random>
  31 #include <vector>
  32 #include <string>
  33 #include <utility>
  34
  35 namespace vulkan_cpu
  36 {
  37 namespace util
  38 {
  39 namespace detail
  40 {
  41 #if 0
  42 #warning testing bitset
  43 struct Bitset_nontemplate_base::Tester final
  44 {
  45     template <std::size_t Bit_count>
  46     static void check_unused_bits(const bitset<Bit_count> &value)
  47     {
  48         constexpr Word_type unused_bits =
  49             Bit_count % word_bit_count ? ~((1ULL << (Bit_count % word_bit_count)) - 1ULL) : 0;
  50         assert((value.get_word(value.word_count - 1) & unused_bits) == 0);
  51     }
  52     static void check_unused_bits(const bitset<0> &)
  53     {
  54     }
  55     template <std::size_t Bit_count>
  56     static void test_default_construct()
  57     {
  58         bitset<Bit_count> value;
  59         for(std::size_t i = 0; i < value.word_count; i++)
  60             assert(value.get_word(i) == 0);
  61         check_unused_bits(value);
  62     }
  63     template <std::size_t Bit_count>
  64     static void test_construct_from_ull()
  65     {
  66         for(std::size_t i = 0; i < std::numeric_limits<unsigned long long>::digits; i++)
  67         {
  68             bitset<Bit_count> value(1ULL << i);
  69             check_unused_bits(value);
  70             assert(bitset<Bit_count>(1ULL << i).to_ullong() == (1ULL << i) || i >= Bit_count);
  71         }
  72     }
  73     template <std::size_t Bit_count>
  74     static void test_reference_assign()
  75     {
  76         std::default_random_engine re;
  77         std::uniform_int_distribution<unsigned long long> distribution;
  78         for(std::size_t i = 0; i < 1000; i++)
  79         {
  80             bitset<Bit_count> src(distribution(re)), dest;
  81             for(std::size_t j = 0; j < Bit_count; j++)
  82             {
  83                 dest[j] = src[j];
  84                 check_unused_bits(src);
  85                 check_unused_bits(dest);
  86             }
  87             assert(src == dest);
  88         }
  89     }
  90     template <std::size_t Bit_count>
  91     static void test_reference_flip()
  92     {
  93         if(Bit_count == 0)
  94             return;
  95         std::default_random_engine re;
  96         std::vector<bool> vector;
  97         vector.resize(Bit_count, false);
  98         bitset<Bit_count> value;
  99         for(std::size_t i = 0; i < 1000; i++)
 100         {
 101             std::size_t index = std::uniform_int_distribution<std::size_t>(0, Bit_count - 1)(re);
 102             vector[index].flip();
 103             value[index].flip();
 104             check_unused_bits(value);
 105             for(std::size_t j = 0; j < Bit_count; j++)
 106                 assert(value[index] == static_cast<bool>(vector[index]));
 107         }
 108     }
 109     template <std::size_t Bit_count>
 110     static void test_test()
 111     {
 112         std::default_random_engine re;
 113         std::vector<bool> vector;
 114         vector.resize(Bit_count, false);
 115         bitset<Bit_count> value;
 116         if(Bit_count != 0)
 117         {
 118             for(std::size_t i = 0; i < 1000; i++)
 119             {
 120                 std::size_t index =
 121                     std::uniform_int_distribution<std::size_t>(0, Bit_count - 1)(re);
 122                 vector[index].flip();
 123                 value[index].flip();
 124                 check_unused_bits(value);
 125             }
 126         }
 127         for(std::size_t i = 0; i < Bit_count + 1000; i++)
 128         {
 129             bool threw = false;
 130             bool result = false;
 131             try
 132             {
 133                 result = value.test(i);
 134             }
 135             catch(std::out_of_range &)
 136             {
 137                 threw = true;
 138             }
 139             if(i >= Bit_count)
 140             {
 141                 assert(threw);
 142             }
 143             else
 144             {
 145                 assert(!threw);
 146                 assert(result == vector[i]);
 147             }
 148         }
 149     }
 150     template <std::size_t Bit_count>
 151     static void test_all_none_any_and_count_helper(const std::vector<bool> &vector,
 152                                                    const bitset<Bit_count> &value)
 153     {
 154         std::size_t set_bit_count = 0;
 155         for(std::size_t i = 0; i < Bit_count; i++)
 156             if(vector[i])
 157                 set_bit_count++;
 158         assert(value.all() == (set_bit_count == Bit_count));
 159         assert(value.any() == (set_bit_count != 0));
 160         assert(value.none() == (set_bit_count == 0));
 161         assert(value.count() == set_bit_count);
 162     }
 163     template <std::size_t Bit_count>
 164     static void test_all_none_any_and_count()
 165     {
 166         std::default_random_engine re;
 167         std::vector<bool> vector;
 168         vector.resize(Bit_count, false);
 169         bitset<Bit_count> value;
 170         test_all_none_any_and_count_helper(vector, value);
 171         if(Bit_count != 0)
 172         {
 173             for(std::size_t i = 0; i < 1000; i++)
 174             {
 175                 std::size_t index =
 176                     std::uniform_int_distribution<std::size_t>(0, Bit_count - 1)(re);
 177                 vector[index].flip();
 178                 value[index].flip();
 179                 check_unused_bits(value);
 180                 test_all_none_any_and_count_helper(vector, value);
 181             }
 182         }
 183         for(std::size_t i = 0; i < Bit_count; i++)
 184         {
 185             value[i] = true;
 186             vector[i] = true;
 187             check_unused_bits(value);
 188             test_all_none_any_and_count_helper(vector, value);
 189         }
 190     }
 191     template <std::size_t Bit_count>
 192     static void test_and_or_and_xor_helper(const std::vector<bool> &vector1,
 193                                            const std::vector<bool> &vector2,
 194                                            const bitset<Bit_count> &bitset1,
 195                                            const bitset<Bit_count> &bitset2)
 196     {
 197         bitset<Bit_count> dest_bitset_and = bitset1 & bitset2;
 198         bitset<Bit_count> dest_bitset_or = bitset1 | bitset2;
 199         bitset<Bit_count> dest_bitset_xor = bitset1 ^ bitset2;
 200         check_unused_bits(dest_bitset_and);
 201         check_unused_bits(dest_bitset_or);
 202         check_unused_bits(dest_bitset_xor);
 203         for(std::size_t i = 0; i < Bit_count; i++)
 204         {
 205             assert(dest_bitset_and[i] == (vector1[i] && vector2[i]));
 206             assert(dest_bitset_or[i] == (vector1[i] || vector2[i]));
 207             assert(dest_bitset_xor[i] == (static_cast<bool>(vector1[i]) != vector2[i]));
 208         }
 209     }
 210     template <std::size_t Bit_count>
 211     static void test_and_or_and_xor()
 212     {
 213         std::default_random_engine re;
 214         std::vector<bool> vector1, vector2;
 215         vector1.resize(Bit_count, false);
 216         vector2.resize(Bit_count, false);
 217         bitset<Bit_count> bitset1, bitset2;
 218         test_and_or_and_xor_helper(vector1, vector2, bitset1, bitset2);
 219         if(Bit_count != 0)
 220         {
 221             for(std::size_t i = 0; i < 2000; i++)
 222             {
 223                 std::size_t index =
 224                     std::uniform_int_distribution<std::size_t>(0, Bit_count * 2 - 1)(re);
 225                 bool is_second_bit_set = index >= Bit_count;
 226                 index %= Bit_count;
 227                 if(is_second_bit_set)
 228                 {
 229                     vector2[index].flip();
 230                     bitset2[index].flip();
 231                 }
 232                 else
 233                 {
 234                     vector1[index].flip();
 235                     bitset1[index].flip();
 236                 }
 237                 check_unused_bits(bitset1);
 238                 check_unused_bits(bitset2);
 239                 test_and_or_and_xor_helper(vector1, vector2, bitset1, bitset2);
 240             }
 241         }
 242         for(std::size_t i = 0; i < Bit_count; i++)
 243         {
 244             bitset1[i] = true;
 245             vector1[i] = true;
 246             check_unused_bits(bitset1);
 247             check_unused_bits(bitset2);
 248             test_and_or_and_xor_helper(vector1, vector2, bitset1, bitset2);
 249         }
 250         for(std::size_t i = 0; i < Bit_count; i++)
 251         {
 252             bitset2[i] = true;
 253             vector2[i] = true;
 254             check_unused_bits(bitset1);
 255             check_unused_bits(bitset2);
 256             test_and_or_and_xor_helper(vector1, vector2, bitset1, bitset2);
 257         }
 258     }
 259     template <std::size_t Bit_count>
 260     static void test_not()
 261     {
 262         std::default_random_engine re;
 263         std::vector<bool> vector;
 264         vector.resize(Bit_count, false);
 265         bitset<Bit_count> value;
 266         if(Bit_count != 0)
 267         {
 268             for(std::size_t i = 0; i < 1000; i++)
 269             {
 270                 std::size_t index =
 271                     std::uniform_int_distribution<std::size_t>(0, Bit_count - 1)(re);
 272                 vector[index].flip();
 273                 value[index].flip();
 274                 check_unused_bits(value);
 275                 bitset<Bit_count> bitset_not = ~value;
 276                 check_unused_bits(bitset_not);
 277                 for(std::size_t j = 0; j < Bit_count; j++)
 278                     assert(vector[j] == !bitset_not[j]);
 279             }
 280         }
 281     }
 282     template <std::size_t Bit_count>
 283     static void test_shift_helper(const std::vector<bool> &vector, const bitset<Bit_count> &value)
 284     {
 285         for(std::size_t shift_count = 0; shift_count < Bit_count * 2 + 1; shift_count++)
 286         {
 287             bitset<Bit_count> bitset_shifted_left = value << shift_count;
 288             bitset<Bit_count> bitset_shifted_right = value >> shift_count;
 289             check_unused_bits(bitset_shifted_left);
 290             check_unused_bits(bitset_shifted_right);
 291             for(std::size_t i = 0; i < Bit_count; i++)
 292             {
 293                 assert(bitset_shifted_left[i]
 294                        == (i < shift_count ? false : static_cast<bool>(vector[i - shift_count])));
 295                 assert(bitset_shifted_right[i] == (shift_count >= Bit_count - i ?
 296                                                        false :
 297                                                        static_cast<bool>(vector[i + shift_count])));
 298             }
 299         }
 300     }
 301     template <std::size_t Bit_count>
 302     static void test_shift()
 303     {
 304         std::default_random_engine re;
 305         std::vector<bool> vector;
 306         vector.resize(Bit_count, false);
 307         bitset<Bit_count> value;
 308         test_shift_helper(vector, value);
 309         if(Bit_count != 0)
 310         {
 311             for(std::size_t i = 0; i < 1000; i++)
 312             {
 313                 std::size_t index =
 314                     std::uniform_int_distribution<std::size_t>(0, Bit_count - 1)(re);
 315                 vector[index].flip();
 316                 value[index].flip();
 317                 check_unused_bits(value);
 318                 test_shift_helper(vector, value);
 319             }
 320         }
 321         for(std::size_t i = 0; i < Bit_count; i++)
 322         {
 323             value[i] = true;
 324             vector[i] = true;
 325             check_unused_bits(value);
 326             test_shift_helper(vector, value);
 327         }
 328     }
 329     template <std::size_t Bit_count>
 330     static void test_global_set_and_reset()
 331     {
 332         bitset<Bit_count> value;
 333         value.reset();
 334         check_unused_bits(value);
 335         assert(value.none());
 336         value.set();
 337         check_unused_bits(value);
 338         assert(value.all());
 339     }
 340     template <std::size_t Bit_count>
 341     static void test_find_helper(const std::string &string, const bitset<Bit_count> &value)
 342     {
 343         for(std::size_t i = 0; i < Bit_count; i++)
 344             assert(string[i] == (value[i] ? '1' : '0'));
 345         for(std::size_t start = 0; start <= Bit_count; start++)
 346         {
 347             assert(string.find_first_of('1', start) == value.find_first(true, start));
 348             assert(string.find_first_not_of('1', start) == value.find_first(false, start));
 349             assert(string.find_last_of('1', start) == value.find_last(true, start));
 350             assert(string.find_last_not_of('1', start) == value.find_last(false, start));
 351         }
 352     }
 353     template <std::size_t Bit_count>
 354     static void test_find()
 355     {
 356         std::default_random_engine re;
 357         std::string string;
 358         string.resize(Bit_count, '0');
 359         bitset<Bit_count> value;
 360         test_find_helper(string, value);
 361         if(Bit_count != 0)
 362         {
 363             for(std::size_t i = 0; i < 1000; i++)
 364             {
 365                 std::size_t index =
 366                     std::uniform_int_distribution<std::size_t>(0, Bit_count - 1)(re);
 367                 string[index] = (string[index] == '0' ? '1' : '0');
 368                 value[index].flip();
 369                 check_unused_bits(value);
 370                 test_find_helper(string, value);
 371             }
 372         }
 373         for(std::size_t i = 0; i < Bit_count; i++)
 374         {
 375             value[i] = true;
 376             string[i] = '1';
 377             check_unused_bits(value);
 378             test_find_helper(string, value);
 379         }
 380         if(Bit_count != 0)
 381         {
 382             for(std::size_t i = 0; i < 1000; i++)
 383             {
 384                 std::size_t index =
 385                     std::uniform_int_distribution<std::size_t>(0, Bit_count - 1)(re);
 386                 string[index] = (string[index] == '0' ? '1' : '0');
 387                 value[index].flip();
 388                 check_unused_bits(value);
 389                 test_find_helper(string, value);
 390             }
 391         }
 392     }
 393     template <std::size_t Bit_count>
 394     static char test()
 395     {
 396         std::cout << "testing bitset<" << Bit_count << ">" << std::endl;
 397         test_default_construct<Bit_count>();
 398         test_construct_from_ull<Bit_count>();
 399         test_reference_assign<Bit_count>();
 400         test_reference_flip<Bit_count>();
 401         test_test<Bit_count>();
 402         test_all_none_any_and_count<Bit_count>();
 403         test_and_or_and_xor<Bit_count>();
 404         test_not<Bit_count>();
 405         test_shift<Bit_count>();
 406         test_global_set_and_reset<Bit_count>();
 407         test_find<Bit_count>();
 408         return 0;
 409     }
 410     template <typename... Args>
 411     static void test_helper(Args...)
 412     {
 413     }
 414     template <std::size_t... Bit_counts>
 415     static void test(std::index_sequence<Bit_counts...>)
 416     {
 417         test_helper(test<Bit_counts>()...);
 418     }
 419     struct Test_runner final
 420     {
 421         Test_runner()
 422         {
 423             test(std::make_index_sequence<128>());
 424             std::exit(0);
 425         }
 426     };
 427     static Test_runner test_runner;
 428 };
 429 Bitset_nontemplate_base::Tester::Test_runner Bitset_nontemplate_base::Tester::test_runner;
 430 #endif
 431 }
 432 }
 433 }