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