csharp/common/reedsolomon/GF256Poly.cs

   1 /*\r
   2 * Copyright 2007 ZXing authors\r
   3 *\r
   4 * Licensed under the Apache License, Version 2.0 (the "License");\r
   5 * you may not use this file except in compliance with the License.\r
   6 * You may obtain a copy of the License at\r
   7 *\r
   8 *      http://www.apache.org/licenses/LICENSE-2.0\r
   9 *\r
  10 * Unless required by applicable law or agreed to in writing, software\r
  11 * distributed under the License is distributed on an "AS IS" BASIS,\r
  12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\r
  13 * See the License for the specific language governing permissions and\r
  14 * limitations under the License.\r
  15 */\r
  16 using System;\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>  Sean Owen\r
  28         /// </author>\r
  29         /// <author>www.Redivivus.in (suraj.supekar@redivivus.in) - Ported from ZXING Java Source \r
  30         /// </author>\r
  31         sealed class GF256Poly\r
  32         {\r
  33                 internal int[] Coefficients\r
  34                 {\r
  35                         get\r
  36                         {\r
  37                                 return coefficients;\r
  38                         }\r
  39                         \r
  40                 }\r
  41                 /// <returns> degree of this polynomial\r
  42                 /// </returns>\r
  43                 internal int Degree\r
  44                 {\r
  45                         get\r
  46                         {\r
  47                                 return coefficients.Length - 1;\r
  48                         }\r
  49                         \r
  50                 }\r
  51                 /// <returns> true iff this polynomial is the monomial "0"\r
  52                 /// </returns>\r
  53                 internal bool Zero\r
  54                 {\r
  55                         get\r
  56                         {\r
  57                                 return coefficients[0] == 0;\r
  58                         }\r
  59                         \r
  60                 }\r
  61                 \r
  62                 //UPGRADE_NOTE: Final was removed from the declaration of 'field '. "ms-help://MS.VSCC.v80/dv_commoner/local/redirect.htm?index='!DefaultContextWindowIndex'&keyword='jlca1003'"\r
  63                 private GF256 field;\r
  64                 //UPGRADE_NOTE: Final was removed from the declaration of 'coefficients '. "ms-help://MS.VSCC.v80/dv_commoner/local/redirect.htm?index='!DefaultContextWindowIndex'&keyword='jlca1003'"\r
  65                 private int[] coefficients;\r
  66                 \r
  67                 /// <param name="field">the {@link GF256} instance representing the field to use\r
  68                 /// to perform computations\r
  69                 /// </param>\r
  70                 /// <param name="coefficients">coefficients as ints representing elements of GF(256), arranged\r
  71                 /// from most significant (highest-power term) coefficient to least significant\r
  72                 /// </param>\r
  73                 /// <throws>  IllegalArgumentException if argument is null or empty, </throws>\r
  74                 /// <summary> or if leading coefficient is 0 and this is not a\r
  75                 /// constant polynomial (that is, it is not the monomial "0")\r
  76                 /// </summary>\r
  77                 internal GF256Poly(GF256 field, int[] coefficients)\r
  78                 {\r
  79                         if (coefficients == null || coefficients.Length == 0)\r
  80                         {\r
  81                                 throw new System.ArgumentException();\r
  82                         }\r
  83                         this.field = field;\r
  84                         int coefficientsLength = coefficients.Length;\r
  85                         if (coefficientsLength > 1 && coefficients[0] == 0)\r
  86                         {\r
  87                                 // Leading term must be non-zero for anything except the constant polynomial "0"\r
  88                                 int firstNonZero = 1;\r
  89                                 while (firstNonZero < coefficientsLength && coefficients[firstNonZero] == 0)\r
  90                                 {\r
  91                                         firstNonZero++;\r
  92                                 }\r
  93                                 if (firstNonZero == coefficientsLength)\r
  94                                 {\r
  95                                         this.coefficients = field.Zero.coefficients;\r
  96                                 }\r
  97                                 else\r
  98                                 {\r
  99                                         this.coefficients = new int[coefficientsLength - firstNonZero];\r
 100                                         Array.Copy(coefficients, firstNonZero, this.coefficients, 0, this.coefficients.Length);\r
 101                                 }\r
 102                         }\r
 103                         else\r
 104                         {\r
 105                                 this.coefficients = coefficients;\r
 106                         }\r
 107                 }\r
 108                 \r
 109                 /// <returns> coefficient of x^degree term in this polynomial\r
 110                 /// </returns>\r
 111                 internal int getCoefficient(int degree)\r
 112                 {\r
 113                         return coefficients[coefficients.Length - 1 - degree];\r
 114                 }\r
 115                 \r
 116                 /// <returns> evaluation of this polynomial at a given point\r
 117                 /// </returns>\r
 118                 internal int evaluateAt(int a)\r
 119                 {\r
 120                         if (a == 0)\r
 121                         {\r
 122                                 // Just return the x^0 coefficient\r
 123                                 return getCoefficient(0);\r
 124                         }\r
 125                         int size = coefficients.Length;\r
 126                         if (a == 1)\r
 127                         {\r
 128                                 // Just the sum of the coefficients\r
 129                                 int result = 0;\r
 130                                 for (int i = 0; i < size; i++)\r
 131                                 {\r
 132                                         result = GF256.addOrSubtract(result, coefficients[i]);\r
 133                                 }\r
 134                                 return result;\r
 135                         }\r
 136                         int result2 = coefficients[0];\r
 137                         for (int i = 1; i < size; i++)\r
 138                         {\r
 139                                 result2 = GF256.addOrSubtract(field.multiply(a, result2), coefficients[i]);\r
 140                         }\r
 141                         return result2;\r
 142                 }\r
 143                 \r
 144                 internal GF256Poly addOrSubtract(GF256Poly other)\r
 145                 {\r
 146                         if (!field.Equals(other.field))\r
 147                         {\r
 148                                 throw new System.ArgumentException("GF256Polys do not have same GF256 field");\r
 149                         }\r
 150                         if (Zero)\r
 151                         {\r
 152                                 return other;\r
 153                         }\r
 154                         if (other.Zero)\r
 155                         {\r
 156                                 return this;\r
 157                         }\r
 158                         \r
 159                         int[] smallerCoefficients = this.coefficients;\r
 160                         int[] largerCoefficients = other.coefficients;\r
 161                         if (smallerCoefficients.Length > largerCoefficients.Length)\r
 162                         {\r
 163                                 int[] temp = smallerCoefficients;\r
 164                                 smallerCoefficients = largerCoefficients;\r
 165                                 largerCoefficients = temp;\r
 166                         }\r
 167                         int[] sumDiff = new int[largerCoefficients.Length];\r
 168                         int lengthDiff = largerCoefficients.Length - smallerCoefficients.Length;\r
 169                         // Copy high-order terms only found in higher-degree polynomial's coefficients\r
 170                         Array.Copy(largerCoefficients, 0, sumDiff, 0, lengthDiff);\r
 171                         \r
 172                         for (int i = lengthDiff; i < largerCoefficients.Length; i++)\r
 173                         {\r
 174                                 sumDiff[i] = GF256.addOrSubtract(smallerCoefficients[i - lengthDiff], largerCoefficients[i]);\r
 175                         }\r
 176                         \r
 177                         return new GF256Poly(field, sumDiff);\r
 178                 }\r
 179                 \r
 180                 internal GF256Poly multiply(GF256Poly other)\r
 181                 {\r
 182                         if (!field.Equals(other.field))\r
 183                         {\r
 184                                 throw new System.ArgumentException("GF256Polys do not have same GF256 field");\r
 185                         }\r
 186                         if (Zero || other.Zero)\r
 187                         {\r
 188                                 return field.Zero;\r
 189                         }\r
 190                         int[] aCoefficients = this.coefficients;\r
 191                         int aLength = aCoefficients.Length;\r
 192                         int[] bCoefficients = other.coefficients;\r
 193                         int bLength = bCoefficients.Length;\r
 194                         int[] product = new int[aLength + bLength - 1];\r
 195                         for (int i = 0; i < aLength; i++)\r
 196                         {\r
 197                                 int aCoeff = aCoefficients[i];\r
 198                                 for (int j = 0; j < bLength; j++)\r
 199                                 {\r
 200                                         product[i + j] = GF256.addOrSubtract(product[i + j], field.multiply(aCoeff, bCoefficients[j]));\r
 201                                 }\r
 202                         }\r
 203                         return new GF256Poly(field, product);\r
 204                 }\r
 205                 \r
 206                 internal GF256Poly multiply(int scalar)\r
 207                 {\r
 208                         if (scalar == 0)\r
 209                         {\r
 210                                 return field.Zero;\r
 211                         }\r
 212                         if (scalar == 1)\r
 213                         {\r
 214                                 return this;\r
 215                         }\r
 216                         int size = coefficients.Length;\r
 217                         int[] product = new int[size];\r
 218                         for (int i = 0; i < size; i++)\r
 219                         {\r
 220                                 product[i] = field.multiply(coefficients[i], scalar);\r
 221                         }\r
 222                         return new GF256Poly(field, product);\r
 223                 }\r
 224                 \r
 225                 internal GF256Poly multiplyByMonomial(int degree, int coefficient)\r
 226                 {\r
 227                         if (degree < 0)\r
 228                         {\r
 229                                 throw new System.ArgumentException();\r
 230                         }\r
 231                         if (coefficient == 0)\r
 232                         {\r
 233                                 return field.Zero;\r
 234                         }\r
 235                         int size = coefficients.Length;\r
 236                         int[] product = new int[size + degree];\r
 237                         for (int i = 0; i < size; i++)\r
 238                         {\r
 239                                 product[i] = field.multiply(coefficients[i], coefficient);\r
 240                         }\r
 241                         return new GF256Poly(field, product);\r
 242                 }\r
 243                 \r
 244                 internal GF256Poly[] divide(GF256Poly other)\r
 245                 {\r
 246                         if (!field.Equals(other.field))\r
 247                         {\r
 248                                 throw new System.ArgumentException("GF256Polys do not have same GF256 field");\r
 249                         }\r
 250                         if (other.Zero)\r
 251                         {\r
 252                                 throw new System.ArgumentException("Divide by 0");\r
 253                         }\r
 254                         \r
 255                         GF256Poly quotient = field.Zero;\r
 256                         GF256Poly remainder = this;\r
 257                         \r
 258                         int denominatorLeadingTerm = other.getCoefficient(other.Degree);\r
 259                         int inverseDenominatorLeadingTerm = field.inverse(denominatorLeadingTerm);\r
 260                         \r
 261                         while (remainder.Degree >= other.Degree && !remainder.Zero)\r
 262                         {\r
 263                                 int degreeDifference = remainder.Degree - other.Degree;\r
 264                                 int scale = field.multiply(remainder.getCoefficient(remainder.Degree), inverseDenominatorLeadingTerm);\r
 265                                 GF256Poly term = other.multiplyByMonomial(degreeDifference, scale);\r
 266                                 GF256Poly iterationQuotient = field.buildMonomial(degreeDifference, scale);\r
 267                                 quotient = quotient.addOrSubtract(iterationQuotient);\r
 268                                 remainder = remainder.addOrSubtract(term);\r
 269                         }\r
 270                         \r
 271                         return new GF256Poly[]{quotient, remainder};\r
 272                 }\r
 273                 \r
 274                 public override System.String ToString()\r
 275                 {\r
 276                         System.Text.StringBuilder result = new System.Text.StringBuilder(8 * Degree);\r
 277                         for (int degree = Degree; degree >= 0; degree--)\r
 278                         {\r
 279                                 int coefficient = getCoefficient(degree);\r
 280                                 if (coefficient != 0)\r
 281                                 {\r
 282                                         if (coefficient < 0)\r
 283                                         {\r
 284                                                 result.Append(" - ");\r
 285                                                 coefficient = - coefficient;\r
 286                                         }\r
 287                                         else\r
 288                                         {\r
 289                                                 if (result.Length > 0)\r
 290                                                 {\r
 291                                                         result.Append(" + ");\r
 292                                                 }\r
 293                                         }\r
 294                                         if (degree == 0 || coefficient != 1)\r
 295                                         {\r
 296                                                 int alphaPower = field.log(coefficient);\r
 297                                                 if (alphaPower == 0)\r
 298                                                 {\r
 299                                                         result.Append('1');\r
 300                                                 }\r
 301                                                 else if (alphaPower == 1)\r
 302                                                 {\r
 303                                                         result.Append('a');\r
 304                                                 }\r
 305                                                 else\r
 306                                                 {\r
 307                                                         result.Append("a^");\r
 308                                                         result.Append(alphaPower);\r
 309                                                 }\r
 310                                         }\r
 311                                         if (degree != 0)\r
 312                                         {\r
 313                                                 if (degree == 1)\r
 314                                                 {\r
 315                                                         result.Append('x');\r
 316                                                 }\r
 317                                                 else\r
 318                                                 {\r
 319                                                         result.Append("x^");\r
 320                                                         result.Append(degree);\r
 321                                                 }\r
 322                                         }\r
 323                                 }\r
 324                         }\r
 325                         return result.ToString();\r
 326                 }\r
 327         }\r
 328 }