tor-browser

The Tor Browser
git clone https://git.dasho.dev/tor-browser.git
Log | Files | Refs | README | LICENSE

random_test.cc (10613B)

      1 // Unless required by applicable law or agreed to in writing, software
      2 // distributed under the License is distributed on an "AS IS" BASIS,
      3 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
      4 // See the License for the specific language governing permissions and
      5 // limitations under the License.
      6 
      7 #include <cstdint>
      8 #include <cstdio>
      9 #include <ctime>
     10 #include <iostream>  // cerr
     11 #include <random>
     12 #include <vector>
     13 
     14 // clang-format off
     15 #undef HWY_TARGET_INCLUDE
     16 #define HWY_TARGET_INCLUDE "hwy/contrib/random/random_test.cc"  // NOLINT
     17 #include "hwy/foreach_target.h"  // IWYU pragma: keep
     18 #include "hwy/highway.h"
     19 #include "hwy/contrib/random/random-inl.h"
     20 #include "hwy/tests/test_util-inl.h"
     21 // clang-format on
     22 
     23 HWY_BEFORE_NAMESPACE();
     24 namespace hwy {
     25 namespace HWY_NAMESPACE {  // required: unique per target
     26 namespace {
     27 
     28 constexpr std::uint64_t tests = 1UL << 10;
     29 
     30 std::uint64_t GetSeed() { return static_cast<uint64_t>(std::time(nullptr)); }
     31 
     32 void RngLoop(const std::uint64_t seed, std::uint64_t* HWY_RESTRICT result,
     33             const size_t size) {
     34  const ScalableTag<std::uint64_t> d;
     35  VectorXoshiro generator{seed};
     36  for (size_t i = 0; i < size; i += Lanes(d)) {
     37    Store(generator(), d, result + i);
     38  }
     39 }
     40 
     41 #if HWY_HAVE_FLOAT64
     42 void UniformLoop(const std::uint64_t seed, double* HWY_RESTRICT result,
     43                 const size_t size) {
     44  const ScalableTag<double> d;
     45  VectorXoshiro generator{seed};
     46  for (size_t i = 0; i < size; i += Lanes(d)) {
     47    Store(generator.Uniform(), d, result + i);
     48  }
     49 }
     50 #endif
     51 
     52 void TestSeeding() {
     53  const std::uint64_t seed = GetSeed();
     54  VectorXoshiro generator{seed};
     55  internal::Xoshiro reference{seed};
     56  const auto& state = generator.GetState();
     57  const ScalableTag<std::uint64_t> d;
     58  const std::size_t lanes = Lanes(d);
     59  for (std::size_t i = 0UL; i < lanes; ++i) {
     60    const auto& reference_state = reference.GetState();
     61    for (std::size_t j = 0UL; j < reference_state.size(); ++j) {
     62      if (state[{j}][i] != reference_state[j]) {
     63        std::cerr << "SEED: " << seed << "\n";
     64        std::cerr << "TEST SEEDING ERROR: ";
     65        std::cerr << "state[" << j << "][" << i << "] -> " << state[{j}][i]
     66                  << " != " << reference_state[j] << "\n";
     67        HWY_ASSERT(0);
     68      }
     69    }
     70    reference.Jump();
     71  }
     72 }
     73 
     74 void TestMultiThreadSeeding() {
     75  const std::uint64_t seed = GetSeed();
     76  const std::uint64_t threadId = std::random_device()() % 1000;
     77  VectorXoshiro generator{seed, threadId};
     78  internal::Xoshiro reference{seed};
     79 
     80  for (std::size_t i = 0UL; i < threadId; ++i) {
     81    reference.LongJump();
     82  }
     83 
     84  const auto& state = generator.GetState();
     85  const ScalableTag<std::uint64_t> d;
     86  const std::size_t lanes = Lanes(d);
     87  for (std::size_t i = 0UL; i < lanes; ++i) {
     88    const auto& reference_state = reference.GetState();
     89    for (std::size_t j = 0UL; j < reference_state.size(); ++j) {
     90      if (state[{j}][i] != reference_state[j]) {
     91        std::cerr << "SEED: " << seed << std::endl;
     92        std::cerr << "TEST SEEDING ERROR: ";
     93        std::cerr << "state[" << j << "][" << i << "] -> " << state[{j}][i]
     94                  << " != " << reference_state[j] << "\n";
     95        HWY_ASSERT(0);
     96      }
     97    }
     98    reference.Jump();
     99  }
    100 }
    101 
    102 void TestRandomUint64() {
    103  const std::uint64_t seed = GetSeed();
    104  const auto result_array = hwy::MakeUniqueAlignedArray<std::uint64_t>(tests);
    105  RngLoop(seed, result_array.get(), tests);
    106  std::vector<internal::Xoshiro> reference;
    107  reference.emplace_back(seed);
    108  const ScalableTag<std::uint64_t> d;
    109  const std::size_t lanes = Lanes(d);
    110  for (std::size_t i = 1UL; i < lanes; ++i) {
    111    auto rng = reference.back();
    112    rng.Jump();
    113    reference.emplace_back(rng);
    114  }
    115 
    116  for (std::size_t i = 0UL; i < tests; i += lanes) {
    117    for (std::size_t lane = 0UL; lane < lanes; ++lane) {
    118      const std::uint64_t result = reference[lane]();
    119      if (result_array[i + lane] != result) {
    120        std::cerr << "SEED: " << seed << std::endl;
    121        std::cerr << "TEST UINT64 GENERATOR ERROR: result_array[" << i + lane
    122                  << "] -> " << result_array[i + lane] << " != " << result
    123                  << std::endl;
    124        HWY_ASSERT(0);
    125      }
    126    }
    127  }
    128 }
    129 void TestUniformDist() {
    130 #if HWY_HAVE_FLOAT64
    131  const std::uint64_t seed = GetSeed();
    132  const auto result_array = hwy::MakeUniqueAlignedArray<double>(tests);
    133  UniformLoop(seed, result_array.get(), tests);
    134  internal::Xoshiro reference{seed};
    135  const ScalableTag<double> d;
    136  const std::size_t lanes = Lanes(d);
    137  for (std::size_t i = 0UL; i < tests; i += lanes) {
    138    const double result = reference.Uniform();
    139    if (result_array[i] != result) {
    140      std::cerr << "SEED: " << seed << std::endl;
    141      std::cerr << "TEST UNIFORM GENERATOR ERROR: result_array[" << i << "] -> "
    142                << result_array[i] << " != " << result << std::endl;
    143      HWY_ASSERT(0);
    144    }
    145  }
    146 #endif  // HWY_HAVE_FLOAT64
    147 }
    148 
    149 void TestNextNRandomUint64() {
    150  const std::uint64_t seed = GetSeed();
    151  VectorXoshiro generator{seed};
    152  const auto result_array = generator.operator()(tests);
    153  std::vector<internal::Xoshiro> reference;
    154  reference.emplace_back(seed);
    155  const ScalableTag<std::uint64_t> d;
    156  const std::size_t lanes = Lanes(d);
    157  for (std::size_t i = 1UL; i < lanes; ++i) {
    158    auto rng = reference.back();
    159    rng.Jump();
    160    reference.emplace_back(rng);
    161  }
    162 
    163  for (std::size_t i = 0UL; i < tests; i += lanes) {
    164    for (std::size_t lane = 0UL; lane < lanes; ++lane) {
    165      const std::uint64_t result = reference[lane]();
    166      if (result_array[i + lane] != result) {
    167        std::cerr << "SEED: " << seed << std::endl;
    168        std::cerr << "TEST UINT64 GENERATOR ERROR: result_array[" << i + lane
    169                  << "] -> " << result_array[i + lane] << " != " << result
    170                  << std::endl;
    171        HWY_ASSERT(0);
    172      }
    173    }
    174  }
    175 }
    176 
    177 void TestNextFixedNRandomUint64() {
    178  const std::uint64_t seed = GetSeed();
    179  VectorXoshiro generator{seed};
    180  const auto result_array = generator.operator()<tests>();
    181  std::vector<internal::Xoshiro> reference;
    182  reference.emplace_back(seed);
    183  const ScalableTag<std::uint64_t> d;
    184  const std::size_t lanes = Lanes(d);
    185  for (std::size_t i = 1UL; i < lanes; ++i) {
    186    auto rng = reference.back();
    187    rng.Jump();
    188    reference.emplace_back(rng);
    189  }
    190 
    191  for (std::size_t i = 0UL; i < tests; i += lanes) {
    192    for (std::size_t lane = 0UL; lane < lanes; ++lane) {
    193      const std::uint64_t result = reference[lane]();
    194      if (result_array[i + lane] != result) {
    195        std::cerr << "SEED: " << seed << std::endl;
    196        std::cerr << "TEST UINT64 GENERATOR ERROR: result_array[" << i + lane
    197                  << "] -> " << result_array[i + lane] << " != " << result
    198                  << std::endl;
    199 
    200        HWY_ASSERT(0);
    201      }
    202    }
    203  }
    204 }
    205 void TestNextNUniformDist() {
    206 #if HWY_HAVE_FLOAT64
    207  const std::uint64_t seed = GetSeed();
    208  VectorXoshiro generator{seed};
    209  const auto result_array = generator.Uniform(tests);
    210  internal::Xoshiro reference{seed};
    211  const ScalableTag<double> d;
    212  const std::size_t lanes = Lanes(d);
    213  for (std::size_t i = 0UL; i < tests; i += lanes) {
    214    const double result = reference.Uniform();
    215    if (result_array[i] != result) {
    216      std::cerr << "SEED: " << seed << std::endl;
    217      std::cerr << "TEST UNIFORM GENERATOR ERROR: result_array[" << i << "] -> "
    218                << result_array[i] << " != " << result << std::endl;
    219 
    220      HWY_ASSERT(0);
    221    }
    222  }
    223 #endif  // HWY_HAVE_FLOAT64
    224 }
    225 
    226 void TestNextFixedNUniformDist() {
    227 #if HWY_HAVE_FLOAT64
    228  const std::uint64_t seed = GetSeed();
    229  VectorXoshiro generator{seed};
    230  const auto result_array = generator.Uniform<tests>();
    231  internal::Xoshiro reference{seed};
    232  const ScalableTag<double> d;
    233  const std::size_t lanes = Lanes(d);
    234  for (std::size_t i = 0UL; i < tests; i += lanes) {
    235    const double result = reference.Uniform();
    236    if (result_array[i] != result) {
    237      std::cerr << "SEED: " << seed << std::endl;
    238      std::cerr << "TEST UNIFORM GENERATOR ERROR: result_array[" << i << "] -> "
    239                << result_array[i] << " != " << result << std::endl;
    240      HWY_ASSERT(0);
    241    }
    242  }
    243 #endif  // HWY_HAVE_FLOAT64
    244 }
    245 
    246 void TestCachedXorshiro() {
    247  const std::uint64_t seed = GetSeed();
    248 
    249  CachedXoshiro<> generator{seed};
    250  std::vector<internal::Xoshiro> reference;
    251  reference.emplace_back(seed);
    252  const ScalableTag<std::uint64_t> d;
    253  const std::size_t lanes = Lanes(d);
    254  for (std::size_t i = 1UL; i < lanes; ++i) {
    255    auto rng = reference.back();
    256    rng.Jump();
    257    reference.emplace_back(rng);
    258  }
    259 
    260  for (std::size_t i = 0UL; i < tests; i += lanes) {
    261    for (std::size_t lane = 0UL; lane < lanes; ++lane) {
    262      const std::uint64_t result = reference[lane]();
    263      const std::uint64_t got = generator();
    264      if (got != result) {
    265        std::cerr << "SEED: " << seed << std::endl;
    266        std::cerr << "TEST CachedXoshiro GENERATOR ERROR: result_array["
    267                  << i + lane << "] -> " << got << " != " << result
    268                  << std::endl;
    269 
    270        HWY_ASSERT(0);
    271      }
    272    }
    273  }
    274 }
    275 void TestUniformCachedXorshiro() {
    276 #if HWY_HAVE_FLOAT64
    277  const std::uint64_t seed = GetSeed();
    278 
    279  CachedXoshiro<> generator{seed};
    280  std::uniform_real_distribution<double> distribution{0., 1.};
    281  for (std::size_t i = 0UL; i < tests; ++i) {
    282    const double result = distribution(generator);
    283 
    284    if (result < 0. || result >= 1.) {
    285      std::cerr << "SEED: " << seed << std::endl;
    286      std::cerr << "TEST CachedXoshiro GENERATOR ERROR: result_array[" << i
    287                << "] -> " << result << " not in interval [0, 1)" << std::endl;
    288      HWY_ASSERT(0);
    289    }
    290  }
    291 #endif  // HWY_HAVE_FLOAT64
    292 }
    293 
    294 }  // namespace
    295 // NOLINTNEXTLINE(google-readability-namespace-comments)
    296 }  // namespace HWY_NAMESPACE
    297 }  // namespace hwy
    298 HWY_AFTER_NAMESPACE();  // required if not using HWY_ATTR
    299 
    300 #if HWY_ONCE
    301 namespace hwy {
    302 namespace {
    303 HWY_BEFORE_TEST(HwyRandomTest);
    304 HWY_EXPORT_AND_TEST_P(HwyRandomTest, TestSeeding);
    305 HWY_EXPORT_AND_TEST_P(HwyRandomTest, TestMultiThreadSeeding);
    306 HWY_EXPORT_AND_TEST_P(HwyRandomTest, TestRandomUint64);
    307 HWY_EXPORT_AND_TEST_P(HwyRandomTest, TestNextNRandomUint64);
    308 HWY_EXPORT_AND_TEST_P(HwyRandomTest, TestNextFixedNRandomUint64);
    309 HWY_EXPORT_AND_TEST_P(HwyRandomTest, TestCachedXorshiro);
    310 HWY_EXPORT_AND_TEST_P(HwyRandomTest, TestUniformDist);
    311 HWY_EXPORT_AND_TEST_P(HwyRandomTest, TestNextNUniformDist);
    312 HWY_EXPORT_AND_TEST_P(HwyRandomTest, TestNextFixedNUniformDist);
    313 HWY_EXPORT_AND_TEST_P(HwyRandomTest, TestUniformCachedXorshiro);
    314 HWY_AFTER_TEST();
    315 }  // namespace
    316 }  // namespace hwy
    317 HWY_TEST_MAIN();
    318 #endif  // HWY_ONCE