.. _program_listing_file_liberate_checksum_crc32.h:

Program Listing for File crc32.h
================================

|exhale_lsh| :ref:`Return to documentation for file <file_liberate_checksum_crc32.h>` (``liberate/checksum/crc32.h``)

.. |exhale_lsh| unicode:: U+021B0 .. UPWARDS ARROW WITH TIP LEFTWARDS

.. code-block:: cpp

   /*
    * 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