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

/**
 * Fft turns a run of numbers into the mixture of steady tones that would add up
 * to it, and back again. Sound is stored as those tones rather than as the wave
 * itself, because most of a tone can be thrown away without a listener noticing
 * while the same is not true of the wave. Everything that compresses sound
 * therefore does this at some point, and it is the slowest thing any of it
 * does. Working it out one tone at a time costs work proportional to the square
 * of the length; splitting the run into smaller runs and reusing the answers
 * brings that down to roughly the length times its logarithm, which for the
 * lengths Opus uses is a saving of about a hundredfold. Opus works in runs of
 * 60, 120, 240 and 480. Those are not powers of two, so splitting in half alone
 * will not do: the run has to be split three and five ways as well. Splitting
 * by four is kept as its own case because it is much the most common and doing
 * it directly saves a good deal of work over splitting by two twice. The work
 * needed to split a run of a given length is the same every time, so it is
 * worked out once for each length and kept.
 */
class Fft
{
    /**
     * plans stores how the work for each length is split, worked out once per
     * length and kept for reuse
     *
     * @var array
     */
    public static $plans = [];
    /**
     * size stores how many numbers this transform works on. A transform
     * is built for one length and reused for every run of that
     * length
     * @var int
     */
    public $size;
    /**
     * splits stores how the run is split, as pairs saying how many ways and how
     * long each part is.
     * @var array
     */
    public $splits;
    /**
     * turn_across stores the sideways part of the turning factors, one for each
     * step round the circle.
     * @var array
     */
    public $turn_across;
    /**
     * turn_up stores the upward part of the turning factors.
     * @var array
     */
    public $turn_up;
    /**
     * forSize works out how to handle a run of a given length, reusing the
     * answer where one has been worked out before
     *
     * @param int $size how long a run to handle
     * @return object something that can handle runs of that length
     */
    public static function forSize($size)
    {
        if (isset(self::$plans[$size])) {
            return self::$plans[$size];
        }
        $plan = new self($size);
        self::$plans[$size] = $plan;
        return $plan;
    }
    /**
     * __construct works out how to split a run of a given length and the
     * turning factors that splitting needs
     *
     * @param int $size how long a run to handle
     */
    public function __construct($size)
    {
        if ($size < 1) {
            throw new \Exception("A run must have some length");
        }
        $this->size = $size;
        $this->splits = self::splitUp($size);
        $this->turn_across = [];
        $this->turn_up = [];
        for ($i = 0; $i < $size; $i++) {
            $angle = -2.0 * M_PI * $i / $size;
            $this->turn_across[$i] = cos($angle);
            $this->turn_up[$i] = sin($angle);
        }
    }
    /**
     * splitUp works out how to break a length down, taking fours first because
     * they are the cheapest, then twos, then whatever odd numbers are left each
     * part is
     *
     * @param int $size the length to break down
     * @return array pairs saying how many ways to split and how long
     */
    public static function splitUp($size)
    {
        $splits = [];
        $left = $size;
        while ($left > 1) {
            $ways = 0;
            if ($left % 4 == 0) {
                $ways = 4;
            } else if ($left % 2 == 0) {
                $ways = 2;
            } else {
                for ($try = 3; $try * $try <= $left; $try += 2) {
                    if ($left % $try == 0) {
                        $ways = $try;
                        break;
                    }
                }
                if ($ways == 0) {
                    $ways = $left;
                }
            }
            $left = intdiv($left, $ways);
            $splits[] = [$ways, $left];
        }
        return $splits;
    }
    /**
     * Turns a run of numbers into the tones that make it up, or back
     * again
     *
     * @param array $across the sideways part of each number, replaced
     *      by the answer
     * @param array $up the upward part of each number, replaced by the
     *      answer
     * @param bool $backwards whether to go from tones back to numbers
     */
    public function run(&$across, &$up, $backwards = false)
    {
        $out_across = array_fill(0, $this->size, 0.0);
        $out_up = array_fill(0, $this->size, 0.0);
        $this->step($out_across, $out_up, 0, $across, $up, 0, 1, 0,
            $backwards);
        $across = $out_across;
        $up = $out_up;
    }
    /**
     * step handles one level of the splitting: breaks the run into parts,
     * handles each part, then joins the answers back together
     *
     * @param array $out_across where the sideways answers go
     * @param array $out_up where the upward answers go
     * @param int $out_at where in those the answers for this part go
     * @param array $across the sideways part of each number given
     * @param array $up the upward part of each number given
     * @param int $in_at where in those this part starts
     * @param int $spacing how far apart this part's numbers sit
     * @param int $level which level of the splitting this is
     * @param bool $backwards whether to go from tones back to numbers
     */
    public function step(&$out_across, &$out_up, $out_at, &$across, &$up,
        $in_at, $spacing, $level, $backwards)
    {
        $ways = $this->splits[$level][0];
        $part_size = $this->splits[$level][1];
        if ($part_size == 1) {
            for ($i = 0; $i < $ways; $i++) {
                $out_across[$out_at + $i] = $across[$in_at + $i * $spacing];
                $out_up[$out_at + $i] = $up[$in_at + $i * $spacing];
            }
        } else {
            for ($i = 0; $i < $ways; $i++) {
                $this->step($out_across, $out_up, $out_at + $i * $part_size,
                    $across, $up, $in_at + $i * $spacing,
                    $spacing * $ways, $level + 1, $backwards);
            }
        }
        if ($ways == 2) {
            $this->joinTwo($out_across, $out_up, $out_at, $spacing,
                $part_size, $backwards);
        } else if ($ways == 4) {
            $this->joinFour($out_across, $out_up, $out_at, $spacing,
                $part_size, $backwards);
        } else {
            $this->joinAny($out_across, $out_up, $out_at, $spacing,
                $part_size, $ways, $backwards);
        }
    }
    /**
     * joinTwo joins the two halves of a transform back into one run of
     * tones, which is the last step of splitting a long transform
     * into two shorter ones
     *
     * @param array $out_across the sideways answers so far
     * @param array $out_up the upward answers so far
     * @param int $at where in those this join works
     * @param int $spacing how far apart the turning factors step
     * @param int $part_size how long each half is
     * @param bool $backwards whether to go from tones back to numbers
     */
    public function joinTwo(&$out_across, &$out_up, $at, $spacing, $part_size,
        $backwards)
    {
        $sign = $backwards ? -1.0 : 1.0;
        for ($i = 0; $i < $part_size; $i++) {
            $turn = $i * $spacing;
            $turn_across = $this->turn_across[$turn];
            $turn_up = $sign * $this->turn_up[$turn];
            $other = $at + $part_size + $i;
            $here = $at + $i;
            $moved_across = $out_across[$other] * $turn_across -
                $out_up[$other] * $turn_up;
            $moved_up = $out_across[$other] * $turn_up +
                $out_up[$other] * $turn_across;
            $out_across[$other] = $out_across[$here] - $moved_across;
            $out_up[$other] = $out_up[$here] - $moved_up;
            $out_across[$here] += $moved_across;
            $out_up[$here] += $moved_up;
        }
    }
    /**
     * joinFour joins four quarters back together, which is the common case and
     * so is done directly rather than as two joins of two
     *
     * @param array $out_across the sideways answers so far
     * @param array $out_up the upward answers so far
     * @param int $at where in those this join works
     * @param int $spacing how far apart the turning factors step
     * @param int $part_size how long each quarter is
     * @param bool $backwards whether to go from tones back to numbers
     */
    public function joinFour(&$out_across, &$out_up, $at, $spacing,
        $part_size, $backwards)
    {
        $sign = $backwards ? -1.0 : 1.0;
        for ($i = 0; $i < $part_size; $i++) {
            $moved = [];
            for ($step = 1; $step <= 3; $step++) {
                $turn = $i * $spacing * $step;
                $turn_across = $this->turn_across[$turn];
                $turn_up = $sign * $this->turn_up[$turn];
                $from = $at + $step * $part_size + $i;
                $moved[$step] = [$out_across[$from] * $turn_across -
                    $out_up[$from] * $turn_up,
                    $out_across[$from] * $turn_up +
                    $out_up[$from] * $turn_across];
            }
            $here = $at + $i;
            $across_difference = $out_across[$here] - $moved[2][0];
            $up_difference = $out_up[$here] - $moved[2][1];
            $out_across[$here] += $moved[2][0];
            $out_up[$here] += $moved[2][1];
            $sum_across = $moved[1][0] + $moved[3][0];
            $sum_up = $moved[1][1] + $moved[3][1];
            $gap_across = $moved[1][0] - $moved[3][0];
            $gap_up = $moved[1][1] - $moved[3][1];
            $out_across[$at + 2 * $part_size + $i] =
                $out_across[$here] - $sum_across;
            $out_up[$at + 2 * $part_size + $i] = $out_up[$here] - $sum_up;
            $out_across[$here] += $sum_across;
            $out_up[$here] += $sum_up;
            $out_across[$at + $part_size + $i] =
                $across_difference + $sign * $gap_up;
            $out_up[$at + $part_size + $i] = $up_difference - $sign *
                $gap_across;
            $out_across[$at + 3 * $part_size + $i] =
                $across_difference - $sign * $gap_up;
            $out_up[$at + 3 * $part_size + $i] =
                $up_difference + $sign * $gap_across;
        }
    }
    /**
     * joinAny joins any other number of parts back together, used for the
     * threes and fives Opus needs
     *
     * @param array $out_across the sideways answers so far
     * @param array $out_up the upward answers so far
     * @param int $at where in those this join works
     * @param int $spacing how far apart the turning factors step
     * @param int $part_size how long each part is
     * @param int $ways how many parts there are
     * @param bool $backwards whether to go from tones back to numbers
     */
    public function joinAny(&$out_across, &$out_up, $at, $spacing, $part_size,
        $ways, $backwards)
    {
        $sign = $backwards ? -1.0 : 1.0;
        $size = $this->size;
        for ($i = 0; $i < $part_size; $i++) {
            $held_across = [];
            $held_up = [];
            $from = $i;
            for ($j = 0; $j < $ways; $j++) {
                $held_across[$j] = $out_across[$at + $from];
                $held_up[$j] = $out_up[$at + $from];
                $from += $part_size;
            }
            $to = $i;
            for ($j = 0; $j < $ways; $j++) {
                $turn = 0;
                $total_across = $held_across[0];
                $total_up = $held_up[0];
                for ($k = 1; $k < $ways; $k++) {
                    $turn += $spacing * $to;
                    if ($turn >= $size) {
                        $turn -= $size;
                    }
                    $turn_across = $this->turn_across[$turn];
                    $turn_up = $sign * $this->turn_up[$turn];
                    $total_across += $held_across[$k] * $turn_across -
                        $held_up[$k] * $turn_up;
                    $total_up += $held_across[$k] * $turn_up +
                        $held_up[$k] * $turn_across;
                }
                $out_across[$at + $to] = $total_across;
                $out_up[$at + $to] = $total_up;
                $to += $part_size;
            }
        }
    }
}
