How to use bitwise operators on raw binary data in Python for a CRC check?

Question

It's the first time I use bitewise operators and raw binary data in Python and I'm struggling to code a CRC check as defined in a documentation.

The documentation define the CRC check in pseudo-code like this:

GENERATOR = 1111111111111010000001001

MSG = binary("8D4840D6202CC371C32CE0576098")  # total 112 bits

FOR i FROM 0 TO 88:                           # 112 - 24 parity bits
  if MSG[i] is 1:
    MSG[i:i+24] = MSG[i:i+24] ^ GENERATOR

CRC = MSG[-24:]                               # last 24 bits

IF CRC not 0:
  MSG is corrupted

So far I've coded this:

adsb_hex = "8D4840D6202CC371C32CE0576098"
adsb_dec = int(adsb_hex, 16)
adsb_bin = bin(adsb_dec)[2:].zfill(8)

generator = 0b1111111111111010000001001

adsb_bin_list = [int((adsb_dec >> bit) & 1) for bit in range(112 - 1, -1, -1)]

check = []
for i in range(88):
    curr_bit = adsb_bin_list[i]
    if curr_bit is 1:
        check[i:i+24] = int(adsb_bin_list[i:i+24]) ^ generator

crc = check[-24:]

I don't know the Pythonic way to correctly do:

MSG[i:i+24] = MSG[i:i+24] ^ GENERATOR

CRC = MSG[-24:]

How can I do it correctly, the Pythonic way?

i think you probably need to convert int to str in statement check[i:i+24] = int(adsb_bin_list[i:i+24]) ^ generator — Azat Ibrakov
– Azat Ibrakov, Commented Jul 24, 2018 at 16:06

WorldSEnder · Accepted Answer · 2018-07-25 03:49:31Z

1

If you can use libraries, I recommend searching for your favorite bitstring/bitvector library. For example, using BitVector==3.4.8 you could write

from BitVector import BitVector

generator = BitVector(bitstring='1111111111111010000001001')
crc_length = len(generator) - 1

def compute_crc(message : BitVector) -> BitVector:
    content_length = len(message) - crc_length
    # to encode a message, you pad it with 0
    # to decode, you pass in the message with the crc appended
    assert content_length >= 0
    # operate on a copy of the data
    message = message.deep_copy()
    for i in range(content_length):
        if message[i]:
            message[i:i + len(generator)] ^= generator
    return message[-crc_length:]

if __name__ == "__main__":
    adsb_hex = "8D4840D6202CC371C32CE0576098"
    adsb_crc = compute_crc(BitVector(hexstring = adsb_hex))

answered Jul 25, 2018 at 3:49

WorldSEnder

5,1063 gold badges33 silver badges68 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

AlexV Over a year ago

Works! Would replacing BitVector with pure Python really hard? Will try to do it because adding libs require approval here. At least I have a working prototype to work with!

WorldSEnder Over a year ago

@AlexV the BitVector library, as far as I can see that is just one source file which you can find at engineering.purdue.edu/kak/dist/BitVector-3.4.8_CodeOnly.html I haven't looked at the license. The most important parts are (1) bit-indexing/slicing (2) supports len() (3) the constructor (4) logical operators, even for slices

WorldSEnder Over a year ago

Basically, weigh your options, but for readability either importing a BitVector class or writing it yourself is a must imo

Dillon Davis · Accepted Answer · 2018-07-25 02:57:00Z

Here's a more pythonic approach you could take, although it forgoes the direct bit arithmetic.

msg_hex = "8D4840D6202CC371C32CE0576098"
msg_dec = int(msg_hex, 16)
msg_bin = list(bin(msg_dec)[2:].zfill(8))

generator = "1111111111111010000001001"

for i in range(88):
    if msg_bin[i] == "1":
        msg_bin[i:i+24] = ["1" if a != b else "0" for a, b in zip(msg_bin[i:i+24], generator)]

if int("".join(msg_bin[-24:])):
    print("corrupted")

You could replace"1" if a != b else "0" with "01"[a!=b] if you wanted, but I think the former is more pythonic.

I could not verify if this solution is correct, since you code does not compile and there's no mention of what the given generator and message should produce. I do suspect there is an error in the problem statement however, since it is doing a check on the last 24 bits, but the generator contains 25.

Collectives™ on Stack Overflow

How to use bitwise operators on raw binary data in Python for a CRC check?

2 Answers 2

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related