代碼如下：

template <typename T>
class foo
{
public:
    class bar
    {
    public:
        bar() {}
        bar(const bar &) {}
        bar(int) {}
        operator T *() const
        {
            return 0;
        }
        bar operator + (int)
        {
            return *this;
        }
    };
};

int main()
{
    foo<int>::bar f;
    size_t i = 1;

    f + i;

    return 0;
}

注意：外層 class foo 和 template 都不能去掉。

這個代碼應該通過編譯么？還是應該報operator +匹配歧義？

實際應用中有時候會遇到需要處理 ZIP 壓縮解壓的情況，這時候我們有大概三種選擇：

1. 調用 rar.exe, unzip.exe 等
2. 使用某現成庫
3. 完全手寫

第一種雖然能完成任務，但是沒法知曉結果。曾經有人對說，可以抓命令行輸出結果來判斷……這種依靠界面文字來進行精確判斷的行為個人認為相當不靠譜。第三種，既然我是個“造輪主義”者，當然說好，但是現在我不了解 ZIP 格式，也不了解 ZIP 算法，所以這個日后再說。今天我們就來切切實實地用一次輪子。

ZIP 相關的庫中比較有名的可能就是 ZLib 和 InfoZip（unzip60）了。InfoZip 我了解的不多，其外層接口似乎也不大好，一堆回調——回調是個很煩人的東西，專門用來打亂代碼結構。另外，這個庫也已經有好多年沒更新了吧，太久的東西給人的感覺總是不太舒服。ZLib 最新版本是 1.2.5，今年 4 月 19 日出的。確切的說，ZLib 可能并不是一個針對 ZIP 文件的庫，它只是一個針對 gzip 以及 deflate 算法的庫。它提供了一個叫做 minizip (contrib\minizip) 例子來給出操作 ZIP 文件的方法。下文將從 ZLib 出發，歸結出兩個傻瓜接口：

BOOL ZipCompress(LPCTSTR lpszSourceFiles, LPCTSTR lpszDestFile);
BOOL ZipExtract(LPCTSTR lpszSourceFile, LPCTSTR lpszDestFolder);

要引入的源文件

1. ZLib 主目錄下的代碼，除 minigzip.c、example.c 外；
2. contrib\minizip 下的代碼，除 minizip.c、miniunz.c 外。

相關 API

雖然 minizip 更像是個例子，但是除去其主程序 minizip.c 和 miniunz.c 后，剩下的部分我們可以看作是 ZLib 的一個上層庫，它封裝了與 ZIP 文件格式相關的操作。而 minizip.c 和 miniunz.c 就是我們要改寫的——把它從命令行程序改為上述傻瓜接口。minizip.c 和 miniunz.c 中用到的 API 主要有：

壓縮相關：

1. zipOpen64
2. zipClose
3. zipOpenNewFileInZip
4. zipCloseFileInZip
5. zipWriteInFileInZip

解壓相關：

1. unzOpen64
2. unzClose
3. unzGetGlobalInfo64
4. unzGoToNextFile
5. unzGetCurrentFileInfo64
6. unzOpenCurrentFile
7. unzCloseCurrentFile
8. unzReadCurrentFile

想必看到這些名字都能猜到怎么用了吧。好的接口果然能帶給人愉悅的。minizip 中的這些函數有的是帶“64”的有的是不帶的，有的還有“2”、“3”、“4”版本。這里一律用帶 64 的，不帶“2”、“3”、“4”的。

具體操作

下文涉及的所有操作，其相關代碼都可以在 http://zlibwrap.codeplex.com/ 上找到（Change Set 2450）。這里就不貼長篇代碼了。另外有個 DLL版本 和 Lib版本，供拿來主義者用。

首先是壓縮操作。使用 zipOpen64 來打開/創建一個 ZIP 文件，然后開始遍歷要被放到壓縮包中去的文件。針對每個文件，先調用一次 zipOpenNewFileInZip，然后開始讀原始文件數據，使用 zipWriteInFileInZip 來寫入到 ZIP 文件中去。zipOpenNewFileInZip 的第三個參數是一個 zip_fileinfo 結構，該結構數據可全部置零，其中 dosDate 可用于填入一個時間（LastModificationTime）。它的第二個參數是 ZIP 中的文件名，若要保持目錄結構，該參數中可以保留路徑，如 foo/bar.txt。

解壓操作稍微復雜一點點。打開一個 ZIP 文件后，需要先使用 unzGetGlobalInfo64 來取得該文件的一些信息，來了解這個壓縮包里一共包含了多少個文件，等等。目前我們用得著的就是這個文件數目。然后開始遍歷 ZIP 中的文件，初始時自動會定位在第一個文件，以后處理完一個后用 unzGoToNextFile 來跳到下一個文件。對于每個內部文件，可用 unzGetCurrentFileInfo64 來查內部文件名。這個文件名和剛才 zipOpenNewFileInZip 的第二個參數是一樣的形式，所以有可能包含路徑。也有可能會以路徑分隔符（/）結尾，表明這是個目錄項（其實壓縮操作的時候也可以針對目錄寫入這樣的內部文件，上面沒有做）。所以接下來要根據情況創建（多級）目錄。unzGetCurrentFileInfo64 的第三個參數是 unz_file_info64 結構，其中也有一項包含了 dosDate 信息，可以還原文件時間。對于非目錄的內部文件，用 unzOpenCurrentFile，打開，然后 unzReadCurrentFile 讀取文件內容，寫入到真實文件中。unzReadCurrentFile 返回 0 表示文件讀取結束。

局限性

1. 只能壓縮、解壓采用 deflate 算法的 ZIP 文件。（不過此類 ZIP 應該占了絕大多數）
2. 由于 minizip 中相關 API 的限制，以及 ZIP 文件格式的限制，被壓縮/解壓的相關文件名必須與系統的當前代碼頁相符合。（雖然 ZIP 格式最近一次更新加入了使用 UTF8 編碼文件名的選項，但是不能保證所遇到的 ZIP 文件都是新格式的，minizip 中似乎也沒有針對此選項做什么動作。）

尾聲

這是一篇低俗的文章，沒有什么思想性。僅僅是一個小記。有不當之處歡迎批評指正。

 

祝大家中秋節快樂！

當耦合很多、多到無法解的時候，人們便將其整理一番，用文檔記下來，稱之為“協議”、“規范”或者“標準”，供后人學習參考。后人在看這些文檔化的耦合的時候，便不怎么容易覺得那是耦合。。。

反過來講，如今的“協議”“標準”所涉及到的內容，其實都是耦合聚集的地方……

不成熟的想法。歡迎板磚。

近來遇上一個很詭異的 bug：InternetOpenURL 內部發生 crash。雖說發生問題的時刻總是處于這個 API 內部，可也一直不敢確定不是其他原因引起的，就這么一直拖著。

前兩天終于有可以隨時操作的且重現幾率非常高的機器了，測試了一下，發現一個規律：只要在調用 InternetOpenURL 之前調用過 SHGetFolderPath，此問題的重現幾率就非常高；如果沒有調用過 SHGetFolderPath，則基本不出現。

目前網上找到的一個幾乎唯一的帖子是 http://social.msdn.microsoft.com/forums/en-US/vcgeneral/thread/2982efc6-8403-4577-9dba-ad5cfdf01753，現象幾乎一模一樣。只可惜沒有有價值的回復。該文章的作者指出的 VPN 等網絡原因好像不是關鍵，在我這里是很普通的局域網，一樣能出現。

測試代碼如下：

#include <Windows.h>
#include <tchar.h>
#include <ShlObj.h>

#include <WinInet.h>
#pragma comment(lib, "wininet.lib")

#define URL _T("http://www.baidu.com/")

int main()
{
    TCHAR szCommonAppData[MAX_PATH];
    SHGetFolderPath(NULL, CSIDL_COMMON_APPDATA, NULL, SHGFP_TYPE_CURRENT, szCommonAppData);

    HINTERNET hInternet = InternetOpen(_T("WCU"), INTERNET_OPEN_TYPE_PRECONFIG_WITH_NO_AUTOPROXY, NULL, NULL, 0);

    if (hInternet == NULL)
    {
        return 0;
    }

    HINTERNET hInternetFile = InternetOpenUrl(hInternet, URL, NULL, 0, INTERNET_FLAG_NO_UI | INTERNET_FLAG_RELOAD, 0);

    if (hInternetFile == NULL)
    {
        InternetCloseHandle(hInternet);
        return 0;
    }

    InternetCloseHandle(hInternetFile);
    InternetCloseHandle(hInternet);

    return 0;
}

在能夠出現此問題的機器上，Ctrl + F5 直接運行，幾乎每次必現；如果 F5 調試運行，則幾率小一點，但是跑個七八次左右基本上能出現。目前 XP 32/64 上都有發現這個問題，Vista/Win7 上暫時沒有發生此現象。（如果 InternetOpenURL 換成 InternetConnect、HttpOpenRequest、HttpSendrequest，則會 crash 在 HttpSendRequest 內。）

附件是一個測試工程，附帶上了 Debug、Release 版本的 EXE、PDB 文件以及 Crash 時的 Dump 文件。請有心人幫忙看看。^_^
點擊下載

可是，如果這個問題確實存在，為什么網上查到的相關內容這么少呢？奇怪~

好久沒寫了。這次寫前一陣子的一個大整數類，順便請教幾個問題。

目標很簡單，就是實現大整數的基本算術運算。

首先，是數據存儲方式問題。簡單明了點可以用直接的數字字符串，但缺點是，一個字節256個信息點只用了10個（或16個，如果用16進制的話），浪費空間，而且增大了數據規模。于是考慮用盡空間，使用整個 unsigned int 作為一個單位，也就是 2^32 進制。定義如下：

template <typename T>
class BigIntT
{
protected:
    Array<T> m_aValue;
};

之所以搞了個 template，一是裝B，二是為了模板而模板——沒有 cpp，直接 include，使用方便。然后定義一個默認的特化：

typedef BigIntT<unsigned int> BigInt;

注意這里的 T 不用 unsigned long long，是有原因的（為了方便乘法實現，見下文）。實際上如果有模板約束，我希望 T 被限制為 unsigned int, unsigned short, 以及 unsigned char。

另外，這里的數據長度將不做限制，也就是這個大數可以是任意有限的大小。各個 unsigned int 的順序是低位在前，高位在后——這樣，正好與 PC 機上的字節順序一致，于是，整塊內存布局看上去就是支持這么多字長的機器上的一個大數的內存。

我想過兩種實現方式。一個是固定長度，也就是通過模板參數或者別的什么，限制其長度，也搞符號位、溢出、移位等，然后想點技巧讓兩個 BigInt<100> 相乘返回 BigInt<200>；二是現在的，不限長度，另有變量作為符號標記，不提供移位操作，偏算術方向。

之后，是數學運算的實現。雖然都是些小操作，但是數字一大，性能瓶頸會很突出，特別是乘除。

（完整代碼見：http://xllib.codeplex.com/SourceControl/changeset/view/1689#1160）

一、加。

加法實現很直接，就是各位相加——同號的情況。每一位如果有溢出，就在后一位加1。這里指的一“位”，是指一個數據單位 T，也就是一個 unsigned int，下同。如果遇到異號的兩個數，把球踢給減法。

二、減。

減法也比較直接。如果兩數同號，且是大的減小的，就一位一位減。碰到有溢出的，下一位減去1。最后清除所遇的0。如果是小的減大的，就換過來減，改變下結果的符號；如果兩數異號，把球踢給加法。

至此，加減實現完畢。

三、乘。

乘法的實現大致有三種：硬乘、分治法以及利用離散傅里葉變換。

由于對后兩種的理解不足，現采用硬乘法。硬乘的道理很簡單，就是小時候打豎式的算法（前面的加法減法也是打豎式）。被乘數的第 i 位和乘數的第 j 位的結果，要加在乘積的第 i + j 位。值得注意的是，這里每一位的乘法我用的是默認的內置類型的乘法，于是出現了上文要求，T至多只能為unsigned int，以保證這里的臨時結果可以用一個unsigned long long 存下。

請教各位關于分治法以及FFT法。1、分治法看上去多了好些加減法，它帶來的好處的前提是加減法實現的很好，可是按上面的加減法，似乎帶不來什么好處（實際測過結果很糟，不知是否我做得不對）。2，FFT法本身我沒弄很明白（很慚愧，數學系的，卻從來沒有會過傅里葉變換，是從來沒有過，不是曾經會過現在忘了= =），不過有個疑問，FFT以及iFFT的過程本身難道不耗性能嗎？

四、除和模。

除法其實也是打豎式，其實到這里為止滿篇都是打豎式，哈。除法的麻煩之處是有個試商過程，試商的時候還要乘一下，看上去會很不理想。為了避免一個一個試，很自然的一個優化方法是二分，對于unsigned int 一個單位的數來說，每個單位至多會嘗試32次，然后會有32次大數乘，32次大數比較。測試的情況是，對于不是特別大的數，還算馬馬虎虎過得去。

嘗試過另外一個方式，那就是另一個極端，用真實的“位”為單位去“試商”——其實不用試，是1是0直接知道了。以為會好一些，實際上更差。初步想了想，一個原因，數據規模沒變，二分試商的時候是 32 * n，現在還是 32 * n，原來的32是32次二分，現在的32是一個單位內的32次移位。除此之外，原生的unsigned int的乘除法沒有被利用起來。不知是否？

后來又想到一個方法，其實不用這么多次試商，試一兩次就夠了，關鍵是利用原生的除法。比如，8000除以213，如果我們事先已經知道了一位數的除法，在算百位上的上的時候，我們會直接考慮8除以2是多少，于是直接考慮商4，然后再算下21*4有沒有超過80，有的話就把商減1，商3。這個時候只進行了一次大數乘法，而商已經基本確定了。除數個位上的3，以及更低位（如果還有）上的數，即便有進位，也會加到十位，而十位的加法對百位的影響只有1，已經很難構成對最后的商的影響了。到這里，將這個數位上的商和整個除數乘起來（如果還是比被除數大，就再減一），于是這位上的上確定了。測試結果，跟二分試商相比，在2048bit級別的大數上，快了8-10倍左右。

模和除基本沒什么區別，只是返回的東西不一樣。

五、冪和模冪。

對于冪的實現，也用二分的思想。比如計算 a 的 10 次方，可以轉化成先算 a 的 5 次方，然后自乘一次。a 的 5 次方，可以轉化成先算 a 的 2 次方，然后自乘、再乘一次 a。a 的 2 次方，就是自乘一次。最后，變成：

((a ^ 2) ^ 2 * a) ^ 2，或者看成 (((1 ^ 2 * a) ^ 2) ^ 2 * a) ^ 2

然后觀察指數 10 的二進制表示：1010

規律是，以 1 為起始，從高位到低位看指數，遇到1就平方再乘底數，遇到0就單單平方。

至于模冪，就在每次平方前/后，把底數模一下，保證參與乘法的兩個數都是“不太大”的。

 

以上，僅介紹我是怎么做的。至于對錯、有沒有更好做法，望各位不吝賜教。

 

最后，做了個簡單的性能測試——做RSA運算：
（plain = 12345; encoded = 0; decoded = 0;）
計算以下兩行的運行時間。
encoded = plain.ExpMod(d, n);
decoded = encoded.ExpMod(e, n);

在我機器（Win7 32bit，Intel E5200 沒超頻）上的測試結果如下——

512位：0.040s.
1024位：0.250s.
2048位：1.495s.

2048位的情形，已經有很明顯的等待了。不知道一般來說現在2048bit的RSA性能是怎樣的，一秒鐘能計算多少次？