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 <idr@us.ibm.com> 27 28import argparse 29 30import gl_XML, glX_XML, glX_proto_common, license 31 32 33def log2(value): 34 for i in range(0, 30): 35 p = 1 << i 36 if p >= value: 37 return i 38 39 return -1 40 41 42def round_down_to_power_of_two(n): 43 """Returns the nearest power-of-two less than or equal to n.""" 44 45 for i in range(30, 0, -1): 46 p = 1 << i 47 if p <= n: 48 return p 49 50 return -1 51 52 53class function_table: 54 def __init__(self, name, do_size_check): 55 self.name_base = name 56 self.do_size_check = do_size_check 57 58 59 self.max_bits = 1 60 self.next_opcode_threshold = (1 << self.max_bits) 61 self.max_opcode = 0 62 63 self.functions = {} 64 self.lookup_table = [] 65 66 # Minimum number of opcodes in a leaf node. 67 self.min_op_bits = 3 68 self.min_op_count = (1 << self.min_op_bits) 69 return 70 71 72 def append(self, opcode, func): 73 self.functions[opcode] = func 74 75 if opcode > self.max_opcode: 76 self.max_opcode = opcode 77 78 if opcode > self.next_opcode_threshold: 79 bits = log2(opcode) 80 if (1 << bits) <= opcode: 81 bits += 1 82 83 self.max_bits = bits 84 self.next_opcode_threshold = 1 << bits 85 return 86 87 88 def divide_group(self, min_opcode, total): 89 """Divide the group starting min_opcode into subgroups. 90 Returns a tuple containing the number of bits consumed by 91 the node, the list of the children's tuple, and the number 92 of entries in the final array used by this node and its 93 children, and the depth of the subtree rooted at the node.""" 94 95 remaining_bits = self.max_bits - total 96 next_opcode = min_opcode + (1 << remaining_bits) 97 empty_children = 0 98 99 for M in range(0, remaining_bits): 100 op_count = 1 << (remaining_bits - M); 101 child_count = 1 << M; 102 103 empty_children = 0 104 full_children = 0 105 for i in range(min_opcode, next_opcode, op_count): 106 used = 0 107 empty = 0 108 109 for j in range(i, i + op_count): 110 if self.functions.has_key(j): 111 used += 1; 112 else: 113 empty += 1; 114 115 116 if empty == op_count: 117 empty_children += 1 118 119 if used == op_count: 120 full_children += 1 121 122 if (empty_children > 0) or (full_children == child_count) or (op_count <= self.min_op_count): 123 break 124 125 126 # If all the remaining bits are used by this node, as is the 127 # case when M is 0 or remaining_bits, the node is a leaf. 128 129 if (M == 0) or (M == remaining_bits): 130 return [remaining_bits, [], 0, 0] 131 else: 132 children = [] 133 count = 1 134 depth = 1 135 all_children_are_nonempty_leaf_nodes = 1 136 for i in range(min_opcode, next_opcode, op_count): 137 n = self.divide_group(i, total + M) 138 139 if not (n[1] == [] and not self.is_empty_leaf(i, n[0])): 140 all_children_are_nonempty_leaf_nodes = 0 141 142 children.append(n) 143 count += n[2] + 1 144 145 if n[3] >= depth: 146 depth = n[3] + 1 147 148 # If all of the child nodes are non-empty leaf nodes, pull 149 # them up and make this node a leaf. 150 151 if all_children_are_nonempty_leaf_nodes: 152 return [remaining_bits, [], 0, 0] 153 else: 154 return [M, children, count, depth] 155 156 157 def is_empty_leaf(self, base_opcode, M): 158 for op in range(base_opcode, base_opcode + (1 << M)): 159 if self.functions.has_key(op): 160 return 0 161 break 162 163 return 1 164 165 166 def dump_tree(self, node, base_opcode, remaining_bits, base_entry, depth): 167 M = node[0] 168 children = node[1] 169 child_M = remaining_bits - M 170 171 172 # This actually an error condition. 173 if children == []: 174 return 175 176 print ' /* [%u] -> opcode range [%u, %u], node depth %u */' % (base_entry, base_opcode, base_opcode + (1 << remaining_bits), depth) 177 print ' %u,' % (M) 178 179 base_entry += (1 << M) + 1 180 181 child_index = base_entry 182 child_base_opcode = base_opcode 183 for child in children: 184 if child[1] == []: 185 if self.is_empty_leaf(child_base_opcode, child_M): 186 print ' EMPTY_LEAF,' 187 else: 188 # Emit the index of the next dispatch 189 # function. Then add all the 190 # dispatch functions for this leaf 191 # node to the dispatch function 192 # lookup table. 193 194 print ' LEAF(%u),' % (len(self.lookup_table)) 195 196 for op in range(child_base_opcode, child_base_opcode + (1 << child_M)): 197 if self.functions.has_key(op): 198 func = self.functions[op] 199 size = func.command_fixed_length() 200 201 if func.glx_rop != 0: 202 size += 4 203 204 size = ((size + 3) & ~3) 205 206 if func.has_variable_size_request(): 207 size_name = "__glX%sReqSize" % (func.name) 208 else: 209 size_name = "" 210 211 if func.glx_vendorpriv == op: 212 func_name = func.glx_vendorpriv_names[0] 213 else: 214 func_name = func.name 215 216 temp = [op, "__glXDisp_%s" % (func_name), "__glXDispSwap_%s" % (func_name), size, size_name] 217 else: 218 temp = [op, "NULL", "NULL", 0, ""] 219 220 self.lookup_table.append(temp) 221 else: 222 print ' %u,' % (child_index) 223 child_index += child[2] 224 225 child_base_opcode += 1 << child_M 226 227 print '' 228 229 child_index = base_entry 230 for child in children: 231 if child[1] != []: 232 self.dump_tree(child, base_opcode, remaining_bits - M, child_index, depth + 1) 233 child_index += child[2] 234 235 base_opcode += 1 << (remaining_bits - M) 236 237 238 def Print(self): 239 # Each dispatch table consists of two data structures. 240 # 241 # The first structure is an N-way tree where the opcode for 242 # the function is the key. Each node switches on a range of 243 # bits from the opcode. M bits are extracted from the opcde 244 # and are used as an index to select one of the N, where 245 # N = 2^M, children. 246 # 247 # The tree is stored as a flat array. The first value is the 248 # number of bits, M, used by the node. For inner nodes, the 249 # following 2^M values are indexes into the array for the 250 # child nodes. For leaf nodes, the followign 2^M values are 251 # indexes into the second data structure. 252 # 253 # If an inner node's child index is 0, the child is an empty 254 # leaf node. That is, none of the opcodes selectable from 255 # that child exist. Since most of the possible opcode space 256 # is unused, this allows compact data storage. 257 # 258 # The second data structure is an array of pairs of function 259 # pointers. Each function contains a pointer to a protocol 260 # decode function and a pointer to a byte-swapped protocol 261 # decode function. Elements in this array are selected by the 262 # leaf nodes of the first data structure. 263 # 264 # As the tree is traversed, an accumulator is kept. This 265 # accumulator counts the bits of the opcode consumed by the 266 # traversal. When accumulator + M = B, where B is the 267 # maximum number of bits in an opcode, the traversal has 268 # reached a leaf node. The traversal starts with the most 269 # significant bits and works down to the least significant 270 # bits. 271 # 272 # Creation of the tree is the most complicated part. At 273 # each node the elements are divided into groups of 2^M 274 # elements. The value of M selected is the smallest possible 275 # value where all of the groups are either empty or full, or 276 # the groups are a preset minimum size. If all the children 277 # of a node are non-empty leaf nodes, the children are merged 278 # to create a single leaf node that replaces the parent. 279 280 tree = self.divide_group(0, 0) 281 282 print '/*****************************************************************/' 283 print '/* tree depth = %u */' % (tree[3]) 284 print 'static const int_fast16_t %s_dispatch_tree[%u] = {' % (self.name_base, tree[2]) 285 self.dump_tree(tree, 0, self.max_bits, 0, 1) 286 print '};\n' 287 288 # After dumping the tree, dump the function lookup table. 289 290 print 'static const void *%s_function_table[%u][2] = {' % (self.name_base, len(self.lookup_table)) 291 index = 0 292 for func in self.lookup_table: 293 opcode = func[0] 294 name = func[1] 295 name_swap = func[2] 296 297 print ' /* [% 3u] = %5u */ {%s, %s},' % (index, opcode, name, name_swap) 298 299 index += 1 300 301 print '};\n' 302 303 if self.do_size_check: 304 var_table = [] 305 306 print 'static const int_fast16_t %s_size_table[%u][2] = {' % (self.name_base, len(self.lookup_table)) 307 index = 0 308 var_table = [] 309 for func in self.lookup_table: 310 opcode = func[0] 311 fixed = func[3] 312 var = func[4] 313 314 if var != "": 315 var_offset = "%2u" % (len(var_table)) 316 var_table.append(var) 317 else: 318 var_offset = "~0" 319 320 print ' /* [%3u] = %5u */ {%3u, %s},' % (index, opcode, fixed, var_offset) 321 index += 1 322 323 324 print '};\n' 325 326 327 print 'static const gl_proto_size_func %s_size_func_table[%u] = {' % (self.name_base, len(var_table)) 328 for func in var_table: 329 print ' %s,' % (func) 330 331 print '};\n' 332 333 334 print 'const struct __glXDispatchInfo %s_dispatch_info = {' % (self.name_base) 335 print ' %u,' % (self.max_bits) 336 print ' %s_dispatch_tree,' % (self.name_base) 337 print ' %s_function_table,' % (self.name_base) 338 if self.do_size_check: 339 print ' %s_size_table,' % (self.name_base) 340 print ' %s_size_func_table' % (self.name_base) 341 else: 342 print ' NULL,' 343 print ' NULL' 344 print '};\n' 345 return 346 347 348class PrintGlxDispatchTables(glX_proto_common.glx_print_proto): 349 def __init__(self): 350 gl_XML.gl_print_base.__init__(self) 351 self.name = "glX_server_table.py (from Mesa)" 352 self.license = license.bsd_license_template % ( "(C) Copyright IBM Corporation 2005, 2006", "IBM") 353 354 self.rop_functions = function_table("Render", 1) 355 self.sop_functions = function_table("Single", 0) 356 self.vop_functions = function_table("VendorPriv", 0) 357 return 358 359 360 def printRealHeader(self): 361 print '#include <inttypes.h>' 362 print '#include "glxserver.h"' 363 print '#include "glxext.h"' 364 print '#include "indirect_dispatch.h"' 365 print '#include "indirect_reqsize.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 387def _parser(): 388 """Parse arguments and return namespace.""" 389 parser = argparse.ArgumentParser() 390 parser.add_argument('-f', 391 dest='filename', 392 default='gl_API.xml', 393 help='An XML file describing an API.') 394 return parser.parse_args() 395 396 397if __name__ == '__main__': 398 args = _parser() 399 printer = PrintGlxDispatchTables() 400 api = gl_XML.parse_GL_API(args.filename, glX_XML.glx_item_factory()) 401 402 printer.Print(api) 403