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 default:
972 return 0;
973 }
974 }
975
976 /* DERIVED FROM:
977 --------------------------------------------------------------------
978 lookup2.c, by Bob Jenkins, December 1996, Public Domain.
979 hash(), hash2(), hash3, and mix() are externally useful functions.
980 Routines to test the hash are included if SELF_TEST is defined.
981 You can use this free for any purpose. It has no warranty.
982 --------------------------------------------------------------------
983 */
984
985 /*
986 --------------------------------------------------------------------
987 mix -- mix 3 32-bit values reversibly.
988 For every delta with one or two bit set, and the deltas of all three
989 high bits or all three low bits, whether the original value of a,b,c
990 is almost all zero or is uniformly distributed,
991 * If mix() is run forward or backward, at least 32 bits in a,b,c
992 have at least 1/4 probability of changing.
993 * If mix() is run forward, every bit of c will change between 1/3 and
994 2/3 of the time. (Well, 22/100 and 78/100 for some 2-bit deltas.)
995 mix() was built out of 36 single-cycle latency instructions in a
996 structure that could supported 2x parallelism, like so:
997 a -= b;
998 a -= c; x = (c>>13);
999 b -= c; a ^= x;
1000 b -= a; x = (a<<8);
1001 c -= a; b ^= x;
1002 c -= b; x = (b>>13);
1003 ...
1004 Unfortunately, superscalar Pentiums and Sparcs can't take advantage
1005 of that parallelism. They've also turned some of those single-cycle
1006 latency instructions into multi-cycle latency instructions. Still,
1007 this is the fastest good hash I could find. There were about 2^^68
1008 to choose from. I only looked at a billion or so.
1009 --------------------------------------------------------------------
1010 */
1011 /* same, but slower, works on systems that might have 8 byte hashval_t's */
1012 #define mix(a,b,c) \
1013 { \
1014 a -= b; a -= c; a ^= (c>>13); \
1015 b -= c; b -= a; b ^= (a<< 8); \
1016 c -= a; c -= b; c ^= ((b&0xffffffff)>>13); \
1017 a -= b; a -= c; a ^= ((c&0xffffffff)>>12); \
1018 b -= c; b -= a; b = (b ^ (a<<16)) & 0xffffffff; \
1019 c -= a; c -= b; c = (c ^ (b>> 5)) & 0xffffffff; \
1020 a -= b; a -= c; a = (a ^ (c>> 3)) & 0xffffffff; \
1021 b -= c; b -= a; b = (b ^ (a<<10)) & 0xffffffff; \
1022 c -= a; c -= b; c = (c ^ (b>>15)) & 0xffffffff; \
1023 }
1024
1025 /*
1026 --------------------------------------------------------------------
1027 hash() -- hash a variable-length key into a 32-bit value
1028 k : the key (the unaligned variable-length array of bytes)
1029 len : the length of the key, counting by bytes
1030 level : can be any 4-byte value
1031 Returns a 32-bit value. Every bit of the key affects every bit of
1032 the return value. Every 1-bit and 2-bit delta achieves avalanche.
1033 About 36+6len instructions.
1034
1035 The best hash table sizes are powers of 2. There is no need to do
1036 mod a prime (mod is sooo slow!). If you need less than 32 bits,
1037 use a bitmask. For example, if you need only 10 bits, do
1038 h = (h & hashmask(10));
1039 In which case, the hash table should have hashsize(10) elements.
1040
1041 If you are hashing n strings (ub1 **)k, do it like this:
1042 for (i=0, h=0; i<n; ++i) h = hash( k[i], len[i], h);
1043
1044 By Bob Jenkins, 1996. bob_jenkins@burtleburtle.net. You may use this
1045 code any way you wish, private, educational, or commercial. It's free.
1046
1047 See http://burtleburtle.net/bob/hash/evahash.html
1048 Use for hash table lookup, or anything where one collision in 2^32 is
1049 acceptable. Do NOT use for cryptographic purposes.
1050 --------------------------------------------------------------------
1051 */
1052
1053 static hashval_t
iterative_hash(const void * k_in,size_t length,hashval_t initval)1054 iterative_hash (const void *k_in /* the key */,
1055 size_t length /* the length of the key */,
1056 hashval_t initval /* the previous hash, or
1057 an arbitrary value */)
1058 {
1059 const unsigned char *k = (const unsigned char *)k_in;
1060 hashval_t a,b,c,len;
1061
1062 /* Set up the internal state */
1063 len = length;
1064 a = b = 0x9e3779b9; /* the golden ratio; an arbitrary value */
1065 c = initval; /* the previous hash value */
1066
1067 /*---------------------------------------- handle most of the key */
1068 while (len >= 12)
1069 {
1070 a += (k[0] +((hashval_t)k[1]<<8) +((hashval_t)k[2]<<16) +((hashval_t)k[3]<<24));
1071 b += (k[4] +((hashval_t)k[5]<<8) +((hashval_t)k[6]<<16) +((hashval_t)k[7]<<24));
1072 c += (k[8] +((hashval_t)k[9]<<8) +((hashval_t)k[10]<<16)+((hashval_t)k[11]<<24));
1073 mix(a,b,c);
1074 k += 12; len -= 12;
1075 }
1076
1077 /*------------------------------------- handle the last 11 bytes */
1078 c += length;
1079 switch(len) /* all the case statements fall through */
1080 {
1081 case 11: c+=((hashval_t)k[10]<<24);
1082 case 10: c+=((hashval_t)k[9]<<16);
1083 case 9 : c+=((hashval_t)k[8]<<8);
1084 /* the first byte of c is reserved for the length */
1085 case 8 : b+=((hashval_t)k[7]<<24);
1086 case 7 : b+=((hashval_t)k[6]<<16);
1087 case 6 : b+=((hashval_t)k[5]<<8);
1088 case 5 : b+=k[4];
1089 case 4 : a+=((hashval_t)k[3]<<24);
1090 case 3 : a+=((hashval_t)k[2]<<16);
1091 case 2 : a+=((hashval_t)k[1]<<8);
1092 case 1 : a+=k[0];
1093 /* case 0: nothing left to add */
1094 }
1095 mix(a,b,c);
1096 /*-------------------------------------------- report the result */
1097 return c;
1098 }
1099
1100 hashval_t
e_hash(const void * a)1101 e_hash (const void *a)
1102 {
1103 const struct entry *e = a;
1104 hashval_t ret = 0;
1105 int i;
1106
1107 if (e[0].etype != ETYPE_STRUCT && e[0].etype != ETYPE_UNION)
1108 abort ();
1109 for (i = 0; i <= e[0].len; ++i)
1110 {
1111 int attriblen;
1112 ret = iterative_hash (&e[i], offsetof (struct entry, attrib), ret);
1113 attriblen = e[i].attrib ? strlen (e[i].attrib) : -1;
1114 ret = iterative_hash (&attriblen, sizeof (int), ret);
1115 if (e[i].attrib)
1116 ret = iterative_hash (e[i].attrib, attriblen, ret);
1117 }
1118 return ret;
1119 }
1120
1121 int
e_eq(const void * a,const void * b)1122 e_eq (const void *a, const void *b)
1123 {
1124 const struct entry *ea = a, *eb = b;
1125 int i;
1126 if (ea[0].etype != ETYPE_STRUCT && ea[0].etype != ETYPE_UNION)
1127 abort ();
1128 if (ea[0].len != eb[0].len)
1129 return 0;
1130 for (i = 0; i <= ea[0].len; ++i)
1131 {
1132 if (ea[i].etype != eb[i].etype
1133 || ea[i].len != eb[i].len
1134 || ea[i].arr_len != eb[i].arr_len
1135 || ea[i].type != eb[i].type)
1136 return 0;
1137 if ((ea[i].attrib == NULL) ^ (eb[i].attrib == NULL))
1138 return 0;
1139 if (ea[i].attrib && strcmp (ea[i].attrib, eb[i].attrib) != 0)
1140 return 0;
1141 }
1142 return 1;
1143 }
1144
1145 static int
e_exists(const struct entry * e)1146 e_exists (const struct entry *e)
1147 {
1148 struct entry *h;
1149 hashval_t hval;
1150
1151 hval = e_hash (e);
1152 for (h = hash_table[hval % HASH_SIZE]; h; h = h->next)
1153 if (e_eq (e, h))
1154 return 1;
1155 return 0;
1156 }
1157
1158 static void
e_insert(struct entry * e)1159 e_insert (struct entry *e)
1160 {
1161 hashval_t hval;
1162
1163 hval = e_hash (e);
1164 e->next = hash_table[hval % HASH_SIZE];
1165 hash_table[hval % HASH_SIZE] = e;
1166 }
1167
1168 /* Output a single type. */
1169 void
output(struct entry * e)1170 output (struct entry *e)
1171 {
1172 int i;
1173 char c;
1174 struct entry *n;
1175
1176 if (e[0].etype != ETYPE_STRUCT && e[0].etype != ETYPE_UNION)
1177 abort ();
1178
1179 if (e_exists (e))
1180 return;
1181
1182 n = (struct entry *) malloc ((e[0].len + 1) * sizeof (struct entry));
1183 memcpy (n, e, (e[0].len + 1) * sizeof (struct entry));
1184 e_insert (n);
1185
1186 if (idx == limidx)
1187 switchfiles (e[0].len);
1188
1189 if (e[0].etype == ETYPE_STRUCT)
1190 fprintf (outfile, "T(%d,", idx);
1191 else
1192 fprintf (outfile, "U(%d,", idx);
1193 c = 'a';
1194
1195 int flex = 0;
1196 for (i = 1; i <= e[0].len; )
1197 i += subfield (e + i, &c, &flex, 0);
1198
1199 fputs (",", outfile);
1200 c = 'a';
1201 for (i = 1; i <= e[0].len; )
1202 {
1203 i += subvalues (e + i, namebuf, &c);
1204 if (e[0].etype == ETYPE_UNION)
1205 break;
1206 }
1207 fputs (")\n", outfile);
1208 if (output_one && idx == limidx)
1209 exit (0);
1210 ++idx;
1211 }
1212
1213 enum FEATURE
1214 {
1215 FEATURE_VECTOR = 1,
1216 FEATURE_ALIGNEDPACKED = 2,
1217 FEATURE_ZEROARRAY = 4,
1218 FEATURE_ZEROBITFLD = 8,
1219 ALL_FEATURES = FEATURE_VECTOR | FEATURE_ZEROARRAY
1220 | FEATURE_ALIGNEDPACKED | FEATURE_ZEROBITFLD
1221 };
1222
1223 void
singles(enum FEATURE features)1224 singles (enum FEATURE features)
1225 {
1226 struct entry e[2];
1227 int i;
1228 memset (e, 0, sizeof (e));
1229 e[0].etype = ETYPE_STRUCT;
1230 output (e);
1231 e[0].etype = ETYPE_UNION;
1232 output (e);
1233 e[0].len = 1;
1234 for (i = 0; i < NTYPES2; ++i)
1235 {
1236 e[0].etype = ETYPE_STRUCT;
1237 e[1].etype = ETYPE_TYPE;
1238 e[1].type = &base_types[i];
1239 output (e);
1240 e[0].etype = ETYPE_UNION;
1241 output (e);
1242 }
1243 if (features & FEATURE_VECTOR)
1244 for (i = 0; i < NVTYPES2; ++i)
1245 {
1246 e[0].etype = ETYPE_STRUCT;
1247 e[1].etype = ETYPE_TYPE;
1248 e[1].type = &vector_types[i];
1249 output (e);
1250 e[0].etype = ETYPE_UNION;
1251 output (e);
1252 }
1253 }
1254
1255 void
choose_type(enum FEATURE features,struct entry * e,int r,int in_array)1256 choose_type (enum FEATURE features, struct entry *e, int r, int in_array)
1257 {
1258 int i;
1259
1260 i = NTYPES2 - NTYPES1;
1261 if (features & FEATURE_VECTOR)
1262 i += NVTYPES2;
1263 if ((r & 3) == 0)
1264 {
1265 if (in_array)
1266 i += NAATYPES2;
1267 else
1268 i += NATYPES2;
1269 }
1270 r >>= 2;
1271 r %= i;
1272 if (r < NTYPES2 - NTYPES1)
1273 e->type = &base_types[r + NTYPES1];
1274 r -= NTYPES2 - NTYPES1;
1275 if (e->type == NULL && (features & FEATURE_VECTOR))
1276 {
1277 if (r < NVTYPES2)
1278 e->type = &vector_types[r];
1279 r -= NVTYPES2;
1280 }
1281 if (e->type == NULL && !in_array)
1282 {
1283 if (r < NATYPES2)
1284 e->type = &attrib_types[r];
1285 r -= NATYPES2;
1286 }
1287 if (e->type == NULL && in_array)
1288 {
1289 if (r < NAATYPES2)
1290 e->type = &attrib_array_types[r];
1291 r -= NAATYPES2;
1292 }
1293 if (e->type == NULL)
1294 abort ();
1295 }
1296
1297 /* This is from gcc.c-torture/execute/builtin-bitops-1.c. */
1298 static int
my_ffsll(unsigned long long x)1299 my_ffsll (unsigned long long x)
1300 {
1301 int i;
1302 if (x == 0)
1303 return 0;
1304 /* We've tested LLONG_MAX for 64 bits so this should be safe. */
1305 for (i = 0; i < 64; i++)
1306 if (x & (1ULL << i))
1307 break;
1308 return i + 1;
1309 }
1310
1311 void
generate_fields(enum FEATURE features,struct entry * e,struct entry * parent,int len)1312 generate_fields (enum FEATURE features, struct entry *e, struct entry *parent,
1313 int len)
1314 {
1315 int r, i, j, ret = 1, n, incr, sametype;
1316
1317 for (n = 0; n < len; n += incr)
1318 {
1319 r = generate_random ();
1320 /* 50% ETYPE_TYPE base_types NTYPES1
1321 12.5% ETYPE_TYPE other
1322 12.5% ETYPE_ARRAY
1323 12.5% ETYPE_BITFLD
1324 12.5% ETYPE_STRUCT|ETYPE_UNION|ETYPE_STRUCT_ARRAY|ETYPE_UNION_ARRAY */
1325 i = (r & 7);
1326 r >>= 3;
1327 incr = 1;
1328 switch (i)
1329 {
1330 case 0:
1331 case 1:
1332 case 2:
1333 case 3:
1334 e[n].etype = ETYPE_TYPE;
1335 e[n].type = &base_types[r % NTYPES1];
1336 break;
1337 case 4:
1338 e[n].etype = ETYPE_TYPE;
1339 choose_type (features, &e[n], r, 0);
1340 break;
1341 case 5:
1342 e[n].etype = ETYPE_ARRAY;
1343 i = r & 1;
1344 r >>= 1;
1345 if (i)
1346 e[n].type = &base_types[r % NTYPES1];
1347 else
1348 choose_type (features, &e[n], r, 1);
1349 r = generate_random ();
1350 if ((features & FEATURE_ZEROARRAY) && (r & 3) == 0)
1351 {
1352 e[n].arr_len = 0;
1353 if (n == len - 1 && (r & 4)
1354 && (parent->etype == ETYPE_STRUCT
1355 || parent->etype == ETYPE_STRUCT_ARRAY))
1356 {
1357 int k;
1358 for (k = 0; k < n; ++k)
1359 if (e[k].etype != ETYPE_BITFLD || e[k].len)
1360 {
1361 e[n].arr_len = 255;
1362 break;
1363 }
1364 }
1365 }
1366 else if ((r & 3) != 3)
1367 e[n].arr_len = (r >> 2) & 7;
1368 else
1369 e[n].arr_len = (r >> 2) & 31;
1370 break;
1371 case 6:
1372 sametype = 1;
1373 switch (r & 7)
1374 {
1375 case 0:
1376 case 1:
1377 case 2:
1378 break;
1379 case 3:
1380 case 4:
1381 case 5:
1382 incr = 1 + (r >> 3) % (len - n);
1383 break;
1384 case 6:
1385 case 7:
1386 sametype = 0;
1387 incr = 1 + (r >> 3) % (len - n);
1388 break;
1389 }
1390 for (j = n; j < n + incr; ++j)
1391 {
1392 int mi, ma;
1393
1394 e[j].etype = ETYPE_BITFLD;
1395 if (j == n || !sametype)
1396 {
1397 int k;
1398 r = generate_random ();
1399 k = r & 3;
1400 r >>= 2;
1401 if (!k)
1402 e[j].type
1403 = &aligned_bitfld_types[r % n_aligned_bitfld_types];
1404 else
1405 e[j].type
1406 = &bitfld_types[r % n_bitfld_types];
1407 }
1408 else
1409 e[j].type = e[n].type;
1410 r = generate_random ();
1411 mi = 0;
1412 ma = 0;
1413 switch (e[j].type->bitfld)
1414 {
1415 case 'C': ma = 8; break;
1416 case 'S': ma = 16; break;
1417 case 'I': ma = 32; break;
1418 case 'L':
1419 case 'Q': ma = 64; break;
1420 case 'B': ma = 1; break;
1421 case ' ':
1422 if (e[j].type->type == TYPE_UENUM)
1423 mi = my_ffsll (e[j].type->maxval + 1) - 1;
1424 else if (e[j].type->type == TYPE_SENUM)
1425 mi = my_ffsll (e[j].type->maxval + 1);
1426 else
1427 abort ();
1428 if (!mi)
1429 mi = 1;
1430 if (mi > 32)
1431 ma = 64;
1432 else if (mi > 16 || !short_enums)
1433 ma = 32;
1434 else if (mi > 8)
1435 ma = 16;
1436 else
1437 ma = 8;
1438 break;
1439 default:
1440 abort ();
1441 }
1442 e[j].len = ma + 1;
1443 if (sametype && (r & 3) == 0 && ma > 1)
1444 {
1445 int sum = 0, k;
1446 for (k = n; k < j; ++k)
1447 sum += e[k].len;
1448 sum %= ma;
1449 e[j].len = sum ? ma - sum : ma;
1450 }
1451 r >>= 2;
1452 if (!sametype && (r & 7) == 0)
1453 ma *= 8;
1454 r >>= 3;
1455 if (! (features & FEATURE_ZEROBITFLD) && mi == 0)
1456 mi = 1;
1457 if (e[j].len < mi || e[j].len > ma)
1458 e[j].len = mi + (r % (ma + 1 - mi));
1459 r >>= 6;
1460 if ((features & FEATURE_ZEROBITFLD) && (r & 3) == 0
1461 && mi == 0)
1462 e[j].len = 0;
1463 }
1464 break;
1465 case 7:
1466 switch (r & 7)
1467 {
1468 case 0:
1469 case 1:
1470 case 2:
1471 e[n].etype = ETYPE_STRUCT;
1472 break;
1473 case 3:
1474 case 4:
1475 e[n].etype = ETYPE_UNION;
1476 break;
1477 case 5:
1478 case 6:
1479 e[n].etype = ETYPE_STRUCT_ARRAY;
1480 break;
1481 case 7:
1482 e[n].etype = ETYPE_UNION_ARRAY;
1483 break;
1484 }
1485 r >>= 3;
1486 e[n].len = r % (len - n);
1487 incr = 1 + e[n].len;
1488 generate_fields (features, &e[n + 1], &e[n], e[n].len);
1489 if (e[n].etype == ETYPE_STRUCT_ARRAY
1490 || e[n].etype == ETYPE_UNION_ARRAY)
1491 {
1492 r = generate_random ();
1493 if ((features & FEATURE_ZEROARRAY) && (r & 3) == 0)
1494 {
1495 e[n].arr_len = 0;
1496 if (n + incr == len && (r & 4)
1497 && (parent->etype == ETYPE_STRUCT
1498 || parent->etype == ETYPE_STRUCT_ARRAY))
1499 {
1500 int k;
1501 for (k = 0; k < n; ++k)
1502 if (e[k].etype != ETYPE_BITFLD || e[k].len)
1503 {
1504 e[n].arr_len = 255;
1505 break;
1506 }
1507 }
1508 }
1509 else if ((r & 3) != 3)
1510 e[n].arr_len = (r >> 2) & 7;
1511 else
1512 e[n].arr_len = (r >> 2) & 31;
1513 }
1514 break;
1515 }
1516 r = generate_random ();
1517 if ((r & 7) == 0)
1518 {
1519 r >>= 3;
1520 i = (features & FEATURE_ALIGNEDPACKED) ? NATTRIBS2 : NATTRIBS1;
1521 e[n].attrib = attributes[r % i];
1522 if (! (features & FEATURE_ALIGNEDPACKED)
1523 && strcmp (e[n].attrib, "atpa") == 0
1524 && ((e[n].type >= &attrib_types[0]
1525 && e[n].type < &attrib_types[NATYPES2])
1526 || (e[n].type >= &attrib_array_types[0]
1527 && e[n].type < &attrib_array_types[NAATYPES2])
1528 || (e[n].type >= &aligned_bitfld_types[0]
1529 && e[n].type < &aligned_bitfld_types[n_aligned_bitfld_types])))
1530 e[n].attrib = NULL;
1531 }
1532 }
1533 }
1534
1535 void
generate_random_tests(enum FEATURE features,int len)1536 generate_random_tests (enum FEATURE features, int len)
1537 {
1538 struct entry e[len + 1];
1539 int i, r;
1540 if (len > 'z' - 'a' + 1)
1541 abort ();
1542 memset (e, 0, sizeof (e));
1543 r = generate_random ();
1544 if ((r & 7) == 0)
1545 e[0].etype = ETYPE_UNION;
1546 else
1547 e[0].etype = ETYPE_STRUCT;
1548 r >>= 3;
1549 e[0].len = len;
1550 generate_fields (features, &e[1], &e[0], len);
1551 output (e);
1552 }
1553
1554 struct { const char *name; enum FEATURE f; }
1555 features[] = {
1556 { "normal", 0 },
1557 { "vector", FEATURE_VECTOR },
1558 { "[0] :0", FEATURE_ZEROARRAY | FEATURE_ZEROBITFLD },
1559 { "vector [0]",
1560 FEATURE_VECTOR | FEATURE_ZEROARRAY },
1561 { "aligned packed vector [0] :0",
1562 FEATURE_VECTOR | FEATURE_ZEROARRAY
1563 | FEATURE_ALIGNEDPACKED | FEATURE_ZEROBITFLD },
1564 };
1565
1566 int
main(int argc,char ** argv)1567 main (int argc, char **argv)
1568 {
1569 int i, j, count, c, n = 3000;
1570 char *optarg;
1571
1572 if (sizeof (int) != 4 || sizeof (long long) != 8)
1573 return 1;
1574
1575 i = 1;
1576 while (i < argc)
1577 {
1578 c = '\0';
1579 if (argv[i][0] == '-' && argv[i][2] == '\0')
1580 c = argv[i][1];
1581 optarg = argv[i + 1];
1582 if (!optarg)
1583 goto usage;
1584 switch (c)
1585 {
1586 case 'n':
1587 n = atoi (optarg);
1588 break;
1589 case 'd':
1590 destdir = optarg;
1591 break;
1592 case 's':
1593 srcdir = optarg;
1594 break;
1595 case 'i':
1596 output_one = 1;
1597 limidx = atoi (optarg);
1598 break;
1599 case 'e':
1600 short_enums = 1;
1601 i--;
1602 break;
1603 default:
1604 fprintf (stderr, "unrecognized option %s\n", argv[i]);
1605 goto usage;
1606 }
1607 i += 2;
1608 }
1609
1610 if (output_one)
1611 {
1612 outfile = fopen ("/dev/null", "w");
1613 if (outfile == NULL)
1614 {
1615 fputs ("could not open /dev/null", stderr);
1616 return 1;
1617 }
1618 n = limidx + 1;
1619 }
1620
1621 if (destdir == NULL && !output_one)
1622 {
1623 usage:
1624 fprintf (stderr, "Usage:\n\
1625 %s [-e] [-s srcdir -d destdir] [-n count] [-i idx]\n\
1626 Either -s srcdir -d destdir or -i idx must be used\n", argv[0]);
1627 return 1;
1628 }
1629
1630 if (srcdir == NULL && !output_one)
1631 goto usage;
1632
1633 if (srcdir != NULL)
1634 {
1635 const char *s = srcdir;
1636 char *ss, *t;
1637 t = ss = malloc (strlen (srcdir) + 1);
1638 if (!ss)
1639 abort ();
1640 do {
1641 if (*s == '\\')
1642 *t++ = '/';
1643 else
1644 *t++ = *s;
1645 } while (*s++);
1646 srcdir_safe = ss;
1647 }
1648
1649 for (i = 0; i < NTYPES2; ++i)
1650 if (base_types[i].bitfld)
1651 bitfld_types[n_bitfld_types++] = base_types[i];
1652 for (i = 0; i < NATYPES2; ++i)
1653 if (attrib_types[i].bitfld)
1654 aligned_bitfld_types[n_aligned_bitfld_types++] = attrib_types[i];
1655 for (i = 0; i < sizeof (features) / sizeof (features[0]); ++i)
1656 {
1657 int startidx = idx;
1658 if (! output_one)
1659 limidx = idx;
1660 if (!i)
1661 count = 200;
1662 else
1663 count = 20;
1664 for (j = 1; j <= 9; ++j)
1665 while (idx < startidx + j * count)
1666 generate_random_tests (features[i].f, j);
1667 while (idx < startidx + count * 10)
1668 generate_random_tests (features[i].f, 10 + (generate_random () % 16));
1669 }
1670 for (i = 0; n > 3000 && i < sizeof (features) / sizeof (features[0]); ++i)
1671 {
1672 int startidx;
1673 startidx = idx;
1674 if (! output_one)
1675 limidx = idx;
1676 singles (features[i].f);
1677 if (!i)
1678 {
1679 count = 1000;
1680 while (idx < startidx + 1000)
1681 generate_random_tests (features[i].f, 1);
1682 }
1683 else
1684 {
1685 startidx = idx;
1686 count = 100;
1687 while (idx < startidx + 100)
1688 generate_random_tests (features[i].f, 1);
1689 }
1690 startidx = idx;
1691 for (j = 2; j <= 9; ++j)
1692 while (idx < startidx + (j - 1) * count)
1693 generate_random_tests (features[i].f, j);
1694 while (idx < startidx + count * 9)
1695 generate_random_tests (features[i].f, 10 + (generate_random () % 16));
1696 }
1697 if (! output_one)
1698 limidx = idx;
1699 while (idx < n)
1700 generate_random_tests (ALL_FEATURES, 1 + (generate_random () % 25));
1701 fclose (outfile);
1702 return 0;
1703 }
1704