2
/*Copyright (C) 2002-2005 3Dlabs Inc. Ltd. */
3
/*All rights reserved. */
5
/*Redistribution and use in source and binary forms, with or without */
6
/*modification, are permitted provided that the following conditions */
9
/* Redistributions of source code must retain the above copyright */
10
/* notice, this list of conditions and the following disclaimer. */
12
/* Redistributions in binary form must reproduce the above */
13
/* copyright notice, this list of conditions and the following */
14
/* disclaimer in the documentation and/or other materials provided */
15
/* with the distribution. */
17
/* Neither the name of 3Dlabs Inc. Ltd. nor the names of its */
18
/* contributors may be used to endorse or promote products derived */
19
/* from this software without specific prior written permission. */
21
/*THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS */
22
/*"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT */
23
/*LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS */
24
/*FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE */
25
/*COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, */
26
/*INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, */
27
/*BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; */
28
/*LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER */
29
/*CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT */
30
/*LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN */
31
/*ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE */
32
/*POSSIBILITY OF SUCH DAMAGE. */
34
/****************************************************************************\
35
Copyright (c) 2002, NVIDIA Corporation.
37
NVIDIA Corporation("NVIDIA") supplies this software to you in
38
consideration of your agreement to the following terms, and your use,
39
installation, modification or redistribution of this NVIDIA software
40
constitutes acceptance of these terms. If you do not agree with these
41
terms, please do not use, install, modify or redistribute this NVIDIA
44
In consideration of your agreement to abide by the following terms, and
45
subject to these terms, NVIDIA grants you a personal, non-exclusive
46
license, under NVIDIA's copyrights in this original NVIDIA software (the
47
"NVIDIA Software"), to use, reproduce, modify and redistribute the
48
NVIDIA Software, with or without modifications, in source and/or binary
49
forms; provided that if you redistribute the NVIDIA Software, you must
50
retain the copyright notice of NVIDIA, this notice and the following
51
text and disclaimers in all such redistributions of the NVIDIA Software.
52
Neither the name, trademarks, service marks nor logos of NVIDIA
53
Corporation may be used to endorse or promote products derived from the
54
NVIDIA Software without specific prior written permission from NVIDIA.
55
Except as expressly stated in this notice, no other rights or licenses
56
express or implied, are granted by NVIDIA herein, including but not
57
limited to any patent rights that may be infringed by your derivative
58
works or by other works in which the NVIDIA Software may be
59
incorporated. No hardware is licensed hereunder.
61
THE NVIDIA SOFTWARE IS BEING PROVIDED ON AN "AS IS" BASIS, WITHOUT
62
WARRANTIES OR CONDITIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED,
63
INCLUDING WITHOUT LIMITATION, WARRANTIES OR CONDITIONS OF TITLE,
64
NON-INFRINGEMENT, MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, OR
65
ITS USE AND OPERATION EITHER ALONE OR IN COMBINATION WITH OTHER
68
IN NO EVENT SHALL NVIDIA BE LIABLE FOR ANY SPECIAL, INDIRECT,
69
INCIDENTAL, EXEMPLARY, CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
70
TO, LOST PROFITS; PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
71
USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) OR ARISING IN ANY WAY
72
OUT OF THE USE, REPRODUCTION, MODIFICATION AND/OR DISTRIBUTION OF THE
73
NVIDIA SOFTWARE, HOWEVER CAUSED AND WHETHER UNDER THEORY OF CONTRACT,
74
TORT (INCLUDING NEGLIGENCE), STRICT LIABILITY OR OTHERWISE, EVEN IF
75
NVIDIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
76
\****************************************************************************/
87
#include "slglobals.h"
93
/*///////////////////////////////////////////////////////////////////////////////////////////// */
94
/*//////////////////////////////////////// String table: ////////////////////////////////////// */
95
/*///////////////////////////////////////////////////////////////////////////////////////////// */
101
{ CPP_AND_OP, "&&" },
102
{ CPP_AND_ASSIGN, "&=" },
103
{ CPP_SUB_ASSIGN, "-=" },
104
{ CPP_MOD_ASSIGN, "%=" },
105
{ CPP_ADD_ASSIGN, "+=" },
106
{ CPP_DIV_ASSIGN, "/=" },
107
{ CPP_MUL_ASSIGN, "*=" },
108
{ CPP_RIGHT_BRACKET, ":>" },
110
{ CPP_XOR_OP, "^^" },
111
{ CPP_XOR_ASSIGN, "^=" },
112
{ CPP_FLOATCONSTANT, "<float-const>" },
114
{ CPP_RIGHT_OP, ">>" },
115
{ CPP_RIGHT_ASSIGN, ">>=" },
116
{ CPP_IDENTIFIER, "<ident>" },
117
{ CPP_INTCONSTANT, "<int-const>" },
119
{ CPP_LEFT_OP, "<<" },
120
{ CPP_LEFT_ASSIGN, "<<=" },
121
{ CPP_LEFT_BRACKET, "<:" },
122
{ CPP_LEFT_BRACE, "<%" },
123
{ CPP_DEC_OP, "--" },
124
{ CPP_RIGHT_BRACE, "%>" },
127
{ CPP_OR_ASSIGN, "|=" },
128
{ CPP_INC_OP, "++" },
129
{ CPP_STRCONSTANT, "<string-const>" },
130
{ CPP_TYPEIDENTIFIER, "<type-ident>" },
133
/*///////////////////////////////////////////////////////////////////////////////////////////// */
134
/*//////////////////////////////////////// String table: ////////////////////////////////////// */
135
/*///////////////////////////////////////////////////////////////////////////////////////////// */
137
#define INIT_STRING_TABLE_SIZE 16384
139
typedef struct StringTable_Rec {
146
* InitStringTable() - Initialize the string table.
150
static int InitStringTable(StringTable *stable)
152
stable->strings = (char *) malloc(INIT_STRING_TABLE_SIZE);
153
if (!stable->strings)
155
/* Zero-th offset means "empty" so don't use it. */
156
stable->nextFree = 1;
157
stable->size = INIT_STRING_TABLE_SIZE;
159
} /* InitStringTable */
162
* FreeStringTable() - Free the string table.
166
static void FreeStringTable(StringTable *stable)
169
free(stable->strings);
170
stable->strings = NULL;
171
stable->nextFree = 0;
173
} /* FreeStringTable */
176
* HashString() - Hash a string with the base hash function.
180
static int HashString(const char *s)
185
hval = (hval*13507 + *s*197) ^ (hval >> 2);
188
return hval & 0x7fffffff;
192
* HashString2() - Hash a string with the incrimenting hash function.
196
static int HashString2(const char *s)
201
hval = (hval*729 + *s*37) ^ (hval >> 1);
208
* AddString() - Add a string to a string table. Return it's offset.
212
static int AddString(StringTable *stable, const char *s)
217
len = (int) strlen(s);
218
if (stable->nextFree + len + 1 >= stable->size) {
219
assert(stable->size < 1000000);
220
str = (char *) malloc(stable->size*2);
221
memcpy(str, stable->strings, stable->size);
222
free(stable->strings);
223
stable->strings = str;
225
loc = stable->nextFree;
226
strcpy(&stable->strings[loc], s);
227
stable->nextFree += len + 1;
231
/*///////////////////////////////////////////////////////////////////////////////////////////// */
232
/*///////////////////////////////////////// Hash table: /////////////////////////////////////// */
233
/*///////////////////////////////////////////////////////////////////////////////////////////// */
235
#define INIT_HASH_TABLE_SIZE 2047
236
#define HASH_TABLE_MAX_COLLISIONS 3
238
typedef struct HashEntry_Rec {
239
int index; /* String table offset of string representation */
240
int value; /* Atom (symbol) value */
243
typedef struct HashTable_Rec {
247
int counts[HASH_TABLE_MAX_COLLISIONS + 1];
251
* InitHashTable() - Initialize the hash table.
255
static int InitHashTable(HashTable *htable, int fsize)
259
htable->entry = (HashEntry *) malloc(sizeof(HashEntry)*fsize);
262
htable->size = fsize;
263
for (ii = 0; ii < fsize; ii++) {
264
htable->entry[ii].index = 0;
265
htable->entry[ii].value = 0;
268
for (ii = 0; ii <= HASH_TABLE_MAX_COLLISIONS; ii++)
269
htable->counts[ii] = 0;
271
} /* InitHashTable */
274
* FreeHashTable() - Free the hash table.
278
static void FreeHashTable(HashTable *htable)
282
htable->entry = NULL;
285
} /* FreeHashTable */
288
* Empty() - See if a hash table entry is empty.
292
static int Empty(HashTable *htable, int hashloc)
294
assert(hashloc >= 0 && hashloc < htable->size);
295
if (htable->entry[hashloc].index == 0) {
303
* Match() - See if a hash table entry is matches a string.
307
static int Match(HashTable *htable, StringTable *stable, const char *s, int hashloc)
311
strloc = htable->entry[hashloc].index;
312
if (!strcmp(s, &stable->strings[strloc])) {
319
/*///////////////////////////////////////////////////////////////////////////////////////////// */
320
/*///////////////////////////////////////// Atom table: /////////////////////////////////////// */
321
/*///////////////////////////////////////////////////////////////////////////////////////////// */
323
#define INIT_ATOM_TABLE_SIZE 1024
326
struct AtomTable_Rec {
327
StringTable stable; /* String table. */
328
HashTable htable; /* Hashes string to atom number and token value. Multiple strings can */
329
/* have the same token value but each unique string is a unique atom. */
330
int *amap; /* Maps atom value to offset in string table. Atoms all map to unique */
331
/* strings except for some undefined values in the lower, fixed part */
332
/* of the atom table that map to "<undefined>". The lowest 256 atoms */
333
/* correspond to single character ASCII values except for alphanumeric */
334
/* characters and '_', which can be other tokens. Next come the */
335
/* language tokens with their atom values equal to the token value. */
336
/* Then come predefined atoms, followed by user specified identifiers. */
337
int *arev; /* Reversed atom for symbol table use. */
342
static AtomTable latable = { { 0 } };
343
AtomTable *atable = &latable;
345
static int AddAtomFixed(AtomTable *atable, const char *s, int atom);
348
* GrowAtomTable() - Grow the atom table to at least "size" if it's smaller.
352
static int GrowAtomTable(AtomTable *atable, int size)
354
int *newmap, *newrev;
356
if (atable->size < size) {
358
newmap = realloc(atable->amap, sizeof(int)*size);
359
newrev = realloc(atable->arev, sizeof(int)*size);
361
newmap = malloc(sizeof(int)*size);
362
newrev = malloc(sizeof(int)*size);
365
if (!newmap || !newrev) {
366
/* failed to grow -- error */
368
atable->amap = newmap;
370
atable->amap = newrev;
373
memset(&newmap[atable->size], 0, (size - atable->size) * sizeof(int));
374
memset(&newrev[atable->size], 0, (size - atable->size) * sizeof(int));
375
atable->amap = newmap;
376
atable->arev = newrev;
380
} /* GrowAtomTable */
383
* lReverse() - Reverse the bottom 20 bits of a 32 bit int.
387
static int lReverse(int fval)
389
unsigned int in = fval;
390
int result = 0, cnt = 0;
399
/* Don't use all 31 bits. One million atoms is plenty and sometimes the */
400
/* upper bits are used for other things. */
408
* AllocateAtom() - Allocate a new atom. Associated with the "undefined" value of -1.
412
static int AllocateAtom(AtomTable *atable)
414
if (atable->nextFree >= atable->size)
415
GrowAtomTable(atable, atable->nextFree*2);
416
atable->amap[atable->nextFree] = -1;
417
atable->arev[atable->nextFree] = lReverse(atable->nextFree);
419
return atable->nextFree - 1;
423
* SetAtomValue() - Allocate a new atom associated with "hashindex".
427
static void SetAtomValue(AtomTable *atable, int atomnumber, int hashindex)
429
atable->amap[atomnumber] = atable->htable.entry[hashindex].index;
430
atable->htable.entry[hashindex].value = atomnumber;
434
* FindHashLoc() - Find the hash location for this string. Return -1 it hash table is full.
438
static int FindHashLoc(AtomTable *atable, const char *s)
440
int hashloc, hashdelta, count;
441
int FoundEmptySlot = 0;
442
int collision[HASH_TABLE_MAX_COLLISIONS + 1];
444
hashloc = HashString(s) % atable->htable.size;
445
if (!Empty(&atable->htable, hashloc)) {
446
if (Match(&atable->htable, &atable->stable, s, hashloc))
448
collision[0] = hashloc;
449
hashdelta = HashString2(s);
451
while (count < HASH_TABLE_MAX_COLLISIONS) {
452
hashloc = ((hashloc + hashdelta) & 0x7fffffff) % atable->htable.size;
453
if (!Empty(&atable->htable, hashloc)) {
454
if (Match(&atable->htable, &atable->stable, s, hashloc)) {
462
collision[count] = hashloc;
465
if (!FoundEmptySlot) {
466
if (cpp->options.DumpAtomTable) {
469
sprintf(str, "*** Hash failed with more than %d collisions. Must increase hash table size. ***",
470
HASH_TABLE_MAX_COLLISIONS);
471
CPPShInfoLogMsg(str);
473
sprintf(str, "*** New string \"%s\", hash=%04x, delta=%04x", s, collision[0], hashdelta);
474
CPPShInfoLogMsg(str);
475
for (ii = 0; ii <= HASH_TABLE_MAX_COLLISIONS; ii++) {
476
sprintf(str, "*** Collides on try %d at hash entry %04x with \"%s\"",
477
ii + 1, collision[ii], GetAtomString(atable, atable->htable.entry[collision[ii]].value));
478
CPPShInfoLogMsg(str);
483
atable->htable.counts[count]++;
490
* IncreaseHashTableSize()
494
static int IncreaseHashTableSize(AtomTable *atable)
496
int ii, strloc, oldhashloc, value, size;
500
/* Save the old atom table and create a new one: */
503
size = oldtable.htable.size*2 + 1;
504
if (!InitAtomTable(atable, size))
507
/* Add all the existing values to the new atom table preserving their atom values: */
509
for (ii = atable->nextFree; ii < oldtable.nextFree; ii++) {
510
strloc = oldtable.amap[ii];
511
s = &oldtable.stable.strings[strloc];
512
oldhashloc = FindHashLoc(&oldtable, s);
513
assert(oldhashloc >= 0);
514
value = oldtable.htable.entry[oldhashloc].value;
515
AddAtomFixed(atable, s, value);
517
FreeAtomTable(&oldtable);
519
} /* IncreaseHashTableSize */
522
* LookUpAddStringHash() - Lookup a string in the hash table. If it's not there, add it and
523
* initialize the atom value in the hash table to 0. Return the hash table index.
526
static int LookUpAddStringHash(AtomTable *atable, const char *s)
531
hashloc = FindHashLoc(atable, s);
534
IncreaseHashTableSize(atable);
537
if (Empty(&atable->htable, hashloc)) {
538
atable->htable.entries++;
539
strloc = AddString(&atable->stable, s);
540
atable->htable.entry[hashloc].index = strloc;
541
atable->htable.entry[hashloc].value = 0;
544
} /* LookUpAddStringHash */
547
* LookUpAddString() - Lookup a string in the hash table. If it's not there, add it and
548
* initialize the atom value in the hash table to the next atom number.
549
* Return the atom value of string.
552
int LookUpAddString(AtomTable *atable, const char *s)
556
hashindex = LookUpAddStringHash(atable, s);
557
atom = atable->htable.entry[hashindex].value;
559
atom = AllocateAtom(atable);
560
SetAtomValue(atable, atom, hashindex);
563
} /* LookUpAddString */
570
const char *GetAtomString(AtomTable *atable, int atom)
574
if (atom > 0 && atom < atable->nextFree) {
575
soffset = atable->amap[atom];
576
if (soffset > 0 && soffset < atable->stable.nextFree) {
577
return &atable->stable.strings[soffset];
579
return "<internal error: bad soffset>";
583
return "<null atom>";
588
return "<invalid atom>";
592
} /* GetAtomString */
599
int GetReversedAtom(AtomTable *atable, int atom)
601
if (atom > 0 && atom < atable->nextFree) {
602
return atable->arev[atom];
606
} /* GetReversedAtom */
609
* AddAtom() - Add a string to the atom, hash and string tables if it isn't already there.
610
* Return it's atom index.
613
int AddAtom(AtomTable *atable, const char *s)
617
atom = LookUpAddString(atable, s);
622
* AddAtomFixed() - Add an atom to the hash and string tables if it isn't already there.
623
* Assign it the atom value of "atom".
626
static int AddAtomFixed(AtomTable *atable, const char *s, int atom)
628
int hashindex, lsize;
630
hashindex = LookUpAddStringHash(atable, s);
631
if (atable->nextFree >= atable->size || atom >= atable->size) {
632
lsize = atable->size*2;
635
GrowAtomTable(atable, lsize);
637
atable->amap[atom] = atable->htable.entry[hashindex].index;
638
atable->htable.entry[hashindex].value = atom;
639
/*if (atom >= atable->nextFree) */
640
/* atable->nextFree = atom + 1; */
641
while (atom >= atable->nextFree) {
642
atable->arev[atable->nextFree] = lReverse(atable->nextFree);
649
* InitAtomTable() - Initialize the atom table.
653
int InitAtomTable(AtomTable *atable, int htsize)
657
htsize = htsize <= 0 ? INIT_HASH_TABLE_SIZE : htsize;
658
if (!InitStringTable(&atable->stable))
660
if (!InitHashTable(&atable->htable, htsize))
663
atable->nextFree = 0;
666
GrowAtomTable(atable, INIT_ATOM_TABLE_SIZE);
670
/* Initialize lower part of atom table to "<undefined>" atom: */
672
AddAtomFixed(atable, "<undefined>", 0);
673
for (ii = 0; ii < FIRST_USER_TOKEN_SY; ii++)
674
atable->amap[ii] = atable->amap[0];
676
/* Add single character tokens to the atom table: */
679
const char *s = "~!%^&*()-+=|,.<>/?;:[]{}#";
685
AddAtomFixed(atable, t, s[0]);
690
/* Add multiple character scanner tokens : */
692
for (ii = 0; ii < sizeof(tokens)/sizeof(tokens[0]); ii++)
693
AddAtomFixed(atable, tokens[ii].str, tokens[ii].val);
695
/* Add error symbol if running in error mode: */
697
if (cpp->options.ErrorMode)
698
AddAtomFixed(atable, "error", ERROR_SY);
700
AddAtom(atable, "<*** end fixed atoms ***>");
703
} /* InitAtomTable */
705
/*///////////////////////////////////////////////////////////////////////////////////////////// */
706
/*//////////////////////////////// Debug Printing Functions: ////////////////////////////////// */
707
/*///////////////////////////////////////////////////////////////////////////////////////////// */
714
void PrintAtomTable(AtomTable *atable)
719
for (ii = 0; ii < atable->nextFree; ii++) {
720
sprintf(str, "%d: \"%s\"", ii, &atable->stable.strings[atable->amap[ii]]);
723
sprintf(str, "Hash table: size=%d, entries=%d, collisions=",
724
atable->htable.size, atable->htable.entries);
726
for (ii = 0; ii < HASH_TABLE_MAX_COLLISIONS; ii++) {
727
sprintf(str, " %d", atable->htable.counts[ii]);
731
} /* PrintAtomTable */
739
char* GetStringOfAtom(AtomTable *atable, int atom)
742
chr_str=&atable->stable.strings[atable->amap[atom]];
744
} /* GetStringOfAtom */
747
* FreeAtomTable() - Free the atom table and associated memory
751
void FreeAtomTable(AtomTable *atable)
753
FreeStringTable(&atable->stable);
754
FreeHashTable(&atable->htable);
761
atable->nextFree = 0;
763
} /* FreeAtomTable */
765
/*///////////////////////////////////////////////////////////////////////////////////////////// */
766
/*/////////////////////////////////////// End of atom.c /////////////////////////////////////// */
767
/*///////////////////////////////////////////////////////////////////////////////////////////// */
added
removed
src/mesa/shader/slang/MachineIndependent/preprocessor/atom.c
