<?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\OggDemuxer;
use seekquarry\yioop\library\av_processing\OpusPacket;
use seekquarry\yioop\library\av_processing\RangeDecoder;
use seekquarry\yioop\configs as C;
use seekquarry\yioop\library\UnitTest;
use seekquarry\yioop\library\av_processing\Laplace;
/**
* Checks that the reader of Opus's compressed numbers gives back
* exactly what was put in.
*
* Nothing else about a recording can be read until this can, and a
* single wrong step makes everything after it meaningless rather than
* merely wrong, so this is checked harder than the parts around it. The
* cases put long runs of numbers in and take them out again, including
* the two arrangements that are easy to get wrong: a run of bytes of
* all ones, where a carry has to ripple back through bytes already
* written, and a piece written from both ends at once, where the two
* ends have to meet without treading on each other.
*
* The last case takes real recordings and reads the opening of every
* piece in them, which is a check the round trip cannot give: it says
* the reader agrees with software that had no sight of it.
*
* @author Chris Pollett
*/
class RangeDecoderTest extends UnitTest
{
/**
* How many bytes to give a written piece in these cases
*/
const ROOM = 4000;
/**
* How many numbers to put in and take out in the longer cases
*/
const RUN_LENGTH = 400;
/**
* A starting point for the made up numbers, so a failing case
* fails the same way every time it is run
*/
const SEED = 20260803;
/**
* Where the quarter second recordings sit
*/
const RECORDINGS = ["/test_files/tiny_recording_ogg.txt",
"/test_files/tiny_recording_webm.txt"];
/**
* Sets the made up numbers off from the same place every run
*/
public function setUp()
{
mt_srand(self::SEED);
}
/**
* Nothing needs clearing away after these cases
*/
public function tearDown()
{
}
/**
* A run of numbers written by likelihood should come back in the
* same order with the same values
*/
public function numbersByLikelihoodTestCase()
{
$total = 64;
$written = [];
$writer = new RangeEncoder(self::ROOM);
for ($i = 0; $i < self::RUN_LENGTH; $i++) {
$which = mt_rand(0, $total - 1);
$written[] = $which;
$writer->encode($which, $which + 1, $total);
}
$piece = $writer->finish();
$this->assertFalse($writer->overflowed, "the piece had room");
$reader = new RangeDecoder($piece);
$matched = 0;
for ($i = 0; $i < self::RUN_LENGTH; $i++) {
$found = $reader->decode($total);
$reader->update($found, $found + 1, $total);
if ($found == $written[$i]) {
$matched++;
}
}
$this->assertEqual($matched, self::RUN_LENGTH,
"every number came back as it went in");
}
/**
* Numbers of very different likelihoods should still come back
* correctly, and a likely number should cost far less room than an
* unlikely one
*/
public function unevenLikelihoodsTestCase()
{
$total = 1024;
$common_end = 1000;
$writer = new RangeEncoder(self::ROOM);
for ($i = 0; $i < self::RUN_LENGTH; $i++) {
$writer->encode(0, $common_end, $total);
}
$likely_size = strlen(rtrim($writer->finish(), "\0"));
$writer = new RangeEncoder(self::ROOM);
for ($i = 0; $i < self::RUN_LENGTH; $i++) {
$writer->encode($common_end, $total, $total);
}
$unlikely_size = strlen(rtrim($writer->finish(), "\0"));
$this->assertTrue($unlikely_size > $likely_size * 4,
"an unlikely number costs much more room than a likely one");
$writer = new RangeEncoder(self::ROOM);
$written = [];
for ($i = 0; $i < self::RUN_LENGTH; $i++) {
$rare = (mt_rand(0, 99) == 0);
$written[] = $rare;
if ($rare) {
$writer->encode($common_end, $total, $total);
} else {
$writer->encode(0, $common_end, $total);
}
}
$reader = new RangeDecoder($writer->finish());
$matched = 0;
for ($i = 0; $i < self::RUN_LENGTH; $i++) {
$found = $reader->decode($total);
$was_rare = ($found >= $common_end);
if ($was_rare) {
$reader->update($common_end, $total, $total);
} else {
$reader->update(0, $common_end, $total);
}
if ($was_rare == $written[$i]) {
$matched++;
}
}
$this->assertEqual($matched, self::RUN_LENGTH,
"a mix of likely and unlikely numbers came back right");
}
/**
* Numbers written from a table of likelihoods counting downwards
* should come back the same way
*/
public function numbersFromTableTestCase()
{
$table = [200, 150, 90, 40, 10, 0];
$shift = 8;
$written = [];
$writer = new RangeEncoder(self::ROOM);
for ($i = 0; $i < self::RUN_LENGTH; $i++) {
$which = mt_rand(0, count($table) - 1);
$written[] = $which;
$writer->encodeFromTable($which, $table, $shift);
}
$reader = new RangeDecoder($writer->finish());
$matched = 0;
for ($i = 0; $i < self::RUN_LENGTH; $i++) {
if ($reader->decodeFromTable($table, $shift) == $written[$i]) {
$matched++;
}
}
$this->assertEqual($matched, self::RUN_LENGTH,
"every number from the table came back as it went in");
}
/**
* Yes and no answers of a given chance should come back the same
* way
*/
public function yesNoAnswersTestCase()
{
$shift = 3;
$written = [];
$writer = new RangeEncoder(self::ROOM);
for ($i = 0; $i < self::RUN_LENGTH; $i++) {
$answer = (mt_rand(0, 7) == 0) ? 1 : 0;
$written[] = $answer;
$writer->encodeBit($answer, $shift);
}
$reader = new RangeDecoder($writer->finish());
$matched = 0;
for ($i = 0; $i < self::RUN_LENGTH; $i++) {
if ($reader->decodeBit($shift) == $written[$i]) {
$matched++;
}
}
$this->assertEqual($matched, self::RUN_LENGTH,
"every answer came back as it went in");
}
/**
* Values written as they are go at the far end of the piece and
* come back from there, so a piece holding both kinds is read from
* both ends at once and the two must not tread on each other
*/
public function bothEndsAtOnceTestCase()
{
$total = 32;
$raw_width = 7;
$by_likelihood = [];
$as_they_are = [];
$writer = new RangeEncoder(self::ROOM);
for ($i = 0; $i < self::RUN_LENGTH; $i++) {
$which = mt_rand(0, $total - 1);
$plain = mt_rand(0, (1 << $raw_width) - 1);
$by_likelihood[] = $which;
$as_they_are[] = $plain;
$writer->encode($which, $which + 1, $total);
$writer->encodeRawBits($plain, $raw_width);
}
$piece = $writer->finish();
$this->assertFalse($writer->overflowed, "the piece had room");
$reader = new RangeDecoder($piece);
$matched = 0;
$plain_matched = 0;
for ($i = 0; $i < self::RUN_LENGTH; $i++) {
$found = $reader->decode($total);
$reader->update($found, $found + 1, $total);
if ($found == $by_likelihood[$i]) {
$matched++;
}
if ($reader->decodeRawBits($raw_width) == $as_they_are[$i]) {
$plain_matched++;
}
}
$this->assertEqual($matched, self::RUN_LENGTH,
"the numbers read from the front all came back");
$this->assertEqual($plain_matched, self::RUN_LENGTH,
"the values read from the back all came back");
}
/**
* A long run of the most likely number makes the writer produce
* bytes of all ones, and a later number can carry into them, which
* has to ripple back through bytes already written
*/
public function carryRipplesBackTestCase()
{
$total = 4096;
$writer = new RangeEncoder(self::ROOM);
/* Choosing the top of the range over and over drives the
written bytes towards all ones, which is what leaves a carry
with somewhere to ripple. */
for ($i = 0; $i < 60; $i++) {
$writer->encode($total - 1, $total, $total);
}
for ($i = 0; $i < 20; $i++) {
$writer->encode(0, 1, $total);
}
$piece = $writer->finish();
$reader = new RangeDecoder($piece);
$matched = 0;
for ($i = 0; $i < 60; $i++) {
$found = $reader->decode($total);
$reader->update($total - 1, $total, $total);
if ($found == $total - 1) {
$matched++;
}
}
for ($i = 0; $i < 20; $i++) {
$found = $reader->decode($total);
$reader->update(0, 1, $total);
if ($found == 0) {
$matched++;
}
}
$this->assertEqual($matched, 80,
"the carry rippled back without disturbing what it passed");
}
/**
* Numbers where every value was as likely as every other should
* come back the same, at both the narrow and the wide sizes, since
* a wide one is written in two parts
*/
public function evenlyLikelyNumbersTestCase()
{
$limits = [2, 17, 256, 257, 1000, 65536];
$matched = 0;
$tried = 0;
foreach ($limits as $limit) {
$written = [];
$writer = new RangeEncoder(self::ROOM);
for ($i = 0; $i < 50; $i++) {
$value = mt_rand(0, $limit - 1);
$written[] = $value;
$writer->encodeNumber($value, $limit);
}
$reader = new RangeDecoder($writer->finish());
for ($i = 0; $i < 50; $i++) {
$tried++;
if ($reader->decodeNumber($limit) == $written[$i]) {
$matched++;
}
}
}
$this->assertEqual($matched, $tried,
"every evenly likely number came back at every size tried");
}
/**
* A piece cut short should be read without complaint rather than
* running off the end, since a damaged recording should give up
* what it can
*/
public function shortPieceIsReadSafelyTestCase()
{
$total = 16;
$writer = new RangeEncoder(self::ROOM);
for ($i = 0; $i < 100; $i++) {
$writer->encode(3, 4, $total);
}
$piece = substr($writer->finish(), 0, 6);
$reader = new RangeDecoder($piece);
$ran = 0;
for ($i = 0; $i < 200; $i++) {
$found = $reader->decode($total);
$reader->update($found, $found + 1, $total);
$ran++;
}
$this->assertEqual($ran, 200,
"reading past the end of a cut piece does not fall over");
}
/**
* Reading the opening of every piece in two real recordings should
* run through without the reader losing its place, which says it
* agrees with software that never saw it
*/
public function realRecordingsAreReadTestCase()
{
$pieces = [];
$stored = file_get_contents(C\PARENT_DIR .
"/tests" . self::RECORDINGS[0]);
$name = C\TEST_DIR . "/test_files/range_decoder_test.ogg";
file_put_contents($name, base64_decode($stored));
$reader = OggDemuxer::fromName($name);
foreach ($reader->packets() as $piece) {
if (strncmp($piece->data, "Opus", 4) != 0) {
$pieces[] = $piece->data;
}
}
unlink($name);
$this->assertTrue(count($pieces) > 5, "there were pieces to read");
$read = 0;
$all_in_range = true;
foreach ($pieces as $piece) {
$opus = OpusPacket::fromString($piece);
foreach ($opus->stretches as $stretch) {
if (strlen($stretch) < 2) {
continue;
}
$entropy = new RangeDecoder($stretch);
/* The reader must always leave its range in the band it
is defined over. A reader that has lost its place
leaves it outside that band, so checking it after a
run of reads catches a fault without needing to know
what the numbers meant. */
for ($i = 0; $i < 16; $i++) {
$entropy->decodeBit(1);
if ($entropy->range <= RangeDecoder::CODE_BOTTOM ||
$entropy->range > 0xFFFFFFFF) {
$all_in_range = false;
}
if ($entropy->value >= $entropy->range) {
$all_in_range = false;
}
}
$read++;
}
}
$this->assertTrue($read > 5, "stretches of real sound were read");
$this->assertTrue($all_in_range,
"the reader kept its place through every stretch");
}
}
/**
* RangeEncoder writes numbers in the range coding an Opus recording uses,
* the opposite of what RangeDecoder reads. Yioop only reads Opus, so only
* tests use it: RangeDecoderTest, LaplaceTest, CeltEnergyTest,
* CeltShapeTest and PvqTest write numbers with it and check that the
* library's readers give the same numbers back. It is kept in this file
* with RangeDecoderTest, its main user.
*
* @author Chris Pollett
*/
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;
}
/**
* encodeLaplace writes $value with the Laplace shape that Opus uses for
* the coarse loudness of a band, the opposite of what Laplace::read
* reads. A value too far from zero for the shape to hold is written
* as the nearest one it can hold, and that value is returned, so a
* check compares what is read back against what was written.
*
* @param int $value the number to write
* @param int $zero_chance the share of the whole the value zero takes
* @param int $fall how fast the share falls away each step from zero
* @return int the value written
*/
public function encodeLaplace($value, $zero_chance, $fall)
{
$below = 0;
$chance = $zero_chance;
$stored = $value;
if ($value != 0) {
$negative = ($value < 0);
$size = abs($value);
$below = $chance;
$chance = Laplace::firstStepChance($chance, $fall);
$steps = 1;
while ($chance > 0 && $steps < $size) {
$chance *= 2;
$below += $chance + 2 * Laplace::SMALLEST_CHANCE;
$chance = ($chance * $fall) >> 15;
$steps++;
}
if ($chance == 0) {
$room = (Laplace::WHOLE - $below + Laplace::SMALLEST_CHANCE
- 1) >> 0;
$room = ($room - ($negative ? -1 : 0)) >> 1;
$further = min($size - $steps, $room - 1);
$below += (2 * $further + 1 + ($negative ? -1 : 0)) *
Laplace::SMALLEST_CHANCE;
$chance = min(Laplace::SMALLEST_CHANCE,
Laplace::WHOLE - $below);
$settled = $steps + $further;
$stored = $negative ? -$settled : $settled;
} else {
$chance += Laplace::SMALLEST_CHANCE;
if (!$negative) {
$below += $chance;
}
}
}
$this->encodeBinary($below, $below + $chance, Laplace::WHOLE_BITS);
return $stored;
}
}
- Yioop Repo - Seekquarry