/* gifpil.c -- convert GIF image to Palm pilot native format 
 Copyright (c) 2001 Ross Thompson
 Author: Ross Thompson <ross@whatsis.com>
*/

/*
 This file is free software; you can redistribute it and/or modify
 it in any way.
 
 This program is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
*/

/*
  To build: gcc -o gifpil -Wall gifpilc.
  To use:   ./gifpil <gif> [<output>]
    (default output is stdout.)
  This is unmaintained software.  You're on your own.
*/

#include <unistd.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <strings.h>
#include <malloc.h>

typedef unsigned char uchar;

#define GLOBAL_CTABLE_FLAG 0x80
#define GLOBAL_CTABLE_SIZE 0x07

#define LOCAL_CTABLE_FLAG 0x80
#define LOCAL_CTABLE_SIZE 0x07

#define ARSIZE(x) (sizeof(x)/sizeof(x[0]))
typedef struct {
    uchar red, green, blue;
} Color;

typedef struct {
    ushort scrwidth, scrheight;
    uchar packed;
    uchar bci;
    uchar par;
    uint ncolors;
    Color ctable[256];
    ushort imwidth, imheight;
    uchar  impacked;
    uchar  minsize;
    uchar *data;
    uchar extension[4];
    uchar transparent;
} Image;

/* ---------- Panic ---------- */

static void Panic(const char *msg)
{
    fputs(msg, stderr);
    fputc('\n', stderr);
    exit(1);
}

/* ---------- bit streams ---------- */

typedef struct {
    uchar *ptr, *end;
    int bits, nbits, writep;
} BitStm;

static void bsInit(BitStm *bs, char *ptr, int len, int writep)
{
    bs->ptr = ptr;
    bs->end = ptr + len;
    bs->bits = bs->nbits = 0;
    bs->writep = writep;
}

static void bsReset(BitStm *bs, char *ptr, int len)
{
    bs->ptr = ptr;
    bs->end = ptr + len;
    if (bs->writep) {
        while (bs->nbits >= 8) {
            *bs->ptr++ = (uchar) (bs->bits & 0xFF);
            bs->bits >>= 8;
            bs->nbits -= 8;
        }
    }
}

static int bsRead(BitStm *bs, int nb)
{
    int val;

    while (bs->nbits < nb && bs->ptr < bs->end) {
        bs->bits |= (*bs->ptr++) << bs->nbits;
        bs->nbits += 8;
    }

    if (bs->nbits < nb) return -1;

    val = bs->bits & ((1 << nb) - 1);
    bs->bits >>= nb;
    bs->nbits -= nb;

    return val;
}

/* ---------- code table ---------- */

#define MAXCODELEN 12
#define MAXCODE (1 << MAXCODELEN)

typedef struct {
    int previous, val, next, bro;
} CEntry;

static struct {
    CEntry codes[MAXCODE];
    int ncodes, codeLen, datLen;
    int clear, end;
} codeTable;

static void initCodes(int datLen)
{
    int i;

    codeTable.datLen = datLen;
    codeTable.codeLen = datLen + 1;
    codeTable.ncodes = (1 << datLen) + 2;
    codeTable.clear = codeTable.ncodes - 2;
    codeTable.end = codeTable.ncodes - 1;
    for (i = 0; i < codeTable.ncodes; i++) {
        codeTable.codes[i].val = i;
        codeTable.codes[i].previous = -1;
        codeTable.codes[i].next = -1;
        codeTable.codes[i].bro = -1;
    }
}

static void resetCodes(void)
{
    initCodes(codeTable.datLen);
}

static void addCode(int val, int prev)
{
    codeTable.codes[codeTable.ncodes].val = val;
    codeTable.codes[codeTable.ncodes].previous = prev;
    codeTable.codes[codeTable.ncodes].next = -1;
    codeTable.codes[codeTable.ncodes].bro = codeTable.codes[prev].next;
    codeTable.codes[prev].next = codeTable.ncodes;
    codeTable.ncodes++;
}

static void bumpCodeSize() { codeTable.codeLen++; }

/* ---------- decoder ---------- */

static struct {
    int done, lastcode, doclear;
    BitStm bs;
    uchar *ptr, *pend;
} Coder;

static void initDecoder(uchar *data, uchar codesize)
{
    bsInit(&Coder.bs, 0, 0, 0);
    initCodes(codesize);
    Coder.done = 0;
    Coder.lastcode = -1;
    Coder.ptr = data;
}

#define decoderDone() Coder.done

static int copycode(int idx)
{
    int fc;

    fc = (codeTable.codes[idx].previous >= 0) ?
        copycode(codeTable.codes[idx].previous) :
        codeTable.codes[idx].val;
    *Coder.ptr++ = codeTable.codes[idx].val;

    return fc;
}

static void decodeBlock(uchar *buf, int sz)
{
    int cur, fc;

    bsReset(&Coder.bs, buf, sz);
    while ((cur = bsRead(&Coder.bs, codeTable.codeLen)) >= 0) {
        if (cur == codeTable.clear) {
            resetCodes();
            Coder.lastcode = -1;
        } else if (cur == codeTable.end) {
            Coder.done = 1;
            return;
        } else if (Coder.lastcode < 0) {
            copycode(cur);
            Coder.lastcode = cur;
        } else if (cur < codeTable.ncodes) {
            fc = copycode(cur);
            if (codeTable.ncodes < MAXCODE) {
                addCode(fc, Coder.lastcode);
                if (codeTable.ncodes == (1 << codeTable.codeLen) &&
                    codeTable.codeLen < MAXCODELEN)
                    bumpCodeSize();
                Coder.lastcode = cur;
            }
        } else if (cur == codeTable.ncodes) {
            fc = copycode(Coder.lastcode);
            copycode(fc);
            addCode(fc, Coder.lastcode);
            if (codeTable.ncodes == (1 << codeTable.codeLen) &&
                codeTable.codeLen < MAXCODELEN)
                bumpCodeSize();
            Coder.lastcode = cur;
        } else {
            Panic("Illegal code in LZW stream.");
        }
    }
}

/* -------------------- */

#define readChar(inf) ((uchar) fgetc(inf))

static ushort readShort(FILE *inf)
{
    ushort val = readChar(inf);
    return val | (readChar(inf) << 8);
}

/* -------------------- */

static void readHeader(FILE *inf, Image *img)
{
    char buf[6];

    if (fread(buf, 1, 6, inf) != 6) Panic("premature EOF");
    if (strncmp(buf, "GIF", 3)) Panic("Not a GIF file.");
}

static void readLogScrDesc(FILE *inf, Image *img)
{
    img->scrwidth = readShort(inf);
    img->scrheight = readShort(inf);
    img->packed = readChar(inf);
    img->bci = readChar(inf);
    img->par = readChar(inf);
    if (img->packed & GLOBAL_CTABLE_FLAG) {
        img->ncolors = (1 << ((img->packed & GLOBAL_CTABLE_SIZE) + 1));
        if (fread(img->ctable, 3, img->ncolors, inf) != img->ncolors)
            Panic("Premature end of file.");
    } else img->ncolors = 0;
}

static void skipExtensionBlock(FILE *inf, Image *img)
{
    int sz;
    char buf[256];

    while ((sz = fgetc(inf)) > 0)
        if (fread(buf, 1, sz, inf) != sz) break;

    if (sz != 0) Panic("premature EOF on input.");
}

static void readImage(FILE *inf, Image *img)
{
    uchar buf[256], sz;

    if (readShort(inf) || readShort(inf))
        Panic("First image is not aligned with screen.");
    img->imwidth = readShort(inf);
    img->imheight = readShort(inf);
    img->impacked = readChar(inf);
    if (img->impacked & LOCAL_CTABLE_FLAG) {
        img->ncolors = (1 << ((img->impacked & LOCAL_CTABLE_SIZE) + 1));
        if (fread(img->ctable, 3, img->ncolors, inf) != img->ncolors)
            Panic("Premature end of file.");
        img->packed &= ~GLOBAL_CTABLE_SIZE;
        img->packed |= (GLOBAL_CTABLE_FLAG | (img->impacked & LOCAL_CTABLE_SIZE));
        img->impacked &= ~LOCAL_CTABLE_FLAG;
    }
    img->data = (uchar *) malloc(img->imwidth * img->imheight);
    if (!img->data) Panic("Out of memory");
    img->minsize = readChar(inf);
    if (img->ncolors == 0) Panic("No colors, man");

    initDecoder(img->data, img->minsize);
    while (!decoderDone()) {
        sz = readChar(inf);
        if (fread(buf, 1, sz, inf) != sz) Panic("Premature EOF.");
        decodeBlock(buf, sz);
    }
}

static void readSection(FILE *inf, Image *img)
{
    switch (fgetc(inf)) {
      case 0x2C: readImage(inf, img); break;
      case 0x21:
        switch (fgetc(inf)) {
          case 0xF9:
            if (fgetc(inf) != 4)
                Panic("Illegal graphic extension block.");
            if (fread(img->extension, 1, 4, inf) != 4)
                Panic("Premature EOF on input.");
            if (fgetc(inf) != 0)
                Panic("Illegal graphic extension block.");
            img->transparent = 1;
            break;
          default:
            skipExtensionBlock(inf, img);
            break;
        }
        break;
      case 0x3B: Panic("No image found in input file.");
      case -1: Panic("Premature EOF on input.");
      default: Panic("Illegal GIF data.");
    }
}

/* ------------------------------ */

#define writeChar(c, f) fputc(c, f)

static void writeShort(ushort s, FILE *f)
{
    writeChar((uchar) (s >> 8), f);
    writeChar((uchar) (s & 0xFF), f);
}

#define PilCompressed    0x8000
#define PilHasColorTable 0x4000
#define PilTransparent   0x2000

/* compression types */
#define PilNoPref     -2
#define PilNoCompress -1
#define PilScanline    0
#define PilRLE         1

#define COMPRESSION PilScanline
#define COMPFLAG(comp) ((comp >= 0) ? PilCompressed : 0)

typedef struct {
    int pxSize, bpr;
} Pimage;

typedef struct {
    int comp, len;
    uchar *data, *datend;
} PilCState;

static void writeHeader(FILE *f, Image *img, Pimage *pim, int comp)
{
    int flags = COMPFLAG(comp) | PilHasColorTable;
    uchar *dp;
    int i, maxc;

    writeShort(img->imwidth, f);
    writeShort(img->imheight, f);
    writeShort(pim->bpr, f);

    if (img->transparent) flags |= PilTransparent;
    writeShort(flags, f);
    writeChar(pim->pxSize, f);
    writeChar(2, f);
    writeShort(0, f);           /* nextDepthOffset */
    writeChar(img->transparent ? img->extension[3] : 0, f); /* transp. idx */
    writeChar(COMPFLAG(comp) ? comp : 0, f);  /* compression type */
    writeShort(0, f);           /* reserved (2 bytes) */

    for (i = img->imwidth * img->imheight, maxc = 0, dp = img->data;
         i-- > 0; dp++) {
        if (maxc < *dp) maxc = *dp;
    }

    /* color table */
    writeShort(++maxc, f); /* include highest used.  Woops. */
    for (i = 0; i < maxc; i++) {
        writeChar(0, f); /* index */
        writeChar(img->ctable[i].red, f);
        writeChar(img->ctable[i].green, f);
        writeChar(img->ctable[i].blue, f);
    }
}

static void writeImage(FILE *f, PilCState *pcs) {
    fwrite(pcs->data, 1, pcs->len, f);
}

static void initPim(Image *img, Pimage *pim)
{
    pim->pxSize = img->minsize;
    if (pim->pxSize == 3) pim->pxSize = 4;
    else if (pim->pxSize > 4) pim->pxSize = 8;

    img->transparent = 0;        /* XXX DEBUG */
    /* pim->pxSize = 8;             XXX DEBUG */

    pim->bpr = (img->imwidth * pim->pxSize + 7) / 8;
    if (pim->bpr & 1) pim->bpr++;
}

static void PCSChar(PilCState *pcs, uchar val)
{
    if (pcs->data + pcs->len < pcs->datend) {
        pcs->data[pcs->len++] = val;
    }
}

static void compressImage(Image *img, Pimage *pim, PilCState *pcs, int meth)
{
    int s = 2 * pim->bpr * img->imheight;

    pcs->data = (uchar *) malloc(s);
    pcs->datend = pcs->data + s;
    pcs->comp = meth;

    if (pcs->comp != PilNoCompress) { /* reserve room for length */
        PCSChar(pcs, 0);
        PCSChar(pcs, 0);
    }

    switch (pcs->comp) {
      case PilScanline: {
          uchar *dp, *sl, rowbytes[8], db;
          int r, c, rbi, sli, i;

          sl = (uchar *) malloc(pim->bpr);

          /* image data -- scanline compression */
          for (r = 0, dp = img->data; r < img->imheight; r++) {
              for (db = c = sli = 0; sli < pim->bpr; sli += 8) {
                  memset(rowbytes, 0, sizeof(rowbytes));
                  for (rbi = 0; rbi < 8; rbi++) {
                      for (i = 8 - pim->pxSize; i >= 0; i -= pim->pxSize) {
                          if (c < img->imwidth) {
                              rowbytes[rbi] |= (*dp++) << i, c++;
                          }
                      }
                  }
                  for (rbi = db = 0; rbi < 8 && rbi + sli < pim->bpr; rbi++) {
                      if (r == 0 || rowbytes[rbi] != sl[sli + rbi]) {
                          db |= (1 << (7 - rbi));
                      }
                  }
                  PCSChar(pcs, db);
                  for (rbi = 0; rbi < 8; rbi++) {
                      if (db & (1 << (7 - rbi))) PCSChar(pcs, rowbytes[rbi]);
                  }
                  memcpy(&sl[sli], rowbytes, 8);
              }
          }

          free(sl);
      }
      break;
      case PilNoCompress: {
          uchar *dp;
          int r, c, b, bc, i;

          for (r = 0, dp = img->data; r < img->imheight; r++) {
              for (c = bc = 0; bc < pim->bpr; bc++) {
                  for (b = 0, i = 8 - pim->pxSize;
                       i >= 0; i -= pim->pxSize, c++) {
                      if (c < img->imwidth) b |= (*dp++) << i;
                  }
                  PCSChar(pcs, b);
              }
          }
      }
      break;
      case PilRLE: {
          uchar *dp;
          int r, bc, c, i, cnt, val, newval;

          /* image data -- run length compression */
          for (r = 0, dp = img->data; r < img->imheight; r++) {
              for (val = -1, bc = cnt = c = 0; bc < pim->bpr; bc++) {
                  for (newval = 0, i = 8 - pim->pxSize;
                       i >= 0; i -= pim->pxSize, c++) {
                      if (c < img->imwidth) newval |= (*dp++) << i;
                  }
                  if (val == newval && cnt < 0xFF) cnt++;
                  else {
                      if (cnt > 0) {
                          PCSChar(pcs, cnt);
                          PCSChar(pcs, val);
                      }
                      val = newval;
                      cnt = 1;
                  }
              }
              if (cnt > 0) {
                  PCSChar(pcs, cnt);
                  PCSChar(pcs, val);
              }
          }

          PCSChar(pcs, 0);
          PCSChar(pcs, 0);
      }
      break;
    }

    if (pcs->comp != PilNoCompress) {
        pcs->data[0] = (pcs->len >> 8) & 0xFF;
        pcs->data[1] = pcs->len & 0xFF;
    }
    if (pcs->len & 1) PCSChar(pcs, 0); /* pad to even length */
}

/* ------------------------------ */

#define USAGE "usage: gifpil [-r|-l|-n] <imgin> [<imgout>]\n"

static int cmethodz[] = {PilNoCompress, PilScanline, PilRLE};

int main(int argc, char **argv)
{
    char *imgin = 0, *imgout = 0;
    FILE *f;
    Image img;
    Pimage pim;
    PilCState pcs[ARSIZE(cmethodz)], *best;
    int i, meth = PilNoPref;

    for (argc--, argv++; argc > 0; argc--, argv++) {
        if (!strcmp(*argv, "-l")) meth = PilScanline;
        else if (!strcmp(*argv, "-n")) meth = PilNoCompress;
        else if (!strcmp(*argv, "-r")) meth = PilRLE;
        else if (!imgin) imgin = *argv;
        else if (!imgout) imgout = *argv;
        else Panic(USAGE);
    }
    if (!imgin) Panic(USAGE);

    memset(&img, 0, sizeof(img));
    memset(&pim, 0, sizeof(pim));
    memset(&pcs, 0, sizeof(pcs));

    if (!(f = fopen(imgin, "r"))) Panic("Could not open input file.");

    readHeader(f, &img);
    readLogScrDesc(f, &img);
    while (!img.data) readSection(f, &img);

    fclose(f);
    if (imgout) {
        if (!(f = fopen(imgout, "w")))
            Panic("Could not open output file.");
    } else f = stdout;

    initPim(&img, &pim);
    if (meth == PilNoPref) {
        for (best = 0, i = 0; i < ARSIZE(cmethodz); i++) {
            compressImage(&img, &pim, &pcs[i], cmethodz[i]);
            if (i == 0 || pcs[i].len < best->len) best = &pcs[i];
        }
    } else {
        compressImage(&img, &pim, &pcs[0], meth);
        best = &pcs[0];
    }        

    writeHeader(f, &img, &pim, best->comp);
    writeImage(f, best);

    fclose(f);

    exit(0);
}