screen03.html

﻿<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
	<title>Lesson 8 Screen03</title>
	<link href="stylesheet.css" rel="Stylesheet" type="text/css" />
	<script language="javascript" type="text/javascript" src="script.js"></script>
</head>
<body>
	<div id="contentAll">
		<div id="courseHead">
			<h1>
				Lesson 8 Screen03</h1>
		</div>
		<div id="pageAll">
			<div id="pageBody">
				<p>
					The Screen03 lesson builds on Screen02, by teaching how to draw text, and also a
					small feature on the command line arguments of the operating system. It is assumed
					you have the code for the <a href="screen02.html">Lesson 7: Screen02</a> operating
					system as a basis.</p>
				<div class="ucampas-toc">
				</div>
				<h2 id="stringtheory">
					1 String Theory</h2>
				<p>
					So, our task for this operating system is to draw text. We have several problems
					to address, the most pressing of which is probably about storing text. Unbelievably
					text has been one of the biggest flaws on computers to date. What should have been
					a straightforward type of data has brought down operating systems, crippled otherwise
					wonderful encryption, and caused many problems for users of different alphabets.
					Nevertheless, it is an incredibly important type of data, as it is an excellent
					link between the computer and the user. Text can be sufficiently structured that
					the operating system understands it, as well as sufficiently readable that humans
					can use it.
				</p>
				<div class="informationBox">
					<p>
						Variable data types such as text require much more complex handling.</p>
				</div>
				<p>
					So how exactly is text stored? Simply enough, we have some system by which we give
					each letter a unique number, and then store a sequence of such numbers. Sounds easy.
					The problem is that the number of numbers is not fixed. Some pieces of text are
					longer than others. With storing ordinary numbers, we have some fixed limit, e.g.
					32 bits, and then we can't go beyond that, we write methods that use numbers of
					that length, etc. In terms of text, or strings as we often call it, we want to write
					functions that work on variable length strings, otherwise we would need a lot of
					functions! This is not a problem for numbers normally, as there are only a few common
					number formats (byte, word, half, double).</p>
				<div class="informationBox">
					<p>
						Buffer overrun attacks have plagued computers for years. Recently, the Wii, Xbox
						and Playstation 2 all suffered buffer overrun attacks, as well as large systems like
						Microsoft's Web and Database servers.</p>
				</div>
				<p>
					So, how do we determine how long the string is? I think the obvious answer is just
					to store how long the string is, and then to store the characters that make it up.
					This is called length prefixing, as the length comes before the string. Unfortunately,
					the pioneers of computer science did not agree. They felt it made more sense to
					have a special character called the null terminator (denoted \0) which represents
					when a string ends. This does indeed simplify many string algorithms, as you just
					keep working until the null terminator. Unfortunately this is the source of many
					security issues. What if a malicious user gives you a very long string? What if
					you didn't have enough space to store it. You might run a string copying function
					that copies until the null terminator, but because the string is so long, it overwrites
					your program. This may sound far fetched, but nevertheless, such buffer overrun attacks
					are incredibly common. Length prefixing mitigates this problem as it is easy to
					deduce the size of the buffer required to store the string. As an operating system
					developer, I leave it to you to decide how best to store text.
				</p>
				<p>
					The next thing we need to establish is how best to map characters to numbers. Fortunately,
					this is reasonably well standardised, so you have two major choices, Unicode and
					ASCII. Unicode maps almost every single useful symbol that can be written to a number,
					in exchange for having a lot more numbers, and a more complicated encoding system.
					ASCII uses one byte per character, and so only stores the Latin alphabet, numbers,
					a few symbols and a few special characters. Thus, ASCII is very easy to implement,
					compared to Unicode, in which not every character takes the same space, making string
					algorithms tricky. Normally operating systems use ASCII for strings which will not
					be displayed to end users (but perhaps to developers or experts), and Unicode for
					displaying messages to users, as Unicode can support things like Japanese characters,
					and so could be localised.
				</p>
				<p>
					Fortunately for us, this decision is irrelevant at the moment, as the first 128
					characters of both are exactly the same, and are encoded exactly the same.</p>
				<table class="monoCellTable">
					<caption>
						Table 1.1 ASCII/Unicode symbols 0-127</caption>
					<thead>
						<tr>
							<th>
							</th>
							<th>
								0
							</th>
							<th>
								1
							</th>
							<th>
								2
							</th>
							<th>
								3
							</th>
							<th>
								4
							</th>
							<th>
								5
							</th>
							<th>
								6
							</th>
							<th>
								7
							</th>
							<th>
								8
							</th>
							<th>
								9
							</th>
							<th>
								a
							</th>
							<th>
								b
							</th>
							<th>
								c
							</th>
							<th>
								d
							</th>
							<th>
								e
							</th>
							<th>
								f
							</th>
						</tr>
					</thead>
					<tbody>
						<tr>
							<th>
								00
							</th>
							<td title="Null Terminator" class="cellBlue">
								NUL
							</td>
							<td title="Start of Header" class="cellBlue">
								SOH
							</td>
							<td title="Start of Text" class="cellBlue">
								STX
							</td>
							<td title="End of Text" class="cellBlue">
								ETX
							</td>
							<td title="End of Transmission" class="cellBlue">
								EOT
							</td>
							<td title="Enquiry" class="cellBlue">
								ENQ
							</td>
							<td title="Acknowledgment" class="cellBlue">
								ACK
							</td>
							<td title="Bell" class="cellBlue">
								BEL
							</td>
							<td title="Backspace" class="cellBlue">
								BS
							</td>
							<td title="Horizontal Tab" class="cellBlue">
								HT
							</td>
							<td title="Line Feed" class="cellBlue">
								LF
							</td>
							<td title="Vertical Tab" class="cellBlue">
								VT
							</td>
							<td title="Form Feed" class="cellBlue">
								FF
							</td>
							<td title="Carriage Return" class="cellBlue">
								CR
							</td>
							<td title="Shift Out" class="cellBlue">
								SO
							</td>
							<td title="Shift In" class="cellBlue">
								SI
							</td>
						</tr>
						<tr>
							<th>
								10
							</th>
							<td title="Data Link Escape" class="cellBlue">
								DLE
							</td>
							<td title="Device Control 1" class="cellBlue">
								DC1
							</td>
							<td title="Device Control 2" class="cellBlue">
								DC2
							</td>
							<td title="Device Control 3" class="cellBlue">
								DC3
							</td>
							<td title="Device Control 4" class="cellBlue">
								DC4
							</td>
							<td title="Negative Acknowledgement" class="cellBlue">
								NAK
							</td>
							<td title="Synchronous Idle" class="cellBlue">
								SYN
							</td>
							<td title="End of Transmission Block" class="cellBlue">
								ETB
							</td>
							<td title="Cancel" class="cellBlue">
								CAN
							</td>
							<td title="End of Medium" class="cellBlue">
								EM
							</td>
							<td title="Substitute" class="cellBlue">
								SUB
							</td>
							<td title="Escape" class="cellBlue">
								ESC
							</td>
							<td title="File Separator" class="cellBlue">
								FS
							</td>
							<td title="Group Separator" class="cellBlue">
								GS
							</td>
							<td title="Record Separator" class="cellBlue">
								RS
							</td>
							<td title="Unit Separator" class="cellBlue">
								US
							</td>
						</tr>
						<tr>
							<th>
								20
							</th>
							<td>
								&#20;
							</td>
							<td>
								!
							</td>
							<td>
								"
							</td>
							<td>
								#
							</td>
							<td>
								$
							</td>
							<td>
								%
							</td>
							<td>
								&
							</td>
							<td>
								.
							</td>
							<td>
								(
							</td>
							<td>
								)
							</td>
							<td>
								*
							</td>
							<td>
								+
							</td>
							<td>
								,
							</td>
							<td>
								-
							</td>
							<td>
								.
							</td>
							<td>
								/
							</td>
						</tr>
						<tr>
							<th>
								30
							</th>
							<td>
								0
							</td>
							<td>
								1
							</td>
							<td>
								2
							</td>
							<td>
								3
							</td>
							<td>
								4
							</td>
							<td>
								5
							</td>
							<td>
								6
							</td>
							<td>
								7
							</td>
							<td>
								8
							</td>
							<td>
								9
							</td>
							<td>
								:
							</td>
							<td>
								;
							</td>
							<td>
								&lt;
							</td>
							<td>
								=
							</td>
							<td>
								&gt;
							</td>
							<td>
								?
							</td>
						</tr>
						<tr>
							<th>
								40
							</th>
							<td>
								@
							</td>
							<td>
								A
							</td>
							<td>
								B
							</td>
							<td>
								C
							</td>
							<td>
								D
							</td>
							<td>
								E
							</td>
							<td>
								F
							</td>
							<td>
								G
							</td>
							<td>
								H
							</td>
							<td>
								I
							</td>
							<td>
								J
							</td>
							<td>
								K
							</td>
							<td>
								L
							</td>
							<td>
								M
							</td>
							<td>
								N
							</td>
							<td>
								O
							</td>
						</tr>
						<tr>
							<th>
								50
							</th>
							<td>
								P
							</td>
							<td>
								Q
							</td>
							<td>
								R
							</td>
							<td>
								S
							</td>
							<td>
								T
							</td>
							<td>
								U
							</td>
							<td>
								V
							</td>
							<td>
								W
							</td>
							<td>
								X
							</td>
							<td>
								Y
							</td>
							<td>
								Z
							</td>
							<td>
								[
							</td>
							<td>
								\
							</td>
							<td>
								]
							</td>
							<td>
								^
							</td>
							<td>
								_
							</td>
						</tr>
						<tr>
							<th>
								60
							</th>
							<td>
								`
							</td>
							<td>
								a
							</td>
							<td>
								b
							</td>
							<td>
								c
							</td>
							<td>
								d
							</td>
							<td>
								e
							</td>
							<td>
								f
							</td>
							<td>
								g
							</td>
							<td>
								h
							</td>
							<td>
								i
							</td>
							<td>
								j
							</td>
							<td>
								k
							</td>
							<td>
								l
							</td>
							<td>
								m
							</td>
							<td>
								n
							</td>
							<td>
								o
							</td>
						</tr>
						<tr>
							<th>
								70
							</th>
							<td>
								p
							</td>
							<td>
								q
							</td>
							<td>
								r
							</td>
							<td>
								s
							</td>
							<td>
								t
							</td>
							<td>
								u
							</td>
							<td>
								v
							</td>
							<td>
								w
							</td>
							<td>
								x
							</td>
							<td>
								y
							</td>
							<td>
								z
							</td>
							<td>
								{
							</td>
							<td>
								|
							</td>
							<td>
								}
							</td>
							<td>
								~
							</td>
							<td title="Delete" class="cellBlue">
								DEL
							</td>
						</tr>
					</tbody>
				</table>
				<p>
					The table shows the first 128 symbols. The hexadecimal representation of the number
					for a symbol is the row value added to the column value, for example A is 41<sub>16</sub>.
					What you may find surprising is the first two rows, and the very last value. These
					33 special characters are not printed at all. In fact, these days, many are ignored.
					They exist because ASCII was originally intended as a system for transmitting data over
					computer networks, and so a lot more information than just the symbols had
					to be sent. The key special symbols that you should learn are NUL, the null terminator
					character I mentioned before, HT, horizontal tab is what we normally refer to as
					a tab and LF, the line feed character is used to make a new line. You may wish to
					research and use the other characters for special meanings in your operating system.</p>
				<h2 id="characters">
					2 Characters</h2>
				<p>
					So, now that we know a bit about strings, we can start to think about how they're
					displayed. The fundamental thing we need to do in order to be able to display a
					string is to be able to display a character. Our first task will be making a DrawCharacter
					function which takes in a character to draw and a location, and then draws the character.</p>
				<div class="informationBox">
					<p>
						The true type font format used in many Operating Systems is so powerful, it has
						its own assembly language built in to ensure letters look correct at any resolution.</p>
				</div>
				<p>
					Naturally, this leads to a discussion about fonts. We already know there are many
					ways to display any given letter in accordance with font choice. So how does a font
					work? In the very early days of computer science, a font was just a series of little
					pictures of all the letters, called a bitmap font, and all the draw character method
					would do is copy one of the pictures to the screen. The trouble with this is when
					people want to resize the text. Sometimes we need big letters, and sometimes small.
					Although we could keep drawing new pictures for every font at every size with every
					character, this would get tedious. Thus, vector fonts were invented. in vector fonts,
					rather than containing an image of the font, the font file contains a description
					of how to draw it, e.g. an 'o' could be circle with radius half that of the maximum
					letter height. Modern operating systems use such fonts almost exclusively, as they
					are perfect at any resolution.</p>
				<p>
					Unfortunately, much though I would love to include an implementation of one of the
					vector font formats, it would take up the remainder of this website. Thus, we will
					implement a bitmap font, though if you wish to make a decent graphical operating
					system, a vector font would be useful.</p>
				<table class="sideMono">
					<tbody>
						<tr>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
						</tr>
						<tr>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
						</tr>
						<tr>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
						</tr>
						<tr>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellWhite">
								1
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
						</tr>
						<tr>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellWhite">
								1
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellWhite">
								1
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
						</tr>
						<tr>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellWhite">
								1
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellWhite">
								1
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
						</tr>
						<tr>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellWhite">
								1
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellWhite">
								1
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
						</tr>
						<tr>
							<td class="cellBlack">
								0
							</td>
							<td class="cellWhite">
								1
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellWhite">
								1
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
						</tr>
						<tr>
							<td class="cellBlack">
								0
							</td>
							<td class="cellWhite">
								1
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellWhite">
								1
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
						</tr>
						<tr>
							<td class="cellBlack">
								0
							</td>
							<td class="cellWhite">
								1
							</td>
							<td class="cellWhite">
								1
							</td>
							<td class="cellWhite">
								1
							</td>
							<td class="cellWhite">
								1
							</td>
							<td class="cellWhite">
								1
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
						</tr>
						<tr>
							<td class="cellWhite">
								1
							</td>
							<td class="cellWhite">
								1
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellWhite">
								1
							</td>
							<td class="cellWhite">
								1
							</td>
							<td class="cellBlack">
								0
							</td>
						</tr>
						<tr>
							<td class="cellWhite">
								1
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellWhite">
								1
							</td>
							<td class="cellBlack">
								0
							</td>
						</tr>
						<tr>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
						</tr>
						<tr>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
						</tr>
						<tr>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
						</tr>
						<tr>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
							<td class="cellBlack">
								0
							</td>
						</tr>
					</tbody>
				</table>
				<p>
					On the downloads page, I have included several '.bin' files in the font section.
					These are just raw binary data files for a few fonts. For this tutorial, pick your
					favourite from the monospace, monochrome, 8x16 section. Download it and store it
					in the 'source' directory as 'font.bin'. These files are just monochrome images
					of each of the letters in turn, with each letter being exactly 8 by 16 pixels. Thus,
					each takes 16 bytes, the first byte being the top row, the second the next, etc.</p>
				<p>
					The diagram shows the 'A' character in the monospace, monochrome, 8x16 font Bitstream
					Vera Sans Mono. In the file, we would find this starting at the 41<sub>16</sub>
					&times; 10<sub>16</sub> = 410<sub>16</sub>th byte as the following sequence in hexadecimal:</p>
				<p>
					00, 00, 00, 10, 28, 28, 28, 44, 44, 7C, C6, 82, 00, 00, 00, 00</p>
				<p>
					We're going to use a monospace font here, because in a monospace font every character
					is the same size. Unfortunately, yet another complication with most fonts is that
					the character's widths vary, leading to more complex display code. I've included
					a few other fonts on the downloads page, as well as an explanation of the format
					I've stored them all in.</p>
				<p>
					So let's get down to business. Copy the following to 'drawing.s' after the <span
						class="armCodeInline">.int 0</span> of graphicsAddress.
				</p>
				<div class="armCodeBlock"><p>
					.align 4<br />
					font:<br />
					.incbin "font.bin"<br />
				</div>
				<div class="commandBox"><p>
					<span class="armCodeInline">.incbin "file"</span> inserts the binary data from the
					file <span class="armCodeInline">file</span>.
				</div>
				<p>
					This code copies the font data from the file to the address labelled font. We've
					used an <span class="armCodeInline">.align 4</span> here to ensure each character
					starts on a multiple of 16 bytes, which can be used for a speed trick later.</p>
				<p>
					Now we want to write the draw character method. I'll give the pseudo code for this,
					so you can try to implement it yourself if you want to. Conventionally &gt;&gt;
					means logical shift right.</p>
				<div class="pseudoCodeBlock"><p>
					<span class="keyword">function</span> drawCharacter(r0 <span class="keyword">is</span>
					character, r1 <span class="keyword">is</span> x, r2 <span class="keyword">is</span>
					y)<br />
					<div class="indent"><p>
						<span class="keyword">if </span>character &gt; 127 <span class="keyword">then exit</span>
						<br />
						<span class="keyword">set</span> charAddress <span class="keyword">to</span> font
						+ character &times; 16<br />
						<span class="keyword">for </span>row = 0 <span class="keyword">to </span>15<br />
						<div class="indent"><p>
							<span class="keyword">set </span>bits <span class="keyword">to </span>readByte(charAddress
							+ row)<br />
							<span class="keyword">for </span>bit = 0 <span class="keyword">to </span>7<br />
							<div class="indent"><p>
								<span class="keyword">if test</span>(bits &gt;&gt; bit, 0x1)<br />
								<span class="keyword">then setPixel</span>(x + bit, y + row)<br />
							</div><p>
							<span class="keyword">next</span><br />
						</div><p>
						<span class="keyword">next</span><br />
						<span class="keyword">return </span>r0 = 8, r1 = 16<br />
					</div><p>
					<span class="keyword">end function</span><br />
				</div>
				<p>
					If implemented directly, this is deliberately not very efficient. With things like
					drawing characters, efficiency is a top priority, as we will do it a lot. Let's
					explore some improvements that bring this closer to optimal assembly code. Firstly,
					we have a &times; 16, which by now you should spot is the same as a logical shift
					left by 4 places. Next we have a variable row, which is only ever added to charAddress
					and to y. Thus, we can eliminate it by increasing these variables instead. The only
					issue now is how to tell when we've finished. This is where the <span class="armCodeInline">
						.align 4</span> comes in handy. We know that charAddress will start with the
					low nibble containing 0. This means we can see how far into the character data we
					are by checking that low nibble.</p>
				<p>
					Though we can eliminate the need for bits, we must introduce a new variable to do
					so, so it is best left in. The only other improvement that can be made is to remove
					the nested <span class="pseudoCodeInline">bits &gt;&gt; bit</span>.</p>
				<div class="pseudoCodeBlock"><p>
					<span class="keyword">function</span> drawCharacter(r0 <span class="keyword">is</span>
					character, r1 <span class="keyword">is</span> x, r2 <span class="keyword">is</span>
					y)<br />
					<div class="indent"><p>
						<span class="keyword">if </span>character &gt; 127 <span class="keyword">then exit</span>
						<br />
						<span class="keyword">set</span> charAddress <span class="keyword">to</span> font
						+ character &lt;&lt; 4<br />
						<span class="keyword">loop</span><br />
						<div class="indent"><p>
							<span class="keyword">set </span>bits <span class="keyword">to </span>readByte(charAddress)<br />
							<span class="keyword">set </span>bit <span class="keyword">to</span> 8<br />
							<span class="keyword">loop</span><br />
							<div class="indent"><p>
								<span class="keyword">set</span> bits <span class="keyword">to</span> bits &lt;&lt;
								1<br />
								<span class="keyword">set</span> bit <span class="keyword">to</span> bit - 1<br />
								<span class="keyword">if test</span>(bits, 0x100)<br />
								<span class="keyword">then setPixel</span>(x + bit, y)<br />
							</div><p>
							<span class="keyword">until </span>bit = 0<br />
							<span class="keyword">set</span> y <span class="keyword">to</span> y + 1<br />
							<span class="keyword">set</span> chadAddress <span class="keyword">to</span> chadAddress
							+ 1<br />
						</div><p>
						<span class="keyword">until</span> charAddress <span class="keyword">AND</span>
						0b1111 = 0<br />
						<span class="keyword">return </span>r0 = 8, r1 = 16<br />
					</div><p>
					<span class="keyword">end function</span><br />
				</div>
				<p>
					Now we've got code that is much closer to assembly code, and is near optimal. Below
					is the assembly code version of the above.</p>
				<div class="armCodeBlock"><p>
					.globl DrawCharacter<br />
					DrawCharacter:<br />
					cmp r0,#127<br />
					movhi r0,#0<br />
					movhi r1,#0<br />
					movhi pc,lr<br />
					<br />
					push {r4,r5,r6,r7,r8,lr}<br />
					x .req r4<br />
					y .req r5<br />
					charAddr .req r6<br />
					mov x,r1<br />
					mov y,r2<br />
					ldr charAddr,=font<br />
					add charAddr, r0,lsl #4<br />
					<br />
					lineLoop$:<br />
					<div class="indent"><p>
						bits .req r7<br />
						bit .req r8<br />
						ldrb bits,[charAddr]<br />
						mov bit,#8<br />
						<br />
						charPixelLoop$:<br />
						<div class="indent"><p>
							subs bit,#1<br />
							blt charPixelLoopEnd$<br />
							lsl bits,#1<br />
							tst bits,#0x100<br />
							beq charPixelLoop$<br />
							<br />
							add r0,x,bit<br />
							mov r1,y<br />
							bl DrawPixel<br />
							<br />
							teq bit,#0<br />
							bne charPixelLoop$<br />
						</div><p>
						charPixelLoopEnd$:<br />
						.unreq bit<br />
						.unreq bits<br />
						add y,#1<br />
						add charAddr,#1<br />
						tst charAddr,#0b1111<br />
						bne lineLoop$<br />
					</div><p>
					.unreq x<br />
					.unreq y<br />
					.unreq charAddr<br />
					<br />
					width .req r0<br />
					height .req r1<br />
					mov width,#8<br />
					mov height,#16<br />
					<br />
					pop {r4,r5,r6,r7,r8,pc}<br />
					.unreq width<br />
					.unreq height<br />
				</div>
				<h2 id="strings">
					3 Strings</h2>
				<p>
					Now that we can draw characters, we can draw text. We need to make a method that,
					for a given string, draws each character in turn, at incrementing positions. To
					be nice, we shall also implement new lines and tabs. It's decision time as far as
					null terminators are concerned, and if you want to make your operating system use
					them, feel free by changing the code below. To avoid the issue, I will have the
					length of the string passed as an argument to the DrawString function, along with
					the address of the string, and the x and y coordinates.</p>
				<div class="pseudoCodeBlock"><p>
					<span class="keyword">function </span>drawString(r0 <span class="keyword">is</span>
					string, r1 <span class="keyword">is</span> length, r2 <span class="keyword">is</span>
					x, r3 <span class="keyword">is</span> y)<br />
					<div class="indent"><p>
						<span class="keyword">set</span> x0 <span class="keyword">to</span> x<br />
						<span class="keyword">for</span> pos = 0 <span class="keyword">to</span> length
						- 1<br />
						<div class="indent"><p>
							<span class="keyword">set</span> char <span class="keyword">to</span> loadByte(string
							+ pos)<br />
							<span class="keyword">set</span> (cwidth, cheight) <span class="keyword">to</span>
							DrawCharacter(char, x, y)<br />
							<span class="keyword">if</span> char = '\n' <span class="keyword">then</span> <span
								class="comment">/* \n is short hand for the character LF */</span><br />
							<div class="indent"><p>
								<span class="keyword">set</span> x <span class="keyword">to</span> x0<br />
								<span class="keyword">set</span> y <span class="keyword">to</span> y + cheight<br />
							</div><p>
							<span class="keyword">otherwise if</span> char = '\t' <span class="keyword">then</span>
							<span class="comment">/* \t is short hand for the character HT */</span><br />
							<div class="indent"><p>
								<span class="keyword">set</span> x1 <span class="keyword">to</span> x<br />
								<span class="keyword">until</span> x1 &gt; x0<br />
								<div class="indent"><p>
									<span class="keyword">set</span> x1 <span class="keyword">to</span> x1 + 5 &times;
									cwidth<br />
								</div><p>
								<span class="keyword">loop</span><br />
								<span class="keyword">set</span> x <span class="keyword">to</span> x1<br />
							</div><p>
							<span class="keyword">otherwise</span><br />
							<div class="indent"><p>
								<span class="keyword">set</span> x <span class="keyword">to</span> x + cwidth<br />
							</div><p>
							<span class="keyword">end if</span><br />
						</div><p>
						<span class="keyword">next</span><br />
					</div><p>
					<span class="keyword">end function</span><br />
				</div>
				<p>
					Once again, this function isn't that close to assembly code. Feel free to try to
					implement it either directly or by simplifying it. I will give the simplification
					and then the assembly code below.</p>
				<p>
					Clearly the person who wrote this function wasn't being very efficient (me in case
					you were wondering). Once again we have a pos variable that just increments and
					is added to something else, which is completely unnecessary. We can remove it, and
					instead simultaneously decrement length until it is 0, saving the need for one register.
					The rest of the function is probably fine, except for that annoying multiplication
					by five. A key thing to do here would be to move the multiplication outside the
					loop; multiplication is slow even with bit shifts, and since we're always adding
					the same constant multiplied by 5, there is no need to recompute this. It can in
					fact be implemented in one operation using the argument shifting in assembly code,
					so I shall rephrase it like that.</p>
				<div class="pseudoCodeBlock"><p>
					<span class="keyword">function </span>drawString(r0 <span class="keyword">is</span>
					string, r1 <span class="keyword">is</span> length, r2 <span class="keyword">is</span>
					x, r3 <span class="keyword">is</span> y)<br />
					<div class="indent"><p>
						<span class="keyword">set</span> x0 <span class="keyword">to</span> x<br />
						<span class="keyword">until</span> length = 0<br />
						<div class="indent"><p>
							<span class="keyword">set</span> length <span class="keyword">to</span> length -
							1<br />
							<span class="keyword">set</span> char <span class="keyword">to</span> loadByte(string)<br />
							<span class="keyword">set</span> (cwidth, cheight) <span class="keyword">to</span>
							DrawCharacter(char, x, y)<br />
							<span class="keyword">if</span> char = '\n' <span class="keyword">then</span><br />
							<div class="indent"><p>
								<span class="keyword">set</span> x <span class="keyword">to</span> x0<br />
								<span class="keyword">set</span> y <span class="keyword">to</span> y + cheight<br />
							</div><p>
							<span class="keyword">otherwise if</span> char = '\t' <span class="keyword">then</span><br />
							<div class="indent"><p>
								<span class="keyword">set</span> x1 <span class="keyword">to</span> x<br />
								<span class="keyword">set</span> cwidth <span class="keyword">to</span> cwidth +
								cwidth &lt;&lt; 2<br />
								<span class="keyword">until</span> x1 &gt; x0<br />
								<div class="indent"><p>
									<span class="keyword">set</span> x1 <span class="keyword">to</span> x1 + cwidth<br />
								</div><p>
								<span class="keyword">loop</span><br />
								<span class="keyword">set</span> x <span class="keyword">to</span> x1<br />
							</div><p>
							<span class="keyword">otherwise</span><br />
							<div class="indent"><p>
								<span class="keyword">set</span> x <span class="keyword">to</span> x + cwidth<br />
							</div><p>
							<span class="keyword">end if</span><br />
							<span class="keyword">set</span> string <span class="keyword">to</span> string +
							1<br />
						</div><p>
						<span class="keyword">loop</span><br />
					</div><p>
					<span class="keyword">end function</span><br />
				</div>
				<p>
					In assembly code:</p>
				<div class="armCodeBlock"><p>
					.globl DrawString<br />
					DrawString:<br />
					x .req r4<br />
					y .req r5<br />
					x0 .req r6<br />
					string .req r7<br />
					length .req r8<br />
					char .req r9<br />
					push {r4,r5,r6,r7,r8,r9,lr}<br />
					<br />
					mov string,r0<br />
					mov x,r2<br />
					mov x0,x<br />
					mov y,r3<br />
					mov length,r1<br />
					<br />
					stringLoop$:<br />
					<div class="indent"><p>
						subs length,#1<br />
						blt stringLoopEnd$<br />
						<br />
						ldrb char,[string]<br />
						add string,#1<br />
						<br />
						mov r0,char<br />
						mov r1,x<br />
						mov r2,y<br />
						bl DrawCharacter<br />
						cwidth .req r0<br />
						cheight .req r1<br />
						<br />
						teq char,#'\n'<br />
						moveq x,x0<br />
						addeq y,cheight<br />
						beq stringLoop$<br />
						<br />
						teq char,#'\t'<br />
						addne x,cwidth<br />
						bne stringLoop$<br />
						<br />
						add cwidth, cwidth,lsl #2<br />
						x1 .req r1<br />
						mov x1,x0<br />
						<br />
						stringLoopTab$:<br />
						<div class="indent"><p>
							add x1,cwidth<br />
							cmp x,x1<br />
							bge stringLoopTab$<br />
						</div><p>
						mov x,x1<br />
						.unreq x1
						<br />
						b stringLoop$<br />
					</div><p>
					stringLoopEnd$:<br />
					.unreq cwidth<br />
					.unreq cheight<br />
					<br />
					pop {r4,r5,r6,r7,r8,r9,pc}<br />
					.unreq x<br />
					.unreq y<br />
					.unreq x0<br />
					.unreq string<br />
					.unreq length<br />
				</div>
				<div class="commandBox"><p>
					<span class="armCodeInline">subs reg,#val</span> subtracts <span class="armCodeInline">
						val</span> from the register <span class="armCodeInline">reg</span> and compares
					the result with 0.</div>
				<p>
					This code makes clever use of a new operation, <span class="armCodeInline">subs</span>
					which subtracts one number from another, stores the result and then compares it
					with 0. In truth, all comparisons are implemented as a subtraction and then comparison
					with 0, but the result is normally discarded. This means that this operation is
					as fast as <span class="armCodeInline">cmp</span>.</p>
				<h2 id="ywimcl">
					4 Your Wish is My Command Line</h2>
				<p>
					Now that we can print strings, the challenge is to find an interesting one to draw.
					Normally in tutorials such as this, people just draw "Hello World!", but after all
					we've done so far, I feel that is a little patronising (feel free to do so if it
					helps). Instead we're going to draw our command line.</p>
				<p>
					A convention has been made for computers running ARM. When they boot, it is important
					they are given certain information about what they have available to them. Most
					all processors have some way of ascertaining this information, and on ARM this is
					by data left at the address 100<sub>16</sub>. The format of the data is as follows:
				</p>
				<ol>
					<li>The data is broken down into a series of 'tags'.</li>
					<li>There are nine types of tag: 'core', 'mem', 'videotext', 'ramdisk', 'initrd2', 'serial'
						'revision', 'videolfb', 'cmdline'.</li>
					<li>Each can only appear once, but all but the 'core' tag don't have to appear.</li>
					<li>The tags are placed from 0x100 in order one after the other.</li>
					<li>The end of the list of tags always contains 2 words which are 0.</li>
					<li>Every tag's size in bytes is a multiple of 4.</li>
					<li>Each tag starts with the size of the tag in words in the tag, including this number.</li>
					<li>This is followed by a half word containing the tag's number. These are numbered
						from 1 in the order above ('core' is 1, 'cmdline' is 9).</li>
					<li>This is followed by a half word containing 5441<sub>16</sub>.</li>
					<li>After this comes the data of the tag, which varies depending on the tag. The size
						of the data in words + 2 is always the same as the length mentioned above.</li>
					<li>A 'core' tag is either 2 or 5 words in length. If it is 2, there is no data, if
						it is 5, it has 3 words.</li>
					<li>A 'mem' tag is always 4 words in length. The data is the first address in a block
						of memory, and the length of that block.</li>
					<li>A 'cmdline' tag contains a null terminated string which is the parameters of the
						kernel.</li>
				</ol>
				<div class="informationBox"><p>
					Almost all Operating Systems support the notion of programs having a 'command line'.
					The idea is to provide a common mechanism for choosing the desired behaviour of the
					program.
				</p></div>
				<p>
					On the current version of the Raspberry Pi, only the 'core', 'mem' and 'cmdline'
					tags are present. You may find these useful later, and a more complete reference
					for these is on our Raspberry Pi reference page. The one we're interested in at
					the moment is the 'cmdline' tag, because it contains a string. We're going to write
					some code to search for the command line tag, and, if found, to print it out with
					each item on a new line. The command line is just a list of things that either the
					graphics processor or the user thought it might be nice for the Operating System
					to know. On the Raspberry Pi, this includes the MAC Address, serial number and screen
					resolution. The string itself is just a list of expressions such as 'key.subkey=value'
					separated by spaces.</p>
				<p>
					Let's start by finding the 'cmdline' tag. In a new file called 'tags.s' copy the
					following code.</p>
				<div class="armCodeBlock"><p>
					.section .data<br />
					tag_core: .int 0<br />
					tag_mem: .int 0<br />
					tag_videotext: .int 0<br />
					tag_ramdisk: .int 0<br />
					tag_initrd2: .int 0<br />
					tag_serial: .int 0<br />
					tag_revision: .int 0<br />
					tag_videolfb: .int 0<br />
					tag_cmdline: .int 0<br />
				</div>
				<p>
					Looking through the list of tags will be a slow operation, as it involves a lot
					of memory access. Therefore, we only want to have to do it once. This code creates
					some data which will store the memory address of the first tag of each of the types.
					Then, to find a tag the following pseudo code will suffice.</p>
				<div class="pseudoCodeBlock"><p>
					<span class="keyword">function</span> FindTag(r0 <span class="keyword">is</span>
					tag)
					<div class="indent"><p>
						<span class="keyword">if </span>tag &gt; 9 <span class="keyword">or</span> tag =
						0 <span class="keyword">then return</span> 0<br />
						<span class="keyword">set</span> tagAddr <span class="keyword">to</span> loadWord(tag_core
						+ (tag - 1) &times; 4)<br />
						<span class="keyword">if not</span> tagAddr = 0 <span class="keyword">then return</span>
						tagAddr<br />
						<span class="keyword">if</span> readWord(tag_core) = 0 <span class="keyword">then return</span>
						0<br />
						<span class="keyword">set</span> tagAddr <span class="keyword">to</span> 0x100<br />
						<span class="keyword">loop forever</span>
						<div class="indent"><p>
							<span class="keyword">set</span> tagIndex <span class="keyword">to</span> readHalfWord(tagAddr
							+ 4)<br />
							<span class="keyword">if</span> tagIndex = 0 <span class="keyword">then return</span>
							FindTag(tag)<br />
							<span class="keyword">if</span> readWord(tag_core+(tagIndex-1)&times;4) = 0<br />
							<span class="keyword">then</span> storeWord(tagAddr, tag_core+(tagIndex-1)&times;4)<br />
							<span class="keyword">set</span> tagAddr <span class="keyword">to</span> tagAddr
							+ loadWord(tagAddr) &times; 4<br />
						</div><p>
						<span class="keyword">end loop</span>
					</div><p>
					<span class="keyword">end function</span>
				</div>
				<p>
					This code is already quite well optimised and close to assembly. It is optimistic
					in that the first thing it tries is loading the tag directly, as all but the first
					time this should be the case. If that fails, it checks if the core tag has an address.
					Since there must always be a core tag, the only reason that it would not have an
					address is if it doesn't exist. If it does have an address, the tag we were looking
					for didn't. If it doesn't we need to find the addresses of all the tags. It does
					this by reading the number of the tag. If it is zero, that must mean we are at the
					end of the list. This means we've now filled in all the tags in our directory. Therefore
					if we run our function again, it will now be able to produce an answer. If the tag
					number is not zero, we check to see if this tag type already has an address. If
					not, we store the address of this tag in our directory. We then add the length of
					this tag in bytes to the tag address to find the next tag.</p>
				<p>
					Have a go at implementing this code in assembly. You will need to simplify it. If
					you get stuck, my answer is below. Don't forget the <span class="armCodeInline">.section
						.text</span>!</p>
				<div class="armCodeBlock"><p>
					.section .text<br />
					.globl FindTag<br />
					FindTag:<br />
					tag .req r0<br />
					tagList .req r1<br />
					tagAddr .req r2<br />
					<br />
					sub tag,#1<br />
					cmp tag,#8<br />
					movhi tag,#0<br />
					movhi pc,lr<br />
					<br />
					ldr tagList,=tag_core<br />
					tagReturn$:<br />
					add tagAddr,tagList, tag,lsl #2<br />
					ldr tagAddr,[tagAddr]<br />
					<br />
					teq tagAddr,#0<br />
					movne r0,tagAddr<br />
					movne pc,lr<br />
					<br />
					ldr tagAddr,[tagList]<br />
					teq tagAddr,#0<br />
					movne r0,#0<br />
					movne pc,lr<br />
					<br />
					mov tagAddr,#0x100<br />
					push {r4}<br />
					tagIndex .req r3<br />
					oldAddr .req r4<br />
					tagLoop$:<br />
					ldrh tagIndex,[tagAddr,#4]<br />
					subs tagIndex,#1<br />
					poplt {r4}<br />
					blt tagReturn$<br />
					<br />
					add tagIndex,tagList, tagIndex,lsl #2<br />
					ldr oldAddr,[tagIndex]<br />
					teq oldAddr,#0<br />
					.unreq oldAddr<br />
					streq tagAddr,[tagIndex]<br />
					<br />
					ldr tagIndex,[tagAddr]<br />
					add tagAddr, tagIndex,lsl #2<br />
					b tagLoop$<br />
					<br />
					.unreq tag<br />
					.unreq tagList<br />
					.unreq tagAddr<br />
					.unreq tagIndex<br />
				</div>
				<h2 id="helloworld">
					5 Hello World</h2>
				<p>
					Now that we have everything we need, we can draw our first string. In 'main.s' delete
					everything after <span class="armCodeInline">bl SetGraphicsAddress</span>, and replace
					it with the following:</p>
				<div class="armCodeBlock"><p>
					mov r0,#9<br />
					bl FindTag<br />
					ldr r1,[r0]<br />
					lsl r1,#2<br />
					sub r1,#8<br />
					add r0,#8<br />
					mov r2,#0<br />
					mov r3,#0<br />
					bl DrawString<br />
					loop$:<br />
					b loop$<br />
				</div>
				<p>
					This code simply uses our FindTag method to find the 9th tag (cmdline) and then
					calculates its length and passes the command and the length to the DrawString method,
					and tells it to draw the string at 0,0. Now test this on the Raspberry Pi. You should
					see a line of text on the screen. If not please see our troubleshooting page.</p>
				<p>
					Once it works, congratulations you've now got the ability to draw text. But there
					is still room for improvement. What if we wanted to write out a number, or a section
					of the memory or manipulate our command line? In <a href="screen04.html">Lesson 9: Screen04</a>,
					we will look at manipulating text and displaying useful numbers and information.</p>
			</div>
			<div id="pageFooter">
				<hr />
				<p>Spot a mistake? You can help improve this tutorial on <a href="https://github.com/chadderz121/bakingpi-www">GitHub</a>.</p>
				<p><a rel="license" href="http://creativecommons.org/licenses/by-sa/3.0/deed.en_GB"><img alt="Creative Commons Licence" style="border-width:0" src="http://i.creativecommons.org/l/by-sa/3.0/88x31.png" /></a><br /><span xmlns:dct="http://purl.org/dc/terms/" property="dct:title">Baking Pi: Operating Systems Development</span> by <span xmlns:cc="http://creativecommons.org/ns#" property="cc:attributionName">Alex Chadwick</span> is licensed under a <a rel="license" href="http://creativecommons.org/licenses/by-sa/3.0/deed.en_GB">Creative Commons Attribution-ShareAlike 3.0 Unported License</a>.</p>
				<p>Based on contributions at <a href="https://github.com/chadderz121/bakingpi-www">https://github.com/chadderz121/bakingpi-www</a>.</p>
			</div>
		</div>
	</div>
</body>
</html>