src/mesa/glapi/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 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                                                         temp = [op, "__glXDisp_%s" % (func.name), "__glXDispSwap_%s" % (func.name), size, size_name]
 211                                                 else:
 212                                                         temp = [op, "NULL", "NULL", 0, ""]
 213
 214                                                 self.lookup_table.append(temp)
 215                         else:
 216                                 print '    %u,' % (child_index)
 217                                 child_index += child[2]
 218
 219                         child_base_opcode += 1 << child_M
 220
 221                 print ''
 222
 223                 child_index = base_entry
 224                 for child in children:
 225                         if child[1] != []:
 226                                 self.dump_tree(child, base_opcode, remaining_bits - M, child_index, depth + 1)
 227                                 child_index += child[2]
 228
 229                         base_opcode += 1 << (remaining_bits - M)
 230
 231
 232         def Print(self):
 233                 # Each dispatch table consists of two data structures.
 234                 #
 235                 # The first structure is an N-way tree where the opcode for
 236                 # the function is the key.  Each node switches on a range of
 237                 # bits from the opcode.  M bits are extracted from the opcde
 238                 # and are used as an index to select one of the N, where
 239                 # N = 2^M, children.
 240                 #
 241                 # The tree is stored as a flat array.  The first value is the
 242                 # number of bits, M, used by the node.  For inner nodes, the
 243                 # following 2^M values are indexes into the array for the
 244                 # child nodes.  For leaf nodes, the followign 2^M values are
 245                 # indexes into the second data structure.
 246                 #
 247                 # If an inner node's child index is 0, the child is an empty
 248                 # leaf node.  That is, none of the opcodes selectable from
 249                 # that child exist.  Since most of the possible opcode space
 250                 # is unused, this allows compact data storage.
 251                 #
 252                 # The second data structure is an array of pairs of function
 253                 # pointers.  Each function contains a pointer to a protocol
 254                 # decode function and a pointer to a byte-swapped protocol
 255                 # decode function.  Elements in this array are selected by the
 256                 # leaf nodes of the first data structure.
 257                 #
 258                 # As the tree is traversed, an accumulator is kept.  This
 259                 # accumulator counts the bits of the opcode consumed by the
 260                 # traversal.  When accumulator + M = B, where B is the
 261                 # maximum number of bits in an opcode, the traversal has
 262                 # reached a leaf node.  The traversal starts with the most
 263                 # significant bits and works down to the least significant
 264                 # bits.
 265                 #
 266                 # Creation of the tree is the most complicated part.  At
 267                 # each node the elements are divided into groups of 2^M
 268                 # elements.  The value of M selected is the smallest possible
 269                 # value where all of the groups are either empty or full, or
 270                 # the groups are a preset minimum size.  If all the children
 271                 # of a node are non-empty leaf nodes, the children are merged
 272                 # to create a single leaf node that replaces the parent.
 273
 274                 tree = self.divide_group(0, 0)
 275
 276                 print '/*****************************************************************/'
 277                 print '/* tree depth = %u */' % (tree[3])
 278                 print 'static const int_fast16_t %s_dispatch_tree[%u] = {' % (self.name_base, tree[2])
 279                 self.dump_tree(tree, 0, self.max_bits, 0, 1)
 280                 print '};\n'
 281
 282                 # After dumping the tree, dump the function lookup table.
 283
 284                 print 'static const void *%s_function_table[%u][2] = {' % (self.name_base, len(self.lookup_table))
 285                 index = 0
 286                 for func in self.lookup_table:
 287                         opcode = func[0]
 288                         name = func[1]
 289                         name_swap = func[2]
 290
 291                         print '    /* [% 3u] = %5u */ {%s, %s},' % (index, opcode, name, name_swap)
 292
 293                         index += 1
 294
 295                 print '};\n'
 296
 297                 if self.do_size_check:
 298                         var_table = []
 299
 300                         print 'static const int_fast16_t %s_size_table[%u][2] = {' % (self.name_base, len(self.lookup_table))
 301                         index = 0
 302                         var_table = []
 303                         for func in self.lookup_table:
 304                                 opcode = func[0]
 305                                 fixed = func[3]
 306                                 var = func[4]
 307
 308                                 if var != "":
 309                                         var_offset = "%2u" % (len(var_table))
 310                                         var_table.append(var)
 311                                 else:
 312                                         var_offset = "~0"
 313
 314                                 print '    /* [%3u] = %5u */ {%3u, %s},' % (index, opcode, fixed, var_offset)
 315                                 index += 1
 316
 317
 318                         print '};\n'
 319
 320
 321                         print 'static const gl_proto_size_func %s_size_func_table[%u] = {' % (self.name_base, len(var_table))
 322                         for func in var_table:
 323                                 print '   %s,' % (func)
 324
 325                         print '};\n'
 326
 327
 328                 print 'const struct __glXDispatchInfo %s_dispatch_info = {' % (self.name_base)
 329                 print '    %u,' % (self.max_bits)
 330                 print '    %s_dispatch_tree,' % (self.name_base)
 331                 print '    %s_function_table,' % (self.name_base)
 332                 if self.do_size_check:
 333                         print '    %s_size_table,' % (self.name_base)
 334                         print '    %s_size_func_table' % (self.name_base)
 335                 else:
 336                         print '    NULL,'
 337                         print '    NULL'
 338                 print '};\n'
 339                 return
 340
 341
 342 class PrintGlxDispatchTables(glX_proto_common.glx_print_proto):
 343         def __init__(self):
 344                 gl_XML.gl_print_base.__init__(self)
 345                 self.name = "glX_server_table.py (from Mesa)"
 346                 self.license = license.bsd_license_template % ( "(C) Copyright IBM Corporation 2005, 2006", "IBM")
 347
 348                 self.rop_functions = function_table("Render", 1)
 349                 self.sop_functions = function_table("Single", 0)
 350                 self.vop_functions = function_table("VendorPriv", 0)
 351                 return
 352
 353
 354         def printRealHeader(self):
 355                 print '#include <inttypes.h>'
 356                 print '#include "glxserver.h"'
 357                 print '#include "glxext.h"'
 358                 print '#include "indirect_dispatch.h"'
 359                 print '#include "indirect_reqsize.h"'
 360                 print '#include "g_disptab.h"'
 361                 print '#include "indirect_table.h"'
 362                 print ''
 363                 return
 364
 365
 366         def printBody(self, api):
 367                 for f in api.functionIterateAll():
 368                         if not f.ignore and f.vectorequiv == None:
 369                                 if f.glx_rop != 0:
 370                                         self.rop_functions.append(f.glx_rop, f)
 371                                 elif f.glx_sop != 0:
 372                                         self.sop_functions.append(f.glx_sop, f)
 373                                 elif f.glx_vendorpriv != 0:
 374                                         self.vop_functions.append(f.glx_vendorpriv, f)
 375
 376                 self.sop_functions.Print()
 377                 self.rop_functions.Print()
 378                 self.vop_functions.Print()
 379                 return
 380
 381
 382 if __name__ == '__main__':
 383         file_name = "gl_API.xml"
 384
 385         try:
 386                 (args, trail) = getopt.getopt(sys.argv[1:], "f:m")
 387         except Exception,e:
 388                 show_usage()
 389
 390         mode = "table_c"
 391         for (arg,val) in args:
 392                 if arg == "-f":
 393                         file_name = val
 394                 elif arg == "-m":
 395                         mode = val
 396
 397         if mode == "table_c":
 398                 printer = PrintGlxDispatchTables()
 399         else:
 400                 show_usage()
 401
 402
 403         api = gl_XML.parse_GL_API( file_name, glX_XML.glx_item_factory() )
 404
 405
 406         printer.Print( api )