1 | /* |
2 | * Copyright 2012-present Facebook, Inc. |
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 <folly/GroupVarint.h> |
18 | |
19 | #include <algorithm> |
20 | #include <cstdarg> |
21 | |
22 | // On platforms where it's not supported, GroupVarint will be compiled out. |
23 | #if HAVE_GROUP_VARINT |
24 | |
25 | #include <folly/portability/GTest.h> |
26 | |
27 | using namespace folly; |
28 | |
29 | namespace { |
30 | |
31 | class StringAppender { |
32 | public: |
33 | /* implicit */ StringAppender(std::string& s) : s_(s) {} |
34 | void operator()(StringPiece sp) { |
35 | s_.append(sp.data(), sp.size()); |
36 | } |
37 | |
38 | private: |
39 | std::string& s_; |
40 | }; |
41 | |
42 | typedef GroupVarintEncoder<uint32_t, StringAppender> GroupVarint32Encoder; |
43 | typedef GroupVarintEncoder<uint64_t, StringAppender> GroupVarint64Encoder; |
44 | |
45 | // Expected bytes follow, terminate with -1 |
46 | void testGroupVarint32(uint32_t a, uint32_t b, uint32_t c, uint32_t d, ...) { |
47 | va_list ap; |
48 | va_start(ap, d); |
49 | std::vector<char> expectedBytes; |
50 | int byte; |
51 | while ((byte = va_arg(ap, int)) != -1) { |
52 | expectedBytes.push_back(byte); |
53 | } |
54 | va_end(ap); |
55 | |
56 | size_t size = GroupVarint32::size(a, b, c, d); |
57 | EXPECT_EQ(expectedBytes.size(), size); |
58 | |
59 | std::vector<char> foundBytes; |
60 | |
61 | // ssse3 decoding requires that the source buffer have length >= 17, |
62 | // so that it can read 128 bits from &start[1] via _mm_loadu_si128. |
63 | foundBytes.resize(std::max<size_t>(size + 4, 17UL)); |
64 | char* start = &(foundBytes.front()); |
65 | char* p = GroupVarint32::encode(start, a, b, c, d); |
66 | EXPECT_EQ((void*)(start + size), (void*)p); |
67 | |
68 | for (size_t i = 0; i < size; i++) { |
69 | EXPECT_EQ(0xff & expectedBytes[i], 0xff & foundBytes[i]); |
70 | } |
71 | |
72 | // Test decoding |
73 | EXPECT_EQ(size, GroupVarint32::encodedSize(start)); |
74 | |
75 | uint32_t fa, fb, fc, fd; |
76 | const char* r = GroupVarint32::decode(start, &fa, &fb, &fc, &fd); |
77 | EXPECT_EQ((void*)(start + size), (void*)r); |
78 | |
79 | EXPECT_EQ(a, fa); |
80 | EXPECT_EQ(b, fb); |
81 | EXPECT_EQ(c, fc); |
82 | EXPECT_EQ(d, fd); |
83 | } |
84 | |
85 | void testGroupVarint64( |
86 | uint64_t a, |
87 | uint64_t b, |
88 | uint64_t c, |
89 | uint64_t d, |
90 | uint64_t e, |
91 | ...) { |
92 | va_list ap; |
93 | va_start(ap, e); |
94 | std::vector<char> expectedBytes; |
95 | int byte; |
96 | while ((byte = va_arg(ap, int)) != -1) { |
97 | expectedBytes.push_back(byte); |
98 | } |
99 | va_end(ap); |
100 | |
101 | size_t size = GroupVarint64::size(a, b, c, d, e); |
102 | EXPECT_EQ(expectedBytes.size(), size); |
103 | |
104 | std::vector<char> foundBytes; |
105 | foundBytes.resize(size + 8); |
106 | char* start = &(foundBytes.front()); |
107 | char* p = GroupVarint64::encode(start, a, b, c, d, e); |
108 | EXPECT_EQ((void*)(start + size), (void*)p); |
109 | |
110 | for (size_t i = 0; i < size; i++) { |
111 | EXPECT_EQ(0xff & expectedBytes[i], 0xff & foundBytes[i]); |
112 | } |
113 | |
114 | // Test decoding |
115 | EXPECT_EQ(size, GroupVarint64::encodedSize(start)); |
116 | |
117 | uint64_t fa, fb, fc, fd, fe; |
118 | const char* r = GroupVarint64::decode(start, &fa, &fb, &fc, &fd, &fe); |
119 | EXPECT_EQ((void*)(start + size), (void*)r); |
120 | |
121 | EXPECT_EQ(a, fa); |
122 | EXPECT_EQ(b, fb); |
123 | EXPECT_EQ(c, fc); |
124 | EXPECT_EQ(d, fd); |
125 | EXPECT_EQ(e, fe); |
126 | } |
127 | |
128 | } // namespace |
129 | |
130 | TEST(GroupVarint, GroupVarint32) { |
131 | EXPECT_EQ(0, GroupVarint32::maxSize(0)); |
132 | EXPECT_EQ(5, GroupVarint32::maxSize(1)); |
133 | EXPECT_EQ(9, GroupVarint32::maxSize(2)); |
134 | EXPECT_EQ(13, GroupVarint32::maxSize(3)); |
135 | EXPECT_EQ(17, GroupVarint32::maxSize(4)); |
136 | EXPECT_EQ(22, GroupVarint32::maxSize(5)); |
137 | EXPECT_EQ(26, GroupVarint32::maxSize(6)); |
138 | // clang-format off |
139 | testGroupVarint32( |
140 | 0, 0, 0, 0, |
141 | 0, 0, 0, 0, 0, -1); |
142 | testGroupVarint32( |
143 | 1, 2, 3, 4, |
144 | 0, 1, 2, 3, 4, -1); |
145 | testGroupVarint32( |
146 | 1 << 8, (2 << 16) + 3, (4 << 24) + (5 << 8) + 6, 7, |
147 | 0x39, 0, 1, 3, 0, 2, 6, 5, 0, 4, 7, -1); |
148 | // clang-format on |
149 | } |
150 | |
151 | TEST(GroupVarint, GroupVarint64) { |
152 | EXPECT_EQ(0, GroupVarint64::maxSize(0)); |
153 | EXPECT_EQ(10, GroupVarint64::maxSize(1)); |
154 | EXPECT_EQ(18, GroupVarint64::maxSize(2)); |
155 | EXPECT_EQ(26, GroupVarint64::maxSize(3)); |
156 | EXPECT_EQ(34, GroupVarint64::maxSize(4)); |
157 | EXPECT_EQ(42, GroupVarint64::maxSize(5)); |
158 | EXPECT_EQ(52, GroupVarint64::maxSize(6)); |
159 | // clang-format off |
160 | testGroupVarint64( |
161 | 0, 0, 0, 0, 0, |
162 | 0, 0, 0, 0, 0, 0, 0, -1); |
163 | testGroupVarint64( |
164 | 1, 2, 3, 4, 5, |
165 | 0, 0, 1, 2, 3, 4, 5, -1); |
166 | testGroupVarint64( |
167 | 1 << 8, (2 << 16) + 3, (4 << 24) + (5 << 8) + 6, |
168 | (7ULL << 32) + (8 << 16), |
169 | (9ULL << 56) + (10ULL << 40) + 11, |
170 | 0xd1, 0x78, |
171 | 0, 1, |
172 | 3, 0, 2, |
173 | 6, 5, 0, 4, |
174 | 0, 0, 8, 0, 7, |
175 | 11, 0, 0, 0, 0, 10, 0, 9, |
176 | -1); |
177 | // clang-format on |
178 | } |
179 | |
180 | TEST(GroupVarint, GroupVarintEncoder) { |
181 | std::string s; |
182 | { |
183 | GroupVarint32Encoder gv(s); |
184 | gv.add(0); |
185 | gv.finish(); |
186 | } |
187 | EXPECT_EQ(2, s.size()); |
188 | EXPECT_EQ(std::string("\x00\x00" , 2), s); |
189 | s.clear(); |
190 | { |
191 | GroupVarint32Encoder gv(s); |
192 | gv.add(1); |
193 | gv.add(2); |
194 | gv.add(3); |
195 | gv.add(4); |
196 | gv.finish(); |
197 | } |
198 | EXPECT_EQ(5, s.size()); |
199 | EXPECT_EQ(std::string("\x00\x01\x02\x03\x04" , 5), s); |
200 | } |
201 | |
202 | TEST(GroupVarint, GroupVarintDecoder) { |
203 | // Make sure we don't read out of bounds |
204 | std::string padding(17, 'X'); |
205 | |
206 | { |
207 | std::string s("\x00\x00" , 2); |
208 | s += padding; |
209 | StringPiece p(s.data(), 2); |
210 | |
211 | GroupVarint32Decoder gv(p); |
212 | uint32_t v; |
213 | EXPECT_TRUE(gv.next(&v)); |
214 | EXPECT_EQ(0, v); |
215 | EXPECT_FALSE(gv.next(&v)); |
216 | EXPECT_TRUE(gv.rest().empty()); |
217 | } |
218 | |
219 | { |
220 | std::string s("\x00\x01\x02\x03\x04\x01\x02\x03\x04" , 9); |
221 | s += padding; |
222 | StringPiece p(s.data(), 9); |
223 | |
224 | GroupVarint32Decoder gv(p); |
225 | uint32_t v; |
226 | EXPECT_TRUE(gv.next(&v)); |
227 | EXPECT_EQ(1, v); |
228 | EXPECT_TRUE(gv.next(&v)); |
229 | EXPECT_EQ(2, v); |
230 | EXPECT_TRUE(gv.next(&v)); |
231 | EXPECT_EQ(3, v); |
232 | EXPECT_TRUE(gv.next(&v)); |
233 | EXPECT_EQ(4, v); |
234 | EXPECT_TRUE(gv.next(&v)); |
235 | EXPECT_EQ(0x0302, v); |
236 | EXPECT_TRUE(gv.next(&v)); |
237 | EXPECT_EQ(4, v); |
238 | EXPECT_FALSE(gv.next(&v)); |
239 | EXPECT_TRUE(gv.rest().empty()); |
240 | } |
241 | |
242 | { |
243 | // Limit max count when reading a full block |
244 | std::string s("\x00\x01\x02\x03\x04\x01\x02\x03\x04" , 9); |
245 | s += padding; |
246 | StringPiece p(s.data(), 9); |
247 | |
248 | GroupVarint32Decoder gv(p, 3); |
249 | uint32_t v; |
250 | EXPECT_TRUE(gv.next(&v)); |
251 | EXPECT_EQ(1, v); |
252 | EXPECT_TRUE(gv.next(&v)); |
253 | EXPECT_EQ(2, v); |
254 | EXPECT_TRUE(gv.next(&v)); |
255 | EXPECT_EQ(3, v); |
256 | EXPECT_FALSE(gv.next(&v)); |
257 | EXPECT_EQ(std::string("\x04\x01\x02\x03\x04" , 5), gv.rest().toString()); |
258 | } |
259 | |
260 | { |
261 | // Limit max count when reading a partial block |
262 | std::string s("\x00\x01\x02\x03\x04\x01\x02\x03\x04" , 9); |
263 | s += padding; |
264 | StringPiece p(s.data(), 9); |
265 | |
266 | GroupVarint32Decoder gv(p, 5); |
267 | uint32_t v; |
268 | EXPECT_TRUE(gv.next(&v)); |
269 | EXPECT_EQ(1, v); |
270 | EXPECT_TRUE(gv.next(&v)); |
271 | EXPECT_EQ(2, v); |
272 | EXPECT_TRUE(gv.next(&v)); |
273 | EXPECT_EQ(3, v); |
274 | EXPECT_TRUE(gv.next(&v)); |
275 | EXPECT_EQ(4, v); |
276 | EXPECT_TRUE(gv.next(&v)); |
277 | EXPECT_EQ(0x0302, v); |
278 | EXPECT_FALSE(gv.next(&v)); |
279 | EXPECT_EQ(std::string("\x04" , 1), gv.rest().toString()); |
280 | } |
281 | } |
282 | |
283 | #endif |
284 | |