PFFFT C++ wrapper for APM
Pretty-Fast Fast Fourier Transform is a 3rd party FFT C library meant to
replace other FFT libraries in WebRTC (see https://crbug.com/webrtc/9577).
This CL adds a WebRTC wrapper meant to be used inside the Audio Processing
Module (APM). As a first step, it only supports aligned memory allocated
via PFFFT. Support for the C++ standard library containers will be done
afterwards since it requires careful investigation and benchmarking (because
PFFFT uses SIMD optimizations).
The wrapper pre-allocates a scratch buffer to avoid VLA.
Bug: webrtc:9577
Change-Id: Ied00c3d3b1df292024f608ccf0ed1917d6e92e56
Reviewed-on: https://webrtc-review.googlesource.com/c/122563
Reviewed-by: Mirko Bonadei <mbonadei@webrtc.org>
Reviewed-by: Max Morin <maxmorin@webrtc.org>
Commit-Queue: Alessio Bazzica <alessiob@webrtc.org>
Cr-Commit-Position: refs/heads/master@{#26808}diff --git a/modules/audio_processing/BUILD.gn b/modules/audio_processing/BUILD.gn
index 46869d0..9bef731 100644
--- a/modules/audio_processing/BUILD.gn
+++ b/modules/audio_processing/BUILD.gn
@@ -449,6 +449,7 @@
"test/conversational_speech:unittest",
"utility:block_mean_calculator_unittest",
"utility:legacy_delay_estimator_unittest",
+ "utility:pffft_wrapper_unittest",
"vad:vad_unittests",
"//testing/gtest",
"//third_party/abseil-cpp/absl/memory",
diff --git a/modules/audio_processing/utility/BUILD.gn b/modules/audio_processing/utility/BUILD.gn
index 6a4304d..f469cd4 100644
--- a/modules/audio_processing/utility/BUILD.gn
+++ b/modules/audio_processing/utility/BUILD.gn
@@ -83,6 +83,18 @@
}
}
+rtc_source_set("pffft_wrapper") {
+ sources = [
+ "pffft_wrapper.cc",
+ "pffft_wrapper.h",
+ ]
+ deps = [
+ "../../../api:array_view",
+ "../../../rtc_base:checks",
+ "//third_party/pffft",
+ ]
+}
+
if (rtc_include_tests) {
rtc_source_set("block_mean_calculator_unittest") {
testonly = true
@@ -111,4 +123,17 @@
"//testing/gtest",
]
}
+
+ rtc_source_set("pffft_wrapper_unittest") {
+ testonly = true
+ sources = [
+ "pffft_wrapper_unittest.cc",
+ ]
+ deps = [
+ ":pffft_wrapper",
+ "../../../test:test_support",
+ "//testing/gtest",
+ "//third_party/pffft",
+ ]
+ }
}
diff --git a/modules/audio_processing/utility/DEPS b/modules/audio_processing/utility/DEPS
new file mode 100644
index 0000000..c72d810
--- /dev/null
+++ b/modules/audio_processing/utility/DEPS
@@ -0,0 +1,3 @@
+include_rules = [
+ "+third_party/pffft",
+]
diff --git a/modules/audio_processing/utility/pffft_wrapper.cc b/modules/audio_processing/utility/pffft_wrapper.cc
new file mode 100644
index 0000000..eb0bff7
--- /dev/null
+++ b/modules/audio_processing/utility/pffft_wrapper.cc
@@ -0,0 +1,110 @@
+/*
+ * Copyright (c) 2019 The WebRTC project authors. All Rights Reserved.
+ *
+ * Use of this source code is governed by a BSD-style license
+ * that can be found in the LICENSE file in the root of the source
+ * tree. An additional intellectual property rights grant can be found
+ * in the file PATENTS. All contributing project authors may
+ * be found in the AUTHORS file in the root of the source tree.
+ */
+
+#include "modules/audio_processing/utility/pffft_wrapper.h"
+
+#include "rtc_base/checks.h"
+#include "third_party/pffft/src/pffft.h"
+
+namespace webrtc {
+namespace {
+
+size_t GetBufferSize(size_t fft_size, Pffft::FftType fft_type) {
+ return fft_size * (fft_type == Pffft::FftType::kReal ? 1 : 2);
+}
+
+float* AllocatePffftBuffer(size_t size) {
+ return static_cast<float*>(pffft_aligned_malloc(size * sizeof(float)));
+}
+
+} // namespace
+
+Pffft::FloatBuffer::FloatBuffer(size_t fft_size, FftType fft_type)
+ : size_(GetBufferSize(fft_size, fft_type)),
+ data_(AllocatePffftBuffer(size_)) {}
+
+Pffft::FloatBuffer::~FloatBuffer() {
+ pffft_aligned_free(data_);
+}
+
+rtc::ArrayView<const float> Pffft::FloatBuffer::GetConstView() const {
+ return {data_, size_};
+}
+
+rtc::ArrayView<float> Pffft::FloatBuffer::GetView() {
+ return {data_, size_};
+}
+
+Pffft::Pffft(size_t fft_size, FftType fft_type)
+ : fft_size_(fft_size),
+ fft_type_(fft_type),
+ pffft_status_(pffft_new_setup(
+ fft_size_,
+ fft_type == Pffft::FftType::kReal ? PFFFT_REAL : PFFFT_COMPLEX)),
+ scratch_buffer_(
+ AllocatePffftBuffer(GetBufferSize(fft_size_, fft_type_))) {
+ RTC_DCHECK(pffft_status_);
+ RTC_DCHECK(scratch_buffer_);
+}
+
+Pffft::~Pffft() {
+ pffft_destroy_setup(pffft_status_);
+ pffft_aligned_free(scratch_buffer_);
+}
+
+bool Pffft::IsValidFftSize(size_t fft_size, FftType fft_type) {
+ if (fft_size == 0) {
+ return false;
+ }
+ // PFFFT only supports transforms for inputs of length N of the form
+ // N = (2^a)*(3^b)*(5^c) where b >=0 and c >= 0 and a >= 5 for the real FFT
+ // and a >= 4 for the complex FFT.
+ constexpr int kFactors[] = {2, 3, 5};
+ int factorization[] = {0, 0, 0};
+ int n = static_cast<int>(fft_size);
+ for (int i = 0; i < 3; ++i) {
+ while (n % kFactors[i] == 0) {
+ n = n / kFactors[i];
+ factorization[i]++;
+ }
+ }
+ int a_min = (fft_type == Pffft::FftType::kReal) ? 5 : 4;
+ return factorization[0] >= a_min && n == 1;
+}
+
+bool Pffft::IsSimdEnabled() {
+ return pffft_simd_size() > 1;
+}
+
+std::unique_ptr<Pffft::FloatBuffer> Pffft::CreateBuffer() const {
+ // Cannot use make_unique from absl because Pffft is the only friend of
+ // Pffft::FloatBuffer.
+ std::unique_ptr<Pffft::FloatBuffer> buffer(
+ new Pffft::FloatBuffer(fft_size_, fft_type_));
+ return buffer;
+}
+
+void Pffft::ForwardTransform(const FloatBuffer& in, FloatBuffer* out) {
+ RTC_DCHECK_EQ(in.size(), GetBufferSize(fft_size_, fft_type_));
+ RTC_DCHECK_EQ(in.size(), out->size());
+ RTC_DCHECK(scratch_buffer_);
+ pffft_transform(pffft_status_, in.const_data(), out->data(), scratch_buffer_,
+ PFFFT_FORWARD);
+}
+
+void Pffft::BackwardTransform(const FloatBuffer& in, FloatBuffer* out) {
+ RTC_DCHECK_EQ(in.size(), GetBufferSize(fft_size_, fft_type_));
+ RTC_DCHECK_EQ(in.size(), out->size());
+ RTC_DCHECK(scratch_buffer_);
+ pffft_transform(pffft_status_, in.const_data(), out->data(), scratch_buffer_,
+ PFFFT_BACKWARD);
+}
+
+} // namespace webrtc
diff --git a/modules/audio_processing/utility/pffft_wrapper.h b/modules/audio_processing/utility/pffft_wrapper.h
new file mode 100644
index 0000000..c190430
--- /dev/null
+++ b/modules/audio_processing/utility/pffft_wrapper.h
@@ -0,0 +1,85 @@
+/*
+ * Copyright (c) 2019 The WebRTC project authors. All Rights Reserved.
+ *
+ * Use of this source code is governed by a BSD-style license
+ * that can be found in the LICENSE file in the root of the source
+ * tree. An additional intellectual property rights grant can be found
+ * in the file PATENTS. All contributing project authors may
+ * be found in the AUTHORS file in the root of the source tree.
+ */
+
+#ifndef MODULES_AUDIO_PROCESSING_UTILITY_PFFFT_WRAPPER_H_
+#define MODULES_AUDIO_PROCESSING_UTILITY_PFFFT_WRAPPER_H_
+
+#include <memory>
+
+#include "api/array_view.h"
+
+// Forward declaration.
+struct PFFFT_Setup;
+
+namespace webrtc {
+
+// Pretty-Fast Fast Fourier Transform (PFFFT) wrapper class.
+// Not thread safe.
+class Pffft {
+ public:
+ enum class FftType { kReal, kComplex };
+
+ // 1D floating point buffer used as input/output data type for the FFT ops.
+ // It must be constructed using Pffft::CreateBuffer().
+ class FloatBuffer {
+ public:
+ FloatBuffer(const FloatBuffer&) = delete;
+ FloatBuffer& operator=(const FloatBuffer&) = delete;
+ ~FloatBuffer();
+
+ rtc::ArrayView<const float> GetConstView() const;
+ rtc::ArrayView<float> GetView();
+
+ private:
+ friend class Pffft;
+ FloatBuffer(size_t fft_size, FftType fft_type);
+ const float* const_data() const { return data_; }
+ float* data() { return data_; }
+ size_t size() const { return size_; }
+
+ const size_t size_;
+ float* const data_;
+ };
+
+ // TODO(https://crbug.com/webrtc/9577): Consider adding a factory and making
+ // the ctor private.
+ // static std::unique_ptr<Pffft> Create(size_t fft_size,
+ // FftType fft_type); Ctor. |fft_size| must be a supported size (see
+ // Pffft::IsValidFftSize()). If not supported, the code will crash.
+ Pffft(size_t fft_size, FftType fft_type);
+ Pffft(const Pffft&) = delete;
+ Pffft& operator=(const Pffft&) = delete;
+ ~Pffft();
+
+ // Returns true if the FFT size is supported.
+ static bool IsValidFftSize(size_t fft_size, FftType fft_type);
+
+ // Returns true if SIMD code optimizations are being used.
+ static bool IsSimdEnabled();
+
+ // Creates a buffer of the right size.
+ std::unique_ptr<FloatBuffer> CreateBuffer() const;
+
+ // TODO(https://crbug.com/webrtc/9577): Overload with rtc::ArrayView args.
+ // Computes the forward fast Fourier transform.
+ void ForwardTransform(const FloatBuffer& in, FloatBuffer* out);
+ // Computes the backward fast Fourier transform.
+ void BackwardTransform(const FloatBuffer& in, FloatBuffer* out);
+
+ private:
+ const size_t fft_size_;
+ const FftType fft_type_;
+ PFFFT_Setup* pffft_status_;
+ float* const scratch_buffer_;
+};
+
+} // namespace webrtc
+
+#endif // MODULES_AUDIO_PROCESSING_UTILITY_PFFFT_WRAPPER_H_
diff --git a/modules/audio_processing/utility/pffft_wrapper_unittest.cc b/modules/audio_processing/utility/pffft_wrapper_unittest.cc
new file mode 100644
index 0000000..8ec2208
--- /dev/null
+++ b/modules/audio_processing/utility/pffft_wrapper_unittest.cc
@@ -0,0 +1,154 @@
+/*
+ * Copyright (c) 2019 The WebRTC project authors. All Rights Reserved.
+ *
+ * Use of this source code is governed by a BSD-style license
+ * that can be found in the LICENSE file in the root of the source
+ * tree. An additional intellectual property rights grant can be found
+ * in the file PATENTS. All contributing project authors may
+ * be found in the AUTHORS file in the root of the source tree.
+ */
+
+#include "modules/audio_processing/utility/pffft_wrapper.h"
+
+#include <algorithm>
+#include <cstdlib>
+#include <memory>
+
+#include "test/gtest.h"
+#include "third_party/pffft/src/pffft.h"
+
+namespace webrtc {
+namespace test {
+namespace {
+
+constexpr size_t kMaxValidSizeCheck = 1024;
+
+static constexpr int kFftSizes[] = {
+ 16, 32, 64, 96, 128, 160, 192, 256, 288, 384, 5 * 96, 512,
+ 576, 5 * 128, 800, 864, 1024, 2048, 2592, 4000, 4096, 12000, 36864};
+
+void CreatePffftWrapper(size_t fft_size, Pffft::FftType fft_type) {
+ Pffft pffft_wrapper(fft_size, fft_type);
+}
+
+float* AllocateScratchBuffer(size_t fft_size, bool complex_fft) {
+ return static_cast<float*>(
+ pffft_aligned_malloc(fft_size * (complex_fft ? 2 : 1) * sizeof(float)));
+}
+
+double frand() {
+ return std::rand() / static_cast<double>(RAND_MAX);
+}
+
+void ExpectArrayViewsEquality(rtc::ArrayView<const float> a,
+ rtc::ArrayView<const float> b) {
+ ASSERT_EQ(a.size(), b.size());
+ for (size_t i = 0; i < a.size(); ++i) {
+ SCOPED_TRACE(i);
+ EXPECT_EQ(a[i], b[i]);
+ }
+}
+
+// Compares the output of the PFFFT C++ wrapper to that of the C PFFFT.
+// Bit-exactness is expected.
+void PffftValidateWrapper(size_t fft_size, bool complex_fft) {
+ // Always use the same seed to avoid flakiness.
+ std::srand(0);
+
+ // Init PFFFT.
+ PFFFT_Setup* pffft_status =
+ pffft_new_setup(fft_size, complex_fft ? PFFFT_COMPLEX : PFFFT_REAL);
+ ASSERT_TRUE(pffft_status) << "FFT size (" << fft_size << ") not supported.";
+ size_t num_floats = fft_size * (complex_fft ? 2 : 1);
+ int num_bytes = static_cast<int>(num_floats) * sizeof(float);
+ float* in = static_cast<float*>(pffft_aligned_malloc(num_bytes));
+ float* out = static_cast<float*>(pffft_aligned_malloc(num_bytes));
+ float* scratch = AllocateScratchBuffer(fft_size, complex_fft);
+
+ // Init PFFFT C++ wrapper.
+ Pffft::FftType fft_type =
+ complex_fft ? Pffft::FftType::kComplex : Pffft::FftType::kReal;
+ ASSERT_TRUE(Pffft::IsValidFftSize(fft_size, fft_type));
+ Pffft pffft_wrapper(fft_size, fft_type);
+ auto in_wrapper = pffft_wrapper.CreateBuffer();
+ auto out_wrapper = pffft_wrapper.CreateBuffer();
+
+ // Input and output buffers views.
+ rtc::ArrayView<float> in_view(in, num_floats);
+ rtc::ArrayView<float> out_view(out, num_floats);
+ auto in_wrapper_view = in_wrapper->GetView();
+ EXPECT_EQ(in_wrapper_view.size(), num_floats);
+ auto out_wrapper_view = out_wrapper->GetConstView();
+ EXPECT_EQ(out_wrapper_view.size(), num_floats);
+
+ // Random input data.
+ for (size_t i = 0; i < num_floats; ++i) {
+ in_wrapper_view[i] = in[i] = static_cast<float>(frand() * 2.0 - 1.0);
+ }
+
+ // Forward transform.
+ pffft_transform(pffft_status, in, out, scratch, PFFFT_FORWARD);
+ pffft_wrapper.ForwardTransform(*in_wrapper, out_wrapper.get());
+ ExpectArrayViewsEquality(out_view, out_wrapper_view);
+
+ // Copy the FFT results into the input buffers to compute the backward FFT.
+ std::copy(out_view.begin(), out_view.end(), in_view.begin());
+ std::copy(out_wrapper_view.begin(), out_wrapper_view.end(),
+ in_wrapper_view.begin());
+
+ // Backward transform.
+ pffft_transform(pffft_status, in, out, scratch, PFFFT_BACKWARD);
+ pffft_wrapper.BackwardTransform(*in_wrapper, out_wrapper.get());
+ ExpectArrayViewsEquality(out_view, out_wrapper_view);
+
+ pffft_destroy_setup(pffft_status);
+ pffft_aligned_free(in);
+ pffft_aligned_free(out);
+ pffft_aligned_free(scratch);
+}
+
+} // namespace
+
+TEST(PffftTest, CreateWrapperWithValidSize) {
+ for (size_t fft_size = 0; fft_size < kMaxValidSizeCheck; ++fft_size) {
+ SCOPED_TRACE(fft_size);
+ if (Pffft::IsValidFftSize(fft_size, Pffft::FftType::kReal)) {
+ CreatePffftWrapper(fft_size, Pffft::FftType::kReal);
+ }
+ if (Pffft::IsValidFftSize(fft_size, Pffft::FftType::kComplex)) {
+ CreatePffftWrapper(fft_size, Pffft::FftType::kComplex);
+ }
+ }
+}
+
+#if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST && !defined(WEBRTC_ANDROID)
+TEST(PffftTest, DoNotCreateWrapperWithInvalidSize) {
+ for (size_t fft_size = 0; fft_size < kMaxValidSizeCheck; ++fft_size) {
+ SCOPED_TRACE(fft_size);
+ if (!Pffft::IsValidFftSize(fft_size, Pffft::FftType::kReal)) {
+ EXPECT_DEATH(CreatePffftWrapper(fft_size, Pffft::FftType::kReal), "");
+ }
+ if (!Pffft::IsValidFftSize(fft_size, Pffft::FftType::kComplex)) {
+ EXPECT_DEATH(CreatePffftWrapper(fft_size, Pffft::FftType::kComplex), "");
+ }
+ }
+}
+#endif
+
+// TODO(https://crbug.com/webrtc/9577): Enable once SIMD is always enabled.
+TEST(PffftTest, DISABLED_CheckSimd) {
+ EXPECT_TRUE(Pffft::IsSimdEnabled());
+}
+
+TEST(PffftTest, FftBitExactness) {
+ for (int fft_size : kFftSizes) {
+ SCOPED_TRACE(fft_size);
+ if (fft_size != 16) {
+ PffftValidateWrapper(fft_size, /*complex_fft=*/false);
+ }
+ PffftValidateWrapper(fft_size, /*complex_fft=*/true);
+ }
+}
+
+} // namespace test
+} // namespace webrtc
