Von Neumann random bytes debiasing

Question

I need to create a method to debias biased bytes from the method get_raw_bytes(length) using von Neumann debiasing method.

Von Neumann method takes two bits at a time. If the input is 01 it will output 0, if the input is 10, it will output 1, if the input is 00 or 11, it won't output anything.

Example:

Raw      : [11010110, 11001001, 01101000]
Debiased : [00110011]

Here's my current code:

def get_raw_bytes(length):
    return open('/dev/hwrng', 'rb').read(length)


def get_debiased_bytes(length):
    arr_debiased_bytes = []
    debiased_byte = 0
    bit_counter = 0
    while len(arr_debiased_bytes) < length:
        raw_bytes = get_raw_bytes(length * 5)
        for byte in raw_bytes:
            for k in range(0, 8, 2):
                bit1 = byte >> k & 1
                bit2 = byte >> k + 1 & 1
                if bit1 != bit2:
                    debiased_byte = debiased_byte << 1 | bit1
                    bit_counter += 1
                    if bit_counter == 8:
                        arr_debiased_bytes.append(debiased_byte)
                        debiased_byte = 0
                        bit_counter = 0
    return bytes(arr_debiased_bytes[:length])

I think my code still can be improved and tidied up. Can anyone help me with this?

Answer 1

• In get_raw_bytes you should use with to close the file. Without using a with or .close the file is not guaranteed to close and so can cause problems depending on how nice Python is feeling on being to you.

  Don't leave bugs to change.

• The code is fairly good, but get_debiased_bytes is doing three things at once.

  1. Converting bytes (\$2^8\$) to crumbs (\$2^2\$).

     for byte in raw_bytes:
         for k in range(0, 8, 2):
             bit1 = byte >> k & 1
             bit2 = byte >> k + 1 & 1
     

  2. Debiasing the crumbs to bits.

     if bit1 != bit2:
         debiased_byte = debiased_byte << 1 | bit1
     

  3. Joining bits to bytes.

     debiased_byte = debiased_byte << 1 | bit1
     bit_counter += 1
     if bit_counter == 8:
         arr_debiased_bytes.append(debiased_byte)
         debiased_byte = 0
         bit_counter = 0
     

  Bundling all this together is making your code harder to read.

• When extracting the above functions I would use generator functions. This has a couple of benefits:

  1. In Python the iterator pattern has a lot of sugar.
  2. By using a generator we have more options on how to deal with the length. We can truncate the size on the input, or only take length amount of items from the sequence after it's been made.

• I'm not a fan of using byte >> k to get the bits / crumb.

  Since bit operators are not commonly used their order of precedence can be confusing. This doesn't help when you're mixing both bitwise and integer operators.

  By using this you're adding a requirement for naming k when there is no need.

• You can extract the nibble in a readable form by using byte & 0b11.

• The code to debiase the crumbs is smart, but not exactly readable.

  We know only two of the four states can yield data. And so just hard coding the values can allow people to just read the code and figure it out faster.

  By using the 0b prefix this can make the code really quite simple.

• The code for building the bytes is ok. It's fairly easy to read.

• The code for building the bytes can silently swallow data.

  I personally would not be a fan of this. Instead I would yield the byte regardless. There are two forms this can take, padding the bits on the left or right.

def bytes_to_crumbs(bytes):
    for byte in bytes:
        for _ in range(4):
            yield byte & 0b11
            byte >>= 2


def debiase_crumbs(crumbs):
    for crumb in crumbs:
        if crumb == 0b10:
            yield 1
        elif crumb == 0b01:
            yield 0


def bits_to_bytes(bits):
    """Just discard."""
    try:
        while True:
            byte = next(bits)
            for _ in range(7):
                byte <<= 1
                byte |= next(bits)
            yield byte
    except StopIteration:
        pass


def bits_to_bytes(bits):
    """Pad to the right - 1111000."""
    try:
        while True:
            byte = next(bits)
            for _ in range(7):
                byte <<= 1
                byte |= next(bits, 0)
            yield byte
    except StopIteration:
        pass


def bits_to_bytes(bits):
    """Pad to the left - 00001111."""
    try:
        while True:
            byte = next(bits)
            for _ in range(7):
                try:
                    bit = next(bits)
                except StopIteration:
                    yield byte
                    return
                byte <<= 1
                byte |= bit
    except StopIteration:
        pass


def get_debiased_bytes(length):
    with open('/dev/hwrng', 'rb') as f:
        _bytes = f.read(length)
    return bytes(bits_to_bytes(debiase_crumbs(bytes_to_crumbs(_bytes))))