Главная » Хабрахабр » [Перевод] Куча различных способов считывания битов

[Перевод] Куча различных способов считывания битов

image

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

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

Первый источник проблем заключается в том, что эта операция будет активно использовать кодеки — и да, она будет ограничена вычислениями, а не памятью и вводом-выводом. Это звучит достаточно просто, и в каком-то смысле так и есть. И по дороге мы столкнёмся со множеством других сложностей: взаимодействия с буферизацией ввода-вывода, обработка конца буфера, тупиковые ситуации в битовых сдвигах, определённых в C/C++ и в разных архитектурах процессоров, а также другие особенности битовых сдвигов. Поэтому нам нужна не просто рабочая, но и эффективная реализация.

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

Степени свободы

«Считать переменное количество битов» — это недостаточное описание задачи. Существует множество приемлемых способов упаковки битов в байты, и у всех них есть свои сильные и слабые места, о которых я расскажу позже. Пока же давайте просто остановимся на их различиях.

То есть если мы вызовем реализуемую функцию getbits и выполним следующий код Для начала нам нужно сделать первый важный выбор — поля будут упаковываться в виде «первым идёт MSB» или «первым идёт LSB» («most significant bit» — наиболее значимый бит и «least significant bit» — наименее значимый бит).

a = getbits(4);
b = getbits(3);

для только что открытого битового потока, то мы ожидаем, что оба значения будут получены от одного и того же байта, но как они упорядочены в этом байте? Если упакованы в виде MSB-first, то «a» занимает 4 бита, начиная с MSB, а «b» находится ниже «a», что приводит нас к следующей схеме:

Я нумерую биты так: LSB — это 0 и приближаясь к MSB, значения увеличиваются. Во многих контекстах такой порядок является стандартным. LSB-first представляет собой противоположную ситуацию: первое поле занимает бит 0, а следующие поля содержат увеличивающиеся номера битов:

Оба формата используются в часто встречающихся форматах файлов. Например, в JPEG применяется упаковка битов в битовом потоке в формате MSB-first, а в DEFLATE (zip) используется LSB-first.

Допустим, у нас есть ещё одно значение «c», которое мы хотим закодировать в 5 битах. Следующий вопрос, который нам нужно решить, заключается в том, что произойдёт, когда значение оказывается растянутым на несколько байтов. Мы можем слегка отсрочить решение проблемы, объявив, что упаковываем значения в 32-битные или 64-битные слова, а не в байты, но в конце концов нам придётся что-то выбирать. Что у нас в результате получится? И здесь мы внезапно сталкиваемся со множеством различных вариантов, поэтому я рассмотрю только основных претендентов.

Заполнив один байт, мы приступаем к следующему. Мы можем воспринимать упаковку битов MSB-first как итерирование по битовому полю «c» от его MSB по направлению к LSB, со вставкой по одному биту за раз. Если следовать этим правилам для нашего битового поля c, то в результате в нашем потоке биты окажутся в следующей схеме:

Учтите, что следуя этим правилам, мы в результате придём к тем же двум байтам, которые получили бы, упаковав биты MSB в большой integer и сохранив его в порядке big-endian. Если бы мы вместо этого решили разбить «c» таким образом, чтобы его LSB был в первом байте, а четыре его бита более высшего порядка — во втором байте, то это бы не сработало. Я буду называть такие непротиворечивые правила упаковки битов «естественными» правилами.

Оно заключается во вставке нового значения бит за битом, начиная с LSB и вверх, и если мы так сделаем, то в результате получим следующий битовый поток: Разумеется, у упаковки битов LSB-first существует собственное естественное правило.

Естественная упаковка LSB-first даёт нам те же байты, что и упаковка LSB-first в большой integer с сохранением его в порядке байтов little-endian. Кроме того, у нас на рисунке возникает очевидная неуклюжесть: логически сопряжённая упаковка поля «c» в несколько байтов выглядит на таком рисунке прерывистой, в то время как рисунок упаковки MSB-first выглядит так, как мы того и ожидаем. Но и в нём возникает проблема: в рисунке MSB-first мы нумеруем биты в увеличивающемся справа налево порядке (стандартном), а байты — в увеличивающемся слева направо порядке (что тоже является стандартным).

Вот, что происходи со схемой битов LSB-first, если мы нарисуем бит 0 (LSB) в каждом байте слева, а бит 7 (MSB) — справа:

Если нарисовать так, то схема будет выглядеть ожидаемым нами способом. Расположение MSB справа кажется странным, если думать о байте как о числе, но гораздо менее странным оказывается, если думать о нём как о массиве из 8 бит (как мы, по сути, и работаем с ним при выполнении побитового ввода-вывода).

Создав схему упаковки битов MSB-first на такой машине с битом 0=MSB, и нумеруя наши собственные битовые поля таким образом, чтобы их бит 0 соответствовал MSB, мы получим точно такую же схему (но это будет означать, что что-то немного отличается). По совпадению, в некоторых big-endian-архитектурах (например, в IBM POWER) биты нумеруются следующим образом — бит 0 — это MSB, бит 31 (или 63) — LSB. Этот стандарт делает порядок битов и байтов согласующимся (что хорошо), но разрушает удобный стандарт соответствия бита k значению 2k (что не совсем хорошо).

Или же увеличивать адреса вправо, но стать немного другим бунтарём и записывать байтовый поток в обратном порядке. И если мысль о перенумерации битов таким образом, чтобы бит 0 являлся MSB, взрывает вам мозг, то можно оставить нумерацию битов неизменной, но стать бунтарём и рисовать адреса байтов увеличивающимся слева. Если выбрать один из этих вариантов, то мы получим следующую схему:

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

Что касается порядка байтов и необходимости упаковки значений в байты, слова или что-то более крупное, то я крайне рекомендую вам использовать наиболее естественный порядок для вашего стандарта упаковки битов: MSB-first естественным образом соответствует порядку байтов в стиле big-endian, а LSB-first естественно соответствует порядку байтов little-endian. Получается у каждого из стандартов упаковки MSB-first и LSB-first есть свои достоинства и недостатки, и гораздо полезнее будет думать о них как об инструментах с разными областями применения, а не назначать один из них «правильным», а другие «ошибочными». Если только вы не записываете байтовые потоки в обратном порядке (верите или нет, но есть логичные причины поступать и так); в этом случае у нас получается MSB-first в обратном порядке, соответствующий little-endian, и LSB-first в обратном порядке, соответствующий big-endian.

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

Наш первый getbits (извлечение битов)

Теперь, когда мы в достаточном объёме описали задачу, можем реализовать решение. Особо простая версия возможна, если предположить, что весь битовый поток расположен в памяти последовательно (как массив байтов), и пока полностью игнорировать неприятные проблемы наподобие попадания в конец массива. Давайте просто притворимся, что он бесконечен! (Или достаточно огромен, или имеет по краям заполнение нулями.)

Давайте начнём с упаковки битов LSB-first: В этом случае мы можем основать реализацию на чисто функциональной функции «извлечения битов», в которой я проиллюстрирую возникающие проблемы и всевозможные функции считывания битов.

// Считаем buf[] одним гигантским числом integer little-endian, получаем "width"
// битов, начиная с номера бита "pos" (LSB=бит 0).
uint64_t bit_extract_lsb(const uint8_t *buf, size_t pos, int width) { assert(width >= 0 && width <= 64 - 7); // Считываем 64-битное число little-endian, начиная с байта, // содержащего бит номер "pos" (относительно "buf"). uint64_t bits = read64LE(&buf[pos / 8]); // Смещаем биты внутри первого байта, который // мы уже считали. // После этого LSB нашего битового поля является LSB битов. bits >>= pos % 8; // Возвращаем нижние "width" битов, обнуляя остальные с помощью битовой маски. return bits & ((1ull << width) - 1);
} // Переменная состояния, предполагается локальной или
// принадлежащей какому-нибудь объекту.
const uint8_t *bitstream; // Входящий битовый поток
size_t bit_pos; // Текущая позиция в потоке в битах. uint64_t getbits_extract_lsb(int width) { // Считывание битов uint64_t result = bit_extract_lsb(bitstream, bit_pos, width); // Перемещаем курсор bit_pos += width; return result;
}

Мы просто воспользовались тем упомянутым выше фактом, что битовый поток LSB-first — это просто большое число little-endian. Сначала мы получаем 64 смежных, упорядоченных в байты битов, начиная с первого байта, содержащего любые из интересующих нас битов, совершаем сдвиг вправо, чтобы избавиться от оставшихся лишних 0-7 битов ниже первого нужного нам бита, а затем возвращаем результат, маской приведённый к нужной ширине.

Поэтому хотя мы и считываем полные 64 бита, максимальное количество, которое мы можем считать за один раз с помощью этого кода, равно 64-7=57 битам. В зависимости от значения pos, это смещение вправо может стоить нам дополнительных 7 битов.

Имея bitextract, мы запросто можем реализовать getbits; мы просто отслеживаем текущую позицию битового потока (в битах), и выполняем его инкремент после считывания.

Соответствующий вариант для MSB-first получается довольно похожим образом, за исключением одной раздражающей проблемы, о которой я расскажу после демонстрации кода:

// Считаем buf[] одним гигантским числом integer big-endian, получаем "width"
// битов, начиная с номера бита "pos" (MSB=бит 0).
uint64_t bit_extract_msb(const uint8_t *buf, size_t pos, int width) { assert(width >= 1 && width <= 64 - 7); // Считываем 64-битное число big-endian, начиная с байта, // содержащего бит номер "pos" (относительно "buf"). uint64_t bits = read64BE(&buf[pos / 8]); // Смещаем биты внутри первого байта, который мы уже считали. // После этого MSB нашего битового поля находится в MSB битов. bits <<= pos % 8; // Возвращаем верхние "width" битов. return bits >> (64 - width);
} uint64_t getbits_extract_msb(int width) { // Считываем биты uint64_t result = bit_extract_msb(bitstream, bit_pos, width); // Перемещаем курсор bit_pos += width; return result;
}

Этот код работает аналогично предыдущему: считываем 64 смежных, упорядоченных в байты бита (на этот раз big-endian), выполняем сдвиг влево, чтобы выровнять верх нужного нам битового поля с MSB bits (в то время как раньше мы делали сдвиг вправо, чтобы выровнять низ нашего битового поля с LSB bits), а затем делаем сдвиг вправо, чтобы расположить верхние width битов внизу для их возврата, потому что при вызове getbits(3) мы обычно ожидаем увидеть значение от 0 до 7.

Граничные случаи сдвигов

Так в чём же проблема? Эта версия кода не позволяет width быть равной нулю. Проблема в том, что если мы позволим сделать width == 0, то конечный сдвиг попытается сдвинуть вправо 64-битное значение на 64 бита, а в C/C++ это неопределённое поведение! В таком случае мы можем выполнять сдвиг на 0-63 байта.

Известный пример: отсутствие требования того, чтобы представление знаковых чисел использовало дополнительный код; хотя архитектуры без дополнительного кода существуют, все они сегодня сохранились лишь в музеях. В некоторых случаях C/C++ оставляет детали неопределёнными для обратной совместимости с машинами, поэтому никто сейчас об этом не беспокоится.

Вот, что происходит на разных широко распространённых архитектурах CPU, когда величина сдвига находится вне пределов интервала: К сожалению, у нас не один из таких случаев.

  • Для 32-битных x86 и x86-64 величины сдвига интепретируются как mod 32 для ширины операндов 32 бит и ниже, и mod 64 для 64-битных операндов. То есть сдвиг вправо 64-битного значения на 64 в результате даст то же, что и сдвиг на 0, т.е. отсутствие операции (no-op).
  • В 32-битных ARM (наборы инструкций A32/T32) величины сдвига берутся mod 256. Сдвиг вправо 32-битного значения на 32 (или 64) в результате даст 0, как и сдвиг вправо на 255, но сдвиг вправо на 256 оставит значение нетронутым.
  • В 64-битных ARM (A64 ISA) величины сдвига берутся mod 32 для 32-битных сдвигов и mod 64 для 64-битных сдвигов (по сути так же, как и в x86-64).
  • RISC-V тоже следует тому же правилу: расстояния 32-битных сдвигов берутся как mod 32, расстояния 64-битных сдвигов — как mod 64.
  • В POWER/PowerPC 32-битные сдвиги берут величину сдвига mod 64, а 64-битные сдвиги берут величину сдвига mod 128.

Чтобы ещё более запутать нас, большинство этих наборов инструкций имеют расширения SIMD, а целочисленные инструкции SIMD обладают другим поведением при сдвиге вне пределов интервала, отличающимся от инструкций не-SIMD. Если вкратце, то это один из тех случаев, когда присутствуют архитектурные различия между популярными платформами; для большинства из вас POWER и RISC-V могут показаться немного устаревшими, но, допустим, 32-битные и 64-битные ARM установлены на данный момент в сотнях миллионов устройств.

На ARM A64 и x86-64 результат сдвига на 64 по сути будет no-op, а getbits(0) поэтому будет (обычно) возвращать ненулевое значение, хотя следует ожидать, что возвращаться должен ноль. Следовательно, даже если всё, что делает компилятор с этим сдвигом вправо — это отдаёт соответствующую инструкцию сдвига вправо для целевой архитектуры (а обычно так и происходит), то мы будем видеть на разных архитектурах разное поведение.

Разумеется, жёстко прописанный в коде getbits(0) не является интересным случаем применения; однако иногда нам необходимо выполнить getbits(x) для какой-то переменной x, где x в некоторых случаях может быть нулём. Почему же это так важно? В этом случае было бы здорово, чтобы код просто работал и не требовал каких-то проверок особых случаев.

Если вы хотите, чтобы этот случай работал, то одним из вариантов будет явная проверка на width == 0 и обработка этого особым образом; другим вариантом будет использование выражения без ветвления, работающего с нулевыми ширинами, например, этого кода, применяемого в FSE Йенна Коллета:

// Возвращаем верхние "width" бит, избегая граничных случаев с width==0. return (bits >> 1) >> (63 - width);

Этот конкретный случай проще обрабатывать для битовых потоков LSB-first. И поскольку я упомянул их, давайте поговорим об операции использования маски, которую я применил для изолирования нижних width битов:

// Возвращаем нижние "width" бит, обнуляя остальные с помощью битовой маски. return bits & ((1ull << width) - 1);

Существует аналогичная форма, которая немного менее затратна в архитектурах с трёхоперандной инструкцией and-with-complement (AND-NOT). К ним относятся многие процессоры RISC CPU, а также x86s с BMI1. А именно, мы можем взять маску всех битов-единиц, выполнить сдвиг влево, чтобы добавить внизу width нулей, а затем дополнить всё:

return bits & ~(~0ull << width);

Если у вас x86 не только с BMI1, но и с поддержкой BMI2, вы также можете использовать инструкцию BZHI, специально созданную для такого случая, если разберётесь с тем, как заставить компилятор отдать её (или использовать ассемблер). Ещё один вариант, который в некоторых случаях будет предпочтительным — просто подготовить небольшую таблицу поиска битовых масок, которая упрощает код до такого:

return bits & width_to_mask_table[width];

Подготовка таблицы поиска, хранящей результат двух целочисленных операций, может показаться смешным действием, особенно потому что вычисление адреса загружаемого элемента таблицы обычно включает в себя и сдвиг, и сложение — ровно те же самые операции, которые мы бы выполняли, если бы у нас не было таблицы! — но в этом безумии есть свой метод: вычисление требуемого адреса может выполняться как часть доступа к памяти в одной инструкции загрузки, например, на машинах с x86 и ARM, поэтому эти сдвиг и сложение вычисляются в блоке генерации адреса (Address Generation Unit, AGU) как часть конвейера загрузки в ЦП, а не с инструкциями целочисленной арифметики и сдвига. То есть подобное контринтуитивное решение заменить две целочисленные инструкции ALU одной инструкцией загрузки целого числа может привести к значительному ускорению кода с активным битовым вводом-выводом, потому что оно лучше уравновешивает нагрузку между разными операционными блоками.

Это важно, потому что по множеству (часто банальных!) причин во многих микроархитектурах сдвиги целых чисел на переменные величины более затратны, чем сдвиги на постоянные величины времени компилирования. Ещё одно интересное свойство заключается в том, что версия LSB-first, использующая таблицу поиска масок, выполняет один сдвиг на переменную величину (чтобы сдвинуть уже считанные биты). На многих микроархитектурах Intel x86 «традиционные» переменные сдвиги x86 (SHR reg, cl и подобные им) в три раза затратнее, чем сдвиги на константу времени компилирования. Например, Cell PPU/Xbox 360 Xenon были печально известны тем, что имели сдвиги на переменное расстояние, тормозившие ядро процессора на ужасно долгое время — 12 циклов, а обычные сдвиги были встроены в конвейер и выполнялись за два цикла.

Но существует трюк, благодаря которому можно вернуться к операции с одиночным сдвигом, а именно использование вместо обычного сдвига циклического: Кажется, что это ещё одна причина отказа от варианта MSB-first: рассмотренные выше варианты выполняют два или три сдвига на операцию извлечения битов, два из которых имеют переменное расстояние.

// Считаем buf[] одним гигантским числом integer big-endian, получаем "width"
// битов, начиная с номера бита "pos" (MSB=бит 0).
uint64_t bit_extract_rot(const uint8_t *buf, size_t pos, int width) { assert(width >= 0 && width <= 64 - 7); // Считываем 64-битное число big-endian, начиная с байта, // содержащего бит номер "pos" (относительно "buf"). uint64_t bits = read64BE(&buf[pos >> 3]); // Выполняем поворот влево, чтобы выровнять низ нашего битового поля с LSB. bits = rotate_left64(bits, (pos & 7) + width); // Возвращаем нижние "width" бит. // (Здесь с использованием таблицы, но также будут работать и другие // способы использования масок в битовом вводе-выводе LSB-first.) return bits & width_to_mask_table[width];
}

Здесь поворот влево (вы должны сами выяснить, как наилучшим образом использовать его в вашем компиляторе C) сначала выполняет работу исходного сдвига влево, а затем выполняет поворот на дополнительные «width» бит, чтобы заставить битовое поле перевернуться от наиболее значимых битов значения к наименее значимым, после чего к ним можно применить маску так же, как и в варианте LSB-first.

Это эквивалентные замены, и вы можете увидеть такие формы в настоящем коде, поэтому я решил их сюда добавить. А, да, и я начал писать деление на 8 как сдвиг право на 3, и mod-8 нашей беззнаковой позиции как двоичное AND с 7.

Стоит заметить, что у этой версии тоже нет проблем с width == 0; единственная проблема — это зависимость от инструкций поворота, которые существуют (и быстро выполняются) в большинстве архитектур, но обычно к ним неудобно получать доступ из кода на C. С помощью такой операции маски поворотом мы (в RAD Game Tools) выполняли считывание битов в Cell PPU и Xbox 360, только потому, что на этом ядре сдвиги с переменным расстоянием были так ужасны.

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

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

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

Вариант 1: считывание ввода по одному байту за раз

Наш считыватель-«извлекатель» предполагал, что весь битовый поток заранее находится в памяти. Это не всегда возможно или желательно; давайте исследуем другой предельный случай, а именно считыватель битов, запрашивающий дополнительные биты по одному за раз и только тогда, когда они нужны.

Нам нужно хранить эти данные в переменной, которую мы назовём «битовым буфером»: В общем случае наши варианты с состоянием будут получать ввод по несколько байт за раз, и у них будут несколько частично обработанных байтов.

// Здесь переменные снова считаются состоянием побитового считывателя
// или локальными, а не глобальными переменными.
uint64_t bitbuf = 0; // значение битов в буфере
int bitcount = 0; // количество битов в буфере

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

Без лишних слов давайте создадим нашу первую реализацию getbits, считывающую по одному байту за раз, и на этот раз начнём с MSB-first:

// Инвариант: в "bitbuf" есть "bitcount" битов, сохранённых с
// MSB сверху вниз; остальные биты в "bitbuf" - это 0. uint64_t getbits1_msb(int count) // Теперь у нас присутствует достаточно битов; наибольшие значимые // "count" биты из "bitbuf" являются нашим результатом. uint64_t result = bitbuf >> (64 - count); // Теперь удаляем эти биты из буфера bitbuf <<= count; bitcount -= count; return result;
}

Как и раньше, мы можем избавиться от требования count≥1, изменив способ получения битов результата, как объяснено в предыдущей части. Я упоминаю об этом в последний раз; просто учитывайте, что каждый раз, когда я буду показывать какой-нибудь вариант алгоритма, то к нему автоматически применяются предыдущие вариации.

Если нет, то мы записываем дополнительные байты по одному за раз, пока у нас не будет их достаточно. Идея здесь довольно проста: сначала мы проверяем, достаточно ли в буфере битов для немедленного удовлетворения запроса. Поскольку мы вставляем по 8 бит за раз, то за один вызов мы можем считать максимум 57 бит; это наибольшее количество битов, на которое мы можем пополнить буфер, не рискуя при этом ничего упустить. Здесь подразумевается, что getbyte() в идеале будет использовать некий механизм буферизированного ввода-вывода, который просто сводится к разыменованию и инкременту указателя на критическом пути; если этого можно избежать, он не должен быть вызовом функции или чем-то затратным.

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

Фаза «пополнения» гарантирует, что в буфере будет присутствовать минимальное количество бит; «просмотр» возвращает несколько следующих битов в буфере, не отбрасывая их, а «потребление» удаляет биты, не глядя на них. Стоит также заметить, что этот процесс удобно разбивается на три отдельные операции меньшего объёма, которые я назову «пополнение» (refill), «просмотр» (peek) и «потребление» (consume). Все они оказываются полезными по отдельности операциями; чтобы показать, как всё это организуется, я покажу эквивалент алгоритма LSB-first, разделённого на меньшие части:

// Инвариант: в "bitbuf" есть "bitcount" битов, сохранённых с
// LSB в снизу вверх; остальные биты в "bitbuf" - это 0.
void refill1_lsb(int count) { assert(count >= 0 && count <= 57); // Новые байты вставляются в верхний конец. while (bitcount < count) { bitbuf |= (uint64_t)getbyte() << bitcount; bitcount += 8; }
} uint64_t peekbits1_lsb(int count) { assert(bit_count >= count); return bitbuf & ((1ull << count) - 1);
} void consume1_lsb(int count) { assert(bit_count >= count); bitbuf >>= count; bitcount -= count;
} uint64_t getbits1_lsb(int count) { refill1_lsb(count); uint64_t result = peekbits1_lsb(count); consume1_lsb(count); return result;
}

Запись getbits в виде сочетания таких трёх меньших примитивов не всегда оптимальна. Например, если мы используем метод поворота для битовых буферов MSB-first, то хотим, чтобы поворот был разделён между фазами peekbits и consume; оптимальная реализация разбивает работу на эти две фазы. Однако разбить код на эти отдельные этапы всё равно полезно, потому что когда вы освоите все эти три фазы как отдельные этапы, то сможете по-разному использовать их вместе.

Смотрим вперёд

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

a = getbits(4); b = getbits(3); c = getbits(5);

Когда getbits реализован так, как выше, этот код будет проверять пополнение (и возможно сам процесс пополнения) до трёх раз. Но это глупо; мы заранее знаем, что будем считывать 4+3+5=12 бит за один раз, поэтому можем получить их все одновременно:

refill(4+3+5); a = getbits_no_refill(4); b = getbits_no_refill(3); c = getbits_no_refill(5);

где getbits_no_refill — это ещё один вариант getbits, который выполняет peekbits и consume, но, как понятно из названия, без пополнения. И когда мы избавились от цикла пополнения между отдельными вызовами getbits, то у нас остался только прямолинейный целочисленный код, который хорошо оптимизируется компиляторами. Иными словами, случай с фиксированными длинами малозатратен; он становится ещё интереснее, когда мы не знаем, сколько битов мы на самом деле будем потреблять, например, как здесь:

temp = getbits(5); if (temp < 28) result = temp; else result = 28 + (temp - 28)*16 + getbits(4);

Это простой код с переменной длиной, где значения с 0 по 27 передаются в 5 битах, а значения от 28 до 91 передаются в 9 битах. Смысл в том, что в этом случае мы не знаем заранее, сколько битов мы в дальнейшем потребим. Однако мы знаем, что их больше 9 битов, поэтому всё равно можем сделать так, чтобы пополнение происходило только один раз:

refill(9); temp = getbits_no_refill(5); if (temp < 28) result = temp; else result = 28 + (temp - 28)*16 + getbits_no_refill(4);

На самом деле, если хотите, можно пуститься во все тяжкие и ещё больше разбить операции, чтобы оба пути выполнения только один раз потребляли (consume) биты. Например, при использовании битового буфера MSB-first, мы можем написать этот маленький декодер так:

refill(9); temp = peekbits(5); if (temp < 28) { result = temp; consume(5); } else { // "Верхний" и "нижний" код стоят спина к спине, // и сочетаются идеально подходящим нам способом! Синергия! result = getbits_no_refill(9) - 28*16 + 28; }

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

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

Изменённый считыватель кода начинает получать дополнительные входные данные ещё до того, как будет уверен в их необходимости. Так мы познакомились с методом lookahead. Да, он может никогда не привести к сбою или считыванию вне пределов потока; но кроме этого он подразумевает принцип работы слоя буферизации ввода или кадрирования. Такой подход имеет много плюсов, но компромисс заключается в том, что он может заставить нас выполнить считывание за пределами логического конца битового потока; это подразумевает, что нам обязательно нужно обеспечить правильную обработку такого случая.

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

  • Мы можем просто плыть по течению и сделать это чьей-то чужой проблемой, потребовав, чтобы все передавали нам правильные данные с дополнительными байтами-заполнителями после конца. Это упрощает нам жизнь, но неудобно для всех остальных.
  • Мы можем организовать всё так, чтобы внешний слой кадрирования, передающий байты процедуре getbits, знал, когда заканчивается сам поток данных (благодаря или какому-то управляющему механизму, или явному заданию размера); затем мы можем или завершить выполнение заглядывания вперёд и при приближении к концу переключиться на более внимательный декодер, или заполнить поток каким-то пустым значением после завершения (чаще всего используются нули).
  • Мы можем сделать так, чтобы какие бы байты мы ни получали во время lookahead при декодировании валидного потока, они всё равно оставались частью общего байтового потока, который обрабатывается нашим кодом. Например, если мы используем 64-битный битовый буфер, то можем обойти проблему, потребовав наличия сразу после битового потока какого-нибудь 8-байтного заполнителя (допустим, контрольной суммы или чего-то подобного). Поэтому даже если наш битовый буфер залез слишком далеко, то эти данные всё равно в результате будут потреблены декодером, что значительно упрощает логистику.
  • В таком случае, любой слой буферизации ввода-вывода, который мы используем, должен позволить нам возвращать некие дополнительные байты, которые мы на самом деле не потребили в буфер. А именно, какие бы байты lookahead у нас ни остались в битовом буфере после завершения декодирования, их необходимо вернуть в буфер для того кода, который будет считывать его дальше. По сути, именно это делает функция стандартной библиотеки C ungetc, только мы не можем вызывать ungetc больше одного раза, а это может нам понадобиться. Поэтому выбор этого пути обрекает нас на внесение изменений в управление буфером ввода-вывода.

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

Вариант 2: когда нам очень нужно считать 64 бита за раз

Все рассмотренные ранее методы используют различные хитрости, чтобы избежать работы с байтовой гранулярностью. Извлекающий читыватель битов начинает с считывания полных 64 битов, но затем ему приходится выполнять сдвиг на 7 позиций, чтобы отбросить уже потреблённую часть текущего байта, а показанный выше getbits1 вставляет в битовый буфер по одному байту за раз; если в буфере уже есть 57 битов, но для нового байта в нём нет места (потому что в результате получится 65 битов, что больше ширины буфера), поэтому такова максимальная ширина, поддерживаемая методом getbits1. 57 бит — это довольно полезный объём, но если мы будем работать на 32-битной платформе, то аналогичным волшебным числом будет 25 бит (32-7), и это довольно малая величина, которой часто недостаточно.

Думаю, на этом этапе вы уже поняли соотношение между методами для MSB-first и LSB-first, поэтому я покажу решение только для одного варианта. К счастью, если нам требуется полная ширина, существуют способы реализовать её (как и технике с поворотом и масками битовых буферов для MSB-first, я научился этому в RAD). Давайте выберем LSB-first:

// Инвариант: "bitbuf" содержит "bitcount" бит, начиная с
// LSB и вверх; 1 <= bitcount <= 64
uint64_t bitbuf = 0; // значение битов в буфере
int bitcount = 0; // количество битов в буфере
uint64_t lookahead = 0; // следующие 64 бита
bool have_lookahead = false; // Это необходимо сделать, чтобы запустить систему!
void initialize() { bitbuf = get_uint64LE(); bitcount = 64; have_lookahead = false;
} void ensure_lookahead() { // берёт слово lookahead, если // у нас его ещё нет. if (!have_lookahead) { lookahead = get_uint64LE(); have_lookahead = true; }
} uint64_t peekbits2_lsb(int count) { assert(bitcount >= 1); assert(count >= 0 && count <= 64); if (count <= bitcount) { // достаточно битов в buf return bitbuf & width_to_mask_table[count]; } else { ensure_lookahead(); // сочетаем текущий bitbuf с lookahead // (биты lookahead поступают в верхнюю часть текущего buf) uint64_t next_bits = bitbuf; next_bits |= lookahead << bitcount; return next_bits & width_to_mask_table[count]; }
} void consume2_lsb(int count) { assert(bitcount >= 1); assert(count >= 0 && count <= 64); if (count < bitcount) { // по-прежнему в текущем buf // просто сдвигаем биты bitbuf >>= count; bitcount -= count; } else { // всё из текущего buf потреблено ensure_lookahead(); // мы полностью перешли на слово lookahead int lookahead_consumed = count - bitcount; bitbuf = lookahead >> lookahead_consumed; bitcount = 64 - lookahead_consumed; have_lookahead = false; } assert(bitcount >= 1);
} uint64_t getbits2_lsb(int count) { uint64_t result = peekbits2_lsb(count); consume2_lsb(count); return result;
}

Такой подход чуть более сложен, чем рассмотренные нами выше, и требует этапа явной инициализации для правильной работы инвариантов. Также в отличие от предыдущих вариантов, в нём используется несколько дополнительных ветвлений, что делает его не слишком подходящим для машин с чётким конвейером, в том числе и для PC. Кроме того, заметьте, что я снова использую width_to_mask_table, и это не просто для демонстрации: никакие арифметические выражения, которые мы использовали в прошлый раз для вычисления маски заданной ширины, не работают для полного интервала 0-64 допустимой width в распространённых 64-битных архитектурах, кроме IBM POWER. Да и в ней она работает, только если мы будем игнорировать вызов неопределённого поведения, чего, разумеется, допускать нельзя.

Мы знаем, сколько битов осталось от последнего считанного 64-битного значения, и когда их недостаточно для peekbits, мы получаем следующее 64-битное значение из входного потока (с помощью реализованного внешне get_uint64LE()), чтобы получить биты, которых нам не хватает. Лежащая в основе идея довольно проста: вместо всего одного битового буфера мы отслеживаем два значения. Если нет, то мы переключаемся на биты из значения lookahead (выполняя сдвиг на те из них, которые были потреблены) и сбрасываем флаг have_lookahead, чтобы указать, что бывшее значение lookahead теперь просто является содержимым битового буфера. Аналогично, consume проверяет, останутся ли биты в текущем входном буфере после потребления width бит.

Например, посмотрите, как peekbits проверяет count <= bitcount, чтобы распознать случай наличия битов в буфере, а consume использует count < bitcount. В этом коде присутствуют ветвления, чтобы гарантировать отсутствие сдвигов вне допустимого диапазона (которые вызывают неопределённое поведение). Поскольку это происходит только на пути, где bitcount < count ≤ 64, то значит bitcount < 64 и мы в безопасности. Это не случайно: вычисление next_bits в peekbits включает в себя сдвиг вправо на bitcount. Условие, окружающее блок, гарантирует, что lookahead_consumed ≥ 0; в другом направлении, поскольку count не больше 64, а bitcount не меньше 1, у нас получается lookahead_consumed ≤ 64 – 1 = 63. В consume ситуация обратная: мы выполняем сдвиг на lookahead_consumed = count - bitcount. То есть, перефразируя слова Кнута, «опасайтесь багов в представленном выше коде; я всего лишь доказал его правильность, но не проверял его».

Показанный выше вариант 1 считывает байты за раз, но требует цикла пополнения; различные варианты без ветвления, которые мы рассмотрим ниже, неявно полагаются на поддержку целевым процессором быстрых невыровненных считываний. Кроме большей ширины битовых полей, эта техника имеет ещё один плюс: заметьте, что она всегда за раз считывает полные 64-битовые uint. Это единственная из версий, выделяющаяся считыванием одного размера и постоянным выравниванием, что делает её более привлекательной для целевых систем, не поддерживающих быстрые невыровненные считывания, например, для множества старых процессоров RISC.

Например, если у нас есть данные, которые мы полностью декодируем в памяти, то нет причин возиться с булевым флагом have_lookahead; можно просто хранить указатель на текущее слово lookahead, и увеличивать этот указатель при потреблении текущего lookahead. Как обычно, существует куча других вариаций, которые я не буду показывать.

Вариант 3: возврат к извлечению битов

Исходный считыватель битов с извлечением из предыдущей части был довольно затратным. Но если нас устраивает требование того, что весь входной поток одновременно находится в памяти, то мы можем обернуть его в паттерн refill/peek/consume, чтобы получить что-то полезное. У нас всё равно будет битовый считыватель, который заглядывает вперёд (а потому создаёт соответствующие сложности), но такова жизнь. Здесь мы для примера снова используем MSB:

const uint8_t *bitptr; // Указатель на текущий байт
uint64_t bitbuf = 0; // последние считанные нами 64 бита
int bitpos = 0; // сколько мы потребили из этих бит void refill3_msb() { assert(bitpos <= 64); // Перемещаем указатель на количество полностью потреблённых бит bitptr += bitpos >> 3; // Пополнение (Refill) bitbuf = read64BE(bitptr); // Количество битов в текущем байте, которое мы уже потребили // (мы уже позаботились о полных байтах; здесь остатки битов, // которые не составляют полный байт.) bitpos &= 7;
} uint64_t peekbits3_msb(int count) { assert(bitpos + count <= 64); assert(count >= 1 && count <= 64 - 7); // Избавляемся сдвигом от уже потреблённых битов uint64_t remaining = bitbuf << bitpos; // Возвращаем верхние "count" бит return remaining >> (64 - count);
} void consume3_msb(int count) { bitpos += count;
}

На этот раз мы также отбросили getbits, построенный из вызовов refill / peek / consume, потому что это ещё один паттерн, который уже должен быть вам понятен.

Когда мы разбили логику извлечения битов на отдельные части «refill» и «peek»/«consume», то стало ясно, насколько малы и понятны эти отдельные куски. Это довольно приятный вариант. Метод ожидает, что невыровненные 64-битные считывания big-endian существуют и достаточно малозатратны (это не проблема для распространённых архитектур x86 и ARM). Кроме того, полностью отсутствует ветвление! рассуждения в разделе о «lookahead». Кроме того, для реалистичной реализации необходимо добавить обработку случаев конца буфера; см.

Вариант 4: другой тип lookahead

Теперь давайте реализуем ещё один вариант lookahead без ветвления. Насколько я знаю, этот вариант тоже был открыт с помощью RAD моим коллегой Чарльзом Блумом и мной при работе над Kraken (ОБНОВЛЕНИЕ: как указал в комментариях Yann, основная идея была использована в Xpack Эрика Биггерса ещё задолго до выпуска Kraken. Мне не было это известно, думаю, что и Чарльзу тоже, но это значит, что эта идея точно не пришла нам первым в голову. Однако у нашего варианта есть интересная особенность — подробности см. в моём ответе). Хотя все битовые считыватели без ветвления (в них нет ветвления, если мы игнорируем проверку конца буфера в refill и тому подобное), но этот вариант обладает некоторыми интересными свойствами (часть из них я обсужу позже, потому что пока нам не хватает нужных знаний), которые в таком сочетании я больше нигде не встречал; если кто-то другой опередил нас, то сообщите мне об этом в комментариях, и я обязательно упомяну авторов! Итак, здесь мы снова возвращаемся к LSB-first, потому что я пытаюсь показать вам, насколько взаимозаменяемы LSB-first/MSB-first на этом уровне, невзирая на все холивары.

const uint8_t *bitptr; // Указатель на следующий байт для вставки в buf
uint64_t bitbuf = 0; // значение битов в буфере
int bitcount = 0; // количество битов в буфере void refill4_lsb() { // Получаем следующие несколько байтов и вставляем их прямо над // текущим верхним уровнем. bitbuf |= read64LE(bitptr) << bitcount; // Перемещаем указатель считывания для следующей итерации bitptr += (63 - bitcount) >> 3; // Обновляем количество доступных битов bitcount |= 56; // now bitcount is in [56,63] } uint64_t peekbits4_lsb(int count) { assert(count >= 0 && count <= 56); assert(count <= bitcount); return bitbuf & ((1ull << count) - 1);
} void consume4_lsb(int count) { assert(count <= bitcount); bitbuf >>= count; bitcount -= count;
}

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

Считывание 64 бит little-endian и их сдвиг для соответствия верхней части нашего текущего битового буфера вам должны быть уже понятны. Причиной является этап refill, работа которого слегка отличается от виденной нами ранее. Но манипуляции с bitptr / bitcount требуют объяснений.

В вариантах, которые мы видели раньше, после refill в буфере обычно оказывалось от 57 до 64 бит. Проще начать с bitcount. Но почему? Однако эта версия нацелена на то, чтобы хранить в буфере от 56 до 63 бит (именно поэтому ограничение счётчика снизилось на единицу). И если мы выполняем refill, нацеливаясь на [56,63] бит в буфере, то можем вычислить обновлённое количество битов единственной двоичной операцией OR. Вставка целого числа байтов означает, что во время refill bitcount будет увеличен на какую-то величину, кратную 8; это значит, что bitcount & 7 (нижние 3 бита) не изменятся.

Давайте просто посмотрим на значения в исходном bitcount: Что приводит меня к следующему вопросу: на сколько байт нужно сдвигать указатель?

  • Если 56 ≤ bitcount ≤ 63, мы уже находимся в нашем целевом интервале и нам не нужно перемещаться на следующий байт.
  • Если 48 ≤ bitcount ≤ 55, то мы прибавляем ровно 1 байт (и должны переместить bit_ptr на ту же величину).
  • Если 40 ≤ bitcount ≤ 47, то мы прибавляем ровно 2 байта.

и так далее. Это работает с (63 - bitcount) >> 3 байтами, которые мы прибавляем к bitptr.

Однако когда такое случается, мы каждый раз применяем OR к одному и тому же значению, поэтому это не меняет результат. Для битов в bitbuf над bitcount операция OR может быть выполнена несколько раз. Следовательно, когда они в дальнейшем движутся ниже (из-за сдвига вправо в функции consume), с ними бывает всё в порядке; нам не нужно беспокоиться о возможности появления мусора.

Когда его стоит использовать вместо, допустим, описанного выше варианта 3? Ну ладно, это конечно интересно, но что особенного в этом варианте?

На самом деле, следующий адрес загрузки становится известен сразу же после завершения предыдущей refill. Есть одна простая причина: в этом варианте адрес, по которому выполняет загрузку refill, не имеет зависимости от текущего значения bitcount. Среди операций с целыми числами, даже при попадании в кэш L1, операции загрузки отличаются высокими задержками (обычно около 3-5 циклов, в то время как большинство целочисленных операций занимает единственный цикл), а точное значение bitcount в конце итерации какого-нибудь цикла часто становится известным слишком поздно (см. Это небольшое отличие оказывается довольно большим преимуществом для процессоров с внеочередным выполнением. простой код для переменной длины, который я показал выше).

Единственным параметром, зависящим от предыдущего значения bitcount, является сдвиг, то есть обычная операция АЛУ, в общем случае занимающая один цикл. Если адрес загрузки не зависит bitcount, то это значит, что потенциально команда загрузки может быть отправлена сразу же после завершения предыдущей refill; тогда у нас останется достаточно времени для завершения загрузки с возможной перестановкой байтов значения, если порядок следования байтов в load не соответствует целевой ISA (допустим, если мы используем битовый буфер MSB-first на little-endian ЦП).

Когда я тестировал её в 2016 году в последней на то время версии декодера Kraken-Хаффмана, на настольных ПК повышение скорости составляло около 10% (по сравнению с предыдущей refill без ветвления, которая показана выше). Если вкратце подвести итог, то эта довольно запутанная версия refill выглядит странно, но обеспечивает гибкое повышение параллелизма на уровне инструкций.


Оставить комментарий

Ваш email нигде не будет показан
Обязательные для заполнения поля помечены *

*

x

Ещё Hi-Tech Интересное!

Конференция «Контентинг» — теперь с поддержкой hyper-threading

Друзья, на связи контент-студия Хабра. 29 ноября мы проводим собственную конференцию про контент и авторов. Будем учить, вдохновлять и рассказывать, как лучше, — в два синхронных потока докладов и дискуссий. Спикеры — эксперты в области контент-маркетинга, которые годами нарабатывали и тестировали ...

J2CL — Лучше поздно, чем никогда

Ещё никому не удалось опоздать на свои похороны.Валентин Домиль Идея трансляции Java в JavaScript далеко не нова, и все уже давно набили шишек с Google Web Toolkit, однако этот продукт сообщество ждало как ни один другой — о нем говорили ...