Здравствуйте, Аноним, Вы писали:
А>Добрый день!
А>Встречались ли кому-нибудь реализации deflate на маленьком объеме ОЗУ, для микроконтроллеров? zlib для этого слишком тяжеловесна. В стандартной конфигурации она требует памяти больше чем имеется физически (всего есть 32 кб, но даже все их использовать нельзя). Можно покрутить размеры окна zlib в сторону уменьшения, но может есть что-то более легковесное для таких случаев?
Здравствуйте, Аноним, Вы писали:
А>Указатели у меня 32-битные. Итого, те же самые 64 кб. Многовато (уложиться бы максимум в 10 кб). И плюс лицензия GPL у нее.
не понятна такая экономия с 32-битными указателями...
за килобайты сражаться надо, если указатели 16-битные, а вообще, что это за контроллер, у которого нет лишних 64 кбайт озу, но при этом указатели 32-битные?
реализация алгоритма deflate на маленьком объеме ОЗУ
От:
Аноним
Дата:
31.05.10 07:29
Оценка:
Добрый день!
Встречались ли кому-нибудь реализации deflate на маленьком объеме ОЗУ, для микроконтроллеров? zlib для этого слишком тяжеловесна. В стандартной конфигурации она требует памяти больше чем имеется физически (всего есть 32 кб, но даже все их использовать нельзя). Можно покрутить размеры окна zlib в сторону уменьшения, но может есть что-то более легковесное для таких случаев?
Re: реализация алгоритма deflate на маленьком объеме ОЗУ
Здравствуйте, Аноним, Вы писали:
А>Добрый день!
А>Встречались ли кому-нибудь реализации deflate на маленьком объеме ОЗУ, для микроконтроллеров? zlib для этого слишком тяжеловесна. В стандартной конфигурации она требует памяти больше чем имеется физически (всего есть 32 кб, но даже все их использовать нельзя). Можно покрутить размеры окна zlib в сторону уменьшения, но может есть что-то более легковесное для таких случаев?
Функция сжатия (на чистейшем K&R Си ) влезает в экран и использует буфер в 4КБ. (Для реального использования её, правда, потребуется слегка подточить -- хотя-бы добавить проверку размера выходного буфера).
Каталог из 96 файлов суммарным объёмом 6+ МБ (исходники, объектники, exe-шники) пожала в 7.5 раз, усреднённый коэффициент сжатия на файл -- 3.9 раза.
Код в public domain, но, возможно, алгоритм закрыт чьим-то патентом. Оригинальные патенты на LZ77 вроде-бы протухли, но в патентах на компрессию чёрт ногу сломит, я так и не смог разобраться в текущей ситуации.
Re[2]: реализация алгоритма deflate на маленьком объеме ОЗУ
От:
Аноним
Дата:
02.06.10 08:30
Оценка:
Здравствуйте, quodum, Вы писали:
А>>Встречались ли кому-нибудь реализации deflate на маленьком объеме ОЗУ, для микроконтроллеров? zlib для этого слишком тяжеловесна. В стандартной конфигурации она требует памяти больше чем имеется физически (всего есть 32 кб, но даже все их использовать нельзя). Можно покрутить размеры окна zlib в сторону уменьшения, но может есть что-то более легковесное для таких случаев?
Q>А нужно обязательно deflate?
Q>Вот, например, LZRW1 от Росса Вильямса.
Q>Функция сжатия (на чистейшем K&R Си ) влезает в экран и использует буфер в 4КБ. (Для реального использования её, правда, потребуется слегка подточить -- хотя-бы добавить проверку размера выходного буфера).
Q>Каталог из 96 файлов суммарным объёмом 6+ МБ (исходники, объектники, exe-шники) пожала в 7.5 раз, усреднённый коэффициент сжатия на файл -- 3.9 раза.
Q>Код в public domain, но, возможно, алгоритм закрыт чьим-то патентом. Оригинальные патенты на LZ77 вроде-бы протухли, но в патентах на компрессию чёрт ногу сломит, я так и не смог разобраться в текущей ситуации.
Большое спасибо! Deflate совсем необязателен. Нужен просто какой-нибудь метод сжатия (получше RLE), который можно реализовать на таких небольших ресурсах памяти. Вашу ссылку посмотрю, еще раз спасибо. Если у кого будут другие варианты — рад услышать.
Re[2]: реализация алгоритма deflate на маленьком объеме ОЗУ
Q>Функция сжатия (на чистейшем K&R Си) влезает в экран и использует буфер в 4КБ.
Эх, наврал. Использует 16КБ на платформе с 32-битными указателями, или 8КБ -- на платформе с 16-битными.
Но если хранить в hash[] не указатели, а смещения, будет 8КБ на любой платформе (16 бит достаточно). А при необходимости можно сократить до 6КБ -- ценой некоторого замедления: на самом деле достаточно 12 бит на смещение, но тогда придётся на каждом цикле пробегаться по всему hash[]'у и вытаптывать уходящие "в прошлое" смещения.
Re[2]: реализация алгоритма deflate на маленьком объеме ОЗУ
От:
Аноним
Дата:
02.06.10 11:46
Оценка:
Здравствуйте, Sergei I. Gorelkin, Вы писали:
А>>Встречались ли кому-нибудь реализации deflate на маленьком объеме ОЗУ, для микроконтроллеров? zlib для этого слишком тяжеловесна. В стандартной конфигурации она требует памяти больше чем имеется физически (всего есть 32 кб, но даже все их использовать нельзя). Можно покрутить размеры окна zlib в сторону уменьшения, но может есть что-то более легковесное для таких случаев?
SIG>Посмотри в сторону LZO (lzop).
Смотрю версию LZO. Написано на страничке — Requires 64 kB of memory for compression.
Смотрю версию miniLZO. Про ее потребление памяти ничего не написано. Смотрю исходники.
Указатели у меня 32-битные. Итого, те же самые 64 кб. Многовато (уложиться бы максимум в 10 кб). И плюс лицензия GPL у нее.
Re[3]: реализация алгоритма deflate на маленьком объеме ОЗУ
От:
Аноним
Дата:
02.06.10 11:56
Оценка:
Здравствуйте, quodum, Вы писали:
Q>>Функция сжатия (на чистейшем K&R Си) влезает в экран и использует буфер в 4КБ.
Q>Эх, наврал. Использует 16КБ на платформе с 32-битными указателями, или 8КБ -- на платформе с 16-битными. Q>Но если хранить в hash[] не указатели, а смещения, будет 8КБ на любой платформе (16 бит достаточно). А при необходимости можно сократить до 6КБ -- ценой некоторого замедления: на самом деле достаточно 12 бит на смещение, но тогда придётся на каждом цикле пробегаться по всему hash[]'у и вытаптывать уходящие "в прошлое" смещения.
8 кб приемлемо. Так понимаю, править для смещений там только вот эти строчки?
А вы не проводили эксперименты, какой результат дает этот алгоритм на маленьких данных? С какого количества начинается выигрыш, примерно? Данные — бинарные (не изображение).
Re[3]: реализация алгоритма deflate на маленьком объеме ОЗУ
Здравствуйте, Аноним, Вы писали:
А>Указатели у меня 32-битные. Итого, те же самые 64 кб. Многовато (уложиться бы максимум в 10 кб). И плюс лицензия GPL у нее.
Вот тут написано, что размер буфера 8 или 64 кБайт в зависимости от уровня сжатия.
Но раз не подходит — значит не судьба
Re[4]: реализация алгоритма deflate на маленьком объеме ОЗУ
По идее, да. Только ещё потребуется доп. проверка на "rollover", если размер сжимаемых данных может превышать 64КБ.
Её можно сделать косвенным образом, в ветке записи обратной ссылки, после len=s-p_src-1: если len == 0 (т.е. ничего не совпало), goto literal (только аккуратно проверить, чтобы все указатели в итоге получали правильные значения). Кстати, такая-же проверка покатит и при хранении в hash[] 12-битных смещений (чтобы ужать его до 6КБ), не нужно на каждом цикле чистить hash, как я написал ранее.
А>А вы не проводили эксперименты, какой результат дает этот алгоритм на маленьких данных? С какого количества начинается выигрыш, примерно? Данные — бинарные (не изображение).
25 одинаковых байтов сжимает в 15. Более короткие последовательности раздувает на +4 байта. Тут, кстати, можно 4 байта выгадать. Автор использует 4-байтовый FLAG_COMPRESS только в целях выравнивания (о чём написано в комментариях к следующей версии алгоритма, LZRW1-A). Заменить его на однобайтовый тривиально. А для сжатых последовательностей можно его вообще не писать, воспользовавшись тем, что в начале сжатого потока обязательно будет литерал, а не обратная ссылка, и первый бит первого контрольного слова обязательно будет сброшен.