<?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;
}
}
(c) 2026 Seekquarry - Open Source Search Engine Software