/*
|
* 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.
|
*/
|
|
#import "ZXIntArray.h"
|
#import "ZXModulusGF.h"
|
#import "ZXModulusPoly.h"
|
#import "ZXPDF417ECErrorCorrection.h"
|
|
@interface ZXPDF417ECErrorCorrection ()
|
|
@property (nonatomic, strong, readonly) ZXModulusGF *field;
|
|
@end
|
|
@implementation ZXPDF417ECErrorCorrection
|
|
- (id)init {
|
if (self = [super init]) {
|
_field = [ZXModulusGF PDF417_GF];
|
}
|
|
return self;
|
}
|
|
- (int)decode:(ZXIntArray *)received numECCodewords:(int)numECCodewords erasures:(ZXIntArray *)erasures {
|
ZXModulusPoly *poly = [[ZXModulusPoly alloc] initWithField:self.field coefficients:received];
|
ZXIntArray *S = [[ZXIntArray alloc] initWithLength:numECCodewords];
|
BOOL error = NO;
|
for (int i = numECCodewords; i > 0; i--) {
|
int eval = [poly evaluateAt:[self.field exp:i]];
|
S.array[numECCodewords - i] = eval;
|
if (eval != 0) {
|
error = YES;
|
}
|
}
|
|
if (!error) {
|
return 0;
|
}
|
|
ZXModulusPoly *knownErrors = self.field.one;
|
if (erasures) {
|
for (int i = 0; i < erasures.length; i++) {
|
int erasure = erasures.array[i];
|
int b = [self.field exp:received.length - 1 - erasure];
|
// Add (1 - bx) term:
|
ZXModulusPoly *term = [[ZXModulusPoly alloc] initWithField:self.field coefficients:[[ZXIntArray alloc] initWithInts:[self.field subtract:0 b:b], 1, -1]];
|
knownErrors = [knownErrors multiply:term];
|
}
|
}
|
|
ZXModulusPoly *syndrome = [[ZXModulusPoly alloc] initWithField:self.field coefficients:S];
|
//[syndrome multiply:knownErrors];
|
|
NSArray *sigmaOmega = [self runEuclideanAlgorithm:[self.field buildMonomial:numECCodewords coefficient:1] b:syndrome R:numECCodewords];
|
if (!sigmaOmega) {
|
return -1;
|
}
|
|
ZXModulusPoly *sigma = sigmaOmega[0];
|
ZXModulusPoly *omega = sigmaOmega[1];
|
|
//sigma = [sigma multiply:knownErrors];
|
|
ZXIntArray *errorLocations = [self findErrorLocations:sigma];
|
if (!errorLocations) {
|
return -1;
|
}
|
ZXIntArray *errorMagnitudes = [self findErrorMagnitudes:omega errorLocator:sigma errorLocations:errorLocations];
|
|
for (int i = 0; i < errorLocations.length; i++) {
|
int position = received.length - 1 - [self.field log:errorLocations.array[i]];
|
if (position < 0) {
|
return -1;
|
}
|
received.array[position] = [self.field subtract:received.array[position] b:errorMagnitudes.array[i]];
|
}
|
|
return errorLocations.length;
|
}
|
|
- (NSArray *)runEuclideanAlgorithm:(ZXModulusPoly *)a b:(ZXModulusPoly *)b R:(int)R {
|
// Assume a's degree is >= b's
|
if (a.degree < b.degree) {
|
ZXModulusPoly *temp = a;
|
a = b;
|
b = temp;
|
}
|
|
ZXModulusPoly *rLast = a;
|
ZXModulusPoly *r = b;
|
ZXModulusPoly *tLast = self.field.zero;
|
ZXModulusPoly *t = self.field.one;
|
|
// Run Euclidean algorithm until r's degree is less than R/2
|
while (r.degree >= R / 2) {
|
ZXModulusPoly *rLastLast = rLast;
|
ZXModulusPoly *tLastLast = tLast;
|
rLast = r;
|
tLast = t;
|
|
// Divide rLastLast by rLast, with quotient in q and remainder in r
|
if (rLast.zero) {
|
// Oops, Euclidean algorithm already terminated?
|
return nil;
|
}
|
r = rLastLast;
|
ZXModulusPoly *q = self.field.zero;
|
int denominatorLeadingTerm = [rLast coefficient:rLast.degree];
|
int dltInverse = [self.field inverse:denominatorLeadingTerm];
|
while (r.degree >= rLast.degree && !r.zero) {
|
int degreeDiff = r.degree - rLast.degree;
|
int scale = [self.field multiply:[r coefficient:r.degree] b:dltInverse];
|
q = [q add:[self.field buildMonomial:degreeDiff coefficient:scale]];
|
r = [r subtract:[rLast multiplyByMonomial:degreeDiff coefficient:scale]];
|
}
|
|
t = [[[q multiply:tLast] subtract:tLastLast] negative];
|
}
|
|
int sigmaTildeAtZero = [t coefficient:0];
|
if (sigmaTildeAtZero == 0) {
|
return nil;
|
}
|
|
int inverse = [self.field inverse:sigmaTildeAtZero];
|
ZXModulusPoly *sigma = [t multiplyScalar:inverse];
|
ZXModulusPoly *omega = [r multiplyScalar:inverse];
|
return @[sigma, omega];
|
}
|
|
- (ZXIntArray *)findErrorLocations:(ZXModulusPoly *)errorLocator {
|
// This is a direct application of Chien's search
|
int numErrors = errorLocator.degree;
|
ZXIntArray *result = [[ZXIntArray alloc] initWithLength:numErrors];
|
int e = 0;
|
for (int i = 1; i < self.field.size && e < numErrors; i++) {
|
if ([errorLocator evaluateAt:i] == 0) {
|
result.array[e] = [self.field inverse:i];
|
e++;
|
}
|
}
|
if (e != numErrors) {
|
return nil;
|
}
|
return result;
|
}
|
|
- (ZXIntArray *)findErrorMagnitudes:(ZXModulusPoly *)errorEvaluator errorLocator:(ZXModulusPoly *)errorLocator errorLocations:(ZXIntArray *)errorLocations {
|
int errorLocatorDegree = errorLocator.degree;
|
ZXIntArray *formalDerivativeCoefficients = [[ZXIntArray alloc] initWithLength:errorLocatorDegree];
|
for (int i = 1; i <= errorLocatorDegree; i++) {
|
formalDerivativeCoefficients.array[errorLocatorDegree - i] =
|
[self.field multiply:i b:[errorLocator coefficient:i]];
|
}
|
ZXModulusPoly *formalDerivative = [[ZXModulusPoly alloc] initWithField:self.field coefficients:formalDerivativeCoefficients];
|
|
// This is directly applying Forney's Formula
|
int s = errorLocations.length;
|
ZXIntArray *result = [[ZXIntArray alloc] initWithLength:s];
|
for (int i = 0; i < s; i++) {
|
int xiInverse = [self.field inverse:errorLocations.array[i]];
|
int numerator = [self.field subtract:0 b:[errorEvaluator evaluateAt:xiInverse]];
|
int denominator = [self.field inverse:[formalDerivative evaluateAt:xiInverse]];
|
result.array[i] = [self.field multiply:numerator b:denominator];
|
}
|
return result;
|
}
|
|
@end
|
