PostGIS  2.5.0dev-r@@SVN_REVISION@@
varint.c
Go to the documentation of this file.
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
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
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
84 {
85  return _varint_u64_encode_buf((uint64_t)val, buf);
86 }
87 
88 size_t
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
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
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
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
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 
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 
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 
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 
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 
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 
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 
size_t varint_u32_encode_buf(uint32_t val, uint8_t *buf)
Definition: varint.c:83
int32_t unzigzag32(uint32_t val)
Definition: varint.c:196
size_t varint_size(const uint8_t *the_start, const uint8_t *the_end)
Definition: varint.c:147
int64_t varint_s64_decode(const uint8_t *the_start, const uint8_t *the_end, size_t *size)
Definition: varint.c:102
static size_t _varint_u64_encode_buf(uint64_t val, uint8_t *buf)
Definition: varint.c:34
unsigned int uint32_t
Definition: uthash.h:78
uint8_t zigzag8(int8_t val)
Definition: varint.c:182
uint64_t zigzag64(int64_t val)
Definition: varint.c:168
int64_t unzigzag64(uint64_t val)
Definition: varint.c:189
uint32_t zigzag32(int32_t val)
Definition: varint.c:175
size_t varint_s32_encode_buf(int32_t val, uint8_t *buf)
Definition: varint.c:95
uint64_t varint_u64_decode(const uint8_t *the_start, const uint8_t *the_end, size_t *size)
Definition: varint.c:109
size_t varint_u64_encode_buf(uint64_t val, uint8_t *buf)
Definition: varint.c:76
size_t varint_s64_encode_buf(int64_t val, uint8_t *buf)
Definition: varint.c:89
unsigned char uint8_t
Definition: uthash.h:79
void lwerror(const char *fmt,...)
Write a notice out to the error handler.
Definition: lwutil.c:190
This library is the generic geometry handling section of PostGIS.
int8_t unzigzag8(uint8_t val)
Definition: varint.c:203