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

/**
 * CeltBandReader reads every band of a stretch, splitting the wider ones as it
 * goes. A band with a lot of room cannot be stored as one pattern of pulses,
 * because the number of patterns to choose from grows too large to number. So a
 * wide band is cut in half, a single value says how the loudness leaned between
 * the halves, and each half is then treated as a band in its own right and cut
 * again if it is still too wide. What comes back is put together from the
 * halves. Two other things happen around that. A band may be reshaped first,
 * trading detail in time for detail in pitch or the other way about, depending
 * on what the stretch said suited it. And a band given no room at all is not
 * left silent: it is filled either with a quiet copy of a band lower down,
 * which sounds better than silence because real sound is alike at different
 * pitches, or with faint noise where there is nothing below to copy. Room not
 * spent on one band is carried forward to the next, so the bands have to be
 * walked in order and each one's reading depends on every one before it. This
 * follows RFC 6716, the specification of the Opus audio codec, in its sections
 * on the band shapes.
 */
class CeltBandReader
{
    /**
     * BIT_PARTS is how finely room is counted, as parts of a bit.
     */
    const BIT_PARTS = 3;
    /**
     * SPLIT_OFFSET is how much of a band's room is favored towards pitch detail
     * over time detail when it is split.
     */
    const SPLIT_OFFSET = 4;
    /**
     * MOST_ROOM is the most room a band may be given.
     */
    const MOST_ROOM = 16383;
    /**
     * REBALANCE_ROOM is how much room a split must leave over before it is
     * worth handing back to the other half.
     */
    const REBALANCE_ROOM = 3;
    /**
     * HARDEST_SMEAR is the setting that smears a band's shape hardest.
     */
    const HARDEST_SMEAR = 3;
    /**
     * FOLD_LEVEL is how quiet the copy of a lower band is made.
     */
    const FOLD_LEVEL = 0.00390625;
    /**
     * SEED_STEP is the two numbers the wandering seed is stepped by.
     */
    const SEED_STEP = 1664525;
    /**
     * SEED_ADD is the amount added at each step of the seed.
     */
    const SEED_ADD = 1013904223;
    /**
     * SEED_LIMIT is how large the number that seeds the noise may be. The
     * seed is written into the frame so a decoder makes the same
     * noise the encoder heard.
     */
    const SEED_LIMIT = 4294967296;
    /**
     * HALF_ORDER is the order the halves of a split band are put back in, laid
     * out for each number of halves.
     */
    const HALF_ORDER = [1, 0, 3, 0, 2, 1, 7, 0, 4, 3, 6, 1, 5, 2,
        15, 0, 8, 7, 12, 3, 11, 4, 14, 1, 9, 6, 13, 2, 10, 5];
    /**
     * FOLD_MARKS is how the marks saying which groups hold something are folded
     * when a band is reshaped towards pitch detail.
     */
    const FOLD_MARKS = [0, 1, 1, 1, 2, 3, 3, 3, 2, 3, 3, 3, 2, 3, 3, 3];
    /**
     * UNFOLD_MARKS is how those marks are opened back out afterwards.
     */
    const UNFOLD_MARKS = [0x00, 0x03, 0x0C, 0x0F, 0x30, 0x33, 0x3C, 0x3F,
        0xC0, 0xC3, 0xCC, 0xCF, 0xF0, 0xF3, 0xFC, 0xFF];
    /**
     * reader stores the range reader this band's values are taken
     * from, kept partway through a stretch of sound so the next band
     * carries on where the last one stopped.
     * @var object
     */
    public $reader;
    /**
     * room_left stores how much room is left in the stretch, in parts of a bit.
     * @var int
     */
    public $room_left;
    /**
     * band stores which of the frequency bands is being read, since
     * how many bits a band gets depends on where it sits.
     * @var int
     */
    public $band;
    /**
     * smear stores how strongly the shapes read for one band are
     * blended into the next, which the format uses to soften a
     * sudden change.
     * @var int
     */
    public $smear;
    /**
     * reshaped stores whether this band's shape was folded from a
     * neighbor rather than read, and which way round it was folded
     * @var int
     */
    public $reshaped;
    /**
     * doublings stores how many times the shortest stretch has been doubled.
     * @var int
     */
    public $doublings;
    /**
     * seed stores a wandering number used to make faint noise where a band has
     * nothing to copy from.
     * @var int
     */
    public $seed;
    /**
     * careful stores whether to leave the first band's split alone rather than
     * risking noise in it.
     * @var bool
     */
    public $careful;
    /**
     * whole_room stores how much room the whole stretch has for its bands,
     * which is what the stretch holds less anything held back before the bands
     * are reached.
     * @var int
     */
    public $whole_room;
    /**
     * __construct sets up a read over the bands of one stretch been doubled
     *
     * @param object $reader the reader partway through a stretch
     * @param int $doublings how many times the shortest stretch has
     * @param int $smear how hard the stretch said to smear
     * @param int $seed where the wandering number starts
     */
    public function __construct($reader, $doublings, $smear, $seed)
    {
        $this->reader = $reader;
        $this->doublings = $doublings;
        $this->smear = $smear;
        $this->seed = $seed;
        $this->room_left = 0;
        $this->whole_room = $reader->size * 8 << self::BIT_PARTS;
        $this->band = 0;
        $this->reshaped = 0;
        $this->careful = false;
    }
    /**
     * nextSeed steps the number that seeds the noise on to its next
     * value. Both sides step it the same way, so both make the same
     * noise
     *
     * @return int the next value
     */
    public function nextSeed()
    {
        $this->seed = (self::SEED_STEP * $this->seed + self::SEED_ADD) %
            self::SEED_LIMIT;
        return $this->seed;
    }
    /**
     * readAll reads every band of a stretch says how many groups a band is
     * looked at in groups of each band hold something
     *
     * @param array $shape_room how much room each band's shape gets
     * @param array $length_changes how each band was reshaped
     * @param int $kept how many bands were kept
     * @param int $sudden whether the stretch changed suddenly, which
     * @param int $spare room left over from sharing out
     * @param int $first_band the lowest band the stretch carries
     * @param int $past_last one past the highest band it carries
     * @return array every band's slots laid end to end, and which
     */
    public function readAll($shape_room, $length_changes, $kept, $sudden,
        $spare, $first_band, $past_last)
    {
        $stretch = 1 << $this->doublings;
        $groups = $sudden ? $stretch : 1;
        $edges = CeltBands::edgesFor($this->doublings);
        $length = $edges[CeltBands::BAND_COUNT];
        $slots = array_fill(0, $length, 0.0);
        $marks = array_fill(0, CeltBands::BAND_COUNT, 0);
        $below = array_fill(0, $length, 0.0);
        $start_at = $edges[$first_band];
        $whole = $this->whole_room;
        $fold_from = 0;
        $keep_folding = true;
        $balance = $spare;
        $this->careful = ($groups > 1);
        for ($band = $first_band; $band < $past_last; $band++) {
            $this->band = $band;
            $at = $edges[$band];
            $width = $edges[$band + 1] - $at;
            $used = $this->reader->bitsUsedFinely();
            if ($band != $first_band) {
                $balance -= $used;
            }
            $this->room_left = $whole - $used - 1;
            $room = 0;
            if ($band <= $kept - 1) {
                $share = intdiv($balance, min(3, $kept - $band));
                $room = max(0, min(self::MOST_ROOM,
                    min($this->room_left + 1, $shape_room[$band] + $share)));
            }
            if ($at - $width >= $start_at &&
                ($keep_folding || $fold_from == 0)) {
                $fold_from = $band;
            }
            $this->reshaped = $length_changes[$band];
            $copy_from = -1;
            $filled = (1 << $groups) - 1;
            if ($fold_from != 0 && ($this->smear != self::HARDEST_SMEAR ||
                $groups > 1 || $this->reshaped < 0)) {
                $copy_from = max(0, $edges[$fold_from] - $start_at - $width);
                $filled = $this->markedBelow($marks, $edges, $fold_from,
                    $copy_from + $start_at, $width, $band);
            }
            $taken = ($copy_from >= 0) ?
                array_slice($below, $copy_from, $width) : null;
            $read = $this->readBand($slots, $at, $width, $room, $groups,
                $taken, $this->doublings, $filled);
            $marks[$band] = $read["marks"];
            if ($band != $past_last - 1) {
                $spread_out = $read["scaled"];
                for ($slot = 0; $slot < $width; $slot++) {
                    $below[$at - $start_at + $slot] = $spread_out[$slot];
                }
            }
            $balance += $shape_room[$band] + $used;
            $keep_folding = ($room > ($width << self::BIT_PARTS));
            $this->careful = false;
        }
        return ["slots" => $slots, "marks" => $marks];
    }
    /**
     * readAllPairs reads every band of a stretch that carries two channels. The
     * two are stored together as an average and a difference, unless the
     * stretch says they were stored side by side, and above a band the stretch
     * names the difference is left out and the two are given the same sound at
     * different loudnesses. being told apart are rather than as an average and
     * a difference band hold something
     *
     * @param array $shape_room how much room each band's shape gets
     * @param array $length_changes how each band was reshaped
     * @param int $kept how many bands were kept
     * @param int $sudden whether the stretch changed suddenly
     * @param int $spare room left over from sharing out
     * @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
     * @return array both channels' slots, and which groups of each
     */
    public function readAllPairs($shape_room, $length_changes, $kept,
        $sudden, $spare, $first_band, $past_last, $joins_from,
        $side_block_y_side)
    {
        $stretch = 1 << $this->doublings;
        $groups = $sudden ? $stretch : 1;
        $edges = CeltBands::edgesFor($this->doublings);
        $length = $edges[CeltBands::BAND_COUNT];
        $left = array_fill(0, $length, 0.0);
        $right = array_fill(0, $length, 0.0);
        $marks = array_fill(0, CeltBands::BAND_COUNT, 0);
        $below_left = array_fill(0, $length, 0.0);
        $below_right = array_fill(0, $length, 0.0);
        $start_at = $edges[$first_band];
        $whole = $this->whole_room;
        $fold_from = 0;
        $keep_folding = true;
        $balance = $spare;
        $this->careful = ($groups > 1);
        for ($band = $first_band; $band < $past_last; $band++) {
            $this->band = $band;
            $at = $edges[$band];
            $width = $edges[$band + 1] - $at;
            $used = $this->reader->bitsUsedFinely();
            if ($band != $first_band) {
                $balance -= $used;
            }
            $this->room_left = $whole - $used - 1;
            $room = 0;
            if ($band <= $kept - 1) {
                $share = intdiv($balance, min(3, $kept - $band));
                $room = max(0, min(self::MOST_ROOM,
                    min($this->room_left + 1, $shape_room[$band] + $share)));
            }
            if ($at - $width >= $start_at &&
                ($keep_folding || $fold_from == 0)) {
                $fold_from = $band;
            }
            $this->reshaped = $length_changes[$band];
            $copy_from = -1;
            $filled = (1 << $groups) - 1;
            if ($fold_from != 0 && ($this->smear != self::HARDEST_SMEAR ||
                $groups > 1 || $this->reshaped < 0)) {
                $copy_from = max(0, $edges[$fold_from] - $start_at - $width);
                $filled = $this->markedBelow($marks, $edges, $fold_from,
                    $copy_from + $start_at, $width, $band);
            }
            /* Side by side ends at the band from which the two
               channels stop being told apart. From there the two are
               read together, and the sound copied into empty bands
               becomes the average of what each channel had. */
            if ($side_block_y_side && $band == $joins_from) {
                $side_block_y_side = 0;
                $count = count($below_left);
                for ($slot = 0; $slot < $count; $slot++) {
                    $below_left[$slot] = 0.5 * ($below_left[$slot] +
                        $below_right[$slot]);
                }
            }
            $taken = ($copy_from >= 0) ?
                array_slice($below_left, $copy_from, $width) : null;
            if ($side_block_y_side) {
                /* Each channel gets half the room rounded down, so an
                   odd eighth of a bit goes to neither. */
                $one = $this->readBand($left, $at, $width,
                    intdiv($room, 2), $groups, $taken, $this->doublings,
                    $filled);
                $other_below = ($copy_from >= 0) ?
                    array_slice($below_right, $copy_from, $width) : null;
                $other = $this->readBand($right, $at, $width,
                    intdiv($room, 2), $groups, $other_below,
                    $this->doublings, $filled);
                $marks[$band] = $one["marks"] | $other["marks"];
                if ($band != $past_last - 1) {
                    $scale = sqrt($width);
                    for ($slot = 0; $slot < $width; $slot++) {
                        $below_left[$at - $start_at + $slot] =
                            $scale * $left[$at + $slot];
                        $below_right[$at - $start_at + $slot] =
                            $scale * $right[$at + $slot];
                    }
                }
            } else {
                $pair = CeltStereoBands::readPair($this, $left,
                    $right, $at, $width, $room, $groups, $taken,
                    $this->doublings, $filled, $band >= $joins_from);
                $marks[$band] = $pair["marks"];
                /* Lower bands are copied from the average channel as it
                   was read, not from the left that came out of the
                   merge. */
                if ($band != $past_last - 1) {
                    $scale = sqrt($width);
                    for ($slot = 0; $slot < $width; $slot++) {
                        $below_left[$at - $start_at + $slot] =
                            $scale * $pair["mid"][$slot];
                    }
                }
            }
            $balance += $shape_room[$band] + $used;
            $keep_folding = ($room > ($width << self::BIT_PARTS));
            $this->careful = false;
        }
        return ["slots" => [$left, $right], "marks" => $marks];
    }
    /**
     * markedBelow works out which groups of the bands being copied from hold
     * something, so that a band filled from below knows what it is getting
     *
     * @param array $marks which groups each band already read holds
     * @param array $edges where each band begins
     * @param int $fold_from the band being copied from
     * @param int $copy_at where in the stretch the copy begins
     * @param int $width how many slots the band being filled has
     * @param int $band which band is being filled
     * @return int a bit for each group that holds something
     */
    public function markedBelow($marks, $edges, $fold_from, $copy_at, $width,
        $band)
    {
        $from = $fold_from;
        while ($from > 0 && $edges[$from - 1] > $copy_at) {
            $from--;
        }
        $from = max(0, $from - 1);
        while ($from > 0 && $edges[$from] > $copy_at) {
            $from--;
        }
        $to = $fold_from - 1;
        while (++$to < $band && $edges[$to] < $copy_at + $width) {
            continue;
        }
        $filled = 0;
        for ($which = $from; $which < $to; $which++) {
            $filled |= $marks[$which];
        }
        return $filled;
    }
    /**
     * readBand reads one band, reshaping it first if the stretch said to and
     * putting it back afterwards been doubled except where a split above has
     * already shared it out ready for the next band to copy from
     *
     * @param array $slots every band's slots, changed in place
     * @param int $at where this band begins
     * @param int $width how many slots it has
     * @param int $room how much room its shape gets
     * @param int $groups how many groups it is looked at in
     * @param mixed $below the band to copy from, or null
     * @param int $doublings how many times the shortest stretch has
     * @param int $filled which groups of the band below hold something
     * @param float $loudness what the band should come to, which is one
     * @return array which groups this band holds, and the band scaled
     */
    public function readBand(&$slots, $at, $width, $room, $groups, $below,
        $doublings, $filled, $loudness = 1.0)
    {
        $band = array_slice($slots, $at, $width);
        $span = $width;
        $each = intdiv($span, $groups);
        $held = $groups;
        $towards_pitch = 0;
        $towards_time = 0;
        if ($width == 1) {
            $read = $this->readSingleSlot($band, $room);
            for ($slot = 0; $slot < $width; $slot++) {
                $slots[$at + $slot] = $band[$slot];
            }
            return ["marks" => 1, "scaled" => $band];
        }
        if ($this->reshaped > 0) {
            $towards_pitch = $this->reshaped;
        }
        for ($step = 0; $step < $towards_pitch; $step++) {
            if ($below !== null) {
                CeltShape::pairUp($below, 0, $span >> $step, 1 << $step);
            }
            $filled = self::FOLD_MARKS[$filled & 0xF] |
                self::FOLD_MARKS[$filled >> 4] << 2;
        }
        $held >>= $towards_pitch;
        $each <<= $towards_pitch;
        $left = $this->reshaped;
        while (($each & 1) == 0 && $left < 0) {
            if ($below !== null) {
                CeltShape::pairUp($below, 0, $each, $held);
            }
            $filled |= $filled << $held;
            $held <<= 1;
            $each >>= 1;
            $towards_time++;
            $left++;
        }
        $started_held = $held;
        $started_each = $each;
        if ($held > 1 && $below !== null) {
            $below = self::toTimeOrder($below, $each >> $towards_pitch,
                $held << $towards_pitch, $groups == 1);
        }
        $marks = $this->readPart($band, 0, $span, $room, $held, $below,
            $doublings, $loudness, $filled);
        if ($started_held > 1) {
            $band = self::toPitchOrder($band, $started_each >> $towards_pitch,
                $started_held << $towards_pitch, $groups == 1);
        }
        $each = $started_each;
        $held = $started_held;
        for ($step = 0; $step < $towards_time; $step++) {
            $held >>= 1;
            $each <<= 1;
            $marks |= $marks >> $held;
            CeltShape::pairUp($band, 0, $each, $held);
        }
        for ($step = 0; $step < $towards_pitch; $step++) {
            $marks = self::UNFOLD_MARKS[$marks & 0xF];
            CeltShape::pairUp($band, 0, $span >> $step, 1 << $step);
        }
        $held <<= $towards_pitch;
        for ($slot = 0; $slot < $width; $slot++) {
            $slots[$at + $slot] = $band[$slot];
        }
        /* What the next band copies from is this band made louder in
           proportion to its width, so that a wide band and a narrow
           one are copied from alike. */
        $scale = sqrt($span);
        $scaled = [];
        for ($slot = 0; $slot < $width; $slot++) {
            $scaled[] = $scale * $band[$slot];
        }
        return ["marks" => $marks & ((1 << $held) - 1), "scaled" => $scaled];
    }
    /**
     * readSingleSlot reads a band of a single slot, which holds nothing but a
     * direction
     *
     * @param array $band the band's one slot, changed in place
     * @param int $room how much room it has
     */
    public function readSingleSlot(&$band, $room)
    {
        $sign = 1.0;
        if ($this->room_left >= 1 << self::BIT_PARTS && $room >=
            1 << self::BIT_PARTS) {
            if ($this->reader->decodeRawBits(1) != 0) {
                $sign = -1.0;
            }
            $this->room_left -= 1 << self::BIT_PARTS;
        }
        $band[0] = $sign;
    }
    /**
     * readPart reads one part of a band, splitting it in half where it is too
     * wide to store as one pattern been doubled
     *
     * @param array $band the part's slots, changed in place
     * @param int $at where in the array the part begins
     * @param int $width how many slots the part has
     * @param int $room how much room the part gets
     * @param int $held how many groups the part is looked at in
     * @param mixed $below the part to copy from, or null
     * @param int $doublings how many times the shortest stretch has
     * @param float $loudness what the part should come to
     * @param int $filled which groups of the part below hold something
     * @return int which groups this part holds
     */
    public function readPart(&$band, $at, $width, $room, $held, $below,
        $doublings, $loudness, $filled)
    {
        $started_held = $held;
        $offers = CeltPulseCache::offerCount($this->band, $doublings);
        $dearest = CeltPulseCache::roomFor($this->band, $doublings, $offers);
        /* Where a part would cost more than the widest pattern on offer
           can carry, it is cut in half instead. */
        if ($doublings != -1 && $room > $dearest + 12 - 1 && $width > 2) {
            $half = $width >> 1;
            $doublings--;
            if ($held == 1) {
                $filled = ($filled & 1) | ($filled << 1);
            }
            $held = ($held + 1) >> 1;
            $lean = $this->readLean($band, $at, $half, $room, $held,
                $started_held, $doublings, $filled);
            $room = $lean["room"];
            $gap = self::nudgeGap($lean["gap"], $lean["turn"],
                $started_held, $half, $doublings);
            $mid_room = max(0, min($room, intdiv($room - $gap, 2)));
            $side_room = $room - $mid_room;
            $lower = ($below !== null) ? array_slice($below, 0, $half) : null;
            $upper = ($below !== null) ?
                array_slice($below, $half, $half) : null;
            $marks = 0;
            if ($mid_room >= $side_room) {
                $before = $this->room_left;
                $marks = $this->readPart($band, $at, $half, $mid_room, $held,
                    $lower, $doublings, $loudness * $lean["mid"], $filled);
                $spare = $mid_room - ($before - $this->room_left);
                if ($spare > self::REBALANCE_ROOM << self::BIT_PARTS &&
                    $lean["turn"] != 0) {
                    $side_room += $spare -
                        (self::REBALANCE_ROOM << self::BIT_PARTS);
                }
                $marks |= $this->readPart($band, $at + $half, $half,
                    $side_room, $held, $upper, $doublings,
                    $loudness * $lean["side"], $filled >> $held)
                    << ($started_held >> 1);
            } else {
                $before = $this->room_left;
                $marks = $this->readPart($band, $at + $half, $half,
                    $side_room, $held, $upper, $doublings,
                    $loudness * $lean["side"], $filled >> $held)
                    << ($started_held >> 1);
                $spare = $side_room - ($before - $this->room_left);
                if ($spare > self::REBALANCE_ROOM << self::BIT_PARTS &&
                    $lean["turn"] != 16384) {
                    $mid_room += $spare -
                        (self::REBALANCE_ROOM << self::BIT_PARTS);
                }
                $marks |= $this->readPart($band, $at, $half, $mid_room,
                    $held, $lower, $doublings, $loudness * $lean["mid"],
                    $filled);
            }
            return $marks;
        }
        return $this->readLeaf($band, $at, $width, $room, $held, $below,
            $doublings, $loudness, $filled);
    }
    /**
     * nudgeGap nudges the split of a part's room between its two halves. Where
     * a part is looked at in more than one group and its loudness did not lean
     * all the way to one side, the plain division between the halves is
     * adjusted. Leaning towards the first half is pulled back a little; leaning
     * towards the second is not allowed to favor it at all. Without this the
     * two halves are handed slightly wrong amounts and every pattern read after
     * that point differs. was cut been doubled, after the cut
     *
     * @param int $gap how the room would divide before nudging
     * @param int $turn how far the loudness leaned
     * @param int $started_held how many groups the part had before it
     * @param int $half how many slots each half has
     * @param int $doublings how many times the shortest stretch has
     * @return int how the room divides after nudging
     */
    public static function nudgeGap($gap, $turn, $started_held, $half,
        $doublings)
    {
        if ($started_held <= 1 || ($turn & 0x3FFF) == 0) {
            return $gap;
        }
        if ($turn > 8192) {
            return $gap - ($gap >> (4 - $doublings));
        }
        return min(0, $gap + ($half << self::BIT_PARTS >> (5 - $doublings)));
    }
    /**
     * readLeaf reads a part small enough to store as one pattern of pulses, or
     * fills it where it was given no room been doubled
     *
     * @param array $band the part's slots, changed in place
     * @param int $at where in the array the part begins
     * @param int $width how many slots the part has
     * @param int $room how much room the part gets
     * @param int $held how many groups the part is looked at in
     * @param mixed $below the part to copy from, or null
     * @param int $doublings how many times the shortest stretch has
     * @param float $loudness what the part should come to
     * @param int $filled which groups of the part below hold something
     * @return int which groups this part holds
     */
    public function readLeaf(&$band, $at, $width, $room, $held, $below,
        $doublings, $loudness, $filled)
    {
        $offer = CeltPulseCache::offerWithin($this->band, $doublings, $room);
        $cost = CeltPulseCache::roomFor($this->band, $doublings, $offer);
        $this->room_left -= $cost;
        /* Never spend more than there is, whatever the offer says. */
        while ($this->room_left < 0 && $offer > 0) {
            $this->room_left += $cost;
            $offer--;
            $cost = CeltPulseCache::roomFor($this->band, $doublings, $offer);
            $this->room_left -= $cost;
        }
        if ($offer != 0) {
            $pulses = CeltPulseCache::pulsesAt($offer);
            $read = CeltShape::readBand($this->reader, $width, $pulses,
                $this->smear, $held, $loudness);
            for ($slot = 0; $slot < $width; $slot++) {
                $band[$at + $slot] = $read["shape"][$slot];
            }
            return $read["filled"];
        }
        return $this->fill($band, $at, $width, $held, $below, $loudness,
            $filled);
    }
    /**
     * fill fills a part that was given no room, either with a quiet copy of a
     * part lower down or with faint noise
     *
     * @param array $band the part's slots, changed in place
     * @param int $at where in the array the part begins
     * @param int $width how many slots the part has
     * @param int $held how many groups the part is looked at in
     * @param mixed $below the part to copy from, or null
     * @param float $loudness what the part should come to
     * @param int $filled which groups of the part below hold something
     * @return int which groups this part holds
     */
    public function fill(&$band, $at, $width, $held, $below, $loudness,
        $filled)
    {
        $all = (1 << $held) - 1;
        $filled &= $all;
        if ($filled == 0) {
            for ($slot = 0; $slot < $width; $slot++) {
                $band[$at + $slot] = 0.0;
            }
            return 0;
        }
        if ($below === null) {
            /* Nothing below to copy, so faint noise is used. Real sound
               is never wholly silent in a band, and silence here would
               be heard as a hole. */
            for ($slot = 0; $slot < $width; $slot++) {
                $wander = $this->nextSeed();
                if ($wander >= 0x80000000) {
                    $wander -= self::SEED_LIMIT;
                }
                $band[$at + $slot] = $wander >> 20;
            }
            $filled = $all;
        } else {
            for ($slot = 0; $slot < $width; $slot++) {
                $wander = $this->nextSeed();
                $nudge = ($wander & 0x8000) ? self::FOLD_LEVEL :
                    -self::FOLD_LEVEL;
                $band[$at + $slot] = $below[$slot] + $nudge;
            }
        }
        CeltShape::scaleTo($band, $at, $width, $loudness);
        return $filled;
    }
    /**
     * readLean reads how the loudness leaned between the two halves of a split
     * the split been doubled what is left of the room
     *
     * @param array $band the part's slots
     * @param int $at where in the array the part begins
     * @param int $half how many slots each half has
     * @param int $room how much room the part gets
     * @param int $held how many groups each half is looked at in
     * @param int $started_held how many groups the part had before
     * @param int $doublings how many times the shortest stretch has
     * @param int $filled which groups of the part below hold something
     * @return array how much each half gets, how the room splits, and
     */
    public function readLean(&$band, $at, $half, $room, $held, $started_held,
        $doublings, &$filled)
    {
        $before = $this->reader->bitsUsedFinely();
        $ceiling = CeltPulseCache::widthLog($this->band) +
            $doublings * (1 << self::BIT_PARTS);
        $offset = ($ceiling >> 1) - self::SPLIT_OFFSET;
        $steps = self::leanSteps($half, $room, $offset, $ceiling);
        $turn = 0;
        if ($steps != 1) {
            if ($started_held > 1) {
                $turn = $this->reader->decodeNumber($steps + 1);
            } else {
                $turn = $this->readTriangular($steps);
            }
            $turn = intdiv($turn * 16384, $steps);
        }
        $spent = $this->reader->bitsUsedFinely() - $before;
        $room -= $spent;
        if ($turn == 0) {
            $mid = 32767 / 32768.0;
            $side = 0.0;
            $filled &= (1 << $held) - 1;
            $gap = -16384;
        } else if ($turn == 16384) {
            $mid = 0.0;
            $side = 32767 / 32768.0;
            $filled &= ((1 << $held) - 1) << $held;
            $gap = 16384;
        } else {
            $across = CeltShape::steadyCos($turn);
            $up = CeltShape::steadyCos(16384 - $turn);
            $mid = $across / 32768.0;
            $side = $up / 32768.0;
            /* How the room divides follows from how far the loudness
               leaned, weighted by how many slots each half has. */
            $gap = CeltShape::fracTimes(($half - 1) << 7,
                CeltShape::leanLog($up, $across));
        }
        $this->room_left -= $spent;
        return ["mid" => $mid, "side" => $side, "gap" => $gap,
            "turn" => $turn, "room" => $room];
    }
    /**
     * readTriangular reads a lean where the middle is more likely than the
     * ends, which is how a split within one group is stored
     *
     * @param int $steps how many steps the lean is stored in
     * @return int which step the lean fell on
     */
    public function readTriangular($steps)
    {
        $half = $steps >> 1;
        $whole = ($half + 1) * ($half + 1);
        $found = $this->reader->decode($whole);
        if ($found < (($half * ($half + 1)) >> 1)) {
            $turn = (self::wholeRoot(8 * $found + 1) - 1) >> 1;
            $width = $turn + 1;
            $below = ($turn * ($turn + 1)) >> 1;
        } else {
            $turn = (2 * ($steps + 1) -
                self::wholeRoot(8 * ($whole - $found - 1) + 1)) >> 1;
            $width = $steps + 1 - $turn;
            $below = $whole -
                ((($steps + 1 - $turn) * ($steps + 2 - $turn)) >> 1);
        }
        $this->reader->update($below, $below + $width, $whole);
        return $turn;
    }
    /**
     * wholeRoot the whole part of a square root, worked out without fractions
     * so that it comes out the same everywhere
     *
     * @param int $value the number to take the root of
     * @return int the whole part of its square root
     */
    public static function wholeRoot($value)
    {
        if ($value <= 0) {
            return 0;
        }
        $root = (int)sqrt($value);
        while ($root * $root > $value) {
            $root--;
        }
        while (($root + 1) * ($root + 1) <= $value) {
            $root++;
        }
        return $root;
    }
    /**
     * leanSteps how many steps a lean is stored in, which depends on how much
     * room the split has to spare
     *
     * @param int $half how many slots each half has
     * @param int $room how much room the part gets
     * @param int $offset how much the split is favored
     * @param int $ceiling the most a shape may cost
     * @return int how many steps
     */
    public static function leanSteps($half, $room, $offset, $ceiling)
    {
        $doubles = [16384, 17866, 19483, 21247, 23170, 25267, 27554, 30048];
        $freedoms = 2 * $half - 1;
        $depth = intdiv($room + $freedoms * $offset, $freedoms);
        $depth = min($room - $ceiling - (4 << self::BIT_PARTS), $depth);
        $depth = min(8 << self::BIT_PARTS, $depth);
        if ($depth < (1 << self::BIT_PARTS >> 1)) {
            return 1;
        }
        $steps = $doubles[$depth & 0x7] >> (14 - ($depth >> self::BIT_PARTS));
        return ($steps + 1) >> 1 << 1;
    }
    /**
     * toTimeOrder lays a band out in time order rather than pitch order order
     * rather than straight through
     *
     * @param array $band the band's slots
     * @param int $each how many slots each group has
     * @param int $groups how many groups there are
     * @param bool $ordered whether the groups are put in a special
     * @return array the band laid out in time order
     */
    public static function toTimeOrder($band, $each, $groups, $ordered)
    {
        $out = array_fill(0, $each * $groups, 0.0);
        $order = $ordered ? self::orderFor($groups) : null;
        for ($group = 0; $group < $groups; $group++) {
            $to = ($order === null) ? $group : $order[$group];
            for ($slot = 0; $slot < $each; $slot++) {
                $out[$to * $each + $slot] = $band[$slot * $groups + $group];
            }
        }
        return $out;
    }
    /**
     * toPitchOrder lays a band back out in pitch order order
     *
     * @param array $band the band's slots
     * @param int $each how many slots each group has
     * @param int $groups how many groups there are
     * @param bool $ordered whether the groups were put in a special
     * @return array the band laid out in pitch order
     */
    public static function toPitchOrder($band, $each, $groups, $ordered)
    {
        $out = array_fill(0, $each * $groups, 0.0);
        $order = $ordered ? self::orderFor($groups) : null;
        for ($group = 0; $group < $groups; $group++) {
            $from = ($order === null) ? $group : $order[$group];
            for ($slot = 0; $slot < $each; $slot++) {
                $out[$slot * $groups + $group] = $band[$from * $each + $slot];
            }
        }
        return $out;
    }
    /**
     * orderFor the order the groups of a band are put in for a given number of
     * groups
     *
     * @param int $groups how many groups there are
     * @return array where each group goes
     */
    public static function orderFor($groups)
    {
        $order = [];
        for ($group = 0; $group < $groups; $group++) {
            $order[] = self::HALF_ORDER[$groups - 2 + $group];
        }
        return $order;
    }
}
