blob: 41f6c6788a5ff2f0d3608a36e8dc5b2707e3307f (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
|
/* Copyright (C) 2007-2008 The Android Open Source Project
**
** This software is licensed under the terms of the GNU General Public
** License version 2, as published by the Free Software Foundation, and
** may be copied, distributed, and modified under those terms.
**
** This program is distributed in the hope that it will be useful,
** but WITHOUT ANY WARRANTY; without even the implied warranty of
** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
** GNU General Public License for more details.
*/
#include <inttypes.h>
#include "varint.h"
// Define some constants for powers of two.
static const int k2Exp6 = 64;
static const uint32_t k2Exp7 = 128;
static const int k2Exp13 = 8192;
static const uint32_t k2Exp14 = 16384;
static const int k2Exp20 = (1 * 1024 * 1024);
static const uint32_t k2Exp21 = (2 * 1024 * 1024);
static const int k2Exp27 = (128 * 1024 * 1024);
static const uint32_t k2Exp28 = (256 * 1024 * 1024);
static const uint64_t k2Exp35 = (32LL * 1024LL * 1024LL * 1024LL);
static const uint64_t k2Exp42 = (4LL * 1024LL * 1024LL * 1024LL * 1024LL);
// Encodes the 64-bit value "value" using the varint encoding. The varint
// encoding uses a prefix followed by some data bits. The valid prefixes
// and the number of data bits are given in the table below.
//
// Prefix Bytes Data bits
// 0 1 7
// 10 2 14
// 110 3 21
// 1110 4 28
// 11110 5 35
// 111110 6 42
// 11111100 9 64
// 11111101 reserved
// 11111110 reserved
// 11111111 reserved
char *varint_encode(uint64_t value, char *buf) {
if (value < k2Exp7) {
*buf++ = value;
} else if (value < k2Exp14) {
*buf++ = (2 << 6) | (value >> 8);
*buf++ = value & 0xff;
} else if (value < k2Exp21) {
*buf++ = (6 << 5) | (value >> 16);
*buf++ = (value >> 8) & 0xff;
*buf++ = value & 0xff;
} else if (value < k2Exp28) {
*buf++ = (0xe << 4) | (value >> 24);
*buf++ = (value >> 16) & 0xff;
*buf++ = (value >> 8) & 0xff;
*buf++ = value & 0xff;
} else if (value < k2Exp35) {
*buf++ = (0x1e << 3) | (value >> 32);
*buf++ = (value >> 24) & 0xff;
*buf++ = (value >> 16) & 0xff;
*buf++ = (value >> 8) & 0xff;
*buf++ = value & 0xff;
} else if (value < k2Exp42) {
*buf++ = (0x3e << 2) | (value >> 40);
*buf++ = (value >> 32) & 0xff;
*buf++ = (value >> 24) & 0xff;
*buf++ = (value >> 16) & 0xff;
*buf++ = (value >> 8) & 0xff;
*buf++ = value & 0xff;
} else {
*buf++ = (0x7e << 1);
*buf++ = (value >> 56) & 0xff;
*buf++ = (value >> 48) & 0xff;
*buf++ = (value >> 40) & 0xff;
*buf++ = (value >> 32) & 0xff;
*buf++ = (value >> 24) & 0xff;
*buf++ = (value >> 16) & 0xff;
*buf++ = (value >> 8) & 0xff;
*buf++ = value & 0xff;
}
return buf;
}
// Encodes the 35-bit signed value "value" using the varint encoding.
// The varint encoding uses a prefix followed by some data bits. The
// valid prefixes and the number of data bits is given in the table
// below.
//
// Prefix Bytes Data bits
// 0 1 7
// 10 2 14
// 110 3 21
// 1110 4 28
// 11110 5 35
char *varint_encode_signed(int64_t value, char *buf) {
if (value < k2Exp6 && value >= -k2Exp6) {
*buf++ = value & 0x7f;
} else if (value < k2Exp13 && value >= -k2Exp13) {
*buf++ = (2 << 6) | ((value >> 8) & 0x3f);
*buf++ = value & 0xff;
} else if (value < k2Exp20 && value >= -k2Exp20) {
*buf++ = (6 << 5) | ((value >> 16) & 0x1f);
*buf++ = (value >> 8) & 0xff;
*buf++ = value & 0xff;
} else if (value < k2Exp27 && value >= -k2Exp27) {
*buf++ = (0xe << 4) | ((value >> 24) & 0xf);
*buf++ = (value >> 16) & 0xff;
*buf++ = (value >> 8) & 0xff;
*buf++ = value & 0xff;
} else {
*buf++ = (0x1e << 3);
*buf++ = (value >> 24) & 0xff;
*buf++ = (value >> 16) & 0xff;
*buf++ = (value >> 8) & 0xff;
*buf++ = value & 0xff;
}
return buf;
}
|
