asm/tokhash.pl

   1 #!/usr/bin/perl
   2 ## --------------------------------------------------------------------------
   3 ##
   4 ##   Copyright 1996-2018 The NASM Authors - All Rights Reserved
   5 ##   See the file AUTHORS included with the NASM distribution for
   6 ##   the specific copyright holders.
   7 ##
   8 ##   Redistribution and use in source and binary forms, with or without
   9 ##   modification, are permitted provided that the following
  10 ##   conditions are met:
  11 ##
  12 ##   * Redistributions of source code must retain the above copyright
  13 ##     notice, this list of conditions and the following disclaimer.
  14 ##   * Redistributions in binary form must reproduce the above
  15 ##     copyright notice, this list of conditions and the following
  16 ##     disclaimer in the documentation and/or other materials provided
  17 ##     with the distribution.
  18 ##
  19 ##     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
  20 ##     CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
  21 ##     INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
  22 ##     MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  23 ##     DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
  24 ##     CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  25 ##     SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  26 ##     NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  27 ##     LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  28 ##     HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  29 ##     CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
  30 ##     OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
  31 ##     EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  32 ##
  33 ## --------------------------------------------------------------------------
  34
  35 #
  36 # Generate a perfect hash for token parsing
  37 #
  38 # Usage: tokenhash.pl insns.dat regs.dat tokens.dat
  39 #
  40
  41 require 'phash.ph';
  42
  43 my($output, $insns_dat, $regs_dat, $tokens_dat) = @ARGV;
  44
  45 %tokens = ();
  46 @tokendata = ();
  47
  48 #
  49 # List of condition codes
  50 #
  51 @conditions = ('a', 'ae', 'b', 'be', 'c', 'e', 'g', 'ge', 'l', 'le',
  52                'na', 'nae', 'nb', 'nbe', 'nc', 'ne', 'ng', 'nge', 'nl',
  53                'nle', 'no', 'np', 'ns', 'nz', 'o', 'p', 'pe', 'po', 's', 'z');
  54
  55 #
  56 # Read insns.dat
  57 #
  58 open(ID, '<', $insns_dat) or die "$0: cannot open $insns_dat: $!\n";
  59 while (defined($line = <ID>)) {
  60     if ($line =~ /^([\?\@A-Z0-9_]+)(|cc)\s/) {
  61         $insn = $1.$2;
  62         ($token = $1) =~ tr/A-Z/a-z/;
  63
  64         if ($2 eq '') {
  65             # Single instruction token
  66             if (!defined($tokens{$token})) {
  67                 $tokens{$token} = scalar @tokendata;
  68                 push(@tokendata, "\"${token}\", ".length($token).
  69                      ", TOKEN_INSN, C_none, 0, I_${insn}");
  70             }
  71         } else {
  72             # Conditional instruction
  73             foreach $cc (@conditions) {
  74                 my $etok = $token.$cc;
  75                 if (!defined($tokens{$etok})) {
  76                     $tokens{$etok} = scalar @tokendata;
  77                     push(@tokendata, "\"${etok}\", ".length($etok).
  78                          ", TOKEN_INSN, C_\U$cc\E, 0, I_${insn}");
  79                 }
  80             }
  81         }
  82     }
  83 }
  84 close(ID);
  85
  86 #
  87 # Read regs.dat
  88 #
  89 open(RD, '<', $regs_dat) or die "$0: cannot open $regs_dat: $!\n";
  90 while (defined($line = <RD>)) {
  91     if ($line =~ /^([\?\@a-z0-9_-]+)\s*\S+\s*\S+\s*[0-9]+\s*(\S*)/) {
  92         $reg = $1;
  93         $reg_flag = $2;
  94
  95         if ($reg =~ /^(.*[^0-9])([0-9]+)\-([0-9]+)(|[^0-9].*)$/) {
  96             $nregs = $3-$2+1;
  97             $reg = $1.$2.$4;
  98             $reg_nr = $2;
  99             $reg_prefix = $1;
 100             $reg_suffix = $4;
 101         } else {
 102             $nregs = 1;
 103             undef $reg_prefix;
 104             undef $reg_suffix;
 105         }
 106
 107         while ($nregs--) {
 108             if (defined($tokens{$reg})) {
 109                 die "Duplicate definition: $reg\n";
 110             }
 111             $tokens{$reg} = scalar @tokendata;
 112             $reg_flag = '0' if ($reg_flag eq '');
 113             push(@tokendata, "\"${reg}\", ".length($reg).", TOKEN_REG, 0, ${reg_flag}, R_\U${reg}\E");
 114
 115             if (defined($reg_prefix)) {
 116                 $reg_nr++;
 117                 $reg = sprintf("%s%u%s", $reg_prefix, $reg_nr, $reg_suffix);
 118             } else {
 119                 # Not a dashed sequence
 120                 die if ($nregs);
 121             }
 122         }
 123     }
 124 }
 125 close(RD);
 126
 127 #
 128 # Read tokens.dat
 129 #
 130 open(TD, '<', $tokens_dat) or die "$0: cannot open $tokens_dat: $!\n";
 131 while (defined($line = <TD>)) {
 132     $line =~ s/\s*(|\#.*)$//;
 133     if ($line =~ /^\%\s+(.*)$/) {
 134         $pattern = $1;
 135     } elsif ($line =~ /^(\S+)/) {
 136         $token = $1;
 137
 138         if (defined($tokens{$token})) {
 139             die "Duplicate definition: $token\n";
 140         }
 141         $tokens{$token} = scalar @tokendata;
 142
 143         $data = $pattern;
 144         if ($data =~ /^(.*)\{(.*)\}(.*)$/) {
 145             my $head = $1, $tail = $3;
 146             my $px = $2;
 147
 148             $px =~ s/\?/\\?/g;
 149             $px =~ s/\*/(.*)/g;
 150             if ($token =~ /$px/i) {
 151                 $data = $head."\U$1".$tail;
 152             } else {
 153                 die "$0: token $token doesn't match $px\n";
 154             }
 155         }
 156
 157         $data =~ s/\*/\U$token/g;
 158         $data =~ s/\?//g;
 159
 160         push(@tokendata, "\"$token\", ".length($token).", $data");
 161     }
 162 }
 163 close(TD);
 164
 165 $max_len = 0;
 166 foreach $token (keys(%tokens)) {
 167     if (length($token) > $max_len) {
 168         $max_len = length($token);
 169     }
 170 }
 171
 172 if ($output eq 'h') {
 173     #
 174     # tokens.h
 175     #
 176
 177     print "/*\n";
 178     print " * This file is generated from insns.dat, regs.dat and token.dat\n";
 179     print " * by tokhash.pl; do not edit.\n";
 180     print " */\n";
 181     print "\n";
 182
 183     print "#ifndef NASM_TOKENS_H\n";
 184     print "#define NASM_TOKENS_H\n";
 185     print "\n";
 186     print "#define MAX_KEYWORD $max_len /* length of longest keyword */\n";
 187     print "\n";
 188     print "#endif /* NASM_TOKENS_H */\n";
 189 } elsif ($output eq 'c') {
 190     #
 191     # tokhash.c
 192     #
 193
 194     @hashinfo = gen_perfect_hash(\%tokens);
 195     if (!@hashinfo) {
 196         die "$0: no hash found\n";
 197     }
 198
 199     # Paranoia...
 200     verify_hash_table(\%tokens, \@hashinfo);
 201
 202     ($n, $sv, $g) = @hashinfo;
 203     die if ($n & ($n-1));
 204
 205     print "/*\n";
 206     print " * This file is generated from insns.dat, regs.dat and token.dat\n";
 207     print " * by tokhash.pl; do not edit.\n";
 208     print " */\n";
 209     print "\n";
 210
 211     print "#include \"compiler.h\"\n";
 212     print "#include \"nasm.h\"\n";
 213     print "#include \"hashtbl.h\"\n";
 214     print "#include \"insns.h\"\n";
 215     print "#include \"stdscan.h\"\n";
 216     print "\n";
 217
 218     # These somewhat odd sizes and ordering thereof are due to the
 219     # relative ranges of the types; this makes it fit in 16 bytes on
 220     # 64-bit machines and 12 bytes on 32-bit machines.
 221     print "struct tokendata {\n";
 222     print "    const char *string;\n";
 223     print "    uint16_t len;\n";
 224     print "    int16_t tokentype;\n";
 225     print "    int16_t aux;\n";
 226     print "    uint16_t tokflag;\n";
 227     print "    int32_t num;\n";
 228     print "};\n";
 229     print "\n";
 230
 231     print "int nasm_token_hash(const char *token, struct tokenval *tv)\n";
 232     print "{\n";
 233
 234     # Put a large value in unused slots.  This makes it extremely unlikely
 235     # that any combination that involves unused slot will pass the range test.
 236     # This speeds up rejection of unrecognized tokens, i.e. identifiers.
 237     print "#define UNUSED_HASH_ENTRY (65535/3)\n";
 238
 239     print "    static const int16_t hash1[$n] = {\n";
 240     for ($i = 0; $i < $n; $i++) {
 241         my $h = ${$g}[$i*2+0];
 242         print "        ", defined($h) ? $h : 'UNUSED_HASH_ENTRY', ",\n";
 243     }
 244     print "    };\n";
 245
 246     print "    static const int16_t hash2[$n] = {\n";
 247     for ($i = 0; $i < $n; $i++) {
 248         my $h = ${$g}[$i*2+1];
 249         print "        ", defined($h) ? $h : 'UNUSED_HASH_ENTRY', ",\n";
 250     }
 251     print "    };\n";
 252
 253     printf "    static const struct tokendata tokendata[%d] = {\n",
 254         scalar(@tokendata);
 255     foreach $d (@tokendata) {
 256         print "        { ", $d, " },\n";
 257     }
 258     print  "    };\n";
 259
 260     print  "    uint32_t k1, k2;\n";
 261     # For correct overflow behavior, "ix" should be unsigned of the same
 262     # width as the hash arrays.
 263     print  "    uint16_t ix;\n";
 264     print  "    const struct tokendata *data;\n";
 265     printf "    char lcbuf[%d];\n", $max_len+1;
 266     print  "    const char *p = token;\n";
 267     print  "    char c, *q = lcbuf;\n";
 268     print  "    size_t len = 0;\n";
 269     printf "    uint64_t crc = UINT64_C(0x%08x%08x);\n", $$sv[0], $$sv[1];
 270     print  "\n";
 271     print  "    while ((c = *p++)) {\n";
 272     printf "        if (++len > %d)\n", $max_len;
 273     print  "            goto notfound;\n";
 274     print  "        *q++ = c = nasm_tolower(c);\n";
 275     print  "        crc = crc64_byte(crc, c);\n";
 276     print  "    };\n";
 277     print  "\n";
 278     print  "    k1 = (uint32_t)crc;\n";
 279     print  "    k2 = (uint32_t)(crc >> 32);\n";
 280     print  "\n";
 281     printf "    ix = hash1[k1 & 0x%x] + hash2[k2 & 0x%x];\n", $n-1, $n-1;
 282     printf "    if (ix >= %d)\n", scalar(@tokendata);
 283     print  "        goto notfound;\n";
 284     print  "\n";
 285     print  "    data = &tokendata[ix];\n";
 286     print  "    if (data->len != len)\n";
 287     print  "        goto notfound;\n";
 288     print  "    if (memcmp(data->string, lcbuf, len))\n";
 289     print  "        goto notfound;\n";
 290     print  "\n";
 291     print  "    tv->t_integer = data->num;\n";
 292     print  "    tv->t_inttwo  = data->aux;\n";
 293     print  "    tv->t_flag    = data->tokflag;\n";
 294     print  "    return tv->t_type = data->tokentype;\n";
 295     print  "\n";
 296     print  "notfound:\n";
 297     print  "    tv->t_integer = 0;\n";
 298     print  "    tv->t_inttwo  = 0;\n";
 299     print  "    tv->t_flag    = 0;\n";
 300     print  "    return tv->t_type = TOKEN_ID;\n";
 301     print  "}\n";
 302 }