[braindeath]

It doesn’t require much memory to shuffle, essentially just an integer permutation generator and possibly an index of block pointers. You could store the latter in the NV storage. This assumes no storable “playlist” at all. If you have playlists then shuffle is trivial.

[av500]

true, but as said below, I was a bit green at that time.

what we did have was that we would remember a song not by its full path which could be like 256 bytes long, but by only 8 bytes, so when we read in an playlist, we would convert each file path into these 8 bytes and use them to retrieve the tracks later. that made parsing playlists "slow". Rockbox did access the playlist as a file, so they would only resolve the path when the next song was needed, but then they had the time and leasure to write a Posix like file API whereas we moved in a hurry and used a much more primitive block based approach. this was also born out of the fact that our design initially had only 128k of RAM and a larger SDRAM for buffering while the drive is off was only added later...

[microcolonel]

Probably today I would use a bloom filter to avoid duplicate plays. You could even produce a transition matrix between albums with similar code and memory complexity.