Organize barcode codes into modules.
[pdfium.git] / xfa / src / fxbarcode / pdf417 / BC_PDF417ECModulusPoly.cpp
1 // Copyright 2014 PDFium Authors. All rights reserved.\r
2 // Use of this source code is governed by a BSD-style license that can be\r
3 // found in the LICENSE file.\r
4 \r
5 // Original code copyright 2014 Foxit Software Inc. http://www.foxitsoftware.com\r
6 // Original code is licensed as follows:\r
7 /*\r
8  * Copyright 2012 ZXing authors\r
9  *\r
10  * Licensed under the Apache License, Version 2.0 (the "License");\r
11  * you may not use this file except in compliance with the License.\r
12  * You may obtain a copy of the License at\r
13  *\r
14  *      http://www.apache.org/licenses/LICENSE-2.0\r
15  *\r
16  * Unless required by applicable law or agreed to in writing, software\r
17  * distributed under the License is distributed on an "AS IS" BASIS,\r
18  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\r
19  * See the License for the specific language governing permissions and\r
20  * limitations under the License.\r
21  */\r
22 \r
23 #include "../barcode.h"\r
24 #include "BC_PDF417Common.h"\r
25 #include "BC_PDF417ECModulusGF.h"\r
26 #include "BC_PDF417ECModulusPoly.h"\r
27 CBC_PDF417ECModulusPoly::CBC_PDF417ECModulusPoly(CBC_PDF417ECModulusGF* field, CFX_Int32Array &coefficients, FX_INT32 &e)\r
28 {\r
29     if (coefficients.GetSize() == 0) {\r
30         e = BCExceptionIllegalArgument;\r
31     }\r
32     m_field = field;\r
33     FX_INT32 coefficientsLength = coefficients.GetSize();\r
34     if (coefficientsLength > 1 && coefficients[0] == 0) {\r
35         FX_INT32 firstNonZero = 1;\r
36         while (firstNonZero < coefficientsLength && coefficients[firstNonZero] == 0) {\r
37             firstNonZero++;\r
38         }\r
39         if (firstNonZero == coefficientsLength) {\r
40             m_coefficients = field->getZero()->m_coefficients;\r
41         } else {\r
42             m_coefficients.SetSize(coefficientsLength - firstNonZero);\r
43             FX_INT32 l = 0;\r
44             for (FX_INT32 i = firstNonZero; i < firstNonZero + m_coefficients.GetSize(); i++) {\r
45                 m_coefficients.SetAt(l, coefficients.GetAt(i));\r
46                 l++;\r
47             }\r
48         }\r
49     } else {\r
50         m_coefficients.Copy(coefficients);\r
51     }\r
52 }\r
53 CBC_PDF417ECModulusPoly::~CBC_PDF417ECModulusPoly()\r
54 {\r
55 }\r
56 CFX_Int32Array& CBC_PDF417ECModulusPoly::getCoefficients()\r
57 {\r
58     return m_coefficients;\r
59 }\r
60 CBC_PDF417ECModulusGF* CBC_PDF417ECModulusPoly::getField()\r
61 {\r
62     return m_field;\r
63 }\r
64 FX_INT32 CBC_PDF417ECModulusPoly::getDegree()\r
65 {\r
66     return m_coefficients.GetSize() - 1;\r
67 }\r
68 FX_BOOL CBC_PDF417ECModulusPoly::isZero()\r
69 {\r
70     return m_coefficients[0] == 0;\r
71 }\r
72 FX_INT32 CBC_PDF417ECModulusPoly::getCoefficient(FX_INT32 degree)\r
73 {\r
74     return m_coefficients[m_coefficients.GetSize() - 1 - degree];\r
75 }\r
76 FX_INT32 CBC_PDF417ECModulusPoly::evaluateAt(FX_INT32 a)\r
77 {\r
78     if (a == 0) {\r
79         return getCoefficient(0);\r
80     }\r
81     FX_INT32 size = m_coefficients.GetSize();\r
82     if (a == 1) {\r
83         FX_INT32 result = 0;\r
84         for (FX_INT32 l = 0; l < m_coefficients.GetSize(); l++) {\r
85             FX_INT32 coefficient = m_coefficients.GetAt(l);\r
86             result = m_field->add(result, coefficient);\r
87         }\r
88         return result;\r
89     }\r
90     FX_INT32 result = m_coefficients[0];\r
91     for (FX_INT32 i = 1; i < size; i++) {\r
92         result = m_field->add(m_field->multiply(a, result), m_coefficients[i]);\r
93     }\r
94     return result;\r
95 }\r
96 CBC_PDF417ECModulusPoly* CBC_PDF417ECModulusPoly::add(CBC_PDF417ECModulusPoly* other, FX_INT32 &e)\r
97 {\r
98     CBC_PDF417ECModulusPoly* modulusPoly = NULL;\r
99     if (isZero()) {\r
100         modulusPoly = FX_NEW CBC_PDF417ECModulusPoly(other->getField(), other->getCoefficients(), e);\r
101         BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
102         return modulusPoly;\r
103     }\r
104     if (other->isZero()) {\r
105         modulusPoly = FX_NEW CBC_PDF417ECModulusPoly(m_field, m_coefficients, e);\r
106         BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
107         return modulusPoly;\r
108     }\r
109     CFX_Int32Array smallerCoefficients;\r
110     smallerCoefficients.Copy(m_coefficients);\r
111     CFX_Int32Array largerCoefficients;\r
112     largerCoefficients.Copy(other->m_coefficients);\r
113     if (smallerCoefficients.GetSize() > largerCoefficients.GetSize()) {\r
114         CFX_Int32Array temp;\r
115         temp.Copy(smallerCoefficients);\r
116         smallerCoefficients.Copy(largerCoefficients);\r
117         largerCoefficients.Copy(temp);\r
118     }\r
119     CFX_Int32Array sumDiff;\r
120     sumDiff.SetSize(largerCoefficients.GetSize());\r
121     FX_INT32 lengthDiff = largerCoefficients.GetSize() - smallerCoefficients.GetSize();\r
122     for (FX_INT32 l = 0; l < lengthDiff; l++) {\r
123         sumDiff.SetAt(l, largerCoefficients.GetAt(l));\r
124     }\r
125     for (FX_INT32 i = lengthDiff; i < largerCoefficients.GetSize(); i++) {\r
126         sumDiff[i] = m_field->add(smallerCoefficients[i - lengthDiff], largerCoefficients[i]);\r
127     }\r
128     modulusPoly = FX_NEW CBC_PDF417ECModulusPoly(m_field, sumDiff, e);\r
129     BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
130     return modulusPoly;\r
131 }\r
132 CBC_PDF417ECModulusPoly* CBC_PDF417ECModulusPoly::subtract(CBC_PDF417ECModulusPoly* other, FX_INT32 &e)\r
133 {\r
134     CBC_PDF417ECModulusPoly* modulusPoly = NULL;\r
135     if (other->isZero()) {\r
136         modulusPoly = FX_NEW CBC_PDF417ECModulusPoly(m_field, m_coefficients, e);\r
137         BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
138         return modulusPoly;\r
139     }\r
140     CBC_PDF417ECModulusPoly* poly  = other->negative(e);\r
141     BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
142     modulusPoly = add(poly, e);\r
143     delete poly;\r
144     BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
145     return modulusPoly;\r
146 }\r
147 CBC_PDF417ECModulusPoly* CBC_PDF417ECModulusPoly::multiply(CBC_PDF417ECModulusPoly* other, FX_INT32 &e)\r
148 {\r
149     CBC_PDF417ECModulusPoly* modulusPoly = NULL;\r
150     if (isZero() || other->isZero()) {\r
151         modulusPoly = FX_NEW CBC_PDF417ECModulusPoly(m_field->getZero()->getField(), m_field->getZero()->getCoefficients(), e);\r
152         BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
153         return modulusPoly;\r
154     }\r
155     CFX_Int32Array aCoefficients;\r
156     aCoefficients.Copy(m_coefficients);\r
157     FX_INT32 aLength = aCoefficients.GetSize();\r
158     CFX_Int32Array bCoefficients;\r
159     bCoefficients.Copy(other->m_coefficients);\r
160     FX_INT32 bLength = bCoefficients.GetSize();\r
161     CFX_Int32Array product;\r
162     product.SetSize(aLength + bLength - 1);\r
163     for (FX_INT32 i = 0; i < aLength; i++) {\r
164         FX_INT32 aCoeff = aCoefficients[i];\r
165         for (FX_INT32 j = 0; j < bLength; j++) {\r
166             product[i + j] = m_field->add(product[i + j], m_field->multiply(aCoeff, bCoefficients[j]));\r
167         }\r
168     }\r
169     modulusPoly = FX_NEW CBC_PDF417ECModulusPoly(m_field, product, e);\r
170     BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
171     return modulusPoly;\r
172 }\r
173 CBC_PDF417ECModulusPoly* CBC_PDF417ECModulusPoly::negative(FX_INT32 &e)\r
174 {\r
175     FX_INT32 size = m_coefficients.GetSize();\r
176     CFX_Int32Array negativeCoefficients;\r
177     negativeCoefficients.SetSize(size);\r
178     for (FX_INT32 i = 0; i < size; i++) {\r
179         negativeCoefficients[i] = m_field->subtract(0, m_coefficients[i]);\r
180     }\r
181     CBC_PDF417ECModulusPoly* modulusPoly = FX_NEW CBC_PDF417ECModulusPoly(m_field, negativeCoefficients, e);\r
182     BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
183     return modulusPoly;\r
184 }\r
185 CBC_PDF417ECModulusPoly* CBC_PDF417ECModulusPoly::multiply(FX_INT32 scalar, FX_INT32 &e)\r
186 {\r
187     CBC_PDF417ECModulusPoly* modulusPoly = NULL;\r
188     if (scalar == 0) {\r
189         modulusPoly = FX_NEW CBC_PDF417ECModulusPoly(m_field->getZero()->getField(), m_field->getZero()->getCoefficients(), e);\r
190         BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
191         return modulusPoly;\r
192     }\r
193     if (scalar == 1) {\r
194         modulusPoly = FX_NEW CBC_PDF417ECModulusPoly(m_field, m_coefficients, e);\r
195         BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
196         return modulusPoly;\r
197     }\r
198     FX_INT32 size = m_coefficients.GetSize();\r
199     CFX_Int32Array product;\r
200     product.SetSize(size);\r
201     for (FX_INT32 i = 0; i < size; i++) {\r
202         product[i] = m_field->multiply(m_coefficients[i], scalar);\r
203     }\r
204     modulusPoly = FX_NEW CBC_PDF417ECModulusPoly(m_field, product, e);\r
205     BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
206     return modulusPoly;\r
207 }\r
208 CBC_PDF417ECModulusPoly* CBC_PDF417ECModulusPoly::multiplyByMonomial(FX_INT32 degree, FX_INT32 coefficient, FX_INT32 &e)\r
209 {\r
210     if (degree < 0) {\r
211         e = BCExceptionIllegalArgument;\r
212         return NULL;\r
213     }\r
214     CBC_PDF417ECModulusPoly* modulusPoly = NULL;\r
215     if (coefficient == 0) {\r
216         modulusPoly = FX_NEW CBC_PDF417ECModulusPoly(m_field->getZero()->m_field, m_field->getZero()->m_coefficients, e);\r
217         BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
218         return modulusPoly;\r
219     }\r
220     FX_INT32 size = m_coefficients.GetSize();\r
221     CFX_Int32Array product;\r
222     product.SetSize(size + degree);\r
223     for (FX_INT32 i = 0; i < size; i++) {\r
224         product[i] = m_field->multiply(m_coefficients[i], coefficient);\r
225     }\r
226     modulusPoly = FX_NEW CBC_PDF417ECModulusPoly(m_field, product, e);\r
227     BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
228     return modulusPoly;\r
229 }\r
230 CFX_PtrArray* CBC_PDF417ECModulusPoly::divide(CBC_PDF417ECModulusPoly* other, FX_INT32 &e)\r
231 {\r
232     if (other->isZero()) {\r
233         e = BCExceptionDivideByZero;\r
234         return NULL;\r
235     }\r
236     CBC_PDF417ECModulusPoly* quotient = FX_NEW CBC_PDF417ECModulusPoly(m_field->getZero()->m_field, m_field->getZero()->m_coefficients, e);\r
237     BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
238     CBC_PDF417ECModulusPoly* remainder = FX_NEW CBC_PDF417ECModulusPoly(m_field, m_coefficients, e);\r
239     if (e != BCExceptionNO) {\r
240         delete quotient;\r
241         return NULL;\r
242     }\r
243     FX_INT32 denominatorLeadingTerm = other->getCoefficient(other->getDegree());\r
244     FX_INT32 inverseDenominatorLeadingTerm = m_field->inverse(denominatorLeadingTerm, e);\r
245     if (e != BCExceptionNO) {\r
246         delete quotient;\r
247         delete remainder;\r
248         return NULL;\r
249     }\r
250     while (remainder->getDegree() >= other->getDegree() && !remainder->isZero()) {\r
251         FX_INT32 degreeDifference = remainder->getDegree() - other->getDegree();\r
252         FX_INT32 scale = m_field->multiply(remainder->getCoefficient(remainder->getDegree()), inverseDenominatorLeadingTerm);\r
253         CBC_PDF417ECModulusPoly* term = other->multiplyByMonomial(degreeDifference, scale, e);\r
254         if (e != BCExceptionNO) {\r
255             delete quotient;\r
256             delete remainder;\r
257             return NULL;\r
258         }\r
259         CBC_PDF417ECModulusPoly* iterationQuotient = m_field->buildMonomial(degreeDifference, scale, e);\r
260         if (e != BCExceptionNO) {\r
261             delete quotient;\r
262             delete remainder;\r
263             delete term;\r
264             return NULL;\r
265         }\r
266         CBC_PDF417ECModulusPoly* temp = quotient;\r
267         quotient = temp->add(iterationQuotient, e);\r
268         delete iterationQuotient;\r
269         delete temp;\r
270         if (e != BCExceptionNO) {\r
271             delete remainder;\r
272             return NULL;\r
273         }\r
274         temp = remainder;\r
275         remainder = temp->subtract(term, e);\r
276         delete term;\r
277         delete temp;\r
278         if (e != BCExceptionNO) {\r
279             delete quotient;\r
280             return NULL;\r
281         }\r
282     }\r
283     CFX_PtrArray* modulusPoly = FX_NEW CFX_PtrArray;\r
284     modulusPoly->Add(quotient);\r
285     modulusPoly->Add(remainder);\r
286     return modulusPoly;\r
287 }\r
288 CFX_ByteString CBC_PDF417ECModulusPoly::toString()\r
289 {\r
290     CFX_ByteString result;\r
291     for (FX_INT32 degree = getDegree(); degree >= 0; degree--) {\r
292         FX_INT32 coefficient = getCoefficient(degree);\r
293         if (coefficient != 0) {\r
294             if (coefficient < 0) {\r
295                 result += " - ";\r
296                 coefficient = -coefficient;\r
297             } else {\r
298                 if (result.GetLength() > 0) {\r
299                     result += " + ";\r
300                 }\r
301             }\r
302             if (degree == 0 || coefficient != 1) {\r
303                 result += coefficient;\r
304             }\r
305             if (degree != 0) {\r
306                 if (degree == 1) {\r
307                     result += 'x';\r
308                 } else {\r
309                     result += "x^";\r
310                     result += degree;\r
311                 }\r
312             }\r
313         }\r
314     }\r
315     return result;\r
316 }\r