#include <unistd.h>
#include <fcntl.h>
#include <string.h>
#include <errno.h>
#include <inttypes.h>
#include <malloc.h>

#define STDIN 0
#define STDOUT 1
#define STDERR 2

#define SECTOR_SIZE 512

#define MAX(a,b) ((a<b)?(b):(a))
#define die(a) _die(__FUNCTION__, __LINE__, a)

#define ATTR_READ_ONLY 0x01
#define ATTR_HIDDEN    0x02
#define ATTR_SYSTEM    0x04
#define ATTR_VOLUME_ID 0x08
#define ATTR_DIRECTORY 0x10
#define ATTR_ARCHIVE   0x20
#define ATTR_LONG_NAME (ATTR_READ_ONLY | ATTR_HIDDEN | ATTR_SYSTEM | \
  ATTR_VOLUME_ID)
#define ATTR_LONG_NAME_MASK (ATTR_READ_ONLY | ATTR_HIDDEN | ATTR_SYSTEM | \
  ATTR_VOLUME_ID | ATTR_DIRECTORY | ATTR_ARCHIVE)

int err = 0;

enum Fattype {
  FATunknown,
  FAT12,
  FAT16,
  FAT32
};

struct Bpb {
  uint8_t  BS_jmpBoot[3];    /* jump instruction to boot code */
  uint8_t  BS_OEMName[8];    /* "MSWIN4.1" */
  uint16_t BPB_BytsPerSec;   /* bytes per sector (512, 1k, 2k, 4k) */
  uint8_t  BPB_SecPerClus;   /* sectors per cluster (2^n, 0<=n<=7) */
  uint16_t BPB_RsvdSecCnt;   /* number of reserved sectors */
  uint8_t  BPB_NumFATs;      /* count of FATs on the volume (usually 2) */
  uint16_t BPB_RootEntCnt;   /* count of root directory entries (0 if FAT32) */
  uint16_t BPB_TotSec16;     /* total count of sectors (0 if FAT32) */
  uint8_t  BPB_Media;        /* media type, usally 0xf8 */
  uint16_t BPB_FATSz16;      /* sectors occupied by one fat (FAT12 / FAT16) */
  uint16_t BPB_SecPerTrk;    /* sectors per track for Int 0x13 */
  uint16_t BPB_NumHeads;     /* numbers of heads for Int 0x13 */
  uint32_t BPB_HiddSec;      /* count of sectors preceding the partition */
  uint32_t BPB_TotSec32;     /* total count of all sectors of the volume */
} __attribute__ ((packed));

struct Bpb16 {
  uint8_t  BS_DrvNum;        /* Int 0x13 drive number, eg. 0x80 */
  uint8_t  BS_Reserved1;     /* reserved for WinNT (usually 0) */
  uint8_t  BS_BootSig;       /* extended boot signature (0x29) */
  uint32_t BS_VolID;         /* volume serial number (date + time) */
  uint8_t  BS_VolLab[11];    /* volume label as stored in the root directory */
  uint8_t  BS_FilSysType[8]; /* informational! */
} __attribute__ ((packed));

struct Bpb32 {
  uint32_t BPB_FATSz32;      /* sectors occupied by one fat (FAT32) */
  uint16_t BPB_ExtFlags;     /* FAT mirrored? */
  uint16_t BPB_FSVer;        /* version number of FAT filesystem type */
  uint32_t BPB_RootClus;     /* cluster number of first cluster of root dir */
  uint16_t BPB_FSInfo;       /* sector number of FSINFO (usually 1) */
  uint16_t BPB_BkBootSec;    /* sector number of copy of boot sector */
  uint8_t  BPB_Reserved[12]; /* reserved for future use */

  uint8_t  BS_DrvNum;        /* Int 0x13 drive number, eg. 0x80 */
  uint8_t  BS_Reserved1;     /* reserved for WinNT (usually 0) */
  uint8_t  BS_BootSig;       /* extended boot signature (0x29) */
  uint32_t BS_VolID;         /* volume serial number (date + time) */
  uint8_t  BS_VolLab[11];    /* volume label as stored in the root directory */
  uint8_t  BS_FilSysType[8]; /* informational! */
} __attribute__ ((packed));

struct Dirent {
  uint8_t  DIR_Name[11];
  uint8_t  DIR_Attr;
  uint8_t  DIR_NTRes;
  uint8_t  DIR_CrtTimeTenth;
  uint16_t DIR_CrtTime;
  uint16_t DIR_CrtDate;
  uint16_t DIR_LstAccDate;
  uint16_t DIR_FstClusHI;
  uint16_t DIR_WrtTime;
  uint16_t DIR_WrtDate;
  uint16_t DIR_FstClusLO;
  uint32_t DIR_FileSize;
} __attribute__ ((packed));

struct Ldirent {
  uint8_t  LDIR_Ord;
  uint8_t  LDIR_Name1[10];
  uint8_t  LDIR_Attr;
  uint8_t  LDIR_Type;
  uint8_t  LDIR_Chksum;
  uint8_t  LDIR_Name2[12];
  uint16_t LDIR_FstClusLO;
  uint8_t  LDIR_Name3[4];
} __attribute__ ((packed));

void _write (int fd, char *msg)
{
  if (msg) write(fd, msg, strlen(msg));
  else write(fd, "[null]", 6);
}

void write1 (char *msg)
{
  if (msg) _write(STDOUT, msg);
}

void write2 (char *msg)
{
  if (msg) _write(STDERR, msg);
}

char *ultoa (uint64_t i)
{
  static char ret[4096];
  static uint64_t itmp;
  static int len;

  len = 0;
  itmp = i;
  do {
    ++len;
    itmp /= 10;
  } while (itmp);
  ret[len] = '\0';
  for (;;) {
    ret[--len] = '0' + i % 10;
    i /= 10;
    if (!len) break;
  }
  return &ret[0];
}

void _die (char *func, int line, char *why)
{
  write2(func);
  write2(" (");
  write2(ultoa(line));
  write2("): ");
  write2(why);
  write2(".\n");
  exit(1);
}

void warn (char *warning)
{
  ++err;
  write1("warning: ");
  write1(warning);
  write1(".\n");
}

void fatal (char *warning)
{
  ++err;
  write1("Fatal: ");
  write1(warning);
  write1(".\n");
}

enum Fattype guess_fattype (struct Bpb *bpb, struct Bpb16 *bpb16,
                            struct Bpb32 *bpb32)
{
  uint64_t clusters, rootdirsectors;
  uint32_t totalsectors, fatsize;
  enum Fattype fat = FAT32;

  write1("=== guessing FAT type ===\nHmm, looks like a ");

  totalsectors = ((bpb->BPB_TotSec16)?(bpb->BPB_TotSec16):(bpb->BPB_TotSec32));

  fatsize = ((bpb->BPB_FATSz16)?(bpb->BPB_FATSz16):(bpb32->BPB_FATSz32));

  rootdirsectors = (bpb->BPB_RootEntCnt * 32 + bpb->BPB_BytsPerSec - 1) / \
                   bpb->BPB_BytsPerSec;

  clusters = (totalsectors - bpb->BPB_RsvdSecCnt - bpb->BPB_NumFATs * fatsize -\
              rootdirsectors) / bpb->BPB_SecPerClus;

  if (clusters < 4085) fat = FAT12;
  if (clusters < 65525) fat = FAT16;

entry:
  err = 0;
  switch (fat) {
    case FATunknown:
    case FAT32:
      write1("FAT32\n");
      if (bpb->BPB_RootEntCnt)       warn("BPB_RootEntCnt non zero");
      if (bpb->BPB_TotSec16)         warn("BPB_TotSec16 non zero");
      if (bpb->BPB_FATSz16)          warn("BPB_FATSz16 non zero");
      if (!bpb->BPB_TotSec32)        warn("BPB_TotSec32 zero");
      if (!bpb32->BPB_FATSz32)       warn("BPB_FATSz32 zero");
      if (bpb32->BPB_FSVer)          warn("BPB_FSVer non zero");
      if (bpb32->BPB_RootClus != 2)  warn("BPB_RootClus not 2");
      if (bpb32->BPB_FSInfo != 1)    warn("BPB_FSInfo not 1");
      if (bpb32->BPB_BkBootSec != 6) warn("BPB_BkBootSec not 6");
      if (bpb32->BS_Reserved1)       warn("BS_Reserved1 non zero");
      write1("BS_VolLab: "); write(STDOUT, bpb32->BS_VolLab, 11); write1("\n");
      if (memcmp(&bpb32->BS_FilSysType[0], "FAT32   ", 8))
        warn("BS_FilSysType not \"FAT32   \"");
      if (err) {
        warn("Too many errors on this FAT32 volume, trying again");
        if (fat != FATunknown) {
          fat = FATunknown;
          goto entry;
        }
      }
      if (fat != FATunknown) break;
    case FAT16:
      write1("FAT16\n");
      if (bpb->BPB_RsvdSecCnt != 1) warn("BPB_RsvdSecCnt not 1");
      if (!bpb->BPB_RootEntCnt)     warn("BPB_RootEntCnt zero");
      if (!bpb->BPB_FATSz16)        warn("BPB_FATSz16 zero");
      if (bpb16->BS_Reserved1)      warn("BS_Reserved1 non zero");
      write1("BS_VolLab: "); write(STDOUT, bpb16->BS_VolLab, 11); write1("\n");
      if (memcmp(&bpb16->BS_FilSysType[0], "FAT16 ", 8))
        warn("BS_FilSysType not \"FAT16   \"");
      if (err) {
        warn("Too many errors on this FAT16 volume, trying again");
        if (fat != FATunknown) {
          fat = FATunknown;
          goto entry;
        }
      }
      if (fat != FATunknown) break;
    case FAT12:
      write1("FAT12\n");
      if (bpb->BPB_RsvdSecCnt != 1) warn("BPB_RsvdSecCnt not 1");
      if (!bpb->BPB_RootEntCnt)     warn("BPB_RootEntCnt zero");
      if (!bpb->BPB_FATSz16)        warn("BPB_FATSz16 zero");
      if (bpb16->BS_Reserved1)      warn("BS_Reserved1 non zero");
      write1("BS_VolLab: "); write(STDOUT, bpb16->BS_VolLab, 11); write1("\n");
      if (memcmp(&bpb16->BS_FilSysType[0], "FAT12 ", 8))
        warn("BS_FilSysType not \"FAT12   \"");
      if (err) {
        warn("Too many errors on this FAT12 volume, trying again");
        if (fat != FATunknown) {
          fat = FATunknown;
          goto entry;
        }
      }
      if (fat != FATunknown) break;
      die("Could not determine FAT type");
  }

  write1("looks fine\n");
  return fat;
}

void dumpbpb (struct Bpb *bpb, struct Bpb16 *bpb16, struct Bpb32 *bpb32,
              enum Fattype fat)
{
  if (!bpb) die("bpb = NULL");
  if (!bpb16) die("bpb16 = NULL");
  if (!bpb32) die("bpb32 = NULL");

  write1("=== dumping ===\n");
  write1("BS_jmpBoot: ");   
  write1(ultoa((uint32_t)(bpb->BS_jmpBoot[0] << 16) + \
                         (bpb->BS_jmpBoot[1] << 8) + \
                          bpb->BS_jmpBoot[2]));
  write1("\nBS_OEMName: ");
  write(STDOUT, &bpb->BS_OEMName[0], 8);
  write1("\nBPB_BytsPerSec: ");
  write1(ultoa(bpb->BPB_BytsPerSec));
  write1("\nBPB_SecPerClus: ");
  write1(ultoa(bpb->BPB_SecPerClus));
  write1("\nBPB_RsvdSecCnt: ");
  write1(ultoa(bpb->BPB_RsvdSecCnt));
  write1("\nBPB_NumFATs: ");
  write1(ultoa(bpb->BPB_NumFATs));
  write1("\nBPB_RootEntCnt: ");
  write1(ultoa(bpb->BPB_RootEntCnt));
  write1("\nBPB_TotSec16: ");
  write1(ultoa(bpb->BPB_TotSec16));
  write1("\nBPB_Media: ");
  write1(ultoa(bpb->BPB_Media));
  write1("\nBPB_FATSz16: ");
  write1(ultoa(bpb->BPB_FATSz16));
  write1("\nBPB_SecPerTrk: ");
  write1(ultoa(bpb->BPB_SecPerTrk));
  write1("\nBPB_NumHeads: ");
  write1(ultoa(bpb->BPB_NumHeads));
  write1("\nBPB_HiddSec: ");
  write1(ultoa(bpb->BPB_HiddSec));
  write1("\nBPB_TotSec32: ");
  write1(ultoa(bpb->BPB_TotSec32));

  if (fat == FAT32) {
    write1("\nFAT32 extensions:\n BPB_FATSz32: ");
    write1(ultoa(bpb32->BPB_FATSz32));
    write1("\n BPB_ExtFlags: ");
    write1(ultoa(bpb32->BPB_ExtFlags));
    write1("\n BPB_FSVer: ");
    write1(ultoa(bpb32->BPB_FSVer));
    write1("\n BPB_RootClus: ");
    write1(ultoa(bpb32->BPB_RootClus));
    write1("\n BPB_FSInfo: ");
    write1(ultoa(bpb32->BPB_FSInfo));
    write1("\n BPB_BkBootSec: ");
    write1(ultoa(bpb32->BPB_BkBootSec));
    write1("\n BPB_Reserved: ");
    write(STDOUT, &bpb32->BPB_Reserved[0], 12);
  }

  write1("\nBS_DrvNum: ");
  write1(ultoa(bpb16->BS_DrvNum));
  write1("\nBS_Reserved1: ");
  write1(ultoa(bpb16->BS_Reserved1));
  write1("\nBS_BootSig: ");
  write1(ultoa(bpb16->BS_BootSig));
  write1("\nBS_VolID: ");
  write1(ultoa(bpb16->BS_VolID));
  write1("\nBS_VolLab: ");
  write(STDOUT, &bpb16->BS_VolLab[0], 11);
  write1("\nBS_FilSysType: ");
  write(STDOUT, &bpb16->BS_FilSysType[0], 8);
  write1("\n");
}

int valid_exp2 (double d, int maxexpo)
{
  for (; maxexpo > -1; --maxexpo) if (d == (1 << maxexpo)) return 1;
  return 0;
}

void checksector (char *sector)
{
  struct Bpb *bpb = (struct Bpb*) sector;

  if (!sector) die("sector = NULL");

  write1("=== doing some overall checks ===\n");

  err = 0;

  if (!((bpb->BS_jmpBoot[0] == 0xeb) && (bpb->BS_jmpBoot[2] == 0x90)) &&
      !(bpb->BS_jmpBoot[0] == 0xe9))
    warn("BS_jmpBoot is malformed");

  if (memcmp(&bpb->BS_OEMName, "MSWIN4.1", 8))
    warn("BS_OEMName not MSWIN4.1");

  if (!valid_exp2(bpb->BPB_BytsPerSec / 512, 3))
    fatal("BPB_BytsPerSec invalid");

  if (!valid_exp2(bpb->BPB_SecPerClus, 7))
    fatal("BPB_SecPerClus invalid");

  if (!bpb->BPB_RsvdSecCnt)
    fatal("BPB_RsvdSecCnt is zero");

  if (bpb->BPB_NumFATs != 2)
    warn("BPB_NumFATs is not set to 2");

  if ((bpb->BPB_TotSec16) && (bpb->BPB_TotSec32))
    warn("BPB_TotSec16 & BPB_TotSec32 are both larger than 0");
  if ((!bpb->BPB_TotSec16) && (!bpb->BPB_TotSec32))
    warn("BPB_TotSec16 & BPB_TotSec32 are both 0");

  if (((uint8_t)(*(sector + SECTOR_SIZE - 2)) != 0x55) || \
      ((uint8_t)(*(sector + SECTOR_SIZE - 1)) != 0xAA))
    warn("Magic boot signature not found");

  if (!err) write1("looks fine\n");
}

uint32_t fatunknown_entry (int volume, struct Bpb *bpb, struct Bpb16 *bpb16,
                           struct Bpb32 *bpb32, uint32_t cluster)
{
  return 0;
}

uint32_t fat12_entry (int volume, struct Bpb *bpb, struct Bpb16 *bpb16,
                      struct Bpb32 *bpb32, uint32_t cluster)
{
  return 0;
}

uint32_t fat16_entry (int volume, struct Bpb *bpb, struct Bpb16 *bpb16,
                      struct Bpb32 *bpb32, uint32_t cluster)
{
  static char tmp[2];

  if (lseek64(volume, bpb->BPB_RsvdSecCnt * bpb->BPB_BytsPerSec + 2 * cluster,
            SEEK_SET) == (off_t)(-1))
    die(strerror(errno));
  read(volume, &tmp[0], 2);
  return *((uint32_t*)(&tmp[0]));
}

uint32_t fat32_entry (int volume, struct Bpb *bpb, struct Bpb16 *bpb16,
                      struct Bpb32 *bpb32, uint32_t cluster)
{
  static char tmp[4];

  if (lseek64(volume, bpb->BPB_RsvdSecCnt * bpb->BPB_BytsPerSec + 4 * cluster,
            SEEK_SET) == (off_t)(-1))
    die(strerror(errno));
  read(volume, &tmp[0], 4);
  return *((uint32_t*)(&tmp[0])) & 0x0FFFFFFF;
}

int validshortname (uint8_t *c, int len)
{
  for (; len; --len, ++c)
    if (!(((*c>='a') && (*c<='z')) ||
         ((*c>='A') && (*c<='Z')) ||
         ((*c>='0') && (*c<='9')) ||
//         (*c<0) ||
         (*c==0) || (*c==0xE5) || (*c==0x05) ||
 (*c=='$') || (*c=='%') || (*c=='\'') || (*c=='-') ||
         (*c=='_') || (*c=='@') || (*c=='~') || (*c=='`') || (*c=='!') ||
         (*c=='(') || (*c==')') || (*c=='{') || (*c=='}') || (*c=='^') ||
         (*c=='#') || (*c=='&'))) return 0;
  return 1;
}

struct {
  uint32_t (*fat_entry)(int volume, struct Bpb *bpb, struct Bpb16 *bpb16,
                        struct Bpb32 *bpb32, uint32_t cluster);
} fat_entries[] = {
  { fatunknown_entry },
  { fat12_entry },
  { fat16_entry },
  { fat32_entry }
};

void dumpvolume (int volume, struct Bpb *bpb, struct Bpb16 *bpb16,
                 struct Bpb32 *bpb32, uint32_t selfclus, uint32_t parentclus,
                 uint32_t (*fat_entry)(int volume, struct Bpb *bpb,
                                       struct Bpb16 *bpb16, struct Bpb32 *bpb32,
                                       uint32_t cluster), char *name)
{
  char buf[sizeof(struct Dirent)], lname[4096], *c, *p;
  uint64_t pos;
  uint32_t childclus, clusoff = 0, cluster = selfclus;
  int i;
  struct Dirent *de = (struct Dirent*) &buf[0];
  struct Ldirent *lde = (struct Ldirent*) &buf[0];

  for (;;) {
    pos = bpb->BPB_RsvdSecCnt + bpb32->BPB_FATSz32 * bpb->BPB_NumFATs;
    pos += bpb->BPB_SecPerClus * (cluster - 2);
    pos *= bpb->BPB_BytsPerSec;
    pos += clusoff;
    if (lseek64(volume, pos, SEEK_SET) != pos) die(strerror(errno));
    lname[0] = 0;
    for (;;) {
      read(volume, de, sizeof(struct Dirent));
      if ((de->DIR_Attr & ATTR_LONG_NAME_MASK) != ATTR_LONG_NAME) break;
      clusoff += sizeof(struct Dirent);

      memmove(&lname[13], &lname[0], 4096 - 13);
      for (i=0; i<5; i++) lname[i] = lde->LDIR_Name1[i*2];
      for (i=0; i<6; i++) lname[i+5] = lde->LDIR_Name2[i*2];
      for (i=0; i<2; i++) lname[i+11] = lde->LDIR_Name3[i*2];
    }
    childclus = (de->DIR_FstClusHI << 16) | de->DIR_FstClusLO;
    if (!childclus) goto nextentry; /* null file */
    write(STDOUT, &de->DIR_Name[0], 11);
    write1(" ");
    write1(&lname[0]);
    if ((de->DIR_Name[0] == 0) || (de->DIR_Name[0] == 0xE5)) {
      write1(" DELETED");
      if (childclus) write1(" CHANCE");
      if (strlen(lname)) { write1(" AUTO_"); write1(lname); }
    }
    if (de->DIR_Attr & ATTR_READ_ONLY) write1(" READ_ONLY");
    if (de->DIR_Attr & ATTR_HIDDEN)    write1(" HIDDEN");
    if (de->DIR_Attr & ATTR_SYSTEM)    write1(" SYSTEM");
    if (de->DIR_Attr & ATTR_VOLUME_ID) write1(" VOLUME_ID");
    if (de->DIR_Attr & ATTR_ARCHIVE)   write1(" ARCHIVE");
    if (de->DIR_Attr & ATTR_DIRECTORY) {
      write1(" DIRECTORY");

      if ((childclus != selfclus) && (childclus != parentclus)) {
        c = (char*) malloc(strlen(name) + 13);
        strcpy(c, name);
        strcat(c, "\\");
        strncat(c, &de->DIR_Name[0], 11);
        *(c + strlen(name) + 12) = 0;
        if ((p=strchr(c, ' '))) *p = 0;
        write1(" ");
        write1(ultoa(parentclus));
        write1(" ");
        write1(ultoa(cluster));
        write1(" ");
        write1(ultoa(childclus));
        write1(" ");
        write1(name);
        write1(" => ");
        write(STDOUT, de->DIR_Name, 11);
        write1("\n");
//        dumpvolume(volume, bpb, bpb16, bpb32, childclus, startclus, fat_entry, c);
        free(c);
      }
    }
    else write1("\n");
nextentry:
    clusoff += sizeof(struct Dirent);
    if (clusoff >= bpb->BPB_BytsPerSec * bpb->BPB_SecPerClus) {
      clusoff %= bpb->BPB_BytsPerSec * bpb->BPB_SecPerClus;
      cluster = fat_entry(volume, bpb, bpb16, bpb32, cluster);
      if (cluster >= 0x0FFFFFF8) return;
      if (cluster == 0) return;
    }
  }
}

int main (int argc, char **argv)
{
  char buf[SECTOR_SIZE];
  struct Bpb *bpb = (struct Bpb*) &buf[0];
  struct Bpb16 *bpb16 = (struct Bpb16*) &buf[sizeof(struct Bpb)];
  struct Bpb32 *bpb32 = (struct Bpb32*) &buf[sizeof(struct Bpb)];
  int fh;
  enum Fattype fat;

  if (argc < 2) die("usage: fat <FAT volume>");
  fh = open64(argv[1], O_RDONLY);
  if (fh < 0) die(strerror(errno));
  read(fh, bpb, SECTOR_SIZE);

  checksector(&buf[0]);

  fat = guess_fattype(bpb, bpb16, bpb32);

  dumpbpb(bpb, bpb16, bpb32, fat);

  write1("=== dump it ===\n");
  dumpvolume(fh, bpb, bpb16, bpb32, bpb32->BPB_RootClus, 0, fat_entries[fat].fat_entry, "");

#if 0
{
#define BLA (sizeof(struct Dirent) * 65536)
  struct Dirent de[65535];
  uint64_t i, bah, buh, bla = 0;

  if (lseek64(fh, 0, SEEK_SET) != 0) die(strerror(errno));
  for (;;) {
    bla = read(fh, &de[0], BLA);
    for (i = 0; i < bla/sizeof(struct Dirent); ++i) {
      if (!(de[i].DIR_Attr & (ATTR_VOLUME_ID | ATTR_DIRECTORY)) &&
          (validshortname(de[i].DIR_Name, 11))) {
        buh = (de[i].DIR_FstClusHI << 16) | de[i].DIR_FstClusLO;
        write(1, de[i].DIR_Name, 11);
        write1(" ");
        write1(ultoa(buh));
        write1(" ");
        bah = lseek64(fh, 0, SEEK_CUR);
        write1(ultoa(fat32_entry(fh, bpb, bpb16, bpb32, buh)));
        if (lseek64(fh, bah, SEEK_SET) != bah) die(strerror(errno));
        write1("\n");
      }
      if (bla != BLA) break;
    }
  }
}
#endif

  close(fh);

  return 0;
}