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