<?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\CeltBands;
use seekquarry\yioop\library\av_processing\CeltPulseCache;
use seekquarry\yioop\library\av_processing\Pvq;
use seekquarry\yioop\library\UnitTest;
/**
* Checks what a band's shape is reckoned to cost, and how much shape a
* given amount of room buys.
*
* These two answers decide how the bits are shared out between bands,
* so the reader has to reach the same numbers the writer did. Getting
* one wrong does not spoil a band on its own: it changes how much room
* that band was thought to have, which changes what is left for every
* band after it, so the whole stretch comes apart.
*
* The costs are not stored as a table here. They follow from how many
* shapes a band of a given width has, which is worked out elsewhere.
* That makes them checkable in a way a copied table would not be: the
* reference implementation ships the same costs as a list of numbers,
* that list sits under test_files, and the first case below works the
* whole thing out from scratch and compares. Three hundred and ninety
* two costs and a hundred and five places have to agree exactly.
*
* @author Chris Pollett
*/
class CeltPulseCacheTest extends UnitTest
{
/**
* Where the reference costs sit
*/
const REFERENCE = "/test_files/pulse_cache_reference.json";
/**
* The longest stretch, which nearly every recording uses
*/
const USUAL_DOUBLINGS = 3;
/**
* How finely costs are counted, as parts of a bit
*/
const BIT_PARTS = 3;
/**
* Nothing needs setting up for these cases
*/
public function setUp()
{
}
/**
* Nothing needs clearing away after these cases
*/
public function tearDown()
{
}
/**
* The costs worked out from scratch should match the ones the
* reference implementation ships, both in their values and in
* where each band's list of them begins
*/
public function matchesTheReferenceTestCase()
{
$stored = json_decode(file_get_contents(__DIR__ . self::REFERENCE),
true);
CeltPulseCache::build(self::USUAL_DOUBLINGS);
$mine = [];
foreach (CeltPulseCache::$starts as $row) {
foreach ($row as $where) {
$mine[] = $where;
}
}
$this->assertEqual(count($mine), count($stored["index"]),
"the same number of places");
$this->assertEqual($mine, $stored["index"],
"every band's list begins where the reference says");
$this->assertEqual(count(CeltPulseCache::$costs),
count($stored["bits"]), "the same number of costs");
$this->assertEqual(CeltPulseCache::$costs, $stored["bits"],
"every cost matches the reference");
}
/**
* The highest useful rate for each band, worked out from scratch,
* should match the one the reference implementation ships.
*
* That rate is where a band stops gaining anything from more room.
* The sharing needs it, because without it bits are poured into a
* band that cannot spend them while a band that could goes short.
*/
public function ceilingsMatchTheReferenceTestCase()
{
$stored = json_decode(file_get_contents(__DIR__ . self::REFERENCE),
true);
CeltPulseCache::buildCeilings(self::USUAL_DOUBLINGS);
$mine = [];
for ($doublings = 0; $doublings <= self::USUAL_DOUBLINGS;
$doublings++) {
for ($channels = 1; $channels <= 2; $channels++) {
for ($band = 0; $band < CeltBands::BAND_COUNT; $band++) {
$mine[] = CeltPulseCache::$ceilings[$doublings][$channels]
[$band];
}
}
}
$this->assertEqual(count($mine), count($stored["caps"]),
"the same number of rates");
$this->assertEqual($mine, $stored["caps"],
"every highest useful rate matches the reference");
}
/**
* A wider band should be able to use more room than a narrow one,
* since it has more slots to spend it on
*/
public function widerBandsCanUseMoreTestCase()
{
$narrow = CeltPulseCache::ceilingRoom(0, self::USUAL_DOUBLINGS, 1);
$wide = CeltPulseCache::ceilingRoom(20, self::USUAL_DOUBLINGS, 1);
$this->assertTrue($wide > $narrow * 4,
"the top band can use far more room than the bottom one");
$this->assertTrue(CeltPulseCache::ceilingRoom(10,
self::USUAL_DOUBLINGS, 2) > CeltPulseCache::ceilingRoom(10,
self::USUAL_DOUBLINGS, 1),
"two channels can use more room than one");
}
/**
* The offered pulse counts should rise one at a time at first and
* then in widening steps, so that a band with little room gets
* fine choices and one with plenty is not given more than it can
* use
*/
public function offersWidenAsTheyRiseTestCase()
{
for ($offer = 0; $offer < 8; $offer++) {
$this->assertEqual(CeltPulseCache::pulsesAt($offer), $offer,
"the first offers rise one pulse at a time");
}
$rising = true;
$widening = true;
$gap = 1;
for ($offer = 1; $offer <= CeltPulseCache::MOST_STEPS; $offer++) {
$step = CeltPulseCache::pulsesAt($offer) -
CeltPulseCache::pulsesAt($offer - 1);
if ($step <= 0) {
$rising = false;
}
if ($step < $gap) {
$widening = false;
}
$gap = $step;
}
$this->assertTrue($rising, "every offer is more than the last");
$this->assertTrue($widening, "the steps never narrow");
}
/**
* More pulses should always cost more room, since a shape with
* more pulses is one of more shapes
*/
public function morePulsesCostMoreTestCase()
{
$wrong = 0;
$checked = 0;
for ($band = 0; $band < CeltBands::BAND_COUNT; $band++) {
$most = CeltPulseCache::offerCount($band, self::USUAL_DOUBLINGS);
$before = 0;
for ($offer = 1; $offer <= $most; $offer++) {
$room = CeltPulseCache::roomFor($band, self::USUAL_DOUBLINGS,
$offer);
if ($room <= $before) {
$wrong++;
}
$before = $room;
$checked++;
}
}
$this->assertTrue($checked > 200, "many costs were checked");
$this->assertEqual($wrong, 0, "every offer costs more than the last");
}
/**
* Asking what a given amount of room buys, and then asking what
* that costs, should lead back to the same offer
*/
public function roomAndOfferAgreeTestCase()
{
$wrong = 0;
$checked = 0;
for ($band = 0; $band < CeltBands::BAND_COUNT; $band++) {
$most = CeltPulseCache::offerCount($band, self::USUAL_DOUBLINGS);
for ($offer = 1; $offer <= $most; $offer++) {
$room = CeltPulseCache::roomFor($band, self::USUAL_DOUBLINGS,
$offer);
if (CeltPulseCache::offerWithin($band, self::USUAL_DOUBLINGS,
$room) != $offer) {
$wrong++;
}
$checked++;
}
}
$this->assertTrue($checked > 200, "many offers were checked");
$this->assertEqual($wrong, 0,
"what an offer costs buys that offer back");
}
/**
* More room should never buy less shape
*/
public function moreRoomNeverBuysLessTestCase()
{
$wrong = 0;
for ($band = 0; $band < CeltBands::BAND_COUNT; $band++) {
$before = -1;
for ($room = 0; $room < 200; $room += 3) {
$offer = CeltPulseCache::offerWithin($band,
self::USUAL_DOUBLINGS, $room);
if ($offer < $before) {
$wrong++;
}
$before = $offer;
}
}
$this->assertEqual($wrong, 0, "more room never buys less shape");
}
/**
* A band with no room at all should be given no pulses, and one
* with a great deal should be capped at what is on offer
*/
public function bothEndsOfTheRangeTestCase()
{
$band = 10;
$this->assertEqual(CeltPulseCache::roomFor($band,
self::USUAL_DOUBLINGS, 0), 0, "no pulses take no room");
$most = CeltPulseCache::offerCount($band, self::USUAL_DOUBLINGS);
$this->assertEqual(CeltPulseCache::offerWithin($band,
self::USUAL_DOUBLINGS, 100000), $most,
"more room than there are offers buys the largest offer");
}
/**
* The logarithm counted in parts of a bit should be exact for
* powers of two and should sit close to the true logarithm
* elsewhere
*/
public function logarithmIsRightTestCase()
{
foreach ([1, 2, 4, 8, 1024, 65536] as $value) {
$whole = (int)round(log($value, 2));
$this->assertEqual(CeltPulseCache::logInParts($value,
self::BIT_PARTS), $whole << self::BIT_PARTS,
"a power of two has an exact logarithm");
}
$worst = 0.0;
foreach ([3, 7, 100, 12345, 1000000, 4000000000] as $value) {
$parts = CeltPulseCache::logInParts($value, self::BIT_PARTS);
$true_log = log($value, 2) * (1 << self::BIT_PARTS);
/* The working rounds up, so the answer sits at or just
above the true logarithm, never below. */
$this->assertTrue($parts >= floor($true_log),
"the logarithm of $value is not rounded down");
$worst = max($worst, abs($parts - $true_log));
}
$this->assertTrue($worst < 2.0,
"the logarithm never strays far from the true one");
}
/**
* The costs should follow from how many shapes a band has, which
* is what makes them computable rather than a table to be copied
*/
public function costsFollowFromTheShapeCountTestCase()
{
$band = 8;
$width = CeltPulseCache::halfWidth($band, self::USUAL_DOUBLINGS + 1);
$wrong = 0;
for ($offer = 1; $offer <= 6; $offer++) {
$shapes = Pvq::patternCount($width,
CeltPulseCache::pulsesAt($offer));
$expected = CeltPulseCache::logInParts($shapes, self::BIT_PARTS);
if (CeltPulseCache::roomFor($band, self::USUAL_DOUBLINGS,
$offer) != $expected) {
$wrong++;
}
}
$this->assertEqual($wrong, 0,
"each cost is the logarithm of how many shapes there are");
}
}
(c) 2026 Seekquarry - Open Source Search Engine Software