annotate src/test/serialize_tests.cpp @ 3640:195f5ad43476 draft

Compact serialization for variable-length integers Variable-length integers: bytes are a MSB base-128 encoding of the number. The high bit in each byte signifies whether another digit follows. To make the encoding is one-to-one, one is subtracted from all but the last digit. Thus, the byte sequence a[] with length len, where all but the last byte has bit 128 set, encodes the number: (a[len-1] & 0x7F) + sum(i=1..len-1, 128^i*((a[len-i-1] & 0x7F)+1)) Properties: * Very small (0-127: 1 byte, 128-16511: 2 bytes, 16512-2113663: 3 bytes) * Every integer has exactly one encoding * Encoding does not depend on size of original integer type
author Pieter Wuille <pieter.wuille@gmail.com>
date Fri, 15 Jun 2012 14:19:11 +0200
parents
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
3640
195f5ad43476 Compact serialization for variable-length integers
Pieter Wuille <pieter.wuille@gmail.com>
parents:
diff changeset
1 #include <boost/test/unit_test.hpp>
195f5ad43476 Compact serialization for variable-length integers
Pieter Wuille <pieter.wuille@gmail.com>
parents:
diff changeset
2
195f5ad43476 Compact serialization for variable-length integers
Pieter Wuille <pieter.wuille@gmail.com>
parents:
diff changeset
3 #include <string>
195f5ad43476 Compact serialization for variable-length integers
Pieter Wuille <pieter.wuille@gmail.com>
parents:
diff changeset
4 #include <vector>
195f5ad43476 Compact serialization for variable-length integers
Pieter Wuille <pieter.wuille@gmail.com>
parents:
diff changeset
5
195f5ad43476 Compact serialization for variable-length integers
Pieter Wuille <pieter.wuille@gmail.com>
parents:
diff changeset
6 #include "serialize.h"
195f5ad43476 Compact serialization for variable-length integers
Pieter Wuille <pieter.wuille@gmail.com>
parents:
diff changeset
7
195f5ad43476 Compact serialization for variable-length integers
Pieter Wuille <pieter.wuille@gmail.com>
parents:
diff changeset
8 using namespace std;
195f5ad43476 Compact serialization for variable-length integers
Pieter Wuille <pieter.wuille@gmail.com>
parents:
diff changeset
9
195f5ad43476 Compact serialization for variable-length integers
Pieter Wuille <pieter.wuille@gmail.com>
parents:
diff changeset
10 BOOST_AUTO_TEST_SUITE(serialize_tests)
195f5ad43476 Compact serialization for variable-length integers
Pieter Wuille <pieter.wuille@gmail.com>
parents:
diff changeset
11
195f5ad43476 Compact serialization for variable-length integers
Pieter Wuille <pieter.wuille@gmail.com>
parents:
diff changeset
12 BOOST_AUTO_TEST_CASE(varints)
195f5ad43476 Compact serialization for variable-length integers
Pieter Wuille <pieter.wuille@gmail.com>
parents:
diff changeset
13 {
195f5ad43476 Compact serialization for variable-length integers
Pieter Wuille <pieter.wuille@gmail.com>
parents:
diff changeset
14 // encode
195f5ad43476 Compact serialization for variable-length integers
Pieter Wuille <pieter.wuille@gmail.com>
parents:
diff changeset
15
195f5ad43476 Compact serialization for variable-length integers
Pieter Wuille <pieter.wuille@gmail.com>
parents:
diff changeset
16 CDataStream ss(SER_DISK, 0);
195f5ad43476 Compact serialization for variable-length integers
Pieter Wuille <pieter.wuille@gmail.com>
parents:
diff changeset
17 CDataStream::size_type size = 0;
195f5ad43476 Compact serialization for variable-length integers
Pieter Wuille <pieter.wuille@gmail.com>
parents:
diff changeset
18 for (int i = 0; i < 100000; i++) {
195f5ad43476 Compact serialization for variable-length integers
Pieter Wuille <pieter.wuille@gmail.com>
parents:
diff changeset
19 ss << VARINT(i);
195f5ad43476 Compact serialization for variable-length integers
Pieter Wuille <pieter.wuille@gmail.com>
parents:
diff changeset
20 size += ::GetSerializeSize(VARINT(i), 0, 0);
195f5ad43476 Compact serialization for variable-length integers
Pieter Wuille <pieter.wuille@gmail.com>
parents:
diff changeset
21 BOOST_CHECK(size == ss.size());
195f5ad43476 Compact serialization for variable-length integers
Pieter Wuille <pieter.wuille@gmail.com>
parents:
diff changeset
22 }
195f5ad43476 Compact serialization for variable-length integers
Pieter Wuille <pieter.wuille@gmail.com>
parents:
diff changeset
23
195f5ad43476 Compact serialization for variable-length integers
Pieter Wuille <pieter.wuille@gmail.com>
parents:
diff changeset
24 for (uint64 i = 0; i < 100000000000ULL; i += 999999937) {
195f5ad43476 Compact serialization for variable-length integers
Pieter Wuille <pieter.wuille@gmail.com>
parents:
diff changeset
25 ss << VARINT(i);
195f5ad43476 Compact serialization for variable-length integers
Pieter Wuille <pieter.wuille@gmail.com>
parents:
diff changeset
26 size += ::GetSerializeSize(VARINT(i), 0, 0);
195f5ad43476 Compact serialization for variable-length integers
Pieter Wuille <pieter.wuille@gmail.com>
parents:
diff changeset
27 BOOST_CHECK(size == ss.size());
195f5ad43476 Compact serialization for variable-length integers
Pieter Wuille <pieter.wuille@gmail.com>
parents:
diff changeset
28 }
195f5ad43476 Compact serialization for variable-length integers
Pieter Wuille <pieter.wuille@gmail.com>
parents:
diff changeset
29
195f5ad43476 Compact serialization for variable-length integers
Pieter Wuille <pieter.wuille@gmail.com>
parents:
diff changeset
30 // decode
195f5ad43476 Compact serialization for variable-length integers
Pieter Wuille <pieter.wuille@gmail.com>
parents:
diff changeset
31 for (int i = 0; i < 100000; i++) {
195f5ad43476 Compact serialization for variable-length integers
Pieter Wuille <pieter.wuille@gmail.com>
parents:
diff changeset
32 int j;
195f5ad43476 Compact serialization for variable-length integers
Pieter Wuille <pieter.wuille@gmail.com>
parents:
diff changeset
33 ss >> VARINT(j);
195f5ad43476 Compact serialization for variable-length integers
Pieter Wuille <pieter.wuille@gmail.com>
parents:
diff changeset
34 BOOST_CHECK_MESSAGE(i == j, "decoded:" << j << " expected:" << i);
195f5ad43476 Compact serialization for variable-length integers
Pieter Wuille <pieter.wuille@gmail.com>
parents:
diff changeset
35 }
195f5ad43476 Compact serialization for variable-length integers
Pieter Wuille <pieter.wuille@gmail.com>
parents:
diff changeset
36
195f5ad43476 Compact serialization for variable-length integers
Pieter Wuille <pieter.wuille@gmail.com>
parents:
diff changeset
37 for (uint64 i = 0; i < 100000000000ULL; i += 999999937) {
195f5ad43476 Compact serialization for variable-length integers
Pieter Wuille <pieter.wuille@gmail.com>
parents:
diff changeset
38 uint64 j;
195f5ad43476 Compact serialization for variable-length integers
Pieter Wuille <pieter.wuille@gmail.com>
parents:
diff changeset
39 ss >> VARINT(j);
195f5ad43476 Compact serialization for variable-length integers
Pieter Wuille <pieter.wuille@gmail.com>
parents:
diff changeset
40 BOOST_CHECK_MESSAGE(i == j, "decoded:" << j << " expected:" << i);
195f5ad43476 Compact serialization for variable-length integers
Pieter Wuille <pieter.wuille@gmail.com>
parents:
diff changeset
41 }
195f5ad43476 Compact serialization for variable-length integers
Pieter Wuille <pieter.wuille@gmail.com>
parents:
diff changeset
42
195f5ad43476 Compact serialization for variable-length integers
Pieter Wuille <pieter.wuille@gmail.com>
parents:
diff changeset
43 }
195f5ad43476 Compact serialization for variable-length integers
Pieter Wuille <pieter.wuille@gmail.com>
parents:
diff changeset
44
195f5ad43476 Compact serialization for variable-length integers
Pieter Wuille <pieter.wuille@gmail.com>
parents:
diff changeset
45 BOOST_AUTO_TEST_SUITE_END()