icons-hash.c (8826B)
1 /* 2 * simple program which outputs a hash-table of `icons_ext` with low collusion. 3 * the hash function is case-insensitive, it also doesn't hash beyond the 4 * length of the longest extension. 5 */ 6 7 #include <stddef.h> 8 #include <stdint.h> 9 #include <inttypes.h> 10 11 #define GOLDEN_RATIO_32 UINT32_C(2654442313) /* golden ratio for 32bits: (2^32) / 1.61803 */ 12 #define GOLDEN_RATIO_64 UINT64_C(0x9E3793492EEDC3F7) 13 #define ICONS_TABLE_SIZE 8 /* size in bits. 8 = 2^8 = 256 */ 14 15 #ifndef TOUPPER 16 #define TOUPPER(ch) (((ch) >= 'a' && (ch) <= 'z') ? ((ch) - 'a' + 'A') : (ch)) 17 #endif 18 19 /* all of this is just for the static hash-table generation. only the hash 20 * function gets included in `nnn` binary. 21 */ 22 #ifdef ICONS_GENERATE 23 24 #include <stdio.h> 25 #include <string.h> 26 #include <strings.h> 27 #include <stdlib.h> 28 #include <limits.h> 29 #include "icons.h" 30 31 /* like assert, but always sticks around during generation. */ 32 #define ENSURE(X) do { \ 33 if (!(X)) { \ 34 fprintf(stderr, "%s:%d: `%s`\n", __FILE__, __LINE__, #X); \ 35 abort(); \ 36 } \ 37 } while (0) 38 #define ARRLEN(X) (sizeof(X) / sizeof((X)[0])) 39 #define MAX(A, B) ((A) > (B) ? (A) : (B)) 40 #define HGEN_ITERARATION (1ul << 13) 41 #define ICONS_PROBE_MAX_ALLOWED 6 42 #define ICONS_MATCH_MAX (512) 43 44 #if 0 /* for logging some interesting info to stderr */ 45 #define log(...) fprintf(stderr, "[INFO]: " __VA_ARGS__) 46 #else 47 #define log(...) ((void)0) 48 #endif 49 50 static uint32_t icon_ext_hash(const char *s); 51 52 /* change ICONS_TABLE_SIZE to increase the size of the table */ 53 static struct icon_pair table[1u << ICONS_TABLE_SIZE]; 54 static uint8_t seen[ARRLEN(table)]; 55 /* arbitrarily picked starting position. change if needed. 56 * but ensure they're above 1 and prefer prime numbers. 57 */ 58 static uint32_t hash_start = 7; 59 static uint32_t hash_mul = 251; /* unused as of now */ 60 61 /* 62 * use robin-hood insertion to reduce the max probe length 63 */ 64 static void 65 rh_insert(const struct icon_pair item, uint32_t idx, uint32_t n) 66 { 67 ENSURE(n != 0); 68 for (uint32_t tries = 0; tries < ARRLEN(table); ++tries, ++n) { 69 if (seen[idx] < n) { 70 struct icon_pair tmp_item = table[idx]; 71 uint32_t tmp_n = seen[idx]; 72 73 ENSURE(n < (uint8_t)-1); 74 table[idx] = item; 75 seen[idx] = n; 76 77 if (tmp_n != 0) /* the slot we inserted to wasn't empty */ 78 rh_insert(tmp_item, idx, tmp_n); 79 return; 80 } 81 idx = (idx + 1) % ARRLEN(table); 82 } 83 ENSURE(0 && "unreachable"); 84 } 85 86 enum { PROBE_MAX, PROBE_TOTAL, PROBE_CNT }; 87 static unsigned int * 88 table_populate(unsigned int p[static PROBE_CNT]) 89 { 90 memset(seen, 0x0, sizeof seen); 91 memset(table, 0x0, sizeof table); 92 for (size_t i = 0; i < ARRLEN(icons_ext); ++i) { 93 if (icons_ext[i].icon[0] == '\0') /* skip empty entries */ 94 continue; 95 uint32_t h = icon_ext_hash(icons_ext[i].match); 96 rh_insert(icons_ext[i], h, 1); 97 } 98 99 p[PROBE_MAX] = p[PROBE_TOTAL] = 0; 100 for (size_t i = 0; i < ARRLEN(seen); ++i) { 101 p[PROBE_MAX] = MAX(p[PROBE_MAX], seen[i]); 102 p[PROBE_TOTAL] += seen[i]; 103 } 104 return p; 105 } 106 107 /* permuted congruential generator */ 108 static uint32_t 109 pcg(uint64_t *state) 110 { 111 uint64_t oldstate = *state; 112 *state *= GOLDEN_RATIO_64; 113 uint32_t r = (oldstate >> 59); 114 uint32_t v = (oldstate ^ (oldstate >> 18)) >> 27; 115 return (v >> (-r & 31)) | (v << r); 116 } 117 118 int 119 main(void) 120 { 121 ENSURE(ARRLEN(icons_ext) < ARRLEN(table)); 122 ENSURE(ICONS_TABLE_SIZE < 16); 123 ENSURE(1u << ICONS_TABLE_SIZE == ARRLEN(table)); 124 ENSURE((GOLDEN_RATIO_32 & 1) == 1); /* must be odd */ 125 ENSURE((GOLDEN_RATIO_64 & 1) == 1); /* must be odd */ 126 ENSURE(hash_start > 1); 127 ENSURE(hash_mul > 1); 128 /* ensure power of 2 hashtable size which allows compiler to optimize 129 * away mod (`%`) operations 130 */ 131 ENSURE((ARRLEN(table) & (ARRLEN(table) - 1)) == 0); 132 133 unsigned int max_probe = (unsigned)-1; 134 uint32_t best_hash_start = 0, best_hash_mul = 0, best_total_probe = 9999; 135 uint64_t hash_start_rng = hash_start, hash_mul_rng = hash_mul; 136 137 for (size_t i = 0; i < HGEN_ITERARATION; ++i) { 138 unsigned *p = table_populate((unsigned [PROBE_CNT]){0}); 139 if (p[PROBE_MAX] < max_probe || 140 (p[PROBE_MAX] == max_probe && p[PROBE_TOTAL] < best_total_probe)) 141 { 142 max_probe = p[PROBE_MAX]; 143 best_total_probe = p[PROBE_TOTAL]; 144 best_hash_start = hash_start; 145 best_hash_mul = hash_mul; 146 } 147 hash_start = pcg(&hash_start_rng); 148 hash_mul = pcg(&hash_mul_rng); 149 } 150 ENSURE(max_probe < ICONS_PROBE_MAX_ALLOWED); 151 hash_start = best_hash_start; 152 hash_mul = best_hash_mul; 153 { 154 unsigned *p = table_populate((unsigned [PROBE_CNT]){0}); 155 ENSURE(p[PROBE_MAX] == max_probe); 156 ENSURE(p[PROBE_TOTAL] == best_total_probe); 157 } 158 159 /* sanity check */ 160 double nitems = 0; 161 unsigned int total_probe = 0; 162 for (size_t i = 0; i < ARRLEN(icons_ext); ++i) { 163 if (icons_ext[i].icon[0] == 0) 164 continue; 165 uint32_t found = 0, h = icon_ext_hash(icons_ext[i].match); 166 for (uint32_t k = 0; k < max_probe; ++k) { 167 uint32_t z = (h + k) % ARRLEN(table); 168 ++total_probe; 169 if (table[z].match && strcasecmp(icons_ext[i].match, table[z].match) == 0) { 170 found = 1; 171 break; 172 } 173 } 174 ENSURE(found); 175 ++nitems; 176 } 177 ENSURE(total_probe == best_total_probe); 178 179 size_t match_max = 0, icon_max = 0; 180 for (size_t i = 0; i < ARRLEN(icons_name); ++i) { 181 match_max = MAX(match_max, strlen(icons_name[i].match) + 1); 182 icon_max = MAX(icon_max, strlen(icons_name[i].icon) + 1); 183 } 184 for (size_t i = 0; i < ARRLEN(icons_ext); ++i) { 185 match_max = MAX(match_max, strlen(icons_ext[i].match) + 1); 186 icon_max = MAX(icon_max, strlen(icons_ext[i].icon) + 1); 187 } 188 icon_max = MAX(icon_max, strlen(dir_icon.icon) + 1); 189 icon_max = MAX(icon_max, strlen(exec_icon.icon) + 1); 190 icon_max = MAX(icon_max, strlen(file_icon.icon) + 1); 191 ENSURE(icon_max < ICONS_MATCH_MAX); 192 193 const char *uniq[ARRLEN(icons_ext)] = {0}; 194 size_t uniq_head = 0; 195 for (size_t i = 0; i < ARRLEN(icons_ext); ++i) { 196 if (icons_ext[i].icon[0] == 0) 197 continue; 198 int isuniq = 1; 199 for (size_t k = 0; k < uniq_head; ++k) { 200 if (strcasecmp(uniq[k], icons_ext[i].icon) == 0) { 201 isuniq = 0; 202 break; 203 } 204 } 205 if (isuniq) { 206 ENSURE(uniq_head < ARRLEN(uniq)); 207 uniq[uniq_head++] = icons_ext[i].icon; 208 } 209 } 210 ENSURE(uniq_head < (unsigned char)-1); 211 212 log("load-factor: %.2f (%u/%zu)\n", (nitems * 100.0) / (double)ARRLEN(table), 213 (unsigned int)nitems, ARRLEN(table)); 214 log("max_probe : %6u\n", max_probe); 215 log("total_probe: %6u\n", total_probe); 216 log("uniq icons : %6zu\n", uniq_head); 217 log("no-compact : %6zu bytes\n", ARRLEN(table) * icon_max); 218 log("compaction : %6zu bytes\n", uniq_head * icon_max + ARRLEN(table)); 219 log("hash_start : %6" PRIu32 "\n", hash_start); 220 log("hash_mul : %6" PRIu32 "\n", hash_mul); 221 222 printf("#ifndef INCLUDE_ICONS_GENERATED\n"); 223 printf("#define INCLUDE_ICONS_GENERATED\n\n"); 224 225 printf("/*\n * NOTE: This file is automatically generated.\n"); 226 printf(" * DO NOT EDIT THIS FILE DIRECTLY.\n"); 227 printf(" * Use `icons.h` to customize icons\n */\n\n"); 228 229 printf("#define hash_start UINT32_C(%" PRIu32 ")\n", hash_start); 230 printf("#define hash_mul UINT32_C(%" PRIu32 ")\n\n", hash_mul); 231 printf("#define ICONS_PROBE_MAX %uu\n", max_probe); 232 printf("#define ICONS_MATCH_MAX %zuu\n\n", match_max); 233 printf("#define ICONS_STR_MAX %zuu\n\n", icon_max); 234 235 printf("struct icon_pair { const char match[ICONS_MATCH_MAX]; " 236 "const char icon[ICONS_STR_MAX]; unsigned char color; };\n\n"); 237 238 printf("static const char icons_ext_uniq[%zu][ICONS_STR_MAX] = {\n", uniq_head); 239 for (size_t i = 0; i < uniq_head; ++i) 240 printf("\t\"%s\",\n", uniq[i]); 241 printf("};\n\n"); 242 243 printf("static const struct {\n\tconst char match[ICONS_MATCH_MAX];\n" 244 "\tunsigned char idx;\n\tunsigned char color;\n} icons_ext[%zu] = {\n", 245 ARRLEN(table)); 246 for (size_t i = 0; i < ARRLEN(table); ++i) { 247 if (table[i].icon == NULL || table[i].icon[0] == '\0') /* skip empty entries */ 248 continue; 249 size_t k; 250 for (k = 0; k < uniq_head; ++k) { 251 if (strcasecmp(table[i].icon, uniq[k]) == 0) 252 break; 253 } 254 ENSURE(k < uniq_head); 255 printf("\t[%3zu] = {\"%s\", %zu, %hhu },\n", 256 i, table[i].match, k, table[i].color); 257 } 258 printf("};\n\n"); 259 260 printf("#endif /* INCLUDE_ICONS_GENERATED */\n"); 261 } 262 263 #else 264 #define ENSURE(X) ((void)0) 265 #endif /* ICONS_GENERATE */ 266 267 #if defined(ICONS_GENERATE) || defined(ICONS_ENABLED) 268 static uint32_t 269 icon_ext_hash(const char *str) 270 { 271 uint32_t i, hash = hash_start; 272 enum { wsz = sizeof hash * CHAR_BIT, z = wsz - ICONS_TABLE_SIZE, r = 5 }; 273 274 /* just an xor-rotate hash. in general, this is a horrible hash 275 * function but for our specific input it works fine while being 276 * computationally cheap. 277 */ 278 for (i = 0; i < ICONS_MATCH_MAX && str[i] != '\0'; ++i) { 279 hash ^= TOUPPER((unsigned char)str[i]); 280 hash = (hash >> (wsz - r)) | (hash << r); 281 } 282 283 /* finalizer: https://probablydance.com/2018/06/16 */ 284 hash ^= (hash >> z); 285 hash *= GOLDEN_RATIO_32; 286 287 hash >>= z; 288 ENSURE(hash < ARRLEN(table)); 289 290 return hash; 291 } 292 #endif