代码如下：

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性能是怎样的，一秒钟能计算多少次？