/*
 EGGX を用いた仮想記憶システムの動作シミュレーション
*/


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

#define ITVL 100  /* interval time (ms) */
#define RSIZ 8    /* real memory size (pages) */
#define VSIZ 16   /* virtual memory size (pages) */

#define RMAX 32   /* max real memory (by page size) */
#define VMAX 32   /* max virtual memory (by page size) */

void usage() {
  fprintf(stderr, "usage: virtmem [-vnSL][-s speed][-r rsize][-x vsize] \n");
  fprintf(stderr, "       v : verbose mode.\n");
  fprintf(stderr, "       S : SKIP mode.\n");
  fprintf(stderr, "       L : simple LRU alogorithm.\n");
  fprintf(stderr, "       s : display interval time (default=%dms)\n", ITVL);
  fprintf(stderr, "       r : real memory size (default=%d pages)\n", RSIZ);
  fprintf(stderr, "       x : virtual memory size (default=%d pages)\n", VSIZ);
  return;
}

int vmode=1;
int smode=1; /* default is step by sep */
int lmode=1;
int itvl=ITVL;
int rsiz=RSIZ;
int vsiz=VSIZ;

int rmem[RMAX]; /* real memory image
		 -1: 未使用 n: vmem[n] 番目に対応することを示す */
int rtim[RMAX]; /* real memory 使用タイミングテーブル */
int vmem[VMAX]; /* virtual memory image
		 0: 未使用 m: プログラム番号（＝描画色）に対応 */
int vflg[VMAX]; /* vm flag 0:inactive 1:active */

int step=0; /* メモリアクセス仮想時間 */
int win;    /* ウィンドウ番号 */

#define W 30 /* メモリ1ページの図形イメージの幅 */
#define H 40 /* メモリ1ページの図形イメージの高さ */

#define WW 800 /* ウィンドウの幅 */
#define HH 400 /* ウィンドウの高さ */

#define XOFF 40 /* 描画をはじめる X 位置のオフセット */
#define YOFF 40 /* 描画をはじめる Y 位置のオフセット */

/* プログラムごとの色対応表 0-赤 1-緑 2-青 3-シアン 4-マゼンタ 5-黄 */
int col1[7][3]={
{255, 255, 255} , /* 白 */ 
{255,   0,   0} , /* 赤 */ 
{  0, 255,   0} , /* 緑 */ 
{  0,   0, 255} , /* 青 */ 
{255, 255,   0} , /* シアン */ 
{255,   0, 255} , /* マゼンタ */ 
{  0, 255, 255} }; /* 黄 */ 

int col2[7][3]={
{96, 96, 96} , /* 灰 */
{255, 96, 96} , /* 赤の淡色 */ 
{96, 255, 96} , /* 緑の淡色 */ 
{96, 96, 255} , /* 青の淡色 */ 
{255, 255, 96} , /* シアンの淡色 */ 
{255, 96, 255} , /* マゼンタの淡色 */ 
{96, 255, 255} }; /* 黄の淡色 */ 

#define MM 20
char com[MM][256]; /* コマンドラインメッセージバッファ */
int  comp[MM]; /* コマンド対象プログラム番号 */
int cp=0; /* コマンドライン行ポインタ com[cp], 0<=cp<MM */

/*
 メモリイメージの初期化
 rmem は値 -1 で空（未使用）
 vmem は値 0 で空（未使用）
 */
int init_memory()
{
  int i;
  for(i=0; i<RMAX; i++) {
    rmem[i]= -1;
    rtim[i]=0;
  };
  for(i=0; i<VMAX; i++) {
    vmem[i]=0;
    vflg[i]=0;
  };

  return 0;
}

/* 
 色コードに対応する色を設定する
*/
int pgcolor(int c, int f)
{
  if(f == 1) { /* active color */
    newrgbcolor(win, col1[c][0], col1[c][1], col1[c][2]);
  } else { /* inactive color */
    newrgbcolor(win, col2[c][0], col2[c][1], col2[c][2]);
  };
  
  return 0;
}

/* 
 背景描画 (show_memory から呼ばれることが前提）
 */
int show_mat()
{
  int i;
  
  gclr(win);

  /* プログラム色見本 */
  for(i=1; i<7; i++) {
    pgcolor(i, 1);
    fillrect(win, WW-375, HH-20-i*25, 20, 20);
    newpen(win, 1);
    drawstr(win, WW-350, HH-15-i*25, 16, 0.0, "PROGRAM %d", i);
  };

  /* 実行コマンド */
  for(i=0; i<cp; i++) {
    newpen(win, 1);
    drawstr(win, WW-200, HH-30-i*20, 16, 0.0, "%s", com[i]);
    if(comp[i] != 0) {
      pgcolor(comp[i], 1);
      fillrect(win, WW-220, HH-30-i*20, 13, 13);
    };
  };

  /* アクセスカウントのラベル */
  newpen(win, 1);
  drawstr(win, XOFF-30, YOFF+H*3+10, 12, 0.0, "access");

  return 0;
}

/* 
 メモリ内容の表示
 */
int show_memory()
{
  int i;

  show_mat();

  /* real memory の描画 */
  for(i=0; i<rsiz; i++) {
    if(rmem[i] == -1) { /* 未使用 */
      newpen(win, 1); /* 白 */
      fillrect(win, XOFF+i*W, YOFF+H*2, W-2, H);
    } else {
      pgcolor(vmem[rmem[i]], 1); /* 対応するプログラム番号の色コード */
      fillrect(win, XOFF+i*W, YOFF+H*2, W-2, H);
      newpen(win, 1);
      drawstr(win, XOFF+i*W+W/3, YOFF+H*2-16, 16, 0.0, "%2d",rmem[i]+1);
      drawstr(win, XOFF+i*W+W/3, YOFF+H*3+8, 12, 0.0, "%2d",rtim[i]);
    };
  };

  /* virtual memory の描画 */
  for(i=0; i<vsiz; i++) {
    if(vmem[i] == 0) { /* 未使用 */
      newpen(win, 1); /* 白で描画 */
    } else {
      pgcolor(vmem[i], vflg[i]); /* 対応するプログラム番号の色 */
    };
    fillrect(win, XOFF+i*W, YOFF, W-2, H);
    newpen(win, 1);
    drawstr(win, XOFF+i*W+W/3, YOFF-16, 16, 0.0, "%2d",i+1);
  };

  copylayer(win, 1, 0);
  
  return 0;
}

/*
 vm_load(v, m) : virtual memory の v 番目にプログラム m をロード
*/
int vm_load(int v, int m) 
{
  vmem[v]=m;
  vflg[v]=1; /* activate */

  return 0;
}

/*
 プログラム実行アニメーション
 x1, y1 と x2, y2 の w, h サイズのフレームを c 色で点滅
 */
int anim_run(int x1, int y1, int w, int h, int x2, int y2, int c)
{
  int i, ww, s=5;
  
  newpen(win, 8);
  fillrect(win, x2, y2, w, h);
  copylayer(win, 1, 0);

  for(i=1; i<=s; i++) {
    ww= (float)(w) * (float)(i) / (float)(s);
    newpen(win, 8);
    fillrect(win, x1, y1, ww, h);
    copylayer(win, 1, 0);
    msleep(itvl/5);
  };
  show_memory();

  return 0;
}

/*
 フレーム移動アニメーション
 x1, y1 から w, h サイズのフレームを x2, y2 位置に移動
 */
int anim_move(int x1, int y1, int w, int h, int x2, int y2)
{
  int i, x, y, s=10;

  for(i=0; i<=s; i++) { 
    x= x1 + (float)(x2-x1) / (float)(s) * i;
    y= y1 + (float)(y2-y1) / (float)(s) * i;
    newpen(win, 8);
    drawrect(win, x, y, w, h);
    copylayer(win, 1, 0);
    msleep(itvl/5);
  };

  return 0;
}

/* 
 page_in(r, v) : real memory の r 番目に virtual memory の v 番目を page in
 */
int page_in(int r, int v)
{
  anim_move(XOFF+v*W-1, YOFF, W-1, H+1, XOFF+r*W-1, YOFF+H*2-1);
  rmem[r]=v;
  rtim[r]=step++; /* 使用時間を設定 */
  vflg[v]=0; /* inactive */
  show_memory();

  return 0;
}

/* 
 page_out(r) : real memory の r 番目を virtual memory に page out
 */
int page_out(int r)
{
  int v;

  v=rmem[r];
  anim_move(XOFF+r*W-1, YOFF+H*2-1, W-1, H+1, XOFF+v*W-1, YOFF);
  rmem[r]= -1;
  rtim[r]=0;
  vflg[v]=1; /* active */
  show_memory();

  return 0;
}

/*
 空いている仮想記憶領域をみつける
 常に先頭から空きを捜すようにする
 戻り値 -1 で発見できず
*/
int vm_find_empty()
{
  int i;

  for(i=0; i<vsiz; i++) {
    if(vmem[i] == 0) { /* 空き発見 */
      return i;
    };
  };

  return -1;
}

/*
 指定の vm エリアが主記憶上にあるかどうかをチェック
 常に先頭から空きを捜すようにする
 戻り値 -1 で発見できず
 それ以外の戻り値はページ番号を返す
*/
int page_check(int v)
{
  int i;

  for(i=0; i<rsiz; i++) {
    if(rmem[i] == v) { /* 発見 */
      return i;
    };
  };

  return -1;
}

/*
 空いているページをみつける 
 常に先頭から空きを捜すようにする
 戻り値 -1 で発見できず
*/
int page_find_empty()
{
  int i;

  for(i=0; i<rsiz; i++) {
    if(rmem[i] == -1) { /* 空き発見 */
      return i;
    };
  };

  return -1;
}

/* 
 掃き出すページを決定する
 LRU 法（ただし lmode=1 なら自分と同じプログラムの領域は優先順位低く）
 c : program type （色に相当）
*/
int page_find_out(int c)
{
  int i, k, m=2147483647;  /* m は 2^31 - 1 を初期最大値として仮定 */

  if( lmode == 1 ) { 

    /* 同じプログラムに属するページは優先順位が低くても掃き出さない */
    k= -1;
    for(i=0; i<rsiz; i++) {
      if((rmem[i] == -1)||(vmem[rmem[i]] == c)) {
	/* 空きページと同一プログラムは処理対象外 */
      } else {
	if(rtim[i] < m) { /* より古くから触っていないページを発見 */
	  m=rtim[i];
	  k=i;
	};
      };
    };
    
    if(k != -1) { /* 掃き出し対象ページ発見 */
      return k;
    };

  };

  /* 同一プログラム内でも掃き出さざるを得ないとして再検索 */
  k= -1;
  for(i=0; i<rsiz; i++) {
    if(rmem[i] != -1) { /* 空きページは処理対象外 */
      if(rtim[i] < m) { /* より古くから触っていないページを発見 */
	m=rtim[i];
	k=i;
      };
    };
  };

  return k;
}

/*
 プログラムをどこかにロードする
 c : program type （色に相当）
 s : program size (pages)
 戻り値 -1 でロード失敗
*/
int load(int c, int s)
{
  int i, v, r;

  for(i=0; i<s; i++) {
    if((v=vm_find_empty()) == -1 ) { /* 空き VM 無し */
      if(vmode) fprintf(stderr, "load(%d, %d) = cannot load. ",c,s);
      return -1; /* ロード失敗 */
    } else {
      vm_load(v, c); /* vm にロード */
      if((r=page_find_empty()) == -1 ) { /* 空きページ無し */
	r=page_find_out(c); /* 掃き出し対象を決定して */
	page_out(r); /* ページを掃き出す */
      };
      page_in(r, v); /* page にロード */
    };
  };

  return 0;
}

/*
 指定のプログラムを実行する
 c : program type （色に相当）
*/
int run(int c)
{
  int r, v;

  for(v=0; v<vsiz; v++) {
    if(vmem[v] == c) { /* 該当プログラム */
      if( (r=page_check(v))== -1) { /* ram 上に無し (page fault) */
	if((r=page_find_empty()) == -1 ) { /* 空きページ無し */
	  r=page_find_out(c); /* 掃き出し対象を決定して */
	  page_out(r); /* ページを掃き出す */
	};
	page_in(r, v); /* page にロード (use timestamp 押しも含まれる) */
      } else {
	rtim[r]=step++; /* use timestamp を押しておく */
      };
      anim_run(XOFF+r*W, YOFF+H*2, W-2, H, XOFF+v*W, YOFF, c);
    };
  };
  
  return 0;
}

/*
 入り口
 */
int main(int argc, char *argv[])
{
  int ch;
  extern char *optarg;
  extern int optind;
  char buf[256];
  int p, l;
  
  /* option recognise */
  while ((ch = getopt(argc, argv, "vnSLs:r:x:")) != EOF) {
    switch((char)ch) {
    case 'v': /* verbose mode */
      vmode=1;
      break;
    case 'n': /* quiet mode */
      vmode=0;
      break;
    case 'S': /* SKIP mode */
      smode=0;
      break;
    case 'L': /* simple LRU algorithm mode */
      lmode=0;
      break;
    case 's': /* interval time */
      itvl=atoi(optarg);
      break;
    case 'r': /* real memory size */
      rsiz=atoi(optarg);
      break;
    case 'x': /* virtual memory size */
      vsiz=atoi(optarg);
      break;
    case '?': /* Help message */
    default:
      usage();
      fprintf(stderr,"virtmem : unrecognized parameter exist.\n");
      exit(1);
    };
  };
  /* Skip the position of argc,argv[] */
  argc -= optind;
  argv += optind;
  
  if(argc!=0) {
    usage();
    fprintf(stderr,"virtmem : extra parameter is exist.\n");
    exit(1);
  };

  win=gopen(WW,HH);
  winname(win, "Virtual memory simulation");
  layer(win, 0, 1);

  init_memory();

  show_memory(); 
  newpen(win, 1);
  fillrect(win, WW-145, 20, 20, 20);
  drawstr(win, WW-120, 25, 16, 0.0, "READY to go.");
  copylayer(win, 1, 0);
  ggetch(win);
  show_memory();

  while(! feof(stdin)) {
    fgets(buf, sizeof(buf), stdin);
    if(vmode) printf("%s",buf);
    strcpy(com[cp], buf);
    comp[cp]=0;
    
    if(strncmp("#", buf, 1)==0) { /* comment */
      cp++;
      /* nothing to do */
    } else if(strncmp("exit", buf, 4)==0) { /* exit */
      cp++;
      break;
    } else if(strncmp("load ", buf, 5)==0) { /* load */
      sscanf(&buf[5], "%d %d", &p, &l);
      comp[cp++]=p;
      show_memory();
      if(smode) ggetch(win);
      load(p, l);
    } else if(strncmp("run ", buf, 4)==0) { /* run */
      sscanf(&buf[4], "%d", &p);
      comp[cp++]=p;
      show_memory();
      if(smode) ggetch(win);
      run(p);
    };
  };
  
  layer(win, 1, 1);
  show_memory();
  newpen(win, 1);
  fillrect(win, WW-145, 20, 20, 20);
  drawstr(win, WW-120, 25, 16, 0.0, "END of DATA");
  copylayer(win, 1, 0);
  ggetch(win);
  gclose(win); 

  return(0);

}