website/includes/qrcodedecoder/Zxing/Common/Reedsolomon/ReedSolomonDecoder.php

<?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;
    }
}