CRC-32
Implement Cyclic Redundancy Check (ISO 3309, ITU-T V.42, Gzip, PNG) as described in wikipedia. Algorithms are described on this page.
Use it to generate a checksum for the following ASCII encoded string of bytes "The quick brown fox jumps over the lazy dog"
C
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>
Go
<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
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>
Ruby
<lang ruby>module CRC
# Divisor is a polynomial of degree 32 in the GF(2) space. # We store Divisor in a 33-bit Integer; the polynomial is # Divisor[32] * x**0 + ... + 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))} #printf "0x%x\n", Divisor #printf "0x%x\n", Divisor >> 1
Table = Array.new(256) do |octet| # Find remainder of _octet_ divided by Divisor. # 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 #p Table.map {|i| "0x%08x" % i}
module_function
def crc32(string, crc = 0) crc ^= 0xffff_ffff string.bytes do |octet| # Update the crc by finding remainder of this dividend # octet[7] * x**0 + ... + octet[0] * x**7 + # crc[31] * x**8 + ... + crc[0] * x**39 # divided by Divisor. We split this dividend into two parts. # 1st part: octet[7] * x**0 + ... + crc[8] * x**31 # 2nd part: crc[7] * x**8 + ... + crc[0] * x**39 # We divide each part by Divisor; 1st remainder is trivial # and 2nd remainder is in our Table. remainder_1 = crc >> 8 remainder_2 = Table[(crc & 0xff) ^ octet]
# The crc equals the sum of both remainders. (This works because # the sum is degree 31 at most, so not too big for Divisor.) # * Addition of polynomials uses exclusive-or :^. crc = remainder_1 ^ remainder_2 end 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.