2011年8月11日 星期四

[C語言] 兩變數內容值互換技巧

記得大學時, C語言課程一定會談到兩變數內容值互換技巧, 其方法利用暫存空間實現, 如底下程式碼所示:

void swap(int *a, int *b)

{
int tmp;

tmp = *a;
*a = *b;
*b = tmp;
}


然而, 有幾個方法不使用暫存空間便能達到此目的.

方法一 使用三次互斥或 (Exclusive OR, XOR)
void swap(int *a, int *b)

{
if(*a != *b) {
*a = *a ^ *b;
*b = *a ^ *b;
*a = *a ^ *b;
}
}


演算式如下所示:


簡化上段程式碼: 試想底下程式碼有沒有什麼問題?
#include <stdio.h>                                                      


void swap(int *a, int *b)
{
if(*a != *b)
*a ^= *b ^= *a ^= *b;
}

int main(void)
{
int a = 11, b = 3;

printf("===== before swapping =====\n");
printf("a: %d, b: %d\n", a, b);

swap(&a, &b);

printf("===== after swapping =====\n");
printf("a: %d, b: %d\n", a, b);

return 0;
}


直接看執行結果:


為什麼會這樣呢? 筆者將此C程式碼用gcc編譯成組合語言, 用以了解其運作邏輯, 底下為swap函式片段程式碼, 完整組合語言程式碼請按此連結下載.

程式堆疊示意圖

程式說明:
由於使用一行程式碼做三次XOR, gcc編譯器會先把*a, *b, *a, *b的內容放在edx(11), ecx(3), ebx(11), eax(3)暫存器 (line 9-16), 然後再分別對這四個暫存器做三次的XOR:
  • line 18-20: 第一次XOR (eax=3 XOR ebx=11), 並將其結果 (ebx=8)回存到變數a的記憶體位址, 如下圖所示:
  • line 21-25: 第二次XOR (eax=8 XOR ecx=3), 並將其結果 (ecx=11)回存到變數b的記憶體位址, 如下圖所示:
  • line 26-30: 第三次XOR (eax=11 XOR edx=11), 並將其結果 (edx=0)回存到變數a的記憶體位址, 如下圖所示:
所以問題在於, 程式設計師不能在一行程式碼中, 對同一變數做兩次的運算, 否則會造成不可預知的結果, 切記!

方法二 使用加減法
void swap(int *a, int *b)

{
if(*a != *b) {
*a = *a + *b;
*b = *a - *b;
*a = *a - *b;
}
}

演算式如下所示:


【Reference】
[1] XOR - the magic swap
[2] XOR swap

2011年8月5日 星期五

簡介C語言volatile關鍵字及其陷阱

volatile變數代表其所儲存的內容會不定時地被改變,宣告volatile變數用來告訴編譯器 (Compiler) 不要對該變數做任何最佳化操作,凡牽涉讀取該volatile變數的操作,保證會到該變數的實體位址讀取,而不會讀取CPU暫存器的內容 (提升效能) 。舉個例子,某一硬體狀態暫存器 (Status Register)就必須宣告volatile關鍵字,因為該狀態暫存器會隨時改變,宣告volatile便可確保每次讀取的內容都是最新的。

Volatile關鍵字的應用範疇
1. 硬體暫存器,如狀態暫存器。
2. 多執行緒所共用的全域變數。
3. 中斷服務函式 (Interrupt Service Rountie,ISR)所使用的全域變數。


Volatile陷阱
想想底下範例是否有問題?


#include <stdio.h>

int square(volatile int *var)
{
return *var **var;
}

int main(void)
{
int var = 5;

printf("result: %d\n", square(&var));
return 0;
}


其問題在於square函式的平方算式,*var**var,此指令代表到var位址讀取其內容。然而,var位址可能儲存硬體暫存器,這些暫存器內容會隨時間而改變 (例如: 狀態暫存器),有可能第一次讀取的時候為4, 下一次讀取為5, 導致計算出來的值不正確。

因此,避免此錯誤發生便是在square函式宣告一local變數,看底下程式範例較為清楚:



#include <stdio.h>

int square(volatile int *var)
{
int local_var = *var;

return local_var * local_var;

}

int main(void)
{
int var = 5;

printf("result: %d\n", square(&var));
return 0;
}


【Reference】
[1] How to Use C's volatile Keyword