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
20 namespace {
21
22 // handle all next_prime(i) for i in [1, 210), special case 0
23 const 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).
78 const 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
151 template <size_t _Sz = sizeof(size_t)>
152 inline _LIBCPP_INLINE_VISIBILITY
153 typename enable_if<_Sz == 4, void>::type
__check_for_overflow(size_t N)154 __check_for_overflow(size_t N)
155 {
156 if (N > 0xFFFFFFFB)
157 __throw_overflow_error("__next_prime overflow");
158 }
159
160 template <size_t _Sz = sizeof(size_t)>
161 inline _LIBCPP_INLINE_VISIBILITY
162 typename enable_if<_Sz == 8, void>::type
__check_for_overflow(size_t N)163 __check_for_overflow(size_t N)
164 {
165 if (N > 0xFFFFFFFFFFFFFFC5ull)
166 __throw_overflow_error("__next_prime overflow");
167 }
168
169 size_t
__next_prime(size_t n)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 }
550 next:
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