/*!
Copyright (c) 2023 Paul Miller (paulmillr.com)
The library paulmillr-qr is dual-licensed under the Apache 2.0 OR MIT license.
You can select a license of your choice.
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.
*/
/**
 * Methods for decoding (reading) QR code patterns.
 * @module
 */

import type { EncodingType, ErrorCorrection, Image, Mask, Point, TArg, TRet } from './index.ts';
import { Bitmap, utils } from './index.ts';

// Constants
const MAX_BITS_ERROR = 3; // Up to 3 bit errors in version/format
// Kept at 8: the block-stat fast path reads two u32 words per row and the
// average uses `sum >>> 6`, so the current binarizer assumes 8x8 = 64 pixels.
const GRAYSCALE_BLOCK_SIZE = 8;
const GRAYSCALE_RANGE = 24;
const PATTERN_VARIANCE = 2;
// Diagonal finder scans are noisier under blur/perspective than horizontal or
// vertical runs, so they use a looser ratio tolerance.
const PATTERN_VARIANCE_DIAGONAL = 1.333;
const PATTERN_MIN_CONFIRMATIONS = 2;
const DETECT_MIN_ROW_SKIP = 3;
// Pair LUTs for the 8x8 block-stat fast path: each 16-bit lane holds two
// brightness bytes, so we can accumulate sum/min/max four pixels at a time.
const SUM16 = new Uint16Array(1 << 16);
const MIN16 = new Uint8Array(1 << 16);
const MAX16 = new Uint8Array(1 << 16);
for (let i = 0; i < SUM16.length; i++) {
  const lo = i & 0xff;
  const hi = i >>> 8;
  SUM16[i] = lo + hi;
  MIN16[i] = lo < hi ? lo : hi;
  MAX16[i] = lo > hi ? lo : hi;
}

// TODO: move to index, nearby with bitmap and other graph related stuff?
// Fast truncation for values expected to be non-negative; negatives would wrap
// through uint32 because this uses `>>> 0`, not `Math.floor()`.
const int = (n: number) => n >>> 0;

type Point4 = [Point, Point, Point, Point];
/** Finder and alignment points returned by the detector. */
export type FinderPoints = [Pattern, Pattern, Point, Pattern];
// distance ^ 2
const distance2 = (p1: Point, p2: Point) => {
  const x = p1.x - p2.x;
  const y = p1.y - p2.y;
  return x * x + y * y;
};
const distance = (p1: Point, p2: Point) => Math.sqrt(distance2(p1, p2));
const sum = (lst: number[]) => lst.reduce((acc, i) => acc + i);
const pointIncr = (p: Point, incr: Point) => {
  p.x += incr.x;
  p.y += incr.y;
};
const pointNeg = (p: Point) => ({ x: -p.x, y: -p.y });
const pointMirror = (p: Point) => ({ x: p.y, y: p.x });
const pointClone = (p: Point) => ({ x: p.x, y: p.y });
const pointInt = (p: Point) => ({ x: int(p.x), y: int(p.y) });
const pointAdd = (a: Point, b: Point) => ({ x: a.x + b.x, y: a.y + b.y });
// Count trailing zeroes in a packed bitmap word so scanLine can skip whole
// runs instead of testing one bit at a time.
const ctz32 = (v: number) => {
  v = v >>> 0;
  if (v === 0) return 32;
  return 31 - Math.clz32((v & -v) >>> 0);
};
function cap(value: number, min?: number, max?: number): number {
  // ISO/IEC 18004:2024 §12 h) builds the sampling grid from "module centres";
  // detector callers pass `0` as a real image edge when clipping those samples
  // and search windows. `|| value` treats that bound as absent.
  let res = value;
  if (max !== undefined) res = Math.min(res, max);
  if (min !== undefined) res = Math.max(res, min);
  return res;
}
function getBytesPerPixel(img: TArg<Image>): number {
  const image = img as Image;
  const perPixel = image.data.length / (image.width * image.height);
  if (perPixel === 3 || perPixel === 4) return perPixel; // RGB or RGBA
  throw new Error(`Unknown image format, bytes per pixel=${perPixel}`);
}
function isBytes(data: unknown): data is Uint8Array {
  return data instanceof Uint8Array || data instanceof Uint8ClampedArray;
}
/**
 * Convert to grayscale. The function is the most expensive part of decoding:
 * it takes up to 90% of time.
 *
 * Binarization pipeline:
 * 1. Convert RGB/RGBA image to one luma byte per pixel.
 * 2. Split the image into 8x8 blocks and collect per-block mean/min/max.
 * 3. Build a 5x5 neighborhood mean over those block means.
 * 4. Turn each 8x8 block into bitmap bits using a local cut derived from:
 *    - the neighborhood mean,
 *    - the current block statistics,
 *    - a cheap whole-image color-spread estimate,
 *    - and, on risky scenes, a local variance field over block means.
 *
 * Instead of producing "best looking" thresholding: we produce a
 * bitmap where finder patterns survive perspective / blur / highlights while
 * keeping false dark regions low enough for downstream finder selection.
 */
function toBitmap(img: TArg<Image>): TRet<Bitmap> {
  const image = img as Image;
  const width = image.width;
  const height = image.height;
  const data = image.data;
  const bytesPerPixel = getBytesPerPixel(img);
  const pixLen = height * width;
  const brightness = new Uint8Array(pixLen);
  if (bytesPerPixel === 4 && isBytes(data) && (data.byteOffset & 3) === 0) {
    // Little-endian RGBA: compute four grayscale bytes and commit as one u32 store.
    // Unaligned RGBA subarray views are still valid inputs; they fall back to
    // the scalar path because Uint32Array would throw on a misaligned offset.
    const pixels = new Uint32Array(data.buffer, data.byteOffset, pixLen);
    const bright32 = new Uint32Array(
      brightness.buffer,
      brightness.byteOffset,
      brightness.length >>> 2
    );
    const n4 = pixels.length & ~3;
    for (let i = 0, j = 0; i < n4; i += 4, j++) {
      const v0 = pixels[i] >>> 0;
      const v1 = pixels[i + 1] >>> 0;
      const v2 = pixels[i + 2] >>> 0;
      const v3 = pixels[i + 3] >>> 0;
      // RGBA words are little-endian here, so this is `(r + 2*g + b) / 4`
      // computed from the packed byte lanes for four pixels at once.
      const b0 = ((v0 & 0xff) + (((v0 >>> 8) & 0xff) << 1) + ((v0 >>> 16) & 0xff)) >>> 2;
      const b1 = ((v1 & 0xff) + (((v1 >>> 8) & 0xff) << 1) + ((v1 >>> 16) & 0xff)) >>> 2;
      const b2 = ((v2 & 0xff) + (((v2 >>> 8) & 0xff) << 1) + ((v2 >>> 16) & 0xff)) >>> 2;
      const b3 = ((v3 & 0xff) + (((v3 >>> 8) & 0xff) << 1) + ((v3 >>> 16) & 0xff)) >>> 2;
      bright32[j] = b0 | (b1 << 8) | (b2 << 16) | (b3 << 24);
    }
    for (let i = n4; i < pixels.length; i++) {
      const v = pixels[i] >>> 0;
      brightness[i] = ((v & 0xff) + (((v >>> 8) & 0xff) << 1) + ((v >>> 16) & 0xff)) >>> 2;
    }
  } else {
    for (let i = 0, j = 0, d = data; i < d.length; i += bytesPerPixel) {
      const r = d[i];
      const g = d[i + 1];
      const b = d[i + 2];
      brightness[j++] = int((r + 2 * g + b) / 4) & 0xff;
    }
  }
  // Sampled color spread is a cheap "scene type" signal:
  // grayscale / flat lighting scenes want conservative cuts, while colorful or
  // high-spread scenes benefit from a slightly darker threshold.
  let spreadSum = 0;
  let spreadCnt = 0;
  const spreadStep = bytesPerPixel * 16;
  for (let i = 0; i < data.length; i += spreadStep) {
    const r = data[i];
    const g = data[i + 1];
    const b = data[i + 2];
    // hi=max(r,g,b), lo=min(r,g,b): this sampled channel spread is a cheap
    // scene-level proxy for "how colorful / highlighty is this frame?".
    const hi = r > g ? (r > b ? r : b) : g > b ? g : b;
    const lo = r < g ? (r < b ? r : b) : g < b ? g : b;
    spreadSum += hi - lo;
    spreadCnt++;
  }
  const spreadMean = spreadSum / spreadCnt;
  // Convert to bitmap
  const block = GRAYSCALE_BLOCK_SIZE;
  if (width < block * 5 || height < block * 5) throw new Error('image too small');
  const bWidth = Math.ceil(width / block);
  const bHeight = Math.ceil(height / block);
  const maxY = height - block;
  const maxX = width - block;
  const blockLen = bWidth * bHeight;
  const blockState = new Uint32Array(blockLen);
  // Each 8x8 block stores packed:
  // - bits 0..7: block baseline brightness used by the threshold field
  // - bits 8..15: block min
  // - bits 16..23: block max
  let hiRangeCnt = 0;
  let veryLowCnt = 0;
  const padW = (width + 3) & ~3;
  let statStride = width;
  let stat32: Uint32Array;
  if ((width & 3) !== 0) {
    const padLen = padW * height;
    const brightPad = new Uint8Array(padLen);
    for (let y = 0; y < height; y++) {
      const src = y * width;
      const dst = y * padW;
      brightPad.set(brightness.subarray(src, src + width), dst);
    }
    // Misaligned widths are padded only for the block-stat fast path.
    statStride = padW;
    stat32 = new Uint32Array(brightPad.buffer, brightPad.byteOffset, (padW * height) >>> 2);
  } else
    stat32 = new Uint32Array(brightness.buffer, brightness.byteOffset, brightness.length >>> 2);
  for (let y = 0; y < bHeight; y++) {
    const yPos = cap(y * block, 0, maxY);
    for (let x = 0; x < bWidth; x++) {
      const xPos = cap(x * block, 0, maxX);
      let sum = 0;
      let min = 0xff;
      let max = 0;
      // The stat-LUT fast path needs the 8-pixel row start to be 32-bit aligned
      // so each row can be read as two full u32 words without any shifts.
      if ((xPos & 3) === 0) {
        for (let yy = 0, pos = yPos * statStride + xPos; yy < block; yy++, pos += statStride) {
          const p = pos >>> 2;
          const w0 = stat32[p] >>> 0;
          const w1 = stat32[p + 1] >>> 0;
          const a0 = w0 & 0xffff;
          const a1 = w0 >>> 16;
          const b0 = w1 & 0xffff;
          const b1 = w1 >>> 16;
          sum += SUM16[a0] + SUM16[a1] + SUM16[b0] + SUM16[b1];
          const min0 = MIN16[a0];
          const min1 = MIN16[a1];
          const min2 = MIN16[b0];
          const min3 = MIN16[b1];
          if (min0 < min) min = min0;
          if (min1 < min) min = min1;
          if (min2 < min) min = min2;
          if (min3 < min) min = min3;
          const max0 = MAX16[a0];
          const max1 = MAX16[a1];
          const max2 = MAX16[b0];
          const max3 = MAX16[b1];
          if (max0 > max) max = max0;
          if (max1 > max) max = max1;
          if (max2 > max) max = max2;
          if (max3 > max) max = max3;
        }
      } else {
        for (let yy = 0, pos = yPos * width + xPos; yy < block; yy++, pos += width) {
          for (let xx = 0; xx < block; xx++) {
            const pixel = brightness[pos + xx];
            sum += pixel;
            if (pixel < min) min = pixel;
            if (pixel > max) max = pixel;
          }
        }
      }
      const bIdx = bWidth * y + x;
      const range = max - min;
      // Average brightness of block
      let average = sum >>> 6;
      if (range <= GRAYSCALE_RANGE) {
        // Low-contrast blocks are unstable if we threshold from their raw mean.
        // Bias toward the local dark floor, then smooth with already-seen
        // neighbors so finder rings don't disappear in washed-out regions.
        average = min / 2;
        if (y > 0 && x > 0) {
          const idx = (x: number, y: number) => y * bWidth + x;
          const neighborNumerator =
            (blockState[idx(x, y - 1)] & 0xff) +
            2 * (blockState[idx(x - 1, y)] & 0xff) +
            (blockState[idx(x - 1, y - 1)] & 0xff);
          if (min * 4 < neighborNumerator) average = neighborNumerator / 4;
        }
      }
      blockState[bIdx] = int(average) | (min << 8) | (max << 16);
      if (range > 40 && average < 224) hiRangeCnt++;
      if (range <= 10) veryLowCnt++;
    }
  }
  const hiRangeFrac = hiRangeCnt / blockLen;
  const veryLowFrac = veryLowCnt / blockLen;
  // These two scene gates are the main "policy" layer on top of the local cut:
  // - `spotBias` darkens globally flat, slightly colorful scenes that otherwise
  //   miss bright-spot / washed-out QR modules.
  // - `useVarField` avoids paying the variance-field cost on scenes where the
  //   plain 5x5 mean is already stable enough.
  const spotBias =
    veryLowFrac > 0.55 &&
    veryLowFrac < 0.66 &&
    hiRangeFrac < 0.02 &&
    spreadMean > 10 &&
    spreadMean < 20
      ? -1
      : 0;
  const useVarField = veryLowFrac < 0.62 || spreadMean > 30;
  const iWidth = bWidth + 1;
  const iHeight = bHeight + 1;
  const integLen = iHeight * iWidth;
  // `integ` is the standard summed-area table of block means.
  const integ = new Uint32Array(integLen);
  // `integSqr` is the square-integral / summed-area table of `v * v` over the
  // same block means, not a u8 pixel buffer. Those prefix sums can overflow
  // 32-bit integer storage on large images, and Float32 was the measured
  // faster compromise vs Float64 for this heuristic field.
  const integSqr = useVarField ? new Float32Array(integLen) : undefined;
  for (let y = 0; y < bHeight; y++) {
    let rowSum = 0;
    let rowSq = 0;
    const bRow = y * bWidth;
    const iRow = (y + 1) * iWidth;
    const iPrev = y * iWidth;
    for (let x = 0; x < bWidth; x++) {
      const v = blockState[bRow + x] & 0xff;
      rowSum += v;
      if (integSqr) rowSq += v * v;
      integ[iRow + x + 1] = integ[iPrev + x + 1] + rowSum;
      if (integSqr) integSqr[iRow + x + 1] = integSqr[iPrev + x + 1] + rowSq;
    }
  }
  const matrix = new Bitmap({ width, height });
  const rows = Math.ceil(width / 32);
  // Decode intentionally writes the packed bitmap words directly here. The
  // per-pixel Bitmap API is too expensive on this hot path, so this must stay
  // in sync with Bitmap's internal `value` layout.
  const bm = (matrix as unknown as { value: Uint32Array }).value;
  const rad = 2;
  const win = rad * 2 + 1;
  const area = win * win;
  for (let y = 0; y < bHeight; y++) {
    const yPos = cap(y * block, 0, maxY);
    const top = cap(y, rad, bHeight - rad - 1);
    const y0 = top - rad;
    const y1 = top + rad;
    const r0 = y0 * iWidth;
    const r1 = (y1 + 1) * iWidth;
    for (let x = 0; x < bWidth; x++) {
      const xPos = cap(x * block, 0, maxX);
      const shift = xPos & 31;
      const col = xPos >>> 5;
      const left = cap(x, rad, bWidth - rad - 1);
      const x0 = left - rad;
      const x1 = left + rad;
      // 5x5 blocks average
      const sum = integ[r1 + (x1 + 1)] - integ[r0 + (x1 + 1)] - integ[r1 + x0] + integ[r0 + x0];
      // `average` is the coarse threshold surface: a 5x5 neighborhood mean of
      // the 8x8 block means. The adjustments below decide when to move away
      // from that surface for the current block.
      const average = (sum / area) | 0;
      let cut = average;
      const bIdx = bWidth * y + x;
      const blk = blockState[bIdx];
      const blockAvg = blk & 0xff;
      const min = (blk >>> 8) & 0xff;
      const max = blk >>> 16;
      const range = max - min;
      if (average < min) continue;
      if (average >= max) {
        const m = 0xff;
        for (let yy = 0, row = yPos * rows + col; yy < block; yy++, row += rows) {
          const lo = (m << shift) >>> 0;
          bm[row] |= lo;
          if (shift > 24) bm[row + 1] |= m >>> (32 - shift);
        }
        continue;
      }
      // `localAdj`: nudge toward the current block when it is darker than
      // its neighborhood. This helps preserve dark rings / modules that are
      // locally meaningful but diluted by the 5x5 field.
      let localAdj = (blockAvg - average) >> 4;
      if (localAdj < 0) localAdj = 0;
      if (localAdj > 1) localAdj = 1;
      // `chromaAdj`: in colorful, mid-tone blocks, slight extra darkening
      // helps where luma alone underestimates QR structure.
      let chromaAdj = 0;
      if (range > 6 && average > 48 && average < 232) {
        const spreadBoost = spreadMean > 8 ? spreadMean - 8 : 0;
        const mid = 128 - Math.abs(average - 128);
        chromaAdj = int((spreadBoost * (range - 6) * mid) / 2200000);
        if (chromaAdj > 1) chromaAdj = 1;
      }
      // `varAdj`: if the surrounding block field has real variance, darken
      // more aggressively when the local mean still sits far above the
      // block minimum. This is what rescues many weak finder cases.
      let varAdj = 0;
      if (integSqr && range >= 6 && range <= 128) {
        const sq =
          integSqr[r1 + (x1 + 1)] - integSqr[r0 + (x1 + 1)] - integSqr[r1 + x0] + integSqr[r0 + x0];
        const meanSq = sq / area;
        let variance = meanSq - average * average;
        if (variance < 0) variance = 0;
        const gap = average - min;
        const num = gap * (variance - 196);
        const den = (variance + 832) * 9;
        // `variance` is clamped non-negative, so `den` stays strictly positive.
        varAdj = int(num / den);
        if (varAdj < -1) varAdj = -1;
        if (varAdj > 4) varAdj = 4;
      }
      cut = average + localAdj + chromaAdj + varAdj;
      // Small scene-level nudges are intentionally separate from the three
      // local terms above: they are cheap and only target known whole-scene
      // failure modes such as washed-out bright-spot images.
      if (spreadMean > 10 && range >= 8 && range <= 96 && average > min + 8 && average < 192) cut++;
      if (veryLowFrac > 0.68 && veryLowFrac < 0.86 && range >= 6 && range <= 20 && average < 196)
        cut++;
      cut += spotBias;
      if (cut < min) cut = min;
      if (cut > max) cut = max;
      // Emit one 8-pixel row of the current 8x8 block: compare against the
      // block cut, pack the 8 black/white decisions into one byte, then OR
      // that byte into the bitmap word(s) at the current x-bit offset.
      for (
        let yy = 0, pos = yPos * width + xPos, row = yPos * rows + col;
        yy < block;
        yy++, pos += width, row += rows
      ) {
        let m = 0;
        if (brightness[pos] <= cut) m |= 1;
        if (brightness[pos + 1] <= cut) m |= 2;
        if (brightness[pos + 2] <= cut) m |= 4;
        if (brightness[pos + 3] <= cut) m |= 8;
        if (brightness[pos + 4] <= cut) m |= 16;
        if (brightness[pos + 5] <= cut) m |= 32;
        if (brightness[pos + 6] <= cut) m |= 64;
        if (brightness[pos + 7] <= cut) m |= 128;
        if (m === 0) continue;
        const lo = (m << shift) >>> 0;
        bm[row] |= lo;
        if (shift > 24) bm[row + 1] |= m >>> (32 - shift);
      }
    }
  }
  return matrix as TRet<Bitmap>;
}

// Various utilities for pattern
type Pattern = Point & { moduleSize: number; count: number };
function patternEquals(p: Pattern, p2: Pattern) {
  if (Math.abs(p2.y - p.y) <= p2.moduleSize && Math.abs(p2.x - p.x) <= p2.moduleSize) {
    const diff = Math.abs(p2.moduleSize - p.moduleSize);
    return diff <= 1.0 || diff <= p.moduleSize;
  }
  return false;
}

function patternMerge(a: Pattern, b: Pattern) {
  const count = a.count + b.count;
  return {
    x: (a.count * a.x + b.count * b.x) / count,
    y: (a.count * a.y + b.count * b.y) / count,
    moduleSize: (a.count * a.moduleSize + b.count * b.moduleSize) / count,
    count,
  };
}

const patternsConfirmed = (lst: Pattern[]) =>
  lst.filter((i) => i.count >= PATTERN_MIN_CONFIRMATIONS);

type Runs = number[];
/**
 * Since pattern means runs of identical color (dark or white), we cannot
 * have pattern like [true, true], because it will be hard to separate same color runs.
 * @param p boolean pattern
 * @param size size of run relative to others
 * @returns
 */
function pattern(p: boolean[], size?: number[]) {
  const _size = size || utils.fillArr(p.length, 1);
  if (p.length !== _size.length) throw new Error('invalid pattern');
  if (!(p.length & 1)) throw new Error('invalid pattern, length should be odd');
  const res = {
    center: Math.ceil(p.length / 2) - 1,
    length: p.length,
    pattern: p,
    size: _size,
    runs: () => utils.fillArr(p.length, 0),
    totalSize: sum(_size),
    total: (runs: Runs) => runs.reduce((acc, i) => acc + i),
    shift: (runs: Runs, n: number) => {
      for (let i = 0; i < runs.length - n; i++) runs[i] = runs[i + 2];
      for (let i = runs.length - n; i < runs.length; i++) runs[i] = 0;
    },
    checkSize(runs: Runs, moduleSize: number, v = PATTERN_VARIANCE) {
      const variance = moduleSize / v;
      for (let i = 0; i < runs.length; i++) {
        if (Math.abs(_size[i] * moduleSize - runs[i]) >= _size[i] * variance) return false;
      }
      return true;
    },
    add(out: Pattern[], x: number, y: number, total: number) {
      // ISO/IEC 18004:2024 §5.3.3.1 gives finder runs as "1:1:3:1:1";
      // §5.3.6 defines alignment as "5 x 5 dark modules", "3 x 3 light
      // modules", and a central dark module. Use this pattern's own run width
      // so alignment candidates are not divided by finder width 7.
      const moduleSize = total / res.totalSize;
      const cur = { x, y, moduleSize, count: 1 };
      for (let idx = 0; idx < out.length; idx++) {
        const f = out[idx];
        if (!patternEquals(f, cur)) continue;
        return (out[idx] = patternMerge(f, cur));
      }
      out.push(cur);
      return;
    },
    toCenter(runs: Runs, end: number) {
      for (let i = p.length - 1; i > res.center; i--) end -= runs[i];
      end -= runs[res.center] / 2;
      return end;
    },
    check(b: TArg<Bitmap>, runs: Runs, center: Point, incr: Point, maxCount?: number) {
      const bm = b as Bitmap;
      let j = 0;
      let i = pointClone(center);
      const neg = pointNeg(incr);
      const check = (p: number, step: Point) => {
        for (; bm.isInside(i) && !!bm.point(i) === res.pattern[p]; pointIncr(i, step)) {
          runs[p]++;
          j++;
        }
        if (runs[p] === 0) return true;
        const center = p === res.center;
        if (maxCount && !center && runs[p] > res.size[p] * maxCount) return true;
        return false;
      };
      for (let p = res.center; p >= 0; p--) if (check(p, neg)) return false;
      i = pointClone(center);
      pointIncr(i, incr);
      j = 1;
      for (let p = res.center; p < res.length; p++) if (check(p, incr)) return false;
      return j;
    },
    scanLine(
      b: TArg<Bitmap>,
      y: number,
      xStart: number,
      xEnd: number,
      fn: (runs: Runs, x: number) => boolean | void
    ) {
      const bm = b as Bitmap;
      const runs = res.runs();
      // Finder scanning also couples to Bitmap internals so it can scan packed
      // 32-bit words directly instead of re-reading one pixel bit at a time.
      const words = (bm as unknown as { words: number }).words;
      const vals = (bm as unknown as { value: Uint32Array }).value;
      const row = y * words;
      const pattern = res.pattern;
      // Scan one packed bitmap row by jumping whole equal-bit runs inside 32-bit
      // words; this keeps finder scanning from degenerating into per-pixel work.
      const bitAt = (x: number) => ((vals[row + (x >>> 5)] >>> (x & 31)) & 1) === 1;
      const runLen = (x: number, want: boolean) => {
        let wi = row + (x >>> 5);
        let bit = x & 31;
        let w = (vals[wi] >>> bit) >>> 0;
        let left = xEnd - x;
        let len = 0;
        while (left > 0) {
          const room = 32 - bit;
          let n = want ? ctz32(~w >>> 0) : ctz32(w);
          if (n > room) n = room;
          if (n > left) n = left;
          len += n;
          if (n < room && n < left) break;
          left -= n;
          if (left <= 0) break;
          wi++;
          bit = 0;
          w = vals[wi] >>> 0;
        }
        return len;
      };
      let pos = 0;
      let x = xStart;
      // If we start in middle of an image, skip first pattern run,
      // since we don't know run length of pixels from left side
      if (xStart) x += runLen(x, pattern[0]);
      for (; x < xEnd; x++) {
        const cur = bitAt(x);
        // Same run, continue counting
        if (cur === pattern[pos]) {
          const n = runLen(x, cur);
          runs[pos] += n;
          x += n - 1;
          // If not last element - continue counting
          if (x !== bm.width - 1) continue;
          // Last element finishes run, set x outside of run
          x++;
        }
        // Not last run: count new one
        if (pos !== res.length - 1) {
          runs[++pos]++;
          continue;
        }
        const found = fn(runs, x);
        if (found) {
          // We found pattern, reset runs counting
          pos = 0;
          runs.fill(0);
        } else if (found === false) {
          // Stop scanning
          break;
        } else {
          // Not found: shift runs by two (so pattern will continue)
          res.shift(runs, 2);
          pos = res.length - 2;
          runs[pos]++;
        }
      }
    },
  };
  return res;
}
// dark/light/dark/light/dark in 1:1:3:1:1 ratio
const FINDER = /* @__PURE__ */ pattern([true, false, true, false, true], [1, 1, 3, 1, 1]);
// central light/dark/light runs of an alignment pattern in 1:1:1 ratio
const ALIGNMENT = /* @__PURE__ */ pattern([false, true, false]);

function findFinder(b: TArg<Bitmap>): {
  bl: Pattern;
  tl: Pattern;
  tr: Pattern;
} {
  const bm = b as Bitmap;
  let found: Pattern[] = [];
  function checkRuns(runs: Runs, v = 2) {
    const total = sum(runs);
    if (total < FINDER.totalSize) return false;
    const moduleSize = total / FINDER.totalSize;
    return FINDER.checkSize(runs, moduleSize, v);
  }
  // Non-diagonal line (horizontal or vertical)
  function checkLine(center: Point, maxCount: number, total: number, incr: Point) {
    const runs = FINDER.runs();
    let i = FINDER.check(bm, runs, center, incr, maxCount);
    if (i === false) return false;
    const runsTotal = sum(runs);
    if (5 * Math.abs(runsTotal - total) >= 2 * total) return false;
    if (checkRuns(runs)) return FINDER.toCenter(runs, i);
    return false;
  }

  function check(runs: Runs, i: number, j: number) {
    if (!checkRuns(runs)) return false;
    const total = sum(runs);
    let x = FINDER.toCenter(runs, j);
    // Vertical
    let y = checkLine({ x: int(x), y: i }, runs[2], total, { y: 1, x: 0 });
    if (y === false) return false;
    y += i;
    // Horizontal
    let xx = checkLine({ x: int(x), y: int(y) }, runs[2], total, { y: 0, x: 1 });
    if (xx === false) return false;
    x = xx + int(x);
    // Diagonal
    const dRuns = FINDER.runs();
    if (!FINDER.check(bm, dRuns, { x: int(x), y: int(y) }, { x: 1, y: 1 })) return false;
    if (!checkRuns(dRuns, PATTERN_VARIANCE_DIAGONAL)) return false;
    FINDER.add(found, x, y, total);
    return true;
  }
  let skipped = false;
  // Start with high skip lines count until we find first pattern
  let ySkip = cap(int((3 * bm.height) / (4 * 97)), DETECT_MIN_ROW_SKIP);
  let done = false;
  for (let y = ySkip - 1; y < bm.height && !done; y += ySkip) {
    FINDER.scanLine(bm, y, 0, bm.width, (runs, x) => {
      if (!check(runs, y, x)) return;
      // Found pattern
      // Reduce row skip, since we found pattern and qr code is nearby
      ySkip = 2;
      if (skipped) {
        // Already skipped, so we have at least 2 patterns, lets check if third is ok
        let count = 0;
        let total = 0;
        for (const p of found) {
          if (p.count < PATTERN_MIN_CONFIRMATIONS) continue;
          count++;
          total += p.moduleSize;
        }
        if (count < 3) return;
        const average = total / found.length;
        let deviation = 0.0;
        for (const p of found) deviation += Math.abs(p.moduleSize - average);
        if (deviation <= 0.05 * total) {
          done = true;
          return false;
        }
      } else if (found.length > 1) {
        // We found two top patterns, lets skip to approximate location of third pattern
        const q = patternsConfirmed(found);
        if (q.length < 2) return true;
        skipped = true;
        const d = int((Math.abs(q[0].x - q[1].x) - Math.abs(q[0].y - q[1].y)) / 2);
        if (d <= runs[2] + ySkip) return true;
        y += d - runs[2] - ySkip;
        return false;
      }
      return;
    });
  }
  const flen = found.length;
  if (flen < 3) throw new Error(`Finder: len(found) = ${flen}`);
  found.sort((i, j) => i.moduleSize - j.moduleSize);
  const pBest = utils.best<[Pattern, Pattern, Pattern]>();
  // Qubic complexity, but we stop search when we found 3 patterns, so not a problem
  for (let i = 0; i < flen - 2; i++) {
    const fi = found[i];
    for (let j = i + 1; j < flen - 1; j++) {
      const fj = found[j];
      const square0 = distance2(fi, fj);
      for (let k = j + 1; k < flen; k++) {
        const fk = found[k];
        if (fk.moduleSize > fi.moduleSize * 1.4) continue;
        const arr = [square0, distance2(fj, fk), distance2(fi, fk)].sort((a, b) => a - b);
        const a = arr[0];
        const b = arr[1];
        const c = arr[2];
        pBest.add(Math.abs(c - 2 * b) + Math.abs(c - 2 * a), [fi, fj, fk]);
      }
    }
  }
  const p = pBest.get();
  if (!p) throw new Error('cannot find finder');
  const p0 = p[0];
  const p1 = p[1];
  const p2 = p[2];
  const d01 = distance(p0, p1);
  const d12 = distance(p1, p2);
  const d02 = distance(p0, p2);
  let tl = p2;
  let bl = p0;
  let tr = p1;
  if (d12 >= d01 && d12 >= d02) {
    tl = p0;
    bl = p1;
    tr = p2;
  } else if (d02 >= d12 && d02 >= d01) {
    tl = p1;
    bl = p0;
    tr = p2;
  }
  // If cross product is negative -> flip points
  if ((tr.x - tl.x) * (bl.y - tl.y) - (tr.y - tl.y) * (bl.x - tl.x) < 0.0) {
    let _bl = bl;
    bl = tr;
    tr = _bl;
  }
  return { bl, tl, tr };
}

function findAlignment(b: TArg<Bitmap>, est: Pattern, allowanceFactor: number): Pattern {
  const bm = b as Bitmap;
  const { moduleSize } = est;
  const allowance = int(allowanceFactor * moduleSize);
  const leftX = cap(est.x - allowance, 0);
  const rightX = cap(est.x + allowance, undefined, bm.width - 1);
  const x = rightX - leftX;
  const topY = cap(est.y - allowance, 0);
  const bottomY = cap(est.y + allowance, undefined, bm.height - 1);
  const y = bottomY - topY;
  if (x < moduleSize * 3 || y < moduleSize * 3)
    throw new Error(`x = ${x}, y=${y} moduleSize = ${moduleSize}`);
  const xStart = leftX;
  const yStart = topY;
  // ISO/IEC 18004:2024 §12 h)3 scans the alignment pattern's white-square
  // outline from the provisional centre. `rightX` / `bottomY` are inclusive
  // clipped image coordinates; convert them to exclusive scan bounds below so
  // an exact 5x5 search window still includes its final row and column.
  const width = rightX - leftX + 1;
  const height = bottomY - topY + 1;
  const found: Pattern[] = [];
  const xEnd = xStart + width;
  const middleY = int(yStart + height / 2);
  for (let yGen = 0; yGen < height; yGen++) {
    const diff = int((yGen + 1) / 2);
    const y = middleY + (yGen & 1 ? -diff : diff);
    let res;
    ALIGNMENT.scanLine(bm, y, xStart, xEnd, (runs, x) => {
      if (!ALIGNMENT.checkSize(runs, moduleSize)) return;
      const total = sum(runs);
      const xx = ALIGNMENT.toCenter(runs, x);
      // Vertical
      const rVert = ALIGNMENT.runs();
      let v = ALIGNMENT.check(bm, rVert, { x: int(xx), y }, { y: 1, x: 0 }, 2 * runs[1]);
      if (v === false) return;
      v += y;
      const vTotal = sum(rVert);
      if (5 * Math.abs(vTotal - total) >= 2 * total) return;
      if (!ALIGNMENT.checkSize(rVert, moduleSize)) return;
      const yy = ALIGNMENT.toCenter(rVert, v);
      res = ALIGNMENT.add(found, xx, yy, total);
      if (res) return false;
      return;
    });
    if (res) return res;
  }
  if (found.length > 0) return found[0];
  throw new Error('Alignment pattern not found');
}

function _single(b: TArg<Bitmap>, from: Point, to: Point) {
  const bm = b as Bitmap;
  // http://en.wikipedia.org/wiki/Bresenham's_line_algorithm
  let steep = false;
  let d = { x: Math.abs(to.x - from.x), y: Math.abs(to.y - from.y) };
  if (d.y > d.x) {
    steep = true;
    from = pointMirror(from);
    to = pointMirror(to);
    d = pointMirror(d);
  }
  let error = -d.x / 2;
  let step = { x: from.x >= to.x ? -1 : 1, y: from.y >= to.y ? -1 : 1 };
  let runPos = 0;
  let xLimit = to.x + step.x;
  // TODO: re-use pattern scanLine here?
  for (let x = from.x, y = from.y; x !== xLimit; x += step.x) {
    let real = { x, y };
    if (steep) real = pointMirror(real);
    // Starting from a dark finder center, walk until the ray crosses
    // light -> dark -> light; `BWBRunLength()` mirrors this to recover the
    // full finder width around the center point.
    if ((runPos === 1) === !!bm.point(real)) {
      if (runPos === 2) return distance({ x, y }, from);
      runPos++;
    }
    error += d.y;
    if (error <= 0) continue;
    if (y === to.y) break;
    y += step.y;
    error -= d.x;
  }
  if (runPos === 2) return distance({ x: to.x + step.x, y: to.y }, from);
  return NaN;
}

function BWBRunLength(b: TArg<Bitmap>, from: Point, to: Point) {
  const bm = b as Bitmap;
  let result = _single(bm, from, to);
  let scaleY = 1.0;
  const { x: fx, y: fy } = from;
  let otherToX = fx - (to.x - fx);
  const bw = bm.width;
  if (otherToX < 0) {
    scaleY = fx / (fx - otherToX);
    otherToX = 0;
  } else if (otherToX >= bw) {
    scaleY = (bw - 1 - fx) / (otherToX - fx);
    otherToX = bw - 1;
  }
  // ISO/IEC 18004:2024 §12 b) uses finder runs in the 1:1:3:1:1 ratio,
  // and §12 h)1 derives module size from finder pattern width. Clipping the
  // reflected ray before `int()` would avoid `>>> 0` wrapping negative near-edge
  // coordinates to a huge uint32 and clamping to the wrong edge. Policy: keep
  // the existing heuristic because the direct fix degraded decode performance
  // on current vectors (BoofCV sweep 134/485 -> 132/485).
  let otherToY = int(fy - (to.y - fy) * scaleY);
  let scaleX = 1.0;
  const bh = bm.height;
  if (otherToY < 0) {
    scaleX = fy / (fy - otherToY);
    otherToY = 0;
  } else if (otherToY >= bh) {
    scaleX = (bh - 1 - fy) / (otherToY - fy);
    otherToY = bh - 1;
  }
  otherToX = int(fx + (otherToX - fx) * scaleX);
  result += _single(bm, from, { x: otherToX, y: otherToY });
  // Both mirrored rays include the center module once, so drop one module
  // after summing them into the full finder-width estimate.
  return result - 1.0;
}

function moduleSizeAvg(b: TArg<Bitmap>, p1: Point, p2: Point) {
  const est1 = BWBRunLength(b, pointInt(p1), pointInt(p2));
  const est2 = BWBRunLength(b, pointInt(p2), pointInt(p1));
  // One ray can fail near image edges, so keep the surviving estimate
  // instead of discarding the finder-width measurement outright.
  if (Number.isNaN(est1)) return est2 / FINDER.totalSize;
  if (Number.isNaN(est2)) return est1 / FINDER.totalSize;
  return (est1 + est2) / (2 * FINDER.totalSize);
}

function detect(b: TArg<Bitmap>): TRet<{
  bits: Bitmap;
  points: FinderPoints;
}> {
  const bm = b as Bitmap;
  let bl, tl, tr;
  try {
    ({ bl, tl, tr } = findFinder(bm));
  } catch (e) {
    try {
      // ISO/IEC 18004:2024 §12 b)5 says to "reverse the colouring of the
      // light and dark pixels" for reflectance reversal. `detect()` works on
      // the `decodeQR()`-owned scratch bitmap, so keep the retry in-place for
      // performance instead of cloning before this private/test-only helper.
      bm.negate();
      ({ bl, tl, tr } = findFinder(bm));
    } catch (e) {
      bm.negate(); // undo negate
      throw e;
    }
  }
  const moduleSize = (moduleSizeAvg(bm, tl, tr) + moduleSizeAvg(bm, tl, bl)) / 2;
  if (moduleSize < 1.0) throw new Error(`invalid moduleSize = ${moduleSize}`);
  // Estimate size
  const tltr = int(distance(tl, tr) / moduleSize + 0.5);
  const tlbl = int(distance(tl, bl) / moduleSize + 0.5);
  let size = int((tltr + tlbl) / 2 + 7);
  // QR side lengths are 21 + 4 * (version - 1), so normalize the estimate
  // to the nearest size that is 1 modulo 4 before decoding the version.
  const rem = size % 4;
  if (rem === 0)
    size++; // -> 1
  else if (rem === 2)
    size--; // -> 1
  else if (rem === 3) size -= 2;
  const version = utils.info.size.decode(size);
  utils.validateVersion(version);
  let alignmentPattern;
  if (utils.info.alignmentPatterns(version).length > 0) {
    // Bottom right estimate
    const br = { x: tr.x - tl.x + bl.x, y: tr.y - tl.y + bl.y };
    const c = 1.0 - 3.0 / (utils.info.size.encode(version) - 7);
    // Estimated alignment pattern position
    const est = {
      x: int(tl.x + c * (br.x - tl.x)),
      y: int(tl.y + c * (br.y - tl.y)),
      moduleSize,
      count: 1,
    };
    for (let i = 4; i <= 16; i <<= 1) {
      try {
        alignmentPattern = findAlignment(bm, est, i);
        break;
      } catch (e) {}
    }
  }
  const toTL = { x: 3.5, y: 3.5 };
  const toTR = { x: size - 3.5, y: 3.5 };
  const toBL = { x: 3.5, y: size - 3.5 };
  let br: Point;
  let toBR;
  if (alignmentPattern) {
    br = alignmentPattern;
    toBR = { x: size - 6.5, y: size - 6.5 };
  } else {
    br = { x: tr.x - tl.x + bl.x, y: tr.y - tl.y + bl.y };
    toBR = { x: size - 3.5, y: size - 3.5 };
  }
  const from: FinderPoints = [tl, tr, br, bl];
  const bits = transform(bm, size, from, [toTL, toTR, toBR, toBL]);
  return { bits: bits as Bitmap, points: from } as TRet<{ bits: Bitmap; points: FinderPoints }>;
}

// Perspective transform by 4 points
function squareToQuadrilateral(p: Point4) {
  const d3 = { x: p[0].x - p[1].x + p[2].x - p[3].x, y: p[0].y - p[1].y + p[2].y - p[3].y };
  if (d3.x === 0.0 && d3.y === 0.0) {
    // Parallelogram fast path: perspective terms vanish, so the homography
    // reduces to an affine transform.
    return [
      [p[1].x - p[0].x, p[2].x - p[1].x, p[0].x],
      [p[1].y - p[0].y, p[2].y - p[1].y, p[0].y],
      [0.0, 0.0, 1.0],
    ];
  } else {
    const d1 = { x: p[1].x - p[2].x, y: p[1].y - p[2].y };
    const d2 = { x: p[3].x - p[2].x, y: p[3].y - p[2].y };
    const den = d1.x * d2.y - d2.x * d1.y;
    const p13 = (d3.x * d2.y - d2.x * d3.y) / den;
    const p23 = (d1.x * d3.y - d3.x * d1.y) / den;
    return [
      [p[1].x - p[0].x + p13 * p[1].x, p[3].x - p[0].x + p23 * p[3].x, p[0].x],
      [p[1].y - p[0].y + p13 * p[1].y, p[3].y - p[0].y + p23 * p[3].y, p[0].y],
      [p13, p23, 1.0],
    ];
  }
}

// Transform quadrilateral to square by 4 points
function transform(b: TArg<Bitmap>, size: number, from: Point4, to: Point4): TRet<Bitmap> {
  const bm = b as Bitmap;
  // TODO: check
  // https://math.stackexchange.com/questions/13404/mapping-irregular-quadrilateral-to-a-rectangle
  const p = squareToQuadrilateral(to);
  // Homographies are scale-invariant, so the adjugate is enough here;
  // there is no need to divide by the determinant when inverting `p`.
  const qToS = [
    [
      p[1][1] * p[2][2] - p[2][1] * p[1][2],
      p[2][1] * p[0][2] - p[0][1] * p[2][2],
      p[0][1] * p[1][2] - p[1][1] * p[0][2],
    ],
    [
      p[2][0] * p[1][2] - p[1][0] * p[2][2],
      p[0][0] * p[2][2] - p[2][0] * p[0][2],
      p[1][0] * p[0][2] - p[0][0] * p[1][2],
    ],
    [
      p[1][0] * p[2][1] - p[2][0] * p[1][1],
      p[2][0] * p[0][1] - p[0][0] * p[2][1],
      p[0][0] * p[1][1] - p[1][0] * p[0][1],
    ],
  ];
  const sToQ = squareToQuadrilateral(from);
  const transform = sToQ.map((i) =>
    i.map((_, qx) => i.reduce((acc, v, j) => acc + v * qToS[j][qx], 0))
  );

  const res = new Bitmap(size);
  const points = utils.fillArr(2 * size, 0);
  const pointsLength = points.length;
  for (let y = 0; y < size; y++) {
    const p = transform;
    for (let i = 0; i < pointsLength - 1; i += 2) {
      const x = i / 2 + 0.5;
      const y2 = y + 0.5;
      const den = p[2][0] * x + p[2][1] * y2 + p[2][2];
      // ISO/IEC 18004:2024 §12 h) maps sampling grid intersections back to
      // image coordinates before deciding dark/light state. Clip projected
      // coordinates before `int()` because `>>> 0` wraps negative samples to a
      // huge uint32 and would clamp them to the far image edge.
      points[i] = int(cap((p[0][0] * x + p[0][1] * y2 + p[0][2]) / den, 0, bm.width - 1));
      points[i + 1] = int(cap((p[1][0] * x + p[1][1] * y2 + p[1][2]) / den, 0, bm.height - 1));
    }
    for (let i = 0; i < pointsLength; i += 2) {
      if (bm.get(points[i], points[i + 1])) res.set((i / 2) | 0, y, true);
    }
  }
  return res as TRet<Bitmap>;
}

// Same as in drawTemplate, but reading
// TODO: merge in CoderType?
function readInfoBits(b: TArg<Bitmap>) {
  const bm = b as Bitmap;
  // Walk each reserved copy from the highest-numbered module back to module 0
  // so the shift accumulator rebuilds the canonical bit string from MSB to LSB.
  const readBit = (x: number, y: number, out: number) => (out << 1) | (bm.get(x, y) ? 1 : 0);
  const size = bm.height;
  // Version information
  let version1 = 0;
  for (let y = 5; y >= 0; y--)
    for (let x = size - 9; x >= size - 11; x--) version1 = readBit(x, y, version1);
  let version2 = 0;
  for (let x = 5; x >= 0; x--)
    for (let y = size - 9; y >= size - 11; y--) version2 = readBit(x, y, version2);
  // Format information
  let format1 = 0;
  for (let x = 0; x < 6; x++) format1 = readBit(x, 8, format1);
  format1 = readBit(7, 8, format1);
  format1 = readBit(8, 8, format1);
  format1 = readBit(8, 7, format1);
  for (let y = 5; y >= 0; y--) format1 = readBit(8, y, format1);
  let format2 = 0;
  for (let y = size - 1; y >= size - 7; y--) format2 = readBit(8, y, format2);
  for (let x = size - 8; x < size; x++) format2 = readBit(x, 8, format2);
  return { version1, version2, format1, format2 };
}

function parseInfo(b: TArg<Bitmap>) {
  const bm = b as Bitmap;
  // Population count over xor -> hamming distance
  const size = bm.height;
  const { version1, version2, format1, format2 } = readInfoBits(bm);
  // Guess format
  let format;
  const bestFormat = utils.best<{ ecc: ErrorCorrection; mask: Mask }>();
  for (const ecc of ['medium', 'low', 'high', 'quartile'] as const) {
    for (let mask: Mask = 0; mask < 8; mask++) {
      const bits = utils.info.formatBits(ecc, mask as Mask);
      const cur = { ecc, mask: mask as Mask };
      if (bits === format1 || bits === format2) {
        format = cur;
        break;
      }
      bestFormat.add(utils.popcnt(format1 ^ bits), cur);
      if (format1 !== format2) bestFormat.add(utils.popcnt(format2 ^ bits), cur);
    }
  }
  if (format === undefined && bestFormat.score() <= MAX_BITS_ERROR) format = bestFormat.get();
  if (format === undefined) throw new Error('invalid format pattern');
  let version: number | undefined = utils.info.size.decode(size); // Guess version based on bitmap size
  // Versions 1-6 do not carry version-information words, so side length is
  // the only authoritative version source until version 7 adds those fields.
  if (version < 7) utils.validateVersion(version);
  else {
    version = undefined;
    // Guess version
    const bestVer = utils.best<number>();
    for (let ver = 7; ver <= 40; ver++) {
      const bits = utils.info.versionBits(ver);
      if (bits === version1 || bits === version2) {
        version = ver;
        break;
      }
      bestVer.add(utils.popcnt(version1 ^ bits), ver);
      if (version1 !== version2) bestVer.add(utils.popcnt(version2 ^ bits), ver);
    }
    if (version === undefined && bestVer.score() <= MAX_BITS_ERROR) version = bestVer.get();
    if (version === undefined) throw new Error('invalid version pattern');
    if (utils.info.size.encode(version) !== size) throw new Error('invalid version size');
  }
  return { version, ...format };
}

// Global symbols in both browsers and Node.js since v11
// See https://github.com/microsoft/TypeScript/issues/31535
declare const TextDecoder: any;

// ISO/IEC 18004:2024 §7.4.3.2 says each ECI is a "6-digit assignment
// number"; §7.4.3.4 says invoked ECIs apply until "a change of ECI".
// Decode through platform TextDecoder only: unsupported labels may throw on
// some runtimes, and callers needing them can provide a custom textDecoder.
const eciToEncoding: Record<number, string> = {
  1: 'iso-8859-1',
  2: 'ibm437',
  3: 'iso-8859-1',
  4: 'iso-8859-2',
  5: 'iso-8859-3',
  6: 'iso-8859-4',
  7: 'iso-8859-5',
  8: 'iso-8859-6',
  9: 'iso-8859-7',
  10: 'iso-8859-8',
  11: 'iso-8859-9',
  13: 'iso-8859-11',
  15: 'iso-8859-13',
  16: 'iso-8859-14',
  17: 'iso-8859-15',
  18: 'iso-8859-16',
  20: 'shift-jis',
  21: 'windows-1250',
  22: 'windows-1251',
  23: 'windows-1252',
  24: 'windows-1256',
  25: 'utf-16be',
  26: 'utf-8',
  28: 'big5',
  29: 'gbk',
  30: 'euc-kr',
};

function decodeWithEci(bytes: TArg<Uint8Array>, eci: number = 26): string {
  // ISO/IEC 18004:2024 §7.3.2 says QR's "default interpretation" is
  // "ECI 000003 representing the ISO/IEC 8859-1 character set". Keep UTF-8
  // here so this library's UTF-8 byte-mode encoder round-trips without ECI.
  const encoding = eciToEncoding[eci];
  if (!encoding) throw new Error(`Unsupported ECI: ${eci}`);
  return new TextDecoder(encoding).decode(bytes);
}

function decodeBitmap(
  b: TArg<Bitmap>,
  decoder: TArg<(bytes: Uint8Array, eci: number) => string> = decodeWithEci
): string {
  const bm = b as Bitmap;
  const size = bm.height;
  if (size < 21 || (size & 0b11) !== 1 || size !== bm.width)
    throw new Error(`decode: invalid size=${size}`);
  const { version, mask, ecc } = parseInfo(bm);
  const tpl = utils.drawTemplate(version, ecc, mask);
  const { total } = utils.info.capacity(version, ecc);
  const bytes = new Uint8Array(total);
  let pos = 0;
  let buf = 0;
  let bitPos = 0;
  utils.zigzag(tpl, mask, (x, y, m) => {
    bitPos++;
    buf <<= 1;
    buf |= +(!!bm.get(x, y) !== m);
    if (bitPos !== 8) return;
    bytes[pos++] = buf;
    bitPos = 0;
    buf = 0;
  });
  if (pos !== total) throw new Error(`decode: pos=${pos}, total=${total}`);
  let bits = Array.from(utils.interleave(version, ecc).decode(bytes))
    .map((i) => utils.bin(i, 8))
    .join('');
  // Reverse operation of index.ts/encode working on bits
  const readBits = (n: number) => {
    if (n > bits.length) throw new Error('Not enough bits');
    const val = bits.slice(0, n);
    bits = bits.slice(n);
    return val;
  };
  const toNum = (n: string) => Number(`0b${n}`);
  // reverse of common.info.modebits
  const modes: Record<string, EncodingType | 'terminator'> = {
    '0000': 'terminator',
    '0001': 'numeric',
    '0010': 'alphanumeric',
    '0100': 'byte',
    '0111': 'eci',
    '1000': 'kanji',
  };
  let res = '';
  // ISO/IEC 18004:2024 §7.3.2 defines no-ECI byte data as ECI 000003
  // / ISO-8859-1. Keep ECI 26 for compatibility with legacy no-ECI UTF-8
  // payloads and with encodeQR's UTF-8 byte-mode default.
  let eci: number = 26; // Default to utf-8 for compat with old behavior
  while (true) {
    if (bits.length < 4) break;
    const modeBits = readBits(4);
    const mode = modes[modeBits];
    if (mode === undefined) throw new Error(`Unknown modeBits=${modeBits} res="${res}"`);
    if (mode === 'terminator') break;
    const countBits = utils.info.lengthBits(version, mode);
    let count = toNum(readBits(countBits));
    if (mode === 'numeric') {
      while (count >= 3) {
        const v = toNum(readBits(10));
        if (v >= 1000) throw new Error(`numberic(3) = ${v}`);
        res += v.toString().padStart(3, '0');
        count -= 3;
      }
      if (count === 2) {
        const v = toNum(readBits(7));
        if (v >= 100) throw new Error(`numeric(2) = ${v}`);
        res += v.toString().padStart(2, '0');
      } else if (count === 1) {
        const v = toNum(readBits(4));
        if (v >= 10) throw new Error(`Numeric(1) = ${v}`);
        res += v.toString();
      }
    } else if (mode === 'alphanumeric') {
      while (count >= 2) {
        const v = toNum(readBits(11));
        res += utils.info.alphabet.alphanumerc.encode([Math.floor(v / 45), v % 45]).join('');
        count -= 2;
      }
      if (count === 1) res += utils.info.alphabet.alphanumerc.encode([toNum(readBits(6))]).join('');
    } else if (mode === 'eci') {
      const first = toNum(readBits(8));
      if ((first & 0x80) === 0) eci = first;
      else if ((first & 0xc0) === 0x80) eci = ((first & 0x3f) << 8) | toNum(readBits(8));
      else eci = ((first & 0x1f) << 16) | toNum(readBits(16));
      continue; // ECI doesn't carry data, just sets state
    } else if (mode === 'byte') {
      const data = new Uint8Array(count);
      for (let i = 0; i < count; i++) data[i] = toNum(readBits(8));
      res += decoder(data, eci);
    } else if (mode === 'kanji') {
      // ISO/IEC 18004:2024 §7.3.6 says Kanji mode uses Shift JIS and
      // "Each two-byte character value is compacted to a 13-bit binary
      // codeword." Keep it unsupported until a real interop fixture can verify
      // the 13-bit-to-Shift-JIS mapping rather than adding untested decoding.
      throw new Error('Kanji mode is not supported');
    } else throw new Error(`Unknown mode=${mode}`);
  }
  return res;
}

/** QR decoding hooks and image preprocessing options. */
export type DecodeOpts = {
  /** Crop rectangular inputs to a centered square before decoding. */
  cropToSquare?: boolean;
  /**
   * Custom byte-to-text decoder used for byte segments.
   *
   * Receives the byte segment and, when needed, the active ECI designator.
   * ISO/IEC 18004:2024 §7.4.3.4 keeps ECIs active "until the end of
   * the encoded data or a change of ECI", so callers need the active
   * designator to apply their own charset policy.
   * @param bytes - Byte segment payload to decode.
   * @param eci - Active ECI designator for the byte segment.
   * @returns Decoded text for the byte segment.
   */
  textDecoder?: TArg<(bytes: Uint8Array, eci?: number) => string>;
  /**
   * Callback invoked with finder/alignment points after detection succeeds.
   *
   * Receives finder and alignment points returned by the detector.
   * @param points - Finder and alignment points returned by the detector.
   */
  pointsOnDetect?: (points: FinderPoints) => void;
  /**
   * Callback invoked with the grayscale bitmap that the detector sees.
   *
   * Receives the grayscale image generated during bitmap conversion.
   * @param img - Grayscale image generated during bitmap conversion.
   */
  imageOnBitmap?: (img: Image) => void;
  /**
   * Callback invoked with the perspective-corrected QR image.
   *
   * Receives the perspective-corrected QR image.
   * @param img - Perspective-corrected QR image.
   */
  imageOnDetect?: (img: Image) => void;
  /**
   * Callback invoked with the final decoded QR image.
   *
   * Receives the final QR image used to decode the payload.
   * @param img - Final QR image used to decode the payload.
   */
  imageOnResult?: (img: Image) => void;
};

// Center-crop to a square and return the original-image offset so
// `decodeQR()` can map detected points back into caller coordinates.
function cropToSquare(img: TArg<Image>) {
  const image = img as Image;
  const data = Array.isArray(image.data) ? new Uint8Array(image.data) : image.data;
  const { height, width } = image;
  const squareSize = Math.min(height, width);
  const offset = {
    x: Math.floor((width - squareSize) / 2),
    y: Math.floor((height - squareSize) / 2),
  };
  const bytesPerPixel = getBytesPerPixel(img);
  const croppedData = new Uint8Array(squareSize * squareSize * bytesPerPixel);
  for (let y = 0; y < squareSize; y++) {
    const srcPos = ((y + offset.y) * width + offset.x) * bytesPerPixel;
    const dstPos = y * squareSize * bytesPerPixel;
    const length = squareSize * bytesPerPixel;
    croppedData.set(data.subarray(srcPos, srcPos + length), dstPos);
  }
  return { offset, img: { height: squareSize, width: squareSize, data: croppedData } };
}

/**
 * Decode text from a QR image.
 * @param img - RGB or RGBA image data that contains a QR code.
 * @param opts - Decoder hooks and image preprocessing options. See {@link DecodeOpts}.
 * @returns Decoded QR payload as a string.
 * @throws If the image, decoder options, or QR contents are invalid. {@link Error}
 * @example
 * Decode text from a QR image.
 * ```ts
 * import encodeQR, { Bitmap } from 'qr';
 * import decodeQR from 'qr/decode.js';
 * const bits = encodeQR('Hello world', 'raw', { scale: 4 });
 * const bm = new Bitmap({ width: bits[0].length, height: bits.length }, bits);
 * const text = decodeQR(bm.toImage());
 * ```
 */
export function decodeQR(img: TArg<Image>, opts: TArg<DecodeOpts> = {}): string {
  let image = img as Image;
  const options = opts as DecodeOpts;
  for (const field of ['height', 'width'] as const) {
    if (!Number.isSafeInteger(image[field]) || image[field] <= 0)
      throw new Error(`invalid img.${field}=${image[field]} (${typeof image[field]})`);
  }
  const { data } = image;
  if (!Array.isArray(data) && !isBytes(data))
    throw new Error(`invalid image.data=${data} (${typeof data})`);
  if (options.cropToSquare !== undefined && typeof options.cropToSquare !== 'boolean')
    throw new Error(`invalid opts.cropToSquare=${options.cropToSquare}`);
  // Validate callbacks before decoding so payload mode does not decide whether
  // an invalid public option is accepted.
  for (const fn of [
    'textDecoder',
    'pointsOnDetect',
    'imageOnBitmap',
    'imageOnDetect',
    'imageOnResult',
  ] as const) {
    if (options[fn] !== undefined && typeof options[fn] !== 'function')
      throw new Error(`invalid opts.${fn}=${options[fn]} (${typeof options[fn]})`);
  }
  let offset = { x: 0, y: 0 };
  if (options.cropToSquare) ({ img: image, offset } = cropToSquare(image));
  const bmp = toBitmap(image) as Bitmap;
  if (options.imageOnBitmap) options.imageOnBitmap(bmp.toImage());
  const { bits, points } = detect(bmp);
  if (options.pointsOnDetect) {
    // Report finder points in the caller's original coordinate space after any center-crop.
    const p = points.map((i) => ({ ...i, ...pointAdd(i, offset) })) as FinderPoints;
    options.pointsOnDetect(p);
  }
  if (options.imageOnDetect) options.imageOnDetect(bits.toImage());
  const res = decodeBitmap(bits, options.textDecoder);
  if (options.imageOnResult) options.imageOnResult(bits.toImage());
  return res;
}

/**
 * Default export alias for {@link decodeQR}.
 * @param img - RGB or RGBA image data that contains a QR code.
 * @param opts - Decoder hooks and image preprocessing options. See {@link DecodeOpts}.
 * @returns Decoded QR payload as a string.
 * @throws If the image, decoder options, or QR contents are invalid. {@link Error}
 * @example
 * Decode a rendered QR image via the default decoder export.
 * ```ts
 * import encodeQR, { Bitmap } from 'qr';
 * import decodeQR from 'qr/decode.js';
 * const bits = encodeQR('Hello world', 'raw', { scale: 4 });
 * const bm = new Bitmap({ width: bits[0].length, height: bits.length }, bits);
 * decodeQR(bm.toImage());
 * ```
 */
export default decodeQR;

// Additional private helpers for focused regression tests; separate from the
// existing `_tests` object so its current keys remain stable.
export const _TESTS: {
  findAlignment: typeof findAlignment;
  transform: typeof transform;
} = /* @__PURE__ */ Object.freeze({
  findAlignment: findAlignment,
  transform: transform,
});

// Unsafe API utils, exported only for tests
export const _tests: {
  toBitmap: typeof toBitmap;
  decodeBitmap: typeof decodeBitmap;
  findFinder: typeof findFinder;
  detect: typeof detect;
} = /* @__PURE__ */ Object.freeze({
  toBitmap,
  decodeBitmap,
  findFinder,
  detect,
});