6.10 Cyclic Redundancy Check (CRC)

Bigloo provides several known cyclic redundancy checks as well as means to create custom checks.

Usually CRCs are executed starting with the leftmost bit inside a byte (big endian). However, especially for serial-port transmissions, a scheme where the least-significant bit is processed first is desirable. Bigloo’s CRC procedures accept a key-parameter (:big-endian) (by default #t) which allows to change this behavior.

The following CRCs (given with the associated polynomial) are provided:

• itu-4: 0x3
• epc-5: 0x9
• itu-5: 0x15
• usb-5: 0x5
• itu-6: 0x3
• 7: 0x9
• atm-8: 0x7
• ccitt-8: 0x8d
• dallas/maxim-8: 0x31
• 8: 0xd5
• sae-j1850-8: 0x1d
• 10: 0x233
• 11: 0x385
• 12: 0x80f
• can-15: 0x4599
• ccitt-16: 0x1021
• dnp-16: 0x3d65
• ibm-16: 0x8005
• 24: 0x5d6dcb
• radix-64-24: 0x864cfb
• 30: 0x2030b9cf
• ieee-32: 0x4c11db7
• c-32: 0x1edc6f41
• k-32: 0x741b8cd7
• q-32: 0x814141ab
• iso-64: 0x1b
• ecma-182-64: 0x42f0e1eba9ea3693

bigloo procedure: crc-names

Returns a list of all provided CRCs (itu-4, epc-5, etc.).

bigloo procedure: crc-polynomial name

bigloo procedure: crc-polynomial-le name

Returns the polynomial for the given name. The -le variant returns the little endian polynomial.

(crc-polynomial 'ieee-32)
    -| #e79764439 ;; == #ex4c11bd7
(crc-polynomial 24)
    -| 6122955    ;; == #x5d6dcb

bigloo procedure: crc-length name

Returns the length of the specified CRC.

bigloo procedure: crc name obj [:init 0] [:final-xor 0] [:big-endian? #t]

bigloo procedure: crc-string name str::bstring [:init 0] [:final-xor 0] [:big-endian? #t]

bigloo procedure: crc-port name p::input-port [:init 0] [:final-xor 0] [:big-endian? #t]

bigloo procedure: crc-mmap name m::mmap [init 0] [:final-xor 0] [big-endian? #t]

bigloo procedure: crc-file name f::bstring [init 0] [:final-xor 0] [big-endian? #t]

Computes the CRC of the given object. name must be one of the provided CRC-algorithms. The optional parameter init can be used to initialize the CRC. The result of the CRC will be XORed with final-xor. The result will however be of the CRC’s length. That is, even if final-xor is bigger then the CRC’s length only the relevant bits will be used to perform the final XOR.

The result will be a number. Depending on the CRC this number can be a fixnum, an elong, or an llong.

The following example mimicks the UNIX cksum command:

(module cksum (main main))
(define (main args)
  (let loop ((sum (crc-file 'ieee-32 (cadr args)))
             (size (elong->fixnum (file-size (cadr args)))))
    (if (=fx size 0)
        (printf "~a ~a ~a\n"
                (bit-andllong #lxFFFFFFFF (elong->llong (bit-notelong sum)))
                (file-size (cadr args))
                (cadr args))
        (loop (crc-string 'ieee-32
                          (string (integer->char-ur (bit-and size #xFF)))
                          :init sum)
	      (bit-rsh size 8)))))

In the following example we implement OpenPGP’s CRC-24:

(define (openpgp-crc-24 str)
  (crc-string 'radix-64-24 str :init #xB704CE))

Be aware that many common CRCs use -1 as init value and invert the result. For compatibility with other implementations you might want to try one of the following alternatives:

(define (alt1 name obj) (crc name obj :init -1))
(define (alt2 name obj) (crc name obj :final-xor -1))
(define (alt3 name obj) (crc name obj :init -1 :final-xor -1))

Bigloo provides means to create additional CRCs: one can either simply provide a new polynomial or use Bigloo’s low level functions.

bigloo procedure: register-crc! name poly len

Adds the given CRC to Bigloo’s list. Name can be of any type (crc will use assoc to find it in its list). The polynomial can be either a fixnum, an elong or an llong. len should give the CRCs size. The type of the polynomial and the given len must be consistent. On a 32 bit machine the following CRC registration would be invalid and yield undefined results:

(register-crc! 'invalid 1337 55)

As 55 is bigger than the fixnum’s bit-size calling crc with this CRC will yield undefinde results.

bigloo procedure: crc-long::long c::char crc::long poly::long len::long

bigloo procedure: crc-elong::elong c::char crc::elong poly::elong len::long

bigloo procedure: crc-llong::llong c::char crc::llong poly::llong len::long

bigloo procedure: crc-long-le::long c::char crc::long poly::long len::long

bigloo procedure: crc-elong-le::elong c::char crc::elong poly::elong len::long

bigloo procedure: crc-llong-le::llong c::char crc::llong poly::llong len::long

These function perform a CRC operation on one byte. The previously described functions are based on these low level functions. The result of all the low level functions will return values that are not cut to the correct length. Usually a crc is done in a loop, and one needs to bit-and only when returning the result. Polynomials can be given with or without the high-order bit.

For instance we could implement openpgp-crc24 as follows:

(define *openpgp-init* #xB704CE)
(define *radix-64-24-poly* #x864CFB)
(define (openpgp-crc-24 str)
  (let loop ((i 0)
             (crc *openpgp-init*))
    (if (=fx i (string-length str))
        (bit-and crc #xFFFFFF) ;; cut to correct length (24 bits)
        (loop (+fx i 1)
              (crc-long (string-ref str i) crc *radix-64-24-poly* 24)))))

bigloo procedure: crc-polynomial-be->le len polynomial

Returns the little endian variant of a given polynomial.

This document was generated on March 31, 2014 using texi2html 5.0.