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 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 <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 "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 )