1 /******************************************************************************
2 * LibGHT, software to manage point clouds.
3 * LibGHT is free and open source software provided by the Government of Canada
4 * Copyright (c) 2012 Natural Resources Canada
5 * Copyright (c) 2011 Lyo Kato <lyo.kato@gmail.com>
6 *
7 ******************************************************************************/
8
9 #include "ght_internal.h"
10 #include <ctype.h>
11
12 #define MAX_HASH_LENGTH 22
13
14 #define REFINE_RANGE(range, bits, offset) \
15 if (((bits) & (offset)) == (offset)) \
16 (range)->min = ((range)->max + (range)->min) / 2.0; \
17 else \
18 (range)->max = ((range)->max + (range)->min) / 2.0;
19
20 #define SET_BIT(bits, mid, range, value, offset) \
21 mid = ((range)->max + (range)->min) / 2.0; \
22 if ((value) >= mid) { \
23 (range)->min = mid; \
24 (bits) |= (0x1 << (offset)); \
25 } else { \
26 (range)->max = mid; \
27 (bits) |= (0x0 << (offset)); \
28 }
29
30 static const char BASE32_ENCODE_TABLE[33] = "0123456789bcdefghjkmnpqrstuvwxyz";
31 static const char BASE32_DECODE_TABLE[44] =
32 {
33 /* 0 */ 0, /* 1 */ 1, /* 2 */ 2, /* 3 */ 3, /* 4 */ 4,
34 /* 5 */ 5, /* 6 */ 6, /* 7 */ 7, /* 8 */ 8, /* 9 */ 9,
35 /* : */ -1, /* ; */ -1, /* < */ -1, /* = */ -1, /* > */ -1,
36 /* ? */ -1, /* @ */ -1, /* A */ -1, /* B */ 10, /* C */ 11,
37 /* D */ 12, /* E */ 13, /* F */ 14, /* G */ 15, /* H */ 16,
38 /* I */ -1, /* J */ 17, /* K */ 18, /* L */ -1, /* M */ 19,
39 /* N */ 20, /* O */ -1, /* P */ 21, /* Q */ 22, /* R */ 23,
40 /* S */ 24, /* T */ 25, /* U */ 26, /* V */ 27, /* W */ 28,
41 /* X */ 29, /* Y */ 30, /* Z */ 31
42 };
43
44 static const char NEIGHBORS_TABLE[8][33] =
45 {
46 "p0r21436x8zb9dcf5h7kjnmqesgutwvy", /* NORTH EVEN */
47 "bc01fg45238967deuvhjyznpkmstqrwx", /* NORTH ODD */
48 "bc01fg45238967deuvhjyznpkmstqrwx", /* EAST EVEN */
49 "p0r21436x8zb9dcf5h7kjnmqesgutwvy", /* EAST ODD */
50 "238967debc01fg45kmstqrwxuvhjyznp", /* WEST EVEN */
51 "14365h7k9dcfesgujnmqp0r2twvyx8zb", /* WEST ODD */
52 "14365h7k9dcfesgujnmqp0r2twvyx8zb", /* SOUTH EVEN */
53 "238967debc01fg45kmstqrwxuvhjyznp" /* SOUTH ODD */
54 };
55
56 static const char BORDERS_TABLE[8][9] =
57 {
58 "prxz", /* NORTH EVEN */
59 "bcfguvyz", /* NORTH ODD */
60 "bcfguvyz", /* EAST EVEN */
61 "prxz", /* EAST ODD */
62 "0145hjnp", /* WEST EVEN */
63 "028b", /* WEST ODD */
64 "028b", /* SOUTH EVEN */
65 "0145hjnp" /* SOUTH ODD */
66 };
67
68 GhtErr
ght_hash_clone(const GhtHash * hash,GhtHash ** hash_new)69 ght_hash_clone(const GhtHash *hash, GhtHash **hash_new)
70 {
71 size_t sz;
72 if ( ! hash )
73 {
74 *hash_new = NULL;
75 return GHT_OK;
76 }
77 sz = strlen(hash) + 1;
78 *hash_new = ght_malloc(sz);
79 memcpy(*hash_new, hash, sz);
80 return GHT_OK;
81 }
82
83 GhtErr
ght_hash_from_coordinate(const GhtCoordinate * coord,unsigned int resolution,GhtHash ** hash)84 ght_hash_from_coordinate(const GhtCoordinate *coord, unsigned int resolution, GhtHash **hash)
85 {
86 int i;
87 GhtHash *geohash;
88 unsigned char bits = 0;
89 double lon = coord->x;
90 double lat = coord->y;
91 double mid;
92 GhtRange lat_range = { -90, 90 };
93 GhtRange lon_range = { -180, 180 };
94
95 double val1, val2, val_tmp;
96 GhtRange *range1, *range2, *range_tmp;
97
98 assert(resolution <= MAX_HASH_LENGTH);
99
100 if ( lat < -90 || lat > 90 || lon < -180 || lon > 180 )
101 {
102 ght_error("%s: coordinate values (%g, %g) out of range (-180/180,-90/90)", __func__, lon, lat);
103 return GHT_ERROR;
104 }
105
106 geohash = ght_malloc(resolution+1);
107
108 if (geohash == NULL)
109 return GHT_ERROR;
110
111 val1 = lon;
112 range1 = &lon_range;
113 val2 = lat;
114 range2 = &lat_range;
115
116 for (i=0; i < resolution; i++)
117 {
118 bits = 0;
119 SET_BIT(bits, mid, range1, val1, 4);
120 SET_BIT(bits, mid, range2, val2, 3);
121 SET_BIT(bits, mid, range1, val1, 2);
122 SET_BIT(bits, mid, range2, val2, 1);
123 SET_BIT(bits, mid, range1, val1, 0);
124
125 geohash[i] = BASE32_ENCODE_TABLE[bits];
126
127 val_tmp = val1;
128 val1 = val2;
129 val2 = val_tmp;
130 range_tmp = range1;
131 range1 = range2;
132 range2 = range_tmp;
133 }
134
135 geohash[resolution] = '\0';
136 *hash = geohash;
137
138 return GHT_OK;
139 }
140
141 GhtErr
ght_coordinate_from_hash(const GhtHash * hash,GhtCoordinate * coord)142 ght_coordinate_from_hash(const GhtHash *hash, GhtCoordinate *coord)
143 {
144 GhtArea area;
145 GHT_TRY(ght_area_from_hash(hash, &area));
146 coord->x = (area.x.min + area.x.max)/2.0;
147 coord->y = (area.y.min + area.y.max)/2.0;
148 return GHT_OK;
149 }
150
151 GhtErr
ght_area_from_hash(const GhtHash * hash,GhtArea * area)152 ght_area_from_hash(const GhtHash *hash, GhtArea *area)
153 {
154
155 const char *p;
156 unsigned char c;
157 char bits;
158 GhtRange *range1, *range2, *range_tmp;
159
160 area->y.max = 90; /* latitude max */
161 area->y.min = -90; /* latitude min */
162 area->x.max = 180; /* longitude max */
163 area->x.min = -180; /* longitude min */
164
165 range1 = &(area->x);
166 range2 = &(area->y);
167
168 p = (const char*)hash;
169
170 while (*p != '\0')
171 {
172 c = toupper(*p++);
173 if (c < 0x30)
174 {
175 return GHT_ERROR;
176 }
177 c -= 0x30;
178 if (c > 43)
179 {
180 return GHT_ERROR;
181 }
182 bits = BASE32_DECODE_TABLE[c];
183 if (bits == -1)
184 {
185 return GHT_ERROR;
186 }
187
188 REFINE_RANGE(range1, bits, 0x10);
189 REFINE_RANGE(range2, bits, 0x08);
190 REFINE_RANGE(range1, bits, 0x04);
191 REFINE_RANGE(range2, bits, 0x02);
192 REFINE_RANGE(range1, bits, 0x01);
193
194 range_tmp = range1;
195 range1 = range2;
196 range2 = range_tmp;
197 }
198 return GHT_OK;
199 }
200
201 int
ght_hash_common_length(const GhtHash * a,const GhtHash * b,int max_len)202 ght_hash_common_length(const GhtHash *a, const GhtHash *b, int max_len)
203 {
204 int min_len;
205 int index = 0;
206 int a_len = strlen(a);
207 int b_len = strlen(b);
208
209 /* One of the arguments is the "magic empty hash" */
210 if ( a_len == 0 || b_len == 0 )
211 return 0;
212
213 /* First chars differ! */
214 if ( *a != *b )
215 return -1;
216
217 min_len = (a_len < b_len) ? a_len : b_len;
218
219 if ( min_len < max_len )
220 max_len = min_len;
221
222
223 while(index < max_len)
224 {
225 if ( *a != *b )
226 return index;
227
228 a++;
229 b++;
230 index++;
231 }
232 return index;
233 }
234
235 /**
236 * Takes in a potential parent hash (a), and a potential child (b).
237 * Returns pointers to the start of the sub-hashes once the
238 * common parts are stripped.
239 * Match types are:
240 * GHT_NONE, GHT_GLOBAL, GHT_SAME, GHT_CHILD, GHT_SPLIT
241 */
242 GhtErr
ght_hash_leaf_parts(const GhtHash * a,const GhtHash * b,int maxlen,GhtHashMatch * matchtype,GhtHash ** a_leaf,GhtHash ** b_leaf)243 ght_hash_leaf_parts(const GhtHash *a, const GhtHash *b, int maxlen,
244 GhtHashMatch *matchtype, GhtHash **a_leaf, GhtHash **b_leaf)
245 {
246 const GhtHash *a_start = a;
247 const GhtHash *b_start = b;
248
249 /* Initialize return values */
250 *a_leaf = (GhtHash*)a;
251 *b_leaf = (GhtHash*)b;
252
253 while( *a && *b && *a == *b && (a - a_start) < maxlen )
254 {
255 a++;
256 b++;
257 }
258
259 /* Still on the first character... */
260 if ( a == a_start )
261 {
262 /* First character is null terminator? */
263 /* First has is the empty string! The "" hash. */
264 if ( *a == 0 )
265 {
266 *matchtype = GHT_GLOBAL;
267 return GHT_OK;
268 }
269 /* First character, but different. */
270 /* The hashes don't match at all! */
271 if ( *b == 0 || (*a && *b) )
272 {
273 *matchtype = GHT_NONE;
274 return GHT_ERROR;
275 }
276 }
277 /* Past the first character... */
278 else
279 {
280 /* Both null terminators, so hashes are identical. */
281 /* "abcdefg" & "abcdefg" */
282 if ( *a == 0 && *b == 0 )
283 {
284 *matchtype = GHT_SAME;
285 return GHT_OK;
286 }
287 /* A got to null terminator, but B didn't, so B is longer. */
288 /* "abcd" & "abcdefg" become "abcd"->["efg"] */
289 else if ( *a == 0 )
290 {
291 *b_leaf = (GhtHash*)b;
292 *matchtype = GHT_CHILD;
293 return GHT_OK;
294 }
295 /* B got to null terminator but A didn't? This shouldn't happen. */
296 /* "abcdefg" & "abcd" */
297 else if ( *b == 0 )
298 {
299 *matchtype = GHT_NONE;
300 return GHT_ERROR;
301 }
302 /* A and B are both inside their respective hashes, we need to split */
303 /* the parent hash up. */
304 /* "abdefg" & "abdpqrs" become "abd"->["efg","pqrs"] */
305 else
306 {
307 *a_leaf = (GhtHash*)a;
308 *b_leaf = (GhtHash*)b;
309 *matchtype = GHT_SPLIT;
310 return GHT_OK;
311 }
312 }
313 return GHT_ERROR;
314 }
315
316 GhtErr
ght_hash_free(GhtHash * hash)317 ght_hash_free(GhtHash *hash)
318 {
319 assert(hash != NULL);
320 ght_free(hash);
321 }
322
323 GhtErr
ght_hash_write(const GhtHash * hash,GhtWriter * writer)324 ght_hash_write(const GhtHash *hash, GhtWriter *writer)
325 {
326 uint8_t hashlen = 0;
327
328 /* Only try to read length if there's something there */
329 if ( hash )
330 hashlen = strlen(hash);
331
332 /* Write the length. Write 0 if there's no hash, so we know it's missing */
333 ght_write(writer, &hashlen, 1);
334
335 /* Write the hash, omit the null terminator */
336 if ( hashlen )
337 ght_write(writer, hash, hashlen);
338
339 return GHT_OK;
340 }
341
342 GhtErr
ght_hash_read(GhtReader * reader,GhtHash ** hash)343 ght_hash_read(GhtReader *reader, GhtHash **hash)
344 {
345 uint8_t hashlen;
346 GhtHash *h = NULL;
347
348 /* Anything there? */
349 ght_read(reader, &hashlen, 1);
350
351 /* Yep, read it. */
352 if ( hashlen )
353 {
354 h = ght_malloc(hashlen+1);
355 ght_read(reader, h, hashlen);
356 h[hashlen] = '\0';
357 }
358
359 *hash = h;
360 return GHT_OK;
361 }
362