macfeng

提要：“你没有一句唱在调子上，为什么还总爱唱个不停?可是我真听不出自己走调在哪里啊?”你的身边一定有这样的人，唱歌爱跑调却总是自恋地充当“麦霸”。其实，唱歌总是找不着调是一种“病”，专家给这种唱歌“爱跑调”的病命名为“失歌症”

最近一直再从事eMule，BT，HTTP，FTP等下载协议的跨协议整合开发工作，对eMule的文件校验进行了仔细的分析，同大家分享一下相关的结果，有些结果来自与网络，向原作者表示感谢。 

1。首先介绍文件校验过程中的几个概念：
 文件ID
     文件ID用来惟一的标识网络中的文件和文件损坏侦测和修复。注意，eMule不依靠文件名来惟一标识和编目文件，通过哈希文件内容计算出的GUID标识文件。有两种类型文件ID-一种主要用来产生惟一的文件ID，另一种是用来损坏侦测和修复。(就是说文件ID是2类HASH值的总称，本身是一个抽象的概念，没有独立的实体)
 
   文件哈希
    文件是用由客户端和基于文件内容计算出来的128位GUID哈希来标识的。GUID是应用MD4算法到文件数据中计算而来。当计算文件ID时，文件被分成每段9.28MB长的部分。每部分单独计算出一个GUID，然后所有的哈希组合成一个惟一的文件ID。当下载的客户端完成一个文件部分下载时，它计算这部分哈希，然后和发送过来的这部分哈希对比，如果这部分发现损坏了，客户端尝试通过逐渐替换这部分中的位（每个180kb）来修复损坏部分，直到哈希计算OK。（具体修复过程参见后面的介绍）。
 
  根哈希
 用SHA1算法来为每部分计算根哈希，基于每块180kb大小。它提供了更高等级的可靠性和可修复性【具体在下面的文件校验方法中有详细说明】。
2。 下载文件的校验方法【详细介绍】
eMule使用各种方式来确保文件在网络共享及下载没有错误.万一错误发生, 称为损坏, eMule 有进阶功能以最小的额外重新下载资料量来修正这个损坏.校验方法分为ICH和AICH大类，或者说是侧重点不同的2个步骤

2。1文件哈希值和 ICH - 智慧型损坏处理

这里涉及到：文件哈希值, 部分哈希值，片段哈希值
在网络共享的每个文件有一个独一无二的识别值是由 MD4 密码数学运算所建立. 这个值称为文件哈希值并且每个标准的 eD2k 链接都有包含, 例如

ed2k://|file|name|12043984|6744FC42EDA527B27F0B2F2538728B3E|/

其中 6744FC42EDA527B27F0B2F2538728B3E 是文件哈希值以确定这个文件在整个网络是独一无二的被识别出.
这个 文件哈希值 是将文件划分为 9.28 MB 为一个部分所计算出来.（这个值是基于文件内容的）每个部分的部分哈希值也是使用相同的 MD4 运算方式计算出来. 那些 部分哈希值, 称为 片段哈希值, 并且它是被用来计算出最终的文件哈希值的.（HASH运算是分块进行的，每个分片的部分HASH可以看作是计算最终文件内容HASH值的中间结果） 例如一个 600 MB 文件被划分为 65 个部分，每个部分都有它自己的 部分哈希值， 而它是用来建立最终的 文件哈希值的.
为确保 eMule 总是接收到正确的块，一个特别的链接能包含片段哈希值, 例如

ed2k://|file|name|12043984|6744FC42EDA527B27F0B2F2538728B3E| p=264E6F6B587985D87EB0157A2A7BAF40:17B9A4D1DCE0E4C2B672DF257145E98A|/

其中 p= 值表示 片段哈希值. 每个 部分哈希值 是由 ":" 来区隔. 这个文件大小为 12043984 位元组 (=11.49 MB) 这表示它有一个完整的 9.28 部分和剩下的到 11.49 MB 部分为二个 部分切细片段.

2。2ICH 智慧型损坏处理详细过程：（这是基本的文件校验方式）
无论何时 eMule 完成某一个部分的下载它将会被检查, 假如下载的资料和部分哈希值一样，这个将成为已完成部分,同时这个部分会提供上传来帮助文件的散布.假如不是, 一个损坏发生，这部分会再次下载。为避免下载全部 9.28 MB文件块, ICH从这部分的开头180 KB重新下载并且再次检查部分是否完整. 假如不是, 下一个 180 KB 会再下载, 并再次检查. 直到部分哈希值正确为止. 最佳情况下假如损坏只在部分的开头 eMule只再次下载180 KB. 最差的情况可能会整个重新下载. 在部分的损坏 ICH 平均可节省50%.AICH - (Advanced Intelligent Corruption Handling)进阶智慧型损坏处理详细过程：（这是从0。44版以后引入的损坏恢复机制）
标准ICH有缺陷,如只对9.28MB的完整文件块有效,但不失为一个高效的功能. 但如果文件块出错的部位多于一处,或有问题的客户端重复地上传错误文件块,又或者根本上连那个文件块的Hash值都是有问题的,ICH就没有办法对付了.
但AICH会料理整个文件数据,让重新下载的数据减少到最小,并且可以重新生成Hash值.

根Hash, 区Hashes 和 AICH Hashset
这里涉及到【中文】： 根哈希值, 区块哈希值 &AICH 片段哈希值

这次处理的对象是文件中这些9.28 MB 的文件块. 每个文件块再细分成53个以180 KB为单位的区, 电骡再使用SHA1 方式为每个区生成一个Hash值. 这些Hash值叫做区Hash值,是AICH Hashset的最底层元素.
上图显示出的是一个由4个文件块组成的文件的Hash树形结构图.每个文件块包含 53 个区,这个文件共有 212 个区Hash值. 这些区hash值构成另7个层,至到最上面的 根Hash值. 这整个Hash树就叫做AICH Hashset.
图中那些绿点和红点表示从最底层的区Hash到最上面的根Hash的算数独立性. 这意味着一旦我们的根 Hash值无误,这树中的所有分枝都可以用它来校验. 电骡可以生成带有根Hash信息的链接, 如

ed2k://|file|文件名|12043984|6744FC42EDA527B27F0B2F2538728B3E|h=A2NWOTYURUU3P3GCUB6KCNW3FTYYELQB|/

其中h= 后面的就是根 Hash值. 在链接中提供这个数值,可以大大保证文件的防出错能力. 参考 可信的根 Hash值

3 修复坏文件块的详细过程：
一旦电骡发现文件块不对,它会使用完整的AICH Hash Set随机向一个客户申请一个修复包. 这个修复包里面包含当前文件块中所有53个区的区Hash数据和一个Hash树的校验码. 上面的图片显示一个由4个文件块构成的文件的修复包信息. 校验码的数量是由文件块的数量决定的.(2^x >= '文件块数量', x = 检验码数量).
当接收到修复包之后,电骡用校验码检查根Hash值. 如果无误,电骡开始用修复包中提供的区Hash值检查所有53个区. AICH会重新下载不符合区Hash的区.
如果修复成功,在日志中会显示如下的信息:

09.09.2004 02:43:43: 文件块 6 发现问题 ([file])
09.09.2004 02:43:46: AICH 成功修复[文件]的第6文件块中 8.22 MB的数据

可信根Hash
最保险的做法是从带有根Hash值的链接下载文件.如果文件的链接是可靠的,这个根Hash值就会被接受,然后电骡将它保存到硬盘中.如果链接中没有提供根 Hash值,电骡就只能接受来源发送过来的根Hash值. 电骡只相信最少10个来源发送过来的,并且一致的根Hash值,并至少92%的来源接受这个数值. 因为这个根Hash值的可靠性不能确定,所以它只在本次连接中有效,电骡也不会将它保存到硬盘,你也不能用它来生成带有根Hash值的链接.一旦 AICH Hashset生成完成, 如文件下载完成, 电骡就开始向其它客房端传播这个根Hash值.为了加快内容分发的速度，分块处理是一种简单有效的方法。emule中对每个文件都进行了分块处理。另外分块还有一个好处就是如果保留了每一分块的hash值，就能在只下载到文件的一部分时判断出下载内容的有效性。emule在获取每个共享文件的信息时，就对它进行了分块处理，因此如果要知道emule中的分块处理和恢复机制，看CKnownFile::CreateFromFile函数的实现就行了。结合eMule的源代码分析，这个函数中牵涉到的和分块处理以及hash计算相关的类都在SHAHashSet.cpp和SHAHashSet.h中。下面介绍其中几个主要的类：
CAICHHash类只负责一块hash值，提供两个CAICHHash类之间的直接赋值，比较等基本操作。CAICHHashAlgo是一个hash算法的通用的接口，其它hash算法只要实现这种接口都能使用，这样，可以很方便得使用不同的hash算法来计算hash值。CAICHHashTree则是一个树状的hash值组织方式，它有一个左子树和右子树成员变量，类型是指向CAICHHashTree的指针，这是一个典型的实现树状结构的方法。CAICHHashSet中包含了一个CAICHHashTree类型的变量，它直接向CKnownFile负责，代表的是一个文件的分块信息。
SHAHashSet.h文件的开始的注释部分向我们解释了它的分块的方式。这里要用到两个常量9728000和184320，它们分别是9500k和180k。这是emule中两种不同粒度的分块方式，即首先把一个很大的文件分割成若干个9500k的块，把这些块组织成一颗树状的结构，然后每一个这样的块又分解成若干个180k的块(52块，再加一个140k的块)，仍然按照树状的结构组织起来。最后总的结构还是一颗树。
CKnownFile::CreateFromFile方法是在读取目标文件的内容时，逐步建立起这样一颗树的。CAICHHashTree::FindHash能够根据读取到的目标文件的偏移量和下一块的大小，来找出对应的树枝节点(就是一个指向CAICHHashTree的指针)。如果有必要的话，还会自动创建这些树枝节点。因此在进行分块操作的时候，把文件从头到尾读一边，整个CAICHHashTree就建立起来了，对应的分块hash值也赋值好了。最后我们还需要注意的就是CKnownFile类中的hashlist变量。就是说它还单独保留直接以9728000字节为单位的所有分块的MD4算法的hash值。这样对于一个文件就有了两套分块验证的机制，能够适应不同场合。

eMule数据文件校验的注意点: 
(1) 新发布的文件或稀有文件可能会没有足够的来源数来产生一个可信的根Hash值. 建议在发布文件时带上这个数值.
(2)如果不存在根Hash值或这个数值是伪造的,电骡会以正常方式下载并完成这个文件.但在这种情况下不能使用AICH功能. 
(3) 因为AICH Hashset比较大,它不被存在内存里,而被保存到known2.met文件中.只有在发现错误时才读取这个信息.
(4) AICH只对v.44a或以上版本的电骡有效,但它和更早版本的电骡兼容.

附：emule实现文件校验的相关数据结构：

CPartFile类是emule中用来表示一个下载任务的类。这就是一个还没有完成的文件。当一个下载任务被创建时，emule会在下载目录中创建两个文件，以三位数字加后缀part的文件，例如001.part，002.part等。还有一个以同样的数字加上.part.met的文件，表示的是对应文件的元信息。part文件会创建得和原始文件大小一样，当下载完成后，文件名会修改成它本来的名称。而事实上，诸如这个文件原来叫什么名称，修改日期等等信息都在对应的.part.met元文件中。.part.met中还包含了该文件中那些部分已经下载完成的信息。CPartFile类中Gap_Struct来表示文件的下载情况，一个Gap_Struct就是一个坑，它表示该文件从多少字节的偏移到多少字节偏移是一个坑。下载的过程就是一个不断填坑的过程。CPartFile类中有个成员变量gaplist就是该文件目前的坑的状况列表。需要主要的是有时填了坑的中间部分后，会把一个坑变成两个坑。坑的列表也会被存进.part.met中。

对数据的校验也是通过这个类完成的：主要数据结构
struct Requested_Block_Struct   （请求块的结构）
{
 uint64 StartOffset;
 uint64 EndOffset;
 uchar FileID[16];
 uint64  transferred; // Barry - This counts bytes completed
};
#pragma pack()

struct Gap_Struct  （标识坑的结构，下载可以看作是填坑的过程）
{
 uint64 start;
 uint64 end;
};

struct PartFileBufferedData （写入文件的缓冲数据结构）
{
 BYTE *data;      // Barry - This is the data to be written
 uint64 start;     // Barry - This is the start offset of the data
 uint64 end;      // Barry - This is the end offset of the data
 Requested_Block_Struct *block; // Barry - This is the requested block that this data relates to
};
在每个任务中又三个链表
CTypedPtrList<CPtrList, Gap_Struct*> gaplist;
 CTypedPtrList<CPtrList, Requested_Block_Struct*> requestedblocks_list;
// Barry - Buffered data to be written
 CTypedPtrList<CPtrList, PartFileBufferedData*> m_BufferedData_list;