Merge to XFA: Use stdint.h types throughout PDFium.
[pdfium.git] / xfa / src / fxbarcode / common / reedsolomon / BC_ReedSolomonDecoder.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 #include "BC_ReedSolomonDecoder.h"\r
27 CBC_ReedSolomonDecoder::CBC_ReedSolomonDecoder(CBC_ReedSolomonGF256* field)\r
28 {\r
29     m_field = field;\r
30 }\r
31 CBC_ReedSolomonDecoder::~CBC_ReedSolomonDecoder()\r
32 {\r
33 }\r
34 void CBC_ReedSolomonDecoder::Decode(CFX_Int32Array* received, int32_t twoS, int32_t &e)\r
35 {\r
36     CBC_ReedSolomonGF256Poly poly;\r
37     poly.Init(m_field, received, e);\r
38     BC_EXCEPTION_CHECK_ReturnVoid(e);\r
39     CFX_Int32Array syndromeCoefficients;\r
40     syndromeCoefficients.SetSize(twoS);\r
41     FX_BOOL dataMatrix = FALSE;\r
42     FX_BOOL noError = TRUE;\r
43     for (int32_t i = 0; i < twoS; i++) {\r
44         int32_t eval = poly.EvaluateAt(m_field->Exp(dataMatrix ? i + 1 : i));\r
45         syndromeCoefficients[twoS - 1 - i] = eval;\r
46         if (eval != 0) {\r
47             noError = FALSE;\r
48         }\r
49     }\r
50     if(noError) {\r
51         return;\r
52     }\r
53     CBC_ReedSolomonGF256Poly syndrome;\r
54     syndrome.Init(m_field, &syndromeCoefficients, e);\r
55     BC_EXCEPTION_CHECK_ReturnVoid(e);\r
56     CBC_ReedSolomonGF256Poly* rsg = m_field->BuildMonomial(twoS, 1, e);\r
57     BC_EXCEPTION_CHECK_ReturnVoid(e);\r
58     CBC_AutoPtr<CBC_ReedSolomonGF256Poly> temp(rsg);\r
59     CFX_PtrArray* pa = RunEuclideanAlgorithm(temp.get(), &syndrome, twoS, e);\r
60     BC_EXCEPTION_CHECK_ReturnVoid(e);\r
61     CBC_AutoPtr<CFX_PtrArray > sigmaOmega(pa);\r
62     CBC_AutoPtr<CBC_ReedSolomonGF256Poly> sigma((CBC_ReedSolomonGF256Poly*)(*sigmaOmega)[0]);\r
63     CBC_AutoPtr<CBC_ReedSolomonGF256Poly> omega((CBC_ReedSolomonGF256Poly*)(*sigmaOmega)[1]);\r
64     CFX_Int32Array* ia1 = FindErrorLocations(sigma.get(), e);\r
65     BC_EXCEPTION_CHECK_ReturnVoid(e);\r
66     CBC_AutoPtr<CFX_Int32Array > errorLocations(ia1);\r
67     CFX_Int32Array* ia2 = FindErrorMagnitudes(omega.get(), errorLocations.get(), dataMatrix, e);\r
68     BC_EXCEPTION_CHECK_ReturnVoid(e);\r
69     CBC_AutoPtr<CFX_Int32Array > errorMagnitudes(ia2);\r
70     for (int32_t k = 0; k < errorLocations->GetSize(); k++) {\r
71         int32_t position = received->GetSize() - 1 - m_field->Log((*errorLocations)[k], e);\r
72         BC_EXCEPTION_CHECK_ReturnVoid(e);\r
73         if(position < 0) {\r
74             e = BCExceptionBadErrorLocation;\r
75             BC_EXCEPTION_CHECK_ReturnVoid(e);\r
76         }\r
77         (*received)[position] = CBC_ReedSolomonGF256::AddOrSubtract((*received)[position], (*errorMagnitudes)[k]);\r
78     }\r
79 }\r
80 CFX_PtrArray *CBC_ReedSolomonDecoder::RunEuclideanAlgorithm(CBC_ReedSolomonGF256Poly* a, CBC_ReedSolomonGF256Poly* b, int32_t R, int32_t &e)\r
81 {\r
82     if (a->GetDegree() < b->GetDegree()) {\r
83         CBC_ReedSolomonGF256Poly* temp = a;\r
84         a = b;\r
85         b = temp;\r
86     }\r
87     CBC_ReedSolomonGF256Poly* rsg1 = a->Clone(e);\r
88     BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
89     CBC_AutoPtr<CBC_ReedSolomonGF256Poly> rLast(rsg1);\r
90     CBC_ReedSolomonGF256Poly* rsg2 = b->Clone(e);\r
91     BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
92     CBC_AutoPtr<CBC_ReedSolomonGF256Poly> r(rsg2);\r
93     CBC_ReedSolomonGF256Poly* rsg3 = m_field->GetOne()->Clone(e);\r
94     BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
95     CBC_AutoPtr<CBC_ReedSolomonGF256Poly> sLast(rsg3);\r
96     CBC_ReedSolomonGF256Poly* rsg4 = m_field->GetZero()->Clone(e);\r
97     BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
98     CBC_AutoPtr<CBC_ReedSolomonGF256Poly> s(rsg4);\r
99     CBC_ReedSolomonGF256Poly* rsg5 = m_field->GetZero()->Clone(e);\r
100     BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
101     CBC_AutoPtr<CBC_ReedSolomonGF256Poly> tLast(rsg5);\r
102     CBC_ReedSolomonGF256Poly* rsg6 = m_field->GetOne()->Clone(e);\r
103     BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
104     CBC_AutoPtr<CBC_ReedSolomonGF256Poly> t(rsg6);\r
105     while (r->GetDegree() >= R / 2) {\r
106         CBC_AutoPtr<CBC_ReedSolomonGF256Poly> rLastLast = rLast;\r
107         CBC_AutoPtr<CBC_ReedSolomonGF256Poly> sLastLast = sLast;\r
108         CBC_AutoPtr<CBC_ReedSolomonGF256Poly> tLastlast = tLast;\r
109         rLast = r;\r
110         sLast = s;\r
111         tLast = t;\r
112         if (rLast->IsZero()) {\r
113             e = BCExceptionR_I_1IsZero;\r
114             BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
115         }\r
116         CBC_ReedSolomonGF256Poly* rsg7 =  rLastLast->Clone(e);\r
117         BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
118         CBC_AutoPtr<CBC_ReedSolomonGF256Poly> rTemp(rsg7);\r
119         r = rTemp;\r
120         CBC_ReedSolomonGF256Poly* rsg8 =  m_field->GetZero()->Clone(e);\r
121         BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
122         CBC_AutoPtr<CBC_ReedSolomonGF256Poly> q(rsg8);\r
123         int32_t denominatorLeadingTerm = rLast->GetCoefficients(rLast->GetDegree());\r
124         int32_t dltInverse = m_field->Inverse(denominatorLeadingTerm, e);\r
125         BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
126         while (r->GetDegree() >= rLast->GetDegree() && !(r->IsZero())) {\r
127             int32_t degreeDiff = r->GetDegree() - rLast->GetDegree();\r
128             int32_t scale = m_field->Multiply(r->GetCoefficients(r->GetDegree()), dltInverse);\r
129             CBC_ReedSolomonGF256Poly* rsgp1 = m_field->BuildMonomial(degreeDiff, scale, e);\r
130             BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
131             CBC_AutoPtr<CBC_ReedSolomonGF256Poly> build(rsgp1);\r
132             CBC_ReedSolomonGF256Poly* rsgp2 = q->AddOrSubtract(build.get(), e);\r
133             BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
134             CBC_AutoPtr<CBC_ReedSolomonGF256Poly> temp(rsgp2);\r
135             q = temp;\r
136             CBC_ReedSolomonGF256Poly* rsgp3 = rLast->MultiplyByMonomial(degreeDiff, scale, e);\r
137             BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
138             CBC_AutoPtr<CBC_ReedSolomonGF256Poly> multiply(rsgp3);\r
139             CBC_ReedSolomonGF256Poly* rsgp4 = r->AddOrSubtract(multiply.get(), e);\r
140             BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
141             CBC_AutoPtr<CBC_ReedSolomonGF256Poly> temp3(rsgp4);\r
142             r = temp3;\r
143         }\r
144         CBC_ReedSolomonGF256Poly* rsg9 = q->Multiply(sLast.get(), e);\r
145         BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
146         CBC_AutoPtr<CBC_ReedSolomonGF256Poly> temp1(rsg9);\r
147         CBC_ReedSolomonGF256Poly* rsg10 = temp1->AddOrSubtract(sLastLast.get(), e);\r
148         BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
149         CBC_AutoPtr<CBC_ReedSolomonGF256Poly> temp2(rsg10);\r
150         s = temp2;\r
151         CBC_ReedSolomonGF256Poly* rsg11 = q->Multiply(tLast.get(), e);\r
152         BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
153         CBC_AutoPtr<CBC_ReedSolomonGF256Poly> temp5(rsg11);\r
154         CBC_ReedSolomonGF256Poly* rsg12 = temp5->AddOrSubtract(tLastlast.get(), e);\r
155         BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
156         CBC_AutoPtr<CBC_ReedSolomonGF256Poly> temp6(rsg12);\r
157         t = temp6;\r
158     }\r
159     int32_t sigmaTildeAtZero = t->GetCoefficients(0);\r
160     if (sigmaTildeAtZero == 0) {\r
161         e = BCExceptionIsZero;\r
162         BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
163     }\r
164     int32_t inverse = m_field->Inverse(sigmaTildeAtZero, e);\r
165     BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
166     CBC_ReedSolomonGF256Poly* rsg13 = t->Multiply(inverse, e);\r
167     BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
168     CBC_AutoPtr<CBC_ReedSolomonGF256Poly> sigma(rsg13);\r
169     CBC_ReedSolomonGF256Poly* rsg14 = r->Multiply(inverse, e);\r
170     BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
171     CBC_AutoPtr<CBC_ReedSolomonGF256Poly> omega(rsg14);\r
172     CFX_PtrArray *temp = FX_NEW CFX_PtrArray;\r
173     temp->Add(sigma.release());\r
174     temp->Add(omega.release());\r
175     return temp;\r
176 }\r
177 CFX_Int32Array *CBC_ReedSolomonDecoder::FindErrorLocations(CBC_ReedSolomonGF256Poly* errorLocator, int32_t &e)\r
178 {\r
179     int32_t numErrors = errorLocator->GetDegree();\r
180     if (numErrors == 1) {\r
181         CBC_AutoPtr<CFX_Int32Array > temp(FX_NEW CFX_Int32Array);\r
182         temp->Add(errorLocator->GetCoefficients(1));\r
183         return temp.release();\r
184     }\r
185     CFX_Int32Array *tempT = FX_NEW CFX_Int32Array;\r
186     tempT->SetSize(numErrors);\r
187     CBC_AutoPtr<CFX_Int32Array > result(tempT);\r
188     int32_t ie = 0;\r
189     for (int32_t i = 1; i < 256 && ie < numErrors; i++) {\r
190         if(errorLocator->EvaluateAt(i) == 0) {\r
191             (*result)[ie] = m_field->Inverse(i, ie);\r
192             BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
193             ie++;\r
194         }\r
195     }\r
196     if (ie != numErrors) {\r
197         e = BCExceptionDegreeNotMatchRoots;\r
198         BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
199     }\r
200     return result.release();\r
201 }\r
202 CFX_Int32Array *CBC_ReedSolomonDecoder::FindErrorMagnitudes(CBC_ReedSolomonGF256Poly* errorEvaluator, CFX_Int32Array* errorLocations, FX_BOOL dataMatrix, int32_t &e)\r
203 {\r
204     int32_t s = errorLocations->GetSize();\r
205     CFX_Int32Array * temp = FX_NEW CFX_Int32Array;\r
206     temp->SetSize(s);\r
207     CBC_AutoPtr<CFX_Int32Array > result(temp);\r
208     for (int32_t i = 0; i < s; i++) {\r
209         int32_t xiInverse = m_field->Inverse(errorLocations->operator [](i), e);\r
210         BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
211         int32_t denominator = 1;\r
212         for(int32_t j = 0; j < s; j++) {\r
213             if(i != j) {\r
214                 denominator = m_field->Multiply(denominator,\r
215                                                 CBC_ReedSolomonGF256::AddOrSubtract(1, m_field->Multiply(errorLocations->operator [](j), xiInverse)));\r
216             }\r
217         }\r
218         int32_t temp = m_field->Inverse(denominator, temp);\r
219         BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
220         (*result)[i] = m_field->Multiply(errorEvaluator->EvaluateAt(xiInverse),\r
221                                          temp);\r
222     }\r
223     return result.release();\r
224 }\r