Mercurial > hg > bitcoin
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 |
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() |