• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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.  Candidate 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
__check_for_overflow(size_t N)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
__check_for_overflow(size_t N)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
__next_prime(size_t n)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