計算機實驗室之樹莓派:課程 9 螢幕04

2019-03-10 20:59:00

螢幕04 課程基於螢幕03 課程來構建,它教你如何操作文字。假設你已經有了 的作業系統程式碼,我們將以它為基礎。

1、操作字串

能夠繪製文字是極好的,但不幸的是,現在你只能繪製預先準備好的字串。如果能夠像命令列那樣顯示任何東西才是完美的,而理想情況下應該是,我們能夠顯示任何我們期望的東西。一如既往地,如果我們付出努力而寫出一個非常好的函數,它能夠操作我們所希望的所有字串,而作為回報,這將使我們以後寫程式碼更容易。曾經如此複雜的函數,在 C 語言程式設計中只不過是一個 sprintf 而已。這個函數基於給定的另一個字串和作為描述的額外的一個引數而生成一個字串。我們對這個函數感興趣的地方是,這個函數是個變長函數。這意味著它可以帶可變數量的引數。引數的數量取決於具體的格式字串,因此它的引數的數量不能預先確定。

變長函數在組合程式碼中看起來似乎不好理解,然而 ,它卻是非常有用和很強大的概念。

這個完整的函數有許多選項,而我們在這裡只列出了幾個。在本教學中將要實現的選項我做了高亮處理,當然,你可以嘗試去實現更多的選項。

函數通過讀取格式化字串來工作,然後使用下表的意思去解釋它。一旦一個引數已經使用了,就不會再次考慮它了。函數的返回值是寫入的字元數。如果方法失敗,將返回一個負數。

表 1.1 sprintf 格式化規則

選項含義
除了 % 之外的任何支付複製字元到輸出。
%%寫一個 % 字元到輸出。
%c將下一個引數寫成字元格式。
%d%i將下一個引數寫成十進位制的有符號整數。
%e將下一個引數寫成科學記數法,使用 eN,意思是 ×10N
%E將下一個引數寫成科學記數法,使用 EN,意思是 ×10N
%f將下一個引數寫成十進位制的 IEEE 754 浮點數。
%g%e%f 的指數表示形式相同。
%G%E%f 的指數表示形式相同。
%o將下一個引數寫成八進位制的無符號整數。
%s下一個引數如果是一個指標,將它寫成空終止符字串。
%u將下一個引數寫成十進位制無符號整數。
%x將下一個引數寫成十六進位制無符號整數(使用小寫的 a、b、c、d、e 和 f)。
%X將下一個引數寫成十六進位制的無符號整數(使用大寫的 A、B、C、D、E 和 F)。
%p將下一個引數寫成指標地址。
%n什麼也不輸出。而是複製到目前為止被下一個引數在本地處理的字元個數。

除此之外,對序列還有許多額外的處理,比如指定最小長度,符號等等。更多資訊可以在 sprintf - C++ 參考 上找到。

下面是呼叫方法和返回的結果的範例。

表 1.2 sprintf 呼叫範例

格式化字串引數結果
"%d"1313
"+%d degrees"12+12 degrees
"+%x degrees"24+1c degrees
"'%c' = 0%o"65, 65‘A’ = 0101
"%d * %d%% = %d"200, 40, 80200 * 40% = 80
"+%d degrees"-5+-5 degrees
"+%u degrees"-5+4294967291 degrees

希望你已經看到了這個函數是多麼有用。實現它需要大量的程式設計工作,但給我們的回報卻是一個非常有用的函數,可以用於各種用途。

2、除法

雖然這個函數看起來很強大、也很複雜。但是,處理它的許多情況的最容易的方式可能是,編寫一個函數去處理一些非常常見的任務。它是個非常有用的函數,可以為任何底的一個有符號或無符號的數位生成一個字串。那麼,我們如何去實現呢?在繼續閱讀之前,嘗試快速地設計一個演算法。

除法是非常慢的,也是非常複雜的基礎數學運算。它在 ARM 組合程式碼中不能直接實現,因為如果直接實現的話,它得出答案需要花費很長的時間,因此它不是個“簡單的”運算。

最簡單的方法或許就是我在 中提到的“除法餘數法”。它的思路如下:

  1. 用當前值除以你使用的底。
  2. 儲存餘數。
  3. 如果得到的新值不為 0,轉到第 1 步。
  4. 將餘數反序連起來就是答案。

例如:

表 2.1 以 2 為底的例子

轉換

新值餘數
137681
68340
34170
1781
840
420
210
101

因此答案是 100010012

這個過程的不幸之外在於使用了除法。所以,我們必須首先要考慮二進位制中的除法。

我們複習一下長除法

假如我們想把 4135 除以 17。

   0243 r 417)4135   0        0 × 17 = 0000   4135     4135 - 0 = 4135   34       200 × 17 = 3400   735      4135 - 3400 = 735   68       40 × 17 = 680   55       735 - 680 = 55   51       3 × 17 = 51   4        55 - 51 = 4

答案:243 餘 4

首先我們來看被除數的最高位。我們看到它是小於或等於除數的最小倍數,因此它是 0。我們在結果中寫一個 0。

接下來我們看被除數倒數第二位和所有的高位。我們看到小於或等於那個數的除數的最小倍數是 34。我們在結果中寫一個 2,和減去 3400。

接下來我們看被除數的第三位和所有高位。我們看到小於或等於那個數的除數的最小倍數是 68。我們在結果中寫一個 4,和減去 680。

最後,我們看一下所有的餘位。我們看到小於餘數的除數的最小倍數是 51。我們在結果中寫一個 3,減去 51。減法的結果就是我們的餘數。

在組合程式碼中做除法,我們將實現二進位制的長除法。我們之所以實現它是因為,數位都是以二進位制方式儲存的,這讓我們很容易地存取所有重要位的移位元運算,並且因為在二進位制中做除法比在其它高進位制中做除法都要簡單,因為它的數更少。

        1011 r 11010)1101111     1010      11111      1010       1011       1010          1

這個範例展示了如何做二進位制的長除法。簡單來說就是,在不超出被除數的情況下,盡可能將除數右移,根據位置輸出一個 1,和減去這個數。剩下的就是餘數。在這個例子中,我們展示了 11011112 ÷ 10102 = 10112 餘數為 12。用十進位制表示就是,111 ÷ 10 = 11 餘 1。

你自己嘗試去實現這個長除法。你應該去寫一個函數 DivideU32 ,其中 r0 是被除數,而 r1 是除數,在 r0 中返回結果,在 r1 中返回餘數。下面,我們將完成一個有效的實現。

function DivideU32(r0 is dividend, r1 is divisor)  set shift to 31  set result to 0  while shift ≥ 0     if dividend ≥ (divisor << shift) then       set dividend to dividend - (divisor <&lt shift)       set result to result + 1     end if     set result to result << 1     set shift to shift - 1  loop  return (result, dividend)end function

這段程式碼實現了我們的目標,但卻不能用於組合程式碼。我們出現的問題是,我們的暫存器只能儲存 32 位,而 divisor << shift 的結果可能在一個暫存器中裝不下(我們稱之為溢位)。這確實是個問題。你的解決方案是否有溢位的問題呢?

幸運的是,有一個稱為 clz計數前導零count leading zeros)的指令,它能計算一個二進位制表示的數位的前導零的個數。這樣我們就可以在溢位發生之前,可以將暫存器中的值進行相應位數的左移。你可以找出的另一個優化就是,每個迴圈我們計算 divisor << shift 了兩遍。我們可以通過將除數移到開始位置來改進它,然後在每個迴圈結束的時候將它移下去,這樣可以避免將它移到別處。

我們來看一下進一步優化之後的組合程式碼。

.globl DivideU32DivideU32:result .req r0remainder .req r1shift .req r2current .req r3clz shift,r1lsl current,r1,shiftmov remainder,r0mov result,#0divideU32Loop$:  cmp shift,#0  blt divideU32Return$  cmp remainder,current    addge result,result,#1  subge remainder,current  sub shift,#1  lsr current,#1  lsl result,#1  b divideU32Loop$divideU32Return$:.unreq currentmov pc,lr.unreq result.unreq remainder.unreq shift

你可能毫無疑問的認為這是個非常高效的作法。它是很好,但是除法是個代價非常高的操作,並且我們的其中一個願望就是不要經常做除法,因為如果能以任何方式提升速度就是件非常好的事情。當我們檢視有迴圈的優化程式碼時,我們總是重點考慮一個問題,這個迴圈會執行多少次。在本案例中,在輸入為 1 的情況下,這個迴圈最多執行 31 次。在不考慮特殊情況的時候,這很容易改進。例如,當 1 除以 1 時,不需要移位,我們將把除數移到它上面的每個位置。這可以通過簡單地在被除數上使用新的 clz 命令並從中減去它來改進。在 1 ÷ 1 的案例中,這意味著移位將設定為 0,明確地表示它不需要移位。如果它設定移位為負數,表示除數大於被除數,因此我們就可以知道結果是 0,而餘數是被除數。我們可以做的另一個快速檢查就是,如果當前值為 0,那麼它是一個整除的除法,我們就可以停止迴圈了。

clz dest,src 將第一個暫存器 dest 中二進位制表示的值的前導零的數量,儲存到第二個暫存器 src 中。

.globl DivideU32DivideU32:result .req r0remainder .req r1shift .req r2current .req r3clz shift,r1clz r3,r0subs shift,r3lsl current,r1,shiftmov remainder,r0mov result,#0blt divideU32Return$divideU32Loop$:  cmp remainder,current  blt divideU32LoopContinue$    add result,result,#1  subs remainder,current  lsleq result,shift  beq divideU32Return$divideU32LoopContinue$:  subs shift,#1  lsrge current,#1  lslge result,#1  bge divideU32Loop$divideU32Return$:.unreq currentmov pc,lr.unreq result.unreq remainder.unreq shift

複製上面的程式碼到一個名為 maths.s 的檔案中。

3、數位字串

現在,我們已經可以做除法了,我們來看一下另外的一個將數位轉換為字串的實現。下列的虛擬碼將暫存器中的一個數位轉換成以 36 為底的字串。根據慣例,a % b 表示 a 被 b 相除之後的餘數。

function SignedString(r0 is value, r1 is dest, r2 is base)  if value ≥ 0  then return UnsignedString(value, dest, base)  otherwise    if dest > 0 then      setByte(dest, '-')      set dest to dest + 1    end if    return UnsignedString(-value, dest, base) + 1  end ifend functionfunction UnsignedString(r0 is value, r1 is dest, r2 is base)  set length to 0  do      set (value, rem) to DivideU32(value, base)    if rem &gt 10    then set rem to rem + '0'    otherwise set rem to rem - 10 + 'a'    if dest > 0    then setByte(dest + length, rem)    set length to length + 1    while value > 0  if dest > 0  then ReverseString(dest, length)  return lengthend functionfunction ReverseString(r0 is string, r1 is length)  set end to string + length - 1  while end > start    set temp1 to readByte(start)    set temp2 to readByte(end)    setByte(start, temp2)    setByte(end, temp1)    set start to start + 1    set end to end - 1  end whileend function

上述程式碼實現在一個名為 text.s 的組合檔案中。記住,如果你遇到了困難,可以在下載頁面找到完整的解決方案。

4、格式化字串

我們繼續回到我們的字串格式化方法。因為我們正在編寫我們自己的作業系統,我們根據我們自己的意願來新增或修改格式化規則。我們可以發現,新增一個 a % b 操作去輸出一個二進位制的數位比較有用,而如果你不使用空終止符字串,那麼你應該去修改 %s 的行為,讓它從另一個引數中得到字串的長度,或者如果你願意,可以從長度字首中獲取。我在下面的範例中使用了一個空終止符。

實現這個函數的一個主要的障礙是它的引數個數是可變的。根據 ABI 規定,額外的引數在呼叫方法之前以相反的順序先推播到棧上。比如,我們使用 8 個引數 1、2、3、4、5、6、7 和 8 來呼叫我們的方法,我們將按下面的順序來處理:

  1. 設定 r0 = 5、r1 = 6、r2 = 7、r3 = 8
  2. 推入 {r0,r1,r2,r3}
  3. 設定 r0 = 1、r1 = 2、r2 = 3、r3 = 4
  4. 呼叫函數
  5. 將 sp 和 #4*4 加起來

現在,我們必須確定我們的函數確切需要的引數。在我的案例中,我將暫存器 r0 用來儲存格式化字串地址,格式化字串長度則放在暫存器 r1 中,目標字串地址放在暫存器 r2 中,緊接著是要求的參數列,從暫存器 r3 開始和像上面描述的那樣在棧上繼續。如果你想去使用一個空終止符格式化字串,在暫存器 r1 中的引數將被移除。如果你想有一個最大緩衝區長度,你可以將它儲存在暫存器 r3 中。由於有額外的修改,我認為這樣修改函數是很有用的,如果目標字串地址為 0,意味著沒有字串被輸出,但如果仍然返回一個精確的長度,意味著能夠精確的判斷格式化字串的長度。

如果你希望嘗試實現你自己的函數,現在就可以去做了。如果不去實現你自己的,下面我將首先構建方法的虛擬碼,然後給出實現的組合程式碼。

function StringFormat(r0 is format, r1 is formatLength, r2 is dest, ...)  set index to 0  set length to 0  while index < formatLength    if readByte(format + index) = '%' then      set index to index + 1      if readByte(format + index) = '%' then        if dest > 0        then setByte(dest + length, '%')        set length to length + 1      otherwise if readByte(format + index) = 'c' then        if dest > 0        then setByte(dest + length, nextArg)        set length to length + 1      otherwise if readByte(format + index) = 'd' or 'i' then        set length to length + SignedString(nextArg, dest, 10)      otherwise if readByte(format + index) = 'o' then        set length to length + UnsignedString(nextArg, dest, 8)      otherwise if readByte(format + index) = 'u' then        set length to length + UnsignedString(nextArg, dest, 10)      otherwise if readByte(format + index) = 'b' then        set length to length + UnsignedString(nextArg, dest, 2)      otherwise if readByte(format + index) = 'x' then        set length to length + UnsignedString(nextArg, dest, 16)      otherwise if readByte(format + index) = 's' then        set str to nextArg        while getByte(str) != '\0'          if dest > 0          then setByte(dest + length, getByte(str))          set length to length + 1          set str to str + 1        loop      otherwise if readByte(format + index) = 'n' then        setWord(nextArg, length)      end if    otherwise      if dest > 0      then setByte(dest + length, readByte(format + index))      set length to length + 1    end if    set index to index + 1  loop  return lengthend function

雖然這個函數很大,但它還是很簡單的。大多數的程式碼都是在檢查所有各種條件,每個程式碼都是很簡單的。此外,所有的無符號整數的大小寫都是相同的(除了底以外)。因此在組合中可以將它們匯總。下面是它的組合程式碼。

.globl FormatStringFormatString:format .req r4formatLength .req r5dest .req r6nextArg .req r7argList .req r8length .req r9push {r4,r5,r6,r7,r8,r9,lr}mov format,r0mov formatLength,r1mov dest,r2mov nextArg,r3add argList,sp,#7*4mov length,#0formatLoop$:  subs formatLength,#1  movlt r0,length  poplt {r4,r5,r6,r7,r8,r9,pc}    ldrb r0,[format]  add format,#1  teq r0,#'%'  beq formatArg$formatChar$:  teq dest,#0  strneb r0,[dest]  addne dest,#1  add length,#1  b formatLoop$formatArg$:  subs formatLength,#1  movlt r0,length  poplt {r4,r5,r6,r7,r8,r9,pc}  ldrb r0,[format]  add format,#1  teq r0,#'%'  beq formatChar$    teq r0,#'c'  moveq r0,nextArg  ldreq nextArg,[argList]  addeq argList,#4  beq formatChar$    teq r0,#'s'  beq formatString$    teq r0,#'d'  beq formatSigned$    teq r0,#'u'  teqne r0,#'x'  teqne r0,#'b'  teqne r0,#'o'  beq formatUnsigned$  b formatLoop$formatString$:  ldrb r0,[nextArg]  teq r0,#0x0  ldreq nextArg,[argList]  addeq argList,#4  beq formatLoop$  add length,#1  teq dest,#0  strneb r0,[dest]  addne dest,#1  add nextArg,#1  b formatString$formatSigned$:  mov r0,nextArg  ldr nextArg,[argList]  add argList,#4  mov r1,dest  mov r2,#10  bl SignedString  teq dest,#0  addne dest,r0  add length,r0  b formatLoop$formatUnsigned$:  teq r0,#'u'  moveq r2,#10  teq r0,#'x'  moveq r2,#16  teq r0,#'b'  moveq r2,#2  teq r0,#'o'  moveq r2,#8    mov r0,nextArg  ldr nextArg,[argList]  add argList,#4  mov r1,dest  bl UnsignedString  teq dest,#0  addne dest,r0  add length,r0  b formatLoop$

5、一個轉換作業系統

你可以使用這個方法隨意轉換你希望的任何東西。比如,下面的程式碼將生成一個換算表,可以做從十進位制到二進位制到十六進位制到八進位制以及到 ASCII 的換算操作。

刪除 main.s 檔案中 bl SetGraphicsAddress 之後的所有程式碼,然後貼上以下的程式碼進去。

mov r4,#0loop$:ldr r0,=formatmov r1,#formatEnd-formatldr r2,=formatEndlsr r3,r4,#4push {r3}push {r3}push {r3}push {r3}bl FormatStringadd sp,#16mov r1,r0ldr r0,=formatEndmov r2,#0mov r3,r4cmp r3,#768-16subhi r3,#768addhi r2,#256cmp r3,#768-16subhi r3,#768addhi r2,#256cmp r3,#768-16subhi r3,#768addhi r2,#256bl DrawStringadd r4,#16b loop$.section .dataformat:.ascii "%d=0b%b=0x%x=0%o='%c'"formatEnd:

你能在測試之前推算出將發生什麼嗎?特別是對於 r3 ≥ 128 會發生什麼?嘗試在樹莓派上執行它,看看你是否猜對了。如果不能正常執行,請檢視我們的排錯頁面。

如果一切順利,恭喜你!你已經完成了螢幕04 教學,螢幕系列的課程結束了!我們學習了畫素和幀緩衝的知識,以及如何將它們應用到樹莓派上。我們學習了如何繪製簡單的線條,也學習如何繪製字元,以及將數位格式化為文字的寶貴技能。我們現在已經擁有了在一個作業系統上進行圖形輸出的全部知識。你可以寫出更多的繪製方法嗎?三維繪圖是什麼?你能實現一個 24 位幀緩衝嗎?能夠從命令列上讀取幀緩衝的大小嗎?

接下來的課程是輸入系列課程,它將教我們如何使用鍵盤和滑鼠去實現一個傳統的計算機控制台。