THUAI6/CAPI/cpp/grpc/include/absl/random/internal/randen_engine.h

// Copyright 2017 The Abseil Authors.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//      https://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

#ifndef ABSL_RANDOM_INTERNAL_RANDEN_ENGINE_H_
#define ABSL_RANDOM_INTERNAL_RANDEN_ENGINE_H_

#include <algorithm>
#include <cinttypes>
#include <cstdlib>
#include <iostream>
#include <iterator>
#include <limits>
#include <type_traits>

#include "absl/base/internal/endian.h"
#include "absl/meta/type_traits.h"
#include "absl/random/internal/iostream_state_saver.h"
#include "absl/random/internal/randen.h"

namespace absl
{
    ABSL_NAMESPACE_BEGIN
    namespace random_internal
    {

        // Deterministic pseudorandom byte generator with backtracking resistance
        // (leaking the state does not compromise prior outputs). Based on Reverie
        // (see "A Robust and Sponge-Like PRNG with Improved Efficiency") instantiated
        // with an improved Simpira-like permutation.
        // Returns values of type "T" (must be a built-in unsigned integer type).
        //
        // RANDen = RANDom generator or beetroots in Swiss High German.
        // 'Strong' (well-distributed, unpredictable, backtracking-resistant) random
        // generator, faster in some benchmarks than std::mt19937_64 and pcg64_c32.
        template<typename T>
        class alignas(8) randen_engine
        {
        public:
            // C++11 URBG interface:
            using result_type = T;
            static_assert(std::is_unsigned<result_type>::value, "randen_engine template argument must be a built-in unsigned "
                                                                "integer type");

            static constexpr result_type(min)()
            {
                return (std::numeric_limits<result_type>::min)();
            }

            static constexpr result_type(max)()
            {
                return (std::numeric_limits<result_type>::max)();
            }

            randen_engine() :
                randen_engine(0)
            {
            }
            explicit randen_engine(result_type seed_value)
            {
                seed(seed_value);
            }

            template<class SeedSequence, typename = typename absl::enable_if_t<!std::is_same<SeedSequence, randen_engine>::value>>
            explicit randen_engine(SeedSequence&& seq)
            {
                seed(seq);
            }

            // alignment requirements dictate custom copy and move constructors.
            randen_engine(const randen_engine& other) :
                next_(other.next_),
                impl_(other.impl_)
            {
                std::memcpy(state(), other.state(), kStateSizeT * sizeof(result_type));
            }
            randen_engine& operator=(const randen_engine& other)
            {
                next_ = other.next_;
                impl_ = other.impl_;
                std::memcpy(state(), other.state(), kStateSizeT * sizeof(result_type));
                return *this;
            }

            // Returns random bits from the buffer in units of result_type.
            result_type operator()()
            {
                // Refill the buffer if needed (unlikely).
                auto* begin = state();
                if (next_ >= kStateSizeT)
                {
                    next_ = kCapacityT;
                    impl_.Generate(begin);
                }
                return little_endian::ToHost(begin[next_++]);
            }

            template<class SeedSequence>
            typename absl::enable_if_t<
                !std::is_convertible<SeedSequence, result_type>::value>
                seed(SeedSequence&& seq)
            {
                // Zeroes the state.
                seed();
                reseed(seq);
            }

            void seed(result_type seed_value = 0)
            {
                next_ = kStateSizeT;
                // Zeroes the inner state and fills the outer state with seed_value to
                // mimic the behaviour of reseed
                auto* begin = state();
                std::fill(begin, begin + kCapacityT, 0);
                std::fill(begin + kCapacityT, begin + kStateSizeT, seed_value);
            }

            // Inserts entropy into (part of) the state. Calling this periodically with
            // sufficient entropy ensures prediction resistance (attackers cannot predict
            // future outputs even if state is compromised).
            template<class SeedSequence>
            void reseed(SeedSequence& seq)
            {
                using sequence_result_type = typename SeedSequence::result_type;
                static_assert(sizeof(sequence_result_type) == 4, "SeedSequence::result_type must be 32-bit");
                constexpr size_t kBufferSize =
                    Randen::kSeedBytes / sizeof(sequence_result_type);
                alignas(16) sequence_result_type buffer[kBufferSize];

                // Randen::Absorb XORs the seed into state, which is then mixed by a call
                // to Randen::Generate. Seeding with only the provided entropy is preferred
                // to using an arbitrary generate() call, so use [rand.req.seed_seq]
                // size as a proxy for the number of entropy units that can be generated
                // without relying on seed sequence mixing...
                const size_t entropy_size = seq.size();
                if (entropy_size < kBufferSize)
                {
                    // ... and only request that many values, or 256-bits, when unspecified.
                    const size_t requested_entropy = (entropy_size == 0) ? 8u : entropy_size;
                    std::fill(buffer + requested_entropy, buffer + kBufferSize, 0);
                    seq.generate(buffer, buffer + requested_entropy);
#ifdef ABSL_IS_BIG_ENDIAN
                    // Randen expects the seed buffer to be in Little Endian; reverse it on
                    // Big Endian platforms.
                    for (sequence_result_type& e : buffer)
                    {
                        e = absl::little_endian::FromHost(e);
                    }
#endif
                    // The Randen paper suggests preferentially initializing even-numbered
                    // 128-bit vectors of the randen state (there are 16 such vectors).
                    // The seed data is merged into the state offset by 128-bits, which
                    // implies prefering seed bytes [16..31, ..., 208..223]. Since the
                    // buffer is 32-bit values, we swap the corresponding buffer positions in
                    // 128-bit chunks.
                    size_t dst = kBufferSize;
                    while (dst > 7)
                    {
                        // leave the odd bucket as-is.
                        dst -= 4;
                        size_t src = dst >> 1;
                        // swap 128-bits into the even bucket
                        std::swap(buffer[--dst], buffer[--src]);
                        std::swap(buffer[--dst], buffer[--src]);
                        std::swap(buffer[--dst], buffer[--src]);
                        std::swap(buffer[--dst], buffer[--src]);
                    }
                }
                else
                {
                    seq.generate(buffer, buffer + kBufferSize);
                }
                impl_.Absorb(buffer, state());

                // Generate will be called when operator() is called
                next_ = kStateSizeT;
            }

            void discard(uint64_t count)
            {
                uint64_t step = std::min<uint64_t>(kStateSizeT - next_, count);
                count -= step;

                constexpr uint64_t kRateT = kStateSizeT - kCapacityT;
                auto* begin = state();
                while (count > 0)
                {
                    next_ = kCapacityT;
                    impl_.Generate(*reinterpret_cast<result_type(*)[kStateSizeT]>(begin));
                    step = std::min<uint64_t>(kRateT, count);
                    count -= step;
                }
                next_ += step;
            }

            bool operator==(const randen_engine& other) const
            {
                const auto* begin = state();
                return next_ == other.next_ &&
                       std::equal(begin, begin + kStateSizeT, other.state());
            }

            bool operator!=(const randen_engine& other) const
            {
                return !(*this == other);
            }

            template<class CharT, class Traits>
            friend std::basic_ostream<CharT, Traits>& operator<<(
                std::basic_ostream<CharT, Traits>& os,  // NOLINT(runtime/references)
                const randen_engine<T>& engine
            )
            {  // NOLINT(runtime/references)
                using numeric_type =
                    typename random_internal::stream_format_type<result_type>::type;
                auto saver = random_internal::make_ostream_state_saver(os);
                auto* it = engine.state();
                for (auto* end = it + kStateSizeT; it < end; ++it)
                {
                    // In the case that `elem` is `uint8_t`, it must be cast to something
                    // larger so that it prints as an integer rather than a character. For
                    // simplicity, apply the cast all circumstances.
                    os << static_cast<numeric_type>(little_endian::FromHost(*it))
                       << os.fill();
                }
                os << engine.next_;
                return os;
            }

            template<class CharT, class Traits>
            friend std::basic_istream<CharT, Traits>& operator>>(
                std::basic_istream<CharT, Traits>& is,  // NOLINT(runtime/references)
                randen_engine<T>& engine
            )
            {  // NOLINT(runtime/references)
                using numeric_type =
                    typename random_internal::stream_format_type<result_type>::type;
                result_type state[kStateSizeT];
                size_t next;
                for (auto& elem : state)
                {
                    // It is not possible to read uint8_t from wide streams, so it is
                    // necessary to read a wider type and then cast it to uint8_t.
                    numeric_type value;
                    is >> value;
                    elem = little_endian::ToHost(static_cast<result_type>(value));
                }
                is >> next;
                if (is.fail())
                {
                    return is;
                }
                std::memcpy(engine.state(), state, sizeof(state));
                engine.next_ = next;
                return is;
            }

        private:
            static constexpr size_t kStateSizeT =
                Randen::kStateBytes / sizeof(result_type);
            static constexpr size_t kCapacityT =
                Randen::kCapacityBytes / sizeof(result_type);

            // Returns the state array pointer, which is aligned to 16 bytes.
            // The first kCapacityT are the `inner' sponge; the remainder are available.
            result_type* state()
            {
                return reinterpret_cast<result_type*>(
                    (reinterpret_cast<uintptr_t>(&raw_state_) & 0xf) ? (raw_state_ + 8) : raw_state_
                );
            }
            const result_type* state() const
            {
                return const_cast<randen_engine*>(this)->state();
            }

            // raw state array, manually aligned in state(). This overallocates
            // by 8 bytes since C++ does not guarantee extended heap alignment.
            alignas(8) char raw_state_[Randen::kStateBytes + 8];
            size_t next_;  // index within state()
            Randen impl_;
        };

    }  // namespace random_internal
    ABSL_NAMESPACE_END
}  // namespace absl

#endif  // ABSL_RANDOM_INTERNAL_RANDEN_ENGINE_H_