Overlapp_add (#2116)

`port c++ Overlapp_Add op to open source in tflm_signal`

-port Overlapp_Add op and corresponding to new open source location for C++

BUG=[b/289291202](https://b.corp.google.com/issues/289291202)
diff --git a/python/tflite_micro/python_ops_resolver.cc b/python/tflite_micro/python_ops_resolver.cc
index 8d508e1..ed4320e 100644
--- a/python/tflite_micro/python_ops_resolver.cc
+++ b/python/tflite_micro/python_ops_resolver.cc
@@ -80,6 +80,7 @@
   AddMul();
   AddNeg();
   AddNotEqual();
+  AddOverlapAdd();
   AddPack();
   AddPad();
   AddPadV2();
diff --git a/signal/micro/kernels/BUILD b/signal/micro/kernels/BUILD
index 040332c..aea77f6 100644
--- a/signal/micro/kernels/BUILD
+++ b/signal/micro/kernels/BUILD
@@ -9,6 +9,7 @@
     name = "register_signal_ops",
     srcs = [
         "framer.cc",
+        "overlap_add.cc",
         "rfft.cc",
         "window.cc",
     ],
@@ -21,6 +22,7 @@
     ],
     deps = [
         "//signal/src:circular_buffer",
+        "//signal/src:overlap_add",
         "//signal/src:rfft",
         "//signal/src:window",
         "//tensorflow/lite:type_to_tflitetype",
@@ -113,3 +115,29 @@
         "//tensorflow/lite/micro/testing:micro_test",
     ],
 )
+
+cc_library(
+    name = "overlap_add_flexbuffers_generated_data",
+    srcs = [
+        "overlap_add_flexbuffers_generated_data.cc",
+    ],
+    hdrs = [
+        "overlap_add_flexbuffers_generated_data.h",
+    ],
+)
+
+cc_test(
+    name = "overlap_add_test",
+    srcs = [
+        "overlap_add_test.cc",
+    ],
+    deps = [
+        ":overlap_add_flexbuffers_generated_data",
+        ":register_signal_ops",
+        "//tensorflow/lite/c:common",
+        "//tensorflow/lite/micro:op_resolvers",
+        "//tensorflow/lite/micro:test_helpers",
+        "//tensorflow/lite/micro/kernels:kernel_runner",
+        "//tensorflow/lite/micro/testing:micro_test",
+    ],
+)
diff --git a/signal/micro/kernels/overlap_add.cc b/signal/micro/kernels/overlap_add.cc
new file mode 100644
index 0000000..8de7463
--- /dev/null
+++ b/signal/micro/kernels/overlap_add.cc
@@ -0,0 +1,241 @@
+/* Copyright 2021 The TensorFlow Authors. All Rights Reserved.
+
+Licensed under the Apache License, Version 2.0 (the "License");
+you may not use this file except in compliance with the License.
+You may obtain a copy of the License at
+
+    http://www.apache.org/licenses/LICENSE-2.0
+
+Unless required by applicable law or agreed to in writing, software
+distributed under the License is distributed on an "AS IS" BASIS,
+WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+See the License for the specific language governing permissions and
+limitations under the License.
+==============================================================================*/
+
+#include "signal/src/overlap_add.h"
+
+#include <stdint.h>
+
+#include "tensorflow/lite/kernels/internal/tensor_ctypes.h"
+#include "tensorflow/lite/kernels/kernel_util.h"
+#include "tensorflow/lite/micro/flatbuffer_utils.h"
+#include "tensorflow/lite/micro/kernels/kernel_util.h"
+#include "tensorflow/lite/portable_type_to_tflitetype.h"
+
+namespace tflite {
+namespace {
+
+constexpr int kInputTensor = 0;
+constexpr int kOutputTensor = 0;
+
+// Indices into the init flexbuffer's vector.
+// The parameter's name is in the comment that follows.
+// Elements in the vectors are ordered alphabetically by parameter name.
+// 'T' is added implicitly by the TensorFlow framework when the type is resolved
+// during graph construction.
+// constexpr int kTypeIndex = 0;  // 'T' (unused)
+constexpr int kFrameStepIndex = 1;  // 'frame_step'
+
+template <typename T>
+struct TFLMSignalOverlapAddParams {
+  int32_t frame_size;
+  int32_t frame_step;
+  int32_t outer_dims;
+  int32_t n_frames;
+  TfLiteType type;
+  T** state_buffers;
+};
+
+template <typename T>
+void ResetState(TFLMSignalOverlapAddParams<T>* params) {
+  for (int i = 0; i < params->outer_dims; i++) {
+    memset(params->state_buffers[i], 0, sizeof(T) * params->frame_size);
+  }
+}
+
+template <typename T>
+void* Init(TfLiteContext* context, const char* buffer, size_t length) {
+  const uint8_t* buffer_t = reinterpret_cast<const uint8_t*>(buffer);
+
+  auto* params = static_cast<TFLMSignalOverlapAddParams<T>*>(
+      context->AllocatePersistentBuffer(context,
+                                        sizeof(TFLMSignalOverlapAddParams<T>)));
+
+  if (params == nullptr) {
+    return nullptr;
+  }
+
+  tflite::FlexbufferWrapper fbw(buffer_t, length);
+  params->type = typeToTfLiteType<T>();
+  params->frame_step = fbw.ElementAsInt32(kFrameStepIndex);
+  return params;
+}
+
+template <typename T, TfLiteType TfLiteTypeEnum>
+TfLiteStatus Prepare(TfLiteContext* context, TfLiteNode* node) {
+  TF_LITE_ENSURE_EQ(context, NumInputs(node), 1);
+  TF_LITE_ENSURE_EQ(context, NumOutputs(node), 1);
+
+  MicroContext* micro_context = GetMicroContext(context);
+
+  TfLiteTensor* input =
+      micro_context->AllocateTempInputTensor(node, kInputTensor);
+  TF_LITE_ENSURE(context, input != nullptr);
+  TfLiteTensor* output =
+      micro_context->AllocateTempOutputTensor(node, kOutputTensor);
+  TF_LITE_ENSURE(context, output != nullptr);
+
+  TF_LITE_ENSURE_EQ(context, NumDimensions(input), NumDimensions(output) + 1);
+
+  TF_LITE_ENSURE_TYPES_EQ(context, input->type, TfLiteTypeEnum);
+  TF_LITE_ENSURE_TYPES_EQ(context, output->type, TfLiteTypeEnum);
+
+  auto* params =
+      reinterpret_cast<TFLMSignalOverlapAddParams<T>*>(node->user_data);
+  RuntimeShape input_shape = GetTensorShape(input);
+  RuntimeShape output_shape = GetTensorShape(output);
+  TF_LITE_ENSURE(context, input_shape.DimensionsCount() >= 2);
+  TF_LITE_ENSURE_EQ(context, input_shape.DimensionsCount(),
+                    output_shape.DimensionsCount() + 1);
+
+  params->frame_size = input_shape.Dims(input_shape.DimensionsCount() - 1);
+  params->n_frames = input_shape.Dims(input_shape.DimensionsCount() - 2);
+  params->outer_dims =
+      input_shape.FlatSize() / (params->frame_size * params->n_frames);
+  params->state_buffers = static_cast<T**>(context->AllocatePersistentBuffer(
+      context, params->outer_dims * sizeof(T*)));
+  TF_LITE_ENSURE(context, params != nullptr);
+
+  for (int i = 0; i < params->outer_dims; i++) {
+    params->state_buffers[i] =
+        static_cast<T*>(context->AllocatePersistentBuffer(
+            context, params->frame_size * sizeof(T)));
+  }
+  ResetState(params);
+
+  micro_context->DeallocateTempTfLiteTensor(input);
+  micro_context->DeallocateTempTfLiteTensor(output);
+  return kTfLiteOk;
+}
+
+template <typename T>
+TfLiteStatus Eval(TfLiteContext* context, TfLiteNode* node) {
+  auto* params =
+      reinterpret_cast<TFLMSignalOverlapAddParams<T>*>(node->user_data);
+  const TfLiteEvalTensor* input =
+      tflite::micro::GetEvalInput(context, node, kInputTensor);
+  TfLiteEvalTensor* output =
+      tflite::micro::GetEvalOutput(context, node, kOutputTensor);
+
+  const T* input_data = tflite::micro::GetTensorData<T>(input);
+  T* output_data = tflite::micro::GetTensorData<T>(output);
+  for (int i = 0; i < params->outer_dims; i++) {
+    T* buffer = params->state_buffers[i];
+    for (int frame = 0; frame < params->n_frames; frame++) {
+      int input_index = (i * params->n_frames + frame) * params->frame_size;
+      int output_index = (i * params->n_frames + frame) * params->frame_step;
+      tflm_signal::OverlapAdd(&input_data[input_index], buffer,
+                              params->frame_size, &output_data[output_index],
+                              params->frame_step);
+    }
+  }
+  return kTfLiteOk;
+}
+
+template <typename T>
+void Reset(TfLiteContext* context, void* buffer) {
+  ResetState(static_cast<TFLMSignalOverlapAddParams<T>*>(buffer));
+}
+
+void* InitAll(TfLiteContext* context, const char* buffer, size_t length) {
+  const uint8_t* buffer_t = reinterpret_cast<const uint8_t*>(buffer);
+  const flexbuffers::Map& m = flexbuffers::GetRoot(buffer_t, length).AsMap();
+  auto tensor_type = static_cast<tflite::TensorType>(m["T"].AsInt32());
+
+  switch (tensor_type) {
+    case TensorType_INT16: {
+      return Init<int16_t>(context, buffer, length);
+    }
+    case TensorType_FLOAT32: {
+      return Init<float>(context, buffer, length);
+    }
+    default:
+      return nullptr;
+  }
+}
+
+TfLiteStatus PrepareAll(TfLiteContext* context, TfLiteNode* node) {
+  auto* params =
+      reinterpret_cast<TFLMSignalOverlapAddParams<void>*>(node->user_data);
+
+  switch (params->type) {
+    case kTfLiteInt16: {
+      return Prepare<int16_t, kTfLiteInt16>(context, node);
+    }
+    case kTfLiteFloat32: {
+      return Prepare<float, kTfLiteFloat32>(context, node);
+    }
+    default:
+      return kTfLiteError;
+  }
+}
+
+TfLiteStatus EvalAll(TfLiteContext* context, TfLiteNode* node) {
+  auto* params =
+      reinterpret_cast<TFLMSignalOverlapAddParams<void>*>(node->user_data);
+
+  switch (params->type) {
+    case kTfLiteInt16: {
+      return Eval<int16_t>(context, node);
+    }
+    case kTfLiteFloat32: {
+      return Eval<float>(context, node);
+    }
+    default:
+      return kTfLiteError;
+  }
+}
+
+void ResetAll(TfLiteContext* context, void* buffer) {
+  auto* params = reinterpret_cast<TFLMSignalOverlapAddParams<void>*>(buffer);
+
+  switch (params->type) {
+    case kTfLiteInt16: {
+      Reset<int16_t>(context, buffer);
+      break;
+    }
+    case kTfLiteFloat32: {
+      Reset<float>(context, buffer);
+      break;
+    }
+    default:
+      break;
+  }
+}
+
+}  // namespace
+
+namespace tflm_signal {
+TFLMRegistration* Register_OVERLAP_ADD() {
+  static TFLMRegistration r = tflite::micro::RegisterOp(
+      InitAll, PrepareAll, EvalAll, nullptr, ResetAll);
+  return &r;
+}
+
+TFLMRegistration* Register_OVERLAP_ADD_FLOAT() {
+  static TFLMRegistration r =
+      tflite::micro::RegisterOp(Init<float>, Prepare<float, kTfLiteFloat32>,
+                                Eval<float>, nullptr, Reset<float>);
+  return &r;
+}
+
+TFLMRegistration* Register_OVERLAP_ADD_INT16() {
+  static TFLMRegistration r =
+      tflite::micro::RegisterOp(Init<int16_t>, Prepare<int16_t, kTfLiteInt16>,
+                                Eval<int16_t>, nullptr, Reset<int16_t>);
+  return &r;
+}
+}  // namespace tflm_signal
+
+}  // namespace tflite
diff --git a/signal/micro/kernels/overlap_add_flexbuffers_generated_data.cc b/signal/micro/kernels/overlap_add_flexbuffers_generated_data.cc
new file mode 100644
index 0000000..7f810db
--- /dev/null
+++ b/signal/micro/kernels/overlap_add_flexbuffers_generated_data.cc
@@ -0,0 +1,32 @@
+/* Copyright 2021 The TensorFlow Authors. All Rights Reserved.
+Licensed under the Apache License, Version 2.0 (the "License");
+you may not use this file except in compliance with the License.
+You may obtain a copy of the License at
+
+    http://www.apache.org/licenses/LICENSE-2.0
+
+Unless required by applicable law or agreed to in writing, software
+distributed under the License is distributed on an "AS IS" BASIS,
+WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+See the License for the specific language governing permissions and
+limitations under the License.
+==============================================================================*/
+
+// This file is generated. See:
+// tensorflow/lite/micro/kernels/test_data_generation/README.md
+
+#include "signal/micro/kernels/overlap_add_flexbuffers_generated_data.h"
+
+const int g_gen_data_size_overlap_add_float = 26;
+const unsigned char g_gen_data_overlap_add_float[] = {
+    0x66, 0x72, 0x61, 0x6d, 0x65, 0x5f, 0x73, 0x74, 0x65,
+    0x70, 0x00, 0x54, 0x00, 0x02, 0x03, 0x0f, 0x02, 0x01,
+    0x02, 0x00, 0x01, 0x04, 0x04, 0x04, 0x24, 0x01,
+};
+
+const int g_gen_data_size_overlap_add_int16 = 26;
+const unsigned char g_gen_data_overlap_add_int16[] = {
+    0x66, 0x72, 0x61, 0x6d, 0x65, 0x5f, 0x73, 0x74, 0x65,
+    0x70, 0x00, 0x54, 0x00, 0x02, 0x03, 0x0f, 0x02, 0x01,
+    0x02, 0x07, 0x01, 0x04, 0x04, 0x04, 0x24, 0x01,
+};
diff --git a/signal/micro/kernels/overlap_add_flexbuffers_generated_data.h b/signal/micro/kernels/overlap_add_flexbuffers_generated_data.h
new file mode 100644
index 0000000..adb4fba
--- /dev/null
+++ b/signal/micro/kernels/overlap_add_flexbuffers_generated_data.h
@@ -0,0 +1,25 @@
+/* Copyright 2021 The TensorFlow Authors. All Rights Reserved.
+
+Licensed under the Apache License, Version 2.0 (the "License");
+you may not use this file except in compliance with the License.
+You may obtain a copy of the License at
+
+    http://www.apache.org/licenses/LICENSE-2.0
+
+Unless required by applicable law or agreed to in writing, software
+distributed under the License is distributed on an "AS IS" BASIS,
+WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+See the License for the specific language governing permissions and
+limitations under the License.
+==============================================================================*/
+
+#ifndef SIGNAL_MICRO_KERNELS_TEST_DATA_GENERATION_GENERATE_OVERLAP_ADD_FLEXBUFFERS_DATA_H_
+#define SIGNAL_MICRO_KERNELS_TEST_DATA_GENERATION_GENERATE_OVERLAP_ADD_FLEXBUFFERS_DATA_H_
+
+extern const int g_gen_data_size_overlap_add_float;
+extern const unsigned char g_gen_data_overlap_add_float[];
+
+extern const int g_gen_data_size_overlap_add_int16;
+extern const unsigned char g_gen_data_overlap_add_int16[];
+
+#endif  // SIGNAL_MICRO_KERNELS_TEST_DATA_GENERATION_GENERATE_OVERLAP_ADD_FLEXBUFFERS_DATA_H_
diff --git a/signal/micro/kernels/overlap_add_test.cc b/signal/micro/kernels/overlap_add_test.cc
new file mode 100644
index 0000000..f7b9f52
--- /dev/null
+++ b/signal/micro/kernels/overlap_add_test.cc
@@ -0,0 +1,252 @@
+/* Copyright 2021 The TensorFlow Authors. All Rights Reserved.
+
+Licensed under the Apache License, Version 2.0 (the "License");
+you may not use this file except in compliance with the License.
+You may obtain a copy of the License at
+
+    http://www.apache.org/licenses/LICENSE-2.0
+
+Unless required by applicable law or agreed to in writing, software
+distributed under the License is distributed on an "AS IS" BASIS,
+WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+See the License for the specific language governing permissions and
+limitations under the License.
+==============================================================================*/
+
+#include <cstdint>
+
+#include "signal/micro/kernels/overlap_add_flexbuffers_generated_data.h"
+#include "tensorflow/lite/micro/kernels/kernel_runner.h"
+#include "tensorflow/lite/micro/test_helpers.h"
+#include "tensorflow/lite/micro/testing/micro_test.h"
+
+namespace tflite {
+
+constexpr int kFrameStepIndex = 1;
+constexpr int kInputsSize = 1;
+constexpr int kOutputsSize = 1;
+constexpr int kTensorsSize = kInputsSize + kOutputsSize;
+
+template <typename T>
+class OverlapAddKernelRunner {
+ public:
+  OverlapAddKernelRunner(int* input_dims_data, T* input_data,
+                         int* output_dims_data, T* output_data)
+      : inputs_array_{testing::IntArrayFromInts(inputs_array_data_)},
+        outputs_array_{testing::IntArrayFromInts(outputs_array_data_)} {
+    tensors_[0] = testing::CreateTensor(
+        input_data, testing::IntArrayFromInts(input_dims_data));
+
+    tensors_[1] = tflite::testing::CreateTensor(
+        output_data, testing::IntArrayFromInts(output_dims_data));
+
+    registration_ = tflm_signal::Register_OVERLAP_ADD();
+
+    // go/tflm-static-cleanups for reasoning new is being used like this
+    kernel_runner_ = new (kernel_runner_buffer) tflite::micro::KernelRunner(
+        *registration_, tensors_, kTensorsSize, inputs_array_, outputs_array_,
+        /*builtin_data=*/nullptr);
+  }
+
+  micro::KernelRunner& GetKernelRunner() { return *kernel_runner_; }
+
+ private:
+  uint8_t kernel_runner_buffer[sizeof(micro::KernelRunner)];
+  int inputs_array_data_[kInputsSize + 1] = {1, 0};
+  int outputs_array_data_[kOutputsSize + 1] = {1, 1};
+  TfLiteTensor tensors_[kTensorsSize] = {};
+  TfLiteIntArray* inputs_array_ = nullptr;
+  TfLiteIntArray* outputs_array_ = nullptr;
+  TFLMRegistration* registration_ = nullptr;
+  micro::KernelRunner* kernel_runner_ = nullptr;
+};
+
+// We can use any of the templated types here - int16_t was picked arbitrarily
+alignas(alignof(OverlapAddKernelRunner<int16_t>)) uint8_t
+    overlap_add_kernel_runner_buffer[sizeof(OverlapAddKernelRunner<int16_t>)];
+
+template <typename T>
+void TestOverlapAddInvoke(int* input_dims_data, T* input_data,
+                          int* output_dims_data, const T* golden_input,
+                          const T* golden_output, int iters,
+                          const unsigned char* flexbuffers_data,
+                          const unsigned int flexbuffers_data_size,
+                          T* output_data, tflite::micro::KernelRunner* runner) {
+  tflite::FlexbufferWrapper fbw(flexbuffers_data, flexbuffers_data_size);
+  int frame_step = fbw.ElementAsInt32(kFrameStepIndex);
+  int frame_size = input_dims_data[input_dims_data[0]];
+  int n_frames = input_dims_data[input_dims_data[0] - 1];
+  int outer_dims = 1;
+  for (int i = 1; i < input_dims_data[0] - 1; i++) {
+    outer_dims *= input_dims_data[i];
+  }
+  for (int i = 0; i < iters; i++) {
+    for (int outer_dim = 0; outer_dim < outer_dims; outer_dim++) {
+      int input_idx = outer_dim * n_frames * frame_size;
+      int golden_input_idx = i * n_frames * frame_size;
+      memcpy(&input_data[input_idx], &golden_input[golden_input_idx],
+             n_frames * frame_size * sizeof(T));
+    }
+    TF_LITE_MICRO_EXPECT_EQ(kTfLiteOk, runner->Invoke());
+    for (int outer_dim = 0; outer_dim < outer_dims; outer_dim++) {
+      int output_idx = outer_dim * n_frames * frame_step;
+      int golden_output_idx = i * n_frames * frame_step;
+      TF_LITE_MICRO_EXPECT_EQ(
+          0, memcmp(&output_data[output_idx], &golden_output[golden_output_idx],
+                    n_frames * frame_step * sizeof(T)));
+    }
+  }
+}
+
+template <typename T>
+void TestOverlapAdd(int* input_dims_data, T* input_data, int* output_dims_data,
+                    const T* golden_input, const T* golden_output, int iters,
+                    const unsigned char* flexbuffers_data,
+                    const unsigned int flexbuffers_data_size, T* output_data) {
+  OverlapAddKernelRunner<T>* overlap_add_runner =
+      new (overlap_add_kernel_runner_buffer) OverlapAddKernelRunner<T>(
+          input_dims_data, input_data, output_dims_data, output_data);
+  // TfLite uses a char* for the raw bytes whereas flexbuffers use an unsigned
+  // char*. This small discrepancy results in compiler warnings unless we
+  // reinterpret_cast right before passing in the flexbuffer bytes to the
+  // KernelRunner.
+  TF_LITE_MICRO_EXPECT_EQ(overlap_add_runner->GetKernelRunner().InitAndPrepare(
+                              reinterpret_cast<const char*>(flexbuffers_data),
+                              flexbuffers_data_size),
+                          kTfLiteOk);
+  TestOverlapAddInvoke<T>(input_dims_data, input_data, output_dims_data,
+                          golden_input, golden_output, iters, flexbuffers_data,
+                          flexbuffers_data_size, output_data,
+                          &overlap_add_runner->GetKernelRunner());
+}
+
+template <typename T>
+void TestOverlapAddReset(int* input_dims_data, T* input_data,
+                         int* output_dims_data, const T* golden_input,
+                         const T* golden_output, int iters,
+                         const unsigned char* flexbuffers_data,
+                         const unsigned int flexbuffers_data_size,
+                         T* output_data) {
+  OverlapAddKernelRunner<T>* overlap_add_runner =
+      new (overlap_add_kernel_runner_buffer) OverlapAddKernelRunner<T>(
+          input_dims_data, input_data, output_dims_data, output_data);
+  // TfLite uses a char* for the raw bytes whereas flexbuffers use an unsigned
+  // char*. This small discrepancy results in compiler warnings unless we
+  // reinterpret_cast right before passing in the flexbuffer bytes to the
+  // KernelRunner.
+  TF_LITE_MICRO_EXPECT_EQ(overlap_add_runner->GetKernelRunner().InitAndPrepare(
+                              reinterpret_cast<const char*>(flexbuffers_data),
+                              flexbuffers_data_size),
+                          kTfLiteOk);
+  TestOverlapAddInvoke(input_dims_data, input_data, output_dims_data,
+                       golden_input, golden_output, iters, flexbuffers_data,
+                       flexbuffers_data_size, output_data,
+                       &overlap_add_runner->GetKernelRunner());
+  overlap_add_runner->GetKernelRunner().Reset();
+  TestOverlapAddInvoke(input_dims_data, input_data, output_dims_data,
+                       golden_input, golden_output, iters, flexbuffers_data,
+                       flexbuffers_data_size, output_data,
+                       &overlap_add_runner->GetKernelRunner());
+}
+
+}  // namespace tflite
+
+TF_LITE_MICRO_TESTS_BEGIN
+
+TF_LITE_MICRO_TEST(OverlapAddTestInt16) {
+  const int kInputSize = 3;
+  const int kOutputSize = 1;
+  int input_dims_data[] = {2, 1, kInputSize};
+  int output_dims_data[] = {1, kOutputSize};
+  int16_t input_data[kInputSize];
+  int16_t output_data = 0;
+  const int16_t golden_input[] = {125, -12, -895, 1000, 65,  -212,
+                                  63,  71,  52,   1,    -17, 32};
+  const int16_t golden_output[] = {125, 988, -767, -140};
+
+  tflite::TestOverlapAdd(input_dims_data, input_data, output_dims_data,
+                         golden_input, golden_output,
+                         sizeof(golden_output) / sizeof(int16_t),
+                         g_gen_data_overlap_add_int16,
+                         g_gen_data_size_overlap_add_int16, &output_data);
+}
+
+TF_LITE_MICRO_TEST(OverlapAddTestFloat) {
+  const int kInputSize = 3;
+  const int kOutputSize = 1;
+  int input_dims_data[] = {2, 1, kInputSize};
+  int output_dims_data[] = {1, kOutputSize};
+  float input_data[kInputSize];
+  float output_data = 0;
+  const float golden_input[] = {12.5, -1.2, -89.5, 100.0, 6.5,  -21.2,
+                                6.3,  7.1,  5.2,   0.1,   -1.7, 3.2};
+  const float golden_output[] = {12.5, 98.8, -76.7, -14.0};
+
+  tflite::TestOverlapAdd(input_dims_data, input_data, output_dims_data,
+                         golden_input, golden_output,
+                         sizeof(golden_output) / sizeof(float),
+                         g_gen_data_overlap_add_float,
+                         g_gen_data_size_overlap_add_float, &output_data);
+}
+
+TF_LITE_MICRO_TEST(OverlapAddTestNframes4Int16) {
+  const int kInputSize = 3;
+  const int kOutputSize = 1;
+  const int kNFrames = 4;
+  int input_dims_data[] = {2, kNFrames, kInputSize};
+  int output_dims_data[] = {1, kNFrames * kOutputSize};
+  int16_t input_data[kNFrames * kInputSize];
+  int16_t output_data[kNFrames * kOutputSize];
+  const int16_t golden_input[] = {125, -12, -895, 1000, 65,  -212,
+                                  63,  71,  52,   1,    -17, 32};
+  const int16_t golden_output[] = {125, 988, -767, -140};
+
+  const int kIters =
+      sizeof(golden_input) / kInputSize / kNFrames / sizeof(int16_t);
+  tflite::TestOverlapAdd(input_dims_data, input_data, output_dims_data,
+                         golden_input, golden_output, kIters,
+                         g_gen_data_overlap_add_int16,
+                         g_gen_data_size_overlap_add_int16, output_data);
+}
+
+TF_LITE_MICRO_TEST(OverlapAddTestNframes4OuterDims4Int16) {
+  const int kInputSize = 3;
+  const int kOutputSize = 1;
+  const int kNFrames = 4;
+  int input_dims_data[] = {4, 2, 2, kNFrames, kInputSize};
+  int output_dims_data[] = {3, 2, 2, kNFrames * kOutputSize};
+  int16_t input_data[2 * 2 * kNFrames * kInputSize];
+  int16_t output_data[2 * 2 * kNFrames * kOutputSize];
+  const int16_t golden_input[] = {125, -12, -895, 1000, 65,  -212,
+                                  63,  71,  52,   1,    -17, 32};
+  const int16_t golden_output[] = {125, 988, -767, -140};
+
+  const int kIters =
+      sizeof(golden_input) / kInputSize / kNFrames / sizeof(int16_t);
+  tflite::TestOverlapAdd(input_dims_data, input_data, output_dims_data,
+                         golden_input, golden_output, kIters,
+                         g_gen_data_overlap_add_int16,
+                         g_gen_data_size_overlap_add_int16, output_data);
+}
+
+TF_LITE_MICRO_TEST(testReset) {
+  const int kInputSize = 3;
+  const int kOutputSize = 1;
+  const int kNFrames = 4;
+  int input_dims_data[] = {4, 2, 2, kNFrames, kInputSize};
+  int output_dims_data[] = {3, 2, 2, kNFrames * kOutputSize};
+  int16_t input_data[2 * 2 * kNFrames * kInputSize];
+  int16_t output_data[2 * 2 * kNFrames * kOutputSize];
+  const int16_t golden_input[] = {125, -12, -895, 1000, 65,  -212,
+                                  63,  71,  52,   1,    -17, 32};
+  const int16_t golden_output[] = {125, 988, -767, -140};
+
+  const int kIters =
+      sizeof(golden_input) / kInputSize / kNFrames / sizeof(int16_t);
+  tflite::TestOverlapAddReset(input_dims_data, input_data, output_dims_data,
+                              golden_input, golden_output, kIters,
+                              g_gen_data_overlap_add_int16,
+                              g_gen_data_size_overlap_add_int16, output_data);
+}
+
+TF_LITE_MICRO_TESTS_END
diff --git a/signal/src/BUILD b/signal/src/BUILD
index c5e51fb..ecb712b 100644
--- a/signal/src/BUILD
+++ b/signal/src/BUILD
@@ -4,12 +4,6 @@
 )
 
 cc_library(
-    name = "circular_buffer",
-    srcs = ["circular_buffer.cc"],
-    hdrs = ["circular_buffer.h"],
-)
-
-cc_library(
     name = "complex",
     hdrs = ["complex.h"],
 )
@@ -33,3 +27,15 @@
     srcs = ["window.cc"],
     hdrs = ["window.h"],
 )
+
+cc_library(
+    name = "circular_buffer",
+    srcs = ["circular_buffer.cc"],
+    hdrs = ["circular_buffer.h"],
+)
+
+cc_library(
+    name = "overlap_add",
+    srcs = ["overlap_add.cc"],
+    hdrs = ["overlap_add.h"],
+)
diff --git a/signal/src/overlap_add.cc b/signal/src/overlap_add.cc
new file mode 100644
index 0000000..fe6e664
--- /dev/null
+++ b/signal/src/overlap_add.cc
@@ -0,0 +1,51 @@
+/* Copyright 2021 The TensorFlow Authors. All Rights Reserved.
+
+Licensed under the Apache License, Version 2.0 (the "License");
+you may not use this file except in compliance with the License.
+You may obtain a copy of the License at
+
+    http://www.apache.org/licenses/LICENSE-2.0
+
+Unless required by applicable law or agreed to in writing, software
+distributed under the License is distributed on an "AS IS" BASIS,
+WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+See the License for the specific language governing permissions and
+limitations under the License.
+==============================================================================*/
+#include "signal/src/overlap_add.h"
+
+#include <stdio.h>
+#include <string.h>
+
+namespace tflm_signal {
+
+void OverlapAdd(const int16_t* input, int16_t* buffer, int input_size,
+                int16_t* output, int output_size) {
+  for (int i = 0; i < input_size; ++i) {
+    int32_t overlap_added_sample = input[i] + buffer[i];
+    if (overlap_added_sample < INT16_MIN) {
+      buffer[i] = INT16_MIN;
+    } else if (overlap_added_sample > INT16_MAX) {
+      buffer[i] = INT16_MAX;
+    } else {
+      buffer[i] = (int16_t)overlap_added_sample;
+    }
+  }
+  memcpy(output, buffer, output_size * sizeof(output[0]));
+  memmove(buffer, &buffer[output_size],
+          (input_size - output_size) * sizeof(buffer[0]));
+  memset(&buffer[input_size - output_size], 0, output_size * sizeof(buffer[0]));
+}
+
+void OverlapAdd(const float* input, float* buffer, int input_size,
+                float* output, int output_size) {
+  for (int i = 0; i < input_size; ++i) {
+    buffer[i] += input[i];
+  }
+  memcpy(output, buffer, output_size * sizeof(output[0]));
+  memmove(buffer, &buffer[output_size],
+          (input_size - output_size) * sizeof(buffer[0]));
+  memset(&buffer[input_size - output_size], 0, output_size * sizeof(buffer[0]));
+}
+
+}  // namespace tflm_signal
diff --git a/signal/src/overlap_add.h b/signal/src/overlap_add.h
new file mode 100644
index 0000000..6189809
--- /dev/null
+++ b/signal/src/overlap_add.h
@@ -0,0 +1,46 @@
+/* Copyright 2021 The TensorFlow Authors. All Rights Reserved.
+
+Licensed under the Apache License, Version 2.0 (the "License");
+you may not use this file except in compliance with the License.
+You may obtain a copy of the License at
+
+    http://www.apache.org/licenses/LICENSE-2.0
+
+Unless required by applicable law or agreed to in writing, software
+distributed under the License is distributed on an "AS IS" BASIS,
+WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+See the License for the specific language governing permissions and
+limitations under the License.
+==============================================================================*/
+#ifndef SIGNAL_SRC_OVERLAP_ADD_H_
+#define SIGNAL_SRC_OVERLAP_ADD_H_
+
+#include <stddef.h>
+#include <stdint.h>
+
+namespace tflm_signal {
+// Adds (with saturation) the contents of `input` to the contents of `buffer`,
+// both of size `input_size`, then copies the first `output_size` elements of
+// `buffer` to `output`, shifts the last `input_size`-`output_size` elements of
+// `buffer` to the beginning of `buffer` and fills the trailing `output_size`
+// samples in `buffer` with zeros.
+// input: {input[0] ... input[input_size-1]}
+// buffer: {buffer[0] ... buffer[input_size-1]}
+// After invocation:
+// output: {saturate(input[0] + buffer[0]),
+//          ... ,
+//          saturate(input[output_size-1] + buffer[output_size-1])}
+// buffer: {saturate(input[output_size] + buffer[output_size]),
+//          ...
+//          saturate(  input[input_size-output_size-1]
+//                   + buffer[input_size-output_size-1]),
+//          zeros(output_size)}
+void OverlapAdd(const int16_t* input, int16_t* buffer, int input_size,
+                int16_t* output, int output_size);
+
+// The same as the int16_t variant above, but without saturation
+void OverlapAdd(const float* input, float* buffer, int input_size,
+                float* output, int output_size);
+
+}  //  namespace tflm_signal
+#endif  // SIGNAL_SRC_OVERLAP_ADD_H_
diff --git a/tensorflow/lite/micro/kernels/Makefile.inc b/tensorflow/lite/micro/kernels/Makefile.inc
index f07af9b..96fb829 100644
--- a/tensorflow/lite/micro/kernels/Makefile.inc
+++ b/tensorflow/lite/micro/kernels/Makefile.inc
@@ -59,6 +59,11 @@
   $(TENSORFLOW_ROOT)signal/micro/kernels/framer_flexbuffers_generated_data.cc, \
   $(TENSORFLOW_ROOT)signal/micro/kernels/framer_flexbuffers_generated_data.h))
 
+$(eval $(call microlite_test,kernel_signal_overlap_add_test,\
+  $(TENSORFLOW_ROOT)signal/micro/kernels/overlap_add_test.cc \
+  $(TENSORFLOW_ROOT)signal/micro/kernels/overlap_add_flexbuffers_generated_data.cc, \
+  $(TENSORFLOW_ROOT)signal/micro/kernels/overlap_add_flexbuffers_generated_data.h))
+
 $(eval $(call microlite_test,kernel_signal_window_test,\
   $(TENSORFLOW_ROOT)signal/micro/kernels/window_test.cc \
   $(TENSORFLOW_ROOT)signal/micro/kernels/window_flexbuffers_generated_data.cc, \
diff --git a/tensorflow/lite/micro/kernels/micro_ops.h b/tensorflow/lite/micro/kernels/micro_ops.h
index 0a2391b..bfc2161 100644
--- a/tensorflow/lite/micro/kernels/micro_ops.h
+++ b/tensorflow/lite/micro/kernels/micro_ops.h
@@ -135,6 +135,7 @@
 // TODO(b/160234179): Change custom OPs to also return by value.
 namespace tflm_signal {
 TFLMRegistration* Register_FRAMER();
+TFLMRegistration* Register_OVERLAP_ADD();
 TFLMRegistration* Register_WINDOW();
 }  // namespace tflm_signal
 
diff --git a/tensorflow/lite/micro/micro_mutable_op_resolver.h b/tensorflow/lite/micro/micro_mutable_op_resolver.h
index 949ce26..c472b55 100644
--- a/tensorflow/lite/micro/micro_mutable_op_resolver.h
+++ b/tensorflow/lite/micro/micro_mutable_op_resolver.h
@@ -392,6 +392,12 @@
                       ParseNotEqual);
   }
 
+  TfLiteStatus AddOverlapAdd() {
+    // TODO(b/286250473): change back name to "OverlapAdd" and remove namespace
+    return AddCustom("SignalOverlapAdd",
+                     tflite::tflm_signal::Register_OVERLAP_ADD());
+  }
+
   TfLiteStatus AddPack() {
     return AddBuiltin(BuiltinOperator_PACK, Register_PACK(), ParsePack);
   }
diff --git a/tensorflow/lite/micro/tools/make/Makefile b/tensorflow/lite/micro/tools/make/Makefile
index 9a0ed19..2cb056d 100644
--- a/tensorflow/lite/micro/tools/make/Makefile
+++ b/tensorflow/lite/micro/tools/make/Makefile
@@ -314,8 +314,10 @@
 MICROLITE_CC_KERNEL_SRCS := \
 $(TENSORFLOW_ROOT)signal/micro/kernels/framer.cc \
 $(TENSORFLOW_ROOT)signal/micro/kernels/rfft.cc \
+$(TENSORFLOW_ROOT)signal/micro/kernels/overlap_add.cc \
 $(TENSORFLOW_ROOT)signal/micro/kernels/window.cc \
 $(TENSORFLOW_ROOT)signal/src/circular_buffer.cc \
+$(TENSORFLOW_ROOT)signal/src/overlap_add.cc \
 $(TENSORFLOW_ROOT)signal/src/rfft_float.cc \
 $(TENSORFLOW_ROOT)signal/src/rfft_int16.cc \
 $(TENSORFLOW_ROOT)signal/src/rfft_int32.cc \