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
21namespace {
22
23// handle all next_prime(i) for i in [1, 210), special case 0
24const 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).
79const 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
152template <size_t _Sz = sizeof(size_t)>
153inline _LIBCPP_INLINE_VISIBILITY
154typename 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
165template <size_t _Sz = sizeof(size_t)>
166inline _LIBCPP_INLINE_VISIBILITY
167typename 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
178size_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        }
559next:
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