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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
|
/*
* upb - a minimalist implementation of protocol buffers.
*
* Copyright (c) 2011 Google Inc. See LICENSE for details.
* Author: Josh Haberman <jhaberman@gmail.com>
*
* A number of routines for varint manipulation (we keep them all around to
* have multiple approaches available for benchmarking).
*/
#ifndef UPB_VARINT_DECODER_H_
#define UPB_VARINT_DECODER_H_
#include <assert.h>
#include <stdint.h>
#include <string.h>
#include "upb/upb.h"
#ifdef __cplusplus
extern "C" {
#endif
/* A list of types as they are encoded on-the-wire. */
typedef enum {
UPB_WIRE_TYPE_VARINT = 0,
UPB_WIRE_TYPE_64BIT = 1,
UPB_WIRE_TYPE_DELIMITED = 2,
UPB_WIRE_TYPE_START_GROUP = 3,
UPB_WIRE_TYPE_END_GROUP = 4,
UPB_WIRE_TYPE_32BIT = 5
} upb_wiretype_t;
#define UPB_MAX_WIRE_TYPE 5
/* The maximum number of bytes that it takes to encode a 64-bit varint.
* Note that with a better encoding this could be 9 (TODO: write up a
* wiki document about this). */
#define UPB_PB_VARINT_MAX_LEN 10
/* Array of the "native" (ie. non-packed-repeated) wire type for the given a
* descriptor type (upb_descriptortype_t). */
extern const uint8_t upb_pb_native_wire_types[];
/* Zig-zag encoding/decoding **************************************************/
UPB_INLINE int32_t upb_zzdec_32(uint32_t n) {
return (n >> 1) ^ -(int32_t)(n & 1);
}
UPB_INLINE int64_t upb_zzdec_64(uint64_t n) {
return (n >> 1) ^ -(int64_t)(n & 1);
}
UPB_INLINE uint32_t upb_zzenc_32(int32_t n) { return (n << 1) ^ (n >> 31); }
UPB_INLINE uint64_t upb_zzenc_64(int64_t n) { return (n << 1) ^ (n >> 63); }
/* Decoding *******************************************************************/
/* All decoding functions return this struct by value. */
typedef struct {
const char *p; /* NULL if the varint was unterminated. */
uint64_t val;
} upb_decoderet;
UPB_INLINE upb_decoderet upb_decoderet_make(const char *p, uint64_t val) {
upb_decoderet ret;
ret.p = p;
ret.val = val;
return ret;
}
/* Four functions for decoding a varint of at most eight bytes. They are all
* functionally identical, but are implemented in different ways and likely have
* different performance profiles. We keep them around for performance testing.
*
* Note that these functions may not read byte-by-byte, so they must not be used
* unless there are at least eight bytes left in the buffer! */
upb_decoderet upb_vdecode_max8_branch32(upb_decoderet r);
upb_decoderet upb_vdecode_max8_branch64(upb_decoderet r);
upb_decoderet upb_vdecode_max8_wright(upb_decoderet r);
upb_decoderet upb_vdecode_max8_massimino(upb_decoderet r);
/* Template for a function that checks the first two bytes with branching
* and dispatches 2-10 bytes with a separate function. Note that this may read
* up to 10 bytes, so it must not be used unless there are at least ten bytes
* left in the buffer! */
#define UPB_VARINT_DECODER_CHECK2(name, decode_max8_function) \
UPB_INLINE upb_decoderet upb_vdecode_check2_ ## name(const char *_p) { \
uint8_t *p = (uint8_t*)_p; \
upb_decoderet r; \
if ((*p & 0x80) == 0) { \
/* Common case: one-byte varint. */ \
return upb_decoderet_make(_p + 1, *p & 0x7fU); \
} \
r = upb_decoderet_make(_p + 2, (*p & 0x7fU) | ((*(p + 1) & 0x7fU) << 7)); \
if ((*(p + 1) & 0x80) == 0) { \
/* Two-byte varint. */ \
return r; \
} \
/* Longer varint, fallback to out-of-line function. */ \
return decode_max8_function(r); \
}
UPB_VARINT_DECODER_CHECK2(branch32, upb_vdecode_max8_branch32)
UPB_VARINT_DECODER_CHECK2(branch64, upb_vdecode_max8_branch64)
UPB_VARINT_DECODER_CHECK2(wright, upb_vdecode_max8_wright)
UPB_VARINT_DECODER_CHECK2(massimino, upb_vdecode_max8_massimino)
#undef UPB_VARINT_DECODER_CHECK2
/* Our canonical functions for decoding varints, based on the currently
* favored best-performing implementations. */
UPB_INLINE upb_decoderet upb_vdecode_fast(const char *p) {
if (sizeof(long) == 8)
return upb_vdecode_check2_branch64(p);
else
return upb_vdecode_check2_branch32(p);
}
UPB_INLINE upb_decoderet upb_vdecode_max8_fast(upb_decoderet r) {
return upb_vdecode_max8_massimino(r);
}
/* Encoding *******************************************************************/
UPB_INLINE int upb_value_size(uint64_t val) {
#ifdef __GNUC__
int high_bit = 63 - __builtin_clzll(val); /* 0-based, undef if val == 0. */
#else
int high_bit = 0;
uint64_t tmp = val;
while(tmp >>= 1) high_bit++;
#endif
return val == 0 ? 1 : high_bit / 8 + 1;
}
/* Encodes a 64-bit varint into buf (which must be >=UPB_PB_VARINT_MAX_LEN
* bytes long), returning how many bytes were used.
*
* TODO: benchmark and optimize if necessary. */
UPB_INLINE size_t upb_vencode64(uint64_t val, char *buf) {
size_t i;
if (val == 0) { buf[0] = 0; return 1; }
i = 0;
while (val) {
uint8_t byte = val & 0x7fU;
val >>= 7;
if (val) byte |= 0x80U;
buf[i++] = byte;
}
return i;
}
UPB_INLINE size_t upb_varint_size(uint64_t val) {
char buf[UPB_PB_VARINT_MAX_LEN];
return upb_vencode64(val, buf);
}
/* Encodes a 32-bit varint, *not* sign-extended. */
UPB_INLINE uint64_t upb_vencode32(uint32_t val) {
char buf[UPB_PB_VARINT_MAX_LEN];
size_t bytes = upb_vencode64(val, buf);
uint64_t ret = 0;
assert(bytes <= 5);
memcpy(&ret, buf, bytes);
assert(ret <= 0xffffffffffU);
return ret;
}
#ifdef __cplusplus
} /* extern "C" */
#endif
#endif /* UPB_VARINT_DECODER_H_ */
|
