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 <gtest/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;
42 typedef GroupVarintDecoder<uint32_t> GroupVarint32Decoder;
43 typedef GroupVarintDecoder<uint32_t> GroupVarint64Decoder;
45 // Expected bytes follow, terminate with -1
46 void testGroupVarint32(uint32_t a, uint32_t b, uint32_t c, uint32_t d, ...) {
49 std::vector<char> expectedBytes;
51 while ((byte = va_arg(ap, int)) != -1) {
52 expectedBytes.push_back(byte);
56 size_t size = GroupVarint32::size(a, b, c, d);
57 EXPECT_EQ(expectedBytes.size(), size);
59 std::vector<char> foundBytes;
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);
68 for (size_t i = 0; i < size; i++) {
69 EXPECT_EQ(0xff & expectedBytes[i], 0xff & foundBytes[i]);
73 EXPECT_EQ(size, GroupVarint32::encodedSize(start));
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);
85 void testGroupVarint64(uint64_t a, uint64_t b, uint64_t c, uint64_t d,
89 std::vector<char> expectedBytes;
91 while ((byte = va_arg(ap, int)) != -1) {
92 expectedBytes.push_back(byte);
96 size_t size = GroupVarint64::size(a, b, c, d, e);
97 EXPECT_EQ(expectedBytes.size(), size);
99 std::vector<char> foundBytes;
100 foundBytes.resize(size + 8);
101 char* start = &(foundBytes.front());
102 char* p = GroupVarint64::encode(start, a, b, c, d, e);
103 EXPECT_EQ((void*)(start + size), (void*)p);
105 for (size_t i = 0; i < size; i++) {
106 EXPECT_EQ(0xff & expectedBytes[i], 0xff & foundBytes[i]);
110 EXPECT_EQ(size, GroupVarint64::encodedSize(start));
112 uint64_t fa, fb, fc, fd, fe;
113 const char* r = GroupVarint64::decode(start, &fa, &fb, &fc, &fd, &fe);
114 EXPECT_EQ((void*)(start + size), (void*)r);
125 TEST(GroupVarint, GroupVarint32) {
126 EXPECT_EQ(0, GroupVarint32::maxSize(0));
127 EXPECT_EQ(5, GroupVarint32::maxSize(1));
128 EXPECT_EQ(9, GroupVarint32::maxSize(2));
129 EXPECT_EQ(13, GroupVarint32::maxSize(3));
130 EXPECT_EQ(17, GroupVarint32::maxSize(4));
131 EXPECT_EQ(22, GroupVarint32::maxSize(5));
132 EXPECT_EQ(26, GroupVarint32::maxSize(6));
133 testGroupVarint32(0, 0, 0, 0,
135 testGroupVarint32(1, 2, 3, 4,
137 testGroupVarint32(1 << 8, (2 << 16) + 3, (4 << 24) + (5 << 8) + 6, 7,
138 0x39, 0, 1, 3, 0, 2, 6, 5, 0, 4, 7, -1);
141 TEST(GroupVarint, GroupVarint64) {
142 EXPECT_EQ(0, GroupVarint64::maxSize(0));
143 EXPECT_EQ(10, GroupVarint64::maxSize(1));
144 EXPECT_EQ(18, GroupVarint64::maxSize(2));
145 EXPECT_EQ(26, GroupVarint64::maxSize(3));
146 EXPECT_EQ(34, GroupVarint64::maxSize(4));
147 EXPECT_EQ(42, GroupVarint64::maxSize(5));
148 EXPECT_EQ(52, GroupVarint64::maxSize(6));
149 testGroupVarint64(0, 0, 0, 0, 0,
150 0, 0, 0, 0, 0, 0, 0, -1);
151 testGroupVarint64(1, 2, 3, 4, 5,
152 0, 0, 1, 2, 3, 4, 5, -1);
153 testGroupVarint64(1 << 8, (2 << 16) + 3, (4 << 24) + (5 << 8) + 6,
154 (7ULL << 32) + (8 << 16),
155 (9ULL << 56) + (10ULL << 40) + 11,
161 11, 0, 0, 0, 0, 10, 0, 9,
165 TEST(GroupVarint, GroupVarintEncoder) {
168 GroupVarint32Encoder gv(s);
172 EXPECT_EQ(2, s.size());
173 EXPECT_EQ(std::string("\x00\x00", 2), s);
176 GroupVarint32Encoder gv(s);
183 EXPECT_EQ(5, s.size());
184 EXPECT_EQ(std::string("\x00\x01\x02\x03\x04", 5), s);
188 TEST(GroupVarint, GroupVarintDecoder) {
189 // Make sure we don't read out of bounds
190 std::string padding(17, 'X');
193 std::string s("\x00\x00", 2);
195 StringPiece p(s.data(), 2);
197 GroupVarint32Decoder gv(p);
199 EXPECT_TRUE(gv.next(&v));
201 EXPECT_FALSE(gv.next(&v));
202 EXPECT_TRUE(gv.rest().empty());
206 std::string s("\x00\x01\x02\x03\x04\x01\x02\x03\x04", 9);
208 StringPiece p(s.data(), 9);
210 GroupVarint32Decoder gv(p);
212 EXPECT_TRUE(gv.next(&v));
214 EXPECT_TRUE(gv.next(&v));
216 EXPECT_TRUE(gv.next(&v));
218 EXPECT_TRUE(gv.next(&v));
220 EXPECT_TRUE(gv.next(&v));
221 EXPECT_EQ(0x0302, v);
222 EXPECT_TRUE(gv.next(&v));
224 EXPECT_FALSE(gv.next(&v));
225 EXPECT_TRUE(gv.rest().empty());
229 // Limit max count when reading a full block
230 std::string s("\x00\x01\x02\x03\x04\x01\x02\x03\x04", 9);
232 StringPiece p(s.data(), 9);
234 GroupVarint32Decoder gv(p, 3);
236 EXPECT_TRUE(gv.next(&v));
238 EXPECT_TRUE(gv.next(&v));
240 EXPECT_TRUE(gv.next(&v));
242 EXPECT_FALSE(gv.next(&v));
243 EXPECT_EQ(std::string("\x04\x01\x02\x03\x04", 5), gv.rest().toString());
247 // Limit max count when reading a partial block
248 std::string s("\x00\x01\x02\x03\x04\x01\x02\x03\x04", 9);
250 StringPiece p(s.data(), 9);
252 GroupVarint32Decoder gv(p, 5);
254 EXPECT_TRUE(gv.next(&v));
256 EXPECT_TRUE(gv.next(&v));
258 EXPECT_TRUE(gv.next(&v));
260 EXPECT_TRUE(gv.next(&v));
262 EXPECT_TRUE(gv.next(&v));
263 EXPECT_EQ(0x0302, v);
264 EXPECT_FALSE(gv.next(&v));
265 EXPECT_EQ(std::string("\x04", 1), gv.rest().toString());