Anonymous user
Talk:LZW compression: Difference between revisions
→C example problem
Line 63:
:'''WARNING: This code appears to have come from a GIF codec that has been modified to meet the requirements of this page, provided that the decoder works with the encoder to produce correct output. For writing GIF files the write_bits subroutine is wrong for Little Endian systems (it may be wrong for Big Endian as well.) The encoder also increases the number of bits in the variable length GIF-LZW after the N-2 code, whereas this must be done after N-1 to produce a working GIF file (just looking at the encoder, it's easy to see how this mistake could be made.)''' --[[User:Mick P.|Mick P.]] ([[User talk:Mick P.|talk]]) 03:17, 21 October 2015 (UTC)
*I was told by a person monitoring the GIF page on Wikipedia that the C code here looks like it may have came from a PDF reader, which they say is similar to GIF but different in subtle ways. In any case, I rewrote the C example for a GIF flavored codec, which does LZW packed to the GIF specification, combined, like the C code. Technically the packing is not LZW, so it may not even be appropriate. The following code could be used to make the C example more readable, although it switches to C++. Unfortunately I do not have a matching decoder to offer. It's also written to be ultra-compact, which may not be helpful, in addition to be slightly unorthodox.
<lang cpp>
//GIF flavored LZW based on:
//rosettacode.org/wiki/LZW_compression#C
//encode_t dictionary[4096];
struct encode_t{ short next[256]; };
static std::vector<encode_t> dictionary;
static std::vector<char> encoded;
template<class T> size_t encode(T in)
{
//2-color must use 2
const int colorbits = 8;
enum{cc=2<<(colorbits-1),eoi,c0};
auto &out = encoded; out.clear();
int next_code = c0;
int next_shift = 2<<colorbits;
dictionary.resize(next_shift);
int len = in.size();
int o = 0, o_bits = 0;
int c_bits = colorbits+1;
unsigned c,nc, code = cc; do
{
c = *in; ++in; //c holds a byte
if(!(nc=dictionary[code].next[c])) cc:
{
o|=code<<o_bits;
for(o_bits+=c_bits;o_bits>=8;o>>=8)
{
o_bits-=8; out.push_back(o&0xFF);
}
if(next_code>=next_shift)
{
if(++c_bits>12) //12 is GIF's limit
{
c_bits = 12; //13? spec is unclear
next_code = c0;
next_shift = 2<<colorbits;
dictionary.clear();
dictionary.resize(next_shift);
code = cc; goto cc;
}
else dictionary.resize(next_shift*=2);
}
if(code!=cc)
nc = dictionary[code].next[c] = next_code++;
else if(c_bits>=12) c_bits = 9;
code = c;
}
else code = nc;
}while(--len>0); switch(len)
{
case 0: goto cc; //truncate
case -1: code = eoi; goto cc;
case -2: c_bits = 8; if(o_bits) goto cc;
}
dictionary.clear();
return out.size();
}
</lang>
--[[User:Mick P.|Mick P.]] ([[User talk:Mick P.|talk]]) 11:08, 27 October 2015 (UTC)
| |||