CRC-32

CRC-32 is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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>

1. include <string.h>
2. 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

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

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")

1. => 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:

Library: Tcllib (Package: crc32)

<lang tcl>package require crc32 puts [format "%x" [crc::crc32 $data]]</lang> With the same input data, it produces identical output.