Keep the valid signal from the formal engine ALU stable, until read
[soc.git] / TLB / src / LFSR2.py
1 # SPDX-License-Identifier: LGPL-2.1-or-later
2 # See Notices.txt for copyright information
3 from nmigen import Signal, Module, Elaboratable, Const
4 from typing import Iterable, FrozenSet, Optional, Iterator, Any, Union
5 from typing_extensions import final
6 from collections.abc import Set, Hashable
7
8
9 @final
10 class LFSRPolynomial(Set):
11 def __init__(self, exponents: Iterable[int] = ()):
12 max_exponent = 0
13
14 def elements() -> Iterable[int]:
15 nonlocal max_exponent
16 yield 0 # 0 is always required
17 for exponent in exponents:
18 if not isinstance(exponent, int):
19 raise TypeError()
20 if exponent < 0:
21 raise ValueError()
22 if exponent > max_exponent:
23 max_exponent = exponent
24 if exponent != 0:
25 yield exponent
26 self.__exponents = frozenset(elements())
27 self.__max_exponent = max_exponent
28
29 @property
30 def exponents(self) -> FrozenSet[int]:
31 return self.__exponents
32
33 @property
34 def max_exponent(self) -> int:
35 return self.__max_exponent
36
37 def __hash__(self) -> int:
38 return hash(self.exponents)
39
40 def __contains__(self, x: Any) -> bool:
41 return x in self.exponents
42
43 def __len__(self) -> int:
44 return len(self.exponents)
45
46 def __iter__(self) -> Iterator[int]:
47 return iter(self.exponents)
48
49 def __str__(self) -> str:
50 exponents = list(self.exponents)
51 exponents.sort(reverse=True)
52 retval = ""
53 separator = ""
54 for i in exponents:
55 retval += separator
56 separator = " + "
57 if i == 0:
58 retval += "1"
59 elif i == 1:
60 retval += "x"
61 else:
62 retval += f"x^{i}"
63 return retval
64
65 def __repr__(self) -> str:
66 exponents = list(self.exponents)
67 exponents.sort(reverse=True)
68 return f"LFSRPolynomial({exponents!r})"
69
70
71 # list of selected polynomials from https://web.archive.org/web/20190418121923/https://en.wikipedia.org/wiki/Linear-feedback_shift_register#Some_polynomials_for_maximal_LFSRs # noqa
72 LFSR_POLY_2 = LFSRPolynomial([2, 1, 0])
73 LFSR_POLY_3 = LFSRPolynomial([3, 2, 0])
74 LFSR_POLY_4 = LFSRPolynomial([4, 3, 0])
75 LFSR_POLY_5 = LFSRPolynomial([5, 3, 0])
76 LFSR_POLY_6 = LFSRPolynomial([6, 5, 0])
77 LFSR_POLY_7 = LFSRPolynomial([7, 6, 0])
78 LFSR_POLY_8 = LFSRPolynomial([8, 6, 5, 4, 0])
79 LFSR_POLY_9 = LFSRPolynomial([9, 5, 0])
80 LFSR_POLY_10 = LFSRPolynomial([10, 7, 0])
81 LFSR_POLY_11 = LFSRPolynomial([11, 9, 0])
82 LFSR_POLY_12 = LFSRPolynomial([12, 11, 10, 4, 0])
83 LFSR_POLY_13 = LFSRPolynomial([13, 12, 11, 8, 0])
84 LFSR_POLY_14 = LFSRPolynomial([14, 13, 12, 2, 0])
85 LFSR_POLY_15 = LFSRPolynomial([15, 14, 0])
86 LFSR_POLY_16 = LFSRPolynomial([16, 15, 13, 4, 0])
87 LFSR_POLY_17 = LFSRPolynomial([17, 14, 0])
88 LFSR_POLY_18 = LFSRPolynomial([18, 11, 0])
89 LFSR_POLY_19 = LFSRPolynomial([19, 18, 17, 14, 0])
90 LFSR_POLY_20 = LFSRPolynomial([20, 17, 0])
91 LFSR_POLY_21 = LFSRPolynomial([21, 19, 0])
92 LFSR_POLY_22 = LFSRPolynomial([22, 21, 0])
93 LFSR_POLY_23 = LFSRPolynomial([23, 18, 0])
94 LFSR_POLY_24 = LFSRPolynomial([24, 23, 22, 17, 0])
95
96
97 @final
98 class LFSR(Elaboratable):
99 def __init__(self, polynomial: Union[Iterable[int], LFSRPolynomial]):
100 self.__polynomial = LFSRPolynomial(polynomial)
101 self.state = Signal(self.width, reset=1)
102 self.enable = Signal(1, reset=1)
103
104 @property
105 def polynomial(self) -> LFSRPolynomial:
106 return self.__polynomial
107
108 @property
109 def width(self) -> int:
110 return self.polynomial.max_exponent
111
112 def elaborate(self, platform: Any) -> Module:
113 m = Module()
114 feedback: Value = Const(0)
115 for exponent in self.polynomial:
116 if exponent > 0:
117 feedback = feedback ^ self.state[exponent - 1]
118 if self.width > 1:
119 with m.If(self.enable):
120 m.d.sync += self.state[1:self.width].eq(
121 self.state[0:self.width - 1])
122 m.d.sync += self.state[0].eq(feedback)
123 return m