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