Home | History | Annotate | Download | only in src
      1 //===-------------------------- hash.cpp ----------------------------------===//
      2 //
      3 //                     The LLVM Compiler Infrastructure
      4 //
      5 // This file is dual licensed under the MIT and the University of Illinois Open
      6 // Source Licenses. See LICENSE.TXT for details.
      7 //
      8 //===----------------------------------------------------------------------===//
      9 
     10 #include "__hash_table"
     11 #include "algorithm"
     12 #include "stdexcept"
     13 #include "type_traits"
     14 
     15 #ifdef __clang__
     16 #pragma clang diagnostic ignored "-Wtautological-constant-out-of-range-compare"
     17 #endif
     18 
     19 _LIBCPP_BEGIN_NAMESPACE_STD
     20 
     21 namespace {
     22 
     23 // handle all next_prime(i) for i in [1, 210), special case 0
     24 const unsigned small_primes[] =
     25 {
     26     0,
     27     2,
     28     3,
     29     5,
     30     7,
     31     11,
     32     13,
     33     17,
     34     19,
     35     23,
     36     29,
     37     31,
     38     37,
     39     41,
     40     43,
     41     47,
     42     53,
     43     59,
     44     61,
     45     67,
     46     71,
     47     73,
     48     79,
     49     83,
     50     89,
     51     97,
     52     101,
     53     103,
     54     107,
     55     109,
     56     113,
     57     127,
     58     131,
     59     137,
     60     139,
     61     149,
     62     151,
     63     157,
     64     163,
     65     167,
     66     173,
     67     179,
     68     181,
     69     191,
     70     193,
     71     197,
     72     199,
     73     211
     74 };
     75 
     76 // potential primes = 210*k + indices[i], k >= 1
     77 //   these numbers are not divisible by 2, 3, 5 or 7
     78 //   (or any integer 2 <= j <= 10 for that matter).
     79 const unsigned indices[] =
     80 {
     81     1,
     82     11,
     83     13,
     84     17,
     85     19,
     86     23,
     87     29,
     88     31,
     89     37,
     90     41,
     91     43,
     92     47,
     93     53,
     94     59,
     95     61,
     96     67,
     97     71,
     98     73,
     99     79,
    100     83,
    101     89,
    102     97,
    103     101,
    104     103,
    105     107,
    106     109,
    107     113,
    108     121,
    109     127,
    110     131,
    111     137,
    112     139,
    113     143,
    114     149,
    115     151,
    116     157,
    117     163,
    118     167,
    119     169,
    120     173,
    121     179,
    122     181,
    123     187,
    124     191,
    125     193,
    126     197,
    127     199,
    128     209
    129 };
    130 
    131 }
    132 
    133 // Returns:  If n == 0, returns 0.  Else returns the lowest prime number that
    134 // is greater than or equal to n.
    135 //
    136 // The algorithm creates a list of small primes, plus an open-ended list of
    137 // potential primes.  All prime numbers are potential prime numbers.  However
    138 // some potential prime numbers are not prime.  In an ideal world, all potential
    139 // prime numbers would be prime.  Candiate prime numbers are chosen as the next
    140 // highest potential prime.  Then this number is tested for prime by dividing it
    141 // by all potential prime numbers less than the sqrt of the candidate.
    142 //
    143 // This implementation defines potential primes as those numbers not divisible
    144 // by 2, 3, 5, and 7.  Other (common) implementations define potential primes
    145 // as those not divisible by 2.  A few other implementations define potential
    146 // primes as those not divisible by 2 or 3.  By raising the number of small
    147 // primes which the potential prime is not divisible by, the set of potential
    148 // primes more closely approximates the set of prime numbers.  And thus there
    149 // are fewer potential primes to search, and fewer potential primes to divide
    150 // against.
    151 
    152 template <size_t _Sz = sizeof(size_t)>
    153 inline _LIBCPP_INLINE_VISIBILITY
    154 typename enable_if<_Sz == 4, void>::type
    155 __check_for_overflow(size_t N)
    156 {
    157 #ifndef _LIBCPP_NO_EXCEPTIONS
    158     if (N > 0xFFFFFFFB)
    159         throw overflow_error("__next_prime overflow");
    160 #else
    161     (void)N;
    162 #endif
    163 }
    164 
    165 template <size_t _Sz = sizeof(size_t)>
    166 inline _LIBCPP_INLINE_VISIBILITY
    167 typename enable_if<_Sz == 8, void>::type
    168 __check_for_overflow(size_t N)
    169 {
    170 #ifndef _LIBCPP_NO_EXCEPTIONS
    171     if (N > 0xFFFFFFFFFFFFFFC5ull)
    172         throw overflow_error("__next_prime overflow");
    173 #else
    174     (void)N;
    175 #endif
    176 }
    177 
    178 size_t
    179 __next_prime(size_t n)
    180 {
    181     const size_t L = 210;
    182     const size_t N = sizeof(small_primes) / sizeof(small_primes[0]);
    183     // If n is small enough, search in small_primes
    184     if (n <= small_primes[N-1])
    185         return *std::lower_bound(small_primes, small_primes + N, n);
    186     // Else n > largest small_primes
    187     // Check for overflow
    188     __check_for_overflow(n);
    189     // Start searching list of potential primes: L * k0 + indices[in]
    190     const size_t M = sizeof(indices) / sizeof(indices[0]);
    191     // Select first potential prime >= n
    192     //   Known a-priori n >= L
    193     size_t k0 = n / L;
    194     size_t in = static_cast<size_t>(std::lower_bound(indices, indices + M, n - k0 * L)
    195                                     - indices);
    196     n = L * k0 + indices[in];
    197     while (true)
    198     {
    199         // Divide n by all primes or potential primes (i) until:
    200         //    1.  The division is even, so try next potential prime.
    201         //    2.  The i > sqrt(n), in which case n is prime.
    202         // It is known a-priori that n is not divisible by 2, 3, 5 or 7,
    203         //    so don't test those (j == 5 ->  divide by 11 first).  And the
    204         //    potential primes start with 211, so don't test against the last
    205         //    small prime.
    206         for (size_t j = 5; j < N - 1; ++j)
    207         {
    208             const std::size_t p = small_primes[j];
    209             const std::size_t q = n / p;
    210             if (q < p)
    211                 return n;
    212             if (n == q * p)
    213                 goto next;
    214         }
    215         // n wasn't divisible by small primes, try potential primes
    216         {
    217             size_t i = 211;
    218             while (true)
    219             {
    220                 std::size_t q = n / i;
    221                 if (q < i)
    222                     return n;
    223                 if (n == q * i)
    224                     break;
    225 
    226                 i += 10;
    227                 q = n / i;
    228                 if (q < i)
    229                     return n;
    230                 if (n == q * i)
    231                     break;
    232 
    233                 i += 2;
    234                 q = n / i;
    235                 if (q < i)
    236                     return n;
    237                 if (n == q * i)
    238                     break;
    239 
    240                 i += 4;
    241                 q = n / i;
    242                 if (q < i)
    243                     return n;
    244                 if (n == q * i)
    245                     break;
    246 
    247                 i += 2;
    248                 q = n / i;
    249                 if (q < i)
    250                     return n;
    251                 if (n == q * i)
    252                     break;
    253 
    254                 i += 4;
    255                 q = n / i;
    256                 if (q < i)
    257                     return n;
    258                 if (n == q * i)
    259                     break;
    260 
    261                 i += 6;
    262                 q = n / i;
    263                 if (q < i)
    264                     return n;
    265                 if (n == q * i)
    266                     break;
    267 
    268                 i += 2;
    269                 q = n / i;
    270                 if (q < i)
    271                     return n;
    272                 if (n == q * i)
    273                     break;
    274 
    275                 i += 6;
    276                 q = n / i;
    277                 if (q < i)
    278                     return n;
    279                 if (n == q * i)
    280                     break;
    281 
    282                 i += 4;
    283                 q = n / i;
    284                 if (q < i)
    285                     return n;
    286                 if (n == q * i)
    287                     break;
    288 
    289                 i += 2;
    290                 q = n / i;
    291                 if (q < i)
    292                     return n;
    293                 if (n == q * i)
    294                     break;
    295 
    296                 i += 4;
    297                 q = n / i;
    298                 if (q < i)
    299                     return n;
    300                 if (n == q * i)
    301                     break;
    302 
    303                 i += 6;
    304                 q = n / i;
    305                 if (q < i)
    306                     return n;
    307                 if (n == q * i)
    308                     break;
    309 
    310                 i += 6;
    311                 q = n / i;
    312                 if (q < i)
    313                     return n;
    314                 if (n == q * i)
    315                     break;
    316 
    317                 i += 2;
    318                 q = n / i;
    319                 if (q < i)
    320                     return n;
    321                 if (n == q * i)
    322                     break;
    323 
    324                 i += 6;
    325                 q = n / i;
    326                 if (q < i)
    327                     return n;
    328                 if (n == q * i)
    329                     break;
    330 
    331                 i += 4;
    332                 q = n / i;
    333                 if (q < i)
    334                     return n;
    335                 if (n == q * i)
    336                     break;
    337 
    338                 i += 2;
    339                 q = n / i;
    340                 if (q < i)
    341                     return n;
    342                 if (n == q * i)
    343                     break;
    344 
    345                 i += 6;
    346                 q = n / i;
    347                 if (q < i)
    348                     return n;
    349                 if (n == q * i)
    350                     break;
    351 
    352                 i += 4;
    353                 q = n / i;
    354                 if (q < i)
    355                     return n;
    356                 if (n == q * i)
    357                     break;
    358 
    359                 i += 6;
    360                 q = n / i;
    361                 if (q < i)
    362                     return n;
    363                 if (n == q * i)
    364                     break;
    365 
    366                 i += 8;
    367                 q = n / i;
    368                 if (q < i)
    369                     return n;
    370                 if (n == q * i)
    371                     break;
    372 
    373                 i += 4;
    374                 q = n / i;
    375                 if (q < i)
    376                     return n;
    377                 if (n == q * i)
    378                     break;
    379 
    380                 i += 2;
    381                 q = n / i;
    382                 if (q < i)
    383                     return n;
    384                 if (n == q * i)
    385                     break;
    386 
    387                 i += 4;
    388                 q = n / i;
    389                 if (q < i)
    390                     return n;
    391                 if (n == q * i)
    392                     break;
    393 
    394                 i += 2;
    395                 q = n / i;
    396                 if (q < i)
    397                     return n;
    398                 if (n == q * i)
    399                     break;
    400 
    401                 i += 4;
    402                 q = n / i;
    403                 if (q < i)
    404                     return n;
    405                 if (n == q * i)
    406                     break;
    407 
    408                 i += 8;
    409                 q = n / i;
    410                 if (q < i)
    411                     return n;
    412                 if (n == q * i)
    413                     break;
    414 
    415                 i += 6;
    416                 q = n / i;
    417                 if (q < i)
    418                     return n;
    419                 if (n == q * i)
    420                     break;
    421 
    422                 i += 4;
    423                 q = n / i;
    424                 if (q < i)
    425                     return n;
    426                 if (n == q * i)
    427                     break;
    428 
    429                 i += 6;
    430                 q = n / i;
    431                 if (q < i)
    432                     return n;
    433                 if (n == q * i)
    434                     break;
    435 
    436                 i += 2;
    437                 q = n / i;
    438                 if (q < i)
    439                     return n;
    440                 if (n == q * i)
    441                     break;
    442 
    443                 i += 4;
    444                 q = n / i;
    445                 if (q < i)
    446                     return n;
    447                 if (n == q * i)
    448                     break;
    449 
    450                 i += 6;
    451                 q = n / i;
    452                 if (q < i)
    453                     return n;
    454                 if (n == q * i)
    455                     break;
    456 
    457                 i += 2;
    458                 q = n / i;
    459                 if (q < i)
    460                     return n;
    461                 if (n == q * i)
    462                     break;
    463 
    464                 i += 6;
    465                 q = n / i;
    466                 if (q < i)
    467                     return n;
    468                 if (n == q * i)
    469                     break;
    470 
    471                 i += 6;
    472                 q = n / i;
    473                 if (q < i)
    474                     return n;
    475                 if (n == q * i)
    476                     break;
    477 
    478                 i += 4;
    479                 q = n / i;
    480                 if (q < i)
    481                     return n;
    482                 if (n == q * i)
    483                     break;
    484 
    485                 i += 2;
    486                 q = n / i;
    487                 if (q < i)
    488                     return n;
    489                 if (n == q * i)
    490                     break;
    491 
    492                 i += 4;
    493                 q = n / i;
    494                 if (q < i)
    495                     return n;
    496                 if (n == q * i)
    497                     break;
    498 
    499                 i += 6;
    500                 q = n / i;
    501                 if (q < i)
    502                     return n;
    503                 if (n == q * i)
    504                     break;
    505 
    506                 i += 2;
    507                 q = n / i;
    508                 if (q < i)
    509                     return n;
    510                 if (n == q * i)
    511                     break;
    512 
    513                 i += 6;
    514                 q = n / i;
    515                 if (q < i)
    516                     return n;
    517                 if (n == q * i)
    518                     break;
    519 
    520                 i += 4;
    521                 q = n / i;
    522                 if (q < i)
    523                     return n;
    524                 if (n == q * i)
    525                     break;
    526 
    527                 i += 2;
    528                 q = n / i;
    529                 if (q < i)
    530                     return n;
    531                 if (n == q * i)
    532                     break;
    533 
    534                 i += 4;
    535                 q = n / i;
    536                 if (q < i)
    537                     return n;
    538                 if (n == q * i)
    539                     break;
    540 
    541                 i += 2;
    542                 q = n / i;
    543                 if (q < i)
    544                     return n;
    545                 if (n == q * i)
    546                     break;
    547 
    548                 i += 10;
    549                 q = n / i;
    550                 if (q < i)
    551                     return n;
    552                 if (n == q * i)
    553                     break;
    554 
    555                 // This will loop i to the next "plane" of potential primes
    556                 i += 2;
    557             }
    558         }
    559 next:
    560         // n is not prime.  Increment n to next potential prime.
    561         if (++in == M)
    562         {
    563             ++k0;
    564             in = 0;
    565         }
    566         n = L * k0 + indices[in];
    567     }
    568 }
    569 
    570 _LIBCPP_END_NAMESPACE_STD
    571