1 /*
2 * librdkafka - The Apache Kafka C/C++ library
3 *
4 * Copyright (c) 2016 Magnus Edenhill
5 * All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions are met:
9 *
10 * 1. Redistributions of source code must retain the above copyright notice,
11 * this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright notice,
13 * this list of conditions and the following disclaimer in the documentation
14 * and/or other materials provided with the distribution.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
26 * POSSIBILITY OF SUCH DAMAGE.
27 */
28
29
30 #ifndef _RDVARINT_H
31 #define _RDVARINT_H
32
33 #include "rd.h"
34 #include "rdbuf.h"
35
36 /**
37 * @name signed varint zig-zag encoder/decoder
38 * @{
39 *
40 */
41
42 /**
43 * @brief unsigned-varint encodes unsigned integer \p num into buffer
44 * at \p dst of size \p dstsize.
45 * @returns the number of bytes written to \p dst, or 0 if not enough space.
46 */
47
48 static RD_INLINE RD_UNUSED
rd_uvarint_enc_u64(char * dst,size_t dstsize,uint64_t num)49 size_t rd_uvarint_enc_u64 (char *dst, size_t dstsize, uint64_t num) {
50 size_t of = 0;
51
52 do {
53 if (unlikely(of >= dstsize))
54 return 0; /* Not enough space */
55
56 dst[of++] = (num & 0x7f) | (num > 0x7f ? 0x80 : 0);
57 num >>= 7;
58 } while (num);
59
60 return of;
61 }
62
63 /**
64 * @brief encodes a signed integer using zig-zag encoding.
65 * @sa rd_uvarint_enc_u64
66 */
67 static RD_INLINE RD_UNUSED
rd_uvarint_enc_i64(char * dst,size_t dstsize,int64_t num)68 size_t rd_uvarint_enc_i64 (char *dst, size_t dstsize, int64_t num) {
69 return rd_uvarint_enc_u64(dst, dstsize, (num << 1) ^ (num >> 63));
70 }
71
72
73 static RD_INLINE RD_UNUSED
rd_uvarint_enc_i32(char * dst,size_t dstsize,int32_t num)74 size_t rd_uvarint_enc_i32 (char *dst, size_t dstsize, int32_t num) {
75 return rd_uvarint_enc_i64(dst, dstsize, num);
76 }
77
78
79
80 /**
81 * @brief Use on return value from rd_uvarint_dec() to check if
82 * decoded varint fit the size_t.
83 *
84 * @returns 1 on overflow, else 0.
85 */
86 #define RD_UVARINT_OVERFLOW(DEC_RETVAL) (DEC_RETVAL > SIZE_MAX)
87
88 /**
89 * @returns 1 if there were not enough bytes to decode the varint, else 0.
90 */
91 #define RD_UVARINT_UNDERFLOW(DEC_RETVAL) (DEC_RETVAL == 0)
92
93
94 /**
95 * @param DEC_RETVAL the return value from \c rd_uvarint_dec()
96 * @returns 1 if varint decoding failed, else 0.
97 * @warning \p DEC_RETVAL will be evaluated twice.
98 */
99 #define RD_UVARINT_DEC_FAILED(DEC_RETVAL) \
100 (RD_UVARINT_UNDERFLOW(DEC_RETVAL) || RD_UVARINT_OVERFLOW(DEC_RETVAL))
101
102
103 /**
104 * @brief Decodes the unsigned-varint in buffer \p src of size \p srcsize
105 * and stores the decoded unsigned integer in \p nump.
106 *
107 * @remark Use RD_UVARINT_OVERFLOW(returnvalue) to check if the varint
108 * could not fit \p nump, and RD_UVARINT_UNDERFLOW(returnvalue) to
109 * check if there were not enough bytes available in \p src to
110 * decode the full varint.
111 *
112 * @returns the number of bytes read from \p src.
113 */
114 static RD_INLINE RD_UNUSED
rd_uvarint_dec(const char * src,size_t srcsize,uint64_t * nump)115 size_t rd_uvarint_dec (const char *src, size_t srcsize, uint64_t *nump) {
116 size_t of = 0;
117 uint64_t num = 0;
118 int shift = 0;
119
120 do {
121 if (unlikely(srcsize-- == 0))
122 return 0; /* Underflow */
123 num |= (uint64_t)(src[(int)of] & 0x7f) << shift;
124 shift += 7;
125 } while (src[(int)of++] & 0x80);
126
127 *nump = num;
128 return of;
129 }
130
131 static RD_INLINE RD_UNUSED
rd_varint_dec_i64(const char * src,size_t srcsize,int64_t * nump)132 size_t rd_varint_dec_i64 (const char *src, size_t srcsize, int64_t *nump) {
133 uint64_t n;
134 size_t r;
135
136 r = rd_uvarint_dec(src, srcsize, &n);
137 if (likely(!RD_UVARINT_DEC_FAILED(r)))
138 *nump = (int64_t)(n >> 1) ^ -(int64_t)(n & 1);
139
140 return r;
141 }
142
143
144 /**
145 * @returns the maximum encoded size for a type
146 */
147 #define RD_UVARINT_ENC_SIZEOF(TYPE) \
148 (sizeof(TYPE) + 1 + (sizeof(TYPE)/7))
149
150 /**
151 * @returns the encoding size of the value 0
152 */
153 #define RD_UVARINT_ENC_SIZE_0() ((size_t)1)
154
155
156 int unittest_rdvarint (void);
157
158 /**@}*/
159
160
161 #endif /* _RDVARINT_H */
162