diff options
Diffstat (limited to 'extern/draco/dracoenc/src/draco/core')
41 files changed, 3274 insertions, 0 deletions
diff --git a/extern/draco/dracoenc/src/draco/core/bit_utils.cc b/extern/draco/dracoenc/src/draco/core/bit_utils.cc new file mode 100644 index 00000000000..37119a7171b --- /dev/null +++ b/extern/draco/dracoenc/src/draco/core/bit_utils.cc @@ -0,0 +1,36 @@ +// Copyright 2017 The Draco Authors. +// +// 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 "draco/core/bit_utils.h" + +namespace draco { + +void ConvertSignedIntsToSymbols(const int32_t *in, int in_values, + uint32_t *out) { + // Convert the quantized values into a format more suitable for entropy + // encoding. + // Put the sign bit into LSB pos and shift the rest one bit left. + for (int i = 0; i < in_values; ++i) { + out[i] = ConvertSignedIntToSymbol(in[i]); + } +} + +void ConvertSymbolsToSignedInts(const uint32_t *in, int in_values, + int32_t *out) { + for (int i = 0; i < in_values; ++i) { + out[i] = ConvertSymbolToSignedInt(in[i]); + } +} + +} // namespace draco diff --git a/extern/draco/dracoenc/src/draco/core/bit_utils.h b/extern/draco/dracoenc/src/draco/core/bit_utils.h new file mode 100644 index 00000000000..f63cd0750c9 --- /dev/null +++ b/extern/draco/dracoenc/src/draco/core/bit_utils.h @@ -0,0 +1,123 @@ +// Copyright 2016 The Draco Authors. +// +// 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. +// +// File containing a basic set of bit manipulation utilities used within the +// Draco library. + +#ifndef DRACO_CORE_BIT_UTILS_H_ +#define DRACO_CORE_BIT_UTILS_H_ + +#include <inttypes.h> +#include <stdint.h> +#include <type_traits> + +#if defined(_MSC_VER) +#include <intrin.h> +#endif // defined(_MSC_VER) + +namespace draco { + +// Returns the number of '1' bits within the input 32 bit integer. +inline int CountOneBits32(uint32_t n) { + n -= ((n >> 1) & 0x55555555); + n = ((n >> 2) & 0x33333333) + (n & 0x33333333); + return (((n + (n >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24; +} + +inline uint32_t ReverseBits32(uint32_t n) { + n = ((n >> 1) & 0x55555555) | ((n & 0x55555555) << 1); + n = ((n >> 2) & 0x33333333) | ((n & 0x33333333) << 2); + n = ((n >> 4) & 0x0F0F0F0F) | ((n & 0x0F0F0F0F) << 4); + n = ((n >> 8) & 0x00FF00FF) | ((n & 0x00FF00FF) << 8); + return (n >> 16) | (n << 16); +} + +// Copies the |nbits| from the src integer into the |dst| integer using the +// provided bit offsets |dst_offset| and |src_offset|. +inline void CopyBits32(uint32_t *dst, int dst_offset, uint32_t src, + int src_offset, int nbits) { + const uint32_t mask = (~static_cast<uint32_t>(0)) >> (32 - nbits) + << dst_offset; + *dst = (*dst & (~mask)) | (((src >> src_offset) << dst_offset) & mask); +} + +// Returns the location of the most significant bit in the input integer |n|. +// The functionality is not defined for |n == 0|. +inline int MostSignificantBit(uint32_t n) { +#if defined(__GNUC__) + return 31 ^ __builtin_clz(n); +#elif defined(_MSC_VER) + + unsigned long where; + _BitScanReverse(&where, n); + return (int)where; +#else + // TODO(fgalligan): Optimize this code. + int msb = -1; + while (n != 0) { + msb++; + n >>= 1; + } + return msb; +#endif +} + +// Helper function that converts signed integer values into unsigned integer +// symbols that can be encoded using an entropy encoder. +void ConvertSignedIntsToSymbols(const int32_t *in, int in_values, + uint32_t *out); + +// Converts unsigned integer symbols encoded with an entropy encoder back to +// signed values. +void ConvertSymbolsToSignedInts(const uint32_t *in, int in_values, + int32_t *out); + +// Helper function that converts a single signed integer value into an unsigned +// integer symbol that can be encoded using an entropy encoder. +template <class IntTypeT> +typename std::make_unsigned<IntTypeT>::type ConvertSignedIntToSymbol( + IntTypeT val) { + typedef typename std::make_unsigned<IntTypeT>::type UnsignedType; + static_assert(std::is_integral<IntTypeT>::value, "IntTypeT is not integral."); + // Early exit if val is positive. + if (val >= 0) { + return static_cast<UnsignedType>(val) << 1; + } + val = -(val + 1); // Map -1 to 0, -2 to -1, etc.. + UnsignedType ret = static_cast<UnsignedType>(val); + ret <<= 1; + ret |= 1; + return ret; +} + +// Converts a single unsigned integer symbol encoded with an entropy encoder +// back to a signed value. +template <class IntTypeT> +typename std::make_signed<IntTypeT>::type ConvertSymbolToSignedInt( + IntTypeT val) { + static_assert(std::is_integral<IntTypeT>::value, "IntTypeT is not integral."); + typedef typename std::make_signed<IntTypeT>::type SignedType; + const bool is_positive = !static_cast<bool>(val & 1); + val >>= 1; + if (is_positive) { + return static_cast<SignedType>(val); + } + SignedType ret = static_cast<SignedType>(val); + ret = -ret - 1; + return ret; +} + +} // namespace draco + +#endif // DRACO_CORE_BIT_UTILS_H_ diff --git a/extern/draco/dracoenc/src/draco/core/bounding_box.cc b/extern/draco/dracoenc/src/draco/core/bounding_box.cc new file mode 100644 index 00000000000..d95b1e90759 --- /dev/null +++ b/extern/draco/dracoenc/src/draco/core/bounding_box.cc @@ -0,0 +1,23 @@ +// Copyright 2018 The Draco Authors. +// +// 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 "draco/core/bounding_box.h" + +namespace draco { + +BoundingBox::BoundingBox(const Vector3f &min_point_in, + const Vector3f &max_point_in) + : min_point_(min_point_in), max_point_(max_point_in) {} + +} // namespace draco diff --git a/extern/draco/dracoenc/src/draco/core/bounding_box.h b/extern/draco/dracoenc/src/draco/core/bounding_box.h new file mode 100644 index 00000000000..0259267c99c --- /dev/null +++ b/extern/draco/dracoenc/src/draco/core/bounding_box.h @@ -0,0 +1,52 @@ +// Copyright 2018 The Draco Authors. +// +// 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 DRACO_CORE_BOUNDING_BOX_H_ +#define DRACO_CORE_BOUNDING_BOX_H_ + +#include "draco/core/vector_d.h" + +namespace draco { + +// Class for detecting the bounding box of a point_cloud or mesh. +// Use the minimum point and the maximum point to define the bounding box. +// TODO(xiaoxumeng): Change the class of BoundingBox to a template, similar to +// draco/src/draco/core/vector_d.h +class BoundingBox { + public: + // Initialization + BoundingBox(const Vector3f &min_point_in, const Vector3f &max_point_in); + + inline const Vector3f &min_point() const { return min_point_; } + inline const Vector3f &max_point() const { return max_point_; } + + // Conditionally updates the bounding box. + // TODO(xiaoxumeng): Change the function to a template function and change the + // argument to an iterator. + inline void update_bounding_box(const Vector3f &new_point) { + for (int i = 0; i < 3; i++) { + if (new_point[i] < min_point_[i]) + min_point_[i] = new_point[i]; + if (new_point[i] > max_point_[i]) + max_point_[i] = new_point[i]; + } + } + + private: + Vector3f min_point_; + Vector3f max_point_; +}; +} // namespace draco + +#endif // DRACO_CORE_BOUNDING_BOX_H_ diff --git a/extern/draco/dracoenc/src/draco/core/buffer_bit_coding_test.cc b/extern/draco/dracoenc/src/draco/core/buffer_bit_coding_test.cc new file mode 100644 index 00000000000..e761284e236 --- /dev/null +++ b/extern/draco/dracoenc/src/draco/core/buffer_bit_coding_test.cc @@ -0,0 +1,116 @@ +// Copyright 2016 The Draco Authors. +// +// 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 "draco/core/decoder_buffer.h" +#include "draco/core/encoder_buffer.h" + +#include "draco/core/draco_test_base.h" + +namespace draco { + +class BufferBitCodingTest : public ::testing::Test { + public: + typedef DecoderBuffer::BitDecoder BitDecoder; + typedef EncoderBuffer::BitEncoder BitEncoder; +}; + +TEST_F(BufferBitCodingTest, TestBitCodersByteAligned) { + constexpr int buffer_size = 32; + char buffer[buffer_size]; + BitEncoder encoder(buffer); + const uint8_t data[] = {0x76, 0x54, 0x32, 0x10, 0x76, 0x54, 0x32, 0x10}; + const int bytes_to_encode = sizeof(data); + + for (int i = 0; i < bytes_to_encode; ++i) { + encoder.PutBits(data[i], sizeof(data[i]) * 8); + ASSERT_EQ((i + 1) * sizeof(data[i]) * 8, encoder.Bits()); + } + + BitDecoder decoder; + decoder.reset(static_cast<const void *>(buffer), bytes_to_encode); + for (int i = 0; i < bytes_to_encode; ++i) { + uint32_t x = 0; + ASSERT_TRUE(decoder.GetBits(8, &x)); + ASSERT_EQ(x, data[i]); + } + + ASSERT_EQ(bytes_to_encode * 8u, decoder.BitsDecoded()); +} + +TEST_F(BufferBitCodingTest, TestBitCodersNonByte) { + constexpr int buffer_size = 32; + char buffer[buffer_size]; + BitEncoder encoder(buffer); + const uint8_t data[] = {0x76, 0x54, 0x32, 0x10, 0x76, 0x54, 0x32, 0x10}; + const uint32_t bits_to_encode = 51; + const int bytes_to_encode = (bits_to_encode / 8) + 1; + + for (int i = 0; i < bytes_to_encode; ++i) { + const int num_bits = (encoder.Bits() + 8 <= bits_to_encode) + ? 8 + : bits_to_encode - encoder.Bits(); + encoder.PutBits(data[i], num_bits); + } + + BitDecoder decoder; + decoder.reset(static_cast<const void *>(buffer), bytes_to_encode); + int64_t bits_to_decode = encoder.Bits(); + for (int i = 0; i < bytes_to_encode; ++i) { + uint32_t x = 0; + const int num_bits = (bits_to_decode > 8) ? 8 : bits_to_decode; + ASSERT_TRUE(decoder.GetBits(num_bits, &x)); + const int bits_to_shift = 8 - num_bits; + const uint8_t test_byte = + ((data[i] << bits_to_shift) & 0xff) >> bits_to_shift; + ASSERT_EQ(x, test_byte); + bits_to_decode -= 8; + } + + ASSERT_EQ(bits_to_encode, decoder.BitsDecoded()); +} + +TEST_F(BufferBitCodingTest, TestSingleBits) { + const int data = 0xaaaa; + + BitDecoder decoder; + decoder.reset(static_cast<const void *>(&data), sizeof(data)); + + for (uint32_t i = 0; i < 16; ++i) { + uint32_t x = 0; + ASSERT_TRUE(decoder.GetBits(1, &x)); + ASSERT_EQ(x, (i % 2)); + } + + ASSERT_EQ(16u, decoder.BitsDecoded()); +} + +TEST_F(BufferBitCodingTest, TestMultipleBits) { + const uint8_t data[] = {0x76, 0x54, 0x32, 0x10, 0x76, 0x54, 0x32, 0x10}; + + BitDecoder decoder; + decoder.reset(static_cast<const void *>(data), sizeof(data)); + + uint32_t x = 0; + for (uint32_t i = 0; i < 2; ++i) { + ASSERT_TRUE(decoder.GetBits(16, &x)); + ASSERT_EQ(x, 0x5476u); + ASSERT_EQ(16 + (i * 32), decoder.BitsDecoded()); + + ASSERT_TRUE(decoder.GetBits(16, &x)); + ASSERT_EQ(x, 0x1032u); + ASSERT_EQ(32 + (i * 32), decoder.BitsDecoded()); + } +} + +} // namespace draco diff --git a/extern/draco/dracoenc/src/draco/core/cycle_timer.cc b/extern/draco/dracoenc/src/draco/core/cycle_timer.cc new file mode 100644 index 00000000000..1eea9f59702 --- /dev/null +++ b/extern/draco/dracoenc/src/draco/core/cycle_timer.cc @@ -0,0 +1,49 @@ +// Copyright 2016 The Draco Authors. +// +// 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 "draco/core/cycle_timer.h" + +namespace draco { +void DracoTimer::Start() { +#ifdef _WIN32 + QueryPerformanceCounter(&tv_start); +#else + gettimeofday(&tv_start, NULL); +#endif +} + +void DracoTimer::Stop() { +#ifdef _WIN32 + QueryPerformanceCounter(&tv_end); +#else + gettimeofday(&tv_end, NULL); +#endif +} + +int64_t DracoTimer::GetInMs() { +#ifdef _WIN32 + LARGE_INTEGER elapsed = {0}; + elapsed.QuadPart = tv_end.QuadPart - tv_start.QuadPart; + + LARGE_INTEGER frequency = {0}; + QueryPerformanceFrequency(&frequency); + return elapsed.QuadPart * 1000 / frequency.QuadPart; +#else + const int64_t seconds = (tv_end.tv_sec - tv_start.tv_sec) * 1000; + const int64_t milliseconds = (tv_end.tv_usec - tv_start.tv_usec) / 1000; + return seconds + milliseconds; +#endif +} + +} // namespace draco diff --git a/extern/draco/dracoenc/src/draco/core/cycle_timer.h b/extern/draco/dracoenc/src/draco/core/cycle_timer.h new file mode 100644 index 00000000000..172f1c2e9b5 --- /dev/null +++ b/extern/draco/dracoenc/src/draco/core/cycle_timer.h @@ -0,0 +1,50 @@ +// Copyright 2016 The Draco Authors. +// +// 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 DRACO_CORE_CYCLE_TIMER_H_ +#define DRACO_CORE_CYCLE_TIMER_H_ + +#ifdef _WIN32 +#ifndef WIN32_LEAN_AND_MEAN +#define WIN32_LEAN_AND_MEAN +#endif +#include <windows.h> +typedef LARGE_INTEGER timeval; +#else +#include <sys/time.h> +#endif + +#include <cinttypes> +#include <cstddef> + +namespace draco { + +class DracoTimer { + public: + DracoTimer() {} + ~DracoTimer() {} + void Start(); + void Stop(); + int64_t GetInMs(); + + private: + timeval tv_start; + timeval tv_end; +}; + +typedef DracoTimer CycleTimer; + +} // namespace draco + +#endif // DRACO_CORE_CYCLE_TIMER_H_ diff --git a/extern/draco/dracoenc/src/draco/core/data_buffer.cc b/extern/draco/dracoenc/src/draco/core/data_buffer.cc new file mode 100644 index 00000000000..3b57367bbf1 --- /dev/null +++ b/extern/draco/dracoenc/src/draco/core/data_buffer.cc @@ -0,0 +1,55 @@ +// Copyright 2016 The Draco Authors. +// +// 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 "draco/core/data_buffer.h" + +namespace draco { + +DataBuffer::DataBuffer() {} + +bool DataBuffer::Update(const void *data, int64_t size) { + const int64_t offset = 0; + return this->Update(data, size, offset); +} + +bool DataBuffer::Update(const void *data, int64_t size, int64_t offset) { + if (data == nullptr) { + if (size + offset < 0) + return false; + // If no data is provided, just resize the buffer. + data_.resize(size + offset); + } else { + if (size < 0) + return false; + if (size + offset > static_cast<int64_t>(data_.size())) + data_.resize(size + offset); + const uint8_t *const byte_data = static_cast<const uint8_t *>(data); + std::copy(byte_data, byte_data + size, data_.data() + offset); + } + descriptor_.buffer_update_count++; + return true; +} + +void DataBuffer::Resize(int64_t size) { + data_.resize(size); + descriptor_.buffer_update_count++; +} + +void DataBuffer::WriteDataToStream(std::ostream &stream) { + if (data_.size() == 0) + return; + stream.write(reinterpret_cast<char *>(data_.data()), data_.size()); +} + +} // namespace draco diff --git a/extern/draco/dracoenc/src/draco/core/data_buffer.h b/extern/draco/dracoenc/src/draco/core/data_buffer.h new file mode 100644 index 00000000000..8ee690540bc --- /dev/null +++ b/extern/draco/dracoenc/src/draco/core/data_buffer.h @@ -0,0 +1,82 @@ +// Copyright 2016 The Draco Authors. +// +// 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 DRACO_CORE_DATA_BUFFER_H_ +#define DRACO_CORE_DATA_BUFFER_H_ + +#include <cstring> +#include <ostream> +#include <vector> + +#include "draco/core/draco_types.h" + +namespace draco { + +// Buffer descriptor servers as a unique identifier of a buffer. +struct DataBufferDescriptor { + DataBufferDescriptor() : buffer_id(0), buffer_update_count(0) {} + // Id of the data buffer. + int64_t buffer_id; + // The number of times the buffer content was updated. + int64_t buffer_update_count; +}; + +// Class used for storing raw buffer data. +class DataBuffer { + public: + DataBuffer(); + bool Update(const void *data, int64_t size); + bool Update(const void *data, int64_t size, int64_t offset); + + // Reallocate the buffer storage to a new size keeping the data unchanged. + void Resize(int64_t new_size); + void WriteDataToStream(std::ostream &stream); + // Reads data from the buffer. Potentially unsafe, called needs to ensure + // the accessed memory is valid. + void Read(int64_t byte_pos, void *out_data, size_t data_size) const { + memcpy(out_data, data() + byte_pos, data_size); + } + + // Writes data to the buffer. Unsafe, caller must ensure the accessed memory + // is valid. + void Write(int64_t byte_pos, const void *in_data, size_t data_size) { + memcpy(const_cast<uint8_t *>(data()) + byte_pos, in_data, data_size); + } + + // Copies data from another buffer to this buffer. + void Copy(int64_t dst_offset, const DataBuffer *src_buf, int64_t src_offset, + int64_t size) { + memcpy(const_cast<uint8_t *>(data()) + dst_offset, + src_buf->data() + src_offset, size); + } + + void set_update_count(int64_t buffer_update_count) { + descriptor_.buffer_update_count = buffer_update_count; + } + int64_t update_count() const { return descriptor_.buffer_update_count; } + size_t data_size() const { return data_.size(); } + const uint8_t *data() const { return data_.data(); } + uint8_t *data() { return &data_[0]; } + int64_t buffer_id() const { return descriptor_.buffer_id; } + void set_buffer_id(int64_t buffer_id) { descriptor_.buffer_id = buffer_id; } + + private: + std::vector<uint8_t> data_; + // Counter incremented by Update() calls. + DataBufferDescriptor descriptor_; +}; + +} // namespace draco + +#endif // DRACO_CORE_DATA_BUFFER_H_ diff --git a/extern/draco/dracoenc/src/draco/core/decoder_buffer.cc b/extern/draco/dracoenc/src/draco/core/decoder_buffer.cc new file mode 100644 index 00000000000..5ce1f064ac2 --- /dev/null +++ b/extern/draco/dracoenc/src/draco/core/decoder_buffer.cc @@ -0,0 +1,70 @@ +// Copyright 2016 The Draco Authors. +// +// 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 "draco/core/decoder_buffer.h" + +#include "draco/core/macros.h" +#include "draco/core/varint_decoding.h" + +namespace draco { + +DecoderBuffer::DecoderBuffer() + : data_(nullptr), + data_size_(0), + pos_(0), + bit_mode_(false), + bitstream_version_(0) {} + +void DecoderBuffer::Init(const char *data, size_t data_size) { + Init(data, data_size, bitstream_version_); +} + +void DecoderBuffer::Init(const char *data, size_t data_size, uint16_t version) { + data_ = data; + data_size_ = data_size; + bitstream_version_ = version; + pos_ = 0; +} + +bool DecoderBuffer::StartBitDecoding(bool decode_size, uint64_t *out_size) { + if (decode_size) { +#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED + if (bitstream_version_ < DRACO_BITSTREAM_VERSION(2, 2)) { + if (!Decode(out_size)) + return false; + } else +#endif + { + if (!DecodeVarint(out_size, this)) + return false; + } + } + bit_mode_ = true; + bit_decoder_.reset(data_head(), remaining_size()); + return true; +} + +void DecoderBuffer::EndBitDecoding() { + bit_mode_ = false; + const uint64_t bits_decoded = bit_decoder_.BitsDecoded(); + const uint64_t bytes_decoded = (bits_decoded + 7) / 8; + pos_ += bytes_decoded; +} + +DecoderBuffer::BitDecoder::BitDecoder() + : bit_buffer_(nullptr), bit_buffer_end_(nullptr), bit_offset_(0) {} + +DecoderBuffer::BitDecoder::~BitDecoder() {} + +} // namespace draco diff --git a/extern/draco/dracoenc/src/draco/core/decoder_buffer.h b/extern/draco/dracoenc/src/draco/core/decoder_buffer.h new file mode 100644 index 00000000000..5e3d1ac738d --- /dev/null +++ b/extern/draco/dracoenc/src/draco/core/decoder_buffer.h @@ -0,0 +1,210 @@ +// Copyright 2016 The Draco Authors. +// +// 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 DRACO_CORE_DECODER_BUFFER_H_ +#define DRACO_CORE_DECODER_BUFFER_H_ + +#include <stdint.h> +#include <cstring> +#include <memory> + +#include "draco/draco_features.h" + +#include "draco/core/macros.h" + +namespace draco { + +// Class is a wrapper around input data used by MeshDecoder. It provides a +// basic interface for decoding either typed or variable-bit sized data. +class DecoderBuffer { + public: + DecoderBuffer(); + DecoderBuffer(const DecoderBuffer &buf) = default; + + DecoderBuffer &operator=(const DecoderBuffer &buf) = default; + + // Sets the buffer's internal data. Note that no copy of the input data is + // made so the data owner needs to keep the data valid and unchanged for + // runtime of the decoder. + void Init(const char *data, size_t data_size); + + // Sets the buffer's internal data. |version| is the Draco bitstream version. + void Init(const char *data, size_t data_size, uint16_t version); + + // Starts decoding a bit sequence. + // decode_size must be true if the size of the encoded bit data was included, + // during encoding. The size is then returned to out_size. + // Returns false on error. + bool StartBitDecoding(bool decode_size, uint64_t *out_size); + + // Ends the decoding of the bit sequence and return to the default + // byte-aligned decoding. + void EndBitDecoding(); + + // Decodes up to 32 bits into out_val. Can be called only in between + // StartBitDecoding and EndBitDecoding. Otherwise returns false. + bool DecodeLeastSignificantBits32(int nbits, uint32_t *out_value) { + if (!bit_decoder_active()) + return false; + bit_decoder_.GetBits(nbits, out_value); + return true; + } + + // Decodes an arbitrary data type. + // Can be used only when we are not decoding a bit-sequence. + // Returns false on error. + template <typename T> + bool Decode(T *out_val) { + if (!Peek(out_val)) + return false; + pos_ += sizeof(T); + return true; + } + + bool Decode(void *out_data, size_t size_to_decode) { + if (data_size_ < static_cast<int64_t>(pos_ + size_to_decode)) + return false; // Buffer overflow. + memcpy(out_data, (data_ + pos_), size_to_decode); + pos_ += size_to_decode; + return true; + } + + // Decodes an arbitrary data, but does not advance the reading position. + template <typename T> + bool Peek(T *out_val) { + const size_t size_to_decode = sizeof(T); + if (data_size_ < static_cast<int64_t>(pos_ + size_to_decode)) + return false; // Buffer overflow. + memcpy(out_val, (data_ + pos_), size_to_decode); + return true; + } + + bool Peek(void *out_data, size_t size_to_peek) { + if (data_size_ < static_cast<int64_t>(pos_ + size_to_peek)) + return false; // Buffer overflow. + memcpy(out_data, (data_ + pos_), size_to_peek); + return true; + } + + // Discards #bytes from the input buffer. + void Advance(int64_t bytes) { pos_ += bytes; } + + // Moves the parsing position to a specific offset from the beginning of the + // input data. + void StartDecodingFrom(int64_t offset) { pos_ = offset; } + + void set_bitstream_version(uint16_t version) { bitstream_version_ = version; } + + // Returns the data array at the current decoder position. + const char *data_head() const { return data_ + pos_; } + int64_t remaining_size() const { return data_size_ - pos_; } + int64_t decoded_size() const { return pos_; } + bool bit_decoder_active() const { return bit_mode_; } + + // Returns the bitstream associated with the data. Returns 0 if unknown. + uint16_t bitstream_version() const { return bitstream_version_; } + + private: + // Internal helper class to decode bits from a bit buffer. + class BitDecoder { + public: + BitDecoder(); + ~BitDecoder(); + + // Sets the bit buffer to |b|. |s| is the size of |b| in bytes. + inline void reset(const void *b, size_t s) { + bit_offset_ = 0; + bit_buffer_ = static_cast<const uint8_t *>(b); + bit_buffer_end_ = bit_buffer_ + s; + } + + // Returns number of bits decoded so far. + inline uint64_t BitsDecoded() const { + return static_cast<uint64_t>(bit_offset_); + } + + // Return number of bits available for decoding + inline uint64_t AvailBits() const { + return ((bit_buffer_end_ - bit_buffer_) * 8) - bit_offset_; + } + + inline uint32_t EnsureBits(int k) { + DRACO_DCHECK_LE(k, 24); + DRACO_DCHECK_LE(static_cast<uint64_t>(k), AvailBits()); + + uint32_t buf = 0; + for (int i = 0; i < k; ++i) { + buf |= PeekBit(i) << i; + } + return buf; // Okay to return extra bits + } + + inline void ConsumeBits(int k) { bit_offset_ += k; } + + // Returns |nbits| bits in |x|. + inline bool GetBits(int32_t nbits, uint32_t *x) { + DRACO_DCHECK_GE(nbits, 0); + DRACO_DCHECK_LE(nbits, 32); + uint32_t value = 0; + for (int32_t bit = 0; bit < nbits; ++bit) + value |= GetBit() << bit; + *x = value; + return true; + } + + private: + // TODO(fgalligan): Add support for error reporting on range check. + // Returns one bit from the bit buffer. + inline int GetBit() { + const size_t off = bit_offset_; + const size_t byte_offset = off >> 3; + const int bit_shift = static_cast<int>(off & 0x7); + if (bit_buffer_ + byte_offset < bit_buffer_end_) { + const int bit = (bit_buffer_[byte_offset] >> bit_shift) & 1; + bit_offset_ = off + 1; + return bit; + } + return 0; + } + + inline int PeekBit(int offset) { + const size_t off = bit_offset_ + offset; + const size_t byte_offset = off >> 3; + const int bit_shift = static_cast<int>(off & 0x7); + if (bit_buffer_ + byte_offset < bit_buffer_end_) { + const int bit = (bit_buffer_[byte_offset] >> bit_shift) & 1; + return bit; + } + return 0; + } + + const uint8_t *bit_buffer_; + const uint8_t *bit_buffer_end_; + size_t bit_offset_; + }; + friend class BufferBitCodingTest; + + const char *data_; + int64_t data_size_; + + // Current parsing position of the decoder. + int64_t pos_; + BitDecoder bit_decoder_; + bool bit_mode_; + uint16_t bitstream_version_; +}; + +} // namespace draco + +#endif // DRACO_CORE_DECODER_BUFFER_H_ diff --git a/extern/draco/dracoenc/src/draco/core/divide.cc b/extern/draco/dracoenc/src/draco/core/divide.cc new file mode 100644 index 00000000000..6d2e57120c8 --- /dev/null +++ b/extern/draco/dracoenc/src/draco/core/divide.cc @@ -0,0 +1,88 @@ +// Copyright 2016 The Draco Authors. +// +// 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 based off libvpx's divide.c. + +#include "draco/core/divide.h" + +namespace draco { + +const struct fastdiv_elem vp10_fastdiv_tab[256] = { + {0, 0}, {0, 0}, {0, 1}, {1431655766, 2}, + {0, 2}, {2576980378, 3}, {1431655766, 3}, {613566757, 3}, + {0, 3}, {3340530120, 4}, {2576980378, 4}, {1952257862, 4}, + {1431655766, 4}, {991146300, 4}, {613566757, 4}, {286331154, 4}, + {0, 4}, {3789677026, 5}, {3340530120, 5}, {2938661835, 5}, + {2576980378, 5}, {2249744775, 5}, {1952257862, 5}, {1680639377, 5}, + {1431655766, 5}, {1202590843, 5}, {991146300, 5}, {795364315, 5}, + {613566757, 5}, {444306962, 5}, {286331154, 5}, {138547333, 5}, + {0, 5}, {4034666248, 6}, {3789677026, 6}, {3558687189, 6}, + {3340530120, 6}, {3134165325, 6}, {2938661835, 6}, {2753184165, 6}, + {2576980378, 6}, {2409371898, 6}, {2249744775, 6}, {2097542168, 6}, + {1952257862, 6}, {1813430637, 6}, {1680639377, 6}, {1553498810, 6}, + {1431655766, 6}, {1314785907, 6}, {1202590843, 6}, {1094795586, 6}, + {991146300, 6}, {891408307, 6}, {795364315, 6}, {702812831, 6}, + {613566757, 6}, {527452125, 6}, {444306962, 6}, {363980280, 6}, + {286331154, 6}, {211227900, 6}, {138547333, 6}, {68174085, 6}, + {0, 6}, {4162814457, 7}, {4034666248, 7}, {3910343360, 7}, + {3789677026, 7}, {3672508268, 7}, {3558687189, 7}, {3448072337, 7}, + {3340530120, 7}, {3235934265, 7}, {3134165325, 7}, {3035110223, 7}, + {2938661835, 7}, {2844718599, 7}, {2753184165, 7}, {2663967058, 7}, + {2576980378, 7}, {2492141518, 7}, {2409371898, 7}, {2328596727, 7}, + {2249744775, 7}, {2172748162, 7}, {2097542168, 7}, {2024065048, 7}, + {1952257862, 7}, {1882064321, 7}, {1813430637, 7}, {1746305385, 7}, + {1680639377, 7}, {1616385542, 7}, {1553498810, 7}, {1491936009, 7}, + {1431655766, 7}, {1372618415, 7}, {1314785907, 7}, {1258121734, 7}, + {1202590843, 7}, {1148159575, 7}, {1094795586, 7}, {1042467791, 7}, + {991146300, 7}, {940802361, 7}, {891408307, 7}, {842937507, 7}, + {795364315, 7}, {748664025, 7}, {702812831, 7}, {657787785, 7}, + {613566757, 7}, {570128403, 7}, {527452125, 7}, {485518043, 7}, + {444306962, 7}, {403800345, 7}, {363980280, 7}, {324829460, 7}, + {286331154, 7}, {248469183, 7}, {211227900, 7}, {174592167, 7}, + {138547333, 7}, {103079216, 7}, {68174085, 7}, {33818641, 7}, + {0, 7}, {4228378656, 8}, {4162814457, 8}, {4098251237, 8}, + {4034666248, 8}, {3972037425, 8}, {3910343360, 8}, {3849563281, 8}, + {3789677026, 8}, {3730665024, 8}, {3672508268, 8}, {3615188300, 8}, + {3558687189, 8}, {3502987511, 8}, {3448072337, 8}, {3393925206, 8}, + {3340530120, 8}, {3287871517, 8}, {3235934265, 8}, {3184703642, 8}, + {3134165325, 8}, {3084305374, 8}, {3035110223, 8}, {2986566663, 8}, + {2938661835, 8}, {2891383213, 8}, {2844718599, 8}, {2798656110, 8}, + {2753184165, 8}, {2708291480, 8}, {2663967058, 8}, {2620200175, 8}, + {2576980378, 8}, {2534297473, 8}, {2492141518, 8}, {2450502814, 8}, + {2409371898, 8}, {2368739540, 8}, {2328596727, 8}, {2288934667, 8}, + {2249744775, 8}, {2211018668, 8}, {2172748162, 8}, {2134925265, 8}, + {2097542168, 8}, {2060591247, 8}, {2024065048, 8}, {1987956292, 8}, + {1952257862, 8}, {1916962805, 8}, {1882064321, 8}, {1847555765, 8}, + {1813430637, 8}, {1779682582, 8}, {1746305385, 8}, {1713292966, 8}, + {1680639377, 8}, {1648338801, 8}, {1616385542, 8}, {1584774030, 8}, + {1553498810, 8}, {1522554545, 8}, {1491936009, 8}, {1461638086, 8}, + {1431655766, 8}, {1401984144, 8}, {1372618415, 8}, {1343553873, 8}, + {1314785907, 8}, {1286310003, 8}, {1258121734, 8}, {1230216764, 8}, + {1202590843, 8}, {1175239808, 8}, {1148159575, 8}, {1121346142, 8}, + {1094795586, 8}, {1068504060, 8}, {1042467791, 8}, {1016683080, 8}, + {991146300, 8}, {965853890, 8}, {940802361, 8}, {915988286, 8}, + {891408307, 8}, {867059126, 8}, {842937507, 8}, {819040276, 8}, + {795364315, 8}, {771906565, 8}, {748664025, 8}, {725633745, 8}, + {702812831, 8}, {680198441, 8}, {657787785, 8}, {635578121, 8}, + {613566757, 8}, {591751050, 8}, {570128403, 8}, {548696263, 8}, + {527452125, 8}, {506393524, 8}, {485518043, 8}, {464823301, 8}, + {444306962, 8}, {423966729, 8}, {403800345, 8}, {383805589, 8}, + {363980280, 8}, {344322273, 8}, {324829460, 8}, {305499766, 8}, + {286331154, 8}, {267321616, 8}, {248469183, 8}, {229771913, 8}, + {211227900, 8}, {192835267, 8}, {174592167, 8}, {156496785, 8}, + {138547333, 8}, {120742053, 8}, {103079216, 8}, {85557118, 8}, + {68174085, 8}, {50928466, 8}, {33818641, 8}, {16843010, 8}, +}; + +} // namespace draco diff --git a/extern/draco/dracoenc/src/draco/core/divide.h b/extern/draco/dracoenc/src/draco/core/divide.h new file mode 100644 index 00000000000..2217c861e0b --- /dev/null +++ b/extern/draco/dracoenc/src/draco/core/divide.h @@ -0,0 +1,41 @@ +// Copyright 2016 The Draco Authors. +// +// 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 DRACO_CORE_DIVIDE_H_ +#define DRACO_CORE_DIVIDE_H_ +// An implementation of the divide by multiply algorithm +// https://gmplib.org/~tege/divcnst-pldi94.pdf +// This file is based off libvpx's divide.h. + +#include <stdint.h> +#include <climits> + +namespace draco { + +struct fastdiv_elem { + unsigned mult; + unsigned shift; +}; + +extern const struct fastdiv_elem vp10_fastdiv_tab[256]; + +static inline unsigned fastdiv(unsigned x, int y) { + unsigned t = + ((uint64_t)x * vp10_fastdiv_tab[y].mult) >> (sizeof(x) * CHAR_BIT); + return (t + x) >> vp10_fastdiv_tab[y].shift; +} + +} // namespace draco + +#endif // DRACO_CORE_DIVIDE_H_ diff --git a/extern/draco/dracoenc/src/draco/core/draco_index_type.h b/extern/draco/dracoenc/src/draco/core/draco_index_type.h new file mode 100644 index 00000000000..d9dd3f64fa8 --- /dev/null +++ b/extern/draco/dracoenc/src/draco/core/draco_index_type.h @@ -0,0 +1,183 @@ +// Copyright 2016 The Draco Authors. +// +// 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 files provides a basic framework for strongly typed indices that are +// used within the Draco library. The motivation of using strongly typed indices +// is to prevent bugs caused by mixing up incompatible indices, such as indexing +// mesh faces with point indices and vice versa. +// +// Usage: +// Define strongly typed index using macro: +// +// DEFINE_NEW_DRACO_INDEX_TYPE(value_type, name) +// +// where |value_type| is the data type of the index value (such as int32_t) +// and |name| is a unique typename of the new index. +// +// E.g., we can define new index types as: +// +// DEFINE_NEW_DRACO_INDEX_TYPE(int, PointIndex) +// DEFINE_NEW_DRACO_INDEX_TYPE(int, FaceIndex) +// +// The new types can then be used in the similar way as the regular weakly +// typed indices (such as int32, int64, ...), but they cannot be +// accidentally misassigned. E.g.: +// +// PointIndex point_index(10); +// FaceIndex face_index; +// face_index = point_index; // Compile error! +// +// One can still cast one type to another explicitly by accessing the index +// value directly using the .value() method: +// +// face_index = FaceIndex(point_index.value()); // Compiles OK. +// +// Strongly typed indices support most of the common binary and unary +// operators and support for additional operators can be added if +// necessary. + +#ifndef DRACO_CORE_DRACO_INDEX_TYPE_H_ +#define DRACO_CORE_DRACO_INDEX_TYPE_H_ + +#include <ostream> + +#include "draco/draco_features.h" + +namespace draco { + +#define DEFINE_NEW_DRACO_INDEX_TYPE(value_type, name) \ + struct name##_tag_type_ {}; \ + typedef IndexType<value_type, name##_tag_type_> name; + +template <class ValueTypeT, class TagT> +class IndexType { + public: + typedef IndexType<ValueTypeT, TagT> ThisIndexType; + typedef ValueTypeT ValueType; + + constexpr IndexType() : value_(ValueTypeT()) {} + constexpr explicit IndexType(ValueTypeT value) : value_(value) {} + + constexpr ValueTypeT value() const { return value_; } + + constexpr bool operator==(const IndexType &i) const { + return value_ == i.value_; + } + constexpr bool operator==(const ValueTypeT &val) const { + return value_ == val; + } + constexpr bool operator!=(const IndexType &i) const { + return value_ != i.value_; + } + constexpr bool operator!=(const ValueTypeT &val) const { + return value_ != val; + } + constexpr bool operator<(const IndexType &i) const { + return value_ < i.value_; + } + constexpr bool operator<(const ValueTypeT &val) const { return value_ < val; } + constexpr bool operator>(const IndexType &i) const { + return value_ > i.value_; + } + constexpr bool operator>(const ValueTypeT &val) const { return value_ > val; } + constexpr bool operator>=(const IndexType &i) const { + return value_ >= i.value_; + } + constexpr bool operator>=(const ValueTypeT &val) const { + return value_ >= val; + } + + inline ThisIndexType &operator++() { + ++value_; + return *this; + } + inline ThisIndexType operator++(int) { + const ThisIndexType ret(value_); + ++value_; + return ret; + } + + inline ThisIndexType &operator--() { + --value_; + return *this; + } + inline ThisIndexType operator--(int) { + const ThisIndexType ret(value_); + --value_; + return ret; + } + + constexpr ThisIndexType operator+(const IndexType &i) const { + return ThisIndexType(value_ + i.value_); + } + constexpr ThisIndexType operator+(const ValueTypeT &val) const { + return ThisIndexType(value_ + val); + } + constexpr ThisIndexType operator-(const IndexType &i) const { + return ThisIndexType(value_ - i.value_); + } + constexpr ThisIndexType operator-(const ValueTypeT &val) const { + return ThisIndexType(value_ - val); + } + + inline ThisIndexType &operator+=(const IndexType &i) { + value_ += i.value_; + return *this; + } + inline ThisIndexType operator+=(const ValueTypeT &val) { + value_ += val; + return *this; + } + inline ThisIndexType &operator-=(const IndexType &i) { + value_ -= i.value_; + return *this; + } + inline ThisIndexType operator-=(const ValueTypeT &val) { + value_ -= val; + return *this; + } + inline ThisIndexType &operator=(const ThisIndexType &i) { + value_ = i.value_; + return *this; + } + inline ThisIndexType &operator=(const ValueTypeT &val) { + value_ = val; + return *this; + } + + private: + ValueTypeT value_; +}; + +// Stream operator << provided for logging purposes. +template <class ValueTypeT, class TagT> +std::ostream &operator<<(std::ostream &os, IndexType<ValueTypeT, TagT> index) { + return os << index.value(); +} + +} // namespace draco + +// Specialize std::hash for the strongly indexed types. +namespace std { + +template <class ValueTypeT, class TagT> +struct hash<draco::IndexType<ValueTypeT, TagT>> { + size_t operator()(const draco::IndexType<ValueTypeT, TagT> &i) const { + return static_cast<size_t>(i.value()); + } +}; + +} // namespace std + +#endif // DRACO_CORE_DRACO_INDEX_TYPE_H_ diff --git a/extern/draco/dracoenc/src/draco/core/draco_index_type_vector.h b/extern/draco/dracoenc/src/draco/core/draco_index_type_vector.h new file mode 100644 index 00000000000..e2062ef3f35 --- /dev/null +++ b/extern/draco/dracoenc/src/draco/core/draco_index_type_vector.h @@ -0,0 +1,77 @@ +// Copyright 2016 The Draco Authors. +// +// 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 DRACO_CORE_DRACO_INDEX_TYPE_VECTOR_H_ +#define DRACO_CORE_DRACO_INDEX_TYPE_VECTOR_H_ + +#include <cstddef> +#include <utility> +#include <vector> + +#include "draco/core/draco_index_type.h" + +namespace draco { + +// A wrapper around the standard std::vector that supports indexing of the +// vector entries using the strongly typed indices as defined in +// draco_index_type.h . +// TODO(ostava): Make the interface more complete. It's currently missing +// features such as iterators. +// TODO(draco-eng): Make unit tests for this class. +template <class IndexTypeT, class ValueTypeT> +class IndexTypeVector { + public: + typedef typename std::vector<ValueTypeT>::const_reference const_reference; + typedef typename std::vector<ValueTypeT>::reference reference; + + IndexTypeVector() {} + explicit IndexTypeVector(size_t size) : vector_(size) {} + IndexTypeVector(size_t size, const ValueTypeT &val) : vector_(size, val) {} + + void clear() { vector_.clear(); } + void reserve(size_t size) { vector_.reserve(size); } + void resize(size_t size) { vector_.resize(size); } + void resize(size_t size, const ValueTypeT &val) { vector_.resize(size, val); } + void assign(size_t size, const ValueTypeT &val) { vector_.assign(size, val); } + + void swap(IndexTypeVector<IndexTypeT, ValueTypeT> &arg) { + vector_.swap(arg.vector_); + } + + size_t size() const { return vector_.size(); } + + void push_back(const ValueTypeT &val) { vector_.push_back(val); } + void push_back(ValueTypeT &&val) { vector_.push_back(std::move(val)); } + + inline reference operator[](const IndexTypeT &index) { + return vector_[index.value()]; + } + inline const_reference operator[](const IndexTypeT &index) const { + return vector_[index.value()]; + } + inline reference at(const IndexTypeT &index) { + return vector_[index.value()]; + } + inline const_reference at(const IndexTypeT &index) const { + return vector_[index.value()]; + } + const ValueTypeT *data() const { return vector_.data(); } + + private: + std::vector<ValueTypeT> vector_; +}; + +} // namespace draco + +#endif // DRACO_CORE_DRACO_INDEX_TYPE_VECTOR_H_ diff --git a/extern/draco/dracoenc/src/draco/core/draco_test_base.h b/extern/draco/dracoenc/src/draco/core/draco_test_base.h new file mode 100644 index 00000000000..f5c9d751e03 --- /dev/null +++ b/extern/draco/dracoenc/src/draco/core/draco_test_base.h @@ -0,0 +1,11 @@ +// Wrapper for including googletest indirectly. Useful when the location of the +// googletest sources must change depending on build environment and repository +// source location. +#ifndef DRACO_CORE_DRACO_TEST_BASE_H_ +#define DRACO_CORE_DRACO_TEST_BASE_H_ + +static bool FLAGS_update_golden_files; +#include "gtest/gtest.h" +#include "testing/draco_test_config.h" + +#endif // DRACO_CORE_DRACO_TEST_BASE_H_ diff --git a/extern/draco/dracoenc/src/draco/core/draco_test_utils.cc b/extern/draco/dracoenc/src/draco/core/draco_test_utils.cc new file mode 100644 index 00000000000..fa225576d9c --- /dev/null +++ b/extern/draco/dracoenc/src/draco/core/draco_test_utils.cc @@ -0,0 +1,83 @@ +// Copyright 2016 The Draco Authors. +// +// 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 "draco/core/draco_test_utils.h" + +#include <fstream> + +#include "draco/core/macros.h" +#include "draco_test_base.h" + +namespace draco { + +namespace { +static constexpr char kTestDataDir[] = DRACO_TEST_DATA_DIR; +static constexpr char kTestTempDir[] = DRACO_TEST_TEMP_DIR; +} // namespace + +std::string GetTestFileFullPath(const std::string &file_name) { + return std::string(kTestDataDir) + std::string("/") + file_name; +} + +std::string GetTestTempFileFullPath(const std::string &file_name) { + return std::string(kTestTempDir) + std::string("/") + file_name; +} + +bool GenerateGoldenFile(const std::string &golden_file_name, const void *data, + int data_size) { + const std::string path = GetTestFileFullPath(golden_file_name); + std::ofstream file(path, std::ios::binary); + if (!file) + return false; + file.write(static_cast<const char *>(data), data_size); + file.close(); + return true; +} + +bool CompareGoldenFile(const std::string &golden_file_name, const void *data, + int data_size) { + const std::string golden_path = GetTestFileFullPath(golden_file_name); + std::ifstream in_file(golden_path); + if (!in_file || data_size < 0) + return false; + const char *const data_c8 = static_cast<const char *>(data); + constexpr int buffer_size = 1024; + char buffer[buffer_size]; + size_t extracted_size = 0; + size_t remaining_data_size = data_size; + int offset = 0; + while ((extracted_size = in_file.read(buffer, buffer_size).gcount()) > 0) { + if (remaining_data_size <= 0) + break; // Input and golden sizes are different. + size_t size_to_check = extracted_size; + if (remaining_data_size < size_to_check) + size_to_check = remaining_data_size; + for (uint32_t i = 0; i < size_to_check; ++i) { + if (buffer[i] != data_c8[offset++]) { + LOG(INFO) << "Test output differed from golden file at byte " + << offset - 1; + return false; + } + } + remaining_data_size -= extracted_size; + } + if (remaining_data_size != extracted_size) { + // Both of these values should be 0 at the end. + LOG(INFO) << "Test output size differed from golden file size"; + return false; + } + return true; +} + +} // namespace draco diff --git a/extern/draco/dracoenc/src/draco/core/draco_test_utils.h b/extern/draco/dracoenc/src/draco/core/draco_test_utils.h new file mode 100644 index 00000000000..2ed93cd960b --- /dev/null +++ b/extern/draco/dracoenc/src/draco/core/draco_test_utils.h @@ -0,0 +1,65 @@ +// Copyright 2016 The Draco Authors. +// +// 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 DRACO_CORE_DRACO_TEST_UTILS_H_ +#define DRACO_CORE_DRACO_TEST_UTILS_H_ + +#include "draco/core/draco_test_base.h" +#include "draco/io/mesh_io.h" +#include "draco/io/point_cloud_io.h" + +namespace draco { + +// Returns the full path to a given file system entry, such as test file or test +// directory. +std::string GetTestFileFullPath(const std::string &entry_name); + +// Returns the full path to a given temporary file (a location where tests store +// generated files). +std::string GetTestTempFileFullPath(const std::string &file_name); + +// Generates a new golden file and saves it into the correct folder. +// Returns false if the file couldn't be created. +bool GenerateGoldenFile(const std::string &golden_file_name, const void *data, + int data_size); + +// Compare a golden file content with the input data. +// Function will log the first byte position where the data differ. +// Returns false if there are any differences. +bool CompareGoldenFile(const std::string &golden_file_name, const void *data, + int data_size); + +// Loads a mesh / point cloud specified by a |file_name| that is going to be +// automatically converted to the correct path available to the testing +// instance. +inline std::unique_ptr<Mesh> ReadMeshFromTestFile( + const std::string &file_name) { + const std::string path = GetTestFileFullPath(file_name); + return ReadMeshFromFile(path).value(); +} +inline std::unique_ptr<Mesh> ReadMeshFromTestFile(const std::string &file_name, + bool use_metadata) { + const std::string path = GetTestFileFullPath(file_name); + return ReadMeshFromFile(path, use_metadata).value(); +} + +inline std::unique_ptr<PointCloud> ReadPointCloudFromTestFile( + const std::string &file_name) { + const std::string path = GetTestFileFullPath(file_name); + return ReadPointCloudFromFile(path).value(); +} + +} // namespace draco + +#endif // DRACO_CORE_DRACO_TEST_UTILS_H_ diff --git a/extern/draco/dracoenc/src/draco/core/draco_tests.cc b/extern/draco/dracoenc/src/draco/core/draco_tests.cc new file mode 100644 index 00000000000..fdaa14da508 --- /dev/null +++ b/extern/draco/dracoenc/src/draco/core/draco_tests.cc @@ -0,0 +1,6 @@ +#include "draco/core/draco_test_base.h" + +int main(int argc, char *argv[]) { + ::testing::InitGoogleTest(&argc, argv); + return RUN_ALL_TESTS(); +} diff --git a/extern/draco/dracoenc/src/draco/core/draco_types.cc b/extern/draco/dracoenc/src/draco/core/draco_types.cc new file mode 100644 index 00000000000..45b22470057 --- /dev/null +++ b/extern/draco/dracoenc/src/draco/core/draco_types.cc @@ -0,0 +1,44 @@ +// Copyright 2016 The Draco Authors. +// +// 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 "draco/core/draco_types.h" + +namespace draco { + +int32_t DataTypeLength(DataType dt) { + switch (dt) { + case DT_INT8: + case DT_UINT8: + return 1; + case DT_INT16: + case DT_UINT16: + return 2; + case DT_INT32: + case DT_UINT32: + return 4; + case DT_INT64: + case DT_UINT64: + return 8; + case DT_FLOAT32: + return 4; + case DT_FLOAT64: + return 8; + case DT_BOOL: + return 1; + default: + return -1; + } +} + +} // namespace draco diff --git a/extern/draco/dracoenc/src/draco/core/draco_types.h b/extern/draco/dracoenc/src/draco/core/draco_types.h new file mode 100644 index 00000000000..4a34d7045a3 --- /dev/null +++ b/extern/draco/dracoenc/src/draco/core/draco_types.h @@ -0,0 +1,46 @@ +// Copyright 2016 The Draco Authors. +// +// 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 DRACO_CORE_DRACO_TYPES_H_ +#define DRACO_CORE_DRACO_TYPES_H_ + +#include <stdint.h> +#include <string> + +#include "draco/draco_features.h" + +namespace draco { + +enum DataType { + // Not a legal value for DataType. Used to indicate a field has not been set. + DT_INVALID = 0, + DT_INT8, + DT_UINT8, + DT_INT16, + DT_UINT16, + DT_INT32, + DT_UINT32, + DT_INT64, + DT_UINT64, + DT_FLOAT32, + DT_FLOAT64, + DT_BOOL, + DT_TYPES_COUNT +}; + +int32_t DataTypeLength(DataType dt); + +} // namespace draco + +#endif // DRACO_CORE_DRACO_TYPES_H_ diff --git a/extern/draco/dracoenc/src/draco/core/draco_version.h b/extern/draco/dracoenc/src/draco/core/draco_version.h new file mode 100644 index 00000000000..45dce22a1d8 --- /dev/null +++ b/extern/draco/dracoenc/src/draco/core/draco_version.h @@ -0,0 +1,27 @@ +// Copyright 2016 The Draco Authors. +// +// 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 DRACO_CORE_DRACO_VERSION_H_ +#define DRACO_CORE_DRACO_VERSION_H_ + +namespace draco { + +// Draco version is comprised of <major>.<minor>.<revision>. +static const char kDracoVersion[] = "1.3.4"; + +const char *Version() { return kDracoVersion; } + +} // namespace draco + +#endif // DRACO_CORE_DRACO_VERSION_H_ diff --git a/extern/draco/dracoenc/src/draco/core/encoder_buffer.cc b/extern/draco/dracoenc/src/draco/core/encoder_buffer.cc new file mode 100644 index 00000000000..a5e936fd89b --- /dev/null +++ b/extern/draco/dracoenc/src/draco/core/encoder_buffer.cc @@ -0,0 +1,90 @@ +// Copyright 2016 The Draco Authors. +// +// 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 "draco/core/encoder_buffer.h" + +#include <cstring> // for memcpy + +#include "draco/core/varint_encoding.h" + +namespace draco { + +EncoderBuffer::EncoderBuffer() + : bit_encoder_reserved_bytes_(false), encode_bit_sequence_size_(false) {} + +void EncoderBuffer::Clear() { + buffer_.clear(); + bit_encoder_reserved_bytes_ = 0; +} + +void EncoderBuffer::Resize(int64_t nbytes) { buffer_.resize(nbytes); } + +bool EncoderBuffer::StartBitEncoding(int64_t required_bits, bool encode_size) { + if (bit_encoder_active()) + return false; // Bit encoding mode already active. + if (required_bits <= 0) + return false; // Invalid size. + encode_bit_sequence_size_ = encode_size; + const int64_t required_bytes = (required_bits + 7) / 8; + bit_encoder_reserved_bytes_ = required_bytes; + uint64_t buffer_start_size = buffer_.size(); + if (encode_size) { + // Reserve memory for storing the encoded bit sequence size. It will be + // filled once the bit encoding ends. + buffer_start_size += sizeof(uint64_t); + } + // Resize buffer to fit the maximum size of encoded bit data. + buffer_.resize(buffer_start_size + required_bytes); + // Get the buffer data pointer for the bit encoder. + const char *const data = buffer_.data() + buffer_start_size; + bit_encoder_ = + std::unique_ptr<BitEncoder>(new BitEncoder(const_cast<char *>(data))); + return true; +} + +void EncoderBuffer::EndBitEncoding() { + if (!bit_encoder_active()) + return; + // Get the number of encoded bits and bytes (rounded up). + const uint64_t encoded_bits = bit_encoder_->Bits(); + const uint64_t encoded_bytes = (encoded_bits + 7) / 8; + // Flush all cached bits that are not in the bit encoder's main buffer. + bit_encoder_->Flush(0); + // Encode size if needed. + if (encode_bit_sequence_size_) { + char *out_mem = const_cast<char *>(data() + size()); + // Make the out_mem point to the memory reserved for storing the size. + out_mem = out_mem - (bit_encoder_reserved_bytes_ + sizeof(uint64_t)); + + EncoderBuffer var_size_buffer; + EncodeVarint(encoded_bytes, &var_size_buffer); + const uint32_t size_len = static_cast<uint32_t>(var_size_buffer.size()); + char *const dst = out_mem + size_len; + const char *const src = out_mem + sizeof(uint64_t); + memmove(dst, src, encoded_bytes); + + // Store the size of the encoded data. + memcpy(out_mem, var_size_buffer.data(), size_len); + + // We need to account for the difference between the preallocated and actual + // storage needed for storing the encoded length. This will be used later to + // compute the correct size of |buffer_|. + bit_encoder_reserved_bytes_ += sizeof(uint64_t) - size_len; + } + // Resize the underlying buffer to match the number of encoded bits. + buffer_.resize(buffer_.size() - bit_encoder_reserved_bytes_ + encoded_bytes); + bit_encoder_reserved_bytes_ = 0; +} + +} // namespace draco diff --git a/extern/draco/dracoenc/src/draco/core/encoder_buffer.h b/extern/draco/dracoenc/src/draco/core/encoder_buffer.h new file mode 100644 index 00000000000..ff3e89ba270 --- /dev/null +++ b/extern/draco/dracoenc/src/draco/core/encoder_buffer.h @@ -0,0 +1,148 @@ +// Copyright 2016 The Draco Authors. +// +// 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 DRACO_CORE_ENCODER_BUFFER_H_ +#define DRACO_CORE_ENCODER_BUFFER_H_ + +#include <memory> +#include <vector> + +#include "draco/core/bit_utils.h" +#include "draco/core/macros.h" + +namespace draco { + +// Class representing a buffer that can be used for either for byte-aligned +// encoding of arbitrary data structures or for encoding of variable-length +// bit data. +class EncoderBuffer { + public: + EncoderBuffer(); + void Clear(); + void Resize(int64_t nbytes); + + // Start encoding a bit sequence. A maximum size of the sequence needs to + // be known upfront. + // If encode_size is true, the size of encoded bit sequence is stored before + // the sequence. Decoder can then use this size to skip over the bit sequence + // if needed. + // Returns false on error. + bool StartBitEncoding(int64_t required_bits, bool encode_size); + + // End the encoding of the bit sequence and return to the default byte-aligned + // encoding. + void EndBitEncoding(); + + // Encode up to 32 bits into the buffer. Can be called only in between + // StartBitEncoding and EndBitEncoding. Otherwise returns false. + bool EncodeLeastSignificantBits32(int nbits, uint32_t value) { + if (!bit_encoder_active()) + return false; + bit_encoder_->PutBits(value, nbits); + return true; + } + // Encode an arbitrary data type. + // Can be used only when we are not encoding a bit-sequence. + // Returns false when the value couldn't be encoded. + template <typename T> + bool Encode(const T &data) { + if (bit_encoder_active()) + return false; + const uint8_t *src_data = reinterpret_cast<const uint8_t *>(&data); + buffer_.insert(buffer_.end(), src_data, src_data + sizeof(T)); + return true; + } + bool Encode(const void *data, size_t data_size) { + if (bit_encoder_active()) + return false; + const uint8_t *src_data = reinterpret_cast<const uint8_t *>(data); + buffer_.insert(buffer_.end(), src_data, src_data + data_size); + return true; + } + + bool bit_encoder_active() const { return bit_encoder_reserved_bytes_ > 0; } + const char *data() const { return buffer_.data(); } + size_t size() const { return buffer_.size(); } + std::vector<char> *buffer() { return &buffer_; } + + private: + // Internal helper class to encode bits to a bit buffer. + class BitEncoder { + public: + // |data| is the buffer to write the bits into. + explicit BitEncoder(char *data) : bit_buffer_(data), bit_offset_(0) {} + + // Write |nbits| of |data| into the bit buffer. + void PutBits(uint32_t data, int32_t nbits) { + DRACO_DCHECK_GE(nbits, 0); + DRACO_DCHECK_LE(nbits, 32); + for (int32_t bit = 0; bit < nbits; ++bit) + PutBit((data >> bit) & 1); + } + + // Return number of bits encoded so far. + uint64_t Bits() const { return static_cast<uint64_t>(bit_offset_); } + + // TODO(fgalligan): Remove this function once we know we do not need the + // old API anymore. + // This is a function of an old API, that currently does nothing. + void Flush(int /* left_over_bit_value */) {} + + // Return the number of bits required to store the given number + static uint32_t BitsRequired(uint32_t x) { + return static_cast<uint32_t>(MostSignificantBit(x)); + } + + private: + void PutBit(uint8_t value) { + const int byte_size = 8; + const uint64_t off = static_cast<uint64_t>(bit_offset_); + const uint64_t byte_offset = off / byte_size; + const int bit_shift = off % byte_size; + + // TODO(fgalligan): Check performance if we add a branch and only do one + // memory write if bit_shift is 7. Also try using a temporary variable to + // hold the bits before writing to the buffer. + + bit_buffer_[byte_offset] &= ~(1 << bit_shift); + bit_buffer_[byte_offset] |= value << bit_shift; + bit_offset_++; + } + + char *bit_buffer_; + size_t bit_offset_; + }; + friend class BufferBitCodingTest; + // All data is stored in this vector. + std::vector<char> buffer_; + + // Bit encoder is used when encoding variable-length bit data. + // TODO(ostava): Currently encoder needs to be recreated each time + // StartBitEncoding method is called. This is not necessary if BitEncoder + // supported reset function which can easily added but let's leave that for + // later. + std::unique_ptr<BitEncoder> bit_encoder_; + + // The number of bytes reserved for bit encoder. + // Values > 0 indicate we are in the bit encoding mode. + int64_t bit_encoder_reserved_bytes_; + + // Flag used indicating that we need to store the length of the currently + // processed bit sequence. + bool encode_bit_sequence_size_; +}; + +} // namespace draco + +#endif // DRACO_CORE_ENCODER_BUFFER_H_ diff --git a/extern/draco/dracoenc/src/draco/core/hash_utils.cc b/extern/draco/dracoenc/src/draco/core/hash_utils.cc new file mode 100644 index 00000000000..9a78c2cfafd --- /dev/null +++ b/extern/draco/dracoenc/src/draco/core/hash_utils.cc @@ -0,0 +1,57 @@ +// Copyright 2016 The Draco Authors. +// +// 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 "draco/core/hash_utils.h" + +#include <cstddef> +#include <functional> +#include <limits> + +namespace draco { + +// Will never return 1 or 0. +uint64_t FingerprintString(const char *s, size_t len) { + const uint64_t seed = 0x87654321; + const int hash_loop_count = static_cast<int>(len / 8) + 1; + uint64_t hash = seed; + + for (int i = 0; i < hash_loop_count; ++i) { + const int off = i * 8; + const int num_chars_left = static_cast<int>(len) - off; + uint64_t new_hash = seed; + + if (num_chars_left > 7) { + const int off2 = i * 8; + new_hash = static_cast<uint64_t>(s[off2]) << 56 | + static_cast<uint64_t>(s[off2 + 1]) << 48 | + static_cast<uint64_t>(s[off2 + 2]) << 40 | + static_cast<uint64_t>(s[off2 + 3]) << 32 | + static_cast<uint64_t>(s[off2 + 4]) << 24 | + static_cast<uint64_t>(s[off2 + 5]) << 16 | + static_cast<uint64_t>(s[off2 + 6]) << 8 | s[off2 + 7]; + } else { + for (int j = 0; j < num_chars_left; ++j) { + new_hash |= static_cast<uint64_t>(s[off + j]) + << (64 - ((num_chars_left - j) * 8)); + } + } + + hash = HashCombine(new_hash, hash); + } + + if (hash < std::numeric_limits<uint64_t>::max() - 1) + hash += 2; + return hash; +} +} // namespace draco diff --git a/extern/draco/dracoenc/src/draco/core/hash_utils.h b/extern/draco/dracoenc/src/draco/core/hash_utils.h new file mode 100644 index 00000000000..0e8da60aa54 --- /dev/null +++ b/extern/draco/dracoenc/src/draco/core/hash_utils.h @@ -0,0 +1,64 @@ +// Copyright 2016 The Draco Authors. +// +// 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 DRACO_CORE_HASH_UTILS_H_ +#define DRACO_CORE_HASH_UTILS_H_ + +#include <stdint.h> +#include <functional> + +// TODO(fgalligan): Move this to core. + +namespace draco { + +template <typename T1, typename T2> +size_t HashCombine(T1 a, T2 b) { + const size_t hash1 = std::hash<T1>()(a); + const size_t hash2 = std::hash<T2>()(b); + return (hash1 << 2) ^ (hash2 << 1); +} + +template <typename T> +size_t HashCombine(T a, size_t hash) { + const size_t hasha = std::hash<T>()(a); + return (hash) ^ (hasha + 239); +} + +inline uint64_t HashCombine(uint64_t a, uint64_t b) { + return (a + 1013) ^ (b + 107) << 1; +} + +// Will never return 1 or 0. +uint64_t FingerprintString(const char *s, size_t len); + +// Hash for std::array. +template <typename T> +struct HashArray { + size_t operator()(const T &a) const { + size_t hash = 79; // Magic number. + for (unsigned int i = 0; i < std::tuple_size<T>::value; ++i) { + hash = HashCombine(hash, ValueHash(a[i])); + } + return hash; + } + + template <typename V> + size_t ValueHash(const V &val) const { + return std::hash<V>()(val); + } +}; + +} // namespace draco + +#endif // DRACO_CORE_HASH_UTILS_H_ diff --git a/extern/draco/dracoenc/src/draco/core/macros.h b/extern/draco/dracoenc/src/draco/core/macros.h new file mode 100644 index 00000000000..e968cbb330b --- /dev/null +++ b/extern/draco/dracoenc/src/draco/core/macros.h @@ -0,0 +1,96 @@ +// Copyright 2016 The Draco Authors. +// +// 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 DRACO_CORE_MACROS_H_ +#define DRACO_CORE_MACROS_H_ + +#include "assert.h" + +#include "draco/draco_features.h" + +#ifdef ANDROID_LOGGING +#include <android/log.h> +#define LOG_TAG "draco" +#define LOGI(...) __android_log_print(ANDROID_LOG_INFO, LOG_TAG, __VA_ARGS__) +#define LOGE(...) __android_log_print(ANDROID_LOG_ERROR, LOG_TAG, __VA_ARGS__) +#else +#define LOGI printf +#define LOGE printf +#endif + +#include <iostream> +namespace draco { + +#define DISALLOW_COPY_AND_ASSIGN(TypeName) \ + TypeName(const TypeName &) = delete; \ + void operator=(const TypeName &) = delete; + +#ifndef FALLTHROUGH_INTENDED +#define FALLTHROUGH_INTENDED void(0); +#endif + +#ifndef LOG +#define LOG(...) std::cout +#endif + +#ifndef VLOG +#define VLOG(...) std::cout +#endif + +} // namespace draco + +#ifdef DRACO_DEBUG +#define DRACO_DCHECK(x) (assert(x)); +#define DRACO_DCHECK_EQ(a, b) assert((a) == (b)); +#define DRACO_DCHECK_NE(a, b) assert((a) != (b)); +#define DRACO_DCHECK_GE(a, b) assert((a) >= (b)); +#define DRACO_DCHECK_GT(a, b) assert((a) > (b)); +#define DRACO_DCHECK_LE(a, b) assert((a) <= (b)); +#define DRACO_DCHECK_LT(a, b) assert((a) < (b)); +#define DRACO_DCHECK_NOTNULL(x) assert((x) != NULL); +#else +#define DRACO_DCHECK(x) +#define DRACO_DCHECK_EQ(a, b) +#define DRACO_DCHECK_NE(a, b) +#define DRACO_DCHECK_GE(a, b) +#define DRACO_DCHECK_GT(a, b) +#define DRACO_DCHECK_LE(a, b) +#define DRACO_DCHECK_LT(a, b) +#define DRACO_DCHECK_NOTNULL(x) +#endif + +// Helper macros for concatenating macro values. +#define DRACO_MACROS_IMPL_CONCAT_INNER_(x, y) x##y +#define DRACO_MACROS_IMPL_CONCAT_(x, y) DRACO_MACROS_IMPL_CONCAT_INNER_(x, y) + +// Expand the n-th argument of the macro. Used to select an argument based on +// the number of entries in a variadic macro argument. Example usage: +// +// #define FUNC_1(x) x +// #define FUNC_2(x, y) x + y +// #define FUNC_3(x, y, z) x + y + z +// +// #define VARIADIC_MACRO(...) +// DRACO_SELECT_NTH_FROM_3(__VA_ARGS__, FUNC_3, FUNC_2, FUNC_1) __VA_ARGS__ +// +#define DRACO_SELECT_NTH_FROM_2(_1, _2, NAME) NAME +#define DRACO_SELECT_NTH_FROM_3(_1, _2, _3, NAME) NAME +#define DRACO_SELECT_NTH_FROM_4(_1, _2, _3, _4, NAME) NAME + +// Macro that converts the Draco bit-stream into one uint16_t number. +// Useful mostly when checking version numbers. +#define DRACO_BITSTREAM_VERSION(MAJOR, MINOR) \ + ((static_cast<uint16_t>(MAJOR) << 8) | MINOR) + +#endif // DRACO_CORE_MACROS_H_ diff --git a/extern/draco/dracoenc/src/draco/core/math_utils.h b/extern/draco/dracoenc/src/draco/core/math_utils.h new file mode 100644 index 00000000000..6bf237d4560 --- /dev/null +++ b/extern/draco/dracoenc/src/draco/core/math_utils.h @@ -0,0 +1,52 @@ +// Copyright 2016 The Draco Authors. +// +// 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 DRACO_CORE_MATH_UTILS_H_ +#define DRACO_CORE_MATH_UTILS_H_ + +#include <inttypes.h> + +#define DRACO_INCREMENT_MOD(I, M) (((I) == ((M)-1)) ? 0 : ((I) + 1)) + +// Returns floor(sqrt(x)) where x is an integer number. The main intend of this +// function is to provide a cross platform and deterministic implementation of +// square root for integer numbers. This function is not intended to be a +// replacement for std::sqrt() for general cases. IntSqrt is in fact about 3X +// slower compared to most implementation of std::sqrt(). +inline uint64_t IntSqrt(uint64_t number) { + if (number == 0) + return 0; + // First estimate good initial value of the square root as log2(number). + uint64_t act_number = number; + uint64_t square_root = 1; + while (act_number >= 2) { + // Double the square root until |square_root * square_root > number|. + square_root *= 2; + act_number /= 4; + } + // Perform Newton's (or Babylonian) method to find the true floor(sqrt()). + do { + // New |square_root| estimate is computed as the average between + // |square_root| and |number / square_root|. + square_root = (square_root + number / square_root) / 2; + + // Note that after the first iteration, the estimate is always going to be + // larger or equal to the true square root value. Therefore to check + // convergence, we can simply detect condition when the square of the + // estimated square root is larger than the input. + } while (square_root * square_root > number); + return square_root; +} + +#endif // DRACO_CORE_MATH_UTILS_H_ diff --git a/extern/draco/dracoenc/src/draco/core/math_utils_test.cc b/extern/draco/dracoenc/src/draco/core/math_utils_test.cc new file mode 100644 index 00000000000..b12b3431e66 --- /dev/null +++ b/extern/draco/dracoenc/src/draco/core/math_utils_test.cc @@ -0,0 +1,19 @@ +#include "draco/core/math_utils.h" + +#include <random> + +#include "draco/core/draco_test_base.h" + +TEST(MathUtils, Mod) { EXPECT_EQ(DRACO_INCREMENT_MOD(1, 1 << 1), 0); } + +TEST(MathUtils, IntSqrt) { + ASSERT_EQ(IntSqrt(0), 0); + // 64-bit pseudo random number generator seeded with a predefined number. + std::mt19937_64 generator(109); + std::uniform_int_distribution<uint64_t> distribution(0, 1ull << 60); + + for (int i = 0; i < 10000; ++i) { + const uint64_t number = distribution(generator); + ASSERT_EQ(IntSqrt(number), static_cast<uint64_t>(floor(std::sqrt(number)))); + } +} diff --git a/extern/draco/dracoenc/src/draco/core/options.cc b/extern/draco/dracoenc/src/draco/core/options.cc new file mode 100644 index 00000000000..c4f6d6a66aa --- /dev/null +++ b/extern/draco/dracoenc/src/draco/core/options.cc @@ -0,0 +1,83 @@ +// Copyright 2016 The Draco Authors. +// +// 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 "draco/core/options.h" + +#include <cstdlib> +#include <string> + +namespace draco { + +Options::Options() {} + +void Options::SetInt(const std::string &name, int val) { + options_[name] = std::to_string(val); +} + +void Options::SetFloat(const std::string &name, float val) { + options_[name] = std::to_string(val); +} + +void Options::SetBool(const std::string &name, bool val) { + options_[name] = std::to_string(val ? 1 : 0); +} + +void Options::SetString(const std::string &name, const std::string &val) { + options_[name] = val; +} + +int Options::GetInt(const std::string &name) const { return GetInt(name, -1); } + +int Options::GetInt(const std::string &name, int default_val) const { + const auto it = options_.find(name); + if (it == options_.end()) + return default_val; + return std::atoi(it->second.c_str()); +} + +float Options::GetFloat(const std::string &name) const { + return GetFloat(name, -1); +} + +float Options::GetFloat(const std::string &name, float default_val) const { + const auto it = options_.find(name); + if (it == options_.end()) + return default_val; + return static_cast<float>(std::atof(it->second.c_str())); +} + +bool Options::GetBool(const std::string &name) const { + return GetBool(name, false); +} + +bool Options::GetBool(const std::string &name, bool default_val) const { + const int ret = GetInt(name, -1); + if (ret == -1) + return default_val; + return static_cast<bool>(ret); +} + +std::string Options::GetString(const std::string &name) const { + return GetString(name, ""); +} + +std::string Options::GetString(const std::string &name, + const std::string &default_val) const { + const auto it = options_.find(name); + if (it == options_.end()) + return default_val; + return it->second; +} + +} // namespace draco diff --git a/extern/draco/dracoenc/src/draco/core/options.h b/extern/draco/dracoenc/src/draco/core/options.h new file mode 100644 index 00000000000..0e69844911d --- /dev/null +++ b/extern/draco/dracoenc/src/draco/core/options.h @@ -0,0 +1,140 @@ +// Copyright 2016 The Draco Authors. +// +// 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 DRACO_CORE_OPTIONS_H_ +#define DRACO_CORE_OPTIONS_H_ + +#include <cstdlib> +#include <map> +#include <string> + +namespace draco { + +// Class for storing generic options as a <name, value> pair in a string map. +// The API provides helper methods for directly storing values of various types +// such as ints and bools. One named option should be set with only a single +// data type. +class Options { + public: + Options(); + void SetInt(const std::string &name, int val); + void SetFloat(const std::string &name, float val); + void SetBool(const std::string &name, bool val); + void SetString(const std::string &name, const std::string &val); + template <class VectorT> + void SetVector(const std::string &name, const VectorT &vec) { + SetVector(name, &vec[0], VectorT::dimension); + } + template <typename DataTypeT> + void SetVector(const std::string &name, const DataTypeT *vec, int num_dims); + + // Getters will return a default value if the entry is not found. The default + // value can be specified in the overloaded version of each function. + int GetInt(const std::string &name) const; + int GetInt(const std::string &name, int default_val) const; + float GetFloat(const std::string &name) const; + float GetFloat(const std::string &name, float default_val) const; + bool GetBool(const std::string &name) const; + bool GetBool(const std::string &name, bool default_val) const; + std::string GetString(const std::string &name) const; + std::string GetString(const std::string &name, + const std::string &default_val) const; + template <class VectorT> + VectorT GetVector(const std::string &name, const VectorT &default_val) const; + // Unlike other Get functions, this function returns false if the option does + // not exist, otherwise it fills |out_val| with the vector values. If a + // default value is needed, it can be set in |out_val|. + template <typename DataTypeT> + bool GetVector(const std::string &name, int num_dims, + DataTypeT *out_val) const; + + bool IsOptionSet(const std::string &name) const { + return options_.count(name) > 0; + } + + private: + // All entries are internally stored as strings and converted to the desired + // return type based on the used Get* method. + // TODO(ostava): Consider adding type safety mechanism that would prevent + // unsafe operations such as a conversion from vector to int. + std::map<std::string, std::string> options_; +}; + +template <typename DataTypeT> +void Options::SetVector(const std::string &name, const DataTypeT *vec, + int num_dims) { + std::string out; + for (int i = 0; i < num_dims; ++i) { + if (i > 0) + out += " "; + +// GNU STL on android doesn't include a proper std::to_string, but the libc++ +// version does +#if defined(ANDROID) && !defined(_LIBCPP_VERSION) + out += to_string(vec[i]); +#else + out += std::to_string(vec[i]); +#endif + } + options_[name] = out; +} + +template <class VectorT> +VectorT Options::GetVector(const std::string &name, + const VectorT &default_val) const { + VectorT ret = default_val; + GetVector(name, VectorT::dimension, &ret[0]); + return ret; +} + +template <typename DataTypeT> +bool Options::GetVector(const std::string &name, int num_dims, + DataTypeT *out_val) const { + const auto it = options_.find(name); + if (it == options_.end()) + return false; + const std::string value = it->second; + if (value.length() == 0) + return true; // Option set but no data is present + const char *act_str = value.c_str(); + char *next_str; + for (int i = 0; i < num_dims; ++i) { + if (std::is_integral<DataTypeT>::value) { +#ifdef ANDROID + const int val = strtol(act_str, &next_str, 10); +#else + const int val = std::strtol(act_str, &next_str, 10); +#endif + if (act_str == next_str) + return true; // End reached. + act_str = next_str; + out_val[i] = static_cast<DataTypeT>(val); + } else { +#ifdef ANDROID + const float val = strtof(act_str, &next_str); +#else + const float val = std::strtof(act_str, &next_str); +#endif + if (act_str == next_str) + return true; // End reached. + act_str = next_str; + out_val[i] = static_cast<DataTypeT>(val); + } + } + return true; +} + +} // namespace draco + +#endif // DRACO_CORE_OPTIONS_H_ diff --git a/extern/draco/dracoenc/src/draco/core/quantization_utils.cc b/extern/draco/dracoenc/src/draco/core/quantization_utils.cc new file mode 100644 index 00000000000..26417b01998 --- /dev/null +++ b/extern/draco/dracoenc/src/draco/core/quantization_utils.cc @@ -0,0 +1,41 @@ +// Copyright 2016 The Draco Authors. +// +// 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 "draco/core/quantization_utils.h" + +namespace draco { + +Quantizer::Quantizer() : inverse_delta_(1.f) {} + +void Quantizer::Init(float range, int32_t max_quantized_value) { + inverse_delta_ = static_cast<float>(max_quantized_value) / range; +} + +void Quantizer::Init(float delta) { inverse_delta_ = 1.f / delta; } + +Dequantizer::Dequantizer() : delta_(1.f) {} + +bool Dequantizer::Init(float range, int32_t max_quantized_value) { + if (max_quantized_value <= 0) + return false; + delta_ = range / static_cast<float>(max_quantized_value); + return true; +} + +bool Dequantizer::Init(float delta) { + delta_ = delta; + return true; +} + +} // namespace draco diff --git a/extern/draco/dracoenc/src/draco/core/quantization_utils.h b/extern/draco/dracoenc/src/draco/core/quantization_utils.h new file mode 100644 index 00000000000..54910467407 --- /dev/null +++ b/extern/draco/dracoenc/src/draco/core/quantization_utils.h @@ -0,0 +1,81 @@ +// Copyright 2016 The Draco Authors. +// +// 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. +// +// A set of classes for quantizing and dequantizing of floating point values +// into integers. +// The quantization works on all floating point numbers within (-range, +range) +// interval producing integers in range +// (-max_quantized_value, +max_quantized_value). + +#ifndef DRACO_CORE_QUANTIZATION_UTILS_H_ +#define DRACO_CORE_QUANTIZATION_UTILS_H_ + +#include <stdint.h> +#include <cmath> + +#include "draco/core/macros.h" + +namespace draco { + +// Class for quantizing single precision floating point values. The values +// should be centered around zero and be within interval (-range, +range), where +// the range is specified in the Init() method. Alternatively, the quantization +// can be defined by |delta| that specifies the distance between two quantized +// values. Note that the quantizer always snaps the values to the nearest +// integer value. E.g. for |delta| == 1.f, values -0.4f and 0.4f would be +// both quantized to 0 while value 0.6f would be quantized to 1. If a value +// lies exactly between two quantized states, it is always rounded up. E.g., +// for |delta| == 1.f, value -0.5f would be quantized to 0 while 0.5f would be +// quantized to 1. +class Quantizer { + public: + Quantizer(); + void Init(float range, int32_t max_quantized_value); + void Init(float delta); + inline int32_t QuantizeFloat(float val) const { + val *= inverse_delta_; + return static_cast<int32_t>(floor(val + 0.5f)); + } + inline int32_t operator()(float val) const { return QuantizeFloat(val); } + + private: + float inverse_delta_; +}; + +// Class for dequantizing values that were previously quantized using the +// Quantizer class. +class Dequantizer { + public: + Dequantizer(); + + // Initializes the dequantizer. Both parameters must correspond to the values + // provided to the initializer of the Quantizer class. + // Returns false when the initialization fails. + bool Init(float range, int32_t max_quantized_value); + + // Initializes the dequantizer using the |delta| between two quantized values. + bool Init(float delta); + + inline float DequantizeFloat(int32_t val) const { + return static_cast<float>(val) * delta_; + } + inline float operator()(int32_t val) const { return DequantizeFloat(val); } + + private: + float delta_; +}; + +} // namespace draco + +#endif // DRACO_CORE_QUANTIZATION_UTILS_H_ diff --git a/extern/draco/dracoenc/src/draco/core/quantization_utils_test.cc b/extern/draco/dracoenc/src/draco/core/quantization_utils_test.cc new file mode 100644 index 00000000000..b4f0473f204 --- /dev/null +++ b/extern/draco/dracoenc/src/draco/core/quantization_utils_test.cc @@ -0,0 +1,91 @@ +// Copyright 2016 The Draco Authors. +// +// 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 "draco/core/quantization_utils.h" + +#include "draco/core/draco_test_base.h" + +namespace draco { + +class QuantizationUtilsTest : public ::testing::Test {}; + +TEST_F(QuantizationUtilsTest, TestQuantizer) { + Quantizer quantizer; + quantizer.Init(10.f, 255); + EXPECT_EQ(quantizer.QuantizeFloat(0.f), 0); + EXPECT_EQ(quantizer.QuantizeFloat(10.f), 255); + EXPECT_EQ(quantizer.QuantizeFloat(-10.f), -255); + EXPECT_EQ(quantizer.QuantizeFloat(4.999f), 127); + EXPECT_EQ(quantizer.QuantizeFloat(5.f), 128); + EXPECT_EQ(quantizer.QuantizeFloat(-4.9999f), -127); + // Note: Both -5.f and +5.f lie exactly on the boundary between two + // quantized values (127.5f and -127.5f). Due to rounding, both values are + // then converted to 128 and -127 respectively. + EXPECT_EQ(quantizer.QuantizeFloat(-5.f), -127); + EXPECT_EQ(quantizer.QuantizeFloat(-5.0001f), -128); + + // Out of range quantization. + // The behavior is technically undefined, but both quantizer and dequantizer + // should still work correctly unless the quantized values overflow. + EXPECT_LT(quantizer.QuantizeFloat(-15.f), -255); + EXPECT_GT(quantizer.QuantizeFloat(15.f), 255); +} + +TEST_F(QuantizationUtilsTest, TestDequantizer) { + Dequantizer dequantizer; + ASSERT_TRUE(dequantizer.Init(10.f, 255)); + EXPECT_EQ(dequantizer.DequantizeFloat(0), 0.f); + EXPECT_EQ(dequantizer.DequantizeFloat(255), 10.f); + EXPECT_EQ(dequantizer.DequantizeFloat(-255), -10.f); + EXPECT_EQ(dequantizer.DequantizeFloat(128), 10.f * (128.f / 255.f)); + + // Test that the dequantizer fails to initialize with invalid input + // parameters. + ASSERT_FALSE(dequantizer.Init(1.f, 0)); + ASSERT_FALSE(dequantizer.Init(1.f, -4)); +} + +TEST_F(QuantizationUtilsTest, TestDeltaQuantization) { + // Test verifies that the quantizer and dequantizer work correctly when + // initialized with a delta value. + Quantizer quantizer_delta; + quantizer_delta.Init(0.5f); + + Quantizer quantizer_range; + quantizer_range.Init(50.f, 100); + + EXPECT_EQ(quantizer_delta.QuantizeFloat(1.2f), 2); + EXPECT_EQ(quantizer_delta.QuantizeFloat(10.f), + quantizer_range.QuantizeFloat(10.f)); + EXPECT_EQ(quantizer_delta.QuantizeFloat(-3.3f), + quantizer_range.QuantizeFloat(-3.3f)); + EXPECT_EQ(quantizer_delta.QuantizeFloat(0.25f), + quantizer_range.QuantizeFloat(0.25f)); + + Dequantizer dequantizer_delta; + dequantizer_delta.Init(0.5f); + + Dequantizer dequantizer_range; + dequantizer_range.Init(50.f, 100); + + EXPECT_EQ(dequantizer_delta.DequantizeFloat(2), 1.f); + EXPECT_EQ(dequantizer_delta.DequantizeFloat(-4), + dequantizer_range.DequantizeFloat(-4)); + EXPECT_EQ(dequantizer_delta.DequantizeFloat(9), + dequantizer_range.DequantizeFloat(9)); + EXPECT_EQ(dequantizer_delta.DequantizeFloat(0), + dequantizer_range.DequantizeFloat(0)); +} + +} // namespace draco diff --git a/extern/draco/dracoenc/src/draco/core/status.h b/extern/draco/dracoenc/src/draco/core/status.h new file mode 100644 index 00000000000..0a483f09369 --- /dev/null +++ b/extern/draco/dracoenc/src/draco/core/status.h @@ -0,0 +1,75 @@ +// Copyright 2017 The Draco Authors. +// +// 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 DRACO_CORE_STATUS_H_ +#define DRACO_CORE_STATUS_H_ + +#include <string> + +namespace draco { + +// Class encapsulating a return status of an operation with an optional error +// message. Intended to be used as a return type for functions instead of bool. +class Status { + public: + enum Code { + OK = 0, + ERROR = -1, // Used for general errors. + IO_ERROR = -2, // Error when handling input or output stream. + INVALID_PARAMETER = -3, // Invalid parameter passed to a function. + UNSUPPORTED_VERSION = -4, // Input not compatible with the current version. + UNKNOWN_VERSION = -5, // Input was created with an unknown version of + // the library. + }; + + Status() : code_(OK) {} + Status(const Status &status) = default; + Status(Status &&status) = default; + explicit Status(Code code) : code_(code) {} + Status(Code code, const std::string &error_msg) + : code_(code), error_msg_(error_msg) {} + + Code code() const { return code_; } + const std::string &error_msg_string() const { return error_msg_; } + const char *error_msg() const { return error_msg_.c_str(); } + + bool operator==(Code code) const { return code == code_; } + bool ok() const { return code_ == OK; } + + Status &operator=(const Status &) = default; + + private: + Code code_; + std::string error_msg_; +}; + +inline std::ostream &operator<<(std::ostream &os, const Status &status) { + os << status.error_msg_string(); + return os; +} + +inline Status OkStatus() { return Status(Status::OK); } + +// Evaluates an expression that returns draco::Status. If the status is not OK, +// the macro returns the status object. +#define DRACO_RETURN_IF_ERROR(expression) \ + { \ + const draco::Status _local_status = (expression); \ + if (!_local_status.ok()) \ + return _local_status; \ + } + +} // namespace draco + +#endif // DRACO_CORE_STATUS_H_ diff --git a/extern/draco/dracoenc/src/draco/core/status_test.cc b/extern/draco/dracoenc/src/draco/core/status_test.cc new file mode 100644 index 00000000000..451ebe2bfab --- /dev/null +++ b/extern/draco/dracoenc/src/draco/core/status_test.cc @@ -0,0 +1,38 @@ +// Copyright 2017 The Draco Authors. +// +// 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 "draco/core/status.h" + +#include <sstream> + +#include "draco/core/draco_test_base.h" + +namespace { + +class StatusTest : public ::testing::Test { + protected: + StatusTest() {} +}; + +TEST_F(StatusTest, TestStatusOutput) { + // Tests that the Status can be stored in a provided std::ostream. + const draco::Status status(draco::Status::ERROR, "Error msg."); + ASSERT_EQ(status.code(), draco::Status::ERROR); + + std::stringstream str; + str << status; + ASSERT_EQ(str.str(), "Error msg."); +} + +} // namespace diff --git a/extern/draco/dracoenc/src/draco/core/statusor.h b/extern/draco/dracoenc/src/draco/core/statusor.h new file mode 100644 index 00000000000..7fa42098442 --- /dev/null +++ b/extern/draco/dracoenc/src/draco/core/statusor.h @@ -0,0 +1,81 @@ +// Copyright 2017 The Draco Authors. +// +// 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 DRACO_CORE_STATUSOR_H_ +#define DRACO_CORE_STATUSOR_H_ + +#include "draco/core/macros.h" +#include "draco/core/status.h" + +namespace draco { + +// Class StatusOr is used to wrap a Status along with a value of a specified +// type |T|. StatusOr is intended to be returned from functions in situations +// where it is desirable to carry over more information about the potential +// errors encountered during the function execution. If there are not errors, +// the caller can simply use the return value, otherwise the Status object +// provides more info about the encountered problem. +template <class T> +class StatusOr { + public: + StatusOr() {} + // Note: Constructors are intentionally not explicit to allow returning + // Status or the return value directly from functions. + StatusOr(const StatusOr &) = default; + StatusOr(StatusOr &&) = default; + StatusOr(const Status &status) : status_(status) {} + StatusOr(const T &value) : status_(OkStatus()), value_(value) {} + StatusOr(T &&value) : status_(OkStatus()), value_(std::move(value)) {} + StatusOr(const Status &status, const T &value) + : status_(status), value_(value) {} + + const Status &status() const { return status_; } + const T &value() const & { return value_; } + const T &&value() const && { return std::move(value_); } + T &&value() && { return std::move(value_); } + + // For consistency with existing Google StatusOr API we also include + // ValueOrDie() that currently returns the value(). + const T &ValueOrDie() const & { return value(); } + T &&ValueOrDie() && { return std::move(value()); } + + bool ok() const { return status_.ok(); } + + private: + Status status_; + T value_; +}; + +// In case StatusOr<T> is ok(), this macro assigns value stored in StatusOr<T> +// to |lhs|, otherwise it returns the error Status. +// +// DRACO_ASSIGN_OR_RETURN(lhs, expression) +// +#define DRACO_ASSIGN_OR_RETURN(lhs, expression) \ + DRACO_ASSIGN_OR_RETURN_IMPL_(DRACO_MACROS_IMPL_CONCAT_(_statusor, __LINE__), \ + lhs, expression, _status) + +// The actual implementation of the above macro. +#define DRACO_ASSIGN_OR_RETURN_IMPL_(statusor, lhs, expression, error_expr) \ + auto statusor = (expression); \ + if (!statusor.ok()) { \ + auto _status = std::move(statusor.status()); \ + (void)_status; /* error_expression may not use it */ \ + return error_expr; \ + } \ + lhs = std::move(statusor).value(); + +} // namespace draco + +#endif // DRACO_CORE_STATUSOR_H_ diff --git a/extern/draco/dracoenc/src/draco/core/varint_decoding.h b/extern/draco/dracoenc/src/draco/core/varint_decoding.h new file mode 100644 index 00000000000..6cd41b29220 --- /dev/null +++ b/extern/draco/dracoenc/src/draco/core/varint_decoding.h @@ -0,0 +1,59 @@ +// Copyright 2016 The Draco Authors. +// +// 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 DRACO_CORE_VARINT_DECODING_H_ +#define DRACO_CORE_VARINT_DECODING_H_ + +#include <type_traits> + +#include "draco/core/bit_utils.h" +#include "draco/core/decoder_buffer.h" + +namespace draco { + +// Decodes a specified integer as varint. Note that the IntTypeT must be the +// same as the one used in the corresponding EncodeVarint() call. +template <typename IntTypeT> +bool DecodeVarint(IntTypeT *out_val, DecoderBuffer *buffer) { + if (std::is_unsigned<IntTypeT>::value) { + // Coding of unsigned values. + // 0-6 bit - data + // 7 bit - next byte? + uint8_t in; + if (!buffer->Decode(&in)) + return false; + if (in & (1 << 7)) { + // Next byte is available, decode it first. + if (!DecodeVarint<IntTypeT>(out_val, buffer)) + return false; + // Append decoded info from this byte. + *out_val <<= 7; + *out_val |= in & ((1 << 7) - 1); + } else { + // Last byte reached + *out_val = in; + } + } else { + // IntTypeT is a signed value. Decode the symbol and convert to signed. + typename std::make_unsigned<IntTypeT>::type symbol; + if (!DecodeVarint(&symbol, buffer)) + return false; + *out_val = ConvertSymbolToSignedInt(symbol); + } + return true; +} + +} // namespace draco + +#endif // DRACO_CORE_VARINT_DECODING_H_ diff --git a/extern/draco/dracoenc/src/draco/core/varint_encoding.h b/extern/draco/dracoenc/src/draco/core/varint_encoding.h new file mode 100644 index 00000000000..b9b6dcab78d --- /dev/null +++ b/extern/draco/dracoenc/src/draco/core/varint_encoding.h @@ -0,0 +1,57 @@ +// Copyright 2016 The Draco Authors. +// +// 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 DRACO_CORE_VARINT_ENCODING_H_ +#define DRACO_CORE_VARINT_ENCODING_H_ + +#include <type_traits> + +#include "draco/core/bit_utils.h" +#include "draco/core/encoder_buffer.h" + +namespace draco { + +// Encodes a specified integer as varint. Note that different coding is used +// when IntTypeT is an unsigned data type. +template <typename IntTypeT> +bool EncodeVarint(IntTypeT val, EncoderBuffer *out_buffer) { + if (std::is_unsigned<IntTypeT>::value) { + // Coding of unsigned values. + // 0-6 bit - data + // 7 bit - next byte? + uint8_t out = 0; + out |= val & ((1 << 7) - 1); + if (val >= (1 << 7)) { + out |= (1 << 7); + if (!out_buffer->Encode(out)) + return false; + if (!EncodeVarint<IntTypeT>(val >> 7, out_buffer)) + return false; + return true; + } + if (!out_buffer->Encode(out)) + return false; + } else { + // IntTypeT is a signed value. Convert to unsigned symbol and encode. + const typename std::make_unsigned<IntTypeT>::type symbol = + ConvertSignedIntToSymbol(val); + if (!EncodeVarint(symbol, out_buffer)) + return false; + } + return true; +} + +} // namespace draco + +#endif // DRACO_CORE_VARINT_ENCODING_H_ diff --git a/extern/draco/dracoenc/src/draco/core/vector_d.h b/extern/draco/dracoenc/src/draco/core/vector_d.h new file mode 100644 index 00000000000..57dcd102663 --- /dev/null +++ b/extern/draco/dracoenc/src/draco/core/vector_d.h @@ -0,0 +1,260 @@ +// Copyright 2016 The Draco Authors. +// +// 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 DRACO_CORE_VECTOR_D_H_ +#define DRACO_CORE_VECTOR_D_H_ + +#include <inttypes.h> +#include <algorithm> +#include <array> +#include <cmath> + +#include "draco/core/macros.h" + +namespace draco { +// D-dimensional vector class with basic operations. +template <class CoeffT, int dimension_t> +class VectorD { + public: + typedef VectorD<CoeffT, dimension_t> Self; + typedef CoeffT CoefficientType; + static constexpr int dimension = dimension_t; + + VectorD() { + for (int i = 0; i < dimension_t; ++i) + (*this)[i] = CoeffT(0); + } + + // The following constructor does not compile in opt mode, which for now led + // to the constructors further down, which is not ideal. + // TODO(hemmer): fix constructor below and remove others. + // template <typename... Args> + // explicit VectorD(Args... args) : v_({args...}) {} + + VectorD(const CoeffT &c0, const CoeffT &c1) : v_({{c0, c1}}) { + DRACO_DCHECK_EQ(dimension_t, 2); + v_[0] = c0; + v_[1] = c1; + } + + VectorD(const CoeffT &c0, const CoeffT &c1, const CoeffT &c2) + : v_({{c0, c1, c2}}) { + DRACO_DCHECK_EQ(dimension_t, 3); + } + + VectorD(const CoeffT &c0, const CoeffT &c1, const CoeffT &c2, + const CoeffT &c3) + : v_({{c0, c1, c2, c3}}) { + DRACO_DCHECK_EQ(dimension_t, 4); + } + + VectorD(const CoeffT &c0, const CoeffT &c1, const CoeffT &c2, + const CoeffT &c3, const CoeffT &c4) + : v_({{c0, c1, c2, c3, c4}}) { + DRACO_DCHECK_EQ(dimension_t, 5); + } + + VectorD(const CoeffT &c0, const CoeffT &c1, const CoeffT &c2, + const CoeffT &c3, const CoeffT &c4, const CoeffT &c5) + : v_({{c0, c1, c2, c3, c4, c5}}) { + DRACO_DCHECK_EQ(dimension_t, 6); + } + + VectorD(const CoeffT &c0, const CoeffT &c1, const CoeffT &c2, + const CoeffT &c3, const CoeffT &c4, const CoeffT &c5, + const CoeffT &c6) + : v_({{c0, c1, c2, c3, c4, c5, c6}}) { + DRACO_DCHECK_EQ(dimension_t, 7); + } + + VectorD(const Self &o) { + for (int i = 0; i < dimension_t; ++i) + (*this)[i] = o[i]; + } + + CoeffT &operator[](int i) { return v_[i]; } + const CoeffT &operator[](int i) const { return v_[i]; } + // TODO(hemmer): remove. + // Similar to interface of Eigen library. + CoeffT &operator()(int i) { return v_[i]; } + const CoeffT &operator()(int i) const { return v_[i]; } + + // Unary operators. + Self operator-() const { + Self ret; + for (int i = 0; i < dimension_t; ++i) { + ret[i] = -(*this)[i]; + } + return ret; + } + + // Binary operators. + Self operator+(const Self &o) const { + Self ret; + for (int i = 0; i < dimension_t; ++i) { + ret[i] = (*this)[i] + o[i]; + } + return ret; + } + + Self operator-(const Self &o) const { + Self ret; + for (int i = 0; i < dimension_t; ++i) { + ret[i] = (*this)[i] - o[i]; + } + return ret; + } + + Self operator*(const CoeffT &o) const { + Self ret; + for (int i = 0; i < dimension_t; ++i) { + ret[i] = (*this)[i] * o; + } + return ret; + } + + Self operator/(const CoeffT &o) const { + Self ret; + for (int i = 0; i < dimension_t; ++i) { + ret[i] = (*this)[i] / o; + } + return ret; + } + + bool operator==(const Self &o) const { + for (int i = 0; i < dimension_t; ++i) { + if ((*this)[i] != o[i]) + return false; + } + return true; + } + + bool operator!=(const Self &x) const { return !((*this) == x); } + + bool operator<(const Self &x) const { + for (int i = 0; i < dimension_t - 1; ++i) { + if (v_[i] < x.v_[i]) + return true; + if (v_[i] > x.v_[i]) + return false; + } + // Only one check needed for the last dimension. + if (v_[dimension_t - 1] < x.v_[dimension_t - 1]) + return true; + return false; + } + + // Functions. + CoeffT SquaredNorm() const { return this->Dot(*this); } + + // Computes L1, the sum of absolute values of all entries. + CoeffT AbsSum() const { + CoeffT result(0); + for (int i = 0; i < dimension_t; ++i) { + result += std::abs(v_[i]); + } + return result; + } + + CoeffT Dot(const Self &o) const { + CoeffT ret(0); + for (int i = 0; i < dimension_t; ++i) { + ret += (*this)[i] * o[i]; + } + return ret; + } + + void Normalize() { + const CoeffT magnitude = std::sqrt(this->SquaredNorm()); + if (magnitude == 0) { + return; + } + for (int i = 0; i < dimension_t; ++i) { + (*this)[i] /= magnitude; + } + } + + CoeffT *data() { return &(v_[0]); } + + private: + std::array<CoeffT, dimension_t> v_; +}; + +// Scalar multiplication from the other side too. +template <class CoeffT, int dimension_t> +VectorD<CoeffT, dimension_t> operator*(const CoeffT &o, + const VectorD<CoeffT, dimension_t> &v) { + return v * o; +} + +// Calculates the squared distance between two points. +template <class CoeffT, int dimension_t> +CoeffT SquaredDistance(const VectorD<CoeffT, dimension_t> &v1, + const VectorD<CoeffT, dimension_t> &v2) { + CoeffT difference; + CoeffT squared_distance = 0; + // Check each index separately so difference is never negative and underflow + // is avoided for unsigned types. + for (int i = 0; i < dimension_t; ++i) { + if (v1[i] >= v2[i]) { + difference = v1[i] - v2[i]; + } else { + difference = v2[i] - v1[i]; + } + squared_distance += (difference * difference); + } + return squared_distance; +} + +// Global function computing the cross product of two 3D vectors. +template <class CoeffT> +VectorD<CoeffT, 3> CrossProduct(const VectorD<CoeffT, 3> &u, + const VectorD<CoeffT, 3> &v) { + // Preventing accidental use with uint32_t and the like. + static_assert(std::is_signed<CoeffT>::value, + "CoeffT must be a signed type. "); + VectorD<CoeffT, 3> r; + r[0] = (u[1] * v[2]) - (u[2] * v[1]); + r[1] = (u[2] * v[0]) - (u[0] * v[2]); + r[2] = (u[0] * v[1]) - (u[1] * v[0]); + return r; +} + +template <class CoeffT, int dimension_t> +inline std::ostream &operator<<( + std::ostream &out, const draco::VectorD<CoeffT, dimension_t> &vec) { + for (int i = 0; i < dimension_t - 1; ++i) { + out << vec[i] << " "; + } + out << vec[dimension_t - 1]; + return out; +} + +typedef VectorD<float, 2> Vector2f; +typedef VectorD<float, 3> Vector3f; +typedef VectorD<float, 4> Vector4f; +typedef VectorD<float, 5> Vector5f; +typedef VectorD<float, 6> Vector6f; +typedef VectorD<float, 7> Vector7f; + +typedef VectorD<uint32_t, 2> Vector2ui; +typedef VectorD<uint32_t, 3> Vector3ui; +typedef VectorD<uint32_t, 4> Vector4ui; +typedef VectorD<uint32_t, 5> Vector5ui; +typedef VectorD<uint32_t, 6> Vector6ui; +typedef VectorD<uint32_t, 7> Vector7ui; + +} // namespace draco + +#endif // DRACO_CORE_VECTOR_D_H_ diff --git a/extern/draco/dracoenc/src/draco/core/vector_d_test.cc b/extern/draco/dracoenc/src/draco/core/vector_d_test.cc new file mode 100644 index 00000000000..967043bb926 --- /dev/null +++ b/extern/draco/dracoenc/src/draco/core/vector_d_test.cc @@ -0,0 +1,205 @@ +// Copyright 2016 The Draco Authors. +// +// 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 "draco/core/vector_d.h" + +#include <sstream> + +#include "draco/core/draco_test_base.h" + +namespace { + +typedef draco::Vector2f Vector2f; +typedef draco::Vector3f Vector3f; +typedef draco::Vector4f Vector4f; +typedef draco::Vector5f Vector5f; +typedef draco::Vector2ui Vector2ui; +typedef draco::Vector3ui Vector3ui; +typedef draco::Vector4ui Vector4ui; +typedef draco::Vector5ui Vector5ui; + +typedef draco::VectorD<int32_t, 3> Vector3i; +typedef draco::VectorD<int32_t, 4> Vector4i; + +class VectorDTest : public ::testing::Test { + protected: + template <class CoeffT, int dimension_t> + void TestSquaredDistance(const draco::VectorD<CoeffT, dimension_t> v1, + const draco::VectorD<CoeffT, dimension_t> v2, + const CoeffT result) { + CoeffT squared_distance = SquaredDistance(v1, v2); + ASSERT_EQ(squared_distance, result); + squared_distance = SquaredDistance(v2, v1); + ASSERT_EQ(squared_distance, result); + } +}; + +TEST_F(VectorDTest, TestOperators) { + { + const Vector3f v; + ASSERT_EQ(v[0], 0); + ASSERT_EQ(v[1], 0); + ASSERT_EQ(v[2], 0); + } + Vector3f v(1, 2, 3); + ASSERT_EQ(v[0], 1); + ASSERT_EQ(v[1], 2); + ASSERT_EQ(v[2], 3); + + Vector3f w = v; + bool comp = (v == w); + ASSERT_TRUE(comp); + comp = (v != w); + ASSERT_TRUE(!comp); + ASSERT_EQ(w[0], 1); + ASSERT_EQ(w[1], 2); + ASSERT_EQ(w[2], 3); + + w = -v; + ASSERT_EQ(w[0], -1); + ASSERT_EQ(w[1], -2); + ASSERT_EQ(w[2], -3); + + w = v + v; + ASSERT_EQ(w[0], 2); + ASSERT_EQ(w[1], 4); + ASSERT_EQ(w[2], 6); + + w = w - v; + ASSERT_EQ(w[0], 1); + ASSERT_EQ(w[1], 2); + ASSERT_EQ(w[2], 3); + + w = v * 2.f; + ASSERT_EQ(w[0], 2); + ASSERT_EQ(w[1], 4); + ASSERT_EQ(w[2], 6); + + ASSERT_EQ(v.SquaredNorm(), 14); + ASSERT_EQ(v.Dot(v), 14); + + Vector3f new_v = v; + new_v.Normalize(); + const float eps = 0.001; + const float magnitude = std::sqrt(v.SquaredNorm()); + const float new_magnitude = std::sqrt(new_v.SquaredNorm()); + ASSERT_LE(new_magnitude, 1 + eps); + ASSERT_GE(new_magnitude, 1 - eps); + for (int i = 0; i < 3; ++i) { + new_v[i] *= magnitude; + ASSERT_LE(new_v[i], v[i] + eps); + ASSERT_GE(new_v[i], v[i] - eps); + } + + Vector3f x(0, 0, 0); + x.Normalize(); + for (int i = 0; i < 3; ++i) { + ASSERT_EQ(0, x[i]); + } +} + +TEST_F(VectorDTest, TestSquaredDistance) { + // Test Vector2f: float, 2D. + Vector2f v1_2f(5.5, 10.5); + Vector2f v2_2f(3.5, 15.5); + float result_f = 29; + TestSquaredDistance(v1_2f, v2_2f, result_f); + + // Test Vector3f: float, 3D. + Vector3f v1_3f(5.5, 10.5, 2.3); + Vector3f v2_3f(3.5, 15.5, 0); + result_f = 34.29; + TestSquaredDistance(v1_3f, v2_3f, result_f); + + // Test Vector4f: float, 4D. + Vector4f v1_4f(5.5, 10.5, 2.3, 7.2); + Vector4f v2_4f(3.5, 15.5, 0, 9.9); + result_f = 41.58; + TestSquaredDistance(v1_4f, v2_4f, result_f); + + // Test Vector5f: float, 5D. + Vector5f v1_5f(5.5, 10.5, 2.3, 7.2, 1.0); + Vector5f v2_5f(3.5, 15.5, 0, 9.9, 0.2); + result_f = 42.22; + TestSquaredDistance(v1_5f, v2_5f, result_f); + + // Test Vector 2ui: uint32_t, 2D. + Vector2ui v1_2ui(5, 10); + Vector2ui v2_2ui(3, 15); + uint32_t result_ui = 29; + TestSquaredDistance(v1_2ui, v2_2ui, result_ui); + + // Test Vector 3ui: uint32_t, 3D. + Vector3ui v1_3ui(5, 10, 2); + Vector3ui v2_3ui(3, 15, 0); + result_ui = 33; + TestSquaredDistance(v1_3ui, v2_3ui, result_ui); + + // Test Vector 4ui: uint32_t, 4D. + Vector4ui v1_4ui(5, 10, 2, 7); + Vector4ui v2_4ui(3, 15, 0, 9); + result_ui = 37; + TestSquaredDistance(v1_4ui, v2_4ui, result_ui); + + // Test Vector 5ui: uint32_t, 5D. + Vector5ui v1_5ui(5, 10, 2, 7, 1); + Vector5ui v2_5ui(3, 15, 0, 9, 12); + result_ui = 158; + TestSquaredDistance(v1_5ui, v2_5ui, result_ui); +} +TEST_F(VectorDTest, TestCrossProduct3D) { + const Vector3i e1(1, 0, 0); + const Vector3i e2(0, 1, 0); + const Vector3i e3(0, 0, 1); + const Vector3i o(0, 0, 0); + ASSERT_EQ(e3, draco::CrossProduct(e1, e2)); + ASSERT_EQ(e1, draco::CrossProduct(e2, e3)); + ASSERT_EQ(e2, draco::CrossProduct(e3, e1)); + ASSERT_EQ(-e3, draco::CrossProduct(e2, e1)); + ASSERT_EQ(-e1, draco::CrossProduct(e3, e2)); + ASSERT_EQ(-e2, draco::CrossProduct(e1, e3)); + ASSERT_EQ(o, draco::CrossProduct(e1, e1)); + ASSERT_EQ(o, draco::CrossProduct(e2, e2)); + ASSERT_EQ(o, draco::CrossProduct(e3, e3)); + + // Orthogonality of result for some general vectors. + const Vector3i v1(123, -62, 223); + const Vector3i v2(734, 244, -13); + const Vector3i orth = draco::CrossProduct(v1, v2); + ASSERT_EQ(0, v1.Dot(orth)); + ASSERT_EQ(0, v2.Dot(orth)); +} + +TEST_F(VectorDTest, TestAbsSum) { + // Testing const of function and zero. + const Vector3i v(0, 0, 0); + ASSERT_EQ(v.AbsSum(), 0); + // Testing semantic. + ASSERT_EQ(Vector3i(0, 0, 0).AbsSum(), 0); + ASSERT_EQ(Vector3i(1, 2, 3).AbsSum(), 6); + ASSERT_EQ(Vector3i(-1, -2, -3).AbsSum(), 6); + ASSERT_EQ(Vector3i(-2, 4, -8).AbsSum(), 14); + // Other dimension. + ASSERT_EQ(Vector4i(-2, 4, -8, 3).AbsSum(), 17); +} + +TEST_F(VectorDTest, TestOstream) { + // Tests that the vector can be stored in a provided std::ostream. + const draco::VectorD<int64_t, 3> vector(1, 2, 3); + std::stringstream str; + str << vector << " "; + ASSERT_EQ(str.str(), "1 2 3 "); +} + +} // namespace |