#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <linux/types.h>

struct ext4_super_block sb;
int block_size = 0;
int tree_depth = 0;
FILE *fp = NULL;


/*
 * Structure of the super block
 */
struct ext4_super_block {
/*00*/  __le32  s_inodes_count;         /* Inodes count */
        __le32  s_blocks_count;         /* Blocks count */
        __le32  s_r_blocks_count;       /* Reserved blocks count */
        __le32  s_free_blocks_count;    /* Free blocks count */
/*10*/  __le32  s_free_inodes_count;    /* Free inodes count */
        __le32  s_first_data_block;     /* First Data Block */
        __le32  s_log_block_size;       /* Block size */
        __le32  s_log_frag_size;        /* Fragment size */
/*20*/  __le32  s_blocks_per_group;     /* # Blocks per group */
        __le32  s_frags_per_group;      /* # Fragments per group */
        __le32  s_inodes_per_group;     /* # Inodes per group */
        __le32  s_mtime;                /* Mount time */
/*30*/  __le32  s_wtime;                /* Write time */
        __le16  s_mnt_count;            /* Mount count */
        __le16  s_max_mnt_count;        /* Maximal mount count */
        __le16  s_magic;                /* Magic signature */
        __le16  s_state;                /* File system state */
        __le16  s_errors;               /* Behaviour when detecting errors */
        __le16  s_minor_rev_level;      /* minor revision level */
/*40*/  __le32  s_lastcheck;            /* time of last check */
        __le32  s_checkinterval;        /* max. time between checks */
        __le32  s_creator_os;           /* OS */
        __le32  s_rev_level;            /* Revision level */
/*50*/  __le16  s_def_resuid;           /* Default uid for reserved blocks */
        __le16  s_def_resgid;           /* Default gid for reserved blocks */
        /*
         * These fields are for EXT4_DYNAMIC_REV superblocks only.
         *
         * Note: the difference between the compatible feature set and
         * the incompatible feature set is that if there is a bit set
         * in the incompatible feature set that the kernel doesn't
         * know about, it should refuse to mount the filesystem.
         *
         * e2fsck's requirements are more strict; if it doesn't know
         * about a feature in either the compatible or incompatible
         * feature set, it must abort and not try to meddle with
         * things it doesn't understand...
         */
        __le32  s_first_ino;            /* First non-reserved inode */
        __le16  s_inode_size;           /* size of inode structure */
        __le16  s_block_group_nr;       /* block group # of this superblock */
        __le32  s_feature_compat;       /* compatible feature set */
/*60*/  __le32  s_feature_incompat;     /* incompatible feature set */
        __le32  s_feature_ro_compat;    /* readonly-compatible feature set */
/*68*/  __u8    s_uuid[16];             /* 128-bit uuid for volume */
/*78*/  char    s_volume_name[16];      /* volume name */
/*88*/  char    s_last_mounted[64];     /* directory where last mounted */
/*C8*/  __le32  s_algorithm_usage_bitmap; /* For compression */
        /*
         * Performance hints.  Directory preallocation should only
         * happen if the EXT4_FEATURE_COMPAT_DIR_PREALLOC flag is on.
         */
        __u8    s_prealloc_blocks;      /* Nr of blocks to try to preallocate*/
        __u8    s_prealloc_dir_blocks;  /* Nr to preallocate for dirs */
        __le16  s_reserved_gdt_blocks;  /* Per group desc for online growth */
        /*
         * Journaling support valid if EXT4_FEATURE_COMPAT_HAS_JOURNAL set.
         */
/*D0*/  __u8    s_journal_uuid[16];     /* uuid of journal superblock */
/*E0*/  __le32  s_journal_inum;         /* inode number of journal file */
        __le32  s_journal_dev;          /* device number of journal file */
        __le32  s_last_orphan;          /* start of list of inodes to delete */
        __le32  s_hash_seed[4];         /* HTREE hash seed */
        __u8    s_def_hash_version;     /* Default hash version to use */
        __u8    s_reserved_char_pad;
        __le16  s_desc_size;            /* size of group descriptor */
/*100*/ __le32  s_default_mount_opts;   
        __le32  s_first_meta_bg;        /* First metablock block group */
        __le32  s_mkfs_time;            /* When the filesystem was created */
        __le32  s_jnl_blocks[17];       /* Backup of the journal inode */
        /* 64bit support valid if EXT4_FEATURE_COMPAT_64BIT */
/*150*/ __le32  s_blocks_count_hi;      /* Blocks count */
        __le32  s_r_blocks_count_hi;    /* Reserved blocks count */
        __le32  s_free_blocks_count_hi; /* Free blocks count */
        __u16   s_min_extra_isize;      /* All inodes have at least # bytes */
        __u16   s_want_extra_isize;     /* New inodes should reserve # bytes */
        __u32   s_flags;                /* Miscellaneous flags */
        __u16   s_raid_stride;          /* RAID stride */
        __u16   s_mmp_interval;         /* # seconds to wait in MMP checking */
        __u64   s_mmp_block;            /* Block for multi-mount protection */
        __u32   s_raid_stripe_width;    /* blocks on all data disks (N*stride)*/
        __u32   s_reserved[163];        /* Padding to the end of the block */
};

#define EXT4_MIN_BLOCK_SIZE             1024

/*
 * Structure of a blocks group descriptor
 */
struct ext4_group_desc
{
        __le32  bg_block_bitmap;                /* Blocks bitmap block */
        __le32  bg_inode_bitmap;                /* Inodes bitmap block */
        __le32  bg_inode_table;         /* Inodes table block */
        __le16  bg_free_blocks_count;   /* Free blocks count */
        __le16  bg_free_inodes_count;   /* Free inodes count */
        __le16  bg_used_dirs_count;     /* Directories count */
        __u16   bg_flags;
        __u32   bg_reserved[3];
        __le32  bg_block_bitmap_hi;     /* Blocks bitmap block MSB */
        __le32  bg_inode_bitmap_hi;     /* Inodes bitmap block MSB */
        __le32  bg_inode_table_hi;      /* Inodes table block MSB */
};

/*
 * Constants relative to the data blocks
 */
#define EXT4_NDIR_BLOCKS                12
#define EXT4_IND_BLOCK                  EXT4_NDIR_BLOCKS
#define EXT4_DIND_BLOCK                 (EXT4_IND_BLOCK + 1)
#define EXT4_TIND_BLOCK                 (EXT4_DIND_BLOCK + 1)
#define EXT4_N_BLOCKS                   (EXT4_TIND_BLOCK + 1)

/*
 * Structure of an inode on the disk
 */
struct ext4_inode {
        __le16  i_mode;         /* File mode */
        __le16  i_uid;          /* Low 16 bits of Owner Uid */
        __le32  i_size;         /* Size in bytes */
        __le32  i_atime;        /* Access time */
        __le32  i_ctime;        /* Inode Change time */
        __le32  i_mtime;        /* Modification time */
        __le32  i_dtime;        /* Deletion Time */
        __le16  i_gid;          /* Low 16 bits of Group Id */
        __le16  i_links_count;  /* Links count */
        __le32  i_blocks;       /* Blocks count */
        __le32  i_flags;        /* File flags */
        union { 
                struct {
                        __u32  l_i_reserved1;
                } linux1;
                struct {
                        __u32  h_i_translator;
                } hurd1;
                struct {
                        __u32  m_i_reserved1;
                } masix1;               
        } osd1;                         /* OS dependent 1 */
        __le32  i_block[EXT4_N_BLOCKS];/* Pointers to blocks */
        __le32  i_generation;   /* File version (for NFS) */
        __le32  i_file_acl;     /* File ACL */
        __le32  i_dir_acl;      /* Directory ACL */
        __le32  i_faddr;        /* Fragment address */
        union { 
                struct {
                        __u8    l_i_frag;       /* Fragment number */
                        __u8    l_i_fsize;      /* Fragment size */
                        __le16  l_i_file_acl_high;
                        __le16  l_i_uid_high;   /* these 2 fields */
                        __le16  l_i_gid_high;   /* were reserved2[0] */
                        __u32   l_i_reserved2;
                } linux2;
                struct {
                        __u8    h_i_frag;       /* Fragment number */
                        __u8    h_i_fsize;      /* Fragment size */
                        __u16   h_i_mode_high;
                        __u16   h_i_uid_high;
                        __u16   h_i_gid_high;
                        __u32   h_i_author;
                } hurd2;
                struct {
                        __u8    m_i_frag;       /* Fragment number */
                        __u8    m_i_fsize;      /* Fragment size */
                        __le16  m_i_file_acl_high;
                        __u32   m_i_reserved2[2];
                } masix2;               
        } osd2;                         /* OS dependent 2 */
        __le16  i_extra_isize;
        __le16  i_pad1;
        __le32  i_ctime_extra;  /* extra Change time      (nsec << 2 | epoch) */
        __le32  i_mtime_extra;  /* extra Modification time(nsec << 2 | epoch) */
        __le32  i_atime_extra;  /* extra Access time      (nsec << 2 | epoch) */
        __le32  i_crtime;       /* File Creation time */
        __le32  i_crtime_extra; /* extra FileCreationtime (nsec << 2 | epoch) */
};

/*      
 * Structure of a directory entry
 */     
#define EXT4_NAME_LEN 255
        
struct ext4_dir_entry {
        __le32  inode;                  /* Inode number */
        __le16  rec_len;                /* Directory entry length */
        __le16  name_len;               /* Name length */
        char    name[EXT4_NAME_LEN];    /* File name */
};      

/*      
 * The new version of the directory entry.  Since EXT4 structures are
 * stored in intel byte order, and the name_len field could never be
 * bigger than 255 chars, it's safe to reclaim the extra byte for the
 * file_type field.
 */
struct ext4_dir_entry_2 {
        __le32  inode;                  /* Inode number */
        __le16  rec_len;                /* Directory entry length */
        __u8    name_len;               /* Name length */
        __u8    file_type;
        char    name[EXT4_NAME_LEN];    /* File name */
};


/*
 * This is the extent on-disk structure.
 * It's used at the bottom of the tree.
 */
struct ext4_extent {
        __le32  ee_block;       /* first logical block extent covers */
        __le16  ee_len;         /* number of blocks covered by extent */
        __le16  ee_start_hi;    /* high 16 bits of physical block */
        __le32  ee_start;       /* low 32 bits of physical block */
};

/*
 * This is index on-disk structure.
 * It's used at all the levels except the bottom.
 */
struct ext4_extent_idx {
        __le32  ei_block;       /* index covers logical blocks from 'block' */
        __le32  ei_leaf;        /* pointer to the physical block of the next *
                                 * level. leaf or next index could be there */
        __le16  ei_leaf_hi;     /* high 16 bits of physical block */
        __u16   ei_unused;
};

/*
 * Each block (leaves and indexes), even inode-stored has header.
 */
struct ext4_extent_header {     
        __le16  eh_magic;       /* probably will support different formats */
        __le16  eh_entries;		/* number of valid entries */
        __le16  eh_max;         /* capacity of store in entries */
        __le16  eh_depth;       /* has tree real underlying blocks? */
        __le32  eh_generation;  /* generation of the tree */
};

#define EXT4_EXT_MAGIC          cpu_to_le16(0xf30a)


void usage()
{
  printf("list_extents [image file] [inode num]\n");
}

int IsExp(long long res, int e)
{
	long long i;

	while (i > e)
	{
		i = i / e;
	}

	if (i == e)
	{
		return 1;
	} 
		
	return 0;
}

int SBInBG(long long block)
{
	if ((block == 0) || (block == 1))
	{
		return 1;
	}

	if (IsExp(block, 3) || IsExp(block, 5) || IsExp(block, 7))
	{
		return 1;
	}

	return 0;
}

int PrintTree(struct ext4_extent_header *eh)
{
	struct ext4_extent ee;
	struct ext4_extent_idx ei;
	struct ext4_extent_header ceh;

	int i;
	long long block;
	char buffer[4096];
	char str[128];
	int j = 0;

	if (eh == NULL)
	{
		printf("error: null pointer to struct ext4_extent_header\n");
		exit(1);
	}
			
	while (j < tree_depth)
	{
		str[j]='-';
		j++;
	}
	str[j]='\0';

	if (eh->eh_depth == 0)
	{
		// leaf
		for (i = 1; i <= eh->eh_entries; i++)
		{
			memcpy(&ee, (struct ext4_extent *)eh + i, sizeof(struct ext4_extent));
			
			// print extents info

			block = (long long)((ee.ee_start_hi & 0xffff) << 32);
			block += ee.ee_start;
			printf("%s logical block: %d - %d, physical block: %lld - %lld\n", \
				str, ee.ee_block, ee.ee_block + ee.ee_len - 1, block, block + ee.ee_len - 1);
		}

		return 0;
	}
	else
	{
		// internal node

		if (eh->eh_depth > tree_depth)
		{
			tree_depth = eh->eh_depth;
		}

		if (eh->eh_depth == tree_depth)
		{
			// root node
			printf("root node: depth of the tree: %d, %d entries in root level\n", tree_depth, eh->eh_entries);
			;
		}

		for (i = 1; i <= eh->eh_entries; i++)
		{
			memcpy(&ei, (struct ext4_extent_idx *)eh + i, sizeof(struct ext4_extent_idx));
			// print idx info

			block = (long long)((ei.ei_leaf_hi & 0xffff) << 32);
			block += ei.ei_leaf;

			printf("%s idx: logical block: %d, block: %lld\n", str, ei.ei_block, block);

			fseek(fp, block * block_size, SEEK_SET);
			fread(buffer, sizeof(buffer), 1, fp);

			PrintTree((struct ext4_extent_header *)buffer);
		}

		return 0;
	}

}

int main(int argc, char **argv)
{
	struct ext4_inode inode;

	char *filename = NULL;
	long long inode_num = 0;
	long long block_group = 0;
	long long it_block = 0;

	if (argc < 3)
	{
		printf("Too few parameters!\n");
		usage();
		exit(1); 
	}

	filename = argv[1];
	inode_num  = atoll(argv[2]);

	fp = fopen(filename, "r"); 
	if (!fp)
	{
		printf("cannot open file: %s\n", filename);
		exit(1);
	}

	fseek(fp, 1024, SEEK_SET);

	fread(&sb, sizeof(struct ext4_super_block), 1, fp);
	block_size = EXT4_MIN_BLOCK_SIZE << sb.s_log_block_size;
	
	if (inode_num > sb.s_inodes_count)
	{
		printf("Invalid inode: %d\n", inode_num);
		exit(1);
	}

	block_group = (inode_num - 1) / sb.s_inodes_per_group;

	if (SBInBG(block_group))
	{
		// super block, block group descriptors and GDT blocks in this block group
		//          boot sector                  sb  gd  reserved gdt blocks      bbm  ibm
		it_block = (block_size > 1024 ? 0 : 1) + 1 + 1 + sb.s_reserved_gdt_blocks + 1 + 1;
	}
	else 
	{
		//        bbm  ibm
		it_block = 1 + 1;
	}

	it_block = block_group * sb.s_blocks_per_group + it_block;
	it_block += ((inode_num - 1) % sb.s_inodes_per_group) / (block_size / sb.s_inode_size);

	fseek(fp, block_size * it_block + (((inode_num - 1) % sb.s_inodes_per_group) % (block_size / sb.s_inode_size)) * sb.s_inode_size, SEEK_SET);

	fread(&inode, sb.s_inode_size, 1, fp);


	PrintTree((struct ext4_extent_header *)&(inode.i_block));

	fclose(fp);
}