Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/thirdparty/zxing-cpp/core/src/GenericGFPoly.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 "GenericGFPoly.h"
9
10 #include "GenericGF.h"
11 #include "ZXAlgorithms.h"
12
13 #include <algorithm>
14 #include <cassert>
15 #include <stdexcept>
16
17 namespace ZXing {
18
19 int
20 GenericGFPoly::evaluateAt(int a) const
21 {
22 if (a == 0) // return the x^0 coefficient
23 return constant();
24
25 if (a == 1) // return the sum of the coefficients
26 return Reduce(_coefficients, 0, [](auto s, auto c) { return s ^ c; });
27
28 return std::accumulate(_coefficients.begin(), _coefficients.end(), 0,
29 [this, a](auto s, auto c) { return _field->multiply(a, s) ^ c; });
30 }
31
32 GenericGFPoly& GenericGFPoly::addOrSubtract(GenericGFPoly& other)
33 {
34 assert(_field == other._field); // "GenericGFPolys do not have same GenericGF field"
35
36 if (isZero()) {
37 swap(*this, other);
38 return *this;
39 }
40
41 if (other.isZero())
42 return *this;
43
44 auto& smallerCoefs = other._coefficients;
45 auto& largerCoefs = _coefficients;
46 if (smallerCoefs.size() > largerCoefs.size())
47 std::swap(smallerCoefs, largerCoefs);
48
49 size_t lengthDiff = largerCoefs.size() - smallerCoefs.size();
50
51 // high-order terms only found in higher-degree polynomial's coefficients stay untouched
52 for (size_t i = lengthDiff; i < largerCoefs.size(); ++i)
53 largerCoefs[i] ^= smallerCoefs[i - lengthDiff];
54
55 normalize();
56 return *this;
57 }
58
59 GenericGFPoly&
60 GenericGFPoly::multiply(const GenericGFPoly& other)
61 {
62 assert(_field == other._field); // "GenericGFPolys do not have same GenericGF field"
63
64 if (isZero() || other.isZero())
65 return setMonomial(0);
66
67 auto& a = _coefficients;
68 auto& b = other._coefficients;
69
70 // To disable the use of the malloc cache, simply uncomment:
71 // Coefficients _cache;
72 _cache.resize(a.size() + b.size() - 1);
73 std::fill(_cache.begin(), _cache.end(), 0);
74 for (size_t i = 0; i < a.size(); ++i)
75 for (size_t j = 0; j < b.size(); ++j)
76 _cache[i + j] ^= _field->multiply(a[i], b[j]);
77
78 _coefficients.swap(_cache);
79
80 normalize();
81 return *this;
82 }
83
84 GenericGFPoly&
85 GenericGFPoly::multiplyByMonomial(int coefficient, int degree)
86 {
87 assert(degree >= 0);
88
89 if (coefficient == 0)
90 return setMonomial(0);
91
92 for (int& c : _coefficients)
93 c = _field->multiply(c, coefficient);
94
95 _coefficients.resize(_coefficients.size() + degree, 0);
96
97 normalize();
98 return *this;
99 }
100
101 GenericGFPoly&
102 GenericGFPoly::divide(const GenericGFPoly& other, GenericGFPoly& quotient)
103 {
104 assert(_field == other._field); // "GenericGFPolys do not have same GenericGF field"
105
106 if (other.isZero())
107 throw std::invalid_argument("Divide by 0");
108
109 quotient.setField(*_field);
110 if (degree() < other.degree()) {
111 // the remainder is this and the quotient is 0
112 quotient.setMonomial(0);
113 return *this;
114 }
115
116 // use Expanded Synthetic Division (see https://en.wikiversity.org/wiki/Reed%E2%80%93Solomon_codes_for_coders):
117 // we use the memory from this (the dividend) and swap it with quotient, which will then accumulate the result as
118 // [quotient : remainder]. we later copy back the remainder into this and shorten the quotient.
119 std::swap(*this, quotient);
120 auto& divisor = other._coefficients;
121 auto& result = quotient._coefficients;
122 auto normalizer = _field->inverse(divisor[0]);
123 for (int i = 0; i < Size(result) - (Size(divisor) - 1); ++i) {
124 auto& ci = result[i];
125 if (ci == 0)
126 continue;
127
128 ci = _field->multiply(ci, normalizer);
129
130 // we always skip the first coefficient of the divisor, because it's only used to normalize the dividend coefficient
131 for (int j = 1; j < Size(divisor); ++j)
132 result[i + j] ^= _field->multiply(divisor[j], ci); // equivalent to: result[i + j] += -divisor[j] * ci
133 }
134
135 // extract the normalized remainder from result
136 auto firstNonZero = std::find_if(result.end() - other.degree(), result.end(), [](int c){ return c != 0; });
137 if (firstNonZero == result.end()) {
138 setMonomial(0);
139 } else {
140 _coefficients.resize(result.end() - firstNonZero);
141 std::copy(firstNonZero, result.end(), _coefficients.begin());
142 }
143 // cut off the tail with the remainder to leave the quotient
144 result.resize(result.size() - other.degree());
145
146 return *this;
147 }
148
149 void GenericGFPoly::normalize()
150 {
151 auto firstNonZero = FindIf(_coefficients, [](int c){ return c != 0; });
152 // Leading term must be non-zero for anything except the constant polynomial "0"
153 if (firstNonZero != _coefficients.begin()) {
154 if (firstNonZero == _coefficients.end()) {
155 _coefficients.resize(1, 0);
156 } else {
157 std::copy(firstNonZero, _coefficients.end(), _coefficients.begin());
158 _coefficients.resize(_coefficients.end() - firstNonZero);
159 }
160 }
161 }
162
163 } // namespace ZXing