csharp/common/reedsolomon/GF256Poly.cs

   1 /*\r
   2 * Licensed under the Apache License, Version 2.0 (the "License");\r
   3 * you may not use this file except in compliance with the License.\r
   4 * You may obtain a copy of the License at\r
   5 *\r
   6 *      http://www.apache.org/licenses/LICENSE-2.0\r
   7 *\r
   8 * Unless required by applicable law or agreed to in writing, software\r
   9 * distributed under the License is distributed on an "AS IS" BASIS,\r
  10 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\r
  11 * See the License for the specific language governing permissions and\r
  12 * limitations under the License.\r
  13 */\r
  14 \r
  15 using System;\r
  16 using System.Text;\r
  17 namespace com.google.zxing.common.reedsolomon\r
  18 {\r
  19 \r
  20     /// <summary> <p>Represents a polynomial whose coefficients are elements of GF(256).\r
  21     /// Instances of this class are immutable.</p>\r
  22     /// \r
  23     /// <p>Much credit is due to William Rucklidge since portions of this code are an indirect\r
  24     /// port of his C++ Reed-Solomon implementation.</p>\r
  25     /// \r
  26     /// </summary>\r
  27     /// <author>  srowen@google.com (Sean Owen)\r
  28     /// </author>\r
  29     public sealed class GF256Poly\r
  30     { \r
  31           private GF256 field;\r
  32           private int[] coefficients;\r
  33 \r
  34           /**\r
  35            * @param field the {@link GF256} instance representing the field to use\r
  36            * to perform computations\r
  37            * @param coefficients coefficients as ints representing elements of GF(256), arranged\r
  38            * from most significant (highest-power term) coefficient to least significant\r
  39            * @throws ArgumentException if argument is null or empty,\r
  40            * or if leading coefficient is 0 and this is not a\r
  41            * constant polynomial (that is, it is not the monomial "0")\r
  42            */\r
  43           public GF256Poly(GF256 field, int[] coefficients) {\r
  44             if (coefficients == null || coefficients.Length == 0) {\r
  45               throw new ArgumentException();\r
  46             }\r
  47             this.field = field;\r
  48             int coefficientsLength = coefficients.Length;\r
  49             if (coefficientsLength > 1 && coefficients[0] == 0) {\r
  50               // Leading term must be non-zero for anything except the constant polynomial "0"\r
  51               int firstNonZero = 1;\r
  52               while (firstNonZero < coefficientsLength && coefficients[firstNonZero] == 0) {\r
  53                 firstNonZero++;\r
  54               }\r
  55               if (firstNonZero == coefficientsLength) {\r
  56                 this.coefficients = field.getZero().coefficients;\r
  57               } else {\r
  58                 this.coefficients = new int[coefficientsLength - firstNonZero];\r
  59                 System.Array.Copy(coefficients,firstNonZero,this.coefficients,0,this.coefficients.Length);\r
  60               }\r
  61             } else {\r
  62               this.coefficients = coefficients;\r
  63             }\r
  64           }\r
  65 \r
  66           public int[] getCoefficients()\r
  67           {\r
  68             return coefficients;\r
  69           }\r
  70 \r
  71           /**\r
  72            * @return degree of this polynomial\r
  73            */\r
  74           public int getDegree()\r
  75           {\r
  76             return coefficients.Length - 1;\r
  77           }\r
  78 \r
  79           /**\r
  80            * @return true iff this polynomial is the monomial "0"\r
  81            */\r
  82           public bool isZero()\r
  83           {\r
  84             return coefficients[0] == 0;\r
  85           }\r
  86 \r
  87           /**\r
  88            * @return coefficient of x^degree term in this polynomial\r
  89            */\r
  90           public int getCoefficient(int degree)\r
  91           {\r
  92             return coefficients[coefficients.Length - 1 - degree];\r
  93           }\r
  94 \r
  95           /**\r
  96            * @return evaluation of this polynomial at a given point\r
  97            */\r
  98           public int evaluateAt(int a)\r
  99           {\r
 100             if (a == 0) {\r
 101               // Just return the x^0 coefficient\r
 102               return getCoefficient(0);\r
 103             }\r
 104             int size = coefficients.Length;\r
 105             int result = 0;\r
 106 \r
 107             if (a == 1) {\r
 108               // Just the sum of the coefficients\r
 109               result = 0;\r
 110               for (int i = 0; i < size; i++) {\r
 111                 result = GF256.addOrSubtract(result, coefficients[i]);\r
 112               }\r
 113               return result;\r
 114             }\r
 115 \r
 116             result = coefficients[0];\r
 117             for (int i = 1; i < size; i++) {\r
 118               result = GF256.addOrSubtract(field.multiply(a, result), coefficients[i]);\r
 119             }\r
 120             return result;\r
 121           }\r
 122 \r
 123           public GF256Poly addOrSubtract(GF256Poly other)\r
 124           {\r
 125             if (!field.Equals(other.field)) {\r
 126               throw new ArgumentException("GF256Polys do not have same GF256 field");\r
 127             }\r
 128             if (isZero()) {\r
 129               return other;\r
 130             }\r
 131             if (other.isZero()) {\r
 132               return this;\r
 133             }\r
 134 \r
 135             int[] smallerCoefficients = this.coefficients;\r
 136             int[] largerCoefficients = other.coefficients;\r
 137             if (smallerCoefficients.Length > largerCoefficients.Length) {\r
 138               int[] temp = smallerCoefficients;\r
 139               smallerCoefficients = largerCoefficients;\r
 140               largerCoefficients = temp;\r
 141             }\r
 142             int[] sumDiff = new int[largerCoefficients.Length];\r
 143             int lengthDiff = largerCoefficients.Length - smallerCoefficients.Length;\r
 144             // Copy high-order terms only found in higher-degree polynomial's coefficients\r
 145             System.Array.Copy(largerCoefficients, 0, sumDiff, 0, lengthDiff);\r
 146 \r
 147             for (int i = lengthDiff; i < largerCoefficients.Length; i++) {\r
 148               sumDiff[i] = GF256.addOrSubtract(smallerCoefficients[i - lengthDiff], largerCoefficients[i]);\r
 149             }\r
 150 \r
 151             return new GF256Poly(field, sumDiff);\r
 152           }\r
 153 \r
 154           public GF256Poly multiply(GF256Poly other)\r
 155           {\r
 156             if (!field.Equals(other.field)) {\r
 157               throw new ArgumentException("GF256Polys do not have same GF256 field");\r
 158             }\r
 159             if (isZero() || other.isZero()) {\r
 160               return field.getZero();\r
 161             }\r
 162             int[] aCoefficients = this.coefficients;\r
 163             int aLength = aCoefficients.Length;\r
 164             int[] bCoefficients = other.coefficients;\r
 165             int bLength = bCoefficients.Length;\r
 166             int[] product = new int[aLength + bLength - 1];\r
 167             for (int i = 0; i < aLength; i++) {\r
 168               int aCoeff = aCoefficients[i];\r
 169               for (int j = 0; j < bLength; j++) {\r
 170                 product[i + j] = GF256.addOrSubtract(product[i + j],\r
 171                     field.multiply(aCoeff, bCoefficients[j]));\r
 172               }\r
 173             }\r
 174             return new GF256Poly(field, product);\r
 175           }\r
 176 \r
 177           public GF256Poly multiply(int scalar)\r
 178           {\r
 179             if (scalar == 0) {\r
 180               return field.getZero();\r
 181             }\r
 182             if (scalar == 1) {\r
 183               return this;\r
 184             }\r
 185             int size = coefficients.Length;\r
 186             int[] product = new int[size];\r
 187             for (int i = 0; i < size; i++) {\r
 188               product[i] = field.multiply(coefficients[i], scalar);\r
 189             }\r
 190             return new GF256Poly(field, product);\r
 191           }\r
 192 \r
 193           public GF256Poly multiplyByMonomial(int degree, int coefficient)\r
 194           {\r
 195             if (degree < 0) {\r
 196               throw new ArgumentException();\r
 197             }\r
 198             if (coefficient == 0) {\r
 199               return field.getZero();\r
 200             }\r
 201             int size = coefficients.Length;\r
 202             int[] product = new int[size + degree];\r
 203             for (int i = 0; i < size; i++) {\r
 204               product[i] = field.multiply(coefficients[i], coefficient);\r
 205             }\r
 206             return new GF256Poly(field, product);\r
 207           }\r
 208 \r
 209           public GF256Poly[] divide(GF256Poly other)\r
 210           {\r
 211             if (!field.Equals(other.field)) {\r
 212               throw new ArgumentException("GF256Polys do not have same GF256 field");\r
 213             }\r
 214             if (other.isZero()) {\r
 215               throw new ArgumentException("Divide by 0");\r
 216             }\r
 217 \r
 218             GF256Poly quotient = field.getZero();\r
 219             GF256Poly remainder = this;\r
 220 \r
 221             int denominatorLeadingTerm = other.getCoefficient(other.getDegree());\r
 222             int inverseDenominatorLeadingTerm = field.inverse(denominatorLeadingTerm);\r
 223 \r
 224             while (remainder.getDegree() >= other.getDegree() && !remainder.isZero()) {\r
 225               int degreeDifference = remainder.getDegree() - other.getDegree();\r
 226               int scale = field.multiply(remainder.getCoefficient(remainder.getDegree()), inverseDenominatorLeadingTerm);\r
 227               GF256Poly term = other.multiplyByMonomial(degreeDifference, scale);\r
 228               GF256Poly iterationQuotient = field.buildMonomial(degreeDifference, scale);\r
 229               quotient = quotient.addOrSubtract(iterationQuotient);\r
 230               remainder = remainder.addOrSubtract(term);\r
 231             }\r
 232 \r
 233             return new GF256Poly[] { quotient, remainder };\r
 234           }\r
 235 \r
 236           public String toString() {\r
 237               StringBuilder result = new StringBuilder(8 * getDegree());\r
 238             for (int degree = getDegree(); degree >= 0; degree--) {\r
 239               int coefficient = getCoefficient(degree);\r
 240               if (coefficient != 0) {\r
 241                 if (coefficient < 0) {\r
 242                   result.Append(" - ");\r
 243                   coefficient = -coefficient;\r
 244                 } else {\r
 245                   if (result.Length > 0) {\r
 246                     result.Append(" + ");\r
 247                   }\r
 248                 }\r
 249                 if (degree == 0 || coefficient != 1) {\r
 250                   int alphaPower = field.log(coefficient);\r
 251                   if (alphaPower == 0) {\r
 252                     result.Append('1');\r
 253                   } else if (alphaPower == 1) {\r
 254                     result.Append('a');\r
 255                   } else {\r
 256                     result.Append("a^");\r
 257                     result.Append(alphaPower);\r
 258                   }\r
 259                 }\r
 260                 if (degree != 0) {\r
 261                   if (degree == 1) {\r
 262                     result.Append('x');\r
 263                   } else {\r
 264                     result.Append("x^");\r
 265                     result.Append(degree);\r
 266                   }\r
 267                 }\r
 268               }\r
 269             }\r
 270             return result.ToString();\r
 271           }\r
 272         \r
 273     }\r
 274 }