"""Galois LFSR model matching lfsr.sv, plus a primitivity check for tap sets. Tap sets use the XAPP052 numbering: bits 1..n, the list always contains n. The Galois mask has bit (t - 1) set for every tap t. """ from __future__ import annotations # Maximal-length taps, copied from XAPP052 Table 3 (Alfke, 1996) for these widths. TAPS: dict[int, tuple[int, ...]] = { 3: (3, 2), 4: (4, 3), 5: (5, 3), 6: (6, 5), 7: (7, 6), 8: (8, 6, 5, 4), 9: (9, 5), 10: (10, 7), 11: (11, 9), 12: (12, 6, 4, 1), 13: (13, 4, 3, 1), 14: (14, 5, 3, 1), 15: (15, 14), 16: (16, 15, 13, 4), 24: (24, 23, 22, 17), 32: (32, 22, 2, 1), } def mask_from_taps(taps: tuple[int, ...]) -> int: return sum(1 << (t - 1) for t in taps) def galois_step(state: int, mask: int) -> int: """One clock of a right-shifting Galois LFSR (the same update as lfsr.sv).""" return (state >> 1) ^ mask if state & 1 else state >> 1 def sequence(width: int, mask: int, seed: int, n: int) -> list[int]: out, s = [], seed for _ in range(n): out.append(s) s = galois_step(s, mask) return out def period(width: int, mask: int, seed: int = 1) -> int: """Clock cycles until the state returns to seed (brute force).""" s, k = galois_step(seed, mask), 1 limit = 1 << width while s != seed: s = galois_step(s, mask) k += 1 if k > limit: raise RuntimeError("state never returned to seed") return k def _polymulmod(a: int, b: int, poly: int, n: int) -> int: r = 0 while b: if b & 1: r ^= a b >>= 1 a <<= 1 if a >> n & 1: a ^= poly return r def _polypowmod(e: int, poly: int, n: int) -> int: result, base = 1, 2 # base is the polynomial x while e: if e & 1: result = _polymulmod(result, base, poly, n) base = _polymulmod(base, base, poly, n) e >>= 1 return result def _prime_factors(m: int) -> list[int]: f, p = [], 2 while p * p <= m: if m % p == 0: f.append(p) while m % p == 0: m //= p p += 1 if m > 1: f.append(m) return f def is_primitive(taps: tuple[int, ...]) -> bool: """True if x^n + sum(x^t for the other taps) + 1 is primitive over GF(2). The order of x modulo the polynomial must be exactly 2^n - 1. """ n = max(taps) poly = (1 << n) | 1 for t in taps: if t != n: poly |= 1 << t order = (1 << n) - 1 if _polypowmod(order, poly, n) != 1: return False return all(_polypowmod(order // q, poly, n) != 1 for q in _prime_factors(order)) if __name__ == "__main__": for w, t in TAPS.items(): print(f"{w:2d} taps {t} mask 0x{mask_from_taps(t):X} primitive {is_primitive(t)}")