aboutsummaryrefslogtreecommitdiff
path: root/src/base
diff options
context:
space:
mode:
Diffstat (limited to 'src/base')
-rw-r--r--src/base/BUILD.bazel45
-rw-r--r--src/base/bit_stream.h77
-rw-r--r--src/base/bottom_n.h78
-rw-r--r--src/base/math_utils.h80
-rw-r--r--src/base/optional.h520
-rw-r--r--src/base/string_utils.h68
-rw-r--r--src/base/test/bit_stream_test.cpp141
-rw-r--r--src/base/test/bottom_n_test.cpp99
-rw-r--r--src/base/test/math_utils_test.cpp78
-rw-r--r--src/base/test/optional_test.cpp481
-rw-r--r--src/base/test/string_utils_test.cpp110
-rw-r--r--src/base/test/type_traits_test.cpp128
-rw-r--r--src/base/test/uint128_test.cpp140
-rw-r--r--src/base/type_traits.h172
-rw-r--r--src/base/uint128.h175
15 files changed, 2392 insertions, 0 deletions
diff --git a/src/base/BUILD.bazel b/src/base/BUILD.bazel
new file mode 100644
index 0000000..9d8b9a0
--- /dev/null
+++ b/src/base/BUILD.bazel
@@ -0,0 +1,45 @@
+# Copyright 2018 Google LLC
+#
+# 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
+#
+# https://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.
+
+cc_library(
+ name = "base",
+ hdrs = [
+ "bit_stream.h",
+ "bottom_n.h",
+ "math_utils.h",
+ "optional.h",
+ "string_utils.h",
+ "type_traits.h",
+ "uint128.h",
+ ],
+ visibility = ["//src/decoder:__pkg__"],
+)
+
+cc_test(
+ name = "base_test",
+ srcs = [
+ "test/bit_stream_test.cpp",
+ "test/bottom_n_test.cpp",
+ "test/math_utils_test.cpp",
+ "test/optional_test.cpp",
+ "test/string_utils_test.cpp",
+ "test/type_traits_test.cpp",
+ "test/uint128_test.cpp",
+ ],
+ deps = [
+ "@gtest//:gtest_main",
+ ":base",
+ ],
+)
+
diff --git a/src/base/bit_stream.h b/src/base/bit_stream.h
new file mode 100644
index 0000000..c878197
--- /dev/null
+++ b/src/base/bit_stream.h
@@ -0,0 +1,77 @@
+// Copyright 2018 Google LLC
+//
+// 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
+//
+// https://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 ASTC_CODEC_BASE_BIT_STREAM_H_
+#define ASTC_CODEC_BASE_BIT_STREAM_H_
+
+#include <cassert>
+#include <cstdint>
+
+namespace astc_codec {
+namespace base {
+
+// Represents a stream of bits that can be read or written in arbitrary-sized
+// chunks.
+template<typename IntType = uint64_t>
+class BitStream {
+ public:
+ // Creates an empty BitStream.
+ BitStream() = default;
+ BitStream(IntType data, uint32_t data_size)
+ : data_(data), data_size_(data_size) {
+ assert(data_size_ <= sizeof(data_) * 8);
+ }
+
+ // Return the number of bits in the stream.
+ uint32_t Bits() const { return data_size_; }
+
+ // Put |size| bits into the stream.
+ // Fails if there is not enough space in the buffer to store the bits.
+ template<typename ResultType>
+ void PutBits(ResultType x, uint32_t size) {
+ assert(data_size_ + size <= sizeof(data_) * 8);
+
+ data_ |= (IntType(x) & MaskFor(size)) << data_size_;
+ data_size_ += size;
+ }
+
+ // Get |count| bits from the stream.
+ // Returns true if |count| bits were successfully retrieved.
+ template<typename ResultType>
+ bool GetBits(uint32_t count, ResultType* result) {
+ if (count <= data_size_) {
+ *result = static_cast<ResultType>(data_ & MaskFor(count));
+ data_ = data_ >> count;
+ data_size_ -= count;
+ return true;
+ } else {
+ *result = 0;
+ return false;
+ }
+ }
+
+ private:
+ IntType MaskFor(uint32_t bits) const {
+ return (bits == sizeof(IntType) * 8) ? ~IntType(0)
+ : (IntType(1) << bits) - 1;
+ }
+
+ IntType data_ = 0;
+ uint32_t data_size_ = 0;
+};
+
+} // namespace base
+} // namespace astc_codec
+
+#endif // ASTC_CODEC_BASE_BIT_STREAM_H_
diff --git a/src/base/bottom_n.h b/src/base/bottom_n.h
new file mode 100644
index 0000000..4edc8ef
--- /dev/null
+++ b/src/base/bottom_n.h
@@ -0,0 +1,78 @@
+// Copyright 2018 Google LLC
+//
+// 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
+//
+// https://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 ASTC_CODEC_BASE_BOTTOM_N_H_
+#define ASTC_CODEC_BASE_BOTTOM_N_H_
+
+#include <algorithm>
+#include <functional>
+#include <vector>
+
+namespace astc_codec {
+namespace base {
+
+// Used to aggregate the lowest N values of data supplied.
+template<typename T, typename CompareFn = std::less<T>>
+class BottomN {
+ public:
+ typedef std::vector<T> ContainerType;
+
+ // Creates an empty BottomN with limit |max_size|.
+ BottomN(size_t max_size) : max_size_(max_size) { }
+
+ bool Empty() const { return data_.empty(); }
+ size_t Size() const { return data_.size(); }
+
+ const T& Top() const { return data_.front(); }
+
+ void Push(const T& value) {
+ if (data_.size() < max_size_ || compare_(value, Top())) {
+ data_.push_back(value);
+ std::push_heap(data_.begin(), data_.end(), compare_);
+
+ if (Size() > max_size_) {
+ PopTop();
+ }
+ }
+ }
+
+ std::vector<T> Pop() {
+ const size_t len = Size();
+ std::vector<T> result(len);
+
+ for (size_t i = 0; i < len; ++i) {
+ result[len - i - 1] = PopTop();
+ }
+
+ return result;
+ }
+
+ private:
+ T PopTop() {
+ std::pop_heap(data_.begin(), data_.end(), compare_);
+ T result = data_.back();
+ data_.pop_back();
+ return result;
+ }
+
+ ContainerType data_;
+ CompareFn compare_;
+
+ const size_t max_size_;
+};
+
+} // namespace base
+} // namespace astc_codec
+
+#endif // ASTC_CODEC_BASE_BOTTOM_N_H_
diff --git a/src/base/math_utils.h b/src/base/math_utils.h
new file mode 100644
index 0000000..48f1a24
--- /dev/null
+++ b/src/base/math_utils.h
@@ -0,0 +1,80 @@
+// Copyright 2018 Google LLC
+//
+// 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
+//
+// https://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 ASTC_CODEC_BASE_MATH_UTILS_H_
+#define ASTC_CODEC_BASE_MATH_UTILS_H_
+
+#include "src/base/uint128.h"
+
+#include <cassert>
+#include <cstdint>
+#include <type_traits>
+
+namespace astc_codec {
+namespace base {
+
+inline int Log2Floor(uint32_t n) {
+ if (n == 0) {
+ return -1;
+ }
+
+ int log = 0;
+ uint32_t value = n;
+ for (int i = 4; i >= 0; --i) {
+ int shift = (1 << i);
+ uint32_t x = value >> shift;
+ if (x != 0) {
+ value = x;
+ log += shift;
+ }
+ }
+ assert(value == 1);
+ return log;
+}
+
+inline int CountOnes(uint32_t n) {
+ n -= ((n >> 1) & 0x55555555);
+ n = ((n >> 2) & 0x33333333) + (n & 0x33333333);
+ return static_cast<int>((((n + (n >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24);
+}
+
+template<typename T>
+inline T ReverseBits(T value) {
+ uint32_t s = sizeof(value) * 8;
+ T mask = ~T(0);
+ while ((s >>= 1) > 0) {
+ mask ^= (mask << s);
+ value = ((value >> s) & mask) | ((value << s) & ~mask);
+ }
+
+ return value;
+}
+
+template<typename T>
+inline T GetBits(T source, uint32_t offset, uint32_t count) {
+ static_assert(std::is_same<T, UInt128>::value || std::is_unsigned<T>::value,
+ "T must be unsigned.");
+
+ const uint32_t total_bits = sizeof(T) * 8;
+ assert(count > 0);
+ assert(offset + count <= total_bits);
+
+ const T mask = count == total_bits ? ~T(0) : ~T(0) >> (total_bits - count);
+ return (source >> offset) & mask;
+}
+
+} // namespace base
+} // namespace astc_codec
+
+#endif // ASTC_CODEC_BASE_MATH_UTILS_H_
diff --git a/src/base/optional.h b/src/base/optional.h
new file mode 100644
index 0000000..5ede4af
--- /dev/null
+++ b/src/base/optional.h
@@ -0,0 +1,520 @@
+// Copyright 2018 Google LLC
+//
+// 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
+//
+// https://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 ASTC_CODEC_BASE_OPTIONAL_H_
+#define ASTC_CODEC_BASE_OPTIONAL_H_
+
+#include "src/base/type_traits.h"
+
+#include <cassert>
+#include <initializer_list>
+#include <type_traits>
+#include <utility>
+
+#include <cstddef>
+
+// Optional<T> - a template class to store an optional value of type T.
+//
+// Usage examples:
+//
+// Initialization and construction:
+// Optional<Foo> foo; // |foo| doesn't contain a value.
+// Optional<Foo> foo(Foo(10)); // |foo| contains a copy-constructed value.
+// Optional<Foo> foo2(foo); // |foo2| contains a copy of |foo|'s value.
+// Optional<Foo> foo3(std::move(foo2)); // Guess what?
+//
+// Assignment:
+// Foo foo_value(0);
+// Optional<Foo> foo; // |foo| is empty.
+// Optional<Foo> foo2; // |foo2| is empty.
+// foo2 = foo; // |foo2| is still empty.
+// foo = foo_value; // set value of |foo| to a copy of |foo_value|
+// foo = std::move(foo_value); // move |foo_value| into |foo|.
+// foo2 = foo; // now |foo2| has a copy of |foo|'s value.
+// foo = kNullopt; // unset |foo|, it has no value.
+//
+// Checking and accessing value:
+// if (foo) {
+// // |foo| has a value.
+// doStuff(*foo); // |*foo| is the value inside |foo|.
+// foo->callMethod(); // Same as (*foo).callMethod().
+// } else {
+// // |foo| is empty.
+// }
+//
+// foo.value() // Same as *foo
+// foo.valueOr(<default>) // Return <default> is |foo| has no value.
+//
+// In-place construction:
+//
+// Optional<Foo> foo; // |foo| is empty.
+// foo.emplace(20); // |foo| now contains a value constructed as Foo(20)
+//
+// Optional<Foo> foo(kInplace, 20); // |foo| is initialized with a value
+// // that is constructed in-place as
+// // Foo(20).
+//
+// return makeOptional<Foo>(20); // Takes Foo constructor arguments
+// // directly.
+//
+// Returning values:
+//
+// Optional<Foo> myFunc(...) {
+// if (someCondition) {
+// return Foo(10); // call Optional<Foo>(Foo&) constructor.
+// } else {
+// return {}; // call Optional<Foo>() constructor, which
+// // builds an empty value.
+// }
+// }
+//
+// Memory layout:
+// Optional<Foo> is equivalent to:
+//
+// struct {
+// bool flag;
+// Foo value;
+// };
+//
+// in terms of memory layout. This means it *doubles* the size of integral
+// types. Also:
+//
+// - Optional<Foo> can be constructed from anything that constructs a Foo.
+//
+// - Same with Optional<Foo>(kInplace, Args...) where Args... matches any
+// arguments that can be passed to a Foo constructor.
+//
+// - Comparison operators are provided. Beware: an empty Optional<Foo>
+// is always smaller than any Foo value.
+
+namespace astc_codec {
+namespace base {
+
+namespace details {
+
+// Base classes to reduce the number of instantiations of the Optional's
+// internal members.
+class OptionalFlagBase {
+ public:
+ void setConstructed(bool constructed) { mConstructed = constructed; }
+ constexpr bool constructed() const { return mConstructed; }
+ constexpr operator bool() const { return constructed(); }
+ bool hasValue() const { return constructed(); }
+
+ constexpr OptionalFlagBase(bool constructed = false)
+ : mConstructed(constructed) { }
+
+ private:
+ bool mConstructed = false;
+};
+
+template<size_t Size, size_t Align>
+class OptionalStorageBase {
+ protected:
+ using StoreT = typename std::aligned_storage<Size, Align>::type;
+ StoreT mStorage = {};
+};
+
+} // namespace details
+
+// A tag type for empty optional construction
+struct NulloptT {
+ constexpr explicit NulloptT(int) { }
+};
+
+// A tag type for inplace value construction
+struct InplaceT {
+ constexpr explicit InplaceT(int) { }
+};
+
+// Tag values for null optional and inplace construction
+constexpr NulloptT kNullopt{1};
+constexpr InplaceT kInplace{1};
+
+// Forward declaration for an early use
+template<class T>
+class Optional;
+
+// A type trait for checking if a type is an optional instantiation
+// Note: if you want to refer to the template name inside the template,
+// you need to declare this alias outside of it - because the
+// class name inside of the template stands for an instantiated template
+// E.g, for template <T> class Foo if you say 'Foo' inside the class, it
+// actually means Foo<T>;
+template<class U>
+using is_any_optional =
+ is_template_instantiation_of<typename std::decay<U>::type, Optional>;
+
+template<class T>
+class Optional
+ : private details::OptionalFlagBase,
+ private details::OptionalStorageBase<sizeof(T),
+ std::alignment_of<T>::value> {
+ // make sure all optionals are buddies - this is needed to implement
+ // conversion from optionals of other types
+ template<class U>
+ friend class Optional;
+
+ template<class U>
+ using self = Optional<U>;
+
+ using base_flag = details::OptionalFlagBase;
+ using base_storage =
+ details::OptionalStorageBase<sizeof(T), std::alignment_of<T>::value>;
+
+ public:
+ // std::optional will have this, so let's provide it
+ using value_type = T;
+
+ // make sure we forbid some Optional instantiations where things may get
+ // really messy
+ static_assert(!std::is_same<typename std::decay<T>::type, NulloptT>::value,
+ "Optional of NulloptT is not allowed");
+ static_assert(!std::is_same<typename std::decay<T>::type, InplaceT>::value,
+ "Optional of InplaceT is not allowed");
+ static_assert(!std::is_reference<T>::value,
+ "Optional references are not allowed: use a pointer instead");
+
+ // constructors
+ constexpr Optional() { }
+ constexpr Optional(NulloptT) { }
+
+ Optional(const Optional& other) : base_flag(other.constructed()) {
+ if (this->constructed()) {
+ new (&get()) T(other.get());
+ }
+ }
+ Optional(Optional&& other) : base_flag(other.constructed()) {
+ if (this->constructed()) {
+ new (&get()) T(std::move(other.get()));
+ }
+ }
+
+ // Conversion constructor from optional of similar type
+ template<class U, class = enable_if_c<!is_any_optional<U>::value &&
+ std::is_constructible<T, U>::value>>
+ Optional(const Optional<U>& other) : base_flag(other.constructed()) {
+ if (this->constructed()) {
+ new (&get()) T(other.get());
+ }
+ }
+
+ // Move-conversion constructor
+ template<class U, class = enable_if_c<!is_any_optional<U>::value &&
+ std::is_constructible<T, U>::value>>
+ Optional(Optional<U>&& other) : base_flag(other.constructed()) {
+ if (this->constructed()) {
+ new (&get()) T(std::move(other.get()));
+ }
+ }
+
+ // Construction from a raw value
+ Optional(const T& value) : base_flag(true) { new (&get()) T(value); }
+ // Move construction from a raw value
+ Optional(T&& value) : base_flag(true) { new (&get()) T(std::move(value)); }
+
+ // Inplace construction from a list of |T|'s ctor arguments
+ template<class... Args>
+ Optional(InplaceT, Args&&... args) : base_flag(true) {
+ new (&get()) T(std::forward<Args>(args)...);
+ }
+
+ // Inplace construction from an initializer list passed into |T|'s ctor
+ template<class U, class = enable_if<
+ std::is_constructible<T, std::initializer_list<U>>>>
+ Optional(InplaceT, std::initializer_list<U> il) : base_flag(true) {
+ new (&get()) T(il);
+ }
+
+ // direct assignment
+ Optional& operator=(const Optional& other) {
+ if (&other == this) {
+ return *this;
+ }
+
+ if (this->constructed()) {
+ if (other.constructed()) {
+ get() = other.get();
+ } else {
+ destruct();
+ this->setConstructed(false);
+ }
+ } else {
+ if (other.constructed()) {
+ new (&get()) T(other.get());
+ this->setConstructed(true);
+ } else {
+ ; // we're good
+ }
+ }
+ return *this;
+ }
+
+ // move assignment
+ Optional& operator=(Optional&& other) {
+ if (this->constructed()) {
+ if (other.constructed()) {
+ get() = std::move(other.get());
+ } else {
+ destruct();
+ this->setConstructed(false);
+ }
+ } else {
+ if (other.constructed()) {
+ new (&get()) T(std::move(other.get()));
+ this->setConstructed(true);
+ } else {
+ ; // we're good
+ }
+ }
+ return *this;
+ }
+
+ // conversion assignment
+ template<class U,
+ class = enable_if_convertible<typename std::decay<U>::type, T>>
+ Optional& operator=(const Optional<U>& other) {
+ if (this->constructed()) {
+ if (other.constructed()) {
+ get() = other.get();
+ } else {
+ destruct();
+ this->setConstructed(false);
+ }
+ } else {
+ if (other.constructed()) {
+ new (&get()) T(other.get());
+ this->setConstructed(true);
+ } else {
+ ; // we're good
+ }
+ }
+ return *this;
+ }
+
+ // conversion move assignment
+ template<class U,
+ class = enable_if_convertible<typename std::decay<U>::type, T>>
+ Optional& operator=(Optional<U>&& other) {
+ if (this->constructed()) {
+ if (other.constructed()) {
+ get() = std::move(other.get());
+ } else {
+ destruct();
+ this->setConstructed(false);
+ }
+ } else {
+ if (other.constructed()) {
+ new (&get()) T(std::move(other.get()));
+ this->setConstructed(true);
+ } else {
+ ; // we're good
+ }
+ }
+ return *this;
+ }
+
+ // the most complicated one: forwarding constructor for anything convertible
+ // to |T|, excluding the stuff implemented above explicitly
+ template<class U,
+ class = enable_if_c<
+ !is_any_optional<typename std::decay<U>::type>::value &&
+ std::is_convertible<typename std::decay<U>::type, T>::value>>
+ Optional& operator=(U&& other) {
+ if (this->constructed()) {
+ get() = std::forward<U>(other);
+ } else {
+ new (&get()) T(std::forward<U>(other));
+ this->setConstructed(true);
+ }
+ return *this;
+ }
+
+ // Adopt value checkers from the parent
+ using base_flag::operator bool;
+ using base_flag::hasValue;
+
+ T& value() {
+ assert(this->constructed());
+ return get();
+ }
+ constexpr const T& value() const {
+ assert(this->constructed());
+ return get();
+ }
+
+ T* ptr() { return this->constructed() ? &get() : nullptr; }
+ constexpr const T* ptr() const {
+ return this->constructed() ? &get() : nullptr;
+ }
+
+ // Value getter with fallback
+ template<class U = T,
+ class = enable_if_convertible<typename std::decay<U>::type, T>>
+ constexpr T valueOr(U&& defaultValue) const {
+ return this->constructed() ? get() : std::move(defaultValue);
+ }
+
+ // Pointer-like operators
+ T& operator*() {
+ assert(this->constructed());
+ return get();
+ }
+ constexpr const T& operator*() const {
+ assert(this->constructed());
+ return get();
+ }
+
+ T* operator->() {
+ assert(this->constructed());
+ return &get();
+ }
+ constexpr const T* operator->() const {
+ assert(this->constructed());
+ return &get();
+ }
+
+ ~Optional() {
+ if (this->constructed()) {
+ destruct();
+ }
+ }
+
+ void clear() {
+ if (this->constructed()) {
+ destruct();
+ this->setConstructed(false);
+ }
+ }
+
+ template<class U,
+ class = enable_if_convertible<typename std::decay<U>::type, T>>
+ void reset(U&& u) {
+ *this = std::forward<U>(u);
+ }
+
+ // In-place construction with possible destruction of the old value
+ template<class... Args>
+ void emplace(Args&&... args) {
+ if (this->constructed()) {
+ destruct();
+ }
+ new (&get()) T(std::forward<Args>(args)...);
+ this->setConstructed(true);
+ }
+
+ // In-place construction with possible destruction of the old value
+ // initializer-list version
+ template<class U, class = enable_if<
+ std::is_constructible<T, std::initializer_list<U>>>>
+ void emplace(std::initializer_list<U> il) {
+ if (this->constructed()) {
+ destruct();
+ }
+ new (&get()) T(il);
+ this->setConstructed(true);
+ }
+
+ private:
+ // A helper function to convert the internal raw storage to T&
+ constexpr const T& get() const {
+ return *reinterpret_cast<const T*>(
+ reinterpret_cast<const char*>(&this->mStorage));
+ }
+
+ // Same thing, mutable
+ T& get() { return const_cast<T&>(const_cast<const Optional*>(this)->get()); }
+
+ // Shortcut for a destructor call for the stored object
+ void destruct() { get().T::~T(); }
+};
+
+template<class T>
+Optional<typename std::decay<T>::type> makeOptional(T&& t) {
+ return Optional<typename std::decay<T>::type>(std::forward<T>(t));
+}
+
+template<class T, class... Args>
+Optional<typename std::decay<T>::type> makeOptional(Args&&... args) {
+ return Optional<typename std::decay<T>::type>(kInplace,
+ std::forward<Args>(args)...);
+}
+
+template<class T>
+bool operator==(const Optional<T>& l, const Optional<T>& r) {
+ return l.hasValue() ? r.hasValue() && *l == *r : !r.hasValue();
+}
+template<class T>
+bool operator==(const Optional<T>& l, NulloptT) {
+ return !l;
+}
+template<class T>
+bool operator==(NulloptT, const Optional<T>& r) {
+ return !r;
+}
+template<class T>
+bool operator==(const Optional<T>& l, const T& r) {
+ return bool(l) && *l == r;
+}
+template<class T>
+bool operator==(const T& l, const Optional<T>& r) {
+ return bool(r) && l == *r;
+}
+
+template<class T>
+bool operator!=(const Optional<T>& l, const Optional<T>& r) {
+ return !(l == r);
+}
+template<class T>
+bool operator!=(const Optional<T>& l, NulloptT) {
+ return bool(l);
+}
+template<class T>
+bool operator!=(NulloptT, const Optional<T>& r) {
+ return bool(r);
+}
+template<class T>
+bool operator!=(const Optional<T>& l, const T& r) {
+ return !l || !(*l == r);
+}
+template<class T>
+bool operator!=(const T& l, const Optional<T>& r) {
+ return !r || !(l == *r);
+}
+
+template<class T>
+bool operator<(const Optional<T>& l, const Optional<T>& r) {
+ return !r ? false : (!l ? true : *l < *r);
+}
+template<class T>
+bool operator<(const Optional<T>&, NulloptT) {
+ return false;
+}
+template<class T>
+bool operator<(NulloptT, const Optional<T>& r) {
+ return bool(r);
+}
+template<class T>
+bool operator<(const Optional<T>& l, const T& r) {
+ return !l || *l < r;
+}
+template<class T>
+bool operator<(const T& l, const Optional<T>& r) {
+ return bool(r) && l < *r;
+}
+
+} // namespace base
+} // namespace astc_codec
+
+#endif // ASTC_CODEC_BASE_OPTIONAL_H_
diff --git a/src/base/string_utils.h b/src/base/string_utils.h
new file mode 100644
index 0000000..c450b27
--- /dev/null
+++ b/src/base/string_utils.h
@@ -0,0 +1,68 @@
+// Copyright 2018 Google LLC
+//
+// 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
+//
+// https://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 ASTC_CODEC_BASE_STRING_UTILS_H_
+#define ASTC_CODEC_BASE_STRING_UTILS_H_
+
+#include <limits>
+#include <string>
+
+namespace astc_codec {
+namespace base {
+
+// Iterates over a string's parts using |splitBy| as a delimiter.
+// |splitBy| must be a nonempty string well, or it's a no-op.
+// Otherwise, |func| is called on each of the splits, excluding the
+// characters that are part of |splitBy|. If two |splitBy|'s occur in a row,
+// |func| will be called on a StringView("") in between. See
+// StringUtils_unittest.cpp for the full story.
+template<class Func>
+void Split(const std::string& str, const std::string& splitBy, Func func) {
+ if (splitBy.empty()) {
+ return;
+ }
+
+ size_t splitSize = splitBy.size();
+ size_t begin = 0;
+ size_t end = str.find(splitBy);
+
+ while (true) {
+ func(str.substr(begin, end - begin));
+ if (end == std::string::npos) {
+ return;
+ }
+
+ begin = end + splitSize;
+ end = str.find(splitBy, begin);
+ }
+}
+
+static int32_t ParseInt32(const char* str, int32_t deflt) {
+ using std::numeric_limits;
+
+ char* error = nullptr;
+ int64_t value = strtol(str, &error, 0);
+ // Limit long values to int32 min/max. Needed for lp64; no-op on 32 bits.
+ if (value > std::numeric_limits<int32_t>::max()) {
+ value = std::numeric_limits<int32_t>::max();
+ } else if (value < std::numeric_limits<int32_t>::min()) {
+ value = std::numeric_limits<int32_t>::min();
+ }
+ return (error == str) ? deflt : static_cast<int32_t>(value);
+}
+
+} // namespace base
+} // namespace astc_codec
+
+#endif // ASTC_CODEC_BASE_STRING_UTILS_H_
diff --git a/src/base/test/bit_stream_test.cpp b/src/base/test/bit_stream_test.cpp
new file mode 100644
index 0000000..0c4b3c9
--- /dev/null
+++ b/src/base/test/bit_stream_test.cpp
@@ -0,0 +1,141 @@
+// Copyright 2018 Google LLC
+//
+// 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
+//
+// https://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 "src/base/bit_stream.h"
+
+#include <gtest/gtest.h>
+
+namespace astc_codec {
+namespace base {
+
+namespace {
+ static constexpr uint64_t kAllBits = 0xFFFFFFFFFFFFFFFF;
+ static constexpr uint64_t k40Bits = 0x000000FFFFFFFFFF;
+}
+
+TEST(BitStream, Decode) {
+ {
+ BitStream<uint64_t> stream(0, 1);
+
+ uint64_t bits = kAllBits;
+ EXPECT_TRUE(stream.GetBits(1, &bits));
+ EXPECT_EQ(bits, 0);
+ EXPECT_FALSE(stream.GetBits(1, &bits));
+ }
+
+ {
+ BitStream<uint64_t> stream(0b1010101010101010, 32);
+ EXPECT_EQ(stream.Bits(), 32);
+
+ uint64_t bits = 0;
+ EXPECT_TRUE(stream.GetBits(1, &bits));
+ EXPECT_EQ(bits, 0);
+
+ EXPECT_TRUE(stream.GetBits(3, &bits));
+ EXPECT_EQ(bits, 0b101);
+
+ EXPECT_TRUE(stream.GetBits(8, &bits));
+ EXPECT_EQ(bits, 0b10101010);
+
+ EXPECT_EQ(stream.Bits(), 20);
+
+ EXPECT_TRUE(stream.GetBits(20, &bits));
+ EXPECT_EQ(bits, 0b1010);
+ EXPECT_EQ(stream.Bits(), 0);
+ }
+
+ {
+ BitStream<uint64_t> stream(kAllBits, 64);
+ EXPECT_EQ(stream.Bits(), 64);
+
+ uint64_t bits = 0;
+ EXPECT_TRUE(stream.GetBits(64, &bits));
+ EXPECT_EQ(bits, kAllBits);
+ EXPECT_EQ(stream.Bits(), 0);
+ }
+
+ {
+ BitStream<uint64_t> stream(kAllBits, 64);
+ EXPECT_EQ(stream.Bits(), 64);
+
+ uint64_t bits = 0;
+ EXPECT_TRUE(stream.GetBits(40, &bits));
+ EXPECT_EQ(bits, k40Bits);
+ EXPECT_EQ(stream.Bits(), 24);
+ }
+
+ {
+ BitStream<uint64_t> stream(kAllBits, 32);
+
+ uint64_t bits = 0;
+ EXPECT_TRUE(stream.GetBits(0, &bits));
+ EXPECT_EQ(bits, 0);
+ EXPECT_TRUE(stream.GetBits(32, &bits));
+ EXPECT_EQ(bits, k40Bits & 0xFFFFFFFF);
+ EXPECT_TRUE(stream.GetBits(0, &bits));
+ EXPECT_EQ(bits, 0);
+ EXPECT_EQ(stream.Bits(), 0);
+ }
+}
+
+TEST(BitStream, Encode) {
+ {
+ BitStream<uint64_t> stream;
+
+ stream.PutBits(0, 1);
+ stream.PutBits(0b11, 2);
+ EXPECT_EQ(stream.Bits(), 3);
+
+ uint64_t bits = 0;
+ EXPECT_TRUE(stream.GetBits(3, &bits));
+ EXPECT_EQ(bits, 0b110);
+ }
+
+ {
+ BitStream<uint64_t> stream;
+
+ uint64_t bits = 0;
+ stream.PutBits(kAllBits, 64);
+ EXPECT_EQ(stream.Bits(), 64);
+
+ EXPECT_TRUE(stream.GetBits(64, &bits));
+ EXPECT_EQ(bits, kAllBits);
+ EXPECT_EQ(stream.Bits(), 0);
+ }
+
+ {
+ BitStream<uint64_t> stream;
+ stream.PutBits(kAllBits, 40);
+
+ uint64_t bits = 0;
+ EXPECT_TRUE(stream.GetBits(40, &bits));
+ EXPECT_EQ(bits, k40Bits);
+ EXPECT_EQ(stream.Bits(), 0);
+ }
+
+ {
+ BitStream<uint64_t> stream;
+ stream.PutBits(0, 0);
+ stream.PutBits(kAllBits, 32);
+ stream.PutBits(0, 0);
+
+ uint64_t bits = 0;
+ EXPECT_TRUE(stream.GetBits(32, &bits));
+ EXPECT_EQ(bits, k40Bits & 0xFFFFFFFF);
+ EXPECT_EQ(stream.Bits(), 0);
+ }
+}
+
+} // namespace base
+} // namespace astc_codec
diff --git a/src/base/test/bottom_n_test.cpp b/src/base/test/bottom_n_test.cpp
new file mode 100644
index 0000000..8a48d30
--- /dev/null
+++ b/src/base/test/bottom_n_test.cpp
@@ -0,0 +1,99 @@
+// Copyright 2018 Google LLC
+//
+// 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
+//
+// https://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 "src/base/bottom_n.h"
+
+#include <gmock/gmock.h>
+#include <gtest/gtest.h>
+
+namespace astc_codec {
+namespace base {
+
+using ::testing::ElementsAre;
+
+template<typename T, size_t N>
+static void pushAll(BottomN<T>& heap, const T (&arr)[N]) {
+ for (auto i : arr) {
+ heap.Push(i);
+ }
+}
+
+TEST(BottomN, Sort) {
+ {
+ BottomN<int> heap(10);
+ EXPECT_TRUE(heap.Empty());
+ pushAll(heap, {1, 2});
+
+ EXPECT_EQ(heap.Size(), 2);
+ EXPECT_FALSE(heap.Empty());
+ EXPECT_THAT(heap.Pop(), ElementsAre(1, 2));
+ }
+
+ {
+ BottomN<int> heap(6);
+ pushAll(heap, {1, 4, 3, 2, 2, 1});
+
+ EXPECT_EQ(heap.Size(), 6);
+ EXPECT_THAT(heap.Pop(), ElementsAre(1, 1, 2, 2, 3, 4));
+ }
+}
+
+TEST(BottomN, Bounds) {
+ {
+ BottomN<int> heap(4);
+ pushAll(heap, {1, 2, 3, 4});
+ EXPECT_EQ(heap.Size(), 4);
+
+ heap.Push(0);
+ EXPECT_EQ(heap.Size(), 4);
+
+ EXPECT_THAT(heap.Pop(), ElementsAre(0, 1, 2, 3));
+ }
+
+ {
+ BottomN<int> heap(4);
+ pushAll(heap, {4, 3, 2, 1});
+ EXPECT_EQ(heap.Size(), 4);
+
+ pushAll(heap, {4, 4, 4, 4});
+ EXPECT_EQ(heap.Size(), 4);
+
+ EXPECT_THAT(heap.Pop(), ElementsAre(1, 2, 3, 4));
+ }
+
+ {
+ BottomN<int> heap(4);
+ pushAll(heap, {4, 3, 2, 1});
+ EXPECT_EQ(heap.Size(), 4);
+
+ pushAll(heap, {5, 5, 5, 5});
+ EXPECT_EQ(heap.Size(), 4);
+
+ EXPECT_THAT(heap.Pop(), ElementsAre(1, 2, 3, 4));
+ }
+
+ {
+ BottomN<int> heap(4);
+ pushAll(heap, {4, 3, 2, 1});
+ EXPECT_EQ(heap.Size(), 4);
+
+ pushAll(heap, {0, 0, 0, 0});
+ EXPECT_EQ(heap.Size(), 4);
+
+ EXPECT_THAT(heap.Pop(), ElementsAre(0, 0, 0, 0));
+ }
+}
+
+} // namespace base
+} // namespace astc_codec
diff --git a/src/base/test/math_utils_test.cpp b/src/base/test/math_utils_test.cpp
new file mode 100644
index 0000000..0371e11
--- /dev/null
+++ b/src/base/test/math_utils_test.cpp
@@ -0,0 +1,78 @@
+// Copyright 2018 Google LLC
+//
+// 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
+//
+// https://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 "src/base/math_utils.h"
+
+#include <gtest/gtest.h>
+
+namespace astc_codec {
+namespace base {
+
+TEST(MathUtils, Log2Floor) {
+ EXPECT_EQ(-1, Log2Floor(0));
+
+ for (int i = 0; i < 32; i++) {
+ uint32_t n = 1U << i;
+ EXPECT_EQ(i, Log2Floor(n));
+ if (n > 2) {
+ EXPECT_EQ(i - 1, Log2Floor(n - 1));
+ EXPECT_EQ(i, Log2Floor(n + 1));
+ }
+ }
+}
+
+TEST(MathUtils, CountOnes) {
+ EXPECT_EQ(0, CountOnes(0));
+ EXPECT_EQ(1, CountOnes(1));
+ EXPECT_EQ(32, CountOnes(static_cast<uint32_t>(~0U)));
+ EXPECT_EQ(1, CountOnes(0x8000000));
+
+ for (int i = 0; i < 32; i++) {
+ EXPECT_EQ(1, CountOnes(1U << i));
+ EXPECT_EQ(31, CountOnes(static_cast<uint32_t>(~0U) ^ (1U << i)));
+ }
+}
+
+TEST(MathUtils, ReverseBits) {
+ EXPECT_EQ(ReverseBits(0u), 0u);
+ EXPECT_EQ(ReverseBits(1u), 1u << 31);
+ EXPECT_EQ(ReverseBits(0xffffffff), 0xffffffff);
+ EXPECT_EQ(ReverseBits(0x00000001), 0x80000000);
+ EXPECT_EQ(ReverseBits(0x80000000), 0x00000001);
+ EXPECT_EQ(ReverseBits(0xaaaaaaaa), 0x55555555);
+ EXPECT_EQ(ReverseBits(0x55555555), 0xaaaaaaaa);
+ EXPECT_EQ(ReverseBits(0x7d5d7f53), 0xcafebabe);
+ EXPECT_EQ(ReverseBits(0xcafebabe), 0x7d5d7f53);
+}
+
+TEST(MathUtils, GetBits) {
+ EXPECT_EQ(GetBits(0u, 0, 1), 0u);
+ EXPECT_EQ(GetBits(0u, 0, 32), 0u);
+ EXPECT_EQ(GetBits(0x00000001u, 0, 1), 0x00000001);
+ EXPECT_EQ(GetBits(0x00000001u, 0, 32), 0x00000001);
+ EXPECT_EQ(GetBits(0x00000001u, 1, 31), 0x00000000);
+ EXPECT_EQ(GetBits(0x00000001u, 31, 1), 0x00000000);
+
+ EXPECT_DEBUG_DEATH(GetBits(0x00000000u, 1, 32), "");
+ EXPECT_DEBUG_DEATH(GetBits(0x00000000u, 32, 0), "");
+ EXPECT_DEBUG_DEATH(GetBits(0x00000000u, 32, 1), "");
+
+ EXPECT_EQ(GetBits(0XFFFFFFFFu, 0, 4), 0x0000000F);
+ EXPECT_EQ(GetBits(0XFFFFFFFFu, 16, 16), 0xFFFF);
+ EXPECT_EQ(GetBits(0x80000000u, 31, 1), 1);
+ EXPECT_EQ(GetBits(0xCAFEBABEu, 24, 8), 0xCA);
+}
+
+} // namespace base
+} // namespace astc_codec
diff --git a/src/base/test/optional_test.cpp b/src/base/test/optional_test.cpp
new file mode 100644
index 0000000..1eeefbd
--- /dev/null
+++ b/src/base/test/optional_test.cpp
@@ -0,0 +1,481 @@
+// Copyright 2018 Google LLC
+//
+// 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
+//
+// https://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 "src/base/optional.h"
+
+#include <gtest/gtest.h>
+
+#include <memory>
+#include <vector>
+
+namespace astc_codec {
+namespace base {
+
+TEST(Optional, TypeProperties) {
+ // Making sure optional has the correct alignment and doesn't waste too much
+ // space
+
+ static_assert(sizeof(Optional<bool>) == 2, "bad Optional<bool> size");
+ static_assert(std::alignment_of<Optional<bool>>::value ==
+ std::alignment_of<bool>::value,
+ "bad Optional<bool> alignment");
+
+ static_assert(sizeof(Optional<char>) == 2, "bad Optional<char> size");
+ static_assert(std::alignment_of<Optional<char>>::value ==
+ std::alignment_of<char>::value,
+ "bad Optional<char> alignment");
+
+ static_assert(sizeof(Optional<int16_t>) == 4, "bad Optional<int16_t> size");
+ static_assert(std::alignment_of<Optional<int16_t>>::value ==
+ std::alignment_of<int16_t>::value,
+ "bad Optional<int16_t> alignment");
+
+ static_assert(sizeof(Optional<int32_t>) == 8, "bad Optional<int32_t> size");
+ static_assert(std::alignment_of<Optional<int32_t>>::value ==
+ std::alignment_of<int32_t>::value,
+ "bad Optional<int32_t> alignment");
+
+ static_assert(sizeof(Optional<int64_t>) == 16, "bad Optional<int64_t> size");
+ static_assert(std::alignment_of<Optional<int64_t>>::value ==
+ std::alignment_of<int64_t>::value,
+ "bad Optional<int64_t> alignment");
+
+ struct S128 {
+ int64_t data[2];
+ };
+
+ static_assert(sizeof(Optional<S128>) == 3 * sizeof(int64_t),
+ "bad Optional<S128> size");
+ static_assert(std::alignment_of<Optional<S128>>::value ==
+ std::alignment_of<S128>::value,
+ "bad Optional<S128> alignment");
+}
+
+TEST(Optional, ConstructFromValue) {
+ {
+ Optional<int> o;
+ EXPECT_FALSE(o);
+ }
+ {
+ Optional<int> o = {};
+ EXPECT_FALSE(o);
+ }
+ {
+ Optional<int> o = kNullopt;
+ EXPECT_FALSE(o);
+ }
+ {
+ Optional<int> o(1);
+ EXPECT_TRUE(o);
+ EXPECT_EQ(1, *o);
+ }
+ {
+ // check the std::decay<> constructor
+ Optional<int> o = static_cast<const short&>(1);
+ EXPECT_TRUE(o);
+ EXPECT_EQ(1, *o);
+ }
+ {
+ Optional<int> o = 1;
+ EXPECT_TRUE(o);
+ EXPECT_EQ(1, *o);
+ }
+ {
+ Optional<int> o{1};
+ EXPECT_TRUE(o);
+ EXPECT_EQ(1, *o);
+ }
+ {
+ short val = 10;
+ Optional<int> o = val;
+ EXPECT_TRUE(o);
+ EXPECT_EQ(10, *o);
+ }
+ {
+ Optional<std::vector<int>> o(kInplace, 10);
+ EXPECT_TRUE(o);
+ EXPECT_EQ((std::vector<int>(10)), *o);
+ }
+ {
+ Optional<std::vector<int>> o(kInplace, {1, 2, 3, 4});
+ EXPECT_TRUE(o);
+ EXPECT_EQ((std::vector<int>{1, 2, 3, 4}), *o);
+ }
+}
+
+TEST(Optional, ConstructFromOptional) {
+ {
+ Optional<int> o = Optional<int>();
+ EXPECT_FALSE(o);
+ }
+ {
+ Optional<short> o2;
+ Optional<int> o(o2);
+ EXPECT_FALSE(o);
+ }
+ {
+ Optional<short> o2 = 42;
+ Optional<int> o(o2);
+ EXPECT_TRUE(o);
+ EXPECT_EQ(42, *o);
+ }
+ {
+ Optional<int> o(Optional<int>(1));
+ EXPECT_TRUE(o);
+ EXPECT_EQ(1, *o);
+ }
+ {
+ Optional<int> o2 = 2;
+ Optional<int> o = o2;
+ EXPECT_TRUE(o);
+ EXPECT_EQ(2, *o);
+ }
+ {
+ Optional<std::vector<int>> o2 = std::vector<int>{20, 30, 40};
+ Optional<std::vector<int>> o = o2;
+ EXPECT_TRUE(o);
+ EXPECT_EQ((std::vector<int>{20, 30, 40}), *o);
+ }
+}
+
+TEST(Optional, Assign) {
+ {
+ Optional<int> o;
+ o = 1;
+ EXPECT_TRUE(o);
+ EXPECT_EQ(1, *o);
+
+ o = 2;
+ EXPECT_TRUE(o);
+ EXPECT_EQ(2, *o);
+
+ o = kNullopt;
+ EXPECT_FALSE(o);
+
+ o = Optional<int>(10);
+ EXPECT_TRUE(o);
+ EXPECT_EQ(10, *o);
+
+ Optional<int> o2;
+ o = o2;
+ EXPECT_FALSE(o);
+
+ o = 2u;
+ EXPECT_TRUE(o);
+ EXPECT_EQ(2, *o);
+
+ o = Optional<short>();
+ EXPECT_FALSE(o);
+
+ o = Optional<short>(20);
+ EXPECT_TRUE(o);
+ EXPECT_EQ(20, *o);
+
+ Optional<short> o3(200);
+ o = o3;
+ EXPECT_TRUE(o);
+ EXPECT_EQ(200, *o);
+
+ o = {};
+ EXPECT_FALSE(o);
+
+ // check the std::decay<> assignment
+ o = static_cast<const short&>(1);
+ EXPECT_TRUE(o);
+ EXPECT_EQ(1, *o);
+ }
+}
+
+TEST(Optional, MakeOptional) {
+ {
+ auto o = makeOptional(1);
+ static_assert(std::is_same<decltype(o), Optional<int>>::value,
+ "Bad type deduction in makeOptional()");
+ EXPECT_TRUE(o);
+ EXPECT_EQ(1, *o);
+ }
+ {
+ auto o = makeOptional(std::vector<char>{'1', '2'});
+ static_assert(std::is_same<decltype(o), Optional<std::vector<char>>>::value,
+ "Bad type deduction in makeOptional()");
+ EXPECT_TRUE(o);
+ EXPECT_EQ((std::vector<char>{'1', '2'}), *o);
+ }
+ {
+ // check std::decay<> in the factory function
+ auto o = makeOptional("String");
+ static_assert(std::is_same<decltype(o), Optional<const char*>>::value,
+ "Bad type deduction in makeOptional()");
+ EXPECT_TRUE(o);
+ EXPECT_STREQ("String", *o);
+ }
+ {
+ auto o = makeOptional<std::string>("String");
+ static_assert(std::is_same<decltype(o), Optional<std::string>>::value,
+ "Bad type deduction in makeOptional()");
+ EXPECT_TRUE(o);
+ EXPECT_STREQ("String", o->c_str());
+ }
+ {
+ auto o = makeOptional<std::string>(5, 'b');
+ static_assert(std::is_same<decltype(o), Optional<std::string>>::value,
+ "Bad type deduction in makeOptional()");
+ EXPECT_TRUE(o);
+ EXPECT_STREQ("bbbbb", o->c_str());
+ }
+ {
+ auto o = makeOptional<std::string>();
+ static_assert(std::is_same<decltype(o), Optional<std::string>>::value,
+ "Bad type deduction in makeOptional()");
+ EXPECT_TRUE(o);
+ EXPECT_STREQ("", o->c_str());
+ }
+}
+
+TEST(Optional, Move) {
+ auto o = makeOptional(std::unique_ptr<int>(new int(10)));
+ {
+ decltype(o) o2 = std::move(o);
+ EXPECT_TRUE(o);
+ EXPECT_TRUE(o2);
+ EXPECT_FALSE(bool(*o));
+ EXPECT_TRUE(bool(*o2));
+ EXPECT_EQ(10, **o2);
+
+ decltype(o) o3;
+ o3 = std::move(o2);
+ EXPECT_TRUE(o2);
+ EXPECT_TRUE(o3);
+ EXPECT_FALSE(bool(*o2));
+ EXPECT_TRUE(bool(*o3));
+ EXPECT_EQ(10, **o3);
+
+ o3 = std::move(o2);
+ EXPECT_TRUE(o2);
+ EXPECT_TRUE(o3);
+ EXPECT_FALSE(bool(*o2));
+ EXPECT_FALSE(bool(*o3));
+ }
+
+ {
+ decltype(o) o1;
+ decltype(o) o2 = std::move(o1);
+ EXPECT_FALSE(o1);
+ EXPECT_FALSE(o2);
+
+ o2 = std::move(o1);
+ EXPECT_FALSE(o1);
+ EXPECT_FALSE(o2);
+
+ decltype(o) o3{kInplace, new int(20)};
+ o3 = std::move(o1);
+ EXPECT_FALSE(o1);
+ EXPECT_FALSE(o3);
+ }
+}
+
+TEST(Optional, Value) {
+ auto o = makeOptional(1);
+ EXPECT_EQ(1, o.value());
+ EXPECT_EQ(1, o.valueOr(2));
+
+ o = kNullopt;
+ EXPECT_EQ(2, o.valueOr(2));
+}
+
+TEST(Optional, Clear) {
+ auto o = makeOptional(1);
+ o.clear();
+ EXPECT_FALSE(o);
+
+ o.clear();
+ EXPECT_FALSE(o);
+}
+
+TEST(Optional, Emplace) {
+ auto o = makeOptional(std::vector<int>{1, 2, 3, 4});
+ o.emplace(3, 1);
+ EXPECT_TRUE(o);
+ EXPECT_EQ((std::vector<int>{1, 1, 1}), *o);
+ EXPECT_EQ(3U, o->capacity());
+
+ o.clear();
+ o.emplace({1, 2});
+ EXPECT_TRUE(o);
+ EXPECT_EQ((std::vector<int>{1, 2}), *o);
+ EXPECT_EQ(2U, o->capacity());
+}
+
+TEST(Optional, Reset) {
+ auto o = makeOptional(std::vector<int>{1, 2, 3, 4});
+ o.reset(std::vector<int>{4, 3});
+ EXPECT_TRUE(o);
+ EXPECT_EQ((std::vector<int>{4, 3}), *o);
+ EXPECT_EQ(2U, o->capacity());
+
+ o.clear();
+ o.reset(std::vector<int>{1});
+ EXPECT_EQ((std::vector<int>{1}), *o);
+ EXPECT_EQ(1U, o->capacity());
+}
+
+TEST(Optional, CompareEqual) {
+ EXPECT_TRUE(makeOptional(1) == makeOptional(1));
+ EXPECT_TRUE(makeOptional(1) == 1);
+ EXPECT_TRUE(1 == makeOptional(1));
+ EXPECT_FALSE(makeOptional(1) == makeOptional(2));
+ EXPECT_FALSE(makeOptional(2) == 1);
+ EXPECT_FALSE(2 == makeOptional(1));
+ EXPECT_TRUE(makeOptional(1) != makeOptional(2));
+ EXPECT_TRUE(makeOptional(1) != 2);
+ EXPECT_TRUE(1 != makeOptional(2));
+
+ EXPECT_FALSE(makeOptional(1) == kNullopt);
+ EXPECT_FALSE(makeOptional(1) == Optional<int>());
+ EXPECT_FALSE(kNullopt == makeOptional(1));
+ EXPECT_FALSE(Optional<int>() == makeOptional(1));
+ EXPECT_TRUE(makeOptional(1) != kNullopt);
+ EXPECT_TRUE(makeOptional(1) != Optional<int>());
+ EXPECT_TRUE(kNullopt != makeOptional(1));
+ EXPECT_TRUE(Optional<int>() != makeOptional(1));
+
+ EXPECT_TRUE(kNullopt == Optional<int>());
+ EXPECT_TRUE(kNullopt == Optional<char*>());
+ EXPECT_FALSE(kNullopt != Optional<int>());
+ EXPECT_FALSE(kNullopt != Optional<char*>());
+ EXPECT_TRUE(Optional<int>() == Optional<int>());
+ EXPECT_FALSE(Optional<int>() != Optional<int>());
+}
+
+TEST(Optional, CompareLess) {
+ EXPECT_TRUE(makeOptional(1) < makeOptional(2));
+ EXPECT_TRUE(1 < makeOptional(2));
+ EXPECT_TRUE(makeOptional(1) < 2);
+
+ EXPECT_FALSE(makeOptional(1) < makeOptional(1));
+ EXPECT_FALSE(1 < makeOptional(1));
+ EXPECT_FALSE(makeOptional(1) < 1);
+ EXPECT_FALSE(makeOptional(2) < makeOptional(1));
+ EXPECT_FALSE(2 < makeOptional(1));
+ EXPECT_FALSE(makeOptional(2) < 1);
+
+ EXPECT_TRUE(kNullopt < makeOptional(2));
+ EXPECT_TRUE(Optional<int>() < makeOptional(2));
+ EXPECT_TRUE(Optional<int>() < 2);
+ EXPECT_FALSE(makeOptional(2) < kNullopt);
+ EXPECT_FALSE(makeOptional(2) < Optional<int>());
+ EXPECT_FALSE(2 < Optional<int>());
+
+ EXPECT_FALSE(kNullopt < Optional<int>());
+ EXPECT_FALSE(Optional<int>() < kNullopt);
+}
+
+TEST(Optional, Destruction) {
+ // create a reference counting class to check if we delete everything
+ // we've created
+ struct Track {
+ Track(int& val) : mVal(val) { ++mVal.get(); }
+ Track(std::initializer_list<int*> vals) : mVal(**vals.begin()) {
+ ++mVal.get();
+ }
+ Track(const Track& other) : mVal(other.mVal) { ++mVal.get(); }
+ Track(Track&& other) : mVal(other.mVal) { ++mVal.get(); }
+ Track& operator=(const Track& other) {
+ --mVal.get();
+ mVal = other.mVal;
+ ++mVal.get();
+ return *this;
+ }
+ Track& operator=(Track&& other) {
+ --mVal.get();
+ mVal = other.mVal;
+ ++mVal.get();
+ return *this;
+ }
+
+ ~Track() { --mVal.get(); }
+
+ std::reference_wrapper<int> mVal;
+ };
+
+ int counter = 0;
+ {
+ auto o = makeOptional(Track(counter));
+ EXPECT_EQ(1, counter);
+ }
+ EXPECT_EQ(0, counter);
+
+ {
+ auto o = makeOptional(Track(counter));
+ EXPECT_EQ(1, counter);
+ o.clear();
+ EXPECT_EQ(0, counter);
+ }
+ EXPECT_EQ(0, counter);
+
+ {
+ auto o = makeOptional(Track(counter));
+ EXPECT_EQ(1, counter);
+ int counter2 = 0;
+ o.emplace(counter2);
+ EXPECT_EQ(0, counter);
+ EXPECT_EQ(1, counter2);
+ o = Track(counter);
+ EXPECT_EQ(1, counter);
+ EXPECT_EQ(0, counter2);
+
+ auto o2 = o;
+ EXPECT_EQ(2, counter);
+ EXPECT_EQ(0, counter2);
+ }
+ EXPECT_EQ(0, counter);
+
+ {
+ auto o = makeOptional(Track(counter));
+ auto o2 = std::move(o);
+ EXPECT_EQ(2, counter);
+ o = o2;
+ EXPECT_EQ(2, counter);
+ }
+ EXPECT_EQ(0, counter);
+
+ int counter2 = 0;
+ {
+ Optional<Track> o;
+ o.emplace(counter);
+ EXPECT_EQ(1, counter);
+
+ o.emplace(counter2);
+ EXPECT_EQ(0, counter);
+ EXPECT_EQ(1, counter2);
+ }
+ EXPECT_EQ(0, counter);
+ EXPECT_EQ(0, counter2);
+
+ {
+ Optional<Track> o;
+ o.emplace({&counter});
+ EXPECT_EQ(1, counter);
+
+ counter2 = 0;
+ o.emplace({&counter2});
+ EXPECT_EQ(0, counter);
+ EXPECT_EQ(1, counter2);
+ }
+ EXPECT_EQ(0, counter);
+ EXPECT_EQ(0, counter2);
+}
+
+} // namespace base
+} // namespace astc_codec
diff --git a/src/base/test/string_utils_test.cpp b/src/base/test/string_utils_test.cpp
new file mode 100644
index 0000000..209da54
--- /dev/null
+++ b/src/base/test/string_utils_test.cpp
@@ -0,0 +1,110 @@
+// Copyright 2018 Google LLC
+//
+// 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
+//
+// https://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 "src/base/string_utils.h"
+
+#include <gtest/gtest.h>
+
+#include <list>
+#include <string>
+#include <vector>
+
+namespace astc_codec {
+namespace base {
+
+TEST(StringUtils, Split) {
+ std::vector<std::string> results;
+
+ auto testFunc = [&results](std::string&& s) {
+ results.push_back(std::move(s));
+ };
+
+ Split("", "abc", testFunc);
+ EXPECT_EQ(results.size(), 1);
+
+ Split("abc", "", testFunc);
+ EXPECT_EQ(results.size(), 1);
+
+ results.clear();
+ Split("abc", "a", testFunc);
+ EXPECT_EQ(results.size(), 2);
+ EXPECT_EQ(results[0], "");
+ EXPECT_EQ(results[1], "bc");
+
+ results.clear();
+ Split("aaa", "a", testFunc);
+ EXPECT_EQ(4, results.size());
+ EXPECT_EQ("", results[0]);
+ EXPECT_EQ("", results[1]);
+ EXPECT_EQ("", results[2]);
+ EXPECT_EQ("", results[3]);
+
+ results.clear();
+ Split("1a2a3a4", "a", testFunc);
+ EXPECT_EQ(4, results.size());
+ EXPECT_EQ("1", results[0]);
+ EXPECT_EQ("2", results[1]);
+ EXPECT_EQ("3", results[2]);
+ EXPECT_EQ("4", results[3]);
+
+ results.clear();
+ Split("1a2aa3a4", "a", testFunc);
+ EXPECT_EQ(5, results.size());
+ EXPECT_EQ("1", results[0]);
+ EXPECT_EQ("2", results[1]);
+ EXPECT_EQ("", results[2]);
+ EXPECT_EQ("3", results[3]);
+ EXPECT_EQ("4", results[4]);
+
+ results.clear();
+ Split("The quick brown fox jumped over the lazy dog",
+ " ", testFunc);
+ EXPECT_EQ(9, results.size());
+ EXPECT_EQ("The", results[0]);
+ EXPECT_EQ("quick", results[1]);
+ EXPECT_EQ("brown", results[2]);
+ EXPECT_EQ("fox", results[3]);
+ EXPECT_EQ("jumped", results[4]);
+ EXPECT_EQ("over", results[5]);
+ EXPECT_EQ("the", results[6]);
+ EXPECT_EQ("lazy", results[7]);
+ EXPECT_EQ("dog", results[8]);
+
+ results.clear();
+ Split("a; b; c; d", "; ", testFunc);
+ EXPECT_EQ(4, results.size());
+ EXPECT_EQ("a", results[0]);
+ EXPECT_EQ("b", results[1]);
+ EXPECT_EQ("c", results[2]);
+ EXPECT_EQ("d", results[3]);
+}
+
+TEST(StringUtils, ParseInt32) {
+ EXPECT_EQ(ParseInt32("0", -1), 0);
+ EXPECT_EQ(ParseInt32("100", -1), 100);
+ EXPECT_EQ(ParseInt32("-100", -1), -100);
+
+ EXPECT_EQ(ParseInt32("", -1), -1);
+ EXPECT_EQ(ParseInt32("a", -1), -1);
+ EXPECT_EQ(ParseInt32("10x1", -1), 10);
+
+ EXPECT_EQ(ParseInt32("2147483647", -1), 2147483647);
+ EXPECT_EQ(ParseInt32("2147483648", -1), 2147483647);
+
+ EXPECT_EQ(ParseInt32("-2147483648", -1), -2147483648);
+ EXPECT_EQ(ParseInt32("-2147483649", -1), -2147483648);
+}
+
+} // namespace base
+} // namespace astc_codec
diff --git a/src/base/test/type_traits_test.cpp b/src/base/test/type_traits_test.cpp
new file mode 100644
index 0000000..b858c01
--- /dev/null
+++ b/src/base/test/type_traits_test.cpp
@@ -0,0 +1,128 @@
+// Copyright 2018 Google LLC
+//
+// 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
+//
+// https://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 "src/base/type_traits.h"
+
+#include <gtest/gtest.h>
+
+#include <array>
+#include <functional>
+#include <list>
+#include <vector>
+
+namespace astc_codec {
+namespace base {
+
+TEST(TypeTraits, IsCallable) {
+ class C;
+ C* c = nullptr;
+
+ auto lambda = [c](bool) -> C* { return nullptr; };
+
+ static_assert(is_callable_as<void(), void()>::value, "simple function");
+ static_assert(is_callable_as<void (&)(), void()>::value,
+ "function reference");
+ static_assert(is_callable_as<void (*)(), void()>::value, "function pointer");
+ static_assert(is_callable_as<int(C&, C*), int(C&, C*)>::value,
+ "function with arguments and return type");
+ static_assert(is_callable_as<decltype(lambda), C*(bool)>::value, "lambda");
+ static_assert(is_callable_as<std::function<bool(int)>, bool(int)>::value,
+ "std::function");
+
+ static_assert(!is_callable_as<int, void()>::value,
+ "int should not be callable");
+ static_assert(!is_callable_as<C, void()>::value, "incomplete type");
+ static_assert(!is_callable_as<void(), void(int)>::value,
+ "different arguments");
+ static_assert(!is_callable_as<int(), void()>::value,
+ "different return types");
+ static_assert(!is_callable_as<int(), short()>::value,
+ "slightly different return types");
+ static_assert(!is_callable_as<int(int), int(int, int)>::value,
+ "more arguments");
+ static_assert(!is_callable_as<int(int, int), int(int)>::value,
+ "less arguments");
+
+ static_assert(!is_callable_as<int(int), int>::value,
+ "bad required signature");
+
+ static_assert(is_callable_with_args<void(), void()>::value,
+ "simple function");
+ static_assert(is_callable_with_args<void (&)(), void()>::value,
+ "function reference");
+ static_assert(is_callable_with_args<void (*)(), void()>::value,
+ "function pointer");
+ static_assert(is_callable_with_args<int(C&, C*), int(C&, C*)>::value,
+ "function with arguments and return type");
+ static_assert(is_callable_with_args<decltype(lambda), C*(bool)>::value,
+ "lambda");
+ static_assert(
+ is_callable_with_args<std::function<bool(int)>, bool(int)>::value,
+ "std::function");
+
+ static_assert(!is_callable_with_args<int, void()>::value,
+ "int should not be callable");
+ static_assert(!is_callable_with_args<C, void()>::value, "incomplete type");
+ static_assert(!is_callable_with_args<void(), void(int)>::value,
+ "different arguments");
+ static_assert(is_callable_with_args<int(), void()>::value,
+ "different return types are ignored");
+ static_assert(is_callable_with_args<int(), short()>::value,
+ "slightly different return types are ignored");
+ static_assert(!is_callable_with_args<int(int), int(int, int)>::value,
+ "more arguments");
+ static_assert(!is_callable_with_args<int(int, int), int(int)>::value,
+ "less arguments");
+
+ static_assert(!is_callable_with_args<int(int), int>::value,
+ "bad required signature");
+}
+
+TEST(TypeTraits, IsTemplateInstantiation) {
+ static_assert(!is_template_instantiation_of<int, std::vector>::value,
+ "int is not an instance of vector");
+ static_assert(!is_template_instantiation_of<std::list<std::vector<int>>,
+ std::vector>::value,
+ "list is not an instance of vector");
+
+ static_assert(
+ is_template_instantiation_of<std::vector<int>, std::vector>::value,
+ "std::vector<int> is an instance of vector");
+ static_assert(
+ is_template_instantiation_of<std::vector<std::vector<std::vector<int>>>,
+ std::vector>::value,
+ "nested std::vector<> is an instance of vector");
+}
+
+TEST(TypeTraits, IsRange) {
+ static_assert(is_range<std::vector<int>>::value,
+ "vector<> should be detected as a range");
+ static_assert(is_range<const std::list<std::function<void()>>>::value,
+ "const list<> should be detected as a range");
+ static_assert(is_range<std::array<std::vector<int>, 10>>::value,
+ "array<> should be detected as a range");
+ char arr[100];
+ static_assert(is_range<decltype(arr)>::value,
+ "C array should be detected as a range");
+ static_assert(is_range<decltype("string")>::value,
+ "String literal should be detected as a range");
+
+ static_assert(!is_range<int>::value, "int shouldn't be a range");
+ static_assert(!is_range<int*>::value, "int* shouldn't be a range");
+ static_assert(!is_range<const int*>::value,
+ "even const int* shouldn't be a range");
+}
+
+} // namespace base
+} // namespace astc_codec
diff --git a/src/base/test/uint128_test.cpp b/src/base/test/uint128_test.cpp
new file mode 100644
index 0000000..0a52244
--- /dev/null
+++ b/src/base/test/uint128_test.cpp
@@ -0,0 +1,140 @@
+// Copyright 2018 Google LLC
+//
+// 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
+//
+// https://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 "src/base/uint128.h"
+
+#include <gtest/gtest.h>
+
+namespace astc_codec {
+namespace base {
+
+TEST(UInt128, Equality) {
+ const UInt128 zero(0);
+ const UInt128 max64(~0ULL);
+
+ EXPECT_EQ(zero, zero);
+ EXPECT_NE(zero, max64);
+ EXPECT_EQ(zero, UInt128(0));
+ EXPECT_NE(zero, UInt128(1));
+ EXPECT_EQ(max64, max64);
+}
+
+TEST(UInt128, Shifting) {
+ const UInt128 max64(~0ULL);
+ const UInt128 upper64(~0ULL, 0);
+ EXPECT_EQ(upper64.HighBits(), ~0ULL);
+ EXPECT_EQ(upper64.LowBits(), 0);
+
+ EXPECT_EQ(upper64 >> 64, max64);
+
+ EXPECT_EQ(UInt128(1) << 1, UInt128(2));
+ EXPECT_EQ(UInt128(0) << 0, UInt128(0));
+ EXPECT_EQ(max64 << 0, max64);
+ EXPECT_EQ(max64 >> 0, max64);
+ EXPECT_EQ(upper64 << 0, upper64);
+ EXPECT_EQ(upper64 >> 0, upper64);
+
+ {
+ const UInt128 bit63 = UInt128(1ULL << 62) << 1;
+ EXPECT_EQ(bit63.LowBits(), 1ULL << 63);
+ EXPECT_EQ(bit63.HighBits(), 0);
+ }
+
+ {
+ const UInt128 bit64 = UInt128(1ULL << 63) << 1;
+ EXPECT_EQ(bit64.LowBits(), 0);
+ EXPECT_EQ(bit64.HighBits(), 1);
+ EXPECT_EQ(bit64 >> 1, UInt128(1ULL << 63));
+ }
+
+ {
+ const UInt128 overshift = max64 << 128;
+ EXPECT_EQ(overshift.HighBits(), 0);
+ EXPECT_EQ(overshift.LowBits(), 0);
+ }
+
+ {
+ const UInt128 overlap = upper64 >> 32;
+ EXPECT_EQ(overlap.HighBits(), 0x00000000FFFFFFFF);
+ EXPECT_EQ(overlap.LowBits(), 0xFFFFFFFF00000000);
+ }
+
+ {
+ const UInt128 overlap = max64 << 32;
+ EXPECT_EQ(overlap.HighBits(), 0x00000000FFFFFFFF);
+ EXPECT_EQ(overlap.LowBits(), 0xFFFFFFFF00000000);
+ }
+}
+
+TEST(UInt128, LargeShift) {
+ const UInt128 base(0xFF);
+ EXPECT_EQ(base << 64, UInt128(0xFFULL, 0));
+ EXPECT_EQ(base << 72, UInt128(0xFF00ULL, 0));
+ EXPECT_EQ(base << 80, UInt128(0xFF0000ULL, 0));
+ EXPECT_EQ(base << 88, UInt128(0xFF000000ULL, 0));
+ EXPECT_EQ(base << 96, UInt128(0xFF00000000ULL, 0));
+ EXPECT_EQ(base << 104, UInt128(0xFF0000000000ULL, 0));
+ EXPECT_EQ(base << 112, UInt128(0xFF000000000000ULL, 0));
+ EXPECT_EQ(base << 120, UInt128(0xFF00000000000000ULL, 0));
+
+ const UInt128 upper(0xFF00000000000000ULL, 0);
+ EXPECT_EQ(upper >> 64, UInt128(0, 0xFF00000000000000ULL));
+ EXPECT_EQ(upper >> 72, UInt128(0, 0xFF000000000000ULL));
+ EXPECT_EQ(upper >> 80, UInt128(0, 0xFF0000000000ULL));
+ EXPECT_EQ(upper >> 88, UInt128(0, 0xFF00000000ULL));
+ EXPECT_EQ(upper >> 96, UInt128(0, 0xFF000000ULL));
+ EXPECT_EQ(upper >> 104, UInt128(0, 0xFF0000ULL));
+ EXPECT_EQ(upper >> 112, UInt128(0, 0xFF00ULL));
+ EXPECT_EQ(upper >> 120, UInt128(0, 0xFFULL));
+}
+
+TEST(UInt128, BooleanOperators) {
+ const UInt128 allOnes(~0ULL, ~0ULL);
+ EXPECT_EQ(allOnes.HighBits(), ~0ULL);
+ EXPECT_EQ(allOnes.LowBits(), ~0ULL);
+
+ EXPECT_EQ(~allOnes, UInt128(0));
+ EXPECT_EQ(~UInt128(0), allOnes);
+
+ EXPECT_EQ(UInt128(0xFFFF00) & UInt128(0x00FFFF), UInt128(0x00FF00));
+ EXPECT_EQ(UInt128(0xFFFF00) | UInt128(0x00FFFF), UInt128(0xFFFFFF));
+ EXPECT_EQ(UInt128(0xFFFF00) ^ UInt128(0x00FFFF), UInt128(0xFF00FF));
+}
+
+TEST(UInt128, Addition) {
+ const UInt128 bit63(1ULL << 63);
+
+ EXPECT_EQ(UInt128(1) + 1, UInt128(2));
+ EXPECT_EQ(bit63 + bit63, UInt128(1) << 64);
+
+ const UInt128 carryUp = UInt128(~0ULL) + 1;
+ EXPECT_EQ(carryUp.HighBits(), 1);
+ EXPECT_EQ(carryUp.LowBits(), 0);
+
+ const UInt128 allOnes(~0ULL, ~0ULL);
+ EXPECT_EQ(allOnes + 1, UInt128(0));
+}
+
+TEST(UInt128, Subtraction) {
+ const UInt128 bit64 = UInt128(1) << 64;
+ EXPECT_EQ(bit64 - 1, UInt128(~0ULL));
+
+ EXPECT_EQ(UInt128(1) - 1, UInt128(0));
+
+ const UInt128 allOnes(~0ULL, ~0ULL);
+ EXPECT_EQ(UInt128(0) - 1, allOnes);
+}
+
+} // namespace base
+} // namespace astc_codec
diff --git a/src/base/type_traits.h b/src/base/type_traits.h
new file mode 100644
index 0000000..917125d
--- /dev/null
+++ b/src/base/type_traits.h
@@ -0,0 +1,172 @@
+// Copyright 2018 Google LLC
+//
+// 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
+//
+// https://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 ASTC_CODEC_BASE_TYPE_TRAITS_H_
+#define ASTC_CODEC_BASE_TYPE_TRAITS_H_
+
+#include <iterator>
+#include <type_traits>
+
+namespace astc_codec {
+namespace base {
+
+namespace details {
+
+// a simple helper class for SFINAE below.
+template<class X = void>
+struct dummy {
+ using type = X;
+};
+
+} // namespace details
+
+// add some convenience shortcuts for an overly complex std::enable_if syntax
+
+// Use 'enable_if<Predicate,Type>' instead of
+// 'typename std::enable_if<Predicate::value,Type>::type'
+template<class Predicate, class Type = void*>
+using enable_if = typename std::enable_if<Predicate::value, Type>::type;
+
+// Use 'enable_if_c<BooleanFlag,Type>' instead of
+// 'typename std::enable_if<BooleanFlag,Type>::type'
+template<bool predicate, class Type = void*>
+using enable_if_c = typename std::enable_if<predicate, Type>::type;
+
+// Use 'enable_if_convertible<From,To,Type>' instead of
+// 'typename std::enable_if<std::is_convertible<From,To>::value, Type>::type'
+template<class From, class To, class Type = void*>
+using enable_if_convertible = enable_if<std::is_convertible<From, To>>;
+
+// -----------------------------------------------------------------------------
+// A predicate for checking if some object is callable with a specific
+// signature. Examples:
+//
+// is_callable_as<int, void()>::value == false.
+// is_callable_as<strcmp, void()>::value == false.
+// is_callable_as<strcmp, int(const char*, const char*)>::value == true
+//
+template<class F, class Signature, class X = void>
+struct is_callable_as : std::false_type {};
+
+// This specialization is SFINAE-d out if template arguments can't be combined
+// into a call expression F(), or if the result of that call is not |R|
+template<class F, class R, class... Args>
+struct is_callable_as<F, R(Args...),
+ typename std::enable_if<std::is_same<
+ typename details::dummy<decltype(std::declval<F>()(
+ std::declval<Args>()...))>::type,
+ R>::value>::type> : std::true_type {};
+
+//
+// A similar predicate to only check arguments of the function call and ignore
+// the specified return type
+//
+// is_callable_as<strcmp, int(const char*, const char*)>::value == true
+// is_callable_as<strcmp, void(const char*, const char*)>::value == false
+// is_callable_with_args<strcmp, void(const char*, const char*)>::value == true
+//
+template<class F, class Signature, class X = void>
+struct is_callable_with_args : std::false_type {};
+
+template<class F, class R, class... Args>
+struct is_callable_with_args<
+ F, R(Args...),
+ typename std::enable_if<
+ !std::is_same<typename details::dummy<decltype(
+ std::declval<F>()(std::declval<Args>()...))>::type,
+ F>::value>::type> : std::true_type {};
+
+// -----------------------------------------------------------------------------
+// Check if a type |T| is any instantiation of a template |U|. Examples:
+//
+// is_template_instantiation_of<int, std::vector>::value == false
+// is_template_instantiation_of<
+// std::list<std::vector<int>>, std::vector>::value == false
+// is_template_instantiation_of<std::vector<int>, std::vector>::value == true
+// is_template_instantiation_of<
+// std::vector<std::vector<int>>, std::vector>::value == true
+//
+template<class T, template<class...> class U>
+struct is_template_instantiation_of : std::false_type {};
+
+template<template<class...> class U, class... Args>
+struct is_template_instantiation_of<U<Args...>, U> : std::true_type {};
+// -----------------------------------------------------------------------------
+
+//
+// is_range<T> - check if type |T| is a range-like type.
+//
+// It makes sure that expressions std::begin(t) and std::end(t) are well-formed
+// and those return the same type.
+//
+// Note: with expression SFINAE from C++14 is_range_helper<> could be renamed to
+// is_range<> with no extra code. C++11 needs an extra level of enable_if<>
+// to make it work when the type isn't a range.
+//
+
+namespace details {
+
+template<class T>
+using is_range_helper = std::is_same<
+ decltype(std::begin(
+ std::declval<typename std::add_lvalue_reference<T>::type>())),
+ decltype(
+ std::end(std::declval<typename std::add_lvalue_reference<T>::type>()))>;
+
+} // namespace details
+
+template<class T, class = void>
+struct is_range : std::false_type {};
+
+template<class T>
+struct is_range<
+ T, typename std::enable_if<details::is_range_helper<T>::value>::type>
+ : std::true_type {};
+
+////////////////////////////////////////////////////////////////////////////////
+//
+// A class to incapsulate integer sequence 0, 1, ..., <num_args>
+// Seq<int...>
+// Useful to pass function parameters in an array/tuple to call it later.
+//
+
+template<int...>
+struct Seq {};
+
+// A 'maker' class to construct Seq<int...> given only <num_args>
+// value.
+// MakeSeq<N, S...> works this way, e.g.
+//
+// MakeSeq<2> inherits MakeSeq<2 - 1, 2 - 1> == MakeSeq<1, 1>
+// MakeSeq<1, 1> : MakeSeq<1 - 1, 1 - 1, 1> == MakeSeq<0, 0, 1>
+// MakeSeq<0, 0, 1> == MakeSeq<0, S...> and defines |type| = Seq<0, 1>
+
+template<int N, int... S>
+struct MakeSeq : MakeSeq<N - 1, N - 1, S...> {};
+
+template<int... S>
+struct MakeSeq<0, S...> {
+ using type = Seq<S...>;
+};
+
+//
+// MakeSeqT alias to quickly create Seq<...>:
+// MakeSeqT<3> == Seq<0, 1, 2>
+template<int... S>
+using MakeSeqT = typename MakeSeq<S...>::type;
+
+} // namespace base
+} // namespace astc_codec
+
+#endif // ASTC_CODEC_BASE_TYPE_TRAITS_H_
diff --git a/src/base/uint128.h b/src/base/uint128.h
new file mode 100644
index 0000000..481e4ea
--- /dev/null
+++ b/src/base/uint128.h
@@ -0,0 +1,175 @@
+// Copyright 2018 Google LLC
+//
+// 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
+//
+// https://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 ASTC_CODEC_BASE_UINT128_H_
+#define ASTC_CODEC_BASE_UINT128_H_
+
+#include <cassert>
+#include <cstdint>
+
+namespace astc_codec {
+namespace base {
+
+class UInt128 {
+ public:
+ UInt128() = default;
+ UInt128(uint64_t low) : low_(low) { }
+ UInt128(uint64_t high, uint64_t low) : low_(low), high_(high) { }
+ UInt128(const UInt128& other) : low_(other.low_), high_(other.high_) { }
+
+ uint64_t LowBits() const { return low_; }
+ uint64_t HighBits() const { return high_; }
+
+ // Allow explicit casts to uint64_t.
+ explicit operator uint64_t() const { return low_; }
+
+ // Copy operators.
+ UInt128& operator=(const UInt128& other) {
+ high_ = other.high_;
+ low_ = other.low_;
+ return *this;
+ }
+
+ // Equality operators.
+ bool operator==(const UInt128& other) const {
+ return high_ == other.high_ && low_ == other.low_;
+ }
+
+ bool operator!=(const UInt128& other) const {
+ return high_ != other.high_ || low_ != other.low_;
+ }
+
+ // Shifting.
+ UInt128& operator<<=(int shift) {
+ high_ = shift >= 64 ? (shift >= 128 ? 0 : low_ << (shift - 64))
+ : high_ << shift;
+
+ if (shift > 0 && shift < 64) {
+ const uint64_t overlappingBits = low_ >> (64 - shift);
+ high_ |= overlappingBits;
+ }
+
+ low_ = shift >= 64 ? 0 : low_ << shift;
+ return *this;
+ }
+
+ UInt128 operator<<(int shift) const {
+ UInt128 result = *this;
+ result <<= shift;
+ return result;
+ }
+
+ UInt128& operator>>=(int shift) {
+ low_ = shift >= 64 ? (shift >= 128 ? 0 : high_ >> (shift - 64))
+ : low_ >> shift;
+
+ if (shift > 0 && shift < 64) {
+ const uint64_t overlappingBits = high_ << (64 - shift);
+ low_ |= overlappingBits;
+ }
+
+ high_ = shift >= 64 ? 0 : high_ >> shift;
+
+ return *this;
+ }
+
+ UInt128 operator>>(int shift) const {
+ UInt128 result = *this;
+ result >>= shift;
+ return result;
+ }
+
+ // Binary operations.
+ UInt128& operator|=(const UInt128& other) {
+ high_ |= other.high_;
+ low_ |= other.low_;
+ return *this;
+ }
+
+ UInt128 operator|(const UInt128& other) const {
+ UInt128 result = *this;
+ result |= other;
+ return result;
+ }
+
+ UInt128& operator&=(const UInt128& other) {
+ high_ &= other.high_;
+ low_ &= other.low_;
+ return *this;
+ }
+
+ UInt128 operator&(const UInt128& other) const {
+ UInt128 result = *this;
+ result &= other;
+ return result;
+ }
+
+ UInt128& operator^=(const UInt128& other) {
+ high_ ^= other.high_;
+ low_ ^= other.low_;
+ return *this;
+ }
+
+ UInt128 operator^(const UInt128& other) const {
+ UInt128 result = *this;
+ result ^= other;
+ return result;
+ }
+
+ UInt128 operator~() const {
+ UInt128 result = *this;
+ result.high_ = ~high_;
+ result.low_ = ~low_;
+ return result;
+ }
+
+ // Addition/subtraction.
+ UInt128& operator+=(const UInt128& other) {
+ const uint64_t carry =
+ (((low_ & other.low_) & 1) + (low_ >> 1) + (other.low_ >> 1)) >> 63;
+ high_ += other.high_ + carry;
+ low_ += other.low_;
+ return *this;
+ }
+
+ UInt128 operator+(const UInt128& other) const {
+ UInt128 result = *this;
+ result += other;
+ return result;
+ }
+
+ UInt128& operator-=(const UInt128& other) {
+ low_ -= other.low_;
+ const uint64_t carry =
+ (((low_ & other.low_) & 1) + (low_ >> 1) + (other.low_ >> 1)) >> 63;
+ high_ -= other.high_ + carry;
+ return *this;
+ }
+
+ UInt128 operator-(const UInt128& other) const {
+ UInt128 result = *this;
+ result -= other;
+ return result;
+ }
+
+ private:
+ // TODO(google): Different order for little endian.
+ uint64_t low_ = 0;
+ uint64_t high_ = 0;
+};
+
+} // namespace base
+} // namespace astc_codec
+
+#endif // ASTC_CODEC_BASE_UINT128_H_
generated by cgit v1.2.3 (git 2.39.1) at 2024-05-18 11:28:33 +0000