Add a simple ring buffer and use it for holding TFLite model inputs.
Bug: 167946763
Test: atest libinput_tests
Change-Id: I7e50d38ed0c593aebc5fdc6af4b25868505d48bc
diff --git a/include/input/RingBuffer.h b/include/input/RingBuffer.h
new file mode 100644
index 0000000..67984b7
--- /dev/null
+++ b/include/input/RingBuffer.h
@@ -0,0 +1,293 @@
+/*
+ * Copyright (C) 2023 The Android Open Source Project
+ *
+ * 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.
+ */
+
+#pragma once
+
+#include <algorithm>
+#include <compare>
+#include <cstddef>
+#include <iterator>
+#include <memory>
+#include <type_traits>
+#include <utility>
+
+#include <android-base/logging.h>
+#include <android-base/stringprintf.h>
+
+namespace android {
+
+// A fixed-size ring buffer of elements.
+//
+// Elements can only be removed from the front/back or added to the front/back, but with O(1)
+// performance. Elements from the opposing side are evicted when new elements are pushed onto a full
+// buffer.
+template <typename T>
+class RingBuffer {
+public:
+ using value_type = T;
+ using size_type = size_t;
+ using difference_type = ptrdiff_t;
+ using reference = value_type&;
+ using const_reference = const value_type&;
+ using pointer = value_type*;
+ using const_pointer = const value_type*;
+
+ template <typename U>
+ class Iterator;
+ using iterator = Iterator<T>;
+ using const_iterator = Iterator<const T>;
+
+ // Creates an empty ring buffer that can hold some capacity.
+ explicit RingBuffer(size_type capacity)
+ : mBuffer(std::allocator<value_type>().allocate(capacity)), mCapacity(capacity) {}
+
+ // Creates a full ring buffer holding a fixed number of elements initialised to some value.
+ explicit RingBuffer(size_type count, const_reference value) : RingBuffer(count) {
+ while (count) {
+ pushBack(value);
+ --count;
+ }
+ }
+
+ RingBuffer(const RingBuffer& other) : RingBuffer(other.capacity()) {
+ for (const auto& element : other) {
+ pushBack(element);
+ }
+ }
+
+ RingBuffer(RingBuffer&& other) noexcept { *this = std::move(other); }
+
+ ~RingBuffer() {
+ if (mBuffer) {
+ clear();
+ std::allocator<value_type>().deallocate(mBuffer, mCapacity);
+ }
+ }
+
+ RingBuffer& operator=(const RingBuffer& other) { return *this = RingBuffer(other); }
+
+ RingBuffer& operator=(RingBuffer&& other) noexcept {
+ if (this == &other) {
+ return *this;
+ }
+ if (mBuffer) {
+ clear();
+ std::allocator<value_type>().deallocate(mBuffer, mCapacity);
+ }
+ mBuffer = std::move(other.mBuffer);
+ mCapacity = other.mCapacity;
+ mBegin = other.mBegin;
+ mSize = other.mSize;
+ other.mBuffer = nullptr;
+ other.mCapacity = 0;
+ other.mBegin = 0;
+ other.mSize = 0;
+ return *this;
+ }
+
+ iterator begin() { return {*this, 0}; }
+ const_iterator begin() const { return {*this, 0}; }
+ iterator end() { return {*this, mSize}; }
+ const_iterator end() const { return {*this, mSize}; }
+
+ reference operator[](size_type i) { return mBuffer[bufferIndex(i)]; }
+ const_reference operator[](size_type i) const { return mBuffer[bufferIndex(i)]; }
+
+ // Removes all elements from the buffer.
+ void clear() {
+ std::destroy(begin(), end());
+ mSize = 0;
+ }
+
+ // Removes and returns the first element from the buffer.
+ value_type popFront() {
+ value_type element = mBuffer[mBegin];
+ std::destroy_at(std::addressof(mBuffer[mBegin]));
+ mBegin = next(mBegin);
+ --mSize;
+ return element;
+ }
+
+ // Removes and returns the last element from the buffer.
+ value_type popBack() {
+ size_type backIndex = bufferIndex(mSize - 1);
+ value_type element = mBuffer[backIndex];
+ std::destroy_at(std::addressof(mBuffer[backIndex]));
+ --mSize;
+ return element;
+ }
+
+ // Adds an element to the front of the buffer.
+ void pushFront(const value_type& element) { pushFront(value_type(element)); }
+ void pushFront(value_type&& element) {
+ mBegin = previous(mBegin);
+ if (size() == capacity()) {
+ mBuffer[mBegin] = std::forward<value_type>(element);
+ } else {
+ // The space at mBuffer[mBegin] is uninitialised.
+ // TODO: Use std::construct_at when it becomes available.
+ new (std::addressof(mBuffer[mBegin])) value_type(std::forward<value_type>(element));
+ ++mSize;
+ }
+ }
+
+ // Adds an element to the back of the buffer.
+ void pushBack(const value_type& element) { pushBack(value_type(element)); }
+ void pushBack(value_type&& element) {
+ if (size() == capacity()) {
+ mBuffer[mBegin] = std::forward<value_type>(element);
+ mBegin = next(mBegin);
+ } else {
+ // The space at mBuffer[...] is uninitialised.
+ // TODO: Use std::construct_at when it becomes available.
+ new (std::addressof(mBuffer[bufferIndex(mSize)]))
+ value_type(std::forward<value_type>(element));
+ ++mSize;
+ }
+ }
+
+ bool empty() const { return mSize == 0; }
+ size_type capacity() const { return mCapacity; }
+ size_type size() const { return mSize; }
+
+ void swap(RingBuffer& other) noexcept {
+ using std::swap;
+ swap(mBuffer, other.mBuffer);
+ swap(mCapacity, other.mCapacity);
+ swap(mBegin, other.mBegin);
+ swap(mSize, other.mSize);
+ }
+
+ friend void swap(RingBuffer& lhs, RingBuffer& rhs) noexcept { lhs.swap(rhs); }
+
+ template <typename U>
+ class Iterator {
+ private:
+ using ContainerType = std::conditional_t<std::is_const_v<U>, const RingBuffer, RingBuffer>;
+
+ public:
+ using iterator_category = std::random_access_iterator_tag;
+ using size_type = ContainerType::size_type;
+ using difference_type = ContainerType::difference_type;
+ using value_type = std::remove_cv_t<U>;
+ using pointer = U*;
+ using reference = U&;
+
+ Iterator(ContainerType& container, size_type index)
+ : mContainer(container), mIndex(index) {}
+
+ Iterator(const Iterator&) = default;
+ Iterator& operator=(const Iterator&) = default;
+
+ Iterator& operator++() {
+ ++mIndex;
+ return *this;
+ }
+
+ Iterator operator++(int) {
+ Iterator iterator(*this);
+ ++(*this);
+ return iterator;
+ }
+
+ Iterator& operator--() {
+ --mIndex;
+ return *this;
+ }
+
+ Iterator operator--(int) {
+ Iterator iterator(*this);
+ --(*this);
+ return iterator;
+ }
+
+ Iterator& operator+=(difference_type n) {
+ mIndex += n;
+ return *this;
+ }
+
+ Iterator operator+(difference_type n) {
+ Iterator iterator(*this);
+ return iterator += n;
+ }
+
+ Iterator& operator-=(difference_type n) { return *this += -n; }
+
+ Iterator operator-(difference_type n) {
+ Iterator iterator(*this);
+ return iterator -= n;
+ }
+
+ difference_type operator-(const Iterator& other) { return mIndex - other.mIndex; }
+
+ bool operator==(const Iterator& rhs) const { return mIndex == rhs.mIndex; }
+
+ bool operator!=(const Iterator& rhs) const { return !(*this == rhs); }
+
+ friend auto operator<=>(const Iterator& lhs, const Iterator& rhs) {
+ return lhs.mIndex <=> rhs.mIndex;
+ }
+
+ reference operator[](difference_type n) { return *(*this + n); }
+
+ reference operator*() const { return mContainer[mIndex]; }
+ pointer operator->() const { return std::addressof(mContainer[mIndex]); }
+
+ private:
+ ContainerType& mContainer;
+ size_type mIndex = 0;
+ };
+
+private:
+ // Returns the index of the next element in mBuffer.
+ size_type next(size_type index) const {
+ if (index == capacity() - 1) {
+ return 0;
+ } else {
+ return index + 1;
+ }
+ }
+
+ // Returns the index of the previous element in mBuffer.
+ size_type previous(size_type index) const {
+ if (index == 0) {
+ return capacity() - 1;
+ } else {
+ return index - 1;
+ }
+ }
+
+ // Converts the index of an element in [0, size()] to its corresponding index in mBuffer.
+ size_type bufferIndex(size_type elementIndex) const {
+ CHECK_LE(elementIndex, size());
+ size_type index = mBegin + elementIndex;
+ if (index >= capacity()) {
+ index -= capacity();
+ }
+ CHECK_LT(index, capacity())
+ << android::base::StringPrintf("Invalid index calculated for element (%zu) "
+ "in buffer of size %zu",
+ elementIndex, size());
+ return index;
+ }
+
+ pointer mBuffer = nullptr;
+ size_type mCapacity = 0; // Total capacity of mBuffer.
+ size_type mBegin = 0; // Index of the first initialised element in mBuffer.
+ size_type mSize = 0; // Total number of initialised elements.
+};
+
+} // namespace android
diff --git a/include/input/TfLiteMotionPredictor.h b/include/input/TfLiteMotionPredictor.h
index ff0f51c..704349c 100644
--- a/include/input/TfLiteMotionPredictor.h
+++ b/include/input/TfLiteMotionPredictor.h
@@ -23,7 +23,8 @@
#include <optional>
#include <span>
#include <string>
-#include <vector>
+
+#include <input/RingBuffer.h>
#include <tensorflow/lite/core/api/error_reporter.h>
#include <tensorflow/lite/interpreter.h>
@@ -83,11 +84,11 @@
private:
int64_t mTimestamp = 0;
- std::vector<float> mInputR;
- std::vector<float> mInputPhi;
- std::vector<float> mInputPressure;
- std::vector<float> mInputTilt;
- std::vector<float> mInputOrientation;
+ RingBuffer<float> mInputR;
+ RingBuffer<float> mInputPhi;
+ RingBuffer<float> mInputPressure;
+ RingBuffer<float> mInputTilt;
+ RingBuffer<float> mInputOrientation;
// The samples defining the current polar axis.
std::optional<TfLiteMotionPredictorSample> mAxisFrom;
diff --git a/libs/input/TfLiteMotionPredictor.cpp b/libs/input/TfLiteMotionPredictor.cpp
index 1a337ad..40653d3 100644
--- a/libs/input/TfLiteMotionPredictor.cpp
+++ b/libs/input/TfLiteMotionPredictor.cpp
@@ -104,13 +104,13 @@
} // namespace
-TfLiteMotionPredictorBuffers::TfLiteMotionPredictorBuffers(size_t inputLength) {
+TfLiteMotionPredictorBuffers::TfLiteMotionPredictorBuffers(size_t inputLength)
+ : mInputR(inputLength, 0),
+ mInputPhi(inputLength, 0),
+ mInputPressure(inputLength, 0),
+ mInputTilt(inputLength, 0),
+ mInputOrientation(inputLength, 0) {
LOG_ALWAYS_FATAL_IF(inputLength == 0, "Buffer input size must be greater than 0");
- mInputR.resize(inputLength);
- mInputPhi.resize(inputLength);
- mInputPressure.resize(inputLength);
- mInputTilt.resize(inputLength);
- mInputOrientation.resize(inputLength);
}
void TfLiteMotionPredictorBuffers::reset() {
@@ -186,17 +186,11 @@
mAxisTo = sample;
// Push the current sample onto the end of the input buffers.
- mInputR.erase(mInputR.begin());
- mInputPhi.erase(mInputPhi.begin());
- mInputPressure.erase(mInputPressure.begin());
- mInputTilt.erase(mInputTilt.begin());
- mInputOrientation.erase(mInputOrientation.begin());
-
- mInputR.push_back(r);
- mInputPhi.push_back(phi);
- mInputPressure.push_back(sample.pressure);
- mInputTilt.push_back(sample.tilt);
- mInputOrientation.push_back(orientation);
+ mInputR.pushBack(r);
+ mInputPhi.pushBack(phi);
+ mInputPressure.pushBack(sample.pressure);
+ mInputTilt.pushBack(sample.tilt);
+ mInputOrientation.pushBack(orientation);
}
std::unique_ptr<TfLiteMotionPredictorModel> TfLiteMotionPredictorModel::create(
diff --git a/libs/input/tests/Android.bp b/libs/input/tests/Android.bp
index 916a8f2..f07164c 100644
--- a/libs/input/tests/Android.bp
+++ b/libs/input/tests/Android.bp
@@ -19,6 +19,7 @@
"InputEvent_test.cpp",
"InputPublisherAndConsumer_test.cpp",
"MotionPredictor_test.cpp",
+ "RingBuffer_test.cpp",
"TfLiteMotionPredictor_test.cpp",
"TouchResampling_test.cpp",
"TouchVideoFrame_test.cpp",
diff --git a/libs/input/tests/RingBuffer_test.cpp b/libs/input/tests/RingBuffer_test.cpp
new file mode 100644
index 0000000..8a6ef4c
--- /dev/null
+++ b/libs/input/tests/RingBuffer_test.cpp
@@ -0,0 +1,208 @@
+/*
+ * Copyright (C) 2023 The Android Open Source Project
+ *
+ * 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 <algorithm>
+#include <iterator>
+#include <memory>
+#include <vector>
+
+#include <gmock/gmock.h>
+#include <gtest/gtest.h>
+#include <input/RingBuffer.h>
+
+namespace android {
+namespace {
+
+using ::testing::ElementsAre;
+using ::testing::ElementsAreArray;
+using ::testing::IsEmpty;
+using ::testing::Not;
+using ::testing::SizeIs;
+
+TEST(RingBufferTest, PushPop) {
+ RingBuffer<int> buffer(/*capacity=*/3);
+
+ buffer.pushBack(1);
+ buffer.pushBack(2);
+ buffer.pushBack(3);
+ EXPECT_THAT(buffer, ElementsAre(1, 2, 3));
+
+ buffer.pushBack(4);
+ EXPECT_THAT(buffer, ElementsAre(2, 3, 4));
+
+ buffer.pushFront(1);
+ EXPECT_THAT(buffer, ElementsAre(1, 2, 3));
+
+ EXPECT_EQ(1, buffer.popFront());
+ EXPECT_THAT(buffer, ElementsAre(2, 3));
+
+ buffer.pushBack(4);
+ EXPECT_THAT(buffer, ElementsAre(2, 3, 4));
+
+ buffer.pushBack(5);
+ EXPECT_THAT(buffer, ElementsAre(3, 4, 5));
+
+ EXPECT_EQ(5, buffer.popBack());
+ EXPECT_THAT(buffer, ElementsAre(3, 4));
+
+ EXPECT_EQ(4, buffer.popBack());
+ EXPECT_THAT(buffer, ElementsAre(3));
+
+ EXPECT_EQ(3, buffer.popBack());
+ EXPECT_THAT(buffer, ElementsAre());
+
+ buffer.pushBack(1);
+ EXPECT_THAT(buffer, ElementsAre(1));
+
+ EXPECT_EQ(1, buffer.popFront());
+ EXPECT_THAT(buffer, ElementsAre());
+}
+
+TEST(RingBufferTest, ObjectType) {
+ RingBuffer<std::unique_ptr<int>> buffer(/*capacity=*/2);
+ buffer.pushBack(std::make_unique<int>(1));
+ buffer.pushBack(std::make_unique<int>(2));
+ buffer.pushBack(std::make_unique<int>(3));
+
+ EXPECT_EQ(2, *buffer[0]);
+ EXPECT_EQ(3, *buffer[1]);
+}
+
+TEST(RingBufferTest, ConstructConstantValue) {
+ RingBuffer<int> buffer(/*count=*/3, /*value=*/10);
+ EXPECT_THAT(buffer, ElementsAre(10, 10, 10));
+ EXPECT_EQ(3u, buffer.capacity());
+}
+
+TEST(RingBufferTest, Assignment) {
+ RingBuffer<int> a(/*capacity=*/2);
+ a.pushBack(1);
+ a.pushBack(2);
+
+ RingBuffer<int> b(/*capacity=*/3);
+ b.pushBack(10);
+ b.pushBack(20);
+ b.pushBack(30);
+
+ std::swap(a, b);
+ EXPECT_THAT(a, ElementsAre(10, 20, 30));
+ EXPECT_THAT(b, ElementsAre(1, 2));
+
+ a = b;
+ EXPECT_THAT(a, ElementsAreArray(b));
+
+ RingBuffer<int> c(b);
+ EXPECT_THAT(c, ElementsAreArray(b));
+
+ RingBuffer<int> d(std::move(b));
+ EXPECT_EQ(0u, b.capacity());
+ EXPECT_THAT(b, ElementsAre());
+ EXPECT_THAT(d, ElementsAre(1, 2));
+
+ b = std::move(d);
+ EXPECT_THAT(b, ElementsAre(1, 2));
+ EXPECT_THAT(d, ElementsAre());
+ EXPECT_EQ(0u, d.capacity());
+}
+
+TEST(RingBufferTest, Subscripting) {
+ RingBuffer<int> buffer(/*capacity=*/2);
+ buffer.pushBack(1);
+ EXPECT_EQ(1, buffer[0]);
+
+ buffer.pushFront(0);
+ EXPECT_EQ(0, buffer[0]);
+ EXPECT_EQ(1, buffer[1]);
+
+ buffer.pushFront(-1);
+ EXPECT_EQ(-1, buffer[0]);
+ EXPECT_EQ(0, buffer[1]);
+}
+
+TEST(RingBufferTest, Iterator) {
+ RingBuffer<int> buffer(/*capacity=*/3);
+ buffer.pushFront(2);
+ buffer.pushBack(3);
+
+ auto begin = buffer.begin();
+ auto end = buffer.end();
+
+ EXPECT_NE(begin, end);
+ EXPECT_LE(begin, end);
+ EXPECT_GT(end, begin);
+ EXPECT_EQ(end, begin + 2);
+ EXPECT_EQ(begin, end - 2);
+
+ EXPECT_EQ(2, end - begin);
+ EXPECT_EQ(1, end - (begin + 1));
+
+ EXPECT_EQ(2, *begin);
+ ++begin;
+ EXPECT_EQ(3, *begin);
+ --begin;
+ EXPECT_EQ(2, *begin);
+ begin += 1;
+ EXPECT_EQ(3, *begin);
+ begin += -1;
+ EXPECT_EQ(2, *begin);
+ begin -= -1;
+ EXPECT_EQ(3, *begin);
+}
+
+TEST(RingBufferTest, Clear) {
+ RingBuffer<int> buffer(/*capacity=*/2);
+ EXPECT_THAT(buffer, ElementsAre());
+
+ buffer.pushBack(1);
+ EXPECT_THAT(buffer, ElementsAre(1));
+
+ buffer.clear();
+ EXPECT_THAT(buffer, ElementsAre());
+ EXPECT_THAT(buffer, SizeIs(0));
+ EXPECT_THAT(buffer, IsEmpty());
+
+ buffer.pushFront(1);
+ EXPECT_THAT(buffer, ElementsAre(1));
+}
+
+TEST(RingBufferTest, SizeAndIsEmpty) {
+ RingBuffer<int> buffer(/*capacity=*/2);
+ EXPECT_THAT(buffer, SizeIs(0));
+ EXPECT_THAT(buffer, IsEmpty());
+
+ buffer.pushBack(1);
+ EXPECT_THAT(buffer, SizeIs(1));
+ EXPECT_THAT(buffer, Not(IsEmpty()));
+
+ buffer.pushBack(2);
+ EXPECT_THAT(buffer, SizeIs(2));
+ EXPECT_THAT(buffer, Not(IsEmpty()));
+
+ buffer.pushBack(3);
+ EXPECT_THAT(buffer, SizeIs(2));
+ EXPECT_THAT(buffer, Not(IsEmpty()));
+
+ buffer.popFront();
+ EXPECT_THAT(buffer, SizeIs(1));
+ EXPECT_THAT(buffer, Not(IsEmpty()));
+
+ buffer.popBack();
+ EXPECT_THAT(buffer, SizeIs(0));
+ EXPECT_THAT(buffer, IsEmpty());
+}
+
+} // namespace
+} // namespace android