高性能文件系统实现
 |
 |
|
当搜索词中有错别字时，搜索引擎会尝试纠错通过相似拼音纠错搜索引擎把这些字还原成拼音，用一个拼音相同的已知的搜索词代替。 这是一种众所周知的纠错策略，但是，当输错的字是多音字，特别是有多个这样的错误输入时，所有的搜索引擎都尽量绕开这个问题，或者仅使用最常用的那些音去纠错。 因为要考虑所有可能的拼音组合，在极端情况下会导致指数爆炸！ 例如某互联网大厂的实现(枚举多音字全排列)。 基于自动机的算法可以完美解决这个指数爆炸问题
这个算法也可以用来解决用户输入预测(智能提示)功能用户只输入Query开头部分，就自动提示出整个Query，例如用户输入举头望，就提示出举头望明月。就像现在各种搜索引擎做的那样。 基于编辑距离的纠错在已知的搜索词中寻找编辑距离与用户 Query 最小的词，使用我的算法也可以高效解决（还没做演示页面） |
|
C++使用模板进行的一种重构
如果有一些遗留代码，里面有很多结构，定义了一些相同的成员，但在一些时候，需要取出这些成员，进行同样的处理。如下面这些代码的红色部分。
——原先的程序结构是使用类型码来区分实际的类型，客观地说，这些遗留代码是比较混乱的。
不想说太多，用简单的代码来说明问题吧。
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
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语言垃圾代码清除工具(含源码)
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，
程序下载（该程序未使用__USE_HASP_MAP，速度不是最快）
使用 C 语言的“准元程序”设计
将 C 语言的预编译语言看成是“元语言”，使用该元语言进行程序设计
但为什么叫“准元程序”?
因为 C 语言的预编译语言没有迭代结构，所以C 语言的元程序语言不是图灵完备的。举个简单的例子，我们无法用 C 语言的“元语言”写出一个计算 factorial(x)——x 的阶乘的程序；而用 C++的模板就可以（使用模板特化）。因为这需要语言的迭代结构。C预编译语言没有迭代结构的原因是宏替换仅发生在源语言的宏调用中，预编译中的宏调用是不会发生替换的（除了条件编译中条件中对宏的调用）如：
|
1 2 3 |
#define macro1(x) (x)*(x) #define macro2(x) macro1(x) // 这里不会发生宏替换 int y = macro2(100); // 宏替换仅发生在这里 |
但是，在条件编译中：
|
1 2 3 |
#if macro2(100) == 10000 // 这里会发生宏替换 …. #endif |
因此，象这样的程序是错误的：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// 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 语言的预编译能力，在很多时候还是可以写出很好的程序，可以尽可能地减少代码冗余，增强程序性能。程序的可读性，也许增加了，也许减少了；但是在这个探索的过程中，很可能对问题的认识更深刻了，问题得到了更高程度的抽象。
元程序使用的几个重要重要指令：
|
1 2 3 4 5 6 7 8 9 10 11 12 |
#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语言的元程序设计有点类似汇编语言，试看：
|
1 2 3 4 5 6 7 8 |
// C 元程序代码 #define param1 ….. #define param2 ….. #define param3 ….. #include “template.c” #undef param1 // 这些 #undef 也可以位于 “template.c”之内 #undef param2 #undef param3 |
|
1 2 3 4 5 6 |
// 汇编的函数调用代码 Push param1 Push param2 Push param3 Call function Add esp, 3 * 4 //恢复堆栈，堆栈也可以在 function 的返回语句恢复 |
实例，实现函数
|
1 2 3 4 |
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 多行！：
代码（附件中有完整代码）
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 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 语言几个绝招
符号展开连接
|
1 2 3 |
#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 展开后再连接，如：
|
1 2 3 4 5 |
#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，可以转化指针
|
1 |
#define convert_bool(x) (!!(x)) |
编译时断言
|
1 2 3 4 5 |
#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类型
|
1 2 3 |
#define? DEFINE_HANDLE_TYPE(handle_type)? \ struct param_##handle_type; \ typedef? void? (*handle_type )(struct param_##handle_type); |
将 Handle 定义为函数指针主要有一个好处：就是禁止了对 Handle 的加减，防止了一些小错误的发生。
定义union中的匿名 struct
|
1 2 3 4 5 6 7 |
struct my_type { union { struct { … } u1; struct { … } u2; struct { … } u3; }; }; |
一个脚本语言编译器
|
|
 |
代码下载：http://febird.nease.net/OtherProduct/ScriptCompiler/ScriptEngine.rar
语言描述：http://febird.nease.net/OtherProduct/ScriptCompiler/Specification.htm |
我的原文：http://febird.nease.net/OtherProduct/ScriptCompiler/ScriptCompiler.htm
按序号索引二叉树
理论上，一个平衡的二叉树，可以在 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
两年前，我曾在毕业设计：《软件加密技术及实现》中设想使用“代码转移”来实现更强大的反破解功能。
直到前不久，在朋友的鼓励下，我在多个方面增强了原先的软件SoftProtector，并改为图形界面，改名为《秦赢甲胄》(可在各搜索引擎搜索)，开始尝试商业化。
为了实现更强大的反破解功能，前不久我开始思考实现“代码转移”，不想实现根设想完全两码事，太复杂了：需要对 x86 进行反汇编，代码分析，甚至虚拟执行（虚拟机），来完善《秦赢甲胄》。
在参考了很多资料之后，我终于深有体会，我需要更多的。
希望大家支持！
目前我的参考资料：
1. 《虚拟机设计与实现》，说实话，该书深度不够，不过它提到了不少好的参考资料。
2. Java KVM 虚拟机源代码：http://www.sun.com
3. IA-32 Intel® Architecture Software Developer’s Manual, http://www.intel.com
在 C 语言中实现模板函数的方法（续）
在 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 语言中实现模板函数的方法
现以一个求和函数 Sum 为例，用 C++ Template 可写如下：
|
1 2 3 4 5 6 |
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 替换者
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
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的替换者
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
#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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
/* 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出几个完全类似的函数副本，维护起来特别烦人。非常需要如此的编程模式，故此，分享出来，大家共同探讨。