src/zonedetect.c

   1 /*
   2  * Copyright (c) 2018, Bertold Van den Bergh (vandenbergh@bertold.org)
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions are met:
   7  *     * Redistributions of source code must retain the above copyright
   8  *       notice, this list of conditions and the following disclaimer.
   9  *     * Redistributions in binary form must reproduce the above copyright
  10  *       notice, this list of conditions and the following disclaimer in the
  11  *       documentation and/or other materials provided with the distribution.
  12  *     * Neither the name of the author nor the
  13  *       names of its contributors may be used to endorse or promote products
  14  *       derived from this software without specific prior written permission.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
  17  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  18  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  19  * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR DISTRIBUTOR BE LIABLE FOR ANY
  20  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  21  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  22  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  23  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  24  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  25  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  26  */
  27
  28 #include <assert.h>
  29 #include <stddef.h>
  30 #include <stdint.h>
  31 #include <stdio.h>
  32 #include <stdlib.h>
  33 #include <string.h>
  34 #include <math.h>
  35 #if defined(_MSC_VER) || defined(__MINGW32__)
  36 #include <windows.h>
  37 #else
  38 #include <errno.h>
  39 #include <sys/mman.h>
  40 #include <fcntl.h>
  41 #include <unistd.h>
  42 #endif
  43
  44 #include "zonedetect.h"
  45
  46 enum ZDInternalError {
  47     ZD_OK,
  48     ZD_E_DB_OPEN,
  49     ZD_E_DB_SEEK,
  50     ZD_E_DB_MMAP,
  51 #if defined(_MSC_VER) || defined(__MINGW32__)
  52     ZD_E_DB_MMAP_MSVIEW,
  53     ZD_E_DB_MAP_EXCEPTION,
  54     ZD_E_DB_MUNMAP_MSVIEW,
  55 #endif
  56     ZD_E_DB_MUNMAP,
  57     ZD_E_DB_CLOSE,
  58     ZD_E_PARSE_HEADER
  59 };
  60
  61 struct ZoneDetectOpaque {
  62 #if defined(_MSC_VER) || defined(__MINGW32__)
  63     HANDLE fd;
  64     HANDLE fdMap;
  65     int32_t length;
  66     int32_t padding;
  67 #else
  68     int fd;
  69     off_t length;
  70 #endif
  71
  72     uint8_t closeType;
  73     uint8_t *mapping;
  74
  75     uint8_t tableType;
  76     uint8_t version;
  77     uint8_t precision;
  78     uint8_t numFields;
  79
  80     char *notice;
  81     char **fieldNames;
  82
  83     uint32_t bboxOffset;
  84     uint32_t metadataOffset;
  85     uint32_t dataOffset;
  86 };
  87
  88 static void (*zdErrorHandler)(int, int);
  89 static void zdError(enum ZDInternalError errZD, int errNative)
  90 {
  91     if (zdErrorHandler) zdErrorHandler((int)errZD, errNative);
  92 }
  93
  94 static int32_t ZDFloatToFixedPoint(float input, float scale, unsigned int precision)
  95 {
  96     const float inputScaled = input / scale;
  97     return (int32_t)(inputScaled * (float)(1 << (precision - 1)));
  98 }
  99
 100 static float ZDFixedPointToFloat(int32_t input, float scale, unsigned int precision)
 101 {
 102     const float value = (float)input / (float)(1 << (precision - 1));
 103     return value * scale;
 104 }
 105
 106 static unsigned int ZDDecodeVariableLengthUnsigned(const ZoneDetect *library, uint32_t *index, uint64_t *result)
 107 {
 108     if(*index >= (uint32_t)library->length) {
 109         return 0;
 110     }
 111
 112     uint64_t value = 0;
 113     unsigned int i = 0;
 114 #if defined(_MSC_VER)
 115     __try {
 116 #endif
 117         uint8_t *const buffer = library->mapping + *index;
 118         uint8_t *const bufferEnd = library->mapping + library->length - 1;
 119
 120         unsigned int shift = 0;
 121         while(1) {
 122             value |= ((((uint64_t)buffer[i]) & UINT8_C(0x7F)) << shift);
 123             shift += 7u;
 124
 125             if(!(buffer[i] & UINT8_C(0x80))) {
 126                 break;
 127             }
 128
 129             i++;
 130             if(buffer + i > bufferEnd) {
 131                 return 0;
 132             }
 133         }
 134 #if defined(_MSC_VER)
 135     } __except(GetExceptionCode() == EXCEPTION_IN_PAGE_ERROR
 136                ? EXCEPTION_EXECUTE_HANDLER
 137                : EXCEPTION_CONTINUE_SEARCH) { /* file mapping SEH exception occurred */
 138         zdError(ZD_E_DB_MAP_EXCEPTION, (int)GetLastError());
 139         return 0;
 140     }
 141 #endif
 142
 143     i++;
 144     *result = value;
 145     *index += i;
 146     return i;
 147 }
 148
 149 static unsigned int ZDDecodeVariableLengthUnsignedReverse(const ZoneDetect *library, uint32_t *index, uint64_t *result)
 150 {
 151     uint32_t i = *index;
 152
 153     if(*index >= (uint32_t)library->length) {
 154         return 0;
 155     }
 156
 157 #if defined(_MSC_VER)
 158     __try {
 159 #endif
 160
 161         if(library->mapping[i] & UINT8_C(0x80)) {
 162             return 0;
 163         }
 164
 165         if(!i) {
 166             return 0;
 167         }
 168         i--;
 169
 170         while(library->mapping[i] & UINT8_C(0x80)) {
 171             if(!i) {
 172                 return 0;
 173             }
 174             i--;
 175         }
 176
 177 #if defined(_MSC_VER)
 178     } __except(GetExceptionCode() == EXCEPTION_IN_PAGE_ERROR
 179                ? EXCEPTION_EXECUTE_HANDLER
 180                : EXCEPTION_CONTINUE_SEARCH) { /* file mapping SEH exception occurred */
 181         zdError(ZD_E_DB_MAP_EXCEPTION, (int)GetLastError());
 182         return 0;
 183     }
 184 #endif
 185
 186     *index = i;
 187
 188     i++;
 189
 190     uint32_t i2 = i;
 191     return ZDDecodeVariableLengthUnsigned(library, &i2, result);
 192 }
 193
 194 static int64_t ZDDecodeUnsignedToSigned(uint64_t value)
 195 {
 196     return (value & 1) ? -(int64_t)(value / 2) : (int64_t)(value / 2);
 197 }
 198
 199 static unsigned int ZDDecodeVariableLengthSigned(const ZoneDetect *library, uint32_t *index, int32_t *result)
 200 {
 201     uint64_t value = 0;
 202     const unsigned int retVal = ZDDecodeVariableLengthUnsigned(library, index, &value);
 203     *result = (int32_t)ZDDecodeUnsignedToSigned(value);
 204     return retVal;
 205 }
 206
 207 static char *ZDParseString(const ZoneDetect *library, uint32_t *index)
 208 {
 209     uint64_t strLength;
 210     if(!ZDDecodeVariableLengthUnsigned(library, index, &strLength)) {
 211         return NULL;
 212     }
 213
 214     uint32_t strOffset = *index;
 215     unsigned int remoteStr = 0;
 216     if(strLength >= 256) {
 217         strOffset = library->metadataOffset + (uint32_t)strLength - 256;
 218         remoteStr = 1;
 219
 220         if(!ZDDecodeVariableLengthUnsigned(library, &strOffset, &strLength)) {
 221             return NULL;
 222         }
 223
 224         if(strLength > 256) {
 225             return NULL;
 226         }
 227     }
 228
 229     char *const str = malloc((size_t)(strLength + 1));
 230
 231     if(str) {
 232 #if defined(_MSC_VER)
 233         __try {
 234 #endif
 235             for(size_t i = 0; i < strLength; i++) {
 236                 str[i] = (char)(library->mapping[strOffset + i] ^ UINT8_C(0x80));
 237             }
 238 #if defined(_MSC_VER)
 239         } __except(GetExceptionCode() == EXCEPTION_IN_PAGE_ERROR
 240                    ? EXCEPTION_EXECUTE_HANDLER
 241                    : EXCEPTION_CONTINUE_SEARCH) { /* file mapping SEH exception occurred */
 242             zdError(ZD_E_DB_MAP_EXCEPTION, (int)GetLastError());
 243             return 0;
 244         }
 245 #endif
 246         str[strLength] = 0;
 247     }
 248
 249     if(!remoteStr) {
 250         *index += (uint32_t)strLength;
 251     }
 252
 253     return str;
 254 }
 255
 256 static int ZDParseHeader(ZoneDetect *library)
 257 {
 258     if(library->length < 7) {
 259         return -1;
 260     }
 261
 262 #if defined(_MSC_VER)
 263     __try {
 264 #endif
 265         if(memcmp(library->mapping, "PLB", 3)) {
 266             return -1;
 267         }
 268
 269         library->tableType = library->mapping[3];
 270         library->version   = library->mapping[4];
 271         library->precision = library->mapping[5];
 272         library->numFields = library->mapping[6];
 273 #if defined(_MSC_VER)
 274     } __except(GetExceptionCode() == EXCEPTION_IN_PAGE_ERROR
 275                ? EXCEPTION_EXECUTE_HANDLER
 276                : EXCEPTION_CONTINUE_SEARCH) { /* file mapping SEH exception occurred */
 277         zdError(ZD_E_DB_MAP_EXCEPTION, (int)GetLastError());
 278         return 0;
 279     }
 280 #endif
 281
 282     if(library->version >= 2) {
 283         return -1;
 284     }
 285
 286     uint32_t index = UINT32_C(7);
 287
 288     library->fieldNames = malloc(library->numFields * sizeof *library->fieldNames);
 289     for(size_t i = 0; i < library->numFields; i++) {
 290         library->fieldNames[i] = ZDParseString(library, &index);
 291     }
 292
 293     library->notice = ZDParseString(library, &index);
 294     if(!library->notice) {
 295         return -1;
 296     }
 297
 298     uint64_t tmp;
 299     /* Read section sizes */
 300     /* By memset: library->bboxOffset = 0 */
 301
 302     if(!ZDDecodeVariableLengthUnsigned(library, &index, &tmp)) return -1;
 303     library->metadataOffset = (uint32_t)tmp + library->bboxOffset;
 304
 305     if(!ZDDecodeVariableLengthUnsigned(library, &index, &tmp))return -1;
 306     library->dataOffset = (uint32_t)tmp + library->metadataOffset;
 307
 308     if(!ZDDecodeVariableLengthUnsigned(library, &index, &tmp)) return -1;
 309
 310     /* Add header size to everything */
 311     library->bboxOffset += index;
 312     library->metadataOffset += index;
 313     library->dataOffset += index;
 314
 315     /* Verify file length */
 316     if(tmp + library->dataOffset != (uint32_t)library->length) {
 317         return -2;
 318     }
 319
 320     return 0;
 321 }
 322
 323 static int ZDPointInBox(int32_t xl, int32_t x, int32_t xr, int32_t yl, int32_t y, int32_t yr)
 324 {
 325     if((xl <= x && x <= xr) || (xr <= x && x <= xl)) {
 326         if((yl <= y && y <= yr) || (yr <= y && y <= yl)) {
 327             return 1;
 328         }
 329     }
 330
 331     return 0;
 332 }
 333
 334 static uint32_t ZDUnshuffle(uint64_t w)
 335 {
 336     w &=                  0x5555555555555555;
 337     w = (w | (w >> 1))  & 0x3333333333333333;
 338     w = (w | (w >> 2))  & 0x0F0F0F0F0F0F0F0F;
 339     w = (w | (w >> 4))  & 0x00FF00FF00FF00FF;
 340     w = (w | (w >> 8))  & 0x0000FFFF0000FFFF;
 341     w = (w | (w >> 16)) & 0x00000000FFFFFFFF;
 342     return (uint32_t)w;
 343 }
 344
 345 static void ZDDecodePoint(uint64_t point, int32_t* lat, int32_t* lon)
 346 {
 347     *lat = (int32_t)ZDDecodeUnsignedToSigned(ZDUnshuffle(point));
 348     *lon = (int32_t)ZDDecodeUnsignedToSigned(ZDUnshuffle(point >> 1));
 349 }
 350
 351 struct Reader {
 352     const ZoneDetect *library;
 353     uint32_t polygonIndex;
 354
 355     uint64_t numVertices;
 356
 357     uint8_t done, first;
 358     uint32_t referenceStart, referenceEnd;
 359     int32_t referenceDirection;
 360
 361     int32_t pointLat, pointLon;
 362     int32_t firstLat, firstLon;
 363 };
 364
 365 static void ZDReaderInit(struct Reader *reader, const ZoneDetect *library, uint32_t polygonIndex)
 366 {
 367     memset(reader, 0, sizeof(*reader));
 368
 369     reader->library = library;
 370     reader->polygonIndex = polygonIndex;
 371
 372     reader->first = 1;
 373 }
 374
 375 static int ZDReaderGetPoint(struct Reader *reader, int32_t *pointLat, int32_t *pointLon)
 376 {
 377     int32_t diffLat = 0, diffLon = 0;
 378
 379 readNewPoint:
 380     if(reader->done > 1) {
 381         return 0;
 382     }
 383
 384     if(reader->first && reader->library->version == 0) {
 385         if(!ZDDecodeVariableLengthUnsigned(reader->library, &reader->polygonIndex, &reader->numVertices)) return -1;
 386         if(!reader->numVertices) return -1;
 387     }
 388
 389     uint8_t referenceDone = 0;
 390
 391     if(reader->library->version == 1) {
 392         uint64_t point = 0;
 393
 394         if(!reader->referenceDirection) {
 395             if(!ZDDecodeVariableLengthUnsigned(reader->library, &reader->polygonIndex, &point)) return -1;
 396         } else {
 397             if(reader->referenceDirection > 0) {
 398                 /* Read reference forward */
 399                 if(!ZDDecodeVariableLengthUnsigned(reader->library, &reader->referenceStart, &point)) return -1;
 400                 if(reader->referenceStart >= reader->referenceEnd) {
 401                     referenceDone = 1;
 402                 }
 403             } else if(reader->referenceDirection < 0) {
 404                 /* Read reference backwards */
 405                 if(!ZDDecodeVariableLengthUnsignedReverse(reader->library, &reader->referenceStart, &point)) return -1;
 406                 if(reader->referenceStart <= reader->referenceEnd) {
 407                     referenceDone = 1;
 408                 }
 409             }
 410         }
 411
 412         if(!point) {
 413             /* This is a special marker, it is not allowed in reference mode */
 414             if(reader->referenceDirection) {
 415                 return -1;
 416             }
 417
 418             uint64_t value;
 419             if(!ZDDecodeVariableLengthUnsigned(reader->library, &reader->polygonIndex, &value)) return -1;
 420
 421             if(value == 0) {
 422                 reader->done = 2;
 423             } else if(value == 1) {
 424                 int32_t diff;
 425                 int64_t start;
 426                 if(!ZDDecodeVariableLengthUnsigned(reader->library, &reader->polygonIndex, (uint64_t*)&start)) return -1;
 427                 if(!ZDDecodeVariableLengthSigned(reader->library, &reader->polygonIndex, &diff)) return -1;
 428
 429                 reader->referenceStart = reader->library->dataOffset+(uint32_t)start;
 430                 reader->referenceEnd = reader->library->dataOffset+(uint32_t)(start + diff);
 431                 reader->referenceDirection = diff;
 432                 if(diff < 0) {
 433                     reader->referenceStart--;
 434                     reader->referenceEnd--;
 435                 }
 436                 goto readNewPoint;
 437             }
 438         } else {
 439             ZDDecodePoint(point, &diffLat, &diffLon);
 440             if(reader->referenceDirection < 0) {
 441                 diffLat = -diffLat;
 442                 diffLon = -diffLon;
 443             }
 444         }
 445     }
 446
 447     if(reader->library->version == 0) {
 448         if(!ZDDecodeVariableLengthSigned(reader->library, &reader->polygonIndex, &diffLat)) return -1;
 449         if(!ZDDecodeVariableLengthSigned(reader->library, &reader->polygonIndex, &diffLon)) return -1;
 450     }
 451
 452     if(!reader->done) {
 453         reader->pointLat += diffLat;
 454         reader->pointLon += diffLon;
 455         if(reader->first) {
 456             reader->firstLat = reader->pointLat;
 457             reader->firstLon = reader->pointLon;
 458         }
 459     } else {
 460         /* Close the polygon (the closing point is not encoded) */
 461         reader->pointLat = reader->firstLat;
 462         reader->pointLon = reader->firstLon;
 463         reader->done = 2;
 464     }
 465
 466     reader->first = 0;
 467
 468     if(reader->library->version == 0) {
 469         reader->numVertices--;
 470         if(!reader->numVertices) {
 471             reader->done = 1;
 472         }
 473         if(!diffLat && !diffLon) {
 474             goto readNewPoint;
 475         }
 476     }
 477
 478     if(referenceDone) {
 479         reader->referenceDirection = 0;
 480     }
 481
 482     if(pointLat) {
 483         *pointLat = reader->pointLat;
 484     }
 485
 486     if(pointLon) {
 487         *pointLon = reader->pointLon;
 488     }
 489
 490     return 1;
 491 }
 492
 493 static int ZDFindPolygon(const ZoneDetect *library, uint32_t wantedId, uint32_t* metadataIndexPtr, uint32_t* polygonIndexPtr)
 494 {
 495     uint32_t polygonId = 0;
 496     uint32_t bboxIndex = library->bboxOffset;
 497
 498     uint32_t metadataIndex = 0, polygonIndex = 0;
 499
 500     while(bboxIndex < library->metadataOffset) {
 501         uint64_t polygonIndexDelta;
 502         int32_t metadataIndexDelta;
 503         int32_t tmp;
 504         if(!ZDDecodeVariableLengthSigned(library, &bboxIndex, &tmp)) break;
 505         if(!ZDDecodeVariableLengthSigned(library, &bboxIndex, &tmp)) break;
 506         if(!ZDDecodeVariableLengthSigned(library, &bboxIndex, &tmp)) break;
 507         if(!ZDDecodeVariableLengthSigned(library, &bboxIndex, &tmp)) break;
 508         if(!ZDDecodeVariableLengthSigned(library, &bboxIndex, &metadataIndexDelta)) break;
 509         if(!ZDDecodeVariableLengthUnsigned(library, &bboxIndex, &polygonIndexDelta)) break;
 510
 511         metadataIndex += (uint32_t)metadataIndexDelta;
 512         polygonIndex += (uint32_t)polygonIndexDelta;
 513
 514         if(polygonId == wantedId) {
 515             if(metadataIndexPtr) {
 516                 metadataIndex += library->metadataOffset;
 517                 *metadataIndexPtr = metadataIndex;
 518             }
 519             if(polygonIndexPtr) {
 520                 polygonIndex += library->dataOffset;
 521                 *polygonIndexPtr = polygonIndex;
 522             }
 523             return 1;
 524         }
 525
 526         polygonId ++;
 527     }
 528
 529     return 0;
 530 }
 531
 532 static int32_t* ZDPolygonToListInternal(const ZoneDetect *library, uint32_t polygonIndex, size_t* length)
 533 {
 534     struct Reader reader;
 535     ZDReaderInit(&reader, library, polygonIndex);
 536
 537     size_t listLength = 2 * 100;
 538     size_t listIndex = 0;
 539
 540     int32_t* list = malloc(sizeof(int32_t) * listLength);
 541     if(!list) {
 542         goto fail;
 543     }
 544
 545     while(1) {
 546         int32_t pointLat, pointLon;
 547         int result = ZDReaderGetPoint(&reader, &pointLat, &pointLon);
 548         if(result < 0) {
 549             goto fail;
 550         } else if(result == 0) {
 551             break;
 552         }
 553
 554         if(listIndex >= listLength) {
 555             listLength *= 2;
 556             if(listLength >= 1048576) {
 557                 goto fail;
 558             }
 559
 560             list = realloc(list, sizeof(int32_t) * listLength);
 561             if(!list) {
 562                 goto fail;
 563             }
 564         }
 565
 566         list[listIndex++] = pointLat;
 567         list[listIndex++] = pointLon;
 568     }
 569
 570     if(length) {
 571         *length = listIndex;
 572     }
 573
 574     return list;
 575
 576 fail:
 577     if(list) {
 578         free(list);
 579     }
 580     return NULL;
 581 }
 582
 583 float* ZDPolygonToList(const ZoneDetect *library, uint32_t polygonId, size_t* lengthPtr)
 584 {
 585     uint32_t polygonIndex;
 586     int32_t* data = NULL;
 587     float* flData = NULL;
 588
 589     if(!ZDFindPolygon(library, polygonId, NULL, &polygonIndex)) {
 590         goto fail;
 591     }
 592
 593     size_t length = 0;
 594     data = ZDPolygonToListInternal(library, polygonIndex, &length);
 595
 596     if(!data) {
 597         goto fail;
 598     }
 599
 600     flData = malloc(sizeof(float) * length);
 601     if(!flData) {
 602         goto fail;
 603     }
 604
 605     for(size_t i = 0; i<length; i+= 2) {
 606         int32_t lat = data[i];
 607         int32_t lon = data[i+1];
 608
 609         flData[i] = ZDFixedPointToFloat(lat, 90, library->precision);
 610         flData[i+1] = ZDFixedPointToFloat(lon, 180, library->precision);
 611     }
 612
 613     if(lengthPtr) {
 614         *lengthPtr = length;
 615     }
 616
 617     return flData;
 618
 619 fail:
 620     if(data) {
 621         free(data);
 622     }
 623     if(flData) {
 624         free(flData);
 625     }
 626     return NULL;
 627 }
 628
 629 static ZDLookupResult ZDPointInPolygon(const ZoneDetect *library, uint32_t polygonIndex, int32_t latFixedPoint, int32_t lonFixedPoint, uint64_t *distanceSqrMin)
 630 {
 631     int32_t pointLat, pointLon, prevLat = 0, prevLon = 0;
 632     int prevQuadrant = 0, winding = 0;
 633
 634     uint8_t first = 1;
 635
 636     struct Reader reader;
 637     ZDReaderInit(&reader, library, polygonIndex);
 638
 639     while(1) {
 640         int result = ZDReaderGetPoint(&reader, &pointLat, &pointLon);
 641         if(result < 0) {
 642             return ZD_LOOKUP_PARSE_ERROR;
 643         } else if(result == 0) {
 644             break;
 645         }
 646
 647         /* Check if point is ON the border */
 648         if(pointLat == latFixedPoint && pointLon == lonFixedPoint) {
 649             if(distanceSqrMin) *distanceSqrMin = 0;
 650             return ZD_LOOKUP_ON_BORDER_VERTEX;
 651         }
 652
 653         /* Find quadrant */
 654         int quadrant;
 655         if(pointLat >= latFixedPoint) {
 656             if(pointLon >= lonFixedPoint) {
 657                 quadrant = 0;
 658             } else {
 659                 quadrant = 1;
 660             }
 661         } else {
 662             if(pointLon >= lonFixedPoint) {
 663                 quadrant = 3;
 664             } else {
 665                 quadrant = 2;
 666             }
 667         }
 668
 669         if(!first) {
 670             int windingNeedCompare = 0, lineIsStraight = 0;
 671             float a = 0, b = 0;
 672
 673             /* Calculate winding number */
 674             if(quadrant == prevQuadrant) {
 675                 /* Do nothing */
 676             } else if(quadrant == (prevQuadrant + 1) % 4) {
 677                 winding ++;
 678             } else if((quadrant + 1) % 4 == prevQuadrant) {
 679                 winding --;
 680             } else {
 681                 windingNeedCompare = 1;
 682             }
 683
 684             /* Avoid horizontal and vertical lines */
 685             if((pointLon == prevLon || pointLat == prevLat)) {
 686                 lineIsStraight = 1;
 687             }
 688
 689             /* Calculate the parameters of y=ax+b if needed */
 690             if(!lineIsStraight && (distanceSqrMin || windingNeedCompare)) {
 691                 a = ((float)pointLat - (float)prevLat) / ((float)pointLon - (float)prevLon);
 692                 b = (float)pointLat - a * (float)pointLon;
 693             }
 694
 695             int onStraight = ZDPointInBox(pointLat, latFixedPoint, prevLat, pointLon, lonFixedPoint, prevLon);
 696             if(lineIsStraight && (onStraight || windingNeedCompare)) {
 697                 if(distanceSqrMin) *distanceSqrMin = 0;
 698                 return ZD_LOOKUP_ON_BORDER_SEGMENT;
 699             }
 700
 701             /* Jumped two quadrants. */
 702             if(windingNeedCompare) {
 703                 /* Check if the target is on the border */
 704                 const int32_t intersectLon = (int32_t)(((float)latFixedPoint - b) / a);
 705                 if(intersectLon >= lonFixedPoint-1 && intersectLon <= lonFixedPoint+1) {
 706                     if(distanceSqrMin) *distanceSqrMin = 0;
 707                     return ZD_LOOKUP_ON_BORDER_SEGMENT;
 708                 }
 709
 710                 /* Ok, it's not. In which direction did we go round the target? */
 711                 const int sign = (intersectLon < lonFixedPoint) ? 2 : -2;
 712                 if(quadrant == 2 || quadrant == 3) {
 713                     winding += sign;
 714                 } else {
 715                     winding -= sign;
 716                 }
 717             }
 718
 719             /* Calculate closest point on line (if needed) */
 720             if(distanceSqrMin) {
 721                 float closestLon, closestLat;
 722                 if(!lineIsStraight) {
 723                     closestLon = ((float)lonFixedPoint + a * (float)latFixedPoint - a * b) / (a * a + 1);
 724                     closestLat = (a * ((float)lonFixedPoint + a * (float)latFixedPoint) + b) / (a * a + 1);
 725                 } else {
 726                     if(pointLon == prevLon) {
 727                         closestLon = (float)pointLon;
 728                         closestLat = (float)latFixedPoint;
 729                     } else {
 730                         closestLon = (float)lonFixedPoint;
 731                         closestLat = (float)pointLat;
 732                     }
 733                 }
 734
 735                 const int closestInBox = ZDPointInBox(pointLon, (int32_t)closestLon, prevLon, pointLat, (int32_t)closestLat, prevLat);
 736
 737                 int64_t diffLat, diffLon;
 738                 if(closestInBox) {
 739                     /* Calculate squared distance to segment. */
 740                     diffLat = (int64_t)(closestLat - (float)latFixedPoint);
 741                     diffLon = (int64_t)(closestLon - (float)lonFixedPoint);
 742                 } else {
 743                     /*
 744                      * Calculate squared distance to vertices
 745                      * It is enough to check the current point since the polygon is closed.
 746                      */
 747                     diffLat = (int64_t)(pointLat - latFixedPoint);
 748                     diffLon = (int64_t)(pointLon - lonFixedPoint);
 749                 }
 750
 751                 /* Note: lon has half scale */
 752                 uint64_t distanceSqr = (uint64_t)(diffLat * diffLat) + (uint64_t)(diffLon * diffLon) * 4;
 753                 if(distanceSqr < *distanceSqrMin) *distanceSqrMin = distanceSqr;
 754             }
 755         }
 756
 757         prevQuadrant = quadrant;
 758         prevLat = pointLat;
 759         prevLon = pointLon;
 760         first = 0;
 761     };
 762
 763     if(winding == -4) {
 764         return ZD_LOOKUP_IN_ZONE;
 765     } else if(winding == 4) {
 766         return ZD_LOOKUP_IN_EXCLUDED_ZONE;
 767     } else if(winding == 0) {
 768         return ZD_LOOKUP_NOT_IN_ZONE;
 769     }
 770
 771     /* Should not happen */
 772     if(distanceSqrMin) *distanceSqrMin = 0;
 773     return ZD_LOOKUP_ON_BORDER_SEGMENT;
 774 }
 775
 776 void ZDCloseDatabase(ZoneDetect *library)
 777 {
 778     if(library) {
 779         if(library->fieldNames) {
 780             for(size_t i = 0; i < (size_t)library->numFields; i++) {
 781                 if(library->fieldNames[i]) {
 782                     free(library->fieldNames[i]);
 783                 }
 784             }
 785             free(library->fieldNames);
 786         }
 787         if(library->notice) {
 788             free(library->notice);
 789         }
 790
 791         if(library->closeType == 0) {
 792 #if defined(_MSC_VER) || defined(__MINGW32__)
 793             if(library->mapping && !UnmapViewOfFile(library->mapping)) zdError(ZD_E_DB_MUNMAP_MSVIEW, (int)GetLastError());
 794             if(library->fdMap && !CloseHandle(library->fdMap))         zdError(ZD_E_DB_MUNMAP, (int)GetLastError());
 795             if(library->fd && !CloseHandle(library->fd))               zdError(ZD_E_DB_CLOSE, (int)GetLastError());
 796 #else
 797             if(library->mapping && munmap(library->mapping, (size_t)(library->length))) zdError(ZD_E_DB_MUNMAP, errno);
 798             if(library->fd >= 0 && close(library->fd))                                  zdError(ZD_E_DB_CLOSE, errno);
 799 #endif
 800         }
 801
 802         free(library);
 803     }
 804 }
 805
 806 ZoneDetect *ZDOpenDatabaseFromMemory(void* buffer, size_t length)
 807 {
 808     ZoneDetect *const library = malloc(sizeof *library);
 809
 810     if(library) {
 811         memset(library, 0, sizeof(*library));
 812         library->closeType = 1;
 813         library->length = (long int)length;
 814
 815         if(library->length <= 0) {
 816             zdError(ZD_E_DB_SEEK, errno);
 817             goto fail;
 818         }
 819
 820         library->mapping = buffer;
 821
 822         /* Parse the header */
 823         if(ZDParseHeader(library)) {
 824             zdError(ZD_E_PARSE_HEADER, 0);
 825             goto fail;
 826         }
 827     }
 828
 829     return library;
 830
 831 fail:
 832     ZDCloseDatabase(library);
 833     return NULL;
 834 }
 835
 836 ZoneDetect *ZDOpenDatabase(const char *path)
 837 {
 838     ZoneDetect *const library = malloc(sizeof *library);
 839
 840     if(library) {
 841         memset(library, 0, sizeof(*library));
 842
 843 #if defined(_MSC_VER) || defined(__MINGW32__)
 844         library->fd = CreateFile(path, GENERIC_READ, 0, NULL, OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL, NULL);
 845         if (library->fd == INVALID_HANDLE_VALUE) {
 846             zdError(ZD_E_DB_OPEN, (int)GetLastError());
 847             goto fail;
 848         }
 849
 850         const DWORD fsize = GetFileSize(library->fd, NULL);
 851         if (fsize == INVALID_FILE_SIZE) {
 852             zdError(ZD_E_DB_SEEK, (int)GetLastError());
 853             goto fail;
 854         }
 855         library->length = (int32_t)fsize;
 856
 857         library->fdMap = CreateFileMappingA(library->fd, NULL, PAGE_READONLY, 0, 0, NULL);
 858         if (!library->fdMap) {
 859             zdError(ZD_E_DB_MMAP, (int)GetLastError());
 860             goto fail;
 861         }
 862
 863         library->mapping = MapViewOfFile(library->fdMap, FILE_MAP_READ, 0, 0, 0);
 864         if (!library->mapping) {
 865             zdError(ZD_E_DB_MMAP_MSVIEW, (int)GetLastError());
 866             goto fail;
 867         }
 868 #else
 869         library->fd = open(path, O_RDONLY | O_CLOEXEC);
 870         if(library->fd < 0) {
 871             zdError(ZD_E_DB_OPEN, errno);
 872             goto fail;
 873         }
 874
 875         library->length = lseek(library->fd, 0, SEEK_END);
 876         if(library->length <= 0 || library->length > 50331648) {
 877             zdError(ZD_E_DB_SEEK, errno);
 878             goto fail;
 879         }
 880         lseek(library->fd, 0, SEEK_SET);
 881
 882         library->mapping = mmap(NULL, (size_t)library->length, PROT_READ, MAP_PRIVATE | MAP_FILE, library->fd, 0);
 883         if(library->mapping == MAP_FAILED) {
 884             zdError(ZD_E_DB_MMAP, errno);
 885             goto fail;
 886         }
 887 #endif
 888
 889         /* Parse the header */
 890         if(ZDParseHeader(library)) {
 891             zdError(ZD_E_PARSE_HEADER, 0);
 892             goto fail;
 893         }
 894     }
 895
 896     return library;
 897
 898 fail:
 899     ZDCloseDatabase(library);
 900     return NULL;
 901 }
 902
 903 ZoneDetectResult *ZDLookup(const ZoneDetect *library, float lat, float lon, float *safezone)
 904 {
 905     const int32_t latFixedPoint = ZDFloatToFixedPoint(lat, 90, library->precision);
 906     const int32_t lonFixedPoint = ZDFloatToFixedPoint(lon, 180, library->precision);
 907     size_t numResults = 0;
 908     uint64_t distanceSqrMin = (uint64_t)-1;
 909
 910     /* Iterate over all polygons */
 911     uint32_t bboxIndex = library->bboxOffset;
 912     uint32_t metadataIndex = 0;
 913     uint32_t polygonIndex = 0;
 914
 915     ZoneDetectResult *results = malloc(sizeof *results);
 916     if(!results) {
 917         return NULL;
 918     }
 919
 920     uint32_t polygonId = 0;
 921
 922     while(bboxIndex < library->metadataOffset) {
 923         int32_t minLat, minLon, maxLat, maxLon, metadataIndexDelta;
 924         uint64_t polygonIndexDelta;
 925         if(!ZDDecodeVariableLengthSigned(library, &bboxIndex, &minLat)) break;
 926         if(!ZDDecodeVariableLengthSigned(library, &bboxIndex, &minLon)) break;
 927         if(!ZDDecodeVariableLengthSigned(library, &bboxIndex, &maxLat)) break;
 928         if(!ZDDecodeVariableLengthSigned(library, &bboxIndex, &maxLon)) break;
 929         if(!ZDDecodeVariableLengthSigned(library, &bboxIndex, &metadataIndexDelta)) break;
 930         if(!ZDDecodeVariableLengthUnsigned(library, &bboxIndex, &polygonIndexDelta)) break;
 931
 932         metadataIndex += (uint32_t)metadataIndexDelta;
 933         polygonIndex += (uint32_t)polygonIndexDelta;
 934
 935         if(latFixedPoint >= minLat) {
 936             if(latFixedPoint <= maxLat &&
 937                     lonFixedPoint >= minLon &&
 938                     lonFixedPoint <= maxLon) {
 939
 940                 const ZDLookupResult lookupResult = ZDPointInPolygon(library, library->dataOffset + polygonIndex, latFixedPoint, lonFixedPoint, (safezone) ? &distanceSqrMin : NULL);
 941                 if(lookupResult == ZD_LOOKUP_PARSE_ERROR) {
 942                     break;
 943                 } else if(lookupResult != ZD_LOOKUP_NOT_IN_ZONE) {
 944                     ZoneDetectResult *const newResults = realloc(results, sizeof *newResults * (numResults + 2));
 945
 946                     if(newResults) {
 947                         results = newResults;
 948                         results[numResults].polygonId = polygonId;
 949                         results[numResults].metaId = metadataIndex;
 950                         results[numResults].numFields = library->numFields;
 951                         results[numResults].fieldNames = library->fieldNames;
 952                         results[numResults].lookupResult = lookupResult;
 953
 954                         numResults++;
 955                     } else {
 956                         break;
 957                     }
 958                 }
 959             }
 960         } else {
 961             /* The data is sorted along minLat */
 962             break;
 963         }
 964
 965         polygonId++;
 966     }
 967
 968     /* Clean up results */
 969     for(size_t i = 0; i < numResults; i++) {
 970         int insideSum = 0;
 971         ZDLookupResult overrideResult = ZD_LOOKUP_IGNORE;
 972         for(size_t j = i; j < numResults; j++) {
 973             if(results[i].metaId == results[j].metaId) {
 974                 ZDLookupResult tmpResult = results[j].lookupResult;
 975                 results[j].lookupResult = ZD_LOOKUP_IGNORE;
 976
 977                 /* This is the same result. Is it an exclusion zone? */
 978                 if(tmpResult == ZD_LOOKUP_IN_ZONE) {
 979                     insideSum++;
 980                 } else if(tmpResult == ZD_LOOKUP_IN_EXCLUDED_ZONE) {
 981                     insideSum--;
 982                 } else {
 983                     /* If on the bodrder then the final result is on the border */
 984                     overrideResult = tmpResult;
 985                 }
 986
 987             }
 988         }
 989
 990         if(overrideResult != ZD_LOOKUP_IGNORE) {
 991             results[i].lookupResult = overrideResult;
 992         } else {
 993             if(insideSum) {
 994                 results[i].lookupResult = ZD_LOOKUP_IN_ZONE;
 995             }
 996         }
 997     }
 998
 999     /* Remove zones to ignore */
1000     size_t newNumResults = 0;
1001     for(size_t i = 0; i < numResults; i++) {
1002         if(results[i].lookupResult != ZD_LOOKUP_IGNORE) {
1003             results[newNumResults] = results[i];
1004             newNumResults++;
1005         }
1006     }
1007     numResults = newNumResults;
1008
1009     /* Lookup metadata */
1010     for(size_t i = 0; i < numResults; i++) {
1011         uint32_t tmpIndex = library->metadataOffset + results[i].metaId;
1012         results[i].data = malloc(library->numFields * sizeof *results[i].data);
1013         if(results[i].data) {
1014             for(size_t j = 0; j < library->numFields; j++) {
1015                 results[i].data[j] = ZDParseString(library, &tmpIndex);
1016             }
1017         }
1018     }
1019
1020     /* Write end marker */
1021     results[numResults].lookupResult = ZD_LOOKUP_END;
1022     results[numResults].numFields = 0;
1023     results[numResults].fieldNames = NULL;
1024     results[numResults].data = NULL;
1025
1026     if(safezone) {
1027         *safezone = sqrtf((float)distanceSqrMin) * 90 / (float)(1 << (library->precision - 1));
1028     }
1029
1030     return results;
1031 }
1032
1033 void ZDFreeResults(ZoneDetectResult *results)
1034 {
1035     unsigned int index = 0;
1036
1037     if(!results) {
1038         return;
1039     }
1040
1041     while(results[index].lookupResult != ZD_LOOKUP_END) {
1042         if(results[index].data) {
1043             for(size_t i = 0; i < (size_t)results[index].numFields; i++) {
1044                 if(results[index].data[i]) {
1045                     free(results[index].data[i]);
1046                 }
1047             }
1048             free(results[index].data);
1049         }
1050         index++;
1051     }
1052     free(results);
1053 }
1054
1055 const char *ZDGetNotice(const ZoneDetect *library)
1056 {
1057     return library->notice;
1058 }
1059
1060 uint8_t ZDGetTableType(const ZoneDetect *library)
1061 {
1062     return library->tableType;
1063 }
1064
1065 const char *ZDLookupResultToString(ZDLookupResult result)
1066 {
1067     switch(result) {
1068         case ZD_LOOKUP_IGNORE:
1069             return "Ignore";
1070         case ZD_LOOKUP_END:
1071             return "End";
1072         case ZD_LOOKUP_PARSE_ERROR:
1073             return "Parsing error";
1074         case ZD_LOOKUP_NOT_IN_ZONE:
1075             return "Not in zone";
1076         case ZD_LOOKUP_IN_ZONE:
1077             return "In zone";
1078         case ZD_LOOKUP_IN_EXCLUDED_ZONE:
1079             return "In excluded zone";
1080         case ZD_LOOKUP_ON_BORDER_VERTEX:
1081             return "Target point is border vertex";
1082         case ZD_LOOKUP_ON_BORDER_SEGMENT:
1083             return "Target point is on border";
1084     }
1085
1086     return "Unknown";
1087 }
1088
1089 #define ZD_E_COULD_NOT(msg) "could not " msg
1090
1091 const char *ZDGetErrorString(int errZD)
1092 {
1093     switch ((enum ZDInternalError)errZD) {
1094         default:
1095             assert(0);
1096         case ZD_OK                :
1097             return "";
1098         case ZD_E_DB_OPEN         :
1099             return ZD_E_COULD_NOT("open database file");
1100         case ZD_E_DB_SEEK         :
1101             return ZD_E_COULD_NOT("retrieve database file size");
1102         case ZD_E_DB_MMAP         :
1103             return ZD_E_COULD_NOT("map database file to system memory");
1104 #if defined(_MSC_VER) || defined(__MINGW32__)
1105         case ZD_E_DB_MMAP_MSVIEW  :
1106             return ZD_E_COULD_NOT("open database file view");
1107         case ZD_E_DB_MAP_EXCEPTION:
1108             return "I/O exception occurred while accessing database file view";
1109         case ZD_E_DB_MUNMAP_MSVIEW:
1110             return ZD_E_COULD_NOT("close database file view");
1111 #endif
1112         case ZD_E_DB_MUNMAP       :
1113             return ZD_E_COULD_NOT("unmap database");
1114         case ZD_E_DB_CLOSE        :
1115             return ZD_E_COULD_NOT("close database file");
1116         case ZD_E_PARSE_HEADER    :
1117             return ZD_E_COULD_NOT("parse database header");
1118     }
1119 }
1120
1121 #undef ZD_E_COULD_NOT
1122
1123 int ZDSetErrorHandler(void (*handler)(int, int))
1124 {
1125     zdErrorHandler = handler;
1126     return 0;
1127 }
1128
1129 char* ZDHelperSimpleLookupString(const ZoneDetect* library, float lat, float lon)
1130 {
1131     ZoneDetectResult *result = ZDLookup(library, lat, lon, NULL);
1132     if(!result) {
1133         return NULL;
1134     }
1135
1136     char* output = NULL;
1137
1138     if(result[0].lookupResult == ZD_LOOKUP_END) {
1139         goto done;
1140     }
1141
1142     char* strings[2] = {NULL};
1143
1144     for(unsigned int i = 0; i < result[0].numFields; i++) {
1145         if(result[0].fieldNames[i] && result[0].data[i]) {
1146             if(library->tableType == 'T') {
1147                 if(!strcmp(result[0].fieldNames[i], "TimezoneIdPrefix")) {
1148                     strings[0] = result[0].data[i];
1149                 }
1150                 if(!strcmp(result[0].fieldNames[i], "TimezoneId")) {
1151                     strings[1] = result[0].data[i];
1152                 }
1153             }
1154             if(library->tableType == 'C') {
1155                 if(!strcmp(result[0].fieldNames[i], "Name")) {
1156                     strings[0] = result[0].data[i];
1157                 }
1158             }
1159         }
1160     }
1161
1162     size_t length = 0;
1163     for(unsigned int i=0; i<sizeof(strings)/sizeof(char*); i++) {
1164         if(strings[i]) {
1165             size_t partLength = strlen(strings[i]);
1166             if(partLength > 512) {
1167                 goto done;
1168             }
1169             length += partLength;
1170         }
1171     }
1172
1173     if(length == 0) {
1174         goto done;
1175     }
1176
1177     length += 1;
1178
1179     output = (char*)malloc(length);
1180     output[0] = 0;
1181     for(unsigned int i=0; i<sizeof(strings)/sizeof(char*); i++) {
1182         if(strings[i]) {
1183             strcat(output + strlen(output), strings[i]);
1184         }
1185     }
1186
1187 done:
1188     ZDFreeResults(result);
1189     return output;
1190 }