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 gl_XML, glX_XML, glX_proto_common, license 29import sys, getopt 30 31 32def 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 41def 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 52class 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 347class 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 <inttypes.h>' 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 "indirect_table.h"' 366 print '' 367 return 368 369 370 def printBody(self, api): 371 for f in api.functionIterateAll(): 372 if not f.ignore and f.vectorequiv == None: 373 if f.glx_rop != 0: 374 self.rop_functions.append(f.glx_rop, f) 375 if f.glx_sop != 0: 376 self.sop_functions.append(f.glx_sop, f) 377 if f.glx_vendorpriv != 0: 378 self.vop_functions.append(f.glx_vendorpriv, f) 379 380 self.sop_functions.Print() 381 self.rop_functions.Print() 382 self.vop_functions.Print() 383 return 384 385 386if __name__ == '__main__': 387 file_name = "gl_API.xml" 388 389 try: 390 (args, trail) = getopt.getopt(sys.argv[1:], "f:m") 391 except Exception,e: 392 show_usage() 393 394 mode = "table_c" 395 for (arg,val) in args: 396 if arg == "-f": 397 file_name = val 398 elif arg == "-m": 399 mode = val 400 401 if mode == "table_c": 402 printer = PrintGlxDispatchTables() 403 else: 404 show_usage() 405 406 407 api = gl_XML.parse_GL_API( file_name, glX_XML.glx_item_factory() ) 408 409 410 printer.Print( api ) 411