--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/mupdf-source/thirdparty/tesseract/src/ccstruct/quspline.cpp	Mon Sep 15 11:43:07 2025 +0200
@@ -0,0 +1,402 @@
+/**********************************************************************
+ * File:        quspline.cpp  (Formerly qspline.c)
+ * Description: Code for the QSPLINE class.
+ * Author:      Ray Smith
+ *
+ * (C) Copyright 1991, Hewlett-Packard Ltd.
+ ** 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.
+ *
+ **********************************************************************/
+
+// Include automatically generated configuration file if running autoconf.
+#ifdef HAVE_CONFIG_H
+#  include "config_auto.h"
+#endif
+
+#include "quspline.h"
+
+#include "points.h"   // for ICOORD
+#include "quadlsq.h"  // for QLSQ
+#include "quadratc.h" // for QUAD_COEFFS
+
+#include <allheaders.h> // for pixRenderPolyline, pixGetDepth, pixGetHeight
+#include "pix.h"        // for L_CLEAR_PIXELS, L_SET_PIXELS, Pix (ptr only)
+
+namespace tesseract {
+
+#define QSPLINE_PRECISION 16 // no of steps to draw
+
+/**********************************************************************
+ * QSPLINE::QSPLINE
+ *
+ * Constructor to build a QSPLINE given the components used in the old code.
+ **********************************************************************/
+
+QSPLINE::QSPLINE(     // constructor
+    int32_t count,    // no of segments
+    int32_t *xstarts, // start coords
+    double *coeffs    // coefficients
+) {
+  int32_t index; // segment index
+
+  // get memory
+  xcoords = new int32_t[count + 1];
+  quadratics = new QUAD_COEFFS[count];
+  segments = count;
+  for (index = 0; index < segments; index++) {
+    // copy them
+    xcoords[index] = xstarts[index];
+    quadratics[index] =
+        QUAD_COEFFS(coeffs[index * 3], coeffs[index * 3 + 1], coeffs[index * 3 + 2]);
+  }
+  // right edge
+  xcoords[index] = xstarts[index];
+}
+
+/**********************************************************************
+ * QSPLINE::QSPLINE
+ *
+ * Constructor to build a QSPLINE by appproximation of points.
+ **********************************************************************/
+
+QSPLINE::QSPLINE(               // constructor
+    int xstarts[],              // spline boundaries
+    int segcount,               // no of segments
+    int xpts[],                 // points to fit
+    int ypts[], int pointcount, // no of pts
+    int degree                  // fit required
+) {
+  int pointindex;    /*no along text line */
+  int segment;       /*segment no */
+  int32_t *ptcounts; // no in each segment
+  QLSQ qlsq;         /*accumulator */
+
+  segments = segcount;
+  xcoords = new int32_t[segcount + 1];
+  ptcounts = new int32_t[segcount + 1];
+  quadratics = new QUAD_COEFFS[segcount];
+  memmove(xcoords, xstarts, (segcount + 1) * sizeof(int32_t));
+  ptcounts[0] = 0; /*none in any yet */
+  for (segment = 0, pointindex = 0; pointindex < pointcount; pointindex++) {
+    while (segment < segcount && xpts[pointindex] >= xstarts[segment]) {
+      segment++; /*try next segment */
+                 /*cumulative counts */
+      ptcounts[segment] = ptcounts[segment - 1];
+    }
+    ptcounts[segment]++; /*no in previous partition */
+  }
+  while (segment < segcount) {
+    segment++;
+    /*zero the rest */
+    ptcounts[segment] = ptcounts[segment - 1];
+  }
+
+  for (segment = 0; segment < segcount; segment++) {
+    qlsq.clear();
+    /*first blob */
+    pointindex = ptcounts[segment];
+    if (pointindex > 0 && xpts[pointindex] != xpts[pointindex - 1] &&
+        xpts[pointindex] != xstarts[segment]) {
+      qlsq.add(xstarts[segment],
+               ypts[pointindex - 1] + (ypts[pointindex] - ypts[pointindex - 1]) *
+                                          (xstarts[segment] - xpts[pointindex - 1]) /
+                                          (xpts[pointindex] - xpts[pointindex - 1]));
+    }
+    for (; pointindex < ptcounts[segment + 1]; pointindex++) {
+      qlsq.add(xpts[pointindex], ypts[pointindex]);
+    }
+    if (pointindex > 0 && pointindex < pointcount && xpts[pointindex] != xstarts[segment + 1]) {
+      qlsq.add(xstarts[segment + 1],
+               ypts[pointindex - 1] + (ypts[pointindex] - ypts[pointindex - 1]) *
+                                          (xstarts[segment + 1] - xpts[pointindex - 1]) /
+                                          (xpts[pointindex] - xpts[pointindex - 1]));
+    }
+    qlsq.fit(degree);
+    quadratics[segment].a = qlsq.get_a();
+    quadratics[segment].b = qlsq.get_b();
+    quadratics[segment].c = qlsq.get_c();
+  }
+  delete[] ptcounts;
+}
+
+/**********************************************************************
+ * QSPLINE::QSPLINE
+ *
+ * Constructor to build a QSPLINE from another.
+ **********************************************************************/
+
+QSPLINE::QSPLINE( // constructor
+    const QSPLINE &src) {
+  segments = 0;
+  xcoords = nullptr;
+  quadratics = nullptr;
+  *this = src;
+}
+
+/**********************************************************************
+ * QSPLINE::~QSPLINE
+ *
+ * Destroy a QSPLINE.
+ **********************************************************************/
+
+QSPLINE::~QSPLINE() {
+  delete[] xcoords;
+  delete[] quadratics;
+}
+
+/**********************************************************************
+ * QSPLINE::operator=
+ *
+ * Copy a QSPLINE
+ **********************************************************************/
+
+QSPLINE &QSPLINE::operator=( // assignment
+    const QSPLINE &source) {
+  delete[] xcoords;
+  delete[] quadratics;
+
+  segments = source.segments;
+  xcoords = new int32_t[segments + 1];
+  quadratics = new QUAD_COEFFS[segments];
+  memmove(xcoords, source.xcoords, (segments + 1) * sizeof(int32_t));
+  memmove(quadratics, source.quadratics, segments * sizeof(QUAD_COEFFS));
+  return *this;
+}
+
+/**********************************************************************
+ * QSPLINE::step
+ *
+ * Return the total of the step functions between the given coords.
+ **********************************************************************/
+
+double QSPLINE::step( // find step functions
+    double x1,        // between coords
+    double x2) {
+  int index1, index2; // indices of coords
+  double total;       /*total steps */
+
+  index1 = spline_index(x1);
+  index2 = spline_index(x2);
+  total = 0;
+  while (index1 < index2) {
+    total += static_cast<double>(quadratics[index1 + 1].y(static_cast<float>(xcoords[index1 + 1])));
+    total -= static_cast<double>(quadratics[index1].y(static_cast<float>(xcoords[index1 + 1])));
+    index1++; /*next segment */
+  }
+  return total; /*total steps */
+}
+
+/**********************************************************************
+ * QSPLINE::y
+ *
+ * Return the y value at the given x value.
+ **********************************************************************/
+
+double QSPLINE::y( // evaluate
+    double x       // coord to evaluate at
+    ) const {
+  int32_t index; // segment index
+
+  index = spline_index(x);
+  return quadratics[index].y(x); // in correct segment
+}
+
+/**********************************************************************
+ * QSPLINE::spline_index
+ *
+ * Return the index to the largest xcoord not greater than x.
+ **********************************************************************/
+
+int32_t QSPLINE::spline_index( // evaluate
+    double x                   // coord to evaluate at
+    ) const {
+  int32_t index;  // segment index
+  int32_t bottom; // bottom of range
+  int32_t top;    // top of range
+
+  bottom = 0;
+  top = segments;
+  while (top - bottom > 1) {
+    index = (top + bottom) / 2; // centre of range
+    if (x >= xcoords[index]) {
+      bottom = index; // new min
+    } else {
+      top = index; // new max
+    }
+  }
+  return bottom;
+}
+
+/**********************************************************************
+ * QSPLINE::move
+ *
+ * Reposition spline by vector
+ **********************************************************************/
+
+void QSPLINE::move( // reposition spline
+    ICOORD vec      // by vector
+) {
+  int32_t segment; // index of segment
+  int16_t x_shift = vec.x();
+
+  for (segment = 0; segment < segments; segment++) {
+    xcoords[segment] += x_shift;
+    quadratics[segment].move(vec);
+  }
+  xcoords[segment] += x_shift;
+}
+
+/**********************************************************************
+ * QSPLINE::overlap
+ *
+ * Return true if spline2 overlaps this by no more than fraction less
+ * than the bounds of this.
+ **********************************************************************/
+
+bool QSPLINE::overlap( // test overlap
+    QSPLINE *spline2,  // 2 cannot be smaller
+    double fraction    // by more than this
+) {
+  int leftlimit = xcoords[1];             /*common left limit */
+  int rightlimit = xcoords[segments - 1]; /*common right limit */
+                                          /*or too non-overlap */
+  return !(spline2->segments < 3 ||
+           spline2->xcoords[1] > leftlimit + fraction * (rightlimit - leftlimit) ||
+           spline2->xcoords[spline2->segments - 1] <
+               rightlimit - fraction * (rightlimit - leftlimit));
+}
+
+/**********************************************************************
+ * extrapolate_spline
+ *
+ * Extrapolates the spline linearly using the same gradient as the
+ * quadratic has at either end.
+ **********************************************************************/
+
+void QSPLINE::extrapolate( // linear extrapolation
+    double gradient,       // gradient to use
+    int xmin,              // new left edge
+    int xmax               // new right edge
+) {
+  int segment;        /*current segment of spline */
+  int dest_segment;   // dest index
+  int32_t *xstarts;   // new boundaries
+  QUAD_COEFFS *quads; // new ones
+  int increment;      // in size
+
+  increment = xmin < xcoords[0] ? 1 : 0;
+  if (xmax > xcoords[segments]) {
+    increment++;
+  }
+  if (increment == 0) {
+    return;
+  }
+  xstarts = new int32_t[segments + 1 + increment];
+  quads = new QUAD_COEFFS[segments + increment];
+  if (xmin < xcoords[0]) {
+    xstarts[0] = xmin;
+    quads[0].a = 0;
+    quads[0].b = gradient;
+    quads[0].c = y(xcoords[0]) - quads[0].b * xcoords[0];
+    dest_segment = 1;
+  } else {
+    dest_segment = 0;
+  }
+  for (segment = 0; segment < segments; segment++) {
+    xstarts[dest_segment] = xcoords[segment];
+    quads[dest_segment] = quadratics[segment];
+    dest_segment++;
+  }
+  xstarts[dest_segment] = xcoords[segment];
+  if (xmax > xcoords[segments]) {
+    quads[dest_segment].a = 0;
+    quads[dest_segment].b = gradient;
+    quads[dest_segment].c = y(xcoords[segments]) - quads[dest_segment].b * xcoords[segments];
+    dest_segment++;
+    xstarts[dest_segment] = xmax + 1;
+  }
+  segments = dest_segment;
+  delete[] xcoords;
+  delete[] quadratics;
+  xcoords = xstarts;
+  quadratics = quads;
+}
+
+/**********************************************************************
+ * QSPLINE::plot
+ *
+ * Draw the QSPLINE in the given colour.
+ **********************************************************************/
+
+#ifndef GRAPHICS_DISABLED
+void QSPLINE::plot(          // draw it
+    ScrollView *window,      // window to draw in
+    ScrollView::Color colour // colour to draw in
+    ) const {
+  int32_t segment;  // index of segment
+  int16_t step;     // index of poly piece
+  double increment; // x increment
+  double x;         // x coord
+
+  window->Pen(colour);
+  for (segment = 0; segment < segments; segment++) {
+    increment = static_cast<double>(xcoords[segment + 1] - xcoords[segment]) / QSPLINE_PRECISION;
+    x = xcoords[segment];
+    for (step = 0; step <= QSPLINE_PRECISION; step++) {
+      if (segment == 0 && step == 0) {
+        window->SetCursor(x, quadratics[segment].y(x));
+      } else {
+        window->DrawTo(x, quadratics[segment].y(x));
+      }
+      x += increment;
+    }
+  }
+}
+#endif
+
+void QSPLINE::plot(Image pix) const {
+  if (pix == nullptr) {
+    return;
+  }
+
+  int32_t segment;  // Index of segment
+  int16_t step;     // Index of poly piece
+  double increment; // x increment
+  double x;         // x coord
+  auto height = static_cast<double>(pixGetHeight(pix));
+  Pta *points = ptaCreate(QSPLINE_PRECISION * segments);
+  const int kLineWidth = 5;
+
+  for (segment = 0; segment < segments; segment++) {
+    increment = static_cast<double>((xcoords[segment + 1] - xcoords[segment])) / QSPLINE_PRECISION;
+    x = xcoords[segment];
+    for (step = 0; step <= QSPLINE_PRECISION; step++) {
+      double y = height - quadratics[segment].y(x);
+      ptaAddPt(points, x, y);
+      x += increment;
+    }
+  }
+
+  switch (pixGetDepth(pix)) {
+    case 1:
+      pixRenderPolyline(pix, points, kLineWidth, L_SET_PIXELS, 1);
+      break;
+    case 32:
+      pixRenderPolylineArb(pix, points, kLineWidth, 255, 0, 0, 1);
+      break;
+    default:
+      pixRenderPolyline(pix, points, kLineWidth, L_CLEAR_PIXELS, 1);
+      break;
+  }
+  ptaDestroy(&points);
+}
+
+} // namespace tesseract