#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

#define EMPTY -1
#define PAGE_SIZE 4096
#define MAX_PAGES 5000

typedef struct _node {
   int pageno;
   struct _node *prev;
   struct _node *next;
} node;

node *PT[MAX_PAGES];
node *LP = NULL, *LAST = NULL;

int checkfault ( int f, int pageno, int *npl )
{
   node *p, *prev, *next;

   // usleep(1000);
   p = PT[pageno];
   if (p != NULL) {         /* Page found */
      prev = p -> prev;
      next = p -> next;
      if (prev != NULL) {   /* bring page to the front */
         prev -> next = next;
         if (next == NULL) LAST = prev; else next -> prev = prev;
         p -> next = LP;
         p -> prev = NULL;
         LP -> prev = p;
         LP = p;
      }
      return 0;
   }

   /* Page fault */

   if (*npl == f) {         /* page replacement necessary */
      p = LAST -> prev;
      PT[LAST -> pageno] = NULL;
      free(LAST);
      LAST = p;
      LAST -> next = NULL;
      if (LAST == NULL) LP = NULL;
   } else {              /* use an empty frame */
      ++(*npl);
   }

   /* Insert the new page at the beginning of LP */
   p = (node *)malloc(sizeof(node)); p -> pageno = pageno; PT[pageno] = p;
   if (LP == NULL) { p -> next = p -> prev = NULL; LP = LAST = p; }
   else { p -> next = LP; LP -> prev = p; p -> prev = NULL; LP = p; }

   return 1;
}

int accesspage1 ( int f, char arrid, int r, int c, int *npl )
{
   int offset;

   switch (arrid) {
      case 'R': offset = 1920 * r + c; break;
      case 'G': offset = 1920 * (1080 + r) + c; break;
      case 'B': offset = 1920 * (2160 + r) + c; break;
      case 'r': offset = 1920 * (3240 + r) + c; break;
      case 'g': offset = 1920 * (4320 + r) + c; break;
      case 'b': offset = 1920 * (5400 + r) + c; break;
      default: fprintf(stderr, "*** Invalid array name: %c\n", arrid); exit(1);
   }
   return checkfault(f, offset / PAGE_SIZE, npl);
}

int accesspage2 ( int f, char arrid, int r, int c, int *npl )
{
   int offset;

   switch (arrid) {
      case 'R': offset = 5760 * r + 3 * c; break;
      case 'G': offset = 5760 * r + 3 * c + 1; break;
      case 'B': offset = 5760 * r + 3 * c + 2; break;
      case 'r': offset = 5760 * (1080 + r) + 3 * c; break;
      case 'g': offset = 5760 * (1080 + r) + 3 * c + 1; break;
      case 'b': offset = 5760 * (1080 + r) + 3 * c + 2; break;
      default: fprintf(stderr, "*** Invalid array name: %c\n", arrid); exit(1);
   }
   return checkfault(f, offset / PAGE_SIZE, npl);
}

int accesspage3 ( int f, char arrid, int r, int c, int *npl )
{
   int offset;

   switch (arrid) {
      case 'R':
      case 'G':
      case 'B': offset = 7680 * r + 4 * c; break;
      case 'r':
      case 'g':
      case 'b': offset = 7680 * (1080 + r) + 4 * c; break;
      default: fprintf(stderr, "*** Invalid array name: %c\n", arrid); exit(1);
   }
   return checkfault(f, offset / PAGE_SIZE, npl);
}

int accesspage4 ( int f, char arrid, int r, int c, int *npl )
{
   int poffset, doffset;

   switch (arrid) {
      case 'R': poffset = 8 * r;
                doffset = 1080 * 8 + 1920 * r + c;
                break;
      case 'G': poffset = 1080 * 1928 + 8 * r;
                doffset = 2160 * 8 + (1080 + r) * 1920 + c;
                break;
      case 'B': poffset = 2160 * 1928 + 8 * r;
                doffset = 3240 * 8 + (2160 + r) * 1920 + c;
                break;
      case 'r': poffset = 3240 * 1928 + 8 * r;
                doffset = 4320 * 8 + (3240 + r) * 1920 + c;
                break;
      case 'g': poffset = 4320 * 1928 + 8 * r;
                doffset = 5400 * 8 + (4320 + r) * 1920 + c;
                break;
      case 'b': poffset = 5400 * 1928 + 8 * r;
                doffset = 6480 * 8 + (5400 + r) * 1920 + c;
                break;
      default: fprintf(stderr, "*** Invalid array name: %c\n", arrid); exit(1);
   }
   return checkfault(f, poffset / PAGE_SIZE, npl) + checkfault(f, doffset / PAGE_SIZE, npl);
}

int accesspage5 ( int f, char arrid, int r, int c, int *npl )
{
   int poffset, doffset;

   switch (arrid) {
      case 'R': poffset = 8 * r; doffset = 8640 + 5760 * r + 3 * c; break;
      case 'G': poffset = 8 * r; doffset = 8640 + 5760 * r + 3 * c + 1; break;
      case 'B': poffset = 8 * r; doffset = 8640 + 5760 * r + 3 * c + 2; break;
      case 'r': poffset = 1080 * 5768 + 8 * r; doffset = 1080 * 5776 + 5760 * r + 3 * c; break;
      case 'g': poffset = 1080 * 5768 + 8 * r; doffset = 1080 * 5776 + 5760 * r + 3 * c + 1; break;
      case 'b': poffset = 1080 * 5768 + 8 * r; doffset = 1080 * 5776 + 5760 * r + 3 * c + 2; break;
      default: fprintf(stderr, "*** Invalid array name: %c\n", arrid); exit(1);
   }
   return checkfault(f, poffset / PAGE_SIZE, npl) + checkfault(f, doffset / PAGE_SIZE, npl);
}

int accesspage6 ( int f, char arrid, int r, int c, int *npl )
{
   int poffset, doffset;

   switch (arrid) {
      case 'R':
      case 'G':
      case 'B': poffset = 8 * r; doffset = 8640 + 7680 * r + 4 * c; break;
      case 'r':
      case 'g':
      case 'b': poffset = 1080 * 7688 + 8 * r; doffset = 1080 * 7696 + 7680 * r + 4 * c; break;
      default: fprintf(stderr, "*** Invalid array name: %c\n", arrid); exit(1);
   }
   return checkfault(f, poffset / PAGE_SIZE, npl) + checkfault(f, doffset / PAGE_SIZE, npl);
}

int accesspage ( int f, char arrid, int r, int c, int scheme, int *npl )
{
   switch (scheme) {
      case 1: return accesspage1(f, arrid, r, c, npl);
      case 2: return accesspage2(f, arrid, r, c, npl);
      case 3: return accesspage3(f, arrid, r, c, npl);
      case 4: return accesspage4(f, arrid, r, c, npl);
      case 5: return accesspage5(f, arrid, r, c, npl);
      case 6: return accesspage6(f, arrid, r, c, npl);
      default: fprintf(stderr, "*** Invalid scheme: %d\n", scheme); exit(1);
   }
   return 0;
}

void blur ( int k, int f, int scheme )
{
   int i, j, rs, re, cs, ce, rd, cd, u, v;
   int nma = 0, npf = 0, npl = 0;


   for (i=0; i<MAX_PAGES; ++i) PT[i] = NULL;
   LP = LAST = NULL;

   switch (scheme) {
      case 1: printf("\n+++ Scheme 1: Three static arrays\n"); break;
      case 2: printf("\n+++ Scheme 2: One static array of char\n"); break;
      case 3: printf("\n+++ Scheme 3: One static array of struct\n"); break;
      case 4: printf("\n+++ Scheme 4: Three dynamic arrays\n"); break;
      case 5: printf("\n+++ Scheme 5: One dynamic array of char\n"); break;
      case 6: printf("\n+++ Scheme 6: One dynamic array of struct\n"); break;
      default: printf("\n*** Unknown scheme: Giving up\n"); return;
   }

   for (i=0; i<1080; ++i) {
      for (j=0; j<1920; ++j) {
         rs = i - k; if (rs < 0) rs = 0;
         re = i + k; if (re >= 1080) re = 1079;
         cs = j - k; if (cs < 0) cs = 0;
         ce = j + k; if (ce >= 1920) ce = 1919;
         for (u=rs; u<=re; ++u) {
            rd = (u - i) * (u - i);
            for (v=cs; v<=ce; ++v) {
               cd = (v - j) * (v - j);
               if (rd + cd <= k * k) {
                  if ((scheme == 3) || (scheme == 6)) {
                     npf += accesspage(f, 'R', u, v, scheme, &npl);
                     if (scheme == 3) nma += 1; else nma += 2;
                  } else {
                     npf += accesspage(f, 'R', u, v, scheme, &npl);
                     npf += accesspage(f, 'G', u, v, scheme, &npl);
                     npf += accesspage(f, 'B', u, v, scheme, &npl);
                     if ((scheme == 1) || (scheme == 2)) nma += 3; else nma += 6;
                  }
               }
            }
         }
         if ((scheme == 3) || (scheme == 6)) {
            npf += accesspage(f, 'r', i, j, scheme, &npl);
            if (scheme == 3) nma += 1; else nma += 2;
         } else {
            npf += accesspage(f, 'r', i, j, scheme, &npl);
            npf += accesspage(f, 'g', i, j, scheme, &npl);
            npf += accesspage(f, 'b', i, j, scheme, &npl);
            if ((scheme == 1) || (scheme == 2)) nma += 3; else nma += 6;
         }
      }
   }

   printf("    Total number of memory accesses = %d\n", nma);
   printf("    Total number of page faults     = %d\n", npf);
   printf("    Page fault rate (percentage)    = %.2lf\n", 100. * (double)npf / (double)nma);
   printf("    Total memory access time        = %.2lf sec\n", npf * 0.01 + nma * 0.0000001);
}

int main ( int argc, char *argv[] )
{
   int k, f, scheme;

   k = (argc > 1) ? atoi(argv[1]) : 5;
   f = (argc > 2) ? atoi(argv[2]) : 10;

   printf("+++ k = %d, f = %d\n", k, f);

   for (scheme = 1; scheme <= 6; ++scheme) blur(k,f,scheme);

   exit(0);
}