绵掌集散地潜水版

魔兽3内存修改器 v6

2008-10-27T13:18:00.001+08:00

原文

由于hsluoyz同学强烈要求我研究一下魔兽3 1.20e的HP摆放位置，以便达到他某个不可告人的目的，加上本人确实无法接受v5版修改器不能改一般单位的事实，所以昨天晚上作了这个v6修改器。这一次的重点是对3个版本的支持以及无注入的新思路。

修改器+源代码+手册打包：war3trainerv6.rar

[新特性]

无注入的新思路：这一版实现了不修改游戏代码，当然更不是内存搜索，全部直接定位。游戏怎么运行，我就怎么拿到数据，十分猥琐。
同时改多个单位：现在你可以一次选中几个单位，我会列出你选择了什么。
又可以改单位了：既然单位可以改，建筑也就可以改。
多版本支持：受不了某些不肯升级游戏的朋友了，现在支持1.20e、1.21、1.22.0.6328三个版本。
修改单位的坐标：下图就演示了主基地平移。
英雄技能：按照hyp的指示，加了最简单的技能修改，更加复杂的修改没有做。

主基地平移，采矿速度提升；
注意到树丛中的大法师了吗？
另外建筑的阴影明显只是一张贴图

[关于选中单位ESI的获得]
以下以1.22为例说明我是怎么拿到玩家选择的所有单位。

另外我要正告hsluoyz同学：我怀疑你找来的那个静态指针不具有普遍意义。我愿意以一顿晚饭的代价跟你打赌。

获得选中列表并不困难，如果你不愿意用我的思路，你也可以直接在内存中搜索“.?AUCUnitListNode@@”获得ESI队列，或者用.\CPlayerWar3.cpp所在的段+90拿到链表基地址然后推算单位地址，都可以。但是我是不做内存搜索的，所以步骤略多：

[6FAA2FFC] 记为A1
参考：
6F416B0A mov edi, 6FAA2FFC
6F416B10 movzx ebx, word ptr [edi + 28]
6F416B14 call 6F52F4A0
[A1 + 58 + 4 * a2] 记为A2，a2取0
参考：6F3A0564 mov eax, [ecx + eax * 4 + 58]
[A2 + 34] 记为UnitListRoot
参考：6F2CC0AE mov ebp, [eax + 34]
这个UnitListRoot的数据结构：
struct UnitListRoot
{
BYTE NotSure[0x1F0];
UnitListNode* Head, End;
DWORD Length;
}
参考：6f415b95 mov eax, [ebx+1F4]
UnitListNode的数据结构：
struct UnitListNode
{
UnitListNode* Next;
DWORD notNext;
UnitBase* thisUnit;
}
其中notNext总是等于~Next，而thisUnit就是上次要找的ESI。

[后记]
这一次我会说得比较小心：我不知道我还会不会更新这个修改器了。

vb的kbhit()实现

2008-10-25T20:36:00.001+08:00

 这里是原文

数值分析考得如此简单，以至于感觉白复习了。

晚上，因为一些原因我很希望串口的数据能及时dump到硬盘上，可恶的是手头的串口调试工具都不怎么顺手，我气愤了，所以决定写一个题为《不就是个串口嘛！》的程序。很多功能还没有来得及加上，以后再完善，先用起来再说。

网上的一些vb6高手似乎很懒，实现了控制台、读取、写入、颜色等等功能，唯独没有加上这个关键的kbhit()函数。那怎么能行呢！所以这篇文章特别dump了c语言的库函数：

Public Function kbHit() As Boolean ' Dim m_StdInput As Long ' m_StdInput = CreateFile("CONIN$", _ ' GENERIC_READ Or GENERIC_WRITE, _ ' FILE_SHARE_READ Or FILE_SHARE_WRITE, _ ' 0, _ ' OPEN_EXISTING, _ ' 0, _ ' 0) ' 或者，m_StdInput = GetStdHandle(STD_INPUT_HANDLE) Dim nRet As Long Dim CharsRead As Long Dim nEvents As Long Dim Events() As INPUT_KEY_EVENT_RECORD nRet = GetNumberOfConsoleInputEvents(m_StdInput, nEvents) If nRet = 0 Or nEvents = 0 Then kbHit = False Exit Function End If ReDim Events(0 To nEvents - 1) nRet = PeekConsoleInput(m_StdInput, Events(0), nEvents, CharsRead) If nRet And CharsRead <> 0 And CharsRead <= nEvents Then Dim i As Long For i = 0 To nEvents - 1 If Events(i).EventType = KEY_EVENT And _ Events(i).bKeyDown Then ' [tc]Caution: Events(i).AsciiChar is ignored ' [tc]Caution: _getextendedkeycode is ignored kbHit = True Exit Function End If Next End If kbHit = False End Function

相关定义我就不贴了，网上满大街都是。这个程序中间我注有两个Caution，如果检测到的按键并不是键盘上的按键，理论上kbhit应该返回False，但是这段代码不是这样。所以这个函数其实是不完美的，为什么我不去实现_getextendedkeycode呢？因为我比较懒……

[tc]的Blogger重新开张

2008-10-13T08:06:00.001+08:00

此前去年由于Blogspot域名被封，本人将Blog搬迁到了yo2。今天决定依然以tctianchi.yo2.cn作为主站，偶尔把好一点的文章转到这里来，07年级以前发布的文章不变。

所以这里就要改名了，现在叫做《绵掌集散地潜水版》。所以还是欢迎网友到主站去玩！

魔兽3内存修改器V5 For 1.22.0.6328，以及智力修改详解

2008-10-09T18:38:00.000+08:00

原贴：http://tctianchi.yo2.cn/articles/%e9%ad%94%e5%85%bd3%e5%86%85%e5%ad%98%e4%bf%ae%e6%94%b9%e5%99%a8v5-for-12206328%ef%bc%8c%e4%bb%a5%e5%8f%8a%e6%99%ba%e5%8a%9b%e4%bf%ae%e6%94%b9%e8%af%a6%e8%a7%a3.html

距离上一次写魔兽修改器（V4在这里）已经有超过一年半的时间了，这个期间有不少网友来信，但是我完全没有要再写一版的意思。包括像出现在本Blog的hyp发布了他自己的修改器（这里），包括暴雪出了1.22补丁，我都没有改。直到另一位网友给我写信（他没有留言，我假设他不希望自己的名字出现在这里）声称他已经能找到所有单位的HP为止，我顿时 ~~愤怒了~~ 对他刮目相看！

于是我想写一个集大成的修改器，可以模拟整个游戏界面，看到地图上的所有单位，可以点击任何想改的数据然后改掉，切换到游戏时已经改好……做一个这样的修改器好像难度也不会很大，但是我还很忙，所以就不要这么麻烦了（雾很大）。

这两天我趁glascholar同学帮我去解决电脑上没有导出并口接插件并且寄到苏州来的空档，做了这个V5修改器来针对1.22.0.6328版的Warcraft 3。为了避免与hyp同学重复，我依然没有用内存搜索的方法来做，而是坚持了我以前的游戏代码篡改的思路。但是与V4不同的是，我花了很大力气实现了只注入一次就能修改全部属性的特性。也就是说：我已经解决了单位各属性地址之间的关系。所以其他人也应该可以根据我的理论实现自己的内存搜索版的修改器。

修改器+源代码+手册打包：war3trainerv5.rar

[特性]

仅适用于魔兽3 1.22.0.6328，其他版本不用试也知道不行
可以修改前10个玩家的钱，并且不用注入就能修改
可以修改英雄的一些属性，每个英雄只需要注入一次，其他地址可以推算
V5的注入对一般单位无效，这反而变成V5修改器的缺陷，而V4版是可以改一般单位的。因为唯一的一次注入放在了英雄状态栏绘制的函数里面，而V4版是每个属性单独注入一次，所以没有这个问题。如果我愿意放下自尊，不去搞什么“只注入一次”的话，就可以解决这个问题，但是这样就无法炫耀技术了，对吧？
智力修改完美解决，现在不可能找不到智力的地址了
新增HP、MP，及其最大值的修改

[详解智力修改]
在V2版（这里）中，我曾经给过一个傻x的修改方案，现在给出更加精确的算法。为什么智力的修改与力量、敏捷不同。这是因为后两者的代码比较集中，而且代码也比较规则。例如力量的绘制代码如下：

6F353D7D	mov ecx, [ebp+0D4h]	eHeroMultiply = *(pAttribute1 + 0x35);
6F353D83	mov esi, [ebp+94h]	vHeroPower = *(pAttribute1 + 0x25);
6F353D89	mov [esp+8ECh+eHeroMultiply], ecx
6F353D8D	lea ecx, [ebp+6Ch]	vPowerAdd = sub_6F4634E0(pAttribute1 + 0x1B);
6F353D90	call sub_6F4634E0	vPowerAdd = sub_6F4634E0(pAttribute1 + 0x1B);
6F353D95	lea edx, [esp+8ECh+eHeroMultiply]
6F353D99	push edx
6F353D9A	mov edx, eax	ePowerAdd = ZipNum_Encode_NotSure(&tmpInt1, vPowerAdd);
6F353D9C	lea ecx, [esp+8F0h+tmpInt1]
6F353DA0	call ZipNum_Encode_NotSure
6F353DA5	mov edx, eax	ePowerSum = ZipNum_Multiply_NotSure(&tmpInt2, ePowerAdd, &eHeroMultiply);
6F353DA7	lea ecx, [esp+8F0h+tmpInt2]
6F353DAB	call ZipNum_Multiply_NotSure
6F353DB0	mov ecx, eax	vPowerSum = ZipNum_Decode_NotSure(ePowerSum);
6F353DB2	call ZipNum_Decode_NotSure	vPowerSum = ZipNum_Decode_NotSure(ePowerSum);
6F353DB7	add eax, esi	s578_SStrPrintf( Buffer1, 0x40u, "%d", vHeroPower + vPowerSum - *AttributeBiasCopy1 );
6F353DB9	sub eax, [ebx]
6F353DBB	push eax
6F353DBC	push offset aD_0 ; "%d"
6F353DC1	lea eax, [esp+8F4h+Buffer1]
6F353DC5	push 40h ; BufferSize
6F353DC7	push eax ; Buffer
6F353DC8	call s578_SStrPrintf
6F353DCD	mov esi, [ebx]
6F353DCF	mov ecx, [esp+8FCh+GBufferCopy1]	GBufferCopy2 = GBufferCopy1;
6F353DD3	add esp, 10h
6F353DD6	add esi, [ecx]	sumPower = GBufferCopy1 + AttributeBiasCopy1; if ( sumPower ) {
6F353DD8	jz short loc_6F353E1B
6F353DDA	test esi, esi
6F353DDC	mov eax, offset aCff00ff00_1 ; " \|CFF00FF00+"	tmpString1 = " \|CFF00FF00+";
6F353DE1	jg short loc_6F353DE8	if ( sumPower<= 0 )
6F353DE3	mov eax, offset aCffff0000_1 ; " \|CFFFF0000"	tmpString1 = " \|CFFFF0000";
6F353DE8	push 40h ; MaxLength	s503_SStrNCat(Buffer1, tmpString1, 0x40u);
6F353DEA	push eax ; pSrc
6F353DEB	lea edx, [esp+8F4h+Buffer1]
6F353DEF	push edx ; pDest
6F353DF0	call s503_SStrNCat
6F353DF5	push esi	s578_SStrPrintf(Buffer2, 0x40u, "%d\|R", sumPower);
6F353DF6	push offset aDR ; "%d\|R"
6F353DFB	lea eax, [esp+8F4h+Buffer2]
6F353DFF	push 40h ; BufferSize
6F353E01	push eax ; Buffer
6F353E02	call s578_SStrPrintf
6F353E07	add esp, 10h	s503_SStrNCat(Buffer1, Buffer2, 0x40u);
6F353E0A	push 40h ; MaxLength
6F353E0C	lea ecx, [esp+8F0h+Buffer2]
6F353E10	push ecx ; pSrc
6F353E11	lea edx, [esp+8F4h+Buffer1]
6F353E15	push edx ; pDest
6F353E16	call s503_SStrNCat	}

智力的代码在6F0DA9D0，内存位置不完全相同，感兴趣可以去看，本质上还是一样的。下面的步骤供修改器使用。但是我要说，如果只注入一次的话，最难改的不是智力，而是移动速度的话，你相信吗？这件事情详见附件里面的手册。这里讲智力。

第1步：搞到英雄的基址，可以在6F353D25拿到ESI，并且解开（即所谓解引用，或者寻址），并且做如下定义：
○ ESI记为ThisUnit
○ [ThisUnit + 1E4] 记为 UnitAttributes（这里用不到，改别的东西要用）
○ [ThisUnit + 1EC] 记为 HeroAttributes
这个1EC是怎么来的呢？
参考的代码：6F353D00
即：int __thiscall DrawHeroProperty(int *GameContext, int **Attributes, int *AttributeBias, unsigned int *GBuffer)
　

6F353D51	mov ebp, [eax + 1ECh]	pAttribute = Attributes[0x7B]; // 7B * 4 = 1EC
……	……	……
6F353EDE	mov ecx, ebp	vIntellect = getHeroIntellect_NotSure(pAttribute);
6F353EE0	call 6F0DA9D0	vIntellect = getHeroIntellect_NotSure(pAttribute);

第2步：获得智力的游戏全局索引，定义：
○ [HeroAttributes + 7C + 2 * 4] 记为 Index1
○ [HeroAttributes + 7C + 3 * 4] 记为 ReferenceNumber1

参考的代码：6F0DA9D0
即：int __fastcall getHeroIntellect_NotSure(int* pAttribute)

6F0DA9DE	lea ecx, [esi + 7Ch]	vHeroIntellect = sub_6F4634E0(pAttribute + 0x1F); // 1F * 4 = 7C
6F0DA9E1	call 6F4634E0

参考的代码：6F4634E0
即：int __fastcall sub_6F4634E0(int *base)
　

6F4634E0	mov edx, [ecx + 0Ch]	return (_DWORD )( getValueFromGame((base + 2), (base + 3)) + 0x78 );
6F4634E3	mov ecx, [ecx + 8]
6F4634E6	call 6F03F180
6F4634EB	mov eax, [eax + 78h]
6F4634EE	retn

第3步：使用所谓<算法1>（6F4634E0），获得智力的地址。

步3.1：[6FAA4178] 记为 ThisGame
步3.2：[ThisGame + C 记为 ThisGameMemory
步3.3：[ThisGameMemory + Index1 * 8 + 4] 记为 Address1
步3.4：[Address1 + 18] 应当等于ReferenceNumber1，不相等游戏会异常（访问地址0），所以做修改器不用考虑这里
步3.5：Address1 + 78 作为地址，里面是智力

参考的代码：6F03F180
即：int __fastcall getValueFromGame(unsigned int nIndex, int ReferenceNumber)

……	……	result = (_DWORD ) ( (_DWORD )(dword_6FAA4178 + 0xC) + 8 * nIndex + 4 ) & ( ((_DWORD ) ((_DWORD ) ((_DWORD )(dword_6FAA4178 + 0xC) + 8 * nIndex + 4 ) + 24 ) != ReferenceNumber) - 1 );
6F03F1DA	mov eax, [esi + 0Ch]
6F03F1DD	mov ecx, [eax + ecx * 8 + 4]
6F03F1E1	xor eax, eax
6F03F1E3	cmp [ecx + 18h], edx
6F03F1E6	pop edi
6F03F1E7	setnz al
6F03F1EA	pop esi
6F03F1EB	sub eax, 1
6F03F1EE	and eax, ecx
6F03F1F0	retn	return result;

需要特别指出的是，还有一个所谓<算法2>（6F468A20）也很重要，改移动速度要用到，详见我的手册。

[后记]
这两天我在game.dll、Storm.dll阅读了超过万行汇编。在这里严重感谢Hex-Rays这款插件，虽然有的时候也会越帮越忙，但是如果没有她，我肯定无法在短时间内完成这样的工作量。

有鉴于我此刻已经厌倦修改魔兽，所以这一回，应该不会再出V6了吧！

C&C3：怎样零伤亡打赢最难电脑

2007-07-20T08:02:00.001+08:00

原贴：http://tctianchi.yo2.cn/articles/cnc3singleplay.html

　　C&C3的最难电脑以疯狂的经济基础而闻名，不过这样的电脑也并不是不可战胜的。观察表明，如果电脑没有矿场或矿车，钱是不会自动增加的。所以压制电脑的经济是越早越好的。以下针对1.05版以GDI为例说明打法，其他阵营仅给出录像。

[地图]
今天的战场是《竞技场》，著名2人地图。我先解释一下这张地图。当前位置为我方出生点，左上角为NOD。中间有两个分矿，对角上有两个蓝矿，电脑不会去用，但是会占领两个地堡。中间的上方和下方各有一个白点，那是油井，我们不管它。

　　任务目标：不使用BUG，不使用工程师逼退策略，赢下最难电脑。争取最短时间、最少伤亡、最多资源。

[初期]
双矿场开局。
主基地：F10生产线－F2矿场－F3兵营－F1电厂
生产线：　　　F1电厂－F2矿场－F5雷达－F8高科
下雷达的时候，兵营造好一个机枪兵，收起基地车，赶往对手分矿。

　　路上遇到一工程师，不要客气。

　　如图所示，放下两个声波塔。补上一个电厂，升级催化。

　　电脑对这种战术感到茫然无措。

　　注意：声波塔到达5个以前非常脆弱，一定要控一下，以最大伤害范围为主旨。

[中期]
过渡时期需要在家里补一两个声波。电脑的偷袭可能从上面、右边、左下进行，根据实际情况安排。

　　电脑迅速做出反应，建造了空军来偷袭，不过我已经备好了防空。那我怎么知道电脑会有毒液的呢？因为意识好！

　　——刚才是吹牛，因为[tc]曾经因此损失矿车一部，没有实现０伤亡。

注意：发现火焰坦克一定要退出里面的机枪兵。

　　电脑看到我防空不多，所以会继续毒液，所以我也继续回应之。

　　现在开始疯狂地扩张（看小地图）。

[后期]
出一些MM的同时，把红血的单位拿来修。

　　注意：最后关头也请时刻注意微操，MM并不是不会挂的。[tc]曾有多次在最后几分钟失去获得零伤亡录像的机会的惨痛经历。

　　用MM来结束战斗会不会太俗套了呢？

　　注意：一旦开始生产MM就要升级轨道炮。[tc]居然忘记升级了，这是本录像的重大失误。

[结局]
后半段[tc]打得并不好看，主要是因为[tc]太过谨慎了。比赛越是到后期，越是有可能损失一两个单位造成遗憾。

　　以上战略实际上10分钟左右就可以结束，但是要保证0部队伤亡＋0建筑损失，是非常不容易的一件事。[tc]我打了整整一个晚上，才成功了一次。

先附上本教学录像：replay-gdi-perf.rar

第二个录像是之前打的版本，除了一不小心挂掉一个炮台之外，应该说比上面的录像打得好。replay-gdi.rar

[其他阵营]
先说NOD。NOD的高机动性、隐形在电脑的作弊下黯然失色，但是NOD拥有本游戏最多的技能，应当加以利用。可惜[tc]暂时还打不出比较好的录像。replay-nod.rar

这个录像和上面一样是Tower Rush，但是没有实现零伤亡。

Scim，1.05版的MotherShip对射程作了调整，所以利用一下。

虽然只要3分钟就可以解决问题，但是录像没有实现零伤亡。replay-sc.rar

NOD和外星人的零伤亡录像我以后再做，现在先摆在这里。

说明：我搬过家了

2007-04-17T22:16:00.000+08:00

由于本Blog日前域名被封，[tc]已于2007-03-25搬迁至

http://tctianchi.yo2.cn/

[tc]魔兽3 1.21内存修改器 V4

2007-03-17T19:54:00.000+08:00

由于Blood+缺了一集，一边等候下载，一边就写了这个V4版。有些代码写的实在垃圾，懒得改了，于是又贴了几个补丁。
　　这次除了补完上次说的“攻击力”、“攻击类型”、“防御类型”之外，“防御力”也被我“一不小心”改出来了。“智力”还是像以前一样，有找不到的几率，暂时还没有想到解决方案。

　　因为此次更新并不完全是一时兴起，所以那个修改金钱的难题是一定要解决的。
　　6F088E78: mov eax,[edx+78] 8b 42 78
　　金钱和智力一样，代码是公用的，有一定的几率会变成无用的地址，好在几率不大，大部分时间是在一个区域内不停的变动，[tc]仔细一看：edx的低16位居然是固定的！比如P1的金钱始终是[0190]，P2是[1410]，只有高16位是不固定的。这就好办了，取下上16位，补上我们自己的下16位即可！该问题完美解决！
　　编程的时候值得一提的是：这次[tc]决意尽可能少的修改原来游戏的代码。此前的修改存在冗余！比如“力量”、“敏捷”，我是分开搜索的。但是明眼人很快会发现，这两个地址是相关的，只要找到其中一个，另一个也能推算出来。这次修改金钱也是一样的道理。
　　[tc]修改了Player 1-10（注：魔兽最多可以有12个在线玩家，我一时偷懒只作了10个）的金、木、人口、最大人口，但是这些数据是相关的：对于同一个人而言，偏移地址是这样的：
　　　　金　　　　　　0x 0
　　　　木　　　　　　0x 80
　　　　最大人口　　　0x180
　　　　当前人口　　　0x200

　　不出意外的话，这是我最后一次更新这个修改器了。因为基本上能想到的东西都已经写了。

推箱子的求解

2007-03-15T22:55:00.001+08:00

经过两周的折腾，白了头发无数，终于能算一些简单的地图了。15x15以内的地图基本上不超过5秒钟能有近似最优解。超过20x20的地图，10分钟之内没有结果，我也没耐心等下去。
　　整个算法看起来是这样的：首先选择可以移动的箱子的集合，选择一个深度优先遍历，当发现下一步有重复时，选择较短的路径；当树的深度超过一个限度时，把叶子节点送入一个链表；只要那个链表不空，那么设定新的最大深度，回到第一步。为了判定初始的深度，需要对箱子与目标点作一次匹配（我选择的是最大代价匹配）。
　　为了实现A*算法，使用了许多类来作支撑，比如：
　　　clsShortestPath　　　　　专门求迷宫的最短路径，翻译自高中时候的程序
　　　clsGraph_MostMatching　　二部图最大匹配
　　　clsMapData　　　　　　　　跟地图有关的操作在这里
　　　clsMapStatus　　　　　　　跟地图状态有关的操作在这里
　　　clsSolution　　　　　　　求解的主程序，根据一个基本clsSolutionNode作为树根，展开所有解
　　　clsSolutionNode　　　　　解的内容、保存下一个解的链状结构，当树的深度超过给定值时会调用制定的函数保存状态
　　　clsSolutionNodeHistory　　纪录解的历史，在重复的解中选择路径比较短的解

　　如果有人说这样写效率会不会很低？我认为不会，我没有使用virtual，不算真正的OO，在静态绑定的作用下，效率不会很低。
　　代码总共33k，没办法把源代码贴出来。下面是程序到目前为止的5个版本的What's New，从中可以说明一些问题。

V1
● 用链表实现广度优先
● 计算下一级时，回收上一级内存

V2
● 改进的内存回收，能快速回收同一层的内存
● 阻止嵌入角落
● 修改了过程保存的方式（不再是string），减小了内存使用
● 防止重复上一次的步骤的反过程（比如上一次是向左，那么这一次不会向右），用list实现

V3
● 下定决心，把广度优先改成深度优先，用树实现，保存下一步的是list
● 新建clsSolutionNodeHistory，加强了重复路径搜索能力，杜绝重复的搜索
● 明确了地图clsMap、地图数据clsMapData的不同（前者只有地形数据），减小了内存占用和构造时间
● 修正了图形显示的小Bug（箱子、目标位置的标记不能通过单次循环完成）
● 新增了一个小的地图编辑器（VB）

V4
● 地图优化：自动判定不能放置箱子的区域（不需要再在地图编辑器中作弊了）
● 改进的clsSolutionNodeHistory：情况相同时，如果上一次失败了，那么取消现在的尝试；如果上一个记录还没有计算过，那么选择路径比较短的一次
● 进一步改进了状态的保存，clsMapData改名为clsMapStatus、clsMap改名为clsMapData
● 追加了一个看似十分垃圾的评价函数，以箱子与目标的距离作为判定依据，这样就形成了一个简化的A*算法
● 强制限定了运算深度，由于不能自动追加深度，还不能看作是IDA*算法
● 为了得到初始的运算深度，用网络流实现了二部图的最优匹配
● 为了提供最优匹配的原始数据（目前是每个箱子到每个目标的距离），编写了最短路经搜索代码，代码用的是高中时写的VB程序，算法名字不记得了，只知道空间复杂度O(n^4)，时间复杂度O(n^2)

V5
● 题解程序将步数溢出的节点压入一个链表，IDA*得以实现
● 最优匹配从自小代价改为最大代价（也就是说，假定编地图的人让玩家总是把箱子推到最远的目标点，真是无语了）

用最大流实现二部图最大匹配

2007-03-15T08:52:00.000+08:00

为了某个已经折腾了两周的程序，花了两天时间实现了二部图的最大匹配，现分享如下。

　　题目的简化版是这样的：ABCD四个节点要对应1234四个节点，每个字母对应一个数字、每个数字对应一个字母。已知每个字母与每个数字只见的对应代价是不一样的。现在求最佳的配对方案，使得总代价最大／最小。
　　这个问题属于二部的带权匹配问题，网上似乎有不少解法，基本上是用匈牙利算法解决的。但是考虑到带权问题的复杂性，以及日后扩充要求的可能性，[tc]决定还是用网络流来求解。

　　[tc]的参考书：《网络最优化》，刘家壮，高等教育出版社，1991年。
　　用网络流求解的思路是这样的。由于已知字母与数字的关系如下图所示（对应关系的弧略去），
　　　A \/ 1
　　　B \/ 2
　　　C /\ 3
　　　D /\ 4
　　可以在现有的关系基础上，增加一个只有出度的开始节点s，和一个只有入度的结束节点t。
　　　　/　A \/ 1 \
　　　S -　B \/ 2 - T
　　　　\　C /\ 3 /
　　　　\　D /\ 4 /
　　显然s到t的计算过程可以找到字母与数字的匹配。现在设网络内的容量全部为1，当前流量为0，那么容易证明匹配结束后，每个字母对应一个数字、每个数字对应一个字母。

　　既然思路确定了，程序也就简单了。下面的代码是用来测试的，实际使用时可以整理成类，整理成类的方法就不说了。
　　注意这个算法的时间复杂度大约是O(n^2*L)，n是矩阵度数，L是一个不确定的值，L < n，与匈牙利算法的O(n ^ 3)相比差不多，但是可以轻易的扩展成更复杂的程序。
　　另外为了功能需要，下面的代码包括了求最大最小值两个代码，是用宏定义来区分的，看代码时请特别小心。

#include "stdafx.h"
//////////////////////////////////////////////////////////////////
// 用最大流实现二分图最大匹配
// 网络最大流（容量1），添加了超级源、超级汇
#include < stdio.h >
#include < string.h >
/*
样例：
INPUT
3

3 5 2
3 2 8
7 5 8

OUTPUT
20
*/

// 如果是寻最大值，需要下面这句
// 如果是寻最小值，屏蔽下面这句
//#define __FIND_MAX

const int maxn=100;
const int maxint=32767;
struct stuAbutMatrixNode // 邻接矩阵
{
int weight, // 权重
flux, // 流量
capability; // 容量
};

struct stuGraphicNode
{
int value, // 值
fa; // 度
};
stuAbutMatrixNode iAbility[maxn+2+1][maxn+2+1]; // 0..maxn+2
stuGraphicNode best[maxn+2+1];
int numItems,
numMaxWork,
s,t; // s、t是始边、终边的下标

void init()
{
int i,j;
scanf("%d",&numItems);
memset(iAbility,0,sizeof(iAbility));
for(i=1;i<=numItems;i++)
for(j=numItems+1;j<=2*numItems;j++)
{
iAbility[i][j].capability=1;
int iInput;
scanf("%d",&iInput);
iAbility[i][j].weight=iInput;
iAbility[j][i].weight=-iInput;
}
s=2*numItems+1;
t=2*numItems+2;
for (i=1;i<=numItems;i++)
{
iAbility[s][i].capability=1;
iAbility[numItems+i][t].capability=1;
}
numMaxWork=0;
}

bool find()
{
int i,j;
bool quit;
#ifdef __FIND_MAX
memset(best,0,sizeof(best));
best[s].value=1;
#else
for(i=1;i<=2*numItems+2;i++)
best[i].value=maxint;
best[s].value=0;
#endif
do
{
quit=true;
for(i=1;i<=2*numItems+2;i++)
#ifdef __FIND_MAX
if(best[i].value>0)
#else
if(best[i].value!=maxint)
#endif
for(j=1;j<=2*numItems+2;j++)
if (iAbility[i][j].flux
#ifdef __FIND_MAX
if (best[i].value+iAbility[i][j].weight>best[j].value)
#else
if (best[i].value+iAbility[i][j].weight
#endif
{
best[j].value=best[i].value+iAbility[i][j].weight;
best[j].fa=i;
quit=false;
}
}while(!quit);

#ifdef __FIND_MAX
if(best[t].value>1)
return true;
else
return false;
#else
if(best[t].value
return true;
else
return false;
#endif
}

void add()
{
int i,j;
i=t;
while(i!=s)
{
j=best[i].fa;
iAbility[j][i].flux++;
iAbility[i][j].flux=-iAbility[j][i].flux;
i=j;
}

int x,y,value;
y=best[t].fa;
x=best[y].fa;
value=iAbility[x][y].weight;
printf("(%d,%d)=%d\n",x,y-numItems,value);

#ifdef __FIND_MAX
numMaxWork+=best[t].value-1;
#else
numMaxWork+=best[t].value;
#endif
}

int main()
{
init();

while(find())
add();

#ifdef __FIND_MAX
printf("Max=%d\n",numMaxWork);
#else
printf("Min=%d\n",numMaxWork);
#endif

return 0;
}

sprintf等C用法在C++的转换的小记

2007-03-10T15:29:00.000+08:00

当我主张（在PC上）用C++的新用法替换C语言的旧式用法时，许多人问来一些奇怪的问题，这里收集了几个典型问题，探讨一下。

1、字符数组
　　别用这个了，string更好，也标准。同寝室有个同学更喜欢CString，好吧，这个我也没意见，我一般用string，因为我总觉得CString是MFC的东西（其实不是），有恐惧心理。
　　另一方面，string是一个模版类，如果需要宽字节（比如Windows程序），就要用wstring代替，关于这个问题我另外撰文说明好了。简单的说，如果要显示中文，应该使用国际化支持，例如：流.imbue(locale("chs"));
　　不过上面这段代码只能在Windows底下用，在Linux下要受到字体配置文件的影响。
　　
2、sprintf()，将printf的结果送入字符串，用于缓冲
　　其实这个问题挺难解决的。
　　首先sprinf有缓冲区溢出的危险，snprintf没有这个危险，但是只有C99容纳了这个函数，C++03似乎没这东西。
　　[tc]的建议是用stringstream，这东西总的说来好用，就是太慢。而且大家也知道，stream基本上没有解决二进制直接访问的问题，所以对效率要求非常高的话还使用指针。
　　好在哪里呢？比如你要把一个"13.2"的字符串转换成13.2的数字，那么可以这样：
　　stringstream ss;float fnum;
　　ss<<"13.2";ss>>fnum;

3、getch()
　　读一个字符本来就不是什么难事。更何况现在一般用这个函数只为了显示一行“Press Any Key To Continue...”，如果只是这样的话，一句“system(pause");”真是又简便又清楚。缺点就是不好移植。

4、动态数组
　　老生常谈了。STL里的容器肯定比你写得好！这里就再废话几句：
　　　数据规模小选vector，使用之前记得reserve()
　　　数据规模大选list
　　　随机存取选vector
　　　用iterator遍历差不多，用vector
　　　前、后部插入首选deque、vector也快
　　　后部删除 deque、vector
　　　前部删除 deque、list
　　　中间插入 list、deque，我比较倾向list
　　　中间删除 vector、deque
　　　交换数据 vector
　　当然还有别的。
　　顺便，不要再问排序了，容器都有.sort()。

在ARM上演示uC/OS

2007-03-02T17:58:00.000+08:00

在克服了一些困难之后，终于可以在ARM上直观的表演uC/OS了。（鼓掌）

　　下面两张图是原作者《嵌入式实时操作系统uC/OS-II第2版》的第一个范例。内容是这样的：建立10个任务，随机的在屏幕上显示本任务的编号，屏幕下方提示的数据分别是：任务数（10个任务+1个监视任务+2个系统任务）、CPU占用率、任务切换情况。

　　左边这张是uC/OS移植到WindowsXP之后的效果，为了兼容原作者的代码，在控制台下显示运行结果。因为刚刚开始运行，屏幕还没有占满。
　　右边的图是今天刚刚改写好的ARM版uC/OS，为了兼容PC下的代码，把PC机上特有的函数封装一层，以“字符模式”运行。值得注意的是CPU占用率将近100%，只要把uC时钟降低，那么CPU占用率也会降低，当然如果那样做的话，ARM有很多时间是空闲的。

　　在ARM平台上，干扰因素比PC多，加上机能限制，当外部中断出现时，你会看到“任务切换次数”下降，但是并没有挂掉。据说uC/OS被验证为是一个足够稳定的系统，可以用于军事、科研、紧急事务处理（医疗救护？）等领域。当然，我认为那是建立在程序不写错的基础上，实际上[tc]的这份uC只要破坏掉看门狗的运行，系统即刻会崩溃的。

　　还需要说明的两个问题：

　　一个是，[tc]很想知道，在CPU空闲的时候，ARM能不能迅速切换到省电模式，降低功耗？问题在于，[tc]分别试验了CPU在65%和98%的两个程序，结果65%的情况下，CPU温度比较低（这项测试是根据[tc]的触觉，不知道有没有心理因素），也就是说，ARM是自动降温的CPU。然而在官方的说明文本里面似乎没有出现相关介绍。

　　另一个问题是，这个程序中，[tc]使用的是自己编写的随机函数。似乎工作的还不错\ OoO /。

　

扫除

2007-03-01T20:32:00.000+08:00

下午跑到宿舍去打扫卫生，阳台的地由于被雨水淋到，脏得够呛。好在是瓷砖地，清洗起来也容易。

3月4日就开学了，以后就算是这种水贴也只能以星期一篇了吧。不过，一想到这学期就要搬本部，我就……哈哈哈哈！

《I''s》系列

2007-03-01T11:56:00.000+08:00

漫画：周刊《少年Jump》1997～2000连载的桂正和的作品。
15卷，累计1000万册销量。
[tc]我有收藏扫描版。

OVA：2002年12月，From I''s，《另一个夏天的故事》，全2话
这是一个仅在便利店贩卖的动画，销售量上、下两集合计7万张。

　　不管从画风还是配乐上看，OVA都难上档次。而且故事内容与原作几乎没有关系，几乎像是同人作品。围绕濑户一贵、秋叶いっき、市村洋介 10年前重新见面的约定展开。和葦月伊织似乎关系不大。另外OVA还聚集了一小帮声优方面的名家。自我感觉声优方面OVA比TV更强一些。

TV：2005年，全6话+5 SP。
　　桂正和本人也参加了这次动画化，绘画水平有了质的飞跃。故事本身基本上是按照原作情节，并且把YY内容专门转移到SP中，是相当成功的手法。

{
/*--------------------------------
* 最近的动画评论真是越来越短了...
--------------------------------*/
}

tcGUI.c

2007-03-01T00:42:00.000+08:00

今天为ST2410做了一个图形库，完成了大约40%。一想到我今天的工作是八十年代的程序员经常做的事，我就 T_T

　　简单的说，这个图形库用于在没有文字显示BIOS的CPU上显示文字的。目前完成了以下工作：

英文8x12点阵的提取
宋体16x16点阵的提取（一个VB小程序），目前做了一级字库
LCD初始化（抄来的）
描点（抄来的）
描线（抄来的）
矩形（抄来的）
实心矩形（抄来的）
清屏（抄来的）
位图图片（抄来的）
英文显示
中文显示
更换颜色，前景/背景
文字透明

　　还需要加入的功能：
屏幕滚动（即翻页）
屏幕保存/恢复（用于实现双缓冲、视频缓冲、直接写屏）
绘制窗体
触摸笔（快成形了）

　　本来，[tc]以为这些代码很好找的，结果处处碰壁。在u龙那里，虽然得到一份差不多用途的东西，可惜是编译好的库文件，不提供代码。一气之下，[tc]自己写了这份代码，深感屏幕存取之效率低下，没有显卡的日子，难！

　　下面第一张图是昨天，为调试方便写的引导程序的图形界面部分。
　　第二张是刚刚实现的成果，似乎实际效果更好一些。不过我这样说也没人相信。
　　在这份成果上，只要将config.h中的#define CHINESE_SUPPORT 1去掉，就会变成第三幅图的样子，目标代码将会减小将近200K。

　　

[tc]NAND Flash BackUP 2.1

2007-02-27T01:22:00.000+08:00

继上次备份NAND Flash以来，由于Linux核心升级到2.6的缘故，[tc]决心重新写一个备份程序。这块NAND Flash型号是Samsung K9F1208U0M 64MB，和上次一样，用串口通讯。

虽说是模仿GHOST，其实没有针对文件系统，只是将Flash中的二进制数据保存下来而已。

为确保正确性，[tc]作了以下两件事：
1、设定了一个简单的信令，由计算机向开发板发送数据请求信号，保证了超时、桢同步错误可以断点续传
2、写了一个简单的MD5算法校验程序

实际情况表明，断点续传作用明显，由于种种原因，通讯有时会中断，在超时程序的帮助下，可以找回正在传输的部分，继续传输。但是，信令带来了额外的传输开销。实际的输出速度为10 KB/s，64MB的Flash共用将近2小时传输。

好在下载这些备份不需要这么慢，可以用USB接口，大约有500KB/s。

[选译]关于随机函数发生器的简单讨论

2007-02-24T00:52:00.000+08:00

（[tc]不是翻译人员，这篇包含个人感情的东西仅供参考）

　　今天有幸看到DONALD E. KNUTH先生的《THE ART OF COMPUTER PROGRAMMING》SECOND EDITION，第2卷：Seminumerical Algorithms，第1部分论述的是随机函数。揭示了[tc]几天前用到的自定义随机函数。
　　其中最简单的函数莫过于Linear Congruential Method，以下译为“线性余数法”。

　　线性余数法1949年发明于D. H. Lehmer，定义了下面的迭代函数，产生一个序列，用于简单的计算机（伪）随机序列：
　　Xn+1 = (aXn + c) mod m,n>=0
　　其中X0为“种子”。对于常数X0,a,c,m的选取，原作进行了详细的讨论，选译如下。

　　定义b=a-1
　　可证a>=2, b>=1时
　　X n+k = (a^k Xn + (a^k - l)c/b) mod m, k >= 0, n >= 0,

定理A：当且仅当m,a,c,X0满足下列条件时，具有长度为m的周期：
1、c与m为互质数
2、b=a-1是p的倍数，p为m的一切质因子
3、如果m是4的倍数，那么b也是
证明稿据说起源于100年前的定理，M.Greenberger将之推广到m=2^e。证明过程反正我也没看懂就不译了。

定理B：令λ(p^e) = (p-1) p^(e-1) , p>2
当c=0时能达到的最大周期是λ(m)。该周期满足下列条件时可以达到。
1、X0与m为互质数
2、a是模m的素元（[tc]：素元是指整环R中的非零非可逆元素。如果p能整除R中某两个元素的乘积（如ab），则必整除其中一个（如p|a或p|b））

问题在于：如何寻找模m的素元？于是：
定理C：满足下列条件之一时，数a是模p^e的素元
1、p^e=2,a为奇数；或者p^e=4,a mod 4=3；或者p^e=8,a mod 8=3,5,7；或者p=2,e>=4,a mod 8=3,5
2、p为奇数，e=1,a<>0(mod p),a^(p-1)<>1(mod p)
3、p为奇数，e>1，a满足第二条，a^(p-1)<>1(mod p^2)
正定理可用于计算机中较大的p的试验

定理D：如果m=10^e,e>=5,c=0,X0不是2或5的倍数，线性余数法周期为5*10^(e-2)。当且仅当a mod 200=下列数之一：
3,11,13,19,21,27,29,37,53,59,61,67,69,77,83,91,109,117,123,131,133,139,141,147,163,131,173,179,181,187,189,197

小结：
　　满足上述要求的a=z^k+1,2<=k<=e
　　若取c=1，则：Xn+1=((z^k+1)Xn+1)mod z^e
（[tc]：这一部分的论述，我认为原作所用的计算方法已经过时了，没有摘抄）

若设X0=0，那么再次出现0可认为是一个周期，所以有
　　Xn=((a^n-1)*c/b) mod m
并且，用二项式展开式展开a^n-1=(b+1)^n-1，化简得：
Xn=c(n+[n,2]b+...+[n,s]b^(s-1))mod m
（[tc]：其中比b^s更高阶的项由于是m的整数倍，被忽略了。式中的[n,2]是排列组合公式）。
（1）基数为1：a=1。Xn=cn(mod m)，显然不随机
（2）基数为2：Xn=cn+cb (n,2)，也不够随机。
(Xn, X(n+1), X(n+2))总是依赖于d+m,d-m,d,d-2m四个位面
（3）基数为3：序列开始比较随机，但是在Xn, X(n+1), X(n+2)中存在高阶相关性。试验表明序列效果一般
总之，基数到达5，看起来才足够随机。

　　例如：m=2^35,a=2^k+1。那么b=2^k。此时k>=18时b^2=2^(2k)是m的倍数，基数为2。如果k=17,16,...,12，基数为3。基数为4时k=11,10,9。因此k<=8，即a<=257.
稍后将会看到，小的乘积因子有可能被忽略。这样我们就排除了所有的成绩因子的取值。

　　假设w是计算机字长，m=w+1或w-1，那么基本上m不可能是质数的大的倍数，较高的基数也是不可能的。因此最大的周期是无法达到的。这就是为什么（当初会提出）c=0。
另外值得强调的是，大的基数也不是必要的。

-----------------------------------------
看到这里，来分析一下[tc]用过的随机函数。
（1）VC++（VS 2005）
　　X0=0, a=214013/(2^17)=3.266, c=2531011/(2^17)=38.620, m=0x7fff=32767
　　这个，OTL，居然是小数，不知道怎么分析。

（2）VB6
　　X0=327680, a=0x43fd43fd=1140671485, c=0xc39ec3=12820163, m=0xffffff+1=16777216
　　
应用定理A：
（1）
12820163的因子为：1, 2293, 5591, 12820163
16777216的因子为：1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216
的确互质。
（2）
1140671485-1的质因子为：2
满足条件。

应用定理B：
327680的因子为：1, 2, 4, 5, 8, 10, 16, 20, 32, 40, 64, 80, 128, 160, 256, 320, 512, 640, 1024, 1280, 2048, 2560, 4096, 5120, 8192, 10240, 16384, 20480, 32768, 40960, 65536, 81920, 163840, 327680
可见X0与m不互质，不过这个不影响。

m=2^24
p=2
e=24
1140671485 mod 8 =5
满足素元要求。

所以这组数据可以满足随机函数要求。

浏览器内嵌播放器错误（勉强解决，供参考）

2007-02-23T00:45:00.000+08:00

[tc]电脑上的浏览器最近出了奇怪的问题，访问某些包含音乐播放器的网站时会出现Windows的错误提示，并关闭浏览器。以至于[tc]自己的Blog都无法访问的严重后果。今天[tc]忍无可忍，奋战一刻钟，勉强解决问题，下面是过程。

[谁在作怪]
　　第一反应是IE不稳定，跑去从镜像里抠出以前的IE，不行。用FF2试了一下，不行。
　　第二反应是暴风影音，换了老版本（其实还不够老），不行。
　　第三反应，mpc的Bug，换了一个mpc以前的主程序，不行。又卸载暴风影音，用WMP 10居然好了！这样不算解决问题！又把暴风影音装回来（废话！当然是不一样的版本！）也OK！

[什么毛病]
　　满心欢喜。其实这是凌晨发生的事。现在是同一天的晚上，问题又来了，现象一样。
　　OK，耐下心，凌晨和现在什么区别？访问的文件不同！[tc]遂想起这一版的暴风影音有个毛病：文件格式不支持的时候会异常退出。
　　接下来的几分钟十分无聊，就不写了。

[祭出必杀]
　　[tc]的必杀技是会用调试器。于是在问题再一次发生时，用Visual Studio自带的调试器打断，发现是一处除数为零错误。
　　03DBBB98 div eax,ecx
　　此时ecx=0。经查发现03DBBB98属于SHNTrans.ax。
　　一阵google，净是些菜鸟抱怨系统不稳定的帖子，无聊。

[再靠自己]
　　把SHNTrans.ax打开一看，发现是个DLL文件。打开之，字符串列表中有一行：Shorter Compressed Audio。放到暴风影音的滤镜列表中一看，叫做SHN to wave Filter。
　　第一反应，又没有新版本？无果。
　　第二反应，不要行不行？我又不听SHN文件，这个滤镜用不上。
　　删除该文件，问题解决。

[结论]
　　DirectShow好奇怪……

欢迎来到NHK

2007-02-21T13:43:00.000+08:00

http://www.kadokawa.co.jp/hikky/

NHK=日本家里蹲协会

　　由泷本龙彦原作小说改编的漫画改编的动画，讲述大学退学的佐藤达广在学弟山崎薫的影响下成为半个Otaku，同时面对女生中原岬的故事。大体上包括相识、签约、跟踪、约会、制作、孤岛、网游（Ultimate Fantasy 诸神的黄昏）、传销、回家、绝望、结局。

　　主角佐藤君的家里蹲史n起n落，令人忍俊不禁。而所谓的“巨大组织的阴谋”、所谓的“罚款100万”（后来变成1000万、1亿万了）、所谓的Purupuru Pururin Rin，都令这部动画增色不少！薫的GAL Game（不是ACG来的吗？）相关内容，大体上也能反映一些Otaku的现状吧。不过网游受害者这个角色，似乎渲染得比较过分了，有点恐怖。~~囧~~

　　小林沙苗配音的　柏瞳（学姐），也是值得关注。中原岬再一次让[tc]深深感觉到，牧野由依的声音比较单调（跟单纯不一样），还要再努力一把！总的说来，NHK是一部成功的作品！

TrueWorld～真実のセカイ～

这个游戏，[tc]我花了一个小时来玩。OTL，剧中的设定在哪里啊～～～～

[tc]Puru Puru Rin
http://webdisk.cech.com.cn/download/file_share_2914802.html

[tc]Lost My Music

2007-02-15T23:12:00.000+08:00

受到某同人网站的一首音乐的影响，花了几个小时吧《凉宫》里的《Lost My Music》从摇滚改成现在这种风格。本来想要加大提琴再抒情一点的，时间有限，只能用钢琴独奏了。

音乐大体上可以反映[tc]的意图，但是许多细节都不尽人意。[tc]我也是工作到今天凌晨三点才搞定的。[tc]搞音乐一向虎头蛇尾，大家就忍了吧。

今天为了上传音乐化了点功夫。结果还使用了网盘。

文件在这里：
[tc]Lost My Music.mp3

两种uC线程切换不同的实现方法

2007-02-15T22:38:00.000+08:00

到底发生了什么
——两种uC线程切换不同的实现方法

一、前言
　　[tc]在VC上移植的uC/OS前些天遇到了许多奇怪的问题：不同的uC线程顺序的使用VC提供的rand()随机函数得到了相同的结果；另一方面，VC版在检查堆栈的使用情况OSTaskStkChk时，总是返回一致的结果。为什么？到底发生了什么？[tc]的移植存在问题吗？

二、两种任务切换方法
　　即将讨论的方法显然不是任务切换仅有的方法，只是[tc]只亲生经历过这两种方法。
1、法一：标准方法
　　即在任务切换时，挂起该任务（在这种方法中，CPU只有一个，实际上调度开始时只要暂停中断即可），保存所有寄存器的内容（EAX、EBX……）到该任务的ptos指示堆栈中，更新OS_TCB。
2、法二：Windows切换
　　而[tc]采用的不是上面的方法，Windows有自己的一套线程调度算法，我只是在VC上实现一些功能而以，何必认真呢？于是每当OSTaskCreate发生时，实际上是调用CreateThread来生成一个线程。与Win32程序不同的是，为了让uC来做调度，不得不挂起这些线程SuspendThread，直到调度方生时恢复之ResumeThread。

三、后果如何
　　实际的效果是，[tc]的uC更加稳定。由于用了M$的函数，可以避免Win下的复杂环境，许多操作实际上Win会帮你完成。而跟踪“标准方法”的某个程序之后，不难发现在复杂的中断发生时，该方法的uC很难保证稳定性。[tc]曾见过文佳同志的uC（我对此人并无恶意，只是就事论事），在控制台属性变化时，系统崩溃。原因大概是uC进入临界代码时无法真正的屏蔽一切中断，结果寄存器遭到修改。
　　缺点也是很明显的。由于实现方法的不同，许多行为与uC的原作者的意愿相背离了。这就是开头所述的问题的起源。

四、解释一下前言中的两个问题
1、随机函数
　　本人接触过的各种编译器所提供的随机函数使用的都是线性迭代法（这名字是[tc]瞎起的，听起来还挺专业……）。即：r(0)=种子，r(n)=(A*r(n-1)+B)/C Mod D，其中A、B、C是常数，C一般取2的幂次以回避除法，D是最大值。我猜想原作者使用的BC4.5也是这样做的。
　　随机函数不具有可重入性这是显而易见的。因此作者建议使用信号量来解决。但是遗憾的是，现在的编译器已经自带了所谓的信号量机制。比如下面是VS 2005的一段东西：
　　_ptiddata ptd = _getptd();
　　也就是说，VS会自动负责区分不同的线程。对于每个线程而言，rand函数是独立的。这就是为什么，[tc]的若干个任务（现在是Windows线程了），虽然顺序的调用随机函数，却不能达到随机的目的的原因。
　　看起来要想解决这个问题有两种方法：（1）写个线程，用来给其他线程提供随机函数（真是有病）；（2）自己写个随机函数，为了装B，可以用华丽的[tc]正态分布函数……

2、不同的线程被认为堆栈使用量相同
　　uC的计算方法大概是，循环遍历整个堆栈，找出已经使用的部分。那么不同的线程，如果算法不同，理应占用不同大小的堆栈。
　　当一个决定性的证据出现——所有线程总是只占用22个字节的堆栈——时，[tc]恍然大悟！
　　道理很简单，由于调用了CreateThread，实际上，线程的堆栈是由Windows分配的，而不是uC。那22个字节是用来保存任务特征的一个数据结构的大小。

五、后记
　　作为uC的初学者就能分析到这一步，佩服自己……

夜明け前より瑠璃色な

2007-02-15T14:48:00.000+08:00

Carillon Harmonia
Yoakena

　　“斯菲阿国”公主菲娜·法姆·阿修莱特到男主角朝雾达哉家后宫的故事。音效欠火候，没气氛，音乐还不错。故事对政治问题分析得很不严肃。以上。

凉宫春日的忧郁 TV 版 ED 舞步演示

2007-02-13T10:44:00.001+08:00

凉宫春日的忧郁 TV 版 ED 舞步演示
http://www.tg777.com/levelup/user/zwei/sos-ed.avi
谁敢不支持团长大人？

让基于uC/OS的ARM程序在VC上调试

2007-02-12T18:23:00.000+08:00

　　明眼人看标题就知道其实这是一个操作系统移植的简单问题。在不同的平台上，只要接口一致，主程序就能互相通用。

1、主题
　　ARM的调试工具已经十分强大了，但是在M$面前还是如同孩子一般幼稚。如果能在Microsoft Visual Studio 2005中建立一个通用的框架，那么ARM平台的程序就可以在x86下设计、调试。完成后拷贝到ADS中编译。

2、移植
　　当然，要让uC/OS能在VC中使用，首先需要将uC/OS移植到PC上。下面的方案我是在参考了一些代码的基础上总结出来的，难称原创，而且估计有不少错误……
　　原作者是在BC4.5上编写uC/OS的。Windows有其特殊的变成风格，比如uC的系统定时器、新进程的启动、中断的允许等问题，完全应该交由Windows完成，而进程调度还是得由uC完成。这里面的矛盾只需要让Windows产生的线程处于睡眠状态就可以轻松搞定。
　　另外中断屏蔽需要用到互斥对象（Mutex），需要时用WaitForSingleObject保持互斥状态，直到进程调度结束。
　　最不好理解的问题莫过于恢复线程状态，这个[tc]我也不是很懂，还要再研究研究。

3、框架
　　完成uC之后，需要分别为ARM和PC设定一个编程框架。[tc]选用的是昨天移植好的ARM的框架。大意如下：

（1）首先是低级初始化
[ARM]
　　还是那些老东西，恢复到“重启”状态、时钟、重入
[PC]
　　什么都不做，x86就是好啊……

（2）Console级
[ARM]
　　2410这东西不能使用stdio.h，所以把各种功能函数定义在这里。
[PC]
　　#include ，x86通用性……
　　为了让各种2410功能也能运行于PC，应该在这里设计各种各样的函数。

（3）FrameWork级
[ARM]
　　设定了分频比、初始化IRQ。但是时钟中断不要修改！初始化MMU。
[PC]
　　基本上，又是什么都不做。x86，我爱你……

（4）Application级-OSinit
[ARM]
　　创建两个基本进程。将看门狗中断定义为系统时钟OSTimeTick()（此前用的是Timer4，但是看门狗更适合。）
[PC]
　　创建两个基本线程，创建时钟线程调用OSTimeTick()，设定Windows线程优先级

　　从这里开始两个平台已经完全一样了。

4、调试
　　这件事情滞后考虑。[tc]眼下想把uC/FS搞来移植，uC/TCPIP就免了，太复杂。其实哪个文件系统已经很复杂了……

[tc]XP补丁包3、4，今日打包

2007-02-12T15:34:00.000+08:00

每年两次的[tc]对XP补丁的打包工作今天结束。此次打包的文件有以下两个：
　　[tc]XP补丁包3 2006.8-2007.1.exe
　　[tc]XP补丁包4 正版用户补丁 2005-2007.1.exe

　　从大小来看，此次的补丁包3的50 MB比以往的补丁要小一些。应该是巧合吧，每次的补丁包是一次比一次小。给人一种“XP问题越来越少”的错觉。

　　与以往不同，今天还打包了一个“包4”，这是自微软Windows Update启用正版用户验证以来，从2005年至今的，仅针对正版用户的Windows补丁。[tc]我的获得途径有两条：一是其它网站，二是某些网站公布的微软网站实际的下载地址（即绕过了正版验证）。

　　不过这些“正版补丁”也大都是一些无关紧要的东西，比如：某国家自某日起时钟改为夏令计时、Windows某软件新增了几个小功能（比如msconfig新增了一页、远程桌面连接增加了身份验证）、AMD双核需要一些补丁修正电源效率问题等等。不装也罢。

　　需要补丁的小朋友发邮件。

现视研相关

2007-02-12T14:03:00.000+08:00

-1签-
现视研
第一季动画一共12集
漫画一共八卷共50话

　　现视研（げんしけん）＝现代视觉文化研究会

　　笹原完士在进入大学之后，致力于理解“漫画·动画·游戏”的新体验。于是认识了包括高坂真琴在内的一票Otaku，自己也朝这个道路前进。另一方面出现在现视研的一直恋慕着高坂的春日部咲和cosplay的大野等各种人也以现视研为舞台展开了许多有趣的生活。
　　木尾士目原作的漫画，描写大学生御宅族生活的《现视研》，一开播反响就很大，今天看到这部作品，果然非常有趣，每一集（特别是接近尾声的时候）等能引人大笑一阵。虽然[tc]不是Otaku，但是似乎能从剧情中找到自己的影子。

-2签-
不公正抽签
OVA 3话

　　除了现视研出现的一些镜头以外，不用问还有其他内容。回过头来看，《现视研》中对《不签》的评论可以说十分到位了。几乎可以说，由于有现视研的评论在先，《不签》才显得格外出色，几乎成为完美的特别适合Otaku看的动画。
　　不同于一般的校园恋爱、恶搞动画，《不签》的全部内容都是围绕“对决”展开的（照理说是指对候补学生会的认同仪式），剧中，蘑菇料理对决、网页点击对决、在三温热里冷得不能再冷的笑话、诱惑的军训、全世界都要崩溃的卡拉OK、拖延时间的外星人游泳（务必请与TV版的外星人联系起来看！）、高度运气的麻将、可以通PHS电话的骷髅地下室。无一不堪称经典!

-3签-
不公正抽签
TV 12话

　　TV版讲述的是千寻一行人从抽签入学到当上次界立桥院学生会的过程。不过改变了“原作”的不少设定。比如把夏本千寻设定为缺钙正太会长（应该是书记），秋山时乃变成了青梅竹马的副会长（应该是会长），律子变成某丰满女（CV居然是小清水亚美，汗）。唯一值得期待的罗莉会计朝雾小雪是个超能力人（应该是会计的浩浩闹闹的一家子中最小的一个），她姐，眼睛女朝雾忍，人如其名，是个忍者（应该是朝雾小牧，会计）、橘泉美　是个反叛的R3S学生会暴力部门领导者（原作是副会长），上石神井莲子原作是一个半路冒出来的大嘴女、现在居然是书记……这个世界是不真实的。T_T
　　这次的人物关系变换，以时尚动画来说的确更适合一些，不过以Otaku的眼光恐怕并不是这样认同的。
　　另外，上届学生会副会长如月香橙的CV是野上ゆかな，泰莎的配音。[tc]一直到最后一集才听出来，失败。
　　从画风角度上说，TV版不如OVA这么卡哇，而且人物经常变型。虽然制作上不受[tc]认同，但是常常在瞬间中产生的暴笑镜头，还是能让本人狂笑不止。特别是外星人的相关内容……

-4签-
现视研2
？？？
　　虽然《现视研2》似乎是理所当然应该出现的，不过制作计划却夭折了。可惜！

μｃ/ＯＳ-II在S3C2410上的移植小记

2007-02-11T20:18:00.000+08:00

μｃ/ＯＳ（下称“uC/OS”）是完成可以进程调度的可剥夺式操作系统。在经历了40小时之后终于能在本人的ST2410上运行了。然而此次移植的主要贡献仍然是uC/OS的原作者：Michael Anburaj。而[tc]由于智商方面的原因只完成了一些简单的工作。

　　uC/OS移植的要点，在[tc]看来主要是两方面：
1、编写任务切换程序
2、实现系统Tick（这是实现可剥夺的关键）

　　前者很简单，备份当前程序的状态，取回下一任务的状态即可。后者主要是利用定时中断的4号定时器完成。4号定时器是一个内部定时器，从200MHz时钟4分频后（分频比应该在初始化系统时间时设定PLL），经过预分频、分频得到适当的定时长度，然后指定pISR_TIMER4的指针，运行服务程序，最终调用OSTimeTick()，就完成了一次调度过程
。
　　这个看似简单的过程实际实施起来却异常艰难。
　　首先，使用定时中断需要MMU帮忙，然而[tc]配的MMU单独运行时没问题，使用定时中断也没问题，但是加上uC就不能工作。
　　其次，初始化程序不大稳定，有时不硬件复位就会自动软复位。
　　总之，[tc]智商不够，最后用了官方的SMDK2410的演示程序为样本，适当修改，这才得以工作。

　　接下来还要调试uC/OS的其它功能，如消息队列、进程同步、死锁、邮箱等等。而进一步的要求，如文件系统、TCPIP等，看来只能等到开学以后了。
　　累！

RightMark CPU Clock Utility

2007-02-09T20:42:00.000+08:00

　　今天发现一款不错的CPU超/降频软件：RightMark CPU Clock Utility。
　　此前还见过一款界面不错的软件：Notebook Hardware Control（也是非常优秀的！），只是那款的未注册版本限制比较多。

　　该软件主要实现按照不同的策略设置CPU频率。如图所示，设置为“最大性能”时，CPU工作在200M X 10 = 2GHz下，而“省电”模式下工作在800MHz下，温度是23摄氏度，按照[tc]在主板BIOS中的设定，风扇停转，十分安静（[tc]的电源风扇也是静音的）！
　　之所以能发现这款软件，完全是因为Gigabyte附送的调整软件不好用，[tc]差一点自己写这样的软件的说。

一个不错的模拟低通滤波器

2007-02-07T12:54:00.000+08:00

对于用模拟电路实现比较理想的低通滤波，[tc]一直以为是非常困难的。相比之下，高通似乎比较容易。中午的时候无聊，居然人品爆发，实现了一个不错的低通滤波器，遂拿出来秀秀。

下面是模型。

忘却的旋律

2007-02-06T22:17:00.000+08:00

The Melody Of Oblivion
GAINAX J.C.STAFF 2004
www.tbs.co.jp/boukyaku/
TV 23话

　　20世纪人类和Monster（怪物）之间发生了一场很大的战争，以Monster一方的胜利告终。新世纪，人们忘记了旋律。直到博卡遇见了黑船先生，成为旋律战士，开始了一场“寻找传说中的女神”的旅途。全篇除了一头一尾以外，以地点为分界线，分为　白夜岬、鼠讲谷、猿人湾、迷宫岛、幸运河、东京站、圈外圈　等数篇。博卡和小夜子……算是在旅行的吧，每到一处，博卡就放不下那里的居民，在一句“燃烧吧，我的小宇宙”式的“奏响吧，我的旋律”之后，在居民的唾骂声中离开。与《翼·年代记》的回娘家型不同，《忘》是打怪练级型。

　　GAINAX负责的这部TV动画的制作，制作人员包括了贞本义行。声优阵容也是一如既往的豪华。Bocca·Selenady：桑岛法子、月之森小夜子：浅野真澄、忘却的旋律：能登麻美子、远音：小林沙苗、スカイブルー：保志总一朗、ホル：森久保祥太郎。非常吸引[tc]的眼球。

　　制作上看，除了个别明显偷工减料的镜头以外，着色艳丽，叙事完整。适当的时候，对人类趋向软弱的本能做出了深刻的反省。而故事的设定决定了不少英雄的无奈的悲剧的循环。恶魔与人类的矛盾、人类不同国家意识的不同步、人类短浅的目光，在动画中一一展现，十分有趣。

　　奇怪的是，这一部内涵严肃的作品，到了尾声《圈外圈》篇时，出现了大量OTL画面设计，令人哭笑不得的舞台剧、时不时插进来的奶牛牧场、怪物联盟成员矫揉造作的表演，着实令《忘》增添了几分恶搞的色彩！

《[tc]魔兽3 1.21内存修改器》V3

2007-02-05T00:30:00.001+08:00

前几天才完成的修改器，今天发现已经有1.21的补丁了，先前的修改不能再用，需要更新。

好在基本的代码不用动，因此花了两个小时来改程序。

还是老样子，改英雄的经验、三围、攻速、移动这几项。突然发现钱、木等也是可以改的（怎么才发现……），不过操作起来比较麻烦，我就不写了。

要修改器的同志发邮件。

《[tc]魔兽3 1.20内存修改器》V2版

2007-01-31T23:18:00.000+08:00

　　半年前[tc]编写这个内存修改器的时候曾经遇到过一个重大问题，昨晚重新翻看的时候，人品爆发，找到了一个可称为“无奈之举”的方案，今天就写了出来。

[问题何在]
　　此前修改英雄属性的时候，力量、敏捷这两项属性代码十分简易，譬如下面是读取敏捷数据的代码：

　　6F13CE7B:
　　8b be a8 00 00 00 mov edi,[esi+000000a8]

　　然而“智力”却十分难修改，关键性代码有多处，其中最显眼的一处是：

　　6F088E78:
　　8b 42 78 mov eax,[edx+78]

　　可是不幸的是，这段代码并不仅仅是读取智力的，它似乎是一个函数，将一些离散的数据从堆地址传送到临时地址。因此，虽然这里面包含了我们想要修改的内容，但同时包含了许多其他内容。
　　另一方面，力量、敏捷、智力这三项属性，在内存分配上可谓是毫无联系，应该是动态分配得到的，实际游戏中无法从其中一个地址判断出其他的地址。

[人品爆发]
　　从大量的数据中滤出所需的“智力”地址，是解决问题的方案之一。
　　昨晚发现，在有限的时间里，经过6F088E78的代码的eax的取值是十分有限的一些数据，而不是任意多个数据。进一步观察发现，在这些数据中，智力的地址竟然是eax的最大值！
　　这一惊人的发现，促使下面的方案的形成。

[无奈之举]

　　嵌入的代码，不用问，和其他的代码是不同的。以往获取力量等属性的时候，一般是将寄存器的内容转移到内存里，以便查阅。而智力这一属性的地址，是“经过6F088E78代码处的eax的值”中的最大值，因此需要挑出最大的一个。
　　例如，针对上面的例子，获得敏捷的地址，可以嵌入下面的代码：

　　89 35 08 10 46 00 mov [00461008],esi

　　那么esi的内容将被转移到00461008处，此后只要查阅[[00461008]+a8]，就可以得到并修改敏捷的值。
　　而针对智力，嵌入下面的代码：

　　39 15 14 10 46 00 cmp [00461014],edx
　　77 06 ja 00449E2E goto L1>
　　89 15 14 10 46 00 mov [00461014],edx save>
　　
　　<原来的代码>

　　那么edx的最大值将被转移到00461014中，在适当的时候取出[[00461014]+78]就可以获得并修改智力值了！
　　接下来的问题：什么是“适当的时候”呢？
　　[tc]无法给出准确的答案，目前的解决方案是：在敏捷获得后的3秒钟时间内获得的数据都是准确有效的数据。为什么安排在敏捷获得之后？主要原因是魔兽3经常运行6F088E78（智力）这里的代码，而不会运行6F13CE7B（敏捷）这里的代码，因此基本上只有运行了敏捷的读取程序才有可能运行智力的读取程序。
　　这种盲目性决定了本方案是一个“无奈之举”的方案。

[程序现状]
　　大体上程序就这么定型了。目前的修改器可以实时修改指定英雄的经验值、力量、敏捷、智力、移动速度、攻击频率等属性。事实上，[tc]还可以实现攻击力、防御力、攻击类型（如混乱、穿刺等）、防御类型（如城甲、英雄甲等）等属性，不过意义不大，[tc]没有编写程序。

结果跑到Blogger来了！

2007-01-30T22:46:00.000+08:00

似乎半个星期前还在Wallop.com转悠，现在就跑到这里来了。作为老一届MyWallop用户，不得不说：微软没能留住人啊！

　　先把昨天的东西贴过来，然后再慢慢打理这里好了！还是那些内容：编程（现在包括嵌入式了）成果、动漫评论、摄影心得等等。

　　化腐朽为绵掌，这里是绵掌集散地！

无敌看版娘

2007-01-29T21:30:00.000+08:00

无敌看版娘
TV 6话

　　高攻无脑型暴力女鬼丸美辉是一个在鬼丸中华料理小店里长大的家伙。不过姑且招牌女服务员。打工期间分神翘班、与周围人打打杀杀是家常便饭。不知道是在店里帮忙还是在帮倒忙。好在在这个世界中，最强人士其实是鬼丸真纪子，美辉的妈妈，能够毫不费力地把美辉按倒，大概她才是支撑这个店的人。
　　小清水亜美　一改以往的角色风格，此次饰演的　神无月めぐみ，是对面面包店的招牌女服务员。表面看起来很可爱，其实性格阴险。由于体质问题根本不是美辉的对手，但是一直坚持着对抗。至于隔壁蔬菜店工作的太田明彦、每天都来挑战的西山勘九郎、只有在吃拉面时才笑的茅原智香，也为这部动画增色颇多。另外，动画中还有一只所向无敌的狗敏行，据说和美辉有同样程度的战斗能力——当然，在真纪子的面前还是毫无办法的。
　　到底是《周刊少年冠军》上获得巨大支持的新系列连载作品，《无敌看板娘》在2006年7月放送时反响似乎也是不错。漫画家　佐渡川准　在秋田书店《周刊少年CHAMPION》上连载至第16卷，还依然绝赞、恶搞连续不断。所以虽然整部动画都充斥着打斗场面（还称不上暴力），不过仍然是一部值得拿来消遣的优秀动画作品！

怎样显示一个整数

2006-02-14T07:58:00.000+08:00

原贴：http://tctianchi.yo2.cn/articles/integer.html

在这个汇编也能调用wprintf的时代讨论这个问题是不是太过时了？如果变量a中保存有十六进制数0FFF FFFF，无论是printf("%d",a);、Print a、writeln(a);，还是echo a;、Response.Write(a)，都能显示它的十进制版本。

将寄存器中的数H:L转化为十进制数显示在屏幕上的过程可归约为以下迭代过程：
1、该十进制数的末位是H:L除以10的余数
2、该十进制数的其余各位是H:L除以10的商形成的新数，应用第1-2条所述规则的结果，直到新数为0
但是仔细想想却不是这样简单的。div指令规定：保存在DX:AX中的32位整数除以16位整数时，商将保存在AX余数在DX。因此如果除数为10，被除数大于9FFFF的话，将发生除法溢出。

研究发现，上面的迭代过程可简化为：
[结论]
1、设x为32位整数，其高位为H除以10的模，低位为L
2、该十进制数的末位是x除以10的余数
3、该十进制数的其余各位是新数y，应用第1-4条所述规则的结果，直到y为0
4、新数y为32位整数，高位为H除以10的商，低位为x除以10的商

[证明]
以下符号中，\为整除，Mod为求模，^为求幂。设H、L为16位整数，S=16^4=2^16。
则H:L=H*S+L，x Mod y = x - (x \ y) * y。
还可推知：x \ y = (x - x Mod y) / y。
性质1：a \ b \ c = a \ c \ b = a \ (b * c)，即整除具有交换率和结合率，但没有分配率。需要分配时，应转换为除法。
性质2：(a + b) Mod c = ((a Mod c) + (b Mod c)) Mod c，证明略。

结论2的证明：(H * S + L) Mod 10 = ((H Mod 10) * S + L) Mod 10
((H Mod 10) * S + L) Mod 10
= ((H - (H \ 10) * 10) * S + L) Mod 10
= ((H * S + L) Mod 10 - ((H \ 10) * 10 * S) Mod 10) Mod 10
∵(H \ 10) * 10 * S) Mod 10
= (H \ 10) * S * 10) Mod 10
= 0
∴原式
= ((H * S + L) Mod 10) Mod 10
= (H * S + L) Mod 10

结论4的证明：(H * S + L) \ 10 = ((H Mod 10) * S + L) \ 10
(H * S + L) \ 10
重新分配高、低16位
= S * ( _
((H * S + L) \ 10) \ S _
) + ( _
((H * S + L) \ 10) Mod S _
)
其中高位 ((H * S + L) \ 10) \ S
= (H * S + L) \ S \ 10
= H \ 10
其中低位 ((H * S + L) \ 10) Mod S
= (H * S + L) \ 10 - (H * S + L) \ 10 \ S * S
= (H * S + L) \ 10 - H \ 10 * S
= (H * S + L - (H * S + L) Mod 10) / 10 - (H - H Mod 10) / 10 * S
= (L - (H * S + L) Mod 10 + (H Mod 10) * S) / 10
∵(H * S + L) Mod 10 = ((H Mod 10) * S + L) Mod 10 ( 结论2 )
∴原式
= ((H Mod 10) * S + L - ((H Mod 10) * S + L) Mod 10) / 10
= ((H Mod 10) * S + L) \ 10
证毕。

; 显示DX:AX中的有符号长整数,
; 转换后的字符串保存在[BX]中
; [tc]天驰2006.2......

;显示整数
TCPRINTCLNG PROC NEAR
PUSH AX
PUSH BX
PUSH CX
PUSH DX
PUSH SI

XOR CX,CX ; CX是计数器
MOV SI,10D
MOV DI,BX
ADD DI,11D

MOV BX,DX
OR BX,BX
; 测负数
JNS TCPRINTLNGLABELCOVERTPRE
NEG BX
NEG AX
SBB BX,+00
CALL TCPRINTLNGLABELCOVERT
DEC DI
; 加一个'-'
MOV BYTE PTR [DI],2DH
INC CX
JMP TCPRINTLNGLABELOUT

TCPRINTLNGLABELCOVERTPRE:
CALL TCPRINTLNGLABELCOVERT
JMP TCPRINTLNGLABELOUT

TCPRINTLNGLABELCOVERT: ; 转换
XOR DX,DX
XCHG BX,AX
DIV SI ; 高位除法
XCHG BX,AX
DIV SI ; 低位除法
ADD DL,30H
CMP DL,3AH ; 个位比'9'大
JB TCPRINTLNGLABELHEX
ADD DL,07H ; 就变成'A'

TCPRINTLNGLABELHEX:
INC CX ; 得到位数
; 保存
DEC DI
MOV BYTE PTR [DI],DL
MOV DX,AX
OR DX,BX
JNZ TCPRINTLNGLABELCOVERTRET

; 正式显示，CX是个数
TCPRINTLNGLABELOUT:
MOV DL,[DI]
INC DI
MOV AH,02H
INT 21H
LOOP TCPRINTLNGLABELOUT

MOV DL,13D ;回车1个
MOV AX,0200H
INT 21H
MOV DL,10D
MOV AX,0200H
INT 21H

POP SI
POP DX
POP CX
POP BX
POP AX
RET

TCPRINTCLNG ENDP

这么冗长的代码本来不想贴的，真的。但我为了这个问题思考了一个晚上，不能白费啊。

这种六七十年代就可能被发明的东西，为什么一直没有人记录下来呢？害得我自己伤脑细胞。