/*
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: cov.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 cov {
    public static final long INTERVALSIZE = 1000000L;

    public static void main(String args[])
    {
        int oldphase = 0;
	Vector phases = new Vector();
	Vector misses = new Vector();
        Vector frequencies = new Vector();
        Vector lines = new Vector();
        Vector indices = new Vector();
        Vector files = new Vector();
        Vector pcs = new Vector();
	BufferedReader br = null;
	if (args.length != 2) {
	    System.err.println("Usage: java cov firefox.pc firefox.labels");
	    System.exit(1);
	}
	try {
	    br = new BufferedReader(new FileReader(args[0]));
	} catch (Exception e) { handleEx(e); }
	while (true) {
            String s = "";
            try { s = br.readLine(); } catch (Exception e) { handleEx(e); }
            if (s == null) break;
            if (s.indexOf("*****") == 0) {
                s = s.substring(6);
                int index = s.indexOf(" *****");
                if (index == -1) continue;
                String phase = s.substring(0, index);
                int PHASE = 0;
                try { PHASE=Integer.parseInt(phase,10);}catch(Exception e) { handleEx(e);}
                for (int i = 0; i < PHASE-oldphase-1; i++) {
                    indices.add(new Integer(-1));
                }
                indices.add(new Integer(lines.size()));
                oldphase = PHASE;
                continue;
	    } else if (s.indexOf(":") != -1) {
                int index = s.indexOf(" ");
                if (index == -1) {
                    System.err.println("fatal error");
                    System.exit(1);
                }
                String pc = s.substring(0, index);
                s = s.substring(index+1);
                index = s.lastIndexOf(":");
                if (index == -1) continue;
                String file = s.substring(0, index);
                String line = s.substring(index+1);
                files.add(new String(file));
                int LINE = Integer.parseInt(line, 10);
                lines.add(new Integer(LINE));
                pcs.add(new String(pc));
            } else {
                int freq = Integer.parseInt(s,10);
                frequencies.add(new Integer(freq));
            }
	}
	try { br.close(); } catch(Exception e) { handleEx(e); } 
	try {
	    br = new BufferedReader(new FileReader(args[1]));
	} catch (Exception e) { handleEx(e); }
	while (true) {
	    String s = "";
	    try { s = br.readLine(); } catch (Exception e) { handleEx(e); }
	    if (s == null) break;
	    int index = s.indexOf(" ");
	    if (index == -1) return;
	    String phase = s.substring(0, index);
	    int PHASE = Integer.parseInt(phase, 10);
	    phases.add(new Integer(PHASE));
	}
	try { br.close(); } catch(Exception e) { handleEx(e); } 
	
	for (int j = 0; j < phases.size(); j++) {
	    int lowerindex = ((Integer)(indices.elementAt(j))).intValue();
            int upperindex=0;
	    if (j == indices.size() - 1) {
		upperindex = lines.size();
	    } else {
		upperindex = ((Integer)(indices.elementAt(j+1))).intValue();            
	    }
	    if (lowerindex == -1 || upperindex == -1) {
		System.err.println("Fatal error.");
		return;
	    } else {
		String s1 = "";
		int num_misses = 0;
                for (int i = lowerindex; i < upperindex; i++) {
                    int freq = ((Integer)(frequencies.elementAt(i))).intValue();
		    num_misses += freq;
                }
		misses.add(new Integer(num_misses));
	    }
	}
	double totalweightedcov = 0.0;
	long totalmiss = 0L;
	int totalphases = 0;
	for (int i = 0; i < phases.size(); i++) {
	    int phase = ((Integer)(phases.elementAt(i))).intValue();
	    int miss = ((Integer)(misses.elementAt(i))).intValue();
	    int N = 0;
	    for (int j = i+1; j < phases.size(); j++) {
		//System.out.print("["+i);
		int nextphase = ((Integer)(phases.elementAt(j))).intValue();
		if (phase == nextphase) {
		    miss += ((Integer)(misses.elementAt(j))).intValue();
		    N++;
		}
		else {
		    break;
		}
	    }
	    double avgmiss = (double)miss / (double)(N+1);
	    double sum = 0;
	    for (int j = i; j < i+N+1; j++) {
		int m = ((Integer)(misses.elementAt(j))).intValue();
		sum += ((double)m-avgmiss) * ((double)m-avgmiss);
	    }
	    sum /= ((double)(N+1));
	    // I should have called this variable "standard deviation"
	    // instead of "variance." Sorry for the confusion.
	    double variance = java.lang.Math.sqrt(sum); 
	    // I should have called this variable 
	    // "unweighted standard deviation"
	    double cov = variance;
	    totalmiss += (long)miss;
	    double weightedcov = cov * ((double)(N+1));
	    totalweightedcov += weightedcov;
	    i += N;
	    totalphases++;
	    //System.out.println(","+i+"]"+(N+1)+" "+phase+":"+miss + " " + avgmiss + " " + variance + " " + cov);
	}
	System.out.println("weighted standard deviation = "+totalweightedcov / (double)(phases.size()));
	//System.out.println("total misses = "+totalmiss);
	//System.out.println("total intervals = "+phases.size());
	//System.out.println("total phases = " + totalphases);
    }
 
    static int insert(long address, Vector addresses, Vector counts, Vector sizes, long size, long weight, Vector weights)
    {
	int low=0, mid, high = addresses.size() - 1;

	while (low <= high) {
	    mid = (low + high) / 2;
	    long val = ((Long)(addresses.elementAt(mid))).longValue();
	    if (address == val) {
		Integer count = (Integer)(counts.elementAt(mid));
		counts.setElementAt(new Integer(count.intValue()+1),mid);
		sizes.setElementAt(new Long(size), mid);
		long oldweight = ((Long)(weights.elementAt(mid))).longValue();
		if (oldweight < weight)
		    weights.setElementAt(new Long(weight), mid);
		return mid;
	    }
	    else if (address < val) {
		high = mid - 1;
	    }
	    else {
		low = mid + 1;
	    }
	}
	addresses.insertElementAt(new Long(address), low);
	counts.insertElementAt(new Integer(1), low);
	sizes.insertElementAt(new Long(size), low);
	weights.insertElementAt(new Long(weight), low);
	return low;
    }

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

    public static void output(Vector counts, Vector sizes, Vector weights)
    {
	System.out.print("T");
	for (int i = 0; i < counts.size(); i++) {
	    int count = ((Integer)(counts.elementAt(i))).intValue();
	    long size = ((Long)(sizes.elementAt(i))).longValue();
	    long weight = ((Long)(weights.elementAt(i))).longValue();
	    int nsize = (int)size;
	    int nweight = (int)weight;
	    //if (nweight != 1)
	    //nweight = 10;
	    if (count > 0) {
		//System.out.print(":"+(i+1)+":"+count*nsize*nweight+" ");
		System.out.print(":"+(i+1)+":"+count*nsize+" ");
	    }
	}
	System.out.println();
    }

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

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