#include <stdio.h>
int main()
{
int a=1;
a=a-=a--;
printf("a=%d\n",a);
int size=sizeof(a=2);
printf("size=%d a=%d\n",size,a);
return 0;
}
输出
a=-1;
size=4 a=-1
2008年3月24日星期一
2008年3月15日星期六
baidu笔试题 IP段问题
Security公司的网络管理工程师Mr. leak最近发现有不少来自公司外部IP的请求，试图非法访问公司内部资源，为了不影响数据访问流程。
他不得不写一个高效的程序――一个工作在Ipv4上的防火墙，如果请求来自非授权的ip地址，则将请求丢弃。为了便于管理，通过文本文件IP.TXT
他不得不写一个高效的程序――一个工作在Ipv4上的防火墙，如果请求来自非授权的ip地址，则将请求丢弃。为了便于管理，通过文本文件IP.TXT
162.105.91.163
59.66.105.0 59.66.105.255
211.71.0.0 211.71.255.255
限制：IP段的起止地址间以空格隔开。文件不超过10万行，内存不超过4M字节。
要求：请编写一个程序，读入IP.TXT文件。并从标准输入接受一个IP地址。如果该地址在授权范围内，则在标准输出上打印Y,否则打印N.如果输入为一个空行，程序结束。
请给出思路（文字描述），完成代码，分析你采用算法的优劣。
请列举测试方法和思路
发信人: Curvelet (小曲线), 信区: Algorithm
标 题: Re: 谈一条网上的百度笔试题
发信站: 水木社区 (Mon Oct 15 20:59:18 2007), 站内
ip 段是可以合并的，
不需要用 trie 或者 interval tree，
用个数组+二分查找即可。
先把 ip 段改写成 ip 区间形式 [ip_a, ip_b]，
ip_a 是起始 ip 地址， ip_b 是结束 ip 地址。
现对所有 ip 区间按 ip_a 排序，
扫描一遍排序结果，
合并相交的 ip 区间，
结果存在一个数组中。
对于给定的 ip_c，
用二分查找在数组中找到最大的 ip_a <= ip_c，
然后看 ip_c 是否在查找到的区间中即可。
最多 10万行数据，每行对应两个 ip 共 8 字节，
最多 0.8MB。
ps:以ip_a升序排序，顺序扫描ip_b,并记录ip_b的最大值，若当前项的ip_a>以上ip_b 的最大值，则生成一个区间段，以下类似。
------------------------------------------------------------------------------------------------------------------------
2005年百度之星有道求重叠区间大小的题目，和上面的解题思路类似，上面是求并，这里是求交：
题目描述：请编写程序，找出下面"输入数据及格式"中所描述的输入数据文件中最大重叠区间的大小。
对一个正整数n，如果n在数据文件中某行的两个正整数（假设为A和B）之间，即A<=n<=B或A>=n>=B，则n属于
该行；如果n同时属于行i和j，则i和j有重叠区间；重叠区间的大小是同时属于行i和j的整数个数。
例如，行（10 20）和（12 25）的重叠区间为[12 20]，其大小为9；行（20 10）和（12 18）的重叠区间为
[12 18]，其大小为7；行(20 10)和（20 30）的重叠区间大小为1。
输入数据：程序读入已被命名为input.txt的输入数据文本文件，该文件的行数在1到1,000,000之间，每行有
用一个空格分隔的2个正整数，这2个正整数的大小次序随机，每个数都在1和2^32-1之间。（为便于调试，
您可下载测试input.txt文件，实际运行时我们会使用不同内容的输入文件。）
输出数据：在标准输出上打印出输入数据文件中最大重叠区间的大小，如果所有行都没有重叠区间，则输出0。
评分标准：程序输出结果必须正确，内存使用必须不超过256MB，程序的执行时间越快越好。
思路：按起点降序排序，扫描一遍，维护当前线段之前的线段对后面造成的最远阴影
代码如下：
#include <stdio.h>
#include <stdlib.h>
struct node{
unsigned x;
unsigned y;
}a[1000000];
int compare(const void *a,const void *b)
{
struct node *da=(struct node*)a;
struct node *db=(struct node*)b;
return (da->x)<(db->x);
}
int main()
{
unsigned i,j;
unsigned n=0;
freopen("qujian.txt","r",stdin);
while(scanf("%u%u",&i,&j)!=EOF)
{
if(i<j)
{
a[n].x=i;
a[n].y=j;
}
else
{
a[n].x=j;
a[n].y=i;
}
n++;
}
qsort(a,n,sizeof(struct node),compare); //以x 降序排序
unsigned max;
unsigned tmp;
unsigned ans=0;
max=a[0].y;
for(i=1;i<n;i++)
{
if(a[i].y>max)
{
tmp=max;
max=a[i].y;
}
else
tmp=a[i].y;
if((tmp-a[i].x+1)>ans) //以本节点x为起点对后面造成的最远阴影
ans=tmp-a[i].x+1;
}
printf("%u\n",ans);
return 0;
}
59.66.105.0 59.66.105.255
211.71.0.0 211.71.255.255
限制：IP段的起止地址间以空格隔开。文件不超过10万行，内存不超过4M字节。
要求：请编写一个程序，读入IP.TXT文件。并从标准输入接受一个IP地址。如果该地址在授权范围内，则在标准输出上打印Y,否则打印N.如果输入为一个空行，程序结束。
请给出思路（文字描述），完成代码，分析你采用算法的优劣。
请列举测试方法和思路
发信人: Curvelet (小曲线), 信区: Algorithm
标 题: Re: 谈一条网上的百度笔试题
发信站: 水木社区 (Mon Oct 15 20:59:18 2007), 站内
ip 段是可以合并的，
不需要用 trie 或者 interval tree，
用个数组+二分查找即可。
先把 ip 段改写成 ip 区间形式 [ip_a, ip_b]，
ip_a 是起始 ip 地址， ip_b 是结束 ip 地址。
现对所有 ip 区间按 ip_a 排序，
扫描一遍排序结果，
合并相交的 ip 区间，
结果存在一个数组中。
对于给定的 ip_c，
用二分查找在数组中找到最大的 ip_a <= ip_c，
然后看 ip_c 是否在查找到的区间中即可。
最多 10万行数据，每行对应两个 ip 共 8 字节，
最多 0.8MB。
ps:以ip_a升序排序，顺序扫描ip_b,并记录ip_b的最大值，若当前项的ip_a>以上ip_b 的最大值，则生成一个区间段，以下类似。
------------------------------------------------------------------------------------------------------------------------
2005年百度之星有道求重叠区间大小的题目，和上面的解题思路类似，上面是求并，这里是求交：
题目描述：请编写程序，找出下面"输入数据及格式"中所描述的输入数据文件中最大重叠区间的大小。
对一个正整数n，如果n在数据文件中某行的两个正整数（假设为A和B）之间，即A<=n<=B或A>=n>=B，则n属于
该行；如果n同时属于行i和j，则i和j有重叠区间；重叠区间的大小是同时属于行i和j的整数个数。
例如，行（10 20）和（12 25）的重叠区间为[12 20]，其大小为9；行（20 10）和（12 18）的重叠区间为
[12 18]，其大小为7；行(20 10)和（20 30）的重叠区间大小为1。
输入数据：程序读入已被命名为input.txt的输入数据文本文件，该文件的行数在1到1,000,000之间，每行有
用一个空格分隔的2个正整数，这2个正整数的大小次序随机，每个数都在1和2^32-1之间。（为便于调试，
您可下载测试input.txt文件，实际运行时我们会使用不同内容的输入文件。）
输出数据：在标准输出上打印出输入数据文件中最大重叠区间的大小，如果所有行都没有重叠区间，则输出0。
评分标准：程序输出结果必须正确，内存使用必须不超过256MB，程序的执行时间越快越好。
思路：按起点降序排序，扫描一遍，维护当前线段之前的线段对后面造成的最远阴影
代码如下：
#include <stdio.h>
#include <stdlib.h>
struct node{
unsigned x;
unsigned y;
}a[1000000];
int compare(const void *a,const void *b)
{
struct node *da=(struct node*)a;
struct node *db=(struct node*)b;
return (da->x)<(db->x);
}
int main()
{
unsigned i,j;
unsigned n=0;
freopen("qujian.txt","r",stdin);
while(scanf("%u%u",&i,&j)!=EOF)
{
if(i<j)
{
a[n].x=i;
a[n].y=j;
}
else
{
a[n].x=j;
a[n].y=i;
}
n++;
}
qsort(a,n,sizeof(struct node),compare); //以x 降序排序
unsigned max;
unsigned tmp;
unsigned ans=0;
max=a[0].y;
for(i=1;i<n;i++)
{
if(a[i].y>max)
{
tmp=max;
max=a[i].y;
}
else
tmp=a[i].y;
if((tmp-a[i].x+1)>ans) //以本节点x为起点对后面造成的最远阴影
ans=tmp-a[i].x+1;
}
printf("%u\n",ans);
return 0;
}
baidu笔试题 数据检索问题 from smth
三、 现有两个文件，
a)数据文件A，格式为：关键词、IP地址、时间
a)数据文件A，格式为：关键词、IP地址、时间
，记录条数为1000万左右，该文件是无序排列的。
b)数据文件B是关键词ID到关键词的对应表文件，格式为：ID、关键词，记录条数在100万左右，也是无序排列的。该对应表中的记录是一一对应的，不存在ID或者关键词重复的情况。
要求将数据文件A对应的关键词替换为B中的ID，生成新的数据文件C，数据文件C的格式为：关键词ID、IP地址、时间。
请设计一个程序，实现上述功能，并分析时间复杂度和空间复杂度。运行程序所使用的服务器的内存为1G，硬盘足够大。(至少要给出关键算法和设计思路)
简评：
如何对海量数据进行快速检索，这是搜索引擎的必需考虑的问题。这又涉及到数
b)数据文件B是关键词ID到关键词的对应表文件，格式为：ID、关键词，记录条数在100万左右，也是无序排列的。该对应表中的记录是一一对应的，不存在ID或者关键词重复的情况。
要求将数据文件A对应的关键词替换为B中的ID，生成新的数据文件C，数据文件C的格式为：关键词ID、IP地址、时间。
请设计一个程序，实现上述功能，并分析时间复杂度和空间复杂度。运行程序所使用的服务器的内存为1G，硬盘足够大。(至少要给出关键算法和设计思路)
简评：
如何对海量数据进行快速检索，这是搜索引擎的必需考虑的问题。这又涉及到数
据结构和算法。 因此，要想进入百度，就必须熟悉一些基本的算法和数据结构。
思路及解决方案如下：
1: 设计用TRIE树实现关键词到其对应id的快速词典查找
TRIE树的每一个节点为一个包含256个元素的数组，同时指针指向其下一级节点
节点定义如下：
struct trienode
{
int id;
struct trienode *child[256];
}TRIENODE;
如果TRIE树的某个节点的指针为NULL，说明从跟节点到当前节点的路径构成文件
B中的一个关键词，
在其节点的id保存该关键词的id;如果指针不为NULL，则id对应为0或者一个无穷
大的整数，标志从根节点
到当前节点的路径不是一个完整的关键词。
将关键词转化为二进制无符号char型数组，即对于汉字等双字节字符视为两个无
符号char型整数，
每个元素的取值范围在0到255之间。
2：生成文件b的TRIE树
步骤1：依次读取文件b的每一行，对每一行执行步骤2到步骤5
步骤2：读取关键词id和关键词，令为key
步骤3：依次读取key的每一个字符，对每一个字符，执行步骤4
思路及解决方案如下：
1: 设计用TRIE树实现关键词到其对应id的快速词典查找
TRIE树的每一个节点为一个包含256个元素的数组，同时指针指向其下一级节点
节点定义如下：
struct trienode
{
int id;
struct trienode *child[256];
}TRIENODE;
如果TRIE树的某个节点的指针为NULL，说明从跟节点到当前节点的路径构成文件
B中的一个关键词，
在其节点的id保存该关键词的id;如果指针不为NULL，则id对应为0或者一个无穷
大的整数，标志从根节点
到当前节点的路径不是一个完整的关键词。
将关键词转化为二进制无符号char型数组，即对于汉字等双字节字符视为两个无
符号char型整数，
每个元素的取值范围在0到255之间。
2：生成文件b的TRIE树
步骤1：依次读取文件b的每一行，对每一行执行步骤2到步骤5
步骤2：读取关键词id和关键词，令为key
步骤3：依次读取key的每一个字符，对每一个字符，执行步骤4
;
步骤4：如果该字符对应的指针为NULL，则创建其儿子节点;
步骤5：为当前节点的对应字符id置为关键词id
3：根据A文件生成C文件
步骤1：依次读取文件A的每一行，对每一行执行步骤2到步骤5
步骤2：分别获取当前行关键词、ip地址和时间
步骤3：令关键词key=c1c2...cm，对c1到cm每个字符，执行步骤4
步骤4：获取根节点的第c1个元素指针，转移到节点node1，
根据node1的第c2个元素指针，转移到node2...
根据nodem的第cm个元素，获取关键词的id
步骤5：往文件c中写入一行数据，格式为关键词的id、ip地址和时间
4：复杂度分析
生成文件B的TRIE树过程时间复杂度为O(n*m)，其中n为文件b行数，m为文件b关
键词的最大长度。TRIE的空间复杂度为O(n*m)，n和m含义同上，但由于实际应用中关
键词之间可能会有很多前缀相同现象，所以实际耗费空间并不会很高。
生成C文件的时间复杂度同样为O(n*m)，n为文件a行数，m为文件a关键词的最大
长度，因为有了TRIE树之后，给定一个关键词获得其id的时间复杂度为关键词长度。
生成C文件的过程除了TRIE树空间外基本不需要太多额外的空间，空间复杂度为O(1)
，由于系统有1G的可用内存，TRIE占用的空间在几十兆到200M之间(与关键词集合有
关)，因此本方法完全可行。
步骤4：如果该字符对应的指针为NULL，则创建其儿子节点;
步骤5：为当前节点的对应字符id置为关键词id
3：根据A文件生成C文件
步骤1：依次读取文件A的每一行，对每一行执行步骤2到步骤5
步骤2：分别获取当前行关键词、ip地址和时间
步骤3：令关键词key=c1c2...cm，对c1到cm每个字符，执行步骤4
步骤4：获取根节点的第c1个元素指针，转移到节点node1，
根据node1的第c2个元素指针，转移到node2...
根据nodem的第cm个元素，获取关键词的id
步骤5：往文件c中写入一行数据，格式为关键词的id、ip地址和时间
4：复杂度分析
生成文件B的TRIE树过程时间复杂度为O(n*m)，其中n为文件b行数，m为文件b关
键词的最大长度。TRIE的空间复杂度为O(n*m)，n和m含义同上，但由于实际应用中关
键词之间可能会有很多前缀相同现象，所以实际耗费空间并不会很高。
生成C文件的时间复杂度同样为O(n*m)，n为文件a行数，m为文件a关键词的最大
长度，因为有了TRIE树之后，给定一个关键词获得其id的时间复杂度为关键词长度。
生成C文件的过程除了TRIE树空间外基本不需要太多额外的空间，空间复杂度为O(1)
，由于系统有1G的可用内存，TRIE占用的空间在几十兆到200M之间(与关键词集合有
关)，因此本方法完全可行。
2008年3月14日星期五
baidu笔试mp3搜索问题 from smth
四、设计题：35分 共1题
注意：请尽可能详细描述你的数据结构、系统架构、设计思路等
注意：请尽可能详细描述你的数据结构、系统架构、设计思路等
。建议多写一些伪代码或者流程说明。
1. 假设一个mp3搜索引擎收录了2^24首歌曲，并记录了可收听这些歌曲的2^30条URL，但每首歌的URL不超过2^10个。系统会定期检查这些URL，如果一个URL不可用则不出现在搜索结果中。现在歌曲名和URL分别通过整型的SONG_ID和URL_ID唯一确定。对该系统有如下需求：
1) 通过SONG_ID搜索一首歌的URL_ID，给出URL_ID计数和列表
2) 给定一个SONG_ID，为其添加一个新的URL_ID
3) 添加一个新的SONG_ID
4) 给定一个URL_ID，将其置为不可用
限制条件：内存占用不超过1G，单个文件大小不超过2G，一个目录下的文件数不超过128个。
为获得最佳性能，请说明设计的数据结构、搜索算法，以及资源消耗。如果系统数据量扩大，该如何多机分布处理？
:================================================
内存不够存储这些url，所以将数据写入若干个文件中。
每一首歌曲对应的存储在文件中的信息格式为（url1, url2……）。
文件的总大小大约为2^24*2^10*4 =2^36 =64GB.根据SongID即可计算出在哪个文件的哪个位置，那么一个随机的查询操作耗时即是一次随机打开文件啊并执行seek操作读取数据的实际，大约是ms级别。
将每首歌曲的信息存入文件中，由于每首歌的url不超过2^10个，所以在文件中每首歌的存储结构是2^10个int数，每个int数字标识着一个url。-1表示url不存在。初始化时将文件中每个int数初始化为-1.
这样每个SongID对应的信息占用的空间为2^10*4=4KB，设每个文件大小1G，那么每个文件可存储2^18=256K个Song的信息。总共需要64个文件，把这些文件编号从0-63.
对于任意一个SongID，他所对应的url信息所在的文件编号是：SongID>>18,在文件中的位置是：(SongID&0x3FFFF)<<12.
另外内存中用一个2^24大小的short int型数组来保存每一首歌曲对应的url的个数，计数组名为urlCount[]，初始化时值为-1,表示对应的Song_ID不存在。此数组占用空间2^25Byte=32MB;
url是否可用的信息用位图来标识。位图保存在内存中，占用的空间为2^30/8=2^27 Byte=128MB.
对所要求的操作：
:1) 通过SONG_ID搜索一首歌的URL_ID，给出URL_ID计数和列表
通过SONG_ID计算出文件号和对应在文件中的位置，从urlCount[]中读取url个数，读出所有的url,并对每个url_ID查询位图看是否可用，若可用，将此url加入返回列表。
:2) 给定一个SONG_ID，为其添加一个新的URL_ID
通过SONG_ID计算出文件号和对应在文件中的位置，设为start，在通过urlCount[]得到url个数，假设有n个url,那么将新的URL_ID写入文件的start+sizeof(int)*n处。修改urlCount[SONG_ID]的值。
:3) 添加一个新的SONG_ID
检查将对应的urlCount[SONG_ID]，若为-1，则修改为0,若大于等于0，则表明改Song_ID已经存在。
:4) 给定一个URL_ID，将其置为不可用
修改url位图，标识URL_ID对应的位，表示为不可用。
1. 假设一个mp3搜索引擎收录了2^24首歌曲，并记录了可收听这些歌曲的2^30条URL，但每首歌的URL不超过2^10个。系统会定期检查这些URL，如果一个URL不可用则不出现在搜索结果中。现在歌曲名和URL分别通过整型的SONG_ID和URL_ID唯一确定。对该系统有如下需求：
1) 通过SONG_ID搜索一首歌的URL_ID，给出URL_ID计数和列表
2) 给定一个SONG_ID，为其添加一个新的URL_ID
3) 添加一个新的SONG_ID
4) 给定一个URL_ID，将其置为不可用
限制条件：内存占用不超过1G，单个文件大小不超过2G，一个目录下的文件数不超过128个。
为获得最佳性能，请说明设计的数据结构、搜索算法，以及资源消耗。如果系统数据量扩大，该如何多机分布处理？
:================================================
内存不够存储这些url，所以将数据写入若干个文件中。
每一首歌曲对应的存储在文件中的信息格式为（url1, url2……）。
文件的总大小大约为2^24*2^10*4 =2^36 =64GB.根据SongID即可计算出在哪个文件的哪个位置，那么一个随机的查询操作耗时即是一次随机打开文件啊并执行seek操作读取数据的实际，大约是ms级别。
将每首歌曲的信息存入文件中，由于每首歌的url不超过2^10个，所以在文件中每首歌的存储结构是2^10个int数，每个int数字标识着一个url。-1表示url不存在。初始化时将文件中每个int数初始化为-1.
这样每个SongID对应的信息占用的空间为2^10*4=4KB，设每个文件大小1G，那么每个文件可存储2^18=256K个Song的信息。总共需要64个文件，把这些文件编号从0-63.
对于任意一个SongID，他所对应的url信息所在的文件编号是：SongID>>18,在文件中的位置是：(SongID&0x3FFFF)<<12.
另外内存中用一个2^24大小的short int型数组来保存每一首歌曲对应的url的个数，计数组名为urlCount[]，初始化时值为-1,表示对应的Song_ID不存在。此数组占用空间2^25Byte=32MB;
url是否可用的信息用位图来标识。位图保存在内存中，占用的空间为2^30/8=2^27 Byte=128MB.
对所要求的操作：
:1) 通过SONG_ID搜索一首歌的URL_ID，给出URL_ID计数和列表
通过SONG_ID计算出文件号和对应在文件中的位置，从urlCount[]中读取url个数，读出所有的url,并对每个url_ID查询位图看是否可用，若可用，将此url加入返回列表。
:2) 给定一个SONG_ID，为其添加一个新的URL_ID
通过SONG_ID计算出文件号和对应在文件中的位置，设为start，在通过urlCount[]得到url个数，假设有n个url,那么将新的URL_ID写入文件的start+sizeof(int)*n处。修改urlCount[SONG_ID]的值。
:3) 添加一个新的SONG_ID
检查将对应的urlCount[SONG_ID]，若为-1，则修改为0,若大于等于0，则表明改Song_ID已经存在。
:4) 给定一个URL_ID，将其置为不可用
修改url位图，标识URL_ID对应的位，表示为不可用。
2008年3月11日星期二
常用字符串Hash函数
// RS Hash Function
unsigned int RSHash(char *str)
{
unsigned int b=378551;
unsigned int a=63689;
unsigned int hash=0;
while(*str)
{
hash=hash*a+(*str++);
a*=b;
}
return (hash & 0x7fffffff);
}
//JS Hash Function
unsigned int JSHash(char *str)
{
unsigned int hash=1315423911;
while(*str)
{
hash^=((hash << 5)+(*str++)+(hash>>2));
}
return (hash & 0x7fffffff);
}
//P.J Weinberger Hash Function
unsigned int PJWHash(char *str)
{
unsigned int BitsInUnignedInt=(unsigned int)(sizeof(unsigned int)*8);
unsigned int ThreeQuarters=(unsigned int)((BitsInunignedInt*3)/4);
unsigned int OneEighth=(unsigned int)(BitsInUnignedInt/8);
unsigned int hash=0;
unsigned int test=0;
while(*str)
{
hash=(hash<<OneEighth)+(*str++);
if((test=hash & HighBits)!=0)
{
hash=((hash^(test>>ThreeQuarters)) & (^HighBits));
}
}
return (hash & 0x7fffffff);
}
//ELF Hash Function
unsigned int ELFHash(char *str)
{
unsigned int hash=0;
unsigned int x=0;
while(*str)
{
hash=(hash<<4)+(*str++);
if((x=hash & 0xf0000000L)!=0)
{
hash^=(x>>24);
hash &=~x;
}
}
return (hash & 0x7fffffff);
}
//BKDR Hash Function
unsigned int BKDRHash(char *str)
{
unsigned int seed=131;//31 131 1313 13131 131313 etc..
unsigned int hash=0;
while(*str)
{
hash=hash*seed+(*str++);
}
return (hash & 0x7fffffff);
}
//SDBM Hash Function
unsigned int SDBMHash(char *str)
{
unsigned int hash=0;
while(*str)
{
hash+=(hash<<5)+(*str++);
}
return (hash & 0x7fffffff);
}
//AP Hash Function
unsigned int APHash(char *str)
{
unsigned int hash=0;
int i;
for(i=0;*str;i++)
{
if((i&1)==0)
{
hash^=((hash<<7)^(*str++)^(hash>>3));
}
else
{
hash^=(~((hash<<11)^(*str++)^(hash>>5)));
}
}
return (hash & 0x7fffffff);
}
//ELF hash Function比较常用
unsigned int RSHash(char *str)
{
unsigned int b=378551;
unsigned int a=63689;
unsigned int hash=0;
while(*str)
{
hash=hash*a+(*str++);
a*=b;
}
return (hash & 0x7fffffff);
}
//JS Hash Function
unsigned int JSHash(char *str)
{
unsigned int hash=1315423911;
while(*str)
{
hash^=((hash << 5)+(*str++)+(hash>>2));
}
return (hash & 0x7fffffff);
}
//P.J Weinberger Hash Function
unsigned int PJWHash(char *str)
{
unsigned int BitsInUnignedInt=(unsigned int)(sizeof(unsigned int)*8);
unsigned int ThreeQuarters=(unsigned int)((BitsInunignedInt*3)/4);
unsigned int OneEighth=(unsigned int)(BitsInUnignedInt/8);
unsigned int hash=0;
unsigned int test=0;
while(*str)
{
hash=(hash<<OneEighth)+(*str++);
if((test=hash & HighBits)!=0)
{
hash=((hash^(test>>ThreeQuarters)) & (^HighBits));
}
}
return (hash & 0x7fffffff);
}
//ELF Hash Function
unsigned int ELFHash(char *str)
{
unsigned int hash=0;
unsigned int x=0;
while(*str)
{
hash=(hash<<4)+(*str++);
if((x=hash & 0xf0000000L)!=0)
{
hash^=(x>>24);
hash &=~x;
}
}
return (hash & 0x7fffffff);
}
//BKDR Hash Function
unsigned int BKDRHash(char *str)
{
unsigned int seed=131;//31 131 1313 13131 131313 etc..
unsigned int hash=0;
while(*str)
{
hash=hash*seed+(*str++);
}
return (hash & 0x7fffffff);
}
//SDBM Hash Function
unsigned int SDBMHash(char *str)
{
unsigned int hash=0;
while(*str)
{
hash+=(hash<<5)+(*str++);
}
return (hash & 0x7fffffff);
}
//AP Hash Function
unsigned int APHash(char *str)
{
unsigned int hash=0;
int i;
for(i=0;*str;i++)
{
if((i&1)==0)
{
hash^=((hash<<7)^(*str++)^(hash>>3));
}
else
{
hash^=(~((hash<<11)^(*str++)^(hash>>5)));
}
}
return (hash & 0x7fffffff);
}
//ELF hash Function比较常用
2008年3月5日星期三
Inline assembly for x86 in Linux
Inline assembly for x86 in Linux
1.Register names are prefixed by %. That is, if eax has to be used, it should be used as %eax.
2.In any instruction, source comes first and destination follows. This differs from Intel syntax, where source comes after destination.
3. An immediate operand is specified by using $.
4. Any indirect references to memory are done by using ( ).
5.GCC provides the special construct "asm" for inline assembly, which has the following format:
1.Register names are prefixed by %. That is, if eax has to be used, it should be used as %eax.
2.In any instruction, source comes first and destination follows. This differs from Intel syntax, where source comes after destination.
3. An immediate operand is specified by using $.
4. Any indirect references to memory are done by using ( ).
5.GCC provides the special construct "asm" for inline assembly, which has the following format:
asm ( assembler template
: output operands (optional)
: input operands (optional)
: list of clobbered registers (optional)
);
6.a %eax
b %ebx
c %ecx
d %edx
S %esi
D %edi
7.Memory operand constraint(m)
When the operands are in the memory, any operations performed on them will occur directly in
the memory location, as opposed to register constraints, which first store the value in a
register to be modified and then write it back to the memory location. But register constraints
are usually used only when they are absolutely necessary for an instruction or they significantly
speed up the process. Memory constraints can be used most efficiently in cases where a C
variable needs to be updated inside "asm" and you really don't want to use a register to hold
its value.
2008年3月4日星期二
MMX
第五章 MMX™的编码技术
本节包括几个简单的例子来帮助你开始编写应用程序，最终目的是提供一些经常使用的、简单的低级操作。每个例子都使用最少的指令数来达到奔腾和P6系统处理器的最佳性能。
每个例子包括：
- 一个简短的描述
- 核心代码
- 必要的解释
考虑到你可能会将这些例子插入到更长的代码序列中，故这些例子中不涉及有关调度问题。
5.1 无符号分组
MMX™技术提供了几条用来将MMX™寄存器中的数据成组和分组的指令。分组指令可用于对一个无符号数进行零扩展(zero-extend)。下例假设源操作数是一个字组数据(16位)类型。
输入：
MM0: 源值
MM7: 0
如果需要，可用一个局部变量代替MM7寄存器。
输出：
MM0: 由2个低端字数据经零扩展形成的两个32位双字。
MM1: 由2个高端字数据经零扩展形成的两个32位双字。
MOVQ MM1, MM0 ;源数据复制
PUNPCKLWD MM0, MM7 ;将两个低端字数据分组为两个32位双字
PUNPCKHWD MM1, MM7 ;将两个高端字数据分组为两个32位双字
5.2 有符号分组
当对一个分组时，应对有符号数进行符号扩展(sign-extend)。这一点与上述零扩展不同。下例假设源操作数是一个成组字数据(16位)类型。
输入：
MM0: 源值
输出：
MM0: 由2个低端字数据经符号扩展形成的两个32位双字。
MM1: 由2个高端字数据经符号扩展形成的两个32位双字。
PUNPCKHWD MM1, MM0 ;将源数据的两个高端字数据分组为
;目标数据的第2个和第4个字数据
PUNPCKHLD MM0, MM0 ;将源数据的两个低端字数据分组为
;目标数据的第2个和第4个字数据
PSRAD MM0, 16 ;将源数据的两个低端字数据
;经符号扩展形成的两个32位双字
PSRAD MM1, 16 ;将源数据的两个高端字数据
;经符号扩展形成的两个32位双字
5.3 饱和模式下的交错成组
PACK指令按预先定义的顺序将两个值合并到目的寄存器。特别说明的是，PACKSSDW指令将源操作数两个有符号双字和目的操作数的两个有符号双字合并成目的寄存器中的四个有符号字。如图5一1所示：
| |
下例将两个值交错送入目的寄存器，如图5一2所示。
| |
本例中源操作数为有符号的双字，结果是交错的有符号字。成组指令不论是否是饱和模式都可执行。
输入：
MM0: 第一个有符号源值
MM1: 第二个有符号源值
输出：
MM0: 第一、三字来自MM0中的饱和模式有符号双字，
第二、四字来自MM1中的饱和模式有符号双字。
PACKSSDW MM0, MM0 ;饱和模式有符号成组
PACKSSDW MM1, MM1 ;饱和模式有符号成组
PUNPKLWD MM0, MM1 ;将操作数低端16位值交错
成组指令总是假设源操作数为有符号数。目的寄存器中的结果由执行操作的成组指令定 义。例如，PACKSSDW指令将两个源数据中各自的两个有符号32位值形成目的寄存器中的四个饱和的16位有符号值。另一方面，PACKUSWB指令将 两个源数据中各自的四个有符号16位值形成目的寄存器中的四个饱和的8位无符号值。有关MMX™指令集的完整说明请见《Intel体系结构MMX™技术程 序员参考手册》(Inte1 Architecture MMX™ Technology Programmers Reference Manual)，(序号243007)。
5.4 非饱和模式下的交错成组
本例除结果字为非饱和的外，同上例相似。另外，为防止溢出，本操作只使用每个双字的低16位。
输入：
MM0: 有符号源值
MM1: 有符号源值
输出：
MM0: 第一、三字来自MM0中的双字的低16位，
第二、四字来自MM1中的的双字的低16位。
PSLLD MM1, 16 ;将每个双字值中的LSB移16位
;到MSB位置
PAND MM0, {0, FFFF, 0, FFFF}
;将每个双字值的16MSB标记为0
POR MM0, MM1 ;合并两个操作数
5.5 非交错分组
分组指令将目的操作数和源操作数的数据元素交错合并到目的寄存器中。下例非交错地 将两个操作数合并到目的寄存器中。例如，从源数据1中的字组数据类型中取两个相邻元素，并将该值放到结果的低32位中。然后从源数据2中的字组数据类型中 取两个相邻元素，并将该值放到结果的高32位中。目的寄存器的一种组合形式如图5一3所示。
| |
目的寄存器的另一种相反的组合如图5一4所示。
| |
下例将两个字组的源数据按非交错方式分组。其实现方法为用将双字变为四字的指令代替将字变为双字的分组指令。
输入：
MM0: 字组源值
MM1: 字组源值
输出：
MM0: 包含两个非交错的初始源值的低端字
MM2: 包含两个非交错的初始源值的高端字
MOVQ MM2, MM0 ;复制源值1
PUNPCKLDQ MM0, MM1 ;用MMl的两个低端字替换MM0的两个高端字，
;保留MM0中的两个低端字
PUNPCKHDQ MM2, MM1 ;将MM2的两个高端字移到低端，
;将MM1的两个高端字送入MM2的两个高端字
5.6 含有一个常数的复数乘法
复数的乘法由四个乘法和两个加法构成。PMADDWD正是这样的指令。为了使用该指令，仅需将数据格式化为四个16位值。每个实部和虚部值应为16位值。
令输入数据为Dr和Di
这里 Dr=数据的实部
Di=数据的虚部
将复数的常系数格式化为内存中的四个16位值[Cr -Ci Ci Cr]。
记住使用MOVQ指令将值取出送到MMX™寄存器中。
输入：
MM0: 由Dr,Di构成的复数
MM1: 在格式[Cr -Ci Ci Cr]中的常复数系数
输出：
MM0: 包含[Pr Pi]的两个32位双字复数，
其实部是由Pr=Dr*Cr-Di*Ci生成，
复数的虚部是由Pi=Dr*Ci+Di*Cr生成。
PUNPCKLDQ MM0，MM0 ;生成［Dr Di Dr Di］
PMADDWD MM0，MM1 ;结果为[(Dr*Cr-Di*Ci)(Dr*Ci+Di*Cr)]
注意，输出为一个字组。如果需要，可用一条成组指令将结果转换为16位值(与输入格式匹配)。
5.7 无符号数差值的绝对值
本例计算两个无符号数差值的绝对值。假设是一个无符号字节组数据类型。这里，我们使用无符号饱和模式下的减法指令。指令按无符号饱和方式将无符号操作数相减。仅支持字节组和字组，不支持双字组。
输入：
MM0: 源操作数
MM1: 源操作数
输出：
MM0: 无符号数差值的绝对值
MOVQ MM2, MM0 ;制做MMO的备份
PSUBSB MM0, MM1 ;计算差值方法1
PSUBSB MM1, MM2 ;计算差值方法2
POR MM0, MM1 ;将两个差值求或
如果操作数有符号，本例不执行。有关有符号差值的绝对值请见下一个例子。
5.8 有符号数差值的绝对值
本例计算两个有符号数差值的绝对值。MMX™指令中没有按无符号饱和方式对有符号 操作数进行减法的操作。这里使用的技巧是，先将两个输入的操作数的对应元素按大小排序，生成一个较大的字组数据和一个较小的字组数据。然后，用较大的值减 去较小的值，就生成了所要求的差值的绝对值。关键是由B=XOR(A，XOR(A,B))和A=XOR(A,0)构成的快速排序技术。然后在成组数据类型 中，使某些元素为XOR(A,B)，某些为0，你可以将这一操作数与A进行XOR操作，并在某些地方生成A,某些地方生成B。下例假设一个字组数据类型， 每个元素为一个有符号数值。
输入：
MM0: 有符号源操作数
MM1: 有符号源操作数
输出：
MM0: 有符号数的差值的绝对值
MOVQ MM2, MM0 ;制做源操作数1的备份(A)
PCMPGTW MM0, MM1 ;取得源操作数1>源操作数2的标志
MOVQ MM4, MM2 ;制做源操作数A的另一个备份
PXOR MM2, MM1 ;生成交换操作XOR(A,B)的中间值
PAND MM2, MM0 ;生成0s和XOR(A,B)元素的标志
;当A>B为值XOR(A,B)，当A<=B为值0
MOVQ MM3, MM2 ;生成交换掩码的备份
PXOR MM4, MM2 ;XOR(A,swap mask)为较小值
PXOR MM1, MM3 ;XOR(B,swap mask)为较大值
PSUBW MM1, MM4 ;差值的绝对值=较大值-较小值
5.9 绝对值
当X为有符号数时，计算|X|。下例假设操作数为有符号字。
输入：
MM0: 有符号源操作数
输出：
MM1: ABS(MM0)
MOVQ MM1, MM0 ;备份X
PSRAW MM0, 15 ;复制符号位(是双字则用31位)
PXOR MM0, MM1 ;如负数则取1的补码
PSUBS MM1, MM0 ;如为负数则加1
注意 最大的负数(即16位的8000H)所求的绝对值不正确，但该代码对这种情况也是合理的，它使减一的结果为7fffH。
5.10 有符号数截取到任意有符号区域[HIGH,LOW]
本例说明了如何将一个有符号值截取到有符号区域[HIGH,LOW]。特别是当值小于LOW或大于HIGH时，截取到相应的LOW或HIGH中。本技术按无符号饱和方式进行成组数据加和成组数据减指令，该技术只能用于字节组和字组数据类型。
下例使用了最大成组数和最小成组数。
下例显示了对字数据值的操作。为简便起见，使用下列常数(在对字节值操作时，使用相应的常数)。
- PACKED_MAX=0x7FFF7FFF7FFF7FFF
- PACKED_MIN=0x8000800080008000
- PACKED_LOW包含了由LOW值构成的、字组数据类型中的全部4个字。
- PACKED_HIGH包含了由HIGH值构成的、字组数据类型中的全部4个字。
- PACKED_USMAX为全1。
- HIGH_US将HIGH值加到PACKED_MIN中的全部元素上。
- LOW_US将LOW值加到PACKED_MIN中的全部元素上。
本例显示了对字数据值的操作。
输入：
MM0: 有符号源操作数
输出：
MM0: 按无符号区域[HIGH,LOW]截取的有符号操作数
PADD MM0, PACKED_MIN ;非饱和方式相加并转换为无符号数
PADDUSW MM0, (PACKED_USMAX-HIGH_US)
;截取HIGH
PSUBUSW MM0, (PACKED_USMAX-HIGH_US+L0W_US)
;截取到LOW
PADDW MM0, PACKED_LOW ;取消前两个偏移量
上述代码先将值转换为无符号数，然后将它们截取到一个无符号区域。最后一条指令将数据转换为有符号数据，并置于有符号区域中。当数据(HIGH-LOW)<0x8000时，将数据转换为无符号数的结果是正确的。
如果(HIGH-LOW)>=0x8000，算法应按下面所示进行简单修改。
MM0: 有符号源操作数
输出：
MM0: 按无符号区域[HIGH,LOW]截取的有符号操作数
PADDSSW MM0, (PACKED_USMAX-HIGH_US) ;截取HIGH
PSUBSSW MM0, (PACKED_USMAX-PACKED_HIGH+PACKED_LOW)
;截取到LOW
PADDW MM0, LOW ;取消前两个偏移量
如果已知(HIGH-LOW)>=0x8000，本算法则省下一个时钟周 期。为了了解为什么在(HIGH-LOW)<0x8000时，这个由三条指令构成的算法不能工作，注意0xFFFF减任何小于0x8000的数都将 产生一个在数量级上大于负数0x8000的数。当PSUBSSW MM0, (0xFFFF-HIGH+LOW)(三行算法的第二条指令)被执行时，一个负数将被减，造成MM0中的值不减反加，这样就产生了一个不正确的结果。
5.11 无符号数截取到任意无符号区域[HIGH,LOW]
本例说明了如何将一个无符号数截取到无符号区域[HIGH,LOW]。如果数据小于LOW或者大于HIGH，那么截取到对应的LOW或HIGH中。本技术按无符号饱和方式进行成组数据加和成组数据减指令，该技术只能用于字节组和字组数据类型。
下例显示了对字数据值的操作。
输入：
MM0: 无符号源操作数
输出：
MM0: 按无符号区域[HIGH,LOW]截取的无符号操作数
PADDUSW MM0, 0xFFFF-HIGH ;截取到HIGH
PSUBUSW MM0, (0xFFFF-HIGH+LOW) ;截取到LOW
PADDW MM0, LOW ;取消前两个偏移量
5.12 常数生成
在MM0中产生0：
PXOR MM0, MM0
在MM1中产生全1数，每个成组数据类型字段为-1
PCMPEQ MM1, MM1
为每个字节组[或成组字](或双字组)字段产生常数1
PXOR MM0, MM0
PCMPEQ MM1, MM1
PSUBB MM0, MM1 [PSUBW MM0, MM1] (PSUBD MM0, MM1)
在每个字组(或双字组)中生成有符号常数2n-1
PCMPEO MM1, MM1
PSRLW MM1, 16-n (PSRLD MM1, 32-n)
在每个字组（或双字组）字段中生成有符号常数-2n
PCMPEO MM1, MM1
PSLLW MM1, n (PSLLD MM1, n)
由于MMX™指令集不支持字节的移位指令，2n-1和-2n只与字组和双字组相关。
source:http://dev.gameres.com/Program/Other/Fmmx/mmx_c5.htm
2008年3月3日星期一
__attribute__ 问题
测试程序
#include <stdio.h>
struct A{
char a;
int b;
unsigned short c;
long d;
unsigned long long e;
char f;
};
struct B{
char a;
int b;
unsigned short c;
long d;
unsigned long long e;
char f;
}__attribute__((aligned));
struct C{
char a;
int b;
unsigned short c;
long d;
unsigned long long e;
char f;
}__attribute__((aligned(1)));
struct D{
char a;
int b;
unsigned short c;
long d;
unsigned long long e;
char f;
}__attribute__((aligned(4)));
struct E{
char a;
int b;
unsigned short c;
long d;
unsigned long long e;
char f;
}__attribute__((aligned(8)));
struct F{
char a;
int b;
unsigned short c;
long d;
unsigned long long e;
char f;
}__attribute__((packed));
int main(int argc, char **argv)
{
printf("A = %d, B = %d, C = %d, D = %d, E = %d, F = %d\n",
sizeof(struct A), sizeof(struct B), sizeof(struct C), sizeof(struct D), sizeof(struct E), sizeof(struct F));
return 0;
}
在fedora 7下的测试结果：
A = 28, B = 32, C = 28, D = 28, E = 32, F = 20
A：不使用__attribute__ 默认4字节对齐
B：__attribute__((aligned))
the compiler automatically sets the alignment for the declared variable or field to the largest alignment which is ever used for any data type on the target machine you are compiling for. Doing this can often make copy operations more efficient, because the compiler can use whatever instructions copy the biggest chunks of memory when performing copies to or from the variables or fields that you have aligned this way.
最大对齐方式，此例中为16字节对齐，同E
C:__attribute__((aligned(1))) 不支持，除了packed 不能减小对齐字节数，以默认对齐方式对齐
D:__attribute__((aligned(4))) 四字节对齐
E：__attribute__((aligned(8))) 八字节对齐
F：__attribute__((packed))
the
The
A = 32, B = 32, C = 32, D = 32, E = 32, F = 20
从测试结果上看默认8字节对齐？或是只支持packed,未知
可参考的文档：
http://developer.apple.com/documentation/DeveloperTools/gcc-3.3/gcc/Variable-Attributes.html
http://www.skynet.org.cn/archiver/?tid-87.html
#include <stdio.h>
struct A{
char a;
int b;
unsigned short c;
long d;
unsigned long long e;
char f;
};
struct B{
char a;
int b;
unsigned short c;
long d;
unsigned long long e;
char f;
}__attribute__((aligned));
struct C{
char a;
int b;
unsigned short c;
long d;
unsigned long long e;
char f;
}__attribute__((aligned(1)));
struct D{
char a;
int b;
unsigned short c;
long d;
unsigned long long e;
char f;
}__attribute__((aligned(4)));
struct E{
char a;
int b;
unsigned short c;
long d;
unsigned long long e;
char f;
}__attribute__((aligned(8)));
struct F{
char a;
int b;
unsigned short c;
long d;
unsigned long long e;
char f;
}__attribute__((packed));
int main(int argc, char **argv)
{
printf("A = %d, B = %d, C = %d, D = %d, E = %d, F = %d\n",
sizeof(struct A), sizeof(struct B), sizeof(struct C), sizeof(struct D), sizeof(struct E), sizeof(struct F));
return 0;
}
在fedora 7下的测试结果：
A = 28, B = 32, C = 28, D = 28, E = 32, F = 20
A：不使用__attribute__ 默认4字节对齐
B：__attribute__((aligned))
the compiler automatically sets the alignment for the declared variable or field to the largest alignment which is ever used for any data type on the target machine you are compiling for. Doing this can often make copy operations more efficient, because the compiler can use whatever instructions copy the biggest chunks of memory when performing copies to or from the variables or fields that you have aligned this way.
最大对齐方式，此例中为16字节对齐，同E
C:__attribute__((aligned(1))) 不支持，除了packed 不能减小对齐字节数，以默认对齐方式对齐
D:__attribute__((aligned(4))) 四字节对齐
E：__attribute__((aligned(8))) 八字节对齐
F：__attribute__((packed))
the
aligned attribute can only increase the alignment; but you can decrease it by specifying packed as well. The
packed attribute specifies that a variable or structure field should have the smallest possible alignment―one byte for a variable, and one bit for a field, unless you specify a larger value with the aligned attribute. Here is a structure in which the field x is packed, so that it immediately follows a:
struct foocygwin下的测试结果：
{
char a;
int x[2] __attribute__ ((packed));
};
变量以字节对齐，结构体域以位对齐
A = 32, B = 32, C = 32, D = 32, E = 32, F = 20
从测试结果上看默认8字节对齐？或是只支持packed,未知
可参考的文档：
http://developer.apple.com/documentation/DeveloperTools/gcc-3.3/gcc/Variable-Attributes.html
http://www.skynet.org.cn/archiver/?tid-87.html
订阅：
博文 (Atom)