PostGIS  2.2.8dev-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  * Copyright (C) 2014 Sandro Santilli <strk@keybit.net>
7  * Copyright (C) 2013 Nicklas Avén
8  *
9  * This is free software; you can redistribute and/or modify it under
10  * the terms of the GNU General Public Licence. See the COPYING file.
11  *
12  **********************************************************************
13  *
14  * Handle varInt values, as described here:
15  * http://developers.google.com/protocol-buffers/docs/encoding#varints
16  *
17  **********************************************************************/
18 
19 #include "varint.h"
20 #include "lwgeom_log.h"
21 #include "liblwgeom.h"
22 
23 /* -------------------------------------------------------------------------------- */
24 
25 static size_t
26 _varint_u64_encode_buf(uint64_t val, uint8_t *buf)
27 {
28  uint8_t grp;
29  uint64_t q = val;
30  uint8_t *ptr = buf;
31  while (1)
32  {
33  /* We put the 7 least significant bits in grp */
34  grp = 0x7f & q;
35  /* We rightshift our input value 7 bits */
36  /* which means that the 7 next least significant bits */
37  /* becomes the 7 least significant */
38  q = q >> 7;
39  /* Check if, after our rightshifting, we still have */
40  /* anything to read in our input value. */
41  if ( q > 0 )
42  {
43  /* In the next line quite a lot is happening. */
44  /* Since there is more to read in our input value */
45  /* we signal that by setting the most siginicant bit */
46  /* in our byte to 1. */
47  /* Then we put that byte in our buffer and move the pointer */
48  /* forward one step */
49  *ptr = 0x80 | grp;
50  ptr++;
51  }
52  else
53  {
54  /* The same as above, but since there is nothing more */
55  /* to read in our input value we leave the most significant bit unset */
56  *ptr = grp;
57  ptr++;
58  return ptr - buf;
59  }
60  }
61  /* This cannot happen */
62  lwerror("%s: Got out of infinite loop. Consciousness achieved.", __func__);
63  return (size_t)0;
64 }
65 
66 
67 size_t
68 varint_u64_encode_buf(uint64_t val, uint8_t *buf)
69 {
70  return _varint_u64_encode_buf(val, buf);
71 }
72 
73 
74 size_t
75 varint_u32_encode_buf(uint32_t val, uint8_t *buf)
76 {
77  return _varint_u64_encode_buf((uint64_t)val, buf);
78 }
79 
80 size_t
81 varint_s64_encode_buf(int64_t val, uint8_t *buf)
82 {
83  return _varint_u64_encode_buf(zigzag64(val), buf);
84 }
85 
86 size_t
87 varint_s32_encode_buf(int32_t val, uint8_t *buf)
88 {
89  return _varint_u64_encode_buf((uint64_t)zigzag32(val), buf);
90 }
91 
92 /* Read from signed 64bit varint */
93 int64_t
94 varint_s64_decode(const uint8_t *the_start, const uint8_t *the_end, size_t *size)
95 {
96  return unzigzag64(varint_u64_decode(the_start, the_end, size));
97 }
98 
99 /* Read from unsigned 64bit varint */
100 uint64_t
101 varint_u64_decode(const uint8_t *the_start, const uint8_t *the_end, size_t *size)
102 {
103  uint64_t nVal = 0;
104  int nShift = 0;
105  uint8_t nByte;
106  const uint8_t *ptr = the_start;
107 
108  /* Check so we don't read beyond the twkb */
109  while( ptr < the_end )
110  {
111  nByte = *ptr;
112  /* Hibit is set, so this isn't the last byte */
113  if (nByte & 0x80)
114  {
115  /* We get here when there is more to read in the input varInt */
116  /* Here we take the least significant 7 bits of the read */
117  /* byte and put it in the most significant place in the result variable. */
118  nVal |= ((uint64_t)(nByte & 0x7f)) << nShift;
119  /* move the "cursor" of the input buffer step (8 bits) */
120  ptr++;
121  /* move the cursor in the resulting variable (7 bits) */
122  nShift += 7;
123  }
124  else
125  {
126  /* move the "cursor" one step */
127  ptr++;
128  /* Move the last read byte to the most significant */
129  /* place in the result and return the whole result */
130  *size = ptr - the_start;
131  return nVal | ((uint64_t)nByte << nShift);
132  }
133  }
134  lwerror("%s: varint extends past end of buffer", __func__);
135  return 0;
136 }
137 
138 size_t
139 varint_size(const uint8_t *the_start, const uint8_t *the_end)
140 {
141  const uint8_t *ptr = the_start;
142 
143  /* Check so we don't read beyond the twkb */
144  while( ptr < the_end )
145  {
146  /* Hibit is set, this isn't the last byte */
147  if (*ptr & 0x80)
148  {
149  ptr++;
150  }
151  else
152  {
153  ptr++;
154  return ptr - the_start;
155  }
156  }
157  return 0;
158 }
159 
160 uint64_t zigzag64(int64_t val)
161 {
162  return val >= 0 ?
163  ((uint64_t)val) << 1 :
164  ((((uint64_t)(-1 - val)) << 1) | 0x01);
165 }
166 
167 uint32_t zigzag32(int32_t val)
168 {
169  return val >= 0 ?
170  ((uint32_t)val) << 1 :
171  ((((uint32_t)(-1 - val)) << 1) | 0x01);
172 }
173 
174 uint8_t zigzag8(int8_t val)
175 {
176  return val >= 0 ?
177  ((uint8_t)val) << 1 :
178  ((((uint8_t)(-1 - val)) << 1) | 0x01);
179 }
180 
181 int64_t unzigzag64(uint64_t val)
182 {
183  return !(val & 0x01) ?
184  ((int64_t)(val >> 1)) :
185  (-1 * (int64_t)((val+1) >> 1));
186 }
187 
188 int32_t unzigzag32(uint32_t val)
189 {
190  return !(val & 0x01) ?
191  ((int32_t)(val >> 1)) :
192  (-1 * (int32_t)((val+1) >> 1));
193 }
194 
195 int8_t unzigzag8(uint8_t val)
196 {
197  return !(val & 0x01) ?
198  ((int8_t)(val >> 1)) :
199  (-1 * (int8_t)((val+1) >> 1));
200 }
size_t varint_u32_encode_buf(uint32_t val, uint8_t *buf)
Definition: varint.c:75
int32_t unzigzag32(uint32_t val)
Definition: varint.c:188
size_t varint_size(const uint8_t *the_start, const uint8_t *the_end)
Definition: varint.c:139
int64_t varint_s64_decode(const uint8_t *the_start, const uint8_t *the_end, size_t *size)
Definition: varint.c:94
static size_t _varint_u64_encode_buf(uint64_t val, uint8_t *buf)
Definition: varint.c:26
uint8_t zigzag8(int8_t val)
Definition: varint.c:174
uint64_t zigzag64(int64_t val)
Definition: varint.c:160
int64_t unzigzag64(uint64_t val)
Definition: varint.c:181
uint32_t zigzag32(int32_t val)
Definition: varint.c:167
size_t varint_s32_encode_buf(int32_t val, uint8_t *buf)
Definition: varint.c:87
uint64_t varint_u64_decode(const uint8_t *the_start, const uint8_t *the_end, size_t *size)
Definition: varint.c:101
size_t varint_u64_encode_buf(uint64_t val, uint8_t *buf)
Definition: varint.c:68
size_t varint_s64_encode_buf(int64_t val, uint8_t *buf)
Definition: varint.c:81
void lwerror(const char *fmt,...)
Write a notice out to the error handler.
Definition: lwutil.c:74
This library is the generic geometry handling section of PostGIS.
int8_t unzigzag8(uint8_t val)
Definition: varint.c:195