<?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\av_processing\RangeDecoder;
/**
* Writes numbers the way an Opus recording stores them, so that what
* the reader gets back can be checked against what was put in.
*
* This exists to check RangeDecoder and is not used to make
* recordings. Turning a recording into an mp4 only ever reads Opus, so
* nothing outside the tests needs to write it. It sits here rather than
* in the library for that reason.
*
* A reader and a writer built by the same hand can agree with each
* other and still both be wrong, so this is not the only check on the
* reader. It is the check that covers the awkward parts: the carry
* that ripples back through bytes already written, and the two ends of
* a piece meeting in the middle. Those are hard to reach with a
* recording made by other software, because a recording that exercises
* them cannot be asked for on purpose.
*/
class RangeEncoder
{
/**
* The bytes written so far
* @var array
*/
public $bytes;
/**
* How many bytes the piece may hold
* @var int
*/
public $capacity;
/**
* How far in from the front the write has got
* @var int
*/
public $front;
/**
* How far in from the back the write has got
* @var int
*/
public $back;
/**
* The bottom of the range still being narrowed
* @var int
*/
public $low;
/**
* How wide the range currently is
* @var int
*/
public $range;
/**
* A byte written but not yet settled, because a later carry may
* still change it. Minus one where there is none.
* @var int
*/
public $held;
/**
* How many bytes of all ones are waiting behind the held byte, any
* of which a carry would turn over
* @var int
*/
public $waiting;
/**
* Bits written as they are, not yet put into a byte
* @var int
*/
public $window;
/**
* How many bits the store above holds
* @var int
*/
public $window_bits;
/**
* Whether the piece ran out of room
* @var bool
*/
public $overflowed;
/**
* Sets up a write of a piece of a given size
*
* @param int $capacity how many bytes the piece may hold
*/
public function __construct($capacity)
{
$this->capacity = $capacity;
$this->bytes = array_fill(0, $capacity, 0);
$this->front = 0;
$this->back = 0;
$this->low = 0;
$this->range = RangeDecoder::CODE_TOP;
$this->held = -1;
$this->waiting = 0;
$this->window = 0;
$this->window_bits = 0;
$this->overflowed = false;
}
/**
* Puts a byte at the front of the piece
*
* @param int $byte the byte to write
*/
public function writeByte($byte)
{
if ($this->front + $this->back >= $this->capacity) {
$this->overflowed = true;
return;
}
$this->bytes[$this->front] = $byte & RangeDecoder::SYMBOL_MAX;
$this->front++;
}
/**
* Puts a byte at the back of the piece, where values written as
* they are go
*
* @param int $byte the byte to write
*/
public function writeByteAtBack($byte)
{
if ($this->front + $this->back >= $this->capacity) {
$this->overflowed = true;
return;
}
$this->back++;
$this->bytes[$this->capacity - $this->back] =
$byte & RangeDecoder::SYMBOL_MAX;
}
/**
* Settles the byte that was being held, turning over any bytes of
* all ones behind it if this one carried
*
* @param int $carry the byte to settle, which may be one too large
* and so carry into the byte before it
*/
public function carryOut($carry)
{
if ($carry != RangeDecoder::SYMBOL_MAX) {
$bump = $carry >> RangeDecoder::SYMBOL_BITS;
if ($this->held >= 0) {
$this->writeByte($this->held + $bump);
}
/* Bytes of all ones could not be settled while a carry
might still turn them over, so they were counted rather
than written. Now that the carry is known they can go
out. */
while ($this->waiting > 0) {
$this->writeByte((RangeDecoder::SYMBOL_MAX + $bump) &
RangeDecoder::SYMBOL_MAX);
$this->waiting--;
}
$this->held = $carry & RangeDecoder::SYMBOL_MAX;
} else {
$this->waiting++;
}
}
/**
* Settles bytes until the range is wide enough to go on writing
* numbers into it
*/
public function narrow()
{
while ($this->range <= RangeDecoder::CODE_BOTTOM) {
$this->carryOut($this->low >> RangeDecoder::CODE_SHIFT);
$this->low = ($this->low << RangeDecoder::SYMBOL_BITS) &
(RangeDecoder::CODE_TOP - 1);
$this->range = ($this->range << RangeDecoder::SYMBOL_BITS) &
0xFFFFFFFF;
}
}
/**
* Writes one number by narrowing the range to the stretch of the
* total that number stands for
*
* @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 encode($low, $high, $total)
{
$part = intdiv($this->range, $total);
if ($low > 0) {
$this->low += $this->range - $part * ($total - $low);
$this->range = $part * ($high - $low);
} else {
$this->range -= $part * ($total - $high);
}
$this->narrow();
}
/**
* Writes one number whose likelihoods are given as a table
* counting downwards from the total
*
* @param int $which which number to write
* @param array $table how likely each number was, counting down
* @param int $shift how many bits the likelihoods add up to
*/
public function encodeFromTable($which, $table, $shift)
{
$part = $this->range >> $shift;
if ($which > 0) {
$this->low += $this->range - $part * $table[$which - 1];
$this->range = $part * ($table[$which - 1] - $table[$which]);
} else {
$this->range -= $part * $table[$which];
}
$this->narrow();
}
/**
* Writes one number where every value was as likely as every other
* and there were a power of two of them
*
* @param int $low where that number's stretch of the whole begins
* @param int $high where that stretch ends
* @param int $bits how many bits the number takes
*/
public function encodeBinary($low, $high, $bits)
{
$part = $this->range >> $bits;
$whole = 1 << $bits;
if ($low > 0) {
$this->low += $this->range - $part * ($whole - $low);
$this->range = $part * ($high - $low);
} else {
$this->range -= $part * ($whole - $high);
}
$this->narrow();
}
/**
* Writes one yes or no whose chance of being yes was one in a
* power of two
*
* @param int $answer one for yes, zero for no
* @param int $shift which power of two
*/
public function encodeBit($answer, $shift)
{
$range = $this->range;
$low = $this->low;
$part = $range >> $shift;
$range -= $part;
if ($answer != 0) {
$this->low = $low + $range;
$this->range = $part;
} else {
$this->range = $range;
}
$this->narrow();
}
/**
* Writes a run of bits as they are rather than by how likely they
* were. These go at the far end of the piece, working backwards.
*
* @param int $value the bits to write, as a number
* @param int $count how many bits to write
*/
public function encodeRawBits($value, $count)
{
$window = $this->window;
$used = $this->window_bits;
if ($used + $count > RangeDecoder::WINDOW_SIZE) {
do {
$this->writeByteAtBack($window & RangeDecoder::SYMBOL_MAX);
$window >>= RangeDecoder::SYMBOL_BITS;
$used -= RangeDecoder::SYMBOL_BITS;
} while ($used >= RangeDecoder::SYMBOL_BITS);
}
$this->window = $window | ($value << $used);
$this->window_bits = $used + $count;
}
/**
* Writes a number that could have been anything from zero up to a
* limit, every value as likely as every other
*
* @param int $value the number to write
* @param int $limit one past the largest it could be
*/
public function encodeNumber($value, $limit)
{
$limit--;
$width = RangeDecoder::bitCount($limit);
if ($width > RangeDecoder::UINT_BITS) {
$width -= RangeDecoder::UINT_BITS;
$coarse = ($limit >> $width) + 1;
$high = $value >> $width;
$this->encode($high, $high + 1, $coarse);
$this->encodeRawBits($value & ((1 << $width) - 1), $width);
} else {
$this->encode($value, $value + 1, $limit + 1);
}
}
/**
* Closes the piece off, settling every byte still held and putting
* the bits written as they are into the far end
*
* @return string the finished piece
*/
public function finish()
{
$left = RangeDecoder::CODE_BITS - RangeDecoder::bitCount($this->range);
$mask = (RangeDecoder::CODE_TOP - 1) >> $left;
$end = ($this->low + $mask) & ~$mask;
/* The piece only has to say enough to pin the range down. Where
rounding up would carry past what the range allows, one more
bit is given and the rounding tried again. */
if (($end | $mask) >= $this->low + $this->range) {
$left++;
$mask >>= 1;
$end = ($this->low + $mask) & ~$mask;
}
while ($left > 0) {
$this->carryOut(($end >> RangeDecoder::CODE_SHIFT) & 0x1FF);
$end = ($end << RangeDecoder::SYMBOL_BITS) &
(RangeDecoder::CODE_TOP - 1);
$left -= RangeDecoder::SYMBOL_BITS;
}
if ($this->held >= 0 || $this->waiting > 0) {
$this->carryOut(0);
}
$window = $this->window;
$used = $this->window_bits;
while ($used >= RangeDecoder::SYMBOL_BITS) {
$this->writeByteAtBack($window & RangeDecoder::SYMBOL_MAX);
$window >>= RangeDecoder::SYMBOL_BITS;
$used -= RangeDecoder::SYMBOL_BITS;
}
for ($i = $this->front; $i < $this->capacity - $this->back; $i++) {
$this->bytes[$i] = 0;
}
if ($used > 0 && $this->back < $this->capacity) {
$this->bytes[$this->capacity - $this->back - 1] |= $window;
}
$piece = "";
for ($i = 0; $i < $this->capacity; $i++) {
$piece .= chr($this->bytes[$i]);
}
return $piece;
}
}
(c) 2026 Seekquarry - Open Source Search Engine Software