LINUX日常代码集锦.pdf-资料库

dns 数据包解析 2012 年 4 月 5 日 11:40 仔细看了看 DNS 协议的相关东西，其实实际编程的时候根本用不到 DNS 细节的东西，要获取域名的时候经终端下用 host 或者 nslookup 指令就可以，在 c 里面使用 gethostbyname 或者 getaddrinfo 都能很轻松得将 dns 域名解析为 ip 地址，写这个纯粹出于个人兴趣，或者说是闲得吧。在进行域名解析的时候，解析程序向域名服务器发起请求，域名服务器也就是在操作系统网络配置的时候写进去的那个 DNS 服务器地址，或者也有可能是由 ISP 提供的自动获取的，原理都一样，域名服务器收到请求后进行处理，首先在本地缓存中查找对应的域名，找到后将 IP 地址直接返回，找不到就向其它的授权服务器请求数据，又可以分为著名的递归查询和非递归查询。递归查询就是说自始至终都由一台域名服务器进行查询，它在自己这里找不到的时候会向其它的域名服务器请求并且获取数据，然后返回给请求方。非递归查询是指域名服务器收到请求后，如果自己有这个域名的信息就返回，如果没有就返回其它域名服务器的指针，请求方再根据这些域名服务器再发起查询。按自己的理解瞎扯了一通，也不知道准不准确，关于 DNS 的相关资料网上有的是，中文的都大批大批的。 DNS 服务器的原理其实没什么好说的，每天都在跟 DNS 打交道，但 DNS 的协议在实现上还是稍微有点意思的，本来想写个程序来测试一个我所了解的 DNS 协议，后来在写的时候还真发现一个小问题，DNS 域名有时候会是一个主域名的别名，比如 www.baidu.com，它就是 www.a.shifen.com 这个域名的别名，在 DNS 请求发送过去之后，response 里面会有一个类型为 CNAME 的 Answers 项，里面包含了主域名的相关信息(其实也就是主域名的名称和 TTL)，在这个应答消息里面可能会出现多个域名消息，比如每个 Answers 的第一个字段就是一个域名，当然为了减少数据包的容量，DNS 系统对域名进行了压缩，同一个域名只会出现一次，其它的时候再出现的话就会用一个 DNS 指针表示。比如域名：www.baidu.com 03 63 6f 6d 00 粗体的是长度，将域名中的点去掉，用长度来分隔域名，以 0 结束。DNS 允许的长度为 0-63 个字节，所以一个 8 位的长度最高两位都为 0。而如果此处域名重复出现，信令中便会用 DNS 指针代替长度，指针为两个字节，16 位的最位都为 1，剩下的 14 位表示在在整个数据包中的偏移量，当程序读取到 c00c 的时候很容易判断它是一个指针而不是一个长度字段，于是根据 c00c 指向的领移量，即从数据包开始后的第 12 个字节，跳转过去读取出域名信息。 #include #include #include #include #include #include #include #include #define DNS_SVR "211.68.71.4" #define DNS_HOST 0x01 #define DNS_CNAME 0x05 03 77 77 77 05 62 61 69 64 75 在数据包中的表示是

int socketfd; struct sockaddr_in dest; static void send_dns_request(const char *dns_name); static void parse_dns_response(); /** * Generate DNS question chunk */ static void generate_question(const char *dns_name , unsigned char *buf , int *len); /** * Check whether the current byte is * a dns pointer or a length */ static int is_pointer(int in); /** * Parse data chunk into dns name * @param chunk The complete response chunk * @param ptr The pointer points to data * @param out This will be filled with dns name * @param len This will be filled with the length of dns name */ static void parse_dns_name(unsigned char *chunk , unsigned char *ptr , char *out , int *len); int main(int argc , char *argv[]){ if(argc != 2){ printf("Usage : %s \n" , argv[0]); exit(-1); } socketfd = socket(AF_INET , SOCK_DGRAM , 0); if(socketfd < 0){ perror("create socket failed"); exit(-1); } bzero(&dest , sizeof(dest)); dest.sin_family = AF_INET; dest.sin_port = htons(53); dest.sin_addr.s_addr = inet_addr(DNS_SVR); send_dns_request(argv[1]); parse_dns_response(); return 0;

} static void parse_dns_response(){ unsigned char buf[1024]; unsigned char *ptr = buf; struct sockaddr_in addr; char *src_ip; int n , i , flag , querys , answers; int type , ttl , datalen , len; char cname[128] , aname[128] , ip[20] , *cname_ptr; unsigned char netip[4]; size_t addr_len = sizeof(struct sockaddr_in); n = recvfrom(socketfd , buf , sizeof(buf) , 0 , (struct sockaddr*)&addr , &addr_len); ptr += 4; /* move ptr to Questions */ querys = ntohs(*((unsigned short*)ptr)); ptr += 2; /* move ptr to Answer RRs */ answers = ntohs(*((unsigned short*)ptr)); ptr += 6; /* move ptr to Querys */ /* move over Querys */ for(i= 0 ; i < querys ; i ++){ for(;;){ flag = (int)ptr[0]; ptr += (flag + 1); if(flag == 0) break; } ptr += 4; } printf("-------------------------------\n"); /* now ptr points to Answers */ for(i = 0 ; i < answers ; i ++){ bzero(aname , sizeof(aname)); len = 0; parse_dns_name(buf , ptr , aname , &len); ptr += 2; /* move ptr to Type*/ type = htons(*((unsigned short*)ptr)); ptr += 4; /* move ptr to Time to live */ ttl = htonl(*((unsigned int*)ptr)); ptr += 4; /* move ptr to Data lenth */ datalen = ntohs(*((unsigned short*)ptr)); ptr += 2; /* move ptr to Data*/ if(type == DNS_CNAME){ bzero(cname , sizeof(cname)); len = 0; parse_dns_name(buf , ptr , cname , &len); printf("%s is an alias for %s\n" , aname , cname); ptr += datalen; } if(type == DNS_HOST){ bzero(ip , sizeof(ip)); if(datalen == 4){ memcpy(netip , ptr , datalen); inet_ntop(AF_INET , netip , ip , sizeof(struct sockaddr));

printf("%s has address %s\n" , aname , ip); printf("\tTime to live: %d minutes , %d seconds\n" , ttl / 60 , ttl % 60); } ptr += datalen; } } ptr += 2; } static void parse_dns_name(unsigned char *chunk , unsigned char *ptr , char *out , int *len){ int n , alen , flag; char *pos = out + (*len); for(;;){ flag = (int)ptr[0]; if(flag == 0) break; if(is_pointer(flag)){ n = (int)ptr[1]; ptr = chunk + n; parse_dns_name(chunk , ptr , out , len); break; }else{ ptr ++; memcpy(pos , ptr , flag); pos += flag; ptr += flag; *len += flag; if((int)ptr[0] != 0){ memcpy(pos , "." , 1); pos += 1; (*len) += 1; } } } } static int is_pointer(int in){ return ((in & 0xc0) == 0xc0); } static void send_dns_request(const char *dns_name){ unsigned char request[256]; unsigned char *ptr = request; unsigned char question[128]; int question_len; generate_question(dns_name , question , &question_len);

*((unsigned short*)ptr) = htons(0xff00); ptr += 2; *((unsigned short*)ptr) = htons(0x0100); ptr += 2; *((unsigned short*)ptr) = htons(1); ptr += 2; *((unsigned short*)ptr) = 0; ptr += 2; *((unsigned short*)ptr) = 0; ptr += 2; *((unsigned short*)ptr) = 0; ptr += 2; memcpy(ptr , question , question_len); ptr += question_len; sendto(socketfd , request , question_len + 12 , 0 , (struct sockaddr*)&dest , sizeof(struct sockaddr)); } static void generate_question(const char *dns_name , unsigned char *buf , int *len){ char *pos; unsigned char *ptr; int n; *len = 0; ptr = buf; pos = (char*)dns_name; for(;;){ n = strlen(pos) - (strstr(pos , ".") ? strlen(strstr(pos , ".")) : 0); *ptr ++ = (unsigned char)n; memcpy(ptr , pos , n); *len += n + 1; ptr += n; if(!strstr(pos , ".")){ *ptr = (unsigned char)0; ptr ++; *len += 1; break; } pos += n + 1; } *((unsigned short*)ptr) = htons(1); *len += 2; ptr += 2; *((unsigned short*)ptr) = htons(1); *len += 2; }

bm 算法 2012 年 4 月 6 日 10:54 BM 算法后缀匹配，是指模式串的比较从右到左，模式串的移动也是从左到右的匹配过程，经典的 BM 算法其实是对后缀蛮力匹配算法的改进。所以还是先从最简单的后缀蛮力匹配算法开始。下面直接给出伪代码，注意这一行代码：j++；BM 算法所做的唯一的事情就是改进了这行代码，即模式串不是每次移动一步，而是根据已经匹配的后缀信息，从而移动更多的距离。 1 2 j = 0； while (j <= strlen(T) - strlen(P)) { for (i = strlen(P) - 1; i >= 0 && P[i] ==T[i + j]; --i) 3 4 5 6 7 8 为了实现更快移动模式串，BM 算法定义了两个规则，好后缀规则和坏字符规则，如下图可以清晰的看出他们的含义。利用好后缀和坏字符可以大大加快模式串的移动距离，不是简单的++j，而是 j+=max (shift(好后缀), shift(坏字符)) else ++j； } match； if (i < 0) 先来看如何根据坏字符来移动模式串，shift(坏字符)分为两种情况： • 坏字符没出现在模式串中，这时可以把模式串移动到坏字符的下一个字符，继续比较，如下图： • 坏字符出现在模式串中，这时可以把模式串第一个出现的坏字符和母串的坏字符对齐，当然，这样可能造成模式串倒退移动，如下图：

为了用代码来描述上述的两种情况，设计一个数组 bmBc['k'] ，表示坏字符 k’在模式串中出现的位置距离模式串末尾的最大长度，那么当遇到坏字符的时候，模式串可以移动距离为： shift(坏字符) = bmBc[T[i]]-（m-1-i)。如下图： ‘ for (i = 0; i < ASIZE; ++i) int i; void preBmBc(char *x, int m, int bmBc[]) { 数组 bmBc 的创建非常简单，直接贴出代码如下： 1 2 3 4 5 6 7 再来看如何根据好后缀规则移动模式串，shift（好后缀）分为三种情况： bmBc[i] = m; for (i = 0; i < m - 1; ++i) } bmBc[x[i]] = m - i - 1; • 模式串中有子串匹配上好后缀，此时移动模式串，让该子串和好后缀对齐即可，如果超过一个子串匹配上好后缀，则选择最靠左边的子串对齐。 • 模式串中没有子串匹配上后后缀，此时需要寻找模式串的一个最长前缀，并让该前缀等于好后缀的后缀，寻找到该前缀后，让该前缀和好后缀对齐即可。

• 模式串中没有子串匹配上后后缀，并且在模式串中找不到最长前缀，让该前缀等于好后缀的后缀。此时，直接移动模式到好后缀的下一个字符。为了实现好后缀规则，需要定义一个数组 suffix[]，其中 suffix[i] = s 表示以 i 为边界，与模式串后缀匹配的最大长度，如下图所示，用公式可以描述：满足 P[i-s, i] == P[m-s, m]的最大长度 s。构建 suffix 数组的代码如下： 1 2 3 4 suffix[m-1]=m; for (i=m-2；i>=0；--i){ q=i; while(q>=0&&P[q]==P[m-1- i+q]) --q; suffix[i]=i-q; 5 6 7 有了 suffix 数组，就可以定义 bmGs[]数组，bmGs[i] 表示遇到好后缀时，模式串应该移动的距离，其中 i 表示好后缀前面一个字符的位置（也就是坏字符的位置），构建 bmGs 数组分为三种情况，分别对应上述的移动模式串的三种情况 } • 模式串中有子串匹配上好后缀

资料库

LINUX日常代码集锦.pdf

相关推荐

操作系统

热门标签

最新资料