/* Program to fill cache. */
#include <stdio.h>
#include <malloc.h>

#define LG_LINE_SIZE 4
#define LG_SET_COUNT 10
#define ASSOCIATIVITY 4

#define SET_COUNT (1<<LG_SET_COUNT)
#define CACHE_SIZE ( ASSOCIATIVITY << ( LG_LINE_SIZE + LG_SET_COUNT ) )

char a[ 2 * CACHE_SIZE ];


int main(int argv, char **argc)
{
  int dummy = 0;

  printf("Cache parameters:\n");
  printf("  %d-way set associative, 2^%d = %d sets.\n", 
         ASSOCIATIVITY, LG_SET_COUNT, 1<<LG_SET_COUNT);
  printf("  Line size 2^%d = %d characters, character size 8 bits = 1 byte.\n",
         LG_LINE_SIZE, 1<<LG_LINE_SIZE);
  printf("  Cache capacity %d bytes, %.2f MiB (megibytes) [sic].\n",
         ASSOCIATIVITY << ( LG_LINE_SIZE + LG_SET_COUNT ),
         ((double)(ASSOCIATIVITY << ( LG_LINE_SIZE + LG_SET_COUNT )))
         / ( 1 << 20 ));


  /* Fill up cache with minimum number of accesses. */

  {
    int s,w;
    char *addr = &a[0];
    int linesize = 1 << LG_LINE_SIZE;

    for(w=0; w<ASSOCIATIVITY; w++)

      for(s=0; s<SET_COUNT; s++) 
        {
          dummy += *addr;
          /* Below, increment index part of address. */
          addr += linesize;
        }
  }

  /* Fill up cache with minimum number of accesses. (Alternate method.) */

  {
    int w;

    for(w=0; w<ASSOCIATIVITY; w++)
      {
        char *b = & a[ w << ( LG_LINE_SIZE + LG_SET_COUNT ) ];
        int s;

        for(s=0; s<SET_COUNT; s++) dummy += b[ s << LG_LINE_SIZE ];
      }
  }

  /* Generate lots of misses while accessing only ASSOCIATIVITY + 1
     array elements. */

  {
    int i, w;
    int deadly_stride = 1 << ( LG_LINE_SIZE + LG_SET_COUNT );

    for(i=0; i<100; i++)
      {
        char *addr = &a[0];

        for(w=0; w<=ASSOCIATIVITY; w++)
          {
            dummy += *addr;  
            /* Below: Increment tag part of address. */
            addr += deadly_stride;
          }
      } 
  }

  if( dummy ) 
    printf("This line prevents optimizer from eliminating code above.\n");

  return 0;
}