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