/*
 * DF-3093 offline detector: FAT cross-link / double-allocation scanner.
 *
 * Parses a FAT12/16/32 image directly (no kernel involvement), walks the
 * root directory (fixed region on FAT12/16, cluster chain on FAT32) and
 * every file/directory chain, and counts the in-degree of every cluster:
 *   +1 for each directory entry whose start cluster is c
 *   +1 for each FAT chain link  FAT[x] == c
 * On a healthy filesystem every cluster 2..maxcluster has in-degree <= 1.
 * Any cluster with in-degree >= 2 means two files (or a file and a
 * directory) share that cluster: the free-cluster allocator handed the
 * same cluster to two chains -- exactly what the missing MSDOSFS_LOCK_MP
 * allows.  Also reports out-of-range links and chain/size mismatches.
 *
 * build: cc -O2 -o fat_scan fat_scan.c
 * usage: ./fat_scan image.img
 * exit:  0 clean, 1 cross-link/corruption found, 2 parse error
 */
#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include <string.h>
#include <stdint.h>

static uint8_t *img;
static size_t imgsiz;

static uint16_t rd16(const uint8_t *p)
{
	return ((uint16_t)p[0] | ((uint16_t)p[1] << 8));
}
static uint32_t rd32(const uint8_t *p)
{
	return ((uint32_t)rd16(p) | ((uint32_t)rd16(p + 2) << 16));
}

static unsigned BytsPerSec, SecPerClust, ResSectors, NFats, RootDirEnts;
static unsigned FATSz, TotSec;
static uint32_t MaxClust, FirstDataSec, RootClust;
static int FatBits;		/* 12, 16 or 32 */
static uint32_t *indeg;
static int problems;

static uint32_t
fatent(uint32_t n)
{
	if (FatBits == 32)
		return (rd32(img + (size_t)(ResSectors + (n * 4 / BytsPerSec)) *
		    BytsPerSec + (n * 4) % BytsPerSec) & 0x0fffffff);
	if (FatBits == 16)
		return (rd16(img + (size_t)(ResSectors + (n * 2 / BytsPerSec)) *
		    BytsPerSec + (n * 2) % BytsPerSec));
	{
		uint32_t off = n * 3 / 2;
		uint32_t v = rd16(img + (size_t)(ResSectors +
		    (off / BytsPerSec)) * BytsPerSec + off % BytsPerSec);
		return ((n & 1) ? (v >> 4) : (v & 0xfff));
	}
}

static int
iseof(uint32_t v)
{
	if (FatBits == 32)
		return (v >= 0x0ffffff8);
	if (FatBits == 16)
		return (v >= 0xfff8);
	return (v >= 0xff8);
}

static void
note(const char *fmt, ...)
{
	va_list ap;
	va_start(ap, fmt);
	vprintf(fmt, ap);
	va_end(ap);
	problems++;
}

/* walk one cluster chain; returns chain length in clusters or -1 */
static long
walk_chain(uint32_t start, const char *who)
{
	uint32_t c = start;
	long steps = 0;

	if (start < 2 || start > MaxClust) {
		note("  %s: bad start cluster %u\n", who, start);
		return (-1);
	}
	indeg[start]++;
	while (!iseof(fatent(c))) {
		uint32_t next = fatent(c);
		if (next < 2 || next > MaxClust) {
			note("  %s: FAT[%u]=%u out of range\n", who, c, next);
			return (-1);
		}
		indeg[next]++;
		c = next;
		if (++steps > (long)MaxClust) {
			note("  %s: chain cycles\n", who);
			return (-1);
		}
	}
	return (steps + 1);
}

static void
scan_dir(const uint8_t *p, size_t len, int depth);

static void
scan_dir_cluster(uint32_t clust, int depth)
{
	while (clust >= 2 && clust <= MaxClust) {
		uint32_t sec = FirstDataSec + (clust - 2) * SecPerClust;
		if ((sec + SecPerClust) * (size_t)BytsPerSec <= imgsiz)
			scan_dir(img + (size_t)sec * BytsPerSec,
			    (size_t)SecPerClust * BytsPerSec, depth);
		clust = fatent(clust);
		if (iseof(clust))
			break;
	}
}

static void
scan_dir(const uint8_t *p, size_t len, int depth)
{
	size_t o;
	char who[64];

	for (o = 0; o + 32 <= len; o += 32) {
		const uint8_t *de = p + o;
		uint32_t s;
		uint32_t fsz;
		long clen;
		unsigned attr;

		if (de[0] == 0x00)
			break;		/* end of directory */
		if (de[0] == 0xE5)
			continue;	/* deleted */
		attr = de[11];
		if (attr == 0x0F)
			continue;	/* LFN fragment */
		if (attr & 0x08)
			continue;	/* volume label */
		s = rd16(de + 26);
		if (FatBits == 32)
			s |= (uint32_t)rd16(de + 20) << 16;
		fsz = rd32(de + 28);
		snprintf(who, sizeof(who), "'%.11s'", (const char *)de);

		if (attr & 0x10) {	/* subdirectory */
			if (depth < 4)
				scan_dir_cluster(s, depth + 1);
			continue;
		}
		if (s == 0)
			continue;	/* empty file */
		clen = walk_chain(s, who);
		if (clen > 0 && fsz > 0) {
			unsigned long want = (fsz +
			    (unsigned long)SecPerClust * BytsPerSec - 1) /
			    ((unsigned long)SecPerClust * BytsPerSec);
			if ((unsigned long)clen != want)
				note("  %s: chain %ld clusters but size %u "
				    "wants %lu\n", who, clen, fsz, want);
		}
	}
}

int
main(int argc, char **argv)
{
	FILE *f;
	uint32_t n, clcount;
	unsigned rootsecs, tot16;
	uint32_t tot32;
	int i;

	if (argc != 2) {
		fprintf(stderr, "usage: %s image.img\n", argv[0]);
		return (2);
	}
	f = fopen(argv[1], "rb");
	if (!f) { perror("fopen"); return (2); }
	fseek(f, 0, SEEK_END);
	imgsiz = ftell(f);
	fseek(f, 0, SEEK_SET);
	img = malloc(imgsiz);
	if (fread(img, 1, imgsiz, f) != imgsiz) {
		fprintf(stderr, "short read\n");
		return (2);
	}
	fclose(f);

	BytsPerSec = rd16(img + 11);
	SecPerClust = img[13];
	ResSectors = rd16(img + 14);
	NFats = img[16];
	RootDirEnts = rd16(img + 17);
	tot16 = rd16(img + 19);
	FATSz = rd16(img + 22);
	tot32 = rd32(img + 32);
	TotSec = tot16 ? tot16 : tot32;
	RootClust = rd32(img + 44);
	if (BytsPerSec != 512 || SecPerClust == 0 || NFats == 0 ||
	    (FATSz == 0 && tot32 == 0)) {
		fprintf(stderr, "unparseable BPB\n");
		return (2);
	}
	if (FATSz == 0)
		FATSz = rd32(img + 36);	/* FAT32 FATSz32 */

	FirstDataSec = ResSectors + NFats * FATSz +
	    (RootDirEnts * 32 + BytsPerSec - 1) / BytsPerSec;
	clcount = (TotSec - FirstDataSec) / SecPerClust;
	MaxClust = clcount + 1;
	if (clcount < 4085)
		FatBits = 12;
	else if (clcount < 65525)
		FatBits = 16;
	else
		FatBits = 32;
	printf("fat_scan: %ubits/entry  maxclust=%u  totsec=%u  "
	    "spc=%u  firstdata=%u\n",
	    FatBits, MaxClust, TotSec, SecPerClust, FirstDataSec);

	indeg = calloc(MaxClust + 2, sizeof(*indeg));

	if (FatBits == 32) {
		scan_dir_cluster(RootClust ? RootClust : 2, 0);
	} else {
		rootsecs = (RootDirEnts * 32 + BytsPerSec - 1) / BytsPerSec;
		scan_dir(img + (size_t)(ResSectors + NFats * FATSz) *
		    BytsPerSec, (size_t)rootsecs * BytsPerSec, 0);
	}

	/* in-degree verdict */
	{
		int worst = 0;
		uint32_t wc = 0;
		for (n = 2; n <= MaxClust; n++) {
			if (indeg[n] > worst) {
				worst = indeg[n];
				wc = n;
			}
		}
		printf("fat_scan: max in-degree = %d (cluster %u)\n",
		    worst, wc);
		if (worst >= 2) {
			int shown = 0;
			note("  clusters with in-degree >= 2:");
			for (n = 2; n <= MaxClust && shown < 16; n++)
				if (indeg[n] >= 2) {
					printf(" %u(%u)", n, indeg[n]);
					shown++;
				}
			printf("%s\n", shown ? "" : " ...");
		}
	}

	if (problems) {
		printf("fat_scan: CORRUPTION FOUND (%d problem[s])\n",
		    problems);
		return (1);
	}
	printf("fat_scan: clean (no cross-links)\n");
	return (0);
}