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

/**
 * Pvq reads back the shape of a band of sound from the single number it was
 * stored as. Opus does not store the loudness of each part of a band
 * separately. It stores one loudness for the whole band, and then stores the
 * shape of the band as a pattern of pulses: so many pulses spread across the
 * band's slots, each pulse positive or negative. Every pattern with the same
 * number of pulses is given a number, and only that number is written down.
 * This turns the shape into a single count that costs only as many bits as
 * there are patterns, which is far fewer than writing each slot out. The work
 * here is turning that number back into the pattern. The patterns have to be
 * numbered in exactly the order the writer used, because the number carries no
 * other clue about which pattern it means. That order is fixed by the Opus
 * specification, RFC 6716, in the section on decoding the band shapes, and by
 * the reference implementation the specification carries. How many patterns
 * exist for a given number of slots and pulses is worked out from a rule that
 * builds each count from three smaller ones, rather than being kept as a table
 * of numbers. The counts reach into the billions for the larger bands, so a
 * table of them would be long, and the rule is quick enough that keeping the
 * answers as they are worked out costs less than storing the whole table would.
 */
class Pvq
{
    /**
     * counts stores counts worked out so far, kept so that a count is never
     * worked out twice
     *
     * @var array
     */
    public static $counts = [];
    /**
     * rows stores the same counts arranged by width first without the swap, so
     * the walk through a pattern can read them straight out of an array
     *
     * @var array
     */
    public static $rows = [];
    /**
     * helperCount a helper count the numbering is built from: how many patterns
     * of a given number of slots and pulses there are once the patterns have
     * been divided up by where their first pulse falls and which way it points.
     * It is not a quantity with much meaning on its own. It exists because the
     * numbering can be worked out from it with plain addition, and because it
     * follows a rule that builds each value from three smaller ones.
     *
     * @param int $slots how many slots the band has
     * @param int $pulses how many pulses are spread across them
     * @return int the helper count
     */
    public static function helperCount($slots, $pulses)
    {
        if ($slots < 0 || $pulses < 0) {
            return 0;
        }
        if ($slots == 0) {
            return ($pulses == 0) ? 1 : 0;
        }
        if ($pulses == 0) {
            return 0;
        }
        /* The count does not change when the two are swapped, so half
           the work can be skipped by always asking for them the same
           way round. */
        if ($slots > $pulses) {
            $swap = $slots;
            $slots = $pulses;
            $pulses = $swap;
        }
        if (isset(self::$counts[$slots][$pulses])) {
            return self::$counts[$slots][$pulses];
        }
        $value = self::helperCount($slots - 1, $pulses) +
            self::helperCount($slots, $pulses - 1) +
            self::helperCount($slots - 1, $pulses - 1);
        self::$counts[$slots][$pulses] = $value;
        return $value;
    }
    /**
     * patternCount how many different patterns exist for a band with a given
     * number of slots and pulses. This is how large the number standing for a
     * pattern may be, so it is what the reader has to be told before it can
     * read that number back.
     *
     * @param int $slots how many slots the band has
     * @param int $pulses how many pulses are spread across them
     * @return int how many patterns there are
     */
    public static function patternCount($slots, $pulses)
    {
        return self::helperCount($slots, $pulses) +
            self::helperCount($slots, $pulses + 1);
    }
    /**
     * patternFor turns the number standing for a pattern back into the pattern
     * itself they point the other way
     *
     * @param int $slots how many slots the band has
     * @param int $pulses how many pulses are spread across them
     * @param int $which which pattern, counting from zero
     * @return array how many pulses fall in each slot, negative where
     */
    public static function patternFor($slots, $pulses, $which)
    {
        if ($slots < 1) {
            throw new \Exception("A band must have a slot to put a pulse in");
        }
        if ($which < 0 || $which >= self::patternCount($slots, $pulses)) {
            throw new \Exception("There is no such pattern");
        }
        $pattern = array_fill(0, $slots, 0);
        $left = $pulses;
        $rest = $which;
        for ($at = 0; $at < $slots - 1; $at++) {
            $wide = $slots - $at;
            if (!isset(self::$rows[$wide][$pulses + 1])) {
                for ($fill = 0; $fill <= $pulses + 1; $fill++) {
                    self::$rows[$wide][$fill] =
                        self::helperCount($wide, $fill);
                }
            }
            $row = self::$rows[$wide];
            /* Patterns whose pulse here points the other way are
               numbered above all those whose pulse here points this
               way, so where the number reaches that far, the pulse
               points the other way and that much comes off. */
            $turned = $row[$left + 1];
            $backwards = ($rest >= $turned);
            if ($backwards) {
                $rest -= $turned;
            }
            /* What is left says how many pulses stayed behind for the
               slots after this one, so the difference is how many fell
               here. */
            $behind = $left;
            while ($row[$behind] > $rest) {
                $behind--;
            }
            $rest -= $row[$behind];
            $here = $left - $behind;
            $pattern[$at] = $backwards ? -$here : $here;
            $left = $behind;
        }
        /* Whatever pulses are left all fall in the last slot, and the
           number that remains says only which way they point. */
        $pattern[$slots - 1] = ($rest != 0) ? -$left : $left;
        return $pattern;
    }
    /**
     * readFrom reads the shape of one band out of a piece of sound sound
     *
     * @param object $reader the reader partway through a piece of
     * @param int $slots how many slots the band has
     * @param int $pulses how many pulses are spread across them
     * @return array how many pulses fall in each slot
     */
    public static function readFrom($reader, $slots, $pulses)
    {
        $which = $reader->decodeNumber(self::patternCount($slots, $pulses));
        return self::patternFor($slots, $pulses, $which);
    }
}
