# Von Neumann random bytes debiasing

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):

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?

• Please provide a specification for your code. Questions should be able to stand on their own as much as possible, so telling us about the Neumann method in your own words would help.
– Mast
Apr 18, 2020 at 15:13
• Please include the definition for get_raw_bytes as well.
– Mast
Apr 18, 2020 at 15:14
• And, assuming bytes is actually a function, that as well.
– Mast
Apr 18, 2020 at 15:14
• @Mast I've added get_raw_bytes definition. bytes is Python's built-in function to convert an array of 8-bit integers into bytes data type. Apr 18, 2020 at 16:41
• Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers.
– Mast
Apr 19, 2020 at 14:10

• 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


• 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):
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:
return bytes(bits_to_bytes(debiase_crumbs(bytes_to_crumbs(_bytes))))

• debias_crumbs can be streamlined: if crumb in [1, 2]: yield (crumb - 1). Sorry for (mis)formatting.
– vnp
Apr 19, 2020 at 7:16
• @vnp I agree that that's smart, and IMO more readable than the OP's. But I really don't think it's as readable as the code I've provided. (the formatting is fine :) Apr 19, 2020 at 11:27