5
\$\begingroup\$

Here is a template class to calculate various CRC checksums. I go out my way to achieve a good C++ encapsulation for a C style code .

Any advice or suggestion is welcome.

//crc.hpp
#ifndef __CRC_HEADER_H__
#define __CRC_HEADER_H__
#include <array>
#include <mutex>

template <typename T, T POLYNOMIAL, T INITIAL_REMAINDER, T FINAL_XOR_VALUE, bool REFLECT_DATA, bool REFLECT_REMAINDER>
class CrcCal
{
public:
    CrcCal();
    T Cal(const uint8_t *message, int nBytes) const;

private:
    unsigned long reflect(unsigned long data, unsigned char nBits) const;
    void InitTable(void); 

static std::array<T, 256> crc_table;
static constexpr uint32_t WIDTH{ 8 * sizeof(T) };
static constexpr uint32_t TOPBIT{ 1u << (uint32_t)(WIDTH - 1) };
static std::once_flag init_flag;
};

using Crc32 = CrcCal<uint32_t, 0x04C11DB7u, 0xFFFFFFFFu, 0xFFFFFFFFu, true, true>;

template class CrcCal<uint32_t, 0x04C11DB7u, 0xFFFFFFFFu, 0xFFFFFFFFu, true, true>;
#endif


//cpp
#include "crc.hpp"

template <typename T, T POLYNOMIAL, T INITIAL_REMAINDER, T FINAL_XOR_VALUE, bool REFLECT_DATA, bool REFLECT_REMAINDER>
unsigned long CrcCal<T, POLYNOMIAL, INITIAL_REMAINDER, FINAL_XOR_VALUE, REFLECT_DATA, REFLECT_REMAINDER>::reflect(unsigned long data, unsigned char nBits) const
{
    unsigned long  reflection = 0x00000000;
    unsigned char  bit;

    for (bit = 0; bit < nBits; ++bit)
    {
        if (data & 0x01)
        {
            reflection |= (1 << ((nBits - 1) - bit));
        }

        data = (data >> 1);
    }

    return (reflection);
}

template <typename T, T POLYNOMIAL, T INITIAL_REMAINDER, T FINAL_XOR_VALUE, bool REFLECT_DATA, bool REFLECT_REMAINDER>
T CrcCal<T, POLYNOMIAL, INITIAL_REMAINDER, FINAL_XOR_VALUE, REFLECT_DATA, REFLECT_REMAINDER>::Cal(const uint8_t *message, int nBytes) const
{
    T              remainder = INITIAL_REMAINDER;
    unsigned char  data;
    int            byte;
    if (REFLECT_DATA)
    {
        for (byte = 0; byte < nBytes; ++byte)
        {
        
            data = ((unsigned char) reflect(message[byte], 8)) ^ (remainder >> (WIDTH - 8));
            remainder = crc_table[data] ^ (remainder << 8);
        }
    }
    else
    {
        for (byte = 0; byte < nBytes; ++byte)
        {
        
            data = (message[byte]) ^ (remainder >> (WIDTH - 8));
            remainder = crc_table[data] ^ (remainder << 8);
        }
    }
    if (REFLECT_REMAINDER)
    {
        return (((T) reflect(remainder, WIDTH)) ^ FINAL_XOR_VALUE);
    }
    else
    {
        return (remainder ^ FINAL_XOR_VALUE);
    
    }
}  

template <typename T, T POLYNOMIAL, T INITIAL_REMAINDER, T FINAL_XOR_VALUE, bool REFLECT_DATA, bool REFLECT_REMAINDER>   
void CrcCal<T, POLYNOMIAL, INITIAL_REMAINDER, FINAL_XOR_VALUE, REFLECT_DATA, REFLECT_REMAINDER>::InitTable(void)
{
    T              remainder;
    int            dividend;
    unsigned char  bit;

    for (dividend = 0; dividend < 256; ++dividend)
    {
        remainder = dividend << (WIDTH - 8);
        for (bit = 8; bit > 0; --bit)
        {
            if (remainder & TOPBIT)
            {
                remainder = (remainder << 1) ^ POLYNOMIAL;
            }
            else
            {
                remainder = (remainder << 1);
            }
        }
        crc_table[dividend] = remainder;
    }
} 


template <typename T, T POLYNOMIAL, T INITIAL_REMAINDER, T FINAL_XOR_VALUE, bool REFLECT_DATA, bool REFLECT_REMAINDER>  
CrcCal<T, POLYNOMIAL, INITIAL_REMAINDER, FINAL_XOR_VALUE, REFLECT_DATA, REFLECT_REMAINDER>::CrcCal()
{
    std::call_once(init_flag, &CrcCal<T, POLYNOMIAL, INITIAL_REMAINDER, FINAL_XOR_VALUE, REFLECT_DATA, REFLECT_REMAINDER>::InitTable, this);
}

template <typename T, T POLYNOMIAL, T INITIAL_REMAINDER, T FINAL_XOR_VALUE, bool REFLECT_DATA, bool REFLECT_REMAINDER>
std::array<T, 256> CrcCal<T, POLYNOMIAL, INITIAL_REMAINDER, FINAL_XOR_VALUE, REFLECT_DATA, REFLECT_REMAINDER>::crc_table;

template <typename T, T POLYNOMIAL, T INITIAL_REMAINDER, T FINAL_XOR_VALUE, bool REFLECT_DATA, bool REFLECT_REMAINDER>
std::once_flag  CrcCal<T, POLYNOMIAL, INITIAL_REMAINDER, FINAL_XOR_VALUE, REFLECT_DATA, REFLECT_REMAINDER>::init_flag;
\$\endgroup\$
3
  • 1
    \$\begingroup\$ Do you have the test suite that goes with this? It's probably worth including it the same review, as that helps us understand what testing you've done, and what you've missed. It also helps validate any suggested changes, which is very much in your own interests. \$\endgroup\$ Commented Sep 6, 2021 at 13:17
  • \$\begingroup\$ @TobySpeight I am new to Code Review. Thank you for your advice. I will add it to the post soon. \$\endgroup\$
    – John
    Commented Sep 7, 2021 at 0:50
  • \$\begingroup\$ I wrote something previously to do this: github.com/Loki-Astari/ThorsCrypto/blob/master/src/ThorsCrypto/… reviewed here codereview.stackexchange.com/questions/248419/… \$\endgroup\$ Commented Sep 9, 2021 at 17:25

2 Answers 2

9
\$\begingroup\$

Here are some things that may help you improve your code.

Understand the nature of templates

In modern C++, putting headers in a header file and the implementation in a .cpp file is common and ingrained. However, in this case, it's also not correct. The reason is that templated functions don't actually cause the compiler to generate any code until and unless the template is instantiated. That means that in this particular case, since all of the functions are templates, all of the code should be in the the .hpp file and you don't need a .cpp file at all.

Provide complete code to reviewers

This is not so much a change to the code as a change in how you present it to other people. Without the full context of the code and an example of how to use it, it takes more effort for other people to understand your code. This affects not only code reviews, but also maintenance of the code in the future, by you or by others. One good way to address that is by the use of comments. Another good technique is to include test code showing how your code is intended to be used. Here's the main file I used to test:

#include "crc.hpp"
#include <iostream>
#include <iomanip>

int main() {
    CrcCal<uint16_t, 0x1021u, 0xffffu, 0xffffu, true, true> CCITT{};
    const uint8_t message[7] = {0xEE,0x00,0x00,0x00,0x00,0x01,0x20};
    auto crc{CCITT.Cal(message, 7)};
    std::cout << "CRC is 0x" << std::hex << std::setw(4) << std::setfill('0') 
        << crc << '\n';
}

Use modern C++ idiom

The site from which you've extracted some of this code includes some code that is not idiomatic, modern C++. For example, it includes these lines:

    data = (data >> 1);
}
return (reflection);

The first line would be better as data >>= 1; and the second should omit the parentheses because return is a keyword and NOT a function call.

Don't use all capital letters for named constants

Traditionally, the use of all capital letters has been reserved for #define constants. To avoid confusing users, don't use such names for anything else, such as WIDTH but also POLYNOMIAL, etc. See NL.9

Simplify your functions

The body of the reflect call could be much better written, I think, like so:

unsigned long reflection{0};
for (unsigned long outmask{1u}, inmask{1u << (nBits - 1)}; inmask; inmask >>= 1, outmask <<= 1) {
    if (data & inmask) {
        reflection |= outmask;
    }
}
return reflection;

The rationale for this is that now only single-bit shifts and bitwise and and or functions are used (no addition, subtraction or multi-bit shifts) which are efficient machine language instructions for most modern processors.

Use the required #includes

The code uses uint32_t which means that it should #include <cstdint>. It was not difficult to infer, but it helps reviewers if the code is complete.

Shift computation to compile time

Rather than using call_once, I would suggest letting the compiler create this table instead. The effect is that the table thus requires no runtime overhead at all to compute and it can also be put into ROM which is helpful for such things as embedded systems where RAM space is typically smaller than ROM space. Here's how to do that by simply rewriting your InitTable as a lambda:

static constexpr auto crc_table = [] {
    std::array<T, 256> tbl{};
    for (int dividend = 0; dividend < 256; ++dividend) {
        T remainder = dividend << (width - 8);
        for (uint8_t bit = 8; bit > 0; --bit) {
            if (remainder & topbit) {
                remainder = (remainder << 1) ^ polynomial;
            } else {
                remainder = (remainder << 1);
            }
        }
        tbl[dividend] = remainder;
    }
    return tbl;
}();

Note that lambdas are only implicitly constexpr in C++17 and later and that the use of constexpr in C++11 is very limited. It is possible to create a C++11 constexpr version, but it's long, difficult to follow and requires a number of helper functions. See Compile-time sieve of Eratosthenes for an example of how something like this might work.

Declare variables as late as possible

Don't declare all variables at the top of the function; that's an old C requirement, but it isn't done in C++. Instead, declare them when they are initialized. This avoids many kinds of errors that can occur with inadvertent use of uninitialized varibles.

Free your functions

There's no real good reason that reflect needs to be a member function. It doesn't even use any of the template parameters, so I'd instead declare it as a free function.

Declare functions constexpr if practical

Any time a function might be used at compile time, it helps the compiler optimizations if you declare it constexpr. So in this case, I'd write this:

constexpr unsigned long reflect(unsigned long data, unsigned char nBits) {

See F.4 for details.

Note that if you really must use C++11, it is possible to write this in a way that complies with C++11, but it's not pretty:

constexpr unsigned long reflect(unsigned long reflection, 
            unsigned long inmask, unsigned long outmask, 
            unsigned long data) 
{
    return inmask ? reflect(reflection | ((data & inmask) ? outmask : 0), 
            inmask << 1, outmask >> 1, data ) : reflection;
}
constexpr unsigned long reflect(unsigned long data, unsigned char nBits) {
    return reflect(0ul, 1ul, 1ul << (nBits - 1), data);
}

Generally speaking, in C++11 constexpr one must abuse the ?: operator to avoid using if...else, and use recursion to avoid using for.

Allow passing modern containers

The interface right now is restricted to a very antique C-style of passing a pointer and a length. Better would be to accept a pair of iterators, which would allow many kinds of modern containers such as std::vector or std::array or even std::string_view when you start using C++17.

Don't declare variables you'd don't use

The code currently contains these two lines:

using Crc32 = CrcCal<uint32_t, 0x04C11DB7u, 0xFFFFFFFFu, 0xFFFFFFFFu, true, true>;
template class CrcCal<uint32_t, 0x04C11DB7u, 0xFFFFFFFFu, 0xFFFFFFFFu, true, true>;

The first one is fine, because it only says that if one wants to use a standard Crc32, it's already declared. However, the next line causes a Crc32 instantiation which is not necessary.

Results

Here's a live version which shows the effects of using most of these suggestions. It also emphasizes the advantage to using constexpr where possible, since it causes this program to be reduced to exactly two runtime instructions:

#include "crc.hpp"

int main() {
    constexpr CrcCal<uint16_t, 0x1021u, 0xffffu, 0xffffu, true, true> CCITT{};
    constexpr uint8_t message[7] = {0xEE,0x00,0x00,0x00,0x00,0x01,0x20};
    static_assert(CCITT.Cal(message, 7) == 0x1013);
}
\$\endgroup\$
11
  • \$\begingroup\$ This code is tagged C++11. I don’t think any of the constexpr suggestions will work in C++11, because std::array wasn’t constexpr until C++17. \$\endgroup\$
    – indi
    Commented Sep 6, 2021 at 16:42
  • \$\begingroup\$ You are right that some of the constexpr items are C++17 only. Yet another motivation for updating the compiler. \$\endgroup\$
    – Edward
    Commented Sep 6, 2021 at 16:54
  • 2
    \$\begingroup\$ Honestly, at this point, I don’t think the problem is the compiler, but just a lack of knowledge. I see lots of people insisting they have to work in C++11 (or even C++98!), but I have a hard time believing there are still huge numbers of people using GCC 4.x or Clang 3.x, or otherwise constrained (for intelligent reasons) to ancient standards. I suspect the reason people think they have to use old standards is 5–10 year old FUD. That’s why I’ve decided to stop coddling people using old standards unless they give a DAMN good reason for it; line 1 of my reviews will be “use a modern standard”. \$\endgroup\$
    – indi
    Commented Sep 6, 2021 at 21:14
  • 2
    \$\begingroup\$ @John, indi's point is that identifiers with two consecutive underscores (or beginning with underscore and followed by an uppercase letter) are reserved identifiers for the implementation to use for any purpose. You are not permitted to define your own macros with such names; doing so is UB. \$\endgroup\$ Commented Sep 7, 2021 at 7:20
  • 1
    \$\begingroup\$ If that's the compiler you are stuck with and you can't update or upgrade it, you will either have to forego the benefits of constexpr or go through the effort to learn how to use the restrictive C++11 constexpr function restrictions. I prefer not to spend my time learning obsolete skills, but you may enjoy the challenge. \$\endgroup\$
    – Edward
    Commented Sep 7, 2021 at 13:28
5
\$\begingroup\$

use a function, not a class

A CrcCal class instance has no state (non-static member variables). The class therefore has no reason to exist. We can implement the algorithm as a simple function that operates on a range of data, and has some additional parameters, e.g.:

template<class T, T polynomial, T initial_remainder, T final_xor_value, bool reflect_data, bool reflect_remainder, class It>
constexpr T crc(It begin, It end)

template<class It>
constexpr std::uint32_t crc_32(It begin, It end) { return crc<std::uint32_t{ 0x04C11DB7 }, std::uint32_t(-1), std::uint32_t(-1), true, true>(begin, end); }

The table cache is a detail that can be taken care of with a static variable - but that does not need to be in a class either.

Note that the current interface forces the choice of polynomial, initial_remainder, etc. to happen at compile-time only. It might be nice to change all these settings to be standard function arguments. Since the function is constexpr we'd then get the best of both worlds (compile-time evaluation where possible, otherwise run-time evaluation). Unfortunately changing polynomial from a template argument to a function argument would cause problems with the creation of the cache table at compile time, since since C++ lacks static constexpr or static variables inside constexpr functions. :(

add safety and reduce complexity with assertions

It's probable that your code works for sensible inputs... but there are no guarantees that the inputs will be sensible, and there are a lot of possibilities to consider, e.g.:

What if message is a nullptr? What if nBytes is negative?

What if T is a signed integer? And what if it's 8 bits, what if it's 64 bits. What if it's not an integral type at all?

unsigned long isn't a fixed size type... will the code work for all its possible sizes?

We can use fixed size types and static_assertions at compile time to rule out cases that we don't want to handle, and assertions to catch remaining issues at run-time. Besides preventing edge-cases that would cause incorrect behavior (bugs), this helps catch user errors, documents the code, and reduces the burden of maintenance by reducing the complexity of the implementation.

avoid implicit conversions

reflect(message[byte], 8) this hides an important change from uint8_t to uint32_t in an implicit cast. It works fine at the moment, but if we decided to change reflect to a template function it would suddenly break.

(message[byte]) ^ (remainder >> (WIDTH - 8)) another hidden cast.

We should instead use a static_cast or at least brace initialization (std::uint32_t{ message[byte] }) to highlight the changes explicitly.

use the <limits> header to write reflect as a template function

It looks like the second parameter of reflect is always the number of bits in the original type, before casting to unsigned long. Instead of casting the value, hard-coding the number of bits as an argument, and then casting the result back, why not just write reflect as a template function taking a value of the appropriate type?

We can get the bit width directly from the type with std::numeric_limits<T>::digits.

We can restrict the function to sensible types with enable_if, or a static_assert, e.g.:

static_assert(std::is_unsigned_v<T>, "reflect expects an unsigned integral type.");

So maybe something like: https://godbolt.org/z/fjhcqP8hG (untested)

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Good comments! If I were writing this in C++20, I'd use c++20 concepts to implement some of your ideas. But as a practical matter, I'd actually just use Boost.CRC. :) \$\endgroup\$
    – Edward
    Commented Sep 8, 2021 at 12:14
  • 1
    \$\begingroup\$ You can leave off the static and just use constexpr for variables scoped inside a function. If you don't expose its address somehow, it generates compile-time constant code and doesn't make a copy for each call. \$\endgroup\$
    – JDługosz
    Commented Sep 8, 2021 at 14:38
  • 1
    \$\begingroup\$ I disagree with writing this as a function (rather than a class). This assumes you have all the data available at one time and ignored streaming interfaces. It may be very useful to be able to apply the data in chunks and thus you need to maintain state between the chunks. \$\endgroup\$ Commented Sep 9, 2021 at 17:29
  • \$\begingroup\$ @MartinYork I agree with you. \$\endgroup\$
    – John
    Commented Sep 10, 2021 at 14:24

Your Answer

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

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