<?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\av_processing;

/**
 * RangeDecoder reads the compressed sound in an Opus recording back into the
 * numbers it was made from. Everything inside a piece of Opus sound is stored
 * this way, so nothing else about the sound can be read until this can. Rather
 * than give each number its own whole bits, the writer narrows a range down a
 * little for each number it stores, in proportion to how likely that number
 * was, and writes out only what is needed to say where in the range it ended
 * up. A number that was expected costs a fraction of a bit; a surprising one
 * costs several. Reading works the same narrowing backwards, which is why the
 * numbers have to come out in exactly the order they went in, and why one wrong
 * step makes everything after it meaningless. Some values are stored as they
 * are rather than by likelihood, and those are written from the far end of the
 * piece working backwards, so a piece is read from both ends at once and the
 * two meet somewhere in the middle. The method is set out in RFC 6716, the
 * specification of the Opus audio codec, in the section on the range coder.
 */
class RangeDecoder
{
    /**
     * CODE_BITS is how wide the working number is, in bits.
     */
    const CODE_BITS = 32;
    /**
     * SYMBOL_BITS is how many bits are taken in at a time when the range gets
     * too narrow to go on.
     */
    const SYMBOL_BITS = 8;
    /**
     * SYMBOL_MAX is largest value the bits above can hold.
     */
    const SYMBOL_MAX = 255;
    /**
     * CODE_TOP is the value the working number is kept below.
     */
    const CODE_TOP = 0x80000000;
    /**
     * CODE_BOTTOM is the value the range is kept above; below this more of the
     * piece is taken in.
     */
    const CODE_BOTTOM = 0x800000;
    /**
     * CODE_EXTRA is how many bits of the first byte are used to start the
     * working number off.
     */
    const CODE_EXTRA = 7;
    /**
     * CODE_SHIFT is how far to shift the working number to reach the byte that
     * has been settled.
     */
    const CODE_SHIFT = 23;
    /**
     * UINT_BITS is largest number of bits a value stored as it is may take
     * before it has to be split in two.
     */
    const UINT_BITS = 8;
    /**
     * WINDOW_SIZE is how wide the store of bits written as they are is.
     */
    const WINDOW_SIZE = 32;
    /**
     * data stores the piece of sound being read.
     * @var string
     */
    public $data;
    /**
     * size stores how long that piece is.
     * @var int
     */
    public $size;
    /**
     * How far in from the front the read has got
     * @var int
     */
    public $front;
    /**
     * How far in from the back the read has got
     * @var int
     */
    public $back;
    /**
     * range stores how wide the span of numbers still in play is.
     * Every value read narrows it by how likely that value was, and it
     * is widened again when it grows too small to split.
     * @var int
     */
    public $range;
    /**
     * value stores where in the range the piece says the numbers ended up.
     * @var int
     */
    public $value;
    /**
     * held stores the last byte taken in from the front, kept because the
     * working number straddles two bytes.
     * @var int
     */
    public $held;
    /**
     * window stores bits taken from the back and not yet handed out.
     * @var int
     */
    public $window;
    /**
     * window_bits stores how many bits the store above holds.
     * @var int
     */
    public $window_bits;
    /**
     * bits_used stores how many bits of the piece have been accounted for,
     * which is how the reader knows when a piece has been read out.
     * @var int
     */
    public $bits_used;
    /**
     * step stores worked out during a read and needed again when the range is
     * narrowed, so it is kept rather than passed back and forth.
     * @var int
     */
    public $step;
    /**
     * __construct sets up a read over one piece of compressed sound
     *
     * @param string $data the piece to read
     */
    public function __construct($data)
    {
        $this->data = $data;
        $this->size = strlen($data);
        $this->front = 0;
        $this->back = 0;
        $this->window = 0;
        $this->window_bits = 0;
        $this->step = 0;
        $this->bits_used = self::CODE_BITS + 1 -
            intdiv(self::CODE_BITS - self::CODE_EXTRA, self::SYMBOL_BITS) *
            self::SYMBOL_BITS;
        /* The range starts at the width of the bits taken from the
           first byte, not at a whole byte. Starting it a byte wide
           leaves it short of the width the writer used, and every
           number after the first few comes out wrong. */
        $this->range = 1 << self::CODE_EXTRA;
        $this->held = $this->readByte();
        $this->value = $this->range - 1 -
            ($this->held >> (self::SYMBOL_BITS - self::CODE_EXTRA));
        $this->widen();
    }
    /**
     * readByte takes the next byte from the front of the piece, giving zero
     * once the piece has run out
     *
     * @return int the byte read
     */
    public function readByte()
    {
        if ($this->front >= $this->size) {
            return 0;
        }
        $byte = ord($this->data[$this->front]);
        $this->front++;
        return $byte;
    }
    /**
     * readByteFromBack takes the next byte from the back of the piece, giving
     * zero once the two ends of the read have met
     *
     * @return int the byte read
     */
    public function readByteFromBack()
    {
        if ($this->back >= $this->size) {
            return 0;
        }
        $this->back++;
        return ord($this->data[$this->size - $this->back]);
    }
    /**
     * widen takes in more of the piece until the range is wide enough to go on
     * reading numbers out of it
     */
    public function widen()
    {
        while ($this->range <= self::CODE_BOTTOM) {
            $this->bits_used += self::SYMBOL_BITS;
            $this->range = ($this->range << self::SYMBOL_BITS) &
                0xFFFFFFFF;
            /* The byte is pulled in place rather than through a call,
               since this is the busiest loop in the reading. */
            $next = ($this->front < $this->size) ?
                ord($this->data[$this->front++]) : 0;
            /* The working number does not line up with the bytes, so
               each step uses the tail of the byte before along with the
               head of the one just taken. */
            $part = (($this->held << self::SYMBOL_BITS) | $next) >>
                (self::SYMBOL_BITS - self::CODE_EXTRA);
            $this->held = $next;
            $this->value = (($this->value << self::SYMBOL_BITS) +
                (self::SYMBOL_MAX - ($part & self::SYMBOL_MAX))) &
                (self::CODE_TOP - 1);
        }
    }
    /**
     * decode says whereabouts in the range the next number falls, without yet
     * narrowing the range to it. What comes back is compared against the
     * writer's table of likelihoods to find which number it was.
     *
     * @param int $total the sum of how likely every possible number was
     * @return int where in that total the next number falls
     */
    public function decode($total)
    {
        $this->step = intdiv($this->range, $total);
        $found = intdiv($this->value, $this->step);
        $reached = $found + 1;
        if ($reached > $total) {
            $reached = $total;
        }
        return $total - $reached;
    }
    /**
     * update narrows the range to the number just found, now that the caller
     * has looked it up and can say which stretch of the total it took
     *
     * @param int $low where that number's stretch of the total begins
     * @param int $high where that stretch ends
     * @param int $total the sum of how likely every possible number was
     */
    public function update($low, $high, $total)
    {
        $above = $this->step * ($total - $high);
        $this->value -= $above;
        if ($low > 0) {
            $this->range = $this->step * ($high - $low);
        } else {
            $this->range -= $above;
        }
        $this->widen();
    }
    /**
     * decodeFromTable reads one number whose likelihoods are given as a table
     * counting downwards from the total
     *
     * @param array $table how likely each number was, counting down
     * @param int $shift how many bits the likelihoods add up to
     * @return int which number was stored
     */
    public function decodeFromTable($table, $shift)
    {
        $range = $this->range;
        $value = $this->value;
        $part = $range >> $shift;
        $found = -1;
        $above = $range;
        do {
            $above = $range;
            $found++;
            $range = $part * $table[$found];
        } while ($value < $range);
        $this->value = $value - $range;
        $this->range = $above - $range;
        $this->widen();
        return $found;
    }
    /**
     * decodeBit reads one yes or no whose chance of being yes was one in a
     * power of two one chance in eight
     *
     * @param int $shift which power of two, so a shift of three means
     * @return int one for yes, zero for no
     */
    public function decodeBit($shift)
    {
        $range = $this->range;
        $value = $this->value;
        $part = $range >> $shift;
        $answer = ($value < $part) ? 1 : 0;
        if ($answer == 0) {
            $this->value = $value - $part;
            $this->range = $range - $part;
        } else {
            $this->range = $part;
        }
        $this->widen();
        return $answer;
    }
    /**
     * decodeRawBits reads a run of bits that were written as they are rather
     * than by how likely they were. These come from the far end of the piece,
     * working backwards.
     *
     * @param int $count how many bits to read
     * @return int the bits read, as a number
     */
    public function decodeRawBits($count)
    {
        $window = $this->window;
        $available = $this->window_bits;
        if ($available < $count) {
            do {
                $window |= $this->readByteFromBack() << $available;
                $available += self::SYMBOL_BITS;
            } while ($available <= self::WINDOW_SIZE - self::SYMBOL_BITS);
        }
        $answer = $window & ((1 << $count) - 1);
        $this->window = $window >> $count;
        $this->window_bits = $available - $count;
        $this->bits_used += $count;
        return $answer;
    }
    /**
     * decodeNumber reads a number that could have been anything from zero up to
     * a limit, every value having been as likely as every other
     *
     * @param int $limit one past the largest the number could be
     * @return int the number stored
     */
    public function decodeNumber($limit)
    {
        $limit--;
        $width = self::bitCount($limit);
        if ($width > self::UINT_BITS) {
            $width -= self::UINT_BITS;
            $coarse = ($limit >> $width) + 1;
            $found = $this->decode($coarse);
            $this->update($found, $found + 1, $coarse);
            $answer = ($found << $width) | $this->decodeRawBits($width);
            if ($answer <= $limit) {
                return $answer;
            }
            return $limit;
        }
        $found = $this->decode($limit + 1);
        $this->update($found, $found + 1, $limit + 1);
        return $found;
    }
    /**
     * bitCount how many bits it takes to write a number down
     *
     * @param int $value the number to measure
     * @return int how many bits it takes
     */
    public static function bitCount($value)
    {
        $count = 0;
        while ($value > 0) {
            $count++;
            $value >>= 1;
        }
        return $count;
    }
    /**
     * decodeBinary reads one number where every value was as likely as every
     * other and there were a power of two of them. This is the same as reading
     * a number by likelihood with a flat set of likelihoods, written out
     * separately because it comes up often enough for the saving to matter.
     *
     * @param int $bits how many bits the number takes
     * @return int where in the range the next number falls
     */
    public function decodeBinary($bits)
    {
        $this->step = $this->range >> $bits;
        $found = intdiv($this->value, $this->step);
        $limit = 1 << $bits;
        $reached = $found + 1;
        if ($reached > $limit) {
            $reached = $limit;
        }
        return $limit - $reached;
    }
    /**
     * PART_EDGES is how the width of the range between two whole bits is turned
     * into eighths of a bit, so that room can be counted more finely than a
     * whole bit allows.
     */
    const PART_EDGES = [35733, 38967, 42495, 46340, 50535, 55109, 60097,
        65535];
    /**
     * bitsUsedFinely how many bits have been accounted for, counted in eighths.
     * Some of the decisions about what to read next turn on amounts smaller
     * than a whole bit, so counting in whole bits would put the reader out of
     * step with the writer. This works the fraction out from how much of the
     * range is left.
     *
     * @return int how many bits have been accounted for, times eight
     */
    public function bitsUsedFinely()
    {
        $whole = $this->bits_used << 3;
        $width = self::bitCount($this->range);
        $scaled = $this->range >> ($width - 16);
        $part = ($scaled >> 12) - 8;
        if ($scaled > self::PART_EDGES[$part]) {
            $part++;
        }
        return $whole - (($width << 3) + $part);
    }
    /**
     * bitsUsed how many bits of the piece have been accounted for so far.
     * Reading does not use up whole bits, so this is how many bits the numbers
     * read would have cost had they been written out one bit at a time. The
     * decoder uses it to decide how much room is left, which changes what it
     * reads next, so it has to come out the same here as it did when the
     * recording was written.
     *
     * @return int how many bits have been accounted for
     */
    public function bitsUsed()
    {
        return $this->bits_used - self::bitCount($this->range);
    }
}
