首先为什么要做这样的判断呢?

当你要strcpy活着strcmp或者hash一个字符串的时候,传统的方法是每个byte进行比较。以strcpy为例,当一个字符串比较长,我们用32(或者64位)的字长进行copy的话,一次拷贝会拷贝4个byte,能节省很多时间(忽略内存对齐等情况)。

但是,使用32位的字长进行拷贝一个难点就是判断字符串的结尾,因为字符串长度不一定是4的整数倍,每次从内存中取4个byte,我们需要判断这4个byte中是否有某个byte是0,从而判断字符串是否结束。

Tagged with:
 

do{...}while(0)的意义和用法

On October 9, 2012, in C语言, 语言学习, by sponge

linux内核和其他一些开源的代码中,经常会遇到这样的代码:

do{
 ...
}while(0)

这样的代码一看就不是一个循环,do..while表面上在这里一点意义都没有,那么为什么要这么用呢?

Tagged with:
 

gcc的内联汇编取全局变量地址

On September 16, 2012, in C语言, 语言学习, by sponge

最近在优化一段代码的过程中,用到了gcc的内联汇编。代码中有用到了许多全局变量,比如:

char mi[10]={...};

开始的时候,我对全局变量的取址是这样的:

__asm__ ("movq (%2, %1, 1 ), %0"
        :"=r"(cookie)
        :"r"(index),"r"(mi)
        );

在一个函数中使用这段代码,一条指令完成了对mi数组的访问,但同时也存在问题,即mi的地址会占用一个寄存器,mi的地址要在早先的时间内被装载到寄存器中(指令由编译器自动生成),同时,被mi占用的寄存器有些情况下不能被其他手工内联的汇编指令随便写入,编译器还没有那么智能帮你讲寄存器的内容保存好。

综上,使用这种方法会存在两方面问题:
1、使用至少两条指令来读取全局变量
2、正确性要小心呵护。

但是,在gcc的O2选项下访问mi变量的时候,因为全局变量的地址在编译时是可以确定的,所以这样的代码

int tmp = mi[3];

反汇编出来是

mov 0x405600(%eax), %ebx;

其中,eax中存的是index,也就是3,ebx是tmp。0x405600是全局变量mi的地址,在编译时就确定了这个地址,所以直接写在指令中了。

由于没系统的学过内联汇编的语法,所以不知道怎么在C语言中直接嵌入全局变量的地址,尝试了几种方法,用约束"P","I"什么的都不行,google也没查到相关的方法,后来在某开源代码中搜了下“(%%”,发现真有类似的方法,原来gcc的内联函数可以直接饮用c的标示符的,可以用下面的代码实现相同的功能:

__asm__ ("movq mi(%1 ), %0"
        :"=r"(cookie)
        :"r"(index)
        );

在我之前优化的代码中这么修改了之后,速度确实提升了一些。

Tagged with:
 

URL相似度计算的思考

On April 24, 2012, in 其他, 算法, by sponge

在做一些web相关的工作的时候,我们往往可能需要做一些对url的处理,其中包括对相似的url的识别和处理。这就需要计算两个url的相似度。

那么怎么进行url相似度的计算的?我首先想到的是把一个url看作是一个字符串,这样就简化成两个字符串相似度的计算。字符串相似度计算有很多已经比较成熟的算法,比如“编辑距离算法”,该算法描述了两个字符串之间转换需要的最小的编辑次数;还有一些其他的比如“最长公共字串”等方法。但这些方法对于url相似度的计算来说是不是够了呢?比如给以下三个url:

url1: www.spongeliu.com/xxx/123.html
url2: www.spongeliu.com/xxx/456.html
url3: www.spongeliu.com/xxx/abc.html

这三个url的编辑距离是一致的,但是直观上我们却认为url1和url2更加相似一些。

再比如我们要判断两个站点是否同一套建站模版建立的,抽出两个url如下这样:
url1: www.163.com/go/artical/43432.html
url2: www.sina.com.cn/go/artical/453109.html

这两个url按照情景应该是相似的,这就超出了字符串相似度判断的能力范围。

Tagged with:
 

C语言可变参数函数取参方法

On February 26, 2012, in C语言, 语言学习, by sponge

熟悉C的人都知道,C语言支持可变参数函数(Variable Argument Functions),即参数的个数可以是不定个,在函数定义的时候用(...)表示,比如我们常用的printf()\execl函数等;printf函数的原型如下:

int printf(const char *format, ...);

注意,采用这种形式定义的可变参数函数,至少需要一个普通的形参,比如上面代码中的*format,后面的省略号是函数原型的一部分。

C语言之所以可以支持可变参数函数,一个重要的原因是C调用规范中规定C语言函数调用时,参数是从右向左压入栈的;这样一个函数实现的时候,就无需关心调用他的函数会传递几个参数过来,而只要关心自己用到几个;以printf为例:

printf("%d%s\n",i,s);

printf函数在定义的时候,不知道函数调用的时候会传递几个参数。在实现上,printf函数只需关心第一个参数,即字符串“%d%s\n”,当读到%d的时候,printf知道自己需要第二个参数,这时只需要去栈上寻找即可;当读到%s时,再去栈上网上寻找一个参数即可。简单说,printf不关心栈上到底压了多少参数,只关心自己需要多少。

那么对于一个定义为可变参数的函数,函数定义的时候并没有定义形参原型,怎么使用参数呢?

Tagged with:
 

很久以前,我接触的最初几本C语言书中,我记得有类似这么一句话“C语言是一种弱类型的语言,类型之间可以进行隐式的转换;而C++是强类型的语言,需要进行强制类型转换”。我忘了是哪本书,但这句话我一直记得。因为实际写代码中一直也没有触碰隐式的转换(我一般都会强制转换),所以也没有深究过这个问题。然而最近的一段代码却给我带来了一些困惑。
copyright@ www.spongeliu.com
先抛开我遇到的问题不说,简单回顾下C语言的隐式类型转换,如下一段代码:

#include <stdio.h>
double sum(double x, double y); //声明一个函数
 
int main()
{
    int x=10;
    int y=10;
 
    double z=sum(x,y);
    printf("%lf\n",z);
    return 0
}

没问题,我们得到的结果是20.000000。

一个十分有趣的字符串算法题目

On April 19, 2011, in 算法, by sponge

在blogspot上看到一个十分有趣的字符串算法题目,原文在这里。作者讲述了自己面试google的一次经历。本文不理会这个故事,只来讨论一下里面着个有趣的算法。

算法题目:有两个字符串由不同的字母组成,一长一短,长的为A短的为B。设计一个算法,如果所有在B中出现的字符都在A中出现,则返回true,否则返回false。
例子:

如下字符串:

字符串A: abddfdioegdddffsfagj
字符串B: dofsjadg

字符串B中每个字符都在A中出现,返回true。

如下字符串:

字符串A: aaaabbbbbbdddddd
字符串B: acc

字符串B中有字符没在A中出现,返回false。

Tagged with:
 

1、在安装openoffice过程中出现大致如下的错误

ERROR: Error 65280 occurred while making /var/tmp/portage/app-office/openoffice-3.2.1-r1/work/ooo/build/OOO320_m19/desktop/zipintro 
rmdir /var/tmp/portage/app-office/openoffice-3.2.1-r1/temp/yERj5YXC9A 
make: *** [stamp/build] Error 1 
* ERROR: app-office/openoffice-3.2.1-r1 failed: 
* Build failed 
* 
* Call stack: 
* ebuild.sh, line 54: Called src_compile 
* environment, line 8141: Called die 
* The specific snippet of code: 
* make || die "Build failed" 
* 
* If you need support, post the output of 'emerge --info =app-office/openoffice-3.2.1-r1', 
* the complete build log and the output of 'emerge -pqv =app-office/openoffice-3.2.1-r1'. 
!!! When you file a bug report, please include the following information: 
GENTOO_VM=sun-jdk-1.6 CLASSPATH="" JAVA_HOME="/opt/sun-jdk-1.6.0.22" 
JAVACFLAGS="-source 1.5 -target 1.5" COMPILER="" 
and of course, the output of emerge --info 
* The complete build log is located at '/var/log/portage/app-office:openoffice-3.2.1-r1:20101120-141010.log'. 
* The ebuild environment file is located at '/var/tmp/portage/app-office/openoffice-3.2.1-r1/temp/environment'. 
* S: '/var/tmp/portage/app-office/openoffice-3.2.1-r1/work/ooo' 
 
>>> Failed to emerge app-office/openoffice-3.2.1-r1, Log file: 
 
>>> '/var/log/portage/app-office:openoffice-3.2.1-r1:20101120-141010.log'

问题原因:openoffice依赖一个包imagemagick,该包编译时需要png。具体机制不详

解决方法: USE="png" emerge -av imagemagick openoffice

Tagged with:
 

这篇文章是一篇译文,跟上一篇文章相呼应的,原文在这里

对于结构体和空类大小是1这个问题,首先这是一个C++问题,在C语言下空结构体大小为0(当然这是编译器相关的)。这里的空类和空结构体是指类或结构体中没有任何成员。

在C++下,空类和空结构体的大小是1(编译器相关),这是为什么呢?为什么不是0?

这是因为,C++标准中规定,“no object shall have the same address in memory as any other variable” ,就是任何不同的对象不能拥有相同的内存地址。 如果空类大小为0,若我们声明一个这个类的对象数组,那么数组中的每个对象都拥有了相同的地址,这显然是违背标准的。

但是,也许你还有一个疑问,为什么C++标准中会有这么无聊的规定呢?

Tagged with:
 

c关键字-sizeof的种种

On November 14, 2010, in C语言, 语言学习, by sponge

熟悉c的人都知道,sizeof是一个关键字而不是一个宏或者库函数什么的,他的值是在编译时确定的,如果这个不了解,可以现看看这篇文章这篇文章

既然如此,让我们先看下面几个小例子:

sizeof(int);
sizeof(char);
sizeof(double);

上面三行sizeof的值是多少呢?这里我们假定在32位的x86系统下。我们会得到答案:4,1,8。这个没什么吧,大多数人都应该知道。那么,下面这个:

sizeof(int);
sizeof(long);

在32位x86下,这两个是多少呢?4,8?实际上,答案是4,4。我们需要注意,long类型在32位系统下是32位的。那么,64位下结果又如何呢?8,8?其实答案是4,8。另一个需要注意的是,64位下的int是32位的

Tagged with:
 
Page 1 of 41234