Go to most recent revision | Details | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
1901 | serge | 1 | #!/bin/env python |
2 | |||
3 | # (C) Copyright IBM Corporation 2005, 2006 |
||
4 | # All Rights Reserved. |
||
5 | # |
||
6 | # Permission is hereby granted, free of charge, to any person obtaining a |
||
7 | # copy of this software and associated documentation files (the "Software"), |
||
8 | # to deal in the Software without restriction, including without limitation |
||
9 | # on the rights to use, copy, modify, merge, publish, distribute, sub |
||
10 | # license, and/or sell copies of the Software, and to permit persons to whom |
||
11 | # the Software is furnished to do so, subject to the following conditions: |
||
12 | # |
||
13 | # The above copyright notice and this permission notice (including the next |
||
14 | # paragraph) shall be included in all copies or substantial portions of the |
||
15 | # Software. |
||
16 | # |
||
17 | # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR |
||
18 | # IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, |
||
19 | # FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. IN NO EVENT SHALL |
||
20 | # IBM AND/OR ITS SUPPLIERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER |
||
21 | # LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING |
||
22 | # FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS |
||
23 | # IN THE SOFTWARE. |
||
24 | # |
||
25 | # Authors: |
||
26 | # Ian Romanick |
||
27 | |||
28 | import gl_XML, glX_XML, glX_proto_common, license |
||
29 | import sys, getopt |
||
30 | |||
31 | |||
32 | def log2(value): |
||
33 | for i in range(0, 30): |
||
34 | p = 1 << i |
||
35 | if p >= value: |
||
36 | return i |
||
37 | |||
38 | return -1 |
||
39 | |||
40 | |||
41 | def round_down_to_power_of_two(n): |
||
42 | """Returns the nearest power-of-two less than or equal to n.""" |
||
43 | |||
44 | for i in range(30, 0, -1): |
||
45 | p = 1 << i |
||
46 | if p <= n: |
||
47 | return p |
||
48 | |||
49 | return -1 |
||
50 | |||
51 | |||
52 | class function_table: |
||
53 | def __init__(self, name, do_size_check): |
||
54 | self.name_base = name |
||
55 | self.do_size_check = do_size_check |
||
56 | |||
57 | |||
58 | self.max_bits = 1 |
||
59 | self.next_opcode_threshold = (1 << self.max_bits) |
||
60 | self.max_opcode = 0 |
||
61 | |||
62 | self.functions = {} |
||
63 | self.lookup_table = [] |
||
64 | |||
65 | # Minimum number of opcodes in a leaf node. |
||
66 | self.min_op_bits = 3 |
||
67 | self.min_op_count = (1 << self.min_op_bits) |
||
68 | return |
||
69 | |||
70 | |||
71 | def append(self, opcode, func): |
||
72 | self.functions[opcode] = func |
||
73 | |||
74 | if opcode > self.max_opcode: |
||
75 | self.max_opcode = opcode |
||
76 | |||
77 | if opcode > self.next_opcode_threshold: |
||
78 | bits = log2(opcode) |
||
79 | if (1 << bits) <= opcode: |
||
80 | bits += 1 |
||
81 | |||
82 | self.max_bits = bits |
||
83 | self.next_opcode_threshold = 1 << bits |
||
84 | return |
||
85 | |||
86 | |||
87 | def divide_group(self, min_opcode, total): |
||
88 | """Divide the group starting min_opcode into subgroups. |
||
89 | Returns a tuple containing the number of bits consumed by |
||
90 | the node, the list of the children's tuple, and the number |
||
91 | of entries in the final array used by this node and its |
||
92 | children, and the depth of the subtree rooted at the node.""" |
||
93 | |||
94 | remaining_bits = self.max_bits - total |
||
95 | next_opcode = min_opcode + (1 << remaining_bits) |
||
96 | empty_children = 0 |
||
97 | |||
98 | for M in range(0, remaining_bits): |
||
99 | op_count = 1 << (remaining_bits - M); |
||
100 | child_count = 1 << M; |
||
101 | |||
102 | empty_children = 0 |
||
103 | full_children = 0 |
||
104 | for i in range(min_opcode, next_opcode, op_count): |
||
105 | used = 0 |
||
106 | empty = 0 |
||
107 | |||
108 | for j in range(i, i + op_count): |
||
109 | if self.functions.has_key(j): |
||
110 | used += 1; |
||
111 | else: |
||
112 | empty += 1; |
||
113 | |||
114 | |||
115 | if empty == op_count: |
||
116 | empty_children += 1 |
||
117 | |||
118 | if used == op_count: |
||
119 | full_children += 1 |
||
120 | |||
121 | if (empty_children > 0) or (full_children == child_count) or (op_count <= self.min_op_count): |
||
122 | break |
||
123 | |||
124 | |||
125 | # If all the remaining bits are used by this node, as is the |
||
126 | # case when M is 0 or remaining_bits, the node is a leaf. |
||
127 | |||
128 | if (M == 0) or (M == remaining_bits): |
||
129 | return [remaining_bits, [], 0, 0] |
||
130 | else: |
||
131 | children = [] |
||
132 | count = 1 |
||
133 | depth = 1 |
||
134 | all_children_are_nonempty_leaf_nodes = 1 |
||
135 | for i in range(min_opcode, next_opcode, op_count): |
||
136 | n = self.divide_group(i, total + M) |
||
137 | |||
138 | if not (n[1] == [] and not self.is_empty_leaf(i, n[0])): |
||
139 | all_children_are_nonempty_leaf_nodes = 0 |
||
140 | |||
141 | children.append(n) |
||
142 | count += n[2] + 1 |
||
143 | |||
144 | if n[3] >= depth: |
||
145 | depth = n[3] + 1 |
||
146 | |||
147 | # If all of the child nodes are non-empty leaf nodes, pull |
||
148 | # them up and make this node a leaf. |
||
149 | |||
150 | if all_children_are_nonempty_leaf_nodes: |
||
151 | return [remaining_bits, [], 0, 0] |
||
152 | else: |
||
153 | return [M, children, count, depth] |
||
154 | |||
155 | |||
156 | def is_empty_leaf(self, base_opcode, M): |
||
157 | for op in range(base_opcode, base_opcode + (1 << M)): |
||
158 | if self.functions.has_key(op): |
||
159 | return 0 |
||
160 | break |
||
161 | |||
162 | return 1 |
||
163 | |||
164 | |||
165 | def dump_tree(self, node, base_opcode, remaining_bits, base_entry, depth): |
||
166 | M = node[0] |
||
167 | children = node[1] |
||
168 | child_M = remaining_bits - M |
||
169 | |||
170 | |||
171 | # This actually an error condition. |
||
172 | if children == []: |
||
173 | return |
||
174 | |||
175 | print ' /* [%u] -> opcode range [%u, %u], node depth %u */' % (base_entry, base_opcode, base_opcode + (1 << remaining_bits), depth) |
||
176 | print ' %u,' % (M) |
||
177 | |||
178 | base_entry += (1 << M) + 1 |
||
179 | |||
180 | child_index = base_entry |
||
181 | child_base_opcode = base_opcode |
||
182 | for child in children: |
||
183 | if child[1] == []: |
||
184 | if self.is_empty_leaf(child_base_opcode, child_M): |
||
185 | print ' EMPTY_LEAF,' |
||
186 | else: |
||
187 | # Emit the index of the next dispatch |
||
188 | # function. Then add all the |
||
189 | # dispatch functions for this leaf |
||
190 | # node to the dispatch function |
||
191 | # lookup table. |
||
192 | |||
193 | print ' LEAF(%u),' % (len(self.lookup_table)) |
||
194 | |||
195 | for op in range(child_base_opcode, child_base_opcode + (1 << child_M)): |
||
196 | if self.functions.has_key(op): |
||
197 | func = self.functions[op] |
||
198 | size = func.command_fixed_length() |
||
199 | |||
200 | if func.glx_rop != 0: |
||
201 | size += 4 |
||
202 | |||
203 | size = ((size + 3) & ~3) |
||
204 | |||
205 | if func.has_variable_size_request(): |
||
206 | size_name = "__glX%sReqSize" % (func.name) |
||
207 | else: |
||
208 | size_name = "" |
||
209 | |||
210 | if func.glx_vendorpriv == op: |
||
211 | func_name = func.glx_vendorpriv_names[0] |
||
212 | else: |
||
213 | func_name = func.name |
||
214 | |||
215 | temp = [op, "__glXDisp_%s" % (func_name), "__glXDispSwap_%s" % (func_name), size, size_name] |
||
216 | else: |
||
217 | temp = [op, "NULL", "NULL", 0, ""] |
||
218 | |||
219 | self.lookup_table.append(temp) |
||
220 | else: |
||
221 | print ' %u,' % (child_index) |
||
222 | child_index += child[2] |
||
223 | |||
224 | child_base_opcode += 1 << child_M |
||
225 | |||
226 | print '' |
||
227 | |||
228 | child_index = base_entry |
||
229 | for child in children: |
||
230 | if child[1] != []: |
||
231 | self.dump_tree(child, base_opcode, remaining_bits - M, child_index, depth + 1) |
||
232 | child_index += child[2] |
||
233 | |||
234 | base_opcode += 1 << (remaining_bits - M) |
||
235 | |||
236 | |||
237 | def Print(self): |
||
238 | # Each dispatch table consists of two data structures. |
||
239 | # |
||
240 | # The first structure is an N-way tree where the opcode for |
||
241 | # the function is the key. Each node switches on a range of |
||
242 | # bits from the opcode. M bits are extracted from the opcde |
||
243 | # and are used as an index to select one of the N, where |
||
244 | # N = 2^M, children. |
||
245 | # |
||
246 | # The tree is stored as a flat array. The first value is the |
||
247 | # number of bits, M, used by the node. For inner nodes, the |
||
248 | # following 2^M values are indexes into the array for the |
||
249 | # child nodes. For leaf nodes, the followign 2^M values are |
||
250 | # indexes into the second data structure. |
||
251 | # |
||
252 | # If an inner node's child index is 0, the child is an empty |
||
253 | # leaf node. That is, none of the opcodes selectable from |
||
254 | # that child exist. Since most of the possible opcode space |
||
255 | # is unused, this allows compact data storage. |
||
256 | # |
||
257 | # The second data structure is an array of pairs of function |
||
258 | # pointers. Each function contains a pointer to a protocol |
||
259 | # decode function and a pointer to a byte-swapped protocol |
||
260 | # decode function. Elements in this array are selected by the |
||
261 | # leaf nodes of the first data structure. |
||
262 | # |
||
263 | # As the tree is traversed, an accumulator is kept. This |
||
264 | # accumulator counts the bits of the opcode consumed by the |
||
265 | # traversal. When accumulator + M = B, where B is the |
||
266 | # maximum number of bits in an opcode, the traversal has |
||
267 | # reached a leaf node. The traversal starts with the most |
||
268 | # significant bits and works down to the least significant |
||
269 | # bits. |
||
270 | # |
||
271 | # Creation of the tree is the most complicated part. At |
||
272 | # each node the elements are divided into groups of 2^M |
||
273 | # elements. The value of M selected is the smallest possible |
||
274 | # value where all of the groups are either empty or full, or |
||
275 | # the groups are a preset minimum size. If all the children |
||
276 | # of a node are non-empty leaf nodes, the children are merged |
||
277 | # to create a single leaf node that replaces the parent. |
||
278 | |||
279 | tree = self.divide_group(0, 0) |
||
280 | |||
281 | print '/*****************************************************************/' |
||
282 | print '/* tree depth = %u */' % (tree[3]) |
||
283 | print 'static const int_fast16_t %s_dispatch_tree[%u] = {' % (self.name_base, tree[2]) |
||
284 | self.dump_tree(tree, 0, self.max_bits, 0, 1) |
||
285 | print '};\n' |
||
286 | |||
287 | # After dumping the tree, dump the function lookup table. |
||
288 | |||
289 | print 'static const void *%s_function_table[%u][2] = {' % (self.name_base, len(self.lookup_table)) |
||
290 | index = 0 |
||
291 | for func in self.lookup_table: |
||
292 | opcode = func[0] |
||
293 | name = func[1] |
||
294 | name_swap = func[2] |
||
295 | |||
296 | print ' /* [% 3u] = %5u */ {%s, %s},' % (index, opcode, name, name_swap) |
||
297 | |||
298 | index += 1 |
||
299 | |||
300 | print '};\n' |
||
301 | |||
302 | if self.do_size_check: |
||
303 | var_table = [] |
||
304 | |||
305 | print 'static const int_fast16_t %s_size_table[%u][2] = {' % (self.name_base, len(self.lookup_table)) |
||
306 | index = 0 |
||
307 | var_table = [] |
||
308 | for func in self.lookup_table: |
||
309 | opcode = func[0] |
||
310 | fixed = func[3] |
||
311 | var = func[4] |
||
312 | |||
313 | if var != "": |
||
314 | var_offset = "%2u" % (len(var_table)) |
||
315 | var_table.append(var) |
||
316 | else: |
||
317 | var_offset = "~0" |
||
318 | |||
319 | print ' /* [%3u] = %5u */ {%3u, %s},' % (index, opcode, fixed, var_offset) |
||
320 | index += 1 |
||
321 | |||
322 | |||
323 | print '};\n' |
||
324 | |||
325 | |||
326 | print 'static const gl_proto_size_func %s_size_func_table[%u] = {' % (self.name_base, len(var_table)) |
||
327 | for func in var_table: |
||
328 | print ' %s,' % (func) |
||
329 | |||
330 | print '};\n' |
||
331 | |||
332 | |||
333 | print 'const struct __glXDispatchInfo %s_dispatch_info = {' % (self.name_base) |
||
334 | print ' %u,' % (self.max_bits) |
||
335 | print ' %s_dispatch_tree,' % (self.name_base) |
||
336 | print ' %s_function_table,' % (self.name_base) |
||
337 | if self.do_size_check: |
||
338 | print ' %s_size_table,' % (self.name_base) |
||
339 | print ' %s_size_func_table' % (self.name_base) |
||
340 | else: |
||
341 | print ' NULL,' |
||
342 | print ' NULL' |
||
343 | print '};\n' |
||
344 | return |
||
345 | |||
346 | |||
347 | class PrintGlxDispatchTables(glX_proto_common.glx_print_proto): |
||
348 | def __init__(self): |
||
349 | gl_XML.gl_print_base.__init__(self) |
||
350 | self.name = "glX_server_table.py (from Mesa)" |
||
351 | self.license = license.bsd_license_template % ( "(C) Copyright IBM Corporation 2005, 2006", "IBM") |
||
352 | |||
353 | self.rop_functions = function_table("Render", 1) |
||
354 | self.sop_functions = function_table("Single", 0) |
||
355 | self.vop_functions = function_table("VendorPriv", 0) |
||
356 | return |
||
357 | |||
358 | |||
359 | def printRealHeader(self): |
||
360 | print '#include |
||
361 | print '#include "glxserver.h"' |
||
362 | print '#include "glxext.h"' |
||
363 | print '#include "indirect_dispatch.h"' |
||
364 | print '#include "indirect_reqsize.h"' |
||
365 | print '#include "g_disptab.h"' |
||
366 | print '#include "indirect_table.h"' |
||
367 | print '' |
||
368 | return |
||
369 | |||
370 | |||
371 | def printBody(self, api): |
||
372 | for f in api.functionIterateAll(): |
||
373 | if not f.ignore and f.vectorequiv == None: |
||
374 | if f.glx_rop != 0: |
||
375 | self.rop_functions.append(f.glx_rop, f) |
||
376 | if f.glx_sop != 0: |
||
377 | self.sop_functions.append(f.glx_sop, f) |
||
378 | if f.glx_vendorpriv != 0: |
||
379 | self.vop_functions.append(f.glx_vendorpriv, f) |
||
380 | |||
381 | self.sop_functions.Print() |
||
382 | self.rop_functions.Print() |
||
383 | self.vop_functions.Print() |
||
384 | return |
||
385 | |||
386 | |||
387 | if __name__ == '__main__': |
||
388 | file_name = "gl_API.xml" |
||
389 | |||
390 | try: |
||
391 | (args, trail) = getopt.getopt(sys.argv[1:], "f:m") |
||
392 | except Exception,e: |
||
393 | show_usage() |
||
394 | |||
395 | mode = "table_c" |
||
396 | for (arg,val) in args: |
||
397 | if arg == "-f": |
||
398 | file_name = val |
||
399 | elif arg == "-m": |
||
400 | mode = val |
||
401 | |||
402 | if mode == "table_c": |
||
403 | printer = PrintGlxDispatchTables() |
||
404 | else: |
||
405 | show_usage() |
||
406 | |||
407 | |||
408 | api = gl_XML.parse_GL_API( file_name, glX_XML.glx_item_factory() ) |
||
409 | |||
410 | |||
411 | printer.Print( api )><>><>><>><>><>><>=>><>><>><>><>=>><>><>><>=>><>><> |