"""
from dataclasses import dataclass, field, fields
-from nmigen.hdl.ir import Elaboratable
from nmigen.hdl.ast import Signal, Value
from nmigen.hdl.dsl import Module
from nmutil.singlepipe import ControlBase
from nmutil.clz import CLZ, clz
-def equal_leading_zero_count_reference(a, b, width):
- """checks if `clz(a) == clz(b)`.
- Reference code for algorithm used in `EqualLeadingZeroCount`.
- """
- assert isinstance(width, int) and 0 <= width
- assert isinstance(a, int) and 0 <= a < (1 << width)
- assert isinstance(b, int) and 0 <= b < (1 << width)
- eq = True # both have no leading zeros so far...
- for i in range(width):
- a_bit = (a >> i) & 1
- b_bit = (b >> i) & 1
- # `both_ones` is set if both have no leading zeros so far
- both_ones = a_bit & b_bit
- # `different` is set if there are a different number of leading
- # zeros so far
- different = a_bit != b_bit
- if both_ones:
- eq = True
- elif different:
- eq = False
- else:
- pass # propagate from lower bits
- return eq
-
-
-class EqualLeadingZeroCount(Elaboratable):
- """checks if `clz(a) == clz(b)`.
-
- Properties:
- width: int
- the width in bits of `a` and `b`.
- a: Signal of width `width`
- input
- b: Signal of width `width`
- input
- out: Signal of width `1`
- output, set if the number of leading zeros in `a` is the same as in
- `b`.
- """
-
- def __init__(self, width):
- assert isinstance(width, int)
- self.width = width
- self.a = Signal(width)
- self.b = Signal(width)
- self.out = Signal()
-
- def elaborate(self, platform):
- # the operation is converted into calculation of the carry-out of a
- # binary addition, allowing FPGAs to re-use their specialized
- # carry-propagation logic. This should be simplified by yosys to
- # remove the extraneous xor gates from addition when targeting
- # FPGAs/ASICs, so no efficiency is lost.
- #
- # see `equal_leading_zero_count_reference` for a Python version of
- # the algorithm, but without conversion to carry-propagation.
- # note that it's possible to do all the bits at once: a for-loop
- # (unlike in the reference-code) is not necessary
-
- m = Module()
- both_ones = Signal(self.width)
- different = Signal(self.width)
-
- # build `both_ones` and `different` such that:
- # for every bit index `i`:
- # * if `both_ones[i]` is set, then both addends bits at index `i` are
- # set in order to set the carry bit out, since `cin + 1 + 1` always
- # has a carry out.
- # * if `different[i]` is set, then both addends bits at index `i` are
- # zeros in order to clear the carry bit out, since `cin + 0 + 0`
- # never has a carry out.
- # * otherwise exactly one of the addends bits at index `i` is set and
- # the other is clear in order to propagate the carry bit from
- # less significant bits, since `cin + 1 + 0` has a carry out that is
- # equal to `cin`.
-
- # `both_ones` is set if both have no leading zeros so far
- m.d.comb += both_ones.eq(self.a & self.b)
- # `different` is set if there are a different number of leading
- # zeros so far
- m.d.comb += different.eq(self.a ^ self.b)
-
- # now [ab]use add: the last bit [carry-out] is the result
- csum = Signal(self.width + 1)
- carry_in = 1 # both have no leading zeros so far, so set carry in
- m.d.comb += csum.eq(both_ones + (~different) + carry_in)
- m.d.comb += self.out.eq(csum[self.width]) # out is carry-out
-
- return m
-
-
def cldivrem_shifting(n, d, width):
""" Carry-less Division and Remainder based on shifting at start and end
allowing us to get away with checking a single bit each iteration
# of Horizon 2020 EU Programme 957073.
import unittest
-from nmigen.hdl.ast import AnyConst, Assert, Signal, Const, unsigned
+from nmigen.hdl.ast import Signal, Const, unsigned
from nmigen.hdl.dsl import Module
from nmutil.formaltest import FHDLTestCase
from nmigen_gf.hdl.cldivrem import (CLDivRemFSMStage, CLDivRemInputData,
CLDivRemOutputData, CLDivRemShape,
- cldivrem_shifting, CLDivRemState,
- equal_leading_zero_count_reference,
- EqualLeadingZeroCount)
+ cldivrem_shifting, CLDivRemState)
from nmigen.sim import Delay, Tick
from nmutil.sim_util import do_sim, hash_256
from nmigen_gf.reference.cldivrem import cldivrem
-class TestEqualLeadingZeroCount(FHDLTestCase):
- def tst(self, width, full):
- dut = EqualLeadingZeroCount(width)
- self.assertEqual(dut.a.shape(), unsigned(width))
- self.assertEqual(dut.b.shape(), unsigned(width))
- self.assertEqual(dut.out.shape(), unsigned(1))
-
- def case(a, b):
- assert isinstance(a, int)
- assert isinstance(b, int)
- expected = a.bit_length() == b.bit_length()
- with self.subTest(a=hex(a), b=hex(b),
- expected=expected):
- reference = equal_leading_zero_count_reference(a, b, width)
- with self.subTest(reference=reference):
- self.assertEqual(expected, reference)
-
- with self.subTest(a=hex(a), b=hex(b),
- expected=expected):
- yield dut.a.eq(a)
- yield dut.b.eq(b)
- yield Delay(1e-6)
- out = yield dut.out
- with self.subTest(out=out):
- self.assertEqual(expected, out)
-
- def process():
- if full:
- for a in range(1 << width):
- for b in range(1 << width):
- yield from case(a, b)
- else:
- for i in range(100):
- a = hash_256(f"eqlzc input a {i}")
- a = Const.normalize(a, dut.a.shape())
- b = hash_256(f"eqlzc input b {i}")
- b = Const.normalize(b, dut.b.shape())
- yield from case(a, b)
-
- with do_sim(self, dut, [dut.a, dut.b, dut.out]) as sim:
- sim.add_process(process)
- sim.run()
-
- def tst_formal(self, width):
- dut = EqualLeadingZeroCount(width)
- m = Module()
- m.submodules.dut = dut
- m.d.comb += dut.a.eq(AnyConst(width))
- m.d.comb += dut.b.eq(AnyConst(width))
- # use a bunch of Value.matches() and boolean logic rather than a
- # giant Switch()/If() to avoid
- # https://github.com/YosysHQ/yosys/issues/3268
- expected_v = False
- for leading_zeros in range(width + 1):
- pattern = '0' * leading_zeros + '1' + '-' * width
- pattern = pattern[0:width]
- a_has_count = Signal(name=f"a_has_{leading_zeros}")
- b_has_count = Signal(name=f"b_has_{leading_zeros}")
- m.d.comb += [
- a_has_count.eq(dut.a.matches(pattern)),
- b_has_count.eq(dut.b.matches(pattern)),
- ]
- expected_v |= a_has_count & b_has_count
- expected = Signal()
- m.d.comb += expected.eq(expected_v)
- m.d.comb += Assert(dut.out == expected)
- self.assertFormal(m)
-
- def test_64(self):
- self.tst(64, full=False)
-
- def test_8(self):
- self.tst(8, full=False)
-
- def test_3(self):
- self.tst(3, full=True)
-
- def test_formal_64(self):
- self.tst_formal(64)
-
- def test_formal_8(self):
- self.tst_formal(8)
-
- def test_formal_3(self):
- self.tst_formal(3)
-
-
class TestCLDivRemShifting(FHDLTestCase):
def tst(self, width, full):
def case(n, d):
projects / nmigen-gf.git / commitdiff