CRC-32
Implement the Cyclic Redundancy Check from ISO 3309, ITU-T V.42, Gzip and PNG. Algorithms are described on Computation of CRC in Wikipedia. This variant of CRC-32 uses LSB-first order, sets the initial CRC to FFFFFFFF16, and complements the final CRC.
Use this CRC-32 to generate a checksum for the following ASCII encoded string of bytes: "The quick brown fox jumps over the lazy dog"
C
Library
Using zlib's crc32: <lang c>#include <stdio.h>
- include <string.h>
- include <zlib.h>
int main() { char *s = "The quick brown fox jumps over the lazy dog"; printf("%lX\n", crc32(0, (void*)s, strlen(s)));
return 0; }</lang>
Implementation
This code is a translation from Ruby, with an adjustment to use 32-bit integers. This code happens to resemble the examples from RFC 1952 section 8 and from PNG annex D, because those examples use an identical table.
<lang c>#include <inttypes.h>
- include <stdio.h>
- include <string.h>
uint32_t rc_crc32(uint32_t crc, const char *buf, size_t len) { static uint32_t table[256]; static int have_table = 0; uint32_t rem, octet; int i, j; const char *p, *q;
/* This check is not thread safe; there is no mutex. */ if (have_table == 0) { /* Calculate CRC table. */ for (i = 0; i < 256; i++) { rem = i; /* remainder from polynomial division */ for (j = 0; j < 8; j++) { if (rem & 1) { rem >>= 1; rem ^= 0xedb88320; } else rem >>= 1; } table[i] = rem; } have_table = 1; }
crc = ~crc; q = buf + len; for (p = buf; p < q; p++) { octet = *p; /* Cast to unsigned octet. */ crc = (crc >> 8) ^ table[(crc & 0xff) ^ octet]; } return ~crc; }
int main() { char *s = "The quick brown fox jumps over the lazy dog"; printf("%" PRIX32 "\n", rc_crc32(0, (void*)s, strlen(s)));
return 0; }</lang>
Go
Library
<lang go>package main
import (
"fmt" "hash/crc32"
)
func main() {
s := []byte("The quick brown fox jumps over the lazy dog") result := crc32.ChecksumIEEE(s) fmt.Printf("%X\n", result)
}</lang> output
414FA339
Implementation
<lang go>package main
import "fmt"
var table [256]uint32
func init() {
for i := range table { word := uint32(i) for j := 0; j < 8; j++ { if word&1 == 1 { word = (word >> 1) ^ 0xedb88320 } else { word >>= 1 } } table[i] = word }
}
func crc32(s string) uint32 {
crc := ^uint32(0) for i := 0; i < len(s); i++ { crc = table[byte(crc)^s[i]] ^ (crc >> 8) } return ^crc
}
func main() {
fmt.Printf("%0x\n", crc32("The quick brown fox jumps over the lazy dog"))
}</lang> Output:
414fa339
Icon and Unicon
There is no library function for this so we implement one. Icon/Unicon binary operations apply to large integers so we need to mask to the desired unsigned word size. This also only applies to full bytes. <lang Icon>link hexcvt,printf
procedure main()
s := "The quick brown fox jumps over the lazy dog" a := "414FA339" printf("crc(%i)=%s - implementation is %s\n", s,r := crc32(s),if r == a then "correct" else "in error")
end
procedure crc32(s) #: return crc-32 (ISO 3309, ITU-T V.42, Gzip, PNG) of s static crcL,mask initial {
crcL := list(256) # crc table p := [0,1,2,4,5,7,8,10,11,12,16,22,23,26] # polynomial terms mask := 2^32-1 # word size mask every (poly := 0) := ior(poly,ishift(1,31-p[1 to *p])) every c := n := 0 to *crcL-1 do { # table every 1 to 8 do c := iand(mask, if iand(c,1) = 1 then ixor(poly,ishift(c,-1)) else ishift(c,-1) ) crcL[n+1] := c } } crc := ixor(0,mask) # invert bits every crc := iand(mask, ixor(crcL[iand(255,ixor(crc,ord(!s)))+1],ishift(crc,-8))) return hexstring(ixor(crc,mask)) # return hexstring
end</lang>
hexcvt.icnprovides hex and hexstring printf.icnprovides formatting
Output:
crc("The quick brown fox jumps over the lazy dog")=414FA339 - implementation is correct
J
<lang j> ((i.32) e. 32 26 23 22 16 12 11 10 8 7 5 4 2 1 0) 128!:3 'The quick brown fox jumps over the lazy dog' _3199229127</lang>
Other possible representations of this result:
<lang j> (2^32x)|((i.32) e. 32 26 23 22 16 12 11 10 8 7 5 4 2 1 0) 128!:3 'The quick brown fox jumps over the lazy dog' 1095738169
require'convert' hfd (2^32x)|((i.32) e. 32 26 23 22 16 12 11 10 8 7 5 4 2 1 0) 128!:3 'The quick brown fox jumps over the lazy dog'
414FA339</lang>
PHP
PHP has a built-in function crc32.
<lang php>printf("%x\n", crc32("The quick brown fox jumps over the lazy dog"));</lang>
414fa339
Python
Library
<lang python>>>> import zlib >>> hex(zlib.crc32('The quick brown fox jumps over the lazy dog')) '0x414fa339'</lang>
Ruby
<lang ruby>module CRC
# Divisor is a polynomial of degree 32 with coefficients modulo 2. # We store Divisor in a 33-bit Integer; the polynomial is # Divisor[32] + Divisor[31] * x + ... + Divisor[0] * x**32 Divisor = [0, 1, 2, 4, 5, 7, 8, 10, 11, 12, 16, 22, 23, 26, 32] \ .inject(0) {|sum, exponent| sum + (1 << (32 - exponent))}
# This table gives the crc (without conditioning) of every possible # _octet_ from 0 to 255. Each _octet_ is a polynomial of degree 7, # octet[7] + octet[6] * x + ... + octet[0] * x**7 # Then remainder = Table[octet] is the remainder from # _octet_ times x**32 divided by Divisor, # remainder[31] + remainder[30] + ... + remainder[0] * x**31 Table = Array.new(256) do |octet| # Find remainder from polynomial long division. # octet[ 7] * x**32 + ... + octet[0] * x**39 # Divisor[32] * x**0 + ... + Divisor[0] * x**32 remainder = octet (0..7).each do |i| # Find next term of quotient. To simplify the code, # we assume that Divisor[0] is 1, and we only check # remainder[i]. We save remainder, forget quotient. if remainder[i].zero? # Next term of quotient is 0 * x**(7 - i). # No change to remainder. else # Next term of quotient is 1 * x**(7 - i). Multiply # this term by Divisor, then subtract from remainder. # * Multiplication uses left shift :<< to align # the x**(39 - i) terms. # * Subtraction uses bitwise exclusive-or :^. remainder ^= (Divisor << i) end end remainder >> 8 # Remove x**32 to x**39 terms. end
module_function
def crc32(string, crc = 0) # Pre-conditioning: Flip all 32 bits. Without this step, a string # preprended with extra "\0" would have same crc32 value. crc ^= 0xffff_ffff
# Iterate octets to perform polynomial long division. string.each_byte do |octet|
# Update _crc_ by continuing its polynomial long division. # Our current remainder is old _crc_ times x**8, plus # new _octet_ times x**32, which is # crc[32] * x**8 + crc[31] * x**9 + ... + crc[8] * x**31 \ # + (crc[7] + octet[7]) * x**32 + ... \ # + (crc[0] + octet[0]) * x**39 # # Our new _crc_ is the remainder from this polynomial divided by # Divisor. We split the terms into part 1 for x**8 to x**31, and # part 2 for x**32 to x**39, and divide each part separately. # Then remainder 1 is trivial, and remainder 2 is in our Table.
remainder_1 = crc >> 8 remainder_2 = Table[(crc & 0xff) ^ octet]
# Our new _crc_ is sum of both remainders. (This sum never # overflows to x**32, so is not too big for Divisor.) crc = remainder_1 ^ remainder_2 end
# Post-conditioning: Flip all 32 bits. If we later update _crc_, # this step cancels the next pre-conditioning. crc ^ 0xffff_ffff end
end
printf "0x%08x\n", CRC.crc32("The quick brown fox jumps over the lazy dog")
- => 0x414fa339</lang>
Tcl
<lang tcl>package require Tcl 8.6
set data "The quick brown fox jumps over the lazy dog" puts [format "%x" [zlib crc32 $data]]</lang> Which produces this output:
414fa339
Alternatively, with older versions of Tcl:
<lang tcl>package require crc32 puts [format "%x" [crc::crc32 $data]]</lang> With the same input data, it produces identical output.