#include "include/jcrc.h"

Detailed Description

Cyclic Redundacy Check (CRC)

See also: https://en.wikipedia.org/wiki/Cyclic_redundancy_check; https://reveng.sourceforge.io/crc-catalogue/all.htm

A cyclic redundancy check (CRC) is an error-detecting code commonly used in digital networks and storage devices to detect accidental changes to digital data. Blocks of data entering these systems get a short check value attached, based on the remainder of a polynomial division of their contents. On retrieval, the calculation is repeated and, in the event the check values do not match, corrective action can be taken against data corruption. CRCs can be used for error correction (see bitfilters)

CRCs are so called because the check (data verification) value is a redundancy (it expands the message without adding information) and the algorithm is based on cyclic codes. CRCs are popular because they are simple to implement in binary hardware, easy to analyze mathematically, and particularly good at detecting common errors caused by noise in transmission channels. Because the check value has a fixed length, the function that generates it is occasionally used as a hash function

Introduction

CRCs are based on the theory of cyclic error-correcting codes. The use of systematic cyclic codes, which encode messages by adding a fixed-length check value, for the purpose of error detection in communication networks, was first proposed by W. Wesley Peterson in 1961.[2] Cyclic codes are not only simple to implement but have the benefit of being particularly well suited for the detection of burst errors: contiguous sequences of erroneous data symbols in messages. This is important because burst errors are common transmission errors in many communication channels, including magnetic and optical storage devices. Typically an n-bit CRC applied to a data block of arbitrary length will detect any single error burst not longer than n bits, and the fraction of all longer error bursts that it will detect is approximately (1 − 2−n)

Specification of a CRC code requires definition of a so-called generator polynomial. This polynomial becomes the divisor in a polynomial long division, which takes the message as the dividend and in which the quotient is discarded and the remainder becomes the result. The important caveat is that the polynomial coefficients are calculated according to the arithmetic of a finite field, so the addition operation can always be performed bitwise-parallel (there is no carry between digits)

In practice, all commonly used CRCs employ the finite field of two elements, GF(2). The two elements are usually called 0 and 1, comfortably matching computer architecture

A CRC is called an n-bit CRC when its check value is n bits long. For a given n, multiple CRCs are possible, each with a different polynomial. Such a polynomial has highest degree n, which means it has n + 1 terms. In other words, the polynomial has a length of n + 1; its encoding requires n + 1 bits. Note that most polynomial specifications either drop the MSB or LSB, since they are always 1. The CRC and associated polynomial typically have a name of the form CRC-n-XXX as in the table below

The simplest error-detection system, the parity bit, is in fact a 1-bit CRC: it uses the generator polynomial x + 1 (two terms),[3] and has the name CRC-1

Specification

The concept of the CRC as an error-detecting code gets complicated when an implementer or standards committee uses it to design a practical system. Here are some of the complications:

Sometimes an implementation prefixes a fixed bit pattern to the bitstream to be checked. This is useful when clocking errors might insert 0-bits in front of a message, an alteration that would otherwise leave the check value unchanged
Usually, but not always, an implementation appends n 0-bits (n being the size of the CRC) to the bitstream to be checked before the polynomial division occurs. Such appending is explicitly demonstrated in the Computation of CRC article. This has the convenience that the remainder of the original bitstream with the check value appended is exactly zero, so the CRC can be checked simply by performing the polynomial division on the received bitstream and comparing the remainder with zero. Due to the associative and commutative properties of the exclusive-or operation, practical table driven implementations can obtain a result numerically equivalent to zero-appending without explicitly appending any zeroes, by using an equivalent, faster algorithm that combines the message bitstream with the stream being shifted out of the CRC register.
Sometimes an implementation exclusive-ORs a fixed bit pattern into the remainder of the polynomial division.
Bit order: Some schemes view the low-order bit of each byte as "first", which then during polynomial division means "leftmost", which is contrary to our customary understanding of "low-order". This convention makes sense when serial-port transmissions are CRC-checked in hardware, because some widespread serial-port transmission conventions transmit bytes least-significant bit first
Byte order: With multi-byte CRCs, there can be confusion over whether the byte transmitted first (or stored in the lowest-addressed byte of memory) is the least-significant byte (LSB) or the most-significant byte (MSB). For example, some 16-bit CRC schemes swap the bytes of the check value.
Omission of the high-order bit of the divisor polynomial: Since the high-order bit is always 1, and since an n-bit CRC must be defined by an (n + 1)-bit divisor which overflows an n-bit register, some writers assume that it is unnecessary to mention the divisor's high-order bit
Omission of the low-order bit of the divisor polynomial: Since the low-order bit is always 1, authors such as Philip Koopman represent polynomials with their high-order bit intact, but without the low-order bit (the x 0 x^{0} or 1 term). This convention encodes the polynomial complete with its degree in one integer

These complications mean that there are three common ways to express a polynomial as an integer: the first two, which are mirror images in binary, are the constants found in code; the third is the number found in Koopman's papers. In each case, one term is omitted. So the polynomial x 4 + x + 1 x^{4}+x+1 may be transcribed as:

0x3 = 0b0011, representing x 4 + ( 0 x 3 + 0 x 2 + 1 x 1 + 1 x 0 ) {\displaystyle x^{4}+(0x^{3}+0x^{2}+1x^{1}+1x^{0})} (MSB-first code)
0xC = 0b1100, representing ( 1 x 0 + 1 x 1 + 0 x 2 + 0 x 3 ) + x 4 {\displaystyle (1x^{0}+1x^{1}+0x^{2}+0x^{3})+x^{4}} (LSB-first code)
0x9 = 0b1001, representing ( 1 x 4 + 0 x 3 + 0 x 2 + 1 x 1 ) + x 0 {\displaystyle (1x^{4}+0x^{3}+0x^{2}+1x^{1})+x^{0}} (Koopman notation)

CRC Representations
		Polynomial representations
Name	Uses	Normal	Reversed	Reciprocal	Reversed reciprocal
CRC-5-USB	USB token packets	0x05	0x14	0x09	0x12
CRC-7	telecom systems, ITU-T G.707, ITU-T G.832, MMC, SD	0x09	0x48	0x11	0x44
CRC-8-CCITT	ITU-T I.432.1; ATM, ISDN HEC and cell delineation; SMBus PEC	0x07	0xE0	0xC1	0x83
CRC-11	FlexRay	0x385	0x50E	0x21D	0x5C2
CRC-12	telecom systems	0x80F	0xF01	0xE03	0xC07
CRC-16-CCITT	known as CRC-CCITT	0x1021	0x8408	0x811	0x8810
CRC-16-IBM	USB, many others; also known as CRC-16 and CRC-16-ANSI	0x8005	0xA001	0x4003	0xC002
CRC-24-Radix-64	OpenPGP, RTCM104v3	0x864CFB	0xDF3261	0xBE64C3	0xC3267D
CRC-32	ISO/IEC/IEEE 802-3 (Ethernet), many others	0x04C11DB7	0xEDB88320	0xDB710641	0x82608EDB
CRC-32C	Castagnoli; iSCSI	0x1EDC6F41	0x82F63B78	0x05EC76F1	0x8F6E37A0
CRC-64-ECMA	ECMA-182 p. 51, XZ Utils	0x42F0E1EBA9EA3693	0xC96C5795D7870F42	0x92D8AF2BAF0E1E85	0xA17870F5D4F51B49
CRC-64-ISO	ISO 3309 (HDLC), Swiss-Prot/TrEMBL	0x000000000000001B	0xD800000000000000	0xB000000000000001	0x800000000000000D

For API Documentation:

See also: ProtocolPP::jarray; ProtocolPP::jcrc; ProtocolPP::jmodes; ProtocolPP::jintegrity

For Additional Documentation:

See also: jarray; jcrc; jmodes; jintegrity

The source code contained or described herein and all documents related to the source code (herein called "Material") are owned by John Peter Greninger and Sheila Rocha Greninger. Title to the Material remains with John Peter Greninger and Sheila Rocha Greninger. The Material contains trade secrets and proprietary and confidential information of John Peter Greninger and Sheila Rocha Greninger. The Material is protected by worldwide copyright and trade secret laws and treaty provisions. No part of the Material may be used, copied, reproduced, modified, published, uploaded, posted, transmitted, distributed, or disclosed in any way without prior express written consent of John Peter Greninger and Sheila Rocha Greninger (both are required)

No license under any patent, copyright, trade secret, or other intellectual property right is granted to or conferred upon you by disclosure or delivery of the Materials, either expressly, by implication, inducement, estoppel, or otherwise. Any license under such intellectual property rights must be express and approved by John Peter Greninger and Sheila Rocha Greninger in writing

Licensing information can be found at www.protocolpp.com/license with use of the binary forms permitted provided that the following conditions are met:

Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution
Any and all modifications must be returned to John Peter Greninger at GitHub.com https://github.com/jpgreninger/protocolpp for evaluation. Inclusion of modifications in the source code shall be determined solely by John Peter Greninger. Failure to provide modifications shall render this license NULL and VOID and revoke any rights to use of Protocol++®
Commercial use (incidental or not) requires a fee-based license obtainable at www.protocolpp.com/shop
Academic or research use requires prior written and notarized permission from John Peter and Sheila Rocha Greninger

Use of the source code requires purchase of the source code. Source code can be purchased at www.protocolpp.com/shop

US Copyrights at https://www.copyright.gov/
- TXu002059872 (Version 1.0.0)
- TXu002066632 (Version 1.2.7)
- TXu002082674 (Version 1.4.0)
- TXu002097880 (Version 2.0.0)
- TXu002169236 (Version 3.0.1)
- TXu002182417 (Version 4.0.0)
- TXu002219402 (Version 5.0.0)
- TXu002272076 (Version 5.2.1)
- TXu002383571 (Version 5.4.3)

The name of its contributor may not be used to endorse or promote products derived from this software without specific prior written permission and licensing

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER AND CONTRIBUTOR "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE

The documentation for this class was generated from the following file:

include/jcrc.h