#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <linux/ext2_fs.h>
#include <string.h>

#define BASE_OFFSET 1024
#define USB_DEVICE "/dev/sdb1"
#define BLOCK_OFFSET(block) (BASE_OFFSET + (block - 1) * block_size)
#include <linux/fs.h>
#define FILTER_BIT(byte, i) ((byte >> i) & 0x01)

static unsigned int block_size = 0;
unsigned int ptrs_per_block = 0;
unsigned int blocks_per_group = 0;
unsigned int inodes_per_group = 0;

/*
 * Reads in the superblock from the device. Returns the file descriptor
 * being used.
 */
int read_superblock(struct ext2_super_block* super);

/*
 * Given a superblock, allocates a group descriptor array large enough and
 * reads it in.
 */
struct ext2_group_desc* get_group_descs(int fd,
					struct ext2_super_block* super);
/* 
 * reads the root inode from the USB drive and stores it in root_inode.
 * Returns the file descriptor.
 */
int get_root_inode(int fd,
		   struct ext2_super_block* super,
		   struct ext2_group_desc* group,
		   struct ext2_inode* root_inode);

/*
 * Function to read in an inode.
 */
void read_inode(int fd, //file descriptor
		struct ext2_super_block* super, //the superblock
		struct ext2_group_desc* group, //current group descriptor
		int inode_no, //the inode to process
		struct ext2_inode* inode //the place to store the inode data
		);

/*
 * Function to list the directory described by inode.
 */
void list_directory(int fd,
                    struct ext2_super_block* super,
                    struct ext2_group_desc* group,
                    struct ext2_inode* inode);

/*
 * STUDENTS, IMPLEMENT THIS! This function is called in list_directory for
 *  each directory entry encountered.
 */
void print_entry(int fd,
		 struct ext2_dir_entry_2* entry,
		 struct ext2_super_block* super,
		 struct ext2_group_desc* group);
/*
 * Reads the file described by inode and returns the bytes.
 */
char* read_file(int fd,
		struct ext2_super_block* super,
		struct ext2_group_desc* group,
		struct ext2_inode* inode);

/*
 * Reads out block_no into buffer.
 */
void read_block(int fd, int block_no, char* buffer);

/*
 * Reads the blocks pointed to in the indirect block at block_num. Stores
 * The bytes into buff, starting at offset. Returns the new offset.
 */
unsigned int read_indirect_block(int fd,
			 	 struct ext2_inode* inode,
				 __le32 block_num,
			 	 char* buff,
			 	 unsigned int offset);

unsigned int read_dbl_indirect_block(int fd,
			 	     struct ext2_inode* inode,
				     __le32 block_num,
			 	     char* buff,
			 	     unsigned int offset);

unsigned int read_trpl_indirect_block(int fd,
			 	      struct ext2_inode* inode,
				      __le32 block_num,
			 	      char* buff,
			 	      unsigned int offset);
int main(void){
  int file_descriptor;
  struct ext2_inode root_inode;
  struct ext2_super_block super;
  struct ext2_group_desc* group;

  file_descriptor = read_superblock(&super);
  group = get_group_descs(file_descriptor, &super);
  get_root_inode(file_descriptor, &super, group, &root_inode);
  
  list_directory(file_descriptor, &super, group, &root_inode);


  close(file_descriptor);
  return 0;
}

char* read_file(int fd,
		struct ext2_super_block* super,
		struct ext2_group_desc* group,
		struct ext2_inode* inode){
  size_t file_size = block_size*(inode->i_size);
  char* buffer = (char*)malloc(file_size);
  unsigned int offset = 0;
  int block_idx = 0;
  unsigned int block_ct = 0;

  if(buffer == NULL){
    //out of memory
    printf("Ran out of memory\n");
    close(fd);
    exit(1);
  }


  //First, we handle the direct block pointers
  while((block_idx < EXT2_NDIR_BLOCKS) && (block_ct <= inode->i_blocks)){
    //read in the block directly
    read_block(fd, inode->i_block[block_idx], (char*)(buffer + offset)); 
    offset += block_size;
    block_ct++;
    block_idx++;
  }

  //Then the indirect block
  if(block_ct <= inode->i_blocks){
    offset = read_indirect_block(fd, inode, 
				inode->i_block[EXT2_IND_BLOCK], buffer, offset);
    block_ct += ptrs_per_block;
  }

  //Then the double-indirect block
  if(block_ct <= inode->i_blocks){
    offset = read_dbl_indirect_block(fd, inode,
		inode->i_block[EXT2_DIND_BLOCK], buffer, offset);
    block_ct += (ptrs_per_block * ptrs_per_block);
  }

  //Then the triple-indirect block
  if(block_ct <= inode->i_blocks){
    offset = read_trpl_indirect_block(fd, inode,
		inode->i_block[EXT2_TIND_BLOCK], buffer, offset);
    //block_ct += (ptrs_per_block * ptrs_per_block * ptrs_per_block);
  }

  return buffer;
}

unsigned int read_indirect_block(int fd,
			 	 struct ext2_inode* inode,
				 __le32 block_num,
			 	 char* buff,
			 	 unsigned int offset){
  __le32* ind_buf = (__le32*)malloc(block_size);
  int idx = 0;

  if(ind_buf == NULL){
    printf("Out of Memory\n");
    close(fd);
    exit(1);
  }

  read_block(fd, block_num, (char*)ind_buf);

  //Now we read in the blocks
  for(idx = 0 ; idx < ptrs_per_block ; idx++){
    read_block(fd, ind_buf[idx], (char*)(buff + offset));
    offset += block_size;
  }

  return offset;
}

unsigned int read_dbl_indirect_block(int fd,
			 	     struct ext2_inode* inode,
				     __le32 block_num,
			 	     char* buff,
			 	     unsigned int offset){
  __le32* dind_buf = (__le32*)malloc(block_size);
  int d_idx;

  if(dind_buf == NULL){
    printf("Out of Memory\n");
    close(fd);
    exit(1);
  }

  read_block(fd, block_num, (char*)dind_buf);

  for(d_idx = 0 ; d_idx < ptrs_per_block ; d_idx++){
    offset = read_indirect_block(fd, inode, dind_buf[d_idx], buff, offset);
  }

  return offset;
}

unsigned int read_trpl_indirect_block(int fd,
			 	      struct ext2_inode* inode,
				      __le32 block_num,
			 	      char* buff,
			 	      unsigned int offset){
  __le32* tind_buf = (__le32*)malloc(block_size);
  int t_idx;

  if(tind_buf == NULL){
    printf("Out of Memory\n");
    close(fd);
    exit(1);
  }

  read_block(fd, block_num, (char*)tind_buf);

  for(t_idx = 0 ; t_idx < ptrs_per_block ; t_idx++){
    offset = read_dbl_indirect_block(fd, inode, tind_buf[t_idx], buff, offset);
  }

  return offset;
}

void list_directory(int fd,
		    struct ext2_super_block* super,
		    struct ext2_group_desc* group,
		    struct ext2_inode* inode){
  char* buffer;
  int size = 0;
  struct ext2_dir_entry_2* entry;

  if(!S_ISDIR(inode->i_mode)){
    printf("Not a Directory!\n");
    return;
  }

  //Now we read in the actual directory blocks
  buffer = read_file(fd, super, group, inode);

  //treat the block like an array of dir_entries
  entry = (struct ext2_dir_entry_2*)buffer;

  //checking to make sure we haven't fallen off the array
  while(size < inode->i_size){
    //printf("Entry #%d\n", entry_num);
    if(entry->inode > 0){ //this is a valid entry
	print_entry(fd, entry, super, group);
    }

    size += entry->rec_len;
    entry = (void*)entry + entry->rec_len;
  }
}


void print_entry(int fd,
		 struct ext2_dir_entry_2* entry,
		 struct ext2_super_block* super,
		 struct ext2_group_desc* group){
   /*
   * Implement this function to print out the directory entry pointed to by
   * entry. You should output "<perm string>\t<file name>\n" where <perm string>
   * is the standard permission string from ls -l. e.g. something like 
   * "dr-xrwx---". Make sure that you remember to set the first character based
   * upon the file type (e.g. 'd' for directories and '-' for normal files).
   */
}

void read_block(int fd, int block_no, char* buffer){
  lseek(fd, BLOCK_OFFSET(block_no), SEEK_SET);
  read(fd, buffer, block_size);
}

void read_inode(int fd, //file descriptor
		struct ext2_super_block* super, //the superblock
		struct ext2_group_desc* group, //current group descriptor
		int inode_no, //the inode to process
		struct ext2_inode* inode //the place to store the inode data
		){
	int group_no = inode_no/inodes_per_group;
	int inode_offset = (inode_no - group_no * inodes_per_group - 1);

/*
	printf("inode_offset = %d\n", inode_offset);
	printf("group_no = %d\n", group_no);
	printf("BLOCK_OFFSET = %d\n", BLOCK_OFFSET(group[group_no].bg_inode_table));
*/

	lseek(fd, 
	      BLOCK_OFFSET(group[group_no].bg_inode_table) + inode_offset *
	   	sizeof(struct ext2_inode),
	      SEEK_SET);
	read(fd, inode, sizeof(struct ext2_inode));
}

int read_superblock(struct ext2_super_block* super){
  int fd;

  /* open USB device */
  fd = open(USB_DEVICE, O_RDONLY); //opening the device for reading
  if(fd < 0){ //some kind of error occurred
    perror(USB_DEVICE);
    exit(1); //we give up at this point
  }

  /* Now we read in Mr. Superblock */
  /* seeking across the 'disk' to the superblock location */
  lseek(fd, BASE_OFFSET, SEEK_SET);
  /*actually reading in the bytes */
  read(fd, super, sizeof(struct ext2_super_block));

  /* Some sanity checks */
  /* Make sure we're reading an EXT2 filesystem */
  if(super->s_magic != EXT2_SUPER_MAGIC){
    fprintf(stderr, "Not an Ext2 filesystem!\n");
    exit(1);
  }

  block_size = 1024 << super->s_log_block_size;
  blocks_per_group = super->s_blocks_per_group;
  inodes_per_group = super->s_inodes_per_group;

  return fd;
}

struct ext2_group_desc* get_group_descs(int fd,
					struct ext2_super_block* super){
  unsigned int num_groups = 
	(super->s_blocks_count + super->s_blocks_per_group - 1) /
	super->s_blocks_per_group;
  unsigned int arr_size = num_groups * sizeof(struct ext2_group_desc);
  struct ext2_group_desc* descs = malloc(arr_size);
  int i = 0;

  printf("arr_size = %d\n", arr_size);

  /*Now onto reading the group descriptor */
  /* seek to the first descriptor */
  /* read it in */
  for(i = 0; i < num_groups ; i++){
    lseek(fd, 
	  BASE_OFFSET + block_size + i*sizeof(struct ext2_group_desc), 
	  SEEK_SET);
    read(fd, descs+i, sizeof(struct ext2_group_desc));
  }

  return descs;
}

int get_root_inode(int fd,
		   struct ext2_super_block* super,
		   struct ext2_group_desc* group,
		   struct ext2_inode* root_inode){

  /* Read the root inode */
  read_inode(fd, super, group, 2, root_inode);

  return fd;
}