C++ Compile Time CRC32

compile_time_crc.hpp

/*
The MIT License (MIT)

Copyright (c) 2018 Ivor Wanders

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.
*/
#ifndef COMPILE_TIME_CRC_H
#define COMPILE_TIME_CRC_H

#include <cstdint>
#include <type_traits>

// Based on code from Python's crcmod module. Polynomial "crc-32".
// polynomial: 0x104C11DB7, bit reverse algorithm: 
//  crcmod.Crc(0x104C11DB7, initCrc=0, xorOut=0xFFFFFFFF)

namespace crcdetail
{
static constexpr const uint32_t table[256] =
{
    0x00000000U, 0x77073096U, 0xEE0E612CU, 0x990951BAU, 0x076DC419U,
    0x706AF48FU, 0xE963A535U, 0x9E6495A3U, 0x0EDB8832U, 0x79DCB8A4U,
    0xE0D5E91EU, 0x97D2D988U, 0x09B64C2BU, 0x7EB17CBDU, 0xE7B82D07U,
    0x90BF1D91U, 0x1DB71064U, 0x6AB020F2U, 0xF3B97148U, 0x84BE41DEU,
    0x1ADAD47DU, 0x6DDDE4EBU, 0xF4D4B551U, 0x83D385C7U, 0x136C9856U,
    0x646BA8C0U, 0xFD62F97AU, 0x8A65C9ECU, 0x14015C4FU, 0x63066CD9U,
    0xFA0F3D63U, 0x8D080DF5U, 0x3B6E20C8U, 0x4C69105EU, 0xD56041E4U,
    0xA2677172U, 0x3C03E4D1U, 0x4B04D447U, 0xD20D85FDU, 0xA50AB56BU,
    0x35B5A8FAU, 0x42B2986CU, 0xDBBBC9D6U, 0xACBCF940U, 0x32D86CE3U,
    0x45DF5C75U, 0xDCD60DCFU, 0xABD13D59U, 0x26D930ACU, 0x51DE003AU,
    0xC8D75180U, 0xBFD06116U, 0x21B4F4B5U, 0x56B3C423U, 0xCFBA9599U,
    0xB8BDA50FU, 0x2802B89EU, 0x5F058808U, 0xC60CD9B2U, 0xB10BE924U,
    0x2F6F7C87U, 0x58684C11U, 0xC1611DABU, 0xB6662D3DU, 0x76DC4190U,
    0x01DB7106U, 0x98D220BCU, 0xEFD5102AU, 0x71B18589U, 0x06B6B51FU,
    0x9FBFE4A5U, 0xE8B8D433U, 0x7807C9A2U, 0x0F00F934U, 0x9609A88EU,
    0xE10E9818U, 0x7F6A0DBBU, 0x086D3D2DU, 0x91646C97U, 0xE6635C01U,
    0x6B6B51F4U, 0x1C6C6162U, 0x856530D8U, 0xF262004EU, 0x6C0695EDU,
    0x1B01A57BU, 0x8208F4C1U, 0xF50FC457U, 0x65B0D9C6U, 0x12B7E950U,
    0x8BBEB8EAU, 0xFCB9887CU, 0x62DD1DDFU, 0x15DA2D49U, 0x8CD37CF3U,
    0xFBD44C65U, 0x4DB26158U, 0x3AB551CEU, 0xA3BC0074U, 0xD4BB30E2U,
    0x4ADFA541U, 0x3DD895D7U, 0xA4D1C46DU, 0xD3D6F4FBU, 0x4369E96AU,
    0x346ED9FCU, 0xAD678846U, 0xDA60B8D0U, 0x44042D73U, 0x33031DE5U,
    0xAA0A4C5FU, 0xDD0D7CC9U, 0x5005713CU, 0x270241AAU, 0xBE0B1010U,
    0xC90C2086U, 0x5768B525U, 0x206F85B3U, 0xB966D409U, 0xCE61E49FU,
    0x5EDEF90EU, 0x29D9C998U, 0xB0D09822U, 0xC7D7A8B4U, 0x59B33D17U,
    0x2EB40D81U, 0xB7BD5C3BU, 0xC0BA6CADU, 0xEDB88320U, 0x9ABFB3B6U,
    0x03B6E20CU, 0x74B1D29AU, 0xEAD54739U, 0x9DD277AFU, 0x04DB2615U,
    0x73DC1683U, 0xE3630B12U, 0x94643B84U, 0x0D6D6A3EU, 0x7A6A5AA8U,
    0xE40ECF0BU, 0x9309FF9DU, 0x0A00AE27U, 0x7D079EB1U, 0xF00F9344U,
    0x8708A3D2U, 0x1E01F268U, 0x6906C2FEU, 0xF762575DU, 0x806567CBU,
    0x196C3671U, 0x6E6B06E7U, 0xFED41B76U, 0x89D32BE0U, 0x10DA7A5AU,
    0x67DD4ACCU, 0xF9B9DF6FU, 0x8EBEEFF9U, 0x17B7BE43U, 0x60B08ED5U,
    0xD6D6A3E8U, 0xA1D1937EU, 0x38D8C2C4U, 0x4FDFF252U, 0xD1BB67F1U,
    0xA6BC5767U, 0x3FB506DDU, 0x48B2364BU, 0xD80D2BDAU, 0xAF0A1B4CU,
    0x36034AF6U, 0x41047A60U, 0xDF60EFC3U, 0xA867DF55U, 0x316E8EEFU,
    0x4669BE79U, 0xCB61B38CU, 0xBC66831AU, 0x256FD2A0U, 0x5268E236U,
    0xCC0C7795U, 0xBB0B4703U, 0x220216B9U, 0x5505262FU, 0xC5BA3BBEU,
    0xB2BD0B28U, 0x2BB45A92U, 0x5CB36A04U, 0xC2D7FFA7U, 0xB5D0CF31U,
    0x2CD99E8BU, 0x5BDEAE1DU, 0x9B64C2B0U, 0xEC63F226U, 0x756AA39CU,
    0x026D930AU, 0x9C0906A9U, 0xEB0E363FU, 0x72076785U, 0x05005713U,
    0x95BF4A82U, 0xE2B87A14U, 0x7BB12BAEU, 0x0CB61B38U, 0x92D28E9BU,
    0xE5D5BE0DU, 0x7CDCEFB7U, 0x0BDBDF21U, 0x86D3D2D4U, 0xF1D4E242U,
    0x68DDB3F8U, 0x1FDA836EU, 0x81BE16CDU, 0xF6B9265BU, 0x6FB077E1U,
    0x18B74777U, 0x88085AE6U, 0xFF0F6A70U, 0x66063BCAU, 0x11010B5CU,
    0x8F659EFFU, 0xF862AE69U, 0x616BFFD3U, 0x166CCF45U, 0xA00AE278U,
    0xD70DD2EEU, 0x4E048354U, 0x3903B3C2U, 0xA7672661U, 0xD06016F7U,
    0x4969474DU, 0x3E6E77DBU, 0xAED16A4AU, 0xD9D65ADCU, 0x40DF0B66U,
    0x37D83BF0U, 0xA9BCAE53U, 0xDEBB9EC5U, 0x47B2CF7FU, 0x30B5FFE9U,
    0xBDBDF21CU, 0xCABAC28AU, 0x53B39330U, 0x24B4A3A6U, 0xBAD03605U,
    0xCDD70693U, 0x54DE5729U, 0x23D967BFU, 0xB3667A2EU, 0xC4614AB8U,
    0x5D681B02U, 0x2A6F2B94U, 0xB40BBE37U, 0xC30C8EA1U, 0x5A05DF1BU,
    0x2D02EF8DU
};

constexpr uint32_t compute(const char* data, uint32_t len, uint32_t crc = 0)
{
    crc = crc ^ 0xFFFFFFFFU;
    for (uint32_t i = 0; i < len; i++)
    {
        crc = table[*data ^ (crc & 0xFF)] ^ (crc >> 8);
        data++;
    }
    crc = crc ^ 0xFFFFFFFFU;
    return crc;
}
}  // namespace crcdetail

// Macro to be used, guarantees hash is computed at compile time.
#define CRC32_STR(A)                                                           \
    std::integral_constant<uint32_t, crcdetail::compute(A, sizeof(A)-1)>::value

#endif  // COMPILE_TIME_CRC_H

proof.cpp

// Based on discussions on https://gist.github.com/iwanders/8e1cb7b92af2ccf8d1a73450d771f483

// g++     : g++ proof.cpp -std=c++14 && ./a.out
// clang++ : clang++ proof.cpp -std=c++14 -stdlib=libc++ && ./a.out
// cl.exe  : cl.exe /std:c++14 proof.cpp && .\main.exe
#include "compile_time_crc.hpp"

// static_assert() performs compile-time assertion checking.
// https://en.cppreference.com/w/cpp/language/static_assert

static_assert(0x9e83486d == CRC32_STR("ab"), "CRC32_STR('ab')"); // Pass
// Uncommenting the following line will result in a compilation error as the static assert fails.
// static_assert(0x00000000 == CRC32_STR("ab"), "CRC32_STR('ab')"); // Fail (compile-time error)

// Another proof is the following two lines.
static constexpr char data[] = {'a', 'b', 0};
constexpr auto CRC32_ab = CRC32_STR(data);
// The symbol for CRC32_ab in the binary will contain 4 bytes holding its CRC: 0x9e83486d.
// They may be reversed in the binary due to endianness and read like 6d, 48, 83, 9e.

// Just a dummy main to make the compiled binary runnable.
int main(int argc, char* argv[]) {
  return 0;
}

Compile-time hash function is not feasible for CRC32 due to its iterative nature over data.

@Mecanik , did you test this?

Make a file called test.cpp with the following content;

#include "compile_time_crc.hpp"
static constexpr char data[] = {'a', 'b', 0};
constexpr auto CRC32_abc = CRC32_STR(data);

Compile with

g++ -std=c++14 -c test.cpp

I used gcc 7.5, note that if this compiles, we already showed that it computed the value at compile time. It must be a compile time constant due the macro passing the value through std::integral_constant.

For further inspection; we can dump the data with objdump -D test.o, looking for the relevant section shows;

0000000000000404 <_ZL9CRC32_abc>:
 404:	6d                   	insl   (%dx),%es:(%rdi)
 405:	48                   	rex.W
 406:	83                   	.byte 0x83
 407:	9e                   	sahf   

Those four bytes hold the global constant. So 9e83486d, which we could also print by modifying test.cpp to be:

#include "compile_time_crc.hpp"
#include "stdio.h"
static constexpr char data[] = {'a', 'b', 0};
constexpr auto CRC32_abc = CRC32_STR(data);
int main(int argc, char* argv[]){
  printf("%x", CRC32_abc);
  return 0;
}

Which indeed outputs 9e83486d.

Reproducing this value with Python requires dropping the 0 byte, because of this function actually calculates only the crc over sizeof(A)-1. The crcmod package is used:

#!/usr/bin/env python3
import crcmod.predefined
crc32_func = crcmod.predefined.mkCrcFun('crc-32')
print(hex(crc32_func(bytearray([ord('a'), ord('b')]))))

Which prints 0x9e83486d, showing that the Python implementation agrees with the value calculated by the C++ code at compile time.

The constexpr cppreference page includes an example that computes a factorial, above it is a comment stating:

// C++14 constexpr functions may use local variables and loops

So iteration is very much possible.

This file is also used in my scalopus tracing system, which has been used in production at my day job since I wrote it.

I'm fairly confident this file works as expected and is valid C++, I hope this clarifies to you that this does actually work.

Hi, thanks for the nice code.
Perhaps, providing static_assert() may help readers to understand what's happening here. For example:

// main.cpp
// g++     : g++ main.cpp -std=c++14 && ./a.out
// clang++ : clang++ main.cpp -std=c++14 -stdlib=libc++ && ./a.out
// cl.exe  : cl.exe /std:c++14 main.cpp && .\main.exe
#include "compile_time_crc.hpp"

// static_assert() performs compile-time assertion checking.
// https://en.cppreference.com/w/cpp/language/static_assert

  static_assert(0x9e83486d == CRC32_STR("ab"), "CRC32_STR('ab')"); // Pass
//static_assert(0x00000000 == CRC32_STR("ab"), "CRC32_STR('ab')"); // Fail (compile-time error)

int main() {} // do nothing

@t-mat , thanks for the suggestion!

I've pushed a revision that includes proof.cpp with the static asserts you proposed, as well as two lines that create a symbol that holds the result. I realise only now that the output of objdump -D test.o of my original reply wasn't the most readable as you have to look at the bytes and not the disassembly, your static assert suggestion is much better.