rxing/common/reedsolomon/
reedsolomon_decoder.rs

1/*
2 * Copyright 2007 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
17//package com.google.zxing.common.reedsolomon;
18
19use crate::Exceptions;
20use crate::common::Result;
21
22use super::{GenericGF, GenericGFPoly, GenericGFRef};
23
24/**
25 * <p>Implements Reed-Solomon decoding, as the name implies.</p>
26 *
27 * <p>The algorithm will not be explained here, but the following references were helpful
28 * in creating this implementation:</p>
29 *
30 * <ul>
31 * <li>Bruce Maggs.
32 * <a href="http://www.cs.cmu.edu/afs/cs.cmu.edu/project/pscico-guyb/realworld/www/rs_decode.ps">
33 * "Decoding Reed-Solomon Codes"</a> (see discussion of Forney's Formula)</li>
34 * <li>J.I. Hall. <a href="www.mth.msu.edu/~jhall/classes/codenotes/GRS.pdf">
35 * "Chapter 5. Generalized Reed-Solomon Codes"</a>
36 * (see discussion of Euclidean algorithm)</li>
37 * </ul>
38 *
39 * <p>Much credit is due to William Rucklidge since portions of this code are an indirect
40 * port of his C++ Reed-Solomon implementation.</p>
41 *
42 * @author Sean Owen
43 * @author William Rucklidge
44 * @author sanfordsquires
45 */
46pub struct ReedSolomonDecoder {
47    field: GenericGFRef,
48}
49
50impl ReedSolomonDecoder {
51    pub const fn new(field: GenericGFRef) -> Self {
52        Self { field }
53    }
54
55    /**
56     * <p>Decodes given set of received codewords, which include both data and error-correction
57     * codewords. Really, this means it uses Reed-Solomon to detect and correct errors, in-place,
58     * in the input.</p>
59     *
60     * @param received data and error-correction codewords
61     * @param twoS number of error-correction codewords available
62     * @throws ReedSolomonException if decoding fails for any reason
63     */
64    pub fn decode(&self, received: &mut [i32], twoS: i32) -> Result<usize> {
65        let poly = GenericGFPoly::new(self.field, received)?;
66        let mut syndromeCoefficients = vec![0; twoS as usize];
67        let mut noError = true;
68        for i in 0..twoS {
69            //for (int i = 0; i < twoS; i++) {
70            let eval = poly.evaluateAt(self.field.exp(i + self.field.getGeneratorBase()) as usize);
71            let len = syndromeCoefficients.len();
72            syndromeCoefficients[len - 1 - i as usize] = eval;
73            if eval != 0 {
74                noError = false;
75            }
76        }
77        if noError {
78            return Ok(0);
79        }
80        let Ok(syndrome) = GenericGFPoly::new(self.field, &syndromeCoefficients) else {
81            return Err(Exceptions::REED_SOLOMON);
82        };
83        let sigmaOmega = self.runEuclideanAlgorithm(
84            &GenericGF::buildMonomial(self.field, twoS as usize, 1),
85            &syndrome,
86            twoS as usize,
87        )?;
88        let sigma = &sigmaOmega[0];
89        let omega = &sigmaOmega[1];
90        let errorLocations = self.findErrorLocations(sigma)?;
91        let errorMagnitudes = self.findErrorMagnitudes(omega, &errorLocations)?;
92        for (error_location, error_magnitude) in errorLocations.iter().zip(errorMagnitudes) {
93            // for i in 0..errorLocations.len() {
94            //for (int i = 0; i < errorLocations.length; i++) {
95            let log_value = self.field.log(*error_location as i32)?;
96            if log_value > received.len() as i32 - 1 {
97                return Err(Exceptions::reed_solomon_with("Bad error location"));
98            }
99            let position: isize = received.len() as isize - 1 - log_value as isize;
100            if position < 0 {
101                return Err(Exceptions::reed_solomon_with("Bad error location"));
102            }
103            received[position as usize] =
104                GenericGF::addOrSubtract(received[position as usize], error_magnitude);
105        }
106        Ok(errorLocations.len())
107    }
108
109    fn runEuclideanAlgorithm(
110        &self,
111        a: &GenericGFPoly,
112        b: &GenericGFPoly,
113        R: usize,
114    ) -> Result<Vec<GenericGFPoly>> {
115        // Assume a's degree is >= b's
116        let mut a = a.clone();
117        let mut b = b.clone();
118        if a.getDegree() < b.getDegree() {
119            std::mem::swap(&mut a, &mut b);
120        }
121
122        let mut rLast = a;
123        let mut r = b;
124        // let tLast = self.field.getZero();
125        // let t = self.field.getOne();
126        let mut tLast = rLast.getZero();
127        let mut t = rLast.getOne();
128
129        // Run Euclidean algorithm until r's degree is less than R/2
130        while 2 * r.getDegree() >= R {
131            let rLastLast = rLast;
132            let tLastLast = tLast;
133            rLast = r;
134            tLast = t;
135
136            // Divide rLastLast by rLast, with quotient in q and remainder in r
137            if rLast.isZero() {
138                // Oops, Euclidean algorithm already terminated?
139                return Err(Exceptions::reed_solomon_with("r_{i-1} was zero"));
140            }
141            r = rLastLast;
142            let mut q = r.getZero();
143            let denominatorLeadingTerm = rLast.getCoefficient(rLast.getDegree());
144            let dltInverse = self.field.inverse(denominatorLeadingTerm)?;
145            while r.getDegree() >= rLast.getDegree() && !r.isZero() {
146                let degreeDiff = r.getDegree() - rLast.getDegree();
147                let scale = self
148                    .field
149                    .multiply(r.getCoefficient(r.getDegree()), dltInverse);
150                q = q.addOrSubtract(&GenericGF::buildMonomial(self.field, degreeDiff, scale))?;
151                r = r.addOrSubtract(&rLast.multiply_by_monomial(degreeDiff, scale)?)?;
152            }
153
154            t = (q.multiply(&tLast)?).addOrSubtract(&tLastLast)?;
155
156            if r.getDegree() >= rLast.getDegree() {
157                return Err(Exceptions::reed_solomon_with(format!(
158                    "Division algorithm failed to reduce polynomial? r: {r}, rLast: {rLast}"
159                )));
160            }
161        }
162
163        let sigmaTildeAtZero = t.getCoefficient(0);
164        if sigmaTildeAtZero == 0 {
165            return Err(Exceptions::reed_solomon_with("sigmaTilde(0) was zero"));
166        }
167
168        let Ok(inverse) = self.field.inverse(sigmaTildeAtZero) else {
169            return Err(Exceptions::reed_solomon_with("ArithmetricException"));
170        };
171        let sigma = t.multiply_with_scalar(inverse);
172        let omega = r.multiply_with_scalar(inverse);
173        Ok(vec![sigma, omega])
174    }
175
176    fn findErrorLocations(&self, errorLocator: &GenericGFPoly) -> Result<Vec<usize>> {
177        // This is a direct application of Chien's search
178        let numErrors = errorLocator.getDegree();
179        if numErrors == 1 {
180            // shortcut
181            return Ok(vec![errorLocator.getCoefficient(1) as usize]);
182        }
183
184        let mut result: Vec<usize> = vec![0; numErrors];
185        let mut e = 0;
186        for i in 1..self.field.getSize() {
187            //for (int i = 1; i < field.getSize() && e < numErrors; i++) {
188            if e >= numErrors {
189                break;
190            }
191            if errorLocator.evaluateAt(i) == 0 {
192                result[e] = self.field.inverse(i as i32)? as usize;
193                e += 1;
194            }
195        }
196        if e != numErrors {
197            return Err(Exceptions::reed_solomon_with(
198                "Error locator degree does not match number of roots",
199            ));
200        }
201        Ok(result)
202    }
203
204    fn findErrorMagnitudes(
205        &self,
206        errorEvaluator: &GenericGFPoly,
207        errorLocations: &[usize],
208    ) -> Result<Vec<i32>> {
209        // This is directly applying Forney's Formula
210        let s = errorLocations.len();
211        let mut result = vec![0; s];
212        for i in 0..s {
213            //for (int i = 0; i < s; i++) {
214            let xiInverse = self.field.inverse(errorLocations[i] as i32)?;
215            let mut denominator = 1;
216            for (j, loc) in errorLocations.iter().enumerate().take(s) {
217                // for j in 0..s {
218                //for (int j = 0; j < s; j++) {
219                if i != j {
220                    //denominator = field.multiply(denominator,
221                    //    GenericGF.addOrSubtract(1, field.multiply(errorLocations[j], xiInverse)));
222                    // Above should work but fails on some Apple and Linux JDKs due to a Hotspot bug.
223                    // Below is a funny-looking workaround from Steven Parkes
224                    let term = self.field.multiply(*loc as i32, xiInverse);
225                    let termPlus1 = if (term & 0x1) == 0 {
226                        term | 1
227                    } else {
228                        term & !1
229                    };
230                    denominator = self.field.multiply(denominator, termPlus1);
231                }
232            }
233            result[i] = self.field.multiply(
234                errorEvaluator.evaluateAt(xiInverse as usize),
235                self.field.inverse(denominator)?,
236            );
237            if self.field.getGeneratorBase() != 0 {
238                result[i] = self.field.multiply(result[i], xiInverse);
239            }
240        }
241        Ok(result)
242    }
243}
rxing/common/reedsolomon/reedsolomon_decoder.rs

rxing/common/reedsolomon/
reedsolomon_decoder.rs
