2 * Copyright 2012-present 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.
17 #include <folly/GroupVarint.h>
22 // On platforms where it's not supported, GroupVarint will be compiled out.
25 #include <folly/portability/GTest.h>
27 using namespace folly;
31 class StringAppender {
33 /* implicit */ StringAppender(std::string& s) : s_(s) { }
34 void operator()(StringPiece sp) {
35 s_.append(sp.data(), sp.size());
41 typedef GroupVarintEncoder<uint32_t, StringAppender> GroupVarint32Encoder;
42 typedef GroupVarintEncoder<uint64_t, StringAppender> GroupVarint64Encoder;
44 // Expected bytes follow, terminate with -1
45 void testGroupVarint32(uint32_t a, uint32_t b, uint32_t c, uint32_t d, ...) {
48 std::vector<char> expectedBytes;
50 while ((byte = va_arg(ap, int)) != -1) {
51 expectedBytes.push_back(byte);
55 size_t size = GroupVarint32::size(a, b, c, d);
56 EXPECT_EQ(expectedBytes.size(), size);
58 std::vector<char> foundBytes;
60 // ssse3 decoding requires that the source buffer have length >= 17,
61 // so that it can read 128 bits from &start[1] via _mm_loadu_si128.
62 foundBytes.resize(std::max<size_t>(size + 4, 17UL));
63 char* start = &(foundBytes.front());
64 char* p = GroupVarint32::encode(start, a, b, c, d);
65 EXPECT_EQ((void*)(start + size), (void*)p);
67 for (size_t i = 0; i < size; i++) {
68 EXPECT_EQ(0xff & expectedBytes[i], 0xff & foundBytes[i]);
72 EXPECT_EQ(size, GroupVarint32::encodedSize(start));
74 uint32_t fa, fb, fc, fd;
75 const char* r = GroupVarint32::decode(start, &fa, &fb, &fc, &fd);
76 EXPECT_EQ((void*)(start + size), (void*)r);
84 void testGroupVarint64(uint64_t a, uint64_t b, uint64_t c, uint64_t d,
88 std::vector<char> expectedBytes;
90 while ((byte = va_arg(ap, int)) != -1) {
91 expectedBytes.push_back(byte);
95 size_t size = GroupVarint64::size(a, b, c, d, e);
96 EXPECT_EQ(expectedBytes.size(), size);
98 std::vector<char> foundBytes;
99 foundBytes.resize(size + 8);
100 char* start = &(foundBytes.front());
101 char* p = GroupVarint64::encode(start, a, b, c, d, e);
102 EXPECT_EQ((void*)(start + size), (void*)p);
104 for (size_t i = 0; i < size; i++) {
105 EXPECT_EQ(0xff & expectedBytes[i], 0xff & foundBytes[i]);
109 EXPECT_EQ(size, GroupVarint64::encodedSize(start));
111 uint64_t fa, fb, fc, fd, fe;
112 const char* r = GroupVarint64::decode(start, &fa, &fb, &fc, &fd, &fe);
113 EXPECT_EQ((void*)(start + size), (void*)r);
124 TEST(GroupVarint, GroupVarint32) {
125 EXPECT_EQ(0, GroupVarint32::maxSize(0));
126 EXPECT_EQ(5, GroupVarint32::maxSize(1));
127 EXPECT_EQ(9, GroupVarint32::maxSize(2));
128 EXPECT_EQ(13, GroupVarint32::maxSize(3));
129 EXPECT_EQ(17, GroupVarint32::maxSize(4));
130 EXPECT_EQ(22, GroupVarint32::maxSize(5));
131 EXPECT_EQ(26, GroupVarint32::maxSize(6));
132 testGroupVarint32(0, 0, 0, 0,
134 testGroupVarint32(1, 2, 3, 4,
136 testGroupVarint32(1 << 8, (2 << 16) + 3, (4 << 24) + (5 << 8) + 6, 7,
137 0x39, 0, 1, 3, 0, 2, 6, 5, 0, 4, 7, -1);
140 TEST(GroupVarint, GroupVarint64) {
141 EXPECT_EQ(0, GroupVarint64::maxSize(0));
142 EXPECT_EQ(10, GroupVarint64::maxSize(1));
143 EXPECT_EQ(18, GroupVarint64::maxSize(2));
144 EXPECT_EQ(26, GroupVarint64::maxSize(3));
145 EXPECT_EQ(34, GroupVarint64::maxSize(4));
146 EXPECT_EQ(42, GroupVarint64::maxSize(5));
147 EXPECT_EQ(52, GroupVarint64::maxSize(6));
148 testGroupVarint64(0, 0, 0, 0, 0,
149 0, 0, 0, 0, 0, 0, 0, -1);
150 testGroupVarint64(1, 2, 3, 4, 5,
151 0, 0, 1, 2, 3, 4, 5, -1);
152 testGroupVarint64(1 << 8, (2 << 16) + 3, (4 << 24) + (5 << 8) + 6,
153 (7ULL << 32) + (8 << 16),
154 (9ULL << 56) + (10ULL << 40) + 11,
160 11, 0, 0, 0, 0, 10, 0, 9,
164 TEST(GroupVarint, GroupVarintEncoder) {
167 GroupVarint32Encoder gv(s);
171 EXPECT_EQ(2, s.size());
172 EXPECT_EQ(std::string("\x00\x00", 2), s);
175 GroupVarint32Encoder gv(s);
182 EXPECT_EQ(5, s.size());
183 EXPECT_EQ(std::string("\x00\x01\x02\x03\x04", 5), s);
187 TEST(GroupVarint, GroupVarintDecoder) {
188 // Make sure we don't read out of bounds
189 std::string padding(17, 'X');
192 std::string s("\x00\x00", 2);
194 StringPiece p(s.data(), 2);
196 GroupVarint32Decoder gv(p);
198 EXPECT_TRUE(gv.next(&v));
200 EXPECT_FALSE(gv.next(&v));
201 EXPECT_TRUE(gv.rest().empty());
205 std::string s("\x00\x01\x02\x03\x04\x01\x02\x03\x04", 9);
207 StringPiece p(s.data(), 9);
209 GroupVarint32Decoder gv(p);
211 EXPECT_TRUE(gv.next(&v));
213 EXPECT_TRUE(gv.next(&v));
215 EXPECT_TRUE(gv.next(&v));
217 EXPECT_TRUE(gv.next(&v));
219 EXPECT_TRUE(gv.next(&v));
220 EXPECT_EQ(0x0302, v);
221 EXPECT_TRUE(gv.next(&v));
223 EXPECT_FALSE(gv.next(&v));
224 EXPECT_TRUE(gv.rest().empty());
228 // Limit max count when reading a full block
229 std::string s("\x00\x01\x02\x03\x04\x01\x02\x03\x04", 9);
231 StringPiece p(s.data(), 9);
233 GroupVarint32Decoder gv(p, 3);
235 EXPECT_TRUE(gv.next(&v));
237 EXPECT_TRUE(gv.next(&v));
239 EXPECT_TRUE(gv.next(&v));
241 EXPECT_FALSE(gv.next(&v));
242 EXPECT_EQ(std::string("\x04\x01\x02\x03\x04", 5), gv.rest().toString());
246 // Limit max count when reading a partial block
247 std::string s("\x00\x01\x02\x03\x04\x01\x02\x03\x04", 9);
249 StringPiece p(s.data(), 9);
251 GroupVarint32Decoder gv(p, 5);
253 EXPECT_TRUE(gv.next(&v));
255 EXPECT_TRUE(gv.next(&v));
257 EXPECT_TRUE(gv.next(&v));
259 EXPECT_TRUE(gv.next(&v));
261 EXPECT_TRUE(gv.next(&v));
262 EXPECT_EQ(0x0302, v);
263 EXPECT_FALSE(gv.next(&v));
264 EXPECT_EQ(std::string("\x04", 1), gv.rest().toString());