1

I'm trying to implement the simple POSIX cksum using Boost.CRC.

The code I'm using amounts to this:

for(int i = 1; i<argc; ++i)
{
  support::file current(argv[i], support::file::access::read);
  size_t octets = 0;
  boost::crc_32_type crc;
  while(true)
  {
    size_t bytes_read = current.read_some(buffer_size, buffer);
    octets += bytes_read;
    crc.process_bytes(&buffer[0], bytes_read);
    if(bytes_read < buffer_size)
      break;
  }
  if(i>1)
    support::print("\n");

  support::print(boost::lexical_cast<string>(crc.checksum()) + " " + boost::lexical_cast<string>(octets) + " " + argv[i]);
}

Where support::file is a simple fopen/fread binary file I/O wrapper, which I succesfully used for a cat implementation. support::print gives the same output as std::cout, but I need it for reliable non-ASCII output on Windows.

The Boost header has this:

typedef crc_optimal<32, 0x04C11DB7, 0xFFFFFFFF, 0xFFFFFFFF, true, true> crc_32_type;

as the only 32-bit CRC typedef. It gives the wrong answer (checked with GNUWin32 coreutils cksum) for an empty file (touch test && cksum test). I have tried using the above typedef and modifying one or both of the 0xFFFFFFFF values to 0, I get the correct result for an empty file, but any other file still gives different results.

How is Boost.CRC related to the POSIX cksum specification?

1 Answer 1

1

This isn't really an answer to your question, but the results of the investigation that I've carried out. I used to struggle with CRC when I was building a simple implementation of an Ethernet controller in VHDL, and I do realize that implementations can be sometimes very varying due to reasons unknown.

Okay, let's begin. The typedef that you found in boost/crc.hpp :

typedef crc_optimal<32, 0x04C11DB7, 0xFFFFFFFF, 0xFFFFFFFF, true, true> crc_32_type;

Is a simple declaration of a CRC generator that will produce the CRC for Ethernet. The parameters of the template are as follows : Bits (the number of bits output by the generator), TruncPoly (the polynomial used by the generator), InitRem (the initial remainder to be fed into the algorithm before processing the first byte of input), FinalXor (the value that the output value should be XORed with after processing all the bytes of the input), ReflectIn and ReflectRem (if the input bytes and/or the output should be bit-reflected, e.g. bit 0 becomes bit 7, and so on). Ethernet not only requires the output to be calculated with the given polynomial, but it also requires the constraints that you can read from that typedef.

According to the specification of cksum, the typedef for the CRC generator for it should look something like this :

typedef crc_optimal<32, 0x04C11DB7, 0, 0xFFFFFFFF, false, false> cksum_crc_type;

This is because :

  • The specification doesn't specify a starting value for the generator, thus 0.
  • The output value should be complemented, according to number 4 of the specification. The same result can be achieved by XORing the value with ones.
  • Bit reflecting is not mentioned anywhere, and thus will not be performed.

However, there is one significant difference when it comes to cksum as opposed to ordinary CRCs :

(...) followed by one or more octets representing the length of the file as a binary value, least significant octet first. The smallest number of octets capable of representing this integer shall be used.

Ordinary CRC generators don't take into account the number of octets that were processed. This would also explain why you got a good result when processing a zero-length file, but a bad one when processing larger files.

Unfortunately, I don't see an easy solution for that problem. I guess what you could do is modify the process_bytes method in a following way :

template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly,
           BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor,
           bool ReflectIn, bool ReflectRem >
inline
void
BOOST_CRC_OPTIMAL_NAME::process_bytes
(
    void const *   buffer,
    std::size_t  byte_count
)
{
    unsigned char const * const  b = static_cast<unsigned char const *>(
     buffer );
    process_block( b, b + byte_count );
    for(; byte_count; byte_count >>= 8)
        rem_ = (rem_ << 8) ^ crc_table_type::table_[((rem_ >> 24) ^ byte_count) & 0xFF];
}

With such an implementation, the method gives the same result as cksum. for loop courtesy of GNU coreutils.

Hope I helped.

4
  • This is why I love SO. Thanks for the detailed analysis. I suppose writing a small wrapper function that does this and calls crc.process_block is the best solution without modifying Boost code.
    – rubenvb
    Apr 7, 2013 at 8:46
  • Sure, I guess that would work. But you need to access the CRC table that's used to compute it, and it's declared private. :( Maybe you could write a template specialization for the cksum CRC generator that would have its own implementation of process_block? Apr 7, 2013 at 9:10
  • Ah yes, template specialization could work. Let's hope I only have to implement process_block :).
    – rubenvb
    Apr 7, 2013 at 9:33
  • You have a few variables like the starting value and where/whether you complement. It's usually fairly quick to play with those. My test file with an initial CRC of 0xFFFFFFFF gives a CRC of 0x2B4F35FE which is wrong but I changed the initial value to 0 and got 0x92E04DBC which is right. This is on a slice-by-4 from create.stephan-brumme.com/crc32 Don't over-think it until you swap a few numbers around. This isn't the first time I've seen this happen.
    – Alan Corey
    Nov 7, 2018 at 2:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.