al_zatv (![[info]](http://l-stat.livejournal.com/img/userinfo.gif){kind=small} al_zatv) wrote,@ 2009-06-05 12:16:00 |
|
забавная задачка для программистов.
1. Все знают что такое RLE-сжатие.
Если кто не, это сжатие путём замены повторяющихся символов на их количество. Например, самый редко используемый символ будет маркером. Где видим кучу одинаковых байт - заменяем на три байта: маркер, символ, кол-во повторов.
2. Все знают что такое мало памяти.
Ну вот у меня RLE-сжатие и мало памяти. Мне хочется, чтобы и сжатие, и распаковка происходили в одном и том же буфере. Размер буфера - тютелька в тютельку чтобы вместить распакованные данные (это картинка, кстати: buf=malloc(width*height*bytes_per_pixel)
Надо: сделать такое RLE, чтобы и сжимало, и разжимало - в один и тот же буфер, и не более того.
Я придумал алгоритм, требующий отдельного хранения двух чисел: count после сжатия, и seed. Фактически, они в буфер не влезают:)
void myRLE_Encode(IN void *buffer, IN int size, OUT int *packed_size, OUT int *seed);
void myRLE_Decode(IN void *buffer, IN int packed_size, IN int seed);
Можно ли обойтись одним числом? Можно ли вообще без чисел?
Эффективность сжатия можно чуточку ухудшить,если надо.
1. Все знают что такое RLE-сжатие.
Если кто не, это сжатие путём замены повторяющихся символов на их количество. Например, самый редко используемый символ будет маркером. Где видим кучу одинаковых байт - заменяем на три байта: маркер, символ, кол-во повторов.
2. Все знают что такое мало памяти.
Ну вот у меня RLE-сжатие и мало памяти. Мне хочется, чтобы и сжатие, и распаковка происходили в одном и том же буфере. Размер буфера - тютелька в тютельку чтобы вместить распакованные данные (это картинка, кстати: buf=malloc(width*height*bytes_per_pixel)
Надо: сделать такое RLE, чтобы и сжимало, и разжимало - в один и тот же буфер, и не более того.
Я придумал алгоритм, требующий отдельного хранения двух чисел: count после сжатия, и seed. Фактически, они в буфер не влезают:)
void myRLE_Encode(IN void *buffer, IN int size, OUT int *packed_size, OUT int *seed);
void myRLE_Decode(IN void *buffer, IN int packed_size, IN int seed);
Можно ли обойтись одним числом? Можно ли вообще без чисел?
Эффективность сжатия можно чуточку ухудшить,если надо.
