Самый лучший способ быстро сравнить IP-адреса?

Question

У меня есть список IP-адресов, которые хранятся как это:

char IP_addresses_list[] = { 
    "157.55.130", /* 157.55.130.0/24 */ 
    "157.56.52", /* 157.56.52.0/24 */ 
    "157.12.53", /* 157.12.53.0/24 */ 
    ... 
}; 

я получаю IP-адрес от понюхал пакета (приведения его к struct iphdr *iph = (struct iphdr *)(packet + sizeof(struct ether_header)); преобразовать его в строку символов, используя inet_ntop, наконец, я сравнить IP-адрес из пакета с тем, в списке с помощью следующего кода:.

/* 
* input: IP address to search in the list 
* output: 1 if IP address is found in the list, 0 otherwise 
*/ 
int find_IP_addr(char *server) { 
    int ret = 0; 
    int i, string_size1, string_size2; 
    char *copied_server, *copied_const_char; 
    char *save_ptr1, *save_ptr2; 
    char dot[2] = "."; 
    /* Here I store the IP address from the packet */ 
    char first_IPaddr_pkt[4], second_IPaddr_pkt[4], third_IPaddr_pkt[4]; 
    /* Here I store the IP address from the list */ 
    char first_IPaddr_list[4], second_IPaddr_list[4], third_IPaddr_list[4]; 

    string_size1 = strlen(server)+1; 
    copied_server = (char *)malloc(string_size1 * sizeof(char)); 
    strcpy(copied_server, server); 

    /* I store and compare the first three bits of the IP address */ 
    strcpy(first_IPaddr_pkt, strtok_r(copied_server, dot, &save_ptr1)); 
    strcpy(second_IPaddr_pkt, strtok_r(NULL, dot, &save_ptr1)); 
    strcpy(third_IPaddr_pkt, strtok_r(NULL, dot, &save_ptr1)); 
    printf("tokenized %s, %s and %s\n", first_IPaddr_pkt, second_IPaddr_pkt, third_IPaddr_pkt); 

    /* Now I scan the list */ 
    for (i=0; i<LIST_LENGTH; i++) { 
     /* I copy an address from the list */ 
     string_size2 = strlen(IP_addresses_list[i])+1; // +1 for null character 
     copied_const_char = (char *)malloc(string_size2 * sizeof(char)); 
     strcpy(copied_const_char, IP_addresses_list[i]); 
     /* Let's split the address from the list */ 
     strcpy(first_IPaddr_list, strtok_r(copied_const_char, dot, &save_ptr2)); 
     strcpy(second_IPaddr_list, strtok_r(NULL, dot, &save_ptr2)); 
     strcpy(third_IPaddr_list, strtok_r(NULL, dot, &save_ptr2)); 
     printf("tokenized %s, %s and %s\n", first_IPaddr_list, second_IPaddr_list, third_IPaddr_list); 
     /* I compare the first byte of the address from the packet I got and 
     the first byte of the address from the list: 
     if they are different, there's no reason to continue comparing 
     the other bytes of the addresses */ 
     if (strcmp(first_IPaddr_pkt, first_IPaddr_list) != 0) { 
      continue; 
     } 
     else { 
      if (strcmp(second_IPaddr_pkt, second_IPaddr_list) != 0) { 
       continue; 
     } 
     else { 
      if (strcmp(third_IPaddr_pkt, third_IPaddr_list) != 0) { 
       continue; 
      } 
      else 
       /* All the bytes are the same! */ 
       ret = 1; 
      } 
     } 
     free(copied_const_char); 
    } 
    free(copied_server); 
    return ret; 
} 

Я хотел бы сделать это более быстро, без использования strtok, strcmp, malloc или free В /usr/include/netinet/ip.h я вижу, что адрес

u_int32_t saddr; 
u_int32_t daddr; 

можно ли сравнивать даже без использования inet_ntop первых, может быть, просто сравнивая два адреса в то время как они все еще u_int32_t?

EDIT: вот пример решения для тех, кто прочитает этот вопрос.

#include <stdio.h> 
#include <sys/types.h> 

int main() { 

    // In the list I have: 104.40.0.0./13 
    int cidr = 13; 
    u_int32_t ipaddr_from_pkt = 1747488105;  // pkt coming from 104.40.141.105 
    u_int32_t ipaddr_from_list = 1747451904; // 104.40.0.0 
    int mask = (-1) << (32 - cidr); 

    if ((ipaddr_from_pkt & mask) == ipaddr_from_list) 
     printf("IP address belongs to the given range!!!\n"); 
    else printf ("failure\n"); 

    return 0; 
} 

Благодаря iharob тоже для bsearch намека.

Answer 1

Я бы не стал преобразовывать двоичные данные в строки.Если вы храните их в двоичном формате, то это довольно легко сравнить:

"/ 24" - это маска. Значит, всего 24 бита. Вы преобразовать его в двоичную маску следующим образом:

listed_mask = (-1) << (32 - 24); 

Answer 2

Проблемы с производительностью не имеют отношения к strcmp(), malloc() не нужно.

Если вы только с IPv4-адреса, которые нужны только символов, чтобы сохранить его, так что вы можете удалить malloc() и объявить временное хранение в виде массива.

Но есть важное улучшение, если в списке будет много IP-адресов.

Сначала вам нужно отсортировать список IP-адресов, а затем использовать bsearch() для поиска правильного IP-адреса. Таким образом, код будет работать в O (журнал (2n)) времени, которое намного быстрее, чем O (N), специально для больших N

Answer 3

Самый быстрый способ будет хранить адреса в словаре, см this link

Answer 4

Мой подход здесь будет:

1. просто использовать strncat с ".0" строить действительные адреса IPv4.
2. использование getaddrinfo с постоянными значениями для сокетов типа и т.д., чтобы построить addrinfo-структуру
3. сравнить соответствующие поля addrinfo.

В принципе, пример от man getaddrinfo does all this.