# fft_prj

**Repository Path**: mudash/fft_prj

## Basic Information

- **Project Name**: fft_prj
- **Description**: No description available
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2026-05-17
- **Last Updated**: 2026-05-17

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# FFT Library

一个高性能的FFT（快速傅里叶变换）库，支持1D和2D变换，包含x86、ARM64和OpenCL优化实现。

## 🎯 功能特性

- **1D FFT变换**：支持前向和反向变换，Cooley-Tukey radix-2算法
- **2D FFT变换**：支持自定义stride配置，适用于图像处理场景
- **多平台优化**：
  - 标准C实现（通用）
  - x86_64 SIMD优化
  - ARM64 NEON优化
  - OpenCL GPU加速
- **高性能**：基于经典的Cooley-Tukey算法，时间复杂度O(n log n)

## 📊 性能测试结果

在 Intel Core i5-12490F 上测试：

### 1D FFT性能
| 数据点 | 时间(ms) | GFLOPs |
|--------|----------|--------|
| 64 | 0.0005 | 4.23 |
| 128 | 0.0011 | 4.19 |
| 256 | 0.0023 | 4.39 |
| 512 | 0.0055 | 4.16 |
| 1024 | 0.0113 | 4.55 |
| 2048 | 0.0270 | 4.17 |
| 4096 | 0.0784 | 3.13 |
| 8192 | 0.1860 | 2.86 |

### 2D FFT性能
| 尺寸 | 时间(ms) | GFLOPs |
|------|----------|--------|
| 32×32 | 0.0134 | 7.66 |
| 64×64 | 0.0686 | 7.16 |
| 128×128 | 0.3428 | 6.69 |
| 256×256 | 1.4551 | 7.21 |
| 512×512 | 7.0869 | 6.66 |

## 🔧 构建

### 标准构建
```bash
make
```

### 启用OpenCL支持
```bash
make USE_OPENCL=1
```

### 清理
```bash
make clean
```

### 运行示例
```bash
./build/fft_example    # 基本功能测试
./build/benchmark_compare  # 完整性能测试套件
```

## 📖 使用示例

### 1D FFT
```c
#include "fft.h"

// 分配内存
size_t n = 1024;
fft_complex* input = (fft_complex*)malloc(n * sizeof(fft_complex));
fft_complex* output = (fft_complex*)malloc(n * sizeof(fft_complex));

// 填充输入数据
for (size_t i = 0; i < n; i++) {
    input[i] = sin(2.0 * M_PI * i / n) + 0 * I;
}

// 创建计划并执行FFT
FFTPlan* plan = fft_create_plan(n, 1);  // 1=前向, -1=反向
fft_execute(plan, input, output);

// 销毁计划
fft_destroy_plan(plan);
free(input);
free(output);
```

### 2D FFT（支持stride）
```c
#include "fft.h"

// 图像尺寸
size_t rows = 256;
size_t cols = 256;
size_t stride = cols;  // 行间距，可大于cols实现内存对齐

// 分配内存
fft_complex* input = (fft_complex*)malloc(rows * stride * sizeof(fft_complex));
fft_complex* output = (fft_complex*)malloc(rows * stride * sizeof(fft_complex));

// 创建2D FFT计划
FFT2DPlan* plan = fft2d_create_plan(rows, cols, stride, 1);
fft2d_execute(plan, input, output);

// 清理
fft2d_destroy_plan(plan);
free(input);
free(output);
```

## 📁 项目结构

```
fft_prj/
├── include/           # 头文件
│   ├── fft.h          # FFT主接口
│   └── opencl.h       # OpenCL动态加载接口
├── src/               # 源代码
│   ├── fft.c          # 标准C实现
│   ├── fft_x86.c      # x86_64优化
│   ├── fft_arm64.c    # ARM64 NEON优化
│   ├── fft_cl.c       # OpenCL实现
│   ├── fft_cl_kernels.cl  # OpenCL内核
│   └── ocl_loader.c   # OpenCL动态加载器
├── examples/          # 示例代码
│   ├── main.c         # 基本功能测试
│   ├── benchmark.c     # 简单性能测试
│   ├── benchmark_compare.c  # 完整性能测试套件
│   └── clinfo.c       # OpenCL设备检测
├── docs/              # 文档
│   └── OPENCL_PERFORMANCE.md  # OpenCL性能对比指南
├── Makefile           # 构建系统
├── .gitignore         # Git忽略规则
└── README.md          # 项目说明
```

## 📚 API参考

### 1D FFT函数
| 函数 | 说明 |
|------|------|
| `fft_create_plan(n, direction)` | 创建FFT计划 |
| `fft_execute(plan, input, output)` | 执行FFT |
| `fft_destroy_plan(plan)` | 销毁计划 |

### 2D FFT函数
| 函数 | 说明 |
|------|------|
| `fft2d_create_plan(rows, cols, stride, direction)` | 创建2D FFT计划 |
| `fft2d_execute(plan, input, output)` | 执行2D FFT |
| `fft2d_destroy_plan(plan)` | 销毁计划 |

### OpenCL函数（需启用USE_OPENCL）
| 函数 | 说明 |
|------|------|
| `fft_cl_create_context(platform_name, device_type)` | 创建OpenCL上下文 |
| `fft_cl_destroy_context(ctx)` | 销毁OpenCL上下文 |
| `fft_cl_create_plan(ctx, n, direction)` | 创建OpenCL FFT计划 |
| `fft_cl_execute(ctx, plan, input, output)` | 执行OpenCL FFT |

## 🚀 性能优化建议

### 选择合适的实现
- **小数据量（<1000点）**：使用标准C实现
- **大数据量（>1000点）**：使用OpenCL GPU加速
- **移动端**：使用ARM64 NEON优化

### 内存优化
- 使用stride参数实现内存对齐
- 复用FFT计划避免重复创建开销
- 批量处理多个FFT任务

## 🤝 贡献

欢迎提交Issue和Pull Request！

### 开发环境要求
- GCC 9.0+
- OpenCL SDK（可选）
- Git

### 代码规范
- 使用标准C99
- 遵循K&R代码风格
- 添加必要的注释

## 📄 许可证

MIT License

## 📧 联系方式

如有问题或建议，欢迎提交Issue。