2013年1月4日 星期五

深入研究 C語言 三元運算子 ( x ? y : z ) (完)

不可否認的事實,C 語言做為最基礎的程式語言,已經超過 25 年歷史依然持續站在
眾多程式語言最上層的王座,完全無可撼動的崇高地位再一次說明作為 OS 母程式語言
所擁有的絕對優勢,絕對不是其他語言可以輕易挑戰,有興趣可以參考
TIOBE 這是一個專門研究世界上數千種程式語言的使用率級排行榜的專業網站。


假如有去看,你可能會覺得奇怪 組合語言呢? 怎麼可能名次這麼差(不過至少有30名內),喔因為這是主要以在 x86 windows 作業系統上人們用的語言來做統計,組合語言就躲得更底層了,它怎麼可能會消失,你隨便逛一下 Microchip 網站,或其他晶片商網站也可以,基礎範例用組合語言寫的多到你看不完,x86 跟它搭配的 OS 是因為太成熟所以很多人沒感覺。

雖然這麼多人在寫 C 語言,但是 你真的對它了解嗎 ? 這就是我本篇要講的短篇題文,本來承接上一篇應該要切入另外一種重要的玩法,從 FASM 呼叫 C 的副常式,間接引出一種自創引導進入點的做法,但是我覺得要中場休息一下,發一些小文,本篇目依然繼承上一篇的思路,還記得上一篇有說過千萬別小看編譯器,這篇就要聊聊編譯器的智慧,有時候它會產生讓你驚呼的組譯碼是你自己用手寫也想不到的聰明。

C語言有很多運算子相信你也背不出來 (這邊有包含 C++ 的運算子),一共 58 種運算子
被分為17類,而 唯一的三元運算子 ( Ternary Operator )  被分類在第15類由上數到下是
第 45 種運算子,為什麼會提到它呢,因為我還記得第一次追蹤這種運算子的組譯碼時,我看到編譯器翻譯出來的程式碼讓我非常驚嘆,所以才會印象深刻,甚至連那個翻譯碼的片段
都背起來了,以後自己手寫組語也用類似的手段處理,要能寫出這種碼,那得要最組語指令
運算的細節要掌握透徹才有可能,因為這個片段用到了即使常常使用組語的人也不見得
很清楚的冷僻細節,即是 CF (進位旗標),應該說不會特別去研究這個玩意能搞出甚麼花樣
沒錯,微軟寫編譯器那些大師們的確就發現了新花樣,讓 Ternary Operator 轉譯為組語時,不
需要使用跳躍指令。

Ternary Operator  ? : ,讀者們應該都知道它的意義,它是 if ... else .. 的短語版
甚麼意思

      val = x ? y : z ;

等價於

        if(x == true) val = y;
        else          val = z;


很清楚吧,因為 C 語言是 不等於零 就是 true,只有 等於零 才稱為 false,所以說
x 這個條件假如出現 0,val 被指定的值就會是 z,否則就是 y。

常常寫組合語言的人應該會馬上聯想到實現的方式當然用 cmp 配 jxx 跳躍指令 :

          mov ebx,[ebp-12]; 假設 y 放在 [ebp-12]
          mov ecx,[ebp-16]; 假設 z 放在 [ebp-16] 
          mov eax,[x]          
          cmp eax, 0      ; 假設條件 x 放在 eax
          jz  eq_zero     ; 組語的邏輯常常都是錯誤條件先判斷
          mov [ebp-8],ebx ; 假設 val 放在[ebp-8], ebx 代表 y
          jmp label;
eq_zero:                  ; 等於 0 則跳來這裡 
          mov [ebp-8],ecx ; ecx 代表 z
label:
          ...             ; 繼續往下執行程式 ...

這是慣用組語的人常常愛用的 Pattern Code,大概有寫過一點組語也都知道這個常識
這個組語邏輯慣用的 Pattern Code 一般是要背起來直接使用。

可是 當 y 與 z 都是數值的時候,這個時候就有可以投機取巧的地方了,來看看一個例子

val = x ? 0xc2 : 0x0a ; 現在 y = 0xc2, z = 0x0a

你直接套用上面的 Pattern Code 就可以達成上面 C 語言這種運算式的功能,現在讓我們來
看看 CL 它對付上面這種語句用怎樣的思考模式,下面是 CL 產生的組譯碼 :

0.    mov eax,[x]   ; eax ← [x] 
1.    neg eax       ; eax ← ~eax + 1 (等價於 -eax)
2.    sbb eax,eax   ; eax ← eax - (eax + CF)
3.    and eax,0b8h  ; eax ← eax & 0b8h
4.    add eax,0ah   ; eax ← eax + 0ah
5.    mov [val],eax ; [val] ← eax

什麼!! CL 產生的組譯碼竟然不需要用到 jxx 之類的指令,用純運算就達成這種效果,這倒底
是怎麼辦到呢 ? 讓我們一行一行分析看看~~

首先,第零行沒甚麼需要研究的地方,直接把 x 的內容放到 eax,準備用 eax 來運算,有趣
的地方是從第一行開始,CL利用了 neg 指令,它會使得運算元變成負數,或者說是二補數
另外一個重要的特性是當運算元不等於零,會導致 CPU 設定 x86 的旗標 CF = 1,表示
剛剛的運算結果是有進位,只有一種情況使 CF = 0,就是當運算元等於零,CF 就會被設定
為零,也就是說可以寫成下面結果

if val eq 0 then val ← 0 and CF ← 0 else
val ← ~val + 1 and CF ← 1



現在考慮兩種情況 eax 等於零 與 eax 不等於零

Case 1: eax 等於零
等於零的時候會導致 CF=0,所以當執行到第二行的時候遇到 sbb 指令,神奇的效果就出現了,sbb 的定義我已經在程式註解寫得很清楚了,當 op1 與 op2 都填一樣的參數時,像
sbb eax, eax 這種語句,神奇的地方在於這種技巧就可以很巧妙的抽出 -CF 值,所以其實
上面這條語句就是做 eax = -CF ,但是現在 CF = 0 不影響所以 eax = 0,所以第三行
利用一條指令 and 來做邏輯條件,and 的特性就是只要有一個 運算元 為零輸出就是零,
所以結果就是 eax = 0,第三行就乾脆利用加法直接把 eax 目前值與 0a 相加在存回 eax,所以
這樣不就達成了 當ternary operator的條件式為 false 的時候 選擇傳回 0a 的效果 !!

Case 2: eax 不等於零
不等於零才是我們興趣所在之處,neg 指令剛剛有提到,只要運算元不等於零,一定會導致CPU 將 CF 旗標設定為 1,所以神奇的地方出現啦,前面有提到第二行利用 sbb 指令的
特性將 -CF 值抽出來,然後傳給運算元,所以結果是 eax = -CF = -1,你從二補數觀點來看,原來 eax = 0xffffffff,然後在配合下一行指令,and 邏輯條件,喔 這真是太神奇了,這樣
0b8 就被選中了,所以在寫回 eax 則變成 eax = 0b8,看到了沒有,然後下一步在來個 add
跟 0x0a 相加,在寫回 eax,你就得到了 你在 C 語言裡面寫的 true 成立條件要傳回的值 0xc2
這樣就達成了 當ternary operator的條件式為 true 的時候 選擇傳回 0c2 的效果 !!
下面那行寫回 val 變數當然沒啥好討論的地方。

0.0+ 假如你有仔細看懂,你就會驚呼一聲,竟然有這種巧妙的方法達成邏輯條件回傳值的選擇,所以把數學學好是很重要的事情,這裡面就用到了邏輯指令、補數、對指令如何影響旗標變化與利用加法補回值剛好等於 true 所要回傳的值,才會寫下這麼經典的片段,只能佩服
微軟內寫 C編譯器的大師們,這是很好的一課阿~~。

所以這個特別的 Code Pattern 的一般性結論我寫在下面 :

C 語言 :
          val = x ? y : z ; 假設 y 與 z 都是數值

組譯碼 :

0.    mov eax,[x]   ; eax ← [x] 
1.    neg eax       ; eax ← ~eax + 1 (等價於 -eax)
2.    sbb eax,eax   ; eax ← eax - (eax + CF)
3.    and eax,y-z   ; eax ← eax & (y-z)
4.    add eax,z     ; eax ← eax + z
5.    mov [val],eax ; [val] ← eax


現在你就知道了,編譯器有時候比你聰明,這種用法並不值觀但是速度快,這種用法
大概只有那群以寫編譯器為職業的人才會想得出來,因為他們比只會用組語寫程式的人
更精通所有指令的細節,把它們當專門的學問在研究,編譯器的最佳化競賽直到現在
仍然沒有停止的跡象。

可不是這樣就結束了,了解這段程式碼還不夠,要了解這種奇妙的方法還得要探討
這是用甚麼樣的哲理,才會有這種想法,這個比知道這段程式碼更重要。

假如你有認真領悟到裡面的哲理,你就會發現這種根本不是寫組合語言的思維模式,
怎麼講 ? 搞程式技術的人常常會說 你用甚麼程式語言就應該懂得

      Thinking in 你用的程式語言 !

這句話是每個搞程式技術的人都知道,但是很遺憾這句話不是永遠成立,上面提到的那個
奇妙想法,就是一個例子,這種想法一般是存在於很接近給設計硬體的人使用,沒錯!!!!!!!
就是硬體描述語言 VHDL 或 Verilog ,我猜微軟寫編譯器的某成員可能還沒跳槽之前,有從事過 VHDL 或 Verilog 編譯器的撰寫,才會發現到有這種技巧,這才是本文的重點
喔,原來是把比組語更低階的原語 設計硬體邏輯語言的想法 搬到組合語言來用,這種語法根本就是好像在設計邏輯電路一樣,因為在邏輯電路上,你可沒辦法用甚麼 jxx 之類的
跳躍指令,硬體不會跳躍,硬體很笨,只會 trigger,你只能想盡辦法用基本邏輯電路
not and or xor (互斥基本上已經被直接算在基本邏輯元件),然後 在配合 時序 也就是 正反器
邏輯電路去想辦法拼拼湊湊 弄出各種邏輯電路去阻擋訊號或是讓訊號通過來達成設計者想要的條件邏輯,現在不妨把那段奇妙的程式碼當成某抽象硬體電路來看看。

? : 運算子的抽象邏輯電路

mov 指令在硬體實現上 可以想像為某種 傳輸介面,例如我用 UART 以序列傳入 CPLD 中
然後用 D型正反器(DFF) 來存放,DFF就是硬體級的 1-bit 記憶體,這個 mov 實際用 VHDL實作內部還要用到計數器一個一個 bit 累加存入暫存器,所以我才會講說是一種抽象邏輯電路而已,這邊不探討每個 block 裡面的 VHDL 怎麼寫,光 mov 那塊用 UART 傳輸
VHDL 可就要分好幾塊來寫在合成一塊,所以知道抽象概念就好,另外你看到怎麼有一個
Trigger 方塊 這個是做甚麼用的阿? 這就是硬體跟軟體最大的不同硬體可以同步做一堆
事情,你要用 Trigger 去擋才可以,結果才不會錯,就是說要等 sbb 方塊吐出 -CF 導致觸發
才允許 z 值傳遞過去做最後的累加放入 val ,在硬體上我們可以先存在 DFF 裡面,也許你
可能會在寫一個 VHDL 轉並列訊號轉序列訊號又傳回電腦看看值是否正確,這很重要
我這樣的設計其實沒有很嚴謹,不能保證 and block 輸出跟 trigger block 輸出一定同時會到達
add block,這個用在低頻訊號大概也沒甚麼問題,不過高頻應該可能會產生錯誤結果,
不過 Trigger block 已經有初步同步的功能,沒加會更慘,能正確運作的頻率更低,至少
我以前實現在 3.456MHz 是可以 work,往上更高呢 ? 不知道,我也沒試過。

0.0+ 你說我的CPLD開發版頻率數字怎麼這麼奇怪 ? 因為這樣跟 UART 的頻率才能湊成
整數倍阿,你大概也發現了,原來我為了研究這個神奇的技巧,還瘋狂的找了一塊
CPLD 開發版,等於我也實作過硬體版的 Ternary Operator,不過 CPLD 玩一玩覺得不好玩我大部分時間還是專注在寫 x86 上的程式這個還是比較有趣,至於 CPLD 就讓它消失在我
的記憶中吧,上面那個方塊圖可不是瞎扯,我當時也要依照這樣的想法寫出了VHDL版,
當然查閱資料撰寫 VHDL 也要花不少時間,讀者有興趣也可以自己試試看。

下一篇就要回到正題囉,從 FASM 呼叫 C 副常式來自創 C 語言進入點。

(完)

9 則留言:

  1. 這個三元運算子我知道
    UART的SDA很常用
    但是用邏輯電路去做我就想不到了...

    現在CPLD還在喔
    還記得葉立安當年弄爆一片

    回覆刪除
  2. : P 夜風果然也是高手阿~~~ ㄎㄎ
    最近有甚麼夜風有甚麼好玩的東西嗎 ?

    SDA? 喔 夜風用的 UART 是與 I2C 共用pin腳型的8051阿~~~ Cool!
    你那顆 8051 是特殊的嗎 ? 還是 datasheet 我在網路上就能下載來看 ??

    因為 I2C 的腳位是 SDA SCL ; 我只能說現在 IC 設計師實在太猛
    我手上這塊 8051 是 cy7c68013a, 它的 I2C 跟 UART 就分開

    不過它的 I2C 有一個特殊功能,就是你可以把程式預先燒錄在 I2C EEPROM
    cy7c68013a 開機直接使用裡面固化的程式,為什麼呢 ?

    囧,它沒有 flash 它的內部是 SRAM 關機就會消失的那種

    像 PIC 好像現在還有直接乾脆提供 Master Synchronous Serial Port (MSSP)
    反正就是看 datasheet 去調整暫存器看你想使用的模式

    應該說 UART I2C SPI 它們硬體實在太像了,其實你用 VHDL 實作 I2C or SPI
    還是得要先實作出 UART ~~~ 因為 UART 是一切串列通訊的基礎阿~~~

    喔 你說 CPLD ㄎㄎ 印表機的 TEA3717 又爆了 今天才去修好一台 ;
    我是玩實驗室老師沒有拿來上課用的那款比較新型的 Altra MAX ;
    哈哈 那位同學不是傳說中 號稱 眼神要很銳利的神人嗎~~~

    回覆刪除
    回覆
    1. 3717只要電壓一不對 MOS很快就爆了
      感覺每次都是爆那個

      我要去查一夏日不是真的共用腳位
      I2C是自己找空腳做的

      刪除
    2. 我寄給你那個 USB MOUSE 韌體範例
      是 P89C61X2BA + PDIUSBD11
      P89C61X2BA 這顆8051算是通用型8051沒甚麼特殊功能裡面算高級的8051
      它的boot code是用硬體完成,所以買來用 UART可以直接 download 韌體
      可是 PDIUSBD11 要用 I2C 去控制 這個控制器的暫存器
      因此 以前做這片的時候 我也是用 GPIO 去模擬 :)

      夜風之前提到架構的問題 不妨可以根據你目前的程式 想一想怎麼來封裝
      架構其實只是一種對程式封裝的技巧,每個人的作法都會不一樣

      就像 P18F4550 要 Enable 晶片的 USB中斷 是很麻煩的事情 每次都要呼叫
      四條指令

      RCONbits.IPEN = 1;
      IPR2bits.USBIP = 1;
      PIE2bits.USBIE = 1;
      INTCONbits.GIEH = 1;

      怎麼封裝,你就把它們用 #define 弄成 HAL 型式 還可以實現多版本
      #define __P18F__
      #define USBEnableInterrupts() \
      { \
      #ifdef __P18F__
      RCONbits.IPEN = 1; /*中斷優先次序致能*/ \
      IPR2bits.USBIP = 1; /*USB中斷次序最先*/ \
      PIE2bits.USBIE = 1; /*USB中斷致能*/ \
      INTCONbits.GIEH = 1; /*致能所有高優先中斷*/ \
      #elif __DSPIC33__
      // 實作其他晶片版本
      #endif
      }

      程式裡面呼叫這個 USBEnableInterrupts()就好了
      microchip的晶片向來都很麻煩一件事情喜歡提供一堆暫存器來微調
      沒有 有系統化的技巧來寫程式 可是會煩死人。

      為什麼不用副程式方法寫 原因很簡單 "慢"
      程式跳躍又跳回來這是很浪費晶片執行資源的事情
      寫晶片程式要盡量用HAL的方法來寫 不是直接操作 暫存器
      這樣才能增加可讀性,操作暫存器的動作封裝在HAL裡面

      刪除
    3. 原來是SPI和UART共用
      I2C是自己找空腳位完成的

      刪除
    4. 話說你給我的那個檔案 有個des檔
      那是設置大量的前置處理器用的嗎?

      刪除
    5. 0.0 你被我誤導囉,其實 C 語言的Header file副檔名不一定要 .h
      啦 只是說 usb 第9章 實在太重要了,我把附檔名改成 .des

      你可以參考 D11chap9.c 我裡面有一行

      #include "chap9.des"

      當時只是為了增加可讀性 因為 usb 有名的 chap9 在實現韌體上有一堆
      descriptor要描述,我在寫的時候 故意把這個特別的表頭弄成 .des

      你也可以改檔案名稱為 chap9desc.h

      D11chap9.c 裡面就變成

      #include "chap9desc.h"

      C 的#include指令不管副檔名
      反正編譯器就是將被含括檔把裡面的內容貼過來整個換掉

      刪除
    6. 還有 des 檔案裡面 你有看到 code 的部分
      那個是 強迫編譯器把 資料放在 code section
      因為 usb 的 descriptor 都蠻占空間的阿
      放在 code section 裡面才夠用 否則編譯不會過

      刪除
  3. 0.0+ 這個其實就引出了 CPU 指令設計的觀念
    假如今天我設計一個 CPU 直接含括這樣的硬體電路
    在指令集上面 設計一個 假設稱為 tny 的指令
    並且假設 條件要放在 eax 暫存器,會傳值也放在 eax

    以後寫程式的人只要

    mov eax, 0;
    tny 1, 2;

    這樣執行指令 eax 結果就會存放 2

    因為 tny 在 CPU 底層直接硬體實現沒有 micro code
    所以 tny 就可以被稱為 精簡指令 (Reduced Instruction)

    回覆刪除