網頁

2006年2月22日 星期三

Makefile用法

OBJS = foo.o bar.o
CC = gcc
CFLAGS = -Wall -O -g

myprog : $(OBJS)
$(CC) $^ -o $@

foo.o : foo.c foo.h bar.h
$(CC) $(CFLAGS) -c $< -o $@
bar.o : bar.c bar.h
$(CC) $(CFLAGS) -c $< -o $@

$<為最靠近冒號的第一個
$^為苜號以後所有的東西

.clean:   
rm edit $(objects)

更安全的作法PHONY表示clean為一個偽裝目標,也就是說,不管clean這個目標發生什麼問題,都繼續執行 
.PHONY : clean
clean :   
-rm edit $(objects)

patsubst是把第二個參數換成第一個參數中所指定的pattern,而第三個參數則是代表所有要代換的東西
%.o:%.c ${CC} ${CLAGS} -o ${patsubst %.o,%,$@} ${STATIC_LIBS}
${CC} ${CLAGS} -o ${@:.o=.cgi} ${STATIC_LIBS}

通配符自動在規則中進行。但是在變量賦值的和函數的參數中通配符不會擴展,如果在這些情況下需要通配符擴展,
必須使用'wildcard'函數。語法如下:
$(wildcard PATTERN...)
這個在makefile任何地方出現的字符串,會被匹配任何一個文件名格式的以空格隔開的現有文件列表替換。
如果沒有任何文件匹配一個模式,這個模式從'wildcard'的輸出中忽略,注意,這和上述的通配符的處理是不一樣的。
wildcard'函數的一個功能是找出目錄中所有的'.c'文件:
$(wildcard *.c)
可以通過替換後綴'.c''.o'C文件列表得到目標文件的列表:
$(patsubst %.c,%.o,$(wildcard *.c))
這樣,上節中的makefile改寫為:
objects := $(patsubst %.c,%.o,$(wildcard *.c))
foo : $(objects) cc -o foo $(objects)

這個makefile利用了編譯C程序的隱含規則,所以不需要對編譯寫出顯式的規則。
':=''='的一個變體) 注意:'PATTERN'是大小寫敏感的。

2006年2月20日 星期一

《陣列》多維動態陣列

《陣列》多維動態陣列

多維動態陣列在 C 中 大概只能用 malloc,但這在一維時尚
不構成問題,但需要多維陣列時怎麼辦呢?這算是程式論壇
最常被問到的問題之一了。
我把它整理了相關的回覆,都只用二維做說明,更多維的陣列
類推即可。
就從 C 談起吧!

動態產生一個[m][n]陣列 Array 的方法


code:------------------------------------------------------------------
int i;
int **Array;
Array= (int **)malloc(m*sizeof(void *));
for (i=0; i<m; i++)
Array=(int *)malloc(n*sizeof(int *));
--------------------------------------------------------------------------

這樣你就有一個 int Array[m][n]; 可以用了
是C 喔!不是 C++
但這不夠好,若你要的是一個較大的mXn陣列,那麼太多的malloc
會使記憶體碎片化(memory fragment)!沒關係,窮則變,變則通!
問題既出在for loop不斷的 memory allocation,就從那兒下手:

code:---------------------------------------------------------------------
int i;
int **Array, *pData;
Array= (int **)malloc(m*sizeof(int *));
pData= (int *)malloc(m*n*sizeof(int));
for (i=0; i<m; i++, pData+=n)
Array[i]=pData;
---------------------------------------------------------------------------

注意到嗎?這次只用了二次的malloc。
當要release memory也只要free Array[0] 和 Array 就成了!
(注意先free Array[0] 再 free Array)
如果嫌兩個alloc/free還是太多,也可簡單併成一個:

code:-----------------------------------------------------------------------
int i;
int **Array, *pData;
Array= (int **)malloc(m*sizeof(int *)+m*n*sizeof(int));
for (i=0,pData= (int *)(Array+m); i<m; i++, pData+=n)
Array[i]=pData;
----------------------------------------------------------------------------

要 free 時只要 free Array 就行了,帥吧?
如果用的是C++,那可用的方法就更多了!

《幼幼班》嘗試錯誤的階段
?> int Array[][] = new int [10][20];//這樣行ㄇ?
當然不行! int Array[][]不是一個指標,而且只能有
一維為不定大小。

《小班》終於會從1數到100了
?> 那...
?> int *Array[] = new int [10][20];//這樣行ㄇ?
有點想法了!但可惜的是 '*' 在 C++的語法是修飾前面的
識別字,所以 int *Array[]的意思是 "Array是一個 int 指標
的一維陣列!"

如果能使那個 '*' 以獨立指標型態去宣告Array,就會變成
"Array是一個指標,指向一維 int 的陣列",而我們知道指標
本身就可以當做一維的陣列,那麼是不是就成了"Array是一個二維
的int陣列"?
對了!這正是我們要的!問題是怎麼讓'*'成為獨立指標型態,
不會去修飾前面的int識別字?答案是使用括號:
int (*Array)[20] = new int [10][20];//這是正解!

但問題又來了, new 運算子可以使用 new int [m][n],但
int (*Array)[20] 的 [20]卻沒辦法以 [n] 來取代,所以就
沒辦法做到不定大小的宣告了。所以這只能算是小班的答案,
要做到不定大小的動態多維宣告,加上 STL 的運用,是不錯
的想法。

《中班》vector 模板的運用
vector<int> *array=new vector<int>[m];
for (int i=0; i<n; i++) array[i].reserve(n);
嘿嘿...不錯吧!?不定大小的二維陣列,而且每個維度還
可以隨時調整大小喔!
不過還是有缺點ㄟ!!那行 for loop 看起來有點礙眼,不能
拿掉嗎?拿掉的話,基本上Array 還是二維陣列,但第二維
並沒有預留空間放東西你可以用push.back等成員函式來增加
空間和存放data,但不能在還沒有空間時使用像
array[5][3]=3; 這種陣列的存取方式。沒更好的方法了嗎?
vector 不是有預留空間大小的建構子嗎?像一維的宣告:
vector<int> *Array= new vector <int>(n);
//這不是預留了 n 個元素的陣列了嗎?
只可惜,這是一維的宣告,若你嘗試做這樣的宣告:
vector<int> *Array= new vector <int>[m](n);
編譯器會給你無情的嘲諷:陣列不能呼叫帶參數的建構子!
這是很令人失望的!為十麼不行?不是邏輯的問題,或許下
一版本的C++會可以這樣宣告吧!但為今之計只能自力救濟
了。

《大班》使用模板在模版中
仔細觀察下面的宣告:
vector<vector<int> > Array(m, vector<int>(n));

memory aligment

對一個 16位元的系統來說,意味著,系統有16data bus,各能存取一個
bit資料。
16位元當然就是2bytes,正如我們2個一數,數數會是2,4,6,8一樣,address
也不會(也不需要)出現奇數位置1,3,5,7...
現在來看看硬體存取一個byte在奇偶數地址的情況:
1.
要取偶數位置E時,會抓到 (E,E+1)一個WORD(因為data bus16bits)
因為E是在Lo Byte 所以硬體只要把 Hi Bytes 拋棄掉就成了。
2.
要取奇數位置O時,會抓到 (O-1,O)一個WORD(因為data bus
16bits), 因為O是在Hi Byte 所以硬體得要把 Hi Bytes 搬到 Lo Bytes
才能算完成存取。

看到奇數地址存取會比偶數地址麻煩了嗎?差一點點而已有什麼關係?
好吧!我們再來看看硬體存取一個WORD在奇偶數地址的情況:
3.
要取偶數位置(E,E+1)時,會抓到 (E,E+1)一個WORD,這樣就完成
存取了。
4.
要取奇數位置(O,O+1)時,要先抓到 (O-1,O)取得Lo Byte O,然後
再抓(O,O+1)得到 Hi Byte(O+1),最後合併(O,O+1)才算完成一個奇數
位址WORD的存取。

比較一下3,4,你就不會說只差一點點了吧!?
32位元和64位元的系統,可以類推。這也是為什麼很多編譯器會預設
把變數位置調整在 2/4/8 倍數上來得到較佳的存取效率。
但這樣做會使像結構的資料大小意外的變化,若是某個結構的大小是很重要
的,你就必需找出編譯器相關的設定或directive(VCpack)來控制
aligment

新不定參數的 C 函式

只要寫過 C 程式的人,都用過 printf 這個函式,也都知道它可是一個
不定參數的函式,了解它的運作方式,你也可以實作自己的不定參數的
函式。
先看一下 printf 的原型:
int printf( const char *format [, argument]... );
在format後面的參數不但不定個數且型態也是不定的。
這些參數是one bye one 的堆在stack裡面。
printf這個函式如何正確的取出這些參數?
秘訣就在 format,函式根據format裡的格式("%d %f...")
依序把堆在stack裡的參數取出。而這取出的動作就是用到
va_arg, va_end, va_start這三個macro再加上va_list。
va_list 事實上是一個 char * 的型態:
typedef char * va_list;
其它的三個macro的例子(不同的平台會有不太一樣的macro)
/* A guess at the proper definitions for other platforms */
#define _INTSIZEOF(n) ( (sizeof(n) + sizeof(int) - 1) & ~(sizeof(int) - 1) )

#define va_start(ap,v) ( ap = (va_list)&v + _INTSIZEOF(v) )
#define va_arg(ap,t) ( *(t *)((ap += _INTSIZEOF(t)) - _INTSIZEOF(t)) )
#define va_end(ap) ( ap = (va_list)0 )

這三個macro若看得懂,對了解它們的運作會很有幫助;看不太懂也沒關係
,看一下下面的說明也差不可以了。
首先 va_start 把取出的指標(va_list)指到第一個不定參數。
然後就可以用 va_arg 以指定的型態從va_list取出資料並把va_list
指標移到下一個位置(例如取走了一個int 4 bytes 的資料, va_list便會加 4)
當取完資料後便可使用 va_end 把 va_list 歸零(這個macro應看得懂吧)。
其實對大部份的應用來說 va_end 做不做是沒太大的關係的。

下面是一個不定參數函式的範例(轉載自MSDN):
int average( int first, ... )
{
int count = 0, sum = 0, i = first;
va_list marker;

va_start( marker, first ); /* Initialize variable arguments. */
while( i != -1 )
{
sum += i;
count++;
i = va_arg( marker, int);
}
va_end( marker ); /* Reset variable arguments. */
return( sum ? (sum / count) : 0 );
}

註:_INTSIZEOF 是 int size memory alignment,如果你不知那是什麼
  就把 _INTSIZEOF 看成這樣的定義會比較容易理解:
#define _INTSIZEOF(n) sizeof(n)
為什麼不直接用sizeof(n)就好了,使用 macro 是為了跨平台時能保持運
作正確。若傳了一個2 bytrs的不定參數(如 short),但在一個 32 bits的
平台推入堆疊就會是4個bytes(32 bits)不是2 bytes,所以參數的取出
就要非常的小心。使用_INTSIZEOF 在於保證引數指標移動的正確。


#define _INTSIZEOF(n) ( (sizeof(n) + sizeof(int) - 1) & ~(sizeof(int) - 1) )


令N=sizeof(n)+sizeof (int)-1
X=sizeof()int
若X為2之倍數

_INTSIZEOF(n)可簡化為N&~(X-1)

而原式為N-N%X,以下證明
N&~(X-1)=N-N%X
IF X=1
N&~(1-1)=N&~(0xFFFF..F)=N-N%1

IF X=2
N&~(2-1)=N&~(0xFFFF...FE)=N-N%2

IF X=4
N&~(4-1)=N&~(0xFFFF...FC)=N-N%4

目的為了讓_INTSIZEOF(n)成為X之倍數,也就是sizeof(int)之倍數

memcpy 跟strcpy 用法上的差別

strcpy()只能透過零結尾來判定結束,所以有以下的缺點:
1. 速度慢,因為只能以BYTE為單位執行拷貝。
2. 容易出現overlay/memory-corruption,這有兩個情況,一個是目標緩衝區太小了,另一個是來源忘了零結尾。
3. 重疊的情況時,拷貝會出錯。
char *strcpy( char *strDestination, const char *strSource )

把 strSource copy 到strDestination
因為C 的字串結束是用 0 所以. strcpy 作法是把strSource 中的資料一個一個設定strDestination 一直到0
程式大概是這樣子

while( (*strSource) != 0 )
{
*strDestination =*strSource;
++strDestination;
++strSource;
};
*strDestination=0;

void *memcpy( void *dest, const void *src, size_t count );
把src copy 到dest . 一共copy count 個byte
注意 count 個byte 是一定要給的.
程式大概是這樣寫的
const unsigned char *pSrc=src;
unsigned char *pDest=dest;
for( size_t i=0 ; i < count ; ++i,++pSrc,++pDest)
*pDest=*pSrc;

2006年2月8日 星期三

volatile宣告

volatile unsigned int SlotStart : 4;
volatile不要對這個變數做最佳化
對於一個 address 的值, 如果有可能在其它地方被修改, 例如 被其它 thread 修改, 或是 硬體I/O 修改, 為了要確定讀到的是最新值, 就必需要用 volatile.