1 /*
2 * Copyright (C) 2017 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #include "perfetto/protozero/proto_utils.h"
18
19 #include <limits>
20
21 #include "perfetto/base/logging.h"
22 #include "perfetto/ext/base/utils.h"
23 #include "test/gtest_and_gmock.h"
24
25 namespace protozero {
26 namespace proto_utils {
27 namespace {
28
29 using ::perfetto::base::ArraySize;
30
31 struct VarIntExpectation {
32 const char* encoded;
33 size_t encoded_size;
34 uint64_t int_value;
35 };
36
37 const VarIntExpectation kVarIntExpectations[] = {
38 {"\x00", 1, 0},
39 {"\x01", 1, 0x1},
40 {"\x7f", 1, 0x7F},
41 {"\xFF\x01", 2, 0xFF},
42 {"\xFF\x7F", 2, 0x3FFF},
43 {"\x80\x80\x01", 3, 0x4000},
44 {"\xFF\xFF\x7F", 3, 0x1FFFFF},
45 {"\x80\x80\x80\x01", 4, 0x200000},
46 {"\xFF\xFF\xFF\x7F", 4, 0xFFFFFFF},
47 {"\x80\x80\x80\x80\x01", 5, 0x10000000},
48 {"\xFF\xFF\xFF\xFF\x0F", 5, 0xFFFFFFFF},
49 {"\x80\x80\x80\x80\x10", 5, 0x100000000},
50 {"\xFF\xFF\xFF\xFF\x7F", 5, 0x7FFFFFFFF},
51 {"\x80\x80\x80\x80\x80\x01", 6, 0x800000000},
52 {"\xFF\xFF\xFF\xFF\xFF\x7F", 6, 0x3FFFFFFFFFF},
53 {"\x80\x80\x80\x80\x80\x80\x01", 7, 0x40000000000},
54 {"\xFF\xFF\xFF\xFF\xFF\xFF\x7F", 7, 0x1FFFFFFFFFFFF},
55 {"\x80\x80\x80\x80\x80\x80\x80\x01", 8, 0x2000000000000},
56 {"\xFF\xFF\xFF\xFF\xFF\xFF\xFF\x7F", 8, 0xFFFFFFFFFFFFFF},
57 {"\x80\x80\x80\x80\x80\x80\x80\x80\x01", 9, 0x100000000000000},
58 {"\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\x7F", 9, 0x7FFFFFFFFFFFFFFF},
59 {"\x80\x80\x80\x80\x80\x80\x80\x80\x80\x01", 10, 0x8000000000000000},
60 {"\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\x01", 10, 0xFFFFFFFFFFFFFFFF},
61 };
62
TEST(ProtoUtilsTest,FieldPreambleEncoding)63 TEST(ProtoUtilsTest, FieldPreambleEncoding) {
64 // According to C++ standard, right shift of negative value has
65 // implementation-defined resulting value.
66 if ((static_cast<int32_t>(0x80000000u) >> 31) != -1)
67 FAIL() << "Platform has unsupported negative number format or arithmetic";
68
69 EXPECT_EQ(0x08u, MakeTagVarInt(1));
70 EXPECT_EQ(0x09u, MakeTagFixed<uint64_t>(1));
71 EXPECT_EQ(0x0Au, MakeTagLengthDelimited(1));
72 EXPECT_EQ(0x0Du, MakeTagFixed<uint32_t>(1));
73
74 EXPECT_EQ(0x03F8u, MakeTagVarInt(0x7F));
75 EXPECT_EQ(0x03F9u, MakeTagFixed<int64_t>(0x7F));
76 EXPECT_EQ(0x03FAu, MakeTagLengthDelimited(0x7F));
77 EXPECT_EQ(0x03FDu, MakeTagFixed<int32_t>(0x7F));
78
79 EXPECT_EQ(0x0400u, MakeTagVarInt(0x80));
80 EXPECT_EQ(0x0401u, MakeTagFixed<double>(0x80));
81 EXPECT_EQ(0x0402u, MakeTagLengthDelimited(0x80));
82 EXPECT_EQ(0x0405u, MakeTagFixed<float>(0x80));
83
84 EXPECT_EQ(0x01FFF8u, MakeTagVarInt(0x3fff));
85 EXPECT_EQ(0x01FFF9u, MakeTagFixed<int64_t>(0x3fff));
86 EXPECT_EQ(0x01FFFAu, MakeTagLengthDelimited(0x3fff));
87 EXPECT_EQ(0x01FFFDu, MakeTagFixed<int32_t>(0x3fff));
88
89 EXPECT_EQ(0x020000u, MakeTagVarInt(0x4000));
90 EXPECT_EQ(0x020001u, MakeTagFixed<int64_t>(0x4000));
91 EXPECT_EQ(0x020002u, MakeTagLengthDelimited(0x4000));
92 EXPECT_EQ(0x020005u, MakeTagFixed<int32_t>(0x4000));
93 }
94
TEST(ProtoUtilsTest,ZigZagEncoding)95 TEST(ProtoUtilsTest, ZigZagEncoding) {
96 EXPECT_EQ(0u, ZigZagEncode(0));
97 EXPECT_EQ(1u, ZigZagEncode(-1));
98 EXPECT_EQ(2u, ZigZagEncode(1));
99 EXPECT_EQ(3u, ZigZagEncode(-2));
100 EXPECT_EQ(4294967293u, ZigZagEncode(-2147483647));
101 EXPECT_EQ(4294967294u, ZigZagEncode(2147483647));
102 EXPECT_EQ(std::numeric_limits<uint32_t>::max(),
103 ZigZagEncode(std::numeric_limits<int32_t>::min()));
104 EXPECT_EQ(std::numeric_limits<uint64_t>::max(),
105 ZigZagEncode(std::numeric_limits<int64_t>::min()));
106
107 EXPECT_EQ(0, ZigZagDecode(ZigZagEncode(0)));
108 EXPECT_EQ(-1, ZigZagDecode(ZigZagEncode(-1)));
109 EXPECT_EQ(1, ZigZagDecode(ZigZagEncode(1)));
110 EXPECT_EQ(-127, ZigZagDecode(ZigZagEncode(-127)));
111 EXPECT_EQ(0x7fffffff, ZigZagDecode(ZigZagEncode(0x7fffffff)));
112 EXPECT_EQ(9000000000, ZigZagDecode(ZigZagEncode(9000000000)));
113 EXPECT_EQ(-9000000000, ZigZagDecode(ZigZagEncode(-9000000000)));
114 }
115
TEST(ProtoUtilsTest,VarIntEncoding)116 TEST(ProtoUtilsTest, VarIntEncoding) {
117 for (size_t i = 0; i < ArraySize(kVarIntExpectations); ++i) {
118 const VarIntExpectation& exp = kVarIntExpectations[i];
119 uint8_t buf[32];
120 uint8_t* res = WriteVarInt<uint64_t>(exp.int_value, buf);
121 ASSERT_EQ(exp.encoded_size, static_cast<size_t>(res - buf));
122 ASSERT_EQ(0, memcmp(buf, exp.encoded, exp.encoded_size));
123
124 if (exp.int_value <= std::numeric_limits<uint32_t>::max()) {
125 uint8_t* res_32 =
126 WriteVarInt<uint32_t>(static_cast<uint32_t>(exp.int_value), buf);
127 ASSERT_EQ(exp.encoded_size, static_cast<size_t>(res_32 - buf));
128 ASSERT_EQ(0, memcmp(buf, exp.encoded, exp.encoded_size));
129 }
130 }
131 }
132
TEST(ProtoUtilsTest,VarIntEncodingNegative)133 TEST(ProtoUtilsTest, VarIntEncodingNegative) {
134 uint8_t buf[32];
135 size_t expected_size = 10;
136 uint8_t expected[] = "\x9c\xff\xff\xff\xff\xff\xff\xff\xff\x01";
137
138 {
139 uint8_t* res = WriteVarInt<int8_t>(-100, buf);
140 ASSERT_EQ(expected_size, static_cast<size_t>(res - buf));
141 ASSERT_EQ(0, memcmp(buf, expected, expected_size));
142 }
143
144 {
145 uint8_t* res = WriteVarInt<int16_t>(-100, buf);
146 ASSERT_EQ(expected_size, static_cast<size_t>(res - buf));
147 ASSERT_EQ(0, memcmp(buf, expected, expected_size));
148 }
149
150 {
151 uint8_t* res = WriteVarInt<int32_t>(-100, buf);
152 ASSERT_EQ(expected_size, static_cast<size_t>(res - buf));
153 ASSERT_EQ(0, memcmp(buf, expected, expected_size));
154 }
155
156 {
157 uint8_t* res = WriteVarInt<int64_t>(-100, buf);
158 ASSERT_EQ(expected_size, static_cast<size_t>(res - buf));
159 ASSERT_EQ(0, memcmp(buf, expected, expected_size));
160 }
161 }
162
TEST(ProtoUtilsTest,RedundantVarIntEncoding)163 TEST(ProtoUtilsTest, RedundantVarIntEncoding) {
164 uint8_t buf[kMessageLengthFieldSize];
165
166 WriteRedundantVarInt(0, buf);
167 EXPECT_EQ(0, memcmp("\x80\x80\x80\x00", buf, sizeof(buf)));
168
169 WriteRedundantVarInt(1, buf);
170 EXPECT_EQ(0, memcmp("\x81\x80\x80\x00", buf, sizeof(buf)));
171
172 WriteRedundantVarInt(0x80, buf);
173 EXPECT_EQ(0, memcmp("\x80\x81\x80\x00", buf, sizeof(buf)));
174
175 WriteRedundantVarInt(0x332211, buf);
176 EXPECT_EQ(0, memcmp("\x91\xC4\xCC\x01", buf, sizeof(buf)));
177
178 // Largest allowed length.
179 WriteRedundantVarInt(0x0FFFFFFF, buf);
180 EXPECT_EQ(0, memcmp("\xFF\xFF\xFF\x7F", buf, sizeof(buf)));
181 }
182
TEST(ProtoUtilsTest,VarIntDecoding)183 TEST(ProtoUtilsTest, VarIntDecoding) {
184 for (size_t i = 0; i < ArraySize(kVarIntExpectations); ++i) {
185 const VarIntExpectation& exp = kVarIntExpectations[i];
186 uint64_t value = std::numeric_limits<uint64_t>::max();
187 const uint8_t* res = ParseVarInt(
188 reinterpret_cast<const uint8_t*>(exp.encoded),
189 reinterpret_cast<const uint8_t*>(exp.encoded + exp.encoded_size),
190 &value);
191 ASSERT_EQ(reinterpret_cast<const void*>(exp.encoded + exp.encoded_size),
192 reinterpret_cast<const void*>(res));
193 ASSERT_EQ(exp.int_value, value);
194 }
195 }
196
197 // ParseVarInt() must fail gracefully if we hit the |end| without seeing the
198 // MSB == 0 (i.e. end-of-sequence).
TEST(ProtoUtilsTest,VarIntDecodingOutOfBounds)199 TEST(ProtoUtilsTest, VarIntDecodingOutOfBounds) {
200 uint8_t buf[] = {0xff, 0xff, 0xff, 0xff};
201 for (size_t i = 0; i < 5; i++) {
202 uint64_t value = static_cast<uint64_t>(-1);
203 const uint8_t* res = ParseVarInt(buf, buf + i, &value);
204 EXPECT_EQ(&buf[0], res);
205 EXPECT_EQ(0u, value);
206 }
207 }
208
209 // Even if we see a valid end-of-sequence, ParseVarInt() must fail if the number
210 // is larger than 10 bytes. That would cause subtl bugs when trying to shift
211 // left by more than 64 bits.
TEST(ProtoUtilsTest,RejectVarIntTooBig)212 TEST(ProtoUtilsTest, RejectVarIntTooBig) {
213 // This is the biggest valid varint we support (2**64 - 1).
214 uint8_t good[] = {0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x01};
215
216 // Parsing this value must succeed.
217 uint64_t value = static_cast<uint64_t>(-1);
218 const uint8_t* res = ParseVarInt(&good[0], &good[sizeof(good)], &value);
219 EXPECT_EQ(&good[sizeof(good)], res);
220 EXPECT_EQ(value, static_cast<uint64_t>(-1));
221
222 uint8_t bad[] = {0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
223 0xff, 0xff, 0xff, 0xff, 0x01};
224 value = static_cast<uint64_t>(-1);
225 res = ParseVarInt(&bad[0], &bad[sizeof(bad)], &value);
226 EXPECT_EQ(&bad[0], res);
227 EXPECT_EQ(0u, value);
228 }
229
230 } // namespace
231 } // namespace proto_utils
232 } // namespace protozero
233