Reduza uma lista de IPv4 para o CIDR comum mais baixo

5

Eu tenho uma longa lista de endereços IP que mostram algum padrão de proximidade

Exemplo:

XX.249.91.16  
XX.249.91.21  
XX.249.91.32  
XX.249.91.160  
XX.249.91.165  
XX.249.92.15  
XX.249.92.25  
XX.249.92.51  
XX.249.92.234  

e às vezes um whois revela um intervalo como este

XX.163.224.0 - XX.163.239.255

Eu gostaria de criar uma lista de CIDR que me fornece o menor número comum

Parece que o Python já tem uma coisa dessas - iprange_to_cidrs - mas eu preciso disso em JavaScript

XX.249.90.0/16

se é isso que iria lidar com

XX.249.91.0 - XX.249.92.255  

idem XX.163.200.0 / nn para lidar com

XX.163.224.0 - XX.163.239.255

Uma calculadora que pode fazer um intervalo de cada vez quando eu mexer com a máscara está aqui link

Meu idioma preferido é JavaScript e eu tenho o início seguinte , mas preciso do algoritmo que combina e transforme

var list = [
    [1234,"10.249.91.16"],
    [5678,"10.249.91.21"],
    [123,"10.249.91.32"],
    [456,"10.249.91.160"],
    [789,"10.249.91.165"],
    [3456,"10.249.92.15"],
    [7890,"10.249.92.25"],
    [1234,"10.249.92.51"],
    [5432,"10.249.92.234"]
]
function dec2bin(ip) { 
    return ip.split(".").map(function(num) { 
      return ("00000000"+parseInt(num,10).toString(2)).slice(-8); 
    }).join(".");
}
$(function() {
    $res = $("#res");
    $.each(list,function(_,arr) {
        $res.append('<br/>'+dec2bin(arr[1])+" - "+arr); 
    });
});

ATUALIZAR depois de analisar uma resposta

FIDDLE

function getDec(ip) {
  var octet = ip.split(".");
  return (octet[0] << 24) | (octet[1] << 16) | (octet[2] << 8) | octet[3];
}
var res = document.getElementById("res");

var adr1 = "111.163.224.0";
var adr2 = "111.163.239.255"
var XOR = getDec(adr1)^getDec(adr2);

// now what?

Atualização 2:

poderia o resultado do intervalo 111.163.224.0 - 111.163.239.255 ser 111.163.224.0/20 ? desde que nós temos

01101111.10100011.11100000.00000000 - 0,111.163.224.0
01101111.10100011.11101111.11111111 - 0,111.163.239.255
    
por mplungjan 30.06.2014 / 16:12
fonte

2 respostas

1

A solução foi mais simples que o esperado. Eu aprecio o tempo e a explicação de Blrfl, mas a coisa toda resumida ao número a ser usado são os dois endereços ANDed mascarados pelo número de 0s iniciais na representação binária dos dois endereços XORed

var adr1 = "111.163.224.0",
    adr2 = "111.163.239.255",
    AND  = dot2dec(adr1)&dot2dec(adr2), 
    XOR  = num2dot(dot2dec(adr1)^dot2dec(adr2)),
    mask = dec2bin(XOR).replace(/\./g,"").indexOf("1");

neste caso, 111.163.224.0/20

    
por 08.07.2014 / 14:04
fonte
6

O que você está procurando é um conjunto de bits de alta ordem contíguos no endereço que não muda em todo o conjunto de endereços. Os endereços IPv4 são, no seu núcleo, inteiros não assinados de 32 bits. A notação quad-ponteada é uma conveniência para os humanos. É melhor lidar com eles dessa forma. A conversão é fácil:

integer_ip = (octet1 << 24) | (octet2 << 16) | (octet3 << 8) | octet4

Depois de ter números inteiros, a ferramenta certa para determinar quais alterações são exclusivas de bits ou ( ^ em muitos idiomas derivados de C). Isso ocorre porque ele detecta a alteração, retornando um 1 bit se o bit correspondente nos dois valores for diferente e um 0 caso contrário.

Vou usar quantidades de 8 bits nos exemplos para mantê-lo legível, mas isso se aplica exatamente aos números de 32 bits que você obtém de um endereço IP.

Precisamos começar com um inteiro cujos bits indiquem quais bits foram alterados, o que não é nenhum deles:

changed_bits = 0x00

Para cada endereço após o primeiro, os itens XOR n e n-1 , resultando no conjunto de bits que mudou entre os dois. Aqueles podem ser ORed com o nosso conjunto de bits alterados para adicionar ao conjunto:

a[0] = 0x10
a[1] = 0x11    0x10 ^ 0x11 = 0x01    changed_bits = 0x00 | 0x01 = 0x01
a[2] = 0x1f    0x11 ^ 0x1f = 0x0e    changed bits = 0x01 | 0x0e = 0x0f

O valor final de changed_bits , 0x0f , indica que durante todas as comparações, os quatro bits superiores não mudaram (são todos zeros) e os quatro bits inferiores (todos). Então, tudo o que você precisa fazer é contar o número de bits inalterados (zero), começando pelo mais significativo:

cidr_size = 0;
for ( bit=0 ; bits < 8 ; ++bits ) {   // Use 32 for IPs
    if ( changed_bits & 0x80 ) {      // Use 0x800000 for IPs
        break;  // Stop when we hit the first bit that changed.
    }
    ++cidr_size;
    changed_bits = changed_bits << 1;  // Rotate the next bit into the high spot
}

Neste ponto, cidr_size manterá o número de bits que seus endereços têm em comum. Então você pode usar isso para construir uma máscara com o número adequado de bits

mask = 0xff << (8 - cidr_size)  // Use 0xffffffff and 32 for IPs

Com isso em mãos, você pode usá-lo contra qualquer um dos inteiros em sua lista para criar o bloco CIDR:

cidr_block = a[0] & mask

Converta cidr_block de volta para octetos, adicione uma barra, cuspa cidr_size e você está no negócio.

Adendo:

O que há nesta resposta vai te dar o CIDR comum mais baixo para uma lista inteira de endereços.

Dado apenas IPs, não existe um algoritmo mágico para determinar o CIDR do qual eles vieram. Com base no que eles têm em comum, os IPs usados na pergunta poderiam ser incluídos em qualquer um dos 13 blocos do CIDR tão grandes quanto 10.0.0.0/8 ou tão pequenos quanto 10.249.88.0/20 . (Blocos maiores que /8 também são possíveis, mas a realidade prática é que nenhum bloco maior do que aquele já foi emitido.)

Para agrupar adequadamente os IPs, você precisaria de um banco de dados dos CIDRs que foram emitidos, os quais poderiam ser associados aos IPs que você possui, agrupados por CIDR e agregados para obter uma contagem. A única outra coisa que você pode fazer é conhecer a máscara de rede que acompanha cada IP, o que não acontecerá porque o destinatário não o vê.

    
por 01.07.2014 / 06:03
fonte