2 * Copyright (c) 2018, Bertold Van den Bergh (vandenbergh@bertold.org)
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.
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.
32 #if defined(_MSC_VER) || defined(__MINGW32__)
34 #elif defined(__APPLE__) || defined(__linux__) || defined(__unix__) || defined(_POSIX_VERSION)
44 #include "zonedetect.h"
46 enum ZDInternalError {
51 #if defined(_MSC_VER) || defined(__MINGW32__)
53 ZD_E_DB_MAP_EXCEPTION,
54 ZD_E_DB_MUNMAP_MSVIEW,
62 #if defined(_MSC_VER) || defined(__MINGW32__)
67 #elif defined(__APPLE__) || defined(__linux__) || defined(__unix__) || defined(_POSIX_VERSION)
86 uint32_t metadataOffset;
90 static void (*zdErrorHandler)(int, int);
91 static void zdError(enum ZDInternalError errZD, int errNative)
93 if (zdErrorHandler) zdErrorHandler(static_cast<int>(errZD), errNative);
96 static int32_t ZDFloatToFixedPoint(float input, float scale, unsigned int precision)
98 const float inputScaled = input / scale;
99 return static_cast<int32_t>(inputScaled * static_cast<float>(1 << (precision - 1)));
102 static float ZDFixedPointToFloat(int32_t input, float scale, unsigned int precision)
104 const float value = static_cast<float>(input) / static_cast<float>(1 << (precision - 1));
105 return value * scale;
108 static unsigned int ZDDecodeVariableLengthUnsigned(const ZoneDetect *library, uint32_t *index, uint64_t *result)
110 if(*index >= static_cast<uint32_t>(library->length)) {
116 #if defined(_MSC_VER)
119 uint8_t *const buffer = library->mapping + *index;
120 uint8_t *const bufferEnd = library->mapping + library->length - 1;
122 unsigned int shift = 0;
124 value |= (((static_cast<uint64_t>(buffer[i])) & UINT8_C(0x7F)) << shift);
127 if(!(buffer[i] & UINT8_C(0x80))) {
132 if(buffer + i > bufferEnd) {
136 #if defined(_MSC_VER)
137 } __except(GetExceptionCode() == EXCEPTION_IN_PAGE_ERROR
138 ? EXCEPTION_EXECUTE_HANDLER
139 : EXCEPTION_CONTINUE_SEARCH) { /* file mapping SEH exception occurred */
140 zdError(ZD_E_DB_MAP_EXCEPTION, (int)GetLastError());
151 static unsigned int ZDDecodeVariableLengthUnsignedReverse(const ZoneDetect *library, uint32_t *index, uint64_t *result)
155 if(*index >= static_cast<uint32_t>(library->length)) {
159 #if defined(_MSC_VER)
163 if(library->mapping[i] & UINT8_C(0x80)) {
172 while(library->mapping[i] & UINT8_C(0x80)) {
179 #if defined(_MSC_VER)
180 } __except(GetExceptionCode() == EXCEPTION_IN_PAGE_ERROR
181 ? EXCEPTION_EXECUTE_HANDLER
182 : EXCEPTION_CONTINUE_SEARCH) { /* file mapping SEH exception occurred */
183 zdError(ZD_E_DB_MAP_EXCEPTION, (int)GetLastError());
193 return ZDDecodeVariableLengthUnsigned(library, &i2, result);
196 static int64_t ZDDecodeUnsignedToSigned(uint64_t value)
198 return (value & 1) ? -static_cast<int64_t>(value / 2) : static_cast<int64_t>(value / 2);
201 static unsigned int ZDDecodeVariableLengthSigned(const ZoneDetect *library, uint32_t *index, int32_t *result)
204 const unsigned int retVal = ZDDecodeVariableLengthUnsigned(library, index, &value);
205 *result = static_cast<int32_t>(ZDDecodeUnsignedToSigned(value));
209 static char *ZDParseString(const ZoneDetect *library, uint32_t *index)
212 if(!ZDDecodeVariableLengthUnsigned(library, index, &strLength)) {
216 uint32_t strOffset = *index;
217 unsigned int remoteStr = 0;
218 if(strLength >= 256) {
219 strOffset = library->metadataOffset + static_cast<uint32_t>(strLength) - 256;
222 if(!ZDDecodeVariableLengthUnsigned(library, &strOffset, &strLength)) {
226 if(strLength > 256) {
231 auto str = static_cast<char *>(malloc(static_cast<size_t>(strLength + 1)));
234 #if defined(_MSC_VER)
238 for(i = 0; i < strLength; i++) {
239 str[i] = static_cast<char>(library->mapping[strOffset + i] ^ UINT8_C(0x80));
241 #if defined(_MSC_VER)
242 } __except(GetExceptionCode() == EXCEPTION_IN_PAGE_ERROR
243 ? EXCEPTION_EXECUTE_HANDLER
244 : EXCEPTION_CONTINUE_SEARCH) { /* file mapping SEH exception occurred */
245 zdError(ZD_E_DB_MAP_EXCEPTION, (int)GetLastError());
253 *index += static_cast<uint32_t>(strLength);
259 static int ZDParseHeader(ZoneDetect *library)
261 if(library->length < 7) {
265 #if defined(_MSC_VER)
268 if(memcmp(library->mapping, "PLB", 3) != 0) {
272 library->tableType = library->mapping[3];
273 library->version = library->mapping[4];
274 library->precision = library->mapping[5];
275 library->numFields = library->mapping[6];
276 #if defined(_MSC_VER)
277 } __except(GetExceptionCode() == EXCEPTION_IN_PAGE_ERROR
278 ? EXCEPTION_EXECUTE_HANDLER
279 : EXCEPTION_CONTINUE_SEARCH) { /* file mapping SEH exception occurred */
280 zdError(ZD_E_DB_MAP_EXCEPTION, (int)GetLastError());
285 if(library->version >= 2) {
289 uint32_t index = UINT32_C(7);
291 library->fieldNames = static_cast<char **>(malloc(library->numFields * sizeof *library->fieldNames));
292 if (!library->fieldNames) {
297 for(i = 0; i < library->numFields; i++) {
298 library->fieldNames[i] = ZDParseString(library, &index);
301 library->notice = ZDParseString(library, &index);
302 if(!library->notice) {
307 /* Read section sizes */
308 /* By memset: library->bboxOffset = 0 */
310 if(!ZDDecodeVariableLengthUnsigned(library, &index, &tmp)) return -1;
311 library->metadataOffset = static_cast<uint32_t>(tmp) + library->bboxOffset;
313 if(!ZDDecodeVariableLengthUnsigned(library, &index, &tmp))return -1;
314 library->dataOffset = static_cast<uint32_t>(tmp) + library->metadataOffset;
316 if(!ZDDecodeVariableLengthUnsigned(library, &index, &tmp)) return -1;
318 /* Add header size to everything */
319 library->bboxOffset += index;
320 library->metadataOffset += index;
321 library->dataOffset += index;
323 /* Verify file length */
324 if(tmp + library->dataOffset != static_cast<uint32_t>(library->length)) {
331 static int ZDPointInBox(int32_t xl, int32_t x, int32_t xr, int32_t yl, int32_t y, int32_t yr)
333 if((xl <= x && x <= xr) || (xr <= x && x <= xl)) {
334 if((yl <= y && y <= yr) || (yr <= y && y <= yl)) {
342 static uint32_t ZDUnshuffle(uint64_t w)
344 w &= 0x5555555555555555LLU;
345 w = (w | (w >> 1)) & 0x3333333333333333LLU;
346 w = (w | (w >> 2)) & 0x0F0F0F0F0F0F0F0FLLU;
347 w = (w | (w >> 4)) & 0x00FF00FF00FF00FFLLU;
348 w = (w | (w >> 8)) & 0x0000FFFF0000FFFFLLU;
349 w = (w | (w >> 16)) & 0x00000000FFFFFFFFLLU;
350 return static_cast<uint32_t>(w);
353 static void ZDDecodePoint(uint64_t point, int32_t* lat, int32_t* lon)
355 *lat = static_cast<int32_t>(ZDDecodeUnsignedToSigned(ZDUnshuffle(point)));
356 *lon = static_cast<int32_t>(ZDDecodeUnsignedToSigned(ZDUnshuffle(point >> 1)));
360 const ZoneDetect *library;
361 uint32_t polygonIndex;
363 uint64_t numVertices;
366 uint32_t referenceStart, referenceEnd;
367 int32_t referenceDirection;
369 int32_t pointLat, pointLon;
370 int32_t firstLat, firstLon;
373 static void ZDReaderInit(struct Reader *reader, const ZoneDetect *library, uint32_t polygonIndex)
375 memset(reader, 0, sizeof(*reader));
377 reader->library = library;
378 reader->polygonIndex = polygonIndex;
383 static int ZDReaderGetPoint(struct Reader *reader, int32_t *pointLat, int32_t *pointLon)
389 if(reader->done > 1) {
393 if(reader->first && reader->library->version == 0) {
394 if(!ZDDecodeVariableLengthUnsigned(reader->library, &reader->polygonIndex, &reader->numVertices)) return -1;
395 if(!reader->numVertices) return -1;
398 uint8_t referenceDone = 0;
400 if(reader->library->version == 1) {
403 if(!reader->referenceDirection) {
404 if(!ZDDecodeVariableLengthUnsigned(reader->library, &reader->polygonIndex, &point)) return -1;
406 if(reader->referenceDirection > 0) {
407 /* Read reference forward */
408 if(!ZDDecodeVariableLengthUnsigned(reader->library, &reader->referenceStart, &point)) return -1;
409 if(reader->referenceStart >= reader->referenceEnd) {
412 } else if(reader->referenceDirection < 0) {
413 /* Read reference backwards */
414 if(!ZDDecodeVariableLengthUnsignedReverse(reader->library, &reader->referenceStart, &point)) return -1;
415 if(reader->referenceStart <= reader->referenceEnd) {
422 /* This is a special marker, it is not allowed in reference mode */
423 if(reader->referenceDirection) {
428 if(!ZDDecodeVariableLengthUnsigned(reader->library, &reader->polygonIndex, &value)) return -1;
432 } else if(value == 1) {
435 if(!ZDDecodeVariableLengthUnsigned(reader->library, &reader->polygonIndex, reinterpret_cast<uint64_t*>(&start))) return -1;
436 if(!ZDDecodeVariableLengthSigned(reader->library, &reader->polygonIndex, &diff)) return -1;
438 reader->referenceStart = reader->library->dataOffset+static_cast<uint32_t>(start);
439 reader->referenceEnd = reader->library->dataOffset+static_cast<uint32_t>(start + diff);
440 reader->referenceDirection = diff;
442 reader->referenceStart--;
443 reader->referenceEnd--;
448 ZDDecodePoint(point, &diffLat, &diffLon);
449 if(reader->referenceDirection < 0) {
456 if(reader->library->version == 0) {
457 if(!ZDDecodeVariableLengthSigned(reader->library, &reader->polygonIndex, &diffLat)) return -1;
458 if(!ZDDecodeVariableLengthSigned(reader->library, &reader->polygonIndex, &diffLon)) return -1;
462 reader->pointLat += diffLat;
463 reader->pointLon += diffLon;
465 reader->firstLat = reader->pointLat;
466 reader->firstLon = reader->pointLon;
469 /* Close the polygon (the closing point is not encoded) */
470 reader->pointLat = reader->firstLat;
471 reader->pointLon = reader->firstLon;
477 if(reader->library->version == 0) {
478 reader->numVertices--;
479 if(!reader->numVertices) {
482 if(!diffLat && !diffLon) {
488 reader->referenceDirection = 0;
495 *pointLat = reader->pointLat;
499 *pointLon = reader->pointLon;
505 static int ZDFindPolygon(const ZoneDetect *library, uint32_t wantedId, uint32_t* metadataIndexPtr, uint32_t* polygonIndexPtr)
507 uint32_t polygonId = 0;
508 uint32_t bboxIndex = library->bboxOffset;
510 uint32_t metadataIndex = 0;
511 uint32_t polygonIndex = 0;
513 while(bboxIndex < library->metadataOffset) {
514 uint64_t polygonIndexDelta;
515 int32_t metadataIndexDelta;
517 if(!ZDDecodeVariableLengthSigned(library, &bboxIndex, &tmp)) break;
518 if(!ZDDecodeVariableLengthSigned(library, &bboxIndex, &tmp)) break;
519 if(!ZDDecodeVariableLengthSigned(library, &bboxIndex, &tmp)) break;
520 if(!ZDDecodeVariableLengthSigned(library, &bboxIndex, &tmp)) break;
521 if(!ZDDecodeVariableLengthSigned(library, &bboxIndex, &metadataIndexDelta)) break;
522 if(!ZDDecodeVariableLengthUnsigned(library, &bboxIndex, &polygonIndexDelta)) break;
524 metadataIndex += static_cast<uint32_t>(metadataIndexDelta);
525 polygonIndex += static_cast<uint32_t>(polygonIndexDelta);
527 if(polygonId == wantedId) {
528 if(metadataIndexPtr) {
529 metadataIndex += library->metadataOffset;
530 *metadataIndexPtr = metadataIndex;
532 if(polygonIndexPtr) {
533 polygonIndex += library->dataOffset;
534 *polygonIndexPtr = polygonIndex;
545 static std::vector<int32_t> ZDPolygonToListInternal(const ZoneDetect *library, uint32_t polygonIndex)
547 struct Reader reader;
548 ZDReaderInit(&reader, library, polygonIndex);
550 constexpr size_t listLength = 2 * 100;
551 std::vector<int32_t> list;
552 list.reserve(listLength);
557 int result = ZDReaderGetPoint(&reader, &pointLat, &pointLon);
565 list.push_back(pointLat);
566 list.push_back(pointLon);
568 if(list.size() >= 1048576) {
576 float* ZDPolygonToList(const ZoneDetect *library, uint32_t polygonId, size_t* lengthPtr)
578 uint32_t polygonIndex;
579 float* flData = nullptr;
581 if (!ZDFindPolygon(library, polygonId, nullptr, &polygonIndex))
584 const auto data = ZDPolygonToListInternal(library, polygonIndex);
588 size_t length = data.size();
590 flData = static_cast<float *>(malloc(sizeof(float) * length));
595 for(size_t i = 0; i<length; i+= 2) {
596 int32_t lat = data[i];
597 int32_t lon = data[i+1];
599 flData[i] = ZDFixedPointToFloat(lat, 90, library->precision);
600 flData[i+1] = ZDFixedPointToFloat(lon, 180, library->precision);
610 static ZDLookupResult ZDPointInPolygon(const ZoneDetect *library, uint32_t polygonIndex, int32_t latFixedPoint, int32_t lonFixedPoint, uint64_t *distanceSqrMin)
616 int prevQuadrant = 0;
621 struct Reader reader;
622 ZDReaderInit(&reader, library, polygonIndex);
625 int result = ZDReaderGetPoint(&reader, &pointLat, &pointLon);
627 return ZD_LOOKUP_PARSE_ERROR;
632 /* Check if point is ON the border */
633 if(pointLat == latFixedPoint && pointLon == lonFixedPoint) {
634 if(distanceSqrMin) *distanceSqrMin = 0;
635 return ZD_LOOKUP_ON_BORDER_VERTEX;
640 if(pointLat >= latFixedPoint) {
641 if(pointLon >= lonFixedPoint) {
647 if(pointLon >= lonFixedPoint) {
655 int windingNeedCompare = 0;
656 int lineIsStraight = 0;
660 /* Calculate winding number */
661 if(quadrant == prevQuadrant) {
663 } else if(quadrant == (prevQuadrant + 1) % 4) {
665 } else if((quadrant + 1) % 4 == prevQuadrant) {
668 windingNeedCompare = 1;
671 /* Avoid horizontal and vertical lines */
672 if((pointLon == prevLon || pointLat == prevLat)) {
676 /* Calculate the parameters of y=ax+b if needed */
677 if(!lineIsStraight && (distanceSqrMin || windingNeedCompare)) {
678 a = (static_cast<float>(pointLat) - static_cast<float>(prevLat)) / (static_cast<float>(pointLon) - static_cast<float>(prevLon));
679 b = static_cast<float>(pointLat) - a * static_cast<float>(pointLon);
682 int onStraight = ZDPointInBox(pointLat, latFixedPoint, prevLat, pointLon, lonFixedPoint, prevLon);
683 if(lineIsStraight && (onStraight || windingNeedCompare)) {
684 if(distanceSqrMin) *distanceSqrMin = 0;
685 return ZD_LOOKUP_ON_BORDER_SEGMENT;
688 /* Jumped two quadrants. */
689 if(windingNeedCompare) {
690 /* Check if the target is on the border */
691 const auto intersectLon = static_cast<int32_t>((static_cast<float>(latFixedPoint) - b) / a);
692 if(intersectLon >= lonFixedPoint-1 && intersectLon <= lonFixedPoint+1) {
693 if(distanceSqrMin) *distanceSqrMin = 0;
694 return ZD_LOOKUP_ON_BORDER_SEGMENT;
697 /* Ok, it's not. In which direction did we go round the target? */
698 const int sign = (intersectLon < lonFixedPoint) ? 2 : -2;
699 if(quadrant == 2 || quadrant == 3) {
706 /* Calculate closest point on line (if needed) */
710 if(!lineIsStraight) {
711 closestLon = (static_cast<float>(lonFixedPoint) + a * static_cast<float>(latFixedPoint) - a * b) / (a * a + 1);
712 closestLat = (a * (static_cast<float>(lonFixedPoint) + a * static_cast<float>(latFixedPoint)) + b) / (a * a + 1);
714 if(pointLon == prevLon) {
715 closestLon = static_cast<float>(pointLon);
716 closestLat = static_cast<float>(latFixedPoint);
718 closestLon = static_cast<float>(lonFixedPoint);
719 closestLat = static_cast<float>(pointLat);
723 const int closestInBox = ZDPointInBox(pointLon, static_cast<int32_t>(closestLon), prevLon, pointLat, static_cast<int32_t>(closestLat), prevLat);
728 /* Calculate squared distance to segment. */
729 diffLat = static_cast<int64_t>(closestLat - static_cast<float>(latFixedPoint));
730 diffLon = static_cast<int64_t>(closestLon - static_cast<float>(lonFixedPoint));
733 * Calculate squared distance to vertices
734 * It is enough to check the current point since the polygon is closed.
736 diffLat = static_cast<int64_t>(pointLat - latFixedPoint);
737 diffLon = static_cast<int64_t>(pointLon - lonFixedPoint);
740 /* Note: lon has half scale */
741 uint64_t distanceSqr = static_cast<uint64_t>(diffLat * diffLat) + static_cast<uint64_t>(diffLon * diffLon) * 4;
742 if(distanceSqr < *distanceSqrMin) *distanceSqrMin = distanceSqr;
746 prevQuadrant = quadrant;
753 return ZD_LOOKUP_IN_ZONE;
755 return ZD_LOOKUP_IN_EXCLUDED_ZONE;
757 return ZD_LOOKUP_NOT_IN_ZONE;
760 /* Should not happen */
761 if(distanceSqrMin) *distanceSqrMin = 0;
762 return ZD_LOOKUP_ON_BORDER_SEGMENT;
765 void ZDCloseDatabase(ZoneDetect *library)
768 if(library->fieldNames) {
770 for(i = 0; i < static_cast<size_t>(library->numFields); i++) {
771 if(library->fieldNames[i]) {
772 free(library->fieldNames[i]);
775 free(library->fieldNames);
777 if(library->notice) {
778 free(library->notice);
781 if(library->closeType == 0) {
782 #if defined(_MSC_VER) || defined(__MINGW32__)
783 if(library->mapping && !UnmapViewOfFile(library->mapping)) zdError(ZD_E_DB_MUNMAP_MSVIEW, (int)GetLastError());
784 if(library->fdMap && !CloseHandle(library->fdMap)) zdError(ZD_E_DB_MUNMAP, (int)GetLastError());
785 if(library->fd && !CloseHandle(library->fd)) zdError(ZD_E_DB_CLOSE, (int)GetLastError());
786 #elif defined(__APPLE__) || defined(__linux__) || defined(__unix__) || defined(_POSIX_VERSION)
787 if(library->mapping && munmap(library->mapping, static_cast<size_t>(library->length))) zdError(ZD_E_DB_MUNMAP, 0);
788 if(library->fd >= 0 && close(library->fd)) zdError(ZD_E_DB_CLOSE, 0);
796 struct ZoneDetectDeleter {
797 void operator()(ZoneDetect *library)
799 ZDCloseDatabase(library);
803 using ZoneDetectPtr = std::unique_ptr<ZoneDetect, ZoneDetectDeleter>;
805 ZoneDetect *ZDOpenDatabaseFromMemory(void* buffer, size_t length)
807 ZoneDetectPtr library{static_cast<ZoneDetect *>(calloc(1, sizeof(ZoneDetect)))};
810 library->closeType = 1;
811 library->length = static_cast<long int>(length);
813 if(library->length <= 0) {
814 #if defined(_MSC_VER) || defined(__MINGW32__) || defined(__APPLE__) || defined(__linux__) || defined(__unix__) || defined(_POSIX_VERSION)
815 zdError(ZD_E_DB_SEEK, errno);
817 zdError(ZD_E_DB_SEEK, 0);
822 library->mapping = static_cast<uint8_t *>(buffer);
824 /* Parse the header */
825 if(ZDParseHeader(library.get())) {
826 zdError(ZD_E_PARSE_HEADER, 0);
831 return library.release();
834 ZoneDetect *ZDOpenDatabase(const char *path)
836 ZoneDetectPtr library{static_cast<ZoneDetect *>(calloc(1, sizeof(ZoneDetect)))};
839 #if defined(_MSC_VER) || defined(__MINGW32__)
840 library->fd = CreateFile(path, GENERIC_READ, 0, NULL, OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL, NULL);
841 if (library->fd == INVALID_HANDLE_VALUE) {
842 zdError(ZD_E_DB_OPEN, (int)GetLastError());
846 const DWORD fsize = GetFileSize(library->fd, NULL);
847 if (fsize == INVALID_FILE_SIZE) {
848 zdError(ZD_E_DB_SEEK, (int)GetLastError());
851 library->length = (int32_t)fsize;
853 library->fdMap = CreateFileMappingA(library->fd, NULL, PAGE_READONLY, 0, 0, NULL);
854 if (!library->fdMap) {
855 zdError(ZD_E_DB_MMAP, (int)GetLastError());
859 library->mapping = MapViewOfFile(library->fdMap, FILE_MAP_READ, 0, 0, 0);
860 if (!library->mapping) {
861 zdError(ZD_E_DB_MMAP_MSVIEW, (int)GetLastError());
864 #elif defined(__APPLE__) || defined(__linux__) || defined(__unix__) || defined(_POSIX_VERSION)
865 library->fd = open(path, O_RDONLY | O_CLOEXEC);
866 if(library->fd < 0) {
867 zdError(ZD_E_DB_OPEN, errno);
871 library->length = lseek(library->fd, 0, SEEK_END);
872 if(library->length <= 0 || library->length > 50331648) {
873 zdError(ZD_E_DB_SEEK, errno);
876 lseek(library->fd, 0, SEEK_SET);
878 library->mapping = static_cast<uint8_t *>(mmap(nullptr, static_cast<size_t>(library->length), PROT_READ, MAP_PRIVATE | MAP_FILE, library->fd, 0));
879 if(library->mapping == MAP_FAILED) {
880 zdError(ZD_E_DB_MMAP, errno);
885 /* Parse the header */
886 if(ZDParseHeader(library.get())) {
887 zdError(ZD_E_PARSE_HEADER, 0);
892 return library.release();
895 ZoneDetectResult *ZDLookup(const ZoneDetect *library, float lat, float lon, float *safezone)
897 const int32_t latFixedPoint = ZDFloatToFixedPoint(lat, 90, library->precision);
898 const int32_t lonFixedPoint = ZDFloatToFixedPoint(lon, 180, library->precision);
899 size_t numResults = 0;
900 auto distanceSqrMin = static_cast<uint64_t>(-1);
902 /* Iterate over all polygons */
903 uint32_t bboxIndex = library->bboxOffset;
904 uint32_t metadataIndex = 0;
905 uint32_t polygonIndex = 0;
907 auto results = static_cast<ZoneDetectResult *>(malloc(sizeof(ZoneDetectResult)));
912 uint32_t polygonId = 0;
914 while(bboxIndex < library->metadataOffset) {
919 int32_t metadataIndexDelta;
920 uint64_t polygonIndexDelta;
921 if(!ZDDecodeVariableLengthSigned(library, &bboxIndex, &minLat)) break;
922 if(!ZDDecodeVariableLengthSigned(library, &bboxIndex, &minLon)) break;
923 if(!ZDDecodeVariableLengthSigned(library, &bboxIndex, &maxLat)) break;
924 if(!ZDDecodeVariableLengthSigned(library, &bboxIndex, &maxLon)) break;
925 if(!ZDDecodeVariableLengthSigned(library, &bboxIndex, &metadataIndexDelta)) break;
926 if(!ZDDecodeVariableLengthUnsigned(library, &bboxIndex, &polygonIndexDelta)) break;
928 metadataIndex += static_cast<uint32_t>(metadataIndexDelta);
929 polygonIndex += static_cast<uint32_t>(polygonIndexDelta);
931 if(latFixedPoint >= minLat) {
932 if(latFixedPoint <= maxLat &&
933 lonFixedPoint >= minLon &&
934 lonFixedPoint <= maxLon) {
936 const ZDLookupResult lookupResult = ZDPointInPolygon(library, library->dataOffset + polygonIndex, latFixedPoint, lonFixedPoint, (safezone) ? &distanceSqrMin : nullptr);
937 if(lookupResult == ZD_LOOKUP_PARSE_ERROR) {
939 } if(lookupResult != ZD_LOOKUP_NOT_IN_ZONE) {
940 auto newResults = static_cast<ZoneDetectResult *>(realloc(results, sizeof(ZoneDetectResult) * (numResults + 2)));
943 results = newResults;
944 results[numResults].polygonId = polygonId;
945 results[numResults].metaId = metadataIndex;
946 results[numResults].numFields = library->numFields;
947 results[numResults].fieldNames = library->fieldNames;
948 results[numResults].lookupResult = lookupResult;
957 /* The data is sorted along minLat */
964 /* Clean up results */
966 for(i = 0; i < numResults; i++) {
968 ZDLookupResult overrideResult = ZD_LOOKUP_IGNORE;
970 for(j = i; j < numResults; j++) {
971 if(results[i].metaId == results[j].metaId) {
972 ZDLookupResult tmpResult = results[j].lookupResult;
973 results[j].lookupResult = ZD_LOOKUP_IGNORE;
975 /* This is the same result. Is it an exclusion zone? */
976 if(tmpResult == ZD_LOOKUP_IN_ZONE) {
978 } else if(tmpResult == ZD_LOOKUP_IN_EXCLUDED_ZONE) {
981 /* If on the bodrder then the final result is on the border */
982 overrideResult = tmpResult;
988 if(overrideResult != ZD_LOOKUP_IGNORE) {
989 results[i].lookupResult = overrideResult;
992 results[i].lookupResult = ZD_LOOKUP_IN_ZONE;
997 /* Remove zones to ignore */
998 size_t newNumResults = 0;
999 for(i = 0; i < numResults; i++) {
1000 if(results[i].lookupResult != ZD_LOOKUP_IGNORE) {
1001 results[newNumResults] = results[i];
1005 numResults = newNumResults;
1007 /* Lookup metadata */
1008 for(i = 0; i < numResults; i++) {
1009 uint32_t tmpIndex = library->metadataOffset + results[i].metaId;
1010 results[i].data = static_cast<char **>(malloc(library->numFields * sizeof *results[i].data));
1011 if(results[i].data) {
1013 for(j = 0; j < library->numFields; j++) {
1014 results[i].data[j] = ZDParseString(library, &tmpIndex);
1015 if (!results[i].data[j]) {
1016 /* free all allocated memory */
1018 for(m = 0; m < j; m++) {
1019 if(results[i].data[m]) {
1020 free(results[i].data[m]);
1024 for(k = 0; k < i; k++) {
1026 for(l = 0; l < static_cast<size_t>(results[k].numFields); l++) {
1027 if(results[k].data[l]) {
1028 free(results[k].data[l]);
1031 if (results[k].data) {
1032 free(results[k].data);
1041 /* free all allocated memory */
1043 for(k = 0; k < i; k++) {
1045 for(l = 0; l < static_cast<size_t>(results[k].numFields); l++) {
1046 if(results[k].data[l]) {
1047 free(results[k].data[l]);
1050 if (results[k].data) {
1051 free(results[k].data);
1059 /* Write end marker */
1060 results[numResults].lookupResult = ZD_LOOKUP_END;
1061 results[numResults].numFields = 0;
1062 results[numResults].fieldNames = nullptr;
1063 results[numResults].data = nullptr;
1066 *safezone = sqrtf(static_cast<float>(distanceSqrMin)) * 90 / static_cast<float>(1 << (library->precision - 1));
1072 void ZDFreeResults(ZoneDetectResult *results)
1074 unsigned int index = 0;
1080 while(results[index].lookupResult != ZD_LOOKUP_END) {
1081 if(results[index].data) {
1083 for(i = 0; i < static_cast<size_t>(results[index].numFields); i++) {
1084 if(results[index].data[i]) {
1085 free(results[index].data[i]);
1088 free(results[index].data);
1095 const char *ZDGetNotice(const ZoneDetect *library)
1097 return library->notice;
1100 uint8_t ZDGetTableType(const ZoneDetect *library)
1102 return library->tableType;
1105 const char *ZDLookupResultToString(ZDLookupResult result)
1108 case ZD_LOOKUP_IGNORE:
1112 case ZD_LOOKUP_PARSE_ERROR:
1113 return "Parsing error";
1114 case ZD_LOOKUP_NOT_IN_ZONE:
1115 return "Not in zone";
1116 case ZD_LOOKUP_IN_ZONE:
1118 case ZD_LOOKUP_IN_EXCLUDED_ZONE:
1119 return "In excluded zone";
1120 case ZD_LOOKUP_ON_BORDER_VERTEX:
1121 return "Target point is border vertex";
1122 case ZD_LOOKUP_ON_BORDER_SEGMENT:
1123 return "Target point is on border";
1129 #define ZD_E_COULD_NOT(msg) "could not " msg
1131 const char *ZDGetErrorString(int errZD)
1133 switch (static_cast<enum ZDInternalError>(errZD)) {
1139 return ZD_E_COULD_NOT("open database file");
1141 return ZD_E_COULD_NOT("retrieve database file size");
1143 return ZD_E_COULD_NOT("map database file to system memory");
1144 #if defined(_MSC_VER) || defined(__MINGW32__)
1145 case ZD_E_DB_MMAP_MSVIEW :
1146 return ZD_E_COULD_NOT("open database file view");
1147 case ZD_E_DB_MAP_EXCEPTION:
1148 return "I/O exception occurred while accessing database file view";
1149 case ZD_E_DB_MUNMAP_MSVIEW:
1150 return ZD_E_COULD_NOT("close database file view");
1152 case ZD_E_DB_MUNMAP :
1153 return ZD_E_COULD_NOT("unmap database");
1154 case ZD_E_DB_CLOSE :
1155 return ZD_E_COULD_NOT("close database file");
1156 case ZD_E_PARSE_HEADER :
1157 return ZD_E_COULD_NOT("parse database header");
1161 #undef ZD_E_COULD_NOT
1163 int ZDSetErrorHandler(void (*handler)(int, int))
1165 zdErrorHandler = handler;
1169 char* ZDHelperSimpleLookupString(const ZoneDetect* library, float lat, float lon)
1171 std::unique_ptr<ZoneDetectResult, decltype(&ZDFreeResults)> result{ZDLookup(library, lat, lon, nullptr), ZDFreeResults};
1176 char* output = nullptr;
1178 char* strings[2] = {nullptr};
1180 if(result->lookupResult == ZD_LOOKUP_END) {
1184 for(int i = 0; i < result->numFields; i++) {
1185 if(result->fieldNames[i] && result->data[i]) {
1186 if(library->tableType == 'T') {
1187 if(!strcmp(result->fieldNames[i], "TimezoneIdPrefix")) {
1188 strings[0] = result->data[i];
1190 if(!strcmp(result->fieldNames[i], "TimezoneId")) {
1191 strings[1] = result->data[i];
1194 if(library->tableType == 'C') {
1195 if(!strcmp(result->fieldNames[i], "Name")) {
1196 strings[0] = result->data[i];
1202 for(const auto& string : strings) {
1204 size_t partLength = strlen(string);
1205 if(partLength > 512) {
1208 length += partLength;
1218 output = static_cast<char*>(malloc(length));
1221 for(const auto& string : strings) {
1223 strcat(output + strlen(output), string);