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