create-okey-map.pl

   1 #!/usr/bin/env perl
   2 require 5.008_001;
   3 use utf8;
   4 #@ Parse 'enum okeys' from nail.h and create okeys.h.  And see acmava.c.
   5 # Public Domain
   6
   7 # Acceptable "longest distance" from hash-modulo-index to key
   8 my $MAXDISTANCE_PENALTY = 5;
   9
  10 my $OUT = 'okeys.h';
  11
  12 ##  --  >8  --  8<  --  ##
  13
  14 use diagnostics -verbose;
  15 use strict;
  16 use warnings;
  17
  18 use sigtrap qw(handler cleanup normal-signals);
  19
  20 my (@ENTS, $CTOOL, $CTOOL_EXE);
  21
  22 sub main_fun {
  23    parse_nail_h();
  24
  25    create_c_tool();
  26
  27    hash_em();
  28    dump_keydat_varmap();
  29
  30    reverser();
  31
  32    cleanup(undef);
  33    exit 0
  34 }
  35
  36 sub cleanup {
  37    die "$CTOOL_EXE: couldn't unlink: $^E"
  38       if $CTOOL_EXE && -f $CTOOL_EXE && 1 != unlink $CTOOL_EXE;
  39    die "$CTOOL: couldn't unlink: $^E"
  40       if $CTOOL && -f $CTOOL && 1 != unlink $CTOOL;
  41    die "Terminating due to signal $_[0]" if $_[0]
  42 };
  43
  44 sub parse_nail_h {
  45    die "nail.h: open: $^E" unless open F, '<', 'nail.h';
  46    my ($init) = (0);
  47    while (<F>) {
  48       # Only want the enum okeys content
  49       if (/^enum okeys/) {$init = 1; next}
  50       if (/^};/) {if ($init) {$init = 2; last}; next}
  51       $init || next;
  52
  53       # Ignore empty and comment lines
  54       /^$/ && next;
  55       /^\s*\/\*/ && next;
  56
  57       # An entry may have a comment with special directives
  58       /^\s*(\w+),?\s*(?:\/\*\s*(?:{(.*)})\s*\*\/\s*)?$/;
  59       my ($k, $x) = ($1, $2);
  60       my %vals;
  61       $vals{enum} = $k;
  62       $vals{binary} = ($k =~ /^ok_b/ ? 1 : 0);
  63       $k = $1 if $k =~ /^ok_[bv]_(.+)$/;
  64       $k =~ s/_/-/g;
  65       $vals{name} = $k;
  66       if ($x) {
  67          while ($x && $x =~ /^([^,]+?)(?:,(.*))?$/) {
  68             $x = $2;
  69             $1 =~ /([^=]+)=(.+)/;
  70             die "Unsupported special directive: $1"
  71                if ($1 ne 'name' && $1 ne 'special');
  72             $vals{$1} = $2
  73          }
  74       }
  75       push @ENTS, \%vals
  76    }
  77    if ($init != 2) {die 'nail.h does not have the expected content'}
  78    close F
  79 }
  80
  81 sub create_c_tool {
  82    $CTOOL = './tmp-okey-tool-' . $$ . '.c';
  83    $CTOOL_EXE = $CTOOL . '.exe';
  84
  85    die "$CTOOL: open: $^E" unless open F, '>', $CTOOL;
  86    # xxx optimize: could read lines and write lines in HASH_MODE..
  87    print F '#define MAX_DISTANCE_PENALTY ', $MAXDISTANCE_PENALTY, "\n";
  88 # >>>>>>>>>>>>>>>>>>>
  89    print F <<'__EOT';
  90 #include <stdint.h>
  91 #include <stdlib.h>
  92 #include <stdio.h>
  93 #include <string.h>
  94
  95 #ifndef NELEM
  96 # define NELEM(A) (sizeof(A) / sizeof(A[0]))
  97 #endif
  98
  99 #define ui32_t    uint32_t
 100 #define ui16_t    uint16_t
 101 #define ui8_t     uint8_t
 102
 103 struct var_map {
 104    ui32_t      vm_hash;
 105    ui16_t      vm_keyoff;
 106    ui8_t       vm_binary;
 107    ui8_t       vm_special;
 108 };
 109
 110 #ifdef HASH_MODE
 111 /* NOTE: copied over from auxlily.c */
 112 static ui32_t
 113 torek_hash(char const *name)
 114 {
 115    /* Chris Torek's hash.
 116     * NOTE: need to change *at least* create-okey-map.pl when changing the
 117     * algorithm!! */
 118         ui32_t h = 0;
 119
 120         while (*name != '\0') {
 121                 h *= 33;
 122                 h += *name++;
 123         }
 124         return h;
 125 }
 126
 127 #else
 128   /* Include what has been written in HASH_MODE */
 129 # include "okeys.h"
 130
 131 static ui8_t   seen_wraparound;
 132 static size_t  longest_distance;
 133
 134 static size_t
 135 next_prime(size_t no) /* blush (brute force) */
 136 {
 137 jredo:
 138    ++no;
 139    for (size_t i = 3; i < no; i += 2)
 140       if (no % i == 0)
 141          goto jredo;
 142    return no;
 143 }
 144
 145 static size_t *
 146 reversy(size_t size)
 147 {
 148    struct var_map const *vmp = _var_map, *vmaxp = vmp + NELEM(_var_map);
 149    size_t ldist = 0, *arr;
 150
 151    arr = malloc(sizeof *arr * size);
 152    for (size_t i = 0; i < size; ++i)
 153       arr[i] = NELEM(_var_map);
 154
 155    seen_wraparound = 0;
 156    longest_distance = 0;
 157
 158    while (vmp < vmaxp) {
 159       ui32_t hash = vmp->vm_hash, i = hash % size, l;
 160
 161       for (l = 0; arr[i] != NELEM(_var_map); ++l)
 162          if (++i == size) {
 163             seen_wraparound = 1;
 164             i = 0;
 165          }
 166       if (l > longest_distance)
 167          longest_distance = l;
 168       arr[i] = (size_t)(vmp++ - _var_map);
 169    }
 170    return arr;
 171 }
 172 #endif /* !HASH_MODE */
 173
 174 int
 175 main(int argc, char **argv)
 176 {
 177 #ifdef HASH_MODE
 178    size_t h = torek_hash(argv[1]);
 179
 180    printf("%lu\n", (unsigned long)h);
 181
 182 #else
 183    size_t *arr, size = NELEM(_var_map);
 184
 185    fprintf(stderr, "Starting reversy, okeys=%zu\n", size);
 186    for (;;) {
 187       arr = reversy(size = next_prime(size));
 188       fprintf(stderr, " - size=%zu longest_distance=%zu seen_wraparound=%d\n",
 189          size, longest_distance, seen_wraparound);
 190       if (longest_distance <= MAX_DISTANCE_PENALTY)
 191          break;
 192       free(arr);
 193    }
 194
 195    printf(
 196       "#define _VAR_REV_ILL         %zuu\n"
 197       "#define _VAR_REV_PRIME       %zuu\n"
 198       "#define _VAR_REV_LONGEST     %zuu\n"
 199       "#define _VAR_REV_WRAPAROUND  %d\n"
 200       "static %s const _var_revmap[_VAR_REV_PRIME] = {\n   ",
 201       NELEM(_var_map), size, longest_distance, seen_wraparound, argv[1]);
 202    for (size_t i = 0; i < size; ++i)
 203       printf("%s%zuu", (i == 0 ? "" : (i % 10 == 0 ? ",\n   " : ", ")), arr[i]);
 204    printf("\n};\n");
 205 #endif
 206    return 0;
 207 }
 208 __EOT
 209 # <<<<<<<<<<<<<<<<<<<
 210    close F
 211 }
 212
 213 sub hash_em {
 214    system("c99 -DHASH_MODE -I. -o $CTOOL_EXE $CTOOL");
 215
 216    foreach my $e (@ENTS) {
 217       my $h = `$CTOOL_EXE $e->{name}`;
 218       chomp $h;
 219       $e->{hash} = $h
 220    }
 221 }
 222
 223 sub dump_keydat_varmap {
 224    die "$OUT: open: $^E" unless open F, '>', $OUT;
 225    print F "/*@ $OUT, generated by $0 on ", scalar gmtime(), ".\n",
 226       " *@ See acmava.c for more */\n\n";
 227
 228    print F 'static char const _var_keydat[] = {', "\n";
 229    my ($i, $alen) = (0, 0);
 230    foreach my $e (@ENTS) {
 231       $e->{keyoff} = $alen;
 232       my $k = $e->{name};
 233       my $l = length $k;
 234       my $a = join '\',\'', split(//, $k);
 235       print F "   /* $i. [$alen]+$l $k, binary=$e->{binary} */\n",
 236          "   '$a','\\0',\n";
 237       ++$i;
 238       $alen += $l + 1
 239    }
 240    print F '};', "\n\n";
 241
 242    print F 'static struct var_map const _var_map[] = {', "\n";
 243    foreach my $e (@ENTS) {
 244       print F "   /* $e->{enum} */ {$e->{hash}u, $e->{keyoff}u, ",
 245          ($e->{binary} ? '1' : '0'), ', ', ($e->{special} ? '1' : '0'), "},\n"
 246    }
 247    print F '};', "\n\n";
 248
 249    die "$OUT: close: $^E" unless close F
 250 }
 251
 252 sub reverser {
 253    system("c99 -I. -o $CTOOL_EXE $CTOOL");
 254    my $t = (@ENTS < 0xFF ? 'ui8_t' : (@ENTS < 0xFFFF ? 'ui16_t' : 'ui32_t'));
 255    `$CTOOL_EXE $t >> $OUT`
 256 }
 257
 258 {package main; main_fun()}
 259
 260 # vim:set fenc=utf-8:s-it-mode