Changeset e7a4f41 in mainline
- Timestamp:
- 2018-07-05T21:41:22Z (7 years ago)
- Branches:
- lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
- Children:
- 6b81ca5
- Parents:
- 08be4a4
- git-author:
- Dzejrou <dzejrou@…> (2018-05-02 19:05:36)
- git-committer:
- Dzejrou <dzejrou@…> (2018-07-05 21:41:22)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
uspace/lib/cpp/include/impl/random.hpp
r08be4a4 re7a4f41 423 423 424 424 template<class UIntType, size_t w, size_t s, size_t r> 425 class subtract_with_carry_engine; 425 class subtract_with_carry_engine 426 { 427 // TODO: fix these 428 /* static_assert(0U < s); */ 429 /* static_assert(s < r); */ 430 /* static_assert(0U < w); */ 431 /* static_assert(w <= numeric_limits<UIntType>::digits); */ 432 433 public: 434 using result_type = UIntType; 435 436 static constexpr size_t word_size = w; 437 static constexpr size_t short_lag = s; 438 static constexpr size_t long_lag = r; 439 440 static constexpr result_type min() 441 { 442 return result_type{}; 443 } 444 445 static constexpr result_type max() 446 { 447 return m_ - 1; 448 } 449 450 static constexpr result_type default_seed = 19780503U; 451 452 explicit subtract_with_carry_engine(result_type value = default_seed) 453 : state_{}, i_{}, carry_{} 454 { 455 seed(value); 456 } 457 458 template<class Seq> 459 explicit subtract_with_carry_engine( 460 enable_if_t<aux::is_seed_sequence_v<Seq, result_type>, Seq&> q 461 ) 462 : state_{}, i_{}, carry_{} 463 { 464 seed(q); 465 } 466 467 void seed(result_type value = default_seed) 468 { 469 linear_congruential_engine< 470 result_type, 40014U, 0U, 2147483563U 471 > e{value == 0U ? default_seed : value}; 472 473 auto n = aux::ceil(w / 32.0); 474 auto z = new result_type[n]; 475 476 for (long long i = -r; i <= -1; ++i) 477 { 478 for (size_t i = 0; i < n; ++i) 479 z[i] = e() % aux::pow2u(32); 480 481 state_[idx_(i)] = result_type{}; 482 for (size_t j = 0; j < n; ++j) 483 state_[idx_(i)] += z[j] * aux::pow2u(32 * j); 484 state_[idx_(i)] %= m_; 485 } 486 487 if (state_[idx_(-1)] == 0) 488 carry_ = 1; 489 else 490 carry_ = 0; 491 492 delete[] z; 493 } 494 495 template<class Seq> 496 void seed( 497 enable_if_t<aux::is_seed_sequence_v<Seq, result_type>, Seq&> q 498 ) 499 { 500 auto k = aux::ceil(w / 32.0); 501 auto arr = new result_type[r * k]; 502 503 q.generate(arr, arr + r * k); 504 505 for (long long i = -r; i <= -1; ++i) 506 { 507 state_[idx_(i)] = result_type{}; 508 for (long long j = 0; j < k; ++j) 509 state_[idx_(i)] += arr[k * (i + r) + j] * aux::pow2(32 * j); 510 state_[idx_(i)] %= m_; 511 } 512 513 delete[] arr; 514 515 if (state_[idx_(-1)] == 0) 516 carry_ = 1; 517 else 518 carry_ = 0; 519 } 520 521 result_type operator()() 522 { 523 return generate_(); 524 } 525 526 void discard(unsigned long long z) 527 { 528 for (unsigned long long i = 0ULL; i < z; ++i) 529 transition_(); 530 } 531 532 bool operator==(const subtract_with_carry_engine& rhs) const 533 { 534 for (size_t i = 0; i < r; ++i) 535 { 536 if (state_[i] != rhs.state_[i]) 537 return false; 538 } 539 540 return true; 541 } 542 543 bool operator!=(const subtract_with_carry_engine& rhs) const 544 { 545 return !(*this == rhs); 546 } 547 548 template<class Char, class Traits> 549 basic_ostream<Char, Traits>& operator<<(basic_ostream<Char, Traits>& os) const 550 { 551 auto flags = os.flags(); 552 os.flags(ios_base::dec | ios_base::left); 553 554 for (size_t j = r + 1; j > 1; --j) 555 { 556 os << state_[idx_(i_ - j - 1)]; 557 os << os.widen(' '); 558 } 559 560 os << carry_; 561 562 os.flags(flags); 563 return os; 564 } 565 566 template<class Char, class Traits> 567 basic_istream<Char, Traits>& operator>>(basic_istream<Char, Traits>& is) const 568 { 569 auto flags = is.flags(); 570 is.flags(ios_base::dec); 571 572 for (size_t j = r + 1; j > 1; --j) 573 { 574 if (!(is >> state_[idx_(i_ - j - 1)])) 575 { 576 is.setstate(ios::failbit); 577 break; 578 } 579 } 580 581 if (!(is >> carry_)) 582 is.setstate(ios::failbit); 583 584 is.flags(flags); 585 return is; 586 } 587 588 private: 589 result_type state_[r]; 590 size_t i_; 591 uint8_t carry_; 592 593 static constexpr result_type m_ = aux::pow2u(w); 594 595 auto transition_() 596 { 597 auto y = static_cast<int64_t>(state_[idx_(i_ - s)]) - state_[idx_(i_ - r)] - carry_; 598 state_[i_] = y % m_; 599 600 i_ = (i_ + 1) % r; 601 602 return static_cast<result_type>(y % m_); 603 } 604 605 result_type generate_() 606 { 607 return transition_(); 608 } 609 610 size_t idx_(size_t idx) const 611 { 612 return idx % r; 613 } 614 }; 426 615 427 616 /**
Note:
See TracChangeset
for help on using the changeset viewer.