Vapor successfully bootstrapped.

Today is the big day for my tiny compiler project - Aqua virtual machine and Vapor programming language.

Building a Red Power Operating System Episode 1: Hello World

Hi everyone. This is a blog for recording all my personal technical stuff. This time, I'm working on the creation of a fully-featured operating system named WishOS for computers in RedPower 2 (a mod for MineCraft). I will continually write small episodes to record my progress onto this project. Once finished, this would become a hacking tutorial for everyone.

To start my work, I have done some research for redpower computers. Basically these computers have a microcontroller derived from the 6502 (the one in Commodore 64!). Although it emulates nearly a fully functional hardware, it lacks good software support. The original bundled operating system, MineOS, has only a FORTH compiler and nothing else. Despite the poor functionality of FORTH, since the system has only a compiler, the code of a program cannot be viewed or changed once it's entered into the system. It has nothing for file systems, either.

So it is obvious I need start building a temporary toolchain for bootstrapping my final system. The temporary toolchain contains only a text editor and a compiler. I will use the text editor to edit system code, and the compiler to make the bootable floppy disk. The binary always starts from the 0 sector. The code will be placed at a fixed starting sector. This design eliminates the need for file systems.

In this episode, I'm going to write a FORTH program which builds a bootable floppy disk, which just prints the legendary "Hello World!" text when being booted.

Firstly we need to understand the way redpower computer boots. The BIOS code can be found at http://integratedredstone.wikispaces.com/RedPower+Control and I will not duplicate the words. The BIOS basically reads floppy disk sectors and put them into memory address at 0x0500.

When looking at the wiki page, you may have noticed the term "emulation mode". This is a mode used by the 65C816 processor (a 16-bit processor) to behave as the 8-bit processor 6502 for providing backwards compatibility. The RedPower CPU is actually a combination of 6502, 65C02 and 65C816 with custom modifications, so it comes with the emulation mode, too. The key point here is that emulation mode makes it possible that you can switch the registers and memory accesses between 8-bit and 16-bit.

Then I just start building the code. I need a basic buffer management utility to manage compiled code buffer.

VARIABLE buf
16384 ALLOT buf !
VARIABLE pos

: CLR
buf @ pos ! ;

: WB
pos @ !
pos @ 1 + pos !
;

: WD
pos @ !
pos @ 2 + pos !
;

Then I have to write instruction emitters for every instruction I'd like to use. To avoid useless work, I wrote the hello world program in assembly at this time point to check what instructions are needed.

0500 18         CLC             ; clear carry
0501 FB         XCE             ; set native mode
0502 C2 30      REP #$30        ; use 16-bit registers

0504 A9 01 00   LDA #$1         ; default id of monitor
0507 EF 00      MMU #$0         ; set redbus
0509 A9 00 03   LDA #$300
050C EF 01      MMU #$1         ; set redbus memory mapping
050E EF 02      MMU #$2         ; enable redbus

0510 A9 01 00   LDA #$1         ; row 1
0513 8D 00 03   STA $300

0516 E2 30      SEP #$30        ; use 8-bit registers
0518 A2 00      LDX #$0         ; loop variable

loop:
051A BD 40 05   LDA $540, X     ; load current character
051D C9 00      CMP #$00        ; zero-terminated string
051F F0 07      BEQ final
0521 9D 10 03   STA $310, X     ; save current character to screen buffer
0524 E8         INX
0525 4C 1A 05   JMP loop

final:
0528 4C 28 05   JMP final       ; dead loop

0540 48 65 6C   "Hello World!", $00
     6C 6F 20
     57 6F 72
     6C 64 21
     00

Now I can define useful instruction emitters. I quickly recognized some instructions have more than one address modes (see http://www.obelisk.demon.co.uk/6502/addressing.html for explanation for each address mode), to distinguish between them, I added suffixes to instruction names.

Suffixes	Address Mode	Example
No suffixes	Direct absolute/relative address, or instructions having only one address mode	LDA $33
I	Immediate value	LDA #128
X	Absolute address + X	LDA $100, X
Y	Absolute address + Y	LDA $100, Y
ID	Indirect	JMP ($200)
IX	Indexed indirect (X)	LDA ($100, X)
IY	Indirect indexed (Y)	LDA ($100), Y
Z	Zero page	LDA $FF
ZX	Zero page + X	LDA $FF, X
ZY	Zero page + Y	LDA $FF, Y
8	8 bit form	See below

The last one is a special suffix which can be appended to all above suffixes to indicate the 8-bit form of that instruction. (By default 16-bit forms of instructions are used.)

After all these preparations, it is now easy to program the instruction emitters. (Remember to run HEX to enter hexadecimal number mode.)

: CLC 18 WB ;
: XCE FB WB ;
: REP C2 WB WB ;
: SEP E2 WB WB ;
: MMU EF WB WB ;
: LDAI A9 WB WD ;
: STA 8D WB WD ;
: LDXI8 A2 WB WB ;
: LDAX BD WB WD ;
: STAX 9D WB WD ;
: CMPI8 C9 WB WB ;
: BEQ F0 WB WB ; (Relative addresses are always 8 bit)
: INX E8 WB ;
: JMP 4C WB WD ;

Lastly we define a helper function to move buffer pointer to a fixed position:

: ORG 500 - buf @ + pos ! ;

We are almost there. Let's assemble the final hello world code.

CLR

CLC
XCE
30 REP
1 LDAI
0 MMU
300 LDAI
1 MMU
2 MMU

1 LDAI
300 STA

30 SEP
0 LDXI8

540 LDAX
0 CMPI8
7 BEQ
310 STAX
INX
51A JMP

528 JMP

540 ORG
48 WB
65 WB
6C WB
6C WB
6F WB
20 WB
57 WB
6F WB
72 WB
6C WB
64 WB
21 WB
0 WB

Our program is done. Try to "burn" it into the floppy disk:

buf @ 0 DISKWS
DISKNAME" Hello"

Insert this disk to another computer and boots it, you will finally see "Hello World!" on the screen:

Enjoy our first bootable floppy!

此博客重新启用，当作笔记本用好了

博客拿来当记事本记录东西也是很不错的。

最近对MineCraft中RedPower2 的Computer产生兴趣。

准备开始写OS及ToolChain，遂开始撰文记录过程。

因主要打算跟老外交流，会采用英文书写。当然如果出现插楼的话就不一定了……

最后，希望这个项目不要再被我坑掉……

APIO'09 归来

嗯，200分压线金牌。第二题输出没排序，就把本来的28分骗分送人了。不过貌似所有200分的第二题都是0，所以也没什么遗憾了。

zouxun考的很囧，第一题用了一种比我麻烦的代码搞了200多行结果WA不少，只得了65分，最后获得银牌，不免有些郁闷。

不过最终大家玩得还是很开心的。

这几天还是抽空写写总结。先把那个 A* 的小结写完，再把答应的某模拟赛题目出出来，最后再写个 APIO'09 总结。嗯，过两天回家再把 APIO'09 的题目加到 RQNOJ 上吧，第二题还是很不错的。第一题和第三题对基本功的考察也还是很不错的。

就写这么多。

A*算法浅谈(60% finished)

嗯，答应的事情的确有太多没有做好，现在就一点一点去补偿吧。

A*可以看成BFS的加强版，或者说BFS就是A*的特殊情况。这里我们在BFS的基础上来逐步介绍A*。我们只考虑路经寻找问题，即寻找从初始状态到目标状态的一条最短路径。我们定义 D[u] 为初始状态到状态 u 的最短路径长度，w[u, v] 为状态 u 到状态 v 的路径长度。

首先我们回顾BFS的过程，我们需要一个队列 queue 保存待扩展节点，一个 hash 表保存待扩展和已经扩展的节点，BFS 过程可以表示如下：

1. 将初始状态加入 queue 和 hash 中
2. while (queue 非空)
3.　　 取出 queue 尾状态 u
4.　　 若 u 是目标状态，则 D[u] 为答案，结束算法
5.　　 枚举每个从状态 u 出发可以到达的状态 v
6.　　　　 若从 D[u] + w[u, v] < D[v] 则
7.　　　　　　更新 D[v] = D[u] + w[u, v]
8.　　　　　　　 若 v 不再 hash 中
9.　　　　　　　　　 v 入队并加入 hash
10.　　不存在所需的路径

不难发现，这个过程与 SPFA 很像。

但是这个算法的效率是很低的，特别对于很多状态空间是无限的问题，BFS可能会迟迟找不到解。究其原因，我们发现，BFS过程完全是按照入队列的顺序扩展状态的，也就是说，如果把状态空间看作一个层次图，BFS 每次只遍历这个层次图的一层，然而每个层次中的大部分状态都是没有用的，可不可以不要去碰这些状态呢？另一方面，对于一些特定的问题，从某个状态出发，往往很容易看出一些后继状态是明显没有“前途”的，那么能不能尽量把这些状态延迟取出，以便加速求解（目标状态可能在这些状态开始扩展之前就到达了，这样就省去了扩展这些节点的操作）？

综合以上两种思路，我们考虑为每个状态 u 设计一个函数 h[u]（通常叫做这个算法的启发函数），表示我们估计从 u 状态到目标状态的最短路径还有多长，设 h*[u] 表示 u 到目标状态的实际最短路径常数。如果我们能直接计算出任意的 h[u]=h*[u]，那么 h[初始状态]=h*[初始状态] 就是答案。但这在大部分的问题中都很难做到。于是我们考虑改进 BFS，每次扩展 h 值最小的状态。但是思考之后可以发现这显然是错的，因为大体上来说一个对于任意一个状态 u 的后继状态 v，一般有 h[u] > h[v]，这样算法就很可能朝着一条路径一直搜索下去，即使找到了目标状态也还是不能保证解的最优性。所以我们考虑“经过状态 u 的最短路径的估计函数”f[u]（同上设最短路径长度的实际值为 f*[u]）。设 g[u]=g*[u] 表示从初始状态到状态 u 的最短路径长度，这可以准确得出，则有：f[u] = g[u] + h[u]。于是算法改为：每次扩展 f 值最小的状态。

但是我们又发现，这样仍然不能保证获得最优解，由于对 h* 估计的不确定性，仍然不能保证第一次找到目标状态时的路径就是最短路径（因为最短路径上的某个状态 u 可能由于错误估计的较大 f[u](h[u]) 值而迟迟得不到扩展），于是我们需要对 h 函数加一些限制，使它能更客观真实地反映一个状态的优劣程度。我们要求对任意状态 u，h[u] 必须满足 h[u] <= h*[u]，即 h[u] 是最短路径的下界。

乍一看找不到反例了，但是这种算法的确能保证第一次遇到的解是最优解吗？答案是肯定的，这种算法正是大名鼎鼎的 A* 算法。首先我们将整个算法流程重新描述如下：

算法正确性的证明分为两步（我的数学很烂，不很会严格证明，大家如果想看严格证明可以自己尝试或者参考《人工智能导论》中的相关章节）：

定理 1. 如果存在一条从初始状态到目标状态的路径，A* 算法一定可以找到这条路径。

说明：容易看出，A* 算法退化到极致之后就是朴素的 BFS，所以只要 BFS 可以找到解，A* 就一定可以找到解（当然，这种证明对于状态空间是无限的问题来说还是有些牵强，不过勉强还能说得过去吧）。

定理 2. 设最优解为 F*。A* 算法未完成时，队列 queue 中一定存在 F[u] <= F* 的状态 u。

说明：在一条最短路径（s、v₁、v₂、……、v_k、t）上的状态 u 显然满足：

f[u] = g[u] + h[u] <= g*[u] + h*[u] = f*[u] = F*

即 u 的估计价值 f[u] 不超过 F*。所以若 A* 算法未完成，则最短路径上的状态就没有全部被扩展，所以一定在这样的状态 u。

定理 3. A* 算法找到的解一定是最优解。

说明：首先根据定理 1，A* 算法一定可以找到解。又根据定理 2，只要 A* 算法未完成，总有 f[u] <= F* 的状态 u，所以 A* 算法每次扩展的状态 u 总有 f[u] <= F*，因而扩展到目标状态时，仍然有 f[t] <= F*，而 F* 为最优解，既有 f[t] = F*，定理得证。

8数码 A*

终于初步学会了A*，也把这个一直留着的8数码AC掉了。
A*的速度的确很快很强大。。。写得这么丑的代码都那么快。。。

PS：我用的启发函数是每个数字当前位置到目标位置的曼哈顿距离之和。

过两天有空写个 A* 的详细解释，也算对这几天研究的一个总结。

program number8;
const
　maxState = 100000;
　Mask: array [0..9] of Longint = (1000000000, 100000000, 10000000, 1000000, 100000, 10000, 1000, 100, 10, 1);
　Ori: array [1..8, 1..2] of Longint = ((1, 1), (1, 2), (1, 3), (2, 3), (3, 3), (3, 2), (3, 1), (2, 1));

type
　TOpenState = record
　　P, F, G: Longint
　end;
　
　TClosedState = record
　　State, P: Longint
　end;

var
　State: array [1..3, 1..3] of Longint;
　i, j: Longint;
　a, b: Longint;
　OpenCount, CloseCount: Longint;
　Open: array [1..maxState] of TOpenState;
　Closed: array [1..maxState] of TClosedState;
　Current, CurrentG: Longint;
　
procedure Swap(a, b: Longint);
var
　T: TOpenState;
　
begin
　T := Open[a];
　Open[a] := Open[b];
　Open[b] := T;
　Closed[Open[a].P].P := a;
　Closed[Open[b].P].P := b
end;

procedure Decrease_Key(t, dstF, dstG: Longint);
var
　u: Longint;
　
begin
　u := t;
　Open[u].F := dstF;
　Open[u].G := dstG;
　while (u > 1) and (Open[u div 2].F > Open[u].F) do
　　begin
　　　Swap(u, u div 2);
　　　u := u div 2
　　end
end;

function Extract_Min: Longint;
var
　u: Longint;
　
begin
　Closed[Open[1].P].P := 0;
　Current := Closed[Open[1].P].State;
　Extract_Min := Open[1].G;
　Open[1] := Open[OpenCount];
　dec(OpenCount);
　u := 1;
　while True do
　　if (u * 2 <= OpenCount) and (Open[u * 2].F < Open[u].F) then
　　　begin
　　　　Swap(u, u * 2);
　　　　u := u * 2
　　　end
　　else if (u * 2 + 1 <= OpenCount) and (Open[u * 2 + 1].F < Open[u].F) then
　　　begin
　　　　Swap(u, u * 2 + 1);
　　　　u := u * 2 + 1
　　　end
　　else
　　　break
end;

function CalculateH: Longint;
var
　i, j: Longint;
　
begin
　CalculateH := 0;
　for i := 1 to 3 do
　　for j := 1 to 3 do
　　　if State[i, j] <> 0 then
　　　　inc(CalculateH, abs(i - Ori[State[i, j], 1]) + abs(j - Ori[State[i, j], 2]))
end;

procedure Expand(a, b, da, db: Longint);
var
　i, j: Longint;
　NowF, NowState: Longint;
　Flag: Boolean;
　
begin
　State[a, b] := State[da, db];
　State[da, db] := 0;
　Flag := False;
　NowState := 0;
　for i := 1 to 3 do
　　for j := 1 to 3 do
　　　inc(NowState, State[i, j] * Mask[(i - 1) * 3 + j]);
　NowF := CurrentG + 1 + CalculateH;
　for i := 1 to CloseCount do
　　if Closed[i].State = NowState then
　　　begin
　　　　Flag := True;
　　　　if (Closed[i].P <> 0) and (NowF <= Open[Closed[i].P].F) then
　　　　　Decrease_Key(Closed[i].P, NowF, CurrentG + 1)
　　　end;
　if not Flag then
　　begin
　　　inc(CloseCount);
　　　inc(OpenCount);
　　　Closed[CloseCount].State := NowState;
　　　Closed[CloseCount].P := OpenCount;
　　　Open[OpenCount].P := CloseCount;
　　　Open[OpenCount].F := MaxLongint;
　　　Decrease_Key(OpenCount, NowF, CurrentG + 1)
　　end;
　State[da, db] := State[a, b];
　State[a, b] := 0
end;

begin
　fillchar(Open, sizeof(Open), 0);
　fillchar(Closed, sizeof(Closed), 0);
　OpenCount := 1;
　CloseCount := 1;
　readln(Closed[1].State);
　Closed[1].P := 1;
　Open[1].G := 0;
　Open[1].P := 1;
　while OpenCount > 0 do
　　begin
　　　CurrentG := Extract_Min;
　　　if Current = 123804765 then
　　　　begin
　　　　　writeln(CurrentG);
　　　　　halt
　　　　end;
　　　for i := 1 to 3 do
　　　　for j := 1 to 3 do
　　　　　begin
　　　　　　State[i, j] := Current mod Mask[(i - 1) * 3 + j - 1] div Mask[(i - 1) * 3 + j];
　　　　　　if State[i, j] = 0 then
　　　　　　　begin
　　　　　　　　a := i;
　　　　　　　　b := j
　　　　　　　end
　　　　　end;
　　　if a > 1 then
　　　　Expand(a, b, a - 1, b);
　　　if a < 3 then
　　　　Expand(a, b, a + 1, b);
　　　if b > 1 then
　　　　Expand(a, b, a, b - 1);
　　　if b < 3 then
　　　　Expand(a, b, a, b + 1)
　　end
end.

省选归来,一切正常,期待APIO'09

省选归来已经是一个星期之前的事情了，考的分数还是很让人郁闷的：不过半的280分。有的时候别人问我靠怎么样，我还可以炫耀一下：与第一名只差20分。殊不知，我与第三名只差10分。- -||

今年是我OI生涯最后一年了（如果拿不到金牌的话……）。所谓成也OI，败也OI。期望越大，失望越大。不过正常发挥就可以了吧。

这两天貌似很多事情都变了很多。QQ 好友数目呈指数爆炸式增长，五一的 RQNOJ 群变得异常火热。终于认识了传说中带狗牛，看到了 RQ 照片，大家还在 IPSC'09 组了队 ~^_^~（话说register添年龄的时候发现我们三的年龄恰成等差数列）。这样给了今年的 APIO 不少期待。虽然估计这次要考差，但见识到这么多传说中的牛人，也不虚此行吧。

怎么说着说着废话又连篇了。- -|| 就到这里吧，期待 APIO'09，大家共同加油！