Re: реализация алгоритма deflate на маленьком объеме ОЗУ
От: Sergei I. Gorelkin Россия  
Дата: 02.06.10 09:18
Оценка: 3 (1)
Здравствуйте, Аноним, Вы писали:

А>Добрый день!


А>Встречались ли кому-нибудь реализации deflate на маленьком объеме ОЗУ, для микроконтроллеров? zlib для этого слишком тяжеловесна. В стандартной конфигурации она требует памяти больше чем имеется физически (всего есть 32 кб, но даже все их использовать нельзя). Можно покрутить размеры окна zlib в сторону уменьшения, но может есть что-то более легковесное для таких случаев?


Посмотри в сторону LZO (lzop).
Re[3]: реализация алгоритма deflate на маленьком объеме ОЗУ
От: Viper_Craft  
Дата: 14.06.10 20:50
Оценка: 1 (1)
Здравствуйте, Аноним, Вы писали:

А>Указатели у меня 32-битные. Итого, те же самые 64 кб. Многовато (уложиться бы максимум в 10 кб). И плюс лицензия GPL у нее.


не понятна такая экономия с 32-битными указателями...
за килобайты сражаться надо, если указатели 16-битные, а вообще, что это за контроллер, у которого нет лишних 64 кбайт озу, но при этом указатели 32-битные?
реализация алгоритма deflate на маленьком объеме ОЗУ
От: Аноним  
Дата: 31.05.10 07:29
Оценка:
Добрый день!

Встречались ли кому-нибудь реализации deflate на маленьком объеме ОЗУ, для микроконтроллеров? zlib для этого слишком тяжеловесна. В стандартной конфигурации она требует памяти больше чем имеется физически (всего есть 32 кб, но даже все их использовать нельзя). Можно покрутить размеры окна zlib в сторону уменьшения, но может есть что-то более легковесное для таких случаев?
Re: реализация алгоритма deflate на маленьком объеме ОЗУ
От: quodum  
Дата: 01.06.10 15:51
Оценка:
Здравствуйте, Аноним, Вы писали:

А>Добрый день!


А>Встречались ли кому-нибудь реализации deflate на маленьком объеме ОЗУ, для микроконтроллеров? zlib для этого слишком тяжеловесна. В стандартной конфигурации она требует памяти больше чем имеется физически (всего есть 32 кб, но даже все их использовать нельзя). Можно покрутить размеры окна zlib в сторону уменьшения, но может есть что-то более легковесное для таких случаев?


А нужно обязательно deflate?

Вот, например, LZRW1 от Росса Вильямса.

Функция сжатия (на чистейшем 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 на маленьком объеме ОЗУ
От: quodum  
Дата: 02.06.10 09:01
Оценка:
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. Про ее потребление памяти ничего не написано. Смотрю исходники.

#define lzo_bytep               unsigned char __LZO_MMODEL *

#ifndef lzo_sizeof_dict_t
#  define lzo_sizeof_dict_t     ((unsigned)sizeof(lzo_bytep))
#endif

#define LZO1X_MEM_COMPRESS      LZO1X_1_MEM_COMPRESS
#define LZO1X_1_MEM_COMPRESS    ((lzo_uint32) (16384L * lzo_sizeof_dict_t))
#define LZO1X_MEM_DECOMPRESS    (0)


Указатели у меня 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 кб приемлемо. Так понимаю, править для смещений там только вот эти строчки?

UBYTE *hash[4096],*p_control; UWORD control=0,control_bits=0;

p=hash[index]; hash[index]=s=p_src; offset=s-p;


А вы не проводили эксперименты, какой результат дает этот алгоритм на маленьких данных? С какого количества начинается выигрыш, примерно? Данные — бинарные (не изображение).
Re[3]: реализация алгоритма deflate на маленьком объеме ОЗУ
От: Sergei I. Gorelkin Россия  
Дата: 02.06.10 13:20
Оценка:
Здравствуйте, Аноним, Вы писали:

А>Указатели у меня 32-битные. Итого, те же самые 64 кб. Многовато (уложиться бы максимум в 10 кб). И плюс лицензия GPL у нее.


Вот тут написано, что размер буфера 8 или 64 кБайт в зависимости от уровня сжатия.
Но раз не подходит — значит не судьба
Re[4]: реализация алгоритма deflate на маленьком объеме ОЗУ
От: quodum  
Дата: 02.06.10 17:20
Оценка:
Здравствуйте, Аноним, Вы писали:

А>8 кб приемлемо. Так понимаю, править для смещений там только вот эти строчки?


А>
А>UBYTE *hash[4096],*p_control; UWORD control=0,control_bits=0;

А>p=hash[index]; hash[index]=s=p_src; offset=s-p;
А>


По идее, да. Только ещё потребуется доп. проверка на "rollover", если размер сжимаемых данных может превышать 64КБ.
Её можно сделать косвенным образом, в ветке записи обратной ссылки, после len=s-p_src-1: если len == 0 (т.е. ничего не совпало), goto literal (только аккуратно проверить, чтобы все указатели в итоге получали правильные значения). Кстати, такая-же проверка покатит и при хранении в hash[] 12-битных смещений (чтобы ужать его до 6КБ), не нужно на каждом цикле чистить hash, как я написал ранее.

А>А вы не проводили эксперименты, какой результат дает этот алгоритм на маленьких данных? С какого количества начинается выигрыш, примерно? Данные — бинарные (не изображение).


25 одинаковых байтов сжимает в 15. Более короткие последовательности раздувает на +4 байта. Тут, кстати, можно 4 байта выгадать. Автор использует 4-байтовый FLAG_COMPRESS только в целях выравнивания (о чём написано в комментариях к следующей версии алгоритма, LZRW1-A). Заменить его на однобайтовый тривиально. А для сжатых последовательностей можно его вообще не писать, воспользовавшись тем, что в начале сжатого потока обязательно будет литерал, а не обратная ссылка, и первый бит первого контрольного слова обязательно будет сброшен.
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.