src/icons-hash.c

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