Въпросът е малко странен и не знам защо го задавам тук, но все пак - има ли някой, който да е запознат ама добре запознат с DEFLATE алгоритъма за компресия (използван от gzip и zip)?!? Имам предвид някой, който е имал достатъчно много вземане-даване с това, примерно писал си е собствена inflate функция. Иначе що е то Хъфманово дърво и що е то LZ77 и аз знам и такива отговори за жалост няма да ми помогнат особено.
Това което на мен ми трябва е някакъв относително бърз начин да знам още от първите няколко байта от блока дали това е валиден блок или не. Първите няколко байта съдържат хедъра, както и описание на distance/code length големините.
Причината да питам за това е идиотска. Тръгнах да троша ZIP файлове върху видеокарти. ZIP encryption-а условно казано има два варианта - един стар encryption алгоритъм, който е слаб, както и новия strong encryption алгоритъм, който ползва PBKDF2 подсилване на ключа и AES криптиране на данните.
Колкото и да е странно, strong encryption-а не е проблема - проблемът е стария им стандарт.
Ще се опитам да обясня - при стария стандарт има прост начин по който паролата се превръща в ключ. С този ключ се декриптират 12 байта от zip архива и се получава една стойност, наречена verifier. Въпросната стойност е само един байт и се сравнява с някаква стойност от ZIP хедъра - ако не съвпаднат, имаме грешна парола. Както сте се досетили, всяка грешна парола-кандидат има шанс 1/256 да мине тази проверка - откъдето следва декриптиране и декомпресиране и ако няма грешка при декомпресирането и сравняването на крайната CRC стойност, значи имаме успешно позната парола.
Последните два процеса са безумна цел за реализация върху видеокарти - просто няма как да се извърши по-бързо, отколкото върху процесора - има прекалено големи изисквания към паметта, а видеопроцесорите за разлика от CPU-тата нямат такива прекрасни L1/L2 кешове от под няколко мегабайта. Не мога да декомпресирам целия файл и не мога да му смятам CRC сума върху видеокартата, поне не мога да го правя бързо.
Обаче съм сигурен че има начин ако декриптирам само първите няколко байта от компресирания stream, да разбера дали това е валиден DEFLATE блок или не. Засега имам една доста генерична проверка върху GPU-тата във първия байт от декриптирания stream, която проверява типа на кодирането и ако не ползваме динамични Huffman codes, връщаме грешка - това е ефективно защото на практика всеки ZIP софтуер (WinZIP, 7z, WinRAR) ползват въпросния метод. Това вдига ситото от 1/256 на 1/1024. Но не е достатъчно. Върху видеокарта среден клас правя около 2 милиона опита в секунда, за момента процесорът ми се справя по-добре, което е странно. Също така има разни комерсиални решения със затворен код, които се хвалят с над 200-300 милиона опита/секунда върху относително калпава NVidia карта и стигам до извода че те парсват и обработват DEFLATE данните в GPU кода по някакъв начин и отсяват по-добре нещата.
Та мисълта ми е - има ли някакъв начин сравнително лесно и бързо ако имам само първите няколко байта от DEFLATE stream-а да кажа: това е валиден такъв или невалиден. Истински вярвам, че има и ако си загубя няколко седмици в четене вероятно ще го открия. Ако все пак някой има идея, ще се радвам да помогне
Автор
Тема: Някой случайно да разбира от DEFLATE компресията? (Прочетена 2556 пъти)