/*
 * bd-sync
 *  Create a simple-to-process list of differences that need to be mirrored
 *  across a source and backup destination.
 *
 *  This program is needed because the stat() call in Windows7/cygwin is
 *  terribly slow. As a comparison, it takes 23 minutes to run rsync on
 *  my backup while this program takes roughly 2 minutes on the same.
 *
 * Notes:
 * 1. Ignore time differences upto 2 seconds (NTFS write error margin).
 *    NB. Does not handle Daylight Savings Time or FAT times
 *        simply because I don't have use for either.
 *        (Should be easy enough to add if needed)
 *
 * http://the-brown-dragon.com/
 */
#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <dirent.h>
#include <sys/stat.h>
#include <time.h>
#include <unistd.h>
#include <windows.h>

typedef void*          vptr_t;
typedef int8_t         byte_t;
typedef int8_t*        byteptr_t;
typedef char           char_t;
typedef char_t*        strptr_t;
typedef int            bool_t;

/**
 * Ignore time differences upto 2 seconds (NTFS write error margin).
 */
#define SLACKTIME 50000000

/**
 * Simple error handling.
 */
static char_t errmsg [2048];
#define ERRRET(r,...) do {\
    if (errno) {sprintf(errmsg,__VA_ARGS__);perror(errmsg);}\
    else {fprintf (stderr,__VA_ARGS__);fprintf(stderr,"\n");}\
    return (r);\
} while (0);

/**
 * Statistics for improving performance.
 */
#ifdef STATS

    #define NEWCLOCK(t) clock_t t
    #define STARTCLOCK(t) t = clock ()
    #define STOPCLOCK(d,t) d = (clock () - t)
    #define ACCUMCLOCK(a,t) do { a##_a = ((a##_a * a##_c) + (clock () - t))/(++(a##_c)); } while (0)
    #define DEFACCUM(w) static double w##_a; static uint32_t w##_c
    #define GETACCUM(w) w##_a

#else

    #define NEWCLOCK(t)
    #define STARTCLOCK(t)
    #define STOPCLOCK(d,t)
    #define ACCUMCLOCK(a,t)
    #define DEFACCUM(w)
    #define GETACCUM(w)

#endif

DEFACCUM (OPEN);
DEFACCUM (READ);
DEFACCUM (CLOSE);
DEFACCUM (STAT);
DEFACCUM (MAKEPATH);
DEFACCUM (ALLOCFI);
DEFACCUM (PRINT);
DEFACCUM (SORTFNAMES);

#ifdef STATS
static inline void dump_stats (void)
{
    printf ("Open:%f\n", GETACCUM(OPEN));
    printf ("Read:%f\n", GETACCUM(READ));
    printf ("Close:%f\n", GETACCUM(CLOSE));
    printf ("Stat:%f\n", GETACCUM(STAT));
    printf ("MakePath:%f\n", GETACCUM(MAKEPATH));
    printf ("AllocFI:%f\n", GETACCUM(ALLOCFI));
    printf ("Print:%f\n", GETACCUM(PRINT));
    printf ("Sort:%f\n", GETACCUM(SORTFNAMES));
}
#endif

/**
 * Basic allocator.
 */
static inline void* xmalloc (size_t pSize)
{
        vptr_t  v;
    if ((v = malloc (pSize))) return v;
    perror ("Out of Memory!");
    exit (EXIT_FAILURE);
}

/**
 * We need to call windows API to get the performance we need.
 * Hence we need windows path support.
 */
static inline strptr_t cygwin_to_win32_path (strptr_t pCygPath)
{
    if (strstr (pCygPath, "/cygdrive/") != pCygPath) return pCygPath;

    pCygPath [9] = pCygPath [10];
    pCygPath [10] = ':';

    return pCygPath + 9;
}

/**
 * Gets file information by calling the windows API.
 */
static inline int get_file_attr (strptr_t pFName,
                                 WIN32_FILE_ATTRIBUTE_DATA *pFAttrs)
{
    if (GetFileAttributesExA(pFName,GetFileExInfoStandard,pFAttrs)) return 0;
    { /* Maybe it's in unicode */
            wchar_t buf[1024];
        if (MultiByteToWideChar (CP_UTF8, 0, pFName, -1, buf, 1024)) {
            if (GetFileAttributesExW(buf,GetFileExInfoStandard,pFAttrs)) return 0;
        }
    }

    switch (GetLastError()) {
        case ERROR_ACCESS_DENIED:
        case ERROR_SHARING_VIOLATION:
        case ERROR_LOCK_VIOLATION:
        case ERROR_SHARING_BUFFER_EXCEEDED:
            return EACCES;
        case ERROR_BUFFER_OVERFLOW:
            return ENAMETOOLONG;
        case ERROR_NOT_ENOUGH_MEMORY:
            return ENOMEM;
        default:
            return ENOENT;
    }
}

/**
 * Walks a given directory.
 */
int walk_dir (strptr_t pDir,
              int (*walk_func) (strptr_t pDirElem, vptr_t pCtx),
              vptr_t pCtx)
{
        DIR           *d;
        struct dirent *de;
        int            r;
        NEWCLOCK(t);

    STARTCLOCK(t);
    if (!(d = opendir (pDir))) ERRRET (1, "Cannot open %s!", pDir);
    ACCUMCLOCK(OPEN,t);

    STARTCLOCK(t);
    while ((errno = 0, de = readdir (d)) != NULL) {
        ACCUMCLOCK(READ,t);
        if ((r = walk_func (de->d_name, pCtx))) return r;
        STARTCLOCK(t);
    }

    if (errno) ERRRET (2, "Error while walking %s!", pDir);

    STARTCLOCK(t);
    (void)closedir (d);
    ACCUMCLOCK(CLOSE,t);

    return 0;
}

/**
 * Here is where we store the file information for comparison.
 */
struct tFileInfo {
    char_t   uFlag;
    strptr_t uFName;
    uint64_t uTime;
    uint64_t uSize;

    struct tFileInfo *uNext;
};

/**
 * Root of the comparison path;
 */
struct tRoot {
    strptr_t          uRoot;
    struct tFileInfo *uHead;
};

/**
 * Application contains source and destination.
 */
struct tAppInfo {
    struct tRoot uSrc;
    struct tRoot uDst;
};

/**
 * Actual walk to save file information.
 */
int walk_save (strptr_t pDirElem, vptr_t pCtx)
{
        WIN32_FILE_ATTRIBUTE_DATA  a;
        struct tRoot              *r = pCtx;
        struct tFileInfo          *fi, *p;
        strptr_t                   o;
        NEWCLOCK(t);

    if ((!strcmp (pDirElem, "."))
            || (!strcmp (pDirElem, ".."))) return 0;

    STARTCLOCK(t);
    fi = xmalloc (sizeof (struct tFileInfo));
    memset (fi, 0, sizeof (struct tFileInfo));
    ACCUMCLOCK(ALLOCFI,t);
    STARTCLOCK(t);
    fi->uFName = xmalloc ((strlen (r->uRoot) + strlen (pDirElem) + 2) * sizeof (char_t));
    sprintf (fi->uFName, "%s/%s", r->uRoot, pDirElem);
    ACCUMCLOCK(MAKEPATH,t);

    STARTCLOCK(t);
    p = r->uHead;
    if (p && (strcmp (p->uFName, fi->uFName) < 0)) {
        fi->uNext = r->uHead;
        r->uHead  = fi;
    } else {
        while (p->uNext && (strcmp (p->uNext->uFName, fi->uFName) > 0)) p = p->uNext;
        fi->uNext = p->uNext;
        p->uNext  = fi;
    }
    ACCUMCLOCK(SORTFNAMES,t);

    STARTCLOCK(t);
    if ((errno = get_file_attr (fi->uFName, &a))) ERRRET (0, "Cannot read %s!", fi->uFName);
    fi->uTime  = ((uint64_t)a.ftLastWriteTime.dwLowDateTime) | (((uint64_t)a.ftLastWriteTime.dwHighDateTime) << 32);
    fi->uSize  = ((uint64_t)a.nFileSizeLow) | (((uint64_t)a.nFileSizeHigh) << 32);
    ACCUMCLOCK(STAT,t);

    o = r->uRoot; r->uRoot = fi->uFName;
    fi->uFlag = (a.dwFileAttributes & FILE_ATTRIBUTE_DIRECTORY) ? 'd' : 'f';
    if (fi->uFlag == 'd') (void)walk_dir (fi->uFName, walk_save, pCtx);
    r->uRoot = o;

    return 0;
}

/**
 * Useful dump function.
 */
static inline void dump_fileinfo (struct tFileInfo *pFI)
{
        SYSTEMTIME ft;
        FILETIME   ftt;

    ftt.dwLowDateTime  = (0xFFFFFFFF & pFI->uTime);
    ftt.dwHighDateTime = (pFI->uTime >> 32);

    if (!(FileTimeToSystemTime (&ftt, &ft))) memset (&ft, 0, sizeof (SYSTEMTIME));
    printf ("%c   %d-%02d-%02dT%02d:%02d:%02d.%02d\t%lld\t%s\n",
            pFI->uFlag,
            (int)ft.wYear, (int)ft.wMonth, (int)ft.wDay,
            (int)ft.wHour, (int)ft.wMinute, (int)ft.wSecond, (int)ft.wMilliseconds,
            pFI->uSize, pFI->uFName);
}

/**
 * Dump application information header
 */
static inline void dump_appinfo (struct tAppInfo *pAI)
{
        struct tFileInfo *fi;

    printf ("#!bd-sync\n");

    printf ("#S[ource]     : %s\n", pAI->uSrc.uRoot);
    for (fi = pAI->uSrc.uHead;fi;fi = fi->uNext) dump_fileinfo (fi);

    printf ("#D[estination]: %s\n", pAI->uDst.uRoot);
    for (fi = pAI->uDst.uHead;fi;fi = fi->uNext) dump_fileinfo (fi);
}

/**
 * Dump file difference.
 */
static inline void dump_filediff (struct tFileInfo *pSrc, struct tFileInfo *pDst)
{
    printf ("%c %s*%s\n", pSrc ? pSrc->uFlag : pDst->uFlag,
                          pSrc ? pSrc->uFName : "",
                          pDst ? pDst->uFName : "");
}

/**
 * Comparision results.
 */
enum eCmpInfo {
    INFO_IDENTICAL,
    INFO_NOMATCH,
    INFO_NOSRC,
    INFO_NODST,
};

/**
 * Simple offsets into path for comparison.
 */
static int sSrcOffset, sDstOffset;

/**
 * Comparison function.
 */
static inline enum eCmpInfo cmp_info (struct tFileInfo *pSrc,
                                      struct tFileInfo *pDst)
{
        int      ci;
        uint64_t d;

    if (!pSrc) return INFO_NOSRC;
    if (!pDst) return INFO_NODST;

    ci = strcmp (pSrc->uFName + sSrcOffset, pDst->uFName + sDstOffset);

    if (ci > 0) return INFO_NOSRC;
    else if (ci < 0) return INFO_NODST;

    if ((pSrc->uFlag == 'd') && (pDst->uFlag == 'f')) return INFO_NOSRC;
    if ((pSrc->uFlag == 'f') && (pDst->uFlag == 'd')) return INFO_NODST;

    if ((pSrc->uFlag == 'd') && (pDst->uFlag == 'd')) return INFO_IDENTICAL;

    d = pSrc->uTime > pDst->uTime ? pSrc->uTime - pDst->uTime :
            pDst->uTime - pSrc->uTime;

    if ((pSrc->uSize == pDst->uSize) && (d < SLACKTIME)) return INFO_IDENTICAL;

    return INFO_NOMATCH;
}

/**
 * Dumps the entire diff information.
 */
static inline int dump_diffinfo (struct tAppInfo *pAppInfo)
{
        struct tFileInfo *src  , *dst;
        enum eCmpInfo     ci;

    printf ("#!bd-sync\n");
    printf ("#S[ource]     : %s\n", pAppInfo->uSrc.uRoot);
    printf ("#D[estination]: %s\n", pAppInfo->uDst.uRoot);

    // Setup closure
    sSrcOffset = strlen (pAppInfo->uSrc.uRoot);
    sDstOffset = strlen (pAppInfo->uDst.uRoot);

    // Walk source and dest
    src = pAppInfo->uSrc.uHead;
    dst = pAppInfo->uDst.uHead;
    while (src || dst) {
        switch ((ci = cmp_info (src, dst))) {
            case INFO_IDENTICAL:
                // Match! Advance both
                src = src->uNext;
                dst = dst->uNext;
                break;
            case INFO_NOMATCH:
                // No match! Display both files
                dump_filediff (src, dst);
                src = src->uNext;
                dst = dst->uNext;
                break;
            case INFO_NOSRC:
                // Only display dest
                dump_filediff (NULL, dst);
                dst = dst->uNext;
                break;
            case INFO_NODST:
                // Only display src
                dump_filediff (src, NULL);
                src = src->uNext;
                break;
            default:
                ERRRET (1, "Comparison not understood (%d)!", ci);
        }
    }

    // All done!
    return 0;

}

/**
 * Setup the root paths.
 */
static inline int setup_root (struct tRoot *pRoot, strptr_t pDir)
{
        char  buf [MAX_PATH];

    /* No cleanup - this memory is needed for lifetime of app anyway */
    pRoot->uHead = xmalloc (sizeof (struct tFileInfo));
    memset (pRoot->uHead, 0, sizeof (struct tFileInfo));
    pRoot->uHead->uFName   = xmalloc (MAX_PATH);

    if (!getcwd (buf, MAX_PATH)) ERRRET (0, "Failed to get full path of current dir!");
    if (chdir (pDir)) ERRRET (0, "Failed to open directory %s!", pDir);
    if (!getcwd (pRoot->uHead->uFName, MAX_PATH)) ERRRET (0, "Failed to get full path of %s!", pDir);
    if (chdir (buf)) ERRRET (0, "Failed to return to current dir!");
    pRoot->uRoot =
    pRoot->uHead->uFName = cygwin_to_win32_path (pRoot->uHead->uFName);

    return 1;
}

/**
 * Parses the arguments.
 */
static inline struct tAppInfo* parse_args (int argc, char *argv[])
{
        struct tAppInfo *ai;

    if (argc != 3) ERRRET (NULL, "Please provide <src> <dest>");

    ai = xmalloc (sizeof (struct tAppInfo));
    memset (ai, 0, sizeof (struct tAppInfo));

    if (!setup_root (&ai->uSrc, argv [1])) goto err;
    if (!setup_root (&ai->uDst, argv [2])) goto err;

    return ai;

err:
    free (ai);
    return NULL;
}

/**
 * Load a particular root (src or dest).
 */
static inline int load (struct tRoot *pRoot)
{
    return walk_dir (pRoot->uHead->uFName, walk_save, pRoot);
}

/**
 * Reverses the gathered list to get it into correct order.
 */
static struct tFileInfo* reverse_list (struct tFileInfo *pNode)
{
        struct tFileInfo *pr, *nxt;

    if (!pNode || !pNode->uNext) return pNode;

    pr = NULL;
    while (pNode) {
        nxt          = pNode->uNext;
        pNode->uNext = pr;
        pr           = pNode;
        pNode        = nxt;
    }
    return pr;
}

/**
 * Populates a particular root (src or dest).
 */
static inline int populate (struct tRoot *pRoot)
{
        int        r;
    if (!(r = load (pRoot))) pRoot->uHead = reverse_list (pRoot->uHead);
    return r;
}

/**
 * Main entry point.
 */
int main (int argc, char *argv[])
{
        struct tAppInfo *ai;

    if (!(ai = parse_args (argc, argv))) return EXIT_FAILURE;

    if (populate (&ai->uSrc)) return EXIT_FAILURE;
    if (populate (&ai->uDst)) return EXIT_FAILURE;

    if (dump_diffinfo (ai)) return EXIT_FAILURE;

    if (getenv ("DEBUGDUMP")) {
        printf ("\n\n#---- DEBUG DUMP ----\n");
        dump_appinfo (ai);
    }

#ifdef STATS
    dump_stats ();
#endif

    return EXIT_SUCCESS;
}