<?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\tests;
use seekquarry\yioop\library\av_processing\Fft;
use seekquarry\yioop\library\UnitTest;
/**
* Checks that turning a run of numbers into the tones that make it up
* gives the same answer as working each tone out one at a time.
*
* Working one tone out at a time is the definition, so it is what the
* fast way has to agree with. The fast way is checked at the four
* lengths Opus uses, at a length that is a prime, and at lengths that
* need each of the ways of splitting, since a fault in one way of
* splitting would otherwise hide behind the others.
*
* @author Chris Pollett
*/
class FftTest extends UnitTest
{
/**
* How close the fast way has to come to the definition, allowing
* for rounding as the numbers are added up
*/
const CLOSE_ENOUGH = 1e-9;
/**
* The lengths Opus works in
*/
const OPUS_LENGTHS = [60, 120];
/**
* The longest length Opus works in. Working every tone of it out
* one at a time takes long enough to be worth avoiding, so it is
* checked at a few tones rather than all of them.
*/
const LONGER_OPUS_LENGTHS = [240, 480];
/**
* Which tones of that longest length to check
*/
const SAMPLED_TONES = [0, 1, 2, 37, 239, 240, 478, 479];
/**
* A starting point for the made up numbers, so a failing case
* fails the same way every time
*/
const SEED = 20260803;
/**
* Sets the made up numbers off from the same place every run
*/
public function setUp()
{
mt_srand(self::SEED);
}
/**
* Nothing needs clearing away after these cases
*/
public function tearDown()
{
}
/**
* Works out the tones one at a time, which is the definition the
* fast way has to agree with
*
* @param array $across the sideways part of each number
* @param array $up the upward part of each number
* @param bool $backwards whether to go the other way
* @return array the tones, as sideways and upward parts
*/
public function oneAtATime($across, $up, $backwards)
{
$size = count($across);
$out_across = [];
$out_up = [];
$sign = $backwards ? 2.0 : -2.0;
for ($i = 0; $i < $size; $i++) {
$total_across = 0.0;
$total_up = 0.0;
for ($j = 0; $j < $size; $j++) {
$angle = $sign * M_PI * $i * $j / $size;
$total_across += $across[$j] * cos($angle) -
$up[$j] * sin($angle);
$total_up += $across[$j] * sin($angle) +
$up[$j] * cos($angle);
}
$out_across[] = $total_across;
$out_up[] = $total_up;
}
return [$out_across, $out_up];
}
/**
* Makes up a run of numbers to work on
*
* @param int $size how long a run to make
* @return array the sideways and upward parts
*/
public function madeUpRun($size)
{
$across = [];
$up = [];
for ($i = 0; $i < $size; $i++) {
$across[] = mt_rand(-1000, 1000) / 1000.0;
$up[] = mt_rand(-1000, 1000) / 1000.0;
}
return [$across, $up];
}
/**
* How far the fast way strays from the definition at one length
*
* @param int $size how long a run to try
* @param bool $backwards whether to go the other way
* @return float the largest difference found
*/
public function strayAt($size, $backwards)
{
list($across, $up) = $this->madeUpRun($size);
list($want_across, $want_up) = $this->oneAtATime($across, $up,
$backwards);
$got_across = $across;
$got_up = $up;
Fft::forSize($size)->run($got_across, $got_up, $backwards);
$stray = 0.0;
for ($i = 0; $i < $size; $i++) {
$stray = max($stray, abs($want_across[$i] - $got_across[$i]),
abs($want_up[$i] - $got_up[$i]));
}
return $stray;
}
/**
* At the four lengths Opus works in, the fast way should agree
* with the definition both ways round
*/
public function opusLengthsTestCase()
{
foreach (self::OPUS_LENGTHS as $size) {
$this->assertTrue($this->strayAt($size, false) <
self::CLOSE_ENOUGH, "length $size going forward");
$this->assertTrue($this->strayAt($size, true) <
self::CLOSE_ENOUGH, "length $size going back");
}
}
/**
* At the longer lengths Opus works in, a scattering of tones
* should match what working those tones out one at a time gives
*/
public function longerOpusLengthsTestCase()
{
foreach (self::LONGER_OPUS_LENGTHS as $size) {
$this->checkSampledTones($size);
}
}
/**
* Checks a few tones of one length against the definition, rather
* than every tone, since working out every tone of a long run
* costs more than the whole rest of these cases together
*
* @param int $size how long a run to check
*/
public function checkSampledTones($size)
{
list($across, $up) = $this->madeUpRun($size);
$got_across = $across;
$got_up = $up;
Fft::forSize($size)->run($got_across, $got_up);
$stray = 0.0;
foreach (self::SAMPLED_TONES as $tone) {
if ($tone >= $size) {
continue;
}
$total_across = 0.0;
$total_up = 0.0;
for ($j = 0; $j < $size; $j++) {
$angle = -2.0 * M_PI * $tone * $j / $size;
$total_across += $across[$j] * cos($angle) -
$up[$j] * sin($angle);
$total_up += $across[$j] * sin($angle) +
$up[$j] * cos($angle);
}
$stray = max($stray, abs($total_across - $got_across[$tone]),
abs($total_up - $got_up[$tone]));
}
$this->assertTrue($stray < self::CLOSE_ENOUGH,
"length $size matches the definition where checked");
}
/**
* Each way of splitting should be right on its own, so lengths are
* tried that need one way and not the others
*/
public function eachWayOfSplittingTestCase()
{
$lengths = [2, 3, 4, 5, 8, 9, 16, 25, 27];
foreach ($lengths as $size) {
$this->assertTrue($this->strayAt($size, false) <
self::CLOSE_ENOUGH, "length $size going forward");
}
}
/**
* A length that will not split at all has to be handled by the
* definition itself, and should still come out right
*/
public function lengthThatWillNotSplitTestCase()
{
foreach ([7, 11, 13, 17] as $size) {
$this->assertTrue($this->strayAt($size, false) <
self::CLOSE_ENOUGH, "prime length $size");
}
}
/**
* Going one way and then the other should give back what was
* started with, once the growth the second pass adds is taken off
*/
public function thereAndBackTestCase()
{
foreach ([60, 120, 480] as $size) {
list($across, $up) = $this->madeUpRun($size);
$there_across = $across;
$there_up = $up;
$plan = Fft::forSize($size);
$plan->run($there_across, $there_up, false);
$plan->run($there_across, $there_up, true);
$stray = 0.0;
for ($i = 0; $i < $size; $i++) {
$stray = max($stray,
abs($across[$i] - $there_across[$i] / $size),
abs($up[$i] - $there_up[$i] / $size));
}
$this->assertTrue($stray < self::CLOSE_ENOUGH,
"length $size came back as it went in");
}
}
/**
* A run of the same number over and over is made of one steady
* tone and nothing else, which is a check that does not depend on
* the definition being worked out again
*/
public function steadyRunIsOneToneTestCase()
{
$size = 120;
$across = array_fill(0, $size, 2.5);
$up = array_fill(0, $size, 0.0);
Fft::forSize($size)->run($across, $up);
$this->assertTrue(abs($across[0] - 2.5 * $size) <
self::CLOSE_ENOUGH, "the steady part holds the whole of it");
$rest = 0.0;
for ($i = 1; $i < $size; $i++) {
$rest = max($rest, abs($across[$i]), abs($up[$i]));
}
$this->assertTrue($rest < self::CLOSE_ENOUGH,
"no other tone is present");
}
/**
* Working out how to handle a length is done once and kept, since
* doing it again for every stretch of a recording would cost more
* than the transform itself
*/
public function workingOutIsKeptTestCase()
{
$first = Fft::forSize(480);
$second = Fft::forSize(480);
$this->assertTrue($first === $second,
"the same length gives back the same working out");
$this->assertEqual(Fft::splitUp(480), [[4, 120], [4, 30], [2, 15],
[3, 5], [5, 1]], "480 splits by fours first, then the rest");
$this->assertEqual(Fft::splitUp(60), [[4, 15], [3, 5], [5, 1]],
"60 splits into a four, a three and a five");
}
}
(c) 2026 Seekquarry - Open Source Search Engine Software