1 /*
2 * Copyright 2016 Nu-book Inc.
3 * Copyright 2016 ZXing authors
4 * Copyright 2017 Axel Waggershauser
5 *
6 * Licensed under the Apache License, Version 2.0 (the "License");
7 * you may not use this file except in compliance with the License.
8 * You may obtain a copy of the License at
9 *
10 * http://www.apache.org/licenses/LICENSE-2.0
11 *
12 * Unless required by applicable law or agreed to in writing, software
13 * distributed under the License is distributed on an "AS IS" BASIS,
14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 * See the License for the specific language governing permissions and
16 * limitations under the License.
17 */
18
19 #include "GenericGFPoly.h"
20
21 #include "GenericGF.h"
22 #include "ZXConfig.h"
23 #include "ZXContainerAlgorithms.h"
24
25 #include <algorithm>
26 #include <cassert>
27 #include <stdexcept>
28
29 namespace ZXing {
30
31 int
evaluateAt(int a) const32 GenericGFPoly::evaluateAt(int a) const
33 {
34 if (a == 0)
35 // Just return the x^0 coefficient
36 return constant();
37
38 if (a == 1)
39 // Just the sum of the coefficients
40 return Reduce(_coefficients, 0, [](auto a, auto b) { return a ^ b; });
41
42 int result = _coefficients[0];
43 for (size_t i = 1; i < _coefficients.size(); ++i)
44 result = _field->multiply(a, result) ^ _coefficients[i];
45 return result;
46 }
47
addOrSubtract(GenericGFPoly & other)48 GenericGFPoly& GenericGFPoly::addOrSubtract(GenericGFPoly& other)
49 {
50 assert(_field == other._field); // "GenericGFPolys do not have same GenericGF field"
51
52 if (isZero()) {
53 swap(*this, other);
54 return *this;
55 }
56
57 if (other.isZero())
58 return *this;
59
60 auto& smallerCoefs = other._coefficients;
61 auto& largerCoefs = _coefficients;
62 if (smallerCoefs.size() > largerCoefs.size())
63 std::swap(smallerCoefs, largerCoefs);
64
65 size_t lengthDiff = largerCoefs.size() - smallerCoefs.size();
66
67 // high-order terms only found in higher-degree polynomial's coefficients stay untouched
68 for (size_t i = lengthDiff; i < largerCoefs.size(); ++i)
69 largerCoefs[i] ^= smallerCoefs[i - lengthDiff];
70
71 normalize();
72 return *this;
73 }
74
75 GenericGFPoly&
multiply(const GenericGFPoly & other)76 GenericGFPoly::multiply(const GenericGFPoly& other)
77 {
78 assert(_field == other._field); // "GenericGFPolys do not have same GenericGF field"
79
80 if (isZero() || other.isZero())
81 return setMonomial(0);
82
83 auto& a = _coefficients;
84 auto& b = other._coefficients;
85
86 // To disable the use of the malloc cache, simply uncomment:
87 // Coefficients _cache;
88 _cache.resize(a.size() + b.size() - 1);
89 std::fill(_cache.begin(), _cache.end(), 0);
90 for (size_t i = 0; i < a.size(); ++i)
91 for (size_t j = 0; j < b.size(); ++j)
92 _cache[i + j] ^= _field->multiply(a[i], b[j]);
93
94 _coefficients.swap(_cache);
95
96 normalize();
97 return *this;
98 }
99
100 GenericGFPoly&
multiplyByMonomial(int coefficient,int degree)101 GenericGFPoly::multiplyByMonomial(int coefficient, int degree)
102 {
103 assert(degree >= 0);
104
105 if (coefficient == 0)
106 return setMonomial(0);
107
108 for (int& c : _coefficients)
109 c = _field->multiply(c, coefficient);
110
111 _coefficients.resize(_coefficients.size() + degree, 0);
112
113 normalize();
114 return *this;
115 }
116
117 GenericGFPoly&
divide(const GenericGFPoly & other,GenericGFPoly & quotient)118 GenericGFPoly::divide(const GenericGFPoly& other, GenericGFPoly& quotient)
119 {
120 assert(_field == other._field); // "GenericGFPolys do not have same GenericGF field"
121
122 if (other.isZero())
123 throw std::invalid_argument("Divide by 0");
124
125 quotient.setField(*_field);
126 if (degree() < other.degree()) {
127 // the remainder is this and the quotient is 0
128 quotient.setMonomial(0);
129 return *this;
130 }
131
132 // use Expanded Synthetic Division (see https://en.wikiversity.org/wiki/Reed%E2%80%93Solomon_codes_for_coders):
133 // we use the memory from this (the dividend) and swap it with quotient, which will then accumulate the result as
134 // [quotient : remainder]. we later copy back the remainder into this and shorten the quotient.
135 std::swap(*this, quotient);
136 auto& divisor = other._coefficients;
137 auto& result = quotient._coefficients;
138 auto normalizer = _field->inverse(divisor[0]);
139 for (int i = 0; i < Size(result) - (Size(divisor) - 1); ++i) {
140 auto& ci = result[i];
141 if (ci == 0)
142 continue;
143
144 ci = _field->multiply(ci, normalizer);
145
146 // we always skip the first coefficient of the divisor, because it's only used to normalize the dividend coefficient
147 for (int j = 1; j < Size(divisor); ++j)
148 result[i + j] ^= _field->multiply(divisor[j], ci); // equivalent to: result[i + j] += -divisor[j] * ci
149 }
150
151 // extract the normalized remainder from result
152 auto firstNonZero = std::find_if(result.end() - other.degree(), result.end(), [](int c){ return c != 0; });
153 if (firstNonZero == result.end()) {
154 setMonomial(0);
155 } else {
156 _coefficients.resize(result.end() - firstNonZero);
157 std::copy(firstNonZero, result.end(), _coefficients.begin());
158 }
159 // cut off the tail with the remainder to leave the quotient
160 result.resize(result.size() - other.degree());
161
162 return *this;
163 }
164
normalize()165 void GenericGFPoly::normalize()
166 {
167 auto firstNonZero = FindIf(_coefficients, [](int c){ return c != 0; });
168 // Leading term must be non-zero for anything except the constant polynomial "0"
169 if (firstNonZero != _coefficients.begin()) {
170 if (firstNonZero == _coefficients.end()) {
171 _coefficients.resize(1, 0);
172 } else {
173 std::copy(firstNonZero, _coefficients.end(), _coefficients.begin());
174 _coefficients.resize(_coefficients.end() - firstNonZero);
175 }
176 }
177 }
178
179 } // namespace ZXing
180