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 2007 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_ReedSolomonGF256.h" 25 #include "BC_ReedSolomonGF256Poly.h" 26 CBC_ReedSolomonGF256Poly::CBC_ReedSolomonGF256Poly(CBC_ReedSolomonGF256* field, 27 int32_t coefficients) { 28 if (field == NULL) { 29 return; 30 } 31 m_field = field; 32 m_coefficients.Add(coefficients); 33 } 34 CBC_ReedSolomonGF256Poly::CBC_ReedSolomonGF256Poly() { 35 m_field = NULL; 36 } 37 void CBC_ReedSolomonGF256Poly::Init(CBC_ReedSolomonGF256* field, 38 CFX_Int32Array* coefficients, 39 int32_t& e) { 40 if (coefficients == NULL || coefficients->GetSize() == 0) { 41 e = BCExceptionCoefficientsSizeIsNull; 42 BC_EXCEPTION_CHECK_ReturnVoid(e); 43 } 44 m_field = field; 45 int32_t coefficientsLength = coefficients->GetSize(); 46 if ((coefficientsLength > 1 && (*coefficients)[0] == 0)) { 47 int32_t firstNonZero = 1; 48 while ((firstNonZero < coefficientsLength) && 49 ((*coefficients)[firstNonZero] == 0)) { 50 firstNonZero++; 51 } 52 if (firstNonZero == coefficientsLength) { 53 m_coefficients.Copy(*(m_field->GetZero()->GetCoefficients())); 54 } else { 55 m_coefficients.SetSize(coefficientsLength - firstNonZero); 56 for (int32_t i = firstNonZero, j = 0; i < coefficientsLength; i++, j++) { 57 m_coefficients[j] = coefficients->operator[](i); 58 } 59 } 60 } else { 61 m_coefficients.Copy(*coefficients); 62 } 63 } 64 CFX_Int32Array* CBC_ReedSolomonGF256Poly::GetCoefficients() { 65 return &m_coefficients; 66 } 67 int32_t CBC_ReedSolomonGF256Poly::GetDegree() { 68 return m_coefficients.GetSize() - 1; 69 } 70 FX_BOOL CBC_ReedSolomonGF256Poly::IsZero() { 71 return m_coefficients[0] == 0; 72 } 73 int32_t CBC_ReedSolomonGF256Poly::GetCoefficients(int32_t degree) { 74 return m_coefficients[m_coefficients.GetSize() - 1 - degree]; 75 } 76 int32_t CBC_ReedSolomonGF256Poly::EvaluateAt(int32_t a) { 77 if (a == 0) { 78 return GetCoefficients(0); 79 } 80 int32_t size = m_coefficients.GetSize(); 81 if (a == 1) { 82 int32_t result = 0; 83 for (int32_t i = 0; i < size; i++) { 84 result = CBC_ReedSolomonGF256::AddOrSubtract(result, m_coefficients[i]); 85 } 86 return result; 87 } 88 int32_t result = m_coefficients[0]; 89 for (int32_t j = 1; j < size; j++) { 90 result = CBC_ReedSolomonGF256::AddOrSubtract(m_field->Multiply(a, result), 91 m_coefficients[j]); 92 } 93 return result; 94 } 95 CBC_ReedSolomonGF256Poly* CBC_ReedSolomonGF256Poly::Clone(int32_t& e) { 96 CBC_ReedSolomonGF256Poly* temp = new CBC_ReedSolomonGF256Poly(); 97 temp->Init(m_field, &m_coefficients, e); 98 BC_EXCEPTION_CHECK_ReturnValue(e, NULL); 99 return temp; 100 } 101 CBC_ReedSolomonGF256Poly* CBC_ReedSolomonGF256Poly::AddOrSubtract( 102 CBC_ReedSolomonGF256Poly* other, 103 int32_t& e) { 104 if (IsZero()) { 105 return other->Clone(e); 106 BC_EXCEPTION_CHECK_ReturnValue(e, NULL); 107 } 108 if (other->IsZero()) { 109 return this->Clone(e); 110 BC_EXCEPTION_CHECK_ReturnValue(e, NULL); 111 } 112 CFX_Int32Array smallerCoefficients; 113 smallerCoefficients.Copy(m_coefficients); 114 CFX_Int32Array largerCoefficients; 115 largerCoefficients.Copy(*(other->GetCoefficients())); 116 if (smallerCoefficients.GetSize() > largerCoefficients.GetSize()) { 117 CFX_Int32Array temp; 118 temp.Copy(smallerCoefficients); 119 smallerCoefficients.Copy(largerCoefficients); 120 largerCoefficients.Copy(temp); 121 } 122 CFX_Int32Array sumDiff; 123 sumDiff.SetSize(largerCoefficients.GetSize()); 124 int32_t lengthDiff = 125 largerCoefficients.GetSize() - smallerCoefficients.GetSize(); 126 for (int32_t i = 0; i < lengthDiff; i++) { 127 sumDiff[i] = largerCoefficients[i]; 128 } 129 for (int32_t j = lengthDiff; j < largerCoefficients.GetSize(); j++) { 130 sumDiff[j] = (CBC_ReedSolomonGF256::AddOrSubtract( 131 smallerCoefficients[j - lengthDiff], largerCoefficients[j])); 132 } 133 CBC_ReedSolomonGF256Poly* temp = new CBC_ReedSolomonGF256Poly(); 134 temp->Init(m_field, &sumDiff, e); 135 BC_EXCEPTION_CHECK_ReturnValue(e, NULL); 136 return temp; 137 } 138 CBC_ReedSolomonGF256Poly* CBC_ReedSolomonGF256Poly::Multiply( 139 CBC_ReedSolomonGF256Poly* other, 140 int32_t& e) { 141 if (IsZero() || other->IsZero()) { 142 CBC_ReedSolomonGF256Poly* temp = m_field->GetZero()->Clone(e); 143 BC_EXCEPTION_CHECK_ReturnValue(e, NULL); 144 return temp; 145 } 146 CFX_Int32Array aCoefficients; 147 aCoefficients.Copy(m_coefficients); 148 int32_t aLength = m_coefficients.GetSize(); 149 CFX_Int32Array bCoefficients; 150 bCoefficients.Copy(*(other->GetCoefficients())); 151 int32_t bLength = other->GetCoefficients()->GetSize(); 152 CFX_Int32Array product; 153 product.SetSize(aLength + bLength - 1); 154 for (int32_t i = 0; i < aLength; i++) { 155 int32_t aCoeff = m_coefficients[i]; 156 for (int32_t j = 0; j < bLength; j++) { 157 product[i + j] = CBC_ReedSolomonGF256::AddOrSubtract( 158 product[i + j], 159 m_field->Multiply(aCoeff, other->GetCoefficients()->operator[](j))); 160 } 161 } 162 CBC_ReedSolomonGF256Poly* temp = new CBC_ReedSolomonGF256Poly(); 163 temp->Init(m_field, &product, e); 164 BC_EXCEPTION_CHECK_ReturnValue(e, NULL); 165 return temp; 166 } 167 CBC_ReedSolomonGF256Poly* CBC_ReedSolomonGF256Poly::Multiply(int32_t scalar, 168 int32_t& e) { 169 if (scalar == 0) { 170 CBC_ReedSolomonGF256Poly* temp = m_field->GetZero()->Clone(e); 171 BC_EXCEPTION_CHECK_ReturnValue(e, NULL); 172 return temp; 173 } 174 if (scalar == 1) { 175 return this->Clone(e); 176 BC_EXCEPTION_CHECK_ReturnValue(e, NULL); 177 } 178 int32_t size = m_coefficients.GetSize(); 179 CFX_Int32Array product; 180 product.SetSize(size); 181 for (int32_t i = 0; i < size; i++) { 182 product[i] = m_field->Multiply(m_coefficients[i], scalar); 183 } 184 CBC_ReedSolomonGF256Poly* temp = new CBC_ReedSolomonGF256Poly(); 185 temp->Init(m_field, &product, e); 186 BC_EXCEPTION_CHECK_ReturnValue(e, NULL); 187 return temp; 188 } 189 CBC_ReedSolomonGF256Poly* CBC_ReedSolomonGF256Poly::MultiplyByMonomial( 190 int32_t degree, 191 int32_t coefficient, 192 int32_t& e) { 193 if (degree < 0) { 194 e = BCExceptionDegreeIsNegative; 195 BC_EXCEPTION_CHECK_ReturnValue(e, NULL); 196 } 197 if (coefficient == 0) { 198 CBC_ReedSolomonGF256Poly* temp = m_field->GetZero()->Clone(e); 199 BC_EXCEPTION_CHECK_ReturnValue(e, NULL); 200 return temp; 201 } 202 int32_t size = m_coefficients.GetSize(); 203 CFX_Int32Array product; 204 product.SetSize(size + degree); 205 for (int32_t i = 0; i < size; i++) { 206 product[i] = (m_field->Multiply(m_coefficients[i], coefficient)); 207 } 208 CBC_ReedSolomonGF256Poly* temp = new CBC_ReedSolomonGF256Poly(); 209 temp->Init(m_field, &product, e); 210 BC_EXCEPTION_CHECK_ReturnValue(e, NULL); 211 return temp; 212 } 213 CFX_PtrArray* CBC_ReedSolomonGF256Poly::Divide(CBC_ReedSolomonGF256Poly* other, 214 int32_t& e) { 215 if (other->IsZero()) { 216 e = BCExceptionDivideByZero; 217 BC_EXCEPTION_CHECK_ReturnValue(e, NULL); 218 } 219 CBC_ReedSolomonGF256Poly* rsg1 = m_field->GetZero()->Clone(e); 220 BC_EXCEPTION_CHECK_ReturnValue(e, NULL); 221 CBC_AutoPtr<CBC_ReedSolomonGF256Poly> quotient(rsg1); 222 CBC_ReedSolomonGF256Poly* rsg2 = this->Clone(e); 223 BC_EXCEPTION_CHECK_ReturnValue(e, NULL); 224 CBC_AutoPtr<CBC_ReedSolomonGF256Poly> remainder(rsg2); 225 int32_t denominatorLeadingTerm = other->GetCoefficients(other->GetDegree()); 226 int32_t inverseDenominatorLeadingTeam = 227 m_field->Inverse(denominatorLeadingTerm, e); 228 BC_EXCEPTION_CHECK_ReturnValue(e, NULL); 229 while (remainder->GetDegree() >= other->GetDegree() && !remainder->IsZero()) { 230 int32_t degreeDifference = remainder->GetDegree() - other->GetDegree(); 231 int32_t scale = 232 m_field->Multiply(remainder->GetCoefficients((remainder->GetDegree())), 233 inverseDenominatorLeadingTeam); 234 CBC_ReedSolomonGF256Poly* rsg3 = 235 other->MultiplyByMonomial(degreeDifference, scale, e); 236 BC_EXCEPTION_CHECK_ReturnValue(e, NULL); 237 CBC_AutoPtr<CBC_ReedSolomonGF256Poly> term(rsg3); 238 CBC_ReedSolomonGF256Poly* rsg4 = 239 m_field->BuildMonomial(degreeDifference, scale, e); 240 BC_EXCEPTION_CHECK_ReturnValue(e, NULL); 241 CBC_AutoPtr<CBC_ReedSolomonGF256Poly> iteratorQuotient(rsg4); 242 CBC_ReedSolomonGF256Poly* rsg5 = 243 quotient->AddOrSubtract(iteratorQuotient.get(), e); 244 BC_EXCEPTION_CHECK_ReturnValue(e, NULL); 245 CBC_AutoPtr<CBC_ReedSolomonGF256Poly> temp(rsg5); 246 quotient = temp; 247 CBC_ReedSolomonGF256Poly* rsg6 = remainder->AddOrSubtract(term.get(), e); 248 BC_EXCEPTION_CHECK_ReturnValue(e, NULL); 249 CBC_AutoPtr<CBC_ReedSolomonGF256Poly> temp1(rsg6); 250 remainder = temp1; 251 } 252 CFX_PtrArray* tempPtrA = new CFX_PtrArray; 253 tempPtrA->Add(quotient.release()); 254 tempPtrA->Add(remainder.release()); 255 return tempPtrA; 256 } 257 CBC_ReedSolomonGF256Poly::~CBC_ReedSolomonGF256Poly() { 258 m_coefficients.RemoveAll(); 259 } 260
