myDC.ru

Здравствуйте, гость ( Вход | Регистрация )

 
 
Ответить в данную темуНачать новую тему

> base32 Encoder, костыль алгоритма

Теги
Нет тегов для показа
Setuper
сообщение 16.2.2012, 22:53
Сообщение #1


RusHub team lead
**************

Группа: Модераторы
Сообщений: 4 030
Регистрация: 20.6.2008
Из: г. Королёв (Моск. обл.)
Пользователь №: 46
Спасибо сказали: 1706 раз




Итак, найден очень неприятный костыль, который тянется из оригинального DC++ клиента, и который перенесён в производные от него клиенты, а также в ADC хабы, которые используют base32 для CID.

Косяк заключается в неправильно алгоритме преобразования из и в base32.

Берется некий ADC CID: "ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ".
Он состоит из 39 символов.
Преобразовываем этот CID по алгоритму DC++ из base32 (размер dst равен 24):
Код
Encoder::fromBase32(src, dst, sizeof(dst))

а потом опять в base32:
Код
Encoder::toBase32(dst, sizeof(dst), newSrc)

По идее должны получить тот же CID, однако получаем следующее: "ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZY"

Почему это возникает?
В base32 кодировке каждый символ имеет всего 32 комбинации, поэтому может занимать 5 бит, вместо 8. Отлично! Умножаем 39 на 5 и делим на 8, получаем 24,375. Однако размер dst равен 24, то есть мы теряем хвост данных.

Дальше ещё интереснее. Если мы возьмём размер dst с запасом - 25, вместо 24, то хвост мы не потеряем, однако на стадии преобразования в base32 мы получим лишние данные, ибо по алгоритму преобразования 0 в пяти битах преобразуется в символ base32 'A'.

Однако, алгоритм может срабатывать правильно. Это возникает тогда, когда хвост не имеет значимой величины (биты хвоста все равны 0). Хвост равен 3 бита. Получаем, что для того чтобы срабатывал алгоритм нужно чтобы последний символ был равен A (00000), I (01000), Q (10000) или Y (11000), в противном случае получаем значимые биты в хвосте, и обратное преобразование ломается.


Спасибо сказали:
Go to the top of the page
+Quote Post
Delia
сообщение 17.2.2012, 13:20
Сообщение #2


Продвинутый участник
****

Группа: Пользователи
Сообщений: 133
Регистрация: 12.5.2010
Пользователь №: 6 838
Спасибо сказали: 24 раза




Цитата
найден очень неприятный костыль

Баян. С этим потерянным байтом очень много срача в своё время было, я думал, передерутся.
Тем не менее даже связанные с этим ошибки проявляться на ADC хабах перестали.
Go to the top of the page
+Quote Post

Ответить в данную темуНачать новую тему
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 



RSS Сейчас: 26.5.2018, 13:04