create_hash_table 9.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306
  1. #! /usr/bin/perl -w
  2. #
  3. # Static Hashtable Generator
  4. #
  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.
  9. #
  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.
  14. #
  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.
  19. #
  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
  23. #
  24. use strict;
  25. my $file = $ARGV[0];
  26. shift;
  27. my $includelookup = 0;
  28. # Use -i as second argument to make it include "Lookup.h"
  29. $includelookup = 1 if (defined($ARGV[0]) && $ARGV[0] eq "-i");
  30. # Use -n as second argument to make it use the third argument as namespace parameter ie. -n KDOM
  31. my $useNameSpace = $ARGV[1] if (defined($ARGV[0]) && $ARGV[0] eq "-n");
  32. print STDERR "Creating hashtable for $file\n";
  33. open(IN, $file) or die "No such file $file";
  34. my @keys = ();
  35. my @attrs = ();
  36. my @values = ();
  37. my @hashes = ();
  38. my $inside = 0;
  39. my $name;
  40. my $pefectHashSize;
  41. my $compactSize;
  42. my $compactHashSizeMask;
  43. my $banner = 0;
  44. sub calcPerfectHashSize();
  45. sub calcCompactHashSize();
  46. sub output();
  47. sub jsc_ucfirst($);
  48. sub hashValue($);
  49. while (<IN>) {
  50. chomp;
  51. s/^\s+//;
  52. next if /^\#|^$/; # Comment or blank line. Do nothing.
  53. if (/^\@begin/ && !$inside) {
  54. if (/^\@begin\s*([:_\w]+)\s*\d*\s*$/) {
  55. $inside = 1;
  56. $name = $1;
  57. } else {
  58. print STDERR "WARNING: \@begin without table name, skipping $_\n";
  59. }
  60. } elsif (/^\@end\s*$/ && $inside) {
  61. calcPerfectHashSize();
  62. calcCompactHashSize();
  63. output();
  64. @keys = ();
  65. @attrs = ();
  66. @values = ();
  67. @hashes = ();
  68. $inside = 0;
  69. } elsif (/^(\S+)\s*(\S+)\s*([\w\|]*)\s*(\w*)\s*$/ && $inside) {
  70. my $key = $1;
  71. my $val = $2;
  72. my $att = $3;
  73. my $param = $4;
  74. push(@keys, $key);
  75. push(@attrs, length($att) > 0 ? $att : "0");
  76. if ($att =~ m/Function/) {
  77. push(@values, { "type" => "Function", "function" => $val, "params" => (length($param) ? $param : "") });
  78. #printf STDERR "WARNING: Number of arguments missing for $key/$val\n" if (length($param) == 0);
  79. } elsif (length($att)) {
  80. my $get = $val;
  81. my $put = !($att =~ m/ReadOnly/) ? "set" . jsc_ucfirst($val) : "0";
  82. push(@values, { "type" => "Property", "get" => $get, "put" => $put });
  83. } else {
  84. push(@values, { "type" => "Lexer", "value" => $val });
  85. }
  86. push(@hashes, hashValue($key));
  87. } elsif ($inside) {
  88. die "invalid data {" . $_ . "}";
  89. }
  90. }
  91. die "missing closing \@end" if ($inside);
  92. sub jsc_ucfirst($)
  93. {
  94. my ($value) = @_;
  95. if ($value =~ /js/) {
  96. $value =~ s/js/JS/;
  97. return $value;
  98. }
  99. return ucfirst($value);
  100. }
  101. sub ceilingToPowerOf2
  102. {
  103. my ($pefectHashSize) = @_;
  104. my $powerOf2 = 1;
  105. while ($pefectHashSize > $powerOf2) {
  106. $powerOf2 <<= 1;
  107. }
  108. return $powerOf2;
  109. }
  110. sub calcPerfectHashSize()
  111. {
  112. tableSizeLoop:
  113. for ($pefectHashSize = ceilingToPowerOf2(scalar @keys); ; $pefectHashSize += $pefectHashSize) {
  114. my @table = ();
  115. foreach my $key (@keys) {
  116. my $h = hashValue($key) % $pefectHashSize;
  117. next tableSizeLoop if $table[$h];
  118. $table[$h] = 1;
  119. }
  120. last;
  121. }
  122. }
  123. sub leftShift($$) {
  124. my ($value, $distance) = @_;
  125. return (($value << $distance) & 0xFFFFFFFF);
  126. }
  127. sub calcCompactHashSize()
  128. {
  129. my @table = ();
  130. my @links = ();
  131. my $compactHashSize = ceilingToPowerOf2(2 * @keys);
  132. $compactHashSizeMask = $compactHashSize - 1;
  133. $compactSize = $compactHashSize;
  134. my $collisions = 0;
  135. my $maxdepth = 0;
  136. my $i = 0;
  137. foreach my $key (@keys) {
  138. my $depth = 0;
  139. my $h = hashValue($key) % $compactHashSize;
  140. while (defined($table[$h])) {
  141. if (defined($links[$h])) {
  142. $h = $links[$h];
  143. $depth++;
  144. } else {
  145. $collisions++;
  146. $links[$h] = $compactSize;
  147. $h = $compactSize;
  148. $compactSize++;
  149. }
  150. }
  151. $table[$h] = $i;
  152. $i++;
  153. $maxdepth = $depth if ( $depth > $maxdepth);
  154. }
  155. }
  156. # Paul Hsieh's SuperFastHash
  157. # http://www.azillionmonkeys.com/qed/hash.html
  158. sub hashValue($) {
  159. my @chars = split(/ */, $_[0]);
  160. # This hash is designed to work on 16-bit chunks at a time. But since the normal case
  161. # (above) is to hash UTF-16 characters, we just treat the 8-bit chars as if they
  162. # were 16-bit chunks, which should give matching results
  163. my $EXP2_32 = 4294967296;
  164. my $hash = 0x9e3779b9;
  165. my $l = scalar @chars; #I wish this was in Ruby --- Maks
  166. my $rem = $l & 1;
  167. $l = $l >> 1;
  168. my $s = 0;
  169. # Main loop
  170. for (; $l > 0; $l--) {
  171. $hash += ord($chars[$s]);
  172. my $tmp = leftShift(ord($chars[$s+1]), 11) ^ $hash;
  173. $hash = (leftShift($hash, 16)% $EXP2_32) ^ $tmp;
  174. $s += 2;
  175. $hash += $hash >> 11;
  176. $hash %= $EXP2_32;
  177. }
  178. # Handle end case
  179. if ($rem != 0) {
  180. $hash += ord($chars[$s]);
  181. $hash ^= (leftShift($hash, 11)% $EXP2_32);
  182. $hash += $hash >> 17;
  183. }
  184. # Force "avalanching" of final 127 bits
  185. $hash ^= leftShift($hash, 3);
  186. $hash += ($hash >> 5);
  187. $hash = ($hash% $EXP2_32);
  188. $hash ^= (leftShift($hash, 2)% $EXP2_32);
  189. $hash += ($hash >> 15);
  190. $hash = $hash% $EXP2_32;
  191. $hash ^= (leftShift($hash, 10)% $EXP2_32);
  192. # Save 8 bits for StringImpl to use as flags.
  193. $hash &= 0xffffff;
  194. # This avoids ever returning a hash code of 0, since that is used to
  195. # signal "hash not computed yet". Setting the high bit maintains
  196. # reasonable fidelity to a hash code of 0 because it is likely to yield
  197. # exactly 0 when hash lookup masks out the high bits.
  198. $hash = (0x80000000 >> 8) if ($hash == 0);
  199. return $hash;
  200. }
  201. sub output() {
  202. if (!$banner) {
  203. $banner = 1;
  204. print "// Automatically generated from $file using $0. DO NOT EDIT!\n";
  205. }
  206. my $nameEntries = "${name}Values";
  207. $nameEntries =~ s/:/_/g;
  208. print "\n#include \"Lookup.h\"\n" if ($includelookup);
  209. if ($useNameSpace) {
  210. print "\nnamespace ${useNameSpace} {\n";
  211. print "\nusing namespace JSC;\n";
  212. } else {
  213. print "\nnamespace JSC {\n";
  214. }
  215. my $count = scalar @keys + 1;
  216. print "\nstatic const struct HashTableValue ${nameEntries}\[$count\] = {\n";
  217. my $i = 0;
  218. foreach my $key (@keys) {
  219. my $firstValue = "";
  220. my $secondValue = "";
  221. my $castStr = "";
  222. if ($values[$i]{"type"} eq "Function") {
  223. $castStr = "static_cast<NativeFunction>";
  224. $firstValue = $values[$i]{"function"};
  225. $secondValue = $values[$i]{"params"};
  226. } elsif ($values[$i]{"type"} eq "Property") {
  227. $castStr = "static_cast<PropertySlot::GetValueFunc>";
  228. $firstValue = $values[$i]{"get"};
  229. $secondValue = $values[$i]{"put"};
  230. } elsif ($values[$i]{"type"} eq "Lexer") {
  231. $firstValue = $values[$i]{"value"};
  232. $secondValue = "0";
  233. }
  234. my $intrinsic = "NoIntrinsic";
  235. $intrinsic = "FromCharCodeIntrinsic" if ($key eq "fromCharCode");
  236. if ($name eq "mathTable") {
  237. $intrinsic = "MinIntrinsic" if ($key eq "min");
  238. $intrinsic = "MaxIntrinsic" if ($key eq "max");
  239. $intrinsic = "SqrtIntrinsic" if ($key eq "sqrt");
  240. $intrinsic = "PowIntrinsic" if ($key eq "pow");
  241. $intrinsic = "AbsIntrinsic" if ($key eq "abs");
  242. $intrinsic = "FloorIntrinsic" if ($key eq "floor");
  243. $intrinsic = "CeilIntrinsic" if ($key eq "ceil");
  244. $intrinsic = "RoundIntrinsic" if ($key eq "round");
  245. $intrinsic = "ExpIntrinsic" if ($key eq "exp");
  246. $intrinsic = "LogIntrinsic" if ($key eq "log");
  247. $intrinsic = "IMulIntrinsic" if ($key eq "imul");
  248. }
  249. if ($name eq "arrayPrototypeTable") {
  250. $intrinsic = "ArrayPushIntrinsic" if ($key eq "push");
  251. $intrinsic = "ArrayPopIntrinsic" if ($key eq "pop");
  252. }
  253. if ($name eq "regExpPrototypeTable") {
  254. $intrinsic = "RegExpExecIntrinsic" if ($key eq "exec");
  255. $intrinsic = "RegExpTestIntrinsic" if ($key eq "test");
  256. }
  257. print " { \"$key\", $attrs[$i], (intptr_t)" . $castStr . "($firstValue), (intptr_t)$secondValue, $intrinsic },\n";
  258. $i++;
  259. }
  260. print " { 0, 0, 0, 0, NoIntrinsic }\n";
  261. print "};\n\n";
  262. print "extern const struct HashTable $name =\n";
  263. print " \{ $compactSize, $compactHashSizeMask, $nameEntries, 0 \};\n";
  264. print "} // namespace\n";
  265. }