# `pwnlib.regsort` — Register sorting

Topographical sort

pwnlib.regsort.check_cycle(reg, assignments, mapping=None)

  Walk down the assignment list of a register, return the path walked if it is encountered again.

  Returns:

    The list of register involved in the cycle. If there is no cycle, this is an empty list.

  Example

      >>> check_cycle('a', {'a': 1})
      []
      >>> check_cycle('a', {'a': 'a'})
      ['a']
      >>> check_cycle('a', {'a': 'b', 'b': 'a'})
      ['a', 'b']
      >>> check_cycle('a', {'a': 'b', 'b': 'c', 'c': 'b', 'd': 'a'})
      []
      >>> check_cycle('a', {'a': 'b', 'b': 'c', 'c': 'd', 'd': 'a'})
      ['a', 'b', 'c', 'd']

pwnlib.regsort.extract_dependencies(reg, assignments, mapping=None)

  Return a list of all registers which directly depend on the specified register.

  Example

      >>> extract_dependencies('a', {'a': 1})
      []
      >>> extract_dependencies('a', {'a': 'b', 'b': 1})
      []
      >>> extract_dependencies('a', {'a': 1, 'b': 'a'})
      ['b']
      >>> extract_dependencies('a', {'a': 1, 'b': 'a', 'c': 'a'})
      ['b', 'c']

pwnlib.regsort.regsort(in_out, all_regs, mapping=None, tmp=None, xchg=True, randomize=None)

  Sorts register dependencies.

  Given a dictionary of registers to desired register contents, return the optimal order in which to set the registers to those contents.

  The implementation assumes that it is possible to move from any register to any other register.

  If a dependency cycle is encountered, one of the following will occur:

  - If `xchg` is `True`, it is assumed that dependency cyles can be broken by swapping the contents of two register (a la the `xchg` instruction on i386).

  - If `xchg` is not set, but not all destination registers in `in_out` are involved in a cycle, one of the registers outside the cycle will be used as a temporary register, and then overwritten with its final value.

  - If `xchg` is not set, and all registers are involved in a dependency cycle, the named register `temporary` is used as a temporary register.

  - If the dependency cycle cannot be resolved as described above, an exception is raised.

  Parameters:

    - in_out (dict) – Dictionary of desired register states. Keys are registers, values are either registers or any other value.

    - all_regs (list) – List of all possible registers. Used to determine which values in `in_out` are registers, versus regular values.

    - tmp (obj, str) – Named register (or other sentinel value) to use as a temporary register. If `tmp` is a named register and appears as a source value in `in_out`, dependencies are handled appropriately. `tmp` cannot be a destination register in `in_out`. If `bool(tmp)==True`, this mode is enabled.

    - xchg (obj) – Indicates the existence of an instruction which can swap the contents of two registers without use of a third register. If `bool(xchg)==False`, this mode is disabled.

    - random (bool) – Randomize as much as possible about the order or registers.

  Returns:

    A list of tuples of `(src, dest)`.

    Each register may appear more than once, if a register is used as a temporary register, and later overwritten with its final value.

    If `xchg` is `True` and it is used to break a dependency cycle, then `reg_name` will be `None` and `value` will be a tuple of the instructions to swap.

  Example

      >>> R = ['a', 'b', 'c', 'd', 'x', 'y', 'z']

  If order doesn’t matter for any subsequence, alphabetic order is used.

      >>> regsort({'a': 1, 'b': 2}, R)
      [('mov', 'a', 1), ('mov', 'b', 2)]
      >>> regsort({'a': 'b', 'b': 'a'}, R)
      [('xchg', 'a', 'b')]
      >>> regsort({'a': 'b', 'b': 'a'}, R, tmp='X')
      [('mov', 'X', 'a'),
       ('mov', 'a', 'b'),
       ('mov', 'b', 'X')]
      >>> regsort({'a': 1, 'b': 'a'}, R)
      [('mov', 'b', 'a'),
       ('mov', 'a', 1)]
      >>> regsort({'a': 'b', 'b': 'a', 'c': 3}, R)
      [('mov', 'c', 3),
       ('xchg', 'a', 'b')]
      >>> regsort({'a': 'b', 'b': 'a', 'c': 'b'}, R)
      [('mov', 'c', 'b'),
       ('xchg', 'a', 'b')]
      >>> regsort({'a':'b', 'b':'a', 'x':'b'}, R, tmp='y', xchg=False)
      [('mov', 'x', 'b'),
       ('mov', 'y', 'a'),
       ('mov', 'a', 'b'),
       ('mov', 'b', 'y')]
      >>> regsort({'a':'b', 'b':'a', 'x':'b'}, R, tmp='x', xchg=False)
      Traceback (most recent call last):
      ...
      PwnlibException: Cannot break dependency cycles ...
      >>> regsort({'a':'b','b':'c','c':'a','x':'1','y':'z','z':'c'}, R)
      [('mov', 'x', '1'),
       ('mov', 'y', 'z'),
       ('mov', 'z', 'c'),
       ('xchg', 'a', 'b'),
       ('xchg', 'b', 'c')]
      >>> regsort({'a':'b','b':'c','c':'a','x':'1','y':'z','z':'c'}, R, tmp='x')
      [('mov', 'y', 'z'),
       ('mov', 'z', 'c'),
       ('mov', 'x', 'a'),
       ('mov', 'a', 'b'),
       ('mov', 'b', 'c'),
       ('mov', 'c', 'x'),
       ('mov', 'x', '1')]
      >>> regsort({'a':'b','b':'c','c':'a','x':'1','y':'z','z':'c'}, R, xchg=0)
      [('mov', 'y', 'z'),
       ('mov', 'z', 'c'),
       ('mov', 'x', 'a'),
       ('mov', 'a', 'b'),
       ('mov', 'b', 'c'),
       ('mov', 'c', 'x'),
       ('mov', 'x', '1')]
       >>> regsort({'a': 'b', 'b': 'c'}, ['a','b','c'], xchg=0)
       [('mov', 'a', 'b'), ('mov', 'b', 'c')]

pwnlib.regsort.resolve_order(reg, deps)

  Resolve the order of all dependencies starting at a given register.

  Example

      >>> want = {'a': 1, 'b': 'c', 'c': 'd', 'd': 7, 'x': 'd'}
      >>> deps = {'a': [], 'b': [], 'c': ['b'], 'd': ['c', 'x'], 'x': []}
      >>> resolve_order('a', deps)
      ['a']
      >>> resolve_order('b', deps)
      ['b']
      >>> resolve_order('c', deps)
      ['b', 'c']
      >>> resolve_order('d', deps)
      ['b', 'c', 'x', 'd']