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