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对应的位，表示为不可用。

常用字符串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比较常用

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:

 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.

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-1　PACKSSDW mm, mm/mm64指令示例

　　下例将两个值交错送入目的寄存器，如图5一2所示。

图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-3　MM0中的非交错分组的结果

　　目的寄存器的另一种相反的组合如图5一4所示。

图5-4　MM1中的非交错分组的结果

　　下例将两个字组的源数据按非交错方式分组。其实现方法为用将双字变为四字的指令代替将字变为双字的分组指令。

　　输入：

	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　常数生成

　　在MMX™指令集中不存在能够将立即数常数取到MMX™寄存器的指令。下列代码段用于生成MMX™寄存器中的常用常数。当然，也可以将常数作为内存中的局域变量。但是如果要这样做，就要在内存中进行数据的复制，以便可用MOVQ指令读取。

　　在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)

　　在每个字组(或双字组)中生成有符号常数2ⁿ-1

PCMPEO MM1, MM1
PSRLW MM1, 16-n　(PSRLD　　MM1, 32-n)

　　在每个字组（或双字组）字段中生成有符号常数-2ⁿ

PCMPEO MM1, MM1
PSLLW MM1, n　　(PSLLD　　MM1, n)

　　由于MMX™指令集不支持字节的移位指令，2ⁿ-1和-2ⁿ只与字组和双字组相关。

source:http://dev.gameres.com/Program/Other/Fmmx/mmx_c5.htm

__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 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 foo
          {
            char a;
            int x[2] __attribute__ ((packed));
          };
   变量以字节对齐，结构体域以位对齐   

cygwin下的测试结果：
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