1 // Copyright 2014 PDFium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4 
5 // Original code copyright 2014 Foxit Software Inc. http://www.foxitsoftware.com
6 // Original code is licensed as follows:
7 /*
8  * Copyright 2012 ZXing authors
9  *
10  * Licensed under the Apache License, Version 2.0 (the "License");
11  * you may not use this file except in compliance with the License.
12  * You may obtain a copy of the License at
13  *
14  *      http://www.apache.org/licenses/LICENSE-2.0
15  *
16  * Unless required by applicable law or agreed to in writing, software
17  * distributed under the License is distributed on an "AS IS" BASIS,
18  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
19  * See the License for the specific language governing permissions and
20  * limitations under the License.
21  */
22 
23 #include "xfa/src/fxbarcode/barcode.h"
24 #include "BC_PDF417Common.h"
25 #include "BC_PDF417ECModulusPoly.h"
26 #include "BC_PDF417ECModulusGF.h"
27 #include "BC_PDF417ECErrorCorrection.h"
28 CBC_PDF417ECModulusGF* CBC_PDF417ECErrorCorrection::m_field = NULL;
Initialize(int32_t & e)29 void CBC_PDF417ECErrorCorrection::Initialize(int32_t& e) {
30   m_field =
31       new CBC_PDF417ECModulusGF(CBC_PDF417Common::NUMBER_OF_CODEWORDS, 3, e);
32 }
Finalize()33 void CBC_PDF417ECErrorCorrection::Finalize() {
34   delete m_field;
35 }
CBC_PDF417ECErrorCorrection()36 CBC_PDF417ECErrorCorrection::CBC_PDF417ECErrorCorrection() {}
~CBC_PDF417ECErrorCorrection()37 CBC_PDF417ECErrorCorrection::~CBC_PDF417ECErrorCorrection() {}
decode(CFX_Int32Array & received,int32_t numECCodewords,CFX_Int32Array & erasures,int32_t & e)38 int32_t CBC_PDF417ECErrorCorrection::decode(CFX_Int32Array& received,
39                                             int32_t numECCodewords,
40                                             CFX_Int32Array& erasures,
41                                             int32_t& e) {
42   CBC_PDF417ECModulusPoly poly(m_field, received, e);
43   BC_EXCEPTION_CHECK_ReturnValue(e, -1);
44   CFX_Int32Array S;
45   S.SetSize(numECCodewords);
46   FX_BOOL error = FALSE;
47   for (int32_t l = numECCodewords; l > 0; l--) {
48     int32_t eval = poly.evaluateAt(m_field->exp(l));
49     S[numECCodewords - l] = eval;
50     if (eval != 0) {
51       error = TRUE;
52     }
53   }
54   if (!error) {
55     return 0;
56   }
57   CBC_PDF417ECModulusPoly* syndrome =
58       new CBC_PDF417ECModulusPoly(m_field, S, e);
59   BC_EXCEPTION_CHECK_ReturnValue(e, -1);
60   CBC_PDF417ECModulusPoly* buildmonomial =
61       m_field->buildMonomial(numECCodewords, 1, e);
62   if (e != BCExceptionNO) {
63     delete syndrome;
64     return -1;
65   }
66   CFX_PtrArray* sigmaOmega =
67       runEuclideanAlgorithm(buildmonomial, syndrome, numECCodewords, e);
68   delete buildmonomial;
69   delete syndrome;
70   BC_EXCEPTION_CHECK_ReturnValue(e, -1);
71   CBC_PDF417ECModulusPoly* sigma =
72       (CBC_PDF417ECModulusPoly*)sigmaOmega->GetAt(0);
73   CBC_PDF417ECModulusPoly* omega =
74       (CBC_PDF417ECModulusPoly*)sigmaOmega->GetAt(1);
75   CFX_Int32Array* errorLocations = findErrorLocations(sigma, e);
76   if (e != BCExceptionNO) {
77     for (int32_t i = 0; i < sigmaOmega->GetSize(); i++) {
78       delete (CBC_PDF417ECModulusPoly*)sigmaOmega->GetAt(i);
79     }
80     sigmaOmega->RemoveAll();
81     delete sigmaOmega;
82     return -1;
83   }
84   CFX_Int32Array* errorMagnitudes =
85       findErrorMagnitudes(omega, sigma, *errorLocations, e);
86   if (e != BCExceptionNO) {
87     delete errorLocations;
88     for (int32_t i = 0; i < sigmaOmega->GetSize(); i++) {
89       delete (CBC_PDF417ECModulusPoly*)sigmaOmega->GetAt(i);
90     }
91     sigmaOmega->RemoveAll();
92     delete sigmaOmega;
93     return -1;
94   }
95   for (int32_t i = 0; i < errorLocations->GetSize(); i++) {
96     int32_t log = m_field->log(errorLocations->GetAt(i), e);
97     ;
98     BC_EXCEPTION_CHECK_ReturnValue(e, -1);
99     int32_t position = received.GetSize() - 1 - log;
100     if (position < 0) {
101       e = BCExceptionChecksumException;
102       delete errorLocations;
103       delete errorMagnitudes;
104       for (int32_t j = 0; j < sigmaOmega->GetSize(); j++) {
105         delete (CBC_PDF417ECModulusPoly*)sigmaOmega->GetAt(j);
106       }
107       sigmaOmega->RemoveAll();
108       delete sigmaOmega;
109       return -1;
110     }
111     received[position] =
112         m_field->subtract(received[position], errorMagnitudes->GetAt(i));
113   }
114   int32_t result = errorLocations->GetSize();
115   delete errorLocations;
116   delete errorMagnitudes;
117   for (int32_t k = 0; k < sigmaOmega->GetSize(); k++) {
118     delete (CBC_PDF417ECModulusPoly*)sigmaOmega->GetAt(k);
119   }
120   sigmaOmega->RemoveAll();
121   delete sigmaOmega;
122   return result;
123 }
runEuclideanAlgorithm(CBC_PDF417ECModulusPoly * a,CBC_PDF417ECModulusPoly * b,int32_t R,int32_t & e)124 CFX_PtrArray* CBC_PDF417ECErrorCorrection::runEuclideanAlgorithm(
125     CBC_PDF417ECModulusPoly* a,
126     CBC_PDF417ECModulusPoly* b,
127     int32_t R,
128     int32_t& e) {
129   if (a->getDegree() < b->getDegree()) {
130     CBC_PDF417ECModulusPoly* temp = a;
131     a = b;
132     b = temp;
133   }
134   CBC_PDF417ECModulusPoly* rLast = a;
135   CBC_PDF417ECModulusPoly* r = b;
136   CBC_PDF417ECModulusPoly* tLast = m_field->getZero();
137   CBC_PDF417ECModulusPoly* t = m_field->getOne();
138   CBC_PDF417ECModulusPoly* qtemp = NULL;
139   CBC_PDF417ECModulusPoly* rtemp = NULL;
140   CBC_PDF417ECModulusPoly* ttemp = NULL;
141   int32_t i = 0;
142   int32_t j = 0;
143   int32_t m = 0;
144   int32_t n = 0;
145   while (r->getDegree() >= R / 2) {
146     CBC_PDF417ECModulusPoly* rLastLast = rLast;
147     CBC_PDF417ECModulusPoly* tLastLast = tLast;
148     rLast = r;
149     tLast = t;
150     m = i;
151     n = j;
152     if (rLast->isZero()) {
153       e = BCExceptionChecksumException;
154       if (qtemp) {
155         delete qtemp;
156       }
157       if (rtemp) {
158         delete rtemp;
159       }
160       if (ttemp) {
161         delete ttemp;
162       }
163       return NULL;
164     }
165     r = rLastLast;
166     CBC_PDF417ECModulusPoly* q = m_field->getZero();
167     int32_t denominatorLeadingTerm = rLast->getCoefficient(rLast->getDegree());
168     int32_t dltInverse = m_field->inverse(denominatorLeadingTerm, e);
169     if (e != BCExceptionNO) {
170       if (qtemp) {
171         delete qtemp;
172       }
173       if (rtemp) {
174         delete rtemp;
175       }
176       if (ttemp) {
177         delete ttemp;
178       }
179       return NULL;
180     }
181     while (r->getDegree() >= rLast->getDegree() && !r->isZero()) {
182       int32_t degreeDiff = r->getDegree() - rLast->getDegree();
183       int32_t scale =
184           m_field->multiply(r->getCoefficient(r->getDegree()), dltInverse);
185       CBC_PDF417ECModulusPoly* buildmonomial =
186           m_field->buildMonomial(degreeDiff, scale, e);
187       if (e != BCExceptionNO) {
188         if (qtemp) {
189           delete qtemp;
190         }
191         if (rtemp) {
192           delete rtemp;
193         }
194         if (ttemp) {
195           delete ttemp;
196         }
197         return NULL;
198       }
199       q = q->add(buildmonomial, e);
200       delete buildmonomial;
201       if (qtemp) {
202         delete qtemp;
203       }
204       if (e != BCExceptionNO) {
205         if (rtemp) {
206           delete rtemp;
207         }
208         if (ttemp) {
209           delete ttemp;
210         }
211         return NULL;
212       }
213       qtemp = q;
214       CBC_PDF417ECModulusPoly* multiply =
215           rLast->multiplyByMonomial(degreeDiff, scale, e);
216       if (e != BCExceptionNO) {
217         if (qtemp) {
218           delete qtemp;
219         }
220         if (rtemp) {
221           delete rtemp;
222         }
223         if (ttemp) {
224           delete ttemp;
225         }
226         return NULL;
227       }
228       CBC_PDF417ECModulusPoly* temp = r;
229       r = temp->subtract(multiply, e);
230       delete multiply;
231       if (m > 1 && i > m) {
232         delete temp;
233         temp = NULL;
234       }
235       if (e != BCExceptionNO) {
236         if (qtemp) {
237           delete qtemp;
238         }
239         if (rtemp) {
240           delete rtemp;
241         }
242         if (ttemp) {
243           delete ttemp;
244         }
245         return NULL;
246       }
247       rtemp = r;
248       i = m + 1;
249     }
250     ttemp = q->multiply(tLast, e);
251     if (qtemp) {
252       delete qtemp;
253       qtemp = NULL;
254     }
255     if (e != BCExceptionNO) {
256       if (rtemp) {
257         delete rtemp;
258       }
259       if (ttemp) {
260         delete ttemp;
261       }
262       return NULL;
263     }
264     t = ttemp->subtract(tLastLast, e);
265     if (n > 1 && j > n) {
266       delete tLastLast;
267     }
268     delete ttemp;
269     if (e != BCExceptionNO) {
270       if (rtemp) {
271         delete rtemp;
272       }
273       return NULL;
274     }
275     ttemp = t;
276     t = ttemp->negative(e);
277     delete ttemp;
278     if (e != BCExceptionNO) {
279       if (rtemp) {
280         delete rtemp;
281       }
282       return NULL;
283     }
284     ttemp = t;
285     j++;
286   }
287   int32_t sigmaTildeAtZero = t->getCoefficient(0);
288   if (sigmaTildeAtZero == 0) {
289     e = BCExceptionChecksumException;
290     if (rtemp) {
291       delete rtemp;
292     }
293     if (ttemp) {
294       delete ttemp;
295     }
296     return NULL;
297   }
298   int32_t inverse = m_field->inverse(sigmaTildeAtZero, e);
299   if (e != BCExceptionNO) {
300     if (rtemp) {
301       delete rtemp;
302     }
303     if (ttemp) {
304       delete ttemp;
305     }
306     return NULL;
307   }
308   CBC_PDF417ECModulusPoly* sigma = t->multiply(inverse, e);
309   if (ttemp) {
310     delete ttemp;
311   }
312   if (e != BCExceptionNO) {
313     if (rtemp) {
314       delete rtemp;
315     }
316     return NULL;
317   }
318   CBC_PDF417ECModulusPoly* omega = r->multiply(inverse, e);
319   if (rtemp) {
320     delete rtemp;
321   }
322   BC_EXCEPTION_CHECK_ReturnValue(e, NULL);
323   CFX_PtrArray* modulusPoly = new CFX_PtrArray;
324   modulusPoly->Add(sigma);
325   modulusPoly->Add(omega);
326   return modulusPoly;
327 }
findErrorLocations(CBC_PDF417ECModulusPoly * errorLocator,int32_t & e)328 CFX_Int32Array* CBC_PDF417ECErrorCorrection::findErrorLocations(
329     CBC_PDF417ECModulusPoly* errorLocator,
330     int32_t& e) {
331   int32_t numErrors = errorLocator->getDegree();
332   CFX_Int32Array* result = new CFX_Int32Array;
333   result->SetSize(numErrors);
334   int32_t ee = 0;
335   for (int32_t i = 1; i < m_field->getSize() && ee < numErrors; i++) {
336     if (errorLocator->evaluateAt(i) == 0) {
337       result->SetAt(ee, m_field->inverse(i, e));
338       if (e != BCExceptionNO) {
339         delete result;
340         return NULL;
341       }
342       ee++;
343     }
344   }
345   if (ee != numErrors) {
346     e = BCExceptionChecksumException;
347     delete result;
348     return NULL;
349   }
350   return result;
351 }
findErrorMagnitudes(CBC_PDF417ECModulusPoly * errorEvaluator,CBC_PDF417ECModulusPoly * errorLocator,CFX_Int32Array & errorLocations,int32_t & e)352 CFX_Int32Array* CBC_PDF417ECErrorCorrection::findErrorMagnitudes(
353     CBC_PDF417ECModulusPoly* errorEvaluator,
354     CBC_PDF417ECModulusPoly* errorLocator,
355     CFX_Int32Array& errorLocations,
356     int32_t& e) {
357   int32_t errorLocatorDegree = errorLocator->getDegree();
358   CFX_Int32Array formalDerivativeCoefficients;
359   formalDerivativeCoefficients.SetSize(errorLocatorDegree);
360   for (int32_t l = 1; l <= errorLocatorDegree; l++) {
361     formalDerivativeCoefficients[errorLocatorDegree - l] =
362         m_field->multiply(l, errorLocator->getCoefficient(l));
363   }
364   CBC_PDF417ECModulusPoly formalDerivative(m_field,
365                                            formalDerivativeCoefficients, e);
366   BC_EXCEPTION_CHECK_ReturnValue(e, NULL);
367   int32_t s = errorLocations.GetSize();
368   CFX_Int32Array* result = new CFX_Int32Array;
369   result->SetSize(s);
370   for (int32_t i = 0; i < s; i++) {
371     int32_t xiInverse = m_field->inverse(errorLocations[i], e);
372     if (e != BCExceptionNO) {
373       delete result;
374       return NULL;
375     }
376     int32_t numerator =
377         m_field->subtract(0, errorEvaluator->evaluateAt(xiInverse));
378     int32_t denominator =
379         m_field->inverse(formalDerivative.evaluateAt(xiInverse), e);
380     if (e != BCExceptionNO) {
381       delete result;
382       return NULL;
383     }
384     result->SetAt(i, m_field->multiply(numerator, denominator));
385   }
386   return result;
387 }
388