Back to index

wims  3.65+svn20090927
gifencod.c
Go to the documentation of this file.
00001 /*
00002  * gifencode.c
00003  *
00004  * Copyright (c) 1997,1998 by Hans Dinsen-Hansen
00005  * The algorithms are inspired by those of gifcode.c
00006  * Copyright (c) 1995,1996 Michael A. Mayer
00007  * All rights reserved.
00008  *
00009  * This software may be freely copied, modified and redistributed
00010  * without fee provided that above copyright notices are preserved
00011  * intact on all copies and modified copies.
00012  *
00013  * There is no warranty or other guarantee of fitness of this software.
00014  * It is provided solely "as is". The author(s) disclaim(s) all
00015  * responsibility and liability with respect to this software's usage
00016  * or its effect upon hardware or computer systems.
00017  *
00018  * The Graphics Interchange format (c) is the Copyright property of
00019  * Compuserve Incorporated.  Gif(sm) is a Service Mark property of
00020  * Compuserve Incorporated.
00021  *
00022  *
00023  *           Implements GIF encoding by means of a tree search.
00024  *           --------------------------------------------------
00025  *
00026  *  - The string table may be thought of being stored in a "b-tree of
00027  * steroids," or more specifically, a {256,128,...,4}-tree, depending on
00028  * the size of the color map.
00029  *  - Each (non-NULL) node contains the string table index (or code) and
00030  * {256,128,...,4} pointers to other nodes.
00031  *  - For example, the index associated with the string 0-3-173-25 would be
00032  * stored in:
00033  *       first->node[0]->node[3]->node[173]->node[25]->code
00034  *
00035  *  - Speed and effectivity considerations, however, have made this
00036  * implementation somewhat obscure, because it is costly to initialize
00037  * a node-array where most elements will never be used.
00038  *  - Initially, a new node will be marked as terminating, TERMIN.
00039  * If this node is used at a later stage, its mark will be changed.
00040  *  - Only nodes with several used nodes will be associated with a
00041  * node-array.  Such nodes are marked LOOKUP.
00042  *  - The remaining nodes are marked SEARCH.  They are linked together
00043  * in a search-list, where a field, NODE->alt, points at an alternative
00044  * following color.
00045  *  - It is hardly feasible exactly to predict which nodes will have most
00046  * used node pointers.  The theory here is that the very first node as
00047  * well as the first couple of nodes which need at least one alternative
00048  * color, will be among the ones with many nodes ("... whatever that
00049  * means", as my tutor in Num. Analysis and programming used to say).
00050  *  - The number of possible LOOKUP nodes depends on the size of the color 
00051  * map.  Large color maps will have many SEARCH nodes; small color maps
00052  * will probably have many LOOKUP nodes.
00053 */
00054 
00055 #include "whirlgif.h"
00056 
00057 #define BLOKLEN 255
00058 #define BUFLEN 1000
00059 
00060 
00061 int chainlen = 0, maxchainlen = 0, nodecount = 0, lookuptypes = 0, nbits;
00062 short need = 8;
00063 GifTree *empty[256], GifRoot = {LOOKUP, 0, 0, empty, NULL, NULL},
00064        *topNode, *baseNode, **nodeArray, **lastArray;
00065 
00066 extern unsigned int debugFlag, verbose;
00067 extern int count;
00068 
00069 void GifEncode(FILE *fout, UBYTE *pixels, int depth, int siz)
00070 {
00071   GifTree *first = &GifRoot, *newNode, *curNode;
00072   UBYTE   *end;
00073   int     cc, eoi, next, tel=0;
00074   short   cLength;
00075 
00076   char    *pos, *buffer;
00077 
00078   empty[0] = NULL;
00079   need = 8;
00080 
00081   nodeArray = empty;
00082   memmove(++nodeArray, empty, 255*sizeof(GifTree **));
00083   if (( buffer = (char *)malloc((BUFLEN+1)*sizeof(char))) == NULL )
00084         TheEnd1("No memory for writing");
00085   buffer++;
00086 
00087 
00088   pos = buffer;
00089   buffer[0] = 0x0;
00090 
00091   cc = (depth == 1) ? 0x4 : 1<<depth;
00092   fputc((depth == 1) ? 2 : depth, fout);
00093   eoi = cc+1;
00094   next = cc+2;
00095 
00096   cLength = (depth == 1) ? 3 : depth+1;
00097 
00098   if (( topNode = baseNode = (GifTree *)malloc(sizeof(GifTree)*4094)) == NULL )
00099         TheEnd1("No memory for GIF-code tree");
00100   if (( nodeArray = first->node = (GifTree **)malloc(256*sizeof(GifTree *)*noOfArrays)) == NULL )
00101         TheEnd1("No memory for search nodes");
00102   lastArray = nodeArray + ( 256*noOfArrays - cc);
00103   ClearTree(cc, first);
00104 
00105   pos = AddCodeToBuffer(cc, cLength, pos);
00106 
00107   end = pixels+siz;
00108   curNode = first;
00109   while(pixels < end) {
00110 
00111     if ( curNode->node[*pixels] != NULL ) {
00112       curNode = curNode->node[*pixels];
00113       tel++;
00114       pixels++;
00115       chainlen++;
00116       continue;
00117     } else if ( curNode->typ == SEARCH ) {
00118       newNode = curNode->nxt;
00119       while ( newNode->alt != NULL ) {
00120        if ( newNode->ix == *pixels ) break;
00121        newNode = newNode->alt;
00122       }
00123       if (newNode->ix == *pixels ) {
00124        tel++;
00125        pixels++;
00126        chainlen++;
00127        curNode = newNode;
00128        continue;
00129       }
00130     }
00131 
00132 /* ******************************************************
00133  * If there is no more thread to follow, we create a new node.  If the
00134  * current node is terminating, it will become a SEARCH node.  If it is
00135  * a SEARCH node, and if we still have room, it will be converted to a
00136  * LOOKUP node.
00137 */
00138   newNode = ++topNode;
00139   switch (curNode->typ ) {
00140    case LOOKUP:
00141      newNode->nxt = NULL;
00142      newNode->alt = NULL,
00143      curNode->node[*pixels] = newNode;
00144    break;
00145    case SEARCH:
00146      if ( nodeArray != lastArray ) {
00147        nodeArray += cc;
00148        curNode->node = nodeArray;
00149        curNode->typ = LOOKUP;
00150        curNode->node[*pixels] = newNode;
00151        curNode->node[(curNode->nxt)->ix] = curNode->nxt;
00152        lookuptypes++;
00153        newNode->nxt = NULL;
00154        newNode->alt = NULL,
00155        curNode->nxt = NULL;
00156        break;
00157      }
00158 /*   otherwise do as we do with a TERMIN node  */
00159    case TERMIN:
00160      newNode->alt = curNode->nxt;
00161      newNode->nxt = NULL,
00162      curNode->nxt = newNode;
00163      curNode->typ = SEARCH;
00164      break;
00165    default:
00166      fprintf(stderr, "Silly node type: %d\n", curNode->typ);
00167   }
00168   newNode->code = next;
00169   newNode->ix = *pixels;
00170   newNode->typ = TERMIN;
00171   newNode->node = empty;
00172   nodecount++;
00173 /*
00174 * End of node creation
00175 * ******************************************************
00176 */
00177   if (debugFlag) {
00178     if (curNode == newNode) fprintf(stderr, "Wrong choice of node\n");
00179     if ( curNode->typ == LOOKUP && curNode->node[*pixels] != newNode ) fprintf(stderr, "Wrong pixel coding\n");
00180     if ( curNode->typ == TERMIN ) fprintf(stderr, "Wrong Type coding; frame no = %d; pixel# = %d; nodecount = %d\n", count, tel, nodecount);
00181   }
00182     pos = AddCodeToBuffer(curNode->code, cLength, pos);
00183     if ( chainlen > maxchainlen ) maxchainlen = chainlen;
00184     chainlen = 0;
00185     if(pos-buffer>BLOKLEN) {
00186       buffer[-1] = BLOKLEN;
00187       fwrite(buffer-1, 1, BLOKLEN+1, fout);
00188       buffer[0] = buffer[BLOKLEN];
00189       buffer[1] = buffer[BLOKLEN+1];
00190       buffer[2] = buffer[BLOKLEN+2];
00191       buffer[3] = buffer[BLOKLEN+3];
00192       pos -= BLOKLEN;
00193     }
00194     curNode = first;
00195 
00196     if(next == (1<<cLength)) cLength++;
00197     next++;
00198 
00199     if(next == 0xfff) {
00200       ClearTree(cc,first);
00201       pos = AddCodeToBuffer(cc, cLength, pos);
00202       if(pos-buffer>BLOKLEN) {
00203        buffer[-1] = BLOKLEN;
00204        fwrite(buffer-1, 1, BLOKLEN+1, fout);
00205        buffer[0] = buffer[BLOKLEN];
00206        buffer[1] = buffer[BLOKLEN+1];
00207        buffer[2] = buffer[BLOKLEN+2];
00208        buffer[3] = buffer[BLOKLEN+3];
00209        pos -= BLOKLEN;
00210       }
00211       next = cc+2;
00212       cLength = (depth == 1)?3:depth+1;
00213     }
00214   }
00215 
00216   pos = AddCodeToBuffer(curNode->code, cLength, pos);
00217   if(pos-buffer>BLOKLEN-3) {
00218     buffer[-1] = BLOKLEN-3;
00219     fwrite(buffer-1, 1, BLOKLEN-2, fout);
00220     buffer[0] = buffer[BLOKLEN-3];
00221     buffer[1] = buffer[BLOKLEN-2];
00222     buffer[2] = buffer[BLOKLEN-1];
00223     buffer[3] = buffer[BLOKLEN];
00224     buffer[4] = buffer[BLOKLEN+1];
00225     pos -= BLOKLEN-3;
00226   }
00227   pos = AddCodeToBuffer(eoi, cLength, pos);
00228   pos = AddCodeToBuffer(0x0, -1, pos);
00229   buffer[-1] = pos-buffer;
00230 
00231   fwrite(buffer-1, pos-buffer+1, 1, fout);
00232   free(buffer-1); free(first->node); free(baseNode);
00233   if (debugFlag) fprintf(stderr, "pixel count = %d; nodeCount = %d lookup nodes = %d\n", tel, nodecount, lookuptypes);
00234   return;
00235 
00236 }
00237 
00238 void ClearTree(int cc, GifTree *root)
00239 {
00240   int i;
00241   GifTree *newNode, **xx;
00242 
00243   if (debugFlag>1) fprintf(stderr, "Clear Tree  cc= %d\n", cc);
00244   if (debugFlag>1) fprintf(stderr, "nodeCount = %d lookup nodes = %d\n", nodecount, lookuptypes);
00245   maxchainlen=0; lookuptypes = 1;
00246   nodecount = 0;
00247   nodeArray = root->node;
00248   xx= nodeArray;
00249   for (i = 0; i < noOfArrays; i++ ) {
00250     memmove (xx, empty, 256*sizeof(GifTree **));
00251     xx += 256;
00252   }
00253   topNode = baseNode;
00254   for(i=0; i<cc; i++) {
00255     root->node[i] = newNode = ++topNode;
00256     newNode->nxt = NULL;
00257     newNode->alt = NULL;
00258     newNode->code = i;
00259     newNode->ix = i;
00260     newNode->typ = TERMIN;
00261     newNode->node = empty;
00262     nodecount++;
00263   }
00264 }
00265 
00266 char *AddCodeToBuffer(int code, short n, char *buf)
00267 {
00268   int    mask;
00269 
00270   if(n<0) {
00271     if(need<8) {
00272       buf++;
00273       *buf = 0x0;
00274     }
00275     need = 8;
00276     return buf;
00277   }
00278 
00279   while(n>=need) {
00280     mask = (1<<need)-1;
00281     *buf += (mask&code)<<(8-need);
00282     buf++;
00283     *buf = 0x0;
00284     code = code>>need;
00285     n -= need;
00286     need = 8;
00287   }
00288   if(n) {
00289     mask = (1<<n)-1;
00290     *buf += (mask&code)<<(8-need);
00291     need -= n;
00292   }
00293   return buf;
00294 }