3 # Static Hashtable Generator
5 # (c) 2000-2002 by Harri Porten <porten@kde.org> and
6 # David Faure <faure@kde.org>
7 # Modified (c) 2004 by Nikolas Zimmermann <wildfox@kde.org>
8 # Copyright (C) 2007, 2008, 2009 Apple Inc. All rights reserved.
10 # This library is free software; you can redistribute it and/or
11 # modify it under the terms of the GNU Lesser General Public
12 # License as published by the Free Software Foundation; either
13 # version 2 of the License, or (at your option) any later version.
15 # This library is distributed in the hope that it will be useful,
16 # but WITHOUT ANY WARRANTY; without even the implied warranty of
17 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
18 # Lesser General Public License for more details.
20 # You should have received a copy of the GNU Lesser General Public
21 # License along with this library; if not, write to the Free Software
22 # Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
29 my $includelookup = 0;
31 # Use -i as second argument to make it include "Lookup.h"
32 $includelookup = 1 if (defined($ARGV[0]) && $ARGV[0] eq "-i");
34 # Use -n as second argument to make it use the third argument as namespace parameter ie. -n KDOM
35 my $useNameSpace = $ARGV[1] if (defined($ARGV[0]) && $ARGV[0] eq "-n");
37 print STDERR "Creating hashtable for $file\n";
38 open(IN, $file) or die "No such file $file";
49 my $compactHashSizeMask;
51 sub calcPerfectHashSize();
52 sub calcCompactHashSize();
60 next if /^\#|^$/; # Comment or blank line. Do nothing.
61 if (/^\@begin/ && !$inside) {
62 if (/^\@begin\s*([:_\w]+)\s*\d*\s*$/) {
66 print STDERR "WARNING: \@begin without table name, skipping $_\n";
68 } elsif (/^\@end\s*$/ && $inside) {
69 calcPerfectHashSize();
70 calcCompactHashSize();
79 } elsif (/^(\S+)\s*(\S+)\s*([\w\|]*)\s*(\w*)\s*$/ && $inside) {
86 push(@attrs, length($att) > 0 ? $att : "0");
88 if ($att =~ m/Function/) {
89 push(@values, { "type" => "Function", "function" => $val, "params" => (length($param) ? $param : "") });
90 #printf STDERR "WARNING: Number of arguments missing for $key/$val\n" if (length($param) == 0);
91 } elsif (length($att)) {
93 my $put = !($att =~ m/ReadOnly/) ? "set" . jsc_ucfirst($val) : "0";
94 push(@values, { "type" => "Property", "get" => $get, "put" => $put });
96 push(@values, { "type" => "Lexer", "value" => $val });
98 push(@hashes, hashValue($key));
100 die "invalid data {" . $_ . "}";
104 die "missing closing \@end" if ($inside);
110 if ($value =~ /js/) {
115 return ucfirst($value);
119 sub ceilingToPowerOf2
121 my ($pefectHashSize) = @_;
124 while ($pefectHashSize > $powerOf2) {
131 sub calcPerfectHashSize()
134 for ($pefectHashSize = ceilingToPowerOf2(scalar @keys); ; $pefectHashSize += $pefectHashSize) {
136 foreach my $key (@keys) {
137 my $h = hashValue($key) % $pefectHashSize;
138 next tableSizeLoop if $table[$h];
146 my ($value, $distance) = @_;
147 return (($value << $distance) & 0xFFFFFFFF);
150 sub calcCompactHashSize()
154 my $compactHashSize = ceilingToPowerOf2(2 * @keys);
155 $compactHashSizeMask = $compactHashSize - 1;
156 $compactSize = $compactHashSize;
160 foreach my $key (@keys) {
162 my $h = hashValue($key) % $compactHashSize;
163 while (defined($table[$h])) {
164 if (defined($links[$h])) {
169 $links[$h] = $compactSize;
176 $maxdepth = $depth if ( $depth > $maxdepth);
180 # Paul Hsieh's SuperFastHash
181 # http://www.azillionmonkeys.com/qed/hash.html
182 # Ported from UString..
184 my @chars = split(/ */, $_[0]);
186 # This hash is designed to work on 16-bit chunks at a time. But since the normal case
187 # (above) is to hash UTF-16 characters, we just treat the 8-bit chars as if they
188 # were 16-bit chunks, which should give matching results
190 my $EXP2_32 = 4294967296;
192 my $hash = 0x9e3779b9;
193 my $l = scalar @chars; #I wish this was in Ruby --- Maks
200 for (; $l > 0; $l--) {
201 $hash += ord($chars[$s]);
202 my $tmp = leftShift(ord($chars[$s+1]), 11) ^ $hash;
203 $hash = (leftShift($hash, 16)% $EXP2_32) ^ $tmp;
205 $hash += $hash >> 11;
211 $hash += ord($chars[$s]);
212 $hash ^= (leftShift($hash, 11)% $EXP2_32);
213 $hash += $hash >> 17;
216 # Force "avalanching" of final 127 bits
217 $hash ^= leftShift($hash, 3);
218 $hash += ($hash >> 5);
219 $hash = ($hash% $EXP2_32);
220 $hash ^= (leftShift($hash, 2)% $EXP2_32);
221 $hash += ($hash >> 15);
222 $hash = $hash% $EXP2_32;
223 $hash ^= (leftShift($hash, 10)% $EXP2_32);
225 # this avoids ever returning a hash code of 0, since that is used to
226 # signal "hash not computed yet", using a value that is likely to be
227 # effectively the same as 0 when the low bits are masked
228 $hash = 0x80000000 if ($hash == 0);
236 print "// Automatically generated from $file using $0. DO NOT EDIT!\n";
239 my $nameEntries = "${name}Values";
240 $nameEntries =~ s/:/_/g;
242 print "\n#include \"Lookup.h\"\n" if ($includelookup);
244 print "\nnamespace ${useNameSpace} {\n";
245 print "\nusing namespace JSC;\n";
247 print "\nnamespace JSC {\n";
249 my $count = scalar @keys + 1;
250 print "#if ENABLE(JIT)\n";
251 print "#define THUNK_GENERATOR(generator) , generator\n";
253 print "#define THUNK_GENERATOR(generator)\n";
255 print "\nstatic const struct HashTableValue ${nameEntries}\[$count\] = {\n";
257 foreach my $key (@keys) {
259 my $secondValue = "";
262 if ($values[$i]{"type"} eq "Function") {
263 $castStr = "static_cast<NativeFunction>";
264 $firstValue = $values[$i]{"function"};
265 $secondValue = $values[$i]{"params"};
266 } elsif ($values[$i]{"type"} eq "Property") {
267 $castStr = "static_cast<PropertySlot::GetValueFunc>";
268 $firstValue = $values[$i]{"get"};
269 $secondValue = $values[$i]{"put"};
270 } elsif ($values[$i]{"type"} eq "Lexer") {
271 $firstValue = $values[$i]{"value"};
274 my $thunkGenerator = "0";
275 if ($key eq "charCodeAt") {
276 $thunkGenerator = "charCodeAtThunkGenerator";
278 if ($key eq "charAt") {
279 $thunkGenerator = "charAtThunkGenerator";
281 if ($key eq "sqrt") {
282 $thunkGenerator = "sqrtThunkGenerator";
285 $thunkGenerator = "powThunkGenerator";
287 print " { \"$key\", $attrs[$i], (intptr_t)" . $castStr . "($firstValue), (intptr_t)$secondValue THUNK_GENERATOR($thunkGenerator) },\n";
290 print " { 0, 0, 0, 0 THUNK_GENERATOR(0) }\n";
292 print "#undef THUNK_GENERATOR\n";
293 print "extern JSC_CONST_HASHTABLE HashTable $name =\n";
294 print " \{ $compactSize, $compactHashSizeMask, $nameEntries, 0 \};\n";
295 print "} // namespace\n";