Commit 2cd9955e for tesseract

commit 2cd9955ef1c6d2aa9974dfdbb5ff5c4e44603b26
Author: İlkecan Bozdoğan <ilkecan@protonmail.com>
Date:   Sun Aug 16 08:46:18 2026 +0300

    Avoid quadratic paragraph restart scan (#4599)

    Sparse-text page segmentation can produce many one-line blocks and paragraphs. PageIterator::RestartParagraph() scanned forward from the start of the page and called PAGE_RES_IT::cmp() at every paragraph. Since cmp() searches the page structure to order two iterators, the combined scan was quadratic in the number of paragraphs.

    A profile of a 4267x3200 PSM 11 reproducer with 1,681 blocks attributed 80.12% of CPU self time to PAGE_RES_IT::cmp().

    The reproducer, input-4267x3200.png, is generated by repeating a 16x16 texture-only image across a 4267x3200 canvas.

    Instead of comparing iterator positions with cmp(), record the current BLOCK_RES* and PARA* and scan forward until the iterator reaches those exact objects. Pointer comparisons are constant time, making the scan O(n).

    The regression test visits every word of a multi-block fixture. At each position it restarts a copied iterator and verifies the paragraph start flag, bounding box and UTF-8 text.

    The minimal reproducer is 5.8x faster. The exact issue #4430 input completed with the change instead of exceeding the five-minute bound.

diff --git a/src/ccmain/pageiterator.cpp b/src/ccmain/pageiterator.cpp
index 43cbebf4..0d10398c 100644
--- a/src/ccmain/pageiterator.cpp
+++ b/src/ccmain/pageiterator.cpp
@@ -111,15 +111,20 @@ void PageIterator::RestartParagraph() {
   if (it_->block() == nullptr) {
     return; // At end of the document.
   }
+  const BLOCK_RES *target_block = it_->block();
+  const PARA *target_para = it_->row() == nullptr ? nullptr : it_->row()->row->para();
   PAGE_RES_IT para(page_res_);
-  PAGE_RES_IT next_para(para);
-  next_para.forward_paragraph();
-  while (next_para.cmp(*it_) <= 0) {
-    para = next_para;
-    next_para.forward_paragraph();
+  // Paragraph and block identities are stable within PAGE_RES. Avoid cmp(),
+  // which searches the page and makes this forward scan quadratic.
+  while (para.block() != nullptr &&
+         (para.block() != target_block ||
+          (para.row() != nullptr && para.row()->row->para() != target_para))) {
+    para.forward_paragraph();
+  }
+  if (para.block() != nullptr) {
+    *it_ = para;
+    BeginWord(0);
   }
-  *it_ = para;
-  BeginWord(0);
 }

 bool PageIterator::IsWithinFirstTextlineOfParagraph() const {
diff --git a/unittest/resultiterator_test.cc b/unittest/resultiterator_test.cc
index f1ad05d8..12021081 100644
--- a/unittest/resultiterator_test.cc
+++ b/unittest/resultiterator_test.cc
@@ -355,6 +355,42 @@ TEST_F(ResultIteratorTest, ComplexTest) {
   delete it;
 }

+// Tests that restarting at a paragraph preserves the current paragraph while
+// iterating a page with multiple blocks and paragraphs.
+TEST_F(ResultIteratorTest, RestartParagraphTest) {
+  SetImage("8087_054.3B.tif");
+  ASSERT_EQ(api_.Recognize(nullptr), 0);
+  ResultIterator *it = api_.GetIterator();
+  ASSERT_NE(it, nullptr);
+  do {
+    int left;
+    int top;
+    int right;
+    int bottom;
+    ASSERT_TRUE(it->BoundingBox(tesseract::RIL_PARA, &left, &top, &right, &bottom));
+    char *paragraph_text = it->GetUTF8Text(tesseract::RIL_PARA);
+
+    ResultIterator paragraph_start(*it);
+    paragraph_start.RestartParagraph();
+    EXPECT_TRUE(paragraph_start.IsAtBeginningOf(tesseract::RIL_PARA));
+    int start_left;
+    int start_top;
+    int start_right;
+    int start_bottom;
+    ASSERT_TRUE(paragraph_start.BoundingBox(tesseract::RIL_PARA, &start_left, &start_top,
+                                            &start_right, &start_bottom));
+    EXPECT_EQ(left, start_left);
+    EXPECT_EQ(top, start_top);
+    EXPECT_EQ(right, start_right);
+    EXPECT_EQ(bottom, start_bottom);
+    char *start_text = paragraph_start.GetUTF8Text(tesseract::RIL_PARA);
+    EXPECT_STREQ(paragraph_text, start_text);
+    delete[] paragraph_text;
+    delete[] start_text;
+  } while (it->Next(tesseract::RIL_WORD));
+  delete it;
+}
+
 // Tests image rebuild on the UNLV page numbered 8087_054.3G.tif. (Dubrovnik)
 TEST_F(ResultIteratorTest, GreyTest) {
   SetImage("8087_054.3G.tif");