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 <stdint.h>
  30 #include <stdio.h>
  31 #include <stdlib.h>
  32 #include <string.h>
  33 #include <math.h>
  34 #if defined(_MSC_VER) || defined(__MINGW32__)
  35   #include <windows.h>
  36 #else
  37   #include <errno.h>
  38   #include <sys/mman.h>
  39   #include <fcntl.h>
  40   #include <unistd.h>
  41 #endif
  42
  43 #include "zonedetect.h"
  44
  45 enum ZDInternalError {
  46     ZD_OK,
  47     ZD_E_DB_OPEN,
  48     ZD_E_DB_SEEK,
  49     ZD_E_DB_MMAP,
  50 #if defined(_MSC_VER) || defined(__MINGW32__)
  51     ZD_E_DB_MMAP_MSVIEW,
  52     ZD_E_DB_MAP_EXCEPTION,
  53     ZD_E_DB_MUNMAP_MSVIEW,
  54 #endif
  55     ZD_E_DB_MUNMAP,
  56     ZD_E_DB_CLOSE,
  57     ZD_E_PARSE_HEADER
  58 };
  59
  60 struct ZoneDetectOpaque {
  61 #if defined(_MSC_VER) || defined(__MINGW32__)
  62     HANDLE fd;
  63     HANDLE fdMap;
  64     int32_t length;
  65     int32_t padding;
  66 #else
  67     int fd;
  68     off_t length;
  69 #endif
  70
  71     uint8_t *mapping;
  72
  73     uint8_t tableType;
  74     uint8_t version;
  75     uint8_t precision;
  76     uint8_t numFields;
  77
  78     char *notice;
  79     char **fieldNames;
  80
  81     uint32_t bboxOffset;
  82     uint32_t metadataOffset;
  83     uint32_t dataOffset;
  84 };
  85
  86 static void (*zdErrorHandler)(int, int);
  87 static void zdError(enum ZDInternalError errZD, int errNative)
  88 {
  89     if (zdErrorHandler) zdErrorHandler((int)errZD, errNative);
  90 }
  91
  92 static int32_t ZDFloatToFixedPoint(float input, float scale, unsigned int precision)
  93 {
  94     const float inputScaled = input / scale;
  95     return (int32_t)(inputScaled * (float)(1 << (precision - 1)));
  96 }
  97
  98 static unsigned int ZDDecodeVariableLengthUnsigned(const ZoneDetect *library, uint32_t *index, uint32_t *result)
  99 {
 100     if(*index >= (uint32_t)library->length) {
 101         return 0;
 102     }
 103
 104     uint32_t value = 0;
 105     unsigned int i = 0;
 106 #if defined(_MSC_VER)
 107     __try {
 108 #endif
 109     uint8_t *const buffer = library->mapping + *index;
 110     uint8_t *const bufferEnd = library->mapping + library->length - 1;
 111
 112     unsigned int shift = 0;
 113     while(1) {
 114         value |= (uint32_t)((buffer[i] & UINT8_C(0x7F)) << shift);
 115         shift += 7u;
 116
 117         if(!(buffer[i] & UINT8_C(0x80))) {
 118             break;
 119         }
 120
 121         i++;
 122         if(buffer + i > bufferEnd) {
 123             return 0;
 124         }
 125     }
 126 #if defined(_MSC_VER)
 127     } __except(GetExceptionCode() == EXCEPTION_IN_PAGE_ERROR
 128       ? EXCEPTION_EXECUTE_HANDLER
 129       : EXCEPTION_CONTINUE_SEARCH) { /* file mapping SEH exception occurred */
 130         zdError(ZD_E_DB_MAP_EXCEPTION, (int)GetLastError());
 131         return 0;
 132     }
 133 #endif
 134
 135     i++;
 136     *result = value;
 137     *index += i;
 138     return i;
 139 }
 140
 141 static unsigned int ZDDecodeVariableLengthSigned(const ZoneDetect *library, uint32_t *index, int32_t *result)
 142 {
 143     uint32_t value = 0;
 144     const unsigned int retVal = ZDDecodeVariableLengthUnsigned(library, index, &value);
 145     *result = (value & 1) ? -(int32_t)(value / 2) : (int32_t)(value / 2);
 146     return retVal;
 147 }
 148
 149 static char *ZDParseString(const ZoneDetect *library, uint32_t *index)
 150 {
 151     uint32_t strLength;
 152     if(!ZDDecodeVariableLengthUnsigned(library, index, &strLength)) {
 153         return NULL;
 154     }
 155
 156     uint32_t strOffset = *index;
 157     unsigned int remoteStr = 0;
 158     if(strLength >= 256) {
 159         strOffset = library->metadataOffset + strLength - 256;
 160         remoteStr = 1;
 161
 162         if(!ZDDecodeVariableLengthUnsigned(library, &strOffset, &strLength)) {
 163             return NULL;
 164         }
 165
 166         if(strLength > 256) {
 167             return NULL;
 168         }
 169     }
 170
 171     char *const str = malloc(strLength + 1);
 172
 173     if(str) {
 174 #if defined(_MSC_VER)
 175     __try {
 176 #endif
 177         for(size_t i = 0; i < strLength; i++) {
 178             str[i] = (char)(library->mapping[strOffset + i] ^ UINT8_C(0x80));
 179         }
 180 #if defined(_MSC_VER)
 181     } __except(GetExceptionCode() == EXCEPTION_IN_PAGE_ERROR
 182       ? EXCEPTION_EXECUTE_HANDLER
 183       : EXCEPTION_CONTINUE_SEARCH) { /* file mapping SEH exception occurred */
 184         zdError(ZD_E_DB_MAP_EXCEPTION, (int)GetLastError());
 185         return 0;
 186     }
 187 #endif
 188         str[strLength] = 0;
 189     }
 190
 191     if(!remoteStr) {
 192         *index += strLength;
 193     }
 194
 195     return str;
 196 }
 197
 198 static int ZDParseHeader(ZoneDetect *library)
 199 {
 200     if(library->length < 7) {
 201         return -1;
 202     }
 203
 204 #if defined(_MSC_VER)
 205     __try {
 206 #endif
 207     if(memcmp(library->mapping, "PLB", 3)) {
 208         return -1;
 209     }
 210
 211     library->tableType = library->mapping[3];
 212     library->version   = library->mapping[4];
 213     library->precision = library->mapping[5];
 214     library->numFields = library->mapping[6];
 215 #if defined(_MSC_VER)
 216     } __except(GetExceptionCode() == EXCEPTION_IN_PAGE_ERROR
 217       ? EXCEPTION_EXECUTE_HANDLER
 218       : EXCEPTION_CONTINUE_SEARCH) { /* file mapping SEH exception occurred */
 219         zdError(ZD_E_DB_MAP_EXCEPTION, (int)GetLastError());
 220         return 0;
 221     }
 222 #endif
 223
 224     if(library->version != 0) {
 225         return -1;
 226     }
 227
 228     uint32_t index = UINT32_C(7);
 229
 230     library->fieldNames = malloc(library->numFields * sizeof *library->fieldNames);
 231     for(size_t i = 0; i < library->numFields; i++) {
 232         library->fieldNames[i] = ZDParseString(library, &index);
 233     }
 234
 235     library->notice = ZDParseString(library, &index);
 236     if(!library->notice) {
 237         return -1;
 238     }
 239
 240     uint32_t tmp;
 241     /* Read section sizes */
 242     /* By memset: library->bboxOffset = 0 */
 243
 244     if(!ZDDecodeVariableLengthUnsigned(library, &index, &tmp)) return -1;
 245     library->metadataOffset = tmp + library->bboxOffset;
 246
 247     if(!ZDDecodeVariableLengthUnsigned(library, &index, &tmp))return -1;
 248     library->dataOffset = tmp + library->metadataOffset;
 249
 250     if(!ZDDecodeVariableLengthUnsigned(library, &index, &tmp)) return -1;
 251
 252     /* Add header size to everything */
 253     library->bboxOffset += index;
 254     library->metadataOffset += index;
 255     library->dataOffset += index;
 256
 257     /* Verify file length */
 258     if(tmp + library->dataOffset != (uint32_t)library->length) {
 259         return -2;
 260     }
 261
 262     return 0;
 263 }
 264
 265 static int ZDPointInBox(int32_t xl, int32_t x, int32_t xr, int32_t yl, int32_t y, int32_t yr)
 266 {
 267     if((xl <= x && x <= xr) || (xr <= x && x <= xl)) {
 268         if((yl <= y && y <= yr) || (yr <= y && y <= yl)) {
 269             return 1;
 270         }
 271     }
 272
 273     return 0;
 274 }
 275
 276 static ZDLookupResult ZDPointInPolygon(const ZoneDetect *library, uint32_t polygonIndex, int32_t latFixedPoint, int32_t lonFixedPoint, uint64_t *distanceSqrMin)
 277 {
 278     uint32_t numVertices;
 279     int32_t pointLat = 0, pointLon = 0, diffLat = 0, diffLon = 0, firstLat = 0, firstLon = 0, prevLat = 0, prevLon = 0;
 280     lonFixedPoint -= 3;
 281
 282     /* Read number of vertices */
 283     if(!ZDDecodeVariableLengthUnsigned(library, &polygonIndex, &numVertices)) return ZD_LOOKUP_PARSE_ERROR;
 284     if(numVertices > 1000000) return ZD_LOOKUP_PARSE_ERROR;
 285
 286     int prevQuadrant = 0, winding = 0;
 287
 288     for(size_t i = 0; i <= (size_t)numVertices; i++) {
 289         if(i < (size_t)numVertices) {
 290             if(!ZDDecodeVariableLengthSigned(library, &polygonIndex, &diffLat)) return ZD_LOOKUP_PARSE_ERROR;
 291             if(!ZDDecodeVariableLengthSigned(library, &polygonIndex, &diffLon)) return ZD_LOOKUP_PARSE_ERROR;
 292             pointLat += diffLat;
 293             pointLon += diffLon;
 294             if(i == 0) {
 295                 firstLat = pointLat;
 296                 firstLon = pointLon;
 297             }
 298         } else {
 299             /* The polygons should be closed, but just in case */
 300             pointLat = firstLat;
 301             pointLon = firstLon;
 302         }
 303
 304         /* Check if point is ON the border */
 305         if(pointLat == latFixedPoint && pointLon == lonFixedPoint) {
 306             if(distanceSqrMin) *distanceSqrMin = 0;
 307             return ZD_LOOKUP_ON_BORDER_VERTEX;
 308         }
 309
 310         /* Find quadrant */
 311         int quadrant;
 312         if(pointLat >= latFixedPoint) {
 313             if(pointLon >= lonFixedPoint) {
 314                 quadrant = 0;
 315             } else {
 316                 quadrant = 1;
 317             }
 318         } else {
 319             if(pointLon >= lonFixedPoint) {
 320                 quadrant = 3;
 321             } else {
 322                 quadrant = 2;
 323             }
 324         }
 325
 326         if(i > 0) {
 327             int windingNeedCompare = 0, lineIsStraight = 0;
 328             float a = 0, b = 0;
 329
 330             /* Calculate winding number */
 331             if(quadrant == prevQuadrant) {
 332                 /* Do nothing */
 333             } else if(quadrant == (prevQuadrant + 1) % 4) {
 334                 winding ++;
 335             } else if((quadrant + 1) % 4 == prevQuadrant) {
 336                 winding --;
 337             } else {
 338                 windingNeedCompare = 1;
 339             }
 340
 341             /* Avoid horizontal and vertical lines */
 342             if((pointLon == prevLon || pointLat == prevLat)) {
 343                 lineIsStraight = 1;
 344             }
 345
 346             /* Calculate the parameters of y=ax+b if needed */
 347             if(!lineIsStraight && (distanceSqrMin || windingNeedCompare)) {
 348                 a = ((float)pointLat - (float)prevLat) / ((float)pointLon - (float)prevLon);
 349                 b = (float)pointLat - a * (float)pointLon;
 350             }
 351
 352             /* Jumped two quadrants. */
 353             if(windingNeedCompare) {
 354                 if(lineIsStraight) {
 355                     if(distanceSqrMin) *distanceSqrMin = 0;
 356                     return ZD_LOOKUP_ON_BORDER_SEGMENT;
 357                 }
 358
 359                 /* Check if the target is on the border */
 360                 const int32_t intersectLon = (int32_t)(((float)latFixedPoint - b) / a);
 361                 if(intersectLon == lonFixedPoint) {
 362                     if(distanceSqrMin) *distanceSqrMin = 0;
 363                     return ZD_LOOKUP_ON_BORDER_SEGMENT;
 364                 }
 365
 366                 /* Ok, it's not. In which direction did we go round the target? */
 367                 const int sign = (intersectLon < lonFixedPoint) ? 2 : -2;
 368                 if(quadrant == 2 || quadrant == 3) {
 369                     winding += sign;
 370                 } else {
 371                     winding -= sign;
 372                 }
 373             }
 374
 375             /* Calculate closest point on line (if needed) */
 376             if(distanceSqrMin) {
 377                 float closestLon, closestLat;
 378                 if(!lineIsStraight) {
 379                     closestLon = ((float)lonFixedPoint + a * (float)latFixedPoint - a * b) / (a * a + 1);
 380                     closestLat = (a * ((float)lonFixedPoint + a * (float)latFixedPoint) + b) / (a * a + 1);
 381                 } else {
 382                     if(pointLon == prevLon) {
 383                         closestLon = (float)pointLon;
 384                         closestLat = (float)latFixedPoint;
 385                     } else {
 386                         closestLon = (float)lonFixedPoint;
 387                         closestLat = (float)pointLat;
 388                     }
 389                 }
 390
 391                 const int closestInBox = ZDPointInBox(pointLon, (int32_t)closestLon, prevLon, pointLat, (int32_t)closestLat, prevLat);
 392
 393                 int64_t diffLat, diffLon;
 394                 if(closestInBox) {
 395                     /* Calculate squared distance to segment. */
 396                     diffLat = (int64_t)(closestLat - (float)latFixedPoint);
 397                     diffLon = (int64_t)(closestLon - (float)lonFixedPoint);
 398                 } else {
 399                     /*
 400                      * Calculate squared distance to vertices
 401                      * It is enough to check the current point since the polygon is closed.
 402                      */
 403                     diffLat = (int64_t)(pointLat - latFixedPoint);
 404                     diffLon = (int64_t)(pointLon - lonFixedPoint);
 405                 }
 406
 407                 /* Note: lon has half scale */
 408                 uint64_t distanceSqr = (uint64_t)(diffLat * diffLat) + (uint64_t)(diffLon * diffLon) * 4;
 409                 if(distanceSqr < *distanceSqrMin) *distanceSqrMin = distanceSqr;
 410             }
 411         }
 412
 413         prevQuadrant = quadrant;
 414         prevLat = pointLat;
 415         prevLon = pointLon;
 416     }
 417
 418     if(winding == -4) {
 419         return ZD_LOOKUP_IN_ZONE;
 420     } else if(winding == 4) {
 421         return ZD_LOOKUP_IN_EXCLUDED_ZONE;
 422     } else if(winding == 0) {
 423         return ZD_LOOKUP_NOT_IN_ZONE;
 424     }
 425
 426     /* Should not happen */
 427     if(distanceSqrMin) *distanceSqrMin = 0;
 428     return ZD_LOOKUP_ON_BORDER_SEGMENT;
 429 }
 430
 431 void ZDCloseDatabase(ZoneDetect *library)
 432 {
 433     if(library) {
 434         if(library->fieldNames) {
 435             for(size_t i = 0; i < (size_t)library->numFields; i++) {
 436                 if(library->fieldNames[i]) {
 437                     free(library->fieldNames[i]);
 438                 }
 439             }
 440             free(library->fieldNames);
 441         }
 442         if(library->notice) {
 443             free(library->notice);
 444         }
 445
 446 #if defined(_MSC_VER) || defined(__MINGW32__)
 447         if(!UnmapViewOfFile(library->mapping)) zdError(ZD_E_DB_MUNMAP_MSVIEW, (int)GetLastError());
 448         if(!CloseHandle(library->fdMap))       zdError(ZD_E_DB_MUNMAP       , (int)GetLastError());
 449         if(!CloseHandle(library->fd))          zdError(ZD_E_DB_CLOSE        , (int)GetLastError());
 450 #else
 451         if(library->mapping && munmap(library->mapping, (size_t)(library->length))) zdError(ZD_E_DB_MUNMAP, errno);
 452         if(library->fd >= 0 && close(library->fd))                                  zdError(ZD_E_DB_CLOSE , errno);
 453 #endif
 454
 455         free(library);
 456     }
 457 }
 458
 459 ZoneDetect *ZDOpenDatabase(const char *path)
 460 {
 461     ZoneDetect *const library = malloc(sizeof *library);
 462
 463     if(library) {
 464         memset(library, 0, sizeof(*library));
 465
 466 #if defined(_MSC_VER) || defined(__MINGW32__)
 467         library->fd = CreateFile(path, GENERIC_READ, 0, NULL, OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL, NULL);
 468         if (library->fd == INVALID_HANDLE_VALUE) {
 469             zdError(ZD_E_DB_OPEN, (int)GetLastError());
 470             goto fail;
 471         }
 472
 473         const DWORD fsize = GetFileSize(library->fd, NULL);
 474         if (fsize == INVALID_FILE_SIZE) {
 475             zdError(ZD_E_DB_SEEK, (int)GetLastError());
 476             goto fail;
 477         }
 478         library->length = (int32_t)fsize;
 479
 480         library->fdMap = CreateFileMappingA(library->fd, NULL, PAGE_READONLY, 0, 0, NULL);
 481         if (!library->fdMap) {
 482             zdError(ZD_E_DB_MMAP, (int)GetLastError());
 483             goto fail;
 484         }
 485
 486         library->mapping = MapViewOfFile(library->fdMap, FILE_MAP_READ, 0, 0, 0);
 487         if (!library->mapping) {
 488             zdError(ZD_E_DB_MMAP_MSVIEW, (int)GetLastError());
 489             goto fail;
 490         }
 491 #else
 492         library->fd = open(path, O_RDONLY | O_CLOEXEC);
 493         if(library->fd < 0) {
 494             zdError(ZD_E_DB_OPEN, errno);
 495             goto fail;
 496         }
 497
 498         library->length = lseek(library->fd, 0, SEEK_END);
 499         if(library->length <= 0) {
 500             zdError(ZD_E_DB_SEEK, errno);
 501             goto fail;
 502         }
 503         lseek(library->fd, 0, SEEK_SET);
 504
 505         library->mapping = mmap(NULL, (size_t)library->length, PROT_READ, MAP_PRIVATE | MAP_FILE, library->fd, 0);
 506         if(!library->mapping) {
 507             zdError(ZD_E_DB_MMAP, errno);
 508             goto fail;
 509         }
 510 #endif
 511
 512         /* Parse the header */
 513         if(ZDParseHeader(library)) {
 514             zdError(ZD_E_PARSE_HEADER, 0);
 515             goto fail;
 516         }
 517     }
 518
 519     return library;
 520
 521 fail:
 522     ZDCloseDatabase(library);
 523     return NULL;
 524 }
 525
 526 ZoneDetectResult *ZDLookup(const ZoneDetect *library, float lat, float lon, float *safezone)
 527 {
 528     const int32_t latFixedPoint = ZDFloatToFixedPoint(lat, 90, library->precision);
 529     const int32_t lonFixedPoint = ZDFloatToFixedPoint(lon, 180, library->precision);
 530     size_t numResults = 0;
 531     uint64_t distanceSqrMin = (uint64_t)-1;
 532
 533     /* Iterate over all polygons */
 534     uint32_t bboxIndex = library->bboxOffset;
 535     uint32_t metadataIndex = 0;
 536     uint32_t polygonIndex = 0;
 537
 538     ZoneDetectResult *results = malloc(sizeof *results);
 539     if(!results) {
 540         return NULL;
 541     }
 542
 543     while(bboxIndex < library->metadataOffset) {
 544         int32_t minLat, minLon, maxLat, maxLon, metadataIndexDelta;
 545         uint32_t polygonIndexDelta;
 546         if(!ZDDecodeVariableLengthSigned(library, &bboxIndex, &minLat)) break;
 547         if(!ZDDecodeVariableLengthSigned(library, &bboxIndex, &minLon)) break;
 548         if(!ZDDecodeVariableLengthSigned(library, &bboxIndex, &maxLat)) break;
 549         if(!ZDDecodeVariableLengthSigned(library, &bboxIndex, &maxLon)) break;
 550         if(!ZDDecodeVariableLengthSigned(library, &bboxIndex, &metadataIndexDelta)) break;
 551         if(!ZDDecodeVariableLengthUnsigned(library, &bboxIndex, &polygonIndexDelta)) break;
 552
 553         metadataIndex += (uint32_t)metadataIndexDelta;
 554         polygonIndex += polygonIndexDelta;
 555
 556         if(latFixedPoint >= minLat) {
 557             if(latFixedPoint <= maxLat &&
 558                     lonFixedPoint >= minLon &&
 559                     lonFixedPoint <= maxLon) {
 560
 561                 /* Indices valid? */
 562                 if(library->metadataOffset + metadataIndex >= library->dataOffset) continue;
 563                 if(library->dataOffset + polygonIndex >= (uint32_t)library->length) continue;
 564
 565                 const ZDLookupResult lookupResult = ZDPointInPolygon(library, library->dataOffset + polygonIndex, latFixedPoint, lonFixedPoint, (safezone) ? &distanceSqrMin : NULL);
 566                 if(lookupResult == ZD_LOOKUP_PARSE_ERROR) {
 567                     break;
 568                 } else if(lookupResult != ZD_LOOKUP_NOT_IN_ZONE) {
 569                     ZoneDetectResult *const newResults = realloc(results, sizeof *newResults * (numResults + 2));
 570
 571                     if(newResults) {
 572                         results = newResults;
 573                         results[numResults].metaId = metadataIndex;
 574                         results[numResults].numFields = library->numFields;
 575                         results[numResults].fieldNames = library->fieldNames;
 576                         results[numResults].lookupResult = lookupResult;
 577
 578                         numResults++;
 579                     } else {
 580                         break;
 581                     }
 582                 }
 583             }
 584         } else {
 585             /* The data is sorted along minLat */
 586             break;
 587         }
 588     }
 589
 590     /* Clean up results */
 591     for(size_t i = 0; i < numResults; i++) {
 592         int insideSum = 0;
 593         ZDLookupResult overrideResult = ZD_LOOKUP_IGNORE;
 594         for(size_t j = i; j < numResults; j++) {
 595             if(results[i].metaId == results[j].metaId) {
 596                 ZDLookupResult tmpResult = results[j].lookupResult;
 597                 results[j].lookupResult = ZD_LOOKUP_IGNORE;
 598
 599                 /* This is the same result. Is it an exclusion zone? */
 600                 if(tmpResult == ZD_LOOKUP_IN_ZONE) {
 601                     insideSum++;
 602                 } else if(tmpResult == ZD_LOOKUP_IN_EXCLUDED_ZONE) {
 603                     insideSum--;
 604                 } else {
 605                     /* If on the bodrder then the final result is on the border */
 606                     overrideResult = tmpResult;
 607                 }
 608
 609             }
 610         }
 611
 612         if(overrideResult != ZD_LOOKUP_IGNORE) {
 613             results[i].lookupResult = overrideResult;
 614         } else {
 615             if(insideSum) {
 616                 results[i].lookupResult = ZD_LOOKUP_IN_ZONE;
 617             }
 618         }
 619     }
 620
 621     /* Remove zones to ignore */
 622     size_t newNumResults = 0;
 623     for(size_t i = 0; i < numResults; i++) {
 624         if(results[i].lookupResult != ZD_LOOKUP_IGNORE) {
 625             results[newNumResults] = results[i];
 626             newNumResults++;
 627         }
 628     }
 629     numResults = newNumResults;
 630
 631     /* Lookup metadata */
 632     for(size_t i = 0; i < numResults; i++) {
 633         uint32_t tmpIndex = library->metadataOffset + results[i].metaId;
 634         results[i].data = malloc(library->numFields * sizeof *results[i].data);
 635         if(results[i].data) {
 636             for(size_t j = 0; j < library->numFields; j++) {
 637                 results[i].data[j] = ZDParseString(library, &tmpIndex);
 638             }
 639         }
 640     }
 641
 642     /* Write end marker */
 643     results[numResults].lookupResult = ZD_LOOKUP_END;
 644     results[numResults].numFields = 0;
 645     results[numResults].fieldNames = NULL;
 646     results[numResults].data = NULL;
 647
 648     if(safezone) {
 649         *safezone = sqrtf((float)distanceSqrMin) * 90 / (float)(1 << (library->precision - 1));
 650     }
 651
 652     return results;
 653 }
 654
 655 void ZDFreeResults(ZoneDetectResult *results)
 656 {
 657     unsigned int index = 0;
 658
 659     if(!results) {
 660         return;
 661     }
 662
 663     while(results[index].lookupResult != ZD_LOOKUP_END) {
 664         if(results[index].data) {
 665             for(size_t i = 0; i < (size_t)results[index].numFields; i++) {
 666                 if(results[index].data[i]) {
 667                     free(results[index].data[i]);
 668                 }
 669             }
 670             free(results[index].data);
 671         }
 672         index++;
 673     }
 674     free(results);
 675 }
 676
 677 const char *ZDGetNotice(const ZoneDetect *library)
 678 {
 679     return library->notice;
 680 }
 681
 682 uint8_t ZDGetTableType(const ZoneDetect *library)
 683 {
 684     return library->tableType;
 685 }
 686
 687 const char *ZDLookupResultToString(ZDLookupResult result)
 688 {
 689     switch(result) {
 690         case ZD_LOOKUP_IGNORE:
 691             return "Ignore";
 692         case ZD_LOOKUP_END:
 693             return "End";
 694         case ZD_LOOKUP_PARSE_ERROR:
 695             return "Parsing error";
 696         case ZD_LOOKUP_NOT_IN_ZONE:
 697             return "Not in zone";
 698         case ZD_LOOKUP_IN_ZONE:
 699             return "In zone";
 700         case ZD_LOOKUP_IN_EXCLUDED_ZONE:
 701             return "In excluded zone";
 702         case ZD_LOOKUP_ON_BORDER_VERTEX:
 703             return "Target point is border vertex";
 704         case ZD_LOOKUP_ON_BORDER_SEGMENT:
 705             return "Target point is on border";
 706     }
 707
 708     return "Unknown";
 709 }
 710
 711 #define ZD_E_COULD_NOT(msg) "could not " msg
 712
 713 const char *ZDGetErrorString(int errZD)
 714 {
 715     switch ((enum ZDInternalError)errZD) {
 716         default: assert(0);
 717         case ZD_OK                : return "";
 718         case ZD_E_DB_OPEN         : return ZD_E_COULD_NOT("open database file");
 719         case ZD_E_DB_SEEK         : return ZD_E_COULD_NOT("retrieve database file size");
 720         case ZD_E_DB_MMAP         : return ZD_E_COULD_NOT("map database file to system memory");
 721 #if defined(_MSC_VER) || defined(__MINGW32__)
 722         case ZD_E_DB_MMAP_MSVIEW  : return ZD_E_COULD_NOT("open database file view");
 723         case ZD_E_DB_MAP_EXCEPTION: return "I/O exception occurred while accessing database file view";
 724         case ZD_E_DB_MUNMAP_MSVIEW: return ZD_E_COULD_NOT("close database file view");
 725 #endif
 726         case ZD_E_DB_MUNMAP       : return ZD_E_COULD_NOT("unmap database");
 727         case ZD_E_DB_CLOSE        : return ZD_E_COULD_NOT("close database file");
 728         case ZD_E_PARSE_HEADER    : return ZD_E_COULD_NOT("parse database header");
 729     }
 730 }
 731
 732 #undef ZD_E_COULD_NOT
 733
 734 int ZDSetErrorHandler(void (*handler)(int, int))
 735 {
 736     zdErrorHandler = handler;
 737     return 0;
 738 }