Merge to XFA: Use stdint.h types throughout PDFium.
[pdfium.git] / xfa / src / fxbarcode / common / reedsolomon / BC_ReedSolomonGF256Poly.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 2007 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_ReedSolomonGF256.h"\r
25 #include "BC_ReedSolomonGF256Poly.h"\r
26 CBC_ReedSolomonGF256Poly::CBC_ReedSolomonGF256Poly(CBC_ReedSolomonGF256* field, int32_t coefficients)\r
27 {\r
28     if(field == NULL) {\r
29         return;\r
30     }\r
31     m_field = field;\r
32     m_coefficients.Add(coefficients);\r
33 }\r
34 CBC_ReedSolomonGF256Poly::CBC_ReedSolomonGF256Poly()\r
35 {\r
36     m_field = NULL;\r
37 }\r
38 void CBC_ReedSolomonGF256Poly::Init(CBC_ReedSolomonGF256* field, CFX_Int32Array* coefficients, int32_t &e)\r
39 {\r
40     if(coefficients == NULL || coefficients->GetSize() == 0) {\r
41         e = BCExceptionCoefficientsSizeIsNull;\r
42         BC_EXCEPTION_CHECK_ReturnVoid(e);\r
43     }\r
44     m_field = field;\r
45     int32_t coefficientsLength = coefficients->GetSize();\r
46     if((coefficientsLength > 1 && (*coefficients)[0] == 0)) {\r
47         int32_t firstNonZero = 1;\r
48         while((firstNonZero < coefficientsLength) && ((*coefficients)[firstNonZero] == 0)) {\r
49             firstNonZero++;\r
50         }\r
51         if(firstNonZero == coefficientsLength) {\r
52             m_coefficients.Copy( *(m_field->GetZero()->GetCoefficients()));\r
53         } else {\r
54             m_coefficients.SetSize(coefficientsLength - firstNonZero);\r
55             for(int32_t i = firstNonZero, j = 0; i < coefficientsLength; i++, j++) {\r
56                 m_coefficients[j] = coefficients->operator [](i);\r
57             }\r
58         }\r
59     } else {\r
60         m_coefficients.Copy(*coefficients);\r
61     }\r
62 }\r
63 CFX_Int32Array* CBC_ReedSolomonGF256Poly::GetCoefficients()\r
64 {\r
65     return &m_coefficients;\r
66 }\r
67 int32_t CBC_ReedSolomonGF256Poly::GetDegree()\r
68 {\r
69     return m_coefficients.GetSize() - 1;\r
70 }\r
71 FX_BOOL CBC_ReedSolomonGF256Poly::IsZero()\r
72 {\r
73     return m_coefficients[0] == 0;\r
74 }\r
75 int32_t CBC_ReedSolomonGF256Poly::GetCoefficients(int32_t degree)\r
76 {\r
77     return m_coefficients[m_coefficients.GetSize() - 1 - degree];\r
78 }\r
79 int32_t CBC_ReedSolomonGF256Poly::EvaluateAt(int32_t a)\r
80 {\r
81     if(a == 0) {\r
82         return GetCoefficients(0);\r
83     }\r
84     int32_t size = m_coefficients.GetSize();\r
85     if(a == 1) {\r
86         int32_t result = 0;\r
87         for(int32_t i = 0; i < size; i++) {\r
88             result = CBC_ReedSolomonGF256::AddOrSubtract(result, m_coefficients[i]);\r
89         }\r
90         return result;\r
91     }\r
92     int32_t result = m_coefficients[0];\r
93     for(int32_t j = 1; j < size; j++) {\r
94         result = CBC_ReedSolomonGF256::AddOrSubtract(\r
95                      m_field->Multiply(a, result),\r
96                      m_coefficients[j]);\r
97     }\r
98     return result;\r
99 }\r
100 CBC_ReedSolomonGF256Poly *CBC_ReedSolomonGF256Poly::Clone(int32_t &e)\r
101 {\r
102     CBC_ReedSolomonGF256Poly *temp  = FX_NEW CBC_ReedSolomonGF256Poly();\r
103     temp->Init(m_field, &m_coefficients, e);\r
104     BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
105     return temp;\r
106 }\r
107 CBC_ReedSolomonGF256Poly* CBC_ReedSolomonGF256Poly::AddOrSubtract(CBC_ReedSolomonGF256Poly* other, int32_t &e)\r
108 {\r
109     if(IsZero()) {\r
110         return other->Clone(e);\r
111         BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
112     }\r
113     if(other->IsZero()) {\r
114         return this->Clone(e);\r
115         BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
116     }\r
117     CFX_Int32Array smallerCoefficients;\r
118     smallerCoefficients.Copy(m_coefficients);\r
119     CFX_Int32Array largerCoefficients;\r
120     largerCoefficients.Copy( *(other->GetCoefficients()));\r
121     if(smallerCoefficients.GetSize() > largerCoefficients.GetSize()) {\r
122         CFX_Int32Array temp;\r
123         temp.Copy(smallerCoefficients);\r
124         smallerCoefficients.Copy(largerCoefficients);\r
125         largerCoefficients.Copy(temp);\r
126     }\r
127     CFX_Int32Array sumDiff;\r
128     sumDiff.SetSize(largerCoefficients.GetSize() );\r
129     int32_t lengthDiff = largerCoefficients.GetSize() - smallerCoefficients.GetSize();\r
130     for(int32_t i = 0; i < lengthDiff; i++) {\r
131         sumDiff[i] = largerCoefficients[i];\r
132     }\r
133     for(int32_t j = lengthDiff; j < largerCoefficients.GetSize(); j++) {\r
134         sumDiff[j] = (CBC_ReedSolomonGF256::AddOrSubtract(smallerCoefficients[j - lengthDiff],\r
135                       largerCoefficients[j]));\r
136     }\r
137     CBC_ReedSolomonGF256Poly *temp = FX_NEW CBC_ReedSolomonGF256Poly();\r
138     temp->Init(m_field, &sumDiff, e);\r
139     BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
140     return temp;\r
141 }\r
142 CBC_ReedSolomonGF256Poly* CBC_ReedSolomonGF256Poly::Multiply(CBC_ReedSolomonGF256Poly* other, int32_t &e)\r
143 {\r
144     if(IsZero() || other->IsZero()) {\r
145         CBC_ReedSolomonGF256Poly *temp = m_field->GetZero()->Clone(e);\r
146         BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
147         return temp;\r
148     }\r
149     CFX_Int32Array aCoefficients ;\r
150     aCoefficients.Copy(m_coefficients);\r
151     int32_t aLength = m_coefficients.GetSize();\r
152     CFX_Int32Array bCoefficients;\r
153     bCoefficients.Copy(*(other->GetCoefficients()));\r
154     int32_t bLength = other->GetCoefficients()->GetSize();\r
155     CFX_Int32Array product;\r
156     product.SetSize(aLength + bLength - 1);\r
157     for(int32_t i = 0; i < aLength; i++) {\r
158         int32_t aCoeff = m_coefficients[i];\r
159         for(int32_t j = 0; j < bLength; j++) {\r
160             product[i + j] = CBC_ReedSolomonGF256::AddOrSubtract(\r
161                                  product[i + j],\r
162                                  m_field->Multiply(aCoeff, other->GetCoefficients()->operator [](j)));\r
163         }\r
164     }\r
165     CBC_ReedSolomonGF256Poly *temp = FX_NEW CBC_ReedSolomonGF256Poly();\r
166     temp->Init(m_field, &product, e);\r
167     BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
168     return temp;\r
169 }\r
170 CBC_ReedSolomonGF256Poly* CBC_ReedSolomonGF256Poly::Multiply(int32_t scalar, int32_t &e)\r
171 {\r
172     if(scalar == 0) {\r
173         CBC_ReedSolomonGF256Poly *temp = m_field->GetZero()->Clone(e);\r
174         BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
175         return temp;\r
176     }\r
177     if(scalar == 1) {\r
178         return this->Clone(e);\r
179         BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
180     }\r
181     int32_t size = m_coefficients.GetSize();\r
182     CFX_Int32Array product;\r
183     product.SetSize(size);\r
184     for(int32_t i = 0; i < size; i++) {\r
185         product[i] = m_field->Multiply(m_coefficients[i], scalar);\r
186     }\r
187     CBC_ReedSolomonGF256Poly *temp = FX_NEW CBC_ReedSolomonGF256Poly();\r
188     temp->Init(m_field, &product, e);\r
189     BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
190     return temp;\r
191 }\r
192 CBC_ReedSolomonGF256Poly* CBC_ReedSolomonGF256Poly::MultiplyByMonomial(int32_t degree, int32_t coefficient, int32_t &e)\r
193 {\r
194     if(degree < 0) {\r
195         e = BCExceptionDegreeIsNegative;\r
196         BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
197     }\r
198     if(coefficient == 0) {\r
199         CBC_ReedSolomonGF256Poly *temp = m_field->GetZero()->Clone(e);\r
200         BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
201         return temp;\r
202     }\r
203     int32_t size = m_coefficients.GetSize();\r
204     CFX_Int32Array product;\r
205     product.SetSize(size + degree);\r
206     for(int32_t i = 0; i < size; i++) {\r
207         product[i] = (m_field->Multiply(m_coefficients[i], coefficient));\r
208     }\r
209     CBC_ReedSolomonGF256Poly *temp = FX_NEW CBC_ReedSolomonGF256Poly();\r
210     temp->Init(m_field, &product, e);\r
211     BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
212     return temp;\r
213 }\r
214 CFX_PtrArray* CBC_ReedSolomonGF256Poly::Divide(CBC_ReedSolomonGF256Poly *other, int32_t &e)\r
215 {\r
216     if(other->IsZero()) {\r
217         e = BCExceptionDivideByZero;\r
218         BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
219     }\r
220     CBC_ReedSolomonGF256Poly* rsg1 = m_field->GetZero()->Clone(e);\r
221     BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
222     CBC_AutoPtr<CBC_ReedSolomonGF256Poly> quotient(rsg1);\r
223     CBC_ReedSolomonGF256Poly* rsg2 = this->Clone(e);\r
224     BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
225     CBC_AutoPtr<CBC_ReedSolomonGF256Poly> remainder(rsg2);\r
226     int32_t denominatorLeadingTerm = other->GetCoefficients(other->GetDegree());\r
227     int32_t inverseDenominatorLeadingTeam = m_field->Inverse(denominatorLeadingTerm, e);\r
228     BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
229     FX_BOOL bFirst = TRUE;\r
230     while(remainder->GetDegree() >= other->GetDegree() && !remainder->IsZero()) {\r
231         int32_t degreeDifference = remainder->GetDegree() - other->GetDegree();\r
232         int32_t scale = m_field->Multiply(remainder->GetCoefficients((remainder->GetDegree())),\r
233                                            inverseDenominatorLeadingTeam);\r
234         CBC_ReedSolomonGF256Poly* rsg3 = other->MultiplyByMonomial(degreeDifference, scale, e);\r
235         BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
236         CBC_AutoPtr<CBC_ReedSolomonGF256Poly> term(rsg3);\r
237         CBC_ReedSolomonGF256Poly* rsg4 = m_field->BuildMonomial(degreeDifference, scale, e);\r
238         BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
239         CBC_AutoPtr<CBC_ReedSolomonGF256Poly> iteratorQuotient(rsg4);\r
240         CBC_ReedSolomonGF256Poly* rsg5 = quotient->AddOrSubtract(iteratorQuotient.get(), e);\r
241         BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
242         CBC_AutoPtr<CBC_ReedSolomonGF256Poly> temp(rsg5);\r
243         quotient = temp;\r
244         CBC_ReedSolomonGF256Poly* rsg6 = remainder->AddOrSubtract(term.get(), e);\r
245         BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
246         CBC_AutoPtr<CBC_ReedSolomonGF256Poly> temp1(rsg6);\r
247         remainder = temp1;\r
248     }\r
249     CFX_PtrArray* tempPtrA = FX_NEW CFX_PtrArray;\r
250     tempPtrA->Add(quotient.release());\r
251     tempPtrA->Add(remainder.release());\r
252     return tempPtrA;\r
253 }\r
254 CBC_ReedSolomonGF256Poly::~CBC_ReedSolomonGF256Poly()\r
255 {\r
256     m_coefficients.RemoveAll();\r
257 }\r