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 2012 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_PDF417Common.h"
25 #include "BC_PDF417ECModulusGF.h"
26 #include "BC_PDF417ECModulusPoly.h"
CBC_PDF417ECModulusPoly(CBC_PDF417ECModulusGF * field,CFX_Int32Array & coefficients,int32_t & e)27 CBC_PDF417ECModulusPoly::CBC_PDF417ECModulusPoly(CBC_PDF417ECModulusGF* field,
28                                                  CFX_Int32Array& coefficients,
29                                                  int32_t& e) {
30   if (coefficients.GetSize() == 0) {
31     e = BCExceptionIllegalArgument;
32   }
33   m_field = field;
34   int32_t coefficientsLength = coefficients.GetSize();
35   if (coefficientsLength > 1 && coefficients[0] == 0) {
36     int32_t firstNonZero = 1;
37     while (firstNonZero < coefficientsLength &&
38            coefficients[firstNonZero] == 0) {
39       firstNonZero++;
40     }
41     if (firstNonZero == coefficientsLength) {
42       m_coefficients = field->getZero()->m_coefficients;
43     } else {
44       m_coefficients.SetSize(coefficientsLength - firstNonZero);
45       int32_t l = 0;
46       for (int32_t i = firstNonZero;
47            i < firstNonZero + m_coefficients.GetSize(); i++) {
48         m_coefficients.SetAt(l, coefficients.GetAt(i));
49         l++;
50       }
51     }
52   } else {
53     m_coefficients.Copy(coefficients);
54   }
55 }
~CBC_PDF417ECModulusPoly()56 CBC_PDF417ECModulusPoly::~CBC_PDF417ECModulusPoly() {}
getCoefficients()57 CFX_Int32Array& CBC_PDF417ECModulusPoly::getCoefficients() {
58   return m_coefficients;
59 }
getField()60 CBC_PDF417ECModulusGF* CBC_PDF417ECModulusPoly::getField() {
61   return m_field;
62 }
getDegree()63 int32_t CBC_PDF417ECModulusPoly::getDegree() {
64   return m_coefficients.GetSize() - 1;
65 }
isZero()66 FX_BOOL CBC_PDF417ECModulusPoly::isZero() {
67   return m_coefficients[0] == 0;
68 }
getCoefficient(int32_t degree)69 int32_t CBC_PDF417ECModulusPoly::getCoefficient(int32_t degree) {
70   return m_coefficients[m_coefficients.GetSize() - 1 - degree];
71 }
evaluateAt(int32_t a)72 int32_t CBC_PDF417ECModulusPoly::evaluateAt(int32_t a) {
73   if (a == 0) {
74     return getCoefficient(0);
75   }
76   int32_t size = m_coefficients.GetSize();
77   if (a == 1) {
78     int32_t result = 0;
79     for (int32_t l = 0; l < m_coefficients.GetSize(); l++) {
80       int32_t coefficient = m_coefficients.GetAt(l);
81       result = m_field->add(result, coefficient);
82     }
83     return result;
84   }
85   int32_t result = m_coefficients[0];
86   for (int32_t i = 1; i < size; i++) {
87     result = m_field->add(m_field->multiply(a, result), m_coefficients[i]);
88   }
89   return result;
90 }
add(CBC_PDF417ECModulusPoly * other,int32_t & e)91 CBC_PDF417ECModulusPoly* CBC_PDF417ECModulusPoly::add(
92     CBC_PDF417ECModulusPoly* other,
93     int32_t& e) {
94   CBC_PDF417ECModulusPoly* modulusPoly = NULL;
95   if (isZero()) {
96     modulusPoly = new CBC_PDF417ECModulusPoly(other->getField(),
97                                               other->getCoefficients(), e);
98     BC_EXCEPTION_CHECK_ReturnValue(e, NULL);
99     return modulusPoly;
100   }
101   if (other->isZero()) {
102     modulusPoly = new CBC_PDF417ECModulusPoly(m_field, m_coefficients, e);
103     BC_EXCEPTION_CHECK_ReturnValue(e, NULL);
104     return modulusPoly;
105   }
106   CFX_Int32Array smallerCoefficients;
107   smallerCoefficients.Copy(m_coefficients);
108   CFX_Int32Array largerCoefficients;
109   largerCoefficients.Copy(other->m_coefficients);
110   if (smallerCoefficients.GetSize() > largerCoefficients.GetSize()) {
111     CFX_Int32Array temp;
112     temp.Copy(smallerCoefficients);
113     smallerCoefficients.Copy(largerCoefficients);
114     largerCoefficients.Copy(temp);
115   }
116   CFX_Int32Array sumDiff;
117   sumDiff.SetSize(largerCoefficients.GetSize());
118   int32_t lengthDiff =
119       largerCoefficients.GetSize() - smallerCoefficients.GetSize();
120   for (int32_t l = 0; l < lengthDiff; l++) {
121     sumDiff.SetAt(l, largerCoefficients.GetAt(l));
122   }
123   for (int32_t i = lengthDiff; i < largerCoefficients.GetSize(); i++) {
124     sumDiff[i] = m_field->add(smallerCoefficients[i - lengthDiff],
125                               largerCoefficients[i]);
126   }
127   modulusPoly = new CBC_PDF417ECModulusPoly(m_field, sumDiff, e);
128   BC_EXCEPTION_CHECK_ReturnValue(e, NULL);
129   return modulusPoly;
130 }
subtract(CBC_PDF417ECModulusPoly * other,int32_t & e)131 CBC_PDF417ECModulusPoly* CBC_PDF417ECModulusPoly::subtract(
132     CBC_PDF417ECModulusPoly* other,
133     int32_t& e) {
134   CBC_PDF417ECModulusPoly* modulusPoly = NULL;
135   if (other->isZero()) {
136     modulusPoly = new CBC_PDF417ECModulusPoly(m_field, m_coefficients, e);
137     BC_EXCEPTION_CHECK_ReturnValue(e, NULL);
138     return modulusPoly;
139   }
140   CBC_PDF417ECModulusPoly* poly = other->negative(e);
141   BC_EXCEPTION_CHECK_ReturnValue(e, NULL);
142   modulusPoly = add(poly, e);
143   delete poly;
144   BC_EXCEPTION_CHECK_ReturnValue(e, NULL);
145   return modulusPoly;
146 }
multiply(CBC_PDF417ECModulusPoly * other,int32_t & e)147 CBC_PDF417ECModulusPoly* CBC_PDF417ECModulusPoly::multiply(
148     CBC_PDF417ECModulusPoly* other,
149     int32_t& e) {
150   CBC_PDF417ECModulusPoly* modulusPoly = NULL;
151   if (isZero() || other->isZero()) {
152     modulusPoly =
153         new CBC_PDF417ECModulusPoly(m_field->getZero()->getField(),
154                                     m_field->getZero()->getCoefficients(), e);
155     BC_EXCEPTION_CHECK_ReturnValue(e, NULL);
156     return modulusPoly;
157   }
158   CFX_Int32Array aCoefficients;
159   aCoefficients.Copy(m_coefficients);
160   int32_t aLength = aCoefficients.GetSize();
161   CFX_Int32Array bCoefficients;
162   bCoefficients.Copy(other->m_coefficients);
163   int32_t bLength = bCoefficients.GetSize();
164   CFX_Int32Array product;
165   product.SetSize(aLength + bLength - 1);
166   for (int32_t i = 0; i < aLength; i++) {
167     int32_t aCoeff = aCoefficients[i];
168     for (int32_t j = 0; j < bLength; j++) {
169       product[i + j] = m_field->add(
170           product[i + j], m_field->multiply(aCoeff, bCoefficients[j]));
171     }
172   }
173   modulusPoly = new CBC_PDF417ECModulusPoly(m_field, product, e);
174   BC_EXCEPTION_CHECK_ReturnValue(e, NULL);
175   return modulusPoly;
176 }
negative(int32_t & e)177 CBC_PDF417ECModulusPoly* CBC_PDF417ECModulusPoly::negative(int32_t& e) {
178   int32_t size = m_coefficients.GetSize();
179   CFX_Int32Array negativeCoefficients;
180   negativeCoefficients.SetSize(size);
181   for (int32_t i = 0; i < size; i++) {
182     negativeCoefficients[i] = m_field->subtract(0, m_coefficients[i]);
183   }
184   CBC_PDF417ECModulusPoly* modulusPoly =
185       new CBC_PDF417ECModulusPoly(m_field, negativeCoefficients, e);
186   BC_EXCEPTION_CHECK_ReturnValue(e, NULL);
187   return modulusPoly;
188 }
multiply(int32_t scalar,int32_t & e)189 CBC_PDF417ECModulusPoly* CBC_PDF417ECModulusPoly::multiply(int32_t scalar,
190                                                            int32_t& e) {
191   CBC_PDF417ECModulusPoly* modulusPoly = NULL;
192   if (scalar == 0) {
193     modulusPoly =
194         new CBC_PDF417ECModulusPoly(m_field->getZero()->getField(),
195                                     m_field->getZero()->getCoefficients(), e);
196     BC_EXCEPTION_CHECK_ReturnValue(e, NULL);
197     return modulusPoly;
198   }
199   if (scalar == 1) {
200     modulusPoly = new CBC_PDF417ECModulusPoly(m_field, m_coefficients, e);
201     BC_EXCEPTION_CHECK_ReturnValue(e, NULL);
202     return modulusPoly;
203   }
204   int32_t size = m_coefficients.GetSize();
205   CFX_Int32Array product;
206   product.SetSize(size);
207   for (int32_t i = 0; i < size; i++) {
208     product[i] = m_field->multiply(m_coefficients[i], scalar);
209   }
210   modulusPoly = new CBC_PDF417ECModulusPoly(m_field, product, e);
211   BC_EXCEPTION_CHECK_ReturnValue(e, NULL);
212   return modulusPoly;
213 }
multiplyByMonomial(int32_t degree,int32_t coefficient,int32_t & e)214 CBC_PDF417ECModulusPoly* CBC_PDF417ECModulusPoly::multiplyByMonomial(
215     int32_t degree,
216     int32_t coefficient,
217     int32_t& e) {
218   if (degree < 0) {
219     e = BCExceptionIllegalArgument;
220     return NULL;
221   }
222   CBC_PDF417ECModulusPoly* modulusPoly = NULL;
223   if (coefficient == 0) {
224     modulusPoly = new CBC_PDF417ECModulusPoly(
225         m_field->getZero()->m_field, m_field->getZero()->m_coefficients, e);
226     BC_EXCEPTION_CHECK_ReturnValue(e, NULL);
227     return modulusPoly;
228   }
229   int32_t size = m_coefficients.GetSize();
230   CFX_Int32Array product;
231   product.SetSize(size + degree);
232   for (int32_t i = 0; i < size; i++) {
233     product[i] = m_field->multiply(m_coefficients[i], coefficient);
234   }
235   modulusPoly = new CBC_PDF417ECModulusPoly(m_field, product, e);
236   BC_EXCEPTION_CHECK_ReturnValue(e, NULL);
237   return modulusPoly;
238 }
divide(CBC_PDF417ECModulusPoly * other,int32_t & e)239 CFX_PtrArray* CBC_PDF417ECModulusPoly::divide(CBC_PDF417ECModulusPoly* other,
240                                               int32_t& e) {
241   if (other->isZero()) {
242     e = BCExceptionDivideByZero;
243     return NULL;
244   }
245   CBC_PDF417ECModulusPoly* quotient = new CBC_PDF417ECModulusPoly(
246       m_field->getZero()->m_field, m_field->getZero()->m_coefficients, e);
247   BC_EXCEPTION_CHECK_ReturnValue(e, NULL);
248   CBC_PDF417ECModulusPoly* remainder =
249       new CBC_PDF417ECModulusPoly(m_field, m_coefficients, e);
250   if (e != BCExceptionNO) {
251     delete quotient;
252     return NULL;
253   }
254   int32_t denominatorLeadingTerm = other->getCoefficient(other->getDegree());
255   int32_t inverseDenominatorLeadingTerm =
256       m_field->inverse(denominatorLeadingTerm, e);
257   if (e != BCExceptionNO) {
258     delete quotient;
259     delete remainder;
260     return NULL;
261   }
262   while (remainder->getDegree() >= other->getDegree() && !remainder->isZero()) {
263     int32_t degreeDifference = remainder->getDegree() - other->getDegree();
264     int32_t scale =
265         m_field->multiply(remainder->getCoefficient(remainder->getDegree()),
266                           inverseDenominatorLeadingTerm);
267     CBC_PDF417ECModulusPoly* term =
268         other->multiplyByMonomial(degreeDifference, scale, e);
269     if (e != BCExceptionNO) {
270       delete quotient;
271       delete remainder;
272       return NULL;
273     }
274     CBC_PDF417ECModulusPoly* iterationQuotient =
275         m_field->buildMonomial(degreeDifference, scale, e);
276     if (e != BCExceptionNO) {
277       delete quotient;
278       delete remainder;
279       delete term;
280       return NULL;
281     }
282     CBC_PDF417ECModulusPoly* temp = quotient;
283     quotient = temp->add(iterationQuotient, e);
284     delete iterationQuotient;
285     delete temp;
286     if (e != BCExceptionNO) {
287       delete remainder;
288       return NULL;
289     }
290     temp = remainder;
291     remainder = temp->subtract(term, e);
292     delete term;
293     delete temp;
294     if (e != BCExceptionNO) {
295       delete quotient;
296       return NULL;
297     }
298   }
299   CFX_PtrArray* modulusPoly = new CFX_PtrArray;
300   modulusPoly->Add(quotient);
301   modulusPoly->Add(remainder);
302   return modulusPoly;
303 }
toString()304 CFX_ByteString CBC_PDF417ECModulusPoly::toString() {
305   CFX_ByteString result;
306   for (int32_t degree = getDegree(); degree >= 0; degree--) {
307     int32_t coefficient = getCoefficient(degree);
308     if (coefficient != 0) {
309       if (coefficient < 0) {
310         result += " - ";
311         coefficient = -coefficient;
312       } else {
313         if (result.GetLength() > 0) {
314           result += " + ";
315         }
316       }
317       if (degree == 0 || coefficient != 1) {
318         result += coefficient;
319       }
320       if (degree != 0) {
321         if (degree == 1) {
322           result += 'x';
323         } else {
324           result += "x^";
325           result += degree;
326         }
327       }
328     }
329   }
330   return result;
331 }
332