3
\$\begingroup\$

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?

\$\endgroup\$
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – Mast Apr 18 at 15:13
  • \$\begingroup\$ Please include the definition for get_raw_bytes as well. \$\endgroup\$ – Mast Apr 18 at 15:14
  • \$\begingroup\$ And, assuming bytes is actually a function, that as well. \$\endgroup\$ – Mast Apr 18 at 15:14
  • \$\begingroup\$ @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. \$\endgroup\$ – Andika Wasisto Apr 18 at 16:41
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Mast Apr 19 at 14:10
2
\$\begingroup\$
  • 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))))
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ debias_crumbs can be streamlined: if crumb in [1, 2]: yield (crumb - 1). Sorry for (mis)formatting. \$\endgroup\$ – vnp Apr 19 at 7:16
  • \$\begingroup\$ @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 :) \$\endgroup\$ – Peilonrayz Apr 19 at 11:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.