crc algo

[compro]

i have been reading crc32 algoritm
and though i have understood the procedure
the algorithm is confusing.

first i used this algorithm

Code: Select all

r=0; while (len--) r = ((r << 8) | *p++) ^ t[(r >> 24) & 0xFF];
for (i=0; i<4; i++) r = (r << 8) ^ t[(r >> 24) & 0xFF];

where t referes to table of crc
crc=r

well this was easy. and i got the who idea.
first the message was bought in. the last line processed the last 4 bytes out of the register
now the author propsed another algorithm(a shorter and better one)

Code: Select all

 r=0; while (len--) r = (r<<8) ^ t[(r >> 24) ^ *p++];

where p is block of data

well this algorithm i couldnt understand
i mean why index table using [(r >> 24) ^ *p++]

why to use p in indexing??
anyone who can explain it to me?
and how is this equal to the algorithm above.

[bluemoon]

No it does not use p as index, it uses *p (de-referenced). And I would suggest to add brackets and perhaps break it down into statements for readability. The optimized code should looks the same (And I guess if the data is huge enough to worth for optimization, the bottleneck will be memory bandwidth, not processing power, anyway)

[turdus]

Here's a solution with lookup tables for 2 polynominals (as used by my mkfs utility):

Code: Select all

//precalculated CRC32c lookup table for polynomial 0x1EDC6F41 (castagnoli-crc)
unsigned long int crc32c_lookup[256]={
	0x00000000L, 0xF26B8303L, 0xE13B70F7L, 0x1350F3F4L, 0xC79A971FL, 0x35F1141CL, 0x26A1E7E8L, 0xD4CA64EBL,
	0x8AD958CFL, 0x78B2DBCCL, 0x6BE22838L, 0x9989AB3BL, 0x4D43CFD0L, 0xBF284CD3L, 0xAC78BF27L, 0x5E133C24L,
	0x105EC76FL, 0xE235446CL, 0xF165B798L, 0x030E349BL, 0xD7C45070L, 0x25AFD373L, 0x36FF2087L, 0xC494A384L,
	0x9A879FA0L, 0x68EC1CA3L, 0x7BBCEF57L, 0x89D76C54L, 0x5D1D08BFL, 0xAF768BBCL, 0xBC267848L, 0x4E4DFB4BL,
	0x20BD8EDEL, 0xD2D60DDDL, 0xC186FE29L, 0x33ED7D2AL, 0xE72719C1L, 0x154C9AC2L, 0x061C6936L, 0xF477EA35L,
	0xAA64D611L, 0x580F5512L, 0x4B5FA6E6L, 0xB93425E5L, 0x6DFE410EL, 0x9F95C20DL, 0x8CC531F9L, 0x7EAEB2FAL,
	0x30E349B1L, 0xC288CAB2L, 0xD1D83946L, 0x23B3BA45L, 0xF779DEAEL, 0x05125DADL, 0x1642AE59L, 0xE4292D5AL,
	0xBA3A117EL, 0x4851927DL, 0x5B016189L, 0xA96AE28AL, 0x7DA08661L, 0x8FCB0562L, 0x9C9BF696L, 0x6EF07595L,
	0x417B1DBCL, 0xB3109EBFL, 0xA0406D4BL, 0x522BEE48L, 0x86E18AA3L, 0x748A09A0L, 0x67DAFA54L, 0x95B17957L,
	0xCBA24573L, 0x39C9C670L, 0x2A993584L, 0xD8F2B687L, 0x0C38D26CL, 0xFE53516FL, 0xED03A29BL, 0x1F682198L,
	0x5125DAD3L, 0xA34E59D0L, 0xB01EAA24L, 0x42752927L, 0x96BF4DCCL, 0x64D4CECFL, 0x77843D3BL, 0x85EFBE38L,
	0xDBFC821CL, 0x2997011FL, 0x3AC7F2EBL, 0xC8AC71E8L, 0x1C661503L, 0xEE0D9600L, 0xFD5D65F4L, 0x0F36E6F7L,
	0x61C69362L, 0x93AD1061L, 0x80FDE395L, 0x72966096L, 0xA65C047DL, 0x5437877EL, 0x4767748AL, 0xB50CF789L,
	0xEB1FCBADL, 0x197448AEL, 0x0A24BB5AL, 0xF84F3859L, 0x2C855CB2L, 0xDEEEDFB1L, 0xCDBE2C45L, 0x3FD5AF46L,
	0x7198540DL, 0x83F3D70EL, 0x90A324FAL, 0x62C8A7F9L, 0xB602C312L, 0x44694011L, 0x5739B3E5L, 0xA55230E6L,
	0xFB410CC2L, 0x092A8FC1L, 0x1A7A7C35L, 0xE811FF36L, 0x3CDB9BDDL, 0xCEB018DEL, 0xDDE0EB2AL, 0x2F8B6829L,
	0x82F63B78L, 0x709DB87BL, 0x63CD4B8FL, 0x91A6C88CL, 0x456CAC67L, 0xB7072F64L, 0xA457DC90L, 0x563C5F93L,
	0x082F63B7L, 0xFA44E0B4L, 0xE9141340L, 0x1B7F9043L, 0xCFB5F4A8L, 0x3DDE77ABL, 0x2E8E845FL, 0xDCE5075CL,
	0x92A8FC17L, 0x60C37F14L, 0x73938CE0L, 0x81F80FE3L, 0x55326B08L, 0xA759E80BL, 0xB4091BFFL, 0x466298FCL,
	0x1871A4D8L, 0xEA1A27DBL, 0xF94AD42FL, 0x0B21572CL, 0xDFEB33C7L, 0x2D80B0C4L, 0x3ED04330L, 0xCCBBC033L,
	0xA24BB5A6L, 0x502036A5L, 0x4370C551L, 0xB11B4652L, 0x65D122B9L, 0x97BAA1BAL, 0x84EA524EL, 0x7681D14DL,
	0x2892ED69L, 0xDAF96E6AL, 0xC9A99D9EL, 0x3BC21E9DL, 0xEF087A76L, 0x1D63F975L, 0x0E330A81L, 0xFC588982L,
	0xB21572C9L, 0x407EF1CAL, 0x532E023EL, 0xA145813DL, 0x758FE5D6L, 0x87E466D5L, 0x94B49521L, 0x66DF1622L,
	0x38CC2A06L, 0xCAA7A905L, 0xD9F75AF1L, 0x2B9CD9F2L, 0xFF56BD19L, 0x0D3D3E1AL, 0x1E6DCDEEL, 0xEC064EEDL,
	0xC38D26C4L, 0x31E6A5C7L, 0x22B65633L, 0xD0DDD530L, 0x0417B1DBL, 0xF67C32D8L, 0xE52CC12CL, 0x1747422FL,
	0x49547E0BL, 0xBB3FFD08L, 0xA86F0EFCL, 0x5A048DFFL, 0x8ECEE914L, 0x7CA56A17L, 0x6FF599E3L, 0x9D9E1AE0L,
	0xD3D3E1ABL, 0x21B862A8L, 0x32E8915CL, 0xC083125FL, 0x144976B4L, 0xE622F5B7L, 0xF5720643L, 0x07198540L,
	0x590AB964L, 0xAB613A67L, 0xB831C993L, 0x4A5A4A90L, 0x9E902E7BL, 0x6CFBAD78L, 0x7FAB5E8CL, 0x8DC0DD8FL,
	0xE330A81AL, 0x115B2B19L, 0x020BD8EDL, 0xF0605BEEL, 0x24AA3F05L, 0xD6C1BC06L, 0xC5914FF2L, 0x37FACCF1L,
	0x69E9F0D5L, 0x9B8273D6L, 0x88D28022L, 0x7AB90321L, 0xAE7367CAL, 0x5C18E4C9L, 0x4F48173DL, 0xBD23943EL,
	0xF36E6F75L, 0x0105EC76L, 0x12551F82L, 0xE03E9C81L, 0x34F4F86AL, 0xC69F7B69L, 0xD5CF889DL, 0x27A40B9EL,
	0x79B737BAL, 0x8BDCB4B9L, 0x988C474DL, 0x6AE7C44EL, 0xBE2DA0A5L, 0x4C4623A6L, 0x5F16D052L, 0xAD7D5351L
};

//precalculated crc lookup table for EFI (ansi-crc)
unsigned long int crc32_lookup[256]={
	0x00000000,0x77073096,0xee0e612c,0x990951ba,0x076dc419,0x706af48f,0xe963a535,0x9e6495a3,0x0edb8832,
	0x79dcb8a4,0xe0d5e91e,0x97d2d988,0x09b64c2b,0x7eb17cbd,0xe7b82d07,0x90bf1d91,0x1db71064,0x6ab020f2,
	0xf3b97148,0x84be41de,0x1adad47d,0x6ddde4eb,0xf4d4b551,0x83d385c7,0x136c9856,0x646ba8c0,0xfd62f97a,
	0x8a65c9ec,0x14015c4f,0x63066cd9,0xfa0f3d63,0x8d080df5,0x3b6e20c8,0x4c69105e,0xd56041e4,0xa2677172,
	0x3c03e4d1,0x4b04d447,0xd20d85fd,0xa50ab56b,0x35b5a8fa,0x42b2986c,0xdbbbc9d6,0xacbcf940,0x32d86ce3,
	0x45df5c75,0xdcd60dcf,0xabd13d59,0x26d930ac,0x51de003a,0xc8d75180,0xbfd06116,0x21b4f4b5,0x56b3c423,
	0xcfba9599,0xb8bda50f,0x2802b89e,0x5f058808,0xc60cd9b2,0xb10be924,0x2f6f7c87,0x58684c11,0xc1611dab,
	0xb6662d3d,0x76dc4190,0x01db7106,0x98d220bc,0xefd5102a,0x71b18589,0x06b6b51f,0x9fbfe4a5,0xe8b8d433,
	0x7807c9a2,0x0f00f934,0x9609a88e,0xe10e9818,0x7f6a0dbb,0x086d3d2d,0x91646c97,0xe6635c01,0x6b6b51f4,
	0x1c6c6162,0x856530d8,0xf262004e,0x6c0695ed,0x1b01a57b,0x8208f4c1,0xf50fc457,0x65b0d9c6,0x12b7e950,
	0x8bbeb8ea,0xfcb9887c,0x62dd1ddf,0x15da2d49,0x8cd37cf3,0xfbd44c65,0x4db26158,0x3ab551ce,0xa3bc0074,
	0xd4bb30e2,0x4adfa541,0x3dd895d7,0xa4d1c46d,0xd3d6f4fb,0x4369e96a,0x346ed9fc,0xad678846,0xda60b8d0,
	0x44042d73,0x33031de5,0xaa0a4c5f,0xdd0d7cc9,0x5005713c,0x270241aa,0xbe0b1010,0xc90c2086,0x5768b525,
	0x206f85b3,0xb966d409,0xce61e49f,0x5edef90e,0x29d9c998,0xb0d09822,0xc7d7a8b4,0x59b33d17,0x2eb40d81,
	0xb7bd5c3b,0xc0ba6cad,0xedb88320,0x9abfb3b6,0x03b6e20c,0x74b1d29a,0xead54739,0x9dd277af,0x04db2615,
	0x73dc1683,0xe3630b12,0x94643b84,0x0d6d6a3e,0x7a6a5aa8,0xe40ecf0b,0x9309ff9d,0x0a00ae27,0x7d079eb1,
	0xf00f9344,0x8708a3d2,0x1e01f268,0x6906c2fe,0xf762575d,0x806567cb,0x196c3671,0x6e6b06e7,0xfed41b76,
	0x89d32be0,0x10da7a5a,0x67dd4acc,0xf9b9df6f,0x8ebeeff9,0x17b7be43,0x60b08ed5,0xd6d6a3e8,0xa1d1937e,
	0x38d8c2c4,0x4fdff252,0xd1bb67f1,0xa6bc5767,0x3fb506dd,0x48b2364b,0xd80d2bda,0xaf0a1b4c,0x36034af6,
	0x41047a60,0xdf60efc3,0xa867df55,0x316e8eef,0x4669be79,0xcb61b38c,0xbc66831a,0x256fd2a0,0x5268e236,
	0xcc0c7795,0xbb0b4703,0x220216b9,0x5505262f,0xc5ba3bbe,0xb2bd0b28,0x2bb45a92,0x5cb36a04,0xc2d7ffa7,
	0xb5d0cf31,0x2cd99e8b,0x5bdeae1d,0x9b64c2b0,0xec63f226,0x756aa39c,0x026d930a,0x9c0906a9,0xeb0e363f,
	0x72076785,0x05005713,0x95bf4a82,0xe2b87a14,0x7bb12bae,0x0cb61b38,0x92d28e9b,0xe5d5be0d,0x7cdcefb7,
	0x0bdbdf21,0x86d3d2d4,0xf1d4e242,0x68ddb3f8,0x1fda836e,0x81be16cd,0xf6b9265b,0x6fb077e1,0x18b74777,
	0x88085ae6,0xff0f6a70,0x66063bca,0x11010b5c,0x8f659eff,0xf862ae69,0x616bffd3,0x166ccf45,0xa00ae278,
	0xd70dd2ee,0x4e048354,0x3903b3c2,0xa7672661,0xd06016f7,0x4969474d,0x3e6e77db,0xaed16a4a,0xd9d65adc,
	0x40df0b66,0x37d83bf0,0xa9bcae53,0xdebb9ec5,0x47b2cf7f,0x30b5ffe9,0xbdbdf21c,0xcabac28a,0x53b39330,
	0x24b4a3a6,0xbad03605,0xcdd70693,0x54de5729,0x23d967bf,0xb3667a2e,0xc4614ab8,0x5d681b02,0x2a6f2b94,
	0xb40bbe37,0xc30c8ea1,0x5a05df1b,0x2d02ef8d};

//calculate CRC32c checksum
unsigned long int crc32_calc(char *start,int length)
{
	unsigned long int crc32_val=0;
	while(length--) crc32_val=(crc32_val>>8)^crc32c_lookup[(crc32_val&0xff)^(unsigned char)*start++];
	return crc32_val;
}

//calculate EFI compatible crc
unsigned long int eficrc32_calc(char *start,int length)
{
	//init
	unsigned long int crc32_val=0xffffffff;
	//calculate
	while(length--) crc32_val=(crc32_val>>8)^crc32_lookup[(crc32_val&0xff)^(unsigned char)*start++];
	//finalize
	crc32_val^=0xffffffff;
	return crc32_val;
}

[compro]

well i guess i wasnt clear enough in asking the question
i know *p is used
and my question is
what exactly this line does

Code: Select all

r=0; while (len--) r = (r<<8) ^ t[(r >> 24) ^ *p++];

i know it calculates crc but how
i read the paper written by ross and yet couldnt fully understand the above code
so can anyone explain??

[Combuster]

Start with computing CRCs, by hand, on paper. Can you do that?

[Yoda]

what exactly this line does

Code: Select all

r=0; while (len--) r = (r<<8) ^ t[(r >> 24) ^ *p++];

This line does the following:
1. Takes the first (most significant) byte of CRC code. (r>>24)
2. XORs it with the next feed byte (res ^ *p++)
3. Translates it through the lookup table (t[res])
4. Takes the rest (untouched part) of CRC code (r<<8)
5. Mixes it to the result of translation (res1 ^ res2)
6. Runs the same steps through the whole sequence.
Doesn't it?

[rdos]

This is more readable:

Code: Select all

    r=0; 
    while (len--)
    { 
        res = r >> 24;
        res = res ^ *p;
        res = t[res];
        res = res ^ (r << 8);
        p++;
     }

I really hate it when people try to optimize code like that. Especially the part that both access and increments a pointer in one step.

[Solar]

I really hate it when people try to optimize code like that. Especially the part that both access and increments a pointer in one step.

While I also prefer having { } around loop bodies, and certainly would have comments with code like that, access-and-increment is standard issue C/C++. That isn't even about "optimization" of any kind, but about expressiveness of code.

[rdos]

My main problem with access and increment is that I'm always unsure about the precedence of the operators, and the fact that the increment is hidden away so it isn't easily seen in the code. So I never use access and increment, but I'm fine with others doing it as long they don't bundle everything on a single line!

If I had written the code myself, I'd probably do it like this instead (avoids both test and decrement and access and increment):

Code: Select all

    r=0; 
    for (i = 0; i < len; i++)
    { 
        res = r >> 24;
        res = res ^ p[i];
        res = t[res];
        r = res ^ (r << 8);
     }

Or possibly like this:

Code: Select all

    r=0; 
    for (i = 0; i < len; i++)
    { 
        res = p[i] ^ (r >> 24);
        r = t[res] ^ (r << 8);
     }

[Owen]

My main problem with access and increment is that I'm always unsure about the precedence of the operators,

p++ = return p, then increment
++p = increment then return p

I'd be worried if I couldn't keep something so trivial straight

[brain]

Rdos means precedence of * and ++, basically post/pre increment and dereference. dereference has higher preference so *p++ means return value pointed at by p and then increment p. you can and probably should make it explicit and readable by putting *(p++) instead. (*p)++ will increment the value at p instead.

[Solar]

Also, use parenthesis when confused.

I'd like to extend that to "always use parenthesis".

It's like source without comments. Was the programmer aware of what his tricky piece of code does, or is the tricky-ness by accident?

[Combuster]

I'd like to extend that to "always use parenthesis".

IMHO I think always is a bit too pedantic:

Code: Select all

lengthsquared = x*x + y*y + z*z;
hermite = a*t*t*t + b*t*t + c*t + offset;
vs
lengthsquared = (x * x) + (y * y) + (z * z);
hermite = (a * t * t * t) + (b * t * t) + (c * t) + offset;

Mostly because it deviates away from the pen-and-paper notation. Too many braces can just cause reading noise in your code. (And yes, I slipped in an alternative style )

[Solar]

When phrasing a style guide I much prefer to phrase in the absolute. That makes for shorter, easier to remember rules. The pedantery would be insisting on the rule in clear-cut cases like your example. But for a general advice, the absolute serves well IMHO.