Me@0: /*
seanhalle@31:  *  Copyright 2010 OpenSourceResearchInstitute.org
Me@0:  *  Licensed under GNU General Public License version 2
Me@0:  *
Me@0:  * Author: seanhalle@yahoo.com
Me@0:  *
Me@0:  */
Me@4: #include <stdio.h>
seanhalle@22: #include <string.h>
Me@0: #include "Histogram.h"
Me@0: 
Me@0: 
Me@0: /*This Histogram Abstract Data Type has a number of bins plus a range of
Me@0:  * values that the bins span, both chosen at creation.
Me@0:  *
Me@0:  *One creates a Histogram instance using the makeHistogram function, then
Me@0:  * updates it with the addToHist function, and prints it out with the
Me@0:  * printHist function.
Me@0:  *
Me@0:  *Note, the bin width is an integer, so the end of the range is adjusted
Me@0:  * accordingly.  Use the bin-width to calculate the bin boundaries.
Me@0:  */
Me@0: 
Me@0: 
Me@0: Histogram *
SeanHalle@5: makeHistogram( int32 numBins, int32 startOfRange, int32 endOfRange )
Me@0:  {
Me@0:    Histogram *hist;
SeanHalle@5:    int32 i;
Me@0: 
Me@0: 
seanhalle@29:    hist = PR_int__malloc( sizeof(Histogram) );
seanhalle@29:    hist->bins = PR_int__malloc( numBins * sizeof(int32) );
Me@0: 
Me@0:    hist->numBins      = numBins;
Me@0:    hist->binWidth     = (endOfRange - startOfRange) / numBins;
Me@0:    hist->endOfRange   = startOfRange + hist->binWidth * numBins;
Me@0:    hist->startOfRange = startOfRange;
Me@0: 
Me@0:    for( i = 0; i < hist->numBins; i++ )
Me@0:     {
Me@0:       hist->bins[ i ] = 0;
Me@0:     }
Me@0: 
Me@7:    hist->name = NULL;
Me@7:    return hist;
Me@7:  }
Me@7: 
Me@7: inline void
Me@7: makeHist_helper( Histogram *hist, int32 numBins,
Me@7:                  int32 startOfRange, int32 binWidth, char *nameCopy )
Me@7:  {
Me@7:    hist->numBins      = numBins;
Me@7:    hist->binWidth     = binWidth;
Me@7:    hist->endOfRange   = startOfRange + hist->binWidth * numBins;
Me@7:    hist->startOfRange = startOfRange;
Me@7:    hist->name         = nameCopy;
Me@7:    memset( hist->bins, 0, numBins * sizeof(int32) );
Me@7:  }
Me@7: 
Me@7: 
Me@7: Histogram *
Me@7: makeFixedBinHist( int32 numBins, int32 startOfRange, int32 binWidth,
Me@7:                   char *name )
Me@7: 
Me@7:  {
Me@7:    Histogram *hist;
Me@7: 
seanhalle@29:    hist = PR_int__malloc( sizeof(Histogram) );
seanhalle@29:    hist->bins = PR_int__malloc( numBins * sizeof(int32) );
Me@7: 
seanhalle@29:    char *nameCopy = (char *)PR_int__strDup(name);
seanhalle@22:    makeHist_helper( hist, numBins, startOfRange, binWidth, nameCopy);
Me@7: 
Me@7:    return hist;
Me@7:  }
Me@7: 
Me@7: Histogram *
Me@15: makeFixedBinHistExt( int32 numBins, int32 startOfRange, int32 binWidth,
Me@7:                      char *name )
Me@7: 
Me@7:  {
Me@7:    Histogram *hist;
Me@7: 
Me@7:    hist = malloc( sizeof(Histogram) );
Me@7:    hist->bins = malloc( numBins * sizeof(int32) );
Me@7: 
Me@7:    makeHist_helper( hist, numBins, startOfRange, binWidth, strdup(name));
Me@7: 
Me@0:    return hist;
Me@0:  }
Me@0: 
SeanHalle@5: void inline
SeanHalle@5: addToHist( int32 value, Histogram *hist )
Me@0:  {
SeanHalle@5:    int32 binIdx;
Me@0: 
Me@0:    if( value < hist->startOfRange )
Me@0:     { binIdx = 0;
Me@0:     }
Me@0:    else if( value > hist->endOfRange )
Me@0:     { binIdx = hist->numBins - 1;
Me@0:     }
Me@0:    else
Me@0:     {
Me@0:       binIdx = (value - hist->startOfRange) / hist->binWidth;
Me@0:     }
Me@0: 
Me@0:    hist->bins[ binIdx ] += 1;
Me@0:  }
Me@0: 
Me@8: void inline
Me@8: subFromHist( int32 value, Histogram *hist )
Me@8:  {
Me@8:    int32 binIdx;
Me@8: 
Me@8:    if( value < hist->startOfRange )
Me@8:     { binIdx = 0;
Me@8:     }
Me@8:    else if( value > hist->endOfRange )
Me@8:     { binIdx = hist->numBins - 1;
Me@8:     }
Me@8:    else
Me@8:     {
Me@8:       binIdx = (value - hist->startOfRange) / hist->binWidth;
Me@8:     }
Me@8: 
Me@8:    hist->bins[ binIdx ] -= 1;
Me@8:  }
Me@8: 
SeanHalle@5: 
Me@7: /*Inline because use with RDTSC in innermost code so need ultra-fast
Me@7:  */
SeanHalle@5: void inline
msach@10: addIntervalToHist( uint32 startIntvl, uint32 endIntvl, Histogram *hist )
SeanHalle@5:  {
SeanHalle@5:    int32 value;
SeanHalle@5: 
SeanHalle@5:    value = endIntvl - startIntvl;
SeanHalle@5:    if( value < 0 || value > 10000000 ) return; //sanity check
SeanHalle@5:    addToHist( value, hist );
SeanHalle@5:  }
SeanHalle@5: 
Me@8: void inline
Me@8: subIntervalFromHist( int32 startIntvl, int32 endIntvl, Histogram *hist )
Me@8:  {
Me@8:    int32 value;
Me@8: 
Me@8:    value = endIntvl - startIntvl;
Me@8:    if( value < 0 || value > 10000000 ) return; //sanity check
Me@8:    subFromHist( value, hist );
Me@8:  }
Me@8: 
Me@0: void
msach@10: saveHistToFile(Histogram *hist)
msach@10: {
msach@10:     FILE *output;
msach@10:     int32 binIdx, binStart, binEnd, centerValue, width;
msach@10:     int32 maxHeight, i,n;
msach@11:     float32 total, total2, expectedValue1, expectedValue2;
msach@10:     
msach@10:     if(hist == NULL || hist->name == NULL)
msach@10:         return;
msach@10:     
msach@10:     //Calculate the average
msach@10:     //do all except the top bin
msach@10:     maxHeight = 0; total = 0.0; expectedValue1 = 0.0;
msach@10:     for( i = 0; i < hist->numBins -1; i++ )
msach@10:     {
msach@10:       if( maxHeight < hist->bins[ i ] ) maxHeight = hist->bins[ i ];
msach@10:       total += hist->bins[ i ];
msach@10:       binStart = hist->startOfRange + hist->binWidth * i;
msach@10:       expectedValue1 += hist->bins[ i ] * (binStart + hist->binWidth/2.0);
msach@10:     }
msach@10:     //copy and calc expected value minus the top bin
msach@10:     expectedValue2  = expectedValue1;
msach@10:     expectedValue2 /= total;
msach@10:     total2          = total;
msach@10:     //now do last iteration, to add the top bin
msach@10:     if(maxHeight < hist->bins[ i ])
msach@10:                 maxHeight = hist->bins[ i ];
msach@10:    total += hist->bins[ i ];
msach@10:    binStart = hist->startOfRange + hist->binWidth * i;
msach@10:    expectedValue1 += hist->bins[ i ] * (binStart + hist->binWidth/2.0);
msach@10:    
msach@10:    expectedValue1 /= total;
msach@10:    
msach@10: 
msach@10:    
msach@10:     
msach@10:     //If a histogram directory does not exist, do not save to file.
msach@10:     //TODO change to argument
msach@10:     char filename[255];    
msach@10:     for(n=0;n<255;n++)
msach@10:     {
msach@10:         sprintf(filename, "./histograms/%s.%d.dat", hist->name,n);
msach@10:         output = fopen(filename,"r");
msach@10:         if(output)
msach@10:         {
msach@10:             fclose(output);
msach@10:         }else{
msach@10:             break;
msach@10:         }
msach@10:     }
msach@10:     printf("Saving Hist to File: %s ...\n", filename);
msach@10:     output = fopen(filename,"w+");
msach@10:     if(output == NULL){
msach@10:         printf("[!]No histogram was saved. To save histograms create folder 'histograms'.\n");
msach@10:         return;
msach@10:     }
msach@10: 
msach@10:     fprintf(output, "#\n# Histogram Name: %s\n", hist->name);
msach@10:     fprintf(output, "# Expected Values\n");
msach@10:     fprintf(output, "#\tnum samples: %d | expected value: %3.2f \n",
msach@10:                                                (int)total, expectedValue1 );
msach@10:     fprintf(output, "#\tminus top bin, num samples: %d | expected value: %3.2f \n",
msach@10:                                                (int)total2, expectedValue2 );
msach@10:     fprintf(output, "#\n# [Interval] [Center Value] [Count] [relative Count] [Width]\n");
msach@10:     
msach@10:     for( binIdx = 0; binIdx < hist->numBins; binIdx++ )
msach@10:     {
msach@10:       binStart = hist->startOfRange + hist->binWidth * binIdx;
msach@10:       binEnd = binStart + hist->binWidth - 1;
msach@10:       centerValue = (binStart+binEnd)/2;
msach@10:       width = (binEnd-binStart)+1;
msach@10:       fprintf(output, "%d-%d\t%d\t%d\t%.4f\t%d\n", binStart, binEnd, centerValue,
msach@10:                                              hist->bins[ binIdx ], 
msach@10:                                              hist->bins[ binIdx ]/total, width);
msach@10:     }
msach@10:     
msach@10:     fclose(output);
msach@10:     fflush(stdout);
msach@10: }
msach@10: 
msach@10: void
Me@0: printHist( Histogram *hist )
Me@0:  {
Me@7:    int32   binIdx, i, numBars, maxHeight, barValue, binStart, binEnd;
Me@8:    float32 total, total2, binPercent, expectedValue1, expectedValue2;
Me@0: 
Me@8:    if( hist == NULL ) return;
Me@8:    
Me@7:       //do all except the top bin
Me@7:    maxHeight = 0; total = 0.0; expectedValue1 = 0.0;
Me@7:    for( i = 0; i < hist->numBins -1; i++ )
Me@0:     {
Me@0:       if( maxHeight < hist->bins[ i ] ) maxHeight = hist->bins[ i ];
Me@7:       total += hist->bins[ i ];
Me@7:       binStart = hist->startOfRange + hist->binWidth * i;
Me@7:       expectedValue1 += hist->bins[ i ] * (binStart + hist->binWidth/2.0);
Me@0:     }
Me@7:       //copy and calc expected value minus the top bin
Me@8:    expectedValue2  = expectedValue1;
Me@7:    expectedValue2 /= total;
Me@8:    total2          = total;
Me@7:       //now do last iteration, to add the top bin
Me@7:    if( maxHeight < hist->bins[ i ] ) maxHeight = hist->bins[ i ];
Me@7:    total += hist->bins[ i ];
Me@7:    binStart = hist->startOfRange + hist->binWidth * i;
Me@7:    expectedValue1 += hist->bins[ i ] * (binStart + hist->binWidth/2.0);
Me@7:    
Me@7:    expectedValue1 /= total;
Me@7:    
Me@7:    printf( "histogram: " );
Me@7:    if( hist->name != NULL ) printf( "%s\n", hist->name );
Me@7:    else printf( "\n" );
Me@8:    printf( "               num samples: %d | expected value: %3.2f \n",
Me@8:                                                (int)total, expectedValue1 );
Me@8:    printf( "minus top bin, num samples: %d | expected value: %3.2f \n",
Me@8:                                                (int)total2, expectedValue2 );
Me@7: 
msach@10:    if(maxHeight < 60){
msach@10:        barValue = 1;
msach@10:        printf("Single Bar Value: %i\n", barValue);
msach@10:    }else{
msach@10:        barValue = maxHeight / 60;  //60 spaces across page for tallest bin
msach@10:        printf("Single Bar Value: %0.3f\n", (float)maxHeight /60);
msach@10:    }
msach@10:    
Me@8:    if( barValue == 0 ) { printf("error: bar val zero\n"); return; }
Me@0:    for( binIdx = 0; binIdx < hist->numBins; binIdx++ )
Me@0:     {
Me@0:       binStart = hist->startOfRange + hist->binWidth * binIdx;
Me@0:       binEnd = binStart + hist->binWidth - 1;
Me@7:       binPercent = 100 * hist->bins[ binIdx ] / total;
Me@7:       printf("bin range: %d - %d | %3.2f", binStart, binEnd, binPercent );
Me@0: 
Me@0:       numBars = hist->bins[ binIdx ] / barValue;
Me@0:          //print one bin, height of bar is num dashes across page
Me@0:       for( i = 0; i < numBars; i++ )
Me@0:        {
Me@0:          printf("-");
Me@0:        }
Me@0:       printf("\n");
Me@0:     }
Me@0:  }
Me@0: 
Me@3: void
Me@3: freeHist( Histogram *hist )
Me@3:  {
seanhalle@29:    PR_int__free( hist->bins );
seanhalle@29:    PR_int__free( hist->name );
seanhalle@29:    PR_int__free( hist );
Me@15:  }
Me@15: void
Me@15: freeHistExt( Histogram *hist )
Me@15:  {
Me@7:    free( hist->bins );
Me@7:    free( hist->name );
Me@7:    free( hist );
Me@7:  }