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