GNU Radio's DVBS2RX Package
gf_util.h
Go to the documentation of this file.
1/* -*- c++ -*- */
2/*
3 * Copyright (c) 2023 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_GF_UTIL_H
11#define INCLUDED_DVBS2RX_GF_UTIL_H
12
13#include "gf.h"
14#include <array>
15#include <stdexcept>
16#include <vector>
17
18
19namespace gr {
20namespace dvbs2rx {
21
22typedef std::vector<unsigned char> u8_vector_t;
23typedef unsigned char* u8_ptr_t; // Pointer to modifiable u8 buffer
24typedef const unsigned char* u8_cptr_t; // Pointer to constant u8 buffer
25
26/**
27 * @brief Get bitmask for the least significant bits of a type T
28 *
29 * @param n_bits Number of bits over which the mask is high.
30 * @return T Bitmask.
31 */
32template <typename T>
33inline T bitmask(int n_bits)
34{
35 return (static_cast<T>(1) << n_bits) - 1;
36}
37
38/**
39 * @overload
40 * @note Template specialization for T = bitset256_t.
41 */
42template <>
43inline bitset256_t bitmask(int n_bits)
44{
45 bitset256_t mask;
46 for (int i = 0; i < n_bits; i++)
47 mask.set(i);
48 return mask;
49}
50
51/**
52 * @brief Get the byte at a given index of a type T value.
53 *
54 * @tparam T Value type.
55 * @param value Value.
56 * @param byte_index Target byte index.
57 * @return uint8_t Extracted byte value.
58 */
59template <typename T>
60inline uint8_t get_byte(const T& value, uint32_t byte_index)
61{
62 return (value >> (byte_index * 8)) & 0xFF;
63}
64
65/**
66 * @overload
67 * @note Template specialization for T = bitset256_t.
68 */
69template <>
70inline uint8_t get_byte(const bitset256_t& value, uint32_t byte_index)
71{
72 uint8_t byte = 0;
73 for (uint32_t i = byte_index * 8; i < (byte_index + 1) * 8; i++)
74 byte |= value[i] << (i - byte_index * 8);
75 return byte;
76}
77
78/**
79 * @brief Get the most significant byte of a given value.
80 *
81 * @tparam T Value type.
82 * @param value Value.
83 * @param lsb_index Index of the least significant bit of the most significant byte,
84 * equivalent to the number of bits to be shifted to the right.
85 * @return uint8_t Extracted byte value.
86 * @note This function differs from get_byte in that it assumes the given value has zeros
87 * in the other byte positions (if any) within the container type T beyond the byte of
88 * interest. In other words, this function does not apply a mask (AND 0xFF) to the result.
89 */
90template <typename T>
91inline uint8_t get_msby(const T& value, uint32_t lsb_index)
92{
93 return value >> lsb_index;
94}
95
96/**
97 * @overload
98 * @note Template specialization for T = bitset256_t.
99 */
100template <>
101inline uint8_t get_msby(const bitset256_t& value, uint32_t lsb_index)
102{
103 uint8_t byte = 0;
104 for (uint32_t i = lsb_index; i < (lsb_index + 8); i++)
105 byte |= value[i] << (i - lsb_index);
106 return byte;
107}
108
109/**
110 * @brief Convert type to u8 vector in network byte order (big-endian)
111 *
112 * @tparam T Bit storage type.
113 * @param val Value to be converted.
114 * @param n_bytes Number of least significant bytes to be converted. E.g., n_bytes=3
115 * converts the three least significant bytes of val into a vector in network order.
116 * @return u8_vector_t Resulting u8 vector.
117 */
118template <typename T>
119inline u8_vector_t to_u8_vector(T val, size_t n_bytes = sizeof(T))
120{
121 if (n_bytes > sizeof(T))
122 throw std::invalid_argument("n_bytes too large for type T");
123 u8_vector_t vec;
124 for (int i = n_bytes - 1; i >= 0; i--) {
125 vec.push_back(get_byte(val, i));
126 }
127 return vec;
128}
129
130/**
131 * @brief Convert u8 array in network byte order (big-endian) to type
132 *
133 * @tparam T Bit storage type.
134 * @param in u8 array to be converted.
135 * @param size Number of bytes to be converted.
136 * @return T Resulting value.
137 */
138template <typename T>
139inline T from_u8_array(u8_cptr_t in, size_t size)
140{
141 if (size > sizeof(T))
142 throw std::invalid_argument("u8 array too large for type T");
143 T val = 0;
144 for (size_t i = 0; i < size; i++) {
145 val |= static_cast<T>(in[i]) << ((size - 1 - i) * 8);
146 }
147 return val;
148}
149
150/**
151 * @brief Convert u8 vector in network byte order (big-endian) to type
152 *
153 * @tparam T Bit storage type.
154 * @param vec u8 vector to be converted.
155 * @return T Resulting value.
156 */
157template <typename T>
158inline T from_u8_vector(const u8_vector_t& vec)
159{
160 return from_u8_array<T>(vec.data(), vec.size());
161}
162
163/**
164 * @brief Build LUT to assist with GF(2) polynomial remainder computation
165 *
166 * The resulting LUT can be used to compute "y % x" more efficiently for any "y" and a
167 * given "x". More specifically, it maps each possible input byte representative of a
168 * dividend polynomial y to the bits that would leak into the succeeding bytes within the
169 * remainder computation. In the end, the LUT allows for computing the remainder with one
170 * iteration per byte instead of one interation per bit.
171 *
172 * @tparam T Type whose bits represent the binary polynomial coefficients.
173 * @param x Divisor polynomial.
174 * @note The divisor should have degree less than or equal to "(sizeof(T) - 1) * 8".
175 * @return std::array<T, 256> Byte-by-byte remainder look-up table.
176 */
177template <typename T>
178std::array<T, 256> build_gf2_poly_rem_lut(const gf2_poly<T>& x)
179{
180 // As the divisor x is bit-shifted and XORed over the bits of an input byte, the
181 // result leaks over at least x.degree() bits following the given byte. More
182 // generally, the division of an input byte by x leaks over as many succeeding bytes
183 // as we want to compute in advance, but the result always occupies the last
184 // x.degree() bits within the designated leak space. For instance, suppose the divisor
185 // is x = x^8 + x^3 + 1 (i.e., x = 0x109). If we wanted to compute 4 leak bytes in
186 // advance for an input byte equal to 1, we would compute 0x100000000 % 0x109, which
187 // results in 0x0000009A, with the non-zero part occupying the 8 least significant
188 // bits of the 4 leak bytes. In contrast, if we wanted 2 leak bytes, we would compute
189 // 0x10000 % 0x109, which yields 0x0041, again occupying the 8 least significant bits.
190 // Here, compute the maximum number of leak bytes that type T can hold, assuming one
191 // byte of T is already used to store the input byte (the dividend).
192 const unsigned int n_leak_bytes = sizeof(T) - 1;
193
194 // But make sure the leak space is enough to hold the remainder of division by x. Note
195 // this verification implies the maximum acceptable degree of x is "n_leak_bytes * 8".
196 if (x.degree() > static_cast<int>(n_leak_bytes) * 8)
197 throw std::runtime_error("Failed to compute remainder LUT. Type T is too small.");
198
199 std::array<T, 256> table;
200 for (int i = 0; i < 256; i++) {
201 T padded_in_byte = static_cast<T>(i) << (n_leak_bytes * 8);
202 gf2_poly<T> y(padded_in_byte);
203 table[i] = (y % x).get_poly();
204 }
205 return table;
206}
207
208/**
209 * @brief Compute the remainder "y % x" of GF2 polynomials y and x using a LUT
210 *
211 * @tparam T Type whose bits represent the binary polynomial coefficients.
212 * @param y Dividend GF(2) polynomial given by an array of bytes in network byte order
213 * (big-endian), i.e., with the most significant byte at index 0.
214 * @param y_size Size of the dividend polynomial y in bytes.
215 * @param x Divisor GF(2) polynomial.
216 * @param x_lut LUT generated by the `build_gf2_poly_rem_lut` function for polynomial x.
217 * @return gf2_poly<T> Resulting remainder.
218 */
219template <typename T>
221 const int y_size,
222 const gf2_poly<T>& x,
223 const std::array<T, 256>& x_lut)
224{
225 static constexpr int n_leak_bytes = sizeof(T) - 1; // see build_gf2_poly_rem_lut
226 static constexpr uint32_t bytes_after_msby = n_leak_bytes - 1;
227 static constexpr uint32_t bits_after_msby = bytes_after_msby * 8;
228 const T leak_mask = bitmask<T>(n_leak_bytes * 8);
229
230 // Over the first "y_size - n_leak_bytes" bytes, iteratively look up the leak that the
231 // input byte introduces into the next n_leak_bytes bytes.
232 T leak = 0;
233 for (int i = 0; i < y_size - n_leak_bytes; i++) {
234 // Incorporate the preceding leak into the input byte. The leak spans over
235 // n_leak_bytes of the type-T word, and the resulting most significant byte (MSBy)
236 // determines the next leak. The other bytes (other than the MSBy) from the
237 // preceding leak continue to leak (are carried forward) over the next bytes.
238 uint8_t in_byte_plus_leak = y[i] ^ get_msby(leak, bits_after_msby);
239 T leak_carried_forward = (leak_mask & (leak << 8));
240 leak = leak_carried_forward ^ x_lut[in_byte_plus_leak];
241 }
242
243 // Convert the last n_leak_bytes of the input vector into a word of type T.
244 //
245 // In doing so, note that:
246 // - We assume the order of bytes on the input u8_vector y is the order in which they
247 // arrive on serialization, i.e., y[0] arrives first and y[size-1] arrives last.
248 // Also, we could assume y carries a word in network byte order (big-endian), with
249 // y[0] representing the most significant byte and y[size-1] the least.
250 // - The last n_leak_bytes are converted into a word of type T in network byte order,
251 // For instance, with T = uint32_t, an input vector {0x0A, 0x0B, 0x0C, 0x0D} would
252 // be converted into an unsigned int equal to 0x0A0B0C0D.
253 // - The last n_leak_bytes are guaranteed to fit in T, otherwise
254 // build_gf2_poly_rem_lut would have thrown an exception.
255 unsigned int n_last_bytes = std::min(n_leak_bytes, y_size);
256 T y_last_bytes = from_u8_array<T>(y + y_size - n_last_bytes, n_last_bytes);
257
258 // Incorporate the leak from the preceding bytes, if any
259 y_last_bytes ^= leak;
260
261 return gf2_poly<T>(y_last_bytes) % x;
262}
263
264/**
265 * @overload
266 * @param y Dividend GF(2) polynomial given by a vector of bytes in network byte order.
267 * @param x Divisor GF(2) polynomial.
268 * @param x_lut LUT generated by the `build_gf2_poly_rem_lut` function for polynomial x.
269 */
270template <typename T>
271gf2_poly<T>
272gf2_poly_rem(const u8_vector_t& y, const gf2_poly<T>& x, const std::array<T, 256>& x_lut)
273{
274 return gf2_poly_rem(y.data(), y.size(), x, x_lut);
275}
276
277} // namespace dvbs2rx
278} // namespace gr
279
280#endif // INCLUDED_DVBS2RX_GF_UTIL_H
Polynomial over GF(2).
Definition gf.h:203
int degree() const
Get the polynomial degree.
Definition gf.h:267
unsigned char * u8_ptr_t
Definition gf_util.h:23
std::array< T, 256 > build_gf2_poly_rem_lut(const gf2_poly< T > &x)
Build LUT to assist with GF(2) polynomial remainder computation.
Definition gf_util.h:178
T from_u8_vector(const u8_vector_t &vec)
Convert u8 vector in network byte order (big-endian) to type.
Definition gf_util.h:158
std::vector< unsigned char > u8_vector_t
Definition gf_util.h:22
uint8_t get_msby(const T &value, uint32_t lsb_index)
Get the most significant byte of a given value.
Definition gf_util.h:91
const unsigned char * u8_cptr_t
Definition gf_util.h:24
T bitmask(int n_bits)
Get bitmask for the least significant bits of a type T.
Definition gf_util.h:33
T from_u8_array(u8_cptr_t in, size_t size)
Convert u8 array in network byte order (big-endian) to type.
Definition gf_util.h:139
u8_vector_t to_u8_vector(T val, size_t n_bytes=sizeof(T))
Convert type to u8 vector in network byte order (big-endian)
Definition gf_util.h:119
gf2_poly< T > gf2_poly_rem(u8_cptr_t y, const int y_size, const gf2_poly< T > &x, const std::array< T, 256 > &x_lut)
Compute the remainder "y % x" of GF2 polynomials y and x using a LUT.
Definition gf_util.h:220
std::bitset< 256 > bitset256_t
Definition gf.h:26
uint8_t get_byte(const T &value, uint32_t byte_index)
Get the byte at a given index of a type T value.
Definition gf_util.h:60
Fixed-length double-ended queue with contiguous volk-aligned elements.
Definition gr_bch.h:22