Fix QR decode failure for small/native-size images (#2061)

* Fix QR decode failure for small/native-size images (#1976)

QRCodeWriter.encode(..., 0, 0) produces a 33x33 native-size QR that
ZXing cannot decode. The CENTER_QUORUM filter in selectBestPatterns()
(added in 110ef9e to fix #1567) removes finder patterns with count < 2.
For small images, the row-skip interval (iSkip=3, MIN_SKIP) means the
scanner only crosses the top two finder pattern centers on a single row
each, giving them count=1. The bottom-left pattern gets count=2 because
it's scanned after iSkip drops to 2. The filter then removes the two
count=1 patterns, leaving 1 of the 3 needed, and throws
NotFoundException.

The fix: only apply the CENTER_QUORUM filter when either (a) at least 3
confirmed patterns would survive, or (b) the total candidate list
exceeds a size threshold. This preserves #1567 protection while
allowing small images through.

Why a size threshold: the filter was added to prevent O(n^3) blowup
in the triangle-selection loop when noisy images produce thousands of
spurious candidates. When the candidate list is small (<= 25 entries,
yielding <= ~2300 loop iterations), the cubic cost is negligible
regardless of whether the patterns are real or spurious. A clean
single-QR image produces ~3 candidates; even a noisy image below the
threshold is computationally trivial. Above the threshold, the filter
applies unconditionally, matching today's behavior.

Alternatives considered:
- Removing the filter entirely: all 561 existing tests pass, but
  re-opens #1567 for pathological images with thousands of spurious
  count=1 candidates.
- Reducing MIN_SKIP from 3 to 1 for small images: addresses the
  symptom (more scan rows = higher counts) but doesn't fix the
  fundamental interaction between iSkip and the quorum filter,
  and changes scan behavior for all small images.
- Fallback (try with filter, retry without on failure): re-opens
  #1567 whenever fewer than 3 confirmed patterns exist, which is
  exactly the scenario that produces thousands of unconfirmed
  candidates in noisy images.

* Increase noisy-image test timeout from 5s to 30s

GitHub shared runners timed out at 5s. Local measurement shows ~1.2s,
implying at least 4x slowdown on CI. 30s gives a comfortable margin
while still catching the O(n^3) regression from #1567.

1 files changed, 66 insertions, 0 deletions

diff --git a/core/src/test/java/com/google/zxing/qrcode/FinderPatternFinderPerformanceTestCase.java b/core/src/test/java/com/google/zxing/qrcode/FinderPatternFinderPerformanceTestCase.java
new file mode 100644
index 000000000..60f6e9cb5
--- /dev/null
+++ b/core/src/test/java/com/google/zxing/qrcode/FinderPatternFinderPerformanceTestCase.java
@@ -0,0 +1,66 @@
+/*
+ * Copyright 2026 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.qrcode;
+
+import com.google.zxing.BinaryBitmap;
+import com.google.zxing.BufferedImageLuminanceSource;
+import com.google.zxing.MultiFormatReader;
+import com.google.zxing.NotFoundException;
+import com.google.zxing.common.HybridBinarizer;
+import org.junit.Assert;
+import org.junit.Test;
+
+import javax.imageio.ImageIO;
+import java.awt.image.BufferedImage;
+import java.nio.file.Files;
+import java.nio.file.Path;
+import java.nio.file.Paths;
+
+/**
+ * Regression test for #1567: a noisy image with many spurious finder
+ * pattern candidates must not cause the decoder to hang.
+ */
+public final class FinderPatternFinderPerformanceTestCase
+    extends Assert {
+
+  private static final String IMAGE_PATH =
+      "src/test/resources/blackbox/triggeringImage1567.jpg";
+
+  @Test(timeout = 30000)
+  public void testNoisyImageDoesNotHang() throws Exception {
+    Path file = Paths.get(IMAGE_PATH);
+    if (!Files.exists(file)) {
+      file = Paths.get("core/").resolve(IMAGE_PATH);
+    }
+    assertTrue("Test image not found", Files.exists(file));
+
+    BufferedImage image = ImageIO.read(file.toFile());
+    assertNotNull("Failed to load test image", image);
+
+    BinaryBitmap bitmap = new BinaryBitmap(
+        new HybridBinarizer(
+            new BufferedImageLuminanceSource(image)));
+
+    MultiFormatReader reader = new MultiFormatReader();
+    try {
+      reader.decode(bitmap);
+    } catch (NotFoundException e) {
+      // Expected: no QR code in the image
+    }
+    // If we get here without timeout, the test passes
+  }
+}