приведение диапазона ip к CIDR-адресации -подскжите алгоритм

[tull]

задан начальный и конечный ip, например: 39789568 - 39793663 (2.95.36.0 - 2.95.51.255)
надо в php-скрипте преобразовать это к:
2.95.36.0/22
2.95.40.0/21
2.95.48.0/22

в сети полно онлайн-калькуляторов, но сами скрипты не выложены.
помогите плиз с алгоритмом...

[Хостинг HostFood.ru]

Тарифы на хостинг в России, от 12 рублей: https://www.host-food.ru/tariffs/hosting/
Тарифы на виртуальные сервера (VPS/VDS/KVM) в РФ, от 189 руб.: https://www.host-food.ru/tariffs/virtualny-server-vps/
Выделенные сервера, Россия, Москва, от 2000 рублей (HP Proliant G5, Intel Xeon E5430 (2.66GHz, Quad-Core, 12Mb), 8Gb RAM, 2x300Gb SAS HDD, P400i, 512Mb, BBU):
https://www.host-food.ru/tariffs/vydelennyi-server-ds/
Недорогие домены в популярных зонах: https://www.host-food.ru/domains/

[FiL]

переводим 39789568 в двоичную (получаем 10010111110010010000000000 ).
Считаем нули с конца (10) - остальное есть сеть. Итого /22

Ну а разбить число на 4 байта - это вообще не должно быть проблемой.

Код: Выделить всё

 echo (39789568 >> 24) & 255;
 echo ".";
 echo (39789568 >> 16) & 255;
 echo ".";
 echo (39789568 >> 8) & 255;
 echo ".";
 echo 39789568 & 255;

[FiL]

p.s. не даёте редактировать сообщение - читайте покореженный листинг

[Alex Keda]

Код: Выделить всё

Ограничение времени на редактирование: 5 минут 
Ограничение времени, в течение которого доступно редактирование новых сообщений. Введите 0 для отключения этой возможности.

Ограничение времени на удаление: 120 минут
Ограничение времени, в течение которого доступно удаление новых сообщений. Введите 0 для отключения этой возможности.

тормозить не надо )

[tull]

переводим 39789568 в двоичную (получаем 10010111110010010000000000 ).
Считаем нули с конца (10) - остальное есть сеть. Итого /22

попробуйте проверить получившийся у вас результат в любом сетевом калькуляторе. посмотрите, какой у вас получился конечный ip. а потом сравните с заданным в моем примере диапазоном.

а я ведь даже правильный ответ заранее привел...
именно для того, чтобы мне не давали советов "считать нули с конца", а посоветовали правильный алгоритм.

[FreeBSP]

наскока я понял
1) первый айпишник задает первую подсеть. приводишь в двоичную форму и находишь длину маски первой подсети
2) прибавляешь к первой подсети инвертированную маску и елиницу получаешь вторую подсеть
3) и так далее

[GhOsT_MZ]

Не, тут скорее угадывать нужно... считаем количество хостов, а исходя из него выбираем ближайшую маску и пытаемся определить адрес сети. После этого, смотрим попадает ли второй адрес в диапозон адресов по сети, если нет, то немного расширяем эту подсеть и заново проверяем. Как только все входит, получается, что мы имеем верную маску.
Допустим, есть диапозон:
192.168.0.1 - 192.168.0.250
Здесь у нас 250 хостов. Ближайшая маска /32 (254 хоста).
Адрес сети получается: 192.168.0.0
Получается, что максимальный адрес: 192.168.0.254

Наша маска: /32.

[FreeBSP]

Код: Выделить всё

39789568 = 100:1011111:00100100:00000000

net1  = 100:1011111:00100100:00000000 
mask1= 1111111:11111111:11111100:00000000 = /22

net2 = net1 + ~mask1 + 1 = 100:1011111:00101000:00000000 10010111110010100000000000 
mask2=1111111:11111111:11111000:00000000=/21

net3=net2+ ~mask2 + 1 = 100:1011111:00101100:00000000 
mask3 = 1111111:11111111:11111100:00000000=/22

вот твои сетки
и так пока net+~mask < end_ip

[GhOsT_MZ]

И каким образом? Не то это. Получается, что у нас 4 сети /22.
Нам нужно взять маску /19, чтобы покрыть весь диапозон, только вот сеть будет 2.95.32.0/19 (2.95.32.0 - 2.95.63.255).

[FreeBSP]

четыре сети /22 не обязательно объединятся в одну /20
/19 покрывает весь диапазон, но захватывает лишнего
то что я написал подходит для данно го случая, но косяки есть
попробую допилить вечером

[rmn]

http://forum.lissyara.su/viewtopic.php?f=32&t=26168

[GhOsT_MZ]

четыре сети /22 не обязательно объединятся в одну /20
/19 покрывает весь диапазон, но захватывает лишнего
то что я написал подходит для данно го случая, но косяки есть
попробую допилить вечером

Ничего подобного...
У нас:
2.95.36.0 - 2.95.51.255

Ваше:
2.95.36.0/22 - 2.95.36.0 - 2.95.39.255
2.95.32.0/21 - 2.95.32.0 - 2.95.39.255

Где здесь оно? В обоих случаях в конце не хватает. Только во втором случае еще и в начале лишнее захватывает.

[rmn]

Код: Выделить всё

remcomp% cat test.php 
<?php

function b2n($bits)
{
    $result = 0;
    while ($bits--)
    {
        $result >>= 1;
        $result |= 0x80000000;
    }

    return $result;
}

function SplitToSubnets($first_ip, $last_ip)
{
    $result = array();
    
    $f_ip = ip2long($first_ip);
    $l_ip = ip2long($last_ip);

    $ip = $f_ip;
        
    while ($ip <= $l_ip)
    {
        for ($bits=0; $bits<=32; $bits++)
        {
            $netmask = b2n($bits);
            if ((($ip & $netmask) == $ip) && ((($ip & $netmask) | ~$netmask) <= $l_ip))
                break;
        }
        
        $result[] = long2ip($ip & $netmask) . "/" . $bits;
        $ip += (~$netmask) + 1;
    }

    return $result;
}

foreach (SplitToSubnets($argv[1], $argv[2]) as $subnet)
    echo $subnet . "\n";

?>

Код: Выделить всё

remcomp% php test.php 2.95.36.0 2.95.51.255
2.95.36.0/22
2.95.40.0/21
2.95.48.0/22
remcomp% php test.php 192.168.0.0 192.168.0.4
192.168.0.0/30
192.168.0.4/32
remcomp% php test.php 192.168.0.11 192.168.7.255
192.168.0.11/32
192.168.0.12/30
192.168.0.16/28
192.168.0.32/27
192.168.0.64/26
192.168.0.128/25
192.168.1.0/24
192.168.2.0/23
192.168.4.0/22

[GhOsT_MZ]

FreeBSP, извиняюсь, был не прав, ибо не вник в первый пост)

[FreeBSP]

Код: Выделить всё

freebsp# cat ipc.php
<?php

function b2n($bits)
{
        $result = 0;
        while ($bits--)
        {
                $result >>= 1;
                $result |= 0x80000000;
        }
        return $result;
}

function SplitToSubnets($first_ip, $last_ip)
{

        $result = array();

        $f_ip = ip2long($first_ip);
        $l_ip = ip2long($last_ip);

        $ip = $f_ip;

        while ($ip <= $l_ip)
        {
                for ($bits=0; $bits<=32; $bits++)
                {
                        $netmask = b2n($bits);
                        if ((($ip & $netmask) == $ip) && ((($ip & $netmask) | ~$netmask) <= $l_ip))
                                break;
                }

                echo long2ip($ip & $netmask) . "/" . $bits . "\n";

                $result[] = long2ip($ip & $netmask) . "/" . $bits;
                $ip += (~$netmask) + 1;
        }

        return $result;
}

foreach (SplitToSubnets($argv[1], $argv[2]) as $subnet)
        echo $subnet . "\n";

?>

freebsp# php ipc.php 192.168.0.11 192.168.7.255 | head -15
192.168.0.11/32
192.168.0.12/33
192.168.0.13/33
192.168.0.14/33
192.168.0.15/33
192.168.0.16/33
192.168.0.17/33
192.168.0.18/33
192.168.0.19/33
192.168.0.20/33
192.168.0.21/33
192.168.0.22/33
192.168.0.23/33
192.168.0.24/33
192.168.0.25/33

[rmn]

думаю, проблема в ip2long - она возвращает знаковое целое, поэтому сравнения не корректны.
у меня ошибка есть, если один из адресов > 0x7fffffff (127.255.255.255)

[FreeBSP]

хзхз
но идея красивая

[tull]

http://forum.lissyara.su/viewtopic.php?f=32&t=26168

там неправильный алгоритм. на 2.95.36.0 2.95.51.255 он дает 2.95.32.0/20

з.ы. офф: а в pf нельзя передавать диапазоны ip? (например nginx диапазоны понимает)

[FiL]

переводим 39789568 в двоичную (получаем 10010111110010010000000000 ).
Считаем нули с конца (10) - остальное есть сеть. Итого /22

попробуйте проверить получившийся у вас результат в любом сетевом калькуляторе. посмотрите, какой у вас получился конечный ip. а потом сравните с заданным в моем примере диапазоном.

а я ведь даже правильный ответ заранее привел...
именно для того, чтобы мне не давали советов "считать нули с конца", а посоветовали правильный алгоритм.

а ты хотел, чтоб за тебя полностью всё расписали? Ну извини. Я думал тебе алгоритма хватит.
А продолжить его на осавшиеся адреса ты и сам догадаешься.
Как и проверить, что получившаяся пара (сеть, маска) не перекрывает лишнего.

[tull]

а ты хотел, чтоб за тебя полностью всё расписали?

я думал, что может у кого-то есть готовое решение

[NoResponse]

написал где то год назад
не совсем то, но думаю поможет двинутся в нужном направлении

Код: Выделить всё

<?php
function ips2cidr($ipsT){
	$ips	= array_map(create_function('$ip','return ip2long($ip);'), $ipsT);
	sort($ips);
	while (count($ips)){
		$cr=0;
		while ($ips[$cr]+1==$ips[$cr+1]){$cr++;}
		$cr++;
		$c=0;
		while ($cr>0){
			$c++;
			$cr=$cr>>1;
		}
		while ($c>0){
			$mask	= (1<<$c>>1)-1;
			$net	= $ips[0] & -$mask-1;
			if (in_array($net, $ips)) {
				$nets[]	= long2ip($net).'/'.(33-$c);
				$ips	= array_slice($ips, 1<<$c>>1);
				$c		= 0;
			}else{
				$c--;
			}
		}
	}
	return $nets;
}
//############################################################################\\
echo '<pre>';

$ips	= array(
	'192.168.0.10',
	'192.168.0.1',
	'192.168.0.2',
	'192.168.0.3',
	'192.168.0.4',
	'192.168.0.5',
	'192.168.0.6',
	'192.168.0.7',
	'10.18.112.80',
	'10.18.112.81',
	'10.18.112.82',
	'10.18.112.83',
	'10.18.112.84',
	'10.18.112.85',
	'110.18.112.80',
	'110.18.112.81',
	'110.18.112.82',
	'110.18.112.83',
	'110.18.112.84',
	'110.18.112.85',
	'110.18.112.86',
	'110.18.112.87',
	'110.18.112.88',
	'110.18.112.89',
);
echo "Before...\r";
print_r($ips);
echo "After...\r";
print_r(ips2cidr($ips));

echo '</pre>';
?> 

[tull]

написал где то год назад
не совсем то, но думаю поможет двинутся в нужном направлении

спасибо, но я все уже сделал
выдрал код из ipcalc

вот, вдруг кому пригодиться:

Код: Выделить всё

function deaggregate ($ip1, $ip2) {
  $cidr = array();
  $thirtytwobits = 4294967295;
  while ($ip1 <= $ip2) {
       $step = 0;
       while (($ip1 | (1 << $step))  != $ip1) {
          if (($ip1 | (((~0) & $thirtytwobits) >> (31-$step))) > $ip2) {
             break;
          }
          $step++;
       }
       $cidr[] = long2ip($ip1) ."/" .(32-$step);
       $ip1 += 1 << $step;
  }
  return $cidr;
}

[FiL]

a в чем сакральный смысл выражения

Код: Выделить всё

(~0) & $thirtytwobits

Чем просто (~0) или просто $thirtytwobits не устраивали?

P.S. А функция получилась короткая и красивая, да.

[tull]

a в чем сакральный смысл выражения

Код: Выделить всё

(~0) & $thirtytwobits

Чем просто (~0) или просто $thirtytwobits не устраивали?

не знаю
это же не мой код, я же говорю - из ipcalc выдрал.
т.е. можно просто:

Код: Выделить всё

if (($ip1 | ((~0 >> (31-$step))) > $ip2)

?

[FiL]

мне как-то вариант

Код: Выделить всё

if (($ip1 | ( $thirtytwobits >> (31-$step) )) > $ip2)

больше нравится. Понятнее. Но можно и ~0.

Только ты там аккуратнее, в твоем вопросе одной закрывающей скобочки не хватает после ~0. Ну, или одна лишняя перед ним.
Я не помню какой там приоритет операций в php и что первым произойдет и потому предпочитаю лишних скобочек наставить.