/*-
 * SPDX-License-Identifier: BSD-2-Clause
 *
 * Copyright (c) 2019 Google LLC
 * Copyright (C) 1995, 1996, 1997 Wolfgang Solfrank
 * Copyright (c) 1995 Martin Husemann
 * Some structure declaration borrowed from Paul Popelka
 * (paulp@uts.amdahl.com), see /sys/msdosfs/ for reference.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHORS ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */


#include <sys/cdefs.h>
#ifndef lint
__RCSID("$NetBSD: dir.c,v 1.20 2006/06/05 16:51:18 christos Exp $");
#endif /* not lint */

#include <assert.h>
#include <inttypes.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <unistd.h>
#include <time.h>

#include <sys/param.h>

#include "ext.h"
#include "fsutil.h"

#define SLOT_EMPTY      0x00            /* slot has never been used */
#define SLOT_E5         0x05            /* the real value is 0xe5 */
#define SLOT_DELETED    0xe5            /* file in this slot deleted */

#define ATTR_NORMAL     0x00            /* normal file */
#define ATTR_READONLY   0x01            /* file is readonly */
#define ATTR_HIDDEN     0x02            /* file is hidden */
#define ATTR_SYSTEM     0x04            /* file is a system file */
#define ATTR_VOLUME     0x08            /* entry is a volume label */
#define ATTR_DIRECTORY  0x10            /* entry is a directory name */
#define ATTR_ARCHIVE    0x20            /* file is new or modified */

#define ATTR_WIN95      0x0f            /* long name record */

/*
 * This is the format of the contents of the deTime field in the direntry
 * structure.
 * We don't use bitfields because we don't know how compilers for
 * arbitrary machines will lay them out.
 */
#define DT_2SECONDS_MASK        0x1F    /* seconds divided by 2 */
#define DT_2SECONDS_SHIFT       0
#define DT_MINUTES_MASK         0x7E0   /* minutes */
#define DT_MINUTES_SHIFT        5
#define DT_HOURS_MASK           0xF800  /* hours */
#define DT_HOURS_SHIFT          11

/*
 * This is the format of the contents of the deDate field in the direntry
 * structure.
 */
#define DD_DAY_MASK             0x1F    /* day of month */
#define DD_DAY_SHIFT            0
#define DD_MONTH_MASK           0x1E0   /* month */
#define DD_MONTH_SHIFT          5
#define DD_YEAR_MASK            0xFE00  /* year - 1980 */
#define DD_YEAR_SHIFT           9


/* dir.c */
static struct dosDirEntry *newDosDirEntry(void);
static void freeDosDirEntry(struct dosDirEntry *);
static struct dirTodoNode *newDirTodo(void);
static void freeDirTodo(struct dirTodoNode *);
static char *fullpath(struct dosDirEntry *);
static u_char calcShortSum(u_char *);
static int delete(struct fat_descriptor *, cl_t, int, cl_t, int, int);
static int removede(struct fat_descriptor *, u_char *, u_char *,
    cl_t, cl_t, cl_t, char *, int);
static int checksize(struct fat_descriptor *, u_char *, struct dosDirEntry *);
static int readDosDirSection(struct fat_descriptor *, struct dosDirEntry *);

/*
 * Manage free dosDirEntry structures.
 */
static struct dosDirEntry *freede;

static struct dosDirEntry *
newDosDirEntry(void)
{
        struct dosDirEntry *de;

        if (!(de = freede)) {
                if (!(de = malloc(sizeof *de)))
                        return (NULL);
        } else
                freede = de->next;
        return de;
}

static void
freeDosDirEntry(struct dosDirEntry *de)
{
        de->next = freede;
        freede = de;
}

/*
 * The same for dirTodoNode structures.
 */
static struct dirTodoNode *freedt;

static struct dirTodoNode *
newDirTodo(void)
{
        struct dirTodoNode *dt;

        if (!(dt = freedt)) {
                if (!(dt = malloc(sizeof *dt)))
                        return 0;
        } else
                freedt = dt->next;
        return dt;
}

static void
freeDirTodo(struct dirTodoNode *dt)
{
        dt->next = freedt;
        freedt = dt;
}

/*
 * The stack of unread directories
 */
static struct dirTodoNode *pendingDirectories = NULL;

/*
 * Return the full pathname for a directory entry.
 */
static char *
fullpath(struct dosDirEntry *dir)
{
        static char namebuf[MAXPATHLEN + 1];
        char *cp, *np;
        int nl;

        cp = namebuf + sizeof namebuf;
        *--cp = '\0';

        for(;;) {
                np = dir->lname[0] ? dir->lname : dir->name;
                nl = strlen(np);
                if (cp <= namebuf + 1 + nl) {
                        *--cp = '?';
                        break;
                }
                cp -= nl;
                memcpy(cp, np, nl);
                dir = dir->parent;
                if (!dir)
                        break;
                *--cp = '/';
        }

        return cp;
}

/*
 * Calculate a checksum over an 8.3 alias name
 */
static inline u_char
calcShortSum(u_char *p)
{
        u_char sum = 0;
        int i;

        for (i = 0; i < 11; i++) {
                sum = (sum << 7)|(sum >> 1);    /* rotate right */
                sum += p[i];
        }

        return sum;
}

/*
 * Global variables temporarily used during a directory scan
 */
static char longName[DOSLONGNAMELEN] = "";
static u_char *buffer = NULL;
static u_char *delbuf = NULL;

static struct dosDirEntry *rootDir;
static struct dosDirEntry *lostDir;

/*
 * Init internal state for a new directory scan.
 */
int
resetDosDirSection(struct fat_descriptor *fat)
{
        int rootdir_size, cluster_size;
        int ret = FSOK;
        size_t len;
        struct bootblock *boot;

        boot = fat_get_boot(fat);

        rootdir_size = boot->bpbRootDirEnts * 32;
        cluster_size = boot->bpbSecPerClust * boot->bpbBytesPerSec;

        if ((buffer = malloc(len = MAX(rootdir_size, cluster_size))) == NULL) {
                perr("No space for directory buffer (%zu)", len);
                return FSFATAL;
        }

        if ((delbuf = malloc(len = cluster_size)) == NULL) {
                free(buffer);
                perr("No space for directory delbuf (%zu)", len);
                return FSFATAL;
        }

        if ((rootDir = newDosDirEntry()) == NULL) {
                free(buffer);
                free(delbuf);
                perr("No space for directory entry");
                return FSFATAL;
        }

        memset(rootDir, 0, sizeof *rootDir);
        if (boot->flags & FAT32) {
                if (!fat_is_cl_head(fat, boot->bpbRootClust)) {
                        pfatal("Root directory doesn't start a cluster chain");
                        return FSFATAL;
                }
                rootDir->head = boot->bpbRootClust;
        }

        return ret;
}

/*
 * Cleanup after a directory scan
 */
void
finishDosDirSection(void)
{
        struct dirTodoNode *p, *np;
        struct dosDirEntry *d, *nd;

        for (p = pendingDirectories; p; p = np) {
                np = p->next;
                freeDirTodo(p);
        }
        pendingDirectories = NULL;
        for (d = rootDir; d; d = nd) {
                if ((nd = d->child) != NULL) {
                        d->child = 0;
                        continue;
                }
                if (!(nd = d->next))
                        nd = d->parent;
                freeDosDirEntry(d);
        }
        rootDir = lostDir = NULL;
        free(buffer);
        free(delbuf);
        buffer = NULL;
        delbuf = NULL;
}

/*
 * Delete directory entries between startcl, startoff and endcl, endoff.
 */
static int
delete(struct fat_descriptor *fat, cl_t startcl,
    int startoff, cl_t endcl, int endoff, int notlast)
{
        u_char *s, *e;
        off_t off;
        int clsz, fd;
        struct bootblock *boot;

        boot = fat_get_boot(fat);
        fd = fat_get_fd(fat);
        clsz = boot->bpbSecPerClust * boot->bpbBytesPerSec;

        s = delbuf + startoff;
        e = delbuf + clsz;
        while (fat_is_valid_cl(fat, startcl)) {
                if (startcl == endcl) {
                        if (notlast)
                                break;
                        e = delbuf + endoff;
                }
                off = (startcl - CLUST_FIRST) * boot->bpbSecPerClust + boot->FirstCluster;

                off *= boot->bpbBytesPerSec;
                if (lseek(fd, off, SEEK_SET) != off) {
                        perr("Unable to lseek to %" PRId64, off);
                        return FSFATAL;
                }
                if (read(fd, delbuf, clsz) != clsz) {
                        perr("Unable to read directory");
                        return FSFATAL;
                }
                while (s < e) {
                        *s = SLOT_DELETED;
                        s += 32;
                }
                if (lseek(fd, off, SEEK_SET) != off) {
                        perr("Unable to lseek to %" PRId64, off);
                        return FSFATAL;
                }
                if (write(fd, delbuf, clsz) != clsz) {
                        perr("Unable to write directory");
                        return FSFATAL;
                }
                if (startcl == endcl)
                        break;
                startcl = fat_get_cl_next(fat, startcl);
                s = delbuf;
        }
        return FSOK;
}

static int
removede(struct fat_descriptor *fat, u_char *start,
    u_char *end, cl_t startcl, cl_t endcl, cl_t curcl,
    char *path, int type)
{
        switch (type) {
        case 0:
                pwarn("Invalid long filename entry for %s\n", path);
                break;
        case 1:
                pwarn("Invalid long filename entry at end of directory %s\n",
                    path);
                break;
        case 2:
                pwarn("Invalid long filename entry for volume label\n");
                break;
        }
        if (ask(0, "Remove")) {
                if (startcl != curcl) {
                        if (delete(fat,
                                   startcl, start - buffer,
                                   endcl, end - buffer,
                                   endcl == curcl) == FSFATAL)
                                return FSFATAL;
                        start = buffer;
                }
                /* startcl is < CLUST_FIRST for !FAT32 root */
                if ((endcl == curcl) || (startcl < CLUST_FIRST))
                        for (; start < end; start += 32)
                                *start = SLOT_DELETED;
                return FSDIRMOD;
        }
        return FSERROR;
}

/*
 * Check an in-memory file entry
 */
static int
checksize(struct fat_descriptor *fat, u_char *p, struct dosDirEntry *dir)
{
        int ret = FSOK;
        size_t chainsize;
        u_int64_t physicalSize;
        struct bootblock *boot;

        boot = fat_get_boot(fat);

        /*
         * Check size on ordinary files
         */
        if (dir->head == CLUST_FREE) {
                physicalSize = 0;
        } else {
                if (!fat_is_valid_cl(fat, dir->head) || !fat_is_cl_head(fat, dir->head)) {
                        pwarn("Directory entry %s of size %u referencing invalid cluster %u\n",
                            fullpath(dir), dir->size, dir->head);
                        if (ask(1, "Truncate")) {
                                p[28] = p[29] = p[30] = p[31] = 0;
                                p[26] = p[27] = 0;
                                if (boot->ClustMask == CLUST32_MASK)
                                        p[20] = p[21] = 0;
                                dir->size = 0;
                                dir->head = CLUST_FREE;
                                return FSDIRMOD;
                        } else {
                                return FSERROR;
                        }
                }
                ret = checkchain(fat, dir->head, &chainsize);
                /*
                 * Upon return, chainsize would hold the chain length
                 * that checkchain() was able to validate, but if the user
                 * refused the proposed repair, it would be unsafe to
                 * proceed with directory entry fix, so bail out in that
                 * case.
                 */
                if (ret == FSERROR) {
                        return (FSERROR);
                }
                /*
                 * The maximum file size on FAT32 is 4GiB - 1, which
                 * will occupy a cluster chain of exactly 4GiB in
                 * size.  On 32-bit platforms, since size_t is 32-bit,
                 * it would wrap back to 0.
                 */
                physicalSize = (u_int64_t)chainsize * boot->ClusterSize;
        }
        if (physicalSize < dir->size) {
                pwarn("size of %s is %u, should at most be %ju\n",
                      fullpath(dir), dir->size, (uintmax_t)physicalSize);
                if (ask(1, "Truncate")) {
                        dir->size = physicalSize;
                        p[28] = (u_char)physicalSize;
                        p[29] = (u_char)(physicalSize >> 8);
                        p[30] = (u_char)(physicalSize >> 16);
                        p[31] = (u_char)(physicalSize >> 24);
                        return FSDIRMOD;
                } else
                        return FSERROR;
        } else if (physicalSize - dir->size >= boot->ClusterSize) {
                pwarn("%s has too many clusters allocated\n",
                      fullpath(dir));
                if (ask(1, "Drop superfluous clusters")) {
                        cl_t cl;
                        u_int32_t sz, len;

                        for (cl = dir->head, len = sz = 0;
                            (sz += boot->ClusterSize) < dir->size; len++)
                                cl = fat_get_cl_next(fat, cl);
                        clearchain(fat, fat_get_cl_next(fat, cl));
                        ret = fat_set_cl_next(fat, cl, CLUST_EOF);
                        return (FSFATMOD | ret);
                } else
                        return FSERROR;
        }
        return FSOK;
}

static const u_char dot_name[11] __nonstring    = ".          ";
static const u_char dotdot_name[11] __nonstring = "..         ";

/*
 * Basic sanity check if the subdirectory have good '.' and '..' entries,
 * and they are directory entries.  Further sanity checks are performed
 * when we traverse into it.
 */
static int
check_subdirectory(struct fat_descriptor *fat, struct dosDirEntry *dir)
{
        u_char *buf, *cp;
        off_t off;
        cl_t cl;
        int retval = FSOK;
        int fd;
        struct bootblock *boot;

        boot = fat_get_boot(fat);
        fd = fat_get_fd(fat);

        cl = dir->head;
        if (dir->parent && !fat_is_valid_cl(fat, cl)) {
                return FSERROR;
        }

        if (!(boot->flags & FAT32) && !dir->parent) {
                off = boot->bpbResSectors + boot->bpbFATs *
                        boot->FATsecs;
        } else {
                off = (cl - CLUST_FIRST) * boot->bpbSecPerClust + boot->FirstCluster;
        }

        /*
         * We only need to check the first two entries of the directory,
         * which is found in the first sector of the directory entry,
         * so read in only the first sector.
         */
        buf = malloc(boot->bpbBytesPerSec);
        if (buf == NULL) {
                perr("No space for directory buffer (%u)",
                    boot->bpbBytesPerSec);
                return FSFATAL;
        }

        off *= boot->bpbBytesPerSec;
        if (lseek(fd, off, SEEK_SET) != off ||
            read(fd, buf, boot->bpbBytesPerSec) != (ssize_t)boot->bpbBytesPerSec) {
                perr("Unable to read directory");
                free(buf);
                return FSFATAL;
        }

        /*
         * Both `.' and `..' must be present and be the first two entries
         * and be ATTR_DIRECTORY of a valid subdirectory.
         */
        cp = buf;
        if (memcmp(cp, dot_name, sizeof(dot_name)) != 0 ||
            (cp[11] & ATTR_DIRECTORY) != ATTR_DIRECTORY) {
                pwarn("%s: Incorrect `.' for %s.\n", __func__, dir->name);
                retval |= FSERROR;
        }
        cp += 32;
        if (memcmp(cp, dotdot_name, sizeof(dotdot_name)) != 0 ||
            (cp[11] & ATTR_DIRECTORY) != ATTR_DIRECTORY) {
                pwarn("%s: Incorrect `..' for %s. \n", __func__, dir->name);
                retval |= FSERROR;
        }

        free(buf);
        return retval;
}

/*
 * Read a directory and
 *   - resolve long name records
 *   - enter file and directory records into the parent's list
 *   - push directories onto the todo-stack
 */
static int
readDosDirSection(struct fat_descriptor *fat, struct dosDirEntry *dir)
{
        struct bootblock *boot;
        struct dosDirEntry dirent, *d;
        u_char *p, *vallfn, *invlfn, *empty;
        off_t off;
        int fd, i, j, k, iosize, entries;
        bool is_legacyroot;
        cl_t cl, valcl = ~0, invcl = ~0, empcl = ~0;
        char *t;
        u_int lidx = 0;
        int shortSum;
        int mod = FSOK;
        size_t dirclusters;
#define THISMOD 0x8000                  /* Only used within this routine */

        boot = fat_get_boot(fat);
        fd = fat_get_fd(fat);

        cl = dir->head;
        if (dir->parent && (!fat_is_valid_cl(fat, cl))) {
                /*
                 * Already handled somewhere else.
                 */
                return FSOK;
        }
        shortSum = -1;
        vallfn = invlfn = empty = NULL;

        /*
         * If we are checking the legacy root (for FAT12/FAT16),
         * we will operate on the whole directory; otherwise, we
         * will operate on one cluster at a time, and also take
         * this opportunity to examine the chain.
         *
         * Derive how many entries we are going to encounter from
         * the I/O size.
         */
        is_legacyroot = (dir->parent == NULL && !(boot->flags & FAT32));
        if (is_legacyroot) {
                iosize = boot->bpbRootDirEnts * 32;
                entries = boot->bpbRootDirEnts;
        } else {
                iosize = boot->bpbSecPerClust * boot->bpbBytesPerSec;
                entries = iosize / 32;
                mod |= checkchain(fat, dir->head, &dirclusters);
        }

        do {
                if (is_legacyroot) {
                        /*
                         * Special case for FAT12/FAT16 root -- read
                         * in the whole root directory.
                         */
                        off = boot->bpbResSectors + boot->bpbFATs *
                            boot->FATsecs;
                } else {
                        /*
                         * Otherwise, read in a cluster of the
                         * directory.
                         */
                        off = (cl - CLUST_FIRST) * boot->bpbSecPerClust + boot->FirstCluster;
                }

                off *= boot->bpbBytesPerSec;
                if (lseek(fd, off, SEEK_SET) != off ||
                    read(fd, buffer, iosize) != iosize) {
                        perr("Unable to read directory");
                        return FSFATAL;
                }

                for (p = buffer, i = 0; i < entries; i++, p += 32) {
                        if (dir->fsckflags & DIREMPWARN) {
                                *p = SLOT_EMPTY;
                                continue;
                        }

                        if (*p == SLOT_EMPTY || *p == SLOT_DELETED) {
                                if (*p == SLOT_EMPTY) {
                                        dir->fsckflags |= DIREMPTY;
                                        empty = p;
                                        empcl = cl;
                                }
                                continue;
                        }

                        if (dir->fsckflags & DIREMPTY) {
                                if (!(dir->fsckflags & DIREMPWARN)) {
                                        pwarn("%s has entries after end of directory\n",
                                              fullpath(dir));
                                        if (ask(1, "Extend")) {
                                                u_char *q;

                                                dir->fsckflags &= ~DIREMPTY;
                                                if (delete(fat,
                                                           empcl, empty - buffer,
                                                           cl, p - buffer, 1) == FSFATAL)
                                                        return FSFATAL;
                                                q = ((empcl == cl) ? empty : buffer);
                                                assert(q != NULL);
                                                for (; q < p; q += 32)
                                                        *q = SLOT_DELETED;
                                                mod |= THISMOD|FSDIRMOD;
                                        } else if (ask(0, "Truncate"))
                                                dir->fsckflags |= DIREMPWARN;
                                }
                                if (dir->fsckflags & DIREMPWARN) {
                                        *p = SLOT_DELETED;
                                        mod |= THISMOD|FSDIRMOD;
                                        continue;
                                } else if (dir->fsckflags & DIREMPTY)
                                        mod |= FSERROR;
                                empty = NULL;
                        }

                        if (p[11] == ATTR_WIN95) {
                                if (*p & LRFIRST) {
                                        if (shortSum != -1) {
                                                if (!invlfn) {
                                                        invlfn = vallfn;
                                                        invcl = valcl;
                                                }
                                        }
                                        memset(longName, 0, sizeof longName);
                                        shortSum = p[13];
                                        vallfn = p;
                                        valcl = cl;
                                } else if (shortSum != p[13]
                                           || lidx != (*p & LRNOMASK)) {
                                        if (!invlfn) {
                                                invlfn = vallfn;
                                                invcl = valcl;
                                        }
                                        if (!invlfn) {
                                                invlfn = p;
                                                invcl = cl;
                                        }
                                        vallfn = NULL;
                                }
                                lidx = *p & LRNOMASK;
                                if (lidx == 0) {
                                        pwarn("invalid long name\n");
                                        if (!invlfn) {
                                                invlfn = vallfn;
                                                invcl = valcl;
                                        }
                                        vallfn = NULL;
                                        continue;
                                }
                                t = longName + --lidx * 13;
                                for (k = 1; k < 11 && t < longName +
                                    sizeof(longName); k += 2) {
                                        if (!p[k] && !p[k + 1])
                                                break;
                                        *t++ = p[k];
                                        /*
                                         * Warn about those unusable chars in msdosfs here?     XXX
                                         */
                                        if (p[k + 1])
                                                t[-1] = '?';
                                }
                                if (k >= 11)
                                        for (k = 14; k < 26 && t < longName + sizeof(longName); k += 2) {
                                                if (!p[k] && !p[k + 1])
                                                        break;
                                                *t++ = p[k];
                                                if (p[k + 1])
                                                        t[-1] = '?';
                                        }
                                if (k >= 26)
                                        for (k = 28; k < 32 && t < longName + sizeof(longName); k += 2) {
                                                if (!p[k] && !p[k + 1])
                                                        break;
                                                *t++ = p[k];
                                                if (p[k + 1])
                                                        t[-1] = '?';
                                        }
                                if (t >= longName + sizeof(longName)) {
                                        pwarn("long filename too long\n");
                                        if (!invlfn) {
                                                invlfn = vallfn;
                                                invcl = valcl;
                                        }
                                        vallfn = NULL;
                                }
                                if (p[26] | (p[27] << 8)) {
                                        pwarn("long filename record cluster start != 0\n");
                                        if (!invlfn) {
                                                invlfn = vallfn;
                                                invcl = cl;
                                        }
                                        vallfn = NULL;
                                }
                                continue;       /* long records don't carry further
                                                 * information */
                        }

                        /*
                         * This is a standard msdosfs directory entry.
                         */
                        memset(&dirent, 0, sizeof dirent);

                        /*
                         * it's a short name record, but we need to know
                         * more, so get the flags first.
                         */
                        dirent.flags = p[11];

                        /*
                         * Translate from 850 to ISO here               XXX
                         */
                        for (j = 0; j < 8; j++)
                                dirent.name[j] = p[j];
                        dirent.name[8] = '\0';
                        for (k = 7; k >= 0 && dirent.name[k] == ' '; k--)
                                dirent.name[k] = '\0';
                        if (k < 0 || dirent.name[k] != '\0')
                                k++;
                        if (dirent.name[0] == SLOT_E5)
                                dirent.name[0] = 0xe5;

                        if (dirent.flags & ATTR_VOLUME) {
                                if (vallfn || invlfn) {
                                        mod |= removede(fat,
                                                        invlfn ? invlfn : vallfn, p,
                                                        invlfn ? invcl : valcl, cl, cl,
                                                        fullpath(dir), 2);
                                        vallfn = NULL;
                                        invlfn = NULL;
                                }
                                continue;
                        }

                        if (p[8] != ' ')
                                dirent.name[k++] = '.';
                        for (j = 0; j < 3; j++)
                                dirent.name[k++] = p[j+8];
                        dirent.name[k] = '\0';
                        for (k--; k >= 0 && dirent.name[k] == ' '; k--)
                                dirent.name[k] = '\0';

                        if (vallfn && shortSum != calcShortSum(p)) {
                                if (!invlfn) {
                                        invlfn = vallfn;
                                        invcl = valcl;
                                }
                                vallfn = NULL;
                        }
                        dirent.head = p[26] | (p[27] << 8);
                        if (boot->ClustMask == CLUST32_MASK)
                                dirent.head |= (p[20] << 16) | (p[21] << 24);
                        dirent.size = p[28] | (p[29] << 8) | (p[30] << 16) | (p[31] << 24);
                        if (vallfn) {
                                strlcpy(dirent.lname, longName,
                                    sizeof(dirent.lname));
                                longName[0] = '\0';
                                shortSum = -1;
                        }

                        dirent.parent = dir;
                        dirent.next = dir->child;

                        if (invlfn) {
                                mod |= k = removede(fat,
                                                    invlfn, vallfn ? vallfn : p,
                                                    invcl, vallfn ? valcl : cl, cl,
                                                    fullpath(&dirent), 0);
                                if (mod & FSFATAL)
                                        return FSFATAL;
                                if (vallfn
                                    ? (valcl == cl && vallfn != buffer)
                                    : p != buffer)
                                        if (k & FSDIRMOD)
                                                mod |= THISMOD;
                        }

                        vallfn = NULL; /* not used any longer */
                        invlfn = NULL;

                        /*
                         * Check if the directory entry is sane.
                         *
                         * '.' and '..' are skipped, their sanity is
                         * checked somewhere else.
                         *
                         * For everything else, check if we have a new,
                         * valid cluster chain (beginning of a file or
                         * directory that was never previously claimed
                         * by another file) when it's a non-empty file
                         * or a directory. The sanity of the cluster
                         * chain is checked at a later time when we
                         * traverse into the directory, or examine the
                         * file's directory entry.
                         *
                         * The only possible fix is to delete the entry
                         * if it's a directory; for file, we have to
                         * truncate the size to 0.
                         */
                        if (!(dirent.flags & ATTR_DIRECTORY) ||
                            (strcmp(dirent.name, ".") != 0 &&
                            strcmp(dirent.name, "..") != 0)) {
                                if ((dirent.size != 0 || (dirent.flags & ATTR_DIRECTORY)) &&
                                    ((!fat_is_valid_cl(fat, dirent.head) ||
                                    !fat_is_cl_head(fat, dirent.head)))) {
                                        if (!fat_is_valid_cl(fat, dirent.head)) {
                                                pwarn("%s starts with cluster out of range(%u)\n",
                                                    fullpath(&dirent),
                                                    dirent.head);
                                        } else {
                                                pwarn("%s doesn't start a new cluster chain\n",
                                                    fullpath(&dirent));
                                        }

                                        if (dirent.flags & ATTR_DIRECTORY) {
                                                if (ask(0, "Remove")) {
                                                        *p = SLOT_DELETED;
                                                        mod |= THISMOD|FSDIRMOD;
                                                } else
                                                        mod |= FSERROR;
                                                continue;
                                        } else {
                                                if (ask(1, "Truncate")) {
                                                        p[28] = p[29] = p[30] = p[31] = 0;
                                                        p[26] = p[27] = 0;
                                                        if (boot->ClustMask == CLUST32_MASK)
                                                                p[20] = p[21] = 0;
                                                        dirent.size = 0;
                                                        dirent.head = 0;
                                                        mod |= THISMOD|FSDIRMOD;
                                                } else
                                                        mod |= FSERROR;
                                        }
                                }
                        }
                        if (dirent.flags & ATTR_DIRECTORY) {
                                /*
                                 * gather more info for directories
                                 */
                                struct dirTodoNode *n;

                                if (dirent.size) {
                                        pwarn("Directory %s has size != 0\n",
                                              fullpath(&dirent));
                                        if (ask(1, "Correct")) {
                                                p[28] = p[29] = p[30] = p[31] = 0;
                                                dirent.size = 0;
                                                mod |= THISMOD|FSDIRMOD;
                                        } else
                                                mod |= FSERROR;
                                }
                                /*
                                 * handle `.' and `..' specially
                                 */
                                if (strcmp(dirent.name, ".") == 0) {
                                        if (dirent.head != dir->head) {
                                                pwarn("`.' entry in %s has incorrect start cluster\n",
                                                      fullpath(dir));
                                                if (ask(1, "Correct")) {
                                                        dirent.head = dir->head;
                                                        p[26] = (u_char)dirent.head;
                                                        p[27] = (u_char)(dirent.head >> 8);
                                                        if (boot->ClustMask == CLUST32_MASK) {
                                                                p[20] = (u_char)(dirent.head >> 16);
                                                                p[21] = (u_char)(dirent.head >> 24);
                                                        }
                                                        mod |= THISMOD|FSDIRMOD;
                                                } else
                                                        mod |= FSERROR;
                                        }
                                        continue;
                                } else if (strcmp(dirent.name, "..") == 0) {
                                        if (dir->parent) {              /* XXX */
                                                if (!dir->parent->parent) {
                                                        if (dirent.head) {
                                                                pwarn("`..' entry in %s has non-zero start cluster\n",
                                                                      fullpath(dir));
                                                                if (ask(1, "Correct")) {
                                                                        dirent.head = 0;
                                                                        p[26] = p[27] = 0;
                                                                        if (boot->ClustMask == CLUST32_MASK)
                                                                                p[20] = p[21] = 0;
                                                                        mod |= THISMOD|FSDIRMOD;
                                                                } else
                                                                        mod |= FSERROR;
                                                        }
                                                } else if (dirent.head != dir->parent->head) {
                                                        pwarn("`..' entry in %s has incorrect start cluster\n",
                                                              fullpath(dir));
                                                        if (ask(1, "Correct")) {
                                                                dirent.head = dir->parent->head;
                                                                p[26] = (u_char)dirent.head;
                                                                p[27] = (u_char)(dirent.head >> 8);
                                                                if (boot->ClustMask == CLUST32_MASK) {
                                                                        p[20] = (u_char)(dirent.head >> 16);
                                                                        p[21] = (u_char)(dirent.head >> 24);
                                                                }
                                                                mod |= THISMOD|FSDIRMOD;
                                                        } else
                                                                mod |= FSERROR;
                                                }
                                        }
                                        continue;
                                } else {
                                        /*
                                         * Only one directory entry can point
                                         * to dir->head, it's '.'.
                                         */
                                        if (dirent.head == dir->head) {
                                                pwarn("%s entry in %s has incorrect start cluster\n",
                                                                dirent.name, fullpath(dir));
                                                if (ask(1, "Remove")) {
                                                        *p = SLOT_DELETED;
                                                        mod |= THISMOD|FSDIRMOD;
                                                } else
                                                        mod |= FSERROR;
                                                continue;
                                        } else if ((check_subdirectory(fat,
                                            &dirent) & FSERROR) == FSERROR) {
                                                /*
                                                 * A subdirectory should have
                                                 * a dot (.) entry and a dot-dot
                                                 * (..) entry of ATTR_DIRECTORY,
                                                 * we will inspect further when
                                                 * traversing into it.
                                                 */
                                                if (ask(1, "Remove")) {
                                                        *p = SLOT_DELETED;
                                                        mod |= THISMOD|FSDIRMOD;
                                                } else
                                                        mod |= FSERROR;
                                                continue;
                                        }
                                }

                                /* create directory tree node */
                                if (!(d = newDosDirEntry())) {
                                        perr("No space for directory");
                                        return FSFATAL;
                                }
                                memcpy(d, &dirent, sizeof(struct dosDirEntry));
                                /* link it into the tree */
                                dir->child = d;

                                /* Enter this directory into the todo list */
                                if (!(n = newDirTodo())) {
                                        perr("No space for todo list");
                                        return FSFATAL;
                                }
                                n->next = pendingDirectories;
                                n->dir = d;
                                pendingDirectories = n;
                        } else if (!(mod & FSERROR)) {
                                mod |= k = checksize(fat, p, &dirent);
                                if (k & FSDIRMOD)
                                        mod |= THISMOD;
                        }
                        boot->NumFiles++;
                }

                if (is_legacyroot) {
                        /*
                         * Don't bother to write back right now because
                         * we may continue to make modification to the
                         * non-FAT32 root directory below.
                         */
                        break;
                } else if (mod & THISMOD) {
                        if (lseek(fd, off, SEEK_SET) != off
                            || write(fd, buffer, iosize) != iosize) {
                                perr("Unable to write directory");
                                return FSFATAL;
                        }
                        mod &= ~THISMOD;
                }
        } while (fat_is_valid_cl(fat, (cl = fat_get_cl_next(fat, cl))));
        if (invlfn || vallfn)
                mod |= removede(fat,
                                invlfn ? invlfn : vallfn, p,
                                invlfn ? invcl : valcl, -1, 0,
                                fullpath(dir), 1);

        /*
         * The root directory of non-FAT32 filesystems is in a special
         * area and may have been modified above removede() without
         * being written out.
         */
        if ((mod & FSDIRMOD) && is_legacyroot) {
                if (lseek(fd, off, SEEK_SET) != off
                    || write(fd, buffer, iosize) != iosize) {
                        perr("Unable to write directory");
                        return FSFATAL;
                }
                mod &= ~THISMOD;
        }
        return mod & ~THISMOD;
}

int
handleDirTree(struct fat_descriptor *fat)
{
        int mod;

        mod = readDosDirSection(fat, rootDir);
        if (mod & FSFATAL)
                return FSFATAL;

        /*
         * process the directory todo list
         */
        while (pendingDirectories) {
                struct dosDirEntry *dir = pendingDirectories->dir;
                struct dirTodoNode *n = pendingDirectories->next;

                /*
                 * remove TODO entry now, the list might change during
                 * directory reads
                 */
                freeDirTodo(pendingDirectories);
                pendingDirectories = n;

                /*
                 * handle subdirectory
                 */
                mod |= readDosDirSection(fat, dir);
                if (mod & FSFATAL)
                        return FSFATAL;
        }

        return mod;
}

/*
 * Try to reconnect a FAT chain into dir
 */
static u_char *lfbuf;
static cl_t lfcl;
static off_t lfoff;

int
reconnect(struct fat_descriptor *fat, cl_t head, size_t length)
{
        struct bootblock *boot = fat_get_boot(fat);
        struct dosDirEntry d;
        int len, dosfs;
        u_char *p;

        dosfs = fat_get_fd(fat);

        if (!ask(1, "Reconnect"))
                return FSERROR;

        if (!lostDir) {
                for (lostDir = rootDir->child; lostDir; lostDir = lostDir->next) {
                        if (!strcmp(lostDir->name, LOSTDIR))
                                break;
                }
                if (!lostDir) {         /* Create LOSTDIR?              XXX */
                        pwarn("No %s directory\n", LOSTDIR);
                        return FSERROR;
                }
        }
        if (!lfbuf) {
                lfbuf = malloc(boot->ClusterSize);
                if (!lfbuf) {
                        perr("No space for buffer");
                        return FSFATAL;
                }
                p = NULL;
        } else
                p = lfbuf;
        while (1) {
                if (p)
                        for (; p < lfbuf + boot->ClusterSize; p += 32)
                                if (*p == SLOT_EMPTY
                                    || *p == SLOT_DELETED)
                                        break;
                if (p && p < lfbuf + boot->ClusterSize)
                        break;
                lfcl = p ? fat_get_cl_next(fat, lfcl) : lostDir->head;
                if (lfcl < CLUST_FIRST || lfcl >= boot->NumClusters) {
                        /* Extend LOSTDIR?                              XXX */
                        pwarn("No space in %s\n", LOSTDIR);
                        lfcl = (lostDir->head < boot->NumClusters) ? lostDir->head : 0;
                        return FSERROR;
                }
                lfoff = (lfcl - CLUST_FIRST) * boot->ClusterSize
                    + boot->FirstCluster * boot->bpbBytesPerSec;

                if (lseek(dosfs, lfoff, SEEK_SET) != lfoff
                    || (size_t)read(dosfs, lfbuf, boot->ClusterSize) != boot->ClusterSize) {
                        perr("could not read LOST.DIR");
                        return FSFATAL;
                }
                p = lfbuf;
        }

        boot->NumFiles++;
        /* Ensure uniqueness of entry here!                             XXX */
        memset(&d, 0, sizeof d);
        /* worst case -1 = 4294967295, 10 digits */
        len = snprintf(d.name, sizeof(d.name), "%u", head);
        d.flags = 0;
        d.head = head;
        d.size = length * boot->ClusterSize;

        memcpy(p, d.name, len);
        memset(p + len, ' ', 11 - len);
        memset(p + 11, 0, 32 - 11);
        p[26] = (u_char)d.head;
        p[27] = (u_char)(d.head >> 8);
        if (boot->ClustMask == CLUST32_MASK) {
                p[20] = (u_char)(d.head >> 16);
                p[21] = (u_char)(d.head >> 24);
        }
        p[28] = (u_char)d.size;
        p[29] = (u_char)(d.size >> 8);
        p[30] = (u_char)(d.size >> 16);
        p[31] = (u_char)(d.size >> 24);
        if (lseek(dosfs, lfoff, SEEK_SET) != lfoff
            || (size_t)write(dosfs, lfbuf, boot->ClusterSize) != boot->ClusterSize) {
                perr("could not write LOST.DIR");
                return FSFATAL;
        }
        return FSDIRMOD;
}

void
finishlf(void)
{
        if (lfbuf)
                free(lfbuf);
        lfbuf = NULL;
}