<?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;
/**
* CeltPulseCache says what a band's shape costs to store, and how much shape a
* given amount of room will buy. Sharing the bits out between bands needs both
* answers, over and over. A band's shape is stored as a pattern of pulses, and
* the cost of a pattern is the logarithm of how many patterns there are to
* choose from. Working that out from scratch each time would be slow, and it
* has to give the same answer as the writer got or the two disagree about how
* much room a band was given. So the costs are worked out once and kept. Not
* every pulse count is offered: they run one at a time up to seven and then in
* widening steps, which is enough resolution to matter while keeping the list
* short. Bands of the same width share one list, and there are far fewer
* distinct widths than there are bands and lengths of stretch. Nothing here is
* stored as a table of numbers. The costs follow from how many patterns a band
* of a given width and pulse count has, which the band shape reader already
* works out. That means the whole list is computed when first wanted, and it
* also means it can be checked against the list the reference implementation
* ships, which is what the test beside this does. This follows RFC 6716, the
* specification of the Opus audio codec, in its section on sharing out the
* bits.
*/
class CeltPulseCache
{
/**
* BIT_PARTS is how finely costs are counted: each whole bit is split into
* this many parts, so that a cost can be carried without rounding away the
* fractions that matter when they are added up.
*/
const BIT_PARTS = 3;
/**
* MOST_STEPS is how many pulse counts are offered at most.
*/
const MOST_STEPS = 40;
/**
* SEARCH_STEPS is how many halvings it takes to search the list of offered
* counts.
*/
const SEARCH_STEPS = 6;
/**
* COUNT_LIMIT is the largest a count worked out here may be before it no
* longer fits where the writer would have kept it.
*/
const COUNT_LIMIT = 4294967295;
/**
* starts stores where each band's list of costs begins, by length of
* stretch and band, worked out once and kept
*
* @var array
*/
public static $starts = [];
/**
* The costs themselves, all bands' lists laid end to end
* @var array
*/
public static $costs = [];
/**
* pulsesAt how many pulses the numbered offer stands for. The offers run
* one at a time up to seven and then widen, so that a band with a little
* room is given fine choices and one with a great deal is not given more
* choices than it can use.
*
* @param int $offer which offer, counting from zero
* @return int how many pulses it stands for
*/
public static function pulsesAt($offer)
{
if ($offer < 8) {
return $offer;
}
return (8 + ($offer & 7)) << (($offer >> 3) - 1);
}
/**
* logInParts the logarithm of a number to base two, counted in parts of a
* bit rather than whole bits, rounded up. Costs have to be carried finely
* because they are added up across twenty one bands, and rounding each to a
* whole bit would lose more than the fractions are worth.
*
* @param int $value the number to take the logarithm of
* @param int $parts how many parts each whole bit is split into
* @return int the logarithm, in parts of a bit
*/
public static function logInParts($value, $parts)
{
$whole = RangeDecoder::bitCount($value);
if (($value & ($value - 1)) == 0) {
/* An exact power of two has an exact logarithm, so none of
the working below is needed. */
return ($whole - 1) << $parts;
}
if ($whole > 16) {
$value = (($value - 1) >> ($whole - 16)) + 1;
} else {
$value <<= 16 - $whole;
}
$total = ($whole - 1) << $parts;
/* Each turn round settles one more part of a bit, by squaring
what is left and taking off whatever whole part that
produced. */
do {
$step = $value >> 16;
$total += $step << $parts;
$value = ($value + $step) >> $step;
$value = ($value * $value + 0x7FFF) >> 15;
$parts--;
} while ($parts >= 0);
return $total + (($value > 0x8000) ? 1 : 0);
}
/**
* build works out the costs for every band at every length of stretch,
* once, and keeps them how many times the shortest has been doubled
*
* @param int $most_doublings the longest stretch to work out, as
*/
public static function build($most_doublings = 3)
{
if (self::$starts != []) {
return;
}
$bands = CeltBands::BAND_COUNT;
$starts = [];
$widths = [];
$offers = [];
$begins = [];
$next = 0;
/* A band is stored in halves when it is split, so the width
that matters is half the band. Many bands share a width once
the lengths of stretch are taken into account, and each
width needs working out only once. */
for ($doublings = 0; $doublings <= $most_doublings + 1; $doublings++) {
for ($band = 0; $band < $bands; $band++) {
$width = self::halfWidth($band, $doublings);
$starts[$doublings][$band] = -1;
$found = false;
for ($seen = 0; $seen <= $doublings && !$found; $seen++) {
for ($other = 0; $other < $bands &&
($seen != $doublings || $other < $band); $other++) {
if ($width == self::halfWidth($other, $seen)) {
$starts[$doublings][$band] =
$starts[$seen][$other];
$found = true;
break;
}
}
}
if ($starts[$doublings][$band] == -1 && $width != 0) {
$most = 0;
while ($most < self::MOST_STEPS &&
Pvq::patternCount($width,
self::pulsesAt($most + 1)) <= self::COUNT_LIMIT) {
$most++;
}
$widths[] = $width;
$offers[] = $most;
$begins[] = $next;
$starts[$doublings][$band] = $next;
$next += $most + 1;
}
}
}
$costs = array_fill(0, $next, 0);
foreach ($widths as $which => $width) {
$most = $offers[$which];
$at = $begins[$which];
/* The first place in a list holds how many offers the list
has, so that a search knows where to stop. */
$costs[$at] = $most;
for ($offer = 1; $offer <= $most; $offer++) {
/* What a shape costs is the logarithm of how many
shapes there were to choose from, less one, since
the writer never spends the last part of a bit. */
$costs[$at + $offer] = self::logInParts(
Pvq::patternCount($width, self::pulsesAt($offer)),
self::BIT_PARTS) - 1;
}
}
self::$starts = $starts;
self::$costs = $costs;
}
/**
* halfWidth half the width of a band, which is the width that matters
* because a band is stored in halves when it is split been doubled
*
* @param int $band which band
* @param int $doublings how many times the shortest stretch has
* @return int half the band's width in slots
*/
public static function halfWidth($band, $doublings)
{
return ((CeltBands::EDGES[$band + 1] - CeltBands::EDGES[$band])
<< $doublings) >> 1;
}
/**
* roomFor how much room a band's shape takes, given how many pulses it
* holds been doubled
*
* @param int $band which band
* @param int $doublings how many times the shortest stretch has
* @param int $offer which of the offered pulse counts
* @return int the room taken, in parts of a bit
*/
public static function roomFor($band, $doublings, $offer)
{
self::build();
if ($offer == 0) {
return 0;
}
$at = self::$starts[$doublings + 1][$band];
return self::$costs[$at + $offer] + 1;
}
/**
* offerWithin which of the offered pulse counts a band can afford, given
* how much room it has been given been doubled
*
* @param int $band which band
* @param int $doublings how many times the shortest stretch has
* @param int $room how much room the band has, in parts of a bit
* @return int which offer it can afford
*/
public static function offerWithin($band, $doublings, $room)
{
self::build();
$at = self::$starts[$doublings + 1][$band];
$low = 0;
$high = self::$costs[$at];
$room--;
/* The list of costs only rises, so the affordable offer is
found by halving the range rather than by walking it. */
for ($step = 0; $step < self::SEARCH_STEPS; $step++) {
$middle = ($low + $high + 1) >> 1;
if (self::$costs[$at + $middle] >= $room) {
$high = $middle;
} else {
$low = $middle;
}
}
/* Both ends of what is left are affordable in the sense that
neither overshoots by much, so the nearer of the two is
taken. */
$under = $room - (($low == 0) ? -1 : self::$costs[$at + $low]);
$over = self::$costs[$at + $high] - $room;
return ($under <= $over) ? $low : $high;
}
/**
* offerCount how many offers a band has to choose from been doubled
*
* @param int $band which band
* @param int $doublings how many times the shortest stretch has
* @return int how many offers there are
*/
public static function offerCount($band, $doublings)
{
self::build();
return self::$costs[self::$starts[$doublings + 1][$band]];
}
/**
* ceilings stores the highest useful rate for each band, by length of
* stretch and channel count, worked out once and kept
*
* @var array
*/
public static $ceilings = [];
/**
* SPLIT_OFFSET is how much finer detail in pitch is favored over detail in
* time.
*/
const SPLIT_OFFSET = 4;
/**
* SPLIT_OFFSET_PAIR is the same, where a band has only two slots and is
* split in a different way.
*/
const SPLIT_OFFSET_PAIR = 16;
/**
* FINE_OFFSET is how much of a band's room the finer loudness pass is
* offered before the rest goes to the shape.
*/
const FINE_OFFSET = 21;
/**
* MOST_FINE_BITS is most bits the finer loudness pass may spend on one
* band.
*/
const MOST_FINE_BITS = 8;
/**
* widthLog the width of a band as a logarithm, which appears throughout the
* ceiling working
*
* @param int $band which band
* @return int the logarithm of the band's width, in parts of a bit
*/
public static function widthLog($band)
{
return self::logInParts(CeltBands::EDGES[$band + 1] -
CeltBands::EDGES[$band], self::BIT_PARTS);
}
/**
* buildCeilings works out the highest rate at which each band can still use
* every bit it is given. Past that rate a band gains nothing from more
* room, so the sharing has to know where it is or it will pour bits into a
* band that cannot spend them while starving one that could. The rate
* follows from what the band's shape costs at its finest, plus what
* splitting the band repeatedly costs, plus what the finer loudness pass
* will take.
*
* @param int $most_doublings the longest stretch to work out
*/
public static function buildCeilings($most_doublings = 3)
{
if (self::$ceilings != []) {
return;
}
self::build($most_doublings);
$ceilings = [];
for ($doublings = 0; $doublings <= $most_doublings; $doublings++) {
for ($channels = 1; $channels <= 2; $channels++) {
for ($band = 0; $band < CeltBands::BAND_COUNT; $band++) {
$ceilings[$doublings][$channels][$band] =
self::ceilingFor($band, $doublings, $channels);
}
}
}
self::$ceilings = $ceilings;
}
/**
* ceilingFor works out one band's highest useful rate been doubled
*
* @param int $band which band
* @param int $doublings how many times the shortest stretch has
* @param int $channels how many channels the sound has
* @return int the highest useful rate for that band
*/
public static function ceilingFor($band, $doublings, $channels)
{
$whole = CeltBands::EDGES[$band + 1] - CeltBands::EDGES[$band];
$slots = $whole;
if (($slots << $doublings) == 1) {
$most = $channels * (1 + self::MOST_FINE_BITS) << self::BIT_PARTS;
} else {
$splits = 0;
/* A band wider than two slots can be split once more than
the stretch's own length would suggest, so the working
starts one level down. */
if ($slots > 2) {
$slots >>= 1;
$splits--;
} else if ($slots <= 1) {
$splits = min($doublings, 1);
$slots <<= $splits;
}
$at = self::$starts[$splits + 1][$band];
$most = self::$costs[$at + self::$costs[$at]] + 1;
$width = $slots;
$log = self::widthLog($band);
for ($step = 0; $step < $doublings - $splits; $step++) {
$most <<= 1;
$offset = (($log + (($splits + $step) << self::BIT_PARTS))
>> 1) - self::SPLIT_OFFSET;
/* Saying which way a split leaned costs a little under
nine tenths of what it is given, which is carried
here as a ratio rather than a fraction. */
$top = 459 * ((2 * $width - 1) * $offset + $most);
$bottom = ((2 * $width - 1) << 9) - 459;
$most += min(intdiv($top + ($bottom >> 1), $bottom), 57);
$width <<= 1;
}
if ($channels == 2) {
$most <<= 1;
$pair = ($width == 2);
$offset = (($log + ($doublings << self::BIT_PARTS)) >> 1) -
($pair ? self::SPLIT_OFFSET_PAIR : self::SPLIT_OFFSET);
$freedoms = 2 * $width - 1 - ($pair ? 1 : 0);
$share = $pair ? 512 : 487;
$top = $share * ($most + $freedoms * $offset);
$bottom = ($freedoms << 9) - $share;
$most += min(intdiv($top + ($bottom >> 1), $bottom),
$pair ? 64 : 61);
}
$freedoms = $channels * $width +
(($channels == 2 && $width > 2) ? 1 : 0);
$offset = (($log + ($doublings << self::BIT_PARTS)) >> 1) -
self::FINE_OFFSET;
if ($width == 2) {
$offset += 1 << self::BIT_PARTS >> 2;
}
$top = $most + $freedoms * $offset;
$bottom = ($freedoms - 1) << self::BIT_PARTS;
$fine = min(intdiv($top + ($bottom >> 1), $bottom),
self::MOST_FINE_BITS);
$most += $channels * $fine << self::BIT_PARTS;
}
return intdiv(4 * $most,
$channels * ($whole << $doublings)) - 64;
}
/**
* ceilingRoom the highest rate a band can use, in parts of a bit been
* doubled
*
* @param int $band which band
* @param int $doublings how many times the shortest stretch has
* @param int $channels how many channels the sound has
* @return int the highest rate, in parts of a bit
*/
public static function ceilingRoom($band, $doublings, $channels)
{
self::buildCeilings();
$slots = (CeltBands::EDGES[$band + 1] - CeltBands::EDGES[$band])
<< $doublings;
return (self::$ceilings[$doublings][$channels][$band] + 64) *
$channels * $slots >> 2;
}
}
(c) 2026 Seekquarry - Open Source Search Engine Software