//
// Copyright (c) Microsoft Corporation.  All rights reserved.
//
//
// Use of this source code is subject to the terms of the Microsoft shared
// source or premium shared source license agreement under which you licensed
// this source code. If you did not accept the terms of the license agreement,
// you are not authorized to use this source code. For the terms of the license,
// please see the license agreement between you and Microsoft or, if applicable,
// see the SOURCE.RTF on your install media or the root of your tools installation.
// THE SOURCE CODE IS PROVIDED "AS IS", WITH NO WARRANTIES OR INDEMNITIES.
//
/*
 * cacheSizeCalculation.cpp
 */

/*
 * Main test code for caches.  The TESTPROCs call into here after
 * setting stuff up.
 */
#include "cacheSizeCalculation.h"
#include "..\..\..\..\common\commonUtils.h"
#include <windows.h>

/***************************************************************************
 *
 *                                Implementation
 *
 ***************************************************************************/

// see header for details
BOOL
runCacheSizeCalculation (
        DWORD *vals,
        DWORD dwMinArray,
        DWORD dwMaxArray,
        DWORD dwMinStride,
        DWORD dwMaxStride,
        DWORD dwCacheSizeJumpRate,
        DWORD dwCacheLineJumpRate,
        CACHE_ACCESS_INFO *pAccessRawData,        
        ULONGLONG ullIterations)
  { 
    BOOL returnVal = TRUE;
    ULONGLONG ullIter, ullRunningTime;
    DWORD dwDummy, index;    
    DWORD dwArrayOffset  = 0;
    DWORD dwStrideOffset = 0;  
    
    DWORD dwSteps, dwArrayEnum;
    numberOfEnum(dwMinStride, dwMaxStride, &dwSteps);
    numberOfEnum(dwMinArray, dwMaxArray, &dwArrayEnum);

    /*
     * Walk through different arrays with different strides
     */      
    for (DWORD dwPt = 0; dwPt < MAX_RUNNING_LOOP; dwPt++)
      {        
        Info (_T("Running loop %u of %u..."), (dwPt + 1), MAX_RUNNING_LOOP);
        ullIter = ullIterations; // reset

        DWORD dwArrayOffset = 0;

        for (DWORD dwArray = dwMinArray; dwArray <= dwMaxArray; dwArray *= 2)
          {            
            DWORD dwStrideOffset = 0;
            for (DWORD dwStride = dwMinStride; dwStride <= dwMaxStride; dwStride *= 2)
              { 
                cacheInit(vals, dwArray, dwStride, &dwDummy);

                returnVal = runCacheAccess (
                                      vals,
                                      dwArray,
                                      dwStride,
                                      ullIter,
                                      &ullRunningTime,
                                      &dwDummy);

                if (returnVal == TRUE)
                  { 
                    /*
                     * for each test running, the results are organized 
                     * consecutively, so this index is to locate the 
                     * correct position
                     */
                    index = dwPt + dwArrayOffset + dwStrideOffset;

                    pAccessRawData[index].dwPt     = dwPt;
                    pAccessRawData[index].dwArray  = dwArray;
                    pAccessRawData[index].dwStride = dwStride;
                    pAccessRawData[index].ullTime  = ullRunningTime;
                    pAccessRawData[index].dwPnt    = ullIter * dwArray;
                    Sleep(500);
                  }
                else 
                  {
                    Error (_T("Cache test failed"));
                    Info (_T(""));
                    goto cleanAndReturn;
                  }                
                
                dwStrideOffset += MAX_RUNNING_LOOP;
              } 

                 
            /*
             * The calculated duration is used to normalize the total access point
             */
            ullIter /= 2;

            dwArrayOffset += dwSteps * MAX_RUNNING_LOOP;            
          } 
      }
  
    Info (_T(""));

    Info (_T("Cache access raw data by loop#, stride# and array size ..."));
    Info (_T("(*** The real cache accesses are NOT in such orders! ***)")); 
    Info (_T("---------------------------"));
    printCacheCal(&pAccessRawData, dwSteps * dwArrayEnum * MAX_RUNNING_LOOP);
    Info (_T("---------------------------"));
    Info (_T(""));
    Sleep(1000);

    // to get the median data, and figure out the cache size/block size
    returnVal = analyzeData(
                      &pAccessRawData, 
                      dwMinStride, 
                      dwMaxStride, 
                      dwArrayEnum,
                      dwCacheSizeJumpRate,
                      dwCacheLineJumpRate);

    Sleep(4000); // wait a while for the output

cleanAndReturn:
    return returnVal;
  }


// see header for the details
VOID
cacheInit(DWORD *vals, DWORD dwSize, DWORD dwStride, DWORD *dwDummy) {
    DWORD dwPos;
    DWORD dwJunk = 0;

    for (dwPos = 0; dwPos < dwSize; dwPos++)
      {
        dwJunk += vals[dwPos];
      }

    for (DWORD dwLoop = 0; dwLoop < 2; dwLoop++) {
      for (dwPos = 0; dwPos < dwSize; dwPos += dwStride)
        {
          dwJunk += vals[dwPos];
        }
      }

    *dwDummy = dwJunk; // cheat the optimizer
  }

/******************************************************************************
 * The core function to access the cache by reading the data from array       *
 *                                                                            *
 * See header for more information about this function.                       *
 ******************************************************************************
 */
BOOL
runCacheAccess(
            DWORD *vals, 
            DWORD dwArray,
            DWORD dwStride,
            ULONGLONG ullIterations,
            ULONGLONG *pRunTime,
            DWORD *dwDummyValue)
{
  DWORD dwPos, dwSample, dwJunk = 0;
  ULONGLONG ullTimeBegin, ullTimeEnd, runningTime;

  ullTimeBegin = (ULONGLONG)GetTickCount();
  for (ULONGLONG ullIter = 0; ullIter < ullIterations; ullIter++)
    {
      for (dwSample = 0; dwSample < dwStride; dwSample++)
        {
          for (dwPos = 0; dwPos < dwArray; dwPos += dwStride)
          {
            dwJunk += vals[dwPos];  /* cache access*/
          }
        }
    }

  ullTimeEnd = (ULONGLONG)GetTickCount();

  /* subtract, accounting for overflow */
  if (AminusB(runningTime, ullTimeEnd, ullTimeBegin, MAX_DWORD) == FALSE)
    {
      // This should never happen.
      IntErr (_T("AminusB failed in runCacheTest"));
      return FALSE;
    }
  
  *pRunTime = runningTime;
  *dwDummyValue = dwJunk;

  return (TRUE);     
}

// see header for the details
BOOL
analyzeData(
       CACHE_ACCESS_INFO **pAccessRawData, 
       DWORD dwMinStride, 
       DWORD dwMaxStride,        
       DWORD dwArrayEnum,
       DWORD dwCacheSizeJumpRate,
       DWORD dwCacheLineJumpRate)
  {
    BOOL returnVal = TRUE;
    DWORD dwJumpPos, dwCacheSize, dwBlockSize;
    DOUBLE doDeviation;

    DWORD dwSteps;
    numberOfEnum(dwMinStride, dwMaxStride, &dwSteps);

    /*
     * for marking the jump position purpose
     *
     * Note: 
     *  There exist four kinds of status which are used for marking the jump, i.e.
     *        - SUCCESSFUL    : jump found
     *        - FAILED        : jump having found is not correct
     *        - NOT_CALCULTED : jump calculation is skipped
     *        - NONE          : initialized
     *  
     *  For all the jump positions relative to different stride#, only those
     *  whose jump status are one of the FIRST THREE will be marked
     */
    WORD *pwJumpStatus = new WORD[dwSteps];
    for (WORD i = 0; i < dwSteps; i++)
      {
        pwJumpStatus[i] = NONE;
      }

    DWORD dwSearchJumpLimit = JUMP_SEARCH_LIMIT / sizeof(DWORD);
    if (dwSearchJumpLimit > dwMaxStride)
      {
        dwSearchJumpLimit = dwMaxStride;
      }

    /*
     * To keep MAX_RUNNING_LOOP number of specific array/stride access info. Then,
     * retrieve the median values from it and store in pMedianValues as below
     *
     */
    CACHE_ACCESS_INFO *pInfo = 
          (CACHE_ACCESS_INFO *)VirtualAlloc(
                      NULL, 
                      sizeof(CACHE_ACCESS_INFO) * MAX_RUNNING_LOOP,
                      MEM_COMMIT, 
                      PAGE_READWRITE);

    if (pInfo == NULL)
      {
        Info (_T("memory allocation error!"));
        return FALSE;
      }

    /*
     * save all the median point values of accessing arrays with different strides
     */
    CACHE_ACCESS_INFO *pMedianValues = 
          (CACHE_ACCESS_INFO *)VirtualAlloc(
                      NULL, 
                      sizeof(CACHE_ACCESS_INFO) * dwSteps * dwArrayEnum,
                      MEM_COMMIT, 
                      PAGE_READWRITE);

    if (pMedianValues == NULL)
      {
        Info (_T("memory allocation error!"));
        return FALSE;
      }

    DWORD newIndex = 0;
    DWORD dwCounter = dwSteps * dwArrayEnum * MAX_RUNNING_LOOP;
    for (DWORD index = 0; index < dwCounter; index+= MAX_RUNNING_LOOP)
      {
        for(DWORD inner = 0; inner < MAX_RUNNING_LOOP; inner++)
          {
            // we just need two params for sorting purposes
            pInfo[inner].ullTime = (*pAccessRawData)[index + inner].ullTime;
            pInfo[inner].dwPt = (*pAccessRawData)[index + inner].dwPt;
          }
        
        // bubble sorting
        sortData(&pInfo);
        
        // retrieve the mean values
        getMedianValue(pMedianValues, newIndex, pInfo);

        // we just simply retrieve one even though the sample is even#
        pMedianValues[newIndex].dwPt = pInfo[MAX_RUNNING_LOOP/2].dwPt;

        // we need other values, too
        pMedianValues[newIndex].dwArray = (*pAccessRawData)[index].dwArray;
        pMedianValues[newIndex].dwStride = (*pAccessRawData)[index].dwStride;
        pMedianValues[newIndex].dwPnt = (*pAccessRawData)[index].dwPnt;  
        newIndex++;
      }

    Info (_T(""));
    Info (_T("Data processing..."));
    Info (_T("As for each size of array's specific stride cache accessess, pick up"));
    Info (_T("the median data point from %u samples"), MAX_RUNNING_LOOP);
    Info (_T(""));
    Info (_T("We use these median data as the source to calculate the cache sizes"));
    Info (_T("and cache line sizes"));
 
    Info (_T(""));
    Info (_T("Cache access median data output..."));
    Info (_T("----------------------------------------------------------------"));
    printCacheCal(&pMedianValues, dwSteps * dwArrayEnum);
    Info (_T("----------------------------------------------------------------"));   
    Sleep(1000);

    Info (_T(""));
    Info (_T("Summary of the cache access time:(unit: ms)"));
    Info (_T("----------------------------------------------------------------"));
    /* 
     * format print out the cache access data, array sizes as the rows, and
     * the stride sizes as the column
     */
    printCacheCalByRow(
          &pMedianValues, 
          0, 
          0, 
          dwSteps * dwArrayEnum, 
          dwSteps, 
          NULL);
    Info (_T("----------------------------------------------------------------"));

    // analyze the data to figure out the size of the cache
    Info (_T(""));
    Info (_T("Calculating the cache size(s) ..."));
    Info (_T(""));
    returnVal = calculateCacheSize(
                          &pMedianValues, 
                          dwMinStride, 
                          dwMaxStride, 
                          dwArrayEnum,
                          dwCacheSizeJumpRate,
                          &dwJumpPos,
                          &dwCacheSize,
                          pwJumpStatus);


    Sleep(1000);

    if (returnVal == FALSE)
      {
        Info (_T("**** Failed to calculate the cache size! ****"));
        return returnVal;
      }


    Info (_T(""));
    Info (_T("-----------------------------------------------------")); 
    Info (_T("Summary of the cache access time:(unit: ms)"));
    Info (_T("==========================================="));
    Info (_T("(Note: S - Successful, F - Failed)"));
    Info (_T("-----------------------------------------------------"));  

    /* 
     * print out the cache calculation result with jump marked
     */
    printCacheCalByRow(
                &pMedianValues, 
                0, 
                dwJumpPos, 
                dwSteps * dwArrayEnum, 
                dwSteps,
                pwJumpStatus);

    doDeviation = getStandardDeviation(&pMedianValues, 0, dwJumpPos * dwSteps);

    DOUBLE *doDeviations = (DOUBLE *)malloc(dwSteps * sizeof(DOUBLE));
    if (doDeviations == NULL)
      {
        Error (_T(""));
        Error (_T("memory allocation error"));
        Error (_T(""));
        returnVal = FALSE;
        goto cleanAndExit;
      }

    if (calculateDeviationsByStride(
                &pMedianValues, 
                dwArrayEnum, 
                dwSteps, 
                dwJumpPos, 
                doDeviations) == FALSE)
      {
        returnVal = FALSE;
        goto cleanAndExit;
      }
    
    Info (_T("----------------------------------------------------------------"));
    Info (_T("Standard deviations by strides: (unit: ms)"));
    Info (_T("Array ==> [%uKB ~ %uKB]"),
              pMedianValues[0].dwArray * sizeof (DWORD) / 1024,
              pMedianValues[(dwJumpPos - 1) * dwSteps].dwArray * sizeof(DWORD) / 1024);
    printDeviationByStride(doDeviations, dwSteps);
    Info (_T("----------------------------------------------------------------"));
    Info (_T(""));
    Info (_T("----------------------------------------------------------------"));

    Info (_T("Standard Deviation (unit: ms): *** %.2f ***"), doDeviation);
    Info (_T("Stride ==> [%ubytes ~ %ubytes]"),
              dwMinStride * sizeof(DWORD),
              dwSearchJumpLimit * sizeof(DWORD));

    Info (_T("Array ==> [%uKB ~ %uKB])"),
              pMedianValues[0].dwArray * sizeof (DWORD) / 1024,
              pMedianValues[(dwJumpPos - 1) * dwSteps].dwArray * sizeof(DWORD) / 1024);
    Info (_T("----------------------------------------------------------------"));
    Info (_T(""));
    Info (_T("NOTE:"));
    Info (_T("The standard deviation measures how spread out the cache access"));
    Info (_T("MISS times are. If MISS time points are all close to the mean,"));
    Info (_T("then the standard deviation is close to zero; otherwise, it is"));
    Info (_T("far from zero"));
    Info (_T(""));
    Info (_T("The standard deviation is measured in the same units as the MISS"));
    Info (_T("time values of the population"));
    Info (_T("----------------------------------------------------------------"));
    Info (_T(""));    

    Info (_T("Calculating the line size(s) ..."));

    // analyze the data to figure out the size of the cache line
    returnVal = calculateBlockSize(
                      &pMedianValues, 
                      dwSteps,
                      dwArrayEnum, 
                      dwCacheSize, 
                      dwMinStride,
                      dwMaxStride,
                      dwCacheLineJumpRate,
                      &dwBlockSize);  

    Sleep(2000);

    Info (_T(""));
    Info (_T("Calculation Report:"));
    Info (_T("----------------------------------------------------------------"));
    Info (_T("**** Cache Size: %uKB ****"), dwCacheSize * 4 / 1024);
    if (returnVal == TRUE)
        Info (_T("**** Block Size: %ubytes ****"), dwBlockSize);
    else
        Info (_T("**** Failed to analyze the block size! ****"));

    Info (_T("----------------------------------------------------------------"));
    Info (_T(""));


cleanAndExit:
    if (VirtualFree (pInfo, 0, MEM_RELEASE) == 0)
      {
        Error (_T("Could not free memory. GetLastError: %u."), GetLastError);
        returnVal = FALSE;
      }

    if (VirtualFree (pMedianValues, 0, MEM_RELEASE) == 0)
      {
        Error (_T("Could not free memory. GetLastError: %u."), GetLastError);
        returnVal = FALSE;
      }

    return returnVal;
  }

// see the header for the details
BOOL
calculateCacheSize(
          CACHE_ACCESS_INFO **pMedianValues, 
          DWORD dwMinStride,
          DWORD dwMaxStride,
          DWORD dwArrayEnum,
          DWORD dwCacheSizeJumpRate,
          DWORD *pdwJumpPos,
          DWORD *pdwCacheSize,
          WORD  *pwJumpStatus)
  {    
    DWORD dwJumpPos, dwPrevSize = 0, dwSize = 0;
    BOOL bFound = FALSE;
    DOUBLE doJumpRate;

    DWORD dwSteps;
    numberOfEnum(dwMinStride, dwMaxStride, &dwSteps);

    DWORD dwBlock = dwSteps * dwArrayEnum;

    /*
     * Search each jump for every stride. And then compare all the jumps, if 
     * they are different, then show the warning and print out the data
     */
    Info (_T("---------------------------------------------------------------"));
    Info (_T("\tSearching jump from stride: %u DWORDs, i.e. %ubytes"), 
              dwMinStride,
              dwMinStride * sizeof(DWORD));
    if (isCacheJump(
              pMedianValues, 
              0, 
              dwSteps, 
              dwBlock,
              dwCacheSizeJumpRate,
              &dwJumpPos, 
              &dwPrevSize, 
              &doJumpRate) == TRUE)
      {
        pwJumpStatus[0] = SUCCESSFUL;
        bFound = TRUE;
        Info (_T("\t\t==>Jump of %.0f%% found, this is above %u%% threshold!!!"), 
                      doJumpRate,
                      dwCacheSizeJumpRate);
        Info (_T(""));
      }

    DWORD dwStart = 0;
    DWORD dwLimit = JUMP_SEARCH_LIMIT / sizeof (DWORD);
    dwLimit = (dwLimit < dwMaxStride) ? dwLimit : dwMaxStride;

    /*
     * walk through the remaining stride(s) up to the search limit to verify
     * the jump
     */
    for (DWORD dwStride = 2 * dwMinStride; dwStride <= dwLimit; dwStride *= 2)
      { 
        Info (_T("\tSearching jump from stride: %u DWORDs, i.e. %ubytes"),
                  dwStride,
                  dwStride * sizeof(DWORD));

        dwStart++;              
        if (isCacheJump(
                pMedianValues,
                dwStart, 
                dwSteps, 
                dwBlock, 
                dwCacheSizeJumpRate,
                &dwJumpPos, 
                &dwSize,
                &doJumpRate) == TRUE)
          {
            Info (_T("\t\t==>Jump of %.0f%% found, this is above %u%% threshold!!!"), 
                      doJumpRate,
                      dwCacheSizeJumpRate);
            Info (_T(""));

            if (dwPrevSize != dwSize)
              {
                if (pwJumpStatus[dwStart - 1] == SUCCESSFUL)
                  {
                    pwJumpStatus[dwStart] = FAILED;
                    Info (_T(""));
                    Info (_T("\tWarning!!! The jumps are not the same"));
                    Info (_T(""));
                    bFound = FALSE;
                  }
                break;
              }
            else if (dwPrevSize != 0)
              {
                pwJumpStatus[dwStart] = SUCCESSFUL;
                bFound = TRUE;
              }

            dwPrevSize = dwSize;
          }

      }

      *pdwJumpPos = dwJumpPos;
      *pdwCacheSize = dwSize;

      // skip the remaining stride(s), mark them as "NOT_CALCULATED"
      for(DWORD dwExtra = dwLimit * 2;  dwExtra <= dwMaxStride; dwExtra *= 2)
        { 
          dwStart++;
          pwJumpStatus[dwStart] = NOT_CALCULATED;
        }

      return bFound;
  }

// see header for the details
BOOL
isCacheJump(
        CACHE_ACCESS_INFO **pMedianValues,
        DWORD  dwStart,
        DWORD  dwSteps,
        DWORD  dwBlock,
        DWORD  dwCacheSizeJumpRate,
        DWORD  *pdwJumpPos,
        DWORD  *pdwCacheSize,
        DOUBLE *pdoJumpRate)
  {
    DOUBLE doCurTime, doPrevTime;
    DWORD dwCacheSize, dwArray, dwJumpPos;

    DOUBLE doJumpFactor = 1.0 + dwCacheSizeJumpRate / 100.0;

    if ((*pMedianValues)[dwStart].ullTime == 0)
      {
        Error (_T("Cache access duration is ZERO"));
        return FALSE;
      }

    // get the start point info
    dwArray = (*pMedianValues)[dwStart].dwArray;
    dwCacheSize = (*pMedianValues)[dwStart].dwArray;
    doPrevTime = (DOUBLE)(*pMedianValues)[dwStart].ullTime;

    dwJumpPos = 0;

    Info (_T("\t\tArray Size: %u KB\t==> access time: %.0f"), 
              dwArray * sizeof(DWORD) / 1024,
              doPrevTime);


    // search the next points and compare the access time for the possible jump
    for(DWORD dwIndex = dwStart + dwSteps; dwIndex < dwBlock; dwIndex += dwSteps)
      {
        if ((*pMedianValues)[dwIndex].ullTime == 0)
          {
            Error (_T("Cache access duration is ZERO"));
            return FALSE;
          }

        dwArray = (*pMedianValues)[dwIndex].dwArray;
        doCurTime = (DOUBLE)(*pMedianValues)[dwIndex].ullTime;
        dwJumpPos++;
        
        Info (_T("\t\tArray Size: %u KB\t==> access time: %.0f"), 
                  dwArray * sizeof(DWORD) / 1024,
                  doCurTime);

        if (doCurTime > doJumpFactor * doPrevTime)
          {
            *pdwCacheSize = dwCacheSize;
            *pdwJumpPos = dwJumpPos;
            *pdoJumpRate = (doCurTime - doPrevTime) / doPrevTime * 100;
            Info (_T(""));
            return TRUE;
          }

        doPrevTime = doCurTime;
        dwCacheSize = (*pMedianValues)[dwIndex].dwArray;
      }

    Info (_T("\t\t*** No %u percent cache jump found ***"), dwCacheSizeJumpRate);
    Info (_T(""));
    return FALSE;
  }

// see the header for the details
BOOL
calculateBlockSize(
            CACHE_ACCESS_INFO **pMedianValues, 
            DWORD dwSteps,
            DWORD dwArrays,
            DWORD dwCacheSize,
            DWORD dwMinStride,
            DWORD dwMaxStride,
            DWORD dwCacheLineJumpRate,
            DWORD *pdwBlockSize)
  {
    BOOL bFound = FALSE;
    DOUBLE doHitTime;
    DWORD dwCacheLine, dwArrayIndex, dwStartPoint = 0;   

    DWORD dwCounter = dwSteps * dwArrays;

    // allocate the maximum memory space to store the calculations
    DOUBLE *doMissTime = (DOUBLE *)malloc(dwSteps * dwArrays * sizeof(DOUBLE));

    if (doMissTime == NULL)
      {
        Error (_T(""));
        Error (_T("Cannot allocate the memory for storing cache MISS times"));
        Error (_T(""));
        return FALSE;
      }

    /* 
     * search the array that jump occurs. we calculate the cache 
     * access MISS/HIT based on this array's access data
     */
    for (; dwStartPoint < dwCounter; dwStartPoint++)
      {
        if ((*pMedianValues)[dwStartPoint].dwArray > dwCacheSize)
          {
            break;
          }
      }

    if (dwStartPoint == 0 || dwStartPoint == dwCounter)
      {
        Error (_T(""));
        Error (_T("Cannot figure out the block size"));
        Error (_T(""));
        return FALSE;
      }

    if (dwStartPoint < dwSteps)
      {
        Error (_T(""));
        Error (_T("Invalid cache size!!!"));
        Error (_T(""));
        return FALSE;
      }   

    doHitTime = (DOUBLE)(*pMedianValues)[dwStartPoint - dwSteps].ullTime;

    Info (_T("\tHitTime ==> %.0f ms"), doHitTime);

    DOUBLE doJumpRate;

    Info (_T(""));

    DWORD dwCacheLineJumpPos = 0;
    DWORD dwMissTimeCounter = 0;
    DWORD dwStart, dwEnd;
    DWORD dwSize;

    /*
     * start the size of the cache line from 2 DWORDs, i.e. 8 bytes
     */
    for (dwCacheLine = dwMinStride; dwCacheLine <= dwMaxStride; dwCacheLine *= 2)
      {
        Info (_T("\t--------------------------------------------------"));
        Info (_T("\tSupposed that the cache line size is: %ubytes, ..."), 
                  dwCacheLine * sizeof(DWORD));

        DWORD dwMaxStrideEnum;
        numberOfEnum(1, dwCacheLine, &dwMaxStrideEnum);        
        
        //dwArrayIndex = dwStartPoint + dwMaxStrideEnum - 1;
        /*
         * calculate the index, just case the calculation overflow. This is supposed
         * to happen!!!
         */
        if (CeDWordAdd3(dwStartPoint, dwMaxStrideEnum - 1, 0, &dwArrayIndex) != S_OK)
          {
            Error (_T("Data overflow during index calculation"));
            bFound = FALSE;
            goto checkAndExit;
          }
        
        if (dwArrayIndex >= dwCounter)
          {
            Error (_T("Index out of boundary"));
            bFound = FALSE;
            goto checkAndExit;
          }        

        dwArrayIndex = dwStartPoint;           

        // counter the element for the following loop
        numberOfEnum(dwMinStride, dwCacheLine, &dwSize);

        dwStart = dwMissTimeCounter;
        dwEnd = dwStart + dwSize - 1;

        /* 
         * based on this pretended cache line size, we then calculate the
         * cache MISS time for different stride#
         */
        for (DWORD dwStride = dwMinStride; dwStride <= dwCacheLine; dwStride *= 2)
          {
            Info (_T("\t\tCalculate the cache miss time for stride: %ubytes ..."),
                      dwStride * sizeof(DWORD));

            Info (_T("\t\t\t%u/%u * MISS + (1 - %u/%u) * HIT = %I64u ms"),
                      dwStride, 
                      dwCacheLine,
                      dwStride,
                      dwCacheLine,
                      (*pMedianValues)[dwArrayIndex].ullTime);

            /*
             * The formula to calcuate the MISS time:
             *
             * ACCESS_TIME[dwStride] 
             *   = (dwStride / dwCacheLine) * MISS + (1 - dwStride / dwCacheLine) * HIT
             *
             * ==> MISS = [dwCacheLine*ACCESS - (dwCacheLine/dwStride - 1)*HITT]/dwStride
             */
            DOUBLE doCurMissTime  = (DOUBLE)dwCacheLine;
            doCurMissTime *= (DOUBLE)(*pMedianValues)[dwArrayIndex].ullTime;
            doCurMissTime -= (dwCacheLine - dwStride) * doHitTime;
            doMissTime[dwMissTimeCounter] = doCurMissTime / dwStride;

            Info (_T("\t\t\t*** HIT time: %.0f ms"),doHitTime);
            Info (_T("\t\t\t==> MISS time: %.0f ms"), doMissTime[dwMissTimeCounter]);
            Info (_T(""));

            dwMissTimeCounter++;
            dwArrayIndex++;
          }        

        if (isBlockJump(
                   doMissTime, 
                   dwStart, 
                   dwEnd,
                   dwCacheLineJumpRate, 
                   &doJumpRate) == TRUE)
          {            
            // need to mark the jump point
            dwCacheLineJumpPos = dwCacheLine;

            //printBlockCalByRow(dwCacheLine, doMissTime, dwMissTimeCounter, TRUE);
            //Info (_T("----------------------------------------------------------------"));         
            Info (_T("*** Jump of %.0f%% found, this is above %u%% threshold! ***"), 
                      doJumpRate, 
                      dwCacheLineJumpRate);
            
            // the previous stride# is the cache line size
            dwCacheLine = dwCacheLine * sizeof(DWORD) / 2;
            bFound = TRUE;
            goto output;
          }
        //else 
        //  {
        //    // don't need to mark the jump point
        //    printBlockCalByRow(dwCacheLine, doMissTime, dwMissTimeCounter, FALSE);
        //  }
        //Info (_T("----------------------------------------------------------------"));
        //Info (_T(""));
      }

output:
    dwStart = 0;
    Info (_T(""));
    Info (_T("Summary of cache access MISS time(ms) per stride"));
    Info (_T("----------------------------------------------------------------"));

    for (DWORD dwOut = dwMinStride; dwOut <= dwMaxStride; dwOut *= 2)
      {
        DWORD dwSize;
        numberOfEnum(dwMinStride, dwOut, &dwSize);

        if (dwCacheLineJumpPos > 0 && dwCacheLineJumpPos == dwOut)
          {
            printBlockCalByRow(dwOut, doMissTime, dwStart, dwStart + dwSize - 1, TRUE);
            break;
          }
        else
          {
            printBlockCalByRow(dwOut, doMissTime, dwStart, dwStart + dwSize - 1, FALSE);
          }
        dwStart += dwSize;
      }
    Info (_T("----------------------------------------------------------------"));
    Info (_T(""));

checkAndExit:
    if (bFound == FALSE)
      {
        Info (_T("\t\t*** No %u percent block jump found ***"), dwCacheLineJumpRate);
        Info (_T(""));
        return FALSE;
      }
    else 
      {
        *pdwBlockSize = dwCacheLine;
      }

    return TRUE;
  }

// see the header for the details
BOOL
isBlockJump(
       DOUBLE *doMissTime, 
       DWORD dwStart,
       DWORD dwEnd,
       DWORD dwCacheLineJumpRate, 
       DOUBLE *pdoJumpRate)
  {
    if ((dwEnd - dwStart) > 1)
      {
        DOUBLE doMin = getMin(doMissTime, dwStart, dwEnd);
        DOUBLE doMax = getMax(doMissTime, dwStart, dwEnd);
        
        if (doMin < 1.0e-3)
          {
            Error (_T("Maximum miss time is too small"));
            return FALSE;
          }    
        
        *pdoJumpRate = (doMax - doMin)/doMin * 100.0;
        
        if (*pdoJumpRate > (DOUBLE)dwCacheLineJumpRate) 
          {        
            return TRUE;
          }
      }

    return FALSE;
  }

// see the header for the details
DOUBLE
getStandardDeviation(CACHE_ACCESS_INFO **pMedianValues, DWORD dwStart, DWORD dwEnd) 
  {
    DWORD dwCounter, dwSize;
    DOUBLE doResult;

    doResult = 0.0;
    
    dwCounter = 0;
    dwSize = dwEnd - dwStart;

    DOUBLE *doSamples = (DOUBLE *)malloc (dwSize * sizeof (DOUBLE));

    if (NULL != doSamples) {
      for(DWORD dwIndex = dwStart; dwIndex < dwEnd; dwIndex++)
        {
          doSamples[dwCounter++] = (DOUBLE)(*pMedianValues)[dwIndex].ullTime;
        } 

      doResult = getStandardDeviation(doSamples, dwSize);
      free (doSamples);
    }

    return doResult;
  }

// see the header for the details
DOUBLE
getStandardDeviation(DOUBLE *doSamples, DWORD dwSize) 
  {
    if (dwSize <= 1)
      {
        return 0.0;
      }

    DOUBLE doSquare = 0;
    DOUBLE doSum = 0;

    for(DWORD dwIndex = 0; dwIndex < dwSize; dwIndex++)
      {
        DOUBLE doTime = doSamples[dwIndex];
        doSquare += doTime * doTime;
        doSum += doTime;
      }    

    return sqrt((doSquare - doSum * doSum / (DOUBLE)dwSize) / (DOUBLE)(dwSize - 1));
  }

    
VOID
printCacheCal(CACHE_ACCESS_INFO **pAccessRawData, DWORD dwCounter)
  {
    Info (_T("Stride unit:   DWORD(s)"));
    Info (_T("Duration unit: millisecond(s)"));
    Info (_T("----------------------------------------------------------------"));
    for(DWORD k = 0; k < dwCounter; k++)
      {
        Info (_T("pt = %u\tsize = %uKB\t\t\t\tstride = %u\t\t\tduration = %I64u"), 
                (*pAccessRawData)[k].dwPt,
                (*pAccessRawData)[k].dwArray * 4/1024,
                (*pAccessRawData)[k].dwStride,
                (*pAccessRawData)[k].ullTime);
      }
  }

// see the header for details
BOOL
numberOfEnum(DWORD dwMinSize, DWORD dwMaxSize, DWORD* dwEnum)
  {
    DWORD dwNum = 0;

    if (dwMinSize > 0 && dwMaxSize > 0)
      {
        while (dwMinSize <= dwMaxSize)
          {
            dwNum++;
            dwMinSize *= 2;
          }
        
        *dwEnum = dwNum;
        
        if (dwNum > 0) 
          {        
            return TRUE;
          }
      }

    return FALSE;
  }

// see the header for the details
VOID
printCacheCalByRow(
         CACHE_ACCESS_INFO **pInfo, 
         DWORD dwStart, 
         DWORD dwJump, 
         DWORD dwEnd, 
         DWORD dwSteps, 
         WORD *pwJumpStatus)
  {
    TCHAR tcTitle[BUFFER_SIZE];
    TCHAR tcInfo[BUFFER_SIZE];
    TCHAR tcTmp[BUFFER_SIZE];

    DWORD dwRows = (dwEnd - dwStart) / dwSteps;

    _tcscpy_s(tcTitle, BUFFER_SIZE, _T("Array Size"));

    for (DWORD i = 0; i < dwSteps; i++)
      {
        concatString(tcTitle, _T("Stride"), 10);
      }

    Info (tcTitle); // print the title 1

    copyString(tcTitle, _T("------"), 10);

    for (DWORD i = 0; i < dwSteps; i++)
        concatString(tcTitle, _T("-bytes-"), 10);
    
    Info (tcTitle); // print the title 2

    copyString(tcTitle, _T("###"), 10);
    for (DWORD i = 0; i < dwSteps; i++)
      {
        _stprintf(tcInfo, _T("%u"), 
                  (*pInfo)[dwStart + i].dwStride * sizeof(DWORD));
         concatString(tcTitle, tcInfo, 10);
      }       
    Info (tcTitle); // print the stride numbers
    Info (_T(""));

    /*
     * print array size, and the access time corresponding to each stride
     */
    for (DWORD i = 0; i < dwRows; i++) 
      {
        _stprintf(tcTmp, _T("%uKB"), 
                  (*pInfo)[dwStart + i * dwSteps].dwArray * 4 / 1024);
        copyString(tcInfo, tcTmp, 10);

        for (DWORD j = 0; j < dwSteps; j++)
          {
            ULONGLONG ullTime = (*pInfo)[dwStart + i * dwSteps + j].ullTime;

            if (pwJumpStatus != NULL && i == dwJump) // mark the jump point(s)
              { 
                switch(pwJumpStatus[j])
                  {
                    case SUCCESSFUL:
                      _stprintf(tcTmp, _T("(S)%I64u"), ullTime);
                      break;

                    case FAILED:
                      _stprintf(tcTmp, _T("(F)%I64u"), ullTime);
                      break;

                    default:
                      _stprintf(tcTmp, _T("%I64u"),    ullTime);
                      break;
                  }
              }
            else // normal output
              {
                _stprintf(tcTmp, _T("%I64u"), ullTime);
              }
            concatString(tcInfo, tcTmp, 10);
          }

        Info (tcInfo);
      }    
  }

// see the header for the details
BOOL
calculateDeviationsByStride(
         CACHE_ACCESS_INFO **pInfo, 
         DWORD dwNumberOfArray, 
         DWORD dwNumberOfStride, 
         DWORD dwJumpPosOfArray,
         DOUBLE *doDeviations)
  {
    DWORD dwDevs = 0;

    DOUBLE *doAccessTime = (DOUBLE *)malloc(dwJumpPosOfArray * sizeof(DOUBLE));
    if (doAccessTime == NULL)
      {
        Error (_T(""));
        Error (_T("memory allocation error for cache info print"));
        Error (_T(""));
        return FALSE;
      }

    /*
     * For each stride#, search the access time for different array size up to the 
     * cache size, then its calculate the standard deviation and saved for 
     * output
     */
    for (DWORD dwCol = 0; dwCol < dwNumberOfStride; dwCol++)
      {
        DWORD dwCounter = 0;
        for (DWORD dwRow = 0; dwRow < dwJumpPosOfArray; dwRow++)
          {
            ULONGLONG ullTime = (*pInfo)[dwCol + dwRow * dwNumberOfStride].ullTime;
            doAccessTime[dwCounter++] = (DOUBLE)ullTime;
          }
        doDeviations[dwDevs++] = getStandardDeviation(doAccessTime, dwCounter);
      }

    free(doAccessTime);

    return TRUE;
  }

// see the header for the details
VOID
printDeviationByStride(DOUBLE *doDeviations, DWORD dwSteps) 
  {
    DWORD dwCounter = 0;
    TCHAR tcDevs[BUFFER_SIZE];
    TCHAR tcTmp[BUFFER_SIZE];

    if (dwSteps == 0) 
      {
        return;
      }

    // calculate the size of the buffer needed to hold the 
    // output string

    copyString(tcDevs,_T("=========="), 10);

    _stprintf(tcTmp, _T("%.2f"), doDeviations[0]);
    concatString(tcDevs, tcTmp, 10);

    for (DWORD dwIndex = 1; dwIndex < dwSteps; dwIndex++)
      {
        _stprintf(tcTmp, _T("%.2f"), doDeviations[dwIndex]);
        concatString(tcDevs, tcTmp, 10);
      }
    Info (tcDevs);
  }


// see the header for the details
VOID
formatString(TCHAR *data, DWORD length) 
  {
    TCHAR tchar[BUFFER_SIZE];
    length -= _tcslen(data);

    if (length > 0) 
      {
        _tcscpy_s(tchar, BUFFER_SIZE, _T(" "));

        for (DWORD i = 0; i < length - 1; i++)
          {
            _tcscat_s(tchar, BUFFER_SIZE, _T(" "));
          }
        _tcscat_s(tchar, BUFFER_SIZE, data);
        _tcscpy_s(data, BUFFER_SIZE, tchar);     
      }
  }

// see the header for the details
VOID
copyString(TCHAR *dest, TCHAR *src, int lengthInTotal) 
  {
    _tcscpy_s(dest, BUFFER_SIZE, src);
    formatString(dest, lengthInTotal);    
  }

// see the header for the details
VOID
concatString(TCHAR *dest, TCHAR *src, int lengthInTotal) 
  {
    TCHAR tTmp[BUFFER_SIZE];
    _tcscpy_s(tTmp, BUFFER_SIZE, src);
    formatString(tTmp, lengthInTotal);
    _tcscat_s(dest, BUFFER_SIZE, tTmp);
  }

// see the header for the details
VOID
getMedianValue(CACHE_ACCESS_INFO *pDest, DWORD dwIndex, CACHE_ACCESS_INFO *pSrc) 
  {
    DWORD median = MAX_RUNNING_LOOP / 2;
    ULONGLONG ullTime = pSrc[median].ullTime;

    // even samples. so, we need to average the two middle ones
    if (MAX_RUNNING_LOOP % 2 == 0) 
      {
        ullTime = (ullTime + pSrc[median - 1].ullTime) / 2;
      }

    pDest[dwIndex].ullTime = ullTime;
  }

//  see the header for the details
VOID
sortData(CACHE_ACCESS_INFO **pInfo)
  {
    bubbleSort(pInfo, MAX_RUNNING_LOOP);
  }

//  see the header for the details
VOID
bubbleSort(CACHE_ACCESS_INFO **pInfo, DWORD dwNum)
  {
    BOOL bSorted = FALSE;

    for (DWORD dwOut = 0; dwOut < dwNum && !bSorted; dwOut++)
      {        
        bSorted = TRUE;
        for (DWORD dwInner = 0; dwInner < dwNum - dwOut - 1; dwInner++)
          {
            if ((*pInfo)[dwInner].ullTime > (*pInfo)[dwInner+1].ullTime)
              {
                swapData(pInfo, dwInner, dwInner+1);
                bSorted = FALSE;
              }
          }
      }
  }

// see the header for the details
VOID swapData(CACHE_ACCESS_INFO **pInfo, DWORD dwIndex1, DWORD dwIndex2)
  {
    ULONGLONG ullTime = (*pInfo)[dwIndex1].ullTime;
    DWORD dwPt = (*pInfo)[dwIndex1].dwPt; 

    (*pInfo)[dwIndex1].ullTime = (*pInfo)[dwIndex2].ullTime;
    (*pInfo)[dwIndex1].dwPt = (*pInfo)[dwIndex2].dwPt;
                
    (*pInfo)[dwIndex2].ullTime = ullTime;
    (*pInfo)[dwIndex2].dwPt = dwPt;
  }

// see the header for the details
VOID
printBlockCalByRow(
              DWORD dwStride, 
              DOUBLE *doMissTime, 
              DWORD dwStart, 
              DWORD dwEnd,
              BOOL needMark)
  {
    TCHAR tMissTime [BUFFER_SIZE];
    TCHAR tTmp[BUFFER_SIZE];

    // stride size
    _stprintf(tTmp, _T("%u"), dwStride * sizeof(DWORD));
    copyString(tMissTime, tTmp, 10);
    concatString(tMissTime, _T("bytes"), 6);

    for (DWORD dwIndex = dwStart; dwIndex <= dwEnd; dwIndex++)
      {
        // miss time
        _stprintf(tTmp, _T("%.0f"), doMissTime[dwIndex]);
        concatString(tMissTime, tTmp, 8);
      }      

    // cache line size found, mark the jump position
    if (needMark == TRUE) 
      {
        concatString(tMissTime, _T("<==Jump"), 8);
      }

    Info (tMissTime);
  }

// see the header for the details
DOUBLE
getMax(DOUBLE *doSamples, DWORD dwStart, DWORD dwEnd)
  {
    DOUBLE doMax = doSamples[dwStart];
    for (DWORD dwIndex = dwStart; dwIndex <= dwEnd; dwIndex++)
      {
        if (doMax < doSamples[dwIndex])
          {
            doMax = doSamples[dwIndex];
          }
      }

    return doMax;
  }

// see the header for the details
DOUBLE
getMin(DOUBLE *doSamples, DWORD dwStart, DWORD dwEnd)
  {
    DOUBLE doMin = doSamples[dwStart];
    for (DWORD dwIndex = dwStart; dwIndex <= dwEnd; dwIndex++)
      {
        if (doMin > doSamples[dwIndex])
          {
            doMin = doSamples[dwIndex];
          }
      }

    return doMin;
  }