Terark & Topling 创始人雷鹏 | 没有上限，只有突破

本网站仅单台服务器: 2核2G 99￥包年，集成兼容 MySQL 的 MyTopling 高压缩高性能数据库

本网站仅单台服务器: MyTopling 2核2G 99￥包年

当搜索词中有错别字时，搜索引擎会尝试纠错

通过相似拼音纠错

搜索引擎把这些字还原成拼音，用一个拼音相同的已知的搜索词代替。

这是一种众所周知的纠错策略，但是，当输错的字是多音字，特别是有多个这样的错误输入时，所有的搜索引擎都尽量绕开这个问题，或者仅使用最常用的那些音去纠错。因为要考虑所有可能的拼音组合，在极端情况下会导致指数爆炸！例如某互联网大厂的实现(枚举多音字全排列)。

基于自动机的算法可以完美解决这个指数爆炸问题

这是自动机应用的又一个绝佳范例，作为演示，这个页面只收录了 800万 条 搜索词+词频，数据也不太干净
该算法全部在内存中运行，使用了 293M 内存，这个数据量，如果用传统方法暴力实现，并且达到这个性能，需要 几十G 的内存
暴力方法是 Query 越长越可怕，该算法则是 Query 越长，优势越大
纠错耗时仅供参考(2核2G 99￥包年)，如果你看到搜索耗时过长，很可能是 mmap 数据被 swap 到了硬盘上，再搜索一次会得到客观的搜索耗时

这个算法也可以用来解决用户输入预测(智能提示)功能

用户只输入Query开头部分，就自动提示出整个Query，例如用户输入举头望，就提示出举头望明月。就像现在各种搜索引擎做的那样。

基于编辑距离的纠错

在已知的搜索词中寻找编辑距离与用户 Query 最小的词，使用我的算法也可以高效解决（还没做演示页面）

创建 DFA Key 与搜索 DFA Key 的耗时包含了收集网页展示需要的信息，耗时占比90%以上！

高性能文件系统实现

作者: rockeet 发表日期: 2005年11月03日分类: 操作系统评论: 0 条阅读次数: 2,078 次

	高性能文件系统-演示文档
	PowerPoint下载

	演示文档首页
	Word Doc 文档下载
	Fat 文件系统规格白皮书

文件系统的两种实现

标题	高性能文件系统（该页文档描述）	最小实现
可扩展性	优良（基于虚拟文件系统构架）	无
时间性能	优良，接近硬件极限速度，可用于驱动硬盘	差，仅可用于驱动存储卡片
空间性能	较大， Rom(Code)30K , Ram(RunTime) >= 32K	Rom(code) < 8KRam(RunTime) >=2K
支持	Fat12/Fat16/Fat32 ，长文件名	Fat12/Fat16 ，仅 8.3 文件名
支持	可自定义路径解析	Fat12/Fat16 ，仅 8.3 文件名
其它特点	对连续簇编组，不用 FatCache	FatCache

	源码下载：
	高性能文件系统（ PowerPoint 文档描述）
	最小实现
	一个国外的Fat文件系统（使用的是 FatCache ，不是对连续簇编组）

这些源码任何人可以自由下载，自由改动，
但我对此不提供技术支持，如果需要支持，请联系我们！

C++使用模板进行的一种重构

作者: rockeet 发表日期: 2005年11月03日分类: C++ 评论: 0 条阅读次数: 2,138 次

如果有一些遗留代码，里面有很多结构，定义了一些相同的成员，但在一些时候，需要取出这些成员，进行同样的处理。如下面这些代码的红色部分。

——原先的程序结构是使用类型码来区分实际的类型，客观地说，这些遗留代码是比较混乱的。

不想说太多，用简单的代码来说明问题吧。

typedef struct   _EVT_SWITCH : public EVT_HEAD {
DWORD dwCategory;
DWORD dwSeverity;
DWORD dwEvtSrcID;
DWORD dwEvtSrcOffset;
DWORD   dwSrcIp;
DWORD   dwSrcPort;
DWORD   dwDstIp;
DWORD   dwDstPort;
DWORD   dwProtocol;
DWORD dwEvtUserOffset;
DWORD   dwEvtUserIp;
DWORD dwStatus;
DWORD   dwOp;
DWORD dwEvtNum;
DWORD dwDetailOffset;
CHAR szContent[0];
}EVT_SWITCH,*PEVT_SWITCH;

typedef struct   _EVT_ROUTER : public EVT_HEAD {
DWORD dwCategory;
DWORD dwSeverity;
DWORD dwEvtSrcID;
DWORD dwEvtSrcOffset;
DWORD   dwSrcIp;
DWORD   dwSrcPort;
DWORD   dwDstIp;
DWORD   dwDstPort;
DWORD   dwProtocol;
DWORD dwEvtUserOffset;
DWORD   dwEvtUserIp;
DWORD dwStatus;
DWORD   dwOp;
DWORD dwEvtNum;
DWORD dwDetailOffset;
CHAR szContent[0];
}EVT_ROUTER,*PEVT_ROUTER;

typedef struct _EVT_NETWORK : public EVT_HEAD {
DWORD dwCategoryOffset;
DWORD dwSeverity;
DWORD dwEvtId;
DWORD dwEvtSrcOffset;
DWORD dwEvtUserOffset;
DWORD dwEvtTypeOffset;
DWORD dwSrcIp;
DWORD dwSrcPort;
DWORD dwDstIp;
DWORD dwDstPort;
DWORD dwProtocol;
DWORD dwSmacOffset;
DWORD dwDmacOffset;
DWORD dwFlagOffset;
DDWORD ddwInB,ddwOutB,ddwInPkt,ddwOutPkt;
DDWORD ddwSessionId;
DWORD dwRuleOffset;
DWORD dwStatusOffset;
DWORD dwOpOffset;
DWORD dwReasonOffset;
int tDuration;
DWORD dwEvtNum;
DWORD dwArgOffset;
DWORD dwMsgOffset;
DWORD dwDetailOffset;
CHAR szContent[0];
}EVT_FW,*PEVT_FW,EVT_NETWORK,*PEVT_NETWORK;

typedef struct _EVT_VPN : public EVT_HEAD {
int tDuration;
DWORD dwCategoryOffset;
DWORD dwSeverity;
DWORD dwEvtId;
DWORD dwEvtSrcOffset;
DWORD dwEvtUserOffset;
DWORD dwEvtTypeOffset;
DWORD   dwDevActionOffset;
DWORD dwDevMoudleNameOffset;
DWORD dwServiceOffset;
DWORD dwSrcIp;
DWORD dwSrcPort;
DWORD dwDstIp;
DWORD dwDstPort;
DWORD dwProtocol;
DWORD dwSmacOffset;
DWORD dwDmacOffset;
DWORD dwTargetUserIDOffset;
DWORD dwTargetDomainOffset;
DWORD dwMessageIDOffset;
DWORD dwTunnelOffset;
DWORD dwInterfaceOffset;
DWORD   dwMmemonicOffset;
DWORD dwFlagOffset;
DDWORD ddwInB,ddwOutB,ddwInPkt,ddwOutPkt;
DDWORD      ddwSessionId;
DWORD dwStatusOffset;
DWORD dwOpOffset;
DWORD dwReasonOffset;
DWORD dwEvtNum;
DWORD   dwArgOffset;
DWORD dwMsgOffset;
DWORD dwDetailOffset;
CHAR szContent[0];

}EVT_VPN,*PEVT_VPN;

typedef struct _EVT_SECURE : public EVT_HEAD {
DWORD dwCategoryOffset;
DWORD dwSeverity;
DWORD dwEvtTypeOffset;
DWORD dwEvtSrcOffset;
DWORD dwEvtUserOffset;
DWORD dwSrcIp;
DWORD dwSrcPort;
DWORD dwDstIp;
DWORD dwDstPort;
DWORD dwProtocol;
DWORD dwFlagOffset;
DDWORD ddwInB,ddwOutB,ddwInPkt,ddwOutPkt;
DDWORD ddwSessionId;
DWORD dwRuleOffset;
DWORD dwStatusOffset;
DWORD dwOpOffset;
DWORD dwReasonOffset;
DWORD dwEvtId;
DWORD dwEvtNum;
DWORD dwSignatureOffset;
DWORD dwDetailOffset;
CHAR szContent[0];
}EVT_SECURE,*PEVT_SECURE;

这些类型实际上是同一类类型，实际上可以从同一个类派生，使用 PullUp Member 方法重构。但是这些结构已经发布，不可能施行这种重构。可以这样：

class CEventWrapper
{
public:
CEventWrapper(PEVT_HEAD p) { m_p = p; }

struct NetInfo
{
  DWORD dwDstIp;
  DWORD dwDstPort;
  DWORD dwSrcIp;
  DWORD dwSrcPort;
  DWORD dwProtocol;
  TCHAR szDstMac[20];
  TCHAR szSrcMac[20];
};
BOOL GetNetInfo(NetInfo* p) const;
template static void
  TemplateGetNetInfo(CEventWrapper::NetInfo* netInfo, const T& x)
{
  netInfo->dwDstIp  = x.dwDstIp;
  netInfo->dwDstPort = x.dwDstPort;
  netInfo->dwSrcIp  = x.dwSrcIp;
  netInfo->dwSrcPort = x.dwSrcPort;
  netInfo->dwProtocol = x.dwProtocol;
}

BOOL HasNetInfo() const;

private:
PEVT_HEAD m_p;
};

BOOL CEventWrapper::HasNetInfo() const
{
NetInfo ni;
return GetNetInfo(&ni);
}

BOOL CEventWrapper::GetNetInfo(NetInfo* netInfo) const
{
memset(netInfo, 0, sizeof(NetInfo));

switch (m_p->dwLogFrt)
{
default:
  ASSERT(0);
  return FALSE;
case DIAL_LOG:
case WEBTRENDS_LOG:
case SNORT_LOG:
case SENDMAIL_LOG:
case SYSLOG:
case NETSCREEN_LOG:
case WIN_FILE_LOG:
case WIN_PROCESS_LOG:
case APACHE_ERROR_LOG:
case IP_MON_LOG:
case IP_UP_LOG:
case PROC_MON_LOG:
case GENERAL_MON_LOG:
case PERF_MON_LOG:
case PORTMON_LOG:
  ASSERT(0);
  return FALSE;

case EVENT_LOG: return FALSE;

case CP_LOG:
  TemplateGetNetInfo(netInfo, *(EVT_VIRUS*)(m_p + 1));
  return TRUE;
case VPN_LOG:
  TemplateGetNetInfo(netInfo, *(EVT_VPN*)(m_p + 1));
  return TRUE;

case SECEXPERT_LOG: return FALSE;

case IIS_FTP_LOG:  return FALSE;
case EXCHANGE_LOG:  return FALSE;
case FW_LOG:
  {
   EVT_FW* p = (EVT_FW*)(m_p + 1);
   TemplateGetNetInfo(netInfo, *p);
   if (p->dwDmacOffset)
    lstrcpyn(netInfo->szDstMac, p->dwDmacOffset + (char*)p,
     dimof(netInfo->szDstMac));
   if (p->dwSmacOffset)
    lstrcpyn(netInfo->szSrcMac, p->dwSmacOffset + (char*)p,
     dimof(netInfo->szSrcMac));
   return TRUE;
  }
case DOMINO_HTTP_LOG:
case APACHE_LOG:
case IIS_HTTP_LOG:
  return FALSE;

case CISCO_PIX_LOG:
case CISCO_IOS_LOG:
case CISCO_SWITCH_LOG:
case HUAWEI_SWITCH_LOG:
case NORTEL_SWITCH_LOG:
TemplateGetNetInfo(netInfo, *(EVT_SWITCH*)(m_p + 1));
return TRUE;

case SQLSERVER_LOG:
case ORACLE_LOG:
case MYSQL_LOG:
return FALSE;

case KIDS_LOG: case IDS_LOG:
TemplateGetNetInfo(netInfo, *(EVT_SECURE*)(m_p + 1));
return TRUE;
}
ASSERT(0);
return FALSE;
}

C语言垃圾代码清除工具(含源码)

作者: rockeet 发表日期: 2005年11月03日分类: C++ 评论: 0 条阅读次数: 2,367 次

CodeClean 使用说明

1. 说明

工程中有许多垃圾代码，CodeClean能识别的垃圾代码指从入口不可达的垃圾函数和全局变量。CodeClean 可以扫描出所有这类代码，从扫描垃圾的角度，未对函数和全局变量未做区别。

有很多函数和全局变量被其它的函数或全局变量引用到，但引用它的函数（或全局变量）从入口是不可达的，这样的函数（或全局变量）称它为 Island。

本程序仅扫描C语言（不包括C++）的垃圾代码。本程序不对C语言程序进行预处理（忽略了“#”开头的行），对宏调用不做特别处理，将它看作是一个普通的函数调用。

对于已知的未使用的变量，或函数（如这些变量或函数在汇编语言程序中使用）。为防止他们被清除掉，可以定义一个哑宏，如：

#define DUMMY_REFER(X)

在某个（已知的）从入口可达的函数（非垃圾函数）中引用该变量（或函数）即可。如：

Void main()

{

…..

DUMMY_REFER(MyPredefinedFunction);

…..

}

2. 命令行

CodeClean options

options: /Fxxx option default is output file name

island object is an object which is not reachable by ‘main’,

but was refered by another object.

/Fmake [make file name(input file, list of input source file names)]

/Fgarbage [garbage object list file name]

/Fisland [island object file name]

/Ferror [error message output file name]

/Fcall [call graph file name]

/Dcall [max call graph depth (default is 32)]

/Ncall [max callees number each object’s call graph (default is 32)]

/Fcaller [caller graph file name]

/Dcaller [max caller graph depth (default is 32)]

/entry [entry point name (default is ‘main’)]

/allcaller (list all callers of each object, in spite of found ‘main’ or not)

/cleancode (generate clean code)

/onlyzero (only list zero refered object to garbage object file)

/tomain (list any callers of each object until found ‘main’ function)

/entrystop (same as ‘tomain’)

/? or /H or /h (show this help message)

3. 命令行详解

以 [ ] 括起来的地方，表示这里必须要有一个参数――如果有前面的 /xxxx 选项。

/Fmake [输入文件名，其中包含 *.C文件名列表，每行一个文件]

/Fgarbage [输出文件名，扫描出的垃圾对象列表]

/Fisland [输出文件名，扫描出的“island”对象列表]

/Ferror [输出文件名，扫描过程中的显示信息，默认是Consol屏幕]

/Fcall [对象调用图（从上往下）]

/Dcall [每个对象调用图的最大深度(默认是 32)]

/Ncall [每个对象调用图的最多只列出的调用对象的数目，默认列出全部]

/Fcaller [对象被调图（从下往上）]

/Dcaller [每个对象被调图的最大深度(默认是 32)]

/entry [入口函数的名字，默认是”main”]

/allcaller (列出每个对象的所有调用者，不管是否搜索已到入口)

/cleancode (生成干净代码，生成的干净代码与原代码在同一目录下，以 .cxx 为后缀名)

/onlyzero (仅列出未被使用的对象，不列出 “island”对象)

/tomain (被调图碰到入口函数就停止)

/entrystop (与‘tomain’相同)

/? or /H or /h (显示这个帮助信息)

例：

CodeClean /tomain /entry MyMain /Fmake make.mak /Fgarbage garbage.txt /Fcaller caller.txt /Fcall call.txt

生成垃圾对象列表和被调图及调用图，其中 ‘MyMain’ 是入口函数名， make.mak 是输入文件名，其中包含要扫描的文件名列表．．．

一个可能的 Mak 文件内容如下：

kernel/oss/kernel.c

kernel/oss/osinit.c

kernel/oss/os_err.c

kernel/oss/os_msg.c

kernel/oss/os_oem.c

kernel/oss/os_stat.c

kernel/oss/os_synch.c

kernel/oss/schtmr.c

4. 程序

如果您的VC（或其它编译环境）安装了STLPort，您可以定义__USE_HASP_MAP宏以便编译出最快的代码。

使用__USE_HASP_MAP，在Windows2000，P42.8，512M内存环境下，扫描2M代码只需要5秒！如果再生成去除垃圾后的干净代码，也只需要10秒钟。连我自己都对这个速度感到惊异！

源码下载

程序下载（该程序未使用__USE_HASP_MAP，速度不是最快）

使用 C 语言的“准元程序”设计

作者: rockeet 发表日期: 2005年11月03日分类: C++ 评论: 2 条阅读次数: 3,745 次

将 C 语言的预编译语言看成是“元语言”，使用该元语言进行程序设计

但为什么叫“准元程序”?

因为 C 语言的预编译语言没有迭代结构，所以C 语言的元程序语言不是图灵完备的。举个简单的例子，我们无法用 C 语言的“元语言”写出一个计算 factorial(x)——x 的阶乘的程序；而用 C++的模板就可以（使用模板特化）。因为这需要语言的迭代结构。C预编译语言没有迭代结构的原因是宏替换仅发生在源语言的宏调用中，预编译中的宏调用是不会发生替换的（除了条件编译中条件中对宏的调用）如：

#define  macro1(x)   (x)*(x)
#define  macro2(x)  macro1(x)  // 这里不会发生宏替换
int y = macro2(100);  // 宏替换仅发生在这里

#define macro1(x) (x)*(x)

#define macro2(x) macro1(x) // 这里不会发生宏替换

int y = macro2(100); // 宏替换仅发生在这里

但是，在条件编译中：

#if  macro2(100) == 10000 // 这里会发生宏替换
….
#endif

#if macro2(100) == 10000 // 这里会发生宏替换

….

#endif

因此，象这样的程序是错误的：

// fac.c, 计算 x 的阶乘
#if x <= 0
#   define  result  1
#else
 
#   undef  temp_x
#   define temp_x  (x - 1)
#   undef  x
#   define x temp_x
#   include "fac.c"
 
#   undef  temp_result
#   define temp_result result * x
#   undef  result
#   define result  temp_result
 
#endif

// fac.c, 计算 x 的阶乘

#if x <= 0

# define result 1

#else

# undef temp_x

# define temp_x (x - 1)

# undef x

# define x temp_x

# include "fac.c"

# undef temp_result

# define temp_result result * x

# undef result

# define result temp_result

#endif

适应它，Play With Preprocessor

虽然如此，用 C 语言的预编译能力，在很多时候还是可以写出很好的程序，可以尽可能地减少代码冗余，增强程序性能。程序的可读性，也许增加了，也许减少了；但是在这个探索的过程中，很可能对问题的认识更深刻了，问题得到了更高程度的抽象。

元程序使用的几个重要重要指令：

#define  macro // 用来定义“模板参数”
#undef   macro // 用来清除“模板参数”
#include "template_body" // 用来定义“模板体”
// 符号展开连接：
#define  CAT_TOKEN_1(t1, t2)  t1##t2
#define  CAT_TOKEN(t1, t2)  CAT_TOKEN_1(t1,t2)
// CAT_TOKEN_1 直接将 t1 和 t2 连接成 t1t2，而
// CAT_TOKEN 将 t1 和 t2 展开后再连接，如：
#define  t1  I_am_
#define  t2  lei_peng
CAT_TOKEN_1(t1, t2) // 结果是  t1t2
CAT_TOKEN(t1, t2)   // 结果是  I_am_leipeng

#define macro // 用来定义“模板参数”

#undef macro // 用来清除“模板参数”

#include "template_body" // 用来定义“模板体”

// 符号展开连接：

#define CAT_TOKEN_1(t1, t2) t1##t2

#define CAT_TOKEN(t1, t2) CAT_TOKEN_1(t1,t2)

// CAT_TOKEN_1 直接将 t1 和 t2 连接成 t1t2，而

// CAT_TOKEN 将 t1 和 t2 展开后再连接，如：

#define t1 I_am_

#define t2 lei_peng

CAT_TOKEN_1(t1, t2) // 结果是 t1t2

CAT_TOKEN(t1, t2) // 结果是 I_am_leipeng

CAT_TOKEN是一个核心的基本构造块。

总体上讲，C++的元程序设计是函数式语言（类似 lisp），而C语言的元程序设计有点类似汇编语言，试看：

// C 元程序代码
#define  param1 ….. 
#define  param2 …..
#define  param3 …..
#include  “template.c”
#undef  param1  // 这些 #undef 也可以位于 “template.c”之内
#undef  param2
#undef  param3

// C 元程序代码

#define param1 …..

#define param2 …..

#define param3 …..

#include “template.c”

#undef param1 // 这些 #undef 也可以位于 “template.c”之内

#undef param2

#undef param3

// 汇编的函数调用代码
Push  param1
Push  param2
Push  param3
Call function
Add esp, 3 * 4  //恢复堆栈，堆栈也可以在 function 的返回语句恢复

// 汇编的函数调用代码

Push param1

Push param2

Push param3

Call function

Add esp, 3 * 4 //恢复堆栈，堆栈也可以在 function 的返回语句恢复

实例，实现函数

int bitblt( GdiDevice* dst, const GdiDevice* src
          , int dx, int dy, int cx, int cy, int sx, int sy
          , BinaryOpCode op
          );

int bitblt( GdiDevice* dst, const GdiDevice* src

, int dx, int dy, int cx, int cy, int sx, int sy

, BinaryOpCode op

);

a) 这是一个性能要求相当高基本图像位传送函数，同时又有许多种位操作：
(1) not,and,or,xor,…完备的布尔代数，共16种布尔操作，去掉全真和全假，是14种操作
(2) 许多种象素位数(1,2,4,8,16,24,32)，甚至更多。
(3) 这些情况组合起来，共有 686种（7×7×14）这显然是一个“过于完备”）的集合。
(4) 如果按普通的方式编码，要写 686多个不同的函数，或者 switch…case中686种不同的 case。而这些代码都是非常相似的，如果把相同部分提取出来，把不同部分使用“模板”替换掉…..

(5) 详细内容见代码，代码是非常短的（同时还有另外一个函数mergeblt，原型与bitblt相同，其中仅实现了16，24，32位象素），这些代码如果使用预编译器输出处理结果，有 6000 多行！：

代码（附件中有完整代码）

// 模板体，bitblt_body.c
//////////////////////////////////////////////////////////////////////////

MCASE(dstBits, srcBits, bitOpCode) {
	callerVars()
	int dstRowBytes = ROW_BYTES_2(dstBits, dst);
	int srcRowBytes = ROW_BYTES_2(srcBits, src);
	int i;
	PBYTE dstRow = dst->data + dy * dstRowBytes + PIX_POS_2(dstBits, dx);
	PBYTE srcRow = src->data + sy * srcRowBytes + PIX_POS_2(srcBits, sx);
	for (i = cy; i; --i) {
		PBYTE dstCol = dstRow;
		PBYTE srcCol = srcRow;
		int j;
		for (j = cx; j; --j) {
			condition(dstCol, srcCol)
				callBitOp(dstCol, srcCol);
		}
		dstRow += dstRowBytes;
		srcRow += srcRowBytes;
	}
}
return 0;

#undef bitOpCode
#undef doBitOp


// 相同象素位的不同位操作（14种）

#define bitOpCode    opCopy
#define doBitOp(d, s)      d = s
#include "bitblt_body.c"

#define bitOpCode    opAnd
#define doBitOp(d, s)      d &= s
#include "bitblt_body.c"

#define bitOpCode    opOr
#define doBitOp(d, s)      d |= s
#include "bitblt_body.c"

#define bitOpCode    opXor
#define doBitOp(d, s)      d ^= s
#include "bitblt_body.c"

#define bitOpCode    opNotSrc
#define doBitOp(d, s)      d = ~s
#include "bitblt_body.c"

#define bitOpCode    opNotAnd
#define doBitOp(d, s)      d = ~(d & s)
#include "bitblt_body.c"

#define bitOpCode    opNotOr
#define doBitOp(d, s)      d = ~(d | s)
#include "bitblt_body.c"

#define bitOpCode    opNotXor
#define doBitOp(d, s)      d = ~(d ^ s)
#include "bitblt_body.c"

#define bitOpCode    opNotDestAnd
#define doBitOp(d, s)      d = ~d & s
#include "bitblt_body.c"

#define bitOpCode    opNotDestOr
#define doBitOp(d, s)      d = ~d | s
#include "bitblt_body.c"

#define bitOpCode    opNotDestXor
#define doBitOp(d, s)      d = ~d ^ s
#include "bitblt_body.c"

#define bitOpCode    opNotSrcAnd
#define doBitOp(d, s)      d &= ~s
#include "bitblt_body.c"

#define bitOpCode    opNotSrcOr
#define doBitOp(d, s)      d |= ~s
#include "bitblt_body.c"

#define bitOpCode    opNotSrcXor
#define doBitOp(d, s)      d ^= ~s
#include "bitblt_body.c"

#undef callBitOp
#undef dstBits
#undef srcBits
#undef pSrcToColor


// blt_body.c, 所有象素位数的模板，这里只定义了 16，24，32三种象素的相互操作

// dst --- 16
#define dstBits  16
#define srcBits  16
#define pSrcToColor  PCOLOR16_TO_32
#define callBitOp(pd, ps)  doBitOp(*(UINT16*)pd,*(UINT16*)ps), pd+=2,ps+=2
#include "bitblt_op.c"

#define dstBits  16
#define srcBits  24
#define pSrcToColor  PCOLOR24_TO_32
#define callBitOp(pd, ps) doBitOp(*(UINT16*)pd, PCOLOR24_TO_16(ps)), 
pd +=2, ps += 3
#include "bitblt_op.c"

#define dstBits  16
#define srcBits  32
#define pSrcToColor(x)  *(x)
#define callBitOp(pd, ps) doBitOp(*(UINT16*)pd, PCOLOR32_TO_16(ps)), 
pd +=2, ps += 4
#include "bitblt_op.c"

// dst --- 24
#define dstBits  24
#define srcBits  16
#define pSrcToColor  PCOLOR16_TO_32
#define callBitOp(pd, ps) doBitOp(pd[0], C16_R(*(UINT16*)ps)), 
doBitOp(pd[1], C16_G(*(UINT16*)ps)), 
	doBitOp(pd[2], C16_B(*(UINT16*)ps)), 
	pd +=3, ps += 2
#include "bitblt_op.c"

#define dstBits  24
#define srcBits  24
#define pSrcToColor  PCOLOR24_TO_32
#define callBitOp(pd, ps) doBitOp(pd[0], ps[0]), 
	doBitOp(pd[1], ps[1]), 
	doBitOp(pd[2], ps[2]),  pd +=3, ps += 3
#include "bitblt_op.c"

#define dstBits  24
#define srcBits  32
#define pSrcToColor(x)  *(x)
#define callBitOp(pd, ps) doBitOp(pd[0], C32_R(*ps)), 
	doBitOp(pd[1], C32_G(*ps)), 
	doBitOp(pd[2], C32_B(*ps)), pd +=3, ps += 4
#include "bitblt_op.c"

	// dst --- 32
#define dstBits  32
#define srcBits  16
#define pSrcToColor  PCOLOR16_TO_32
#define callBitOp(pd, ps)  doBitOp(*(UINT32*)pd, PCOLOR16_TO_32(ps)), 
	pd +=4, ps += 2
#include "bitblt_op.c"

#define dstBits  32
#define srcBits  24
#define pSrcToColor  PCOLOR24_TO_32
#define callBitOp(pd, ps) doBitOp(*(UINT32*)pd, PCOLOR24_TO_32(ps)), 
	pd +=4, ps += 3
#include "bitblt_op.c"

#define dstBits  32
#define srcBits  32
#define pSrcToColor(x)  *(x)
#define callBitOp(pd, ps)  doBitOp(*(UINT32*)pd,*(UINT32*)ps), pd+=4, ps+=4
#include "bitblt_op.c"


	// 函数体，适用于 bitblt 和 mergeblt，模板参数为 condition

	static const unsigned char jump_table[] = {
		0,    bit_1,       bit_2, 0, bit_4 , 0, 0, 0,
		bit_8 ,        0,           0, 0, bit_12, 0, 0, 0,
		bit_16,              0,           0, 0,        0, 0, 0, 0,
		bit_24,        0,     0, 0,        0, 0, 0, 0,
		bit_32
	};
	int jump_index;

	if (dst->colorBits > 32) return -1;
	if (src->colorBits > 32) return -2;
	if ((unsigned int)op >= (unsigned int)BinaryOpCode_Radix)
		return -4;

	jump_index =
		jump_table[dst->colorBits] +
		jump_table[src->colorBits] * bitRadix +  op * bitRadix*bitRadix;

	switch (jump_index)
	{
	default:
		if (0 == jump_table[dst->colorBits])
			return -1; // dst->colorBits error
		else if (0 == jump_table[src->colorBits])
			return -2; // src->colorBits error
		else
			return -3; // not support
#include "blt_body.c"
	}

	return -5; // it will not goes here

#undef  condition



// gdi.h 定义图像基本类型和常量，及 utilities

#ifndef __GDI_H__
#define __GDI_H__

typedef enum BinaryOpCode
{
	opCopy,              // dst = src
	opXor,        // dst = src ^ dst
	opAnd,        // dst = src & dst
	opOr,         // dst = src | dst

	opNotSrc,     // dst = ~src
	opNotAnd,     // dst = ~(src & dst)
	opNotOr,      // dst = ~(src | dst)
	opNotXor,     // dst = ~(src ^ dst)

	opNotDestAnd, // dst = ~dst &  src
	opNotDestOr,  // dst = ~dst |  src
	opNotDestXor, // dst = ~dst ^  src
	opNotSrcAnd,  // dst =  dst & ~src
	opNotSrcOr,          // dst =  dst | ~src
	opNotSrcXor,  // dst =  dst ^ ~src

	//     opSet,        // dst = 1
	//     opClear,      // dst = 0

	BinaryOpCode_Radix
} BinaryOpCode;

typedef unsigned char BYTE, *PBYTE;
typedef unsigned long COLOR;
typedef unsigned short UINT16;
typedef unsigned long  UINT32;

typedef struct _GdiDevice
{
	unsigned int colorBits;
	int           width;
	int           height;
	COLOR  transparentColor;
	int           transparentTolerance;
	COLOR* pallete;
	PBYTE  data;
} GdiDevice;

#define ROW_BYTES_2(colorBits, gdi) ((7 + (gdi)->width * colorBits) >> 3)
#define PIX_POS_2(colorBits, x) ((x * colorBits) >> 3)

#define ROW_BYTES(gdi) ((7 + (gdi)->width * (gdi)->colorBits) >> 3)
#define PIX_POS(gdi, x) ((x * (gdi)->colorBits) >> 3)

#endif


// bitblt.c
// bitblt 函数和 mergeblt的函数体

#include "gdi.h"

enum ColorBitKind
{
	bitError = 0,
	bit_1 = 1,
	bit_2 = 2,
	bit_4,
	bit_8,
	bit_12,
	bit_16,
	bit_24,
	bit_32,
	bitRadix
};

#define CAT_TOKEN1(t1, t2)  t1##t2
#define CAT_TOKEN(t1, t2)   CAT_TOKEN1(t1, t2)

#define MCASE(dstBits, srcBits, bitOpCode)      
   case CAT_TOKEN(bit_, dstBits) + 
        CAT_TOKEN(bit_, srcBits)*bitRadix + bitOpCode*bitRadix*bitRadix:


// 00RR-RRRR-RRRR-GGGG-GGGG-GGBB-BBBB-BBBB
// 0x3FF00000  0x000FFC00  0x000003FF
#define C32_R(c)     (c >> 20 & 0x3FF)
#define C32_G(c)     (c >> 10 & 0x3FF)
#define C32_B(c)     (c     & 0x3FF)

#define C16_R(c)     (c >> 10 & 0x1F)
#define C16_G(c)     (c >>  5 & 0x1F)
#define C16_B(c)     (c     & 0x1F)

#define PCOLOR24_TO_16(p24)  (
		((UINT16)p24[2]&0xF8) << 8 |
		((UINT16)p24[1]&0xF8) << 3 |
				 p24[0]       >> 3)
// 这几种颜色转换未实现
#define PCOLOR32_TO_16(p32)  0

#define PCOLOR16_TO_24(p16)  0
#define PCOLOR32_TO_24(p16)  0

#define PCOLOR16_TO_32(p24)  0
#define PCOLOR24_TO_32(p24)  0

// empty...
#define callerVars()

int bitblt(GdiDevice* dst, const GdiDevice* src,
		int dx, int dy, int cx, int cy, int sx, int sy, BinaryOpCode op)
{
#define condition(pd, ps)
#include "template/fun_body.c"
}

int mergeblt(GdiDevice* dst, const GdiDevice* src,
		int dx, int dy, int cx, int cy, int sx, int sy, BinaryOpCode op)
{
	// condition no tolerance...
#define condition(pd, ps)  if (pSrcToColor(ps) != src->transparentColor)
#include "template/fun_body.c"
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

320

321

322

323

// 模板体，bitblt_body.c

//////////////////////////////////////////////////////////////////////////

MCASE(dstBits, srcBits, bitOpCode) {

callerVars()

int dstRowBytes = ROW_BYTES_2(dstBits, dst);

int srcRowBytes = ROW_BYTES_2(srcBits, src);

int i;

PBYTE dstRow = dst->data + dy * dstRowBytes + PIX_POS_2(dstBits, dx);

PBYTE srcRow = src->data + sy * srcRowBytes + PIX_POS_2(srcBits, sx);

for (i = cy; i; --i) {

PBYTE dstCol = dstRow;

PBYTE srcCol = srcRow;

int j;

for (j = cx; j; --j) {

condition(dstCol, srcCol)

callBitOp(dstCol, srcCol);

}

dstRow += dstRowBytes;

srcRow += srcRowBytes;

}

return 0;

#undef bitOpCode

#undef doBitOp

// 相同象素位的不同位操作（14种）

#define bitOpCode opCopy

#define doBitOp(d, s) d = s

#include "bitblt_body.c"

#define bitOpCode opAnd

#define doBitOp(d, s) d &= s

#include "bitblt_body.c"

#define bitOpCode opOr

#define doBitOp(d, s) d |= s

#include "bitblt_body.c"

#define bitOpCode opXor

#define doBitOp(d, s) d ^= s

#include "bitblt_body.c"

#define bitOpCode opNotSrc

#define doBitOp(d, s) d = ~s

#include "bitblt_body.c"

#define bitOpCode opNotAnd

#define doBitOp(d, s) d = ~(d & s)

#include "bitblt_body.c"

#define bitOpCode opNotOr

#define doBitOp(d, s) d = ~(d | s)

#include "bitblt_body.c"

#define bitOpCode opNotXor

#define doBitOp(d, s) d = ~(d ^ s)

#include "bitblt_body.c"

#define bitOpCode opNotDestAnd

#define doBitOp(d, s) d = ~d & s

#include "bitblt_body.c"

#define bitOpCode opNotDestOr

#define doBitOp(d, s) d = ~d | s

#include "bitblt_body.c"

#define bitOpCode opNotDestXor

#define doBitOp(d, s) d = ~d ^ s

#include "bitblt_body.c"

#define bitOpCode opNotSrcAnd

#define doBitOp(d, s) d &= ~s

#include "bitblt_body.c"

#define bitOpCode opNotSrcOr

#define doBitOp(d, s) d |= ~s

#include "bitblt_body.c"

#define bitOpCode opNotSrcXor

#define doBitOp(d, s) d ^= ~s

#include "bitblt_body.c"

#undef callBitOp

#undef dstBits

#undef srcBits

#undef pSrcToColor

// blt_body.c, 所有象素位数的模板，这里只定义了 16，24，32三种象素的相互操作

// dst --- 16

#define dstBits 16

#define srcBits 16

#define pSrcToColor PCOLOR16_TO_32

#define callBitOp(pd, ps) doBitOp(*(UINT16*)pd,*(UINT16*)ps), pd+=2,ps+=2

#include "bitblt_op.c"

#define dstBits 16

#define srcBits 24

#define pSrcToColor PCOLOR24_TO_32

#define callBitOp(pd, ps) doBitOp(*(UINT16*)pd, PCOLOR24_TO_16(ps)),

pd +=2, ps += 3

#include "bitblt_op.c"

#define dstBits 16

#define srcBits 32

#define pSrcToColor(x) *(x)

#define callBitOp(pd, ps) doBitOp(*(UINT16*)pd, PCOLOR32_TO_16(ps)),

pd +=2, ps += 4

#include "bitblt_op.c"

// dst --- 24

#define dstBits 24

#define srcBits 16

#define pSrcToColor PCOLOR16_TO_32

#define callBitOp(pd, ps) doBitOp(pd[0], C16_R(*(UINT16*)ps)),

doBitOp(pd[1], C16_G(*(UINT16*)ps)),

doBitOp(pd[2], C16_B(*(UINT16*)ps)),

pd +=3, ps += 2

#include "bitblt_op.c"

#define dstBits 24

#define srcBits 24

#define pSrcToColor PCOLOR24_TO_32

#define callBitOp(pd, ps) doBitOp(pd[0], ps[0]),

doBitOp(pd[1], ps[1]),

doBitOp(pd[2], ps[2]), pd +=3, ps += 3

#include "bitblt_op.c"

#define dstBits 24

#define srcBits 32

#define pSrcToColor(x) *(x)

#define callBitOp(pd, ps) doBitOp(pd[0], C32_R(*ps)),

doBitOp(pd[1], C32_G(*ps)),

doBitOp(pd[2], C32_B(*ps)), pd +=3, ps += 4

#include "bitblt_op.c"

// dst --- 32

#define dstBits 32

#define srcBits 16

#define pSrcToColor PCOLOR16_TO_32

#define callBitOp(pd, ps) doBitOp(*(UINT32*)pd, PCOLOR16_TO_32(ps)),

pd +=4, ps += 2

#include "bitblt_op.c"

#define dstBits 32

#define srcBits 24

#define pSrcToColor PCOLOR24_TO_32

#define callBitOp(pd, ps) doBitOp(*(UINT32*)pd, PCOLOR24_TO_32(ps)),

pd +=4, ps += 3

#include "bitblt_op.c"

#define dstBits 32

#define srcBits 32

#define pSrcToColor(x) *(x)

#define callBitOp(pd, ps) doBitOp(*(UINT32*)pd,*(UINT32*)ps), pd+=4, ps+=4

#include "bitblt_op.c"

// 函数体，适用于 bitblt 和 mergeblt，模板参数为 condition

static const unsigned char jump_table[] = {

0, bit_1, bit_2, 0, bit_4 , 0, 0, 0,

bit_8 , 0, 0, 0, bit_12, 0, 0, 0,

bit_16, 0, 0, 0, 0, 0, 0, 0,

bit_24, 0, 0, 0, 0, 0, 0, 0,

bit_32

};

int jump_index;

if (dst->colorBits > 32) return -1;

if (src->colorBits > 32) return -2;

if ((unsigned int)op >= (unsigned int)BinaryOpCode_Radix)

return -4;

jump_index =

jump_table[dst->colorBits] +

jump_table[src->colorBits] * bitRadix + op * bitRadix*bitRadix;

switch (jump_index)

{

default:

if (0 == jump_table[dst->colorBits])

return -1; // dst->colorBits error

else if (0 == jump_table[src->colorBits])

return -2; // src->colorBits error

else

return -3; // not support

#include "blt_body.c"

}

return -5; // it will not goes here

#undef condition

// gdi.h 定义图像基本类型和常量，及 utilities

#ifndef __GDI_H__

#define __GDI_H__

typedef enum BinaryOpCode

{

opCopy, // dst = src

opXor, // dst = src ^ dst

opAnd, // dst = src & dst

opOr, // dst = src | dst

opNotSrc, // dst = ~src

opNotAnd, // dst = ~(src & dst)

opNotOr, // dst = ~(src | dst)

opNotXor, // dst = ~(src ^ dst)

opNotDestAnd, // dst = ~dst & src

opNotDestOr, // dst = ~dst | src

opNotDestXor, // dst = ~dst ^ src

opNotSrcAnd, // dst = dst & ~src

opNotSrcOr, // dst = dst | ~src

opNotSrcXor, // dst = dst ^ ~src

// opSet, // dst = 1

// opClear, // dst = 0

BinaryOpCode_Radix

} BinaryOpCode;

typedef unsigned char BYTE, *PBYTE;

typedef unsigned long COLOR;

typedef unsigned short UINT16;

typedef unsigned long UINT32;

typedef struct _GdiDevice

{

unsigned int colorBits;

int width;

int height;

COLOR transparentColor;

int transparentTolerance;

COLOR* pallete;

PBYTE data;

} GdiDevice;

#define ROW_BYTES_2(colorBits, gdi) ((7 + (gdi)->width * colorBits) >> 3)

#define PIX_POS_2(colorBits, x) ((x * colorBits) >> 3)

#define ROW_BYTES(gdi) ((7 + (gdi)->width * (gdi)->colorBits) >> 3)

#define PIX_POS(gdi, x) ((x * (gdi)->colorBits) >> 3)

#endif

// bitblt.c

// bitblt 函数和 mergeblt的函数体

#include "gdi.h"

enum ColorBitKind

{

bitError = 0,

bit_1 = 1,

bit_2 = 2,

bit_4,

bit_8,

bit_12,

bit_16,

bit_24,

bit_32,

bitRadix

};

#define CAT_TOKEN1(t1, t2) t1##t2

#define CAT_TOKEN(t1, t2) CAT_TOKEN1(t1, t2)

#define MCASE(dstBits, srcBits, bitOpCode)

case CAT_TOKEN(bit_, dstBits) +

CAT_TOKEN(bit_, srcBits)*bitRadix + bitOpCode*bitRadix*bitRadix:

// 00RR-RRRR-RRRR-GGGG-GGGG-GGBB-BBBB-BBBB

// 0x3FF00000 0x000FFC00 0x000003FF

#define C32_R(c) (c >> 20 & 0x3FF)

#define C32_G(c) (c >> 10 & 0x3FF)

#define C32_B(c) (c & 0x3FF)

#define C16_R(c) (c >> 10 & 0x1F)

#define C16_G(c) (c >> 5 & 0x1F)

#define C16_B(c) (c & 0x1F)

#define PCOLOR24_TO_16(p24) (

((UINT16)p24[2]&0xF8) << 8 |

((UINT16)p24[1]&0xF8) << 3 |

p24[0] >> 3)

// 这几种颜色转换未实现

#define PCOLOR32_TO_16(p32) 0

#define PCOLOR16_TO_24(p16) 0

#define PCOLOR32_TO_24(p16) 0

#define PCOLOR16_TO_32(p24) 0

#define PCOLOR24_TO_32(p24) 0

// empty...

#define callerVars()

int bitblt(GdiDevice* dst, const GdiDevice* src,

int dx, int dy, int cx, int cy, int sx, int sy, BinaryOpCode op)

{

#define condition(pd, ps)

#include "template/fun_body.c"

}

int mergeblt(GdiDevice* dst, const GdiDevice* src,

int dx, int dy, int cx, int cy, int sx, int sy, BinaryOpCode op)

{

// condition no tolerance...

#define condition(pd, ps) if (pSrcToColor(ps) != src->transparentColor)

#include "template/fun_body.c"

}

C 语言几个绝招

作者: rockeet 发表日期: 2005年11月03日分类: C++ 评论: 0 条阅读次数: 3,108 次

符号展开连接

#define CAT_TOKEN_1(t1, t2)? t1##t2
#define CAT_TOKEN_2(t1, t2)? CAT_TOKEN_1(t1,t2)
#define CAT_TOKEN  CAT_TOKEN_2

#define CAT_TOKEN_1(t1, t2)? t1##t2

#define CAT_TOKEN_2(t1, t2)? CAT_TOKEN_1(t1,t2)

#define CAT_TOKEN CAT_TOKEN_2

CAT_TOKEN_1 将 t1 和 t2 连接成 t1t2 ，不预先将 t1 和 t2 展开，而

CAT_TOKEN_2 将 t1 和 t2 展开后再连接，如：

#define t1 I_am_
#define t2 lei_peng

CAT_TOKEN_1(t1, t2) // 结果是 t1t2
CAT_TOKEN_2(t1, t2) // 结果是 I_am_leipeng

#define t1 I_am_

#define t2 lei_peng

CAT_TOKEN_1(t1, t2) // 结果是 t1t2

CAT_TOKEN_2(t1, t2) // 结果是 I_am_leipeng

将0转化为0，而将非零转化为 1，可以转化指针

#define convert_bool(x) (!!(x))

1	#define convert_bool(x) (!!(x))

编译时断言

#define COMPILE_ASSERT(x)? \
     enum { CAT_TOKEN (comp_assert_, __LINE__) = 1 / !!(x) };
// 或者
#define COMPILE_ASSERT_2(x)?\
     void CAT_TOKEN(comp_assert_fun_,__LINE__)? (int x[][x]);

#define COMPILE_ASSERT(x)? \

enum { CAT_TOKEN (comp_assert_, __LINE__) = 1 / !!(x) };

// 或者

#define COMPILE_ASSERT_2(x)?\

void CAT_TOKEN(comp_assert_fun_,__LINE__)? (int x[][x]);

定义 Handle类型

#define? DEFINE_HANDLE_TYPE(handle_type)? \
    struct param_##handle_type;  \
    typedef? void? (*handle_type )(struct param_##handle_type);

#define? DEFINE_HANDLE_TYPE(handle_type)? \

struct param_##handle_type; \

typedef? void? (*handle_type )(struct param_##handle_type);

将 Handle 定义为函数指针主要有一个好处：就是禁止了对 Handle 的加减，防止了一些小错误的发生。

定义union中的匿名 struct

struct my_type {
    union {
        struct { … } u1;
        struct { … } u2;
        struct { … } u3;
    };
};

struct my_type {

union {

struct { … } u1;

struct { … } u2;

struct { … } u3;

};

一个脚本语言编译器

作者: rockeet 发表日期: 2005年11月03日分类: 自动机评论: 0 条阅读次数: 2,150 次

　　该编译器及运行环境采用虚拟机执行方式，即将源文件编译为中间代码（类似 Java 字节码），而中间代码在虚拟机（不是堆栈机，Java虚拟机是“准堆栈机”，大部分指令是堆栈式的，但为了效率，也有小部分指令不是堆栈式的）上执行。可用于编译原理学习。

代码下载：http://febird.nease.net/OtherProduct/ScriptCompiler/ScriptEngine.rar

语言描述：http://febird.nease.net/OtherProduct/ScriptCompiler/Specification.htm

我的原文：http://febird.nease.net/OtherProduct/ScriptCompiler/ScriptCompiler.htm

按序号索引二叉树

作者: rockeet 发表日期: 2005年11月03日分类: 算法评论: 0 条阅读次数: 1,764 次

　　理论上，一个平衡的二叉树，可以在 O(logn)时间内，按中序遍历的顺序号（或者说下标）完成对结点的搜索。不过，这需要在每个结点上存储以该结点为根的子树的大小，通过增加存储的途径，来改善性能。

　　如果这是一棵排序树，那么这个序号就是按大小排列的顺序号。

　　但是如果这颗树在程序运行过程中有对结点的动态插入和删除（插入和删除时，以及调整平衡性时，都需要调整插入/删除结点路径上的Node.count，时间复杂度为O(logn)），那么每个结点的序号就是变化的。

　　因此，不能把序号存储在某个地方，然后又企图根据这一序号，重新找到该序号先前对应的那个结点。可能时因为这个原因，在很多时候，没有对这种计算的需求。我目前还没有在什么地方看到过这方面的文章。自己苦思冥想，竟也完成了。

class Node
{
public:
Node* getByIndex(int index)
{
  Node* p = this;
  while (p)
  {
   Node* q = p->left;
   while (q && q->count > index)
   {
    p = q;
    q = q->left;
   }
   if (0 == q || q->count == index) return p;

   p = p->right;
   index–;
   if (q) index -= q->count;
  }
  return 0;
}
private:
Node *left, *right;
int count; // node count of ‘this’ and its subtree
};

软件加密技术及实现－续－01

作者: rockeet 发表日期: 2004年06月15日分类: 操作系统评论: 0 条阅读次数: 2,036 次

两年前，我曾在毕业设计：《软件加密技术及实现》中设想使用“代码转移”来实现更强大的反破解功能。

直到前不久，在朋友的鼓励下，我在多个方面增强了原先的软件SoftProtector，并改为图形界面，改名为《秦赢甲胄》(可在各搜索引擎搜索)，开始尝试商业化。

为了实现更强大的反破解功能，前不久我开始思考实现“代码转移”，不想实现根设想完全两码事，太复杂了：需要对 x86 进行反汇编，代码分析，甚至虚拟执行（虚拟机），来完善《秦赢甲胄》。

在参考了很多资料之后，我终于深有体会，我需要更多的。

希望大家支持！

目前我的参考资料：

1. 《虚拟机设计与实现》，说实话，该书深度不够，不过它提到了不少好的参考资料。

2. Java KVM 虚拟机源代码：http://www.sun.com

3. IA-32 Intel® Architecture Software Developer’s Manual, http://www.intel.com

在 C 语言中实现模板函数的方法（续）

作者: rockeet 发表日期: 2004年06月10日分类: C++ 评论: 0 条阅读次数: 2,191 次

在 C 语言中实现模板函数的方法（续）：

/* 定义一个宏，用来连接两个标识符：*/

#define MAKE_NAME(className, methodName) calssName##__##methodName

/* 模板源文件：template.c

* 必须重定义的宏：TheClass

* 其它需要重定义的宏（如对一个搜索树的实现，需要比较元素或键值大小的宏）

Int MAKE_NAME(TheClass, Method1) (int param1, int param2)

{

….

Return 0;

}

Int MAKE_NAME(TheClass, Method2) (int param1, int param2)

{

….

Return 0;

}

Int MAKE_NAME(TheClass, Method3) (int param1, int param2)

{

….

Return 0;

}

…..

/* 引用该模板的文件：samp1.c */

#undef TheClass

#define TheClass Class1

#include template.c

/* end samp1.c */

在 C 语言中实现模板函数的方法

作者: csdn-whinah 发表日期: 2004年06月07日分类: C++ 评论: 8 条阅读次数: 4,339 次

现以一个求和函数 Sum 为例，用 C++ Template 可写如下：

template<class T, class R>
R Sum(const T *array, int n) {
    R sum = 0;
    for (int i = 0; i < n; ++i) sum += i;
    return sum;
}

template<class T, class R>

R Sum(const T *array, int n) {

R sum = 0;

for (int i = 0; i < n; ++i) sum += i;

return sum;

}

如果不是内置类型，该模板隐式地需要有R R::operator+=(T)运算符可用。

三种使用 C 语言模拟C++的模板的方法

1. 使用函数指针作为 Functor 替换者

struct AddClass {
    Void (*add)(char* r1, const char* r2);
    Int elemSize;
    Char  sum[MAX_ELEM_SIZE];
};
void Sum(struct AddClass* self, const char* array, int n) {
     int i;
     for (i = 0; i < n; ++i)
         self->add(self->sum, array + i*self->elemSize);
}
 
// 使用时：
// …..
 
Void AddInt(char* r1, const char* r2) {
    *(long*)r1 += *(int*)r2;
}
AddClass addClass = {AddInt, 2, 0 };
Int array[100];
Read(array);
Sum(&addClass, array, 100);
// …..

struct AddClass {

Void (*add)(char* r1, const char* r2);

Int elemSize;

Char sum[MAX_ELEM_SIZE];

};

void Sum(struct AddClass* self, const char* array, int n) {

int i;

for (i = 0; i < n; ++i)

self->add(self->sum, array + i*self->elemSize);

}

// 使用时：

// …..

Void AddInt(char* r1, const char* r2) {

*(long*)r1 += *(int*)r2;

}

AddClass addClass = {AddInt, 2, 0 };

Int array[100];

Read(array);

Sum(&addClass, array, 100);

// …..

2. 用宏作为Functor的替换者

#define GenSumFun(SumFunName, Add, RetType, ElemType) \
RetType SumFunName (const ElemType *array, int n) {   \
    RetType sum = 0; int i;                           \
    for (i = 0 ; i < n ; ++i) Add(sum, i);            \
    return sum;                                       \
}
// 使用时：
#define AddInt(x, y)  ((x) += (y))
GenSumFun(SumInt, AddInt, long, int)
// …..
int array[100];
Read(array);
long sum = SumInt(array, 100);
// …..

#define GenSumFun(SumFunName, Add, RetType, ElemType) \

RetType SumFunName (const ElemType *array, int n) { \

RetType sum = 0; int i; \

for (i = 0 ; i < n ; ++i) Add(sum, i); \

return sum; \

}

// 使用时：

#define AddInt(x, y) ((x) += (y))

GenSumFun(SumInt, AddInt, long, int)

// …..

int array[100];

Read(array);

long sum = SumInt(array, 100);

// …..

3. 所有可替换参数均为宏

至少需要一个额外的文件(实现文件)为 impsum.c

/* impsum.c */
RetType FunName(const ElemType *array, int n) {                                                                     
    RetType sum = 0;
    int i;
    for (i = 0 ; i < n ; ++i) Add(sum, i);                            
    return sum;                                          
}
 
// 使用时：
#undef  RetType
#undef  FunName
#undef  ElemType
#undef  Add
#define AddInt(x, y)  ((x) += (y))
#define RetType long
#define FunName SumInt
#define ElemType int
#define Add  AddInt
 
#include impsum.c
 
…..
int array[100];
Read(array);
long sum = SumInt(array, 100);
…..

/* impsum.c */

RetType FunName(const ElemType *array, int n) {

RetType sum = 0;

int i;

for (i = 0 ; i < n ; ++i) Add(sum, i);

return sum;

}

// 使用时：

#undef RetType

#undef FunName

#undef ElemType

#undef Add

#define AddInt(x, y) ((x) += (y))

#define RetType long

#define FunName SumInt

#define ElemType int

#define Add AddInt

#include impsum.c

…..

int array[100];

Read(array);

long sum = SumInt(array, 100);

…..

总结：

第一种方法，易于跟踪调试，但是效率低下，适用于对可变函数（函数指针）的效率要求不高，但程序出错的可能性较大（复杂），模板函数（Sum）本身很复杂，模板参数也比较复杂（add）的场合。

第二种方法，效率高，但很难跟踪调试，在模板函数和模板参数本身都很复杂的时候更是如此。

第三种方法，是我最近几天才想出的，我认为是最好的，在模板参数（Add）比较复杂时可以用函数（第二种也可以如此），简单时可以用宏，并且，易于调试。在模板函数本身很复杂，而模板参数比较简单时更为优越。但是，可能有点繁琐。

一般情况下，没有必要做如此劳心的工作，一切交给编译器去做就行了。但是本人在开发一个文件系统时，由于是基于一种少见的平台，没有可用的C++编译器，有几个函数，除了其中的类型不同（uint16和uint32），和几个可参数化的宏不同，其它地方完全相同，而函数本身很复杂（两百多行代码）。Copy出几个完全类似的函数副本，维护起来特别烦人。非常需要如此的编程模式，故此，分享出来，大家共同探讨。

本网站仅单台服务器: 2核2G 99￥包年，集成兼容 MySQL 的 MyTopling 高压缩高性能数据库

本网站仅单台服务器: MyTopling 2核2G 99￥包年

当搜索词中有错别字时，搜索引擎会尝试纠错

通过相似拼音纠错

基于自动机的算法可以完美解决这个指数爆炸问题

这个算法也可以用来解决用户输入预测(智能提示)功能

基于编辑距离的纠错

创建 DFA Key 与搜索 DFA Key 的耗时包含了收集网页展示需要的信息，耗时占比90%以上！

高性能文件系统实现

C++使用模板进行的一种重构

C语言垃圾代码清除工具(含源码)

使用 C 语言的“准元程序”设计

但为什么叫“准元程序”?

适应它，Play With Preprocessor

元程序使用的几个重要重要指令：

实例，实现函数

代码（附件中有完整代码）

C 语言几个绝招

符号展开连接

将0转化为0，而将非零转化为 1，可以转化指针

编译时断言

定义 Handle类型

定义union中的匿名 struct

一个脚本语言编译器

按序号索引二叉树

软件加密技术及实现－续－01

在 C 语言中实现模板函数的方法（续）

在 C 语言中实现模板函数的方法

现以一个求和函数 Sum 为例，用 C++ Template 可写如下：

三种使用 C 语言模拟C++的模板的方法

1. 使用函数指针作为 Functor 替换者

2. 用宏作为Functor的替换者

3. 所有可替换参数均为宏

总结：

近期文章

近期评论

文章归档

分类目录

功能

本网站仅单台服务器: 2核2G 99￥包年，集成兼容 MySQL 的 MyTopling 高压缩高性能数据库

本网站仅单台服务器: MyTopling 2核2G 99￥包年

当搜索词中有错别字时，搜索引擎会尝试纠错

通过相似拼音纠错

基于自动机的算法可以完美解决这个指数爆炸问题

这个算法也可以用来解决用户输入预测(智能提示)功能

基于编辑距离的纠错

创建 DFA Key 与 搜索 DFA Key 的 耗时 包含了 收集网页展示需要的信息，耗时占比90%以上！

但为什么叫“准元程序”?

适应它，Play With Preprocessor

元程序使用的几个重要重要指令：

实例，实现函数

代码（附件中有完整代码）

符号展开连接

将0转化为0，而将非零转化为 1，可以转化指针

编译时断言

定义 Handle类型

定义union中的匿名 struct

现以一个求和函数 Sum 为例，用 C++ Template 可写如下：

三种使用 C 语言模拟C++的模板的方法

1. 使用函数指针作为 Functor 替换者

2. 用宏作为Functor的替换者

3. 所有可替换参数均为宏

总结：

近期文章

近期评论

文章归档

分类目录

功能

创建 DFA Key 与搜索 DFA Key 的耗时包含了收集网页展示需要的信息，耗时占比90%以上！