geohash.c

#include <stdio.h>

#define EVEN(x) ((x % 2) == 0)

static char *base32_encoder = "0123456789bcdefghjkmnpqrstuvwxyz";

typedef struct {
        double current_guess;
        double error_margin;
} Guess;

/** Returns 0 if real_value is less than current_guess, 1 if greater. */
int guess_next_bit(Guess *g, double real_value) {
        g->error_margin = g->error_margin/2;
        if (real_value < g->current_guess) {
                g->current_guess -= g->error_margin;
                return 0;
        }
        g->current_guess += g->error_margin;
        return 1;
}

void geohash_encode(double lat, double lon, char buf[], int len) {
        int i;
        Guess lat_guess = {0, 90};
        Guess lon_guess = {0, 180};

        for (i = 0; i < len; i++) {
                int bits = 0;
                int j;
                for (j = 0; j < 5; j++) {
                        int bit_position = i * 5 + j;
                        Guess *g;
                        double *d;
                        if (EVEN(bit_position)) {
                                g = &lon_guess;
                                d = &lon;
                        } else {
                                g = &lat_guess;
                                d = &lat;
                        }
                        int bit = guess_next_bit(g, *d);
                        bits |= bit << (4-j);
                }
                buf[i] = base32_encoder[bits];
        }
        buf[i] = '\0';
}

int main(void) {
        char hash[51];

        geohash_encode(42.6, -5.6, hash, 22);
        printf("%s\n", hash);

        return 0;
}