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