From bcfd774b9d980de45afa643f1c734f799770a870 Mon Sep 17 00:00:00 2001 From: Jukka Ojanen Date: Sun, 16 Nov 2014 14:59:46 +0200 Subject: Rename src/ffts.h to src/ffts_internal.h to avoid conflicts with include/ffts.h --- src/ffts_internal.h | 238 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 238 insertions(+) create mode 100644 src/ffts_internal.h (limited to 'src/ffts_internal.h') diff --git a/src/ffts_internal.h b/src/ffts_internal.h new file mode 100644 index 0000000..a8e27b8 --- /dev/null +++ b/src/ffts_internal.h @@ -0,0 +1,238 @@ +/* + + This file is part of FFTS -- The Fastest Fourier Transform in the South + + Copyright (c) 2012, Anthony M. Blake + Copyright (c) 2012, The University of Waikato + + 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 name of the organization nor the + names of its 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 ANTHONY M. BLAKE 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. + +*/ + +#ifndef __CP_SSE_H__ +#define __CP_SSE_H__ + +//#include "config.h" +//#include "codegen.h" +#include "ffts_attributes.h" +#include "types.h" + +#include +#include +#include +#include +#include +#include + +#define FFTS_PREFIX ffts + +#ifndef FFTS_CAT_PREFIX2 +#define FFTS_CAT_PREFIX2(a,b) a ## b +#endif + +#ifndef FFTS_CAT_PREFIX +#define FFTS_CAT_PREFIX(a,b) FFTS_CAT_PREFIX2(a ## _, b) +#endif + +/* prevent symbol name clashes */ +#ifdef FFTS_PREFIX +#define FUNC_TO_REWRITE FFTS_CAT_PREFIX(FFTS_PREFIX, FUNC_TO_REWRITE) +#endif + +#ifdef __ANDROID__ +#include +#define LOG(s) __android_log_print(ANDROID_LOG_ERROR, "FFTS", s) +#else +#define LOG(s) fprintf(stderr, s) +#endif + +#ifndef M_PI +#define M_PI 3.1415926535897932384626433832795028841971693993751058209 +#endif + +typedef struct _ffts_plan_t ffts_plan_t; + +typedef void (*transform_func_t)(ffts_plan_t *p, const void *in, void *out); + +/** + * Contains all the Information need to perform FFT + * + * + * DO NOT CHANGE THE ORDER OF MEMBERS + * ASSEMBLY CODE USES HARD CODED OFFSETS TO REFERENCE + * SOME OF THESE VARIABES!! + */ +struct _ffts_plan_t { + + /** + * + */ + ptrdiff_t *offsets; +#ifdef DYNAMIC_DISABLED + /** + * Twiddle factors + */ + void *ws; + + /** + * ee - 2 size x size8 + * oo - 2 x size4 in parallel + * oe - + */ + void *oe_ws, *eo_ws, *ee_ws; +#else + void FFTS_ALIGN(32) *ws; + void FFTS_ALIGN(32) *oe_ws, *eo_ws, *ee_ws; +#endif + + /** + * Pointer into an array of precomputed indexes for the input data array + */ + ptrdiff_t *is; + + /** + * Twiddle Factor Indexes + */ + size_t *ws_is; + + /** + * Size of the loops for the base cases + */ + size_t i0, i1, n_luts; + + /** + * Size fo the Transform + */ + size_t N; + void *lastlut; + + /** + * Used in multidimensional Code ?? + */ + size_t *transforms; + + /** + * Pointer to the dynamically generated function + * that will execute the FFT + */ + transform_func_t transform; + + /** + * Pointer to the base memory address of + * of the transform function + */ + void *transform_base; + + /** + * Size of the memory block contain the + * generated code + */ + size_t transform_size; + + /** + * Points to the cosnant variables used by + * the Assembly Code + */ + void *constants; + + // multi-dimensional stuff: + struct _ffts_plan_t **plans; + int rank; + size_t *Ns, *Ms; + void *buf; + + void *transpose_buf; + + /** + * Pointer to the destroy function + * to clean up the plan after use + * (differs for real and multi dimension transforms + */ + void (*destroy)(ffts_plan_t *); + + /** + * Coefficiants for the real valued transforms + */ + float *A, *B; + + size_t i2; +}; + +static FFTS_INLINE void *ffts_aligned_malloc(size_t size) +{ +#if defined(_MSC_VER) + return _aligned_malloc(size, 32); +#else + return valloc(size); +#endif +} + +static FFTS_INLINE void ffts_aligned_free(void *p) +{ +#if defined(_MSC_VER) + _aligned_free(p); +#else + free(p); +#endif +} + +#if GCC_VERSION_AT_LEAST(3,3) +#define ffts_ctzl __builtin_ctzl +#elif defined(_MSC_VER) +#include +#ifdef _M_X64 +#pragma intrinsic(_BitScanForward64) +static __inline unsigned long ffts_ctzl(size_t N) +{ + unsigned long count; + _BitScanForward64((unsigned long*) &count, N); + return count; +} +#else +#pragma intrinsic(_BitScanForward) +static __inline unsigned long ffts_ctzl(size_t N) +{ + unsigned long count; + _BitScanForward((unsigned long*) &count, N); + return count; +} +#endif /* _WIN64 */ +#endif /* _MSC_VER */ + +static FFTS_ALWAYS_INLINE float W_re(float N, float k) +{ + return cos(-2.0 * M_PI * k / N); +} + +static FFTS_ALWAYS_INLINE float W_im(float N, float k) +{ + return sin(-2.0 * M_PI * k / N); +} + +void ffts_free(ffts_plan_t *); +void ffts_execute(ffts_plan_t *, const void *, void *); +ffts_plan_t *ffts_init_1d(size_t N, int sign); + +#endif -- cgit v1.1 From b77da5c3a3342bbb9ddb2bfe75ea8633016ac2da Mon Sep 17 00:00:00 2001 From: Jukka Ojanen Date: Sun, 16 Nov 2014 18:20:51 +0200 Subject: Follow the "one definition rule" --- src/ffts_internal.h | 10 +++------- 1 file changed, 3 insertions(+), 7 deletions(-) (limited to 'src/ffts_internal.h') diff --git a/src/ffts_internal.h b/src/ffts_internal.h index a8e27b8..68a08db 100644 --- a/src/ffts_internal.h +++ b/src/ffts_internal.h @@ -31,8 +31,8 @@ */ -#ifndef __CP_SSE_H__ -#define __CP_SSE_H__ +#ifndef FFTS_INTERNAL_H +#define FFTS_INTERNAL_H //#include "config.h" //#include "codegen.h" @@ -231,8 +231,4 @@ static FFTS_ALWAYS_INLINE float W_im(float N, float k) return sin(-2.0 * M_PI * k / N); } -void ffts_free(ffts_plan_t *); -void ffts_execute(ffts_plan_t *, const void *, void *); -ffts_plan_t *ffts_init_1d(size_t N, int sign); - -#endif +#endif /* FFTS_INTERNAL_H */ -- cgit v1.1 From 71f1f4dae77c2f6b335c3e06c13a3ecedf73ccda Mon Sep 17 00:00:00 2001 From: Jukka Ojanen Date: Mon, 17 Nov 2014 15:39:46 +0200 Subject: Fix redefinition of ffts_plan_t --- src/ffts_internal.h | 2 -- 1 file changed, 2 deletions(-) (limited to 'src/ffts_internal.h') diff --git a/src/ffts_internal.h b/src/ffts_internal.h index 68a08db..413bb51 100644 --- a/src/ffts_internal.h +++ b/src/ffts_internal.h @@ -72,8 +72,6 @@ #define M_PI 3.1415926535897932384626433832795028841971693993751058209 #endif -typedef struct _ffts_plan_t ffts_plan_t; - typedef void (*transform_func_t)(ffts_plan_t *p, const void *in, void *out); /** -- cgit v1.1 From df3e73b193429e9b3db977a3aa67a77a0155e39c Mon Sep 17 00:00:00 2001 From: Jukka Ojanen Date: Tue, 10 Mar 2015 11:31:53 +0200 Subject: Remove FFTS plan variable 'transforms', which is not used --- src/ffts_internal.h | 5 ----- 1 file changed, 5 deletions(-) (limited to 'src/ffts_internal.h') diff --git a/src/ffts_internal.h b/src/ffts_internal.h index 413bb51..a77fb0d 100644 --- a/src/ffts_internal.h +++ b/src/ffts_internal.h @@ -127,11 +127,6 @@ struct _ffts_plan_t { void *lastlut; /** - * Used in multidimensional Code ?? - */ - size_t *transforms; - - /** * Pointer to the dynamically generated function * that will execute the FFT */ -- cgit v1.1 From ebae52c72d3488d123c6ca9e31dfd95872d0575c Mon Sep 17 00:00:00 2001 From: Jukka Ojanen Date: Tue, 10 Mar 2015 12:19:38 +0200 Subject: Check existence of various headers and add guards for them --- src/ffts_internal.h | 7 +++++++ 1 file changed, 7 insertions(+) (limited to 'src/ffts_internal.h') diff --git a/src/ffts_internal.h b/src/ffts_internal.h index a77fb0d..2007242 100644 --- a/src/ffts_internal.h +++ b/src/ffts_internal.h @@ -42,8 +42,15 @@ #include #include #include + +#ifdef HAVE_STDINT_H #include +#endif + +#ifdef HAVE_STDLIB_H #include +#endif + #include #define FFTS_PREFIX ffts -- cgit v1.1 From 7ab9d5cc36798afd58accdf589a9004fa0ed49f0 Mon Sep 17 00:00:00 2001 From: Jukka Ojanen Date: Tue, 10 Mar 2015 13:01:29 +0200 Subject: Removal of 'transforms' broke dynamic code --- src/ffts_internal.h | 2 ++ 1 file changed, 2 insertions(+) (limited to 'src/ffts_internal.h') diff --git a/src/ffts_internal.h b/src/ffts_internal.h index 2007242..3e788f8 100644 --- a/src/ffts_internal.h +++ b/src/ffts_internal.h @@ -133,6 +133,8 @@ struct _ffts_plan_t { size_t N; void *lastlut; + size_t *temporary_fix_as_dynamic_code_assumes_fixed_offset; + /** * Pointer to the dynamically generated function * that will execute the FFT -- cgit v1.1 From 2014019a6760e712a019ba639e76aaa8729d8843 Mon Sep 17 00:00:00 2001 From: Jukka Ojanen Date: Thu, 19 Mar 2015 13:38:40 +0200 Subject: To support building for Windows with MinGW, don't assume MSVC to be the compiler --- src/ffts_internal.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/ffts_internal.h') diff --git a/src/ffts_internal.h b/src/ffts_internal.h index 3e788f8..f992811 100644 --- a/src/ffts_internal.h +++ b/src/ffts_internal.h @@ -184,7 +184,7 @@ struct _ffts_plan_t { static FFTS_INLINE void *ffts_aligned_malloc(size_t size) { -#if defined(_MSC_VER) +#if defined(_WIN32) return _aligned_malloc(size, 32); #else return valloc(size); -- cgit v1.1 From dfab21f8096660f441fb33bf5012e7f2c3652fa9 Mon Sep 17 00:00:00 2001 From: Jukka Ojanen Date: Tue, 31 Mar 2015 16:47:06 +0300 Subject: Generate cosine and sine table without using C math library. About 100 times faster on ARM and 15 times faster on x86. --- src/ffts_internal.h | 10 ---------- 1 file changed, 10 deletions(-) (limited to 'src/ffts_internal.h') diff --git a/src/ffts_internal.h b/src/ffts_internal.h index f992811..60de539 100644 --- a/src/ffts_internal.h +++ b/src/ffts_internal.h @@ -223,14 +223,4 @@ static __inline unsigned long ffts_ctzl(size_t N) #endif /* _WIN64 */ #endif /* _MSC_VER */ -static FFTS_ALWAYS_INLINE float W_re(float N, float k) -{ - return cos(-2.0 * M_PI * k / N); -} - -static FFTS_ALWAYS_INLINE float W_im(float N, float k) -{ - return sin(-2.0 * M_PI * k / N); -} - #endif /* FFTS_INTERNAL_H */ -- cgit v1.1 From 8f0c8c7f7243a1255cfcc4d63a169c21a61200fc Mon Sep 17 00:00:00 2001 From: Jukka Ojanen Date: Thu, 2 Jul 2015 17:04:44 +0300 Subject: Incorrect stride with GCC flags "-march=native -ffast-math" Note that N/leaf_N is always a multiply of 2 --- src/ffts_internal.h | 5 +++-- 1 file changed, 3 insertions(+), 2 deletions(-) (limited to 'src/ffts_internal.h') diff --git a/src/ffts_internal.h b/src/ffts_internal.h index 60de539..18b3bd5 100644 --- a/src/ffts_internal.h +++ b/src/ffts_internal.h @@ -79,7 +79,8 @@ #define M_PI 3.1415926535897932384626433832795028841971693993751058209 #endif -typedef void (*transform_func_t)(ffts_plan_t *p, const void *in, void *out); +struct _ffts_plan_t; +typedef void (*transform_func_t)(struct _ffts_plan_t *p, const void *in, void *out); /** * Contains all the Information need to perform FFT @@ -172,7 +173,7 @@ struct _ffts_plan_t { * to clean up the plan after use * (differs for real and multi dimension transforms */ - void (*destroy)(ffts_plan_t *); + void (*destroy)(struct _ffts_plan_t *); /** * Coefficiants for the real valued transforms -- cgit v1.1 From b481f5980e000a4ff5e123e8165e52b6dea6ea54 Mon Sep 17 00:00:00 2001 From: Jukka Ojanen Date: Mon, 6 Jul 2015 11:51:59 +0300 Subject: Fix ffts_aligned_free MinGW crash --- src/ffts_internal.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/ffts_internal.h') diff --git a/src/ffts_internal.h b/src/ffts_internal.h index 18b3bd5..2d1dbd3 100644 --- a/src/ffts_internal.h +++ b/src/ffts_internal.h @@ -194,7 +194,7 @@ static FFTS_INLINE void *ffts_aligned_malloc(size_t size) static FFTS_INLINE void ffts_aligned_free(void *p) { -#if defined(_MSC_VER) +#if defined(_WIN32) _aligned_free(p); #else free(p); -- cgit v1.1 From f571c435ceccc56e79c024f626a91c57f52d94ff Mon Sep 17 00:00:00 2001 From: Jukka Ojanen Date: Tue, 14 Jul 2015 23:51:35 +0300 Subject: FFTS is no longer depended on any other math library, and this should help to verify its numerical accuracy. --- src/ffts_internal.h | 1 - 1 file changed, 1 deletion(-) (limited to 'src/ffts_internal.h') diff --git a/src/ffts_internal.h b/src/ffts_internal.h index 2d1dbd3..59f46f8 100644 --- a/src/ffts_internal.h +++ b/src/ffts_internal.h @@ -40,7 +40,6 @@ #include "types.h" #include -#include #include #ifdef HAVE_STDINT_H -- cgit v1.1 From e8ec1ae614ecb4cbed7de0ecb298e2979bf39f13 Mon Sep 17 00:00:00 2001 From: Jukka Ojanen Date: Wed, 15 Jul 2015 00:39:51 +0300 Subject: Remove some dead code --- src/ffts_internal.h | 19 ------------------- 1 file changed, 19 deletions(-) (limited to 'src/ffts_internal.h') diff --git a/src/ffts_internal.h b/src/ffts_internal.h index 59f46f8..912a198 100644 --- a/src/ffts_internal.h +++ b/src/ffts_internal.h @@ -52,21 +52,6 @@ #include -#define FFTS_PREFIX ffts - -#ifndef FFTS_CAT_PREFIX2 -#define FFTS_CAT_PREFIX2(a,b) a ## b -#endif - -#ifndef FFTS_CAT_PREFIX -#define FFTS_CAT_PREFIX(a,b) FFTS_CAT_PREFIX2(a ## _, b) -#endif - -/* prevent symbol name clashes */ -#ifdef FFTS_PREFIX -#define FUNC_TO_REWRITE FFTS_CAT_PREFIX(FFTS_PREFIX, FUNC_TO_REWRITE) -#endif - #ifdef __ANDROID__ #include #define LOG(s) __android_log_print(ANDROID_LOG_ERROR, "FFTS", s) @@ -74,10 +59,6 @@ #define LOG(s) fprintf(stderr, s) #endif -#ifndef M_PI -#define M_PI 3.1415926535897932384626433832795028841971693993751058209 -#endif - struct _ffts_plan_t; typedef void (*transform_func_t)(struct _ffts_plan_t *p, const void *in, void *out); -- cgit v1.1 From cb35f8927bc8c6992d41efcc3b972f2d8ee318dc Mon Sep 17 00:00:00 2001 From: Jukka Ojanen Date: Thu, 16 Jul 2015 10:45:32 +0300 Subject: Define [pa] and [pb] as constant input variables, not writable outputs --- src/ffts_internal.h | 1 - 1 file changed, 1 deletion(-) (limited to 'src/ffts_internal.h') diff --git a/src/ffts_internal.h b/src/ffts_internal.h index 912a198..14d037d 100644 --- a/src/ffts_internal.h +++ b/src/ffts_internal.h @@ -35,7 +35,6 @@ #define FFTS_INTERNAL_H //#include "config.h" -//#include "codegen.h" #include "ffts_attributes.h" #include "types.h" -- cgit v1.1 From e1a92c370e5bd57a29f4ad66c72bae1078275f62 Mon Sep 17 00:00:00 2001 From: Jukka Ojanen Date: Thu, 30 Jul 2015 12:06:13 +0300 Subject: Detect presence of malloc.h, fixes anthonix/ffts#40 --- src/ffts_internal.h | 3 +++ 1 file changed, 3 insertions(+) (limited to 'src/ffts_internal.h') diff --git a/src/ffts_internal.h b/src/ffts_internal.h index 14d037d..30e814b 100644 --- a/src/ffts_internal.h +++ b/src/ffts_internal.h @@ -38,7 +38,10 @@ #include "ffts_attributes.h" #include "types.h" +#ifdef HAVE_MALLOC_H #include +#endif + #include #ifdef HAVE_STDINT_H -- cgit v1.1 From c85bf4b4a7a1199d9c48c24ec5a49ea0b16e1af1 Mon Sep 17 00:00:00 2001 From: Jukka Ojanen Date: Wed, 6 Apr 2016 17:34:23 +0300 Subject: Try to remove some of the hard coded offsets to _ffts_plan_t --- src/ffts_internal.h | 60 +++++++++++++++++++++++++++-------------------------- 1 file changed, 31 insertions(+), 29 deletions(-) (limited to 'src/ffts_internal.h') diff --git a/src/ffts_internal.h b/src/ffts_internal.h index 30e814b..7ae8789 100644 --- a/src/ffts_internal.h +++ b/src/ffts_internal.h @@ -1,33 +1,33 @@ /* - This file is part of FFTS -- The Fastest Fourier Transform in the South - - Copyright (c) 2012, Anthony M. Blake - Copyright (c) 2012, The University of Waikato - - 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 name of the organization nor the - names of its 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 ANTHONY M. BLAKE 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. +This file is part of FFTS -- The Fastest Fourier Transform in the South + +Copyright (c) 2012, Anthony M. Blake +Copyright (c) 2012, The University of Waikato + +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 name of the organization nor the +names of its 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 ANTHONY M. BLAKE 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. */ @@ -116,7 +116,9 @@ struct _ffts_plan_t { size_t N; void *lastlut; - size_t *temporary_fix_as_dynamic_code_assumes_fixed_offset; +#ifdef __arm__ + size_t *temporary_fix_as_dynamic_code_assumes_fixed_offset; +#endif /** * Pointer to the dynamically generated function -- cgit v1.1