Program Listing for File crc32.h

↰ Return to documentation for file (liberate/checksum/crc32.h)

/*
 * This file is part of liberate.
 *
 * Author(s): Jens Finkhaeuser <jens@finkhaeuser.de>
 *
 * Copyright (c) 2021 Jens Finkhaeuser.
 * Copyright (c) 2022 Interpeer gUG (haftungsbeschränkt)
 *
 * SPDX-License-Identifier: GPL-3.0-only
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */
#ifndef LIBERATE_CHECKSUM_CRC32_H
#define LIBERATE_CHECKSUM_CRC32_H

#ifndef __cplusplus
#error You are trying to include a C++ only header file
#endif

#include <liberate.h>

#include <numeric>
#include <array>

namespace liberate::checksum {

using crc32_checksum = std::uint_fast32_t;

using crc32_serialize = uint32_t; // For size estimation

constexpr crc32_checksum CRC32_MASK = ~crc32_checksum{0} & crc32_checksum{0xFFFFFFFFuL};

constexpr crc32_checksum CRC32_INITIALIZER = CRC32_MASK;

enum crc32_polynomials : crc32_checksum
{
  CRC32 = crc32_checksum{0xEDB88320uL},
  CRC32_ISO3309 = CRC32,
  CRC32_IEEE802_3 = CRC32,
  CRC32_GZIP = CRC32,
  CRC32_BZIP2 = CRC32,
  CRC32_POSIX = CRC32,

  CRC32C = crc32_checksum{0x82F63B78uL},
  CRC32_CASTAGNOLI = CRC32C,
  CRC32C_SCTP = CRC32C,
  CRC32C_SSE42 = CRC32C,

  CRC32K = crc32_checksum{0xEB31D82EuL},
  CRC32_KOOPMAN = CRC32K,

  CRC32K2 = crc32_checksum{0x992C1A4CuL},
  CRC32_KOOPMAN2 = CRC32K,

  CRC32Q = crc32_checksum{0xD5828281uL},
  CRC32_AIXM = CRC32Q,
};

namespace {

template <
  crc32_checksum POLYNOMIAL,
  size_t table_size = 256
>
struct crc32_table_generator
{
private:
  // Calculate iteration value based on current value and LSB.
  template <crc32_checksum VAL, bool flag>
  struct iter_value;

  template <crc32_checksum VAL>
  struct iter_value<VAL, true>
  {
    static constexpr crc32_checksum value = (VAL >> 1) ^ POLYNOMIAL;
  };

  template <crc32_checksum VAL>
  struct iter_value<VAL, false>
  {
    static constexpr crc32_checksum value = (VAL >> 1);
  };

  // Calculation for table elements; index is the table index, N is the
  // iteration value.
  template <uint8_t index, uint8_t N = 0>
  struct table_element
  {
    static constexpr bool lsb =
      static_cast<bool>(
          table_element<index, N + 1>::value & 0x01u
      );

    static constexpr crc32_checksum value = iter_value<
      table_element<index, N + 1>::value,
      lsb
    >::value;
  };

  template <uint8_t index>
  struct table_element<index, 7>
  {
    static constexpr bool lsb =
      static_cast<bool>(
          index & 0x01u
      );

    static constexpr crc32_checksum value = iter_value<
      index,
      lsb
    >::value;
  };

  // Calculation of table
  template <
    size_t N = table_size - 1,
    crc32_checksum ...Indices
  >
  struct table
  {
    static constexpr auto value = table<
      N - 1,
      table_element<N>::value,
      Indices...
    >::value;
  };

  template <
    crc32_checksum ...Indices
  >
  struct table<0, Indices...>
  {
    static constexpr std::array<crc32_checksum, sizeof...(Indices) + 1> value
      = {{ table_element<0>::value, Indices... }};
  };

public:

  // Final array calculation
  static constexpr std::array<crc32_checksum, table_size> value = table<>::value;
};



template <
  typename tableT,
  typename valueT
>
struct checksum_step
{
  static constexpr auto table = tableT::value;

  static crc32_checksum
  step(crc32_checksum checksum, valueT value)
  {
    return checksum_step<tableT, std::uint_fast8_t>::step(checksum,
        static_cast<std::uint_fast8_t>(value));
  }
};


template <
  typename tableT
>
struct checksum_step<tableT, std::uint_fast8_t>
{
  static constexpr auto table = tableT::value;

  static crc32_checksum
  step(crc32_checksum checksum, std::uint_fast8_t value)
  {
    return table[(checksum ^ value) & 0xFFu] ^ (checksum >> 8);
  }

};


} // anonymous namespace

template <
  crc32_checksum POLYNOMIAL,
  typename iterT
>
crc32_checksum
crc32(iterT begin, iterT end, crc32_checksum initial = CRC32_INITIALIZER)
{
  auto init = initial == CRC32_INITIALIZER
    ? initial
    : ~initial & CRC32_MASK;

  // Calculate checksum
  return CRC32_MASK &
    ~std::accumulate(begin, end, init,
        checksum_step<
          crc32_table_generator<POLYNOMIAL>,
          typename std::iterator_traits<iterT>::value_type
        >::step
    );
}

} // namespace liberate::checksum

#endif // guard