1# coding=utf-8
2#
3# Copyright © 2015 Intel Corporation
4#
5# Permission is hereby granted, free of charge, to any person obtaining a
6# copy of this software and associated documentation files (the "Software"),
7# to deal in the Software without restriction, including without limitation
8# the rights to use, copy, modify, merge, publish, distribute, sublicense,
9# and/or sell copies of the Software, and to permit persons to whom the
10# Software is furnished to do so, subject to the following conditions:
11#
12# The above copyright notice and this permission notice (including the next
13# paragraph) shall be included in all copies or substantial portions of the
14# Software.
15#
16# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
19# THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
21# FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
22# IN THE SOFTWARE.
23#
24
25import sys
26import xml.etree.ElementTree as ET
27
28# We generate a static hash table for entry point lookup
29# (vkGetProcAddress). We use a linear congruential generator for our hash
30# function and a power-of-two size table. The prime numbers are determined
31# experimentally.
32
33none = 0xffff
34hash_size = 256
35u32_mask = 2**32 - 1
36hash_mask = hash_size - 1
37
38prime_factor = 5024183
39prime_step = 19
40
41def hash(name):
42    h = 0;
43    for c in name:
44        h = (h * prime_factor + ord(c)) & u32_mask
45
46    return h
47
48def print_guard_start(guard):
49    if guard is not None:
50        print "#ifdef {0}".format(guard)
51
52def print_guard_end(guard):
53    if guard is not None:
54        print "#endif // {0}".format(guard)
55
56opt_header = False
57opt_code = False
58
59if (sys.argv[1] == "header"):
60    opt_header = True
61    sys.argv.pop()
62elif (sys.argv[1] == "code"):
63    opt_code = True
64    sys.argv.pop()
65
66# Extract the entry points from the registry
67def get_entrypoints(doc, entrypoints_to_defines):
68    entrypoints = []
69    commands = doc.findall('./commands/command')
70    for i, command in enumerate(commands):
71        type = command.find('./proto/type').text
72        fullname = command.find('./proto/name').text
73        shortname = fullname[2:]
74        params = map(lambda p: "".join(p.itertext()), command.findall('./param'))
75        params = ', '.join(params)
76        if fullname in entrypoints_to_defines:
77            guard = entrypoints_to_defines[fullname]
78        else:
79            guard = None
80        entrypoints.append((type, shortname, params, i, hash(fullname), guard))
81    return entrypoints
82
83# Maps entry points to extension defines
84def get_entrypoints_defines(doc):
85    entrypoints_to_defines = {}
86    extensions = doc.findall('./extensions/extension')
87    for extension in extensions:
88        define = extension.get('protect')
89        entrypoints = extension.findall('./require/command')
90        for entrypoint in entrypoints:
91            fullname = entrypoint.get('name')
92            entrypoints_to_defines[fullname] = define
93    return entrypoints_to_defines
94
95doc = ET.parse(sys.stdin)
96entrypoints = get_entrypoints(doc, get_entrypoints_defines(doc))
97
98# For outputting entrypoints.h we generate a radv_EntryPoint() prototype
99# per entry point.
100
101if opt_header:
102    print "/* This file generated from vk_gen.py, don't edit directly. */\n"
103
104    print "struct radv_dispatch_table {"
105    print "   union {"
106    print "      void *entrypoints[%d];" % len(entrypoints)
107    print "      struct {"
108
109    for type, name, args, num, h, guard in entrypoints:
110        if guard is not None:
111            print "#ifdef {0}".format(guard)
112            print "         PFN_vk{0} {0};".format(name)
113            print "#else"
114            print "         void *{0};".format(name)
115            print "#endif"
116        else:
117            print "         PFN_vk{0} {0};".format(name)
118    print "      };\n"
119    print "   };\n"
120    print "};\n"
121
122    for type, name, args, num, h, guard in entrypoints:
123        print_guard_start(guard)
124        print "%s radv_%s(%s);" % (type, name, args)
125        print_guard_end(guard)
126    exit()
127
128
129
130print """/*
131 * Copyright © 2015 Intel Corporation
132 *
133 * Permission is hereby granted, free of charge, to any person obtaining a
134 * copy of this software and associated documentation files (the "Software"),
135 * to deal in the Software without restriction, including without limitation
136 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
137 * and/or sell copies of the Software, and to permit persons to whom the
138 * Software is furnished to do so, subject to the following conditions:
139 *
140 * The above copyright notice and this permission notice (including the next
141 * paragraph) shall be included in all copies or substantial portions of the
142 * Software.
143 *
144 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
145 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
146 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
147 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
148 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
149 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
150 * IN THE SOFTWARE.
151 */
152
153/* DO NOT EDIT! This is a generated file. */
154
155#include "radv_private.h"
156
157struct radv_entrypoint {
158   uint32_t name;
159   uint32_t hash;
160};
161
162/* We use a big string constant to avoid lots of reloctions from the entry
163 * point table to lots of little strings. The entries in the entry point table
164 * store the index into this big string.
165 */
166
167static const char strings[] ="""
168
169offsets = []
170i = 0;
171for type, name, args, num, h, guard in entrypoints:
172    print "   \"vk%s\\0\"" % name
173    offsets.append(i)
174    i += 2 + len(name) + 1
175print "   ;"
176
177# Now generate the table of all entry points
178
179print "\nstatic const struct radv_entrypoint entrypoints[] = {"
180for type, name, args, num, h, guard in entrypoints:
181    print "   { %5d, 0x%08x }," % (offsets[num], h)
182print "};\n"
183
184print """
185
186/* Weak aliases for all potential implementations. These will resolve to
187 * NULL if they're not defined, which lets the resolve_entrypoint() function
188 * either pick the correct entry point.
189 */
190"""
191
192for layer in [ "radv" ]:
193    for type, name, args, num, h, guard in entrypoints:
194        print_guard_start(guard)
195        print "%s %s_%s(%s) __attribute__ ((weak));" % (type, layer, name, args)
196        print_guard_end(guard)
197    print "\nconst struct radv_dispatch_table %s_layer = {" % layer
198    for type, name, args, num, h, guard in entrypoints:
199        print_guard_start(guard)
200        print "   .%s = %s_%s," % (name, layer, name)
201        print_guard_end(guard)
202    print "};\n"
203
204print """
205
206void * __attribute__ ((noinline))
207radv_resolve_entrypoint(uint32_t index)
208{
209   return radv_layer.entrypoints[index];
210}
211"""
212
213# Now generate the hash table used for entry point look up.  This is a
214# uint16_t table of entry point indices. We use 0xffff to indicate an entry
215# in the hash table is empty.
216
217map = [none for f in xrange(hash_size)]
218collisions = [0 for f in xrange(10)]
219for type, name, args, num, h, guard in entrypoints:
220    level = 0
221    while map[h & hash_mask] != none:
222        h = h + prime_step
223        level = level + 1
224    if level > 9:
225        collisions[9] += 1
226    else:
227        collisions[level] += 1
228    map[h & hash_mask] = num
229
230print "/* Hash table stats:"
231print " * size %d entries" % hash_size
232print " * collisions  entries"
233for i in xrange(10):
234    if (i == 9):
235        plus = "+"
236    else:
237        plus = " "
238
239    print " *     %2d%s     %4d" % (i, plus, collisions[i])
240print " */\n"
241
242print "#define none 0x%04x\n" % none
243
244print "static const uint16_t map[] = {"
245for i in xrange(0, hash_size, 8):
246    print "   ",
247    for j in xrange(i, i + 8):
248        if map[j] & 0xffff == 0xffff:
249            print "  none,",
250        else:
251            print "0x%04x," % (map[j] & 0xffff),
252    print
253
254print "};"
255
256# Finally we generate the hash table lookup function.  The hash function and
257# linear probing algorithm matches the hash table generated above.
258
259print """
260void *
261radv_lookup_entrypoint(const char *name)
262{
263   static const uint32_t prime_factor = %d;
264   static const uint32_t prime_step = %d;
265   const struct radv_entrypoint *e;
266   uint32_t hash, h, i;
267   const char *p;
268
269   hash = 0;
270   for (p = name; *p; p++)
271      hash = hash * prime_factor + *p;
272
273   h = hash;
274   do {
275      i = map[h & %d];
276      if (i == none)
277         return NULL;
278      e = &entrypoints[i];
279      h += prime_step;
280   } while (e->hash != hash);
281
282   if (strcmp(name, strings + e->name) != 0)
283      return NULL;
284
285   return radv_resolve_entrypoint(i);
286}
287""" % (prime_factor, prime_step, hash_mask)
288