GNU Radio's DVBS2RX Package
crc.h
Go to the documentation of this file.
1/* -*- c++ -*- */
2/*
3 * Copyright (c) 2022 Igor Freire.
4 *
5 * This file is part of gr-dvbs2rx.
6 *
7 * SPDX-License-Identifier: GPL-3.0-or-later
8 */
9
10#ifndef INCLUDED_DVBS2RX_CRC_H
11#define INCLUDED_DVBS2RX_CRC_H
12
13#include <array>
14#include <cstdint>
15#include <vector>
16
17namespace gr {
18namespace dvbs2rx {
19
20#define BITS_AFTER_MSB(T) ((sizeof(T) - 1) * 8) // bits after the most significant byte
21#define MSB_MASK(T) \
22 (static_cast<T>(1) << (sizeof(T) * 8 - 1)) // mask to check the most significant bit
23
24/**
25 * @brief Build the CRC computation look-up table (LUT)
26 *
27 * @tparam T CRC data type.
28 * @param gen_poly_no_msb Generator polynomial in normal representation but excluding the
29 * MSB. For instance, x^4 + x + 1 would be given as 0b11.
30 * @return std::array<T, 256> Byte-by-byte CRC look-up table.
31 * @note This implementation only works for generator polynomials with degrees multiple of
32 * 8, e.g., for CRC8, CRC16, CRC32, etc.
33 */
34template <typename T>
35std::array<T, 256> build_crc_lut(const T& gen_poly_no_msb)
36{
37 // See http://www.sunshine2k.de/articles/coding/crc/understanding_crc.html
38 std::array<T, 256> table;
39 for (int dividend = 0; dividend < 256; dividend++) {
40 T shift_reg = static_cast<T>(dividend)
41 << BITS_AFTER_MSB(T); // dividend byte on the MSB
42 for (unsigned char bit = 0; bit < 8; bit++) {
43 if (shift_reg & MSB_MASK(T)) {
44 shift_reg = (shift_reg << 1) ^ gen_poly_no_msb;
45 } else {
46 shift_reg <<= 1;
47 }
48 }
49 table[dividend] = shift_reg;
50 }
51 return table;
52};
53
54/**
55 * @brief Compute the CRC of a sequence of input bytes.
56 *
57 * @tparam T CRC data type.
58 * @param in_bytes Vector of input bytes.
59 * @param crc_lut Look-up table constructed with the build_crc_lut function.
60 * @return T CRC value (checksum), the remainder of the division by the generator
61 * polynomial.
62 */
63template <typename T>
64T calc_crc(const std::vector<uint8_t>& in_bytes, const std::array<T, 256>& crc_lut)
65{
66 T crc = 0;
67 for (const uint8_t& in_byte : in_bytes) {
68 // Even if T is larger than a single byte, the dividend used for table look-up is
69 // always a single byte, more specifically, the MSB of the CRC register. Also, on
70 // each iteration, the looked-up dividend is the input byte XORed with whatever
71 // leaked from the previous iteration into the MSB of the CRC register. The bits
72 // leaking into the other bytes (past the MSB) are not taken into account for the
73 // table look-up, but they must be added (mod-2) back in the end.
74 T padded_in_byte = static_cast<T>(in_byte) << BITS_AFTER_MSB(T);
75 uint8_t dividend = (crc ^ padded_in_byte) >> BITS_AFTER_MSB(T);
76 // The table look-up returns the remainder that would result if the dividend byte
77 // padded with BITS_AFTER_MSB was divided by the generator polynomial. This
78 // remainder leaks into the succeeding input bytes. Also, the non-MSB bytes of the
79 // previous iteration's remainder continue to leak over future input bytes. For
80 // example, with a CRC-16, each remainder has 2 bytes, one affecting the current
81 // input byte (XORed into the dividend) and the other affecting the next byte.
82 // Hence, the non-MSB bytes of the previous remainder must be added back mod-2.
83 crc = (crc << 8) ^ crc_lut[dividend];
84 }
85 return crc;
86};
87
88} // namespace dvbs2rx
89} // namespace gr
90
91#endif
#define MSB_MASK(T)
Definition crc.h:21
#define BITS_AFTER_MSB(T)
Definition crc.h:20
std::array< T, 256 > build_crc_lut(const T &gen_poly_no_msb)
Build the CRC computation look-up table (LUT)
Definition crc.h:35
T calc_crc(const std::vector< uint8_t > &in_bytes, const std::array< T, 256 > &crc_lut)
Compute the CRC of a sequence of input bytes.
Definition crc.h:64
Fixed-length double-ended queue with contiguous volk-aligned elements.
Definition gr_bch.h:22