/*
 * dir.c
 *
 * Copyright (C) 1995-1997, 1999 Martin von Lwis
 * Copyright (C) 1999 Steve Dodd
 * Copyright (C) 1999 Joseph Malicki
 * Copyright (C) 2001 Anton Altaparmakov (AIA)
 */

#include "ntfstypes.h"
#include "struct.h"
#include "dir.h"
#include "macros.h"

#include <linux/errno.h>
#include "super.h"
#include "inode.h"
#include "attr.h"
#include "support.h"
#include "util.h"
#include <linux/smp_lock.h>
#include <linux/bitops.h>

static char I30[] = "$I30";

/* An index record should start with INDX, and the last word in each block
 * should contain the check value. If it passes, the original values need to
 * be restored. */
int ntfs_check_index_record(ntfs_inode *ino, char *record)
{
	return ntfs_fixup_record(record, "INDX", ino->u.index.recordsize);
}

static inline int ntfs_is_top(ntfs_u64 stack)
{
	return stack == 14;
}

static int ntfs_pop(ntfs_u64 *stack)
{
	static int width[16] = {1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,-1};
	int res = -1;
	
	switch (width[*stack & 15]) {
	case 1:
		res = (int)((*stack & 15) >> 1);
		*stack >>= 4;
		break;
	case 2:
		res = (int)(((*stack & 63) >> 2) + 7);
		*stack >>= 6;
		break;
	case 3:
		res = (int)(((*stack & 255) >> 3) + 23);
		*stack >>= 8;
		break;
	case 4:
		res = (int)(((*stack & 1023) >> 4) + 55);
		*stack >>= 10;
		break;
	default:
		ntfs_error("Unknown encoding\n");
	}
	return res;
}

static inline unsigned int ntfs_top(void)
{
	return 14;
}

static ntfs_u64 ntfs_push(ntfs_u64 stack, int i)
{
	if (i < 7)
		return (stack << 4) | (i << 1);
	if (i < 23)
		return (stack << 6) | ((i - 7) << 2) | 1;
	if (i < 55)
		return (stack << 8) | ((i - 23) << 3) | 3;
	if (i < 120)
		return (stack << 10) | ((i - 55) << 4) | 7;
	ntfs_error("Too many entries\n");
	return ~((ntfs_u64)0);
}

#if 0
static void ntfs_display_stack(ntfs_u64 stack)
{
	while(!ntfs_is_top(stack))
	{
		printf("%d ", ntfs_pop(&stack));
	}
	printf("\n");
}
#endif

/* True if the entry points to another block of entries. */
static inline int ntfs_entry_has_subnodes(char *entry)
{
	return (NTFS_GETU16(entry + 0xc) & 1);
}

/* True if it is not the 'end of dir' entry. */
static inline int ntfs_entry_is_used(char *entry)
{
	return !(NTFS_GETU16(entry + 0xc) & 2);
}

/*
 * Removed RACE for allocating index blocks. But stil not too happy.
 * There might be more races afterwards. (AIA)
 */
static int ntfs_allocate_index_block(ntfs_iterate_s *walk)
{
	ntfs_attribute *allocation, *bitmap = 0;
	int error, size, i, bit;
	ntfs_u8 *bmap;
	ntfs_io io;
	ntfs_volume *vol = walk->dir->vol;

	/* Check for allocation attribute. */
	allocation = ntfs_find_attr(walk->dir, vol->at_index_allocation, I30);
	if (!allocation) {
		ntfs_u8 bmp[8];
		/* Create index allocation attribute. */
		error = ntfs_create_attr(walk->dir, vol->at_index_allocation,
					 I30, 0, 0, &allocation);
		if (error)
			goto err_ret;
		ntfs_bzero(bmp, sizeof(bmp));
		error = ntfs_create_attr(walk->dir, vol->at_bitmap, I30, bmp,
					 sizeof(bmp), &bitmap);
		if (error)
			goto err_ret;
	} else
		bitmap = ntfs_find_attr(walk->dir, vol->at_bitmap, I30);
	if (!bitmap) {
		ntfs_error("Directory w/o bitmap\n");
		error = -EINVAL;
		goto err_ret;
	}
	size = bitmap->size;
	bmap = ntfs_malloc(size);
	if (!bmap) {
		error = -ENOMEM;
		goto err_ret;
	}
	io.fn_put = ntfs_put;
	io.fn_get = ntfs_get;
try_again:
	io.param = bmap;
	io.size = size;
	error = ntfs_read_attr(walk->dir, vol->at_bitmap, I30, 0, &io);
	if (error || (io.size != size && (error = -EIO, 1)))
		goto err_fb_out;
	/* Allocate a bit. */
	for (bit = i = 0; i < size; i++) {
		if (bmap[i] == 0xFF)
			continue;
		bit = ffz(bmap[i]);
		if (bit < 8)
			break;
	}
	if (i >= size) {
		/* FIXME: Extend bitmap. */
		error = -EOPNOTSUPP;
		goto err_fb_out;
	}
	/* Get the byte containing our bit again, now taking the BKL. */
	io.param = bmap;
	io.size = 1;
	lock_kernel();
	error = ntfs_read_attr(walk->dir, vol->at_bitmap, I30, i, &io);
	if (error || (io.size != 1 && (error = -EIO, 1)))
		goto err_unl_out;
	if (ntfs_test_and_set_bit(bmap, bit)) {
		unlock_kernel();
		/* Give other process(es) a chance to finish. */
		schedule();
		goto try_again;
	}
	walk->newblock = (i * 8 + bit) * walk->dir->u.index.clusters_per_record;
	io.param = bmap;
	error = ntfs_write_attr(walk->dir, vol->at_bitmap, I30, i, &io);
	if (error || (io.size != size && (error = -EIO, 1)))
		goto err_unl_out;
	/* Change inode on disk, required when bitmap is resident. */
	error = ntfs_update_inode(walk->dir);
	if (error)
		goto err_unl_out;
	unlock_kernel();
	ntfs_free(bmap);
	/* Check whether record is out of allocated range. */
	size = allocation->size;
	if (walk->newblock * vol->cluster_size >= size) {
		/* Build index record. */
		int hsize;
		int s1 = walk->dir->u.index.recordsize;
		int nr_fix = (s1 >> vol->sector_size) + 1;
		char *record = ntfs_malloc(s1);
		if (!record) {
			error = -ENOMEM;
			goto err_ret;
		}
		ntfs_bzero(record, s1);
		/* Magic */
		ntfs_memcpy(record, "INDX", 4);
		/* Offset to fixups */
		NTFS_PUTU16(record + 4, 0x28);
		/* Number of fixups. */
		NTFS_PUTU16(record + 6, nr_fix);
		/* Log file sequence number - We don't do journalling so we
		 * just set it to zero which should be the Right Thing. (AIA) */
		NTFS_PUTU64(record + 8, 0);
		/* VCN of buffer */
		NTFS_PUTU64(record + 0x10, walk->newblock);
		/* Header size. */
		hsize = 0x10 + 2 * nr_fix;
		hsize = (hsize + 7) & ~7; /* Align. */
		NTFS_PUTU16(record + 0x18, hsize);
		/* Total size of record. */
		NTFS_PUTU32(record + 0x20, s1 - 0x18);
		/* Writing the data will extend the attribute. */
		io.param = record;
		io.size = s1;
		io.do_read = 0;
		error = ntfs_readwrite_attr(walk->dir, allocation, size, &io);
		ntfs_free(record);
		if (error || (io.size != s1 && (error = -EIO, 1)))
			goto err_ret;
		error = ntfs_update_inode(walk->dir);
		if (error)
			goto err_ret;
	}
	return 0;
err_unl_out:
	unlock_kernel();
err_fb_out:
	ntfs_free(bmap);
err_ret:
	return error;
}

/* Write an index block (root or allocation) back to storage.
 * Used is the total number of bytes in buf, including all headers. */
static int ntfs_index_writeback(ntfs_iterate_s *walk, ntfs_u8 *buf, int block,
				int used)
{
	ntfs_io io;
	int error;
	ntfs_attribute *a;
	ntfs_volume *vol = walk->dir->vol;
	
	io.fn_put = 0;
	io.fn_get = ntfs_get;
	io.param = buf;
	if (block == -1) {	/* Index root. */
		NTFS_PUTU16(buf + 0x14, used - 0x10);
		/* 0x18 is a copy thereof. */
		NTFS_PUTU16(buf + 0x18, used - 0x10);
		io.size = used;
		error = ntfs_write_attr(walk->dir, vol->at_index_root, I30, 0,
					&io);
		if (error || (io.size != used && (error = -EIO, 1)))
			return error;
		/* Shrink if necessary. */
		a = ntfs_find_attr(walk->dir, vol->at_index_root, I30);
		ntfs_resize_attr(walk->dir, a, used);
	} else {
		NTFS_PUTU16(buf + 0x1C, used - 0x18);
		io.size = walk->dir->u.index.recordsize;
		error = ntfs_insert_fixups(buf, io.size);
		if (error) {
			printk(KERN_ALERT "NTFS: ntfs_index_writeback() caught "
					"corrupt index record ntfs record "
					"header. Refusing to write corrupt "
					"data to disk. Unmount and run chkdsk "
					"immediately!\n");
			return -EIO;
		}
		error = ntfs_write_attr(walk->dir, vol->at_index_allocation,
				I30, (__s64)block << vol->cluster_size_bits,
				&io);
		if (error || (io.size != walk->dir->u.index.recordsize &&
				(error = -EIO, 1)))
			return error;
	}
	return 0;
}

static int ntfs_split_record(ntfs_iterate_s *walk, char *start, int bsize,
			     int usize)
{
	char *entry, *prev;
	ntfs_u8 *newbuf = 0, *middle = 0;
	int error, othersize, mlen;
	ntfs_io io;
	ntfs_volume *vol = walk->dir->vol;
	int oldblock;

	error = ntfs_allocate_index_block(walk);
	if (error)
		return error;
	/* This should not happen. */
	if (walk->block == -1) {
		ntfs_error("Trying to split root");
		return -EOPNOTSUPP;
	}
	entry = start + NTFS_GETU16(start + 0x18) + 0x18; 
	for (prev = entry; entry - start < usize / 2; 
					       entry += NTFS_GETU16(entry + 8))
		prev = entry;
	newbuf = ntfs_malloc(vol->index_record_size);
	if (!newbuf)
		return -ENOMEM;
	io.fn_put = ntfs_put;
	io.fn_get = ntfs_get;
	io.param = newbuf;
	io.size = vol->index_record_size;
	/* Read in old header. FIXME: Reading everything is overkill. */
	error = ntfs_read_attr(walk->dir, vol->at_index_allocation, I30,
			(__s64)walk->newblock << vol->cluster_size_bits, &io);
	if (error)
		goto out;
	if (io.size != vol->index_record_size) {
		error = -EIO;
		goto out;
	}
	/* FIXME: Adjust header. */
	/* Copy everything from entry to new block. */
	othersize = usize - (entry - start);
	ntfs_memcpy(newbuf + NTFS_GETU16(newbuf + 0x18) + 0x18, entry,
								    othersize);
	/* Copy flags. */
	NTFS_PUTU32(newbuf + 0x24, NTFS_GETU32(start + 0x24));
	error = ntfs_index_writeback(walk, newbuf, walk->newblock,
				othersize + NTFS_GETU16(newbuf + 0x18) + 0x18);
	if (error)
		goto out;
	/* Move prev to walk. */
	mlen = NTFS_GETU16(prev + 0x8);
	/* Remember old child node. */
	if (ntfs_entry_has_subnodes(prev))
		oldblock = NTFS_GETU32(prev + mlen - 8);
	else
		oldblock = -1;
	/* Allow for pointer to subnode. */
	middle = ntfs_malloc(ntfs_entry_has_subnodes(prev) ? mlen : mlen + 8);
	if (!middle){
		error = -ENOMEM;
		goto out;
	}
	ntfs_memcpy(middle, prev, mlen);
	/* Set has_subnodes flag. */
	NTFS_PUTU8(middle + 0xC, NTFS_GETU8(middle + 0xC) | 1);
	/* Middle entry points to block, parent entry will point to newblock. */
	NTFS_PUTU64(middle + mlen - 8, walk->block);
	if (walk->new_entry)
		ntfs_error("Entry not reset");
	walk->new_entry = middle;
	walk->u.flags |= ITERATE_SPLIT_DONE;
	/* Terminate old block. */
	othersize = usize - (prev-start);
	NTFS_PUTU64(prev, 0);
	if (oldblock == -1) {
		NTFS_PUTU32(prev + 8, 0x10);
		NTFS_PUTU32(prev + 0xC, 2);
		othersize += 0x10;
	} else {
		NTFS_PUTU32(prev + 8, 0x18);
		NTFS_PUTU32(prev + 0xC, 3);
		NTFS_PUTU64(prev + 0x10, oldblock);
		othersize += 0x18;
	}
	/* Write back original block. */
	error = ntfs_index_writeback(walk, start, walk->block, othersize);
 out:
	if (newbuf)
		ntfs_free(newbuf);
	if (middle)
		ntfs_free(middle);
	return error;
}

static int ntfs_dir_insert(ntfs_iterate_s *walk, char *start, char* entry)
{
	int blocksize, usedsize, error, offset;
	int do_split = 0;
	offset = entry - start;
	if (walk->block == -1) { /* index root */
		blocksize = walk->dir->vol->mft_record_size;
		usedsize = NTFS_GETU16(start + 0x14) + 0x10;
	} else {
		blocksize = walk->dir->u.index.recordsize;
		usedsize = NTFS_GETU16(start + 0x1C) + 0x18;
	}
	if (usedsize + walk->new_entry_size > blocksize) {
		char* s1 = ntfs_malloc(blocksize + walk->new_entry_size);
		if (!s1)
			return -ENOMEM;
		ntfs_memcpy(s1, start, usedsize);
		do_split = 1;
		/* Adjust entry to s1. */
		entry = s1 + (entry - start);
		start = s1;
	}
	ntfs_memmove(entry + walk->new_entry_size, entry, usedsize - offset);
	ntfs_memcpy(entry, walk->new_entry, walk->new_entry_size);
	usedsize += walk->new_entry_size;
	ntfs_free(walk->new_entry);
	walk->new_entry = 0;
	if (do_split) {
		error = ntfs_split_record(walk, start, blocksize, usedsize);
		ntfs_free(start);
	} else {
		error = ntfs_index_writeback(walk, start, walk->block,usedsize);
		if (error)
			return error;
	}
	return 0;
}

/* Try to split INDEX_ROOT attributes. Return -E2BIG if nothing changed. */
int ntfs_split_indexroot(ntfs_inode *ino)
{
	ntfs_attribute *ra;
	ntfs_u8 *root = 0, *index = 0;
	ntfs_io io;
	int error, off, i, bsize, isize;
	ntfs_iterate_s walk;

	ra = ntfs_find_attr(ino, ino->vol->at_index_root, I30);
	if (!ra)
		return -ENOTDIR;
	bsize = ino->vol->mft_record_size;
	root = ntfs_malloc(bsize);
	if (!root)
		return -E2BIG;
	io.fn_put = ntfs_put;
	io.param = root;
	io.size = bsize;
	error = ntfs_read_attr(ino, ino->vol->at_index_root, I30, 0, &io);
	if (error)
		goto out;
	off = 0x20;
	/* Count number of entries. */
	for (i = 0; ntfs_entry_is_used(root + off); i++)
		off += NTFS_GETU16(root + off + 8);
	if (i <= 2) {
		/* We don't split small index roots. */
		error = -E2BIG;
		goto out;
	}
	index = ntfs_malloc(ino->vol->index_record_size);
	if (!index) {
		error = -ENOMEM;
		goto out;
	}
	walk.dir = ino;
	walk.block = -1;
	walk.result = walk.new_entry = 0;
	walk.name = 0;
	error = ntfs_allocate_index_block(&walk);
	if (error)
		goto out;
	/* Write old root to new index block. */
	io.param = index;
	io.size = ino->vol->index_record_size;
	error = ntfs_read_attr(ino, ino->vol->at_index_allocation, I30,
		(__s64)walk.newblock << ino->vol->cluster_size_bits, &io);
	if (error)
		goto out;
	isize = NTFS_GETU16(root + 0x18) - 0x10;
	ntfs_memcpy(index + NTFS_GETU16(index + 0x18) + 0x18, root+0x20, isize);
	/* Copy flags. */
	NTFS_PUTU32(index + 0x24, NTFS_GETU32(root + 0x1C));
	error = ntfs_index_writeback(&walk, index, walk.newblock, 
				     isize + NTFS_GETU16(index + 0x18) + 0x18);
	if (error)
		goto out;
	/* Mark root as split. */
	NTFS_PUTU32(root + 0x1C, 1);
	/* Truncate index root. */
	NTFS_PUTU64(root + 0x20, 0);
	NTFS_PUTU32(root + 0x28, 0x18);
	NTFS_PUTU32(root + 0x2C, 3);
	NTFS_PUTU64(root + 0x30, walk.newblock);
	error = ntfs_index_writeback(&walk, root, -1, 0x38);
 out:
	ntfs_free(root);
	ntfs_free(index);
	return error;
}

/* The entry has been found. Copy the result in the caller's buffer */
static int ntfs_copyresult(char *dest, char *source)
{
	int length = NTFS_GETU16(source + 8);
	ntfs_memcpy(dest, source, length);
	return 1;
}

/* Use $UpCase some day. */
static inline unsigned short ntfs_my_toupper(ntfs_volume *vol, ntfs_u16 x)
{
	/* We should read any pending rest of $UpCase here. */
	if (x >= vol->upcase_length)
		return x;
	return vol->upcase[x];
}

/* Everything passed in walk and entry. */
static int ntfs_my_strcmp(ntfs_iterate_s *walk, const unsigned char *entry)
{
	int lu = *(entry + 0x50);
	int i;

	ntfs_u16* name = (ntfs_u16*)(entry + 0x52);
	ntfs_volume *vol = walk->dir->vol;
	for (i = 0; i < lu && i < walk->namelen; i++)
		if (ntfs_my_toupper(vol, NTFS_GETU16(name + i)) != 
			     ntfs_my_toupper(vol, NTFS_GETU16(walk->name + i)))
			break;
	if (i == lu && i == walk->namelen)
		return 0;
	if (i == lu)
		return 1;
	if (i == walk->namelen)
		return -1;
	if (ntfs_my_toupper(vol, NTFS_GETU16(name + i)) < 
			    ntfs_my_toupper(vol, NTFS_GETU16(walk->name + i)))
		return 1;
	return -1;
}

/* Necessary forward declaration. */
static int ntfs_getdir_iterate(ntfs_iterate_s *walk, char *start, char *entry);

/* Parse a block of entries. Load the block, fix it up, and iterate over the
 * entries. The block is given as virtual cluster number. */
static int ntfs_getdir_record(ntfs_iterate_s *walk, int block)
{
	int length = walk->dir->u.index.recordsize;
	char *record = (char*)ntfs_malloc(length);
	char *offset;
	int retval,error;
	int oldblock;
	ntfs_io io;

	if (!record)
		return -ENOMEM;
	io.fn_put = ntfs_put;
	io.param = record;
	io.size = length;
	/* Read the block from the index allocation attribute. */
	error = ntfs_read_attr(walk->dir, walk->dir->vol->at_index_allocation,
		I30, (__s64)block << walk->dir->vol->cluster_size_bits, &io);
	if (error || io.size != length) {
		ntfs_error("read failed\n");
		ntfs_free(record);
		return 0;
	}
	if (!ntfs_check_index_record(walk->dir, record)) {
		ntfs_error("%x is not an index record\n", block);
		ntfs_free(record);
		return 0;
	}
	offset = record + NTFS_GETU16(record + 0x18) + 0x18;
	oldblock = walk->block;
	walk->block = block;
	retval = ntfs_getdir_iterate(walk, record, offset);
	walk->block = oldblock;
	ntfs_free(record);
	return retval;
}

/* Go down to the next block of entries. These collate before the current
 * entry. */
static int ntfs_descend(ntfs_iterate_s *walk, ntfs_u8 *start, ntfs_u8 *entry)
{
	int length = NTFS_GETU16(entry + 8);
	int nextblock = NTFS_GETU32(entry + length - 8);
	int error;

	if (!ntfs_entry_has_subnodes(entry)) {
		ntfs_error("illegal ntfs_descend call\n");
		return 0;
	}
	error = ntfs_getdir_record(walk, nextblock);
	if (!error && walk->type == DIR_INSERT && 
	    (walk->u.flags & ITERATE_SPLIT_DONE)) {
		/* Split has occurred. Adjust entry, insert new_entry. */
		NTFS_PUTU32(entry + length - 8, walk->newblock);
		/* Reset flags, as the current block might be split again. */
		walk->u.flags &= ~ITERATE_SPLIT_DONE;
		error = ntfs_dir_insert(walk, start, entry);
	}
	return error;
}

static int ntfs_getdir_iterate_byposition(ntfs_iterate_s *walk, char* start,
					  char *entry)
{
	int retval = 0;
	int curpos = 0, destpos = 0;
	int length;
	if (walk->u.pos != 0) {
		if (ntfs_is_top(walk->u.pos))
			return 0;
		destpos = ntfs_pop(&walk->u.pos);
	}
	while (1) {
		if (walk->u.pos == 0) {
			if (ntfs_entry_has_subnodes(entry))
				ntfs_descend(walk, start, entry);
			else
				walk->u.pos = ntfs_top();
			if (ntfs_is_top(walk->u.pos) && 
			    !ntfs_entry_is_used(entry))
				return 1;
			walk->u.pos = ntfs_push(walk->u.pos, curpos);
			return 1;
		}
		if (curpos == destpos) {
			if (!ntfs_is_top(walk->u.pos) && 
			    ntfs_entry_has_subnodes(entry)) {
				retval = ntfs_descend(walk, start, entry);
				if (retval) {
					walk->u.pos = ntfs_push(walk->u.pos,
								curpos);
					return retval;
				}
				if (!ntfs_entry_is_used(entry))
					return 0;
				walk->u.pos = 0;
			}
			if (ntfs_entry_is_used(entry)) {
				retval = ntfs_copyresult(walk->result, entry);
				walk->u.pos = 0;
			} else {
				walk->u.pos = ntfs_top();
				return 0;
			}
		}
		curpos++;
		if (!ntfs_entry_is_used(entry))
			break;
		length = NTFS_GETU16(entry + 8);
		if (!length) {
			ntfs_error("infinite loop\n");
			break;
		}
		entry += length;
	}
	return -1;
}
	
/* Iterate over a list of entries, either from an index block, or from the
 * index root.
 * If searching BY_POSITION, pop the top index from the position. If the
 * position stack is empty then, return the item at the index and set the
 * position to the next entry. If the position stack is not empty, 
 * recursively proceed for subnodes. If the entry at the position is the
 * 'end of dir' entry, return 'not found' and the empty stack.
 * If searching BY_NAME, walk through the items until found or until
 * one item is collated after the requested item. In the former case, return
 * the result. In the latter case, recursively proceed to the subnodes.
 * If 'end of dir' is reached, the name is not in the directory */
static int ntfs_getdir_iterate(ntfs_iterate_s *walk, char *start, char *entry)
{
	int length;
	int cmp;

	if (walk->type == BY_POSITION)
		return ntfs_getdir_iterate_byposition(walk, start, entry);
	do {
		/* If the current entry is a real one, compare with the
		 * requested item. If the current entry is the last item, it
		 * is always larger than the requested item. */
		cmp = ntfs_entry_is_used(entry) ? 
						ntfs_my_strcmp(walk,entry) : -1;
		switch (walk->type) {
		case BY_NAME:
			switch (cmp) {
			case -1:
				return ntfs_entry_has_subnodes(entry) ?
					ntfs_descend(walk, start, entry) : 0;
			case  0:
				return ntfs_copyresult(walk->result, entry);
			case  1:
				break;
			}
			break;
		case DIR_INSERT:
			switch (cmp) {
			case -1:
				return ntfs_entry_has_subnodes(entry) ?
					ntfs_descend(walk, start, entry) :
					ntfs_dir_insert(walk, start, entry);
			case  0:
				return -EEXIST;
			case  1:
				break;
			}
			break;
		default:
			ntfs_error("TODO\n"); /* FIXME: ? */
		}
		if (!ntfs_entry_is_used(entry))
			break;
		length = NTFS_GETU16(entry + 8);
		if (!length) {
			ntfs_error("infinite loop\n");
			break;
		}
		entry += length;
	} while (1);
	return 0;
}

/*  Tree walking is done using position numbers. The following numbers have a
 *  special meaning:
 *       0   start (.)
 *      -1   no more entries
 *      -2   ..
 *  All other numbers encode sequences of indices. The sequence a, b, c is 
 *  encoded as <stop><c><b><a>, where <foo> is the encoding of foo. The
 *  first few integers are encoded as follows:
 *      0:    0000    1:    0010    2:    0100    3:    0110
 *      4:    1000    5:    1010    6:    1100 stop:    1110
 *      7:  000001    8:  000101    9:  001001   10:  001101
 *  The least significant bits give the width of this encoding, the other bits
 *  encode the value, starting from the first value of the interval.
 *   tag     width  first value  last value
 *   0       3      0            6
 *   01      4      7            22
 *   011     5      23           54
 *   0111    6      55           119
 *   More values are hopefully not needed, as the file position has currently
 *   64 bits in total. */

/* Find an entry in the directory. Return 0 if not found, otherwise copy the
 * entry to the result buffer. */
int ntfs_getdir(ntfs_iterate_s *walk)
{
	int length = walk->dir->vol->mft_record_size;
	int retval, error;
	/* Start at the index root. */
	char *root = ntfs_malloc(length);
	ntfs_io io;

	if (!root)
		return -ENOMEM;
	io.fn_put = ntfs_put;
	io.param = root;
	io.size = length;
	error = ntfs_read_attr(walk->dir, walk->dir->vol->at_index_root, I30,
			       0, &io);
	if (error) {
		ntfs_error("Not a directory\n");
		return 0;
	}
	walk->block = -1;
	/* FIXME: Move these to walk. */
	walk->dir->u.index.recordsize = NTFS_GETU32(root + 0x8);
	walk->dir->u.index.clusters_per_record = NTFS_GETU32(root + 0xC);
	/* FIXME: Consistency check. */
	/* Skip header. */
	retval = ntfs_getdir_iterate(walk, root, root + 0x20);
	ntfs_free(root);
	return retval;
}

/* Find an entry in the directory by its position stack. Iteration starts
 * if the stack is 0, in which case the position is set to the first item
 * in the directory. If the position is nonzero, return the item at the
 * position and change the position to the next item. The position is -1
 * if there are no more items. */
int ntfs_getdir_byposition(ntfs_iterate_s *walk)
{
	walk->type = BY_POSITION;
	return ntfs_getdir(walk);
}

/* Find an entry in the directory by its name. Return 0 if not found. */
int ntfs_getdir_byname(ntfs_iterate_s *walk)
{
	walk->type = BY_NAME;
	return ntfs_getdir(walk);
}

int ntfs_getdir_unsorted(ntfs_inode *ino, u32 *p_high, u32 *p_low,
		int (*cb)(ntfs_u8 *, void *), void *param)
{
	s64 ib_ofs;
	char *buf = 0, *entry = 0;
	ntfs_attribute *attr;
	ntfs_volume *vol;
	int byte, bit, err = 0;
	u32 start, finish, ibs, max_size;
	ntfs_io io;
	u8 ibs_bits;

	if (!ino) {
		ntfs_error(__FUNCTION__ "(): No inode! Returning -EINVAL.\n");
		return -EINVAL;
	}
	vol = ino->vol;
	if (!vol) {
		ntfs_error(__FUNCTION__ "(): Inode 0x%lx has no volume. "
				"Returning -EINVAL.\n", ino->i_number);
		return -EINVAL;
	}
	ntfs_debug(DEBUG_DIR3, __FUNCTION__ "(): Unsorted 1: Entering for "
			"inode 0x%lx, p_high = 0x%x, p_low = 0x%x.\n",
			ino->i_number, *p_high, *p_low);
	if (!*p_high) {
		/* We are still in the index root. */
		buf = ntfs_malloc(io.size = vol->mft_record_size);
		if (!buf)
			return -ENOMEM;
		io.fn_put = ntfs_put;
		io.param = buf;
		err = ntfs_read_attr(ino, vol->at_index_root, I30, 0, &io);
		if (err || !io.size)
			goto read_err_ret;
		ino->u.index.recordsize = ibs = NTFS_GETU32(buf + 0x8);
		ino->u.index.clusters_per_record = NTFS_GETU32(buf + 0xC);
		entry = buf + 0x20;
		ntfs_debug(DEBUG_DIR3, __FUNCTION__ "(): Unsorted 2: In index "
				"root.\n");
		ibs_bits = ffs(ibs) - 1;
		/* Compensate for faked "." and "..". */
		start = 2;
	} else { /* We are in an index record. */
		io.size = ibs = ino->u.index.recordsize;
		buf = ntfs_malloc(ibs);
		if (!buf)
			return -ENOMEM;
		ibs_bits = ffs(ibs) - 1;
		io.fn_put = ntfs_put;
		io.param = buf;
		/*
		 * 0 is index root, index allocation starts at 1 and works in
		 * units of index block size (ibs).
		 */
		ib_ofs = (s64)(*p_high - 1) << ibs_bits;
		err = ntfs_read_attr(ino, vol->at_index_allocation, I30, ib_ofs,
				&io);
		if (err || io.size != ibs)
			goto read_err_ret;
		if (!ntfs_check_index_record(ino, buf)) {
			ntfs_error(__FUNCTION__ "(): Index block 0x%x is not "
					"an index record. Returning "
					"-ENOTDIR.\n", *p_high - 1);
			ntfs_free(buf);
			return -ENOTDIR;
		}
		entry = buf + 0x18 + NTFS_GETU16(buf + 0x18);
		ntfs_debug(DEBUG_DIR3, __FUNCTION__ "(): Unsorted 3: In index "
				"allocation.\n");
		start = 0;
	}
	/* Process the entries. */
	finish = *p_low;
	for (; entry < (buf + ibs) && ntfs_entry_is_used(entry);
			entry += NTFS_GETU16(entry + 8)) {
		if (start < finish) {
			/* Skip entries that were already processed. */
			ntfs_debug(DEBUG_DIR3, __FUNCTION__ "(): Unsorted 4: "
					"Skipping already processed entry "
					"p_high 0x%x, p_low 0x%x.\n", *p_high,
					start);
			start++;
			continue;
		}
		ntfs_debug(DEBUG_DIR3, __FUNCTION__ "(): Unsorted 5: "
				"Processing entry p_high 0x%x, p_low 0x%x.\n",
				*p_high, *p_low);
		if ((err = cb(entry, param))) {
			/* filldir signalled us to stop. */
			ntfs_debug(DEBUG_DIR3, __FUNCTION__ "(): "
					"Unsorted 6: cb returned %i, "
					"returning 0, p_high 0x%x, p_low 0x%x."
					"\n", *p_high, *p_low);
			ntfs_free(buf);
			return 0;
		}
		++*p_low;
	}
	ntfs_debug(DEBUG_DIR3, __FUNCTION__ "(): Unsorted 7: After processing "
			"entries, p_high 0x%x, p_low 0x%x.\n", *p_high, *p_low);
	/* We have to locate the next record. */
	ntfs_free(buf);
	buf = 0;
	*p_low = 0;
	attr = ntfs_find_attr(ino, vol->at_bitmap, I30);
	if (!attr) {
		/* Directory does not have index bitmap and index allocation. */
		*p_high = 0x7fff;
		ntfs_debug(DEBUG_DIR3, __FUNCTION__ "(): Unsorted 8: No index "
				"allocation. Returning 0, p_high 0x7fff, "
				"p_low 0x0.\n");
		return 0;
	}
	max_size = attr->size;
	if (max_size > 0x7fff >> 3) {
		ntfs_error(__FUNCTION__ "(): Directory too large. Visible "
				"length is truncated.\n");
		max_size = 0x7fff >> 3;
	}
	buf = ntfs_malloc(max_size);
	if (!buf)
		return -ENOMEM;
	io.param = buf;
	io.size = max_size;
	err = ntfs_read_attr(ino, vol->at_bitmap, I30, 0, &io);
	if (err || io.size != max_size)
		goto read_err_ret;
	attr = ntfs_find_attr(ino, vol->at_index_allocation, I30);
	if (!attr) {
		ntfs_free(buf);
		ntfs_debug(DEBUG_DIR3, __FUNCTION__ "(): Unsorted 9: Find "
				"attr failed. Returning -EIO.\n");
		return -EIO;
	}
	if (attr->resident) {
		ntfs_free(buf);
		ntfs_debug(DEBUG_DIR3, __FUNCTION__ "(): Unsorted 9.5: IA is "
				"resident. Not allowed. Returning EINVAL.\n");
		return -EINVAL;
	}
	/* Loop while going through non-allocated index records. */
	max_size <<= 3;
	while (1) {
		if (++*p_high >= 0x7fff) {
			ntfs_error(__FUNCTION__ "(): Unsorted 10: Directory "
					"inode 0x%lx overflowed the maximum "
					"number of index allocation buffers "
					"the driver can cope with. Pretending "
					"to be at end of directory.\n",
					ino->i_number);
			goto fake_eod;
		}
		if (*p_high > max_size || (s64)*p_high << ibs_bits >
				attr->initialized) {
fake_eod:
			/* No more index records. */
			*p_high = 0x7fff;
			*p_low = 0;
			ntfs_free(buf);
			ntfs_debug(DEBUG_DIR3, __FUNCTION__ "(): Unsorted "
					"10.5: No more index records. "
					"Returning 0, p_high 0x7fff, p_low "
					"0.\n");
			return 0;
		}
		byte = (ntfs_cluster_t)(*p_high - 1);
		bit = 1 << (byte & 7);
		byte >>= 3;
		if ((buf[byte] & bit))
			break;
	};
	ntfs_debug(DEBUG_DIR3, __FUNCTION__ "(): Unsorted 11: Done. "
			"Returning 0, p_high 0x%x, p_low 0x%x.\n", *p_high,
			*p_low);
	ntfs_free(buf);
	return 0;
read_err_ret:
	if (!err)
		err = -EIO;
	ntfs_error(__FUNCTION__ "(): Read failed. Returning error code %i.\n",
			err);
	ntfs_free(buf);
	return err;
}

int ntfs_dir_add(ntfs_inode *dir, ntfs_inode *new, ntfs_attribute *name)
{
	ntfs_iterate_s walk;
	int nsize, esize;
	ntfs_u8* entry, *ndata;
	int error;

	walk.type = DIR_INSERT;
	walk.dir = dir;
	walk.u.flags = 0;
	nsize = name->size;
	ndata = name->d.data;
	walk.name = (ntfs_u16*)(ndata + 0x42);
	walk.namelen = NTFS_GETU8(ndata + 0x40);
	walk.new_entry_size = esize = (nsize + 0x10 + 7) & ~7;
	walk.new_entry = entry = ntfs_malloc(esize);
	if (!entry)
		return -ENOMEM;
	NTFS_PUTINUM(entry, new);
	NTFS_PUTU16(entry + 0x8, esize); /* Size of entry. */
	NTFS_PUTU16(entry + 0xA, nsize); /* Size of original name attribute. */
	NTFS_PUTU16(entry + 0xC, 0);     /* Flags. */
	NTFS_PUTU16(entry + 0xE, 0);	 /* Reserved. */
	ntfs_memcpy(entry + 0x10, ndata, nsize);
	ntfs_bzero(entry + 0x10 + nsize, esize - 0x10 - nsize);
	error = ntfs_getdir(&walk);
	if (walk.new_entry)
		ntfs_free(walk.new_entry);
	return error;
}

#if 0
int ntfs_dir_add1(ntfs_inode *dir, const char* name, int namelen,
		  ntfs_inode *ino)
{
	ntfs_iterate_s walk;
	int error;
	int nsize;
	char *entry;
	ntfs_attribute *name_attr;
	error = ntfs_decodeuni(dir->vol, name, namelen, &walk.name,
			       &walk.namelen);
	if (error)
		return error;
	/* FIXME: Set flags. */
	walk.type = DIR_INSERT;
	walk.dir = dir;
	/* walk.new = ino; */
	/* Prepare new entry. */
	/* Round up to a multiple of 8. */
	walk.new_entry_size = nsize = ((0x52 + 2 * walk.namelen + 7) / 8) * 8;
	walk.new_entry = entry = ntfs_malloc(nsize);
	if (!entry)
		return -ENOMEM;
	ntfs_bzero(entry, nsize);
	NTFS_PUTINUM(entry, ino);
	NTFS_PUTU16(entry + 8, nsize);
	NTFS_PUTU16(entry + 0xA, 0x42 + 2 * namelen); /* FIXME: Size of name 
						       * attribute. */
	NTFS_PUTU32(entry + 0xC, 0); /* FIXME: D-F? */
	name_attr = ntfs_find_attr(ino, vol->at_file_name, 0);
						    /* FIXME: multiple names */
	if (!name_attr || !name_attr->resident)
		return -EIDRM;
	/* Directory, file stamps, sizes, filename. */
	ntfs_memcpy(entry + 0x10, name_attr->d.data, 0x42 + 2 * namelen);
	error = ntfs_getdir(&walk);
	ntfs_free(walk.name);
	return error;
}
#endif

/* Fills out and creates an INDEX_ROOT attribute. */
int ntfs_add_index_root(ntfs_inode *ino, int type)
{
	ntfs_attribute *da;
	ntfs_u8 data[0x30]; /* 0x20 header, 0x10 last entry. */
	char name[10];

	NTFS_PUTU32(data, type);
	/* Collation rule. 1 == COLLATION_FILENAME */
	NTFS_PUTU32(data + 4, 1);
	NTFS_PUTU32(data + 8, ino->vol->index_record_size);
	NTFS_PUTU32(data + 0xC, ino->vol->index_clusters_per_record);
	/* Byte offset to first INDEX_ENTRY. */
	NTFS_PUTU32(data + 0x10, 0x10);
	/* Size of entries, including header. */
	NTFS_PUTU32(data + 0x14, 0x20);
	NTFS_PUTU32(data + 0x18, 0x20);
	/* No index allocation, yet. */
	NTFS_PUTU32(data + 0x1C, 0);
	/* Add last entry. */
	/* Indexed MFT record. */
	NTFS_PUTU64(data + 0x20, 0);
	/* Size of entry. */
	NTFS_PUTU32(data + 0x28, 0x10);
	/* Flags: Last entry, no child nodes. */
	NTFS_PUTU32(data + 0x2C, 2);
	/* Compute name. */
	ntfs_indexname(name, type);
	return ntfs_create_attr(ino, ino->vol->at_index_root, name,
				data, sizeof(data), &da);
}

int ntfs_mkdir(ntfs_inode *dir, const char *name, int namelen,
	       ntfs_inode *result)
{
	int error;
	
	error = ntfs_alloc_inode(dir, result, name, namelen, NTFS_AFLAG_DIR);
	if (error)
		goto out;
	error = ntfs_add_index_root(result, 0x30);
	if (error)
		goto out;
	/* Set directory bit. */
	result->attr[0x16] |= 2;
	error = ntfs_update_inode(dir);
	if (error)
		goto out;
	error = ntfs_update_inode(result);
	if (error)
		goto out;
 out:
	return error;
}