lfsr.hpp

Go to the documentation of this file.

/*
 * SPDX-FileCopyrightText: 2025 M5Stack Technology CO LTD
 *
 * SPDX-License-Identifier: MIT
 */
#ifndef M5_UTILITY_LFSR_HPP
#define M5_UTILITY_LFSR_HPP
 
#include <bitset>
#include <climits>
#include "misc.hpp"
 
namespace m5 {
namespace utility {
 
template <uint32_t N, uint32_t... Taps>
class FibonacciLFSR_Right {
    static_assert(N >= 1, "N must be >= 1");
    static_assert(N <= 64, "N must be <= 64");
    static_assert(sizeof...(Taps) >= 1, "At least one tap required");
 
    // Tap boundary check: 1..N-1
    template <uint32_t...>
    struct all_valid : std::true_type {
        //
    };
    template <uint32_t A, uint32_t... Rest>
    struct all_valid<A, Rest...> : std::integral_constant<bool, (A >= 1 && A <= N) && all_valid<Rest...>::value> {
        //
    };
    static_assert(all_valid<Taps...>::value, "Taps out of range");
 
protected:
    // XOR of taps; bit index is N - Ts (Ts is exponent)
    template <uint32_t... Ts>
    static bool taps_xor(const std::bitset<N>& s)
    {
        bool r{};
        using swallow = int[];
        (void)swallow{0, (r ^= s.test(N - Ts), 0)...};  //  Swallow idiom
        return r;
    }
 
public:
    using storage_t    = typename uint_least_for_bits<N>::type;  
    using state_type_t = std::bitset<N>;                         
 
    explicit FibonacciLFSR_Right(const storage_t seed) noexcept : _state{seed}
    {
    }
 
    inline const state_type_t& state() const noexcept
    {
        return _state;
    }
 
    template <typename UL                                                                  = unsigned long,
              typename std::enable_if<(sizeof(UL) * CHAR_BIT >= 64), std::nullptr_t>::type = nullptr>
    inline storage_t value() const
    {
        return static_cast<storage_t>(_state.to_ulong());
    }
    template <typename UL                                                                 = unsigned long,
              typename std::enable_if<(sizeof(UL) * CHAR_BIT < 64), std::nullptr_t>::type = nullptr>
    inline storage_t value() const
    {
        return static_cast<storage_t>(_state.to_ullong());
    }
 
    bool step() noexcept
    {
        //        x = x >> 1 | (x >> 16 ^ x >> 18 ^ x >> 19 ^ x >> 21) << 31;
        const bool out = _state.test(0);             // LSB (output)
        const bool fb  = taps_xor<Taps...>(_state);  // feedback
        _state >>= 1;                                // Shift to right
        _state.set(N - 1, fb);                       // Insert feedback into MSB
        return out;
    }
 
    uint64_t step(const uint32_t nbits) noexcept
    {
        uint64_t v{};
        for (uint32_t i = 0; i < nbits; ++i) {
            v |= (uint64_t(step()) << i);
        }
        return v;
    }
 
    inline uint16_t next16() noexcept
    {
        return (uint16_t)step(16);
    }
    inline uint32_t next32() noexcept
    {
        return (uint32_t)step(32);
    }
    inline uint64_t next64() noexcept
    {
        return step(64);
    }
 
protected:
    static inline bool taps_xor_all(const state_type_t& s)
    {
        return taps_xor<Taps...>(s);
    }
 
    state_type_t _state;
};
 
template <uint32_t N, uint32_t... Taps>
class FibonacciLFSR_Left {
    static_assert(N >= 1, "N must be >= 1");
    static_assert(N <= 64, "N must be <= 64");
    static_assert(sizeof...(Taps) >= 1, "At least one tap required");
 
    // Tap boundary check: 1..N-1
    template <uint32_t...>
    struct all_valid : std::true_type {
        //
    };
    template <uint32_t A, uint32_t... Rest>
    struct all_valid<A, Rest...> : std::integral_constant<bool, (A >= 1 && A <= N) && all_valid<Rest...>::value> {
        //
    };
    static_assert(all_valid<Taps...>::value, "Taps out of range");
 
protected:
    template <uint32_t... Ts>
    static bool taps_xor(const std::bitset<N>& s)
    {
        bool r{};
        using swallow = int[];
        (void)swallow{0, (r ^= s.test(Ts - 1), 0)...};  // Swallow idiom
        return r;
    }
 
public:
    using storage_t    = typename uint_least_for_bits<N>::type;  
    using state_type_t = std::bitset<N>;                         
 
    explicit FibonacciLFSR_Left(const uint64_t seed) noexcept : _state{seed}
    {
    }
 
    inline const state_type_t& state() const noexcept
    {
        return _state;
    }
 
    template <typename UL                                                                  = unsigned long,
              typename std::enable_if<(sizeof(UL) * CHAR_BIT >= 64), std::nullptr_t>::type = nullptr>
    inline storage_t value() const
    {
        return static_cast<storage_t>(_state.to_ulong());
    }
    template <typename UL                                                                 = unsigned long,
              typename std::enable_if<(sizeof(UL) * CHAR_BIT < 64), std::nullptr_t>::type = nullptr>
    inline storage_t value() const
    {
        return static_cast<storage_t>(_state.to_ullong());
    }
 
    bool step() noexcept
    {
        const bool out = _state.test(N - 1);         // MSB (output)
        const bool fb  = taps_xor<Taps...>(_state);  // feedback
        _state <<= 1;                                // shift to left
        _state.set(0, fb);                           // insert feedback into LSB
        return out;
    }
 
    uint64_t step(const uint32_t nbits) noexcept
    {
        uint64_t v{};
        for (uint32_t i = 0; i < nbits; ++i) {
            v |= (uint64_t(step()) << i);  // i-th output placed at bit i
        }
        return v;
    }
 
    inline uint16_t next16() noexcept
    {
        return (uint16_t)step(16);
    }
    inline uint32_t next32() noexcept
    {
        return (uint32_t)step(32);
    }
    inline uint64_t next64() noexcept
    {
        return step(64);
    }
 
protected:
    static inline bool taps_xor_all(const state_type_t& s)
    {
        return taps_xor<Taps...>(s);
    }
    state_type_t _state;
};
 
}  // namespace utility
}  // namespace m5
#endif