/*
|
* 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 "ZXErrors.h"
|
#import "ZXGenericGF.h"
|
#import "ZXGenericGFPoly.h"
|
#import "ZXIntArray.h"
|
#import "ZXReedSolomonDecoder.h"
|
|
@interface ZXReedSolomonDecoder ()
|
|
@property (nonatomic, strong, readonly) ZXGenericGF *field;
|
|
@end
|
|
@implementation ZXReedSolomonDecoder
|
|
- (id)initWithField:(ZXGenericGF *)field {
|
if (self = [super init]) {
|
_field = field;
|
}
|
|
return self;
|
}
|
|
- (BOOL)decode:(ZXIntArray *)received twoS:(int)twoS error:(NSError **)error {
|
ZXGenericGFPoly *poly = [[ZXGenericGFPoly alloc] initWithField:self.field coefficients:received];
|
ZXIntArray *syndromeCoefficients = [[ZXIntArray alloc] initWithLength:twoS];
|
BOOL noError = YES;
|
for (int i = 0; i < twoS; i++) {
|
int eval = [poly evaluateAt:[self.field exp:i + self.field.generatorBase]];
|
syndromeCoefficients.array[syndromeCoefficients.length - 1 - i] = eval;
|
if (eval != 0) {
|
noError = NO;
|
}
|
}
|
if (noError) {
|
return YES;
|
}
|
ZXGenericGFPoly *syndrome = [[ZXGenericGFPoly alloc] initWithField:self.field coefficients:syndromeCoefficients];
|
NSArray *sigmaOmega = [self runEuclideanAlgorithm:[self.field buildMonomial:twoS coefficient:1] b:syndrome R:twoS error:error];
|
if (!sigmaOmega) {
|
return NO;
|
}
|
ZXGenericGFPoly *sigma = sigmaOmega[0];
|
ZXGenericGFPoly *omega = sigmaOmega[1];
|
ZXIntArray *errorLocations = [self findErrorLocations:sigma error:error];
|
if (!errorLocations) {
|
return NO;
|
}
|
ZXIntArray *errorMagnitudes = [self findErrorMagnitudes:omega errorLocations:errorLocations];
|
for (int i = 0; i < errorLocations.length; i++) {
|
int position = received.length - 1 - [self.field log:errorLocations.array[i]];
|
if (position < 0) {
|
NSDictionary *userInfo = @{NSLocalizedDescriptionKey: @"Bad error location"};
|
|
if (error) *error = [[NSError alloc] initWithDomain:ZXErrorDomain code:ZXReedSolomonError userInfo:userInfo];
|
return NO;
|
}
|
received.array[position] = [ZXGenericGF addOrSubtract:received.array[position] b:errorMagnitudes.array[i]];
|
}
|
return YES;
|
}
|
|
- (NSArray *)runEuclideanAlgorithm:(ZXGenericGFPoly *)a b:(ZXGenericGFPoly *)b R:(int)R error:(NSError **)error {
|
if (a.degree < b.degree) {
|
ZXGenericGFPoly *temp = a;
|
a = b;
|
b = temp;
|
}
|
|
ZXGenericGFPoly *rLast = a;
|
ZXGenericGFPoly *r = b;
|
ZXGenericGFPoly *tLast = self.field.zero;
|
ZXGenericGFPoly *t = self.field.one;
|
|
while ([r degree] >= R / 2) {
|
ZXGenericGFPoly *rLastLast = rLast;
|
ZXGenericGFPoly *tLastLast = tLast;
|
rLast = r;
|
tLast = t;
|
|
if ([rLast zero]) {
|
NSDictionary *userInfo = @{NSLocalizedDescriptionKey: @"r_{i-1} was zero"};
|
|
if (error) *error = [[NSError alloc] initWithDomain:ZXErrorDomain code:ZXReedSolomonError userInfo:userInfo];
|
return nil;
|
}
|
r = rLastLast;
|
ZXGenericGFPoly *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 addOrSubtract:[self.field buildMonomial:degreeDiff coefficient:scale]];
|
r = [r addOrSubtract:[rLast multiplyByMonomial:degreeDiff coefficient:scale]];
|
}
|
|
t = [[q multiply:tLast] addOrSubtract:tLastLast];
|
|
if (r.degree >= rLast.degree) {
|
@throw [NSException exceptionWithName:@"IllegalStateException"
|
reason:@"Division algorithm failed to reduce polynomial?"
|
userInfo:nil];
|
}
|
}
|
|
int sigmaTildeAtZero = [t coefficient:0];
|
if (sigmaTildeAtZero == 0) {
|
NSDictionary *userInfo = @{NSLocalizedDescriptionKey: @"sigmaTilde(0) was zero"};
|
|
if (error) *error = [[NSError alloc] initWithDomain:ZXErrorDomain code:ZXReedSolomonError userInfo:userInfo];
|
return nil;
|
}
|
|
int inverse = [self.field inverse:sigmaTildeAtZero];
|
ZXGenericGFPoly *sigma = [t multiplyScalar:inverse];
|
ZXGenericGFPoly *omega = [r multiplyScalar:inverse];
|
return @[sigma, omega];
|
}
|
|
- (ZXIntArray *)findErrorLocations:(ZXGenericGFPoly *)errorLocator error:(NSError **)error {
|
int numErrors = [errorLocator degree];
|
if (numErrors == 1) {
|
ZXIntArray *array = [[ZXIntArray alloc] initWithLength:1];
|
array.array[0] = [errorLocator coefficient:1];
|
return array;
|
}
|
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) {
|
NSDictionary *userInfo = @{NSLocalizedDescriptionKey: @"Error locator degree does not match number of roots"};
|
|
if (error) *error = [[NSError alloc] initWithDomain:ZXErrorDomain code:ZXReedSolomonError userInfo:userInfo];
|
return nil;
|
}
|
return result;
|
}
|
|
- (ZXIntArray *)findErrorMagnitudes:(ZXGenericGFPoly *)errorEvaluator errorLocations:(ZXIntArray *)errorLocations {
|
int s = errorLocations.length;
|
ZXIntArray *result = [[ZXIntArray alloc] initWithLength:s];
|
ZXGenericGF *field = self.field;
|
for (int i = 0; i < s; i++) {
|
int xiInverse = [field inverse:errorLocations.array[i]];
|
int denominator = 1;
|
for (int 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
|
int term = [field multiply:errorLocations.array[j] b:xiInverse];
|
int termPlus1 = (term & 0x1) == 0 ? term | 1 : term & ~1;
|
denominator = [field multiply:denominator b:termPlus1];
|
}
|
}
|
result.array[i] = [field multiply:[errorEvaluator evaluateAt:xiInverse] b:[field inverse:denominator]];
|
if (field.generatorBase != 0) {
|
result.array[i] = [field multiply:result.array[i] b:xiInverse];
|
}
|
}
|
|
return result;
|
}
|
|
@end
|
