Debian Codegraph @

xs/geohash.xs

raw
1 #include "EXTERN.h"
2 #include "perl.h"
3 #include "XSUB.h"
4 #define NEED_sv_2pv_flags_GLOBAL
5 #include "ppport.h"
6 #include <math.h>
7 #include "xshelper.h"
8
9 static char PIECES[32] = {
10 '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
11 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'j', 'k', 'm',
12 'n', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z',
13 };
14
15 STATIC_INLINE
16 void
17 encode(char *buf, STRLEN precision, NV lat, NV lon) {
18 IV which = 0;
19 STRLEN count = 0;
20 NV
21 lat_min = -90,
22 lat_max = 90,
23 lon_min = -180,
24 lon_max = 180
25 ;
26
27 while ( count < precision ) {
28 IV i;
29 IV bits = 0;
30 for( i = 0; i < 5; i++ ) {
31 IV bit;
32 if (which) {
33 NV mid = (lat_max + lat_min) / 2;
34 bit = lat >= mid ? 1 : 0;
35 if ( bit ) { lat_min = mid; }
36 else { lat_max = mid; }
37 } else {
38 NV mid = (lon_max + lon_min) / 2;
39 bit = lon >= mid ? 1 : 0;
40 if ( bit ) { lon_min = mid; }
41 else { lon_max = mid; }
42 }
43 bits = ( ( bits << 1 ) | bit );
44 which ^= 1;
45 }
46
47 buf[count] = PIECES[bits];
48 count++;
49 }
50
51
52 buf[count] = '\0';
53 }
54
55 STATIC_INLINE
56 void
57 decode_to_interval(char *hash, STRLEN len, NV *lat_min_out, NV *lat_max_out, NV *lon_min_out, NV *lon_max_out) {
58 STRLEN i, j;
59 IV which = 0, min_or_max;
60 NV
61 lat_min = -90,
62 lat_max = 90,
63 lon_min = -180,
64 lon_max = 180
65 ;
66 for (i = 0; i < len; i++ ) {
67 IV bits;
68 int x = (int) hash[i];
69 if (x >= 48 && x <= 57) {
70 bits = x - 48;
71 } else if ( x >= 98 && x <= 104 ) {
72 bits = x - 88;
73 } else if ( x >= 106 && x <= 107 ) {
74 bits = x - 89;
75 } else if ( x >= 109 && x <= 110 ) {
76 bits = x - 90;
77 } else if ( x >= 112 && x <= 122 ) {
78 bits = x - 91;
79 } else {
80 croak("Bad character '%c' in hash '%s'", hash[i], hash);
81 }
82
83 for (j = 0; j < 5; j++){
84 min_or_max = ( bits & 16 ) >> 4;
85 if (which) {
86 NV mid = (lat_max + lat_min ) / 2;
87 if (min_or_max) { /* max */
88 lat_min = mid;
89 } else {
90 lat_max = mid;
91 }
92 } else {
93 NV mid = (lon_max + lon_min ) / 2;
94 if (min_or_max) { /* max */
95 lon_min = mid;
96 } else {
97 lon_max = mid;
98 }
99 }
100
101 which ^= 1;
102 bits <<= 1;
103 }
104 }
105
106 *lat_min_out = lat_min;
107 *lat_max_out = lat_max;
108 *lon_min_out = lon_min;
109 *lon_max_out = lon_max;
110 }
111
112 STATIC_INLINE
113 void
114 decode(char *hash, IV len, NV *lat, NV *lon) {
115 NV lat_min = 0, lat_max = 0, lon_min = 0, lon_max = 0;
116 decode_to_interval(hash, len, &lat_min, &lat_max, &lon_min, &lon_max);
117 *lat = (lat_max + lat_min) / 2;
118 *lon = (lon_max + lon_min) / 2;
119 }
120
121 static char* NEIGHBORS[4][2] = {
122 { "bc01fg45238967deuvhjyznpkmstqrwx", "p0r21436x8zb9dcf5h7kjnmqesgutwvy" },
123 { "238967debc01fg45kmstqrwxuvhjyznp", "14365h7k9dcfesgujnmqp0r2twvyx8zb" },
124 { "p0r21436x8zb9dcf5h7kjnmqesgutwvy", "bc01fg45238967deuvhjyznpkmstqrwx" },
125 { "14365h7k9dcfesgujnmqp0r2twvyx8zb", "238967debc01fg45kmstqrwxuvhjyznp" }
126 };
127
128 static char* BORDERS[4][2] = {
129 { "bcfguvyz", "prxz" },
130 { "0145hjnp", "028b" },
131 { "prxz", "bcfguvyz" },
132 { "028b", "0145hjnp" }
133 };
134
135 #define LOG2_OF_10 3.32192809488736
136 #define LOG2_OF_180 7.49185309632967
137 #define LOG2_OF_360 8.49185309632968
138
139 STATIC_INLINE
140 IV
141 bits_for_number(char *number) {
142 for(; *number != '\0'; number++){
143 if(*number == '.'){
144 number++; /* skip dot */
145 return (IV) (strlen(number)) * LOG2_OF_10 + 1;
146 }
147 }
148 return 0;
149 }
150
151 STATIC_INLINE
152 IV
153 precision(SV *lat, SV *lon) {
154 IV lab = bits_for_number(SvPV_nolen(lat)) + 8; /* 8 > log_2(180) */
155 IV lob = bits_for_number(SvPV_nolen(lon)) + 9; /* 9 > log_2(360) */
156
157 /* Though it seems I should use ceil(), I copied the logic from Geo::Hash */
158 return (IV) ( ( ( lab > lob ? lab : lob ) + 1 ) / 2.5 );
159 }
160
161 enum GH_DIRECTION {
162 ADJ_RIGHT = 0,
163 ADJ_LEFT = 1,
164 ADJ_TOP = 2,
165 ADJ_BOTTOM = 3
166 };
167
168 /* need to free this return value! */
169 #define HASHBASE_BUFSIZ 8192
170 STATIC_INLINE
171 char *
172 adjacent(char *hash, STRLEN hashlen, enum GH_DIRECTION direction) {
173 char base[HASHBASE_BUFSIZ];
174 char last_ch = hash[ hashlen - 1 ];
175 char *pos, *ret;
176 IV type = hashlen % 2;
177 IV base_len;
178
179 if (hashlen < 1)
180 croak("PANIC: hash too short!");
181 if (hashlen > HASHBASE_BUFSIZ)
182 croak("PANIC: hash too big!");
183
184 memcpy(base, hash, hashlen - 1);
185 *(base + hashlen - 1) = '\0';
186
187 if (hashlen > 1) {
188 pos = strchr(BORDERS[direction][type], last_ch);
189 if (pos != NULL) {
190 char *tmp = adjacent(base, strlen(base), direction);
191 strcpy(base, tmp);
192 Safefree(tmp);
193 }
194 }
195 base_len = strlen(base);
196 Newxz( ret, base_len + 2, char );
197 strcpy( ret, base );
198 ret[ base_len ] = PIECES[ strchr(NEIGHBORS[direction][type], last_ch) - NEIGHBORS[direction][type] ];
199 *(ret + base_len + 1) = '\0';
200 return ret;
201 }
202
203 STATIC_INLINE
204 void
205 neighbors(char *hash, STRLEN hashlen, int around, int offset, char ***neighbors, int *nsize) {
206 char *xhash;
207 STRLEN xhashlen = hashlen;
208 int i = 1;
209
210 Newxz( xhash, hashlen + 1, char );
211 Copy( hash, xhash, hashlen, char );
212 *(xhash + hashlen) = '\0';
213
214 *nsize = ( (around + offset) * 2 + 1 ) * ( (around + offset) * 2 + 1 )
215 - (offset * 2 + 1) * (offset * 2 + 1);
216 Newxz( *neighbors, *nsize, char *);
217
218 while ( offset > 0 ) {
219 char *top = adjacent( xhash, xhashlen, ADJ_TOP );
220 char *left = adjacent( top, strlen(top), ADJ_LEFT );
221 Safefree(top);
222 Safefree(xhash);
223 xhash = left;
224 xhashlen = strlen(left);
225
226 offset--;
227 i++;
228 }
229
230 {
231 int m = 0;
232 char *tmp = xhash;
233 while (around-- > 0) {
234 int j;
235 /* going to insert this many neighbors */
236 (*neighbors)[m++] = adjacent(xhash, xhashlen, ADJ_TOP);
237
238 for ( j = 0; j < 2 * i - 1; j ++ ) {
239 xhash = (*neighbors)[m - 1];
240 xhashlen = strlen( xhash );
241 (*neighbors)[m++] = adjacent(xhash, xhashlen, ADJ_RIGHT);
242 }
243 for ( j = 0; j < 2 * i; j ++ ) {
244 xhash = (*neighbors)[m - 1];
245 xhashlen = strlen( xhash );
246 (*neighbors)[m++] = adjacent(xhash, xhashlen, ADJ_BOTTOM);
247 }
248 for ( j = 0; j < 2 * i; j ++ ) {
249 xhash = (*neighbors)[m - 1];
250 xhashlen = strlen( xhash );
251 (*neighbors)[m++] = adjacent(xhash, xhashlen, ADJ_LEFT);
252 }
253 for ( j = 0; j < 2 * i; j ++ ) {
254 xhash = (*neighbors)[m - 1];
255 xhashlen = strlen( xhash );
256 (*neighbors)[m++] = adjacent(xhash, xhashlen, ADJ_TOP);
257 }
258 i++;
259 xhash = (*neighbors)[m - 1];
260 xhashlen = strlen( xhash );
261 }
262 Safefree(tmp);
263 }
264 }
265
266 MODULE = Geo::Hash::XS PACKAGE = Geo::Hash::XS
267
268 PROTOTYPES: DISABLE
269
270 SV *
271 encode(self, lat, lon, p = 0)
272 SV *self;
273 SV *lat;
274 SV *lon;
275 IV p;
276 PREINIT:
277 char *encoded;
278 CODE:
279 if (! looks_like_number(lat) || ! looks_like_number(lon) ) {
280 croak("encode() only works on degrees, not dms values");
281 }
282
283 if (p <= 0) {
284 p = precision(lat, lon);
285 }
286 PERL_UNUSED_VAR(self);
287
288 Newxz(encoded, p + 1, char);
289 encode(encoded, p, SvNV(lat), SvNV(lon));
290
291 RETVAL = newSV(0);
292 sv_setpv( RETVAL, encoded );
293 Safefree( encoded );
294 OUTPUT:
295 RETVAL
296
297 void
298 decode_to_interval(self, hash)
299 SV *self;
300 char *hash;
301 PREINIT:
302 NV lat_min = 0, lat_max = 0, lon_min = 0, lon_max = 0;
303 STRLEN len = strlen(hash);
304 AV *lat_range = (AV *)sv_2mortal((SV *)newAV());
305 AV *lon_range = (AV *)sv_2mortal((SV *)newAV());
306 PPCODE:
307 PERL_UNUSED_VAR(self);
308 decode_to_interval(hash, len, &lat_min, &lat_max, &lon_min, &lon_max);
309
310 av_push(lat_range, newSVnv(lat_max));
311 av_push(lat_range, newSVnv(lat_min));
312 av_push(lon_range, newSVnv(lon_max));
313 av_push(lon_range, newSVnv(lon_min));
314
315 XPUSHs(sv_2mortal(newRV_inc((SV *)lat_range)));
316 XPUSHs(sv_2mortal(newRV_inc((SV *)lon_range)));
317
318 void
319 decode(self, hash)
320 SV *self;
321 char *hash;
322 PREINIT:
323 NV lat = 0, lon = 0;
324 STRLEN len = strlen(hash);
325 PPCODE:
326 PERL_UNUSED_VAR(self);
327 decode(hash, len, &lat, &lon);
328 mXPUSHn(lat);
329 mXPUSHn(lon);
330
331 IV
332 precision(self, lat, lon)
333 SV *self
334 SV *lat
335 SV *lon;
336 CODE:
337 PERL_UNUSED_VAR(self);
338 RETVAL = precision(lat, lon);
339 OUTPUT:
340 RETVAL
341
342 SV *
343 adjacent(self, hash, direction)
344 SV *self;
345 char *hash;
346 int direction;
347 PREINIT:
348 char *adj;
349 CODE:
350 PERL_UNUSED_VAR(self);
351 adj = adjacent(hash, strlen(hash), direction);
352
353 RETVAL = newSV(0);
354 sv_setpv(RETVAL, adj);
355 Safefree(adj);
356 OUTPUT:
357 RETVAL
358
359 void
360 neighbors(self, hash, around = 1, offset = 0)
361 SV *self;
362 char *hash;
363 int around;
364 int offset;
365 PREINIT:
366 int i;
367 int nsize;
368 char **list;
369 PPCODE:
370 PERL_UNUSED_VAR(self);
371 neighbors(hash, strlen(hash), around, offset, &list, &nsize);
372
373 for( i = 0; i < nsize; i++ ) {
374 mXPUSHp( list[i], strlen(list[i]) );
375 }
376 for( i = 0; i < nsize; i++ ) {
377 Safefree(list[i]);
378 }
379 Safefree(list);
380
381 IV
382 _constant()
383 ALIAS:
384 ADJ_TOP = ADJ_TOP
385 ADJ_RIGHT = ADJ_RIGHT
386 ADJ_LEFT = ADJ_LEFT
387 ADJ_BOTTOM = ADJ_BOTTOM
388 CODE:
389 RETVAL = ix;
390 OUTPUT:
391 RETVAL
392