note 72378 added to function.crc32

Useful book: Numerical Recipes in C. They have a section on cyclic redundancy checksums, including crc32. The basic algorithm is: <?php function mycrc32($value, $width, $polynomial, $shift = 0xFFFFFFFF) { for ($jj = 0; $jj < $width; $jj++) { // PHP only does signed integers. When >> is used on a negative number, // the sign bit is extended, which gives incorrect results. So after // the right shift, we always clear the MSBit. if (($shift ^ $value) & 1) $shift = (($shift >> 1) & 0x7FFFFFFF) ^ $polynomial; else $shift = (($shift >> 1) & 0x7FFFFFFF); // We don't care about sign bit extension on $value, because we never // test past original bit 32, and discard $value when we are done. $value = ($value >> 1); } return $shift; } ?> You can handle arbitrary (bit) lengths of data by simply feeding the result of the previous CRC calculation in as the $shift value for the next calculation, and then chewing on some more data bits. So long as you chew data bits in the same order, it doesn't matter whether you feed it 32, 16, 8, 3, or even 1 bit at a time. Since the PHP crc32() does not export the starting value, you don't have the opportunity to "chain" it in this fashion - it's all or nothing on the whole string. Any number of polynomial values can be used, and many different values are used by different standards. The bits in the 'polynomial' value represent coefficients in a polynomial: (bit31)*x^31 + (bit30)*x^30 + ... + (bit1)*x^1 + (bit0) The resulting polynomial should be "primitive" or non-factorable: that is, a value of 0101b is not primitive, because the corresponding polynomial (x^2 + 1) factors into (x+1)*(x-1); conversely 0111b is primitive, because (x^2 + x + 1) cannot be factored. So, you can't use just any 32-bit value, but there are a lot of them that you can use. Different CRC implementations use different polynomials. The MSBit set (plus 1) determines the "order" of the polynomial, so for a crc32() you must have bit 31 set. For a crc16(), you must have bit 15 set, and bits 16 and above zero. The resulting CRC value will never have any bits set above the MSBit in the polynomial. One useful characteristic of all CRCs is that if you append the CRC bits themselves to the end of the data, the total CRC of the extended data is always zero. This puzzled me, because it doesn't appear to work with crc32(). However, a common (standard) variant on the "vanilla" crcr32 is to XOR the final result with a known constant. That appears to be what happens with this crc32() implementation, and the constant appears to be the value 0x2144DF1C. If you pack the crc32() value (little-endian) onto the end of the string and compute the crc32() of the whole thing, you will always get 0x2144DF1C. The following snippet can be used to "package" a string for transmission somewhere, with subsequent verification upon receipt: <?php function packetize($string) { return $string . pack("V", crc32($string)); } function verify($packet) { if ((crc32($packet) ^ 0x2144DF1C) == 0) return substr($packet, 0, -4); return false; } ?> This can be useful if there is some chance the transmission channel drops bits, or if going from one host (or protocol) to another switches the byte order, or you are manipulating the bits (e.g. encryption/decryption) and want to make reasonably sure you didn't scramble anything. ---- Server IP: 216.194.113.175 Probable Submitter: 24.9.89.42 ---- Manual Page -- http://www.php.net/manual/en/function.crc32.php Edit -- https://master.php.net/note/edit/72378 Del: integrated -- https://master.php.net/note/delete/72378/integrated Del: useless -- https://master.php.net/note/delete/72378/useless Del: bad code -- https://master.php.net/note/delete/72378/bad+code Del: spam -- https://master.php.net/note/delete/72378/spam Del: non-english -- https://master.php.net/note/delete/72378/non-english Del: in docs -- https://master.php.net/note/delete/72378/in+docs Del: other reasons-- https://master.php.net/note/delete/72378 Reject -- https://master.php.net/note/reject/72378 Search -- https://master.php.net/manage/user-notes.php