What's wrong with my CRC algorithm? (Java)

Question

Had asked a much broader question yesterday, but figured it may be prudent to delete it and narrow my question down a bit. Again, in the interest of honesty, yes, this is homework. I'm trying to develop a CRC algorithm with the following polynomial:

x15+x13+x6+x4+x1+1

I'm supposed to pass two bytes (8-bits), combine them into a 16-bit result (so I shift the first byte left 8, then add the two together), and then find the CRC using the above polynomial. I've been checking what my output should be using this tool, but I can't seem to get the correct answer.

What I have:

(Relevant Global Variables)

static String binaryCRC = "1010000001010011";
static long divisor = Long.parseLong(binaryCRC, 2);
static int mask = 0x8000;

(Actual Algorithm)

public static void crc(byte first, byte second) {

    long total = ((first << 8) + second);
    System.out.print(Long.toHexString(total));

    for (int i = 0; i < binaryCRC.length(); i++) {
        if ((total & mask) == mask) {
            total ^= divisor;
        }

        total <<= 1;
    }
    System.out.println(" -> " + Long.toHexString(total));
}

EDIT: My attempt to revise my for-loop utilizing the suggestion given below:

for (int i = 0; i < binaryCRC.length(); i++) {
        if ((total & mask) == mask) {
            total = (total << 1) ^ divisor;
        } else {
            total <<= 1;
        }
    }

Perhaps I'm doing it incorrectly, but my output becomes incredibly far off when I do this way. When setting the value of my two bytes to the ASCII values of chars 'a' and 'b' (total = 6162), I get 6162 -> 4f1b065d, when I should be getting 77eb.

EDIT 2: I briefly outlined it below, but in the interest of clarity, I'm adding the rest of what I need to do, because I don't know how to find the cumulative CRC across multiple characters.

I need to find the cumulative CRC of the String below, and print the CRC thus far every 64th character. My answer is currently bf58 for the first 64, when the answer SHOULD be 1a6a.

public class test2 {

static String binaryCRC = "1010000001010011";
static long divisor = Long.parseLong(binaryCRC, 2);
static long cumCRC = divisor;
static long mask = 0x8000;
static long[] crcTable = new long[256];
static int counter = 0;

static String text = "abcdefghijklmnopqrstuvwxyz12345-ABCDEFGHIJKLMNOPQRSTUVWX"
        + "YZ12345abcdefghijklmnopqrstuvwxyz12345-ABCDEFGHIJKLMNOPQ"
        + "RSTUVWXYZ12345abcdefghijklmnopqrstuvwxyz12345-ABCDEFGHIJ"
        + "KLMNOPQRSTUVWXYZ12345abcdefghijklmnopqrstuvwxyz12345-ABC"
        + "DEFGHIJKLMNOPQRSTUVWXYZ12345abcdefghijklmnopqrstuvwxyz12"
        + "345-ABCDEFGHIJKLMNOPQRSTUVWXYZ12345abcdefghijklmnopqrstu"
        + "vwxyz12345-ABCDEFGHIJKLMNOPQRSTUVWXYZ12345.............."
        + "........................................................"
        + "........................................................"
        + "000075dc";

static char[] chars = text.toCharArray();

public static void main(String[] args) {

    for (int i = 0; i < chars.length - 8; i += 2) {
        crc((byte)chars[i], (byte)chars[i + 1]);
        System.out.print(chars[i] + "" + chars[i+1]);

         //Probably wrong
         cumCRC = ((cumCRC >> 8) ^ crcTable[i / 2]) & 0xFFFF;

        if ((i + 2) % 64 == 0) {
            System.out.println(" - " + Long.toHexString(cumCRC));
        }
    }

}

public static void crc(byte first, byte second) {

    long total = ((first << 8) + second);
    //System.out.print(Long.toHexString(total));

    for (int i = 0; i < binaryCRC.length(); i++) {
        if ((total & mask) != 0) {
            total = (total << 1) ^ divisor;
        } else {
            total <<= 1;
        }

    }
    //System.out.println(" -> " + Long.toHexString(total));

    crcTable[counter] = total;
    counter++;
}
}

Mark Adler Mark Adler · Accepted Answer · 2014-11-25T23:58:06

Ok, this is closer. You need to check the high bit, then shift, then exclusive-or the polynomial if the high bit was a one. You are doing the shift after, which is obviously wrong since it guarantees that the answer always has a low bit of zero.

Update for edited answer:

The code is now correct. However you are entering the polynomial incorrectly on the website you linked. The actual polynomial has an x¹⁶ term as well. Put in that leading one.

Update for another edit:

You do not calculate a CRC for each pair of bytes separately. Instead you continue to process the CRC with more bytes. Before the first step, you exclusive-ored the initial CRC, zero, with the two bytes (though you may not realize you did that). Just keep doing that with the intermediate CRCs.

What's wrong with my CRC algorithm? (Java)

1 Answers