Bit-TrickCGDB

利用 Bit-Trick 實作分支陳述式

根據 C 語言規格書中 6.8.4 所定義的 Context-free grammar

selection-statement:
          if ( expression ) statement
          if ( expression ) statement else statement
          switch ( expression ) statement

倘若我們選擇了第一條 production rule,那麼 gcc 一定會產生 Branch Instructions。基於效能上的需求,可以使用以下實作。

假設存在兩個有號整數: int32_t a, b; 和分支陳述式 if (b < 0) a++; , 那麼分支陳述式可以取代為 a -= b >> 31;

一開始我們定義 b 是一個有號整數,因此 b 右移 31 位後,其值必為 Sign Bit 。也就是說,如果 b > 0, 那麼 b >> 31 必為 0。如果 b < 0, 那麼 b >> 31 必為 -1。a -= -1; -> a = a - (-1) -> a = a + 1; -> a++;

可以用 GDB 來觀察

7 a = 3; b = -5; c = 7; d = 11;
8 a -= b >> 31;
9 c -= d >> 31;

p/x b
$1 = 0xfffffffb
p/x d
$2 = 0xb
p/x b >> 31
$3 = 0xffffffff
p/x d >> 31
$4 = 0x0

-完-

廣告
Bit-TrickCGDB

白板上的程式碼

幾天以前我被要求在白板之上,使用不多於三分鐘的時間,寫出 Big Endian to Little Endian 和 Little Endian to Big Endian 的 C 語言程式碼。

要實作出這兩個函式,除了要知道 MSB 和 LSB 的 Byte Order 不一樣之外,還要考慮 Data 是 Unsigned, 還是 Signed ? 是 32 位元,還是 64 位元?

我以 32 位元作為例子分享給大家。

轉換函式
int32_t ltob(int32_t num) {
    return (num >> 24 & 0x000000FF) ^
            (num >> 8 & 0x0000FF00) ^
            (num << 8 & 0x00FF0000) ^
            (num << 24 & 0xFF000000);  
}
測試程式
void main() {
    int32_t l = -0x12345678;
    int32_t b = ltob(l);
    while (1);
}
使用 GDB 進行驗証

$ gcc -g -o test test.c

(gdb) p/x l
$1 = 0xedcba988
(gdb) p/x b
$2 = 0x88a9cbed

不出所料,在 GDB 中能看到預期的結果。接著,在 GDB 中觀察以下的 Byte Order 變化。

(gdb) p/x l
$5 = 0xedcba988
(gdb) p/x l >> 24
$6 = 0xffffffed
(gdb) p/x l >> 24 & 0x000000FF
$7 = 0xed

從上述的觀察可以得出結論︰Operator Shift 決定了新的 Byte Order,Operator And 消除多餘的 Byte。同樣的道理可以轉換其他的 Byte ,最後用 XOR 組合它們即可。


[註]︰可以利用 Objdump 觀察機器的 Endian

void main() {
    int32_t l = 0x12345678; 
}

$ gcc -o test test.c
$ objdump -d test


  400589:   55                      push   %rbp
  40058a:   48 89 e5                mov    %rsp,%rbp
  40058d:   c7 45 fc 78 56 34 12   movl   $0x12345678,-0x4(%rbp)
  400594:   b8 00 00 00 00          mov    $0x0,%eax
  400599:   5d                      pop    %rbp
  40059a:   c3                      retq   
  40059b:   0f 1f 44 00 00          nopl   0x0(%rax,%rax,1)

– 完 –