//
// chk -- Checksum all files in directory, recursively.
//
// - Default display is mod time, attributes, checksum, size, file name.
// - Ignore system files to avoid corrupt sectors or open/read errors.
// - Tool fails on some unusual unicode directory or file names.
//
// 02-Sep-2011 Tom Van Baak (tvb) www.LeapSecond.com/tools
//

#include <direct.h>
#include <io.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/stat.h>
#include <time.h>

typedef unsigned long ulong;
char *get_time_str (time_t t, int utc);
char *get_decimal_str (ulong n);
int get_checksum (char *filename, ulong *crc);

// Collect statistics.
struct {
    ulong files, dirs, errors, system, empty;
    double bytes;   // max 2^53 (2^23 GB)
} total;

// Program options.
#define SHOW_DEFAULT "tacsn+"   // default output
#define SHOW_ALL "ztacsnf+i"     // all options (see below)
char *show_list = SHOW_DEFAULT;
int depth_limit = -1;
ulong mega_limit = 0;
char *a0;
FILE *STDERR = stderr;

// Called once for each file found.
void do_file (struct _finddata_t *fd, char *fullpath)
{
    char buf[1000], *p;
    ulong crc;
    int integer = 0;
    int len = 0;

    // (optional) Only look at large files.
    if (mega_limit != 0 && (fd->size >> 20) < mega_limit) {
        return;
    }

    // Output user-specified columns in order requested.
    for (p = show_list; *p != '\0'; p += 1) {
        char *tab = len ? " " : "";

        switch (*p) {
        case 't' :  // mod time (local)
            len += sprintf(&buf[len], "%s%s", tab, get_time_str(fd->time_write, 0));
            break;

        case 'z' :  // mod time (zulu, UTC)
            len += sprintf(&buf[len], "%s%s", tab, get_time_str(fd->time_write, 1));
            break;

        case 'a' :  // attributes
            len += sprintf(&buf[len], "%s%c%c%c%c%c", tab,
                           (fd->attrib & _A_RDONLY) ? 'R' : '-',
                           (fd->attrib & _A_HIDDEN) ? 'H' : '-',
                           (fd->attrib & _A_SYSTEM) ? 'S' : '-',
                           (fd->attrib & _A_SUBDIR) ? 'D' : '-',
                           (fd->attrib & _A_ARCH) ?   'A' : '-');
            break;

        case 'c' :  // checksum
            if (fd->attrib & _A_SYSTEM) {
                total.system += 1;
                len += sprintf(&buf[len], "%s%s", tab, "ssssssss");

            } else {
                if (0 == fd->size) {
                    total.empty += 1; // count zero length files
                }
                if (!get_checksum(fd->name, &crc)) {
                    fprintf(STDERR, "%s: crc failed: %s\n", a0, fullpath);
                    total.errors += 1;
                    len += sprintf(&buf[len], "%s%s", tab, "eeeeeeee");
                } else {
                    if (integer) {
                        len += sprintf(&buf[len], "%s%lu", tab, crc);
                    } else {
                        len += sprintf(&buf[len], "%s%.8lx", tab, crc);
                    }
                }
            }
            break;

        case 's' :  // size
            if (integer) {
                len += sprintf(&buf[len], "%s%ld", tab, fd->size);
            } else {
                len += sprintf(&buf[len], "%s%13s", tab, get_decimal_str(fd->size));
            }
            break;

        case 'n' :  // name (full pathname)
            len += sprintf(&buf[len], "%s%s", tab, fullpath);
            break;

        case 'f' :  // file name only (no base directory)
            len += sprintf(&buf[len], "%s%s", tab, fd->name);
            break;

        case 'i' :  // plain integer values
            integer = 1;
            break;

        case '+' :  // accumulate totals, show summary at end
            total.bytes += (double) fd->size;
            break;

        default :
            fprintf(stderr, "%s: letter `%c' in \"%s\" unknown; all (%s), default (%s)\n",
                    a0, *p, show_list, SHOW_ALL, SHOW_DEFAULT);
            exit(1);
        }
    }
    if (len) {
        printf("%s\n", buf);
    }
}

#define EXCLUDE_MAX 10
int exclude_count;
char *exclude_list[EXCLUDE_MAX];

void exclude_add (char *path)
{
    if (exclude_count < EXCLUDE_MAX) {
        exclude_list[exclude_count] = path;
        exclude_count += 1;
    }
}

// Avoid certain directories.
int exclude (char *path)
{
    int i;
    for (i = 0; i < exclude_count; i += 1) {
        if (strcmp(exclude_list[i], path) == 0) {
            return 1;
        }
    }
    return 0;
}

// Combine parent directory with file names.
char *make_fullpath (char *fullpath, char *dir, char *file)
{
    if (strlen(dir) == 0) {
        sprintf(fullpath, "%s", file);

    } else if ('\\' == dir[strlen(dir) - 1]) {
        sprintf(fullpath, "%s%s", dir, file);

    } else {
        sprintf(fullpath, "%s\\%s", dir, file);
    }
    return fullpath;
}

// Call-back function to sort directory entries alphabetically.
int fd_cmp (const struct _finddata_t **a, const struct _finddata_t **b)
{
    // return strcmp((*a)->name, (*b)->name);
    return _stricmp((*a)->name, (*b)->name);
}

// Called once for each directory found.
void do_dir (char *basepath, char *target, int level)
{
    long fh, n, n_max, i;
    struct _finddata_t fd;
    struct _finddata_t **fdlist;
    char fullpath[1000];

    // Phase 1 - gather all names in current directory.

    fh = _findfirst(target, &fd);
    if (-1 == fh) {
        fprintf(STDERR, "%s: not found or empty: %s\n", a0, basepath);
        total.errors += 1;
        return;
    }
    n_max = 100;
    if (NULL == (fdlist = malloc(n_max * sizeof fdlist[0]))) {
        _findclose(fh);
        fprintf(STDERR, "%s: no memory\n", a0);
        total.errors += 1;
        return;
    }
    n = 0;
    do {
        if (strcmp(fd.name, ".") != 0 && strcmp(fd.name, "..") != 0) {
            if (n == n_max) {
                n_max *= 2;
                if (NULL == (fdlist = realloc(fdlist, n_max * sizeof fdlist[0]))) {
                    fprintf(STDERR, "%s: no memory\n", a0);
                    total.errors += 1;
                    break;
                }
            }
            // Make copy of entire _finddata_t structure.
            if (NULL == (fdlist[n] = malloc(sizeof **fdlist))) {
                fprintf(STDERR, "%s: no memory\n", a0);
                total.errors += 1;
                break;
            }
            memcpy(fdlist[n], &fd, sizeof **fdlist);
            n += 1;
        }
    } while (_findnext(fh, &fd) != -1) ;
    _findclose(fh);

    // Phase 2 - sort names alphabetically.

    qsort(fdlist, n, sizeof fdlist[0], fd_cmp);

    // Phase 3 - process files, if any.

    for (i = 0; i < n; i += 1) {
        struct _finddata_t *fdp = fdlist[i];
        if (!(fdp->attrib & _A_SUBDIR)) {
            make_fullpath(fullpath, basepath, fdp->name);
            do_file(fdp, fullpath);
            total.files += 1;
        } else {
            // do_file(fdp, fullpath); // show directory entry
        }
    }

    // Phase 4 - descend into subdirectories, if any.

    if (depth_limit == -1 || level < depth_limit) {
        for (i = 0; i < n; i += 1) {
            struct _finddata_t *fdp = fdlist[i];
            if (fdp->attrib & _A_SUBDIR) {
                make_fullpath(fullpath, basepath, fdp->name);
                if (exclude(fullpath)) {
                    fprintf(STDERR, "%s: exclude: %s\n", a0, fullpath);
                    total.errors += 1;
                    continue;
                }
                if (_chdir(fdp->name)) {
                    fprintf(STDERR, "%s: unreadable: %s\n", a0, fullpath);
                    total.errors += 1;
                } else {
                    do_dir(fullpath, "*", level + 1);
                    total.dirs += 1;
                    if (_chdir("..")) {
                        fprintf(STDERR, "%s: chdir(..) failed; trouble ahead\n", a0);
                        total.errors += 1;
                    }
                }
            }
        }
    }

    // Clean up.
    for (i = 0; i < n; i += 1) {
        free(fdlist[i]);
    }
    free(fdlist);
}

// Display total kB MB GB as scientific (1e3) rather than binary (2^10) bytes.
void summary (void)
{
    if (total.bytes != 0 || total.errors != 0) {
        printf("%s files", get_decimal_str(total.files));
        printf(", %s dirs", get_decimal_str(total.dirs));
        printf(", %.3lf kB", total.bytes / 1e3);
        printf(", %.3lf MB", total.bytes / 1e6);
        printf(", %.3lf GB", total.bytes / 1e9);
        if (total.empty) {
            printf(", %lu empty", total.empty);
        }
        if (total.system) {
            printf(", %lu system", total.system);
        }
        if (total.errors) {
            printf(", %lu errors", total.errors);
        }
        printf("\n");
    }
}

char usage[] =
  "Usage: %s [options] [path]\n"
  "\n"
  "Options:\n"
  "  /t     -- show file mod time\n"
  "  /z     -- show file mod time (zulu, UTC)\n"
  "  /a     -- show file attributes\n"
  "  /s     -- show file size\n"
  "  /c     -- show file checksum\n"
  "  /n     -- show full pathname\n"
  "  /f     -- show filename only\n"
  "  /+     -- accumlate soze totals\n"
  "  /i     -- plain integer size or checksum\n"
  "  /<n>   -- limit subdirectory depth to <n> levels\n"
  "\n"
  "Examples:\n"
  "  chk /tasn      (recursive file list)\n"
  "  chk /tacsn     (recursive file checksums)\n"
  "  chk /0         (current directory only)\n"
  ;

// Parse options and handle file, directory, or no arguments.
int main (int argc, char *argv[])
{
    char *p;

    a0 = argv[0];
    // Get user options.
    while (argc > 1 && argv[1][0] == '/') {
        char *slash = argv[1];
        char *colon = strchr(slash, ':'); // may be NULL

        if (strncmp(slash, "/X:", 3) == 0) {
            exclude_add(colon + 1);
        } else

        if (strcmp(slash, "/M") == 0) {
            mega_limit = 1;
        } else

        if (strncmp(slash, "/M:", 3) == 0) {
            mega_limit = atol(colon + 1);
        } else

        if (strcmp(slash, "/?") == 0) {
            fprintf(stderr, usage, a0);
            exit(0);
        } else

        if (slash[1] >= '0' && slash[1] <= '9') {
            // User-specified directory depth limit.
            depth_limit = atoi(slash + 1);
        } else

        if (strlen(slash + 1) == strspn(slash + 1, SHOW_ALL)) {
            // User-specified file display fields.
            show_list = slash + 1;
        } else
        {
            fprintf(stderr, "%s: unknown option: %s\n", a0, argv[1]);
            exit(1);
        }
        argc -= 1;
        argv += 1;
    }

    // If $STDERR defined write error messages to that file.
    if ((p = getenv("STDERR")) != NULL) {
        STDERR = fopen(p, "a");
        fprintf(stderr, "%s: STDERR = %s\n", a0, p);
    }

    if (argc == 1) {
        // Run chk on current directory.
        do_dir("", "*", 0);

    } else {
        for (; argc > 1; argc -=1, argv += 1) {
            char *path = argv[1];
            struct _stat st;

            if (_stat(path, &st)) {
                fprintf(stderr, "%s: %s not found\n", a0, path);
                continue;
            }
            if (st.st_mode & _S_IFDIR) {
                if (_chdir(path)) {
                    fprintf(stderr, "%s: %s directory not readable\n", a0, path);
                    continue;
                }
                // Run chk on given directory.
                do_dir(path, "*", 0);

            } else {
                if (NULL == (p = strrchr(path, '\\'))) {
                    // Run chk on one file in current directory.
                    do_dir("", path, 0);

                } else {
                    *p = '\0';
                    if (_chdir(path)) {
                        fprintf(stderr, "%s: %s directory not readable\n", a0, path);
                        continue;
                    }
                    // Run chk on one file in given directory.
                    do_dir(path, p + 1, 0);
                }
            }
        }
    }
    if (total.files > 1) {
        summary();
    }
    if (STDERR != stderr) {
        fclose(STDERR);
    }
    return 0;
}

// Display date and time (using - for UTC and / for local).
char *get_time_str (time_t t, int utc)
{
    static char s[100]; // STATIC
    static struct tm tm0 = { 0, 0, 0, 0, -1, -1900 };
    struct tm *tm = utc ? gmtime(&t) : localtime(&t);

    if (NULL == tm) {
        tm = &tm0;
    }
    sprintf(s, "%.4d%c%.2d%c%.2d%c%.2d:%.2d:%.2d",
           tm->tm_year + 1900,
           utc ? '-' : '/',
           tm->tm_mon + 1,
           utc ? '-' : '/',
           tm->tm_mday,
           ' ',
           tm->tm_hour,
           tm->tm_min,
           tm->tm_sec);
    return s; // STATIC
}

// Display decimal numbers with thousands separators.
char *get_decimal_str (ulong n)
{
    ulong d[4], M = 1000;
    static char s[100]; // STATIC

    // Here kilo units are 10^3 (engineering k) not 2^10 (computer K).
    d[3] = n / (M*M*M) % M;
    d[2] = n /   (M*M) % M;
    d[1] = n /      M  % M;
    d[0] = n           % M;

    if (d[3]) {
        sprintf(s, "%ld,%.3ld,%.3ld,%.3ld", d[3], d[2], d[1], d[0]);
    } else if (d[2]) {
        sprintf(s, "%ld,%.3ld,%.3ld", d[2], d[1], d[0]);
    } else if (d[1]) {
        sprintf(s, "%ld,%.3ld", d[1], d[0]);
    } else {
        sprintf(s, "%ld", d[0]);
    }
    return s; // STATIC
}

// Fast crc32 look-up table (triangle version).
ulong crctab[] = {
  0x00000000,
  0x77073096, 0xee0e612c,
  0x990951ba, 0x076dc419, 0x706af48f,
  0xe963a535, 0x9e6495a3, 0x0edb8832, 0x79dcb8a4,
  0xe0d5e91e, 0x97d2d988, 0x09b64c2b, 0x7eb17cbd, 0xe7b82d07,
  0x90bf1d91, 0x1db71064, 0x6ab020f2, 0xf3b97148, 0x84be41de, 0x1adad47d,
  0x6ddde4eb, 0xf4d4b551, 0x83d385c7, 0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec,
  0x14015c4f, 0x63066cd9, 0xfa0f3d63, 0x8d080df5, 0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172,
  0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b, 0x35b5a8fa, 0x42b2986c, 0xdbbbc9d6,
  0xacbcf940, 0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59, 0x26d930ac,
  0x51de003a, 0xc8d75180, 0xbfd06116, 0x21b4f4b5, 0x56b3c423,
  0xcfba9599, 0xb8bda50f, 0x2802b89e, 0x5f058808,
  0xc60cd9b2, 0xb10be924, 0x2f6f7c87,
  0x58684c11, 0xc1611dab,
  0xb6662d3d,
  0x76dc4190,
  0x01db7106, 0x98d220bc,
  0xefd5102a, 0x71b18589, 0x06b6b51f,
  0x9fbfe4a5, 0xe8b8d433, 0x7807c9a2, 0x0f00f934,
  0x9609a88e, 0xe10e9818, 0x7f6a0dbb, 0x086d3d2d, 0x91646c97,
  0xe6635c01, 0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e, 0x6c0695ed,
  0x1b01a57b, 0x8208f4c1, 0xf50fc457, 0x65b0d9c6, 0x12b7e950, 0x8bbeb8ea, 0xfcb9887c,
  0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65, 0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2,
  0x4adfa541, 0x3dd895d7, 0xa4d1c46d, 0xd3d6f4fb, 0x4369e96a, 0x346ed9fc, 0xad678846,
  0xda60b8d0, 0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9, 0x5005713c,
  0x270241aa, 0xbe0b1010, 0xc90c2086, 0x5768b525, 0x206f85b3,
  0xb966d409, 0xce61e49f, 0x5edef90e, 0x29d9c998,
  0xb0d09822, 0xc7d7a8b4, 0x59b33d17,
  0x2eb40d81, 0xb7bd5c3b,
  0xc0ba6cad,
  0xedb88320,
  0x9abfb3b6, 0x03b6e20c,
  0x74b1d29a, 0xead54739, 0x9dd277af,
  0x04db2615, 0x73dc1683, 0xe3630b12, 0x94643b84,
  0x0d6d6a3e, 0x7a6a5aa8, 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27,
  0x7d079eb1, 0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe, 0xf762575d,
  0x806567cb, 0x196c3671, 0x6e6b06e7, 0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc,
  0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5, 0xd6d6a3e8, 0xa1d1937e, 0x38d8c2c4, 0x4fdff252,
  0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b, 0xd80d2bda, 0xaf0a1b4c, 0x36034af6,
  0x41047a60, 0xdf60efc3, 0xa867df55, 0x316e8eef, 0x4669be79, 0xcb61b38c,
  0xbc66831a, 0x256fd2a0, 0x5268e236, 0xcc0c7795, 0xbb0b4703,
  0x220216b9, 0x5505262f, 0xc5ba3bbe, 0xb2bd0b28,
  0x2bb45a92, 0x5cb36a04, 0xc2d7ffa7,
  0xb5d0cf31, 0x2cd99e8b,
  0x5bdeae1d,
  0x9b64c2b0,
  0xec63f226, 0x756aa39c,
  0x026d930a, 0x9c0906a9, 0xeb0e363f,
  0x72076785, 0x05005713, 0x95bf4a82, 0xe2b87a14,
  0x7bb12bae, 0x0cb61b38, 0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7,
  0x0bdbdf21, 0x86d3d2d4, 0xf1d4e242, 0x68ddb3f8, 0x1fda836e, 0x81be16cd,
  0xf6b9265b, 0x6fb077e1, 0x18b74777, 0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c,
  0x8f659eff, 0xf862ae69, 0x616bffd3, 0x166ccf45, 0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2,
  0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db, 0xaed16a4a, 0xd9d65adc, 0x40df0b66,
  0x37d83bf0, 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9, 0xbdbdf21c,
  0xcabac28a, 0x53b39330, 0x24b4a3a6, 0xbad03605, 0xcdd70693,
  0x54de5729, 0x23d967bf, 0xb3667a2e, 0xc4614ab8,
  0x5d681b02, 0x2a6f2b94, 0xb40bbe37,
  0xc30c8ea1, 0x5a05df1b,
  0x2d02ef8d
};

// Calculate CRC32 of given buffer.
ulong crc_init = 0xffffffffL;
ulong calc_crc32_block (ulong crc, unsigned char *p, long n)
{
    while (n--) {
        crc = crctab[((int)crc ^ (*p++)) & 0xff] ^ (crc >> 8);
    }
    return crc;
}

// Open, read, compute file checksum.
char iobuf[1024 * 1024];
int get_checksum (char *filename, ulong *crc)
{
    FILE *f;
    long resid, size;
    struct _stat st;

    if (NULL == (f = fopen(filename, "rb"))) {
        return 0;
    }
    if (_fstat(_fileno(f), &st) != 0) {
        fclose(f);
        return 0;
    }
    *crc = crc_init;
    for (resid = st.st_size; resid > 0; resid -= size) {
        size = min(resid, sizeof iobuf);
        if (fread(iobuf, size, 1, f) != 1) {
            fclose(f);
            return 0;
        }
        *crc = calc_crc32_block(*crc, iobuf, size);
    }
    fclose(f);
    *crc ^= crc_init;
    return 1;
}