/**
 * Copyright (c) 2004-2005, Regents of the University of California
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * Redistributions of source code must retain the above copyright notice,
 * this list of conditions and the following disclaimer.
 *
 * Redistributions in binary form must reproduce the above copyright
 * notice, this list of conditions and the following disclaimer in the
 * documentation and/or other materials provided with the distribution.
 *
 * Neither the name of the University of California, Los Angeles nor the
 * names of its contributors may be used to endorse or promote products
 * derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

package jintgen.gen.disassembler;

import cck.text.*;
import cck.util.*;
import jintgen.gen.Generator;
import jintgen.isdl.*;
import java.util.LinkedList;
import java.util.List;

/**
 * The <code>DisassemblerGenerator</code> class is a generator that can create a Java class
 * from an architecture description that disassembles binary instructions into the instruction
 * IR generated by the <code>InstrIRGenerator</code>.
 *
 * @author Ben L. Titzer
 */
public class DisassemblerGenerator extends Generator {

    static int WORD_SIZE;
    static boolean LITTLE_ENDIAN;
    static boolean LITTLE_BIT_ENDIAN;

    protected final Option.Bool MULTI_TREE = options.newOption("multiple-trees", false,
            "This option selects whether the disassembler generator will create multiple decode trees " +
            "(i.e. one per priority level) or whether it will create a single, unified tree. In some " +
            "instances one large tree is more efficient, while in others multiple smaller trees may be " +
            "more efficient.");
    protected final Option.Bool PARALLEL_TREE = options.newOption("parallel-trees", false,
            "This option selects whether the disassembler generator will create multiple decode trees " +
            "that are applied in parallel to resolve both the addressing mode and instruction. For " +
            "complex architectures, this can result in tremendously reduced tree sizes. For small architecture, " +
            "the result can be less efficient.");
    protected final Option.Bool CHAINED = options.newOption("chained-trees", false,
            "This option selects whether the disassembler generator will chain the decoders from multiple " +
            "priority levels together into one larger tree. This can reduce the complexity of the main " +
            "decoder loop, but is only supported for non-parallel decoder implementations.");
    protected final Option.Long WORD = options.newOption("word-size", 16,
            "This option controls the word size (in bits) that is used when generating the disassembler " +
            "code. The disassembler reads fields from individual words of the instruction stream. This " +
            "option tunes whether the disassembler will read 8, 16, 32, etc bits from the instruction " +
            "stream at a time.");
    protected final Option.Str ENDIAN = options.newOption("endian", "little",
            "This option controls whether the generated disassembler assumes big-endian or little-endian " +
            "ordering of bytes within words.");
    protected final Option.Str BIT_ENDIAN = options.newOption("bit-endian", "big",
            "This option controls whether the generated disassembler assumes big-endian or little-endian " +
            "ordering of bits within words. This is important for the description of encodings of " +
            "instructions. When set to \"big\", the disassembler generator assumes that the first logical " +
            "bit of an encoding description is the most significant bit of the word.");

    Verbose.Printer verbose = Verbose.getVerbosePrinter("jintgen.disassem");
    Verbose.Printer verboseDump = Verbose.getVerbosePrinter("jintgen.disassem.tree");
    Verbose.Printer dotDump = Verbose.getVerbosePrinter("jintgen.disassem.dot");

    int numEncodings = 0;
    int encodingInstances = 0;
    int instrs = 0;
    int pseudoInstrs = 0;
    int minInstrLength = Integer.MAX_VALUE;
    int maxInstrLength = 0;

    ReaderImplementation reader;
    Decoder implementation;

    public void generate() throws Exception {
        List<String> imports = new LinkedList<String>();
	imports.add("avrora.arch.AbstractDisassembler");
	imports.add("avrora.arch.AbstractInstr");
        imports.add("java.util.Arrays");
        initStatics();
        List<String> impl = new LinkedList<String>();
        impl.add("AbstractDisassembler");
        setPrinter(newClassPrinter("disassembler", imports, null, impl,
                tr("The <code>$disassembler</code> class decodes bit patterns into instructions. It has " +
                "been generated automatically by jIntGen from a file containing a description of the instruction " +
                "set and their encodings.\n\n" +
                "The following options have been specified to tune this implementation:\n\n" +
                "</p>-word-size=$1\n"+
                "</p>-parallel-trees=$2\n"+
                "</p>-multiple-trees=$3\n"+
                "</p>-chained-trees=$4\n",
                        WORD.get(), PARALLEL_TREE.get(), MULTI_TREE.get(), CHAINED.get())));

        generateHeader();
        generateDecodeTables();
        int maxprio = getMaxPriority();
        if ( PARALLEL_TREE.get() )
            implementation = new Decoder.Parallel(this, maxprio);
        else
            implementation = new Decoder.Serial(this, maxprio);

        reader = new ReaderImplementation(this);
        visitInstructions();
        reader.generateOperandReaders();
        implementation.compute();
        implementation.generate();
        if ( verboseDump.enabled ) {
            implementation.print(verboseDump);
        }
        if ( dotDump.enabled ) {
            implementation.dotDump();
        }
        Terminal.nextln();
        TermUtil.reportQuantity("Instructions", instrs, "");
        TermUtil.reportQuantity("Pseudo-instructions", pseudoInstrs, "");
        TermUtil.reportQuantity("Encodings", numEncodings, "");
        TermUtil.reportQuantity("Encoding Instances", encodingInstances, "");
        TermUtil.reportQuantity("Decoding Trees", implementation.numTrees, "");
        TermUtil.reportQuantity("Nodes", implementation.treeNodes, "");
        endblock();
    }

    private void initStatics() {
        properties.setProperty("addr", className("AddrMode"));
        properties.setProperty("instr", className("Instr"));
        properties.setProperty("operand", className("Operand"));
        properties.setProperty("opvisitor", className("OperandVisitor"));
        properties.setProperty("visitor", className("InstrVisitor"));
        properties.setProperty("builder", className("InstrBuilder"));
        properties.setProperty("symbol", className("Symbol"));
        properties.setProperty("disassembler", className("Disassembler"));

        WORD_SIZE = (int)WORD.get();
        LITTLE_ENDIAN = "little".equals(ENDIAN.get());
        LITTLE_BIT_ENDIAN = "little".equals(BIT_ENDIAN.get());
    }

    private int getMaxPriority() {
        int maxprio = 0;
        for ( InstrDecl d : arch.instructions ) {
            if (!d.pseudo) {
                for ( AddrModeDecl am : d.addrMode.addrModes ) {
                    for ( FormatDecl ed : am.encodings ) {
                        int prio = ed.getPriority();
                        if ( prio > maxprio ) maxprio = prio;
                    }
                }
            }
        }
        return maxprio;
    }

    private void visitInstructions() {
        for ( InstrDecl d : arch.instructions ) {
            if ( d.pseudo ) {
                pseudoInstrs++;
            } else {
                instrs++;
                int encodings = addEncodings(d);
                if ( encodings == 0 ) {
                    Terminal.nextln();
                    Terminal.printYellow("Warning");
                    Terminal.println(": instruction "+d.name+" has no declared encodings");
                }
            }
        }
    }

    private int addEncodings(InstrDecl d) {
        int encodings = 0;
        if ( d.addrMode.localDecl != null ) {
            encodings = addAllEncodings(d.addrMode.localDecl, d, d);
        } else {
            for ( AddrModeDecl am : d.addrMode.addrModes ) {
                encodings += addAllEncodings(am, d, null);
            }
        }
        return encodings;
    }

    private int addAllEncodings(AddrModeDecl am, InstrDecl d, InstrDecl instr) {
        int cntr = 0;
        for ( FormatDecl ed : am.encodings ) {
            addEncodingInfo(d, am, ed);
            String eName = encodingName(am, cntr);
            reader.addEncoding(eName, instr, ed, am);
            cntr++;
        }
        return cntr;
    }

    private String encodingName(AddrModeDecl am, int cntr) {
        return javaName(am.name+"_"+cntr);
    }

    private void generateHeader() {
        startblock("public static class InvalidInstruction extends Exception");
        startblock("InvalidInstruction(int pc) ");
        println("super(\"Invalid instruction at \"+pc);");
        endblock();
        endblock();
    }

    private void addEncodingInfo(InstrDecl d, AddrModeDecl am, FormatDecl ed) {
        EncodingInst ei = new EncodingInst(d, am, ed);
        implementation.add(ei);
        encodingInstances++;
    }

    private void generateDecodeTables() {
        for ( EnumDecl d : arch.enums ) {
            generateEnumDecodeTable(d);
        }
    }

    void generateEnumDecodeTable(EnumDecl d) {
        int max = getTableSize(d);
        String[] symbol = new String[max+1];
        for ( SymbolMapping.Entry e : d.map.getEntries() ) {
            symbol[e.value] = e.name;
        }
        String tablename = d.name+"_table";
        startblock("static final $symbol.$1[] $2 =", d.name, tablename);
        for ( int cntr = 0; cntr < symbol.length; cntr++ ) {
            if ( symbol[cntr] == null ) print("null");
            else print("$symbol.$1.$2", d.name, symbol[cntr].toUpperCase());
            if ( cntr != symbol.length - 1) print(", ");
            emitDecodeComment(max, cntr, symbol);
            nextln();
        }
        endblock(";");
    }

    private void emitDecodeComment(int max, int cntr, String[] symbol) {
        int lb = Arithmetic.highestBit(max);
        if ( lb <= 0 ) lb = 0;
        print(" // $1 (0b$2) -> $3", cntr, StringUtil.toBin(cntr, lb+1), symbol[cntr]);
    }

    private int getTableSize(EnumDecl d) {
        int max = 0;
        for ( SymbolMapping.Entry e : d.map.getEntries() ) {
            if ( e.value > max ) max = e.value;
        }
        if ( max > 64 && max > (d.map.size() * 2) ) {
            throw Util.failure("Enumeration "+StringUtil.quote(d.name)+" too sparse");
        }
        return max;
    }

    abstract class DTNodeImpl {
        String def;
        String action;
        final String nname;
        final int left;
        final int mask;
        final int length;

        DTNodeImpl(DTNode dt, String act, String d) {
            nname = nodeName(dt);
            def = d;
            length = dt.right_bit - dt.left_bit + 1;
            left = nativeBitOrder(dt.left_bit, length);
            mask = Arithmetic.getBitRangeMask(0, length - 1);
            action = act;
        }
        abstract void add(int value, String nname);
        abstract void generate();
    }

    class DTArrayNodeImpl extends DTNodeImpl {
        int current;
        String[] vals;

        DTArrayNodeImpl(DTNode dt, String action, String d) {
            super(dt, action, d);
            vals = new String[1 << length];
        }
        void add(int value, String nname) {
            if ( value == -1 ) def = nname;
            else {
                vals[value] = nname;
            }
        }
        void generate() {
            beginList("DTNode $1 = new DTArrayNode($2, $3, $4, new DTNode[] {", nname, action, left, mask);
            for ( String str : vals ) {
                if ( str == null ) print(def);
                else print(str);
            }
            endListln("});");
        }

    }

    class DTSortedNodeImpl extends DTNodeImpl {
        LinkedList<String> init = new LinkedList<String>();
        LinkedList<Integer> values = new LinkedList<Integer>();
        DTSortedNodeImpl(DTNode dt, String act, String d) {
            super(dt, act, d);
        }
        void add(int value, String nname) {
            if ( value == -1 ) def = nname;
            else {
                init.add(nname);
                values.add(value);
            }
        }

        void generate() {
            beginList("DTNode $1 = new DTSortedNode($2, $3, $4, new int[] {", nname, action, left, mask);
            for ( Integer i : values ) {
                print(i.toString());
            }
            endList("}, ");
            beginList("new DTNode[] {");
            for ( String str : init ) {
                print(str);
            }
            endListln("}, $1);", def);
        }
    }

    String nodeName(DTNode cdt) {
        if ( cdt.isLeaf() ) return "T"+cdt.number;
        else return "N"+cdt.number;
    }

    DTNodeImpl newDTNode(DTNode dt, String action, String def) {
        int size = 1 << (dt.right_bit - dt.left_bit);
        if ( size > 16 && (dt.getChildren().size() < (size/2)) ) return new DTSortedNodeImpl(dt, action, def);
        return new DTArrayNodeImpl(dt, action, def);
    }

    public static int nativeBitOrder(int left_bit, int length) {
        if ( !LITTLE_BIT_ENDIAN ) return WORD_SIZE - left_bit - length;
        return left_bit;
    }
}
