Account for MacOS X ABI reserved space in linkage area (Andreas Faerber)

[qemu.git] / block-vvfat.c

/* vim:set shiftwidth=4 ts=8: */
/*
 * QEMU Block driver for virtual VFAT (shadows a local directory)
 *
 * Copyright (c) 2004,2005 Johannes E. Schindelin
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
 */
#include <sys/stat.h>
#include <dirent.h>
#include <assert.h>
#include "qemu-common.h"
#include "block_int.h"

#ifndef S_IWGRP
#define S_IWGRP 0
#endif
#ifndef S_IWOTH
#define S_IWOTH 0
#endif

/* TODO: add ":bootsector=blabla.img:" */
/* LATER TODO: add automatic boot sector generation from
    BOOTEASY.ASM and Ranish Partition Manager
    Note that DOS assumes the system files to be the first files in the
    file system (test if the boot sector still relies on that fact)! */
/* MAYBE TODO: write block-visofs.c */
/* TODO: call try_commit() only after a timeout */

/* #define DEBUG */

#ifdef DEBUG

#define DLOG(a) a

#undef stderr
#define stderr STDERR
FILE* stderr = NULL;

static void checkpoint(void);

#ifdef __MINGW32__
void nonono(const char* file, int line, const char* msg) {
    fprintf(stderr, "Nonono! %s:%d %s\n", file, line, msg);
    exit(-5);
}
#undef assert
#define assert(a) do {if (!(a)) nonono(__FILE__, __LINE__, #a);}while(0)
#endif

#else

#define DLOG(a)

#endif

/* dynamic array functions */
typedef struct array_t {
    char* pointer;
    unsigned int size,next,item_size;
} array_t;

static inline void array_init(array_t* array,unsigned int item_size)
{
    array->pointer=0;
    array->size=0;
    array->next=0;
    array->item_size=item_size;
}

static inline void array_free(array_t* array)
{
    if(array->pointer)
        free(array->pointer);
    array->size=array->next=0;
}

/* does not automatically grow */
static inline void* array_get(array_t* array,unsigned int index) {
    assert(index < array->next);
    return array->pointer + index * array->item_size;
}

static inline int array_ensure_allocated(array_t* array, int index)
{
    if((index + 1) * array->item_size > array->size) {
	int new_size = (index + 32) * array->item_size;
	array->pointer = realloc(array->pointer, new_size);
	if (!array->pointer)
	    return -1;
	array->size = new_size;
	array->next = index + 1;
    }

    return 0;
}

static inline void* array_get_next(array_t* array) {
    unsigned int next = array->next;
    void* result;

    if (array_ensure_allocated(array, next) < 0)
	return NULL;

    array->next = next + 1;
    result = array_get(array, next);

    return result;
}

static inline void* array_insert(array_t* array,unsigned int index,unsigned int count) {
    if((array->next+count)*array->item_size>array->size) {
	int increment=count*array->item_size;
	array->pointer=realloc(array->pointer,array->size+increment);
	if(!array->pointer)
	    return 0;
	array->size+=increment;
    }
    memmove(array->pointer+(index+count)*array->item_size,
		array->pointer+index*array->item_size,
		(array->next-index)*array->item_size);
    array->next+=count;
    return array->pointer+index*array->item_size;
}

/* this performs a "roll", so that the element which was at index_from becomes
 * index_to, but the order of all other elements is preserved. */
static inline int array_roll(array_t* array,int index_to,int index_from,int count)
{
    char* buf;
    char* from;
    char* to;
    int is;

    if(!array ||
	    index_to<0 || index_to>=array->next ||
	    index_from<0 || index_from>=array->next)
	return -1;

    if(index_to==index_from)
	return 0;

    is=array->item_size;
    from=array->pointer+index_from*is;
    to=array->pointer+index_to*is;
    buf=malloc(is*count);
    memcpy(buf,from,is*count);

    if(index_to<index_from)
	memmove(to+is*count,to,from-to);
    else
	memmove(from,from+is*count,to-from);

    memcpy(to,buf,is*count);

    free(buf);

    return 0;
}

static inline int array_remove_slice(array_t* array,int index, int count)
{
    assert(index >=0);
    assert(count > 0);
    assert(index + count <= array->next);
    if(array_roll(array,array->next-1,index,count))
	return -1;
    array->next -= count;
    return 0;
}

static int array_remove(array_t* array,int index)
{
    return array_remove_slice(array, index, 1);
}

/* return the index for a given member */
static int array_index(array_t* array, void* pointer)
{
    size_t offset = (char*)pointer - array->pointer;
    assert((offset % array->item_size) == 0);
    assert(offset/array->item_size < array->next);
    return offset/array->item_size;
}

/* These structures are used to fake a disk and the VFAT filesystem.
 * For this reason we need to use __attribute__((packed)). */

typedef struct bootsector_t {
    uint8_t jump[3];
    uint8_t name[8];
    uint16_t sector_size;
    uint8_t sectors_per_cluster;
    uint16_t reserved_sectors;
    uint8_t number_of_fats;
    uint16_t root_entries;
    uint16_t total_sectors16;
    uint8_t media_type;
    uint16_t sectors_per_fat;
    uint16_t sectors_per_track;
    uint16_t number_of_heads;
    uint32_t hidden_sectors;
    uint32_t total_sectors;
    union {
        struct {
	    uint8_t drive_number;
	    uint8_t current_head;
	    uint8_t signature;
	    uint32_t id;
	    uint8_t volume_label[11];
	} __attribute__((packed)) fat16;
	struct {
	    uint32_t sectors_per_fat;
	    uint16_t flags;
	    uint8_t major,minor;
	    uint32_t first_cluster_of_root_directory;
	    uint16_t info_sector;
	    uint16_t backup_boot_sector;
	    uint16_t ignored;
	} __attribute__((packed)) fat32;
    } u;
    uint8_t fat_type[8];
    uint8_t ignored[0x1c0];
    uint8_t magic[2];
} __attribute__((packed)) bootsector_t;

typedef struct {
    uint8_t head;
    uint8_t sector;
    uint8_t cylinder;
} mbr_chs_t;

typedef struct partition_t {
    uint8_t attributes; /* 0x80 = bootable */
    mbr_chs_t start_CHS;
    uint8_t   fs_type; /* 0x1 = FAT12, 0x6 = FAT16, 0xe = FAT16_LBA, 0xb = FAT32, 0xc = FAT32_LBA */
    mbr_chs_t end_CHS;
    uint32_t start_sector_long;
    uint32_t length_sector_long;
} __attribute__((packed)) partition_t;

typedef struct mbr_t {
    uint8_t ignored[0x1b8];
    uint32_t nt_id;
    uint8_t ignored2[2];
    partition_t partition[4];
    uint8_t magic[2];
} __attribute__((packed)) mbr_t;

typedef struct direntry_t {
    uint8_t name[8];
    uint8_t extension[3];
    uint8_t attributes;
    uint8_t reserved[2];
    uint16_t ctime;
    uint16_t cdate;
    uint16_t adate;
    uint16_t begin_hi;
    uint16_t mtime;
    uint16_t mdate;
    uint16_t begin;
    uint32_t size;
} __attribute__((packed)) direntry_t;

/* this structure are used to transparently access the files */

typedef struct mapping_t {
    /* begin is the first cluster, end is the last+1 */
    uint32_t begin,end;
    /* as s->directory is growable, no pointer may be used here */
    unsigned int dir_index;
    /* the clusters of a file may be in any order; this points to the first */
    int first_mapping_index;
    union {
	/* offset is
	 * - the offset in the file (in clusters) for a file, or
	 * - the next cluster of the directory for a directory, and
	 * - the address of the buffer for a faked entry
	 */
	struct {
	    uint32_t offset;
	} file;
	struct {
	    int parent_mapping_index;
	    int first_dir_index;
	} dir;
    } info;
    /* path contains the full path, i.e. it always starts with s->path */
    char* path;

    enum { MODE_UNDEFINED = 0, MODE_NORMAL = 1, MODE_MODIFIED = 2,
	MODE_DIRECTORY = 4, MODE_FAKED = 8,
	MODE_DELETED = 16, MODE_RENAMED = 32 } mode;
    int read_only;
} mapping_t;

#ifdef DEBUG
static void print_direntry(const struct direntry_t*);
static void print_mapping(const struct mapping_t* mapping);
#endif

/* here begins the real VVFAT driver */

typedef struct BDRVVVFATState {
    BlockDriverState* bs; /* pointer to parent */
    unsigned int first_sectors_number; /* 1 for a single partition, 0x40 for a disk with partition table */
    unsigned char first_sectors[0x40*0x200];

    int fat_type; /* 16 or 32 */
    array_t fat,directory,mapping;

    unsigned int cluster_size;
    unsigned int sectors_per_cluster;
    unsigned int sectors_per_fat;
    unsigned int sectors_of_root_directory;
    uint32_t last_cluster_of_root_directory;
    unsigned int faked_sectors; /* how many sectors are faked before file data */
    uint32_t sector_count; /* total number of sectors of the partition */
    uint32_t cluster_count; /* total number of clusters of this partition */
    uint32_t max_fat_value;

    int current_fd;
    mapping_t* current_mapping;
    unsigned char* cluster; /* points to current cluster */
    unsigned char* cluster_buffer; /* points to a buffer to hold temp data */
    unsigned int current_cluster;

    /* write support */
    BlockDriverState* write_target;
    char* qcow_filename;
    BlockDriverState* qcow;
    void* fat2;
    char* used_clusters;
    array_t commits;
    const char* path;
    int downcase_short_names;
} BDRVVVFATState;

/* take the sector position spos and convert it to Cylinder/Head/Sector position
 * if the position is outside the specified geometry, fill maximum value for CHS
 * and return 1 to signal overflow.
 */
static int sector2CHS(BlockDriverState* bs, mbr_chs_t * chs, int spos){
    int head,sector;
    sector   = spos % (bs->secs);  spos/= bs->secs;
    head     = spos % (bs->heads); spos/= bs->heads;
    if(spos >= bs->cyls){
        /* Overflow,
        it happens if 32bit sector positions are used, while CHS is only 24bit.
        Windows/Dos is said to take 1023/255/63 as nonrepresentable CHS */
        chs->head     = 0xFF;
        chs->sector   = 0xFF;
        chs->cylinder = 0xFF;
        return 1;
    }
    chs->head     = (uint8_t)head;
    chs->sector   = (uint8_t)( (sector+1) | ((spos>>8)<<6) );
    chs->cylinder = (uint8_t)spos;
    return 0;
}

static void init_mbr(BDRVVVFATState* s)
{
    /* TODO: if the files mbr.img and bootsect.img exist, use them */
    mbr_t* real_mbr=(mbr_t*)s->first_sectors;
    partition_t* partition=&(real_mbr->partition[0]);
    int lba;

    memset(s->first_sectors,0,512);

    /* Win NT Disk Signature */
    real_mbr->nt_id= cpu_to_le32(0xbe1afdfa);

    partition->attributes=0x80; /* bootable */

    /* LBA is used when partition is outside the CHS geometry */
    lba = sector2CHS(s->bs, &partition->start_CHS, s->first_sectors_number-1);
    lba|= sector2CHS(s->bs, &partition->end_CHS,   s->sector_count);

    /*LBA partitions are identified only by start/length_sector_long not by CHS*/
    partition->start_sector_long =cpu_to_le32(s->first_sectors_number-1);
    partition->length_sector_long=cpu_to_le32(s->sector_count - s->first_sectors_number+1);

    /* FAT12/FAT16/FAT32 */
    /* DOS uses different types when partition is LBA,
       probably to prevent older versions from using CHS on them */
    partition->fs_type= s->fat_type==12 ? 0x1:
                        s->fat_type==16 ? (lba?0xe:0x06):
                         /*fat_tyoe==32*/ (lba?0xc:0x0b);

    real_mbr->magic[0]=0x55; real_mbr->magic[1]=0xaa;
}

/* direntry functions */

/* dest is assumed to hold 258 bytes, and pads with 0xffff up to next multiple of 26 */
static inline int short2long_name(char* dest,const char* src)
{
    int i;
    int len;
    for(i=0;i<129 && src[i];i++) {
        dest[2*i]=src[i];
	dest[2*i+1]=0;
    }
    len=2*i;
    dest[2*i]=dest[2*i+1]=0;
    for(i=2*i+2;(i%26);i++)
	dest[i]=0xff;
    return len;
}

static inline direntry_t* create_long_filename(BDRVVVFATState* s,const char* filename)
{
    char buffer[258];
    int length=short2long_name(buffer,filename),
        number_of_entries=(length+25)/26,i;
    direntry_t* entry;

    for(i=0;i<number_of_entries;i++) {
	entry=array_get_next(&(s->directory));
	entry->attributes=0xf;
	entry->reserved[0]=0;
	entry->begin=0;
	entry->name[0]=(number_of_entries-i)|(i==0?0x40:0);
    }
    for(i=0;i<26*number_of_entries;i++) {
	int offset=(i%26);
	if(offset<10) offset=1+offset;
	else if(offset<22) offset=14+offset-10;
	else offset=28+offset-22;
	entry=array_get(&(s->directory),s->directory.next-1-(i/26));
	entry->name[offset]=buffer[i];
    }
    return array_get(&(s->directory),s->directory.next-number_of_entries);
}

static char is_free(const direntry_t* direntry)
{
    return direntry->name[0]==0xe5 || direntry->name[0]==0x00;
}

static char is_volume_label(const direntry_t* direntry)
{
    return direntry->attributes == 0x28;
}

static char is_long_name(const direntry_t* direntry)
{
    return direntry->attributes == 0xf;
}

static char is_short_name(const direntry_t* direntry)
{
    return !is_volume_label(direntry) && !is_long_name(direntry)
	&& !is_free(direntry);
}

static char is_directory(const direntry_t* direntry)
{
    return direntry->attributes & 0x10 && direntry->name[0] != 0xe5;
}

static inline char is_dot(const direntry_t* direntry)
{
    return is_short_name(direntry) && direntry->name[0] == '.';
}

static char is_file(const direntry_t* direntry)
{
    return is_short_name(direntry) && !is_directory(direntry);
}

static inline uint32_t begin_of_direntry(const direntry_t* direntry)
{
    return le16_to_cpu(direntry->begin)|(le16_to_cpu(direntry->begin_hi)<<16);
}

static inline uint32_t filesize_of_direntry(const direntry_t* direntry)
{
    return le32_to_cpu(direntry->size);
}

static void set_begin_of_direntry(direntry_t* direntry, uint32_t begin)
{
    direntry->begin = cpu_to_le16(begin & 0xffff);
    direntry->begin_hi = cpu_to_le16((begin >> 16) & 0xffff);
}

/* fat functions */

static inline uint8_t fat_chksum(const direntry_t* entry)
{
    uint8_t chksum=0;
    int i;

    for(i=0;i<11;i++)
	chksum=(((chksum&0xfe)>>1)|((chksum&0x01)?0x80:0))
	    +(unsigned char)entry->name[i];

    return chksum;
}

/* if return_time==0, this returns the fat_date, else the fat_time */
static uint16_t fat_datetime(time_t time,int return_time) {
    struct tm* t;
#ifdef _WIN32
    t=localtime(&time); /* this is not thread safe */
#else
    struct tm t1;
    t=&t1;
    localtime_r(&time,t);
#endif
    if(return_time)
	return cpu_to_le16((t->tm_sec/2)|(t->tm_min<<5)|(t->tm_hour<<11));
    return cpu_to_le16((t->tm_mday)|((t->tm_mon+1)<<5)|((t->tm_year-80)<<9));
}

static inline void fat_set(BDRVVVFATState* s,unsigned int cluster,uint32_t value)
{
    if(s->fat_type==32) {
	uint32_t* entry=array_get(&(s->fat),cluster);
	*entry=cpu_to_le32(value);
    } else if(s->fat_type==16) {
	uint16_t* entry=array_get(&(s->fat),cluster);
	*entry=cpu_to_le16(value&0xffff);
    } else {
	int offset = (cluster*3/2);
	unsigned char* p = array_get(&(s->fat), offset);
        switch (cluster&1) {
	case 0:
		p[0] = value&0xff;
		p[1] = (p[1]&0xf0) | ((value>>8)&0xf);
		break;
	case 1:
		p[0] = (p[0]&0xf) | ((value&0xf)<<4);
		p[1] = (value>>4);
		break;
	}
    }
}

static inline uint32_t fat_get(BDRVVVFATState* s,unsigned int cluster)
{
    if(s->fat_type==32) {
	uint32_t* entry=array_get(&(s->fat),cluster);
	return le32_to_cpu(*entry);
    } else if(s->fat_type==16) {
	uint16_t* entry=array_get(&(s->fat),cluster);
	return le16_to_cpu(*entry);
    } else {
	const uint8_t* x=(uint8_t*)(s->fat.pointer)+cluster*3/2;
	return ((x[0]|(x[1]<<8))>>(cluster&1?4:0))&0x0fff;
    }
}

static inline int fat_eof(BDRVVVFATState* s,uint32_t fat_entry)
{
    if(fat_entry>s->max_fat_value-8)
	return -1;
    return 0;
}

static inline void init_fat(BDRVVVFATState* s)
{
    if (s->fat_type == 12) {
	array_init(&(s->fat),1);
	array_ensure_allocated(&(s->fat),
		s->sectors_per_fat * 0x200 * 3 / 2 - 1);
    } else {
	array_init(&(s->fat),(s->fat_type==32?4:2));
	array_ensure_allocated(&(s->fat),
		s->sectors_per_fat * 0x200 / s->fat.item_size - 1);
    }
    memset(s->fat.pointer,0,s->fat.size);

    switch(s->fat_type) {
	case 12: s->max_fat_value=0xfff; break;
	case 16: s->max_fat_value=0xffff; break;
	case 32: s->max_fat_value=0x0fffffff; break;
	default: s->max_fat_value=0; /* error... */
    }

}

/* TODO: in create_short_filename, 0xe5->0x05 is not yet handled! */
/* TODO: in parse_short_filename, 0x05->0xe5 is not yet handled! */
static inline direntry_t* create_short_and_long_name(BDRVVVFATState* s,
	unsigned int directory_start, const char* filename, int is_dot)
{
    int i,j,long_index=s->directory.next;
    direntry_t* entry=0;
    direntry_t* entry_long=0;

    if(is_dot) {
	entry=array_get_next(&(s->directory));
	memset(entry->name,0x20,11);
	memcpy(entry->name,filename,strlen(filename));
	return entry;
    }

    entry_long=create_long_filename(s,filename);

    i = strlen(filename);
    for(j = i - 1; j>0  && filename[j]!='.';j--);
    if (j > 0)
	i = (j > 8 ? 8 : j);
    else if (i > 8)
	i = 8;

    entry=array_get_next(&(s->directory));
    memset(entry->name,0x20,11);
    strncpy((char*)entry->name,filename,i);

    if(j > 0)
	for (i = 0; i < 3 && filename[j+1+i]; i++)
	    entry->extension[i] = filename[j+1+i];

    /* upcase & remove unwanted characters */
    for(i=10;i>=0;i--) {
	if(i==10 || i==7) for(;i>0 && entry->name[i]==' ';i--);
	if(entry->name[i]<=' ' || entry->name[i]>0x7f
		|| strchr(".*?<>|\":/\\[];,+='",entry->name[i]))
	    entry->name[i]='_';
        else if(entry->name[i]>='a' && entry->name[i]<='z')
            entry->name[i]+='A'-'a';
    }

    /* mangle duplicates */
    while(1) {
	direntry_t* entry1=array_get(&(s->directory),directory_start);
	int j;

	for(;entry1<entry;entry1++)
	    if(!is_long_name(entry1) && !memcmp(entry1->name,entry->name,11))
		break; /* found dupe */
	if(entry1==entry) /* no dupe found */
	    break;

	/* use all 8 characters of name */
	if(entry->name[7]==' ') {
	    int j;
	    for(j=6;j>0 && entry->name[j]==' ';j--)
		entry->name[j]='~';
	}

	/* increment number */
	for(j=7;j>0 && entry->name[j]=='9';j--)
	    entry->name[j]='0';
	if(j>0) {
	    if(entry->name[j]<'0' || entry->name[j]>'9')
	        entry->name[j]='0';
	    else
	        entry->name[j]++;
	}
    }

    /* calculate checksum; propagate to long name */
    if(entry_long) {
        uint8_t chksum=fat_chksum(entry);

	/* calculate anew, because realloc could have taken place */
	entry_long=array_get(&(s->directory),long_index);
	while(entry_long<entry && is_long_name(entry_long)) {
	    entry_long->reserved[1]=chksum;
	    entry_long++;
	}
    }

    return entry;
}

/*
 * Read a directory. (the index of the corresponding mapping must be passed).
 */
static int read_directory(BDRVVVFATState* s, int mapping_index)
{
    mapping_t* mapping = array_get(&(s->mapping), mapping_index);
    direntry_t* direntry;
    const char* dirname = mapping->path;
    int first_cluster = mapping->begin;
    int parent_index = mapping->info.dir.parent_mapping_index;
    mapping_t* parent_mapping = (mapping_t*)
	(parent_index >= 0 ? array_get(&(s->mapping), parent_index) : 0);
    int first_cluster_of_parent = parent_mapping ? parent_mapping->begin : -1;

    DIR* dir=opendir(dirname);
    struct dirent* entry;
    int i;

    assert(mapping->mode & MODE_DIRECTORY);

    if(!dir) {
	mapping->end = mapping->begin;
	return -1;
    }

    i = mapping->info.dir.first_dir_index =
	    first_cluster == 0 ? 0 : s->directory.next;

    /* actually read the directory, and allocate the mappings */
    while((entry=readdir(dir))) {
	unsigned int length=strlen(dirname)+2+strlen(entry->d_name);
        char* buffer;
	direntry_t* direntry;
        struct stat st;
	int is_dot=!strcmp(entry->d_name,".");
	int is_dotdot=!strcmp(entry->d_name,"..");

	if(first_cluster == 0 && (is_dotdot || is_dot))
	    continue;

	buffer=(char*)malloc(length);
	assert(buffer);
	snprintf(buffer,length,"%s/%s",dirname,entry->d_name);

	if(stat(buffer,&st)<0) {
	    free(buffer);
            continue;
	}

	/* create directory entry for this file */
	direntry=create_short_and_long_name(s, i, entry->d_name,
		is_dot || is_dotdot);
	direntry->attributes=(S_ISDIR(st.st_mode)?0x10:0x20);
	direntry->reserved[0]=direntry->reserved[1]=0;
	direntry->ctime=fat_datetime(st.st_ctime,1);
	direntry->cdate=fat_datetime(st.st_ctime,0);
	direntry->adate=fat_datetime(st.st_atime,0);
	direntry->begin_hi=0;
	direntry->mtime=fat_datetime(st.st_mtime,1);
	direntry->mdate=fat_datetime(st.st_mtime,0);
	if(is_dotdot)
	    set_begin_of_direntry(direntry, first_cluster_of_parent);
	else if(is_dot)
	    set_begin_of_direntry(direntry, first_cluster);
	else
	    direntry->begin=0; /* do that later */
        if (st.st_size > 0x7fffffff) {
	    fprintf(stderr, "File %s is larger than 2GB\n", buffer);
	    free(buffer);
	    return -2;
        }
	direntry->size=cpu_to_le32(S_ISDIR(st.st_mode)?0:st.st_size);

	/* create mapping for this file */
	if(!is_dot && !is_dotdot && (S_ISDIR(st.st_mode) || st.st_size)) {
	    s->current_mapping=(mapping_t*)array_get_next(&(s->mapping));
	    s->current_mapping->begin=0;
	    s->current_mapping->end=st.st_size;
	    /*
	     * we get the direntry of the most recent direntry, which
	     * contains the short name and all the relevant information.
	     */
	    s->current_mapping->dir_index=s->directory.next-1;
	    s->current_mapping->first_mapping_index = -1;
	    if (S_ISDIR(st.st_mode)) {
		s->current_mapping->mode = MODE_DIRECTORY;
		s->current_mapping->info.dir.parent_mapping_index =
		    mapping_index;
	    } else {
		s->current_mapping->mode = MODE_UNDEFINED;
		s->current_mapping->info.file.offset = 0;
	    }
	    s->current_mapping->path=buffer;
	    s->current_mapping->read_only =
		(st.st_mode & (S_IWUSR | S_IWGRP | S_IWOTH)) == 0;
	}
    }
    closedir(dir);

    /* fill with zeroes up to the end of the cluster */
    while(s->directory.next%(0x10*s->sectors_per_cluster)) {
	direntry_t* direntry=array_get_next(&(s->directory));
	memset(direntry,0,sizeof(direntry_t));
    }

/* TODO: if there are more entries, bootsector has to be adjusted! */
#define ROOT_ENTRIES (0x02 * 0x10 * s->sectors_per_cluster)
    if (mapping_index == 0 && s->directory.next < ROOT_ENTRIES) {
	/* root directory */
	int cur = s->directory.next;
	array_ensure_allocated(&(s->directory), ROOT_ENTRIES - 1);
	memset(array_get(&(s->directory), cur), 0,
		(ROOT_ENTRIES - cur) * sizeof(direntry_t));
    }

     /* reget the mapping, since s->mapping was possibly realloc()ed */
    mapping = (mapping_t*)array_get(&(s->mapping), mapping_index);
    first_cluster += (s->directory.next - mapping->info.dir.first_dir_index)
	* 0x20 / s->cluster_size;
    mapping->end = first_cluster;

    direntry = (direntry_t*)array_get(&(s->directory), mapping->dir_index);
    set_begin_of_direntry(direntry, mapping->begin);

    return 0;
}

static inline uint32_t sector2cluster(BDRVVVFATState* s,off_t sector_num)
{
    return (sector_num-s->faked_sectors)/s->sectors_per_cluster;
}

static inline off_t cluster2sector(BDRVVVFATState* s, uint32_t cluster_num)
{
    return s->faked_sectors + s->sectors_per_cluster * cluster_num;
}

static inline uint32_t sector_offset_in_cluster(BDRVVVFATState* s,off_t sector_num)
{
    return (sector_num-s->first_sectors_number-2*s->sectors_per_fat)%s->sectors_per_cluster;
}

#ifdef DBG
static direntry_t* get_direntry_for_mapping(BDRVVVFATState* s,mapping_t* mapping)
{
    if(mapping->mode==MODE_UNDEFINED)
	return 0;
    return (direntry_t*)(s->directory.pointer+sizeof(direntry_t)*mapping->dir_index);
}
#endif

static int init_directories(BDRVVVFATState* s,
	const char* dirname)
{
    bootsector_t* bootsector;
    mapping_t* mapping;
    unsigned int i;
    unsigned int cluster;

    memset(&(s->first_sectors[0]),0,0x40*0x200);

    s->cluster_size=s->sectors_per_cluster*0x200;
    s->cluster_buffer=malloc(s->cluster_size);
    assert(s->cluster_buffer);

    /*
     * The formula: sc = spf+1+spf*spc*(512*8/fat_type),
     * where sc is sector_count,
     * spf is sectors_per_fat,
     * spc is sectors_per_clusters, and
     * fat_type = 12, 16 or 32.
     */
    i = 1+s->sectors_per_cluster*0x200*8/s->fat_type;
    s->sectors_per_fat=(s->sector_count+i)/i; /* round up */

    array_init(&(s->mapping),sizeof(mapping_t));
    array_init(&(s->directory),sizeof(direntry_t));

    /* add volume label */
    {
	direntry_t* entry=array_get_next(&(s->directory));
	entry->attributes=0x28; /* archive | volume label */
	snprintf((char*)entry->name,11,"QEMU VVFAT");
    }

    /* Now build FAT, and write back information into directory */
    init_fat(s);

    s->faked_sectors=s->first_sectors_number+s->sectors_per_fat*2;
    s->cluster_count=sector2cluster(s, s->sector_count);

    mapping = array_get_next(&(s->mapping));
    mapping->begin = 0;
    mapping->dir_index = 0;
    mapping->info.dir.parent_mapping_index = -1;
    mapping->first_mapping_index = -1;
    mapping->path = strdup(dirname);
    i = strlen(mapping->path);
    if (i > 0 && mapping->path[i - 1] == '/')
	mapping->path[i - 1] = '\0';
    mapping->mode = MODE_DIRECTORY;
    mapping->read_only = 0;
    s->path = mapping->path;

    for (i = 0, cluster = 0; i < s->mapping.next; i++) {
	int j;
	/* MS-DOS expects the FAT to be 0 for the root directory
	 * (except for the media byte). */
	/* LATER TODO: still true for FAT32? */
	int fix_fat = (i != 0);
	mapping = array_get(&(s->mapping), i);

        if (mapping->mode & MODE_DIRECTORY) {
	    mapping->begin = cluster;
	    if(read_directory(s, i)) {
		fprintf(stderr, "Could not read directory %s\n",
			mapping->path);
		return -1;
	    }
	    mapping = array_get(&(s->mapping), i);
	} else {
	    assert(mapping->mode == MODE_UNDEFINED);
	    mapping->mode=MODE_NORMAL;
	    mapping->begin = cluster;
	    if (mapping->end > 0) {
		direntry_t* direntry = array_get(&(s->directory),
			mapping->dir_index);

		mapping->end = cluster + 1 + (mapping->end-1)/s->cluster_size;
		set_begin_of_direntry(direntry, mapping->begin);
	    } else {
		mapping->end = cluster + 1;
		fix_fat = 0;
	    }
	}

	assert(mapping->begin < mapping->end);

	/* fix fat for entry */
	if (fix_fat) {
	    for(j = mapping->begin; j < mapping->end - 1; j++)
		fat_set(s, j, j+1);
	    fat_set(s, mapping->end - 1, s->max_fat_value);
	}

	/* next free cluster */
	cluster = mapping->end;

	if(cluster > s->cluster_count) {
	    fprintf(stderr,"Directory does not fit in FAT%d\n",s->fat_type);
	    return -1;
	}
    }

    mapping = array_get(&(s->mapping), 0);
    s->sectors_of_root_directory = mapping->end * s->sectors_per_cluster;
    s->last_cluster_of_root_directory = mapping->end;

    /* the FAT signature */
    fat_set(s,0,s->max_fat_value);
    fat_set(s,1,s->max_fat_value);

    s->current_mapping = NULL;

    bootsector=(bootsector_t*)(s->first_sectors+(s->first_sectors_number-1)*0x200);
    bootsector->jump[0]=0xeb;
    bootsector->jump[1]=0x3e;
    bootsector->jump[2]=0x90;
    memcpy(bootsector->name,"QEMU    ",8);
    bootsector->sector_size=cpu_to_le16(0x200);
    bootsector->sectors_per_cluster=s->sectors_per_cluster;
    bootsector->reserved_sectors=cpu_to_le16(1);
    bootsector->number_of_fats=0x2; /* number of FATs */
    bootsector->root_entries=cpu_to_le16(s->sectors_of_root_directory*0x10);
    bootsector->total_sectors16=s->sector_count>0xffff?0:cpu_to_le16(s->sector_count);
    bootsector->media_type=(s->fat_type!=12?0xf8:s->sector_count==5760?0xf9:0xf8); /* media descriptor */
    s->fat.pointer[0] = bootsector->media_type;
    bootsector->sectors_per_fat=cpu_to_le16(s->sectors_per_fat);
    bootsector->sectors_per_track=cpu_to_le16(s->bs->secs);
    bootsector->number_of_heads=cpu_to_le16(s->bs->heads);
    bootsector->hidden_sectors=cpu_to_le32(s->first_sectors_number==1?0:0x3f);
    bootsector->total_sectors=cpu_to_le32(s->sector_count>0xffff?s->sector_count:0);

    /* LATER TODO: if FAT32, this is wrong */
    bootsector->u.fat16.drive_number=s->fat_type==12?0:0x80; /* assume this is hda (TODO) */
    bootsector->u.fat16.current_head=0;
    bootsector->u.fat16.signature=0x29;
    bootsector->u.fat16.id=cpu_to_le32(0xfabe1afd);

    memcpy(bootsector->u.fat16.volume_label,"QEMU VVFAT ",11);
    memcpy(bootsector->fat_type,(s->fat_type==12?"FAT12   ":s->fat_type==16?"FAT16   ":"FAT32   "),8);
    bootsector->magic[0]=0x55; bootsector->magic[1]=0xaa;

    return 0;
}

#ifdef DEBUG
static BDRVVVFATState *vvv = NULL;
#endif

static int enable_write_target(BDRVVVFATState *s);
static int is_consistent(BDRVVVFATState *s);

static int vvfat_open(BlockDriverState *bs, const char* dirname, int flags)
{
    BDRVVVFATState *s = bs->opaque;
    int floppy = 0;
    int i;

#ifdef DEBUG
    vvv = s;
#endif

DLOG(if (stderr == NULL) {
    stderr = fopen("vvfat.log", "a");
    setbuf(stderr, NULL);
})

    s->bs = bs;

    s->fat_type=16;
    /* LATER TODO: if FAT32, adjust */
    s->sectors_per_cluster=0x10;
    /* 504MB disk*/
    bs->cyls=1024; bs->heads=16; bs->secs=63;

    s->current_cluster=0xffffffff;

    s->first_sectors_number=0x40;
    /* read only is the default for safety */
    bs->read_only = 1;
    s->qcow = s->write_target = NULL;
    s->qcow_filename = NULL;
    s->fat2 = NULL;
    s->downcase_short_names = 1;

    if (!strstart(dirname, "fat:", NULL))
	return -1;

    if (strstr(dirname, ":floppy:")) {
	floppy = 1;
	s->fat_type = 12;
	s->first_sectors_number = 1;
	s->sectors_per_cluster=2;
	bs->cyls = 80; bs->heads = 2; bs->secs = 36;
    }

    s->sector_count=bs->cyls*bs->heads*bs->secs;

    if (strstr(dirname, ":32:")) {
	fprintf(stderr, "Big fat greek warning: FAT32 has not been tested. You are welcome to do so!\n");
	s->fat_type = 32;
    } else if (strstr(dirname, ":16:")) {
	s->fat_type = 16;
    } else if (strstr(dirname, ":12:")) {
	s->fat_type = 12;
	s->sector_count=2880;
    }

    if (strstr(dirname, ":rw:")) {
	if (enable_write_target(s))
	    return -1;
	bs->read_only = 0;
    }

    i = strrchr(dirname, ':') - dirname;
    assert(i >= 3);
    if (dirname[i-2] == ':' && isalpha(dirname[i-1]))
	/* workaround for DOS drive names */
	dirname += i-1;
    else
	dirname += i+1;

    bs->total_sectors=bs->cyls*bs->heads*bs->secs;

    if(init_directories(s, dirname))
	return -1;

    s->sector_count = s->faked_sectors + s->sectors_per_cluster*s->cluster_count;

    if(s->first_sectors_number==0x40)
	init_mbr(s);

    /* for some reason or other, MS-DOS does not like to know about CHS... */
    if (floppy)
	bs->heads = bs->cyls = bs->secs = 0;

    //    assert(is_consistent(s));
    return 0;
}

static inline void vvfat_close_current_file(BDRVVVFATState *s)
{
    if(s->current_mapping) {
	s->current_mapping = NULL;
	if (s->current_fd) {
		close(s->current_fd);
		s->current_fd = 0;
	}
    }
    s->current_cluster = -1;
}

/* mappings between index1 and index2-1 are supposed to be ordered
 * return value is the index of the last mapping for which end>cluster_num
 */
static inline int find_mapping_for_cluster_aux(BDRVVVFATState* s,int cluster_num,int index1,int index2)
{
    int index3=index1+1;
    while(1) {
	mapping_t* mapping;
	index3=(index1+index2)/2;
	mapping=array_get(&(s->mapping),index3);
	assert(mapping->begin < mapping->end);
	if(mapping->begin>=cluster_num) {
	    assert(index2!=index3 || index2==0);
	    if(index2==index3)
		return index1;
	    index2=index3;
	} else {
	    if(index1==index3)
		return mapping->end<=cluster_num ? index2 : index1;
	    index1=index3;
	}
	assert(index1<=index2);
	DLOG(mapping=array_get(&(s->mapping),index1);
	assert(mapping->begin<=cluster_num);
	assert(index2 >= s->mapping.next ||
		((mapping = array_get(&(s->mapping),index2)) &&
		mapping->end>cluster_num)));
    }
}

static inline mapping_t* find_mapping_for_cluster(BDRVVVFATState* s,int cluster_num)
{
    int index=find_mapping_for_cluster_aux(s,cluster_num,0,s->mapping.next);
    mapping_t* mapping;
    if(index>=s->mapping.next)
	return 0;
    mapping=array_get(&(s->mapping),index);
    if(mapping->begin>cluster_num)
	return 0;
    assert(mapping->begin<=cluster_num && mapping->end>cluster_num);
    return mapping;
}

/*
 * This function simply compares path == mapping->path. Since the mappings
 * are sorted by cluster, this is expensive: O(n).
 */
static inline mapping_t* find_mapping_for_path(BDRVVVFATState* s,
	const char* path)
{
    int i;

    for (i = 0; i < s->mapping.next; i++) {
	mapping_t* mapping = array_get(&(s->mapping), i);
	if (mapping->first_mapping_index < 0 &&
		!strcmp(path, mapping->path))
	    return mapping;
    }

    return NULL;
}

static int open_file(BDRVVVFATState* s,mapping_t* mapping)
{
    if(!mapping)
	return -1;
    if(!s->current_mapping ||
	    strcmp(s->current_mapping->path,mapping->path)) {
	/* open file */
	int fd = open(mapping->path, O_RDONLY | O_BINARY | O_LARGEFILE);
	if(fd<0)
	    return -1;
	vvfat_close_current_file(s);
	s->current_fd = fd;
	s->current_mapping = mapping;
    }
    return 0;
}

static inline int read_cluster(BDRVVVFATState *s,int cluster_num)
{
    if(s->current_cluster != cluster_num) {
	int result=0;
	off_t offset;
	assert(!s->current_mapping || s->current_fd || (s->current_mapping->mode & MODE_DIRECTORY));
	if(!s->current_mapping
		|| s->current_mapping->begin>cluster_num
		|| s->current_mapping->end<=cluster_num) {
	    /* binary search of mappings for file */
	    mapping_t* mapping=find_mapping_for_cluster(s,cluster_num);

	    assert(!mapping || (cluster_num>=mapping->begin && cluster_num<mapping->end));

	    if (mapping && mapping->mode & MODE_DIRECTORY) {
		vvfat_close_current_file(s);
		s->current_mapping = mapping;
read_cluster_directory:
		offset = s->cluster_size*(cluster_num-s->current_mapping->begin);
		s->cluster = (unsigned char*)s->directory.pointer+offset
			+ 0x20*s->current_mapping->info.dir.first_dir_index;
		assert(((s->cluster-(unsigned char*)s->directory.pointer)%s->cluster_size)==0);
		assert((char*)s->cluster+s->cluster_size <= s->directory.pointer+s->directory.next*s->directory.item_size);
		s->current_cluster = cluster_num;
		return 0;
	    }

	    if(open_file(s,mapping))
		return -2;
	} else if (s->current_mapping->mode & MODE_DIRECTORY)
	    goto read_cluster_directory;

	assert(s->current_fd);

	offset=s->cluster_size*(cluster_num-s->current_mapping->begin)+s->current_mapping->info.file.offset;
	if(lseek(s->current_fd, offset, SEEK_SET)!=offset)
	    return -3;
	s->cluster=s->cluster_buffer;
	result=read(s->current_fd,s->cluster,s->cluster_size);
	if(result<0) {
	    s->current_cluster = -1;
	    return -1;
	}
	s->current_cluster = cluster_num;
    }
    return 0;
}

#ifdef DEBUG
static void hexdump(const void* address, uint32_t len)
{
    const unsigned char* p = address;
    int i, j;

    for (i = 0; i < len; i += 16) {
	for (j = 0; j < 16 && i + j < len; j++)
	    fprintf(stderr, "%02x ", p[i + j]);
	for (; j < 16; j++)
	    fprintf(stderr, "   ");
	fprintf(stderr, " ");
	for (j = 0; j < 16 && i + j < len; j++)
	    fprintf(stderr, "%c", (p[i + j] < ' ' || p[i + j] > 0x7f) ? '.' : p[i + j]);
	fprintf(stderr, "\n");
    }
}

static void print_direntry(const direntry_t* direntry)
{
    int j = 0;
    char buffer[1024];

    fprintf(stderr, "direntry 0x%x: ", (int)direntry);
    if(!direntry)
	return;
    if(is_long_name(direntry)) {
	unsigned char* c=(unsigned char*)direntry;
	int i;
	for(i=1;i<11 && c[i] && c[i]!=0xff;i+=2)