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