Pods/ZXingObjC/ZXingObjC/pdf417/detector/ZXPDF417Detector.m
/*
 * 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 "ZXBitArray.h"
#import "ZXBitMatrix.h"
#import "ZXBinaryBitmap.h"
#import "ZXDecodeHints.h"
#import "ZXErrors.h"
#import "ZXGridSampler.h"
#import "ZXMathUtils.h"
#import "ZXPDF417Detector.h"
#import "ZXPDF417DetectorResult.h"
#import "ZXPerspectiveTransform.h"
#import "ZXResultPoint.h"

const int ZX_PDF417_INDEXES_START_PATTERN[] = {0, 4, 1, 5};
const int ZX_PDF417_INDEXES_STOP_PATTERN[] = {6, 2, 7, 3};
const float ZX_PDF417_MAX_AVG_VARIANCE = 0.42f;
const float ZX_PDF417_MAX_INDIVIDUAL_VARIANCE = 0.8f;

// B S B S B S B S Bar/Space pattern
// 11111111 0 1 0 1 0 1 000
const int ZX_PDF417_DETECTOR_START_PATTERN[] = {8, 1, 1, 1, 1, 1, 1, 3};

// 1111111 0 1 000 1 0 1 00 1
const int ZX_PDF417_DETECTOR_STOP_PATTERN[] = {7, 1, 1, 3, 1, 1, 1, 2, 1};
const int ZX_PDF417_MAX_PIXEL_DRIFT = 3;
const int ZX_PDF417_MAX_PATTERN_DRIFT = 5;
// if we set the value too low, then we don't detect the correct height of the bar if the start patterns are damaged.
// if we set the value too high, then we might detect the start pattern from a neighbor barcode.
const int ZX_PDF417_SKIPPED_ROW_COUNT_MAX = 25;
// A PDF471 barcode should have at least 3 rows, with each row being >= 3 times the module width. Therefore it should be at least
// 9 pixels tall. To be conservative, we use about half the size to ensure we don't miss it.
const int ZX_PDF417_ROW_STEP = 5;
const int ZX_PDF417_BARCODE_MIN_HEIGHT = 10;

@implementation ZXPDF417Detector

+ (ZXPDF417DetectorResult *)detect:(ZXBinaryBitmap *)image hints:(ZXDecodeHints *)hints multiple:(BOOL)multiple error:(NSError **)error {
  // TODO detection improvement, tryHarder could try several different luminance thresholds/blackpoints or even
  // different binarizers
  //boolean tryHarder = hints != null && hints.containsKey(DecodeHintType.TRY_HARDER);

  ZXBitMatrix *bitMatrix = [image blackMatrixWithError:error];

  NSArray *barcodeCoordinates = [self detect:multiple bitMatrix:bitMatrix error:error];
  if (!barcodeCoordinates) {
    return nil;
  }
  if ([barcodeCoordinates count] == 0) {
    bitMatrix = [bitMatrix copy];
    [bitMatrix rotate180];
    barcodeCoordinates = [self detect:multiple bitMatrix:bitMatrix error:error];
    if (!barcodeCoordinates) {
      return nil;
    }
  }
  return [[ZXPDF417DetectorResult alloc] initWithBits:bitMatrix points:barcodeCoordinates];
}

/**
 * Detects PDF417 codes in an image. Only checks 0 degree rotation
 * @param multiple if true, then the image is searched for multiple codes. If false, then at most one code will
 * be found and returned
 * @param bitMatrix bit matrix to detect barcodes in
 * @return List of ResultPoint arrays containing the coordinates of found barcodes
 */
+ (NSArray *)detect:(BOOL)multiple bitMatrix:(ZXBitMatrix *)bitMatrix error:(NSError **)error {
  NSMutableArray *barcodeCoordinates = [NSMutableArray array];
  int row = 0;
  int column = 0;
  BOOL foundBarcodeInRow = NO;
  while (row < bitMatrix.height) {
    NSArray *vertices = [self findVertices:bitMatrix startRow:row startColumn:column];

    if (vertices[0] == [NSNull null] && vertices[3] == [NSNull null]) {
      if (!foundBarcodeInRow) {
        // we didn't find any barcode so that's the end of searching
        break;
      }
      // we didn't find a barcode starting at the given column and row. Try again from the first column and slightly
      // below the lowest barcode we found so far.
      foundBarcodeInRow = NO;
      column = 0;
      for (NSArray *barcodeCoordinate in barcodeCoordinates) {
        if (barcodeCoordinate[1] != [NSNull null]) {
          row = MAX(row, (int) [(ZXResultPoint *)barcodeCoordinate[1] y]);
        }
        if (barcodeCoordinate[3] != [NSNull null]) {
          row = MAX(row, (int) [(ZXResultPoint *)barcodeCoordinate[3] y]);
        }
      }
      row += ZX_PDF417_ROW_STEP;
      continue;
    }
    foundBarcodeInRow = YES;
    [barcodeCoordinates addObject:vertices];
    if (!multiple) {
      break;
    }
    // if we didn't find a right row indicator column, then continue the search for the next barcode after the
    // start pattern of the barcode just found.
    if (vertices[2] != [NSNull null]) {
      column = (int) [(ZXResultPoint *)vertices[2] x];
      row = (int) [(ZXResultPoint *)vertices[2] y];
    } else {
      column = (int) [(ZXResultPoint *)vertices[4] x];
      row = (int) [(ZXResultPoint *)vertices[4] y];
    }
  }
  return barcodeCoordinates;
}

/**
 * Locate the vertices and the codewords area of a black blob using the Start
 * and Stop patterns as locators.
 *
 * @param matrix the scanned barcode image.
 * @return an array containing the vertices:
 *           vertices[0] x, y top left barcode
 *           vertices[1] x, y bottom left barcode
 *           vertices[2] x, y top right barcode
 *           vertices[3] x, y bottom right barcode
 *           vertices[4] x, y top left codeword area
 *           vertices[5] x, y bottom left codeword area
 *           vertices[6] x, y top right codeword area
 *           vertices[7] x, y bottom right codeword area
 */
+ (NSMutableArray *)findVertices:(ZXBitMatrix *)matrix startRow:(int)startRow startColumn:(int)startColumn {
  int height = matrix.height;
  int width = matrix.width;

  NSMutableArray *result = [NSMutableArray arrayWithCapacity:8];
  for (int i = 0; i < 8; i++) {
    [result addObject:[NSNull null]];
  }
  [self copyToResult:result
           tmpResult:[self findRowsWithPattern:matrix
                                        height:height
                                         width:width
                                      startRow:startRow
                                   startColumn:startColumn
                                       pattern:ZX_PDF417_DETECTOR_START_PATTERN
                                    patternLen:sizeof(ZX_PDF417_DETECTOR_START_PATTERN) / sizeof(int)]
  destinationIndexes:ZX_PDF417_INDEXES_START_PATTERN
              length:sizeof(ZX_PDF417_INDEXES_START_PATTERN) / sizeof(int)];

  if (result[4] != [NSNull null]) {
    startColumn = (int) [(ZXResultPoint *)result[4] x];
    startRow = (int) [(ZXResultPoint *)result[4] y];
  }
  [self copyToResult:result
           tmpResult:[self findRowsWithPattern:matrix
                                        height:height
                                         width:width
                                      startRow:startRow
                                   startColumn:startColumn
                                       pattern:ZX_PDF417_DETECTOR_STOP_PATTERN
                                    patternLen:sizeof(ZX_PDF417_DETECTOR_STOP_PATTERN) / sizeof(int)]
  destinationIndexes:ZX_PDF417_INDEXES_STOP_PATTERN
              length:sizeof(ZX_PDF417_INDEXES_STOP_PATTERN) / sizeof(int)];
  return result;
}

+ (void)copyToResult:(NSMutableArray *)result tmpResult:(NSMutableArray *)tmpResult destinationIndexes:(const int[])destinationIndexes length:(int)length {
  for (int i = 0; i < length; i++) {
    result[destinationIndexes[i]] = tmpResult[i];
  }
}

+ (NSMutableArray *)findRowsWithPattern:(ZXBitMatrix *)matrix height:(int)height width:(int)width startRow:(int)startRow
                            startColumn:(int)startColumn pattern:(const int[])pattern patternLen:(int)patternLen {
  NSMutableArray *result = [NSMutableArray array];
  for (int i = 0; i < 4; i++) {
    [result addObject:[NSNull null]];
  }
  BOOL found = NO;
  int counters[patternLen];
  memset(counters, 0, patternLen * sizeof(int));
  for (; startRow < height; startRow += ZX_PDF417_ROW_STEP) {
    NSRange loc = [self findGuardPattern:matrix column:startColumn row:startRow width:width whiteFirst:false pattern:pattern patternLen:patternLen counters:counters];
    if (loc.location != NSNotFound) {
      while (startRow > 0) {
        NSRange previousRowLoc = [self findGuardPattern:matrix column:startColumn row:--startRow width:width whiteFirst:false pattern:pattern patternLen:patternLen counters:counters];
        if (previousRowLoc.location != NSNotFound) {
          loc = previousRowLoc;
        } else {
          startRow++;
          break;
        }
      }
      result[0] = [[ZXResultPoint alloc] initWithX:loc.location y:startRow];
      result[1] = [[ZXResultPoint alloc] initWithX:NSMaxRange(loc) y:startRow];
      found = YES;
      break;
    }
  }
  int stopRow = startRow + 1;
  // Last row of the current symbol that contains pattern
  if (found) {
    int skippedRowCount = 0;
    NSRange previousRowLoc = NSMakeRange((NSUInteger) [(ZXResultPoint *)result[0] x], ((NSUInteger)[(ZXResultPoint *)result[1] x]) - ((NSUInteger)[(ZXResultPoint *)result[0] x]));
    for (; stopRow < height; stopRow++) {
      NSRange loc = [self findGuardPattern:matrix column:(int)previousRowLoc.location row:stopRow width:width whiteFirst:NO pattern:pattern patternLen:patternLen counters:counters];
      // a found pattern is only considered to belong to the same barcode if the start and end positions
      // don't differ too much. Pattern drift should be not bigger than two for consecutive rows. With
      // a higher number of skipped rows drift could be larger. To keep it simple for now, we allow a slightly
      // larger drift and don't check for skipped rows.
      if (loc.location != NSNotFound &&
          ABS((int)previousRowLoc.location - (int)loc.location) < ZX_PDF417_MAX_PATTERN_DRIFT &&
          ABS((int)NSMaxRange(previousRowLoc) - (int)NSMaxRange(loc)) < ZX_PDF417_MAX_PATTERN_DRIFT) {
        previousRowLoc = loc;
        skippedRowCount = 0;
      } else {
        if (skippedRowCount > ZX_PDF417_SKIPPED_ROW_COUNT_MAX) {
          break;
        } else {
          skippedRowCount++;
        }
      }
    }
    stopRow -= skippedRowCount + 1;
    result[2] = [[ZXResultPoint alloc] initWithX:previousRowLoc.location y:stopRow];
    result[3] = [[ZXResultPoint alloc] initWithX:NSMaxRange(previousRowLoc) y:stopRow];
  }
  if (stopRow - startRow < ZX_PDF417_BARCODE_MIN_HEIGHT) {
    for (int i = 0; i < 4; i++) {
      result[i] = [NSNull null];
    }
  }
  return result;
}

/**
 * @param matrix row of black/white values to search
 * @param column x position to start search
 * @param row y position to start search
 * @param width the number of pixels to search on this row
 * @param pattern pattern of counts of number of black and white pixels that are
 *                 being searched for as a pattern
 * @param counters array of counters, as long as pattern, to re-use
 * @return start/end horizontal offset of guard pattern, as an array of two ints.
 */
+ (NSRange)findGuardPattern:(ZXBitMatrix *)matrix
                     column:(int)column
                        row:(int)row
                      width:(int)width
                 whiteFirst:(BOOL)whiteFirst
                    pattern:(const int[])pattern
                 patternLen:(int)patternLen
                   counters:(int *)counters {
  int patternLength = patternLen;
  memset(counters, 0, patternLength * sizeof(int));
  BOOL isWhite = whiteFirst;
  int patternStart = column;
  int pixelDrift = 0;

  // if there are black pixels left of the current pixel shift to the left, but only for ZX_PDF417_MAX_PIXEL_DRIFT pixels
  while ([matrix getX:patternStart y:row] && patternStart > 0 && pixelDrift++ < ZX_PDF417_MAX_PIXEL_DRIFT) {
    patternStart--;
  }
  int x = patternStart;
  int counterPosition = 0;
  for (;x < width; x++) {
    BOOL pixel = [matrix getX:x y:row];
    if (pixel ^ isWhite) {
      counters[counterPosition] = counters[counterPosition] + 1;
    } else {
      if (counterPosition == patternLength - 1) {
        if ([self patternMatchVariance:counters countersSize:patternLength pattern:pattern maxIndividualVariance:ZX_PDF417_MAX_INDIVIDUAL_VARIANCE] < ZX_PDF417_MAX_AVG_VARIANCE) {
          return NSMakeRange(patternStart, x - patternStart);
        }
        patternStart += counters[0] + counters[1];
        for (int y = 2; y < patternLength; y++) {
          counters[y - 2] = counters[y];
        }
        counters[patternLength - 2] = 0;
        counters[patternLength - 1] = 0;
        counterPosition--;
      } else {
        counterPosition++;
      }
      counters[counterPosition] = 1;
      isWhite = !isWhite;
    }
  }
  if (counterPosition == patternLength - 1) {
    if ([self patternMatchVariance:counters countersSize:patternLen pattern:pattern maxIndividualVariance:ZX_PDF417_MAX_INDIVIDUAL_VARIANCE] < ZX_PDF417_MAX_AVG_VARIANCE) {
      return NSMakeRange(patternStart, x - patternStart - 1);
    }
  }
  return NSMakeRange(NSNotFound, 0);
}

/**
 * Determines how closely a set of observed counts of runs of black/white
 * values matches a given target pattern. This is reported as the ratio of
 * the total variance from the expected pattern proportions across all
 * pattern elements, to the length of the pattern.
 *
 * @param counters observed counters
 * @param pattern expected pattern
 * @param maxIndividualVariance The most any counter can differ before we give up
 * @return ratio of total variance between counters and pattern compared to total pattern size
 */
+ (float)patternMatchVariance:(int *)counters countersSize:(int)countersSize pattern:(const int[])pattern maxIndividualVariance:(float)maxIndividualVariance {
  int numCounters = countersSize;
  int total = 0;
  int patternLength = 0;
  for (int i = 0; i < numCounters; i++) {
    total += counters[i];
    patternLength += pattern[i];
  }

  if (total < patternLength || patternLength == 0) {
    return FLT_MAX;
  }
  float unitBarWidth = (float) total / patternLength;
  maxIndividualVariance *= unitBarWidth;

  float totalVariance = 0.0f;
  for (int x = 0; x < numCounters; x++) {
    int counter = counters[x];
    float scaledPattern = pattern[x] * unitBarWidth;
    float variance = counter > scaledPattern ? counter - scaledPattern : scaledPattern - counter;
    if (variance > maxIndividualVariance) {
      return FLT_MAX;
    }
    totalVariance += variance;
  }

  return totalVariance / total;
}

@end
