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
27using namespace folly;
28
29namespace {
30
31class 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
42typedef GroupVarintEncoder<uint32_t, StringAppender> GroupVarint32Encoder;
43typedef GroupVarintEncoder<uint64_t, StringAppender> GroupVarint64Encoder;
44
45// Expected bytes follow, terminate with -1
46void 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
85void 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
130TEST(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
151TEST(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
180TEST(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
202TEST(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