Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/thirdparty/zxing-cpp/core/src/ReedSolomonDecoder.cpp @ 2:b50eed0cc0ef upstream

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
ADD: MuPDF v1.26.7: the MuPDF source as downloaded by a default build of PyMuPDF 1.26.4. The directory name has changed: no version number in the expanded directory now.
author Franz Glasner <fzglas.hg@dom66.de>
date Mon, 15 Sep 2025 11:43:07 +0200
parents
children
comparison
equal deleted inserted replaced
1:1d09e1dec1d9 2:b50eed0cc0ef
1 /*
2 * Copyright 2016 Nu-book Inc.
3 * Copyright 2016 ZXing authors
4 * Copyright 2017 Axel Waggershauser
5 */
6 // SPDX-License-Identifier: Apache-2.0
7
8 #include "ReedSolomonDecoder.h"
9
10 #include "GenericGF.h"
11 #include "ZXConfig.h"
12
13 #include <algorithm>
14 #include <stdexcept>
15 #include <utility>
16
17 namespace ZXing {
18
19 static bool
20 RunEuclideanAlgorithm(const GenericGF& field, std::vector<int>&& rCoefs, GenericGFPoly& sigma, GenericGFPoly& omega)
21 {
22 int R = Size(rCoefs); // == numECCodeWords
23 GenericGFPoly r(field, std::move(rCoefs));
24 GenericGFPoly& tLast = omega.setField(field);
25 GenericGFPoly& t = sigma.setField(field);
26 ZX_THREAD_LOCAL GenericGFPoly q, rLast;
27
28 rLast.setField(field);
29 q.setField(field);
30
31 rLast.setMonomial(1, R);
32 tLast.setMonomial(0);
33 t.setMonomial(1);
34
35 // Assume r's degree is < rLast's
36 if (r.degree() >= rLast.degree())
37 swap(r, rLast);
38
39 // Run Euclidean algorithm until r's degree is less than R/2
40 while (r.degree() >= R / 2) {
41 swap(tLast, t);
42 swap(rLast, r);
43
44 // Divide rLastLast by rLast, with quotient in q and remainder in r
45 if (rLast.isZero())
46 return false; // Oops, Euclidean algorithm already terminated?
47
48 r.divide(rLast, q);
49
50 q.multiply(tLast);
51 q.addOrSubtract(t);
52 swap(t, q); // t = q
53
54 if (r.degree() >= rLast.degree())
55 throw std::runtime_error("Division algorithm failed to reduce polynomial?");
56 }
57
58 int sigmaTildeAtZero = t.constant();
59 if (sigmaTildeAtZero == 0)
60 return false;
61
62 int inverse = field.inverse(sigmaTildeAtZero);
63 t.multiplyByMonomial(inverse);
64 r.multiplyByMonomial(inverse);
65
66 // sigma is t
67 omega = std::move(r);
68 return true;
69 }
70
71 static std::vector<int>
72 FindErrorLocations(const GenericGF& field, const GenericGFPoly& errorLocator)
73 {
74 // This is a direct application of Chien's search
75 int numErrors = errorLocator.degree();
76 std::vector<int> res;
77 res.reserve(numErrors);
78
79 for (int i = 1; i < field.size() && Size(res) < numErrors; i++)
80 if (errorLocator.evaluateAt(i) == 0)
81 res.push_back(field.inverse(i));
82
83 if (Size(res) != numErrors)
84 return {}; // Error locator degree does not match number of roots
85
86 return res;
87 }
88
89 static std::vector<int>
90 FindErrorMagnitudes(const GenericGF& field, const GenericGFPoly& errorEvaluator, const std::vector<int>& errorLocations)
91 {
92 // This is directly applying Forney's Formula
93 int s = Size(errorLocations);
94 std::vector<int> res(s);
95 for (int i = 0; i < s; ++i) {
96 int xiInverse = field.inverse(errorLocations[i]);
97 int denom = 1;
98 for (int j = 0; j < s; ++j)
99 if (i != j)
100 denom = field.multiply(denom, 1 ^ field.multiply(errorLocations[j], xiInverse));
101 res[i] = field.multiply(errorEvaluator.evaluateAt(xiInverse), field.inverse(denom));
102 if (field.generatorBase() != 0)
103 res[i] = field.multiply(res[i], xiInverse);
104 }
105 return res;
106 }
107
108 bool
109 ReedSolomonDecode(const GenericGF& field, std::vector<int>& message, int numECCodeWords)
110 {
111 GenericGFPoly poly(field, message);
112
113 std::vector<int> syndromes(numECCodeWords);
114 for (int i = 0; i < numECCodeWords; i++)
115 syndromes[numECCodeWords - 1 - i] = poly.evaluateAt(field.exp(i + field.generatorBase()));
116
117 // if all syndromes are 0 there is no error to correct
118 if (std::all_of(syndromes.begin(), syndromes.end(), [](int c) { return c == 0; }))
119 return true;
120
121 ZX_THREAD_LOCAL GenericGFPoly sigma, omega;
122
123 if (!RunEuclideanAlgorithm(field, std::move(syndromes), sigma, omega))
124 return false;
125
126 auto errorLocations = FindErrorLocations(field, sigma);
127 if (errorLocations.empty())
128 return false;
129
130 auto errorMagnitudes = FindErrorMagnitudes(field, omega, errorLocations);
131
132 int msgLen = Size(message);
133 for (int i = 0; i < Size(errorLocations); ++i) {
134 int position = msgLen - 1 - field.log(errorLocations[i]);
135 if (position < 0)
136 return false;
137
138 message[position] ^= errorMagnitudes[i];
139 }
140 return true;
141 }
142
143 } // namespace ZXing