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"
27CBC_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}
56CBC_PDF417ECModulusPoly::~CBC_PDF417ECModulusPoly() {}
57CFX_Int32Array& CBC_PDF417ECModulusPoly::getCoefficients() {
58  return m_coefficients;
59}
60CBC_PDF417ECModulusGF* CBC_PDF417ECModulusPoly::getField() {
61  return m_field;
62}
63int32_t CBC_PDF417ECModulusPoly::getDegree() {
64  return m_coefficients.GetSize() - 1;
65}
66FX_BOOL CBC_PDF417ECModulusPoly::isZero() {
67  return m_coefficients[0] == 0;
68}
69int32_t CBC_PDF417ECModulusPoly::getCoefficient(int32_t degree) {
70  return m_coefficients[m_coefficients.GetSize() - 1 - degree];
71}
72int32_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}
91CBC_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}
131CBC_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}
147CBC_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}
177CBC_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}
189CBC_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}
214CBC_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}
239CFX_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}
304CFX_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