/Users/deen/code/yugabyte-db/src/yb/util/varint-test.cc

Source
// Copyright (c) YugaByte, Inc.
//
// 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 "yb/util/result.h"
#include "yb/util/test_macros.h"
#include "yb/util/test_util.h"
#include "yb/util/varint.h"

namespace yb {
namespace util {

const std::string kTooSmall = "-9223372036854775809";
const std::string kTooBig = "9223372036854775808";

class VarIntTest : public YBTest {
 protected:
  void SetUp() override {
    YBTest::SetUp();

    // Should be ordered by value, since it is used in comparison tests.
    std::vector<std::string> inputs = {
      "-37618632178637216379216387",
      kTooSmall,
      std::to_string(std::numeric_limits<int64_t>::min()),
      std::to_string(std::numeric_limits<int>::min() - 1LL),
      std::to_string(std::numeric_limits<int>::min()),
      "-129",
      "-128",
      "-127",
      "-23",
      "0",
      "38",
      std::to_string(std::numeric_limits<int>::max()),
      std::to_string(std::numeric_limits<int>::max() + 1LL),
      std::to_string(std::numeric_limits<int64_t>::max()),
      kTooBig,
      "8429024091289482183283928321",
    };

    values_.reserve(inputs.size());

    for (const auto& input : inputs) {
      values_.push_back(ASSERT_RESULT(VarInt::CreateFromString(input)));
    }
  }

  std::string ToDebugString(const std::string& input) {
    size_t num_bytes = input.size();
    string output = "[ ";
    for (size_t i = 0; i < num_bytes; i++) {
      for (size_t j = 0; j < 8; j++) {
        output += '0' + static_cast<char>(input[i] >> (7 - j) & 1);
      }
      output += ' ';
    }
    output += ']';
    return output;
  }

  void CheckInt(int64_t val) {
    VarInt varint(val);
    auto converted = ASSERT_RESULT(varint.ToInt64());
    ASSERT_EQ(val, converted);
    ASSERT_EQ(std::to_string(val), varint.ToString());
  }

  std::vector<VarInt> values_;
};

TEST_F(VarIntTest, TestTypeConversions) {
  int64_t max = std::numeric_limits<int64_t>::max();
  int64_t min = std::numeric_limits<int64_t>::min();
  int64_t zero = 0;
  int64_t negative = -380;

  CheckInt(max);
  CheckInt(min);
  CheckInt(zero);
  CheckInt(negative);

  // One more and less than largest value should overflow.
  auto too_big = ASSERT_RESULT(VarInt::CreateFromString("9223372036854775808"));
  ASSERT_FALSE(too_big.ToInt64().ok());
  auto very_big = ASSERT_RESULT(VarInt::CreateFromString("99999999999999999999999"));
  ASSERT_FALSE(very_big.ToInt64().ok());
  auto too_small = ASSERT_RESULT(VarInt::CreateFromString("-9223372036854775809"));
  ASSERT_FALSE(too_small.ToInt64().ok());
  auto very_small = ASSERT_RESULT(VarInt::CreateFromString("-99999999999999999999999"));
  ASSERT_FALSE(very_small.ToInt64().ok());
}

TEST_F(VarIntTest, TestComparison) {
  std::vector<std::string> encoded;
  encoded.reserve(values_.size());

  for (const auto& value : values_) {
    encoded.push_back(value.EncodeToComparable());
  }

  for (size_t i = 0; i != values_.size(); ++i) {
    for (size_t j = 0; j != values_.size(); ++j) {
      ASSERT_EQ(i < j, values_[i] < values_[j]);
      ASSERT_EQ(i <= j, values_[i] <= values_[j]);
      ASSERT_EQ(i == j, values_[i] == values_[j]);
      ASSERT_EQ(i >= j, values_[i] >= values_[j]);
      ASSERT_EQ(i > j, values_[i] > values_[j]);

      ASSERT_EQ(i < j, encoded[i] < encoded[j]);
      ASSERT_EQ(i <= j, encoded[i] <= encoded[j]);
      ASSERT_EQ(i == j, encoded[i] == encoded[j]);
      ASSERT_EQ(i >= j, encoded[i] >= encoded[j]);
      ASSERT_EQ(i > j, encoded[i] > encoded[j]);
    }
  }
}

TEST_F(VarIntTest, TestArithmetic) {
  ASSERT_EQ(VarInt(74), VarInt(28) + VarInt(46));
  ASSERT_EQ(VarInt(-113), VarInt(28) - VarInt(141));
  ASSERT_EQ(VarInt(0), VarInt(23) + VarInt(3) + VarInt(-26));
  ASSERT_EQ(VarInt(1), VarInt(23) + VarInt(3) + VarInt(-25));
  ASSERT_EQ(VarInt(-1), VarInt(23) + VarInt(3) + VarInt(-27));
}

TEST_F(VarIntTest, ComparableEncodingWithReserve) {
  constexpr int kNumReservedBits = 2;
  for (int i = 0; i != 0xffff; ++i) {
    SCOPED_TRACE(Format("i: $0", i));
    VarInt v(i);
    auto encoded = v.EncodeToComparable(kNumReservedBits);
    VarInt decoded;
    size_t decoded_size = 0;
    ASSERT_OK(decoded.DecodeFromComparable(encoded, &decoded_size, kNumReservedBits));
    ASSERT_EQ(v, decoded);
    ASSERT_EQ(encoded.size(), decoded_size);
  }
}

TEST_F(VarIntTest, TestComparableEncoding) {
  std::vector<std::string> expected = {
      "[ 00000000 00000111 11100000 11100001 11110001 11011101 00000001 00110000 "
        "11011100 11111011 11101101 01011101 11111100 ]", // -37618632178637216379216387
      "[ 00000000 00111111 01111111 11111111 11111111 11111111 11111111 11111111 11111111 "
        "11111110 ]", // kTooSmall,
      "[ 00000000 00111111 01111111 11111111 11111111 11111111 11111111 11111111 11111111 "
        "11111111 ]", // std::to_string(std::numeric_limits<int64_t>::min()),
      "[ 00000111 01111111 11111111 11111111 11111110 ]",
          // std::to_string(std::numeric_limits<int>::min() - 1LL),
      "[ 00000111 01111111 11111111 11111111 11111111 ]",
          // std::to_string(std::numeric_limits<int>::min()),
      "[ 00111111 01111110 ]", // -129
      "[ 00111111 01111111 ]", // -128
      "[ 00111111 10000000 ]", // -127
      "[ 01101000 ]", // -23
      "[ 10000000 ]", // 0
      "[ 10100110 ]", // 38
      "[ 11111000 01111111 11111111 11111111 11111111 ]",
          // std::to_string(std::numeric_limits<int>::max()),
      "[ 11111000 10000000 00000000 00000000 00000000 ]",
          // std::to_string(std::numeric_limits<int>::max() + 1LL),
      "[ 11111111 11000000 01111111 11111111 11111111 11111111 11111111 11111111 11111111 "
        "11111111 ]", // std::to_string(std::numeric_limits<int64_t>::max()),
      "[ 11111111 11000000 10000000 00000000 00000000 00000000 00000000 00000000 00000000 "
        "00000000 ]", // kTooBig,
      "[ 11111111 11111100 00011011 00111100 01010011 01000111 10010101 11011111 "
        "00011011 00001010 01111011 11111101 01101101 00000001 ]" // 8429024091289482183283928321
  };
  ASSERT_EQ(expected.size(), values_.size());
  for (size_t i = 0; i != values_.size(); ++i) {
    SCOPED_TRACE(Format("Index: $0, value: $1", i, values_[i]));
    auto encoded = values_[i].EncodeToComparable();
    EXPECT_EQ(expected[i], ToDebugString(encoded));
    VarInt decoded;
    size_t size;
    ASSERT_OK(decoded.DecodeFromComparable(encoded, &size));
    EXPECT_EQ(encoded.size(), size);
    EXPECT_EQ(values_[i], decoded);
  }
}

TEST_F(VarIntTest, TestTwosComplementEncoding) {
  std::vector<std::string> expected = {
      "[ 11100000 11100001 11110001 11011101 00000001 00110000 11011100 11111011 "
        "11101101 01011101 11111101 ]", // -37618632178637216379216387
      "[ 11111111 01111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 ]",
          // kTooSmall
      "[ 10000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 ]",
          // std::to_string(std::numeric_limits<int64_t>::min())
      "[ 11111111 01111111 11111111 11111111 11111111 ]",
          // std::to_string(std::numeric_limits<int>::min() - 1LL)
      "[ 10000000 00000000 00000000 00000000 ]", // std::to_string(std::numeric_limits<int>::min())
      "[ 11111111 01111111 ]", // -129
      "[ 10000000 ]", // -128
      "[ 10000001 ]", // -127
      "[ 11101001 ]", // -23
      "[ 00000000 ]", // 0
      "[ 00100110 ]", // 38
      "[ 01111111 11111111 11111111 11111111 ]", // std::to_string(std::numeric_limits<int>::max())
      "[ 00000000 10000000 00000000 00000000 00000000 ]",
          // std::to_string(std::numeric_limits<int>::max() + 1LL)
      "[ 01111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 ]",
          // std::to_string(std::numeric_limits<int64_t>::max())
      "[ 00000000 10000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 ]",
          // kTooBig
      "[ 00011011 00111100 01010011 01000111 10010101 11011111 00011011 00001010 "
        "01111011 11111101 01101101 00000001 ]" // 8429024091289482183283928321
  };
  ASSERT_EQ(expected.size(), values_.size());
  for (size_t i = 0; i != values_.size(); ++i) {
    SCOPED_TRACE(Format("Index: $0, value: $1", i, values_[i]));
    auto encoded = values_[i].EncodeToTwosComplement();
    EXPECT_EQ(expected[i], ToDebugString(encoded));
    VarInt decoded;
    ASSERT_OK(decoded.DecodeFromTwosComplement(encoded));
    EXPECT_EQ(values_[i], decoded);
  }
}

} // namespace util
} // namespace yb

YugabyteDB (2.13.0.0-b42, bfc6a6643e7399ac8a0e81d06a3ee6d6571b33ab)

Coverage Report

Created: 2022-03-09 17:30

Line	Count	Source
1		// Copyright (c) YugaByte, Inc.
2		//
3		// Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
4		// in compliance with the License. You may obtain a copy of the License at
5		//
6		// http://www.apache.org/licenses/LICENSE-2.0
7		//
8		// Unless required by applicable law or agreed to in writing, software distributed under the License
9		// is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
10		// or implied. See the License for the specific language governing permissions and limitations
11		// under the License.
12		//
13
14		#include "yb/util/result.h"
15		#include "yb/util/test_macros.h"
16		#include "yb/util/test_util.h"
17		#include "yb/util/varint.h"
18
19		namespace yb {
20		namespace util {
21
22		const std::string kTooSmall = "-9223372036854775809";
23		const std::string kTooBig = "9223372036854775808";
24
25		class VarIntTest : public YBTest {
26		protected:
27	6	void SetUp() override {
28	6	YBTest::SetUp();
29
30		// Should be ordered by value, since it is used in comparison tests.
31	6	std::vector<std::string> inputs = {
32	6	"-37618632178637216379216387",
33	6	kTooSmall,
34	6	std::to_string(std::numeric_limits<int64_t>::min()),
35	6	std::to_string(std::numeric_limits<int>::min() - 1LL),
36	6	std::to_string(std::numeric_limits<int>::min()),
37	6	"-129",
38	6	"-128",
39	6	"-127",
40	6	"-23",
41	6	"0",
42	6	"38",
43	6	std::to_string(std::numeric_limits<int>::max()),
44	6	std::to_string(std::numeric_limits<int>::max() + 1LL),
45	6	std::to_string(std::numeric_limits<int64_t>::max()),
46	6	kTooBig,
47	6	"8429024091289482183283928321",
48	6	};
49
50	6	values_.reserve(inputs.size());
51
52	96	for (const auto& input : inputs) {
53	96	values_.push_back(ASSERT_RESULT(VarInt::CreateFromString(input)));
54	96	}
55	6	}
56
57	32	std::string ToDebugString(const std::string& input) {
58	32	size_t num_bytes = input.size();
59	32	string output = "[ ";
60	210	for (size_t i = 0; i < num_bytes; i++) {
61	1.60k	for (size_t j = 0; j < 8; j++) {
62	1.42k	output += '0' + static_cast<char>(input[i] >> (7 - j) & 1);
63	1.42k	}
64	178	output += ' ';
65	178	}
66	32	output += ']';
67	32	return output;
68	32	}
69
70	4	void CheckInt(int64_t val) {
71	4	VarInt varint(val);
72	4	auto converted = ASSERT_RESULT(varint.ToInt64());
73	4	ASSERT_EQ(val, converted);
74	4	ASSERT_EQ(std::to_string(val), varint.ToString());
75	4	}
76
77		std::vector<VarInt> values_;
78		};
79
80	1	TEST_F(VarIntTest, TestTypeConversions) {
81	1	int64_t max = std::numeric_limits<int64_t>::max();
82	1	int64_t min = std::numeric_limits<int64_t>::min();
83	1	int64_t zero = 0;
84	1	int64_t negative = -380;
85
86	1	CheckInt(max);
87	1	CheckInt(min);
88	1	CheckInt(zero);
89	1	CheckInt(negative);
90
91		// One more and less than largest value should overflow.
92	1	auto too_big = ASSERT_RESULT(VarInt::CreateFromString("9223372036854775808"));
93	1	ASSERT_FALSE(too_big.ToInt64().ok());
94	1	auto very_big = ASSERT_RESULT(VarInt::CreateFromString("99999999999999999999999"));
95	1	ASSERT_FALSE(very_big.ToInt64().ok());
96	1	auto too_small = ASSERT_RESULT(VarInt::CreateFromString("-9223372036854775809"));
97	1	ASSERT_FALSE(too_small.ToInt64().ok());
98	1	auto very_small = ASSERT_RESULT(VarInt::CreateFromString("-99999999999999999999999"));
99	1	ASSERT_FALSE(very_small.ToInt64().ok());
100	1	}
101
102	1	TEST_F(VarIntTest, TestComparison) {
103	1	std::vector<std::string> encoded;
104	1	encoded.reserve(values_.size());
105
106	16	for (const auto& value : values_) {
107	16	encoded.push_back(value.EncodeToComparable());
108	16	}
109
110	17	for (size_t i = 0; i != values_.size(); ++i) {
111	272	for (size_t j = 0; j != values_.size(); ++j) {
112	256	ASSERT_EQ(i < j, values_[i] < values_[j]);
113	256	ASSERT_EQ(i <= j, values_[i] <= values_[j]);
114	256	ASSERT_EQ(i == j, values_[i] == values_[j]);
115	256	ASSERT_EQ(i >= j, values_[i] >= values_[j]);
116	256	ASSERT_EQ(i > j, values_[i] > values_[j]);
117
118	256	ASSERT_EQ(i < j, encoded[i] < encoded[j]);
119	256	ASSERT_EQ(i <= j, encoded[i] <= encoded[j]);
120	256	ASSERT_EQ(i == j, encoded[i] == encoded[j]);
121	256	ASSERT_EQ(i >= j, encoded[i] >= encoded[j]);
122	256	ASSERT_EQ(i > j, encoded[i] > encoded[j]);
123	256	}
124	16	}
125	1	}
126
127	1	TEST_F(VarIntTest, TestArithmetic) {
128	1	ASSERT_EQ(VarInt(74), VarInt(28) + VarInt(46));
129	1	ASSERT_EQ(VarInt(-113), VarInt(28) - VarInt(141));
130	1	ASSERT_EQ(VarInt(0), VarInt(23) + VarInt(3) + VarInt(-26));
131	1	ASSERT_EQ(VarInt(1), VarInt(23) + VarInt(3) + VarInt(-25));
132	1	ASSERT_EQ(VarInt(-1), VarInt(23) + VarInt(3) + VarInt(-27));
133	1	}
134
135	1	TEST_F(VarIntTest, ComparableEncodingWithReserve) {
136	1	constexpr int kNumReservedBits = 2;
137	65.5k	for (int i = 0; i != 0xffff; ++i) {
138	65.5k	SCOPED_TRACE(Format("i: $0", i));
139	65.5k	VarInt v(i);
140	65.5k	auto encoded = v.EncodeToComparable(kNumReservedBits);
141	65.5k	VarInt decoded;
142	65.5k	size_t decoded_size = 0;
143	65.5k	ASSERT_OK(decoded.DecodeFromComparable(encoded, &decoded_size, kNumReservedBits));
144	65.5k	ASSERT_EQ(v, decoded);
145	65.5k	ASSERT_EQ(encoded.size(), decoded_size);
146	65.5k	}
147	1	}
148
149	1	TEST_F(VarIntTest, TestComparableEncoding) {
150	1	std::vector<std::string> expected = {
151	1	"[ 00000000 00000111 11100000 11100001 11110001 11011101 00000001 00110000 "
152	1	"11011100 11111011 11101101 01011101 11111100 ]", // -37618632178637216379216387
153	1	"[ 00000000 00111111 01111111 11111111 11111111 11111111 11111111 11111111 11111111 "
154	1	"11111110 ]", // kTooSmall,
155	1	"[ 00000000 00111111 01111111 11111111 11111111 11111111 11111111 11111111 11111111 "
156	1	"11111111 ]", // std::to_string(std::numeric_limits<int64_t>::min()),
157	1	"[ 00000111 01111111 11111111 11111111 11111110 ]",
158		// std::to_string(std::numeric_limits<int>::min() - 1LL),
159	1	"[ 00000111 01111111 11111111 11111111 11111111 ]",
160		// std::to_string(std::numeric_limits<int>::min()),
161	1	"[ 00111111 01111110 ]", // -129
162	1	"[ 00111111 01111111 ]", // -128
163	1	"[ 00111111 10000000 ]", // -127
164	1	"[ 01101000 ]", // -23
165	1	"[ 10000000 ]", // 0
166	1	"[ 10100110 ]", // 38
167	1	"[ 11111000 01111111 11111111 11111111 11111111 ]",
168		// std::to_string(std::numeric_limits<int>::max()),
169	1	"[ 11111000 10000000 00000000 00000000 00000000 ]",
170		// std::to_string(std::numeric_limits<int>::max() + 1LL),
171	1	"[ 11111111 11000000 01111111 11111111 11111111 11111111 11111111 11111111 11111111 "
172	1	"11111111 ]", // std::to_string(std::numeric_limits<int64_t>::max()),
173	1	"[ 11111111 11000000 10000000 00000000 00000000 00000000 00000000 00000000 00000000 "
174	1	"00000000 ]", // kTooBig,
175	1	"[ 11111111 11111100 00011011 00111100 01010011 01000111 10010101 11011111 "
176	1	"00011011 00001010 01111011 11111101 01101101 00000001 ]" // 8429024091289482183283928321
177	1	};
178	1	ASSERT_EQ(expected.size(), values_.size());
179	17	for (size_t i = 0; i != values_.size(); ++i) {
180	16	SCOPED_TRACE(Format("Index: $0, value: $1", i, values_[i]));
181	16	auto encoded = values_[i].EncodeToComparable();
182	16	EXPECT_EQ(expected[i], ToDebugString(encoded));
183	16	VarInt decoded;
184	16	size_t size;
185	16	ASSERT_OK(decoded.DecodeFromComparable(encoded, &size));
186	16	EXPECT_EQ(encoded.size(), size);
187	16	EXPECT_EQ(values_[i], decoded);
188	16	}
189	1	}
190
191	1	TEST_F(VarIntTest, TestTwosComplementEncoding) {
192	1	std::vector<std::string> expected = {
193	1	"[ 11100000 11100001 11110001 11011101 00000001 00110000 11011100 11111011 "
194	1	"11101101 01011101 11111101 ]", // -37618632178637216379216387
195	1	"[ 11111111 01111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 ]",
196		// kTooSmall
197	1	"[ 10000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 ]",
198		// std::to_string(std::numeric_limits<int64_t>::min())
199	1	"[ 11111111 01111111 11111111 11111111 11111111 ]",
200		// std::to_string(std::numeric_limits<int>::min() - 1LL)
201	1	"[ 10000000 00000000 00000000 00000000 ]", // std::to_string(std::numeric_limits<int>::min())
202	1	"[ 11111111 01111111 ]", // -129
203	1	"[ 10000000 ]", // -128
204	1	"[ 10000001 ]", // -127
205	1	"[ 11101001 ]", // -23
206	1	"[ 00000000 ]", // 0
207	1	"[ 00100110 ]", // 38
208	1	"[ 01111111 11111111 11111111 11111111 ]", // std::to_string(std::numeric_limits<int>::max())
209	1	"[ 00000000 10000000 00000000 00000000 00000000 ]",
210		// std::to_string(std::numeric_limits<int>::max() + 1LL)
211	1	"[ 01111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 ]",
212		// std::to_string(std::numeric_limits<int64_t>::max())
213	1	"[ 00000000 10000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 ]",
214		// kTooBig
215	1	"[ 00011011 00111100 01010011 01000111 10010101 11011111 00011011 00001010 "
216	1	"01111011 11111101 01101101 00000001 ]" // 8429024091289482183283928321
217	1	};
218	1	ASSERT_EQ(expected.size(), values_.size());
219	17	for (size_t i = 0; i != values_.size(); ++i) {
220	16	SCOPED_TRACE(Format("Index: $0, value: $1", i, values_[i]));
221	16	auto encoded = values_[i].EncodeToTwosComplement();
222	16	EXPECT_EQ(expected[i], ToDebugString(encoded));
223	16	VarInt decoded;
224	16	ASSERT_OK(decoded.DecodeFromTwosComplement(encoded));
225	16	EXPECT_EQ(values_[i], decoded);
226	16	}
227	1	}
228
229		} // namespace util
230		} // namespace yb