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 "gtest/gtest.h"
22 #include "perfetto/base/logging.h"
23 #include "perfetto/base/utils.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 
TEST(ProtoUtilsTest,VarIntEncoding)108 TEST(ProtoUtilsTest, VarIntEncoding) {
109   for (size_t i = 0; i < ArraySize(kVarIntExpectations); ++i) {
110     const VarIntExpectation& exp = kVarIntExpectations[i];
111     uint8_t buf[32];
112     uint8_t* res = WriteVarInt<uint64_t>(exp.int_value, buf);
113     ASSERT_EQ(exp.encoded_size, static_cast<size_t>(res - buf));
114     ASSERT_EQ(0, memcmp(buf, exp.encoded, exp.encoded_size));
115 
116     if (exp.int_value <= std::numeric_limits<uint32_t>::max()) {
117       uint8_t* res_32 =
118           WriteVarInt<uint32_t>(static_cast<uint32_t>(exp.int_value), buf);
119       ASSERT_EQ(exp.encoded_size, static_cast<size_t>(res_32 - buf));
120       ASSERT_EQ(0, memcmp(buf, exp.encoded, exp.encoded_size));
121     }
122   }
123 }
124 
TEST(ProtoUtilsTest,RedundantVarIntEncoding)125 TEST(ProtoUtilsTest, RedundantVarIntEncoding) {
126   uint8_t buf[kMessageLengthFieldSize];
127 
128   WriteRedundantVarInt(0, buf);
129   EXPECT_EQ(0, memcmp("\x80\x80\x80\x00", buf, sizeof(buf)));
130 
131   WriteRedundantVarInt(1, buf);
132   EXPECT_EQ(0, memcmp("\x81\x80\x80\x00", buf, sizeof(buf)));
133 
134   WriteRedundantVarInt(0x80, buf);
135   EXPECT_EQ(0, memcmp("\x80\x81\x80\x00", buf, sizeof(buf)));
136 
137   WriteRedundantVarInt(0x332211, buf);
138   EXPECT_EQ(0, memcmp("\x91\xC4\xCC\x01", buf, sizeof(buf)));
139 
140   // Largest allowed length.
141   WriteRedundantVarInt(0x0FFFFFFF, buf);
142   EXPECT_EQ(0, memcmp("\xFF\xFF\xFF\x7F", buf, sizeof(buf)));
143 }
144 
TEST(ProtoUtilsTest,VarIntDecoding)145 TEST(ProtoUtilsTest, VarIntDecoding) {
146   for (size_t i = 0; i < ArraySize(kVarIntExpectations); ++i) {
147     const VarIntExpectation& exp = kVarIntExpectations[i];
148     uint64_t value = std::numeric_limits<uint64_t>::max();
149     const uint8_t* res = ParseVarInt(
150         reinterpret_cast<const uint8_t*>(exp.encoded),
151         reinterpret_cast<const uint8_t*>(exp.encoded + exp.encoded_size),
152         &value);
153     ASSERT_EQ(reinterpret_cast<const void*>(exp.encoded + exp.encoded_size),
154               reinterpret_cast<const void*>(res));
155     ASSERT_EQ(exp.int_value, value);
156   }
157 }
158 
TEST(ProtoUtilsTest,VarIntDecodingOutOfBounds)159 TEST(ProtoUtilsTest, VarIntDecodingOutOfBounds) {
160   uint8_t buf[] = {0xff, 0xff, 0xff, 0xff};
161   for (size_t i = 0; i < 5; i++) {
162     uint64_t value = static_cast<uint64_t>(-1);
163     const uint8_t* res = ParseVarInt(buf, buf + i, &value);
164     EXPECT_EQ(&buf[0] + i, res);
165     EXPECT_EQ(0u, value);
166   }
167 }
168 
TEST(ProtoUtilsTest,FieldDecoding)169 TEST(ProtoUtilsTest, FieldDecoding) {
170   struct FieldExpectation {
171     const char* encoded;
172     size_t encoded_size;
173     uint32_t id;
174     FieldType type;
175     uint64_t int_value;
176   };
177 
178   const FieldExpectation kFieldExpectations[] = {
179       {"\x08\x00", 2, 1, kFieldTypeVarInt, 0},
180       {"\x08\x42", 2, 1, kFieldTypeVarInt, 0x42},
181       {"\xF8\x07\x42", 3, 127, kFieldTypeVarInt, 0x42},
182       {"\x90\x4D\xFF\xFF\xFF\xFF\x0F", 7, 1234, kFieldTypeVarInt, 0xFFFFFFFF},
183       {"\x7D\x42\x00\x00\x00", 5, 15, kFieldTypeFixed32, 0x42},
184       {"\x95\x4D\x78\x56\x34\x12", 6, 1234, kFieldTypeFixed32, 0x12345678},
185       {"\x79\x42\x00\x00\x00\x00\x00\x00\x00", 9, 15, kFieldTypeFixed64, 0x42},
186       {"\x91\x4D\x08\x07\x06\x05\x04\x03\x02\x01", 10, 1234, kFieldTypeFixed64,
187        0x0102030405060708},
188       {"\x0A\x00", 2, 1, kFieldTypeLengthDelimited, 0},
189       {"\x0A\x04|abc", 6, 1, kFieldTypeLengthDelimited, 4},
190       {"\x92\x4D\x04|abc", 7, 1234, kFieldTypeLengthDelimited, 4},
191       {"\x92\x4D\x83\x01|abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzab"
192        "cdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstu"
193        "vwx",
194        135, 1234, kFieldTypeLengthDelimited, 131},
195   };
196 
197   for (size_t i = 0; i < ArraySize(kFieldExpectations); ++i) {
198     const FieldExpectation& exp = kFieldExpectations[i];
199     FieldType field_type = kFieldTypeVarInt;
200     uint32_t field_id = std::numeric_limits<uint32_t>::max();
201     uint64_t field_intvalue = std::numeric_limits<uint64_t>::max();
202     const uint8_t* res = ParseField(
203         reinterpret_cast<const uint8_t*>(exp.encoded),
204         reinterpret_cast<const uint8_t*>(exp.encoded + exp.encoded_size),
205         &field_id, &field_type, &field_intvalue);
206     ASSERT_EQ(reinterpret_cast<const void*>(exp.encoded + exp.encoded_size),
207               reinterpret_cast<const void*>(res));
208     ASSERT_EQ(exp.id, field_id);
209     ASSERT_EQ(exp.type, field_type);
210     ASSERT_EQ(exp.int_value, field_intvalue);
211   }
212 }
213 
214 }  // namespace
215 }  // namespace proto_utils
216 }  // namespace protozero
217