yum-mirror/slang

Making it easier to work with shaders

git clone https://git.yummers.dev/yum-mirror/slang

Ellie Hermaszewskaformatf65d756bf

master
branchesmasterall refs →
6.8 KiB215 linesraw
1#include "slang-perfect-hash.h"
2
3#include "../core/slang-string-util.h"
4#include "../core/slang-writer.h"
5
6namespace Slang
7{
8
9// Implemented according to "Hash, displace, and compress"
10// https://cmph.sourceforge.net/papers/esa09.pdf
11HashFindResult minimalPerfectHash(const List<String>& ss, HashParams& hashParams)
12{
13    // Check for uniqueness
14    for (Index i = 0; i < ss.getCount(); ++i)
15    {
16        for (Index j = i + 1; j < ss.getCount(); ++j)
17        {
18            if (ss[i] == ss[j])
19            {
20                return HashFindResult::NonUniqueKeys;
21            }
22        }
23    }
24
25    SLANG_ASSERT(UIndex(ss.getCount()) < std::numeric_limits<UInt32>::max());
26    const UInt32 nBuckets = UInt32(ss.getCount());
27    List<List<String>> initialBuckets;
28    initialBuckets.setCount(nBuckets);
29
30    const auto hash = [&](const String& s, const HashCode32 salt = 0) -> UInt32
31    {
32        //
33        // The current getStableHashCode is susceptible to patterns of
34        // collisions causing the search to fail for the SPIR-V opnames; it
35        // performs poorly on short strings, taking over 300000 iterations to
36        // diverge on "Ceil" and "FMix" (and place them in already unoccupied
37        // slots)!
38        //
39        // Use FNV Hash here which seem perform much better on these short inputs
40        // https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function
41        //
42        // If you change this, don't forget to also sync the version below in
43        // the printing code.
44        UInt32 h = salt;
45        for (const char c : s)
46            h = (h * 0x01000193) ^ c;
47        return h % nBuckets;
48    };
49
50    // Assign the inputs into their buckets according to the hash without salt.
51    // Sort the buckets according to size, so that later we can make these have
52    // unique destinations starting with the largest ones first as they are at
53    // most risk of collision.
54    for (const auto& s : ss)
55    {
56        initialBuckets[hash(s)].add(s);
57    }
58    initialBuckets.stableSort([](const List<String>& a, const List<String>& b)
59                              { return a.getCount() > b.getCount(); });
60
61    // These are our outputs, the salts are calculated such that for all input
62    // word, x, hash(x, salt[hash(x, 0)]) is unique
63    //
64    // We keep the final table as we need to detect when we've been given a
65    // word not in our language.
66    hashParams.saltTable.setCount(nBuckets);
67    for (auto& s : hashParams.saltTable)
68        s = 0;
69    hashParams.destTable.setCount(nBuckets);
70    for (auto& s : hashParams.destTable)
71        s.reduceLength(0);
72
73    // This mask will, in each salt tryout, be used to prevent collisions
74    // within a single bucket.
75    List<bool> bucketDestinations = List<bool>::makeRepeated(false, nBuckets);
76
77    for (const auto& b : initialBuckets)
78    {
79        // Break if we've reached the empty buckets
80        if (!b.getCount())
81        {
82            break;
83        }
84
85        // Try out all the salts until we get one which has no internal
86        // collisions for this bucket and also no collisions with the buckets
87        // we've processed so far.
88        UInt32 salt = 1;
89        while (true)
90        {
91            bool collision = false;
92            for (auto& d : bucketDestinations)
93            {
94                d = false;
95            }
96
97            for (const auto& s : b)
98            {
99                const auto i = hash(s, salt);
100                if (hashParams.destTable[i].getLength() || bucketDestinations[i])
101                {
102                    collision = true;
103                    break;
104                }
105                bucketDestinations[i] = true;
106            }
107            if (!collision)
108            {
109                break;
110            }
111            salt++;
112
113            // If we fail to find a solution after some massive amount of tries
114            // it's almost certainly because of some property of the hash
115            // function and language causing an irresolvable collision.
116            if (salt > 10000 * nBuckets)
117            {
118                return HashFindResult::UnavoidableHashCollision;
119            }
120        }
121        for (const auto& s : b)
122        {
123            hashParams.saltTable[hash(s)] = salt;
124            hashParams.destTable[hash(s, salt)] = s;
125        }
126    }
127    return HashFindResult::Success;
128}
129
130String perfectHashToEmbeddableCpp(
131    const HashParams& hashParams,
132    const UnownedStringSlice& valueType,
133    const UnownedStringSlice& funcName,
134    const List<String>& values)
135{
136    SLANG_ASSERT(hashParams.saltTable.getCount() == hashParams.destTable.getCount());
137    SLANG_ASSERT(hashParams.saltTable.getCount() == values.getCount());
138
139    StringBuilder sb;
140    StringWriter writer(&sb, WriterFlags(0));
141    WriterHelper w(&writer);
142    const auto line = [&](const char* l)
143    {
144        w.put(l);
145        w.put("\n");
146    };
147
148    w.print(
149        "bool %s(const UnownedStringSlice& str, %s& value)\n",
150        String(funcName).getBuffer(),
151        String(valueType).getBuffer());
152    line("{");
153
154    w.print("    static const unsigned tableSalt[%d] = {\n", (int)hashParams.saltTable.getCount());
155    w.print("       ");
156    for (Index i = 0; i < hashParams.saltTable.getCount(); ++i)
157    {
158        const auto salt = hashParams.saltTable[i];
159        if (i != hashParams.saltTable.getCount() - 1)
160        {
161            w.print(" %d,", salt);
162            if (i % 16 == 15)
163            {
164                w.print("\n       ");
165            }
166        }
167        else
168        {
169            w.print(" %d", salt);
170        }
171    }
172    line("\n    };");
173    line("");
174
175    w.print("    using KV = std::pair<const char*, %s>;\n", String(valueType).getBuffer());
176    line("");
177
178    w.print("    static const KV words[%d] =\n", (int)hashParams.destTable.getCount());
179    line("    {");
180    for (Index i = 0; i < hashParams.destTable.getCount(); ++i)
181    {
182        const auto& s = hashParams.destTable[i];
183        const auto& v = values[i];
184        w.print("        {\"%s\", %s},\n", s.getBuffer(), v.getBuffer());
185    }
186    line("    };");
187    line("");
188
189    // Make sure to update the hash function in the search function above if
190    // you change this.
191    line("    static const auto hash = [](const UnownedStringSlice& str, UInt32 salt){");
192    line("        UInt32 h = salt;");
193    line("        for (const char c : str)");
194    line("            h = (h * 0x01000193) ^ c;");
195    w.print("        return h %% %d;\n", (int)hashParams.saltTable.getCount());
196    line("    };");
197    line("");
198
199    line("    const auto i = hash(str, tableSalt[hash(str, 0)]);");
200    line("    if(str == words[i].first)");
201    line("    {");
202    line("        value = words[i].second;");
203    line("        return true;");
204    line("    }");
205    line("    else");
206    line("    {");
207    line("        return false;");
208    line("    }");
209    line("}");
210    line("");
211
212    return sb.produceString();
213}
214
215} // namespace Slang