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 "xfa/src/fxbarcode/barcode.h"
24 #include "BC_ReedSolomonGF256.h"
25 #include "BC_ReedSolomonGF256Poly.h"
CBC_ReedSolomonGF256Poly(CBC_ReedSolomonGF256 * field,int32_t coefficients)26 CBC_ReedSolomonGF256Poly::CBC_ReedSolomonGF256Poly(CBC_ReedSolomonGF256* field,
27 int32_t coefficients) {
28 if (field == NULL) {
29 return;
30 }
31 m_field = field;
32 m_coefficients.Add(coefficients);
33 }
CBC_ReedSolomonGF256Poly()34 CBC_ReedSolomonGF256Poly::CBC_ReedSolomonGF256Poly() {
35 m_field = NULL;
36 }
Init(CBC_ReedSolomonGF256 * field,CFX_Int32Array * coefficients,int32_t & e)37 void CBC_ReedSolomonGF256Poly::Init(CBC_ReedSolomonGF256* field,
38 CFX_Int32Array* coefficients,
39 int32_t& e) {
40 if (coefficients == NULL || coefficients->GetSize() == 0) {
41 e = BCExceptionCoefficientsSizeIsNull;
42 BC_EXCEPTION_CHECK_ReturnVoid(e);
43 }
44 m_field = field;
45 int32_t coefficientsLength = coefficients->GetSize();
46 if ((coefficientsLength > 1 && (*coefficients)[0] == 0)) {
47 int32_t firstNonZero = 1;
48 while ((firstNonZero < coefficientsLength) &&
49 ((*coefficients)[firstNonZero] == 0)) {
50 firstNonZero++;
51 }
52 if (firstNonZero == coefficientsLength) {
53 m_coefficients.Copy(*(m_field->GetZero()->GetCoefficients()));
54 } else {
55 m_coefficients.SetSize(coefficientsLength - firstNonZero);
56 for (int32_t i = firstNonZero, j = 0; i < coefficientsLength; i++, j++) {
57 m_coefficients[j] = coefficients->operator[](i);
58 }
59 }
60 } else {
61 m_coefficients.Copy(*coefficients);
62 }
63 }
GetCoefficients()64 CFX_Int32Array* CBC_ReedSolomonGF256Poly::GetCoefficients() {
65 return &m_coefficients;
66 }
GetDegree()67 int32_t CBC_ReedSolomonGF256Poly::GetDegree() {
68 return m_coefficients.GetSize() - 1;
69 }
IsZero()70 FX_BOOL CBC_ReedSolomonGF256Poly::IsZero() {
71 return m_coefficients[0] == 0;
72 }
GetCoefficients(int32_t degree)73 int32_t CBC_ReedSolomonGF256Poly::GetCoefficients(int32_t degree) {
74 return m_coefficients[m_coefficients.GetSize() - 1 - degree];
75 }
EvaluateAt(int32_t a)76 int32_t CBC_ReedSolomonGF256Poly::EvaluateAt(int32_t a) {
77 if (a == 0) {
78 return GetCoefficients(0);
79 }
80 int32_t size = m_coefficients.GetSize();
81 if (a == 1) {
82 int32_t result = 0;
83 for (int32_t i = 0; i < size; i++) {
84 result = CBC_ReedSolomonGF256::AddOrSubtract(result, m_coefficients[i]);
85 }
86 return result;
87 }
88 int32_t result = m_coefficients[0];
89 for (int32_t j = 1; j < size; j++) {
90 result = CBC_ReedSolomonGF256::AddOrSubtract(m_field->Multiply(a, result),
91 m_coefficients[j]);
92 }
93 return result;
94 }
Clone(int32_t & e)95 CBC_ReedSolomonGF256Poly* CBC_ReedSolomonGF256Poly::Clone(int32_t& e) {
96 CBC_ReedSolomonGF256Poly* temp = new CBC_ReedSolomonGF256Poly();
97 temp->Init(m_field, &m_coefficients, e);
98 BC_EXCEPTION_CHECK_ReturnValue(e, NULL);
99 return temp;
100 }
AddOrSubtract(CBC_ReedSolomonGF256Poly * other,int32_t & e)101 CBC_ReedSolomonGF256Poly* CBC_ReedSolomonGF256Poly::AddOrSubtract(
102 CBC_ReedSolomonGF256Poly* other,
103 int32_t& e) {
104 if (IsZero()) {
105 return other->Clone(e);
106 BC_EXCEPTION_CHECK_ReturnValue(e, NULL);
107 }
108 if (other->IsZero()) {
109 return this->Clone(e);
110 BC_EXCEPTION_CHECK_ReturnValue(e, NULL);
111 }
112 CFX_Int32Array smallerCoefficients;
113 smallerCoefficients.Copy(m_coefficients);
114 CFX_Int32Array largerCoefficients;
115 largerCoefficients.Copy(*(other->GetCoefficients()));
116 if (smallerCoefficients.GetSize() > largerCoefficients.GetSize()) {
117 CFX_Int32Array temp;
118 temp.Copy(smallerCoefficients);
119 smallerCoefficients.Copy(largerCoefficients);
120 largerCoefficients.Copy(temp);
121 }
122 CFX_Int32Array sumDiff;
123 sumDiff.SetSize(largerCoefficients.GetSize());
124 int32_t lengthDiff =
125 largerCoefficients.GetSize() - smallerCoefficients.GetSize();
126 for (int32_t i = 0; i < lengthDiff; i++) {
127 sumDiff[i] = largerCoefficients[i];
128 }
129 for (int32_t j = lengthDiff; j < largerCoefficients.GetSize(); j++) {
130 sumDiff[j] = (CBC_ReedSolomonGF256::AddOrSubtract(
131 smallerCoefficients[j - lengthDiff], largerCoefficients[j]));
132 }
133 CBC_ReedSolomonGF256Poly* temp = new CBC_ReedSolomonGF256Poly();
134 temp->Init(m_field, &sumDiff, e);
135 BC_EXCEPTION_CHECK_ReturnValue(e, NULL);
136 return temp;
137 }
Multiply(CBC_ReedSolomonGF256Poly * other,int32_t & e)138 CBC_ReedSolomonGF256Poly* CBC_ReedSolomonGF256Poly::Multiply(
139 CBC_ReedSolomonGF256Poly* other,
140 int32_t& e) {
141 if (IsZero() || other->IsZero()) {
142 CBC_ReedSolomonGF256Poly* temp = m_field->GetZero()->Clone(e);
143 BC_EXCEPTION_CHECK_ReturnValue(e, NULL);
144 return temp;
145 }
146 CFX_Int32Array aCoefficients;
147 aCoefficients.Copy(m_coefficients);
148 int32_t aLength = m_coefficients.GetSize();
149 CFX_Int32Array bCoefficients;
150 bCoefficients.Copy(*(other->GetCoefficients()));
151 int32_t bLength = other->GetCoefficients()->GetSize();
152 CFX_Int32Array product;
153 product.SetSize(aLength + bLength - 1);
154 for (int32_t i = 0; i < aLength; i++) {
155 int32_t aCoeff = m_coefficients[i];
156 for (int32_t j = 0; j < bLength; j++) {
157 product[i + j] = CBC_ReedSolomonGF256::AddOrSubtract(
158 product[i + j],
159 m_field->Multiply(aCoeff, other->GetCoefficients()->operator[](j)));
160 }
161 }
162 CBC_ReedSolomonGF256Poly* temp = new CBC_ReedSolomonGF256Poly();
163 temp->Init(m_field, &product, e);
164 BC_EXCEPTION_CHECK_ReturnValue(e, NULL);
165 return temp;
166 }
Multiply(int32_t scalar,int32_t & e)167 CBC_ReedSolomonGF256Poly* CBC_ReedSolomonGF256Poly::Multiply(int32_t scalar,
168 int32_t& e) {
169 if (scalar == 0) {
170 CBC_ReedSolomonGF256Poly* temp = m_field->GetZero()->Clone(e);
171 BC_EXCEPTION_CHECK_ReturnValue(e, NULL);
172 return temp;
173 }
174 if (scalar == 1) {
175 return this->Clone(e);
176 BC_EXCEPTION_CHECK_ReturnValue(e, NULL);
177 }
178 int32_t size = m_coefficients.GetSize();
179 CFX_Int32Array product;
180 product.SetSize(size);
181 for (int32_t i = 0; i < size; i++) {
182 product[i] = m_field->Multiply(m_coefficients[i], scalar);
183 }
184 CBC_ReedSolomonGF256Poly* temp = new CBC_ReedSolomonGF256Poly();
185 temp->Init(m_field, &product, e);
186 BC_EXCEPTION_CHECK_ReturnValue(e, NULL);
187 return temp;
188 }
MultiplyByMonomial(int32_t degree,int32_t coefficient,int32_t & e)189 CBC_ReedSolomonGF256Poly* CBC_ReedSolomonGF256Poly::MultiplyByMonomial(
190 int32_t degree,
191 int32_t coefficient,
192 int32_t& e) {
193 if (degree < 0) {
194 e = BCExceptionDegreeIsNegative;
195 BC_EXCEPTION_CHECK_ReturnValue(e, NULL);
196 }
197 if (coefficient == 0) {
198 CBC_ReedSolomonGF256Poly* temp = m_field->GetZero()->Clone(e);
199 BC_EXCEPTION_CHECK_ReturnValue(e, NULL);
200 return temp;
201 }
202 int32_t size = m_coefficients.GetSize();
203 CFX_Int32Array product;
204 product.SetSize(size + degree);
205 for (int32_t i = 0; i < size; i++) {
206 product[i] = (m_field->Multiply(m_coefficients[i], coefficient));
207 }
208 CBC_ReedSolomonGF256Poly* temp = new CBC_ReedSolomonGF256Poly();
209 temp->Init(m_field, &product, e);
210 BC_EXCEPTION_CHECK_ReturnValue(e, NULL);
211 return temp;
212 }
Divide(CBC_ReedSolomonGF256Poly * other,int32_t & e)213 CFX_PtrArray* CBC_ReedSolomonGF256Poly::Divide(CBC_ReedSolomonGF256Poly* other,
214 int32_t& e) {
215 if (other->IsZero()) {
216 e = BCExceptionDivideByZero;
217 BC_EXCEPTION_CHECK_ReturnValue(e, NULL);
218 }
219 CBC_ReedSolomonGF256Poly* rsg1 = m_field->GetZero()->Clone(e);
220 BC_EXCEPTION_CHECK_ReturnValue(e, NULL);
221 CBC_AutoPtr<CBC_ReedSolomonGF256Poly> quotient(rsg1);
222 CBC_ReedSolomonGF256Poly* rsg2 = this->Clone(e);
223 BC_EXCEPTION_CHECK_ReturnValue(e, NULL);
224 CBC_AutoPtr<CBC_ReedSolomonGF256Poly> remainder(rsg2);
225 int32_t denominatorLeadingTerm = other->GetCoefficients(other->GetDegree());
226 int32_t inverseDenominatorLeadingTeam =
227 m_field->Inverse(denominatorLeadingTerm, e);
228 BC_EXCEPTION_CHECK_ReturnValue(e, NULL);
229 while (remainder->GetDegree() >= other->GetDegree() && !remainder->IsZero()) {
230 int32_t degreeDifference = remainder->GetDegree() - other->GetDegree();
231 int32_t scale =
232 m_field->Multiply(remainder->GetCoefficients((remainder->GetDegree())),
233 inverseDenominatorLeadingTeam);
234 CBC_ReedSolomonGF256Poly* rsg3 =
235 other->MultiplyByMonomial(degreeDifference, scale, e);
236 BC_EXCEPTION_CHECK_ReturnValue(e, NULL);
237 CBC_AutoPtr<CBC_ReedSolomonGF256Poly> term(rsg3);
238 CBC_ReedSolomonGF256Poly* rsg4 =
239 m_field->BuildMonomial(degreeDifference, scale, e);
240 BC_EXCEPTION_CHECK_ReturnValue(e, NULL);
241 CBC_AutoPtr<CBC_ReedSolomonGF256Poly> iteratorQuotient(rsg4);
242 CBC_ReedSolomonGF256Poly* rsg5 =
243 quotient->AddOrSubtract(iteratorQuotient.get(), e);
244 BC_EXCEPTION_CHECK_ReturnValue(e, NULL);
245 CBC_AutoPtr<CBC_ReedSolomonGF256Poly> temp(rsg5);
246 quotient = temp;
247 CBC_ReedSolomonGF256Poly* rsg6 = remainder->AddOrSubtract(term.get(), e);
248 BC_EXCEPTION_CHECK_ReturnValue(e, NULL);
249 CBC_AutoPtr<CBC_ReedSolomonGF256Poly> temp1(rsg6);
250 remainder = temp1;
251 }
252 CFX_PtrArray* tempPtrA = new CFX_PtrArray;
253 tempPtrA->Add(quotient.release());
254 tempPtrA->Add(remainder.release());
255 return tempPtrA;
256 }
~CBC_ReedSolomonGF256Poly()257 CBC_ReedSolomonGF256Poly::~CBC_ReedSolomonGF256Poly() {
258 m_coefficients.RemoveAll();
259 }
260