首页 > 代码库 > 计算机系统要素：第十二章 操作系统
计算机系统要素：第十二章 操作系统
终于来到了Hack计算机架构的最后一部分——操作系统的构建了！这一章的内容涉及了大量的逻辑架构、算法问题与细节处理，需要花很多精力才能够完成。我曾经与nand2tetris团队的一位工作人员有过联系，他就指出，这本书最后几个较难的章节介绍性的内容太少了，最后的OS章节如果作为正常的上课来学习的话，两周时间是绝对不够的（只要想想，计算机专业的学生得花一个学期学OS），其中涉及了太多问题。因此，在这篇文章中，我会将语言规范、溢出处理、特殊情况处理等几个重要的问题单独列出加以讨论。
Math
溢出(overflow)处理：
Math中各个算法的实现其实都不难，重要的是必须考虑溢出情况，因为这是一台16位的计算机，所以它能表示的数字范围在-32768~32767之间。而溢出情况就是指计算的数字超出了这个范围，如果不加以考虑的话，溢出部分的数字会出现混乱。这里，我给大家提供一篇参考文章，里面详细阐述了这方面的内容。
// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/12/Math.jack
/**
* A basic math library.
*/
class Math {
/** Initializes the library. */
function void init() {
return;
}
/** Returns the absolute value of x. */
function int abs(int x) {
var int absNum;
if (x < 0){
let absNum = -x;
}
else{
let absNum = x;
}
return absNum;
}
/** Returns the product of x and y. */
function int multiply(int x, int y) {
var int sum;
var int shiftedX,functionY;
var int flag,j;
var boolean WhetherNeg;
let sum = 0;
let shiftedX = Math.abs(x);
let functionY= Math.abs(y);
let flag=1;
let j=0;
if ((x=0)|(y=0)){
return 0;
}
let WhetherNeg = ((x<0)=(y<0));
while(j<16){
if(functionY&flag=flag){
let sum = sum + shiftedX;
}
let shiftedX=shiftedX+shiftedX;
let flag=flag+flag;
let j=j+1;
}
if (~WhetherNeg){
let sum=-sum;
}
return sum;
}
/** Returns the integer part of x/y (x>0,y>0). */
function int div(int x, int y) {
var int q,qy;
if((y<0)|(y>x)){
return 0;
}
let q = Math.div(x,y+y);
let qy = Math.multiply(q,y);
if (x-qy-qy<y){
return q+q;
}
else{
return q+q+1;
}
}
/** Returns the integer part of x/y. */
function int divide(int x, int y) {
var int answer;
var int absX,absY;
var boolean WhetherNeg;
let absX = Math.abs(x);
let absY= Math.abs(y);
if(absY=0){
return Sys.error(3);
}
let WhetherNeg = ((x<0)=(y<0));
let answer = Math.div(absX, absY);
if (~WhetherNeg){
let answer=-answer;
}
return answer;
}
/** Returns to the exponent number n where x <= 2^n. */
function int logTwo(int x){
var int powerTwo,flag;
if ((x>16384)&((x<32767)|(x=32767))){
return 15;
}
let powerTwo = 1;
let flag = 0;
while (powerTwo<x){
let powerTwo = powerTwo+powerTwo;
let flag = flag + 1;
}
return flag;
}
/** Returns to x^y. */
function int power(int x, int y){
var int flag;
var int result;
let flag = y;
let result = 1;
if(y=0){
return 1;
}
while ( flag>0 ){
let result = Math.multiply(result,x);
let flag=flag-1;
}
return result;
}
/** Returns the integer part of the square root of x. */
function int sqrt(int x) {
var int y,j,flag,powerJ;
var int n,halfN;
let y=0;
let n = Math.logTwo(x);
let halfN = Math.divide(n,2);
let j=halfN;
if (x<0){
return Sys.error(3);
}
while (j>-1){
let powerJ = Math.power(2,j);
let flag = y+powerJ;
let flag = Math.multiply(flag,flag);
if (((flag < x) | (flag = x)) & (flag > 0)){
let y = y + powerJ;
}
let j=j-1;
}
return y;
}
/** Returns the greater number. */
function int max(int a, int b) {
if (a>b){
return a;
}
else{
return b;
}
}
/** Returns the smaller number. */
function int min(int a, int b) {
if (a<b){
return a ;
}
else{
return b;
}
}
}
Array
Array模块的实现非常简单，只需要注意，它调用了Memory模块中的相关函数，以实现动态分配内存。
// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/12/Array.jack
/**
* Represents an array. Can be used to hold any type of object.
*/
class Array {
/** Constructs a new Array of the given size. */
function Array new(int size) {
var Array a;
let a=Memory.alloc(size);
return a;
}
/** De-allocates the array and frees its space. */
method void dispose() {
do Memory.deAlloc(this);
return;
}
}
String
语言规范：field变量的使用
String的本质是一个数组，在每一个String类中，都必须有四个全局参数，一个是数组a，代表了String的起始地址，一个是当前字符串长度stringLength和最大字符串长度allocLength（注意，这两个长度是不同的！），另外还有判断String是否为负数字符串的negFlag。
负数的处理：
1，String.new(0) 参数小于0时最好报错，参数等于0时，默认给它赋1的空间。
2，数字与字符串相转换时，若数字为负数，需要加符号，这里用negFlag来判别。
此外，本书的字符串编码与ASCII有细微差异，例如，书中将backspace定义为129，换行定义为128，读者只需了解即可。
// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/12/String.jack
/**
* Represents a String object. Implements the String type.
*/
class String {
field Array a;
field int stringLength;
field boolean negFlag;
field int allocLength;
/** Constructs a new empty String with a maximum length of maxLength. */
constructor String new(int maxLength) {
if (maxLength<1){
let maxLength = 1;
}
let allocLength = maxLength;
let negFlag = false;
let a = Array.new(maxLength);
let stringLength = 0;
return this;
}
/** De-allocates the string and frees its space. */
method void dispose() {
do a.dispose();
return;
}
/** Returns the current length of this String. */
method int length() {
return stringLength;
}
/** Returns the character at location j. */
method char charAt(int j) {
var char c;
let c=a[j];
return c;
}
/** Sets the j"th character of this string to be c. */
method void setCharAt(int j, char c) {
let a[j]=c;
return;
}
/** Appends the character c to the end of this String.
* Returns this string as the return value. */
method String appendChar(char c) {
var int length;
if(stringLength=allocLength){
do Sys.error(17);
}
let length = stringLength;
let a[length] = c;
let stringLength=stringLength+1;
return this;
}
/** Erases the last character from this String. */
method void eraseLastChar() {
var int length;
let length = stringLength;
let stringLength=stringLength-1;
return;
}
/** Returns the integer value of this String until the first non
* numeric character. */
method int intValue() {
var int length,i,result;
var int temp;
var boolean flag;
let flag=false;
let i=0;
let length = stringLength;
let result = 0;
if (a[0]=45){
let flag = true;
let i=i+1;
}
while (i < length){
if ((a[i]>47)&(a[i]<58)){
let temp = a[i]-48;
let result = Math.multiply(result,10) + temp;
let i=i+1;
}
else{
if (flag){
let result = -result;
}
return result;
}
}
if (flag){
let result = -result;
}
return result;
}
/** Sets this String to hold a representation of the given number. */
method void setInt(int number) {
var int lastDigit;
var int divNumber,tenNumber;
var int c;
let stringLength = 0;
if (number < 0){
let negFlag = true;
let number = Math.abs(number);
}
let divNumber = Math.divide(number,10);
let tenNumber = Math.multiply(divNumber,10);
let lastDigit = number - tenNumber;
let c = lastDigit+48;
if (number<10){
if (negFlag){
do appendChar(45);
let negFlag = false;
}
do appendChar(c);
}
else{
do setInt(divNumber);
do appendChar(c);
}
return;
}
/** Returns the new line character. */
function char newLine() {
return 128;
}
/** Returns the backspace character. */
function char backSpace() {
return 129;
}
/** Returns the double quote (") character. */
function char doubleQuote() {
return 34;
}
}
Memory
Memory模块的实现比较难入手，因为其中涉及到对于堆栈的操作。而且，内置的OS算法和书中给出的算法并不相同，我更倾向于内置的算法，它比较易于实现。
（图中第一列代表堆栈位置，第二列代表存储数据）
图一：
图二：
图一是堆栈的初始状态，起始位置为2048，其中存储的14334代表从2050开始到16383，一共有14334个可用空间，2049的位置则表示下一个指针指向的位置。
图二表示的是堆栈经过一次alloc后的状态，在这儿，我们做的事alloc(2)，也就是取出了两个栈空间使用。从图中可以看到，分配完两个空间后，此时的2048位置已经变为了0，如果下一次指针游走到这个位置，它就会明白该空间已经被占据，需要往下移一个位置到2049，寻找下一个节点（2052），到了下一个节点，发现空间为14330，如果够用的话，就按照上述规律在其中分配空间。可以看到，其实每一次分配的空间并不等于size，而是size+2。
PS：我给出的代码没有完成整合碎片的步骤，请读者自行思考。
// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/12/Memory.jack
/**
* Memory operations library.
*/
class Memory {
static Array freelist;
/** Initializes memory parameters. */
function void init() {
let freelist = 0;
let freelist[2048]=14334;
let freelist[2049]=2050;
return;
}
/** Returns the value of the main memory at the given address. */
function int peek(int address) {
return freelist[address];
}
/** Sets the value of the main memory at this address
* to the given value. */
function void poke(int address, int value) {
let freelist[address] = value;
return;
}
/** finds and allocates from the heap a memory block of the
* specified size and returns a reference to its base address. */
function int alloc(int size) {
var int listRoom,listTag,tempAdd,returnVal;
var int minSize;
let minSize=size+3;
let listTag=2048;
let listRoom=Memory.peek(listTag);
while(minSize>listRoom){
let listTag=listTag+1;
let listTag=Memory.peek(listTag);
let listRoom=Memory.peek(listTag);
if(listTag=0) {
do Sys.error(7);
}
}
let returnVal=listTag+2;
do Memory.poke(listTag,0);
let listTag=listTag+1;
let tempAdd=Memory.peek(listTag)+size;
do Memory.poke(listTag,tempAdd);
do Memory.poke(tempAdd,listRoom-size-2);
let listTag=tempAdd+1;
do Memory.poke(listTag,listTag+1);
return returnVal;
}
/** De-allocates the given object and frees its space. */
function void deAlloc(int object) {
var int length;
let length = Memory.peek(object+1)-object-2;
do Memory.poke(object,length);
return;
}
}
Screen：
像素位的分配：
首先，我们需要搞清楚，这256*512的像素阵列是如何存入16384~24575的RAM中的。显存共8192个字，每个字有16位，8192*16=256*512，所以每个像素只占一个比特位。所有像素从左上角(0,0)位置开始，按照自左向右，自上而下的顺序排列，需要注意的是，第一个像素点是存在第一个字的第一位，而非第十六位。
此外要注意的是，按照书上的算法，逐个画像素也能完成画线功能，但是这在实际应用中的效率之低是无法忍受的。如果你这个Screen.vm应用到PongGame中，你会发现其运行速度非常之慢，所以，对于画线，后期最好将算法改进为按字填色。
// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/12/Screen.jack
/**
* Graphic screen library.
*/
class Screen {
static boolean color;
/** Initializes the Screen. */
function void init() {
let color = true;
return;
}
/** Erases the whole screen. */
function void clearScreen() {
var int address;
let address=16384;
while(address<24576){
do Memory.poke(address,0);
let address=address+1;
}
return;
}
/** Sets the color to be used in further draw commands
* where white = false, black = true. */
function void setColor(boolean b) {
let color=b;
return;
}
/** Draws the (x, y) pixel. */
function void drawPixel(int x, int y) {
var int i,divNum,address,remain,temp;
if((x>511)|(y>255)){
do Sys.error(11);
}
let i=1;
let divNum=Math.divide(x,16);
let address=16384+Math.multiply(y,32)+divNum;
let remain=x-Math.multiply(divNum,16);
let temp=Memory.peek(address);
while(remain>0){
let i=i+i;
let remain=remain-1;
}
//if color = false, negate the i to draw white pixel
if(color){
let temp=(temp|i);
}
else{
let i = ~i;
let temp = (temp&i);
}
do Memory.poke(address,temp);
return;
}
/** Draws a line from (x1, y1) to (x2, y2). */
function void drawLine(int x1, int y1, int x2, int y2) {
var int a,b,dx,dy,compDx,compDy,adyMinusbdx;
let dx=x2-x1;
let dy=y2-y1;
let compDx=Math.abs(dx)+1;
let compDy=Math.abs(dy)+1;
let a=0;
let b=0;
if (dy=0){
if(dx>0){
while(a<compDx){
do Screen.drawPixel(x1+a,y1);
let a=a+1;
}
return;
}
else{
while(a<compDx){
do Screen.drawPixel(x1-a,y1);
let a=a+1;
}
return;
}
}
if (dx=0){
if(dy>0){
while(a<compDy){
do Screen.drawPixel(x1,y1+a);
let a=a+1;
}
return;
}
else{
while(a<compDy){
do Screen.drawPixel(x1,y1-a);
let a=a+1;
}
return;
}
}
if((dx>0)&(dy>0)){
let adyMinusbdx=0;
while((a<compDx)&(b<compDy)){
do Screen.drawPixel(x1+a,y1+b);
if(adyMinusbdx<0){
let adyMinusbdx=adyMinusbdx+dy;
let a=a+1;
}
else{
let adyMinusbdx=adyMinusbdx-dx;
let b=b+1;
}
}
return;
}
if((dx<1)&(dy<1)){
let adyMinusbdx=0;
while((a<compDx)&(b<compDy)){
do Screen.drawPixel(x2+a,y2+b);
if(adyMinusbdx<0){
let adyMinusbdx=adyMinusbdx-dy;
let a=a+1;
}
else{
let adyMinusbdx=adyMinusbdx+dx;
let b=b+1;
}
}
return;
}
if((dx>0)&(dy<1)){
let adyMinusbdx=0;
while((a<compDx)&(b<compDy)){
do Screen.drawPixel(x1+a,y1-b);
if(adyMinusbdx<0){
let adyMinusbdx=adyMinusbdx-dy;
let a=a+1;
}
else{
let adyMinusbdx=adyMinusbdx-dx;
let b=b+1;
}
}
return;
}
if((dy>0)&(dx<1)){
let adyMinusbdx=0;
while((a<compDx)&(b<compDy)){
do Screen.drawPixel(x2+a,y2-b);
if(adyMinusbdx<0){
let adyMinusbdx=adyMinusbdx+dy;
let a=a+1;
}
else{
let adyMinusbdx=adyMinusbdx+dx;
let b=b+1;
}
}
return;
}
return;
}
/** Draws a filled rectangle where the top left corner
* is (x1, y1) and the bottom right corner is (x2, y2). */
function void drawRectangle(int x1, int y1, int x2, int y2) {
var int y;
let y=y1;
while(y<y2){
do Screen.drawLine(x1,y,x2,y);
let y=y+1;
}
do Screen.drawLine(x1,y,x2,y);
return;
}
/** Draws a filled circle of radius r around (cx, cy). */
function void drawCircle(int cx, int cy, int r) {
var int y,dy,dyPower,rPower,halfDistance,sqrNum,xLeft,xRight;
if((cx>511)|(cy>255)|(r>181)){
do Sys.error(12);
}
let dy=-r;
let rPower=Math.multiply(r,r);
while(dy<r){
let dyPower=Math.multiply(dy,dy);
let halfDistance=rPower-dyPower;
let sqrNum=Math.sqrt(halfDistance);
let xLeft=cx-sqrNum;
let xRight=cx+sqrNum;
let y=cy+dy;
do Screen.drawLine(xLeft,y,xRight,y);
let dy=dy+1;
}
do Screen.drawPixel(cx,cy+r);
return;
}
}
Output：
编码与字符的转换：
虽然我们早就对字符显示在屏幕上这种事情习以为常，但是它涉及的各项操作还真是挺复杂的。
首先要注意的是，由于全屏被分为23*64个字符区域，而每一行只有16个字段，因此，每一个字事实上都包含了两个字符的其中的一行（也就是说上下区域连续11个字节才表示两个完整的字符），所以说，奇数列和偶数列的字符操作是不同的：偶数列（从第0列开始）只需要将相应的表示填充位置的数字读入相应的字段，而奇数列则需要将该数字向右移8位，再加上原先的偶数列中的数据才能读入相应字段。
第二点，光标的设置并没有规定，但是设置为32（也就是空字符）操作起来相对方便一些，这样的话，光标移到哪里，就会直接将原区域的数据清零，方便接下来的操作。
// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/12/Output.jack
/**
* Handles writing characters to the screen.
* The text screen (256 columns and 512 roes) is divided into 23 text rows (0..22),
* each containing 64 text columns (0..63).
* Each row is 11 pixels high (including 1 space pixel), and 8 pixels wide
* (including 2 space pixels).
*/
class Output {
// Character map for printing on the left of a screen word
static Array charMaps;
static int cursorRow,cursorCol; //record the actual pixel line in 256*512
static int charRow,charCol; //record the char line in 23*64
/** Initializes the screen and locates the cursor at the screen's top-left. */
function void init() {
let cursorRow=0;
let cursorCol=0;
let charRow=0;
let charCol=0;
do Output.initMap();
return;
}
// Initalizes the character map array
function void initMap() {
var int i;
let charMaps = Array.new(127);
// black square (used for non printable characters)
do Output.create(0,63,63,63,63,63,63,63,63,63,0,0);
// Assigns the bitmap for each character in the charachter set.
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(35,0,18,18,63,18,18,63,18,18,0,0); // #
do Output.create(36,12,30,51,3,30,48,51,30,12,12,0); // $
do Output.create(37,0,0,35,51,24,12,6,51,49,0,0); // %
do Output.create(38,12,30,30,12,54,27,27,27,54,0,0); // &
do Output.create(39,12,12,6,0,0,0,0,0,0,0,0); // '
do Output.create(40,24,12,6,6,6,6,6,12,24,0,0); // (
do Output.create(41,6,12,24,24,24,24,24,12,6,0,0); // )
do Output.create(42,0,0,0,51,30,63,30,51,0,0,0); // *
do Output.create(43,0,0,0,12,12,63,12,12,0,0,0); // +
do Output.create(44,0,0,0,0,0,0,0,12,12,6,0); // ,
do Output.create(45,0,0,0,0,0,63,0,0,0,0,0); // -
do Output.create(46,0,0,0,0,0,0,0,12,12,0,0); // .
do Output.create(47,0,0,32,48,24,12,6,3,1,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(51,30,51,48,48,28,48,48,51,30,0,0); // 3
do Output.create(52,16,24,28,26,25,63,24,24,60,0,0); // 4
do Output.create(53,63,3,3,31,48,48,48,51,30,0,0); // 5
do Output.create(54,28,6,3,3,31,51,51,51,30,0,0); // 6
do Output.create(55,63,49,48,48,24,12,12,12,12,0,0); // 7
do Output.create(56,30,51,51,51,30,51,51,51,30,0,0); // 8
do Output.create(57,30,51,51,51,62,48,48,24,14,0,0); // 9
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(61,0,0,0,63,0,0,63,0,0,0,0); // =
do Output.create(62,0,0,3,6,12,24,12,6,3,0,0); // >
do Output.create(64,30,51,51,59,59,59,27,3,30,0,0); // @
do Output.create(63,30,51,51,24,12,12,0,12,12,0,0); // ?
do Output.create(65,12,30,51,51,63,51,51,51,51,0,0); // A ** TO BE FILLED **
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(68,15,27,51,51,51,51,51,27,15,0,0); // D
do Output.create(69,63,51,35,11,15,11,35,51,63,0,0); // E
do Output.create(70,63,51,35,11,15,11,3,3,3,0,0); // F
do Output.create(71,28,54,35,3,59,51,51,54,44,0,0); // G
do Output.create(72,51,51,51,51,63,51,51,51,51,0,0); // H
do Output.create(73,30,12,12,12,12,12,12,12,30,0,0); // I
do Output.create(74,60,24,24,24,24,24,27,27,14,0,0); // J
do Output.create(75,51,51,51,27,15,27,51,51,51,0,0); // K
do Output.create(76,3,3,3,3,3,3,35,51,63,0,0); // L
do Output.create(77,33,51,63,63,51,51,51,51,51,0,0); // M
do Output.create(78,51,51,55,55,63,59,59,51,51,0,0); // N
do Output.create(79,30,51,51,51,51,51,51,51,30,0,0); // O
do Output.create(80,31,51,51,51,31,3,3,3,3,0,0); // P
do Output.create(81,30,51,51,51,51,51,63,59,30,48,0);// Q
do Output.create(82,31,51,51,51,31,27,51,51,51,0,0); // R
do Output.create(83,30,51,51,6,28,48,51,51,30,0,0); // S
do Output.create(84,63,63,45,12,12,12,12,12,30,0,0); // T
do Output.create(85,51,51,51,51,51,51,51,51,30,0,0); // U
do Output.create(86,51,51,51,51,51,30,30,12,12,0,0); // V
do Output.create(87,51,51,51,51,51,63,63,63,18,0,0); // W
do Output.create(88,51,51,30,30,12,30,30,51,51,0,0); // X
do Output.create(89,51,51,51,51,30,12,12,12,30,0,0); // Y
do Output.create(90,63,51,49,24,12,6,35,51,63,0,0); // Z
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(94,8,28,54,0,0,0,0,0,0,0,0); // ^
do Output.create(95,0,0,0,0,0,0,0,0,0,63,0); // _
do Output.create(96,6,12,24,0,0,0,0,0,0,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(100,48,48,48,60,54,51,51,51,30,0,0); // d
do Output.create(101,0,0,0,30,51,63,3,51,30,0,0); // e
do Output.create(102,28,54,38,6,15,6,6,6,15,0,0); // f
do Output.create(103,0,0,30,51,51,51,62,48,51,30,0); // g
do Output.create(104,3,3,3,27,55,51,51,51,51,0,0); // h
do Output.create(105,12,12,0,14,12,12,12,12,30,0,0); // i
do Output.create(106,48,48,0,56,48,48,48,48,51,30,0); // j
do Output.create(107,3,3,3,51,27,15,15,27,51,0,0); // k
do Output.create(108,14,12,12,12,12,12,12,12,30,0,0); // l
do Output.create(109,0,0,0,29,63,43,43,43,43,0,0); // m
do Output.create(110,0,0,0,29,51,51,51,51,51,0,0); // n
do Output.create(111,0,0,0,30,51,51,51,51,30,0,0); // o
do Output.create(112,0,0,0,30,51,51,51,31,3,3,0); // p
do Output.create(113,0,0,0,30,51,51,51,62,48,48,0); // q
do Output.create(114,0,0,0,29,55,51,3,3,7,0,0); // r
do Output.create(115,0,0,0,30,51,6,24,51,30,0,0); // s
do Output.create(116,4,6,6,15,6,6,6,54,28,0,0); // t
do Output.create(117,0,0,0,27,27,27,27,27,54,0,0); // u
do Output.create(118,0,0,0,51,51,51,51,30,12,0,0); // v
do Output.create(119,0,0,0,51,51,51,63,63,18,0,0); // w
do Output.create(120,0,0,0,51,30,12,12,30,51,0,0); // x
do Output.create(121,0,0,0,51,51,51,62,48,24,15,0); // y
do Output.create(122,0,0,0,63,27,12,6,51,63,0,0); // z
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); // }
do Output.create(126,38,45,25,0,0,0,0,0,0,0,0); // ~
return;
}
// Creates a character map array of the given char index with the given values.
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;
}
// Returns the character map (array of size 11) for the given character
// If an invalid character is given, returns the character map of a black square.
function Array getMap(char c) {
if ((c < 32) | (c > 126)) {
let c = 0;
}
return charMaps[c];
}
/** Moves the cursor to the j抰h column of the i抰h row,
* and erases the character that was there. */
function void moveCursor(int i, int j) {
var boolean oddOrEven;
var int column,row,flag,tempVal;
var int divNum,address;
var int tempChar,oriChar,answer;
var Array zeroMap;
let flag=0;
if(i=23){
let cursorRow=0;
let cursorCol=0;
let charRow=0;
let charCol=0;
}
else{
let cursorRow=Math.multiply(i,11);
let cursorCol=Math.multiply(j,8);
let charRow=i;
let charCol=j;
}
let row=cursorRow;
let column=cursorCol;
//define zeroMap[]
let zeroMap = Output.getMap(32);
//find address
let divNum=Math.divide(column,16);
let address=16384+Math.multiply(row,32)+divNum;
//print char 0
let tempVal=Math.multiply(Math.divide(charCol,2),2);
if(tempVal=charCol){
let oddOrEven=true;
}
else{
let oddOrEven=false;
}
if(~oddOrEven){
while(flag<11){
let tempChar=Math.multiply(zeroMap[flag],256);
let oriChar=Memory.peek(address);
let oriChar=(oriChar&255);
let answer=tempChar+oriChar;
do Memory.poke(address,answer);
let address=address+32;
let flag=flag+1;
}
}
else{
while(flag<11){
do Memory.poke(address,zeroMap[flag]);
let address=address+32;
let flag=flag+1;
}
}
return;
}
/** Prints c at the cursor location and advances the cursor one
* column forward. */
function void printChar(char c) {
var int row,column;
var int i,divNum,address,oriChar,tempChar,answer,tempVal;
var boolean oddOrEven;
var Array characterMap;
let i=0;
let characterMap=Output.getMap(c);
let row=cursorRow;
let column=cursorCol;
//find address
let divNum=Math.divide(column,16);
let address=16384+Math.multiply(row,32)+divNum;
let tempVal=Math.multiply(Math.divide(charCol,2),2);
if(tempVal=charCol){
let oddOrEven=true;
}
else{
let oddOrEven=false;
}
if(~oddOrEven){
while(i<11){
let tempChar=Math.multiply(characterMap[i],256);
let oriChar=Memory.peek(address);
let answer=tempChar+oriChar;
do Memory.poke(address,answer);
let address=address+32;
let i=i+1;
}
}
else{
while(i<11){
do Memory.poke(address,characterMap[i]);
let address=address+32;
let i=i+1;
}
}
if(charCol=63){
do Output.println();
return;
}
else{
let charCol=charCol+1;
do Output.moveCursor(charRow,charCol);
return;
}
}
/** Prints s starting at the cursor location, and advances the
* cursor appropriately. */
function void printString(String s) {
var int strLength;
var char temp;
var int i;
let i=0;
let strLength=s.length();
while(i<strLength){
let temp = s.charAt(i);
do Output.printChar(temp);
let i=i+1;
}
return;
}
/** Prints i starting at the cursor location, and advances the
* cursor appropriately. */
function void printInt(int i) {
var String str;
let str = String.new(6);
do str.setInt(i);
do Output.printString(str);
return;
}
/** Advances the cursor to the beginning of the next line. */
function void println() {
let charRow=charRow+1;
let charCol=0;
do Output.moveCursor(charRow,charCol);
return;
}
/** Moves the cursor one column back. */
function void backSpace() {
var boolean oddOrEven;
var int column,row,flag,tempVal;
var int divNum,address;
var int tempChar,oriChar,answer;
var Array zeroMap;
if(charCol=0){
if(charRow>0){
let charRow=charRow-1;
let charCol=63;
}
}
else{
let charCol=charCol-1;
}
do Output.moveCursor(charRow,charCol);
return;
}
}
Keyboard：
Keyboard的实现相对简单，按照书上的伪代码操作即可。
// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/12/Keyboard.jack
/**
* A library for handling user input from the keyboard.
*/
class Keyboard {
/** Initializes the keyboard. */
function void init() {
return;
}
/**
* Returns the ASCII code (as char) of the currently pressed key,
* or 0 if no key is currently pressed.
* Recognizes all ASCII characters, as well as the following extension
* of action keys:
* New line = 128 = String.newline()
* Backspace = 129 = String.backspace()
* Left Arrow = 130
* Up Arrow = 131
* Right Arrow = 132
* Down Arrow = 133
* Home = 134
* End = 135
* Page Up = 136
* Page Down = 137
* Insert = 138
* Delete = 139
* ESC = 140
* F1 - F12 = 141 - 152
*/
function char keyPressed() {
return Memory.peek(24576);
}
/**
* Reads the next character from the keyboard.
* waits until a key is pressed and then released, then echoes
* the key to the screen, and returns the value of the pressed key.
*/
function char readChar() {
var char c;
while(~(Keyboard.keyPressed())){}
let c=Keyboard.keyPressed();
while(c=Keyboard.keyPressed()){}
do Output.printChar(c);
return c;
}
/**
* Prints the message on the screen, reads the next line
* (until a newline character) from the keyboard, and returns its value.
*/
function String readLine(String message) {
var String s;
var char c;
do Output.printString(message);
let s=String.new(100);
while(true){
let c=Keyboard.readChar();
if (c=128){
do Output.printChar(128);
return s;
}
if (c=129){
do s.eraseLastChar();
do Output.backSpace();
}
else{
let s=s.appendChar(c);
}
}
return s;
}
/**
* Prints the message on the screen, reads the next line
* (until a newline character) from the keyboard, and returns its
* integer value (until the first non numeric character).
*/
function int readInt(String message) {
var String s;
let s=Keyboard.readLine(message);
return s.intValue();
}
}
Sys：
Sys的实现也非常简单，需要注意的是wait函数，在实现它时，我们采取1ms=50times的策略模拟即可。
// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/12/Sys.jack
/**
* A library of basic system services.
*/
class Sys {
/** Performs all the initializations required by the OS. */
function void init() {
do Memory.init();
do Math.init();
do Screen.init();
do Output.init();
do Keyboard.init();
do Main.main();
do Sys.halt();
return;
}
/** Halts execution. */
function void halt() {
while(true){}
return;
}
/** Waits approximately duration milliseconds and then returns. */
function void wait(int duration) {
var int temp;
if(duration<0){
do Sys.error(1);
}
while(duration>0){
let temp=50;
while(temp>0){
let temp=temp-1;
}
let duration=duration-1;
}
return;
}
/** Prints the given error code in the form "ERR<errorCode>", and halts. */
function void error(int errorCode) {
var String s;
let s=String.new(3);
let s="ERR";
do Output.printString(s);
do Output.printInt(errorCode);
do Sys.halt();
return;
}
}
计算机系统要素：第十二章 操作系统
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。