src/mapi/glapi/gen/glX_server_table.py

   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
  28 import argparse
  29
  30 import gl_XML, glX_XML, glX_proto_common, license
  31
  32
  33 def 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
  42 def 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
  53 class 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
 348 class 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
 387 def _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
 397 if __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)