CODEWITHSUNDEEP
c++decodegifcompression
Mathias Hölzl
Mathias Hölzl

Reputation: 263

GIF LZW decompression

I am trying to implement a simple Gif-Reader in c++.

I currently stuck with decompressing the Imagedata. If an image includes a Clear Code my decompression algorithm fails.

After the Clear Code I rebuild the CodeTable reset the CodeSize to MinimumLzwCodeSize + 1.
Then I read the next code and add it to the indexstream. The problem is that after clearing, the next codes include values greater than the size of the current codetable.
For example the sample file from wikipedia: rotating-earth.gif has a code value of 262 but the GlobalColorTable is only 256.

How do I handle this?
I implemented the lzw decompression according to gif spec..

here is the main code part of decompressing:

int prevCode = GetCode(ptr, offset, codeSize);
codeStream.push_back(prevCode);

while (true)
{
auto code = GetCode(ptr, offset, codeSize);

//
//Clear code
//
if (code == IndexClearCode)
{
    //reset codesize
    codeSize = blockA.LZWMinimumCodeSize + 1;
    currentNodeValue = pow(2, codeSize) - 1;

    //reset codeTable
    codeTable.resize(colorTable.size() + 2);

    //read next code
    prevCode = GetCode(ptr, offset, codeSize);
    codeStream.push_back(prevCode);

    continue;
}
else if (code == IndexEndOfInformationCode)
    break;


//exists in dictionary
if (codeTable.size() > code)
{
    if (prevCode >= codeTable.size())
    {
        prevCode = code;
        continue;
    }

    for (auto c : codeTable[code])
        codeStream.push_back(c);

    newEntry = codeTable[prevCode];
    newEntry.push_back(codeTable[code][0]);

    codeTable.push_back(newEntry);

    prevCode = code;

    if (codeTable.size() - 1 == currentNodeValue)
    {
        codeSize++;
        currentNodeValue = pow(2, codeSize) - 1;
    }
}
else
{
    if (prevCode >= codeTable.size())
    {
        prevCode = code;
        continue;
    }

    newEntry = codeTable[prevCode];
    newEntry.push_back(codeTable[prevCode][0]);

    for (auto c : newEntry)
        codeStream.push_back(c);

    codeTable.push_back(newEntry);

    prevCode = codeTable.size() - 1;

    if (codeTable.size() - 1 == currentNodeValue)
    {
        codeSize++;
        currentNodeValue = pow(2, codeSize) - 1;
    }
}
}

Upvotes: 2

Views: 1493

Answers (1)

Mathias Hölzl
Mathias Hölzl

Reputation: 263

Found the solution. It is called Deferred clear code.
So when I check if the codeSize needs to be incremented I also need to check if the codeSize is already max(12), as it is possible to to get codes that are of the maximum Code Size.
See spec-gif89a.txt.

if (codeTable.size() - 1 == currentNodeValue && codeSize < 12)
{
   codeSize++;
   currentNodeValue = (1 << codeSize) - 1;
}

Upvotes: 4

Related Questions