1 // Copyright 2014 PDFium Authors. All rights reserved.
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 "fxbarcode/common/reedsolomon/BC_ReedSolomonGF256.h"
30 #include "third_party/base/ptr_util.h"
31 #include "third_party/base/stl_util.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 ASSERT(m_field);
38 ASSERT(!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 pdfium::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 pdfium::MakeUnique<CBC_ReedSolomonGF256Poly>(m_field.Get(),
79 m_coefficients);
80 }
81
82 std::unique_ptr<CBC_ReedSolomonGF256Poly>
AddOrSubtract(const CBC_ReedSolomonGF256Poly * other)83 CBC_ReedSolomonGF256Poly::AddOrSubtract(const CBC_ReedSolomonGF256Poly* other) {
84 if (IsZero())
85 return other->Clone();
86 if (other->IsZero())
87 return Clone();
88
89 std::vector<int32_t> smallerCoefficients = m_coefficients;
90 std::vector<int32_t> largerCoefficients = other->GetCoefficients();
91 if (smallerCoefficients.size() > largerCoefficients.size())
92 std::swap(smallerCoefficients, largerCoefficients);
93
94 std::vector<int32_t> sumDiff(largerCoefficients.size());
95 size_t lengthDiff = largerCoefficients.size() - smallerCoefficients.size();
96 for (size_t i = 0; i < lengthDiff; ++i)
97 sumDiff[i] = largerCoefficients[i];
98
99 for (size_t i = lengthDiff; i < largerCoefficients.size(); ++i) {
100 sumDiff[i] = CBC_ReedSolomonGF256::AddOrSubtract(
101 smallerCoefficients[i - lengthDiff], largerCoefficients[i]);
102 }
103 return pdfium::MakeUnique<CBC_ReedSolomonGF256Poly>(m_field.Get(), sumDiff);
104 }
105
Multiply(const CBC_ReedSolomonGF256Poly * other)106 std::unique_ptr<CBC_ReedSolomonGF256Poly> CBC_ReedSolomonGF256Poly::Multiply(
107 const CBC_ReedSolomonGF256Poly* other) {
108 if (IsZero() || other->IsZero())
109 return m_field->GetZero()->Clone();
110
111 const std::vector<int32_t>& aCoefficients = m_coefficients;
112 const std::vector<int32_t>& bCoefficients = other->GetCoefficients();
113 size_t aLength = aCoefficients.size();
114 size_t bLength = bCoefficients.size();
115 std::vector<int32_t> product(aLength + bLength - 1);
116 for (size_t i = 0; i < aLength; i++) {
117 int32_t aCoeff = aCoefficients[i];
118 for (size_t j = 0; j < bLength; j++) {
119 product[i + j] = CBC_ReedSolomonGF256::AddOrSubtract(
120 product[i + j], m_field->Multiply(aCoeff, bCoefficients[j]));
121 }
122 }
123 return pdfium::MakeUnique<CBC_ReedSolomonGF256Poly>(m_field.Get(), product);
124 }
125
126 std::unique_ptr<CBC_ReedSolomonGF256Poly>
MultiplyByMonomial(int32_t degree,int32_t coefficient) const127 CBC_ReedSolomonGF256Poly::MultiplyByMonomial(int32_t degree,
128 int32_t coefficient) const {
129 if (degree < 0)
130 return nullptr;
131 if (coefficient == 0)
132 return m_field->GetZero()->Clone();
133
134 size_t size = m_coefficients.size();
135 std::vector<int32_t> product(size + degree);
136 for (size_t i = 0; i < size; i++)
137 product[i] = m_field->Multiply(m_coefficients[i], coefficient);
138
139 return pdfium::MakeUnique<CBC_ReedSolomonGF256Poly>(m_field.Get(), product);
140 }
141
Divide(const CBC_ReedSolomonGF256Poly * other)142 std::unique_ptr<CBC_ReedSolomonGF256Poly> CBC_ReedSolomonGF256Poly::Divide(
143 const CBC_ReedSolomonGF256Poly* other) {
144 if (other->IsZero())
145 return nullptr;
146
147 auto quotient = m_field->GetZero()->Clone();
148 if (!quotient)
149 return nullptr;
150 auto remainder = Clone();
151 if (!remainder)
152 return nullptr;
153
154 int32_t denominatorLeadingTerm = other->GetCoefficients(other->GetDegree());
155 Optional<int32_t> inverseDenominatorLeadingTeam =
156 m_field->Inverse(denominatorLeadingTerm);
157 if (!inverseDenominatorLeadingTeam.has_value())
158 return nullptr;
159
160 while (remainder->GetDegree() >= other->GetDegree() && !remainder->IsZero()) {
161 int32_t degreeDifference = remainder->GetDegree() - other->GetDegree();
162 int32_t scale =
163 m_field->Multiply(remainder->GetCoefficients((remainder->GetDegree())),
164 inverseDenominatorLeadingTeam.value());
165 auto term = other->MultiplyByMonomial(degreeDifference, scale);
166 if (!term)
167 return nullptr;
168 auto iteratorQuotient = m_field->BuildMonomial(degreeDifference, scale);
169 if (!iteratorQuotient)
170 return nullptr;
171 quotient = quotient->AddOrSubtract(iteratorQuotient.get());
172 if (!quotient)
173 return nullptr;
174 remainder = remainder->AddOrSubtract(term.get());
175 if (!remainder)
176 return nullptr;
177 }
178 return remainder;
179 }
180