Add bitarray implementation to eliminate external dependency #265

mndza · 2021-01-24T15:28:57Z

This PR is an attempt to address #179. This bitarray implementation follows the interface established by glasgow.support.bits while changing the backing storage to an array() object. Currently the element size of this array is a byte and not a machine word.

I am not particularly happy with the byte_reverse / byte_reversed method names to imply in-place modification or not. Also, I am not sure about the correct behavior in those functions when the number of stored bits is not a multiple of the byte size. Right now it drops the bits that exceed the bit length after the byte reversal.

Please note that for initializing the bitarray from a bytes object you need to provide the explicit length in bits. This is because I copied the constructor interface from glasgow.support.bits, but I do not know if that is the desired operation.

Most of the test cases were copied from glasgow.support.bits.

Great performance gain compared to the previous direct approach

attie

@mndza thanks very much for doing this!

I've had a rummage, and found a few issues - sorry!

... this should be a "request changes" review, I'm still learning GitHub's interface.

attie · 2021-01-26T22:16:48Z

software/glasgow/support/bitarray.py

+    def setall(self, value):
+        value_int = ~(-1 << self._len_) if bool(value) else 0
+        value_bytes = value_int.to_bytes(len(self._array_), "little")
+        self._array_ = array('B', value_bytes)


This implementation makes me nervous as it stands...

It seems to work with absurdly large integers, but did I just not go high / complex enough?

I still haven't found a way to do it faster than this. Regarding your concern, this code should in fact work for arbitrarily large numbers, as Python's int implementation is only limited by the amount of available memory.

I also tried some other approaches. The following runs at least 10x slower in my machine, testing with 1GiB bitarray:

def setall(self, value): byte = 0xFF if bool(value) else 0 self._array_ = array('B', bytes(byte for _ in range(len(self._array_)))) if self._len_ % 8: self._array_[-1] &= ~(-1 << (self._len_ % 8))

software/glasgow/applet/display/pdi/__init__.py

software/glasgow/applet/program/xc6s/__init__.py

attie · 2021-01-26T22:19:14Z

software/glasgow/protocol/jesd3.py

-        self.fuse = bitarray(int(count, 10), endian="little")
+        self.fuse = bitarray(0, int(count, 10))


Again re avoiding changes...

Do you handle endianness at all at the moment? Is it important?

Regarding endianness, the class currently only works in "little-endian" mode: least significant bytes are stored at the smallest address, and bits are ordered from LSB to MSB inside a byte. This is also consistent with glasgow.support.bits.

I am not sure if this is a problem though.

Endianness should emphatically not be a property of the new bitarray class. However, it must be possible to specify endianness when serializing/deserializing to/from buffer objects. E.g. SPI and JTAG have opposite endianness and we are actually going to hit this when working on gateware.

However, I can see that glasgow.support.bits does not have a way to do so. It's fine to extend both of them at the same time in a different PR, provided that existing bitarray-using code can be ported as it is.

software/glasgow/protocol/jesd3.py

software/glasgow/support/bitarray.py

attie · 2021-01-26T23:26:29Z

software/glasgow/support/bitarray.py

+    def byte_reverse(self):
+        """ In-place byte reversal """
+        if not hasattr(self.byte_reverse, "table"):  # only build once
+            self.byte_reverse.__func__.table = self.__build_revbyte_table()
+        table = self.byte_reverse.table
+        for i in range(len(self._array_)):
+            self._array_[i] = table[self._array_[i]]
+        if self._len_ % 8:
+            self._array_[-1] &= ~(-1 << (self._len_ % 8))
+        return self
+
+    def byte_reversed(self):
+        new = self.__class__(self._array_, self._len_)
+        return new.byte_reverse()
+
+    def reversed(self):
+        if self._len_ % 8:
+            # Adding zero padding in the low bits allows easier bit reversal
+            # for the cases where bit length is not multiple of byte size
+            out = self.__class__(0, 8-(self._len_%8)) + self
+        else:
+            out = self.__class__(self._array_, self._len_)
+        out._array_.reverse()   # Reverse byte order (last to first)
+        out.byte_reverse()      # Reverse bit order in every byte
+        out._len_ = self._len_  # Truncate possible length extension due to padding
+        return out


The distinction between bitarray.byte_reverse(), bitarray.byte_reversed() and bitarray.reversed() is very subtle on first glance... perhaps a comment?

Also, some don't behave properly, or observe self._len_ properly: 😬

>>> x = bitarray.from_bytes(b'abc', 8*4) >>> x bitarray('00000000011000110110001001100001') >>> x.byte_reverse() bitarray('00000000110001100100011010000110') >>> x.byte_reversed() bitarray('00000000011000110110001001100001') >>> x.reversed() bitarray('00000000011000010110001001100011')

Yes, I know the distinction is not very clear (see my original PR message). I will add some docstrings, but maybe we could remove one of the methods (byte_reverse() or byte_reversed()) ?

The wrong result in reversed() was caused by the bug fixed in b99b66f.

Regarding self._len_:

In reversed(), self._len_ is used to determine how much padding should be added before the actual reverse process. Not seeing the problem here.

In byte_reverse() / byte_reversed(), entire bytes are reversed, so the only thing I do when self._len_ is not multiple of 8 is mask the final byte. I also stated my doubts about the correct operation here in the original PR. Could you explain what behavior are you expecting in this case? Then I may modify the method to comply.

since commit b99b66f this assertion is redundant

whitequark · 2021-01-29T02:50:13Z

software/glasgow/support/bitarray.py

+
+    def __bitop(self, other, op, clear_top=False):
+        other = self.__class__(other)
+        # Only perform operation in-place when the other bitarray is smaller


This seems like a wrong condition to pick between mutating and copying operations.

What would be the proper response when other's bit length is larger? Maybe raise an exception like @attie (#265 (comment)) mentioned? If so, should that only happen for the in-place / mutating operations?

Changed the behavior in commit ffc277a

whitequark

Thank you for your contribution. Unfortunately, while the basic approach to the task was sound, this particular implementation includes a substantial degree of complexity (e.g. the __copy_bit_slice method) and numerous issues (see inline comments), and as a result I cannot convince myself that we should merge it. Again unfortunately, I also do not expect that I will have the review bandwidth necessary to bring this implementation to the point where it would be mergeable.

I apologize for causing you to spend your time in this way. I think that some of the code in this PR could be reused by a future developer handling the same task, so hopefully it will have some utility in the end.

mndza · 2023-07-25T15:42:55Z

I do agree with you: looking at this code now (it's been a while) and I'm not happy with it. I should have targeted for simplicity and correctness first. My apologies.

whitequark · 2023-07-26T03:06:09Z

Thank you for understanding. I'm happy to work with you on any future contributions, if you would like to.

mndza added 4 commits January 24, 2021 16:21

bitarray: initial implementation, eliminate dependency

0b2b56c

bitarray: consistent naming in object creation

40be04d

avoid some internal copies to improve performance

54b1511

bitarray: reverse bytes using lookup table

a2ed4ee

Great performance gain compared to the previous direct approach

attie reviewed Jan 26, 2021

View reviewed changes

mndza added 8 commits January 27, 2021 12:37

bitarray: fix bug allowing out-of-bounds access, check index

0cc3898

bitarray: fix &, |, ^ methods when other bitarray is larger

78e0654

bitarray: extra brackets for clarity

42ee9a6

bitarray: fix from_bytes creation when length exceeds value length

b99b66f

bitarray: fix reversed index error exception message between set and get

b95bb60

bitarray: rename internal method __slice_bits to __copy_bit_slice

1469130

bitarray: remove redundant assertion

db075e0

since commit b99b66f this assertion is redundant

bitarray: more brackets

20a6de0

whitequark reviewed Jan 29, 2021

View reviewed changes

mndza added 3 commits February 15, 2021 16:50

bitarray: in-place bit operations do not mutate length

ffc277a

bitarray: improve comments in __copy_bit_slice

529963e

bitarray: remove reference to python3-bitarray in README.md

db5f4d3

Base automatically changed from master to main February 27, 2021 09:59

Merge branch 'GlasgowEmbedded:main' into builtin-bitarray

f6d757b

whitequark requested changes Jul 1, 2023

View reviewed changes

whitequark closed this Jul 1, 2023

peterzieba mentioned this pull request Aug 7, 2023

Fixed small bug where jesd3.py would not see that the default fuse state was in fact set. whitequark/prjbureau#13

Merged

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Add bitarray implementation to eliminate external dependency #265

Add bitarray implementation to eliminate external dependency #265

mndza commented Jan 24, 2021 •

edited

attie left a comment •

edited

attie Jan 26, 2021

mndza Jan 27, 2021

attie Jan 26, 2021

mndza Jan 27, 2021

whitequark Jan 29, 2021

whitequark Jan 29, 2021

attie Jan 26, 2021

mndza Jan 27, 2021 •

edited

whitequark Jan 29, 2021

mndza Jan 29, 2021 •

edited

mndza Feb 15, 2021

whitequark left a comment

mndza commented Jul 25, 2023

whitequark commented Jul 26, 2023

		self.fuse = bitarray(int(count, 10), endian="little")
		self.fuse = bitarray(0, int(count, 10))

Add bitarray implementation to eliminate external dependency #265

Add bitarray implementation to eliminate external dependency #265

Conversation

mndza commented Jan 24, 2021 • edited

attie left a comment • edited

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

mndza Jan 27, 2021 • edited

Choose a reason for hiding this comment

Choose a reason for hiding this comment

mndza Jan 29, 2021 • edited

Choose a reason for hiding this comment

Choose a reason for hiding this comment

whitequark left a comment

Choose a reason for hiding this comment

mndza commented Jul 25, 2023

whitequark commented Jul 26, 2023

mndza commented Jan 24, 2021 •

edited

attie left a comment •

edited

mndza Jan 27, 2021 •

edited

mndza Jan 29, 2021 •

edited