Fix Bits-slices value assignment

[hawajkm]

The problem arises because of the way the the values checked when a value is assigned to a Bits object. To better explain this, we need to consider how Bits handle value assignments. Bits class handle different value assignment in two different way: Positive Values and Negative Values. Since Bits is unsigned, positive values are treated as unsigned while negative values are treated as signed two's complement.

When a positive value is assigned to a Bits object or a slice of it, the class checks whether the value would overflow given the available number of bits considering the value to be unsigned binary. Therefore, Bits class has two different definition of the Maximum and Minimum value to be assigned as seen in the following lines: Bits.py:38-39

Checks in Bits class happens at multiple times with two different ways: either using _max and _min object attribute, or using _get_nbits() to inspect if the value can fit in the limited bits the object has.

The problem with this approach is that the check using _max and _min is conclusive and always correct as the boundary are well studied, However, the check using number of bits is flimsy as it uses bit_length() native function of the int class of Python. The symantx of bit_length() is detailed in the following page: int.bit_length()

To quote:

Return the number of bits necessary to represent an integer in binary, excluding the sign and leading zeros

The problem happens when we deal with negative numbers. In that sense, bit_length() becomes problematic as in cases where the value is a perfect exponentiation of 2, then the sign bit is implicitly included in the number of bits returned by bit_length(); therefore, finding the actual number of bits by just using bit_length() becomes dirty as more code needs to be added to check whether the number of bits needs to be incremented or not. Therefore, it is cleaner to re-write the routine to implement the logic we want. In that logic, we determine the number of bits for positive numbers as if they were unsigned and thus the equation becomes: math.ceil( math.log( value + 1, 2 ) )

Where is the number is negative, we use the following equation math.ceil( math.log( abs( value ), 2 ) ) + 1

Working the math for the above is straight-forward.

The last point that this pull-request fixes is how single-bit slices/Bits objects are dealt with; if we assume that the assigned values are dealt with the same logic outlined above, then it is possible that a negative value assignment could produce the same positive value assignment as the positive value is unsigned while the negative number is 2's complement signed number. Therefore, for single bits objects, the range will be from -1 to 1; -1 in 1 bit number is basically: 0b1

While unsigned 1 in 1 bit is also: 0b1

As a result, to keep things consistent and adherent to a logic, the changes in the pull request implements a strict logic of treating positive values as unsigned and negative as 2's complement values; this fixes bugs that seem to be caused by the different logic of treating both the positive and negative values.

Finally, the pull request introduces test cases that test the tests the outlined inconsistencies as well as fixes cases that tests the logic of assigning value of -1 to a Bits object of size of 1 bit. However, these test cases enforces behaviors that does not confine to any of the other logic.

[cbatten]

I wonder what the impact on performance would be ... I am worried the ceil/log will be expensive. Another good reason to write Bits in RPython ...

[hawajkm]

That is an excellent point!

In all my implementations, I include a set of standard functions. One of them is a fast implementation of clog2 similar to standard Verilog clog2. Maybe we should invest some effort in introducing clog2 to PyMTL with optimized implementation?

Knowing that we will perform ceiling, the log operation can be performed without Taylor's series expansion making it cheap and lightweight.

[hawajkm]

Quick update!

I performed performance tests for both ceil/log and bit_length() and here is what I have got

For bit_length():

>>>timeit.timeit('import random; import math; int( random.randrange(0, 1 << 32) ).bit_length()', number=1000000)
3.721266984939575

For ceil/log:

>>> timeit.timeit('import random; import math; int( math.ceil( math.log( random.randrange(0, 1 << 32), 2 ) ) )', number=1000000)
4.359133005142212

I am disappointed and quiet surprised. I am disappointed that ceil/log is not of the same performance; but, at the same time, I am surprised that they are close.