base32 Encoder, костыль алгоритма |
Здравствуйте, гость ( Вход | Регистрация )
base32 Encoder, костыль алгоритма |
16.2.2012, 22:53
Сообщение
#1
|
|
RusHub team lead Группа: Модераторы Сообщений: 4 030 Регистрация: 20.6.2008 Из: г. Королёв (Моск. обл.) Пользователь №: 46 Спасибо сказали: 1708 раз |
Итак, найден очень неприятный костыль, который тянется из оригинального 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), в противном случае получаем значимые биты в хвосте, и обратное преобразование ломается. |
|
|
17.2.2012, 13:20
Сообщение
#2
|
|
Продвинутый участник Группа: Пользователи Сообщений: 133 Регистрация: 12.5.2010 Пользователь №: 6 838 Спасибо сказали: 24 раза |
Цитата найден очень неприятный костыль Баян. С этим потерянным байтом очень много срача в своё время было, я думал, передерутся. Тем не менее даже связанные с этим ошибки проявляться на ADC хабах перестали. |
|
|
|
Сейчас: 26.11.2024, 20:56 |