2 ## --------------------------------------------------------------------------
4 ## Copyright 1996-2014 The NASM Authors - All Rights Reserved
5 ## See the file AUTHORS included with the NASM distribution for
6 ## the specific copyright holders.
8 ## Redistribution and use in source and binary forms, with or without
9 ## modification, are permitted provided that the following
10 ## conditions are met:
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.
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.
33 ## --------------------------------------------------------------------------
36 # Generate a perfect hash for token parsing
38 # Usage: tokenhash.pl insns.dat regs.dat tokens.dat
43 my($output, $insns_dat, $regs_dat, $tokens_dat) = @ARGV;
49 # List of condition codes
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');
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/) {
62 ($token = $1) =~ tr/A-Z/a-z/;
65 # Single instruction token
66 if (!defined($tokens{$token})) {
67 $tokens{$token} = scalar @tokendata;
68 push(@tokendata, "\"${token}\", TOKEN_INSN, C_none, 0, I_${insn}");
71 # Conditional instruction
72 foreach $cc (@conditions) {
73 if (!defined($tokens{$token.$cc})) {
74 $tokens{$token.$cc} = scalar @tokendata;
75 push(@tokendata, "\"${token}${cc}\", TOKEN_INSN, C_\U$cc\E, 0, I_${insn}");
86 open(RD
, "< ${regs_dat}") or die "$0: cannot open $regs_dat: $!\n";
87 while (defined($line = <RD
>)) {
88 if ($line =~ /^([a-z0-9_-]+)\s*\S+\s*\S+\s*[0-9]+\s*(\S*)/) {
92 if ($reg =~ /^(.*[^0-9])([0-9]+)\-([0-9]+)(|[^0-9].*)$/) {
100 undef $reg_prefix, $reg_suffix;
104 if (defined($tokens{$reg})) {
105 die "Duplicate definition: $reg\n";
107 $tokens{$reg} = scalar @tokendata;
108 if ($reg_flag eq '') {
109 push(@tokendata, "\"${reg}\", TOKEN_REG, 0, 0, R_\U${reg}\E");
111 push(@tokendata, "\"${reg}\", TOKEN_REG, 0, ${reg_flag}, R_\U${reg}\E");
114 if (defined($reg_prefix)) {
116 $reg = sprintf("%s%u%s", $reg_prefix, $reg_nr, $reg_suffix);
118 # Not a dashed sequence
129 open(TD
, "< ${tokens_dat}") or die "$0: cannot open $tokens_dat: $!\n";
130 while (defined($line = <TD
>)) {
131 if ($line =~ /^\%\s+(.*)$/) {
133 } elsif ($line =~ /^([a-z0-9_-]+)/) {
136 if (defined($tokens{$token})) {
137 die "Duplicate definition: $token\n";
139 $tokens{$token} = scalar @tokendata;
142 if ($data =~ /^(.*)\{(.*)\}(.*)$/) {
143 my $head = $1, $tail = $3;
147 if ($token =~ /$px/i) {
148 $data = $head."\U$1".$tail;
150 die "$0: token $token doesn't match $px\n";
154 $data =~ s/\*/\U$token/g;
156 push(@tokendata, "\"$token\", $data");
161 if ($output eq 'h') {
167 foreach $token (keys(%tokens)) {
168 if (length($token) > $max_len) {
169 $max_len = length($token);
174 print " * This file is generated from insns.dat, regs.dat and token.dat\n";
175 print " * by tokhash.pl; do not edit.\n";
179 print "#ifndef NASM_TOKENS_H\n";
180 print "#define NASM_TOKENS_H\n";
182 print "#define MAX_KEYWORD $max_len /* length of longest keyword */\n";
184 print "#endif /* NASM_TOKENS_H */\n";
185 } elsif ($output eq 'c') {
190 @hashinfo = gen_perfect_hash
(\
%tokens);
192 die "$0: no hash found\n";
196 verify_hash_table
(\
%tokens, \
@hashinfo);
198 ($n, $sv, $g) = @hashinfo;
201 die if ($n & ($n-1));
204 print " * This file is generated from insns.dat, regs.dat and token.dat\n";
205 print " * by tokhash.pl; do not edit.\n";
209 print "#include \"compiler.h\"\n";
210 print "#include <string.h>\n";
211 print "#include \"nasm.h\"\n";
212 print "#include \"hashtbl.h\"\n";
213 print "#include \"insns.h\"\n";
214 print "#include \"stdscan.h\"\n";
217 # These somewhat odd sizes and ordering thereof are due to the
218 # relative ranges of the types; this makes it fit in 16 bytes on
219 # 64-bit machines and 12 bytes on 32-bit machines.
220 print "struct tokendata {\n";
221 print " const char *string;\n";
222 print " int16_t tokentype;\n";
223 print " int8_t aux;\n";
224 print " int8_t tokflag;\n";
225 print " int32_t num;\n";
229 print "int nasm_token_hash(const char *token, struct tokenval *tv)\n";
232 # Put a large value in unused slots. This makes it extremely unlikely
233 # that any combination that involves unused slot will pass the range test.
234 # This speeds up rejection of unrecognized tokens, i.e. identifiers.
235 print "#define UNUSED 16383\n";
237 print " static const int16_t hash1[$n] = {\n";
238 for ($i = 0; $i < $n; $i++) {
239 my $h = ${$g}[$i*2+0];
240 print " ", defined($h) ?
$h : 'UNUSED', ",\n";
244 print " static const int16_t hash2[$n] = {\n";
245 for ($i = 0; $i < $n; $i++) {
246 my $h = ${$g}[$i*2+1];
247 print " ", defined($h) ?
$h : 'UNUSED', ",\n";
251 printf " static const struct tokendata tokendata[%d] = {\n", scalar(@tokendata);
252 foreach $d (@tokendata) {
253 print " { ", $d, " },\n";
257 print " uint32_t k1, k2;\n";
258 print " uint64_t crc;\n";
259 # For correct overflow behavior, "ix" should be unsigned of the same
260 # width as the hash arrays.
261 print " uint16_t ix;\n";
262 print " const struct tokendata *data;\n";
264 printf " tv->t_flag = 0;\n";
265 printf " crc = crc64(UINT64_C(0x%08x%08x), token);\n",
267 print " k1 = (uint32_t)crc;\n";
268 print " k2 = (uint32_t)(crc >> 32);\n";
270 printf " ix = hash1[k1 & 0x%x] + hash2[k2 & 0x%x];\n", $n-1, $n-1;
271 printf " if (ix >= %d)\n", scalar(@tokendata);
272 print " return tv->t_type = TOKEN_ID;\n";
274 print " data = &tokendata[ix];\n";
276 print " if (strcmp(data->string, token))\n";
277 print " return tv->t_type = TOKEN_ID;\n";
279 print " tv->t_integer = data->num;\n";
280 print " tv->t_inttwo = data->aux;\n";
281 print " tv->t_flag = data->tokflag;\n";
282 print " return tv->t_type = data->tokentype;\n";