Just recently booted up my NES PowerPak for the first time in months and it reminded me of the annoying problem it had. The files do not sort alphabetically which can make searching for a game quite a chore. Finding a windows program to do this was fairly easy but I do not use Windows, does anybody know of a GNU/Linux program? Thank you very much.
Google linux fat sort brought up this Fedora discussion as the first result, but apparently it's not that hot, and foldersort should work in Wine.
danntor wrote:
Just recently booted up my NES PowerPak for the first time in months and it reminded me of the annoying problem it had. The files do not sort alphabetically which can make searching for a game quite a chore.
Believe me, it would be much more annoying if the 6502 was in charge of alphabetically sorting thousands of files. It would probably take more time for the menu to load than it currently takes for you to locate the game you want.
Also, if you use some sort of folder structure (a folder for each letter, or genre, or company, whatever) locating games isn't so hard. Now, if you just pasted an entire "complete ROM set" full of files you will never touch (alternate versions, overdumps, different regions, languages you don't understand, hacks, etc...) into the root folder, then yeah, it will be hard.
tepples wrote:
Google linux fat sort brought up this Fedora discussion as the first result, but apparently it's not that hot, and foldersort should work in Wine.
Under any *n*x, the following bash shell script one-liner will achieve the same — assuming no file names with @ in them.
Code:
j=`mktemp -d XXXXXXXX.tmp`; mv * $j; cd $j; for i in `ls | sort | tr ' ' @`; do mv -vi "`echo $i | tr @ ' '`" ..; done; cd ..; rmdir $j
lidnariq, you are a champion. That is getting added to the list of useful commands I have found or made over the years.
@tepples
I was going to do that as last resort. Thanks for the help though
@tepples
I was going to do that as last resort. Thanks for the help though
Is sorting really that slow? You pre-load a list of all filenames into memory, then assign each file a sequence number, and build the pointer table so you can look up filenames given a sequence number.
Then you sort the sequence numbers, by comparing their associated strings. You end up with a table of numbers in some random-looking order, but their associated strings are sorted.
For the sorting, you use Iterative Merge Sort. It takes exactly N*lg2(N) string comparisons, and because you are using numbers to represent the arrays, you aren't needlessly copying a bunch of strings. And it doesn't require any stack space, just a second copy of the integer array.
Lets's say you have string comparison routine that takes exactly 600 CPU cycles per iteration (worst case). If you had 1024 files, that would work out to about 3.5 seconds of sorting.
Then you sort the sequence numbers, by comparing their associated strings. You end up with a table of numbers in some random-looking order, but their associated strings are sorted.
For the sorting, you use Iterative Merge Sort. It takes exactly N*lg2(N) string comparisons, and because you are using numbers to represent the arrays, you aren't needlessly copying a bunch of strings. And it doesn't require any stack space, just a second copy of the integer array.
Lets's say you have string comparison routine that takes exactly 600 CPU cycles per iteration (worst case). If you had 1024 files, that would work out to about 3.5 seconds of sorting.
3.5 seconds of sorting is still slow as fsck. Imagine having to wait 3.5 seconds every time you go back up a directory. I'd love to be proven wrong with a sort demo ROM.
It's the way I did it on the GBA, and the sorting is instantaneous on its mighty 16MHZ ARM processor.
Edit: more calculations...
When reading all files in a directory, If filenames are 32 characters long on average, that's about 128 bytes per filename, and reads 256K of data to read 1024 filenames. That probably dwarfs the sorting time.
Oh well, just build an index (array of Directory Entry numbers in sorted order), and test if the directory's size and contents/hash of the last cluster matches to check if it's dirty.
Edit: more calculations...
When reading all files in a directory, If filenames are 32 characters long on average, that's about 128 bytes per filename, and reads 256K of data to read 1024 filenames. That probably dwarfs the sorting time.
Oh well, just build an index (array of Directory Entry numbers in sorted order), and test if the directory's size and contents/hash of the last cluster matches to check if it's dirty.
I'd recommend heapsort instead because heapsort takes O(n) for the first filename on average and then O(k log n) for the next k filenames, both of which are less than O(n log n) to sort the whole thing. After the names are displayed, the rest of the sorting will happen in the background while the user is scrolling down. I call this "streaming heapsort".
I ought to implement some sorting algorithms in Python and then in 6502 asm to demonstrate Shell sort, merge sort, heapsort, and streaming heapsort. The last time I touched sorting on the NES, it was Who's Cuter, a demo of Shell sort and PackBits tile compression. But does anyone following this topic speak French as a first language?
I ought to implement some sorting algorithms in Python and then in 6502 asm to demonstrate Shell sort, merge sort, heapsort, and streaming heapsort. The last time I touched sorting on the NES, it was Who's Cuter, a demo of Shell sort and PackBits tile compression. But does anyone following this topic speak French as a first language?
tepples wrote:
I ought to implement some sorting algorithms in Python and then in 6502 asm to demonstrate Shell sort, merge sort, heapsort, and streaming heapsort.
I'm curious now, is the Power Pak's interface just a simple firmware that can be updated easily? I was thinking of possibly making a more "pretty" interface kinda like Dreamcast's, or something.
At the same time, implementing sorting on the Power Pak wouldn't be too terrible, the Power Pak is capable of writing to the memory card too, right? Why not just sort the roms once, and record the file order in a cache-file? I can't imagine your rom folders changing too drastically, too often. Even if it does, you could easily update the cache-file to add and remove files, without needing to regenerate the whole thing
Drag wrote:
tepples wrote:
I ought to implement some sorting algorithms in Python and then in 6502 asm to demonstrate Shell sort, merge sort, heapsort, and streaming heapsort.
I'm curious now, is the Power Pak's interface just a simple firmware that can be updated easily? I was thinking of possibly making a more "pretty" interface kinda like Dreamcast's, or something.
Code for menus and such is stored in the CF card ("POWERPAK" dir together with NES mappers). So yeah they can be updated easily.
Quote:
At the same time, implementing sorting on the Power Pak wouldn't be too terrible, the Power Pak is capable of writing to the memory card too, right? Why not just sort the roms once, and record the file order in a cache-file? I can't imagine your rom folders changing too drastically, too often. Even if it does, you could easily update the cache-file to add and remove files, without needing to regenerate the whole thing
Yeah I thought about caching too, should work for most purposes. PowerPak currently doesn't know how to create new files though, so an empty cache file needs to be added to the CF.
It'd probably be feasible, but no technical details about the modules have been released, so it would require a fair amount of reverse engineering. I'm not sure if it's worth it just to get sorting.
Anyway if you/others want to give a better menu a go, I can probably help with the RE part, I have most of it figured out already anyways.
The results of "merdesort" are in. I just implemented three sort algorithms in Python, sorting 500 integers that have been shuffled.
Merge sort completed after 3841 to 3886 compares.
Shell sort completed in 5555 to 5790 compares.
Heapsort finished fix heap after 900 to 943 compares.
Heapsort returned 20 results after 1218 to 1263 compares.
Heapsort completed after 7385 to 7450 compares.
Conclusion: Merge sort finishes fastest, but heapsort returns the first page of results fastest. I can provide source code if you want to reproduce results.
Merge sort completed after 3841 to 3886 compares.
Shell sort completed in 5555 to 5790 compares.
Heapsort finished fix heap after 900 to 943 compares.
Heapsort returned 20 results after 1218 to 1263 compares.
Heapsort completed after 7385 to 7450 compares.
Conclusion: Merge sort finishes fastest, but heapsort returns the first page of results fastest. I can provide source code if you want to reproduce results.