Update kiss-fft to 1.4.0 and disable OpenMP for it.

11 files changed, 156 insertions, 91 deletions

diff --git a/media/kiss_fft/BACKGROUND b/media/kiss_fft/BACKGROUND
new file mode 100644
index 000000000..dd43fa535
--- /dev/null
+++ b/media/kiss_fft/BACKGROUND
@@ -0,0 +1,25 @@
+BACKGROUND:
+
+    I started coding this because I couldn't find a fixed point FFT that didn't 
+use assembly code.  I started with floating point numbers so I could get the 
+theory straight before working on fixed point issues.  In the end, I had a 
+little bit of code that could be recompiled easily to do ffts with short, float
+or double (other types should be easy too).  
+
+    Once I got my FFT working, I was curious about the speed compared to
+a well respected and highly optimized fft library.  I don't want to criticize 
+this great library, so let's call it FFT_BRANDX.
+During this process, I learned:
+
+    1. FFT_BRANDX has more than 100K lines of code. The core of kiss_fft is about 500 lines (cpx 1-d).
+    2. It took me an embarrassingly long time to get FFT_BRANDX working.
+    3. A simple program using FFT_BRANDX is 522KB. A similar program using kiss_fft is 18KB (without optimizing for size).
+    4. FFT_BRANDX is roughly twice as fast as KISS FFT in default mode.
+
+    It is wonderful that free, highly optimized libraries like FFT_BRANDX exist.
+But such libraries carry a huge burden of complexity necessary to extract every 
+last bit of performance.
+
+    Sometimes simpler is better, even if it's not better.
+    
+    -- Mark Borgerding
\ No newline at end of file
diff --git a/media/kiss_fft/CHANGELOG b/media/kiss_fft/CHANGELOG
index 2dd360375..5a77c34e2 100644
--- a/media/kiss_fft/CHANGELOG
+++ b/media/kiss_fft/CHANGELOG
@@ -1,3 +1,8 @@
+1.4.0 2017-10-26
+  Forked from the original library, relicensed under the unmodified BSD 3-clause license.
+  Fixed stack exhaustion/corruption when using parallelization.
+  Fixed buffer corruption when using parallelization.
+
 1.3.0 2012-07-18
   removed non-standard malloc.h from kiss_fft.h
 
diff --git a/media/kiss_fft/COPYING b/media/kiss_fft/COPYING
deleted file mode 100644
index 2fc6685a6..000000000
--- a/media/kiss_fft/COPYING
+++ /dev/null
@@ -1,11 +0,0 @@
-Copyright (c) 2003-2010 Mark Borgerding
-
-All rights reserved.
-
-Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:
-
-    * Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
-    * Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.
-    * Neither the author nor the names of any contributors may be used to endorse or promote products derived from this software without specific prior written permission.
-
-THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
diff --git a/media/kiss_fft/LICENSE b/media/kiss_fft/LICENSE
new file mode 100644
index 000000000..ad9ce33b9
--- /dev/null
+++ b/media/kiss_fft/LICENSE
@@ -0,0 +1,25 @@
+Copyright (c) 2003-2010 Mark Borgerding
+Copyright (c) 2017 Mark Straver BASc
+
+Redistribution and use in source and binary forms, with or without modification,
+are permitted provided that the following conditions are met:
+
+    * Redistributions of source code must retain the above copyright notice,
+      this list of conditions and the following disclaimer.
+    * Redistributions in binary form must reproduce the above copyright notice,
+      this list of conditions and the following disclaimer in the documentation
+      and/or other materials provided with the distribution.
+    * Neither the author nor the names of any contributors may be used to
+      endorse or promote products derived from this software without specific
+      prior written permission.
+
+THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
+ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 
+WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 
+DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR 
+ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 
+(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 
+LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON 
+ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 
+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 
+SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
diff --git a/media/kiss_fft/Makefile.in b/media/kiss_fft/Makefile.in
new file mode 100644
index 000000000..eabc66309
--- /dev/null
+++ b/media/kiss_fft/Makefile.in
@@ -0,0 +1,14 @@
+# This Source Code Form is subject to the terms of the Mozilla Public
+# License, v. 2.0. If a copy of the MPL was not distributed with this
+# file, You can obtain one at http://mozilla.org/MPL/2.0/.
+
+include $(topsrcdir)/config/rules.mk
+
+# We don't want OpenMP for KISS-FFT
+ifeq ($(OS_ARCH),WINNT)
+  CFLAGS := $(filter-out -openmp,$(CFLAGS))
+endif
+
+ifdef GNU_CC
+  CFLAGS := $(filter-out -ftree-parallelize-loops -fopenmp,$(CFLAGS))
+endif
diff --git a/media/kiss_fft/README b/media/kiss_fft/README
index 03b2e7a9c..b18d62a02 100644
--- a/media/kiss_fft/README
+++ b/media/kiss_fft/README
@@ -44,30 +44,6 @@ The core fft and most tools/ code can be compiled to use float, double,
  Q15 short or Q31 samples. The default is float.
 
 
-BACKGROUND:
-
-    I started coding this because I couldn't find a fixed point FFT that didn't 
-use assembly code.  I started with floating point numbers so I could get the 
-theory straight before working on fixed point issues.  In the end, I had a 
-little bit of code that could be recompiled easily to do ffts with short, float
-or double (other types should be easy too).  
-
-    Once I got my FFT working, I was curious about the speed compared to
-a well respected and highly optimized fft library.  I don't want to criticize 
-this great library, so let's call it FFT_BRANDX.
-During this process, I learned:
-
-    1. FFT_BRANDX has more than 100K lines of code. The core of kiss_fft is about 500 lines (cpx 1-d).
-    2. It took me an embarrassingly long time to get FFT_BRANDX working.
-    3. A simple program using FFT_BRANDX is 522KB. A similar program using kiss_fft is 18KB (without optimizing for size).
-    4. FFT_BRANDX is roughly twice as fast as KISS FFT in default mode.
-
-    It is wonderful that free, highly optimized libraries like FFT_BRANDX exist.
-But such libraries carry a huge burden of complexity necessary to extract every 
-last bit of performance.
-
-    Sometimes simpler is better, even if it's not better.
-
 FREQUENTLY ASKED QUESTIONS:
 	Q: Can I use kissfft in a project with a ___ license?
 	A: Yes.  See LICENSE below.
@@ -78,10 +54,6 @@ FREQUENTLY ASKED QUESTIONS:
 		2) mixed build environment -- all code must be compiled with same preprocessor 
 		definitions for FIXED_POINT and kiss_fft_scalar
 
-	Q: Will you write/debug my code for me?
-	A: Probably not unless you pay me.  I am happy to answer pointed and topical questions, but 
-	I may refer you to a book, a forum, or some other resource.
-
 
 PERFORMANCE:
     (on Athlon XP 2100+, with gcc 2.96, float data type)
@@ -111,24 +83,25 @@ UNDER THE HOOD:
     FFTs in parallel (packed into real&imag), and then combines them via twiddling.  The result is 
     nfft/2+1 complex frequency bins from DC to Nyquist.  If you don't know what this means, search the web.
 
-    The fast convolution filtering uses the overlap-scrap method, slightly 
-    modified to put the scrap at the tail.
+    The fast convolution filtering uses the overlap-scrap method, slightly modified to put
+    the scrap at the tail.
 
 LICENSE:
-    Revised BSD License, see COPYING for verbiage. 
+    BSD-3-Clause License, see LICENSE for verbiage. 
     Basically, "free to use&change, give credit where due, no guarantees"
     Note this license is compatible with GPL at one end of the spectrum and closed, commercial software at 
     the other end.  See http://www.fsf.org/licensing/licenses
-
-    A commercial license is available which removes the requirement for attribution.  Contact me for details.
-
-  
-TODO:
+    
+    This fork of the library always requires attribution. Contrary to the original version of the library,
+    written by a sole developer, no exception to the license is available that allows use without attribution
+    because of contributed code.
+ 
+TO-DO:
     *) Add real optimization for odd length FFTs 
     *) Document/revisit the input/output fft scaling
     *) Make doc describing the overlap (tail) scrap fast convolution filtering in kiss_fastfir.c
     *) Test all the ./tools/ code with fixed point (kiss_fastfir.c doesn't work, maybe others)
 
-AUTHOR:
-    Mark Borgerding
-    Mark@Borgerding.net
+AUTHORS:
+    Mark Borgerding (mark@borgerding.net)
+    Mark Straver BASc (moonchild@palemoon.org)
diff --git a/media/kiss_fft/README_MOZILLA b/media/kiss_fft/README_MOZILLA
index a2fd35d6a..c6e00926d 100644
--- a/media/kiss_fft/README_MOZILLA
+++ b/media/kiss_fft/README_MOZILLA
@@ -1,8 +1,8 @@
-The source from this directory was copied from the kissfft hg repository using
+The source from this directory was copied from the kissfft github repository using
 the update.sh script.  The only changes made were those applied by update.sh
 and the addition of moz.build and Makefile.in build files for the Mozilla build
 system.
 
-The kissfft hg repository is: http://hg.code.sf.net/p/kissfft/code
+The kissfft git repository is: https://github.com/MoonchildProductions/kissfft
 
-The hg revision ID used was fbe1bb0bc7b94ec252842b8b7e3f3347ec75d92f.
+The git commit used was fa1bf9189dc84f960d4e56c0bed25d961c0ccb76.
diff --git a/media/kiss_fft/kiss_fft.c b/media/kiss_fft/kiss_fft.c
index 465d6c97a..df818dad3 100644
--- a/media/kiss_fft/kiss_fft.c
+++ b/media/kiss_fft/kiss_fft.c
@@ -1,15 +1,29 @@
 /*
-Copyright (c) 2003-2010, Mark Borgerding
-
-All rights reserved.
-
-Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:
-
-    * Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
-    * Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.
-    * Neither the author nor the names of any contributors may be used to endorse or promote products derived from this software without specific prior written permission.
-
-THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+Copyright (c) 2003-2010 Mark Borgerding
+Copyright (c) 2017 Mark Straver BASc
+
+Redistribution and use in source and binary forms, with or without modification,
+are permitted provided that the following conditions are met:
+
+    * Redistributions of source code must retain the above copyright notice,
+      this list of conditions and the following disclaimer.
+    * Redistributions in binary form must reproduce the above copyright notice,
+      this list of conditions and the following disclaimer in the documentation
+      and/or other materials provided with the distribution.
+    * Neither the author nor the names of any contributors may be used to
+      endorse or promote products derived from this software without specific
+      prior written permission.
+
+THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
+ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 
+WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 
+DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR 
+ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 
+(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 
+LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON 
+ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 
+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 
+SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
 */
 
 
@@ -203,6 +217,10 @@ static void kf_bfly_generic(
         int p
         )
 {
+#ifdef _OPENMP
+#pragma omp critical (bfly_generic)
+  {
+#endif
     int u,k,q1,q;
     kiss_fft_cpx * twiddles = st->twiddles;
     kiss_fft_cpx t;
@@ -232,6 +250,9 @@ static void kf_bfly_generic(
         }
     }
     KISS_FFT_TMP_FREE(scratch);
+#ifdef _OPENMP
+  }
+#endif
 }
 
 static
@@ -252,7 +273,7 @@ void kf_work(
 #ifdef _OPENMP
     // use openmp extensions at the 
     // top-level (not recursive)
-    if (fstride==1 && p<=5)
+    if (fstride==1 && p<=5 && m!=1)
     {
         int k;
 
diff --git a/media/kiss_fft/kiss_fftr.c b/media/kiss_fft/kiss_fftr.c
index b8e238b1e..184f979d1 100644
--- a/media/kiss_fft/kiss_fftr.c
+++ b/media/kiss_fft/kiss_fftr.c
@@ -1,15 +1,29 @@
 /*
-Copyright (c) 2003-2004, Mark Borgerding
-
-All rights reserved.
-
-Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:
-
-    * Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
-    * Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.
-    * Neither the author nor the names of any contributors may be used to endorse or promote products derived from this software without specific prior written permission.
-
-THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+Copyright (c) 2003-2010 Mark Borgerding
+Copyright (c) 2017 Mark Straver BASc
+
+Redistribution and use in source and binary forms, with or without modification,
+are permitted provided that the following conditions are met:
+
+    * Redistributions of source code must retain the above copyright notice,
+      this list of conditions and the following disclaimer.
+    * Redistributions in binary form must reproduce the above copyright notice,
+      this list of conditions and the following disclaimer in the documentation
+      and/or other materials provided with the distribution.
+    * Neither the author nor the names of any contributors may be used to
+      endorse or promote products derived from this software without specific
+      prior written permission.
+
+THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
+ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 
+WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 
+DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR 
+ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 
+(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 
+LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON 
+ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 
+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 
+SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 
 #include "kiss_fftr.h"
diff --git a/media/kiss_fft/moz.build b/media/kiss_fft/moz.build
index 798240b91..3dcf9123a 100644
--- a/media/kiss_fft/moz.build
+++ b/media/kiss_fft/moz.build
@@ -1,4 +1,4 @@
-# -*- Mode: python; indent-tabs-mode: nil; tab-width: 40 -*-
+# -*- Mode: python; c-basic-offset: 4; indent-tabs-mode: nil; tab-width: 40 -*-
 # vim: set filetype=python:
 # This Source Code Form is subject to the terms of the Mozilla Public
 # License, v. 2.0. If a copy of the MPL was not distributed with this
@@ -14,4 +14,12 @@ SOURCES += [
     'kiss_fftr.c',
 ]
 
+# kiss_fft causes OOM error with some 32bit versions of GCC when using -O2
+if '64' not in CONFIG['OS_TEST']:
+    if CONFIG['GNU_CC']:
+        CFLAGS += ['-O1']
+
+if CONFIG['GKMEDIAS_SHARED_LIBRARY']:
+    NO_VISIBILITY_FLAGS = True
+
 FINAL_LIBRARY = 'xul'
diff --git a/media/kiss_fft/update.sh b/media/kiss_fft/update.sh
index e11a7406d..5829b82a4 100755
--- a/media/kiss_fft/update.sh
+++ b/media/kiss_fft/update.sh
@@ -6,10 +6,11 @@ if [ ! -d "$1" ]; then
   exit 1
 fi
 
-FILES="CHANGELOG \
-       COPYING \
+FILES="docs/CHANGELOG \
+       LICENSE \
        README \
-       README.simd \
+       docs/README.simd \
+       docs/BACKGROUND \
        _kiss_fft_guts.h \
        kiss_fft.c \
        kiss_fft.h \
@@ -20,15 +21,5 @@ for file in $FILES; do
   cp "$1/$file" .
 done
 
-if [ -d "$1/.hg" ]; then
-  rev=$(cd "$1" && hg log --template='{node}' -r `hg identify -i`)
-fi
-
-if [ -n "$rev" ]; then
-  version=$rev
-  sed -i.bak -e "/The hg revision ID used was/ s/[0-9a-f]\{40\}\./$version./" README_MOZILLA
-  rm README_MOZILLA.bak
-else
-  echo "Remember to update README_MOZILLA with the version details."
-fi
+echo "Remember to update README_MOZILLA with the version details."