crc.hpp

Go to the documentation of this file.

/* SPDX-License-Identifier: Apache-2.0 */
/* Copyright 2015-2019 Peter A. Bigot */
 
#ifndef PABIGOT_CRC_HPP
#define PABIGOT_CRC_HPP
#pragma once
 
#include <array>
#include <cstdint>
#include <limits>
#include <tuple>
#include <type_traits>
#include <utility>
 
#include <pabigot/byteorder.hpp>
 
namespace pabigot {
 
namespace crc {
 
namespace details {
 
template <typename UI>
static constexpr UI
reverse_low_bits (const UI& v,
                  unsigned int bits)
{
  UI msb = (static_cast<UI>(1) << (bits - 1));
  UI lsb = 1;
  UI out = 0;
 
  /* msb right-shifts; when it becomes zero we're done. */
  while (msb) {
    if (msb & v) {
      out |= lsb;
    }
    msb >>= 1;
    lsb <<= 1;
  }
  return out;
}
 
template <unsigned int B>
constexpr unsigned int uint_category ()
{
  return (B<=8) + (B<=16) + (B<=32) + (B<=64);
}
 
template <unsigned int C>
struct uint_size_traits
{ };
 
template <>
struct uint_size_traits<4>
{
  static constexpr unsigned int width = 8;
  using fast_type = uint_fast8_t;
  using least_type = uint_least8_t;
};
 
template <>
struct uint_size_traits<3>
{
  static constexpr unsigned int width = 16;
  using fast_type = uint_fast16_t;
  using least_type = uint_least16_t;
};
 
template <>
struct uint_size_traits<2>
{
  static constexpr unsigned int width = 32;
  using fast_type = uint_fast32_t;
  using least_type = uint_least32_t;
};
 
template <>
struct uint_size_traits<1>
{
  static constexpr unsigned int width = 64;
  using fast_type = uint_fast64_t;
  using least_type = uint_least64_t;
};
 
template <unsigned int C>
struct uint_traits : public uint_size_traits<C>
{
  using super = uint_size_traits<C>;
  using typename super::fast_type;
  using typename super::least_type;
  using fast_limits = std::numeric_limits<fast_type>;
 
  static constexpr fast_type
  reverse (const fast_type& v,
           unsigned int bits)
  {
    return reverse_low_bits<fast_type>(v, bits);
  }
 
  static constexpr fast_type
  mask_for_bits (unsigned int bits)
  {
    return ((bits == fast_limits::digits)
            ? static_cast<fast_type>(-1)
            : ((static_cast<fast_type>(1) << bits) - 1));
  }
 
};
 
using uint8_traits = uint_traits<4>;
using uint16_traits = uint_traits<3>;
using uint32_traits = uint_traits<2>;
using uint64_traits = uint_traits<1>;
 
template <unsigned int B>
struct uint_support
{
  static constexpr unsigned int width = B;
 
  using uint_traits = details::uint_traits<uint_category<B>()>;
 
  using fast_type = typename uint_traits::fast_type;
 
  using least_type = typename uint_traits::least_type;
 
  static constexpr unsigned int fast_width = std::numeric_limits<fast_type>::digits;
 
  static constexpr unsigned int least_width = std::numeric_limits<least_type>::digits;
 
  static constexpr fast_type mask{uint_traits::mask_for_bits(width)};
 
  static constexpr fast_type msbit{static_cast<fast_type>(1) << (width - 1)};
 
  static constexpr fast_type lsbit{static_cast<fast_type>(1)};
 
  static constexpr fast_type
  reflect (const fast_type& v,
           unsigned int n = width)
  {
    return uint_traits::reverse(v, n);
  }
 
  static constexpr fast_type
  crc_apply (const fast_type& poly,
             const fast_type& crc,
             const fast_type& msg,
             const unsigned int n)
  {
    auto rv = crc;
    rv ^= msg << (width - n);
    for (unsigned int bi{}; bi < n; ++bi) {
      bool xor_poly{msbit & rv};
      rv <<= 1;
      if (xor_poly) {
        rv ^= poly;
      }
    }
    return mask & rv;
  }
};
 
template <typename CRC,
         size_t... n>
constexpr auto lookup_table (std::index_sequence<n...>)
{
  using least_type = typename CRC::least_type;
  return std::array<least_type, sizeof...(n)>{{CRC::lookup_for_byte(n)...}};
}
 
template <typename CRC>
constexpr auto lookup_table()
{
  return lookup_table<CRC>(std::make_integer_sequence<size_t, 256>{});
}
 
template <unsigned int W,
          bool Rin = false>
class base_crc
{
public:
  static constexpr unsigned int width = W;
 
  static constexpr unsigned int size = (7 + width) / 8;
 
protected:
  using support_traits = details::uint_support<width>;
 
public:
  using uint_traits = typename support_traits::uint_traits;
 
  using fast_type = typename support_traits::fast_type;
 
  using least_type = typename support_traits::least_type;
 
  static constexpr fast_type mask = support_traits::mask;
 
  static constexpr bool refin = Rin;
 
  static constexpr fast_type
  reflect (const fast_type& v)
  {
    return support_traits::reflect(v, width);
  }
 
  static constexpr uint8_t*
  store (fast_type crc,
         uint8_t* bp)
  {
    auto nb = size;
    while (nb--) {
      if (refin) {
        *bp++ = crc;
        crc >>= 8;
      } else {
        *bp++ = crc >> (8 * nb);
      }
    }
    return bp;
  }
 
protected:
 
  static constexpr least_type
  lookup_for_byte (const fast_type& poly,
                   std::uint_fast8_t byte)
  {
    if (refin) {
      byte = support_traits::reflect(byte, 8);
    }
 
    auto rv = crc_apply(poly, 0, byte, 8);
    /* Assume the common case that refin==refout.  For cross-endian we need to
     * correct this during finalize. */
    if (refin) {
      rv = reflect(rv);
    }
    return mask & rv;
  }
 
  static constexpr fast_type
  crc_apply (const fast_type& poly,
             const fast_type& crc,
             fast_type msg,
             unsigned int n)
  {
    auto rv = crc;
    while (n > width) {
      fast_type submsg = msg >> (n - width);
      rv = support_traits::crc_apply(poly, rv, submsg, width);
      n -= width;
    }
    return support_traits::crc_apply(poly, rv, msg, n);
  }
};
 
} // ns details
 
template <typename CRC>
class Tabler : public CRC::uint_traits
{
  using super_ = typename CRC::uint_traits;
 
public:
  using crc_type = CRC;
 
  using typename super_::fast_type;
 
  using typename super_::least_type;
 
  using table_type = std::array<least_type, 256>;
 
  struct params {
    static constexpr unsigned int width = CRC::width;
    static constexpr least_type poly = CRC::poly;
    static constexpr least_type init = CRC::init;
    static constexpr least_type xorout = CRC::xorout;
    static constexpr bool refin = CRC::refin;
    static constexpr bool refout = CRC::refout;
  };
 
  static constexpr size_t size = CRC::size;
 
private:
 
  static constexpr fast_type
  make_init ()
  {
    fast_type crc = CRC::init;
 
    /* The table incorporates the effects of input reflection, but for that to
     * work the initial value needs to be reflected. */
    if (CRC::refin) {
      crc = super_::reverse(crc, CRC::width);
    }
    return crc;
  }
 
  // CRC is the only thing allowed to construct these.  Nobody can copy them.
  friend CRC;
 
  constexpr Tabler () :
    table{details::lookup_table<CRC>()}
  { }
 
  Tabler (const Tabler&) = delete;
  Tabler& operator= (const Tabler&) = delete;
  Tabler (const Tabler&&) = delete;
  Tabler& operator= (const Tabler&&) = delete;
 
public:
 
  uint8_t*
  store (least_type crc,
         uint8_t* bp) const
  {
    size_t nb{size};
    while (nb--) {
      if (CRC::refin) {
        *bp++ = crc;
        crc >>= 8;
      } else {
        *bp++ = crc >> (8 * nb);
      }
    }
    return bp;
  }
 
  constexpr fast_type
  append (uint8_t octet,
          fast_type crc = init) const
  {
    constexpr fast_type index_mask = 0xFFu;
    if (CRC::refin) {
      crc = table[(crc ^ octet) & index_mask] ^ (crc >> 8);
    } else {
      crc = table[((crc >> (CRC::width - 8)) ^ octet) & index_mask] ^ (crc << 8);
    }
    return CRC::mask & crc;
  }
 
  template <typename InputIterator>
  constexpr fast_type
  append (InputIterator first,
          InputIterator last,
          fast_type crc = init) const
  {
    using src_type = typename std::iterator_traits<InputIterator>::value_type;
    using limits = std::numeric_limits<src_type>;
 
    /* Unsigned 8-bit or signed 7-bit data passes this test */
    constexpr auto bits_per_chunk = limits::digits + (limits::is_signed ? 1U : 0U);
    static_assert(bits_per_chunk == 8,
                  "cannot do table-driven from non-octet source");
 
    auto rv = crc;
    while (last != first) {
      rv = append(static_cast<uint8_t>(*first), rv);
      ++first;
    }
    return rv;
  }
 
  constexpr least_type
  finalize (fast_type crc) const
  {
    crc ^= CRC::xorout;
 
    /* As long as the input and output endian match the result doesn't need
     * additional processing because the tables values are already reflected.
     * If they differ, then the output needs to be reflected. */
    if (CRC::refin ^ CRC::refout) {
      crc = super_::reverse(crc, CRC::width);
    }
    return static_cast<least_type>(crc);
  }
 
  static constexpr fast_type init = make_init();
 
  static constexpr least_type residue = CRC::residue();
 
  const table_type table;
};
 
template <unsigned int W,
          uintmax_t Poly,
          bool Rin = false,
          bool Rout = false,
          uintmax_t Init = 0,
          uintmax_t XorOut = 0>
class crc : public details::base_crc<W, Rin>
{
  using super_ = details::base_crc<W, Rin>;
  using this_type = crc<W, Poly, Rin, Rout, Init, XorOut>;
 
protected:
  using typename super_::support_traits;
 
public:
  using typename super_::fast_type;
  using typename super_::least_type;
 
  using tabler_type = Tabler<this_type>;
 
  static constexpr bool refout = Rout;
 
  static constexpr least_type residue ()
  {
    uint8_t buf[super_::size]{};
    store(finalize(init), buf);
    return finalize(append(buf, buf + sizeof(buf)));
  }
 
  using super_::store;
 
  static constexpr fast_type poly = super_::mask & Poly;
 
  static constexpr least_type init = super_::mask & Init;
 
  static constexpr least_type xorout = super_::mask & XorOut;
 
  template <typename InputIterator>
  static constexpr fast_type
  append (InputIterator first,
          InputIterator last,
          const fast_type& crc = init)
  {
    using src_type = typename std::iterator_traits<InputIterator>::value_type;
    constexpr auto bits_per_chunk =
      std::numeric_limits<src_type>::digits
      + (std::numeric_limits<src_type>::is_signed ? 1U : 0U);
    static_assert(bits_per_chunk <= support_traits::fast_width,
                  "cannot aggregate from source exceeding CRC operating type capacity");
    auto rv = crc;
    while (last != first) {
      /* Support signed values (viz. `signed char`) by first casting them to
       * the unsigned least type, so they can promote to the unsigned fast type
       * without violating narrowing rules. */
      fast_type chunk = static_cast<least_type>(*first);
      ++first;
      if (super_::refin) {
        chunk = support_traits::reflect(chunk, bits_per_chunk);
      }
      rv = super_::crc_apply(poly, rv, chunk, bits_per_chunk);
    }
    return rv;
  }
 
  static constexpr least_type
  lookup_for_byte (std::uint_fast8_t byte)
  {
    return super_::lookup_for_byte(poly, byte);
  }
 
  static constexpr least_type
  finalize (fast_type crc)
  {
    if (refout) {
      crc = super_::reflect(crc);
    }
    crc ^= xorout;
    return static_cast<least_type>(crc);
  }
 
  static constexpr tabler_type instantiate_tabler ()
  {
    return {};
  }
};
 
using CRC32 = crc<32, 0x04c11db7, true, true, -1, -1>;
 
} // ns crc
} // ns pabigot
 
#endif /* PABIGOT_CRC_HPP */