一些CRC算法的分析用于确认Orx HashTable的Bug

2010年08月05日

一些CRC算法的分析用于确认Orx HashTable的Bug

上文
我阅读了Orx自己实现的一套hashTable，经我过的初步分析，一个CRC算法作为key是有可能冲突的，但是并没有验证，作为bug提交的话，有些不够完整，所以，我写个测试程序真实的验证一下这个CRC算法，同时，也验证一下自己的分析是否正确。简而言之，就是验证此CRC算法在实际使用中，到底有无冲突的可能。

原理很简单，就是生成一堆字符串，然后传进此CRC算法，然后比较CRC后的值有无重复。此时我真希望可以使用Python，但是想想有写将接口使用Python API让Python使用的功夫，我都已经将测试代码写完了，于是作罢，还是老老实实的用C++吧。

先将整个Orx的Crc算法抽出来，如下：

#include

typedef
unsigned
  long
          orxU32;
typedef
char
                    orxCHAR;
#define orxCHAR_NULL
'0'

#define orxASSERT assert

#define orxSTRING               orxCHAR *

#define orxNULL               (
0
)

static
const
orxU32 sau32CRCTable[256
] =
{
  0x00000000
, 0x04C11DB7
, 0x09823B6E
, 0x0D4326D9
, 0x130476DC
, 0x17C56B6B
, 0x1A864DB2
, 0x1E475005
,
  0x2608EDB8
, 0x22C9F00F
, 0x2F8AD6D6
, 0x2B4BCB61
, 0x350C9B64
, 0x31CD86D3
, 0x3C8EA00A
, 0x384FBDBD
,
  0x4C11DB70
, 0x48D0C6C7
, 0x4593E01E
, 0x4152FDA9
, 0x5F15ADAC
, 0x5BD4B01B
, 0x569796C2
, 0x52568B75
,
  0x6A1936C8
, 0x6ED82B7F
, 0x639B0DA6
, 0x675A1011
, 0x791D4014
, 0x7DDC5DA3
, 0x709F7B7A
, 0x745E66CD
,
  0x9823B6E0
, 0x9CE2AB57
, 0x91A18D8E
, 0x95609039
, 0x8B27C03C
, 0x8FE6DD8B
, 0x82A5FB52
, 0x8664E6E5
,
  0xBE2B5B58
, 0xBAEA46EF
, 0xB7A96036
, 0xB3687D81
, 0xAD2F2D84
, 0xA9EE3033
, 0xA4AD16EA
, 0xA06C0B5D
,
  0xD4326D90
, 0xD0F37027
, 0xDDB056FE
, 0xD9714B49
, 0xC7361B4C
, 0xC3F706FB
, 0xCEB42022
, 0xCA753D95
,
  0xF23A8028
, 0xF6FB9D9F
, 0xFBB8BB46
, 0xFF79A6F1
, 0xE13EF6F4
, 0xE5FFEB43
, 0xE8BCCD9A
, 0xEC7DD02D
,
  0x34867077
, 0x30476DC0
, 0x3D044B19
, 0x39C556AE
, 0x278206AB
, 0x23431B1C
, 0x2E003DC5
, 0x2AC12072
,
  0x128E9DCF
, 0x164F8078
, 0x1B0CA6A1
, 0x1FCDBB16
, 0x018AEB13
, 0x054BF6A4
, 0x0808D07D
, 0x0CC9CDCA
,
  0x7897AB07
, 0x7C56B6B0
, 0x71159069
, 0x75D48DDE
, 0x6B93DDDB
, 0x6F52C06C
, 0x6211E6B5
, 0x66D0FB02
,
  0x5E9F46BF
, 0x5A5E5B08
, 0x571D7DD1
, 0x53DC6066
, 0x4D9B3063
, 0x495A2DD4
, 0x44190B0D
, 0x40D816BA
,
  0xACA5C697
, 0xA864DB20
, 0xA527FDF9
, 0xA1E6E04E
, 0xBFA1B04B
, 0xBB60ADFC
, 0xB6238B25
, 0xB2E29692
,
  0x8AAD2B2F
, 0x8E6C3698
, 0x832F1041
, 0x87EE0DF6
, 0x99A95DF3
, 0x9D684044
, 0x902B669D
, 0x94EA7B2A
,
  0xE0B41DE7
, 0xE4750050
, 0xE9362689
, 0xEDF73B3E
, 0xF3B06B3B
, 0xF771768C
, 0xFA325055
, 0xFEF34DE2
,
  0xC6BCF05F
, 0xC27DEDE8
, 0xCF3ECB31
, 0xCBFFD686
, 0xD5B88683
, 0xD1799B34
, 0xDC3ABDED
, 0xD8FBA05A
,
  0x690CE0EE
, 0x6DCDFD59
, 0x608EDB80
, 0x644FC637
, 0x7A089632
, 0x7EC98B85
, 0x738AAD5C
, 0x774BB0EB
,
  0x4F040D56
, 0x4BC510E1
, 0x46863638
, 0x42472B8F
, 0x5C007B8A
, 0x58C1663D
, 0x558240E4
, 0x51435D53
,
  0x251D3B9E
, 0x21DC2629
, 0x2C9F00F0
, 0x285E1D47
, 0x36194D42
, 0x32D850F5
, 0x3F9B762C
, 0x3B5A6B9B
,
  0x0315D626
, 0x07D4CB91
, 0x0A97ED48
, 0x0E56F0FF
, 0x1011A0FA
, 0x14D0BD4D
, 0x19939B94
, 0x1D528623
,
  0xF12F560E
, 0xF5EE4BB9
, 0xF8AD6D60
, 0xFC6C70D7
, 0xE22B20D2
, 0xE6EA3D65
, 0xEBA91BBC
, 0xEF68060B
,
  0xD727BBB6
, 0xD3E6A601
, 0xDEA580D8
, 0xDA649D6F
, 0xC423CD6A
, 0xC0E2D0DD
, 0xCDA1F604
, 0xC960EBB3
,
  0xBD3E8D7E
, 0xB9FF90C9
, 0xB4BCB610
, 0xB07DABA7
, 0xAE3AFBA2
, 0xAAFBE615
, 0xA7B8C0CC
, 0xA379DD7B
,
  0x9B3660C6
, 0x9FF77D71
, 0x92B45BA8
, 0x9675461F
, 0x8832161A
, 0x8CF30BAD
, 0x81B02D74
, 0x857130C3
,
  0x5D8A9099
, 0x594B8D2E
, 0x5408ABF7
, 0x50C9B640
, 0x4E8EE645
, 0x4A4FFBF2
, 0x470CDD2B
, 0x43CDC09C
,
  0x7B827D21
, 0x7F436096
, 0x7200464F
, 0x76C15BF8
, 0x68860BFD
, 0x6C47164A
, 0x61043093
, 0x65C52D24
,
  0x119B4BE9
, 0x155A565E
, 0x18197087
, 0x1CD86D30
, 0x029F3D35
, 0x065E2082
, 0x0B1D065B
, 0x0FDC1BEC
,
  0x3793A651
, 0x3352BBE6
, 0x3E119D3F
, 0x3AD08088
, 0x2497D08D
, 0x2056CD3A
, 0x2D15EBE3
, 0x29D4F654
,
  0xC5A92679
, 0xC1683BCE
, 0xCC2B1D17
, 0xC8EA00A0
, 0xD6AD50A5
, 0xD26C4D12
, 0xDF2F6BCB
, 0xDBEE767C
,
  0xE3A1CBC1
, 0xE760D676
, 0xEA23F0AF
, 0xEEE2ED18
, 0xF0A5BD1D
, 0xF464A0AA
, 0xF9278673
, 0xFDE69BC4
,
  0x89B8FD09
, 0x8D79E0BE
, 0x803AC667
, 0x84FBDBD0
, 0x9ABC8BD5
, 0x9E7D9662
, 0x933EB0BB
, 0x97FFAD0C
,
  0xAFB010B1
, 0xAB710D06
, 0xA6322BDF
, 0xA2F33668
, 0xBCB4666D
, 0xB8757BDA
, 0xB5365D03
, 0xB1F740B4

};

orxU32 orxString_ContinueCRC(const
orxSTRING _zString, orxU32 _u32CRC)
{
  register
orxU32          u32CRC;
  register
const
orxCHAR *pc;

/*
Checks
*/

orxASSERT(_zString != orxNULL);

/*
Inits CRC
*/

u32CRC = _u32CRC ^ 0xFFFFFFFFL
;

  /*
For the whole string
*/

  for
(pc = _zString; *pc != orxCHAR_NULL; pc++)
  {
    /*
Computes the CRC
*/

    u32CRC = sau32CRCTable[(u32CRC ^ *pc) & 0xFF
] ^ (u32CRC >> 8
);
  }

/*
Done!
*/

return
(u32CRC ^ 0xFFFFFFFFL
);
}

由于在Orx中使用的时候，第2参数一直为0，所以函数实际可以改成下面这样

orxU32 orxString_ContinueCRC(const
orxSTRING _zString)
{
  register
orxU32          u32CRC;
  register
const
orxCHAR *pc;

/*
Checks
*/

orxASSERT(_zString != orxNULL);

/*
Inits CRC
*/

u32CRC = 0
^ 0xFFFFFFFFL
;

  /*
For the whole string
*/

  for
(pc = _zString; *pc != orxCHAR_NULL; pc++)
  {
    /*
Computes the CRC
*/

    u32CRC = sau32CRCTable[(u32CRC ^ *pc) & 0xFF
] ^ (u32CRC >> 8
);
  }

/*
Done!
*/

return
(u32CRC ^ 0xFFFFFFFFL
);
}

作为测试结果，我希望检验是否会在string较短时就发生冲突，并且，真的冲突的话，输出冲突的字符串。这里暂时仅测试ASCII的字符，按照Orx的实际使用，UTF8字符的冲突的可能性只会比这个高，不会比这个低。

突然觉得想出一个这样的测试算法也挺有意思的。

作为较短的函数，暂时将字符串长度定在20以下。

第一步：生成测试字符串：

这里为了简化，就全生成同样长度的小写字符串了，其实本来想遍历生成的，后来觉得太麻烦，想了想，其实没有必要，只要能找到冲突就行，不一定要遍历。

char
*rand_str(char
*str,const
int
len)
{
  char
*c = str;
  for
(int
i=0
; i
    *c='a'
+rand()%26
;
  }

*c='0'
;
return
str;
}

用这个函数来生成随机指定长度的字符串。

我然后用下列函数来检验：

typedef
hash_map<unsigned
long
, list > resultType;
resultType result;
void
testIt(char
* testString) {
unsigned
long
crcValue = orxString_ContinueCRC(testString);

  resultType::iterator clashIt = result.find(crcValue);
  if
(clashIt != result.end()) {
    // have a clash

    list &clashList = (clashIt->second);
    clashList.push_back(testString);

    printf("Clash strings: "
);
    for
(list::iterator it = clashList.begin();
      it != clashList.end();
      ++it) {
        printf("
%s
t
"
, it->c_str());
    }
    printf("
n
"
);
    return
;
  }

  list newVaule;
  newVaule.push_back(testString);
  result.insert(make_pair(crcValue, newVaule));
}

原理上也没有什么好说的了，就是一个hash_map<unsigned
long
, list >
的变量，用于来保存目前测试过的所有字符串，key是CRC计算后的值，list用于存储字符串。这种用法消耗内存非常多。。。。。。。

驱动代码如下，需要增加测试数量的，改NumOftest是改测试字符串的长度，i的最大值是测试的次数。

int
_tmain(int
argc, _TCHAR* argv[])
{
  srand(time(NULL
));
  const
int
NumOftest = 11
;
  char
test[NumOftest + 1
];
  for
(int
i = 0
; i < 200000
; ++i) {
    rand_str(test, NumOftest);
    testIt(test);
  }

system("PAUSE"
);

return
0
;
}

事实上，经过测试，在上面这个级别我就测试出了4组冲突：

Clash strings: rdvohjmmqco      dzfmlbvurvy
Clash strings: ezmchjdxzvc      heugmqpnwhr
Clash strings: xuosifsuqnz      hdnklsfofvo
Clash strings: cxezqfgwkdy      hjccdfyaamc

20W的级别，长度为十的字符串。。。。。。。。。。。。这不是现实中可能出现的组合，出现这样的情况，Orx中的hashTable必然就会出现问题。。。。。

另外，这也说明了出现问题的概率不是小到宇宙毁灭的几率那样，谁也不能保证在Orx使用一个256长度的hashTable的时候会不会出现问题。。。。。。。。。。。。。。。。事实上，即使为了效率，也还是参考参考MPQ中暴雪对CRC的使用，或者是如一般std扩展中hashmap的使用吧。

原创文章作者保留版权转载请注明原作者并给出链接

2010年08月04日

非典型2D游戏引擎 Orx 源码阅读笔记(4) 用C实现的基本容器（List,HashTable,Tree）

C语言中没有标准的容器，所以为了跨平台，Orx中自己实现了一套。

在Orx中作者分别实现了HashTable,List,Tree3个容器，虽然没有实现一个自己的String，但是为orxSTRING（实际为char*的typedef)实现了一堆的辅助函数。

下面分别来看看，为了不使本文成为一个类似algorithm in C的讲算法的文章，这里只看看使用和各容器的特性^^

List

以前有人说过，几乎每个程序员在职业生涯都会自己实现一个List,不知道是不是真这样，虽然我的确实现过。。。。。。。。。。
先看结构：

/*
* Node list structure

*/

typedef
struct
__orxLINKLIST_NODE_t
{
  struct
__orxLINKLIST_NODE_t *pstNext;         /*
*< Next node pointer : 4
*/

  struct
__orxLINKLIST_NODE_t *pstPrevious;     /*
*< Previous node pointer : 8
*/

  struct
__orxLINKLIST_t      *pstList;         /*
*< Associated list pointer : 12
*/

} orxLINKLIST_NODE;

/*
* List structure

*/

typedef
struct
__orxLINKLIST_t
{
  orxLINKLIST_NODE *pstFirst;                   /*
*< First node pointer : 4
*/

  orxLINKLIST_NODE *pstLast;                    /*
*< Last node pointer : 8
*/

  orxU32            u32Counter;                 /*
*< Node counter : 12
*/

} orxLINKLIST;

从结构看，我感觉实现的有些特殊，我以前看到的一般的list实现（自然是指C语言中的）一般用一个结构就解决一切了，都是用list的node本身（一般是头结点）来表示一个list,Orx这里额外特别的抽象出了一个List结构，然后node还反过来有指针指向list，有点奇怪的是，没有看到数据存在哪里。。。。。。。。。。。然后，突然发现，我没有看到list的Create函数。。。。。。。。看了一下Orx对List的使用，原来都是直接使用orxLINKLIST
。。。。。。。。。。。。
再然后，没有地方存储数据（比如类似pData的指针）的疑惑也解开了。。。。。。所有使用这个list的地方都用一个以orxLINKLIST_NODE
为第一个成员变量的结构，然后node的指针，就相当于整个结构的指针了。。。。。。。。。。。。。
比如下面这个config的结构：
typedef struct __orxCONFIG_SECTION_t
{
orxLINKLIST_NODE stNode;                 /**< List node : 12 */
orxBANK          *pstEntryBank;           /**< Entry bank : 16 */
orxSTRING         zName;                  /**< Section name : 20 */
orxU32            u32ID;                  /**< Section ID (CRC) : 24 */
orxU32            u32ParentID;            /**< Parent ID (CRC) : 28 */
orxS32            s32ProtectionCounter;   /**< Protection counter : 32 */
orxLINKLIST       stEntryList;            /**< Entry list : 44 */

orxPAD(44)

} orxCONFIG_SECTION;

谜底解开了，总的来说，这个List很诡异。。。。。。。。。。。。

HashTable

一个HashTable容器拥有O(1)的查找效率，被誉为20世纪最重要的编程领域发明之一。。。。。（不记得在哪看到的了）
先看看结构：
#define orxHASHTABLE_KU32_INDEX_SIZE                          256
/*
* Hash table cell definition.
*/

typedef
struct
__orxHASHTABLE_CELL_t
{
  orxU32                        u32Key;                       /*
*< Key element of a hash table : 4
*/

  void
                         *pData;                        /*
*< Address of data : 8
*/

  struct
__orxHASHTABLE_CELL_t *pstNext;                      /*
*< Next cell with the same index : 12
*/

orxPAD(12
)
} orxHASHTABLE_CELL;

/*
* Hash Table
*/

struct
__orxHASHTABLE_t
{
  orxHASHTABLE_CELL *apstCell[orxHASHTABLE_KU32_INDEX_SIZE]; /*
*< Hash table
*/

  orxBANK            *pstBank;                                /*
*< Bank where are stored cells
*/

  orxU32              u32Counter;                             /*
*< Hashtable item counter
*/

};

每个hashTable的数据自然是一个cell,存储在pData中，通过注释基本也能理解Orx的Hash table的结构了。
所有的数据通过apstCell[orxHASHTABLE_KU32_INDEX_SIZE];
数组来存储，并且通过某个较小的key（说明这个较小的key一定小于orxHASHTABLE_KU32_INDEX_SIZE
）来索引这个数据，假如有第一个较小的key冲突的情况，通过orxHASHTABLE_CELL
的*pstNext
变量来保存成链状，并通过u32Key
这个32位的key来区别。这个结构与一般C++ STL扩展中的hashTable实现原理基本一样。（HashTable目前还不是C++标准库的内容，所以只在扩展库中存在）
谁说看结构比看流程清晰来着？说的实在是太对了。当结构是这样定的时候，流程还能玩出啥花来？

用下面这样的代码来测试一下，同时验证想法。
orxHASHTABLE* hashTable = orxHashTable_Create(32
, orxHASHTABLE_KU32_FLAG_NONE, orxMEMORY_TYPE_MAIN);

  char
* firstKey = "FirstKey"
;
  char
* secondKey = "secondKey"
;
  char
* thirdKey = "thirdKey"
;
  orxHashTable_Add(hashTable, orxString_ToCRC(firstKey), firstKey);
  orxHashTable_Add(hashTable, orxString_ToCRC(secondKey), secondKey);
  orxHashTable_Set(hashTable, orxString_ToCRC(firstKey), secondKey);
  orxHashTable_Set(hashTable, orxString_ToCRC(thirdKey), thirdKey);
  char
* value = (char
*)orxHashTable_Get(hashTable, orxString_ToCRC(firstKey));
  orxHashTable_Delete(hashTable);

  printf("Value:
%s
"
, value);

解释：
orxHashTable_Create实际仅仅分配了内存而已。值得一提的仅仅是cell的内存使用上一节
提到的bank来分配的。
orxString_ToCRC用于将string进行CRC，没有啥好说的。只是不知道Orx的这个CRC效果怎么样，比如速度快不快，冲突几率高不高。
orxHashTable_Add中先判断是否有同样key的数据存在，存在的话会报错。
其中调用的下列函数非常关键，用于获取前面提到的较小的key，来合成数组的索引。原来就是取CRC出来的32位值的与orxHASHTABLE_KU32_INDEX_SIZE
匹配的低位而已。（虽然这里用取模会意思更加自然一些，但是一个取模操作比一个位操作慢的不是一点点）
static
orxINLINE orxU32 orxHashTable_FindIndex(const
orxHASHTABLE *_pstHashTable, orxU32 _u32Key)
{
  /*
Checks
*/

  orxASSERT(_pstHashTable != orxNULL);

/*
Computes the hash index
*/

return
(_u32Key & (orxHASHTABLE_KU32_INDEX_SIZE - 1
));
}

找到位置以后的操作就太自然了。

/*
Get the hash table index
*/

u32Index = orxHashTable_FindIndex(_pstHashTable, _u32Key);

/*
Allocate a new cell if possible
*/

pstCell = (orxHASHTABLE_CELL *)orxBank_Allocate(_pstHashTable->pstBank);

    /*
If allocation succeed, insert the new cell
*/

    if
(pstCell != orxNULL)
    {
      /*
Set datas
*/

      pstCell->u32Key = _u32Key;
      pstCell->pData = _pData;
      pstCell->pstNext = _pstHashTable->apstCell[u32Index];

      /*
Insert it
*/

      _pstHashTable->apstCell[u32Index] = pstCell;
      eStatus = orxSTATUS_SUCCESS;

      /*
Updates counter
*/

      _pstHashTable->u32Counter++;
    }

由于iarwain的注释存在，我更加没有必要说太多了。值得一提的是可以看到这里面甚至没有判断这个数组索引所在的位置是否已经被占，然后进行冲突处理的操作。
原因在于先
pstCell->pstNext = _pstHashTable->apstCell[u32Index];

然后
_pstHashTable->apstCell[u32Index] = pstCell;

假如原来此位置为空，next也就是空了，假如原来此位置有原来的值（甚至可以是一个链），就将整个链接在现在新数据的后面。

然后看set函数：

  /*
Traverse to find the key
*/

  pstCell = _pstHashTable->apstCell[u32Index];
  while
(pstCell != orxNULL && pstCell->u32Key != _u32Key)
  {
    /*
Try with next cell
*/

    pstCell = pstCell->pstNext;
  }

  /*
Cell found ?
*/

  if
(pstCell != orxNULL)
  {
    /*
Set associated datas
*/

    pstCell->pData = _pData;
  }
  else

  {
    /*
Allocate a new cell if possible
*/

    pstCell = (orxHASHTABLE_CELL *)orxBank_Allocate(_pstHashTable->pstBank);

      /*
Insert it
*/

      _pstHashTable->apstCell[u32Index] = pstCell;
    }
  }

  /*
Done!
*/

  return
orxSTATUS_SUCCESS;

用于在此数组位置进行进一步的索引，找到32位key完全一致的值。
while
(pstCell != orxNULL && pstCell->u32Key != _u32Key)
  {
    /*
Try with next cell
*/

    pstCell = pstCell->pstNext;
  }

而
/*
Cell found ?
*/

  if
(pstCell != orxNULL)
  {
    /*
Set associated datas
*/

    pstCell->pData = _pData;
  }
  else

  {

.....
}

则完美回答了我博客中以前评论中的踢出来的问题，当hashTable 进行Set的时候，假如原来这个Key不存在会进行什么操作，很明显，不存在就Add。

到了这里，Get,Delete函数我感觉已经没有太多讲的必要了，只要对hashTable的概念还算熟悉的，对Orx的hashtable应该有足够的了解了，无论是实现的原理还是效率。

我小结一下：

1、Orx的HashTable定死了apstCell[orxHASHTABLE_KU32_INDEX_SIZE]这个数组的大小，orxHASHTABLE_KU32_INDEX_SIZE
等于256，所以，很自然的，此hashTable
在数量较小的时候才能保持较高的效率，（即HashTable的理论值O(1))假如数量远远超过256，那么查询效率几乎接近线性效率O(n)。

2、Orx这里的索引完全依赖于其String的32位CRC计算，但是很遗憾的，CRC的计算时会有冲突的，也就是会出现两个不同String但是计算出同样CRC的情况，我没有仔细了解这个CRC的计算，但是将整个HashTable的基础建立在这个不稳定的基石上，总的来说已经说明了这个HashTable存在问题。。。。。。。。。。。。。

Orx的HashTableKey是建立在String上的，为了提高String的比较效率，所以对String进行了CRC，效率是高了，但是引发了第2点说的问题。

但是这里其实不是没有解决方案的。

1。高效的方案：如暴雪的MPQ那样，不以一个CRC来决定一切，额外用2个来做保险，也就是进行3次不同的CRC运算，同时比较3个CRC都一样时才能确定一个真正的数据位置。此方法比Orx的方法多2次CRC计算，并且多2次整数比较，但是出错几率会比Orx的低的多。（在实际中，就算到几十万这个等级，我也没有碰到过3个CRC同时冲突）

2。而作为对比，C++中实现的hashTable（可以参考VS或者boost的hashMap实现），由于模板的存在，可以使用任何东西作为key，同时，在第一次快速索引时，使用一个hash值，当hash值冲突后，完全使用原来的key来进行比较，虽然假如是字符串的话会稍微慢一点，但是起码能保证绝对无错。

Tree

还是先看结构：

/*
* Tree node structure

*/

typedef
struct
__orxTREE_NODE_t
{
  struct
__orxTREE_NODE_t *pstParent;           /*
*< Parent node pointer : 4
*/

  struct
__orxTREE_NODE_t *pstChild;            /*
*< First child node pointer : 8
*/

  struct
__orxTREE_NODE_t *pstSibling;          /*
*< Next sibling node pointer : 12
*/

  struct
__orxTREE_t      *pstTree;             /*
*< Associated tree pointer : 16
*/

} orxTREE_NODE;

/*
* Tree structure

*/

typedef
struct
__orxTREE_t
{
orxTREE_NODE *pstRoot; /*
*< Root node pointer : 4
*/

orxU32 u32Counter; /*
*< Node counter : 8
*/

} orxTREE;

看到结构的时候，从list的诡异中我诡异的理解了这个Tree的意思，也就是，这个tree的用法也和list类似了。。。。。。。。。。。。

我虽然以前学习数据结构的时候是以伪码和C++的实现为主，没有看过太多C语言实现的数据结构，但还真不是完全没有见过，我感觉Orx的实现是很诡异的。。。。。。使用方式也是在算不上正统，为了求证，以防止是因为自己的孤陋寡闻引起的笑话，特意求证glib实现。。。。。。

比如GList

typedef
struct
_GList GList;

struct
_GList
{
  gpointer data;
  GList *next;
  GList *prev;
};

一看到结构。。。。。。。。。。。。我大呼。。。。。数据结构的书籍还是没有骗我的啊。。。。。。。。。。。。。。。。。诡异的还是Orx。。。。。。。。。哪有需要自己一定要用一个新结构来包含Node来用一个list/tree的话。。。。。我要保存一个整数怎么办？。。。。。。。。简单的说，Orx的这个容器实现的非主流，不推荐大家使用及学习。。。。我这里也仅仅为了了解Orx的源代码而看看吧。。。。。。。。

原创文章作者保留版权转载请注明原作者并给出链接

2010年08月03日

Cocos2D For IPhone中的慢动作

慢动作是游戏中常用的特效手法，感觉Cocos2D这样完善的引擎应该原生支持才对，我在网上搜索了一下，竟然没有搜到，（不知道英文是不是该搜索Slow Action，但是原来公司的项目都这样叫的）。
于是自己实现了一下，在自己项目的最底层的update中，添加一个slowAction的scale值，设定每次将update的参数ts传进来后，立刻乘以此scale值。只要原来的代码都是时间相关的，可以看到慢动作效果了。刚开始都还好，但是Cocos2D的粒子效果不吃这套，由于粒子系统不受我控制，我没法强行改变其值。本来还想通过全局变量强行改cocos2D的源代码的，在粒子系统的step函数中下了断点，然后通过callback stack中看到了sharedDirector调用了sharedScheduler的tick来实现cocos2d内部的update，并且很惊奇的发现了CCScheduler的timeScale变量。

于是，本文真正的非废话就下面一句：
[[CCScheduler sharedScheduler] setTimeScale:倍率];

同时，这也得原来的代码都是时间相关才能实现的，假如都是按帧走的，那么就哭去吧。。。。。。。。。。。。。所以说，很久很久以前，大家就开始认为时间相关的代码优于帧相关的代码不是没有道理的。。。。。。。。。。

原创文章作者保留版权转载请注明原作者并给出链接

2010年08月01日

非典型2D游戏引擎 Orx 源码阅读笔记(3) 内存管理

内存管理在任何希望达到高效的游戏引擎中都是基础，我以前恰好做过类似的工作，所以这里先看看Orx的实现，再谈谈自己以往做类似工作时的经验。

Memory模块

个人感觉这是非常没有必要成为一个模块的模块。因为实质上没有任何必要的全局变量需要初始化，退出的时候也没有任何需要的扫尾工作，仅仅是几个函数而已，为啥Orx中这些函数会集中在一起作为一个Orx的模块，除了出于逻辑上一致的考虑，我感觉纯粹属于过度设计。。。。。。。。起码从目前来看是这样。

extern
orxDLLAPI void
*orxFASTCALL      orxMemory_Allocate(orxU32 _u32Size, orxMEMORY_TYPE _eMemType);
extern
orxDLLAPI void
orxFASTCALL       orxMemory_Free(void
*_pMem);
extern
orxDLLAPI void
*orxFASTCALL      orxMemory_Copy(void
*_pDest, const
void
*_pSrc, orxU32 _u32Size);
extern
orxDLLAPI void
*orxFASTCALL      orxMemory_Move(void
*_pDest, void
*_pSrc, orxU32 _u32Size);
extern
orxDLLAPI orxU32 orxFASTCALL     orxMemory_Compare(const
void
*_pMem1, const
void
*_pMem2, orxU32 _u32Size);
extern
orxDLLAPI void
*orxFASTCALL      orxMemory_Set(void
*_pDest, orxU8 _u8Data, orxU32 _u32Size);
extern
orxDLLAPI void
*orxFASTCALL      orxMemory_Zero(void
*_pDest, orxU32 _u32Size);
extern
orxDLLAPI void
*orxFASTCALL      orxMemory_Reallocate(void
*_pMem, orxU32 _u32Size);

除了allocate多了一个type，其余全部的有用接口其实都是C语言中对应接口的直接包装，都只需要一条C语句就能完成。

从内存的type上：
typedef enum __orxMEMORY_TYPE_t
{
orxMEMORY_TYPE_MAIN = 0, /**< Main memory type */

orxMEMORY_TYPE_VIDEO,                 /**< Video memory type */
orxMEMORY_TYPE_SPRITE,                /**< Sprite memory type */
orxMEMORY_TYPE_BACKGROUND,            /**< Background memory type */
orxMEMORY_TYPE_PALETTE,               /**< Palette memory type */

orxMEMORY_TYPE_CONFIG, /**< Config memory */
orxMEMORY_TYPE_TEXT, /**< Text memory */

orxMEMORY_TYPE_TEMP, /**< Temporary / scratch memory */

orxMEMORY_TYPE_NUMBER, /**< Number of memory type */

orxMEMORY_TYPE_NONE = orxENUM_NONE /**< Invalid memory type */

} orxMEMORY_TYPE;
可以看到作者的一些想法，但是事实上，物理上都没有区分的内存，（除了显存）无论怎么按类型分都是没有实际价值的。事实上，现在Orx也没有关心这个type。

void
*orxFASTCALL orxMemory_Allocate(orxU32 _u32Size, orxMEMORY_TYPE _eMemType)
{
/*
Module initialized ?
*/

orxASSERT((sstMemory.u32Flags & orxMEMORY_KU32_STATIC_FLAG_READY) == orxMEMORY_KU32_STATIC_FLAG_READY);

/*
Valid parameters ?
*/

orxASSERT(_eMemType < orxMEMORY_TYPE_NUMBER);

/*
Returns system allocation function
*/

return
((void
*)malloc(_u32Size));
}

对C语言中标准的函数进行无意义的封装个人感觉除了影响效率，没有任何好处，这些C标准的东西本身也是跨平台的，封装它们干什么？从优化效率上考虑，稍微有些必要封装的也就是malloc和free两个而已。（realloc用的实在不多）除非Orx的作者看的更远，希望将来对包括内存Copy
,compare在内的内存操作函数都进行自己针对特定CPU/平台的汇编级优化。

bank模块

这是Orx用于优化性能实现的内存缓存的模块。
主要结构如下：

/*
**************************************************************************

* Structure declaration                                                   *

**************************************************************************
*/

typedef
struct
__orxBANK_SEGMENT_t
{
  orxU32                     *pu32CellAllocationMap; /*
*< List of bits that represents free and used elements in the segment
*/

  void
                       *pSegmentData;     /*
*< Pointer address on the head of the segment data cells
*/

  struct
__orxBANK_SEGMENT_t *pstNext;          /*
*< Pointer on the next segment
*/

  orxU16                      u16NbFree;        /*
*< Number of free elements in the segment
*/

} orxBANK_SEGMENT;

struct
__orxBANK_t
{
  orxBANK_SEGMENT *pstFirstSegment;        /*
*< First segment used in the bank
*/

  orxU32            u32Flags;               /*
*< Flags set for the memory bank
*/

  orxMEMORY_TYPE    eMemType;               /*
*< Memory type that will be used by the memory allocation
*/

  orxU32            u32ElemSize;            /*
*< Size of a cell
*/

  orxU16            u16NbCellPerSegments;   /*
*< Number of cells per banks
*/

  orxU16            u16SizeSegmentBitField; /*
*< Number of u32 (4 bytes) to represent a segment
*/

  orxU32            u32Counter;             /*
*< Number of allocated cells
*/

};

typedef
struct
__orxBANK_STATIC_t
{
orxU32 u32Flags; /*
*< Flags set by the memory module
*/

} orxBANK_STATIC;

/*
**************************************************************************

* Module global variable *

**************************************************************************
*/

static
orxBANK_STATIC sstBank;

从结构上看，bank应该以__orxBANK_t
结构为主要结构，代表一个bank,每个bank中还可以包含一个orxBANK_SEGMENT
类型的列表。实际内存缓存在orxBANK_SEGMENT
类型对象的pSegmentData成员变量中。

主要对外接口有4个：

/*
* Creates a new bank in memory and returns a pointer on it

* @param[in] _u16NbElem Number of elements per segments

* @param[in] _u32Size    Size of an element

* @param[in] _u32Flags   Flags set for this bank

* @param[in] _eMemType   Memory type where the datas will be allocated

* @return returns a pointer on the memory bank

*/

extern
orxDLLAPI orxBANK *orxFASTCALL       orxBank_Create(orxU16 _u16NbElem, orxU32 _u32Size, orxU32 _u32Flags, orxMEMORY_TYPE _eMemType);

/*
* Frees a portion of memory allocated with orxMemory_Allocate

* @param[in] _pstBank Pointer on the memory bank allocated by orx

*/

extern
orxDLLAPI void
orxFASTCALL orxBank_Delete(orxBANK *_pstBank);

/*
* Allocates a new cell from the bank

* @param[in] _pstBank Pointer on the memory bank to use

* @return a new cell of memory (orxNULL if no allocation possible)

*/

extern
orxDLLAPI void
*orxFASTCALL orxBank_Allocate(orxBANK *_pstBank);

/*
* Frees an allocated cell

* @param[in] _pstBank    Bank of memory from where _pCell has been allocated

* @param[in] _pCell      Pointer on the cell to free

* @return a new cell of memory (orxNULL if no allocation possible)

*/

extern
orxDLLAPI void
orxFASTCALL           orxBank_Free(orxBANK *_pstBank, void
*_pCell);

从流程上来看看：
先建立一个测试工程，在原来的Orx独立应用程序上改改，有下面的代码已经几乎可以做到走遍bank全部主要部分代码：

struct
myStruct {
  int
i;
};
orxSTATUS GameApp::Init() {
  orxBANK *bank = orxBank_Create(2
, sizeof
(myStruct), orxBANK_KU32_FLAG_NONE, orxMEMORY_TYPE_MAIN);
  myStruct *p1 = (myStruct *)orxBank_Allocate(bank);
  myStruct *p2 = (myStruct *)orxBank_Allocate(bank);
  myStruct *p3 = (myStruct *)orxBank_Allocate(bank);
  orxBank_Free(bank, p1);
  orxBank_Free(bank, p2);
  orxBank_Free(bank, p3);
  orxBank_Delete(bank);

    return
orxSTATUS_SUCCESS;
}
orxBank_Create与orxBank_Delete是一对，用于创建删除一个bank对象。
然后可以通过orxBank_Allocate
，orxBank_Free
来获取或者释放内存。使用还算是简单，对于完全不想自己写内存管理模块的，即使是自己的项目也可以使用这个内存管理的部分，因为这是Orx中最最底层的代码，没有依赖太多其他的东西，剥离出来也不是很难。

因为内存这一部分可以说是小技巧众多并且非常dirty的部分了，几乎都是一个一个字节相关的内容，我就是从编写内存管理模块和文件系统开始习惯看成篇的2进制内存/文件数据的。所以这里我也没有兴趣一句一句的去了解Orx的做法了，大概的了解一下。

操作流程部分：在用orxBank_Create
创建bank的时候，就会使用orxBank_SegmentCreate创建一个指定数量缓存的Segment，每个cell的大小当然就是第2个参数指定的。事实上，每一个Segment都是一个列表，保存着orxBank_Create
第一参数指定数量的cell。在默认情况下，当一个Segment中的缓存都分配完了的时候，会自动分配新的Segment，新的Segment中的cell数量还是一样多，并且通过前一个Segment的pstNext
成员变量串起来。

内存实际分配结构：
每次分配Segment的时候实际分配的大小为：
/* Compute the segment size */
u32SegmentSize = sizeof(orxBANK_SEGMENT) +                                /* Size of the structure */
                   _pstBank->u16SizeSegmentBitField * sizeof(orxU32) +      /* Size of bitfields */
                   _pstBank->u16NbCellPerSegments * _pstBank->u32ElemSize; /* Size of stored Data */

总体的使用：

  /*
Allocate a new segent of memory
*/

  pstSegment = (orxBANK_SEGMENT *)orxMemory_Allocate(u32SegmentSize, _pstBank->eMemType);
  if
(pstSegment != orxNULL)
  {
    /*
Set initial segment values
*/

    orxMemory_Zero(pstSegment, u32SegmentSize);
    pstSegment->pstNext               = orxNULL;
    pstSegment->u16NbFree             = _pstBank->u16NbCellPerSegments;
    pstSegment->pu32CellAllocationMap = (orxU32 *)(((orxU8 *)pstSegment) + sizeof
(orxBANK_SEGMENT));
    pstSegment->pSegmentData          = (void
*)(((orxU8 *)pstSegment->pu32CellAllocationMap) + (_pstBank->u16SizeSegmentBitField * sizeof
(orxU32)));
  }

相当于将Segment自己的内存与其需要对外分配的内存一起分配，每次分配内存前面sizeof(orxBANK_SEGMENT)字节数的内存实际就做一个Segment结构对象使用，后面的_pstBank->u16SizeSegmentBitField * sizeof(orxU32)字节数内存作为一个标志数组使用，用于标志对应的某段内存是否已经分配，再后面的，才是实际会返回给用户使用的内存。

小结

Orx的内存管理模块对于习惯使用缓存并且非常需要使用缓存的地方还算是比较合适的，并且也还算容易使用。类似的技术也已经非常普遍了。
但是，个人感觉，类似的方式仅适用于的确已经常年习惯使用这种方式的人了，将这样添加缓存的功能完全的压到每个程序员头上，我感觉并不是很合适，最好的办法应该是在最底层透明的实现相关的功能，而不是这样将性能方面的要求强加给每个人。其次，对于已有项目，使用类似的技术需要对每个使用缓存的部分新加特别的代码，并不是很方便。还有，将缓存的代码遍布于项目中的每个角落，实在也不便于修改。在Orx中，memory,bank模块几乎被任何一个其他模块所依赖，很难想象需要改动的时候怎么办。

其实做的更加人性，更加好一点的办法也不难，说的简单点，在C语言下就是直接替换malloc,free的实现，在C++中就是重载new,delete操作符，直接通过内存的size来进行用户级别的缓存，而完全不考虑每次分配内存的用途(比如Orx中的内存type)，实际的内存分配模块也的确不应该考虑和关心用户到底最后用此内存来做什么，给用户需要长度的内存就好了，那样做是加大了两方面的耦合。
基于size的缓存可以做的很简单，也可以很复杂，一般来说，对很小size的内存单独成链，为了限制链表的数量，可以取2次幂的方式。比如保存4,8,16,32,64等size的链表，每次分配这些大小的内存直接从链表中取，假如分配的大小在两个大小之间，则直接取一个更大的内存返回即可。比如用户分配9字节的内存，返回16给它，虽然造成了一定的内存浪费，但是考虑到效率和实现的问题，这并不是不可以接受。另外，对于C++来说，还可以重载标准库容器的分配器，上述方法和重载容器的分配器的方法可以参考一下SGI的STL实现。（在侯捷《STL源码剖析》中有详细描述）
其实，内存管理在C/C++中不仅仅出于效率方面的考虑，在大型项目中对于内存泄露的检测（特别是隐式的）这也是很重要的。
最后，其实，就我看到的资料都说明，现在C语言实现的自动垃圾回收效率已经非常高了，甚至已经比一般人写的手工内存管理效率还要高，如此说来，一个自动或半自动的垃圾回收机制也是个不错的选择。
总之，虽然我以前写服务器代码（常常需要以空间换时间）时写过很多类似Orx这种手工管理缓存的代码，但是，我感觉还是有很多更好的替代方案的。

原创文章作者保留版权转载请注明原作者并给出链接

2010年08月01日

非典型2D游戏引擎 Orx 源码阅读笔记(2) 基础模块与模块管理模块

上一节中对Orx的整体框架及结构进行了梳理，本节开始阅读Orx底层的各个模块。本节的主要内容是基础模块和用于管理模块的部分代码。

基础部分

orxDecl.h,orxType.h/orxType.c:

对于每个跨平台的库总会有些杂事需要处理，比如统一每个长度的变量命名，为各平台的换行符，路径分隔符进行统一命名，大小头等。这两个文件就是做类似的事情。列举一些特别典型的：

变量：

/*
Windows
*/

#ifdef __orxWINDOWS__

typedef
void
* orxHANDLE;

  typedef
unsigned
  long
          orxU32;

  typedef
unsigned
  short
         orxU16;

  typedef
unsigned
  char
          orxU8;

  typedef
signed
    long
          orxS32;

  typedef
signed
    short
         orxS16;

  typedef
signed
    char
          orxS8;

  typedef
unsigned
  long
          orxBOOL;

typedef
float
orxFLOAT;

typedef
double
orxDOUBLE;

  typedef
char
                    orxCHAR;
  #define orxSTRING               orxCHAR *

typedef
orxU32 orxENUM;

#define orx2F(V) ((orxFLOAT)(V))

#define orxENUM_NONE
0xFFFFFFFFL

/*
Compiler specific
*/

#ifdef __orxGCC__

    typedef
unsigned
  long
long
   orxU64;

    typedef
signed
    long
long
   orxS64;

#endif
/*
__orxGCC__
*/

#ifdef __orxMSVC__

typedef
unsigned
__int64 orxU64;

typedef
signed
__int64 orxS64;

#endif
/*
__orxMSVC__
*/

#else
/*
__orxWINDOWS__
*/

/*
Linux / Mac
*/

#if defined(__orxLINUX__) || defined(__orxMAC__) || defined(__orxGP2X__) || defined(__orxWII__) || defined(__orxIPHONE__)

typedef
void
* orxHANDLE;

    typedef
unsigned
  long
long
   orxU64;

    typedef
unsigned
  long
        orxU32;

    typedef
unsigned
  short
       orxU16;

    typedef
unsigned
  char
        orxU8;

    typedef
signed
    long
long
   orxS64;

    typedef
signed
    long
        orxS32;

    typedef
signed
    short
       orxS16;

    typedef
signed
    char
        orxS8;

    typedef
unsigned
  long
        orxBOOL;

typedef
float
orxFLOAT;

typedef
double
orxDOUBLE;

    typedef
char
                  orxCHAR;
    #define orxSTRING             orxCHAR *

typedef
orxU32 orxENUM;

#define orx2F(V) ((orxFLOAT)(V))

#define orxENUM_NONE
0xFFFFFFFFL

#endif
/*
__orxLINUX__ || __orxMAC__ || __orxGP2X__ || __orxWII__ || __orxIPHONE__
*/

#endif
/*
__orxWINDOWS__
*/

换行符：
#define orxCHAR_CR
'/r'

#define orxCHAR_LF
'/n'

#ifdef __orxWINDOWS__

const
orxCHAR orxCHAR_EOL = '/n'
;

const
orxSTRING orxSTRING_EOL = "
/r/n
"
;

#elif defined(__orxLINUX__) || defined(__orxGP2X__) || defined(__orxWII__) || defined(__orxIPHONE__)

const
orxCHAR orxCHAR_EOL = '/n'
;

const
orxSTRING orxSTRING_EOL = "
/n
"
;

#elif defined(__orxMAC__)

const
orxCHAR orxCHAR_EOL = '/r'
;

const
orxSTRING orxSTRING_EOL = "
/r
"
;

#endif

目录分割符：

/*
*** Directory separators ***
*/

const
orxCHAR     orxCHAR_DIRECTORY_SEPARATOR_WINDOWS    = '//'
;
const
orxCHAR     orxCHAR_DIRECTORY_SEPARATOR_LINUX      = '/'
;
const
orxSTRING   orxSTRING_DIRECTORY_SEPARATOR_WINDOWS = "
//
"
;
const
orxSTRING   orxSTRING_DIRECTORY_SEPARATOR_LINUX    = "/"
;

#ifdef __orxWINDOWS__

const
orxCHAR orxCHAR_DIRECTORY_SEPARATOR = '//'
;

const
orxSTRING orxSTRING_DIRECTORY_SEPARATOR = "
//
"
;

#else
/*
__orxWINDOWS__
*/

/*
Linux / Mac / GP2X / Wii
*/

#if defined(__orxLINUX__) || defined(__orxMAC__) || defined(__orxGP2X__) || defined(__orxWII__) || defined(__orxIPHONE__)

const
orxCHAR orxCHAR_DIRECTORY_SEPARATOR = '/'
;

const
orxSTRING orxSTRING_DIRECTORY_SEPARATOR = "/"
;

#endif
/*
__orxLINUX__ || __orxMAC__ || __orxGP2X__ || __orxWII__ || __orxIPHONE__
*/

#endif
/*
__orxWINDOWS__
*/

做跨平台应用的总会感叹有个标准多好，因为不同厂商在自己系统上定义的东西总是那么的千差万别，甚至感觉故意为了不同而不同，上面这些都不多说了。想起OpenGL和D3D中右手左手坐标系，纵优先行优先矩阵等问题就脑袋疼。

orxModule.h/orxModule.c：

这两个文件算是Orx的模块的基础，因为他们就是管理各个模块的。

记得有个编程中的话是这么说的，“你给我看流程图后，我什么都还不清楚，你给我看你的表结构，我就知道你的流程图会是怎么样了。”

所以这里先看Orx模块管理中的基础结构，看了以后的确不用看具体函数实现了。

/*
**************************************************************************

* Structure declaration *

**************************************************************************
*/

/*
* Internal module info structure

*/

typedef
struct
__orxMODULE_INFO_t

{

orxU64 u64DependFlags; /*
*< Dependency flags : 8
*/

orxU64 u64OptionalDependFlags; /*
*< Optional dependency flags : 16
*/

orxMODULE_SETUP_FUNCTION pfnSetup; /*
*< Setup function : 20
*/

orxMODULE_INIT_FUNCTION pfnInit; /*
*< Init function : 24
*/

orxMODULE_EXIT_FUNCTION pfnExit; /*
*< Exit function : 28
*/

orxU32 u32StatusFlags; /*
*< Status flags : 32
*/

} orxMODULE_INFO;

/*
* Static structure

*/

typedef
struct
__orxMODULE_STATIC_t

{

orxMODULE_INFO astModuleInfo[orxMODULE_ID_NUMBER];

orxU32 u32InitLoopCounter;

orxU32 u32Flags;

} orxMODULE_STATIC;

/*
**************************************************************************

* Static variables *

**************************************************************************
*/

/*
* static data

*/

static
orxMODULE_STATIC sstModule;

所有的相关函数都是操作sstModule这个全局的变量。此变量的主要结构是orxMODULE_INFO
类型的数组，每个orxMODULE_INFO
类型的变量都包含自己的依赖标志，可选依赖标志和状态标志，以及3个函数指针变量。3个函数指针变量分别是Init,Setup,Exit。

结构定义完以后，该怎么操作就和能清晰了。首先为每个模块指定确定的3大函数，指定各模块自己依赖的模块，每次操作后修改状态标志。

各函数实现概述：

orxModule_Register:指定"三大函数"：

/* Stores module functions */

sstModule.astModuleInfo[_eModuleID].pfnSetup = _pfnSetup;

sstModule.astModuleInfo[_eModuleID].pfnInit = _pfnInit;

sstModule.astModuleInfo[_eModuleID].pfnExit = _pfnExit;

Setup函数设置模块依赖的模块，Init用于初始化，Exit用于退出。

orxModule_RegisterAll：依次用orxModule_Register注册所有的模块：

并且，orx作者为了方便，使用了一个宏：

#define orxMODULE_REGISTER(MODULE_ID, MODULE_BASENAME) orxModule_Register(MODULE_ID, MODULE_BASENAME##_Setup, MODULE_BASENAME##_Init, MODULE_BASENAME##_Exit)

宏的意义很明显，即用MODULE_BASENAME来按对应规则生成对应的Setup,Init,Exit函数。

比如说，Orx的内存管理模块的ID是orxMODULE_ID_BANK，

定义的三个函数是：

/*
* Setups the bank module

*/

extern
orxDLLAPI void
orxFASTCALL orxBank_Setup();

/*
* Inits the bank Module

* @return orxSTATUS_SUCCESS / orxSTATUS_FAILURE

*/

extern
orxDLLAPI orxSTATUS orxFASTCALL orxBank_Init();

/*
* Exits from the bank module

*/

extern
orxDLLAPI void
orxFASTCALL orxBank_Exit();

注册的时候，使用宏就简单的用

orxMODULE_REGISTER(orxMODULE_ID_BANK, orxBank);

效果相当于

orxModule_Register(orxMODULE_ID_BANK
, orxBank_Setup
, orxBank_Init()
, orxBank_Exit()
)

其实也没有什么太多好说的，就是个宏扩展的使用而已。

orxModule_AddDependency:

设定标志位而已。

sstModule.astModuleInfo[_eModuleID].u64DependFlags |= ((orxU64)1) << _eDependID;

可以看到，对于依赖的标志位是以一个无符号64位的整数来指定的，每一位表示对一个模块的支持，所以Orx目前最多支持64个模块。

Setup,SetupAll,InitAll,Exit,ExitAll的函数感觉没有什么太多好说的了，就是调用对应模块/所有模块Register好的3大函数指针指向的函数。

Init,单独初始化某个模块的部分可以稍微分析一下：

首先，初始化时，会先通过

if(!(sstModule.astModuleInfo[_eModuleID].u32StatusFlags & (orxMODULE_KU32_STATUS_FLAG_INITIALIZED|orxMODULE_KU32_STATUS_FLAG_TEMP)))

来判断当前模块是否已经初始化，已经初始化的话就直接返回了。

在确认当前模块需要进行初始化时，需要先初始化此模块的依赖的模块，在初始化所有依赖的模块后，为正在初始化模块的状态位或上orxMODULE_KU32_STATUS_FLAG_TEMP标志

表示开始初始化，然后调用Register过此模块Init的函数指针指向的函数进行实质的初始化，初始化过后，再加置orxMODULE_KU32_STATUS_FLAG_INITIALIZED标志。

同时在初始化模块开始时

/* Increases loop counter */

sstModule.u32InitLoopCounter++;

结束时

/* Decreases loop counter */

sstModule.u32InitLoopCounter--;

然后通过

/* Was external call? */

if(sstModule.u32InitLoopCounter == 0)

来判断什么时候一整轮初始化的结束，结束时调用

/* For all modules */

for(u32Index = 0; u32Index < orxMODULE_ID_NUMBER; u32Index++)

{

/* Cleans temp status */

sstModule.astModuleInfo[u32Index].u32StatusFlags &= ~orxMODULE_KU32_STATUS_FLAG_TEMP;

}

取消所有本轮初始化的临时状态。

光是讲流程的话可能有些混乱，形象的描述一下初始化单独一个模块的过程。

因为模块之间的依赖问题，初始化一个模块就相当于需要初始化此模块依赖的所有模块，也需要初始化依赖模块依赖的模块，最后形成的是一个树状结构。只有当依赖关系到达树的叶节点（也就表示此模块是最基础的模块了，没有其他依赖）时才进行叶节点实际的初始化。同时，没初始化一个都置标志位，防止同一个模块初始化两次。当sstModule.u32InitLoopCounter为0时，表示此轮初始化已经又回到了最开始初始化的那个模块(根节点)，此轮初始化结束。

从这个描述中也说明了一个问题，那就是Orx不允许模块的循环依赖，否则会初始化失败。但是多个模块依赖一个模块和一个模块依赖多个模块都是允许的。

同时，稍微看一下Orx的模块之间的依赖关系，可以发现相互的依赖非常复杂，我本来想做一个依赖图的，发现难度太大。。。。。。。。。Orx的模块依赖关
系虽然总体上是个树形结构，但是该树没有太良好的层级结构，大量跨层的依赖，导致显得非常混乱。

小结

首先，这么一大堆模块管理代码存在的必要性。从作用来看，假如非要讲优点的话，我感觉模块管理的作用有下面几个：

1。正常初始化，释放各模块，对于C语言来讲，没有构造函数，没有析构函数，对于一个模块只能使用一个结构来完成，初始化和退出都需要手动来做，使用Orx这样的模块管理可以在模块级别实现稍微自动化一些的初始化和退出。

2。集中管理各模块之间的依赖，使得初始化更加自动化，不易出错。

3。依赖于第2点，对于完全不需要的模块，可以完全不初始化。

但是，这些作用（其实我也不知道真实目的）都没有太好的完成。

首先，初始化的依赖问题虽然比较麻烦，但是可以在一个集中的初始化函数中一次完成，没有必要弄这么多代码出来。另外，虽然现在Orx的模块管理代码可以使得不需要的模块不初始化，但是因为每个模块都是用一个相关结构的全局变量来实现的，所以仅仅只能省一些初始化时间而已，内存上并没有节省，另外，对于不想初始化的代码，直接去掉初始化函数的调用就可以了，费不着用这么多代码来实现自动化。即使说初始化什么模块可能是通过配置来决定的，所以自动化有必要，但是仅仅剩下一些初始化时间的必要性并不大，还不如全部都初始化了。

但是，我还是很欣赏这种将模块管理起来的代码，虽然有些冗余，但是将模块统一管理在一个数组之中，比在某些巨大的Init,Exit函数去一一调用各模块的相应函数要来的漂亮。新添加模块的时候，只需要添加对应的3大函数就能自动化的完成一些初始化及收尾工作，也比每添加一个就需要在巨大的Init,Exit函数中添加一条来的方便。

原创文章作者保留版权转载请注明原作者并给出链接

2010年07月31日

非典型2D游戏引擎 Orx 源码阅读笔记(1) 总体结构

前言

完全不了解Orx的可以参考我写的《orx 库简单介绍
》以及官方主页
。

开始学习Orx其实很久了，但是一直仅仅是学习了一些基础的用法，没有深入研究源代码，在用Orx写游戏的时候常常会因为某个配置出现问题而完全束手无策，求助于iarwain，最近在移植一个Win32编好的游戏到IPhone上时，又碰到了问题，还是束手无策，因为我决定还是看看Orx的源代码，不然，命运总是不掌握在自己的手里，就像撞大运编程一样。这也是我当时选择引擎最大的要求之一，开源，所能带来的好处之一。而Orx这种"数据驱动"式的引擎，更加是使得了解源代码如此重要，因为我感觉对于我来说，我更加能够发现调用一个API的错误，而非常难去发现一个配置上的错误，我一直也认为这是Orx"数据驱动"的弊端之一，这也是我认为Orx非典型的原因。

源码阅读思路及目标

对于源码阅读，我还是用个人习惯的的先从整体上了解各个模块，然后单独了解各模块源码，最后整个的走一下主要的执行流程，了解各个模块是怎么结合在一起的。

对于Orx的源码阅读，我还是不准备达到到句句理解的地步，基本上还是以整体了解为主，顺便关心一下个人比较感兴趣的渲染部分，对源码的理解程度以最后能够完全脱离Orx的配置模块，靠自己的代码将各个模块组合起来，并实现基本的Orx功能为止。Orx作为跨平台引擎，我不能去分析所有其支持的平台，主要关心的版本是Win32版本及IPhone版本，当然，事实上因为Orx的跨平台主要是依赖于将SDL,GLFW等库作为插件来完成的，所以，其实在Orx这一层的代码其实都一样。（IPhone版本比较特殊）

为了无论在何时都能找到本文对应的源码，这里使用最新的Orx1.2版本的源码，并未使用svn上的版本。

Orx总体结构

作为一个iarwain目标为完整game engine的Orx,模块的构成还是比较复杂的。

物理结构：

从Orx源代码的目录上可以基本区分出来：

Animation：动画部分

base：基础部分，包含一些为了跨平台而定义的宏，Orx本身需要的宏和常用常量,函数，还有Orx的模块处理

core：内核部分，包括时钟，配置，事件部分，本地化部分

debug：日志部分及FPS显示

display：显示部分

io：IO部分，包括文件IO，及摇杆，鼠标，键盘的输入。

main：main函数参数处理

math：数学相关部分，包括一个vector的实现

memory：内存处理部分，

object：object部分

physics:物理部分

plugin：插件部分

render：渲染部分，包括摄像机，特效，渲染器，shader，视口等部分

sound：声音部分

utils：工具类部分，包括用C语言实现的HashTable,List,Tree3大容器，一些有用的String函数，以及一个screenshot实现。（感觉这个放在display更加合适）

另外，Orx比较特殊的是包含一套插件：

通过插件来实现的部分有：Display,Joystick,Keyboard,Mouse,Physics,Render,Sound。

通用插件（实现除物理，声音以外的功能）本身现在有4套：GLFW
,IPhone,SDL
,SFML
。

其中SFML是1.1版本前使用的插件。GLFW是现在(1.2版本)默认使用的插件。

其中SFML,GLFW插件支持3大主流平台(Win32,Linux,MacOS)，SDL插件仅支持Win32,Linux。

IPhone的插件是因为IPhone版本比较特殊而特别加入的，对应支持IPhone/IPad平台。

声音插件现在有SFML的插件和OpenAL的插件。SFML为1.1以前版本默认声音插件，OpenAL的实现为1.2版本默认声音插件。可能是因为OpenAL插件太好，所以作者虽然使用了SDL，但是并没有使用SDL的声音模块做SDL的声音插件。

物理插件目前仅有Box2D实现的插件。

逻辑结构：

从"orxModule.h"的一个枚举定义中，可以看到Orx作者为Orx整体的逻辑模块的划分。

/*
* Module enum
*/

typedef
enum
__orxMODULE_ID_t

{

orxMODULE_ID_ANIM = 0
,

orxMODULE_ID_ANIMPOINTER,

orxMODULE_ID_ANIMSET,

orxMODULE_ID_BANK,

orxMODULE_ID_BODY,

orxMODULE_ID_CAMERA,

orxMODULE_ID_CLOCK,

orxMODULE_ID_CONFIG,

orxMODULE_ID_DISPLAY,

orxMODULE_ID_EVENT,

orxMODULE_ID_FILE,

orxMODULE_ID_FILESYSTEM,

orxMODULE_ID_FONT,

orxMODULE_ID_FPS,

orxMODULE_ID_FRAME,

orxMODULE_ID_FX,

orxMODULE_ID_FXPOINTER,

orxMODULE_ID_GRAPHIC,

orxMODULE_ID_INPUT,

orxMODULE_ID_JOYSTICK,

orxMODULE_ID_KEYBOARD,

orxMODULE_ID_LOCALE,

orxMODULE_ID_MAIN,

orxMODULE_ID_MEMORY,

orxMODULE_ID_MOUSE,

orxMODULE_ID_OBJECT,

orxMODULE_ID_PARAM,

orxMODULE_ID_PHYSICS,

orxMODULE_ID_PLUGIN,

orxMODULE_ID_RENDER,

orxMODULE_ID_SCREENSHOT,

orxMODULE_ID_SHADER,

orxMODULE_ID_SHADERPOINTER,

orxMODULE_ID_SOUND,

orxMODULE_ID_SOUNDPOINTER,

orxMODULE_ID_SOUNDSYSTEM,

orxMODULE_ID_SPAWNER,

orxMODULE_ID_STRUCTURE,

orxMODULE_ID_SYSTEM,

orxMODULE_ID_TEXT,

orxMODULE_ID_TEXTURE,

orxMODULE_ID_VIEWPORT,

orxMODULE_ID_NUMBER,

orxMODULE_ID_MAX_NUMBER = 64
,

orxMODULE_ID_NONE = orxENUM_NONE

} orxMODULE_ID;

因为英文命名的枚举已经很能说明各逻辑模块包含的内容了，这里就不一一介绍了。

引用的外部工程

现在已经不是需要所有事情都从头做起的年代了，作为游戏引擎，需要处理的各个方面内容实在太多，很难都完全自己处理，Orx使用了一些外部库来完成一些相应功能。

深蓝在Orx的官方中文论坛中进行了一些总结
，较为详细，可供参考。

我这里仅仅简单的说明一下：

Box2D：物理部分

freetype：制作字体工具时使用，因为Orx引擎本身并不支持freetype即时生成的材质实现字体显示，所以事实上Orx引擎本身并不需要freetype。

glfw,SDL，SFML：作为主要模块的插件实现，主要用于解决跨平台相关的问题。

SOIL：用于支持常用的图片格式。

OpenAL：声音处理。

stb_vorbis：ogg声音格式支持。

libsndfile：wav,aiff声音格式支持。

我描述的仅仅是大概的情况，关于引用外部工程以及插件的详细使用情况可以参考Orx的changelog
。

关于SFML

在最后提供一些额外的关于SFML信息，虽然与Orx的总体结构无关，但是也顺便在此记录。

很多外部工程的引用都是从新的1.2开始的，而且都是为了替代SFML的相关部分而引入的，也就是说，最后Orx用glfw/SDL + SOIL + OpenAL + stb_vorbis + libsndfile才实现了SFML的部分功能。这还真的仅仅是SFML的部分功能，仅仅是Orx需要的那一部分功能。这里可以看出SFML有多么强大，其作为simple and fast Multimedia library的库，与SDL(Simple DirectMedia Layer)相比真的是太不simple了。事实上，从SFML的License页
可以看到，SFML本身就使用了

GLEW
is under the BSD license
, the SGI license
or the GLX license
OpenAL-Soft
is under the LGPL license
libsndfile
is under the LGPL license
stb_vorbis
is public domain
libjpeg
is public domain
libpng
is under the zlib/png license
zlib
is under the zlib/png license
SOIL
is public domain
freetype
is under the FreeType license
or the GPL license

这么多的外部库。而其中Orx最后使用用于替代SFML的相应部分的库，可以看到，也基本来自于SFML本身使用的这些库。。。。。。。。#@￥#@%……￥#@……￥6

iarwain对SFML的评价是强大，简单，但是buggy。

并且，从效率上来看，iarwain也是使用了这些外部库，但是在changelog中,有这么一句：

* IMPORTANT: Added new plugins for embedded versions: SDL plugins for win/linux (35-40% than the SFML ones) and GLFW plugins for win/linux/osx (~2% faster than SDL ones).

也就是说，在1.2版本比1.1版本要快35%一样，仅仅因为使用了新的插件替代了SFML。不知道SFML在simple与fast的平衡中，是否因为太过强大，功能太过丰富，而导致实现simple的代价过大。

在features页面
上，可以看到，SFML甚至还包含一个网络模块。。。。。

不过，SFML用C++结合了上面这么多有用的库，实现那么多功能，还有一堆的其他语言(Python,Ruby,D,C#等）绑定，并且也使用很自由的zlib/png协议，感觉还是值得一试的。特别是当对效率没有那么高的要求的时候。。。。。。

原创文章作者保留版权转载请注明原作者并给出链接

2010年07月30日

SDL源码阅读笔记（3）渲染模块

这是SDL中我最关心的模块，即SDL是怎么抽象渲染模块的接口然后实现跨平台的，已经在DirectX/OpenGL中绘制图形的。
本文与前面两篇使用不同的描述方式，前面两篇文章以结构性的铺开分析为主，本文决定使用流程分析。

SDL+OpenGL

   对于OpenGL版本，由于主要的绘制都是由OpenGL的API来完成，与SDL关系并不大，所以只看SDL_SetVideoMode
部分。
    在写上一篇文章
的时候，我很惊讶的发现，即使是在SDL使用了DirectX版本的video driver后，仍然可以使用OpenGL来完成渲染。关键点在SDL_SetVideoMode
函数上，先看此函数。
使用OpenGL时，用以下方式调用此函数：
SDL_Surface* screen = SDL_SetVideoMode( WINDOW_WIDTH, WINDOW_HEIGHT, 16, SDL_OPENGL);
即最后一个参数为SDL_OPENGL。
此时，最后使用DirectX来渲染还是使用OpenGL来渲染，最大的不同自然在于surface的创建，
在SDL_SetVideoMode中会有这么一句：
mode = video->SetVideoMode(this, prev_mode,video_w,video_h,video_bpp,flags);
即使用当前video driver来设置video mode，由于我已经选中了directX的video driver了，所以实际调用的是：
SDL_Surface *DX5_SetVideoMode(_THIS, SDL_Surface *current,
               int width, int height, int bpp, Uint32 flags)
此函数中，有这么一段代码：

    /*
If we are setting a GL mode, use GDI, not DirectX (yuck)
*/

    if
( flags & SDL_OPENGL ) {
        Uint32 Rmask, Gmask, Bmask;

        /*
Recalculate the bitmasks if necessary
*/

        if
( bpp == current->format->BitsPerPixel ) {
            video = current;
        } else
{
            switch
(bpp) {
                case
15
:
                case
16
:
                if
( 0
/*
DIB_SussScreenDepth() == 15
*/
) {
                    /*
5-5-5
*/

                    Rmask = 0x00007c00
;
                    Gmask = 0x000003e0
;
                    Bmask = 0x0000001f
;
                } else
{
                    /*
5-6-5
*/

                    Rmask = 0x0000f800
;
                    Gmask = 0x000007e0
;
                    Bmask = 0x0000001f
;
                }
                break
;
                case
24
:
                case
32
:
                /*
GDI defined as 8-8-8
*/

                Rmask = 0x00ff0000
;
                Gmask = 0x0000ff00
;
                Bmask = 0x000000ff
;
                break
;
                default
:
                Rmask = 0x00000000
;
                Gmask = 0x00000000
;
                Bmask = 0x00000000
;
                break
;
            }
            video = SDL_CreateRGBSurface(SDL_SWSURFACE, 0
, 0
, bpp,
                                         Rmask, Gmask, Bmask, 0
);
            if
( video == NULL
) {
                SDL_OutOfMemory();
                return
(NULL
);
            }
        }

看作者的注释：
/*
If we are setting a GL mode, use GDI, not DirectX (yuck)
*/

啥都明白了，原来即使是使用DirectX的video driver,SDL会在SetVideoMode的时候判断是否是使用OpenGL，是的话还是改用了GDI。
然后，WIN_GL_SetupWindow函数中，完成了在Windows下使用OpenGL需要设定的内容。具体的内容可以参考《Win32下的OpenGL编程必须步骤
》。

既然使用DirectX版本video driver的SDL最后其实也是使用GDI版本的surface,这里回头来看看GDI版本创建surface的步骤。
在GDI版本的video driver实际调用的是DIB_SetVideoMode函数来设定VideMode。

    /*
Recalculate the bitmasks if necessary
*/

    if
( bpp == current->format->BitsPerPixel ) {
        video = current;
    } else
{
        switch
(bpp) {
            case
15
:
            case
16
:
                if
( DIB_SussScreenDepth() == 15
) {
                    /*
5-5-5
*/

                    Rmask = 0x00007c00
;
                    Gmask = 0x000003e0
;
                    Bmask = 0x0000001f
;
                } else
{
                    /*
5-6-5
*/

                    Rmask = 0x0000f800
;
                    Gmask = 0x000007e0
;
                    Bmask = 0x0000001f
;
                }
                break
;
            case
24
:
            case
32
:
                /*
GDI defined as 8-8-8
*/

                Rmask = 0x00ff0000
;
                Gmask = 0x0000ff00
;
                Bmask = 0x000000ff
;
                break
;
            default
:
                Rmask = 0x00000000
;
                Gmask = 0x00000000
;
                Bmask = 0x00000000
;
                break
;
        }
        video = SDL_CreateRGBSurface(SDL_SWSURFACE,
                    0
, 0
, bpp, Rmask, Gmask, Bmask, 0
);
        if
( video == NULL
) {
            SDL_OutOfMemory();
            return
(NULL
);
        }
    }

其实与DX5_SetVideoMode中创建Surface的代码一模一样，DX5_SetVideoMode函数中所谓的使用GDI的surface其实指的就是拷贝一份GDI创建surface的代码过去吧。。。。。接下来，同样的调用WIN_GL_SetupWindow完成Windows下设置OpenGL使用的必要操作。
看完相关源代码后，发现一切还是比较简单。

SDL GDI video driver

    看完了SDL+OpenGL，这里了解一下SDL在使用GDI video driver时，自己附带的渲染功能。至于DirectX部分我就不看了，毕竟我对DirectX了解的不算太多，而且SDL用的DirectX版本实在太老了，但是，其实应该也不难懂，使用DDraw的方法其实和SDL的surface差不多。
SDL_LoadBMP其实是这样定义的一个宏：
#define SDL_LoadBMP(file)   SDL_LoadBMP_RW(SDL_RWFromFile(file, "rb"), 1)
SDL用SDL_Surface * SDL_LoadBMP_RW (SDL_RWops *src, int freesrc)这个函数来完成自己的从二进制数据中对BMP的解析，没有使用Windows提供的API（为了不同平台使用一套代码），加上BMP图形的数据解析起来还是比较简单的。
在
用类似
SDL_Surface *screen = SDL_SetVideoMode(640 , 480 , 16 , SDL_DOUBLEBUF);
的代码创建surface的时候，（即不是使用OpenGL的时候）
在SetVideoMode的时候，SDL用以下代码来完成offscreen buffer：（这也是我第一次了解怎么使用Windows API来创建offscreen buffer）

        /*
Create the offscreen bitmap buffer
*/

        hdc = GetDC(SDL_Window);
        screen_bmp = CreateDIBSection(hdc, binfo, DIB_RGB_COLORS,
                    (void
**)(&video->pixels), NULL
, 0
);
        ReleaseDC(SDL_Window, hdc);
        SDL_free(binfo);
        if
( screen_bmp == NULL
) {
            if
( video != current ) {
                SDL_FreeSurface(video);
            }
            SDL_SetError("Couldn't create DIB section"
);
            return
(NULL
);
        }

最主要的API自然是CreateDIBSection，我查了下MSDN:

CreateDIBSection Function

The CreateDIBSection
function creates a DIB that applications can write to directly. The function gives you a pointer to the location of the bitmap bit values. You can supply a handle to a file-mapping object that the function will use to create the bitmap, or you can let the system allocate the memory for the bitmap.

按API的意思，其实这也不是原生用于offscreen buffer的，仅仅是一个可以直接写bitmap的内存。
在最后flip的时候，下面这段函数很关键：

static
void
DIB_NormalUpdate(_THIS, int
numrects, SDL_Rect *rects)
{
HDC hdc, mdc;
int
i;

    hdc = GetDC(SDL_Window);
    if
( screen_pal ) {
        SelectPalette(hdc, screen_pal, FALSE);
    }
    mdc = CreateCompatibleDC(hdc);
    SelectObject(mdc, screen_bmp);
    for
( i=0
; i
        BitBlt(hdc, rects[i].x, rects[i].y, rects[i].w, rects[i].h,
                    mdc, rects[i].x, rects[i].y, SRCCOPY);
    }
    DeleteDC(mdc);
    ReleaseDC(SDL_Window, hdc);
}

在这里，使用了

mdc = CreateCompatibleDC(hdc);
SelectObject(mdc, screen_bmp);

选择offscreen buffer到新创建的mdc中，然后从新创建的mdc向当前的hdc进行BitBlt，完成flip操作。当然，个人感觉，这种GDI模拟offscreen buffer的操作，在flip的时候还需要进行BitBlt，即使在两个dc间进行BitBlt比从内存到dc的快，但是效率上还是与OpenGL/D3D那种直接支持offscrren buffer的不在一个数量级，那可是直接切换显示不同区域的显存数据而已。

SDL源码大概浏览了一遍，没有细看，总的来说，看源码还是挺有帮助的，对于开源软件来说，文档也不能完全的详细说明每一个API的使用，但是对于开源软件，源码就是最好的文档。就此结束SDL的源码阅读过程，下一步，也许是略看Orx源码的时候了。。。。。。。。。。。。。。。。。。。。。。

总结

基本上，对于游戏来讲，OpenGL的渲染部分其实并没有太大价值，虽然其接口的确非常简单，（也许不是游戏可以考虑使用一下）但是，作为一个跨平台的库，SDL还是有其独特的价值，SDL提供了一个跨平台的窗口管理模块，事件系统，多线程模块，声音模块，并且能够让你很方便的使用OpenGL渲染与其配置，基本上可以看做是一个非常强大并且完整的OpenGL使用环境。就像glut/free glut曾经想要做到的那样，只不过SDL比其走的更远而已。类似的库还有GLFW
，完成的其实也不错。对于只想好好的关心渲染部分，对其他跨平台的脏活累活不感兴趣的，SDL算是不错的选择。

原创文章作者保留版权转载请注明原作者并给出链接

2010年07月26日

SDL源码阅读笔记（2） video dirver的初始化及选择

前一篇文章
讲了SDL的除video以外的大部分模块。本文主要关注SDL的video模块部分。

SDL中的video模块包含了大部分与平台相关的代码，并且SDL处理的很有技巧性，这里利用C语言的函数指针来模拟了一种类似于面向对象的效果。

主要的关键点在

SDL_VideoDevice *current_video = NULL;

这一句定义的全局变量current_video上，我们先来看看这个变量类型SDL_VideoDevice。

主要在SDL_sysvideo.h这个文件中

struct
SDL_VideoDevice {

/*
* *
*/

/*
The name of this video driver
*/

const
char
*name;

/*
* *
*/

/*
Initialization/Query functions
*/

/*
Initialize the native video subsystem, filling 'vformat' with the

"best" display pixel format, returning 0 or -1 if there's an error.

int
(*VideoInit)(_THIS, SDL_PixelFormat *vformat);

/*
List the available video modes for the given pixel format, sorted

from largest to smallest.

SDL_Rect **(*ListModes)(_THIS, SDL_PixelFormat *format, Uint32 flags);

    /*
Set the requested video mode, returning a surface which will be

       set to the SDL_VideoSurface. The width and height will already

       be verified by ListModes(), and the video subsystem is free to

       set the mode to a supported bit depth different from the one

       specified -- the desired bpp will be emulated with a shadow

       surface if necessary. If a new mode is returned, this function

       should take care of cleaning up the current mode.

SDL_Surface *(*SetVideoMode)(_THIS, SDL_Surface *current,

int
width, int
height, int
bpp, Uint32 flags);

/*
Toggle the fullscreen mode
*/

int
(*ToggleFullScreen)(_THIS, int
on);

    /*
This is called after the video mode has been set, to get the

       initial mouse state. It should queue events as necessary to

       properly represent the current mouse focus and position.

void
(*UpdateMouse)(_THIS);

    /*
Create a YUV video surface (possibly overlay) of the given

       format. The hardware should be able to perform at least 2x

       scaling on display.

SDL_Overlay *(*CreateYUVOverlay)(_THIS, int
width, int
height,

Uint32 format, SDL_Surface *display);

        /*
Sets the color entries { firstcolor .. (firstcolor+ncolors-1) }

       of the physical palette to those in 'colors'. If the device is

       using a software palette (SDL_HWPALETTE not set), then the

       changes are reflected in the logical palette of the screen

       as well.

       The return value is 1 if all entries could be set properly

       or 0 otherwise.

int
(*SetColors)(_THIS, int
firstcolor, int
ncolors,

SDL_Color *colors);

/*
This pointer should exist in the native video subsystem and should

point to an appropriate update function for the current video mode

void
(*UpdateRects)(_THIS, int
numrects, SDL_Rect *rects);

/*
Reverse the effects VideoInit() -- called if VideoInit() fails

or if the application is shutting down the video subsystem.

void
(*VideoQuit)(_THIS);

/*
* *
*/

/*
Hardware acceleration functions
*/

/*
Information about the video hardware
*/

SDL_VideoInfo info;

/*
The pixel format used when SDL_CreateRGBSurface creates SDL_HWSURFACEs with alpha
*/

SDL_PixelFormat* displayformatalphapixel;

/*
Allocates a surface in video memory
*/

int
(*AllocHWSurface)(_THIS, SDL_Surface *surface);

/*
Sets the hardware accelerated blit function, if any, based

on the current flags of the surface (colorkey, alpha, etc.)

int
(*CheckHWBlit)(_THIS, SDL_Surface *src, SDL_Surface *dst);

/*
Fills a surface rectangle with the given color
*/

int
(*FillHWRect)(_THIS, SDL_Surface *dst, SDL_Rect *rect, Uint32 color);

/*
Sets video mem colorkey and accelerated blit function
*/

int
(*SetHWColorKey)(_THIS, SDL_Surface *surface, Uint32 key);

/*
Sets per surface hardware alpha value
*/

int
(*SetHWAlpha)(_THIS, SDL_Surface *surface, Uint8 value);

/*
Returns a readable/writable surface
*/

int
(*LockHWSurface)(_THIS, SDL_Surface *surface);

void
(*UnlockHWSurface)(_THIS, SDL_Surface *surface);

/*
Performs hardware flipping
*/

int
(*FlipHWSurface)(_THIS, SDL_Surface *surface);

/*
Frees a previously allocated video surface
*/

void
(*FreeHWSurface)(_THIS, SDL_Surface *surface);

/*
* *
*/

/*
Gamma support
*/

Uint16 *gamma;

/*
Set the gamma correction directly (emulated with gamma ramps)
*/

int
(*SetGamma)(_THIS, float
red, float
green, float
blue);

/*
Get the gamma correction directly (emulated with gamma ramps)
*/

int
(*GetGamma)(_THIS, float
*red, float
*green, float
*blue);

/*
Set the gamma ramp
*/

int
(*SetGammaRamp)(_THIS, Uint16 *ramp);

/*
Get the gamma ramp
*/

int
(*GetGammaRamp)(_THIS, Uint16 *ramp);

/*
* *
*/

/*
OpenGL support
*/

/*
Sets the dll to use for OpenGL and loads it
*/

int
(*GL_LoadLibrary)(_THIS, const
char
*path);

/*
Retrieves the address of a function in the gl library
*/

void
* (*GL_GetProcAddress)(_THIS, const
char
*proc);

/*
Get attribute information from the windowing system.
*/

int
(*GL_GetAttribute)(_THIS, SDL_GLattr attrib, int
* value);

/*
Make the context associated with this driver current
*/

int
(*GL_MakeCurrent)(_THIS);

/*
Swap the current buffers in double buffer mode.
*/

void
(*GL_SwapBuffers)(_THIS);

/*
OpenGL functions for SDL_OPENGLBLIT
*/

#if SDL_VIDEO_OPENGL

#if !defined(__WIN32__)

#define WINAPI

#endif

#define SDL_PROC(ret,func,params) ret (WINAPI *func) params;

#include
"SDL_glfuncs.h"

#undef SDL_PROC

/*
Texture id
*/

GLuint texture;
#endif

int
is_32bit;

/*
* *
*/

/*
Window manager functions
*/

/*
Set the title and icon text
*/

void
(*SetCaption)(_THIS, const
char
*title, const
char
*icon);

/*
Set the window icon image
*/

void
(*SetIcon)(_THIS, SDL_Surface *icon, Uint8 *mask);

    /*
Iconify the window.

       This function returns 1 if there is a window manager and the

       window was actually iconified, it returns 0 otherwise.

int
(*IconifyWindow)(_THIS);

/*
Grab or ungrab keyboard and mouse input
*/

SDL_GrabMode (*GrabInput)(_THIS, SDL_GrabMode mode);

/*
Get some platform dependent window information
*/

int
(*GetWMInfo)(_THIS, SDL_SysWMinfo *info);

/*
* *
*/

/*
Cursor manager functions
*/

/*
Free a window manager cursor

This function can be NULL if CreateWMCursor is also NULL.

void
(*FreeWMCursor)(_THIS, WMcursor *cursor);

/*
If not NULL, create a black/white window manager cursor
*/

WMcursor *(*CreateWMCursor)(_THIS,

Uint8 *data, Uint8 *mask, int
w, int
h, int
hot_x, int
hot_y);

/*
Show the specified cursor, or hide if cursor is NULL
*/

int
(*ShowWMCursor)(_THIS, WMcursor *cursor);

/*
Warp the window manager cursor to (x,y)

If NULL, a mouse motion event is posted internally.

void
(*WarpWMCursor)(_THIS, Uint16 x, Uint16 y);

/*
If not NULL, this is called when a mouse motion event occurs
*/

void
(*MoveWMCursor)(_THIS, int
x, int
y);

    /*
Determine whether the mouse should be in relative mode or not.

       This function is called when the input grab state or cursor

       visibility state changes.

       If the cursor is not visible, and the input is grabbed, the

       driver can place the mouse in relative mode, which may result

       in higher accuracy sampling of the pointer motion.

void
(*CheckMouseMode)(_THIS);

/*
* *
*/

/*
Event manager functions
*/

/*
Initialize keyboard mapping for this driver
*/

void
(*InitOSKeymap)(_THIS);

/*
Handle any queued OS events
*/

void
(*PumpEvents)(_THIS);

/*
* *
*/

/*
Data common to all drivers
*/

SDL_Surface *screen;

SDL_Surface *shadow;

SDL_Surface *visible;

SDL_Palette *physpal; /*
physical palette, if != logical palette
*/

SDL_Color *gammacols; /*
gamma-corrected colours, or NULL
*/

char
*wm_title;

char
*wm_icon;

int
offset_x;

int
offset_y;

SDL_GrabMode input_grab;

/*
Driver information flags
*/

int
handles_any_size; /*
Driver handles any size video mode
*/

/*
* *
*/

/*
Data used by the GL drivers
*/

struct
{

int
red_size;

int
green_size;

int
blue_size;

int
alpha_size;

int
depth_size;

int
buffer_size;

int
stencil_size;

int
double_buffer;

int
accum_red_size;

int
accum_green_size;

int
accum_blue_size;

int
accum_alpha_size;

int
stereo;

int
multisamplebuffers;

int
multisamplesamples;

int
accelerated;

int
swap_control;

int
driver_loaded;

char
driver_path[256
];

void
* dll_handle;

} gl_config;

/*
* *
*/

/*
Data private to this driver
*/

struct
SDL_PrivateVideoData *hidden;

struct
SDL_PrivateGLData *gl_data;

/*
* *
*/

/*
The function used to dispose of this structure
*/

void
(*free)(_THIS);

};

这个结构主要包含的是函数指针，每个函数指针表示了一个与平台相关的函数。在运行时，给这些函数指针赋值，指定成对应平台的函数实现，以此实现了使用此结构指针current_video的上层的代码的稳定与一致。

这里首先关心两个流程，其一，初始化给这些函数指针赋值的过程。

这个过程在SDL_VideoInit函数中实现：

SDL初始化基本流程：

SDL_Init(SDL_INIT_VIDEO)->SDL_InitSubSystem（SDL_INIT_VIDEO)->SDL_VideoInit()

中途会调用以"SDL_VIDEODRIVER"为参数调用SDL_getenv函数来获取全局配置中指定的对应的video driver。

代码如下：

if
( SDL_VideoInit(SDL_getenv("SDL_VIDEODRIVER"
),

(flags&SDL_INIT_EVENTTHREAD)) < 0
) {

return
(-1
);

}

我没有设定，所以会以name = NULL为第一参数来调用SDL_VideoInit，也就是让SDL自己选择一个video driver。

SDL会从一个

typedef
struct
VideoBootStrap {

const
char
*name;

const
char
*desc;

int
(*available)(void
);

SDL_VideoDevice *(*create)(int
devindex);

} VideoBootStrap;

结构的全局变量bootstrap数组中选取一个可以使用的video driver。

一共有这么多可能的video driver:

/*
Available video drivers
*/

static
VideoBootStrap *bootstrap[] = {
#if SDL_VIDEO_DRIVER_QUARTZ

&QZ_bootstrap,
#endif

#if SDL_VIDEO_DRIVER_X11

&X11_bootstrap,
#endif

#if SDL_VIDEO_DRIVER_DGA

&DGA_bootstrap,
#endif

#if SDL_VIDEO_DRIVER_NANOX

&NX_bootstrap,
#endif

#if SDL_VIDEO_DRIVER_IPOD

&iPod_bootstrap,
#endif

#if SDL_VIDEO_DRIVER_QTOPIA

&Qtopia_bootstrap,
#endif

#if SDL_VIDEO_DRIVER_WSCONS

&WSCONS_bootstrap,
#endif

#if SDL_VIDEO_DRIVER_FBCON

&FBCON_bootstrap,
#endif

#if SDL_VIDEO_DRIVER_DIRECTFB

&DirectFB_bootstrap,
#endif

#if SDL_VIDEO_DRIVER_PS2GS

&PS2GS_bootstrap,
#endif

#if SDL_VIDEO_DRIVER_PS3

&PS3_bootstrap,
#endif

#if SDL_VIDEO_DRIVER_GGI

&GGI_bootstrap,
#endif

#if SDL_VIDEO_DRIVER_VGL

&VGL_bootstrap,
#endif

#if SDL_VIDEO_DRIVER_SVGALIB

&SVGALIB_bootstrap,
#endif

#if SDL_VIDEO_DRIVER_GAPI

&GAPI_bootstrap,
#endif

#if SDL_VIDEO_DRIVER_WINDIB

&WINDIB_bootstrap,
#endif

#if SDL_VIDEO_DRIVER_DDRAW

&DIRECTX_bootstrap,
#endif

#if SDL_VIDEO_DRIVER_BWINDOW

&BWINDOW_bootstrap,
#endif

#if SDL_VIDEO_DRIVER_TOOLBOX

&TOOLBOX_bootstrap,
#endif

#if SDL_VIDEO_DRIVER_DRAWSPROCKET

&DSp_bootstrap,
#endif

#if SDL_VIDEO_DRIVER_PHOTON

&ph_bootstrap,
#endif

#if SDL_VIDEO_DRIVER_EPOC

&EPOC_bootstrap,
#endif

#if SDL_VIDEO_DRIVER_XBIOS

&XBIOS_bootstrap,
#endif

#if SDL_VIDEO_DRIVER_GEM

&GEM_bootstrap,
#endif

#if SDL_VIDEO_DRIVER_PICOGUI

&PG_bootstrap,
#endif

#if SDL_VIDEO_DRIVER_DC

&DC_bootstrap,
#endif

#if SDL_VIDEO_DRIVER_NDS

&NDS_bootstrap,
#endif

#if SDL_VIDEO_DRIVER_RISCOS

&RISCOS_bootstrap,
#endif

#if SDL_VIDEO_DRIVER_OS2FS

&OS2FSLib_bootstrap,
#endif

#if SDL_VIDEO_DRIVER_AALIB

&AALIB_bootstrap,
#endif

#if SDL_VIDEO_DRIVER_CACA

&CACA_bootstrap,
#endif

#if SDL_VIDEO_DRIVER_DUMMY

&DUMMY_bootstrap,
#endif

NULL

};

都是通过宏来筛选的。

- bootstrap 0x100a2b1c bootstrap VideoBootStrap * [4]

+ [0x0] 0x100a1160 _WINDIB_bootstrap {name=0x10099428 "windib" desc=0x1009940c "Win95/98/NT/2000/CE GDI" available=0x1005eaf0 ...} VideoBootStrap *

+ [0x1] 0x100a25e8 _DIRECTX_bootstrap {name=0x10099ab4 "directx" desc=0x10099a98 "Win95/98/2000 DirectX" available=0x100651d0 ...} VideoBootStrap *

+ [0x2] 0x100a2aec _DUMMY_bootstrap {name=0x100995a4 "dummy" desc=0x1009b3e4 "SDL dummy video driver" available=0x10072090 ...} VideoBootStrap *

+ [0x3] 0x00000000 {name=??? desc=??? available=??? ...} VideoBootStrap *

在我的电脑上(Win32），一共有上面3种可能，windib（即GDI）,directX,dummy。事实上OpenGL在Win32的环境中都没有列出来，当然，但是在以前的例子中，我还是使用了SDL+OpenGL来渲染，原因在于video毕竟不是如同其名字所示，仅仅包含渲染或者视频方面的东西，它其实代表了大部分SDL与平台相关的东西，渲染在SDL中也仅仅是占比较小的一部分。

选取video driver的时候，先调用VideoBootStrap
结构中的available
函数来判断此video driver有效则通过此结构的create函数来创建一个video driver.

如下：

for
( i=0
; bootstrap[i]; ++i ) {

if
( bootstrap[i]->available() ) {

video = bootstrap[i]->create(index);

if
( video != NULL
) {

break
;

}

创建的时候附带index,并且一旦创建成功，就停止了创建过程，在我的例子中，由于GDI方式排在第一，所以事实上，SDL在Win32环境下默认是选择了使用GDI的video driver。

此GDI video driver的create函数如下：

static
SDL_VideoDevice *DIB_CreateDevice(int
devindex)

{

SDL_VideoDevice *device;

/*
Initialize all variables that we clean on shutdown
*/

device = (SDL_VideoDevice *)SDL_malloc(sizeof
(SDL_VideoDevice));

if
( device ) {

SDL_memset(device, 0
, (sizeof
*device));

device->hidden = (struct
SDL_PrivateVideoData *)

SDL_malloc((sizeof
*device->hidden));

if
(device->hidden){

SDL_memset(device->hidden, 0
, (sizeof
*device->hidden));

device->hidden->dibInfo = (DibInfo *)SDL_malloc((sizeof
(DibInfo)));

if
(device->hidden->dibInfo == NULL
)

{

SDL_free(device->hidden);

device->hidden = NULL
;

}

device->gl_data = (struct
SDL_PrivateGLData *)

SDL_malloc((sizeof
*device->gl_data));

}

if
( (device == NULL
) || (device->hidden == NULL
) ||

(device->gl_data == NULL
) ) {

SDL_OutOfMemory();

DIB_DeleteDevice(device);

return
(NULL
);

}

SDL_memset(device->hidden->dibInfo, 0
, (sizeof
*device->hidden->dibInfo));

SDL_memset(device->gl_data, 0
, (sizeof
*device->gl_data));

/*
Set the function pointers
*/

device->VideoInit = DIB_VideoInit;

device->ListModes = DIB_ListModes;

device->SetVideoMode = DIB_SetVideoMode;

device->UpdateMouse = WIN_UpdateMouse;

device->SetColors = DIB_SetColors;

device->UpdateRects = NULL
;

device->VideoQuit = DIB_VideoQuit;

device->AllocHWSurface = DIB_AllocHWSurface;

device->CheckHWBlit = NULL
;

device->FillHWRect = NULL
;

device->SetHWColorKey = NULL
;

device->SetHWAlpha = NULL
;

device->LockHWSurface = DIB_LockHWSurface;

device->UnlockHWSurface = DIB_UnlockHWSurface;

device->FlipHWSurface = NULL
;

device->FreeHWSurface = DIB_FreeHWSurface;

device->SetGammaRamp = DIB_SetGammaRamp;

device->GetGammaRamp = DIB_GetGammaRamp;
#if SDL_VIDEO_OPENGL

device->GL_LoadLibrary = WIN_GL_LoadLibrary;

device->GL_GetProcAddress = WIN_GL_GetProcAddress;

device->GL_GetAttribute = WIN_GL_GetAttribute;

device->GL_MakeCurrent = WIN_GL_MakeCurrent;

device->GL_SwapBuffers = WIN_GL_SwapBuffers;
#endif

device->SetCaption = WIN_SetWMCaption;

device->SetIcon = WIN_SetWMIcon;

device->IconifyWindow = WIN_IconifyWindow;

device->GrabInput = WIN_GrabInput;

device->GetWMInfo = WIN_GetWMInfo;

device->FreeWMCursor = WIN_FreeWMCursor;

device->CreateWMCursor = WIN_CreateWMCursor;

device->ShowWMCursor = WIN_ShowWMCursor;

device->WarpWMCursor = WIN_WarpWMCursor;

device->CheckMouseMode = WIN_CheckMouseMode;

device->InitOSKeymap = DIB_InitOSKeymap;

device->PumpEvents = DIB_PumpEvents;

/*
Set up the windows message handling functions
*/

WIN_Activate = DIB_Activate;

WIN_RealizePalette = DIB_RealizePalette;

WIN_PaletteChanged = DIB_PaletteChanged;

WIN_WinPAINT = DIB_WinPAINT;

HandleMessage = DIB_HandleMessage;

device->free = DIB_DeleteDevice;

/*
We're finally ready
*/

return
device;

}

开始时为video driver分配内存，然后为相应的参数赋值，最最重要的就是为video driver的函数指针赋值，赋值成当前video driver的函数，以此实现我开始说的，以C语言实现类似面向对象的效果。

video driver的那一堆函数指针就像是抽象的接口，这里的函数就像是子类的实现。上层逻辑只需要使用video driver的指针并调用其中的函数即可，完全统一，并且不用关心指针具体是调用了哪个"子类“的函数。因为习惯了C++，我很少使用C语言来编写大规模的代码，所以对这些特性并不是非常熟悉，但是在C语言实现面向对象特性方面，我见过几派，我感觉这种方式算是比较好的，比完全使用宏来模拟C++的效果看上去要更加容易理解和自然。当然，因为C语言的确没有"标准"的面向对象实现方式，所以到底那个更好，也只能是见仁见智的问题了，估计也会像"大括号战争”一样没有休止。

此处还值得一提的是，SDL_VIDEO_OPENGL宏是默认开启的，也就是说，在Win32下使用GDI这个默认的video driver时，

SDL进行了
device->GL_LoadLibrary = WIN_GL_LoadLibrary;

device->GL_GetProcAddress = WIN_GL_GetProcAddress;

device->GL_GetAttribute = WIN_GL_GetAttribute;

device->GL_MakeCurrent = WIN_GL_MakeCurrent;

device->GL_SwapBuffers = WIN_GL_SwapBuffers;

这些函数的赋值。形成了对OpenGL的支持。这里与我以前了解的有些差异，因为我以前以为SDL在Win32下是默认使用DirectX加速的，现在看来并不是，就如侯捷所言，"源码面前了无秘密"，这些点点滴滴的东西，也算是看源码的一种收获。

然后，我查看了文档：
《SDL支持哪些系统平台？

》

有如下描述：

有两个版本，一个是适合所有基于Win32的系统的安全版本，另一个是基于DirectX的高性能版本。
安全版本的视频显示采用GDI。高性能版本采用DirectDraw，并支持硬件加速。
安全版本的音频回放采用waveOut API。高性能版本采用DirectSound。

这里可以看出，默认的时候SDL使用了Win32系统的安全版本。

此步初始化后，再利用video driver自己的VideoInit函数再次进行针对特殊的video driver的初始化。然后再开始SDL的事件线程（详细内容见上节）

然后，此时已经回到SDL_InitSubSystem函数了，此函数还需要进行一些其他模块的初始化，比如时间模块，摇杆等，这里就不多讲了。

看到这里，对于初始化部分的流程应该就比较清楚了，现在有个问题：

怎么改变SDL使用的video driver的默认值？比如，改成DirectX版本的。

从上面来看，有两种办法，

其一，改变bootstrap
数组中各driver的顺序，将directX的driver提到第一，那样默认就初始化directX版本了。

其二，让SDL_getenv("SDL_VIDEODRIVER"
)
返回directX版本driver的名字。

个人感觉方法二明显更加自然一些，感觉也是SDL作者提供的选择方案。那么，尝试一下，这里我通过SDL提供的接口SDL_putenv来设置环境变量，看看效果。

根据SDL_getenv的调用及前面查看的bootstrap的值，知道SDL查看的环境变量名为SDL_VIDEODRIVER，directX表示的driver名字为directx，所以在初始化前添加如下代码：

SDL_putenv("SDL_VIDEODRIVER=directx");

可以看到效果是以"directx"为第一参数调用SDL_VideoInit，并且进入了一下代码：

for
( i=0
; bootstrap[i]; ++i ) {

if
( SDL_strcasecmp(bootstrap[i]->name, driver_name) == 0
) {

if
( bootstrap[i]->available() ) {

video = bootstrap[i]->create(index);

break
;

}

}

此时，通过SDL_strcasecmp的调用，略过了GDI的video driver，然后使用了directX的driver。首先进入的available函数是：DX5_Available，晕了，DX5。。。。。什么年代的东西啊。。。。。。无语中。

在DX5_Available的调用中，仅仅通过以下语句判断了DINPUT.DLL和DDRAW.DLL动态库及DirectDrawCreate函数的存在，来判断DX5 driver是否可用。

DInputDLL = LoadLibrary(TEXT("DINPUT.DLL"));

DDrawDLL = LoadLibrary(TEXT("DDRAW.DLL"));

DDrawCreate = (void *)GetProcAddress(DDrawDLL, TEXT("DirectDrawCreate"));

同时，上述语句也说明，SDL使用的DirectX加速使用的是DX5.....并且使用的是DirectDraw，在那古老的年代，我不知道有没有D3D，不过对DDraw的使用倒是印证了我初看SDL渲染接口时的印象，抽象的接口与DDraw太像了。。。。。。。下面函数赋值的时候应该还能看到。

DX5_CreateDevice为SDL DirectX driver的创建函数，如同GDI版本一样对函数进行赋值。

/*
Set the function pointers
*/

device->VideoInit = DX5_VideoInit;

device->ListModes = DX5_ListModes;

device->SetVideoMode = DX5_SetVideoMode;

device->UpdateMouse = WIN_UpdateMouse;

device->CreateYUVOverlay = DX5_CreateYUVOverlay;

device->SetColors = DX5_SetColors;

device->UpdateRects = NULL
;

device->VideoQuit = DX5_VideoQuit;

device->AllocHWSurface = DX5_AllocHWSurface;

device->CheckHWBlit = DX5_CheckHWBlit;

device->FillHWRect = DX5_FillHWRect;

device->SetHWColorKey = DX5_SetHWColorKey;

device->SetHWAlpha = DX5_SetHWAlpha;

device->LockHWSurface = DX5_LockHWSurface;

device->UnlockHWSurface = DX5_UnlockHWSurface;

device->FlipHWSurface = DX5_FlipHWSurface;

device->FreeHWSurface = DX5_FreeHWSurface;

device->SetGammaRamp = DX5_SetGammaRamp;

device->GetGammaRamp = DX5_GetGammaRamp;
#if SDL_VIDEO_OPENGL

device->GL_LoadLibrary = WIN_GL_LoadLibrary;

device->GL_GetProcAddress = WIN_GL_GetProcAddress;

device->GL_GetAttribute = WIN_GL_GetAttribute;

device->GL_MakeCurrent = WIN_GL_MakeCurrent;

device->GL_SwapBuffers = WIN_GL_SwapBuffers;
#endif

device->SetCaption = WIN_SetWMCaption;

device->SetIcon = WIN_SetWMIcon;

device->IconifyWindow = WIN_IconifyWindow;

device->GrabInput = WIN_GrabInput;

device->GetWMInfo = WIN_GetWMInfo;

device->FreeWMCursor = WIN_FreeWMCursor;

device->CreateWMCursor = WIN_CreateWMCursor;

device->ShowWMCursor = WIN_ShowWMCursor;

device->WarpWMCursor = WIN_WarpWMCursor;

device->CheckMouseMode = WIN_CheckMouseMode;

device->InitOSKeymap = DX5_InitOSKeymap;

device->PumpEvents = DX5_PumpEvents;

/*
Set up the windows message handling functions
*/

WIN_Activate = DX5_Activate;

WIN_RealizePalette = DX5_RealizePalette;

WIN_PaletteChanged = DX5_PaletteChanged;

WIN_WinPAINT = DX5_WinPAINT;

HandleMessage = DX5_HandleMessage;

这里我们可以看到，相对GDI版本而言，除了速度之外，DirectX版本明显支持的特性更多，上面的函数指针赋值就没有GDI版本那么多NULL了，全部都有对应的函数。

最让人惊讶的时候，还是有OpenGL的函数。最后经过我测试，的确也是能够使用OpenGL。。。。。。

很显然，关键在于

SDL_Surface* screen = SDL_SetVideoMode( WINDOW_WIDTH, WINDOW_HEIGHT, 16, SDL_OPENGL);

一句的调用。

因为本文太长，在Google Document上输入都已经很卡了，所以留待下篇文章再看。

原创文章作者保留版权转载请注明原作者并给出链接

2010年07月24日

SDL源码阅读笔记（1）基本模块

前言

对于大牛来说，写关于阅读源码的文章都会叫源码剖析或者深入浅出啥的，对于我，自己阅读阅读源码，写一些自己的阅读笔记吧。

SDL我就不多介绍了，很多使用过的人都说很好，我自己实际使用的感觉
SDL也是非常成熟易用，绝对对得起其
simple两字。

基本模块

通过SDL.h中看到SDL作者对SDL进行的划分，可以看出SDL大概包含的内容：

#include

"SDL_main.h"

#include

"SDL_stdinc.h"

#include

"SDL_audio.h" //

声音

#include

"SDL_cdrom.h"

#include

"SDL_cpuinfo.h"

#include

"SDL_endian.h"

#include

"SDL_error.h"

#include

"SDL_events.h"

#include

"SDL_loadso.h" // Unix/Linux

动态库

#include

"SDL_mutex.h" //

多线程互斥量

#include

"SDL_rwops.h"

#include

"SDL_thread.h" //

多线程

#include

"SDL_timer.h" //

计时器

#include

"SDL_video.h" // video

模块

#include

"SDL_version.h"

有声音模块，cdrom模块，有事件模块，多线程模块，计时器模块，video模块等6大模块。

SDL_InitSubSystem的参数，可以看出SDL的作者将SDL划分为下列可选子系统：

#define

SDL_INIT_TIMER
0x00000001

#define

SDL_INIT_AUDIO
0x00000010

#define

SDL_INIT_VIDEO
0x00000020

#define

SDL_INIT_CDROM
0x00000100

#define

SDL_INIT_JOYSTICK
0x00000200

#define

SDL_INIT_NOPARACHUTE
0x00100000 /**< Don't catch fatal signals */

#define

SDL_INIT_EVENTTHREAD
0x01000000 /**< Not supported on all OS's */

#define

SDL_INIT_EVERYTHING
0x0000FFFF

这里的可选模块与包含的头文件并不是太一致。

除了声音我的确不是很了解以外，其他模块会在这里逐一来看看，因为个人爱好，将以video模块为主，当然，事实上这也应该是SDL中最重要的模块，虽然video模块的字面意义上是显示模块，但是实际上SDL主要的平台相关函数几乎都集中在了video模块中了。其中，对源码的最主要分析在于SDL是怎么使用C语言对各类接口进行抽象并实现跨平台的，并不会逐句逐句的理解，那样非常没有必要。当然，我不能理解所有SDL支持的平台，这里仅以我熟悉的3大平台为例，Win32,Unix/Linux,Macos，事实上这也是目前最为流行的平台，应该也算是最具代表性了。

计时器
(timer)

计时器和时间相关的东西是几乎每个有意义的游戏都会用到的，将其接口抽象出来并实现跨平台几乎是每个跨平台库的必要工作，相对来说还比较简单，这里以此作为第一篇，也算是热热身。

以下是SDL的timer.h头文件中有的计时器API：

extern

DECLSPEC
Uint32
SDLCALL
SDL_GetTicks
(void
);

extern

DECLSPEC
void
SDLCALL
SDL_Delay
(Uint32
ms
);

typedef

Uint32
(SDLCALL
*SDL_TimerCallback
)(Uint32
interval
);

extern

DECLSPEC
int
SDLCALL
SDL_SetTimer
(Uint32
interval
, SDL_TimerCallback
callback
);

typedef

Uint32
(SDLCALL
*SDL_NewTimerCallback
)(Uint32
interval
, void
*param
);

typedef

struct
_SDL_TimerID
*SDL_TimerID
;

extern

DECLSPEC
SDL_TimerID
SDLCALL
SDL_AddTimer
(Uint32
interval
, SDL_NewTimerCallback
callback
, void
*param
);

extern

DECLSPEC
SDL_bool
SDLCALL
SDL_RemoveTimer
(SDL_TimerID
t
);

个人感觉是没有什么值得学习的，叫100个人来设计计时器接口，基本99个与这个类似。无论是用过Unix/Linux还是用过Windows 计时器的人都可以对SDL的计时器API与相应平台的计时器接口对号入座。接口是简单，但是实现并不算简单，各个平台之间的计时器和时间函数还是有些差异。当然，作为C语言的跨平台库，首先要习惯的就是满篇满篇的宏了，这是C语言库跨平台的必要装备。

SDL_GetTicks

：

Win32主要由QueryPerformanceCounter或者timeGetTime实现。

Unix主要由clock_gettime或者更常见的gettimeofday实现。

MacOS下首先实现了一套FastTimer的函数，然后再调用这些函数实现，虽然我没有完全明白作者为什么不直接使用MacOS freeBSD相关的系统调用来实现，但是看了源代码感觉主要的问题在于现在MacOS都是64位的，所以作者需要进行一些处理。另外，还有PowerPC的MacOS部分，作者甚至使用了汇编来完成。

总的来说，很明显支持MacOS是最不容易的。。。。。假如作者原意在MacOS部分使用Objective C的代码的话，可能会好很多，但是估计作者是想尽量保持SDL简单的C库特征。

另外，此函数返回的并不是一般的从开机开始的计时，而是SDL自己计算的从SDL_StartTicks开始的计时。此函数在SDL的计时模块初始化的时候调用。

SDL_Delay：

Win32下是最清晰简单的函数，sleep而已。

Unix下有nano sleep的话调用nanosleep自然是最简单的，没有的话调用select来进行等待。当年看《Unix网络编程》的时候，作者用select实现了一个定时器，想不到还真有这样用的。

Macos下完全自己计时进行循环。。。。。。。这个应该是效率最低的了，不明白为啥这样做。

SDL_SetTimer，
SDL_AddTimer，
SDL_RemoveTimer：

我原以为每个平台都会有的函数

Win32完全靠计时线程加一个SDL自己的timerID列表来完成，不明白为什么不用Win32自己的Timer来完成。

Unix下用setitimer开始，也用setitimer结束。

MacOS下用InsXTime，PrimeTime开始，然后用RmvTime停止。

多线程模块

extern

DECLSPEC
SDL_Thread
* SDLCALL
SDL_CreateThread
(int
(SDLCALL
*fn
)(void
*), void
*data
);

#endif

extern

DECLSPEC
Uint32
SDLCALL
SDL_ThreadID
(void
);

extern

DECLSPEC
Uint32
SDLCALL
SDL_GetThreadID
(SDL_Thread
*thread
);

extern

DECLSPEC
void
SDLCALL
SDL_WaitThread
(SDL_Thread
*thread
, int
*status
);

extern

DECLSPEC
void
SDLCALL
SDL_KillThread
(SDL_Thread
*thread
);

多线程模块应该是最一致的模块了，Win32下分别上述接口在的一一对应的接口。

Unix,MacOS下使用pthread，接口也几乎一一对应，只是命名上有些差异，没有什么好说的。

这应该是最最简单的模块了。

事件模块

在事件模块中，SDL统一了所有的输入，将所有的输入最大的与上层逻辑解耦。

/** Event enumerations */

typedef

enum
{

SDL_NOEVENT
= 0, /**< Unused (do not remove) */

SDL_ACTIVEEVENT
, /**< Application loses/gains visibility */

SDL_KEYDOWN
, /**< Keys pressed */

SDL_KEYUP
, /**< Keys released */

SDL_MOUSEMOTION
, /**< Mouse moved */

SDL_MOUSEBUTTONDOWN
, /**< Mouse button pressed */

SDL_MOUSEBUTTONUP
, /**< Mouse button released */

SDL_JOYAXISMOTION
, /**< Joystick axis motion */

SDL_JOYBALLMOTION
, /**< Joystick trackball motion */

SDL_JOYHATMOTION
, /**< Joystick hat position change */

SDL_JOYBUTTONDOWN
, /**< Joystick button pressed */

SDL_JOYBUTTONUP
, /**< Joystick button released */

SDL_QUIT
, /**< User-requested quit */

SDL_SYSWMEVENT
, /**< System specific event */

SDL_EVENT_RESERVEDA
, /**< Reserved for future use.. */

SDL_EVENT_RESERVEDB
, /**< Reserved for future use.. */

SDL_VIDEORESIZE
, /**< User resized video mode */

SDL_VIDEOEXPOSE
, /**< Screen needs to be redrawn */

SDL_EVENT_RESERVED2
, /**< Reserved for future use.. */

SDL_EVENT_RESERVED3
, /**< Reserved for future use.. */

SDL_EVENT_RESERVED4
, /**< Reserved for future use.. */

SDL_EVENT_RESERVED5
, /**< Reserved for future use.. */

SDL_EVENT_RESERVED6
, /**< Reserved for future use.. */

SDL_EVENT_RESERVED7
, /**< Reserved for future use.. */

/** Events SDL_USEREVENT through SDL_MAXEVENTS-1 are for your use */

SDL_USEREVENT
= 24,

/** This last event is only for bounding internal arrays

* It is the number of bits in the event mask datatype -- Uint32

SDL_NUMEVENTS
= 32

} SDL_EventType
;

通过这个枚举，可以看到，除了输入，还包括一些系统事件，比如SDL_VIDEORESIZE和SDL_QUIT。

虽然说大部分以C语言实现的事件系统都实现不了类型安全以及订阅-发布的模式，所以都避免不了需要通过事件类型来决定事件的输入，并且进行强转的操作，然后形成一个很长的switch case，

但是SDL中的事件系统还算实现的不错了。

事件的参数是一个这样的联合结构：

/** General event structure */

typedef

union
SDL_Event
{

Uint8
type
;

SDL_ActiveEvent
active
;

SDL_KeyboardEvent
key
;

SDL_MouseMotionEvent
motion
;

SDL_MouseButtonEvent
button
;

SDL_JoyAxisEvent
jaxis
;

SDL_JoyBallEvent
jball
;

SDL_JoyHatEvent
jhat
;

SDL_JoyButtonEvent
jbutton
;

SDL_ResizeEvent
resize
;

SDL_ExposeEvent
expose
;

SDL_QuitEvent
quit
;

SDL_UserEvent
user
;

SDL_SysWMEvent
syswm
;

} SDL_Event
;

所以可以不进行强转，在相应的事件中，直接通过指定对应的成员变量来获取信息。虽然并不是完全类型安全，但是起码减少了强转的步骤。

事件模块有的API如下：

extern

DECLSPEC
void
SDLCALL
SDL_PumpEvents
(void
);

typedef

enum
{

SDL_ADDEVENT
,

SDL_PEEKEVENT
,

SDL_GETEVENT

} SDL_eventaction
;

extern

DECLSPEC
int
SDLCALL
SDL_PeepEvents
(SDL_Event
*events
, int
numevents
,

SDL_eventaction
action
, Uint32
mask
);

extern

DECLSPEC
int
SDLCALL
SDL_PollEvent
(SDL_Event
*event
);

extern

DECLSPEC
int
SDLCALL
SDL_WaitEvent
(SDL_Event
*event
);

extern

DECLSPEC
int
SDLCALL
SDL_PushEvent
(SDL_Event
*event
);

typedef

int
(SDLCALL
*SDL_EventFilter
)(const
SDL_Event
*event
);

extern

DECLSPEC
void
SDLCALL
SDL_SetEventFilter
(SDL_EventFilter
filter
);

extern

DECLSPEC
SDL_EventFilter
SDLCALL
SDL_GetEventFilter
(void
);

#define

SDL_QUERY
-1

#define

SDL_IGNORE
0

#define

SDL_DISABLE
0

#define

SDL_ENABLE
1

extern

DECLSPEC
Uint8
SDLCALL
SDL_EventState
(Uint8
type
, int
state
);

其中各个接口的含义还算比较好理解，与Win32的API中消息相关的接口类似，只是命名有差异而已。另外，事件模块本身的实现是与各个操作系统并不太相关的，属于依靠ANSI C跨平台的代码。

我用的最多的是SDL_PollEvent接口，比如在主循环中：

while
(running
) {

//While there's an event to handle

SDL_Event
event
;

while
( SDL_PollEvent
( &event
) ) {

if
(event
.type
== SDL_QUIT
) {

running
= false
;

}

这样来轮询事件。

这个最常用的API是由其他API实现的：

int

SDL_PollEvent
(SDL_Event
*event
)

{

SDL_PumpEvents
();

/* We can't return -1, just return 0 (no event) on error */

if
( SDL_PeepEvents
(event
, 1, SDL_GETEVENT
, SDL_ALLEVENTS
) <= 0 )

return
0;

return
1;

}

所以这里再看看SDL_PumpEvents()和SDL_PeepEvents：

SDL_PumpEvents主要就是调用显示模块的PumpEvent函数以获取上面那些与显示相关的事件，然后就是检测按键和摇杆了，其实很简单。

SDL_PeepEvents是事件模块中较为关键的函数，通过SDL_eventaction参数类型区别并完成

typedef

enum
{

SDL_ADDEVENT
,

SDL_PEEKEVENT
,

SDL_GETEVENT

} SDL_eventaction
;

这三类操作。添加事件，查看事件和获取事件。

看完API，来看看事件模块的内部：在内部，通过上述函数，其实都是操作同一个全局的事件列表：

static

struct
{

SDL_mutex
*lock
;

int
active
;

int
head
;

int
tail
;

SDL_Event
event
[MAXEVENTS
];

int
wmmsg_next
;

struct
SDL_SysWMmsg
wmmsg
[MAXEVENTS
];

} SDL_EventQ
;

并且，SDL通过自己的事件线程来维护事件系统的运作，在SDL_StartEventThread函数中启动了一个函数为SDL_GobbleEvents的事件线程。

此函数中是一个死循环（只要事件模块还是激活状态）以下是有删节的主要内容：

while
( SDL_EventQ
.active
) {

SDL_VideoDevice
*video
= current_video
;

SDL_VideoDevice
*this
= current_video
;

/* Get events from the video subsystem */

if
( video
) {

video
->PumpEvents
(this
);

}

/* Queue pending key-repeat events */

SDL_CheckKeyRepeat
();

#if

!SDL_JOYSTICK_DISABLED

/* Check for joystick state change */

if
( SDL_numjoysticks
&& (SDL_eventstate
& SDL_JOYEVENTMASK
) ) {

SDL_JoystickUpdate
();

}

#endif

if
( SDL_timer_running
) {

SDL_ThreadedTimerCheck
();

}

SDL_Delay
(1);

}

可以看到主要是调用显示模块的PumpEvents来获取显示系统相关的事件，其次就是重复按键的事件检测和摇杆了。另外，可以看到前面那个全局事件列表是带互斥量的，事实上，整个SDL的事件系统的实现都是线程安全的。
SDL_SetEventFilter等事件过滤的函数，实现非常简单，就是根据设置的回调函数的结果来决定事件是否添加到事件列表，就不多说了。

事实上，虽然各类输入最后都统一归结到SDL的事件模块中，然后提供给用户或者SDL本身进行处理，但是在SDL中将这些输入检测本身都放在了video模块中。所以这里暂时不讲它们的实现了。

小结：

以一般看源码一边记录下来的方式完成本文，基本上将SDL除Video以外的一些周边模块都看了一遍，除了事件模块，这些模块的编写都没有太多值得深入了解的东西，无非就是抽象出一个大概的API，然后在不同的平台上实现，相当于SDL将很多平台相关的dirty的工作都做了，剩下clean的跨平台接口供用户使用。事件模块本身就不是平台相关的，SDL的实现相对来说使用还是比较方便的。利用联合来减少强转虽然不是第一次见，但是还是比更常见的void*表示event data+强转更加方便。看得出SDL的用心设计。

因为这些周边模块主要抽象一些接口，然后实现，没有太多亮点，所以看的时候有的时候都不知道该写什么，所以按照自己看源码的流程记录了一些琐碎的东西，全文比较混乱。

准备下篇文章中讲述SDL最关键的video模块，相对来说，就比这些周边模块有意思的多。

原创文章作者保留版权转载请注明原作者并给出链接