битовый поток что это
Битовый поток
Битовые потоки широко используются в телекоммуникациях и компьютерных технологиях. Например, технология транспортных телекоммуникационных сетей SDH и коммуникационный протокол TCP представлены битовыми потоками.
Когда битовый поток захватывается и сохраняется на носителе информации, то создаётся компьютерный файл.
Термин «битовый поток» часто используется для описания конфигурационных данных, которые загружаются в программируемую пользователем вентильную матрицу (FPGA). Это использование, возможно, возникло на основе общих методов конфигурирования FPGA через последовательный битовый поток, как правило, с последовательного PROM или чипа флеш-памяти. Вместе с тем многие FPGA также поддерживают метод загрузки данных через параллельный байтовый поток. Подробный формат битового потока для конкретного чипа FPGA, как правило, считается собственностью поставщика этого FPGA.
В математике несколько определённых бесконечных последовательностей битов были изучены для определения их математических свойств. Сюда входят en:Baum–Sweet sequence, en:Ehrenfeucht–Mycielski sequence, en:Fibonacci word, en:Kolakoski sequence, en:Regular paperfolding sequence, последовательность Рудина-Шапиро, последовательность Морса-Туэ.
Аналогично к битовому потоку, байтовый поток — это последовательность как правило 8-битных байтов. Байтовый поток и может рассматриваться как частный случай битового потока.
Ссылки
Полезное
Смотреть что такое «Битовый поток» в других словарях:
битовый поток — двоичный поток цифровой поток — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Тематики информационные технологии в целом Синонимы двоичный потокцифровой поток EN bit stream … Справочник технического переводчика
Поток данных — У этого термина существуют и другие значения, см. Поток. Не следует путать с Многопоточность. Поток данных (англ. stream) в программировании абстракция, используемая для чтения или записи файлов, сокетов и т. п. в единой… … Википедия
Цифровое видео — Цифровое видео множество технологий записи, обработки, передачи, хранения и воспроизведения визуального или аудиовизуального материала в цифровом представлении. Основное отличие от аналогового видео в том, что видеосигналы кодируются и… … Википедия
Flash Video — В данной статье или разделе имеется список источников или внешних ссылок, но источники отдельных утверждений остаются неясными из за отсутствия сносок … Википедия
MJPEG — (Motion JPEG) покадровый метод видеосжатия, основной особенностью которого является сжатие каждого отдельного кадра видеопотока с помощью алгоритма сжатия изображений JPEG. При сжатии методом MJPG межкадровая разница не учитывается.… … Википедия
Передача данных — Сеть передачи данных Передача данных (обмен данными, цифровая передача, цифровая связь) физический перенос … Википедия
BitTorrent — Эта статья о протоколе. Статья о клиенте: BitTorrent (программа). BitTórrent (букв. англ. «битовый поток») пиринговый (P2P) сетевой протокол для кооперативного обмена файлами через Интернет. Файлы передаются частями, каждый torrent… … Википедия
Сетевая плата — (ISA) с разъёмами AUI (сверху) и … Википедия
LM-хеш — или LAN Manager хеш один из форматов используемых Microsoft LAN Manager и версиями Microsoft Windows до Windows Vista для хранения пользовательских паролей меньше 15 символов длиной. Это единственный вид шифрования используемый в Microsoft LAN… … Википедия
Source Input Format — (SIF) определенный в стандарте MPEG 1 формат хранения и передачи цифрового видео. 625/50 Формат SIF в PAL/SECAM имеет разрешение 352(или 360) x 288 пикселей при частоте 25 кадров в секунду. 525/59.94 Формат SIF в NTSC имеет разрешение 352(или… … Википедия
Битстрим: что это такое и как это работает в домашнем кинотеатре
Bitstream Audio – важнейший элемент домашнего кинотеатра – выясните, почему
Мы принимаем легкость, с которой мы слушаем аудио как должное, но передача музыки, диалогов и звуковых эффектов от источника к вашим ушам требует почти волшебных технологий.
Одна технология, используемая для доставки звука, называется Битовый поток (он же Битовый поток аудио, Битовый поток, Цифровой битовый поток или Аудио битовый поток).
Определен битовый поток
Битовый поток – это двоичные биты информации (1 и 0), которые могут передаваться с одного устройства на другое. Битовые потоки используются в ПК, сетях и аудио приложениях.
Что касается аудио, битовый поток может использоваться для преобразования звука в цифровые биты, а затем эта информация передается с устройства-источника на приемник и, в конце концов, на ваши уши.
PCM и Hi-Res audio являются примерами цифровых аудиоформатов, использующих битовые потоки.
Как битстрим используется в домашнем кинотеатре
В домашнем кинотеатре поток битов более узко определен как метод передачи кодированных аудиосигналов определенных форматов объемного звука от источника на совместимый приемник домашнего кинотеатра или комбинацию предусилителя AV/процессора/усилителя мощности.
Приемник домашнего кинотеатра или AV-процессор обнаруживает отправленный ему кодированный формат объемного звучания. Приемник/AV-процессор продолжает декодировать информацию на основе инструкций, предоставленных в сигнале битового потока. Может быть добавлена постобработка, и сигнал преобразуется в аналоговую форму, чтобы его можно было усилить и отправить на динамики, чтобы вы могли слышать его.
Процесс потока битов начинается с того, что создатель контента и/или звукорежиссер/микшер решают, какой формат объемного звука использовать для конкретной аудиозаписи или прямой трансляции, а затем приступают к кодированию звука в виде цифровых битов в формате, выбранном в соответствии с правилами формат.
По завершении этого процесса биты помещаются на диск (DVD, Blu-ray, Ultra HD Blu-ray), кабельный или спутниковый сервис, потоковый источник или встраиваются в прямую телевизионную передачу.
Примеры форматов объемного звука, которые используют процесс передачи битового потока, включают Dolby Digital, EX, Plus, TrueHD, Atmos, DTS, DTS-ES, DTS 96/24, DTS HD-Master Audio и DTS: X.
Поток битов может быть отправлен из выбранного источника непосредственно на приемник для домашнего кинотеатра (или предусилитель/процессор AV) через физическое соединение (цифровое оптическое, цифровое коаксиальное или HDMI). Битовый поток также может быть отправлен по беспроводной связи через антенну или домашнюю сеть.
Примеры управления битовым потоком
Вот примеры того, как передача битового аудио может работать в домашнем кинотеатре:
Кодирование битового потока является основной технологией, которая используется в домашнем кинотеатре. Он обеспечивает способ передачи информации объемного звука, насыщенного данными, между устройством-источником и ресивером домашнего кинотеатра или предусилителем/процессором AV в узкой полосе пропускания, используя различные варианты подключения.
Куча различных способов считывания битов
Возобновляя старую традицию своего блога, я возьму простую задачу, рассмотрю чрезмерно длинный список её альтернативных решений и оценю их достоинства.
Наша простая задача будет заключаться в следующем: мы хотим считывать из байтового потока данные, значения закодированные переменным количеством бит. Считывание отдельных байтов, машинных слов и т.д. непосредственно поддерживается большинством процессоров и многими языками программирования, но при вводе-выводе с переменной битовой длиной обычно необходимо реализовывать решение самостоятельно.
Это звучит достаточно просто, и в каком-то смысле так и есть. Первый источник проблем заключается в том, что эта операция будет активно использовать кодеки — и да, она будет ограничена вычислениями, а не памятью и вводом-выводом. Поэтому нам нужна не просто рабочая, но и эффективная реализация. И по дороге мы столкнёмся со множеством других сложностей: взаимодействия с буферизацией ввода-вывода, обработка конца буфера, тупиковые ситуации в битовых сдвигах, определённых в C/C++ и в разных архитектурах процессоров, а также другие особенности битовых сдвигов.
В этом посте в основном сосредоточусь на множестве различных способов реализации считывателя; по сути, все рассмотренные здесь техники аналогично применимы и к записывающей части, но я не хочу удваивать количество вариаций алгоритмов. Их и так будет достаточно.
Степени свободы
«Считать переменное количество битов» — это недостаточное описание задачи. Существует множество приемлемых способов упаковки битов в байты, и у всех них есть свои сильные и слабые места, о которых я расскажу позже. Пока же давайте просто остановимся на их различиях.
Для начала нам нужно сделать первый важный выбор — поля будут упаковываться в виде «первым идёт MSB» или «первым идёт LSB» («most significant bit» — наиболее значимый бит и «least significant bit» — наименее значимый бит). То есть если мы вызовем реализуемую функцию getbits и выполним следующий код
для только что открытого битового потока, то мы ожидаем, что оба значения будут получены от одного и того же байта, но как они упорядочены в этом байте? Если упакованы в виде 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-first существует собственное естественное правило. Оно заключается во вставке нового значения бит за битом, начиная с LSB и вверх, и если мы так сделаем, то в результате получим следующий битовый поток:
Естественная упаковка LSB-first даёт нам те же байты, что и упаковка LSB-first в большой integer с сохранением его в порядке байтов little-endian. Кроме того, у нас на рисунке возникает очевидная неуклюжесть: логически сопряжённая упаковка поля «c» в несколько байтов выглядит на таком рисунке прерывистой, в то время как рисунок упаковки MSB-first выглядит так, как мы того и ожидаем. Но и в нём возникает проблема: в рисунке MSB-first мы нумеруем биты в увеличивающемся справа налево порядке (стандартном), а байты — в увеличивающемся слева направо порядке (что тоже является стандартным).
Вот, что происходи со схемой битов LSB-first, если мы нарисуем бит 0 (LSB) в каждом байте слева, а бит 7 (MSB) — справа:
Если нарисовать так, то схема будет выглядеть ожидаемым нами способом. Расположение MSB справа кажется странным, если думать о байте как о числе, но гораздо менее странным оказывается, если думать о нём как о массиве из 8 бит (как мы, по сути, и работаем с ним при выполнении побитового ввода-вывода).
По совпадению, в некоторых big-endian-архитектурах (например, в IBM POWER) биты нумеруются следующим образом — бит 0 — это MSB, бит 31 (или 63) — LSB. Создав схему упаковки битов MSB-first на такой машине с битом 0=MSB, и нумеруя наши собственные битовые поля таким образом, чтобы их бит 0 соответствовал MSB, мы получим точно такую же схему (но это будет означать, что что-то немного отличается). Этот стандарт делает порядок битов и байтов согласующимся (что хорошо), но разрушает удобный стандарт соответствия бита k значению 2 k (что не совсем хорошо).
И если мысль о перенумерации битов таким образом, чтобы бит 0 являлся MSB, взрывает вам мозг, то можно оставить нумерацию битов неизменной, но стать бунтарём и рисовать адреса байтов увеличивающимся слева. Или же увеличивать адреса вправо, но стать немного другим бунтарём и записывать байтовый поток в обратном порядке. Если выбрать один из этих вариантов, то мы получим следующую схему:
Я понимаю, что это уже начинает запутывать, и на этом остановлюсь, но здесь нужно сказать о важном: не стоит слишком привязываться к способу получения байтов. Легко обмануться, решив, что один вариант лучше другого просто потому, что он выглядит лучше, но стандарты получения байтов слева направо и битов внутри них справа налево совершенно произвольны, поэтому какой бы вы ни выбрали, у вас в результате всё равно получится что-то странное.
Получается у каждого из стандартов упаковки MSB-first и LSB-first есть свои достоинства и недостатки, и гораздо полезнее будет думать о них как об инструментах с разными областями применения, а не назначать один из них «правильным», а другие «ошибочными». Что касается порядка байтов и необходимости упаковки значений в байты, слова или что-то более крупное, то я крайне рекомендую вам использовать наиболее естественный порядок для вашего стандарта упаковки битов: MSB-first естественным образом соответствует порядку байтов в стиле big-endian, а LSB-first естественно соответствует порядку байтов little-endian. Если только вы не записываете байтовые потоки в обратном порядке (верите или нет, но есть логичные причины поступать и так); в этом случае у нас получается MSB-first в обратном порядке, соответствующий little-endian, и LSB-first в обратном порядке, соответствующий big-endian.
Причина выбора «естественных» порядков заключается в том, что они дают нам в разных реализациях бОльшую свободу. Поток с естественным порядком позволяет использовать множество различных декодеров (и кодеров), у каждого из которых есть свои компромиссы (и свои преимущества в разных случаях). «Неестественные» порядки обычно применяются с одной конкретной реализацией и при декодировании любым другим способом оказываются очень неудобными.
Наш первый getbits (извлечение битов)
Теперь, когда мы в достаточном объёме описали задачу, можем реализовать решение. Особо простая версия возможна, если предположить, что весь битовый поток расположен в памяти последовательно (как массив байтов), и пока полностью игнорировать неприятные проблемы наподобие попадания в конец массива. Давайте просто притворимся, что он бесконечен! (Или достаточно огромен, или имеет по краям заполнение нулями.)
В этом случае мы можем основать реализацию на чисто функциональной функции «извлечения битов», в которой я проиллюстрирую возникающие проблемы и всевозможные функции считывания битов. Давайте начнём с упаковки битов LSB-first:
Мы просто воспользовались тем упомянутым выше фактом, что битовый поток LSB-first — это просто большое число little-endian. Сначала мы получаем 64 смежных, упорядоченных в байты битов, начиная с первого байта, содержащего любые из интересующих нас битов, совершаем сдвиг вправо, чтобы избавиться от оставшихся лишних 0-7 битов ниже первого нужного нам бита, а затем возвращаем результат, маской приведённый к нужной ширине.
Соответствующий вариант для MSB-first получается довольно похожим образом, за исключением одной раздражающей проблемы, о которой я расскажу после демонстрации кода:
Этот код работает аналогично предыдущему: считываем 64 смежных, упорядоченных в байты бита (на этот раз big-endian), выполняем сдвиг влево, чтобы выровнять верх нужного нам битового поля с MSB bits (в то время как раньше мы делали сдвиг вправо, чтобы выровнять низ нашего битового поля с LSB bits ), а затем делаем сдвиг вправо, чтобы расположить верхние width битов внизу для их возврата, потому что при вызове getbits(3) мы обычно ожидаем увидеть значение от 0 до 7.
Граничные случаи сдвигов
В некоторых случаях C/C++ оставляет детали неопределёнными для обратной совместимости с машинами, поэтому никто сейчас об этом не беспокоится. Известный пример: отсутствие требования того, чтобы представление знаковых чисел использовало дополнительный код; хотя архитектуры без дополнительного кода существуют, все они сегодня сохранились лишь в музеях.
К сожалению, у нас не один из таких случаев. Вот, что происходит на разных широко распространённых архитектурах CPU, когда величина сдвига находится вне пределов интервала:
Следовательно, даже если всё, что делает компилятор с этим сдвигом вправо — это отдаёт соответствующую инструкцию сдвига вправо для целевой архитектуры (а обычно так и происходит), то мы будем видеть на разных архитектурах разное поведение. На ARM A64 и x86-64 результат сдвига на 64 по сути будет no-op, а getbits(0) поэтому будет (обычно) возвращать ненулевое значение, хотя следует ожидать, что возвращаться должен ноль.
Почему же это так важно? Разумеется, жёстко прописанный в коде getbits(0) не является интересным случаем применения; однако иногда нам необходимо выполнить getbits(x) для какой-то переменной x, где x в некоторых случаях может быть нулём. В этом случае было бы здорово, чтобы код просто работал и не требовал каких-то проверок особых случаев.
Если вы хотите, чтобы этот случай работал, то одним из вариантов будет явная проверка на width == 0 и обработка этого особым образом; другим вариантом будет использование выражения без ветвления, работающего с нулевыми ширинами, например, этого кода, применяемого в FSE Йенна Коллета:
Этот конкретный случай проще обрабатывать для битовых потоков LSB-first. И поскольку я упомянул их, давайте поговорим об операции использования маски, которую я применил для изолирования нижних width битов:
Существует аналогичная форма, которая немного менее затратна в архитектурах с трёхоперандной инструкцией and-with-complement (AND-NOT). К ним относятся многие процессоры RISC CPU, а также x86s с BMI1. А именно, мы можем взять маску всех битов-единиц, выполнить сдвиг влево, чтобы добавить внизу width нулей, а затем дополнить всё:
Подготовка таблицы поиска, хранящей результат двух целочисленных операций, может показаться смешным действием, особенно потому что вычисление адреса загружаемого элемента таблицы обычно включает в себя и сдвиг, и сложение — ровно те же самые операции, которые мы бы выполняли, если бы у нас не было таблицы! — но в этом безумии есть свой метод: вычисление требуемого адреса может выполняться как часть доступа к памяти в одной инструкции загрузки, например, на машинах с x86 и ARM, поэтому эти сдвиг и сложение вычисляются в блоке генерации адреса (Address Generation Unit, AGU) как часть конвейера загрузки в ЦП, а не с инструкциями целочисленной арифметики и сдвига. То есть подобное контринтуитивное решение заменить две целочисленные инструкции ALU одной инструкцией загрузки целого числа может привести к значительному ускорению кода с активным битовым вводом-выводом, потому что оно лучше уравновешивает нагрузку между разными операционными блоками.
Ещё одно интересное свойство заключается в том, что версия LSB-first, использующая таблицу поиска масок, выполняет один сдвиг на переменную величину (чтобы сдвинуть уже считанные биты). Это важно, потому что по множеству (часто банальных!) причин во многих микроархитектурах сдвиги целых чисел на переменные величины более затратны, чем сдвиги на постоянные величины времени компилирования. Например, Cell PPU/Xbox 360 Xenon были печально известны тем, что имели сдвиги на переменное расстояние, тормозившие ядро процессора на ужасно долгое время — 12 циклов, а обычные сдвиги были встроены в конвейер и выполнялись за два цикла. На многих микроархитектурах Intel x86 «традиционные» переменные сдвиги x86 ( SHR reg, cl и подобные им) в три раза затратнее, чем сдвиги на константу времени компилирования.
Кажется, что это ещё одна причина отказа от варианта MSB-first: рассмотренные выше варианты выполняют два или три сдвига на операцию извлечения битов, два из которых имеют переменное расстояние. Но существует трюк, благодаря которому можно вернуться к операции с одиночным сдвигом, а именно использование вместо обычного сдвига циклического:
Здесь поворот влево (вы должны сами выяснить, как наилучшим образом использовать его в вашем компиляторе C) сначала выполняет работу исходного сдвига влево, а затем выполняет поворот на дополнительные «width» бит, чтобы заставить битовое поле перевернуться от наиболее значимых битов значения к наименее значимым, после чего к ним можно применить маску так же, как и в варианте LSB-first.
А, да, и я начал писать деление на 8 как сдвиг право на 3, и mod-8 нашей беззнаковой позиции как двоичное AND с 7. Это эквивалентные замены, и вы можете увидеть такие формы в настоящем коде, поэтому я решил их сюда добавить.
С помощью такой операции маски поворотом мы (в RAD Game Tools) выполняли считывание битов в Cell PPU и Xbox 360, только потому, что на этом ядре сдвиги с переменным расстоянием были так ужасны. Стоит заметить, что у этой версии тоже нет проблем с width == 0 ; единственная проблема — это зависимость от инструкций поворота, которые существуют (и быстро выполняются) в большинстве архитектур, но обычно к ним неудобно получать доступ из кода на C.
Мы уже обсудили множество различных способов выполнения битового сдвига и маскирования, и в дальнейшем я буду ссылаться на них. Но я ещё не показал вам никакой практической логики битового ввода-вывода: форма извлечения битов — это хорошая стартовая точка, удобная для объяснения концепций, не задумываясь о состоянии, но в реальном коде вы скорее всего не будете использовать её, не в последнюю очередь потому, что она предполагает, что весь битовый поток находится в памяти и его можно легко считать до конца буфера в обычном процессе выполнения!
Итак, мы определились с основной задачей и рассмотрели различные способы выполнения сдвига и использования масок, обнаружив свойственные им сложности. Выбранная мной форма «извлечения битов» основана на примитиве без состояния, с которого удобно было начинать, потому что в нём не использовались инварианты цикла.
Сейчас мы перейдём к стилю с состоянием, который используется в большинстве считывателей битов, которые вы встретите (потому что он оказывается наименее затратным). Также мы перейдём от монолитной функции getbits к чему-то более разбитому на части. Но давайте начнём с начала.
Вариант 1: считывание ввода по одному байту за раз
Наш считыватель-«извлекатель» предполагал, что весь битовый поток заранее находится в памяти. Это не всегда возможно или желательно; давайте исследуем другой предельный случай, а именно считыватель битов, запрашивающий дополнительные биты по одному за раз и только тогда, когда они нужны.
В общем случае наши варианты с состоянием будут получать ввод по несколько байт за раз, и у них будут несколько частично обработанных байтов. Нам нужно хранить эти данные в переменной, которую мы назовём «битовым буфером»:
В процессе обработки ввода мы всегда будем записывать новые биты в этот буфер, когда он заканчивается, или при возможности считывать биты из этого буфера.
Как и раньше, мы можем избавиться от требования count ≥1, изменив способ получения битов результата, как объяснено в предыдущей части. Я упоминаю об этом в последний раз; просто учитывайте, что каждый раз, когда я буду показывать какой-нибудь вариант алгоритма, то к нему автоматически применяются предыдущие вариации.
Идея здесь довольно проста: сначала мы проверяем, достаточно ли в буфере битов для немедленного удовлетворения запроса. Если нет, то мы записываем дополнительные байты по одному за раз, пока у нас не будет их достаточно. Здесь подразумевается, что getbyte() в идеале будет использовать некий механизм буферизированного ввода-вывода, который просто сводится к разыменованию и инкременту указателя на критическом пути; если этого можно избежать, он не должен быть вызовом функции или чем-то затратным. Поскольку мы вставляем по 8 бит за раз, то за один вызов мы можем считать максимум 57 бит; это наибольшее количество битов, на которое мы можем пополнить буфер, не рискуя при этом ничего упустить.
После этого мы получаем верхние count битов из буфера, а затем смещаем их. Сохраняемый здесь инвариант заключается в том, что первый несчитанный бит хранится в MSB буфера.
Стоит также заметить, что этот процесс удобно разбивается на три отдельные операции меньшего объёма, которые я назову «пополнение» (refill), «просмотр» (peek) и «потребление» (consume). Фаза «пополнения» гарантирует, что в буфере будет присутствовать минимальное количество бит; «просмотр» возвращает несколько следующих битов в буфере, не отбрасывая их, а «потребление» удаляет биты, не глядя на них. Все они оказываются полезными по отдельности операциями; чтобы показать, как всё это организуется, я покажу эквивалент алгоритма LSB-first, разделённого на меньшие части:
Запись getbits в виде сочетания таких трёх меньших примитивов не всегда оптимальна. Например, если мы используем метод поворота для битовых буферов MSB-first, то хотим, чтобы поворот был разделён между фазами peekbits и consume ; оптимальная реализация разбивает работу на эти две фазы. Однако разбить код на эти отдельные этапы всё равно полезно, потому что когда вы освоите все эти три фазы как отдельные этапы, то сможете по-разному использовать их вместе.
Смотрим вперёд
Наиболее важная такая транформация — это амортизация пополнения для нескольких операций декодирования. Давайте начнём с простого игрушечного примера: допустим, мы хотим считать три битовых поля, которые мы брали раньше:
Когда getbits реализован так, как выше, этот код будет проверять пополнение (и возможно сам процесс пополнения) до трёх раз. Но это глупо; мы заранее знаем, что будем считывать 4+3+5=12 бит за один раз, поэтому можем получить их все одновременно:
Это простой код с переменной длиной, где значения с 0 по 27 передаются в 5 битах, а значения от 28 до 91 передаются в 9 битах. Смысл в том, что в этом случае мы не знаем заранее, сколько битов мы в дальнейшем потребим. Однако мы знаем, что их больше 9 битов, поэтому всё равно можем сделать так, чтобы пополнение происходило только один раз:
На самом деле, если хотите, можно пуститься во все тяжкие и ещё больше разбить операции, чтобы оба пути выполнения только один раз потребляли ( consume ) биты. Например, при использовании битового буфера MSB-first, мы можем написать этот маленький декодер так:
Подобная микронастройка сильно не рекомендуется за границами очень нагруженных циклов, но как я упоминал выше, некоторые из этих циклов декодера достаточно нагружены, и в этом случае экономия нескольких инструкций в разных местах выливается в серьёзный выигрыш. Особенно важная техника декодирования кодов с переменной длиной (например, кодов Хаффмана) заключается в заглядывании вперёд на определённое количество бит с дальнейшим поиском в таблице на основании результата. В элементе таблицы указано, каким должен быть декодированный символ и сколько символов нужно потребить (т.е. какое число просмотренных битов на самом деле принадлежит символу). Это значительно быстрее, чем считывать код по одному-два бита за раз с проверкой на каждом этапе по дереву Хаффмана (к сожалению, этот метод предлагается во многих учебниках и других вводных текстах.)
Однако здесь есть проблема. Техника заглядывания вперёд и принятия решений о том, сколько бит нужно потребить, достаточно мощна, но мы только что изменили правила: показанная выше реализация getbits стремится считывать лишние байты только при крайней необходимости. Но наш изменённый пример считывателя кода с переменной длиной всегда пополняется, поэтому буфер содержит не менее 9 бит, даже если в конце мы потребим всего 5 бит. В зависимости от того, где происходит пополнение, это может даже привести к считыванию после конца самого потока данных.
Так мы познакомились с методом lookahead. Изменённый считыватель кода начинает получать дополнительные входные данные ещё до того, как будет уверен в их необходимости. Такой подход имеет много плюсов, но компромисс заключается в том, что он может заставить нас выполнить считывание за пределами логического конца битового потока; это подразумевает, что нам обязательно нужно обеспечить правильную обработку такого случая. Да, он может никогда не привести к сбою или считыванию вне пределов потока; но кроме этого он подразумевает принцип работы слоя буферизации ввода или кадрирования.
Если мы хотим выполнять заглядывание вперёд, то нам нужен какой-то способ обработки этого. Основные варианты таковы:
Вариант 2: когда нам очень нужно считать 64 бита за раз
К счастью, если нам требуется полная ширина, существуют способы реализовать её (как и технике с поворотом и масками битовых буферов для MSB-first, я научился этому в RAD). Думаю, на этом этапе вы уже поняли соотношение между методами для MSB-first и LSB-first, поэтому я покажу решение только для одного варианта. Давайте выберем LSB-first:
Кроме большей ширины битовых полей, эта техника имеет ещё один плюс: заметьте, что она всегда за раз считывает полные 64-битовые uint. Показанный выше вариант 1 считывает байты за раз, но требует цикла пополнения; различные варианты без ветвления, которые мы рассмотрим ниже, неявно полагаются на поддержку целевым процессором быстрых невыровненных считываний. Это единственная из версий, выделяющаяся считыванием одного размера и постоянным выравниванием, что делает её более привлекательной для целевых систем, не поддерживающих быстрые невыровненные считывания, например, для множества старых процессоров RISC.
Как обычно, существует куча других вариаций, которые я не буду показывать. Например, если у нас есть данные, которые мы полностью декодируем в памяти, то нет причин возиться с булевым флагом have_lookahead ; можно просто хранить указатель на текущее слово lookahead, и увеличивать этот указатель при потреблении текущего lookahead.
Вариант 3: возврат к извлечению битов
Исходный считыватель битов с извлечением из предыдущей части был довольно затратным. Но если нас устраивает требование того, что весь входной поток одновременно находится в памяти, то мы можем обернуть его в паттерн refill/peek/consume, чтобы получить что-то полезное. У нас всё равно будет битовый считыватель, который заглядывает вперёд (а потому создаёт соответствующие сложности), но такова жизнь. Здесь мы для примера снова используем MSB:
Это довольно приятный вариант. Когда мы разбили логику извлечения битов на отдельные части «refill» и «peek»/«consume», то стало ясно, насколько малы и понятны эти отдельные куски. Кроме того, полностью отсутствует ветвление! Метод ожидает, что невыровненные 64-битные считывания big-endian существуют и достаточно малозатратны (это не проблема для распространённых архитектур x86 и ARM). Кроме того, для реалистичной реализации необходимо добавить обработку случаев конца буфера; см. рассуждения в разделе о «lookahead».
Вариант 4: другой тип lookahead
Теперь давайте реализуем ещё один вариант lookahead без ветвления. Насколько я знаю, этот вариант тоже был открыт с помощью RAD моим коллегой Чарльзом Блумом и мной при работе над Kraken (ОБНОВЛЕНИЕ: как указал в комментариях Yann, основная идея была использована в Xpack Эрика Биггерса ещё задолго до выпуска Kraken. Мне не было это известно, думаю, что и Чарльзу тоже, но это значит, что эта идея точно не пришла нам первым в голову. Однако у нашего варианта есть интересная особенность — подробности см. в моём ответе). Хотя все битовые считыватели без ветвления (в них нет ветвления, если мы игнорируем проверку конца буфера в refill и тому подобное), но этот вариант обладает некоторыми интересными свойствами (часть из них я обсужу позже, потому что пока нам не хватает нужных знаний), которые в таком сочетании я больше нигде не встречал; если кто-то другой опередил нас, то сообщите мне об этом в комментариях, и я обязательно упомяну авторов! Итак, здесь мы снова возвращаемся к LSB-first, потому что я пытаюсь показать вам, насколько взаимозаменяемы LSB-first/MSB-first на этом уровне, невзирая на все холивары.
Мы уже видели ранее этапы peek и consume, однако на этот раз максимально допустимая битовая ширина по какой-то причине уменьшилась на единицу и составляет 56 бита.
Причиной является этап refill, работа которого слегка отличается от виденной нами ранее. Считывание 64 бит little-endian и их сдвиг для соответствия верхней части нашего текущего битового буфера вам должны быть уже понятны. Но манипуляции с bitptr / bitcount требуют объяснений.
Что приводит меня к следующему вопросу: на сколько байт нужно сдвигать указатель? Давайте просто посмотрим на значения в исходном bitcount :
Для битов в bitbuf над bitcount операция OR может быть выполнена несколько раз. Однако когда такое случается, мы каждый раз применяем OR к одному и тому же значению, поэтому это не меняет результат. Следовательно, когда они в дальнейшем движутся ниже (из-за сдвига вправо в функции consume), с ними бывает всё в порядке; нам не нужно беспокоиться о возможности появления мусора.
Ну ладно, это конечно интересно, но что особенного в этом варианте? Когда его стоит использовать вместо, допустим, описанного выше варианта 3?
Если вкратце подвести итог, то эта довольно запутанная версия refill выглядит странно, но обеспечивает гибкое повышение параллелизма на уровне инструкций. Когда я тестировал её в 2016 году в последней на то время версии декодера Kraken-Хаффмана, на настольных ПК повышение скорости составляло около 10% (по сравнению с предыдущей refill без ветвления, которая показана выше).