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