Author Topic: Mysterious USB Stick Sorting Algorithm  (Read 1798 times)

0 Members and 1 Guest are viewing this topic.

Offline IDEngineerTopic starter

  • Super Contributor
  • ***
  • Posts: 1950
  • Country: us
Mysterious USB Stick Sorting Algorithm
« on: December 15, 2021, 05:01:17 pm »
Years ago, my wife got tired of constantly straightening the framed photos on the living room wall.

"You're an Engineer, fix this!"

So I plumbed in dedicated outlets and hung a pair of flat screen TV's. About once a year, generally near the holiday season when we have folks coming over, I add selected photos from the last year to two USB sticks. The screens rotate the image about every 10 seconds so there's a nice running sequence of stills, about 2000+ photos per screen. It's very popular; people watch the screens for scenes in which they, or people they know, appear and relive the memories.

I'm doing my annual update now, and have rediscovered a strange behavior: The screens display the photos as they were last sorted in Windows Explorer. No, I'm not making that up.

Here's the sequence:

1) I update the photos in the two directories I maintain for this purpose (one for each screen).

2) I delete all existing photos from the USB sticks, which are formatted in FAT32 because that's what the screens require.

3) I copy each directory into its USB stick. There's nothing else on the sticks (to avoid confusing the screens), just the root directory full of JPG's. No thumbs.db, no other directories, nothing.

Here's where it gets interesting. If I view a USB stick using Windows Explorer, the last sorting algorithm controls the order that the flat screen TV's display them. If I sort by name, and then unplug the USB stick and plug it into a TV, the images will be displayed in name order. If I sort by date, they will be displayed by date. If I sort by size, they are displayed in size order.

How is that possible? The USB stick does not appear to have any files on it that would "record" the last sorting choice. Each TV is a standalone device, hanging on the wall, whose only connection to the outside world is its power cord. I'm not 100% familiar with how FAT32 manages disk space but I find it unlikely that it would record an application-specific, OS-specific, sorting choice. And even less likely that a standalone device which does not run the same OS would recognize and respect such a choice.

Any ideas on this?!?
« Last Edit: December 15, 2021, 05:04:21 pm by IDEngineer »
 

Offline tom66

  • Super Contributor
  • ***
  • Posts: 7334
  • Country: gb
  • Electronics Hobbyist & FPGA/Embedded Systems EE
Re: Mysterious USB Stick Sorting Algorithm
« Reply #1 on: December 15, 2021, 05:17:49 pm »
Windows is fond of putting a hidden folder on USB storage volumes called "System Volume Information".  Within it is a file known as 'WPSettings.dat', which is undocumented.  However, if this file is used to store the sorting information and somehow, your TV can also read this file, it could explain the behaviour.

You can delete the SVI folder if you show hidden files on exFAT/FAT32.  Can't be deleted on NTFS. 

Who makes the screens?  Are they Android based or just a generic flatscreen TV OS?  Android has implemented a lot of the idiosyncrasies supported by exFAT and FAT32 into it, perhaps this is one of them!
 

Offline IDEngineerTopic starter

  • Super Contributor
  • ***
  • Posts: 1950
  • Country: us
Re: Mysterious USB Stick Sorting Algorithm
« Reply #2 on: December 15, 2021, 05:35:33 pm »
I have Explorer configured to display everything. System Volume Information is visible on some of my USB sticks, but not on those used for this application. As I said, I'm careful to keep these sticks totally empty except for the .JPG's.

The screens are very old plasma displays dating from ~2006-2007. They have a single USB port, no Ethernet interface, etc. Whatever code they're using cannot accommodate more than 2GB of data on the stick... the stick can have greater capacity but if it has more than 2GB of data the screen can only "see" a limited number of the photos and fails to display the rest. Feels like address space wrapping. (The limit seems based on total active memory, not on file count.) My point is these are old screens with very limited processing power. I seriously doubt they are running any form of formal OS and likely just have some sort of dedicated embedded firmware.
 

Offline CatalinaWOW

  • Super Contributor
  • ***
  • Posts: 5569
  • Country: us
Re: Mysterious USB Stick Sorting Algorithm
« Reply #3 on: December 15, 2021, 06:43:47 pm »
It sounds like Windows writes the files in the current sort order.  Since you are writing into a completely erased thumb there is no reason to expect them to be in a different order.  The TV just reads them back in sequence.

This could be an advantage if you used one of the other standard attributes (track number seems like an obvious choice) as a sequence number which would give you complete freedom in ordering (at the cost of a lot of tedium assigning track numbers).

I would also guess that your old TV assumes FAT32 with 32K sectors. 
 

Offline edavid

  • Super Contributor
  • ***
  • Posts: 3464
  • Country: us
Re: Mysterious USB Stick Sorting Algorithm
« Reply #4 on: December 15, 2021, 06:59:10 pm »
It sounds like Windows writes the files in the current sort order.  Since you are writing into a completely erased thumb there is no reason to expect them to be in a different order.  The TV just reads them back in sequence.

He is not rewriting the files after changing the sort order, but the TV display order still changes.

My guess is that Explorer is changing one of the time stamps, but I don't know why that would happen.

I would try to figure out what's happening with the FileActivityWatch utility:

https://www.nirsoft.net/utils/file_activity_watch.html
 

Offline sleemanj

  • Super Contributor
  • ***
  • Posts: 3051
  • Country: nz
  • Professional tightwad.
    • The electronics hobby components I sell.
Re: Mysterious USB Stick Sorting Algorithm
« Reply #5 on: December 15, 2021, 08:06:48 pm »
If it's not the SVI, then it can only be the FAT I think.

You could test this by getting your own FAT sorter and resorting with that to see if the "last Windows Explorer" sort is nuked.
~~~
EEVBlog Members - get yourself 10% discount off all my electronic components for sale just use the Buy Direct links and use Coupon Code "eevblog" during checkout.  Shipping from New Zealand, international orders welcome :-)
 

Offline Simon

  • Global Moderator
  • *****
  • Posts: 18118
  • Country: gb
  • Did that just blow up? No? might work after all !!
    • Simon's Electronics
Re: Mysterious USB Stick Sorting Algorithm
« Reply #6 on: December 15, 2021, 08:09:59 pm »
I have had a lot of fun with the opposite, where the player plays in the order they are stored. I volunteer with my local talking newspaper, we use players that take a memory stick. To simplify file transfers in the right order we came up with a procedure we could teach everyone.

Name all files with numbers of the same number of digits: Track01' track02.....
If you don't your name ordering will be 1, 10, 2, 20, 3, 30.....
list files by name.
Select all files.
Drag the files to the destination by the first file.
If you don't the files will start copying from the one you dragged, followed the those after it and then those remaining from the start will copy.

This all sounds simple enough but it took months of working out why things were going wrong. For a time I thought that windows would always copy the last file then the rest in order until I observed several people always use the las file that was usually the closest to the mouse after selection and drag it and so worked out that it was not the last file that was copied first but the one that is used as the "handle".
 

Offline Bicurico

  • Super Contributor
  • ***
  • Posts: 1816
  • Country: pt
    • VMA's Satellite Blog
Re: Mysterious USB Stick Sorting Algorithm
« Reply #7 on: December 15, 2021, 08:17:13 pm »
Every file has a last accessed time stamp.
The TV probably shows from oldest to newest time stamp, which does make sense.

Regards,
Vitor

Offline retiredfeline

  • Frequent Contributor
  • **
  • Posts: 572
  • Country: au
Re: Mysterious USB Stick Sorting Algorithm
« Reply #8 on: December 15, 2021, 08:21:22 pm »
A similar thing used to happen to me with MP3 players on USB sticks, they play in the order the files were written to the directory in the FAT filesystem. I used to use a program called fatsort to make sure the order was sorted.
 

Offline edavid

  • Super Contributor
  • ***
  • Posts: 3464
  • Country: us
Re: Mysterious USB Stick Sorting Algorithm
« Reply #9 on: December 15, 2021, 08:34:28 pm »
Every file has a last accessed time stamp.

That is not correct.  OP said he is using FAT32, which does not have an access timestamp.
 

Offline tom66

  • Super Contributor
  • ***
  • Posts: 7334
  • Country: gb
  • Electronics Hobbyist & FPGA/Embedded Systems EE
Re: Mysterious USB Stick Sorting Algorithm
« Reply #10 on: December 15, 2021, 08:56:50 pm »
Perhaps the files are having a thumbnail added by Windows, which is changing their last-modified date.

That said, I've never heard of Windows doing this.  Thumbnails are stored in thumbs.db.  A 3rd party piece of software on the machine could be doing this, perhaps?
 

Offline retiredfeline

  • Frequent Contributor
  • **
  • Posts: 572
  • Country: au
Re: Mysterious USB Stick Sorting Algorithm
« Reply #11 on: December 15, 2021, 09:10:22 pm »
The only explanation I can think of is that Windows Explorer rewrites the directory table to the current sort order so that when you view it again later, it's still in the same order. And the order in the table would be what a dumb player algorithm would use.
 

Offline Nominal Animal

  • Super Contributor
  • ***
  • Posts: 7192
  • Country: fi
    • My home page and email address
Re: Mysterious USB Stick Sorting Algorithm
« Reply #12 on: December 17, 2021, 03:25:32 am »
What I'd do, is take an exact image of the USB stick in Linux without mounting it at all (dd if=/dev/sdX bs=2097152 of=before), move the stick to the Windows machine and change the sort order and eject the stick, and then take another exact image of it in Linux without mounting it; and then compare the two images.
There will be some unrelated changes due to mounting (root directory timestamp and such), so there is a bit of noise in the raw data.
The images can also be loopback-mounted in Linux, so that one can compare the files on the images as well.
 

Offline eti

  • Super Contributor
  • ***
  • !
  • Posts: 1801
  • Country: gb
  • MOD: a.k.a Unlokia, glossywhite, iamwhoiam etc
Re: Mysterious USB Stick Sorting Algorithm
« Reply #13 on: December 17, 2021, 08:43:43 am »
Screens, screens, screens, it’s all people every look at. I’d be happy straightening the photos than doing all that melarkey.
 
The following users thanked this post: voltsandjolts

Offline Rick Law

  • Super Contributor
  • ***
  • Posts: 3490
  • Country: us
Re: Mysterious USB Stick Sorting Algorithm
« Reply #14 on: December 19, 2021, 12:09:19 am »
I have this problem with audio on my car's usb reader not playing it the order as displayed.

Then I recall one thing about the original FAT system.  Not verbatim, but as I recall:"When a file is deleted, the slot is left there with ~ as first character...  when a file is added, it go find the first empty slot...  DIR display the files in slot order skipping the deleted..."  So, native FAT "file order" is creation and/or modification date time, oldest=first.

Recalling that info, now when I move things around on my FAT32 audio usb stick, I reformat the USB stick and copy it back in the order I want the play to play.  This ensured the play order is same as native storage order and the old DOS/WinXP DIR display.

Sorting/accessing by latest vs oldest also has a worst problem at least for me.  Different Microsoft system (Win7 explorer, Win7 dos box, Win XP explorer, WinXP dos box...) may showing you different date/time for the same file.  The times you see by these method could differ by 2 seconds and or +1 hours.  That shows search by date/time really depends on what system you use and what program that systems use.

Win7 file explorer's date/time would use FILEDATE (stored somewhere hidden) where as, win7's dos box DIR use FILEINFO data in NTFS.  FAT data is converted at run time to FILEDATE or FILEINFO data.   WinXP file explorer and WinXP dos box use FILEINFO data.  Of course, DOS uses data in FAT.

When Win7 windows, Win7 dos box, WinXP windows, WinXP dos box, dos may all be showing different date/time for the same file, it shows how directory searching and sorting by date entirely depends on how your "reading system" wrote its search.

-----------------------------------------------------------------------------------------------------
Detail info on the different "display time" if you are interested, here is "diving deeper into that rabbit hole":

In Windows, one could be using _FindFirst and _FindNext (with their w or no w variant) which returns _FILEINFO.  When file is FAT, FAT data is converted to _FILEINFO data during run time.  DOS is FAT's time structure obtained directly from FAT.  Other systems like an audio or picture player... who knows.

As far as I know, there are two places to store file date/time, and three formats:
- FAT way is 16 bit 2 seconds resolution, no understanding of time zone and no understanding of daylight savings.
- _FILEINFO is 32 bit 1 second resolution Unix time.
- FILEDATE is 64 bit 100ns resolution in a hidden file.

The way microsoft implemented FILEDATE, in their words, they "want it to be reversible when a time occur twice."   A time occur twice on daylight savings time change and turn the clock back 1 hour.  I don't know what they mean by reversible.  Net result is, on Win7 (may be for later as well) where I tried to put in a "touch" function in a program, some unix time values cannot be used as FILEDATE during certain times.

You convert the unix time value into FILEDATE format, put it into FILEDATE say as last mod date, update the file's FILEDATE, read it back, convert it back to unix time, and the unix time value you read back may not be the unix time value you you started with.  The read back value will depend on the time value's DST/EST status (ie: is the date you are setting a DST date or not), the DST/EST of when you did the setting, and the DST/EST of when you did the reading.  Yeah, I am positive you don't always get back the same.  You can offset that value by 3600 (1hr), you may read the right value back immediately, but then when you read it back again after DST/EST changed, you will get back a different time_t value.  _tzset will not change that.  However, if you turn off "automatic daylight saving time adjustment" for your machine, that problem will go away.
« Last Edit: December 19, 2021, 01:02:28 am by Rick Law »
 

Offline SilverSolder

  • Super Contributor
  • ***
  • Posts: 6126
  • Country: 00
Re: Mysterious USB Stick Sorting Algorithm
« Reply #15 on: December 19, 2021, 02:15:44 am »

I use a free utility, "DriveSort", to fix this problem.  From the author:

"Recent operating systems sort the files before showing them to the user, either by name, by size or by whatever the user choose. However, it is not always the case in embedded OSes on small portable devices like MP3 players. On these devices the lack of resources (CPU, memory) can lead their developers to make it display or play the files in the order in which they are on the disk.

This order depends mostly of the order in which they were added to the disk, which is not convenient for the user. DriveSort can change this order to help such devices to play or view their files in the order you want, by putting them on the disk in a customizable order.

DriveSort sorts files and folders according to various options available in the popup menu next to the sort icon. The order can then be saved to disk either folder by folder, or for all sub-folders."

http://www.anerty.net/software/file/DriveSort/
 
The following users thanked this post: edavid


Share me

Digg  Facebook  SlashDot  Delicious  Technorati  Twitter  Google  Yahoo
Smf