C++11/C++14: Generate CRC tables at compile time. With slices.

CrcTablesWithSlices.cpp

// Generate CRC tables at compile time. With slices.
// Based on http://create.stephan-brumme.com/crc32/#slicing-by-8-overview
//
// C++11, C++14 utility library, constexpr, variadic templates, initializer lists. 
//
// Tested using gcc-6.2, clang-3.9.0, and latest msvc 2015 compilers.
// clang: -std=c++14 -ftemplate-depth=512
//
// @twoscomplement 2016-09-26


#include <stdint.h>
#include <utility>


template<typename T, T Poly, int Slices>
struct Crc {
  
  // Generating the table
  constexpr Crc()
    : Crc(std::make_integer_sequence<int, Slices - 1>(), std::make_integer_sequence<T, 256>()) {}
  
  template<int ...Ss>
  constexpr Crc(std::integer_sequence<int, Ss...>, std::make_integer_sequence<T, 256> m)
    : m_Slice{ Slice(m), 
               Slice(m_Slice[0], m_Slice[Ss + 1 - 1], m)... } {}
  // Ss is (0 ... Slices - 2),
  // + 1 to translate to the index of the slice being generated (1 ... Slices - 1),
  // - 1 to reference the slice preceding the slice being generated.

  
  struct Slice {
    static constexpr T Gen0(T v, int r = 8) {
      return r ? Gen0((v >> 1) ^ (v & 1 ? Poly : 0), r - 1) : v;
    }
    
    static constexpr T GenN(T v, const Slice& s0, const Slice& sp) {
      return (sp[v] >> 8) ^ (s0[sp[v] & 0xff]); 
    }
    
    // Constructor for slice 0
    template<T ...Is>
    constexpr Slice(std::integer_sequence<T, Is...>)
      : m_V{ Gen0(Is)... } 
    {}
    
    // Constructor for all other slices, referencing slice 0 (s0) and the previous slice (sp)
    template<T ...Is>
    constexpr Slice(const Slice& s0, const Slice& sp, std::integer_sequence<T, Is...>)
      : m_V{ GenN(Is, s0, sp)... }
    {}
    
    constexpr T operator[](T i) const { return m_V[i]; }
    
    T m_V[256];
  };
  
  constexpr const Slice& operator[](int i) const { return m_Slice[i]; }

  Slice m_Slice[Slices];
};


constexpr Crc<uint32_t, 0xEDB88320, 16> kCrc32;
constexpr Crc<uint64_t, 0xC96C5795D7870F42, 16> kCrc64;

// Validate a somewhat random entry in the generated slices
static_assert(kCrc32[14][3] == 0x117d6a79, "nope");