diff options
author | David Walter Seikel | 2012-01-23 23:36:30 +1000 |
---|---|---|
committer | David Walter Seikel | 2012-01-23 23:36:30 +1000 |
commit | 6523585c66c04cea54df50013df8886b589847d8 (patch) | |
tree | 0b22aee7064166d88595eda260ca2d17c0773da5 /libraries/luajit-2.0/src/buildvm_fold.c | |
parent | Update the EFL to what I'm actually using, coz I'm using some stuff not yet r... (diff) | |
download | SledjHamr-6523585c66c04cea54df50013df8886b589847d8.zip SledjHamr-6523585c66c04cea54df50013df8886b589847d8.tar.gz SledjHamr-6523585c66c04cea54df50013df8886b589847d8.tar.bz2 SledjHamr-6523585c66c04cea54df50013df8886b589847d8.tar.xz |
Add luaproc and LuaJIT libraries.
Two versions of LuaJIT, the stable release, and the dev version. Try the dev version first, until ih fails badly.
Diffstat (limited to '')
-rw-r--r-- | libraries/luajit-2.0/src/buildvm_fold.c | 229 |
1 files changed, 229 insertions, 0 deletions
diff --git a/libraries/luajit-2.0/src/buildvm_fold.c b/libraries/luajit-2.0/src/buildvm_fold.c new file mode 100644 index 0000000..b43d2c4 --- /dev/null +++ b/libraries/luajit-2.0/src/buildvm_fold.c | |||
@@ -0,0 +1,229 @@ | |||
1 | /* | ||
2 | ** LuaJIT VM builder: IR folding hash table generator. | ||
3 | ** Copyright (C) 2005-2011 Mike Pall. See Copyright Notice in luajit.h | ||
4 | */ | ||
5 | |||
6 | #include "buildvm.h" | ||
7 | #include "lj_obj.h" | ||
8 | #include "lj_ir.h" | ||
9 | |||
10 | /* Context for the folding hash table generator. */ | ||
11 | static int lineno; | ||
12 | static int funcidx; | ||
13 | static uint32_t foldkeys[BUILD_MAX_FOLD]; | ||
14 | static uint32_t nkeys; | ||
15 | |||
16 | /* Try to fill the hash table with keys using the hash parameters. */ | ||
17 | static int tryhash(uint32_t *htab, uint32_t sz, uint32_t r, int dorol) | ||
18 | { | ||
19 | uint32_t i; | ||
20 | if (dorol && ((r & 31) == 0 || (r>>5) == 0)) | ||
21 | return 0; /* Avoid zero rotates. */ | ||
22 | memset(htab, 0xff, (sz+1)*sizeof(uint32_t)); | ||
23 | for (i = 0; i < nkeys; i++) { | ||
24 | uint32_t key = foldkeys[i]; | ||
25 | uint32_t k = key & 0xffffff; | ||
26 | uint32_t h = (dorol ? lj_rol(lj_rol(k, r>>5) - k, r&31) : | ||
27 | (((k << (r>>5)) - k) << (r&31))) % sz; | ||
28 | if (htab[h] != 0xffffffff) { /* Collision on primary slot. */ | ||
29 | if (htab[h+1] != 0xffffffff) { /* Collision on secondary slot. */ | ||
30 | /* Try to move the colliding key, if possible. */ | ||
31 | if (h < sz-1 && htab[h+2] == 0xffffffff) { | ||
32 | uint32_t k2 = htab[h+1] & 0xffffff; | ||
33 | uint32_t h2 = (dorol ? lj_rol(lj_rol(k2, r>>5) - k2, r&31) : | ||
34 | (((k2 << (r>>5)) - k2) << (r&31))) % sz; | ||
35 | if (h2 != h+1) return 0; /* Cannot resolve collision. */ | ||
36 | htab[h+2] = htab[h+1]; /* Move colliding key to secondary slot. */ | ||
37 | } else { | ||
38 | return 0; /* Collision. */ | ||
39 | } | ||
40 | } | ||
41 | htab[h+1] = key; | ||
42 | } else { | ||
43 | htab[h] = key; | ||
44 | } | ||
45 | } | ||
46 | return 1; /* Success, all keys could be stored. */ | ||
47 | } | ||
48 | |||
49 | /* Print the generated hash table. */ | ||
50 | static void printhash(BuildCtx *ctx, uint32_t *htab, uint32_t sz) | ||
51 | { | ||
52 | uint32_t i; | ||
53 | fprintf(ctx->fp, "static const uint32_t fold_hash[%d] = {\n0x%08x", | ||
54 | sz+1, htab[0]); | ||
55 | for (i = 1; i < sz+1; i++) | ||
56 | fprintf(ctx->fp, ",\n0x%08x", htab[i]); | ||
57 | fprintf(ctx->fp, "\n};\n\n"); | ||
58 | } | ||
59 | |||
60 | /* Exhaustive search for the shortest semi-perfect hash table. */ | ||
61 | static void makehash(BuildCtx *ctx) | ||
62 | { | ||
63 | uint32_t htab[BUILD_MAX_FOLD*2+1]; | ||
64 | uint32_t sz, r; | ||
65 | /* Search for the smallest hash table with an odd size. */ | ||
66 | for (sz = (nkeys|1); sz < BUILD_MAX_FOLD*2; sz += 2) { | ||
67 | /* First try all shift hash combinations. */ | ||
68 | for (r = 0; r < 32*32; r++) { | ||
69 | if (tryhash(htab, sz, r, 0)) { | ||
70 | printhash(ctx, htab, sz); | ||
71 | fprintf(ctx->fp, | ||
72 | "#define fold_hashkey(k)\t(((((k)<<%u)-(k))<<%u)%%%u)\n\n", | ||
73 | r>>5, r&31, sz); | ||
74 | return; | ||
75 | } | ||
76 | } | ||
77 | /* Then try all rotate hash combinations. */ | ||
78 | for (r = 0; r < 32*32; r++) { | ||
79 | if (tryhash(htab, sz, r, 1)) { | ||
80 | printhash(ctx, htab, sz); | ||
81 | fprintf(ctx->fp, | ||
82 | "#define fold_hashkey(k)\t(lj_rol(lj_rol((k),%u)-(k),%u)%%%u)\n\n", | ||
83 | r>>5, r&31, sz); | ||
84 | return; | ||
85 | } | ||
86 | } | ||
87 | } | ||
88 | fprintf(stderr, "Error: search for perfect hash failed\n"); | ||
89 | exit(1); | ||
90 | } | ||
91 | |||
92 | /* Parse one token of a fold rule. */ | ||
93 | static uint32_t nexttoken(char **pp, int allowlit, int allowany) | ||
94 | { | ||
95 | char *p = *pp; | ||
96 | if (p) { | ||
97 | uint32_t i; | ||
98 | char *q = strchr(p, ' '); | ||
99 | if (q) *q++ = '\0'; | ||
100 | *pp = q; | ||
101 | if (allowlit && !strncmp(p, "IRFPM_", 6)) { | ||
102 | for (i = 0; irfpm_names[i]; i++) | ||
103 | if (!strcmp(irfpm_names[i], p+6)) | ||
104 | return i; | ||
105 | } else if (allowlit && !strncmp(p, "IRFL_", 5)) { | ||
106 | for (i = 0; irfield_names[i]; i++) | ||
107 | if (!strcmp(irfield_names[i], p+5)) | ||
108 | return i; | ||
109 | } else if (allowlit && !strncmp(p, "IRCALL_", 7)) { | ||
110 | for (i = 0; ircall_names[i]; i++) | ||
111 | if (!strcmp(ircall_names[i], p+7)) | ||
112 | return i; | ||
113 | } else if (allowlit && !strncmp(p, "IRCONV_", 7)) { | ||
114 | for (i = 0; irt_names[i]; i++) { | ||
115 | const char *r = strchr(p+7, '_'); | ||
116 | if (r && !strncmp(irt_names[i], p+7, r-(p+7))) { | ||
117 | uint32_t j; | ||
118 | for (j = 0; irt_names[j]; j++) | ||
119 | if (!strcmp(irt_names[j], r+1)) | ||
120 | return (i << 5) + j; | ||
121 | } | ||
122 | } | ||
123 | } else if (allowlit && *p >= '0' && *p <= '9') { | ||
124 | for (i = 0; *p >= '0' && *p <= '9'; p++) | ||
125 | i = i*10 + (*p - '0'); | ||
126 | if (*p == '\0') | ||
127 | return i; | ||
128 | } else if (allowany && !strcmp("any", p)) { | ||
129 | return allowany; | ||
130 | } else { | ||
131 | for (i = 0; ir_names[i]; i++) | ||
132 | if (!strcmp(ir_names[i], p)) | ||
133 | return i; | ||
134 | } | ||
135 | fprintf(stderr, "Error: bad fold definition token \"%s\" at line %d\n", p, lineno); | ||
136 | exit(1); | ||
137 | } | ||
138 | return 0; | ||
139 | } | ||
140 | |||
141 | /* Parse a fold rule. */ | ||
142 | static void foldrule(char *p) | ||
143 | { | ||
144 | uint32_t op = nexttoken(&p, 0, 0); | ||
145 | uint32_t left = nexttoken(&p, 0, 0x7f); | ||
146 | uint32_t right = nexttoken(&p, 1, 0x3ff); | ||
147 | uint32_t key = (funcidx << 24) | (op << 17) | (left << 10) | right; | ||
148 | uint32_t i; | ||
149 | if (nkeys >= BUILD_MAX_FOLD) { | ||
150 | fprintf(stderr, "Error: too many fold rules, increase BUILD_MAX_FOLD.\n"); | ||
151 | exit(1); | ||
152 | } | ||
153 | /* Simple insertion sort to detect duplicates. */ | ||
154 | for (i = nkeys; i > 0; i--) { | ||
155 | if ((foldkeys[i-1]&0xffffff) < (key & 0xffffff)) | ||
156 | break; | ||
157 | if ((foldkeys[i-1]&0xffffff) == (key & 0xffffff)) { | ||
158 | fprintf(stderr, "Error: duplicate fold definition at line %d\n", lineno); | ||
159 | exit(1); | ||
160 | } | ||
161 | foldkeys[i] = foldkeys[i-1]; | ||
162 | } | ||
163 | foldkeys[i] = key; | ||
164 | nkeys++; | ||
165 | } | ||
166 | |||
167 | /* Emit C source code for IR folding hash table. */ | ||
168 | void emit_fold(BuildCtx *ctx) | ||
169 | { | ||
170 | char buf[256]; /* We don't care about analyzing lines longer than that. */ | ||
171 | const char *fname = ctx->args[0]; | ||
172 | FILE *fp; | ||
173 | |||
174 | if (fname == NULL) { | ||
175 | fprintf(stderr, "Error: missing input filename\n"); | ||
176 | exit(1); | ||
177 | } | ||
178 | |||
179 | if (fname[0] == '-' && fname[1] == '\0') { | ||
180 | fp = stdin; | ||
181 | } else { | ||
182 | fp = fopen(fname, "r"); | ||
183 | if (!fp) { | ||
184 | fprintf(stderr, "Error: cannot open input file '%s': %s\n", | ||
185 | fname, strerror(errno)); | ||
186 | exit(1); | ||
187 | } | ||
188 | } | ||
189 | |||
190 | fprintf(ctx->fp, "/* This is a generated file. DO NOT EDIT! */\n\n"); | ||
191 | fprintf(ctx->fp, "static const FoldFunc fold_func[] = {\n"); | ||
192 | |||
193 | lineno = 0; | ||
194 | funcidx = 0; | ||
195 | nkeys = 0; | ||
196 | while (fgets(buf, sizeof(buf), fp) != NULL) { | ||
197 | lineno++; | ||
198 | /* The prefix must be at the start of a line, otherwise it's ignored. */ | ||
199 | if (!strncmp(buf, FOLDDEF_PREFIX, sizeof(FOLDDEF_PREFIX)-1)) { | ||
200 | char *p = buf+sizeof(FOLDDEF_PREFIX)-1; | ||
201 | char *q = strchr(p, ')'); | ||
202 | if (p[0] == '(' && q) { | ||
203 | p++; | ||
204 | *q = '\0'; | ||
205 | foldrule(p); | ||
206 | } else if ((p[0] == 'F' || p[0] == 'X') && p[1] == '(' && q) { | ||
207 | p += 2; | ||
208 | *q = '\0'; | ||
209 | if (funcidx) | ||
210 | fprintf(ctx->fp, ",\n"); | ||
211 | if (p[-2] == 'X') | ||
212 | fprintf(ctx->fp, " %s", p); | ||
213 | else | ||
214 | fprintf(ctx->fp, " fold_%s", p); | ||
215 | funcidx++; | ||
216 | } else { | ||
217 | buf[strlen(buf)-1] = '\0'; | ||
218 | fprintf(stderr, "Error: unknown fold definition tag %s%s at line %d\n", | ||
219 | FOLDDEF_PREFIX, p, lineno); | ||
220 | exit(1); | ||
221 | } | ||
222 | } | ||
223 | } | ||
224 | fclose(fp); | ||
225 | fprintf(ctx->fp, "\n};\n\n"); | ||
226 | |||
227 | makehash(ctx); | ||
228 | } | ||
229 | |||