計算機實驗室之樹莓派：課程 8 螢幕03

螢幕03 課程基於螢幕02 課程來構建，它教你如何繪製文字，和一個作業系統命令列引數上的一個小特性。假設你已經有了 的作業系統程式碼，我們將以它為基礎來構建。

1、字串的理論知識

是的，我們的任務是為這個作業系統繪製文字。我們有幾個問題需要去處理，最緊急的那個可能是如何去儲存文字。令人難以置信的是，文字是迄今為止在計算機上最大的缺陷之一。原本應該是簡單的資料型別卻導致了作業系統的崩潰，從而削弱其他方面的加密效果，並給使用其它字母表的使用者帶來了許多問題。儘管如此，它仍然是極其重要的資料型別，因為它將計算機和使用者很好地連線起來。文字是計算機能夠理解的非常好的結構，同時人類使用它時也有足夠的可讀性。

那麼，文字是如何儲存的呢？非常簡單，我們使用一種方法，給每個字母分配一個唯一的編號，然後我們儲存一系列的這種編號。看起來很容易吧。問題是，那個編號的數量是不固定的。一些文字段可能比其它的長。儲存普通數位，我們有一些固有的限制，即：32 位，我們不能超過這個限制，我們要新增方法去使用該長度的數位等等。“文字”這個術語，我們經常也叫它“字串”，我們希望能夠寫一個可用於可變長度字串的函數，否則就需要寫很多函數！對於一般的數位來說，這不是個問題，因為只有幾種通用的數位格式（位元組、字、半位元組、雙位元組）。

可變資料型別（比如文字）要求能夠進行很複雜的處理。

因此，如何判斷字串長度？我想顯而易見的答案是儲存字串的長度，然後去儲存組成字串的字元。這稱為長度字首，因為長度位於字串的前面。不幸的是，電腦科學家的先驅們不同意這麼做。他們認為使用一個稱為空終止符（NULL）的特殊字元（用 \0 表示）來表示字串結束更有意義。這樣確定簡化了許多字串演算法，因為你只需要持續操作直到遇到空終止符為止。不幸的是，這成為了許多安全問題的根源。如果一個惡意使用者給你一個特別長的字串會發生什麼狀況？如果沒有足夠的空間去儲存這個特別長的字串會發生什麼狀況？你可以使用一個字串複製函數來做複製，直到遇到空終止符為止，但是因為字串特別長，而覆寫了你的程式，怎麼辦？這看上去似乎有些較真，但是，緩衝區溢位攻擊還是經常發生。長度字首可以很容易地緩解這種問題，因為它可以很容易地推算出儲存這個字串所需要的緩衝區的長度。作為一個作業系統開發者，我留下這個問題，由你去決定如何才能更好地儲存文字。

緩衝區溢位攻擊禍害計算機由來已久。最近，Wii、Xbox 和 Playstation 2、以及大型系統如 Microsoft 的 Web 和資料庫伺服器，都遭受到緩衝區溢位攻擊。

接下來的事情是，我們需要確定的是如何最好地將字元對映到數位。幸運的是，這是高度標準化的，我們有兩個主要的選擇，Unicode 和 ASCII。Unicode 幾乎將每個有用的符號都對映為數位，作為代價，我們需要有很多很多的數位，和一個更複雜的編碼方法。ASCII 為每個字元使用一個位元組，因此它僅儲存拉丁字母、數位、少數符號和少數特殊字元。因此，ASCII 是非常易於實現的，與之相比，Unicode 的每個字元佔用的空間並不相同，這使得字串演算法更棘手。通常，作業系統上字元使用 ASCII，並不是為了顯示給終端使用者的（開發者和專家使用者除外），給終端使用者顯示資訊使用 Unicode，因為 Unicode 能夠支援像日語字元這樣的東西，並且因此可以實現在地化。

幸運的是，在這裡我們不需要去做選擇，因為它們的前 128 個字元是完全相同的，並且編碼也是完全一樣的。

表 1.1 ASCII/Unicode 符號 0-127

這個表顯示了前 128 個符號。一個符號的十六進位制表示是行的值加上列的值，比如 A 是 41₁₆。你可以驚奇地發現前兩行和最後的值。這 33 個特殊字元是不可列印字元。事實上，許多人都忽略了它們。它們之所以存在是因為 ASCII 最初設計是基於計算機網路來傳輸資料的一種方法。因此它要傳送的資訊不僅僅是符號。你應該學習的重要的特殊字元是 NUL，它就是我們前面提到的空終止符。HT 水平製表符就是我們經常說的 tab，而 LF 換行符用於生成一個新行。你可能想研究和使用其它特殊字元在你的操行系統中的意義。

2、字元

到目前為止，我們已經知道了一些關於字串的知識，我們可以開始想想它們是如何顯示的。為了顯示一個字串，我們需要做的最基礎的事情是能夠顯示一個字元。我們的第一個任務是編寫一個 DrawCharacter 函數，給它一個要繪製的字元和一個位置，然後它將這個字元繪製出來。

這就很自然地引出關於字型的討論。我們已經知道有許多方式去按照選定的字型去顯示任何給定的字母。那麼字型又是如何工作的呢？在電腦科學的早期階段，字型就是所有字母的一系列小圖片而已，這種字型稱為點陣圖字型，而所有的字元繪製方法就是將圖片複製到螢幕上。當人們想去調整字型大小時就出問題了。有時我們需要大的字母，而有時我們需要的是小的字母。儘管我們可以為每個字型、每種大小、每個字元都繪製新圖片，但這種作法過於單調乏味。所以，發明了向量字型。向量字型不包含字型的影象，它包含的是如何去繪製字元的描述，即：一個 o 可能是最大字母高度的一半為半徑繪製的圓。現代作業系統都幾乎僅使用這種字型，因為這種字型在任何解析度下都很完美。

在許多作業系統中使用的 TrueType 字型格式是很強大的，它內建有它自己的組合語言，以確保在任何解析度下字母看起來都是正確的。

不幸的是，雖然我很想包含一個向量字型的格式的實現，但它的內容太多了，將佔用這個網站的剩餘部分。所以，我們將去實現一個點陣圖字型，可是，如果你想去做一個像樣的圖形作業系統，那麼向量字型將是很有用的。

在下載頁面上的字型節中，我們提供了幾個 .bin 檔案。這些只是字型的原始二進位制資料檔案。為完成本教學，從等寬、單色、8x16 節中挑選你喜歡的字型。然後下載它並儲存到 source 目錄中並命名為 font.bin 檔案。這些檔案只是每個字母的單色圖片，它們每個字母剛好是 8 x 16 個畫素。所以，每個字母占用 16 位元組，第一個位元組是第一行，第二個位元組是第二行，依此類推。

這個示意圖展示了等寬、單色、8x16 的字元 A 的 “Bitstream Vera Sans Mono” 字型。在這個檔案中，我們可以找到，它從第 41₁₆ × 10₁₆ = 410₁₆ 位元組開始的十六進位制序列：

00, 00, 00, 10, 28, 28, 28, 44, 44, 7C, C6, 82, 00, 00, 00, 00

在這裡我們將使用等寬字型，因為等寬字型的每個字元大小是相同的。不幸的是，大多數位體的複雜之處就是因為它的寬度不同，從而導致它的顯示程式碼更複雜。在下載頁面上還包含有幾個其它的字型，並包含了這種字型的儲存格式介紹。

我們回到正題。複製下列程式碼到 drawing.s 中的 graphicsAddress 的 .int 0 之後。

.align 4font:.incbin "font.bin"

.incbin "file" 插入來自檔案 “file” 中的二進位制資料。

這段程式碼複製檔案中的字型資料到標籤為 font 的地址。我們在這裡使用了一個 .align 4 去確保每個字元都是從 16 位元組的倍數開始，這是一個以後經常用到的用於加快存取速度的技巧。

現在我們去寫繪製字元的方法。我在下面給出了虛擬碼，你可以嘗試自己去實現它。按慣例 >> 的意思是邏輯右移。

function drawCharacter(r0 is character, r1 is x, r2 is y)  if character > 127 then exit  set charAddress to font + character × 16  for row = 0 to 15  set bits to readByte(charAddress + row)  for bit = 0 to 7    if test(bits >> bit, 0x1)    then setPixel(x + bit, y + row)    next  next  return r0 = 8, r1 = 16end function

如果直接去實現它，這顯然不是個高效率的做法。像繪製字元這樣的事情，效率是最重要的。因為我們要頻繁使用它。我們來探索一些改善的方法，使其成為最佳化的組合程式碼。首先，因為我們有一個 × 16，你應該會馬上想到它等價於邏輯左移 4 位。緊接著我們有一個變數 row，它只與 charAddress 和 y 相加。所以，我們可以通過增加替代變數來消除它。現在唯一的問題是如何判斷我們何時完成。這時，一個很好用的 .align 4 上場了。我們知道，charAddress 將從包含 0 的低位半位元組開始。這意味著我們可以通過檢查低位半位元組來看到進入字元資料的程度。

雖然我們可以消除對 bit 的需求，但我們必須要引入新的變數才能實現，因此最好還是保留它。剩下唯一的改進就是去除巢狀的 bits >> bit。

function drawCharacter(r0 is character, r1 is x, r2 is y)  if character > 127 then exit  set charAddress to font + character << 4  loop    set bits to readByte(charAddress)    set bit to 8    loop      set bits to bits << 1      set bit to bit - 1      if test(bits, 0x100)      then setPixel(x + bit, y)    until bit = 0    set y to y + 1    set chadAddress to chadAddress + 1  until charAddress AND 0b1111 = 0  return r0 = 8, r1 = 16end function

現在，我們已經得到了非常接近組合程式碼的程式碼了，並且程式碼也是經過優化的。下面就是上述程式碼用組合寫出來的程式碼。

.globl DrawCharacterDrawCharacter:cmp r0,#127movhi r0,#0movhi r1,#0movhi pc,lrpush {r4,r5,r6,r7,r8,lr}x .req r4y .req r5charAddr .req r6mov x,r1mov y,r2ldr charAddr,=fontadd charAddr, r0,lsl #4lineLoop$:  bits .req r7  bit .req r8  ldrb bits,[charAddr]  mov bit,#8    charPixelLoop$:      subs bit,#1    blt charPixelLoopEnd$    lsl bits,#1    tst bits,#0x100    beq charPixelLoop$        add r0,x,bit    mov r1,y    bl DrawPixel        teq bit,#0    bne charPixelLoop$    charPixelLoopEnd$:  .unreq bit  .unreq bits  add y,#1  add charAddr,#1  tst charAddr,#0b1111  bne lineLoop$.unreq x.unreq y.unreq charAddrwidth .req r0height .req r1mov width,#8mov height,#16pop {r4,r5,r6,r7,r8,pc}.unreq width.unreq height

3、字串

現在，我們可以繪製字元了，我們可以繪製文字了。我們需要去寫一個方法，給它一個字串為輸入，它通過遞增位置來繪製出每個字元。為了做的更好，我們應該去實現新的行和製表符。是時候決定關於空終止符的問題了，如果你想讓你的作業系統使用它們，可以按需來修改下面的程式碼。為避免這個問題，我將給 DrawString 函數傳遞一個字串長度，以及字串的地址，和 x 和 y 的坐標作為引數。

function drawString(r0 is string, r1 is length, r2 is x, r3 is y)  set x0 to x  for pos = 0 to length - 1    set char to loadByte(string + pos)    set (cwidth, cheight) to DrawCharacter(char, x, y)    if char = '\n' then      set x to x0      set y to y + cheight    otherwise if char = '\t' then      set x1 to x      until x1 > x0        set x1 to x1 + 5 × cwidth      loop    set x to x1    otherwise      set x to x + cwidth    end if  nextend function

同樣，這個函數與組合程式碼還有很大的差距。你可以隨意去嘗試實現它，即可以直接實現它，也可以簡化它。我在下面給出了簡化後的函數和組合程式碼。

很明顯，寫這個函數的人並不很有效率（感到奇怪嗎？它就是我寫的）。再說一次，我們有一個 pos 變數，它用於遞增及與其它東西相加，這是完全沒有必要的。我們可以去掉它，而同時進行長度遞減，直到減到 0 為止，這樣就少用了一個暫存器。除了那個煩人的乘以 5 以外，函數的其餘部分還不錯。在這裡要做的一個重要事情是，將乘法移到回圈外面；即便使用位移運算，乘法仍然是很慢的，由於我們總是加一個乘以 5 的相同的常數，因此沒有必要重新計算它。實際上，在組合程式碼中它可以在一個運算元中通過引數移位來實現，因此我將程式碼改變為下面這樣。

function drawString(r0 is string, r1 is length, r2 is x, r3 is y)  set x0 to x  until length = 0    set length to length - 1    set char to loadByte(string)    set (cwidth, cheight) to DrawCharacter(char, x, y)    if char = '\n' then      set x to x0      set y to y + cheight    otherwise if char = '\t' then      set x1 to x      set cwidth to cwidth + cwidth << 2      until x1 > x0        set x1 to x1 + cwidth      loop      set x to x1    otherwise      set x to x + cwidth    end if    set string to string + 1  loopend function

以下是它的組合程式碼：

.globl DrawStringDrawString:x .req r4y .req r5x0 .req r6string .req r7length .req r8char .req r9push {r4,r5,r6,r7,r8,r9,lr}mov string,r0mov x,r2mov x0,xmov y,r3mov length,r1stringLoop$:  subs length,#1  blt stringLoopEnd$    ldrb char,[string]  add string,#1    mov r0,char  mov r1,x  mov r2,y  bl DrawCharacter  cwidth .req r0  cheight .req r1    teq char,#'\n'  moveq x,x0  addeq y,cheight  beq stringLoop$    teq char,#'\t'  addne x,cwidth  bne stringLoop$    add cwidth, cwidth,lsl #2  x1 .req r1  mov x1,x0    stringLoopTab$:    add x1,cwidth    cmp x,x1    bge stringLoopTab$  mov x,x1  .unreq x1  b stringLoop$stringLoopEnd$:.unreq cwidth.unreq cheightpop {r4,r5,r6,r7,r8,r9,pc}.unreq x.unreq y.unreq x0.unreq string.unreq length

這個程式碼中非常聰明地使用了一個新運算，subs 是從一個運算元中減去另一個數，儲存結果，然後將結果與 0 進行比較。實現上，所有的比較都可以實現為減法後的結果與 0 進行比較，但是結果通常會丟棄。這意味著這個操作與 cmp 一樣快。

subs reg,#val 從暫存器 reg 中減去 val，然後將結果與 0 進行比較。

4、你的意願是我的命令列

現在，我們可以輸出字串了，而挑戰是找到一個有意思的字串去繪製。一般在這樣的教學中，人們都希望去繪製 “Hello World!”，但是到目前為止，雖然我們已經能做到了，我覺得這有點“君臨天下”的感覺（如果喜歡這種感覺，請隨意！）。因此，作為替代，我們去繼續繪製我們的命令列。

有一個限制是我們所做的作業系統是用在 ARM 架構的計算機上。最關鍵的是，在它們引導時，給它一些資訊告訴它有哪些可用資源。幾乎所有的處理器都有某些方式來確定這些資訊，而在 ARM 上，它是通過位於地址 100₁₆ 處的資料來確定的，這個資料的格式如下：

1. 資料是可分解的一系列的標籤。2. 這裡有九種型別的標籤：`core`、`mem`、`videotext`、`ramdisk`、`initrd2`、`serial`、`revision`、`videolfb`、`cmdline`。3. 每個標籤只能出現一次，除了 `core` 標籤是必不可少的之外，其它的都是可有可無的。4. 所有標籤都依次放置在地址 `0x100` 處。5. 標籤列表的結束處總是有兩個<ruby>字<rt>word</rt></ruby>，它們全為 0。6. 每個標籤的位元組數都是 4 的倍數。7. 每個標籤都是以標籤中（以字為單位）的標籤大小開始（標籤包含這個數位）。8. 緊接著是包含標籤編號的一個半字。編號是按上面列出的順序，從 1 開始（`core` 是 1，`cmdline` 是 9）。9. 緊接著是一個包含 5441<sub>16</sub> 的半字。10. 之後是標籤的資料，它根據標籤不同是可變的。資料大小（以字為單位）+ 2 的和總是與前面提到的長度相同。11. 一個 `core` 標籤的長度可以是 2 個字也可以是 5 個字。如果是 2 個字，表示沒有資料，如果是 5 個字，表示它有 3 個字的資料。12. 一個 `mem` 標籤總是 4 個字的長度。資料是記憶體塊的第一個地址，和記憶體塊的長度。13. 一個 `cmdline` 標籤包含一個 `null` 終止符字串，它是個核心引數。

在目前的樹莓派版本中，只提供了 core、mem 和 cmdline 標籤。你可以在後面找到它們的用法，更全面的參考資料在樹莓派的參考頁面上。現在，我們感興趣的是 cmdline 標籤，因為它包含一個字串。我們繼續寫一些搜尋這個命令列（cmdline）標籤的程式碼，如果找到了，以每個條目一個新行的形式輸出它。命令列只是圖形處理器或使用者認為作業系統應該知道的東西的一個列表。在樹莓派上，這包含了 MAC 地址、序列號和螢幕解析度。字串本身也是一個由空格隔開的表示式（像 key.subkey=value 這樣的）的列表。

幾乎所有的作業系統都支援一個“命令列”的程式。它的想法是為選擇一個程式所期望的行為而提供一個通用的機制。

我們從查詢 cmdline 標籤開始。將下列的程式碼複製到一個名為 tags.s 的新檔案中。

.section .datatag_core: .int 0tag_mem: .int 0tag_videotext: .int 0tag_ramdisk: .int 0tag_initrd2: .int 0tag_serial: .int 0tag_revision: .int 0tag_videolfb: .int 0tag_cmdline: .int 0

通過標籤列表來查詢是一個很慢的操作，因為這涉及到許多記憶體存取。因此，我們只想做一次。程式碼建立一些資料，用於儲存每個型別的第一個標籤的記憶體地址。接下來，用下面的虛擬碼就可以找到一個標籤了。

function FindTag(r0 is tag)  if tag > 9 or tag = 0 then return 0  set tagAddr to loadWord(tag_core + (tag - 1) × 4)  if not tagAddr = 0 then return tagAddr  if readWord(tag_core) = 0 then return 0  set tagAddr to 0x100  loop forever    set tagIndex to readHalfWord(tagAddr + 4)    if tagIndex = 0 then return FindTag(tag)    if readWord(tag_core+(tagIndex-1)×4) = 0    then storeWord(tagAddr, tag_core+(tagIndex-1)×4)    set tagAddr to tagAddr + loadWord(tagAddr) × 4  end loopend function

這段程式碼已經是優化過的，並且很接近組合了。它嘗試直接載入標籤，第一次這樣做是有些樂觀的，但是除了第一次之外的其它所有情況都是可以這樣做的。如果失敗了，它將去檢查 core 標籤是否有地址。因為 core 標籤是必不可少的，如果它沒有地址，唯一可能的原因就是它不存在。如果它有地址，那就是我們沒有找到我們要找的標籤。如果沒有找到，那我們就需要查詢所有標籤的地址。這是通過讀取標籤編號來做的。如果標籤編號為 0，意味著已經到了標籤列表的結束位置。這意味著我們已經查詢了目錄中所有的標籤。所以，如果我們再次執行我們的函數，現在它應該能夠給出一個答案。如果標籤編號不為 0，我們檢查這個標簽型別是否已經有一個地址。如果沒有，我們在目錄中儲存這個標籤的地址。然後增加這個標籤的長度（以位元組為單位）到標籤地址中，然後去查詢下一個標籤。

嘗試去用組合實現這段程式碼。你將需要簡化它。如果被卡住了，下面是我的答案。不要忘了 .section .text！

.section .text.globl FindTagFindTag:tag .req r0tagList .req r1tagAddr .req r2sub tag,#1cmp tag,#8movhi tag,#0movhi pc,lrldr tagList,=tag_coretagReturn$:add tagAddr,tagList, tag,lsl #2ldr tagAddr,[tagAddr]teq tagAddr,#0movne r0,tagAddrmovne pc,lrldr tagAddr,[tagList]teq tagAddr,#0movne r0,#0movne pc,lrmov tagAddr,#0x100push {r4}tagIndex .req r3oldAddr .req r4tagLoop$:ldrh tagIndex,[tagAddr,#4]subs tagIndex,#1poplt {r4}blt tagReturn$add tagIndex,tagList, tagIndex,lsl #2ldr oldAddr,[tagIndex]teq oldAddr,#0.unreq oldAddrstreq tagAddr,[tagIndex]ldr tagIndex,[tagAddr]add tagAddr, tagIndex,lsl #2b tagLoop$.unreq tag.unreq tagList.unreq tagAddr.unreq tagIndex

5、Hello World

現在，我們已經萬事俱備了，我們可以去繪製我們的第一個字串了。在 main.s 檔案中刪除 bl SetGraphicsAddress 之後的所有程式碼，然後將下面的程式碼放進去：

mov r0,#9bl FindTagldr r1,[r0]lsl r1,#2sub r1,#8add r0,#8mov r2,#0mov r3,#0bl DrawStringloop$:b loop$

這段程式碼簡單地使用了我們的 FindTag 方法去查詢第 9 個標籤（cmdline），然後計算它的長度，然後傳遞命令和長度給 DrawString 方法，告訴它在 0,0 處繪製字串。現在可以在樹莓派上測試它了。你應該會在螢幕上看到一行文字。如果沒有，請檢視我們的排錯頁面。

如果一切正常，恭喜你已經能夠繪製文字了。但它還有很大的改進空間。如果想去寫了一個數位，或記憶體的一部分，或操作我們的命令列，該怎麼做呢？在 課程 9：螢幕04 中，我們將學習如何操作文字和顯示有用的數位和資訊。