problem with small width CRCs
Hi, I ran into a problem using the CRC library for SDH LCAS control words (3-bit CRC) and SDH Trail Trace Identifier messages (7-bit CRC). For CRC widths smaller than character width the theoretical and optimized CRC computers produce different results for non-reflected input. Gcc produces this warning: /usr/local/boost/boost_1_31_0/boost/crc.hpp:581: warning: right shift count >= width of type The problem is that for the table based computer the msb of the remainder needs to be compared to the msb of the input byte. For most popular CRC parameters that's a right shift, but for CRC widths smaller than a character this should be a left shift... Reflected input requires comparing lsb's which doesn't involve any shifting. I've attached a patch that solved the problem for me. Regards, Bert Klaps /usr/local/boost/boost_1_31_0/boost/crc.hpp: In static member function `static unsigned char boost::detail::crc_helper<Bits, false>::index(typename boost::uint_t<Bits>::fast, unsigned char) [with unsigned int Bits = 3]': /usr/local/boost/boost_1_31_0/boost/crc.hpp:928: instantiated from `void boost::crc_optimal<Bits, TruncPoly, InitRem, FinalXor, ReflectIn, ReflectRem>::process_block(const void*, const void*) [with unsigned int Bits = 3, typename boost::uint_t<Bits>::fast TruncPoly = 3, typename boost::uint_t<Bits>::fast InitRem = 0, typename boost::uint_t<Bits>::fast FinalXor = 0, bool ReflectIn = false, bool ReflectRem = false]' /usr/local/boost/boost_1_31_0/boost/crc.hpp:947: instantiated from `void boost::crc_optimal<Bits, TruncPoly, InitRem, FinalXor, ReflectIn, ReflectRem>::process_bytes(const void*, unsigned int) [with unsigned int Bits = 3, typename boost::uint_t<Bits>::fast TruncPoly = 3, typename boost::uint_t<Bits>::fast InitRem = 0, typename boost::uint_t<Bits>::fast FinalXor = 0, bool ReflectIn = false, bool ReflectRem = false]' /usr/local/boost/boost_1_31_0/boost/crc.hpp:907: instantiated from `void boost::crc_optimal<Bits, TruncPoly, InitRem, FinalXor, ReflectIn, ReflectRem>::process_byte(unsigned char) [with unsigned int Bits = 3, typename boost::uint_t<Bits>::fast TruncPoly = 3, typename boost::uint_t<Bits>::fast InitRem = 0, typename boost::uint_t<Bits>::fast FinalXor = 0, bool ReflectIn = false, bool ReflectRem = false]' /usr/local/boost/boost_1_31_0/boost/crc.hpp:973: instantiated from `void boost::crc_optimal<Bits, TruncPoly, InitRem, FinalXor, ReflectIn, ReflectRem>::operator()(unsigned char) [with unsigned int Bits = 3, typename boost::uint_t<Bits>::fast TruncPoly = 3, typename boost::uint_t<Bits>::fast InitRem = 0, typename boost::uint_t<Bits>::fast FinalXor = 0, bool ReflectIn = false, bool ReflectRem = false]' /usr/lib/gcc-lib/i686-pc-linux-gnu/3.3.3/include/g++-v3/bits/stl_algo.h:157: instantiated from `_Function std::for_each(_InputIter, _InputIter, _Function) [with _InputIter = __gnu_cxx::__normal_iterator<unsigned char*, std::vector<unsigned char, std::allocator<unsigned char> > >, _Function = boost::crc_optimal<3, 3, 0, 0, false, false>]' lcas.cpp:44: instantiated from here /usr/local/boost/boost_1_31_0/boost/crc.hpp:581: warning: right shift count >= width of type *** crc.hpp.orig Tue Aug 10 14:10:34 2004 --- crc.hpp Tue Aug 10 14:57:06 2004 *************** *** 527,532 **** --- 527,556 ---- did_init = true; } + #ifndef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION + // Align the msb of the remainder to a byte + template < std::size_t Bits, bool RightShift > + class remainder + { + public: + typedef typename uint_t<Bits>::fast value_type; + + static unsigned char align_msb( value_type rem ) + { return rem >> (Bits - CHAR_BIT); } + }; + + // Specialization for the case that the remainder has less + // bits than a byte: align the remainder msb to the byte msb + template < std::size_t Bits > + class remainder< Bits, false > + { + public: + typedef typename uint_t<Bits>::fast value_type; + + static unsigned char align_msb( value_type rem ) + { return rem << (CHAR_BIT - Bits); } + }; + #endif // CRC helper routines template < std::size_t Bits, bool DoReflect > *************** *** 555,561 **** // Compare a byte to the remainder's highest byte static unsigned char index( value_type rem, unsigned char x ) ! { return x ^ ( rem >> (DoReflect ? 0u : Bits - CHAR_BIT) ); } // Shift out the remainder's highest byte static value_type shift( value_type rem ) --- 579,587 ---- // Compare a byte to the remainder's highest byte static unsigned char index( value_type rem, unsigned char x ) ! { return x ^ ( DoReflect ? rem : ! ((Bits>CHAR_BIT)?( rem >> (Bits - CHAR_BIT) ) : ! ( rem << (CHAR_BIT - Bits) ))); } // Shift out the remainder's highest byte static value_type shift( value_type rem ) *************** *** 578,584 **** // Compare a byte to the remainder's highest byte static unsigned char index( value_type rem, unsigned char x ) ! { return x ^ ( rem >> (Bits - CHAR_BIT) ); } // Shift out the remainder's highest byte static value_type shift( value_type rem ) --- 604,610 ---- // Compare a byte to the remainder's highest byte static unsigned char index( value_type rem, unsigned char x ) ! { return x ^ remainder<Bits,(Bits>CHAR_BIT)>::align_msb( rem ); } // Shift out the remainder's highest byte static value_type shift( value_type rem )
On 8/10/04 11:32 AM, "Bert Klaps" <bertk@txc.com> wrote:
I ran into a problem using the CRC library for SDH LCAS control words (3-bit CRC) and SDH Trail Trace Identifier messages (7-bit CRC).
Could you provide sample data and answer so a new test case can be added?
For CRC widths smaller than character width the theoretical and optimized CRC computers produce different results for non-reflected input. Gcc produces this warning:
/usr/local/boost/boost_1_31_0/boost/crc.hpp:581: warning: right shift count >= width of type
The problem is that for the table based computer the msb of the remainder needs to be compared to the msb of the input byte. For most popular CRC parameters that's a right shift, but for CRC widths smaller than a character this should be a left shift...
Reflected input requires comparing lsb's which doesn't involve any shifting.
I've attached a patch that solved the problem for me. [TRUNCATED list of errors and the patch]
Does anyone know how to add patches to a file? (It looked like it was in a "diff" format. Isn't there an automated tool for this, or do I apply the changes manually?) Have we branched for release yet? I don't want to add the changes (to the main line) until then so I won't risk breaking the release build. -- Daryle Walker Mac, Internet, and Video Game Junkie darylew AT hotmail DOT com
On Sat, 14 Aug 2004 22:44:48 -0400, Daryle Walker wrote
Does anyone know how to add patches to a file? (It looked like it was in a "diff" format. Isn't there an automated tool for this, or do I apply the changes manually?)
On unix it's typically: patch filename_to_patch name_of_patchfile
Have we branched for release yet? I don't want to add the changes (to the main line) until then so I won't risk breaking the release build.
Nope, no branch that I've seen yet... Jeff
On Sat, Aug 14, 2004 at 10:44:48PM -0400, Daryle Walker wrote:
On 8/10/04 11:32 AM, "Bert Klaps" <bertk@txc.com> wrote:
I ran into a problem using the CRC library for SDH LCAS control words (3-bit CRC) and SDH Trail Trace Identifier messages (7-bit CRC).
Could you provide sample data and answer so a new test case can be added?
Sure, though in the end I picked random values for polynomials etc and found that for CRC width or `Bits' < 8 and ReflectIn = false crc_basic and crc_optimal give different results for those as well - crc_basic is correct of course. Example #1 is a SDH/SONET Low Order LCAS control word with CRC-3 taken from ITU-T G.707 (12/03) XIII.2: That's a 29 bit word protected by a 3 bit CRC, together 32 bits or 4 bytes. The ITU-T text itself has 4 examples which include a correct CRC-3. So the answer to these four sequences should be zero. a. 0x3a 0xc4 0x08 0x06, answer is 0 b. 0x42 0xc5 0x0a 0x41, answer is 0 c. 0x4a 0xc5 0x08 0x22, answer is 0 d. 0x52 0xc4 0x08 0x05, answer is 0 The LCAS CRC-3 parameters are: - polynomial: 0x3 ( x^3 + x + 1 ) - initial remainder: 0 - final xor value: 0 - reflected input: false - reflected remainder: false Example #2 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: That's basically calculated over 16 bytes: the first input byte is always 0x80, the following 15 bytes are printable characters. Some examples: a. "\x80""123456789ABCDEF" , answer is 0x62 b. "\x80""TTI UNAVAILABLE" , answer is 0x23 The TTI CRC-7 parameters are: - polynomial: 0x9 ( x^7 + x^3 + 1 ) - initial remainder: 0 - final xor value: 0 - reflected input: false - reflected remainder: false
Does anyone know how to add patches to a file? (It looked like it was in a "diff" format.
Plain "diff -c"... Regards Bert Klaps
On 8/15/04 5:34 PM, "Bert Klaps" <bertk@easics.be> wrote:
On Sat, Aug 14, 2004 at 10:44:48PM -0400, Daryle Walker wrote:
On 8/10/04 11:32 AM, "Bert Klaps" <bertk@txc.com> wrote:
I ran into a problem using the CRC library for SDH LCAS control words (3-bit CRC) and SDH Trail Trace Identifier messages (7-bit CRC).
Could you provide sample data and answer so a new test case can be added?
Sure, though in the end I picked random values for polynomials etc and found that for CRC width or `Bits' < 8 and ReflectIn = false crc_basic and crc_optimal give different results for those as well - crc_basic is correct of course.
Example #1 is a SDH/SONET Low Order LCAS control word with CRC-3 taken from ITU-T G.707 (12/03) XIII.2: That's a 29 bit word protected by a 3 bit CRC, together 32 bits or 4 bytes. The ITU-T text itself has 4 examples which include a correct CRC-3. So the answer to these four sequences should be zero. a. 0x3a 0xc4 0x08 0x06, answer is 0 b. 0x42 0xc5 0x0a 0x41, answer is 0 c. 0x4a 0xc5 0x08 0x22, answer is 0 d. 0x52 0xc4 0x08 0x05, answer is 0 The LCAS CRC-3 parameters are: - polynomial: 0x3 ( x^3 + x + 1 ) - initial remainder: 0 - final xor value: 0 - reflected input: false - reflected remainder: false
Example #2 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: That's basically calculated over 16 bytes: the first input byte is always 0x80, the following 15 bytes are printable characters. Some examples: a. "\x80""123456789ABCDEF" , answer is 0x62 b. "\x80""TTI UNAVAILABLE" , answer is 0x23 The TTI CRC-7 parameters are: - polynomial: 0x9 ( x^7 + x^3 + 1 ) - initial remainder: 0 - final xor value: 0 - reflected input: false - reflected remainder: false
Does anyone know how to add patches to a file? (It looked like it was in a "diff" format.
Plain "diff -c"...
OK, I added the fixes from the original patch, and I added the two test cases above. I'm wondering: do the augmented-CRC functions need similar protection from inappropriate shifting? When I tried the augmented-CRC functions with the new tests, I got (right) shifting warnings. My attempt to generalize the patch fix to the augmented-CRC functions got simultaneous left- and right-shift warnings (so I removed that "fix"). I guess I haven't thought about the problem enough. The affected files would be "crc.hpp" and "crc_test.cpp". -- Daryle Walker Mac, Internet, and Video Game Junkie darylew AT hotmail DOT com
participants (4)
-
Bert Klaps -
Bert Klaps -
Daryle Walker -
Jeff Garland