CRC16.hh

Go to the documentation of this file.

#ifndef CRC16_HH
#define CRC16_HH
 
#include "narrow.hh"
#include "xrange.hh"
#include <array>
#include <cstddef>
#include <cstdint>
#include <initializer_list>
#include <span>
 
namespace openmsx {
 
class CRC16
{
public:
        explicit constexpr CRC16(uint16_t initialCRC = 0xffff)
                : crc(initialCRC)
        {
        }
 
        constexpr void init(uint16_t initialCRC)
        {
                crc = initialCRC;
        }
 
        constexpr void init(std::initializer_list<uint8_t> list)
        {
                crc = 0xffff;
                for (const auto& val : list) {
                        update(val);
                }
        }
 
        constexpr void update(uint8_t value)
        {
                // Classical byte-at-a-time algorithm by Dilip V. Sarwate
                crc = uint16_t((crc << 8) ^ tab[0][(crc >> 8) ^ value]);
        }
 
        constexpr void update(std::span<const uint8_t> data)
        {
                // Based on:
                //   Slicing-by-4 and slicing-by-8 algorithms by Michael E.
                //   Kounavis and Frank L. Berry from Intel Corp.
                //   http://www.intel.com/technology/comms/perfnet/download/CRC_generators.pdf
                // and the implementation by Peter Kankowski found on:
                //   http://www.strchr.com/crc32_popcnt
                // I transformed the code from CRC32 to CRC16 (this was not
                // trivial because both CRCs use a different convention about
                // bit order). I also made the code work on bigendian hosts.
 
                unsigned c = crc; // 32-bit are faster than 16-bit calculations
                                  // on x86 and many other modern architectures
                // calculate the bulk of the data 8 bytes at a time
                while (data.size() >= 8) {
                        c = tab[7][data[0] ^ (c >>  8)] ^
                            tab[6][data[1] ^ (c & 255)] ^
                            tab[5][data[2]] ^
                            tab[4][data[3]] ^
                            tab[3][data[4]] ^
                            tab[2][data[5]] ^
                            tab[1][data[6]] ^
                            tab[0][data[7]];
                        data = data.subspan(8);
                }
                // calculate the remaining bytes in the usual way
                for (auto d : data) {
                        c = uint16_t(c << 8) ^ tab[0][(c >> 8) ^ d];
                }
                crc = uint16_t(c); // store back in a 16-bit result
        }
 
        [[nodiscard]] constexpr uint16_t getValue() const
        {
                return crc;
        }
 
private:
        static inline constexpr auto tab = [] {
                std::array<std::array<uint16_t, 0x100>, 8> result = {}; // uint16_t[8][0x100]
                for (auto i : xrange(0x100)) {
                        auto x = uint16_t(i << 8);
                        repeat(8, [&] {
                                x = narrow_cast<uint16_t>((x << 1) ^ ((x & 0x8000) ? 0x1021 : 0));
                        });
                        result[0][i] = x;
                }
                for (auto i : xrange(0x100)) {
                        uint16_t c = result[0][i];
                        for (auto j : xrange(1, 8)) {
                                c = narrow_cast<uint16_t>(result[0][c >> 8] ^ (c << 8));
                                result[j][i] = c;
                        }
                }
                return result;
        }();
 
        uint16_t crc;
};
 
} // namespace openmsx
 
#endif