Двоичные и побитовые операции в PHP

Недавно я обратил внимание, что в разных проектах мне приходится активно писать побитовые операции на PHP. Это очень интересное и полезное умение, которое пригодится начиная с чтения двоичных файлов до эмуляции процессоров.

В PHP есть много инструментов, помогающих манипулировать двоичными данными, но хочу сразу предупредить: если вам нужно супернизкоуровневая эффективность, то этот язык не для вас.

А теперь к делу! В этой статье я расскажу много интересного о побитовых операциях, двоичной и шестнадцатеричной обработке, которые будут полезны в ЛЮБОМ языке.

• Почему PHP может оказаться не лучшим кандидатом
• Быстрое введение в двоичное и шестнадцатеричное представление данных
• Операции переноса
• Представление данных в памяти компьютера
• Арифметические переполнения
• Двоичные числа и строки в PHP
• Двоичность: что использовать в PHP, числа или строки?
• Отладка двоичных значений в PHP
• Визуализация двоичных строк
• Побитовые операции
• Что такое битовая маска
• Нормализация чисел
• Заключение

Почему PHP может оказаться не лучшим кандидатом

Я люблю PHP, не поймите меня неправильно. И я уверен, что этот язык будет прекрасно работать в большинстве случаев. Но если вам нужна максимальная эффективность обработки двоичных данных, то PHP не потянет.

Поясню: я не говорю о том, что приложение может потреблять на пять или десять мегабайт больше, а о выделении конкретного количества памяти для хранения данных определённого типа.

Согласно официальной документации о целых числах, PHP представляет десятичные, шестнадцатеричные, восьмеричные и двоичные значения с помощью целочисленного типа (integer). Так что не имеет значения, какие данные вы туда положите, они всегда будут целочисленными.

Вероятно, вы уже знаете про ZVAL — это С-структура, представляющая каждую PHP-переменную. В ней есть поле zend_long для представления всех чисел. У этого поля тип lval, размер которого зависит от платформы: на 64-битных платформах поле будет представлено как 64-битное число, а на 32-битных платформах — как 32-битное число.

# zval stores every integer as a lval
typedef union _zend_value {
  zend_long lval;
  // ...
} zend_value;

# lval is a 32 or 64-bit integer
#ifdef ZEND_ENABLE_ZVAL_LONG64
 typedef int64_t zend_long;
 // ...
#else
 typedef int32_t zend_long;
 // ...
#endif

Суть вот в чём: не имеет значения, нужно ли вам хранить 0xff, 0xffff, 0xffffff или что-то другое. В PHP все эти значения будут храниться как long (lval) с длиной 32 или 64 бита.

К примеру, недавно я экспериментировал с эмуляцией микроконтроллеров. И хотя необходимо корректно обрабатывать содержимое памяти и операции, мне не требовалось слишком большой эффективности использования памяти, потому что моя хостинговая машина компенсировала расходы на порядки.

Конечно, всё меняется, если мы говорим о С-расширениях или FFI, но это и не входит в мои цели. Я рассказываю о чистом PHP.

Поэтому помните: он работает и может вести себя так, как вам нужно, но в большинстве случаев типы будут расходовать память неэффективно.

Быстрое введение в двоичное и шестнадцатеричное представление данных

Прежде чем разговаривать о том, как PHP обрабатывает двоичные данные, нужно сначала поговорить о том, что такое двоичность. Если вы думаете, что уже всё знаете об этом, то переходите к главе Двоичные числа и строки в PHP.

В математике есть понятие «основание». Оно определяет, как мы можем представлять количества в разных форматах. Люди обычно используют десятичное основание (основание 10), что позволяет нам представлять любое число с помощью цифр 0, 1, 2, 3, 4, 5, 6, 7, 8 и 9.

Чтобы пояснить следующий пример, я буду называть число 20 как «десятичное 20».

Двоичные числа (основание 2) могут представлять любое число, но только с помощью двух цифр: 0 и 1.

Десятичное 20 в двоичной форме выглядит так: 0b00010100. Вам не нужно преобразовывать его в привычный вид самостоятельно, пусть это делают компьютеры. ;)

Шестнадцатеричные числа (основание 16) могут представлять любые числа с помощью десяти цифр 0, 1, 2, 3, 4, 5, 6, 7, 8 и 9, а также дополнительных шести символов из латинского алфавита: a, b, c, d, e и f.

Десятичное 20 в шестнадцатеричной форме выглядит так: 0x14. Его преобразование тоже возложите на компьютеры, они в этом эксперты!

Важно понимать, что числа можно представлять по разным основаниям: двоичному (основание 2), восьмеричному (основание 8), десятичному (основание 10, наше обычное) и шестнадцатеричному (основание 16).

В PHP и многих других языках двоичные числа пишутся как и любые другие, но с префиксом 0b: десятичное 20 выглядит как 0b00010100. Шестнадцатеричные числа получают префикс 0x: десятичное 20 выглядит как 0x14.

Как вы уже можете знать, компьютеры не хранят литеральные данные. Они всё представляют в виде двоичных чисел, нулей и единиц. Символы, цифры, буквы, инструкции — всё представлено по основанию 2. Буквы являются лишь условностью числовых последовательностей. Например, буква «a» имеет номер 97 в ASCII-таблице.

Но хотя всё хранится в двоичном виде, программистам удобнее всего читать данные в шестнадцатеричном формате. Они так лучше выглядят. Вы только посмотрите:

# string "abc"
'abc'

# binary form (bleh)
0b01100001 0b01100010 0b01100011

# hexadecimal form (such wow)
0x61 0x62 0x63

Хотя двоичный формат визуально занимает много места, шестнадцатеричные данные очень похожи на двоичное представление. Поэтому обычно мы используем их в низкоуровневом программировании.

Операции переноса

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

В десятичном наборе у нас есть десять отдельных цифр для представления чисел, от 0 до 9. Но когда мы пытаемся представить числе больше девяти, нам не хватает цифр! И тут применяется операция переноса: мы делаем для числа префикс из цифры 1, а правую цифру сбрасываем в 0.

# decimal (base 10)
1 + 1 = 2
2 + 2 = 4
9 + 1 = 10 // <- Carry

Двоичное основание ведёт себя так же, только оно ограничено цифрами 0 и 1.

# binary (base 2)
0 + 0  = 0
0 + 1  = 1
1 + 1  = 10 // <- Carry
1 + 10 = 11

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

# hexadecimal (base 16)
1 + 9  = a // no carry, a is in range
1 + a  = b
1 + f  = 10 // <- Carry
1 + 10 = 11

Как вы поняли, для операции переноса нужно больше цифр для представления определённых чисел. Это позволяет нам понять, как ограничены определённые типы данных и, поскольку они хранятся в компьютерах, как ограничено их представление в двоичной форме.

Представление данных в памяти компьютера

Как я упоминал выше, компьютеры всё хранят в двоичном формате. То есть они содержат в памяти только нули и единицы.

Проще всего визуализировать эту концепцию в виде большой таблицы из одной строки и множества колонок (столько, сколько позволяет ёмкость памяти. Каждая колонка представляет собой двоичное число (бит).

Представление нашего десятичного 20 в такой таблице с помощью 8 бит выглядит так:

Позиция (адрес)	0	1	2	3	4	5	6	7
Бит	0	0	0	1	0	1	0	0

Беззнаковое 8-битное целое — это число, которое можно представить максимум с помощью 8 двоичных чисел. То есть 0b11111111 (десятичное 255) будет самым большим среди беззнаковых 8-битных чисел. Добавление к нему 1 потребует применения операции переноса, что уже нельзя представить с помощью того же количества цифр.

Зная это, мы можем легко разобраться, почему для чисел существует так много представлений в памяти и что они собой представляют: uint8 — это беззнаковые 8-битные целочисленные (десятичные 0—255), uint16 — беззнаковые 16-битные целочисленные (десятичные 0—65535). Есть также uint32, uint64 и, теоретически, более высокие.

Знаковые целые числа, которые могут представлять отрицательные значения, обычно используют последний бит для определения положительности (последний бит = 0) или отрицательности (последний бит = 1). Как вы понимаете, они позволяют хранить в том же объёме памяти более маленькие значения. Знаковое 8-битное целочисленное варьируется от —128 до десятичного 127.

Вот десятичное —20, представленное в виде знакового 8-битного целочисленного. Обратите внимание, что задан первый бит (адрес 0, значение 1), это означает отрицательное число.

Позиция (адрес)	0	1	2	3	4	5	6	7
Бит	1	0	0	1	0	1	0	0

Надеюсь, пока всё понятно. Это введение очень важно для понимания внутренней работы компьютеров. Помните об этом, и тогда всегда будете понимать, как PHP работает под капотом.

Арифметические переполнения

Выбранное представление числа (8-битное, 16-битное) определяет минимальное и максимальное значение диапазона. Всё дело в том, как числа хранятся в памяти: добавление 1 к двоичной цифре 1 приводит к операции переноса, то есть нужен другой бит в качестве префикса для текущего числа. Поскольку целочисленный формат очень тщательно определён, мы не можем полагаться на операции переноса, выходящие за заданные пределы (на самом деле это возможно, но довольно безумно).

Позиция (адрес)	0	1	2	3	4	5	6	7
Бит	1	1	1	1	1	1	1	0

Здесь мы очень близки к 8-битному пределу (десятичному 255). Если мы добавим единицу, то получим десятичное 255 в двоичном представлении:

Позиция (адрес)	0	1	2	3	4	5	6	7
Бит	1	1	1	1	1	1	1	1

Все биты назначены! Добавление 1 потребует операции переноса, которая будет невозможна, потому что у нас не хватает битов, все 8 уже назначены! Эта ситуация называется переполнением, мы выходим за какой-то предел. Двоичная операция 255 + 2 должна дать 8-битный результат 1.

Позиция (адрес)	0	1	2	3	4	5	6	7
Бит	0	0	0	0	0	0	0	1

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

Двоичные числа и строки в PHP

Вернёмся к PHP! Извините за этот большой экскурс, но я считаю его важным.

Надеюсь, у вас в голове уже начали собираться кусочки мозаики: двоичные числа, в каком виде они хранятся, что такое переполнение, как PHP представляет числа…

Десятичное 20, представленное в PHP в виде целочисленного значения, в зависимости от платформы может иметь два разных представления. На х86-платформе это будет 32-битное представление, на х64 — 64-битное, но в обоих случаях будет стоять знак (то есть значение может быть отрицательным). Мы знаем, что десятичное 20 может поместиться в 8-битное пространство, но PHP обращается с любым десятичным числом как с 32- или 64-битным.

Также в PHP есть двоичные строки, которые можно преобразовывать туда-обратно с помощью функций pack() и unpack().

В PHP главное отличие между двоичными строками и числами в том, что строки просто содержат данные, как буфер. Целочисленные значения (двоичные и не только) позволяют выполнять с собой арифметические операции, но и двоичные (побитовые), такие как AND, OR, XOR и NOT.

Двоичность: что использовать в PHP, числа или строки?

Для транспортировки данных мы обычно используем двоичные строки. Поэтому чтение двоичного файла или сетевое взаимодействие требует упаковки и распаковки двоичных строк.

Однако фактические операции, такие как OR и XOR, со строковыми не получится выполнять надёжно, поэтому нужно использовать числа.

Отладка двоичных значений в PHP

Теперь давайте развлечёмся и немного поиграем с PHP-кодом!

Сначала я покажу, как визуализировать данные. Надо ведь понять, с чем мы имеем дело.

Отлаживать целые числа очень-очень просто, мы можем использовать функцию sprintf(). У неё очень мощное форматирование, и она поможет нам быстро понять, с какими значениями мы работаем.

Давайте представим десятичное 20 в 8-битном двоичном формате и в 1-байтном шестнадцатеричном:

<?php
// Decimal 20
$n = 20;

echo sprintf('%08b', $n) . "\n";
echo sprintf('%02X', $n) . "\n";

// Output:
00010100
14

Формат %08b выводит переменную $n двоичном представлении (b) с восемью цифрами (08).

Формат %02X выводит переменную $n в шестнадцатеричном представлении (X) с двумя цифрами (02).

Визуализация двоичных строк

Хотя в PHP целые числа всегда длиной 32 или 64 бита, длина строк равна длине их содержимого. Чтобы декодировать их двоичные значения и визуализировать их, нам нужно исследовать и преобразовать каждый байт.

К счастью, в PHP строки не являются именоваными, как массивы, и каждая позиция указывает на символ размером в 1 байт. Вот пример обращения к символам:

<?php
$str = 'thephp.website';

echo $str[3];
echo $str[4];
echo $str[5];

// Outputs:
php

Если считать, что один символ занимает 1 байт, мы можем вызвать функцию ord() для приведения к 1-байтному целому числу:

<?php
$str = 'thephp.website';

$f = ord($str[3]);
$s = ord($str[4]);
$t = ord($str[5]);

echo sprintf(
  '%02X %02X %02X',
  $f,
  $s,
  $t,
);
// Outputs:
70 68 70

Теперь можно выполнить двойную проверку с помощью приложения для командной строки hexdump:

$ echo 'php' | hexdump
// Outputs
0000000 70 68 70 ...

В первой колонке расположен только адрес, а во второй колонке мы видим шестнадцатеричные значения, представляющие символы p, h и p.

Также при обработке двоичных строк мы можем использовать функции pack() и unpack(), и у меня есть для вас отличный пример! Допустим, вам нужно прочитать JPEG-файл, чтобы извлечь какие-нибудь данные (например, EXIF). С помощью режима чтения двоичных данных можно открыть обработчик файла и сразу же прочитать первые два байта:

<?php

$h = fopen('file.jpeg', 'rb');

// Read 2 bytes
$soi = fread($h, 2);

Чтобы извлечь значения в целочисленный массив, можно просто распаковать их:

$ints = unpack('C*', $soi);

var_dump($ints);
// Outputs
array(2) {
  [1] => int(-1)
  [2] => int(-40)
}

echo sprintf('%02X', $ints[1]);
echo sprintf('%02X', $ints[2]);
// Outputs
FFD8

Обратите внимание, что формат С в функции unpack() преобразует символ в строку $soi в виде беззнаковых 8-битных чисел. Модификатор * распаковывает всю строку.

Побитовые операции

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

PHP-код	Название	Описание
$x | $y	Inclusive OR	$x и $y присваивается значение со всеми заданными битами.
$x ^ $y	Exclusive OR	$x или $y присваивается значение с заданными битами.
$x & $y	AND	$x и $y одновременно присваивается значение с заданными битами.
~$x	NOT	Меняет значения всех битов в $x.
$x << $y	Left SHIFT	Смещает биты $x влево на $y позиций.
$x >> $y	Right SHIFT	Смещает биты $x вправо на $y позиций.

Я объясню работу каждого из них!

Пусть $x = 0x20 и $y = 0x30. Ниже я покажу примеры с использованием двоичной нотации.

Как работает Inclusive Or ($x | $y)

Операция inclusive OR (включительное ИЛИ) берёт все биты из обоих входных данных. То есть $x | $y должно вернуть 0x30. Посмотрите:

// 1 | 1 = 1
// 1 | 0 = 1
// 0 | 0 = 0

0b00100000 // $x = 0x20
0b00110000 // $y = 0x30
OR ------- // $x | $y
0b00110000 // 0x30

Примечание: справа налево был задан шестой бит $x (1), а также пятый и шестой биты $y. Данные были объединены и сгенерировано значение заданными пятым и шестым битами: 0x30.

Как работает Exclusive Or ($x ^ $y)

Операция exclusive OR (исключительное ИЛИ, также известное как XOR) берёт биты, имеющиеся только с одной стороны. То есть результатом вычисления $x ^ $y будет 0x10:

// 1 ^ 1 = 0
// 1 ^ 0 = 1
// 0 ^ 0 = 0

0b00100000 // $x = 0x20
0b00110000 // $y = 0x30
XOR ------ // $x ^ $y
0b00010000 // 0x10

Как работает AND ($x & $y)

Оператор AND гораздо проще для понимания. Он к каждому биту применяет операцию И, так что извлечены будут только те значения, которые равны друг другу с обеих сторон. Результатом вычисления $x & $y будет 0x20:

// 1 & 1 = 1
// 1 & 0 = 0
// 0 & 0 = 0

0b00100000 // $x = 0x20
0b00110000 // $y = 0x30
AND ------ // $x & $y
0b00100000 // 0x20

Как работает NOT (~$x)

Операции NOT требуется один параметр, она просто меняет значения всех переданных битов. Все 0 она превращает в 1, а все 1 — в 0.:

// ~1 = 0
// ~0 = 1

0b00100000 // $x = 0x20
NOT ------ // ~$x
0b11011111 // 0xDF

Если вы выполнили эту операцию в PHP и решили отладить с помощью sprintf(), то, вероятно, заметили более широкие числа? В главе Нормализация чисел я объясню, что тут происходит и как это исправить.

Как работает Left SHIFT и Right SHIFT ($x << $n и $x >> $n)

Смещение битов аналогично умножению или делению чисел на степень двойки. Все биты переходят на $n позиций влево или вправо.

Возьмём маленькое двоичное число, чтобы было проще показать, например, $x = 0b0010. Если мы однократно сместим $x влево, этот один бит должен передвинуться на одну позицию влево:

$x = 0b0010;
$x = $x << 1;
// 0b0100

То же самое со смещением вправо:

$x = 0b0100;
$x = $x >> 2;
// 0b0001

То есть смещение числа $n раз влево равносильно умножению двое $n раз, а смещение числа $n раз вправо равносильно делению на два $n раз.

Что такое битовая маска

С этими операциями и прочими методиками можно сделать много интересного. Например, применить битовую маску. Так называется произвольное двоичное число на ваш выбор, созданные для извлечения очень специфической информации.

Например, возьмём идею, что 8-битное знаковое число является положительным, если не задан восьмой бит (0), и отрицательным, если бит задан. Является ли положительным или отрицательным число 0x20? А что насчёт 0x81?

Чтобы ответить на это, мы можем создать очень удобный байт с единственным заданным отрицательным битом (0b10000000, эквивалентно 0x80) и применить к 0x20 операцию AND. Если результат равен 0x80 (0b10000000, нашей маске), то это отрицательное число, в противном случае оно положительное:

// 0x80 === 0b10000000 (bitmask)
// 0x20 === 0b00100000
// 0x81 === 0b10000001

0x20 & 0x80 === 0x80 // false
0x81 & 0x80 === 0x80 // true

Такое часто бывает нужно при работе с флагами. Можно даже найти примеры использования в самом PHP, например, флаги сообщения об ошибках.

Можно выбрать, какого рода ошибки будут выдаваться:

error_reporting(E_WARNING | E_NOTICE);

Что здесь происходит? Просто посмотрите на своё значение:

0b00000010 (0x02) E_WARNING
0b00001000 (0x08) E_NOTICE
OR -------
0b00001010 (0x0A)

Когда PHP видит уведомление, которое можно передать, он проверяет нечто подобное:

// error reporting we set before
$e_level = 0x0A;

// Needs to throw a notice
if ($e_level & E_NOTICE === E_NOTICE)
 // Flag is set: throws notice

И вы увидите это везде! Двоичные файлы, процессоры, всякие низкоуровневые вещи!

Нормализация чисел

В PHP есть одна особенность, связанная с обработкой двоичных чисел: целые числа имеют размер 32 или 64 бита. Это означает, что зачастую нам нужно нормализовать их, чтобы доверять своим вычислениям.

Например, исполнение этой операции на 64-битной машине даст странный (но ожидаемый) результат:

echo sprintf(
  '0b%08b',
  ~0x20
);

// Expected
0b11011111
// Actual
0b1111111111111111111111111111111111111111111111111111111111011111

Что тут произошло? Операция NOT в 8-битном целом числе (0x20) превратила все нулевые биты в единицы. Угадайте, что у нас было нулями? Правильно, все остальные 56 битов слева, которые до этого игнорировались!

Повторюсь, причина в том, что в PHP длина целых чисел составляет 32 или 64 бита, вне зависимости от их значений!

Однако код работает ожидаемо. Например, результатом операции ~0x20 & 0b11011111 === 0b11011111 будет булево значение (true). Но не забывайте, что эти биты слева никуда не деваются, иначе вы получите странное поведение кода.

Для решения этой проблемы можно нормализовать числа, применив битовую маску, которая очищает все нули. Например, для нормализации ~0x20 в 8-битное целое число нужно применить AND с 0xFF (0b11111111), чтобы все предыдущие 56 битов превратились в нули.

~0x20 & 0xFF
-> 0b11011111

Внимание! Не забывайте о том, что содержится в ваших переменных, иначе получите неожиданное поведение. Например, давайте взглянем, что произойдёт, когда мы смещаем вышеописанное значение вправо без 8-битной маски:

~0x20 & 0xFF
-> 0b11011111

0b11011111 >> 2
-> 0b00110111 // expected

(~0x20 & 0xFF) >> 2
-> 0b00110111 // expected

(~0x20 >> 2) & 0xFF
-> 0b11110111 // expected?

Поясню: с точки зрения PHP это является ожидаемым, потому что вы явно обрабатываете 64-битное число. Вы должны понимать, что ожидает ВАША программа.

Совет: избегайте подобных глупых ошибок, программируя в парадигме TDD.

Заключение: двоичность и PHP классные

Когда вооружишься такими инструментами, всё остальное превращается лишь в поиск правильной документации по поведению двоичных файлов или протоколов. Ведь всё является двоичными последовательностями.

Очень рекомендую почитать спецификации PDF или EXIF. Возможно, вы даже захотите поэкспериментировать с собственной реализацией формата сериализации MessagePack, или Avro, Protobuf… Возможности безграничны!