rxing/pdf417/decoder/ec/
error_correction.rs

1/*
2 * Copyright 2012 ZXing authors
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17use crate::{
18    common::Result,
19    pdf417::{decoder::ec::ModulusGF, pdf_417_common::NUMBER_OF_CODEWORDS},
20    Exceptions,
21};
22
23use super::ModulusPoly;
24
25use once_cell::sync::Lazy;
26
27// static ref PDF417_GF : Arc<&ModulusGF> =  Arc::new(&ModulusGF::new(NUMBER_OF_CODEWORDS, 3));
28static FLD_INTERIOR: Lazy<ModulusGF> = Lazy::new(|| ModulusGF::new(NUMBER_OF_CODEWORDS, 3));
29
30/*
31 * <p>PDF417 error correction implementation.</p>
32 *
33 * <p>This <a href="http://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction#Example">example</a>
34 * is quite useful in understanding the algorithm.</p>
35 *
36 * @author Sean Owen
37 * @see com.google.zxing.common.reedsolomon.ReedSolomonDecoder
38 */
39
40/**
41 * @param received received codewords
42 * @param numECCodewords number of those codewords used for EC
43 * @param erasures location of erasures
44 * @return number of errors
45 * @throws ChecksumException if errors cannot be corrected, maybe because of too many errors
46 */
47pub fn decode(received: &mut [u32], numECCodewords: u32, erasures: &mut [u32]) -> Result<usize> {
48    let field: &'static ModulusGF = &FLD_INTERIOR;
49    let poly = ModulusPoly::new(field, received.to_vec())?;
50    let mut S = vec![0u32; numECCodewords as usize];
51    let mut error = false;
52    for i in (1..=numECCodewords).rev() {
53        // for (int i = numECCodewords; i > 0; i--) {
54        let eval = poly.evaluateAt(field.exp(i));
55        S[(numECCodewords - i) as usize] = eval;
56        if eval != 0 {
57            error = true;
58        }
59    }
60
61    if !error {
62        return Ok(0);
63    }
64
65    let mut knownErrors: ModulusPoly = ModulusPoly::getOne(field);
66    let mut b;
67    let mut term;
68    let mut kE: ModulusPoly;
69    if !erasures.is_empty() {
70        for erasure in erasures {
71            // for (int erasure : erasures) {
72            b = field.exp(received.len() as u32 - 1 - *erasure);
73            // Add (1 - bx) term:
74            term = ModulusPoly::new(field, vec![field.subtract(0, b), 1])?;
75            kE = knownErrors.clone();
76            knownErrors = kE.multiply(term)?;
77        }
78    }
79
80    let syndrome = ModulusPoly::new(field, S)?;
81    //syndrome = syndrome.multiply(knownErrors);
82
83    let sigmaOmega = runEuclideanAlgorithm(
84        ModulusPoly::buildMonomial(field, numECCodewords as usize, 1),
85        syndrome,
86        numECCodewords,
87        field,
88    )?;
89    let sigma = sigmaOmega[0].clone();
90    let omega = sigmaOmega[1].clone();
91
92    //sigma = sigma.multiply(knownErrors);
93
94    let mut errorLocations = findErrorLocations(sigma.clone(), field)?;
95    let errorMagnitudes = findErrorMagnitudes(omega, sigma, &mut errorLocations, field);
96
97    for i in 0..errorLocations.len() {
98        // for (int i = 0; i < errorLocations.length; i++) {
99        let position = received.len() as isize - 1 - field.log(errorLocations[i])? as isize;
100        if position < 0 {
101            return Err(Exceptions::checksum_with(file!()));
102        }
103        received[position as usize] =
104            field.subtract(received[position as usize], errorMagnitudes[i]);
105    }
106
107    Ok(errorLocations.len())
108}
109
110fn runEuclideanAlgorithm(
111    a: ModulusPoly,
112    b: ModulusPoly,
113    R: u32,
114    field: &'static ModulusGF,
115) -> Result<[ModulusPoly; 2]> {
116    // Assume a's degree is >= b's
117    let mut a = a;
118    let mut b = b;
119    if a.getDegree() < b.getDegree() {
120        std::mem::swap(&mut a, &mut b);
121    }
122
123    let mut rLast = a;
124    let mut r = b;
125    let mut tLast = ModulusPoly::getZero(field);
126    let mut t = ModulusPoly::getOne(field);
127
128    // Run Euclidean algorithm until r's degree is less than R/2
129    while r.getDegree() >= R / 2 {
130        let rLastLast = rLast.clone();
131        let tLastLast = tLast.clone();
132        rLast = r;
133        tLast = t;
134
135        // Divide rLastLast by rLast, with quotient in q and remainder in r
136        if rLast.isZero() {
137            // Oops, Euclidean algorithm already terminated?
138            return Err(Exceptions::checksum_with(file!()));
139        }
140        r = rLastLast;
141        let mut q = ModulusPoly::getZero(field); //field.getZero();
142        let denominatorLeadingTerm = rLast.getCoefficient(rLast.getDegree() as usize);
143        let dltInverse = field.inverse(denominatorLeadingTerm)?;
144        while r.getDegree() >= rLast.getDegree() && !r.isZero() {
145            let degreeDiff = r.getDegree() - rLast.getDegree();
146            let scale = field.multiply(r.getCoefficient(r.getDegree() as usize), dltInverse);
147            q = q.add(ModulusPoly::buildMonomial(
148                field,
149                degreeDiff as usize,
150                scale,
151            ))?;
152            r = r.subtract(rLast.multiplyByMonomial(degreeDiff as usize, scale))?;
153        }
154
155        t = q.multiply(tLast.clone())?.subtract(tLastLast)?.negative();
156    }
157
158    let sigmaTildeAtZero = t.getCoefficient(0);
159    if sigmaTildeAtZero == 0 {
160        return Err(Exceptions::checksum_with(file!()));
161    }
162
163    let inverse = field.inverse(sigmaTildeAtZero)?;
164    let sigma = t.multiplyByScaler(inverse);
165    let omega = r.multiplyByScaler(inverse);
166
167    Ok([sigma, omega])
168}
169
170fn findErrorLocations(errorLocator: ModulusPoly, field: &ModulusGF) -> Result<Vec<u32>> {
171    // This is a direct application of Chien's search
172    let numErrors = errorLocator.getDegree();
173    let mut result = vec![0u32; numErrors as usize];
174    let mut e = 0;
175    let mut i = 1;
176    while i < field.getSize() && e < numErrors {
177        // for (int i = 1; i < PDF417_GF.getSize() && e < numErrors; i++) {
178        if errorLocator.evaluateAt(i) == 0 {
179            result[e as usize] = field.inverse(i)?;
180            e += 1;
181        }
182        i += 1;
183    }
184    if e != numErrors {
185        return Err(Exceptions::checksum_with(file!()));
186    }
187    Ok(result)
188}
189
190fn findErrorMagnitudes(
191    errorEvaluator: ModulusPoly,
192    errorLocator: ModulusPoly,
193    errorLocations: &mut [u32],
194    field: &'static ModulusGF,
195) -> Vec<u32> {
196    let errorLocatorDegree = errorLocator.getDegree();
197    if errorLocatorDegree < 1 {
198        return vec![0; 0];
199    }
200    let mut formalDerivativeCoefficients = vec![0u32; errorLocatorDegree as usize];
201    for i in 1..=errorLocatorDegree {
202        // for (int i = 1; i <= errorLocatorDegree; i++) {
203        formalDerivativeCoefficients[errorLocatorDegree as usize - i as usize] =
204            field.multiply(i, errorLocator.getCoefficient(i as usize));
205    }
206    let formalDerivative =
207        ModulusPoly::new(field, formalDerivativeCoefficients).expect("should generate good poly");
208
209    // This is directly applying Forney's Formula
210    let s = errorLocations.len();
211    let mut result = vec![0u32; s];
212    for i in 0..s {
213        // for (int i = 0; i < s; i++) {
214        let xiInverse = field.inverse(errorLocations[i]).expect("must invert");
215        let numerator = field.subtract(0, errorEvaluator.evaluateAt(xiInverse));
216        let denominator = field
217            .inverse(formalDerivative.evaluateAt(xiInverse))
218            .expect("must invert");
219        result[i] = field.multiply(numerator, denominator);
220    }
221
222    result
223}
rxing/pdf417/decoder/ec/error_correction.rs

rxing/pdf417/decoder/ec/
error_correction.rs
