Python indexing vs. bit indexing

[kubaraczkowski]

One feature that would be great with bitstring would be to be able to use 'normal bit indexing' (https://en.wikipedia.org/wiki/Bit_numbering).
All is nice for LSB-first data, but that's not default.
When having a MSB-first bitstring, index 0 goes to MSB, which is ... inconvenient. Sure, it is compliant with python indexing (like a list), but it's often not what you want to do when working with binary data.
For instance: "please give me bit 2 out of this byte of data" - in "bit indexing" it would be data[2](counting from 0!), but in bitstring (and python in general) you're forced to do data[5] (or generally data[len(data) - ix + 1]...

Would implementing a proper indexing for MSB-first data possible? Or am I missing something that's already in bitstring?

[scott-griffiths]

Bitstrings are always interpreted as MSB-first, so I'm assuming you're asking for indexing for LSB-first data.

Well you can use standard Python negative indices, so for LSB-first n you ask for data[-n-1] (much better and more Pythonic than using len(data)). It's a bit annoying that you need the -1 but it can't be avoided.

I've never been able to think of a good interface for LSB-first bitstrings. You could have a per-module or per-bitstring flag that says 'LSB-first', but then as well as indexing differences there are changes to many of the properties (uint etc.) and lots of other incidental changes which might cause confusion.

A few people have asked though, so perhaps I should give it a bit more thought.

[kubaraczkowski]

Well, you understand the trouble right ( data[-n-1] works, but the minus
and the -1 are indeed annoying), but I still think it's for MSB-first data,
not LSB-first.
12 is 1100 in MSB-first 4bit, can be annotated with bit numbers like:

bit : 1 1 0 0
bit number: 3 2 1 0

[0] of the '1100' will be the leftmost '1', but you're expecting the
rightmost 0 : that's the trouble.

Do you see now?

I'm guessing that this way of indexing would break the complete library and
all code that uses it though :/

On Wed, Feb 24, 2016 at 10:35 AM, Scott Griffiths notifications@github.com
wrote:

Bitstrings are always interpreted as MSB-first, so I'm assuming you're
asking for indexing for LSB-first data.

Well you can use standard Python negative indices, so for LSB-first n you
ask for data[-n-1](much better and more Pythonic than using len%28data%29).
It's a bit annoying that you need the -1 but it can't be avoided.

I've never been able to think of a good interface for LSB-first
bitstrings. You could have a per-module or per-bitstring flag that says
'LSB-first', but then as well as indexing differences there are changes to
many of the properties (uint etc.) and lots of other incidental changes
which might cause confusion.

A few people have asked though, so perhaps I should give it a bit more
thought.

—
Reply to this email directly or view it on GitHub
#156 (comment)
.

[scott-griffiths]

Ah OK, you're talking about the LSB 0 bit numbering you linked to, which isn't the same as LSB first.

MSB or LSB-first concerns the order of the bits in the bitstream, whereas MSB or LSB 0 refers to whether the first or last bit in the bitstream is the '0' bit.

So for unsigned integer 12: [This is mostly for my reference]:

MSB-first, MSB-0 (the default)
s = 1100
s[0] = 1

MSB-first, LSB-0
s = 1100
s[0] = 0

LSB-first, LSB-0
s = 0011
s[0] = 1

LSB-first, MSB-0
s = 0011
s[0] = 0

---

OK, no wonder everyone gets confused (myself included). So I think you want MSB-first, LSB-0.

So an 'LSB-0' mode wouldn't change any of the bitstring interpretations (uint, bin, hex, bytes etc.) but would only change slicing.

You would want s[0:3] for example to be the final three bits, but still MSB-first (and LSB-0) so it would be s[-3:].

Hmmm, so if a bitstring (or the module) has the new lsb0 flag set we change the meaning of indices in __getitem__ and __setitem__, but don't change any interpretations of the data.

So if you say s[0:3] = '0b001 it would change the bitstring from 1100 to 1001, i.e. the replacement bitstring is being given in the opposite direction to the way the index is counting... Not sure about that.

The change would also affect methods which can specify bit positions: all, any, cut, endswith, find, findall, rfind, split, startswith, byteswap, insert, invert, overwrite, replace, reverse, rol, ror and set. Phew.

Must be a better way...

[kubaraczkowski]

Right, exactly... Confusing as hell... and we did not even start on
endiannes :)
Indeed, MSB-first, LSB-0 is the 'natural' way.
See for example (just took whatever reference from a msp430 datasheet)
https://msuraj.files.wordpress.com/2011/10/bcs2.png

How are the bits defined? MSB-first, LSB-0. Datasheet says: bits 7-6 do
'something something'.
If you're writing a driver for it in C, you know by how much you need to
shift left your data to come in the right spot (6 in this case).
example:
binary_number |= (1<<6) - sets bit 6, but counting from right
In python (and bitstring) you select [0:2] which is, well, confusing. Not
super crazy if you talk about 2 first bits in a 8bit data, but if you need
to access bits 13 and 14 in 32bit word... super confusing.

No changes to internal interpretations indeed - everything python is
msb-first already, so that's fine.

On Wed, Feb 24, 2016 at 11:44 AM, Scott Griffiths notifications@github.com
wrote:

Ah OK, you're talking about the LSB 0 bit numbering you linked to, which
isn't the same as LSB first.

MSB or LSB-first concerns the order of the bits in the bitstream, whereas
MSB or LSB 0 refers to whether the first or last bit in the bitstream is
the '0' bit.

So for unsigned integer 12: [This is mostly for my reference]:

MSB-first, MSB-0 (the default)
s = 1100
s[0] = 1

MSB-first, LSB-0
s = 1100
s[0] = 0

LSB-first, LSB-0
s = 0011
s[0] = 1

LSB-first, MSB-0
s = 0011

s[0] = 0

OK, no wonder everyone gets confused (myself included). So I think you
want MSB-first, LSB-0.

So an 'LSB-0' mode wouldn't change any of the bitstring interpretations (
uint, bin, hex, bytes etc.) but would only change slicing.

You would want s[0:3] for example to be the final three bits, but still
MSB-first (and LSB-0) so it would be s[-3:].

Hmmm, so if a bitstring (or the module) has the new lsb0 flag set we
change the meaning of indices in getitem and setitem, but don't
change any interpretations of the data.

So if you say s[0:3] = '0b001 it would change the bitstring from 1100 to
1001, i.e. the replacement bitstring is being given in the opposite
direction to the way the index is counting... Not sure about that.

The change would also affect methods which can specify bit positions: all,
any, cut, endswith, find, findall, rfind, split, startswith, byteswap,
insert, invert, overwrite, replace, reverse, rol, ror and set. Phew.

Must be a better way...

—
Reply to this email directly or view it on GitHub
#156 (comment)
.

[scott-griffiths]

Cool, although my experience is that everyone disagrees about what the 'natural' and 'obvious' ways to do things are - it depends upon your field of interest.

So my other thought was that you might not expect s[0:3] to be the final three bits, it might be more natural to say s[2:]. For your 7 and 6 bits you would say s[7:5] rather than s[6:8]. So as we're labelling the bits backwards, to get a forwards slice you need the end number smaller than the start.

Which hurts my head a little, but probably less than the alternative.

So I think that is now back to replacing each index n with -n-1. So to get the 7 and 6 bits together you say s[7:5] which gets converted to s[-8:-6] which is correct. For a bit at position 0 you ask for s[0] which becomes s[-1]. For a reversed slice s[2:5:-1] this would become s[-3:-6:-1] which is again OK.

If you just wanted a way of using s[a:b:c] for LSB-0 I think the code would be fairly easy, but I'm not sure of the interface. You could use an ordinary method: s.getlsb0slice(a, b, c) but that's pretty ugly.

It could be a flag in the bitstring object, but that would get confusing when working with multiple bitstrings with different flags.

Or it could be a module wide flag (like bytealigned) so you just say bitstring.lsb0 = True and then it uses the new slicing algorithm. Probably this is the best option, but I'm not so keen on altering all the other methods although I suspect that some of them (but not all) will be using __getitem__ and __setitem__ themselves and so will need to be changed.

OK, that just about makes a sane feature request I think!

[kubaraczkowski]

Right, completely agree with you that using general statements like 'natural' and 'obvious' is completely useless here - just like choosing which 'endianness' is the correct one :)

I forgot to talk about the indexing example you've shown, I think it's not accurate.
lets have s = '0b1100' and replace s[0:3] by '001'. s explicitly is:

s[0] = 0
s[1] = 0
s[2] = 1
s[3] = 1

so 'unwrapping' the index [0:3] would bes[0:3] = s[0,1,2] = '001' => s[0]=0,s[1]=0,s[2]=1 which then results in (oh gosh, it gets tricky again) s = 0b1100 , same 12 :)

so the 'easier to understand' way of doing the slicing would be from left to right, not right to left:
s[3:0] = '100'. this way the 'replacement' is also msb-first lsb-0. The start of 3 is confusing again of course (thanks python...) In fact in sth low-level digital like verilog/vhdl/etc. you'd say s[2:0] = '100'

You're right that mixing two styles of indexing in one program would get very confusing.. so maybe a module-wide flag could be an option

[m-schubert]

I figured I'd just chime in here. I'm using bitstring for parsing of some registers on a system-on-module. I (incorrectly) assumed that index 0 would correspond to the LSB, as that is pretty standard across the electronic engineering world. I very rarely come across datasheets that reference bit 0 (or 1) as the MSB.

A modulewide flag to change the behaviour would be awesome.

[andrew-vant]

I had a need for this some time back and emailed Scott about it at the time. Since then I've mostly-solved my own problem by monkeypatching bitstring to add a .lbin interpreter/constructor arg, which does the same thing as .bin but reverses the bits in each byte; I can't say that's the best solution but it worked for me. It probably does strange things with slices.

I had a bit of an epiphany this morning about how these things come up:

FLAG0 = 0x01
FLAG1 = 0x02
FLAG2 = 0x04
FLAG3 = 0x08
FLAG4 = 0x10
FLAG5 = 0x20
FLAG6 = 0x40
FLAG7 = 0x80
# ...maybe more...

This seems like a pretty common pattern for packing multiple boolean values into a single byte. If the flags are mostly unrelated, it doesn't matter, but if the order is important somewhere else (e.g. something references flag #n rather than specifically FLAG4), you need LSB-0 indexing or things break.

I would expect this to be more common than the alternative in most binaries, though people tend to write MSB-first instead...presumably because that's how we write decimal numbers.

One peculiarity of my own case is that I sometimes have to deal with LSB-0 bitfields and sometimes MSB-0. I've yet to come across both in the same program run but I can't be sure it won't happen.

(another peculiarity is that I'm more concerned with the order that comes out of .bin rather than slicing order, but there are ways around that)

Thirding the request for this feature or something like it; my monkeypatch works but it's a bit of a wart.

[FlyingLotus1983]

I'd like to voice my support for this issue. I completely agree with @kubaraczkowski that the slicing format should be LSB=0. To @scott-griffiths point on Feb. 24, the display should stay as-is (MSB-first), but when slicing, 0 should return the LSB, and work their way towards the MSB when incrementing. I've not gotten into bit-shifting and other things yet, but I'm assuming they work as expected.

This is very much a standard (and some would say sacred) way of accessing bits across all of computer science.

I'm going to take a stab at modifying the backend code to support this, as I need the functionality this week :) No idea if it will be worthy of submitting a pull request, quality-wise. We'll see, I'm up for the challenge.

[florisla]

This functionality would be very valuable, but I would hate to see it directed by flags.

What do you think of exposing an LSB-0 accessor as a separate attribute next to bin, int and oct -- let's name it bits.

It could work like this:

>>> data = BitArray('0b0111')
>>> # get the LSBit (bit 0)
>>> data.bits[0]
True
>>> # get a range of bits: 2 down to 0 (three in total)
>>> data.bits[2:0]
0b111

So you have to be aware that this indexing works inversely compared to regular Python indexing, but that's exactly what we want to have.

One could debate whether '2:0' should include or exclude bit 0. Excluding it matches better to Python, whereas including it matches better with reading 2:0 as 'bit 2 down to 0'.

[florisla]

The above functionality actually uses very little code:

class Bits:

    def __init__(self, data):
        self.data = data

    def __getitem__(self, item):
        if isinstance(item, int):
            msb0_index = - item - 1
            return self.data[msb0_index]

        if isinstance(item, slice):
            start = - item.start - 1 if item.start is not None else None
            stop = - item.stop if item.stop else None
            return self.data[slice(start, stop, item.step)]

        raise ValueError("Expecting int or slice: {} ({})".format(
            item,
            type(item),
        ))



data = BitArray('0b0111')
# monkey-patch the 'bits' accessor into BitArray
BitArray.bits = Bits(data)

[robshep]

Hacked my own LSB extractor as a result of device data being packed in this manner.
This satisfies my requirements

def _subbits_lsb(bit_string, start_pos, num_bits, extract_fmt):
    """
    Take a string of bits (E.g. from BitStream(...).bin and extact uints reading from the right )
    :param start_pos: the start position, from the RIGHT, where RIGHT-most bit is position 0
    :param num_bits: the number of bits to collect, RIGHTWARDS
    :param extract_fmt: Bitstring read() format
    """
    f_pos = 0 - num_bits - start_pos
    e_pos = len(bit_string) - start_pos
    sub_bits = bit_string[f_pos:e_pos]
    print bit_string, sub_bits, f_pos, e_pos
    return BitStream(bin=sub_bits).read(extract_fmt)

Tests

assert _subbits_lsb('0001', 0, 2, 'uint') == 1
assert _subbits_lsb('110000', 4, 2, 'uint') == 3
assert _subbits_lsb('0011110000', 6, 3, 'uint') == 3
assert _subbits_lsb('0000101000000', 6, 3, 'uint') == 5

[daguren]

Except you mean "the number of bits to collect, LEFTWARDS".

[robshep]

Yes, It definitely does collect R/W, sorry. Dang copy and paste omission from the lefty version.

[scott-griffiths]

This is quite an old thread, but finally there is some movement.

I've just released 3.1.7, which has an experimental Least Significant Bit Zero mode. If anyone has any feedback please don't hesitate. From the release notes:

Experimental LSB0 mode

This feature allows bitstring to use Least Significant Bit Zero
(LSB0) bit numbering; that is the final bit in the bitstring will
be bit 0, and the first bit will be bit (n-1), rather than the
other way around. LSB0 is a more natural numbering
system in many fields, but is the opposite to Most Significant Bit
Zero (MSB0) numbering which is the natural option when thinking of
bitstrings as standard Python containers.

To switch from the default MSB0, use the module level function

>>> bitstring.set_lsb0(True)

Getting and setting bits should work in this release, as will some
other methods. Many other methods are not tested yet and might not
work as expected. This is mostly a release to get feedback before
finalising the interface.

Slicing is still done with the start bit smaller than the end bit.
For example:

>>> s = Bits('0b000000111')
>>> s[0:5]
Bits('0b00111')
>>> s[0]
True

Negative indices work as (hopefully) you'd expect, with the first stored
bit being s[-1] and the final stored bit being s[-n].

[andrew-vant]

I still have a need for this and I want to check it out and give feedback, but I'm booked for the next couple weeks. How long do you expect it to stay experimental before finalizing the interface?

[scott-griffiths]

Oh it will be at least a few weeks, quite possibly a couple of months. Only got round to it now because I had time off work and there's not much else to do! There are still a whole load of untested methods that use the start and end positions, plus BitStream methods that have the concept of a current bit position. So I need to write maybe 30 more tests and fix everything. I just noticed that even append/prepend which I thought were working aren't - I wrote the test the wrong way round. It's sometimes difficult to get used to LSB0.

[andrew-vant]

Okay, I had a look. Either something is still wrong, or we have different ideas about correct behavior.

I created a couple of Bits objects to test with, like this:

bitstring.set_lsb0(True)
one = bitstring.Bits(bytes([1]))             # One byte, unsigned integer 1
multi = bitstring.Bits(bytes([1, 2, 4, 8]))  # Four bytes representing uints

Then I tried a few variations on interpretation. It seemed mostly-right for the one-byte case, and mostly-wrong for the multi-byte case. Here and below, when I refer to bit #n I mean the nth-least-significant-bit of a given byte; when I refer to byte #n, I mean the nth byte of the bytes object passed to the constructor above:

value            expected  actual    comment
one.uint         1         1         Round trip check OK
one[0]           True      True      OK, first bit is LSB
one[:3][0]       True      True      OK, slicing starts from the same end as lookup
one.bin          10000000  00000001  ? First displayed bit is MSB. Same for `list(one)`
multi.bytes[0]   1         1         Round trip check OK
multi.bytes[-1]  8         8         Round trip check OK
multi[0]         True      False     ? Expected LSB of first byte, got...something else
multi[:8].uint   1         8         ? Expected first byte as uint, got last
multi[-8:].uint  8         1         ? Expected last byte as uint, got first
multi[3]         False     True      ? Expected bit 3 of first byte, got bit 3 of last byte
multi[3*8]       False     True      ? Expected LSB of byte 3, got LSB of byte 0
multi[:8].bin    n/a       00001000  ? Note lack of commutativity below
multi.bin[:8]    n/a       00000001  ?
multi[-8:].bin   n/a       00000001  ?
multi.bin[-8:]   n/a       00001000  ?

I can see an argument for the .bin string displaying in MSB order, so I'm less concerned about that, although I'd prefer something like 'lbin for LSB0 order, mbin for MSB0 order, bin for current-mode order'

It's the rest that confuses me. I haven't looked at the code, but it looks to me like the lsb0 mode now indexes bits like this -- assuming a four-byte bitstring created as bs = Bits(bytes(4)):

• bit 0 = byte 3 least-significant-bit
• bit 1 = byte 3 second-least-significant-bit
• ... ...
• bit 7 = byte 3 most-significant-bit
• bit 8 = byte 2 least-significant bit
• ...until we get to byte 0's most-significant-bit, which becomes bs[-1]

When I expected this:

• bit 0 = byte 0 least-significant-bit
• bit 1 = byte 0 second-least-significant-bit
• ... ...
• bit 7 = byte 0 most-significant-bit
• bit 8 = byte 1 least-significant-bit
• ...and so on.

That is, the new mode isn't just changing the indexing of bits-within-a-byte, it's changing the order of bytes within the stream. bs[8:16] != Bits(bs.bytes[1:2]) -- but should.

[andrew-vant]

I just noticed a concise way to define that last part:

• Current LSB0 behavior: Bit #N is the bit set by Bits(uintbe=2**n, ...)
• Expected LSB0 behavior: Bit #N is the bit set by Bits(uintle=2**n, ...)

(I think I have that right...[edit: note that I don't know if others in this thread had the same expectation])

Unrelated: indexing and iteration don't match. That is: [bs[i] for i in range(len(bs))] != [i for i in bs]. I'm guessing this has something to do with .bin and list(Bits) both producing items in msb0 order. I'm not sure how much of that is "experimental code is experimental" and how much is intended behavior, but it feels like a bug to me.

[scott-griffiths]

Yes, this is complex. Partly because some things are known not to work.

So we have one.bin = '00000001' and multi.bin = '00000001 00000010 00000100 00001000'

I think you may have had the expectation that on the creation of multi it may have reversed the bytes? Or reversed the whole bitstring? It's not going to do that. It's being initialised by a built in object which hasn't got any idea about how it should be interpreted

I won't go through every case as there are still bugs (notably here the uint interpretation), but some examples:

multi[:8] is the final 8 bits of multi (it takes bits from the right), so equals 00001000. This does =8 with LSB0

one.uint should actually be 128. The least significant bit is bit 0, and the uint interpretation read the whole bitstring and interprets it as an unsigned integer. So it reads a 1 first then 7 zeros, which is 128.

I wouldn't expect the commutativity you mention. Standard Python indexing is left-to-right, so when you use bin you convert to an ordinary Python string that can't possibly know that you want your next slice to be done the other way. So multi[:8].bin is the the first 8 bits of multi, which is the final 8 bits of the string at the top of this message. So that what you get when you convert it to a Python string with bin. multi.bin[:8] on the other hand converts first to the Python string of the whole bitstring and the takes a slice of that string.

Hope that makes sense ! I think that is all OK (except for interpretation bugs), but good to run through sanity checks. Feel free to argue though!

Thanks.

[andrew-vant]

Pardon the delay again. We still have a disconnect, but I think I've figured out what it is. I think this part shows that we have very different assumptions about what 'lsb0 mode' should do:

one.uint should actually be 128...

...because that seems very wrong to me, and I want to make sure I understand you correctly. Disclaimer: everything below here is me trying to guess what you're thinking; if I'm wrong, correct me:

value_in = 1
value_out = Bits(bytes([value_in])).uint
# does value_in == value_out?

It seems obvious to me that the value I get out should be the same as the value I put in -- after all, I haven't changed it.

But 128 is what you would get if you reversed the significance of the bits, and I think that might be where our disconnect is. When I refer to lsb0, I'm talking about the order in which bits are indexed, sliced, and iterated. Not which bit in a given byte is most or least significant, but which bit is labeled as bit '0'.

Based on the example above, it looks like you expect 'lsb0 mode' to reverse the significance of the bits themselves -- changing not their labeling, but their interpretation. That's not what I wanted, and it's not how I interpret the relevant section of wikipedia (sorry, I couldn't find a better source).

Have I understood you so far? I'm happy to argue about correct behavior, but I want to make sure I'm arguing against the right thing.

[tthommes]

Hi, I just read through this thread and I greately appreciate the LSB0 indexing-mode.

The last few posts might have introduced some confusion though... From my view (as I am a Computer-Engineer) the bit-indexing and uint-conversion (assuming big-endian meaning most significant byte first) are just fine as expected! Especially one.uint == 1 is the correct interpretation here. (Although we have LSB0 indexing this does not mean that the usual arithmetic number representation of least significant digit being displayed at the right should be reversed.)

What @andrew-vant might have expected is multi = Bits(bytes([1,2,4,8])) interpreting the bytes-object as little-endian... → So the question should be whether there is a possibility to configure the endianness of conversion from and to bytes object?

[qxzkjp]

Hi, I've just run into this issue while trying to read gzip bitstreams with this library. I'd like to say that I agree (I think) with Andrew, that reversing the order of the bytes is not what is expected, although my reasons are a bit different.

A string of bytes does not have an "endianness", that only exists when it's converted to/from an integer. A string of bytes has exactly one expected direction, going from the 0th byte to the nth. So if I write 'b\x11\x22\x33' to a BitStream, it should give me the exact same result as writing b'\x11' then b'\x22' and then b'\x33'. This is regardless of whether we are lsb0 or msb0, or any other condition. It comes directly from the definition of a byte string (in the abstract CS sense). Having it work any other way is unexpected and very unlikely to be helpful.

As it is now, the changes work perfectly if I append one byte at a time. Exactly as expected. But if I write more than one byte at once, the byte string is reversed. This has a direct performance impact and a direct dev frustration impact. The way that lsb0 currently works also likely has a performance impact for appending, because internally the strings are being prepended (which is usually slower, but I've not benchmarked it).

If that's still not clear (I don't blame you if so), here's a section from RFC 1952 that explains the common programming convention:

Bytes stored within a computer do not have a "bit order", since
they are always treated as a unit.  However, a byte considered as
an integer between 0 and 255 does have a most- and least-
significant bit, and since we write numbers with the most-
significant digit on the left, we also write bytes with the most-
significant bit on the left.  In the diagrams below, we number the
bits of a byte so that bit 0 is the least-significant bit, i.e.,
the bits are numbered:

   +--------+
   |76543210|
   +--------+

This document does not address the issue of the order in which
bits of a byte are transmitted on a bit-sequential medium, since
the data format described here is byte- rather than bit-oriented.

Within a computer, a number may occupy multiple bytes.  All
multi-byte numbers in the format described here are stored with
the least-significant byte first (at the lower memory address).
For example, the decimal number 520 is stored as:

       0        1
   +--------+--------+
   |00001000|00000010|
   +--------+--------+
    ^        ^
    |        |
    |        + more significant byte = 2 x 256
    + less significant byte = 8

Would you be open to a PR that demonstrates the "correct" way?

[scott-griffiths]

Version 4.0 now has documented lsb0 support, although I've still put a beta tag on it as there are still likely to be issues when using streaming methods in some cases. I think most use cases will be working though, so I'm closing this issue as done, and any new bugs can be reported as new issues.

Thank you all for your patience and comments on this.