Подтвердить что ты не робот

Побитовые операции CIDR - могу ли я быть немного мудрее?

Я создаю класс для представления подсети IPv4. Я сохраняю сетевой адрес и маску подсети как 4 байтовые двоичные строки, которые строятся во время конструктора на основе аргументов. Одним из представлений, которые я хотел бы принять конструктору, является нотация CIDR.

Мои побитовые операции немного ржавые, и где я застрял в преобразовании десятичного целого CIDR-представления маски подсети в 4-байтовую двоичную строку и наоборот. Я также обнаружил, что не могу выполнять сдвиги влево/вправо в строке - что я уверен, что я успешно сделал это раньше?


Мне удалось получить преобразование в двоичную строку для работы со следующим кодом:

// An example input value.
$mask = 24; // 255.255.255.0

if ($mask < 0 || $mask > 32) {
  // Invalid prefix size
  throw new RangeException('Invalid CIDR prefix size');
} else if ($mask === 0) {
  // Handle 0
  $mask = "\x00\x00\x00\x00";
} else {
  // Left-pad a 4-byte string with $mask set bits
  $mask = pack('N', (0x01 << 31) >> ($mask - 1));
}

Мне не нравится эта логика по двум причинам:

  • Мне не нравится рассматривать 0 как особый случай
  • Мне не нравится сдвиг вправо, а затем левый сдвиг

Я уверен, что есть способ сделать это более эффективно так, чтобы обрабатывать 0 правильно, не рассматривая его как особый случай.


При преобразовании двоичной строки обратно в десятичное представление размера префикса CIDR, я в настоящее время использую код ниже. У меня есть еще один очень похожий блок кода при проверке маски подсети, предоставляемой в других форматах, чтобы гарантировать, что установленные биты смежны.

// An example input value.
$mask = "\xff\xff\xff\x00"; // /24

// Convert the binary string to an int so bit shifts will work
$mask = current(unpack('N', $mask));

// A counter to represent the CIDR
$cidr = 0;

// Loop and check each bit
for ($i = 31; $i > 0; $i--) {
  if (($mask >> $i) & 0x01) {
    $cidr++;
  } else {
    break;
  }
}

// Return the result
return $cidr;

Мне не нравится это из-за цикла - я уверен, что есть более интеллектуальный побитовый способ сделать это.


Есть ли более разумный способ выполнить любую из этих задач?

Мысли/предложения/общее насилие, пожалуйста...


EDIT:

Любые решения должны работать на PHP 4.3.10 и выше и должны работать как на 32-, так и на 64-битных платформах. Имейте в виду, что все целые числа в PHP подписаны, а на 32-битной платформе все >= 0x80000000 будет храниться как двойное (и поэтому не будет хорошо работать с побитовыми операциями).

4b9b3361

Ответ 1

Вторая проблема может быть заменена на поиск первого набора бит в инвертированном номере (вместо поиска первого не установленного бита в неинвертированном номере), что эквивалентно поиску целого log2 числа.

Это довольно распространенная проблема в побитом мире, и для нее существуют многочисленные алгоритмы оптимизации скорости. Вы используете (медленный) очевидный алгоритм: http://www-graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious

Но я предполагаю, что вам действительно не нужна скорость, а скорее краткость, в этом случае вы можете сделать что-то вроде этого:

$cidr = (int) (32 - log(~current(unpack('N', $mask)) & 0xffffffff, 2));

& 0xffffffff необходимо согласовать с 64-битными целыми числами.

Ответ 2

Вторая проблема может быть решена с помощью текстового подхода:

$mask = "\xff\xff\xff\x00";

$cidr = strspn(sprintf('%b', current(unpack('N', $mask))), 1);

Он использует sprintf() для преобразования целого в двоичное текстовое представление, а strspn() подсчитывает количество начальных.

Обновление

На 64-битных машинах двоичное текстовое представление слева добавлено с 32 нулями, поэтому код должен быть исправлен с помощью ltrim() следующим образом:

$cidr = strspn(ltrim(sprintf('%b', current(unpack('N', $mask))), 0), 1);

Обновление 2

Первая проблема также может быть решена с помощью текстового подхода, хотя это требует использования str_split() (который не работает в PHP 4.x):

$mask = vsprintf('%c%c%c%c', array_map('bindec', str_split(str_pad(str_repeat(1, $mask), 32, 0), 8)));

Обновление 3

Для меня работает следующее (тестируется как на 32, так и на 64 бит):

$mask = pack('N', 0xffffffff << (32 - $mask));

В этом процессе число становится плавающим, но сохраняет достаточную точность для обработки сдвига битов.

Ответ 3

Почему бы не сделать:

$netmask = ( (1<<32) -1 ) << ( 32 - $cidr);

Вы сказали, что вам не нравятся левые, а затем правые смены, как насчет двух сдвигов влево;)

После этого я вбрасываю его в ip2long или long2ip. Чтобы перейти от маски к CIDR, я сделаю:

$mask = ip2long($mask);
$base = ( ( 1 << 32 ) - 1 );
$cidr = 32 - log( ( $mask ^ $base ) + 1 , 2);

Конечно, вы можете pack или dechex, или unpack выше, если это необходимо, чтобы соответствовать типу вашего хранилища.

Ответ 4

Зачем его вообще вычислять? Просто создайте массив из 32 масок подсети.

$cidr2mask = array( "\x00\x00\x00\x00", "\x80\x00\x00\x00", "\xc0\x00\x00\x00", "\xe0\x00\x00\x00",
                    "\xf0\x00\x00\x00", "\xf8\x00\x00\x00", "\xfc\x00\x00\x00", "\xfe\x00\x00\x00", 
                    "\xff\x00\x00\x00", "\xff\x80\x00\x00", "\xff\xc0\x00\x00", "\xff\xe0\x00\x00", 
                    "\xff\xf0\x00\x00", "\xff\xf8\x00\x00", "\xff\xfc\x00\x00", "\xff\xfe\x00\x00", 
                    "\xff\xff\x00\x00", "\xff\xff\x80\x00", "\xff\xff\xc0\x00", "\xff\xff\xe0\x00", 
                    "\xff\xff\xf0\x00", "\xff\xff\xf8\x00", "\xff\xff\xfc\x00", "\xff\xff\xfe\x00", 
                    "\xff\xff\xff\x00", "\xff\xff\xff\x80", "\xff\xff\xff\xc0", "\xff\xff\xff\xe0", 
                    "\xff\xff\xff\xf0", "\xff\xff\xff\xf8", "\xff\xff\xff\xfc", "\xff\xff\xff\xfe");

$mask2cidr = array_flip($cidr2mask);

Затем просто используйте $cidr2mask[$cidr]; и $mask2cidr[$mask].

Ответ 5

(Самостоятельное самосовершенствование)

Я построил библиотеку PHP, которая очень похожа на IP-адреса.

Вот как я создаю маску подсети IPv4:

<?php
$mask = (~0) << (32 - $cidr);
$binary_mask = pack('N', $mask);
echo implode('.', unpack('C4', $binary_mask));

Он не будет работать в более старых версиях PHP из-за пространств имен, но имеет ветки до их добавления, к которым я был бы рад принять запросы на загрузку, чтобы исправить проблемы совместимости. Код (почти) на 100% распространяется на модульные тесты:)

Единственная зависимость - это пакет груши Math_BigInteger.