FAT-32 Sorter - 对 FAT32 文件系统中的文件表进行排序的实用程序
我如何编写了一个实用程序来对 FAT-32 存储设备中的文件进行排序，并修复受不当排序顺序影响的产品，例如各种音乐播放器。
目录
引言
在本文中，我将介绍我编写的一个小型实用程序，用于对 FAT32 文件系统的文件表进行排序。该实用程序解决了大多数基于 FAT32 的音乐播放器存在的问题——歌曲排序不确定。这个问题出现在我的车载音响系统和亚马逊的 Kindle 上。
寻找和解决这个问题是一次愉快的旅程，涉及到对闪存驱动器文件系统的底层进行研究和编程。我已经提供了理解本文所需的大部分背景知识，但你需要具备一些 C++ 编程的先验知识才能理解代码。
你可以在我的 Github 仓库中找到该实用程序的源代码 - https://github.com/Udinic/FAT32-Sorter。
一位陌生人
这就是这一切的开始
不久前，我为我的汽车购买了一个音响系统 - Pioneer DEH-P4050UB。这款产品的主要优点是能够读取 USB 闪存驱动器中的音乐。到目前为止都很好，但我喜欢随机听音乐，并且我注意到了一些令人不安的事情——在随机模式下，如果歌曲结束，那么下一首将被随机选中。然而，如果我自己切换到下一首歌（使用快进按钮），那么下一首歌将是当前歌曲的顺序下一首！
思考了一会儿，我想起了有一个“下一个目录”按钮，所以我可以随时切换到下一个专辑。这样，我就可以放一个非常短的音频文件，它将按字母顺序排在专辑的第一个（即*11111udi.mp3*），在播放完这个文件（很短的时间）后，下一首歌将被随机选中！这样我就可以一键获得一首随机歌曲！
不幸的是，先锋的诸神有不同的计划。我注意到，不知何故，新的短音频文件并不是目录中播放的第一个。之后，我还注意到我的许多专辑中的歌曲不是按字母顺序播放的，这表明存在某种神秘的顺序需要被揭示。
FAT32 简要说明
在我们开始动手之前，让我们先了解一下我的 USB 格式化到的文件系统（音响系统要求的）。学习 FAT32 的所有方面可能需要很长时间。我在此提供一些此文件系统的关键特性，以帮助您理解我的问题的解决方案。
结构
不深入细节，文件系统以引导扇区开始，其中包含文件系统的所有参数值（例如扇区大小，稍后解释）。FAT32 文件系统的布局在此图所示
摘自文章“Paul's 8051's code library: Understanding FAT32 Filesystems”。
让我们讨论重要的事情
- 卷 ID (引导扇区) - 包含有关当前分区的关键信息，例如簇大小和文件系统中的 FAT 表大小。
- 簇 - 为了方便地导航文件系统，所有位都被划分为更大的数据组，称为“扇区”和“簇”。扇区是最小的组，其大小是固定的，并在引导扇区中说明（目前是 512 字节）。由于扇区很大，但不够大——我们使用簇，簇不过是扇区的集合。每个簇的官方扇区数也在引导扇区中定义（通常，簇 = 8 个扇区）。从现在开始——我们将只把簇作为我们最小的数据单位。
- FAT 表 - 一个簇可能不足以容纳文件数据。单个簇可以容纳 4096KB 数据（8 个扇区 * 每个 512 字节）。因此，为了将数据分散在不同的簇中，我们需要一种方法来跟踪它们。这就是我们拥有 FAT 表的原因！给定某个簇号，我们可以转到其中一个 FAT 表并计算链中的下一个簇，然后是下一个，再下一个……直到达到某个停止该链的标志。有两个表互相备份，以防一个表因某种原因损坏。
目录条目
文件系统中的每个文件和文件夹都表示在一个或多个称为“目录条目”的条目中。目录条目保存有关文件/文件夹的所有信息，如下一图所示
- “起始簇号”（DIR_FstClusLO 和 DIR_FstClustHI）是我们可以找到文件/文件夹本身的数据的簇。
- 文件数据 可以从文本到二进制文件、图像甚至可执行文件不等。
- 文件夹数据 包含其所有文件和子文件夹的列表。该列表中的每个条目都是一个“目录条目”，它指向自己的数据簇。
“DIR_Name”保存文件/文件夹的名称。你可能会问自己：“‘文件名’字段只有 11 个字节？！但我可以在 FAT32 中使用更长的文件名！”嗯，你是对的。有一个小“技巧”可以使用其他类型的条目来写入更长文件名，称为“长文件名条目”（LFN 条目）。
任何文件名超过 11 个字节的文件，或需要 UNICODE 的其他语言的文件名，都使用 1 个或多个 LFN 条目。每个条目都有几个字节来存储文件名。组合所有 LFN 条目，我们得到长文件名！
在所有文件的 LFN 条目旁边，有一个短目录条目，其中包含有关文件的关键信息，并有助于支持不熟悉 LFN 条目的旧操作系统。所以实际上，一个长文件名的文件使用了多个目录条目。它使用尽可能多的 LFN 条目，以及一个短目录条目以实现向后兼容。
在下一图中，我们可以看到两个文件的条目：“*udini01.txt*”和“long name for a file.txt”。第一个文件有短文件名，因此只使用一个短目录条目。但是，第二个文件需要更多条目，因此它使用了 2 个 LFN 条目（标记为 #1 和 #2），之后——一个向后兼容的短条目，带有一个截断的文件名。
此屏幕截图来自程序“DiskExplorer for FAT”，该程序可以让你很好地了解你的文件系统，查看所有内容是如何存储的。你可以 在这里 下载它。
仔细看，你甚至可以看到一些文件的其他属性。例如，这些文件的*数据*分别存储在“*udini.txt*”和“long name for a file.txt”的簇号 3 和 4 中。
寻找问题
在获得一些背景知识后，让我们回到我们的问题：我的歌曲在我车载音响中播放时，以某种神秘的方式排序。在玩了一些读取目录的操作系统命令后，我发现 `FindFirstFile` 和 `FindNextFile` 函数返回的文件顺序与我的车载音响相同。那么是什么决定了它们的顺序呢？
关于这些函数排序文件的方式，MSDN 说：“搜索返回文件的顺序，例如字母顺序，不保证，并且取决于文件系统。”
这意味着——我需要找到导致这种顺序的**文件系统**的确切原因，并在**设备本身**中进行排序。另一种选择是更改我的车载音响的固件，在它读取的每个目录中对文件进行排序，这只是大量的工作。
让我们看一些文件，以及它们在 Windows 资源管理器和 FAT32 文件系统中的排序方式。
Windows 资源管理器中的文件（已排序）
文件系统中的文件表（未排序）
使用优秀的“DiskExplorer for FAT”，我可以看到文件系统内文件表的排序顺序。
让我们专注于数字的顺序（圆圈中标记）。我们可以看到文件系统中的顺序与 Windows 资源管理器窗口中的顺序不同。我编写了一个使用 `FindFirstFile`/`FindNextFile` 函数（如上所示）的小型 C 程序，它给了我这个顺序
- Riverside - **04** - left out
- Riverside - **02** - driven to destruction
- Riverside - **05** - hybrid times
- Riverside - **03** - egoist hedonist
- Riverside - **01** - hyperactive.mp3
这与文件表中的顺序完全相同，得出结论：函数以它们在文件表中存储的顺序返回文件！这种顺序是由将文件复制到设备上的操作系统引起的，而操作系统很难控制。如果我尝试一次复制一个文件，那么文件表将以相同的方式排序。当然，这对于包含几百首歌曲的 USB 闪存驱动器来说，几乎不是一个解决方案……我们该怎么办？！让我们看看……
排序问题
为了让音乐以正确的顺序播放（按字母顺序，而不是您复制的顺序！），我不得不编写一个实用程序来按字母顺序对目录条目进行排序。
条目实体
读取文件系统时有很多信息。每个文件或文件夹可以有超过 10 个目录条目（感谢 LFN 支持），我们需要妥善组织数据。以下是我用于维护数据的类的简化类图。
- CEntry - 这是系统中所有条目类型的抽象父类。文件系统中的每个文件或文件夹都存储在其子类之一中。`m_data` 数据成员保存了短条目的 32 字节（如果存在 LFN 条目，则不是 LFN 条目）。`m_chainedLFNEntry` 是一个动态数组，包含该文件/文件夹的所有 LFN 条目。`getName()` 返回文件/文件夹的名称。如果存在 LFN 条目，则文件名字节从 `m_chainedLFNEntries` 中的所有 LFN 条目收集，并组合成一个字符串，即长文件名本身。
- CFileEntry - 表示系统中的单个文件。
- CSpecialEntry - 这是一个特殊条目，表示一些非文件或文件夹的条目。这些条目是卷标签条目（包含设备的标签名称）。其他特殊条目是“.”和“..”条目，它们只是指向当前文件夹和当前文件夹父文件夹的“指针”。
- CFolderEntry - 此条目表示一个文件夹，该文件夹在其内部（在 `m_files` 中）包含所有文件，在其内部（在 `m_folders` 中）包含所有子文件夹。它还具有排序功能，这是该实用程序的主要功能。
CFileSystem
此类是文件系统的高级 API。它使用 `CVolumeAccess` 类（稍后将描述）进行低级设备访问。它提供了更简化的 API 来执行文件系统的主要功能。该类保存 `m_rootDir` 数据成员，它是根实体（`CRootEntry`），包含表示整个文件系统的文件和文件夹树。`initFDT()` 函数负责填充数据。`sort()` 函数用于对文件系统中的所有文件和文件夹进行排序。
CVolumeAccess
所有低级文件系统访问都由这个实用类完成。
此类是单例。初始化时，它会向设备发送命令以锁定和卸载它（需要低级访问时卸载设备，从 Windows Vista 开始是必需的）。在初始化阶段，它还将 FAT 表加载到内存中（`m_FAT1Data` / `m_FAT2Data` 数据成员），以便我们稍后可以使用它来查找链接在一起的所有簇。在下一个代码片段中，我们看到如何从随机簇链读取数据。
DWORD dwNextClusterNum = aStartClusterNum;
DWORD dwNumClustersRead = 0;
// As long we didn't reach the end of the chain
while (dwNextClusterNum != FAT_END_CHAIN)
{
// Reads from the device the whole cluster, and puts it in the next free
// position in the buffer
if (!readBytesFromDeviceCluster(aoChainedClustersData+(
dwNumClustersRead*m_clusterSizeBytes),
m_clusterSizeBytes,
dwNextClusterNum))
{
return false;
}
dwNextClusterNum = m_FAT1Data[dwNextClusterNum];
++dwNumClustersRead;
}
上述代码取自 `readChainedClusters()` 函数。`aoChainedClustersData` 缓冲区用簇链中的数据填充。
链中的簇不一定是连续的（实际上，很可能不是）。例如，簇链可以是簇序列：4、5、8、23、87、432。`aStartClusterNum` 保存链中第一个簇的编号。该数字在文件/文件夹的目录条目中指定（参见上面的“FAT32 字节目录条目结构”图）。
`dwNextClusterNum` 变量用于存储下一个数字。如果我们把当前簇号标记为 X，那么下一个簇号就是位于 FAT 表 X 索引处的数字。这解释了行 `dwNextClusterNum = m_FAT1Data[dwNextClusterNum];`
第一个 FAT 表 `m_FAT1Data` 是任意选择 `m_FAT2Data` 的，因为两个表都相同。这个循环一直进行，直到下一个簇达到 `FAT_END_CHAIN` 常量，该常量标志着链的结束。
使用 `readChainedClusters()`，我们可以获取所有文件夹的文件/子文件夹列表，从而轻松地遍历文件系统，将数据填充到适当的 `CEntry` 对象中。根文件夹将保存在 `CFileSystem` 对象中，并且其所有子文件夹将通过 `sort()` 函数递归排序。
使用该实用程序
它能做什么？
我编写的该实用程序提供了以下功能：
- 转储文件表（备份） - 将文件表保存到文件中，以便将来出现错误时可以恢复。备份文件名将始终是“*dirs.dat*”。
- 加载文件表（恢复） - 从先前保存的文件加载文件表。数据将仅从名为“dirs.dat”的文件加载，该文件位于实用程序所在的目录中。
- 导出文件夹列表 - 将设备上所有文件和文件夹的列表存储在一个名为“*Files List.txt*”的文件中，这些文件和文件夹的顺序与文件表中的顺序相同。数据将以树形格式打印，每个目录的格式为：[序列号|名称]。序列号只是设备中所有文件夹的计数器。这对我很有用，因为我的车载音响只显示文件夹的序列号。有了这样的列表，我就可以轻松搜索某个特定的专辑。我希望其他人也能出于他们的目的找到它。
这是此类列表的一个示例
排序 FAT 表 - 这是主要功能。此命令对文件表进行排序，并将排序后的表刷新回设备。注意：此操作会自动保存备份文件，因此无需在此之前使用备份。如果排序后的表有问题，您可以通过将创建的备份文件重命名为“*dirs.dat*”并使用菜单中的“恢复”选项来恢复。
如何开始？
为了对文件表进行排序，您需要选择设备挂载到的驱动器。使用主菜单中的选项 1，然后输入正确的驱动器号。
请注意，设备需要连接并挂载到此驱动器。它也需要格式化为 FAT32 文件系统。否则，对设备的任何操作都将失败。
之后，您可以使用排序选项（菜单中的第 5 项），这将导致实用程序加载文件表，对其进行排序，然后将其刷新回设备。
注意：“???”只是此 DOS 窗口无法显示的希伯来字符中的一些文件夹，但排序过程不会受到影响或损害。
对于 16GB USB 驱动器，此过程大约需要 1-2 分钟。它相当安全，因为您始终可以从备份文件中恢复表。要查看更改，您可以在排序过程之前和之后打印 FilesList（别忘了每次操作后重命名它，否则它会被覆盖！）。
有了这个实用程序，您可以轻松地按应有的正确顺序排列您的歌曲！此解决方案也适用于亚马逊的 Kindle（也以加载时的顺序播放所有歌曲，如 此处 描述）——只需使用此实用程序对 Kindle 的文件表（即 FAT32）进行排序，即可！所有歌曲都按字母顺序排列。
资源
- GitHub 上的 FAT-32 Sorter.
- 微软的 FAT 文件系统规范.
- 来自 http://www.easeus.com 的数据恢复电子书。