从0到1构建计算机(10/12)--简单的操作系统

上一篇我们完成了Jack的编译器，这就意味着我们可以随心所欲地在Hack上编写Jack程序了。但是以Jack目前的能力，即使是想完成一些简单的操作也要编写非常复杂的代码，例如我们想要在屏幕上输出“Hello Workd!”，就必须在屏幕上特定位置绘制上几百个像素点。所以我们需要实现一个简单的操作系统来让事情变得更简单一些。

操作系统就是用来衔接计算机的硬件系统和软件系统的，以使得计算机对程序员和用户而言更容易使用。本篇的操作系统包含了一个最小规模的操作系统（其实就是一个Jack标准库的集合），主要包括：数学运算、字符串操作、内存管理、文本和图形输出到屏幕、键盘输入处理等功能，不包括：进程管理、磁盘管理、通信等功能。

数学操作

目前Hack在硬件上只支持加法和减法，因此我们需要在软件层面完善Hack的数学操作，包括：乘法、除法、绝对值、最大值、最小值、开平方操作。

效率第一，在加减法的基础上实现这些数学操作的方式可能有很多，在这里我们最应该关注的是执行的效率，因为数学操作是计算机工作时最常做的基本操作之一，最大程度的优化数学操作是优化计算机性能的重要主题。例如CPU会专门为浮点数设计浮点数计算单元，更擅长数学运算的GPU也被设计出来用于辅助计算机的数学运算。

乘法

对于乘法 sum=x*y，最简单的方法是把 sum=sum+x 重复运算 y 次，算法的时间复杂度为 O(n)。另一种方式是模拟小学运算乘法的竖式方式：用 shiftedx 去乘 y 的每一位，如果 y 的这位为1，则把结果加到 sum 中，如果为0则舍弃；处理完 y 的当前位后，处理 y 的下一位，此时需要操作 shiftedx=shiftedx*2（此操作可以通过加法实现，或者通过移位实现，移位效率更高，虽然Hack不支持移位操作）。第二种方式效率更高，算法的时间复杂度为 O(log2(n))。

实现：

static int powers_of_two;

function void init() {
    let powers_of_two = Array.new(16);
    let powers_of_two[0] = 1;
    let powers_of_two[1] = 2;
    let powers_of_two[2] = 4;
    let powers_of_two[3] = 8;
    let powers_of_two[4] = 16;
    let powers_of_two[5] = 32;
    let powers_of_two[6] = 64;
    let powers_of_two[7] = 128;
    let powers_of_two[8] = 256;
    let powers_of_two[9] = 512;
    let powers_of_two[10] = 1024;
    let powers_of_two[11] = 2048;
    let powers_of_two[12] = 4096;
    let powers_of_two[13] = 8192;
    let powers_of_two[14] = 16384;
    let powers_of_two[15] = 16384+16384;
    return;
}

// 判断x的第n位是否为1
function boolean bit(int x, int n) {
    return ~((x & powers_of_two[n]) = 0);
}

function int multiply(int x, int y) {
    var int sum, shiftedX;
    var int j;
    
    let sum = 0;
    let shiftedX = x;
    let j = 0;
    while( j < 16 ) {   // 16-bit numbers
        if(Math.bit(y, j)) {
            let sum = sum + shiftedX;
        }
        let shiftedX = shiftedX + shiftedX;
        let j = j + 1;
    }
    return sum;
}

除法

对于除法 d=x/y，容易想到的方法是重复计算 x=x-y，每计算一次后 d=d+1，直至 x-y<0 为止。在这种情况下，最坏的情况是 y=1 的情况，此时的步长最短，需要重复计算x次，时间复杂度为 O(x)。我们可以进一步优化，增加步长，每次不是减去y，而是减去2y，而且是递归的进行下去，直至 x<y 时返回，此时最坏的时间复杂度为 O(log2(n))。

function int divide(int x, int y) {
    var int neg_x, neg_y;
    var int q;
    var int result;
    
    let neg_x = x < 0;
    let neg_y = y < 0;
    let x = Math.abs(x);
    let y = Math.abs(y);

    if( y > x ) {
        return 0;
    }
    let q = Math.divide(x, y+y);
    if( x-(2*q*y) < y ) {
        let result = q+q;
    }
    else {
        let result = q+q+1;
    }
    
    if( neg_x = neg_y ) {
        return result;
    }
    else {
        return -result;
    }
}

开平方

这个开平方函数返回入参 x 开平方后结果的整数部分。算法可以使用二分查找的方式，找到 $y^2\leq x<(y+1)^2$ 即可。该算法的时间复杂度为O(log2(n))，但由于我们计算的 x 大小有上限（$2^{16}-1$），所以真实执行时循环的次数是固定的 n/2 (n=16)，复杂度是O(n/2)。

伪代码：
y = 0
for j = n/2 - 1 ... 1, 0 do
    if (y+2^j)^2 < x then y = 2^j
return y

function int sqrt(int x) {
    var int j, y;
    var int approx;
    var int approx_squared;
    
    let y = 0;
    let j = 7;      // = #bits / 2 - 1
    while( ~(j < 0) ) {
        let approx = y + powers_of_two[j];
        let approx_squared = approx * approx;
        if( ~(approx_squared > x) & (approx_squared > 0) ) {    // in case of overflow
            let y = approx;
        }
        let j = j - 1;
    }
    return y;
}

绝对值、最大值、最小值、取模

这些运算就比较简单了

function int max(int a, int b) {
    if( a > b ) {
        return a;
    }
    else {
        return b;
    }
}

function int min(int a, int b) {
    if( a < b ) {
        return a;
    }
    else {
        return b;
    }
}

function int abs(int x) {
    if( x < 0 ) {
        let x = -x;
    }
    return x;
}

function int mod(int x, int y) {
    var int q;
    
    let q = Math.divide(x, y);
    return x - (q*y);
}

字符串

字符串的逻辑比较简单。在Jack中，一个字符串是一个数组，存储内容一串ascii编码（且不需要以\0结尾）。我们用String类来实现，其中最核心的两个方法是构造函数 new(int length) 和 appendChar(char c)，这里我们只支持一个一个地追加字符，不支持直接传入一个字符串😂。附上ascii编码表：

class String {
    field Array buffer;
    field int buffer_len;
    field int str_len;
    
    constructor String new(int maxLength) {
        if( maxLength = 0 ) {
            let maxLength = 1;
        }
        let buffer = Array.new(maxLength);
        let buffer_len = maxLength;
        let str_len = 0;
        return this;
    }

    method void dispose() {
        do Array.dispose(buffer);
        return;
    }

    method int length() {
        return str_len;
    }

    method char charAt(int j) {
        return buffer[j];
    }

    method void setCharAt(int j, char c) {
        let buffer[j] = c;
        return;
    }

     *  Returns this string as the return value. */
    method String appendChar(char c) {
        if( str_len < buffer_len ) {
            let buffer[str_len] = c;
            let str_len = str_len + 1;
        }
        return this;
    }

    method void eraseLastChar() {
        if( str_len > 0 ) {
            let str_len = str_len - 1;
        }
        return;
    }

    /** 返回字符串代表的整数值 */
    method int intValue() {
        var int int_val;
        var int i;
        var boolean neg;
        
        let int_val = 0;
        
        if( (str_len > 0) & (buffer[0] = 45) ) {      // '-'
            let neg = true;
            let i = 1;
        }
        else {
            let neg = false;
            let i = 0;
        }
        
        while( (i < str_len) & String.is_digit(buffer[i]) ) {
            let int_val = (int_val * 10) + String.digit_val(buffer[i]);
            let i = i + 1;
        }
        
        if( neg ) {
            return -int_val;
        }
        else {
            return int_val;
        }
    }
    
    function boolean is_digit(char c) {
        return ~(c < 48) & ~(c > 57);
    }
    
    function int digit_val(char c) {
        return c - 48;
    }
    
    function char digit_char(int i) {
        return i + 48;
    }

    /** 以字符串的形式保存整数 */
    method void setInt(int number) {
        let str_len = 0;    // Clear string
        
        if( number < 0 ) {
            let number = -number;
            do appendChar(45);      // leading '-'
        }
        
        do do_set_int(number);
        return;
    }

    method void do_set_int(int number) {
        var int q;
        var int mod;
        var char c;
        
        let q = number / 10;
        let mod = number - (q*10);
        let c = String.digit_char(mod);
        
        if( number < 10 ) {
            do appendChar(c);
        }
        else {
            do do_set_int(q);
            do appendChar(c);
        }
        return;
    }
    
    function char newLine() {
        return 128;
    }

    function char backSpace() {
        return 129;
    }

    /** 双引号 */
    function char doubleQuote() {
        return 34;
    }
}

内存管理

使用高级语言，最大的方便之一就是开发者几乎不用关注内存管理的细节，所有复杂琐碎的工作都又操作系统，编译器，虚拟机，汇编器等底层来负责实现。不同变量类型的内存在程序声明周期中的不同时刻被分配，例如，静态变量在编译期由编译器为其分配内存；局部变量则在每个函数运行的时候分配在栈内存上；其他内存则是在程序运行时被动态地分配在堆内存上，这些内存就需要借助操作系统来管理了。操作系统可能使用不同的方式来管理内存的分配和回收，通常都是用alloc()和deAlloc()这两个函数中实现的。

最简单的内存管理算法

使用一个单一的指针 free 指向还未使用过的内存的基地址。这种方式只是简单的向前分配内存，不负责回收内存。

// 伪代码
initialize free = heapBase

// 分配一块大小为 size 的内存
alloc(size)
  pointer = free
  free = free + size 
  return pointer

// 回收object的内存
deAlloc(object)
do nothing        // 不做内存回收处理

算法改进

经典的算法是可以使用链表来管理内存。该算法管理一个freeList链表，链表的每一个节点都是一个内存段，调用者申请分配内存时，操作系统从可用内存段中挑选一个合适的内存段（内存段内存大于申请的内存），将其（内存段的全部内存或部分内存）返回给调用者，然后更新链表。调用者申请回收内存时，操作系统把需要回收的这段内存加入freeList链表。

每个内存段的第一个位置用于保存该内存段的长度，第二个位置用于指向 Next 内存段。当操作系统查找合适的内存段时可以使用最优适应算法，即查找整个链表中大小最匹配变量的内存段；或者最先适应算法，即找到第一个满足变量需求的内存段。

我们以下图为例，当前的freeList状态如左图所示，有三块内存，其内存段大小分别是4、9、5（可用大小是2、7、3）。当调用者执行alloc(5)时，代表调用者需要大小为5的内存，此时三块内存中只有大小为9的内存块满足需求，我们中取出后6位内存返回给调用者（多的一位用来标识该变量占用内存大小，后续用于内存回收时使用），然后大小为9的内存块就还剩3了。

// 伪代码
Initialize:
	freeList = heap
	freeList.length = heapLength
	freeList.next = null

// 分配内存
alloc(size):
	利用“最优适应算法”或者“最先适应算法”找到合适的内存段（满足条件 segement.length > size）
	if 找不到
	  返回 fail 或者尝试整合内存碎片
	else
	  block = 从内存段中取出一段内存，大小为 size + 1（如果取出后，该内存段剩余太小，则直接是这整个内存段就好，防止小碎片出现）
	  更新选中的内存的剩余情况
	  block[-1] = size + 1，标识变量申请的占用内存大小，后续用于内存回收时使用
	  return block

// 回收内存
deAlloc(object)
	segement = object - 1，该段内存的基地址
	segement.length = object[-1]，变量占用内存的大小
	将segement插入freeList

// 用jack实现
class Memory {
    static Array memory;
    static Array freeList;
    static Array NO_BLOCK;
    
    static int FL_LENGTH;  // freeList长度在segement上的index，值为为0
    static int FL_NEXT;    // freeListnext指针在segement上的ndex，值为为1
    static int ALLOC_SIZE; // 分配的block的size，在block上的index，值为-1
    
    /** 初始化 */
    function void init() {
        let memory = 0;
        let freeList = 2048;    // heap基地址
        let NO_BLOCK = 16384;   
        let FL_LENGTH = 0;
        let FL_NEXT = 1;
        let ALLOC_SIZE = -1;
        let freeList[FL_LENGTH] = 16384-2048;   //初始化freeList，此时free的内存为整个heap
        let freeList[FL_NEXT] = null;
        return;
    }

    /** 返回地址为address的内存单元的内容 */
    function int peek(int address) {
        return memory[address];
    }

    /** 把数值value存储到地址为address的内存单元中 */
    function void poke(int address, int value) {
        let memory[address] = value;
        return;
    }

    /** 从可用内存中寻找一块合适的内存块，返回内存块的基地址 */
    function Array alloc(int size) {
        var Array prev_block;
        var Array found_block;
        
        let prev_block = Memory.best_fit(size);   // prev_block 是目标 block 的前一个block
        if( prev_block = NO_BLOCK ) {
            let found_block = null;               // 未找到
        }
        else {
            if( prev_block = null ) {
                let found_block = freeList;       // 目标 block 是 freeList 的第一个节点
                let freeList = Memory.do_alloc(found_block, size); // 分配内存，并更新freeList
            }
            else {
                let found_block = prev_block[FL_NEXT];
                let prev_block[FL_NEXT] = Memory.do_alloc(found_block, size); // 分配内存，并更新freeList
            }
        }
        return found_block+1;
    }
    
    /** 最优匹配算法 */
    function Array best_fit(int size) {
        var Array best_block;
        var Array prev_block;
        var Array cur_block;
        var int best_size;
        var int cur_size;
        
        let best_block = NO_BLOCK;
        let best_size = 16384 - 2048;
        let cur_block = freeList;
        let prev_block = null;
        
        // 遍历freeList，找到可用内存大于sie，且其中最小的block
        while( ~(cur_block = null) ) {
            let cur_size = cur_block[FL_LENGTH]-1;
            if( ~(cur_size < size) & (cur_size < best_size) ) {
                let best_block = prev_block;
                let best_size = cur_size;
            }
            let prev_block = cur_block;
            let cur_block = cur_block[FL_NEXT];
        }
        
        return best_block;  // 返回最优block的前一个block
    }

    /** 分配内存，并填充block header的值（值为block的长度）*/
    function Array do_alloc(Array found_block, int size) {
        var Array next_block;
        var int block_size;
        
        if( found_block[FL_LENGTH] > (size+1+2) ) {          // block内存大于申请内内存，分配block的一部分
            let next_block = found_block + size+1;           // next_block的位置
            let next_block[FL_NEXT] = found_block[FL_NEXT];  // next_block重置block信息
            let next_block[FL_LENGTH] = found_block[FL_LENGTH] - (next_block - found_block);
            let found_block = found_block + 1;               // found_block重置block信息
            let found_block[ALLOC_SIZE] = size+1;            
        }
        else {                                               // 把整块内存都分配给申请者
            let next_block = found_block[FL_NEXT];
            let block_size = found_block[FL_LENGTH];
            let found_block = found_block + 1;               // found_block重置block信息
            let found_block[ALLOC_SIZE] = block_size;
        }
        
        return next_block;
    }

    /** 释放内存 */
    function void deAlloc(Array object) {
        var int alloc_size;
        var Array prev_block;
        var Array next_block;
        
        let alloc_size = object[ALLOC_SIZE];
        let object = object - 1;        
        let prev_block = Memory.find_prev_free(object);     // 找到prev_block
        
        if( prev_block = null ) {                           // object成为新的首节点
            let object[FL_LENGTH] = alloc_size;
            let object[FL_NEXT] = freeList;
            let freeList = object;
            let prev_block = object;
        }
        else {
            if( (prev_block + prev_block[FL_LENGTH]) = object ) {
                // 如果 prev_block 和 object 相连，则合并两个block
                let prev_block[FL_LENGTH] = prev_block[FL_LENGTH] + alloc_size;
            }
            else {
                // 链接两个block
                let object[FL_LENGTH] = alloc_size;
                let object[FL_NEXT] = prev_block[FL_NEXT];
                let prev_block[FL_NEXT] = object;
                let prev_block = object;
            }
        }
        
        if( (prev_block + prev_block[FL_LENGTH]) = prev_block[FL_NEXT] ) {
            // 尝试合并prev_block和next_block
            let next_block = prev_block[FL_NEXT];
            let prev_block[FL_LENGTH] = prev_block[FL_LENGTH] + next_block[FL_LENGTH];
            let prev_block[FL_NEXT] = next_block[FL_NEXT];
        }
        return
    }    
    
    /** 返回block的prev_block */
    function Array find_prev_free(Array object) {
        var Array block;
        
        if( freeList > object ) {
            return null;
        }
        
        let block = freeList;
        while( ~(block[FL_NEXT] = null) & (block[FL_NEXT] < object) ) {
            let block = block[FL_NEXT];
        }
        return block;
    }
}

I/O

计算机一般会连接一些输入输出设备，例如：显示器、鼠标、键盘、硬盘、网卡等，这些I/O设备都有自己的特性，在这些设备上进行读写操作也是很复杂的，但对于程序员而言，我们可以通过操作系统来操作它们，操作系统使用一组驱动程序来处理各个I/O设备的操作细节，然后向上提供一组封装好的API接口。

I/O设备对于CPU和操作系统而言，其实是一段内存和一组BIOS驱动程序（在Hack中没有这些驱动程序，需要我们自己写），当操作系统想要和I/O设备交互时，就通过这些程序从相应的内存中读取或写入数据。在Hack中，我们只有两个I/O设备：显示器和键盘，显示器的内存映射是从16384开始的连续的 8K 地址空间（该显示器的分辨率是：512*256）；键盘更简单，它只映射24576这一个地址单元的地址空间（因为足以容纳所有英文字符和符号）

键盘

当我们敲击键盘时，敲击的字符的sacii码会写入到地址为24576的内存中。我们的驱动程序要做的事情就是，完成一组特定的API，他们可以从24576号地址中读取字符（读取单个字符或者先组合成字符串）。

监测键盘输入

第一件事需要做的是，监测到键盘的输入。该方法的核心就是从键盘的内存映像中读出当前按下的字符的ascii码，当读取的值不为0的时候，代表有字符输入。

// keyPress() 伪代码
if 有按键按下
    return 该键的sacii码
else 
    return 0

// Jack实现
function char keyPressed() {
    return keyboard[0];
}

读取单个字符

读取单个字符时我们需要面对两个问题。第一个，什么情况下才叫用户输入了一个单个字符呢？这里我们定义用户按下一个按键，然后松开按键，这过程会输入一个字符（即使长时间按住再松开也是输入一个），所以我们需要做的事情是等待用户输入，然后记录数值，然后等待用户松开，完成本次单个字符读取。第二个，给用户一个可视化反馈，当用户输入一个字符后，需要在屏幕上回显出来，并且辅助以光标提示（虽然这个操作看似理所当然，但其中经过的过程并不简单）。

// readChar() 伪代码

while 没有任何按键按下
    等待...直到有按键按下

c = 当前按下的按键值

while 当前按键还处于按下状态
    等待...直到按键松开

print c // 把字符回显到屏幕上
将光标右移一格

return c

// jack实现
function char readChar() {
    var char key;
    while( Keyboard.keyPressed() = 0 ) {}
    let key = Keyboard.keyPressed();
    while( ~(Keyboard.keyPressed() = 0) ) {}
    do Output.printChar(key);
    return key;
}

读取一行字符

然后我们在 readChar() 的基础上扩展出 readLine()，readLine()需要解决两个问题。第一个，把读取的单个字符写入字符串缓冲区，直到输入换行符时结束。第二个，允许用户在输入过程中使用删除键删除

// readLine() 伪代码
s = 空字符串
repeat
    c = readChar()
    if c = 换行符
        print 换行符
        return s
    else if c = 退格键
        s 删除最后一个字符
        光标左移一格
    else
        s = s.append(c)

// Jack实现
function String readLine(String message) {
    var String line;
    var char c;
    
    do Output.printString(message);
    
    let line = String.new(50);     // max length
    let c = Keyboard.readChar();
    while( ~(c = String.newLine()) ) {
        if( c = String.backSpace() ) {
            do line.eraseLastChar();
            do Output.backSpace();
        }
        else {
            do line.appendChar(c);
        }
        let c = Keyboard.readChar();
    }
    return line;
}   

可以看到，键盘输入的设计实现还是基于一系列级联的分层抽象。高级程序readLine()依赖readChar()，readChar()依赖于keyPress()，keyPress()依赖于硬件。可见分层抽象的设计模式贯穿了整个计算机的宏观架构和微观实现，可以说是计算机科学的精华思想。

图形显示

现代计算机大多使用位图（bitmap）或称光栅（raster）的技术来显示图形或文字。屏幕由一组二维的平面点组成，每个点是一个像素（pixel），每个像素点对应到显存中的某个地址，计算机要做的就是给每个像素点赋上一个颜色的值，Hack只支持黑和白，因此只占1bit，如果显示器支持彩色显示，那么每个像素就会占用更多bit的内存。

Hack的屏幕分辨率是512*256，即屏幕上有131072个像素点。像素点和显存的对应关系如下：现存中每个Bit对应一个像素点（1代表黑色，0代表白色），一行512个像素需要对应 32*16bit（一个word），32word/行*256行=8192word，正好是8K地址空间。因此存在对应关系：第r行第c列的像素点，对应地址为 Screen[r*32+c/16] 的word的第 c%16 的bit。

点

了解了上面像素点和内存bit的对应关系后，我们就可以写出给单一像素点赋值的方法了。

/** 绘制像素点 (x, y) */
function void drawPixel(int x, int y) {
    var int address;
    var int mask;

    let address = (y*32) + (x/16);       // 先找到第几个word
    let mask = Math.two_to_the(x & 15);  // 再找到该word的第几个bit，并转成掩码的形式。例如第4个bit，对应0000000000000100

    if( cur_colour ) {
        let screen[address] = screen[address] | mask;
    }
    else {
        let screen[address] = screen[address] & ~mask;
    }

    return;
}

/** 清除屏幕 */
function void clearScreen() {
    var int i;
    let i = 0;
    while( i < 8192 ) {
        let screen[i] = white;
    }
    return;
}

/** 设置将要使用的color white = false, black = true. */
function void setColor(boolean b) {
    let cur_colour = b;
    return;
}

线

点很容易绘制，线则复杂很多。由于像素点是一个个矩形的小方块，所以除了横线和竖线，我们无法绘制出完全笔直的线（斜线都是带锯齿毛边的），当然通过缩小像素点的大小我们可以无限逼近笔直（当像素点小到人眼无法分辨时就可以了，即所谓的视网膜屏幕）。

我们在绘制线的时候，分为3种场景：横线、竖线和斜线。其中横线和竖线都比较容易实现，绘制斜线则复杂一些，需要借助特定的算法。

/** 从 (x1, y1) 到 (x2, y2) 绘制一条线 */
function void drawLine(int x1, int y1, int x2, int y2) {
    var int dx, dy;
    var int temp;
    
    // 保证 x1 <= x2
    if( x1 > x2 ) {
        let temp = x1;
        let x1 = x2;
        let x2 = temp;
        let temp = y1;
        let y1 = y2;
        let y2 = temp;
    }

    let dx = x2 - x1;
    let dy = y2 - y1;
    
    if( dx = 0 ) {
        do Screen.drawVerticalLine( x1, y1, y2 );
    }
    else { if( dy = 0 ) {
        do Screen.drawHorizontalLine( x1, x2, y1 );
    }
    else {
        do Screen.drawDiagonalLine( x1, y1, x2, y2, dx, dy );
    }}
    
    return;
}

竖线

绘制竖线较容易，调用 drawPixel() 方法，从 y1 绘制到 y2 即可（y1<=y2）。

function void drawVerticalLine( int x, int y1, int y2 ) {
    var int temp;
    
    // 保证 y1 <= y2
    if( y1 > y2 ) {
        let temp = y1;
        let y1 = y2;
        let y2 = temp;
    }
    
    while( ~(y1 > y2) ) {
        do Screen.drawPixel( x, y1 );
        let y1 = y1 + 1;
    }
    return;
}

横线

横线的实现方式可以和竖线一样，一个个像素的绘制完即可。但这里我们做一个小优化，一条横线会横跨n个word，除了头和尾，中间的word都是连续的，所有我们可以为这些word一次性赋值16个bit，这样循环的次数会缩短16倍。

function void drawHorizontalLine( int x1, int x2, int y ) {
    var int start_addr, end_addr;
    var int x1mod16, x2mod16;
    
    let x1mod16 = x1 & 15;               // 线在一个word内的偏移量
    let x2mod16 = x2 & 15;               // 线在最后一个word内的偏移量
    let start_addr = (y*32) + (x1/16);
    let end_addr = (y*32) + (x2/16) + (x2mod16=0);

    if( start_addr = end_addr ) {        // 线的长度在一个word内
        do Screen.draw_short_horizontal_line( x1, x2, y );
    }
    else { 
        if( ~(x1mod16 = 0) ) {           // 线在第一个Word内的一小段
            let start_addr = start_addr + 1;
            do Screen.draw_short_horizontal_line( x1, x1+16-x1mod16, y );
        }
        if( ~(x2mod16 = 0) ) {           // 线在最后个Word内的一小段
            let end_addr = end_addr - 1;
            do Screen.draw_short_horizontal_line( x2-x2mod16, x2, y );
        }
        while( ~(start_addr > end_addr) ) {     // 中间的若干段word
            let screen[start_addr] = cur_colour;
            let start_addr = start_addr + 1;
        }
    }
    
    return;
}

function void draw_short_horizontal_line( int x1, int x2, int y ) {
    while( ~(x1 > x2) ) {
        do Screen.drawPixel( x1, y );
        let x1 = x1 + 1;
    }

    return;
}

斜线

斜线的绘制法比直线复杂，因为我们在绘制像素点的时候只能向上、下、左、右四个方向绘制，而不能斜着绘制，所以我们只能尽量让我们的斜线和目标斜线近似。为了完成绘制斜线，我们需要引入斜率来辅助：如下图所示，我们在绘制斜线时，新绘制的像素点的运动位置是像蛇一样左右蜿蜒前进的，我们的算法的目的就是别让这条蛇跑偏，当前斜率小于目标斜率时，我们就向上绘制像素点以增大斜率；当前斜率大于目标斜率时，我们就向右绘制像素点以减小斜率。

算法思想如上述，我们下面要做的就是实现它的普遍适用版本（不同方向的斜线）。

function void drawDiagonalLine( int x1, int y1, int x2, int y2, int dx, int dy ) {
    var int a, b;
    var int adyMinusbdx;
    var int y_incr;

    let a = 0;
    let b = 0;
    let adyMinusbdx = 0;
    
    if( dy < 0 ) {  // 斜线方向
        let y_incr = -1;
    }
    else {
        let y_incr = 1;
    }

    while( ~(a > dx) & (((y_incr = 1) & ~(b > dy)) | ((y_incr = -1) & ~(b < dy))) ) {  // 是否绘制到了终点
        do Screen.drawPixel( x1+a, y1+b );
        if( adyMinusbdx < 0 ) {  // 如果斜率偏大，向右绘制
            let a = a + 1;
            let adyMinusbdx = adyMinusbdx + (dy*y_incr);
        }
        else {                   // 如果斜率偏小，向上（下）绘制
            let b = b + y_incr;
            let adyMinusbdx = adyMinusbdx - dx;
        }
    }
    return;
}

矩形

矩形的绘制比较简单，就是绘制n条横线即可。

function void drawRectangle(int x1, int y1, int x2, int y2) {
    var int y;
    
    let y = y1;
    while( ~(y > y2) ) {
        do Screen.drawHorizontalLine(x1, x2, y);
        let y = y + 1;
    }
    return;
}

圆

圆也有一个简单的绘制算法：从上到下一行行的绘制，一种每一行的长度都可以根据半径r和偏移量dy计算出来（涉及到平方和开发运算，我们在Math类汇中已经实现）

function void drawCircle(int cx, int cy, int r) {
    var int dx, dy;
    var int r_squared;
    
    let dy = -r;
    let r_squared = r*r;
    while( ~(dy > r) ) {
        let dx = Math.sqrt(r_squared-(dy*dy));
        do Screen.drawHorizontalLine( cx-dx, cx+dx, cy+dy );
        let dy = dy + 1;
    }
    return;
}

文字显示

为了在屏幕上输出文字，我们把512*256的屏幕划分成若干个8*11大小的的方格子（总共划分了64*23个），在每个方格子中我们可以利用88个像素点来绘制文字，以下图的为例。

实现文字绘制的逻辑也是比简单的，最重要的是要先设计出字符的bitMap（字符的bitMap决定了字符的字形和字体），Hack支持127中字符的展示，这里我们列出其中的一部分：

// 黑色方块                                          
do Output.create(0,63,63,63,63,63,63,63,63,63,0,0);

// 各个字符的 bitmap
do Output.create(32,0,0,0,0,0,0,0,0,0,0,0);          //
do Output.create(33,12,30,30,30,12,12,0,12,12,0,0);  // !
do Output.create(34,54,54,20,0,0,0,0,0,0,0,0);       // "
......

do Output.create(48,12,30,51,51,51,51,51,30,12,0,0); // 0
do Output.create(49,12,14,15,12,12,12,12,12,63,0,0); // 1
do Output.create(50,30,51,48,24,12,6,3,51,63,0,0);   // 2
......

do Output.create(58,0,0,12,12,0,0,12,12,0,0,0);      // :
do Output.create(59,0,0,12,12,0,0,12,12,6,0,0);      // ;
do Output.create(60,0,0,24,12,6,3,6,12,24,0,0);      // <
......

do Output.create(65,12,30,51,51,63,51,51,51,51,0,0); // A
do Output.create(66,31,51,51,51,31,51,51,51,31,0,0); // B
do Output.create(67,28,54,35,3,3,3,35,54,28,0,0);    // C
......

do Output.create(91,30,6,6,6,6,6,6,6,30,0,0);          // [
do Output.create(92,0,0,1,3,6,12,24,48,32,0,0);        // \
do Output.create(93,30,24,24,24,24,24,24,24,30,0,0);   // ]
......

do Output.create(97,0,0,0,14,24,30,27,27,54,0,0);      // a
do Output.create(98,3,3,3,15,27,51,51,51,30,0,0);      // b
do Output.create(99,0,0,0,30,51,3,3,51,30,0,0);        // c
......

do Output.create(123,56,12,12,12,7,12,12,12,56,0,0);   // {
do Output.create(124,12,12,12,12,12,12,12,12,12,0,0);  // |
do Output.create(125,7,12,12,12,56,12,12,12,7,0,0);    // }
......

// 创建一个8*11的bitMap, 其中 a,b,c 代表其中某一行的bitMap情况
function void create(int index, int a, int b, int c, int d, int e, int f, int g, int h, int i, int j, int k) {
    var Array map;

    let map = Array.new(11);
    let charMaps[index] = map;

    let map[0] = a;
    let map[1] = b;
    let map[2] = c;
    let map[3] = d;
    let map[4] = e;
    let map[5] = f;
    let map[6] = g;
    let map[7] = h;
    let map[8] = i;
    let map[9] = j;
    let map[10] = k;

    return;
}

除了字符，我们还需要通过光标来辅助指示当前字符显示的位置，包括向前、向后移动，换行：

/** 移动光标位置 */
function void moveCursor(int i, int j) {
    let cursor_x = j;
    let cursor_y = i;
    return;
}

/** 在屏幕上换行 */
function void println() {
    let cursor_x = 0;
    if( cursor_y < 22 ) {
        let cursor_y = cursor_y + 1;
    }
    else {
        do Output.scroll();
    }
    return;
}

/** 屏幕翻页 */
function void scroll() {
    let cursor_x = 0;
    let cursor_y = 0;
            
    return;
}

/** 退格 */
function void backSpace() {
    if( cursor_x = 0 ) {
        if( ~(cursor_y = 0) ) {
            let cursor_x = 63;
            let cursor_y = cursor_y - 1;
        }
    }
    else {
        let cursor_x = cursor_x - 1;
    }
    
    return;
}

最后是在光标的位置打印一个字符（或一串字符），这个过程是：先根据光标的位置计算出字符应该占用的内存的位置，然后把字符的 bitMap 填充到这块内存的过程。

/** 在屏幕上打印字符，并将光标位置向前移动一格 */
function void printChar(char c) {
    var Array map;
    var int address;
    var int mask;
    var int bitmap;
    var int i;
    
    // 获取字符的bitMap，地址锚点到当前光标位置
    let map = Output.getMap(c);
    let address = (cursor_y*32*11) + (cursor_x/2);
    let mask = cursor_x & 1;
    
    // 把bitMap的值，填充到锚点到的内存（11*8的方块）
    let i = 0;
    while( i < 11 ) {
        let bitmap = map[i];
        if( mask = 1 ) {
            let bitmap = bitmap * 256;
        }
        let screen[address] = screen[address] & charMasks[mask] | bitmap;
        let address = address + 32;
        let i = i + 1;
    }
    
    // 移动光标位置
    if( cursor_x = 63 ) {
        do Output.println();
    }
    else {
        let cursor_x = cursor_x + 1;
    }
    
    return;
}

/** 在屏幕上打印一个字符 */
function void printString(String s) {
    var int i;
    let i = 0;
    while( i < s.length() ) {
        do Output.printChar(s.charAt(i));
        let i = i + 1;
    }
    return;
}

/** 在屏幕上打印一个数字 */
function void printInt(int i) {
    var String s;
    let s = String.new(10);
    do s.setInt(i);
    do Output.printString(s);
    do s.dispose();
    return;
}

System

我们完成了一系列的Jack操作系统的基础库，它们提高了我们使用Jack编写程序的效率，拓展了程序的人机交互能力。最后我们需要再写一个System类，把这些库整合起来，形成Jack操作系统。首先我们要知道操作系统也是一个程序，当计算机启动时，首先被执行的程序就是操作系统（准确的说先执行引导程序，引导执行操作系统程序）。Jack操作系统会先执行一系列标准库初始化工作，然后再把执行交给主程序，主程序执行完后（如果主程序不是以无限循环的方式执行的话），操作系统把计算机挂起（无限循环的方式）。

class Sys {

    function void init() {
        do Math.init();    // 系统库初始化
        do Output.init();
        do Screen.init();
        do Keyboard.init();
        do Memory.init();
        do Main.main();    // 执行主程序
        do Sys.halt();     // 完成主程序后，挂起
        return;
    }

    /** 挂起：无限循环 */
    function void halt() {
        while(true){}
        return;
    }

    /** Wait 一小段时间 */
    function void wait(int duration) {
        var int i, j;
        let i = 0;
        while( i < duration ) {
            let j = 0;
            while( j < 200 ) {
                let j = j + 1;
            }
            let i = i + 1;
        }
        return;
    }

    /** 打印错误信息 */
    function void error(int errorCode) {
        do Output.printString("Err");
        do Output.printInt(errorCode);
        do Sys.halt();
        return;
    }
}

总结

可以说我们本篇实现的操作系统完全算不上一个真正意义上的操作系统，最终这个操作系统和我们的主程序会被一起编译，生成一个静态程序。最终Hack执行的是这个目标程序，而不是操作系统，Jack操作系统完全没有起到管理程序的作用。但这不妨碍我们从中窥到操作系统中的一些底层操作的工作原理（主要是内存管理和I/0管理）。

我们也完全可以对它进行扩展，例如可以在操作系统中集成进100个小游戏，启动后在屏幕上展示所有游戏的图标，用户选择游戏后，操作系统切换到相应的游戏程序执行。这样我们就把Hack变成了一个小霸王游戏机😅。

本篇完整实现放在了:github