Merge pull request #963 from nofiv/find_path_from_src

Added function find_path_from_src

1 files changed, 35 insertions, 0 deletions

diff --git a/miasm2/core/graph.py b/miasm2/core/graph.py
index f61d1e67..e385b044 100644
--- a/miasm2/core/graph.py
+++ b/miasm2/core/graph.py
@@ -143,6 +143,14 @@ class DiGraph(object):
         return [x for x in self.heads_iter()]
 
     def find_path(self, src, dst, cycles_count=0, done=None):
+        """
+        Searches for paths from @src to @dst
+        @src: loc_key of basic block from which it should start
+        @dst: loc_key of basic block where it should stop
+        @cycles_count: maximum number of times a basic block can be processed
+        @done: dictionary of already processed loc_keys, it's value is number of times it was processed
+        @out: list of paths from @src to @dst
+        """
         if done is None:
             done = {}
         if dst in done and done[dst] > cycles_count:
@@ -157,6 +165,33 @@ class DiGraph(object):
                 if path and path[0] == src:
                     out.append(path + [dst])
         return out
+    
+    def find_path_from_src(self, src, dst, cycles_count=0, done=None):
+        """
+        This function does the same as function find_path.
+        But it searches the paths from src to dst, not vice versa like find_path.
+        This approach might be more efficient in some cases.
+        @src: loc_key of basic block from which it should start
+        @dst: loc_key of basic block where it should stop
+        @cycles_count: maximum number of times a basic block can be processed
+        @done: dictionary of already processed loc_keys, it's value is number of times it was processed
+        @out: list of paths from @src to @dst
+        """
+        
+        if done is None:
+            done = {}
+        if src == dst:
+            return [[src]]
+        if src in done and done[src] > cycles_count:
+            return [[]]
+        out = []
+        for node in self.successors(src):
+            done_n = dict(done)
+            done_n[src] = done_n.get(src, 0) + 1
+            for path in self.find_path_from_src(node, dst, cycles_count, done_n):
+                if path and path[len(path)-1] == dst:
+                    out.append([src] + path)
+        return out
 
     def nodeid(self, node):
         """