// Copyright (C) 2014-2025 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.

/**
 * @file mapcoder.c
 * @brief Core implementation of the Mapcode encoding and decoding system
 *
 * This file contains the complete implementation of the Mapcode system, which provides
 * a way to encode any location on Earth into a short alphanumeric code and decode
 * it back to precise coordinates.
 *
 * Key functionality includes:
 * - Encoding latitude/longitude coordinates to mapcode strings
 * - Decoding mapcode strings back to coordinates
 * - Territory-based encoding for shorter codes within specific regions
 * - Support for high-precision encoding with extra digits
 * - Multi-alphabet support for international usage
 * - Territory name handling and lookup functions
 *
 * The encoding uses a sophisticated grid system that divides the Earth's surface
 * into increasingly fine grids, with special handling for different territory
 * shapes and boundary conditions.
 *
 * @author Stichting Mapcode Foundation
 * @version See MAPCODE_C_VERSION constant
 */

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

#include "mapcoder.h"
#include "internal_data.h"
#include "internal_iso3166_data.h"
#include "internal_territory_alphabets.h"
#include "internal_territory_names_local.h"
#include "internal_alphabet_recognizer.h"
#include "internal_territory_names_af.h"
#include "internal_territory_names_ar.h"
#include "internal_territory_names_be.h"
#include "internal_territory_names_cn.h"
#include "internal_territory_names_cs.h"
#include "internal_territory_names_da.h"
#include "internal_territory_names_de.h"
#include "internal_territory_names_en.h"
#include "internal_territory_names_es.h"
#include "internal_territory_names_fi.h"
#include "internal_territory_names_fr.h"
#include "internal_territory_names_he.h"
#include "internal_territory_names_hi.h"
#include "internal_territory_names_hr.h"
#include "internal_territory_names_id.h"
#include "internal_territory_names_it.h"
#include "internal_territory_names_ja.h"
#include "internal_territory_names_ko.h"
#include "internal_territory_names_nl.h"
#include "internal_territory_names_no.h"
#include "internal_territory_names_pl.h"
#include "internal_territory_names_pt.h"
#include "internal_territory_names_ru.h"
#include "internal_territory_names_sv.h"
#include "internal_territory_names_sw.h"
#include "internal_territory_names_tr.h"
#include "internal_territory_names_uk.h"

/**
 * @section exported_constants Exported Constants
 * The constants are also exported as variables to allow other languages to use them.
 * This provides runtime access to compile-time constants for language bindings.
 */
char* _MAPCODE_C_VERSION = MAPCODE_C_VERSION;                           // Version string of the mapcode library
int _MAX_NR_OF_MAPCODE_RESULTS = MAX_NR_OF_MAPCODE_RESULTS;             // Maximum number of mapcode results returned
int _MAX_PRECISION_DIGITS = MAX_PRECISION_DIGITS;                       // Maximum extra precision digits supported
int _MAX_PROPER_MAPCODE_ASCII_LEN = MAX_PROPER_MAPCODE_ASCII_LEN;       // Maximum length of a proper mapcode in ASCII
int _MAX_ISOCODE_ASCII_LEN = MAX_ISOCODE_ASCII_LEN;                     // Maximum length of ISO territory code
int _MAX_CLEAN_MAPCODE_ASCII_LEN = MAX_CLEAN_MAPCODE_ASCII_LEN;         // Maximum length of clean mapcode (no territory)
int _MAX_MAPCODE_RESULT_ASCII_LEN = MAX_MAPCODE_RESULT_ASCII_LEN;       // Maximum length of complete result string
int _MAX_TERRITORY_FULLNAME_UTF8_LEN = MAX_TERRITORY_FULLNAME_UTF8_LEN; // Maximum territory name length in UTF-8
int _MAX_MAPCODE_RESULT_UTF8_LEN = MAX_MAPCODE_RESULT_UTF8_LEN;         // Maximum result length in UTF-8
int _MAX_MAPCODE_RESULT_UTF16_LEN = MAX_MAPCODE_RESULT_UTF16_LEN;       // Maximum result length in UTF-16
int _MAX_ALPHABETS_PER_TERRITORY = MAX_ALPHABETS_PER_TERRITORY;         // Maximum alphabets supported per territory

/**
 * @section debug_system Debug and Assertion System
 * Debug mode provides runtime assertion checking to catch programming errors
 * during development and testing.
 */
#ifdef DEBUG

#include <stdio.h>

/**
 * @brief Debug assertion function that tracks and reports failed conditions
 * @param iCondition The condition to test (should be true)
 * @param cstrFile Source file where assertion occurred
 * @param iLine Line number where assertion occurred
 *
 * This function provides detailed error reporting when assertions fail in debug mode.
 * It keeps track of assertion failures and terminates the program after too many
 * failures to prevent cascading errors.
 */
void _TestAssert(int iCondition, const char* cstrFile, int iLine) {
    static int nrAsserts = 0;
    if (!iCondition) {
        fprintf(stderr, "** Assertion failed: file \"%s\", line %d\n", cstrFile, iLine);
        ++nrAsserts;
        if (nrAsserts >= 25) {
            fprintf(stderr, "** Stopped execution after %d assertions!\n", nrAsserts);
            exit(-1);
        }
    }
}

// In debug mode, assertions are active and report failures
#define ASSERT(condition) _TestAssert((int) (condition), __FILE__, (int) __LINE__)
#else
// In release mode, assertions are compiled out for performance
#define ASSERT(condition)
#endif


// If you do not want to use the fast encoding from internal_territory_search.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 "internal_territory_search.h"

#endif

/**
 * @section territory_flag_macros Territory Boundary Flag Extraction Macros
 * These macros extract specific information from the flags field of territory boundary records.
 * Each territory has flags that encode various properties used during encoding/decoding.
 */
#define IS_NAMELESS(m)        (TERRITORY_BOUNDARIES[m].flags & 64)      // Territory uses nameless encoding (bit 6)
#define IS_RESTRICTED(m)      (TERRITORY_BOUNDARIES[m].flags & 512)     // Territory has access restrictions (bit 9)
#define IS_SPECIAL_SHAPE(m)   (TERRITORY_BOUNDARIES[m].flags & 1024)    // Territory has non-standard shape (bit 10)
#define REC_TYPE(m)           ((TERRITORY_BOUNDARIES[m].flags >> 7) & 3) // Record type (bits 7-8): grid encoding method
#define SMART_DIV(m)          ((int)((unsigned int)(TERRITORY_BOUNDARIES[m].flags) >> 16))  // Smart divider value (bits 16+): grid subdivision
#define HEADER_LETTER(m)      (ENCODE_CHARS[(TERRITORY_BOUNDARIES[m].flags >> 11) & 31]) // Header letter for encoding (bits 11-15)

/**
 * @section parsing_tokens Token Types for Mapcode Parsing
 * These constants define different types of tokens encountered during mapcode parsing.
 */
#define TOKENSEP   0    // Separator character (space, hyphen, etc.)
#define TOKENDOT   1    // Dot character '.'
#define TOKENCHR   2    // Regular character (consonant or digit)
#define TOKENVOWEL 3    // Vowel character (A, E, U)
#define TOKENZERO  4    // Zero digit '0'
#define TOKENHYPH  5    // Hyphen character '-'

/**
 * @section parsing_state Parsing State Constants
 */
#define STATE_GO  31    // Active parsing state identifier

/**
 * @section mathematical_constants Mathematical and Earth Constants
 * Fundamental constants used in coordinate calculations and grid mathematics.
 */
#define MATH_PI                 3.14159265358979323846  // High-precision value of π
#define MAX_PRECISION_FACTOR    810000      // 30^(MAX_PRECISION_DIGITS/2) - base precision factor

// Earth's radius in meters (WGS84 ellipsoid approximation)
#define EARTH_RADIUS_X_METERS 6378137       // Equatorial radius (semi-major axis)
#define EARTH_RADIUS_Y_METERS 6356752       // Polar radius (semi-minor axis)

// Earth's circumference in meters
#define EARTH_CIRCUMFERENCE_X (EARTH_RADIUS_X_METERS * 2 * MATH_PI)  // Equatorial circumference
#define EARTH_CIRCUMFERENCE_Y (EARTH_RADIUS_Y_METERS * 2 * MATH_PI)  // Meridional circumference

/**
 * @section coordinate_conversion Coordinate Conversion Factors
 * Factors for converting between different coordinate representations.
 */
#define MICROLAT_TO_FRACTIONS_FACTOR ((double) MAX_PRECISION_FACTOR)    // Convert latitude microdegrees to fractions
#define MICROLON_TO_FRACTIONS_FACTOR (4.0 * MAX_PRECISION_FACTOR)       // Convert longitude microdegrees to fractions

/**
 * @section grid_encoding_constants Grid and Encoding Constants
 * These constants define the fundamental grid structure used in mapcode encoding.
 * The mapcode system uses a base-31 grid system that recursively subdivides space.
 */
#define GRID_SIZE_31           31               // Base grid size: 31x31 grid cells (base-31 encoding)
#define GRID_SIZE_961          961              // 31^2 = 961 - second level grid size
#define GRID_SIZE_962          962              // 961 + 1 - used for boundary calculations
#define GRID_SIZE_SQUARED      (961 * 961)     // 961^2 - third level grid size for fine precision
#define MAX_NAMELESS_RECORDS   62               // Maximum nameless territory records in subdivision
#define Y_DIVIDER              90               // Standard latitude divider for grid calculations
#define SPECIAL_CODEX_21       21               // Special encoding method identifier (type 21)
#define SPECIAL_CODEX_22       22               // Special encoding method identifier (type 22)
#define SPECIAL_CODEX_13       13               // Special encoding method identifier (type 13)
#define SPECIAL_CODEX_14       14               // Special encoding method identifier (type 14)
#define GRID_MULTIPLIER_16     16               // Multiplier for grid offset calculations

/**
 * @section string_encoding_flags String Encoding Type Flags
 * Flags to distinguish between different string encoding formats.
 */
#define FLAG_UTF8_STRING      0                 // Interpret string pointer as UTF-8 characters
#define FLAG_UTF16_STRING     1                 // Interpret string pointer as UTF-16 characters

/**
 * @section distance_calculation Distance Calculation Constants
 * Meters per degree latitude is constant globally. For longitude, the actual
 * distance varies by latitude, so use factor * cos(midpoint_latitude).
 */
static const double METERS_PER_DEGREE_LAT = EARTH_CIRCUMFERENCE_Y / 360.0;  // ~111,319 meters per degree latitude
static const double METERS_PER_DEGREE_LON = EARTH_CIRCUMFERENCE_X / 360.0;  // ~111,320 meters per degree longitude at equator

/**
 * @section debug_control Debug Control Variables
 */
static const int DEBUG_STOP_AT = -1; // Internal debug limit for encoding tests (do not use in production!)

/**
 * @section locale_support Locale and Language Support Structures
 * These structures support multi-language territory names for international usage.
 */

/**
 * @brief Registry item linking a locale identifier to territory name translations
 * @param locale Two-character locale identifier (e.g., "EN", "FR", "DE")
 * @param territoryFullNames Array of translated territory names for this locale
 */
typedef struct {
    const char* locale;                 // Language/locale identifier
    const char** territoryFullNames;    // Array of territory names in this language
} LocaleRegistryItem;

/**
 * @brief Registry of supported locales and their territory name translations
 * This array maps two-character locale codes to arrays of translated territory names.
 * Supports major world languages for international mapcode applications.
 */
static const LocaleRegistryItem LOCALE_REGISTRY[] = {
    {"AF", TERRITORY_FULL_NAME_AF},     // Afrikaans
    {"AR", TERRITORY_FULL_NAME_AR},     // Arabic
    {"BE", TERRITORY_FULL_NAME_BE},     // Belarusian
    {"CN", TERRITORY_FULL_NAME_CN},     // Chinese (Simplified)
    {"CS", TERRITORY_FULL_NAME_CS},     // Czech
    {"DA", TERRITORY_FULL_NAME_DA},     // Danish
    {"DE", TERRITORY_FULL_NAME_DE},     // German
    {"EN", TERRITORY_FULL_NAME_EN},     // English
    {"ES", TERRITORY_FULL_NAME_ES},     // Spanish
    {"FI", TERRITORY_FULL_NAME_FI},     // Finnish
    {"FR", TERRITORY_FULL_NAME_FR},     // French
    {"HE", TERRITORY_FULL_NAME_HE},     // Hebrew
    {"HI", TERRITORY_FULL_NAME_HI},     // Hindi
    {"HR", TERRITORY_FULL_NAME_HR},     // Croatian
    {"ID", TERRITORY_FULL_NAME_ID},     // Indonesian
    {"IT", TERRITORY_FULL_NAME_IT},     // Italian
    {"JA", TERRITORY_FULL_NAME_JA},     // Japanese
    {"KO", TERRITORY_FULL_NAME_KO},     // Korean
    {"NL", TERRITORY_FULL_NAME_NL},     // Dutch
    {"NO", TERRITORY_FULL_NAME_NO},     // Norwegian
    {"PT", TERRITORY_FULL_NAME_PT},     // Portuguese
    {"PL", TERRITORY_FULL_NAME_PL},     // Polish
    {"RU", TERRITORY_FULL_NAME_RU},     // Russian
    {"SV", TERRITORY_FULL_NAME_SV},     // Swedish
    {"SW", TERRITORY_FULL_NAME_SW},     // Swahili
    {"TR", TERRITORY_FULL_NAME_TR},     // Turkish
    {"UK", TERRITORY_FULL_NAME_UK}      // Ukrainian
};

/**
 * @section parent_territories Parent Territory Information
 * The 8 major parent territories that contain subdivisions with shorter mapcodes.
 * These large countries/regions are subdivided to allow shorter codes within them.
 */

/**
 * @brief Three-letter ISO codes for parent territories
 * Comma-separated string of 3-letter ISO codes for the 8 major parent territories
 */
static const char* PARENTS_3 = "USA,IND,CAN,AUS,MEX,BRA,RUS,CHN,";

/**
 * @brief Two-letter ISO codes for parent territories
 * Comma-separated string of 2-letter ISO codes corresponding to PARENTS_3
 */
static const char* PARENTS_2 = "US,IN,CA,AU,MX,BR,RU,CN,";

/**
 * @brief Territory enumeration values for parent territories
 * Array mapping parent territory numbers (1-8) to their Territory enum values.
 * Index 0 is TERRITORY_NONE, indices 1-8 are the 8 parent territories.
 */
static const enum Territory PARENT_NR[9] = {
    TERRITORY_NONE,     // 0 - no parent
    TERRITORY_USA,      // 1 - United States of America
    TERRITORY_IND,      // 2 - India
    TERRITORY_CAN,      // 3 - Canada
    TERRITORY_AUS,      // 4 - Australia
    TERRITORY_MEX,      // 5 - Mexico
    TERRITORY_BRA,      // 6 - Brazil
    TERRITORY_RUS,      // 7 - Russia
    TERRITORY_CHN       // 8 - China
};

/**
 * @section base31_encoding Base-31 Encoding Character Set
 * The mapcode system uses a base-31 alphabet for compact encoding.
 * Character set is designed to avoid ambiguous characters and improve readability.
 */

/**
 * @brief Base-31 encoding alphabet used for mapcode generation
 *
 * Character mapping:
 * - Positions 0-9:   Digits '0'-'9'
 * - Positions 10-30: Consonants 'B','C','D','F','G','H','J','K','L','M','N','P','Q','R','S','T','V','W','X','Y','Z'
 * - Positions 31-33: Vowels 'A','E','U' (used for special purposes)
 *
 * Notable exclusions: 'I' and 'O' are excluded to avoid confusion with '1' and '0'
 */
static const char ENCODE_CHARS[34] = {
    '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',           // Digits (0-9)
    'B', 'C', 'D', 'F', 'G', 'H', 'J', 'K', 'L', 'M',         // Consonants (10-19)
    'N', 'P', 'Q', 'R', 'S', 'T', 'V', 'W', 'X', 'Y', 'Z',    // Consonants (20-30)
    'A', 'E', 'U'                                              // Vowels (31-33)
};


///////////////////////////////////////////////////////////////////////////////////////////////
//
//  PRECOMPUTED COMPANION TABLES
//
//  Derived once from TERRITORY_BOUNDARIES.flags; queried in hot encode/decode loops
//  to avoid repeated bit-masking on the same record per iteration.
//
///////////////////////////////////////////////////////////////////////////////////////////////

#define KIND_BIT_NAMELESS       0x01u
#define KIND_BIT_RESTRICTED     0x02u
#define KIND_BIT_SPECIAL_SHAPE  0x04u

static unsigned char RECORD_CODEX[MAPCODE_BOUNDARY_MAX + 1];
static unsigned char RECORD_REC_TYPE[MAPCODE_BOUNDARY_MAX + 1];
static unsigned char RECORD_KIND[MAPCODE_BOUNDARY_MAX + 1];
static unsigned char RECORD_HEADER_LETTER[MAPCODE_BOUNDARY_MAX + 1];
static unsigned short RECORD_SMART_DIV[MAPCODE_BOUNDARY_MAX + 1];

#define TERRITORY_TABLE_SIZE (_TERRITORY_MAX - _TERRITORY_MIN)
static int TERRITORY_FIRST_NAMELESS[TERRITORY_TABLE_SIZE];
static int TERRITORY_NAMELESS_COUNT[TERRITORY_TABLE_SIZE];

/* Not thread-safe for concurrent first call. Duplicate concurrent init writes
   identical values so results are logically correct, but callers must ensure
   the library is initialized before spawning threads, or initialize once
   explicitly on the main thread. */
static int companion_initialized = 0;

static void initCompanionTables(void) {
    int m;
    int t;
    if (companion_initialized) {
        return;
    }
    for (m = 0; m <= MAPCODE_BOUNDARY_MAX; m++) {
        const int flags = TERRITORY_BOUNDARIES[m].flags;
        const int c = flags & 31;
        const int codex_val = 10 * (c / 5) + ((c % 5) + 1);
        const int rec_type = (flags >> 7) & 3;
        unsigned char kind = 0;
        if (flags & 64)   { kind |= KIND_BIT_NAMELESS; }
        if (flags & 512)  { kind |= KIND_BIT_RESTRICTED; }
        if (flags & 1024) { kind |= KIND_BIT_SPECIAL_SHAPE; }
        RECORD_CODEX[m]         = (unsigned char) codex_val;
        RECORD_REC_TYPE[m]      = (unsigned char) rec_type;
        RECORD_KIND[m]          = kind;
        RECORD_HEADER_LETTER[m] = (unsigned char) ENCODE_CHARS[(flags >> 11) & 31];
        RECORD_SMART_DIV[m]     = (unsigned short) ((unsigned int) flags >> 16);
    }
    for (t = 0; t < TERRITORY_TABLE_SIZE; t++) {
        TERRITORY_FIRST_NAMELESS[t] = -1;
        TERRITORY_NAMELESS_COUNT[t] = 0;
    }
    for (t = 0; t < TERRITORY_TABLE_SIZE - 1; t++) {
        const int from = DATA_START[t];
        const int upto_excl = DATA_START[t + 1];
        int i;
        int first = -1;
        int count = 0;
        for (i = from; i < upto_excl; i++) {
            if (RECORD_KIND[i] & KIND_BIT_NAMELESS) {
                if (first < 0) {
                    first = i;
                }
                count++;
            }
        }
        TERRITORY_FIRST_NAMELESS[t] = first;
        TERRITORY_NAMELESS_COUNT[t] = count;
    }
#ifdef DEBUG
    for (m = 0; m <= MAPCODE_BOUNDARY_MAX; m++) {
        const int flagsDbg = TERRITORY_BOUNDARIES[m].flags;
        const int cDbg = flagsDbg & 31;
        const int codex_valDbg = 10 * (cDbg / 5) + ((cDbg % 5) + 1);
        ASSERT(RECORD_CODEX[m] == (unsigned char) codex_valDbg);
        ASSERT(RECORD_REC_TYPE[m] == (unsigned char) ((flagsDbg >> 7) & 3));
        ASSERT(((RECORD_KIND[m] & KIND_BIT_NAMELESS) != 0) == ((flagsDbg & 64) != 0));
        ASSERT(((RECORD_KIND[m] & KIND_BIT_RESTRICTED) != 0) == ((flagsDbg & 512) != 0));
        ASSERT(((RECORD_KIND[m] & KIND_BIT_SPECIAL_SHAPE) != 0) == ((flagsDbg & 1024) != 0));
        ASSERT(RECORD_HEADER_LETTER[m] == (unsigned char) ENCODE_CHARS[(flagsDbg >> 11) & 31]);
        ASSERT(RECORD_SMART_DIV[m] == (unsigned short) ((unsigned int) flagsDbg >> 16));
    }
#endif
    companion_initialized = 1;
}


/**
 * @brief Convert ASCII character to base-31 value for mapcode decoding
 * @param ch ASCII character to decode
 * @return Base-31 value (0-30), or negative for special cases:
 *         -1: illegal character
 *         -2: vowel 'A' (position 31 in ENCODE_CHARS)
 *         -3: vowel 'E' (position 32 in ENCODE_CHARS)
 *         -4: vowel 'U' (position 33 in ENCODE_CHARS)
 *
 * Special handling: 'O'/'o' maps to '0', 'I'/'i' maps to '1' for user convenience.
 * This allows users to type potentially confusing characters and still get correct results.
 */
static signed char decodeChar(const char ch) {
    // Lookup table for base-31 value of ASCII character (negative for illegal characters)
    // Special cases -2, -3, -4 for vowels; 'O' and 'I' interpreted as '0' and '1'.
    static const signed char decode_chars[256] = {
        -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, // 0
        -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, // 16
        -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, // 32
        0, 1, 2, 3, 4, 5, 6, 7, 8, 9, -1, -1, -1, -1, -1, -1, // 48
        -1, -2, 10, 11, 12, -3, 13, 14, 15, 1, 16, 17, 18, 19, 20, 0, // 64
        21, 22, 23, 24, 25, -4, 26, 27, 28, 29, 30, -1, -1, -1, -1, -1, // 80
        -1, -2, 10, 11, 12, -3, 13, 14, 15, 1, 16, 17, 18, 19, 20, 0, // 96
        21, 22, 23, 24, 25, -4, 26, 27, 28, 29, 30, -1, -1, -1, -1, -1, // 112
        -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, // 128
        -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, // 144
        -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, // 160
        -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, // 176
        -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, // 192
        -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, // 208
        -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, // 224
        -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 // 240
    };
    return decode_chars[(unsigned char)ch]; // ch can be negative, must be fit to range 0-255.
}

/**
 * @brief Calculate the distance in meters between two coordinate points
 * @param latDeg1 Latitude of first point in degrees (-90 to 90)
 * @param lonDeg1 Longitude of first point in degrees (-180 to 180)
 * @param latDeg2 Latitude of second point in degrees (-90 to 90)
 * @param lonDeg2 Longitude of second point in degrees (-180 to 180)
 * @return Distance between the two points in meters
 *
 * This function calculates the approximate distance between two points on Earth's surface
 * using a simplified spherical model. The calculation:
 * 1. Handles longitude wrapping around the 180°/-180° meridian
 * 2. Uses cosine correction for longitude distance based on average latitude
 * 3. Applies Pythagorean theorem to get final distance
 *
 * Note: This is an approximation suitable for mapcode purposes but not a precise
 * geodetic distance calculation (which would require ellipsoid math).
 *
 * @public
 */
double distanceInMeters(double latDeg1, double lonDeg1, double latDeg2, double lonDeg2) {
    double dx;
    double dy;
    double deltaLonDegrees;
    double deltaLatDegrees;
    int wrapped = lonDeg1 > lonDeg2;
    ASSERT((-90.0 <= latDeg1) && (latDeg1 <= 90.0));
    ASSERT((-90.0 <= latDeg2) && (latDeg2 <= 90.0));
    if (wrapped) {
        deltaLonDegrees = 360.0 - (lonDeg1 - lonDeg2);
    }
    else {
        deltaLonDegrees = lonDeg2 - lonDeg1;
    }
    if (deltaLonDegrees > 180.0) {
        deltaLonDegrees = 360.0 - deltaLonDegrees;
    }
    deltaLatDegrees = fabs(latDeg1 - latDeg2);
    dy = deltaLatDegrees * METERS_PER_DEGREE_LAT;
    dx = deltaLonDegrees * METERS_PER_DEGREE_LON * cos((latDeg1 + (latDeg2 - latDeg1) / 2.0) * MATH_PI / 180.0);
    return sqrt(dx * dx + dy * dy);
}

/**
 * @section precision_error_calculation Precision Error Calculation
 * The mapcode system supports high-precision encoding with additional digits.
 * Each extra digit reduces the maximum possible error by approximately a factor of 5.
 */

/**
 * @brief Maximum error distances in meters for different precision levels
 *
 * This lookup table contains the maximum possible error (in meters) for each
 * supported precision level. The values are empirically determined based on
 * the mapcode grid system:
 *
 * Index 0: Base precision (no extra digits) - ~7.49m max error
 * Index 1: 1 extra digit - ~1.39m max error
 * Index 2: 2 extra digits - ~0.251m max error
 * ... and so on up to MAX_PRECISION_DIGITS
 *
 * Each additional precision level reduces error by approximately 30^0.5 ≈ 5.48x
 */
static const double MAX_ERROR_IN_METERS[MAX_PRECISION_DIGITS + 1] = {
    7.49,       // 0 extra digits - base precision
    1.39,       // 1 extra digit
    0.251,      // 2 extra digits
    0.0462,     // 3 extra digits
    0.00837,    // 4 extra digits
    0.00154,    // 5 extra digits
    0.000279,   // 6 extra digits
    0.0000514,  // 7 extra digits
    0.0000093   // 8 extra digits (maximum supported)
};

/**
 * @brief Get the maximum possible error for a given precision level
 * @param extraDigits Number of extra precision digits (0 to MAX_PRECISION_DIGITS)
 * @return Maximum error in meters for this precision level, or 0.0 for invalid input
 *
 * This function returns the theoretical maximum error that can occur when encoding
 * a coordinate at the specified precision level. The actual error is typically
 * much smaller than this maximum value.
 *
 * @public
 */
double maxErrorInMeters(int extraDigits) {
    ASSERT(extraDigits >= 0);
    if ((extraDigits < 0) || (extraDigits > MAX_PRECISION_DIGITS)) {
        return 0.0;
    }
    return MAX_ERROR_IN_METERS[extraDigits];
}

/**
 * @section coordinate_structures Coordinate Representation Structures
 * The mapcode system uses multiple coordinate representations for different purposes:
 * - Point32: Integer microdegree coordinates (precise, efficient)
 * - Point: Floating-point coordinates (flexible units depending on context)
 */

/**
 * @brief Integer coordinate point in microdegrees
 *
 * This structure represents coordinates using 32-bit integers in microdegrees
 * (millionths of a degree). This provides:
 * - High precision without floating-point rounding errors
 * - Efficient storage and comparison operations
 * - Range: approximately ±2147 degrees (more than sufficient for Earth coordinates)
 */
typedef struct {
    int latMicroDeg;    // Latitude in microdegrees (±90,000,000 for ±90°)
    int lonMicroDeg;    // Longitude in microdegrees (±180,000,000 for ±180°)
} Point32;

/**
 * @brief Floating-point coordinate point with flexible units
 *
 * This structure uses double-precision floating-point numbers.
 * The units depend on context:
 * - Sometimes degrees (for user-facing coordinates)
 * - Sometimes fractions (for internal grid calculations)
 * - Sometimes other units (for intermediate calculations)
 */
typedef struct {
    double lat;         // Latitude (units depend on usage context)
    double lon;         // Longitude (units depend on usage context)
} Point;

/**
 * @brief Convert fraction coordinates to 32-bit microdegree coordinates
 * @param p Point containing coordinates in fraction units
 * @return Point32 with coordinates converted to microdegrees
 *
 * This function converts from the internal fraction coordinate system
 * to microdegree integers. The conversion factors (810000, 3240000) are
 * derived from the mapcode grid mathematics.
 */
static Point32 convertFractionsToCoord32(const Point* p) {
    Point32 p32;
    p32.latMicroDeg = (int)floor(p->lat / 810000);      // Convert latitude fractions to microdegrees
    p32.lonMicroDeg = (int)floor(p->lon / 3240000);     // Convert longitude fractions to microdegrees
    return p32;
}

/**
 * @brief Convert fraction coordinates to degree coordinates
 * @param p Point containing coordinates in fraction units
 * @return Point with coordinates converted to degrees
 *
 * This function converts from the internal fraction coordinate system
 * to standard degree coordinates. The large divisors (810000 * 1000000,
 * 3240000 * 1000000) scale from fractions to degrees.
 */
static Point convertFractionsToDegrees(const Point* p) {
    Point pd;
    pd.lat = p->lat / (810000 * 1000000.0);            // Convert latitude fractions to degrees
    pd.lon = p->lon / (3240000 * 1000000.0);           // Convert longitude fractions to degrees
    return pd;
}


static enum MapcodeError
convertCoordsToMicrosAndFractions(Point32* coord32, int* fracLat, int* fracLon, double latDeg, double lonDeg) {
    double frac;
    ASSERT(coord32);
    if (isnan(lonDeg) || isinf(lonDeg) || isnan(latDeg) || isinf(latDeg)) {
        return ERR_BAD_COORDINATE;
    }
    if (latDeg < -90) {
        latDeg = -90;
    }
    else if (latDeg > 90) {
        latDeg = 90;
    }
    latDeg += 90; // lat now [0..180]
    ASSERT((0.0 <= latDeg) && (latDeg <= 180.0));
    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>
    ASSERT((0.0 <= lonDeg) && (lonDeg < 360.0));
    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 ERR_OK;
}

///////////////////////////////////////////////////////////////////////////////////////////////
//
//  TerritoryBoundary (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 TerritoryBoundary
static int fitsInsideBoundaries(const Point32* coord32, const TerritoryBoundary* b) {
    ASSERT(coord32);
    ASSERT(b);
    return (b->miny <= coord32->latMicroDeg &&
        coord32->latMicroDeg < b->maxy &&
        isInRange(coord32->lonMicroDeg, b->minx, b->maxx));
}


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

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


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) {
    ASSERT(z);
    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) {
    ASSERT(z);
    return ((z->fmaxx <= z->fminx) || (z->fmaxy <= z->fminy));
}


static Point getMidPointFractions(const MapcodeZone* z) {
    Point p;
    ASSERT(z);
    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) {
    ASSERT(target);
    ASSERT(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 boundary of territory rectangle m.
// returns nonzero in case such a zone exists
static int restrictZoneTo(MapcodeZone* z, const MapcodeZone* zone, const TerritoryBoundary* b) {
    ASSERT(z);
    ASSERT(zone);
    ASSERT(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;
}

///////////////////////////////////////////////////////////////////////////////////////////////
//
//  COPY ROUTINES
//
///////////////////////////////////////////////////////////////////////////////////////////////

// PRIVATE - copy characters into targetString, limited to its size
static char* lengthCopy(char* targetString, const char* sourceString, int nrCharacters, int targetSize) {
    if (nrCharacters >= targetSize) {
        nrCharacters = targetSize - 1;
    }
    memcpy(targetString, sourceString, (size_t)nrCharacters);
    targetString[nrCharacters] = 0;
    return targetString;
}


// PRIVATE - copy as much of sourceString as will fit; returns targetString
static char* safeCopy(char* targetString, const char* sourceString, const int targetSize) {
    int sourceLength = (int)strlen(sourceString);
    return lengthCopy(targetString, sourceString, sourceLength, targetSize);
}


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

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

static int firstRec(const enum Territory ccode) {
    ASSERT((_TERRITORY_MIN < ccode) && (ccode < _TERRITORY_MAX));
    return DATA_START[INDEX_OF_TERRITORY(ccode)];
}


static int lastRec(const enum Territory ccode) {
    ASSERT((_TERRITORY_MIN < ccode) && (ccode < _TERRITORY_MAX));
    return DATA_START[INDEX_OF_TERRITORY(ccode) + 1] - 1;
}


// returns parent of ccode (or TERRITORY_NONE)
static enum Territory parentTerritoryOf(const enum Territory ccode) {
    if (ccode <= _TERRITORY_MIN || ccode >= _TERRITORY_MAX) {
        return TERRITORY_NONE;
    }
    return PARENT_NR[(int)PARENT_LETTER[INDEX_OF_TERRITORY(ccode)]];
}


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


static int xDivider4(const int miny, const int maxy) {
    // 360 * cos(microdegrees>>19)
    static const int xdivider19[172] = {
        360, 360, 360, 360, 360, 360, 361, 361, 361, 361,
        362, 362, 362, 363, 363, 363, 364, 364, 365, 366,
        366, 367, 367, 368, 369, 370, 370, 371, 372, 373,
        374, 375, 376, 377, 378, 379, 380, 382, 383, 384,
        386, 387, 388, 390, 391, 393, 394, 396, 398, 399,
        401, 403, 405, 407, 409, 411, 413, 415, 417, 420,
        422, 424, 427, 429, 432, 435, 437, 440, 443, 446,
        449, 452, 455, 459, 462, 465, 469, 473, 476, 480,
        484, 488, 492, 496, 501, 505, 510, 515, 520, 525,
        530, 535, 540, 546, 552, 558, 564, 570, 577, 583,
        590, 598, 605, 612, 620, 628, 637, 645, 654, 664,
        673, 683, 693, 704, 715, 726, 738, 751, 763, 777,
        791, 805, 820, 836, 852, 869, 887, 906, 925, 946,
        968, 990, 1014, 1039, 1066, 1094, 1123, 1154, 1187, 1223,
        1260, 1300, 1343, 1389, 1438, 1490, 1547, 1609, 1676, 1749,
        1828, 1916, 2012, 2118, 2237, 2370, 2521, 2691, 2887, 3114,
        3380, 3696, 4077, 4547, 5139, 5910, 6952, 8443, 10747, 14784,
        23681, 59485
    };
    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 enum Territory ccode) {
    return parentTerritoryOf(ccode) != TERRITORY_NONE;
}


// 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 = (int) RECORD_CODEX[m];
    ASSERT((0 <= m) && (m <= MAPCODE_BOUNDARY_MAX));
    ASSERT((0 <= firstcode) && (firstcode <= MAPCODE_BOUNDARY_MAX));
    while (i >= firstcode && (int) RECORD_CODEX[i] == codexm && (RECORD_KIND[i] & KIND_BIT_NAMELESS)) {
        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 = (int) RECORD_CODEX[m];
    int last = m;
    ASSERT((0 <= m) && (m <= MAPCODE_BOUNDARY_MAX));
    ASSERT((0 <= firstcode) && (firstcode <= MAPCODE_BOUNDARY_MAX));
    while ((int) RECORD_CODEX[last] == codexm) {
        last++;
    }
    ASSERT((0 <= last) && (last <= MAPCODE_BOUNDARY_MAX));
    ASSERT(last >= first);
    return (last - first);
}


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


static void makeUppercase(char* s) {
    ASSERT(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) ? PARENTS_2 : PARENTS_3);
    const char* f;
    char country[4];
    ASSERT(s[0] && s[1]);
    ASSERT((2 <= len) && (len <= 3));
    ASSERT(s && ((int) strlen(s) >= len));
    lengthCopy(country, s, len, 4);
    makeUppercase(country);
    f = strstr(p, country);
    if (!f) {
        return -1;
    }
    return 1 + (int)((f - p) / (len + 1));
}

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

static void repackIfAllDigits(char* input, const int aonly) {
    char* s = input;
    int alldigits = 1; // assume all digits
    char* e;
    char* dotpos = NULL;
    ASSERT(input);
    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 unpackIfAllDigits(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 (int)ERR_INVALID_CHARACTER;
            }
            else {
                v += decodeChar(*e);
            }

            if (v < 100) {
                *s = ENCODE_CHARS[(unsigned int)v / 10];
                *e = ENCODE_CHARS[(unsigned int)v % 10];
            }
            else {
                return (int)ERR_INVALID_ENDVOWELS; // mapcodes ends 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
{
    ASSERT(result);
    ASSERT(enc);
    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) {
    ASSERT(result);
    ASSERT(nrchars >= 0);
    result[nrchars] = 0; // zero-terminate!
    while (nrchars > 0) {
        const int q = value / 31;
        const int r = value - q * 31;
        nrchars--;
        result[nrchars] = ENCODE_CHARS[r];
        value = q;
    }
}


static void encodeTriple(char* result, const int difx, const int dify) {
    ASSERT(result);
    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);
    }
} // encodeTriple

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 ***

// default cell divisions for n characters
static const int X_SIDE[6] = {0, 5, 31, 168, 961, 168 * 31};
static const int Y_SIDE[6] = {0, 6, 31, 176, 961, 176 * 31};
// number of combinations for n characters
static const int NC[6] = {1, 31, 961, 29791, 923521, 28629151};


// 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 TerritoryBoundary* b = TERRITORY_BOUNDARY(m);
    const int orgcodex = coDex(m);
    int codexm;
    ASSERT(result);
    ASSERT(enc);
    ASSERT((0 <= m) && (m <= MAPCODE_BOUNDARY_MAX));
    ASSERT((0 <= extraDigits) && (extraDigits <= MAX_PRECISION_DIGITS));
    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 = SMART_DIV(m);
        ASSERT(divy > 0);
        if (divy == 1) {
            divx = X_SIDE[prelen];
            divy = Y_SIDE[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 + Y_SIDE[postlen] - 1) / Y_SIDE[postlen]);
                const int dividerx = ((xgridsize + X_SIDE[postlen] - 1) / X_SIDE[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 = Y_SIDE[postlen] - 1 - dify;

                    if (postlen == 3) // encode special
                    {
                        encodeTriple(resultptr, difx, dify);
                    }
                    else {
                        encodeBase31(resultptr, (difx) * Y_SIDE[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
}


/**
 * Helper function to calculate storage offset for nameless encoding.
 * Determines the storage offset based on the number of nameless records (A),
 * the current record index (X), and the codex value (codexm).
 * This complex calculation was extracted to improve readability of encodeNameless.
 */
static int calculateStorageOffset(int A, int X, int codexm) {
    const int p = GRID_SIZE_31 / A;
    const int r = GRID_SIZE_31 % A; // the first r items are p+1

    if (codexm != SPECIAL_CODEX_21 && A <= GRID_SIZE_31) {
        return (X * p + (X < r ? X : r)) * GRID_SIZE_SQUARED;
    }
    else if (codexm != SPECIAL_CODEX_21 && A < MAX_NAMELESS_RECORDS) {
        if (X < (MAX_NAMELESS_RECORDS - A)) {
            return X * GRID_SIZE_SQUARED;
        }
        else {
            int storage_offset = (MAX_NAMELESS_RECORDS - A + ((X - MAX_NAMELESS_RECORDS + A) / 2)) * GRID_SIZE_SQUARED;
            if ((X + A) & 1) {
                storage_offset += (GRID_MULTIPLIER_16 * GRID_SIZE_961 * GRID_SIZE_31);
            }
            return storage_offset;
        }
    }
    else {
        const int BASEPOWER = (codexm == SPECIAL_CODEX_21) ? GRID_SIZE_SQUARED : GRID_SIZE_SQUARED * GRID_SIZE_31;
        int BASEPOWERA = (BASEPOWER / A);
        if (A == MAX_NAMELESS_RECORDS) {
            BASEPOWERA++;
        }
        else {
            BASEPOWERA = GRID_SIZE_961 * (BASEPOWERA / GRID_SIZE_961);
        }
        return X * BASEPOWERA;
    }
}

// *result==0 in case of error
static void encodeNameless(char* result, const EncodeRec* enc, const enum Territory ccode,
                           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(ccode));
    const int X = m - firstNamelessRecord(m, firstRec(ccode));
    ASSERT(result);
    ASSERT(enc);
    ASSERT((0 <= m) && (m <= MAPCODE_BOUNDARY_MAX));
    ASSERT((0 <= extraDigits) && (extraDigits <= MAX_PRECISION_DIGITS));
    *result = 0;

    {
        const int codexm = coDex(m);
        const int codexlen = (codexm / 10) + (codexm % 10);
        // determine side of square around centre
        int SIDE;

        const int storage_offset = calculateStorageOffset(A, X, codexm);
        const TerritoryBoundary* b;

        int xSIDE, orgSIDE;

        SIDE = SMART_DIV(m);
        ASSERT(SIDE > 0);

        b = TERRITORY_BOUNDARY(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 = Y_DIVIDER;
            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 (IS_SPECIAL_SHAPE(m)) {
                SIDE = 1 + ((b->maxy - b->miny) / Y_DIVIDER); // 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 == SPECIAL_CODEX_13) {
                    dotp--;
                }
                memmove(result + dotp, result + dotp - 1, 4);
                result[dotp - 1] = '.';
            }

            if (!IS_SPECIAL_SHAPE(m)) {
                if (codexm == SPECIAL_CODEX_22 && A < MAX_NAMELESS_RECORDS && orgSIDE == GRID_SIZE_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 TerritoryBoundary* b;

    // search back to first of the group
    int firstindex = m;
    const int codexm = coDex(m);
    ASSERT(result);
    ASSERT(enc);
    ASSERT((1 <= m) && (m <= MAPCODE_BOUNDARY_MAX));
    ASSERT((0 <= extraDigits) && (extraDigits <= MAX_PRECISION_DIGITS));

    while (REC_TYPE(firstindex - 1) > 1 && coDex(firstindex - 1) == codexm) {
        firstindex--;
    }

    i = firstindex;
    for (;;) {
        b = TERRITORY_BOUNDARY(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 (REC_TYPE(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] = '.';
            encodeTriple(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 enum Territory ccode, const EncodeRec* enc, const int stop_with_one_result,
                          const int extraDigits, const int requiredEncoder, const enum Territory ccode_override) {
    int from;
    int upto;
    ASSERT(enc);
    ASSERT((0 <= extraDigits) && (extraDigits <= MAX_PRECISION_DIGITS));

    if (!enc || (ccode < _TERRITORY_MIN)) {
        return;
    } // bad arguments

    from = firstRec(ccode);
    upto = lastRec(ccode);

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

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

        *result = 0;
        for (i = from; i <= upto; i++) {
            if (fitsInsideBoundaries(&enc->coord32, TERRITORY_BOUNDARY(i))) {
                const unsigned char kind     = RECORD_KIND[i];
                const unsigned char recTypeI = RECORD_REC_TYPE[i];
                if (kind & KIND_BIT_NAMELESS) {
                    encodeNameless(result, enc, ccode, extraDigits, i);
                }
                else if (recTypeI > 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 IS_RESTRICTED records unless there already is a result
                    if (result_counter || !(kind & KIND_BIT_RESTRICTED)) {
                        if (RECORD_CODEX[i] < 54) {
                            const char headerletter = (char)((recTypeI == 1) ? RECORD_HEADER_LETTER[i] : 0);
                            encodeGrid(result, enc, i, extraDigits, headerletter);
                        }
                    }
                }

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

                    repackIfAllDigits(result, 0);

                    if ((requiredEncoder < 0) || (requiredEncoder == i)) {
                        const enum Territory ccodeFinal = (ccode_override != TERRITORY_NONE ? ccode_override : ccode);
                        if (*result && enc->mapcodes && (enc->mapcodes->count < MAX_NR_OF_MAPCODE_RESULTS)) {
                            char* s = enc->mapcodes->mapcode[enc->mapcodes->count++];
                            if (ccodeFinal == TERRITORY_AAA) {
                                // AAA is never shown with territory
                                strcpy(s, result);
                            }
                            else {
                                getTerritoryIsoName(s, ccodeFinal, 0);
                                {
                                    size_t isoLen = strlen(s);
                                    size_t resultLen = strlen(result);
                                    s[isoLen] = ' ';
                                    memcpy(s + isoLen + 1, result, resultLen + 1);  /* +1 includes NUL */
                                }
                            }
                        }
                        if (requiredEncoder == i) {
                            return;
                        }
                    }
                    if (stop_with_one_result) {
                        return;
                    }
                    *result = 0; // clear for next iteration
                }
            }
        } // for i
    }
}


// pass Point to an array of pointers (at least 42), will be made to Point to result strings...
// returns nr of results;
static int encodeLatLonToMapcodes_internal(Mapcodes* mapcodes,
                                           const double lat, const double lon,
                                           const enum Territory territoryContext, const int stop_with_one_result,
                                           const int requiredEncoder, const int extraDigits) {
    EncodeRec enc;
    enc.mapcodes = mapcodes;
    enc.mapcodes->count = 0;
    ASSERT(mapcodes);
    ASSERT((0 <= extraDigits) && (extraDigits <= MAX_PRECISION_DIGITS));
    initCompanionTables();

    if (convertCoordsToMicrosAndFractions(&enc.coord32, &enc.fraclat, &enc.fraclon, lat, lon) < 0) {
        return 0;
    }

    if (territoryContext < _TERRITORY_MIN) // ALL results?
    {
#ifndef NO_FAST_ENCODE
        {
            const int sum = enc.coord32.lonMicroDeg + enc.coord32.latMicroDeg;
            int coord = enc.coord32.lonMicroDeg;
            int i = 0; // pointer into REDIVAR
            for (;;) {
                const int r = REDIVAR[i++];
                if (r >= 0 && r < 1024) {
                    // leaf?
                    int j;
                    for (j = 0; j <= r; j++) {
                        const enum Territory ccode = (j == r ? TERRITORY_AAA : (enum Territory)REDIVAR[i + j]);
                        encoderEngine(ccode, &enc, stop_with_one_result, extraDigits, requiredEncoder, TERRITORY_NONE);
                        if ((stop_with_one_result || (requiredEncoder >= 0)) && (enc.mapcodes->count > 0)) {
                            break;
                        }
                    }
                    break;
                }
                else {
                    coord = sum - coord;
                    if (coord > r) {
                        i = REDIVAR[i];
                    }
                    else {
                        i++;
                    }
                }
            }
        }
#else
        {
            int i;
            for (i = _TERRITORY_MIN + 1; i < _TERRITORY_MAX; i++) {
                encoderEngine((enum Territory)i, &enc, stop_with_one_result, extraDigits, requiredEncoder,
                              TERRITORY_NONE);
                if ((stop_with_one_result || (requiredEncoder >= 0)) && (enc.mapcodes->count > 0)) {
                    break;
                }
            }
        }
#endif
    }
    else {
        encoderEngine(territoryContext, &enc, stop_with_one_result, extraDigits, requiredEncoder, TERRITORY_NONE);
    }
    return mapcodes->count;
}

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

typedef struct {
    // input
    MapcodeElements mapcodeElements;
    const char* orginput; // original full input string
    const char* mapcode; // input mapcode (first character of proper mapcode excluding territory code)
    const char* extension; // input extension (or empty)
    enum Territory context; // input territory context (or TERRITORY_NONE)
    const char* iso; // input territory alphacode (context)
    // output
    Point result; // result
    Point32 coord32; // result in integer arithmetic (microdegrees)
    MapcodeZone zone; // result zone (in "DegreeFractions")
} DecodeRec;


// decode the high-precision extension (0-8 characters)
// this routine takes the integer-arithmeteic decoding results (dec->coord32), adds precision,
// and determines result zone (dec->zone); returns negative in case of error.
static enum MapcodeError decodeExtension(DecodeRec* dec,
                                         int dividerx4, int dividery,
                                         const int lon_offset4,
                                         const int extremeLat32, const int maxLon32) {
    double lat1, lon4;
    const char* extrapostfix = dec->extension;
    int lon32 = 0;
    int lat32 = 0;
    int processor = 1;
    int odd = 0;
    ASSERT(dec);
    if (strlen(extrapostfix) > MAX_PRECISION_DIGITS) {
        return ERR_EXTENSION_INVALID_LENGTH;
    }
    while (*extrapostfix) {
        int column1, row1, column2, row2;
        const int c1 = decodeChar(*extrapostfix++);
        if (c1 < 0 || c1 == 30) {
            return ERR_EXTENSION_INVALID_CHARACTER;
        } // illegal extension character
        row1 = (c1 / 5);
        column1 = (c1 % 5);
        if (*extrapostfix) {
            const int c2 = decodeChar(*extrapostfix++);
            if (c2 < 0 || c2 == 30) {
                return ERR_EXTENSION_INVALID_CHARACTER;
            } // illegal extension character
            row2 = (c2 / 6);
            column2 = (c2 % 6);
        }
        else {
            odd = 1;
            row2 = 0;
            column2 = 0;
        }

        processor *= 30;
        lon32 = lon32 * 30 + column1 * 6 + column2;
        lat32 = lat32 * 30 + row1 * 5 + row2;
    }

    while (processor < MAX_PRECISION_FACTOR) {
        dividerx4 *= 30;
        dividery *= 30;
        processor *= 30;
    }

    lon4 = (dec->coord32.lonMicroDeg * 4 * (double)MAX_PRECISION_FACTOR) + ((lon32 * (double)dividerx4)) +
        (lon_offset4 * (double)MAX_PRECISION_FACTOR);
    lat1 = (dec->coord32.latMicroDeg * (double)MAX_PRECISION_FACTOR) + ((lat32 * (double)dividery));

    // determine the range of coordinates that are encoded to this mapcode
    if (odd) {
        setFromFractions(&dec->zone, lat1, lon4, 5 * dividery, 6 * dividerx4);
    }
    else {
        setFromFractions(&dec->zone, lat1, lon4, dividery, dividerx4);
    }

    // restrict the coordinate range to the extremes that were provided
    if (dec->zone.fmaxx > maxLon32 * MICROLON_TO_FRACTIONS_FACTOR) {
        dec->zone.fmaxx = maxLon32 * MICROLON_TO_FRACTIONS_FACTOR;
    }
    if (dividery >= 0) {
        if (dec->zone.fmaxy > extremeLat32 * MICROLAT_TO_FRACTIONS_FACTOR) {
            dec->zone.fmaxy = extremeLat32 * MICROLAT_TO_FRACTIONS_FACTOR;
        }
    }
    else {
        if (dec->zone.fminy < extremeLat32 * MICROLAT_TO_FRACTIONS_FACTOR) {
            dec->zone.fminy = extremeLat32 * MICROLAT_TO_FRACTIONS_FACTOR;
        }
    }
    if (isEmpty(&dec->zone)) {
        return ERR_EXTENSION_UNDECODABLE;
    }
    return ERR_OK;
}


// decode 'code' until either a dot or an end-of-string is encountered
static int decodeBase31(const char* code) {
    int value = 0;
    ASSERT(code);
    while (*code != '.' && *code != 0) {
        value = value * 31 + decodeChar(*code++);
    }
    return value;
}


static void decodeTriple(const char* result, int* difx, int* dify) {
    // decode the first character
    const int c1 = decodeChar(*result++);
    ASSERT(result - 1);
    ASSERT(difx);
    ASSERT(dify);
    if (c1 < 24) {
        int m = decodeBase31(result);
        *difx = (c1 % 6) * 28 + (m / 34);
        *dify = (c1 / 6) * 34 + (m % 34);
    }
    else // bottom row
    {
        int x = decodeBase31(result);
        *dify = (x % 40) + 136;
        *difx = (x / 40) + 24 * (c1 - 24);
    }
} // decodeTriple

static void decodeSixWide(const int v, const int width, const int height,
                          int* x, int* y) {
    int w;
    int D = 6;
    int col = v / (height * 6);
    const int maxcol = (width - 4) / 6;
    ASSERT(x);
    ASSERT(y);
    if (col >= maxcol) {
        col = maxcol;
        D = width - maxcol * 6;
    }
    w = v - (col * height * 6);

    *x = col * 6 + (w % D);
    *y = height - 1 - (w / D);
}

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

// decodes dec->mapcode in context of territory rectangle m; returns negative if error
static enum MapcodeError decodeGrid(DecodeRec* dec, const int m, const int hasHeaderLetter) {
    const char* input = (hasHeaderLetter ? dec->mapcode + 1 : dec->mapcode);
    const int codexlen = (int)(strlen(input) - 1);
    int prelen = (int)(strchr(input, '.') - input);
    char result[MAX_PROPER_MAPCODE_ASCII_LEN + 1];
    ASSERT(dec);

    if (codexlen > MAX_PROPER_MAPCODE_ASCII_LEN) {
        return ERR_BAD_MAPCODE_LENGTH;
    }
    if (prelen > 5) {
        return ERR_UNEXPECTED_DOT;
    }

    strcpy(result, input);
    if (prelen == 1 && codexlen == 5) {
        result[1] = result[2];
        result[2] = '.';
        prelen++;
    }

    {
        const int postlen = codexlen - prelen;

        int divx, divy;

        divy = SMART_DIV(m);
        ASSERT(divy > 0);
        if (divy == 1) {
            divx = X_SIDE[prelen];
            divy = Y_SIDE[prelen];
        }
        else {
            divx = (NC[prelen] / divy);
        }

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

        {
            int relx, rely;
            int v = decodeBase31(result);

            if (divx != divy && prelen > 2) {
                // special grid, useful when prefix is 3 or more, and not a nice 961x961
                decodeSixWide(v, divx, divy, &relx, &rely);
            }
            else {
                relx = (v / divy);
                rely = divy - 1 - (v % divy);
            }

            if (relx < 0 || rely < 0 || relx >= divx || rely >= divy) {
                return ERR_MAPCODE_UNDECODABLE; // type 4 "usa A222.22AA"
            }


            {
                const TerritoryBoundary* b = TERRITORY_BOUNDARY(m);
                const int ygridsize = (b->maxy - b->miny + divy - 1) / divy; // microdegrees per cell
                const int xgridsize = (b->maxx - b->minx + divx - 1) / divx; // microdegrees per cell

                // encode relative to THE CORNER of this cell
                rely = b->miny + (rely * ygridsize);
                relx = b->minx + (relx * xgridsize);

                {
                    const int xp = X_SIDE[postlen];
                    const int dividerx = ((xgridsize + xp - 1) / xp);
                    const int yp = Y_SIDE[postlen];
                    const int dividery = ((ygridsize + yp - 1) / yp);
                    // decoderelative

                    {
                        char* r = result + prelen + 1;
                        int difx, dify;

                        if (postlen == 3) // decode special
                        {
                            decodeTriple(r, &difx, &dify);
                        }
                        else {
                            if (postlen == 4) {
                                char t = r[1];
                                r[1] = r[2];
                                r[2] = t;
                            } // swap
                            v = decodeBase31(r);
                            difx = (v / yp);
                            dify = (v % yp);
                            if (postlen == 4) {
                                char t = r[1];
                                r[1] = r[2];
                                r[2] = t;
                            } // swap back
                        }

                        // reverse y-direction
                        dify = yp - 1 - dify;

                        dec->coord32.lonMicroDeg = relx + (difx * dividerx);
                        dec->coord32.latMicroDeg = rely + (dify * dividery);
                        if (!fitsInsideBoundaries(&dec->coord32, TERRITORY_BOUNDARY(m))) {
                            return ERR_MAPCODE_UNDECODABLE; // type 2 "NLD Q000.000"
                        }

                        {
                            const int decodeMaxx = ((relx + xgridsize) < b->maxx) ? (relx + xgridsize) : b->maxx;
                            const int decodeMaxy = ((rely + ygridsize) < b->maxy) ? (rely + ygridsize) : b->maxy;
                            return decodeExtension(dec, dividerx << 2, dividery, 0, decodeMaxy, decodeMaxx); // grid
                        }
                    } // decoderelative
                }
            }
        }
    }
}


// decodes dec->mapcode in context of territory rectangle m, territory dec->context
// Returns negative in case of error
static enum MapcodeError decodeNameless(DecodeRec* dec, int m) {
    int A, F;
    char input[8];
    const int codexm = coDex(m);
    const int codexlen = (int)(strlen(dec->mapcode) - 1);
    ASSERT(dec);
    ASSERT((0 <= m) && (m <= MAPCODE_BOUNDARY_MAX));
    if (codexlen != 4 && codexlen != 5) {
        return ERR_BAD_MAPCODE_LENGTH;
    } // solve bad args

    // copy without dot
    {
        const int dc = (codexm != 22) ? 2 : 3;
        strcpy(input, dec->mapcode);
        strcpy(input + dc, dec->mapcode + dc + 1);
    }

    A = countNamelessRecords(m, firstRec(dec->context));
    F = firstNamelessRecord(m, firstRec(dec->context));

    {
        const int p = 31 / A;
        const int r = 31 % A;
        int v = 0;
        int SIDE;
        int swapletters = 0;
        int xSIDE;
        int X;
        const TerritoryBoundary* b;

        // make copy of input, so we can swap around letters during the decoding
        char result[32];
        strcpy(result, input);

        // now determine X = index of first area, and SIDE
        if (codexm != 21 && A <= 31) {
            const int offset = decodeChar(*result);

            if (offset < r * (p + 1)) {
                X = offset / (p + 1);
            }
            else {
                swapletters = ((p == 1) && (codexm == 22));
                X = r + (offset - (r * (p + 1))) / p;
            }
        }
        else if (codexm != 21 && A < 62) {
            X = decodeChar(*result);
            if (X < (62 - A)) {
                swapletters = (codexm == 22);
            }
            else {
                X = X + (X - (62 - A));
            }
        }
        else // code==21 || A>=62
        {
            const int BASEPOWER = (codexm == 21) ? 961 * 961 : 961 * 961 * 31;
            int BASEPOWERA = (BASEPOWER / A);

            if (A == 62) {
                BASEPOWERA++;
            }
            else {
                BASEPOWERA = 961 * (BASEPOWERA / 961);
            }

            v = decodeBase31(result);
            X = (v / BASEPOWERA);
            v %= BASEPOWERA;
        }


        if (swapletters) {
            if (!IS_SPECIAL_SHAPE(F + X)) {
                const char t = result[codexlen - 3];
                result[codexlen - 3] = result[codexlen - 2];
                result[codexlen - 2] = t;
            }
        }

        if (codexm != 21 && A <= 31) {
            v = decodeBase31(result);
            if (X > 0) {
                v -= (X * p + (X < r ? X : r)) * (961 * 961);
            }
        }
        else if (codexm != 21 && A < 62) {
            v = decodeBase31(result + 1);
            if (X >= (62 - A)) {
                if (v >= (16 * 961 * 31)) {
                    v -= (16 * 961 * 31);
                    X++;
                }
            }
        }

        m = (F + X);

        SIDE = SMART_DIV(m);
        ASSERT(SIDE > 0);
        xSIDE = SIDE;

        b = TERRITORY_BOUNDARY(m);

        // decode
        {
            int dx, dy;

            if (IS_SPECIAL_SHAPE(m)) {
                xSIDE *= SIDE;
                SIDE = 1 + ((b->maxy - b->miny) / 90); // side purely on y range
                xSIDE = xSIDE / SIDE;

                decodeSixWide(v, xSIDE, SIDE, &dx, &dy);
                dy = SIDE - 1 - dy;
            }
            else {
                dy = v % SIDE;
                dx = v / SIDE;
            }


            if (dx >= xSIDE) {
                return ERR_MAPCODE_UNDECODABLE; // type 1 "NLD ZZ.ZZ"
            }

            {
                const int dividerx4 = xDivider4(b->miny, b->maxy); // *** note: dividerx4 is 4 times too large!
                const int dividery = 90;

                // *** note: FIRST multiply, then divide... more precise, larger rects
                dec->coord32.lonMicroDeg = b->minx + ((dx * dividerx4) / 4);
                dec->coord32.latMicroDeg = b->maxy - (dy * dividery);

                return decodeExtension(dec, dividerx4, -dividery, ((dx * dividerx4) % 4), b->miny, b->maxx); // nameless
            }
        }
    }
}


// decodes dec->mapcode in context of territory rectangle m or one of its mates
static enum MapcodeError decodeAutoHeader(DecodeRec* dec, int m) {
    const char* input = dec->mapcode;
    const int codexm = coDex(m);
    const char* dot = strchr(input, '.');
    int STORAGE_START = 0;
    int value;
    ASSERT(dec);
    ASSERT((0 <= m) && (m <= MAPCODE_BOUNDARY_MAX));
    if (dot == NULL) {
        return ERR_DOT_MISSING;
    }

    value = decodeBase31(input); // decode top
    value *= (961 * 31);

    for (; coDex(m) == codexm && REC_TYPE(m) > 1; m++) {
        const TerritoryBoundary* b = TERRITORY_BOUNDARY(m);
        // determine how many cells
        int H = (b->maxy - b->miny + 89) / 90; // multiple of 10m
        const int xdiv = xDivider4(b->miny, b->maxy);
        int W = ((b->maxx - b->minx) * 4 + (xdiv - 1)) / xdiv;
        int product;

        // decode
        H = 176 * ((H + 176 - 1) / 176);
        W = 168 * ((W + 168 - 1) / 168);
        product = (W / 168) * (H / 176) * 961 * 31;

        if (REC_TYPE(m) == 2) {
            const int GOODROUNDER = codexm >= 23 ? (961 * 961 * 31) : (961 * 961);
            product = ((STORAGE_START + product + GOODROUNDER - 1) / GOODROUNDER) * GOODROUNDER - STORAGE_START;
        }

        if (value >= STORAGE_START && value < STORAGE_START + product) {
            const int dividerx = (b->maxx - b->minx + W - 1) / W;
            const int dividery = (b->maxy - b->miny + H - 1) / H;

            value -= STORAGE_START;
            value /= (961 * 31);

            {
                int difx, dify;
                decodeTriple(dot + 1, &difx, &dify); // decode bottom 3 chars
                {
                    const int vx = (value / (H / 176)) * 168 + difx; // is vx/168
                    const int vy = (value % (H / 176)) * 176 + dify; // is vy/176

                    dec->coord32.latMicroDeg = b->maxy - vy * dividery;
                    dec->coord32.lonMicroDeg = b->minx + vx * dividerx;

                    if ((dec->coord32.lonMicroDeg < b->minx) || (dec->coord32.lonMicroDeg >= b->maxx) ||
                        (dec->coord32.latMicroDeg < b->miny) ||
                        (dec->coord32.latMicroDeg > b->maxy)) // *** CAREFUL! do this test BEFORE adding remainder...
                    {
                        return ERR_MAPCODE_UNDECODABLE; // type 5 "atf hhh.hhh"
                    }
                }
            }

            return decodeExtension(dec, dividerx << 2, -dividery, 0, b->miny, b->maxx); // autoheader decode
        }
        STORAGE_START += product;
    } // for j
    return ERR_MAPCODE_UNDECODABLE; // type 6 "ASM zz.zzh"
}

/**
 * ROMAN / ABJAD
 *
 */


// Returns romanised version of character, or question mark in not recognized
static unsigned char getRomanVersionOf(UWORD w) {
    if (w > ROMAN_VERSION_MAX_CHAR || ROMAN_VERSION_OF[w >> 6] == NULL) {
        return '?';
    }
    return (unsigned char)ROMAN_VERSION_OF[w >> 6][w & 63];
}


static void convertFromAbjad(char* s) {
    int len, dot, form, c;
    char* postfix = strchr(s, '-');
    {
        const char* dotptr = strchr(s, '.');
        dot = dotptr ? (int)(dotptr - s) : -1;
    }
    if (dot < 2 || dot > 5) {
        return;
    }
    if (postfix) {
        *postfix = 0;
    }

    unpackIfAllDigits(s);

    len = (int)strlen(s);
    form = (dot >= 2 && dot <= 5 ? dot * 10 + (len - dot - 1) : 0);

    if (form == 23) {
        c = decodeChar(s[3]) * 8 + (decodeChar(s[4]) - 18);
        if (c >= 0 && c < 31) {
            //          s[0] = s[0];
            //          s[1] = s[1];
            //          s[2] = '.';
            s[3] = ENCODE_CHARS[c];
            s[4] = s[5];
            s[5] = 0;
        }
    }
    else if (form == 24) {
        c = decodeChar(s[3]) * 8 + (decodeChar(s[4]) - 18);
        if (c >= 0 && c < 63) {
            //          s[0] = s[0];
            //          s[1] = s[1];
            //          s[2] = '.';
            s[3] = '.';
            s[4] = s[5];
            s[5] = s[6];
            s[6] = 0;
            if (c >= 32) {
                s[2] = ENCODE_CHARS[c - 32];
            }
            else {
                s[3] = ENCODE_CHARS[c];
            }
        }
    }
    else if (form == 34) {
        c = (decodeChar(s[2]) * 10) + (decodeChar(s[5]) - 7);
        if (c >= 0 && c < 93) {
            //          s[0] = s[0];
            //          s[1] = s[1];
            s[2] = '.';
            //          s[3] = '.';
            //          s[4] = s[4];
            s[5] = s[6];
            s[6] = s[7];
            s[7] = 0;

            if (c < 31) {
                s[3] = ENCODE_CHARS[c];
            }
            else if (c < 62) {
                s[2] = ENCODE_CHARS[c - 31];
            }
            else {
                s[2] = ENCODE_CHARS[c - 62];
                s[3] = s[4];
                s[4] = '.';
            }
        }
    }
    else if (form == 35) {
        c = (decodeChar(s[2]) * 8) + (decodeChar(s[6]) - 18);
        if (c >= 0 && c < 63) {
            //          s[0] = s[0];
            //          s[1] = s[1];
            //          s[3] = '.';
            //          s[4] = s[4];
            //          s[5] = s[5];
            s[6] = s[7];
            s[7] = s[8];
            s[8] = 0;
            if (c >= 32) {
                s[2] = ENCODE_CHARS[c - 32];
                s[3] = s[4];
                s[4] = '.';
            }
            else {
                s[2] = ENCODE_CHARS[c];
            }
        }
    }
    else if (form == 45) {
        c = (decodeChar(s[2]) * 100) + (decodeChar(s[5]) * 10) + (decodeChar(s[8]) - 39);
        if (c >= 0 && c < 961) {
            //          s[0] = s[0];
            //          s[1] = s[1];
            s[2] = ENCODE_CHARS[c / 31];
            //          s[3] = s[3];
            //          s[4] = '.';
            s[5] = s[6];
            s[6] = s[7];
            s[7] = s[9];
            s[8] = ENCODE_CHARS[c % 31];
            s[9] = 0;
        }
    }
    else if (form == 55) {
        c = (decodeChar(s[2]) * 100) + (decodeChar(s[6]) * 10) + (decodeChar(s[9]) - 39);
        if (c >= 0 && c < 961) {
            //          s[0] = s[0];
            //          s[1] = s[1];
            s[2] = ENCODE_CHARS[c / 31];
            //          s[3] = s[3];
            //          s[4] = s[4];
            //          s[5] = '.';
            s[6] = s[7];
            s[7] = s[8];
            s[8] = s[10];
            s[9] = ENCODE_CHARS[c % 31];
            s[10] = 0;
        }
    }
    repackIfAllDigits(s, 0);
    if (postfix) {
        len = (int)strlen(s);
        *postfix = '-';
        memmove(s + len, postfix, strlen(postfix) + 1);
    }
}


/**
 * Returns the alphabet of given UTF8 (of ASCII) string (based on the
 * first recognizable non-Latin character).
 *
 * Arguments:
 *      utf8   - Zero-terminated UTF8 (or ASCII) string
 *
 * Returns:
 *      ALPHABET_ROMAN if all characters are in ASCII range 0..0xBF.
 *      otherwise returns the alphabet of the first different character
 *      encountered, or negative (_ALPHABET_MIN) if it isn't recognized.
 */
static enum Alphabet recognizeAlphabetUtf8(const char* utf8) {
    ASSERT(utf8);
    while (*utf8 != 0) {
        int c = (unsigned char)*utf8++;
        if (c >= 0xC0) {
            enum Alphabet alphabet;
            int c2 = (unsigned char)*utf8++;
            if (c2 < 0x80) {
                return _ALPHABET_MIN; // utf8 error!
            }
            c = ((c - 0xC0) << 6) + (c2 & 63);
            if (c >= 0x800) {
                int c3 = (unsigned char)*utf8++;
                c = ((c - 0x800) << 6) + (c3 & 63);
                if (c3 < 0x80 || c > 0xFFFF) {
                    return _ALPHABET_MIN; // utf8 error!
                }
            }
            alphabet = ALPHABET_OF_CHAR((UWORD) c);
            if (alphabet != ALPHABET_ROMAN) {
                return alphabet;
            }
        }
    }
    return ALPHABET_ROMAN;
}


///////////////////////////////////////////////////////////////////////////////////////////////
//
//  compareWithMapcodeFormat & parseMapcode
//
///////////////////////////////////////////////////////////////////////////////////////////////


// 32=busyextension 64=end territory 128(256)=end of clean mapcode(with extension) 512=end of extension
static const int STATE_MACHINE[27][6] = {
    // SPACE                       DOT                 DETTER                      VOWEL                            ZERO                      HYPHEN
    // 0 start === looking for very first detter
    {0, ERR_UNEXPECTED_DOT, 1, 1, ERR_DOT_MISSING, ERR_UNEXPECTED_HYPHEN},
    // 1 L/P === det:LL vowel:TA
    {ERR_BAD_TERRITORY_FORMAT, ERR_UNEXPECTED_DOT, 2, 23, ERR_DOT_MISSING, ERR_BAD_TERRITORY_FORMAT},
    // 2 LL/PP === white: TT waitprefix | dot: PP. | det:LLL/PPP | vowel:TTA | hyphen:TT-
    {
        18 |
        64,
        6, 3, 24, ERR_DOT_MISSING, 14
    },
    // 3 LLL/PPP === white: TTT prefix | dot: PPP. mapcode | det: PPPP | hyphen: TTT-
    {
        18 |
        64,
        6, 4, ERR_INVALID_VOWEL, ERR_DOT_MISSING, 14
    },
    // 4 PPPP === dot: PPPP. | det: PPPPP
    {ERR_BAD_TERRITORY_FORMAT, 6, 5, ERR_INVALID_VOWEL, ERR_DOT_MISSING, ERR_BAD_TERRITORY_FORMAT},
    // 5 PPPPP === must get dot now! Dot:PPPPP.
    {
        ERR_BAD_TERRITORY_FORMAT, 6, ERR_INVALID_MAPCODE_FORMAT, ERR_INVALID_VOWEL, ERR_DOT_MISSING,
        ERR_BAD_TERRITORY_FORMAT
    },
    // 6 prefix. === get first postfix! det: prefix.L | vowel: prefix.A
    {ERR_INVALID_MAPCODE_FORMAT, ERR_UNEXPECTED_DOT, 7, 25, ERR_MAPCODE_INCOMPLETE, ERR_UNEXPECTED_HYPHEN},
    // 7 prefix.L === get 2nd postfix! det: prefix.LL | vowel: prefix.LA
    {ERR_INVALID_MAPCODE_FORMAT, ERR_UNEXPECTED_DOT, 8, 25, ERR_MAPCODE_INCOMPLETE, ERR_UNEXPECTED_HYPHEN},
    // 8 prefix.LL === get 3d postfix! white:trail | det: prefix.LLL | vowel: prefix.LLA | zero:done | hyphen: mc-
    {
        22 | 128, ERR_UNEXPECTED_DOT, 9, 25, STATE_GO |
        128,
        11 |
        256
    },
    // 9 prefix.LLL === white:trail | zero:done | hyphen:mc-
    {
        22 |
        128,
        ERR_UNEXPECTED_DOT, 10, 25, STATE_GO |
        128,
        11 |
        256
    },
    //10 prefix.LLLL === white:trail | zero:done | hyphen:mc- | det/vowel = postfix full
    {
        22 |
        128,
        ERR_UNEXPECTED_DOT, 13, 13, STATE_GO |
        128,
        11 |
        256
    },

    //11 mc- === MUST get first precision detter
    {
        ERR_EXTENSION_INVALID_LENGTH, ERR_UNEXPECTED_DOT, 12, ERR_EXTENSION_INVALID_CHARACTER, ERR_MAPCODE_INCOMPLETE,
        ERR_UNEXPECTED_HYPHEN
    },
    //12 mc-L* === Keep reading precision detters | white=trail | zero=done
    {
        22 | 512, ERR_UNEXPECTED_DOT, 12 | 32, ERR_EXTENSION_INVALID_CHARACTER,
        STATE_GO |
        512,
        ERR_UNEXPECTED_HYPHEN
    },

    //13 prefix.LLLLL ===
    {
        22 |
        128,
        ERR_UNEXPECTED_DOT, ERR_INVALID_MAPCODE_FORMAT, ERR_INVALID_VOWEL, STATE_GO |
        128,
        11 |
        256
    },

    //14 TC- === get first state letter
    {ERR_BAD_TERRITORY_FORMAT, ERR_UNEXPECTED_DOT, 15, 15, ERR_BAD_TERRITORY_FORMAT, ERR_UNEXPECTED_HYPHEN},
    //15 TC-S === get 2nd state letter
    {ERR_BAD_TERRITORY_FORMAT, ERR_UNEXPECTED_DOT, 16, 16, ERR_BAD_TERRITORY_FORMAT, ERR_UNEXPECTED_HYPHEN},
    //16 TC-SS === white:waitprefix | det/vow:TC-SSS
    {
        18 |
        64,
        ERR_UNEXPECTED_DOT, 17, 17, ERR_DOT_MISSING, ERR_UNEXPECTED_HYPHEN
    },
    //17 TC-SSS === white:waitprefix
    {
        18 |
        64,
        ERR_UNEXPECTED_DOT, ERR_BAD_TERRITORY_FORMAT, ERR_BAD_TERRITORY_FORMAT, ERR_DOT_MISSING, ERR_UNEXPECTED_HYPHEN
    },

    //18 TC waitprefix === skip more whitespace, MUST get 1st prefix letter/vowel
    {18, ERR_UNEXPECTED_DOT, 19, 19, ERR_DOT_MISSING, ERR_UNEXPECTED_HYPHEN},
    //19 TC P === get second prefix detter
    {ERR_DOT_MISSING, ERR_UNEXPECTED_DOT, 20, ERR_INVALID_VOWEL, ERR_DOT_MISSING, ERR_UNEXPECTED_HYPHEN},
    //20 TC PP === dot:prefix. | det:TC PPP
    {ERR_DOT_MISSING, 6, 21, ERR_INVALID_VOWEL, ERR_DOT_MISSING, ERR_UNEXPECTED_HYPHEN},
    //21 TC PPP === dot:prefix. | det:PPPP
    {ERR_DOT_MISSING, 6, 4, ERR_INVALID_VOWEL, ERR_DOT_MISSING, ERR_UNEXPECTED_HYPHEN},

    //22 trailing === skip whitespace until end of string
    {22, ERR_UNEXPECTED_DOT, ERR_TRAILING_CHARACTERS, ERR_TRAILING_CHARACTERS, STATE_GO, ERR_UNEXPECTED_HYPHEN},

    //23 TA === white:waitprefix | det: TAT | vowel:TAA | hyphen:TC-
    {
        18 |
        64,
        ERR_INVALID_VOWEL, 24, 24, ERR_DOT_MISSING, 14
    },
    //24 TTA/TAT/TAA === space:TC waitprefix | hyphen:TC-
    {
        18 |
        64,
        ERR_INVALID_VOWEL, ERR_INVALID_VOWEL, ERR_INVALID_VOWEL, ERR_DOT_MISSING, 14
    },

    //25 prefix.[L*]A === white:trail | det/vow:full mc | zero:done | hyphen:mc-
    {
        22 |
        128,
        ERR_UNEXPECTED_DOT, 26, 26, STATE_GO |
        128,
        11 |
        256
    },
    //26 prefix.[L*]AL === white:trail | zero:done | hyphen:mc-
    {
        22 |
        128,
        ERR_UNEXPECTED_DOT, ERR_INVALID_VOWEL, ERR_INVALID_VOWEL, STATE_GO |
        128,
        11 |
        256
    },
};


// Returns 0 if ok, negative in case of error (where -999 represents "may BECOME a valid mapcode if more characters are added)
static enum MapcodeError parseMapcodeString(MapcodeElements* mapcodeElements, const char* string, int interpretAsUtf16,
                                            enum Territory territory) {
    const UWORD* utf16 = (const UWORD*)string;
    int isAbjad = 0;
    const unsigned char* utf8 = (unsigned char*)string;
    int extensionLength = 0;
    char* cleanPtr = NULL;
    int nondigits = 0, vowels = 0;
    int state = 0;
    ASSERT(string);
    if (mapcodeElements) {
        *mapcodeElements->precisionExtension = 0;
        *mapcodeElements->territoryISO = 0;
        cleanPtr = mapcodeElements->properMapcode;
    }
    for (;;) {
        int newstate, token;
        unsigned char cx;
        // handle utf16
        if (interpretAsUtf16) {
            const enum Alphabet alphabet = ALPHABET_OF_CHAR(*utf16);
            if (alphabet == ALPHABET_GREEK || alphabet == ALPHABET_HEBREW ||
                alphabet == ALPHABET_ARABIC || alphabet == ALPHABET_KOREAN) {
                isAbjad = 1;
            }
            cx = getRomanVersionOf(*utf16++);
        }
        else {
            cx = *utf8++;
        }
        // recognize token: decode returns -2=a -3=e -4=0, 0..9 for digit or "o" or "i", 10..31 for char, -1 for illegal char
        if (cx == '.') {
            token = TOKENDOT;
            if (mapcodeElements) {
                mapcodeElements->indexOfDot = (int)(cleanPtr - mapcodeElements->properMapcode);
            }
            if (mapcodeElements) {
                *cleanPtr++ = cx;
            }
        }
        else if (cx == '-') {
            token = TOKENHYPH;
            if (mapcodeElements) {
                *cleanPtr++ = cx;
            }
        }
        else if (cx == 0) {
            token = TOKENZERO;
        }
        else if ((cx == ' ') || (cx == '\t')) {
            token = TOKENSEP;
        }
        else {
            signed char c;
            if (cx >= 0xC0) {
                // utf8 character
                unsigned char c2 = *utf8++;
                int w = ((cx - 0xC0) << 6) + (c2 & 63);
                if (c2 < 0x80) {
                    return ERR_INVALID_CHARACTER; // utf8 error
                }
                if (w >= 0x800) {
                    int c3 = (int)*utf8++;
                    w = ((w - 0x800) << 6) + (c3 & 63);
                    if (c3 < 0x80 || w > 0xFFFF) {
                        return ERR_INVALID_CHARACTER; // utf8 error
                    }
                }
                {
                    const enum Alphabet alphabet = ALPHABET_OF_CHAR(w);
                    if (alphabet == ALPHABET_GREEK || alphabet == ALPHABET_HEBREW ||
                        alphabet == ALPHABET_ARABIC || alphabet == ALPHABET_KOREAN) {
                        isAbjad = 1;
                    }
                }
                cx = getRomanVersionOf((UWORD)w);
            }
            c = decodeChar(cx);
            if (c < 0) {
                // vowel or illegal?
                if (c == -1) {
                    // illegal?
                    return ERR_INVALID_CHARACTER;
                }
                token = TOKENVOWEL;
                vowels++;
                if (mapcodeElements) {
                    *cleanPtr++ = (char)toupper(cx);
                }
            }
            else if (c < 10) {
                // digit
                token = TOKENCHR; // digit
                if (mapcodeElements) {
                    *cleanPtr++ = (char)toupper(cx);
                }
            }
            else {
                // character B-Z
                token = TOKENCHR;
                if (!extensionLength) {
                    nondigits++;
                }
                if (mapcodeElements) {
                    *cleanPtr++ = (char)toupper(cx);
                }
            }
        }
        newstate = STATE_MACHINE[state][token];
        if (newstate >= 32) {
            if (newstate >= 512) {
                // end of extension
                if (mapcodeElements) {
                    *cleanPtr = 0;
                    cleanPtr = mapcodeElements->precisionExtension;
                }
            }
            else if (newstate >= 128) {
                if (newstate >= 256) {
                    // start of extension
                    extensionLength = 1;
                    cleanPtr--; // get rid of hyphen
                }
                // end of proper mapcode
                if (mapcodeElements) {
                    *cleanPtr = 0;
                    cleanPtr = mapcodeElements->precisionExtension;
                }
            }
            else if (newstate >= 64) {
                // end of territory
                nondigits = vowels = 0;
                if (mapcodeElements) {
                    int len = (int)(cleanPtr - mapcodeElements->properMapcode);
                    ASSERT(len < MAX_ISOCODE_ASCII_LEN);
                    lengthCopy(mapcodeElements->territoryISO, mapcodeElements->properMapcode, len,
                               MAX_ISOCODE_ASCII_LEN + 1);
                    cleanPtr = mapcodeElements->properMapcode;
                }
            }
            else {
                // add to extension
                if (++extensionLength > MAX_PRECISION_DIGITS) {
                    return ERR_EXTENSION_INVALID_LENGTH;
                }
            }
            newstate &= 31;
        }

        if (newstate < 0) {
            return (enum MapcodeError)newstate;
        }
        else if (newstate == STATE_GO) {
            if (vowels > 3 || (nondigits == 1 && vowels > 1) || (nondigits > 1 && vowels > 0)) {
                return ERR_INVALID_VOWEL;
            }
            else if (nondigits == 0 && vowels == 0) {
                return ERR_ALL_DIGIT_CODE;
            }
            if (mapcodeElements) {
                if (*mapcodeElements->properMapcode == 'A') {
                    unpackIfAllDigits(mapcodeElements->properMapcode);
                    repackIfAllDigits(mapcodeElements->properMapcode, 0);
                }
                if (isAbjad) {
                    convertFromAbjad(mapcodeElements->properMapcode);
                    mapcodeElements->indexOfDot = (int)(strchr(mapcodeElements->properMapcode, '.') -
                        mapcodeElements->properMapcode);
                }
                if (*mapcodeElements->territoryISO) {
                    mapcodeElements->territoryCode = getTerritoryCode(mapcodeElements->territoryISO, territory);
                    if (mapcodeElements->territoryCode < _TERRITORY_MIN) {
                        return ERR_UNKNOWN_TERRITORY;
                    }
                }
                else {
                    mapcodeElements->territoryCode = territory;
                }
                if ((mapcodeElements->territoryCode == TERRITORY_MEX) && (strlen(mapcodeElements->properMapcode) < 8)) {
                    // special case: short MEX codes are handled in the state (which ALSO has iso code MEX)
                    mapcodeElements->territoryCode = TERRITORY_MX_MX;
                }
            }
            return ERR_OK;
        }
        state = newstate;
    }
    ASSERT(0);
}


enum MapcodeError compareWithMapcodeFormatUtf8(const char* utf8String) {
    ASSERT(utf8String);
    return parseMapcodeString(NULL, utf8String, FLAG_UTF8_STRING, TERRITORY_NONE);
}


enum MapcodeError compareWithMapcodeFormatUtf16(const UWORD* Utf16String) {
    ASSERT(Utf16String);
    return parseMapcodeString(NULL, (const char*)Utf16String, FLAG_UTF16_STRING, TERRITORY_NONE);
}


/**
 * Main decoder engine that converts a mapcode string to coordinates.
 * Handles territory context, validates format, and iterates through
 * possible territory boundaries to find the correct decoding.
 * Returns ERR_OK on success, or appropriate error code on failure.
 */
static enum MapcodeError decoderEngine(DecodeRec* dec, int parseFlags) {
    enum Territory ccode;
    enum MapcodeError err;
    int codex;
    int from;
    int upto;
    int i;
    char* s;
    int wasAllDigits = 0;
    ASSERT(dec);
    initCompanionTables();

    // Parse the mapcode string into its components (territory, proper mapcode, extension)
    err = parseMapcodeString(&dec->mapcodeElements, dec->orginput, parseFlags, dec->context);
    if (err) {
        // Clear all parsed fields in case of error to ensure clean state
        dec->mapcodeElements.territoryISO[0] = 0;
        dec->mapcodeElements.properMapcode[0] = 0;
        dec->mapcodeElements.precisionExtension[0] = 0;
        return err;
    }

    ccode = dec->mapcodeElements.territoryCode;
    dec->context = ccode;
    dec->mapcode = dec->mapcodeElements.properMapcode;
    dec->extension = dec->mapcodeElements.precisionExtension;
    codex = dec->mapcodeElements.indexOfDot * 9 + (int)strlen(dec->mapcodeElements.properMapcode) - 1;
    s = dec->mapcodeElements.properMapcode;

    if (strchr(s, 'A') || strchr(s, 'E') || strchr(s, 'U')) {
        if (unpackIfAllDigits(s) <= 0) {
            return ERR_INVALID_VOWEL;
        }
        wasAllDigits = 1;
    }

    if (codex > 54) {
        ASSERT(codex == 55);
        return ERR_MAPCODE_UNDECODABLE;
    }
    else if (codex == 54) {
        // international mapcodes must be in international context
        ccode = TERRITORY_AAA;
    }
    else if (ccode < _TERRITORY_MIN) {
        return ERR_MISSING_TERRITORY;
    }
    else if (isSubdivision(ccode)) {
        // int mapcodes must be interpreted in the parent of a subdivision
        enum Territory parent = parentTerritoryOf(ccode);
        if ((codex == 44) || ((codex == 34 || codex == 43) && (parent == TERRITORY_IND || parent == TERRITORY_MEX))) {
            ccode = parent;
        }
    }

    from = firstRec(ccode);
    upto = lastRec(ccode);

    // try all ccode rectangles to decode s (pointing to first character of proper mapcode), assume not decodable
    err = ERR_MAPCODE_UNDECODABLE;
    for (i = from; i <= upto; i++) {
        const unsigned char kind   = RECORD_KIND[i];
        const int codexi           = (int) RECORD_CODEX[i];
        const int r                = (int) RECORD_REC_TYPE[i];
        if (r == 0) {
            if (kind & KIND_BIT_NAMELESS) {
                if (((codexi == 21) && (codex == 22)) ||
                    ((codexi == 22) && (codex == 32)) ||
                    ((codexi == 13) && (codex == 23))) {
                    err = decodeNameless(dec, i);
                    break;
                }
            }
            else {
                if ((codexi == codex) || ((codex == 22) && (codexi == 21))) {
                    err = decodeGrid(dec, i, 0);

                    // first of all, make sure the zone fits the country
                    restrictZoneTo(&dec->zone, &dec->zone, TERRITORY_BOUNDARY(upto));

                    if ((err == ERR_OK) && (kind & KIND_BIT_RESTRICTED)) {
                        int nrZoneOverlaps = 0;
                        int j;

                        // *** make sure decode fits somewhere ***
                        dec->result = getMidPointFractions(&dec->zone);
                        dec->coord32 = convertFractionsToCoord32(&dec->result);
                        for (j = i - 1; j >= from; j--) {
                            // look in previous rects
                            if (!(RECORD_KIND[j] & KIND_BIT_RESTRICTED)) {
                                if (fitsInsideBoundaries(&dec->coord32, TERRITORY_BOUNDARY(j))) {
                                    nrZoneOverlaps = 1;
                                    break;
                                }
                            }
                        }

                        if (!nrZoneOverlaps) {
                            MapcodeZone zfound;
                            TerritoryBoundary prevu;
                            for (j = from; j < i; j++) {
                                // try all smaller rectangles j
                                if (!(RECORD_KIND[j] & KIND_BIT_RESTRICTED)) {
                                    MapcodeZone z;
                                    if (restrictZoneTo(&z, &dec->zone, TERRITORY_BOUNDARY(j))) {
                                        nrZoneOverlaps++;
                                        if (nrZoneOverlaps == 1) {
                                            // first fit! remember...
                                            zoneCopyFrom(&zfound, &z);
                                            ASSERT(j <= MAPCODE_BOUNDARY_MAX);
                                            memcpy(&prevu, TERRITORY_BOUNDARY(j), sizeof(TerritoryBoundary));
                                        }
                                        else {
                                            // nrZoneOverlaps >= 2
                                            // more than one hit
                                            break; // give up
                                        }
                                    }
                                } // IS_RESTRICTED
                            } // for j

                            // if several sub-areas intersect, just return the whole zone
                            // (the center of which may NOT re-encode to the same mapcode!)
                            if (nrZoneOverlaps == 1) {
                                // found exactly ONE intersection?
                                zoneCopyFrom(&dec->zone, &zfound);
                            }
                        }

                        if (!nrZoneOverlaps) {
                            err = ERR_MAPCODE_UNDECODABLE; // type 3 "NLD L222.222"
                        }
                    } // *** make sure decode fits somewhere ***
                    break;
                }
            }
        }
        else if (r == 1) {
            if (codex == codexi + 10 && (unsigned char) *s == RECORD_HEADER_LETTER[i]) {
                err = decodeGrid(dec, i, 1);
                break;
            }
        }
        else {
            //r>1
            if (((codex == 23) && (codexi == 22)) ||
                ((codex == 33) && (codexi == 23))) {
                err = decodeAutoHeader(dec, i);
                break;
            }
        }
    } // for

    if (!err) {
        restrictZoneTo(&dec->zone, &dec->zone, TERRITORY_BOUNDARY(lastRec(ccode)));

        if (isEmpty(&dec->zone)) {
            err = ERR_MAPCODE_UNDECODABLE; // type 0 "BRA xx.xx"
        }
    }

    if (err) {
        dec->result.lat = dec->result.lon = 0;
        return err;
    }

    dec->result = getMidPointFractions(&dec->zone);
    dec->result = convertFractionsToDegrees(&dec->result);

    // normalise between =180 and 180
    if (dec->result.lat < -90.0) {
        dec->result.lat = -90.0;
    }
    if (dec->result.lat > 90.0) {
        dec->result.lat = 90.0;
    }
    if (dec->result.lon < -180.0) {
        dec->result.lon += 360.0;
    }
    if (dec->result.lon >= 180.0) {
        dec->result.lon -= 360.0;
    }

    if (wasAllDigits) {
        repackIfAllDigits(dec->mapcodeElements.properMapcode, 0);
    }
    return ERR_OK;
}

///////////////////////////////////////////////////////////////////////////////////////////////
//
//  Alphabet support
//
///////////////////////////////////////////////////////////////////////////////////////////////

// WARNING - these alphabets have NOT yet been released as standard! use at your own risk! check www.mapcode.com for details.
static const UWORD ASCII_TO_UTF16[_ALPHABET_MAX][36] = {
    // A-Z equivalents for ascii characters A to Z, 0-9
    //  A       B       C       D       E       F       G       H       I       J       K       L       M       N       O       P       Q       R       S       T       U       V       W       X       Y       Z       0       1       2       3       4       5       6       7       8       9
    {
        0x0041, 0x0042, 0x0043, 0x0044, 0x0045, 0x0046, 0x0047, 0x0048, 0x0049, 0x004a, 0x004b, 0x004c, 0x004d, 0x004e,
        0x004f, 0x0050, 0x0051, 0x0052, 0x0053, 0x0054, 0x0055, 0x0056, 0x0057, 0x0058, 0x0059, 0x005a, 0x0030, 0x0031,
        0x0032, 0x0033, 0x0034, 0x0035, 0x0036, 0x0037, 0x0038, 0x0039
    }, // roman
    {
        0x0391, 0x0392, 0x039e, 0x0394, 0x0388, 0x0395, 0x0393, 0x0397, 0x0399, 0x03a0, 0x039a, 0x039b, 0x039c, 0x039d,
        0x039f, 0x03a1, 0x0398, 0x03a8, 0x03a3, 0x03a4, 0x0389, 0x03a6, 0x03a9, 0x03a7, 0x03a5, 0x0396, 0x0030, 0x0031,
        0x0032, 0x0033, 0x0034, 0x0035, 0x0036, 0x0037, 0x0038, 0x0039
    }, // greek
    {
        0x0410, 0x0412, 0x0421, 0x0414, 0x0415, 0x0416, 0x0413, 0x041d, 0x0049, 0x041f, 0x041a, 0x041b, 0x041c, 0x0417,
        0x041e, 0x0420, 0x0424, 0x042f, 0x0426, 0x0422, 0x042d, 0x0427, 0x0428, 0x0425, 0x0423, 0x0411, 0x0030, 0x0031,
        0x0032, 0x0033, 0x0034, 0x0035, 0x0036, 0x0037, 0x0038, 0x0039
    }, // cyrillic
    {
        0x05d0, 0x05d1, 0x05d2, 0x05d3, 0x05e3, 0x05d4, 0x05d6, 0x05d7, 0x05d5, 0x05d8, 0x05d9, 0x05da, 0x05db, 0x05dc,
        0x05e1, 0x05dd, 0x05de, 0x05e0, 0x05e2, 0x05e4, 0x05e5, 0x05e6, 0x05e7, 0x05e8, 0x05e9, 0x05ea, 0x0030, 0x0031,
        0x0032, 0x0033, 0x0034, 0x0035, 0x0036, 0x0037, 0x0038, 0x0039
    }, // hebrew
    {
        0x0905, 0x0915, 0x0917, 0x0918, 0x090f, 0x091a, 0x091c, 0x091f, 0x0049, 0x0920, 0x0923, 0x0924, 0x0926, 0x0927,
        0x004f, 0x0928, 0x092a, 0x092d, 0x092e, 0x0930, 0x092b, 0x0932, 0x0935, 0x0938, 0x0939, 0x092c, 0x0966, 0x0967,
        0x0968, 0x0969, 0x096a, 0x096b, 0x096c, 0x096d, 0x096e, 0x096f
    }, // Devanagari
    {
        0x0d12, 0x0d15, 0x0d16, 0x0d17, 0x0d0b, 0x0d1a, 0x0d1c, 0x0d1f, 0x0049, 0x0d21, 0x0d24, 0x0d25, 0x0d26, 0x0d27,
        0x0d20, 0x0d28, 0x0d2e, 0x0d30, 0x0d31, 0x0d32, 0x0d09, 0x0d34, 0x0d35, 0x0d36, 0x0d38, 0x0d39, 0x0d66, 0x0d67,
        0x0d68, 0x0d69, 0x0d6a, 0x0d6b, 0x0d6c, 0x0d6d, 0x0d6e, 0x0d6f
    }, // Malayalam
    {
        0x10a0, 0x10a1, 0x10a3, 0x10a6, 0x10a4, 0x10a9, 0x10ab, 0x10ac, 0x0049, 0x10ae, 0x10b0, 0x10b1, 0x10b2, 0x10b4,
        0x10ad, 0x10b5, 0x10b6, 0x10b7, 0x10b8, 0x10b9, 0x10a8, 0x10ba, 0x10bb, 0x10bd, 0x10be, 0x10bf, 0x0030, 0x0031,
        0x0032, 0x0033, 0x0034, 0x0035, 0x0036, 0x0037, 0x0038, 0x0039
    }, // Georgian
    {
        0x30a2, 0x30ab, 0x30ad, 0x30af, 0x30aa, 0x30b1, 0x30b3, 0x30b5, 0x0049, 0x30b9, 0x30c1, 0x30c8, 0x30ca, 0x30cc,
        0x004f, 0x30d2, 0x30d5, 0x30d8, 0x30db, 0x30e1, 0x30a8, 0x30e2, 0x30e8, 0x30e9, 0x30ed, 0x30f2, 0x0030, 0x0031,
        0x0032, 0x0033, 0x0034, 0x0035, 0x0036, 0x0037, 0x0038, 0x0039
    }, // Katakana
    {
        0x0e30, 0x0e01, 0x0e02, 0x0e04, 0x0e32, 0x0e07, 0x0e08, 0x0e09, 0x0049, 0x0e0a, 0x0e11, 0x0e14, 0x0e16, 0x0e17,
        0x004f, 0x0e18, 0x0e1a, 0x0e1c, 0x0e21, 0x0e23, 0x0e2c, 0x0e25, 0x0e27, 0x0e2d, 0x0e2e, 0x0e2f, 0x0e50, 0x0e51,
        0x0e52, 0x0e53, 0x0e54, 0x0e55, 0x0e56, 0x0e57, 0x0e58, 0x0e59
    }, // Thai
    {
        0x0eb0, 0x0e81, 0x0e82, 0x0e84, 0x0ec3, 0x0e87, 0x0e88, 0x0e8a, 0x0ec4, 0x0e8d, 0x0e94, 0x0e97, 0x0e99, 0x0e9a,
        0x004f, 0x0e9c, 0x0e9e, 0x0ea1, 0x0ea2, 0x0ea3, 0x0ebd, 0x0ea7, 0x0eaa, 0x0eab, 0x0ead, 0x0eaf, 0x0030, 0x0031,
        0x0032, 0x0033, 0x0034, 0x0035, 0x0036, 0x0037, 0x0038, 0x0039
    }, // Laos
    {
        0x0556, 0x0532, 0x0533, 0x0534, 0x0535, 0x0538, 0x0539, 0x053a, 0x053b, 0x053d, 0x053f, 0x0540, 0x0541, 0x0543,
        0x0555, 0x0547, 0x0548, 0x054a, 0x054d, 0x054e, 0x0545, 0x054f, 0x0550, 0x0551, 0x0552, 0x0553, 0x0030, 0x0031,
        0x0032, 0x0033, 0x0034, 0x0035, 0x0036, 0x0037, 0x0038, 0x0039
    }, // armenian
    {
        0x099c, 0x0998, 0x0995, 0x0996, 0x09ae, 0x0997, 0x0999, 0x099a, 0x0049, 0x099d, 0x09a0, 0x09a1, 0x09a2, 0x09a3,
        0x004f, 0x09a4, 0x09a5, 0x09a6, 0x09a8, 0x09aa, 0x099f, 0x09ac, 0x09ad, 0x09af, 0x09b2, 0x09b9, 0x09e6, 0x09e7,
        0x09e8, 0x09e9, 0x09ea, 0x09eb, 0x09ec, 0x09ed, 0x09ee, 0x09ef
    }, // Bengali/Assamese
    {
        0x0a05, 0x0a15, 0x0a17, 0x0a18, 0x0a0f, 0x0a1a, 0x0a1c, 0x0a1f, 0x0049, 0x0a20, 0x0a23, 0x0a24, 0x0a26, 0x0a27,
        0x004f, 0x0a28, 0x0a2a, 0x0a2d, 0x0a2e, 0x0a30, 0x0a2b, 0x0a32, 0x0a35, 0x0a38, 0x0a39, 0x0a21, 0x0a66, 0x0a67,
        0x0a68, 0x0a69, 0x0a6a, 0x0a6b, 0x0a6c, 0x0a6d, 0x0a6e, 0x0a6f
    }, // Gurmukhi
    {
        0x0f58, 0x0f40, 0x0f41, 0x0f42, 0x0f64, 0x0f44, 0x0f45, 0x0f46, 0x0049, 0x0f47, 0x0f49, 0x0f55, 0x0f50, 0x0f4f,
        0x004f, 0x0f51, 0x0f53, 0x0f54, 0x0f56, 0x0f5e, 0x0f60, 0x0f5f, 0x0f61, 0x0f62, 0x0f63, 0x0f66, 0x0f20, 0x0f21,
        0x0f22, 0x0f23, 0x0f24, 0x0f25, 0x0f26, 0x0f27, 0x0f28, 0x0f29
    }, // Tibetan
    {
        0x0628, 0x062a, 0x062d, 0x062e, 0x062B, 0x062f, 0x0630, 0x0631, 0x0627, 0x0632, 0x0633, 0x0634, 0x0635, 0x0636,
        0x0647, 0x0637, 0x0638, 0x0639, 0x063a, 0x0641, 0x0642, 0x062C, 0x0644, 0x0645, 0x0646, 0x0648, 0x0030, 0x0031,
        0x0032, 0x0033, 0x0034, 0x0035, 0x0036, 0x0037, 0x0038, 0x0039
    }, // Arabic
    {
        0x1112, 0x1100, 0x1102, 0x1103, 0x1166, 0x1105, 0x1107, 0x1109, 0x1175, 0x1110, 0x1111, 0x1161, 0x1162, 0x1163,
        0x110b, 0x1164, 0x1165, 0x1167, 0x1169, 0x1172, 0x1174, 0x110c, 0x110e, 0x110f, 0x116d, 0x116e, 0x0030, 0x0031,
        0x0032, 0x0033, 0x0034, 0x0035, 0x0036, 0x0037, 0x0038, 0x0039
    }, // Korean // 0xc601, 0xc77c, 0xc774, 0xc0bc, 0xc0ac, 0xc624, 0xc721, 0xce60, 0xd314, 0xad6c (vocal digits)
    {
        0x1005, 0x1000, 0x1001, 0x1002, 0x1013, 0x1003, 0x1004, 0x101a, 0x0049, 0x1007, 0x100c, 0x100d, 0x100e, 0x1010,
        0x101d, 0x1011, 0x1012, 0x101e, 0x1014, 0x1015, 0x1016, 0x101f, 0x1017, 0x1018, 0x100f, 0x101c, 0x1040, 0x1041,
        0x1042, 0x1043, 0x1044, 0x1045, 0x1046, 0x1047, 0x1048, 0x1049
    }, // Burmese
    {
        0x1789, 0x1780, 0x1781, 0x1782, 0x1785, 0x1783, 0x1784, 0x1787, 0x179a, 0x1788, 0x178a, 0x178c, 0x178d, 0x178e,
        0x004f, 0x1791, 0x1792, 0x1793, 0x1794, 0x1795, 0x179f, 0x1796, 0x1798, 0x179b, 0x17a0, 0x17a2, 0x17e0, 0x17e1,
        0x17e2, 0x17e3, 0x17e4, 0x17e5, 0x17e6, 0x17e7, 0x17e8, 0x17e9
    }, // Khmer
    {
        0x0d85, 0x0d9a, 0x0d9c, 0x0d9f, 0x0d89, 0x0da2, 0x0da7, 0x0da9, 0x0049, 0x0dac, 0x0dad, 0x0daf, 0x0db1, 0x0db3,
        0x004f, 0x0db4, 0x0db6, 0x0db8, 0x0db9, 0x0dba, 0x0d8b, 0x0dbb, 0x0dbd, 0x0dc0, 0x0dc3, 0x0dc4, 0x0030, 0x0031,
        0x0032, 0x0033, 0x0034, 0x0035, 0x0036, 0x0037, 0x0038, 0x0039
    }, // Sinhalese
    {
        0x0794, 0x0780, 0x0781, 0x0782, 0x0797, 0x0783, 0x0784, 0x0785, 0x0049, 0x0786, 0x0787, 0x0788, 0x0789, 0x078a,
        0x004f, 0x078b, 0x078c, 0x078d, 0x078e, 0x078f, 0x079c, 0x0790, 0x0791, 0x0792, 0x0793, 0x07b1, 0x0030, 0x0031,
        0x0032, 0x0033, 0x0034, 0x0035, 0x0036, 0x0037, 0x0038, 0x0039
    }, // Thaana
    {
        0x3123, 0x3105, 0x3108, 0x3106, 0x3114, 0x3107, 0x3109, 0x310a, 0x0049, 0x310b, 0x310c, 0x310d, 0x310e, 0x310f,
        0x004f, 0x3115, 0x3116, 0x3110, 0x3111, 0x3112, 0x3113, 0x3129, 0x3117, 0x3128, 0x3118, 0x3119, 0x0030, 0x0031,
        0x0032, 0x0033, 0x0034, 0x0035, 0x0036, 0x0037, 0x0038, 0x0039
    }, // Chinese
    {
        0x2D49, 0x2D31, 0x2D33, 0x2D37, 0x2D53, 0x2D3C, 0x2D3D, 0x2D40, 0x2D4F, 0x2D43, 0x2D44, 0x2D45, 0x2D47, 0x2D4D,
        0x2D54, 0x2D4E, 0x2D55, 0x2D56, 0x2D59, 0x2D5A, 0x2D62, 0x2D5B, 0x2D5C, 0x2D5F, 0x2D61, 0x2D63, 0x0030, 0x0031,
        0x0032, 0x0033, 0x0034, 0x0035, 0x0036, 0x0037, 0x0038, 0x0039
    }, // Tifinagh (BERBER)
    {
        0x0b99, 0x0b95, 0x0b9a, 0x0b9f, 0x0b86, 0x0ba4, 0x0ba8, 0x0baa, 0x0049, 0x0bae, 0x0baf, 0x0bb0, 0x0bb2, 0x0bb5,
        0x004f, 0x0bb4, 0x0bb3, 0x0bb1, 0x0b85, 0x0b88, 0x0b93, 0x0b89, 0x0b8e, 0x0b8f, 0x0b90, 0x0b92, 0x0030, 0x0031,
        0x0032, 0x0033, 0x0034, 0x0035, 0x0036, 0x0037, 0x0038, 0x0039
    }, // Tamil (digits 0xBE6-0xBEF)
    {
        0x121B, 0x1260, 0x1264, 0x12F0, 0x121E, 0x134A, 0x1308, 0x1200, 0x0049, 0x12E8, 0x12AC, 0x1208, 0x1293, 0x1350,
        0x12D0, 0x1354, 0x1240, 0x1244, 0x122C, 0x1220, 0x12C8, 0x1226, 0x1270, 0x1276, 0x1338, 0x12DC, 0x1372, 0x1369,
        0x136a, 0x136b, 0x136c, 0x136d, 0x136e, 0x136f, 0x1370, 0x1371
    }, // Amharic (digits 1372|1369-1371)
    {
        0x0C1E, 0x0C15, 0x0C17, 0x0C19, 0x0C2B, 0x0C1A, 0x0C1C, 0x0C1F, 0x0049, 0x0C20, 0x0C21, 0x0C23, 0x0C24, 0x0C25,
        0x004f, 0x0C26, 0x0C27, 0x0C28, 0x0C2A, 0x0C2C, 0x0C2D, 0x0C2E, 0x0C30, 0x0C32, 0x0C33, 0x0C35, 0x0030, 0x0031,
        0x0032, 0x0033, 0x0034, 0x0035, 0x0036, 0x0037, 0x0038, 0x0039
    }, // Telugu
    {
        0x0B1D, 0x0B15, 0x0B16, 0x0B17, 0x0B23, 0x0B18, 0x0B1A, 0x0B1C, 0x0049, 0x0B1F, 0x0B21, 0x0B22, 0x0B24, 0x0B25,
        0x0B20, 0x0B26, 0x0B27, 0x0B28, 0x0B2A, 0x0B2C, 0x0B39, 0x0B2E, 0x0B2F, 0x0B30, 0x0B33, 0x0B38, 0x0030, 0x0031,
        0x0032, 0x0033, 0x0034, 0x0035, 0x0036, 0x0037, 0x0038, 0x0039
    }, // Odia
    {
        0x0C92, 0x0C95, 0x0C96, 0x0C97, 0x0C8E, 0x0C99, 0x0C9A, 0x0C9B, 0x0049, 0x0C9C, 0x0CA0, 0x0CA1, 0x0CA3, 0x0CA4,
        0x004f, 0x0CA6, 0x0CA7, 0x0CA8, 0x0CAA, 0x0CAB, 0x0C87, 0x0CAC, 0x0CAD, 0x0CB0, 0x0CB2, 0x0CB5, 0x0030, 0x0031,
        0x0032, 0x0033, 0x0034, 0x0035, 0x0036, 0x0037, 0x0038, 0x0039
    }, // Kannada
    {
        0x0AB3, 0x0A97, 0x0A9C, 0x0AA1, 0x0A87, 0x0AA6, 0x0AAC, 0x0A95, 0x0049, 0x0A9A, 0x0A9F, 0x0AA4, 0x0AAA, 0x0AA0,
        0x004f, 0x0AB0, 0x0AB5, 0x0A9E, 0x0AAE, 0x0AAB, 0x0A89, 0x0AB7, 0x0AA8, 0x0A9D, 0x0AA2, 0x0AAD, 0x0030, 0x0031,
        0x0032, 0x0033, 0x0034, 0x0035, 0x0036, 0x0037, 0x0038, 0x0039
    }, // Gujarati
};

///////////////////////////////////////////////////////////////////////////////////////////////
//
//  ABJAD ROUTINES
//
///////////////////////////////////////////////////////////////////////////////////////////////


/// PRIVATE convert a mapcode to an ABJAD-format (never more than 2 non-digits in a row)
static char* convertToAbjad(char* targetAsciiString, const char* sourceAsciiString, int maxLength) {
    int form, i, dot, inarow, len;
    const char* rest;
    ASSERT(targetAsciiString);
    ASSERT(sourceAsciiString);
    len = (int)strlen(sourceAsciiString);
    rest = strchr(sourceAsciiString, '-');
    if (rest != NULL) {
        len = ((int)(rest - sourceAsciiString));
    }
    if (len >= maxLength) {
        len = maxLength - 1;
    }
    while (len > 0 && sourceAsciiString[len - 1] == ' ') {
        len--;
    }

    lengthCopy(targetAsciiString, sourceAsciiString, len, maxLength);
    unpackIfAllDigits(targetAsciiString);

    len = (int)strlen(targetAsciiString);
    {
        const char* dotptr = strchr(targetAsciiString, '.');
        dot = dotptr ? (int)(dotptr - targetAsciiString) : -1;
    }

    form = dot * 10 + (len - dot - 1);

    // see if >2 non-digits in a row
    inarow = 0;
    for (i = 0; i < len; i++) {
        char c = targetAsciiString[i];
        if (c != 46) {
            inarow++;
            if (decodeChar(c) <= 9) {
                inarow = 0;
            }
            else if (inarow > 2) {
                break;
            }
        }
    }
    if (dot < 2 || dot > 5 || (inarow < 3 &&
        (form == 22 || form == 32 || form == 33 || form == 42 || form == 43 || form == 44 ||
            form == 54))) {
        // no need to do anything, return input unchanged
        return safeCopy(targetAsciiString, sourceAsciiString, maxLength);
    }
    else if (form >= 22 && form <= 54) {
        char c1, c2, c3 = '?';
        int c = decodeChar(targetAsciiString[2]);
        if (c < 0) {
            c = decodeChar(targetAsciiString[3]);
        }

        if (form >= 44) {
            c = (c * 31) + (decodeChar(targetAsciiString[len - 1]) + 39);
            c1 = ENCODE_CHARS[c / 100];
            c2 = ENCODE_CHARS[(c % 100) / 10];
            c3 = ENCODE_CHARS[c % 10];
        }
        else if (len == 7) {
            if (form == 24) {
                c += 7;
            }
            else if (form == 33) {
                c += 38;
            }
            else if (form == 42) {
                c += 69;
            }
            c1 = ENCODE_CHARS[c / 10];
            c2 = ENCODE_CHARS[c % 10];
        }
        else {
            c1 = ENCODE_CHARS[2 + (c / 8)];
            c2 = ENCODE_CHARS[2 + (c % 8)];
        }

        if (form == 22) // s0 s1 . s3 s4 -> s0 s1 . C1 C2 s4
        {
            targetAsciiString[6] = 0;
            targetAsciiString[5] = targetAsciiString[4];
            targetAsciiString[4] = c2;
            targetAsciiString[3] = c1;
            //          targetAsciiString[2] = '.';
            //          targetAsciiString[1] = targetAsciiString[1];
            //          targetAsciiString[0] = targetAsciiString[0];
        }
        else if (form == 23) {
            // s0 s1 . s3 s4 s5 -> s0 s1 . C1 C2 s4 s5
            targetAsciiString[7] = 0;
            targetAsciiString[6] = targetAsciiString[5];
            targetAsciiString[5] = targetAsciiString[4];
            targetAsciiString[4] = c2;
            targetAsciiString[3] = c1;
            //          targetAsciiString[2] = '.';
            //          targetAsciiString[1] = targetAsciiString[1];
            //          targetAsciiString[0] = targetAsciiString[0];
        }
        else if (form == 32) {
            // s0 s1 s2 . s4 s5 -> s0 s1 . C* C2 s4 s5
            targetAsciiString[7] = 0;
            targetAsciiString[6] = targetAsciiString[5];
            targetAsciiString[5] = targetAsciiString[4];
            targetAsciiString[4] = c2;
            targetAsciiString[3] = (char)(c1 + 4);
            targetAsciiString[2] = '.';
            //          targetAsciiString[1] = targetAsciiString[1];
            //          targetAsciiString[0] = targetAsciiString[0];
        }
        else if (form == 24 || form == 33 || form == 42) {
            // s0 s1 . s3 s4 s5 s6 -> s0 s1 C1 . s4 C2 s5 s6
            // s0 s1 s2 . s4 s5 s6 -> s0 s1 C1 . s4 C2 s5 s6
            // s0 s1 s2 s3 . s5 s6 -> s0 s1 C1 . s3 C2 s5 s6
            targetAsciiString[8] = 0;
            targetAsciiString[7] = targetAsciiString[6];
            targetAsciiString[6] = targetAsciiString[5];
            targetAsciiString[5] = c2;
            targetAsciiString[4] = targetAsciiString[(form == 42 ? 3 : 4)];
            targetAsciiString[3] = '.';
            targetAsciiString[2] = c1;
            //          targetAsciiString[1] = targetAsciiString[1];
            //          targetAsciiString[0] = targetAsciiString[0];
        }
        else if (form == 34) {
            // s0 s1 s2 . s4 s5 s6 s7 -> s0 s1 C1 . s4 s5 C2 S6 S7
            targetAsciiString[9] = 0;
            targetAsciiString[8] = targetAsciiString[7];
            targetAsciiString[7] = targetAsciiString[6];
            targetAsciiString[6] = c2;
            //          targetAsciiString[5] = targetAsciiString[5];
            //          targetAsciiString[4] = targetAsciiString[4];
            //          targetAsciiString[3] = '.';
            targetAsciiString[2] = c1;
            //          targetAsciiString[1] = targetAsciiString[1];
            //          targetAsciiString[0] = targetAsciiString[0];
        }
        else if (form == 43) {
            // s0 s1 s2 s3 . s5 s6 s7 -> s0 s1 C* . s3 s5 C2 S6 S7
            targetAsciiString[9] = 0;
            targetAsciiString[8] = targetAsciiString[7];
            targetAsciiString[7] = targetAsciiString[6];
            targetAsciiString[6] = c2;
            //          targetAsciiString[5] = targetAsciiString[5];
            targetAsciiString[4] = targetAsciiString[3];
            targetAsciiString[3] = '.';
            targetAsciiString[2] = (char)(c1 + 4);
            //          targetAsciiString[1] = targetAsciiString[1];
            //          targetAsciiString[0] = targetAsciiString[0];
        }
        else if (form == 44) {
            targetAsciiString[10] = 0;
            targetAsciiString[9] = targetAsciiString[7];
            targetAsciiString[8] = c3;
            targetAsciiString[7] = targetAsciiString[6];
            targetAsciiString[6] = targetAsciiString[5];
            targetAsciiString[5] = c2;
            //          targetAsciiString[4] = '.';
            //          targetAsciiString[3] = targetAsciiString[3];
            targetAsciiString[2] = c1;
            //          targetAsciiString[1] = targetAsciiString[1];
            //          targetAsciiString[0] = targetAsciiString[0];
        }
        else if (form == 54) {
            targetAsciiString[11] = 0;
            targetAsciiString[10] = targetAsciiString[8];
            targetAsciiString[9] = c3;
            targetAsciiString[8] = targetAsciiString[7];
            targetAsciiString[7] = targetAsciiString[6];
            targetAsciiString[6] = c2;
            //          targetAsciiString[5] = '.';
            //          targetAsciiString[4] = targetAsciiString[4];
            //          targetAsciiString[3] = targetAsciiString[3];
            targetAsciiString[2] = c1;
            //          targetAsciiString[1] = targetAsciiString[1];
            //          targetAsciiString[0] = targetAsciiString[0];
        }
    }
    repackIfAllDigits(targetAsciiString, 0);
    if (rest) {
        int totalLen = (int)strlen(targetAsciiString);
        int needed = (int)strlen(rest);
        int tocopy = maxLength - totalLen - 1;
        if (tocopy > needed) {
            tocopy = needed;
        }
        if (tocopy > 0) {
            memcpy(targetAsciiString + totalLen, rest, (size_t)tocopy);
            targetAsciiString[totalLen + tocopy] = 0;
        }
    }
    return targetAsciiString;
}


static UWORD* encodeUtf16(UWORD* utf16String, const int maxLength, const char* asciiString,
                          const enum Alphabet alphabet) // convert mapcode string alphabet
{
    UWORD* w = utf16String;
    const UWORD* e = w + maxLength - 1;
    const char* r = asciiString;
    ASSERT(utf16String);
    ASSERT(asciiString);
    while (*r != 0 && w < e) {
        char c = *r++;
        if ((c >= 'a') && (c <= 'z')) {
            c += ('A' - 'a');
        }
        if ((c < ' ') || (c > 'Z')) {
            // not in any valid range?
            *w++ = (UWORD)c; // leave untranslated
        }
        else if ((c >= '0') && (c <= '9')) {
            // digit?
            *w++ = ASCII_TO_UTF16[alphabet][26 + (int)c - '0'];
        }
        else if (c < 'A') {
            // valid but not a letter (e.g. a dot, a space...)
            *w++ = (UWORD)c; // leave untranslated
        }
        else {
            *w++ = ASCII_TO_UTF16[alphabet][c - 'A'];
        }
    }
    *w = 0;
    return utf16String;
}


// PUBLIC - convert as much as will fit of mapcode into utf16String
UWORD* convertToAlphabet(UWORD* utf16String, int maxLength, const char* asciiString,
                         enum Alphabet alphabet) // 0=roman, 2=cyrillic
{
    UWORD* startbuf = utf16String;
    UWORD* lastspot = &utf16String[maxLength - 1];
    ASSERT(utf16String);
    ASSERT(asciiString);
    if (maxLength > 0) {
        char targetAsciiString[MAX_MAPCODE_RESULT_ASCII_LEN] = "";
        char abjadString[MAX_MAPCODE_RESULT_ASCII_LEN] = "";

        // skip leading spaces
        while (*asciiString > 0 && *asciiString <= 32) {
            asciiString++;
        }

        // straight-copy everything up to and including first space
        {
            const char* e = strchr(asciiString, ' ');
            if (e) {
                while (asciiString <= e) {
                    if (utf16String == lastspot) {
                        // buffer fully filled?
                        // zero-terminate and return
                        *utf16String = 0;
                        return startbuf;
                    }
                    *utf16String++ = (UWORD)*asciiString++;
                }
                while (*asciiString == ' ') {
                    asciiString++;
                }
            }
        }

        if (alphabet == ALPHABET_GREEK || alphabet == ALPHABET_HEBREW ||
            alphabet == ALPHABET_ARABIC || alphabet == ALPHABET_KOREAN) {
            asciiString = convertToAbjad(abjadString, asciiString, MAX_MAPCODE_RESULT_ASCII_LEN);
        }

        // re-pack E/U-voweled mapcodes when necessary:
        if (alphabet == ALPHABET_GREEK) {
            // alphabet has fewer characters than Roman!
            if (strchr(asciiString, 'E') || strchr(asciiString, 'U') ||
                strchr(asciiString, 'e') || strchr(asciiString, 'u')) {
                // copy trimmed mapcode into temporary buffer targetAsciiString
                int len = (int)strlen(asciiString);
                if (len < MAX_MAPCODE_RESULT_ASCII_LEN) {
                    while (len > 0 && asciiString[len - 1] > 0 && asciiString[len - 1] <= 32) {
                        len--;
                    }
                    lengthCopy(targetAsciiString, asciiString, len, maxLength);
                    // re-pack into A-voweled mapcode
                    unpackIfAllDigits(targetAsciiString);
                    repackIfAllDigits(targetAsciiString, 1);
                    asciiString = targetAsciiString;
                }
            }
        }

        encodeUtf16(utf16String, 1 + (int)(lastspot - utf16String), asciiString, alphabet);
    }
    return startbuf;
}


/**
 * Convert a zero-terminated UTF16 to a UTF8 string
 */
char* convertUtf16ToUtf8(char* utf8, const UWORD* utf16) {
    char* start = utf8;
    ASSERT(utf16);
    ASSERT(utf8);
    while (*utf16) {
        UWORD c = *utf16++;
        if (c < 0x80) {
            *utf8++ = (char)c;
        }
        else if (c < 0x800) {
            *utf8++ = (char)(0xC0 + (c >> 6));
            *utf8++ = (char)(0x80 + (c & 63));
        }
        else {
            *utf8++ = (char)(0xE0 + (c >> 12));
            *utf8++ = (char)(0x80 + ((c >> 6) & 63));
            *utf8++ = (char)(0x80 + (c & 63));
        }
    }
    *utf8 = 0;
    return start;
}

// Caller must make sure utf8String can hold at least MAX_MAPCODE_RESULT_LEN characters (including 0-terminator).
UWORD* convertMapcodeToAlphabetUtf16(UWORD* utf16String, const char* mapcodeString, enum Alphabet alphabet) {
    ASSERT(utf16String);
    ASSERT(mapcodeString);
    ASSERT(alphabet > _ALPHABET_MIN && alphabet < _ALPHABET_MAX);
    *utf16String = 0;
    if (strlen(mapcodeString) < MAX_MAPCODE_RESULT_ASCII_LEN) {
        convertToAlphabet(utf16String, MAX_MAPCODE_RESULT_UTF16_LEN, mapcodeString, alphabet);
    }
    return utf16String;
}


char* convertMapcodeToAlphabetUtf8(char* utf8String, const char* mapcodeString, enum Alphabet alphabet) {
    UWORD utf16[MAX_MAPCODE_RESULT_UTF16_LEN + 1];
    return convertUtf16ToUtf8(utf8String, convertMapcodeToAlphabetUtf16(utf16, mapcodeString, alphabet));
}


///////////////////////////////////////////////////////////////////////////////////////////////
//
//  PUBLIC INTERFACE
//
///////////////////////////////////////////////////////////////////////////////////////////////

// PUBLIC - returns name of territory in (sufficiently large!) result string.
// useShortNames: 0=full 1=short
// returns empty string in case of error
char* getTerritoryIsoName(char* territoryISO, enum Territory territory, int useShortName) {
    ASSERT(territoryISO);
    ASSERT(useShortName == 0 || useShortName == 1);
    if (territory <= _TERRITORY_MIN || territory >= _TERRITORY_MAX) {
        *territoryISO = 0;
    }
    else {
        const char* alphaCode = ISO3166_ALPHA[INDEX_OF_TERRITORY(territory)];
        const char* hyphen = strchr(alphaCode, '-');
        if (useShortName && hyphen != NULL) {
            strcpy(territoryISO, hyphen + 1);
        }
        else {
            strcpy(territoryISO, alphaCode);
        }
    }
    return territoryISO;
}


// PUBLIC - returns negative if territory is not a code that has a parent country
enum Territory getParentCountryOf(enum Territory territory) {
    return parentTerritoryOf(territory);
}


// PUBLIC - returns territory if it is a country, or parent country if territory is a state.
// returns megative if territory is invalid.
enum Territory getCountryOrParentCountry(enum Territory territory) {
    const enum Territory tp = getParentCountryOf(territory);
    if (tp != TERRITORY_NONE) {
        return tp;
    }
    return territory;
}


// PUBLIC - returns nonzero if coordinate is near more than one territory border
int multipleBordersNearby(double latDeg, double lonDeg, enum Territory territory) {
    const enum Territory ccode = territory;
    if ((ccode > _TERRITORY_MIN) && (ccode != TERRITORY_AAA)) {
        // valid territory, not earth
        const enum Territory parentTerritoryCode = getParentCountryOf(territory);
        if (parentTerritoryCode != TERRITORY_NONE) {
            // there is a parent! check its borders as well...
            if (multipleBordersNearby(latDeg, lonDeg, parentTerritoryCode)) {
                return 1;
            }
        }
        {
            int m;
            int nrFound = 0;
            const int from = firstRec(ccode);
            const int upto = lastRec(ccode);
            Point32 coord32;
            convertCoordsToMicrosAndFractions(&coord32, NULL, NULL, latDeg, lonDeg);
            for (m = upto; m >= from; m--) {
                if (!IS_RESTRICTED(m)) {
                    if (isNearBorderOf(&coord32, TERRITORY_BOUNDARY(m))) {
                        nrFound++;
                        if (nrFound > 1) {
                            return 1;
                        }
                    }
                }
            }
        }
    }
    return 0;
}


static int compareAlphaCode(const void* e1, const void* e2) {
    const AlphaRec* a1 = (const AlphaRec*)e1;
    const AlphaRec* a2 = (const AlphaRec*)e2;
    ASSERT(e1);
    ASSERT(e2);
    return strcmp(a1->alphaCode, a2->alphaCode);
} // cmp

static enum Territory findMatch(const int parentNumber, const char* territoryISO) {
    // build an uppercase search term
    char codeISO[MAX_ISOCODE_ASCII_LEN + 1];
    const char* r = territoryISO;
    int len = 0;
    ASSERT(territoryISO);

    if (parentNumber < 0) {
        return TERRITORY_NONE;
    }
    if (parentNumber > 0) {
        codeISO[0] = PARENTS_2[3 * parentNumber - 3];
        codeISO[1] = PARENTS_2[3 * parentNumber - 2];
        codeISO[2] = '-';
        len = 3;
    }
    while ((len < MAX_ISOCODE_ASCII_LEN) && (*r > 32)) {
        codeISO[len++] = *r++;
    }
    if (*r > 32) {
        return TERRITORY_NONE;
    }
    codeISO[len] = 0;
    makeUppercase(codeISO);
    {
        // binary-search the result
        const AlphaRec* p;
        AlphaRec t;
        t.alphaCode = codeISO;

        p = (const AlphaRec*)bsearch(&t, ALPHA_SEARCH, NR_TERRITORY_RECS, sizeof(AlphaRec), compareAlphaCode);
        if (p) {
            if (strcmp(t.alphaCode, p->alphaCode) == 0) {
                // only interested in PERFECT match
                return p->territory;
            } // match
        } // found
    } //
    return TERRITORY_NONE;
}


// PUBLIC - returns territory of territoryISO (or negative if not found).
// optionalTerritoryContext: pass to handle ambiguities (pass TERRITORY_NONE if unknown).
enum Territory getTerritoryCode(const char* territoryISO, enum Territory optionalTerritoryContext) {
    if (territoryISO == NULL) {
        return TERRITORY_NONE;
    }
    ASSERT(territoryISO);
    while (*territoryISO > 0 && *territoryISO <= 32) {
        territoryISO++;
    } // skip leading whitespace

    if (territoryISO[0] && territoryISO[1]) {
        if (territoryISO[2] == '-') {
            return findMatch(getParentNumber(territoryISO, 2), territoryISO + 3);
        }
        else if (territoryISO[2] && territoryISO[3] == '-') {
            return findMatch(getParentNumber(territoryISO, 3), territoryISO + 4);
        }
        else {
            enum Territory b;
            int parentNumber = 0;
            if (optionalTerritoryContext > _TERRITORY_MIN) {
                parentNumber = PARENT_NUMBER[INDEX_OF_TERRITORY(getCountryOrParentCountry(optionalTerritoryContext))];
            }
            b = findMatch(parentNumber, territoryISO);
            if (b != TERRITORY_NONE) {
                return b;
            }
        }
        return findMatch(0, territoryISO);
    } // else, fail:
    return TERRITORY_NONE;
}


// PUBLIC - decode string into lat,lon; returns negative in case of error
enum MapcodeError decodeMapcodeToLatLonUtf8(double* latDeg, double* lonDeg,
                                            const char* mapcode, enum Territory territory,
                                            MapcodeElements* mapcodeElements) {
    if ((latDeg == NULL) || (lonDeg == NULL) || (mapcode == NULL)) {
        return ERR_BAD_ARGUMENTS;
    }
    else {
        enum MapcodeError ret;
        DecodeRec dec = {
            {"", TERRITORY_NONE, "", 0, ""},
            0,
            0,
            0,
            TERRITORY_NONE,
            0,
            {0.0, 0.0},
            {0, 0},
            {0.0, 0.0, 0.0, 0.0}
        };
        dec.orginput = mapcode;
        dec.context = territory;

        ret = decoderEngine(&dec, 0);
        *latDeg = dec.result.lat;
        *lonDeg = dec.result.lon;

        if (mapcodeElements) {
            memcpy(mapcodeElements, &dec.mapcodeElements, sizeof(MapcodeElements));
        }
        return ret;
    }
}


// PUBLIC - decode string into lat,lon; returns negative in case of error
enum MapcodeError decodeMapcodeToLatLonUtf16(double* latDeg, double* lonDeg,
                                             const UWORD* mapcode, enum Territory territory,
                                             MapcodeElements* mapcodeElements) {
    if ((latDeg == NULL) || (lonDeg == NULL) || (mapcode == NULL)) {
        return ERR_BAD_ARGUMENTS;
    }
    else {
        enum MapcodeError ret;
        DecodeRec dec = {
            {"", TERRITORY_NONE, "", 0, ""},
            0,
            0,
            0,
            TERRITORY_NONE,
            0,
            {0.0, 0.0},
            {0, 0},
            {0.0, 0.0, 0.0, 0.0}
        };
        dec.orginput = (const char*)mapcode;
        dec.context = territory;

        ret = decoderEngine(&dec, FLAG_UTF16_STRING);
        *latDeg = dec.result.lat;
        *lonDeg = dec.result.lon;

        if (mapcodeElements) {
            memcpy(mapcodeElements, &dec.mapcodeElements, sizeof(MapcodeElements));
        }
        return ret;
    }
}


// PUBLIC - encode lat,lon for territory to a mapcode with extraDigits accuracy
int
encodeLatLonToSingleMapcode(char* mapcode, double latDeg, double lonDeg, enum Territory territory, int extraDigits) {
    Mapcodes rlocal;
    int ret;
    ASSERT(mapcode);
    if (extraDigits < 0) {
        return 0;
    }
    if (extraDigits > MAX_PRECISION_DIGITS) {
        extraDigits = MAX_PRECISION_DIGITS;
    }
    ret = encodeLatLonToMapcodes_internal(&rlocal, latDeg, lonDeg, territory, 1, DEBUG_STOP_AT, extraDigits);
    *mapcode = 0;
    if (ret <= 0) {
        // no solutions?
        return ret;
    }
    // prefix territory unless international
    strcpy(mapcode, rlocal.mapcode[0]);
    return 1;
}


// PUBLIC - encode lat,lon for territory to a selected mapcode (from all results) with extraDigits accuracy
int
encodeLatLonToSelectedMapcode(char* mapcode, double latDeg, double lonDeg, enum Territory territory, int extraDigits,
                              int indexOfSelected) {
    Mapcodes mapcodes;
    int nrOfResults = 0;
    nrOfResults = encodeLatLonToMapcodes(&mapcodes, latDeg, lonDeg, territory, extraDigits);
    ASSERT(nrOfResults == mapcodes.count);
    if ((nrOfResults <= 0) || (indexOfSelected < 0) || (indexOfSelected >= nrOfResults)) {
        return 0;
    }
    strcpy(mapcode, mapcodes.mapcode[indexOfSelected]);
    return nrOfResults;
}


// PUBLIC - encode lat,lon for (optional) territory to mapcodes with extraDigits accuracy
int
encodeLatLonToMapcodes(Mapcodes* mapcodes, double latDeg, double lonDeg, enum Territory territory, int extraDigits) {
    ASSERT(mapcodes);
    if (extraDigits < 0) {
        return 0;
    }
    if (extraDigits > MAX_PRECISION_DIGITS) {
        extraDigits = MAX_PRECISION_DIGITS;
    }
    return encodeLatLonToMapcodes_internal(mapcodes, latDeg, lonDeg, territory, 0, DEBUG_STOP_AT, extraDigits);
}

///////////////////////////////////////////////////////////////////////////////////////////////
//
//  ALPHABET / UTF ROUTINES
//
///////////////////////////////////////////////////////////////////////////////////////////////

// PUBLIC - returns most common alphabets for territory, NULL if error
const TerritoryAlphabets* getAlphabetsForTerritory(enum Territory territory) {
    if (territory > _TERRITORY_MIN && territory < _TERRITORY_MAX) {
        return &ALPHABETS_FOR_TERRITORY[INDEX_OF_TERRITORY(territory)];
    }
    return NULL;
}


///////////////////////////////////////////////////////////////////////////////////////////////
//
//  FULL TERRITORY NAMES
//
///////////////////////////////////////////////////////////////////////////////////////////////

static int
getFullTerritoryName_internal(char* territoryName, enum Territory territory, int alternative, const char* locale,
                              enum Alphabet alphabet) {
    const char* territoryNamesPiped;
    const char* pipePtr;
    const char** territoryNamesList = NULL;

    ASSERT(territoryName);
    ASSERT((_TERRITORY_MIN < territory) && (territory < _TERRITORY_MAX));
    ASSERT((alphabet == _ALPHABET_MIN) || ((_ALPHABET_MIN < alphabet) && (alphabet < _ALPHABET_MAX)));

    // Defensive bail out if incorrect arguments.
    if (!territoryName || (alternative < 0) || (territory <= _TERRITORY_MIN) || (territory >= _TERRITORY_MAX)) {
        if (territoryName) {
            *territoryName = 0;
        }
        return 0;
    }

    // Check locale.
    if (locale == NULL) {
        // Use local names if locale is null.
        territoryNamesList = TERRITORY_FULL_NAME_LOCAL;
    }
    else {
        // Try and get correct list.
        int i;
        int upTo = (int)strlen(locale);
        char localeUpper[4] = ""; // Default locale is empty (which implies 'fallback').
        char* sep = strchr(locale, '_'); // Official separator is '_' (as in "en_US").
        if (!sep) {
            sep = strchr(locale, '-'); // But we also allow '-' (often used as well).
        }
        if (sep) {
            upTo = (int)(sep - locale);
        }
        lengthCopy(localeUpper, locale, upTo, sizeof(localeUpper));
        makeUppercase(localeUpper);

        territoryNamesList = NULL;
        for (i = 0; i < (int)(sizeof(LOCALE_REGISTRY) / sizeof(LOCALE_REGISTRY[0])); ++i) {
            if (!strcmp(LOCALE_REGISTRY[i].locale, localeUpper)) {
                territoryNamesList = LOCALE_REGISTRY[i].territoryFullNames;
                break;
            }
        }
    }

    // Use English if locale is invalid (or was empty = fallback).
    if (territoryNamesList == NULL || territoryNamesList[0] == NULL) {
        territoryNamesList = DEFAULT_TERRITORY_FULL_NAME;
    }

    *territoryName = 0;
    territoryNamesPiped = territoryNamesList[INDEX_OF_TERRITORY(territory)];
    for (;;) {
        pipePtr = strchr(territoryNamesPiped, '|');

        if ((_ALPHABET_MIN < alphabet) && (alphabet < _ALPHABET_MAX)) {
            // Alphabet was specified.
            if (pipePtr) {
                ASSERT((pipePtr - territoryNamesPiped) <= MAX_TERRITORY_FULLNAME_UTF8_LEN);
                lengthCopy(territoryName, territoryNamesPiped, (int)(pipePtr - territoryNamesPiped),
                           MAX_TERRITORY_FULLNAME_UTF8_LEN);
            }
            else {
                ASSERT(strlen(territoryNamesPiped) <= MAX_TERRITORY_FULLNAME_UTF8_LEN);
                strcpy(territoryName, territoryNamesPiped);
            }
            if (alphabet != recognizeAlphabetUtf8(territoryName)) {
                // filter out
                if (!pipePtr) {
                    // this is the last string!
                    return 0;
                }
                territoryNamesPiped = pipePtr + 1;
                continue;
            }
        }

        if (!pipePtr) {
            // this is the last string!
            if (alternative > 0) {
                // not what we want?
                return 0;
            }
            ASSERT(strlen(territoryNamesPiped) <= MAX_TERRITORY_FULLNAME_UTF8_LEN);
            strcpy(territoryName, territoryNamesPiped); // no bracket, return it all
            return 1;
        }
        else {
            if (!alternative) {
                // what we want?
                break;
            }
            alternative--;
            territoryNamesPiped = pipePtr + 1;
        }
    }
    lengthCopy(territoryName, territoryNamesPiped, (int)(pipePtr - territoryNamesPiped),
               MAX_TERRITORY_FULLNAME_UTF8_LEN);
    return 1;
}


int getFullTerritoryNameEnglish(char* territoryName, enum Territory territory, int alternative) {
    ASSERT(territoryName);
    ASSERT((_TERRITORY_MIN < territory) && (territory < _TERRITORY_MAX));
    return getFullTerritoryNameInLocaleUtf8(territoryName, territory, alternative, "en_US");
}


int getFullTerritoryNameInLocaleUtf8(char* territoryName, enum Territory territory, int alternative,
                                     const char* locale) {
    ASSERT(territoryName);
    ASSERT(((_TERRITORY_MIN < territory) && (territory < _TERRITORY_MAX)) || (territory == TERRITORY_UNKNOWN));
    return getFullTerritoryName_internal(territoryName, territory, alternative, locale, _ALPHABET_MIN);
}


int getFullTerritoryNameInLocaleInAlphabetUtf8(char* territoryName, enum Territory territory, int alternative,
                                               const char* locale, enum Alphabet alphabet) {
    ASSERT(territoryName);
    ASSERT((_TERRITORY_MIN < territory) && (territory < _TERRITORY_MAX));
    if ((alphabet <= _ALPHABET_MIN) || (alphabet >= _ALPHABET_MAX)) {
        *territoryName = 0;
        return 0;
    }
    return getFullTerritoryName_internal(territoryName, territory, alternative, locale, alphabet);
}


int getFullTerritoryNameLocalUtf8(char* territoryName, enum Territory territory, int alternative) {
    ASSERT(territoryName);
    ASSERT((_TERRITORY_MIN < territory) && (territory < _TERRITORY_MAX));
    return getFullTerritoryName_internal(territoryName, territory, alternative, NULL, _ALPHABET_MIN);
}


int getFullTerritoryNameLocalInAlphabetUtf8(char* territoryName, enum Territory territory, int alternative,
                                            enum Alphabet alphabet) {
    ASSERT(territoryName);
    ASSERT((_TERRITORY_MIN < territory) && (territory < _TERRITORY_MAX));
    if ((alphabet <= _ALPHABET_MIN) || (alphabet >= _ALPHABET_MAX)) {
        *territoryName = 0;
        return 0;
    }
    return getFullTerritoryName_internal(territoryName, territory, alternative, NULL, alphabet);
}