Файловый менеджер - Редактировать - /home/lakoyani/lakoyani.com.fj/Reedsolomon.tar
Назад
ReedSolomonDecoder.php 0000777 00000017377 14711055570 0011024 0 ustar 00 <?php /* * Copyright 2007 ZXing authors * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */ namespace Zxing\Common\Reedsolomon; /** * <p>Implements Reed-Solomon decoding, as the name implies.</p> * * <p>The algorithm will not be explained here, but the following references were helpful * in creating this implementation:</p> * * <ul> * <li>Bruce Maggs. * <a href="http://www.cs.cmu.edu/afs/cs.cmu.edu/project/pscico-guyb/realworld/www/rs_decode.ps"> * "Decoding Reed-Solomon Codes"</a> (see discussion of Forney's Formula)</li> * <li>J.I. Hall. <a href="www.mth.msu.edu/~jhall/classes/codenotes/GRS.pdf"> * "Chapter 5. Generalized Reed-Solomon Codes"</a> * (see discussion of Euclidean algorithm)</li> * </ul> * * <p>Much credit is due to William Rucklidge since portions of this code are an indirect * port of his C++ Reed-Solomon implementation.</p> * * @author Sean Owen * @author William Rucklidge * @author sanfordsquires */ final class ReedSolomonDecoder { private $field; public function __construct($field) { $this->field = $field; } /** * <p>Decodes given set of received codewords, which include both data and error-correction * codewords. Really, this means it uses Reed-Solomon to detect and correct errors, in-place, * in the input.</p> * * @param received data and error-correction codewords * @param twoS number of error-correction codewords available * * @throws ReedSolomonException if decoding fails for any reason */ public function decode(&$received, $twoS) { $poly = new GenericGFPoly($this->field, $received); $syndromeCoefficients = fill_array(0, $twoS, 0); $noError = true; for ($i = 0; $i < $twoS; $i++) { $eval = $poly->evaluateAt($this->field->exp($i + $this->field->getGeneratorBase())); $syndromeCoefficients[count($syndromeCoefficients) - 1 - $i] = $eval; if ($eval != 0) { $noError = false; } } if ($noError) { return; } $syndrome = new GenericGFPoly($this->field, $syndromeCoefficients); $sigmaOmega = $this->runEuclideanAlgorithm($this->field->buildMonomial($twoS, 1), $syndrome, $twoS); $sigma = $sigmaOmega[0]; $omega = $sigmaOmega[1]; $errorLocations = $this->findErrorLocations($sigma); $errorMagnitudes = $this->findErrorMagnitudes($omega, $errorLocations); $errorLocationsCount = count($errorLocations); for ($i = 0; $i < $errorLocationsCount; $i++) { $position = count($received) - 1 - $this->field->log($errorLocations[$i]); if ($position < 0) { throw new ReedSolomonException("Bad error location"); } $received[$position] = GenericGF::addOrSubtract($received[$position], $errorMagnitudes[$i]); } } private function runEuclideanAlgorithm($a, $b, $R) { // Assume a's degree is >= b's if ($a->getDegree() < $b->getDegree()) { $temp = $a; $a = $b; $b = $temp; } $rLast = $a; $r = $b; $tLast = $this->field->getZero(); $t = $this->field->getOne(); // Run Euclidean algorithm until r's degree is less than R/2 while ($r->getDegree() >= $R / 2) { $rLastLast = $rLast; $tLastLast = $tLast; $rLast = $r; $tLast = $t; // Divide rLastLast by rLast, with quotient in q and remainder in r if ($rLast->isZero()) { // Oops, Euclidean algorithm already terminated? throw new ReedSolomonException("r_{i-1} was zero"); } $r = $rLastLast; $q = $this->field->getZero(); $denominatorLeadingTerm = $rLast->getCoefficient($rLast->getDegree()); $dltInverse = $this->field->inverse($denominatorLeadingTerm); while ($r->getDegree() >= $rLast->getDegree() && !$r->isZero()) { $degreeDiff = $r->getDegree() - $rLast->getDegree(); $scale = $this->field->multiply($r->getCoefficient($r->getDegree()), $dltInverse); $q = $q->addOrSubtract($this->field->buildMonomial($degreeDiff, $scale)); $r = $r->addOrSubtract($rLast->multiplyByMonomial($degreeDiff, $scale)); } $t = $q->multiply($tLast)->addOrSubtract($tLastLast); if ($r->getDegree() >= $rLast->getDegree()) { throw new ReedSolomonException("Division algorithm failed to reduce polynomial?"); } } $sigmaTildeAtZero = $t->getCoefficient(0); if ($sigmaTildeAtZero == 0) { throw new ReedSolomonException("sigmaTilde(0) was zero"); } $inverse = $this->field->inverse($sigmaTildeAtZero); $sigma = $t->multiply($inverse); $omega = $r->multiply($inverse); return [$sigma, $omega]; } private function findErrorLocations($errorLocator) { // This is a direct application of Chien's search $numErrors = $errorLocator->getDegree(); if ($numErrors == 1) { // shortcut return [$errorLocator->getCoefficient(1)]; } $result = fill_array(0, $numErrors, 0); $e = 0; for ($i = 1; $i < $this->field->getSize() && $e < $numErrors; $i++) { if ($errorLocator->evaluateAt($i) == 0) { $result[$e] = $this->field->inverse($i); $e++; } } if ($e != $numErrors) { throw new ReedSolomonException("Error locator degree does not match number of roots"); } return $result; } private function findErrorMagnitudes($errorEvaluator, $errorLocations) { // This is directly applying Forney's Formula $s = count($errorLocations); $result = fill_array(0, $s, 0); for ($i = 0; $i < $s; $i++) { $xiInverse = $this->field->inverse($errorLocations[$i]); $denominator = 1; for ($j = 0; $j < $s; $j++) { if ($i != $j) { //denominator = field.multiply(denominator, // GenericGF.addOrSubtract(1, field.multiply(errorLocations[j], xiInverse))); // Above should work but fails on some Apple and Linux JDKs due to a Hotspot bug. // Below is a funny-looking workaround from Steven Parkes $term = $this->field->multiply($errorLocations[$j], $xiInverse); $termPlus1 = ($term & 0x1) == 0 ? $term | 1 : $term & ~1; $denominator = $this->field->multiply($denominator, $termPlus1); } } $result[$i] = $this->field->multiply($errorEvaluator->evaluateAt($xiInverse), $this->field->inverse($denominator)); if ($this->field->getGeneratorBase() != 0) { $result[$i] = $this->field->multiply($result[$i], $xiInverse); } } return $result; } } ReedSolomonException.php 0000777 00000001512 14711055570 0011375 0 ustar 00 <?php /* * Copyright 2007 ZXing authors * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */ namespace Zxing\Common\Reedsolomon; /** * <p>Thrown when an exception occurs during Reed-Solomon decoding, such as when * there are too many errors to correct.</p> * * @author Sean Owen */ final class ReedSolomonException extends \Exception { } GenericGF.php 0000777 00000013141 14711055570 0007062 0 ustar 00 <?php /* * Copyright 2007 ZXing authors * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */ namespace Zxing\Common\Reedsolomon; /** * <p>This class contains utility methods for performing mathematical operations over * the Galois Fields. Operations use a given primitive polynomial in calculations.</p> * * <p>Throughout this package, elements of the GF are represented as an {@code int} * for convenience and speed (but at the cost of memory). * </p> * * @author Sean Owen * @author David Olivier */ final class GenericGF { public static $AZTEC_DATA_12; public static $AZTEC_DATA_10; public static $AZTEC_DATA_6; public static $AZTEC_PARAM; public static $QR_CODE_FIELD_256; public static $DATA_MATRIX_FIELD_256; public static $AZTEC_DATA_8; public static $MAXICODE_FIELD_64; private $expTable; private $logTable; private $zero; private $one; private $size; private $primitive; private $generatorBase; /** * Create a representation of GF(size) using the given primitive polynomial. * * @param primitive irreducible polynomial whose coefficients are represented by * the bits of an int, where the least-significant bit represents the constant * coefficient * @param size the size of the field * @param b the factor b in the generator polynomial can be 0- or 1-based * (g(x) = (x+a^b)(x+a^(b+1))...(x+a^(b+2t-1))). * In most cases it should be 1, but for QR code it is 0. */ public function __construct($primitive, $size, $b) { $this->primitive = $primitive; $this->size = $size; $this->generatorBase = $b; $this->expTable = []; $this->logTable = []; $x = 1; for ($i = 0; $i < $size; $i++) { $this->expTable[$i] = $x; $x *= 2; // we're assuming the generator alpha is 2 if ($x >= $size) { $x ^= $primitive; $x &= $size - 1; } } for ($i = 0; $i < $size - 1; $i++) { $this->logTable[$this->expTable[$i]] = $i; } // logTable[0] == 0 but this should never be used $this->zero = new GenericGFPoly($this, [0]); $this->one = new GenericGFPoly($this, [1]); } public static function Init() { self::$AZTEC_DATA_12 = new GenericGF(0x1069, 4096, 1); // x^12 + x^6 + x^5 + x^3 + 1 self::$AZTEC_DATA_10 = new GenericGF(0x409, 1024, 1); // x^10 + x^3 + 1 self::$AZTEC_DATA_6 = new GenericGF(0x43, 64, 1); // x^6 + x + 1 self::$AZTEC_PARAM = new GenericGF(0x13, 16, 1); // x^4 + x + 1 self::$QR_CODE_FIELD_256 = new GenericGF(0x011D, 256, 0); // x^8 + x^4 + x^3 + x^2 + 1 self::$DATA_MATRIX_FIELD_256 = new GenericGF(0x012D, 256, 1); // x^8 + x^5 + x^3 + x^2 + 1 self::$AZTEC_DATA_8 = self::$DATA_MATRIX_FIELD_256; self::$MAXICODE_FIELD_64 = self::$AZTEC_DATA_6; } /** * Implements both addition and subtraction -- they are the same in GF(size). * * @return sum/difference of a and b */ public static function addOrSubtract($a, $b) { return $a ^ $b; } public function getZero() { return $this->zero; } public function getOne() { return $this->one; } /** * @return the monomial representing coefficient * x^degree */ public function buildMonomial($degree, $coefficient) { if ($degree < 0) { throw new \InvalidArgumentException(); } if ($coefficient == 0) { return $this->zero; } $coefficients = fill_array(0, $degree + 1, 0);//new int[degree + 1]; $coefficients[0] = $coefficient; return new GenericGFPoly($this, $coefficients); } /** * @return 2 to the power of a in GF(size) */ public function exp($a) { return $this->expTable[$a]; } /** * @return base 2 log of a in GF(size) */ public function log($a) { if ($a == 0) { throw new \InvalidArgumentException(); } return $this->logTable[$a]; } /** * @return multiplicative inverse of a */ public function inverse($a) { if ($a == 0) { throw new \Exception(); } return $this->expTable[$this->size - $this->logTable[$a] - 1]; } /** * @return int product of a and b in GF(size) */ public function multiply($a, $b) { if ($a == 0 || $b == 0) { return 0; } return $this->expTable[($this->logTable[$a] + $this->logTable[$b]) % ($this->size - 1)]; } public function getSize() { return $this->size; } public function getGeneratorBase() { return $this->generatorBase; } // @Override public function toString() { return "GF(0x" . dechex((int)($this->primitive)) . ',' . $this->size . ')'; } } GenericGF::Init(); GenericGFPoly.php 0000777 00000023442 14711055570 0007733 0 ustar 00 <?php /* * Copyright 2007 ZXing authors * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */ namespace Zxing\Common\Reedsolomon; /** * <p>Represents a polynomial whose coefficients are elements of a GF. * Instances of this class are immutable.</p> * * <p>Much credit is due to William Rucklidge since portions of this code are an indirect * port of his C++ Reed-Solomon implementation.</p> * * @author Sean Owen */ final class GenericGFPoly { private $field; private $coefficients; /** * @param field the {@link GenericGF} instance representing the field to use * to perform computations * @param coefficients array coefficients as ints representing elements of GF(size), arranged * from most significant (highest-power term) coefficient to least significant * * @throws InvalidArgumentException if argument is null or empty, * or if leading coefficient is 0 and this is not a * constant polynomial (that is, it is not the monomial "0") */ public function __construct($field, $coefficients) { if (count($coefficients) == 0) { throw new \InvalidArgumentException(); } $this->field = $field; $coefficientsLength = count($coefficients); if ($coefficientsLength > 1 && $coefficients[0] == 0) { // Leading term must be non-zero for anything except the constant polynomial "0" $firstNonZero = 1; while ($firstNonZero < $coefficientsLength && $coefficients[$firstNonZero] == 0) { $firstNonZero++; } if ($firstNonZero == $coefficientsLength) { $this->coefficients = [0]; } else { $this->coefficients = fill_array(0, $coefficientsLength - $firstNonZero, 0); $this->coefficients = arraycopy($coefficients, $firstNonZero, $this->coefficients, 0, count($this->coefficients)); } } else { $this->coefficients = $coefficients; } } public function getCoefficients() { return $this->coefficients; } /** * @return evaluation of this polynomial at a given point */ public function evaluateAt($a) { if ($a == 0) { // Just return the x^0 coefficient return $this->getCoefficient(0); } $size = count($this->coefficients); if ($a == 1) { // Just the sum of the coefficients $result = 0; foreach ($this->coefficients as $coefficient) { $result = GenericGF::addOrSubtract($result, $coefficient); } return $result; } $result = $this->coefficients[0]; for ($i = 1; $i < $size; $i++) { $result = GenericGF::addOrSubtract($this->field->multiply($a, $result), $this->coefficients[$i]); } return $result; } /** * @return coefficient of x^degree term in this polynomial */ public function getCoefficient($degree) { return $this->coefficients[count($this->coefficients) - 1 - $degree]; } public function multiply($other) { if (is_int($other)) { return $this->multiply_($other); } if ($this->field !== $other->field) { throw new \InvalidArgumentException("GenericGFPolys do not have same GenericGF field"); } if ($this->isZero() || $other->isZero()) { return $this->field->getZero(); } $aCoefficients = $this->coefficients; $aLength = count($aCoefficients); $bCoefficients = $other->coefficients; $bLength = count($bCoefficients); $product = fill_array(0, $aLength + $bLength - 1, 0); for ($i = 0; $i < $aLength; $i++) { $aCoeff = $aCoefficients[$i]; for ($j = 0; $j < $bLength; $j++) { $product[$i + $j] = GenericGF::addOrSubtract($product[$i + $j], $this->field->multiply($aCoeff, $bCoefficients[$j])); } } return new GenericGFPoly($this->field, $product); } public function multiply_($scalar) { if ($scalar == 0) { return $this->field->getZero(); } if ($scalar == 1) { return $this; } $size = count($this->coefficients); $product = fill_array(0, $size, 0); for ($i = 0; $i < $size; $i++) { $product[$i] = $this->field->multiply($this->coefficients[$i], $scalar); } return new GenericGFPoly($this->field, $product); } /** * @return true iff this polynomial is the monomial "0" */ public function isZero() { return $this->coefficients[0] == 0; } public function multiplyByMonomial($degree, $coefficient) { if ($degree < 0) { throw new \InvalidArgumentException(); } if ($coefficient == 0) { return $this->field->getZero(); } $size = count($this->coefficients); $product = fill_array(0, $size + $degree, 0); for ($i = 0; $i < $size; $i++) { $product[$i] = $this->field->multiply($this->coefficients[$i], $coefficient); } return new GenericGFPoly($this->field, $product); } public function divide($other) { if ($this->field !== $other->field) { throw new \InvalidArgumentException("GenericGFPolys do not have same GenericGF field"); } if ($other->isZero()) { throw new \InvalidArgumentException("Divide by 0"); } $quotient = $this->field->getZero(); $remainder = $this; $denominatorLeadingTerm = $other->getCoefficient($other->getDegree()); $inverseDenominatorLeadingTerm = $this->field->inverse($denominatorLeadingTerm); while ($remainder->getDegree() >= $other->getDegree() && !$remainder->isZero()) { $degreeDifference = $remainder->getDegree() - $other->getDegree(); $scale = $this->field->multiply($remainder->getCoefficient($remainder->getDegree()), $inverseDenominatorLeadingTerm); $term = $other->multiplyByMonomial($degreeDifference, $scale); $iterationQuotient = $this->field->buildMonomial($degreeDifference, $scale); $quotient = $quotient->addOrSubtract($iterationQuotient); $remainder = $remainder->addOrSubtract($term); } return [$quotient, $remainder]; } /** * @return degree of this polynomial */ public function getDegree() { return count($this->coefficients) - 1; } public function addOrSubtract($other) { if ($this->field !== $other->field) { throw new \InvalidArgumentException("GenericGFPolys do not have same GenericGF field"); } if ($this->isZero()) { return $other; } if ($other->isZero()) { return $this; } $smallerCoefficients = $this->coefficients; $largerCoefficients = $other->coefficients; if (count($smallerCoefficients) > count($largerCoefficients)) { $temp = $smallerCoefficients; $smallerCoefficients = $largerCoefficients; $largerCoefficients = $temp; } $sumDiff = fill_array(0, count($largerCoefficients), 0); $lengthDiff = count($largerCoefficients) - count($smallerCoefficients); // Copy high-order terms only found in higher-degree polynomial's coefficients $sumDiff = arraycopy($largerCoefficients, 0, $sumDiff, 0, $lengthDiff); $countLargerCoefficients = count($largerCoefficients); for ($i = $lengthDiff; $i < $countLargerCoefficients; $i++) { $sumDiff[$i] = GenericGF::addOrSubtract($smallerCoefficients[$i - $lengthDiff], $largerCoefficients[$i]); } return new GenericGFPoly($this->field, $sumDiff); } //@Override public function toString() { $result = ''; for ($degree = $this->getDegree(); $degree >= 0; $degree--) { $coefficient = $this->getCoefficient($degree); if ($coefficient != 0) { if ($coefficient < 0) { $result .= " - "; $coefficient = -$coefficient; } else { if (strlen($result) > 0) { $result .= " + "; } } if ($degree == 0 || $coefficient != 1) { $alphaPower = $this->field->log($coefficient); if ($alphaPower == 0) { $result .= '1'; } else if ($alphaPower == 1) { $result .= 'a'; } else { $result .= "a^"; $result .= ($alphaPower); } } if ($degree != 0) { if ($degree == 1) { $result .= 'x'; } else { $result .= "x^"; $result .= $degree; } } } } return $result; } }
| ver. 1.4 |
Github
|
.
| PHP 7.4.33 | Генерация страницы: 0 |
proxy
|
phpinfo
|
Настройка