Linux中國

計算機實驗室之樹莓派:課程 8 屏幕03

屏幕03 課程基於屏幕02 課程來構建,它教你如何繪製文本,和一個操作系統命令行參數上的一個小特性。假設你已經有了課程 7:屏幕02 的操作系統代碼,我們將以它為基礎來構建。

1、字元串的理論知識

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

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

可變數據類型(比如文本)要求能夠進行很複雜的處理。

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

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

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

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

表 1.1 ASCII/Unicode 符號 0-127

0 1 2 3 4 5 6 7 8 9 a b c d e f
00 NUL SOH STX ETX EOT ENQ ACK BEL BS HT LF VT FF CR SO SI
10 DLE DC1 DC2 DC3 DC4 NAK SYN ETB CAN EM SUB ESC FS GS RS US
20 ! # $ % & . ( ) * + , - . /
30 0 1 2 3 4 5 6 7 8 9 : ; < = > ?
40 @ A B C D E F G H I J K L M N O
50 P Q R S T U V W X Y Z [ ] ^ _
60 ` a b c d e f g h i j k l m n o
70 p q r s t u v w x y z { } ~ DEL

這個表顯示了前 128 個符號。一個符號的十六進位表示是行的值加上列的值,比如 A 是 41 16。你可以驚奇地發現前兩行和最後的值。這 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 16 × 10 16 = 410 16 位元組開始的十六進位序列:

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

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

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

.align 4
font:
.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 = 16
end function

如果直接去實現它,這顯然不是個高效率的做法。像繪製字元這樣的事情,效率是最重要的。因為我們要頻繁使用它。我們來探索一些改善的方法,使其成為最優化的彙編代碼。首先,因為我們有一個 × 16,你應該會馬上想到它等價於邏輯左移 4 位。緊接著我們有一個變數 row,它只與 charAddressy 相加。所以,我們可以通過增加替代變數來消除它。現在唯一的問題是如何判斷我們何時完成。這時,一個很好用的 .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 = 16
end function

現在,我們已經得到了非常接近彙編代碼的代碼了,並且代碼也是經過優化的。下面就是上述代碼用彙編寫出來的代碼。

.globl DrawCharacter
DrawCharacter:
cmp r0,#127
movhi r0,#0
movhi r1,#0
movhi pc,lr

push {r4,r5,r6,r7,r8,lr}
x .req r4
y .req r5
charAddr .req r6
mov x,r1
mov y,r2
ldr charAddr,=font
add charAddr, r0,lsl #4

lineLoop$:

  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 charAddr

width .req r0
height .req r1
mov width,#8
mov height,#16

pop {r4,r5,r6,r7,r8,pc}
.unreq width
.unreq height

3、字元串

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

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 = &apos;n&apos; then
      set x to x0
      set y to y + cheight
    otherwise if char = &apos;t&apos; 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
  next
end 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 = &apos;n&apos; then
      set x to x0
      set y to y + cheight
    otherwise if char = &apos;t&apos; 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
  loop
end function

以下是它的彙編代碼:

.globl DrawString
DrawString:
x .req r4
y .req r5
x0 .req r6
string .req r7
length .req r8
char .req r9
push {r4,r5,r6,r7,r8,r9,lr}

mov string,r0
mov x,r2
mov x0,x
mov y,r3
mov length,r1

stringLoop$:
  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,#&apos;n&apos;
  moveq x,x0
  addeq y,cheight
  beq stringLoop$

  teq char,#&apos;t&apos;
  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 cheight

pop {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 16 處的數據來確定的,這個數據的格式如下:

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` 終止符字元串,它是個內核參數。

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

幾乎所有的操作系統都支持一個「命令行」的程序。它的想法是為選擇一個程序所期望的行為而提供一個通用的機制。

我們從查找 cmdline 標籤開始。將下列的代碼複製到一個名為 tags.s 的新文件中。

.section .data
tag_core: .int 0
tag_mem: .int 0
tag_videotext: .int 0
tag_ramdisk: .int 0
tag_initrd2: .int 0
tag_serial: .int 0
tag_revision: .int 0
tag_videolfb: .int 0
tag_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 loop
end function

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

嘗試去用彙編實現這段代碼。你將需要簡化它。如果被卡住了,下面是我的答案。不要忘了 .section .text

.section .text
.globl FindTag
FindTag:
tag .req r0
tagList .req r1
tagAddr .req r2

sub tag,#1
cmp tag,#8
movhi tag,#0
movhi pc,lr

ldr tagList,=tag_core
tagReturn$:
add tagAddr,tagList, tag,lsl #2
ldr tagAddr,[tagAddr]

teq tagAddr,#0
movne r0,tagAddr
movne pc,lr

ldr tagAddr,[tagList]
teq tagAddr,#0
movne r0,#0
movne pc,lr

mov tagAddr,#0x100
push {r4}
tagIndex .req r3
oldAddr .req r4
tagLoop$:
ldrh tagIndex,[tagAddr,#4]
subs tagIndex,#1
poplt {r4}
blt tagReturn$

add tagIndex,tagList, tagIndex,lsl #2
ldr oldAddr,[tagIndex]
teq oldAddr,#0
.unreq oldAddr
streq tagAddr,[tagIndex]

ldr tagIndex,[tagAddr]
add tagAddr, tagIndex,lsl #2
b tagLoop$

.unreq tag
.unreq tagList
.unreq tagAddr
.unreq tagIndex

5、Hello World

現在,我們已經萬事俱備了,我們可以去繪製我們的第一個字元串了。在 main.s 文件中刪除 bl SetGraphicsAddress 之後的所有代碼,然後將下面的代碼放進去:

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

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

如果一切正常,恭喜你已經能夠繪製文本了。但它還有很大的改進空間。如果想去寫了一個數字,或內存的一部分,或操作我們的命令行,該怎麼做呢?在 課程 9:屏幕04 中,我們將學習如何操作文本和顯示有用的數字和信息。

via: https://www.cl.cam.ac.uk/projects/raspberrypi/tutorials/os/screen03.html

作者:Alex Chadwick 選題:lujun9972 譯者:qhwdw 校對:wxy

本文由 LCTT 原創編譯,Linux中國 榮譽推出


本文轉載來自 Linux 中國: https://github.com/Linux-CN/archive

對這篇文章感覺如何?

太棒了
0
不錯
0
愛死了
0
不太好
0
感覺很糟
0
雨落清風。心向陽

    You may also like

    Leave a reply

    您的電子郵箱地址不會被公開。 必填項已用 * 標註

    此站點使用Akismet來減少垃圾評論。了解我們如何處理您的評論數據

    More in:Linux中國