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