Prison

reedsolomon.cpp
1/*
2 SPDX-FileCopyrightText: 2017 Volker Krause <vkrause@kde.org>
3
4 SPDX-License-Identifier: MIT
5*/
6
7#include "bitvector_p.h"
8#include "reedsolomon_p.h"
9
10
11#include <memory>
12
13using namespace Prison;
14
15// See https://en.wikiversity.org/wiki/Reed%E2%80%93Solomon_codes_for_coders
16
17static int highestBit(int n)
18{
19 int i = 0;
20 while (n >= (1 << i)) {
21 ++i;
22 }
23 return i - 1;
24}
25
26ReedSolomon::ReedSolomon(int polynom, int symbolCount)
27 : m_symCount(symbolCount)
28{
29 m_symSize = highestBit(polynom);
30
31 // calculate the log/alog tables
32 const auto logmod = (1 << m_symSize) - 1;
33 m_logTable.reset(new int[logmod + 1]);
34 m_antiLogTable.reset(new int[logmod]);
35
36 for (int p = 1, v = 0; v < logmod; v++) {
37 m_antiLogTable[v] = p;
38 m_logTable[p] = v;
39 p <<= 1;
40 if (p & (1 << m_symSize)) {
41 p ^= polynom;
42 }
43 }
44
45 // compute the encoding polynom
46 m_polynom.reset(new int[m_symCount + 1]);
47 m_polynom[0] = 1;
48 for (int i = 1; i <= m_symCount; ++i) {
49 m_polynom[i] = 1;
50 for (int k = i - 1; k > 0; --k) {
51 if (m_polynom[k]) {
52 m_polynom[k] = m_antiLogTable[(m_logTable[m_polynom[k]] + i) % logmod];
53 }
54 m_polynom[k] ^= m_polynom[k - 1];
55 }
56 m_polynom[0] = m_antiLogTable[(m_logTable[m_polynom[0]] + i) % logmod];
57 }
58}
59
60ReedSolomon::~ReedSolomon() = default;
61
62BitVector ReedSolomon::encode(const BitVector &input) const
63{
64 std::unique_ptr<int[]> result(new int[m_symCount]);
65 for (int i = 0; i < m_symCount; ++i) {
66 result[i] = 0;
67 }
68
69 const auto logmod = (1 << m_symSize) - 1;
70 for (int i = 0; i < input.size() / m_symSize; i++) {
71 auto m = result[m_symCount - 1] ^ input.valueAtMSB(i * m_symSize, m_symSize);
72 for (int k = m_symCount - 1; k > 0; --k) {
73 if (m && m_polynom[k]) {
74 result[k] = result[k - 1] ^ m_antiLogTable[(m_logTable[m] + m_logTable[m_polynom[k]]) % logmod];
75 } else {
76 result[k] = result[k - 1];
77 }
78 }
79 if (m && m_polynom[0]) {
80 result[0] = m_antiLogTable[(m_logTable[m] + m_logTable[m_polynom[0]]) % logmod];
81 } else {
82 result[0] = 0;
83 }
84 }
85
86 BitVector v;
87 for (int i = m_symCount - 1; i >= 0; --i) {
88 v.appendMSB(result[i], m_symSize);
89 }
90 return v;
91}
Provides classes and methods for generating barcodes.
Definition barcode.h:24
This file is part of the KDE documentation.
Documentation copyright © 1996-2024 The KDE developers.
Generated on Tue Mar 26 2024 11:16:07 by doxygen 1.10.0 written by Dimitri van Heesch, © 1997-2006

KDE's Doxygen guidelines are available online.