1 // Copyright 2016 The Fuchsia Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4 
5 #pragma once
6 
7 #include <stdint.h>
8 
9 namespace fbl {
10 namespace tests {
11 
12 namespace internal {
13 
14 // A templated implementation of a linear feedback shift register for various
15 // core state sizes.  With proper selection of the generator, the LFSR will be a
16 // maximum-cycle LFSR meaning that it will cycle through all of its core states
17 // (except for all zeros) exactly once before repeating.
18 template <typename CoreType, CoreType generator>
19 class Lfsr {
20 public:
21     static_assert(is_unsigned_integer<CoreType>::value,
22                  "LFSR core type must be an unsigned integer!");
23 
Lfsr(CoreType initial_core)24     constexpr explicit Lfsr(CoreType initial_core) : core_(initial_core) { }
25 
26     template <typename T>
SetCore(T val)27     void SetCore(T val) {
28         static_assert(is_unsigned_integer<T>::value,
29                      "LFSR initializer type must be an unsigned integer!");
30         core_ = static_cast<CoreType>(val);
31     };
32 
PeekCore()33     CoreType PeekCore() const {
34         return core_;
35     }
36 
GetNext()37     CoreType GetNext() {
38         CoreType ret  = 0u;
39         CoreType flag = 1u;
40 
41         for (size_t i = 0; i < (sizeof(size_t) << 3); ++i) {
42             bool bit = core_ & 1u;
43             core_ = static_cast<CoreType>(core_ >> 1u);
44             if (bit) {
45                 core_ ^= generator;
46                 ret   |= flag;
47             }
48 
49             flag = static_cast<CoreType>(flag << 1u);
50         }
51 
52         return ret;
53     }
54 
55 private:
56     CoreType core_;
57 };
58 
59 }  // namespace internal
60 
61 // User-facing implementation of LFSRs of various sizes with pre-selected
62 // maximum-cycle generators.
63 template <typename T, typename Enable = void>
64 class Lfsr;
65 
66 // MAKE_LFSR
67 //
68 // Temporary macro which deals with the boilerplate declaration of an LFSR of a
69 // particular core size with a particular generator, exposing the constructor in
70 // the process.
71 #define MAKE_LFSR(_bits, _gen)                                                  \
72 template <typename T>                                                           \
73 class Lfsr<T,                                                                   \
74            typename enable_if<is_unsigned_integer<T>::value &&                  \
75                               ((sizeof(T) << 3) == _bits)>::type                \
76           > : public internal::Lfsr<uint ## _bits ## _t, _gen> {                \
77 public:                                                                         \
78     using CoreType = uint ## _bits ## _t;                                       \
79                                                                                 \
80     template <typename U>                                                       \
81     constexpr explicit Lfsr(U initial_core)                                     \
82         : internal::Lfsr<CoreType, _gen>(static_cast<CoreType>(initial_core)) { \
83         static_assert(is_unsigned_integer<U>::value,                            \
84                      "LFSR initializer type must be an unsigned integer!");     \
85     }                                                                           \
86                                                                                 \
87     constexpr Lfsr() : internal::Lfsr<CoreType, _gen>(1u) { }                   \
88 }
89 
90 MAKE_LFSR(8,  0xB8);
91 MAKE_LFSR(16, 0xB400);
92 MAKE_LFSR(32, 0xA3000000);
93 MAKE_LFSR(64, 0xD800000000000000);
94 
95 #undef MAKE_LFSR
96 
97 }  // namespace tests
98 }  // namespace fbl
99