<?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");
    }
}
