/*
UC Santa Barbara ArchLab
www.cs.ucsb.edu/~arch
Wavelet-Based Phase Classification Source Code
www.cs.ucsb.edu/~arch/wavelet

Copyright (c) 2006 The Regents of the University of California.
All Rights Reserved.

Permission to use, copy, modify, and distribute this software and its
documentation for educational, research and non-profit purposes,
without fee, and without a written agreement is hereby granted,
provided that the above copyright notice, this paragraph and the
following three paragraphs appear in all copies.

Permission to incorporate this software into commercial products may
be obtained by contacting the University of California. For
information about obtaining such a license contact:
Tim Sherwood <sherwood at cs dot ucsb dot edu>

This software program and documentation are copyrighted by The Regents
of the University of California. The software program and
documentation are supplied "as is", without any accompanying services
from The Regents. The Regents does not warrant that the operation of
the program will be uninterrupted or error-free. The end-user
understands that the program was developed for research purposes and
is advised not to rely exclusively on the program for any reason.

IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY
FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES,
INCLUDING LOST PROFITS, ARISING OUT OF THE USE OF THIS SOFTWARE AND
ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF CALIFORNIA HAS BEEN
ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. THE UNIVERSITY OF
CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING, BUT NOT
LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS ON AN "AS IS"
BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATIONS TO PROVIDE
MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.

Ted Huffmire, (www.cs.ucsb.edu/~huffmire, huffmire at cs dot ucsb dot edu)
Tim Sherwood (www.cs.ucsb.edu/~sherwood, sherwood at cs dot ucsb dot edu)
14 June 2006

File: bb3.java

Publication:
Ted Huffmire and Tim Sherwood. Wavelet-Based Phase Classification. Proceedings 
of the Fifteenth International Conference on Parallel Architectures and 
Compilation Techniques (PACT'06), Seattle, Washington, September 16-20, 2006.
*/

import java.util.*;
import java.io.*;

class bb3 {
    public static final long INTERVALSIZE = 1000000L;

    public static void main(String args[])
    {
	long current_interval = 0;
	Vector addresses = new Vector();
	Vector lines = new Vector();

	BufferedReader br = null;
	if (args.length != 0) {
	    System.err.println("Usage: java bb3 < bb.out");
	    return;
	}
	cachesim cs = new cachesim(16384, 2, 32, 1048576, 4, 64);
	count is_l1hit = new count();
	count is_l2hit = new count();
	count accesstime = new count();
	try {
	    br = new BufferedReader(new InputStreamReader(System.in));
	} catch (Exception e) { handleEx(e); }
	Vector line_vector = new Vector();
	Vector frequency_vector = new Vector();
	Vector inst_vector = new Vector();
	Vector name_vector = new Vector();
	long OLDCOUNT = 0L;
	while (true) {
	    String s = "";
	    long COUNT=0L,ADDR=0L,MEMADDR=0L;
	    int index=0;
	    try { s = br.readLine(); } catch (Exception e) { handleEx(e); }

	    if (s == null || s.length() == 0) {
		try {s = br.readLine(); } catch (Exception e) { handleEx(e); }
		if (s == null)
		    break;
		else if (s.length() == 0)
		    continue;
	    }

	    if (s.charAt(0) == '#') continue;
	    else if (s.indexOf("Fini") != -1) continue;

	    index = s.indexOf(" ");
	    
	    if (index == -1) continue;
	    
	    String count = "", addr = "", memaddr="";

	    try {
		count = s.substring(0,index);
		s = s.substring(index+1);
		index = s.indexOf(" ");
		if (index == -1) continue;
		addr = s.substring(2, index);
		s = s.substring(index+1);
		index = s.indexOf(" ");
		if (index == -1) continue;
		memaddr = s.substring(2, index);
	    } catch (Exception e) { continue; }

	    try {
		COUNT = Long.parseLong(count, 10);
		if (COUNT > 2000000000L) {
		    System.err.println(""+COUNT);
		    continue;
		}
		OLDCOUNT = COUNT;
		ADDR = Long.parseLong(addr, 16);
		MEMADDR = Long.parseLong(memaddr, 16);
	    } catch (Exception e) { continue; }

	    String hexaddr = new PrintfFormat("%x").sprintf(ADDR);
	    String line = hexaddr+" ???:???:0";

	    cs.access(MEMADDR, is_l1hit, is_l2hit, accesstime);
	    if (is_l2hit.getvalue() == 0)
		insert(line, line_vector, frequency_vector);

	    if (COUNT/INTERVALSIZE > current_interval) {
		// reset stuff here
		System.err.println(" COUNT="+COUNT);
		output(current_interval, line_vector, frequency_vector);
		line_vector = null;
		frequency_vector = null;
		System.gc();
		line_vector = new Vector();
		frequency_vector = new Vector();
		System.gc();
		current_interval = COUNT/INTERVALSIZE;
	    }
	}
	output(current_interval, line_vector, frequency_vector);
	try { br.close(); } catch(Exception e) { handleEx(e); } 
    }

    static int find(long val, Vector vect)
    {
        int low=0, mid, high = vect.size() - 1;

        while (low <= high) {
            mid = (low + high) / 2;
            if (val == ((Long)(vect.elementAt(mid))).longValue()) {
                return mid;
            }
            else if (val < ((Long)(vect.elementAt(mid))).longValue()) {
                high = mid - 1;
            }
            else {
                low = mid + 1;
            }
        }
        return -1;
    }
 
    static int insert(String line, Vector lines, Vector frequencies)
    {
	int low=0, mid, high = lines.size() - 1;

	while (low <= high) {
	    mid = (low + high) / 2;
	    String val = (String)(lines.elementAt(mid));
	    if (line.compareTo(val) == 0) {
		Integer freq = (Integer)(frequencies.elementAt(mid));
		frequencies.setElementAt(new Integer(freq.intValue()+1),mid);
		return mid;
	    }
	    else if (line.compareTo(val) < 0) {
		high = mid - 1;
	    }
	    else {
		low = mid + 1;
	    }
	}
	lines.insertElementAt(new String(line), low);
	frequencies.insertElementAt(new Integer(1), low);
	return low;
    }

    static int insert(long addr, Vector addresses)
    {
	int low=0, mid, high = addresses.size() - 1;

	while (low <= high) {
	    mid = (low + high) / 2;
	    long val = ((Long)(addresses.elementAt(mid))).longValue();
	    if (addr == val) {
		return mid;
	    }
	    else if (addr < val) {
		high = mid - 1;
	    }
	    else {
		low = mid + 1;
	    }
	}
	addresses.insertElementAt(new Long(addr), low);
	return low;
    }

    public static void handleEx(Exception e) {
	System.err.println("" + e);
	e.printStackTrace();
    }

    static int findMax(Vector v)
    {
        int max = -1;
        int maxindex = 0;
        for (int i = 0; i < v.size(); i++) {
            int val = ((Integer)(v.elementAt(i))).intValue();
            if (val > max) {
                max = val;
                maxindex = i;
            }
        }
        return maxindex;
    }

    /*static void output(long current_interval, Vector line_vector, Vector frequency_vector)
    {
	System.err.print(""+current_interval+" ");
	System.err.print(" ["+line_vector.size()+"]");
	System.out.println("***** "+current_interval+" *****");
	int max = 100;
	for (int i = 0; i < max && i < line_vector.size(); i++) {
	    int maxindex = findMax(frequency_vector);
	    String line = (String)line_vector.elementAt(maxindex);
	    int freq = ((Integer)(frequency_vector.elementAt(maxindex))).intValue();
	    System.out.println(line);
	    System.out.println(""+freq);
	    line_vector.removeElementAt(maxindex);
	    frequency_vector.removeElementAt(maxindex);
	}
    }*/

    static void output(long current_interval, Vector line_vector, Vector frequency_vector)
    {
	System.err.print(""+current_interval+" ");
	System.err.print("["+line_vector.size()+"] ");
	System.out.println("***** "+current_interval+" *****");
	Vector indices = new Vector(), temp = new Vector();
	for (int i = 0; i < frequency_vector.size(); i++) {
	    indices.add(new Integer(i));
	    temp.add(new Integer(0));
	}
	mergeSort(frequency_vector, indices, temp, frequency_vector.size());
	int max = 100;
	for (int i = 0; i < max && i < line_vector.size(); i++) {
	    int maxindex = ((Integer)(indices.elementAt(frequency_vector.size() - 1 - i))).intValue();
	    String line = (String)line_vector.elementAt(maxindex);
	    int freq = ((Integer)(frequency_vector.elementAt(maxindex))).intValue();
	    System.out.println(line);
	    System.out.println(""+freq);
	}
    }

    static void mergeSort(Vector numbers, Vector indices, Vector temp, int size)
    {
	m_sort(numbers, indices, temp, 0, size-1);
    }
    
    static void m_sort(Vector numbers, Vector indices, Vector temp, int left, int right)
    {
	int mid;
	if (right > left) {
	    mid = (right + left) / 2;
	    m_sort(numbers, indices, temp, left, mid);
	    m_sort(numbers, indices, temp, mid+1, right);
	    merge(numbers, indices, temp, left, mid+1, right);
	}
    }
    
    static void merge(Vector numbers, Vector indices, Vector temp, int left, int mid, int right)
    {
	int i, left_end, num_elements, tmp_pos;
	left_end = mid-1;
	tmp_pos = left;
	num_elements = right - left + 1;
	while ((left <= left_end) && (mid <= right)) {
	    int leftindex = ((Integer)(indices.elementAt(left))).intValue();
	    int midindex = ((Integer)(indices.elementAt(mid))).intValue();
	    int leftnum = ((Integer)(numbers.elementAt(leftindex))).intValue();
	    int midnum = ((Integer)(numbers.elementAt(midindex))).intValue();
	    if (leftnum <= midnum) {
		temp.setElementAt((Integer)(indices.elementAt(left)),tmp_pos);
		tmp_pos++;
		left++;
	    } else {
		temp.setElementAt((Integer)(indices.elementAt(mid)), tmp_pos);
		tmp_pos++;
		mid++;
	    }
	}
	while (left <= left_end) {
	    temp.setElementAt((Integer)(indices.elementAt(left)),tmp_pos);
	    left++;
	    tmp_pos++;
	}
	while (mid <= right) {
	    temp.setElementAt((Integer)(indices.elementAt(mid)),tmp_pos);
	    mid++;
	    tmp_pos++;
	}
	for (i = 0; i <= num_elements; i++) {
	    if (right < 0) break;
	    indices.setElementAt((Integer)(temp.elementAt(right)),right);
	    right--;
	}
    }

    public static void zero(Vector counts)
    {
	for (int i = 0; i < counts.size(); i++) {
	    counts.setElementAt(new Integer(0), i);
	}
    }
}