<?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;
/**
* 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()
{
/* The writer used to check the reader is test support rather
than library code, so Yioop does not find it by itself and
it is named here. */
if (!class_exists("seekquarry\\yioop\\tests\\RangeEncoder")) {
require_once C\PARENT_DIR . "/tests/test_files/RangeEncoder.php";
}
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 = sys_get_temp_dir() . "/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");
}
}
(c) 2026 Seekquarry - Open Source Search Engine Software