<commit_before># Copyright (c) 2017 <NAME>
# Distributed under the MIT software license, see the accompanying
# file COPYING or http://www.opensource.org/licenses/mit-license.php.
import opcodes
from decompiler.basicblock import find_basic_blocks
from decompiler.dataflow import analyze_basic_block, BBInput, IOutput, OMakeSet
from decompiler.expression import (Expression, OpExpression, ConstantIntExpression, FunctionCall, TakeAddressOf,
        VariableRef, GlobalVariableRef, ParameterRef, ReturnValueRef, LocalVariableRef, TempVariableRef,
        NilExpression)
from decompiler.statement import Statement, ExprStatement, AssignmentStatement
'''
p-code decompilation:

While tracing the flow of execution, keep track of a stack model.
This is fairly trivial as long as no set operations are encountered:

- Normal instructions can be represented as function calls e.g.
  sldc(0x02)
  ldcb(0x12)
  ldci(0x1234)
  mpi(ldci(0x1234), ldcb(0x12))
  ...
  Most of them return one value at most.
  First the instruction arguments, then the stack arguments.

- Storage instructions can be represented as statement:
  stl(0x12, 0x34)
  sro(0x14, ldcb(0x12))
  str(...)
  ...
  After the statement, the stack will (generally) be empty.

- Procedure calls can be represented in the same way. The number of arguments
  for every procedure is known and fixed (except for CFP).
  Return arguments should be handled pecially: we may need a static
  analysis pass to find these. Or use a heuristic. E.g. if something is pushed
  before the function call then used afterwards, this must be a return argument.
  Procedure calls have only up to one return value.

- Some instructions may have multiple return arguments which could be considered one
  unit, e.g. 
  
  - IXP for packed arrays, which LDP consumes. Then again, it also happens
  regularly that LDP input is simply pushed to the stack with other means,
  although the last two arguments are always constants.

  - Another set of stack values that could be considered one unit is the "string pointer"
  or "byte array pointer" which consists of an erec (which can be null for memory) and offset.

  - In this case being able to regard a block of stack values as unit helps, too.

- Set operations are where the difficulty appears: a set is one atomic "unit"
  for various operations but it gets pushed to the stack in multiple steps.
  What makes this somewhat easier is that all sets are statically-sized.
  - Small sets can be pushed as sequence of LDCI.
  - LDC, followed by LDCI for the size.
  - UNI: max(size(a),size(b))
  - INT: min(size(a),size(b))Ggg
  - DIF: size(a)
  - SRS: subrange set (depends on input)

- Control flow: (almost?) always the stack will be empty at control flow statements.
  This can be represented as goto's, ifs or while() statements where appropriate.

- Per basic block
  - Infer initial stack expectation
    e.g. [Int,Int,Set]
      - Complication: If a block of values is found to be a Set, this must be propagated back to previous blocks?
  - Inter stack expectation on exit
  - Should calls be treated as end of basic block?
    I don't think that is necessary in this analysis.

initial: [Int,Int]
dup1 [Int] [Int, Int]
srs  [Int Int] -> [Set]
ldc 0x2,0x2,0x7  -> [Set] [Block]
sldc7  [Set] [Block] [Int]
insert: virtual operation [Block Int] -> [Set]
uni   [Set Set] -> [Set]
inn   [Int Set] -> [Int]

- Insert virtual operation if a Set is needed and there's no set at the top of the stack
- If stack empty and pop happens -> add at start of initial stack expectation

Overall flow:

- Low level:
    - Determine basic blocks
    - Analyze each basic block
      - Link instruction inputs/outputs. Each instruction stack argument can link to either:
        - An output of a previous instruction
        - An input to the basic block (initial stack)
      - Outputs of basic block consist of the stack state.
- High level:
    - Use the resulting data structure to convert to statements and expressions
    - most instructions will be part of expressions - should take care
      to assign shared expressions to temporary variables
      (happens only in case of DUP1?)
    - in-values of BBs should get a temporary variable
    - assignment statements
      (store global, store local, store intermediate, store to memory ...)
    - variable references
      (load global, load local, load intermediate, load from memory...)
      also: take address of, with &
    - function calls (need to handle those that return values)
    - loops

'''

# TODO:
#  - handle instructions with multiple outputs (such as ixp) sanely - need
#  either multi-assignment to temporaries `(a,b,c) = ixp()` (DONE) or "types"
#  that wrap multiple values e.g. 'PackedIndex'.  Or both.  (set is a special
#  example of this). Of the often-used instructions only these have multiple out:
#    - ixp
#    - swap (handled by simply regarding expressions as swapped)
#    - dup1 (handled by assigning expression to temporary)
#
#  - xjp: jump tables
#  - lco: strings in-place?
#  - sind, ixa: indexing

####### Top level ########

def link_basic_blocks(basic_blocks):
    '''Link together basic blocks inputs and outputs with temporaries'''
    # The overall algorithm is to visit all outputs of all basic blocks,
    # and group them together. Each such group is assigned a temporary.
    # Outputs belong to the same group if they share an input on some bb.
    # Inputs are labeled with the same temporary.

    # TODO: as it is a stack oriented machine, it is possible for BB outputs to
    # 'jump over' basic blocks if something is pushed deeper on the stack of
    # the origin bb than the target bb will consume. To handle this it'd be
    # necessary to consider longer paths instead of just direct connections.
    # For now, assert that ins match outs. This seems to be enough to get us
    # through SYSTEM.STARTUP.
    for bb in basic_blocks.blocks:
        for bbs in bb.succ:
            if len(bbs.ins) != len(bb.outs):
                print('DIFFERENCE: %05x outs %d versus %05x ins %d' % (bb.addr, len(bb.outs), bbs.addr, len(bbs.ins)))
                print(bb.outs)
                print(bbs.ins)
                raise NotImplementedError

    tcount = 0x100 # Non-local temps
    # Iterate, assign temporaries
    for bb in basic_blocks.blocks:<commit_msg>decompile: comment update<commit_after># Copyright (c) 2017 <NAME>
# Distributed under the MIT software license, see the accompanying
# file COPYING or http://www.opensource.org/licenses/mit-license.php.
import opcodes
from decompiler.basicblock import find_basic_blocks
from decompiler.dataflow import analyze_basic_block, BBInput, IOutput, OMakeSet
from decompiler.expression import (Expression, OpExpression, ConstantIntExpression, FunctionCall, TakeAddressOf,
        VariableRef, GlobalVariableRef, ParameterRef, ReturnValueRef, LocalVariableRef, TempVariableRef,
        NilExpression)
from decompiler.statement import Statement, ExprStatement, AssignmentStatement
'''
p-code decompilation:

While tracing the flow of execution, keep track of a stack model.
This is fairly trivial as long as no set operations are encountered:

- Normal instructions can be represented as function calls e.g.
  sldc(0x02)
  ldcb(0x12)
  ldci(0x1234)
  mpi(ldci(0x1234), ldcb(0x12))
  ...
  Most of them return one value at most.
  First the instruction arguments, then the stack arguments.

- Storage instructions can be represented as statement:
  stl(0x12, 0x34)
  sro(0x14, ldcb(0x12))
  str(...)
  ...
  After the statement, the stack will (generally) be empty.

- Procedure calls can be represented in the same way. The number of arguments
  for every procedure is known and fixed (except for CFP).
  Return arguments should be handled pecially: we may need a static
  analysis pass to find these. Or use a heuristic. E.g. if something is pushed
  before the function call then used afterwards, this must be a return argument.
  Procedure calls have only up to one return value.

- Some instructions may have multiple return arguments which could be considered one
  unit, e.g. 
  
  - IXP for packed arrays, which LDP consumes. Then again, it also happens
  regularly that LDP input is simply pushed to the stack with other means,
  although the last two arguments are always constants.

  - Another set of stack values that could be considered one unit is the "string pointer"
  or "byte array pointer" which consists of an erec (which can be null for memory) and offset.

  - In this case being able to regard a block of stack values as unit helps, too.

- Set operations are where the difficulty appears: a set is one atomic "unit"
  for various operations but it gets pushed to the stack in multiple steps.
  What makes this somewhat easier is that all sets are statically-sized.
  - Small sets can be pushed as sequence of LDCI.
  - LDC, followed by LDCI for the size.
  - UNI: max(size(a),size(b))
  - INT: min(size(a),size(b))Ggg
  - DIF: size(a)
  - SRS: subrange set (depends on input)

- Control flow: (almost?) always the stack will be empty at control flow statements.
  This can be represented as goto's, ifs or while() statements where appropriate.

- Per basic block
  - Infer initial stack expectation
    e.g. [Int,Int,Set]
      - Complication: If a block of values is found to be a Set, this must be propagated back to previous blocks?
  - Inter stack expectation on exit
  - Should calls be treated as end of basic block?
    I don't think that is necessary in this analysis.

initial: [Int,Int]
dup1 [Int] [Int, Int]
srs  [Int Int] -> [Set]
ldc 0x2,0x2,0x7  -> [Set] [Block]
sldc7  [Set] [Block] [Int]
insert: virtual operation [Block Int] -> [Set]
uni   [Set Set] -> [Set]
inn   [Int Set] -> [Int]

- Insert virtual operation if a Set is needed and there's no set at the top of the stack
- If stack empty and pop happens -> add at start of initial stack expectation

Overall flow:

- Low level:
    - Determine basic blocks
    - Analyze each basic block
      - Link instruction inputs/outputs. Each instruction stack argument can link to either:
        - An output of a previous instruction
        - An input to the basic block (initial stack)
      - Outputs of basic block consist of the stack state.
- High level:
    - Use the resulting data structure to convert to statements and expressions
    - most instructions will be part of expressions - should take care
      to assign shared expressions to temporary variables
      (happens only in case of DUP1?)
    - in-values of BBs should get a temporary variable
    - assignment statements
      (store global, store local, store intermediate, store to memory ...)
    - variable references
      (load global, load local, load intermediate, load from memory...)
      also: take address of, with &
    - function calls (need to handle those that return values)
    - loops

'''

# TODO:
#  - handle instructions with multiple outputs (such as ixp) sanely - need
#  either multi-assignment to temporaries `(a,b,c) = ixp()` (DONE) or "types"
#  that wrap multiple values e.g. 'PackedIndex'.  Or both.  (set is a special
#  example of this). Of the often-used instructions only these have multiple out:
#    - ixp
#    - swap (handled by simply regarding expressions as swapped)
#    - dup1 (handled by assigning expression to temporary)
#
#  - xjp: jump tables
#  - lco: strings in-place?
#  - sind, ixa: indexing
#  - use labels for jump instruction, for better consistency
#     bb0029:
#     004a: ujp(0x29)

####### Top level ########

def link_basic_blocks(basic_blocks):
    '''Link together basic blocks inputs and outputs with temporaries'''
    # The overall algorithm is to visit all outputs of all basic blocks,
    # and group them together. Each such group is assigned a temporary.
    # Outputs belong to the same group if they share an input on some bb.
    # Inputs are labeled with the same temporary.

    # TODO: as it is a stack oriented machine, it is possible for BB outputs to
    # 'jump over' basic blocks if something is pushed deeper on the stack of
    # the origin bb than the target bb will consume. To handle this it'd be
    # necessary to consider longer paths instead of just direct connections.
    # For now, assert that ins match outs. This seems to be enough to get us
    # through SYSTEM.STARTUP.
    for bb in basic_blocks.blocks:
        for bbs in bb.succ:
            if len(bbs.ins) != len(bb.outs):
                print('DIFFERENCE: %05x outs %d versus %05x ins %d' % (bb.addr, len(bb.outs), bbs.addr, len(bbs.ins)))
                print(bb.outs)
                print(bbs.ins)
                raise NotImplementedError

    tcount = 0x100 # Non-local temps
    # Iterate, assign temporaries
    for bb in basic_blocks.blocks:
{'fraction_non_alphanumeric': 0.07238333463612913, 'fraction_numerical': 0.009067458766512937, 'mean_word_length': 3.281793842034806, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 17, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4075717', 'n_tokens_mistral': 3645, 'n_tokens_neox': 3490, 'n_words': 1728}