<?php
/**
 * SeekQuarry/Yioop --
 * Open Source Pure PHP Search Engine, Crawler, and Indexer
 *
 * Copyright (C) 2009 - 2026  Chris Pollett chris@pollett.org
 *
 * LICENSE:
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see
 * <https://www.gnu.org/licenses/>.
 *
 * END LICENSE
 *
 * @author Chris Pollett chris@pollett.org
 * @license https://www.gnu.org/licenses/ GPL3
 * @link https://www.seekquarry.com/
 * @copyright 2009 - 2026
 * @filesource
 */
namespace seekquarry\yioop\library;

/**
 * Decodes a black-and-white image coded the way a fax machine codes one,
 * giving back one byte per pixel: 0 for black, 1 for white.
 *
 * This coding is defined by ITU-T Recommendations T.4 (Group 3) and T.6
 * (Group 4), written for sending a page over a telephone line. It is met
 * in two places a crawler cares about: a PDF stream whose Filter is
 * CCITTFaxDecode, which is how a magazine cover's lettering is often
 * carried as a stencil, and a TIFF whose Compression tag is 3 or 4.
 *
 * The coding writes each row as the differences from the row above it,
 * since two neighboring rows of a page are usually nearly the same. A row
 * is a list of runs of one color, and each run is written in one of three
 * ways: vertical mode, where the run ends within three pixels of where the
 * one above it ended; pass mode, where the run above ends before this one
 * does; and horizontal mode, where two run lengths are written outright
 * using the code tables T.4 gives for white and black runs.
 *
 * What is handled and what is not:
 * - Two-dimensional coding with no end-of-line markers, which is what
 *   K less than zero means and is what a PDF almost always carries.
 * - The extended run lengths above 1728 pixels, so a wide image decodes.
 * - It does NOT handle: one-dimensional rows (K of zero), mixed coding
 *   (K above zero), byte-aligned rows, or uncompressed mode. A stream
 *   using those returns nothing rather than a wrong picture.
 *
 * Typical use:
 *   $rows = CcittFax::decode($bytes, $width, $height, $black_is_one);
 *   // $rows[$y][$x] is 0 or 1
 * Nothing comes back where the stream cannot be followed, so a caller
 * should check for an empty result rather than assume a picture.
 *
 * @author Chris Pollett
 */
class CcittFax
{
    /**
     * How far to either side of the run above a vertical-mode run may
     * end
     * @var int
     */
    const VERTICAL_REACH = 3;
    /**
     * How many rows may be read before the decoder gives up, so a stream
     * that does not end cannot run forever
     * @var int
     */
    const MOST_ROWS = 20000;
    /**
     * The run lengths white runs are written with, by the code that
     * stands for each. A code is given as its length in bits and its
     * value, since a code of three zero bits is not the same as one.
     * @var array
     */
    public static $white_codes = [
        "00110101" => 0, "000111" => 1, "0111" => 2, "1000" => 3,
        "1011" => 4, "1100" => 5, "1110" => 6, "1111" => 7,
        "10011" => 8, "10100" => 9, "00111" => 10, "01000" => 11,
        "001000" => 12, "000011" => 13, "110100" => 14, "110101" => 15,
        "101010" => 16, "101011" => 17, "0100111" => 18, "0001100" => 19,
        "0001000" => 20, "0010111" => 21, "0000011" => 22, "0000100" => 23,
        "0101000" => 24, "0101011" => 25, "0010011" => 26, "0100100" => 27,
        "0011000" => 28, "00000010" => 29, "00000011" => 30,
        "00011010" => 31, "00011011" => 32, "00010010" => 33,
        "00010011" => 34, "00010100" => 35, "00010101" => 36,
        "00010110" => 37, "00010111" => 38, "00101000" => 39,
        "00101001" => 40, "00101010" => 41, "00101011" => 42,
        "00101100" => 43, "00101101" => 44, "00000100" => 45,
        "00000101" => 46, "00001010" => 47, "00001011" => 48,
        "01010010" => 49, "01010011" => 50, "01010100" => 51,
        "01010101" => 52, "00100100" => 53, "00100101" => 54,
        "01011000" => 55, "01011001" => 56, "01011010" => 57,
        "01011011" => 58, "01001010" => 59, "01001011" => 60,
        "00110010" => 61, "00110011" => 62, "00110100" => 63,
        "11011" => 64, "10010" => 128, "010111" => 192, "0110111" => 256,
        "00110110" => 320, "00110111" => 384, "01100100" => 448,
        "01100101" => 512, "01101000" => 576, "01100111" => 640,
        "011001100" => 704, "011001101" => 768, "011010010" => 832,
        "011010011" => 896, "011010100" => 960, "011010101" => 1024,
        "011010110" => 1088, "011010111" => 1152, "011011000" => 1216,
        "011011001" => 1280, "011011010" => 1344, "011011011" => 1408,
        "010011000" => 1472, "010011001" => 1536, "010011010" => 1600,
        "011000" => 1664, "010011011" => 1728];
    /**
     * The run lengths black runs are written with, by the code that
     * stands for each
     * @var array
     */
    public static $black_codes = [
        "0000110111" => 0, "010" => 1, "11" => 2, "10" => 3, "011" => 4,
        "0011" => 5, "0010" => 6, "00011" => 7, "000101" => 8,
        "000100" => 9, "0000100" => 10, "0000101" => 11, "0000111" => 12,
        "00000100" => 13, "00000111" => 14, "000011000" => 15,
        "0000010111" => 16, "0000011000" => 17, "0000001000" => 18,
        "00001100111" => 19, "00001101000" => 20, "00001101100" => 21,
        "00000110111" => 22, "00000101000" => 23, "00000010111" => 24,
        "00000011000" => 25, "000011001010" => 26, "000011001011" => 27,
        "000011001100" => 28, "000011001101" => 29, "000001101000" => 30,
        "000001101001" => 31, "000001101010" => 32, "000001101011" => 33,
        "000011010010" => 34, "000011010011" => 35, "000011010100" => 36,
        "000011010101" => 37, "000011010110" => 38, "000011010111" => 39,
        "000001101100" => 40, "000001101101" => 41, "000011011010" => 42,
        "000011011011" => 43, "000001010100" => 44, "000001010101" => 45,
        "000001010110" => 46, "000001010111" => 47, "000001100100" => 48,
        "000001100101" => 49, "000001010010" => 50, "000001010011" => 51,
        "000000100100" => 52, "000000110111" => 53, "000000111000" => 54,
        "000000100111" => 55, "000000101000" => 56, "000001011000" => 57,
        "000001011001" => 58, "000000101011" => 59, "000000101100" => 60,
        "000001011010" => 61, "000001100110" => 62, "000001100111" => 63,
        "0000001111" => 64, "000011001000" => 128, "000011001001" => 192,
        "000001011011" => 256, "000000110011" => 320,
        "000000110100" => 384, "000000110101" => 448,
        "0000001101100" => 512, "0000001101101" => 576,
        "0000001001010" => 640, "0000001001011" => 704,
        "0000001001100" => 768, "0000001001101" => 832,
        "0000001110010" => 896, "0000001110011" => 960,
        "0000001110100" => 1024, "0000001110101" => 1088,
        "0000001110110" => 1152, "0000001110111" => 1216,
        "0000001010010" => 1280, "0000001010011" => 1344,
        "0000001010100" => 1408, "0000001010101" => 1472,
        "0000001011010" => 1536, "0000001011011" => 1600,
        "0000001100100" => 1664, "0000001100101" => 1728];
    /**
     * The run lengths both colors share for runs above 1728 pixels
     * @var array
     */
    public static $long_codes = [
        "00000001000" => 1792, "00000001100" => 1856,
        "00000001101" => 1920, "000000010010" => 1984,
        "000000010011" => 2048, "000000010100" => 2112,
        "000000010101" => 2176, "000000010110" => 2240,
        "000000010111" => 2304, "000000011100" => 2368,
        "000000011101" => 2432, "000000011110" => 2496,
        "000000011111" => 2560];
    /**
     * Decodes an image, giving back one byte per pixel.
     *
     * @param string $bytes the coded image
     * @param int $wide how many pixels across each row is
     * @param int $high how many rows there are, or 0 to read until the
     *      stream runs out
     * @param bool $black_is_one whether a one bit means black, which a
     *      PDF says with BlackIs1
     * @return array each row as a list of 0 for black and 1 for white,
     *      empty where the stream cannot be followed
     */
    public static function decode($bytes, $wide, $high,
        $black_is_one = false)
    {
        if ($wide < 1) {
            return [];
        }
        $bits = self::bitsOfBytes($bytes);
        $length = strlen($bits);
        $at = 0;
        /* The row above the first is taken to be all white, which is what
           the coding assumes for the first row of a page. */
        $above = [$wide, $wide];
        $rows = [];
        $most = ($high > 0) ? $high : self::MOST_ROWS;
        while (count($rows) < $most && $at < $length) {
            $changes = self::decodeRow($bits, $at, $wide, $above);
            if ($changes === false) {
                break;
            }
            $rows[] = self::rowPixelsFromChanges($changes, $wide,
                $black_is_one);
            $above = $changes;
        }
        return $rows;
    }
    /**
     * Turns the bytes of a coded image into a string of ones and zeroes,
     * which is how the codes are matched.
     *
     * @param string $bytes the coded image
     * @return string the bits
     */
    public static function bitsOfBytes($bytes)
    {
        $bits = "";
        $length = strlen($bytes);
        for ($at = 0; $at < $length; $at++) {
            $bits .= str_pad(decbin(ord($bytes[$at])), 8, "0",
                STR_PAD_LEFT);
        }
        return $bits;
    }
    /**
     * Decodes one row, giving back the places along it where the color
     * changes. A row is described against the row above it.
     *
     * @param string $bits the whole coded image as bits
     * @param int &$at where in the bits this row begins, moved past it
     * @param int $wide how many pixels across the row is
     * @param array $above where the color changed on the row above
     * @return mixed the places where the color changes, or false where
     *      the row cannot be followed
     */
    public static function decodeRow($bits, &$at, $wide, $above)
    {
        $changes = [];
        $place = 0;
        /* The coding measures from an imaginary white pixel just before
           the row rather than from its first pixel, so a run that ends at
           the very start of the row is still to the right of where the
           reading began. Starting at the first pixel instead skips such a
           change and every run after it lands one boundary out. */
        $behind = -1;
        $white = true;
        $length = strlen($bits);
        while ($place < $wide) {
            if ($at >= $length) {
                return empty($changes) ? false :
                    self::closeRowChanges($changes, $wide);
            }
            $first = self::firstChangeOnReferenceLine($above, $behind,
                $white, $wide);
            $second = self::nextChangeOnReferenceLine($above, $first, $wide);
            $mode = self::readCodingMode($bits, $at);
            if ($mode === false) {
                return empty($changes) ? false :
                    self::closeRowChanges($changes, $wide);
            }
            if ($mode === "pass") {
                $place = $second;
                $behind = $place;
                continue;
            }
            if ($mode === "horizontal") {
                $first_run = self::readRunLength($bits, $at, $white);
                $second_run = self::readRunLength($bits, $at, !$white);
                if ($first_run === false || $second_run === false) {
                    return empty($changes) ? false :
                        self::closeRowChanges($changes, $wide);
                }
                $place = min($wide, $place + $first_run);
                $changes[] = $place;
                $place = min($wide, $place + $second_run);
                $changes[] = $place;
                $behind = $place;
                continue;
            }
            /* Vertical mode: the run ends within three pixels of where
               the run above it ended, and the color turns over. */
            $place = max(0, min($wide, $first + $mode));
            $changes[] = $place;
            $behind = $place;
            $white = !$white;
        }
        return self::closeRowChanges($changes, $wide);
    }
    /**
     * Rounds off a row's changes so every row ends at its full width,
     * which the next row is described against.
     *
     * @param array $changes where the color changed
     * @param int $wide how many pixels across the row is
     * @return array the changes, ending at the row's width
     */
    public static function closeRowChanges($changes, $wide)
    {
        $changes[] = $wide;
        $changes[] = $wide;
        return $changes;
    }
    /**
     * Reads which of the three ways the next run is written.
     *
     * @param string $bits the coded image as bits
     * @param int &$at where to read from, moved past what was read
     * @return mixed "pass", "horizontal", a number from minus three to
     *      three for vertical mode, or false where the bits say none of
     *      them
     */
    public static function readCodingMode($bits, &$at)
    {
        $modes = ["1" => 0, "011" => 1, "010" => -1, "001" => "horizontal",
            "0001" => "pass", "000011" => 2, "000010" => -2,
            "0000011" => 3, "0000010" => -3];
        foreach ([1, 3, 4, 6, 7] as $wide) {
            $said = substr($bits, $at, $wide);
            if (strlen($said) < $wide) {
                return false;
            }
            if (isset($modes[$said])) {
                $at += $wide;
                return $modes[$said];
            }
        }
        return false;
    }
    /**
     * Reads one run length, which may be written as a long run followed
     * by a short one.
     *
     * @param string $bits the coded image as bits
     * @param int &$at where to read from, moved past what was read
     * @param bool $white whether this is a run of white
     * @return mixed how many pixels the run covers, or false where the
     *      bits say no run
     */
    public static function readRunLength($bits, &$at, $white)
    {
        $total = 0;
        $steps = 0;
        while ($steps < 64) {
            $steps++;
            $codes = $white ? self::$white_codes : self::$black_codes;
            $run = self::readOneRunCode($bits, $at, $codes);
            if ($run === false) {
                return false;
            }
            $total += $run;
            /* A run of 64 or more is written as a multiple of 64 and then
               the rest, so reading goes on until a short run ends it. */
            if ($run < 64) {
                return $total;
            }
        }
        return $total;
    }
    /**
     * Reads one code, whether from a color's own table or from the table
     * both colors share for long runs.
     *
     * @param string $bits the coded image as bits
     * @param int &$at where to read from, moved past what was read
     * @param array $codes the color's own table
     * @return mixed how many pixels the code stands for, or false
     */
    public static function readOneRunCode($bits, &$at, $codes)
    {
        for ($wide = 2; $wide <= 14; $wide++) {
            $said = substr($bits, $at, $wide);
            if (strlen($said) < $wide) {
                return false;
            }
            if (isset($codes[$said])) {
                $at += $wide;
                return $codes[$said];
            }
            if (isset(self::$long_codes[$said])) {
                $at += $wide;
                return self::$long_codes[$said];
            }
        }
        return false;
    }
    /**
     * Gives where the row above next changes to the color opposite the
     * one being written, which vertical and pass mode are measured from.
     *
     * @param array $above where the color changed on the row above
     * @param int $behind where the run being written began, which is
     *      minus one at the start of a row
     * @param bool $white whether the run being written is white
     * @param int $wide how many pixels across the row is
     * @return int where the row above changes
     */
    public static function firstChangeOnReferenceLine($above, $behind,
        $white, $wide)
    {
        $count = count($above);
        for ($step = 0; $step < $count; $step++) {
            /* The changes above alternate in color, the first of them a
               change to black, so which of them can end this run depends
               on the color being written. */
            $to_black = (($step % 2) == 0);
            if ($above[$step] > $behind && $to_black == $white) {
                return $above[$step];
            }
        }
        return $wide;
    }
    /**
     * Gives the change on the row above that follows a given one, which
     * pass mode moves to.
     *
     * @param array $above where the color changed on the row above
     * @param int $first the change already found
     * @param int $wide how many pixels across the row is
     * @return int the change after it
     */
    public static function nextChangeOnReferenceLine($above, $first, $wide)
    {
        foreach ($above as $change) {
            if ($change > $first) {
                return $change;
            }
        }
        return $wide;
    }
    /**
     * Turns a row's changes into one byte per pixel.
     *
     * @param array $changes where the color changed along the row
     * @param int $wide how many pixels across the row is
     * @param bool $black_is_one whether a one bit means black
     * @return array the row, 0 for black and 1 for white
     */
    public static function rowPixelsFromChanges($changes, $wide, $black_is_one)
    {
        $row = array_fill(0, $wide, $black_is_one ? 0 : 1);
        $white = true;
        $place = 0;
        foreach ($changes as $change) {
            $change = max(0, min($wide, $change));
            if (!$white) {
                for ($step = $place; $step < $change; $step++) {
                    $row[$step] = $black_is_one ? 1 : 0;
                }
            }
            $place = $change;
            $white = !$white;
            if ($place >= $wide) {
                break;
            }
        }
        return $row;
    }
}
