Forum Rule: Always post complete source code & details to reproduce any issue!
Page 3 of 4 FirstFirst 1 2 3 4 LastLast
Results 51 to 75 of 84

Thread: SPI Flash Allocation Table

  1. #51
    Senior Member+ Frank B's Avatar
    Join Date
    Apr 2014
    Location
    Germany NRW
    Posts
    5,679
    I updated the flashingtool, the "c-source" output is:
    Code:
    const int SPIFlash[7] = {
                    0x0000000,  //"201159~1.RAW"
                    0x002C800,  //"82583_~1.RAW"
                    0x0053300,  //"86334_~1.RAW"
                    0x0065B00,  //"86773_~1.RAW"
                    0x01F1D00,  //"102790~1.RAW"
                    0x020A100,  //"171104~1.RAW"
                    0x0214900}; //"P2.RAW"
    
    const char SPIFlashFilename[7][13] = {
                    "201159~1.RAW",
                    "82583_~1.RAW",
                    "86334_~1.RAW",
                    "86773_~1.RAW",
                    "102790~1.RAW",
                    "171104~1.RAW",
                    "P2.RAW"};
    So, you can use these "allocation consts" for now... if you don't need filenames, don't copy them :-)

    Paul, did you think about the allocation table ?
    Last edited by Frank B; 01-25-2015 at 06:29 PM.

  2. #52
    Senior Member PaulStoffregen's Avatar
    Join Date
    Nov 2012
    Posts
    20,546
    This is still near the top of my TO-DO list, but Teensy-LC has been taking all my dev time the last several days.

  3. #53
    Senior Member+ Frank B's Avatar
    Join Date
    Apr 2014
    Location
    Germany NRW
    Posts
    5,679
    Here's my suggestion:

    We can just talk about it, but I would like to finish this theme.
    I want to customize my flashutility and the audio players.

    Code:
    1  byte filetype (=hash of extension without '.')
    1  byte offset of data 0xff = no data, end of list
    1  byte reserved
    3  byte address of next file
    x  filename + #0 (optional)
    data
    The size of this header is 6 Bytes +( length of optional filename + 1 (0x00) . To search a file in our list, we have to read all the fileheaders over SPI until we have found our file, so i tried to keep it as small as possible.


    So..
    1) to open a file with filename (slowest, but one could use a caching-mechanism) :
    - The filetype is a 8bit hash of the fileextension.
    This allows to decide very quick if the file has the correct extension, and if not, jump to the next candidate in the list.
    The second hint is the dataoffset - we can calculate very fast the length of the filename of the current file and compare it with the length of the filename we search. If it's not the same, there is no need to compare the filenames.
    Long filenames are allowed, maximum allowed length is 256 - 7 bytes.
    Edit: If speed matters, they should be short.

    2) Open a file with known index X (number of file)
    - We don't need a filename here, so it's length can be 0 (but not has to be)
    We read X times the 3 bytes address of next file and jump to this position.

    3) Open a file with known address(fastest) ( will be my (personally)preferred method, the flashutil prints c-code;-)
    - trivial.

    For flash larger than 16 Megabyte we can use some bits of the reserved byte (because the 24bits "address of next file" are not enough). Some bits can be used for future extensions.

    Edit: i choosed a hash for the extension, because we don't need to define a list of known extensions in this case + it allows fast compare
    Edit: Hashfunction - Pseudocode:
    for all characters: hash = (hash << 2 ) ^ character
    Last edited by Frank B; 02-22-2015 at 07:57 PM.

  4. #54
    Senior Member
    Join Date
    Feb 2013
    Posts
    563
    sounds good to me. as long as simplicity/efficiency will remain an option, i won't complain. as you say, preferred method will be opening a file by address. file names aren't even easier to deal with. they are, as far as I am concerned, only good for UI purposes.

    I'd be fine with fixing the names to 8.3, having fixed slot sizes might make certain things a bit easier/quicker; then again my thinking is (and i might be wrong), for audio stuff the file info would be mainly used for 3 things once, during start-up: figuring out how many files they are, what their addresses are, and what they're called. so in those cases efficient search isn't of the essence.

  5. #55
    Senior Member+ Frank B's Avatar
    Join Date
    Apr 2014
    Location
    Germany NRW
    Posts
    5,679
    The direct access via address will be as fast as before.
    The length of the filenames is not that important.. it's only of interest when searching a file. To compare the filenames, we have to read the filname via the serial interface.
    That could be cached easyly (an array), but has to be done by the user (I don't think that I want to implement a cache for this) and needs some ram.

    The length of the filenames is controlled by the user If one wants to display them, it's better to allow longer names i think.

    We could make the searching faster with an additional hash for the filename. I'm open to this idea... but do we need that ?
    Last edited by Frank B; 02-22-2015 at 08:18 PM.

  6. #56
    Senior Member
    Join Date
    Feb 2013
    Posts
    563
    Quote Originally Posted by Frank B View Post

    The length of the filenames is controlled by the user If one wants to display them, it's better to allow longer names i think.
    true ...

    Quote Originally Posted by Frank B View Post
    We could make the searching faster with an additional hash for the filename. I'm open to this idea... but do we need that ?
    i'd say no (... i can't speak for everyone of course, but it's hard to imagine a scenario where someone would actually prefer to open the file by its name rather than the address?).

    btw. so is the plan to move the flashing utility into the player libraries? i added a few things to my copy of your play_serialflash library, which makes it easier to use it all in one sketch. it's slightly unintuitive though, ie calling the player object to flash/erase/read from the flash ...
    Last edited by mxxx; 02-22-2015 at 08:24 PM.

  7. #57
    Senior Member+ Frank B's Avatar
    Join Date
    Apr 2014
    Location
    Germany NRW
    Posts
    5,679
    First, I want to make a better version of the flashing-utility. The "File Allocation Table" will be optional - I'ts not needed with direct addressing, so why use it in this case.
    It should be
    - able to flash different chips,
    - don't erase the whole chip every time, instead erase only the needed sectors
    - allow to append files
    - don't align to pages (I don't remember why i did this ;-)

    And yes, i want to make a flashing library(or perhaps Flash-FAT-lib ? ). The utility will use it. So the flash-utility will be optional.
    And, perhaps, in a future version, it will be able to flash the free space of the teensy-inbuilt-flash too. I've already written code for this.

  8. #58
    Senior Member+ Frank B's Avatar
    Join Date
    Apr 2014
    Location
    Germany NRW
    Posts
    5,679
    With the new memory boards from onehorse, and the comming MTP, we need to talk again, i think...

    We have different kinds of memory:
    - the teensy built-in flash
    - the optional flash on the audioboard
    - onehorse's memory boards
    - sd
    - ram(?)

    I would be perfect to have a solution that fits all.. and perhaps we should think of a solution that makes our filesystem compatible to MTP. As far as i know, MTP uses abstract "objects" to access files, so it should be possible, but we need a layer between MTP and the different kinds of memory.

    Edit:
    Perhaps we want that it works _without_ MTP, too.
    Last edited by Frank B; 03-16-2015 at 05:59 PM.

  9. #59
    Senior Member PaulStoffregen's Avatar
    Join Date
    Nov 2012
    Posts
    20,546
    Just a quick update... I've been working on this SPI flash file allocation stuff over the last few days.

    I'm working on a simple library that provides a syntax similar to the SD library, but is highly optimized for low latency and minimal overhead. I should have it to a sharable state in the next day or two.

    The library has 3 parts.

    1: Raw SPI Flash access, with busy suspend, SPI transactions, 24 vs 32 bit address, etc
    2: File create & open & directory list functions
    3: File access functions

    The file access stuff is just inline functions that call the actual raw flash functions. A "file" object has only 3 integers: address of the file, length of the file, and current read/write position. Inline functions allow access to these, so if you want to build highly optimized SPIFIFO-based code that interleaves audio work with the SPI transfers, you can. Or you can call the library functions, which are designed around reading a block as fast as possible (and minimized SPI transaction time).

    The file create and open functions access a data structure that holds the locations and names of all the files. When you "create" a file, it just adds to the table and allocates space after the last allocated file. The file size has to be given at create time, and can never be changed. Files can't be deleted or renamed.

    I've been putting some work into optimizing the "open" function, to very quickly locate your file. There's a hash table of 16 bit numbers for each filename, so when searching for a particular filename, almost all can be ignored by just comparing 16 bits.

    All this "file" stuff may sound like quite a bit of overhead. It does add some code. Ultimately, once a file is opened, it's just a matter of an object with the address, length, and seek position... the same is if you'd hard-coded these.

  10. #60
    Senior Member PaulStoffregen's Avatar
    Join Date
    Nov 2012
    Posts
    20,546
    Here's a first version of the code. It's still pretty rough around a few edges. It's not yet using the SPI FIFO, but I'm planning to do that soon...

    https://github.com/PaulStoffregen/SerialFlash

  11. #61
    Senior Member+ Frank B's Avatar
    Join Date
    Apr 2014
    Location
    Germany NRW
    Posts
    5,679
    Wow great. I'll update my code then to use it.

  12. #62
    Senior Member PaulStoffregen's Avatar
    Join Date
    Nov 2012
    Posts
    20,546
    I added a couple more minor commits to the library. The main one is always aligning files to page boundaries. The library supports suspending in-progress write or erase operations, so they don't force reads to wait. In theory, this should allow one object to be recording audio and other to play. But it does require allocating files so reading from any file will not hit the same page as a write operation in progress on another file, which is the motivation for this change.

    Soon I'm going to add FIFO optimization.

    The other part that's not implemented is sector-based erase, and using it to erase individual files. So far, I don't know how to detect the uniform sector size. This might need to be a lookup table for known chips?

  13. #63
    Senior Member
    Join Date
    Feb 2013
    Posts
    563
    oh wow.

    Quote Originally Posted by PaulStoffregen View Post
    All this "file" stuff may sound like quite a bit of overhead. It does add some code. Ultimately, once a file is opened, it's just a matter of an object with the address, length, and seek position... the same is if you'd hard-coded these.
    it does (to my naive ears) ... so i assume this only applies in cases when someone wanted to open a file/wavetable/whatever by giving the file name? (rather than a/the address)?


    Quote Originally Posted by PaulStoffregen View Post
    Soon I'm going to add FIFO optimization.
    Paul, while you're at it, will you get a chance to look into the native/non-native CS issues reported here?

  14. #64
    Senior Member+ Frank B's Avatar
    Join Date
    Apr 2014
    Location
    Germany NRW
    Posts
    5,679
    Maybe I would replace the crc with a hash function.
    CRC is good for detecting random bit errors, but for the purpose to compare texts a HASH function is better.

    http://en.wikipedia.org/wiki/Hash_function

    but that's not important. crc will work too...
    Last edited by Frank B; 03-24-2015 at 08:08 AM.

  15. #65
    Senior Member PaulStoffregen's Avatar
    Join Date
    Nov 2012
    Posts
    20,546
    I'm happy to switch to a better hash algorithm. Do you have any specific ones in mind?

  16. #66
    Senior Member+ Frank B's Avatar
    Join Date
    Apr 2014
    Location
    Germany NRW
    Posts
    5,679
    Quote Originally Posted by PaulStoffregen View Post
    I'm happy to switch to a better hash algorithm. Do you have any specific ones in mind?
    The FNV-1 hash is very common - and, as a nice sideeffect - its a bit faster than CRC.

    Source:
    isthe.com/chongo/tech/comp/fnv/
    (Can be folded to 16 BIT)

    Ariticle on Wikipedia about FNV:
    http://en.wikipedia.org/wiki/Fowler%..._hash_function

    But of course, there are many other good hashfunctions.

  17. #67
    Senior Member PaulStoffregen's Avatar
    Join Date
    Nov 2012
    Posts
    20,546
    Quote Originally Posted by mxxx View Post
    so i assume this only applies in cases when someone wanted to open a file/wavetable/whatever by giving the file name? (rather than a/the address)?
    In this scheme, you always open files by their name. Yes, that involves overhead to read data structures stored in the flash memory. The idea is you normally only do this once at startup. But if you do it at runtime, a hash table is used speed the process as much as possible.

    Once you have a SerialFlashFile object, which uses only 12 bytes of RAM, you can access the file without extra overhead. You can read the file as many times as you like. Seeking anywhere within the file doesn't require any extra overhead.

    If there's a strong need to open a file by a known flash address, another way to initialize a SerialFlashFile object could be added. Or you could call SerialFlash.read() to directly read anywhere on the chip, instead of within a file. But I really would like to discourage placing known flash addresses into #define lines within sketches. While that is more efficient, it only optimizes open files which can be done at startup. The downside is it leads to not-very-portable code. That's more maintenance for you, and an extra step for beginners, and much less easily shared code for examples and helping others online.

  18. #68
    Senior Member
    Join Date
    Feb 2013
    Posts
    563
    ah, i see.

    Quote Originally Posted by PaulStoffregen View Post
    If there's a strong need to open a file by a known flash address, another way to initialize a SerialFlashFile object could be added. Or you could call SerialFlash.read() to directly read anywhere on the chip, instead of within a file. But I really would like to discourage placing known flash addresses into #define lines within sketches.
    i don't know. but i'm hoping the audio libraries will preserve or include the option to read/play/seek from known flash addresses? i guess i was mainly thinking in terms of the existing (ie Frank's) flash/wav library, which is easy to use not least because it doesn't involve any of the complexity that comes with SD. one just has to retrieve the data-addresses at start-up. with play_sd_wav, for instance, currently programmes typically have to read in all the filenames at start-up and store them in some array, then retrieve the name, open the file, etc. it's not a big deal, perhaps, but the filenames usually serve no purpose and having them can trip up people resp. the RAM just as well (in as much as filenames encourage usage of String, say).

  19. #69
    Senior Member PaulStoffregen's Avatar
    Join Date
    Nov 2012
    Posts
    20,546
    Quote Originally Posted by Frank B View Post
    The FNV-1 hash is very common - and, as a nice sideeffect - its a bit faster than CRC.
    Ok, I've switched to FNV-1

    https://github.com/PaulStoffregen/Se...6e6abb234d0133

  20. #70
    Senior Member PaulStoffregen's Avatar
    Join Date
    Nov 2012
    Posts
    20,546
    Quote Originally Posted by mxxx View Post
    i guess i was mainly thinking in terms of the existing (ie Frank's) flash/wav library, which is easy to use not least because it doesn't involve any of the complexity that comes with SD.
    This approach preserves the speed and low latency of SPI Flash for reading data, while adding some of the convenience and usability of conventional filesystems with file names.

    It also adds the ability to suspend an in-progress write or erase, so those won't block audio objects needing to read other files.

  21. #71
    Senior Member
    Join Date
    Feb 2013
    Posts
    563
    Quote Originally Posted by PaulStoffregen View Post
    This approach preserves the speed and low latency of SPI Flash for reading data, while adding some of the convenience and usability of conventional filesystems with file names.
    i'm not complaining ... but can't there be both? what I don't understand is what's convenient about filenames. they are needed for displays, etc. -- granted. other than that, I'd say they're mainly making things *more* difficult (why use names if i simply could use an integer?) and/or less efficient (well, who knows ... but some people (mainly zachtos) keep on inquiring about the open "file-by-index" thing with play_sd_wav, as you know).

  22. #72
    Senior Member+ Frank B's Avatar
    Join Date
    Apr 2014
    Location
    Germany NRW
    Posts
    5,679
    Quote Originally Posted by mxxx View Post
    i'm not complaining ... but can't there be both? what I don't understand is what's convenient about filenames. they are needed for displays, etc. -- granted. other than that, I'd say they're mainly making things *more* difficult (why use names if i simply could use an integer?) and/or less efficient (well, who knows ... but some people (mainly zachtos) keep on inquiring about the open "file-by-index" thing with play_sd_wav, as you know).
    Perhaps you need a function that translates a filename to address ? (to cache it)

    While I understand the need for low latency, i think we should think a bit about the relations:

    I hav'nt measured the latency to open a file of Pauls lib, but i think it's much below 1 ms. In addition, we can't get reliable times below 3ms because of the auidiobuffering.
    Sound needs ~3 millisecond for 1 meter distance. So, for example for a guitar in 30-40cm distance it's 1ms - without any electronic.
    If a guitarplayer uses loudspeakers in - lets say 3 meters distance - the latency is already 9ms MINIMUM (add delays for effects and other electronics).
    In a big classic orchestra, distances between the musicians are easyly 20 meters or more. This makes ~58ms.

    I don't think that anyone can hear a latency below, lets say 10ms. Its as with the eyes - in a cinema the pictures are changing with only 25Hz (or is it 50?) because this is sufficiant.
    Remember, 1 ms is 1/1000 of a second!
    Last edited by Frank B; 03-24-2015 at 06:33 PM.

  23. #73
    Senior Member PaulStoffregen's Avatar
    Join Date
    Nov 2012
    Posts
    20,546
    Quote Originally Posted by Frank B View Post
    Perhaps you need a function that translates a filename to address ? (to cache it)
    Yes. To cache the info, just keep a copy of the SerialFlashFile object. To start back from the beginning, just use seek(0).

    A wavetable object using SerialFlash should certainly do this. Maybe sound samples should too?

  24. #74
    Senior Member+ Frank B's Avatar
    Join Date
    Apr 2014
    Location
    Germany NRW
    Posts
    5,679
    sure.. perhaps next weekend.

  25. #75
    Senior Member
    Join Date
    Feb 2013
    Posts
    563
    Quote Originally Posted by Frank B View Post
    Perhaps you need a function that translates a filename to address ? (to cache it)
    oh, i'm fine all in all. but what seems odd to me is making simple things complex. like translating names to addresses when more often than not, there's no need for names. sometimes, i can see there might be a need to translate an address to a filename - for user-interface purposes -, but not the other way round. as i said, i don't think it's a big deal, but for the sake of audio performance and usage, i guess i personally would have preferred if SD wav et al had become more like the spi flash wav library, not v.v.

    While I understand the need for low latency, i think we should think a bit about the relations

    I hav'nt measured the latency to open a file of Pauls lib, but i think it's much below 1 ms. In addition, we can't get reliable times below 3ms because of the auidiobuffering.
    i don't know. it might be that's it's negligible. it might not. i'm not so much worried about latency, anyways. that said, re the cinema analogy i wouldn't agree entirely. it's a question of what you do. when trying to be in sync with other things, it does make a difference. also, the (total) latency - physical event to sound - is lower with SPI flash vs SD (~3.5 ms vs ~8.5ms); i can't tell why that is but it makes spi flash more suitable for things where timing needs to be tight.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •