编译且移植FFTW3到Android手机上(2)

本文主要对如何将FFTW3编译且移植到Android App上进行介绍，同时对各FFTW提供的一些快速傅里叶变换的方法在手机进行性能测试，总结出使用FFTW3进行小规模傅里叶变换的最佳方式。

文章重点内容有：FFTW configure；编译so库；ARM NEON优化；float加速；多线程

第2部分为详细说明版，如想查看快速使用，请查看第1部分 : http://he-kai.com/?p=11 内容

详细代码：https://github.com/hekai/fftw_android

准备工作：

确保已完成 快速入门 部分的准备工作

编译FFTW：

打开fftw_android目录下的build.sh文件，默认的脚本中已启用neon优化和float支持

#!/bin/sh

# Compiles fftw3 for Android
# Make sure you have NDK_DIR defined in .bashrc or .bash_profile

#NDK Version r9c  http://dl.google.com/android/ndk/android-ndk-r9c-linux-x86_64.tar.bz2
NDK_DIR="/home/hekai/software/android-ndk-r9c"
INSTALL_DIR="`pwd`/jni/fftw3"
SRC_DIR="`pwd`/../fftw-3.3.3"

cd $SRC_DIR

export PATH="$NDK_DIR/toolchains/arm-linux-androideabi-4.8/prebuilt/linux-x86_64/bin/:$PATH"
export SYS_ROOT="$NDK_DIR/platforms/android-8/arch-arm/"
export CC="arm-linux-androideabi-gcc --sysroot=$SYS_ROOT -march=armv7-a -mfloat-abi=softfp"
export LD="arm-linux-androideabi-ld"
export AR="arm-linux-androideabi-ar"
export RANLIB="arm-linux-androideabi-ranlib"
export STRIP="arm-linux-androideabi-strip"
#export CFLAGS="-mfpu=neon -mfloat-abi=softfp"

mkdir -p $INSTALL_DIR
./configure --host=arm-eabi 
        --prefix=$INSTALL_DIR 
        LIBS="-lc -lgcc" 
        --enable-float 
        --enable-threads 
#        --with-combined-threads 
        --enable-neon

make
make install

exit 0

将NDK_DIR的路径修改为本机实际的NDK路径，如果版本不是r9c，请查看$NDK_DIR/toolchains/arm-linux-androideabi-4.8/prebuilt/linux-x86_64/bin/该路径是否存在，如不存在，请从NDK根目录开始找，寻找类似命名的文件夹，并将最终路径替换到build.sh中的export PATH=中

为验证编译效果，可将fftw_android/jni/fftw3中的文件夹全部删除，Android.mk留下！

打开终端，进入fftw_android所在目录，输入./build.sh，回车即可，终端上会显示编译过程，先会检查各编译器是否OK，再生成相应的config.h，最后再生成相关.a库文件，并自动复制到fftw_android/jni/fftw3目录下

通过默认的build.sh生成的只是支持float，neon和threads库文件(libfftwf3.a和libfftwf3_threads.a)，由于代码中还用到了double做对比测试，请将–enable-float，–enable-threads，–enable-neon对应的行用#号注释，将export CC中的-march=armv7-a -mfloat-abi=softfp直接删除，再运行./build.sh，从而生成支持double的库文件(libfftw3.a)

编写代码：

.a库生成好后，通过已写好的Android.mk在NDK或者Eclipse中即可生成完整so文件，下面描述如何使用这些so库进行编程

下面的过程就是常见的JNI编程过程，基本代码搭建示例很多，这里不做过多阐述，最简单的示例程序在NDK路径下的sample文件中，有hello-jni项目可供参考。大概过程是：Java代码中定义native的方法，并loadLibrary将后续要生成的so库载入内存；在jni中编写相应c/cpp文件实现native方法；Android.mk中定义好so库名，以及代码文件和依赖的库。

现主要对如何使用FFTW进行描述：

为方便测试，预先定义了几个常用方法如下：

#define SIZE 160 //SIZE x SIZE , default: 160 x 160

int init_in_fftw_complex(fftw_complex* in){
        int i,j,index;
        for (i = 0; i < SIZE; i++) {
                for (j = 0; j < SIZE; j++) {
                        index = j + i * SIZE;
                        in[index][0] = index + 1;
                        in[index][1] = 0;
                }
        }
        return 0;
}

int init_in_fftwf_float(float* in){
        int i,j,index;
        for (i = 0; i < SIZE; i++) {
                for (j = 0; j < SIZE; j++) {
                        index = j + i * SIZE;
                        in[index] = (float)(index + 1);
                }
        }
        return 0;
}

static double now_ms(void)
{
    struct timeval tv;
    gettimeofday(&tv, NULL);
    return tv.tv_sec*1000. + tv.tv_usec/1000.;
}

上述代码主要用于初始化二维矩阵，以及获取当前时间用来判断消耗。

基本

先写一个最基本的二维矩阵进行快速傅里叶变换，代码如下：

JNIEXPORT jstring JNICALL Java_com_hekai_fftw_1android_Utils_fftw_1dft_12d(
                JNIEnv * env, jobject thiz) {
        double t_start, t_end, t_span;
        t_start = now_ms();

        fftw_complex *in, *out;
        fftw_plan p;
        in = (fftw_complex*) fftw_malloc(sizeof(fftw_complex) * SIZE * SIZE);
        out = (fftw_complex*) fftw_malloc(sizeof(fftw_complex) * SIZE * SIZE);

        init_in_fftw_complex(in);

        p = fftw_plan_dft_2d(SIZE, SIZE, in, out, FFTW_FORWARD, FFTW_ESTIMATE);
        fftw_execute(p);

        fftw_destroy_plan(p);
        fftw_free(in);
        fftw_free(out);

        t_end = now_ms();
        t_span = t_end - t_start;
        LOGD("fftw_dft_2d() costs time %f ms", t_span);

        return (*env)->NewStringUTF(env, "fftw_dft_2d");
}

上述代码使用的是fftw_complex结构体，这会使用double类型做运算，需要依赖的库为libfftw3.a。通过fftw_plan_dft_2d 创建plan，并调用fftw_execute执行plan（可多次调用）。执行后，如果想查看结果，可以遍历out来查看，需要注意的是out是二维的，out[index][0]和out[index][1]中分别为结果的实数和虚数部分。运行结果可与Matlab或Octave的结果进行对比，以确定是否运算正确。

纯实数

针对纯实数矩阵，fftw提供有专门的函数加快运算过程，具体为携带有r2c标识的，如下所示：

JNIEXPORT jstring JNICALL Java_com_hekai_fftw_1android_Utils_fftw_1dft_1r2c_12d(
                JNIEnv * env, jobject thiz) {
        double t_start, t_end, t_span;
        t_start = now_ms();

        fftw_complex *in, *out;
        fftw_plan p;
        int NTmp = floor(SIZE/2 +1);
        in = (fftw_complex*) fftw_malloc(sizeof(fftw_complex) * SIZE * SIZE);
        out = (fftw_complex*) fftw_malloc(sizeof(fftw_complex) * SIZE * NTmp);

        init_in_fftw_complex(in);

        p = fftw_plan_dft_r2c_2d(SIZE, SIZE, in, out, FFTW_ESTIMATE);
        fftw_execute(p);

        fftw_destroy_plan(p);
        fftw_free(in);
        fftw_free(out);

        t_end = now_ms();
        t_span = t_end - t_start;
        LOGD("fftw_dft_r2c_2d() costs time %f ms", t_span);

        return (*env)->NewStringUTF(env, "fftw_dft_r2c_2d");
}

需要注意的是，纯实数矩阵做傅里叶变换后的结果具有对称性，因此out里没有N x N的结果，而是只有N x floor(N/2 + 1)的结果，遍历out时需注意。

Float

当不要求double的运算精度时，FFTW支持float运算，从而节省相应时间，代码如下：

JNIEXPORT jstring JNICALL Java_com_hekai_fftw_1android_Utils_fftwf_1dft_1r2c_12d(
                JNIEnv * env, jobject thiz) {
        double t_start, t_end, t_span;
        t_start = now_ms();

        float *in;
        fftwf_complex *out;
        fftwf_plan p;
        int NTmp = floor(SIZE / 2 + 1);
        in = (float*) fftw_malloc(sizeof(float) * SIZE * SIZE);
        out = (fftwf_complex*) fftwf_malloc(sizeof(fftwf_complex) * SIZE * NTmp);

        init_in_fftwf_float(in);

        p = fftwf_plan_dft_r2c_2d(SIZE, SIZE, in, out, FFTW_ESTIMATE);
        fftwf_execute(p);

        fftwf_destroy_plan(p);
        fftwf_free(in);
        fftwf_free(out);

        t_end = now_ms();
        t_span = t_end - t_start;
        LOGD("fftwf_dft_r2c_2d() costs time %f ms", t_span);

        return (*env)->NewStringUTF(env, "fftwf_dft_r2c_2d");
}

使用float运算时需注意，输入变为float*了，且相关的方法或数据结构都需要变为fftwf_***，即增加一个f，其他过程一样。

多线程

FFTW还支持多线程，但在小规模时反而会拖慢时间，具体代码如下：

JNIEXPORT jstring JNICALL Java_com_hekai_fftw_1android_Utils_fftwf_1dft_1r2c_12d_1thread(
                JNIEnv * env, jobject thiz) {
        double t_start, t_end, t_span;
        t_start = now_ms();

        int thread_ok = 0;
        int n_threads = 4;
        float *in;
        fftwf_complex *out;
        fftwf_plan p;
        int NTmp = floor(SIZE / 2 + 1);
        in = (float*) fftw_malloc(sizeof(float) * SIZE * SIZE);
        out = (fftwf_complex*) fftwf_malloc(sizeof(fftwf_complex) * SIZE * NTmp);

        init_in_fftwf_float(in);

        thread_ok = fftwf_init_threads();
        if(thread_ok)
                fftwf_plan_with_nthreads(n_threads);
        p = fftwf_plan_dft_r2c_2d(SIZE, SIZE, in, out, FFTW_ESTIMATE);
        fftwf_execute(p);

        fftwf_destroy_plan(p);
        if(thread_ok)
                fftwf_cleanup_threads();
        fftwf_free(in);
        fftwf_free(out);

        t_end = now_ms();
        t_span = t_end - t_start;
        LOGD("fftwf_dft_r2c_2d_thread() costs time %f ms. thread_ok = %d", t_span, thread_ok);

        return (*env)->NewStringUTF(env, "fftwf_dft_r2c_2d_thread");
}

使用多线程需要在对FFTW做configure时，开启–enable-threads，代码中通过thread_ok = fftwf_init_threads();获取当前是否支持多线程，1为支持。后续再通过fftwf_plan_with_nthreads(n_threads);指定线程数，以及fftwf_cleanup_threads();回收资源。

NEON优化

对于Android手机，如果CPU是ARM-v7架构的，可编译neon优化的so库加快运算速度，具体如下：

在build.sh中开启–enable-float和–enable-neon，并在CC中加入-march=armv7-a -mfloat-abi=softfp 。要开启NEON优化，必须开启float，即double运算不能进行NEON优化。最根本的原因主要是因为ARM-v7架构的问题，寄存器不够NEON优化来做double运算，而新的64位架构的ARM-v8a则解决了这个问题，不够需要重新porting相关NEON优化代码。ARM架构更多的信息请查阅ARM官网相关文档，这里不再做展开。

开启NEON优化后，c/cpp代码无需更改，直接可以运行查看运行效果。

在手机上，经过NEON优化后的so库运行效率有明显提高，当然不同的CPU可能有不同的改善效果…

总结：

• 在Android上使用so库，能支持NEON优化的，尽量使用以提高效率。
• FFTW的多线程在小规模时可以不用开启了，具体阈值多大需要具体去测试才行。
• float和r2c的方法请根据实际情况选用。

参考文献：

1. Compiling open source libraries with Android NDK: Part 2
2. 一个FFTW NDK的例子 https://github.com/jimjh/fftw-ndk-example
3. FFTW官方文档 http://fftw.org/fftw3_doc/