gif/lzw algorithms and code

[88888 Dihedral]

BGBæ–¼ 2012å¹´8月22日星期三UTC+8上åˆ9時01分49秒寫é“：

I've been looking for algorithms/code to render gif's

from in-memory pixel rasters, and gif/rbtree from

http://www.malcolmmclean.site11.com/www/datadensity/

seems among the best. Anybody used that, have comments

or alternative/better recommendations?

My interest mostly stems from forkosh.com/lineart.html whose

C source currently uses http://shh.thathost.com/pub-unix/#gifsave

and then system()'s imagemagick convert for animations.

But I now need to render animated gif's internally, and

modify somebody's gif code for that purpose (or develop it from

scratch). The better functional decomposition of gif/rbtree

seems to make that easier for me than gifsave.

But I noticed some occasionally-nasty comments about that on

http://bytes.com/topic/c/answers/682627-malcolms-new-book

while googling (some of them by frequent posters in this ng.

Does gif/rbtree work pretty robustly (that "looking-for-comma"

at the start of loadgif() seems a little risky, though I haven't

read the gif specification carefully yet, and wouldn't need that

half of the code, anyway)?

While testing savegif() myself, just using the embedded test

driver, I did find a trivial bug which always replaces the

savegif(loadgif(argv[1])) with an empty image. Just a "return"

at the end of if(argc==2){...}, or a guard for the empty-image

savegif() with else{...} or if(argc!=2){...} is needed.

But then my own tests worked fine, except that it occasionally

gets the background color wrong. But I haven't looked into that yet,

or even studied the code carefully. Before I start, any other

recommendations for this kind of little project? Thanks,

I think the LZW patents of Unysis and the arithmetic coding patents

of IBM are all expired long time ago.

the LZW patent expired in 2006 IIRC.



I think many other forms of arithmetic coding are also in the clear as

well. the main downside of AC though is that it generally isn't as fast

as Huffman, so it is more a small gain in compression for a loss in speed..



although, it isn't that bad, for example, the H.264 / MPEG-4 AVC codec

successfully uses arithmetic coding.

Those are not too difficult to implement in C for a lossless

data compression in 199X.

I got paid well for those trivial easy jobs from my old image processing

library with those technitians who can't even write a 64 bit by 64 bit

integer multiplication in the 80386 instructin set.

It's kind of slow and boring except the pay in the small scale casino park.

Google and Facebook proved that the US Hi-tech casinos are much more

well paid for the funders.

still annoyingly hard to get paid as a programmer though.

"the money" is always far away and one lives life generally being

regarded as useless by any potential employers.



this is partly why I am looking into trying to develop and market

something myself...

It is easy to implement the LZW codec in C.

The problem is just equivalent to a hash table implementation in C.

 

[BGB]

BGBæ–¼ 2012å¹´8月22日星期三UTC+8上åˆ9時01分49秒寫é“：

I've been looking for algorithms/code to render gif's
from in-memory pixel rasters, and gif/rbtree from

http://www.malcolmmclean.site11.com/www/datadensity/

seems among the best. Anybody used that, have comments
or alternative/better recommendations?
My interest mostly stems from forkosh.com/lineart.html whose
C source currently uses http://shh.thathost.com/pub-unix/#gifsave
and then system()'s imagemagick convert for animations.
But I now need to render animated gif's internally, and
modify somebody's gif code for that purpose (or develop it from
scratch). The better functional decomposition of gif/rbtree
seems to make that easier for me than gifsave.
But I noticed some occasionally-nasty comments about that on

http://bytes.com/topic/c/answers/682627-malcolms-new-book

while googling (some of them by frequent posters in this ng.
Does gif/rbtree work pretty robustly (that "looking-for-comma"
at the start of loadgif() seems a little risky, though I haven't
read the gif specification carefully yet, and wouldn't need that
half of the code, anyway)?
While testing savegif() myself, just using the embedded test
driver, I did find a trivial bug which always replaces the
savegif(loadgif(argv[1])) with an empty image. Just a "return"
at the end of if(argc==2){...}, or a guard for the empty-image
savegif() with else{...} or if(argc!=2){...} is needed.
But then my own tests worked fine, except that it occasionally
gets the background color wrong. But I haven't looked into that yet,
or even studied the code carefully. Before I start, any other
recommendations for this kind of little project? Thanks,

--

John Forkosh ( mailto: (e-mail address removed) where j=john and f=forkosh )
I think the LZW patents of Unysis and the arithmetic coding patents

of IBM are all expired long time ago.

the LZW patent expired in 2006 IIRC.



I think many other forms of arithmetic coding are also in the clear as

well. the main downside of AC though is that it generally isn't as fast

as Huffman, so it is more a small gain in compression for a loss in speed.



although, it isn't that bad, for example, the H.264 / MPEG-4 AVC codec

successfully uses arithmetic coding.

Those are not too difficult to implement in C for a lossless

data compression in 199X.

I got paid well for those trivial easy jobs from my old image processing

library with those technitians who can't even write a 64 bit by 64 bit

integer multiplication in the 80386 instructin set.

It's kind of slow and boring except the pay in the small scale casino park.

Google and Facebook proved that the US Hi-tech casinos are much more

well paid for the funders.

still annoyingly hard to get paid as a programmer though.

"the money" is always far away and one lives life generally being

regarded as useless by any potential employers.



this is partly why I am looking into trying to develop and market

something myself...

It is easy to implement the LZW codec in C.

The problem is just equivalent to a hash table implementation in C.

actually, what I am trying to figure out how to develop to marketable
levels is not (just) some compression code, but rather a game project.

I have actually implemented LZW before, just in my tests it didn't
really compare favorably to LZ77 variants on my test data (didn't
compress as well and was slower), so most of my own similar compression
stuff has been based either on LZ77 or LZ+Markov-Chains.

many of my specialized structured-data compressors though have been
MRU-based, so are "sort of" like LZW (datums which are frequently used
move to the front of the list, and others slide backwards and are
eventually discarded).


there are a few videos of my game project I put up on here:
http://www.youtube.com/user/BGBTech?feature=guide

but it is still in development, and is still a bit far from being
marketable.


it does include a video codec though, built on an augmented version of
MJPEG. the main issue is how much I can do with it while still retaining
some semblance of backwards compatibility (with normal JPEG and MJPEG).

for example, I could bolt-on block-based motion-compensation (like in
MPEG/...), but a generic decoder would see garbage (only the I-frames
would come out looking "sane"). likewise, using a more compact encoding
for the Huffman tables would break compatibility.

crossing that line would leave me with "just another obscure video
codec" (even if one partially backwards compatible with MJPEG).


there are plenty of other things in a project this size though, and it
is actually partly an effort of trying to keep things moderately focused
and avoiding spreading my efforts too thinly.


or such...

 

[88888 Dihedral]

BGBæ–¼ 2012å¹´8月23日星期四UTC+8上åˆ2時03分23秒寫é“：

BGBæ–¼ 2012å¹´8月22日星期三UTC+8上åˆ9時01分49秒寫é“：

On 8/21/2012 2:16 PM, 88888 Dihedral wrote:

On Thursday, August 16, 2012 1:51:01 PM UTC+8, JohnF wrote:

I've been looking for algorithms/code to render gif's



from in-memory pixel rasters, and gif/rbtree from



http://www.malcolmmclean.site11.com/www/datadensity/



seems among the best. Anybody used that, have comments



or alternative/better recommendations?



My interest mostly stems from forkosh.com/lineart.html whose



C source currently uses http://shh.thathost.com/pub-unix/#gifsave



and then system()'s imagemagick convert for animations.



But I now need to render animated gif's internally, and



modify somebody's gif code for that purpose (or develop it from



scratch). The better functional decomposition of gif/rbtree



seems to make that easier for me than gifsave.



But I noticed some occasionally-nasty comments about that on



http://bytes.com/topic/c/answers/682627-malcolms-new-book



while googling (some of them by frequent posters in this ng.



Does gif/rbtree work pretty robustly (that "looking-for-comma"



at the start of loadgif() seems a little risky, though I haven't



read the gif specification carefully yet, and wouldn't need that



half of the code, anyway)?



While testing savegif() myself, just using the embedded test



driver, I did find a trivial bug which always replaces the



savegif(loadgif(argv[1])) with an empty image. Just a "return"



at the end of if(argc==2){...}, or a guard for the empty-image



savegif() with else{...} or if(argc!=2){...} is needed.



But then my own tests worked fine, except that it occasionally



gets the background color wrong. But I haven't looked into that yet,



or even studied the code carefully. Before I start, any other



recommendations for this kind of little project? Thanks,



--



John Forkosh ( mailto: (e-mail address removed) where j=john and f=forkosh )



I think the LZW patents of Unysis and the arithmetic coding patents

of IBM are all expired long time ago.





the LZW patent expired in 2006 IIRC.



I think many other forms of arithmetic coding are also in the clear as

well. the main downside of AC though is that it generally isn't as fast

as Huffman, so it is more a small gain in compression for a loss in speed.



although, it isn't that bad, for example, the H.264 / MPEG-4 AVC codec

successfully uses arithmetic coding.





Those are not too difficult to implement in C for a lossless

data compression in 199X.



I got paid well for those trivial easy jobs from my old image processing

library with those technitians who can't even write a 64 bit by 64 bit

integer multiplication in the 80386 instructin set.



It's kind of slow and boring except the pay in the small scale casinopark.



Google and Facebook proved that the US Hi-tech casinos are much more

well paid for the funders.







still annoyingly hard to get paid as a programmer though.

"the money" is always far away and one lives life generally being

regarded as useless by any potential employers.



this is partly why I am looking into trying to develop and market

something myself...

It is easy to implement the LZW codec in C.
The problem is just equivalent to a hash table implementation in C.

actually, what I am trying to figure out how to develop to marketable

levels is not (just) some compression code, but rather a game project.



I have actually implemented LZW before, just in my tests it didn't

really compare favorably to LZ77 variants on my test data (didn't

compress as well and was slower), so most of my own similar compression

stuff has been based either on LZ77 or LZ+Markov-Chains.



many of my specialized structured-data compressors though have been

MRU-based, so are "sort of" like LZW (datums which are frequently used

move to the front of the list, and others slide backwards and are

eventually discarded).





there are a few videos of my game project I put up on here:

http://www.youtube.com/user/BGBTech?feature=guide



but it is still in development, and is still a bit far from being

marketable.





it does include a video codec though, built on an augmented version of

MJPEG. the main issue is how much I can do with it while still retaining

some semblance of backwards compatibility (with normal JPEG and MJPEG).



for example, I could bolt-on block-based motion-compensation (like in

MPEG/...), but a generic decoder would see garbage (only the I-frames

would come out looking "sane"). likewise, using a more compact encoding

for the Huffman tables would break compatibility.



crossing that line would leave me with "just another obscure video

codec" (even if one partially backwards compatible with MJPEG).





there are plenty of other things in a project this size though, and it

is actually partly an effort of trying to keep things moderately focused

and avoiding spreading my efforts too thinly.

It is the

or such...

It is the trade off between the data compression ration to save the memory
and the computing powers required to RW the data.

The higher computing power should lead to a better data compression ratio
in an implementation of SW for the markete.

The arithmetic coding part is as difficult as computing
arithmetic operations of millions of bits by register machines with a finite
register width and the finite buffer I/O capabilities avaible for results
to be saved or retrived in the codec.

It is jsut slightly more difficult than the Fibanaci sesries compution
for Fib ( N >1 million).

 

[BartC]

Maybe explicitly organize the book in three Parts, with
a separate intro at the front of each Part. For example, that
"Maths Functions" (where'd you British pick up that trailing
"s" from?)

It's a contraction of 'Mathematics'. Just like 'Statistics' might be
shortened to 'Stats'; or do you say 'Stat'?

 

[JohnF]

It's a contraction of 'Mathematics'. Just like 'Statistics' might be
shortened to 'Stats'; or do you say 'Stat'?

Thanks for the infos. Regarding MM's "grab-bag" remark, again,
take a look at,
Algorithms and Theory of Computation Handbook,
Mikhail J. Atallah, Editor,
CRC Press, 1999, ISBN 0-8493-2649-4.
That's a real grab-bag, with 48 chapters covering everything from
VLSI Layout, chap 23, to Computational Geometry, chaps 19 and 20, to
Simulated Annealing, chap 37, to Compression, chap 12, which includes
an lzw discussion and pseudocode. And it's apparently been pretty
successfully published, though pitched at a somewhat higher level,
and not C-specific, if those distinctions make any difference.
But you might want to take a look, and see if its layout and treatment
suggest anything you might want to incorporate in a 2nd ed.