Есть такая задачка: в пространстве символов


закодировать строку (массив) из такого пространства символов



я знаю как решается эта задача (наитупейший маппинг в цикле), если мы сделаем такое допущение: на один символ из пространства-отправителя приходится два символа из пространства получателя, например ё == cb, ж == cf и т.д.

В этом случае outBuf.strlen() = initBuf.strlen() * 2

у нас целевое пространство 26 символов
исходное пространство 26 * 2 + 33 * 2 + 10 + 34 = 162 символа
парные комбинации из 26^2 = 676 / 162 = 4
значит существует возможность обеспечить

outBuf.strlen() = initBuf.strlen() * ( 1 + 1 / 4 )

- - - - - - -

Задача в следующем: произвести битовую упаковку, но только так, чтобы результат состоял только из символов пространства получателя, т.е. из а-z

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

Если можно подскажите как происходит запись и чтение
я видел конструкции типа currentCharacter << 6 но у меня реально крышняк сносит чтобы не наделать ошибок, когда битовые комплекты одного символа голова в одном символе, а хвост в другом
Ладно ещё когда можно использовать все битовое пространство, но в этой задаче можно использовать только битовое пространство соответствующее символам a-z (десятичные ascii коды 141 - 172, битовое с 01100001 - 01111001)

и ещё забыл одно условие назвать: алгоритму должно быть пофиг в какой кодировке поставляется буфер с символами отправителями

ИзопропилLumixалгоритму должно быть пофиг в какой кодировке поставляется буфер с символами отправителями
как это пофиг?

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

Dimitry SibiryakovБери входной буфер как очень длинное целое число и переводи его в
двадцатишестиричную систему как и любое другое число - делением с остатком.

Мозгов не хватает перевести эту рекомендацию в код. Может кто-нибудь поможет?

Dimitry SibiryakovДелить-то ты,
надеюсь, умеешь?..


Вот эту операцию знаю, если речь о ней.

ИзопропилLumixМы исходим из того, что нашему коду уже поставляется готовый символ.
это значит перекодирование из исходной в свою (0.. 161) уже произведено. не говори "пофиг"

Да, все верно: можно считать, что стоит задача упаковать последовательность чисел из диапазона 0 - 161




Вот по такой схеме




При этом упаковка происходит в бинарную форму, а не в символьную.

Рабочая гипотеза решения такая:
1) бинарное пространство дает чанки степени двойки, т.е. "вагончиками" могут быть только 1, 11, 111, 1111, 11111, ... т.е. "корзины" емкостью 2, 4, 8, 16, 32, 64, 128, 256, ...
2) если у нас 161 символ, то минимальный вагончик для нашей задачи 256 == 8 бит
3) количество символов получателей 26, значит для них минимальный вагончик 32 == 5 бит




4) пространство, в которое мы хотим складывать это диапазон ascii адресов 97 - 122, но этот диапазон может быть представлен как 97 + (0 - 25)

на этих тезисах получается такой алгоритм
1) конвертим строку в собственную 8-битную кодировку, где занятыми будут первые 162 символа
2) в новом цикле берем каждый символ (число) и конвертим его в бинарную форму и складываем в бинарный буфер (битовый массив)
3) в новом цикле считаываем из полученного бинарного буфера чанки по 5 бит, конвертим в десятичное число, прибавляем к этому числу 97, конвертим в символ ascii и складываем в строковый буфер

раскодировка
1) в цикле читаем из буфера символ, конвертим его десятичное число, вычитаем 97, конвертим в 5 битный бинарник и складываем в бинарный буфер
2) в новом цикле читаем чанки по 8 бит, конвертим в десятичное число, преобразуем из своей 8 битовой кодировки в исходную строковую кодировку и складываем в строковый буфер

Вопросы:
1) насколько это алгоритм взрослый?
2) как такое мутится средствами плюсов? где тут используется операция деления с остатком?

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

Эта задача не про архивацию, а про упаковку без архивации. Это задача про конвертацию.

MasterZiv


Я эти операции знаю, но мне не хватает мозгов как ими читать и писать чанки




Битовый массив как я понял из примера выше задается вот так




Буква z из нашей кастомной кодировки 0-161, которую мы ввели специально для целей данной темы соответствует десятичному коду 25, что в 8 битах означает 00011001

Вопрос первый как имея на руках десятичное число 25 записать в bitbuf скажем в 315 позицию (битовый адрес которой 315 * 8 = 2520)

В принципе ответ очевиден




Но при этом мы не использовали битовую адресацию. А как можно выполнить ту же самую операцию, но использовать именно битовую запись, указав при этом длину чанка 8 бит?




- - - - - - -

Теперь имея в битбуфе чанки по 8 бит, наша задача в цикле брать порциями по 5 бит, добавлять к ним 97 и складывать полученное число в строковый буфер, рассчитывая при этом получать только ascii буквы a-z




Как эта функция на плюсах выполняется? Тоже каким-то хитрым битовым шифтом?

- - - - - - -

Ещё возникает вопрос, поскольку сумма 8 битовых чанков не равняется сумме 5 битовых чанков (ну разве что при Summ = 40 как минимальный общий знаменатель), то возникает вопрос, как в цикле читая 5 битовые чанки мы сможем определить окончание и что нам делать в этом случае? Просто доращивать битбуф нулями, чтобы он делился на 5 без остатка?

- - - - - - - - -

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

ИзопропилLumix,

Посмотри как устроена кодировка Base64

http://base64.sourceforge.net/b64.c

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