NOF file system, for small Flash chips

Under construction!!

NOF idea

Read and store data from/to source files on some sort of background medium. For these purposes a file system could be used. There are lots of variants present: FAT16, FAT32, NTFS, Ext2, Etc.
This design is about a compact file system for small controllers and Flash memory chips. It uses 16-bit CRC-codes instead of file names and directory names. NOF was developed on top of noForth and stands for nOForth File system. It can ofcourse be used on any system with limited resources.

NOF structure

  • The reading is done on a per-byte basis
  • Write goes in 256-byte sectors
  • Erasure is done with sectors of 4096 bytes, or … the entire chip at once
  • The first 4096 bytes is the FET (File Entry Table)
  • The FET sector contains the FID (File ID) & DID (Directory ID)
  • A file has a size of 4096 bytes or a multiple of that
  • Each file-ID is 8-bytes, a directory-ID is 16-bytes
  • The first 32 bytes of a file contains the file name, file type and an auxillary byte

A 2-Mbyte Flash has 512 pages of 4096 bytes. When the first sector is used for the FET, 511 pages are free for files. The FID gets 3072 bytes, the DID the remaining 1024 bytes. This means there is space for 384 files and 64 directories. When you are in need for more files and directories, just take the first two sectors of the Flash chip for administration.

File ID record

        2 Bytes        2 Bytes      2 Bytes        2 Bytes (8 bytes)
    | sector number | dir hash | filename hash | file length |  ( max. 384 files )

Directory ID record

       2 Bytes       2 Bytes        12 bytes  (16 bytes)
    | Dir-hash | Working-Dir-hash | Dir-name string |  ( max. 64 directories )

File header

      Byte Byte      30 bytes
    | FIT | Aux | Filename 30 bytes | File data       |

NOF basic implementation parts

  1. An SPI-driver & setup for the Flash chip
  2. Operating commands for the Flash chip (Write, Read, Erase, etc.)
  3. Some tools (FDUMP dump flash memory)
  4. Multiple file buffers
  5. Directory stack
  6. MOUNT function
  7. Convert a string to 16-bits CRC
  8. Choose & show directory
  9. Find file & include file
  10. Write, Read & Erase given sectors
  11. Build FID entry & file name block

Later on some more additions, like:

  1. Store ASCII files
  2. File viewer
  3. Remove files, wipe complete disk
  4. Make directory and a directory TREE function


Pseudo code for the NOF SPI layer

More detailed info on SPI all numbers in hexadecimal (SPI protocol, general introduction)

Function: FSPI-OUT   ( b -- )  \ Output a byte using SPI-bus
Function: FSPI-IN    ( -- b )  \ Read a byte from SPI-bus
Function: FSPI-SETUP ( +f -- ) \ Initialise SPI-bus to Flash with frequency +f
Function: {FL        ( b -- )  \ Enable Flash access & send first byte 
Function: FL}        ( -- )    \ Close Flash access
Function: {FREAD     ( a c -- b )
    {fl   split 32bit into two 16bit hi part on top   fspi-out
    split 16bit into two 8bit part hi part on top   fspi-out
    fspi-out   fspi-in
Function: FREADY?    ( -- f )
   5 {fl   spi-in   fl}  1 and 0=
Function: WRITE-ON   ( -- )         6 {fl  fl}
Function: BUSY       ( -- )         begin  fready? until
Function: CHIP-ERASE ( -- )         write-on  60 {fl  fl}  busy
Function: POWER-UP   ( -- )         66 {fl  99 fspi-out  fl}
Function: FC@        ( a -- b ) 3   {fread  fl}
Function: FC@+       ( a -- a+1 b ) dup 1 + swap fc@
Function: F@         ( a -- x )     3 {fread  fspi-in  fl} make 16-bit
Function: F@+        ( a -- a+2 x ) dup 2 + swap F@ 
Function: FTYPE      ( a u -- )     0 ?DO  fc@+ emit  LOOP  drop
Function: ID.        ( -- )         0 90 {fread  fspi-in  fl}  .  .
   Save number base & set it to decimal
Function: FDUMP      ( a u -- )
    <freq> fspi-setup  power-up
    0 ?DO   new line and print address followed by ':'
            show 10 bytes from flash memory in hexadecimal
            show 10 bytes as ASCII or a space when not a valid character
            Add 10 to address
            Stop when a key was pressed
    LOOP drop address

Pseudo code for the NOF structure layer


Function: RWDATA      ( A data structure of 7 cells for the NOF structure layer )
Function: !DATA  ( x +n -- )  Store x op position +n in RWDATA
Function: @DATA  ( +n -- x )  Read x from position +n in RWDATA

0000 value #SECTOR    ( Flash sector counter, initialised by MOUNT )
0000 value BUF        ( Buffer in use  0/1 )	 
0000 value #N         ( Byte index in sector buffer )	 
 200000 100 / constant #FLASH ( Minimal flash size, max: 1000000 )
0000 constant #FID    ( Begin address of file ID block )
0C00 constant #DID    ( Begin address of directory ID block )
1000 constant #FILES  ( Begin of file area )

Function: INIT-RWDATA  ( -- )	 
    Write flag is zero, collected data is zero, 	 
    store zero in #n and select buffer-0	 

Function: 'NAME  and reserve 20 bytes for string to convert
create DID and reserve 0C bytes RAM after it  
value DPT   ( Directory nesting pointer )
value 'DID  ( Free directory space pointer )
value 'FID  ( Free file index pointer )
value HASH> ( Hash working space )

Function: .DFREE     ( -- )
    Save number base & set it to decimal
    Subtract #SECTOR from #FLASH and divide by 4
    to convert from sectors to kBytes, print it & restore base

Function: ROOT   ( -- )  0 did h!   0 to dpt
Function: DID>   ( -- )  dpt IF  did dup 2 +  swap dpt move  DPT = DPT + 2  THEN

Function: $>UPC  ( a1 u -- a2 u )
    Store string a1 u1 at 'name, save length
    Convert string in 'name to uppercase
    leave address of converted string & length
Function: IHASH  ( h -- )          Store h in HASH>
Function: >HASH  ( c -- )          Read HASH> xor char c do result times 2 and store in HASH>
Function: HASH   ( a u h0 -- h1 )  Generate file hash h1 from given string a u & hash seed h0
Function: DHASH  ( 'did h0 -- h1 ) Generate dir hash h1 from string stored in 'did+2 & hash seed h0

value FADDR
Function: FKEY   ( -- c )
    faddr fc@  increase faddr  ?dup ?exit  -2 to source-id  0D ;

Function: MOUNT  ( -- )
     <freq> fspi-setup  initialise R/W data structure
     Token of FKEY to alternative KEY-vector
     Initialise 'FID by scanning the FID memory until FFFF is found
     Initialise 'DID by scanning the DID memory until FFFF is found
     Initialise first free file sector from reading the last found file entry
     store it in #SECTOR  finally set directory to the root

Pseudo code for the NOF directory mechanism


Function: CHECK-DHASH  ( h -- f )
    Save current DIR-entry address
    #did 'did over - bounds DO  ( Loop true directory space )
        dup i f@ = IF           ( Is there a hash match? )
            replace dir-entry address
            Leave true and leave loop immediately
    10 +LOOP                    ( To next DIR-entry )
    drop false                  ( No directory found )
Function: .DIR  ( did -- )
    When did is zero its the root show that ans ready
    check-dhash IF
        Read dir-entry address and print it's name

Function: .PATH  ( -- )
    Get DID  read DPT pointer and print
    the current directory nesting in correct order

Function: >DHASH  ( a u -- h1 h0 )
    Limit string to 0E characters ( 00 to 0D )
    Generate root hash value h0 and current DIR hash value h1, leave both

Function: CHOOSE-DIR  ( a u -- )
    >dhash  was it a backslash then select ROOT
    Is it a dot then go back one directory nesting when possible
    check-dhash and abort when it's an invalid directory
    Otherwise extend directory nesting and save current DIR record address

Function: CD  ( "dir" -- )
    Set a new directory nesting by unraveling the given string by parsing it with 
    backslashes. When there is a backslash in front start in the root.
    When the string is done, show the new directory path using .PATH

Function: .FIT  ( +n -- )
    Print file type +n as an ASCII string, +n comes from the 20 bytes file header

Function: DIR  ( -- )
    1) Print current dir path with .PATH
    2) Read current directory entry from DID and print all
       sub)directories in it by calculating the nested hash with DHASH
       Print the directory names that give a valid hash code
    3) Now print the files names, by checking if it's dir-hash code is the
       same as the one stored in DID if so print the file type and the name 
       from the 20 bytes file header
    4) Finally show the free space on the Flash disk using .DFREE

Pseudo code for the NOF file search function


Function: CHECK-FHASH  ( h -- f )
    #fid  'fid bounds ?DO          ( Setup search range )
        Read dir hash value from second cell in FID entry 
        is it equal to the contents of DID
            IF  Read the the file hash from the third cell
                when equal, save this FID record
                leave true and were ready
    8 +LOOP                         ( To next FID entry )
    file hash not found, leave false
Function: >FHASH  ( a u -- h )
    Limit string to 1D chars, do:  $>upc DID h@ dhash
Function: 'SEEK?  ( a u -- sector true | false )
    >fhash  check-fhash IF
        Read the files start sector, leave true & ready
    THEN  print "File not found" & leave false
Function: LOADFILE  ( a -- )
    source-id greater then zero, nest file address pointer
    nest source-id  and store a to faddr
    set source-id to 1
    call interpreter, when done
    unnest source-id
    when source-id is greater then zero unnest faddr & save

Function: SEEK  ( "name" -- sector )
    read blank delimited string "name"
    'seek?  issue error message when result was zero
Function: INCLUDE  ( "name" -- )  immediate word
    abort when used in a definition
    read blank delimited string "name"
    check if it's a forth file ans issue an error message when not
    Calculate the files address & call: loadfile
Function: FILE  ( "name" -- a )  immediate word
    seek  convert sector to file address 
    and compile it as a literal

Pseudocode for creating a file header


Create: 'SECTOR  200 allot  ( -- a )    ( Reserve RAM for two sectors )
Define: ADDR-SECTOR  ( sa -- )
    split sa in low- & high-byte  fspi-out  fspi-out  0 fspi-out
Define: BUFFER  ( +b -- a )
    1 and  100 *  'sector +
Define: READ-SECTOR  ( sa +b -- )
    >r  3 {fl  addr-sector  r> buffer
    100 0 do  fspi-in  over c!  1 +  loop  fl}  drop  

Define: WRITE-SECTOR  ( sa +b -- )
    >r  write-on  2 {fl  addr-sector  r> buffer
    100 0 do  count fspi-out  loop  drop  fl}  busy 

Define: ERASE-SECTOR  ( sa -- )
    write-on  20 {fl  addr-sector  fl}  busy

Define: B,  ( b -- )
    #n 100 = IF  set buffer full flag,  select next buffer and clear #n  THEN  
    store b in current buffer & increase pointer #n

Define: WR-BUFFER  ( -- )
    Write buffer-0 to #sector and increase #sector

Define: <WRITE>  ( -- )
    When buffer overflow has occured do: wr-buffer
    and clear buffer full flag, copy buffer overflow
    from buffer-1 to buffer-0, slect buffer-0 again

Define: !FLENGTH  ( -- )    ( Patch current rounded file length in last FID record )
    Read last used sector, round it to next 10th sector
    Read current part of FID sector to buffer-1
    Patch calculated file length into it
    Write buffer-1 back to current FID sector

Define: FILE-NAME  ( #fit a u -- )
    init-rwdata  limit string to 1D ans make uppercase
    Calculate & check file hash value, abort when the hash value is not unique
    Calculate, save & read current FID-sector in buffer-0
    Save address of new FID record too
    Store DID in record, after that the file-hash
    Now write FID sector back & add 8 to 'FID
    Now store file type on address 0 in buffer-0
    after that the (limited) file name string
    Set #n to 20 and ready

Define: ADD-FID  ( #fit "name" -- )
    Read next word from input stream and build a new file entry with it

NOF files

The added NOF example files are for noForth R on the GD32VF103, especially the seeed board which has a W25Q64 (8 Mbyte) Flash chip added on the board!

File name Purpose in Dropbox (external link)
SPI Flash-03.f NOF SPI layer SPI Flash-03.f
NOF-3i.f NOF base file NOF-3i.f
NOF-write-1.f NOF write NOF-write-1.f
NOF-additions-1.f NOF additions NOF-additions-1.f

Back to PFW page

pfw/file_systems.txt · Zuletzt geändert: 2023-05-19 16:38 von willem