_THE MICROSOFT FLASH FILE SYSTEM_
by Peter Torelli

Listing One

struct FileOrDirectoryEntry {   struct FileInfoStructure {
    word    Status;         word    Status
    dword   SiblingPtr;     dword   SiblingPtr;
    dword   PrimaryPtr;     dword   ExtentPtr;
    dword   SecondaryPtr;   dword   SecondaryPtr;
    byte    Attributes;     byte    Attributes;
    word    Time;           word    Time;
    word    Date;           word    Date;
    word    VarStructLen;   word    VarStructLen
    byte    NameLen;        word    UncompressedExtentLen
    byte    Name[8];        word    CompressedExtentLen
    byte    Ext[3];     };
};


Listing Two

struct BlockAllocationStructure {   struct BlockAllocationMember {
    dword   BootRecordPtr;          byte    Status;
    dword   EraseCount;             byte    Offset[3];
    word    BlockSeq;               word    Len;
    word    BlockSeqChecksum;       };
    word    Status;
};


Listing Three

struct BlockAllocStruct read_BAS( UINT block ) {
  struct BlockAllocStruct BAS;
  dword  address=0UL;

  /* Calculate the top of the physical block address. */
  address = (ULONG) ( block * (ULONG) block_size );
  /* Subtract back the size of a BlockAllocStruct. */
  address -= sizeof( struct BlockAllocStruct );
  /* Read it. */
  read_memory( (UCHAR *) &BAS, address, sizeof( struct BlockAllocStruct ) );
  /* Return the BAS. */
  return BAS;
}


Listing Four

UINT log2phy( UINT lblock ) {
  struct BlockAllocStruct CurBAS;
  UINT   block=0;
  ULONG  address=0UL;

  /* Start at physical block 1. */
  block = 1;
  /* Read each BAS. */
  while( block <= NumBlocks ) {
    CurBAS = read_BAS( block );
    /* Look for the sequence that matches our requested lblock. */
    if( CurBAS.BlockSeq == lblock ) break;
    block++;
  }
  return block;
}
struct BlockAllocMember get_BAM_data( ULONG BAMptr ) {
  struct BlockAllocMember BAM;
  UINT   logical_BAM=0;
  UINT   logical_block=0;
  UINT   physical_block=0;
  ULONG  address=0UL;
  /* Determine the logical Block and BAM number. */
  logical_block  = (ULONG) BAMptr >> 16;
  logical_BAM    = BAMptr & 0xFFFF;
  /* Call the routine that determines the physical block number.  This
     might actually parse each BAS, or it may be read from a look-up table
     that FFS creates for every card insertion and maintains thereafter.  For
     now, translate by reading the BASs. */
  physical_block = log2phy( logical_block );
  /* Determine the top of the physical blocks address. */
  address  = (ULONG) ( physical_block * block_size );
  /* Subtract from it the size of a BAS plus the Number of BAMs
     preceeding the BAM we wish to read. */
  address -= ( sizeof( BlockAllocStruct ) + 
               ( ( logical_BAM + 1 ) * sizeof( struct BlockAllocMember ) ) );
  /* Read the BAM. */
  read_memory( (UCHAR *) &BAM, address, sizeof( struct BlockAllocMember ) );
  /* Return the BAM. */
  return BAM;
}


Listing Five

ULONG get_block_base( ULONG BAMptr ) {
  UINT lblock=0;
  UINT block=0;

  /* Get the logical block # from the BAM. */
  lblock = ( (ULONG) BAMptr ) >> 16;
  /* Translate it to physical. */
  block = log2phy( lblock );
  /* Return its physical base address. */
  return ( ( block - 1 ) * block_size );
}


Listing Six

ULONG translate_BAM_offset( ULONG BAM ) {
  ULONG address=0UL;

  /* Sum the BAM offset components. */
  address = (   ( (ULONG) BAM.Offset[0] ) + 
              ( ( (ULONG) BAM.Offset[1] ) << 8  ) + 
              ( ( (ULONG) BAM.Offset[2] ) << 16 ) );
  return address;
}


Listing Seven

struct FEDE_Entry get_FEDE( ULONG CurrentBAMptr ) {
  struct BlockAllocMember BAM;
  struct FEDE_Entry FEDE;
  ULONG  address=0UL;
  UINT   length=0;
  
  /* Read the BAM data. */
  BAM = get_BAM_data( CurrentBAMptr );
  /* Determine the base absolute address of the Boot Record's block. */
  address = get_block_base( CurrentBAMptr );
  /* Calculate the offset (in that block) of the Boot Record. */
  address += translate_BAM_offset( BAM );
  /* Reat the structure. */
  read_memory( (UCHAR *) &FEDE, address, sizeof( struct FEDE_Entry ) );
  /* And return it. */
  return FEDE;
}

Listing Eight

ULONG go_to_end_of_FEDE( ULONG CurrentBAMptr ) {
  struct FEDE_Entry FEDE;
  UCHAR  buffer[12];

  /* Start traversing at the given point in list specified by CurrentBAMptr. */
  do {
    /* Read the FEDE structure. */
    FEDE = get_FEDE( CurrentBAMptr );
    /* Un-comment the following lines and this code will print out 
       the filenames as it goes.  Passing it the PrimaryPtr of the parent
       directory would list all of the files/subdirs in that directory. */
     /* strncpy( buffer, FEDE.Name, 11 ); */
     /* buffer[11]=0; */
     /* printf("%s\n", buffer); */
    /* If the this isn't the last element, then save the next pointer. */
    if( FEDE.SiblingPtr != FNULL ) CurrentBAMptr = FEDE.SiblingPtr;
    /* Otherwise exit the loop. */
  } while( FEDE.SiblingPtr != FNULL );
  /* The CurrentBAMptr now references the last structure of the chain. */
  return CurrentBAMptr;
}


Listing Nine

void add_FEDE_sibling( ULONG CurrentBAMptr, ULONG LinkBAMptr ) {
  struct BlockAllocMember BAM;
  struct FEDE_Entry FEDE;
  ULONG  LastBAMptr=0UL;
  UINT   length=0;
  ULONG  address=0UL;

  /* Go to the end of current FEDE chain. */
  LastBAMptr = go_to_end_of_FEDE( CurrentBAMptr );
  /* Read the FEDE. */
  FEDE = get_FEDE( LastBAMptr );
  /* Connect the link and update the status bits. */
  FEDE.SiblingPtr = LinkBAMptr;
  /* Zero bit 6 of the status word, indicating the SiblingPtr is valid. */
  FEDE.Status &= 0xFFCF;
  /* Since only the Sibling pointer and status get programmed (the other data
     remains unchanged) re-write the new data to the same location. */
  address = get_block_base( CurrentBAMptr );
  address += translate_BAM_offset( BAM );
  write_memory( (UCHAR *) &FEDE, address, sizeof( struct FEDE_Entry ) );
}


Listing Ten

ULONG find_Boot_Record( void ) {
  struct BlockAllocStruct BAS;
  UINT   current_block=0;
  UCHAR  got_BR_flag=FALSE;

  /* Start at physical block one. */
  current_block = 1;
  /* Loop through physical blocks until we find the Boot Record. */
  do {
    /* Read the BAS of the current BAS. */
    BAS = read_BAS( current_block );
    /* No Boot Record, go to next block. */
    if( BAS.Status & 0x70 != 0x30 ) current_block++;
    /* Otherwise set our flag and break with the correct block. */
    else {
      got_BR_flag = TRUE;
      break;
    }
    /* Make sure we don't run out of blocks (external variable) just
       in case this card was not formatted previously. */
  } while( current_block <= number_of_blocks );
  /* If the flag wasn't set then we didn't find the Boot Record. */
  if( !got_BR_flag ) return ERROR; 
  /* Otherwise, return the Boot Record Pointer. */
  return BAS.BootRecordPtr;
}


Listing Eleven

struct BootRecord read_Boot_Record( ULONG BootRecBAMptr ) {
  struct BootRecord BR;
  struct BlockAllocMember BAM;
  ULONG address=0UL;
  UINT length=0;

  /* Given the root directory BAM pointer, read the BAM to find structure. */
  BAM = get_BAM_data( BootRecBAMptr );
  /* Determine the base absolute address of the Boot Record's block. */
  address = get_block_base( BootRecBAMptr );
  /* Calculate the offset (in that block) of the Boot Record. */
  address += translate_BAM_offset( BAM );
  /* Read it. */
  read_memory( (UCHAR *) &BR, address, sizeof( BootRecord ) );
  /* Return the Boot Record. */
  return BR;  
}


Listing Twelve

ULONG get_ROOT_BAM( void ) {
  struct BootRecord BR;
  ULONG  BAMptr=0UL;

  /* Search for the Boot Record BAM. */
  BAMptr = find_Boot_Record();
  /* Read the Boot Record. */
  BR = read_Boot_Record( BAMptr );
  /* Return the ROOT BAM Pointer;
  return BR.RootDirectoryPtr;
}


Listing Thirteen

ULONG find_in_FEDE( char *DOSname, ULONG topBAMptr ) {
  struct FEDE_Entry FEDE;
  UCHAR  index=0;
  UCHAR  error=FALSE;
  char   buffer[12];
  
  /* Start traversing the FEDE chain starting with topBAMptr. */
  do {
    error=FALSE;
    index = 0;
    /* Read each FEDE element. */
    FEDE = get_FEDE( topBAMptr );
    /* Compare the first 8 characters of the 11 char. DOS name. */
    do {
      /* If one character doesnt match, set the error flag and break. */
      if( DOSname[index] != FEDE.Name[index] ) {
        error = TRUE;
        break;
      }
      index++;
    } while( index < 8 );
    /* If the name matched, check the extension. */
    if( !error ) {
      do {
        if( DOSname[index] != FEDE.Ext[index-8] ) {
          error = TRUE;
          break;
        }
        index++;
      } while( index < 11 );
    }
    /* If we've finished the matching loop WITHOUT an error, than we found
       our entry. */
    if( !error ) break;
    topBAMptr = FEDE.SiblingPtr;
  } while( topBAMptr != FNULL );

  /* There's No point in checking for the topBAMptr to see if we reached
     the end, we defined ERROR as -1 which is a 32 bit FNULL. */
  return topBAMptr;
}


Listing Fourteen

#define TRUE   0
#define FALSE  1
#define ERROR -1

/*  The following assumptions about machine data size are:
      ULONG = dword = 32 bits
      UINT  = word  = 16 bits
      UCHAR = byte  =  8 bits
*/ 

typedef unsigned long ULONG;
typedef unsigned int  UINT;
typedef unsigned char UCHAR;

struct BlockAllocStruct {
  ULONG BootRecordPtr;
  ULONG EraseCount;
  UINT  BlockSeq;
  UINT  BlockSeqChecksum;
  UINT  Status;
};
struct BlockAllocMember {
  UCHAR Status;
  UCHAR Offset[3];
  UINT  Len;
};
struct FEDE_Entry {
  UINT  Status;
  ULONG SiblingPtr;
  ULONG PrimaryPtr;
  ULONG SecondaryPtr;
  UCHAR Attributes;
  UINT  Time;
  UINT  Date;
  UINT  VarStructLen;
  UCHAR NameLen;
  UCHAR Name[8];
  UCHAR Ext[3];
}
/* Function prototypes for our sample code. */
struct BlockAllocStruct read_BAS( UINT block );
UINT   log2phy( UINT lblock );
struct BlockAllocMember get_BAM_data( ULONG BAMptr );
ULONG  get_block_base( ULONG BAMptr );
ULONG  translate_BAM_offset( ULONG BAM );
struct FEDE_Entry get_FEDE( ULONG CurrentBAMptr );
ULONG  go_to_end_of_FEDE( ULONG CurrentBAMptr );
void   add_FEDE_sibling( ULONG CurrentBAMptr, ULONG LinkBAMptr );
ULONG  find_Boot_Record( void );
struct BootRecord read_Boot_Record( ULONG BootRecBAMptr );
ULONG  get_ROOT_BAM( void );
ULONG  find_in_FEDE( char *DOSname, ULONG topBAMptr );

/* The following two procedures are hardware dependent and must be 
included by the OEM. */
UINT read_memory( UCHAR *to_buffer, ULONG from_address, UINT size );
UINT write_memory( UCHAR *from_buffer, ULONG to_address, UINT size );

/* The following external data describe the flash array. */
const extern ULONG block_size;
const extern UINT  number_of_blocks;