TLB/src/LFSR.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