1[library Boost.CRC 2 [quickbook 1.5] 3 [version 1.5] 4 [id crc] 5 [dirname crc] 6 [copyright 2001 2003 2012 Daryle Walker] 7 [purpose Cyclic Redundancy Code computation] 8 [category Miscellaneous] 9 [authors [Walker, Daryle]] 10 [license 11 Distributed under the Boost Software License, Version 1.0. 12 (See the accompanying file LICENSE_1_0.txt or a copy at 13 [@http://www.boost.org/LICENSE_1_0.txt]) 14 ] 15 [source-mode c++] 16] 17 18[/ Macros ] 19[def __RMCA__ Rocksoft\u2122 Model CRC Algorithm] 20 21[section:motivation What is Boost.CRC?] 22 23CRCs (cyclic redundancy codes) is one common technique to confirming data 24integrity after transmission. The [*Boost.CRC] library provides access to two 25styles of CRC computation, one as a function template, the other as a function 26template and two computation object class templates, where the two class 27templates differ in speed. 28 29[endsect] 30[section:introduction Introduction] 31 32[note 33 Some of the introductory material is based on 34 [@http://www.ross.net/crc/download/crc_v3.txt ['A Painless Guide to CRC 35 Error Detection Algorithms]] by Ross N. Williams at his 36 [@http://www.ross.net/crc/ [*The CRC Pitstop]] site. 37] 38 39When binary data is transmitted, usually electronically, there is a chance that 40the data gets corrupted. One method to pick up said corruption is to generate 41some value that is coded from the original data, send said value to the 42receiver, then confirm that the received data generates the same value when it's 43coded at the destination. 44 45There are several possibilities after the receiver's check: 46 47* The check value matches at both places and the data was transmitted intact. 48* The data got corrupted and the check values do not match. 49* The data is intact, but the check value got corrupted. This can't the 50 distinguished from the previous case, but is a (relatively) safe false 51 positive. 52* Either the data and/or check value gets corrupted, but such that the results 53 of the check-coding are still consistent. This is a dangerous false negative! 54 55The way to minimize false negatives is to choose coding algorithms that cause a 56lot of churn per input, especially a variable amount. 57 58The check values are known as [*checksum]s because they are used to /check/ for 59data consistency and the first coding algorithms were addition- (i.e. 60['sum]ming-) based. 61 62[section:intro_crcs CRCs] 63 64[*Cyclic Redundancy Codes] are a type of consistency check that treats the 65message data as a (long) dividend of a modulo-2 polynomial division. Modulo-2 66arithmetic doesn't use carries/borrows when combining numbers. A specific CRC 67defines a set number of bits to work on at a time, where said number is also the 68degree of a fixed polynomial (with modulo-2 coefficients) used as a divisor. 69 70Since ordering doesn't apply to modulo arithmetic, the check between the current 71high part of the dividend and the trial partial product (of the divisor and the 72trial new quotient coefficient) is done by seeing if the highest-degree 73coefficient of the dividend is one. (The highest-degree coefficient of the 74divisor must be one by definition, since it's the only non-zero choice.) The 75remainder after the division is finished is used as the basis of the CRC 76checksum. 77 78[section:intro_crcs_impl CRC Implementation] 79 80For a given degree /x/ for the modulo-2 polynomial divisor, the remainder will 81have at most /x/ terms (from degree /x/ - 1 down to the constant term). The 82coefficients are modulo-2, which means that they can be represented by 0's and 831's. So a remainder can be modeled by an (unsigned) integer of at least /x/ 84bits in *width*. 85 86The divisor must have its /x/ degree term be one, which means it is always known 87and can be implied instead of having to explicitly include in representations. 88Its lower /x/ terms must be specified, so a divisor can be modeled the same way 89as remainders. With such a modeling, the divisor representation could be said 90to be truncated since the uppermost term's value is implied and not stored. 91 92The remainder and [*(truncated) divisor polynomial]s are stored as basic 93computer integers. This is in contrast to the dividend, which is modeled from 94the input stream of data bits, where each new incoming bit is the next lower 95term of the dividend polynomial. Long division can be processed in piecemeal, 96reading new upper terms as needed. This maps to reading the data a byte (or 97bit) at a time, generating updated remainders just-in-time, without needing to 98read (and/or store(!)) the entire data message at once. 99 100Long division involves appending new dividend terms after the previous terms 101have been processed into the (interim) remainder. So the remainder it the only 102thing that has to change during each division step; a new input byte (or bit) is 103combined with the remainder to make the interim dividend, and then combined with 104the partial product (based on the divisor and top dividend bit(s)) to become a 105remainder again. 106 107[endsect] 108[section:intro_crcs_augment Message Augmentation] 109 110When all of the input data has been read during division, the last /x/ bits are 111still stuck in the interim remainder. They have not been pushed through the 112division steps; to do so, /x/ zero-valued extra bits must be passed into the 113system. This ensures all of the message's data bits get processed. The 114post-processed remainder is the checksum. The system requires the message to be 115*augmented* with /x/ extra bits to get results. 116 117Alternatively, if the post-division augmentation bits are the expected checksum 118instead, then the remainder will "subtract" the checksum with itself, giving 119zero as the final remainder. The remainder will end up non-zero if bit errors 120exist in either the data or checksum or both. This option requires the checksum 121to be fed from highest-order bit first on down (i.e. big endian). 122 123Exploiting the properties of how the division is carried out, the steps can be 124rearranged such that the post-processing zero-valued bits are not needed; their 125effect is merged into the start of the process. Such systems read *unaugmented* 126messages and expose the checksum directly from the interim remainder afterwards. 127(You can't use the "augment-message-with-checksum-and-zero-check" technique with 128this, of course.) 129 130[endsect] 131[section:intro_crcs_param Other CRC Parameters] 132 133Since long division proceeds from the uppermost terms on down, it's easiest to 134treat an incoming byte as the uppermost unprocessed terms, and to read the bits 135within that byte as the highest-order bit is the uppermost unprocessed term and 136go down. However, some hardware implementations have an easier time reading 137each byte from the lowest-order bit and go up. To simulate those systems in 138software, the program needs to be flagged that *input reflection* needs to be 139applied. Reflecting a built-in integer reverses the order of its bits, such 140that the lowest- and highest-order bits swap states, the next-lowest- and 141next-highest-order bits swap, etc. The input reflection can be done by 142reflecting each byte as it comes in or keeping the bytes unchanged but reflect 143the other internal functioning. The latter sounds harder, but what it usually 144done in the real world, since it's a one-time cost, unlike reflecting the bytes. 145 146Similarly, the final remainder is processed by some hardware in reverse order, 147which means software that simulate such systems need to flag that *output 148reflection* is in effect. 149 150Some CRCs don't return the remainder directly (reflected or not), but add an 151extra step complementing the output bits. Complementing turns 1 values into 0 152values and vice versa. This can simulated by using a XOR (exclusive-or) bit 153mask of all 1-values (of the same bit length as the remainder). Some systems 154use a *final XOR mask* that isn't all 1-values, for variety. (This mask takes 155place /after/ any output reflection.) 156 157At the other end, the built-in-integer register normally starts at zero as the 158first bytes are read. Instead of just doing nothing but load input bits for /x/ 159steps, some CRC systems use a non-zero *initial remainder* to add extra 160processing. This initial value has to be different for the augmented versus 161un-augmented versions of the same system, due to possible incorporation with the 162zero-valued augment bits. 163 164[endsect] 165[section:intro_crcs_rmca Compact CRC Parameter Specification] 166 167The __RMCA__, or RMCA for short, was designed by Ross Williams to describe all 168the specification points of a given CRC system (quoted): 169 170[variablelist RMCA Parameters 171 [[WIDTH] [This is the width of the algorithm expressed in bits. This 172 is one less than the width of the Poly.]] 173 [[POLY] [This parameter is the poly. This is a binary value that 174 should be specified as a hexadecimal number. The top bit of the 175 poly should be omitted. For example, if the poly is 10110, you 176 should specify 06. An important aspect of this parameter is that it 177 represents the unreflected poly; the bottom bit of this parameter 178 is always the LSB of the divisor during the division regardless of 179 whether the algorithm being modelled is reflected.]] 180 [[INIT] [This parameter specifies the initial value of the register 181 when the algorithm starts. This is the value that is to be assigned 182 to the register in the direct table algorithm. In the table 183 algorithm, we may think of the register always commencing with the 184 value zero, and this value being XORed into the register after the 185 N'th bit iteration. This parameter should be specified as a 186 hexadecimal number.]] 187 [[REFIN] [This is a boolean parameter. If it is FALSE, input bytes are 188 processed with bit 7 being treated as the most significant bit 189 (MSB) and bit 0 being treated as the least significant bit. If this 190 parameter is FALSE, each byte is reflected before being processed.]] 191 [[REFOUT] [This is a boolean parameter. If it is set to FALSE, the 192 final value in the register is fed into the XOROUT stage directly, 193 otherwise, if this parameter is TRUE, the final register value is 194 reflected first.]] 195 [[XOROUT] [This is an W-bit value that should be specified as a 196 hexadecimal number. It is XORed to the final register value (after 197 the REFOUT) stage before the value is returned as the official 198 checksum.]] 199] 200 201His description assumes an octet-sized byte. The /POLY/ is the (truncated) 202divisor. The /INIT/ is the initial remainder, assuming the unaugmented version 203of CRC processing is used. (If you're using an augmented-style CRC, you have to 204undo the effect of the built-in zero-augment before initialization.) 205 206[endsect] 207 208The two function templates and two class templates in this library provide ways 209to carry out CRC computations. You give the various __RMCA__ parameters as 210template parameters and/or constructor parameters. You then submit all the 211message data bytes at once (for the functions) or piecemeal (for the class 212objects). 213 214[endsect] 215 216Note that some error-detection techniques merge their checksum results within 217the message data, while CRC checksums are either at the end (when augmented, 218without either kind of reflection, with a bit-width that's a multiple of byte 219size, and no XOR mask) or out-of-band. 220 221[endsect] 222[section:crc_basic Theoretical CRC Computer] 223 224 #include <cstddef> // for std::size_t 225 226 namespace boost 227 { 228 template < std::size_t Bits > 229 class crc_basic; 230 } 231 232The [*`boost::crc_basic`] class template acts as an unaugmented-CRC processor 233that can accept input at the bit-level. It only takes one __RMCA__ parameter as 234a template parameter, the /WIDTH/, which determines the built-in unsigned integer 235type used for division registers. The other __RMCA__ parameters can be passed 236on through the constructor. (Most of the parameters have defaults.) 237 238The integer type used for registers is published as `value_type`, while the 239__RMCA__ attributes can be discovered as: 240 241[table:crc_basic_rmca RMCA Parameters in boost::crc_basic 242 [[Parameter] [Member Name] [Kind] [Expression Type]] 243 [[['WIDTH]] [`bit_count`] [class-static immutable data member] [`std::size_t`]] 244 [[['POLY]] [`get_truncated_polynominal`] [`const` member function] [`value_type`]] 245 [[['INIT]] [`get_initial_remainder`] [`const` member function] [`value_type`]] 246 [[['REFIN]] [`get_reflect_input`] [`const` member function] [`bool`]] 247 [[['REFOUT]] [`get_reflect_remainder`] [`const` member function] [`bool`]] 248 [[['XOROUT]] [`get_final_xor_value`] [`const` member function] [`value_type`]] 249] 250 251Since most of the parameters are specified at run-time, you can reuse a single 252computer object for separate runs with differing parameters. The type uses the 253automatically-defined copy/move/assign and destruction routines. 254 255[import ./crc_examples.cpp] 256[crc_basic_reuse] 257 258This example necessarily demonstrates input and output. There is one output 259member function, `checksum` that returns the remainder from the CRC steps plus 260any post-processing reflection and/or XOR-masking. There are several options 261to submit input data for processing: 262 263[table:crc_basic_input Member Functions for Input in boost::crc_basic 264 [[Member Function] [Input Type/Style]] 265 [[`process_bit`] [A single bit.]] 266 [[`process_bits`] [A specified number of bits within the given byte. 267 Reading starts from the highest-order desired bit.]] 268 [[`process_byte`] [An entire byte. The bits within the byte are read in an 269 order consistent with `get_reflect_input`.]] 270 [[`process_block`] [All bytes in the range. The range is defined by a 271 pointer to the first byte and another pointer to one (byte) past-the-end.]] 272 [[`process_bytes`] [All bytes in the range. The range is defined by a 273 pointer to the first byte and a count of number of bytes to read.]] 274] 275 276The input functions currently do not return anything. 277 278[crc_piecemeal_run] 279 280The input-influenced state of a computer object may be read with the 281`get_interim_remainder` member function. An object may be loaded with the same 282kind of state with the one-argument version of the `reset` member function. 283The state is the remainder from the CRC operations performed on all the 284already-entered input, without any output post-processing. 285 286The two functions can be used together to save the state to a persistent medium 287and restore it later. Note that the __RMCA__ parameters have to saved/restored 288via other means, if they're not fixed within a program. 289 290Calling `reset` with no arguments sets the interim remainder to what /INIT/ was 291set at object construction. This lets one computer object be used for 292independent runs with separate data messages using the same CRC standard. 293 294[endsect] 295[section:crc_optimal Optimized CRC Computer] 296 297 #include <boost/cstdint.hpp> // for boost::uintmax_t 298 #include <cstddef> // for std::size_t 299 300 namespace boost 301 { 302 template < std::size_t Bits, uintmax_t TruncPoly, uintmax_t InitRem, 303 uintmax_t FinalXor, bool ReflectIn, bool ReflectRem > 304 class crc_optimal; 305 } 306 307The [*`boost::crc_optimal`] class template acts as an unaugmented-CRC processor 308that can accept input at the byte-level. It takes all the __RMCA__ parameters 309as template parameters. Like in `crc_basic`, the /WIDTH/ stays as the first 310parameter and determines the built-in unsigned integer type used for division 311registers. The other __RMCA__ parameters move up to the template parameter 312field in the same relative order they were in the `crc_basic` constructor. 313(Some parameters have defaults.) Objects based from `crc_optimal` can either be 314default-constructed, giving it the same behavior as a `crc_basic` object with 315the equivalent settings, or use one parameter, which overrides the initial 316remainder value[footnote i.e. The interim-remainder before any input is read.] 317without permanently affecting the initial-remainder attribute. 318 319Besides template parameters and construction, `crc_optimal` differs from 320`crc_basic` interface-wise by: 321 322* Adding five class-static immutable data members corresponding to the new 323 template parameters. 324 [table:crc_optimal_rmca Additional RMCA Expressions in boost::crc_optimal 325 [[New Member] [Equivalent]] 326 [[`truncated_polynominal`] [`get_truncated_polynominal`]] 327 [[`initial_remainder`] [`get_initial_remainder`]] 328 [[`reflect_input`] [`get_reflect_input`]] 329 [[`reflect_remainder`] [`get_reflect_remainder`]] 330 [[`final_xor_value`] [`get_final_xor_value`]] 331 ] 332* Removing the `process_bit` and `process_bits` member functions. 333* Adding two versions of the `operator ()` member function. The single-argument 334 version forwards to `process_byte`, making it suitable to STL algorithms that 335 take (and possibly return) function objects[footnote Like `std::for_each`.]. 336 The argument-less version forwards to `checksum`, making it suitable for STL 337 algorithms that expect generator objects[footnote Albeit this object won't 338 change its return value within code that only uses it as a generator.]. 339* Merging the two `reset` member functions into one. (It uses a single 340 parameter that can have a default argument). 341 342The major difference between `crc_basic` and `crc_optimal` is the internals. 343Objects from `crc_basic` run their CRC algorithm one bit at a time, no matter 344which unit is used as input. Objects from `crc_optimal`, when /WIDTH/ is at 345least `CHAR_BIT`[footnote i.e. The optimizations are suspended if the /WIDTH/ 346only justifies using part of a single byte.], use a byte-indexed table-driven CRC 347algorithm which is a *lot* faster than processing individual bits. 348 349Since all of the parameters are specified at compile-time, you cannot reuse a 350single computer object for separate runs with differing parameters. The type 351uses the automatically-defined copy/move/assign and destruction routines. 352 353[endsect] 354[section:crc_function CRC Function] 355 356 #include <boost/cstdint.hpp> // for boost::uintmax_t 357 #include <boost/integer.hpp> // for boost::uint_t 358 #include <cstddef> // for std::size_t 359 360 namespace boost 361 { 362 template < std::size_t Bits, uintmax_t TruncPoly, uintmax_t InitRem, 363 uintmax_t FinalXor, bool ReflectIn, bool ReflectRem > 364 typename uint_t<Bits>::fast crc( void const *buffer, std::size_t 365 byte_count ); 366 } 367 368The [*`boost::crc`] function template computes the unaugmented CRC of a single 369data block in one pass. It has the same template parameter list as 370`boost::crc_optimal`, which it uses for implementation. This function saves you 371the trouble of setting up and using the `boost::crc_optimal` object manually. 372 373[endsect] 374[section:acrc_function Augmented-CRC Function] 375 376 #include <boost/cstdint.hpp> // for boost::uintmax_t 377 #include <boost/integer.hpp> // for boost::uint_t 378 #include <cstddef> // for std::size_t 379 380 namespace boost 381 { 382 template < std::size_t Bits, uintmax_t TruncPoly > 383 typename uint_t<Bits>::fast augmented_crc( void const *buffer, 384 std::size_t byte_count, typename uint_t<Bits>::fast initial_remainder 385 = 0u ); 386 } 387 388The [*`boost::augmented_crc`] function computes the augmented-style CRC of a 389data block. Like `boost::crc`, the first two template parameters are the 390/WIDTH/ and /POLY/. However, the /INIT/ has moved to being a function 391parameter, after the data block's starting address and byte length, defaulting 392to zero if not given. 393 394This function uses modulo-2 division at its most raw, and so forfeits the 395/REFIN/, /REFOUT/, and /XOROUT/ attributes, setting them to `0` or `false`. 396Another difference from `boost::crc` is that a non-zero /INIT/ has to be skewed 397when used with this function. (No conversion functions are currently given.) 398 399[acrc_piecemeal_run] 400 401Since `augmented_crc` doesn't know when your data ends, you must supply the 402augment, either /WIDTH/ zero bits or the expected checksum. The augment can be 403either at the end of last data block or from an extra call. Remember that if an 404expected checksum is used as the augment, its bits must be arranged in 405big-endian order. Because `augmented_crc` reads byte-wise, while augments 406assume bit-wise reading, augmentations are valid only when /WIDTH/ is a multiple 407of the bits-per-byte ratio (`CHAR_BIT`). 408 409[endsect] 410[section:crc_samples Pre-Defined CRC Samples] 411 412 namespace boost 413 { 414 typedef crc_optimal<16, 0x8005, 0, 0, true, true> 415 crc_16_type; 416 417 typedef crc_optimal<16, 0x1021, 0xFFFF, 0, false, false> 418 crc_ccitt_false_t, crc_ccitt_type; 419 typedef crc_optimal<16, 0x1021, 0, 0, true, true> crc_ccitt_true_t; 420 421 typedef crc_optimal<16, 0x8408, 0, 0, true, true> crc_xmodem_type; 422 typedef crc_optimal<16, 0x1021, 0, 0, false, false> crc_xmodem_t; 423 424 typedef crc_optimal<32, 0x04C11DB7, 0xFFFFFFFF, 0xFFFFFFFF, true, true> 425 crc_32_type; 426 } 427 428Several sample CRC types are given, representing common CRC algorithms. The 429samples have now been checked against the 430[@http://regregex.bbcmicro.net/crc-catalogue.htm ['Catalogue of parametrised CRC 431algorithms]], leading to some new type-aliases corresponding to the corrected 432profiles. (Older, incorrect profiles keep their name for backwards 433compatibility.) However, this library is primarily concerned with CRC 434implementation, and not with determining "good" sets of CRC parameters. 435 436[table:crc_samples_list Common CRCs 437 [[Computer Type] [Standard(s)]] 438 [[`crc_16_type`] [BISYNCH, ARC, LHA, ZOO]] 439 [[`crc_ccitt_false_t`] [Commonly misidentified as the standard by CCITT]] 440 [[`crc_ccitt_type`] [`crc_ccitt_false_t` (I made the same mistake.)]] 441 [[`crc_ccitt_true_t`] [Designated by CCITT (Comit\u00E9 Consultatif 442 International T\u00E9l\u00E9graphique et T\u00E9l\u00E9phonique), KERMIT]] 443 [[`crc_xmodem_type`] [A mistake I didn't catch in defining 444 `crc_xmodem_t`.]] 445 [[`crc_xmodem_t`] [XMODEM, ZMODEM, ACORN]] 446 [[`crc_32_type`] [ADCCP, PKZip, libPNG, AUTODIN II, Ethernet, FDDI]] 447] 448 449[endsect] 450[section:end End Matter] 451[heading References] 452 453*The [@boost:/boost/crc.hpp CRC header] itself 454*Some [@boost:/libs/crc/test/crc_test.cpp test code] and some 455 [@boost:/libs/crc/test/crc_test2.cpp newer tests] that use the 456 [@boost:/libs/test/index.html Boost test library] 457*Some [@boost:/libs/crc/crc_example.cpp example code] 458 459[variablelist History 460 [[Boost 1.49.0] [Refined implementation, testing, and documentation. Some 461 interfaces were tweaked.]] 462 [[Boost 1.30.2 (estimated)] [Released an example program.]] 463 [[Boost 1.22.0] [First public release.]] 464] 465 466[heading Acknowledgments] 467 468For giving advice on compiler/C++ compliance, implementation, interface, 469algorithms, and bug reports: 470 471*Darin Adler 472*Beman Dawes 473*Doug Gregor 474*John Maddock 475*Joe Mariadassou 476*Jens Maurer 477*Vladimir Prus 478*Joel Young 479 480[variablelist Contributors 481 [[Michael Barr [@mailto:mbarr@netrino.com mbarr@netrino.com]] 482 [Wrote 483 [@http://www.netrino.com/Embedded-Systems/How-To/CRC-Calculation-C-Code 484 ["CRC Implementation Code in C]], a less-confusing guide to implementing 485 CRC algorithms. (Originally published as ["Slow and Steady Never Lost the 486 Race] in the January 2000 issue of [@http://www.embedded.com ['Embedded 487 Systems Programming]], pages 37\u201346. The web version used to be known 488 as [@http://www.netrino.com/Connecting/2000-01/ ['Easier Said Than Done]].) 489 ]] 490 [[Daryle Walker] 491 [Started the library and contributed the theoretical and optimal CRC 492 computation class templates and the CRC computing function template. 493 Contributed the test and example code. 494 ]] 495 [[Ross N. Williams] 496 [Wrote [@http://www.ross.net/crc/crcpaper.html ['A Painless Guide to CRC 497 Error Detection Algorithms]], a definitive source of CRC information. 498 ]] 499] 500 501[endsect] 502 503[xinclude autodoc.xml] 504