Bulletin number: 391 Products affected: D7205A Description: CRC documentation Component: crc.lib Date: Thu Apr 2 14:52:51 BST 1992 ----- Correction and improvement to documentation of CRC routines in occam toolset Dx205 The lead paragraph of the documentation in part 2 of the occam 2 toolset user manual of the routines in _crc.lib_ is incorrect. Here is a better description of the routines: The block CRC library provides two functions for calculating cyclic redundancy check values from byte strings. Such values can be of use in, for example, the generation of the frame check sequence (FCS) in data communications. A cyclic redundancy check value is the remainder from modulo 2 polynomial division. Consider bit sequences as representing the co-efficients of polynomials; for example, the bit sequence 10100100 (where the leading bit is the most significant bit) corresponds to P(x) = x^7 + x^5 + x^2. The routines in the library calculate the remainder of the modulo 2 polynomial division ( x^(k+n)H(x) + x^(n)F(x)) / G(x) where F(x) corresponds to _InputString_, G(x) corresponds to _PolynomialGenerator_, H(x) corresponds to _OldCRC_, k is the number of bits in _InputString_, and n is the word size in bits of the processor used (i.e. n is 16 or 32). (OldCRC can be viewed as the value that would be pre-loaded into the cyclic shift register that is part of hardware implementations of CRC generators.) When representing G(x) in the word PolynomialGenerator, note that there is an understood bit before the msb of PolynomialGenerator: for example, on a 16-bit processor, with G(x) = x^16 + x^12 + x^5 + 1, which is #11021, then PolynomialGenerator must be assigned #1021, as the bit corresponding to x^16 is understood. Thus, a value of #9603 for PolynomialGenerator, corresponds to G(x) = x^16 + x^15 + x^12 + x^10 + x^9 + x + 1, for a 16-bit processor. A similar situation holds on a 32-bit processor, so that G(x) = x^32 + x^26 + x^23 + x^22 + x^16 + x^12 + x^11 + x^10 + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1 is encoded in PolynomialGenerator as #04C11DB7. One can, however, calculate a 16-bit CRC on a 32-bit processor: say G(x) = x^16 + x^12 + x^5 + 1, then PolynomialGenerator is #10210000, as the most significant 16 bits of the 32-bit integer form a 16-bit generator; the least significant 16 bits of _OldCRC_ form the initial CRC value; and the calculated CRC is the most significant 16 bits of the result from _CRCFROMMSB_ and the least significant 16 bits of the result from _CRCFROMLSB_. -------------- Example of use -------------- Say we are transmitting information between two 32-bit transputers, and the message that we wish to transmit is the byte array [data FROM 4 FOR size.message], where there are (size.message) bytes in the message. Both the transmitter and receiver use the same 32-bit generating polynomial and OldCRC value. Then if we give CRCFROMMSB the message as input string, put the result into the first four bytes of _data_ and send this, then the receiver can either give the received _data_ (being (size.message) + 4 bytes long) to _CRCFROMMSB_ and expect a result of zero, or give the received [data FROM 4 FOR (SIZE message)] to _CRCFROMMSB_ and check that the result is equal to the INT contained in the received [data FROM 0 FOR 4]. These methods of checking for the receiver are equivalent. If the check fails then the transmitted data was corrupted and re-transmission can be requested; if the check passes then it is most probable that the data was transmitted without corruption - just how probable depends on many factors, for which one should see a proper exposition on CRCs. ----- Note: ----- The occam predefines _CRCBYTE_ and _CRCWORD_ can be chained together to help calculate a CRC from a byte string, and this is indeed the use to which they are put in _CRCFROMMSB_ and _CRCFROMLSB_, but because these latter routines shift the polynomial F(x) corresponding to _InputString_ by x^n, these routines should not be chained together over segments of a byte string to find its CRC; the whole string must be used in a single call to _CRCFROMMSB_ or _CRCFROMLSB_. The description of each routine also changes: CRCFROMMSB INT FUNCTION CRCFROMMSB (VAL []BYTE InputString, VAL INT PolynomialGenerator, VAL INT OldCRC) This routine is intended for strings in normal transputer format (little-endian). The most significant bit of the given string is taken to be bit-16 or bit-32, depending on the word size of the processor, of InputString[(SIZE InputString) - 1]. PolynomialGenerator, OldCRC and the result are all also in normal transputer format (little-endian). CRCFROMLSB INT FUNCTION CRCFROMLSB (VAL []BYTE InputString, VAL INT PolynomialGenerator, VAL INT OldCRC) This routine is provided to accommodate strings in big-endian format. The most significant bit of _InputString_ is taken to be bit 0 of _InputString[0]_. The generated CRC is given in big-endian format. _PolynomialGenerator_ and _OldCRC_ are taken to be in little-endian format. Further, the descriptions of the occam predefines _CRCWORD_ and _CRCBYTE_ on p13 of part 2 of the occam 2 toolset user manual could be better. A cyclic redundancy check value is the remainder from modulo 2 polynomial division. Consider bit sequences as representing the co-efficients of polynomials; for example, the bit sequence 10100100 (where the leading bit is the most significant bit) corresponds to P(x) = x^7 + x^5 + x^2. _CRCWORD_ and _CRCBYTE_ calculate the remainder of the modulo 2 polynomial division (x^(n)H(x) + F(x)) / G(x) where F(x) corresponds to _data_ (the whole word for _CRCWORD_; only the most significant byte for _CRCBYTE_), G(x) corresponds to _generator_, H(x) corresponds to _CRCIn_ and _n_ is the word size in bits of the processor used (i.e. n is 16 or 32). (CRCIn can be viewed as the value that would be pre-loaded into the cyclic shift register that is part of hardware implementations of CRC generators.) When representing G(x) in the word generator, note that there is an understood bit before the msb of generator: for example, on a 16-bit processor, with G(x) = x^16 + x^12 + x^5 + 1, which is #11021, then generator must be assigned #1021, as the bit corresponding to x^16 is understood. Thus, a value of #9603 for generator, corresponds to G(x) = x^16 + x^15 + x^12 + x^10 + x^9 + x + 1, for a 16-bit processor. A similar situation holds on a 32-bit processor, so that G(x) = x^32 + x^26 + x^23 + x^22 + x^16 + x^12 + x^11 + x^10 + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1 is encoded in generator as #04C11DB7. One can, however, calculate a 16-bit CRC on a 32-bit processor: say G(x) = x^16 + x^12 + x^5 + 1, then generator is #10210000, as the most significant 16 bits of the 32-bit integer form a 16-bit generator; (a) for _CRCWORD_: the least significant 16 bits of _CRCIn_ form the initial CRC value; the most significant 16 bits of _data_ form the data; and the calculated CRC is the most significant 16 bits of the result; (b) for _CRCBYTE_: the most significant 16 bits of _CRCIn_ form the initial CRC value; the next 8 bits of _CRCIn_ (the third most significant byte) form the byte of data; and the calculated CRC is the most significant 16 bits of the result. CRCWORD INT FUNCTION CRCWORD (VAL INT data, CRCIn, generator) Takes the whole of the word _data_ to correspond to F(x) in the above formula. CRCBYTE INT FUNCTION CRCBYTE (VAL INT data, CRCIn, generator) Takes the _most_ significant byte of _data_ to correspond to F(x) in the above formula. Note: The predefines _CRCBYTE_ and _CRCWORD_ can be chained together to help calculate a CRC from a string considered as one long polynomial. A simple chaining would calculate (x^(k)H(x) + F(x)) / G(x) where F(x) corresponds to the string and _k_ is the number of bits in the string. This is not the same CRC that is calculated by _CRCFROMMSB_ and _CRCFROMLSB_ in _crc.lib_, section xx.xxx, because these latter routines shift the numerator by x^n.