Package Libs :: Module immvcglib
[hide private]
[frames] | no frames]

Source Code for Module Libs.immvcglib

   1  #!/usr/bin/env python 
   2   
   3  """ 
   4  Reads vcg buffer and creates the graph using Immunity Debugger lib 
   5   
   6  (c) Immunity, Inc. 2004-2007 
   7   
   8   
   9  U{Immunity Inc.<http://www.immunityinc.com>} 
  10   
  11   
  12  """ 
  13   
  14  __VERSION__ = '1.2' 
  15   
  16   
  17  """ 
  18  NOTES: 
  19  need to divide graph in layers 
  20  save max layer in graph 
  21  every set of childs [unique and different part vertex] E a different layer 
  22  save vertex of layer in each layer 
  23  mark blank path points in each layer [i preffer path points to dummy vertices]  
  24   
  25  for layer in layers: 
  26     move east and west vertices, depending on their type * 
  27   
  28  pathfinder(graph) 
  29    search empy spots where edge lines might travel 
  30     
  31     
  32  a cool thing might be mark the whole graph as east-slanted or west-slanted, according the graph 
  33  the n east or n west it will move 
  34   
  35  if the graph is slanting too much to east from center point, we can start thinking on going west 
  36  that can be too fuzzy, but will try to make an aproach for human eye 
  37   
  38   
  39  new lib against old lib: 
  40  orphan vertices from old lib has been solved, now every vertex has at least 1 relationship saved  
  41  parent<->child type of vertex are correctly relationed now 
  42   
  43  """ 
  44   
  45  import graphclass 
  46   
  47  import immlib 
  48  import debugger 
  49  #chaos is our friend  
  50  # XXX: Sure .. but how does chaos theory relate to random human interaction? 
  51  # XXX: Chance meetings that ultimately end up derailing your life .. 
  52  # XXX: The butterfly effect of hello's .. I don't know .. do you? 
  53  from random import randint 
  54   
  55  # default GRAPH palette 
  56  PALETTE = [] 
  57   
  58  PALETTE.append("manhattan_edges: yes\r\n") 
  59  PALETTE.append("layoutalgorithm: mindepth\r\n") 
  60  PALETTE.append("finetuning: no\r\n") 
  61  PALETTE.append("layout_downfactor: 100\r\n") 
  62  PALETTE.append("layout_upfactor: 0\r\n") 
  63  PALETTE.append("layout_nearfactor: 0\r\n") 
  64  PALETTE.append("xlspace: 12\r\n") 
  65  PALETTE.append("yspace: 30\r\n") 
  66  PALETTE.append("colorentry 32: 0 0 0\r\n") 
  67  PALETTE.append("colorentry 33: 0 0 255\r\n") 
  68  PALETTE.append("colorentry 34: 0 0 255\r\n") 
  69  PALETTE.append("colorentry 35: 128 128 128\r\n") 
  70  PALETTE.append("colorentry 36: 128 128 128\r\n") 
  71  PALETTE.append("colorentry 37: 0 0 128\r\n") 
  72  PALETTE.append("colorentry 38: 0 0 128\r\n") 
  73  PALETTE.append("colorentry 39: 0 0 255\r\n") 
  74  PALETTE.append("colorentry 40: 0 0 255\r\n") 
  75  PALETTE.append("colorentry 41: 0 0 128\r\n") 
  76  PALETTE.append("colorentry 42: 0 128 0\r\n") 
  77  PALETTE.append("colorentry 43: 0 255 0\r\n") 
  78  PALETTE.append("colorentry 44: 0 128 0\r\n") 
  79  PALETTE.append("colorentry 45: 255 128 0\r\n") 
  80  PALETTE.append("colorentry 46: 0 128 0\r\n") 
  81  PALETTE.append("colorentry 47: 128 128 255\r\n") 
  82  PALETTE.append("colorentry 48: 255 0 0\r\n") 
  83  PALETTE.append("colorentry 49: 128 128 0\r\n") 
  84  PALETTE.append("colorentry 50: 1 1 1\r\n") 
  85  PALETTE.append("colorentry 51: 192 192 192\r\n") 
  86  PALETTE.append("colorentry 52: 0 0 255\r\n") 
  87  PALETTE.append("colorentry 53: 0 0 255\r\n") 
  88  PALETTE.append("colorentry 54: 0 0 255\r\n") 
  89  PALETTE.append("colorentry 55: 128 128 128\r\n") 
  90  PALETTE.append("colorentry 56: 128 128 255\r\n") 
  91  PALETTE.append("colorentry 57: 0 128 0\r\n") 
  92  PALETTE.append("colorentry 58: 0 0 128\r\n") 
  93  PALETTE.append("colorentry 59: 0 0 255\r\n") 
  94  PALETTE.append("colorentry 60: 128 0 128\r\n") 
  95  PALETTE.append("colorentry 61: 0 128 0\r\n") 
  96  PALETTE.append("colorentry 62: 0 128 0\r\n") 
  97  PALETTE.append("colorentry 63: 0 128 64\r\n") 
  98  PALETTE.append("colorentry 64: 0 0 128\r\n") 
  99  PALETTE.append("colorentry 65: 0 0 128\r\n") 
 100  PALETTE.append("colorentry 66: 255 0 255\r\n") 
 101  PALETTE.append("colorentry 67: 128 128 0\r\n") 
 102  PALETTE.append("colorentry 68: 0 0 128\r\n") 
 103  PALETTE.append("colorentry 69: 0 0 255\r\n") 
 104  PALETTE.append("colorentry 70: 0 0 128\r\n") 
 105  PALETTE.append("colorentry 71: 0 0 255\r\n") 
 106  PALETTE.append("colorentry 72: 0 0 0\r\n") 
 107  PALETTE.append("colorentry 73: 255 255 255\r\n") 
 108  PALETTE.append("colorentry 74: 192 192 192\r\n") 
 109  PALETTE.append("colorentry 75: 0 255 255\r\n") 
 110  PALETTE.append("colorentry 76: 0 0 0\r\n") 
 111  PALETTE.append("colorentry 77: 128 0 0\r\n") 
 112  PALETTE.append("colorentry 78: 128 128 128\r\n") 
 113  PALETTE.append("colorentry 79: 128 128 0\r\n") 
 114  PALETTE.append("colorentry 80: 255 0 255\r\n") 
 115  PALETTE.append("colorentry 81: 0 0 0\r\n") 
 116  PALETTE.append("colorentry 82: 0 0 255\r\n") 
 117  PALETTE.append("colorentry 83: 0 0 0\r\n") 
 118   
119 -class graphTree:
120 # address to call tree from, ID immlib.Debugger() object
121 - def __init__(self, address, imm):
122 """ Init the graphing object """ 123 self.imm = imm 124 self.callTree = imm.getCallTree(address) 125 self.address = address
126
127 - def orderNodesFromTree(self):
128 """ return a call ordered list of nodes """ 129 130 # call[0] -> line number in column 131 # call[1] -> dummy (must be 1) 132 # call[2] -> type (set of TY_xxx) 133 # call[3] -> entry (address of function) 134 # call[4] -> from (address of calling function) 135 # call[5] -> calls to (address of called subfunction) 136 137 # so really for now we just do up and down for the first entry 138 TARGET = [] 139 PARENTS = [] 140 CHILDREN = [] 141 142 for call in self.callTree: 143 if call[3]: 144 if "0x%X"%call[3] not in TARGET: 145 TARGET.append("0x%X"% call[3]) 146 if call[4]: 147 if "0x%X"%call[4] not in PARENTS: 148 PARENTS.append("0x%X"% call[4]) 149 if call[5]: 150 if "0x%X"%call[5] not in CHILDREN: 151 CHILDREN.append("0x%X"% call[5]) 152 153 return TARGET, PARENTS, CHILDREN
154
155 - def makeNode(self, title, content = "", vertical_order = 0):
156 """ build a simple node VCG buf entry """ 157 node = [] 158 node.append('node: {\r\n') 159 node.append('title: "%s"\r\n'% title) 160 node.append('vertical_order: %d\r\n'% vertical_order) 161 if content != "": 162 node.append('label: "\x0c69%s\x0c31\r\n%s"\r\n'% (title, content)) 163 else: 164 node.append('label: "\x0c69%s\x0c31\r\n'% title) 165 node.append('}\r\n') 166 return node
167
168 - def makeEdge(self, source, target, label = "", color = "green"):
169 """ work out the relations between the boxies """ 170 # we call these 'edges', edges basically connect the boxies 171 edge = [] 172 173 edge.append('edge: {\r\n') 174 edge.append('sourcename: "%s"\r\n'% source) 175 edge.append('targetname: "%s"\r\n'% target) 176 if label != "": 177 edge.append('label: "%s"\r\n'% label) 178 edge.append('color: %s\r\n'% color) 179 edge.append('}\r\n') 180 181 return edge
182
183 - def makeVCG(self, title, nodes = [], edges = []):
184 """ build a simple node tree VCG buffer """ 185 vcg = [] 186 187 vcg.append('graph: {\r\n') 188 # XXX: dummy title (0xaddress) so parser doesn't choke .. fix that 189 vcg.append('title: "%s"\r\n'% title) 190 191 # add default palette 192 for line in PALETTE: 193 vcg.append(line) 194 195 # add nodes, nodes is a list of node entries 196 for node in nodes: 197 for line in node: 198 vcg.append(line) 199 200 # work out the relations from the call tree 201 for edge in edges: 202 for line in edge: 203 vcg.append(line) 204 205 # close the graph 206 vcg.append('}\r\n') 207 208 return vcg
209
210 - def graphCallTree(self):
211 """ pop up a call tree graph for this address """ 212 TARGET, PARENTS, CHILDREN = self.orderNodesFromTree() 213 214 nodes = [] 215 unique = [] 216 # make sure we don't double up on nodes .. 217 for title in TARGET+PARENTS+CHILDREN: 218 if title not in unique: 219 unique.append(title) 220 221 # make nodes for all the entries 222 for title in unique: 223 224 if title in PARENTS: 225 order = 0 226 if title in TARGET: 227 order = 1 228 if title in CHILDREN: 229 order = 2 230 231 # try to resolve to symbol using decodeAddress() 232 node_content = self.imm.decodeAddress(int(title, 16)) 233 nodes.append(self.makeNode(title, content = node_content, vertical_order = order)) 234 235 edges = [] 236 # we want to connect all the parents to the target and the target to all the children 237 target = TARGET[0] 238 239 for parent in PARENTS: 240 ### makeEdge(source-node, target-node) 241 edges.append(self.makeEdge(parent, target)) 242 for child in CHILDREN: 243 edges.append(self.makeEdge(target, child)) 244 245 # make the main VCG 246 vcg = self.makeVCG("Call Graph <-for-> %s [0x%X]"% (self.imm.decodeAddress(self.address), self.address), nodes, edges) 247 248 # XXX: debug write out 249 fd = open("CALLTREE.vcg", "w") 250 for line in vcg: 251 fd.write(line) 252 fd.close() 253 254 # pop up the MDI window 255 generateGraphFromBuf(vcg)
256
257 -class ParseVCGList:
258 """ recursive VCG parser """ 259
260 - def __init__(self, vcgList):
261 """ pre-process our shiznit """ 262 self.sep = '!SEP!' 263 self.DEBUG = False 264 265 # XXX: need to implement the full VCG grammar at some point 266 # XXX: also see http://www.penguin-soft.com/penguin/man/1/vcg.html 267 268 # WHEN MOVING TO MORE COMPLEX VCG, ADD FUNCTIONALITY _HERE_ 269 self.MODETOKENS = [ 'graph:', 'node:', 'edge:' ] 270 271 self.VARTOKENS = [ 'title:', 'label:', 'vertical_order:', 'horizontal_order:', 'manhattan_edges:', 'layoutalgorithm:' ] 272 self.VARTOKENS += [ 'finetuning:', 'layout_downfactor:', 'layout_upfactor:' ] 273 self.VARTOKENS += [ 'layout_nearfactor:', 'xlspace:', 'yspace:' ] 274 self.VARTOKENS += [ 'sourcename:', 'targetname:', 'color:' ] 275 276 # strip comment lines ... 277 cleanVCG = [] 278 # in string mode we don't want to replace .. 279 sMode = False 280 281 for line in vcgList: 282 283 # skip comments ... 284 if line[:2] == "//": 285 continue 286 287 clean = [] 288 lineList = list(line) 289 290 for c in lineList: 291 if c == '"': 292 # flip pre-process mode 293 sMode = not sMode 294 295 if sMode == True: # string mode open 296 clean.append(c) 297 else: 298 if c in ['\r']: # stripped chars .. 299 continue 300 if c in ['\n', ' ']: 301 clean.append(self.sep) 302 else: 303 clean.append(c) 304 305 line = ''.join(clean) 306 307 if len(line): 308 cleanVCG.append(line) 309 310 self.vcgText = ''.join(cleanVCG) 311 312 self.nodeList = [] 313 self.edgeList = [] 314 self.graphList = [] 315 316 self.lastMode = ""
317
318 - def error(self, error):
319 """ raise an error exception """ 320 raise error
321
322 - def reParse(self, vcgItems, mode = ""):
323 """ used for recursive parse """ 324 325 # DEBUG LOGS 326 if self.DEBUG: 327 logger = immlib.Debugger() 328 logger.Log(repr(vcgItems)) 329 330 # if not empty == True .. recursive calls .. bla bla 331 if vcgItems: 332 333 if vcgItems[0] in self.MODETOKENS: 334 mode = vcgItems[0] 335 self.lastMode = mode 336 self.reParse(vcgItems[1:], mode = mode) 337 338 elif vcgItems[0] in self.VARTOKENS or 'colorentry' in vcgItems[0]: 339 340 ### Special case color entry ... 341 if 'colorentry' in vcgItems[0]: 342 vcgItems[0] = " ".join([vcgItems[0], vcgItems[1]]) 343 del vcgItems[1] 344 345 args = [] 346 key = vcgItems[0] 347 348 i = 1 349 while vcgItems[i] not in self.VARTOKENS and vcgItems[i] not in self.MODETOKENS and 'colorentry' not in vcgItems[i]: 350 if '}' in vcgItems[i]: 351 break 352 args.append(vcgItems[i]) 353 i += 1 354 355 if mode == 'node:' and len(self.nodeList): 356 self.nodeList[len(self.nodeList)-1][key] = " ".join(args) 357 358 if mode == 'edge:' and len(self.edgeList): 359 self.edgeList[len(self.edgeList)-1][key] = " ".join(args) 360 361 if mode == 'graph:' and len(self.graphList): 362 self.graphList[len(self.graphList)-1][key] = " ".join(args) 363 364 self.reParse(vcgItems[i:], mode = self.lastMode) 365 366 elif '{' in vcgItems[0]: 367 368 # decide if mode needs a new dict .. or if it's just a pair: val 369 if mode == 'graph:': 370 self.graphList.append({}) 371 elif mode == 'node:': 372 self.nodeList.append({}) 373 elif mode == 'edge:': 374 self.edgeList.append({}) 375 376 self.reParse(vcgItems[1:], mode = mode) 377 378 # close control block, go up one mode 379 elif '}' in vcgItems[0]: 380 self.reParse(vcgItems[1:], mode = '') 381 382 # all done .. 383 return self.graphList, self.nodeList, self.edgeList
384
385 - def parseGraph(self):
386 """ Parse a VCG graph .. not 100% proper .. but proper enough """ 387 vcgItems = self.vcgText.split(self.sep) 388 return self.reParse(vcgItems)
389
390 -def testVCGParse(path):
391 """ test our new VCG parsing logic """ 392 vcgList = [] 393 394 fd = open(path, 'r') 395 for line in fd: 396 vcgList.append(line) 397 fd.close() 398 399 parser = ParseVCGList(vcgList) 400 401 # these are lists of dicts :> so 1 dict per node/edge/graph 402 graph, nodes, edges = parser.parseGraph() 403 404 logger = immlib.Debugger() 405 406 logger.Log("GRAPH:") 407 for gDict in graph: 408 for key in gDict: 409 logger.Log("KeyVal: %s"% key) 410 logger.Log(repr(gDict[key])) 411 logger.Log("EDGES:") 412 for eDict in edges: 413 for key in eDict: 414 logger.Log("KeyVal: %s"% key) 415 logger.Log(repr(eDict[key])) 416 logger.Log("NODES:") 417 for nDict in nodes: 418 for key in nDict: 419 logger.Log("KeyVal: %s"% key) 420 logger.Log(repr(nDict[key])) 421 422 return
423 424 # re-done for new parser code
425 -def generateGraphFromBuf(buf):
426 # XXX: the new parser returns 3 lists of dicts .. for the graph, nodes, and edges 427 # XXX: so then you can just go 'for nodeDict in nodes: handleNode(nodeDict)' etc. 428 # XXX: the new parser doesn't care about specific filelayouts and uses recursion 429 430 parser = ParseVCGList(buf) 431 # these are lists of dicts :> so 1 dict per node/edge/graph 432 GRAPH, NODES, EDGES = parser.parseGraph() 433 434 # 1. get the graph title (assuming only one VCG graph per .vcg) 435 title = GRAPH[0]['title:'] 436 437 # 2. get the start address 438 try: 439 # XXX: we wanna get rid of splits for parsing eventually :> 440 start_address = title.split("(")[1][:8] 441 except: 442 start_address = "0xcafebabe" 443 444 # DO GRAPHICS MUCK 445 Draw = graphclass.Draw() 446 # Get mdi handler 447 DrawHandler = Draw.createGraphWindow(title, start_address) 448 G = graphclass.Graph() 449 # Link the window handler to our graph 450 G.setHandler(DrawHandler) 451 452 # 3. handle NODES 453 vertices = createVertexList(NODES, DrawHandler) 454 455 # Once we has the vertices and the buffers we can calculate every vertex absolute size 456 for vertex in vertices: 457 vertex.calculateAbsoluteSize(vertex.getVertexBuffer()) 458 # Add list of vertex objects to graph instance 459 G.addVertices(vertices) 460 # Create edge list for graph instance + adjlists for vertex instance 461 createAdjacencyList(G, vertices, EDGES) 462 463 """ 464 at this point we have: 465 * draw instance [graph window inside debugger] 466 * graph instance 467 * vertex instances list 468 * edges lists + properties [true, false, direct] 469 * vertex instances list 470 * buffers 471 * absolute sizes 472 * adj lists of in and out edges 473 we now need to iterate our lists and define the best way to place 474 vertices 475 """ 476 477 # First attempt, place according true/false logic 478 firstAttemptToPlace(vertices) 479 # Was first attempt enough? 480 finalAttemptToPlace(vertices) 481 # Get the new startCoords 482 adjustStartCoords(vertices, G) 483 # Set the bitmap size 484 G.setBitSize(vertices) 485 # Try to get the best path for edges 486 edgelist = pathFinder(vertices) 487 # Draw lines 488 drawEdges(edgelist, DrawHandler) 489 # Draw boxes 490 drawVertices(vertices) 491 ### not here 492 ###checkPlanarity(vertices) 493 # splash the graph onto screen 494 G.splashTime()
495 496
497 -def generateGraph(address):
498 """ generates a VCG given a function address """ 499 try: 500 vcg = generateVCG(address) 501 except: 502 print "[XXX] Error generating VCG" 503 return 504 505 # XXX: replaces old duplicate, duplicating code is bad mmkay 506 generateGraphFromBuf(vcg)
507 508
509 -def adjustStartCoords(vertices,G):
510 (x,y)=vertices[0].getStartCoords() 511 (h,w)=G.getBitSize() 512 temp=w/2 513 #debugger.Error("%s - %s" % (str(x), str(temp))) 514 for vertex in vertices: 515 vertex.moveEast(x+temp)
516 517 518 # handles nodes - re-done for new parser
519 -def createVertexList(nodes, handler):
520 """ iterate vcg file to get vertex list and vertices's buffers""" 521 vertices = [] 522 523 for node in nodes: 524 vertexbuf = [] 525 v = graphclass.Vertex(handler) 526 527 logger = immlib.Debugger() 528 # XXX: assuming control chars are always there 529 label = node['label:'] 530 content = label[label.find("\x0c31") + 3:] 531 content = content.replace('"', '') 532 label = label[label.find("\x0c69") + 3 : label.find("\x0c31")] 533 534 v.setLabel(label) 535 536 title = node['title:'] 537 v.setName(title) 538 vertices.append(v) 539 540 vertexbuf += [v.getLabel()] 541 for key in node: 542 if key not in ['vertical_order:', 'title:', 'label:']: 543 nodeLine = node[key] 544 vertexbuf += [' '.join([key, node[key]])] 545 546 # add content to node box ... strings are kept intact newlines and all by preprocessor 547 content = content.split('\r\n') 548 for line in content: 549 # skip empty lines 550 if len(line): 551 vertexbuf += [line] 552 553 v.setVertexBuffer(vertexbuf) 554 555 return vertices
556 557 #for a in range(15,len(buf)): 558 # if buf[a][:6] == "node: ": 559 # vertexbuf=[] 560 # v=graphclass.Vertex(handler) 561 # v.setLabel(buf[a].split("\"")[3].split("\x0c")[1][2:]) 562 # v.setName(buf[a].split("\"")[1]) 563 # vertices.append(v) 564 # #fill vertex buffer 565 # vertexbuf+=[v.getLabel()] 566 # #immlib.Error("node: " + v.getName() +" Labeled: " + v.getLabel()) 567 # 568 # #if a > 20: #skip options in vcg header 569 # if buf[a][:6] != "node: " and buf[a][:2] != "//" and buf[a][:10] !="colorentry": 570 # if buf[a].find("}") == -1: 571 # vertexbuf+=[buf[a]] 572 # else: 573 # #we dont want to add blank vertexbuf or to a non existant vertex 574 # if vertexbuf and v: 575 # v.setVertexBuffer(vertexbuf[:-1]) 576 # vertexbuf=[] 577 #return vertices 578
579 -def finalAttemptToPlace(vertices):
580 #flag = False 581 #while not flag: 582 #for vertex in vertices: 583 #ret=checkForPlacedVertex(vertex,vertices) 584 #if not ret: 585 #flag = True 586 for a in range(1,15): 587 for vertex in vertices: 588 checkForPlacedVertex(vertex,vertices)
589
590 -def searchForDummyPathsH2South(edgelist,vertices):
591 templist=edgelist 592 vertexlist=[] 593 (xl,yl,x2l,y2l,color) = edgelist[-1] 594 for vertex in vertices: 595 (x,y,x2,y2) = vertex.getCoords() 596 #if vertex.getName() == "40fa96": 597 #f.write("%s: xl: %d, yl: %d, x2l: %d, y2l: %d\tx: %d, y: %d, x2: %d, y2: %d\n" % (vertex.getName(), xl, yl, x2l, y2l, x, y , x2, y2)) 598 if xl >= x-5 and xl <= x2+5 and yl < y and y2l > y: 599 vertexlist.append(vertex) 600 601 return applyDummyPathsH2South(vertexlist,edgelist)
602
603 -def searchForDummyPathsH2North(edgelist,vertices):
604 templist=edgelist 605 vertexlist=[] 606 (xl,yl,x2l,y2l,color) = edgelist[-1] 607 for vertex in vertices: 608 (x,y,x2,y2) = vertex.getCoords() 609 if xl >= x-5 and xl <= x2+5 and yl > y and y2l < y: 610 vertexlist.append(vertex) 611 612 return applyDummyPathsH2North(vertexlist,edgelist)
613 614 """ 615 NOTES: 616 617 if i use an edge templist i might be able to grep off 618 the non usefull bendings: 619 620 --| 621 __| 622 623 => 624 625 | 626 | 627 628 another nice thing would be to check wheter im nearest to east or west of 629 the overlapped vertex, so i can decide where to escape 630 """ 631 632
633 -def applyDummyPathsH2SouthTrue(vertexlist,edgelist):
634 (xl,yl,x2l,y2l,color) = edgelist[-1] 635 vertexlist.sort() 636 for vertex in vertexlist: 637 (x,y,x2,y2) = vertex.getCoords() 638 cm = randint(-20,-10) 639 640 if y2l-5 > y and y2l <= y2 and len(vertexlist) == 1: # line overlapp part of vertex, but it doesnt cross all over it 641 (tx,ty,tx2,ty2,color) = edgelist[-1] 642 edgelist[-1] = (( tx,ty,tx2, y-10, color)) 643 else: 644 if vertexlist.index(vertex) == 0: 645 edgelist[-1] = ((xl,yl,xl,y-10,color)) 646 else: 647 pass 648 #edgelist.append((endx,endy,endx,y-10,color)) 649 #edgelist[-1] = ((xl,yl,xl,y-10,color)) 650 edgelist.append((xl,y-10,x-10+cm,y-10,color)) 651 edgelist.append((x-10+cm,y-10,x-10+cm,y2+10,color)) 652 if vertex != vertexlist[-1]: #leave pathfinder() do the last stroke 653 edgelist.append((x-10+cm,y2+10,xl,y2+10,color)) 654 endx=xl 655 endy=y2+10 656 #edgelist.append((xl,y2+10,xl,endy,color)) 657 658 return edgelist
659
660 -def applyDummyPathsH2South(vertexlist,edgelist):
661 (xl,yl,x2l,y2l,color) = edgelist[-1] 662 vertexlist.sort() 663 for vertex in vertexlist: 664 (x,y,x2,y2) = vertex.getCoords() 665 if y2l > y and y2l <= y2 and len(vertexlist) == 1: # line overlapp part of vertex, but it doesnt cross all over it 666 (tx,ty,tx2,ty2,color) = edgelist[-1] 667 edgelist[-1] = (( tx,ty,tx2, y-10, color)) 668 else: 669 if vertexlist.index(vertex) == 0: 670 edgelist[-1] = ((xl,yl,xl,y-10,color)) 671 else: 672 pass 673 edgelist.append((endx,endy,endx,y-10,color)) 674 #edgelist[-1] = ((xl,yl,xl,y-10,color)) 675 if x2 - xl < xl -x: # go for the eastern exit 676 cm = randint(-5,5) 677 edgelist.append((xl,y-10,x2+20+cm,y-10,color)) 678 edgelist.append((x2+20+cm,y-10,x2+20+cm,y2+10,color)) 679 if vertex != vertexlist[-1]: #leave pathfinder() do the last stroke 680 edgelist.append((x2+20+cm,y2+10,xl,y2+10,color)) 681 endx=xl 682 endy=y2+10 683 else: #western exit 684 cm = randint(-20,-10) 685 edgelist.append((xl,y-10,x-10+cm,y-10,color)) 686 edgelist.append((x-10+cm,y-10,x-10+cm,y2+10,color)) 687 if vertex != vertexlist[-1]: #leave pathfinder() do the last stroke 688 edgelist.append((x-10+cm,y2+10,xl,y2+10,color)) 689 endx=xl 690 endy=y2+10 691 692 #edgelist.append((xl,y2+10,xl,endy,color)) 693 694 return edgelist
695 696
697 -def applyDummyPathsH2North2(vertexlist,edgelist):
698 (xl,yl,x2l,y2l,color) = edgelist[-1] 699 vertexlist.sort() 700 vertexlist.reverse() 701 for vertex in vertexlist: 702 (x,y,x2,y2) = vertex.getCoords() 703 if y2l > y and y2l <= y2 and len(vertexlist) == 1: # line overlapp part of vertex, but it doesnt cross all over it 704 pass 705 #(tx,ty,tx2,ty2,color) = edgelist[-1] 706 #edgelist[-1] = (( tx,ty,tx2, y-10, color)) 707 else: 708 if vertexlist.index(vertex) == 0: 709 edgelist[-1] = ((xl,yl,xl,y2+10,"Blue")) 710 else: 711 pass 712 edgelist.append((endx,endy,endx,y-10,"Aqua")) 713 #edgelist[-1] = ((xl,yl,xl,y-10,color)) 714 #if x2 - xl < xl -x: # go for the eastern exit 715 cm = randint(-5,5) 716 edgelist.append((xl,y2+10,x2+20+cm,y2+10,"red")) 717 edgelist.append((x2+20+cm,y2+10,x2+20+cm,y-10,"Yellow")) 718 if vertex != vertexlist[-1]: #leave pathfinder() do the last stroke 719 edgelist.append((x2+20+cm,y2+10,xl,y2+10,"Maroon")) 720 endx=xl 721 endy=y-10 722 723 #else: #western exit 724 #cm = randint(-5,5) 725 #edgelist.append((xl,y2+10,x-20+cm,y2+10,color)) 726 #edgelist.append((x-20+cm,y2+10,x-20+cm,y-10,color)) 727 #if vertex != vertexlist[-1]: #leave pathfinder() do the last stroke 728 #edgelist.append((x-20+cm,y2+10,xl,y2+10,color)) 729 #endx=xl 730 #endy=y2+10 731 # pass 732 733 734 #edgelist.append((xl,y2+10,xl,endy,color)) 735 736 return edgelist
737
738 -def applyDummyPathsH2North(vertexlist,edgelist):
739 (xl,yl,x2l,y2l,color) = edgelist[-1] 740 vertexlist.sort() 741 vertexlist.reverse() 742 for vertex in vertexlist: 743 (x,y,x2,y2) = vertex.getCoords() 744 if y2l > y and y2l <= y2 and len(vertexlist) == 1: # line overlapp part of vertex, but it doesnt cross all over it 745 (tx,ty,tx2,ty2,color) = edgelist[-1] 746 edgelist[-1] = (( tx,ty,tx2, y-10, color)) 747 if vertexlist.index(vertex) == 0: 748 edgelist[-1] = ((xl,yl,xl,y2+10,color)) 749 else: 750 edgelist.append((endx,endy,endx,y2+10,color)) 751 752 cm = randint(-5,5) 753 if x2 - xl < xl -x: # go for the eastern exit 754 edgelist.append((xl,y2+10,x2+20+cm,y2+10,color)) 755 edgelist.append((x2+20+cm,y2+10,x2+20+cm,y-10,color)) 756 if vertex != vertexlist[-1]: #leave pathfinder() do the last stroke 757 edgelist.append((x2+20+cm,y-10,xl,y-10,color)) 758 endx=xl 759 endy=y-10 760 else: 761 edgelist.append((xl,y2+10,x-20+cm,y2+10,color)) 762 edgelist.append((x-20+cm,y2+10,x-20+cm,y-10,color)) 763 if vertex != vertexlist[-1]: #leave pathfinder() do the last stroke 764 edgelist.append((x-20+cm,y-10,xl,y-10,color)) 765 endx=xl 766 endy=y-10 767 768 return edgelist
769 770
771 -def searchForDummyPathsW(edgelist,vertices):
772 return 773 (xl,yl,x2l,y2l,a) = edgelist[-1] 774 for vertex in vertices: 775 (x,y,x2,y2) = vertex.getCoords() 776 if xl > x or yl < x2 and x2l > y2: 777 pass 778 else: 779 f=open("ea.txt","w+") 780 f.write("quilombo %s\n" % str(x)) 781 f.close() 782 return edgelist
783
784 -def pathFinder(vertices):
785 """find edge's path 786 To find an endge path we start joining two vertex with 3 basic strokes, 787 A -> B -> C 788 after placing each of this basci strokes we check if it is not overlapping a vertex, if so 789 we decide a alternate path based on dummy blank points 790 A -> A' -> A'' -> B -> C 791 where A' (x2,y2) is the original A (x2,y2) so the next basic stroke B, knows how 792 to keep going 793 794 """ 795 """note on adding edges to edgelist: 796 since edgelist will self modify with other functions if pretty important 797 to add relative values and not absolute values. 798 ie: before adding a new edge check the last one, and the new values must be relative to edgelist[-1] 799 """ 800 edgelist=[] 801 f=open("edges.txt","w") 802 for vertex in vertices: 803 (x,y,x2,y2) = vertex.getCoords() 804 parentw=vertex.getWidth() 805 parenth=vertex.getHeight() 806 outadj=vertex.getOutAdj() 807 for child in outadj: 808 if child[1] == 1: #true child 809 for vertexchild in vertices: 810 if child[0] == vertexchild.getName(): 811 if vertex.getName() == vertexchild.getName(): 812 # parent = child, then loop in same vertex 813 edgelist.append((parentw*1/4+x+chaosmov,parenth+y-1,parentw*1/4+x+chaosmov,parenth+y+5,"darkgreen")) 814 edgelist.append((parentw*1/4+x+chaosmov,parenth+y+5,x-14,parenth+y+5,"darkgreen")) 815 edgelist.append((x-14,parenth+y+5,x-14,y-10,"darkgreen")) 816 edgelist.append((x-14,y-10,parentw*1/4+x+chaosmov,y-10,"darkgreen")) 817 edgelist.append((parentw*1/4+x+chaosmov,y-10,parentw*1/4+x+chaosmov,y-1,"darkgreen")) 818 else: 819 (xch,ych,x2ch,y2ch) = vertexchild.getCoords() 820 childw=vertexchild.getWidth() 821 #if x >= xp and x <= x2p: 822 #immlib.Error("%s and %s overlaps LEFT: %d" % (vertex.getName(),vertex2check.getName(),x2p-x)) 823 824 #if x2 >= xp and x <= x2p: 825 #immlib.Error("%s and %s overlaps RIGHT" % (vertex.getName(),vertex2check.getName())) 826 f.write("Edge true from %s (%d,%d,%d,%d) to %s (%d,%d,%d,%d)\n" % (vertex.getName(),x,y,x2,y2,vertexchild.getName(),xch,ych,x2ch,y2ch)) 827 chaosmov=randint(-5, 0) 828 if (parenth+y-1) > ych-2-25: # go north 829 edgelist.append((parentw*1/4+x+chaosmov,parenth+y-1,parentw*1/4+x+chaosmov,parenth+y+5,"Blue")) 830 edgelist.append((parentw*1/4+x+chaosmov,parenth+y+5,x-14,parenth+y+5,"Blue")) 831 edgelist.append((x-14,parenth+y+5,x-14,ych-2-20+chaosmov,"Blue")) 832 edgelist=searchForDummyPathsH2North(edgelist,vertices) 833 (tx,ty,tx2,ty2,color) = edgelist[-1] 834 edgelist.append((tx2,ty2,xch+(childw*1/2)+chaosmov,ty2,color)) 835 (tx,ty,tx2,ty2,color) = edgelist[-1] 836 if ty2 < y2ch: 837 edgelist.append((tx2,ty2,tx2,ych-2,color)) #last stroke enters from north 838 else: 839 edgelist.append((tx2,ty2,tx2,y2ch-2,color)) # last stroke enters from south 840 #edgelist=searchForDummyPathsH2North(edgelist,vertices) 841 else: # go south 842 #starting line 843 edgelist.append((parentw*1/4+x+chaosmov,parenth+y-1,parentw*1/4+x+chaosmov,ych-2-25+chaosmov,"darkgreen")) 844 edgelist=searchForDummyPathsH2South(edgelist,vertices) 845 #bend line #1 846 (tx,ty,tx2,ty2,color) = edgelist[-1] 847 edgelist.append((tx,ty2,xch+(childw*1/2)+chaosmov,ty2,color)) 848 (tx,ty,tx2,ty2,color) = edgelist[-1] 849 if ty2 < y2ch: 850 edgelist.append((tx2,ty2,tx2,ych-2,color)) #last stroke enters from north 851 else: 852 edgelist.append((tx2,ty2,tx2,y2ch-2,color)) # last stroke enters from south 853 edgelist.append((tx2,ty2,tx2,ych-2,color)) 854 855 #add endpoint 856 addEndPointToEdge(edgelist) 857 858 859 elif child[1] == 2 : #false child 860 for vertexchild in vertices: 861 if child[0] == vertexchild.getName(): 862 if vertex.getName() == vertexchild.getName(): 863 # parent = child, then loop in same vertex 864 debugger.Error("loop false") 865 edgelist.append((parentw*1/4+x+chaosmov,parenth+y-1,parentw*1/4+x+chaosmov,parenth+y+5,"red")) 866 edgelist.append((parentw*1/4+x+chaosmov,parenth+y+5,x-14,parenth+y+5,"red")) 867 edgelist.append((x-14,parenth+y+5,x-14,y-10,"red")) 868 edgelist.append((x-14,y-10,parentw*1/4+x+chaosmov,y-10,"red")) 869 edgelist.append((parentw*1/4+x+chaosmov,y-10,parentw*1/4+x+chaosmov,y-1,"red")) 870 871 else: 872 (xch,ych,x2ch,y2ch) = vertexchild.getCoords() 873 childw=vertexchild.getWidth() 874 chaosmov=randint(0, 5) 875 if (parenth+y-1) > ych-2-25: # go north 876 edgelist.append((parentw*3/4+x+chaosmov,parenth+y-1,parentw*3/4+x+chaosmov,parenth+y+5,"Blue")) 877 edgelist.append((parentw*3/4+x+chaosmov,parenth+y+5,x2+14,parenth+y+5,"Blue")) 878 edgelist.append((x2+14,parenth+y+5,x2+14,ych-2-20+chaosmov,"Blue")) 879 edgelist=searchForDummyPathsH2North(edgelist,vertices) 880 (tx,ty,tx2,ty2,color) = edgelist[-1] 881 edgelist.append((tx2,ty2,xch+(childw*1/2)+chaosmov,ty2,color)) 882 (tx,ty,tx2,ty2,color) = edgelist[-1] 883 if ty2 < y2ch: 884 edgelist.append((tx2,ty2,tx2,ych-2,color)) #last stroke enters from north 885 else: 886 edgelist.append((tx2,ty2,tx2,y2ch-2,color)) # last stroke enters from south 887 else: #go south 888 edgelist.append((parentw*3/4+x+chaosmov,parenth+y-1,parentw*3/4+x+chaosmov,ych-2-25+chaosmov,"red")) 889 edgelist=searchForDummyPathsH2South(edgelist,vertices) 890 (tx,ty,tx2,ty2,color) = edgelist[-1] 891 edgelist.append((tx,ty2,xch+(childw*1/2)+chaosmov,ty2,color)) 892 (tx,ty,tx2,ty2,color) = edgelist[-1] 893 edgelist.append((tx2,ty2,tx2,ych-2,color)) 894 edgelist=searchForDummyPathsH2South(edgelist,vertices) 895 #add endpoint 896 addEndPointToEdge(edgelist) 897 898 899 900 901 902 903 elif child[1] == 0 : #direct child 904 for vertexchild in vertices: 905 if child[0] == vertexchild.getName(): 906 if vertex.getName() == vertexchild.getName(): 907 # parent = child, then loop in same vertex 908 debugger.Error("loop direct") 909 else: 910 (xch,ych,x2ch,y2ch) = vertexchild.getCoords() 911 f.write("Edge direct from %s (%d,%d,%d,%d) to %s (%d,%d,%d,%d)\n" % (vertex.getName(),x,y,x2,y2,vertexchild.getName(),xch,ych,x2ch,y2ch)) 912 chaosmov=randint(-5, 5) 913 chaosmovlastx=randint(-20,20) 914 childw=vertexchild.getWidth() 915 if (parenth+y-1) > ych-2-25: # go north 916 edgelist.append((parentw*1/2+x+chaosmov,parenth+y-1,parentw*1/2+x+chaosmov,parenth+y+5,"Blue")) 917 edgelist.append((parentw*1/2+x+chaosmov,parenth+y+5,x-10,parenth+y+5,"Blue")) 918 edgelist.append((x-10,parenth+y+5,x-10,ych-2-20+chaosmov,"Blue")) 919 edgelist=searchForDummyPathsH2North(edgelist,vertices) 920 (tx,ty,tx2,ty2,color) = edgelist[-1] 921 edgelist.append((tx2,ty2,xch+(childw*1/2)+chaosmov,ty2,color)) 922 (tx,ty,tx2,ty2,color) = edgelist[-1] 923 if ty2 < y2ch: 924 edgelist.append((tx2,ty2,tx2,ych-2,color)) #last stroke enters from north 925 else: 926 edgelist.append((tx2,ty2,tx2,y2ch-2,color)) # last stroke enters from south 927 928 else: # go south 929 edgelist.append((parentw*1/2+x+chaosmov,parenth+y-1,parentw*1/2+x+chaosmov,ych-2-25+chaosmov,"Black")) 930 edgelist=searchForDummyPathsH2South(edgelist,vertices) 931 (tx,ty,tx2,ty2,color) = edgelist[-1] 932 edgelist.append((tx,ty2,xch+(childw*1/2)+chaosmov,ty2,color)) 933 (tx,ty,tx2,ty2,color) = edgelist[-1] 934 edgelist.append((tx2,ty2,tx2,ych-2,color)) 935 936 937 938 #add endpoint 939 addEndPointToEdge(edgelist) 940 941 942 943 return edgelist
944
945 -def addEndPointToEdge(edgelist):
946 (endx,endy,endx2,endy2,color)=edgelist[-1] 947 edgelist.append((endx2,endy2,endx2,endy2+2,color)) 948 edgelist.append((endx2,endy2,endx2,endy2-2,color)) 949 edgelist.append((endx2,endy2+2,endx2+2,endy2+2,color)) 950 edgelist.append((endx2,endy2+2,endx2-2,endy2+2,color)) 951 edgelist.append((endx2+2,endy2-2,endx2+2,endy2+3,color)) 952 edgelist.append((endx2-2,endy2-2,endx2-2,endy2+3,color)) 953 edgelist.append((endx2-2,endy2-2,endx2+2,endy2-2,color)) 954 955 return edgelist
956
957 -def drawVertices(vertices):
958 startx=None 959 for vertex in vertices: 960 if vertex.isDrawn() == False: 961 if startx==None: 962 startx=1 963 else: 964 startx=0 965 checkForPlacedVertex(vertex,vertices) 966 (x,y)=vertex.getRelPos() 967 vertex.placeVertex(x,y,vertex.getVertexBuffer(),"Black","Gray",startx) 968 vertex.setDrawn() 969 970 return
971
972 -def drawEdges(edgelist,handler):
973 for line in edgelist: 974 linej=graphclass.Line(handler) 975 x_pos=line[0] 976 y_pos=line[1] 977 x_to=line[2] 978 y_to=line[3] 979 color=line[4] 980 linej.draw(x_pos,y_pos,x_to,y_to,color) 981 return
982 983 984 # handles edges - re-done for new parser
985 -def createAdjacencyList(G, vertices, edges):
986 """ creates a directed adjacency list for every vertex """ 987 for edge in edges: 988 source = edge['sourcename:'] 989 target = edge['targetname:'] 990 991 type = 0 992 if 'label:' in edge: 993 if 'TRUE' in edge['label:'].upper(): 994 type = 1 995 if 'FALSE' in edge['label:'].upper(): 996 type = 2 997 998 G.addEdges((source, target, type)) 999 1000 for vertex in vertices: 1001 if vertex.getName() == source: 1002 vertex.addOutAdj(target, type) 1003 if vertex.getName() == target: 1004 vertex.addInAdj(source) 1005 return
1006 1007 # for a in range(1,len(buf)): 1008 # if buf[a][:7] == "edge: {": 1009 # edge=buf[a].split("\n") 1010 # for b in edge: 1011 # if len(b) > 1: 1012 # parse=b.split("\"") 1013 # source=parse[1] 1014 # target=parse[3] 1015 # type=0 1016 # if len(parse) == 7: 1017 # if parse[5] == "true": 1018 # type=1 1019 # elif parse[5] == "false": 1020 # type=2 1021 # G.addEdges((source,target,type)) 1022 # #print "source: " + source + " target : " + target 1023 # for vertex in vertices: 1024 # if vertex.getName() == source: 1025 # vertex.addOutAdj(target,type) 1026 # elif vertex.getName() == target: 1027 # vertex.addInAdj(source) 1028 # return 1029
1030 -def checkPlanarity(vertices):
1031 #for a in range(0,10): 1032 #for vertex in vertices: 1033 #checkForPlacedVertex(vertex,vertices) 1034 return
1035
1036 -def firstAttemptToPlace(vertices):
1037 """First attempt to place vertices 1038 We are going to suppose Graph is planar and 1039 attempt to place vertices directly, 1040 in real world this wont happens, but at least 1041 we'll have temptative coords for every vertex""" 1042 1043 for vertex in vertices: 1044 if vertices.index(vertex) == 0 : 1045 (x,y)=vertex.getStartCoords() 1046 vertex.setRelPos(x,y) 1047 (x,y,x2,y2)=vertex.getCoords() 1048 vertex.setPlaced() 1049 (x,y)=vertex.getRelPos() 1050 #vertex.placeVertex(x,y,vertex.getVertexBuffer(),"Black","Gray",0) 1051 outadj=vertex.getOutAdj() 1052 #immlib.Error("Parent: %s" % str(vertex.getName())) 1053 if len(outadj) > 0: #dont do if no childs 1054 for child in outadj: 1055 if child[1] == 1: 1056 for vertexchild in vertices: 1057 if child[0] == vertexchild.getName() and vertexchild.isPlaced() == False: 1058 (xp,yp)=vertex.getRelPos() 1059 if xp == 0: #this means that no parent is still defined, maybe a recursive cycle? 1060 #immlib.Error("recursive cycle? check inadj list true") 1061 """Note: usually we dont want to go back from Point of No Return, 1062 but in this special case of vertex, we need to do it. 1063 we should have in mind, that overlapping might occur, but we wont move south , instead 1064 we need to move east/west""" 1065 inadj=vertex.getInAdj() 1066 for parent in inadj: 1067 for parentvertex in vertices: 1068 if parent == parentvertex.getName(): 1069 (xp,yp)=parentvertex.getRelPos() 1070 y=yp+parentvertex.getHeight()+55 1071 x=xp-(parentvertex.getWidth()*0.75) 1072 x=xp-100 1073 vertexchild.setRelPos(x,y) 1074 #checkForPlacedVertex(vertexchild, vertices) 1075 vertexchild.setPlaced() 1076 else: 1077 1078 y=yp+vertex.getHeight()+55 1079 #x=xp-(vertex.getWidth()*0.75) 1080 x=xp-100 1081 vertexchild.setRelPos(x,y) 1082 checkForPlacedVertex(vertexchild, vertices) 1083 vertexchild.setPlaced() 1084 1085 #immlib.Error("Child True: %s\nx: %s\ny:%s\nParent:%s %s, %s" % (str(child[0]),str(x),str(y),vertex.getName(),str(xp),str(yp))) 1086 elif child[1] == 2 : 1087 for vertexchild in vertices: 1088 if child[0] == vertexchild.getName() and vertexchild.isPlaced() == False: 1089 (xp,yp)=vertex.getRelPos() 1090 if xp == 0: 1091 """special case""" 1092 #immlib.Error("recursive cycle? check inadj list false") 1093 inadj=vertex.getInAdj() 1094 #immlib.Error(str(inadj)) 1095 for parent in inadj: 1096 for parentvertex in vertices: 1097 if parent == parentvertex.getName(): 1098 (xp,yp)=parentvertex.getRelPos() 1099 y=yp+parentvertex.getHeight()+15 1100 #x=xp+(parentvertex.getWidth()*0.75) 1101 x=xp+parentvertex.getWidth()+50 1102 vertexchild.setRelPos(x,y) 1103 #checkForPlacedVertex(vertexchild, vertices) 1104 vertexchild.setPlaced() 1105 1106 else: 1107 y=yp+vertex.getHeight()+55 1108 #x=xp+(vertex.getWidth()*0.75) 1109 x=xp+vertex.getWidth()+50 1110 vertexchild.setRelPos(x,y) 1111 checkForPlacedVertex(vertexchild, vertices) 1112 vertexchild.setPlaced() 1113 1114 #immlib.Error("Child False: %s\nx: %s\ny:%s\nParent:%s %s, %s" % (str(child[0]),str(x),str(y),vertex.getName(),str(xp),str(yp))) 1115 1116 if child[1] == 0 : 1117 for vertexchild in vertices: 1118 if child[0] == vertexchild.getName() and vertexchild.isPlaced() == False: 1119 (xp,yp)=vertex.getRelPos() 1120 if xp == 0: 1121 """special case""" 1122 #immlib.Error("recursive cycle? check inadj list direct") 1123 inadj=vertex.getInAdj() 1124 #immlib.Error(str(inadj)) 1125 for parent in inadj: 1126 for parentvertex in vertices: 1127 if parent == parentvertex.getName(): 1128 (xp,yp)=parentvertex.getRelPos() 1129 y=yp+parentvertex.getHeight()+55 1130 x=xp+(parentvertex.getWidth()/2) 1131 vertexchild.setRelPos(x,y) 1132 #checkForPlacedVertex(vertexchild, vertices) 1133 vertexchild.setPlaced() 1134 1135 1136 else: 1137 y=yp+vertex.getHeight()+55 1138 x=xp+(vertex.getWidth()/2) 1139 vertexchild.setRelPos(x,y) 1140 checkForPlacedVertex(vertexchild, vertices) 1141 vertexchild.setPlaced() 1142 1143 #immlib.Error("Child Direct: %s\nx: %s\ny:%s\nParent:%s %s, %s" % (str(child[0]),str(x),str(y),vertex.getName(),str(xp),str(yp))) 1144 1145 return
1146 1147 1148 1149 1150
1151 -def checkForPlacedVertex(vertex2check,vertices):
1152 1153 """Note: needs to divide graph in layers 1154 1155 Draft notes: 1156 step 1 get temptative coords to place vertex 1157 step 2 check if coords overlaps already placed vertex 1158 1159 step 2 a) 1160 first we have to check if (y,y2) of vertex is in range of the placed vertex, 1161 1162 if y >= yp and y <= y2p or y2 >= yp and y2 <= y2p: 1163 1164 if that condition is true, means we have a vertex in the same y that an already placed vertex, so it might be 1165 possible of an overlapping to exists, so we are going to ask: 1166 1167 if x >= xp and x <= x2p: 1168 if that condition is true, then we have an overlapping over the y coord of the vertex (left point) 1169 1170 if x2 >= xp and x <= x2p: 1171 if that condition is true, then we have an overlapping over the y coord of the vertex (right point) 1172 1173 and if does, check whether x or x2 is overlapping 1174 once we know that, we need to check wheter x or x2 of overlapped vertex is touched 1175 if x , move west x - 10 and recheck 1176 """ 1177 ret=False 1178 (x,y,x2,y2) = vertex2check.getCoords() 1179 for vertex in vertices: 1180 if vertex.getName() == vertex2check.getName() : 1181 pass 1182 else: 1183 if 1 == 1: 1184 (xp,yp,x2p,y2p) = vertex.getCoords() 1185 if y >= yp and y <= y2p or y2 >= yp and y2 <= y2p: 1186 #immlib.Error("%s and %s are in the same x range" % (vertex.getName(),vertex2check.getName())) 1187 if x >= xp and x <= x2p: 1188 #immlib.Error("%s and %s overlaps LEFT: %d" % (vertex.getName(),vertex2check.getName(),x2p-x)) 1189 vertex2check.moveSouth(y2p-y+25) 1190 (xp,yp,x2p,y2p) = vertex.getCoords() 1191 (x,y,x2,y2) = vertex2check.getCoords() 1192 ret=True 1193 if x2 >= xp and x <= x2p: 1194 #immlib.Error("%s and %s overlaps RIGHT" % (vertex.getName(),vertex2check.getName())) 1195 vertex2check.moveSouth(y2p-y+25) 1196 (xp,yp,x2p,y2p) = vertex.getCoords() 1197 (x,y,x2,y2) = vertex2check.getCoords() 1198 ret=True 1199 return ret
1200
1201 -def checkForPlacedVertex2(vertex2check,vertices):
1202 1203 """Note: needs to divide graph in layers 1204 1205 Draft notes: 1206 step 1 get temptative coords to place vertex 1207 step 2 check if coords overlaps already placed vertex 1208 1209 step 2 a) 1210 first we have to check if (y,y2) of vertex is in range of the placed vertex, 1211 1212 if y >= yp and y <= y2p or y2 >= yp and y2 <= y2p: 1213 1214 if that condition is true, means we have a vertex in the same y that an already placed vertex, so it might be 1215 possible of an overlapping to exists, so we are going to ask: 1216 1217 if x >= xp and x <= x2p: 1218 if that condition is true, then we have an overlapping over the y coord of the vertex (left point) 1219 1220 if x2 >= xp and x <= x2p: 1221 if that condition is true, then we have an overlapping over the y coord of the vertex (right point) 1222 1223 and if does, check whether x or x2 is overlapping 1224 once we know that, we need to check wheter x or x2 of overlapped vertex is touched 1225 if x , move west x - 10 and recheck 1226 """ 1227 ret=False 1228 (x,y,x2,y2) = vertex2check.getCoords() 1229 for vertex in vertices: 1230 if vertex.getName() == vertex2check.getName() : 1231 pass 1232 else: 1233 if 1 == 1: 1234 (xp,yp,x2p,y2p) = vertex.getCoords() 1235 if y >= yp and y <= y2p or y2 >= yp and y2 <= y2p: 1236 immlib.Error("%s and %s are in the same x range" % (vertex.getName(),vertex2check.getName())) 1237 if x >= xp and x <= x2p: 1238 immlib.Error("%s and %s overlaps LEFT: %d" % (vertex.getName(),vertex2check.getName(),x2p-x)) 1239 vertex2check.moveSouth(20) 1240 (xp,yp,x2p,y2p) = vertex.getCoords() 1241 (x,y,x2,y2) = vertex2check.getCoords() 1242 ret=True 1243 if x2 >= xp and x <= x2p: 1244 vertex2check.moveSouth(20) 1245 immlib.Error("%s and %s overlaps RIGHT" % (vertex.getName(),vertex2check.getName())) 1246 (xp,yp,x2p,y2p) = vertex.getCoords() 1247 (x,y,x2,y2) = vertex2check.getCoords() 1248 ret=True 1249 return ret
1250 1251
1252 -def defineVertexRelation(vertices):
1253 #first vertex coords 1254 #x=300 1255 #y=10 1256 #vertices[0].setRelPos(x,y) 1257 1258 #vertices[0].placeVertex(x,y,vertices[0].getVertexBuffer(),"Black","Blue",0) 1259 1260 #draw[0].draw(draw[1],draw[2],draw[0].getNodeBuffer(),"Black","Blue",startx) 1261 return
1262 1263 # XXX: if it's rainy out, re-do this too ...
1264 -def generateVCG(address):
1265 """ this function will generate a vcg compatible buffer to create the graph """ 1266 imm = immlib.Debugger() 1267 ret = imm.getFunctionBegin(address) 1268 if ret: 1269 address = ret 1270 f = imm.getFunction(address) 1271 buf=[] 1272 buf.append('graph: {\x0d\x0a') 1273 buf.append('title: "Graph of %s (0x%08x)"\r\n' % (f.getName(),int(f.start))) 1274 buf.append("//default palette\r\n") 1275 ### add the default palette 1276 buf += PALETTE 1277 basicblocks = f.getBasicBlocks() 1278 basicblocks.sort() 1279 #first basicblock 1280 buf.append('node: { title: "0x%08x" vertical_order: 0 label: "\x0c69%s (0x%08x):\x0c31\r\n' % (int(basicblocks[0].start),f.getName(),int(f.start))) 1281 instr=basicblocks[0].getInstructions(imm) 1282 for i in instr: 1283 if len(i.comment) > 0: 1284 buf.append("%s || %s\r\n" % (i.result,i.comment.replace("\"",""))) 1285 else: 1286 buf.append("%s\r\n" % i.result) 1287 buf.append("\"") 1288 1289 #from second the last one -1 basicblocks 1290 1291 for a in range(1,len(basicblocks)): 1292 buf.append(" }\n") 1293 buf.append('node: { title: "0x%08x" label: "\x0c69 0x%08x\x0c31\n' % (int(basicblocks[a].start),int(basicblocks[a].start))) 1294 instr=basicblocks[a].getInstructions(imm) 1295 for i in instr: 1296 if len(i.comment) > 0: 1297 buf.append("%s || %s\r\n" % (i.result,i.comment.replace("\"",""))) 1298 else: 1299 buf.append("%s\r\n" % i.result) 1300 1301 buf.append('"\r\n') 1302 1303 buf.append("}\r\n" ) 1304 #generate edges list 1305 buf.append("//nodes edges\r\n") 1306 for a in range(0,len(basicblocks)-1): 1307 (true,false) = basicblocks[a].getEdges() 1308 if false != 0: 1309 buf.append('edge: { sourcename: "0x%08x" targetname: "0x%08x" label: "false" color: red }\r\n' % (int(basicblocks[a].start),int(basicblocks[a].end))) 1310 buf.append('edge: { sourcename: "0x%08x" targetname: "0x%08x" label: "true" color: darkgreen }\r\n' % (int(basicblocks[a].start),int(true))) 1311 else: 1312 buf.append('edge: { sourcename: "0x%08x" targetname: "0x%08x" }\r\n' % (int(basicblocks[a].start),int(true))) 1313 buf.append("\n}\r\n") 1314 return buf
1315 1316
1317 -def saveVCG(address,filename):
1318 vcg_buf=generateVCG(address) 1319 if len(vcg_buf) > 0: 1320 fd=open(filename,"wb") 1321 for a in vcg_buf: 1322 fd.write(a) 1323 fd.close() 1324 else: 1325 debugger.Error("There is no VCG graph")
1326 1327 1328 if __name__=="__main__": 1329 main() 1330