/*
 *  inode.c
 *
 *  Copyright (C) 1995-1997 Martin von Löwis
 *  Copyright (C) 1996 Albert D. Cahalan
 *  Copyright (C) 1996-1997 Régis Duchesne
 */

#include "types.h"
#include "struct.h"
#include "inode.h"

#include <errno.h>
#include "macros.h"
#include "attr.h"
#include "super.h"
#include "dir.h"
#include "support.h"
#include "util.h"

typedef struct {
	int recno;
	unsigned char* record;
} ntfs_mft_record;

typedef struct {
	int size;
	int count;
	ntfs_mft_record* records;
} ntfs_disk_inode;

static void
fill_mft_header(ntfs_u8*mft,int record_size,int blocksize,
		int sequence_number)
{
	int fixup_count = record_size / blocksize + 1;
	int attr_offset = (0x2a + (2 * fixup_count) + 7) & ~7;
	int fixup_offset = 0x2a;

	NTFS_PUTU32(mft + 0x00, 0x454c4946);	     /* FILE */
	NTFS_PUTU16(mft + 0x04, 0x2a);		     /* offset to fixup */
	NTFS_PUTU16(mft + 0x06, fixup_count);	     /* Number of fixups */
	NTFS_PUTU16(mft + 0x10, sequence_number);
	NTFS_PUTU16(mft + 0x12, 1);                  /* hard link count */
	NTFS_PUTU16(mft + 0x14, attr_offset);	     /* Offset to attributes */
	NTFS_PUTU16(mft + 0x16, 1);                  /*FIXME: flags ?? */
	NTFS_PUTU32(mft + 0x18, attr_offset + 0x08);	/* In use */
	NTFS_PUTU32(mft + 0x1c, record_size);	     /* Total size */

	NTFS_PUTU16(mft + fixup_offset, 1);		/* Fixup word */
	NTFS_PUTU32(mft + attr_offset, 0xffffffff);	/* End marker */
}

/* Search in an inode an attribute by type and name */
ntfs_attribute* 
ntfs_find_attr(ntfs_inode *ino,int type,char *name)
{
	int i;
	if(!ino){
		ntfs_error("ntfs_find_attr: NO INODE!\n");
		return 0;
	}
	for(i=0;i<ino->attr_count;i++)
	{
		if(type==ino->attrs[i].type)
		{
			if(!name && !ino->attrs[i].name)
				return ino->attrs+i;
			if(name && !ino->attrs[i].name)
				return 0;
			if(!name && ino->attrs[i].name)
				return 0;
			if(ntfs_ua_strncmp(ino->attrs[i].name,name,strlen(name))==0)
				return ino->attrs+i;
		}
		if(type<ino->attrs[i].type)
			return 0;
	}
	return 0;
}

/* FIXME: need better strategy to extend the MFT */
static int 
ntfs_extend_mft(ntfs_volume *vol)
{
	/* Try to allocate at least 0.1% of the remaining disk space
	   for inodes. If the disk is almost full, make sure at least one
	   inode is requested.
	 */
	int size,rcount,error,block;
	ntfs_attribute* mdata,*bmp;
	ntfs_u8 *buf;
	ntfs_io io;

	mdata=ntfs_find_attr(vol->mft_ino,vol->at_data,0);
	/* first check whether there is uninitialized space */
	if(mdata->allocated<mdata->size+vol->mft_recordsize){
		size=ntfs_get_free_cluster_count(vol->bitmap)*vol->clustersize;
		block=vol->mft_recordsize;
		size=max(size/1000,block);
		size=((size+block-1)/block)*block;
		/* require this to be a single chunk */
		error=ntfs_extend_attr(vol->mft_ino,mdata,&size,
				       ALLOC_REQUIRE_SIZE);
		/* Try again, now we have the largest available fragment */
		if(error==ENOSPC){
			/* round down to multiple of mft record size */
			size=(size/vol->mft_recordsize)*vol->mft_recordsize;
			if(!size)return ENOSPC;
			error=ntfs_extend_attr(vol->mft_ino,mdata,&size,
					       ALLOC_REQUIRE_SIZE);
		}
		if(error)
			return error;
	}
	/* even though we might have allocated more than needed,
	   we initialize only one record */
	mdata->size+=vol->mft_recordsize;
	
	/* now extend the bitmap if necessary*/
	rcount=mdata->size/vol->mft_recordsize;
	bmp=ntfs_find_attr(vol->mft_ino,vol->at_bitmap,0);
	if(bmp->size*8<rcount){ /* less bits than MFT records */
		ntfs_u8 buf[1];
		/* extend bitmap by one byte */
		error=ntfs_resize_attr(vol->mft_ino,bmp,bmp->size+1);
		if(error)return error;
		/* write the single byte */
		buf[0]=0;
		io.fn_put=ntfs_put;
		io.fn_get=ntfs_get;
		io.param=buf;
		io.size=1;
		error=ntfs_write_attr(vol->mft_ino,vol->at_bitmap,0,
				      bmp->size-1,&io);
		if(error)return error;
		if(io.size!=1)return EIO;
	}

	/* now fill in the MFT header for the new block */
	buf=ntfs_calloc(vol->mft_recordsize);
	if(!buf)return ENOMEM;
	fill_mft_header(buf,vol->mft_recordsize,vol->blocksize,0);
	ntfs_insert_fixups(buf,vol->blocksize);
	io.param=buf;
	io.size=vol->mft_recordsize;
	error=ntfs_write_attr(vol->mft_ino,vol->at_data,0,
			      (rcount-1)*vol->mft_recordsize,&io);
	if(error)return error;
	if(io.size!=vol->mft_recordsize)return EIO;
	return 0;
}

/* Insert all attributes from the record mftno of the MFT in the inode ino */
void ntfs_insert_mft_attributes(ntfs_inode* ino,char *mft,int mftno)
{
	int i;
	char *it;
	int type,len;
	/* check for duplicate */
	for(i=0;i<ino->record_count;i++)
		if(ino->records[i]==mftno)
			return;
	/* (re-)allocate space if necessary */
	if(ino->record_count % 8==0)
	{
		int *old=ino->records;
		ino->records=ntfs_malloc((ino->record_count+8)*sizeof(int));
		if(old) {
			for(i=0;i<ino->record_count;i++)
				ino->records[i]=old[i];
			ntfs_free(old);
		}
	}
	ino->records[ino->record_count]=mftno;
	ino->record_count++;
	it = mft + NTFS_GETU16(mft + 0x14);
	do{
		type=NTFS_GETU32(it);
		len=NTFS_GETU32(it+4);
		if(type!=-1)
			ntfs_insert_attribute(ino,it);
		it+=len;
	}while(type!=-1); /* attribute list ends with type -1 */
}

/* Read and insert all the attributes of an 'attribute list' attribute
   Return the number of remaining bytes in *plen
*/
static int parse_attributes(ntfs_inode *ino, void *alist, int *plen)
{
	char *mft;
	int mftno,l,error;
	int last_mft=-1;
	int len=*plen;
	mft=ntfs_malloc(ino->vol->mft_recordsize);
	while(len>8)
	{
		l=NTFS_GETU16(alist+4);
		if(l>len)break;
	        /* process an attribute description */
		mftno=NTFS_GETU32(alist+0x10); /* BUG: this is u64 */
		if(mftno!=last_mft){
			last_mft=mftno;
			/* FIXME: avoid loading record if it's 
			   already processed */
			error=ntfs_read_mft_record(ino->vol,mftno,mft);
			if(error)return error;
			ntfs_insert_mft_attributes(ino,mft,mftno);
		}
		len-=l;
		alist+=l;
	}
	ntfs_free(mft);
	*plen=len;
	return 0;
}

static void ntfs_load_attributes(ntfs_inode* ino)
{
	ntfs_attribute *alist;
	int datasize;
	int offset,len,delta;
	char *buf;
	ntfs_volume *vol=ino->vol;
	ntfs_debug(DEBUG_OTHER, "load_attributes %x 1\n",ino->i_number);
	ntfs_insert_mft_attributes(ino,ino->attr,ino->i_number);
	ntfs_debug(DEBUG_OTHER, "load_attributes %x 2\n",ino->i_number);
	alist=ntfs_find_attr(ino,vol->at_attribute_list,0);
	ntfs_debug(DEBUG_OTHER, "load_attributes %x 3\n",ino->i_number);
	if(!alist)
		return;
	ntfs_debug(DEBUG_OTHER, "load_attributes %x 4\n",ino->i_number);
	datasize=alist->size;
	if(alist->resident)
	{
		parse_attributes(ino,alist->d.data,&datasize);
		return;
	}
	buf=ntfs_malloc(1024);
	delta=0;
	for(offset=0;datasize;datasize-=len)
	{
		ntfs_io io;
		io.fn_put=ntfs_put;
		io.fn_get=0;
		io.param=buf+delta;
		io.size=len=min(datasize,1024-delta);
		if(ntfs_read_attr(ino,vol->at_attribute_list,0,offset,&io)){
			ntfs_error("error in load_attributes\n");
		}
		delta=len;
		parse_attributes(ino,buf,&delta);
		if(delta)
			/* move remaining bytes to buffer start */
			ntfs_memmove(buf,buf+len-delta,delta);
	}
	ntfs_debug(DEBUG_OTHER, "load_attributes %x 5\n",ino->i_number);
	ntfs_free(buf);
}
	
int ntfs_init_inode(ntfs_inode *ino,ntfs_volume *vol,int inum)
{
	char *buf;
	int error;

	ntfs_debug(DEBUG_OTHER, "Initializing inode %x\n",inum);
	if(!vol)
		ntfs_error("NO VOLUME!\n");
	ino->i_number=inum;
	ino->vol=vol;
	ino->attr=buf=ntfs_malloc(vol->mft_recordsize);
	error=ntfs_read_mft_record(vol,inum,ino->attr);
	if(error){
		ntfs_debug(DEBUG_OTHER, "init inode: %x failed\n",inum);
		return error;
	}
	ntfs_debug(DEBUG_OTHER, "Init: got mft %x\n",inum);
	ino->sequence_number=NTFS_GETU16(buf+0x10);
	ino->attr_count=0;
	ino->record_count=0;
	ino->records=0;
	ino->attrs=0;
	ntfs_load_attributes(ino);
	ntfs_debug(DEBUG_OTHER, "Init: done %x\n",inum);
	return 0;
}

void ntfs_clear_inode(ntfs_inode *ino)
{
	int i;
	if(!ino->attr){
		ntfs_error("ntfs_clear_inode: double free\n");
		return;
	}
	ntfs_free(ino->attr);
	ino->attr=0;
	ntfs_free(ino->records);
	ino->records=0;
	for(i=0;i<ino->attr_count;i++)
	{
		if(ino->attrs[i].name)
			ntfs_free(ino->attrs[i].name);
		if(ino->attrs[i].resident)
		{
			if(ino->attrs[i].d.data)
				ntfs_free(ino->attrs[i].d.data);
		}else{
			if(ino->attrs[i].d.r.runlist)
				ntfs_free(ino->attrs[i].d.r.runlist);
		}
	}
	ntfs_free(ino->attrs);
	ino->attrs=0;
}

/* Check and fixup a MFT record */
int ntfs_check_mft_record(ntfs_volume *vol,char *record)
{
	return ntfs_fixup_record(vol, record, "FILE", vol->mft_recordsize);
}

/* Return (in result) the value indicating the next available attribute 
   chunk number. Works for inodes w/o extension records only */
int ntfs_allocate_attr_number(ntfs_inode *ino, int *result)
{
	if(ino->record_count!=1)
		return EOPNOTSUPP;
	*result=NTFS_GETU16(ino->attr+0x28);
	NTFS_PUTU16(ino->attr+0x28, (*result)+1);
	return 0;
}

/* find the location of an attribute in the inode. A name of NULL indicates
   unnamed attributes. Return pointer to attribute or NULL if not found */
char *
ntfs_get_attr(ntfs_inode *ino,int attr,char *name)
{
	/* location of first attribute */
	char *it= ino->attr + NTFS_GETU16(ino->attr + 0x14);
	int type;
	int len;
	/* Only check for magic DWORD here, fixup should have happened before */
	if(!IS_MFT_RECORD(ino->attr))return 0;
	do{
		type=NTFS_GETU32(it);
		len=NTFS_GETU16(it+4);
		/* We found the attribute type. Is the name correct, too? */
		if(type==attr)
		{
			int namelen=NTFS_GETU8(it+9);
			char *name_it;
			/* match given name and attribute name if present,
			   make sure attribute name is Unicode */
			for(name_it=it+NTFS_GETU16(it+10);namelen;
			    name++,name_it+=2,namelen--)
				if(*name_it!=*name || name_it[1])break;
			if(!namelen)break;
		}
		it+=len;
	}while(type!=-1); /* attribute list end with type -1 */
	if(type==-1)return 0;
	return it;
}

int 
ntfs_get_attr_size(ntfs_inode*ino,int type,char*name)
{
	ntfs_attribute *attr=ntfs_find_attr(ino,type,name);
	if(!attr)return 0;
	return attr->size;
}
	
int 
ntfs_attr_is_resident(ntfs_inode*ino,int type,char*name)
{
	ntfs_attribute *attr=ntfs_find_attr(ino,type,name);
	if(!attr)return 0;
	return attr->resident;
}
	
/*
 * A run is coded as a type indicator, an unsigned length, and a signed cluster
 * offset.
 * . To save space, length and offset are fields of variable length. The low
 *   nibble of the type indicates the width of the length :), the high nibble
 *   the width of the offset.
 * . The first offset is relative to cluster 0, later offsets are relative to
 *   the previous cluster.
 *
 * This function decodes a run. Length is an output parameter, data and cluster
 * are in/out parameters.
 */
int ntfs_decompress_run(unsigned char **data, int *length, int *cluster,
	int *ctype)
{
	unsigned char type=*(*data)++;
	*ctype=0;
	switch(type & 0xF)
	{
	case 1: *length=NTFS_GETU8(*data);(*data)++;break;
	case 2: *length=NTFS_GETU16(*data);
		*data+=2;
		break;
	case 3: *length = NTFS_GETU24(*data);
		*data+=3;
		break;
		/* TODO: case 4-8 */
	default:
		ntfs_error("Can't decode run type field %x\n",type);
		return -1;
	}
	switch(type & 0xF0)
	{
	case 0:    *ctype=2;break;
	case 0x10: *cluster+=NTFS_GETS8(*data);(*data)++;break;
	case 0x20: *cluster+=NTFS_GETS16(*data);
		*data+=2;
		break;
	case 0x30: 	*cluster+=NTFS_GETS24(*data);
		*data+=3;
		break;
		/* TODO: case 0x40-0x80 */
	default:
		ntfs_error("Can't decode run type field %x\n",type);
		return -1;
	}
	return 0;
}

/* Reads l bytes of the attribute (attr,name) of ino starting at offset
   on vol into buf. Returns the number of bytes read in the ntfs_io struct.
   Returns 0 on success, errno on failure */
int ntfs_readwrite_attr(ntfs_inode *ino, ntfs_attribute *attr, int offset,
	ntfs_io *dest)
{
	int datasize,rnum;
	int cluster,s_cluster,vcn,len,l,chunk,copied;
	int s_vcn;
	int clustersize;
	int error;

	clustersize=ino->vol->clustersize;
	datasize=attr->size;
	l=dest->size;
	if(dest->do_read)
	{
		if(offset>=datasize){
			dest->size=0;
			return 0;
		}
		if(offset+l>=datasize) 
			l=dest->size=datasize-offset;
	}else { /* fixed by CSA: if writing beyond end, extend attribute */
		if (offset+l>datasize) {
			error=ntfs_resize_attr(ino,attr,offset+l);
			if(error)
				return error;
		}
	}
	if(attr->resident)
	{
		if(dest->do_read)
			dest->fn_put(dest,attr->d.data+offset,l);
		else
		{
			dest->fn_get(attr->d.data+offset,dest,l);
			ntfs_update_inode(ino);
		}
		dest->size=l;
		return 0;
	}
	if(attr->compressed)
		if(dest->do_read)
			return ntfs_read_compressed(ino,attr,offset,dest);
		else
			return ntfs_write_compressed(ino,attr,offset,dest);
	vcn=0;
	s_vcn = offset/clustersize;
	for(rnum=0;rnum<attr->d.r.len && 
		    vcn+attr->d.r.runlist[rnum].len<=s_vcn;rnum++)
		vcn+=attr->d.r.runlist[rnum].len;
	if(rnum==attr->d.r.len)
		/*FIXME: should extend runlist */
		return EOPNOTSUPP;
	
	copied=0;
	while(l)
	{
		s_vcn = offset/clustersize;
		cluster=attr->d.r.runlist[rnum].cluster;
		len=attr->d.r.runlist[rnum].len;

		s_cluster = cluster+s_vcn-vcn;
			
		chunk=min((vcn+len)*clustersize-offset,l);
		dest->size=chunk;
		error=ntfs_getput_clusters(ino->vol,s_cluster,
					   offset-s_vcn*clustersize,dest);
		if(error)/* FIXME: maybe return failure */
		{
			ntfs_error("Read error\n");
			dest->size=copied;
			return 0;
		}
		l-=chunk;
		copied+=chunk;
		offset+=chunk;
		if(l && offset>=((vcn+len)*clustersize))
		{
			rnum++;
			vcn+=len;
			cluster = attr->d.r.runlist[rnum].cluster;
			len = attr->d.r.runlist[rnum].len;
		}
	}
	dest->size=copied;
	return 0;
}

int ntfs_read_attr(ntfs_inode *ino, int type, char *name, int offset,
        ntfs_io *buf)
{
	ntfs_attribute *attr;
	buf->do_read=1;
	attr=ntfs_find_attr(ino,type,name);
	if(!attr)
		return EINVAL;
	return ntfs_readwrite_attr(ino,attr,offset,buf);
}

int ntfs_write_attr(ntfs_inode *ino, int type, char *name, int offset,
		ntfs_io *buf)
{
	ntfs_attribute *attr;
	buf->do_read=0;
	attr=ntfs_find_attr(ino,type,name);
	if(!attr)
		return EINVAL;
	return ntfs_readwrite_attr(ino,attr,offset,buf);
}

int ntfs_vcn_to_lcn(ntfs_inode *ino,int vcn)
{
	int rnum;
	ntfs_attribute *data=ntfs_find_attr(ino,ino->vol->at_data,0);
	/* It's hard to give an error code */
	if(!data)return -1;
	if(data->resident)return -1;
	if(data->compressed)return -1;
	if(data->size<vcn*ino->vol->clustersize)return -1;

	for(rnum=0;rnum<data->d.r.len && 
		    vcn>data->d.r.runlist[rnum].len;rnum++)
		vcn-=data->d.r.runlist[rnum].len;
	
	return data->d.r.runlist[rnum].cluster+vcn;
}

static int 
allocate_store(ntfs_volume *vol,ntfs_disk_inode *store,int count)
{
	int i;
	if(store->count>count)
		return 0;
	if(store->size<count){
		ntfs_mft_record* n=ntfs_malloc((count+4)*sizeof(ntfs_mft_record));
		if(!n)
			return ENOMEM;
		if(store->size){
			for(i=0;i<store->size;i++)
				n[i]=store->records[i];
			ntfs_free(store->records);
		}
		store->size=count+4;
		store->records=n;
	}
	for(i=store->count;i<count;i++){
		store->records[i].record=ntfs_malloc(vol->mft_recordsize);
		if(!store->records[i].record)
			return ENOMEM;
		store->count++;
	}
	return 0;
}

static void 
deallocate_store(ntfs_disk_inode* store)
{
	int i;
	for(i=0;i<store->count;i++)
		ntfs_free(store->records[i].record);
	ntfs_free(store->records);
	store->count=store->size=0;
	store->records=0;
}

int 
layout_runs(ntfs_attribute *attr,char* rec,int* offs,int size)
{
	int i,cluster,rclus,len,offset,coffs;
	ntfs_runlist *rl=attr->d.r.runlist;
	cluster=0;
	offset=*offs;
	for(i=0;i<attr->d.r.len;i++){
		rclus=rl[i].cluster-cluster;
		len=rl[i].len;
		rec[offset]=0;
		if(offset+8>size)
			return E2BIG; /* it might still fit, but this simplifies testing */
		if(len<0x100){
			*(rec+offset)|=1;
			NTFS_PUTU8(rec+offset+1,len);
			coffs=2;
		}else if(len<0x10000){
			*(rec+offset)|=2;
			NTFS_PUTU16(rec+offset+1,len);
			coffs=3;
		}else if(len<0x1000000){
			*(rec+offset)|=3;
			NTFS_PUTU24(rec+offset+1,len);
			coffs=4;
		}else{
			*(rec+offset)|=4;
			NTFS_PUTU32(rec+offset+1,len);
			coffs=5;
		}
    
		if(rl[i].cluster==0) /*compressed run*/
			/*nothing*/;
		else if(rclus>-0x80 && rclus<0x7F){
			*(rec+offset)|=0x10;
			NTFS_PUTS8(rec+offset+coffs,rclus);
			coffs+=1;
		}else if(rclus>-0x8000 && rclus<0x7FFF){
			*(rec+offset)|=0x20;
			NTFS_PUTS16(rec+offset+coffs,rclus);
			coffs+=2;
		}else if(rclus>-0x800000 && rclus<0x7FFFFF){
			*(rec+offset)|=0x30;
			NTFS_PUTS24(rec+offset+coffs,rclus);
			coffs+=3;
		}else{
			*(rec+offset)|=0x40;
			NTFS_PUTS32(rec+offset+coffs,rclus);
			coffs+=4;
		}
		offset+=coffs;
		if(rl[i].cluster)
			cluster=rl[i].cluster;
	}
	*offs=offset;
	return 0;
}

static void 
count_runs(ntfs_attribute *attr,char *buf)
{
	int first,count,last,i;
	first=0;
	for(i=0,count=0;i<attr->d.r.len;i++)
		count+=attr->d.r.runlist[i].len;
	last=first+count-1;

	NTFS_PUTU32(buf+0x10,first);
	NTFS_PUTU32(buf+0x18,last);
} 

static int
layout_attr(ntfs_attribute* attr,char*buf, int size,int *psize)
{
	int asize,error;
	if(size<10)return E2BIG;
	NTFS_PUTU32(buf,attr->type);
	/* fill in length later */
	NTFS_PUTU8(buf+8,attr->resident ? 0:1);
	NTFS_PUTU8(buf+9,attr->namelen);
	/* fill in offset to name later */
	NTFS_PUTU16(buf+0xA,0);
	NTFS_PUTU16(buf+0xC,attr->compressed);
	/* FIXME: assign attribute ID??? */
	NTFS_PUTU16(buf+0xE,attr->attrno);
	if(attr->resident){
		if(size<attr->size+0x18+attr->namelen)return E2BIG;
		asize=0x18;
		NTFS_PUTU32(buf+0x10,attr->size);
		NTFS_PUTU16(buf+0x16,attr->indexed);
		if(attr->name){
			ntfs_memcpy(buf+asize,attr->name,2*attr->namelen);
			NTFS_PUTU16(buf+0xA,asize);
			asize+=2*attr->namelen;
			asize=(asize+7) & ~7;
		}
		NTFS_PUTU16(buf+0x14,asize);
		ntfs_memcpy(buf+asize,attr->d.data,attr->size);
		asize+=attr->size;
	}else{
		/* FIXME: fragments */
		count_runs(attr,buf);
		/* offset to data is added later */
		NTFS_PUTU16(buf+0x22,attr->cengine);
		NTFS_PUTU32(buf+0x24,0);
		NTFS_PUTU64(buf+0x28,attr->allocated);
		NTFS_PUTU64(buf+0x30,attr->size);
		NTFS_PUTU64(buf+0x38,attr->initialized);
		if(attr->compressed){
			NTFS_PUTU64(buf+0x40,attr->compsize);
			asize=0x48;
		}else
			asize=0x40;
		if(attr->name){
			NTFS_PUTU16(buf+0xA,asize);
			ntfs_memcpy(buf+asize,attr->name,2*attr->namelen);
			asize+=2*attr->namelen;
			asize=(asize+7) & ~7;
		}
		/* asize points at the beginning of the data */
		NTFS_PUTU16(buf+0x20,asize);
		error=layout_runs(attr,buf,&asize,size);
		/* now asize pointes at the end of the data */
		if(error)
			return error;
	}
	asize=(asize+7) & ~7;
	NTFS_PUTU32(buf+4,asize);
	*psize=asize;
	return 0;
}
		
		

/* Try to layout ino into store. Return 0 on success,
   E2BIG if it does not fit, 
   ENOMEM if memory allocation problem,
   EOPNOTSUP if beyound our capabilities 
*/
int 
layout_inode(ntfs_inode *ino,ntfs_disk_inode *store)
{
	int offset,i;
	ntfs_attribute *attr;
	unsigned char *rec;
	int size,psize;
	int error;

	if(ino->record_count>1)
	{
		ntfs_error("layout_inode: attribute lists not supported\n");
		return EOPNOTSUPP;
	}
	error=allocate_store(ino->vol,store,1);
	if(error)
		return error;
	rec=store->records[0].record;
	size=ino->vol->mft_recordsize;
	store->records[0].recno=ino->records[0];
	/* copy header */
	offset=NTFS_GETU16(ino->attr+0x14);
	ntfs_memcpy(rec,ino->attr,offset);
	for(i=0;i<ino->attr_count;i++){
		attr=ino->attrs+i;
		error=layout_attr(attr,rec+offset,size-offset,&psize);
		if(error)return error;
		offset+=psize;
#if 0
		/* copy attribute header */
		ntfs_memcpy(rec+offset,attr->header,
			    min(sizeof(attr->header),size-offset)); /* consider overrun */
		if(attr->namelen)
			/* named attributes are added later */
			return EOPNOTSUPP;
		/* FIXME: assign attribute ID??? */
		if(attr->resident){
			asize=attr->size;
			aoffset=NTFS_GETU16(rec+offset+0x14);
			if(offset+aoffset+asize>size)
				return E2BIG;
			ntfs_memcpy(rec+offset+aoffset,attr->d.data,asize);
			next=offset+aoffset+asize;
		}else{
			count_runs(attr,rec+offset);
			aoffset=NTFS_GETU16(rec+offset+0x20);
			next=offset+aoffset;
			error=layout_runs(attr,rec,&next,size);
			if(error)
				return error;
		}
		next=(next+7) & ~7; /* align to DWORD */
		NTFS_PUTU16(rec+offset+4,next-offset);
		offset=next;
#endif
	}
	/* terminating attribute */
	if(offset+8<size){
		NTFS_PUTU32(rec+offset,0xFFFFFFFF);
		offset+=4;
		NTFS_PUTU32(rec+offset,0);
		offset+=4;
	}else
		return E2BIG;
	NTFS_PUTU32(rec+0x18,offset);
	return 0;
}
  
int ntfs_update_inode(ntfs_inode *ino)
{
	int error;
	ntfs_disk_inode store;
	ntfs_io io;
	int i;

	store.count=store.size=0;
	store.records=0;
	error=layout_inode(ino,&store);
	if(error==E2BIG){
		/* should try:
		   make attributes non-resident
		   introduce extension records
		   */
		ntfs_error("cannot handle saving inode %x\n",ino->i_number);
		deallocate_store(&store);
		return EOPNOTSUPP;
	}
	if(error){
		deallocate_store(&store);
		return error;
	}
	io.fn_get=ntfs_get;
	io.fn_put=0;
	for(i=0;i<store.count;i++){
		ntfs_insert_fixups(store.records[i].record,ino->vol->blocksize);
		io.param=store.records[i].record;
		io.size=ino->vol->mft_recordsize;
		/* FIXME: is this the right way? */
		error=ntfs_write_attr(
			ino->vol->mft_ino,ino->vol->at_data,0,
			store.records[i].recno*ino->vol->mft_recordsize,&io);
		if(error || io.size!=ino->vol->mft_recordsize){
			/* big trouble, partially written file */
			ntfs_error("Please unmount: write error in inode %x\n",ino->i_number);
			deallocate_store(&store);
			return error?error:EIO;
		}
	}
	return 0;
}

void ntfs_decompress(unsigned char *dest, unsigned char *src, ntfs_size_t l)
{
	int head,comp;
	int copied=0;
	unsigned char *stop;
	int bits;
	int tag=0;
	int clear_pos;
	while(1)
	{
		head = NTFS_GETU16(src) & 0xFFF;
		/* high bit indicates that compression was performed */
		comp = NTFS_GETU16(src) & 0x8000;
		src += 2;
		stop = src+head;
		bits = 0;
		clear_pos=0;
		if(head==0)
			/* block is not used */
			return;/* FIXME: copied */
		if(!comp) /* uncompressible */
		{
			ntfs_memcpy(dest,src,0x1000);
			dest+=0x1000;
			copied+=0x1000;
			src+=0x1000;
			if(l==copied)
				return;
			continue;
		}
		while(src<=stop)
		{
			if(clear_pos>4096)
			{
				ntfs_error("Error 1 in decompress\n");
				return;
			}
			if(!bits){
				tag=NTFS_GETU8(src);
				bits=8;
				src++;
				if(src>stop)
					break;
			}
			if(tag & 1){
				int i,len,delta,code,lmask,dshift;
				code = NTFS_GETU16(src);
				src+=2;
				if(!clear_pos)
				{
					ntfs_error("Error 2 in decompress\n");
					return;
				}
				for(i=clear_pos-1,lmask=0xFFF,dshift=12;i>=0x10;i>>=1)
				{
					lmask >>= 1;
					dshift--;
				}
				delta = code >> dshift;
				len = (code & lmask) + 3;
				for(i=0; i<len; i++)
				{
					dest[clear_pos]=dest[clear_pos-delta-1];
					clear_pos++;
					copied++;
					if(copied==l)
						return;
				}
			}else{
				dest[clear_pos++]=NTFS_GETU8(src);
				src++;
				copied++;
				if(copied==l)
					return;
			}
			tag>>=1;
			bits--;
		}
		dest+=clear_pos;
	}
}

/* Caveat: No range checking in either ntfs_set_bit or ntfs_clear_bit */
void 
ntfs_set_bit (unsigned char *byte, int bit)
{
	byte += (bit >> 3);
	bit &= 7;
	*byte |= (1 << bit);
}

void 
ntfs_clear_bit (unsigned char *byte, int bit)
{
	byte += (bit >> 3);
	bit &= 7;
	*byte &= ~(1 << bit);
}

/* We have to skip the 16 metafiles and the 8 reserved entries */
static int 
new_inode (ntfs_volume* vol,int* result)
{
	int byte,error;
	int bit;
	int size,length;
	unsigned char value;
	ntfs_u8 *buffer;
	ntfs_io io;
	ntfs_attribute *data;

	buffer=ntfs_malloc(2048);
	if(!buffer)return ENOMEM;
	io.fn_put=ntfs_put;
	io.fn_get=ntfs_get;
	io.param=buffer;
	/* FIXME: bitmaps larger than 2048 bytes */
	io.size=2048;
	error=ntfs_read_attr(vol->mft_ino,vol->at_bitmap,0,0,&io);
	if(error){
		ntfs_free(buffer);
		return error;
	}
	size=io.size;
	data=ntfs_find_attr(vol->mft_ino,vol->at_data,0);
	length=data->size/vol->mft_recordsize;

	for (byte = 3; 8*byte < length; byte++)
	{
		value = buffer[byte];
		if(value==0xFF)
			continue;
		for (bit = 0; (bit < 8) && (8*byte+bit<length); 
		     bit++, value >>= 1)
		{
			if (!(value & 1)){
				*result=byte*8+bit;
				return 0;
			}
		}
	}
	/* There is no free space.  We must first extend the MFT. */
	return ENOSPC;
}

static int 
add_mft_header (ntfs_inode *ino)
{
	unsigned char* mft;
	ntfs_volume *vol=ino->vol;
	mft=ino->attr;

	ntfs_bzero(mft, vol->mft_recordsize);
	fill_mft_header(mft,vol->mft_recordsize,vol->blocksize,
			ino->sequence_number);
	return 0;
}

/* We need 0x48 bytes in total */
static int 
add_standard_information (ntfs_inode *ino)
{
	ntfs_time64_t now;
	char data[0x30];
	char *position=data;
	int error;
	ntfs_attribute *si;

	now = ntfs_now();
	NTFS_PUTU64(position + 0x00, now);		/* File creation */
	NTFS_PUTU64(position + 0x08, now);		/* Last modification */
	NTFS_PUTU64(position + 0x10, now);		/* Last mod for MFT */
	NTFS_PUTU64(position + 0x18, now);		/* Last access */

	NTFS_PUTU64(position + 0x20, 0x00);		/* MSDOS file perms */
	NTFS_PUTU64(position + 0x28, 0);               /* unknown */
	error=ntfs_create_attr(ino,ino->vol->at_standard_information,0,
			       data,sizeof(data),&si);

	return error;
}

static int 
add_filename (ntfs_inode* ino, ntfs_inode* dir, 
			 const unsigned char *filename, int length)
{
	unsigned char   *position;
	unsigned int    size;
	ntfs_time64_t   now;
	int		count;
	int error;
	unsigned char* data;
	ntfs_attribute *fn;

	/* work out the size */
	size = 0x42 + 2 * length;
	data = ntfs_malloc(size);
	ntfs_bzero(data,size);

	/* search for a position */
	position = data;

	NTFS_PUTINUM(position, dir);	/* Inode num of dir */

	now = ntfs_now();
	NTFS_PUTU64(position + 0x08, now);		/* File creation */
	NTFS_PUTU64(position + 0x10, now);		/* Last modification */
	NTFS_PUTU64(position + 0x18, now);		/* Last mod for MFT */
	NTFS_PUTU64(position + 0x20, now);		/* Last access */

	/* Don't know */
	NTFS_PUTU8(position+0x38, 0x0);  /*should match standard attributes*/

	NTFS_PUTU8(position + 0x40, length);	      /* Filename length */
	NTFS_PUTU8(position + 0x41, 0x0);	      /* only long name */

	position += 0x42;
	for (count = 0; count < length; count++)
	{
		NTFS_PUTU16(position + 2 * count, filename[count]);
	}

	error=ntfs_create_attr(ino,ino->vol->at_file_name,0,data,size,&fn);
	if(!error)
		error=ntfs_dir_add(dir,ino,fn);
	ntfs_free(data);
	return error;
}

int 
add_security (ntfs_inode* ino, ntfs_inode* dir)
{
	int error;
	char *buf;
	int size;
	ntfs_attribute* attr;
	ntfs_io io;
	ntfs_attribute *se;

	attr=ntfs_find_attr(dir,ino->vol->at_security_descriptor,0);
	if(!attr)
		return EOPNOTSUPP; /* need security in directory */
	size = attr->size;
	if(size>512)
		return EOPNOTSUPP;
	buf=ntfs_malloc(size);
	if(!buf)
		return ENOMEM;
	io.fn_get=ntfs_get;
	io.fn_put=ntfs_put;
	io.param=buf;
	io.size=size;
	error=ntfs_read_attr(dir,ino->vol->at_security_descriptor,0,0,&io);
	if(!error && io.size!=size)ntfs_error("wrong size in add_security");
	if(error){
		ntfs_free(buf);
		return error;
	}
	/* FIXME: consider ACL inheritance */
	error=ntfs_create_attr(ino,ino->vol->at_security_descriptor,
			       0,buf,size,&se);
	ntfs_free(buf);
	return error;
}

static int 
add_data (ntfs_inode* ino, unsigned char *data, int length)
{
	int error;
	ntfs_attribute *da;
	error=ntfs_create_attr(ino,ino->vol->at_data,0,data,length,&da);
	return error;
}


/* We _could_ use 'dir' to help optimise inode allocation */
int ntfs_alloc_inode (ntfs_inode *dir, ntfs_inode *result, char *filename,
		int namelen)
{
	ntfs_io io;
	int error;
	ntfs_u8 buffer[1];
	ntfs_volume* vol=dir->vol;
	int byte,bit;

	error=new_inode (vol,&(result->i_number));
	if(error==ENOSPC){
		error=ntfs_extend_mft(vol);
		if(error)return error;
		error=new_inode(vol,&(result->i_number));
	}
	if(error){
		ntfs_error ("ntfs_get_empty_inode: no free inodes\n");
		return error;
	}
	byte=result->i_number/8;
	bit=result->i_number & 7;

	io.fn_put = ntfs_put;
	io.fn_get = ntfs_get;
	io.param = buffer;
	io.size=1;
	/* set a single bit */
	error=ntfs_read_attr(vol->mft_ino,vol->at_bitmap,0,byte,&io);
	if(error)return error;
	if(io.size!=1)
		return EIO;
	ntfs_set_bit (buffer, bit);
	io.param = buffer;
	io.size = 1;
 	error = ntfs_write_attr (vol->mft_ino, vol->at_bitmap, 0, byte, &io);
	if(error)return error;
	if (io.size != 1)
		return EIO;
	/*FIXME: Should change MFT on disk
	  error=ntfs_update_inode(vol->mft_ino);
	  if(error)return error;
	  */
	/* get the sequence number */
	io.param = buffer;
	io.size = 0x10;
	error = ntfs_read_attr(vol->mft_ino, vol->at_data, 0, 
			       result->i_number*vol->mft_recordsize+0x10,&io);
	if(error)
		return error;
	result->sequence_number=NTFS_GETU16(buffer)+1;
	result->vol=vol;
	result->attr=ntfs_malloc(vol->mft_recordsize);
	result->attr_count=0;
	result->attrs=0;
	result->record_count=1;
	result->records=ntfs_malloc(8*sizeof(int));
	result->records[0]=result->i_number;
	error=add_mft_header(result);
	if(error)
		return error;
	error=add_standard_information(result);
	if(error)
		return error;
	error=add_filename(result,dir,filename,namelen);
	if(error)
		return error;
	error=add_security(result,dir);
	/*FIXME: check error */
	error=add_data(result,0,0);
	if(error)
		return error;
	return 0;
}

/*
 * Local variables:
 * c-file-style: "linux"
 * End:
 */