Modified byte-ordering used for instruction decoding for ARM64.
[dyninst.git] / instructionAPI / aarch64_manual_pareser.py
1 #!/usr/bin/env python
2 # encoding: utf-8
3
4 """
5 Author: Steve Song
6 Email:  songxi.buaa@gmail.com
7 Date:   Sep 2015
8 """
9
10 import os, sys
11 from sets import Set
12 from array import *
13
14 #######################################
15 # a flag for vector and floating points
16 #######################################
17 #VEC_SIMD_SWITCH = False
18 VEC_SIMD_SWITCH = True
19
20 ####################################
21 # dir to store aarch64 ISA xml files
22 ####################################
23 ISA_dir = '/p/paradyn/arm/arm-download-1350222/AR100-DA-70000-r0p0-00rel10/AR100-DA-70000-r0p0-00rel10/ISA_xml/ISA_xml_v2_00rel11/'
24 files_dir = os.listdir(ISA_dir)
25
26 flagFieldsSet = set(['S', 'imm', 'option', 'opt', 'N', 'cond', 'sz', 'size', 'type'])
27 #forwardFieldsSet = set([ ])
28
29 insn_set = Set()
30 fp_insn_set = Set()
31
32 masksArray = list()
33 encodingsArray = list()
34
35 class Opcode:
36     def __init__(self, ISA_dir, vec_FP=True):
37         self.op_set = Set()
38         self.insn_set = Set()
39         self.fp_insn_set =Set()
40         self.vec_FP = vec_FP
41         self.base_insn_file = open(ISA_dir+'index.xml')
42         if self.vec_FP == True:
43             self.vec_FP_insn_file = open(ISA_dir+'fpsimdindex.xml')
44
45     # to get op IDs
46     def printP(self, op):
47         print '  aarch64_op_'+op+','
48
49     ##############################
50     # parse xml files
51     # get opcodes
52     ##############################
53     def getOpcodes(self):
54         for lines in self.base_insn_file:
55             if lines.startswith("    <iform"):
56                 self.op_set.add(lines.split('"')[1].split('.xml')[0].split('_')[0])
57                 self.insn_set.add(lines.split('"')[1].split('.xml')[0])
58
59         if self.vec_FP == True:
60             for lines in self.vec_FP_insn_file:
61                 if lines.startswith("    <iform"):
62                     self.op_set.add(lines.split('"')[1].split('.xml')[0].split('_')[0])
63                     self.insn_set.add(lines.split('"')[1].split('.xml')[0])
64                     self.fp_insn_set.add(lines.split('"')[1].split('.xml')[0])
65
66     def printOpcodes(self):
67         self.getOpcodes()
68         print('enum {')
69         self.printP('INVALID')
70         self.printP('extended')
71
72         for ele in sorted(self.insn_set):
73             self.printP(ele)
74
75         print('}')
76         print 'number of instructions: ', len(self.insn_set)
77
78     def get_insn_set(self):
79         return self.insn_set
80
81     def get_fp_insn_set(self):
82         return self.fp_insn_set
83
84 #################################
85 # to find all control field names
86 # discarded
87 #################################
88 '''
89 control_field_set = Set()
90 non_ctl_field_set = Set(['sf'] )
91
92 def getDecodeFieldNames():
93
94     decodeFile = open(ISA_dir + 'encodingindex.xml')
95
96     startReadDecodeField = False
97
98     for line in decodeFile:
99         if startReadDecodeField == True:
100             if line.find('\"bitfields\"') != -1:
101                 control_field_set.add(line.split('>')[1].split('<')[0])
102
103         if line.find('Decode fields') !=-1:
104             startReadDecodeField = True
105
106         if line.find('</thread>')!=-1 and startReadDecodeField == True:
107             startReadDecodeField = False
108
109         if line.find('funcgrouphearder') !=-1 and line.find('simd-dp')!=-1:
110             break
111
112     control_field_set.difference_update(non_ctl_field_set)
113     print sorted(control_field_set)
114     '''
115
116
117 def shifting(bitlist):
118     out = 0
119     for bit in bitlist:
120         out = (out<<1) | (bit=='1' )
121     return out
122
123 ##########################
124 # parse xml files and get
125 # opcodes and operands
126 ##########################
127
128 def getOperand_Insn(line):
129     '''
130     analyze one <box> line </box> to get operand
131     '''
132     for field in line.split(' '):
133         if field.find('name') != -1 and field.find('usename') == -1:
134             opname = field.split('\"')[1]
135             if opname.find('imm') !=-1:
136                 opname = 'imm'
137             return opname
138         # else continue do nothing
139
140 def isRnUpdated(line):
141     if line.find('post-idx') != -1 or line.find('pre-idx') !=-1:
142         return True;
143     return False;
144
145 def ifNeedToSetFlags(line):
146     if line.find('<iclass ') != -1 :
147         for field in line.split(' '):
148             if field.find('id=') !=-1:
149                 if field.split('\"')[1] == 's':
150                     return True
151
152     if line.find('<regdiagram') != -1:
153         if line.find('float/compare') != -1:
154             return True
155     return False
156
157
158 class OpTable:
159     global files_dir
160
161     def __init__(self):
162         self.masksArray = list()
163         self.encodingsArray = list()
164         self.insnArray = list()
165         self.operandsArray = list()
166         self.operandsSet = set()
167         self.insn_unallocated = (2**28+2**27)
168
169     def getTable(self):
170         return self.masksArray, self.encodingsArray, self.insnArray, self.operandsArray
171
172     def analyzeEncodeBit(self, encodeBit, maskBit, encodingArray, operands_pos_Insn, reserve_operand_pos, maskStartBit):
173         if encodeBit == '1' or encodeBit == '0':
174             maskBit[31-maskStartBit] = '1'
175             encodingArray[31-maskStartBit] = encodeBit
176
177         elif encodeBit == '(1)':
178             maskBit[31-maskStartBit] = '1'
179             encodingArray[31-maskStartBit] = '1'
180
181         elif encodeBit == '(0)':
182             maskBit[31-maskStartBit] = '1'
183             encodingArray[31-maskStartBit] = '0'
184
185         # if it is 'x', we set it as not a control field
186         # and append the reserved operand to the list
187         elif encodeBit == 'x':
188             maskBit[31-maskStartBit] = '0'
189             encodingArray[31-maskStartBit] = '0'
190
191             operands_pos_Insn.append(reserve_operand_pos)
192             if reserve_operand_pos[0] not in self.operandsSet:
193                 self.operandsSet.add(reserve_operand_pos[0])
194
195         # if it is blank, same as 'x', do late operand appending
196         elif encodeBit == '' or encodeBit.startswith('!=') != -1:
197             operands_pos_Insn.append(reserve_operand_pos)
198             if reserve_operand_pos[0] not in self.operandsSet:
199                 self.operandsSet.add(reserve_operand_pos[0])
200
201         else:
202             #if not encodeBit.startswith('!='):
203             print '[WARN] something not has been analyzed:'+ encodeBit
204
205
206     # to get the encoding table
207     def printOpTable(self ):
208
209         self.masksArray.append(self.insn_unallocated)
210         self.encodingsArray.append(int(0))
211         self.insnArray.append('INVALID')
212         self.operandsArray.append('')
213
214         indexOfInsn = 1
215
216         print 0, '%22s'%'INVALID',  '%34s'%bin(self.insn_unallocated), '(', hex(self.insn_unallocated), ')'
217
218         for file in sorted(files_dir):
219
220             if file.endswith('.xml'):
221                 instruction = file.split('.xml')[0]
222
223                 if instruction in insn_set:
224                     #print file
225                     curFile = open(ISA_dir+file)
226
227                     startBox = False
228
229                     startDiagram = False
230                     maskBit = list('0'*32)
231                     encodingArray = list('0'*32)
232                     operands_pos_Insn = list()
233
234                     reserve_operand_pos = list()
235                     maskStartBit = 31
236                     isRnUp = False
237                     needToSetFlags = False
238
239                     # to analyze lines , do iterative passes#
240                     for line in curFile:
241
242                         if line.find('<iclass ') != -1 :
243                             needToSetFlags = ifNeedToSetFlags(line)
244
245                         # diagram starts #
246                         if line.find('<regdiagram')!=-1:
247                             isRnUp = isRnUpdated(line)
248                             if needToSetFlags == False:
249                                 needToSetFlags = ifNeedToSetFlags(line)
250                             startDiagram = True
251                             continue
252
253                         # end of diagram #
254                         if line.find('</regdiagram')!=-1:
255                             if needToSetFlags == True:
256                                 operands_pos_Insn.insert(0, ('setFlags',) )
257                             self.printInstnEntry(maskBit, encodingArray, indexOfInsn, instruction, operands_pos_Insn)
258
259                             startDiagram = False
260                             maskBit = list('0'*32)
261                             encodingArray = list('0'*32)
262                             operands_pos_Insn = list()
263
264                             indexOfInsn +=1
265                             continue
266
267                         # analyze each box #
268                         if startDiagram == True and line.find('<box') != -1:
269                             #name, start bit, length
270                             for x in line.split(' '):
271                                 if x.find('hibit') != -1:
272                                     maskStartBit = int(x.split('\"')[1])
273                                     break
274
275                             # reserve the operand and position information
276                             # it only will be appended if the encoding fields are not defined unique
277                             reserve_operand_pos = getOperandValues(line, instruction, isRnUp)
278                             startBox = True
279
280                         # end of box #
281                         if line.find('</box') != -1:
282                             startBox = False
283                             continue
284
285                         # read box content #
286                         if startBox == True:
287                             # start of <c>
288                             if line.find('<c') != -1:
289                                 encodeBit = line.split('>')[1].split('<')[0]
290                                 self.analyzeEncodeBit(encodeBit, maskBit, encodingArray, operands_pos_Insn, reserve_operand_pos, maskStartBit)
291                                 maskStartBit = maskStartBit - 1
292
293
294                     # end of each line #
295
296     ####################################
297     # generate instructions
298     ####################################
299     def printInstnEntry(self, maskBit, encodingArray, index, instruction, operands):
300
301         # print instruction and encoding mask per file
302         maskBitInt = int(''.join(maskBit), 2)
303         encodingBitInt = int( ''.join(encodingArray),2)
304
305         self.masksArray.append(maskBitInt)
306         self.encodingsArray.append(encodingBitInt)
307         self.insnArray.append(instruction)
308         self.operandsArray.append(operands)
309
310         print index, "%22s"%instruction, '\t', ''.join(maskBit),'(', hex(maskBitInt),')', '\t', ''.join(encodingArray), '(', hex(encodingBitInt), ')', operands
311
312
313     def isLDST(self, insn):
314         if insn.startswith('ld') or insn.startswith('st'):
315             return True
316         return False
317
318     def getRegWidth(self, insn):
319
320         insnMnemonic = insn.split('_')[0]
321         # ld/st register, do nothing
322         if insnMnemonic.endswith('b') and not insnMnemonic.endswith('sb'):
323             return 32
324         elif insnMnemonic.endswith('h') and not insnMnemonic.endswith('sh'):
325             return 32
326         elif insnMnemonic.endswith('sb'):
327             return 64
328         elif insnMnemonic.endswith('sh'):
329             return 64
330         elif insnMnemonic.endswith('sw'):
331             return 64
332         elif insnMnemonic.endswith('r'):
333             return 64
334         elif insnMnemonic.endswith('p'):
335             return 64
336         else :
337             return 128
338             #print '[WARN] not recognized instruction:', insn
339         return 64
340
341     def isSIMD(self, insn):
342         if insn.find('simd') != -1:
343             return True
344         return False
345
346
347     ####################################
348     # generate the c++ code
349     # which builds the instruction table
350     ####################################
351     def buildInsnTable(self):
352         assert len(self.masksArray) == len(self.encodingsArray) ==len(self.insnArray)
353         print len(self.insnArray)
354         print '*** instruction table ***'
355
356         for i in range(0, len(self.insnArray)):
357             instruction = self.insnArray[i]
358
359             if len(self.operandsArray[i]) == 0:
360                 operands = 'operandSpec()'
361             else:
362                 operands = 'list_of'
363
364                 # recognize FP and SIMD
365                 if instruction in fp_insn_set:
366                     if self.isSIMD(instruction) == False:
367                         self.operandsArray[i].insert(0, ('setFPMode',) )
368                     else:
369                         self.operandsArray[i].insert(0, ('setSIMDMode',) )
370
371                 if self.isLDST(instruction) == True:
372                     if self.getRegWidth(instruction) == 32 or self.getRegWidth(instruction) == 64:
373                         self.operandsArray[i].insert(0, ('setRegWidth',) )
374                     else:
375                         if self.getRegWidth(instruction) != 128:
376                             print '[WARN] unknown width'
377
378                 for index, operand in enumerate(self.operandsArray[i]):
379                     # this is solution the compiler bug
380                     # if OPRimm<x, y> appears in the first place of the list
381                     if len(operand) != 1 and index == 0:
382                         operands += '( (operandFactory) fn('
383                     else:
384                         operands += '( fn('
385
386                     if len(operand) != 1:
387                         operands += 'OPR'+operand[0]+'<'+ str(operand[1][0])+' COMMA ' + str(operand[1][1])+'>'
388                     else:
389                         curOperandName = operand[0]
390                         if curOperandName.startswith('set'):
391                             operands += curOperandName
392                         else:
393                             operands += 'OPR'+ curOperandName
394
395                     operands += ') )'
396
397             print '\tmain_insn_table.push_back(aarch64_insn_entry(aarch64_op_'+ self.insnArray[i]+', \t\"'+ self.insnArray[i].split('_')[0]+'\",\t'+ operands +' ));'
398
399 ##################
400 # a helper function
401 # clapse(1001, 1101) => (101 & 111) => 101 => 5
402 ##################
403 def clapseMask(encoding, curMask):
404     ret = 0
405     while curMask!=0:
406         if curMask & 0x80000000 != 0:
407             ret = (ret<<1)|((encoding & 0x80000000)>>31)
408         curMask = (curMask << 1)&0xffffffff
409         encoding = (encoding << 1)&0xffffffff
410     return ret
411
412 ####################################
413 # generate the c++ code
414 # which builds the decoding table
415 ####################################
416 def printDecodertable(entryToPlace, curMask=0, entryList=list(), index=-1 ):
417     entries = 'map_list_of'
418     if len(entryList) == 0:
419         entries = 'branchMap()'
420     else:
421         for ent in entryList:
422             entries += '('+str(ent[0])+','+str(ent[1])+')'
423
424     print '\tmain_decoder_table['+str(entryToPlace)+']=aarch64_mask_entry('+str(hex(curMask))+', '+entries+','+str(index)+');'
425
426 def num1sInMask(x):
427     mask = masksArray[x]
428     num = 0
429     while mask != 0:
430         if mask &1 == 1:
431             num +=1
432         mask = mask>>1
433     return int(num)
434
435 def alias_comparator( x, y ):
436     return num1sInMask(x) - num1sInMask(y)
437
438 class DecodeTable:
439     global masksArray
440     global encodingsArray
441     global insnArray
442     global operandsArray
443
444     ##########################
445     # generate decoding tree #
446     ##########################
447     def __init__(self):
448         self.numOfLeafNodes=0
449         self.processedIndex = Set()
450         self.numNodes = 0
451         ####################################
452         # this is the init value that the instruction
453         # entry should start from. 0 is reserved for
454         # invalid insn.
455         ####################################
456         self.entryAvailable = 1
457
458     ###########################################
459     # arg-1 is self
460     # arg0 is the range of indexes in the instruction array
461     #   that you want to analyze
462     # arg1 is the bit mask that has been processed
463     # arg2 is the entry of the decoding table
464     #   where the current call should place for one decision node
465     ###########################################
466     def buildDecodeTable(self, inInsnIndex , processedMask, entryToPlace):
467
468         # guards, redundant
469         if entryToPlace > 2**32:
470             print '*** [WARN] should not reach here ***'
471             return
472
473         # terminated condition 1
474         if len(inInsnIndex) < 1:
475             print '*** [WARN] should not reach here ***'
476             return
477
478         # size of inInsnIndex is 1. This means we should generate a leaf node
479         if len(inInsnIndex) ==1:
480             printDecodertable(entryToPlace, 0, list() , inInsnIndex[0]);
481             self.numNodes += 1
482             #print insnArray[inInsnIndex[0]]
483             if inInsnIndex[0] in self.processedIndex:
484                 print '[WARN] index processed, repeated index is ', inInsnIndex[0]
485
486             self.processedIndex.add(inInsnIndex[0])
487             self.numOfLeafNodes +=1
488             return
489
490         validMaskBits = int(''.join('1'*32), 2)
491
492         # find the minimum common mask bit field
493         for i in inInsnIndex:
494             validMaskBits = validMaskBits & masksArray[i]
495
496         # eliminate the processed mask bit field
497         validMaskBits = validMaskBits&(~processedMask)
498         #print hex(validMaskBits), bin(validMaskBits)
499
500         # terminated condition 2
501         # if the mask we get is 0, this means we have a bunch of instructions
502         # sharing the same opcode. They are aliases actually.
503         # Group them together.
504         addMask = 0
505         if validMaskBits == 0:
506             # weak solution to aliases
507             self.numOfLeafNodes += len(inInsnIndex)
508
509             inInsnIndex.sort( cmp=alias_comparator )
510
511             for i in inInsnIndex:
512                 self.processedIndex.add(i)
513                 #print insnArray[i], '\t', bin( masksArray[i] ), '\t', bin(encodingsArray[i])
514             printDecodertable(entryToPlace, 0, list(), inInsnIndex[0]);
515             self.numNodes += 1
516             return
517
518             '''
519             for i in inInsnIndex:
520                 #print '%3d'%i+'%22s'%insnArray[i]+'%34s'%bin(masksArray[i])+'%34s'%bin(encodingsArray[i])
521                 addMask |= masksArray[i] &(~processedMask)
522                 #addMask ^= encodingsArray[i] &(~processedMask)
523
524             # handle alias, merge them into one node
525             if addMask == 0:
526                 numOfLeafNodes += len(inInsnIndex)
527                 for i in inInsnIndex:
528                     processedIndex.add(i)
529                 printDecodertable(entryToPlace, 0, list(), inInsnIndex[0]);
530                 numNodes += 1
531                 return
532             # handle more mask bits
533             else:
534                 validMaskBits = addMask
535                 #print bin(addMask)
536                 '''
537
538         # till here we should have got the mask bits
539         MSBmask = 0x80000000
540         curMask = 0
541         numCurMaskBit = 0
542
543         #print hex(validMaskBits)
544
545         # get currrent valid mask
546         # check bit one by one from MSB
547         for bit in range(0, 32):
548             if (MSBmask & validMaskBits) == 0 :
549                 validMaskBits = (validMaskBits << 1)
550             else:
551                 curMask |= 1<<(31-bit)
552                 validMaskBits = (validMaskBits << 1)
553                 numCurMaskBit += 1
554
555         #print 'cur mask', hex(curMask)
556
557         # should not be 0
558         if curMask == 0:
559             print "[WARN] mask is 0"
560             #print '%25s'%'processed mask'+'%35s'%bin(processedMask)
561             for i in inInsnIndex:
562                 print '%3d'%i+'%22s'%insnArray[i]+'%35s'%bin(masksArray[i])+'%35s'%bin(encodingsArray[i])
563             self.numOfLeafNodes+=len(inInsnIndex)
564             return
565
566
567         # update processed mask
568         processedMask = processedMask | curMask
569
570         indexList = [ ]
571         for i in range(0, 2**numCurMaskBit):
572             indexList.append([])
573
574         # generate the branches
575         # glue instructions to that branch
576         for index in inInsnIndex:
577             branchNo = clapseMask(encodingsArray[index] & curMask, curMask)
578             #print 'branchNo' ,branchNo
579             indexList[branchNo].append(index)
580
581         # get number of branches
582         # a trick to eliminate null branches
583         numBranch = 0
584         validIndexList = []
585         brNoinIndexList = 0
586         posToBrNo = list()
587         for i in indexList:
588             if len(i)!=0:
589                 numBranch+=1
590                 validIndexList.append(i)
591                 posToBrNo.append(brNoinIndexList)
592             brNoinIndexList += 1
593
594         # typedef mask_table vector<mask_entry>;
595         # assign entry number to that branch
596         entryList = []
597         for i in range(0, numBranch):
598             entryList.append( (posToBrNo[i], self.entryAvailable + i) )
599
600         # reserve room
601         self.entryAvailable += numBranch
602
603         printDecodertable(entryToPlace, curMask, entryList, -1);
604         self.numNodes += 1
605
606         """
607         print '%34s'%bin(curMask)
608         for i in zeroIndexes:
609             print '%34s'%bin(encodingsArray[i])
610
611         for i in oneIndexes:
612             print '%34s'%bin(encodingsArray[i])
613         """
614         #print validIndexList
615         for i in range(0, numBranch):
616             self.buildDecodeTable( validIndexList[i], processedMask, entryList[i][1])
617
618 ###############################################################
619 # the following section is for parsing and generating operands.
620 ###############################################################
621
622 def getOperandValues(line, instruction, isRnUp):
623     multiOperandSet = flagFieldsSet
624
625     if line.find(' name') != -1:
626         width = 1
627         tokens = line.split(' ')
628         for token in tokens:
629             if token.find('name')!=-1 and token.find('usename')== -1:
630                 name = token.split('\"')[1]
631                 if name.find('imm') != -1:
632                     name = 'imm'
633             if token.find('hibit')!=-1:
634                 bit = int(token.split('\"')[1])
635             if token.find('width') != -1:
636                 width = int(token.split('\"')[1])
637     else:
638         #print '*** [WARN] Blank operand field ***'
639         return ('', [0, 0])
640
641     if name.find('Rt') != -1 or name.find('Rt2') != -1 or name.find('Rn') !=-1:
642         if instruction.startswith('ld'):
643             name += 'L'
644
645         if instruction.startswith('st'):
646             name += 'S'
647
648     if instruction.startswith('ld') or instruction.startswith('st'):
649         if name.startswith('Rn'):
650             if isRnUp == True:
651                 name += 'U'
652
653     endbit = bit - (width-1)
654     if name in multiOperandSet:
655         return (name, [bit, endbit])
656     else:
657         return (name,)
658
659
660 def printOperandFuncs(operandsSet):
661     print 'operand function declares'
662     for operand in operandsSet:
663         print 'void '+ 'OPR'+operand + '(){ }'
664
665
666 def main():
667
668     ######################################
669     # get opcodes of GP instructions
670     # and FP/VEC instructions respectively
671     ######################################
672     opcodes = Opcode(ISA_dir, True)
673     opcodes.printOpcodes()
674     global insn_set
675     global fp_insn_set
676     insn_set = opcodes.get_insn_set()
677     fp_insn_set = opcodes.get_fp_insn_set()
678
679     #################################################################
680     # get instructions, opcodes, lists of operands
681     # each set is stored in an array
682     # indexes in the arrays are used to find the instruction you want
683     #################################################################
684     opTable = OpTable()
685     opTable.printOpTable()
686
687     ###############################################
688     # instruction table
689     # generate C++ code to build instruction tables
690     ###############################################
691     opTable.buildInsnTable()
692
693     global masksArray
694     global encodingsArray
695     global insnArray
696     global operandsArray
697     masksArray, encodingsArray, insnArray, operandsArray = opTable.getTable()
698
699     #########################################
700     # generate C++ code of operands functions
701     #########################################
702     print '*** operands ***'
703     print sorted(opTable.operandsSet)
704     printOperandFuncs(opTable.operandsSet)
705
706     ###########################################
707     # Decoder table.
708     # Generate C++ code to build decoding table.
709     # Basically, the generated stuff is a decision tree, which is represented in a map.
710     #
711     # Each entry stands for a decision node in the decision tree with a few or zero
712     #   branches. One branch contains a {Key, Value} pair. Key is used to index. Value is
713     #   the next entry number in the map, like a pointer.
714     #
715     # Binaries are passed to the root node first, and compared with the decision mask in
716     #   that node. Instrution binary does bit operation AND over the mask. The result of it
717     #   will be compared with the Key of the branches. Once matched to the Key, the instruction
718     #   will be passed to next decision node pointed by the branch.
719     #   Recursively do this, until to the leaf node.
720     #
721     # Each leaf node contains the index of the instruction array in the last field,
722     #   which holds the instruction entry.
723     ###########################################
724     print '*** decoder table ***'
725     validInsnIndex = list( range(0, len(opTable.insnArray) ) )
726     decodeTable = DecodeTable()
727     decodeTable.buildDecodeTable(validInsnIndex, 0 , 0)
728
729     ###############################
730     # some statistics for debugging
731     ###############################
732     print 'num of vaild leaves', decodeTable.numOfLeafNodes
733     allIndex = Set(range(0, len(opTable.insnArray)) )
734     print 'processed indexex: ', decodeTable.processedIndex, len(decodeTable.processedIndex)
735     print 'missing indexes:', sorted(allIndex - decodeTable.processedIndex), len(allIndex-decodeTable.processedIndex)
736     print 'number of total nodes in the tree:', decodeTable.numNodes
737
738 if __name__ == '__main__':
739     main()
740
741
742
743