CRC-32: Difference between revisions
→{{header|Go}}: added implementation |
|||
Line 72: | Line 72: | ||
414fa339 |
414fa339 |
||
</pre> |
</pre> |
||
=={{header|Icon}} and {{header|Unicon}}== |
|||
<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) # quick implementation |
|||
every crc := iand(ixor(crcL[iand(255,ixor(crc,ord(!s)))+1],ishift(crc,-8)),mask) |
|||
return hexstring(ixor(crc,mask)) |
|||
end</lang> |
|||
{{libheader|Icon Programming Library}} |
|||
[http://www.cs.arizona.edu/icon/library/src/procs/hexcvt.icn hexcvt.icnprovides hex and hexstring] |
|||
[http://www.cs.arizona.edu/icon/library/src/procs/printf.icn printf.icnprovides formatting] |
|||
Output:<pre>crc("The quick brown fox jumps over the lazy dog")=414FA339 - implementation is correct</pre> |
|||
=={{header|J}}== |
=={{header|J}}== |
Revision as of 04:24, 9 December 2011
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
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
<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) # quick implementation every crc := iand(ixor(crcL[iand(255,ixor(crc,ord(!s)))+1],ishift(crc,-8)),mask) return hexstring(ixor(crc,mask))
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>
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.