I am trying to implement CRC32 calculation of file by splitting it in parts. I used algorithms and ideas from CRC Calculation Of A Mostly Static Data Stream. Unfortunately, my program gives incorrect answer, although it returns the same value of CRC regardless of number of parts. Please, tell me where the mistake is and what I do wrong. Here is the code of program:
#include <iostream>
#include <fstream>
#include <stdint.h>
#include <string>
#include <sstream>
#include <stdlib.h>
#include <stdio.h>
#include <pthread.h>
using namespace std;
struct data {
pthread_t id;
uint8_t *buf;
long int start, end;
long int num_zeros;
uint32_t crc;
};
//Straight function
uint32_t crc_32(ifstream& input) {
input.seekg(0, input.end);
size_t size = input.tellg();
input.seekg(0, input.beg);
uint32_t polynomial = 0xEDB88320;
uint32_t table[256];
for(uint32_t i=0; i<=0xff; i++) {
uint32_t c = i;
for (size_t j = 0; j < 8; j++)
{
if (c & 1) {
c = polynomial ^ (c >> 1);
}
else {
c >>= 1;
}
}
table[i] = c;
}
uint32_t CRC = 0xffffffff;
uint8_t buf;
for(size_t i=0; i<size; i++) {
input.read( (char *) &buf, sizeof(buf));
CRC = (CRC>>8) ^ table[(CRC ^ buf) & 0xff ];
}
CRC ^= 0xffffffff;
return CRC;
}
// generate crc
uint32_t GenCrc(data *work, long int beg, long int end, uint32_t *crctbl) {
uint32_t init = 0x00000000;
for(long int i = beg; i<end; i++) {
init = (init<<8)^crctbl[ (init>>24) ^ work->buf[i] ];
}
return init;
}
// (a*b)%crc
uint32_t MpyModCrc(uint32_t a, uint32_t b) {
uint32_t pd = 0;
uint32_t i;
for(i = 0; i < 32; i++){
pd = (pd<<1)^((0-(pd>>31))&0x04c11db7);
pd ^= (0-(b>>31))&a;
b <<= 1;
}
return pd;
}
// pow(2,p)%crc
uint32_t PowModCrc(uint32_t p) {
uint32_t prd = 0x1u;
uint32_t sqr = 0x2u;
while(p) {
if(p&1)
prd = MpyModCrc(prd, sqr);
sqr = MpyModCrc(sqr, sqr);
p >>= 1;
}
return prd;
}
void do_work(data *work) {
//Generate lookup table:
uint32_t polynomial = 0x04c11db7;
uint32_t crctbl[256];
uint32_t crc;
uint32_t c;
uint32_t i;
for(c=0; c <256; c++) {
crc = c<<24;
/*
for(i=0; i <8; i++) {
if( (crc & 0x80000000) !=0) {
crc <<= 1;
crc ^= polynomial;
}
else {
crc <<=1;
}
}
*/
for(i=0; i<8; i++) {
crc = (crc<<1)^(0-(crc>>31))&polynomial;
}
crctbl[c] = crc;
}
uint32_t pmc;
uint32_t crf;
crf = GenCrc(work, work->start, work->end, crctbl);
if(work->num_zeros > 0) {
pmc = PowModCrc((work->num_zeros)*8);
crf = MpyModCrc(crf, pmc);
}
work->crc = crf;
}
void *do_stuff(void *d) {
data *mydata = (data*)d;
do_work(mydata);
return 0;
}
int main(int argc, char** argv) {
ifstream input("8733718.zip", ios::binary);
if(!input) {
cerr << "Can't open file." <<endl;
}
input.seekg(0, input.end);
long int len = input.tellg();
input.seekg(0, input.beg);
uint8_t *buf = new uint8_t[len];
input.read( (char *) buf, len);
int k;
cout << "Enter number of parts: ";
if(!(cin >> k) || k<1) {
cout << "Error. We need at least one part!" <<endl;
return -1;
}
data *work = new data[k+1];
for(int i=0; i < k; i++) {
work[i].start = len*i;
work[i].start /=k;
work[i].end = len * (i+1);
work[i].end /= k;
work[i].num_zeros = len - work[i].end;
work[i].buf = buf;
}
for(int i=0; i < k; i++) {
void *tmp = (void*)&work[i];
pthread_create(&work[i].id, 0, do_stuff, tmp);
}
for(int i=0; i<k; i++) {
pthread_join(work[i].id, 0);
}
uint32_t crc = work[0].crc;
for(int i=1; i<k; i++) {
crc ^= work[i].crc;
}
delete [] buf;
delete [] work;
cout << "Straigth CRC_32 = ";
uint32_t result;
result = crc_32(input);
cout << hex << result;
cout <<endl <<endl;
cout << "Parallel CRC_32 = ";
uint32_t result2;
result2 = crc;
cout << hex << crc <<endl <<endl;
cout <<endl <<endl;
cout <<"=========================="<<endl<<endl;
input.close();
return 0;
}
"Straight" function gives the answer which coincides with the answer of, for example, website https://emn178.github.io/online-tools/crc32_checksum.html. But "parallel" procedure gives another answer.
