<?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
 *
 * This class turns a Theora keyframe into a picture.
 */
namespace seekquarry\yioop\library\av_processing;
/**
 * TheoraDecoder turns a Theora keyframe into a picture.
 */
final class TheoraDecoder
{
    /**
     * $version_major stores which version of Theora the stream was written for,
     * checked before anything else is read.
     * @var int
     */
    public int $version_major = 0;
    /**
     * $version_minor stores the second part of that version.
     * @var int
     */
    public int $version_minor = 0;
    /**
     * $version_revision stores the third part of that version.
     * @var int
     */
    public int $version_revision = 0;
    /**
     * $macroblocks_across stores how many macroblocks the frame is across.
     * Theora works in
     * sixteen by sixteen squares like the others.
     * @var int
     */
    public int $macroblocks_across = 0;
    /**
     * $macroblocks_down stores how many macroblocks the frame is down.
     * @var int
     */
    public int $macroblocks_down = 0;
    /**
     * $picture_w stores how wide the picture is meant to be shown, which can be
     * less than the coded frame.
     * @var int
     */
    public int $picture_w = 0;
    /**
     * $picture_h stores how tall the picture is meant to be shown.
     * @var int
     */
    public int $picture_h = 0;
    /**
     * $picture_x stores how far across the coded frame the shown picture
     * starts.
     * @var int
     */
    public int $picture_x = 0;
    /**
     * $picture_y stores how far down the coded frame it starts.
     * @var int
     */
    public int $picture_y = 0;
    /**
     * $frame_rate_count stores the upper half of the frame rate, which over the
     * lower half gives how many frames a second the video runs at.
     * @var int
     */
    public int $frame_rate_count = 1;
    /**
     * $frame_rate_den stores the lower half of the frame rate, used with the
     * upper half to turn a frame number into a moment in the video.
     * @var int
     */
    public int $frame_rate_den = 1;
    /**
     * $pixel_format stores how the color planes are shrunk against the
     * brightness: zero for half in each direction, two for half
     * across only, and three for no shrinking at all.
     * @var int
     */
    public int $pixel_format = 0;
    /**
     * $keyframe_granule_shift stores how many bits of a page's time stand for
     * the frames since the last keyframe. Ogg writes a frame's time as two
     * numbers packed into one, and this says where to split it.
     * @var int
     */
    public int $keyframe_granule_shift = 6;
    /**
     * $loop_filter_limits stores how far a value may be moved while smoothing
     * an edge, one limit per quantizer.
     * @var array
     */
    private array $loop_filter_limits = [];
    /**
     * $other_values_scale stores how the quantizer scales the values after the
     * first, one
     * entry per quality setting.
     * @var array
     */
    private array $other_values_scale = [];
    /**
     * $first_value_scale stores how it scales the first value of a block.
     * @var array
     */
    private array $first_value_scale = [];
    /**
     * $base_matrices stores the tables the stream carries for scaling values,
     * which the ranges below pick between.
     * @var array
     */
    private array $base_matrices = [];
    /**
     * $q_ranges stores which of those tables to use at each quality setting.
     * @var array
     */
    private array $q_ranges = [];
    /**
     * $huffman stores the trees the stream's values are read from, eighty of
     * them, read once out of the setup header.
     * @var array
     */
    private array $huffman = [];
    /**
     * $plane_width stores how wide each plane is, in samples.
     * @var array
     */
    private array $plane_width = [];
    /**
     * $plane_height stores how tall each plane is, in samples.
     * @var array
     */
    private array $plane_height = [];
    /**
     * $fragment_width stores how many eight by eight fragments each plane is
     * across. Theora codes a frame as fragments rather than whole blocks.
     * @var array
     */
    private array $fragment_width = [];
    /**
     * $fragment_height stores how many fragments each plane is down.
     * @var array
     */
    private array $fragment_height = [];
    /**
     * $fragment_start stores where each plane's fragments begin in the one long
     * list they are all kept in.
     * @var array
     */
    private array $fragment_start = [];
    /**
     * $fragment_count stores how many fragments each plane holds.
     * @var array
     */
    private array $fragment_count = [];
    /**
     * $total_fragments stores how many fragments the frame holds altogether.
     * @var int
     */
    private int $total_fragments = 0;
    /**
     * $coded_order stores the order the fragments are visited in, which is not
     * the order they sit in the picture.
     * @var array
     */
    private array $coded_order = [];
    /**
     * $have_identification stores whether the stream's first header has been
     * read.
     * Nothing can be decoded before it.
     * @var bool
     */
    private bool $have_identification = false;
    /**
     * $have_setup stores whether the stream's setup header has been read, which
     * carries the tables and trees.
     * @var bool
     */
    private bool $have_setup = false;
    /**
     * HILBERT is the order the sixteen four by four blocks of a macroblock are
     * visited in, which winds through them rather than reading row by row.
     * @var mixed
     */
    private const HILBERT = [
        [0, 0], [1, 0], [1, 1], [0, 1],
        [0, 2], [0, 3], [1, 3], [1, 2],
        [2, 2], [2, 3], [3, 3], [3, 2],
        [3, 1], [2, 1], [2, 0], [3, 0],
    ];
    /**
     * GROUP_MAX says where each group of places in a block stops. A
     * block's values are read with a different tree of choices
     * depending on how far into the block they sit, and this gives
     * the first place past each group.
     */
    private const GROUP_MAX = [1, 6, 15, 28, 64];
    /**
     * EOB_BASE is the smallest number of blocks each end-of-block code stands
     * for.
     * @var mixed
     */
    private const EOB_BASE = [1, 2, 3, 4, 8, 16, 0];
    /**
     * EOB_BITS is how many further bits follow each of those codes.
     * @var mixed
     */
    private const EOB_BITS = [0, 0, 0, 2, 3, 4, 12];
    /**
     * ZERO_RUN_BASE is the smallest run of zeros each run code stands for.
     * @var mixed
     */
    private const ZERO_RUN_BASE = [
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
        2, 3, 4, 5, 6, 10, 1, 2,
    ];
    /**
     * ZERO_RUN_BITS is how many further bits follow each run code.
     * @var mixed
     */
    private const ZERO_RUN_BITS = [
        0, 0, 0, 0, 0, 0, 0, 3, 6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 2, 3, 0, 1,
    ];
    /**
     * COEFF_BITS is how many bits the value itself takes, for each code that
     * carries one.
     * @var mixed
     */
    private const COEFF_BITS = [
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 3, 4, 5, 6, 10, 1,
        1, 1, 1, 1, 1, 1, 2, 2,
    ];
    /**
     * $value_tables stores which tree to read each value from, worked out from
     * the quantizer once rather than for every block.
     * @var array
     */
    private static array $value_tables = [];
    /**
     * C1S7 is iDCT constants (VP3).
     * @var mixed
     */
    private const C1S7 = 64277;
    /**
     * C2S6 is one of the fixed pairs of numbers the transform multiplies by,
     * standing for a cosine and a sine of the same angle.
     * @var mixed
     */
    private const C2S6 = 60547;
    /**
     * C3S5 is one of the fixed pairs of numbers the transform multiplies by,
     * standing for a cosine and a sine of the same angle.
     * @var mixed
     */
    private const C3S5 = 54491;
    /**
     * C4S4 is one of the fixed pairs of numbers the transform multiplies by,
     * standing for a cosine and a sine of the same angle.
     * @var mixed
     */
    private const C4S4 = 46341;
    /**
     * C5S3 is one of the fixed pairs of numbers the transform multiplies by,
     * standing for a cosine and a sine of the same angle.
     * @var mixed
     */
    private const C5S3 = 36410;
    /**
     * C6S2 is one of the fixed pairs of numbers the transform multiplies by,
     * standing for a cosine and a sine of the same angle.
     * @var mixed
     */
    private const C6S2 = 25080;
    /**
     * C7S1 is one of the fixed pairs of numbers the transform multiplies by,
     * standing for a cosine and a sine of the same angle.
     * @var mixed
     */
    private const C7S1 = 12785;
    /**
     * buildCoeffTables builds the code tables the coefficients are read with,
     * from the lengths the setup header lists.
     */
    private static function buildCoeffTables(): void
    {
        if (self::$value_tables !== []) {
            return;
        }
        $target = array_fill(0, 32, []);
        $target[7] = [0];
        $target[8] = [0];
        $target[9] = [1];
        $target[10] = [-1];
        $target[11] = [2];
        $target[12] = [-2];
        $target[13] = [3, -3];
        $target[14] = [4, -4];
        $target[15] = [5, -5];
        $target[16] = [6, -6];
        /* tokens 17..22 code increasingly wide magnitude ranges, positives */
        /* first then the matching negatives */
        foreach ([17 => [7, 8], 18 => [9, 12], 19 => [13, 20], 20
            => [21, 36], 21 => [37, 68], 22 => [69, 580]] as $token
                => [$lo, $hi]) {
            $values = [];
            for ($value = $lo; $value <= $hi; $value++) {
                $values[] = $value;
            }
            for ($value = $lo; $value <= $hi; $value++) {
                $values[] = -$value;
            }
            $target[$token] = $values;
        }
        for ($token = 23; $token <= 29; $token++) {
            $target[$token] = [1, -1];
        }
        $target[30] = [2, 3, -2, -3];
        $target[31] = [2, 3, -2, -3];
        self::$value_tables = $target;
    }
    /**
     * addHeader feed the identification, comment and setup header packets
     *
     * @param string $packet the packet read off the stream
     */
    public function addHeader(string $packet): void
    {
        if ($packet === '' || (ord($packet[0]) & 0x80) === 0) {
            return;
        }
        $type = ord($packet[0]);
        if (substr($packet, 1, 6) !== 'theora') {
            throw new VideoException('not a Theora header packet');
        }
        $bits = new BitReader(substr($packet, 7));
        if ($type === 0x80) {
            $this->parseIdentification($bits);
        } elseif ($type === 0x82) {
            $this->parseSetup($bits);
        }
        /* 0x81 is the comment header and carries nothing the decoder needs */
    }
    /**
     * isReady says whether all three setup headers have been read, so a frame
     * can be decoded.
     *
     * @return bool what was read
     */
    public function isReady(): bool
    {
        return $this->have_identification && $this->have_setup;
    }
    /**
     * parseIdentification reads the first setup header, which gives the picture
     * size, the frame rate and the quality.
     *
     * @param BitReader $bits the reader the stream's bits are taken from
     */
    private function parseIdentification(BitReader $bits): void
    {
        $this->version_major = $bits->readBits(8);
        $this->version_minor = $bits->readBits(8);
        $this->version_revision = $bits->readBits(8);
        if ($this->version_major !== 3) {
            throw new VideoException('unsupported Theora version '
                . $this->version_major);
        }
        $this->macroblocks_across = $bits->readBits(16);
        $this->macroblocks_down = $bits->readBits(16);
        $this->picture_w = $bits->readBits(24);
        $this->picture_h = $bits->readBits(24);
        $this->picture_x = $bits->readBits(8);
        $this->picture_y = $bits->readBits(8);
        $this->frame_rate_count = $bits->readBits(32);
        $this->frame_rate_den = $bits->readBits(32);
        /* pixel aspect numerator */
        $bits->readBits(24);
        /* pixel aspect denominator */
        $bits->readBits(24);
        /* color space */
        $bits->readBits(8);
        /* nominal bitrate */
        $bits->readBits(24);
        /* quality hint */
        $bits->readBits(6);
        $this->keyframe_granule_shift = $bits->readBits(5);
        $this->pixel_format = $bits->readBits(2);
        /* reserved */
        $bits->readBits(3);
        if ($this->pixel_format !== 0) {
            throw new VideoException('only 4:2:0 Theora is supported');
        }
        if ($this->macroblocks_across < 1 || $this->macroblocks_down < 1
            || $this->macroblocks_across * $this->macroblocks_down > 139264) {
            throw new VideoException('Theora frame size out of range: '
                . $this->macroblocks_across . 'x' . $this
                    ->macroblocks_down . ' macroblocks');
        }
        if ($this->picture_w < 2 || $this->picture_h < 2
            || $this->picture_x + $this->picture_w > $this
                ->macroblocks_across * 16
            || $this->picture_y + $this->picture_h > $this
                ->macroblocks_down * 16) {
            throw new VideoException(
                'Theora picture region does not fit its frame');
        }
        $this->initGeometry();
        $this->have_identification = true;
    }
    /**
     * initGeometry works out the plane sizes and the order the blocks are
     * visited in, from the picture size just read.
     */
    private function initGeometry(): void
    {
        $this->plane_width
            = [$this->macroblocks_across * 16, $this
                ->macroblocks_across * 8, $this->macroblocks_across * 8];
        $this->plane_height
            = [$this->macroblocks_down * 16, $this->macroblocks_down * 8,
                $this->macroblocks_down * 8];
        $this->fragment_width = [$this->macroblocks_across * 2, $this
            ->macroblocks_across, $this->macroblocks_across];
        $this->fragment_height = [$this->macroblocks_down * 2, $this
            ->macroblocks_down, $this->macroblocks_down];
        $start = 0;
        for ($plane_at = 0; $plane_at < 3; $plane_at++) {
            $this->fragment_start[$plane_at] = $start;
            $this->fragment_count[$plane_at]
                = $this->fragment_width[$plane_at] * $this
                    ->fragment_height[$plane_at];
            $start += $this->fragment_count[$plane_at];
        }
        $this->total_fragments = $start;
        /* fragments are visited in superblock order, following a fixed */
        /* space-filling curve inside each 4x4 superblock */
        for ($plane_at = 0; $plane_at < 3; $plane_at++) {
            $forward = $this->fragment_width[$plane_at];
            $handle = $this->fragment_height[$plane_at];
            $superblock_width = intdiv($forward + 3, 4);
            $superblock_height = intdiv($handle + 3, 4);
            $list = [];
            for ($superblock_y = 0; $superblock_y <
                $superblock_height; $superblock_y++) {
                for ($superblock_x = 0; $superblock_x <
                    $superblock_width; $superblock_x++) {
                    foreach (self::HILBERT as [$half_across, $hy]) {
                        $across = 4 * $superblock_x + $half_across;
                        $down = 4 * $superblock_y + $hy;
                        if ($across < $forward && $down < $handle) {
                            $list[] = $this
                                ->fragment_start[$plane_at] + $down * $forward
                                + $across;
                        }
                    }
                }
            }
            $this->coded_order[$plane_at] = $list;
        }
    }
    /**
     * parseSetup reads the third setup header, which holds the quantizer
     * matrices and the code tables.
     *
     * @param BitReader $bits the reader the stream's bits are taken from
     */
    private function parseSetup(BitReader $bits): void
    {
        if (!$this->have_identification) {
            throw new VideoException(
                'Theora setup header arrived before the identification header');
        }
        $bit_count = $bits->readBits(3);
        for ($quantizer = 0; $quantizer < 64; $quantizer++) {
            $this->loop_filter_limits[$quantizer] = $bit_count > 0
                ? $bits->readBits($bit_count)
                : 0;
        }
        $bit_count = $bits->readBits(4) + 1;
        for ($quantizer = 0; $quantizer < 64; $quantizer++) {
            $this->other_values_scale[$quantizer] = $bits->readBits($bit_count);
        }
        $bit_count = $bits->readBits(4) + 1;
        for ($quantizer = 0; $quantizer < 64; $quantizer++) {
            $this->first_value_scale[$quantizer] = $bits->readBits($bit_count);
        }
        $base_count = $bits->readBits(9) + 1;
        for ($i = 0; $i < $base_count; $i++) {
            $matches = [];
            for ($channel_index = 0; $channel_index < 64; $channel_index++) {
                $matches[$channel_index] = $bits->readBits(8);
            }
            $this->base_matrices[$i] = $matches;
        }
        $index_bits = self::bitsNeededFor($base_count - 1);
        for ($i = 0; $i < 6; $i++) {
            $quantizer_kind = intdiv($i, 3);
            $plane_at = $i % 3;
            if ($i > 0 && $bits->readBit() === 0) {
                /* this range set repeats an earlier one */
                if ($quantizer_kind > 0 && $bits->readBit() === 1) {
                    $source_quantizer_kind = $quantizer_kind - 1;
                    $source_plane = $plane_at;
                } else {
                    $source_quantizer_kind = intdiv($i - 1, 3);
                    $source_plane = ($i - 1) % 3;
                }
                $this->q_ranges[$quantizer_kind][$plane_at]
                    = $this->q_ranges[$source_quantizer_kind][$source_plane];
                continue;
            }
            $bases = [$bits->readBits($index_bits)];
            $sizes = [];
            $quantizer = 0;
            while ($quantizer < 63) {
                $size = $bits
                    ->readBits(self::bitsNeededFor(62 - $quantizer)) + 1;
                $sizes[] = $size;
                $quantizer += $size;
                $bases[] = $bits->readBits($index_bits);
            }
            if ($quantizer > 63) {
                throw new VideoException('malformed Theora quantizer ranges');
            }
            $this->q_ranges[$quantizer_kind][$plane_at] = ['sizes' => $sizes,
                'bases' => $bases];
        }
        self::buildCoeffTables();
        for ($i = 0; $i < 80; $i++) {
            $leaves = 0;
            $this->huffman[$i] = $this->readHuffmanTree($bits, 0, $leaves);
        }
        $this->have_setup = true;
    }
    /**
     * readHuffmanTree a Huffman table is stored as the shape of its binary tree
     *
     * @param BitReader $bits the reader the stream's bits are taken from
     * @param int $depth how deep in the tree
     * @param int $leaves what the tree's choices stand for
     * @return array the tree read, as its branches and their values
     */
    private function readHuffmanTree(
        BitReader $bits, int $depth, int &$leaves)
    {
        if ($depth > 32) {
            throw new VideoException('Theora Huffman tree too deep');
        }
        if ($bits->readBit() === 1) {
            /* a table has one leaf per token, so anything past 32 is corrupt */
            if (++$leaves > 32) {
                throw new VideoException(
                    'Theora Huffman table has too many entries');
            }
            return $bits->readBits(5);
        }
        $left = $this->readHuffmanTree($bits, $depth + 1, $leaves);
        $right = $this->readHuffmanTree($bits, $depth + 1, $leaves);
        return [$left, $right];
    }
    /**
     * bitsNeededFor works out how many bits a number needs, which the format
     * uses to size several of its fields.
     *
     * @param int $value the value read
     * @return int what was read
     */
    private static function bitsNeededFor(int $value): int
    {
        $total = 0;
        while ($value > 0) {
            $total++;
            $value >>= 1;
        }
        return $total;
    }
    /**
     * huffDecode reads one value by walking a code tree a bit at a time.
     *
     * @param BitReader $bits the reader the stream's bits are taken from
     * @param int $table the table to read from
     * @return int what was read
     */
    private function huffDecode(BitReader $bits, int $table): int
    {
        $node = $this->huffman[$table];
        $guard = 0;
        while (is_array($node)) {
            $node = $node[$bits->readBit()];
            if (++$guard > 32) {
                throw new VideoException('invalid Theora Huffman code');
            }
        }
        return $node;
    }
    /**
     * dequantMatrix dequantization matrix in raster order for one quality index
     * / plane for color one for the rest
     *
     * @param int $quantizer which quantizer the frame was coded at
     * @param int $plane_at which plane, zero for brightness and one or two
     * @param int $quantizer_kind which quantizer table, one for keyframes and
     * @return array what was read
     */
    private function dequantMatrix(int $quantizer, int $plane_at,
        int $quantizer_kind): array
    {
        $range = $this->q_ranges[$quantizer_kind][$plane_at];
        $sizes = $range['sizes'];
        $bases = $range['bases'];
        $sum = 0;
        $quantizer_range = 0;
        for ($quantizer_range = 0; $quantizer_range <
            count($sizes); $quantizer_range++) {
            $sum += $sizes[$quantizer_range];
            if ($quantizer <= $sum) {
                break;
            }
        }
        if ($quantizer_range >= count($sizes)) {
            $quantizer_range = max(0, count($sizes) - 1);
            $sum = array_sum($sizes);
        }
        $size = $sizes[$quantizer_range];
        $quantizer_start = $sum - $size;
        $block_mode_a = $this->base_matrices[$bases[$quantizer_range]];
        $block_mode_b = $this->base_matrices[$bases[$quantizer_range + 1]];
        $other_values = $this->other_values_scale[$quantizer];
        $first_value = $this->first_value_scale[$quantizer];
        $written = [];
        for ($i = 0; $i < 64; $i++) {
            /* interpolate between the two base matrices bracketing this qi */
            $value = intdiv(
                2 * ($sum - $quantizer) * $block_mode_a[$i] - 2 *
                    ($quantizer_start -
                    $quantizer) * $block_mode_b[$i]
                    + $size,
                2 * $size
            );
            $smallest_quantizer = 8 << ($quantizer_kind + ($i === 0 ? 1 : 0));
            $quantizer_scale = $i ? $other_values : $first_value;
            $quant = intdiv($quantizer_scale * $value, 100) * 4;
            if ($quant < $smallest_quantizer) {
                $quant = $smallest_quantizer;
            } elseif ($quant > 4096) {
                $quant = 4096;
            }
            $written[$i] = $quant;
        }
        return $written;
    }
    /**
     * decodeIntra decode one intra frame packet.
     *
     * @return VideoPicture what was read
     * @param string $packet the packet read off the stream
     */
    public function decodeIntra(string $packet): VideoPicture
    {
        if (!$this->isReady()) {
            throw new VideoException('Theora headers have not been read');
        }
        if ($packet === '') {
            throw new VideoException('empty Theora packet');
        }
        $bits = new BitReader($packet);
        if ($bits->readBit() !== 0) {
            throw new VideoException('expected a Theora data packet');
        }
        if ($bits->readBit() !== 0) {
            throw new VideoException('only Theora keyframes can be decoded');
        }
        $quantizers = [$bits->readBits(6)];
        if ($bits->readBit() === 1) {
            $quantizers[] = $bits->readBits(6);
            if ($bits->readBit() === 1) {
                $quantizers[] = $bits->readBits(6);
            }
        }
        /* three unused bits, a holdover from VP3 */
        $bits->readBits(3);
        /* in an intra frame every fragment is coded and every one is intra */
        $quantizer_step = $this->unpackBlockQis($bits, count($quantizers));
        $values = $this->unpackTokens($bits);
        $this->reverseDcPrediction($values);
        return $this->reconstruct($values, $quantizers, $quantizer_step);
    }
    /**
     * unpackBlockQis 0-based quality index selector per fragment, in coded
     * order
     *
     * @param BitReader $bits the reader the stream's bits are taken from
     * @param int $quantizer_count how many quantizers the stream offers
     * @return array what was read
     */
    private function unpackBlockQis(BitReader $bits,
        int $quantizer_count): array
    {
        $quantizer_step = array_fill(0, $this->total_fragments, 0);
        if ($quantizer_count === 1) {
            return $quantizer_step;
        }
        $all = array_merge(
            $this->coded_order[0], $this->coded_order[1],
                $this->coded_order[2]);
        $total = count($all);
        /* a run-length coded flag per fragment, then a second pass to */
        /* distinguish the second and third quality indices */
        $flag = $bits->readBit();
        $i = 0;
        $quantizer_count_one = 0;
        while ($i < $total) {
            $run = self::runUnpack($bits);
            $full = $run >= 4129;
            do {
                $quantizer_step[$all[$i++]] = $flag;
                $quantizer_count_one += $flag;
            } while (--$run > 0 && $i < $total);
            $flag = ($full && $i < $total) ? $bits->readBit() : 1 - $flag;
        }
        if ($quantizer_count === 3 && $quantizer_count_one > 0) {
            $flag = $bits->readBit();
            $i = 0;
            while ($i < $total) {
                while ($i < $total && $quantizer_step[$all[$i]] === 0) {
                    $i++;
                }
                if ($i >= $total) {
                    break;
                }
                $run = self::runUnpack($bits);
                $full = $run >= 4129;
                while ($run > 0 && $i < $total) {
                    if ($quantizer_step[$all[$i]] !== 0) {
                        $quantizer_step[$all[$i]] = 1 + $flag;
                        $run--;
                    }
                    $i++;
                }
                $flag = ($full && $i < $total) ? $bits->readBit() : 1
                    - $flag;
            }
        }
        return $quantizer_step;
    }
    /**
     * runUnpack the run length code shared by superblock coded flags and block
     * quality indices: 0                    1 10x                  2-3 110x
     * 4-5 1110xx               6-9 11110 then three more bits: 10 to 17 111110
     * then four more bits: 18 to 33 111111 then twelve more bits: 34 to 4129
     *
     * @param BitReader $bits the reader the stream's bits are taken from
     * @return int what was read
     */
    private static function runUnpack(BitReader $bits): int
    {
        if ($bits->readBit() === 0) {
            return 1;
        }
        if ($bits->readBit() === 0) {
            return 2 + $bits->readBits(1);
        }
        if ($bits->readBit() === 0) {
            return 4 + $bits->readBits(1);
        }
        if ($bits->readBit() === 0) {
            return 6 + $bits->readBits(2);
        }
        if ($bits->readBit() === 0) {
            return 10 + $bits->readBits(3);
        }
        if ($bits->readBit() === 0) {
            return 18 + $bits->readBits(4);
        }
        return 34 + $bits->readBits(12);
    }
    /**
     * unpackTokens read every coefficient token. Tokens are not grouped by
     * block: the whole frame is scanned once per coefficient index, and within
     * each pass once per plane, so a block's coefficients are spread across the
     * packet. End-of-block runs carry over between planes and between passes.
     *
     * @return array coefficients per fragment, in zig-zag order
     * @param BitReader $bits the reader the stream's bits are taken from
     */
    private function unpackTokens(BitReader $bits): array
    {
        $values = [];
        $ti = array_fill(0, $this->total_fragments, 0);
        $this->end_of_block_run = 0;
        $first_value_y = $bits->readBits(4);
        $first_value_c = $bits->readBits(4);
        for ($plane_at = 0; $plane_at < 3; $plane_at++) {
            $this->unpackPass($bits, 0, $plane_at, $plane_at ===
                0 ? $first_value_y
                : $first_value_c, $values, $ti);
        }
        $other_values_y = $bits->readBits(4);
        $other_values_c = $bits->readBits(4);
        $order_at = 1;
        for ($half_group_index = 1; $half_group_index <
            5; $half_group_index++) {
            $table_y = $other_values_y + 16 * $half_group_index;
            $table_c = $other_values_c + 16 * $half_group_index;
            for (; $order_at <
                self::GROUP_MAX[$half_group_index]; $order_at++) {
                for ($plane_at = 0; $plane_at < 3; $plane_at++) {
                    $this->unpackPass($bits, $order_at, $plane_at,
                        $plane_at === 0
                        ? $table_y
                        : $table_c, $values, $ti);
                }
            }
        }
        return $values;
    }
    /**
     * $end_of_block_run stores how many blocks in a row have nothing
     * left to read. A stream says once that a run of blocks is
     * finished rather than saying so for each.
     * @var int
     */
    private int $end_of_block_run = 0;
    /**
     * unpackPass reads one pass of the coefficient data, which is stored a
     * position at a time across all blocks rather than a block at a time. for
     * color
     *
     * @param BitReader $bits the reader the stream's bits are taken from
     * @param int $order_at where in that order the value sits
     * @param int $plane_at which plane, zero for brightness and one or two
     * @param int $table the table to read from
     * @param array & $values
     * @param array & $ti
     */
    private function unpackPass(BitReader $bits, int $order_at, int $plane_at,
        int $table, array &$values, array &$ti): void
    {
        self::buildCoeffTables();
        foreach ($this->coded_order[$plane_at] as $fi) {
            if ($ti[$fi] !== $order_at) {
                continue;
            }
            if ($this->end_of_block_run > 0) {
                $this->end_of_block_run--;
                $ti[$fi] = 64;
                continue;
            }
            if ($bits->bitsLeft() <= 0) {
                $ti[$fi] = 64;
                continue;
            }
            $token = $this->huffDecode($bits, $table);
            if ($token <= 6) {
                $run = self::EOB_BASE[$token];
                if (self::EOB_BITS[$token] > 0) {
                    $run += $bits->readBits(self::EOB_BITS[$token]);
                }
                if ($run === 0) {
                    /* an empty count means "to the end" */
                    $run = PHP_INT_MAX;
                }
                $this->end_of_block_run = $run - 1;
                $ti[$fi] = 64;
                continue;
            }
            $bits = self::COEFF_BITS[$token];
            $index = $bits > 0 ? $bits->readBits($bits) : 0;
            $value = self::$value_tables[$token][$index] ?? 0;
            $zero_run = self::ZERO_RUN_BASE[$token];
            if (self::ZERO_RUN_BITS[$token] > 0) {
                $zero_run += $bits->readBits(self::ZERO_RUN_BITS[$token]);
            }
            $position = $order_at + $zero_run;
            if ($position > 63) {
                $ti[$fi] = 64;
                continue;
            }
            if ($value !== 0) {
                if (!isset($values[$fi])) {
                    $values[$fi] = array_fill(0, 64, 0);
                }
                $values[$fi][$position] = $value;
            }
            $ti[$fi] = $position + 1;
        }
    }
    /**
     * reverseDcPrediction the DC coefficient of each block is coded as a
     * difference from a prediction built out of its already-decoded neighbors.
     *
     * @param array $values the values the block was coded as
     */
    private function reverseDcPrediction(array &$values): void
    {
        /* weights for up-left, up, up-right and left, selected by which of */
        /* those neighbors exist */
        static $transform = [
            [0, 0, 0, 0], [0, 0, 0, 128], [0, 0, 128, 0], [0, 0, 53, 75],
            [0, 128, 0, 0], [0, 64, 0, 64], [0, 128, 0, 0], [0, 0, 53, 75],
            [128, 0, 0, 0], [0, 0, 0, 128], [64, 0, 64, 0], [0, 0, 53, 75],
            [0, 128, 0, 0], [-104, 116, 0, 116], [24, 80, 24, 0],
            [-104, 116, 0, 116],
        ];
        for ($plane_at = 0; $plane_at < 3; $plane_at++) {
            $forward = $this->fragment_width[$plane_at];
            $handle = $this->fragment_height[$plane_at];
            $base = $this->fragment_start[$plane_at];
            $last_first_value = 0;
            for ($down = 0; $down < $handle; $down++) {
                for ($across = 0; $across < $forward; $across++) {
                    $i = $base + $down * $forward + $across;
                    $mask = 0;
                    $vertical_left = $vu = $upper_right = $upper_left = 0;
                    if ($across > 0) {
                        $mask |= 1;
                        $vertical_left = $values[$i - 1][0] ?? 0;
                    }
                    if ($down > 0 && $across + 1 < $forward) {
                        $mask |= 2;
                        $upper_right = $values[$i - $forward + 1][0] ?? 0;
                    }
                    if ($down > 0) {
                        $mask |= 4;
                        $vu = $values[$i - $forward][0] ?? 0;
                    }
                    if ($down > 0 && $across > 0) {
                        $mask |= 8;
                        $upper_left = $values[$i - $forward - 1][0] ?? 0;
                    }
                    if ($mask === 0) {
                        $predicted = $last_first_value;
                    } else {
                        $wide = $transform[$mask];
                        $predicted = intdiv(
                            $wide[0] * $upper_left + $wide[1] * $vu +
                                $wide[2] * $upper_right
                                + $wide[3] * $vertical_left,
                            128
                        );
                        if ($mask === 15 || $mask === 13) {
                            /* guard against the three-and-four neighbor */
                            /* predictors running away from their inputs */
                            if (abs($predicted - $vu) > 128) {
                                $predicted = $vu;
                            } elseif (abs($predicted - $vertical_left) > 128) {
                                $predicted = $vertical_left;
                            } elseif (abs($predicted - $upper_left) > 128) {
                                $predicted = $upper_left;
                            }
                        }
                    }
                    $first_value = ($values[$i][0] ?? 0) + $predicted;
                    if ($first_value !== 0 && !isset($values[$i])) {
                        $values[$i] = array_fill(0, 64, 0);
                    }
                    if (isset($values[$i])) {
                        $values[$i][0] = $first_value;
                    }
                    $last_first_value = $first_value;
                }
            }
        }
    }
    /**
     * reconstruct dequantize, transform and filter every block into the output
     * planes
     *
     * @param array $values the values the block was coded as
     * @param array $quantizers the quantizers the stream offers
     * @param array $quantizer_step which step of the quantizer range
     * @return VideoPicture what was read
     */
    private function reconstruct(
        array $values, array $quantizers, array $quantizer_step): VideoPicture
    {
        $planes = [];
        /* [qiIndex][plane] => matrix */
        $descale = [];
        foreach ($quantizers as $k => $quantizer) {
            for ($plane_at = 0; $plane_at < 3; $plane_at++) {
                $descale[$k][$plane_at] = $this->dequantMatrix($quantizer,
                    $plane_at, 0);
            }
        }
        $first_value_quant = [];
        for ($plane_at = 0; $plane_at < 3; $plane_at++) {
            $first_value_quant[$plane_at] = $descale[0][$plane_at][0];
        }
        $block_order = H264Scan::ZZ8;
        for ($plane_at = 0; $plane_at < 3; $plane_at++) {
            $picture_width = $this->plane_width[$plane_at];
            $picture_header = $this->plane_height[$plane_at];
            $plane = array_fill(0, $picture_width * $picture_header, 0);
            $forward = $this->fragment_width[$plane_at];
            $handle = $this->fragment_height[$plane_at];
            $base = $this->fragment_start[$plane_at];
            for ($down = 0; $down < $handle; $down++) {
                for ($across = 0; $across < $forward; $across++) {
                    $i = $base + $down * $forward + $across;
                    $block = array_fill(0, 64, 0);
                    if (isset($values[$i])) {
                        $quant = $descale[$quantizer_step[$i] ?? 0][$plane_at];
                        $chunk = $values[$i];
                        for ($order_at = 1; $order_at < 64; $order_at++) {
                            if ($chunk[$order_at] !== 0) {
                                $result = $block_order[$order_at];
                                $block[$result]
                                    = $chunk[$order_at] * $quant[$result];
                            }
                        }
                        /* the DC uses the first quality index's matrix so that
                          */
                        /* DC prediction stays consistent across the frame */
                        $block[0] = $chunk[0] * $first_value_quant[$plane_at];
                    }
                    self::idctPut($plane, $picture_width, $across * 8,
                        $down * 8, $block);
                }
            }
            $planes[$plane_at] = $plane;
        }
        $this->loopFilter($planes, $quantizers[0]);
        return $this->toPicture($planes);
    }
    /**
     * fixedPointMultiply 32-bit truncating fixed-point multiply, as the format
     * defines it
     *
     * @param int $amount how much
     * @param int $bits the reader the stream's bits are taken from
     * @return int what was read
     */
    private static function fixedPointMultiply(int $amount, int $bits): int
    {
        $position = ($amount * $bits) & 0xFFFFFFFF;
        if ($position >= 0x80000000) {
            $position -= 0x100000000;
        }
        return $position >> 16;
    }
    /**
     * holdInsideByte holds a sample inside the range a byte can carry.
     *
     * @param int $value the value read
     * @return int what was read
     */
    private static function holdInsideByte(int $value): int
    {
        return $value < 0 ? 0 : ($value > 255 ? 255 : $value);
    }
    /**
     * idctPut vP3 inverse DCT, writing an intra block straight into the plane.
     * Rows are transformed first and columns second. The two passes are not
     * interchangeable: each rounds its output, so swapping them shifts a
     * scattering of samples by one.
     *
     * @param array $plane which of the picture's planes, brightness or color
     * @param int $stride how many values one row of the picture takes
     * @param int $pixel_x how far across the frame the pixel is
     * @param int $pixel_y how far down the frame the pixel is
     * @param array $self_contained whether the block stands on its own
     */
    private static function idctPut(array
        &$plane, int $stride, int $pixel_x, int $pixel_y,
            array $self_contained): void
    {
        /* pass one: rows, in place */
        for ($i = 0; $i < 8; $i++) {
            $offset = $i * 8;
            if (($self_contained[$offset] | $self_contained[$offset + 1] |
                $self_contained[$offset
                + 2] | $self_contained[$offset + 3]
                | $self_contained[$offset + 4] | $self_contained[$offset +
                    5] | $self_contained[$offset
                    + 6] | $self_contained[$offset
                    + 7]) === 0) {
                continue;
            }
            $above_run = self::fixedPointMultiply(self::C1S7,
                $self_contained[$offset + 1])
                + self::fixedPointMultiply(self::C7S1,
                    $self_contained[$offset + 7]);
            $below_run = self::fixedPointMultiply(self::C7S1,
                $self_contained[$offset + 1])
                - self::fixedPointMultiply(self::C1S7,
                    $self_contained[$offset + 7]);
            $carry = self::fixedPointMultiply(self::C3S5,
                $self_contained[$offset + 3])
                + self::fixedPointMultiply(self::C5S3,
                    $self_contained[$offset + 5]);
            $diagonal = self::fixedPointMultiply(self::C3S5,
                $self_contained[$offset + 5])
                - self::fixedPointMultiply(self::C5S3,
                    $self_contained[$offset + 3]);
            $ad = self::fixedPointMultiply(self::C4S4, $above_run - $carry);
            $bit_depth = self::fixedPointMultiply(self::C4S4,
                $below_run - $diagonal);
            $code = $above_run + $carry;
            $difference = $below_run + $diagonal;
            $east = self::fixedPointMultiply(self::C4S4,
                $self_contained[$offset] +
                $self_contained[$offset + 4]);
            $far = self::fixedPointMultiply(self::C4S4,
                $self_contained[$offset] -
                $self_contained[$offset + 4]);
            $gain = self::fixedPointMultiply(self::C2S6,
                $self_contained[$offset + 2])
                + self::fixedPointMultiply(self::C6S2,
                    $self_contained[$offset + 6]);
            $tall = self::fixedPointMultiply(self::C6S2,
                $self_contained[$offset + 2])
                - self::fixedPointMultiply(self::C2S6,
                    $self_contained[$offset + 6]);
            $ed = $east - $gain;
            $image_library = $east + $gain;
            $add = $far + $ad;
            $bit_depth_delta = $bit_depth - $tall;
            $file_handle = $far - $ad;
            $header = $bit_depth + $tall;
            $self_contained[$offset]     = $image_library + $code;
            $self_contained[$offset + 7] = $image_library - $code;
            $self_contained[$offset + 1] = $add + $header;
            $self_contained[$offset + 2] = $add - $header;
            $self_contained[$offset + 3] = $ed + $difference;
            $self_contained[$offset + 4] = $ed - $difference;
            $self_contained[$offset + 5] = $file_handle + $bit_depth_delta;
            $self_contained[$offset + 6] = $file_handle - $bit_depth_delta;
        }
        /* pass two: columns, writing the block out */
        for ($across = 0; $across < 8; $across++) {
            if (($self_contained[$across + 8] | $self_contained[$across +
                16] | $self_contained[$across
                + 24] | $self_contained[$across + 32]
                | $self_contained[$across + 40] | $self_contained[$across +
                    48] | $self_contained[$across
                    + 56]) === 0) {
                $value = self::holdInsideByte(128
                    + ((self::C4S4 * $self_contained[$across] +
                        (8 << 16)) >> 20));
                for ($k = 0; $k < 8; $k++) {
                    $plane[($pixel_y + $k) * $stride + $pixel_x + $across] =
                        $value;
                }
                continue;
            }
            $above_run = self::fixedPointMultiply(self::C1S7,
                $self_contained[$across + 8])
                + self::fixedPointMultiply(self::C7S1,
                    $self_contained[$across + 56]);
            $below_run = self::fixedPointMultiply(self::C7S1,
                $self_contained[$across + 8])
                - self::fixedPointMultiply(self::C1S7,
                    $self_contained[$across + 56]);
            $carry = self::fixedPointMultiply(self::C3S5,
                $self_contained[$across + 24])
                + self::fixedPointMultiply(self::C5S3,
                    $self_contained[$across + 40]);
            $diagonal = self::fixedPointMultiply(self::C3S5,
                $self_contained[$across + 40])
                - self::fixedPointMultiply(self::C5S3,
                    $self_contained[$across + 24]);
            $ad = self::fixedPointMultiply(self::C4S4, $above_run - $carry);
            $bit_depth = self::fixedPointMultiply(self::C4S4,
                $below_run - $diagonal);
            $code = $above_run + $carry;
            $difference = $below_run + $diagonal;
            $east = self::fixedPointMultiply(self::C4S4,
                $self_contained[$across] +
                $self_contained[$across + 32]) + 8
                + 16 * 128;
            $far = self::fixedPointMultiply(self::C4S4,
                $self_contained[$across] -
                $self_contained[$across + 32]) + 8
                + 16 * 128;
            $gain = self::fixedPointMultiply(self::C2S6,
                $self_contained[$across + 16])
                + self::fixedPointMultiply(self::C6S2,
                    $self_contained[$across + 48]);
            $tall = self::fixedPointMultiply(self::C6S2,
                $self_contained[$across + 16])
                - self::fixedPointMultiply(self::C2S6,
                    $self_contained[$across + 48]);
            $ed = $east - $gain;
            $image_library = $east + $gain;
            $add = $far + $ad;
            $bit_depth_delta = $bit_depth - $tall;
            $file_handle = $far - $ad;
            $header = $bit_depth + $tall;
            $col = $pixel_x + $across;
            $plane[$pixel_y * $stride + $col]
                = self::holdInsideByte(($image_library + $code) >> 4);
            $plane[($pixel_y + 7) * $stride + $col]
                = self::holdInsideByte(($image_library - $code) >> 4);
            $plane[($pixel_y + 1) * $stride + $col]
                = self::holdInsideByte(($add + $header) >> 4);
            $plane[($pixel_y + 2) * $stride + $col]
                = self::holdInsideByte(($add - $header) >> 4);
            $plane[($pixel_y + 3) * $stride + $col]
                = self::holdInsideByte(($ed + $difference) >> 4);
            $plane[($pixel_y + 4) * $stride + $col]
                = self::holdInsideByte(($ed - $difference) >> 4);
            $plane[($pixel_y + 5) * $stride + $col]
                = self::holdInsideByte(($file_handle + $bit_depth_delta) >> 4);
            $plane[($pixel_y + 6) * $stride + $col]
                = self::holdInsideByte(($file_handle - $bit_depth_delta) >> 4);
        }
    }
    /**
     * loopFilter deblocking. Every block is coded in an intra frame, so only
     * the left and top edge of each block is filtered; the right and bottom
     * edges are picked up as the left and top edges of the next block.
     *
     * @param array $planes the picture's planes, brightness and color
     * @param int $quantizer which quantizer the frame was coded at
     */
    private function loopFilter(array &$planes, int $quantizer): void
    {
        $limit = $this->loop_filter_limits[$quantizer] ?? 0;
        if ($limit <= 0) {
            return;
        }
        $bounds = self::boundingValues($limit);
        for ($plane_at = 0; $plane_at < 3; $plane_at++) {
            $stride = $this->plane_width[$plane_at];
            $forward = $this->fragment_width[$plane_at];
            $handle = $this->fragment_height[$plane_at];
            $plane = &$planes[$plane_at];
            for ($down = 0; $down < $handle; $down++) {
                for ($across = 0; $across < $forward; $across++) {
                    $ox = $across * 8;
                    $origin_y = $down * 8;
                    if ($across > 0) {
                        for ($k = 0; $k < 8; $k++) {
                            self::filterLine($plane, ($origin_y + $k) * $stride
                                + $ox, 1, $bounds);
                        }
                    }
                    if ($down > 0) {
                        for ($k = 0; $k < 8; $k++) {
                            self::filterLine($plane, $origin_y * $stride + $ox
                                + $k, $stride, $bounds);
                        }
                    }
                }
            }
            unset($plane);
        }
    }
    /**
     * boundingValues works out how far a value may be moved while smoothing an
     * edge, for the quantizer in force.
     *
     * @return array indexed by difference + 256
     * @param int $limit the most that may be read
     */
    private static function boundingValues(int $limit): array
    {
        $bits = array_fill(0, 512, 0);
        for ($across = 0; $across < $limit; $across++) {
            $bits[256 - $across] = -$across;
            $bits[256 + $across] = $across;
        }
        for ($across = $limit, $value = $limit; $across < 128
            && $value > 0; $across++, $value--) {
            $bits[256 + $across] = $value;
            $bits[256 - $across] = -$value;
        }
        return $bits;
    }
    /**
     * filterLine smooths one line of samples crossing a block edge.
     *
     * @param array & $plane zero for luma, one and two for the chroma planes
     * @param int $base the value the rest are measured from
     * @param int $step how far to move each time
     * @param array $bounds how far the values may go
     */
    private static function filterLine(array
        &$plane, int $base, int $step, array $bounds): void
    {
        $before_edge_two = $plane[$base - 2 * $step];
        $before_edge_one = $plane[$base - $step];
        $after_edge = $plane[$base];
        $after_edge_one = $plane[$base + $step];
        $frame = ($before_edge_two - $after_edge_one) + ($after_edge -
            $before_edge_one) * 3;
        $frame = ($frame + 4) >> 3;
        if ($frame < -255) {
            $frame = -255;
        } elseif ($frame > 255) {
            $frame = 255;
        }
        $frame = $bounds[256 + $frame];
        if ($frame === 0) {
            return;
        }
        $plane[$base - $step] = self::holdInsideByte($before_edge_one + $frame);
        $plane[$base] = self::holdInsideByte($after_edge - $frame);
    }
    /**
     * toPicture flip into display orientation and apply the picture region
     *
     * @param array $planes the picture's planes, brightness and color
     * @return VideoPicture what was read
     */
    private function toPicture(array $planes): VideoPicture
    {
        $line_width = $this->plane_width[0];
        $left_half = $this->plane_height[0];
        $code_word = $this->plane_width[1];
        $channel = $this->plane_height[1];
        $luma = array_fill(0, $line_width * $left_half, 0);
        for ($down = 0; $down < $left_half; $down++) {
            $source = ($left_half - 1 - $down) * $line_width;
            $target = $down * $line_width;
            for ($across = 0; $across < $line_width; $across++) {
                $luma[$target + $across] = $planes[0][$source + $across];
            }
        }
        $blue = array_fill(0, $code_word * $channel, 0);
        $red = array_fill(0, $code_word * $channel, 0);
        for ($down = 0; $down < $channel; $down++) {
            $source = ($channel - 1 - $down) * $code_word;
            $target = $down * $code_word;
            for ($across = 0; $across < $code_word; $across++) {
                $blue[$target + $across] = $planes[1][$source + $across];
                $red[$target + $across] = $planes[2][$source + $across];
            }
        }
        /* the picture offset is measured from the bottom in Theora's space */
        $off_x = $this->picture_x;
        $off_y = $left_half - $this->picture_h - $this->picture_y;
        return new VideoPicture(
            $luma, $blue, $red,
            $this->picture_w, $this->picture_h,
            $line_width, $code_word,
            $off_x, $off_y
        );
    }
}
