[Ffmpeg-devel] TIFF LZW decoder (was: [PATCH] change gif demuxer to gif decoder)

Kostya kostya.shishkov
Mon Oct 23 15:21:04 CEST 2006


On Mon, Oct 23, 2006 at 10:26:57AM +0300, Kostya wrote:
> 
[...]
> Different LZW implementations may differ by:
> a) initial code size
> b) output codeword size (may vary from smth to smth or be constant 12 bits)
> c) additional symbols for decoder reset and dictionary size expansion
> 
> As I implemented TIFF decoder for FFmpeg it'll be probably me who will
> add LZW support to TIFF. I'll look in libtiff sources for further details.

Reality is far more curly than expected:
a) there are two LZW variants - one is very similar (or identical) to GIF but
it is not used
b) TIFF LZW has MSB codeword order (i.e. next byte has lower 8 bits, not high)
c) Codeword size should be increased _before_ the current dictionary is full
d) Each line should end with end-of-image code and decoder needs to be reset
before decoding next line.

Also preliminary patch for LZW support in TIFF is provided. It has some bugs but
it should work more or less.
-------------- next part --------------
Index: libavcodec/tiff.c
===================================================================
--- libavcodec/tiff.c	(revision 6773)
+++ libavcodec/tiff.c	(working copy)
@@ -20,6 +20,7 @@
  *
  */
 #include "avcodec.h"
+#include "bytestream.h"
 #ifdef CONFIG_ZLIB
 #include <zlib.h>
 #endif
@@ -60,6 +61,34 @@
     TIFF_LONGLONG
 };
 
+/* LZW-specific data */
+#define MAXBITS                 12
+#define SIZTABLE                (1<<MAXBITS)
+
+typedef struct LZWState {
+    /* LZW compatible decoder */
+    uint8_t *bytestream;
+    int eob_reached;
+    uint8_t *pbuf, *ebuf;
+    int bbits;
+    unsigned int bbuf;
+
+    int cursize;                /* The current code size */
+    int curmask;
+    int codesize;
+    int clear_code;
+    int end_code;
+    int newcodes;               /* First available code */
+    int top_slot;               /* Highest code for current size */
+    int slot;                   /* Last read code */
+    int fc, oc;
+    uint8_t *sp;
+    uint8_t stack[SIZTABLE];
+    uint8_t suffix[SIZTABLE];
+    uint16_t prefix[SIZTABLE];
+    uint8_t buf[256];
+} LZWState;
+
 typedef struct TiffContext {
     AVCodecContext *avctx;
     AVFrame picture;
@@ -74,6 +103,9 @@
     uint8_t* stripdata;
     uint8_t* stripsizes;
     int stripsize, stripoff;
+
+    LZWState lzw;
+    int lzw_inited;
 } TiffContext;
 
 static int tget_short(uint8_t **p, int le){
@@ -97,6 +129,151 @@
     }
 }
 
+static const uint16_t mask[17] =
+{
+    0x0000, 0x0001, 0x0003, 0x0007,
+    0x000F, 0x001F, 0x003F, 0x007F,
+    0x00FF, 0x01FF, 0x03FF, 0x07FF,
+    0x0FFF, 0x1FFF, 0x3FFF, 0x7FFF, 0xFFFF
+};
+
+static void TLZWDecodeInit(LZWState * s, int csize)
+{
+    /* read buffer */
+    s->eob_reached = 0;
+    s->pbuf = s->buf;
+    s->ebuf = s->buf;
+    s->bbuf = 0;
+    s->bbits = 0;
+
+    /* decoder */
+    s->codesize = csize;
+    s->cursize = s->codesize + 1;
+    s->curmask = mask[s->cursize];
+    s->top_slot = 1 << s->cursize;
+    s->clear_code = 1 << s->codesize;
+    s->end_code = s->clear_code + 1;
+    s->slot = s->newcodes = s->clear_code + 2;
+    s->oc = s->fc = 0;
+    s->sp = s->stack;
+}
+
+static inline int GetCode(LZWState * s)
+{
+    int c, sizbuf;
+    uint8_t *ptr;
+
+    while (s->bbits < s->cursize) {
+        ptr = s->pbuf;
+        if (ptr >= s->ebuf) {
+            if (!s->eob_reached) {
+                sizbuf = 256;//bytestream_get_byte(&s->bytestream);
+                s->ebuf = s->buf + sizbuf;
+                s->pbuf = s->buf;
+                if (sizbuf > 0) {
+                    bytestream_get_buffer(&s->bytestream, s->buf, sizbuf);
+                } else {
+                    s->eob_reached = 1;
+                }
+            }
+            ptr = s->pbuf;
+        }
+        s->bbuf = (s->bbuf << 8) | ptr[0];
+        ptr++;
+        s->pbuf = ptr;
+        s->bbits += 8;
+    }
+    c = (s->bbuf >> (s->bbits - s->cursize))& s->curmask;
+    s->bbits -= s->cursize;
+    return c;
+}
+
+/* NOTE: the algorithm here is inspired from the LZW GIF decoder
+   written by Steven A. Bennett in 1987.
+   Slightly modified to handle TIFF LZW variant */
+/* return the number of byte decoded */
+static int TLZWDecode(LZWState * s, uint8_t * buf, int len)
+{
+    int l, c, code, oc, fc;
+    uint8_t *sp;
+
+    if (s->end_code < 0)
+        return 0;
+
+    l = len;
+    sp = s->sp;
+    oc = s->oc;
+    fc = s->fc;
+
+    while (sp > s->stack) {
+        *buf++ = *(--sp);
+        if ((--l) == 0)
+            goto the_end;
+    }
+
+    for (;;) {
+        c = GetCode(s);
+        if (c == s->end_code) {
+            /* reset before ending */
+            s->cursize = s->codesize + 1;
+            s->curmask = mask[s->cursize];
+            s->slot = s->newcodes;
+            s->top_slot = 1 << s->cursize;
+            break;
+        } else if (c == s->clear_code) {
+            s->cursize = s->codesize + 1;
+            s->curmask = mask[s->cursize];
+            s->slot = s->newcodes;
+            s->top_slot = 1 << s->cursize;
+            while ((c = GetCode(s)) == s->clear_code);
+            if (c == s->end_code) {
+                s->end_code = -1;
+                break;
+            }
+            /* test error */
+            if (c >= s->slot)
+                c = 0;
+            fc = oc = c;
+            *buf++ = c;
+            if ((--l) == 0)
+                break;
+        } else {
+            code = c;
+            if (code >= s->slot) {
+                *sp++ = fc;
+                code = oc;
+            }
+            while (code >= s->newcodes) {
+                *sp++ = s->suffix[code];
+                code = s->prefix[code];
+            }
+            *sp++ = code;
+            if (s->slot < s->top_slot) {
+                s->suffix[s->slot] = fc = code;
+                s->prefix[s->slot++] = oc;
+                oc = c;
+            }
+            if (s->slot == s->top_slot - 1) {
+                if (s->cursize < MAXBITS) {
+                    s->top_slot <<= 1;
+                    s->curmask = mask[++s->cursize];
+                }
+            }
+            while (sp > s->stack) {
+                *buf++ = *(--sp);
+                if ((--l) == 0)
+                    goto the_end;
+            }
+        }
+    }
+  the_end:
+    s->sp = sp;
+    s->oc = oc;
+    s->fc = fc;
+    return len - l;
+}
+
+
 static int tiff_unpack_strip(TiffContext *s, uint8_t* dst, int stride, uint8_t *src, int size, int lines){
     int c, line, pixels, code;
     uint8_t *ssrc = src;
@@ -126,6 +303,10 @@
         return 0;
     }
 #endif
+    if(s->compr == TIFF_LZW){
+        s->lzw.bytestream = src;
+        TLZWDecodeInit(&s->lzw, 8);
+    }
     for(line = 0; line < lines; line++){
         if(src - ssrc > size){
             av_log(s->avctx, AV_LOG_ERROR, "Source data overread\n");
@@ -160,6 +341,10 @@
                 }
             }
             break;
+        case TIFF_LZW:
+            memset(dst, 0xFF, width);
+            pixels = TLZWDecode(&s->lzw, dst, width + 1);
+            break;
         }
         dst += stride;
     }
@@ -247,6 +432,7 @@
         switch(s->compr){
         case TIFF_RAW:
         case TIFF_PACKBITS:
+        case TIFF_LZW:
             break;
         case TIFF_DEFLATE:
         case TIFF_ADOBE_DEFLATE:
@@ -256,9 +442,6 @@
             av_log(s->avctx, AV_LOG_ERROR, "Deflate: ZLib not compiled in\n");
             return -1;
 #endif
-        case TIFF_LZW:
-            av_log(s->avctx, AV_LOG_ERROR, "LZW: not implemented yet\n");
-            return -1;
         case TIFF_G3:
             av_log(s->avctx, AV_LOG_ERROR, "CCITT G3 compression is not supported\n");
             return -1;



More information about the ffmpeg-devel mailing list