/* misc.c -- Miscellaneous functions Copyright © 2021-2023 Samuel Lidén Borell Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions: The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software. THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ #include "internal.h" #include "hash.h" #include #include #define INTERR_MISC(errnum) MAKE_INTERR(errnum, INTERRBASE_MISC) #define X 0xFF static const unsigned char unb64[128-32] = { /* 20-2F: special characters */ X, X, X, X, X, X, X, X, X, X, X, 62, X, X, X, 63, /* 30-3F: 01234... */ 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, X, X, X, X, X, X, /* 40-4F: @ABCD... */ X, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, /* 50-5F: PQRST... */ 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, X, X, X, X, X, /* 60-6F: `abcd... */ X, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, /* 70-7F: pqrst... */ 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, X, X, X, X, X }; #undef X #define GETCHAR \ c = *(in++); \ if (c < 32 || c > 127) return 0; \ c = unb64[c-32]; \ if (c > 63) return 0; /** * Decodes a string from standard Base64 to binary. No padding is allowed at * the end. * * \param in Base64 encoded input string * \param inlen Length of input in bytes * \param out Binary output * \param outlen Length of output * \return 1 if successful, or 0 if the input not not correctly encoded * or if the output buffer is too small. */ int unbase64(const char *in, size_t inlen, unsigned char *out, size_t outlen) { uint32 v; unsigned char c; for (;;) { if (inlen < 4) goto end_chunk; if (outlen < 3) return 0; GETCHAR v = (uint32)c << 18; GETCHAR v |= (uint32)c << 12; GETCHAR v |= c << 6; GETCHAR v |= c; *(out++) = (v >> 16) & 0xFF; *(out++) = (v >> 8) & 0xFF; *(out++) = v & 0xFF; inlen -= 4; outlen -= 3; } end_chunk: if (!inlen) return 1; /* We can have 2 or 3 trailing characters */ if (inlen == 1) return 0; GETCHAR v = (uint32)c << 18; GETCHAR v |= (uint32)c << 12; if (inlen >= 3) { GETCHAR v |= c << 6; if (outlen < 2) return 0; } else if (outlen < 1) return 0; *(out++) = (v >> 16) & 0xFF; /* Check that there are no extranous bits */ v &= ~0xFF0000; if (inlen >= 3) { *(out++) = (v >> 8) & 0xFF; v &= ~0xFF00; } return !v; } /* These correspends to the bit index of types */ #define LATIN 0 #define CYRILLIC 1 #define GREEK 2 #define SPECIALS 3 #define OTHER 4 #define RTL 8 /** NONE = left-to-right script with no risk of confusion */ #define NONE 15 struct CharRange { /** Upper bound of this character range (lower bound is inferred) */ uint32 upper_bound; /** Script of this range */ unsigned script : 4; /** A few characters may belong to another script/group */ unsigned except_script : 4; /** First index in exception table */ unsigned except_start : 12; /** Last index in exception table. 0 = no exceptions */ unsigned except_end : 12; }; /** * Table of Unicode scripts. CJK scripts count as NONE because their * characters look so different that there is no risk of confusion * with other ASCII characters (or other scripts in general). */ static const struct CharRange unicode_scripts[] = { { 0x24F, LATIN, OTHER, 0x7C, 0x90 }, /* Latin ext */ { 0x36F, OTHER, 0, 0, 0 }, /* IPA, modifiers */ { 0x3E1, GREEK, 0, 0, 0 }, { 0x3EF, OTHER, 0, 0, 0 }, /* Coptic */ { 0x3FF, GREEK, 0, 0, 0 }, { 0x52F, CYRILLIC, 0, 0, 0 }, { 0x58F, OTHER, 0, 0, 0 }, /* Armenian */ { 0x86F, RTL, 0, 0, 0 }, /* Hebrew -5FF, Arabic -6FF, Syriac -74F, Misc other uncommon RTL languages */ { 0x89F, OTHER, 0, 0, 0 }, /* Unassigned */ { 0x8FF, RTL, 0, 0, 0 }, /* Arabic */ { 0x10FF, OTHER, 0, 0, 0 }, { 0x11FF, NONE, 0, 0, 0 }, /* Hangul */ { 0x1C7F, OTHER, 0, 0, 0 }, { 0x1C8F, CYRILLIC, 0, 0, 0 }, { 0x1DFF, OTHER, 0, 0, 0 }, { 0x1EFF, LATIN, 0, 0, 0 }, { 0x1FFF, GREEK, 0, 0, 0 }, { 0x201F, SPECIALS, RTL, 0x66, 0x67 }, /* Separators and control chars */ { 0x2023, NONE, 0, 0, 0 }, /* Bullet points */ { 0x2026, SPECIALS, 0, 0, 0 }, /* Ellipsis */ { 0x2029, NONE, SPECIALS, 0x91, 0x92 }, /* Line sep. sign, paragraph sep. */ { 0x202F, RTL, 0, 0, 0 }, { 0x20CF, NONE, SPECIALS, 0x68, 0x7B }, { 0x218F, SPECIALS, 0, 0, 0 }, /* Combining, letterlike, numerals */ { 0x23FF, NONE, SPECIALS, 0x0, 0x21 }, { 0x24FF, SPECIALS, 0, 0, 0 }, { 0x27FF, NONE, SPECIALS, 0x22, 0x35 }, { 0x28FF, OTHER, 0, 0, 0 }, { 0x2BFF, NONE, SPECIALS, 0x36, 0x46 }, { 0x2C5F, OTHER, 0, 0, 0 }, { 0x2C7F, LATIN, 0, 0, 0 }, { 0x2DDF, OTHER, 0, 0, 0 }, { 0x2DFF, CYRILLIC, 0, 0, 0 }, { 0x30FF, NONE, SPECIALS, 0x47, 0x54 }, { 0x312F, OTHER, 0, 0, 0 }, { 0x3163, NONE, OTHER, 0x55, 0x55 }, { 0x318F, NONE, SPECIALS, 0x56, 0x56 }, { 0x31BF, OTHER, 0, 0, 0 }, { 0x32CB, NONE, OTHER, 0x57, 0x58 }, { 0x32CF, OTHER, 0, 0, 0 }, /* Hg,erg,eV,LTD,... */ { 0x3370, NONE, 0, 0, 0 }, { 0x337A, OTHER, 0, 0, 0 }, /* hPa,da,... */ { 0x337F, NONE, 0, 0, 0 }, { 0x33DF, OTHER, 0, 0, 0 }, /* pA,nA,... */ { 0x9FFF, NONE, OTHER, 0x59, 0x5A }, { 0xA63F, OTHER, 0, 0, 0 }, { 0xA69F, CYRILLIC, 0, 0, 0 }, { 0xA71F, OTHER, 0, 0, 0 }, { 0xA72F, LATIN, 0, 0, 0 }, { 0xA736, OTHER, 0, 0, 0 }, /* F,s,AA,...,ao,AJ */ { 0xA7FF, LATIN, OTHER, 0x5B, 0x5E }, { 0xA95F, OTHER, 0, 0, 0 }, { 0xA97F, NONE, 0, 0, 0 }, { 0xAB2F, OTHER, 0, 0, 0 }, { 0xAB6F, LATIN, OTHER, 0x5F, 0x62 }, { 0xABFF, OTHER, 0, 0, 0 }, { 0xD7FF, NONE, 0, 0, 0 }, /* Hangul */ /* D800-DFFF = high/low surrogate characters. Those are never allowed. */ { 0xF8FF, SPECIALS, 0, 0, 0 }, /* Private Use */ { 0xFAFF, NONE, 0, 0, 0 }, /* CJK */ { 0xFB1C, OTHER, 0, 0, 0 }, /* Ligatures, etc. */ { 0xFDFF, RTL, 0, 0, 0 }, /* Hebrw and Arabic dito */ { 0xFE1F, SPECIALS, 0, 0, 0 }, /* Variant selectors, vertical forms */ { 0xFE2F, OTHER, 0, 0, 0 }, { 0xFE4F, NONE, SPECIALS, 0x63, 0x64 }, { 0xFE6F, SPECIALS, 0, 0, 0 }, { 0xFEFC, RTL, 0, 0, 0 }, /* Arabic */ /* FEFE/FEFD = unassigned, FEFF = NBSP */ { 0xFFFF, SPECIALS, 0, 0, 0 }, { 0x1018F, OTHER, 0, 0, 0 }, { 0x101CF, SPECIALS, 0, 0, 0 }, /* Note: gaps at 10200-1027F, 103E0-103FF, 10570-105FF, 1077F-107FF, 108AF-108DF, 1093F-1097F, 10A9F-10ABF, 10BAF-10BFF, 10D3F-10E5F, 10EBF-10EFF, 10F6F-10FAF, 1124F-1127F, 1137F-113FF, 114DF-1157F, 116CF-116FF, 1173F-117FF ...and several more. The gaps are mapped to either "Other" or "RTL" depending on their adjacent blocks */ { 0x107FF, OTHER, 0, 0, 0 }, { 0x10D3F, RTL, 0, 0, 0 }, { 0x10E7F, OTHER, 0, 0, 0 }, { 0x10FFF, RTL, 0, 0, 0 }, { 0x1D0FF, OTHER, 0, 0, 0 }, { 0x1D1FF, SPECIALS, 0, 0, 0 }, /* Several combining chars in this block */ { 0x1D3FF, OTHER, 0, 0, 0 }, { 0x1D7FF, SPECIALS, 0, 0, 0 }, /* Math alphanumeric characters */ { 0x1E7FF, OTHER, 0, 0, 0 }, { 0x1E95F, RTL, 0, 0, 0 }, { 0x1EDFF, OTHER, 0, 0, 0 }, { 0x1EEFF, RTL, 0, 0, 0 }, /* Arabic math */ { 0x1F0FF, OTHER, 0, 0, 0 }, /* Playing cards */ { 0x1F2FF, SPECIALS, 0, 0, 0 }, /* Enclosed chars. Flags */ { 0x1F6FF, NONE, SPECIALS, 0x65, 0x65 }, /* Symbols, emojis, etc. */ { 0x1F77F, SPECIALS, 0, 0, 0 }, /* Alchemy. Many are letter-like */ { 0x1F7A0, NONE, 0, 0, 0 }, /* Various symbols */ { 0x1F7BA, SPECIALS, 0, 0, 0 }, /* Lookalikes of +, x, and * */ { 0x1FB6F, NONE, 0, 0, 0 }, /* Various symbols */ { 0x1FB7B, SPECIALS, 0, 0, 0 }, /* Lookalikes of +, x, and * */ { 0x1FBFF, NONE, 0, 0, 0 }, /* Various symbols */ /* Large gap from 1FC00-1FFFF. These are mapped to "Other" */ { 0x1FFFF, OTHER, 0, 0, 0 }, { 0x3134F, NONE, 0, 0, 0 }, /* CJK blocks (with several gaps) */ { 0xDFFFF, OTHER, 0, 0, 0 }, /* Unassigned = other */ { 0x10FFFF, SPECIALS, 0, 0, 0 } /* Tags, Var. select., Private use */ }; #undef LATIN #undef CYRILLIC #undef GREEK #undef SPECIALS #undef OTHER #undef RTL #undef NONE /** * Exceptions for look-alikes and characters belonging to another * script than that of the Unicode block that it belongs to. * * Source: Own work, based on manual check of Unicode blocks * in gucharmap in Debian with (most?) "Noto" fonts installed. * * TODO Compare this against Unicode's list of confusable characters. */ static const uint32 unicode_exceptions[] = { /* 2190-23FF: Arrows/math/tech */ /* 0- */ 0x2201/* C */, 0x2212/* - */, 0x2215/* / */, 0x2216/* \ */, /* 4- */ 0x2217/* * */, 0x2223/* | */, 0x223C/* ~ */, 0x223D/* ~ */, /* 8- */ 0x227A/* < */, 0x227B/* > */, 0x22C1/* V */, 0x22C3/* U */, /* C- */ 0x22CE/* v */, 0x22FF/* E */, 0x2303/* ^ */, 0x2329/* < */, /* 10- */ 0x232A/* > */, 0x2373/* i */, 0x2374/* p */, 0x2375/* w */, /* 14- */ 0x237A/* a */, 0x239C/* | */, 0x239F/* | */, 0x23A2/* | */, /* 18- */ 0x23A5/* | */, 0x23AA/* | */, 0x23AE/* | */, 0x23AF/* _ */, /* 1C- */ 0x23B8/* | */, 0x23B9/* | */, 0x23BB/* - */, 0x23BC/* - */, /* -21 */ 0x23BD/* _ */, 0x23E4/* - */, /* 2500-27FF: Box drawing, block elements, shapes, symbols, math */ /* 22- */ 0x2500/* - */, 0x2502/* | */, 0x2503/* | */, 0x2550/* = */, /* 26- */ 0x2571/* / */, 0x2572/* \ */, 0x258F/* | */, 0x2595/* | */, /* 2A- */ 0x25CB/* o */, 0x25EF/* O */, 0x268A/* _ */, 0x268C/* = */, /* 2E- */ 0x2758/* | */, 0x2759/* | */, 0x27CB/* / */, 0x27CD/* \ */, /* -35 */ 0x27E8/* ( */, 0x27E9/* ) */, 0x27EE/* ( */, 0x27EF/* ) */, /* 2900-2BFF: Arrows B, math */ /* 36- */ 0x292B/* x */, 0x292C/* x */, 0x2960/* 1 */, 0x29F5/* \ */, /* 3A- */ 0x29F8/* / */, 0x29F9/* \ */, 0x29FC/* < */, 0x29FD/* > */, /* 3E- */ 0x29FE/* + */, 0x29FF/* - */, 0x2A2F/* x */, 0x2A75/* == */, /* 42- */ 0x2A76/* === */, 0x2AA5/* >< */, 0x2AFB/* /// */, 0x2AFC/* ||| */, /* -46 */ 0x2AFD/* // */, /* 2E00-30FF: Separators and CJK */ /* 47- */ 0x2E0F/* _ */, 0x2E28/* (( */, 0x2E29/* )) */, 0x3000/* space */, /* 4B- */ 0x3008/* < */, 0x3009/* > */, 0x300A/* << */, 0x300B/* >> */, /* 4F- */ 0x301C/* ~ */, 0x3021/* | */, 0x3033/* / */, 0x3035/* \ */, /* -54 */ 0x3037/* XX */, 0x30A0/* ~ */, /* 3130-31BF: CJK */ /* -56 */ 0x3147/* o */, 0x3164/* space */, /* 31C0-9FFF: CJK */ /* -58 */ 0x31D1/* | */, 0x31D7/* L */, /* -5A */ 0x33FF/* gal */, 0x4E28/* | */, /* A720-A7FF: Latin */ /* -5E */ 0xA756/* Q */, 0xA757/* q */, 0xA7AE/* I */, 0xA7FE/* | */, /* AB30-AB6F: Latin */ /* -62 */ 0xAB35/* f */, 0xAB36/* g */, 0xAB48/* r */, 0xAB64/* a */, /* FE30-FE4F: CJK compatibility */ /* -64 */ 0xFE31/* | */, 0xFE33/* | */, /* 1F300-1F6FF: Symbols, emojis, etc */ /* -65 */ 0x1F5D9/* x */, /* 2000-201F: Separator chars */ /* -67 */ 0x200E/* LRM */, 0x200F/* RLM */, /* 68- */ 0x2032/* ' */, 0x2033/* '' */, 0x2034/* ''' */, 0x2035/* ' */, /* 6C- */ 0x2036/* '' */, 0x2037/* ''' */, 0x2039/* < */, 0x203A/* > */, /* 70- */ 0x203C/* !! */, 0x2043/* - */, 0x2044/* / */, 0x2047/* ?? */, /* 74- */ 0x2048/* ?! */, 0x2049/* !? */, 0x204A/* 7 */, 0x204E/* * */, /* -7B */ 0x2052/* % */, 0x2053/* ~ */, 0x2057/* "" */, 0x205A/* : */, /* 7C- */ 0xA0/* NPSP */, 0xAD/* SHY */, 0x132/* IJ */, 0x133/* ij */, /* 80- */ 0x196/* l */, 0x1B7/* 3 */, 0x1BC/* 5 */, 0x1BD/* 5 */, /* 84- */ 0x1C0/* | */, 0x1C1/* || */, 0x1C3/* ! */, 0x1C7/* LJ */, /* 88- */ 0x1C8/* Lj */, 0x1C9/* lj */, 0x1CA/* NJ */, 0x1CB/* Nj */, /* 8C- */ 0x1CC/* nj */, 0x1F1/* DZ */, 0x1F2/* Dz */, 0x1F3/* dz */, /* -90 */ 0x222/* 8 */, /* -92 */ 0x2028/* visible line sep */, 0x2029/* paragraph separator */ }; /** * Returns any of the SCRIPT_* constants for a given codepoint. * 0 is returned for common characters and for CJK scripts. * Only codepoints > 7F are supported. */ unsigned get_unicode_script(uint32 codepoint) { const struct CharRange *range; unsigned match; assert(codepoint <= 0x10FFFF); /* Find the character range (these are rougly groups of Unicode blocks) */ for (range = &unicode_scripts[0]; codepoint > range->upper_bound; range++) { } /* Check if the character is an exception */ if (range->except_end) { const uint32 *exc_char = &unicode_exceptions[range->except_start]; int numleft = range->except_end - range->except_start + 1; while (numleft--) { if (*(exc_char++) == codepoint) { match = range->except_script; goto found; } } } match = range->script; found: /* The SCRIPTS_* constants are bitmasks */ return (1 << match) & 0x1FF; } /** * Compares two versions. The strings must be valid version strings. * Returns: * 0 if equal, * < 0 if a < b, or * > 0 if a > b */ int versioncmp(const char *a, size_t alen, const char *b, size_t blen) { #define X 0x00 #define TILDE 0x01 #define END 0x02 #define DOT 0x03 #define DIGIT 0x40 #define ALPHA 0x60 #define A(n) (ALPHA+(n)) #define D(n) (DIGIT+(n)) #define MASK 0x60 static const signed char table[] = { /* Lower case letters, digits, dot and tilde are allowed */ /* . / 0 1 2 3 4 5 6 7 8 9 : ; < = > ? */ DOT, X,D(0),D(1),D(2),D(3),D(4),D(5),D(6),D(7),D(8),D(9),X,X,X,X,X,X, /* @ A B C D E F G H I J K L M N O P Q R S T U V W X Y Z [ \ ] ^ _ ` */ X, X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X, /* a - z */ A(0),A(1),A(2),A(3),A(4),A(5),A(6),A(7),A(8),A(9),A(10),A(11),A(12), A(13),A(14),A(15),A(16),A(17),A(18),A(19),A(20),A(21),A(22),A(23), A(24),A(25), /* { | } ~ */ X, X,X,TILDE }; #undef X if (alen == blen && !memcmp(a, b, alen)) return 0; for (;;) { signed char ac; signed char bc; if (alen) { unsigned ai = (unsigned)*(a++) - '.'; assert(ai < sizeof(table)); ac = table[ai]; assert(ac); alen--; } else ac = END; if (blen) { unsigned bi = (unsigned)*(b++) - '.'; assert(bi < sizeof(table)); bc = table[bi]; assert(bc); blen--; } else { assert(alen); bc = END; } if ((ac & MASK) == DIGIT && (bc & MASK) == DIGIT) { /* Numeric component */ const char *start_a = a-1; const char *start_b = b-1; const char *adigit, *bdigit; int diff; int zerosdiff; /* Find end of numbers */ while (alen) { unsigned ai = (unsigned)*a - '.'; assert(ai < sizeof(table)); ac = table[ai]; assert(ac); if ((ac & MASK) != DIGIT) break; a++; alen--; } while (blen) { unsigned bi = (unsigned)*b - '.'; assert(bi < sizeof(table)); bc = table[bi]; assert(bc); if ((bc & MASK) != DIGIT) break; b++; blen--; } /* Skip leading zeros, and handle 0 */ zerosdiff = 0; while (start_a < a && *start_a == '0') { start_a++; zerosdiff++; } while (start_b < b && *start_b == '0') { start_b++; zerosdiff--; } if (start_a == a) { if (start_b != b) return -1; if (zerosdiff) return zerosdiff; continue; } else if (start_b == b) { return 1; } /* Compare digit by digit from end */ adigit = a-1; bdigit = b-1; diff = 0; for (;;) { ac = *adigit; bc = *bdigit; if (ac < bc) diff = -1; else if (ac > bc) diff = 1; if (adigit == start_a) { if (bdigit == start_b) { if (diff) return diff; break; } return -1; } if (bdigit == start_b) { return 1; } adigit--; bdigit--; } /* Components are equal if we got here */ if (zerosdiff) return zerosdiff; if (!alen) { assert(blen); return *b == '~' ? 1 : -1; } if (!blen) { return *a == '~' ? -1 : 1; } } else { /* Non-numeric component */ if (ac != bc) return ac - bc; } } } #undef TILDE #undef END #undef DOT #undef ALPHA #undef DIGIT #undef D #undef A #undef MASK int node_vercmp(const struct TreeNode *a, const char *b, size_t blen) { return versioncmp(node_nameptr(a), a->length, b, blen); } int nodes_vercmp(const struct TreeNode *a, const struct TreeNode *b) { return versioncmp(node_nameptr(a), a->length, node_nameptr(b), b->length); } HashCode hash_str(const char *s, size_t len) { HashCode h = 0; while (len--) { h = HASH(h, *(s++)); } return h; }