(self)
Computes the diff of the functions and saves the result.
Computes the diff of the functions and saves the result.
Computes the diff of the functions and saves the result .
def _compute_diff(self):
        """
        Computes the diff of the functions and saves the result.
        """
        # get the attributes for all blocks
        l.debug("Computing diff of functions: %s, %s",
                ("%#x" % self._function_a.startpoint.addr) if self._function_a.startpoint is not None else "None",
                ("%#x" % self._function_b.startpoint.addr) if self._function_b.startpoint is not None else "None"
                )
        self.attributes_a = self._compute_block_attributes(self._function_a)
        self.attributes_b = self._compute_block_attributes(self._function_b)

        # get the initial matches
        initial_matches = self._get_block_matches(self.attributes_a, self.attributes_b,
                                                  tiebreak_with_block_similarity=False)

        # Use a queue so we process matches in the order that they are found
        to_process = deque(initial_matches)

        # Keep track of which matches we've already added to the queue
        processed_matches = set((x, y) for (x, y) in initial_matches)

        # Keep a dict of current matches, which will be updated if better matches are found
        matched_a = dict()
        matched_b = dict()
        for (x, y) in processed_matches:
            matched_a[x] = y
            matched_b[y] = x

        # while queue is not empty
        while to_process:
            (block_a, block_b) = to_process.pop()
            l.debug("FunctionDiff: Processing (%#x, %#x)", block_a.addr, block_b.addr)

            # we could find new matches in the successors or predecessors of functions
            block_a_succ = list(self._function_a.graph.successors(block_a))
            block_b_succ = list(self._function_b.graph.successors(block_b))
            block_a_pred = list(self._function_a.graph.predecessors(block_a))
            block_b_pred = list(self._function_b.graph.predecessors(block_b))

            # propagate the difference in blocks as delta
            delta = tuple((i-j) for i, j in zip(self.attributes_b[block_b], self.attributes_a[block_a]))

            # get possible new matches
            new_matches = []

            # if the blocks are identical then the successors should most likely be matched in the same order
            if self.blocks_probably_identical(block_a, block_b) and len(block_a_succ) == len(block_b_succ):
                ordered_succ_a = self._get_ordered_successors(self._project_a, block_a, block_a_succ)
                ordered_succ_b = self._get_ordered_successors(self._project_b, block_b, block_b_succ)
                new_matches.extend(zip(ordered_succ_a, ordered_succ_b))

            new_matches += self._get_block_matches(self.attributes_a, self.attributes_b, block_a_succ, block_b_succ,
                                                   delta, tiebreak_with_block_similarity=True)
            new_matches += self._get_block_matches(self.attributes_a, self.attributes_b, block_a_pred, block_b_pred,
                                                   delta, tiebreak_with_block_similarity=True)

            # for each of the possible new matches add it if it improves the matching
            for (x, y) in new_matches:
                if (x, y) not in processed_matches:
                    processed_matches.add((x, y))
                    l.debug("FunctionDiff: checking if (%#x, %#x) is better", x.addr, y.addr)
                    # if it's a better match than what we already have use it
                    if _is_better_match(x, y, matched_a, matched_b, self.attributes_a, self.attributes_b):
                        l.debug("FunctionDiff: adding possible match (%#x, %#x)", x.addr, y.addr)
                        if x in matched_a:
                            old_match = matched_a[x]
                            del matched_b[old_match]
                        if y in matched_b:
                            old_match = matched_b[y]
                            del matched_a[old_match]
                        matched_a[x] = y
                        matched_b[y] = x
                        to_process.appendleft((x, y))

        # reformat matches into a set of pairs
        self._block_matches = set((x, y) for (x, y) in matched_a.items())

        # get the unmatched blocks
        self._unmatched_blocks_from_a = set(x for x in self._function_a.graph.nodes() if x not in matched_a)
        self._unmatched_blocks_from_b = set(x for x in self._function_b.graph.nodes() if x not in matched_b)
def _compute_diff ( self ) : # get the attributes for all blocks l . debug ( "Computing diff of functions: %s, %s" , ( "%#x" % self . _function_a . startpoint . addr ) if self . _function_a . startpoint is not None else "None" , ( "%#x" % self . _function_b . startpoint . addr ) if self . _function_b . startpoint is not None else "None" ) self . attributes_a = self . _compute_block_attributes ( self . _function_a ) self . attributes_b = self . _compute_block_attributes ( self . _function_b ) # get the initial matches initial_matches = self . _get_block_matches ( self . attributes_a , self . attributes_b , tiebreak_with_block_similarity = False ) # Use a queue so we process matches in the order that they are found to_process = deque ( initial_matches ) # Keep track of which matches we've already added to the queue processed_matches = set ( ( x , y ) for ( x , y ) in initial_matches ) # Keep a dict of current matches, which will be updated if better matches are found matched_a = dict ( ) matched_b = dict ( ) for ( x , y ) in processed_matches : matched_a [ x ] = y matched_b [ y ] = x # while queue is not empty while to_process : ( block_a , block_b ) = to_process . pop ( ) l . debug ( "FunctionDiff: Processing (%#x, %#x)" , block_a . addr , block_b . addr ) # we could find new matches in the successors or predecessors of functions block_a_succ = list ( self . _function_a . graph . successors ( block_a ) ) block_b_succ = list ( self . _function_b . graph . successors ( block_b ) ) block_a_pred = list ( self . _function_a . graph . predecessors ( block_a ) ) block_b_pred = list ( self . _function_b . graph . predecessors ( block_b ) ) # propagate the difference in blocks as delta delta = tuple ( ( i - j ) for i , j in zip ( self . attributes_b [ block_b ] , self . attributes_a [ block_a ] ) ) # get possible new matches new_matches = [ ] # if the blocks are identical then the successors should most likely be matched in the same order if self . blocks_probably_identical ( block_a , block_b ) and len ( block_a_succ ) == len ( block_b_succ ) : ordered_succ_a = self . _get_ordered_successors ( self . _project_a , block_a , block_a_succ ) ordered_succ_b = self . _get_ordered_successors ( self . _project_b , block_b , block_b_succ ) new_matches . extend ( zip ( ordered_succ_a , ordered_succ_b ) ) new_matches += self . _get_block_matches ( self . attributes_a , self . attributes_b , block_a_succ , block_b_succ , delta , tiebreak_with_block_similarity = True ) new_matches += self . _get_block_matches ( self . attributes_a , self . attributes_b , block_a_pred , block_b_pred , delta , tiebreak_with_block_similarity = True ) # for each of the possible new matches add it if it improves the matching for ( x , y ) in new_matches : if ( x , y ) not in processed_matches : processed_matches . add ( ( x , y ) ) l . debug ( "FunctionDiff: checking if (%#x, %#x) is better" , x . addr , y . addr ) # if it's a better match than what we already have use it if _is_better_match ( x , y , matched_a , matched_b , self . attributes_a , self . attributes_b ) : l . debug ( "FunctionDiff: adding possible match (%#x, %#x)" , x . addr , y . addr ) if x in matched_a : old_match = matched_a [ x ] del matched_b [ old_match ] if y in matched_b : old_match = matched_b [ y ] del matched_a [ old_match ] matched_a [ x ] = y matched_b [ y ] = x to_process . appendleft ( ( x , y ) ) # reformat matches into a set of pairs self . _block_matches = set ( ( x , y ) for ( x , y ) in matched_a . items ( ) ) # get the unmatched blocks self . _unmatched_blocks_from_a = set ( x for x in self . _function_a . graph . nodes ( ) if x not in matched_a ) self . _unmatched_blocks_from_b = set ( x for x in self . _function_b . graph . nodes ( ) if x not in matched_b )