1 // Copyright 2014 The PDFium Authors
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 // Original code copyright 2014 Foxit Software Inc. http://www.foxitsoftware.com
6 // Original code is licensed as follows:
7 /*
8 * Copyright 2007 ZXing authors
9 *
10 * Licensed under the Apache License, Version 2.0 (the "License");
11 * you may not use this file except in compliance with the License.
12 * You may obtain a copy of the License at
13 *
14 * http://www.apache.org/licenses/LICENSE-2.0
15 *
16 * Unless required by applicable law or agreed to in writing, software
17 * distributed under the License is distributed on an "AS IS" BASIS,
18 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
19 * See the License for the specific language governing permissions and
20 * limitations under the License.
21 */
22
23 #include "fxbarcode/common/reedsolomon/BC_ReedSolomonGF256Poly.h"
24
25 #include <memory>
26 #include <utility>
27
28 #include "core/fxcrt/fx_system.h"
29 #include "core/fxcrt/stl_util.h"
30 #include "fxbarcode/common/reedsolomon/BC_ReedSolomonGF256.h"
31 #include "third_party/base/check.h"
32
CBC_ReedSolomonGF256Poly(CBC_ReedSolomonGF256 * field,const std::vector<int32_t> & coefficients)33 CBC_ReedSolomonGF256Poly::CBC_ReedSolomonGF256Poly(
34 CBC_ReedSolomonGF256* field,
35 const std::vector<int32_t>& coefficients)
36 : m_field(field) {
37 DCHECK(m_field);
38 DCHECK(!coefficients.empty());
39 if (coefficients.size() == 1 || coefficients.front() != 0) {
40 m_coefficients = coefficients;
41 return;
42 }
43
44 size_t firstNonZero = 1;
45 while (firstNonZero < coefficients.size() &&
46 coefficients[firstNonZero] == 0) {
47 firstNonZero++;
48 }
49 if (firstNonZero == coefficients.size()) {
50 m_coefficients = m_field->GetZero()->GetCoefficients();
51 } else {
52 m_coefficients.resize(coefficients.size() - firstNonZero);
53 for (size_t i = firstNonZero, j = 0; i < coefficients.size(); i++, j++)
54 m_coefficients[j] = coefficients[i];
55 }
56 }
57
58 CBC_ReedSolomonGF256Poly::~CBC_ReedSolomonGF256Poly() = default;
59
GetCoefficients() const60 const std::vector<int32_t>& CBC_ReedSolomonGF256Poly::GetCoefficients() const {
61 return m_coefficients;
62 }
63
GetDegree() const64 int32_t CBC_ReedSolomonGF256Poly::GetDegree() const {
65 return fxcrt::CollectionSize<int32_t>(m_coefficients) - 1;
66 }
67
IsZero() const68 bool CBC_ReedSolomonGF256Poly::IsZero() const {
69 return m_coefficients.front() == 0;
70 }
71
GetCoefficients(int32_t degree) const72 int32_t CBC_ReedSolomonGF256Poly::GetCoefficients(int32_t degree) const {
73 return m_coefficients[m_coefficients.size() - 1 - degree];
74 }
75
Clone() const76 std::unique_ptr<CBC_ReedSolomonGF256Poly> CBC_ReedSolomonGF256Poly::Clone()
77 const {
78 return std::make_unique<CBC_ReedSolomonGF256Poly>(m_field, m_coefficients);
79 }
80
81 std::unique_ptr<CBC_ReedSolomonGF256Poly>
AddOrSubtract(const CBC_ReedSolomonGF256Poly * other)82 CBC_ReedSolomonGF256Poly::AddOrSubtract(const CBC_ReedSolomonGF256Poly* other) {
83 if (IsZero())
84 return other->Clone();
85 if (other->IsZero())
86 return Clone();
87
88 std::vector<int32_t> smallerCoefficients = m_coefficients;
89 std::vector<int32_t> largerCoefficients = other->GetCoefficients();
90 if (smallerCoefficients.size() > largerCoefficients.size())
91 std::swap(smallerCoefficients, largerCoefficients);
92
93 std::vector<int32_t> sumDiff(largerCoefficients.size());
94 size_t lengthDiff = largerCoefficients.size() - smallerCoefficients.size();
95 for (size_t i = 0; i < lengthDiff; ++i)
96 sumDiff[i] = largerCoefficients[i];
97
98 for (size_t i = lengthDiff; i < largerCoefficients.size(); ++i) {
99 sumDiff[i] = CBC_ReedSolomonGF256::AddOrSubtract(
100 smallerCoefficients[i - lengthDiff], largerCoefficients[i]);
101 }
102 return std::make_unique<CBC_ReedSolomonGF256Poly>(m_field, sumDiff);
103 }
104
Multiply(const CBC_ReedSolomonGF256Poly * other)105 std::unique_ptr<CBC_ReedSolomonGF256Poly> CBC_ReedSolomonGF256Poly::Multiply(
106 const CBC_ReedSolomonGF256Poly* other) {
107 if (IsZero() || other->IsZero())
108 return m_field->GetZero()->Clone();
109
110 const std::vector<int32_t>& aCoefficients = m_coefficients;
111 const std::vector<int32_t>& bCoefficients = other->GetCoefficients();
112 size_t aLength = aCoefficients.size();
113 size_t bLength = bCoefficients.size();
114 std::vector<int32_t> product(aLength + bLength - 1);
115 for (size_t i = 0; i < aLength; i++) {
116 int32_t aCoeff = aCoefficients[i];
117 for (size_t j = 0; j < bLength; j++) {
118 product[i + j] = CBC_ReedSolomonGF256::AddOrSubtract(
119 product[i + j], m_field->Multiply(aCoeff, bCoefficients[j]));
120 }
121 }
122 return std::make_unique<CBC_ReedSolomonGF256Poly>(m_field, product);
123 }
124
125 std::unique_ptr<CBC_ReedSolomonGF256Poly>
MultiplyByMonomial(int32_t degree,int32_t coefficient) const126 CBC_ReedSolomonGF256Poly::MultiplyByMonomial(int32_t degree,
127 int32_t coefficient) const {
128 if (degree < 0)
129 return nullptr;
130 if (coefficient == 0)
131 return m_field->GetZero()->Clone();
132
133 size_t size = m_coefficients.size();
134 std::vector<int32_t> product(size + degree);
135 for (size_t i = 0; i < size; i++)
136 product[i] = m_field->Multiply(m_coefficients[i], coefficient);
137
138 return std::make_unique<CBC_ReedSolomonGF256Poly>(m_field, product);
139 }
140
Divide(const CBC_ReedSolomonGF256Poly * other)141 std::unique_ptr<CBC_ReedSolomonGF256Poly> CBC_ReedSolomonGF256Poly::Divide(
142 const CBC_ReedSolomonGF256Poly* other) {
143 if (other->IsZero())
144 return nullptr;
145
146 auto quotient = m_field->GetZero()->Clone();
147 if (!quotient)
148 return nullptr;
149 auto remainder = Clone();
150 if (!remainder)
151 return nullptr;
152
153 int32_t denominatorLeadingTerm = other->GetCoefficients(other->GetDegree());
154 absl::optional<int32_t> inverseDenominatorLeadingTeam =
155 m_field->Inverse(denominatorLeadingTerm);
156 if (!inverseDenominatorLeadingTeam.has_value())
157 return nullptr;
158
159 while (remainder->GetDegree() >= other->GetDegree() && !remainder->IsZero()) {
160 int32_t degreeDifference = remainder->GetDegree() - other->GetDegree();
161 int32_t scale =
162 m_field->Multiply(remainder->GetCoefficients((remainder->GetDegree())),
163 inverseDenominatorLeadingTeam.value());
164 auto term = other->MultiplyByMonomial(degreeDifference, scale);
165 if (!term)
166 return nullptr;
167 auto iteratorQuotient = m_field->BuildMonomial(degreeDifference, scale);
168 if (!iteratorQuotient)
169 return nullptr;
170 quotient = quotient->AddOrSubtract(iteratorQuotient.get());
171 if (!quotient)
172 return nullptr;
173 remainder = remainder->AddOrSubtract(term.get());
174 if (!remainder)
175 return nullptr;
176 }
177 return remainder;
178 }
179