The Elements of Computing Systems: Building a Modern Computer from First Principles (47 page)
Read The Elements of Computing Systems: Building a Modern Computer from First Principles Online
Authors: Noam Nisan,Shimon Schocken
BOOK: The Elements of Computing Systems: Building a Modern Computer from First Principles
13.2Mb size Format: txt, pdf, ePub
■ function char
backSpace
(): returns the backspace character;
backSpace
(): returns the backspace character;
■ function char
doubleQuote
(): returns the double quote (“) character;
doubleQuote
(): returns the double quote (“) character;
■ function char
newLine
(): returns the newline character.
12.2.3 ArraynewLine
(): returns the newline character.
This class enables the construction and disposal of arrays.
• function Array
new
(int size): constructs a new array of the given size;
• method void
dispose
(): disposes this array.
This class allows writing text on the screen.
■ function void
init
(): for internal use only;
init
(): for internal use only;
■ function void
moveCursor
(int i, int j): moves the cursor to the j-th column of the i-th row, and erases the character displayed there;
moveCursor
(int i, int j): moves the cursor to the j-th column of the i-th row, and erases the character displayed there;
■ function void
printChar
(char c): prints c at the cursor location and advances the cursor one column forward;
printChar
(char c): prints c at the cursor location and advances the cursor one column forward;
■ function void
printString
(String s): prints s starting at the cursor location and advances the cursor appropriately;
printString
(String s): prints s starting at the cursor location and advances the cursor appropriately;
■ function void
printInt
(int i): prints i starting at the cursor location and advances the cursor appropriately;
printInt
(int i): prints i starting at the cursor location and advances the cursor appropriately;
■ function void
println
(): advances the cursor to the beginning of the next line;
println
(): advances the cursor to the beginning of the next line;
■ function void
backSpace
(): moves the cursor one column back.
12.2.5 ScreenbackSpace
(): moves the cursor one column back.
This class allows drawing graphics on the screen. Column indices start at 0 and are left to right. Row indices start at 0 and are top to bottom. The screen size is hardware-dependant (in the Hack platform: 256 rows by 512 columns).
■ function void
init
(): for internal use only;
init
(): for internal use only;
■ function void
clearScreen
(): erases the entire screen;
clearScreen
(): erases the entire screen;
■ function void
setColor
(boolean b): sets a color (white = false, black = true) to be used for all further drawXXX commands;
setColor
(boolean b): sets a color (white = false, black = true) to be used for all further drawXXX commands;
■ function void
drawPixel
(int x, int y): draws the (x,y) pixel;
drawPixel
(int x, int y): draws the (x,y) pixel;
■ function void
drawLine
(int x1, int y1, int x2, int y2): draws a line from pixel (x1,y1) to pixel (x2,y2);
drawLine
(int x1, int y1, int x2, int y2): draws a line from pixel (x1,y1) to pixel (x2,y2);
■ function void
drawRectangle
(int x1, int y1, int x2, int y2): draws a filled rectangle whose top left corner is (x1,y1) and whose bottom right corner is (x2,y2);
drawRectangle
(int x1, int y1, int x2, int y2): draws a filled rectangle whose top left corner is (x1,y1) and whose bottom right corner is (x2,y2);
■ function void
drawCircle
(int x, int y, int r): draws a filled circle of radius r <= 181 around (x,y).
12.2.6 KeyboarddrawCircle
(int x, int y, int r): draws a filled circle of radius r <= 181 around (x,y).
This class allows reading inputs from a standard keyboard.
■ function void
init
(): for internal use only;
init
(): for internal use only;
■ function char
keyPressed
(): returns the character of the currently pressed key on the keyboard; if no key is currently pressed, returns 0;
keyPressed
(): returns the character of the currently pressed key on the keyboard; if no key is currently pressed, returns 0;
■ function char
readChar
(): waits until a key is pressed on the keyboard and released, then echoes the key to the screen and returns the character of the pressed key;
readChar
(): waits until a key is pressed on the keyboard and released, then echoes the key to the screen and returns the character of the pressed key;
■ function String
readLine
(String message): prints the message on the screen, reads the line (text until a newline character is detected) from the keyboard, echoes the line to the screen, and returns its value. This function also handles user backspaces;
readLine
(String message): prints the message on the screen, reads the line (text until a newline character is detected) from the keyboard, echoes the line to the screen, and returns its value. This function also handles user backspaces;
■ function int
readInt
(String message): prints the message on the screen, reads the line (text until a newline character is detected) from the keyboard, echoes the line to the screen, and returns its integer value (until the first non-digit character in the line is detected). This function also handles user backspaces.
12.2.7 MemoryreadInt
(String message): prints the message on the screen, reads the line (text until a newline character is detected) from the keyboard, echoes the line to the screen, and returns its integer value (until the first non-digit character in the line is detected). This function also handles user backspaces.
This class allows direct access to the main memory of the host platform.
■ function void
init
(): for internal use only;
init
(): for internal use only;
■ function int
peek
(int address): returns the value of the main memory at this address;
peek
(int address): returns the value of the main memory at this address;
■ function void
poke
(int address, int value): sets the contents of the main memory at this address to value;
poke
(int address, int value): sets the contents of the main memory at this address to value;
■ function Array
alloc
(int size): finds and allocates from the heap a memory block of the specified size and returns a reference to its base address;
alloc
(int size): finds and allocates from the heap a memory block of the specified size and returns a reference to its base address;
■ function void
deAlloc
(Array o): De-allocates the given object and frees its memory space.
12.2.8 SysdeAlloc
(Array o): De-allocates the given object and frees its memory space.
This class supports some execution-related services.
■ function void
init
(): calls the init functions of the other OS classes and then calls the Main . main () function. For internal use only;
init
(): calls the init functions of the other OS classes and then calls the Main . main () function. For internal use only;
■ function void
halt
(): halts the program execution;
halt
(): halts the program execution;
■ function void
error
(int errorCode): prints the error code on the screen and halts;
error
(int errorCode): prints the error code on the screen and halts;
■ function void
wait
(int duration): waits approximately duration milliseconds and returns.
12.3 Implementationwait
(int duration): waits approximately duration milliseconds and returns.
The operating system described in the previous section can be implemented as a collection of Jack classes. Each OS subroutine can be implemented as a Jack constructor, function, or method. The API of all these subroutines was given in section 12.2, and key algorithms were presented in section 12.1. This section provides some additional hints and suggestions for completing this implementation. Final technical details and test programs for unit-testing all the OS services are given in section 12.5. Note that most of the subroutines specified in the OS API are rather simple, requiring straightforward Jack programming. Thus we focus here only on the implementation of selected OS subroutines.
Some OS classes require class-level initialization. For example, some mathematical functions can run more quickly if they can use previously calculated values, kept in some static array, constructed once and for all in the Math class. As a rule, when an OS class Xxx needs some initialization code, this code should be embedded in a single function called Xxx.init(). Later in this section we explain how these init () functions are activated when the computer boots up and the OS starts running.
12.3.1 MathMath.multiply(), Math.divide(): The algorithms in figures 12.1 and 12.2 are designed to operate on non-negative integers only. A simple way of handling negative numbers is applying the algorithms on absolute values and then setting the sign appropriately. For the multiplication algorithm, this is not really needed: it turns out that if the multiplicands are given in 2’s complement, their product will be correct with no further ado.
Note that in each iteration j of the algorithm in figure 12.1, the j-th bit of the second number is extracted. We suggest encapsulating this operation in the following function:
bit(x,j): Returns true if the
j
-th bit of the integer
x
is 1 and false otherwise.
j
-th bit of the integer
x
is 1 and false otherwise.
The bit(x,j) function can be easily implemented using shifting operations. Alas, Jack does not support shifting. Instead, to speed up this function implementation in Jack, it may be convenient to define a fixed static array of length 16, say twoToThe[ j], whose
j
-th location holds the value 2 to the power of
j
. This array may be initialized once (in Math . init), and then used, via bitwise Boolean operations, in the implementation of bit (x , j).
j
-th location holds the value 2 to the power of
j
. This array may be initialized once (in Math . init), and then used, via bitwise Boolean operations, in the implementation of bit (x , j).
In figure 12.2,
y
is multiplied by a factor of 2 until
y
> x. A detail that needs to be taken into account is that
y
can overflow. The overflow can be detected by noting when
y
becomes negative.
y
is multiplied by a factor of 2 until
y
> x. A detail that needs to be taken into account is that
y
can overflow. The overflow can be detected by noting when
y
becomes negative.
Math.sqrt(): Since the calculation of (
y
+ 2
j
)
2
in figure 12.3 can overflow, the result may be an abnormally negative number. This problem can be addressed by (efficiently) changing the algorithm’s
if
logic to if ((
y
+ 2
j
)
2
≤
x
) and ((
y
+ 2
j
)
2
> 0) then
y
=
y
+ 2
j
12.3.2 Stringy
+ 2
j
)
2
in figure 12.3 can overflow, the result may be an abnormally negative number. This problem can be addressed by (efficiently) changing the algorithm’s
if
logic to if ((
y
+ 2
j
)
2
≤
x
) and ((
y
+ 2
j
)
2
> 0) then
y
=
y
+ 2
j
As explained in section 12.1.4, string objects can be implemented as arrays. In a similar vein, all the string related services can be implemented as operations on arrays. An important implementation detail is that the actual length of the string must be maintained throughout these operations and that array entries beyond this length are not considered part of the string.
String.intValue, String.setInt:
These functions can be implemented using the algorithms from figures 12.4 and 12.5, respectively. Note that both algorithms don’t handle negative numbers—a detail that must be handled by the implementation.
These functions can be implemented using the algorithms from figures 12.4 and 12.5, respectively. Note that both algorithms don’t handle negative numbers—a detail that must be handled by the implementation.
All other subroutines in this class are straightforward. Note that the ASCII codes of newline, backspace, and doubleQuote are 128, 129, and 34, respectively.
12.3.3 ArrayNote that Array.new ( ) is not a constructor, but rather a function (despite its name). Therefore, memory space for a new array should be explicitly allocated using a call to Memory.alloc ( ). Similarly, de-allocation of arrays must be done explicitly using Memory.deAlloc ( ).
12.3.4 OutputCharacter Bitmaps We suggest using character bitmaps of 11 rows by 8 columns, leading to 23 lines of 64 characters each. Since designing and building bitmaps for all the printable ASCII characters is quite a burden, we supply predefined bitmaps (except for one or two characters, left to you as an exercise). Specifically, we supply a skeletal Output class containing Jack code that defines, for each printable ASCII character, an array that holds its bitmap (implementing a font that we created). The array consists of 11 entries, each corresponding to a row of pixels. In particular, the value of entry j is a binary number whose bits represent the 8 pixels that render the character’s image in the
j
-th row of its bitmap.
12.3.5 Screenj
-th row of its bitmap.
Screen.drawPixel():
Drawing a pixel on the screen is done by directly accessing the screen’s memory map using Memory.peek() and Memory.poke(). Recall that the memory map of the screen on the Hack platform specifies that the pixel at column c and row
r
(0 ≤
c
≤ 511, 0 ≤
r
≤ 255) is mapped to the
c
%16 bit of memory location 16384 + r · 32 +
c
/16. Notice that drawing a single pixel requires changing a single bit in the accessed word, a task that can be achieved in Jack using bit-wise operations.
Drawing a pixel on the screen is done by directly accessing the screen’s memory map using Memory.peek() and Memory.poke(). Recall that the memory map of the screen on the Hack platform specifies that the pixel at column c and row
r
(0 ≤
c
≤ 511, 0 ≤
r
≤ 255) is mapped to the
c
%16 bit of memory location 16384 + r · 32 +
c
/16. Notice that drawing a single pixel requires changing a single bit in the accessed word, a task that can be achieved in Jack using bit-wise operations.
Screen.drawLine ( ):
The algorithm from figure 12.8a can potentially lead to overflow. However, the efficiency improvement suggested in figure 12.8b also eliminates the overflow problem.
The algorithm from figure 12.8a can potentially lead to overflow. However, the efficiency improvement suggested in figure 12.8b also eliminates the overflow problem.
Screen.drawCircle ( ):
Likewise, the algorithm from figure 12.9 can potentially lead to overflow. Limiting circle radii to be at most 181 avoids this problem.
12.3.6 KeyboardLikewise, the algorithm from figure 12.9 can potentially lead to overflow. Limiting circle radii to be at most 181 avoids this problem.
In the Hack platform, the memory map of the keyboard is a single 16-bit word located at memory address 24576.
Keyboard.keyPressed ( ):
This function provides “raw” (direct) access to this memory location and can be implemented easily using Memory.peek().
This function provides “raw” (direct) access to this memory location and can be implemented easily using Memory.peek().
Keyboard.readChar, Keyboard.readString:
These functions provide “cooked” access to single character inputs and to string inputs, respectively. Proposed cooking instructions appear in figures 12.12 and 12.13.
12.3.7 MemoryThese functions provide “cooked” access to single character inputs and to string inputs, respectively. Proposed cooking instructions appear in figures 12.12 and 12.13.
Memory.peek(),
Memory.poke ( ):
These functions are supposed to provide direct access to the underlying memory. How can this be accomplished in a high-level language? As it turns out, the Jack language includes a trapdoor that enables programmers to gain complete control of the computer’s memory. This hacking trick can be exploited to implement peek and poke using plain Jack programming.
Memory.poke ( ):
These functions are supposed to provide direct access to the underlying memory. How can this be accomplished in a high-level language? As it turns out, the Jack language includes a trapdoor that enables programmers to gain complete control of the computer’s memory. This hacking trick can be exploited to implement peek and poke using plain Jack programming.
The trick is based on an anomalous use of reference variables (pointers). Specifically, the Jack language does not prevent the programmer from assigning a constant to a reference variable. This constant can then be treated as an absolute memory address. In particular, when the reference variable happens to be an array, this trick can give convenient and direct access to the entire computer memory. Figure 12.4 gives the details.
Following the first two lines of figure 12.14, the base of the memory array points to the first address in the computer’s RAM. To set or get the value of the RAM location whose physical address is j, all we have to do is manipulate the array entry memory[j]. This will cause the compiler to manipulate the RAM location whose address is 0+j, which is precisely what is desired.
Other books
Hearts Racing by Hodgson, Jim
Kilts and Kisses by Victoria Roberts
Salem's Sight by Eden Elgabri
The Deep by Nick Cutter
Reclaimed by Sarah Guillory
The Betting Season (A Regency Season Book) by Knight-Catania, Jerrica, Gayle, Catherine, Stone, Ava, Charles, Jane
Queen for a Day (BBW Billionaire Romance) by Christa Wick
Hunted by James Alan Gardner
Jack by Liesl Shurtliff
Shadow of the Father by Kyell Gold
