2 * Copyright 2016 Facebook, Inc.
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
19 #include <folly/GroupVarint.h>
21 // On platforms where it's not supported, GroupVarint will be compiled out.
24 #include <folly/portability/GTest.h>
26 using namespace folly;
30 class StringAppender {
32 /* implicit */ StringAppender(std::string& s) : s_(s) { }
33 void operator()(StringPiece sp) {
34 s_.append(sp.data(), sp.size());
40 typedef GroupVarintEncoder<uint32_t, StringAppender> GroupVarint32Encoder;
41 typedef GroupVarintEncoder<uint64_t, StringAppender> GroupVarint64Encoder;
43 // Expected bytes follow, terminate with -1
44 void testGroupVarint32(uint32_t a, uint32_t b, uint32_t c, uint32_t d, ...) {
47 std::vector<char> expectedBytes;
49 while ((byte = va_arg(ap, int)) != -1) {
50 expectedBytes.push_back(byte);
54 size_t size = GroupVarint32::size(a, b, c, d);
55 EXPECT_EQ(expectedBytes.size(), size);
57 std::vector<char> foundBytes;
59 // ssse3 decoding requires that the source buffer have length >= 17,
60 // so that it can read 128 bits from &start[1] via _mm_loadu_si128.
61 foundBytes.resize(std::max<size_t>(size + 4, 17UL));
62 char* start = &(foundBytes.front());
63 char* p = GroupVarint32::encode(start, a, b, c, d);
64 EXPECT_EQ((void*)(start + size), (void*)p);
66 for (size_t i = 0; i < size; i++) {
67 EXPECT_EQ(0xff & expectedBytes[i], 0xff & foundBytes[i]);
71 EXPECT_EQ(size, GroupVarint32::encodedSize(start));
73 uint32_t fa, fb, fc, fd;
74 const char* r = GroupVarint32::decode(start, &fa, &fb, &fc, &fd);
75 EXPECT_EQ((void*)(start + size), (void*)r);
83 void testGroupVarint64(uint64_t a, uint64_t b, uint64_t c, uint64_t d,
87 std::vector<char> expectedBytes;
89 while ((byte = va_arg(ap, int)) != -1) {
90 expectedBytes.push_back(byte);
94 size_t size = GroupVarint64::size(a, b, c, d, e);
95 EXPECT_EQ(expectedBytes.size(), size);
97 std::vector<char> foundBytes;
98 foundBytes.resize(size + 8);
99 char* start = &(foundBytes.front());
100 char* p = GroupVarint64::encode(start, a, b, c, d, e);
101 EXPECT_EQ((void*)(start + size), (void*)p);
103 for (size_t i = 0; i < size; i++) {
104 EXPECT_EQ(0xff & expectedBytes[i], 0xff & foundBytes[i]);
108 EXPECT_EQ(size, GroupVarint64::encodedSize(start));
110 uint64_t fa, fb, fc, fd, fe;
111 const char* r = GroupVarint64::decode(start, &fa, &fb, &fc, &fd, &fe);
112 EXPECT_EQ((void*)(start + size), (void*)r);
123 TEST(GroupVarint, GroupVarint32) {
124 EXPECT_EQ(0, GroupVarint32::maxSize(0));
125 EXPECT_EQ(5, GroupVarint32::maxSize(1));
126 EXPECT_EQ(9, GroupVarint32::maxSize(2));
127 EXPECT_EQ(13, GroupVarint32::maxSize(3));
128 EXPECT_EQ(17, GroupVarint32::maxSize(4));
129 EXPECT_EQ(22, GroupVarint32::maxSize(5));
130 EXPECT_EQ(26, GroupVarint32::maxSize(6));
131 testGroupVarint32(0, 0, 0, 0,
133 testGroupVarint32(1, 2, 3, 4,
135 testGroupVarint32(1 << 8, (2 << 16) + 3, (4 << 24) + (5 << 8) + 6, 7,
136 0x39, 0, 1, 3, 0, 2, 6, 5, 0, 4, 7, -1);
139 TEST(GroupVarint, GroupVarint64) {
140 EXPECT_EQ(0, GroupVarint64::maxSize(0));
141 EXPECT_EQ(10, GroupVarint64::maxSize(1));
142 EXPECT_EQ(18, GroupVarint64::maxSize(2));
143 EXPECT_EQ(26, GroupVarint64::maxSize(3));
144 EXPECT_EQ(34, GroupVarint64::maxSize(4));
145 EXPECT_EQ(42, GroupVarint64::maxSize(5));
146 EXPECT_EQ(52, GroupVarint64::maxSize(6));
147 testGroupVarint64(0, 0, 0, 0, 0,
148 0, 0, 0, 0, 0, 0, 0, -1);
149 testGroupVarint64(1, 2, 3, 4, 5,
150 0, 0, 1, 2, 3, 4, 5, -1);
151 testGroupVarint64(1 << 8, (2 << 16) + 3, (4 << 24) + (5 << 8) + 6,
152 (7ULL << 32) + (8 << 16),
153 (9ULL << 56) + (10ULL << 40) + 11,
159 11, 0, 0, 0, 0, 10, 0, 9,
163 TEST(GroupVarint, GroupVarintEncoder) {
166 GroupVarint32Encoder gv(s);
170 EXPECT_EQ(2, s.size());
171 EXPECT_EQ(std::string("\x00\x00", 2), s);
174 GroupVarint32Encoder gv(s);
181 EXPECT_EQ(5, s.size());
182 EXPECT_EQ(std::string("\x00\x01\x02\x03\x04", 5), s);
186 TEST(GroupVarint, GroupVarintDecoder) {
187 // Make sure we don't read out of bounds
188 std::string padding(17, 'X');
191 std::string s("\x00\x00", 2);
193 StringPiece p(s.data(), 2);
195 GroupVarint32Decoder gv(p);
197 EXPECT_TRUE(gv.next(&v));
199 EXPECT_FALSE(gv.next(&v));
200 EXPECT_TRUE(gv.rest().empty());
204 std::string s("\x00\x01\x02\x03\x04\x01\x02\x03\x04", 9);
206 StringPiece p(s.data(), 9);
208 GroupVarint32Decoder gv(p);
210 EXPECT_TRUE(gv.next(&v));
212 EXPECT_TRUE(gv.next(&v));
214 EXPECT_TRUE(gv.next(&v));
216 EXPECT_TRUE(gv.next(&v));
218 EXPECT_TRUE(gv.next(&v));
219 EXPECT_EQ(0x0302, v);
220 EXPECT_TRUE(gv.next(&v));
222 EXPECT_FALSE(gv.next(&v));
223 EXPECT_TRUE(gv.rest().empty());
227 // Limit max count when reading a full block
228 std::string s("\x00\x01\x02\x03\x04\x01\x02\x03\x04", 9);
230 StringPiece p(s.data(), 9);
232 GroupVarint32Decoder gv(p, 3);
234 EXPECT_TRUE(gv.next(&v));
236 EXPECT_TRUE(gv.next(&v));
238 EXPECT_TRUE(gv.next(&v));
240 EXPECT_FALSE(gv.next(&v));
241 EXPECT_EQ(std::string("\x04\x01\x02\x03\x04", 5), gv.rest().toString());
245 // Limit max count when reading a partial block
246 std::string s("\x00\x01\x02\x03\x04\x01\x02\x03\x04", 9);
248 StringPiece p(s.data(), 9);
250 GroupVarint32Decoder gv(p, 5);
252 EXPECT_TRUE(gv.next(&v));
254 EXPECT_TRUE(gv.next(&v));
256 EXPECT_TRUE(gv.next(&v));
258 EXPECT_TRUE(gv.next(&v));
260 EXPECT_TRUE(gv.next(&v));
261 EXPECT_EQ(0x0302, v);
262 EXPECT_FALSE(gv.next(&v));
263 EXPECT_EQ(std::string("\x04", 1), gv.rest().toString());