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

Question

I'm porting a CRC check function made in Python to JavaScript and I'm struggling a bit.

Here is the working Python code:

from BitVector import BitVector  # BitVector==3.4.8


def compute_crc(message):
    message = message.deep_copy()
    generator = BitVector(bitstring='1111111111111010000001001')
    crc_length = len(generator) - 1
    content_length = len(message) - crc_length

    assert content_length >= 0

    for i in range(content_length):
        if message[i]:
            message[i:i + len(generator)] ^= generator

    return message[-crc_length:]


adsb_hex = "8D4840D6202CC371C32CE0576098"
adsb_crc = compute_crc(BitVector(hexstring = adsb_hex))

if int(adsb_crc) != 0:
    print 'Bad'
else:
    print 'Good'

Here is my (bad) JavaScript code:

function BinToDec(binStr)
{
    var regexp = /^[01]+$/
    if (!regexp.test(binStr)) {
        return false;
    }
    var result = parseInt(binStr, 2);
    if (isNaN(result)) {
        return false;
    }
    return result;
}

function StrToBinArray(binStr)
{
    var result = new Array();
    for (var i = 0; i < binStr.length; i++) {
        result[i] = binStr[i] === '0' ? 0 : 1;
    }
    return result;
}

function TestCRC(adsbBinStr)
{
    var genStr = '1111111111111010000001001';
    var generatorInt = BinToDec(genStr);
    var generator = StrToBinArray(genStr);
    var crcLength = generator.length - 1;
    var contentLength = adsbBinStr.length - crcLength;

    if (contentLength < 0) {
        return false;
    }

    var adsbBin = StrToBinArray(adsbBinStr);

    for (var i = 0; i <= contentLength; i++) {
        if (adsbBin[i]) {
            var currSlice =  adsbBin.slice(i, i + generator.length);
            var currSliceInt = BinToDec(BinArrayToStr(currSlice));
            var currCheck = currSliceInt ^ generatorInt;
            var currCheckBin = currCheck.toString(2);

            for (var j = 0; j <= currCheckBin.length; j++) {
                adsbBin[i + j] = currCheckBin[j];
            }
        }
    }


    return BinToDec(BinArrayToStr(adsbBin.slice(contentLength + 2))) === 0;
}

TestCRC('1000110101001000010000001101011000100000001011001100001101110001110000110010110011100000010101110110000010011000');

If it helps here is the CRC check as pseudocode:

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

TLDR I'm struggling to port message[i:i + len(generator)] ^= generator correctly from Python to JavaScript and I need help.

Your pseudocode contains MSG[i:i+24], but in Python, you are using len(generator) which is 25. Is that mistake? — bigless
– bigless, Commented Aug 2, 2018 at 21:56

AlexV · Accepted Answer · 2018-08-03 15:54:46Z

1

According to your Python code, this could be an alternative in Javascript.

// just some util functions to replace BitVector functionality
// https://stackoverflow.com/a/12987042/4209136
function checkBin(n){return/^[01]{1,64}$/.test(n)}
function checkDec(n){return/^[0-9]{1,64}$/.test(n)}
function checkHex(n){return/^[0-9A-Fa-f]{1,64}$/.test(n)}
function Bin2Dec(n){if(!checkBin(n))return 0;return parseInt(n,2).toString(10)}
function Dec2Bin(n){if(!checkDec(n)||n<0)return 0;return n.toString(2)}
function Hex2Bin(n){if(!checkHex(n))return 0;return parseInt(n,16).toString(2)}

function ZeroPad(num, size)
{
    var result = String(num);
    while (result.length < size) {
        result = '0' + result;
    }
    return result;
}

function computeCrc(message) {
  var generator = '1111111111111010000001001';
  var genInt = Bin2Dec(generator);
  var crcLength = generator.length - 1;
  var contentLength = message.length - crcLength;
  
  if (contentLength < 0) {
    throw 'Invalid content length.';
  }
  
  for (var i = 0;i < contentLength;i++) {
    if (message[i] === '0') continue;

    let curInt = Bin2Dec(message.substr(i, i + generator.length));

    message = message.substr(0, i) + 
      ZeroPad(Dec2Bin(curInt ^ genInt), generator.length) + 
      message.substr(i + generator.length);
  }
  
  return message.substr(message.length - crcLength);
}

var adsbCrc = computeCrc(Hex2Bin("8D4840D6202CC371C32CE0576098"));

console.log(parseInt(adsbCrc) === 0 ? 'Good' : 'Bad');

edited Aug 3, 2018 at 15:54

AlexV

23.2k21 gold badges89 silver badges131 bronze badges

answered Aug 2, 2018 at 22:24

bigless

3,14124 silver badges35 bronze badges

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

2 Comments

AlexV Over a year ago

Fixed the answer where the leading zeroes in the XOR were dropped but are really important! Also the Hex2Bin is broken (the limit is 64-bit but I'm using 112-bits messages) but using mine in the question works. Thanks!

bigless Over a year ago

Eh. Most of my knowledge about basic binary operations is lost so sorry about that.. Anyway I'm glad to hear that it led you to solution..

Collectives™ on Stack Overflow

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

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related