1 # SPDX-License-Identifier: LGPL-3-or-later

2 # Copyright 2022 Jacob Lifshay programmerjake@gmail.com

4 # Funded by NLnet Assure Programme 2021-02-052, https://nlnet.nl/assure part

5 # of Horizon 2020 EU Programme 957073.

7 """ Carry-less Division and Remainder.

9 https://bugs.libre-soc.org/show_bug.cgi?id=784

10 """

18 """checks if `clz(a) == clz(b)`.

19 Reference code for algorithm used in `EqualLeadingZeroCount`.

20 """

28 # `both_ones` is set if both have no leading zeros so far

30 # `different` is set if there are a different number of leading

31 # zeros so far

39 return eq

43 """checks if `clz(a) == clz(b)`.

45 Properties:

46 width: int

47 the width in bits of `a` and `b`.

48 a: Signal of width `width`

49 input

50 b: Signal of width `width`

51 input

52 out: Signal of width `1`

53 output, set if the number of leading zeros in `a` is the same as in

54 `b`.

55 """

65 # the operation is converted into calculation of the carry-out of a

66 # binary addition, allowing FPGAs to re-use their specialized

67 # carry-propagation logic. This should be simplified by yosys to

68 # remove the extraneous xor gates from addition when targeting

69 # FPGAs/ASICs, so no efficiency is lost.

70 #

71 # see `equal_leading_zero_count_reference` for a Python version of

72 # the algorithm, but without conversion to carry-propagation.

77 # `both_ones` is set if both have no leading zeros so far

79 # `different` is set if there are a different number of leading

80 # zeros so far

83 # build addend1 and addend2 such that:

84 # * if both_ones is set, then addend1[i] and addend2[i] are both

85 # ones in order to set the carry bit out.

86 # * if different is set, then addend1[i] and addend2[i] are both

87 # zeros in order to clear the carry bit out.

88 # * otherwise exactly one of addend1[i] and addend2[i] are set and

89 # the other is clear in order to propagate the carry bit from

90 # less significant bits.

93 # different is zero when both_ones is set, so we don't need to

94 # OR-in both_ones

96 ]

101 return m

103 # TODO: add CLDivRem