全部博文（370）
分类： LINUX
2012-01-19 16:26:20
对位图的操作主要在bitfield.h和bitfield.c中，负责创建位图，设置和获取位图某一位的值，保存位图等。
bitfield.h
#ifndef BITFIELD_H
#define BITFIELD_H
typedef struct _Bitmap {
unsigned char *bitfield; // 保存位图
int bitfield_length; // 位图所占的总字节数
int valid_length; // 位图有效的总位数,每一位代表一个piece
} Bitmap;
int create_bitfield(); // 创建位图,分配内存并进行初始化
int get_bit_value(Bitmap *bitmap,int index); // 获取某一位的值
int set_bit_value(Bitmap *bitmap,int index, unsigned char value);
// 设置某一位的值
int all_zero(Bitmap *bitmap); // 全部清零
int all_set(Bitmap *bitmap); // 全部设置为1
void release_memory_in_bitfield(); // 释放bitfield.c中动态分配的内存
int print_bitfield(Bitmap *bitmap); // 打印位图值,用于调试
int restore_bitmap(); // 将位图存储到文件中
// 在下次下载时,先读取该文件获取已经下载的进度
int is_interested(Bitmap *dst,Bitmap *src); // 拥有位图src的peer是否对拥有
// dst位图的peer感兴趣
int get_download_piece_num(); // 获取当前已下载到的总piece数
#endif
程序说明。
（1）结构体Bitmap中，bitfield_length为指针bitfield所指向的内存的长度（以字节为单位），而valid_length为位图的有效位数。例如，某位图占100字节，而有效位数位795，则位图最后一个字节的最后5位(100 ′ 8−795)是无效的。
（2）函数is_interested用于判断两个peer是否感兴趣，如果peer1拥有某个piece，而peer2没有，则peer2对peer1感兴趣，希望从peer1处下载它没有的piece。
（3）函数get_download_piece_num用于获得已下载的piece数，其方法是统计结构体Bitmap的bitfield成员所指向的内存中值为1的位数。
文件bitfield.c的头部包含的文件如下：
bitfield.c文件头部包括的内容
#include
#include
#include
#include
#include
#include
#include
#include "parse_metafile.h"
#include "bitfield.h"
extern int pieces_length;
extern char *file_name;
Bitmap *bitmap = NULL; // 指向位图
int download_piece_num = 0; // 当前已下载的piece数
程序说明。
（1）语句“extern int pieces_length;”声明了一个变量，这个变量是在parse_metafile.c中定义的全局变量。如果要在其他源文件中使用某个源文件中定义的变量，需要在使用该变量的源文件的头部以extern关键字声明。注意声明和定义的区别，声明仅仅是告知编译器有某个变量，而对于定义，编译器要分配内存空间来存储该变量的值。
（2）全局变量bitmap指向自己的位图，可以从位图中获知下载的进度。peer的位图存放在Peer结构体中。
l int create_bitfield()
功能：创建待下载文件的位图该函数较为简单，不另加注释
int create_bitfield()
{
bitmap = (Bitmap *)malloc(sizeof(Bitmap));
if(bitmap == NULL) {
printf("allocate memory for bitmap fiailed\n");
return -1;
}
// pieces_length除以20即为总的piece数
bitmap->valid_length = pieces_length / 20;
bitmap->bitfield_length = pieces_length / 20 / 8;
if( (pieces_length/20) % 8 != 0 ) bitmap->bitfield_length++;
bitmap->bitfield = (unsigned char *)malloc(bitmap->bitfield_length);
if(bitmap->bitfield == NULL) {
printf("allocate memory for bitmap->bitfield fiailed\n");
if(bitmap != NULL) free(bitmap);
return -1;
}
char bitmapfile[64];
sprintf(bitmapfile,"%dbitmap",pieces_length);
int i;
FILE *fp = fopen(bitmapfile,"rb");
if(fp == NULL) { // 若打开文件失败,说明开始的是一个全新的下载
memset(bitmap->bitfield, 0, bitmap->bitfield_length);
} else {
fseek(fp,0,SEEK_SET);
for(i = 0; i < bitmap->bitfield_length; i++)
(bitmap->bitfield)[i] = fgetc(fp);
fclose(fp);
// 给download_piece_num赋新的初值
download_piece_num = get_download_piece_num();
}
return 0;
}
l int get_bit_value(Bitmap *bitmap,int index)
功能：获取位图中某一位的值
int get_bit_value(Bitmap *bitmap,int index)
{
int ret;
int byte_index;
unsigned char byte_value;
unsigned char inner_byte_index;
if(bitmap==NULL || index >= bitmap->valid_length) return -1;
byte_index = index / 8;
byte_value = bitmap->bitfield[byte_index];
inner_byte_index = index % 8;
byte_value = byte_value >> (7 - inner_byte_index);
if(byte_value % 2 == 0) ret = 0;
else ret = 1;
return ret;
}
为了方便对get-bit-value函数的理解，可以假设某位图为2字节(其值为10110011 01010100)，有效位数为14位，也就是待下载文件共有14个piece。位图第一个字节指明index为0～7的piece是否已下载，第二个字节指明index为8～13的piece是否已下载。现在要判断index为8的piece是否已经下载，也就是要获取位图第二个字节最高位的值。
l int set_bit_value(Bitmap *bitmap,int index,unsigned char value)
功能：设置位图中某一位的值
int set_bit_value(Bitmap *bitmap,int index,unsigned char v)
{
int byte_index;
unsigned charinner_byte_index;
if(bitmapv==NULL || index >= bitmap->valid_length) return -1;
if((v != 0) && (v != 1)) return -1;
byte_index = index / 8;
inner_byte_index = index % 8;
v = v << (7 - inner_byte_index);
bitmap->bitfield[byte_index] = bitmap->bitfield[byte_index] | v;
return 0;
}
l int all_zero(Bitmap *bitmap)
功能：将位图所有位清0
int all_zero(Bitmap *bitmap)
{
if(bitmap->bitfield == NULL) return -1;
memset(bitmap->bitfield,0,bitmap->bitfield_length);
return 0;
}
l int all_set(Bitmap *bitmap)
功能：将位图所有位放置1
int all_set(Bitmap *bitmap)
{
if(bitmap->bitfield == NULL) return -1;
memset(bitmap->bitfield,0xff,bitmap->bitfield_length);
return 0;
}
l void release_memory_in_bitfield()
功能：释放本模块所申请的动态内存
void release_memory_in_bitfield()
{
if(bitmap->bitfield != NULL) free(bitmap->bitfield);
if(bitmap != NULL) free(bitmap);
}
l int print_bitfield(Bitmap *bitmap)
功能：打印位图，用于调试程序
int print_bitfield(Bitmap *bitmap)
{
int i;
for(i = 0; i < bitmap->bitfield_length; i++) {
printf("%.2X ",bitmap->bitfield[i]); // 以16进制的方式打印每个位图中的字节
if( (i+1) % 16 == 0) printf("\n"); // 每行打印16个字节
}
printf("\n");
return 0;
}
l int restore_bitmap()
功能：保存位图，用于断点续传
int restore_bitmap()
{
int fd;
char bitmapfile[64];
if( (bitmap == NULL) || (file_name == NULL) ) return -1;
sprintf(bitmapfile,"%dbitmap",pieces_length);
fd = open(bitmapfile,O_RDWR|O_CREAT|O_TRUNC,0666);
if(fd < 0) return -1;
write(fd,bitmap->bitfield,bitmap->bitfield_length);
close(fd);
return 0;
}
l int is_interested(Bitmap *dst,Bitmap *src)
功能：判断具有src位图的peer对具有dst位图的peer是否感兴趣
int is_interested(Bitmap *dst,Bitmap *src)
{
unsigned char const_char[8] = { 0x80,0x40,0x20,0x10,0x08,0x04,0x02,0x01};
unsigned char c1, c2;
int i, j;
if( dst==NULL || src==NULL ) return -1;
if( dst->bitfield==NULL || src->bitfield==NULL ) return -1;
if( dst->bitfield_length!=src->bitfield_length || dst->valid_length!=src-> valid_length )
return -1;
// 如果dst中某位为1而src对应为0，则说明src对dst感兴趣
for(i = 0; i < dst->bitfield_length-1; i++) {
for(j = 0; j < 8; j++) { // 比较某个字节的所有位
c1 = (dst->bitfield)[i] & const_char[j]; // 获取每一位的值
c2 = (src->bitfield)[i] & const_char[j];
if(c1>0 && c2==0) return 1;
}
}
j = dst->valid_length % 8;
c1 = dst->bitfield[dst->bitfield_length-1];
c2 = src->bitfield[src->bitfield_length-1];
for(i = 0; i < j; i++) { // 比较位图的最后一个字节
if( (c1&const_char[i])>0 && (c2&const_char[i])==0 )
return 1;
}
return 0;
}
以上函数的功能正确性测试代码如下：
// 测试时可以交换map1.bitfield和map2.bitfield的值或赋于其他值
Bitmap map1, map2;
unsigned char bf1[2] = { 0xa0, 0xa0 }; // 位图每一位的值为10100000 10100000
unsigned char bf2[2] = { 0xe0, 0xe0 }; // 位图每一位的值为11100000 11100000
map1.bitfield = bf1;
map1.bitfield_length = 2;
map1.valid_length = 11;
map2.bitfield = bf2;
map2.bitfield_length = 2;
map2.valid_length = 11;
int ret = is_interested(&map1,&map2);
printf("%d\n",ret);
在编写模块时，测试其中的每一个函数是很有必要的，否则无法知道模块中每一个函数是否达到预期的功能。限于篇幅，不能列出每个模块的测试代码。由于每个模块的相对独立性，读者不妨编写一些测试代码来测试某些模块的代码。
l int get_download_piece_num()
功能：获取当前已下载到的总piece数。函数实现代码如下：
int get_download_piece_num()
{
unsigned char const_char[8] = { 0x80,0x40,0x20,0x10,0x08,0x04,0x02,0x01};
int i, j;
if(bitmap==NULL || bitmap->bitfield==NULL) return 0;
download_piece_num = 0;
for(i = 0; i < bitmap->bitfield_length-1; i++) {
for(j = 0; j < 8; j++) {
if( ((bitmap->bitfield)[i] & const_char[j]) != 0)
download_piece_num++;
}
}
unsigned char c = (bitmap->bitfield)[i]; // c存放位图最后一个字节的值
j = bitmap->valid_length % 8; // j是位图最后一个字节的有效位数
for(i = 0; i < j; i++) {
if( (c & const_char[i]) !=0 ) download_piece_num++;
}
return download_piece_num;
}
