1 /* Copyright 2015 The TensorFlow Authors. All Rights Reserved. 2 3 Licensed under the Apache License, Version 2.0 (the "License"); 4 you may not use this file except in compliance with the License. 5 You may obtain a copy of the License at 6 7 http://www.apache.org/licenses/LICENSE-2.0 8 9 Unless required by applicable law or agreed to in writing, software 10 distributed under the License is distributed on an "AS IS" BASIS, 11 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 See the License for the specific language governing permissions and 13 limitations under the License. 14 ==============================================================================*/ 15 16 #include "tensorflow/core/lib/strings/ordered_code.h" 17 18 #include <float.h> 19 #include <stddef.h> 20 #include <limits> 21 #include <vector> 22 23 #include "tensorflow/core/lib/core/stringpiece.h" 24 #include "tensorflow/core/lib/random/simple_philox.h" 25 #include "tensorflow/core/platform/logging.h" 26 #include "tensorflow/core/platform/test.h" 27 #include "tensorflow/core/platform/test_benchmark.h" 28 #include "tensorflow/core/platform/types.h" 29 30 namespace tensorflow { 31 namespace strings { 32 namespace { 33 34 string RandomString(random::SimplePhilox* rnd, size_t len) { 35 string x; 36 for (size_t i = 0; i < len; i++) { 37 x += rnd->Uniform(256); 38 } 39 return x; 40 } 41 42 // --------------------------------------------------------------------- 43 // Utility template functions (they help templatize the tests below) 44 45 // Read/WriteIncreasing are defined for string, uint64, int64 below. 46 template <typename T> 47 void OCWriteIncreasing(string* dest, const T& val); 48 template <typename T> 49 bool OCReadIncreasing(StringPiece* src, T* result); 50 51 // Read/WriteIncreasing<string> 52 template <> 53 void OCWriteIncreasing<string>(string* dest, const string& val) { 54 OrderedCode::WriteString(dest, val); 55 } 56 template <> 57 bool OCReadIncreasing<string>(StringPiece* src, string* result) { 58 return OrderedCode::ReadString(src, result); 59 } 60 61 // Read/WriteIncreasing<uint64> 62 template <> 63 void OCWriteIncreasing<uint64>(string* dest, const uint64& val) { 64 OrderedCode::WriteNumIncreasing(dest, val); 65 } 66 template <> 67 bool OCReadIncreasing<uint64>(StringPiece* src, uint64* result) { 68 return OrderedCode::ReadNumIncreasing(src, result); 69 } 70 71 // Read/WriteIncreasing<int64> 72 template <> 73 void OCWriteIncreasing<int64>(string* dest, const int64& val) { 74 OrderedCode::WriteSignedNumIncreasing(dest, val); 75 } 76 template <> 77 bool OCReadIncreasing<int64>(StringPiece* src, int64* result) { 78 return OrderedCode::ReadSignedNumIncreasing(src, result); 79 } 80 81 template <typename T> 82 string OCWrite(T val) { 83 string result; 84 OCWriteIncreasing<T>(&result, val); 85 return result; 86 } 87 88 template <typename T> 89 void OCWriteToString(string* result, T val) { 90 OCWriteIncreasing<T>(result, val); 91 } 92 93 template <typename T> 94 bool OCRead(StringPiece* s, T* val) { 95 return OCReadIncreasing<T>(s, val); 96 } 97 98 // --------------------------------------------------------------------- 99 // Numbers 100 101 template <typename T> 102 T TestRead(const string& a) { 103 // gracefully reject any proper prefix of an encoding 104 for (int i = 0; i < a.size() - 1; ++i) { 105 StringPiece s(a.data(), i); 106 CHECK(!OCRead<T>(&s, nullptr)); 107 CHECK_EQ(s, a.substr(0, i)); 108 } 109 110 StringPiece s(a); 111 T v; 112 CHECK(OCRead<T>(&s, &v)); 113 CHECK(s.empty()); 114 return v; 115 } 116 117 template <typename T> 118 void TestWriteRead(T expected) { 119 EXPECT_EQ(expected, TestRead<T>(OCWrite<T>(expected))); 120 } 121 122 // Verifies that the second Write* call appends a non-empty string to its 123 // output. 124 template <typename T, typename U> 125 void TestWriteAppends(T first, U second) { 126 string encoded; 127 OCWriteToString<T>(&encoded, first); 128 string encoded_first_only = encoded; 129 OCWriteToString<U>(&encoded, second); 130 EXPECT_NE(encoded, encoded_first_only); 131 EXPECT_TRUE(StringPiece(encoded).starts_with(encoded_first_only)); 132 } 133 134 template <typename T> 135 void TestNumbers(T multiplier) { 136 // first test powers of 2 (and nearby numbers) 137 for (T x = std::numeric_limits<T>().max(); x != 0; x /= 2) { 138 TestWriteRead(multiplier * (x - 1)); 139 TestWriteRead(multiplier * x); 140 if (x != std::numeric_limits<T>::max()) { 141 TestWriteRead(multiplier * (x + 1)); 142 } else if (multiplier < 0 && multiplier == -1) { 143 TestWriteRead(-x - 1); 144 } 145 } 146 147 random::PhiloxRandom philox(301, 17); 148 random::SimplePhilox rnd(&philox); 149 for (int bits = 1; bits <= std::numeric_limits<T>().digits; ++bits) { 150 // test random non-negative numbers with given number of significant bits 151 const uint64 mask = (~0ULL) >> (64 - bits); 152 for (int i = 0; i < 1000; i++) { 153 T x = rnd.Rand64() & mask; 154 TestWriteRead(multiplier * x); 155 T y = rnd.Rand64() & mask; 156 TestWriteAppends(multiplier * x, multiplier * y); 157 } 158 } 159 } 160 161 // Return true iff 'a' is "before" 'b' 162 bool CompareStrings(const string& a, const string& b) { return (a < b); } 163 164 template <typename T> 165 void TestNumberOrdering() { 166 // first the negative numbers (if T is signed, otherwise no-op) 167 string laststr = OCWrite<T>(std::numeric_limits<T>().min()); 168 for (T num = std::numeric_limits<T>().min() / 2; num != 0; num /= 2) { 169 string strminus1 = OCWrite<T>(num - 1); 170 string str = OCWrite<T>(num); 171 string strplus1 = OCWrite<T>(num + 1); 172 173 CHECK(CompareStrings(strminus1, str)); 174 CHECK(CompareStrings(str, strplus1)); 175 176 // Compare 'str' with 'laststr'. When we approach 0, 'laststr' is 177 // not necessarily before 'strminus1'. 178 CHECK(CompareStrings(laststr, str)); 179 laststr = str; 180 } 181 182 // then the positive numbers 183 laststr = OCWrite<T>(0); 184 T num = 1; 185 while (num < std::numeric_limits<T>().max() / 2) { 186 num *= 2; 187 string strminus1 = OCWrite<T>(num - 1); 188 string str = OCWrite<T>(num); 189 string strplus1 = OCWrite<T>(num + 1); 190 191 CHECK(CompareStrings(strminus1, str)); 192 CHECK(CompareStrings(str, strplus1)); 193 194 // Compare 'str' with 'laststr'. 195 CHECK(CompareStrings(laststr, str)); 196 laststr = str; 197 } 198 } 199 200 // Helper routine for testing TEST_SkipToNextSpecialByte 201 size_t FindSpecial(const string& x) { 202 const char* p = x.data(); 203 const char* limit = p + x.size(); 204 const char* result = OrderedCode::TEST_SkipToNextSpecialByte(p, limit); 205 return result - p; 206 } 207 208 // Helper function template to create strings from string literals (excluding 209 // the terminal zero byte of the underlying character array). 210 template <size_t N> 211 string ByteSequence(const char (&arr)[N]) { 212 return string(arr, N - 1); 213 } 214 215 TEST(OrderedCode, SkipToNextSpecialByte) { 216 for (size_t len = 0; len < 256; len++) { 217 random::PhiloxRandom philox(301, 17); 218 random::SimplePhilox rnd(&philox); 219 string x; 220 while (x.size() < len) { 221 char c = 1 + rnd.Uniform(254); 222 ASSERT_NE(c, 0); 223 ASSERT_NE(c, 255); 224 x += c; // No 0 bytes, no 255 bytes 225 } 226 EXPECT_EQ(FindSpecial(x), x.size()); 227 for (size_t special_pos = 0; special_pos < len; special_pos++) { 228 for (size_t special_test = 0; special_test < 2; special_test++) { 229 const char special_byte = (special_test == 0) ? 0 : 255; 230 string y = x; 231 y[special_pos] = special_byte; 232 EXPECT_EQ(FindSpecial(y), special_pos); 233 if (special_pos < 16) { 234 // Add some special bytes after the one at special_pos to make sure 235 // we still return the earliest special byte in the string 236 for (size_t rest = special_pos + 1; rest < len; rest++) { 237 if (rnd.OneIn(3)) { 238 y[rest] = rnd.OneIn(2) ? 0 : 255; 239 EXPECT_EQ(FindSpecial(y), special_pos); 240 } 241 } 242 } 243 } 244 } 245 } 246 } 247 248 TEST(OrderedCode, ExhaustiveFindSpecial) { 249 char buf[16]; 250 char* limit = buf + sizeof(buf); 251 int count = 0; 252 for (int start_offset = 0; start_offset <= 5; start_offset += 5) { 253 // We test exhaustively with all combinations of 3 bytes starting 254 // at offset 0 and offset 5 (so as to test with the bytes at both 255 // ends of a 64-bit word). 256 for (size_t i = 0; i < sizeof(buf); i++) { 257 buf[i] = 'a'; // Not a special byte 258 } 259 for (int b0 = 0; b0 < 256; b0++) { 260 for (int b1 = 0; b1 < 256; b1++) { 261 for (int b2 = 0; b2 < 256; b2++) { 262 buf[start_offset + 0] = b0; 263 buf[start_offset + 1] = b1; 264 buf[start_offset + 2] = b2; 265 char* expected; 266 if (b0 == 0 || b0 == 255) { 267 expected = &buf[start_offset]; 268 } else if (b1 == 0 || b1 == 255) { 269 expected = &buf[start_offset + 1]; 270 } else if (b2 == 0 || b2 == 255) { 271 expected = &buf[start_offset + 2]; 272 } else { 273 expected = limit; 274 } 275 count++; 276 EXPECT_EQ(expected, 277 OrderedCode::TEST_SkipToNextSpecialByte(buf, limit)); 278 } 279 } 280 } 281 } 282 EXPECT_EQ(count, 256 * 256 * 256 * 2); 283 } 284 285 TEST(Uint64, EncodeDecode) { TestNumbers<uint64>(1); } 286 287 TEST(Uint64, Ordering) { TestNumberOrdering<uint64>(); } 288 289 TEST(Int64, EncodeDecode) { 290 TestNumbers<int64>(1); 291 TestNumbers<int64>(-1); 292 } 293 294 TEST(Int64, Ordering) { TestNumberOrdering<int64>(); } 295 296 // Returns the bitwise complement of s. 297 inline string StrNot(const string& s) { 298 string result; 299 for (string::const_iterator it = s.begin(); it != s.end(); ++it) 300 result.push_back(~*it); 301 return result; 302 } 303 304 template <typename T> 305 void TestInvalidEncoding(const string& s) { 306 StringPiece p(s); 307 EXPECT_FALSE(OCRead<T>(&p, nullptr)); 308 EXPECT_EQ(s, p); 309 } 310 311 TEST(OrderedCodeInvalidEncodingsTest, Overflow) { 312 // 1U << 64, increasing and decreasing 313 const string k2xx64U = "\x09\x01" + string(8, 0); 314 TestInvalidEncoding<uint64>(k2xx64U); 315 316 // 1 << 63 and ~(1 << 63), increasing and decreasing 317 const string k2xx63 = "\xff\xc0\x80" + string(7, 0); 318 TestInvalidEncoding<int64>(k2xx63); 319 TestInvalidEncoding<int64>(StrNot(k2xx63)); 320 } 321 322 TEST(OrderedCodeInvalidEncodingsDeathTest, NonCanonical) { 323 // Test "ambiguous"/"non-canonical" encodings. 324 // These are non-minimal (but otherwise "valid") encodings that 325 // differ from the minimal encoding chosen by OrderedCode::WriteXXX 326 // and thus should be avoided to not mess up the string ordering of 327 // encodings. 328 329 random::PhiloxRandom philox(301, 17); 330 random::SimplePhilox rnd(&philox); 331 332 for (int n = 2; n <= 9; ++n) { 333 // The zero in non_minimal[1] is "redundant". 334 string non_minimal = 335 string(1, n - 1) + string(1, 0) + RandomString(&rnd, n - 2); 336 EXPECT_EQ(n, non_minimal.length()); 337 338 EXPECT_NE(OCWrite<uint64>(0), non_minimal); 339 #ifndef NDEBUG 340 StringPiece s(non_minimal); 341 EXPECT_DEATH(OrderedCode::ReadNumIncreasing(&s, nullptr), 342 "invalid encoding"); 343 #else 344 TestRead<uint64>(non_minimal); 345 #endif 346 } 347 348 for (int n = 2; n <= 10; ++n) { 349 // Header with 1 sign bit and n-1 size bits. 350 string header = string(n / 8, 0xff) + string(1, 0xff << (8 - (n % 8))); 351 // There are more than 7 zero bits between header bits and "payload". 352 string non_minimal = header + 353 string(1, rnd.Uniform(256) & ~*header.rbegin()) + 354 RandomString(&rnd, n - header.length() - 1); 355 EXPECT_EQ(n, non_minimal.length()); 356 357 EXPECT_NE(OCWrite<int64>(0), non_minimal); 358 #ifndef NDEBUG 359 StringPiece s(non_minimal); 360 EXPECT_DEATH(OrderedCode::ReadSignedNumIncreasing(&s, nullptr), 361 "invalid encoding") 362 << n; 363 #else 364 TestRead<int64>(non_minimal); 365 #endif 366 } 367 } 368 369 // Returns random number with specified number of bits, 370 // i.e., in the range [2^(bits-1),2^bits). 371 uint64 NextBits(random::SimplePhilox* rnd, int bits) { 372 return (bits != 0) 373 ? (rnd->Rand64() % (1LL << (bits - 1))) + (1LL << (bits - 1)) 374 : 0; 375 } 376 377 template <typename T> 378 void BM_WriteNum(int n, T multiplier) { 379 constexpr int kValues = 64; 380 T values[kValues]; 381 random::PhiloxRandom philox(301, 17); 382 random::SimplePhilox rnd(&philox); 383 // Use enough distinct values to confuse the branch predictor 384 for (int i = 0; i < kValues; i++) { 385 values[i] = NextBits(&rnd, n % 64) * multiplier; 386 } 387 string result; 388 int index = 0; 389 while (n-- > 0) { 390 result.clear(); 391 OCWriteToString<T>(&result, values[index % kValues]); 392 index++; 393 } 394 } 395 396 template <typename T> 397 void BM_ReadNum(int n, T multiplier) { 398 string x; 399 random::PhiloxRandom philox(301, 17); 400 random::SimplePhilox rnd(&philox); 401 // Use enough distinct values to confuse the branch predictor 402 constexpr int kValues = 64; 403 string values[kValues]; 404 for (int i = 0; i < kValues; i++) { 405 T val = NextBits(&rnd, i % 64) * multiplier; 406 values[i] = OCWrite<T>(val); 407 } 408 uint32 index = 0; 409 while (n-- > 0) { 410 T val; 411 StringPiece s = values[index++ % kValues]; 412 OCRead<T>(&s, &val); 413 } 414 } 415 416 #define BENCHMARK_NUM(name, T, multiplier) \ 417 void BM_Write##name(int n) { BM_WriteNum<T>(n, multiplier); } \ 418 BENCHMARK(BM_Write##name); \ 419 void BM_Read##name(int n) { BM_ReadNum<T>(n, multiplier); } \ 420 BENCHMARK(BM_Read##name) 421 422 BENCHMARK_NUM(NumIncreasing, uint64, 1); 423 BENCHMARK_NUM(SignedNum, int64, 1); 424 BENCHMARK_NUM(SignedNumNegative, int64, -1); 425 426 #undef BENCHMARK_NUM 427 428 // --------------------------------------------------------------------- 429 // Strings 430 431 TEST(String, EncodeDecode) { 432 random::PhiloxRandom philox(301, 17); 433 random::SimplePhilox rnd(&philox); 434 435 for (int len = 0; len < 256; len++) { 436 const string a = RandomString(&rnd, len); 437 TestWriteRead(a); 438 for (int len2 = 0; len2 < 64; len2++) { 439 const string b = RandomString(&rnd, len2); 440 441 TestWriteAppends(a, b); 442 443 string out; 444 OCWriteToString<string>(&out, a); 445 OCWriteToString<string>(&out, b); 446 447 string a2, b2, dummy; 448 StringPiece s = out; 449 StringPiece s2 = out; 450 CHECK(OCRead<string>(&s, &a2)); 451 CHECK(OCRead<string>(&s2, nullptr)); 452 CHECK_EQ(s, s2); 453 454 CHECK(OCRead<string>(&s, &b2)); 455 CHECK(OCRead<string>(&s2, nullptr)); 456 CHECK_EQ(s, s2); 457 458 CHECK(!OCRead<string>(&s, &dummy)); 459 CHECK(!OCRead<string>(&s2, nullptr)); 460 CHECK_EQ(a, a2); 461 CHECK_EQ(b, b2); 462 CHECK(s.empty()); 463 CHECK(s2.empty()); 464 } 465 } 466 } 467 468 // 'str' is a string literal that may contain '\0'. 469 #define STATIC_STR(str) StringPiece((str), sizeof(str) - 1) 470 471 string EncodeStringIncreasing(StringPiece value) { 472 string encoded; 473 OrderedCode::WriteString(&encoded, value); 474 return encoded; 475 } 476 477 TEST(String, Increasing) { 478 // Here are a series of strings in non-decreasing order, including 479 // consecutive strings such that the second one is equal to, a proper 480 // prefix of, or has the same length as the first one. Most also contain 481 // the special escaping characters '\x00' and '\xff'. 482 ASSERT_EQ(EncodeStringIncreasing(STATIC_STR("")), 483 EncodeStringIncreasing(STATIC_STR(""))); 484 485 ASSERT_LT(EncodeStringIncreasing(STATIC_STR("")), 486 EncodeStringIncreasing(STATIC_STR("\x00"))); 487 488 ASSERT_EQ(EncodeStringIncreasing(STATIC_STR("\x00")), 489 EncodeStringIncreasing(STATIC_STR("\x00"))); 490 491 ASSERT_LT(EncodeStringIncreasing(STATIC_STR("\x00")), 492 EncodeStringIncreasing(STATIC_STR("\x01"))); 493 494 ASSERT_LT(EncodeStringIncreasing(STATIC_STR("\x01")), 495 EncodeStringIncreasing(STATIC_STR("a"))); 496 497 ASSERT_EQ(EncodeStringIncreasing(STATIC_STR("a")), 498 EncodeStringIncreasing(STATIC_STR("a"))); 499 500 ASSERT_LT(EncodeStringIncreasing(STATIC_STR("a")), 501 EncodeStringIncreasing(STATIC_STR("aa"))); 502 503 ASSERT_LT(EncodeStringIncreasing(STATIC_STR("aa")), 504 EncodeStringIncreasing(STATIC_STR("\xff"))); 505 506 ASSERT_LT(EncodeStringIncreasing(STATIC_STR("\xff")), 507 EncodeStringIncreasing(STATIC_STR("\xff\x00"))); 508 509 ASSERT_LT(EncodeStringIncreasing(STATIC_STR("\xff\x00")), 510 EncodeStringIncreasing(STATIC_STR("\xff\x01"))); 511 } 512 513 TEST(EncodingIsExpected, String) { 514 std::vector<std::pair<string, string>> data = { 515 {"", string("\x00\x01", 2)}, 516 {"foo", string("foo\x00\x01", 5)}, 517 {"hello", string("hello\x00\x01", 7)}, 518 {string("\x00\x01\xff", 3), string("\x00\xff\x01\xff\x00\x00\x01", 7)}, 519 }; 520 for (const auto& t : data) { 521 string result; 522 OrderedCode::WriteString(&result, t.first); 523 EXPECT_EQ(t.second, result); 524 525 StringPiece in = result; 526 string decoded; 527 EXPECT_TRUE(OrderedCode::ReadString(&in, &decoded)); 528 EXPECT_EQ(t.first, decoded); 529 EXPECT_EQ("", in); 530 } 531 } 532 533 TEST(EncodingIsExpected, Unsigned) { 534 std::vector<std::pair<uint64, string>> data = { 535 {0x0ull, ByteSequence("\000")}, 536 {0x1ull, ByteSequence("\001\001")}, 537 {0x2ull, ByteSequence("\001\002")}, 538 {0x1ull, ByteSequence("\001\001")}, 539 {0x2ull, ByteSequence("\001\002")}, 540 {0x3ull, ByteSequence("\001\003")}, 541 {0x3ull, ByteSequence("\001\003")}, 542 {0x4ull, ByteSequence("\001\004")}, 543 {0x5ull, ByteSequence("\001\005")}, 544 {0x7ull, ByteSequence("\001\007")}, 545 {0x8ull, ByteSequence("\001\010")}, 546 {0x9ull, ByteSequence("\001\t")}, 547 {0xfull, ByteSequence("\001\017")}, 548 {0x10ull, ByteSequence("\001\020")}, 549 {0x11ull, ByteSequence("\001\021")}, 550 {0x1full, ByteSequence("\001\037")}, 551 {0x20ull, ByteSequence("\001 ")}, 552 {0x21ull, ByteSequence("\001!")}, 553 {0x3full, ByteSequence("\001?")}, 554 {0x40ull, ByteSequence("\001@")}, 555 {0x41ull, ByteSequence("\001A")}, 556 {0x7full, ByteSequence("\001\177")}, 557 {0x80ull, ByteSequence("\001\200")}, 558 {0x81ull, ByteSequence("\001\201")}, 559 {0xffull, ByteSequence("\001\377")}, 560 {0x100ull, ByteSequence("\002\001\000")}, 561 {0x101ull, ByteSequence("\002\001\001")}, 562 {0x1ffull, ByteSequence("\002\001\377")}, 563 {0x200ull, ByteSequence("\002\002\000")}, 564 {0x201ull, ByteSequence("\002\002\001")}, 565 {0x3ffull, ByteSequence("\002\003\377")}, 566 {0x400ull, ByteSequence("\002\004\000")}, 567 {0x401ull, ByteSequence("\002\004\001")}, 568 {0x7ffull, ByteSequence("\002\007\377")}, 569 {0x800ull, ByteSequence("\002\010\000")}, 570 {0x801ull, ByteSequence("\002\010\001")}, 571 {0xfffull, ByteSequence("\002\017\377")}, 572 {0x1000ull, ByteSequence("\002\020\000")}, 573 {0x1001ull, ByteSequence("\002\020\001")}, 574 {0x1fffull, ByteSequence("\002\037\377")}, 575 {0x2000ull, ByteSequence("\002 \000")}, 576 {0x2001ull, ByteSequence("\002 \001")}, 577 {0x3fffull, ByteSequence("\002?\377")}, 578 {0x4000ull, ByteSequence("\002@\000")}, 579 {0x4001ull, ByteSequence("\002@\001")}, 580 {0x7fffull, ByteSequence("\002\177\377")}, 581 {0x8000ull, ByteSequence("\002\200\000")}, 582 {0x8001ull, ByteSequence("\002\200\001")}, 583 {0xffffull, ByteSequence("\002\377\377")}, 584 {0x10000ull, ByteSequence("\003\001\000\000")}, 585 {0x10001ull, ByteSequence("\003\001\000\001")}, 586 {0x1ffffull, ByteSequence("\003\001\377\377")}, 587 {0x20000ull, ByteSequence("\003\002\000\000")}, 588 {0x20001ull, ByteSequence("\003\002\000\001")}, 589 {0x3ffffull, ByteSequence("\003\003\377\377")}, 590 {0x40000ull, ByteSequence("\003\004\000\000")}, 591 {0x40001ull, ByteSequence("\003\004\000\001")}, 592 {0x7ffffull, ByteSequence("\003\007\377\377")}, 593 {0x80000ull, ByteSequence("\003\010\000\000")}, 594 {0x80001ull, ByteSequence("\003\010\000\001")}, 595 {0xfffffull, ByteSequence("\003\017\377\377")}, 596 {0x100000ull, ByteSequence("\003\020\000\000")}, 597 {0x100001ull, ByteSequence("\003\020\000\001")}, 598 {0x1fffffull, ByteSequence("\003\037\377\377")}, 599 {0x200000ull, ByteSequence("\003 \000\000")}, 600 {0x200001ull, ByteSequence("\003 \000\001")}, 601 {0x3fffffull, ByteSequence("\003?\377\377")}, 602 {0x400000ull, ByteSequence("\003@\000\000")}, 603 {0x400001ull, ByteSequence("\003@\000\001")}, 604 {0x7fffffull, ByteSequence("\003\177\377\377")}, 605 {0x800000ull, ByteSequence("\003\200\000\000")}, 606 {0x800001ull, ByteSequence("\003\200\000\001")}, 607 {0xffffffull, ByteSequence("\003\377\377\377")}, 608 {0x1000000ull, ByteSequence("\004\001\000\000\000")}, 609 {0x1000001ull, ByteSequence("\004\001\000\000\001")}, 610 {0x1ffffffull, ByteSequence("\004\001\377\377\377")}, 611 {0x2000000ull, ByteSequence("\004\002\000\000\000")}, 612 {0x2000001ull, ByteSequence("\004\002\000\000\001")}, 613 {0x3ffffffull, ByteSequence("\004\003\377\377\377")}, 614 {0x4000000ull, ByteSequence("\004\004\000\000\000")}, 615 {0x4000001ull, ByteSequence("\004\004\000\000\001")}, 616 {0x7ffffffull, ByteSequence("\004\007\377\377\377")}, 617 {0x8000000ull, ByteSequence("\004\010\000\000\000")}, 618 {0x8000001ull, ByteSequence("\004\010\000\000\001")}, 619 {0xfffffffull, ByteSequence("\004\017\377\377\377")}, 620 {0x10000000ull, ByteSequence("\004\020\000\000\000")}, 621 {0x10000001ull, ByteSequence("\004\020\000\000\001")}, 622 {0x1fffffffull, ByteSequence("\004\037\377\377\377")}, 623 {0x20000000ull, ByteSequence("\004 \000\000\000")}, 624 {0x20000001ull, ByteSequence("\004 \000\000\001")}, 625 {0x3fffffffull, ByteSequence("\004?\377\377\377")}, 626 {0x40000000ull, ByteSequence("\004@\000\000\000")}, 627 {0x40000001ull, ByteSequence("\004@\000\000\001")}, 628 {0x7fffffffull, ByteSequence("\004\177\377\377\377")}, 629 {0x80000000ull, ByteSequence("\004\200\000\000\000")}, 630 {0x80000001ull, ByteSequence("\004\200\000\000\001")}, 631 {0xffffffffull, ByteSequence("\004\377\377\377\377")}, 632 {0x100000000ull, ByteSequence("\005\001\000\000\000\000")}, 633 {0x100000001ull, ByteSequence("\005\001\000\000\000\001")}, 634 {0x1ffffffffull, ByteSequence("\005\001\377\377\377\377")}, 635 {0x200000000ull, ByteSequence("\005\002\000\000\000\000")}, 636 {0x200000001ull, ByteSequence("\005\002\000\000\000\001")}, 637 {0x3ffffffffull, ByteSequence("\005\003\377\377\377\377")}, 638 {0x400000000ull, ByteSequence("\005\004\000\000\000\000")}, 639 {0x400000001ull, ByteSequence("\005\004\000\000\000\001")}, 640 {0x7ffffffffull, ByteSequence("\005\007\377\377\377\377")}, 641 {0x800000000ull, ByteSequence("\005\010\000\000\000\000")}, 642 {0x800000001ull, ByteSequence("\005\010\000\000\000\001")}, 643 {0xfffffffffull, ByteSequence("\005\017\377\377\377\377")}, 644 {0x1000000000ull, ByteSequence("\005\020\000\000\000\000")}, 645 {0x1000000001ull, ByteSequence("\005\020\000\000\000\001")}, 646 {0x1fffffffffull, ByteSequence("\005\037\377\377\377\377")}, 647 {0x2000000000ull, ByteSequence("\005 \000\000\000\000")}, 648 {0x2000000001ull, ByteSequence("\005 \000\000\000\001")}, 649 {0x3fffffffffull, ByteSequence("\005?\377\377\377\377")}, 650 {0x4000000000ull, ByteSequence("\005@\000\000\000\000")}, 651 {0x4000000001ull, ByteSequence("\005@\000\000\000\001")}, 652 {0x7fffffffffull, ByteSequence("\005\177\377\377\377\377")}, 653 {0x8000000000ull, ByteSequence("\005\200\000\000\000\000")}, 654 {0x8000000001ull, ByteSequence("\005\200\000\000\000\001")}, 655 {0xffffffffffull, ByteSequence("\005\377\377\377\377\377")}, 656 {0x10000000000ull, ByteSequence("\006\001\000\000\000\000\000")}, 657 {0x10000000001ull, ByteSequence("\006\001\000\000\000\000\001")}, 658 {0x1ffffffffffull, ByteSequence("\006\001\377\377\377\377\377")}, 659 {0x20000000000ull, ByteSequence("\006\002\000\000\000\000\000")}, 660 {0x20000000001ull, ByteSequence("\006\002\000\000\000\000\001")}, 661 {0x3ffffffffffull, ByteSequence("\006\003\377\377\377\377\377")}, 662 {0x40000000000ull, ByteSequence("\006\004\000\000\000\000\000")}, 663 {0x40000000001ull, ByteSequence("\006\004\000\000\000\000\001")}, 664 {0x7ffffffffffull, ByteSequence("\006\007\377\377\377\377\377")}, 665 {0x80000000000ull, ByteSequence("\006\010\000\000\000\000\000")}, 666 {0x80000000001ull, ByteSequence("\006\010\000\000\000\000\001")}, 667 {0xfffffffffffull, ByteSequence("\006\017\377\377\377\377\377")}, 668 {0x100000000000ull, ByteSequence("\006\020\000\000\000\000\000")}, 669 {0x100000000001ull, ByteSequence("\006\020\000\000\000\000\001")}, 670 {0x1fffffffffffull, ByteSequence("\006\037\377\377\377\377\377")}, 671 {0x200000000000ull, ByteSequence("\006 \000\000\000\000\000")}, 672 {0x200000000001ull, ByteSequence("\006 \000\000\000\000\001")}, 673 {0x3fffffffffffull, ByteSequence("\006?\377\377\377\377\377")}, 674 {0x400000000000ull, ByteSequence("\006@\000\000\000\000\000")}, 675 {0x400000000001ull, ByteSequence("\006@\000\000\000\000\001")}, 676 {0x7fffffffffffull, ByteSequence("\006\177\377\377\377\377\377")}, 677 {0x800000000000ull, ByteSequence("\006\200\000\000\000\000\000")}, 678 {0x800000000001ull, ByteSequence("\006\200\000\000\000\000\001")}, 679 {0xffffffffffffull, ByteSequence("\006\377\377\377\377\377\377")}, 680 {0x1000000000000ull, ByteSequence("\007\001\000\000\000\000\000\000")}, 681 {0x1000000000001ull, ByteSequence("\007\001\000\000\000\000\000\001")}, 682 {0x1ffffffffffffull, ByteSequence("\007\001\377\377\377\377\377\377")}, 683 {0x2000000000000ull, ByteSequence("\007\002\000\000\000\000\000\000")}, 684 {0x2000000000001ull, ByteSequence("\007\002\000\000\000\000\000\001")}, 685 {0x3ffffffffffffull, ByteSequence("\007\003\377\377\377\377\377\377")}, 686 {0x4000000000000ull, ByteSequence("\007\004\000\000\000\000\000\000")}, 687 {0x4000000000001ull, ByteSequence("\007\004\000\000\000\000\000\001")}, 688 {0x7ffffffffffffull, ByteSequence("\007\007\377\377\377\377\377\377")}, 689 {0x8000000000000ull, ByteSequence("\007\010\000\000\000\000\000\000")}, 690 {0x8000000000001ull, ByteSequence("\007\010\000\000\000\000\000\001")}, 691 {0xfffffffffffffull, ByteSequence("\007\017\377\377\377\377\377\377")}, 692 {0x10000000000000ull, ByteSequence("\007\020\000\000\000\000\000\000")}, 693 {0x10000000000001ull, ByteSequence("\007\020\000\000\000\000\000\001")}, 694 {0x1fffffffffffffull, ByteSequence("\007\037\377\377\377\377\377\377")}, 695 {0x20000000000000ull, ByteSequence("\007 \000\000\000\000\000\000")}, 696 {0x20000000000001ull, ByteSequence("\007 \000\000\000\000\000\001")}, 697 {0x3fffffffffffffull, ByteSequence("\007?\377\377\377\377\377\377")}, 698 {0x40000000000000ull, ByteSequence("\007@\000\000\000\000\000\000")}, 699 {0x40000000000001ull, ByteSequence("\007@\000\000\000\000\000\001")}, 700 {0x7fffffffffffffull, ByteSequence("\007\177\377\377\377\377\377\377")}, 701 {0x80000000000000ull, ByteSequence("\007\200\000\000\000\000\000\000")}, 702 {0x80000000000001ull, ByteSequence("\007\200\000\000\000\000\000\001")}, 703 {0xffffffffffffffull, ByteSequence("\007\377\377\377\377\377\377\377")}, 704 {0x100000000000000ull, 705 ByteSequence("\010\001\000\000\000\000\000\000\000")}, 706 {0x100000000000001ull, 707 ByteSequence("\010\001\000\000\000\000\000\000\001")}, 708 {0x1ffffffffffffffull, 709 ByteSequence("\010\001\377\377\377\377\377\377\377")}, 710 {0x200000000000000ull, 711 ByteSequence("\010\002\000\000\000\000\000\000\000")}, 712 {0x200000000000001ull, 713 ByteSequence("\010\002\000\000\000\000\000\000\001")}, 714 {0x3ffffffffffffffull, 715 ByteSequence("\010\003\377\377\377\377\377\377\377")}, 716 {0x400000000000000ull, 717 ByteSequence("\010\004\000\000\000\000\000\000\000")}, 718 {0x400000000000001ull, 719 ByteSequence("\010\004\000\000\000\000\000\000\001")}, 720 {0x7ffffffffffffffull, 721 ByteSequence("\010\007\377\377\377\377\377\377\377")}, 722 {0x800000000000000ull, 723 ByteSequence("\010\010\000\000\000\000\000\000\000")}, 724 {0x800000000000001ull, 725 ByteSequence("\010\010\000\000\000\000\000\000\001")}, 726 {0xfffffffffffffffull, 727 ByteSequence("\010\017\377\377\377\377\377\377\377")}, 728 {0x1000000000000000ull, 729 ByteSequence("\010\020\000\000\000\000\000\000\000")}, 730 {0x1000000000000001ull, 731 ByteSequence("\010\020\000\000\000\000\000\000\001")}, 732 {0x1fffffffffffffffull, 733 ByteSequence("\010\037\377\377\377\377\377\377\377")}, 734 {0x2000000000000000ull, 735 ByteSequence("\010 \000\000\000\000\000\000\000")}, 736 {0x2000000000000001ull, 737 ByteSequence("\010 \000\000\000\000\000\000\001")}, 738 {0x3fffffffffffffffull, 739 ByteSequence("\010?\377\377\377\377\377\377\377")}, 740 {0x4000000000000000ull, 741 ByteSequence("\010@\000\000\000\000\000\000\000")}, 742 {0x4000000000000001ull, 743 ByteSequence("\010@\000\000\000\000\000\000\001")}, 744 {0x7fffffffffffffffull, 745 ByteSequence("\010\177\377\377\377\377\377\377\377")}, 746 {0x8000000000000000ull, 747 ByteSequence("\010\200\000\000\000\000\000\000\000")}, 748 {0x8000000000000001ull, 749 ByteSequence("\010\200\000\000\000\000\000\000\001")}, 750 }; 751 for (const auto& t : data) { 752 uint64 num = t.first; 753 string result; 754 OrderedCode::WriteNumIncreasing(&result, num); 755 EXPECT_EQ(t.second, result) << std::hex << num; 756 757 StringPiece in = result; 758 uint64 decoded; 759 EXPECT_TRUE(OrderedCode::ReadNumIncreasing(&in, &decoded)); 760 EXPECT_EQ(num, decoded); 761 EXPECT_EQ("", in); 762 } 763 } 764 765 TEST(EncodingIsExpected, Signed) { 766 std::vector<std::pair<int64, string>> data = { 767 {0ll, ByteSequence("\200")}, 768 {1ll, ByteSequence("\201")}, 769 {2ll, ByteSequence("\202")}, 770 {1ll, ByteSequence("\201")}, 771 {2ll, ByteSequence("\202")}, 772 {3ll, ByteSequence("\203")}, 773 {3ll, ByteSequence("\203")}, 774 {4ll, ByteSequence("\204")}, 775 {5ll, ByteSequence("\205")}, 776 {7ll, ByteSequence("\207")}, 777 {8ll, ByteSequence("\210")}, 778 {9ll, ByteSequence("\211")}, 779 {15ll, ByteSequence("\217")}, 780 {16ll, ByteSequence("\220")}, 781 {17ll, ByteSequence("\221")}, 782 {31ll, ByteSequence("\237")}, 783 {32ll, ByteSequence("\240")}, 784 {33ll, ByteSequence("\241")}, 785 {63ll, ByteSequence("\277")}, 786 {64ll, ByteSequence("\300@")}, 787 {65ll, ByteSequence("\300A")}, 788 {127ll, ByteSequence("\300\177")}, 789 {128ll, ByteSequence("\300\200")}, 790 {129ll, ByteSequence("\300\201")}, 791 {255ll, ByteSequence("\300\377")}, 792 {256ll, ByteSequence("\301\000")}, 793 {257ll, ByteSequence("\301\001")}, 794 {511ll, ByteSequence("\301\377")}, 795 {512ll, ByteSequence("\302\000")}, 796 {513ll, ByteSequence("\302\001")}, 797 {1023ll, ByteSequence("\303\377")}, 798 {1024ll, ByteSequence("\304\000")}, 799 {1025ll, ByteSequence("\304\001")}, 800 {2047ll, ByteSequence("\307\377")}, 801 {2048ll, ByteSequence("\310\000")}, 802 {2049ll, ByteSequence("\310\001")}, 803 {4095ll, ByteSequence("\317\377")}, 804 {4096ll, ByteSequence("\320\000")}, 805 {4097ll, ByteSequence("\320\001")}, 806 {8191ll, ByteSequence("\337\377")}, 807 {8192ll, ByteSequence("\340 \000")}, 808 {8193ll, ByteSequence("\340 \001")}, 809 {16383ll, ByteSequence("\340?\377")}, 810 {16384ll, ByteSequence("\340@\000")}, 811 {16385ll, ByteSequence("\340@\001")}, 812 {32767ll, ByteSequence("\340\177\377")}, 813 {32768ll, ByteSequence("\340\200\000")}, 814 {32769ll, ByteSequence("\340\200\001")}, 815 {65535ll, ByteSequence("\340\377\377")}, 816 {65536ll, ByteSequence("\341\000\000")}, 817 {65537ll, ByteSequence("\341\000\001")}, 818 {131071ll, ByteSequence("\341\377\377")}, 819 {131072ll, ByteSequence("\342\000\000")}, 820 {131073ll, ByteSequence("\342\000\001")}, 821 {262143ll, ByteSequence("\343\377\377")}, 822 {262144ll, ByteSequence("\344\000\000")}, 823 {262145ll, ByteSequence("\344\000\001")}, 824 {524287ll, ByteSequence("\347\377\377")}, 825 {524288ll, ByteSequence("\350\000\000")}, 826 {524289ll, ByteSequence("\350\000\001")}, 827 {1048575ll, ByteSequence("\357\377\377")}, 828 {1048576ll, ByteSequence("\360\020\000\000")}, 829 {1048577ll, ByteSequence("\360\020\000\001")}, 830 {2097151ll, ByteSequence("\360\037\377\377")}, 831 {2097152ll, ByteSequence("\360 \000\000")}, 832 {2097153ll, ByteSequence("\360 \000\001")}, 833 {4194303ll, ByteSequence("\360?\377\377")}, 834 {4194304ll, ByteSequence("\360@\000\000")}, 835 {4194305ll, ByteSequence("\360@\000\001")}, 836 {8388607ll, ByteSequence("\360\177\377\377")}, 837 {8388608ll, ByteSequence("\360\200\000\000")}, 838 {8388609ll, ByteSequence("\360\200\000\001")}, 839 {16777215ll, ByteSequence("\360\377\377\377")}, 840 {16777216ll, ByteSequence("\361\000\000\000")}, 841 {16777217ll, ByteSequence("\361\000\000\001")}, 842 {33554431ll, ByteSequence("\361\377\377\377")}, 843 {33554432ll, ByteSequence("\362\000\000\000")}, 844 {33554433ll, ByteSequence("\362\000\000\001")}, 845 {67108863ll, ByteSequence("\363\377\377\377")}, 846 {67108864ll, ByteSequence("\364\000\000\000")}, 847 {67108865ll, ByteSequence("\364\000\000\001")}, 848 {134217727ll, ByteSequence("\367\377\377\377")}, 849 {134217728ll, ByteSequence("\370\010\000\000\000")}, 850 {134217729ll, ByteSequence("\370\010\000\000\001")}, 851 {268435455ll, ByteSequence("\370\017\377\377\377")}, 852 {268435456ll, ByteSequence("\370\020\000\000\000")}, 853 {268435457ll, ByteSequence("\370\020\000\000\001")}, 854 {536870911ll, ByteSequence("\370\037\377\377\377")}, 855 {536870912ll, ByteSequence("\370 \000\000\000")}, 856 {536870913ll, ByteSequence("\370 \000\000\001")}, 857 {1073741823ll, ByteSequence("\370?\377\377\377")}, 858 {1073741824ll, ByteSequence("\370@\000\000\000")}, 859 {1073741825ll, ByteSequence("\370@\000\000\001")}, 860 {2147483647ll, ByteSequence("\370\177\377\377\377")}, 861 {2147483648ll, ByteSequence("\370\200\000\000\000")}, 862 {2147483649ll, ByteSequence("\370\200\000\000\001")}, 863 {4294967295ll, ByteSequence("\370\377\377\377\377")}, 864 {4294967296ll, ByteSequence("\371\000\000\000\000")}, 865 {4294967297ll, ByteSequence("\371\000\000\000\001")}, 866 {8589934591ll, ByteSequence("\371\377\377\377\377")}, 867 {8589934592ll, ByteSequence("\372\000\000\000\000")}, 868 {8589934593ll, ByteSequence("\372\000\000\000\001")}, 869 {17179869183ll, ByteSequence("\373\377\377\377\377")}, 870 {17179869184ll, ByteSequence("\374\004\000\000\000\000")}, 871 {17179869185ll, ByteSequence("\374\004\000\000\000\001")}, 872 {34359738367ll, ByteSequence("\374\007\377\377\377\377")}, 873 {34359738368ll, ByteSequence("\374\010\000\000\000\000")}, 874 {34359738369ll, ByteSequence("\374\010\000\000\000\001")}, 875 {68719476735ll, ByteSequence("\374\017\377\377\377\377")}, 876 {68719476736ll, ByteSequence("\374\020\000\000\000\000")}, 877 {68719476737ll, ByteSequence("\374\020\000\000\000\001")}, 878 {137438953471ll, ByteSequence("\374\037\377\377\377\377")}, 879 {137438953472ll, ByteSequence("\374 \000\000\000\000")}, 880 {137438953473ll, ByteSequence("\374 \000\000\000\001")}, 881 {274877906943ll, ByteSequence("\374?\377\377\377\377")}, 882 {274877906944ll, ByteSequence("\374@\000\000\000\000")}, 883 {274877906945ll, ByteSequence("\374@\000\000\000\001")}, 884 {549755813887ll, ByteSequence("\374\177\377\377\377\377")}, 885 {549755813888ll, ByteSequence("\374\200\000\000\000\000")}, 886 {549755813889ll, ByteSequence("\374\200\000\000\000\001")}, 887 {1099511627775ll, ByteSequence("\374\377\377\377\377\377")}, 888 {1099511627776ll, ByteSequence("\375\000\000\000\000\000")}, 889 {1099511627777ll, ByteSequence("\375\000\000\000\000\001")}, 890 {2199023255551ll, ByteSequence("\375\377\377\377\377\377")}, 891 {2199023255552ll, ByteSequence("\376\002\000\000\000\000\000")}, 892 {2199023255553ll, ByteSequence("\376\002\000\000\000\000\001")}, 893 {4398046511103ll, ByteSequence("\376\003\377\377\377\377\377")}, 894 {4398046511104ll, ByteSequence("\376\004\000\000\000\000\000")}, 895 {4398046511105ll, ByteSequence("\376\004\000\000\000\000\001")}, 896 {8796093022207ll, ByteSequence("\376\007\377\377\377\377\377")}, 897 {8796093022208ll, ByteSequence("\376\010\000\000\000\000\000")}, 898 {8796093022209ll, ByteSequence("\376\010\000\000\000\000\001")}, 899 {17592186044415ll, ByteSequence("\376\017\377\377\377\377\377")}, 900 {17592186044416ll, ByteSequence("\376\020\000\000\000\000\000")}, 901 {17592186044417ll, ByteSequence("\376\020\000\000\000\000\001")}, 902 {35184372088831ll, ByteSequence("\376\037\377\377\377\377\377")}, 903 {35184372088832ll, ByteSequence("\376 \000\000\000\000\000")}, 904 {35184372088833ll, ByteSequence("\376 \000\000\000\000\001")}, 905 {70368744177663ll, ByteSequence("\376?\377\377\377\377\377")}, 906 {70368744177664ll, ByteSequence("\376@\000\000\000\000\000")}, 907 {70368744177665ll, ByteSequence("\376@\000\000\000\000\001")}, 908 {140737488355327ll, ByteSequence("\376\177\377\377\377\377\377")}, 909 {140737488355328ll, ByteSequence("\376\200\000\000\000\000\000")}, 910 {140737488355329ll, ByteSequence("\376\200\000\000\000\000\001")}, 911 {281474976710655ll, ByteSequence("\376\377\377\377\377\377\377")}, 912 {281474976710656ll, ByteSequence("\377\001\000\000\000\000\000\000")}, 913 {281474976710657ll, ByteSequence("\377\001\000\000\000\000\000\001")}, 914 {562949953421311ll, ByteSequence("\377\001\377\377\377\377\377\377")}, 915 {562949953421312ll, ByteSequence("\377\002\000\000\000\000\000\000")}, 916 {562949953421313ll, ByteSequence("\377\002\000\000\000\000\000\001")}, 917 {1125899906842623ll, ByteSequence("\377\003\377\377\377\377\377\377")}, 918 {1125899906842624ll, ByteSequence("\377\004\000\000\000\000\000\000")}, 919 {1125899906842625ll, ByteSequence("\377\004\000\000\000\000\000\001")}, 920 {2251799813685247ll, ByteSequence("\377\007\377\377\377\377\377\377")}, 921 {2251799813685248ll, ByteSequence("\377\010\000\000\000\000\000\000")}, 922 {2251799813685249ll, ByteSequence("\377\010\000\000\000\000\000\001")}, 923 {4503599627370495ll, ByteSequence("\377\017\377\377\377\377\377\377")}, 924 {4503599627370496ll, ByteSequence("\377\020\000\000\000\000\000\000")}, 925 {4503599627370497ll, ByteSequence("\377\020\000\000\000\000\000\001")}, 926 {9007199254740991ll, ByteSequence("\377\037\377\377\377\377\377\377")}, 927 {9007199254740992ll, ByteSequence("\377 \000\000\000\000\000\000")}, 928 {9007199254740993ll, ByteSequence("\377 \000\000\000\000\000\001")}, 929 {18014398509481983ll, ByteSequence("\377?\377\377\377\377\377\377")}, 930 {18014398509481984ll, ByteSequence("\377@\000\000\000\000\000\000")}, 931 {18014398509481985ll, ByteSequence("\377@\000\000\000\000\000\001")}, 932 {36028797018963967ll, ByteSequence("\377\177\377\377\377\377\377\377")}, 933 {36028797018963968ll, 934 ByteSequence("\377\200\200\000\000\000\000\000\000")}, 935 {36028797018963969ll, 936 ByteSequence("\377\200\200\000\000\000\000\000\001")}, 937 {72057594037927935ll, 938 ByteSequence("\377\200\377\377\377\377\377\377\377")}, 939 {72057594037927936ll, 940 ByteSequence("\377\201\000\000\000\000\000\000\000")}, 941 {72057594037927937ll, 942 ByteSequence("\377\201\000\000\000\000\000\000\001")}, 943 {144115188075855871ll, 944 ByteSequence("\377\201\377\377\377\377\377\377\377")}, 945 {144115188075855872ll, 946 ByteSequence("\377\202\000\000\000\000\000\000\000")}, 947 {144115188075855873ll, 948 ByteSequence("\377\202\000\000\000\000\000\000\001")}, 949 {288230376151711743ll, 950 ByteSequence("\377\203\377\377\377\377\377\377\377")}, 951 {288230376151711744ll, 952 ByteSequence("\377\204\000\000\000\000\000\000\000")}, 953 {288230376151711745ll, 954 ByteSequence("\377\204\000\000\000\000\000\000\001")}, 955 {576460752303423487ll, 956 ByteSequence("\377\207\377\377\377\377\377\377\377")}, 957 {576460752303423488ll, 958 ByteSequence("\377\210\000\000\000\000\000\000\000")}, 959 {576460752303423489ll, 960 ByteSequence("\377\210\000\000\000\000\000\000\001")}, 961 {1152921504606846975ll, 962 ByteSequence("\377\217\377\377\377\377\377\377\377")}, 963 {1152921504606846976ll, 964 ByteSequence("\377\220\000\000\000\000\000\000\000")}, 965 {1152921504606846977ll, 966 ByteSequence("\377\220\000\000\000\000\000\000\001")}, 967 {2305843009213693951ll, 968 ByteSequence("\377\237\377\377\377\377\377\377\377")}, 969 {2305843009213693952ll, 970 ByteSequence("\377\240\000\000\000\000\000\000\000")}, 971 {2305843009213693953ll, 972 ByteSequence("\377\240\000\000\000\000\000\000\001")}, 973 {4611686018427387903ll, 974 ByteSequence("\377\277\377\377\377\377\377\377\377")}, 975 {4611686018427387904ll, 976 ByteSequence("\377\300@\000\000\000\000\000\000\000")}, 977 {4611686018427387905ll, 978 ByteSequence("\377\300@\000\000\000\000\000\000\001")}, 979 {9223372036854775807ll, 980 ByteSequence("\377\300\177\377\377\377\377\377\377\377")}, 981 {-9223372036854775807ll, 982 ByteSequence("\000?\200\000\000\000\000\000\000\001")}, 983 {0ll, ByteSequence("\200")}, 984 {-1ll, ByteSequence("\177")}, 985 {-2ll, ByteSequence("~")}, 986 {-1ll, ByteSequence("\177")}, 987 {-2ll, ByteSequence("~")}, 988 {-3ll, ByteSequence("}")}, 989 {-3ll, ByteSequence("}")}, 990 {-4ll, ByteSequence("|")}, 991 {-5ll, ByteSequence("{")}, 992 {-7ll, ByteSequence("y")}, 993 {-8ll, ByteSequence("x")}, 994 {-9ll, ByteSequence("w")}, 995 {-15ll, ByteSequence("q")}, 996 {-16ll, ByteSequence("p")}, 997 {-17ll, ByteSequence("o")}, 998 {-31ll, ByteSequence("a")}, 999 {-32ll, ByteSequence("`")}, 1000 {-33ll, ByteSequence("_")}, 1001 {-63ll, ByteSequence("A")}, 1002 {-64ll, ByteSequence("@")}, 1003 {-65ll, ByteSequence("?\277")}, 1004 {-127ll, ByteSequence("?\201")}, 1005 {-128ll, ByteSequence("?\200")}, 1006 {-129ll, ByteSequence("?\177")}, 1007 {-255ll, ByteSequence("?\001")}, 1008 {-256ll, ByteSequence("?\000")}, 1009 {-257ll, ByteSequence(">\377")}, 1010 {-511ll, ByteSequence(">\001")}, 1011 {-512ll, ByteSequence(">\000")}, 1012 {-513ll, ByteSequence("=\377")}, 1013 {-1023ll, ByteSequence("<\001")}, 1014 {-1024ll, ByteSequence("<\000")}, 1015 {-1025ll, ByteSequence(";\377")}, 1016 {-2047ll, ByteSequence("8\001")}, 1017 {-2048ll, ByteSequence("8\000")}, 1018 {-2049ll, ByteSequence("7\377")}, 1019 {-4095ll, ByteSequence("0\001")}, 1020 {-4096ll, ByteSequence("0\000")}, 1021 {-4097ll, ByteSequence("/\377")}, 1022 {-8191ll, ByteSequence(" \001")}, 1023 {-8192ll, ByteSequence(" \000")}, 1024 {-8193ll, ByteSequence("\037\337\377")}, 1025 {-16383ll, ByteSequence("\037\300\001")}, 1026 {-16384ll, ByteSequence("\037\300\000")}, 1027 {-16385ll, ByteSequence("\037\277\377")}, 1028 {-32767ll, ByteSequence("\037\200\001")}, 1029 {-32768ll, ByteSequence("\037\200\000")}, 1030 {-32769ll, ByteSequence("\037\177\377")}, 1031 {-65535ll, ByteSequence("\037\000\001")}, 1032 {-65536ll, ByteSequence("\037\000\000")}, 1033 {-65537ll, ByteSequence("\036\377\377")}, 1034 {-131071ll, ByteSequence("\036\000\001")}, 1035 {-131072ll, ByteSequence("\036\000\000")}, 1036 {-131073ll, ByteSequence("\035\377\377")}, 1037 {-262143ll, ByteSequence("\034\000\001")}, 1038 {-262144ll, ByteSequence("\034\000\000")}, 1039 {-262145ll, ByteSequence("\033\377\377")}, 1040 {-524287ll, ByteSequence("\030\000\001")}, 1041 {-524288ll, ByteSequence("\030\000\000")}, 1042 {-524289ll, ByteSequence("\027\377\377")}, 1043 {-1048575ll, ByteSequence("\020\000\001")}, 1044 {-1048576ll, ByteSequence("\020\000\000")}, 1045 {-1048577ll, ByteSequence("\017\357\377\377")}, 1046 {-2097151ll, ByteSequence("\017\340\000\001")}, 1047 {-2097152ll, ByteSequence("\017\340\000\000")}, 1048 {-2097153ll, ByteSequence("\017\337\377\377")}, 1049 {-4194303ll, ByteSequence("\017\300\000\001")}, 1050 {-4194304ll, ByteSequence("\017\300\000\000")}, 1051 {-4194305ll, ByteSequence("\017\277\377\377")}, 1052 {-8388607ll, ByteSequence("\017\200\000\001")}, 1053 {-8388608ll, ByteSequence("\017\200\000\000")}, 1054 {-8388609ll, ByteSequence("\017\177\377\377")}, 1055 {-16777215ll, ByteSequence("\017\000\000\001")}, 1056 {-16777216ll, ByteSequence("\017\000\000\000")}, 1057 {-16777217ll, ByteSequence("\016\377\377\377")}, 1058 {-33554431ll, ByteSequence("\016\000\000\001")}, 1059 {-33554432ll, ByteSequence("\016\000\000\000")}, 1060 {-33554433ll, ByteSequence("\r\377\377\377")}, 1061 {-67108863ll, ByteSequence("\014\000\000\001")}, 1062 {-67108864ll, ByteSequence("\014\000\000\000")}, 1063 {-67108865ll, ByteSequence("\013\377\377\377")}, 1064 {-134217727ll, ByteSequence("\010\000\000\001")}, 1065 {-134217728ll, ByteSequence("\010\000\000\000")}, 1066 {-134217729ll, ByteSequence("\007\367\377\377\377")}, 1067 {-268435455ll, ByteSequence("\007\360\000\000\001")}, 1068 {-268435456ll, ByteSequence("\007\360\000\000\000")}, 1069 {-268435457ll, ByteSequence("\007\357\377\377\377")}, 1070 {-536870911ll, ByteSequence("\007\340\000\000\001")}, 1071 {-536870912ll, ByteSequence("\007\340\000\000\000")}, 1072 {-536870913ll, ByteSequence("\007\337\377\377\377")}, 1073 {-1073741823ll, ByteSequence("\007\300\000\000\001")}, 1074 {-1073741824ll, ByteSequence("\007\300\000\000\000")}, 1075 {-1073741825ll, ByteSequence("\007\277\377\377\377")}, 1076 {-2147483647ll, ByteSequence("\007\200\000\000\001")}, 1077 {-2147483648ll, ByteSequence("\007\200\000\000\000")}, 1078 {-2147483649ll, ByteSequence("\007\177\377\377\377")}, 1079 {-4294967295ll, ByteSequence("\007\000\000\000\001")}, 1080 {-4294967296ll, ByteSequence("\007\000\000\000\000")}, 1081 {-4294967297ll, ByteSequence("\006\377\377\377\377")}, 1082 {-8589934591ll, ByteSequence("\006\000\000\000\001")}, 1083 {-8589934592ll, ByteSequence("\006\000\000\000\000")}, 1084 {-8589934593ll, ByteSequence("\005\377\377\377\377")}, 1085 {-17179869183ll, ByteSequence("\004\000\000\000\001")}, 1086 {-17179869184ll, ByteSequence("\004\000\000\000\000")}, 1087 {-17179869185ll, ByteSequence("\003\373\377\377\377\377")}, 1088 {-34359738367ll, ByteSequence("\003\370\000\000\000\001")}, 1089 {-34359738368ll, ByteSequence("\003\370\000\000\000\000")}, 1090 {-34359738369ll, ByteSequence("\003\367\377\377\377\377")}, 1091 {-68719476735ll, ByteSequence("\003\360\000\000\000\001")}, 1092 {-68719476736ll, ByteSequence("\003\360\000\000\000\000")}, 1093 {-68719476737ll, ByteSequence("\003\357\377\377\377\377")}, 1094 {-137438953471ll, ByteSequence("\003\340\000\000\000\001")}, 1095 {-137438953472ll, ByteSequence("\003\340\000\000\000\000")}, 1096 {-137438953473ll, ByteSequence("\003\337\377\377\377\377")}, 1097 {-274877906943ll, ByteSequence("\003\300\000\000\000\001")}, 1098 {-274877906944ll, ByteSequence("\003\300\000\000\000\000")}, 1099 {-274877906945ll, ByteSequence("\003\277\377\377\377\377")}, 1100 {-549755813887ll, ByteSequence("\003\200\000\000\000\001")}, 1101 {-549755813888ll, ByteSequence("\003\200\000\000\000\000")}, 1102 {-549755813889ll, ByteSequence("\003\177\377\377\377\377")}, 1103 {-1099511627775ll, ByteSequence("\003\000\000\000\000\001")}, 1104 {-1099511627776ll, ByteSequence("\003\000\000\000\000\000")}, 1105 {-1099511627777ll, ByteSequence("\002\377\377\377\377\377")}, 1106 {-2199023255551ll, ByteSequence("\002\000\000\000\000\001")}, 1107 {-2199023255552ll, ByteSequence("\002\000\000\000\000\000")}, 1108 {-2199023255553ll, ByteSequence("\001\375\377\377\377\377\377")}, 1109 {-4398046511103ll, ByteSequence("\001\374\000\000\000\000\001")}, 1110 {-4398046511104ll, ByteSequence("\001\374\000\000\000\000\000")}, 1111 {-4398046511105ll, ByteSequence("\001\373\377\377\377\377\377")}, 1112 {-8796093022207ll, ByteSequence("\001\370\000\000\000\000\001")}, 1113 {-8796093022208ll, ByteSequence("\001\370\000\000\000\000\000")}, 1114 {-8796093022209ll, ByteSequence("\001\367\377\377\377\377\377")}, 1115 {-17592186044415ll, ByteSequence("\001\360\000\000\000\000\001")}, 1116 {-17592186044416ll, ByteSequence("\001\360\000\000\000\000\000")}, 1117 {-17592186044417ll, ByteSequence("\001\357\377\377\377\377\377")}, 1118 {-35184372088831ll, ByteSequence("\001\340\000\000\000\000\001")}, 1119 {-35184372088832ll, ByteSequence("\001\340\000\000\000\000\000")}, 1120 {-35184372088833ll, ByteSequence("\001\337\377\377\377\377\377")}, 1121 {-70368744177663ll, ByteSequence("\001\300\000\000\000\000\001")}, 1122 {-70368744177664ll, ByteSequence("\001\300\000\000\000\000\000")}, 1123 {-70368744177665ll, ByteSequence("\001\277\377\377\377\377\377")}, 1124 {-140737488355327ll, ByteSequence("\001\200\000\000\000\000\001")}, 1125 {-140737488355328ll, ByteSequence("\001\200\000\000\000\000\000")}, 1126 {-140737488355329ll, ByteSequence("\001\177\377\377\377\377\377")}, 1127 {-281474976710655ll, ByteSequence("\001\000\000\000\000\000\001")}, 1128 {-281474976710656ll, ByteSequence("\001\000\000\000\000\000\000")}, 1129 {-281474976710657ll, ByteSequence("\000\376\377\377\377\377\377\377")}, 1130 {-562949953421311ll, ByteSequence("\000\376\000\000\000\000\000\001")}, 1131 {-562949953421312ll, ByteSequence("\000\376\000\000\000\000\000\000")}, 1132 {-562949953421313ll, ByteSequence("\000\375\377\377\377\377\377\377")}, 1133 {-1125899906842623ll, ByteSequence("\000\374\000\000\000\000\000\001")}, 1134 {-1125899906842624ll, ByteSequence("\000\374\000\000\000\000\000\000")}, 1135 {-1125899906842625ll, ByteSequence("\000\373\377\377\377\377\377\377")}, 1136 {-2251799813685247ll, ByteSequence("\000\370\000\000\000\000\000\001")}, 1137 {-2251799813685248ll, ByteSequence("\000\370\000\000\000\000\000\000")}, 1138 {-2251799813685249ll, ByteSequence("\000\367\377\377\377\377\377\377")}, 1139 {-4503599627370495ll, ByteSequence("\000\360\000\000\000\000\000\001")}, 1140 {-4503599627370496ll, ByteSequence("\000\360\000\000\000\000\000\000")}, 1141 {-4503599627370497ll, ByteSequence("\000\357\377\377\377\377\377\377")}, 1142 {-9007199254740991ll, ByteSequence("\000\340\000\000\000\000\000\001")}, 1143 {-9007199254740992ll, ByteSequence("\000\340\000\000\000\000\000\000")}, 1144 {-9007199254740993ll, ByteSequence("\000\337\377\377\377\377\377\377")}, 1145 {-18014398509481983ll, ByteSequence("\000\300\000\000\000\000\000\001")}, 1146 {-18014398509481984ll, ByteSequence("\000\300\000\000\000\000\000\000")}, 1147 {-18014398509481985ll, ByteSequence("\000\277\377\377\377\377\377\377")}, 1148 {-36028797018963967ll, ByteSequence("\000\200\000\000\000\000\000\001")}, 1149 {-36028797018963968ll, ByteSequence("\000\200\000\000\000\000\000\000")}, 1150 {-36028797018963969ll, 1151 ByteSequence("\000\177\177\377\377\377\377\377\377")}, 1152 {-72057594037927935ll, 1153 ByteSequence("\000\177\000\000\000\000\000\000\001")}, 1154 {-72057594037927936ll, 1155 ByteSequence("\000\177\000\000\000\000\000\000\000")}, 1156 {-72057594037927937ll, ByteSequence("\000~\377\377\377\377\377\377\377")}, 1157 {-144115188075855871ll, 1158 ByteSequence("\000~\000\000\000\000\000\000\001")}, 1159 {-144115188075855872ll, 1160 ByteSequence("\000~\000\000\000\000\000\000\000")}, 1161 {-144115188075855873ll, 1162 ByteSequence("\000}\377\377\377\377\377\377\377")}, 1163 {-288230376151711743ll, 1164 ByteSequence("\000|\000\000\000\000\000\000\001")}, 1165 {-288230376151711744ll, 1166 ByteSequence("\000|\000\000\000\000\000\000\000")}, 1167 {-288230376151711745ll, 1168 ByteSequence("\000{\377\377\377\377\377\377\377")}, 1169 {-576460752303423487ll, 1170 ByteSequence("\000x\000\000\000\000\000\000\001")}, 1171 {-576460752303423488ll, 1172 ByteSequence("\000x\000\000\000\000\000\000\000")}, 1173 {-576460752303423489ll, 1174 ByteSequence("\000w\377\377\377\377\377\377\377")}, 1175 {-1152921504606846975ll, 1176 ByteSequence("\000p\000\000\000\000\000\000\001")}, 1177 {-1152921504606846976ll, 1178 ByteSequence("\000p\000\000\000\000\000\000\000")}, 1179 {-1152921504606846977ll, 1180 ByteSequence("\000o\377\377\377\377\377\377\377")}, 1181 {-2305843009213693951ll, 1182 ByteSequence("\000`\000\000\000\000\000\000\001")}, 1183 {-2305843009213693952ll, 1184 ByteSequence("\000`\000\000\000\000\000\000\000")}, 1185 {-2305843009213693953ll, 1186 ByteSequence("\000_\377\377\377\377\377\377\377")}, 1187 {-4611686018427387903ll, 1188 ByteSequence("\000@\000\000\000\000\000\000\001")}, 1189 {-4611686018427387904ll, 1190 ByteSequence("\000@\000\000\000\000\000\000\000")}, 1191 {-4611686018427387905ll, 1192 ByteSequence("\000?\277\377\377\377\377\377\377\377")}, 1193 {-9223372036854775807ll, 1194 ByteSequence("\000?\200\000\000\000\000\000\000\001")}, 1195 {9223372036854775807ll, 1196 ByteSequence("\377\300\177\377\377\377\377\377\377\377")}, 1197 }; 1198 for (const auto& t : data) { 1199 int64 num = t.first; 1200 string result; 1201 OrderedCode::WriteSignedNumIncreasing(&result, num); 1202 EXPECT_EQ(t.second, result) << std::hex << num; 1203 1204 StringPiece in = result; 1205 int64 decoded; 1206 EXPECT_TRUE(OrderedCode::ReadSignedNumIncreasing(&in, &decoded)); 1207 EXPECT_EQ(num, decoded); 1208 EXPECT_EQ("", in); 1209 } 1210 } 1211 1212 void BM_WriteString(int n, int len) { 1213 testing::StopTiming(); 1214 random::PhiloxRandom philox(301, 17); 1215 random::SimplePhilox rnd(&philox); 1216 string x; 1217 for (int i = 0; i < len; i++) { 1218 x += rnd.Uniform(256); 1219 } 1220 string y; 1221 1222 testing::BytesProcessed(n * len); 1223 testing::StartTiming(); 1224 while (n-- > 0) { 1225 y.clear(); 1226 OCWriteToString<string>(&y, x); 1227 } 1228 } 1229 1230 void BM_ReadString(int n, int len) { 1231 testing::StopTiming(); 1232 random::PhiloxRandom philox(301, 17); 1233 random::SimplePhilox rnd(&philox); 1234 string x; 1235 for (int i = 0; i < len; i++) { 1236 x += rnd.Uniform(256); 1237 } 1238 string data; 1239 OCWriteToString<string>(&data, x); 1240 string result; 1241 1242 testing::BytesProcessed(n * len); 1243 testing::StartTiming(); 1244 while (n-- > 0) { 1245 result.clear(); 1246 StringPiece s = data; 1247 OCRead<string>(&s, &result); 1248 } 1249 } 1250 1251 void BM_WriteStringIncreasing(int n, int len) { BM_WriteString(n, len); } 1252 void BM_ReadStringIncreasing(int n, int len) { BM_ReadString(n, len); } 1253 1254 BENCHMARK(BM_WriteStringIncreasing)->Range(0, 1024); 1255 BENCHMARK(BM_ReadStringIncreasing)->Range(0, 1024); 1256 1257 } // namespace 1258 } // namespace strings 1259 } // namespace tensorflow 1260
