<?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;
    }
}
