1 /* Structure layout test generator.
2 Copyright (C) 2004-2014
3 Free Software Foundation, Inc.
4 Contributed by Jakub Jelinek <jakub@redhat.com>.
5
6 This file is part of GCC.
7
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
11 version.
12
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
21
22
23 /* Compile with gcc -o struct-layout-1_generate{,.c} generate_random{,_r}.c */
24
25 /* N.B. -- This program cannot use libiberty as that will not work
26 when testing an installed compiler. */
27 #include <limits.h>
28 #include <stdio.h>
29 #include <stdlib.h>
30 #include <string.h>
31 #include <stddef.h>
32 /* We use our own pseudo-random number generator, so that it gives the same
33 values on all hosts. */
34 #include "../../gcc.dg/compat/generate-random.h"
35
36 #if LLONG_MAX != 9223372036854775807LL && __LONG_LONG_MAX__ != 9223372036854775807LL
37 # error Need 64-bit long long
38 #endif
39
40 #if defined __MSVCRT__
41 #define COMPAT_PRLL "I64"
42 #else
43 #define COMPAT_PRLL "ll"
44 #endif
45
46 const char *dg_options[] = {
47 "/* { dg-options \"%s-I%s -Wno-abi\" } */\n",
48 "/* { dg-options \"%s-I%s -mno-mmx -Wno-abi\" { target i?86-*-* x86_64-*-* } } */\n",
49 "/* { dg-options \"%s-I%s -fno-common\" { target hppa*-*-hpux* powerpc*-*-darwin* *-*-mingw32* *-*-cygwin* } } */\n",
50 "/* { dg-options \"%s-I%s -mno-mmx -fno-common -Wno-abi\" { target i?86-*-darwin* x86_64-*-darwin* i?86-*-mingw32* x86_64-*-mingw32* i?86-*-cygwin* } } */\n",
51 "/* { dg-options \"%s-I%s -mno-base-addresses\" { target mmix-*-* } } */\n",
52 "/* { dg-options \"%s-I%s -mlongcalls -mtext-section-literals\" { target xtensa*-*-* } } */\n"
53 #define NDG_OPTIONS (sizeof (dg_options) / sizeof (dg_options[0]))
54 };
55
56 typedef unsigned int hashval_t;
57
58 enum TYPE
59 {
60 TYPE_INT,
61 TYPE_UINT,
62 TYPE_FLOAT,
63 TYPE_SENUM,
64 TYPE_UENUM,
65 TYPE_PTR,
66 TYPE_FNPTR,
67 TYPE_OTHER
68 };
69
70 struct types
71 {
72 const char *name;
73 enum TYPE type;
74 unsigned long long int maxval;
75 char bitfld;
76 };
77
78 struct types base_types[] = {
79 /* As we don't know whether char will be signed or not, just limit ourselves
80 to unsigned values less than maximum signed char value. */
81 { "char", TYPE_UINT, 127, 'C' },
82 { "signed char", TYPE_INT, 127, 'C' },
83 { "unsigned char", TYPE_UINT, 255, 'C' },
84 { "short int", TYPE_INT, 32767, 'S' },
85 { "unsigned short int", TYPE_UINT, 65535, 'S' },
86 { "int", TYPE_INT, 2147483647, 'I' },
87 { "unsigned int", TYPE_UINT, 4294967295U, 'I' },
88 { "long int", TYPE_INT, 9223372036854775807LL, 'L' },
89 { "unsigned long int", TYPE_UINT, 18446744073709551615ULL, 'L' },
90 { "long long int", TYPE_INT, 9223372036854775807LL, 'Q' },
91 { "unsigned long long int", TYPE_UINT, 18446744073709551615ULL, 'Q' },
92 { "bool", TYPE_UINT, 1, 'B' },
93 { "void *", TYPE_PTR, 0, 0 },
94 { "char *", TYPE_PTR, 0, 0 },
95 { "int *", TYPE_PTR, 0, 0 },
96 { "float", TYPE_FLOAT, 0, 0 },
97 { "double", TYPE_FLOAT, 0, 0 },
98 { "long double", TYPE_FLOAT, 0, 0 },
99 #define NTYPES1 18
100 { "Tchar", TYPE_UINT, 127, 'C' },
101 { "Tschar", TYPE_INT, 127, 'C' },
102 { "Tuchar", TYPE_UINT, 255, 'C' },
103 { "Tshort", TYPE_INT, 32767, 'S' },
104 { "Tushort", TYPE_UINT, 65535, 'S' },
105 { "Tint", TYPE_INT, 2147483647, 'I' },
106 { "Tuint", TYPE_UINT, 4294967295U, 'I' },
107 { "Tlong", TYPE_INT, 9223372036854775807LL, 'L' },
108 { "Tulong", TYPE_UINT, 18446744073709551615ULL, 'L' },
109 { "Tllong", TYPE_INT, 9223372036854775807LL, 'Q' },
110 { "Tullong", TYPE_UINT, 18446744073709551615ULL, 'Q' },
111 { "Tbool", TYPE_UINT, 1, 'B' },
112 { "size_t", TYPE_UINT, 18446744073709551615ULL, 0 },
113 { "Tptr", TYPE_PTR, 0, 0 },
114 { "Tcptr", TYPE_PTR, 0, 0 },
115 { "Tiptr", TYPE_PTR, 0, 0 },
116 { "Tfnptr", TYPE_FNPTR, 0, 0 },
117 { "Tfloat", TYPE_FLOAT, 0, 0 },
118 { "Tdouble", TYPE_FLOAT, 0, 0 },
119 { "Tldouble", TYPE_FLOAT, 0, 0 },
120 { "enum E0", TYPE_UENUM, 0, ' ' },
121 { "enum E1", TYPE_UENUM, 1, ' ' },
122 { "enum E2", TYPE_SENUM, 3, ' ' },
123 { "enum E3", TYPE_SENUM, 127, ' ' },
124 { "enum E4", TYPE_UENUM, 255, ' ' },
125 { "enum E5", TYPE_SENUM, 32767, ' ' },
126 { "enum E6", TYPE_UENUM, 65535, ' ' },
127 { "enum E7", TYPE_SENUM, 2147483647, ' ' },
128 { "enum E8", TYPE_UENUM, 4294967295U, ' ' },
129 { "enum E9", TYPE_SENUM, 1099511627775LL, ' ' },
130 { "TE0", TYPE_UENUM, 0, ' ' },
131 { "TE1", TYPE_UENUM, 1, ' ' },
132 { "TE2", TYPE_SENUM, 3, ' ' },
133 { "TE3", TYPE_SENUM, 127, ' ' },
134 { "TE4", TYPE_UENUM, 255, ' ' },
135 { "TE5", TYPE_SENUM, 32767, ' ' },
136 { "TE6", TYPE_UENUM, 65535, ' ' },
137 { "TE7", TYPE_SENUM, 2147483647, ' ' },
138 { "TE8", TYPE_UENUM, 4294967295U, ' ' },
139 { "TE9", TYPE_SENUM, 1099511627775LL, ' ' },
140 /* vector-defs.h typedefs */
141 { "qi", TYPE_INT, 127, 0 },
142 { "hi", TYPE_INT, 32767, 0 },
143 { "si", TYPE_INT, 2147483647, 0 },
144 { "di", TYPE_INT, 9223372036854775807LL, 0 },
145 { "sf", TYPE_FLOAT, 0, 0 },
146 { "df", TYPE_FLOAT, 0, 0 }
147 #define NTYPES2 (sizeof (base_types) / sizeof (base_types[0]))
148 };
149 struct types vector_types[] = {
150 /* vector-defs.h typedefs */
151 { "v8qi", TYPE_OTHER, 0, 0 },
152 { "v16qi", TYPE_OTHER, 0, 0 },
153 { "v2hi", TYPE_OTHER, 0, 0 },
154 { "v4hi", TYPE_OTHER, 0, 0 },
155 { "v8hi", TYPE_OTHER, 0, 0 },
156 { "v2si", TYPE_OTHER, 0, 0 },
157 { "v4si", TYPE_OTHER, 0, 0 },
158 { "v1di", TYPE_OTHER, 0, 0 },
159 { "v2di", TYPE_OTHER, 0, 0 },
160 { "v2sf", TYPE_OTHER, 0, 0 },
161 { "v4sf", TYPE_OTHER, 0, 0 },
162 { "v16sf", TYPE_OTHER, 0, 0 },
163 { "v2df", TYPE_OTHER, 0, 0 },
164 { "u8qi", TYPE_OTHER, 0, 0 },
165 { "u16qi", TYPE_OTHER, 0, 0 },
166 { "u2hi", TYPE_OTHER, 0, 0 },
167 { "u4hi", TYPE_OTHER, 0, 0 },
168 { "u8hi", TYPE_OTHER, 0, 0 },
169 { "u2si", TYPE_OTHER, 0, 0 },
170 { "u4si", TYPE_OTHER, 0, 0 },
171 { "u1di", TYPE_OTHER, 0, 0 },
172 { "u2di", TYPE_OTHER, 0, 0 },
173 { "u2sf", TYPE_OTHER, 0, 0 },
174 { "u4sf", TYPE_OTHER, 0, 0 },
175 { "u16sf", TYPE_OTHER, 0, 0 },
176 { "u2df", TYPE_OTHER, 0, 0 },
177 { "__m64", TYPE_OTHER, 0, 0 },
178 { "__m128", TYPE_OTHER, 0, 0 }
179 #define NVTYPES2 (sizeof (vector_types) / sizeof (vector_types[0]))
180 };
181 struct types attrib_types[] = {
182 { "Talchar", TYPE_UINT, 127, 'C' },
183 { "Talschar", TYPE_INT, 127, 'C' },
184 { "Taluchar", TYPE_UINT, 255, 'C' },
185 { "Talshort", TYPE_INT, 32767, 'S' },
186 { "Talushort", TYPE_UINT, 65535, 'S' },
187 { "Talint", TYPE_INT, 2147483647, 'I' },
188 { "Taluint", TYPE_UINT, 4294967295U, 'I' },
189 { "Tallong", TYPE_INT, 9223372036854775807LL, 'L' },
190 { "Talulong", TYPE_UINT, 18446744073709551615ULL, 'L' },
191 { "Talllong", TYPE_INT, 9223372036854775807LL, 'Q' },
192 { "Talullong", TYPE_UINT, 18446744073709551615ULL, 'Q' },
193 { "Talbool", TYPE_UINT, 1, 'B' },
194 { "Talptr", TYPE_PTR, 0, 0 },
195 { "Talcptr", TYPE_PTR, 0, 0 },
196 { "Taliptr", TYPE_PTR, 0, 0 },
197 { "Talfloat", TYPE_FLOAT, 0, 0 },
198 { "Taldouble", TYPE_FLOAT, 0, 0 },
199 { "Talldouble", TYPE_FLOAT, 0, 0 },
200 { "TalE0", TYPE_UENUM, 0, ' ' },
201 { "TalE1", TYPE_UENUM, 1, ' ' },
202 { "TalE2", TYPE_SENUM, 3, ' ' },
203 { "TalE3", TYPE_SENUM, 127, ' ' },
204 { "TalE4", TYPE_UENUM, 255, ' ' },
205 { "TalE5", TYPE_SENUM, 32767, ' ' },
206 { "TalE6", TYPE_UENUM, 65535, ' ' },
207 { "TalE7", TYPE_SENUM, 2147483647, ' ' },
208 { "TalE8", TYPE_UENUM, 4294967295U, ' ' },
209 { "TalE9", TYPE_SENUM, 1099511627775LL, ' ' },
210 { "Tal1char", TYPE_UINT, 127, 'C' },
211 { "Tal1schar", TYPE_INT, 127, 'C' },
212 { "Tal1uchar", TYPE_UINT, 255, 'C' },
213 { "Tal1short", TYPE_INT, 32767, 'S' },
214 { "Tal1ushort", TYPE_UINT, 65535, 'S' },
215 { "Tal1int", TYPE_INT, 2147483647, 'I' },
216 { "Tal1uint", TYPE_UINT, 4294967295U, 'I' },
217 { "Tal1long", TYPE_INT, 9223372036854775807LL, 'L' },
218 { "Tal1ulong", TYPE_UINT, 18446744073709551615ULL, 'L' },
219 { "Tal1llong", TYPE_INT, 9223372036854775807LL, 'Q' },
220 { "Tal1ullong", TYPE_UINT, 18446744073709551615ULL, 'Q' },
221 { "Tal1bool", TYPE_UINT, 1, 'B' },
222 { "Tal1ptr", TYPE_PTR, 0, 0 },
223 { "Tal1cptr", TYPE_PTR, 0, 0 },
224 { "Tal1iptr", TYPE_PTR, 0, 0 },
225 { "Tal1float", TYPE_FLOAT, 0, 0 },
226 { "Tal1double", TYPE_FLOAT, 0, 0 },
227 { "Tal1ldouble", TYPE_FLOAT, 0, 0 },
228 { "Tal1E0", TYPE_UENUM, 0, ' ' },
229 { "Tal1E1", TYPE_UENUM, 1, ' ' },
230 { "Tal1E2", TYPE_SENUM, 3, ' ' },
231 { "Tal1E3", TYPE_SENUM, 127, ' ' },
232 { "Tal1E4", TYPE_UENUM, 255, ' ' },
233 { "Tal1E5", TYPE_SENUM, 32767, ' ' },
234 { "Tal1E6", TYPE_UENUM, 65535, ' ' },
235 { "Tal1E7", TYPE_SENUM, 2147483647, ' ' },
236 { "Tal1E8", TYPE_UENUM, 4294967295U, ' ' },
237 { "Tal1E9", TYPE_SENUM, 1099511627775LL, ' ' },
238 { "Tal2char", TYPE_UINT, 127, 'C' },
239 { "Tal2schar", TYPE_INT, 127, 'C' },
240 { "Tal2uchar", TYPE_UINT, 255, 'C' },
241 { "Tal2short", TYPE_INT, 32767, 'S' },
242 { "Tal2ushort", TYPE_UINT, 65535, 'S' },
243 { "Tal2int", TYPE_INT, 2147483647, 'I' },
244 { "Tal2uint", TYPE_UINT, 4294967295U, 'I' },
245 { "Tal2long", TYPE_INT, 9223372036854775807LL, 'L' },
246 { "Tal2ulong", TYPE_UINT, 18446744073709551615ULL, 'L' },
247 { "Tal2llong", TYPE_INT, 9223372036854775807LL, 'Q' },
248 { "Tal2ullong", TYPE_UINT, 18446744073709551615ULL, 'Q' },
249 { "Tal2bool", TYPE_UINT, 1, 'B' },
250 { "Tal2ptr", TYPE_PTR, 0, 0 },
251 { "Tal2cptr", TYPE_PTR, 0, 0 },
252 { "Tal2iptr", TYPE_PTR, 0, 0 },
253 { "Tal2float", TYPE_FLOAT, 0, 0 },
254 { "Tal2double", TYPE_FLOAT, 0, 0 },
255 { "Tal2ldouble", TYPE_FLOAT, 0, 0 },
256 { "Tal2E0", TYPE_UENUM, 0, ' ' },
257 { "Tal2E1", TYPE_UENUM, 1, ' ' },
258 { "Tal2E2", TYPE_SENUM, 3, ' ' },
259 { "Tal2E3", TYPE_SENUM, 127, ' ' },
260 { "Tal2E4", TYPE_UENUM, 255, ' ' },
261 { "Tal2E5", TYPE_SENUM, 32767, ' ' },
262 { "Tal2E6", TYPE_UENUM, 65535, ' ' },
263 { "Tal2E7", TYPE_SENUM, 2147483647, ' ' },
264 { "Tal2E8", TYPE_UENUM, 4294967295U, ' ' },
265 { "Tal2E9", TYPE_SENUM, 1099511627775LL, ' ' },
266 { "Tal4char", TYPE_UINT, 127, 'C' },
267 { "Tal4schar", TYPE_INT, 127, 'C' },
268 { "Tal4uchar", TYPE_UINT, 255, 'C' },
269 { "Tal4short", TYPE_INT, 32767, 'S' },
270 { "Tal4ushort", TYPE_UINT, 65535, 'S' },
271 { "Tal4int", TYPE_INT, 2147483647, 'I' },
272 { "Tal4uint", TYPE_UINT, 4294967295U, 'I' },
273 { "Tal4long", TYPE_INT, 9223372036854775807LL, 'L' },
274 { "Tal4ulong", TYPE_UINT, 18446744073709551615ULL, 'L' },
275 { "Tal4llong", TYPE_INT, 9223372036854775807LL, 'Q' },
276 { "Tal4ullong", TYPE_UINT, 18446744073709551615ULL, 'Q' },
277 { "Tal4bool", TYPE_UINT, 1, 'B' },
278 { "Tal4ptr", TYPE_PTR, 0, 0 },
279 { "Tal4cptr", TYPE_PTR, 0, 0 },
280 { "Tal4iptr", TYPE_PTR, 0, 0 },
281 { "Tal4float", TYPE_FLOAT, 0, 0 },
282 { "Tal4double", TYPE_FLOAT, 0, 0 },
283 { "Tal4ldouble", TYPE_FLOAT, 0, 0 },
284 { "Tal4E0", TYPE_UENUM, 0, ' ' },
285 { "Tal4E1", TYPE_UENUM, 1, ' ' },
286 { "Tal4E2", TYPE_SENUM, 3, ' ' },
287 { "Tal4E3", TYPE_SENUM, 127, ' ' },
288 { "Tal4E4", TYPE_UENUM, 255, ' ' },
289 { "Tal4E5", TYPE_SENUM, 32767, ' ' },
290 { "Tal4E6", TYPE_UENUM, 65535, ' ' },
291 { "Tal4E7", TYPE_SENUM, 2147483647, ' ' },
292 { "Tal4E8", TYPE_UENUM, 4294967295U, ' ' },
293 { "Tal4E9", TYPE_SENUM, 1099511627775LL, ' ' },
294 { "Tal8char", TYPE_UINT, 127, 'C' },
295 { "Tal8schar", TYPE_INT, 127, 'C' },
296 { "Tal8uchar", TYPE_UINT, 255, 'C' },
297 { "Tal8short", TYPE_INT, 32767, 'S' },
298 { "Tal8ushort", TYPE_UINT, 65535, 'S' },
299 { "Tal8int", TYPE_INT, 2147483647, 'I' },
300 { "Tal8uint", TYPE_UINT, 4294967295U, 'I' },
301 { "Tal8long", TYPE_INT, 9223372036854775807LL, 'L' },
302 { "Tal8ulong", TYPE_UINT, 18446744073709551615ULL, 'L' },
303 { "Tal8llong", TYPE_INT, 9223372036854775807LL, 'Q' },
304 { "Tal8ullong", TYPE_UINT, 18446744073709551615ULL, 'Q' },
305 { "Tal8bool", TYPE_UINT, 1, 'B' },
306 { "Tal8ptr", TYPE_PTR, 0, 0 },
307 { "Tal8cptr", TYPE_PTR, 0, 0 },
308 { "Tal8iptr", TYPE_PTR, 0, 0 },
309 { "Tal8float", TYPE_FLOAT, 0, 0 },
310 { "Tal8double", TYPE_FLOAT, 0, 0 },
311 { "Tal8ldouble", TYPE_FLOAT, 0, 0 },
312 { "Tal8E0", TYPE_UENUM, 0, ' ' },
313 { "Tal8E1", TYPE_UENUM, 1, ' ' },
314 { "Tal8E2", TYPE_SENUM, 3, ' ' },
315 { "Tal8E3", TYPE_SENUM, 127, ' ' },
316 { "Tal8E4", TYPE_UENUM, 255, ' ' },
317 { "Tal8E5", TYPE_SENUM, 32767, ' ' },
318 { "Tal8E6", TYPE_UENUM, 65535, ' ' },
319 { "Tal8E7", TYPE_SENUM, 2147483647, ' ' },
320 { "Tal8E8", TYPE_UENUM, 4294967295U, ' ' },
321 { "Tal8E9", TYPE_SENUM, 1099511627775LL, ' ' },
322 { "Tal16char", TYPE_UINT, 127, 'C' },
323 { "Tal16schar", TYPE_INT, 127, 'C' },
324 { "Tal16uchar", TYPE_UINT, 255, 'C' },
325 { "Tal16short", TYPE_INT, 32767, 'S' },
326 { "Tal16ushort", TYPE_UINT, 65535, 'S' },
327 { "Tal16int", TYPE_INT, 2147483647, 'I' },
328 { "Tal16uint", TYPE_UINT, 4294967295U, 'I' },
329 { "Tal16long", TYPE_INT, 9223372036854775807LL, 'L' },
330 { "Tal16ulong", TYPE_UINT, 18446744073709551615ULL, 'L' },
331 { "Tal16llong", TYPE_INT, 9223372036854775807LL, 'Q' },
332 { "Tal16ullong", TYPE_UINT, 18446744073709551615ULL, 'Q' },
333 { "Tal16bool", TYPE_UINT, 1, 'B' },
334 { "Tal16ptr", TYPE_PTR, 0, 0 },
335 { "Tal16cptr", TYPE_PTR, 0, 0 },
336 { "Tal16iptr", TYPE_PTR, 0, 0 },
337 { "Tal16float", TYPE_FLOAT, 0, 0 },
338 { "Tal16double", TYPE_FLOAT, 0, 0 },
339 { "Tal16ldouble", TYPE_FLOAT, 0, 0 },
340 { "Tal16E0", TYPE_UENUM, 0, ' ' },
341 { "Tal16E1", TYPE_UENUM, 1, ' ' },
342 { "Tal16E2", TYPE_SENUM, 3, ' ' },
343 { "Tal16E3", TYPE_SENUM, 127, ' ' },
344 { "Tal16E4", TYPE_UENUM, 255, ' ' },
345 { "Tal16E5", TYPE_SENUM, 32767, ' ' },
346 { "Tal16E6", TYPE_UENUM, 65535, ' ' },
347 { "Tal16E7", TYPE_SENUM, 2147483647, ' ' },
348 { "Tal16E8", TYPE_UENUM, 4294967295U, ' ' },
349 { "Tal16E9", TYPE_SENUM, 1099511627775LL, ' ' }
350 #define NATYPES2 (sizeof (attrib_types) / sizeof (attrib_types[0]))
351 };
352
353 struct types bitfld_types[NTYPES2];
354 int n_bitfld_types;
355 struct types aligned_bitfld_types[NATYPES2];
356 int n_aligned_bitfld_types;
357
358 const char *attributes[] = {
359 "atal",
360 "atpa",
361 "atal1",
362 "atal2",
363 "atal4",
364 "atal8",
365 "atal16",
366 #define NATTRIBS1 7
367 "atalpa",
368 "atpaal",
369 "atal1pa",
370 "atal2pa",
371 "atal4pa",
372 "atal8pa",
373 "atal16pa",
374 "atpaal1",
375 "atpaal2",
376 "atpaal4",
377 "atpaal8",
378 "atpaal16"
379 #define NATTRIBS2 (sizeof (attributes) / sizeof (attributes[0]))
380 };
381
382 enum ETYPE
383 {
384 ETYPE_TYPE,
385 ETYPE_ARRAY,
386 ETYPE_BITFLD,
387 ETYPE_STRUCT,
388 ETYPE_UNION,
389 ETYPE_STRUCT_ARRAY,
390 ETYPE_UNION_ARRAY
391 };
392
393 struct entry
394 {
395 #ifdef __GNUC__
396 enum ETYPE etype : 8;
397 #else
398 unsigned char etype;
399 #endif
400 unsigned short len;
401 unsigned char arr_len;
402 struct types *type;
403 const char *attrib;
404 /* Used to chain together entries in the hash table. */
405 struct entry *next;
406 };
407 struct types attrib_array_types[] = {
408 { "Talx1char", TYPE_UINT, 127, 'C' },
409 { "Talx1schar", TYPE_INT, 127, 'C' },
410 { "Talx1uchar", TYPE_UINT, 255, 'C' },
411 { "Talx1short", TYPE_INT, 32767, 'S' },
412 { "Talx1ushort", TYPE_UINT, 65535, 'S' },
413 { "Talx1int", TYPE_INT, 2147483647, 'I' },
414 { "Talx1uint", TYPE_UINT, 4294967295U, 'I' },
415 { "Talx1long", TYPE_INT, 9223372036854775807LL, 'L' },
416 { "Talx1ulong", TYPE_UINT, 18446744073709551615ULL, 'L' },
417 { "Talx1llong", TYPE_INT, 9223372036854775807LL, 'Q' },
418 { "Talx1ullong", TYPE_UINT, 18446744073709551615ULL, 'Q' },
419 { "Talx1bool", TYPE_UINT, 1, 'B' },
420 { "Talx1ptr", TYPE_PTR, 0, 0 },
421 { "Talx1cptr", TYPE_PTR, 0, 0 },
422 { "Talx1iptr", TYPE_PTR, 0, 0 },
423 { "Talx1float", TYPE_FLOAT, 0, 0 },
424 { "Talx1double", TYPE_FLOAT, 0, 0 },
425 { "Talx1ldouble", TYPE_FLOAT, 0, 0 },
426 { "Talx1E0", TYPE_UENUM, 0, ' ' },
427 { "Talx1E1", TYPE_UENUM, 1, ' ' },
428 { "Talx1E2", TYPE_SENUM, 3, ' ' },
429 { "Talx1E3", TYPE_SENUM, 127, ' ' },
430 { "Talx1E4", TYPE_UENUM, 255, ' ' },
431 { "Talx1E5", TYPE_SENUM, 32767, ' ' },
432 { "Talx1E6", TYPE_UENUM, 65535, ' ' },
433 { "Talx1E7", TYPE_SENUM, 2147483647, ' ' },
434 { "Talx1E8", TYPE_UENUM, 4294967295U, ' ' },
435 { "Talx1E9", TYPE_SENUM, 1099511627775LL, ' ' },
436 { "Talx2short", TYPE_INT, 32767, 'S' },
437 { "Talx2ushort", TYPE_UINT, 65535, 'S' },
438 { "Talx2int", TYPE_INT, 2147483647, 'I' },
439 { "Talx2uint", TYPE_UINT, 4294967295U, 'I' },
440 { "Talx2long", TYPE_INT, 9223372036854775807LL, 'L' },
441 { "Talx2ulong", TYPE_UINT, 18446744073709551615ULL, 'L' },
442 { "Talx2llong", TYPE_INT, 9223372036854775807LL, 'Q' },
443 { "Talx2ullong", TYPE_UINT, 18446744073709551615ULL, 'Q' },
444 { "Talx2ptr", TYPE_PTR, 0, 0 },
445 { "Talx2cptr", TYPE_PTR, 0, 0 },
446 { "Talx2iptr", TYPE_PTR, 0, 0 },
447 { "Talx2float", TYPE_FLOAT, 0, 0 },
448 { "Talx2double", TYPE_FLOAT, 0, 0 },
449 { "Talx2ldouble", TYPE_FLOAT, 0, 0 },
450 { "Talx2E0", TYPE_UENUM, 0, ' ' },
451 { "Talx2E1", TYPE_UENUM, 1, ' ' },
452 { "Talx2E2", TYPE_SENUM, 3, ' ' },
453 { "Talx2E3", TYPE_SENUM, 127, ' ' },
454 { "Talx2E4", TYPE_UENUM, 255, ' ' },
455 { "Talx2E5", TYPE_SENUM, 32767, ' ' },
456 { "Talx2E6", TYPE_UENUM, 65535, ' ' },
457 { "Talx2E7", TYPE_SENUM, 2147483647, ' ' },
458 { "Talx2E8", TYPE_UENUM, 4294967295U, ' ' },
459 { "Talx2E9", TYPE_SENUM, 1099511627775LL, ' ' },
460 { "Talx4int", TYPE_INT, 2147483647, 'I' },
461 { "Talx4uint", TYPE_UINT, 4294967295U, 'I' },
462 { "Talx4long", TYPE_INT, 9223372036854775807LL, 'L' },
463 { "Talx4ulong", TYPE_UINT, 18446744073709551615ULL, 'L' },
464 { "Talx4llong", TYPE_INT, 9223372036854775807LL, 'Q' },
465 { "Talx4ullong", TYPE_UINT, 18446744073709551615ULL, 'Q' },
466 { "Talx4ptr", TYPE_PTR, 0, 0 },
467 { "Talx4cptr", TYPE_PTR, 0, 0 },
468 { "Talx4iptr", TYPE_PTR, 0, 0 },
469 { "Talx4float", TYPE_FLOAT, 0, 0 },
470 { "Talx4double", TYPE_FLOAT, 0, 0 },
471 { "Talx4ldouble", TYPE_FLOAT, 0, 0 },
472 { "Talx4E0", TYPE_UENUM, 0, ' ' },
473 { "Talx4E1", TYPE_UENUM, 1, ' ' },
474 { "Talx4E2", TYPE_SENUM, 3, ' ' },
475 { "Talx4E3", TYPE_SENUM, 127, ' ' },
476 { "Talx4E4", TYPE_UENUM, 255, ' ' },
477 { "Talx4E5", TYPE_SENUM, 32767, ' ' },
478 { "Talx4E6", TYPE_UENUM, 65535, ' ' },
479 { "Talx4E7", TYPE_SENUM, 2147483647, ' ' },
480 { "Talx4E8", TYPE_UENUM, 4294967295U, ' ' },
481 { "Talx4E9", TYPE_SENUM, 1099511627775LL, ' ' },
482 { "Taly8long", TYPE_INT, 9223372036854775807LL, 'L' },
483 { "Taly8ulong", TYPE_UINT, 18446744073709551615ULL, 'L' },
484 { "Talx8llong", TYPE_INT, 9223372036854775807LL, 'Q' },
485 { "Talx8ullong", TYPE_UINT, 18446744073709551615ULL, 'Q' },
486 { "Taly8ptr", TYPE_PTR, 0, 0 },
487 { "Taly8cptr", TYPE_PTR, 0, 0 },
488 { "Taly8iptr", TYPE_PTR, 0, 0 },
489 { "Talx8double", TYPE_FLOAT, 0, 0 },
490 { "Talx8ldouble", TYPE_FLOAT, 0, 0 }
491 #define NAATYPES2 (sizeof (attrib_array_types) / sizeof (attrib_array_types[0]))
492 };
493
494 /* A prime number giving the number of slots in the hash table. */
495 #define HASH_SIZE 32749
496 static struct entry *hash_table[HASH_SIZE];
497
498 /* The index of the current type being output. */
499 static int idx;
500
501 /* The maximum index of the type(s) to output. */
502 static int limidx;
503
504 /* Set to non-zero to output a single type in response to the -i option
505 (which sets LIMIDX to the index of the type to output. */
506 static int output_one;
507 static int short_enums;
508 static const char *destdir;
509 static const char *srcdir;
510 static const char *srcdir_safe;
511 FILE *outfile;
512
513 void
switchfiles(int fields)514 switchfiles (int fields)
515 {
516 static int filecnt;
517 static char *destbuf, *destptr;
518 int i;
519
520 ++filecnt;
521 if (outfile)
522 fclose (outfile);
523 if (output_one)
524 {
525 outfile = stdout;
526 return;
527 }
528 if (destbuf == NULL)
529 {
530 size_t len = strlen (destdir);
531 destbuf = malloc (len + 20);
532 if (!destbuf)
533 abort ();
534 memcpy (destbuf, destdir, len);
535 if (!len || destbuf[len - 1] != '/')
536 destbuf[len++] = '/';
537 destptr = destbuf + len;
538 }
539 sprintf (destptr, "t%03d_main.C", filecnt);
540 outfile = fopen (destbuf, "w");
541 if (outfile == NULL)
542 {
543 fail:
544 fputs ("failed to create test files\n", stderr);
545 exit (1);
546 }
547
548 for (i = 0; i < NDG_OPTIONS; i++)
549 fprintf (outfile, dg_options[i], "", srcdir_safe);
550 fprintf (outfile, "\n\
551 #include \"struct-layout-1.h\"\n\
552 \n\
553 #define TX(n, type, attrs, fields, ops) extern void test##n (void);\n\
554 #include \"t%03d_test.h\"\n\
555 #undef TX\n\
556 \n\
557 int main (void)\n\
558 {\n\
559 #define TX(n, type, attrs, fields, ops) test##n ();\n\
560 #include \"t%03d_test.h\"\n\
561 #undef TX\n\
562 if (fails)\n\
563 {\n\
564 fflush (stdout);\n\
565 abort ();\n\
566 }\n\
567 exit (0);\n\
568 }\n", filecnt, filecnt);
569 fclose (outfile);
570 sprintf (destptr, "t%03d_x.C", filecnt);
571 outfile = fopen (destbuf, "w");
572 if (outfile == NULL)
573 goto fail;
574 for (i = 0; i < NDG_OPTIONS; i++)
575 fprintf (outfile, dg_options[i], "-w ", srcdir_safe);
576 fprintf (outfile, "\n\
577 #include \"struct-layout-1_x1.h\"\n\
578 #include \"t%03d_test.h\"\n\
579 #include \"struct-layout-1_x2.h\"\n\
580 #include \"t%03d_test.h\"\n", filecnt, filecnt);
581 fclose (outfile);
582 sprintf (destptr, "t%03d_y.C", filecnt);
583 outfile = fopen (destbuf, "w");
584 if (outfile == NULL)
585 goto fail;
586 for (i = 0; i < NDG_OPTIONS; i++)
587 fprintf (outfile, dg_options[i], "-w ", srcdir_safe);
588 fprintf (outfile, "\n\
589 #include \"struct-layout-1_y1.h\"\n\
590 #include \"t%03d_test.h\"\n\
591 #include \"struct-layout-1_y2.h\"\n\
592 #include \"t%03d_test.h\"\n", filecnt, filecnt);
593 fclose (outfile);
594 sprintf (destptr, "t%03d_test.h", filecnt);
595 outfile = fopen (destbuf, "w");
596 if (outfile == NULL)
597 goto fail;
598 if (fields <= 2)
599 limidx = idx + 300;
600 else if (fields <= 4)
601 limidx = idx + 200;
602 else if (fields <= 6)
603 limidx = idx + 100;
604 else
605 limidx = idx + 50;
606 }
607
608 unsigned long long int
getrandll(void)609 getrandll (void)
610 {
611 unsigned long long int ret;
612 ret = generate_random () & 0xffffff;
613 ret |= (generate_random () & 0xffffffLL) << 24;
614 ret |= ((unsigned long long int) generate_random ()) << 48;
615 return ret;
616 }
617
618 /* Generate a subfield. The object pointed to by FLEX is set to a non-zero
619 value when the generated field is a flexible array member. When set, it
620 prevents subsequent fields from being generated (a flexible array member
621 must be the last member of the struct it's defined in). ARRAY is non-
622 zero when the enclosing structure is part of an array. In that case,
623 avoid generating a flexible array member as a subfield (such a member
624 would be invalid). */
625
626 int
subfield(struct entry * e,char * letter,int * flex,int array)627 subfield (struct entry *e, char *letter, int *flex, int array)
628 {
629 int i, type;
630 char buf[20];
631 const char *p;
632 switch (e[0].etype)
633 {
634 case ETYPE_STRUCT:
635 case ETYPE_UNION:
636 case ETYPE_STRUCT_ARRAY:
637 case ETYPE_UNION_ARRAY:
638 type = e[0].attrib ? 1 + (generate_random () & 3) : 0;
639 if (e[0].etype == ETYPE_STRUCT || e[0].etype == ETYPE_STRUCT_ARRAY)
640 p = "struct";
641 else
642 p = "union";
643 if (e[0].etype == ETYPE_STRUCT_ARRAY || e[0].etype == ETYPE_UNION_ARRAY)
644 {
645 if (e[0].arr_len == 255)
646 {
647 *flex = 1;
648 snprintf (buf, 20, "%c[]", *letter);
649 }
650 else
651 snprintf (buf, 20, "%c[%d]", *letter, e[0].arr_len);
652 /* If this is an array type, do not put aligned attributes on
653 elements. Aligning elements to a value greater than their
654 size will result in a compiler error. */
655 if (type == 1
656 && ((strncmp (e[0].attrib, "atal", 4) == 0)
657 || strncmp (e[0].attrib, "atpaal", 6) == 0))
658 type = 2;
659 }
660 else
661 {
662 buf[0] = *letter;
663 buf[1] = '\0';
664 }
665 ++*letter;
666 switch (type)
667 {
668 case 0:
669 case 3:
670 case 4:
671 fprintf (outfile, "%s{", p);
672 break;
673 case 1:
674 fprintf (outfile, "%s %s{", e[0].attrib, p);
675 break;
676 case 2:
677 fprintf (outfile, "%s %s{", p, e[0].attrib);
678 break;
679 }
680
681 for (i = 1; !*flex && i <= e[0].len; )
682 {
683 /* Avoid generating flexible array members if the enclosing
684 type is an array. */
685 int array
686 = (e[0].etype == ETYPE_STRUCT_ARRAY
687 || e[0].etype == ETYPE_UNION_ARRAY);
688 i += subfield (e + i, letter, flex, array);
689 }
690
691 switch (type)
692 {
693 case 0:
694 case 1:
695 case 2:
696 fprintf (outfile, "}%s;", buf);
697 break;
698 case 3:
699 fprintf (outfile, "}%s %s;", e[0].attrib, buf);
700 break;
701 case 4:
702 fprintf (outfile, "}%s %s;", buf, e[0].attrib);
703 break;
704 }
705 return 1 + e[0].len;
706 case ETYPE_TYPE:
707 case ETYPE_ARRAY:
708 if (e[0].etype == ETYPE_ARRAY)
709 {
710 if (!array && e[0].arr_len == 255)
711 {
712 *flex = 1;
713 snprintf (buf, 20, "%c[]", *letter);
714 }
715 else
716 snprintf (buf, 20, "%c[%d]", *letter, e[0].arr_len);
717 }
718 else
719 {
720 buf[0] = *letter;
721 buf[1] = '\0';
722 }
723 ++*letter;
724 if (e[0].attrib)
725 {
726 /* If this is an array type, do not put aligned attributes on
727 elements. Aligning elements to a value greater than their
728 size will result in a compiler error. */
729 if (e[0].etype == ETYPE_ARRAY
730 && ((strncmp (e[0].attrib, "atal", 4) == 0)
731 || strncmp (e[0].attrib, "atpaal", 6) == 0))
732 type = 2;
733 else
734 type = generate_random () % 3;
735 switch (type)
736 {
737 case 0:
738 fprintf (outfile, "%s %s %s;", e[0].attrib, e[0].type->name,
739 buf);
740 break;
741 case 1:
742 fprintf (outfile, "%s %s %s;", e[0].type->name, e[0].attrib,
743 buf);
744 break;
745 case 2:
746 fprintf (outfile, "%s %s %s;", e[0].type->name, buf,
747 e[0].attrib);
748 break;
749 }
750 }
751 else
752 fprintf (outfile, "%s %s;", e[0].type->name, buf);
753 return 1;
754 case ETYPE_BITFLD:
755 if (e[0].len == 0)
756 {
757 if (e[0].attrib)
758 switch (generate_random () % 3)
759 {
760 case 0:
761 fprintf (outfile, "%s %s:0;", e[0].attrib, e[0].type->name);
762 break;
763 case 1:
764 fprintf (outfile, "%s %s:0;", e[0].type->name, e[0].attrib);
765 break;
766 case 2:
767 fprintf (outfile, "%s:0 %s;", e[0].type->name, e[0].attrib);
768 break;
769 }
770 else
771 fprintf (outfile, "%s:0;", e[0].type->name);
772 ++*letter;
773 return 1;
774 }
775 snprintf (buf, 20, "%d", e[0].len);
776 if (e[0].attrib)
777 switch (generate_random () % 3)
778 {
779 case 0:
780 fprintf (outfile, "%s %s %c:%s;", e[0].attrib, e[0].type->name,
781 *letter, buf);
782 break;
783 case 1:
784 fprintf (outfile, "%s %s %c:%s;", e[0].type->name, e[0].attrib,
785 *letter, buf);
786 break;
787 case 2:
788 fprintf (outfile, "%s %c:%s %s;", e[0].type->name, *letter,
789 buf, e[0].attrib);
790 break;
791 }
792 else
793 fprintf (outfile, "%s %c:%s;", e[0].type->name, *letter, buf);
794 ++*letter;
795 return 1;
796 default:
797 abort ();
798 }
799 }
800
801 char namebuf[1024];
802
803 void
output_FNB(char mode,struct entry * e)804 output_FNB (char mode, struct entry *e)
805 {
806 unsigned long long int l1, l2, m;
807 int signs = 0;
808 const char *p, *q;
809
810 if (e->type->type == TYPE_OTHER)
811 {
812 if (mode == 'B')
813 abort ();
814 fprintf (outfile, "N(%d,%s)", idx, namebuf);
815 return;
816 }
817 fprintf (outfile, "%c(%d,%s,", mode, idx, namebuf);
818 l1 = getrandll ();
819 l2 = getrandll ();
820 switch (e->type->type)
821 {
822 case TYPE_INT:
823 signs = generate_random () & 3;
824 m = e->type->maxval;
825 if (mode == 'B')
826 m &= e->len > 1 ? (1ULL << (e->len - 1)) - 1 : 1;
827 l1 &= m;
828 l2 &= m;
829 fprintf (outfile, "%s%" COMPAT_PRLL "u%s,%s%" COMPAT_PRLL "u%s",
830 (signs & 1) ? "-" : "", l1, l1 > 2147483647 ? "LL" : "",
831 (signs & 2) ? "-" : "", l2, l2 > 2147483647 ? "LL" : "");
832 break;
833 case TYPE_UINT:
834 m = e->type->maxval;
835 if (mode == 'B')
836 m &= (1ULL << e->len) - 1;
837 l1 &= m;
838 l2 &= m;
839 fprintf (outfile,"%" COMPAT_PRLL "uU%s,%" COMPAT_PRLL "uU%s",
840 l1, l1 > 4294967295U ? "LL" : "",
841 l2, l2 > 4294967295U ? "LL" : "");
842 break;
843 case TYPE_FLOAT:
844 l1 &= 0xffffff;
845 l2 &= 0xffffff;
846 signs = generate_random () & 3;
847 fprintf (outfile, "%s%f,%s%f", (signs & 1) ? "-" : "",
848 ((double) l1) / 64, (signs & 2) ? "-" : "", ((double) l2) / 64);
849 break;
850 case TYPE_UENUM:
851 if (e->type->maxval == 0)
852 fputs ("e0_0,e0_0", outfile);
853 else if (e->type->maxval == 1)
854 fprintf (outfile, "e1_%" COMPAT_PRLL "d,e1_%" COMPAT_PRLL "d",
855 l1 & 1, l2 & 1);
856 else
857 {
858 p = strchr (e->type->name, '\0');
859 while (--p >= e->type->name && *p >= '0' && *p <= '9');
860 p++;
861 l1 %= 7;
862 l2 %= 7;
863 if (l1 > 3)
864 l1 += e->type->maxval - 6;
865 if (l2 > 3)
866 l2 += e->type->maxval - 6;
867 fprintf (outfile, "e%s_%" COMPAT_PRLL "d,e%s_%" COMPAT_PRLL "d",
868 p, l1, p, l2);
869 }
870 break;
871 case TYPE_SENUM:
872 p = strchr (e->type->name, '\0');
873 while (--p >= e->type->name && *p >= '0' && *p <= '9');
874 p++;
875 l1 %= 7;
876 l2 %= 7;
877 fprintf (outfile, "e%s_%s%" COMPAT_PRLL "d,e%s_%s%" COMPAT_PRLL "d",
878 p, l1 < 3 ? "m" : "",
879 l1 == 3 ? 0LL : e->type->maxval - (l1 & 3),
880 p, l2 < 3 ? "m" : "",
881 l2 == 3 ? 0LL : e->type->maxval - (l2 & 3));
882 break;
883 case TYPE_PTR:
884 l1 %= 256;
885 l2 %= 256;
886 fprintf (outfile,
887 "(%s)&intarray[%" COMPAT_PRLL "d], (%s)&intarray[%" COMPAT_PRLL "d]",
888 e->type->name, l1, e->type->name, l2);
889 break;
890 case TYPE_FNPTR:
891 l1 %= 10;
892 l2 %= 10;
893 fprintf (outfile,
894 "fn%" COMPAT_PRLL "d,fn%" COMPAT_PRLL "d", l1, l2);
895 break;
896 default:
897 abort ();
898 }
899 fputs (")", outfile);
900 }
901
902 int
subvalues(struct entry * e,char * p,char * letter)903 subvalues (struct entry *e, char *p, char *letter)
904 {
905 int i, j;
906 char *q;
907 if (p >= namebuf + sizeof (namebuf) - 32)
908 abort ();
909 p[0] = *letter;
910 p[1] = '\0';
911 q = p + 1;
912 switch (e[0].etype)
913 {
914 case ETYPE_STRUCT_ARRAY:
915 case ETYPE_UNION_ARRAY:
916 if (e[0].arr_len == 0 || e[0].arr_len == 255)
917 {
918 *letter += 1 + e[0].len;
919 return 1 + e[0].len;
920 }
921 i = generate_random () % e[0].arr_len;
922 snprintf (p, sizeof (namebuf) - (p - namebuf) - 1,
923 "%c[%d]", *letter, i);
924 q = strchr (p, '\0');
925 /* FALLTHROUGH */
926 case ETYPE_STRUCT:
927 case ETYPE_UNION:
928 *q++ = '.';
929 ++*letter;
930 for (i = 1; i <= e[0].len; )
931 {
932 i += subvalues (e + i, q, letter);
933 if (e[0].etype == ETYPE_UNION || e[0].etype == ETYPE_UNION_ARRAY)
934 {
935 *letter += e[0].len - i + 1;
936 break;
937 }
938 }
939 return 1 + e[0].len;
940 case ETYPE_TYPE:
941 ++*letter;
942 output_FNB ('F', e);
943 return 1;
944 case ETYPE_ARRAY:
945 if (e[0].arr_len == 0 || e[0].arr_len == 255)
946 {
947 ++*letter;
948 return 1;
949 }
950 i = generate_random () % e[0].arr_len;
951 snprintf (p, sizeof (namebuf) - (p - namebuf),
952 "%c[%d]", *letter, i);
953 output_FNB ('F', e);
954 if ((generate_random () & 7) == 0)
955 {
956 j = generate_random () % e[0].arr_len;
957 if (i != j)
958 {
959 snprintf (p, sizeof (namebuf) - (p - namebuf),
960 "%c[%d]", *letter, j);
961 output_FNB ('F', e);
962 }
963 }
964 ++*letter;
965 return 1;
966 case ETYPE_BITFLD:
967 ++*letter;
968 if (e[0].len != 0)
969 output_FNB ('B', e);
970 return 1;
971 }
972 }
973
974 /* DERIVED FROM:
975 --------------------------------------------------------------------
976 lookup2.c, by Bob Jenkins, December 1996, Public Domain.
977 hash(), hash2(), hash3, and mix() are externally useful functions.
978 Routines to test the hash are included if SELF_TEST is defined.
979 You can use this free for any purpose. It has no warranty.
980 --------------------------------------------------------------------
981 */
982
983 /*
984 --------------------------------------------------------------------
985 mix -- mix 3 32-bit values reversibly.
986 For every delta with one or two bit set, and the deltas of all three
987 high bits or all three low bits, whether the original value of a,b,c
988 is almost all zero or is uniformly distributed,
989 * If mix() is run forward or backward, at least 32 bits in a,b,c
990 have at least 1/4 probability of changing.
991 * If mix() is run forward, every bit of c will change between 1/3 and
992 2/3 of the time. (Well, 22/100 and 78/100 for some 2-bit deltas.)
993 mix() was built out of 36 single-cycle latency instructions in a
994 structure that could supported 2x parallelism, like so:
995 a -= b;
996 a -= c; x = (c>>13);
997 b -= c; a ^= x;
998 b -= a; x = (a<<8);
999 c -= a; b ^= x;
1000 c -= b; x = (b>>13);
1001 ...
1002 Unfortunately, superscalar Pentiums and Sparcs can't take advantage
1003 of that parallelism. They've also turned some of those single-cycle
1004 latency instructions into multi-cycle latency instructions. Still,
1005 this is the fastest good hash I could find. There were about 2^^68
1006 to choose from. I only looked at a billion or so.
1007 --------------------------------------------------------------------
1008 */
1009 /* same, but slower, works on systems that might have 8 byte hashval_t's */
1010 #define mix(a,b,c) \
1011 { \
1012 a -= b; a -= c; a ^= (c>>13); \
1013 b -= c; b -= a; b ^= (a<< 8); \
1014 c -= a; c -= b; c ^= ((b&0xffffffff)>>13); \
1015 a -= b; a -= c; a ^= ((c&0xffffffff)>>12); \
1016 b -= c; b -= a; b = (b ^ (a<<16)) & 0xffffffff; \
1017 c -= a; c -= b; c = (c ^ (b>> 5)) & 0xffffffff; \
1018 a -= b; a -= c; a = (a ^ (c>> 3)) & 0xffffffff; \
1019 b -= c; b -= a; b = (b ^ (a<<10)) & 0xffffffff; \
1020 c -= a; c -= b; c = (c ^ (b>>15)) & 0xffffffff; \
1021 }
1022
1023 /*
1024 --------------------------------------------------------------------
1025 hash() -- hash a variable-length key into a 32-bit value
1026 k : the key (the unaligned variable-length array of bytes)
1027 len : the length of the key, counting by bytes
1028 level : can be any 4-byte value
1029 Returns a 32-bit value. Every bit of the key affects every bit of
1030 the return value. Every 1-bit and 2-bit delta achieves avalanche.
1031 About 36+6len instructions.
1032
1033 The best hash table sizes are powers of 2. There is no need to do
1034 mod a prime (mod is sooo slow!). If you need less than 32 bits,
1035 use a bitmask. For example, if you need only 10 bits, do
1036 h = (h & hashmask(10));
1037 In which case, the hash table should have hashsize(10) elements.
1038
1039 If you are hashing n strings (ub1 **)k, do it like this:
1040 for (i=0, h=0; i<n; ++i) h = hash( k[i], len[i], h);
1041
1042 By Bob Jenkins, 1996. bob_jenkins@burtleburtle.net. You may use this
1043 code any way you wish, private, educational, or commercial. It's free.
1044
1045 See http://burtleburtle.net/bob/hash/evahash.html
1046 Use for hash table lookup, or anything where one collision in 2^32 is
1047 acceptable. Do NOT use for cryptographic purposes.
1048 --------------------------------------------------------------------
1049 */
1050
1051 static hashval_t
iterative_hash(const void * k_in,size_t length,hashval_t initval)1052 iterative_hash (const void *k_in /* the key */,
1053 size_t length /* the length of the key */,
1054 hashval_t initval /* the previous hash, or
1055 an arbitrary value */)
1056 {
1057 const unsigned char *k = (const unsigned char *)k_in;
1058 hashval_t a,b,c,len;
1059
1060 /* Set up the internal state */
1061 len = length;
1062 a = b = 0x9e3779b9; /* the golden ratio; an arbitrary value */
1063 c = initval; /* the previous hash value */
1064
1065 /*---------------------------------------- handle most of the key */
1066 while (len >= 12)
1067 {
1068 a += (k[0] +((hashval_t)k[1]<<8) +((hashval_t)k[2]<<16) +((hashval_t)k[3]<<24));
1069 b += (k[4] +((hashval_t)k[5]<<8) +((hashval_t)k[6]<<16) +((hashval_t)k[7]<<24));
1070 c += (k[8] +((hashval_t)k[9]<<8) +((hashval_t)k[10]<<16)+((hashval_t)k[11]<<24));
1071 mix(a,b,c);
1072 k += 12; len -= 12;
1073 }
1074
1075 /*------------------------------------- handle the last 11 bytes */
1076 c += length;
1077 switch(len) /* all the case statements fall through */
1078 {
1079 case 11: c+=((hashval_t)k[10]<<24);
1080 case 10: c+=((hashval_t)k[9]<<16);
1081 case 9 : c+=((hashval_t)k[8]<<8);
1082 /* the first byte of c is reserved for the length */
1083 case 8 : b+=((hashval_t)k[7]<<24);
1084 case 7 : b+=((hashval_t)k[6]<<16);
1085 case 6 : b+=((hashval_t)k[5]<<8);
1086 case 5 : b+=k[4];
1087 case 4 : a+=((hashval_t)k[3]<<24);
1088 case 3 : a+=((hashval_t)k[2]<<16);
1089 case 2 : a+=((hashval_t)k[1]<<8);
1090 case 1 : a+=k[0];
1091 /* case 0: nothing left to add */
1092 }
1093 mix(a,b,c);
1094 /*-------------------------------------------- report the result */
1095 return c;
1096 }
1097
1098 hashval_t
e_hash(const void * a)1099 e_hash (const void *a)
1100 {
1101 const struct entry *e = a;
1102 hashval_t ret = 0;
1103 int i;
1104
1105 if (e[0].etype != ETYPE_STRUCT && e[0].etype != ETYPE_UNION)
1106 abort ();
1107 for (i = 0; i <= e[0].len; ++i)
1108 {
1109 int attriblen;
1110 ret = iterative_hash (&e[i], offsetof (struct entry, attrib), ret);
1111 attriblen = e[i].attrib ? strlen (e[i].attrib) : -1;
1112 ret = iterative_hash (&attriblen, sizeof (int), ret);
1113 if (e[i].attrib)
1114 ret = iterative_hash (e[i].attrib, attriblen, ret);
1115 }
1116 return ret;
1117 }
1118
1119 int
e_eq(const void * a,const void * b)1120 e_eq (const void *a, const void *b)
1121 {
1122 const struct entry *ea = a, *eb = b;
1123 int i;
1124 if (ea[0].etype != ETYPE_STRUCT && ea[0].etype != ETYPE_UNION)
1125 abort ();
1126 if (ea[0].len != eb[0].len)
1127 return 0;
1128 for (i = 0; i <= ea[0].len; ++i)
1129 {
1130 if (ea[i].etype != eb[i].etype
1131 || ea[i].len != eb[i].len
1132 || ea[i].arr_len != eb[i].arr_len
1133 || ea[i].type != eb[i].type)
1134 return 0;
1135 if ((ea[i].attrib == NULL) ^ (eb[i].attrib == NULL))
1136 return 0;
1137 if (ea[i].attrib && strcmp (ea[i].attrib, eb[i].attrib) != 0)
1138 return 0;
1139 }
1140 return 1;
1141 }
1142
1143 static int
e_exists(const struct entry * e)1144 e_exists (const struct entry *e)
1145 {
1146 struct entry *h;
1147 hashval_t hval;
1148
1149 hval = e_hash (e);
1150 for (h = hash_table[hval % HASH_SIZE]; h; h = h->next)
1151 if (e_eq (e, h))
1152 return 1;
1153 return 0;
1154 }
1155
1156 static void
e_insert(struct entry * e)1157 e_insert (struct entry *e)
1158 {
1159 hashval_t hval;
1160
1161 hval = e_hash (e);
1162 e->next = hash_table[hval % HASH_SIZE];
1163 hash_table[hval % HASH_SIZE] = e;
1164 }
1165
1166 /* Output a single type. */
1167 void
output(struct entry * e)1168 output (struct entry *e)
1169 {
1170 int i;
1171 char c;
1172 struct entry *n;
1173
1174 if (e[0].etype != ETYPE_STRUCT && e[0].etype != ETYPE_UNION)
1175 abort ();
1176
1177 if (e_exists (e))
1178 return;
1179
1180 n = (struct entry *) malloc ((e[0].len + 1) * sizeof (struct entry));
1181 memcpy (n, e, (e[0].len + 1) * sizeof (struct entry));
1182 e_insert (n);
1183
1184 if (idx == limidx)
1185 switchfiles (e[0].len);
1186
1187 if (e[0].etype == ETYPE_STRUCT)
1188 fprintf (outfile, "T(%d,", idx);
1189 else
1190 fprintf (outfile, "U(%d,", idx);
1191 c = 'a';
1192
1193 int flex = 0;
1194 for (i = 1; i <= e[0].len; )
1195 i += subfield (e + i, &c, &flex, 0);
1196
1197 fputs (",", outfile);
1198 c = 'a';
1199 for (i = 1; i <= e[0].len; )
1200 {
1201 i += subvalues (e + i, namebuf, &c);
1202 if (e[0].etype == ETYPE_UNION)
1203 break;
1204 }
1205 fputs (")\n", outfile);
1206 if (output_one && idx == limidx)
1207 exit (0);
1208 ++idx;
1209 }
1210
1211 enum FEATURE
1212 {
1213 FEATURE_VECTOR = 1,
1214 FEATURE_ALIGNEDPACKED = 2,
1215 FEATURE_ZEROARRAY = 4,
1216 FEATURE_ZEROBITFLD = 8,
1217 ALL_FEATURES = FEATURE_VECTOR | FEATURE_ZEROARRAY
1218 | FEATURE_ALIGNEDPACKED | FEATURE_ZEROBITFLD
1219 };
1220
1221 void
singles(enum FEATURE features)1222 singles (enum FEATURE features)
1223 {
1224 struct entry e[2];
1225 int i;
1226 memset (e, 0, sizeof (e));
1227 e[0].etype = ETYPE_STRUCT;
1228 output (e);
1229 e[0].etype = ETYPE_UNION;
1230 output (e);
1231 e[0].len = 1;
1232 for (i = 0; i < NTYPES2; ++i)
1233 {
1234 e[0].etype = ETYPE_STRUCT;
1235 e[1].etype = ETYPE_TYPE;
1236 e[1].type = &base_types[i];
1237 output (e);
1238 e[0].etype = ETYPE_UNION;
1239 output (e);
1240 }
1241 if (features & FEATURE_VECTOR)
1242 for (i = 0; i < NVTYPES2; ++i)
1243 {
1244 e[0].etype = ETYPE_STRUCT;
1245 e[1].etype = ETYPE_TYPE;
1246 e[1].type = &vector_types[i];
1247 output (e);
1248 e[0].etype = ETYPE_UNION;
1249 output (e);
1250 }
1251 }
1252
1253 void
choose_type(enum FEATURE features,struct entry * e,int r,int in_array)1254 choose_type (enum FEATURE features, struct entry *e, int r, int in_array)
1255 {
1256 int i;
1257
1258 i = NTYPES2 - NTYPES1;
1259 if (features & FEATURE_VECTOR)
1260 i += NVTYPES2;
1261 if ((r & 3) == 0)
1262 {
1263 if (in_array)
1264 i += NAATYPES2;
1265 else
1266 i += NATYPES2;
1267 }
1268 r >>= 2;
1269 r %= i;
1270 if (r < NTYPES2 - NTYPES1)
1271 e->type = &base_types[r + NTYPES1];
1272 r -= NTYPES2 - NTYPES1;
1273 if (e->type == NULL && (features & FEATURE_VECTOR))
1274 {
1275 if (r < NVTYPES2)
1276 e->type = &vector_types[r];
1277 r -= NVTYPES2;
1278 }
1279 if (e->type == NULL && !in_array)
1280 {
1281 if (r < NATYPES2)
1282 e->type = &attrib_types[r];
1283 r -= NATYPES2;
1284 }
1285 if (e->type == NULL && in_array)
1286 {
1287 if (r < NAATYPES2)
1288 e->type = &attrib_array_types[r];
1289 r -= NAATYPES2;
1290 }
1291 if (e->type == NULL)
1292 abort ();
1293 }
1294
1295 /* This is from gcc.c-torture/execute/builtin-bitops-1.c. */
1296 static int
my_ffsll(unsigned long long x)1297 my_ffsll (unsigned long long x)
1298 {
1299 int i;
1300 if (x == 0)
1301 return 0;
1302 /* We've tested LLONG_MAX for 64 bits so this should be safe. */
1303 for (i = 0; i < 64; i++)
1304 if (x & (1ULL << i))
1305 break;
1306 return i + 1;
1307 }
1308
1309 void
generate_fields(enum FEATURE features,struct entry * e,struct entry * parent,int len)1310 generate_fields (enum FEATURE features, struct entry *e, struct entry *parent,
1311 int len)
1312 {
1313 int r, i, j, ret = 1, n, incr, sametype;
1314
1315 for (n = 0; n < len; n += incr)
1316 {
1317 r = generate_random ();
1318 /* 50% ETYPE_TYPE base_types NTYPES1
1319 12.5% ETYPE_TYPE other
1320 12.5% ETYPE_ARRAY
1321 12.5% ETYPE_BITFLD
1322 12.5% ETYPE_STRUCT|ETYPE_UNION|ETYPE_STRUCT_ARRAY|ETYPE_UNION_ARRAY */
1323 i = (r & 7);
1324 r >>= 3;
1325 incr = 1;
1326 switch (i)
1327 {
1328 case 0:
1329 case 1:
1330 case 2:
1331 case 3:
1332 e[n].etype = ETYPE_TYPE;
1333 e[n].type = &base_types[r % NTYPES1];
1334 break;
1335 case 4:
1336 e[n].etype = ETYPE_TYPE;
1337 choose_type (features, &e[n], r, 0);
1338 break;
1339 case 5:
1340 e[n].etype = ETYPE_ARRAY;
1341 i = r & 1;
1342 r >>= 1;
1343 if (i)
1344 e[n].type = &base_types[r % NTYPES1];
1345 else
1346 choose_type (features, &e[n], r, 1);
1347 r = generate_random ();
1348 if ((features & FEATURE_ZEROARRAY) && (r & 3) == 0)
1349 {
1350 e[n].arr_len = 0;
1351 if (n == len - 1 && (r & 4)
1352 && (parent->etype == ETYPE_STRUCT
1353 || parent->etype == ETYPE_STRUCT_ARRAY))
1354 {
1355 int k;
1356 for (k = 0; k < n; ++k)
1357 if (e[k].etype != ETYPE_BITFLD || e[k].len)
1358 {
1359 e[n].arr_len = 255;
1360 break;
1361 }
1362 }
1363 }
1364 else if ((r & 3) != 3)
1365 e[n].arr_len = (r >> 2) & 7;
1366 else
1367 e[n].arr_len = (r >> 2) & 31;
1368 break;
1369 case 6:
1370 sametype = 1;
1371 switch (r & 7)
1372 {
1373 case 0:
1374 case 1:
1375 case 2:
1376 break;
1377 case 3:
1378 case 4:
1379 case 5:
1380 incr = 1 + (r >> 3) % (len - n);
1381 break;
1382 case 6:
1383 case 7:
1384 sametype = 0;
1385 incr = 1 + (r >> 3) % (len - n);
1386 break;
1387 }
1388 for (j = n; j < n + incr; ++j)
1389 {
1390 int mi, ma;
1391
1392 e[j].etype = ETYPE_BITFLD;
1393 if (j == n || !sametype)
1394 {
1395 int k;
1396 r = generate_random ();
1397 k = r & 3;
1398 r >>= 2;
1399 if (!k)
1400 e[j].type
1401 = &aligned_bitfld_types[r % n_aligned_bitfld_types];
1402 else
1403 e[j].type
1404 = &bitfld_types[r % n_bitfld_types];
1405 }
1406 else
1407 e[j].type = e[n].type;
1408 r = generate_random ();
1409 mi = 0;
1410 ma = 0;
1411 switch (e[j].type->bitfld)
1412 {
1413 case 'C': ma = 8; break;
1414 case 'S': ma = 16; break;
1415 case 'I': ma = 32; break;
1416 case 'L':
1417 case 'Q': ma = 64; break;
1418 case 'B': ma = 1; break;
1419 case ' ':
1420 if (e[j].type->type == TYPE_UENUM)
1421 mi = my_ffsll (e[j].type->maxval + 1) - 1;
1422 else if (e[j].type->type == TYPE_SENUM)
1423 mi = my_ffsll (e[j].type->maxval + 1);
1424 else
1425 abort ();
1426 if (!mi)
1427 mi = 1;
1428 if (mi > 32)
1429 ma = 64;
1430 else if (mi > 16 || !short_enums)
1431 ma = 32;
1432 else if (mi > 8)
1433 ma = 16;
1434 else
1435 ma = 8;
1436 break;
1437 default:
1438 abort ();
1439 }
1440 e[j].len = ma + 1;
1441 if (sametype && (r & 3) == 0 && ma > 1)
1442 {
1443 int sum = 0, k;
1444 for (k = n; k < j; ++k)
1445 sum += e[k].len;
1446 sum %= ma;
1447 e[j].len = sum ? ma - sum : ma;
1448 }
1449 r >>= 2;
1450 if (!sametype && (r & 7) == 0)
1451 ma *= 8;
1452 r >>= 3;
1453 if (! (features & FEATURE_ZEROBITFLD) && mi == 0)
1454 mi = 1;
1455 if (e[j].len < mi || e[j].len > ma)
1456 e[j].len = mi + (r % (ma + 1 - mi));
1457 r >>= 6;
1458 if ((features & FEATURE_ZEROBITFLD) && (r & 3) == 0
1459 && mi == 0)
1460 e[j].len = 0;
1461 }
1462 break;
1463 case 7:
1464 switch (r & 7)
1465 {
1466 case 0:
1467 case 1:
1468 case 2:
1469 e[n].etype = ETYPE_STRUCT;
1470 break;
1471 case 3:
1472 case 4:
1473 e[n].etype = ETYPE_UNION;
1474 break;
1475 case 5:
1476 case 6:
1477 e[n].etype = ETYPE_STRUCT_ARRAY;
1478 break;
1479 case 7:
1480 e[n].etype = ETYPE_UNION_ARRAY;
1481 break;
1482 }
1483 r >>= 3;
1484 e[n].len = r % (len - n);
1485 incr = 1 + e[n].len;
1486 generate_fields (features, &e[n + 1], &e[n], e[n].len);
1487 if (e[n].etype == ETYPE_STRUCT_ARRAY
1488 || e[n].etype == ETYPE_UNION_ARRAY)
1489 {
1490 r = generate_random ();
1491 if ((features & FEATURE_ZEROARRAY) && (r & 3) == 0)
1492 {
1493 e[n].arr_len = 0;
1494 if (n + incr == len && (r & 4)
1495 && (parent->etype == ETYPE_STRUCT
1496 || parent->etype == ETYPE_STRUCT_ARRAY))
1497 {
1498 int k;
1499 for (k = 0; k < n; ++k)
1500 if (e[k].etype != ETYPE_BITFLD || e[k].len)
1501 {
1502 e[n].arr_len = 255;
1503 break;
1504 }
1505 }
1506 }
1507 else if ((r & 3) != 3)
1508 e[n].arr_len = (r >> 2) & 7;
1509 else
1510 e[n].arr_len = (r >> 2) & 31;
1511 }
1512 break;
1513 }
1514 r = generate_random ();
1515 if ((r & 7) == 0)
1516 {
1517 r >>= 3;
1518 i = (features & FEATURE_ALIGNEDPACKED) ? NATTRIBS2 : NATTRIBS1;
1519 e[n].attrib = attributes[r % i];
1520 if (! (features & FEATURE_ALIGNEDPACKED)
1521 && strcmp (e[n].attrib, "atpa") == 0
1522 && ((e[n].type >= &attrib_types[0]
1523 && e[n].type < &attrib_types[NATYPES2])
1524 || (e[n].type >= &attrib_array_types[0]
1525 && e[n].type < &attrib_array_types[NAATYPES2])
1526 || (e[n].type >= &aligned_bitfld_types[0]
1527 && e[n].type < &aligned_bitfld_types[n_aligned_bitfld_types])))
1528 e[n].attrib = NULL;
1529 }
1530 }
1531 }
1532
1533 void
generate_random_tests(enum FEATURE features,int len)1534 generate_random_tests (enum FEATURE features, int len)
1535 {
1536 struct entry e[len + 1];
1537 int i, r;
1538 if (len > 'z' - 'a' + 1)
1539 abort ();
1540 memset (e, 0, sizeof (e));
1541 r = generate_random ();
1542 if ((r & 7) == 0)
1543 e[0].etype = ETYPE_UNION;
1544 else
1545 e[0].etype = ETYPE_STRUCT;
1546 r >>= 3;
1547 e[0].len = len;
1548 generate_fields (features, &e[1], &e[0], len);
1549 output (e);
1550 }
1551
1552 struct { const char *name; enum FEATURE f; }
1553 features[] = {
1554 { "normal", 0 },
1555 { "vector", FEATURE_VECTOR },
1556 { "[0] :0", FEATURE_ZEROARRAY | FEATURE_ZEROBITFLD },
1557 { "vector [0]",
1558 FEATURE_VECTOR | FEATURE_ZEROARRAY },
1559 { "aligned packed vector [0] :0",
1560 FEATURE_VECTOR | FEATURE_ZEROARRAY
1561 | FEATURE_ALIGNEDPACKED | FEATURE_ZEROBITFLD },
1562 };
1563
1564 int
main(int argc,char ** argv)1565 main (int argc, char **argv)
1566 {
1567 int i, j, count, c, n = 3000;
1568 char *optarg;
1569
1570 if (sizeof (int) != 4 || sizeof (long long) != 8)
1571 return 1;
1572
1573 i = 1;
1574 while (i < argc)
1575 {
1576 c = '\0';
1577 if (argv[i][0] == '-' && argv[i][2] == '\0')
1578 c = argv[i][1];
1579 optarg = argv[i + 1];
1580 if (!optarg)
1581 goto usage;
1582 switch (c)
1583 {
1584 case 'n':
1585 n = atoi (optarg);
1586 break;
1587 case 'd':
1588 destdir = optarg;
1589 break;
1590 case 's':
1591 srcdir = optarg;
1592 break;
1593 case 'i':
1594 output_one = 1;
1595 limidx = atoi (optarg);
1596 break;
1597 case 'e':
1598 short_enums = 1;
1599 i--;
1600 break;
1601 default:
1602 fprintf (stderr, "unrecognized option %s\n", argv[i]);
1603 goto usage;
1604 }
1605 i += 2;
1606 }
1607
1608 if (output_one)
1609 {
1610 outfile = fopen ("/dev/null", "w");
1611 if (outfile == NULL)
1612 {
1613 fputs ("could not open /dev/null", stderr);
1614 return 1;
1615 }
1616 n = limidx + 1;
1617 }
1618
1619 if (destdir == NULL && !output_one)
1620 {
1621 usage:
1622 fprintf (stderr, "Usage:\n\
1623 %s [-e] [-s srcdir -d destdir] [-n count] [-i idx]\n\
1624 Either -s srcdir -d destdir or -i idx must be used\n", argv[0]);
1625 return 1;
1626 }
1627
1628 if (srcdir == NULL && !output_one)
1629 goto usage;
1630
1631 if (srcdir != NULL)
1632 {
1633 const char *s = srcdir;
1634 char *ss, *t;
1635 t = ss = malloc (strlen (srcdir) + 1);
1636 if (!ss)
1637 abort ();
1638 do {
1639 if (*s == '\\')
1640 *t++ = '/';
1641 else
1642 *t++ = *s;
1643 } while (*s++);
1644 srcdir_safe = ss;
1645 }
1646
1647 for (i = 0; i < NTYPES2; ++i)
1648 if (base_types[i].bitfld)
1649 bitfld_types[n_bitfld_types++] = base_types[i];
1650 for (i = 0; i < NATYPES2; ++i)
1651 if (attrib_types[i].bitfld)
1652 aligned_bitfld_types[n_aligned_bitfld_types++] = attrib_types[i];
1653 for (i = 0; i < sizeof (features) / sizeof (features[0]); ++i)
1654 {
1655 int startidx = idx;
1656 if (! output_one)
1657 limidx = idx;
1658 if (!i)
1659 count = 200;
1660 else
1661 count = 20;
1662 for (j = 1; j <= 9; ++j)
1663 while (idx < startidx + j * count)
1664 generate_random_tests (features[i].f, j);
1665 while (idx < startidx + count * 10)
1666 generate_random_tests (features[i].f, 10 + (generate_random () % 16));
1667 }
1668 for (i = 0; n > 3000 && i < sizeof (features) / sizeof (features[0]); ++i)
1669 {
1670 int startidx;
1671 startidx = idx;
1672 if (! output_one)
1673 limidx = idx;
1674 singles (features[i].f);
1675 if (!i)
1676 {
1677 count = 1000;
1678 while (idx < startidx + 1000)
1679 generate_random_tests (features[i].f, 1);
1680 }
1681 else
1682 {
1683 startidx = idx;
1684 count = 100;
1685 while (idx < startidx + 100)
1686 generate_random_tests (features[i].f, 1);
1687 }
1688 startidx = idx;
1689 for (j = 2; j <= 9; ++j)
1690 while (idx < startidx + (j - 1) * count)
1691 generate_random_tests (features[i].f, j);
1692 while (idx < startidx + count * 9)
1693 generate_random_tests (features[i].f, 10 + (generate_random () % 16));
1694 }
1695 if (! output_one)
1696 limidx = idx;
1697 while (idx < n)
1698 generate_random_tests (ALL_FEATURES, 1 + (generate_random () % 25));
1699 fclose (outfile);
1700 return 0;
1701 }
1702