From af6976a907b0d2a9fadbb14d7258bab44f075364 Mon Sep 17 00:00:00 2001 From: zxu Date: Sat, 27 Jan 2018 17:53:27 -0500 Subject: normalize and port the rest of Firebase/Port code (#713) * normalize bits * normalize ordered_code --- .../Example/Firestore.xcodeproj/project.pbxproj | 34 +- .../Tests/Local/FSTLevelDBMutationQueueTests.mm | 5 +- .../Local/FSTLevelDBRemoteDocumentCacheTests.mm | 5 +- Firestore/Port/bits.cc | 39 -- Firestore/Port/bits.h | 160 ------ Firestore/Port/bits_test.cc | 138 ----- Firestore/Port/ordered_code.cc | 585 ------------------- Firestore/Port/ordered_code.h | 116 ---- Firestore/Port/ordered_code_test.cc | 528 ----------------- Firestore/Source/Local/FSTLevelDBKey.mm | 37 +- Firestore/Source/Local/FSTLevelDBMutationQueue.mm | 2 - Firestore/Source/Local/FSTLevelDBQueryCache.mm | 3 - .../Source/Local/FSTLevelDBRemoteDocumentCache.mm | 3 - Firestore/Source/Local/FSTWriteGroup.mm | 3 - Firestore/Source/Local/StringView.h | 12 + .../src/firebase/firestore/util/CMakeLists.txt | 4 + Firestore/core/src/firebase/firestore/util/bits.cc | 43 ++ Firestore/core/src/firebase/firestore/util/bits.h | 166 ++++++ .../src/firebase/firestore/util/ordered_code.cc | 622 +++++++++++++++++++++ .../src/firebase/firestore/util/ordered_code.h | 129 +++++ .../src/firebase/firestore/util/secure_random.h | 16 + .../test/firebase/firestore/util/CMakeLists.txt | 2 + .../core/test/firebase/firestore/util/bits_test.cc | 142 +++++ .../firebase/firestore/util/ordered_code_test.cc | 508 +++++++++++++++++ .../firebase/firestore/util/secure_random_test.cc | 25 + 25 files changed, 1713 insertions(+), 1614 deletions(-) delete mode 100644 Firestore/Port/bits.cc delete mode 100644 Firestore/Port/bits.h delete mode 100644 Firestore/Port/bits_test.cc delete mode 100644 Firestore/Port/ordered_code.cc delete mode 100644 Firestore/Port/ordered_code.h delete mode 100644 Firestore/Port/ordered_code_test.cc create mode 100644 Firestore/core/src/firebase/firestore/util/bits.cc create mode 100644 Firestore/core/src/firebase/firestore/util/bits.h create mode 100644 Firestore/core/src/firebase/firestore/util/ordered_code.cc create mode 100644 Firestore/core/src/firebase/firestore/util/ordered_code.h create mode 100644 Firestore/core/test/firebase/firestore/util/bits_test.cc create mode 100644 Firestore/core/test/firebase/firestore/util/ordered_code_test.cc (limited to 'Firestore') diff --git a/Firestore/Example/Firestore.xcodeproj/project.pbxproj b/Firestore/Example/Firestore.xcodeproj/project.pbxproj index 7c6508a..6a5b795 100644 --- a/Firestore/Example/Firestore.xcodeproj/project.pbxproj +++ b/Firestore/Example/Firestore.xcodeproj/project.pbxproj @@ -67,6 +67,8 @@ AB356EF7200EA5EB0089B766 /* field_value_test.cc in Sources */ = {isa = PBXBuildFile; fileRef = AB356EF6200EA5EB0089B766 /* field_value_test.cc */; }; AB380CFB2019388600D97691 /* target_id_generator_test.cc in Sources */ = {isa = PBXBuildFile; fileRef = AB380CF82019382300D97691 /* target_id_generator_test.cc */; }; AB380CFE201A2F4500D97691 /* string_util_test.cc in Sources */ = {isa = PBXBuildFile; fileRef = AB380CFC201A2EE200D97691 /* string_util_test.cc */; }; + AB380D02201BC69F00D97691 /* bits_test.cc in Sources */ = {isa = PBXBuildFile; fileRef = AB380D01201BC69F00D97691 /* bits_test.cc */; }; + AB380D04201BC6E400D97691 /* ordered_code_test.cc in Sources */ = {isa = PBXBuildFile; fileRef = AB380D03201BC6E400D97691 /* ordered_code_test.cc */; }; AB382F7C1FE02A1F007CA955 /* FIRDocumentReferenceTests.m in Sources */ = {isa = PBXBuildFile; fileRef = AB382F7B1FE02A1F007CA955 /* FIRDocumentReferenceTests.m */; }; AB382F7E1FE03059007CA955 /* FIRFieldPathTests.m in Sources */ = {isa = PBXBuildFile; fileRef = AB382F7D1FE03059007CA955 /* FIRFieldPathTests.m */; }; AB7BAB342012B519001E0872 /* geo_point_test.cc in Sources */ = {isa = PBXBuildFile; fileRef = AB7BAB332012B519001E0872 /* geo_point_test.cc */; }; @@ -251,6 +253,8 @@ AB356EF6200EA5EB0089B766 /* field_value_test.cc */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.cpp.cpp; path = field_value_test.cc; sourceTree = ""; }; AB380CF82019382300D97691 /* target_id_generator_test.cc */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = target_id_generator_test.cc; sourceTree = ""; }; AB380CFC201A2EE200D97691 /* string_util_test.cc */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = string_util_test.cc; path = ../../core/test/firebase/firestore/util/string_util_test.cc; sourceTree = ""; }; + AB380D01201BC69F00D97691 /* bits_test.cc */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = bits_test.cc; path = ../../core/test/firebase/firestore/util/bits_test.cc; sourceTree = ""; }; + AB380D03201BC6E400D97691 /* ordered_code_test.cc */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = ordered_code_test.cc; path = ../../core/test/firebase/firestore/util/ordered_code_test.cc; sourceTree = ""; }; AB382F7B1FE02A1F007CA955 /* FIRDocumentReferenceTests.m */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.objc; path = FIRDocumentReferenceTests.m; sourceTree = ""; }; AB382F7D1FE03059007CA955 /* FIRFieldPathTests.m */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.objc; path = FIRFieldPathTests.m; sourceTree = ""; }; AB7BAB332012B519001E0872 /* geo_point_test.cc */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = geo_point_test.cc; path = ../../core/test/firebase/firestore/geo_point_test.cc; sourceTree = ""; }; @@ -404,8 +408,10 @@ children = ( 548DB926200D590300E00ABC /* assert_test.cc */, 54740A521FC913E500713A1A /* autoid_test.cc */, + AB380D01201BC69F00D97691 /* bits_test.cc */, 548DB928200D59F600E00ABC /* comparison_test.cc */, 54C2294E1FECABAE007D065B /* log_test.cc */, + AB380D03201BC6E400D97691 /* ordered_code_test.cc */, 54740A531FC913E500713A1A /* secure_random_test.cc */, 5436F32320008FAD006E51E3 /* string_printf_test.cc */, AB380CFC201A2EE200D97691 /* string_util_test.cc */, @@ -418,7 +424,6 @@ children = ( AB380CF7201937B800D97691 /* core */, AB356EF5200E9D1A0089B766 /* model */, - 54764FAD1FAA0C650085E60A /* Port */, 54740A561FC913EB00713A1A /* util */, 54764FAE1FAA21B90085E60A /* FSTGoogleTestTests.mm */, AB7BAB332012B519001E0872 /* geo_point_test.cc */, @@ -426,13 +431,6 @@ name = GoogleTests; sourceTree = ""; }; - 54764FAD1FAA0C650085E60A /* Port */ = { - isa = PBXGroup; - children = ( - ); - name = Port; - sourceTree = ""; - }; 6003F581195388D10070C39A = { isa = PBXGroup; children = ( @@ -594,31 +592,31 @@ DE51B1621F0D48AC0013853F /* Local */ = { isa = PBXGroup; children = ( - 61E1D8AF1FCF6AF500753285 /* StringViewTests.mm */, - DE51B16A1F0D48AC0013853F /* FSTLocalStoreTests.h */, - DE51B1701F0D48AC0013853F /* FSTMutationQueueTests.h */, - DE51B1721F0D48AC0013853F /* FSTPersistenceTestHelpers.h */, - DE51B1741F0D48AC0013853F /* FSTQueryCacheTests.h */, - DE51B1771F0D48AC0013853F /* FSTRemoteDocumentCacheTests.h */, DE51B1631F0D48AC0013853F /* FSTEagerGarbageCollectorTests.m */, + DE51B1641F0D48AC0013853F /* FSTLevelDBKeyTests.mm */, DE51B1651F0D48AC0013853F /* FSTLevelDBLocalStoreTests.m */, + DE51B1661F0D48AC0013853F /* FSTLevelDBMutationQueueTests.mm */, DE51B1671F0D48AC0013853F /* FSTLevelDBQueryCacheTests.m */, + DE51B1681F0D48AC0013853F /* FSTLevelDBRemoteDocumentCacheTests.mm */, DE51B1691F0D48AC0013853F /* FSTLocalSerializerTests.m */, + DE51B16A1F0D48AC0013853F /* FSTLocalStoreTests.h */, DE51B16B1F0D48AC0013853F /* FSTLocalStoreTests.m */, DE51B16C1F0D48AC0013853F /* FSTMemoryLocalStoreTests.m */, DE51B16D1F0D48AC0013853F /* FSTMemoryMutationQueueTests.m */, DE51B16E1F0D48AC0013853F /* FSTMemoryQueryCacheTests.m */, DE51B16F1F0D48AC0013853F /* FSTMemoryRemoteDocumentCacheTests.m */, + DE51B1701F0D48AC0013853F /* FSTMutationQueueTests.h */, DE51B1711F0D48AC0013853F /* FSTMutationQueueTests.m */, + DE51B1721F0D48AC0013853F /* FSTPersistenceTestHelpers.h */, DE51B1731F0D48AC0013853F /* FSTPersistenceTestHelpers.m */, + DE51B1741F0D48AC0013853F /* FSTQueryCacheTests.h */, DE51B1751F0D48AC0013853F /* FSTQueryCacheTests.m */, DE51B1761F0D48AC0013853F /* FSTReferenceSetTests.m */, + DE51B1771F0D48AC0013853F /* FSTRemoteDocumentCacheTests.h */, DE51B1781F0D48AC0013853F /* FSTRemoteDocumentCacheTests.m */, DE51B1791F0D48AC0013853F /* FSTRemoteDocumentChangeBufferTests.m */, - DE51B1641F0D48AC0013853F /* FSTLevelDBKeyTests.mm */, - DE51B1661F0D48AC0013853F /* FSTLevelDBMutationQueueTests.mm */, - DE51B1681F0D48AC0013853F /* FSTLevelDBRemoteDocumentCacheTests.mm */, DE51B17A1F0D48AC0013853F /* FSTWriteGroupTests.mm */, + 61E1D8AF1FCF6AF500753285 /* StringViewTests.mm */, ); path = Local; sourceTree = ""; @@ -1274,6 +1272,7 @@ DE51B1E01F0D490D0013853F /* FSTMemoryQueryCacheTests.m in Sources */, DE51B1E91F0D490D0013853F /* FSTLevelDBMutationQueueTests.mm in Sources */, 54764FAF1FAA21B90085E60A /* FSTGoogleTestTests.mm in Sources */, + AB380D04201BC6E400D97691 /* ordered_code_test.cc in Sources */, DE51B1E61F0D490D0013853F /* FSTRemoteDocumentCacheTests.m in Sources */, 61E1D8B11FCF6C5700753285 /* StringViewTests.mm in Sources */, DE51B1D91F0D490D0013853F /* FSTEagerGarbageCollectorTests.m in Sources */, @@ -1290,6 +1289,7 @@ DE51B1FC1F0D492C0013853F /* FSTMockDatastore.m in Sources */, DE51B1CE1F0D48CD0013853F /* FSTEventManagerTests.m in Sources */, DE51B1E41F0D490D0013853F /* FSTQueryCacheTests.m in Sources */, + AB380D02201BC69F00D97691 /* bits_test.cc in Sources */, DE51B1CD1F0D48CD0013853F /* FSTDatabaseInfoTests.m in Sources */, AB382F7E1FE03059007CA955 /* FIRFieldPathTests.m in Sources */, 548DB929200D59F600E00ABC /* comparison_test.cc in Sources */, diff --git a/Firestore/Example/Tests/Local/FSTLevelDBMutationQueueTests.mm b/Firestore/Example/Tests/Local/FSTLevelDBMutationQueueTests.mm index 6c26fd9..fe79598 100644 --- a/Firestore/Example/Tests/Local/FSTLevelDBMutationQueueTests.mm +++ b/Firestore/Example/Tests/Local/FSTLevelDBMutationQueueTests.mm @@ -19,7 +19,6 @@ #import #include -#include "Firestore/Port/ordered_code.h" #import "Firestore/Protos/objc/firestore/local/Mutation.pbobjc.h" #import "Firestore/Source/Auth/FSTUser.h" #import "Firestore/Source/Local/FSTLevelDB.h" @@ -29,6 +28,8 @@ #import "Firestore/Example/Tests/Local/FSTMutationQueueTests.h" #import "Firestore/Example/Tests/Local/FSTPersistenceTestHelpers.h" +#include "Firestore/core/src/firebase/firestore/util/ordered_code.h" + NS_ASSUME_NONNULL_BEGIN using leveldb::DB; @@ -36,7 +37,7 @@ using leveldb::Slice; using leveldb::Status; using leveldb::WriteOptions; using Firestore::StringView; -using Firestore::OrderedCode; +using firebase::firestore::util::OrderedCode; // A dummy mutation value, useful for testing code that's known to examine only mutation keys. static const char *kDummy = "1"; diff --git a/Firestore/Example/Tests/Local/FSTLevelDBRemoteDocumentCacheTests.mm b/Firestore/Example/Tests/Local/FSTLevelDBRemoteDocumentCacheTests.mm index 1f84aa6..638ab2f 100644 --- a/Firestore/Example/Tests/Local/FSTLevelDBRemoteDocumentCacheTests.mm +++ b/Firestore/Example/Tests/Local/FSTLevelDBRemoteDocumentCacheTests.mm @@ -18,16 +18,17 @@ #include -#include "Firestore/Port/ordered_code.h" #import "Firestore/Source/Local/FSTLevelDB.h" #import "Firestore/Source/Local/FSTLevelDBKey.h" #import "Firestore/Example/Tests/Local/FSTPersistenceTestHelpers.h" +#include "Firestore/core/src/firebase/firestore/util/ordered_code.h" + NS_ASSUME_NONNULL_BEGIN using leveldb::WriteOptions; -using Firestore::OrderedCode; +using firebase::firestore::util::OrderedCode; // A dummy document value, useful for testing code that's known to examine only document keys. static const char *kDummy = "1"; diff --git a/Firestore/Port/bits.cc b/Firestore/Port/bits.cc deleted file mode 100644 index 3e61223..0000000 --- a/Firestore/Port/bits.cc +++ /dev/null @@ -1,39 +0,0 @@ -/* - * Copyright 2017 Google - * - * 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 "Firestore/Port/bits.h" - -#include - -namespace Firestore { - -int Bits::Log2Floor_Portable(uint32_t n) { - if (n == 0) return -1; - int log = 0; - uint32_t value = n; - for (int i = 4; i >= 0; --i) { - int shift = (1 << i); - uint32_t x = value >> shift; - if (x != 0) { - value = x; - log += shift; - } - } - assert(value == 1); - return log; -} - -} // namespace Firestore diff --git a/Firestore/Port/bits.h b/Firestore/Port/bits.h deleted file mode 100644 index d212bf8..0000000 --- a/Firestore/Port/bits.h +++ /dev/null @@ -1,160 +0,0 @@ -/* - * Copyright 2017 Google - * - * 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 IPHONE_FIRESTORE_PORT_BITS_H_ -#define IPHONE_FIRESTORE_PORT_BITS_H_ - -// Various bit-twiddling functions, all of which are static members of the Bits -// class (making it effectively a namespace). Operands are unsigned integers. -// Munging bits in _signed_ integers is fraught with peril! For example, -// -5 << n has undefined behavior (for some values of n). - -#include - -class Bits_Port32_Test; -class Bits_Port64_Test; - -namespace Firestore { - -class Bits { - public: - // Return floor(log2(n)) for positive integer n. Returns -1 iff n == 0. - static int Log2Floor(uint32_t n); - static int Log2Floor64(uint64_t n); - - // Potentially faster version of Log2Floor() that returns an - // undefined value if n == 0 - static int Log2FloorNonZero(uint32_t n); - static int Log2FloorNonZero64(uint64_t n); - - private: - // Portable implementations. - static int Log2Floor_Portable(uint32_t n); - static int Log2Floor64_Portable(uint64_t n); - static int Log2FloorNonZero_Portable(uint32_t n); - static int Log2FloorNonZero64_Portable(uint64_t n); - - Bits(Bits const&) = delete; - void operator=(Bits const&) = delete; - - // Allow tests to call _Portable variants directly. - friend class ::Bits_Port32_Test; - friend class ::Bits_Port64_Test; -}; - -// ------------------------------------------------------------------------ -// Implementation details follow -// ------------------------------------------------------------------------ - -#if defined(__GNUC__) - -inline int Bits::Log2Floor(uint32_t n) { - return n == 0 ? -1 : 31 ^ __builtin_clz(n); -} - -inline int Bits::Log2FloorNonZero(uint32_t n) { - return 31 ^ __builtin_clz(n); -} - -inline int Bits::Log2Floor64(uint64_t n) { - return n == 0 ? -1 : 63 ^ __builtin_clzll(n); -} - -inline int Bits::Log2FloorNonZero64(uint64_t n) { - return 63 ^ __builtin_clzll(n); -} - -#elif defined(COMPILER_MSVC) - -inline int Bits::Log2FloorNonZero(uint32 n) { -#ifdef _M_IX86 - _asm { - bsr ebx, n - mov n, ebx - } - return n; -#else - return Bits::Log2FloorNonZero_Portable(n); -#endif -} - -inline int Bits::Log2Floor(uint32 n) { -#ifdef _M_IX86 - _asm { - xor ebx, ebx - mov eax, n - and eax, eax - jz return_ebx - bsr ebx, eax - return_ebx: - mov n, ebx - } - return n; -#else - return Bits::Log2Floor_Portable(n); -#endif -} - -inline int Bits::Log2Floor64(uint64_t n) { - return Bits::Log2Floor64_Portable(n); -} - -inline int Bits::Log2FloorNonZero64(uint64_t n) { - return Bits::Log2FloorNonZero64_Portable(n); -} - -#else // !__GNUC__ && !COMPILER_MSVC - -inline int Bits::Log2Floor64(uint64_t n) { - return Bits::Log2Floor64_Portable(n); -} - -inline int Bits::Log2FloorNonZero64(uint64_t n) { - return Bits::Log2FloorNonZero64_Portable(n); -} - -#endif - -inline int Bits::Log2FloorNonZero_Portable(uint32_t n) { - // Just use the common routine - return Log2Floor(n); -} - -// Log2Floor64() is defined in terms of Log2Floor32(), Log2FloorNonZero32() -inline int Bits::Log2Floor64_Portable(uint64_t n) { - const uint32_t topbits = static_cast(n >> 32); - if (topbits == 0) { - // Top bits are zero, so scan in bottom bits - return Log2Floor(static_cast(n)); - } else { - return 32 + Log2FloorNonZero(topbits); - } -} - -// Log2FloorNonZero64() is defined in terms of Log2FloorNonZero32() -inline int Bits::Log2FloorNonZero64_Portable(uint64_t n) { - const uint32_t topbits = static_cast(n >> 32); - if (topbits == 0) { - // Top bits are zero, so scan in bottom bits - return Log2FloorNonZero(static_cast(n)); - } else { - return 32 + Log2FloorNonZero(topbits); - } -} - -} // namespace Firestore - -#endif // IPHONE_FIRESTORE_PORT_BITS_H_ diff --git a/Firestore/Port/bits_test.cc b/Firestore/Port/bits_test.cc deleted file mode 100644 index 8c3c246..0000000 --- a/Firestore/Port/bits_test.cc +++ /dev/null @@ -1,138 +0,0 @@ -/* - * Copyright 2017 Google - * - * 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 "Firestore/Port/bits.h" - -#include - -#include "base/commandlineflags.h" -#include "testing/base/public/gunit.h" -#include "util/random/mt_random.h" - -using Firestore::Bits; - -DEFINE_int32(num_iterations, 10000, "Number of test iterations to run."); - -class BitsTest : public testing::Test { - public: - BitsTest() : random_(testing::FLAGS_gunit_random_seed) {} - - protected: - MTRandom random_; -}; - -TEST_F(BitsTest, Log2EdgeCases) { - std::cout << "TestLog2EdgeCases" << std::endl; - - EXPECT_EQ(-1, Bits::Log2Floor(0)); - EXPECT_EQ(-1, Bits::Log2Floor64(0)); - - for (int i = 0; i < 32; i++) { - uint32 n = 1U << i; - EXPECT_EQ(i, Bits::Log2Floor(n)); - EXPECT_EQ(i, Bits::Log2FloorNonZero(n)); - if (n > 2) { - EXPECT_EQ(i - 1, Bits::Log2Floor(n - 1)); - EXPECT_EQ(i, Bits::Log2Floor(n + 1)); - EXPECT_EQ(i - 1, Bits::Log2FloorNonZero(n - 1)); - EXPECT_EQ(i, Bits::Log2FloorNonZero(n + 1)); - } - } - - for (int i = 0; i < 64; i++) { - uint64 n = 1ULL << i; - EXPECT_EQ(i, Bits::Log2Floor64(n)); - EXPECT_EQ(i, Bits::Log2FloorNonZero64(n)); - if (n > 2) { - EXPECT_EQ(i - 1, Bits::Log2Floor64(n - 1)); - EXPECT_EQ(i, Bits::Log2Floor64(n + 1)); - EXPECT_EQ(i - 1, Bits::Log2FloorNonZero64(n - 1)); - EXPECT_EQ(i, Bits::Log2FloorNonZero64(n + 1)); - } - } -} - -TEST_F(BitsTest, Log2Random) { - std::cout << "TestLog2Random" << std::endl; - - for (int i = 0; i < FLAGS_num_iterations; i++) { - int maxbit = -1; - uint32 n = 0; - while (!random_.OneIn(32)) { - int bit = random_.Uniform(32); - n |= (1U << bit); - maxbit = std::max(bit, maxbit); - } - EXPECT_EQ(maxbit, Bits::Log2Floor(n)); - if (n != 0) { - EXPECT_EQ(maxbit, Bits::Log2FloorNonZero(n)); - } - } -} - -TEST_F(BitsTest, Log2Random64) { - std::cout << "TestLog2Random64" << std::endl; - - for (int i = 0; i < FLAGS_num_iterations; i++) { - int maxbit = -1; - uint64 n = 0; - while (!random_.OneIn(64)) { - int bit = random_.Uniform(64); - n |= (1ULL << bit); - maxbit = std::max(bit, maxbit); - } - EXPECT_EQ(maxbit, Bits::Log2Floor64(n)); - if (n != 0) { - EXPECT_EQ(maxbit, Bits::Log2FloorNonZero64(n)); - } - } -} - -TEST(Bits, Port32) { - for (int shift = 0; shift < 32; shift++) { - for (int delta = -1; delta <= +1; delta++) { - const uint32 v = (static_cast(1) << shift) + delta; - EXPECT_EQ(Bits::Log2Floor_Portable(v), Bits::Log2Floor(v)) << v; - if (v != 0) { - EXPECT_EQ(Bits::Log2FloorNonZero_Portable(v), Bits::Log2FloorNonZero(v)) - << v; - } - } - } - static const uint32 M32 = kuint32max; - EXPECT_EQ(Bits::Log2Floor_Portable(M32), Bits::Log2Floor(M32)) << M32; - EXPECT_EQ(Bits::Log2FloorNonZero_Portable(M32), Bits::Log2FloorNonZero(M32)) - << M32; -} - -TEST(Bits, Port64) { - for (int shift = 0; shift < 64; shift++) { - for (int delta = -1; delta <= +1; delta++) { - const uint64 v = (static_cast(1) << shift) + delta; - EXPECT_EQ(Bits::Log2Floor64_Portable(v), Bits::Log2Floor64(v)) << v; - if (v != 0) { - EXPECT_EQ(Bits::Log2FloorNonZero64_Portable(v), - Bits::Log2FloorNonZero64(v)) - << v; - } - } - } - static const uint64 M64 = kuint64max; - EXPECT_EQ(Bits::Log2Floor64_Portable(M64), Bits::Log2Floor64(M64)) << M64; - EXPECT_EQ(Bits::Log2FloorNonZero64_Portable(M64), - Bits::Log2FloorNonZero64(M64)) - << M64; -} diff --git a/Firestore/Port/ordered_code.cc b/Firestore/Port/ordered_code.cc deleted file mode 100644 index 05a1569..0000000 --- a/Firestore/Port/ordered_code.cc +++ /dev/null @@ -1,585 +0,0 @@ -/* - * Copyright 2017 Google - * - * 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 "Firestore/Port/ordered_code.h" - -#include - -#include -#include -#include -#include // For Slice - -#include "Firestore/Port/bits.h" - -#define UNALIGNED_LOAD32 ABSL_INTERNAL_UNALIGNED_LOAD32 -#define UNALIGNED_LOAD64 ABSL_INTERNAL_UNALIGNED_LOAD64 -#define UNALIGNED_STORE32 ABSL_INTERNAL_UNALIGNED_STORE32 -#define UNALIGNED_STORE64 ABSL_INTERNAL_UNALIGNED_STORE64 - -// We encode a string in different ways depending on whether the item -// should be in lexicographically increasing or decreasing order. -// -// -// Lexicographically increasing order -// -// We want a string-to-string mapping F(x) such that for any two strings -// -// x < y => F(x) < F(y) -// -// In addition to the normal characters '\x00' through '\xff', we want to -// encode a few extra symbols in strings: -// -// Separator between items -// Infinite string -// -// Therefore we need an alphabet with at least 258 symbols. Each -// character '\1' through '\xfe' is mapped to itself. The other four are -// encoded into two-letter sequences starting with '\0' and '\xff': -// -// encoded as => \0\1 -// \0 encoded as => \0\xff -// \xff encoded as => \xff\x00 -// encoded as => \xff\xff -// -// The remaining two-letter sequences starting with '\0' and '\xff' are -// currently unused. -// -// F() is defined above. For any finite string x, F(x) is the -// the encodings of x's characters followed by the encoding for . The -// ordering of two finite strings is the same as the ordering of the -// respective characters at the first position where they differ, which in -// turn is the same as the ordering of the encodings of those two -// characters. Moreover, for every finite string x, F(x) < F(). - -namespace Firestore { - -using leveldb::Slice; - -static const char kEscape1 = '\000'; -static const char kNullCharacter = '\xff'; // Combined with kEscape1 -static const char kSeparator = '\001'; // Combined with kEscape1 - -static const char kEscape2 = '\xff'; -static const char kInfinity = '\xff'; // Combined with kEscape2 -static const char kFFCharacter = '\000'; // Combined with kEscape2 - -static const char kEscape1_Separator[2] = {kEscape1, kSeparator}; - -// Append to "*dest" the "len" bytes starting from "*src". -inline static void AppendBytes(std::string* dest, const char* src, size_t len) { - dest->append(src, len); -} - -inline bool IsSpecialByte(char c) { return ((unsigned char)(c + 1)) < 2; } - -// Returns 0 if one or more of the bytes in the specified uint32 value -// are the special values 0 or 255, and returns 4 otherwise. The -// result of this routine can be added to "p" to either advance past -// the next 4 bytes if they do not contain a special byte, or to -// remain on this set of four bytes if they contain the next special -// byte occurrence. -// -// REQUIRES: v is the value of loading the next 4 bytes from "*p" (we -// pass in v rather than loading it because in some cases, the client -// may already have the value in a register: "p" is just used for -// assertion checking). -inline int AdvanceIfNoSpecialBytes(uint32_t v_32, const char* p) { - assert(UNALIGNED_LOAD32(p) == v_32); - // See comments in SkipToNextSpecialByte if you wish to - // understand this expression (which checks for the occurrence - // of the special byte values 0 or 255 in any of the bytes of v_32). - if ((v_32 - 0x01010101u) & ~(v_32 + 0x01010101u) & 0x80808080u) { - // Special byte is in p[0..3] - assert(IsSpecialByte(p[0]) || IsSpecialByte(p[1]) || IsSpecialByte(p[2]) || - IsSpecialByte(p[3])); - return 0; - } else { - assert(!IsSpecialByte(p[0])); - assert(!IsSpecialByte(p[1])); - assert(!IsSpecialByte(p[2])); - assert(!IsSpecialByte(p[3])); - return 4; - } -} - -// Return a pointer to the first byte in the range "[start..limit)" -// whose value is 0 or 255 (kEscape1 or kEscape2). If no such byte -// exists in the range, returns "limit". -inline const char* SkipToNextSpecialByte(const char* start, const char* limit) { - // If these constants were ever changed, this routine needs to change - assert(kEscape1 == 0); - assert((kEscape2 & 0xffu) == 255u); - const char* p = start; - while (p + 8 <= limit) { - // Find out if any of the next 8 bytes are either 0 or 255 (our - // two characters that require special handling). We do this using - // the technique described in: - // - // http://graphics.stanford.edu/~seander/bithacks.html#HasLessInWord - // - // We use the test (x + 1) < 2 to check x = 0 or -1(255) - // - // If x is a byte value (0x00..0xff): - // (x - 0x01) & 0x80 is true only when x = 0x81..0xff, 0x00 - // ~(x + 0x01) & 0x80 is true only when x = 0x00..0x7e, 0xff - // The intersection of the above two sets is x = 0x00 or 0xff. - // We can ignore carry between bytes because only x = 0x00 or 0xff - // can cause carry in the expression -- and such x already makes the - // result value non-zero. - uint64_t v = UNALIGNED_LOAD64(p); - bool hasZeroOr255Byte = (v - 0x0101010101010101ull) & - ~(v + 0x0101010101010101ull) & - 0x8080808080808080ull; - if (!hasZeroOr255Byte) { - // No special values in the next 8 bytes - p += 8; - } else { -// We know the next 8 bytes have a special byte: find it -#ifdef IS_LITTLE_ENDIAN - uint32_t v_32 = static_cast(v); // Low 32 bits of v -#else - uint32_t v_32 = UNALIGNED_LOAD32(p); -#endif - // Test 32 bits at once to see if special byte is in next 4 bytes - // or the following 4 bytes - p += AdvanceIfNoSpecialBytes(v_32, p); - if (IsSpecialByte(p[0])) return p; - if (IsSpecialByte(p[1])) return p + 1; - if (IsSpecialByte(p[2])) return p + 2; - assert(IsSpecialByte(p[3])); // Last byte must be the special one - return p + 3; - } - } - if (p + 4 <= limit) { - uint32_t v_32 = UNALIGNED_LOAD32(p); - p += AdvanceIfNoSpecialBytes(v_32, p); - } - while (p < limit && !IsSpecialByte(*p)) { - p++; - } - return p; -} - -// Expose SkipToNextSpecialByte for testing purposes -const char* OrderedCode::TEST_SkipToNextSpecialByte(const char* start, - const char* limit) { - return SkipToNextSpecialByte(start, limit); -} - -// Helper routine to encode "s" and append to "*dest", escaping special -// characters. -inline static void EncodeStringFragment(std::string* dest, Slice s) { - const char* p = s.data(); - const char* limit = p + s.size(); - const char* copy_start = p; - while (true) { - p = SkipToNextSpecialByte(p, limit); - if (p >= limit) break; // No more special characters that need escaping - char c = *(p++); - assert(IsSpecialByte(c)); - if (c == kEscape1) { - AppendBytes(dest, copy_start, p - copy_start - 1); - dest->push_back(kEscape1); - dest->push_back(kNullCharacter); - copy_start = p; - } else { - assert(c == kEscape2); - AppendBytes(dest, copy_start, p - copy_start - 1); - dest->push_back(kEscape2); - dest->push_back(kFFCharacter); - copy_start = p; - } - } - if (p > copy_start) { - AppendBytes(dest, copy_start, p - copy_start); - } -} - -void OrderedCode::WriteString(std::string* dest, Slice s) { - EncodeStringFragment(dest, s); - AppendBytes(dest, kEscape1_Separator, 2); -} - -// Return number of bytes needed to encode the non-length portion -// of val in ordered coding. Returns number in range [0,8]. -static inline unsigned int OrderedNumLength(uint64_t val) { - const int lg = Bits::Log2Floor64(val); // -1 if val==0 - return static_cast(lg + 1 + 7) / 8; -} - -// Append n bytes from src to *dst. -// REQUIRES: n <= 9 -// REQUIRES: src[0..8] are readable bytes (even if n is smaller) -// -// If we use string::append() instead of this routine, it increases the -// runtime of WriteNumIncreasing from ~9ns to ~13ns. -static inline void AppendUpto9(std::string* dst, const char* src, - unsigned int n) { - dst->append(src, 9); // Fixed-length append - const size_t extra = 9 - n; // How many extra bytes we added - dst->erase(dst->size() - extra, extra); -} - -void OrderedCode::WriteNumIncreasing(std::string* dest, uint64_t val) { - // Values are encoded with a single byte length prefix, followed - // by the actual value in big-endian format with leading 0 bytes - // dropped. - - // 8 bytes for value plus one byte for length. In addition, we have - // 8 extra bytes at the end so that we can have a fixed-length append - // call on *dest. - char buf[17]; - - UNALIGNED_STORE64(buf + 1, absl::ghtonll(val)); // buf[0] may be needed for length - const unsigned int length = OrderedNumLength(val); - char* start = buf + 9 - length - 1; - *start = length; - AppendUpto9(dest, start, length + 1); -} - -inline static void WriteInfinityInternal(std::string* dest) { - // Make an array so that we can just do one string operation for performance - static const char buf[2] = {kEscape2, kInfinity}; - dest->append(buf, 2); -} - -void OrderedCode::WriteInfinity(std::string* dest) { - WriteInfinityInternal(dest); -} - -void OrderedCode::WriteTrailingString(std::string* dest, Slice str) { - dest->append(str.data(), str.size()); -} - -// Parse the encoding of a string previously encoded with or without -// inversion. If parse succeeds, return true, consume encoding from -// "*src", and if result != NULL append the decoded string to "*result". -// Otherwise, return false and leave both undefined. -inline static bool ReadStringInternal(Slice* src, std::string* result) { - const char* start = src->data(); - const char* string_limit = src->data() + src->size(); - - // We only scan up to "limit-2" since a valid string must end with - // a two character terminator: 'kEscape1 kSeparator' - const char* limit = string_limit - 1; - const char* copy_start = start; - while (true) { - start = SkipToNextSpecialByte(start, limit); - if (start >= limit) break; // No terminator sequence found - const char c = *(start++); - // If inversion is required, instead of inverting 'c', we invert the - // character constants to which 'c' is compared. We get the same - // behavior but save the runtime cost of inverting 'c'. - assert(IsSpecialByte(c)); - if (c == kEscape1) { - if (result) { - AppendBytes(result, copy_start, start - copy_start - 1); - } - // kEscape1 kSeparator ends component - // kEscape1 kNullCharacter represents '\0' - const char next = *(start++); - if (next == kSeparator) { - src->remove_prefix(start - src->data()); - return true; - } else if (next == kNullCharacter) { - if (result) { - *result += '\0'; - } - } else { - return false; - } - copy_start = start; - } else { - assert(c == kEscape2); - if (result) { - AppendBytes(result, copy_start, start - copy_start - 1); - } - // kEscape2 kFFCharacter represents '\xff' - // kEscape2 kInfinity is an error - const char next = *(start++); - if (next == kFFCharacter) { - if (result) { - *result += '\xff'; - } - } else { - return false; - } - copy_start = start; - } - } - return false; -} - -bool OrderedCode::ReadString(Slice* src, std::string* result) { - return ReadStringInternal(src, result); -} - -bool OrderedCode::ReadNumIncreasing(Slice* src, uint64_t* result) { - if (src->empty()) { - return false; // Not enough bytes - } - - // Decode length byte - const int len = static_cast((*src)[0]); - - // If len > 0 and src is longer than 1, the first byte of "payload" - // must be non-zero (otherwise the encoding is not minimal). - // In opt mode, we don't enforce that encodings must be minimal. - assert(0 == len || src->size() == 1 || (*src)[1] != '\0'); - - if (len + 1 > src->size() || len > 8) { - return false; // Not enough bytes or too many bytes - } - - if (result) { - uint64_t tmp = 0; - for (int i = 0; i < len; i++) { - tmp <<= 8; - tmp |= static_cast((*src)[1 + i]); - } - *result = tmp; - } - src->remove_prefix(len + 1); - return true; -} - -inline static bool ReadInfinityInternal(Slice* src) { - if (src->size() >= 2 && ((*src)[0] == kEscape2) && ((*src)[1] == kInfinity)) { - src->remove_prefix(2); - return true; - } else { - return false; - } -} - -bool OrderedCode::ReadInfinity(Slice* src) { return ReadInfinityInternal(src); } - -inline static bool ReadStringOrInfinityInternal(Slice* src, std::string* result, - bool* inf) { - if (ReadInfinityInternal(src)) { - if (inf) *inf = true; - return true; - } - - // We don't use ReadStringInternal here because that would inline - // the whole encoded string parsing code here. Depending on INVERT, only - // one of the following two calls will be generated at compile time. - bool success = OrderedCode::ReadString(src, result); - if (success) { - if (inf) *inf = false; - return true; - } else { - return false; - } -} - -bool OrderedCode::ReadStringOrInfinity(Slice* src, std::string* result, - bool* inf) { - return ReadStringOrInfinityInternal(src, result, inf); -} - -bool OrderedCode::ReadTrailingString(Slice* src, std::string* result) { - if (result) result->assign(src->data(), src->size()); - src->remove_prefix(src->size()); - return true; -} - -void OrderedCode::TEST_Corrupt(std::string* str, int k) { - int seen_seps = 0; - for (int i = 0; i < str->size() - 1; i++) { - if ((*str)[i] == kEscape1 && (*str)[i + 1] == kSeparator) { - seen_seps++; - if (seen_seps == k) { - (*str)[i + 1] = kSeparator + 1; - return; - } - } - } -} - -// Signed number encoding/decoding ///////////////////////////////////// -// -// The format is as follows: -// -// The first bit (the most significant bit of the first byte) -// represents the sign, 0 if the number is negative and -// 1 if the number is >= 0. -// -// Any unbroken sequence of successive bits with the same value as the sign -// bit, up to 9 (the 8th and 9th are the most significant bits of the next -// byte), are size bits that count the number of bytes after the first byte. -// That is, the total length is between 1 and 10 bytes. -// -// The value occupies the bits after the sign bit and the "size bits" -// till the end of the string, in network byte order. If the number -// is negative, the bits are in 2-complement. -// -// -// Example 1: number 0x424242 -> 4 byte big-endian hex string 0xf0424242: -// -// +---------------+---------------+---------------+---------------+ -// 1 1 1 1 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 0 -// +---------------+---------------+---------------+---------------+ -// ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ -// | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | -// | | | | payload: the remaining bits after the sign and size bits -// | | | | and the delimiter bit, the value is 0x424242 -// | | | | -// | size bits: 3 successive bits with the same value as the sign bit -// | (followed by a delimiter bit with the opposite value) -// | mean that there are 3 bytes after the first byte, 4 total -// | -// sign bit: 1 means that the number is non-negative -// -// Example 2: negative number -0x800 -> 2 byte big-endian hex string 0x3800: -// -// +---------------+---------------+ -// 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 -// +---------------+---------------+ -// ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ -// | | | | | | | | | | | | | | | | | | | | | | | | | | | | | -// | | payload: the remaining bits after the sign and size bits and the -// | | delimiter bit, 2-complement because of the negative sign, -// | | value is ~0x7ff, represents the value -0x800 -// | | -// | size bits: 1 bit with the same value as the sign bit -// | (followed by a delimiter bit with the opposite value) -// | means that there is 1 byte after the first byte, 2 total -// | -// sign bit: 0 means that the number is negative -// -// -// Compared with the simpler unsigned format used for uint64_t numbers, -// this format is more compact for small numbers, namely one byte encodes -// numbers in the range [-64,64), two bytes cover the range [-2^13,2^13), etc. -// In general, n bytes encode numbers in the range [-2^(n*7-1),2^(n*7-1)). -// (The cross-over point for compactness of representation is 8 bytes, -// where this format only covers the range [-2^55,2^55), -// whereas an encoding with sign bit and length in the first byte and -// payload in all following bytes would cover [-2^56,2^56).) - -static const int kMaxSigned64Length = 10; - -// This array maps encoding length to header bits in the first two bytes. -static const char kLengthToHeaderBits[1 + kMaxSigned64Length][2] = { - {0, 0}, {'\x80', 0}, {'\xc0', 0}, {'\xe0', 0}, - {'\xf0', 0}, {'\xf8', 0}, {'\xfc', 0}, {'\xfe', 0}, - {'\xff', 0}, {'\xff', '\x80'}, {'\xff', '\xc0'}}; - -// This array maps encoding lengths to the header bits that overlap with -// the payload and need fixing when reading. -static const uint64_t kLengthToMask[1 + kMaxSigned64Length] = { - 0ULL, - 0x80ULL, - 0xc000ULL, - 0xe00000ULL, - 0xf0000000ULL, - 0xf800000000ULL, - 0xfc0000000000ULL, - 0xfe000000000000ULL, - 0xff00000000000000ULL, - 0x8000000000000000ULL, - 0ULL}; - -// This array maps the number of bits in a number to the encoding -// length produced by WriteSignedNumIncreasing. -// For positive numbers, the number of bits is 1 plus the most significant -// bit position (the highest bit position in a positive int64_t is 63). -// For a negative number n, we count the bits in ~n. -// That is, length = kBitsToLength[Bits::Log2Floor64(n < 0 ? ~n : n) + 1]. -static const int8_t kBitsToLength[1 + 63] = { - 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 4, - 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 7, 7, - 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 10}; - -// Calculates the encoding length in bytes of the signed number n. -static inline int SignedEncodingLength(int64_t n) { - return kBitsToLength[Bits::Log2Floor64(n < 0 ? ~n : n) + 1]; -} - -// Slightly faster version for n > 0. -static inline int SignedEncodingLengthPositive(int64_t n) { - return kBitsToLength[Bits::Log2FloorNonZero64(n) + 1]; -} - -void OrderedCode::WriteSignedNumIncreasing(std::string* dest, int64_t val) { - const uint64_t x = val < 0 ? ~val : val; - if (x < 64) { // fast path for encoding length == 1 - *dest += kLengthToHeaderBits[1][0] ^ val; - return; - } - // buf = val in network byte order, sign extended to 10 bytes - const char sign_byte = val < 0 ? '\xff' : '\0'; - char buf[10] = { - sign_byte, sign_byte, - }; - UNALIGNED_STORE64(buf + 2, absl::ghtonll(val)); - - static_assert(sizeof(buf) == kMaxSigned64Length, "max length size mismatch"); - const int len = SignedEncodingLengthPositive(x); - assert(len >= 2); - char* const begin = buf + sizeof(buf) - len; - begin[0] ^= kLengthToHeaderBits[len][0]; - begin[1] ^= kLengthToHeaderBits[len][1]; // ok because len >= 2 - dest->append(begin, len); -} - -bool OrderedCode::ReadSignedNumIncreasing(Slice* src, int64_t* result) { - if (src->empty()) return false; - const uint64_t xor_mask = (!((*src)[0] & 0x80)) ? ~0ULL : 0ULL; - const unsigned char first_byte = (*src)[0] ^ (xor_mask & 0xff); - - // now calculate and test length, and set x to raw (unmasked) result - int len; - uint64_t x; - if (first_byte != 0xff) { - len = 7 - Bits::Log2FloorNonZero(first_byte ^ 0xff); - if (src->size() < len) return false; - x = xor_mask; // sign extend using xor_mask - for (int i = 0; i < len; ++i) - x = (x << 8) | static_cast((*src)[i]); - } else { - len = 8; - if (src->size() < len) return false; - const unsigned char second_byte = (*src)[1] ^ (xor_mask & 0xff); - if (second_byte >= 0x80) { - if (second_byte < 0xc0) { - len = 9; - } else { - const unsigned char third_byte = (*src)[2] ^ (xor_mask & 0xff); - if (second_byte == 0xc0 && third_byte < 0x80) { - len = 10; - } else { - return false; // either len > 10 or len == 10 and #bits > 63 - } - } - if (src->size() < len) return false; - } - x = absl::gntohll(UNALIGNED_LOAD64(src->data() + len - 8)); - } - - x ^= kLengthToMask[len]; // remove spurious header bits - - assert(len == SignedEncodingLength(x)); - - if (result) *result = x; - src->remove_prefix(len); - return true; -} - -} // namespace Firestore - diff --git a/Firestore/Port/ordered_code.h b/Firestore/Port/ordered_code.h deleted file mode 100644 index 7c390a5..0000000 --- a/Firestore/Port/ordered_code.h +++ /dev/null @@ -1,116 +0,0 @@ -/* - * Copyright 2017 Google - * - * 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 module provides routines for encoding a sequence of typed -// entities into a string. The resulting strings can be -// lexicographically compared to yield the same comparison value that -// would have been generated if the encoded items had been compared -// one by one according to their type. -// -// More precisely, suppose: -// 1. string A is generated by encoding the sequence of items [A_1..A_n] -// 2. string B is generated by encoding the sequence of items [B_1..B_n] -// 3. The types match; i.e., for all i: A_i was encoded using -// the same routine as B_i -// Then: -// Comparing A vs. B lexicographically is the same as comparing -// the vectors [A_1..A_n] and [B_1..B_n] lexicographically. -// -// Furthermore, if n < m, the encoding of [A_1..A_n] is a strict prefix of -// [A_1..A_m] (unless m = n+1 and A_m is the empty string encoded with -// WriteTrailingString, in which case the encodings are equal). -// -// This module is often useful when generating multi-part sstable -// keys that have to be ordered in a particular fashion. - -#ifndef IPHONE_FIRESTORE_PORT_ORDERED_CODE_H_ -#define IPHONE_FIRESTORE_PORT_ORDERED_CODE_H_ - -#include - -namespace leveldb { -class Slice; -} - -namespace Firestore { - -class OrderedCode { - public: - // ------------------------------------------------------------------- - // Encoding routines: each one of the following routines append - // one item to "*dest". The Write(Signed)NumIncreasing() and - // Write(Signed)NumDecreasing() routines differ in whether the resulting - // encoding is ordered by increasing number or decreasing number. - // Similarly, WriteString() and WriteStringDecreasing() differ in whether - // the resulting encoding is ordered by the original string in - // lexicographically increasing or decreasing order. WriteString() - // is not called WriteStringIncreasing() for convenience and backward - // compatibility. - - static void WriteString(std::string* dest, leveldb::Slice str); - static void WriteNumIncreasing(std::string* dest, uint64_t num); - static void WriteSignedNumIncreasing(std::string* dest, int64_t num); - - // Creates an encoding for the "infinite string", a value considered to - // be lexicographically after any real string. Note that in the case of - // WriteInfinityDecreasing(), this would come before any real string as - // the ordering puts lexicographically greater values first. - static void WriteInfinity(std::string* dest); - - // Special string append that can only be used at the tail end of - // an encoded string -- blindly appends "str" to "*dest". - static void WriteTrailingString(std::string* dest, leveldb::Slice str); - - // ------------------------------------------------------------------- - // Decoding routines: these extract an item earlier encoded using - // the corresponding WriteXXX() routines above. The item is read - // from "*src"; "*src" is modified to point past the decoded item; - // and if "result" is non-NULL, "*result" is modified to contain the - // result. In case of string result, the decoded string is appended to - // "*result". Returns true if the next item was read successfully, false - // otherwise. - - static bool ReadString(leveldb::Slice* src, std::string* result); - static bool ReadNumIncreasing(leveldb::Slice* src, uint64_t* result); - static bool ReadSignedNumIncreasing(leveldb::Slice* src, int64_t* result); - - static bool ReadInfinity(leveldb::Slice* src); - static bool ReadTrailingString(leveldb::Slice* src, std::string* result); - - // REQUIRES: next item was encoded by WriteInfinity() or WriteString() - static bool ReadStringOrInfinity(leveldb::Slice* src, std::string* result, bool* inf); - - // Helper for testing: corrupt "*str" by changing the kth item separator - // in the string. - static void TEST_Corrupt(std::string* str, int k); - - // Helper for testing. - // SkipToNextSpecialByte is an internal routine defined in the .cc file - // with the following semantics. Return a pointer to the first byte - // in the range "[start..limit)" whose value is 0 or 255. If no such - // byte exists in the range, returns "limit". - static const char* TEST_SkipToNextSpecialByte(const char* start, const char* limit); - - // Not an instantiable class, but the class exists to make it easy to - // use with a single using statement. - OrderedCode() = delete; - OrderedCode(const OrderedCode&) = delete; - OrderedCode& operator=(const OrderedCode&) = delete; -}; - -} // namespace Firestore - -#endif // IPHONE_FIRESTORE_PORT_ORDERED_CODE_H_ diff --git a/Firestore/Port/ordered_code_test.cc b/Firestore/Port/ordered_code_test.cc deleted file mode 100644 index 0a339fc..0000000 --- a/Firestore/Port/ordered_code_test.cc +++ /dev/null @@ -1,528 +0,0 @@ -/* - * Copyright 2017 Google - * - * 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 "Firestore/Port/ordered_code.h" - -// #include -// #include -#include -#include - -#include "base/logging.h" -#include "testing/base/public/gunit.h" -#include -#include "util/random/acmrandom.h" - -using Firestore::OrderedCode; -using leveldb::Slice; - -// Make Slices writeable to ostream, making all the CHECKs happy below. -namespace { -void WritePadding(std::ostream& o, size_t pad) { - char fill_buf[32]; - memset(fill_buf, o.fill(), sizeof(fill_buf)); - while (pad) { - size_t n = std::min(pad, sizeof(fill_buf)); - o.write(fill_buf, n); - pad -= n; - } -} -} // namespace - -namespace leveldb { - -std::ostream& operator<<(std::ostream& o, const Slice slice) { - std::ostream::sentry sentry(o); - if (sentry) { - size_t lpad = 0; - size_t rpad = 0; - if (o.width() > slice.size()) { - size_t pad = o.width() - slice.size(); - if ((o.flags() & o.adjustfield) == o.left) { - rpad = pad; - } else { - lpad = pad; - } - } - if (lpad) WritePadding(o, lpad); - o.write(slice.data(), slice.size()); - if (rpad) WritePadding(o, rpad); - o.width(0); - } - return o; -} - -} // namespace leveldb - -static std::string RandomString(ACMRandom* rnd, int len) { - std::string x; - for (int i = 0; i < len; i++) { - x += rnd->Uniform(256); - } - return x; -} - -// --------------------------------------------------------------------- -// Utility template functions (they help templatize the tests below) - -// Read/WriteIncreasing are defined for string, uint64_t, int64_t below. -template -static void OCWriteIncreasing(std::string* dest, const T& val); -template -static bool OCReadIncreasing(Slice* src, T* result); - -// Read/WriteIncreasing -template <> -void OCWriteIncreasing(std::string* dest, const std::string& val) { - OrderedCode::WriteString(dest, val); -} -template <> -bool OCReadIncreasing(Slice* src, std::string* result) { - return OrderedCode::ReadString(src, result); -} - -// Read/WriteIncreasing -template <> -void OCWriteIncreasing(std::string* dest, const uint64_t& val) { - OrderedCode::WriteNumIncreasing(dest, val); -} -template <> -bool OCReadIncreasing(Slice* src, uint64_t* result) { - return OrderedCode::ReadNumIncreasing(src, result); -} - -enum Direction { INCREASING = 0 }; - -// Read/WriteIncreasing -template <> -void OCWriteIncreasing(std::string* dest, const int64_t& val) { - OrderedCode::WriteSignedNumIncreasing(dest, val); -} -template <> -bool OCReadIncreasing(Slice* src, int64_t* result) { - return OrderedCode::ReadSignedNumIncreasing(src, result); -} - -template -std::string OCWrite(T val, Direction direction) { - std::string result; - OCWriteIncreasing(&result, val); - return result; -} - -template -void OCWriteToString(std::string* result, T val, Direction direction) { - OCWriteIncreasing(result, val); -} - -template -bool OCRead(Slice* s, T* val, Direction direction) { - return OCReadIncreasing(s, val); -} - -// --------------------------------------------------------------------- -// Numbers - -template -static T TestRead(Direction d, const std::string& a) { - // gracefully reject any proper prefix of an encoding - for (int i = 0; i < a.size() - 1; ++i) { - Slice s(a.data(), i); - CHECK(!OCRead(&s, NULL, d)); - CHECK_EQ(s, a.substr(0, i)); - } - - Slice s(a); - T v; - CHECK(OCRead(&s, &v, d)); - CHECK(s.empty()); - return v; -} - -template -static void TestWriteRead(Direction d, T expected) { - EXPECT_EQ(expected, TestRead(d, OCWrite(expected, d))); -} - -// Verifies that the second Write* call appends a non-empty std::string to its -// output. -template -static void TestWriteAppends(Direction d, T first, U second) { - std::string encoded; - OCWriteToString(&encoded, first, d); - std::string encoded_first_only = encoded; - OCWriteToString(&encoded, second, d); - EXPECT_NE(encoded, encoded_first_only); - EXPECT_TRUE(Slice(encoded).starts_with(encoded_first_only)); -} - -template -static void TestNumbers(T multiplier) { - for (int j = 0; j < 2; ++j) { - const Direction d = static_cast(j); - - // first test powers of 2 (and nearby numbers) - for (T x = std::numeric_limits().max(); x != 0; x /= 2) { - TestWriteRead(d, multiplier * (x - 1)); - TestWriteRead(d, multiplier * x); - if (x != std::numeric_limits::max()) { - TestWriteRead(d, multiplier * (x + 1)); - } else if (multiplier < 0 && multiplier == -1) { - TestWriteRead(d, -x - 1); - } - } - - ACMRandom rnd(301); - for (int bits = 1; bits <= std::numeric_limits().digits; ++bits) { - // test random non-negative numbers with given number of significant bits - const uint64_t mask = (~0ULL) >> (64 - bits); - for (int i = 0; i < 1000; i++) { - T x = rnd.Next64() & mask; - TestWriteRead(d, multiplier * x); - T y = rnd.Next64() & mask; - TestWriteAppends(d, multiplier * x, multiplier * y); - } - } - } -} - -// Return true iff 'a' is "before" 'b' according to 'direction' -static bool CompareStrings(const std::string& a, const std::string& b, - Direction d) { - return (INCREASING == d) ? (a < b) : (b < a); -} - -template -static void TestNumberOrdering() { - const Direction d = INCREASING; - - // first the negative numbers (if T is signed, otherwise no-op) - std::string laststr = OCWrite(std::numeric_limits().min(), d); - for (T num = std::numeric_limits().min() / 2; num != 0; num /= 2) { - std::string strminus1 = OCWrite(num - 1, d); - std::string str = OCWrite(num, d); - std::string strplus1 = OCWrite(num + 1, d); - - CHECK(CompareStrings(strminus1, str, d)); - CHECK(CompareStrings(str, strplus1, d)); - - // Compare 'str' with 'laststr'. When we approach 0, 'laststr' is - // not necessarily before 'strminus1'. - CHECK(CompareStrings(laststr, str, d)); - laststr = str; - } - - // then the positive numbers - laststr = OCWrite(0, d); - T num = 1; - while (num < std::numeric_limits().max() / 2) { - num *= 2; - std::string strminus1 = OCWrite(num - 1, d); - std::string str = OCWrite(num, d); - std::string strplus1 = OCWrite(num + 1, d); - - CHECK(CompareStrings(strminus1, str, d)); - CHECK(CompareStrings(str, strplus1, d)); - - // Compare 'str' with 'laststr'. - CHECK(CompareStrings(laststr, str, d)); - laststr = str; - } -} - -// Helper routine for testing TEST_SkipToNextSpecialByte -static int FindSpecial(const std::string& x) { - const char* p = x.data(); - const char* limit = p + x.size(); - const char* result = OrderedCode::TEST_SkipToNextSpecialByte(p, limit); - return result - p; -} - -TEST(OrderedCode, SkipToNextSpecialByte) { - for (int len = 0; len < 256; len++) { - ACMRandom rnd(301); - std::string x; - while (x.size() < len) { - char c = 1 + rnd.Uniform(254); - ASSERT_NE(c, 0); - ASSERT_NE(c, 255); - x += c; // No 0 bytes, no 255 bytes - } - EXPECT_EQ(FindSpecial(x), x.size()); - for (int special_pos = 0; special_pos < len; special_pos++) { - for (int special_test = 0; special_test < 2; special_test++) { - const char special_byte = (special_test == 0) ? 0 : 255; - std::string y = x; - y[special_pos] = special_byte; - EXPECT_EQ(FindSpecial(y), special_pos); - if (special_pos < 16) { - // Add some special bytes after the one at special_pos to make sure - // we still return the earliest special byte in the string - for (int rest = special_pos + 1; rest < len; rest++) { - if (rnd.OneIn(3)) { - y[rest] = rnd.OneIn(2) ? 0 : 255; - EXPECT_EQ(FindSpecial(y), special_pos); - } - } - } - } - } - } -} - -TEST(OrderedCode, ExhaustiveFindSpecial) { - char buf[16]; - char* limit = buf + sizeof(buf); - int count = 0; - for (int start_offset = 0; start_offset <= 5; start_offset += 5) { - // We test exhaustively with all combinations of 3 bytes starting - // at offset 0 and offset 5 (so as to test with the bytes at both - // ends of a 64-bit word). - for (char& c : buf) { - c = 'a'; // Not a special byte - } - for (int b0 = 0; b0 < 256; b0++) { - for (int b1 = 0; b1 < 256; b1++) { - for (int b2 = 0; b2 < 256; b2++) { - buf[start_offset + 0] = b0; - buf[start_offset + 1] = b1; - buf[start_offset + 2] = b2; - char* expected; - if (b0 == 0 || b0 == 255) { - expected = &buf[start_offset]; - } else if (b1 == 0 || b1 == 255) { - expected = &buf[start_offset + 1]; - } else if (b2 == 0 || b2 == 255) { - expected = &buf[start_offset + 2]; - } else { - expected = limit; - } - count++; - EXPECT_EQ(expected, - OrderedCode::TEST_SkipToNextSpecialByte(buf, limit)); - } - } - } - } - EXPECT_EQ(count, 256 * 256 * 256 * 2); -} - -TEST(Uint64, EncodeDecode) { TestNumbers(1); } - -TEST(Uint64, Ordering) { TestNumberOrdering(); } - -TEST(Int64, EncodeDecode) { - TestNumbers(1); - TestNumbers(-1); -} - -TEST(Int64, Ordering) { TestNumberOrdering(); } - -// Returns the bitwise complement of s. -static inline std::string StrNot(const std::string& s) { - std::string result; - for (const char c : s) result.push_back(~c); - return result; -} - -template -static void TestInvalidEncoding(Direction d, const std::string& s) { - Slice p(s); - EXPECT_FALSE(OCRead(&p, static_cast(NULL), d)); - EXPECT_EQ(s, p); -} - -TEST(OrderedCodeInvalidEncodingsTest, Overflow) { - // 1U << 64, increasing - const std::string k2xx64U = "\x09\x01" + std::string(8, 0); - TestInvalidEncoding(INCREASING, k2xx64U); - - // 1 << 63 and ~(1 << 63), increasing - const std::string k2xx63 = "\xff\xc0\x80" + std::string(7, 0); - TestInvalidEncoding(INCREASING, k2xx63); - TestInvalidEncoding(INCREASING, StrNot(k2xx63)); -} - -TEST(OrderedCodeInvalidEncodingsTest, NonCanonical) { - // Test DCHECK failures of "ambiguous"/"non-canonical" encodings. - // These are non-minimal (but otherwise "valid") encodings that - // differ from the minimal encoding chosen by OrderedCode::WriteXXX - // and thus should be avoided to not mess up the string ordering of - // encodings. - - ACMRandom rnd(301); - - for (int n = 2; n <= 9; ++n) { - // The zero in non_minimal[1] is "redundant". - std::string non_minimal = - std::string(1, n - 1) + std::string(1, 0) + RandomString(&rnd, n - 2); - EXPECT_EQ(n, non_minimal.length()); - - EXPECT_NE(OCWrite(0, INCREASING), non_minimal); - if (DEBUG_MODE) { - Slice s(non_minimal); - EXPECT_DEATH_IF_SUPPORTED(OrderedCode::ReadNumIncreasing(&s, NULL), - "ssertion failed"); - } else { - TestRead(INCREASING, non_minimal); - } - } - - for (int n = 2; n <= 10; ++n) { - // Header with 1 sign bit and n-1 size bits. - std::string header = - std::string(n / 8, 0xff) + std::string(1, 0xff << (8 - (n % 8))); - // There are more than 7 zero bits between header bits and "payload". - std::string non_minimal = - header + std::string(1, rnd.Uniform(256) & ~*header.rbegin()) + - RandomString(&rnd, n - header.length() - 1); - EXPECT_EQ(n, non_minimal.length()); - - EXPECT_NE(OCWrite(0, INCREASING), non_minimal); - if (DEBUG_MODE) { - Slice s(non_minimal); - EXPECT_DEATH_IF_SUPPORTED(OrderedCode::ReadSignedNumIncreasing(&s, NULL), - "ssertion failed") - << n; - s = non_minimal; - } else { - TestRead(INCREASING, non_minimal); - } - } -} - -// --------------------------------------------------------------------- -// Strings - -TEST(String, Infinity) { - const std::string value("\xff\xff foo"); - bool is_inf; - std::string encoding, parsed; - Slice s; - - // Check encoding/decoding of "infinity" for ascending order - encoding.clear(); - OrderedCode::WriteInfinity(&encoding); - encoding.push_back('a'); - s = encoding; - EXPECT_TRUE(OrderedCode::ReadInfinity(&s)); - EXPECT_EQ(1, s.size()); - s = encoding; - is_inf = false; - EXPECT_TRUE(OrderedCode::ReadStringOrInfinity(&s, NULL, &is_inf)); - EXPECT_EQ(1, s.size()); - EXPECT_TRUE(is_inf); - - // Check ReadStringOrInfinity() can parse ordinary strings - encoding.clear(); - OrderedCode::WriteString(&encoding, value); - encoding.push_back('a'); - s = encoding; - is_inf = false; - parsed.clear(); - EXPECT_TRUE(OrderedCode::ReadStringOrInfinity(&s, &parsed, &is_inf)); - EXPECT_EQ(1, s.size()); - EXPECT_FALSE(is_inf); - EXPECT_EQ(value, parsed); -} - -TEST(String, EncodeDecode) { - ACMRandom rnd(301); - for (int i = 0; i < 2; ++i) { - const Direction d = static_cast(i); - - for (int len = 0; len < 256; len++) { - const std::string a = RandomString(&rnd, len); - TestWriteRead(d, a); - for (int len2 = 0; len2 < 64; len2++) { - const std::string b = RandomString(&rnd, len2); - - TestWriteAppends(d, a, b); - - std::string out; - OCWriteToString(&out, a, d); - OCWriteToString(&out, b, d); - - std::string a2, b2, dummy; - Slice s = out; - Slice s2 = out; - CHECK(OCRead(&s, &a2, d)); - CHECK(OCRead(&s2, NULL, d)); - CHECK_EQ(s, s2); - - CHECK(OCRead(&s, &b2, d)); - CHECK(OCRead(&s2, NULL, d)); - CHECK_EQ(s, s2); - - CHECK(!OCRead(&s, &dummy, d)); - CHECK(!OCRead(&s2, NULL, d)); - CHECK_EQ(a, a2); - CHECK_EQ(b, b2); - CHECK(s.empty()); - CHECK(s2.empty()); - } - } - } -} - -// 'str' is a static C-style string that may contain '\0' -#define STATIC_STR(str) Slice((str), sizeof(str) - 1) - -static std::string EncodeStringIncreasing(Slice value) { - std::string encoded; - OrderedCode::WriteString(&encoded, value); - return encoded; -} - -TEST(String, Increasing) { - // Here are a series of strings in non-decreasing order, including - // consecutive strings such that the second one is equal to, a proper - // prefix of, or has the same length as the first one. Most also contain - // the special escaping characters '\x00' and '\xff'. - ASSERT_EQ(EncodeStringIncreasing(STATIC_STR("")), - EncodeStringIncreasing(STATIC_STR(""))); - - ASSERT_LT(EncodeStringIncreasing(STATIC_STR("")), - EncodeStringIncreasing(STATIC_STR("\x00"))); - - ASSERT_EQ(EncodeStringIncreasing(STATIC_STR("\x00")), - EncodeStringIncreasing(STATIC_STR("\x00"))); - - ASSERT_LT(EncodeStringIncreasing(STATIC_STR("\x00")), - EncodeStringIncreasing(STATIC_STR("\x01"))); - - ASSERT_LT(EncodeStringIncreasing(STATIC_STR("\x01")), - EncodeStringIncreasing(STATIC_STR("a"))); - - ASSERT_EQ(EncodeStringIncreasing(STATIC_STR("a")), - EncodeStringIncreasing(STATIC_STR("a"))); - - ASSERT_LT(EncodeStringIncreasing(STATIC_STR("a")), - EncodeStringIncreasing(STATIC_STR("aa"))); - - ASSERT_LT(EncodeStringIncreasing(STATIC_STR("aa")), - EncodeStringIncreasing(STATIC_STR("\xff"))); - - ASSERT_LT(EncodeStringIncreasing(STATIC_STR("\xff")), - EncodeStringIncreasing(STATIC_STR("\xff\x00"))); - - ASSERT_LT(EncodeStringIncreasing(STATIC_STR("\xff\x00")), - EncodeStringIncreasing(STATIC_STR("\xff\x01"))); - - std::string infinity; - OrderedCode::WriteInfinity(&infinity); - ASSERT_LT(EncodeStringIncreasing(std::string(1 << 20, '\xff')), infinity); -} diff --git a/Firestore/Source/Local/FSTLevelDBKey.mm b/Firestore/Source/Local/FSTLevelDBKey.mm index 074d5c5..9850fff 100644 --- a/Firestore/Source/Local/FSTLevelDBKey.mm +++ b/Firestore/Source/Local/FSTLevelDBKey.mm @@ -18,13 +18,14 @@ #include -#include "Firestore/Port/ordered_code.h" #import "Firestore/Source/Model/FSTDocumentKey.h" #import "Firestore/Source/Model/FSTPath.h" +#include "Firestore/core/src/firebase/firestore/util/ordered_code.h" + NS_ASSUME_NONNULL_BEGIN -using Firestore::OrderedCode; +using firebase::firestore::util::OrderedCode; using Firestore::StringView; using leveldb::Slice; @@ -109,11 +110,11 @@ void WriteComponentLabel(std::string *dest, FSTComponentLabel label) { */ BOOL ReadComponentLabel(leveldb::Slice *contents, FSTComponentLabel *label) { int64_t rawResult = 0; - Slice tmp = *contents; + absl::string_view tmp(contents->data(), contents->size()); if (OrderedCode::ReadSignedNumIncreasing(&tmp, &rawResult)) { if (rawResult >= FSTComponentLabelTerminator && rawResult <= FSTComponentLabelUnknown) { *label = static_cast(rawResult); - *contents = tmp; + *contents = leveldb::Slice(tmp.data(), tmp.size()); return YES; } } @@ -128,9 +129,9 @@ BOOL ReadComponentLabel(leveldb::Slice *contents, FSTComponentLabel *label) { * * If the read is successful, returns YES and contents will be updated to the next unread byte. */ -BOOL ReadComponentLabelMatching(Slice *contents, FSTComponentLabel expectedLabel) { +BOOL ReadComponentLabelMatching(absl::string_view *contents, FSTComponentLabel expectedLabel) { int64_t rawResult = 0; - Slice tmp = *contents; + absl::string_view tmp = *contents; if (OrderedCode::ReadSignedNumIncreasing(&tmp, &rawResult)) { if (rawResult == expectedLabel) { *contents = tmp; @@ -152,10 +153,10 @@ BOOL ReadComponentLabelMatching(Slice *contents, FSTComponentLabel expectedLabel */ BOOL ReadInt32(Slice *contents, int32_t *result) { int64_t rawResult = 0; - Slice tmp = *contents; + absl::string_view tmp(contents->data(), contents->size()); if (OrderedCode::ReadSignedNumIncreasing(&tmp, &rawResult)) { if (rawResult >= INT32_MIN && rawResult <= INT32_MAX) { - *contents = tmp; + *contents = leveldb::Slice(tmp.data(), tmp.size()); *result = static_cast(rawResult); return YES; } @@ -180,10 +181,11 @@ void WriteLabeledInt32(std::string *dest, FSTComponentLabel label, int32_t value * value will be set to the decoded integer value. */ BOOL ReadLabeledInt32(Slice *contents, FSTComponentLabel expectedLabel, int32_t *value) { - Slice tmp = *contents; + absl::string_view tmp(contents->data(), contents->size()); if (ReadComponentLabelMatching(&tmp, expectedLabel)) { - if (ReadInt32(&tmp, value)) { - *contents = tmp; + Slice tmpSlice = leveldb::Slice(tmp.data(), tmp.size()); + if (ReadInt32(&tmpSlice, value)) { + *contents = tmpSlice; return YES; } } @@ -207,10 +209,10 @@ void WriteLabeledString(std::string *dest, FSTComponentLabel label, StringView v * value will be set to the decoded string value. */ BOOL ReadLabeledString(Slice *contents, FSTComponentLabel expectedLabel, std::string *value) { - Slice tmp = *contents; + absl::string_view tmp(contents->data(), contents->size()); if (ReadComponentLabelMatching(&tmp, expectedLabel)) { if (OrderedCode::ReadString(&tmp, value)) { - *contents = tmp; + *contents = leveldb::Slice(tmp.data(), tmp.size()); return YES; } } @@ -272,7 +274,7 @@ BOOL ReadDocumentKey(Slice *contents, FSTDocumentKey *__strong *result) { for (;;) { // Advance a temporary slice to avoid advancing contents into the next key component which may // not be a path segment. - Slice readPosition = completeSegments; + absl::string_view readPosition(completeSegments.data(), completeSegments.size()); if (!ReadComponentLabelMatching(&readPosition, FSTComponentLabelPathSegment)) { break; } @@ -284,7 +286,7 @@ BOOL ReadDocumentKey(Slice *contents, FSTDocumentKey *__strong *result) { [pathSegments addObject:pathSegment]; segment.clear(); - completeSegments = readPosition; + completeSegments = leveldb::Slice(readPosition.data(), readPosition.size()); } FSTResourcePath *path = [FSTResourcePath pathWithSegments:pathSegments]; @@ -304,7 +306,10 @@ inline void WriteTerminator(std::string *dest) { } inline BOOL ReadTerminator(Slice *contents) { - return ReadComponentLabelMatching(contents, FSTComponentLabelTerminator); + absl::string_view tmp(contents->data(), contents->size()); + BOOL result = ReadComponentLabelMatching(&tmp, FSTComponentLabelTerminator); + *contents = leveldb::Slice(tmp.data(), tmp.size()); + return result; } inline void WriteTableName(std::string *dest, const char *tableName) { diff --git a/Firestore/Source/Local/FSTLevelDBMutationQueue.mm b/Firestore/Source/Local/FSTLevelDBMutationQueue.mm index 74463ee..dbe58e8 100644 --- a/Firestore/Source/Local/FSTLevelDBMutationQueue.mm +++ b/Firestore/Source/Local/FSTLevelDBMutationQueue.mm @@ -34,12 +34,10 @@ #import "Firestore/Source/Model/FSTPath.h" #import "Firestore/Source/Util/FSTAssert.h" -#include "Firestore/Port/ordered_code.h" #include "Firestore/core/src/firebase/firestore/util/string_util.h" NS_ASSUME_NONNULL_BEGIN -using Firestore::OrderedCode; using Firestore::StringView; using leveldb::DB; using leveldb::Iterator; diff --git a/Firestore/Source/Local/FSTLevelDBQueryCache.mm b/Firestore/Source/Local/FSTLevelDBQueryCache.mm index 5feb9f1..46af918 100644 --- a/Firestore/Source/Local/FSTLevelDBQueryCache.mm +++ b/Firestore/Source/Local/FSTLevelDBQueryCache.mm @@ -29,11 +29,8 @@ #import "Firestore/Source/Model/FSTDocumentKey.h" #import "Firestore/Source/Util/FSTAssert.h" -#include "Firestore/Port/ordered_code.h" - NS_ASSUME_NONNULL_BEGIN -using Firestore::OrderedCode; using Firestore::StringView; using leveldb::DB; using leveldb::Iterator; diff --git a/Firestore/Source/Local/FSTLevelDBRemoteDocumentCache.mm b/Firestore/Source/Local/FSTLevelDBRemoteDocumentCache.mm index 039712c..b842cb5 100644 --- a/Firestore/Source/Local/FSTLevelDBRemoteDocumentCache.mm +++ b/Firestore/Source/Local/FSTLevelDBRemoteDocumentCache.mm @@ -32,11 +32,8 @@ #import "Firestore/Source/Model/FSTPath.h" #import "Firestore/Source/Util/FSTAssert.h" -#include "Firestore/Port/ordered_code.h" - NS_ASSUME_NONNULL_BEGIN -using Firestore::OrderedCode; using leveldb::DB; using leveldb::Iterator; using leveldb::ReadOptions; diff --git a/Firestore/Source/Local/FSTWriteGroup.mm b/Firestore/Source/Local/FSTWriteGroup.mm index 6859d53..80d09ca 100644 --- a/Firestore/Source/Local/FSTWriteGroup.mm +++ b/Firestore/Source/Local/FSTWriteGroup.mm @@ -23,9 +23,6 @@ #import "Firestore/Source/Local/FSTLevelDBKey.h" #import "Firestore/Source/Util/FSTAssert.h" -#include "Firestore/Port/ordered_code.h" - -using Firestore::OrderedCode; using Firestore::StringView; using leveldb::DB; using leveldb::Slice; diff --git a/Firestore/Source/Local/StringView.h b/Firestore/Source/Local/StringView.h index b81b7b5..8156193 100644 --- a/Firestore/Source/Local/StringView.h +++ b/Firestore/Source/Local/StringView.h @@ -25,6 +25,7 @@ #include #include +#include "absl/strings/string_view.h" namespace Firestore { @@ -64,6 +65,10 @@ class StringView { StringView(leveldb::Slice slice) : data_(slice.data()), size_(slice.size()) { } + // Creates a StringView from the absl::string_view. + StringView(absl::string_view s) : data_(s.data()), size_(s.size()) { + } + // Creates a StringView from the given std::string. The string must be an // lvalue for the lifetime requirements to be satisfied. StringView(const std::string &str) : data_(str.data()), size_(str.size()) { @@ -76,6 +81,13 @@ class StringView { return leveldb::Slice(data_, size_); } + // Converts this StringView to a absl::string_view, which is an equivalent (and more + // functional) type. The returned string_view has the same lifetime as this + // StringView. + operator absl::string_view() { + return absl::string_view(data_, size_); + } + private: const char *data_; const size_t size_; diff --git a/Firestore/core/src/firebase/firestore/util/CMakeLists.txt b/Firestore/core/src/firebase/firestore/util/CMakeLists.txt index 51621a0..b763a63 100644 --- a/Firestore/core/src/firebase/firestore/util/CMakeLists.txt +++ b/Firestore/core/src/firebase/firestore/util/CMakeLists.txt @@ -107,11 +107,15 @@ cc_library( SOURCES autoid.cc autoid.h + bits.cc + bits.h comparison.cc comparison.h config.h firebase_assert.h log.h + ordered_code.cc + ordered_code.h secure_random.h string_util.cc string_util.h diff --git a/Firestore/core/src/firebase/firestore/util/bits.cc b/Firestore/core/src/firebase/firestore/util/bits.cc new file mode 100644 index 0000000..0bfe4c3 --- /dev/null +++ b/Firestore/core/src/firebase/firestore/util/bits.cc @@ -0,0 +1,43 @@ +/* + * Copyright 2017 Google + * + * 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 "Firestore/core/src/firebase/firestore/util/bits.h" + +#include "Firestore/core/src/firebase/firestore/util/firebase_assert.h" + +namespace firebase { +namespace firestore { +namespace util { + +int Bits::Log2Floor_Portable(uint32_t n) { + if (n == 0) return -1; + int log = 0; + uint32_t value = n; + for (int i = 4; i >= 0; --i) { + int shift = (1 << i); + uint32_t x = value >> shift; + if (x != 0) { + value = x; + log += shift; + } + } + FIREBASE_ASSERT(value == 1); + return log; +} + +} // namespace util +} // namespace firestore +} // namespace firebase diff --git a/Firestore/core/src/firebase/firestore/util/bits.h b/Firestore/core/src/firebase/firestore/util/bits.h new file mode 100644 index 0000000..185273f --- /dev/null +++ b/Firestore/core/src/firebase/firestore/util/bits.h @@ -0,0 +1,166 @@ +/* + * Copyright 2017 Google + * + * 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 FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_UTIL_BITS_H_ +#define FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_UTIL_BITS_H_ + +// Various bit-twiddling functions, all of which are static members of the Bits +// class (making it effectively a namespace). Operands are unsigned integers. +// Munging bits in _signed_ integers is fraught with peril! For example, +// -5 << n has undefined behavior (for some values of n). + +#include + +class Bits_Port32_Test; +class Bits_Port64_Test; + +namespace firebase { +namespace firestore { +namespace util { + +class Bits { + public: + /** Return floor(log2(n)) for positive integer n. Returns -1 iff n == 0. */ + static int Log2Floor(uint32_t n); + static int Log2Floor64(uint64_t n); + + /** + * Potentially faster version of Log2Floor() that returns an + * undefined value if n == 0. + */ + static int Log2FloorNonZero(uint32_t n); + static int Log2FloorNonZero64(uint64_t n); + + private: + // Portable implementations. + static int Log2Floor_Portable(uint32_t n); + static int Log2Floor64_Portable(uint64_t n); + static int Log2FloorNonZero_Portable(uint32_t n); + static int Log2FloorNonZero64_Portable(uint64_t n); + + Bits(Bits const&) = delete; + void operator=(Bits const&) = delete; + + // Allow tests to call _Portable variants directly. + friend class Bits_Port32_Test; + friend class Bits_Port64_Test; +}; + +// ------------------------------------------------------------------------ +// Implementation details follow +// ------------------------------------------------------------------------ + +#if defined(__GNUC__) + +inline int Bits::Log2Floor(uint32_t n) { + return n == 0 ? -1 : 31 ^ __builtin_clz(n); +} + +inline int Bits::Log2FloorNonZero(uint32_t n) { + return 31 ^ __builtin_clz(n); +} + +inline int Bits::Log2Floor64(uint64_t n) { + return n == 0 ? -1 : 63 ^ __builtin_clzll(n); +} + +inline int Bits::Log2FloorNonZero64(uint64_t n) { + return 63 ^ __builtin_clzll(n); +} + +#elif defined(COMPILER_MSVC) + +inline int Bits::Log2FloorNonZero(uint32 n) { +#ifdef _M_IX86 + _asm { + bsr ebx, n + mov n, ebx + } + return n; +#else + return Bits::Log2FloorNonZero_Portable(n); +#endif +} + +inline int Bits::Log2Floor(uint32 n) { +#ifdef _M_IX86 + _asm { + xor ebx, ebx + mov eax, n + and eax, eax + jz return_ebx + bsr ebx, eax + return_ebx: + mov n, ebx + } + return n; +#else + return Bits::Log2Floor_Portable(n); +#endif +} + +inline int Bits::Log2Floor64(uint64_t n) { + return Bits::Log2Floor64_Portable(n); +} + +inline int Bits::Log2FloorNonZero64(uint64_t n) { + return Bits::Log2FloorNonZero64_Portable(n); +} + +#else // !__GNUC__ && !COMPILER_MSVC + +inline int Bits::Log2Floor64(uint64_t n) { + return Bits::Log2Floor64_Portable(n); +} + +inline int Bits::Log2FloorNonZero64(uint64_t n) { + return Bits::Log2FloorNonZero64_Portable(n); +} + +#endif + +inline int Bits::Log2FloorNonZero_Portable(uint32_t n) { + // Just use the common routine + return Log2Floor(n); +} + +// Log2Floor64() is defined in terms of Log2Floor32(), Log2FloorNonZero32() +inline int Bits::Log2Floor64_Portable(uint64_t n) { + const uint32_t topbits = static_cast(n >> 32); + if (topbits == 0) { + // Top bits are zero, so scan in bottom bits + return Log2Floor(static_cast(n)); + } else { + return 32 + Log2FloorNonZero(topbits); + } +} + +// Log2FloorNonZero64() is defined in terms of Log2FloorNonZero32() +inline int Bits::Log2FloorNonZero64_Portable(uint64_t n) { + const uint32_t topbits = static_cast(n >> 32); + if (topbits == 0) { + // Top bits are zero, so scan in bottom bits + return Log2FloorNonZero(static_cast(n)); + } else { + return 32 + Log2FloorNonZero(topbits); + } +} + +} // namespace util +} // namespace firestore +} // namespace firebase + +#endif // FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_UTIL_BITS_H_ diff --git a/Firestore/core/src/firebase/firestore/util/ordered_code.cc b/Firestore/core/src/firebase/firestore/util/ordered_code.cc new file mode 100644 index 0000000..688f15c --- /dev/null +++ b/Firestore/core/src/firebase/firestore/util/ordered_code.cc @@ -0,0 +1,622 @@ +/* + * Copyright 2017 Google + * + * 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 "Firestore/core/src/firebase/firestore/util/ordered_code.h" + +#include +#include +#include + +#include "Firestore/core/src/firebase/firestore/util/bits.h" +#include "Firestore/core/src/firebase/firestore/util/firebase_assert.h" + +#define UNALIGNED_LOAD32 ABSL_INTERNAL_UNALIGNED_LOAD32 +#define UNALIGNED_LOAD64 ABSL_INTERNAL_UNALIGNED_LOAD64 +#define UNALIGNED_STORE32 ABSL_INTERNAL_UNALIGNED_STORE32 +#define UNALIGNED_STORE64 ABSL_INTERNAL_UNALIGNED_STORE64 + +// We encode a string in different ways depending on whether the item +// should be in lexicographically increasing or decreasing order. +// +// +// Lexicographically increasing order +// +// We want a string-to-string mapping F(x) such that for any two strings +// +// x < y => F(x) < F(y) +// +// In addition to the normal characters '\x00' through '\xff', we want to +// encode a few extra symbols in strings: +// +// Separator between items +// Infinite string +// +// Therefore we need an alphabet with at least 258 symbols. Each +// character '\1' through '\xfe' is mapped to itself. The other four are +// encoded into two-letter sequences starting with '\0' and '\xff': +// +// encoded as => \0\1 +// \0 encoded as => \0\xff +// \xff encoded as => \xff\x00 +// encoded as => \xff\xff +// +// The remaining two-letter sequences starting with '\0' and '\xff' are +// currently unused. +// +// F() is defined above. For any finite string x, F(x) is the +// the encodings of x's characters followed by the encoding for . The +// ordering of two finite strings is the same as the ordering of the +// respective characters at the first position where they differ, which in +// turn is the same as the ordering of the encodings of those two +// characters. Moreover, for every finite string x, F(x) < F(). + +namespace firebase { +namespace firestore { +namespace util { + +static const char kEscape1 = '\000'; +static const char kNullCharacter = '\xff'; // Combined with kEscape1 +static const char kSeparator = '\001'; // Combined with kEscape1 + +static const char kEscape2 = '\xff'; +static const char kInfinity = '\xff'; // Combined with kEscape2 +static const char kFFCharacter = '\000'; // Combined with kEscape2 + +static const char kEscape1_Separator[2] = {kEscape1, kSeparator}; + +/** Append to "*dest" the "len" bytes starting from "*src". */ +inline static void AppendBytes(std::string* dest, const char* src, size_t len) { + dest->append(src, len); +} + +inline static bool IsSpecialByte(char c) { + return ((unsigned char)(c + 1)) < 2; +} + +/** + * Returns 0 if one or more of the bytes in the specified uint32 value + * are the special values 0 or 255, and returns 4 otherwise. The + * result of this routine can be added to "p" to either advance past + * the next 4 bytes if they do not contain a special byte, or to + * remain on this set of four bytes if they contain the next special + * byte occurrence. + * + * REQUIRES: v_32 is the value of loading the next 4 bytes from "*p" (we + * pass in v_32 rather than loading it because in some cases, the client + * may already have the value in a register: "p" is just used for + * assertion checking). + */ +inline static int AdvanceIfNoSpecialBytes(uint32_t v_32, const char* p) { + FIREBASE_ASSERT(UNALIGNED_LOAD32(p) == v_32); + // See comments in SkipToNextSpecialByte if you wish to + // understand this expression (which checks for the occurrence + // of the special byte values 0 or 255 in any of the bytes of v_32). + if ((v_32 - 0x01010101u) & ~(v_32 + 0x01010101u) & 0x80808080u) { + // Special byte is in p[0..3] + FIREBASE_ASSERT(IsSpecialByte(p[0]) || IsSpecialByte(p[1]) || + IsSpecialByte(p[2]) || IsSpecialByte(p[3])); + return 0; + } else { + FIREBASE_ASSERT(!IsSpecialByte(p[0])); + FIREBASE_ASSERT(!IsSpecialByte(p[1])); + FIREBASE_ASSERT(!IsSpecialByte(p[2])); + FIREBASE_ASSERT(!IsSpecialByte(p[3])); + return 4; + } +} + +/** + * Return a pointer to the first byte in the range "[start..limit)" + * whose value is 0 or 255 (kEscape1 or kEscape2). If no such byte + * exists in the range, returns "limit". + */ +inline static const char* SkipToNextSpecialByte(const char* start, + const char* limit) { + // If these constants were ever changed, this routine needs to change + FIREBASE_ASSERT(kEscape1 == 0); + FIREBASE_ASSERT((kEscape2 & 0xff) == 255); + const char* p = start; + while (p + 8 <= limit) { + // Find out if any of the next 8 bytes are either 0 or 255 (our + // two characters that require special handling). We do this using + // the technique described in: + // + // http://graphics.stanford.edu/~seander/bithacks.html#HasLessInWord + // + // We use the test (x + 1) < 2 to check x = 0 or -1(255) + // + // If x is a byte value (0x00..0xff): + // (x - 0x01) & 0x80 is true only when x = 0x81..0xff, 0x00 + // ~(x + 0x01) & 0x80 is true only when x = 0x00..0x7e, 0xff + // The intersection of the above two sets is x = 0x00 or 0xff. + // We can ignore carry between bytes because only x = 0x00 or 0xff + // can cause carry in the expression -- and such x already makes the + // result value non-zero. + uint64_t v = UNALIGNED_LOAD64(p); + bool hasZeroOr255Byte = (v - 0x0101010101010101ull) & + ~(v + 0x0101010101010101ull) & + 0x8080808080808080ull; + if (!hasZeroOr255Byte) { + // No special values in the next 8 bytes + p += 8; + } else { +// We know the next 8 bytes have a special byte: find it +#ifdef IS_LITTLE_ENDIAN + uint32_t v_32 = static_cast(v); // Low 32 bits of v +#else + uint32_t v_32 = UNALIGNED_LOAD32(p); +#endif + // Test 32 bits at once to see if special byte is in next 4 bytes + // or the following 4 bytes + p += AdvanceIfNoSpecialBytes(v_32, p); + if (IsSpecialByte(p[0])) return p; + if (IsSpecialByte(p[1])) return p + 1; + if (IsSpecialByte(p[2])) return p + 2; + FIREBASE_ASSERT( + IsSpecialByte(p[3])); // Last byte must be the special one + return p + 3; + } + } + if (p + 4 <= limit) { + uint32_t v_32 = UNALIGNED_LOAD32(p); + p += AdvanceIfNoSpecialBytes(v_32, p); + } + while (p < limit && !IsSpecialByte(*p)) { + p++; + } + return p; +} + +// Expose SkipToNextSpecialByte for testing purposes +const char* OrderedCode::TEST_SkipToNextSpecialByte(const char* start, + const char* limit) { + return SkipToNextSpecialByte(start, limit); +} + +/** + * Helper routine to encode "s" and append to "*dest", escaping special + * characters. + */ +inline static void EncodeStringFragment(std::string* dest, + absl::string_view s) { + const char* p = s.data(); + const char* limit = p + s.size(); + const char* copy_start = p; + while (true) { + p = SkipToNextSpecialByte(p, limit); + if (p >= limit) break; // No more special characters that need escaping + char c = *(p++); + FIREBASE_ASSERT(IsSpecialByte(c)); + if (c == kEscape1) { + AppendBytes(dest, copy_start, static_cast(p - copy_start) - 1); + dest->push_back(kEscape1); + dest->push_back(kNullCharacter); + copy_start = p; + } else { + FIREBASE_ASSERT(c == kEscape2); + AppendBytes(dest, copy_start, static_cast(p - copy_start) - 1); + dest->push_back(kEscape2); + dest->push_back(kFFCharacter); + copy_start = p; + } + } + if (p > copy_start) { + AppendBytes(dest, copy_start, static_cast(p - copy_start)); + } +} + +void OrderedCode::WriteString(std::string* dest, absl::string_view s) { + EncodeStringFragment(dest, s); + AppendBytes(dest, kEscape1_Separator, 2); +} + +/** + * Return number of bytes needed to encode the non-length portion + * of val in ordered coding. Returns number in range [0,8]. + */ +static inline unsigned int OrderedNumLength(uint64_t val) { + const int lg = Bits::Log2Floor64(val); // -1 if val==0 + return static_cast(lg + 1 + 7) / 8; +} + +/** + * Append n bytes from src to *dst. + * REQUIRES: n <= 9 + * REQUIRES: src[0..8] are readable bytes (even if n is smaller) + * + * If we use string::append() instead of this routine, it increases the + * runtime of WriteNumIncreasing from ~9ns to ~13ns. + */ +static inline void AppendUpto9(std::string* dst, + const char* src, + unsigned int n) { + dst->append(src, 9); // Fixed-length append + const size_t extra = 9 - n; // How many extra bytes we added + dst->erase(dst->size() - extra, extra); +} + +void OrderedCode::WriteNumIncreasing(std::string* dest, uint64_t val) { + // Values are encoded with a single byte length prefix, followed + // by the actual value in big-endian format with leading 0 bytes + // dropped. + + // 8 bytes for value plus one byte for length. In addition, we have + // 8 extra bytes at the end so that we can have a fixed-length append + // call on *dest. + char buf[17]; + + UNALIGNED_STORE64(buf + 1, + absl::ghtonll(val)); // buf[0] may be needed for length + const unsigned int length = OrderedNumLength(val); + char* start = buf + 9 - length - 1; + *start = static_cast(length); + AppendUpto9(dest, start, length + 1); +} + +inline static void WriteInfinityInternal(std::string* dest) { + // Make an array so that we can just do one string operation for performance + static const char buf[2] = {kEscape2, kInfinity}; + dest->append(buf, 2); +} + +void OrderedCode::WriteInfinity(std::string* dest) { + WriteInfinityInternal(dest); +} + +void OrderedCode::WriteTrailingString(std::string* dest, + absl::string_view str) { + dest->append(str.data(), str.size()); +} + +/** + * Parse the encoding of a string previously encoded with or without + * inversion. If parse succeeds, return true, consume encoding from + * "*src", and if result != NULL append the decoded string to "*result". + * Otherwise, return false and leave both undefined. + */ +inline static bool ReadStringInternal(absl::string_view* src, + std::string* result) { + const char* start = src->data(); + const char* string_limit = src->data() + src->size(); + + // We only scan up to "limit-2" since a valid string must end with + // a two character terminator: 'kEscape1 kSeparator' + const char* limit = string_limit - 1; + const char* copy_start = start; + while (true) { + start = SkipToNextSpecialByte(start, limit); + if (start >= limit) break; // No terminator sequence found + const char c = *(start++); + // If inversion is required, instead of inverting 'c', we invert the + // character constants to which 'c' is compared. We get the same + // behavior but save the runtime cost of inverting 'c'. + FIREBASE_ASSERT(IsSpecialByte(c)); + if (c == kEscape1) { + if (result) { + AppendBytes(result, copy_start, + static_cast(start - copy_start) - 1); + } + // kEscape1 kSeparator ends component + // kEscape1 kNullCharacter represents '\0' + const char next = *(start++); + if (next == kSeparator) { + src->remove_prefix(static_cast(start - src->data())); + return true; + } else if (next == kNullCharacter) { + if (result) { + *result += '\0'; + } + } else { + return false; + } + copy_start = start; + } else { + FIREBASE_ASSERT(c == kEscape2); + if (result) { + AppendBytes(result, copy_start, + static_cast(start - copy_start) - 1); + } + // kEscape2 kFFCharacter represents '\xff' + // kEscape2 kInfinity is an error + const char next = *(start++); + if (next == kFFCharacter) { + if (result) { + *result += '\xff'; + } + } else { + return false; + } + copy_start = start; + } + } + return false; +} + +bool OrderedCode::ReadString(absl::string_view* src, std::string* result) { + return ReadStringInternal(src, result); +} + +bool OrderedCode::ReadNumIncreasing(absl::string_view* src, uint64_t* result) { + if (src->empty()) { + return false; // Not enough bytes + } + + // Decode length byte + const size_t len = static_cast((*src)[0]); + + // If len > 0 and src is longer than 1, the first byte of "payload" + // must be non-zero (otherwise the encoding is not minimal). + // In opt mode, we don't enforce that encodings must be minimal. + FIREBASE_ASSERT(0 == len || src->size() == 1 || (*src)[1] != '\0'); + + if (len + 1 > src->size() || len > 8) { + return false; // Not enough bytes or too many bytes + } + + if (result) { + uint64_t tmp = 0; + for (size_t i = 0; i < len; i++) { + tmp <<= 8; + tmp |= static_cast((*src)[1 + i]); + } + *result = tmp; + } + src->remove_prefix(len + 1); + return true; +} + +inline static bool ReadInfinityInternal(absl::string_view* src) { + if (src->size() >= 2 && ((*src)[0] == kEscape2) && ((*src)[1] == kInfinity)) { + src->remove_prefix(2); + return true; + } else { + return false; + } +} + +bool OrderedCode::ReadInfinity(absl::string_view* src) { + return ReadInfinityInternal(src); +} + +inline static bool ReadStringOrInfinityInternal(absl::string_view* src, + std::string* result, + bool* inf) { + if (ReadInfinityInternal(src)) { + if (inf) *inf = true; + return true; + } + + // We don't use ReadStringInternal here because that would inline + // the whole encoded string parsing code here. Depending on INVERT, only + // one of the following two calls will be generated at compile time. + bool success = OrderedCode::ReadString(src, result); + if (success) { + if (inf) *inf = false; + return true; + } else { + return false; + } +} + +bool OrderedCode::ReadStringOrInfinity(absl::string_view* src, + std::string* result, + bool* inf) { + return ReadStringOrInfinityInternal(src, result, inf); +} + +bool OrderedCode::ReadTrailingString(absl::string_view* src, + std::string* result) { + if (result) result->assign(src->data(), src->size()); + src->remove_prefix(src->size()); + return true; +} + +void OrderedCode::TEST_Corrupt(std::string* str, int k) { + int seen_seps = 0; + for (size_t i = 0; i < str->size() - 1; i++) { + if ((*str)[i] == kEscape1 && (*str)[i + 1] == kSeparator) { + seen_seps++; + if (seen_seps == k) { + (*str)[i + 1] = kSeparator + 1; + return; + } + } + } +} + +// Signed number encoding/decoding ///////////////////////////////////// +// +// The format is as follows: +// +// The first bit (the most significant bit of the first byte) +// represents the sign, 0 if the number is negative and +// 1 if the number is >= 0. +// +// Any unbroken sequence of successive bits with the same value as the sign +// bit, up to 9 (the 8th and 9th are the most significant bits of the next +// byte), are size bits that count the number of bytes after the first byte. +// That is, the total length is between 1 and 10 bytes. +// +// The value occupies the bits after the sign bit and the "size bits" +// till the end of the string, in network byte order. If the number +// is negative, the bits are in 2-complement. +// +// +// Example 1: number 0x424242 -> 4 byte big-endian hex string 0xf0424242: +// +// +---------------+---------------+---------------+---------------+ +// 1 1 1 1 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 0 +// +---------------+---------------+---------------+---------------+ +// ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ +// | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +// | | | | payload: the remaining bits after the sign and size bits +// | | | | and the delimiter bit, the value is 0x424242 +// | | | | +// | size bits: 3 successive bits with the same value as the sign bit +// | (followed by a delimiter bit with the opposite value) +// | mean that there are 3 bytes after the first byte, 4 total +// | +// sign bit: 1 means that the number is non-negative +// +// Example 2: negative number -0x800 -> 2 byte big-endian hex string 0x3800: +// +// +---------------+---------------+ +// 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 +// +---------------+---------------+ +// ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ +// | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +// | | payload: the remaining bits after the sign and size bits and the +// | | delimiter bit, 2-complement because of the negative sign, +// | | value is ~0x7ff, represents the value -0x800 +// | | +// | size bits: 1 bit with the same value as the sign bit +// | (followed by a delimiter bit with the opposite value) +// | means that there is 1 byte after the first byte, 2 total +// | +// sign bit: 0 means that the number is negative +// +// +// Compared with the simpler unsigned format used for uint64_t numbers, +// this format is more compact for small numbers, namely one byte encodes +// numbers in the range [-64,64), two bytes cover the range [-2^13,2^13), etc. +// In general, n bytes encode numbers in the range [-2^(n*7-1),2^(n*7-1)). +// (The cross-over point for compactness of representation is 8 bytes, +// where this format only covers the range [-2^55,2^55), +// whereas an encoding with sign bit and length in the first byte and +// payload in all following bytes would cover [-2^56,2^56).) + +static const int kMaxSigned64Length = 10; + +// This array maps encoding length to header bits in the first two bytes. +static const char kLengthToHeaderBits[1 + kMaxSigned64Length][2] = { + {0, 0}, {'\x80', 0}, {'\xc0', 0}, {'\xe0', 0}, + {'\xf0', 0}, {'\xf8', 0}, {'\xfc', 0}, {'\xfe', 0}, + {'\xff', 0}, {'\xff', '\x80'}, {'\xff', '\xc0'}}; + +// This array maps encoding lengths to the header bits that overlap with +// the payload and need fixing when reading. +static const uint64_t kLengthToMask[1 + kMaxSigned64Length] = { + 0ULL, + 0x80ULL, + 0xc000ULL, + 0xe00000ULL, + 0xf0000000ULL, + 0xf800000000ULL, + 0xfc0000000000ULL, + 0xfe000000000000ULL, + 0xff00000000000000ULL, + 0x8000000000000000ULL, + 0ULL}; + +// This array maps the number of bits in a number to the encoding +// length produced by WriteSignedNumIncreasing. +// For positive numbers, the number of bits is 1 plus the most significant +// bit position (the highest bit position in a positive int64_t is 63). +// For a negative number n, we count the bits in ~n. +// That is, length = kBitsToLength[Bits::Log2Floor64(n < 0 ? ~n : n) + 1]. +static const int8_t kBitsToLength[1 + 63] = { + 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 4, + 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 7, 7, + 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 10}; + +/** Calculates the encoding length in bytes of the signed number n. */ +static inline int SignedEncodingLength(int64_t n) { + return kBitsToLength[Bits::Log2Floor64( + static_cast(n < 0 ? ~n : n)) + + 1]; +} + +/** Slightly faster version for n > 0. */ +static inline int SignedEncodingLengthPositive(int64_t n) { + return kBitsToLength[Bits::Log2FloorNonZero64(static_cast(n)) + 1]; +} + +void OrderedCode::WriteSignedNumIncreasing(std::string* dest, int64_t val) { + const int64_t x = val < 0 ? ~val : val; + if (x < 64) { // fast path for encoding length == 1 + *dest += static_cast(kLengthToHeaderBits[1][0] ^ val); + return; + } + // buf = val in network byte order, sign extended to 10 bytes + const char sign_byte = val < 0 ? '\xff' : '\0'; + char buf[10] = { + sign_byte, + sign_byte, + }; + UNALIGNED_STORE64(buf + 2, absl::ghtonll(static_cast(val))); + + FIREBASE_ASSERT_MESSAGE_WITH_EXPRESSION(sizeof(buf) == kMaxSigned64Length, + sizeof(buf) == kMaxSigned64Length, + "max length size mismatch"); + const size_t len = static_cast(SignedEncodingLengthPositive(x)); + FIREBASE_ASSERT(len >= 2); + char* const begin = buf + sizeof(buf) - len; + begin[0] ^= kLengthToHeaderBits[len][0]; + begin[1] ^= kLengthToHeaderBits[len][1]; // ok because len >= 2 + dest->append(begin, len); +} + +bool OrderedCode::ReadSignedNumIncreasing(absl::string_view* src, + int64_t* result) { + if (src->empty()) return false; + const uint64_t xor_mask = (!((*src)[0] & 0x80)) ? ~0ULL : 0ULL; + const unsigned char first_byte = static_cast( + static_cast((*src)[0]) ^ (xor_mask & 0xff)); + + // now calculate and test length, and set x to raw (unmasked) result + size_t len; + uint64_t x; + if (first_byte != 0xff) { + len = static_cast(7 - Bits::Log2FloorNonZero(first_byte ^ 0xff)); + if (src->size() < len) return false; + x = xor_mask; // sign extend using xor_mask + for (size_t i = 0; i < len; ++i) + x = (x << 8) | static_cast((*src)[i]); + } else { + len = 8; + if (src->size() < len) return false; + const unsigned char second_byte = static_cast( + static_cast((*src)[1]) ^ (xor_mask & 0xff)); + if (second_byte >= 0x80) { + if (second_byte < 0xc0) { + len = 9; + } else { + const unsigned char third_byte = static_cast( + static_cast((*src)[2]) ^ (xor_mask & 0xff)); + if (second_byte == 0xc0 && third_byte < 0x80) { + len = 10; + } else { + return false; // either len > 10 or len == 10 and #bits > 63 + } + } + if (src->size() < len) return false; + } + x = absl::gntohll(UNALIGNED_LOAD64(src->data() + len - 8)); + } + + x ^= kLengthToMask[len]; // remove spurious header bits + + FIREBASE_ASSERT(len == static_cast( + SignedEncodingLength(static_cast(x)))); + + if (result) *result = static_cast(x); + src->remove_prefix(static_cast(len)); + return true; +} + +} // namespace util +} // namespace firestore +} // namespace firebase diff --git a/Firestore/core/src/firebase/firestore/util/ordered_code.h b/Firestore/core/src/firebase/firestore/util/ordered_code.h new file mode 100644 index 0000000..57b84bd --- /dev/null +++ b/Firestore/core/src/firebase/firestore/util/ordered_code.h @@ -0,0 +1,129 @@ +/* + * Copyright 2017 Google + * + * 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 module provides routines for encoding a sequence of typed +// entities into a string. The resulting strings can be +// lexicographically compared to yield the same comparison value that +// would have been generated if the encoded items had been compared +// one by one according to their type. +// +// More precisely, suppose: +// 1. string A is generated by encoding the sequence of items [A_1..A_n] +// 2. string B is generated by encoding the sequence of items [B_1..B_n] +// 3. The types match; i.e., for all i: A_i was encoded using +// the same routine as B_i +// Then: +// Comparing A vs. B lexicographically is the same as comparing +// the vectors [A_1..A_n] and [B_1..B_n] lexicographically. +// +// Furthermore, if n < m, the encoding of [A_1..A_n] is a strict prefix of +// [A_1..A_m] (unless m = n+1 and A_m is the empty string encoded with +// WriteTrailingString, in which case the encodings are equal). +// +// This module is often useful when generating multi-part sstable +// keys that have to be ordered in a particular fashion. + +#ifndef FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_UTIL_ORDERED_CODE_H_ +#define FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_UTIL_ORDERED_CODE_H_ + +#include + +#include "absl/strings/string_view.h" + +namespace firebase { +namespace firestore { +namespace util { + +class OrderedCode { + public: + // ------------------------------------------------------------------- + // Encoding routines: each one of the following routines append + // one item to "*dest". The Write(Signed)NumIncreasing() and + // Write(Signed)NumDecreasing() routines differ in whether the resulting + // encoding is ordered by increasing number or decreasing number. + // Similarly, WriteString() and WriteStringDecreasing() differ in whether + // the resulting encoding is ordered by the original string in + // lexicographically increasing or decreasing order. WriteString() + // is not called WriteStringIncreasing() for convenience and backward + // compatibility. + + static void WriteString(std::string* dest, absl::string_view str); + static void WriteNumIncreasing(std::string* dest, uint64_t num); + static void WriteSignedNumIncreasing(std::string* dest, int64_t num); + + /** + * Creates an encoding for the "infinite string", a value considered to + * be lexicographically after any real string. Note that in the case of + * WriteInfinityDecreasing(), this would come before any real string as + * the ordering puts lexicographically greater values first. + */ + static void WriteInfinity(std::string* dest); + + /** + * Special string append that can only be used at the tail end of + * an encoded string -- blindly appends "str" to "*dest". + */ + static void WriteTrailingString(std::string* dest, absl::string_view str); + + // ------------------------------------------------------------------- + // Decoding routines: these extract an item earlier encoded using + // the corresponding WriteXXX() routines above. The item is read + // from "*src"; "*src" is modified to point past the decoded item; + // and if "result" is non-NULL, "*result" is modified to contain the + // result. In case of string result, the decoded string is appended to + // "*result". Returns true if the next item was read successfully, false + // otherwise. + + static bool ReadString(absl::string_view* src, std::string* result); + static bool ReadNumIncreasing(absl::string_view* src, uint64_t* result); + static bool ReadSignedNumIncreasing(absl::string_view* src, int64_t* result); + + static bool ReadInfinity(absl::string_view* src); + static bool ReadTrailingString(absl::string_view* src, std::string* result); + + /** REQUIRES: next item was encoded by WriteInfinity() or WriteString(). */ + static bool ReadStringOrInfinity(absl::string_view* src, + std::string* result, + bool* inf); + + /** + * Helper for testing: corrupt "*str" by changing the kth item separator + * in the string. + */ + static void TEST_Corrupt(std::string* str, int k); + + /** + * Helper for testing. + * SkipToNextSpecialByte is an internal routine defined in the .cc file + * with the following semantics. Return a pointer to the first byte + * in the range "[start..limit)" whose value is 0 or 255. If no such + * byte exists in the range, returns "limit". + */ + static const char* TEST_SkipToNextSpecialByte(const char* start, + const char* limit); + + // Not an instantiable class, but the class exists to make it easy to + // use with a single using statement. + OrderedCode() = delete; + OrderedCode(const OrderedCode&) = delete; + OrderedCode& operator=(const OrderedCode&) = delete; +}; + +} // namespace util +} // namespace firestore +} // namespace firebase + +#endif // FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_UTIL_ORDERED_CODE_H_ diff --git a/Firestore/core/src/firebase/firestore/util/secure_random.h b/Firestore/core/src/firebase/firestore/util/secure_random.h index 72be1bd..95b41e1 100644 --- a/Firestore/core/src/firebase/firestore/util/secure_random.h +++ b/Firestore/core/src/firebase/firestore/util/secure_random.h @@ -50,6 +50,22 @@ class SecureRandom { } result_type operator()(); + + /** Returns a uniformly distributed pseudorandom integer in [0, n). */ + inline result_type Uniform(result_type n) { + // Divides the range into buckets of size n plus leftovers. + const result_type rem = (max() - min()) % n + min() + 1; + result_type rnd; + // Generates random number until the number falls into a bucket. + do { + rnd = (*this)(); + } while (rnd < rem); + return rnd % n; + } + + inline bool OneIn(result_type n) { + return Uniform(n) == 0; + } }; } // namespace util diff --git a/Firestore/core/test/firebase/firestore/util/CMakeLists.txt b/Firestore/core/test/firebase/firestore/util/CMakeLists.txt index 13a2e46..eb5a898 100644 --- a/Firestore/core/test/firebase/firestore/util/CMakeLists.txt +++ b/Firestore/core/test/firebase/firestore/util/CMakeLists.txt @@ -36,7 +36,9 @@ cc_test( firebase_firestore_util_test SOURCES autoid_test.cc + bits_test.cc comparison_test.cc + ordered_code_test.cc string_printf_test.cc string_util_test.cc DEPENDS diff --git a/Firestore/core/test/firebase/firestore/util/bits_test.cc b/Firestore/core/test/firebase/firestore/util/bits_test.cc new file mode 100644 index 0000000..cb0976b --- /dev/null +++ b/Firestore/core/test/firebase/firestore/util/bits_test.cc @@ -0,0 +1,142 @@ +/* + * Copyright 2017 Google + * + * 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 "Firestore/core/src/firebase/firestore/util/bits.h" + +#include +#include +#include + +#include "Firestore/core/src/firebase/firestore/util/secure_random.h" +#include "gtest/gtest.h" + +namespace firebase { +namespace firestore { +namespace util { + +const int kNumIterations = 10000; // "Number of test iterations to run. + +class BitsTest : public testing::Test { + protected: + SecureRandom random_; +}; + +TEST_F(BitsTest, Log2EdgeCases) { + std::cout << "TestLog2EdgeCases" << std::endl; + + EXPECT_EQ(-1, Bits::Log2Floor(0)); + EXPECT_EQ(-1, Bits::Log2Floor64(0)); + + for (int i = 0; i < 32; i++) { + uint32_t n = 1U << i; + EXPECT_EQ(i, Bits::Log2Floor(n)); + EXPECT_EQ(i, Bits::Log2FloorNonZero(n)); + if (n > 2) { + EXPECT_EQ(i - 1, Bits::Log2Floor(n - 1)); + EXPECT_EQ(i, Bits::Log2Floor(n + 1)); + EXPECT_EQ(i - 1, Bits::Log2FloorNonZero(n - 1)); + EXPECT_EQ(i, Bits::Log2FloorNonZero(n + 1)); + } + } + + for (int i = 0; i < 64; i++) { + uint64_t n = 1ULL << i; + EXPECT_EQ(i, Bits::Log2Floor64(n)); + EXPECT_EQ(i, Bits::Log2FloorNonZero64(n)); + if (n > 2) { + EXPECT_EQ(i - 1, Bits::Log2Floor64(n - 1)); + EXPECT_EQ(i, Bits::Log2Floor64(n + 1)); + EXPECT_EQ(i - 1, Bits::Log2FloorNonZero64(n - 1)); + EXPECT_EQ(i, Bits::Log2FloorNonZero64(n + 1)); + } + } +} + +TEST_F(BitsTest, Log2Random) { + std::cout << "TestLog2Random" << std::endl; + + for (int i = 0; i < kNumIterations; i++) { + int maxbit = -1; + uint32_t n = 0; + while (!random_.OneIn(32u)) { + int bit = static_cast(random_.Uniform(32u)); + n |= (1U << bit); + maxbit = std::max(bit, maxbit); + } + EXPECT_EQ(maxbit, Bits::Log2Floor(n)); + if (n != 0) { + EXPECT_EQ(maxbit, Bits::Log2FloorNonZero(n)); + } + } +} + +TEST_F(BitsTest, Log2Random64) { + std::cout << "TestLog2Random64" << std::endl; + + for (int i = 0; i < kNumIterations; i++) { + int maxbit = -1; + uint64_t n = 0; + while (!random_.OneIn(64u)) { + int bit = static_cast(random_.Uniform(64u)); + n |= (1ULL << bit); + maxbit = std::max(bit, maxbit); + } + EXPECT_EQ(maxbit, Bits::Log2Floor64(n)); + if (n != 0) { + EXPECT_EQ(maxbit, Bits::Log2FloorNonZero64(n)); + } + } +} + +TEST(Bits, Port32) { + for (int shift = 0; shift < 32; shift++) { + for (uint32_t delta = 0; delta <= 2; delta++) { + const uint32_t v = (static_cast(1) << shift) - 1 + delta; + EXPECT_EQ(Bits::Log2Floor_Portable(v), Bits::Log2Floor(v)) << v; + if (v != 0) { + EXPECT_EQ(Bits::Log2FloorNonZero_Portable(v), Bits::Log2FloorNonZero(v)) + << v; + } + } + } + static const uint32_t M32 = std::numeric_limits::max(); + EXPECT_EQ(Bits::Log2Floor_Portable(M32), Bits::Log2Floor(M32)) << M32; + EXPECT_EQ(Bits::Log2FloorNonZero_Portable(M32), Bits::Log2FloorNonZero(M32)) + << M32; +} + +TEST(Bits, Port64) { + for (int shift = 0; shift < 64; shift++) { + for (uint64_t delta = 0; delta <= 2; delta++) { + const uint64_t v = (static_cast(1) << shift) - 1 + delta; + EXPECT_EQ(Bits::Log2Floor64_Portable(v), Bits::Log2Floor64(v)) << v; + if (v != 0) { + EXPECT_EQ(Bits::Log2FloorNonZero64_Portable(v), + Bits::Log2FloorNonZero64(v)) + << v; + } + } + } + static const uint64_t M64 = std::numeric_limits::max(); + EXPECT_EQ(Bits::Log2Floor64_Portable(M64), Bits::Log2Floor64(M64)) << M64; + EXPECT_EQ(Bits::Log2FloorNonZero64_Portable(M64), + Bits::Log2FloorNonZero64(M64)) + << M64; +} + +} // namespace util +} // namespace firestore +} // namespace firebase diff --git a/Firestore/core/test/firebase/firestore/util/ordered_code_test.cc b/Firestore/core/test/firebase/firestore/util/ordered_code_test.cc new file mode 100644 index 0000000..fd2ce83 --- /dev/null +++ b/Firestore/core/test/firebase/firestore/util/ordered_code_test.cc @@ -0,0 +1,508 @@ +/* + * Copyright 2017 Google + * + * 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 "Firestore/core/src/firebase/firestore/util/ordered_code.h" + +#include +#include + +#include "Firestore/core/src/firebase/firestore/util/secure_random.h" +#include "gtest/gtest.h" + +namespace firebase { +namespace firestore { +namespace util { + +static std::string RandomString(SecureRandom* rnd, int len) { + std::string x; + for (int i = 0; i < len; i++) { + x += static_cast(rnd->Uniform(256)); + } + return x; +} + +// --------------------------------------------------------------------- +// Utility template functions (they help templatize the tests below) + +// Read/WriteIncreasing are defined for string, uint64_t, int64_t below. +template +static void OCWriteIncreasing(std::string* dest, const T& val); +template +static bool OCReadIncreasing(absl::string_view* src, T* result); + +// Read/WriteIncreasing +template <> +void OCWriteIncreasing(std::string* dest, const std::string& val) { + OrderedCode::WriteString(dest, val); +} +template <> +bool OCReadIncreasing(absl::string_view* src, + std::string* result) { + return OrderedCode::ReadString(src, result); +} + +// Read/WriteIncreasing +template <> +void OCWriteIncreasing(std::string* dest, const uint64_t& val) { + OrderedCode::WriteNumIncreasing(dest, val); +} +template <> +bool OCReadIncreasing(absl::string_view* src, uint64_t* result) { + return OrderedCode::ReadNumIncreasing(src, result); +} + +enum Direction { INCREASING = 0 }; + +// Read/WriteIncreasing +template <> +void OCWriteIncreasing(std::string* dest, const int64_t& val) { + OrderedCode::WriteSignedNumIncreasing(dest, val); +} +template <> +bool OCReadIncreasing(absl::string_view* src, int64_t* result) { + return OrderedCode::ReadSignedNumIncreasing(src, result); +} + +template +std::string OCWrite(T val, Direction direction) { + EXPECT_EQ(INCREASING, direction); // DECREASING never implemented. + std::string result; + OCWriteIncreasing(&result, val); + return result; +} + +template +void OCWriteToString(std::string* result, T val, Direction direction) { + EXPECT_EQ(INCREASING, direction); // DECREASING never implemented. + OCWriteIncreasing(result, val); +} + +template +bool OCRead(absl::string_view* s, T* val, Direction direction) { + EXPECT_EQ(INCREASING, direction); // DECREASING never implemented. + return OCReadIncreasing(s, val); +} + +// --------------------------------------------------------------------- +// Numbers + +template +static T TestRead(Direction d, const std::string& a) { + // gracefully reject any proper prefix of an encoding + for (size_t i = 0; i < a.size() - 1; ++i) { + absl::string_view s(a.data(), i); + EXPECT_TRUE(!OCRead(&s, NULL, d)); + EXPECT_EQ(s, a.substr(0, i)); + } + + absl::string_view s(a); + T v; + EXPECT_TRUE(OCRead(&s, &v, d)); + EXPECT_TRUE(s.empty()); + return v; +} + +template +static void TestWriteRead(Direction d, T expected) { + EXPECT_EQ(expected, TestRead(d, OCWrite(expected, d))); +} + +// Verifies that the second Write* call appends a non-empty std::string to its +// output. +template +static void TestWriteAppends(Direction d, T first, U second) { + std::string encoded; + OCWriteToString(&encoded, first, d); + std::string encoded_first_only = encoded; + OCWriteToString(&encoded, second, d); + EXPECT_NE(encoded, encoded_first_only); + EXPECT_EQ(absl::string_view(encoded).substr(0, encoded_first_only.length()), + encoded_first_only); +} + +template +static void TestNumbers(T multiplier) { + for (int j = 0; j < 1; ++j) { + const Direction d = static_cast(j); + + // first test powers of 2 (and nearby numbers) + for (T x = std::numeric_limits().max(); x != 0; x /= 2) { + TestWriteRead(d, multiplier * (x - 1)); + TestWriteRead(d, multiplier * x); + if (x != std::numeric_limits::max()) { + TestWriteRead(d, multiplier * (x + 1)); + } else if (multiplier < 0 && static_cast(multiplier) == -1) { + TestWriteRead(d, -x - 1); + } + } + + SecureRandom rnd; // Generate 32bit pseudo-random integer. + for (int bits = 1; bits <= std::numeric_limits().digits; ++bits) { + // test random non-negative numbers with given number of significant bits + const uint64_t mask = (~0ULL) >> (64 - bits); + for (int i = 0; i < 1000; i++) { + T x = static_cast((static_cast(rnd()) << 32 | + static_cast(rnd())) & + mask); + TestWriteRead(d, multiplier * x); + T y = static_cast((static_cast(rnd()) << 32 | + static_cast(rnd())) & + mask); + TestWriteAppends(d, multiplier * x, multiplier * y); + } + } + } +} + +// Return true iff 'a' is "before" 'b' according to 'direction' +static bool CompareStrings(const std::string& a, + const std::string& b, + Direction d) { + return (INCREASING == d) ? (a < b) : (b < a); +} + +template +static void TestNumberOrdering() { + const Direction d = INCREASING; + + // first the negative numbers (if T is signed, otherwise no-op) + std::string laststr = OCWrite(std::numeric_limits().min(), d); + for (T num = std::numeric_limits().min() / 2; num != 0; num /= 2) { + std::string strminus1 = OCWrite(num - 1, d); + std::string str = OCWrite(num, d); + std::string strplus1 = OCWrite(num + 1, d); + + EXPECT_TRUE(CompareStrings(strminus1, str, d)); + EXPECT_TRUE(CompareStrings(str, strplus1, d)); + + // Compare 'str' with 'laststr'. When we approach 0, 'laststr' is + // not necessarily before 'strminus1'. + EXPECT_TRUE(CompareStrings(laststr, str, d)); + laststr = str; + } + + // then the positive numbers + laststr = OCWrite(0, d); + T num = 1; + while (num < std::numeric_limits().max() / 2) { + num *= 2; + std::string strminus1 = OCWrite(num - 1, d); + std::string str = OCWrite(num, d); + std::string strplus1 = OCWrite(num + 1, d); + + EXPECT_TRUE(CompareStrings(strminus1, str, d)); + EXPECT_TRUE(CompareStrings(str, strplus1, d)); + + // Compare 'str' with 'laststr'. + EXPECT_TRUE(CompareStrings(laststr, str, d)); + laststr = str; + } +} + +// Helper routine for testing TEST_SkipToNextSpecialByte +static size_t FindSpecial(const std::string& x) { + const char* p = x.data(); + const char* limit = p + x.size(); + const char* result = OrderedCode::TEST_SkipToNextSpecialByte(p, limit); + return static_cast(result - p); +} + +TEST(OrderedCode, SkipToNextSpecialByte) { + for (size_t len = 0; len < 256; len++) { + SecureRandom rnd; + std::string x; + while (x.size() < len) { + char c = 1 + static_cast(rnd.Uniform(254)); + ASSERT_NE(c, 0); + ASSERT_NE(c, 255); + x += c; // No 0 bytes, no 255 bytes + } + EXPECT_EQ(FindSpecial(x), x.size()); + for (size_t special_pos = 0; special_pos < len; special_pos++) { + for (int special_test = 0; special_test < 2; special_test++) { + const char special_byte = (special_test == 0) ? 0 : '\xff'; + std::string y = x; + y[special_pos] = special_byte; + EXPECT_EQ(FindSpecial(y), special_pos); + if (special_pos < 16) { + // Add some special bytes after the one at special_pos to make sure + // we still return the earliest special byte in the string + for (size_t rest = special_pos + 1; rest < len; rest++) { + if (rnd.OneIn(3)) { + y[rest] = rnd.OneIn(2) ? 0 : '\xff'; + EXPECT_EQ(FindSpecial(y), special_pos); + } + } + } + } + } + } +} + +TEST(OrderedCode, ExhaustiveFindSpecial) { + char buf[16]; + char* limit = buf + sizeof(buf); + int count = 0; + for (int start_offset = 0; start_offset <= 5; start_offset += 5) { + // We test exhaustively with all combinations of 3 bytes starting + // at offset 0 and offset 5 (so as to test with the bytes at both + // ends of a 64-bit word). + for (char& c : buf) { + c = 'a'; // Not a special byte + } + for (int b0 = 0; b0 < 256; b0++) { + for (int b1 = 0; b1 < 256; b1++) { + for (int b2 = 0; b2 < 256; b2++) { + buf[start_offset + 0] = static_cast(b0); + buf[start_offset + 1] = static_cast(b1); + buf[start_offset + 2] = static_cast(b2); + char* expected; + if (b0 == 0 || b0 == 255) { + expected = &buf[start_offset]; + } else if (b1 == 0 || b1 == 255) { + expected = &buf[start_offset + 1]; + } else if (b2 == 0 || b2 == 255) { + expected = &buf[start_offset + 2]; + } else { + expected = limit; + } + count++; + EXPECT_EQ(expected, + OrderedCode::TEST_SkipToNextSpecialByte(buf, limit)); + } + } + } + } + EXPECT_EQ(count, 256 * 256 * 256 * 2); +} + +TEST(OrderedCodeUint64, EncodeDecode) { + TestNumbers(1); +} + +TEST(OrderedCodeUint64, Ordering) { + TestNumberOrdering(); +} + +TEST(OrderedCodeInt64, EncodeDecode) { + TestNumbers(1); + TestNumbers(-1); +} + +TEST(OrderedCodeInt64, Ordering) { + TestNumberOrdering(); +} + +// Returns the bitwise complement of s. +static inline std::string StrNot(const std::string& s) { + std::string result; + for (const char c : s) result.push_back(~c); + return result; +} + +template +static void TestInvalidEncoding(Direction d, const std::string& s) { + absl::string_view p(s); + EXPECT_FALSE(OCRead(&p, static_cast(NULL), d)); + EXPECT_EQ(s, p); +} + +TEST(OrderedCodeInvalidEncodingsTest, Overflow) { + // 1U << 64, increasing + const std::string k2xx64U = "\x09\x01" + std::string(8, 0); + TestInvalidEncoding(INCREASING, k2xx64U); + + // 1 << 63 and ~(1 << 63), increasing + const std::string k2xx63 = "\xff\xc0\x80" + std::string(7, 0); + TestInvalidEncoding(INCREASING, k2xx63); + TestInvalidEncoding(INCREASING, StrNot(k2xx63)); +} + +TEST(OrderedCodeInvalidEncodingsTest, NonCanonical) { + // Test DCHECK failures of "ambiguous"/"non-canonical" encodings. + // These are non-minimal (but otherwise "valid") encodings that + // differ from the minimal encoding chosen by OrderedCode::WriteXXX + // and thus should be avoided to not mess up the string ordering of + // encodings. + + SecureRandom rnd; + + for (int n = 2; n <= 9; ++n) { + // The zero in non_minimal[1] is "redundant". + std::string non_minimal = + std::string(1, n - 1) + std::string(1, 0) + RandomString(&rnd, n - 2); + EXPECT_EQ(static_cast(n), non_minimal.length()); + + EXPECT_NE(OCWrite(0, INCREASING), non_minimal); + +#if defined(NDEBUG) + TestRead(INCREASING, non_minimal); +#else // defined(NDEBUG) + absl::string_view s(non_minimal); + EXPECT_ANY_THROW(OrderedCode::ReadNumIncreasing(&s, NULL)); +#endif // defined(NDEBUG) + } + + for (int n = 2; n <= 10; ++n) { + // Header with 1 sign bit and n-1 size bits. + std::string header = + std::string(n / 8, 0xff) + std::string(1, 0xff << (8 - (n % 8))); + // There are more than 7 zero bits between header bits and "payload". + std::string non_minimal = + header + + std::string(1, + static_cast(rnd.Uniform(256)) & ~*header.rbegin()) + + RandomString(&rnd, n - static_cast(header.length()) - 1); + EXPECT_EQ(static_cast(n), non_minimal.length()); + + EXPECT_NE(OCWrite(0, INCREASING), non_minimal); + +#if defined(NDEBUG) + TestRead(INCREASING, non_minimal); +#else // defined(NDEBUG) + absl::string_view s(non_minimal); + EXPECT_ANY_THROW(OrderedCode::ReadSignedNumIncreasing(&s, NULL)); + s = non_minimal; +#endif // defined(NDEBUG) + } +} + +// --------------------------------------------------------------------- +// Strings + +TEST(OrderedCodeString, Infinity) { + const std::string value("\xff\xff foo"); + bool is_inf; + std::string encoding, parsed; + absl::string_view s; + + // Check encoding/decoding of "infinity" for ascending order + encoding.clear(); + OrderedCode::WriteInfinity(&encoding); + encoding.push_back('a'); + s = encoding; + EXPECT_TRUE(OrderedCode::ReadInfinity(&s)); + EXPECT_EQ(1u, s.size()); + s = encoding; + is_inf = false; + EXPECT_TRUE(OrderedCode::ReadStringOrInfinity(&s, NULL, &is_inf)); + EXPECT_EQ(1u, s.size()); + EXPECT_TRUE(is_inf); + + // Check ReadStringOrInfinity() can parse ordinary strings + encoding.clear(); + OrderedCode::WriteString(&encoding, value); + encoding.push_back('a'); + s = encoding; + is_inf = false; + parsed.clear(); + EXPECT_TRUE(OrderedCode::ReadStringOrInfinity(&s, &parsed, &is_inf)); + EXPECT_EQ(1u, s.size()); + EXPECT_FALSE(is_inf); + EXPECT_EQ(value, parsed); +} + +TEST(OrderedCodeString, EncodeDecode) { + SecureRandom rnd; + for (int i = 0; i < 1; ++i) { + const Direction d = static_cast(i); + + for (int len = 0; len < 256; len++) { + const std::string a = RandomString(&rnd, len); + TestWriteRead(d, a); + for (int len2 = 0; len2 < 64; len2++) { + const std::string b = RandomString(&rnd, len2); + + TestWriteAppends(d, a, b); + + std::string out; + OCWriteToString(&out, a, d); + OCWriteToString(&out, b, d); + + std::string a2, b2, dummy; + absl::string_view s = out; + absl::string_view s2 = out; + EXPECT_TRUE(OCRead(&s, &a2, d)); + EXPECT_TRUE(OCRead(&s2, NULL, d)); + EXPECT_EQ(s, s2); + + EXPECT_TRUE(OCRead(&s, &b2, d)); + EXPECT_TRUE(OCRead(&s2, NULL, d)); + EXPECT_EQ(s, s2); + + EXPECT_TRUE(!OCRead(&s, &dummy, d)); + EXPECT_TRUE(!OCRead(&s2, NULL, d)); + EXPECT_EQ(a, a2); + EXPECT_EQ(b, b2); + EXPECT_TRUE(s.empty()); + EXPECT_TRUE(s2.empty()); + } + } + } +} + +// 'str' is a static C-style string that may contain '\0' +#define STATIC_STR(str) absl::string_view((str), sizeof(str) - 1) + +static std::string EncodeStringIncreasing(absl::string_view value) { + std::string encoded; + OrderedCode::WriteString(&encoded, value); + return encoded; +} + +TEST(OrderedCodeString, Increasing) { + // Here are a series of strings in non-decreasing order, including + // consecutive strings such that the second one is equal to, a proper + // prefix of, or has the same length as the first one. Most also contain + // the special escaping characters '\x00' and '\xff'. + EXPECT_EQ(EncodeStringIncreasing(STATIC_STR("")), + EncodeStringIncreasing(STATIC_STR(""))); + + ASSERT_LT(EncodeStringIncreasing(STATIC_STR("")), + EncodeStringIncreasing(STATIC_STR("\x00"))); + + EXPECT_EQ(EncodeStringIncreasing(STATIC_STR("\x00")), + EncodeStringIncreasing(STATIC_STR("\x00"))); + + ASSERT_LT(EncodeStringIncreasing(STATIC_STR("\x00")), + EncodeStringIncreasing(STATIC_STR("\x01"))); + + ASSERT_LT(EncodeStringIncreasing(STATIC_STR("\x01")), + EncodeStringIncreasing(STATIC_STR("a"))); + + EXPECT_EQ(EncodeStringIncreasing(STATIC_STR("a")), + EncodeStringIncreasing(STATIC_STR("a"))); + + ASSERT_LT(EncodeStringIncreasing(STATIC_STR("a")), + EncodeStringIncreasing(STATIC_STR("aa"))); + + ASSERT_LT(EncodeStringIncreasing(STATIC_STR("aa")), + EncodeStringIncreasing(STATIC_STR("\xff"))); + + ASSERT_LT(EncodeStringIncreasing(STATIC_STR("\xff")), + EncodeStringIncreasing(STATIC_STR("\xff\x00"))); + + ASSERT_LT(EncodeStringIncreasing(STATIC_STR("\xff\x00")), + EncodeStringIncreasing(STATIC_STR("\xff\x01"))); + + std::string infinity; + OrderedCode::WriteInfinity(&infinity); + ASSERT_LT(EncodeStringIncreasing(std::string(1 << 20, '\xff')), infinity); +} + +} // namespace util +} // namespace firestore +} // namespace firebase diff --git a/Firestore/core/test/firebase/firestore/util/secure_random_test.cc b/Firestore/core/test/firebase/firestore/util/secure_random_test.cc index ee2ae00..0b7a51b 100644 --- a/Firestore/core/test/firebase/firestore/util/secure_random_test.cc +++ b/Firestore/core/test/firebase/firestore/util/secure_random_test.cc @@ -30,3 +30,28 @@ TEST(SecureRandomTest, ResultsAreBounded) { EXPECT_LE(value, rng.max()); } } + +TEST(SecureRandomTest, Uniform) { + SecureRandom rng; + int count[10] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; + + for (int i = 0; i < 1000; i++) { + count[rng.Uniform(10)]++; + } + for (int i = 0; i < 10; i++) { + // Practically, each count should be close to 100. + EXPECT_LT(50, count[i]) << count[i]; + } +} + +TEST(SecureRandomTest, OneIn) { + SecureRandom rng; + int count = 0; + + for (int i = 0; i < 1000; i++) { + if (rng.OneIn(10)) count++; + } + // Practically, count should be close to 100. + EXPECT_LT(50, count) << count; + EXPECT_GT(150, count) << count; +} -- cgit v1.2.3