001/* 002 * Copyright 2007 ZXing authors 003 * 004 * Licensed under the Apache License, Version 2.0 (the "License"); 005 * you may not use this file except in compliance with the License. 006 * You may obtain a copy of the License at 007 * 008 * http://www.apache.org/licenses/LICENSE-2.0 009 * 010 * Unless required by applicable law or agreed to in writing, software 011 * distributed under the License is distributed on an "AS IS" BASIS, 012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 013 * See the License for the specific language governing permissions and 014 * limitations under the License. 015 */ 016 017package com.itextpdf.text.pdf.qrcode; 018 019/** 020 * <p>Represents a polynomial whose coefficients are elements of GF(256). 021 * Instances of this class are immutable.</p> 022 * 023 * <p>Much credit is due to William Rucklidge since portions of this code are an indirect 024 * port of his C++ Reed-Solomon implementation.</p> 025 * 026 * @author Sean Owen 027 * @since 5.0.2 028 */ 029final class GF256Poly { 030 031 private final GF256 field; 032 private final int[] coefficients; 033 034 /** 035 * @param field the {@link GF256} instance representing the field to use 036 * to perform computations 037 * @param coefficients coefficients as ints representing elements of GF(256), arranged 038 * from most significant (highest-power term) coefficient to least significant 039 * @throws IllegalArgumentException if argument is null or empty, 040 * or if leading coefficient is 0 and this is not a 041 * constant polynomial (that is, it is not the monomial "0") 042 */ 043 GF256Poly(GF256 field, int[] coefficients) { 044 if (coefficients == null || coefficients.length == 0) { 045 throw new IllegalArgumentException(); 046 } 047 this.field = field; 048 int coefficientsLength = coefficients.length; 049 if (coefficientsLength > 1 && coefficients[0] == 0) { 050 // Leading term must be non-zero for anything except the constant polynomial "0" 051 int firstNonZero = 1; 052 while (firstNonZero < coefficientsLength && coefficients[firstNonZero] == 0) { 053 firstNonZero++; 054 } 055 if (firstNonZero == coefficientsLength) { 056 this.coefficients = field.getZero().coefficients; 057 } else { 058 this.coefficients = new int[coefficientsLength - firstNonZero]; 059 System.arraycopy(coefficients, 060 firstNonZero, 061 this.coefficients, 062 0, 063 this.coefficients.length); 064 } 065 } else { 066 this.coefficients = coefficients; 067 } 068 } 069 070 int[] getCoefficients() { 071 return coefficients; 072 } 073 074 /** 075 * @return degree of this polynomial 076 */ 077 int getDegree() { 078 return coefficients.length - 1; 079 } 080 081 /** 082 * @return true iff this polynomial is the monomial "0" 083 */ 084 boolean isZero() { 085 return coefficients[0] == 0; 086 } 087 088 /** 089 * @return coefficient of x^degree term in this polynomial 090 */ 091 int getCoefficient(int degree) { 092 return coefficients[coefficients.length - 1 - degree]; 093 } 094 095 /** 096 * @return evaluation of this polynomial at a given point 097 */ 098 int evaluateAt(int a) { 099 if (a == 0) { 100 // Just return the x^0 coefficient 101 return getCoefficient(0); 102 } 103 int size = coefficients.length; 104 if (a == 1) { 105 // Just the sum of the coefficients 106 int result = 0; 107 for (int i = 0; i < size; i++) { 108 result = GF256.addOrSubtract(result, coefficients[i]); 109 } 110 return result; 111 } 112 int result = coefficients[0]; 113 for (int i = 1; i < size; i++) { 114 result = GF256.addOrSubtract(field.multiply(a, result), coefficients[i]); 115 } 116 return result; 117 } 118 119 GF256Poly addOrSubtract(GF256Poly other) { 120 if (!field.equals(other.field)) { 121 throw new IllegalArgumentException("GF256Polys do not have same GF256 field"); 122 } 123 if (isZero()) { 124 return other; 125 } 126 if (other.isZero()) { 127 return this; 128 } 129 130 int[] smallerCoefficients = this.coefficients; 131 int[] largerCoefficients = other.coefficients; 132 if (smallerCoefficients.length > largerCoefficients.length) { 133 int[] temp = smallerCoefficients; 134 smallerCoefficients = largerCoefficients; 135 largerCoefficients = temp; 136 } 137 int[] sumDiff = new int[largerCoefficients.length]; 138 int lengthDiff = largerCoefficients.length - smallerCoefficients.length; 139 // Copy high-order terms only found in higher-degree polynomial's coefficients 140 System.arraycopy(largerCoefficients, 0, sumDiff, 0, lengthDiff); 141 142 for (int i = lengthDiff; i < largerCoefficients.length; i++) { 143 sumDiff[i] = GF256.addOrSubtract(smallerCoefficients[i - lengthDiff], largerCoefficients[i]); 144 } 145 146 return new GF256Poly(field, sumDiff); 147 } 148 149 GF256Poly multiply(GF256Poly other) { 150 if (!field.equals(other.field)) { 151 throw new IllegalArgumentException("GF256Polys do not have same GF256 field"); 152 } 153 if (isZero() || other.isZero()) { 154 return field.getZero(); 155 } 156 int[] aCoefficients = this.coefficients; 157 int aLength = aCoefficients.length; 158 int[] bCoefficients = other.coefficients; 159 int bLength = bCoefficients.length; 160 int[] product = new int[aLength + bLength - 1]; 161 for (int i = 0; i < aLength; i++) { 162 int aCoeff = aCoefficients[i]; 163 for (int j = 0; j < bLength; j++) { 164 product[i + j] = GF256.addOrSubtract(product[i + j], 165 field.multiply(aCoeff, bCoefficients[j])); 166 } 167 } 168 return new GF256Poly(field, product); 169 } 170 171 GF256Poly multiply(int scalar) { 172 if (scalar == 0) { 173 return field.getZero(); 174 } 175 if (scalar == 1) { 176 return this; 177 } 178 int size = coefficients.length; 179 int[] product = new int[size]; 180 for (int i = 0; i < size; i++) { 181 product[i] = field.multiply(coefficients[i], scalar); 182 } 183 return new GF256Poly(field, product); 184 } 185 186 GF256Poly multiplyByMonomial(int degree, int coefficient) { 187 if (degree < 0) { 188 throw new IllegalArgumentException(); 189 } 190 if (coefficient == 0) { 191 return field.getZero(); 192 } 193 int size = coefficients.length; 194 int[] product = new int[size + degree]; 195 for (int i = 0; i < size; i++) { 196 product[i] = field.multiply(coefficients[i], coefficient); 197 } 198 return new GF256Poly(field, product); 199 } 200 201 GF256Poly[] divide(GF256Poly other) { 202 if (!field.equals(other.field)) { 203 throw new IllegalArgumentException("GF256Polys do not have same GF256 field"); 204 } 205 if (other.isZero()) { 206 throw new IllegalArgumentException("Divide by 0"); 207 } 208 209 GF256Poly quotient = field.getZero(); 210 GF256Poly remainder = this; 211 212 int denominatorLeadingTerm = other.getCoefficient(other.getDegree()); 213 int inverseDenominatorLeadingTerm = field.inverse(denominatorLeadingTerm); 214 215 while (remainder.getDegree() >= other.getDegree() && !remainder.isZero()) { 216 int degreeDifference = remainder.getDegree() - other.getDegree(); 217 int scale = field.multiply(remainder.getCoefficient(remainder.getDegree()), inverseDenominatorLeadingTerm); 218 GF256Poly term = other.multiplyByMonomial(degreeDifference, scale); 219 GF256Poly iterationQuotient = field.buildMonomial(degreeDifference, scale); 220 quotient = quotient.addOrSubtract(iterationQuotient); 221 remainder = remainder.addOrSubtract(term); 222 } 223 224 return new GF256Poly[] { quotient, remainder }; 225 } 226 227 public String toString() { 228 StringBuffer result = new StringBuffer(8 * getDegree()); 229 for (int degree = getDegree(); degree >= 0; degree--) { 230 int coefficient = getCoefficient(degree); 231 if (coefficient != 0) { 232 if (coefficient < 0) { 233 result.append(" - "); 234 coefficient = -coefficient; 235 } else { 236 if (result.length() > 0) { 237 result.append(" + "); 238 } 239 } 240 if (degree == 0 || coefficient != 1) { 241 int alphaPower = field.log(coefficient); 242 if (alphaPower == 0) { 243 result.append('1'); 244 } else if (alphaPower == 1) { 245 result.append('a'); 246 } else { 247 result.append("a^"); 248 result.append(alphaPower); 249 } 250 } 251 if (degree != 0) { 252 if (degree == 1) { 253 result.append('x'); 254 } else { 255 result.append("x^"); 256 result.append(degree); 257 } 258 } 259 } 260 } 261 return result.toString(); 262 } 263 264}