Merge XFA to PDFium master at 4dc95e7 on 10/28/2014
[pdfium.git] / xfa / src / fxbarcode / src / BC_PDF417ECErrorCorrection.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_PDF417ECModulusPoly.h"\r
10 #include "include/BC_PDF417ECModulusGF.h"\r
11 #include "include/BC_PDF417ECErrorCorrection.h"\r
12 CBC_PDF417ECModulusGF* CBC_PDF417ECErrorCorrection::m_field = NULL;\r
13 void CBC_PDF417ECErrorCorrection::Initialize(FX_INT32 &e)\r
14 {\r
15     m_field = FX_NEW CBC_PDF417ECModulusGF(CBC_PDF417Common::NUMBER_OF_CODEWORDS, 3, e);\r
16 }\r
17 void CBC_PDF417ECErrorCorrection::Finalize()\r
18 {\r
19     delete m_field;\r
20 }\r
21 CBC_PDF417ECErrorCorrection::CBC_PDF417ECErrorCorrection()\r
22 {\r
23 }\r
24 CBC_PDF417ECErrorCorrection::~CBC_PDF417ECErrorCorrection()\r
25 {\r
26 }\r
27 FX_INT32 CBC_PDF417ECErrorCorrection::decode(CFX_Int32Array &received, FX_INT32 numECCodewords, CFX_Int32Array &erasures, FX_INT32 &e)\r
28 {\r
29     CBC_PDF417ECModulusPoly poly(m_field, received, e);\r
30     BC_EXCEPTION_CHECK_ReturnValue(e, -1);\r
31     CFX_Int32Array S;\r
32     S.SetSize(numECCodewords);\r
33     FX_BOOL error = FALSE;\r
34     for (FX_INT32 l = numECCodewords; l > 0; l--) {\r
35         FX_INT32 eval = poly.evaluateAt(m_field->exp(l));\r
36         S[numECCodewords - l] = eval;\r
37         if (eval != 0) {\r
38             error = TRUE;\r
39         }\r
40     }\r
41     if (!error) {\r
42         return 0;\r
43     }\r
44     CBC_PDF417ECModulusPoly* syndrome = FX_NEW CBC_PDF417ECModulusPoly(m_field, S, e);\r
45     BC_EXCEPTION_CHECK_ReturnValue(e, -1);\r
46     CBC_PDF417ECModulusPoly* buildmonomial = m_field->buildMonomial(numECCodewords, 1, e);\r
47     if (e != BCExceptionNO) {\r
48         delete syndrome;\r
49         return -1;\r
50     }\r
51     CFX_PtrArray* sigmaOmega = runEuclideanAlgorithm(buildmonomial, syndrome, numECCodewords, e);\r
52     delete buildmonomial;\r
53     delete syndrome;\r
54     BC_EXCEPTION_CHECK_ReturnValue(e, -1);\r
55     CBC_PDF417ECModulusPoly* sigma = (CBC_PDF417ECModulusPoly*)sigmaOmega->GetAt(0);\r
56     CBC_PDF417ECModulusPoly* omega = (CBC_PDF417ECModulusPoly*)sigmaOmega->GetAt(1);\r
57     CFX_Int32Array* errorLocations = findErrorLocations(sigma, e);\r
58     if (e != BCExceptionNO) {\r
59         for (FX_INT32 i = 0; i < sigmaOmega->GetSize(); i++) {\r
60             delete (CBC_PDF417ECModulusPoly*)sigmaOmega->GetAt(i);\r
61         }\r
62         sigmaOmega->RemoveAll();\r
63         delete sigmaOmega;\r
64         return -1;\r
65     }\r
66     CFX_Int32Array* errorMagnitudes = findErrorMagnitudes(omega, sigma, *errorLocations, e);\r
67     if (e != BCExceptionNO) {\r
68         delete errorLocations;\r
69         for (FX_INT32 i = 0; i < sigmaOmega->GetSize(); i++) {\r
70             delete (CBC_PDF417ECModulusPoly*)sigmaOmega->GetAt(i);\r
71         }\r
72         sigmaOmega->RemoveAll();\r
73         delete sigmaOmega;\r
74         return -1;\r
75     }\r
76     for (FX_INT32 i = 0; i < errorLocations->GetSize(); i++) {\r
77         FX_INT32 log = m_field->log(errorLocations->GetAt(i), e);;\r
78         BC_EXCEPTION_CHECK_ReturnValue(e, -1);\r
79         FX_INT32 position = received.GetSize() - 1 - log;\r
80         if (position < 0) {\r
81             e = BCExceptionChecksumException;\r
82             delete errorLocations;\r
83             delete errorMagnitudes;\r
84             for (FX_INT32 j = 0; j < sigmaOmega->GetSize(); j++) {\r
85                 delete (CBC_PDF417ECModulusPoly*)sigmaOmega->GetAt(j);\r
86             }\r
87             sigmaOmega->RemoveAll();\r
88             delete sigmaOmega;\r
89             return -1;\r
90         }\r
91         received[position] = m_field->subtract(received[position], errorMagnitudes->GetAt(i));\r
92     }\r
93     FX_INT32 result = errorLocations->GetSize();\r
94     delete errorLocations;\r
95     delete errorMagnitudes;\r
96     for (FX_INT32 k = 0; k < sigmaOmega->GetSize(); k++) {\r
97         delete (CBC_PDF417ECModulusPoly*)sigmaOmega->GetAt(k);\r
98     }\r
99     sigmaOmega->RemoveAll();\r
100     delete sigmaOmega;\r
101     return result;\r
102 }\r
103 CFX_PtrArray* CBC_PDF417ECErrorCorrection::runEuclideanAlgorithm(CBC_PDF417ECModulusPoly* a, CBC_PDF417ECModulusPoly* b, FX_INT32 R, FX_INT32 &e)\r
104 {\r
105     if (a->getDegree() < b->getDegree()) {\r
106         CBC_PDF417ECModulusPoly* temp = a;\r
107         a = b;\r
108         b = temp;\r
109     }\r
110     CBC_PDF417ECModulusPoly* rLast = a;\r
111     CBC_PDF417ECModulusPoly* r = b;\r
112     CBC_PDF417ECModulusPoly* tLast = m_field->getZero();\r
113     CBC_PDF417ECModulusPoly* t = m_field->getOne();\r
114     CBC_PDF417ECModulusPoly* qtemp = NULL;\r
115     CBC_PDF417ECModulusPoly* rtemp = NULL;\r
116     CBC_PDF417ECModulusPoly* ttemp = NULL;\r
117     FX_INT32 i = 0;\r
118     FX_INT32 j = 0;\r
119     FX_INT32 m = 0;\r
120     FX_INT32 n = 0;\r
121     while (r->getDegree() >= R / 2) {\r
122         CBC_PDF417ECModulusPoly* rLastLast = rLast;\r
123         CBC_PDF417ECModulusPoly* tLastLast = tLast;\r
124         rLast = r;\r
125         tLast = t;\r
126         m = i;\r
127         n = j;\r
128         if (rLast->isZero()) {\r
129             e = BCExceptionChecksumException;\r
130             if (qtemp) {\r
131                 delete qtemp;\r
132             }\r
133             if (rtemp) {\r
134                 delete rtemp;\r
135             }\r
136             if (ttemp) {\r
137                 delete ttemp;\r
138             }\r
139             return NULL;\r
140         }\r
141         r = rLastLast;\r
142         CBC_PDF417ECModulusPoly* q = m_field->getZero();\r
143         FX_INT32 denominatorLeadingTerm = rLast->getCoefficient(rLast->getDegree());\r
144         FX_INT32 dltInverse = m_field->inverse(denominatorLeadingTerm, e);\r
145         if (e != BCExceptionNO) {\r
146             if (qtemp) {\r
147                 delete qtemp;\r
148             }\r
149             if (rtemp) {\r
150                 delete rtemp;\r
151             }\r
152             if (ttemp) {\r
153                 delete ttemp;\r
154             }\r
155             return NULL;\r
156         }\r
157         while (r->getDegree() >= rLast->getDegree() && !r->isZero()) {\r
158             FX_INT32 degreeDiff = r->getDegree() - rLast->getDegree();\r
159             FX_INT32 scale = m_field->multiply(r->getCoefficient(r->getDegree()), dltInverse);\r
160             CBC_PDF417ECModulusPoly* buildmonomial = m_field->buildMonomial(degreeDiff, scale, e);\r
161             if (e != BCExceptionNO) {\r
162                 if (qtemp) {\r
163                     delete qtemp;\r
164                 }\r
165                 if (rtemp) {\r
166                     delete rtemp;\r
167                 }\r
168                 if (ttemp) {\r
169                     delete ttemp;\r
170                 }\r
171                 return NULL;\r
172             }\r
173             q = q->add(buildmonomial, e);\r
174             delete buildmonomial;\r
175             if (qtemp) {\r
176                 delete qtemp;\r
177             }\r
178             if (e != BCExceptionNO) {\r
179                 if (rtemp) {\r
180                     delete rtemp;\r
181                 }\r
182                 if (ttemp) {\r
183                     delete ttemp;\r
184                 }\r
185                 return NULL;\r
186             }\r
187             qtemp = q;\r
188             CBC_PDF417ECModulusPoly* multiply  = rLast->multiplyByMonomial(degreeDiff, scale, e);\r
189             if (e != BCExceptionNO) {\r
190                 if (qtemp) {\r
191                     delete qtemp;\r
192                 }\r
193                 if (rtemp) {\r
194                     delete rtemp;\r
195                 }\r
196                 if (ttemp) {\r
197                     delete ttemp;\r
198                 }\r
199                 return NULL;\r
200             }\r
201             CBC_PDF417ECModulusPoly* temp = r;\r
202             r = temp->subtract(multiply, e);\r
203             delete multiply;\r
204             if (m > 1 && i > m) {\r
205                 delete temp;\r
206                 temp = NULL;\r
207             }\r
208             if (e != BCExceptionNO) {\r
209                 if (qtemp) {\r
210                     delete qtemp;\r
211                 }\r
212                 if (rtemp) {\r
213                     delete rtemp;\r
214                 }\r
215                 if (ttemp) {\r
216                     delete ttemp;\r
217                 }\r
218                 return NULL;\r
219             }\r
220             rtemp = r;\r
221             i = m + 1;\r
222         }\r
223         ttemp = q->multiply(tLast, e);\r
224         if (qtemp) {\r
225             delete qtemp;\r
226             qtemp = NULL;\r
227         }\r
228         if (e != BCExceptionNO) {\r
229             if (rtemp) {\r
230                 delete rtemp;\r
231             }\r
232             if (ttemp) {\r
233                 delete ttemp;\r
234             }\r
235             return NULL;\r
236         }\r
237         t = ttemp->subtract(tLastLast, e);\r
238         if (n > 1 && j > n) {\r
239             delete tLastLast;\r
240         }\r
241         delete ttemp;\r
242         if (e != BCExceptionNO) {\r
243             if (rtemp) {\r
244                 delete rtemp;\r
245             }\r
246             return NULL;\r
247         }\r
248         ttemp = t;\r
249         t = ttemp->negative(e);\r
250         delete ttemp;\r
251         if (e != BCExceptionNO) {\r
252             if (rtemp) {\r
253                 delete rtemp;\r
254             }\r
255             return NULL;\r
256         }\r
257         ttemp = t;\r
258         j++;\r
259     }\r
260     FX_INT32 aa = t->getCoefficient(1);\r
261     FX_INT32 sigmaTildeAtZero = t->getCoefficient(0);\r
262     if (sigmaTildeAtZero == 0) {\r
263         e = BCExceptionChecksumException;\r
264         if (rtemp) {\r
265             delete rtemp;\r
266         }\r
267         if (ttemp) {\r
268             delete ttemp;\r
269         }\r
270         return NULL;\r
271     }\r
272     FX_INT32 inverse = m_field->inverse(sigmaTildeAtZero, e);\r
273     if (e != BCExceptionNO) {\r
274         if (rtemp) {\r
275             delete rtemp;\r
276         }\r
277         if (ttemp) {\r
278             delete ttemp;\r
279         }\r
280         return NULL;\r
281     }\r
282     CBC_PDF417ECModulusPoly* sigma = t->multiply(inverse, e);\r
283     if (ttemp) {\r
284         delete ttemp;\r
285     }\r
286     if (e != BCExceptionNO) {\r
287         if (rtemp) {\r
288             delete rtemp;\r
289         }\r
290         return NULL;\r
291     }\r
292     CBC_PDF417ECModulusPoly* omega = r->multiply(inverse, e);\r
293     if (rtemp) {\r
294         delete rtemp;\r
295     }\r
296     BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
297     CFX_PtrArray* modulusPoly = FX_NEW CFX_PtrArray;\r
298     modulusPoly->Add(sigma);\r
299     modulusPoly->Add(omega);\r
300     return modulusPoly;\r
301 }\r
302 CFX_Int32Array* CBC_PDF417ECErrorCorrection::findErrorLocations(CBC_PDF417ECModulusPoly* errorLocator, FX_INT32 &e)\r
303 {\r
304     FX_INT32 numErrors = errorLocator->getDegree();\r
305     CFX_Int32Array* result = FX_NEW CFX_Int32Array;\r
306     result->SetSize(numErrors);\r
307     FX_INT32 ee = 0;\r
308     for (FX_INT32 i = 1; i < m_field->getSize() && ee < numErrors; i++) {\r
309         if (errorLocator->evaluateAt(i) == 0) {\r
310             result->SetAt(ee, m_field->inverse(i, e));\r
311             if (e != BCExceptionNO) {\r
312                 delete result;\r
313                 return NULL;\r
314             }\r
315             ee++;\r
316         }\r
317     }\r
318     if (ee != numErrors) {\r
319         e = BCExceptionChecksumException;\r
320         delete result;\r
321         return NULL;\r
322     }\r
323     return result;\r
324 }\r
325 CFX_Int32Array* CBC_PDF417ECErrorCorrection::findErrorMagnitudes(CBC_PDF417ECModulusPoly* errorEvaluator, CBC_PDF417ECModulusPoly* errorLocator, CFX_Int32Array &errorLocations, FX_INT32 &e)\r
326 {\r
327     FX_INT32 errorLocatorDegree = errorLocator->getDegree();\r
328     CFX_Int32Array formalDerivativeCoefficients;\r
329     formalDerivativeCoefficients.SetSize(errorLocatorDegree);\r
330     for (FX_INT32 l = 1; l <= errorLocatorDegree; l++) {\r
331         formalDerivativeCoefficients[errorLocatorDegree - l] = m_field->multiply(l, errorLocator->getCoefficient(l));\r
332     }\r
333     CBC_PDF417ECModulusPoly formalDerivative(m_field, formalDerivativeCoefficients, e);\r
334     BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
335     FX_INT32 s = errorLocations.GetSize();\r
336     CFX_Int32Array* result = FX_NEW CFX_Int32Array;\r
337     result->SetSize(s);\r
338     for (FX_INT32 i = 0; i < s; i++) {\r
339         FX_INT32 xiInverse = m_field->inverse(errorLocations[i], e);\r
340         if (e != BCExceptionNO) {\r
341             delete result;\r
342             return NULL;\r
343         }\r
344         FX_INT32 numerator = m_field->subtract(0, errorEvaluator->evaluateAt(xiInverse));\r
345         FX_INT32 denominator = m_field->inverse(formalDerivative.evaluateAt(xiInverse), e);\r
346         if (e != BCExceptionNO) {\r
347             delete result;\r
348             return NULL;\r
349         }\r
350         result->SetAt(i, m_field->multiply(numerator, denominator));\r
351     }\r
352     return result;\r
353 }\r