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"
26CBC_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}
34CBC_ReedSolomonGF256Poly::CBC_ReedSolomonGF256Poly() {
35  m_field = NULL;
36}
37void 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}
64CFX_Int32Array* CBC_ReedSolomonGF256Poly::GetCoefficients() {
65  return &m_coefficients;
66}
67int32_t CBC_ReedSolomonGF256Poly::GetDegree() {
68  return m_coefficients.GetSize() - 1;
69}
70FX_BOOL CBC_ReedSolomonGF256Poly::IsZero() {
71  return m_coefficients[0] == 0;
72}
73int32_t CBC_ReedSolomonGF256Poly::GetCoefficients(int32_t degree) {
74  return m_coefficients[m_coefficients.GetSize() - 1 - degree];
75}
76int32_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}
95CBC_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}
101CBC_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}
138CBC_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}
167CBC_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}
189CBC_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}
213CFX_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}
257CBC_ReedSolomonGF256Poly::~CBC_ReedSolomonGF256Poly() {
258  m_coefficients.RemoveAll();
259}
260