Слово как четыре байта сразу: нулевой байт и разворот битов

Если ты объяснишь, почему вычитание 0x01010101 находит нулевой байт и почему старший из найденных может быть ложным, и развернёшь порядок байтов в 32-битном слове двумя строками, - листай до «Теперь сам».

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

Строка в C заканчивается нулевым байтом, и её длину узнают, читая байты по одному до нуля. Процессор умеет читать сразу четыре или восемь байтов одним словом.

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

На что это похоже

В одной строке бланка через широкие промежутки записаны четыре небольших числа. Нужно от каждого отнять единицу. Можно четыре раза вычесть. А можно прочитать всю строку как одно длинное число и вычесть из него число, в котором под каждым полем стоит единица, - одно вычитание столбиком сделает все четыре, пока ни одно поле не уходит в минус.

А если поле было нулём, оно уйдёт в минус и займёт единицу у соседа слева. Обычно это ошибка. Здесь это и есть сигнал: заём возник - значит, в поле был ноль.

Механизм: заём как признак нуля

Приём, в котором одно слово используют как ряд независимых полей и обрабатывают все поля одной командой, называют SWAR. Сложение половинками из урока про счёт единиц - тоже он.

Выражение разбирается на три шага.

x              =  41  00  43  44        четыре байта, второй слева - ноль
x − 0x01010101 =  3F  FF  42  43        нулевой байт стал FF и занял единицу у соседа слева
~x             =  BE  FF  BC  BB
& 0x80808080      проверяются только старшие биты байтов

(x − 0x01010101) & ~x & 0x80808080  =  00  80  00  00

Пока нет займа от соседа, старший бит байта после вычитания единицы равен единице в двух случаях: байт был нулём и стал FF, или байт был больше 0x80 и остался не меньше 0x80. Второй случай убирает & ~x: у таких байтов старший бит был единицей с самого начала, и в ~x там ноль. Остаётся только первый случай. Маска 0x80808080 оставляет от каждого байта один бит-флажок.

Теперь про заём. Нулевой байт, уходя в FF, занимает единицу у байта слева, и тот уменьшается на два, а не на один. Если слева стоял байт 01, он тоже станет FF и получит ложный флажок:

x              =  00  FF  01  00
результат      =  80  00  80  80        третий слева байт был 01, а не 00

Но заём идёт только влево, к старшим байтам. Правее самого младшего нулевого байта занимать некому, поэтому самый младший флажок всегда честный. Ответ на вопрос «есть ли в слове нулевой байт» точен, ответ «где первый» точен, если первым считать младший.

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

Правило

В слове x есть нулевой байт тогда и только тогда, когда (x - 0x01010101) & ~x & 0x80808080 не ноль; младший установленный флажок указывает на младший нулевой байт, флажки старше могут быть ложными. Байт, равный c, ищут так же в слове x ^ (c * 0x01010101): умножение размножает байт на все четыре места, 0x6C · 0x01010101 = 0x6C6C6C6C. Порядок битов разворачивают пятью обменами соседних полей с масками 0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF, 0x0000FFFF; порядок байтов - двумя последними из них.

Разбор: конец строки по четыре байта

def est_nol(x):
    return (x - 0x01010101) & ~x & 0x80808080

def h(x):
    return hex(x)[2:].zfill(8)

for x in [0x41424344, 0x41004344, 0x41424300, 0x80808080, 0x01010101, 0x00FF0100]:
    print(h(x), h(est_nol(x)))
print(h(0x6C6C6548 ^ 0x6C6C6C6C), h(est_nol(0x6C6C6548 ^ 0x6C6C6C6C)))

41424344 00000000
41004344 00800000
41424300 00000080
80808080 00000000
01010101 00000000
00ff0100 80008080
00000924 80800000

Функция h печатает восемь шестнадцатеричных цифр: hex даёт строку с приставкой 0x, срез её убирает, zfill дополняет нулями слева. Четвёртая и пятая строки вывода - проверка на прочность: байты 80 и 01 нулём не считаются. Шестая - ложный флажок над байтом 01. Последняя - поиск буквы: слово 0x6C6C6548 - это «Hell», записанное младшим байтом вперёд, 0x6C - код буквы l. После ^ байты, равные l, стали нулями, и флажки стоят на двух старших.

Теперь длина строки. Побайтно:

n = 0
while bajty[n] != 0:
    n = n + 1
print(n)

Здесь bajty - коды символов строки с нулём в конце. И по слову за круг: slova собраны из тех же байтов по четыре, первый байт строки - младший, то есть слово - это b0 | b1 << 8 | b2 << 16 | b3 << 24:

i = 0
while (slova[i] - 0x01010101) & ~slova[i] & 0x80808080 == 0:
    i = i + 1
x = slova[i]
n = i * 4
while x & 255 != 0:
    x = x >> 8
    n = n + 1
print(n)

На строке из 407 символов обе программы печатают 407; первая тратит 817 шагов, вторая - 217. Второй цикл досматривает последнее слово побайтно - не больше трёх кругов.

Разбор: разворот битов и байтов, и где начинаются оговорки

def razvernut_bity(x):
    x = (x & 0x55555555) << 1 | x >> 1 & 0x55555555
    x = (x & 0x33333333) << 2 | x >> 2 & 0x33333333
    x = (x & 0x0F0F0F0F) << 4 | x >> 4 & 0x0F0F0F0F
    x = (x & 0x00FF00FF) << 8 | x >> 8 & 0x00FF00FF
    x = (x & 0x0000FFFF) << 16 | x >> 16
    return x

def razvernut_bajty(x):
    x = (x & 0x00FF00FF) << 8 | x >> 8 & 0x00FF00FF
    x = (x & 0x0000FFFF) << 16 | x >> 16
    return x

print(hex(razvernut_bity(0x12345678)), razvernut_bity(1))
print(hex(razvernut_bajty(0x12345678)), hex(razvernut_bajty(0xC0A8011E)))

0x1e6a2c48 2147483648
0x78563412 0x1e01a8c0

Единица в младшем бите переехала в старший: 2³¹ = 2 147 483 648. Вторая строка - порядок байтов. Процессоры x86 и ARM хранят число младшим байтом по младшему адресу, а сетевые протоколы передают старшим байтом вперёд. Адрес 192.168.1.30 в пакете - байты C0 A8 01 1E; прочитанные с провода как одно слово, они дают 0x1E01A8C0, и чтобы получить число 0xC0A8011E, байты разворачивают.

У поиска нулевого байта оговорок три. Первая - ложные флажки: посчитать число нулевых байтов числом флажков нельзя. Вторая - направление: на машине, где первый байт строки попадает в старший байт слова, нужен старший флажок, а он как раз ненадёжен; там проверяют иначе. Третья - край памяти: читая по четыре байта, легко прочитать три байта за концом строки. Пока они на той же странице памяти, это безвредно; за границей страницы, если следующая страница программе не выдана, - аварийная остановка. Настоящая функция длины строки сначала идёт побайтно до адреса, кратного размеру слова, и только потом переключается на слова: выровненное слово границу страницы не пересекает.

Что ломается без этого

Первое: рамка в Python. И x - 0x01010101 для маленького x, и ~x для любого - отрицательные числа. Ответу это не мешает: последняя маска 0x80808080 обрезает результат до 32 битов. Но промежуточные значения на строки схемы не похожи: hex(~0x41004344) печатает -0x41004345, а не beffbcbb. Чтобы увидеть слово, добавляют & 0xFFFFFFFF.

Второе: порядок байтов забыт. Число, записанное в файл на одной машине и прочитанное на другой без разворота, превращается в другое число: 1 становится 16 777 216. Форматы файлов и протоколы поэтому всегда называют порядок явно.

Третье: разворот битов вместо разворота байтов. Это разные операции: при развороте байтов биты внутри байта остаются на местах.

Четвёртое: сдвиг влево без маски. В строках разворота левое слагаемое сначала режется маской и только потом сдвигается - поэтому за 32 бита оно не вылезает. Наоборот - сдвинуть и не обрезать - в Python даёт число длиннее слова.

Зачем это в работе

Функции strlen, memchr и strchr в стандартной библиотеке C работают именно так, по восемь байтов за круг, а на процессорах с широкими регистрами - по 32 или 64 байта. Разборщики JSON и CSV тем же приёмом ищут кавычки и переводы строк сразу во всём слове.

Разворот байтов нужен при каждом разборе сетевого пакета: функции htonl и ntohl - это он, и в процессоре для него есть команда BSWAP. Разворот битов нужен быстрому преобразованию Фурье - элементы переставляются по номерам с развёрнутыми битами - и контрольным суммам из последней главы раздела, которые считают младшим битом вперёд.

Общий случай - собрать в плотную группу биты, отмеченные произвольной маской, или разложить группу обратно - тоже имеет свои команды, PEXT и PDEP. Через них шахматные программы за одну команду получают индекс в таблице ходов.

Теперь сам

1. Вычисли est_nol(0x12003400). Все ли флажки честные?
2. В слове 0x2F727375 нужно найти байт 0x2F. С чем сделать ^ и какой получится флажок?
3. Почему слово 0x80808080 не получает ни одного флажка, хотя после вычитания старшие биты изменились?
4. Разверни порядок байтов в 0x0A000001.
5. Разверни биты в байте 0001 0110 тремя обменами: соседние биты, пары, четвёрки.