/ src / library / av_processing / CeltAllocation.php
<?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;

/**
 * CeltAllocation decides how much room each band of a stretch is given. A
 * stretch has a fixed number of bits and twenty one bands wanting them. Nothing
 * in the recording says outright how many each band got. Instead the writer and
 * the reader run the same sharing out, from the same starting point, and arrive
 * at the same answer. A few things that could not be worked out are stored: how
 * much extra a band was given beyond its share, whether the stretch leaned
 * towards the low bands or the high ones, and which bands were dropped
 * entirely. The rest is arithmetic both sides do alike. That makes this the
 * least forgiving part of the decoder. Every other part reads something and can
 * be wrong about that one thing. This part reads almost nothing and works
 * almost everything out, so a fault does not misread a value, it hands every
 * band after it the wrong amount of room, and the stretch is lost. The sharing
 * works from a set of curves saying how much each band deserves at eleven
 * different rates. The stretch's true rate falls between two of them, so the
 * two are found by halving the range, and then the point between them is found
 * by halving again. What comes out is how much room each band's shape gets, how
 * many bits the finer loudness pass gets, and which bands were dropped. The
 * curves and the likelihoods here come from the Opus specification, RFC 6716,
 * and the reference implementation it carries. The notice covering them is in
 * the docblock of src/library/media/CeltBands.php.
 */
class CeltAllocation
{
    /**
     * BIT_PARTS is how finely room is counted: each whole bit is split into
     * this many parts.
     */
    const BIT_PARTS = 3;
    /**
     * BETWEEN_STEPS is how many times the range between two curves is halved to
     * find the point between them.
     */
    const BETWEEN_STEPS = 6;
    /**
     * CURVE_COUNT is how many bit-sharing curves the format fixes. Each
     * says how to spread a frame's bits across its bands, and a
     * frame is read as a point between two of them.
     */
    const CURVE_COUNT = 11;
    /**
     * MOST_FINE_BITS is most bits the finer loudness pass may spend on one
     * band.
     */
    const MOST_FINE_BITS = 8;
    /**
     * 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;
    /**
     * BOOST_CHANCE is how unlikely a band is to ask for extra room, before any
     * band has asked.
     */
    const BOOST_CHANCE = 6;
    /**
     * REPEAT_BOOST_CHANCE is how unlikely a band is to ask for more once it has
     * asked once.
     */
    const REPEAT_BOOST_CHANCE = 1;
    /**
     * KEENEST_BOOST_CHANCE is the least unlikely asking for extra room is
     * allowed to become.
     */
    const KEENEST_BOOST_CHANCE = 2;
    /**
     * SMALLEST_BOOST_STEP is the smallest step of extra room a band may ask
     * for.
     */
    const SMALLEST_BOOST_STEP = 6;
    /**
     * TILT_CHANCES is the likelihoods for which way the stretch leaned,
     * counting down from the whole.
     */
    const TILT_CHANCES = [126, 124, 119, 109, 87, 41, 19, 9, 4, 2, 0];
    /**
     * TILT_BITS is how many bits those likelihoods add up to.
     */
    const TILT_BITS = 7;
    /**
     * TILT_MIDDLE is the lean used when the stretch says nothing about it,
     * which is the middle of the range.
     */
    const TILT_MIDDLE = 5;
    /**
     * TILT_ROOM is room needed before the lean is stored.
     */
    const TILT_ROOM = 6;
    /**
     * CHOICE_COSTS is the cost of saying which band the two channels stopped
     * being told apart at, by how many bands there are to choose from.
     */
    const CHOICE_COSTS = [0, 8, 13, 16, 19, 21, 23, 24, 26, 27, 28, 29, 30,
        31, 32, 32, 33, 34, 34, 35, 36, 36, 37, 37];
    /**
     * curves how much each band deserves at eleven different rates, from
     * nothing at all up to as much as a band can use. The stretch's own rate
     * falls between two of these.
     *
     * @return array eleven curves, one value per band
     */
    public static function curves()
    {
        static $curves = null;
        if ($curves !== null) {
            return $curves;
        }
        $curves = [
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
            [90, 80, 75, 69, 63, 56, 49, 40, 34, 29, 20, 18, 10, 0, 0, 0, 0,
                0, 0, 0, 0],
            [110, 100, 90, 84, 78, 71, 65, 58, 51, 45, 39, 32, 26, 20, 12, 0,
                0, 0, 0, 0, 0],
            [118, 110, 103, 93, 86, 80, 75, 70, 65, 59, 53, 47, 40, 31, 23,
                15, 4, 0, 0, 0, 0],
            [126, 119, 112, 104, 95, 89, 83, 78, 72, 66, 60, 54, 47, 39, 32,
                25, 17, 12, 1, 0, 0],
            [134, 127, 120, 114, 103, 97, 91, 85, 78, 72, 66, 60, 54, 47, 41,
                35, 29, 23, 16, 10, 1],
            [144, 137, 130, 124, 113, 107, 101, 95, 88, 82, 76, 70, 64, 57,
                51, 45, 39, 33, 26, 15, 1],
            [152, 145, 138, 132, 123, 117, 111, 105, 98, 92, 86, 80, 74, 67,
                61, 55, 49, 43, 36, 20, 1],
            [162, 155, 148, 142, 133, 127, 121, 115, 108, 102, 96, 90, 84,
                77, 71, 65, 59, 53, 46, 30, 1],
            [172, 165, 158, 152, 143, 137, 131, 125, 118, 112, 106, 100, 94,
                87, 81, 75, 69, 63, 56, 45, 20],
            [200, 200, 200, 200, 200, 200, 200, 200, 198, 193, 188, 183, 178,
                173, 168, 163, 158, 153, 148, 129, 104]];
        return $curves;
    }
    /**
     * readBoosts reads the extra room each band asked for beyond its share. A
     * band that carries something the ear will notice can ask to be given more
     * than the curves would allow. Asking is made cheaper once any band has
     * asked, since a stretch that boosts one band usually boosts others. been
     * doubled of a bit left of the stretch's room
     *
     * @param object $reader the reader partway through a stretch
     * @param int $doublings how many times the shortest stretch has
     * @param int $channels how many channels the sound has
     * @param int $first_band the lowest band the stretch carries
     * @param int $past_last one past the highest band it carries
     * @param int $room how much room the whole stretch has, in parts
     * @return array the extra room each band asked for, and what is
     */
    public static function readBoosts($reader, $doublings, $channels,
        $first_band, $past_last, $room)
    {
        $boosts = array_fill(0, CeltBands::BAND_COUNT, 0);
        $chance = self::BOOST_CHANCE;
        $used = $reader->bitsUsedFinely();
        for ($band = $first_band; $band < $past_last; $band++) {
            $width = $channels * CeltBands::widthOf($band, $doublings);
            /* A step is six bits, but never more than one bit for each
               slot of the band nor less than an eighth of one. */
            $step = min($width << self::BIT_PARTS,
                max(self::SMALLEST_BOOST_STEP << self::BIT_PARTS, $width));
            $ceiling = CeltPulseCache::ceilingRoom($band, $doublings,
                $channels);
            $this_chance = $chance;
            $boost = 0;
            while ($used + ($this_chance << self::BIT_PARTS) < $room &&
                $boost < $ceiling) {
                $asked = $reader->decodeBit($this_chance);
                $used = $reader->bitsUsedFinely();
                if ($asked == 0) {
                    break;
                }
                $boost += $step;
                $room -= $step;
                $this_chance = self::REPEAT_BOOST_CHANCE;
            }
            $boosts[$band] = $boost;
            if ($boost > 0) {
                $chance = max(self::KEENEST_BOOST_CHANCE, $chance - 1);
            }
        }
        return ["boosts" => $boosts, "room" => $room];
    }
    /**
     * readTilt reads which way the stretch leaned, towards the low bands or the
     * high ones
     *
     * @param object $reader the reader partway through a stretch
     * @param int $room how much room the whole stretch has
     * @return int the lean, where the middle of the range is five
     */
    public static function readTilt($reader, $room)
    {
        if ($reader->bitsUsedFinely() + (self::TILT_ROOM << self::BIT_PARTS)
            > $room) {
            return self::TILT_MIDDLE;
        }
        return $reader->decodeFromTable(self::TILT_CHANCES, self::TILT_BITS);
    }
    /**
     * shareOut shares the stretch's room out between its bands bit been doubled
     * bits its finer loudness gets, which bands asked first for leftovers, how
     * many bands were kept, and what is left over
     *
     * @param object $reader the reader partway through a stretch
     * @param array $boosts the extra room each band asked for
     * @param int $tilt which way the stretch leaned
     * @param int $room how much room is left to share, in parts of a
     * @param int $doublings how many times the shortest stretch has
     * @param int $channels how many channels the sound has
     * @param int $first_band the lowest band the stretch carries
     * @param int $past_last one past the highest band it carries
     * @return array how much room each band's shape gets, how many
     */
    public static function shareOut($reader, $boosts, $tilt, $room,
        $doublings, $channels, $first_band, $past_last)
    {
        $room = max($room, 0);
        $bands = CeltBands::BAND_COUNT;
        $last_kept = $first_band;
        /* One bit is held back to say where the dropping of bands
           stops, and in two channel sound two more are held back to
           say where the channels stop being told apart. */
        $stop_held = ($room >= 1 << self::BIT_PARTS) ?
            1 << self::BIT_PARTS : 0;
        $room -= $stop_held;
        $join_held = 0;
        $split_held = 0;
        if ($channels == 2) {
            $join_held = self::CHOICE_COSTS[$past_last - $first_band];
            if ($join_held > $room) {
                $join_held = 0;
            } else {
                $room -= $join_held;
                $split_held = ($room >= 1 << self::BIT_PARTS) ?
                    1 << self::BIT_PARTS : 0;
                $room -= $split_held;
            }
        }
        $floors = array_fill(0, $bands, 0);
        $leans = array_fill(0, $bands, 0);
        for ($band = $first_band; $band < $past_last; $band++) {
            $slots = CeltBands::EDGES[$band + 1] - CeltBands::EDGES[$band];
            /* Below this a band would get too little to be worth
               storing a shape for at all. */
            $floors[$band] = max($channels << self::BIT_PARTS,
                (3 * $slots << $doublings << self::BIT_PARTS) >> 4);
            $leans[$band] = $channels * $slots *
                ($tilt - self::TILT_MIDDLE - $doublings) *
                ($past_last - $band - 1) *
                (1 << ($doublings + self::BIT_PARTS)) >> 6;
            if (($slots << $doublings) == 1) {
                $leans[$band] -= $channels << self::BIT_PARTS;
            }
        }
        $found = self::findCurves($boosts, $floors, $leans, $room,
            $doublings, $channels, $first_band, $past_last);
        return self::settle($reader, $found, $floors, $room, $stop_held,
            $join_held, $split_held, $doublings, $channels, $first_band,
            $past_last, $found["skip_from"]);
    }
    /**
     * findCurves finds the two curves the stretch's rate falls between, and how
     * much each band would get on each been doubled and the lowest band that
     * may be dropped
     *
     * @param array $boosts the extra room each band asked for
     * @param array $floors the least a band may be given
     * @param array $leans the tilt applied to each band
     * @param int $room how much room is left to share
     * @param int $doublings how many times the shortest stretch has
     * @param int $channels how many channels the sound has
     * @param int $first_band the lowest band the stretch carries
     * @param int $past_last one past the highest band it carries
     * @return array the lower curve, the step up to the higher one,
     */
    public static function findCurves($boosts, $floors, $leans, $room,
        $doublings, $channels, $first_band, $past_last)
    {
        $low = 1;
        $high = self::CURVE_COUNT - 1;
        do {
            $middle = ($low + $high) >> 1;
            $total = 0;
            $reached = false;
            for ($band = $past_last - 1; $band >= $first_band; $band--) {
                $gets = self::curveGives($middle, $band, $doublings,
                    $channels, $leans, $boosts, true);
                if ($gets >= $floors[$band] || $reached) {
                    $reached = true;
                    $total += min($gets, CeltPulseCache::ceilingRoom($band,
                        $doublings, $channels));
                } else if ($gets >= $channels << self::BIT_PARTS) {
                    $total += $channels << self::BIT_PARTS;
                }
            }
            if ($total > $room) {
                $high = $middle - 1;
            } else {
                $low = $middle + 1;
            }
        } while ($low <= $high);
        $high = $low;
        $low--;
        $lower = array_fill(0, CeltBands::BAND_COUNT, 0);
        $step = array_fill(0, CeltBands::BAND_COUNT, 0);
        $skip_from = $first_band;
        for ($band = $first_band; $band < $past_last; $band++) {
            $under = self::curveGives($low, $band, $doublings, $channels,
                $leans, $boosts, $low > 0);
            if ($high >= self::CURVE_COUNT) {
                /* Even at the ceiling the lean still applies, and any
                   extra asked for goes on top of that. */
                $over = CeltPulseCache::ceilingRoom($band, $doublings,
                    $channels);
                if ($over > 0) {
                    $over = max(0, $over + $leans[$band]);
                }
                $over += $boosts[$band];
            } else {
                $over = self::curveGives($high, $band, $doublings, $channels,
                    $leans, $boosts, true);
            }
            if ($boosts[$band] > 0) {
                $skip_from = $band;
            }
            $lower[$band] = $under;
            $step[$band] = max(0, $over - $under);
        }
        return ["lower" => $lower, "step" => $step, "skip_from" => $skip_from];
    }
    /**
     * curveGives what one curve would give a band, once the lean and any extra
     * asked for are applied been doubled
     *
     * @param int $curve which curve
     * @param int $band which band
     * @param int $doublings how many times the shortest stretch has
     * @param int $channels how many channels the sound has
     * @param array $leans the tilt applied to each band
     * @param array $boosts the extra room each band asked for
     * @param bool $with_boost whether to add the extra asked for
     * @return int what the band would get, in parts of a bit
     */
    public static function curveGives($curve, $band, $doublings, $channels,
        $leans, $boosts, $with_boost)
    {
        $slots = CeltBands::EDGES[$band + 1] - CeltBands::EDGES[$band];
        $gets = $channels * $slots * self::curves()[$curve][$band]
            << $doublings >> 2;
        if ($gets > 0) {
            $gets = max(0, $gets + $leans[$band]);
        }
        if ($with_boost) {
            $gets += $boosts[$band];
        }
        return $gets;
    }
    /**
     * settle settles on a point between the two curves, drops the bands that
     * cannot be afforded, and splits what each band gets between its shape and
     * its finer loudness stops channels stop being told apart channels were
     * stored apart been doubled
     *
     * @param object $reader the reader partway through a stretch
     * @param array $found the two curves
     * @param array $floors the least a band may be given
     * @param int $room how much room is left to share
     * @param int $stop_held the bit held back to say where dropping
     * @param int $join_held the room held back to say where the
     * @param int $split_held the bit held back to say whether the
     * @param int $doublings how many times the shortest stretch has
     * @param int $channels how many channels the sound has
     * @param int $first_band the lowest band the stretch carries
     * @param int $past_last one past the highest band it carries
     * @param int $skip_from the lowest band that may be dropped
     * @return array what each band got and how many bands were kept
     */
    public static function settle($reader, $found, $floors, $room,
        $stop_held, $join_held, $split_held, $doublings, $channels,
        $first_band, $past_last, $skip_from)
    {
        $lower = $found["lower"];
        $step = $found["step"];
        $bands = CeltBands::BAND_COUNT;
        $least = $channels << self::BIT_PARTS;
        $low = 0;
        $high = 1 << self::BETWEEN_STEPS;
        for ($turn = 0; $turn < self::BETWEEN_STEPS; $turn++) {
            $middle = ($low + $high) >> 1;
            $total = 0;
            $reached = false;
            for ($band = $past_last - 1; $band >= $first_band; $band--) {
                $gets = $lower[$band] +
                    ($middle * $step[$band] >> self::BETWEEN_STEPS);
                if ($gets >= $floors[$band] || $reached) {
                    $reached = true;
                    $total += min($gets, CeltPulseCache::ceilingRoom($band,
                        $doublings, $channels));
                } else if ($gets >= $least) {
                    $total += $least;
                }
            }
            if ($total > $room) {
                $high = $middle;
            } else {
                $low = $middle;
            }
        }
        $given = array_fill(0, $bands, 0);
        $total = 0;
        $reached = false;
        for ($band = $past_last - 1; $band >= $first_band; $band--) {
            $gets = $lower[$band] +
                ($low * $step[$band] >> self::BETWEEN_STEPS);
            if ($gets < $floors[$band] && !$reached) {
                $gets = ($gets >= $least) ? $least : 0;
            } else {
                $reached = true;
            }
            $gets = min($gets, CeltPulseCache::ceilingRoom($band, $doublings,
                $channels));
            $given[$band] = $gets;
            $total += $gets;
        }
        $kept = self::dropBands($reader, $given, $floors, $room, $total,
            $stop_held, $join_held, $doublings, $first_band, $past_last,
            $skip_from, $channels);
        /* Where two channels were held room for, the recording now says
           from which band up the two stop being told apart, and whether
           they were stored side by side rather than as a middle and a
           difference. */
        $joins_from = 0;
        $side_block_y_side = 0;
        if ($join_held > 0) {
            $joins_from = $first_band +
                $reader->decodeNumber($kept["kept"] + 1 - $first_band);
        }
        if ($split_held > 0) {
            $side_block_y_side = $reader->decodeBit(1);
        }
        $shared = self::splitEach($given, $kept["given"], $kept["kept"],
            $kept["room"], $kept["total"], $doublings, $channels,
            $first_band, $past_last, $joins_from, $side_block_y_side);
        $shared["joins_from"] = $joins_from;
        $shared["side_by_side"] = $side_block_y_side;
        return $shared;
    }
    /**
     * dropBands drops the highest bands while the recording says to, working
     * downwards, and hands their room back to the bands below stops been
     * doubled room and total after dropping
     *
     * @param object $reader the reader partway through a stretch
     * @param array $given what each band got
     * @param array $floors the least a band may be given
     * @param int $room how much room is left to share
     * @param int $total how much has been given out so far
     * @param int $stop_held the bit held back to say where dropping
     * @param int $join_held the room held back for the channels
     * @param int $doublings how many times the shortest stretch has
     * @param int $first_band the lowest band the stretch carries
     * @param int $past_last one past the highest band it carries
     * @param int $skip_from the lowest band that may be dropped
     * @param int $channels how many channels the sound has
     * @return array what each band got, how many were kept, and the
     */
    public static function dropBands($reader, $given, $floors, $room, $total,
        $stop_held, $join_held, $doublings, $first_band, $past_last,
        $skip_from, $channels = 1)
    {
        /* A dropped band may still keep one bit for each channel, all
           of it going to its loudness, so the least worth keeping is a
           bit per channel rather than a bit. */
        $least = $channels << self::BIT_PARTS;
        /* Room is shared out in proportion to a band's width measured
           in the shortest stretch's slots, not in this stretch's, so
           the edges are used as they stand rather than widened. */
        $edges = CeltBands::EDGES;
        $kept = $past_last;
        while (true) {
            $band = $kept - 1;
            if ($band <= $skip_from) {
                $room += $stop_held;
                break;
            }
            $left = $room - $total;
            $span = $edges[$kept] - $edges[$first_band];
            $each = ($span > 0) ? intdiv($left, $span) : 0;
            $left -= $span * $each;
            $spare = max($left - ($edges[$band] - $edges[$first_band]), 0);
            $width = $edges[$kept] - $edges[$band];
            $would_get = $given[$band] + $each * $width + $spare;
            /* A band is only asked about where it would have had
               enough to be worth keeping. Below that it goes without
               anything being stored. */
            if ($would_get >= max($floors[$band], $least + (1 << 3))) {
                if ($reader->decodeBit(1) != 0) {
                    break;
                }
                $total += 1 << self::BIT_PARTS;
                $would_get -= 1 << self::BIT_PARTS;
            }
            $total -= $given[$band] + $join_held;
            if ($join_held > 0) {
                $join_held = self::CHOICE_COSTS[$band - $first_band];
            }
            $total += $join_held;
            if ($would_get >= $least) {
                $total += $least;
                $given[$band] = $least;
            } else {
                $given[$band] = 0;
            }
            $kept--;
        }
        return ["given" => $given, "kept" => $kept, "room" => $room,
            "total" => $total];
    }
    /**
     * splitEach hands out what is still unspent and splits each band's room
     * between its shape and its finer loudness been doubled being told apart
     *
     * @param array $before what each band got before the leftovers
     * @param array $given what each band got after dropping
     * @param int $kept how many bands were kept
     * @param int $room how much room is left to share
     * @param int $total how much has been given out
     * @param int $doublings how many times the shortest stretch has
     * @param int $channels how many channels the sound has
     * @param int $first_band the lowest band the stretch carries
     * @param int $past_last one past the highest band it carries
     * @param int $joins_from the band from which the two channels stop
     * @param int $side_block_y_side whether the two were stored as they are
     * @return array what each band got, split three ways
     */
    public static function splitEach($before, $given, $kept, $room, $total,
        $doublings, $channels, $first_band, $past_last, $joins_from = 0,
        $side_block_y_side = 0)
    {
        $bands = CeltBands::BAND_COUNT;
        $edges = CeltBands::EDGES;
        $left = $room - $total;
        $span = $edges[$kept] - $edges[$first_band];
        $each = ($span > 0) ? intdiv($left, $span) : 0;
        $left -= $span * $each;
        for ($band = $first_band; $band < $kept; $band++) {
            $given[$band] += $each * ($edges[$band + 1] - $edges[$band]);
        }
        for ($band = $first_band; $band < $kept; $band++) {
            $take = min($left, $edges[$band + 1] - $edges[$band]);
            $given[$band] += $take;
            $left -= $take;
        }
        $shape = array_fill(0, $bands, 0);
        $fine = array_fill(0, $bands, 0);
        $keenest = array_fill(0, $bands, 0);
        $spare = 0;
        $paired = ($channels > 1) ? 1 : 0;
        $stretch_log = $doublings << self::BIT_PARTS;
        for ($band = $first_band; $band < $kept; $band++) {
            /* Sharing the leftovers goes by width in the shortest
               stretch's slots, but splitting a band's own room between
               its shape and its loudness goes by the width it really
               has, which is that widened by the stretch's length. */
            $slots = ($edges[$band + 1] - $edges[$band]) << $doublings;
            $has = $given[$band] + $spare;
            if ($slots > 1) {
                $over = max($has - CeltPulseCache::ceilingRoom($band,
                    $doublings, $channels), 0);
                $has -= $over;
                /* A band of two channels read together as an average
                   and a difference carries one more degree of freedom
                   than the slots of its two channels alone, and the
                   split leans on that count. */
                $freedoms = $channels * $slots;
                if ($channels == 2 && $slots > 2 && !$side_block_y_side &&
                    $band < $joins_from) {
                    $freedoms++;
                }
                $weight = $freedoms *
                    (CeltPulseCache::widthLog($band) + $stretch_log);
                $offset = ($weight >> 1) - $freedoms * self::FINE_OFFSET;
                if ($slots == 2) {
                    $offset += $freedoms << self::BIT_PARTS >> 2;
                }
                /* The first few bits of finer loudness are worth more
                   than the ones after, so the offer is sweetened while
                   a band still has very few. */
                if ($has + $offset < $freedoms * 2 << self::BIT_PARTS) {
                    $offset += $weight >> 2;
                } else if ($has + $offset < $freedoms * 3 << self::BIT_PARTS) {
                    $offset += $weight >> 3;
                }
                $bits = max(0, $has + $offset +
                    ($freedoms << (self::BIT_PARTS - 1)));
                $bits = intdiv($bits, $freedoms) >> self::BIT_PARTS;
                if ($channels * $bits > ($has >> self::BIT_PARTS)) {
                    $bits = $has >> $paired >> self::BIT_PARTS;
                }
                $bits = min($bits, self::MOST_FINE_BITS);
                $keenest[$band] = ($bits * ($freedoms << self::BIT_PARTS) >=
                    $has + $offset) ? 1 : 0;
                $has -= $channels * $bits << self::BIT_PARTS;
                $fine[$band] = $bits;
            } else {
                $over = max(0, $has - ($channels << self::BIT_PARTS));
                $has -= $over;
                $fine[$band] = 0;
                $keenest[$band] = 1;
            }
            if ($over > 0) {
                $extra = min($over >> ($paired + self::BIT_PARTS),
                    self::MOST_FINE_BITS - $fine[$band]);
                $fine[$band] += $extra;
                $used = $extra * $channels << self::BIT_PARTS;
                $keenest[$band] = ($used >= $over - $spare) ? 1 : 0;
                $over -= $used;
            }
            $spare = $over;
            $shape[$band] = $has;
        }
        for ($band = $kept; $band < $past_last; $band++) {
            $fine[$band] = $given[$band] >> $paired >> self::BIT_PARTS;
            $shape[$band] = 0;
            $keenest[$band] = ($fine[$band] < 1) ? 1 : 0;
        }
        /* A dropped band's room, where it kept any, all goes to its
           loudness: one bit for each channel and nothing stored. */
        for ($band = $kept; $band < $past_last; $band++) {
            $fine[$band] = $given[$band] >> $paired >> self::BIT_PARTS;
            $keenest[$band] = ($fine[$band] < 1) ? 1 : 0;
        }
        return ["shape" => $shape, "fine" => $fine, "keenest" => $keenest,
            "kept" => $kept, "spare" => $spare, "joins_from" => 0,
            "side_by_side" => 0];
    }
}
X