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 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 163 __check_for_overflow(size_t N) 164 { 165 if (N > 0xFFFFFFFFFFFFFFC5ull) 166 __throw_overflow_error("__next_prime overflow"); 167 } 168 169 size_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 } 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