PostGIS  2.5.0beta2dev-r@@SVN_REVISION@@
cu_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) 2013 Nicklas Avén
7  *
8  * This is free software; you can redistribute and/or modify it under
9  * the terms of the GNU General Public Licence. See the COPYING file.
10  *
11  **********************************************************************/
12 
13 #include <stdio.h>
14 #include <stdlib.h>
15 #include <string.h>
16 #include "CUnit/Basic.h"
17 #include "CUnit/CUnit.h"
18 #include "liblwgeom_internal.h"
19 #include "varint.h"
20 #include "cu_tester.h"
21 
22 
23 
24 // size_t varint_u32_encode_buf(uint32_t val, uint8_t *buf);
25 // size_t varint_s32_encode_buf(int32_t val, uint8_t *buf);
26 // size_t varint_u64_encode_buf(uint64_t val, uint8_t *buf);
27 // size_t varint_s64_encode_buf(int64_t val, uint8_t *buf);
28 // int64_t varint_s64_decode(const uint8_t *the_start, const uint8_t *the_end, size_t *size);
29 // uint64_t varint_u64_decode(const uint8_t *the_start, const uint8_t *the_end, size_t *size);
30 //
31 // size_t varint_size(const uint8_t *the_start, const uint8_t *the_end);
32 //
33 
34 static void do_test_u32_varint(uint32_t nr, int expected_size, char* expected_res)
35 {
36  int size;
37  char *hex;
38  uint8_t buf[16];
39 
40  size = varint_u32_encode_buf(nr, buf);
41  if ( size != expected_size )
42  printf("Expected: %d\nObtained: %d\n", expected_size, size);
43 
44  CU_ASSERT_EQUAL(size, expected_size);
45 
46  hex = hexbytes_from_bytes(buf, size);
47  ASSERT_STRING_EQUAL(hex, expected_res);
48  lwfree(hex);
49 }
50 
51 static void do_test_s32_varint(int32_t nr,int expected_size, char* expected_res)
52 {
53  uint8_t buf[16];
54  int size;
55  char *hex;
56 
57  size = varint_s32_encode_buf(nr, buf);
58  if ( size != expected_size )
59  {
60  printf("Expected: %d\nObtained: %d\n", expected_size, size);
61  }
62  CU_ASSERT_EQUAL(size,expected_size);
63 
64  hex = hexbytes_from_bytes(buf, size);
65  ASSERT_STRING_EQUAL(hex, expected_res);
66  lwfree(hex);
67 }
68 
69 static void do_test_u64_varint(uint64_t nr,int expected_size, char* expected_res)
70 {
71  uint8_t buf[16];
72  int size;
73  char *hex;
74 
75  size = varint_u64_encode_buf(nr, buf);
76  if ( size != expected_size )
77  {
78  printf("Expected: %d\nObtained: %d\n", expected_size, size);
79  }
80  CU_ASSERT_EQUAL(size,expected_size);
81 
82  hex = hexbytes_from_bytes(buf,size);
83  ASSERT_STRING_EQUAL(hex, expected_res);
84  lwfree(hex);
85 }
86 
87 static void do_test_s64_varint(int64_t nr,int expected_size, char* expected_res)
88 {
89  uint8_t buf[16];
90  int size;
91  char *hex;
92 
93  size = varint_s64_encode_buf(nr, buf);
94  if ( size != expected_size )
95  {
96  printf("Expected: %d\nObtained: %d\n", expected_size, size);
97  }
98  CU_ASSERT_EQUAL(size,expected_size);
99 
100  hex = hexbytes_from_bytes(buf,size);
101  ASSERT_STRING_EQUAL(hex, expected_res);
102  lwfree(hex);
103 }
104 
105 static void test_varint(void)
106 {
107 
108  do_test_u64_varint(1, 1, "01");
109  do_test_u64_varint(300, 2, "AC02");
110  do_test_u64_varint(150, 2, "9601");
111  do_test_u64_varint(240, 2, "F001");
112  do_test_u64_varint(0x4000, 3, "808001");
113  /*
114  0100:0000 0000:0000 - input (0x4000)
115  1000:0000 1000:0000 0000:0001 - output (0x808001)
116  000:0000 000:0000 000:0001 - chop
117  000:0001 000:0000 000:0000 - swap
118  0:0000 0100:0000 0000:0000 - concat = input
119  */
120  do_test_u64_varint(2147483647, 5, "FFFFFFFF07");
121  /*
122  0111:1111 1111:1111 1111:1111 1111:1111 - input (0x7FFFFFFF)
123  1111:1111 1111:1111 1111:1111 1111:1111 0000:0111 - output(0xFFFFFFFF07)
124  111:1111 111:1111 111:1111 111:1111 000:0111 - chop
125  000:0111 111:1111 111:1111 111:1111 111:1111 - swap
126  0111:1111 1111:1111 1111:1111 1111:1111 - concat = input
127  | | | |
128  2^32 2^16 2^8 2^0
129  */
130  do_test_s64_varint(1, 1, "02");
131  do_test_s64_varint(-1, 1, "01");
132  do_test_s64_varint(-2, 1, "03");
133 
134  do_test_u32_varint(2147483647, 5, "FFFFFFFF07");
135  /*
136  0111:1111 1111:1111 1111:1111 1111:1111 - input (7fffffff)
137  1111:1111 1111:1111 1111:1111 1111:1111 0000:0111 - output (ffffff07)
138  111:1111 111:1111 111:1111 111:1111 000:0111 - chop
139  000:0111 111:1111 111:1111 111:1111 111:1111 - swap
140  0111:1111 1111:1111 1111:1111 1111:1111 - concat = input
141  | | | |
142  2^32 2^16 2^8 2^0
143  */
144  do_test_s32_varint(2147483647, 5, "FEFFFFFF0F");
145  /*
146  0111:1111 1111:1111 1111:1111 1111:1111 - input (7fffffff)
147  1111:1110 1111:1111 1111:1111 1111:1111 0000:1111 - output(feffffff0f)
148  1111:1111 1111:1111 1111:1111 1111:1111 0000:0111 - zigzag (ffffff07)
149  111:1111 111:1111 111:1111 111:1111 000:0111 - chop
150  000:0111 111:1111 111:1111 111:1111 111:1111 - swap
151  0111:1111 1111:1111 1111:1111 1111:1111 - concat = input
152  | | | |
153  2^32 2^16 2^8 2^0
154  */
155  do_test_s32_varint(-2147483648, 5, "FFFFFFFF0F");
156 
157  do_test_s32_varint(1, 1, "02");
158  /*
159  0000:0001 - input (01)
160  0000:0010 - A: input << 1
161  0000:0000 - B: input >> 31
162  0000:0010 - zigzag (A xor B) == output
163  */
164 
165  do_test_s32_varint(-1, 1, "01");
166  /*
167  1111:1111 ... 1111:1111 - input (FFFFFFFF)
168  1111:1111 ... 1111:1110 - A: input << 1
169  1111:1111 ... 1111:1111 - B: input >> 31
170  0000:0000 ... 0000:0001 - zigzag (A xor B) == output
171  */
172 
173 
174 }
175 
176 
177 static void do_test_u64_roundtrip(uint64_t i64_in)
178 {
179  uint8_t buffer[16];
180  uint64_t i64_out;
181  size_t size_in, size_out;
182  size_in = varint_u64_encode_buf(i64_in, buffer);
183  i64_out = varint_u64_decode(buffer, buffer + size_in, &size_out);
184  CU_ASSERT_EQUAL(i64_in, i64_out);
185  CU_ASSERT_EQUAL(size_in, size_out);
186 }
187 
188 static void do_test_s64_roundtrip(int64_t i64_in)
189 {
190  uint8_t buffer[16];
191  int64_t i64_out;
192  size_t size_in, size_out;
193  size_in = varint_s64_encode_buf(i64_in, buffer);
194  i64_out = varint_s64_decode(buffer, buffer + size_in, &size_out);
195  CU_ASSERT_EQUAL(i64_in, i64_out);
196  CU_ASSERT_EQUAL(size_in, size_out);
197 }
198 
199 static void test_varint_roundtrip(void)
200 {
201 
202  do_test_u64_roundtrip(0xFFFFFFFFFFFFFFFF);
203 
204  int i;
205  for ( i = 0; i < 1024; i += 63 )
206  {
209  do_test_s64_roundtrip(-1*i);
210  }
211 }
212 
213 static void test_zigzag(void)
214 {
215  int64_t a;
216  int32_t b;
217  int i;
218 
219  for ( i = 1; i < 1024; i += 31 )
220  {
221  a = b = i;
222  CU_ASSERT_EQUAL(a, unzigzag64(zigzag64(a)));
223  CU_ASSERT_EQUAL(b, unzigzag32(zigzag32(b)));
224 
225  a = b = -1 * i;
226  CU_ASSERT_EQUAL(a, unzigzag64(zigzag64(a)));
227  CU_ASSERT_EQUAL(b, unzigzag32(zigzag32(b)));
228  }
229 
230  //8
231  CU_ASSERT_EQUAL(-INT8_MAX, unzigzag8(zigzag8(-INT8_MAX)));
232  CU_ASSERT_EQUAL(INT8_MAX, unzigzag8(zigzag8(INT8_MAX)));
233  CU_ASSERT_EQUAL(0, unzigzag8(zigzag8(0)));
234 
235  //32
236  CU_ASSERT_EQUAL(-INT32_MAX, unzigzag32(zigzag32(-INT32_MAX)));
237  CU_ASSERT_EQUAL(INT32_MAX, unzigzag32(zigzag32(INT32_MAX)));
238  CU_ASSERT_EQUAL(0, unzigzag32(zigzag32(0)));
239 
240  //64
241  CU_ASSERT_EQUAL(-INT64_MAX, unzigzag64(zigzag64(-INT64_MAX)));
242  CU_ASSERT_EQUAL(INT64_MAX, unzigzag64(zigzag64(INT64_MAX)));
243  CU_ASSERT_EQUAL(0, unzigzag64(zigzag64(0)));
244 }
245 
246 
247 /*
248 ** Used by the test harness to register the tests in this file.
249 */
250 void varint_suite_setup(void);
252 {
253  CU_pSuite suite = CU_add_suite("varint", NULL, NULL);
254  PG_ADD_TEST(suite, test_zigzag);
255  PG_ADD_TEST(suite, test_varint);
257 }
size_t varint_u32_encode_buf(uint32_t val, uint8_t *buf)
Definition: varint.c:83
void lwfree(void *mem)
Definition: lwutil.c:244
static void do_test_u64_varint(uint64_t nr, int expected_size, char *expected_res)
Definition: cu_varint.c:69
#define ASSERT_STRING_EQUAL(o, e)
int32_t unzigzag32(uint32_t val)
Definition: varint.c:196
static void do_test_s32_varint(int32_t nr, int expected_size, char *expected_res)
Definition: cu_varint.c:51
#define INT8_MAX
Definition: lwin_wkt_lex.c:328
int64_t varint_s64_decode(const uint8_t *the_start, const uint8_t *the_end, size_t *size)
Definition: varint.c:102
unsigned int uint32_t
Definition: uthash.h:78
static void test_zigzag(void)
Definition: cu_varint.c:213
uint8_t zigzag8(int8_t val)
Definition: varint.c:182
static void do_test_u64_roundtrip(uint64_t i64_in)
Definition: cu_varint.c:177
#define INT32_MAX
Definition: lwin_wkt_lex.c:334
Datum buffer(PG_FUNCTION_ARGS)
uint64_t zigzag64(int64_t val)
Definition: varint.c:168
int64_t unzigzag64(uint64_t val)
Definition: varint.c:189
static void do_test_s64_roundtrip(int64_t i64_in)
Definition: cu_varint.c:188
#define PG_ADD_TEST(suite, testfunc)
uint32_t zigzag32(int32_t val)
Definition: varint.c:175
static void test_varint_roundtrip(void)
Definition: cu_varint.c:199
size_t varint_s32_encode_buf(int32_t val, uint8_t *buf)
Definition: varint.c:95
static void test_varint(void)
Definition: cu_varint.c:105
uint64_t varint_u64_decode(const uint8_t *the_start, const uint8_t *the_end, size_t *size)
Definition: varint.c:109
static void do_test_s64_varint(int64_t nr, int expected_size, char *expected_res)
Definition: cu_varint.c:87
char * hexbytes_from_bytes(const uint8_t *bytes, size_t size)
Definition: lwout_wkb.c:39
static void do_test_u32_varint(uint32_t nr, int expected_size, char *expected_res)
Definition: cu_varint.c:34
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
void varint_suite_setup(void)
Definition: cu_varint.c:251
unsigned char uint8_t
Definition: uthash.h:79
int8_t unzigzag8(uint8_t val)
Definition: varint.c:203