Houjie
2025-07-24 52a3ff1bce1417b39f6872d8e8cb378e9c2ccc6f
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
"use strict";
/*
* Copyright 2012 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.
*/
var __values = (this && this.__values) || function(o) {
    var s = typeof Symbol === "function" && Symbol.iterator, m = s && o[s], i = 0;
    if (m) return m.call(o);
    if (o && typeof o.length === "number") return {
        next: function () {
            if (o && i >= o.length) o = void 0;
            return { value: o && o[i++], done: !o };
        }
    };
    throw new TypeError(s ? "Object is not iterable." : "Symbol.iterator is not defined.");
};
Object.defineProperty(exports, "__esModule", { value: true });
// package com.google.zxing.pdf417.decoder.ec;
// import com.google.zxing.ChecksumException;
var ChecksumException_1 = require("../../../ChecksumException");
var ModulusPoly_1 = require("./ModulusPoly");
var ModulusGF_1 = require("./ModulusGF");
/**
 * <p>PDF417 error correction implementation.</p>
 *
 * <p>This <a href="http://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction#Example">example</a>
 * is quite useful in understanding the algorithm.</p>
 *
 * @author Sean Owen
 * @see com.google.zxing.common.reedsolomon.ReedSolomonDecoder
 */
var ErrorCorrection = /** @class */ (function () {
    function ErrorCorrection() {
        this.field = ModulusGF_1.default.PDF417_GF;
    }
    /**
     * @param received received codewords
     * @param numECCodewords number of those codewords used for EC
     * @param erasures location of erasures
     * @return number of errors
     * @throws ChecksumException if errors cannot be corrected, maybe because of too many errors
     */
    ErrorCorrection.prototype.decode = function (received, numECCodewords, erasures) {
        var e_1, _a;
        var poly = new ModulusPoly_1.default(this.field, received);
        var S = new Int32Array(numECCodewords);
        var error = false;
        for (var i /*int*/ = numECCodewords; i > 0; i--) {
            var evaluation = poly.evaluateAt(this.field.exp(i));
            S[numECCodewords - i] = evaluation;
            if (evaluation !== 0) {
                error = true;
            }
        }
        if (!error) {
            return 0;
        }
        var knownErrors = this.field.getOne();
        if (erasures != null) {
            try {
                for (var erasures_1 = __values(erasures), erasures_1_1 = erasures_1.next(); !erasures_1_1.done; erasures_1_1 = erasures_1.next()) {
                    var erasure = erasures_1_1.value;
                    var b = this.field.exp(received.length - 1 - erasure);
                    // Add (1 - bx) term:
                    var term = new ModulusPoly_1.default(this.field, new Int32Array([this.field.subtract(0, b), 1]));
                    knownErrors = knownErrors.multiply(term);
                }
            }
            catch (e_1_1) { e_1 = { error: e_1_1 }; }
            finally {
                try {
                    if (erasures_1_1 && !erasures_1_1.done && (_a = erasures_1.return)) _a.call(erasures_1);
                }
                finally { if (e_1) throw e_1.error; }
            }
        }
        var syndrome = new ModulusPoly_1.default(this.field, S);
        // syndrome = syndrome.multiply(knownErrors);
        var sigmaOmega = this.runEuclideanAlgorithm(this.field.buildMonomial(numECCodewords, 1), syndrome, numECCodewords);
        var sigma = sigmaOmega[0];
        var omega = sigmaOmega[1];
        // sigma = sigma.multiply(knownErrors);
        var errorLocations = this.findErrorLocations(sigma);
        var errorMagnitudes = this.findErrorMagnitudes(omega, sigma, errorLocations);
        for (var i /*int*/ = 0; i < errorLocations.length; i++) {
            var position = received.length - 1 - this.field.log(errorLocations[i]);
            if (position < 0) {
                throw ChecksumException_1.default.getChecksumInstance();
            }
            received[position] = this.field.subtract(received[position], errorMagnitudes[i]);
        }
        return errorLocations.length;
    };
    /**
     *
     * @param ModulusPoly
     * @param a
     * @param ModulusPoly
     * @param b
     * @param int
     * @param R
     * @throws ChecksumException
     */
    ErrorCorrection.prototype.runEuclideanAlgorithm = function (a, b, R) {
        // Assume a's degree is >= b's
        if (a.getDegree() < b.getDegree()) {
            var temp = a;
            a = b;
            b = temp;
        }
        var rLast = a;
        var r = b;
        var tLast = this.field.getZero();
        var t = this.field.getOne();
        // Run Euclidean algorithm until r's degree is less than R/2
        while (r.getDegree() >= Math.round(R / 2)) {
            var rLastLast = rLast;
            var 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 ChecksumException_1.default.getChecksumInstance();
            }
            r = rLastLast;
            var q = this.field.getZero();
            var denominatorLeadingTerm = rLast.getCoefficient(rLast.getDegree());
            var dltInverse = this.field.inverse(denominatorLeadingTerm);
            while (r.getDegree() >= rLast.getDegree() && !r.isZero()) {
                var degreeDiff = r.getDegree() - rLast.getDegree();
                var scale = this.field.multiply(r.getCoefficient(r.getDegree()), dltInverse);
                q = q.add(this.field.buildMonomial(degreeDiff, scale));
                r = r.subtract(rLast.multiplyByMonomial(degreeDiff, scale));
            }
            t = q.multiply(tLast).subtract(tLastLast).negative();
        }
        var sigmaTildeAtZero = t.getCoefficient(0);
        if (sigmaTildeAtZero === 0) {
            throw ChecksumException_1.default.getChecksumInstance();
        }
        var inverse = this.field.inverse(sigmaTildeAtZero);
        var sigma = t.multiply(inverse);
        var omega = r.multiply(inverse);
        return [sigma, omega];
    };
    /**
     *
     * @param errorLocator
     * @throws ChecksumException
     */
    ErrorCorrection.prototype.findErrorLocations = function (errorLocator) {
        // This is a direct application of Chien's search
        var numErrors = errorLocator.getDegree();
        var result = new Int32Array(numErrors);
        var e = 0;
        for (var i /*int*/ = 1; i < this.field.getSize() && e < numErrors; i++) {
            if (errorLocator.evaluateAt(i) === 0) {
                result[e] = this.field.inverse(i);
                e++;
            }
        }
        if (e !== numErrors) {
            throw ChecksumException_1.default.getChecksumInstance();
        }
        return result;
    };
    ErrorCorrection.prototype.findErrorMagnitudes = function (errorEvaluator, errorLocator, errorLocations) {
        var errorLocatorDegree = errorLocator.getDegree();
        var formalDerivativeCoefficients = new Int32Array(errorLocatorDegree);
        for (var i /*int*/ = 1; i <= errorLocatorDegree; i++) {
            formalDerivativeCoefficients[errorLocatorDegree - i] =
                this.field.multiply(i, errorLocator.getCoefficient(i));
        }
        var formalDerivative = new ModulusPoly_1.default(this.field, formalDerivativeCoefficients);
        // This is directly applying Forney's Formula
        var s = errorLocations.length;
        var result = new Int32Array(s);
        for (var i /*int*/ = 0; i < s; i++) {
            var xiInverse = this.field.inverse(errorLocations[i]);
            var numerator = this.field.subtract(0, errorEvaluator.evaluateAt(xiInverse));
            var denominator = this.field.inverse(formalDerivative.evaluateAt(xiInverse));
            result[i] = this.field.multiply(numerator, denominator);
        }
        return result;
    };
    return ErrorCorrection;
}());
exports.default = ErrorCorrection;