Writing bitfields with varying field lengths

[Bengt Richter]

On Mon, 18 Aug 2003 23:32:49 GMT, Grumfish <nobody at nowhere.com> wrote:

>In order to familiarize my self with Flash files and their bytecode I've 
>started to make an assembler. My first problem is writing the bitfields 
>the format uses often. It is a series of fields, each can be a different 
>number of bits, combined into the least amount of bytes possible. Extra 
>bits in the last byte are padded with zeros. I would like to make a 
>function that takes a size and value for each field needed, calculate 
>the amount of needed bytes, place the values, and the nretun a binary 
>string of the resulting bitfield. I am at a complete loss on how to 
>place the values into the field. I've Googled but have found nothing 
>helpful. Can anybody help?
>
Well, a Python integer or long can hold a large number of bits, so your
problem is just how to specify a narrow field. The simplest thing is probably
just to use tuples to specify bits in an integer, and how many you mean
in the other  element of the tuple, e.g., (bit_integer, number_of_bits),
or (bi,nb) for short. You could then give some opcode and flagbit constants
names, e.g.,

    FROOBLE  = (0x13, 5)
    FROZ_ON  = (0X1, 1)
    FROZ_OFF = (0x0, 1)
    FRAZZLE  = (0xff1, 12)

Then if you wanted to pack those into a single bit sequence with FROOBLE at
the most significant end and FRAZZLE at the least, thus:
     
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |1 0 0 1 1|1|1 1 1 1 1 1 1 1 0 0 0 1|
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     \frooble/ ^  \______frazzle________/
               |
               +-froz_on

you could write a packer, that takes the list and returns a single combined tuple, e.g.,
...(later...) actually, why not a Bitfield class that will show interactively and
that you can just add to join bitfields? E.g., (hot out of the kitchen, not very tested)

====< bitfield.py >=======================================================
class Bitfield(tuple):
    """Instantiate by Bitfield() for Bitfield(0,0), or Bitfield(bitdata, nbits)"""
    def __new__(cls, *args):
        if not args: args = (0,0)   #default zero width bitfield
        return tuple.__new__(cls, args)
    def __repr__(self):
        bits, nb = self
        return '<BF[%d]:%r>'%(nb,''.join([chr(48+((bits>>(nb-1-i))&1)) for i in xrange(nb)]))
    def __add__(self, *others):
        """Add another bitfield or sequence of bitfield objects"""
        if others and not isinstance(others[0], Bitfield): others = others[0]
        combo, totb = self
        for bf, nb in others:
            combo = (combo<<nb)|(bf&((1L<<nb)-1)) # or just (bits<<nb)|bf if bf value trusted
            totb += nb
        return Bitfield(combo, totb)
    def rpadto(self, align):
        frag = self[1]%align
        if frag==0: return self
        return self + Bitfield(0,align-frag)
    def lpadto(self,align):
        frag = self[1]%align
        if frag==0: return self
        return Bitfield(0,align-frag)+self

FROOBLE  = Bitfield(0x13, 5)
FROZ_ON  = Bitfield(0x1, 1)
FROZ_OFF = Bitfield(0x0, 1)
FRAZZLE  = Bitfield(0xff1, 12)

def test():
    # example use:
    bf_seq = [FROOBLE, FROZ_ON, FRAZZLE]
    print 'bf_seq:', bf_seq

    combined_bitfield = Bitfield() + bf_seq
    print 'combined_bitfield:', combined_bitfield

    bf, nbits = combined_bitfield
    # pad to an even byte on the right, if desired, e.g.,
    right_padded = combined_bitfield.rpadto(8)
    left_padded =  combined_bitfield.lpadto(8)
    print 'right_padded:', right_padded
    print ' left_padded:', left_padded

if __name__ == '__main__':
    test()
==========================================================================
Oop, forgot to docstring rpadto and lpadto, but they obviously pad on
respective sides to make the full width a multiple of the specified alignment
width.

The test gives this result:

bf_seq: [<BF[5]:'10011'>, <BF[1]:'1'>, <BF[12]:'111111110001'>]
combined_bitfield: <BF[18]:'100111111111110001'>
right_padded: <BF[24]:'100111111111110001000000'>
 left_padded: <BF[24]:'000000100111111111110001'>

If we spread the combined bits out so we can compare, we get

<BF[18]:
    '1 0 0 1 1 1 1 1 1 1 1 1 1 1 0 0 0 1'>
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |1 0 0 1 1|1|1 1 1 1 1 1 1 1 0 0 0 1|
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     \frooble/ ^  \______frazzle________/
               |
               +-froz_on


You can play with this interactively, e.g.,

 >>> import bitfield
 >>> BF = bitfield.Bitfield # for short
 >>> BF() # zero width field
 <BF[0]:''>
 >>> BF() + BF(0xa,4)
 <BF[4]:'1010'>
 >>> BF() + BF(0xa,4)+ BF(07,3)
 <BF[7]:'1010111'>
 >>> BF() + BF(0xa,4)+ BF(07,3)+BF(0,1)
 <BF[8]:'10101110'>
 >>> byte = BF() + BF(0xa,4)+ BF(07,3)+BF(0,1)
 >>> byte
 <BF[8]:'10101110'>
 >>> bits, nb = byte
 >>> hex(bits)
 '0xAEL'
 >>> nb
 8
 >>> byte
 <BF[8]:'10101110'>
 >>> BF(-1, 5)
 <BF[5]:'11111'>
 >>> BF(-1, 0)
 <BF[0]:''> 

HTH

Regards,
Bengt Richter