看了 Windows 的 DLL 保存字符串资源代码，再次惊掉我下巴。
3dwelcome · 2021-05-29 02:26:48 +08:00 · 3684 次点击这是一个创建于 1266 天前的主题，其中的信息可能已经有所发展或是发生改变。
以 Visual Studio 2017 举例，主界面上不同语言翻译文件，是保存在 IDE{LANGID}\msenvmui.dll 下面，可以用资源编辑器打开，截图这样：
有 ID 和对应的字符串，我这时候猜测，资源里就是一个表格文本，读取和翻译应该很容易。
然后花一小时读了源代码，最后发现完全不是自己想的这样。
在 msenvmui.dll 里，一共有 82 个有效字符串，中间穿插了一百多个空字符串。
[正常 string] [空 string] [空 string] [正常 string], 就是这种文件布局，空 string 都是实际占空间的(两个字节)。
为什么空呢，因为微软对 ID 字符串用的是二分法查找。查询键值是纯数字 ID，比如 1 到 100，就算中间一大片都没有 ID 对应的字符串，也需要占位符给填满，所谓有序排序。
微软可真是个小机灵鬼。
 |
1
NilChan 2021-05-29 02:32:22 +08:00 via Android  3
谁能来预测一下楼主还有几个下巴？
|
 |
2
zhilincom 2021-05-29 02:49:36 +08:00
存储空间不值钱。。
|
 |
3
codehz 2021-05-29 02:51:05 +08:00 via Android
完全不是这个原因。。。
通过优化布局加速查找那只能算常数优化。。。反正复杂度摆在那里，根本不可能真的有什么决定性的效果。。 占位的原因有很多，唯独不可能是为了优化查询效率，我猜测最有可能的原因有两个，一是空的 id 以前有用，现在不用了，但是为了避免出问题，就没有把后续的都移动一格填满 二是类似传统语言行号一样，预留空间给未来加入新的文本 |
 |
4
3dwelcome OP @codehz 我把源代码贴出来吧
https://github.com/Uberi/AHK-Scripts/blob/master/%40Completed/Programs/Decompiler/winmm/winmm/FindResource.cpp 代码可以编译调试。你看开始的超大一片注释，有很详细的设计说明。 字符串的 ID 键值，比如主图上"(c) 2017 Microsoft ..."对应的 30728 ID 数字，确实参与二分法查找的。 |
 |
5
no1xsyzy 2021-05-29 03:48:25 +08:00
没懂怎么个「二分法」
二分法不是只需要有序吗？中间添加空档不会影响啊 而且，二分不是要求有序吗，图片里这些也并不有序啊 …… 想了想，你说的是不是堆叠排列的二叉搜索树？感觉也不像啊 |
 |
6
ysc3839 2021-05-29 04:21:06 +08:00
https://devblogs.microsoft.com/oldnewthing/20040130-00/?p=40813
不是因为二分查找，是因为每 16 个字符串打包成一个 resource，然后第 N 个 resource 存的是 ID 为 (N-1)*16 到 (N-1)*16+15 的字符串，其中的格式是 2 字节的 length 加上字符串数据。如果字符串不存在的话，那也得保留 length，这就是你说的“[空 string]”，实际上代表的是 length = 0 。 |
|
7
3dwelcome OP @ysc3839 "不是因为二分查找，是因为每 16 个字符串打包成一个 resource"
30728 这个 ID，实际代码中被切成了两小块（ 30728 = 0x7808 = 0x780 * 0x10 + 0x8)。前一半(0x780)是二分查找，后一半(0x8)才是你说的每 16 个字符串打包。 |
|
8
ysc3839 2021-05-29 04:30:47 +08:00
|
|
9
ysc3839 2021-05-29 04:35:30 +08:00
@3dwelcome
你说“前一半(0x780)是二分查找”，我没感觉出这和二分查找有什么关系。 二分查找不是拿一个排好序的数组，去找指定值所在的位置吗？ 这里是已知 string id，根据 string id 到 resource id 的规则去找对应的 bundle 。 |
|
10
3dwelcome OP @no1xsyzy 我为了少写一点文字，化简部分原始二分算法。要不然首楼写太多文字，基本没人会看下去。
原始 ID 是按照 16 为间距，被分成一组一组。相当于其他算法里的 padding 。就算 DLL 里面只有一行文本资源，也会产生 1 个 string+15 个空 string 。 二分算法是为了在 DLL 的几万条文字资源里，也能快速找到特定 ID 号下，所对应的文本。 |
|
11
3dwelcome OP @ysc3839 “你说前一半(0x780)是二分查找，我没感觉出这和二分查找有什么关系。"
0x780 就是二分资源查找的索引啊。你比如 DLL 有几万行文本，要提取一个 ID，不可能一个个去挨个搜索。 微软就是对一组 16 个 string 的 ID 号，排序后保存到文件里的。 |
|
12
ysc3839 2021-05-29 04:46:33 +08:00
@3dwelcome
二分查找需要索引？你确定我们说的是同一个东西？ https://zh.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E6%90%9C%E5%B0%8B%E6%BC%94%E7%AE%97%E6%B3%95 我觉得这设计完全是为了避免查找，而设计的固定的寻址算法。查找是只有所有数据和值的情况下，找到值所在的位置。 而这个 string resource 的设计是有所有数据和 string id 的情况下，通过一个 O(1) 的算法算出 string id 对应的 bundle id 。 至于拿到 bundle 内容后的循环，是因为内容是不等长的，所以只能从头一个个长度相加得出最终位置，这跟查找也没关系。 |
|
13
3dwelcome OP @ysc3839 你 wiki 里提到的 khey，就是我说的二分索引值，中文表达不是很确切，就是这个意思。
楼上贴的原始代码地址也没错，具体代码是 // level 2: search by ID FindResDirEntry(0x708); 0x708 就是 khey, 是 DLL 文本资源的 resourceid 前半部分。你看这个函数内容，就是标准的二分查找算法。 |
|
14
ysc3839 2021-05-29 04:57:52 +08:00
@3dwelcome
那里的 khey 就是要查找位置的目标值啊，怎么是索引了。 再者，FindResDirEntry 以及你前面发的 FindResource.cpp 就不是 string resource 的东西，这是 PE resource 的格式。 你看看我前面发的 The Old New Thing 的代码，string resource 完全不关心 FindResourceEx 的实现，只要它能根据 ID 返回对应的 bundle 就行了。 |
|
15
3dwelcome OP “再者，FindResDirEntry 以及你前面发的 FindResource.cpp 就不是 string resource 的东西，这是 PE resource 的格式。”
别被函数名字给误导了，你别以为 string resource 是一个区块。而是一大批 ID 排序后，很多很多单独的区块。 所以我才说需要二分排序，如果你文本资源全部都在一个区块内，那还排序个啥。 只是 VS 的资源编辑器，让你误认为资源严格分块分类型，其实是打乱的。 |
|
16
ysc3839 2021-05-29 05:10:13 +08:00
@3dwelcome
我没有“以为 string resource 是一个区块”，我前面就说了“每 16 个字符串打包成一个 resource”。 无论 PE resource 怎么实现，只要它能够根据 ID 返回对应的 data，string resource 那套机制都能正常工作。 |
 |
17
Helsing 2021-05-29 09:19:21 +08:00 via iPhone
是不是为了字节对齐，这样寻址更高效
|
 |
18
loading 2021-05-29 09:22:48 +08:00
我为了我的配置文件不被乱改，我的配置文件名是：
system.dll ，其实原文件名是 port.conf 。 狗头。 |
 |
19
ntop 2021-05-29 20:46:24 +08:00
我怎么觉得你们说的都不对，我看下实现大概思路是：
1. 设计一个资源结构 - （其实是多个块）用来存储二进制结构的字符串资源 2. 设计一个寻址结构 - 用来查找字符串名到字符串地址的映射 也就是用二分的地方实际是计算字符串名的二进制的资源表的地址的，而这个地址存在的东西是结构化的。 类似于这种结构： 'hello' => 0x12345 => "I'm hello world". 先用可读的字符串名 “Hello” 去查字符串在 blocks 中的地址，然后直接读取字符串。 PS：上面这种资源存储方式其实很常见的，我只看了注释也有可能理解错误。 |
 |
20
wangxn 2021-05-30 11:39:15 +08:00
二分搜索需要元素的大小是固定的，显然变长字符串不可能符合这个要求。即使用了二分搜索也是如楼上所说，是在一堆大小固定的索引中进行搜索，再根据索引去其他地方拿具体的字符串。
|
Select Language