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 #ifndef _LIBCPP_NO_EXCEPTIONS 157 if (N > 0xFFFFFFFB) 158 throw overflow_error("__next_prime overflow"); 159 #else 160 (void)N; 161 #endif 162 } 163 164 template <size_t _Sz = sizeof(size_t)> 165 inline _LIBCPP_INLINE_VISIBILITY 166 typename enable_if<_Sz == 8, void>::type 167 __check_for_overflow(size_t N) 168 { 169 #ifndef _LIBCPP_NO_EXCEPTIONS 170 if (N > 0xFFFFFFFFFFFFFFC5ull) 171 throw overflow_error("__next_prime overflow"); 172 #else 173 (void)N; 174 #endif 175 } 176 177 size_t 178 __next_prime(size_t n) 179 { 180 const size_t L = 210; 181 const size_t N = sizeof(small_primes) / sizeof(small_primes[0]); 182 // If n is small enough, search in small_primes 183 if (n <= small_primes[N-1]) 184 return *std::lower_bound(small_primes, small_primes + N, n); 185 // Else n > largest small_primes 186 // Check for overflow 187 __check_for_overflow(n); 188 // Start searching list of potential primes: L * k0 + indices[in] 189 const size_t M = sizeof(indices) / sizeof(indices[0]); 190 // Select first potential prime >= n 191 // Known a-priori n >= L 192 size_t k0 = n / L; 193 size_t in = static_cast<size_t>(std::lower_bound(indices, indices + M, n - k0 * L) 194 - indices); 195 n = L * k0 + indices[in]; 196 while (true) 197 { 198 // Divide n by all primes or potential primes (i) until: 199 // 1. The division is even, so try next potential prime. 200 // 2. The i > sqrt(n), in which case n is prime. 201 // It is known a-priori that n is not divisible by 2, 3, 5 or 7, 202 // so don't test those (j == 5 -> divide by 11 first). And the 203 // potential primes start with 211, so don't test against the last 204 // small prime. 205 for (size_t j = 5; j < N - 1; ++j) 206 { 207 const std::size_t p = small_primes[j]; 208 const std::size_t q = n / p; 209 if (q < p) 210 return n; 211 if (n == q * p) 212 goto next; 213 } 214 // n wasn't divisible by small primes, try potential primes 215 { 216 size_t i = 211; 217 while (true) 218 { 219 std::size_t q = n / i; 220 if (q < i) 221 return n; 222 if (n == q * i) 223 break; 224 225 i += 10; 226 q = n / i; 227 if (q < i) 228 return n; 229 if (n == q * i) 230 break; 231 232 i += 2; 233 q = n / i; 234 if (q < i) 235 return n; 236 if (n == q * i) 237 break; 238 239 i += 4; 240 q = n / i; 241 if (q < i) 242 return n; 243 if (n == q * i) 244 break; 245 246 i += 2; 247 q = n / i; 248 if (q < i) 249 return n; 250 if (n == q * i) 251 break; 252 253 i += 4; 254 q = n / i; 255 if (q < i) 256 return n; 257 if (n == q * i) 258 break; 259 260 i += 6; 261 q = n / i; 262 if (q < i) 263 return n; 264 if (n == q * i) 265 break; 266 267 i += 2; 268 q = n / i; 269 if (q < i) 270 return n; 271 if (n == q * i) 272 break; 273 274 i += 6; 275 q = n / i; 276 if (q < i) 277 return n; 278 if (n == q * i) 279 break; 280 281 i += 4; 282 q = n / i; 283 if (q < i) 284 return n; 285 if (n == q * i) 286 break; 287 288 i += 2; 289 q = n / i; 290 if (q < i) 291 return n; 292 if (n == q * i) 293 break; 294 295 i += 4; 296 q = n / i; 297 if (q < i) 298 return n; 299 if (n == q * i) 300 break; 301 302 i += 6; 303 q = n / i; 304 if (q < i) 305 return n; 306 if (n == q * i) 307 break; 308 309 i += 6; 310 q = n / i; 311 if (q < i) 312 return n; 313 if (n == q * i) 314 break; 315 316 i += 2; 317 q = n / i; 318 if (q < i) 319 return n; 320 if (n == q * i) 321 break; 322 323 i += 6; 324 q = n / i; 325 if (q < i) 326 return n; 327 if (n == q * i) 328 break; 329 330 i += 4; 331 q = n / i; 332 if (q < i) 333 return n; 334 if (n == q * i) 335 break; 336 337 i += 2; 338 q = n / i; 339 if (q < i) 340 return n; 341 if (n == q * i) 342 break; 343 344 i += 6; 345 q = n / i; 346 if (q < i) 347 return n; 348 if (n == q * i) 349 break; 350 351 i += 4; 352 q = n / i; 353 if (q < i) 354 return n; 355 if (n == q * i) 356 break; 357 358 i += 6; 359 q = n / i; 360 if (q < i) 361 return n; 362 if (n == q * i) 363 break; 364 365 i += 8; 366 q = n / i; 367 if (q < i) 368 return n; 369 if (n == q * i) 370 break; 371 372 i += 4; 373 q = n / i; 374 if (q < i) 375 return n; 376 if (n == q * i) 377 break; 378 379 i += 2; 380 q = n / i; 381 if (q < i) 382 return n; 383 if (n == q * i) 384 break; 385 386 i += 4; 387 q = n / i; 388 if (q < i) 389 return n; 390 if (n == q * i) 391 break; 392 393 i += 2; 394 q = n / i; 395 if (q < i) 396 return n; 397 if (n == q * i) 398 break; 399 400 i += 4; 401 q = n / i; 402 if (q < i) 403 return n; 404 if (n == q * i) 405 break; 406 407 i += 8; 408 q = n / i; 409 if (q < i) 410 return n; 411 if (n == q * i) 412 break; 413 414 i += 6; 415 q = n / i; 416 if (q < i) 417 return n; 418 if (n == q * i) 419 break; 420 421 i += 4; 422 q = n / i; 423 if (q < i) 424 return n; 425 if (n == q * i) 426 break; 427 428 i += 6; 429 q = n / i; 430 if (q < i) 431 return n; 432 if (n == q * i) 433 break; 434 435 i += 2; 436 q = n / i; 437 if (q < i) 438 return n; 439 if (n == q * i) 440 break; 441 442 i += 4; 443 q = n / i; 444 if (q < i) 445 return n; 446 if (n == q * i) 447 break; 448 449 i += 6; 450 q = n / i; 451 if (q < i) 452 return n; 453 if (n == q * i) 454 break; 455 456 i += 2; 457 q = n / i; 458 if (q < i) 459 return n; 460 if (n == q * i) 461 break; 462 463 i += 6; 464 q = n / i; 465 if (q < i) 466 return n; 467 if (n == q * i) 468 break; 469 470 i += 6; 471 q = n / i; 472 if (q < i) 473 return n; 474 if (n == q * i) 475 break; 476 477 i += 4; 478 q = n / i; 479 if (q < i) 480 return n; 481 if (n == q * i) 482 break; 483 484 i += 2; 485 q = n / i; 486 if (q < i) 487 return n; 488 if (n == q * i) 489 break; 490 491 i += 4; 492 q = n / i; 493 if (q < i) 494 return n; 495 if (n == q * i) 496 break; 497 498 i += 6; 499 q = n / i; 500 if (q < i) 501 return n; 502 if (n == q * i) 503 break; 504 505 i += 2; 506 q = n / i; 507 if (q < i) 508 return n; 509 if (n == q * i) 510 break; 511 512 i += 6; 513 q = n / i; 514 if (q < i) 515 return n; 516 if (n == q * i) 517 break; 518 519 i += 4; 520 q = n / i; 521 if (q < i) 522 return n; 523 if (n == q * i) 524 break; 525 526 i += 2; 527 q = n / i; 528 if (q < i) 529 return n; 530 if (n == q * i) 531 break; 532 533 i += 4; 534 q = n / i; 535 if (q < i) 536 return n; 537 if (n == q * i) 538 break; 539 540 i += 2; 541 q = n / i; 542 if (q < i) 543 return n; 544 if (n == q * i) 545 break; 546 547 i += 10; 548 q = n / i; 549 if (q < i) 550 return n; 551 if (n == q * i) 552 break; 553 554 // This will loop i to the next "plane" of potential primes 555 i += 2; 556 } 557 } 558 next: 559 // n is not prime. Increment n to next potential prime. 560 if (++in == M) 561 { 562 ++k0; 563 in = 0; 564 } 565 n = L * k0 + indices[in]; 566 } 567 } 568 569 _LIBCPP_END_NAMESPACE_STD 570