public abstract class AbstractCodeNode {

	private static final int INITIAL_BUFFER_SIZE = 4;
	private AbstractCodeNode[] childs;
	private int codeAddress;
	
	
	public abstract void print(CodePrinter printer);
	
	public AbstractCodeNode() {
		childs = new AbstractCodeNode[INITIAL_BUFFER_SIZE];
		codeAddress = 0;
	}
	
	public AbstractCodeNode read() {
		if (childs[codeAddress] == null)
			return null;
		return childs[codeAddress++];
	}
	
	public AbstractCodeNode read(int addr) {
		if (addr < 0 || addr >= childs.length || (addr > 0 && childs[addr - 1] == null))
			throw new IllegalArgumentException("Invalid address.");
		return childs[addr];
	}
	
	public void write(AbstractCodeNode node) {
		if (needsExpand())
			expand();
		if (childs[codeAddress] == null)
			childs[codeAddress++] = node;
		else {
			List<AbstractCodeNode> taken = new ArrayList<AbstractCodeNode>();
			for (int i = codeAddress; i < childs.length; i++) {
				if (childs[i] != null) {
					taken.add(childs[i]);
					childs[i] = null;
				}
			}
			childs[codeAddress] = node;
			int write = ++codeAddress;
			for (AbstractCodeNode n : taken)
				childs[write++] = n;
		}
	}
	
	public void delete() {
		delete(codeAddress);
	}
	
	public void delete(int address) {
		if (address < 0 || address >= childs.length || (address > 0 && childs[address - 1] == null))
			throw new IllegalArgumentException("Invalid address.");
		if (childs[address] == null)
			throw new RuntimeException("No element to delete.");
		if ((address + 1) < childs.length && childs[address + 1] == null)
			childs[address] = null;
		else {
			childs[address] = null;
			for (int i = address + 1; i < childs.length; i++) {
				childs[i - 1] = childs[i];
				childs[i] = null;
			}
		}
	}
	
	public int addressOf(AbstractCodeNode child) {
		for (int i = 0; i < childs.length; i++)
			if (childs[i] == child)
				return i;
		return -1;
	}
	
	public List<AbstractCodeNode> listChilds() {
		List<AbstractCodeNode> list = new ArrayList<AbstractCodeNode>();
		for (int i = 0; i < childs.length; i++)
			if (childs[i] != null)
				list.add(childs[i]);
		return list;
	}
	
	public int size() {
		int total = 0;
		for (int i = 0; i < childs.length; i++)
			if (childs[i] != null)
				total++;
		return total;
	}
	

	private boolean needsExpand() {
		double max = childs.length * 0.50;
		return (double)size() > max;
	}
	
	
	private void expand() {
		if (childs.length >= Integer.MAX_VALUE)
			throw new RuntimeException("Can't expand anymore.");
		long newSize = childs.length * 2;
		if (newSize > Integer.MAX_VALUE)
			newSize = Integer.MAX_VALUE;
		AbstractCodeNode[] newBuffer = new AbstractCodeNode[(int)newSize];
		System.arraycopy(childs, 0, newBuffer, 0, childs.length);
		childs = newBuffer;
	}	

	
	@Override
	public String toString() {
		return CodePrinter.print(this);
	}

	public void setCodeAddress(int codeAddress) {
		if (codeAddress < 0 || codeAddress >= childs.length || (codeAddress > 0 && childs[codeAddress - 1] == null))
			throw new IllegalArgumentException("Invalid address.");
		this.codeAddress = codeAddress;
	}

	public int getCodeAddress() {
		return codeAddress;
	}
}
 public class ConditionalFlowBlockJump extends AbstractCodeNode {

    /**
     * Contains expression which type is boolean.
     */
    private ExpressionNode expression;
    /**
     * Contains target flow block.
     */
    private FlowBlock target;
    
    public ConditionalFlowBlockJump(ExpressionNode expr,FlowBlock target) {
    	this.expression = expr;
    	this.target = target;
		this.write(expr);
		expr.setParent(this);
    }
    

	public ExpressionNode getExpression() {
		return expression;
	}
	
	public FlowBlock getTarget() {
		return target;
	}

	@Override
	public void print(CodePrinter printer) {
		printer.beginPrinting(this);
		printer.print("IF (");
		expression.print(printer);
		printer.print(") ");
		printer.tab();
		printer.print("\nGOTO\t" + "flow_" + target.getBlockID());
		printer.untab();
		printer.endPrinting(this);
	}
}
 public class FlowBlock extends AbstractCodeNode {

	/**
	 * Contains ID of this flow block.
	 * Main flow block ID is always 0.
	 */
	private int blockID;
	/**
	 * Contains all blocks to which this blocks 
	 * jumps with instructions.
	 */
	private List<FlowBlock> sucessors;
	/**
	 * Contains all blocks which jumps to this block
	 * with instructions.
	 */
	private List<FlowBlock> predecesors;
	/**
	 * Contains next flow block by code order.
	 * Can be null if this block is the last block.
	 */
	private FlowBlock next;
	/**
	 * Contains previous flow block by code order.
	 * Can be null if this block is the first block.
	 */
	private FlowBlock prev;
	/**
	 * Contains stack content before jumping/walking into this
	 * block dumped to local variables. 
	 */
	private CS2Stack variableStack;
	/**
	 * Contains start address of this flow block in instructions.
	 * Not guaranteed to be correct.
	 */
	private int startAddress;

	public FlowBlock() {
		this(0, 0, new CS2Stack());
	}
	
	public FlowBlock(int blockID, int startAddress,CS2Stack stack) {
		this.blockID = blockID;
		this.startAddress = startAddress;
		this.variableStack = stack;
		this.sucessors = new ArrayList<FlowBlock>();
		this.predecesors = new ArrayList<FlowBlock>();
	}
	
	
	
	@Override
	public void print(CodePrinter printer) {
		printer.beginPrinting(this);
		printer.print("flow_" + this.blockID + ":");
		printer.tab();
		List<AbstractCodeNode> childs = this.listChilds();
		for (AbstractCodeNode node : childs) {
			printer.print('\n');
			node.print(printer);
		}
		printer.untab();
		printer.endPrinting(this);
	}
	
	public List<FlowBlock> getPredecesors() {
		return predecesors;
	}
	
	public List<FlowBlock> getSucessors() {
		return sucessors;
	} 

	public void setNext(FlowBlock next) {
		this.next = next;
	}

	public FlowBlock getNext() {
		return next;
	}

	public void setPrev(FlowBlock prev) {
		this.prev = prev;
	}

	public FlowBlock getPrev() {
		return prev;
	}
	
	public CS2Stack getStack() {
		return variableStack;
	}

	public int getStartAddress() {
		return startAddress;
	}
	
	public int getBlockID() {
		return blockID;
	}
	
	public boolean isSynthethic() {
		return startAddress < 0;
	}



}
 public class FunctionNode extends AbstractCodeNode {

	private int id;
	private String name;
	private CS2Type[] argumentTypes;
	private String[] argumentNames;
	private LocalVariable[] argumentLocals;
	private CS2Type returnType;
	private ScopeNode scope;
	

	public FunctionNode(int id, String name,CS2Type[] args, String[] argnames, CS2Type returnType) {
		this.id = id;
		this.name = name;
		this.argumentTypes = args;
		this.argumentNames = argnames;
		this.returnType = returnType;
		this.argumentLocals = new LocalVariable[args.length];
		this.scope = new ScopeNode();
		this.write(scope);
		scope.setParent(this);
	}

	
	public int getId() {
		return id;
	}

	public String getName() {
		return name;
	}

	public CS2Type[] getArgumentTypes() {
		return argumentTypes;
	}
	
	public String[] getArgumentNames() {
		return argumentNames;
	}
	
	public LocalVariable[] getArgumentLocals() {
		return argumentLocals;
	}

	public void setReturnType(CS2Type returnType) {
		this.returnType = returnType;
	}

	public CS2Type getReturnType() {
		return returnType;
	}


	public ScopeNode getScope() {
		return scope;
	}
	

	@Override
	public void print(CodePrinter printer) {
		printer.beginPrinting(this);
		int precount = 0;
		for (int i = 0; i < size(); i++) {
			if (read(i) == scope)
				break;
			read(i).print(printer);
			printer.print('\n');
			precount++;
		}
		
		if (precount > 0)
			printer.print("\n\n");
		
		printer.print(this.returnType.toString());
		printer.print(' ');
		printer.print(this.name);
		printer.print('(');
		for (int i = 0; i < argumentLocals.length; i++) {
			printer.print(argumentLocals[i].toString());
			if ((i + 1) < argumentTypes.length)
				printer.print(',');
		}
		printer.print(')');
		printer.print(' ');
		this.scope.print(printer);
		printer.endPrinting(this);
	}


	
}
 public class LocalVariable {

	private String name;
	private CS2Type type;
	private int identifier = -1;
	private boolean needsScopeDeclaration = true;
	private boolean isArgument;
	
	public LocalVariable(String name,CS2Type type) {
		this(name,type, false);
	}
	
	public LocalVariable(String name,CS2Type type, boolean isArgument) {
		this.name = name;
		this.type = type;
		this.isArgument = isArgument;
	}

	public CS2Type getType() {
		return type;
	}

	public String getName() {
		return name;
	}
	
	public void setName(String name) {
		this.name = name;
	}
	
	public boolean isArgument() {
		return isArgument;
	}
	
	public String toString() {
		return type + " " + name;
	}

	public void setIdentifier(int identifier) {
		this.identifier = identifier;
	}

	public int getIdentifier() {
		return identifier;
	}
	
	public boolean needsScopeDeclaration() {
		return needsScopeDeclaration;
	}
	
	public void setNeedsScopeDeclaration(boolean v) {
		needsScopeDeclaration = v;
	}

	public static int makeIdentifier(int index,int stackType) {
		return index | stackType << 16;
	}
	
	public static int makeStackDumpIdentifier(int index, int stackType) {
		return index | (stackType << 16) | 0x40000000;
	}
}
 public class ReturnNode extends AbstractCodeNode {

    /**
     * Contains return expression.
     */
    private ExpressionNode expression;
        
    public ReturnNode() {
    	this(null);
    }
    
    public ReturnNode(ExpressionNode expr) {
    	this.expression = expr;
		if (expr != null) {
			this.write(expr);
			expr.setParent(this);
		}
    }

	public ExpressionNode getExpression() {
		return expression;
	}

	@Override
	public void print(CodePrinter printer) {
		printer.beginPrinting(this);
		if (this.expression != null) {
			printer.print("return ");
			expression.print(printer);
			printer.print(';');
		}
		else {
			printer.print("return;");
		}
		printer.endPrinting(this);
	}

}
 public class SwitchFlowBlockJump extends AbstractCodeNode {


    private ExpressionNode expression;
    private int[] cases;
    private FlowBlock[] targets;
    private int defaultIndex;
    
    public SwitchFlowBlockJump(ExpressionNode expr,int[] cases, FlowBlock[] targets, int defaultIndex) {
    	this.expression = expr;
    	this.cases = cases;
    	this.targets = targets;
		this.defaultIndex = defaultIndex;
		this.write(expr);
		expr.setParent(this);
    }
    

	public ExpressionNode getExpression() {
		return expression;
	}
	
	public int[] getCases() {
		return cases;
	}
	
	public FlowBlock[] getTargets() {
		return targets;
	}
	
	public int getDefaultIndex() {
		return defaultIndex;
	}
	


	@Override
	public void print(CodePrinter printer) {
		printer.beginPrinting(this);
		printer.print("SWITCH (");
		expression.print(printer);
		printer.print(") {");
		printer.tab();
		for (int i = 0; i < cases.length; i++) {
			if (i == defaultIndex)
				printer.print("\ndefault:\n\t GOTO flow_" + targets[i].getBlockID());
			else
				printer.print("\ncase " + cases[i] + ":\n\t GOTO flow_" + targets[i].getBlockID());
		}
		
		printer.untab();
		printer.print("\n}");
		printer.endPrinting(this);

	}
}
 public class UnconditionalFlowBlockJump extends AbstractCodeNode {

    /**
     * Contains target flow block.
     */
    private FlowBlock target;
    
    public UnconditionalFlowBlockJump(FlowBlock target) {
    	this.target = target;
    }
 
	
	public FlowBlock getTarget() {
		return target;
	}

	@Override
	public void print(CodePrinter printer) {
		printer.beginPrinting(this);
		printer.print("GOTO\t" + "flow_" + target.getBlockID());
		printer.endPrinting(this);
	}
}
 public class VariableAssignationNode extends ExpressionNode {


    private LocalVariable variable;
    private ExpressionNode expression;
    private boolean isDeclaration = false;
    
    public VariableAssignationNode(LocalVariable variable,ExpressionNode expr) {
    	this.variable = variable;
    	this.expression = expr;
    	this.write(expr);
    	expr.setParent(this);
    }
    
    @Override
    public int getPriority() {
    	return ExpressionNode.PRIORITY_ASSIGNMENT;
    }

    @Override
    public CS2Type getType() {
    	return this.expression.getType();
    }

	@Override
	public ExpressionNode copy() {
		return new VariableAssignationNode(this.variable,this.expression.copy());
	}

	public LocalVariable getVariable() {
		return variable;
	}
	
	public void setVariable(LocalVariable v) {
		this.variable = v;
	}

	public ExpressionNode getExpression() {
		return expression;
	}
	
	public boolean isDeclaration() {
		return isDeclaration;
	}
	
	public void setIsDeclaration(boolean is) {
		isDeclaration = is;
	}

	@Override
	public void print(CodePrinter printer) {
		printer.beginPrinting(this);
		boolean needsParen = expression.getPriority() > getPriority();
		if (isDeclaration)
			printer.print(variable.getType() + " ");
		printer.print(variable.getName() + " = ");
		if (needsParen)
			printer.print('(');
		expression.print(printer);
		if (needsParen)
			printer.print(')');
		printer.endPrinting(this);
	}

}
 public class VariableLoadNode extends ExpressionNode {


    private LocalVariable variable;
    
    public VariableLoadNode(LocalVariable variable) {
    	this.variable = variable;
    }

    @Override
    public CS2Type getType() {
    	return this.variable.getType();
    }

	@Override
	public ExpressionNode copy() {
		return new VariableLoadNode(this.variable);
	}

	public LocalVariable getVariable() {
		return variable;
	}
	
	public void setVariable(LocalVariable v) {
		this.variable = v;
	}

	@Override
	public void print(CodePrinter printer) {
		printer.beginPrinting(this);
		printer.print(variable.getName());
		printer.endPrinting(this);
	}

}

import mgi.tools.jagdecs2.ast.VariableAssignationNode;
import mgi.tools.jagdecs2.ast.VariableLoadNode;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import mgi.tools.jagdecs2.ast.AbstractCodeNode;
import mgi.tools.jagdecs2.ast.ConditionalFlowBlockJump;
import mgi.tools.jagdecs2.ast.FlowBlock;
import mgi.tools.jagdecs2.ast.FunctionNode;
import mgi.tools.jagdecs2.ast.LocalVariable;
import mgi.tools.jagdecs2.ast.ReturnNode;
import mgi.tools.jagdecs2.ast.SwitchFlowBlockJump;
import mgi.tools.jagdecs2.ast.UnconditionalFlowBlockJump;

				
				processNode(states[i], blocks[i]);
				count++;
			}
		}
		while (count > 0);
		
	}
	
	private void end() {	
		for (AbstractCodeNode n : accesses.keySet())
			merge(new ArrayList<Integer>(accesses.get(n)));		
		
		
		List<LocalVariable> old = function.getScope().copyDeclaredVariables();
		for (LocalVariable v : old)
			function.getScope().undeclare(v);
		
		List<LocalVariable> nvars = new ArrayList<LocalVariable>();
		List<LocalVariable> nargs = new ArrayList<LocalVariable>();
		
		int count = 0;
		int argcount = 0;
		for (List<Integer> vars : accesses.values()) {
			if (vars.size() != 1)
				throw new DecompilerException("Not merged");
			
			LocalVariable v = variables.get(vars.get(0));
			if (nvars.contains(v))
				continue;
			
			nvars.add(v);
			if (v.isArgument()) {
				v.setNeedsScopeDeclaration(false);
				nargs.add(v);
			}
			v.setName(v.isArgument() ? ("a" + argcount++) : ("v" + count++));
		}
		
		System.err.println(nargs.size() + "," + function.getArgumentLocals().length);
		if (nargs.size() != function.getArgumentLocals().length)
			throw new DecompilerException("something failed");
		
		int write = 0;
		for (LocalVariable v : nargs)
			function.getArgumentLocals()[write++] = v;
		
		for (LocalVariable v : nvars)
			function.getScope().declare(v);
		
		for (AbstractCodeNode n : accesses.keySet()) {
			LocalVariable nvar = variables.get(accesses.get(n).get(0));
			if (n instanceof VariableLoadNode)
				((VariableLoadNode)n).setVariable(nvar);
			else if (n instanceof VariableAssignationNode)
				((VariableAssignationNode)n).setVariable(nvar);
			else if (n.getCodeAddress() == Integer.MIN_VALUE)
				; // XXX this is our dummy node
			else
				throw new DecompilerException("logic error");
		}
	}
	
	private void merge(List<Integer> vars) {
		if (vars.size() < 2)
			return;
		
		int main = vars.get(0);
		LocalVariable vmain = variables.get(main);
		String name = vmain.getName();
		CS2Type type = vmain.getType();
		boolean arg = vmain.isArgument();
		for (int var : vars) {
			if (var == main)
				continue;
			
			LocalVariable vother = variables.get(var);
			if (!vother.getName().equals(name) || !vother.getType().equals(type))
				throw new DecompilerException("Can't merge " + vmain + " with " + vother);
			arg = arg || vother.isArgument();
		}
		
		LocalVariable merged = new LocalVariable(name, type, arg);
		variables.put(main, merged);
		
		for (AbstractCodeNode n : accesses.keySet()) {
			List<Integer> varlist = accesses.get(n);
			
			boolean has = false;
			Iterator<Integer> it$ = varlist.iterator();
			while (it$.hasNext()) {
				Integer var = it$.next();
				if (vars.contains(var)) {
					it$.remove();
					has = true;
				}
			}
			
			if (has)
				varlist.add(main);
		}
	}
	
	
	private boolean processNode(FlowBlockState state, AbstractCodeNode n) {
		boolean quit = false;
		for (int i = 0; i < n.size(); i++) {
			boolean q = processNode(state, n.read(i));
			quit = quit || q;
		}
		
		if (n instanceof ConditionalFlowBlockJump) {
			ConditionalFlowBlockJump jmp = (ConditionalFlowBlockJump)n;
			queue(state, jmp.getTarget());
		}
		else if (n instanceof UnconditionalFlowBlockJump) {
			UnconditionalFlowBlockJump jmp = (UnconditionalFlowBlockJump)n;
			queue(state, jmp.getTarget());
			return true;
		}

		else if (n instanceof SwitchFlowBlockJump) {
