mapcoder.c

/*
 * Copyright (C) 2014-2015 Stichting Mapcode Foundation (http://www.mapcode.com)
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *    http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#include <string.h> // strlen strcpy strcat memcpy memmove strstr strchr memcmp
#include <stdlib.h> // atof
#include <ctype.h>  // toupper
#include <math.h>   // floor
#include "mapcoder.h"
#include "basics.h"
#include "mapcode_fastalpha.h"

// If you do not want to use the fast encoding from mapcode_fast_encode.h, define NO_FAST_ENCODE on the
// command-line of your compiler (or uncomment the following line).
// #define NO_FAST_ENCODE

#ifndef NO_FAST_ENCODE

#include "mapcode_fast_encode.h"

#endif

#define isNameless(m)        (mminfo[m].flags & 64)
#define isRestricted(m)      (mminfo[m].flags & 512)
#define isSpecialShape22(m)  (mminfo[m].flags & 1024)
#define recType(m)           ((mminfo[m].flags >> 7) & 3)
#define smartDiv(m)          (mminfo[m].flags >> 16)
#define headerLetter(m)      (encode_chars[(mminfo[m].flags >> 11) & 31])
#define boundaries(m)        (&mminfo[m])

#define TOKENSEP   0
#define TOKENDOT   1
#define TOKENCHR   2
#define TOKENVOWEL 3
#define TOKENZERO  4
#define TOKENHYPH  5

#define STATE_ERR -1
#define STATE_PRT -9
#define STATE_GO  31

#define USIZE 256

#define MATH_PI 3.14159265358979323846

// Radius of Earth.
#define EARTH_RADIUS_X_METERS 6378137
#define EARTH_RADIUS_Y_METERS 6356752

// Circumference of Earth.
#define EARTH_CIRCUMFERENCE_X (EARTH_RADIUS_X_METERS * 2 * MATH_PI)
#define EARTH_CIRCUMFERENCE_Y (EARTH_RADIUS_Y_METERS * 2 * MATH_PI)

// Meters per degree latitude is fixed. For longitude: use factor * cos(midpoint of two degree latitudes).
#define METERS_PER_DEGREE_LAT (EARTH_CIRCUMFERENCE_Y / 360.0)
#define METERS_PER_DEGREE_LON (EARTH_CIRCUMFERENCE_X / 360.0)

#define PARENT_LETTER(ccode) ((int) parentletter[ccode])

// Legacy buffers: NOT threadsafe!
static char legacy_asciiBuffer[MAX_MAPCODE_RESULT_LEN];
static UWORD legacy_utf16Buffer[MAX_MAPCODE_RESULT_LEN];
static int debugStopAt = -1; // to externally test-restrict internal encoding, do not use!


typedef mminforec Boundaries;

static signed char decodeChar(char ch) {
    return decode_chars[(unsigned char) ch];   // ch can be negative, must be fit to range 0-255.
}

///////////////////////////////////////////////////////////////////////////////////////////////
//
//  distanceInMeters
//
///////////////////////////////////////////////////////////////////////////////////////////////

// PUBLIC - returns distance (in meters) between two coordinates (in degrees)
double distanceInMeters(double latDeg1, double lonDeg1, double latDeg2, double lonDeg2) {
    if (lonDeg1 < 0 && lonDeg2 > 1) {
        lonDeg1 += 360;
    }
    if (lonDeg2 < 0 && lonDeg1 > 1) {
        lonDeg2 += 360;
    }
    {
        const double dy = (latDeg2 - latDeg1) * METERS_PER_DEGREE_LAT;
        const double dx = (lonDeg2 - lonDeg1) * METERS_PER_DEGREE_LON * cos((latDeg1 + latDeg2) * MATH_PI / 360.0);
        return sqrt(dx * dx + dy * dy);
    }
}

///////////////////////////////////////////////////////////////////////////////////////////////
//
//  maxErrorInMeters
//
///////////////////////////////////////////////////////////////////////////////////////////////

// maximum error in meters for a certain nr of high-precision digits
static const double maxErrorInMetersForDigits[MAX_PRECISION_DIGITS + 1] = {
        7.49,
        1.39,
        0.251,
        0.0462,
        0.00837,
        0.00154,
        0.00028,
        0.000052,
        0.0000093
};

// PUBLIC - returns maximum error in meters for a certain nr of high-precision digits
double maxErrorInMeters(int extraDigits) {
    if ((extraDigits < 0) || (extraDigits > MAX_PRECISION_DIGITS)) {
        return (double) 0;
    }
    return maxErrorInMetersForDigits[extraDigits];
}

///////////////////////////////////////////////////////////////////////////////////////////////
//
//  point / point32
//
///////////////////////////////////////////////////////////////////////////////////////////////

typedef struct {
    int latMicroDeg; // latitude in microdegrees
    int lonMicroDeg; // longitude in microdegrees
} point32;

typedef struct { // point
    double lat;  // latitude (units depend on situation)
    double lon;  // longitude (units depend on situation)
} point;

static point32 convertFractionsToCoord32(const point *p) {
    point32 p32;
    p32.latMicroDeg = (int) floor(p->lat / 810000);
    p32.lonMicroDeg = (int) floor(p->lon / 3240000);
    return p32;
}

static point convertFractionsToDegrees(const point *p) {
    point pd;
    pd.lat = p->lat / (810000 * 1000000.0);
    pd.lon = p->lon / (3240000 * 1000000.0);
    return pd;
}

static const unsigned char DOUBLE_NAN[8] = {0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
                                            0x7F};     // NAN - See: https://en.wikipedia.org/wiki/Double-precision_floating-point_format
static const unsigned char DOUBLE_INF[8] = {0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xF0, 0x7F};     // +Infinity
static const unsigned char DOUBLE_MIN_INF[8] = {0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xF0, 0xFF}; // -Infinity

static int
convertCoordsToMicrosAndFractions(point32 *coord32, int *fracLat, int *fracLon, double latDeg, double lonDeg) {
    double frac;
    if (memcmp(&lonDeg, DOUBLE_NAN, 8) == 0 || memcmp(&lonDeg, DOUBLE_INF, 8) == 0 ||
        memcmp(&lonDeg, DOUBLE_MIN_INF, 8) == 0 ||
        memcmp(&latDeg, DOUBLE_NAN, 8) == 0) {
        return -1;
    }
    if (latDeg < -90) {
        latDeg = -90;
    } else if (latDeg > 90) {
        latDeg = 90;
    }
    latDeg += 90; // lat now [0..180]
    latDeg *= (double) 810000000000;
    frac = floor(latDeg + 0.1);
    coord32->latMicroDeg = (int) (frac / (double) 810000);
    if (fracLat) {
        frac -= ((double) coord32->latMicroDeg * (double) 810000);
        *fracLat = (int) frac;
    }
    coord32->latMicroDeg -= 90000000;

    lonDeg -= (360.0 * floor(lonDeg / 360)); // lon now in [0..360>
    lonDeg *= (double) 3240000000000;
    frac = floor(lonDeg + 0.1);
    coord32->lonMicroDeg = (int) (frac / (double) 3240000);
    if (fracLon) {
        frac -= (double) coord32->lonMicroDeg * (double) 3240000;
        *fracLon = (int) frac;
    }
    if (coord32->lonMicroDeg >= 180000000) {
        coord32->lonMicroDeg -= 360000000;
    }
    return 0;
}

///////////////////////////////////////////////////////////////////////////////////////////////
//
//  Boundaries (specified in microDegrees)
//
///////////////////////////////////////////////////////////////////////////////////////////////


// returns nonzero if x in the range minx...maxx
static int isInRange(int lonMicroDeg, const int minLonMicroDeg, const int maxLonMicroDeg) {
    if (minLonMicroDeg <= lonMicroDeg && lonMicroDeg < maxLonMicroDeg) {
        return 1;
    }
    if (lonMicroDeg < minLonMicroDeg) {
        lonMicroDeg += 360000000;
    } else {
        lonMicroDeg -= 360000000;
    } // 1.32 fix FIJI edge case
    if (minLonMicroDeg <= lonMicroDeg && lonMicroDeg < maxLonMicroDeg) {
        return 1;
    }
    return 0;
}

// returns true iff given coordinate "coord32" fits inside given Boundaries
static int fitsInsideBoundaries(const point32 *coord32, const Boundaries *b) {
    return (b->miny <= coord32->latMicroDeg &&
            coord32->latMicroDeg < b->maxy &&
            isInRange(coord32->lonMicroDeg, b->minx, b->maxx));
}

// set target Boundaries to a source extended with deltalat, deltaLon (in microDegrees)
static Boundaries *getExtendedBoundaries(Boundaries *target, const Boundaries *source,
                                         const int deltaLatMicroDeg, const int deltaLonMicroDeg) {
    target->miny = source->miny - deltaLatMicroDeg;
    target->minx = source->minx - deltaLonMicroDeg;
    target->maxy = source->maxy + deltaLatMicroDeg;
    target->maxx = source->maxx + deltaLonMicroDeg;
    return target;
}

///////////////////////////////////////////////////////////////////////////////////////////////
//
//  MapcodeZone
//
///////////////////////////////////////////////////////////////////////////////////////////////

#define MICROLAT_TO_FRACTIONS_FACTOR ((double)MAX_PRECISION_FACTOR)
#define MICROLON_TO_FRACTIONS_FACTOR (4.0 * MAX_PRECISION_FACTOR)
typedef struct {
    // latitudes in "810 billionths", range [-729 E11 .. +720 E11), is well within (-2^47 ... +2^47)
    double fminy;
    double fmaxy;
    // latitudes in "3240 billionths", range [-2916 E13 .. +2916 E13), is well within (-2^49 ... +2^49)
    double fminx;
    double fmaxx;
} MapcodeZone;

static void setFromFractions(MapcodeZone *z,
                             const double y, const double x,
                             const double yDelta, const double xDelta) {
    z->fminx = x;
    z->fmaxx = x + xDelta;
    if (yDelta < 0) {
        z->fminy = y + 1 + yDelta; // y+yDelta can NOT be represented
        z->fmaxy = y + 1;          // y CAN be represented
    } else {
        z->fminy = y;
        z->fmaxy = y + yDelta;
    }
}

static int isEmpty(const MapcodeZone *z) {
    return ((z->fmaxx <= z->fminx) || (z->fmaxy <= z->fminy));
}

static point getMidPointFractions(const MapcodeZone *z) {
    point p;
    p.lon = floor((z->fminx + z->fmaxx) / 2);
    p.lat = floor((z->fminy + z->fmaxy) / 2);
    return p;
}

static void zoneCopyFrom(MapcodeZone *target, const MapcodeZone *source) {
    target->fminy = source->fminy;
    target->fmaxy = source->fmaxy;
    target->fminx = source->fminx;
    target->fmaxx = source->fmaxx;
}

// determine the non-empty intersection zone z between a given zone and the boundaries of territory rectangle m.
// returns nonzero in case such a zone exists
static int restrictZoneTo(MapcodeZone *z, const MapcodeZone *zone, const Boundaries *b) {
    z->fminy = zone->fminy;
    z->fmaxy = zone->fmaxy;
    if (z->fminy < b->miny * MICROLAT_TO_FRACTIONS_FACTOR) {
        z->fminy = b->miny * MICROLAT_TO_FRACTIONS_FACTOR;
    }
    if (z->fmaxy > b->maxy * MICROLAT_TO_FRACTIONS_FACTOR) {
        z->fmaxy = b->maxy * MICROLAT_TO_FRACTIONS_FACTOR;
    }
    if (z->fminy < z->fmaxy) {
        double bminx = b->minx * MICROLON_TO_FRACTIONS_FACTOR;
        double bmaxx = b->maxx * MICROLON_TO_FRACTIONS_FACTOR;
        z->fminx = zone->fminx;
        z->fmaxx = zone->fmaxx;
        if (bmaxx < 0 && z->fminx > 0) {
            bminx += (360000000 * MICROLON_TO_FRACTIONS_FACTOR);
            bmaxx += (360000000 * MICROLON_TO_FRACTIONS_FACTOR);
        } else if (bminx > 0 && z->fmaxx < 0) {
            bminx -= (360000000 * MICROLON_TO_FRACTIONS_FACTOR);
            bmaxx -= (360000000 * MICROLON_TO_FRACTIONS_FACTOR);
        }
        if (z->fminx < bminx) {
            z->fminx = bminx;
        }
        if (z->fmaxx > bmaxx) {
            z->fmaxx = bmaxx;
        }
        return (z->fminx < z->fmaxx);
    }
    return 0;
}

///////////////////////////////////////////////////////////////////////////////////////////////
//
//  Data access
//
///////////////////////////////////////////////////////////////////////////////////////////////

/*** low-level data access ***/

static int firstrec(const int ccode) {
    return data_start[ccode];
}

static int lastrec(const int ccode) {
    return data_start[ccode + 1] - 1;
}

// returns parent of ccode, or -1
static int parentTerritoryOf(const int ccode) {
    if (ccode < 0 || ccode > ccode_earth) {
        return -1;
    }
    return parentnr[PARENT_LETTER(ccode)];
}

static int coDex(const int m) {
    int c = mminfo[m].flags & 31;
    return 10 * (c / 5) + ((c % 5) + 1);
}

static int xDivider4(const int miny, const int maxy) {
    if (miny >= 0) { // both above equator? then miny is closest
        return xdivider19[(miny) >> 19];
    }
    if (maxy >= 0) { // opposite sides? then equator is worst
        return xdivider19[0];
    }
    return xdivider19[(-maxy) >> 19]; // both negative, so maxy is closest to equator
}

/*** mid-level data access ***/

// returns true iff ccode is a subdivision of some other country
static int isSubdivision(const int ccode) {
    return (parentTerritoryOf(ccode) >= 0);
}

// find first territory rectangle of the same type as m
static int firstNamelessRecord(const int m, const int firstcode) {
    int i = m;
    const int codexm = coDex(m);
    while (i >= firstcode && coDex(i) == codexm && isNameless(i)) {
        i--;
    }
    return (i + 1);
}

// count all territory rectangles of the same type as m
static int countNamelessRecords(const int m, const int firstcode) {
    const int first = firstNamelessRecord(m, firstcode);
    const int codexm = coDex(m);
    int last = m;
    while (coDex(last) == codexm) {
        last++;
    }
    return (last - first);
}

static int isNearBorderOf(const point32 *coord32, const Boundaries *b) {
    int xdiv8 = xDivider4(b->miny, b->maxy) / 4; // should be /8 but there's some extra margin
    Boundaries tmp;
    return (fitsInsideBoundaries(coord32, getExtendedBoundaries(&tmp, b, +60, +xdiv8)) &&
            (!fitsInsideBoundaries(coord32, getExtendedBoundaries(&tmp, b, -60, -xdiv8))));
}

static void makeupper(char *s) {
    while (*s) {
        *s = (char) toupper(*s);
        s++;
    }
}

// returns 1 - 8, or negative if error
static int getParentNumber(const char *s, const int len) {
    const char *p = (len == 2 ? parents2 : parents3);
    const char *f;
    char country[4];
    if (s[0] == 0 || s[1] == 0) {
        return -27;
    } // solve bad args
    if (len != 2 && len != 3) {
        return -923;
    } // solve bad args
    memcpy(country, s, (size_t) len);
    country[len] = 0;
    makeupper(country);
    f = strstr(p, country);
    if (f == NULL) {
        return -23; // unknown country
    }
    return 1 + (int) ((f - p) / (len + 1));
}

///////////////////////////////////////////////////////////////////////////////////////////////
//
//  MAPCODE ALL-DIGIT PACKING/UNPACKING
//
///////////////////////////////////////////////////////////////////////////////////////////////

static void repack_if_alldigits(char *input, const int aonly) {
    char *s = input;
    int alldigits = 1; // assume all digits
    char *e;
    char *dotpos = NULL;

    for (e = s; *e != 0 && *e != '-'; e++) {
        if (*e < '0' || *e > '9') {
            if (*e == '.' && !dotpos) {
                dotpos = e;
            } else {
                alldigits = 0;
                break;
            }
        }
    }
    e--;
    s = e - 1;
    if (alldigits && dotpos &&
        s > dotpos) // e is last char, s is one before, both are beyond dot, all characters are digits
    {
        if (aonly) // v1.50 - encode only using the letter A
        {
            const int v = ((*input) - '0') * 100 + ((*s) - '0') * 10 + ((*e) - '0');
            *input = 'A';
            *s = encode_chars[v / 32];
            *e = encode_chars[v % 32];
        } else // encode using A,E,U
        {
            const int v = ((*s) - '0') * 10 + ((*e) - '0');
            *s = encode_chars[(v / 34) + 31];
            *e = encode_chars[v % 34];
        }
    }
}

// rewrite all-digit codes
// returns 1 if unpacked, 0 if left unchanged, negative if unchanged and an error was detected
static int unpack_if_alldigits(char *input) {
    char *s = input;
    char *dotpos = NULL;
    const int aonly = ((*s == 'A') || (*s == 'a'));
    if (aonly) {
        s++;
    } // v1.50
    for (; *s != 0 && s[2] != 0 && s[2] != '-'; s++) {
        if (*s == '-') {
            break;
        } else if (*s == '.' && !dotpos) {
            dotpos = s;
        } else if ((decodeChar(*s) < 0) || (decodeChar(*s) > 9)) {
            return 0;
        }  // nondigit, so stop
    }

    if (dotpos) {
        if (aonly) // v1.50 encoded only with A's
        {
            const int v = (((s[0] == 'A') || (s[0] == 'a')) ? 31 : decodeChar(s[0])) * 32 +
                          (((s[1] == 'A') || (s[1] == 'a')) ? 31 : decodeChar(s[1]));
            *input = (char) ('0' + (v / 100));
            s[0] = (char) ('0' + ((v / 10) % 10));
            s[1] = (char) ('0' + (v % 10));
            return 1;
        } // v1.50

        if ((*s == 'a') || (*s == 'e') || (*s == 'u') ||
            (*s == 'A') || (*s == 'E') || (*s == 'U')) {
            char *e = s + 1;  // s is vowel, e is lastchar

            int v = 0;
            if (*s == 'e' || *s == 'E') {
                v = 34;
            } else if (*s == 'u' || *s == 'U') {
                v = 68;
            }

            if ((*e == 'a') || (*e == 'A')) {
                v += 31;
            } else if ((*e == 'e') || (*e == 'E')) {
                v += 32;
            } else if ((*e == 'u') || (*e == 'U')) {
                v += 33;
            } else if (decodeChar(*e) < 0) {
                return -9; // invalid last character!
            } else {
                v += decodeChar(*e);
            }

            if (v < 100) {
                *s = encode_chars[(unsigned int) v / 10];
                *e = encode_chars[(unsigned int) v % 10];
            } else {
                return -31; // overflow (ending in UE or UU)
            }
            return 1;
        }
    }
    return 0; // no vowel just before end
}

///////////////////////////////////////////////////////////////////////////////////////////////
//
//  DECODING
//
///////////////////////////////////////////////////////////////////////////////////////////////

typedef struct {
    // input
    point32 coord32;
    int fraclat; // latitude fraction of microdegrees, expressed in 1 / 810,000ths
    int fraclon; // longitude fraction of microdegrees, expressed in 1 / 3,240,000ths
    // output
    Mapcodes *mapcodes;
} encodeRec;

// encode the high-precision extension (0-8 characters)
static void encodeExtension(char *result, const int extrax4, const int extray, const int dividerx4,
                            const int dividery, int extraDigits, const int ydirection,
                            const encodeRec *enc) // append extra characters to result for more precision
{
    if (extraDigits > 0) { // anything to do?
        char *s = result + strlen(result);
        double factorx = (double) MAX_PRECISION_FACTOR * dividerx4; // perfect integer!
        double factory = (double) MAX_PRECISION_FACTOR * dividery; // perfect integer!
        double valx = ((double) MAX_PRECISION_FACTOR * extrax4) + enc->fraclon; // perfect integer!
        double valy = ((double) MAX_PRECISION_FACTOR * extray) + (ydirection * enc->fraclat); // perfect integer!

        // protect against floating point errors
        if (valx < 0) {
            valx = 0;
        } else if (valx >= factorx) {
            valx = factorx - 1;
        }
        if (valy < 0) {
            valy = 0;
        } else if (valy >= factory) {
            valy = factory - 1;
        }

        if (extraDigits > MAX_PRECISION_DIGITS) {
            extraDigits = MAX_PRECISION_DIGITS;
        }

        *s++ = '-';

        for (;;) {
            int gx, gy;

            factorx /= 30;
            gx = (int) (valx / factorx);

            factory /= 30;
            gy = (int) (valy / factory);

            *s++ = encode_chars[(gy / 5) * 5 + (gx / 6)];
            if (--extraDigits == 0) {
                break;
            }

            *s++ = encode_chars[(gy % 5) * 6 + (gx % 6)];
            if (--extraDigits == 0) {
                break;
            }

            valx -= factorx * gx; // for next iteration
            valy -= factory * gy; // for next iteration
        }
        *s = 0; // terminate the result
    }
}

// encode 'value' into result[nrchars]
static void encodeBase31(char *result, int value, int nrchars) {
    result[nrchars] = 0; // zero-terminate!
    while (nrchars-- > 0) {
        result[nrchars] = encode_chars[value % 31];
        value /= 31;
    }
}

static void encode_triple(char *result, const int difx, const int dify) {
    if (dify < 4 * 34) // first 4(x34) rows of 6(x28) wide
    {
        *result = encode_chars[((difx / 28) + 6 * (dify / 34))];
        encodeBase31(result + 1, ((difx % 28) * 34 + (dify % 34)), 2);
    } else // bottom row
    {
        *result = encode_chars[(difx / 24) + 24];
        encodeBase31(result + 1, (difx % 24) * 40 + (dify - 136), 2);
    }
} // encode_triple

static int encodeSixWide(int x, int y, int width, int height) {
    int v;
    int D = 6;
    int col = x / 6;
    const int maxcol = (width - 4) / 6;
    if (col >= maxcol) {
        col = maxcol;
        D = width - maxcol * 6;
    }
    v = (height * 6 * col) + (height - 1 - y) * D + (x - col * 6);
    return v;
}

// *** mid-level encode routines ***

// returns *result==0 in case of error
static void encodeGrid(char *result, const encodeRec *enc, const int m, const int extraDigits,
                       const char headerLetter) {
    const Boundaries *b = boundaries(m);

    const int orgcodex = coDex(m);
    int codexm = orgcodex;
    if (codexm == 21) {
        codexm = 22;
    } else if (codexm == 14) {
        codexm = 23;
    }

    *result = 0;
    if (headerLetter) {
        result++;
    }

    { // encode
        int divx, divy;
        const int prelen = codexm / 10;
        const int postlen = codexm % 10;

        divy = smartDiv(m);
        if (divy == 1) {
            divx = xside[prelen];
            divy = yside[prelen];
        } else {
            divx = (nc[prelen] / divy);
        }

        { // grid
            const int ygridsize = (b->maxy - b->miny + divy - 1) / divy;
            const int xgridsize = (b->maxx - b->minx + divx - 1) / divx;
            int rely = enc->coord32.latMicroDeg - b->miny;
            int x = enc->coord32.lonMicroDeg;
            int relx = x - b->minx;

            if (relx < 0) {
                relx += 360000000;
                x += 360000000;
            } else if (relx >= 360000000) // 1.32 fix FIJI edge case
            {
                relx -= 360000000;
                x -= 360000000;
            }

            rely /= ygridsize;
            relx /= xgridsize;

            if (relx >= divx || rely >= divy) {
                return;
            }

            { // prefix
                int v;
                if (divx != divy && prelen > 2) {
                    v = encodeSixWide(relx, rely, divx, divy);
                } else {
                    v = relx * divy + (divy - 1 - rely);
                }
                encodeBase31(result, v, prelen);
            } // prefix

            if (prelen == 4 && divx == 961 && divy == 961) {
                const char t = result[1];
                result[1] = result[2];
                result[2] = t;
            }

            rely = b->miny + (rely * ygridsize);
            relx = b->minx + (relx * xgridsize);

            { // postfix
                const int dividery = ((ygridsize + yside[postlen] - 1) / yside[postlen]);
                const int dividerx = ((xgridsize + xside[postlen] - 1) / xside[postlen]);
                int extrax, extray;

                {
                    char *resultptr = result + prelen;


                    int difx = x - relx;
                    int dify = enc->coord32.latMicroDeg - rely;

                    *resultptr++ = '.';

                    extrax = difx % dividerx;
                    extray = dify % dividery;
                    difx /= dividerx;
                    dify /= dividery;


                    // reverse y-direction
                    dify = yside[postlen] - 1 - dify;

                    if (postlen == 3) // encode special
                    {
                        encode_triple(resultptr, difx, dify);
                    } else {
                        encodeBase31(resultptr, (difx) * yside[postlen] + dify, postlen);
                        // swap 4-int codes for readability
                        if (postlen == 4) {
                            char t = resultptr[1];
                            resultptr[1] = resultptr[2];
                            resultptr[2] = t;
                        }
                    }
                }

                if (orgcodex == 14) {
                    result[2] = result[1];
                    result[1] = '.';
                }

                encodeExtension(result, extrax << 2, extray, dividerx << 2, dividery, extraDigits, 1, enc); // grid
                if (headerLetter) {
                    result--;
                    *result = headerLetter;
                }
            } // postfix
        } // grid
    }  // encode
}

// *result==0 in case of error
static void encodeNameless(char *result, const encodeRec *enc, const int input_ctry,
                           const int extraDigits, const int m) {
    // determine how many nameless records there are (A), and which one is this (X)...
    const int A = countNamelessRecords(m, firstrec(input_ctry));
    const int X = m - firstNamelessRecord(m, firstrec(input_ctry));

    *result = 0;

    {
        const int p = 31 / A;
        const int r = 31 % A; // the first r items are p+1
        const int codexm = coDex(m);
        const int codexlen = (codexm / 10) + (codexm % 10);
        // determine side of square around centre
        int SIDE;

        int storage_offset;
        const Boundaries *b;

        int xSIDE, orgSIDE;

        if (codexm != 21 && A <= 31) {
            storage_offset = (X * p + (X < r ? X : r)) * (961 * 961);
        } else if (codexm != 21 && A < 62) {
            if (X < (62 - A)) {
                storage_offset = X * (961 * 961);
            } else {
                storage_offset = (62 - A + ((X - 62 + A) / 2)) * (961 * 961);
                if ((X + A) & 1) {
                    storage_offset += (16 * 961 * 31);
                }
            }
        } else {
            const int BASEPOWER = (codexm == 21) ? 961 * 961 : 961 * 961 * 31;
            int BASEPOWERA = (BASEPOWER / A);
            if (A == 62) {
                BASEPOWERA++;
            } else {
                BASEPOWERA = (961) * (BASEPOWERA / 961);
            }

            storage_offset = X * BASEPOWERA;
        }

        SIDE = smartDiv(m);

        b = boundaries(m);
        orgSIDE = SIDE;

        {
            int v = storage_offset;

            const int dividerx4 = xDivider4(b->miny, b->maxy); // *** note: dividerx4 is 4 times too large!
            const int xFracture = (enc->fraclon / MAX_PRECISION_FACTOR);
            const int dx = (4 * (enc->coord32.lonMicroDeg - b->minx) + xFracture) / dividerx4; // div with quarters
            const int extrax4 = (enc->coord32.lonMicroDeg - b->minx) * 4 - (dx * dividerx4); // mod with quarters

            const int dividery = 90;
            int dy = (b->maxy - enc->coord32.latMicroDeg) / dividery;
            int extray = (b->maxy - enc->coord32.latMicroDeg) % dividery;

            if (extray == 0 && enc->fraclat > 0) {
                dy--;
                extray += dividery;
            }

            if (isSpecialShape22(m)) {
                SIDE = 1 + ((b->maxy - b->miny) / 90); // new side, based purely on y-distance
                xSIDE = (orgSIDE * orgSIDE) / SIDE;
                v += encodeSixWide(dx, SIDE - 1 - dy, xSIDE, SIDE);
            } else {
                v += (dx * SIDE + dy);
            }

            encodeBase31(result, v, codexlen + 1); // nameless
            {
                int dotp = codexlen;
                if (codexm == 13) {
                    dotp--;
                }
                memmove(result + dotp, result + dotp - 1, 4);
                result[dotp - 1] = '.';
            }

            if (!isSpecialShape22(m)) {
                if (codexm == 22 && A < 62 && orgSIDE == 961) {
                    const char t = result[codexlen - 2];
                    result[codexlen - 2] = result[codexlen];
                    result[codexlen] = t;
                }
            }

            encodeExtension(result, extrax4, extray, dividerx4, dividery, extraDigits, -1, enc); // nameless

            return;

        } // in range
    }
}

// encode in m (known to fit)
static void encodeAutoHeader(char *result, const encodeRec *enc, const int m, const int extraDigits) {
    int i;
    int STORAGE_START = 0;
    int W, H, xdiv, product;
    const Boundaries *b;

    // search back to first of the group
    int firstindex = m;
    const int codexm = coDex(m);
    while (recType(firstindex - 1) > 1 && coDex(firstindex - 1) == codexm) {
        firstindex--;
    }

    i = firstindex;
    for (;;) {
        b = boundaries(i);
        // determine how many cells
        H = (b->maxy - b->miny + 89) / 90; // multiple of 10m
        xdiv = xDivider4(b->miny, b->maxy);
        W = ((b->maxx - b->minx) * 4 + (xdiv - 1)) / xdiv;

        // round up to multiples of 176*168...
        H = 176 * ((H + 176 - 1) / 176);
        W = 168 * ((W + 168 - 1) / 168);
        product = (W / 168) * (H / 176) * 961 * 31;
        if (recType(i) == 2) { // plus pipe
            const int GOODROUNDER = codexm >= 23 ? (961 * 961 * 31) : (961 * 961);
            product = ((STORAGE_START + product + GOODROUNDER - 1) / GOODROUNDER) * GOODROUNDER - STORAGE_START;
        }
        if (i == m) {
            // encode
            const int dividerx = (b->maxx - b->minx + W - 1) / W;
            const int vx = (enc->coord32.lonMicroDeg - b->minx) / dividerx;
            const int extrax = (enc->coord32.lonMicroDeg - b->minx) % dividerx;

            const int dividery = (b->maxy - b->miny + H - 1) / H;
            int vy = (b->maxy - enc->coord32.latMicroDeg) / dividery;
            int extray = (b->maxy - enc->coord32.latMicroDeg) % dividery;

            const int codexlen = (codexm / 10) + (codexm % 10);
            int value = (vx / 168) * (H / 176);

            if (extray == 0 && enc->fraclat > 0) {
                vy--;
                extray += dividery;
            }

            value += (vy / 176);

            // PIPELETTER ENCODE
            encodeBase31(result, (STORAGE_START / (961 * 31)) + value, codexlen - 2);
            result[codexlen - 2] = '.';
            encode_triple(result + codexlen - 1, vx % 168, vy % 176);

            encodeExtension(result, extrax << 2, extray, dividerx << 2, dividery, extraDigits, -1, enc); // autoheader
            return;
        }
        STORAGE_START += product;
        i++;
    }
}

static void encoderEngine(const int ccode, const encodeRec *enc, const int stop_with_one_result,
                          const int extraDigits, const int requiredEncoder, const int ccode_override) {
    int from, upto;

    if ((enc == NULL) || (ccode < 0) || (ccode > ccode_earth)) {
        return;
    } // bad arguments

    from = firstrec(ccode);
    upto = lastrec(ccode);

    if (!fitsInsideBoundaries(&enc->coord32, boundaries(upto))) {
        return;
    }

    ///////////////////////////////////////////////////////////
    // look for encoding options
    ///////////////////////////////////////////////////////////
    {
        int i;
        char result[128];
        int result_counter = 0;

        *result = 0;
        for (i = from; i <= upto; i++) {
            if (fitsInsideBoundaries(&enc->coord32, boundaries(i))) {
                if (isNameless(i)) {
                    encodeNameless(result, enc, ccode, extraDigits, i);
                } else if (recType(i) > 1) {
                    encodeAutoHeader(result, enc, i, extraDigits);
                } else if ((i == upto) && isSubdivision(ccode)) {
                    // *** do a recursive call for the parent ***
                    encoderEngine(parentTerritoryOf(ccode), enc, stop_with_one_result, extraDigits, requiredEncoder,
                                  ccode);
                    return;
                } else // must be grid
                {
                    // skip isRestricted records unless there already is a result
                    if (result_counter || !isRestricted(i)) {
                        if (coDex(i) < 54) {
                            char headerletter = (char) ((recType(i) == 1) ? headerLetter(i) : 0);
                            encodeGrid(result, enc, i, extraDigits, headerletter);
                        }
                    }
                }

                // =========== handle result (if any)
                if (*result) {
                    result_counter++;

                    repack_if_alldigits(result, 0);

                    if ((requiredEncoder < 0) || (requiredEncoder == i)) {
                        const int cc = (ccode_override >= 0 ? ccode_override : ccode);
                        if (*result && enc->mapcodes && (enc->mapcodes->count < MAX_NR_OF_MAPCODE_RESULTS)) {
                            char *s = enc->mapcodes->mapcode[enc->mapcodes->count++];
                            if (cc == ccode_earth) {
                                strcpy(s, result);
                            } else {
                                getTerritoryIsoName(s, cc + 1, 0);
                                strcat(s, " ");
                                strcat(s, result);
                            }
                        }
                        if (requiredEncoder == i) {
                            return;
                        }
                    }
                    if (stop_with_one_result) {