版主
主题
帖子
积分10609
阅读权限200
注册时间2008-11-22
最后登录1970-1-1
在线时间 小时
|
楼主 |
发表于 2009-4-13 20:46
|
显示全部楼层
研究了好一段时间了终于明白了8成的原理了!这个东西可能没有多少人会看上的可能太复杂的吧呵呵,没所谓吧反正这个以后可以自己重温一下!下面是这个的C语言:8 ? B8 N, `6 U+ @4 B4 i
; D4 N: ?7 S8 `* P6 ^
$ k, f+ O! ^( K: d9 X. S/* DECODE.C - An LZW decoder for GIF. i) j `2 z' z4 Z9 a0 R
* Copyright (C) 1987, by Steven A. Bennett6 x" p3 b( u+ K& l+ G/ A
* {+ U* O, b) I% Y5 d
* Permission is given by the author to freely redistribute and include! }0 C# S e# Z( R
* this code in any program as long as this credit is given where due.# i n' w4 N2 _$ e1 m
*
: a/ P( N1 r; x1 _* Q5 h * In accordance with the above, I want to credit Steve Wilhite who wrote
6 N4 k/ l$ k- C" v * the code which this is heavily inspired by...3 g4 t# c* t; e+ B0 I
*% Z0 c* T7 Z- ^# B, R
* GIF and 'Graphics Interchange Format' are trademarks (tm) of
+ {, u5 k/ v6 s * Compuserve, Incorporated, an H&R Block Company.2 q4 X- Q8 B/ B/ N) z
*
) K% H5 m9 L. s * Release Notes: This file contains a decoder routine for GIF images
* t) a# p- M* O C8 C$ I * which is similar, structurally, to the original routine by Steve Wilhite.
* B6 t1 Z3 A$ G+ L * It is, however, somewhat noticably faster in most cases.
( V( r7 w: x2 E( f; D$ R, ?7 I& q *0 \1 `4 l1 J& [$ B5 I% g' b& ^- R
*/ l; p, B1 }! @' W: v+ S0 j
4 s, u3 F/ t l9 v#include "std.h". Q& I0 A4 E" i1 j3 D; Y
#include "errs.h"
% N! q" b" K: V: d
, F! L; p4 X* L, O% f0 QIMPORT TEXT *malloc(); /* Standard C library allocation */' q4 S; j4 J: l3 J, e$ t
% o# E [& u+ f- N/* IMPORT INT get_byte(): B( l7 c1 B: V; m- N$ V) U
*$ c, M3 T2 s1 W) q3 t3 m/ L
* - This external (machine specific) function is expected to return
' x$ L0 B6 A: M, O! x) g; f * either the next byte from the GIF file, or a negative number, as
: |8 p- { t, _+ y6 ?* K3 |3 P * defined in ERRS.H.
, T, [% U. {. U% \ */
I: W7 G' H7 n- |* WIMPORT INT get_byte();
, L0 m- I6 I3 w. j% L) ?0 A( r5 v, W4 _
/* IMPORT INT out_line(pixels, linelen)
" b8 M4 ]; _: P5 Z* r. L: n; Y * UBYTE pixels[];. }% P! r0 D7 E; {
* INT linelen;
4 ]4 s7 X' H5 [7 o* X6 R% a' ]' | *
" i+ b9 |% S8 ]! F/ d3 L; V, E- A+ [ * - This function takes a full line of pixels (one byte per pixel) and
' i/ u4 a! Z7 x * displays them (or does whatever your program wants with them...). It
6 G$ Y6 c# l% c * should return zero, or negative if an error or some other event occurs
* G, P, d* |2 O }: u7 S P * which would require aborting the decode process... Note that the length
- t* o4 @; x- W% B1 E9 g * passed will almost always be equal to the line length passed to the; q2 E- r0 S1 f/ l0 k- z V5 ^0 J
* decoder function, with the sole exception occurring when an ending code. e3 `* O2 I9 Y4 c" L1 _
* occurs in an odd place in the GIF file... In any case, linelen will be
" U' z& t& c% z# G% S * equal to the number of pixels passed...
, d" Y- _* R/ |2 C+ I, ^ */
5 A4 b& u1 b7 E- CIMPORT INT out_line();
$ k0 l) ?. t2 B
; R* i4 M7 v/ _, @: T( Z+ `/* IMPORT INT bad_code_count;+ s7 h- {& J' Z' a& Q+ R3 ^0 z0 O
*
" b* f6 m2 |) @: o * This value is the only other global required by the using program, and& u( \: X! o* ^, v
* is incremented each time an out of range code is read by the decoder.
3 V& |7 K& @: n# b( [ * When this value is non-zero after a decode, your GIF file is probably
5 T( h$ Z0 H0 ?/ J6 ^0 q2 i * corrupt in some way.... s8 c: Y: q+ x9 C# f9 W/ \
*/% _: Q0 Y+ U4 Y1 D1 b) D
IMPORT INT bad_code_count;
6 C% t1 z6 r4 ?' [4 p
) n9 f8 n4 @$ s" k#define NULL 0L
* p# i0 p- {6 x5 e% ^9 g5 Q#define MAX_CODES 40959 ?4 C& U" j' b# Q- T! _
, p! ] ]! F, E5 ], @6 w
/* Static variables */
" \4 h' R. ?# r% j/ fLOCAL WORD curr_size; /* The current code size */
' V. Y! c: {6 _LOCAL WORD clear; /* Value for a clear code */2 a* l6 P. d9 u% @2 p% J2 i
LOCAL WORD ending; /* Value for a ending code */
9 Y5 J. L& L: d N0 r$ Z5 |6 w7 FLOCAL WORD newcodes; /* First available code */- H% f& b1 B$ r5 |+ W, x
LOCAL WORD top_slot; /* Highest code for current size */$ Q) b! v( n. b- o. o
LOCAL WORD slot; /* Last read code */. ]4 C: ^6 ~2 \7 A3 E/ z! M
4 ^4 T6 v j* t7 ~* H# j
/* The following static variables are used4 M; p$ a3 \; h. r d$ z
* for seperating out codes& p. I1 j' r; G# X. a
*/
7 T3 ^) Q) x& HLOCAL WORD navail_bytes = 0; /* # bytes left in block */
1 g5 }3 K2 r" D; m! d& t/ ^+ ]LOCAL WORD nbits_left = 0; /* # bits left in current byte */
. { b6 ]' G, l! _! N0 uLOCAL UTINY b1; /* Current byte */: j3 y/ b6 W: Q+ B
LOCAL UTINY byte_buff[257]; /* Current block */
, S( H3 ]) n: ELOCAL UTINY *pbytes; /* Pointer to next byte in block */$ ]6 S5 r' H% _% Z8 \
. t' p" h" a1 f
LOCAL LONG code_mask[13] = {
- \# E# h0 ~' x3 S2 F3 C 0,
* T+ e# p3 G, t' f5 u( Z 0x0001, 0x0003,& ^1 o( \ o2 b. J2 A
0x0007, 0x000F,
% o- S: {0 O& V0 u' }" @$ ] 0x001F, 0x003F,
6 Q1 l9 a5 f6 ]9 L! q& q! z& [ 0x007F, 0x00FF,
( n! j! b+ b' U/ L3 p: s9 V 0x01FF, 0x03FF,0 p, u) w6 o% q* J
0x07FF, 0x0FFF! A: ]( q5 |$ _. P8 y6 U
}; W* ?: X2 C! r1 g7 ~7 j2 s; S; v
! P- d- T7 r+ v3 f4 m1 Y: |5 Y
8 ?2 [2 v3 P3 z n/* This function initializes the decoder for reading a new image.
9 ]- q2 c" f! C3 W( A */
8 f- i, w. B! K0 r+ WLOCAL WORD init_exp(size)
# ~1 v& t4 [& o+ |9 M( f2 f1 U WORD size;
- U* \5 q$ W7 |! {" {; m! b1 c {
B \0 C6 c! g- K9 s. a0 @3 x2 y0 M0 `9 @ curr_size = size + 1;
( ^. c( y) E# d1 G" c4 g0 B! B. G top_slot = 1 << curr_size;' U2 X! h$ g9 k* X$ c( I0 n
clear = 1 << size;
. `. C5 X% W9 y% T3 L7 ` ending = clear + 1;/ \; A! r1 F, m( J1 O' q% }# E
slot = newcodes = ending + 1;* }4 a, u& C E0 X+ z9 \
navail_bytes = nbits_left = 0;
' |; o# V, C6 K9 |. D: k return(0);
/ D) a- a: O ?, x: |" I }
% X% X- `( z6 I" @5 J2 r2 b. v# [! s4 ]0 F1 a
/* get_next_code()
, d5 q& Z: o$ D% I1 k' ^ X * - gets the next code from the GIF file. Returns the code, or else% X, O' l, U& M5 X9 v, k
* a negative number in case of file errors...
" J! d& X/ E+ [5 q6 p */! c. h" T2 R% o
LOCAL WORD get_next_code()
, r: y0 K: h9 p- C# T {- x& z4 R7 R4 y( j& o+ g
WORD i, x;
+ t) R1 H4 q6 v3 [6 p7 e ULONG ret;
/ [6 F8 i' @, Y0 g+ `8 c2 [% p' j/ x: t2 F
if (nbits_left == 0): [* \. m5 z2 a0 x0 m& G
{
?0 J# N7 ^6 E: o' c if (navail_bytes <= 0)
0 x) b! X; G7 }( I2 K {
4 G, {: N! ^$ B
$ s' S5 p1 X1 W /* Out of bytes in current block, so read next block
" G$ a; D6 H1 m5 ^' q */: ^( I: o+ V6 V: {
pbytes = byte_buff;
, q! d- W d: z if ((navail_bytes = get_byte()) < 0)) U; ]3 c/ _2 J2 }
return(navail_bytes);
- e" a& S6 {: U& q" j else if (navail_bytes)3 v, Y' y0 Q$ G( u& h9 x
{
( R2 a; v! d4 I' D for (i = 0; i < navail_bytes; ++i)7 o6 o) `2 ^+ D
{: o0 g ~5 b) ~3 J3 ^+ G
if ((x = get_byte()) < 0), E/ }# e0 c5 m- u
return(x);
; q$ B! E" j8 {# U1 x* ] byte_buff = x;1 g+ _( e& {; D4 [
}. H+ V" ?* N, O, \7 {" s
}' l9 K. [+ |) K( n7 P* V& {
}
" a. p. _6 B/ V- h b1 = *pbytes++;# q+ \+ D& Q2 C8 A7 K
nbits_left = 8;2 s4 D3 _. f' z, M% g# V V9 l' b$ [
--navail_bytes;
- \) |% j! e8 k$ K1 ?! } }
2 ^7 G, k3 q1 @, l; v7 o& k' Y0 a$ V7 |; q3 Y
ret = b1 >> (8 - nbits_left);
9 [: ]4 x. ?2 u8 z, L: ]: Z while (curr_size > nbits_left)
5 S+ f1 y( t+ [" ~ C4 Q {
$ Q7 i3 j6 n" G: b3 Y! ` if (navail_bytes <= 0)
7 t; ]; q6 u. }9 x) V7 L: j5 k {! G( j3 |3 X. P. x& H/ ?( z$ l
& h1 y: I8 p' {6 V/ O
/* Out of bytes in current block, so read next block5 G. y7 k- i/ F! i1 c
*/4 W4 M% R5 T5 ]6 C( }9 H
pbytes = byte_buff;
, U" M4 \' T+ H if ((navail_bytes = get_byte()) < 0)
8 j. u% K- G+ c4 Q- R return(navail_bytes);6 Q j# z$ X, o) P5 H
else if (navail_bytes)0 g/ ^% I# q7 j+ P
{
6 {' ~2 \; a. d% m for (i = 0; i < navail_bytes; ++i)! ]8 k: B8 Q, O- O
{
' D a. r' O! }8 b1 \& P if ((x = get_byte()) < 0)
6 |; `" M1 U- k* a- l) b return(x);" ^1 e7 }' ~: U. w; r; s5 q) M6 Q
byte_buff = x;
: m0 B9 U1 m! O8 Q }. e9 s' w$ }( z5 f$ W
}
( r# f8 \; x$ v/ C- z: | }& p2 O* V6 r9 O& k3 n# a6 U
b1 = *pbytes++;
3 V' x) I1 }5 x ret |= b1 << nbits_left;% q6 t8 e0 r3 L
nbits_left += 8;
4 B2 @9 X1 x* q) r/ s --navail_bytes;- j, ]# `" B" l% Z8 W7 a& v' h
}
7 ]0 t' t3 J2 m8 A* S nbits_left -= curr_size;4 _# [( o3 Q0 a U/ l+ H! n
ret &= code_mask[curr_size];, m) z' T0 X' h: o7 N8 T
return((WORD)(ret));/ w/ v6 {: c; i; M
}
. x x: }% v; e5 u, L2 p5 c
" a/ o7 t6 F; @2 ]' O d2 n) d" d! `. ]& M; M. a7 Q ~. E4 r0 t
/* The reason we have these seperated like this instead of using' T# H+ K: `" L( G5 y$ M; M
* a structure like the original Wilhite code did, is because this0 I6 W6 G5 Y0 \1 }3 f6 r* p
* stuff generally produces significantly faster code when compiled...
+ H' i+ T$ B* o* O * This code is full of similar speedups... (For a good book on writing$ ^% r r" n/ l. ~ f3 Y
* C for speed or for space optomisation, see Efficient C by Tom Plum,
/ P3 ~7 k/ {/ H$ A5 l2 ]9 f D * published by Plum-Hall Associates...)
! }2 r9 Y8 r! _. o& L */, [; Y5 A A- Q6 @
LOCAL UTINY stack[MAX_CODES + 1]; /* Stack for storing pixels */
- O N" ?* P h2 Q" D( V2 f. aLOCAL UTINY suffix[MAX_CODES + 1]; /* Suffix table */3 d0 P8 P- o7 m8 G t: ]6 h
LOCAL UWORD prefix[MAX_CODES + 1]; /* Prefix linked list */& ^* M( p+ K0 L% _$ M+ C( J* c
% d. K8 B- w# e- m& `: ]
/* WORD decoder(linewidth)
1 e; {/ t) d) m$ O0 G4 i * WORD linewidth; * Pixels per line of image *
* N. h1 ~0 A B7 W5 G" g# T- ^) u *
. u; W( O6 Y; T& C) R * - This function decodes an LZW image, according to the method used
) O% P0 `5 M1 V * in the GIF spec. Every *linewidth* "characters" (ie. pixels) decoded
; A- H, l. e/ Z5 g; {/ X1 y * will generate a call to out_line(), which is a user specific function
. q0 ]) G0 N( r: t- N * to display a line of pixels. The function gets it's codes from6 r6 \! I" g$ I: S
* get_next_code() which is responsible for reading blocks of data and
8 m5 y0 [9 u7 o; ]' } * seperating them into the proper size codes. Finally, get_byte() is& x* o9 j, @4 @$ R- J( Y+ J; _1 }
* the global routine to read the next byte from the GIF file.
" ~2 E& v# I: _1 N* \( q2 Y) Y- G * `! k! m& \$ M* d* `
* It is generally a good idea to have linewidth correspond to the actual+ ~9 X) z3 J5 V
* width of a line (as specified in the Image header) to make your own
& Y4 Q6 n0 a7 r1 ` * code a bit simpler, but it isn't absolutely necessary.9 I. g9 [+ k% Y4 @2 D/ ^
*
1 n# f0 B9 x0 B, }( J * Returns: 0 if successful, else negative. (See ERRS.H), z O; F& W- ^$ Y. ^$ q
*
( y! a. B! C5 }* m4 n *// w4 |8 I( C/ k0 s3 r! a
6 B% K7 y% T" j E. bWORD decoder(linewidth); T- o6 x6 L- k6 v4 F
WORD linewidth;/ ]2 R/ I8 t% `. z8 ]) P
{
- B I0 P7 x( v& Z3 c0 `3 s FAST UTINY *sp, *bufptr;. B1 ~; u' v9 A
UTINY *buf;
/ F3 i3 j2 E1 z! j" w FAST WORD code, fc, oc, bufcnt;
6 @5 U$ W' @1 ^% @ a$ x/ M WORD c, size, ret;
* h5 G' {( x' q2 }) R
/ c$ d: w3 R% w! _. H; ? /* Initialize for decoding a new image...
8 K1 o# T. p+ k2 ?: L1 [ */5 }2 f+ O3 \3 r& Z/ V
if ((size = get_byte()) < 0)
! ? ` d3 A" S/ p$ q0 F return(size);
. r6 {9 \/ d% {* Q5 c1 w if (size < 2 || 9 < size), g$ Y3 m0 ~! W% j( X+ z4 d7 C4 ^
return(BAD_CODE_SIZE);
# l0 H7 T8 h/ C/ |8 H0 j" p init_exp(size);: C# M9 a; t; [
: N/ \' A' o2 N8 J
/* Initialize in case they forgot to put in a clear code.
' u) y4 `9 [; } L6 y0 `# a * (This shouldn't happen, but we'll try and decode it anyway...)
0 d# I+ v$ X! _2 t2 G9 @* t */
( b5 P% k( ]3 C" @: N: v- i/ I7 N' Q oc = fc = 0;
9 \. `; j7 Z/ R& p f% w7 `; l6 t, J# v5 y/ i+ j
/* Allocate space for the decode buffer$ N1 J: ]' j0 I6 ?' Z( ~, m
*/
) m1 [( z# Y8 V if ((buf = (UTINY *)malloc(linewidth + 1)) == NULL). x# B& ^6 t1 t% W( A* X
return(OUT_OF_MEMORY);
2 w4 O+ n7 u6 X3 b8 m5 ]
/ v9 E( b' ~( T0 A, R /* Set up the stack pointer and decode buffer pointer' H; {+ b) \) m
*/1 }' {2 n& b1 I( X4 N
sp = stack;+ ^. D) b+ }! }7 }: a2 V
bufptr = buf;
1 o# U+ A8 _. A9 u bufcnt = linewidth;: o( \( C% v" v _/ c
& G, ?8 \2 U1 d8 ~8 X) d7 x7 Q, H
/* This is the main loop. For each code we get we pass through the3 j; K- K8 C5 b+ p _
* linked list of prefix codes, pushing the corresponding "character" for2 q0 w* S) M: T$ c
* each code onto the stack. When the list reaches a single "character"
j; g. x( K8 n7 {8 l3 N * we push that on the stack too, and then start unstacking each
: P7 x- k+ ?+ w Y8 h3 D& J7 f * character for output in the correct order. Special handling is. P+ r0 L2 m- n' B+ [; E* Z, |
* included for the clear code, and the whole thing ends when we get* n; r$ i: a9 J7 o% |, s# E
* an ending code.
" J7 T) J, K8 m! X5 Y7 C1 W8 S2 f */$ N R7 y! j( y# C8 Q6 P" e8 L v
while ((c = get_next_code()) != ending)
e$ I5 {1 K6 } C0 U' @, S, f {
$ P! U# J) Q+ |; G5 L8 `+ l" {1 t1 J, K( t3 y& f/ w
/* If we had a file error, return without completing the decode
) \: D) w5 S5 N- x6 R */2 |( j. p8 K: v+ y% n; f$ g
if (c < 0)5 C5 `' h4 i' ]# \- \( u
{
, |9 A2 T5 p& W. A free(buf);) _* L8 S, h1 {' k/ B
return(0);
, u7 I: x2 I* W. M( W }
/ n$ C, g+ q+ \2 Z4 q0 ~9 v! d2 ]# W0 F5 Q' x
/* If the code is a clear code, reinitialize all necessary items.
, ?/ _: k8 o! N, w */
% t/ ]7 v9 f3 G0 _! N" z, x8 s/ _. { if (c == clear)
% n1 W: B8 ?9 b3 s/ e1 u! U, \- R {
% e3 s) {- `3 x+ Y, P curr_size = size + 1;2 [* Y3 `9 \) `
slot = newcodes;! i# t" l. P3 Q" [0 e2 Q" ^1 w
top_slot = 1 << curr_size;- M% ^( o" V4 P% \5 t' \! M
7 c6 W h, r: L2 S" V$ g4 A /* Continue reading codes until we get a non-clear code
/ U. Q2 I& }$ T5 v l' J: t * (Another unlikely, but possible case...)4 U \1 n; k. Y; v2 i
*/: y/ }5 f9 { e& \9 J; a/ b; t
while ((c = get_next_code()) == clear)
& Q: i2 }+ p* i+ Q+ _ ;
8 V: }! N- F8 h3 w' s" v$ I" F1 l9 T, T: ^2 q0 E* G9 P9 k: w) O
/* If we get an ending code immediately after a clear code/ |( c$ q" G9 U0 A ?% U( }
* (Yet another unlikely case), then break out of the loop.
' O% K A8 m3 F# ?# W */& d1 L) ] l: T% s
if (c == ending): N& u5 S+ U, P1 s' {7 d2 ?
break;
) K# f4 t5 z8 o' z6 _+ u0 E: w# E8 o8 G" i& `
/* Finally, if the code is beyond the range of already set codes,- M2 A+ d. | O" Q- S! ]: I* M ^
* (This one had better NOT happen... I have no idea what will
! {/ `5 P- v$ W/ {9 C * result from this, but I doubt it will look good...) then set it4 ]+ q1 T0 Q8 W6 @$ y1 {4 p/ x
* to color zero.
. D8 z# h( B' t4 c */
?/ [, M3 Z- [3 U if (c >= slot)
, d& v8 Q- \0 [8 j9 P, y c = 0;. B- C ]1 P: C4 V( n' L( y
% J% s2 |8 s* a" G z+ R2 S oc = fc = c;
: X! t7 x/ f! R1 z# Y- D; s
. k+ H+ n- d9 |7 A7 ` /* And let us not forget to put the char into the buffer... And2 P4 |7 s. }2 Z6 U; b; _; k! a
* if, on the off chance, we were exactly one pixel from the end
$ S( @( y# m# p6 h * of the line, we have to send the buffer to the out_line()
* D" M; W+ b, L P * routine...
& Z, K0 F' {2 G8 r */
# a! l- S0 O1 L# _ *bufptr++ = c;
: t% _! E6 H: Y, _( |! w if (--bufcnt == 0)
7 H( F) n b, M: J {
- a5 i% f8 y1 G if ((ret = out_line(buf, linewidth)) < 0)
9 X, J7 U6 Q6 P1 n {
4 X& Q7 K T5 ]: y. w2 ` free(buf);. @7 A1 i. V9 y2 ]7 o9 w
return(ret);
5 @ J4 {( h+ S2 R5 w% O0 h3 ^ }9 y/ K+ F4 J& r6 Q
bufptr = buf;3 s8 c8 e: w5 \. e( f; i
bufcnt = linewidth;8 {5 p8 r* G# x/ x2 ^* w
}8 e, W& n7 i; \/ a0 Q8 L) j2 b
}
/ z v4 M& d1 A% F$ A2 y- n& z: \+ H else! _2 G0 Y v1 Q1 r- @$ z$ `$ |
{) R2 Y8 t" F, n' p, L
$ M& F* F7 h3 O% M
/* In this case, it's not a clear code or an ending code, so0 y$ Y& j% N4 [9 R
* it must be a code code... So we can now decode the code into+ s2 v" u$ L* e# H& U y
* a stack of character codes. (Clear as mud, right?)0 W, O! g4 e* K; R4 m
*/
9 v1 G9 ]0 v% P code = c;
3 O5 }/ {2 C g9 n3 h$ j
4 |5 Z5 }$ |/ R3 V4 C1 [ /* Here we go again with one of those off chances... If, on the2 l" V4 F4 ^7 A7 n
* off chance, the code we got is beyond the range of those already6 R% I5 o n+ U1 @7 u1 D/ k& L
* set up (Another thing which had better NOT happen...) we trick
7 w4 s0 [ y. F2 L, S * the decoder into thinking it actually got the last code read.8 Q7 @# e; C, T9 J9 N
* (Hmmn... I'm not sure why this works... But it does...)4 y0 B- H8 e7 ?" r& u
*/" d8 |6 i! ?/ R- E
if (code >= slot)* ~9 m( }; T" [/ [
{ f& z1 X/ m# Z. z
if (code > slot) l! ?3 a. F1 W7 I* C
++bad_code_count; D9 q/ Y2 y$ e: y# x
code = oc;- T0 x/ g, _: R7 V
*sp++ = fc; G5 V; c6 j( H) J* n7 r) S' ~
}& v E. N) Y$ J0 }, _2 \) Q
' o0 B7 \8 h. Y$ {- A4 O0 }$ {5 w3 o
/* Here we scan back along the linked list of prefixes, pushing
# `& k# R) C5 [6 c; n6 z4 F0 E * helpless characters (ie. suffixes) onto the stack as we do so.
1 y" ~; N- q7 Z7 a) R e4 E */
* B* `8 p7 \ H* N while (code >= newcodes)
' c# X+ U. C' G; X {: ~8 M" X4 B& ^" x/ S" Z9 U$ T1 p
*sp++ = suffix[code];
8 B9 q: v1 @7 P7 G! e" i' v4 m code = prefix[code];" \% n6 d% d2 [+ C9 N
} N3 c9 @- G6 y* ]1 A: O& x
3 E- \8 @# a" q: x& j /* Push the last character on the stack, and set up the new
+ p `- D* ^1 ~ * prefix and suffix, and if the required slot number is greater
5 D. {! M! R; e * than that allowed by the current bit size, increase the bit
- n% M+ t8 Z: N4 C5 u4 q * size. (NOTE - If we are all full, we *don't* save the new# l. x& @* t. j, e; ~; \* ]* `3 |% D
* suffix and prefix... I'm not certain if this is correct...
( H4 U3 V+ O( r9 s6 y. V * it might be more proper to overwrite the last code...
& o% T1 b4 M1 c$ b */
& Q- U2 c9 A0 w9 ?* r8 W5 q6 v# x *sp++ = code;
; Y% B6 X4 R) J4 N if (slot < top_slot)8 @: G- S/ M7 |0 z
{$ ?* k a8 x3 V& @/ s
suffix[slot] = fc = code;
& U5 G. _. J* a- ^ prefix[slot++] = oc;
7 w7 Z( L& ?- s oc = c;' B( N- }9 c8 Z" H0 r2 U0 c c! K1 y- ]+ E
}
; @5 j ^! s% P! d: y6 f if (slot >= top_slot)& ^* w) y. d# u& e9 i7 }
if (curr_size < 12)) i# }0 ~- n. W
{
% y5 X/ K8 J, [. v e5 O top_slot <<= 1;
* a$ _' G' r. g+ f/ K+ f2 z ++curr_size;
/ z; ^" z! H: r: x K9 J }
$ F2 X6 M: `8 [+ O2 U+ R# n+ S6 r5 \+ l5 p/ ^, }
/* Now that we've pushed the decoded string (in reverse order)# w3 P7 K. M# q* f6 J6 {
* onto the stack, lets pop it off and put it into our decode5 i, t$ p2 n1 j) G- z
* buffer... And when the decode buffer is full, write another
8 l( B9 P/ Z! z4 R9 U L6 x * line...
2 c$ x) n, Y) i0 s' m2 V */' o$ ], R: B. K {& T
while (sp > stack)
, L9 ?- B( [% t9 ~) q2 A {
! u1 s) f5 c! H. L: a5 s *bufptr++ = *(--sp);
- {0 i/ ~# x8 s if (--bufcnt == 0)+ r# G8 p) b- Z2 n9 M# `- [
{( ?$ l& X/ N; w. v& A& @
if ((ret = out_line(buf, linewidth)) < 0)0 l7 e& C+ @/ U$ _6 E
{
7 y4 o- Q8 x7 h# C free(buf);5 V+ ?0 V l: Y
return(ret);5 X& {+ ~& R# ^
}
& v/ W# U. T, m; ~8 f# d% l bufptr = buf;
8 k1 j N4 U0 r% o+ d, H" M( Q V bufcnt = linewidth;, n+ x( w! C+ I# }0 \: z6 ]
}
! y' v; q3 G0 ~, P2 c( i) Z" } }: c& e9 [/ ^, r. V9 \. A) L
}( ]8 ]$ h( ^+ w' k7 X% [- }
}2 k5 n/ g9 N) [3 y0 q7 Y
ret = 0;! \" Q; W |9 @5 y- w+ J0 y, j
if (bufcnt != linewidth)6 t9 @# H0 s% D R- k% h) h9 E
ret = out_line(buf, (linewidth - bufcnt));
8 e3 c- {( B+ r6 f free(buf);
, |) J+ ^7 O' ~3 V return(ret);1 X: f. I* D5 [2 z( c
} |
|