/*
 * 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