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