1 /**********************************************************************
2 *
3 * PostGIS - Spatial Types for PostgreSQL
4 * http://postgis.net
5 *
6 * PostGIS is free software: you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation, either version 2 of the License, or
9 * (at your option) any later version.
10 *
11 * PostGIS is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with PostGIS. If not, see <http://www.gnu.org/licenses/>.
18 *
19 **********************************************************************
20 *
21 * Copyright (C) 2014 Sandro Santilli <strk@kbt.io>
22 * Copyright (C) 2013 Nicklas Avén
23 *
24 **********************************************************************/
25
26
27 #include "varint.h"
28 #include "lwgeom_log.h"
29 #include "liblwgeom.h"
30
31 /* -------------------------------------------------------------------------------- */
32
33 static size_t
_varint_u64_encode_buf(uint64_t val,uint8_t * buf)34 _varint_u64_encode_buf(uint64_t val, uint8_t *buf)
35 {
36 uint8_t grp;
37 uint64_t q = val;
38 uint8_t *ptr = buf;
39 while (1)
40 {
41 /* We put the 7 least significant bits in grp */
42 grp = 0x7f & q;
43 /* We rightshift our input value 7 bits */
44 /* which means that the 7 next least significant bits */
45 /* becomes the 7 least significant */
46 q = q >> 7;
47 /* Check if, after our rightshifting, we still have */
48 /* anything to read in our input value. */
49 if ( q > 0 )
50 {
51 /* In the next line quite a lot is happening. */
52 /* Since there is more to read in our input value */
53 /* we signal that by setting the most significant bit */
54 /* in our byte to 1. */
55 /* Then we put that byte in our buffer and move the pointer */
56 /* forward one step */
57 *ptr = 0x80 | grp;
58 ptr++;
59 }
60 else
61 {
62 /* The same as above, but since there is nothing more */
63 /* to read in our input value we leave the most significant bit unset */
64 *ptr = grp;
65 ptr++;
66 return ptr - buf;
67 }
68 }
69 /* This cannot happen */
70 lwerror("%s: Got out of infinite loop. Consciousness achieved.", __func__);
71 return (size_t)0;
72 }
73
74
75 size_t
varint_u64_encode_buf(uint64_t val,uint8_t * buf)76 varint_u64_encode_buf(uint64_t val, uint8_t *buf)
77 {
78 return _varint_u64_encode_buf(val, buf);
79 }
80
81
82 size_t
varint_u32_encode_buf(uint32_t val,uint8_t * buf)83 varint_u32_encode_buf(uint32_t val, uint8_t *buf)
84 {
85 return _varint_u64_encode_buf((uint64_t)val, buf);
86 }
87
88 size_t
varint_s64_encode_buf(int64_t val,uint8_t * buf)89 varint_s64_encode_buf(int64_t val, uint8_t *buf)
90 {
91 return _varint_u64_encode_buf(zigzag64(val), buf);
92 }
93
94 size_t
varint_s32_encode_buf(int32_t val,uint8_t * buf)95 varint_s32_encode_buf(int32_t val, uint8_t *buf)
96 {
97 return _varint_u64_encode_buf((uint64_t)zigzag32(val), buf);
98 }
99
100 /* Read from signed 64bit varint */
101 int64_t
varint_s64_decode(const uint8_t * the_start,const uint8_t * the_end,size_t * size)102 varint_s64_decode(const uint8_t *the_start, const uint8_t *the_end, size_t *size)
103 {
104 return unzigzag64(varint_u64_decode(the_start, the_end, size));
105 }
106
107 /* Read from unsigned 64bit varint */
108 uint64_t
varint_u64_decode(const uint8_t * the_start,const uint8_t * the_end,size_t * size)109 varint_u64_decode(const uint8_t *the_start, const uint8_t *the_end, size_t *size)
110 {
111 uint64_t nVal = 0;
112 int nShift = 0;
113 uint8_t nByte;
114 const uint8_t *ptr = the_start;
115
116 /* Check so we don't read beyond the twkb */
117 while( ptr < the_end )
118 {
119 nByte = *ptr;
120 /* Hibit is set, so this isn't the last byte */
121 if (nByte & 0x80)
122 {
123 /* We get here when there is more to read in the input varInt */
124 /* Here we take the least significant 7 bits of the read */
125 /* byte and put it in the most significant place in the result variable. */
126 nVal |= ((uint64_t)(nByte & 0x7f)) << nShift;
127 /* move the "cursor" of the input buffer step (8 bits) */
128 ptr++;
129 /* move the cursor in the resulting variable (7 bits) */
130 nShift += 7;
131 }
132 else
133 {
134 /* move the "cursor" one step */
135 ptr++;
136 /* Move the last read byte to the most significant */
137 /* place in the result and return the whole result */
138 *size = ptr - the_start;
139 return nVal | ((uint64_t)nByte << nShift);
140 }
141 }
142 lwerror("%s: varint extends past end of buffer", __func__);
143 return 0;
144 }
145
146 size_t
varint_size(const uint8_t * the_start,const uint8_t * the_end)147 varint_size(const uint8_t *the_start, const uint8_t *the_end)
148 {
149 const uint8_t *ptr = the_start;
150
151 /* Check so we don't read beyond the twkb */
152 while( ptr < the_end )
153 {
154 /* Hibit is set, this isn't the last byte */
155 if (*ptr & 0x80)
156 {
157 ptr++;
158 }
159 else
160 {
161 ptr++;
162 return ptr - the_start;
163 }
164 }
165 return 0;
166 }
167
zigzag64(int64_t val)168 uint64_t zigzag64(int64_t val)
169 {
170 return val >= 0 ?
171 ((uint64_t)val) << 1 :
172 ((((uint64_t)(-1 - val)) << 1) | 0x01);
173 }
174
zigzag32(int32_t val)175 uint32_t zigzag32(int32_t val)
176 {
177 return val >= 0 ?
178 ((uint32_t)val) << 1 :
179 ((((uint32_t)(-1 - val)) << 1) | 0x01);
180 }
181
zigzag8(int8_t val)182 uint8_t zigzag8(int8_t val)
183 {
184 return val >= 0 ?
185 ((uint8_t)val) << 1 :
186 ((((uint8_t)(-1 - val)) << 1) | 0x01);
187 }
188
unzigzag64(uint64_t val)189 int64_t unzigzag64(uint64_t val)
190 {
191 return !(val & 0x01) ?
192 ((int64_t)(val >> 1)) :
193 (-1 * (int64_t)((val+1) >> 1));
194 }
195
unzigzag32(uint32_t val)196 int32_t unzigzag32(uint32_t val)
197 {
198 return !(val & 0x01) ?
199 ((int32_t)(val >> 1)) :
200 (-1 * (int32_t)((val+1) >> 1));
201 }
202
unzigzag8(uint8_t val)203 int8_t unzigzag8(uint8_t val)
204 {
205 return !(val & 0x01) ?
206 ((int8_t)(val >> 1)) :
207 (-1 * (int8_t)((val+1) >> 1));
208 }
209
210
211