<?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\tests;
use seekquarry\yioop\library\CcittFax;
use seekquarry\yioop\library\UnitTest;
/**
* Checks that an image coded the way a fax machine codes one comes back
* as the picture it started as.
*
* The coding writes each row as the differences from the row above it, so
* one row read wrongly makes every row after it wrong. A decoder can
* therefore look right on the first few rows of a picture and drift into
* nonsense further down, which is what happened here: a magazine's
* lettering read correctly at the top and filled in solid halfway down.
* These cases code small pictures by hand, decode them, and compare row
* by row, so a drift shows up as a mismatched row rather than having to
* be spotted by eye in a thumbnail.
*
* @author Chris Pollett
*/
class CcittFaxTest extends UnitTest
{
/**
* Sets up nothing; each case builds the little picture it needs.
*/
public function setUp()
{
}
/**
* Tears down nothing; no case leaves anything behind.
*/
public function tearDown()
{
}
/**
* Codes a picture the way a fax machine codes one, so a decoding can
* be checked against the picture it began as. Each row is written as
* the differences from the row above, using vertical mode where a run
* ends near where the run above it ended and horizontal mode
* otherwise.
*
* @param array $rows the picture, each row a list of 0 for black and
* 1 for white
* @return string the coded picture's bytes
*/
public function codeRows($rows)
{
$bits = "";
$wide = empty($rows) ? 0 : count($rows[0]);
$above = $this->changesIn(array_fill(0, $wide, 1));
foreach ($rows as $row) {
$bits .= $this->codeRow($this->changesIn($row), $above, $wide);
$above = $this->changesIn($row);
}
$bits .= str_repeat("0", (8 - (strlen($bits) % 8)) % 8);
$bytes = "";
for ($at = 0; $at < strlen($bits); $at += 8) {
$bytes .= chr(bindec(substr($bits, $at, 8)));
}
return $bytes;
}
/**
* Gives the places along a row where its color changes, which is how
* the coding describes a row.
*
* @param array $row the row, 0 for black and 1 for white
* @return array where the color changes, ending at the row's width
*/
public function changesIn($row)
{
$changes = [];
$wide = count($row);
$white = true;
for ($at = 0; $at < $wide; $at++) {
$is_white = ($row[$at] == 1);
if ($is_white != $white) {
$changes[] = $at;
$white = $is_white;
}
}
$changes[] = $wide;
$changes[] = $wide;
return $changes;
}
/**
* Codes one row against the row above it, writing each run in
* vertical mode where it can and horizontal mode where it cannot.
*
* @param array $changes where this row's color changes
* @param array $above where the row above changes
* @param int $wide how many pixels across the row is
* @return string the row's bits
*/
public function codeRow($changes, $above, $wide)
{
$bits = "";
$place = 0;
/* The coding measures from an imaginary white pixel just before
the row, so a run ending at the very first pixel is still to
the right of where the reading began. */
$behind = -1;
$white = true;
$step = 0;
while ($place < $wide) {
$ends = $changes[$step] ?? $wide;
$first = $this->firstChangeAbove($above, $behind, $white,
$wide);
$offset = $ends - $first;
if ($offset >= -3 && $offset <= 3) {
$bits .= $this->verticalBits($offset);
$place = $ends;
$behind = $place;
$white = !$white;
$step++;
continue;
}
/* Horizontal mode writes this run and the one after it
outright, so two runs are consumed at once. */
$next = $changes[$step + 1] ?? $wide;
$bits .= "001" . $this->runBits($ends - $place, $white) .
$this->runBits($next - $ends, !$white);
$place = $next;
$behind = $place;
$step += 2;
}
return $bits;
}
/**
* Gives where the row above next changes, worked out here rather than
* asked of the decoder, so that a wrong idea of it cannot be shared
* between the coding and the decoding and pass unnoticed.
*
* The rule is the one the coding is defined by: the first place the
* row above changes that lies past where this row has got to, and
* that changes to the color opposite the one being written. The row
* above is described as a list of places where it changes, the first
* of them a change from white to black.
*
* @param array $above where the row above changes
* @param int $behind where the run being written began, 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 function firstChangeAbove($above, $behind, $white, $wide)
{
foreach ($above as $step => $change) {
$to_black = (($step % 2) == 0);
if ($change > $behind && $to_black == $white) {
return $change;
}
}
return $wide;
}
/**
* Gives the bits that say a run ends a given distance from where the
* run above it ended.
*
* @param int $offset how far, from minus three to three
* @return string the bits
*/
public function verticalBits($offset)
{
$said = ["0" => "1", "1" => "011", "-1" => "010", "2" => "000011",
"-2" => "000010", "3" => "0000011", "-3" => "0000010"];
return $said[(string)$offset];
}
/**
* Gives the bits that write a run length outright, in the color's own
* table.
*
* @param int $length how many pixels the run covers
* @param bool $white whether the run is white
* @return string the bits
*/
public function runBits($length, $white)
{
$codes = $white ? CcittFax::$white_codes : CcittFax::$black_codes;
$bits = "";
while ($length >= 64) {
$most = 64 * (int)floor($length / 64);
$found = "";
foreach ($codes as $said => $covers) {
if ($covers == $most) {
$found = $said;
break;
}
}
if ($found === "") {
$most = 64;
$found = array_search(64, $codes);
}
$bits .= $found;
$length -= $most;
}
return $bits . array_search($length, $codes);
}
/**
* A picture of plain stripes comes back as the stripes it began as,
* which is the simplest thing the coding has to get right.
*/
public function stripesComeBackTestCase()
{
$rows = [];
for ($down = 0; $down < 8; $down++) {
$row = [];
for ($across = 0; $across < 16; $across++) {
$row[] = ($across >= 4 && $across < 12) ? 0 : 1;
}
$rows[] = $row;
}
$read = CcittFax::decode($this->codeRows($rows), 16, 8);
$this->assertEqual(8, count($read), "every row comes back");
for ($down = 0; $down < 8; $down++) {
$this->assertEqual(implode("", $rows[$down]),
implode("", $read[$down] ?? []),
"row " . $down . " is the row it began as");
}
}
/**
* A picture whose rows differ from one another comes back unchanged.
* A decoder that loses the row above it reads correctly at the top
* and drifts lower down, so every row is compared rather than the
* first few.
*/
public function changingRowsComeBackTestCase()
{
$rows = [];
for ($down = 0; $down < 24; $down++) {
$row = [];
$begins = $down % 10;
for ($across = 0; $across < 32; $across++) {
$row[] = ($across >= $begins && $across < $begins + 7) ?
0 : 1;
}
$rows[] = $row;
}
$read = CcittFax::decode($this->codeRows($rows), 32, 24);
$this->assertEqual(24, count($read), "every row comes back");
$wrong = 0;
foreach ($rows as $down => $row) {
if (implode("", $row) !== implode("", $read[$down] ?? [])) {
$wrong++;
}
}
$this->assertEqual(0, $wrong, "no row drifts from what it was");
}
/**
* A row that is wholly one color comes back that color, which the
* coding writes as a single run and a decoder can easily turn over.
*/
public function wholeRowsComeBackTestCase()
{
$rows = [array_fill(0, 20, 1), array_fill(0, 20, 0),
array_fill(0, 20, 1)];
$read = CcittFax::decode($this->codeRows($rows), 20, 3);
$this->assertEqual(3, count($read), "every row comes back");
foreach ($rows as $down => $row) {
$this->assertEqual(implode("", $row),
implode("", $read[$down] ?? []),
"row " . $down . " is the row it began as");
}
}
/**
* A picture of several separate marks on a row comes back with all
* of them, since a row of lettering is many small runs rather than
* one.
*/
public function severalMarksOnARowComeBackTestCase()
{
$rows = [];
for ($down = 0; $down < 12; $down++) {
$row = array_fill(0, 40, 1);
foreach ([3, 11, 19, 27, 35] as $at) {
$row[$at + ($down % 2)] = 0;
$row[$at + ($down % 2) + 1] = 0;
}
$rows[] = $row;
}
$read = CcittFax::decode($this->codeRows($rows), 40, 12);
$wrong = 0;
foreach ($rows as $down => $row) {
if (implode("", $row) !== implode("", $read[$down] ?? [])) {
$wrong++;
}
}
$this->assertEqual(0, $wrong, "no row drifts from what it was");
}
/**
* A mark that vanishes from one row to the next comes back. Where a
* run on the row above ends before the run being written does, the
* coding uses pass mode, and a decoder that mishandles it loses its
* place and every row after that is wrong.
*/
public function vanishingMarksComeBackTestCase()
{
$rows = [];
/* Two marks, then one wide mark covering both, then none: the
middle row passes over the pair above it. */
$shapes = [[[4, 8], [14, 18]], [[2, 22]], [], [[10, 12]], []];
for ($step = 0; $step < 5; $step++) {
for ($again = 0; $again < 3; $again++) {
$row = array_fill(0, 30, 1);
foreach ($shapes[$step] as $mark) {
for ($at = $mark[0]; $at < $mark[1]; $at++) {
$row[$at] = 0;
}
}
$rows[] = $row;
}
}
$read = CcittFax::decode($this->codeRows($rows), 30, count($rows));
$wrong = 0;
foreach ($rows as $down => $row) {
if (implode("", $row) !== implode("", $read[$down] ?? [])) {
$wrong++;
}
}
$this->assertEqual(0, $wrong, "no row drifts from what it was");
}
/**
* Ink stays a small share of a picture of lettering. A decoder that
* loses its place fills rows in solid, so the share of ink rising
* far above what was coded is the shape that fault takes.
*/
public function inkStaysWhatItWasTestCase()
{
$rows = [];
for ($down = 0; $down < 40; $down++) {
$row = array_fill(0, 60, 1);
$begins = 5 + ($down % 7);
for ($across = $begins; $across < $begins + 6; $across++) {
$row[$across] = 0;
}
for ($across = 40; $across < 44; $across++) {
$row[$across] = 0;
}
$rows[] = $row;
}
$read = CcittFax::decode($this->codeRows($rows), 60, 40);
$most = 0;
foreach ($read as $row) {
$black = 0;
foreach ($row as $one) {
if ($one == 0) {
$black++;
}
}
$most = max($most, $black);
}
$this->assertTrue($most <= 12,
"no row holds more ink than was coded into it");
}
}
(c) 2026 Seekquarry - Open Source Search Engine Software