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.

73 # note that it's possible to do all the bits at once: a for-loop

74 # (unlike in the reference-code) is not necessary

80 # build `both_ones` and `different` such that:

81 # for every bit index `i`:

82 # * if `both_ones[i]` is set, then both addends bits at index `i` are

83 # set in order to set the carry bit out, since `cin + 1 + 1` always

84 # has a carry out.

85 # * if `different[i]` is set, then both addends bits at index `i` are

86 # zeros in order to clear the carry bit out, since `cin + 0 + 0`

87 # never has a carry out.

88 # * otherwise exactly one of the addends bits at index `i` is set and

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

90 # less significant bits, since `cin + 1 + 0` has a carry out that is

91 # equal to `cin`.

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

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

96 # zeros so far

99 # now [ab]use add: the last bit [carry-out] is the result

105 return m

107 # TODO: add CLDivRem