<?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;
}
}
}
}
(c) 2026 Seekquarry - Open Source Search Engine Software