diff options
| author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-27 18:24:20 +0000 |
|---|---|---|
| committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-27 18:24:20 +0000 |
| commit | 483eb2f56657e8e7f419ab1a4fab8dce9ade8609 (patch) | |
| tree | e5d88d25d870d5dedacb6bbdbe2a966086a0a5cf /src/boost/libs/crc | |
| parent | Initial commit. (diff) | |
| download | ceph-483eb2f56657e8e7f419ab1a4fab8dce9ade8609.tar.xz ceph-483eb2f56657e8e7f419ab1a4fab8dce9ade8609.zip | |
Adding upstream version 14.2.21.upstream/14.2.21upstream
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'src/boost/libs/crc')
| -rw-r--r-- | src/boost/libs/crc/crc.html | 632 | ||||
| -rw-r--r-- | src/boost/libs/crc/crc_example.cpp | 75 | ||||
| -rw-r--r-- | src/boost/libs/crc/index.html | 14 | ||||
| -rw-r--r-- | src/boost/libs/crc/meta/libraries.json | 14 | ||||
| -rw-r--r-- | src/boost/libs/crc/test/Jamfile.v2 | 8 | ||||
| -rw-r--r-- | src/boost/libs/crc/test/crc_test.cpp | 756 | ||||
| -rw-r--r-- | src/boost/libs/crc/test/crc_test2.cpp | 637 |
7 files changed, 2136 insertions, 0 deletions
diff --git a/src/boost/libs/crc/crc.html b/src/boost/libs/crc/crc.html new file mode 100644 index 00000000..a11c0200 --- /dev/null +++ b/src/boost/libs/crc/crc.html @@ -0,0 +1,632 @@ +<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN"> +<html> +<head> +<meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1"> +<title>Boost CRC Library Documentation</title> +</head> + +<body text="black" bgcolor="white" link="blue" vlink="purple" alink="red"> + +<h1><img src="../../boost.png" alt="boost.png (6897 bytes)" +align="middle" width="277" height="86">Header <cite><<a +href="../../boost/crc.hpp">boost/crc.hpp</a>></cite></h1> + +<p>The header <cite><<a +href="../../boost/crc.hpp">boost/crc.hpp</a>></cite> supplies two +class templates in namespace <code>boost</code>. These templates define +objects that can compute the <dfn>CRC</dfn>, or cyclic redundancy code +(or check), of a given stream of data. The header also supplies +function templates to compute a CRC in one step.</p> + +<h2><a name="contents">Contents</a></h2> + +<ol> + <li><a href="#contents">Contents</a></li> + <li><a href="#header">Header Synopsis</a></li> + <li><a href="#rationale">Rationale</a></li> + <li><a href="#background">Background</a> + <ul> + <li><a href="#parameters">CRC Parameters</a></li> + </ul></li> + <li><a href="#crc_basic">Theoretical CRC Computer</a></li> + <li><a href="#crc_optimal">Optimized CRC Computer</a></li> + <li><a href="#usage">Computer Usage</a></li> + <li><a href="#crc_func">CRC Function</a></li> + <li><a href="#a_crc_func">Augmented-CRC Function</a></li> + <li><a href="#crc_ex">Pre-Defined CRC Samples</a></li> + <li><a href="#references">References</a></li> + <li><a href="#credits">Credits</a> + <ul> + <li><a href="#contributors">Contributors</a></li> + <li><a href="#acknowledgements">Acknowledgements</a></li> + <li><a href="#history">History</a></li> + </ul></li> +</ol> + +<h2><a name="header">Header Synopsis</a></h2> + +<blockquote><pre>#include <boost/integer.hpp> <i>// for boost::uint_t</i> +#include <cstddef> <i>// for std::size_t</i> + +namespace boost +{ + +template < std::size_t Bits > + class crc_basic; + +template < std::size_t Bits, <em>impl_def</em> TruncPoly = 0u, + <em>impl_def</em> InitRem = 0u, + <em>impl_def</em> FinalXor = 0u, bool ReflectIn = false, + bool ReflectRem = false > + class crc_optimal; + +template < std::size_t Bits, <em>impl_def</em> TruncPoly, + <em>impl_def</em> InitRem, <em>impl_def</em> FinalXor, + bool ReflectIn, bool ReflectRem > + typename uint_t<Bits>::fast crc( void const *buffer, + std::size_t byte_count ); + +template < std::size_t Bits, <em>impl_def</em> TruncPoly > + typename uint_t<Bits>::fast augmented_crc( void const *buffer, + std::size_t byte_count, + typename uint_t<Bits>::fast initial_remainder = 0u ); + +typedef crc_optimal<16, 0x8005, 0, 0, true, true> crc_16_type; +typedef crc_optimal<16, 0x1021, 0xFFFF, 0, false, false> crc_ccitt_type; +typedef crc_optimal<16, 0x8408, 0, 0, true, true> crc_xmodem_type; + +typedef crc_optimal<32, 0x04C11DB7, 0xFFFFFFFF, 0xFFFFFFFF, true, true> + crc_32_type; + +} +</pre></blockquote> + +<p>The implementation-defined type <var>impl_def</var> stands for the +quickest-to-manipulate built-in unsigned integral type that can +represent at least <var>Bits</var> bits.</p> + +<h2><a name="rationale">Rationale</a></h2> + +<p>A common error detection technique, especially with electronic +communications, is an appended checksum. The transmitter sends its data +bits, followed by the bits of the checksum. The checksum is based on +operations done on the data bit stream. The receiver applies the same +operations on the bits it gets, and then gets the checksum. If the +computed checksum doesn't match the received checksum, then an error +ocurred in the transmission. There is the slight chance that the error +is only in the checksum, and an actually-correct data stream is +rejected. There is also the chance of an error occurring that does not +change the checksum, making that error invisible. CRC is a common +checksum type, used for error detection for hardware interfaces and +encoding formats.</p> + +<h2><a name="background">Background</a></h2> + +<p>CRCs work by computing the remainder of a modulo-2 polynominal +division. The message is treated as the (binary) coefficents of a long +polynominal for the dividend, with the earlier bits of the message fed +first as the polynominal's highest coefficents. A particular CRC +algorithm has another polynominal associated with it to be used as the +divisor. The quotient is ignored. The remainder of the division +considered the checksum. However, the division uses modulo-2 rules (no +carries) for the coefficents.</p> + +<p>See <cite><a href="http://www.ross.net/crc/crcpaper.html">A +Painless Guide to CRC Error Detection Algorithms</a></cite> for complete +information. A clearer guide is at the <a +href="http://www.netrino.com/Embedded-Systems/How-To/CRC-Calculation-C-Code">CRC +Implementation Code in C</a> web page.</p> + +<h3><a name="parameters">CRC Parameters</a></h3> + +<dl> + <dt>Truncated polynominal + <dd>The divisor polynominal has a degree one bit larger than the + checksum (remainder) size. That highest bit is always one, so + it is ignored when describing a particular CRC type. Excluding + this bit makes the divisor fit in the same data type as the + checksum. + + <dt>Initial remainder + <dd>The interim CRC remainder changes as each bit is processed. + Usually, the interim remainder starts at zero, but some CRCs use + a different initial value to avoid "blind spots." A + blind spot is when a common sequence of message bits does not + change certain interim remainder values. + + <dt>Final XOR value + <dd>A CRC remainder can be combined with a defined value, <i>via</i> + a bitwise exclusive-or operation, before being returned to the + user. The value is usually zero, meaning the interim remainder + is returned unchanged. The other common value is an all-ones + value, meaning that the bitwise complement of the interim + remainder is returned. + + <dt>Reflected input + <dd>A message's bits are usually fed a byte at a time, with the + highest bits of the byte treated as the higher bits of the + dividend polynominal. Some CRCs reflect the bits (about the + byte's center, so the first and last bits are switched, + <i>etc.</i>) before feeding. + + <dt>Reflected (remainder) output + <dd>Some CRCs return the reflection of the interim remainder (taking + place <em>before</em> the final XOR value stage). +</dl> + +<h2><a name="crc_basic">Theoretical CRC Computer</a></h2> + +<blockquote><pre>template < std::size_t Bits > +class boost::crc_basic +{ +public: + // Type + typedef <em>implementation_defined</em> value_type; + + // Constant reflecting template parameter + static std::size_t const bit_count = Bits; + + // Constructor + explicit crc_basic( value_type truncated_polynominal, + value_type initial_remainder = 0, value_type final_xor_value = 0, + bool reflect_input = false, bool reflect_remainder = false ); + + // Internal Operations + value_type get_truncated_polynominal() const; + value_type get_initial_remainder() const; + value_type get_final_xor_value() const; + bool get_reflect_input() const; + bool get_reflect_remainder() const; + + value_type get_interim_remainder() const; + void reset( value_type new_rem ); + void reset(); + + // External Operations + void process_bit( bool bit ); + void process_bits( unsigned char bits, std::size_t bit_count ); + void process_byte( unsigned char byte ); + void process_block( void const *bytes_begin, void const *bytes_end ); + void process_bytes( void const *buffer, std::size_t byte_count ); + + value_type checksum() const; + +}; +</pre></blockquote> + +<p>The <code>value_type</code> is the smallest built-in type that can +hold the specified (by <code>Bits</code>) number of bits. This should +be <code>boost::uint_t<Bits>::least</code>, see the <a +href="../integer/doc/html/boost_integer/integer.html">documentation for integer type +selection</a> for details.</p> + +<p>This implementation is slow since it computes its CRC the same way as +in theory, bit by bit. No optimizations are performed. It wastes space +since most of the CRC parameters are specified at run-time as +constructor parameters.</p> + +<h2><a name="crc_optimal">Optimized CRC Computer</a></h2> + +<blockquote><pre>template < std::size_t Bits, <em>impl_def</em> TruncPoly, + <em>impl_def</em> InitRem, <em>impl_def</em> FinalXor, + bool ReflectIn, bool ReflectRem > +class boost::crc_optimal +{ +public: + // Type + typedef <em>implementation_defined</em> value_type; + + // Constants reflecting template parameters + static std::size_t const bit_count = Bits; + static value_type const truncated_polynominal = TruncPoly; + static value_type const initial_remainder = InitRem; + static value_type const final_xor_value = FinalXor; + static bool const reflect_input = ReflectIn; + static bool const reflect_remainder = ReflectRem; + + // Constructor + explicit crc_optimal( value_type init_rem = InitRem ); + + // Internal Operations + value_type get_truncated_polynominal() const; + value_type get_initial_remainder() const; + value_type get_final_xor_value() const; + bool get_reflect_input() const; + bool get_reflect_remainder() const; + + value_type get_interim_remainder() const; + void reset( value_type new_rem = InitRem ); + + // External Operations + void process_byte( unsigned char byte ); + void process_block( void const *bytes_begin, void const *bytes_end ); + void process_bytes( void const *buffer, std::size_t byte_count ); + + value_type checksum() const; + + // Operators + void operator ()( unsigned char byte ); + value_type operator ()() const; + +}; +</pre></blockquote> + +<p>The <code>value_type</code> is the quickest-to-manipulate built-in +type that can hold at least the specified (by <code>Bits</code>) number +of bits. This should be <code>boost::uint_t<Bits>::fast</code>. +See the <a href="../integer/doc/html/boost_integer/integer.html">integer type selection +documentation</a> for details. The <code>TruncPoly</code>, +<code>InitRem</code>, and <code>FinalXor</code> template parameters also +are of this type.</p> + +<p>This implementation is fast since it uses as many optimizations as +practical. All of the CRC parameters are specified at compile-time as +template parameters. No individual bits are considered; only whole +bytes are passed. A table of interim CRC values versus byte values is +pre-computed when the first object using a particular bit size, +truncated polynominal, and input reflection state is processed.</p> + +<h2><a name="usage">Computer Usage</a></h2> + +<p>The two class templates have different policies on where the CRC's +parameters go. Both class templates use the number of bits in the CRC +as the first template parameter. The theoretical computer class +template has the bit count as its only template parameter, all the other +CRC parameters are entered through the constructor. The optimized +computer class template obtains all its CRC parameters as template +parameters, and instantiated objects are usually +default-constructed.</p> + +<p>The CRC parameters can be inspected at run-time with the following +member functions: <code>get_truncated_polynominal</code>, +<code>get_initial_remainder</code>, <code>get_final_xor_value</code>, +<code>get_reflect_input</code>, and <code>get_reflect_remainder</code>. +The fast computer also provides compile-time constants for its CRC +parameters.</p> + +<p>The <code>get_interim_remainder</code> member function returns the +internal state of the CRC remainder. It represents the unreflected +remainder of the last division. Saving an interim remainder allows the +freezing of CRC processing, as long as the other CRC parameters and the +current position of the bit stream are saved. Restarting a frozen +stream involves constructing a new computer with the most of the old +computer's parameters. The only change is to use the frozen remainder +as the new computer's initial remainder. Then the interrupted bit +stream can be fed as if nothing happened. The fast CRC computer has a +special constructor that takes one argument, an interim remainder, for +this purpose (overriding the initial remainder CRC parameter).</p> + +<p>The <code>reset</code> member functions reset the internal state of +the CRC remainder to the given value. If no value is given, then the +internal remainder is set to the initial remainder value when the object +was created. The remainder must be unreflected. When a CRC calculation +is finished, calling <code>reset</code> lets the object be reused for a +new session.</p> + +<p>After any construction, both CRC computers work the same way. +Feeding new data to a computer is in a seperate operation(s) from +extracting the current CRC value from the computer. The following table +lists the feeding and extracting operations.</p> + +<table cellpadding="5" border="1"> + <caption>Regular CRC Operations</caption> + <tr> + <th>Operation</th> + <th>Description</th> + </tr> + <tr> + <td><code>void process_bit( bool bit );</code></td> + <td>Feeds the single <var>bit</var> to the computer, updating + the interim CRC. It is only defined for the slow CRC + computer.</td> + </tr> + <tr> + <td><code>void process_bits( unsigned char bits, std::size_t + bit_count );</code></td> + <td>Acts as applying <code>process_bit</code> to the lowest + <var>bit_count</var> bits given in <var>bits</var>, most + significant relevant bit first. The results are undefined + if <var>bit_count</var> exceeds the number of bits per byte. + It is only defined for the slow CRC computer.</td> + </tr> + <tr> + <td><code>void process_byte( unsigned char byte );</code></td> + <td>Acts as applying <code>process_bit</code> to the all the + bits in <var>byte</var>. If reflection is not desired, the + bits are fed from the most to least significant. The bits + are fed in the opposite order if reflection is desired.</td> + </tr> + <tr> + <td><code>void process_block( void const *bytes_begin, void + const *bytes_end );</code></td> + <td>Acts as applying <code>process_byte</code> to each byte in + the given memory block. This memory block starts at + <var>bytes_begin</var> and finishes before + <var>bytes_end</var>. The bytes are processed in that + order.</td> + </tr> + <tr> + <td><code>void process_bytes( void const *buffer, std::size_t + byte_count );</code></td> + <td>Acts as applying <code>process_byte</code> to each byte in + the given memory block. This memory block starts at + <var>buffer</var> and lasts for <var>byte_count</var> bytes. + The bytes are processed in ascending order.</td> + </tr> + <tr> + <td><code>value_type checksum() const;</code></td> + <td>Returns the CRC checksum of the data passed in so far, + possibly after applying the remainder-reflection and + exclusive-or operations.</td> + </tr> + <tr> + <td><code>void operator ()( unsigned char byte );</code></td> + <td>Calls <code>process_byte</code>. This member function lets + its object act as a (stateful) function object. It is only + defined for the fast CRC computer.</td> + </tr> + <tr> + <td><code>value_type operator ()() const;</code></td> + <td>Calls <code>checksum</code>. This member function lets + its object act as a generator function object. It is only + defined for the fast CRC computer.</td> + </tr> +</table> + +<p>You can use them like this:</p> + +<blockquote><pre>#include <boost/crc.hpp> <i>// for boost::crc_basic, boost::crc_optimal</i> +#include <boost/cstdint.hpp> <i>// for boost::uint16_t</i> + +#include <algorithm> <i>// for std::for_each</i> +#include <cassert> <i>// for assert</i> +#include <cstddef> <i>// for std::size_t</i> +#include <iostream> <i>// for std::cout</i> +#include <ostream> <i>// for std::endl</i> + + +// Main function +int +main () +{ + // This is "123456789" in ASCII + unsigned char const data[] = { 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, + 0x38, 0x39 }; + std::size_t const data_len = sizeof( data ) / sizeof( data[0] ); + + // The expected CRC for the given data + boost::uint16_t const expected = 0x29B1; + + // Simulate CRC-CCITT + boost::crc_basic<16> crc_ccitt1( 0x1021, 0xFFFF, 0, false, false ); + crc_ccitt1.process_bytes( data, data_len ); + assert( crc_ccitt1.checksum() == expected ); + + // Repeat with the optimal version (assuming a 16-bit type exists) + boost::crc_optimal<16, 0x1021, 0xFFFF, 0, false, false> crc_ccitt2; + crc_ccitt2 = std::for_each( data, data + data_len, crc_ccitt2 ); + assert( crc_ccitt2() == expected ); + + std::cout << "All tests passed." << std::endl; + return 0; +} +</pre></blockquote> + +<h2><a name="crc_func">CRC Function</a></h2> + +<blockquote><pre>template < std::size_t Bits, <em>impl_def</em> TruncPoly, + <em>impl_def</em> InitRem, <em>impl_def</em> FinalXor, + bool ReflectIn, bool ReflectRem > +typename boost::uint_t<Bits>::fast +boost::crc( void const *buffer, std::size_t byte_count ); +</pre></blockquote> + +<p>The <code>boost::crc</code> function template computes the CRC of a +given data block. The data block starts at the address given by +<var>buffer</var> and lasts for <var>byte_count</var> bytes. The CRC +parameters are passed through template arguments, identical to the +optimized CRC computer (<a href="#crc_optimal">see above</a>). In fact, +such a computer is used to implement this function.</p> + +<h2><a name="a_crc_func">Augmented-CRC Function</a></h2> + +<blockquote><pre>template < std::size_t Bits, <em>impl_def</em> TruncPoly > +typename boost::uint_t<Bits>::fast +boost::augmented_crc( void const *buffer, std::size_t byte_count, + typename boost::uint_t<Bits>::fast initial_remainder = 0u ); +</pre></blockquote> + +<p>All the other CRC-computing function or class templates work assuming +that the division steps start immediately on the first message bits. +The <code>boost::augmented_crc</code> function template has a +different division order. Instead of combining (<i>via</i> bitwise +exclusive-or) the current message bit with the highest bit of a separate +remainder, these templates shift a new message bit into the low bit of a +remainder register as the highest bit is shifted out. The new method +means that the bits in the inital remainder value are processed before +any of the actual message bits are processed. To compensate, the real +CRC can only be extracted after feeding enough zero bits (the same count +as the register size) after the message bits.</p> + +<p>The template parameters of the function template are +the CRC's bit size (<code>Bits</code>) and the truncated polynominal +(<code>TruncPoly</code>). The function parameters are the starting address of +the data block to be worked on (<var>buffer</var>), the number of bytes in that +data block (<var>byte_count</var>), and the incoming value of the remainder +(<var>initial_remainder</var>). That last parameter defaults to zero if it is +ommitted.</p> + +<p>This function template is useful if the bytes of the CRC directly +follow the message's bytes. First, set the bytes of where the CRC will +go to zero. Then use <code>augmented_crc</code> over the augmented +message, <i>i.e.</i> the message bytes and the appended CRC bytes. Then +assign the result to the CRC. To later check a received message, either +use <code>augmented_crc</code> (with the same parameters as +transmission, of course) on the received <em>unaugmented</em> message +and check if the result equals the CRC, or use +<code>augmented_crc</code> on the received <em>augmented</em> message +and check if the result equals zero. Note that the CRC has to be stored +with the more-significant bytes first (big-endian).</p> + +<p>Interruptions in the CRC data can be handled by feeding the result of +<code>augmented_crc</code> of the previous data block as the +<var>initial_remainder</var> when calling <code>augmented_crc</code> on +the next data block. Remember that the actual CRC can only be +determined after feeding the augmented bytes. Since this method uses +modulo-2 polynominal division at its most raw, neither final XOR values +nor reflection can be used.</p> + +<p>Note that for the same CRC system, the initial remainder for +augmented message method will be different than for the unaugmented +message method. The main exception is zero; if the augmented-CRC +algorithm uses a zero initial remainder, the equivalent unaugmented-CRC +algorithm will also use a zero initial remainder. Given an initial +remainder for a augmented-CRC algorithm, the result from processing just +zero-valued CRC bytes without any message bytes is the equivalent inital +remainder for the unaugmented-CRC algorithm. An example follows:</p> + +<blockquote><pre>#include <boost/crc.hpp> <i>// for boost::crc_basic, boost::augmented_crc</i> +#include <boost/cstdint.hpp> <i>// for boost::uint16_t</i> + +#include <cassert> <i>// for assert</i> +#include <iostream> <i>// for std::cout</i> +#include <ostream> <i>// for std::endl</i> + + +// Main function +int +main () +{ + using boost::uint16_t; + using boost::augmented_crc; + + uint16_t data[6] = { 2, 4, 31, 67, 98, 0 }; + uint16_t const init_rem = 0x123; + + uint16_t crc1 = augmented_crc<16, 0x8005>( data, sizeof(data), init_rem ); + + uint16_t const zero = 0; + uint16_t const new_init_rem = augmented_crc<16, 0x8005>( &zero, sizeof(zero) ); + + boost::crc_basic<16> crc2( 0x8005, new_init_rem ); + crc2.process_block( data, &data[5] ); // don't include CRC + assert( crc2.checksum() == crc1 ); + + std::cout << "All tests passed." << std::endl; + return 0; +} +</pre></blockquote> + +<h2><a name="crc_ex">Pre-Defined CRC Samples</a></h2> + +<p>Four sample CRC types are given, representing several common CRC +algorithms. For example, computations from <code>boost::crc_32_type</code> +can be used for implementing the PKZip standard. Note that, in general, this +library is concerned with CRC implementation, and not with determining +"good" sets of CRC parameters.</p> + +<table cellpadding="5" border="1"> + <caption>Common CRCs</caption> + <tr> + <th>Algorithm</th> + <th>Example Protocols</th> + </tr> + <tr> + <td><code>crc_16_type</code></td> + <td>BISYNCH, ARC</td> + </tr> + <tr> + <td><code>crc_ccitt_type</code></td> + <td>designated by CCITT (Comité Consultatif International + Télégraphique et Téléphonique)</td> + </tr> + <tr> + <td><code>crc_xmodem_type</code></td> + <td>XMODEM</td> + </tr> + <tr> + <td><code>crc_32_type</code></td> + <td>PKZip, AUTODIN II, Ethernet, FDDI</td> + </tr> +</table> + +<hr> + +<h2><a name="references">References</a></h2> + +<ul> + <li>The CRC header itself: <cite><a href="../../boost/crc.hpp">crc.hpp</a></cite> + <li>Some test code: <cite><a href="test/crc_test.cpp">crc_test.cpp</a></cite> + <li>Some example code: <cite><a href="crc_example.cpp">crc_example.cpp</a></cite> +</ul> + +<h2><a name="credits">Credits</a></h2> + +<h3><a name="contributors">Contributors</a></h3> + +<dl> + <dt>Michael Barr (<a + href="mailto:mbarr@netrino.com">mbarr@netrino.com</a>) + <dd>Wrote <a + href="http://www.netrino.com/Embedded-Systems/How-To/CRC-Calculation-C-Code">CRC + Implementation Code in C</a>, a less-confusing guide to implementing CRC + algorithms. (Originally published as "Slow and Steady + Never Lost the Race" in the January 2000 issue of <cite><a + href="http://www.embedded.com/">Embedded Systems + Programming</a></cite>, pages 37–46. The web version used to be + known as <cite><a href="http://www.netrino.com/Connecting/2000-01/">Easier + Said Than Done</a></cite>.) + + <dt>Daryle Walker + <dd>Started the library and contributed the theoretical and optimal + CRC computation class templates and the CRC computing function + template. Contributed <cite><a + href="test/crc_test.cpp">crc_test.cpp</a></cite> and <cite><a + href="crc_example.cpp">crc_example.cpp</a></cite>. + + <dt>Ross N. Williams + <dd>Wrote <cite><a href="http://www.ross.net/crc/crcpaper.html">A + Painless Guide to CRC Error Detection Algorithms</a></cite>, a + definitive source of CRC information. +</dl> + +<h3><a name="acknowledgements">Acknowledgements</a></h3> + +<p>For giving advice on compiler/C++ compliance, implementation, +interface, algorithms, and bug reports:</p> + +<ul> + <li>Darin Adler</li> + <li>Beman Dawes</li> + <li>Doug Gregor</li> + <li>John Maddock</li> + <li>Joe Mariadassou</li> + <li>Jens Maurer</li> + <li>Vladimir Prus</li> + <li>Joel Young</li> +</ul> + +<h3><a name="history">History</a></h3> + +<dl> + <dt>18 Dec 2011, Daryle Walker + <dd>Folded the two versions of <code>boost::augmented_crc</code> together. + + <dt>15 Jun 2003, Daryle Walker + <dd>Added example program. + + <dt>14 May 2001, Daryle Walker + <dd>Initial version. +</dl> + +<hr> + +<p>Revised: 18 December 2011</p> + +<p>Copyright 2001, 2003, 2011 Daryle Walker. Use, modification, and distribution +are subject to the Boost Software License, Version 1.0. (See accompanying +file <a href="../../LICENSE_1_0.txt">LICENSE_1_0.txt</a> or a copy at +<<a href="http://www.boost.org/LICENSE_1_0.txt">http://www.boost.org/LICENSE_1_0.txt</a>>.)</p> + +</body> +</html> diff --git a/src/boost/libs/crc/crc_example.cpp b/src/boost/libs/crc/crc_example.cpp new file mode 100644 index 00000000..a40e61d1 --- /dev/null +++ b/src/boost/libs/crc/crc_example.cpp @@ -0,0 +1,75 @@ +// Boost CRC example program file ------------------------------------------// + +// Copyright 2003 Daryle Walker. Use, modification, and distribution are +// subject to the Boost Software License, Version 1.0. (See accompanying file +// LICENSE_1_0.txt or a copy at <http://www.boost.org/LICENSE_1_0.txt>.) + +// See <http://www.boost.org/libs/crc/> for the library's home page. + +// Revision History +// 17 Jun 2003 Initial version (Daryle Walker) + +#include <boost/crc.hpp> // for boost::crc_32_type + +#include <cstdlib> // for EXIT_SUCCESS, EXIT_FAILURE +#include <exception> // for std::exception +#include <fstream> // for std::ifstream +#include <ios> // for std::ios_base, etc. +#include <iostream> // for std::cerr, std::cout +#include <ostream> // for std::endl + + +// Redefine this to change to processing buffer size +#ifndef PRIVATE_BUFFER_SIZE +#define PRIVATE_BUFFER_SIZE 1024 +#endif + +// Global objects +std::streamsize const buffer_size = PRIVATE_BUFFER_SIZE; + + +// Main program +int +main +( + int argc, + char const * argv[] +) +try +{ + boost::crc_32_type result; + + for ( int i = 1 ; i < argc ; ++i ) + { + std::ifstream ifs( argv[i], std::ios_base::binary ); + + if ( ifs ) + { + do + { + char buffer[ buffer_size ]; + + ifs.read( buffer, buffer_size ); + result.process_bytes( buffer, ifs.gcount() ); + } while ( ifs ); + } + else + { + std::cerr << "Failed to open file '" << argv[i] << "'." + << std::endl; + } + } + + std::cout << std::hex << std::uppercase << result.checksum() << std::endl; + return EXIT_SUCCESS; +} +catch ( std::exception &e ) +{ + std::cerr << "Found an exception with '" << e.what() << "'." << std::endl; + return EXIT_FAILURE; +} +catch ( ... ) +{ + std::cerr << "Found an unknown exception." << std::endl; + return EXIT_FAILURE; +} diff --git a/src/boost/libs/crc/index.html b/src/boost/libs/crc/index.html new file mode 100644 index 00000000..96cf616d --- /dev/null +++ b/src/boost/libs/crc/index.html @@ -0,0 +1,14 @@ +<!-- +Copyright 2012 Daryle Walker +Distributed under the Boost Software License, Version 1.0. (See the accompanying +file LICENSE_1_0.txt or a copy at http://www.boost.org/LICENSE_1_0.txt) +--> +<html> +<head> +<meta http-equiv="refresh" content="0; URL=../../doc/html/crc.html"> +</head> +<body> +<p>Automatic redirection failed, please go to +<a href="../../doc/html/crc.html">../../doc/html/crc.html</a>.</p> +</body> +</html> diff --git a/src/boost/libs/crc/meta/libraries.json b/src/boost/libs/crc/meta/libraries.json new file mode 100644 index 00000000..70c2e131 --- /dev/null +++ b/src/boost/libs/crc/meta/libraries.json @@ -0,0 +1,14 @@ +{ + "key": "crc", + "name": "CRC", + "authors": [ + "Daryle Walker" + ], + "description": "The Boost CRC Library provides two implementations of CRC (cyclic redundancy code) computation objects and two implementations of CRC computation functions. The implementations are template-based.", + "category": [ + "Domain" + ], + "maintainers": [ + "Daryle Walker <darylew -at- hotmail.com>" + ] +} diff --git a/src/boost/libs/crc/test/Jamfile.v2 b/src/boost/libs/crc/test/Jamfile.v2 new file mode 100644 index 00000000..59139f89 --- /dev/null +++ b/src/boost/libs/crc/test/Jamfile.v2 @@ -0,0 +1,8 @@ +#~ Copyright Rene Rivera 2008, Daryle Walker 2011 +#~ Distributed under the Boost Software License, Version 1.0. +#~ (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) + +import testing ; + +run crc_test.cpp ; +run crc_test2.cpp ; diff --git a/src/boost/libs/crc/test/crc_test.cpp b/src/boost/libs/crc/test/crc_test.cpp new file mode 100644 index 00000000..a9a092ba --- /dev/null +++ b/src/boost/libs/crc/test/crc_test.cpp @@ -0,0 +1,756 @@ +// Boost CRC test program file ---------------------------------------------// + +// Copyright 2001, 2003, 2004 Daryle Walker. Use, modification, and +// distribution are subject to the Boost Software License, Version 1.0. (See +// accompanying file LICENSE_1_0.txt or a copy at +// <http://www.boost.org/LICENSE_1_0.txt>.) + +// See <http://www.boost.org/libs/crc/> for the library's home page. + +// Revision History +// 28 Aug 2004 Added CRC tests for polynominals shorter than 8 bits +// (Daryle Walker, by patch from Bert Klaps) +// 23 Aug 2003 Adjust to updated Test framework (Daryle Walker) +// 14 May 2001 Initial version (Daryle Walker) + + +#include <boost/config.hpp> // for BOOST_MSVC, etc. +#include <boost/crc.hpp> // for boost::crc_basic, etc. +#include <boost/cstdint.hpp> // for boost::uint16_t, etc. +#include <boost/cstdlib.hpp> // for boost::exit_success +#include <boost/integer.hpp> // for boost::uint_t +#include <boost/random/linear_congruential.hpp> // for boost::minstd_rand +#include <boost/core/lightweight_test.hpp> +#include <boost/timer.hpp> // for boost::timer + +#include <algorithm> // for std::for_each, std::generate_n, std::count +#include <climits> // for CHAR_BIT +#include <cstddef> // for std::size_t +#include <iostream> // for std::cout (std::ostream and std::endl indirectly) + + +#if CHAR_BIT != 8 +#error The expected results assume an eight-bit byte. +#endif + +#if !(defined(BOOST_NO_DEPENDENT_TYPES_IN_TEMPLATE_VALUE_PARAMETERS) || (defined(BOOST_MSVC) && (BOOST_MSVC <= 1300))) +#define CRC_PARM_TYPE typename boost::uint_t<Bits>::fast +#else +#define CRC_PARM_TYPE unsigned long +#endif + +#if !defined(BOOST_MSVC) && !defined(__GNUC__) +#define PRIVATE_DECLARE_BOOST( TypeName ) using boost:: TypeName +#else +#define PRIVATE_DECLARE_BOOST( TypeName ) typedef boost:: TypeName TypeName +#endif + + +// Types +template < std::size_t Bits, CRC_PARM_TYPE TrPo, CRC_PARM_TYPE InRe, + CRC_PARM_TYPE FiXo, bool ReIn, bool ReRe > +class crc_tester +{ +public: + // All the following were separate function templates, but they have + // been moved to class-static member functions of a class template + // because MS VC++ 6 can't handle function templates that can't + // deduce all their template arguments from their function arguments. + + typedef typename boost::uint_t<Bits>::fast value_type; + + static void master_test( char const *test_name, value_type expected ); + +private: + typedef boost::crc_optimal<Bits, TrPo, InRe, FiXo, ReIn, ReRe> + optimal_crc_type; + typedef boost::crc_basic<Bits> basic_crc_type; + + static void compute_test( value_type expected ); + static void interrupt_test( value_type expected ); + static void error_test(); + +}; // crc_tester + +// Global data +unsigned char const std_data[] = { 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, + 0x38, 0x39 }; +std::size_t const std_data_len = sizeof( std_data ) / sizeof( std_data[0] ); + +boost::uint16_t const std_crc_ccitt_result = 0x29B1; +boost::uint16_t const std_crc_16_result = 0xBB3D; +boost::uint32_t const std_crc_32_result = 0xCBF43926; + +// Function prototypes +void timing_test(); +boost::uint32_t basic_crc32( void const *buffer, std::size_t byte_count ); +boost::uint32_t optimal_crc32( void const *buffer, std::size_t byte_count ); +boost::uint32_t quick_crc32( void const *buffer, std::size_t byte_count ); +boost::uint32_t quick_reflect( boost::uint32_t value, std::size_t bits ); +double time_trial( char const *name, + boost::uint32_t (*crc_func)(void const *, std::size_t), + boost::uint32_t expected, void const *data, std::size_t length ); + +void augmented_tests(); +boost::uint32_t native_to_big( boost::uint32_t x ); +boost::uint32_t big_to_native( boost::uint32_t x ); + +void small_crc_test1(); +void small_crc_test2(); + + +// Macro to compact code +#define PRIVATE_TESTER_NAME crc_tester<Bits, TrPo, InRe, FiXo, ReIn, ReRe> + +// Run a test on slow and fast CRC computers and function +template < std::size_t Bits, CRC_PARM_TYPE TrPo, CRC_PARM_TYPE InRe, + CRC_PARM_TYPE FiXo, bool ReIn, bool ReRe > +void +PRIVATE_TESTER_NAME::compute_test +( + typename PRIVATE_TESTER_NAME::value_type expected +) +{ + std::cout << "\tDoing computation tests." << std::endl; + + optimal_crc_type fast_crc; + basic_crc_type slow_crc( TrPo, InRe, FiXo, ReIn, ReRe ); + value_type const func_result = boost::crc<Bits, TrPo, InRe, FiXo, ReIn, + ReRe>( std_data, std_data_len ); + + fast_crc.process_bytes( std_data, std_data_len ); + slow_crc.process_bytes( std_data, std_data_len ); + BOOST_TEST_EQ( fast_crc.checksum(), expected ); + BOOST_TEST_EQ( slow_crc.checksum(), expected ); + BOOST_TEST_EQ( func_result, expected ); +} + +// Run a test in two runs, and check all the inspectors +template < std::size_t Bits, CRC_PARM_TYPE TrPo, CRC_PARM_TYPE InRe, + CRC_PARM_TYPE FiXo, bool ReIn, bool ReRe > +void +PRIVATE_TESTER_NAME::interrupt_test +( + typename PRIVATE_TESTER_NAME::value_type expected +) +{ + std::cout << "\tDoing interrupt tests." << std::endl; + + // Process the first half of the data (also test accessors) + optimal_crc_type fast_crc1; + basic_crc_type slow_crc1( fast_crc1.get_truncated_polynominal(), + fast_crc1.get_initial_remainder(), fast_crc1.get_final_xor_value(), + fast_crc1.get_reflect_input(), fast_crc1.get_reflect_remainder() ); + + BOOST_TEST_EQ( fast_crc1.get_interim_remainder(), + slow_crc1.get_initial_remainder() ); + + std::size_t const mid_way = std_data_len / 2; + unsigned char const * const std_data_end = std_data + std_data_len; + + fast_crc1.process_bytes( std_data, mid_way ); + slow_crc1.process_bytes( std_data, mid_way ); + BOOST_TEST_EQ( fast_crc1.checksum(), slow_crc1.checksum() ); + + // Process the second half of the data (also test accessors) + boost::crc_optimal<optimal_crc_type::bit_count, + optimal_crc_type::truncated_polynominal, optimal_crc_type::initial_remainder, + optimal_crc_type::final_xor_value, optimal_crc_type::reflect_input, + optimal_crc_type::reflect_remainder> + fast_crc2( fast_crc1.get_interim_remainder() ); + boost::crc_basic<basic_crc_type::bit_count> slow_crc2( + slow_crc1.get_truncated_polynominal(), slow_crc1.get_interim_remainder(), + slow_crc1.get_final_xor_value(), slow_crc1.get_reflect_input(), + slow_crc1.get_reflect_remainder() ); + + fast_crc2.process_block( std_data + mid_way, std_data_end ); + slow_crc2.process_block( std_data + mid_way, std_data_end ); + BOOST_TEST_EQ( fast_crc2.checksum(), slow_crc2.checksum() ); + BOOST_TEST_EQ( fast_crc2.checksum(), expected ); + BOOST_TEST_EQ( slow_crc2.checksum(), expected ); +} + +// Run a test to see if a single-bit error is detected +template < std::size_t Bits, CRC_PARM_TYPE TrPo, CRC_PARM_TYPE InRe, + CRC_PARM_TYPE FiXo, bool ReIn, bool ReRe > +void +PRIVATE_TESTER_NAME::error_test +( +) +{ + PRIVATE_DECLARE_BOOST( uint32_t ); + + // A single-bit error is ensured to be detected if the polynominal + // has at least two bits set. The highest bit is what is removed + // to give the truncated polynominal, and it is always set. This + // means that the truncated polynominal needs at least one of its + // bits set, which implies that it cannot be zero. + if ( !(TrPo & boost::detail::low_bits_mask_c<Bits>::value) ) + { + BOOST_ERROR( "truncated CRC polymonial is zero" ); + } + + std::cout << "\tDoing error tests." << std::endl; + + // Create a random block of data + uint32_t ran_data[ 256 ]; + std::size_t const ran_length = sizeof(ran_data) / sizeof(ran_data[0]); + + std::generate_n( ran_data, ran_length, boost::minstd_rand() ); + + // Create computers and compute the checksum of the data + optimal_crc_type fast_tester; + basic_crc_type slow_tester( TrPo, InRe, FiXo, ReIn, ReRe ); + + fast_tester.process_bytes( ran_data, sizeof(ran_data) ); + slow_tester.process_bytes( ran_data, sizeof(ran_data) ); + + uint32_t const fast_checksum = fast_tester.checksum(); + uint32_t const slow_checksum = slow_tester.checksum(); + + BOOST_TEST_EQ( fast_checksum, slow_checksum ); + + // Do the checksum again (and test resetting ability) + fast_tester.reset(); + slow_tester.reset( InRe ); + fast_tester.process_bytes( ran_data, sizeof(ran_data) ); + slow_tester.process_bytes( ran_data, sizeof(ran_data) ); + BOOST_TEST_EQ( fast_tester.checksum(), slow_tester.checksum() ); + BOOST_TEST_EQ( fast_tester.checksum(), fast_checksum ); + BOOST_TEST_EQ( slow_tester.checksum(), slow_checksum ); + + // Produce a single-bit error + ran_data[ ran_data[0] % ran_length ] ^= ( 1 << (ran_data[1] % 32) ); + + // Compute the checksum of the errorenous data + // (and continue testing resetting ability) + fast_tester.reset( InRe ); + slow_tester.reset(); + fast_tester.process_bytes( ran_data, sizeof(ran_data) ); + slow_tester.process_bytes( ran_data, sizeof(ran_data) ); + BOOST_TEST_EQ( fast_tester.checksum(), slow_tester.checksum() ); + BOOST_TEST_NE( fast_tester.checksum(), fast_checksum ); + BOOST_TEST_NE( slow_tester.checksum(), slow_checksum ); +} + +// Run the other CRC object tests +template < std::size_t Bits, CRC_PARM_TYPE TrPo, CRC_PARM_TYPE InRe, + CRC_PARM_TYPE FiXo, bool ReIn, bool ReRe > +void +PRIVATE_TESTER_NAME::master_test +( + char const * test_name, + typename PRIVATE_TESTER_NAME::value_type expected +) +{ + std::cout << "Doing test suite for " << test_name << '.' << std::endl; + compute_test( expected ); + interrupt_test( expected ); + error_test(); +} + +// Undo limited macros +#undef PRIVATE_TESTER_NAME + + +// A CRC-32 computer based on crc_basic, for timing +boost::uint32_t +basic_crc32 +( + void const * buffer, + std::size_t byte_count +) +{ + static boost::crc_basic<32> computer( 0x04C11DB7, 0xFFFFFFFF, 0xFFFFFFFF, + true, true ); + + computer.reset(); + computer.process_bytes( buffer, byte_count ); + return computer.checksum(); +} + +// A CRC-32 computer based on crc_optimal, for timing +inline +boost::uint32_t +optimal_crc32 +( + void const * buffer, + std::size_t byte_count +) +{ + static boost::crc_32_type computer; + + computer.reset(); + computer.process_bytes( buffer, byte_count ); + return computer.checksum(); +} + +// Reflect the lower "bits" bits of a "value" +boost::uint32_t +quick_reflect +( + boost::uint32_t value, + std::size_t bits +) +{ + boost::uint32_t reflection = 0; + for ( std::size_t i = 0 ; i < bits ; ++i ) + { + if ( value & (1u << i) ) + { + reflection |= 1 << ( bits - 1 - i ); + } + } + + return reflection; +} + +// A customized CRC-32 computer, for timing +boost::uint32_t +quick_crc32 +( + void const * buffer, + std::size_t byte_count +) +{ + PRIVATE_DECLARE_BOOST( uint32_t ); + typedef unsigned char byte_type; + + // Compute the CRC table (first run only) + static bool did_init = false; + static uint32_t crc_table[ 1ul << CHAR_BIT ]; + if ( !did_init ) + { + uint32_t const value_high_bit = static_cast<uint32_t>(1) << 31u; + + byte_type dividend = 0; + do + { + uint32_t remainder = 0; + for ( byte_type mask = 1u << (CHAR_BIT - 1u) ; mask ; mask >>= 1 ) + { + if ( dividend & mask ) + { + remainder ^= value_high_bit; + } + + if ( remainder & value_high_bit ) + { + remainder <<= 1; + remainder ^= 0x04C11DB7u; + } + else + { + remainder <<= 1; + } + } + + crc_table[ quick_reflect(dividend, CHAR_BIT) ] + = quick_reflect( remainder, 32 ); + } + while ( ++dividend ); + + did_init = true; + } + + // Compute the CRC of the data + uint32_t rem = 0xFFFFFFFF; + + byte_type const * const b_begin = static_cast<byte_type const *>( buffer ); + byte_type const * const b_end = b_begin + byte_count; + for ( byte_type const *p = b_begin ; p < b_end ; ++p ) + { + byte_type const byte_index = *p ^ rem; + rem >>= CHAR_BIT; + rem ^= crc_table[ byte_index ]; + } + + return ~rem; +} + +// Run an individual timing trial +double +time_trial +( + char const * name, + boost::uint32_t (*crc_func)(void const *, std::size_t), + boost::uint32_t expected, + void const * data, + std::size_t length +) +{ + PRIVATE_DECLARE_BOOST( uint32_t ); + using std::cout; + + // Limits of a trial + static uint32_t const max_count = 1L << 16; // ~square-root of max + static double const max_time = 3.14159; // easy as pi(e) + + // Mark the trial + cout << '\t' << name << " CRC-32: "; + + // Trial loop + uint32_t trial_count = 0, wrong_count = 0; + double elapsed_time = 0.0; + boost::timer t; + + do + { + uint32_t const scratch = (*crc_func)( data, length ); + + if ( scratch != expected ) + { + ++wrong_count; + } + elapsed_time = t.elapsed(); + ++trial_count; + } while ( (trial_count < max_count) && (elapsed_time < max_time) ); + + if ( wrong_count ) + { + BOOST_ERROR( "at least one time trial didn't match expected" ); + } + + // Report results + double const rate = trial_count / elapsed_time; + + cout << trial_count << " runs, " << elapsed_time << " s, " << rate + << " run/s" << std::endl; + return rate; +} + +// Time runs of Boost CRCs vs. a customized CRC function +void +timing_test +( +) +{ + PRIVATE_DECLARE_BOOST( uint32_t ); + using std::cout; + using std::endl; + + cout << "Doing timing tests." << endl; + + // Create a random block of data + boost::int32_t ran_data[ 256 ]; + std::size_t const ran_length = sizeof(ran_data) / sizeof(ran_data[0]); + + std::generate_n( ran_data, ran_length, boost::minstd_rand() ); + + // Use the first runs as a check. This gives a chance for first- + // time static initialization to not interfere in the timings. + uint32_t const basic_result = basic_crc32( ran_data, sizeof(ran_data) ); + uint32_t const optimal_result = optimal_crc32( ran_data, sizeof(ran_data) ); + uint32_t const quick_result = quick_crc32( ran_data, sizeof(ran_data) ); + + BOOST_TEST_EQ( basic_result, optimal_result ); + BOOST_TEST_EQ( optimal_result, quick_result ); + BOOST_TEST_EQ( quick_result, basic_result ); + + // Run trials + double const basic_rate = time_trial( "Boost-Basic", basic_crc32, + basic_result, ran_data, sizeof(ran_data) ); + double const optimal_rate = time_trial( "Boost-Optimal", optimal_crc32, + optimal_result, ran_data, sizeof(ran_data) ); + double const quick_rate = time_trial( "Reference", quick_crc32, + quick_result, ran_data, sizeof(ran_data) ); + + // Report results + cout << "\tThe optimal Boost version has " << optimal_rate / quick_rate * + 100.0 << "% the speed of the reference version.\n"; + cout << "\tThe basic Boost version has " << basic_rate / quick_rate * 100.0 + << "% the speed of the reference version.\n"; + cout << "\tThe basic Boost version has " << basic_rate / optimal_rate * + 100.0 << "% the speed of the optimal Boost version." + << endl; +} + + +// Reformat an integer to the big-endian storage format +boost::uint32_t +native_to_big +( + boost::uint32_t x +) +{ + boost::uint32_t temp; + unsigned char * tp = reinterpret_cast<unsigned char *>( &temp ); + + for ( std::size_t i = sizeof(x) ; i > 0 ; --i ) + { + tp[ i - 1 ] = static_cast<unsigned char>( x ); + x >>= CHAR_BIT; + } + + return temp; +} + +// Restore an integer from the big-endian storage format +boost::uint32_t +big_to_native +( + boost::uint32_t x +) +{ + boost::uint32_t temp = 0; + unsigned char * xp = reinterpret_cast<unsigned char *>( &x ); + + for ( std::size_t i = 0 ; i < sizeof(x) ; ++i ) + { + temp <<= CHAR_BIT; + temp |= xp[ i ]; + } + + return temp; +} + +// Run tests on using CRCs on augmented messages +void +augmented_tests +( +) +{ + #define PRIVATE_ACRC_FUNC boost::augmented_crc<32, 0x04C11DB7> + + using std::size_t; + PRIVATE_DECLARE_BOOST( uint32_t ); + + std::cout << "Doing CRC-augmented message tests." << std::endl; + + // Create a random block of data, with space for a CRC. + uint32_t ran_data[ 257 ]; + size_t const ran_length = sizeof(ran_data) / sizeof(ran_data[0]); + size_t const data_length = ran_length - 1; + + std::generate_n( ran_data, data_length, boost::minstd_rand() ); + + // When creating a CRC for an augmented message, use + // zeros in the appended CRC spot for the first run. + uint32_t & ran_crc = ran_data[ data_length ]; + + ran_crc = 0; + + // Compute the CRC with augmented-CRC computing function + typedef boost::uint_t<32>::fast return_type; + + ran_crc = PRIVATE_ACRC_FUNC( ran_data, sizeof(ran_data) ); + + // With the appended CRC set, running the checksum again should get zero. + // NOTE: CRC algorithm assumes numbers are in big-endian format + ran_crc = native_to_big( ran_crc ); + + uint32_t ran_crc_check = PRIVATE_ACRC_FUNC( ran_data, sizeof(ran_data) ); + + BOOST_TEST_EQ( 0, ran_crc_check ); + + // Compare that result with other CRC computing functions + // and classes, which don't accept augmented messages. + typedef boost::crc_optimal<32, 0x04C11DB7> fast_crc_type; + typedef boost::crc_basic<32> slow_crc_type; + + fast_crc_type fast_tester; + slow_crc_type slow_tester( 0x04C11DB7 ); + size_t const data_size = data_length * sizeof(ran_data[0]); + uint32_t const func_tester = boost::crc<32, 0x04C11DB7, 0, 0, false, + false>( ran_data, data_size ); + + fast_tester.process_bytes( ran_data, data_size ); + slow_tester.process_bytes( ran_data, data_size ); + BOOST_TEST_EQ( fast_tester.checksum(), slow_tester.checksum() ); + ran_crc = big_to_native( ran_crc ); + BOOST_TEST_EQ( fast_tester.checksum(), ran_crc ); + BOOST_TEST_EQ( func_tester, ran_crc ); + + // Do a single-bit error test + ran_crc = native_to_big( ran_crc ); + ran_data[ ran_data[0] % ran_length ] ^= ( 1 << (ran_data[1] % 32) ); + ran_crc_check = PRIVATE_ACRC_FUNC( ran_data, sizeof(ran_data) ); + BOOST_TEST_NE( 0, ran_crc_check ); + + // Run a version of these tests with a nonzero initial remainder. + uint32_t const init_rem = ran_data[ ran_data[2] % ran_length ]; + + ran_crc = 0; + ran_crc = PRIVATE_ACRC_FUNC( ran_data, sizeof(ran_data), init_rem ); + + // Have some fun by processing data in two steps. + size_t const mid_index = ran_length / 2; + + ran_crc = native_to_big( ran_crc ); + ran_crc_check = PRIVATE_ACRC_FUNC( ran_data, mid_index + * sizeof(ran_data[0]), init_rem ); + ran_crc_check = PRIVATE_ACRC_FUNC( &ran_data[mid_index], sizeof(ran_data) + - mid_index * sizeof(ran_data[0]), ran_crc_check ); + BOOST_TEST_EQ( 0, ran_crc_check ); + + // This substep translates an augmented-CRC initial + // remainder to an unaugmented-CRC initial remainder. + uint32_t const zero = 0; + uint32_t const new_init_rem = PRIVATE_ACRC_FUNC( &zero, sizeof(zero), + init_rem ); + slow_crc_type slow_tester2( 0x04C11DB7, new_init_rem ); + + slow_tester2.process_bytes( ran_data, data_size ); + ran_crc = big_to_native( ran_crc ); + BOOST_TEST_EQ( slow_tester2.checksum(), ran_crc ); + + // Redo single-bit error test + ran_data[ ran_data[3] % ran_length ] ^= ( 1 << (ran_data[4] % 32) ); + ran_crc_check = PRIVATE_ACRC_FUNC( ran_data, sizeof(ran_data), init_rem ); + BOOST_TEST_NE( 0, ran_crc_check ); + + #undef PRIVATE_ACRC_FUNC +} + + +// Run tests on CRCs below a byte in size (here, 3 bits) +void +small_crc_test1 +( +) +{ + std::cout << "Doing short-CRC (3-bit augmented) message tests." + << std::endl; + + // The CRC standard is a SDH/SONET Low Order LCAS control word with CRC-3 + // taken from ITU-T G.707 (12/03) XIII.2. + + // Four samples, each four bytes; should all have a CRC of zero + unsigned char const samples[4][4] + = { + { 0x3A, 0xC4, 0x08, 0x06 }, + { 0x42, 0xC5, 0x0A, 0x41 }, + { 0x4A, 0xC5, 0x08, 0x22 }, + { 0x52, 0xC4, 0x08, 0x05 } + }; + + // Basic computer + boost::crc_basic<3> tester1( 0x03 ); + + tester1.process_bytes( samples[0], 4 ); + BOOST_TEST_EQ( tester1.checksum(), 0 ); + + tester1.reset(); + tester1.process_bytes( samples[1], 4 ); + BOOST_TEST_EQ( tester1.checksum(), 0 ); + + tester1.reset(); + tester1.process_bytes( samples[2], 4 ); + BOOST_TEST_EQ( tester1.checksum(), 0 ); + + tester1.reset(); + tester1.process_bytes( samples[3], 4 ); + BOOST_TEST_EQ( tester1.checksum(), 0 ); + + // Optimal computer + #define PRIVATE_CRC_FUNC boost::crc<3, 0x03, 0, 0, false, false> + #define PRIVATE_ACRC_FUNC boost::augmented_crc<3, 0x03> + + BOOST_TEST_EQ( 0, PRIVATE_CRC_FUNC(samples[0], 4) ); + BOOST_TEST_EQ( 0, PRIVATE_CRC_FUNC(samples[1], 4) ); + BOOST_TEST_EQ( 0, PRIVATE_CRC_FUNC(samples[2], 4) ); + BOOST_TEST_EQ( 0, PRIVATE_CRC_FUNC(samples[3], 4) ); + + // maybe the fix to CRC functions needs to be applied to augmented CRCs? + + #undef PRIVATE_ACRC_FUNC + #undef PRIVATE_CRC_FUNC +} + +// Run tests on CRCs below a byte in size (here, 7 bits) +void +small_crc_test2 +( +) +{ + std::cout << "Doing short-CRC (7-bit augmented) message tests." + << std::endl; + + // The CRC standard is a SDH/SONET J0/J1/J2/N1/N2/TR TTI (trace message) + // with CRC-7, o.a. ITU-T G.707 Annex B, G.832 Annex A. + + // Two samples, each sixteen bytes + // Sample 1 is '\x80' + ASCII("123456789ABCDEF") + // Sample 2 is '\x80' + ASCII("TTI UNAVAILABLE") + unsigned char const samples[2][16] + = { + { 0x80, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, 0x38, 0x39, 0x41, + 0x42, 0x43, 0x44, 0x45, 0x46 }, + { 0x80, 0x54, 0x54, 0x49, 0x20, 0x55, 0x4E, 0x41, 0x56, 0x41, 0x49, + 0x4C, 0x41, 0x42, 0x4C, 0x45 } + }; + unsigned const results[2] = { 0x62, 0x23 }; + + // Basic computer + boost::crc_basic<7> tester1( 0x09 ); + + tester1.process_bytes( samples[0], 16 ); + BOOST_TEST_EQ( tester1.checksum(), results[0] ); + + tester1.reset(); + tester1.process_bytes( samples[1], 16 ); + BOOST_TEST_EQ( tester1.checksum(), results[1] ); + + // Optimal computer + #define PRIVATE_CRC_FUNC boost::crc<7, 0x09, 0, 0, false, false> + #define PRIVATE_ACRC_FUNC boost::augmented_crc<7, 0x09> + + BOOST_TEST_EQ( results[0], PRIVATE_CRC_FUNC(samples[0], 16) ); + BOOST_TEST_EQ( results[1], PRIVATE_CRC_FUNC(samples[1], 16) ); + + // maybe the fix to CRC functions needs to be applied to augmented CRCs? + + #undef PRIVATE_ACRC_FUNC + #undef PRIVATE_CRC_FUNC +} + + +#ifndef BOOST_MSVC +// Explicit template instantiations +// (needed to fix a link error in Metrowerks CodeWarrior Pro 5.3) +template class crc_tester<16, 0x1021, 0xFFFF, 0, false, false>; +template class crc_tester<16, 0x8005, 0, 0, true, true>; +template class crc_tester<32, 0x04C11DB7, 0xFFFFFFFF, 0xFFFFFFFF, true, true>; +#endif + +// Main testing function +int main() +{ + using std::cout; + using std::endl; + + // Run simulations on some CRC types + typedef crc_tester<16, 0x1021, 0xFFFF, 0, false, false> crc_ccitt_tester; + typedef crc_tester<16, 0x8005, 0, 0, true, true> crc_16_tester; + typedef crc_tester<32, 0x04C11DB7, 0xFFFFFFFF, 0xFFFFFFFF, true, true> + crc_32_tester; + + crc_ccitt_tester::master_test( "CRC-CCITT", std_crc_ccitt_result ); + crc_16_tester::master_test( "CRC-16", std_crc_16_result ); + crc_32_tester::master_test( "CRC-32", std_crc_32_result ); + + // Run a timing comparison test + timing_test(); + + // Test using augmented messages + augmented_tests(); + + // Test with CRC types smaller than a byte + small_crc_test1(); + small_crc_test2(); + + // Try a CRC based on the (x + 1) polynominal, which is a factor in + // many real-life polynominals and doesn't fit evenly in a byte. + cout << "Doing one-bit polynominal CRC test." << endl; + boost::crc_basic<1> crc_1( 1 ); + crc_1.process_bytes( std_data, std_data_len ); + BOOST_TEST_EQ( crc_1.checksum(), 1 ); + + // Test the function object interface + cout << "Doing functional object interface test." << endl; + boost::crc_optimal<16, 0x8005, 0, 0, true, true> crc_16; + crc_16 = std::for_each( std_data, std_data + std_data_len, crc_16 ); + BOOST_TEST_EQ( crc_16(), std_crc_16_result ); + + return boost::report_errors(); +} diff --git a/src/boost/libs/crc/test/crc_test2.cpp b/src/boost/libs/crc/test/crc_test2.cpp new file mode 100644 index 00000000..699cb059 --- /dev/null +++ b/src/boost/libs/crc/test/crc_test2.cpp @@ -0,0 +1,637 @@ +// Boost CRC unit test program file ----------------------------------------// + +// Copyright 2011 Daryle Walker. +// Distributed under the Boost Software License, Version 1.0. (See the +// accompanying file LICENSE_1_0.txt or a copy at +// <http://www.boost.org/LICENSE_1_0.txt>.) + +// See <http://www.boost.org/libs/crc/> for the library's home page. + +#include <boost/core/lightweight_test.hpp> +#include <boost/crc.hpp> // for boost::crc_basic,crc_optimal,augmented_crc,crc + +#include <boost/cstdint.hpp> // for boost::uint16_t, uint32_t, uintmax_t +#include <boost/predef/other/endian.h> +#include <boost/integer.hpp> // for boost::uint_t +#include <boost/typeof/typeof.hpp> // for BOOST_AUTO +#include <boost/random/linear_congruential.hpp> // for boost::minstd_rand + +#include <algorithm> // for std::generate_n, for_each +#include <climits> // for CHAR_BIT +#include <cstddef> // for std::size_t + +// Sanity check +#if CHAR_BIT != 8 +#error The expected results assume octet-sized bytes. +#endif + +// Control tests at compile-time +#ifndef CONTROL_SUB_BYTE_MISMATCHED_REFLECTION_TEST +#define CONTROL_SUB_BYTE_MISMATCHED_REFLECTION_TEST 1 +#endif + + +// Common definitions -------------------------------------------------------// + +namespace { + +// Many CRC configurations use the string "123456789" in ASCII as test data. +unsigned char const std_data[] = { 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, + 0x38, 0x39 }; +std::size_t const std_data_len = sizeof( std_data ) / sizeof( std_data[0] ); + +// Checksums of the standard test data for common configurations +boost::uint16_t const std_crc_ccitt_false_result = 0x29B1u; +boost::uint16_t const std_crc_ccitt_true_result = 0x2189u; +boost::uint16_t const std_crc_xmodem_result = 0x31C3u; +boost::uint16_t const std_crc_16_result = 0xBB3Du; +boost::uint32_t const std_crc_32_result = 0xCBF43926ul; + +// Conversion functions between native- and big-endian representations +#if BOOST_ENDIAN_BIG_BYTE +boost::uint32_t native_to_big( boost::uint32_t x ) { return x; } +boost::uint32_t big_to_native( boost::uint32_t x ) { return x; } +#else +union endian_convert +{ + boost::uint32_t w; + unsigned char p[ 4 ]; +}; + +boost::uint32_t native_to_big( boost::uint32_t x ) +{ + endian_convert e; + + e.p[ 0 ] = x >> 24; + e.p[ 1 ] = x >> 16; + e.p[ 2 ] = x >> 8; + e.p[ 3 ] = x; + return e.w; +} + +boost::uint32_t big_to_native( boost::uint32_t x ) +{ + endian_convert e; + + e.w = x; + x = e.p[ 0 ]; + x <<= 8; + x |= e.p[ 1 ]; + x <<= 8; + x |= e.p[ 2 ]; + x <<= 8; + x |= e.p[ 3 ]; + return x; +} +#endif + +// Define CRC parameters inside traits classes. Probably will use this in a +// future version of the CRC libray! +template < std::size_t Bits > +class my_crc_rt_traits +{ +public: + typedef boost::integral_constant<std::size_t, Bits> register_length_c; + typedef typename boost::uint_t<Bits>::fast register_type; + typedef boost::crc_basic<Bits> computer_type; + + register_type divisor_polynominal; + register_type initial_remainder; + bool reflect_input_byte; + bool reflect_output_remainder; + register_type final_xor_mask; + + computer_type make_crc_basic() const + { return computer_type(divisor_polynominal, initial_remainder, + final_xor_mask, reflect_input_byte, reflect_output_remainder); } +}; + +template < std::size_t Bits, boost::uintmax_t DivisorPolynominal, + boost::uintmax_t InitialRemainder, bool ReflectInputBytes, + bool ReflectOutputRemainder, boost::uintmax_t FinalXorMask > +class my_crc_ct_traits +{ +public: + typedef my_crc_rt_traits<Bits> rt_adaptor_type; + typedef typename rt_adaptor_type::register_type register_type; + typedef boost::crc_optimal<Bits, DivisorPolynominal, InitialRemainder, + FinalXorMask, ReflectInputBytes, ReflectOutputRemainder> computer_type; + + typedef boost::integral_constant<std::size_t, Bits> register_length_c; + typedef boost::integral_constant<register_type, DivisorPolynominal> + divisor_polynominal_c; + typedef boost::integral_constant<register_type, InitialRemainder> + initial_remainder_c; + typedef boost::integral_constant<bool, ReflectInputBytes> reflect_input_byte_c; + typedef boost::integral_constant<bool, ReflectOutputRemainder> + reflect_output_remainder_c; + typedef boost::integral_constant<register_type, FinalXorMask> + final_xor_mask_c; + + operator rt_adaptor_type() const + { + rt_adaptor_type const result = { divisor_polynominal_c::value, + initial_remainder_c::value, reflect_input_byte_c::value, + reflect_output_remainder_c::value, final_xor_mask_c::value }; + + return result; + } + + static computer_type make_crc_optimal() + { return boost::crc_optimal<register_length_c::value, + divisor_polynominal_c::value, initial_remainder_c::value, + final_xor_mask_c::value, reflect_input_byte_c::value, + reflect_output_remainder_c::value>(); } +}; + +template < std::size_t Bits, boost::uintmax_t DivisorPolynominal, + boost::uintmax_t InitialRemainder, bool ReflectInputBytes, + bool ReflectOutputRemainder, boost::uintmax_t FinalXorMask, + boost::uintmax_t StandardTestDataResult > +class my_crc_test_traits +{ +public: + typedef my_crc_ct_traits<Bits, DivisorPolynominal, InitialRemainder, + ReflectInputBytes, ReflectOutputRemainder, FinalXorMask> ct_traits_type; + typedef my_crc_rt_traits<Bits> rt_traits_type; + + typedef typename rt_traits_type::register_type register_type; + + typedef boost::integral_constant<std::size_t, Bits> register_length_c; + typedef boost::integral_constant<register_type, DivisorPolynominal> + divisor_polynominal_c; + typedef boost::integral_constant<register_type, InitialRemainder> + initial_remainder_c; + typedef boost::integral_constant<bool, ReflectInputBytes> reflect_input_byte_c; + typedef boost::integral_constant<bool, ReflectOutputRemainder> + reflect_output_remainder_c; + typedef boost::integral_constant<register_type, FinalXorMask> + final_xor_mask_c; + typedef boost::integral_constant<register_type, StandardTestDataResult> + standard_test_data_CRC_c; + + typedef typename ct_traits_type::computer_type computer_ct_type; + typedef typename rt_traits_type::computer_type computer_rt_type; + + static computer_ct_type make_crc_optimal() + { return ct_traits_type::make_crc_optimal(); } + static computer_rt_type make_crc_basic() + { return ct_traits_type().operator rt_traits_type().make_crc_basic(); } +}; + +// Now make some example CRC profiles +typedef my_crc_test_traits<16u, 0x8005u, 0u, true, true, 0u, std_crc_16_result> + my_crc_16_traits; +typedef my_crc_test_traits<16u, 0x1021u, 0xFFFFu, false, false, 0u, + std_crc_ccitt_false_result> my_crc_ccitt_false_traits; +typedef my_crc_test_traits<16u, 0x1021u, 0u, true, true, 0u, + std_crc_ccitt_true_result> my_crc_ccitt_true_traits; +typedef my_crc_test_traits<16u, 0x1021u, 0u, false, false, 0u, + std_crc_xmodem_result> my_crc_xmodem_traits; +typedef my_crc_test_traits<32u, 0x04C11DB7ul, 0xFFFFFFFFul, true, true, + 0xFFFFFFFFul, std_crc_32_result> my_crc_32_traits; + +template<class Test> +void run_crc_test_policies() +{ + Test()(my_crc_16_traits()); + Test()(my_crc_ccitt_false_traits()); + Test()(my_crc_ccitt_true_traits()); + Test()(my_crc_xmodem_traits()); + Test()(my_crc_32_traits()); +} + +// Need to test when ReflectInputBytes and ReflectOutputRemainder differ +// (Grabbed from table at <http://regregex.bbcmicro.net/crc-catalogue.htm>.) +typedef my_crc_test_traits<6u, 0x19u, 0u, true, false, 0u, 0x19u> + my_crc_6_darc_traits; +typedef my_crc_test_traits<12u, 0x80Fu, 0u, false, true, 0u, 0xDAFu> + my_crc_12_3gpp_traits; + +template<class Test> +void run_crc_extended_test_policies() +{ + Test()(my_crc_16_traits()); + Test()(my_crc_ccitt_false_traits()); + Test()(my_crc_ccitt_true_traits()); + Test()(my_crc_xmodem_traits()); + Test()(my_crc_32_traits()); +#if CONTROL_SUB_BYTE_MISMATCHED_REFLECTION_TEST + Test()(my_crc_6_darc_traits()); +#endif + Test()(my_crc_12_3gpp_traits()); +} + +// Bit mask constants +template < std::size_t BitIndex > +struct high_bit_mask_c + : boost::detail::high_bit_mask_c<BitIndex> +{}; +template < std::size_t BitCount > +struct low_bits_mask_c + : boost::detail::low_bits_mask_c<BitCount> +{}; + +} // anonymous namespace + + +// Unit tests ---------------------------------------------------------------// + +struct computation_comparison_test { +template<class CRCPolicy> +void operator()(CRCPolicy) +{ + BOOST_AUTO( crc_f, CRCPolicy::make_crc_optimal() ); + BOOST_AUTO( crc_s, CRCPolicy::make_crc_basic() ); + typename CRCPolicy::register_type const func_result + = boost::crc<CRCPolicy::register_length_c::value, + CRCPolicy::divisor_polynominal_c::value, + CRCPolicy::initial_remainder_c::value, + CRCPolicy::final_xor_mask_c::value, + CRCPolicy::reflect_input_byte_c::value, + CRCPolicy::reflect_output_remainder_c::value>( std_data, std_data_len ); + + crc_f.process_bytes( std_data, std_data_len ); + crc_s.process_bytes( std_data, std_data_len ); + + BOOST_TEST_EQ( crc_f.checksum(), + CRCPolicy::standard_test_data_CRC_c::value ); + BOOST_TEST_EQ( crc_s.checksum(), + CRCPolicy::standard_test_data_CRC_c::value ); + BOOST_TEST_EQ( CRCPolicy::standard_test_data_CRC_c::value, + func_result ); +} +}; + +struct accessor_and_split_run_test { +template<class CRCPolicy> +void operator()(CRCPolicy) +{ + typedef typename CRCPolicy::computer_ct_type optimal_crc_type; + typedef typename CRCPolicy::computer_rt_type basic_crc_type; + + // Test accessors + optimal_crc_type faster_crc1; + basic_crc_type slower_crc1( faster_crc1.get_truncated_polynominal(), + faster_crc1.get_initial_remainder(), faster_crc1.get_final_xor_value(), + faster_crc1.get_reflect_input(), faster_crc1.get_reflect_remainder() ); + + BOOST_TEST_EQ( faster_crc1.get_interim_remainder(), + slower_crc1.get_initial_remainder() ); + + // Process the first half of the standard data + std::size_t const mid_way = std_data_len / 2u; + + faster_crc1.process_bytes( std_data, mid_way ); + slower_crc1.process_bytes( std_data, mid_way ); + + BOOST_TEST_EQ( faster_crc1.checksum(), slower_crc1.checksum() ); + + // Process the second half of the standard data, testing more accessors + unsigned char const * const std_data_end = std_data + std_data_len; + boost::crc_optimal<optimal_crc_type::bit_count, + optimal_crc_type::truncated_polynominal, + optimal_crc_type::initial_remainder, optimal_crc_type::final_xor_value, + optimal_crc_type::reflect_input, optimal_crc_type::reflect_remainder> + faster_crc2( faster_crc1.get_interim_remainder() ); + boost::crc_basic<basic_crc_type::bit_count> slower_crc2( + slower_crc1.get_truncated_polynominal(), + slower_crc1.get_interim_remainder(), slower_crc1.get_final_xor_value(), + slower_crc1.get_reflect_input(), slower_crc1.get_reflect_remainder() ); + + faster_crc2.process_block( std_data + mid_way, std_data_end ); + slower_crc2.process_block( std_data + mid_way, std_data_end ); + + BOOST_TEST_EQ( slower_crc2.checksum(), faster_crc2.checksum() ); + BOOST_TEST_EQ( faster_crc2.checksum(), + CRCPolicy::standard_test_data_CRC_c::value ); + BOOST_TEST_EQ( CRCPolicy::standard_test_data_CRC_c::value, + slower_crc2.checksum() ); +} +}; + +struct reset_and_single_bit_error_test { +template<class CRCPolicy> +void operator()(CRCPolicy) +{ + // A single-bit error in a CRC can be guaranteed to be detected if the + // modulo-2 polynomial divisor has at least two non-zero coefficients. The + // implicit highest coefficient is always one, so that leaves an explicit + // coefficient, i.e. at least one of the polynomial's bits is set. + BOOST_TEST( CRCPolicy::divisor_polynominal_c::value & + low_bits_mask_c<CRCPolicy::register_length_c::value>::value ); + + // Create a random block of data + boost::uint32_t ran_data[ 256 ]; + std::size_t const ran_length = sizeof(ran_data) / sizeof(ran_data[0]); + + std::generate_n( ran_data, ran_length, boost::minstd_rand() ); + + // Create computers and compute the checksum of the data + BOOST_AUTO( optimal_tester, CRCPolicy::make_crc_optimal() ); + BOOST_AUTO( basic_tester, CRCPolicy::make_crc_basic() ); + + optimal_tester.process_bytes( ran_data, sizeof(ran_data) ); + basic_tester.process_bytes( ran_data, sizeof(ran_data) ); + + BOOST_AUTO( const optimal_checksum, optimal_tester.checksum() ); + BOOST_AUTO( const basic_checksum, basic_tester.checksum() ); + + BOOST_TEST_EQ( optimal_checksum, basic_checksum ); + + // Do the checksum again, while testing the capability to reset the current + // remainder (to either a default or a given value) + optimal_tester.reset(); + basic_tester.reset( CRCPolicy::initial_remainder_c::value ); + + optimal_tester.process_bytes( ran_data, sizeof(ran_data) ); + basic_tester.process_bytes( ran_data, sizeof(ran_data) ); + + BOOST_TEST_EQ( optimal_tester.checksum(), basic_tester.checksum() ); + BOOST_TEST_EQ( optimal_tester.checksum(), optimal_checksum ); + BOOST_TEST_EQ( basic_tester.checksum(), basic_checksum ); + + // Introduce a single-bit error + ran_data[ ran_data[0] % ran_length ] ^= ( 1u << (ran_data[ 1 ] % 32u) ); + + // Compute the checksum of the errorenous data, while continuing to test + // the remainder-resetting methods + optimal_tester.reset( CRCPolicy::initial_remainder_c::value ); + basic_tester.reset(); + + optimal_tester.process_bytes( ran_data, sizeof(ran_data) ); + basic_tester.process_bytes( ran_data, sizeof(ran_data) ); + + BOOST_TEST_EQ( basic_tester.checksum(), optimal_tester.checksum() ); + BOOST_TEST_NE( optimal_checksum, optimal_tester.checksum() ); + BOOST_TEST_NE( basic_checksum, basic_tester.checksum() ); +} +}; + +void augmented_crc_test() +{ + using std::size_t; + using boost::uint32_t; + using boost::augmented_crc; + + // Common CRC parameters, all others are zero/false + static size_t const bits = 32u; + static uint32_t const poly = 0x04C11DB7ul; + + // Create a random block of data, with space at the end for a CRC + static size_t const data_length = 256u; + static size_t const run_length = data_length + 1u; + + uint32_t run_data[ run_length ]; + uint32_t & run_crc = run_data[ data_length ]; + size_t const data_size = sizeof( run_data ) - sizeof( run_crc ); + + std::generate_n( run_data, data_length, boost::minstd_rand() ); + run_crc = 0u; + + // The augmented-CRC routine needs to push an appropriate number of zero + // bits (the register size) through before the checksum can be extracted. + // The other CRC methods, which are un-augmented, don't need to do this. + uint32_t const checksum = boost::crc<bits, poly, 0u, 0u, false, false>( + run_data, data_size ); + + BOOST_TEST_EQ( (augmented_crc<bits, poly>)(run_data, sizeof( run_data + )), checksum ); + + // Now appending a message's CRC to the message should lead to a zero-value + // checksum. Note that the CRC must be read from the largest byte on down, + // i.e. big-endian! + run_crc = native_to_big( checksum ); + BOOST_TEST_EQ( (augmented_crc<bits, poly>)(run_data, sizeof( run_data + )), 0u ); + + // Check again with the non-augmented methods + boost::crc_basic<bits> crc_b( poly ); + + crc_b.process_bytes( run_data, data_size ); + BOOST_TEST_EQ( crc_b.checksum(), checksum ); + + // Introduce a single-bit error, now the checksum shouldn't match! + uint32_t const affected_word_index = run_data[ 0 ] % data_length; + uint32_t const affected_bit_index = run_data[ 1 ] % 32u; + uint32_t const affecting_mask = 1ul << affected_bit_index; + + run_data[ affected_word_index ] ^= affecting_mask; + + crc_b.reset(); + crc_b.process_bytes( run_data, data_size ); + BOOST_TEST_NE( crc_b.checksum(), checksum ); + + BOOST_TEST_NE( (augmented_crc<bits, poly>)(run_data, sizeof( run_data )), + 0u ); + + run_crc = 0u; + BOOST_TEST_NE( (augmented_crc<bits, poly>)(run_data, sizeof( run_data )), + checksum ); + + // Now introduce the single error in the checksum instead + run_data[ affected_word_index ] ^= affecting_mask; + run_crc = native_to_big( checksum ) ^ affecting_mask; + BOOST_TEST_NE( (augmented_crc<bits, poly>)(run_data, sizeof( run_data )), + 0u ); + + // Repeat these tests with a non-zero initial remainder. Before we can + // check the results against a non-augmented CRC computer, realize that they + // interpret the inital remainder differently. However, the two standards + // can convert between each other. + // (checksum2 initial value is as a scratch pad. So are the address and new + // value of run_crc, but it's also useful for the next sub-step.) + // (TODO: getting the equivalent unaugmented-CRC initial-remainder given an + // augmented-CRC initial-remainder is done by putting said augmented-CRC + // initial-remainder through the augmented-CRC computation with a + // zero-value message. I don't know how to go the other way, yet.) + run_crc = 0u; + uint32_t checksum2 = run_data[ run_data[2] % data_length ]; + uint32_t const initial_residue = checksum2 + !checksum2; // ensure nonzero + uint32_t const initial_residue_unaugmented = augmented_crc<bits, poly>( + &run_crc, sizeof(run_crc), initial_residue ); + + BOOST_TEST_NE( initial_residue, 0u ); + crc_b.reset( initial_residue_unaugmented ); + crc_b.process_bytes( run_data, data_size ); + checksum2 = crc_b.checksum(); + + BOOST_TEST_EQ( run_crc, 0u ); + BOOST_TEST_EQ( (augmented_crc<bits, poly>)(run_data, sizeof( run_data ), + initial_residue), checksum2 ); + run_crc = native_to_big( checksum2 ); + BOOST_TEST_EQ( (augmented_crc<bits, poly>)(run_data, sizeof( run_data ), + initial_residue), 0u ); + + // Use the inital remainder argument to split a CRC-computing run + size_t const split_index = data_length / 2u; + uint32_t const intermediate = augmented_crc<bits, poly>( run_data, + sizeof(run_crc) * split_index, initial_residue ); + + BOOST_TEST_EQ( (augmented_crc<bits, poly>)(&run_data[ split_index ], + sizeof( run_data ) - sizeof( run_crc ) * split_index, intermediate), 0u ); + run_crc = 0u; + BOOST_TEST_EQ( (augmented_crc<bits, poly>)(&run_data[ split_index ], + sizeof( run_data ) - sizeof( run_crc ) * split_index, intermediate), + checksum2 ); + + // Repeat the single-bit error test, with a non-zero initial-remainder + run_data[ run_data[3] % data_length ] ^= ( 1ul << (run_data[4] % 32u) ); + run_crc = native_to_big( checksum2 ); + BOOST_TEST_NE( (augmented_crc<bits, poly>)(run_data, sizeof( run_data ), + initial_residue), 0u ); +} + +// Optimal computer, via the single-run function +unsigned crc_f1( const void * buffer, std::size_t byte_count ) +{ + return boost::crc<3u, 0x03u, 0u, 0u, false, false>( buffer, byte_count ); +} + +void sub_nybble_polynominal_test() +{ + // The CRC standard is a SDH/SONET Low Order LCAS control word with CRC-3 + // taken from ITU-T G.707 (12/03) XIII.2. + + // Four samples, each four bytes; should all have a CRC of zero + unsigned char const samples[4][4] + = { + { 0x3Au, 0xC4u, 0x08u, 0x06u }, + { 0x42u, 0xC5u, 0x0Au, 0x41u }, + { 0x4Au, 0xC5u, 0x08u, 0x22u }, + { 0x52u, 0xC4u, 0x08u, 0x05u } + }; + + // Basic computer + boost::crc_basic<3u> crc_1( 0x03u ); + + crc_1.process_bytes( samples[0], 4u ); + BOOST_TEST_EQ( crc_1.checksum(), 0u ); + + crc_1.reset(); + crc_1.process_bytes( samples[1], 4u ); + BOOST_TEST_EQ( crc_1.checksum(), 0u ); + + crc_1.reset(); + crc_1.process_bytes( samples[2], 4u ); + BOOST_TEST_EQ( crc_1.checksum(), 0u ); + + crc_1.reset(); + crc_1.process_bytes( samples[3], 4u ); + BOOST_TEST_EQ( crc_1.checksum(), 0u ); + + BOOST_TEST_EQ( crc_f1(samples[ 0 ], 4u), 0u ); + BOOST_TEST_EQ( crc_f1(samples[ 1 ], 4u), 0u ); + BOOST_TEST_EQ( crc_f1(samples[ 2 ], 4u), 0u ); + BOOST_TEST_EQ( crc_f1(samples[ 3 ], 4u), 0u ); + + // TODO: do similar tests with boost::augmented_crc<3, 0x03> + // (Now I think that this can't be done right now, since that function reads + // byte-wise, so the register size needs to be a multiple of CHAR_BIT.) +} + +// Optimal computer, via the single-run function +unsigned crc_f2( const void * buffer, std::size_t byte_count ) +{ + return boost::crc<7u, 0x09u, 0u, 0u, false, false>( buffer, byte_count ); +} + +void sub_octet_polynominal_test() +{ + // The CRC standard is a SDH/SONET J0/J1/J2/N1/N2/TR TTI (trace message) + // with CRC-7, o.a. ITU-T G.707 Annex B, G.832 Annex A. + + // Two samples, each sixteen bytes + // Sample 1 is '\x80' + ASCII("123456789ABCDEF") + // Sample 2 is '\x80' + ASCII("TTI UNAVAILABLE") + unsigned char const samples[2][16] + = { + { 0x80u, 0x31u, 0x32u, 0x33u, 0x34u, 0x35u, 0x36u, 0x37u, 0x38u, + 0x39u, 0x41u, 0x42u, 0x43u, 0x44u, 0x45u, 0x46u }, + { 0x80u, 0x54u, 0x54u, 0x49u, 0x20u, 0x55u, 0x4Eu, 0x41u, 0x56u, + 0x41u, 0x49u, 0x4Cu, 0x41u, 0x42u, 0x4Cu, 0x45u } + }; + unsigned const results[2] = { 0x62u, 0x23u }; + + // Basic computer + boost::crc_basic<7u> crc_1( 0x09u ); + + crc_1.process_bytes( samples[0], 16u ); + BOOST_TEST_EQ( crc_1.checksum(), results[0] ); + + crc_1.reset(); + crc_1.process_bytes( samples[1], 16u ); + BOOST_TEST_EQ( crc_1.checksum(), results[1] ); + + BOOST_TEST_EQ( crc_f2(samples[ 0 ], 16u), results[0] ); + BOOST_TEST_EQ( crc_f2(samples[ 1 ], 16u), results[1] ); + + // TODO: do similar tests with boost::augmented_crc<7, 0x09> + // (Now I think that this can't be done right now, since that function reads + // byte-wise, so the register size needs to be a multiple of CHAR_BIT.) +} + +void one_bit_polynominal_test() +{ + // Try a CRC based on the (x + 1) polynominal, which is a factor in + // many real-life polynominals and doesn't fit evenly in a byte. + boost::crc_basic<1u> crc_1( 1u ); + + crc_1.process_bytes( std_data, std_data_len ); + BOOST_TEST_EQ( crc_1.checksum(), 1u ); + + // Do it again, but using crc_optimal. The real purpose of this is to test + // crc_optimal::process_byte, which doesn't get exercised anywhere else in + // this file (directly or indirectly). + boost::crc_optimal<1u, 1u, 0u, 0u, false, false> crc_2; + + for ( std::size_t i = 0u ; i < std_data_len ; ++i ) + crc_2.process_byte( std_data[i] ); + BOOST_TEST_EQ( crc_2.checksum(), 1u ); +} + +struct function_object_test { +template<class CRCPolicy> +void operator()(CRCPolicy) +{ + typename CRCPolicy::computer_ct_type crc_c; + + crc_c = std::for_each( std_data, std_data + std_data_len, crc_c ); + BOOST_TEST_EQ( crc_c(), CRCPolicy::standard_test_data_CRC_c::value ); +} +}; + +// Ticket #2492: crc_optimal with reversed CRC16 +// <https://svn.boost.org/trac/boost/ticket/2492> +void issue_2492_test() +{ + // I'm trusting that the original bug reporter got his/her calculations + // correct. + boost::uint16_t const expected_result = 0xF990u; + + boost::crc_optimal<16, 0x100Bu, 0xFFFFu, 0x0000, true, false> boost_crc_1; + boost::crc_basic<16> boost_crc_2( 0x100Bu, 0xFFFFu, 0x0000, true, false ); + + // This should be right... + boost_crc_1.process_byte( 0u ); + BOOST_TEST_EQ( boost_crc_1.checksum(), expected_result ); + + // ...but the reporter said this didn't reflect, giving 0x099F as the + // (wrong) result. However, I get the right answer! + boost_crc_2.process_byte( 0u ); + BOOST_TEST_EQ( boost_crc_2.checksum(), expected_result ); +} + +int main() +{ + run_crc_extended_test_policies<computation_comparison_test>(); + run_crc_test_policies<accessor_and_split_run_test>(); + run_crc_test_policies<reset_and_single_bit_error_test>(); + augmented_crc_test(); + sub_nybble_polynominal_test(); + sub_octet_polynominal_test(); + one_bit_polynominal_test(); + run_crc_test_policies<function_object_test>(); + issue_2492_test(); + return boost::report_errors(); +} |