Add parts of zxing library to generate qr codes

5 files changed, 685 insertions, 0 deletions

diff --git a/OpenPGP-Keychain/src/com/google/zxing/multi/ByQuadrantReader.java b/OpenPGP-Keychain/src/com/google/zxing/multi/ByQuadrantReader.java
new file mode 100644
index 000000000..35904d364
--- /dev/null
+++ b/OpenPGP-Keychain/src/com/google/zxing/multi/ByQuadrantReader.java
@@ -0,0 +1,96 @@
+/*
+ * Copyright 2009 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.
+ */
+
+package com.google.zxing.multi;
+
+import com.google.zxing.BinaryBitmap;
+import com.google.zxing.ChecksumException;
+import com.google.zxing.FormatException;
+import com.google.zxing.NotFoundException;
+import com.google.zxing.Reader;
+import com.google.zxing.Result;
+
+import java.util.Hashtable;
+
+/**
+ * This class attempts to decode a barcode from an image, not by scanning the whole image,
+ * but by scanning subsets of the image. This is important when there may be multiple barcodes in
+ * an image, and detecting a barcode may find parts of multiple barcode and fail to decode
+ * (e.g. QR Codes). Instead this scans the four quadrants of the image -- and also the center
+ * 'quadrant' to cover the case where a barcode is found in the center.
+ *
+ * @see GenericMultipleBarcodeReader
+ */
+public final class ByQuadrantReader implements Reader {
+
+  private final Reader delegate;
+
+  public ByQuadrantReader(Reader delegate) {
+    this.delegate = delegate;
+  }
+
+  public Result decode(BinaryBitmap image)
+      throws NotFoundException, ChecksumException, FormatException {
+    return decode(image, null);
+  }
+
+  public Result decode(BinaryBitmap image, Hashtable hints)
+      throws NotFoundException, ChecksumException, FormatException {
+
+    int width = image.getWidth();
+    int height = image.getHeight();
+    int halfWidth = width / 2;
+    int halfHeight = height / 2;
+
+    BinaryBitmap topLeft = image.crop(0, 0, halfWidth, halfHeight);
+    try {
+      return delegate.decode(topLeft, hints);
+    } catch (NotFoundException re) {
+      // continue
+    }
+
+    BinaryBitmap topRight = image.crop(halfWidth, 0, halfWidth, halfHeight);
+    try {
+      return delegate.decode(topRight, hints);
+    } catch (NotFoundException re) {
+      // continue
+    }
+
+    BinaryBitmap bottomLeft = image.crop(0, halfHeight, halfWidth, halfHeight);
+    try {
+      return delegate.decode(bottomLeft, hints);
+    } catch (NotFoundException re) {
+      // continue
+    }
+
+    BinaryBitmap bottomRight = image.crop(halfWidth, halfHeight, halfWidth, halfHeight);
+    try {
+      return delegate.decode(bottomRight, hints);
+    } catch (NotFoundException re) {
+      // continue
+    }
+
+    int quarterWidth = halfWidth / 2;
+    int quarterHeight = halfHeight / 2;
+    BinaryBitmap center = image.crop(quarterWidth, quarterHeight, halfWidth, halfHeight);
+    return delegate.decode(center, hints);
+  }
+
+  public void reset() {
+    delegate.reset();
+  }
+
+}
diff --git a/OpenPGP-Keychain/src/com/google/zxing/multi/GenericMultipleBarcodeReader.java b/OpenPGP-Keychain/src/com/google/zxing/multi/GenericMultipleBarcodeReader.java
new file mode 100644
index 000000000..70d454251
--- /dev/null
+++ b/OpenPGP-Keychain/src/com/google/zxing/multi/GenericMultipleBarcodeReader.java
@@ -0,0 +1,156 @@
+/*
+ * Copyright 2009 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.
+ */
+
+package com.google.zxing.multi;
+
+import com.google.zxing.BinaryBitmap;
+import com.google.zxing.NotFoundException;
+import com.google.zxing.Reader;
+import com.google.zxing.ReaderException;
+import com.google.zxing.Result;
+import com.google.zxing.ResultPoint;
+
+import java.util.Hashtable;
+import java.util.Vector;
+
+/**
+ * <p>Attempts to locate multiple barcodes in an image by repeatedly decoding portion of the image.
+ * After one barcode is found, the areas left, above, right and below the barcode's
+ * {@link com.google.zxing.ResultPoint}s are scanned, recursively.</p>
+ *
+ * <p>A caller may want to also employ {@link ByQuadrantReader} when attempting to find multiple
+ * 2D barcodes, like QR Codes, in an image, where the presence of multiple barcodes might prevent
+ * detecting any one of them.</p>
+ *
+ * <p>That is, instead of passing a {@link Reader} a caller might pass
+ * <code>new ByQuadrantReader(reader)</code>.</p>
+ *
+ * @author Sean Owen
+ */
+public final class GenericMultipleBarcodeReader implements MultipleBarcodeReader {
+
+  private static final int MIN_DIMENSION_TO_RECUR = 100;
+
+  private final Reader delegate;
+
+  public GenericMultipleBarcodeReader(Reader delegate) {
+    this.delegate = delegate;
+  }
+
+  public Result[] decodeMultiple(BinaryBitmap image) throws NotFoundException {
+    return decodeMultiple(image, null);
+  }
+
+  public Result[] decodeMultiple(BinaryBitmap image, Hashtable hints)
+      throws NotFoundException {
+    Vector results = new Vector();
+    doDecodeMultiple(image, hints, results, 0, 0);
+    if (results.isEmpty()) {
+      throw NotFoundException.getNotFoundInstance();
+    }
+    int numResults = results.size();
+    Result[] resultArray = new Result[numResults];
+    for (int i = 0; i < numResults; i++) {
+      resultArray[i] = (Result) results.elementAt(i);
+    }
+    return resultArray;
+  }
+
+  private void doDecodeMultiple(BinaryBitmap image,
+                                Hashtable hints,
+                                Vector results,
+                                int xOffset,
+                                int yOffset) {
+    Result result;
+    try {
+      result = delegate.decode(image, hints);
+    } catch (ReaderException re) {
+      return;
+    }
+    boolean alreadyFound = false;
+    for (int i = 0; i < results.size(); i++) {
+      Result existingResult = (Result) results.elementAt(i);
+      if (existingResult.getText().equals(result.getText())) {
+        alreadyFound = true;
+        break;
+      }
+    }
+    if (alreadyFound) {
+      return;
+    }
+    results.addElement(translateResultPoints(result, xOffset, yOffset));
+    ResultPoint[] resultPoints = result.getResultPoints();
+    if (resultPoints == null || resultPoints.length == 0) {
+      return;
+    }
+    int width = image.getWidth();
+    int height = image.getHeight();
+    float minX = width;
+    float minY = height;
+    float maxX = 0.0f;
+    float maxY = 0.0f;
+    for (int i = 0; i < resultPoints.length; i++) {
+      ResultPoint point = resultPoints[i];
+      float x = point.getX();
+      float y = point.getY();
+      if (x < minX) {
+        minX = x;
+      }
+      if (y < minY) {
+        minY = y;
+      }
+      if (x > maxX) {
+        maxX = x;
+      }
+      if (y > maxY) {
+        maxY = y;
+      }
+    }
+
+    // Decode left of barcode
+    if (minX > MIN_DIMENSION_TO_RECUR) {
+      doDecodeMultiple(image.crop(0, 0, (int) minX, height),
+                       hints, results, xOffset, yOffset);
+    }
+    // Decode above barcode
+    if (minY > MIN_DIMENSION_TO_RECUR) {
+      doDecodeMultiple(image.crop(0, 0, width, (int) minY),
+                       hints, results, xOffset, yOffset);
+    }
+    // Decode right of barcode
+    if (maxX < width - MIN_DIMENSION_TO_RECUR) {
+      doDecodeMultiple(image.crop((int) maxX, 0, width - (int) maxX, height),
+                       hints, results, xOffset + (int) maxX, yOffset);
+    }
+    // Decode below barcode
+    if (maxY < height - MIN_DIMENSION_TO_RECUR) {
+      doDecodeMultiple(image.crop(0, (int) maxY, width, height - (int) maxY),
+                       hints, results, xOffset, yOffset + (int) maxY);
+    }
+  }
+
+  private static Result translateResultPoints(Result result, int xOffset, int yOffset) {
+    ResultPoint[] oldResultPoints = result.getResultPoints();
+    ResultPoint[] newResultPoints = new ResultPoint[oldResultPoints.length];
+    for (int i = 0; i < oldResultPoints.length; i++) {
+      ResultPoint oldPoint = oldResultPoints[i];
+      newResultPoints[i] = new ResultPoint(oldPoint.getX() + xOffset, oldPoint.getY() + yOffset);
+    }
+    return new Result(result.getText(), result.getRawBytes(), newResultPoints,
+        result.getBarcodeFormat());
+  }
+
+}
diff --git a/OpenPGP-Keychain/src/com/google/zxing/multi/MultipleBarcodeReader.java b/OpenPGP-Keychain/src/com/google/zxing/multi/MultipleBarcodeReader.java
new file mode 100644
index 000000000..5f0c7eb5d
--- /dev/null
+++ b/OpenPGP-Keychain/src/com/google/zxing/multi/MultipleBarcodeReader.java
@@ -0,0 +1,37 @@
+/*
+ * Copyright 2009 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.
+ */
+
+package com.google.zxing.multi;
+
+import com.google.zxing.BinaryBitmap;
+import com.google.zxing.NotFoundException;
+import com.google.zxing.Result;
+
+import java.util.Hashtable;
+
+/**
+ * Implementation of this interface attempt to read several barcodes from one image.
+ *
+ * @see com.google.zxing.Reader
+ * @author Sean Owen
+ */
+public interface MultipleBarcodeReader {
+
+  Result[] decodeMultiple(BinaryBitmap image) throws NotFoundException;
+
+  Result[] decodeMultiple(BinaryBitmap image, Hashtable hints) throws NotFoundException;
+
+}
diff --git a/OpenPGP-Keychain/src/com/google/zxing/multi/qrcode/detector/MultiDetector.java b/OpenPGP-Keychain/src/com/google/zxing/multi/qrcode/detector/MultiDetector.java
new file mode 100644
index 000000000..584c41404
--- /dev/null
+++ b/OpenPGP-Keychain/src/com/google/zxing/multi/qrcode/detector/MultiDetector.java
@@ -0,0 +1,72 @@
+/*
+ * Copyright 2009 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.
+ */
+
+package com.google.zxing.multi.qrcode.detector;
+
+import com.google.zxing.NotFoundException;
+import com.google.zxing.ReaderException;
+import com.google.zxing.common.BitMatrix;
+import com.google.zxing.common.DetectorResult;
+import com.google.zxing.qrcode.detector.Detector;
+import com.google.zxing.qrcode.detector.FinderPatternInfo;
+
+import java.util.Hashtable;
+import java.util.Vector;
+
+/**
+ * <p>Encapsulates logic that can detect one or more QR Codes in an image, even if the QR Code
+ * is rotated or skewed, or partially obscured.</p>
+ *
+ * @author Sean Owen
+ * @author Hannes Erven
+ */
+public final class MultiDetector extends Detector {
+
+  private static final DetectorResult[] EMPTY_DETECTOR_RESULTS = new DetectorResult[0];
+
+  public MultiDetector(BitMatrix image) {
+    super(image);
+  }
+
+  public DetectorResult[] detectMulti(Hashtable hints) throws NotFoundException {
+    BitMatrix image = getImage();
+    MultiFinderPatternFinder finder = new MultiFinderPatternFinder(image);
+    FinderPatternInfo[] info = finder.findMulti(hints);
+
+    if (info == null || info.length == 0) {
+      throw NotFoundException.getNotFoundInstance();
+    }
+
+    Vector result = new Vector();
+    for (int i = 0; i < info.length; i++) {
+      try {
+        result.addElement(processFinderPatternInfo(info[i]));
+      } catch (ReaderException e) {
+        // ignore
+      }
+    }
+    if (result.isEmpty()) {
+      return EMPTY_DETECTOR_RESULTS;
+    } else {
+      DetectorResult[] resultArray = new DetectorResult[result.size()];
+      for (int i = 0; i < result.size(); i++) {
+        resultArray[i] = (DetectorResult) result.elementAt(i);
+      }
+      return resultArray;
+    }
+  }
+
+}
diff --git a/OpenPGP-Keychain/src/com/google/zxing/multi/qrcode/detector/MultiFinderPatternFinder.java b/OpenPGP-Keychain/src/com/google/zxing/multi/qrcode/detector/MultiFinderPatternFinder.java
new file mode 100644
index 000000000..1162324e2
--- /dev/null
+++ b/OpenPGP-Keychain/src/com/google/zxing/multi/qrcode/detector/MultiFinderPatternFinder.java
@@ -0,0 +1,324 @@
+/*

+ * Copyright 2009 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.

+ */

+

+package com.google.zxing.multi.qrcode.detector;

+

+import com.google.zxing.DecodeHintType;

+import com.google.zxing.NotFoundException;

+import com.google.zxing.ResultPoint;

+import com.google.zxing.ResultPointCallback;

+import com.google.zxing.common.BitMatrix;

+import com.google.zxing.common.Collections;

+import com.google.zxing.common.Comparator;

+import com.google.zxing.qrcode.detector.FinderPattern;

+import com.google.zxing.qrcode.detector.FinderPatternFinder;

+import com.google.zxing.qrcode.detector.FinderPatternInfo;

+

+import java.util.Hashtable;

+import java.util.Vector;

+

+/**

+ * <p>This class attempts to find finder patterns in a QR Code. Finder patterns are the square

+ * markers at three corners of a QR Code.</p>

+ *

+ * <p>This class is thread-safe but not reentrant. Each thread must allocate its own object.

+ *

+ * <p>In contrast to {@link FinderPatternFinder}, this class will return an array of all possible

+ * QR code locations in the image.</p>

+ *

+ * <p>Use the TRY_HARDER hint to ask for a more thorough detection.</p>

+ *

+ * @author Sean Owen

+ * @author Hannes Erven

+ */

+final class MultiFinderPatternFinder extends FinderPatternFinder {

+

+  private static final FinderPatternInfo[] EMPTY_RESULT_ARRAY = new FinderPatternInfo[0];

+

+  // TODO MIN_MODULE_COUNT and MAX_MODULE_COUNT would be great hints to ask the user for

+  // since it limits the number of regions to decode

+

+  // max. legal count of modules per QR code edge (177)

+  private static final float MAX_MODULE_COUNT_PER_EDGE = 180;

+  // min. legal count per modules per QR code edge (11)

+  private static final float MIN_MODULE_COUNT_PER_EDGE = 9;

+

+  /**

+   * More or less arbitrary cutoff point for determining if two finder patterns might belong

+   * to the same code if they differ less than DIFF_MODSIZE_CUTOFF_PERCENT percent in their

+   * estimated modules sizes.

+   */

+  private static final float DIFF_MODSIZE_CUTOFF_PERCENT = 0.05f;

+

+  /**

+   * More or less arbitrary cutoff point for determining if two finder patterns might belong

+   * to the same code if they differ less than DIFF_MODSIZE_CUTOFF pixels/module in their

+   * estimated modules sizes.

+   */

+  private static final float DIFF_MODSIZE_CUTOFF = 0.5f;

+

+

+  /**

+   * A comparator that orders FinderPatterns by their estimated module size.

+   */

+  private static class ModuleSizeComparator implements Comparator {

+    public int compare(Object center1, Object center2) {

+      float value = ((FinderPattern) center2).getEstimatedModuleSize() -

+                    ((FinderPattern) center1).getEstimatedModuleSize();

+      return value < 0.0 ? -1 : value > 0.0 ? 1 : 0;

+    }

+  }

+

+  /**

+   * <p>Creates a finder that will search the image for three finder patterns.</p>

+   *

+   * @param image image to search

+   */

+  MultiFinderPatternFinder(BitMatrix image) {

+    super(image);

+  }

+

+  MultiFinderPatternFinder(BitMatrix image, ResultPointCallback resultPointCallback) {

+    super(image, resultPointCallback);

+  }

+

+  /**

+   * @return the 3 best {@link FinderPattern}s from our list of candidates. The "best" are

+   *         those that have been detected at least {@link #CENTER_QUORUM} times, and whose module

+   *         size differs from the average among those patterns the least

+   * @throws NotFoundException if 3 such finder patterns do not exist

+   */

+  private FinderPattern[][] selectBestPatterns() throws NotFoundException {

+    Vector possibleCenters = getPossibleCenters();

+    int size = possibleCenters.size();

+

+    if (size < 3) {

+      // Couldn't find enough finder patterns

+      throw NotFoundException.getNotFoundInstance();

+    }

+

+    /*

+     * Begin HE modifications to safely detect multiple codes of equal size

+     */

+    if (size == 3) {

+      return new FinderPattern[][]{

+          new FinderPattern[]{

+              (FinderPattern) possibleCenters.elementAt(0),

+              (FinderPattern) possibleCenters.elementAt(1),

+              (FinderPattern) possibleCenters.elementAt(2)

+          }

+      };

+    }

+

+    // Sort by estimated module size to speed up the upcoming checks

+    Collections.insertionSort(possibleCenters, new ModuleSizeComparator());

+

+    /*

+     * Now lets start: build a list of tuples of three finder locations that

+     *  - feature similar module sizes

+     *  - are placed in a distance so the estimated module count is within the QR specification

+     *  - have similar distance between upper left/right and left top/bottom finder patterns

+     *  - form a triangle with 90° angle (checked by comparing top right/bottom left distance

+     *    with pythagoras)

+     *

+     * Note: we allow each point to be used for more than one code region: this might seem

+     * counterintuitive at first, but the performance penalty is not that big. At this point,

+     * we cannot make a good quality decision whether the three finders actually represent

+     * a QR code, or are just by chance layouted so it looks like there might be a QR code there.

+     * So, if the layout seems right, lets have the decoder try to decode.     

+     */

+

+    Vector results = new Vector(); // holder for the results

+

+    for (int i1 = 0; i1 < (size - 2); i1++) {

+      FinderPattern p1 = (FinderPattern) possibleCenters.elementAt(i1);

+      if (p1 == null) {

+        continue;

+      }

+

+      for (int i2 = i1 + 1; i2 < (size - 1); i2++) {

+        FinderPattern p2 = (FinderPattern) possibleCenters.elementAt(i2);

+        if (p2 == null) {

+          continue;

+        }

+

+        // Compare the expected module sizes; if they are really off, skip

+        float vModSize12 = (p1.getEstimatedModuleSize() - p2.getEstimatedModuleSize()) /

+            Math.min(p1.getEstimatedModuleSize(), p2.getEstimatedModuleSize());

+        float vModSize12A = Math.abs(p1.getEstimatedModuleSize() - p2.getEstimatedModuleSize());

+        if (vModSize12A > DIFF_MODSIZE_CUTOFF && vModSize12 >= DIFF_MODSIZE_CUTOFF_PERCENT) {

+          // break, since elements are ordered by the module size deviation there cannot be

+          // any more interesting elements for the given p1.

+          break;

+        }

+

+        for (int i3 = i2 + 1; i3 < size; i3++) {

+          FinderPattern p3 = (FinderPattern) possibleCenters.elementAt(i3);

+          if (p3 == null) {

+            continue;

+          }

+

+          // Compare the expected module sizes; if they are really off, skip

+          float vModSize23 = (p2.getEstimatedModuleSize() - p3.getEstimatedModuleSize()) /

+              Math.min(p2.getEstimatedModuleSize(), p3.getEstimatedModuleSize());

+          float vModSize23A = Math.abs(p2.getEstimatedModuleSize() - p3.getEstimatedModuleSize());

+          if (vModSize23A > DIFF_MODSIZE_CUTOFF && vModSize23 >= DIFF_MODSIZE_CUTOFF_PERCENT) {

+            // break, since elements are ordered by the module size deviation there cannot be

+            // any more interesting elements for the given p1.

+            break;

+          }

+

+          FinderPattern[] test = {p1, p2, p3};

+          ResultPoint.orderBestPatterns(test);

+

+          // Calculate the distances: a = topleft-bottomleft, b=topleft-topright, c = diagonal

+          FinderPatternInfo info = new FinderPatternInfo(test);

+          float dA = ResultPoint.distance(info.getTopLeft(), info.getBottomLeft());

+          float dC = ResultPoint.distance(info.getTopRight(), info.getBottomLeft());

+          float dB = ResultPoint.distance(info.getTopLeft(), info.getTopRight());

+

+          // Check the sizes

+          float estimatedModuleCount = (dA + dB) / (p1.getEstimatedModuleSize() * 2.0f);

+          if (estimatedModuleCount > MAX_MODULE_COUNT_PER_EDGE ||

+              estimatedModuleCount < MIN_MODULE_COUNT_PER_EDGE) {

+            continue;

+          }

+

+          // Calculate the difference of the edge lengths in percent

+          float vABBC = Math.abs((dA - dB) / Math.min(dA, dB));

+          if (vABBC >= 0.1f) {

+            continue;

+          }

+

+          // Calculate the diagonal length by assuming a 90° angle at topleft

+          float dCpy = (float) Math.sqrt(dA * dA + dB * dB);

+          // Compare to the real distance in %

+          float vPyC = Math.abs((dC - dCpy) / Math.min(dC, dCpy));

+

+          if (vPyC >= 0.1f) {

+            continue;

+          }

+

+          // All tests passed!

+          results.addElement(test);

+        } // end iterate p3

+      } // end iterate p2

+    } // end iterate p1

+

+    if (!results.isEmpty()) {

+      FinderPattern[][] resultArray = new FinderPattern[results.size()][];

+      for (int i = 0; i < results.size(); i++) {

+        resultArray[i] = (FinderPattern[]) results.elementAt(i);

+      }

+      return resultArray;

+    }

+

+    // Nothing found!

+    throw NotFoundException.getNotFoundInstance();

+  }

+

+  public FinderPatternInfo[] findMulti(Hashtable hints) throws NotFoundException {

+    boolean tryHarder = hints != null && hints.containsKey(DecodeHintType.TRY_HARDER);

+    BitMatrix image = getImage();

+    int maxI = image.getHeight();

+    int maxJ = image.getWidth();

+    // We are looking for black/white/black/white/black modules in

+    // 1:1:3:1:1 ratio; this tracks the number of such modules seen so far

+

+    // Let's assume that the maximum version QR Code we support takes up 1/4 the height of the

+    // image, and then account for the center being 3 modules in size. This gives the smallest

+    // number of pixels the center could be, so skip this often. When trying harder, look for all

+    // QR versions regardless of how dense they are.

+    int iSkip = (int) (maxI / (MAX_MODULES * 4.0f) * 3);

+    if (iSkip < MIN_SKIP || tryHarder) {

+      iSkip = MIN_SKIP;

+    }

+

+    int[] stateCount = new int[5];

+    for (int i = iSkip - 1; i < maxI; i += iSkip) {

+      // Get a row of black/white values

+      stateCount[0] = 0;

+      stateCount[1] = 0;

+      stateCount[2] = 0;

+      stateCount[3] = 0;

+      stateCount[4] = 0;

+      int currentState = 0;

+      for (int j = 0; j < maxJ; j++) {

+        if (image.get(j, i)) {

+          // Black pixel

+          if ((currentState & 1) == 1) { // Counting white pixels

+            currentState++;

+          }

+          stateCount[currentState]++;

+        } else { // White pixel

+          if ((currentState & 1) == 0) { // Counting black pixels

+            if (currentState == 4) { // A winner?

+              if (foundPatternCross(stateCount)) { // Yes

+                boolean confirmed = handlePossibleCenter(stateCount, i, j);

+                if (!confirmed) {

+                  do { // Advance to next black pixel

+                    j++;

+                  } while (j < maxJ && !image.get(j, i));

+                  j--; // back up to that last white pixel

+                }

+                // Clear state to start looking again

+                currentState = 0;

+                stateCount[0] = 0;

+                stateCount[1] = 0;

+                stateCount[2] = 0;

+                stateCount[3] = 0;

+                stateCount[4] = 0;

+              } else { // No, shift counts back by two

+                stateCount[0] = stateCount[2];

+                stateCount[1] = stateCount[3];

+                stateCount[2] = stateCount[4];

+                stateCount[3] = 1;

+                stateCount[4] = 0;

+                currentState = 3;

+              }

+            } else {

+              stateCount[++currentState]++;

+            }

+          } else { // Counting white pixels

+            stateCount[currentState]++;

+          }

+        }

+      } // for j=...

+

+      if (foundPatternCross(stateCount)) {

+        handlePossibleCenter(stateCount, i, maxJ);

+      } // end if foundPatternCross

+    } // for i=iSkip-1 ...

+    FinderPattern[][] patternInfo = selectBestPatterns();

+    Vector result = new Vector();

+    for (int i = 0; i < patternInfo.length; i++) {

+      FinderPattern[] pattern = patternInfo[i];

+      ResultPoint.orderBestPatterns(pattern);

+      result.addElement(new FinderPatternInfo(pattern));

+    }

+

+    if (result.isEmpty()) {

+      return EMPTY_RESULT_ARRAY;

+    } else {

+      FinderPatternInfo[] resultArray = new FinderPatternInfo[result.size()];

+      for (int i = 0; i < result.size(); i++) {

+        resultArray[i] = (FinderPatternInfo) result.elementAt(i);

+      }

+      return resultArray;

+    }

+  }

+

+}