【转】谁说 C宏 是 智者的利刃,愚者的恶梦!

水平不高不低的C++程序员最喜欢挂在嘴上的一句话就是:C宏,万恶之首,错误的开端,应该被废弃。
请注意,我用了一句不敬的修饰语“水平不高不低的”。为什么这么说?因为水平低都插不上话,都在在静静地听老前辈布道呢。水平高的,比如Bane Stroustrup老人家,也只是说若干种场合下C++语言能够提供比C macro更好的解决方案,而没有完全否定C macro的价值。但是话就怕传来传去,一传就走样。久而久之,就被传成上面那句话。其实说来也很好笑:java程序员经常说java比C++好,说C+ +手动释放内存老搞内存泄漏;C++程序员便反驳说,那是你水平低不会用。但是谈到C宏,水平不高不低的C++程序员居然也走java的老路了——明明是 自己不会用,自己知道的少,却把责任推卸到C宏上。你自己笨我管不着,但是错误的言论如果误导后人就不好了吧。:)
本文就举几个简单的使用C宏的例子,如果这些例子用C++不用宏的语法能更好的解决,那么你一定要回复blog告诉我,这样下次我就不乱说话了。否则,笑笑很生气,后果很严重。:)

例一、用C宏,书写代码更简洁 这段代码写网络程序的朋友都很眼熟,是Net/3中mbuf的实现。

struct mbuf
{
struct m_hdr mhdr;
union {
struct
{
struct pkthdr MH_pkthdr; /* M_PKTHDR set */
union
{
struct m_ext MH_ext; /* M_EXT set */
char MH_databuf[MHLEN];
} MH_dat;
} MH;
char M_databuf[MLEN]; /* !M_PKTHER, !M_EXT*/
} M_dat;
};

上面的代码,假如我想访问最里层的MH_databuf,那么我必须写M_dat.MH.MH_dat.MH_databuf; 这是不是很长,很难写呀?这样的代码阅读起来也不明了。其实,对于MH_pkthdr、MH_ext、MH_databuf来说,虽然不是在一个结构层次 上,但是如果我们站在mbuf之外来看,它们都是mbuf的属性,完全可以压扁到一个平面上去看。所以,源码中有这么一组宏:

#define m_next      m_hdr.mh_next
#define m_len m_hdr.mh_len
#define m_data m_hdr.mh_data
... ...
#define m_pkthdr M_dat.MH.MH_pkthdr
#define m_pktdat M_dat.MH.MH_dat.MH_databuf
... ...

这样写起代码来,是不是很精练呢!

例二、用C宏,实现跨平台和编译器的需要 这方面的例子太好举了,一举一大摞,就从VC的库源码中随意copy一段出来吧。

#ifndef _CRTAPI1
#if _MSC_VER >= 800 && _M_IX86 >= 300
#define _CRTAPI1 __cdecl
#else /* _MSC_VER >= 800 && _M_IX86 >= 300 */
#define _CRTAPI1
#endif /* _MSC_VER >= 800 && _M_IX86 >= 300 */
#endif /* _CRTAPI1 */

#ifndef _SIZE_T_DEFINED
typedef unsigned int size_t;
#define _SIZE_T_DEFINED
#endif /* _SIZE_T_DEFINED */

#ifndef _MAC
#ifndef _WCHAR_T_DEFINED
typedef unsigned short wchar_t;
#define _WCHAR_T_DEFINED
#endif /* _WCHAR_T_DEFINED */
#endif /* _MAC */

#ifndef _NLSCMP_DEFINED
#define _NLSCMPERROR 2147483647 /* currently == INT_MAX */
#define _NLSCMP_DEFINED
#endif /* _NLSCMP_DEFINED */

请问,这些指示宏如何取代呢?如果真的是没有了这些宏,实现起来就更麻烦了吧。

例三、用C宏,自动生成代码 这方面的例子也是多得很,不过有鉴于很多朋友不用很多编译器,不做嵌入式的开发,我就举个win平台的例子吧。我们知道MFC实现了windows的消息映射,比如:

ON_COMMAND(IDM_ABOUT, OnAbout)
ON_COMMAND(IDM_FILENEW, OnFileNew)

它是如何实现的IDM_ABOUT和OnAbout的关联的呢?这要用到几个宏。

#define DECLARE_MESSAGE_MAP() 
private:
static const AFX_MSGMAP_ENTRY _messageEntries[];
protected:
static AFX_DATA const AFX_MSGMAP messageMap;
virtual const AFX_MSGMAP* GetMessageMap() const;

#define BEGIN_MESSAGE_MAP(theClass, baseClass)
const AFX_MSGMAP* theClass::GetMessageMap() const
{ return &theClass::messageMap; }
AFX_COMDAT AFX_DATADEF const AFX_MSGMAP theClass::messageMap =
{ &baseClass::messageMap, &theClass::_messageEntries[0] };
AFX_COMDAT const AFX_MSGMAP_ENTRY theClass::_messageEntries[] =
{

#define ON_COMMAND(id, memberFxn)
{ WM_COMMAND, 0, (WORD)id, (WORD)id, AfxSig_vv, (AFX_PMSG)memberFxn },

#define END_MESSAGE_MAP()
{0, 0, 0, 0, AfxSig_end, (AFX_PMSG)0 }
};
#define DECLARE_MESSAGE_MAP()
private:
static const AFX_MSGMAP_ENTRY _messageEntries[];
protected:
static AFX_DATA const AFX_MSGMAP messageMap;
virtual const AFX_MSGMAP* GetMessageMap() const;

#define BEGIN_MESSAGE_MAP(theClass, baseClass)
const AFX_MSGMAP* theClass::GetMessageMap() const
{ return &theClass::messageMap; }
AFX_COMDAT AFX_DATADEF const AFX_MSGMAP theClass::messageMap =
{ &baseClass::messageMap, &theClass::_messageEntries[0] };
AFX_COMDAT const AFX_MSGMAP_ENTRY theClass::_messageEntries[] =
{

#define ON_COMMAND(id, memberFxn)
{ WM_COMMAND, 0, (WORD)id, (WORD)id, AfxSig_vv, (AFX_PMSG)memberFxn },

#define END_MESSAGE_MAP()
{0, 0, 0, 0, AfxSig_end, (AFX_PMSG)0 }
};

嘿嘿,就这么几个宏,就构造出一个消息数组来。

例四、用C宏,智者思维的火花 说了半天了,嘴皮子都干了,举个例子大家轻松一下——看看人家老外是怎么用宏的。 这个例子摘自《C专家编程》。 根据位模式构建图形 图标(icon)或者图形(glyph),是一种小型的位模式映射于屏幕产生的图像。一个位代表图像上的一个像素。如果一个位被设置,那么它所代表的像素 就是“亮”的。如果一个位被清除,那么它所代表的像素就是“暗”的。所以,一系列的整数值能够用于为图像编码。类似Iconedit这样的工具就是用于绘 图的,他们所输出的是一个包含一系列整型数的ASCII文件,可以被一个窗口程序所包含。它所存在的问题是程序中的图标只是一串十六进制数。在C语言中, 典型的16X16的黑白图形可能如下:

static unsigned short stopwatch[] = {
0x07C6,
0x1FF7,
0x383B,
0x600C,
0x600C,
0xC006,
0xC006,
0xDF06,
0xC106,
0xC106,
0x610C,
0x610C,
0x3838,
0x1FF0,
0x07C0,
0x0000
};

正如所看到的那样,这些C语言常量并未有提供有关图形实际模样的任何线索。这里有一个惊人的#define定义的优雅集合,允许程序建立常量使它们看上去像是屏幕上的图形。

#define X )*2+1
#define _ )*2
#define s ((((((((((((((((0 /* For building glyphs 16 bits wide */

定义了它们之后,只要画所需要的图标或者图形等,程序会自动创建它们的十六进制模式。使用这些宏定义,程序的自描述能力大大加强,上面这个例子可以转变为:

static unsigned short stopwatch[] =
{
s _ _ _ _ _ X X X X X _ _ _ X X _ ,
s _ _ _ X X X X X X X X X _ X X X ,
s _ _ X X X _ _ _ _ _ X X X _ X X ,
s _ X X _ _ _ _ _ _ _ _ _ X X _ _ ,
s _ X X _ _ _ _ _ _ _ _ _ X X _ _ ,
s X X _ _ _ _ _ _ _ _ _ _ _ X X _ ,
s X X _ _ _ _ _ _ _ _ _ _ _ X X _ ,
s X X _ X X X X X _ _ _ _ _ X X _ ,
s X X _ _ _ _ _ X _ _ _ _ _ X X _ ,
s X X _ _ _ _ _ X _ _ _ _ _ X X _ ,
s _ X X _ _ _ _ X _ _ _ _ X X _ _ ,
s _ X X _ _ _ _ X _ _ _ _ X X _ _ ,
s _ _ X X X _ _ _ _ _ X X X _ _ _ ,
s _ _ _ X X X X X X X X X _ _ _ _ ,
s _ _ _ _ _ X X X X X _ _ _ _ _ _ ,
s _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
};

显然,与前面的代码相比,它的意思更为明显。标准的C语言具有八进制、十进制和十六进制常量,但没有二进制常量,否则的话倒是一种更为简单的绘制图形模式的方法。
如果抓住书的右上角,并斜这看这一页,可能会猜测这是一个用于流行窗口系统的“cursor busy”小秒表图形。我是在几年前从Usenet comp.lang.c新闻组学到这个技巧的。

千万不要忘了在绘图结束后清除这些宏定义,否这很可能会给你后面的代码带来不可预测的后果。

好了,今天的废话就到这里了。水能载舟,亦能覆舟,把握好手中的双刃剑,让它好好的为你服务吧,别割破了手。:)

Read: 780

递归的应用 — 最简单分形图形实现

作者:吉林大学 胡卓玮

下载本文源代码


图一 例子代码运行结果

    大家在C/C++学习时都会遇到递归,课本上以汗诺塔为例进行讲解,然后大家都希望自己找到一个递归的实例。本文以一个最简单的分形图形来讲解递归的实现过程。
    先来看看绘制这个分形图形的思路。如图二所示,给定两点(p1和p2)确定一条直线,计算这条直线的长度,如果长度小于预先设定的极限值则将这两个点用直 线相连,否则,取其1/3处点(点1)、2/3处点(点2),以及中点上方一个点(点3),这个点与第1点、第2点构成的直线与直线p1p2的夹角为60 度。判断这五个点按照顺序形成的四条直线的长度是否小于预先设定的极限值,如果小于,则在将相应的两个点相连在屏幕上显示一条直线,否则继续对相应两点形 成的直线进行以上判断。


图二 分形图形实现示意图

    这是一个典型的递归问题。我们可以看看如果不使用递归该怎样得到我们需要的结果。首先需要设立一些变量来存储点的坐标,由于不使用递归,我们需要在整个过 程的最后,把计算所得并保存起来的点的坐标传递给画线的函数,在不满足递归过程结束的条件下(即直线的长度大于极限值),将需要增加三个点,这时是四条直 线,如果下一次仍然达不到结束条件,将会得到的点数为2 + 3 + 4 * 3,直线数为4^2。这样,对于第n次不满足结束条件后获得的点数为:2 + 3 + 3 * 4 + 3 * 4 ^ 2 + …… + 3 * 4 ^ (n – 1),直线数为4 ^ n条。随着n的增大,这不是一个小数目。但如果使用递归实现,情况会大不一样,不需要定义过多的变量,不需要考虑复杂的点的顺序关系。
    来看看我们的程序当中是如何利用递归实现这个简单的分形图形的。整个实现过程封装到类KSQXClass中,为了方便点坐标的存取,定义了 KSQXPoint类,参看文件KSQXClass.h和KSQXClass.cpp,大家可以看到类的具体定义和实现。
    整个递归过程用函数Draw来实现。参数含义如下:
CDC* pdc; //设备描述表,绘制分形图形的设备
KSQXPoint p1, KSQXPoint p2; //直线的起点和终点,KSQXPoint以点的x,y坐标作为成员变量
    一开始需要计算直线的长度并判断其长度是否小于极限值:

      ds = (float)sqrt(dx * dx + dy * dy);
if(ds <= m_limit)
{
 pdc->MoveTo((int)p1.m_x, (int)p1.m_y);
 pdc->LineTo((int)p2.m_x, (int)p2.m_y);
 return;
}

其中的极限值m_limit通过成员函数SetLimit设定。

如果ds大于极限值,进行以下工作。
计算点1、点2和点3的坐标。关于点的坐标的计算,这里不进行过多的讲解,读者对照程序代码去理解吧。
    这三个点的坐标得到以后,就可以组成四条直线:p1和1,1和3,3和2,2和p2,分别以这四条直线的起点、终点坐标为参数代入函数Draw中,进行递归调用。

      Draw(pdc, p1, tempp1);
Draw(pdc, tempp1, tempp3);
Draw(pdc, tempp3, tempp2);
Draw(pdc, tempp2, p2);

一切准备好以后,就可以到程序的主体里去获取我们想要得到的结果了。

      KSQXClass myksqx;
KSQXPoint p1, p2;
p1.m_x = 100;
p1.m_y = 300;
p2.m_x = 400;
p2.m_y = 300;
myksqx.SetLimit(1);
CDC* pdc;
pdc = GetDC();
myksqx.Draw(pdc, p1, p2);

程序运行结果如本文图一所示。
关于代码和文章中的问题大家可以和作者联系:
通信地址:吉林省长春市西民主大街6号地球探测科学与技术学院2001级硕士研究生 胡卓玮
电子信箱:QiGi@vip.sina.com
欢迎访问作者的主页:forevergis.6to23.com

Read: 852

启程动态数组V2.0

作者:黄建雄

下载源代码

简介
大量数据的管理是很多程序员的心病,很难找到一个速度快、效率高、支持超大规模数据的表,在1.0版本的基础上,启程花血本写下了这个强化了数据插入 与删除的修正版,启程动态数组是一个功能强大的列表形数据管理链表,利用它可以轻松实现超大数据量的随机插入、删除、修改等操作,它另外一个特点就是速度 极快,内存利用率高。
大量数据的管理必然需要占用大量的内存空间,如果这些数据占用的空间大小是随各种条件变化的,我们就不能使用数组来管理这些数据了(道理就不多说 了),这时我们需要一个动态数组。MFC提供了一个很好的动态数组类CArray,对于少量数据,使用CArray就足够好用了,但是对于大量数据 (10W级)它就力不从心了,因为它的本质就是一个数组,只不过对常用的插入、删除等操作进行了一个复杂的包装。为了解决这个问题,启程动态数组开创性地 将链表与数组巧妙的结合起来,既有数组的高速随机索引的优点,又有链表的数据量灵活多变的特点。

工作原理
启程动态数组的数据结构如图(这是1.0版本的示意图,2.0版在结点中增加了一个指示当前数据段中已经使用的空间变量)。为了解决大量数据的动态存 储问题,启程动态数组将数据分段存放在链表的节点中,每一段可以保存一定数量的数据,如果数据量增加,则在内存中分配一个新数据段,如果数据减少则释放空 闲的数据段,从而有效地解决了该问题。相对于1.0版,2.0版中引入了每个结点中已使用空间用和总空闲空间两个变量,经过这个处理,在进行数据的插入删 除时就不再需要对整个数组中的数据进行移动而只需要对目标数据段做一个简单的处理。

插入数据
如果目标数据段有空闲位置,那么只需要将该段进行曲整理并插入数据;如果目标段没有空闲空间,启程动态数据自动在内存中申请一段新的数据,并将该数据段链接到链表中。

删除数据
找到目标段后,从目标数据段中删除目标数据,如果目标段中只包含目标数据,启程动态数组自动删除目标段,并维护好链表的完整性。

添加数据
检查最后一个数据段,如果有空间就不再分配,没有就申请订报的数据段。

随机索引(数据定位)
相比较普通链表在随机索引方面的不足,启程动态数组在这方面可以说是趋于完美。由于启程动态数组在数据结构上的优势,它在数据定位的时候是段式跳跃的 搜索,因此它的速度得到了有力的保障。另一方面,为了加速索引速度它还经过了特别的优化,就是设置了一个当前位置的指针,这样不仅在普通的索引中可以成倍 的提高速度,特别是在遍历类的操作时甚至可以达到数组的速度。

数据压缩
如果细心的人一定会发现,按照上面的模式中可能存在很严重的空间滥废,事实上如果不作处理也是如此,因为在的插入数据时,我只需要插入一个数据,结果 却申请了一个完整的数据段,这在空间有限的计算机中将会造成很大的问题。还记得上面提到的新引入的用来记录空闲空间数量的变量吗?好了,有了它,我们就可 以把握有多少空间没有利用到,当这个值达到一个的范围时,启程动态数组自动对它占用的空间进行整理,经过整理后不再需要的空间自动回收。当然您可也可强制 整理,只需要调用一个简单的接口就好了。

参数设置
启动动态数组的性能很大程度上依赖于参数的设置,关键的参数有勇有2个,一是数据段的大小,一是空闲空间压缩阀,这两个参数应该也是比较好理解的。数 据段的大小主要应该根据目标数据的容量及计算机的内存来设置,压缩阀则要考虑你的机器的内存以及插入、删除操作的频率。对于10万级的数据量,数据段设成 100就差不多了,如果需要大量进行插入、删除压缩阀可适应加大,否则反之。

执行性能
代码的性能估计是大家最为关心的问题,同时也是它存在的根本。由于没有其实的代码做参考,这里只能与MFC的CArray进行比较。在10万级综合操 作测试中,启程动态数组耗时300MS左右,而CArray则需要3000MS,而且因为启程动态数组的耗时与数据量基本是线性关系,而CArray则基 本是指数关系,因此数据量越大启程动态数组的性能优势越明显。

测试程序
在开发这个程序时写了一个相应的测试工具,界面如下图:

“efficiency compare”部分是进行性能比较的,其它的都是进行程序正确性测试用的。做完测试后可以用刷新来显示内存中的数据。

版本历史

  • 2.0:2004-6-3
  • 增强插入删除
  • 1.0:2003- 09-25

担保
本代码可以任意使用、修改、传播,但作者不对使用该链表造成的后果承担任何直接或间接责任。

写在最后
这是我以为写得最好的一段代码,拿出来共享只希望能够给大家带来一点点方便。如果大家觉得它有价值将是我最大的快乐!如果发现程序的bug请一定告诉我!希望大空用的开心。

联系方式

  • e-mail: huangjianxiong@sina.com.cn
  • 个人网站:http://setoutsoft.3322.net
  • Read: 798

    URL编码

    作者: Chandrasekhar Vuppalapati
    翻译:eastvc

    下载源代码

    本文的目的是设计一个完成URL编码的C++类。在我曾经的项目中,我需要从VC++ 6.0应用程序中POST数据,而这些数据需要进行URL编码。我在MSDN中查找能根据提供的字符串生成URL编码的相关类或API,但我没有找到,因 此我必须设计一个自己的URLEncode C++类。

    URLEncoder.exe是一个使用URLEncode类的MFC对话框程序。

    如何处理

    一些特殊字符在Internet上传送是件棘手的事情, 经URL编码特殊处理,可以使所有字符安全地从Internet传送。

    例如,回车的ASCII值是13,在发送FORM数据时候这就认为是一行数据的结束。

    通常,所有应用程序采用HTTP或HTTPS协议在客户端和服务器端传送数据。服务器端从客户端接收数据有两种基本方法:

    1、数据可以从HTTP头传送(COOKIES或作为FORM数据发送)
    2、可以包含在URL中的查询部分

    当数据包含在URL,它必须遵循URL语法进行编码。在WEB服务器端,数据自动解码。考虑一下下面的URL,哪个数据是作为查询参数。

    例如:http://WebSite/ResourceName?Data=Data

    WebSite是URL名称
    ResourceName可以是ASP或Servlet名称
    Data是需要发送的数据。如果MIME类型是Content-Type: application/x-www-form-urlencoded,则要求进行编码。

    RFC 1738

    RFC 1738指明了统一资源定位(URLs)中的字符应该是US-ASCII字符集的子集。这是受HTML的限制,另一方面,允许在文档中使用所有ISO- 8859-1(ISO-Latin)字符集。这将意味着在HTML FORM里POST的数据(或作为查询字串的一部分),所有HTML编码必须被编码。

    ISO-8859-1 (ISO-Latin)字符集

    在下表中,包含了完整的ISO-8859-1 (ISO-Latin)字符集,表格提供了每个字符范围(10进制),描述,实际值,十六进制值,HTML结果。某个范围中的字符是否安全。

    Character range(decimal) Type Values Safe/Unsafe
    0-31 ASCII Control Characters These characters are not printable Unsafe
    32-47 Reserved Characters ” ”!?#$%&”()*+,-./ Unsafe
    48-57 ASCII Characters and Numbers 0-9 Safe
    58-64 Reserved Characters :;<=>?@ Unsafe
    65-90 ASCII Characters A-Z Safe
    91-96 Reserved Characters []^_` Unsafe
    97-122 ASCII Characters a-z Safe
    123-126 Reserved Characters {|}~ Unsafe
    127 Control Characters ” ” Unsafe
    128-255 Non-ASCII Characters ” ” Unsafe

    所有不安全的ASCII字符都需要编码,例如,范围(32-47, 58-64, 91-96, 123-126)。
    下表描述了这些字符为什么不安全。

    Character Unsafe Reason Character Encode
    "<" Delimiters around URLs in free text %3C
    > Delimiters around URLs in free text %3E
    . Delimits URLs in some systems %22
    # It is used in the World Wide Web and in other systems to delimit a URL from a fragment/anchor identifier that might follow it. %23
    { Gateways and other transport agents are known to sometimes modify such characters %7B
    } Gateways and other transport agents are known to sometimes modify such characters %7D
    | Gateways and other transport agents are known to sometimes modify such characters %7C
    Gateways and other transport agents are known to sometimes modify such characters %5C
    ^ Gateways and other transport agents are known to sometimes modify such characters %5E
    ~ Gateways and other transport agents are known to sometimes modify such characters %7E
    [ Gateways and other transport agents are known to sometimes modify such characters %5B
    ] Gateways and other transport agents are known to sometimes modify such characters %5D
    ` Gateways and other transport agents are known to sometimes modify such characters %60
    + Indicates a space (spaces cannot be used in a URL) %20
    / Separates directories and subdirectories %2F
    ? Separates the actual URL and the parameters %3F
    & Separator between parameters specified in the URL %26

    如何实现

    字符的URL编码是将字符转换到8位16进制并在前面加上”%”前缀。例如,US-ASCII字符集中空格是10进制
    的32或16进制的20,因此,URL编码是%20。

    URLEncode: URLEncode是一个C++类,来实现字符串的URL编码。CURLEncode类包含如下函数:
    isUnsafeString
    decToHex
    convert
    URLEncode

    URLEncode()函数完成编码过程,URLEncode检查每个字符,看是否安全。如果不安全将用%16进制值进行转换并添加
    到原始字符串中。

    代码片断:

    class CURLEncode
    {
    private:
    static CString csUnsafeString;
    CString (char num, int radix);
    bool isUnsafe(char compareChar);
    CString convert(char val);

    public:
    CURLEncode() { };
    virtual ~CURLEncode() { };
    CString (CString vData);
    };

    bool CURLEncode::isUnsafe(char compareChar)
    {
    bool bcharfound = false;
    char tmpsafeChar;
    int m_strLen = 0;

    m_strLen = csUnsafeString.GetLength();
    for(int ichar_pos = 0; ichar_pos < m_strLen ;ichar_pos++)
    {
    tmpsafeChar = csUnsafeString.GetAt(ichar_pos);
    if(tmpsafeChar == compareChar)
    {
    bcharfound = true;
    break;
    }
    }
    int char_ascii_value = 0;
    //char_ascii_value = __toascii(compareChar);
    char_ascii_value = (int) compareChar;

    if(bcharfound == false && char_ascii_value > 32 &&
    char_ascii_value < 123)
    {
    return false;
    }
    // found no unsafe chars, return false
    else
    {
    return true;
    }

    return true;
    }

    CString CURLEncode::decToHex(char num, int radix)
    {
    int temp=0;
    CString csTmp;
    int num_char;

    num_char = (int) num;
    if (num_char < 0)
    num_char = 256 + num_char;

    while (num_char >= radix)
    {
    temp = num_char % radix;
    num_char = (int)floor(num_char / radix);
    csTmp = hexVals[temp];
    }

    csTmp += hexVals[num_char];

    if(csTmp.GetLength() < 2)
    {
    csTmp += ''0'';
    }

    CString strdecToHex(csTmp);
    // Reverse the String
    strdecToHex.MakeReverse();

    return strdecToHex;
    }

    CString CURLEncode::convert(char val)
    {
    CString csRet;
    csRet += "%";
    csRet += decToHex(val, 16);
    return csRet;
    }

    参考:

    URL编码: http://www.blooberry.com/indexdot/html/topics/urlencoding.htm.

    RFC 1866: The HTML 2.0 规范 (纯文本). 附录包含了字符表: http://www.rfc-editor.org/rfc/rfc1866.txt.

    Web HTML 2.0 版本(RFC 1866) : http://www.w3.org/MarkUp/html-spec/html-spec_13.html.

    The HTML 3.2 (Wilbur) 建议: http://www.w3.org/MarkUp/Wilbur/.

    The HTML 4.0 建议: http://www.w3.org/TR/REC-html40/.

    W3C HTML 国际化区域: http://www.w3.org/International/O-HTML.html.

    Read: 883

    简单快速的哈夫曼编码

    作者:Hatem Mostafa
    译者:happyparrot

    下载源代码

    介绍

    本文描述在网上能够找到的最简单,最快速的哈夫曼编码。本方法不使用任何扩展动态库,比如STL或者组件。只使用简单的C函数,比如:memset,memmove,qsort,malloc,realloc和memcpy。

    因此,大家都会发现,理解甚至修改这个编码都是很容易的。

    背景

    哈夫曼压缩是个无损的压缩算法,一般用来压缩文本和程序文件。哈夫曼压缩属于可变代码长度算法一族。意思是个体符号(例如,文本文件中的字符)用一个特定长度的位序列替代。因此,在文件中出现频率高的符号,使用短的位序列,而那些很少出现的符号,则用较长的位序列。

    编码使用

    我用简单的C函数写这个编码是为了让它在任何地方使用都会比较方便。你可以将他们放到类中,或者直接使用这个函数。并且我使用了简单的格式,仅仅输入输出缓冲区,而不象其它文章中那样,输入输出文件。

    bool CompressHuffman(BYTE *pSrc, int nSrcLen, BYTE *&pDes, int &nDesLen);
    bool DecompressHuffman(BYTE *pSrc, int nSrcLen, BYTE *&pDes, int &nDesLen);

    要点说明

    速度

    为了让它(huffman.cpp)快速运行,我花了很长时间。同时,我没有使用任何动态库,比如STL或者MFC。它压缩1M数据少于100ms(P3处理器,主频1G)。

    压缩

    压缩代码非常简单,首先用ASCII值初始化511个哈夫曼节点:

    CHuffmanNode nodes[511];

    for(int nCount = 0; nCount < 256; nCount++)
    nodes[nCount].byAscii = nCount;

    然后,计算在输入缓冲区数据中,每个ASCII码出现的频率:

    for(nCount = 0; nCount < nSrcLen; nCount++)
    nodes[pSrc[nCount]].nFrequency++;

    然后,根据频率进行排序:

    qsort(nodes, 256, sizeof(CHuffmanNode), frequencyCompare);

    现在,构造哈夫曼树,获取每个ASCII码对应的位序列:

    int nNodeCount = GetHuffmanTree(nodes);

    构造哈夫曼树非常简单,将所有的节点放到一个队列中,用一个节点替换两个频率最低的节点,新节点的频率就是这两个节点的频率之和。这样,新节点就是两个被替换节点的父节点了。如此循环,直到队列中只剩一个节点(树根)。

    // parent node
    pNode = &nodes[nParentNode++];

    // pop first child
    pNode->pLeft = PopNode(pNodes, nBackNode--, false);

    // pop second child
    pNode->pRight = PopNode(pNodes, nBackNode--, true);

    // adjust parent of the two poped nodes
    pNode->pLeft->pParent = pNode->pRight->pParent = pNode;

    // adjust parent frequency
    pNode->nFrequency = pNode->pLeft->nFrequency + pNode->pRight->nFrequency;

    这里我用了一个好的诀窍来避免使用任何队列组件。我先前就直到ASCII码只有256个,但我分配了511个(CHuffmanNode nodes[511]),前255个记录ASCII码,而用后255个记录哈夫曼树中的父节点。并且在构造树的时候只使用一个指针数组 (ChuffmanNode *pNodes[256])来指向这些节点。同样使用两个变量来操作队列索引(int nParentNode = nNodeCount;nBackNode = nNodeCount –1)。

    接着,压缩的最后一步是将每个ASCII编码写入输出缓冲区中:

    int nDesIndex = 0;

    // loop to write codes
    for(nCount = 0; nCount < nSrcLen; nCount++)
    {
    *(DWORD*)(pDesPtr+(nDesIndex>>3)) |=
    nodes[pSrc[nCount]].dwCode << (nDesIndex&7);
    nDesIndex += nodes[pSrc[nCount]].nCodeLength;
    }
    • (nDesIndex>>3): >>3 以8位为界限右移后到达右边字节的前面
    • (nDesIndex&7): &7 得到最高位.

    注意:在压缩缓冲区中,我们必须保存哈夫曼树的节点以及位序列,这样我们才能在解压缩时重新构造哈夫曼树(只需保存ASCII值和对应的位序列)。

    解压缩

    解压缩比构造哈夫曼树要简单的多,将输入缓冲区中的每个编码用对应的ASCII码逐个替换就可以了。只要记住,这里的输入缓冲区是一个包含每个ASCII 值的编码的位流。因此,为了用ASCII值替换编码,我们必须用位流搜索哈夫曼树,直到发现一个叶节点,然后将它的ASCII值添加到输出缓冲区中:

    int nDesIndex = 0;
    DWORD nCode;
    while(nDesIndex < nDesLen)
    {
    nCode = (*(DWORD*)(pSrc+(nSrcIndex>>3)))>>(nSrcIndex&7);
    pNode = pRoot;
    while(pNode->pLeft)
    {
    pNode = (nCode&1) ? pNode->pRight : pNode->pLeft;
    nCode >>= 1;
    nSrcIndex++;
    }
    pDes[nDesIndex++] = pNode->byAscii;
    }
    • (nDesIndex>>3): >>3 以8位为界限右移后到达右边字节的前面
    • (nDesIndex&7): &7 得到最高位.

    源文件: Huffman.cpp Huffman.h 请见本文提供的源代码压缩包。

    Read: 1618