Bit-packed GF2

[amirebrahimi]

Hi Matt,

We've been using GF2 for a project and it's been quite useful, but have since needed to move to bit-packing for performance reasons. Is this something you've ever thought about adding or would want to have included in the package (only for GF2 specifically). We have a few routes we can move forward with, such as rolling our own package or possibly contributing some work back to Galois, so I figured I'd ask.

Cheers,
Amir

[mhostetter]

Hey Amir, thanks for reaching out. I did something similar with bit-packing GF(2) arrays in the past. What kinds of operations do you desire with a bit-packed array? Simple addition and multiplication? Or more complex things like matrix multiplication?

I can see a use-case here. There would probably need to be a separate class, perhaps GF2BitPacked or GF2Packed? Supporting addition and multiplication is easy, but some other operations are trickier and would require custom ufuncs. I think adding something like this could be useful to the library.

[amirebrahimi]

As far as a separate class, it would be ideal if bitpacked=True could be passed instead of creating a whole separate class and just have the internals handled differently in that case. If it must be a separate class, I'd assume we could inherit from GF2?

[mhostetter]

Every type of field is a unique FieldArray subclass. So GF = galois.GF(7) returns a new class that defines the arithmetic for that field. That way x.view(GF) will work as intended. The bit-packed GF(2) class will need to be separate from the conventional GF(2) class because the ufuncs will differ. We can, however, make the API convenient. So GF = galois.GF(2, bitpacked=True) is easy enough. But technically that would return a different class than GF = galois.GF(2).

What types of dtypes do you desire support for? Just uint8 or all unsigned integers?

I'm trying to understand how the bit-packing would work with > 1D arrays. For instance, with matrix multiplication, can you give me an example of the dimensions of the arrays and the number of packed bits?

For instance, below is a 2x1 array of uint8s. Would you consider this a 2x8 conventional (non-packed) matrix?

In [3]: x = np.array([[0b01001100], [0b11100010]]); x
Out[3]: 
array([[ 76],
       [226]])

How would you multiply a conventional 8x3 matrix to this one? It needs 8 rows, which is easy. But it also needs 3 columns. How would a bit-packed array with uint8s have 3 columns, since each element contains 8 values?

Maybe I'm missing something obvious...

[amirebrahimi]

I think uint8 is sufficient. Possibly bool, too.
We'd follow the same convention as np.packbits, which pads the arrays to full bytes by adding 0s.
Unfortunately, for matrix multiplication we'd still incur a hit with unpacking bits.

[mhostetter]

I think that sounds good. Potentially we can intercept the call to np.packbits() such that GF2 instances passed into np.packbits() are returned automatically as GF2Packed instances. The same could be done for np.unpackbits().

If you all are interested in submitted a PR, I'm open to adding this to the library. I can provide some pointers on where I think functionality will need to be added.

[oscarhiggott]

I'd also find it useful if there was an option for GF2 to be bitpacked. Would row operations e.g. in GF2.row_reduce be vectorised, and if so would it also make sense to support bitpacking into 64-bit integers to improve performance?

[amirebrahimi]

Sounds good. We haven't started on this work yet, so we are open to any pointers you wish to provide.