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

struct pte_int{
  unsigned int page_no   :20;
  unsigned int read_prot :1;
  unsigned int write_prot:1;
  unsigned int exec_prot :1;
  unsigned int resident  :1;
} __attribute__((__packed__)) ;

typedef struct pte_int table_entry_t;

typedef table_entry_t* main_entry_t;

#define INVALID_ENTRY ((main_entry_t)0)

#define PAGE_SIZE 4096

#define LOG_MAIN_TABLE_SIZE 10
#define MAIN_TABLE_SIZE (1 << (LOG_MAIN_TABLE_SIZE))
#define LOG_SECONDARY_SIZE 10
#define SECONDARY_SIZE (1 << (LOG_SECONDARY_SIZE) )

#define CLUSTER_SIZE 384

main_entry_t* alloc_tables(int num_phys_pages, int num_virt_pages);
void gen_virtual_pages(unsigned int* virts, int num_pages);
void assign_page(char* phys, int num_phys, unsigned int* virts, 
		int num_virts, main_entry_t* table);
int random_probe(char* phys, int num_phys);

unsigned int* virts = NULL;

unsigned int get_main_idx(unsigned int virtual_addr);
unsigned int get_sec_idx(unsigned int virtual_addr);
unsigned int get_page_offs(unsigned int virtual_addr);

/*
 * STUDENTS: Implement this!
 */
void* print_entry(void* virtual_addr, main_entry_t* main_table);

int main(int argc, char** argv){
  if(argc < 3){
    printf("Usage: pageTable <num physical> <num virtual>\n");
    return 0;
  }

  int num_phys, num_virts;

  if((sscanf(argv[1], "%d", &num_phys) == 0) ||
     (sscanf(argv[2], "%d", &num_virts) == 0)){
    printf("Usage: pageTable <num physical> <num virtual>\n");
    return 0;
  }

  main_entry_t* table = alloc_tables(num_phys, num_virts);

  int idx;
  unsigned int addr;
  for(idx = 0 ; idx < num_virts ; idx++){
    addr = virts[idx] + (random() % PAGE_SIZE);
    print_entry((void*)addr, table);
  }
  
  return 0;
}

main_entry_t* alloc_tables(int num_phys_pages, int num_virt_pages){
  char* phys_pagez = 
		malloc(num_phys_pages); //checklist for physical pages
  virts = 
		malloc(sizeof(unsigned int) * num_virt_pages);
  main_entry_t* main_table = 
		malloc(sizeof(main_entry_t) * MAIN_TABLE_SIZE);
  int i;

  memset(phys_pagez, 0, num_phys_pages);
  memset(virts, 0, num_virt_pages * sizeof(unsigned int));

  gen_virtual_pages(virts, num_virt_pages);

  for(i = 0 ; i < MAIN_TABLE_SIZE ; i++){
    main_table[i] = INVALID_ENTRY;
  }

  assign_page(phys_pagez, num_phys_pages, 
		virts, num_virt_pages, main_table);

  free(phys_pagez);
  /* free(virts); */

  return main_table;
}

void gen_virtual_pages(unsigned int* virts, int num_pages){
  int i, j;
  int addr, sec;
  srandom(17);

  char* sec_ls = malloc(SECONDARY_SIZE);
  bzero(sec_ls, SECONDARY_SIZE);

  addr = random() & 0xFFFFF000;
  sec = get_main_idx(addr);

  for(i = 0 ; i < num_pages ;){
    while(sec_ls[sec] != 0){
      addr = random() & 0xFFFFF000;
      sec = get_main_idx(addr);
    }

    /* got a clean secondary spot */
    for(j = 0 ; j < CLUSTER_SIZE ; j++){
      if((j + i) >= num_pages){
	i += j;
	break;
      }
      virts[i+j] = addr;
      addr += 0x1000;
    }
    i += CLUSTER_SIZE;
  }
}

void assign_page(char* phys, int num_phys, unsigned int* virts, 
                int num_virts, main_entry_t* table){
  unsigned int virt_page;
  unsigned int main_idx, sec_idx;
  main_entry_t sec_table;
  int phys_idx = 0;
  int forward_idx = 0;
  int backward_idx = num_phys - 1;
  int virt_idx = 0;
  int phys_ct = 0;

  /* do all pages as initially resident. overflow randomly assigned,
   * non-resident.
   */
  
  for(virt_idx = 0 ; 
      (virt_idx < num_virts) && (phys_ct < num_phys) ; 
      virt_idx++, phys_ct++){

    virt_page = virts[virt_idx];
    main_idx = get_main_idx(virt_page);
    sec_table = table[main_idx];


    if(sec_table == INVALID_ENTRY){
      //need to allocate a secondary table
      int sz = sizeof(table_entry_t) * SECONDARY_SIZE;
      sec_table = malloc(sz);
      table[main_idx] = sec_table;
      bzero(sec_table, sz);
      printf("Allocating secondary table at main index %d\n", main_idx);
    }
    sec_idx = get_sec_idx(virt_page);

    printf("Assigning virtual page 0x%x", virt_page);

    /* Now we assign a physical page, first we randomly probe,
     *  if that fails, with random probability we march forward
     *  or backward through the physical page marker looking for
     *  a free spot.
     */
    phys_idx = random_probe(phys, num_phys);
    if(phys_idx != -1){
      /* success */
      sec_table[sec_idx].page_no = phys_idx;
      sec_table[sec_idx].resident = 1;
      phys[phys_idx] = 1;
      printf(" to random physical page 0x%x\n", phys_idx);
      continue;
    } 
    /* we need to march forwards or backwards */
    int choice = random();
    if(choice & 0x1){
      //odd, forwards
      for( ; forward_idx <= backward_idx ; forward_idx++){
	if(phys[forward_idx] == 0){
	  phys_idx = forward_idx;
	  forward_idx++;
	  break;
        }
      }
    }else{
      //even, backwards
      for( ; backward_idx >= forward_idx ; backward_idx--){
	if(phys[backward_idx] == 0){
	  phys_idx = backward_idx;
	  backward_idx--;
	  break;
        }
      }
    }

    phys[phys_idx] = 1;
    sec_table[sec_idx].page_no = phys_idx;
    sec_table[sec_idx].resident = 1;
    printf(" to physical page 0x%x\n", phys_idx);
  }

  /* either we ran out of virtual pages or physical pages */

  for( ; virt_idx < num_virts ; virt_idx++){
  /* ran out of physical pages, make the leftovers non-resident
   */
    virt_page = virts[virt_idx];
    main_idx = get_main_idx(virt_page);
    sec_table = table[main_idx];

    if(sec_table == INVALID_ENTRY){
      //need to allocate a secondary table
      int sz = sizeof(table_entry_t) * SECONDARY_SIZE;
      sec_table = malloc(sz);
      table[main_idx] = sec_table;
      bzero(sec_table, sz);
    }
    sec_idx = get_sec_idx(virt_page);

    /* assign physical page randomly */
    phys_idx = random() % num_phys;
    sec_table[sec_idx].page_no = phys_idx;
    sec_table[sec_idx].resident = 0;

    printf("Assigning virtual page 0x%x to non-resident page 0x%x\n",
		virt_page, phys_idx);
  }

  return;
}

int random_probe(char* phys, int num_phys){
  int idx = random() % num_phys;
  if(phys[idx] != 0){
    return -1;
  }
  return idx;
}

/* STUDENT CODE */

unsigned int get_main_idx(unsigned int virtual_addr){

}

unsigned int get_sec_idx(unsigned int virtual_addr){

}

unsigned int get_page_offs(unsigned int virtual_addr){

}

/* STUDENTS: this function takes a virtual address and a pointer to
 * the main page table and returns the physical address corresponding
 * to the virtual address. This code basically walks the page table.
 * If the virtual address is incorrect, this function should return NULL.
 */
void* print_entry(void* virtual_addr, main_entry_t* main_table){

  /* This function should output the mappings like so, where virt is the 
   * virtual address, phys_addr is the physical address and ent is the
   * table_entry_t for this address.
   */
  printf("Virtual: 0x%x -> 0x%x\n", virt, phys_addr);
  printf("page_no = 0x%x\n", ent.page_no);
  printf("resident = %d\n", ent.resident);

}