Subversion Repositories wimsdev

Rev

Go to most recent revision | Blame | Compare with Previous | Last modification | View Log | RSS feed

  1. /*
  2.  * gifencode.c
  3.  *
  4.  * Copyright (c) 1997,1998 by Hans Dinsen-Hansen
  5.  * The algorithms are inspired by those of gifcode.c
  6.  * Copyright (c) 1995,1996 Michael A. Mayer
  7.  * All rights reserved.
  8.  *
  9.  * This software may be freely copied, modified and redistributed
  10.  * without fee provided that above copyright notices are preserved
  11.  * intact on all copies and modified copies.
  12.  *
  13.  * There is no warranty or other guarantee of fitness of this software.
  14.  * It is provided solely "as is". The author(s) disclaim(s) all
  15.  * responsibility and liability with respect to this software's usage
  16.  * or its effect upon hardware or computer systems.
  17.  *
  18.  * The Graphics Interchange format (c) is the Copyright property of
  19.  * Compuserve Incorporated.  Gif(sm) is a Service Mark property of
  20.  * Compuserve Incorporated.
  21.  *
  22.  *
  23.  *           Implements GIF encoding by means of a tree search.
  24.  *           --------------------------------------------------
  25.  *
  26.  *  - The string table may be thought of being stored in a "b-tree of
  27.  * steroids," or more specifically, a {256,128,...,4}-tree, depending on
  28.  * the size of the color map.
  29.  *  - Each (non-NULL) node contains the string table index (or code) and
  30.  * {256,128,...,4} pointers to other nodes.
  31.  *  - For example, the index associated with the string 0-3-173-25 would be
  32.  * stored in:
  33.  *       first->node[0]->node[3]->node[173]->node[25]->code
  34.  *
  35.  *  - Speed and effectivity considerations, however, have made this
  36.  * implementation somewhat obscure, because it is costly to initialize
  37.  * a node-array where most elements will never be used.
  38.  *  - Initially, a new node will be marked as terminating, TERMIN.
  39.  * If this node is used at a later stage, its mark will be changed.
  40.  *  - Only nodes with several used nodes will be associated with a
  41.  * node-array.  Such nodes are marked LOOKUP.
  42.  *  - The remaining nodes are marked SEARCH.  They are linked together
  43.  * in a search-list, where a field, NODE->alt, points at an alternative
  44.  * following color.
  45.  *  - It is hardly feasible exactly to predict which nodes will have most
  46.  * used node pointers.  The theory here is that the very first node as
  47.  * well as the first couple of nodes which need at least one alternative
  48.  * color, will be among the ones with many nodes ("... whatever that
  49.  * means", as my tutor in Num. Analysis and programming used to say).
  50.  *  - The number of possible LOOKUP nodes depends on the size of the color
  51.  * map.  Large color maps will have many SEARCH nodes; small color maps
  52.  * will probably have many LOOKUP nodes.
  53. */
  54.  
  55. #include "whirlgif.h"
  56.  
  57. #define BLOKLEN 255
  58. #define BUFLEN 1000
  59.  
  60.  
  61. int chainlen = 0, maxchainlen = 0, nodecount = 0, lookuptypes = 0, nbits;
  62. short need = 8;
  63. GifTree *empty[256], GifRoot = {LOOKUP, 0, 0, empty, NULL, NULL},
  64.         *topNode, *baseNode, **nodeArray, **lastArray;
  65.  
  66. extern unsigned int debugFlag, verbose;
  67. extern int count;
  68.  
  69. void GifEncode(FILE *fout, UBYTE *pixels, int depth, int siz)
  70. {
  71.   GifTree *first = &GifRoot, *newNode, *curNode;
  72.   UBYTE   *end;
  73.   int     cc, eoi, next, tel=0;
  74.   short   cLength;
  75.  
  76.   char    *pos, *buffer;
  77.  
  78.   empty[0] = NULL;
  79.   need = 8;
  80.  
  81.   nodeArray = empty;
  82.   memmove(++nodeArray, empty, 255*sizeof(GifTree **));
  83.   if (( buffer = (char *)malloc((BUFLEN+1)*sizeof(char))) == NULL )
  84.          TheEnd1("No memory for writing");
  85.   buffer++;
  86.  
  87.  
  88.   pos = buffer;
  89.   buffer[0] = 0x0;
  90.  
  91.   cc = (depth == 1) ? 0x4 : 1<<depth;
  92.   fputc((depth == 1) ? 2 : depth, fout);
  93.   eoi = cc+1;
  94.   next = cc+2;
  95.  
  96.   cLength = (depth == 1) ? 3 : depth+1;
  97.  
  98.   if (( topNode = baseNode = (GifTree *)malloc(sizeof(GifTree)*4094)) == NULL )
  99.          TheEnd1("No memory for GIF-code tree");
  100.   if (( nodeArray = first->node = (GifTree **)malloc(256*sizeof(GifTree *)*noOfArrays)) == NULL )
  101.          TheEnd1("No memory for search nodes");
  102.   lastArray = nodeArray + ( 256*noOfArrays - cc);
  103.   ClearTree(cc, first);
  104.  
  105.   pos = AddCodeToBuffer(cc, cLength, pos);
  106.  
  107.   end = pixels+siz;
  108.   curNode = first;
  109.   while(pixels < end) {
  110.  
  111.     if ( curNode->node[*pixels] != NULL ) {
  112.       curNode = curNode->node[*pixels];
  113.       tel++;
  114.       pixels++;
  115.       chainlen++;
  116.       continue;
  117.     } else if ( curNode->typ == SEARCH ) {
  118.       newNode = curNode->nxt;
  119.       while ( newNode->alt != NULL ) {
  120.         if ( newNode->ix == *pixels ) break;
  121.         newNode = newNode->alt;
  122.       }
  123.       if (newNode->ix == *pixels ) {
  124.         tel++;
  125.         pixels++;
  126.         chainlen++;
  127.         curNode = newNode;
  128.         continue;
  129.       }
  130.     }
  131.  
  132. /* ******************************************************
  133.  * If there is no more thread to follow, we create a new node.  If the
  134.  * current node is terminating, it will become a SEARCH node.  If it is
  135.  * a SEARCH node, and if we still have room, it will be converted to a
  136.  * LOOKUP node.
  137. */
  138.   newNode = ++topNode;
  139.   switch (curNode->typ ) {
  140.    case LOOKUP:
  141.      newNode->nxt = NULL;
  142.      newNode->alt = NULL,
  143.      curNode->node[*pixels] = newNode;
  144.    break;
  145.    case SEARCH:
  146.      if ( nodeArray != lastArray ) {
  147.        nodeArray += cc;
  148.        curNode->node = nodeArray;
  149.        curNode->typ = LOOKUP;
  150.        curNode->node[*pixels] = newNode;
  151.        curNode->node[(curNode->nxt)->ix] = curNode->nxt;
  152.        lookuptypes++;
  153.        newNode->nxt = NULL;
  154.        newNode->alt = NULL,
  155.        curNode->nxt = NULL;
  156.        break;
  157.      }
  158. /*   otherwise do as we do with a TERMIN node  */
  159.    case TERMIN:
  160.      newNode->alt = curNode->nxt;
  161.      newNode->nxt = NULL,
  162.      curNode->nxt = newNode;
  163.      curNode->typ = SEARCH;
  164.      break;
  165.    default:
  166.      fprintf(stderr, "Silly node type: %d\n", curNode->typ);
  167.   }
  168.   newNode->code = next;
  169.   newNode->ix = *pixels;
  170.   newNode->typ = TERMIN;
  171.   newNode->node = empty;
  172.   nodecount++;
  173. /*
  174. * End of node creation
  175. * ******************************************************
  176. */
  177.   if (debugFlag) {
  178.     if (curNode == newNode) fprintf(stderr, "Wrong choice of node\n");
  179.     if ( curNode->typ == LOOKUP && curNode->node[*pixels] != newNode ) fprintf(stderr, "Wrong pixel coding\n");
  180.     if ( curNode->typ == TERMIN ) fprintf(stderr, "Wrong Type coding; frame no = %d; pixel# = %d; nodecount = %d\n", count, tel, nodecount);
  181.   }
  182.     pos = AddCodeToBuffer(curNode->code, cLength, pos);
  183.     if ( chainlen > maxchainlen ) maxchainlen = chainlen;
  184.     chainlen = 0;
  185.     if(pos-buffer>BLOKLEN) {
  186.       buffer[-1] = BLOKLEN;
  187.       fwrite(buffer-1, 1, BLOKLEN+1, fout);
  188.       buffer[0] = buffer[BLOKLEN];
  189.       buffer[1] = buffer[BLOKLEN+1];
  190.       buffer[2] = buffer[BLOKLEN+2];
  191.       buffer[3] = buffer[BLOKLEN+3];
  192.       pos -= BLOKLEN;
  193.     }
  194.     curNode = first;
  195.  
  196.     if(next == (1<<cLength)) cLength++;
  197.     next++;
  198.  
  199.     if(next == 0xfff) {
  200.       ClearTree(cc,first);
  201.       pos = AddCodeToBuffer(cc, cLength, pos);
  202.       if(pos-buffer>BLOKLEN) {
  203.         buffer[-1] = BLOKLEN;
  204.         fwrite(buffer-1, 1, BLOKLEN+1, fout);
  205.         buffer[0] = buffer[BLOKLEN];
  206.         buffer[1] = buffer[BLOKLEN+1];
  207.         buffer[2] = buffer[BLOKLEN+2];
  208.         buffer[3] = buffer[BLOKLEN+3];
  209.         pos -= BLOKLEN;
  210.       }
  211.       next = cc+2;
  212.       cLength = (depth == 1)?3:depth+1;
  213.     }
  214.   }
  215.  
  216.   pos = AddCodeToBuffer(curNode->code, cLength, pos);
  217.   if(pos-buffer>BLOKLEN-3) {
  218.     buffer[-1] = BLOKLEN-3;
  219.     fwrite(buffer-1, 1, BLOKLEN-2, fout);
  220.     buffer[0] = buffer[BLOKLEN-3];
  221.     buffer[1] = buffer[BLOKLEN-2];
  222.     buffer[2] = buffer[BLOKLEN-1];
  223.     buffer[3] = buffer[BLOKLEN];
  224.     buffer[4] = buffer[BLOKLEN+1];
  225.     pos -= BLOKLEN-3;
  226.   }
  227.   pos = AddCodeToBuffer(eoi, cLength, pos);
  228.   pos = AddCodeToBuffer(0x0, -1, pos);
  229.   buffer[-1] = pos-buffer;
  230.  
  231.   fwrite(buffer-1, pos-buffer+1, 1, fout);
  232.   free(buffer-1); free(first->node); free(baseNode);
  233.   if (debugFlag) fprintf(stderr, "pixel count = %d; nodeCount = %d lookup nodes = %d\n", tel, nodecount, lookuptypes);
  234.   return;
  235.  
  236. }
  237.  
  238. void ClearTree(int cc, GifTree *root)
  239. {
  240.   int i;
  241.   GifTree *newNode, **xx;
  242.  
  243.   if (debugFlag>1) fprintf(stderr, "Clear Tree  cc= %d\n", cc);
  244.   if (debugFlag>1) fprintf(stderr, "nodeCount = %d lookup nodes = %d\n", nodecount, lookuptypes);
  245.   maxchainlen=0; lookuptypes = 1;
  246.   nodecount = 0;
  247.   nodeArray = root->node;
  248.   xx= nodeArray;
  249.   for (i = 0; i < noOfArrays; i++ ) {
  250.     memmove (xx, empty, 256*sizeof(GifTree **));
  251.     xx += 256;
  252.   }
  253.   topNode = baseNode;
  254.   for(i=0; i<cc; i++) {
  255.     root->node[i] = newNode = ++topNode;
  256.     newNode->nxt = NULL;
  257.     newNode->alt = NULL;
  258.     newNode->code = i;
  259.     newNode->ix = i;
  260.     newNode->typ = TERMIN;
  261.     newNode->node = empty;
  262.     nodecount++;
  263.   }
  264. }
  265.  
  266. char *AddCodeToBuffer(int code, short n, char *buf)
  267. {
  268.   int    mask;
  269.  
  270.   if(n<0) {
  271.     if(need<8) {
  272.       buf++;
  273.       *buf = 0x0;
  274.     }
  275.     need = 8;
  276.     return buf;
  277.   }
  278.  
  279.   while(n>=need) {
  280.     mask = (1<<need)-1;
  281.     *buf += (mask&code)<<(8-need);
  282.     buf++;
  283.     *buf = 0x0;
  284.     code = code>>need;
  285.     n -= need;
  286.     need = 8;
  287.   }
  288.   if(n) {
  289.     mask = (1<<n)-1;
  290.     *buf += (mask&code)<<(8-need);
  291.     need -= n;
  292.   }
  293.   return buf;
  294. }
  295.