CRC calculation - bit by bit - C++

Question

I need to create a program, that calculates CRC from file. It needs to be done bit by bit.

The way I would like to read a file:

unsigned char byte;
ifstream file;
bool result;
int number;

file.open("test.txt", ios::binary);

while(true)
{
    byte = file.get();
    number = (int)byte;

    result = file.good();
    if(!result) 
    break;  
}

However, I don't know how to read it bit by bit.

My CRC's divisor (called a "polynomial") is 0x04C11DB7 and I need to import 1 new bit from file each time I calculate my buffer.

My idea is to add first 4 bytes to variable (for let's say "1234" it would be 0x31323334), then remove last bit (by moving the number 1 bit to the left), but I don't know how to add a new bit from the next char.

Read a byte and then process every bit in a byte one by one. — Slava, Jun 07 '18 at 20:03
Given your edit, I think that you are asking how to move a 4 byte "window" through a datastream, one bit at a time. Is that your question? — Drew Dormann, Jun 07 '18 at 20:11
You can't read a bit at a time. Read a byte at a time (or more), then process those bytes bit by bit. — Jesper Juhl, Jun 07 '18 at 20:12
https://en.wikipedia.org/wiki/Computation_of_cyclic_redundancy_checks — Michał, Jun 07 '18 at 20:15
Every time i calculate buffor, I need to remove last bit and add a new one the next char. For "A" which is 0x41 = 0100 0001 I need to firstly read 0, then 1, then 0, then 0, then 0, then and so on for each single char — Michał, Jun 07 '18 at 20:16
That linked example is sort of brutal. Most CRCs are done at the byte-level or above. To get what you want you will have to do some bit masking on bytes. eg: `val &0x80` and then `val &0x40` and then `val &0x20`, etc... walking the you are inspecting along one bit at a time. — user4581301, Jun 07 '18 at 20:17
Why don't you simply use the [boost crc](https://www.boost.org/doc/libs/1_64_0/libs/crc/crc.html) ? — Victor Gubin, Jun 07 '18 at 20:31
*use boost* seems to be an universal answer for everything these days... — Timo, Jun 07 '18 at 20:35
I used to make my own CRC routines as I needed them for work. However, you have to be VERY careful with shifts (lengths, especially) and overflows that you don't stumble into UB accidentally. Still, its fun to do and helps understanding CRCs. — doug, Jun 07 '18 at 22:32

score 0 · Answer 1 · answered Jun 07 '18 at 20:44

Do you mean something along these lines? The CRC calculation may vary, but the focus here is on getting the file content "bit by bit".

#include <iostream>
#include <fstream>

int main(int argc, char* argv[])
{
    unsigned char next;
    unsigned long crc = 0;
    if (argc < 2)
        return -1;
    std::fstream fs(argv[1], std::fstream::in);
    while (!fs.bad() && !fs.eof())
    {
        fs >> next;
        for (int i = 0; i < 8; i++)
        {
            crc += next & 1;
            next >>= 1;
        }
    }
    std::cout << "CRC " << crc << std::endl;
    return 0;
}

score 0 · Answer 2 · answered Jun 07 '18 at 20:58

The divisor is not just called a polynomial. It means that each bit is a coefficient of a polynomial (of degree 32) and thus the way of computing with polynomial differs significantly from working with integers. You can add (and substract, which is the same in this case) two polynomials with a simple XOR operation. Multiplying/Dividing with/by X means shifting. To the right or to the left depends on the order in which the coefficients of the polynomials are written. This is important to know because both directions (left to right and right to left) actually exist. In the case of 0x04C11DB7, the coefficient of X^0 is bit 0 and the coefficient of X^31 is bit 31. Be aware that the popular implementation of the IEEE802.3 CRC has the opposite bit order. So, just copying the implementation of an Ethernet CRC will not work.

This means the next bit to process is always bit 31. You must therefore check for 0x80000000. If the bit is set, XOR your polynomial. This means, you subtract the polynomical from your work register. In any case, shift the result to the left afterwards. Then a 0 bit is shifted in at the right. Replace it with the next bit to process by a binary or operation (| in C++). You obtain that bit in the same way: if you are reading byte by byte, your next bit is 1 or 0, depending on whether 0x80 is set in your input. Then shift your input to the left.

CRC calculation - bit by bit - C++

2 Answers2