1 b6afd33e 2003-11-23 devnull #include <u.h>
2 b6afd33e 2003-11-23 devnull #include <libc.h>
3 b6afd33e 2003-11-23 devnull #include <flate.h>
5 b6afd33e 2003-11-23 devnull typedef struct Chain Chain;
6 b6afd33e 2003-11-23 devnull typedef struct Chains Chains;
7 b6afd33e 2003-11-23 devnull typedef struct Dyncode Dyncode;
8 b6afd33e 2003-11-23 devnull typedef struct Huff Huff;
9 b6afd33e 2003-11-23 devnull typedef struct LZblock LZblock;
10 b6afd33e 2003-11-23 devnull typedef struct LZstate LZstate;
15 b6afd33e 2003-11-23 devnull * deflate format paramaters
17 b6afd33e 2003-11-23 devnull DeflateUnc = 0, /* uncompressed block */
18 b6afd33e 2003-11-23 devnull DeflateFix = 1, /* fixed huffman codes */
19 b6afd33e 2003-11-23 devnull DeflateDyn = 2, /* dynamic huffman codes */
21 b6afd33e 2003-11-23 devnull DeflateEob = 256, /* end of block code in lit/len book */
22 b6afd33e 2003-11-23 devnull DeflateMaxBlock = 64*1024-1, /* maximum size of uncompressed block */
24 b6afd33e 2003-11-23 devnull DeflateMaxExp = 10, /* maximum expansion for a block */
26 b6afd33e 2003-11-23 devnull LenStart = 257, /* start of length codes in litlen */
27 b6afd33e 2003-11-23 devnull Nlitlen = 288, /* number of litlen codes */
28 b6afd33e 2003-11-23 devnull Noff = 30, /* number of offset codes */
29 b6afd33e 2003-11-23 devnull Nclen = 19, /* number of codelen codes */
31 b6afd33e 2003-11-23 devnull MaxOff = 32*1024,
32 b6afd33e 2003-11-23 devnull MinMatch = 3, /* shortest match possible */
33 b6afd33e 2003-11-23 devnull MaxMatch = 258, /* longest match possible */
36 b6afd33e 2003-11-23 devnull * huffman code paramaters
38 b6afd33e 2003-11-23 devnull MaxLeaf = Nlitlen,
39 b6afd33e 2003-11-23 devnull MaxHuffBits = 16, /* max bits in a huffman code */
40 b6afd33e 2003-11-23 devnull ChainMem = 2 * (MaxHuffBits - 1) * MaxHuffBits,
43 b6afd33e 2003-11-23 devnull * coding of the lz parse
45 b6afd33e 2003-11-23 devnull LenFlag = 1 << 3,
46 b6afd33e 2003-11-23 devnull LenShift = 4, /* leaves enough space for MinMatchMaxOff */
47 b6afd33e 2003-11-23 devnull MaxLitRun = LenFlag - 1,
50 b6afd33e 2003-11-23 devnull * internal lz paramaters
52 b6afd33e 2003-11-23 devnull DeflateOut = 4096, /* output buffer size */
53 b6afd33e 2003-11-23 devnull BlockSize = 8192, /* attempted input read quanta */
54 b6afd33e 2003-11-23 devnull DeflateBlock = DeflateMaxBlock & ~(BlockSize - 1),
55 b6afd33e 2003-11-23 devnull MinMatchMaxOff = 4096, /* max profitable offset for small match;
56 b6afd33e 2003-11-23 devnull * assumes 8 bits for len, 5+10 for offset
57 b6afd33e 2003-11-23 devnull * DONT CHANGE WITHOUT CHANGING LZPARSE CONSTANTS
59 b6afd33e 2003-11-23 devnull HistSlop = 512, /* must be at lead MaxMatch */
60 b6afd33e 2003-11-23 devnull HistBlock = 64*1024,
61 b6afd33e 2003-11-23 devnull HistSize = HistBlock + HistSlop,
63 b6afd33e 2003-11-23 devnull HashLog = 13,
64 b6afd33e 2003-11-23 devnull HashSize = 1<<HashLog,
66 b6afd33e 2003-11-23 devnull MaxOffCode = 256, /* biggest offset looked up in direct table */
68 b6afd33e 2003-11-23 devnull EstLitBits = 8,
69 b6afd33e 2003-11-23 devnull EstLenBits = 4,
70 cbeb0b26 2006-04-01 devnull EstOffBits = 5
74 b6afd33e 2003-11-23 devnull * knuth vol. 3 multiplicative hashing
75 b6afd33e 2003-11-23 devnull * each byte x chosen according to rules
76 b6afd33e 2003-11-23 devnull * 1/4 < x < 3/10, 1/3 x < < 3/7, 4/7 < x < 2/3, 7/10 < x < 3/4
77 b6afd33e 2003-11-23 devnull * with reasonable spread between the bytes & their complements
79 b6afd33e 2003-11-23 devnull * the 3 byte value appears to be as almost good as the 4 byte value,
80 b6afd33e 2003-11-23 devnull * and might be faster on some machines
83 00c6cee8 2006-06-07 devnull #define hashit(c) ((u32int)((c) * 0x6b43a9) >> (24 - HashLog))
85 00c6cee8 2006-06-07 devnull #define hashit(c) ((u32int)(((c) & 0xffffff) * 0x6b43a9b5) >> (32 - HashLog))
88 b6afd33e 2003-11-23 devnull * lempel-ziv style compression state
90 b6afd33e 2003-11-23 devnull struct LZstate
92 b6afd33e 2003-11-23 devnull uchar hist[HistSize];
93 b6afd33e 2003-11-23 devnull ulong pos; /* current location in history buffer */
94 b6afd33e 2003-11-23 devnull ulong avail; /* data available after pos */
96 b6afd33e 2003-11-23 devnull ushort hash[HashSize]; /* hash chains */
97 b6afd33e 2003-11-23 devnull ushort nexts[MaxOff];
98 b6afd33e 2003-11-23 devnull int now; /* pos in hash chains */
99 b6afd33e 2003-11-23 devnull int dot; /* dawn of time in history */
100 b6afd33e 2003-11-23 devnull int prevlen; /* lazy matching state */
101 b6afd33e 2003-11-23 devnull int prevoff;
102 b6afd33e 2003-11-23 devnull int maxcheck; /* compressor tuning */
104 b6afd33e 2003-11-23 devnull uchar obuf[DeflateOut];
105 b6afd33e 2003-11-23 devnull uchar *out; /* current position in the output buffer */
106 b6afd33e 2003-11-23 devnull uchar *eout;
107 b6afd33e 2003-11-23 devnull ulong bits; /* bit shift register */
108 b6afd33e 2003-11-23 devnull int nbits;
109 b6afd33e 2003-11-23 devnull int rbad; /* got an error reading the buffer */
110 b6afd33e 2003-11-23 devnull int wbad; /* got an error writing the buffer */
111 b6afd33e 2003-11-23 devnull int (*w)(void*, void*, int);
112 b6afd33e 2003-11-23 devnull void *wr;
114 b6afd33e 2003-11-23 devnull ulong totr; /* total input size */
115 b6afd33e 2003-11-23 devnull ulong totw; /* total output size */
116 b6afd33e 2003-11-23 devnull int debug;
119 b6afd33e 2003-11-23 devnull struct LZblock
121 b6afd33e 2003-11-23 devnull ushort parse[DeflateMaxBlock / 2 + 1];
122 b6afd33e 2003-11-23 devnull int lastv; /* value being constucted for parse */
123 b6afd33e 2003-11-23 devnull ulong litlencount[Nlitlen];
124 b6afd33e 2003-11-23 devnull ulong offcount[Noff];
125 b6afd33e 2003-11-23 devnull ushort *eparse; /* limit for parse table */
126 b6afd33e 2003-11-23 devnull int bytes; /* consumed from the input */
127 b6afd33e 2003-11-23 devnull int excost; /* cost of encoding extra len & off bits */
131 b6afd33e 2003-11-23 devnull * huffman code table
133 b6afd33e 2003-11-23 devnull struct Huff
135 b6afd33e 2003-11-23 devnull short bits; /* length of the code */
136 b6afd33e 2003-11-23 devnull ushort encode; /* the code */
140 b6afd33e 2003-11-23 devnull * encoding of dynamic huffman trees
142 b6afd33e 2003-11-23 devnull struct Dyncode
144 b6afd33e 2003-11-23 devnull int nlit;
145 b6afd33e 2003-11-23 devnull int noff;
146 b6afd33e 2003-11-23 devnull int nclen;
147 b6afd33e 2003-11-23 devnull int ncode;
148 b6afd33e 2003-11-23 devnull Huff codetab[Nclen];
149 b6afd33e 2003-11-23 devnull uchar codes[Nlitlen+Noff];
150 b6afd33e 2003-11-23 devnull uchar codeaux[Nlitlen+Noff];
153 b6afd33e 2003-11-23 devnull static int deflateb(LZstate *lz, LZblock *lzb, void *rr, int (*r)(void*, void*, int));
154 b6afd33e 2003-11-23 devnull static int lzcomp(LZstate*, LZblock*, uchar*, ushort*, int finish);
155 b6afd33e 2003-11-23 devnull static void wrblock(LZstate*, int, ushort*, ushort*, Huff*, Huff*);
156 b6afd33e 2003-11-23 devnull static int bitcost(Huff*, ulong*, int);
157 b6afd33e 2003-11-23 devnull static int huffcodes(Dyncode*, Huff*, Huff*);
158 b6afd33e 2003-11-23 devnull static void wrdyncode(LZstate*, Dyncode*);
159 b6afd33e 2003-11-23 devnull static void lzput(LZstate*, ulong bits, int nbits);
160 b6afd33e 2003-11-23 devnull static void lzflushbits(LZstate*);
161 b6afd33e 2003-11-23 devnull static void lzflush(LZstate *lz);
162 b6afd33e 2003-11-23 devnull static void lzwrite(LZstate *lz, void *buf, int n);
164 b6afd33e 2003-11-23 devnull static int hufftabinit(Huff*, int, ulong*, int);
165 b6afd33e 2003-11-23 devnull static int mkgzprecode(Huff*, ulong *, int, int);
167 b6afd33e 2003-11-23 devnull static int mkprecode(Huff*, ulong *, int, int, ulong*);
168 b6afd33e 2003-11-23 devnull static void nextchain(Chains*, int);
169 b6afd33e 2003-11-23 devnull static void leafsort(ulong*, ushort*, int, int);
171 b6afd33e 2003-11-23 devnull /* conversion from len to code word */
172 b6afd33e 2003-11-23 devnull static int lencode[MaxMatch];
175 b6afd33e 2003-11-23 devnull * conversion from off to code word
176 b6afd33e 2003-11-23 devnull * off <= MaxOffCode ? offcode[off] : bigoffcode[off >> 7]
178 b6afd33e 2003-11-23 devnull static int offcode[MaxOffCode];
179 b6afd33e 2003-11-23 devnull static int bigoffcode[256];
181 b6afd33e 2003-11-23 devnull /* litlen code words LenStart-285 extra bits */
182 b6afd33e 2003-11-23 devnull static int litlenbase[Nlitlen-LenStart];
183 b6afd33e 2003-11-23 devnull static int litlenextra[Nlitlen-LenStart] =
185 b6afd33e 2003-11-23 devnull /* 257 */ 0, 0, 0,
186 b6afd33e 2003-11-23 devnull /* 260 */ 0, 0, 0, 0, 0, 1, 1, 1, 1, 2,
187 b6afd33e 2003-11-23 devnull /* 270 */ 2, 2, 2, 3, 3, 3, 3, 4, 4, 4,
188 b6afd33e 2003-11-23 devnull /* 280 */ 4, 5, 5, 5, 5, 0, 0, 0
191 b6afd33e 2003-11-23 devnull /* offset code word extra bits */
192 b6afd33e 2003-11-23 devnull static int offbase[Noff];
193 b6afd33e 2003-11-23 devnull static int offextra[] =
195 b6afd33e 2003-11-23 devnull 0, 0, 0, 0, 1, 1, 2, 2, 3, 3,
196 b6afd33e 2003-11-23 devnull 4, 4, 5, 5, 6, 6, 7, 7, 8, 8,
197 b6afd33e 2003-11-23 devnull 9, 9, 10, 10, 11, 11, 12, 12, 13, 13,
201 b6afd33e 2003-11-23 devnull /* order code lengths */
202 b6afd33e 2003-11-23 devnull static int clenorder[Nclen] =
204 b6afd33e 2003-11-23 devnull 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
207 b6afd33e 2003-11-23 devnull /* static huffman tables */
208 b6afd33e 2003-11-23 devnull static Huff litlentab[Nlitlen];
209 b6afd33e 2003-11-23 devnull static Huff offtab[Noff];
210 b6afd33e 2003-11-23 devnull static Huff hofftab[Noff];
212 b6afd33e 2003-11-23 devnull /* bit reversal for brain dead endian swap in huffman codes */
213 b6afd33e 2003-11-23 devnull static uchar revtab[256];
214 b6afd33e 2003-11-23 devnull static ulong nlits;
215 b6afd33e 2003-11-23 devnull static ulong nmatches;
218 b6afd33e 2003-11-23 devnull deflateinit(void)
220 b6afd33e 2003-11-23 devnull ulong bitcount[MaxHuffBits];
221 b6afd33e 2003-11-23 devnull int i, j, ci, n;
223 b6afd33e 2003-11-23 devnull /* byte reverse table */
224 b6afd33e 2003-11-23 devnull for(i=0; i<256; i++)
225 b6afd33e 2003-11-23 devnull for(j=0; j<8; j++)
226 b6afd33e 2003-11-23 devnull if(i & (1<<j))
227 b6afd33e 2003-11-23 devnull revtab[i] |= 0x80 >> j;
229 b6afd33e 2003-11-23 devnull /* static Litlen bit lengths */
230 b6afd33e 2003-11-23 devnull for(i=0; i<144; i++)
231 b6afd33e 2003-11-23 devnull litlentab[i].bits = 8;
232 b6afd33e 2003-11-23 devnull for(i=144; i<256; i++)
233 b6afd33e 2003-11-23 devnull litlentab[i].bits = 9;
234 b6afd33e 2003-11-23 devnull for(i=256; i<280; i++)
235 b6afd33e 2003-11-23 devnull litlentab[i].bits = 7;
236 b6afd33e 2003-11-23 devnull for(i=280; i<Nlitlen; i++)
237 b6afd33e 2003-11-23 devnull litlentab[i].bits = 8;
239 b6afd33e 2003-11-23 devnull memset(bitcount, 0, sizeof(bitcount));
240 b6afd33e 2003-11-23 devnull bitcount[8] += 144 - 0;
241 b6afd33e 2003-11-23 devnull bitcount[9] += 256 - 144;
242 b6afd33e 2003-11-23 devnull bitcount[7] += 280 - 256;
243 b6afd33e 2003-11-23 devnull bitcount[8] += Nlitlen - 280;
245 b6afd33e 2003-11-23 devnull if(!hufftabinit(litlentab, Nlitlen, bitcount, 9))
246 b6afd33e 2003-11-23 devnull return FlateInternal;
248 b6afd33e 2003-11-23 devnull /* static offset bit lengths */
249 b6afd33e 2003-11-23 devnull for(i = 0; i < Noff; i++)
250 b6afd33e 2003-11-23 devnull offtab[i].bits = 5;
252 b6afd33e 2003-11-23 devnull memset(bitcount, 0, sizeof(bitcount));
253 b6afd33e 2003-11-23 devnull bitcount[5] = Noff;
255 b6afd33e 2003-11-23 devnull if(!hufftabinit(offtab, Noff, bitcount, 5))
256 b6afd33e 2003-11-23 devnull return FlateInternal;
258 b6afd33e 2003-11-23 devnull bitcount[0] = 0;
259 b6afd33e 2003-11-23 devnull bitcount[1] = 0;
260 b6afd33e 2003-11-23 devnull if(!mkgzprecode(hofftab, bitcount, 2, MaxHuffBits))
261 b6afd33e 2003-11-23 devnull return FlateInternal;
263 b6afd33e 2003-11-23 devnull /* conversion tables for lens & offs to codes */
265 b6afd33e 2003-11-23 devnull for(i = LenStart; i < 286; i++){
266 b6afd33e 2003-11-23 devnull n = ci + (1 << litlenextra[i - LenStart]);
267 b6afd33e 2003-11-23 devnull litlenbase[i - LenStart] = ci;
268 b6afd33e 2003-11-23 devnull for(; ci < n; ci++)
269 b6afd33e 2003-11-23 devnull lencode[ci] = i;
271 b6afd33e 2003-11-23 devnull /* patch up special case for len MaxMatch */
272 b6afd33e 2003-11-23 devnull lencode[MaxMatch-MinMatch] = 285;
273 b6afd33e 2003-11-23 devnull litlenbase[285-LenStart] = MaxMatch-MinMatch;
276 b6afd33e 2003-11-23 devnull for(i = 0; i < 16; i++){
277 b6afd33e 2003-11-23 devnull n = ci + (1 << offextra[i]);
278 b6afd33e 2003-11-23 devnull offbase[i] = ci;
279 b6afd33e 2003-11-23 devnull for(; ci < n; ci++)
280 b6afd33e 2003-11-23 devnull offcode[ci] = i;
283 b6afd33e 2003-11-23 devnull ci = ci >> 7;
284 b6afd33e 2003-11-23 devnull for(; i < 30; i++){
285 b6afd33e 2003-11-23 devnull n = ci + (1 << (offextra[i] - 7));
286 b6afd33e 2003-11-23 devnull offbase[i] = ci << 7;
287 b6afd33e 2003-11-23 devnull for(; ci < n; ci++)
288 b6afd33e 2003-11-23 devnull bigoffcode[ci] = i;
290 b6afd33e 2003-11-23 devnull return FlateOk;
293 b6afd33e 2003-11-23 devnull static void
294 b6afd33e 2003-11-23 devnull deflatereset(LZstate *lz, int level, int debug)
296 b6afd33e 2003-11-23 devnull memset(lz->nexts, 0, sizeof lz->nexts);
297 b6afd33e 2003-11-23 devnull memset(lz->hash, 0, sizeof lz->hash);
298 b6afd33e 2003-11-23 devnull lz->totr = 0;
299 b6afd33e 2003-11-23 devnull lz->totw = 0;
300 b6afd33e 2003-11-23 devnull lz->pos = 0;
301 b6afd33e 2003-11-23 devnull lz->avail = 0;
302 b6afd33e 2003-11-23 devnull lz->out = lz->obuf;
303 b6afd33e 2003-11-23 devnull lz->eout = &lz->obuf[DeflateOut];
304 b6afd33e 2003-11-23 devnull lz->prevlen = MinMatch - 1;
305 b6afd33e 2003-11-23 devnull lz->prevoff = 0;
306 b6afd33e 2003-11-23 devnull lz->now = MaxOff + 1;
307 b6afd33e 2003-11-23 devnull lz->dot = lz->now;
308 b6afd33e 2003-11-23 devnull lz->bits = 0;
309 b6afd33e 2003-11-23 devnull lz->nbits = 0;
310 b6afd33e 2003-11-23 devnull lz->maxcheck = (1 << level);
311 b6afd33e 2003-11-23 devnull lz->maxcheck -= lz->maxcheck >> 2;
312 b6afd33e 2003-11-23 devnull if(lz->maxcheck < 2)
313 b6afd33e 2003-11-23 devnull lz->maxcheck = 2;
314 b6afd33e 2003-11-23 devnull else if(lz->maxcheck > 1024)
315 b6afd33e 2003-11-23 devnull lz->maxcheck = 1024;
317 b6afd33e 2003-11-23 devnull lz->debug = debug;
321 b6afd33e 2003-11-23 devnull deflate(void *wr, int (*w)(void*, void*, int), void *rr, int (*r)(void*, void*, int), int level, int debug)
323 b6afd33e 2003-11-23 devnull LZstate *lz;
324 b6afd33e 2003-11-23 devnull LZblock *lzb;
327 b6afd33e 2003-11-23 devnull lz = malloc(sizeof *lz + sizeof *lzb);
328 b6afd33e 2003-11-23 devnull if(lz == nil)
329 b6afd33e 2003-11-23 devnull return FlateNoMem;
330 b6afd33e 2003-11-23 devnull lzb = (LZblock*)&lz[1];
332 b6afd33e 2003-11-23 devnull deflatereset(lz, level, debug);
333 b6afd33e 2003-11-23 devnull lz->w = w;
334 b6afd33e 2003-11-23 devnull lz->wr = wr;
335 b6afd33e 2003-11-23 devnull lz->wbad = 0;
336 b6afd33e 2003-11-23 devnull lz->rbad = 0;
337 b6afd33e 2003-11-23 devnull lz->eof = 0;
338 b6afd33e 2003-11-23 devnull ok = FlateOk;
339 b6afd33e 2003-11-23 devnull while(!lz->eof || lz->avail){
340 b6afd33e 2003-11-23 devnull ok = deflateb(lz, lzb, rr, r);
341 b6afd33e 2003-11-23 devnull if(ok != FlateOk)
344 b6afd33e 2003-11-23 devnull if(ok == FlateOk && lz->rbad)
345 b6afd33e 2003-11-23 devnull ok = FlateInputFail;
346 b6afd33e 2003-11-23 devnull if(ok == FlateOk && lz->wbad)
347 b6afd33e 2003-11-23 devnull ok = FlateOutputFail;
348 b6afd33e 2003-11-23 devnull free(lz);
349 b6afd33e 2003-11-23 devnull return ok;
352 b6afd33e 2003-11-23 devnull static int
353 b6afd33e 2003-11-23 devnull deflateb(LZstate *lz, LZblock *lzb, void *rr, int (*r)(void*, void*, int))
355 b6afd33e 2003-11-23 devnull Dyncode dyncode, hdyncode;
356 b6afd33e 2003-11-23 devnull Huff dlitlentab[Nlitlen], dofftab[Noff], hlitlentab[Nlitlen];
357 b6afd33e 2003-11-23 devnull ulong litcount[Nlitlen];
358 b6afd33e 2003-11-23 devnull long nunc, ndyn, nfix, nhuff;
359 b6afd33e 2003-11-23 devnull uchar *slop, *hslop;
360 b6afd33e 2003-11-23 devnull ulong ep;
361 b6afd33e 2003-11-23 devnull int i, n, m, mm, nslop;
363 b6afd33e 2003-11-23 devnull memset(lzb->litlencount, 0, sizeof lzb->litlencount);
364 b6afd33e 2003-11-23 devnull memset(lzb->offcount, 0, sizeof lzb->offcount);
365 b6afd33e 2003-11-23 devnull lzb->litlencount[DeflateEob]++;
367 b6afd33e 2003-11-23 devnull lzb->bytes = 0;
368 b6afd33e 2003-11-23 devnull lzb->eparse = lzb->parse;
369 b6afd33e 2003-11-23 devnull lzb->lastv = 0;
370 b6afd33e 2003-11-23 devnull lzb->excost = 0;
372 b6afd33e 2003-11-23 devnull slop = &lz->hist[lz->pos];
373 b6afd33e 2003-11-23 devnull n = lz->avail;
374 b6afd33e 2003-11-23 devnull while(n < DeflateBlock && (!lz->eof || lz->avail)){
376 b6afd33e 2003-11-23 devnull * fill the buffer as much as possible,
377 b6afd33e 2003-11-23 devnull * while leaving room for MaxOff history behind lz->pos,
378 b6afd33e 2003-11-23 devnull * and not reading more than we can handle.
380 b6afd33e 2003-11-23 devnull * make sure we read at least HistSlop bytes.
382 b6afd33e 2003-11-23 devnull if(!lz->eof){
383 b6afd33e 2003-11-23 devnull ep = lz->pos + lz->avail;
384 b6afd33e 2003-11-23 devnull if(ep >= HistBlock)
385 b6afd33e 2003-11-23 devnull ep -= HistBlock;
386 b6afd33e 2003-11-23 devnull m = HistBlock - MaxOff - lz->avail;
387 b6afd33e 2003-11-23 devnull if(m > HistBlock - n)
388 b6afd33e 2003-11-23 devnull m = HistBlock - n;
389 b6afd33e 2003-11-23 devnull if(m > (HistBlock + HistSlop) - ep)
390 b6afd33e 2003-11-23 devnull m = (HistBlock + HistSlop) - ep;
391 b6afd33e 2003-11-23 devnull if(m & ~(BlockSize - 1))
392 b6afd33e 2003-11-23 devnull m &= ~(BlockSize - 1);
395 b6afd33e 2003-11-23 devnull * be nice to the caller: stop reads that are too small.
396 b6afd33e 2003-11-23 devnull * can only get here when we've already filled the buffer some
398 b6afd33e 2003-11-23 devnull if(m < HistSlop){
399 b6afd33e 2003-11-23 devnull if(!m || !lzb->bytes)
400 b6afd33e 2003-11-23 devnull return FlateInternal;
404 b6afd33e 2003-11-23 devnull mm = (*r)(rr, &lz->hist[ep], m);
405 b6afd33e 2003-11-23 devnull if(mm > 0){
407 b6afd33e 2003-11-23 devnull * wrap data to end if we're read it from the beginning
408 b6afd33e 2003-11-23 devnull * this way, we don't have to wrap searches.
410 b6afd33e 2003-11-23 devnull * wrap reads past the end to the beginning.
411 b6afd33e 2003-11-23 devnull * this way, we can guarantee minimum size reads.
413 b6afd33e 2003-11-23 devnull if(ep < HistSlop)
414 b6afd33e 2003-11-23 devnull memmove(&lz->hist[ep + HistBlock], &lz->hist[ep], HistSlop - ep);
415 b6afd33e 2003-11-23 devnull else if(ep + mm > HistBlock)
416 b6afd33e 2003-11-23 devnull memmove(&lz->hist[0], &lz->hist[HistBlock], ep + mm - HistBlock);
418 b6afd33e 2003-11-23 devnull lz->totr += mm;
419 b6afd33e 2003-11-23 devnull n += mm;
420 b6afd33e 2003-11-23 devnull lz->avail += mm;
422 b6afd33e 2003-11-23 devnull if(mm < 0)
423 b6afd33e 2003-11-23 devnull lz->rbad = 1;
424 b6afd33e 2003-11-23 devnull lz->eof = 1;
427 b6afd33e 2003-11-23 devnull ep = lz->pos + lz->avail;
428 b6afd33e 2003-11-23 devnull if(ep > HistSize)
429 b6afd33e 2003-11-23 devnull ep = HistSize;
430 b6afd33e 2003-11-23 devnull if(lzb->bytes + ep - lz->pos > DeflateMaxBlock)
431 b6afd33e 2003-11-23 devnull ep = lz->pos + DeflateMaxBlock - lzb->bytes;
432 b6afd33e 2003-11-23 devnull m = lzcomp(lz, lzb, &lz->hist[ep], lzb->eparse, lz->eof);
433 b6afd33e 2003-11-23 devnull lzb->bytes += m;
434 b6afd33e 2003-11-23 devnull lz->pos = (lz->pos + m) & (HistBlock - 1);
435 b6afd33e 2003-11-23 devnull lz->avail -= m;
437 b6afd33e 2003-11-23 devnull if(lzb->lastv)
438 b6afd33e 2003-11-23 devnull *lzb->eparse++ = lzb->lastv;
439 b6afd33e 2003-11-23 devnull if(lzb->eparse > lzb->parse + nelem(lzb->parse))
440 b6afd33e 2003-11-23 devnull return FlateInternal;
441 b6afd33e 2003-11-23 devnull nunc = lzb->bytes;
443 b6afd33e 2003-11-23 devnull if(!mkgzprecode(dlitlentab, lzb->litlencount, Nlitlen, MaxHuffBits)
444 b6afd33e 2003-11-23 devnull || !mkgzprecode(dofftab, lzb->offcount, Noff, MaxHuffBits))
445 b6afd33e 2003-11-23 devnull return FlateInternal;
447 b6afd33e 2003-11-23 devnull ndyn = huffcodes(&dyncode, dlitlentab, dofftab);
448 b6afd33e 2003-11-23 devnull if(ndyn < 0)
449 b6afd33e 2003-11-23 devnull return FlateInternal;
450 b6afd33e 2003-11-23 devnull ndyn += bitcost(dlitlentab, lzb->litlencount, Nlitlen)
451 b6afd33e 2003-11-23 devnull + bitcost(dofftab, lzb->offcount, Noff)
452 b6afd33e 2003-11-23 devnull + lzb->excost;
454 b6afd33e 2003-11-23 devnull memset(litcount, 0, sizeof litcount);
456 b6afd33e 2003-11-23 devnull nslop = nunc;
457 b6afd33e 2003-11-23 devnull if(nslop > &lz->hist[HistSize] - slop)
458 b6afd33e 2003-11-23 devnull nslop = &lz->hist[HistSize] - slop;
460 b6afd33e 2003-11-23 devnull for(i = 0; i < nslop; i++)
461 b6afd33e 2003-11-23 devnull litcount[slop[i]]++;
462 b6afd33e 2003-11-23 devnull hslop = &lz->hist[HistSlop - nslop];
463 b6afd33e 2003-11-23 devnull for(; i < nunc; i++)
464 b6afd33e 2003-11-23 devnull litcount[hslop[i]]++;
465 b6afd33e 2003-11-23 devnull litcount[DeflateEob]++;
467 b6afd33e 2003-11-23 devnull if(!mkgzprecode(hlitlentab, litcount, Nlitlen, MaxHuffBits))
468 b6afd33e 2003-11-23 devnull return FlateInternal;
469 b6afd33e 2003-11-23 devnull nhuff = huffcodes(&hdyncode, hlitlentab, hofftab);
470 b6afd33e 2003-11-23 devnull if(nhuff < 0)
471 b6afd33e 2003-11-23 devnull return FlateInternal;
472 b6afd33e 2003-11-23 devnull nhuff += bitcost(hlitlentab, litcount, Nlitlen);
474 b6afd33e 2003-11-23 devnull nfix = bitcost(litlentab, lzb->litlencount, Nlitlen)
475 b6afd33e 2003-11-23 devnull + bitcost(offtab, lzb->offcount, Noff)
476 b6afd33e 2003-11-23 devnull + lzb->excost;
478 b6afd33e 2003-11-23 devnull lzput(lz, lz->eof && !lz->avail, 1);
480 b6afd33e 2003-11-23 devnull if(lz->debug){
481 b6afd33e 2003-11-23 devnull fprint(2, "block: bytes=%lud entries=%ld extra bits=%d\n\tuncompressed=%lud fixed=%lud dynamic=%lud huffman=%lud\n",
482 b6afd33e 2003-11-23 devnull nunc, lzb->eparse - lzb->parse, lzb->excost, (nunc + 4) * 8, nfix, ndyn, nhuff);
483 b6afd33e 2003-11-23 devnull fprint(2, "\tnlit=%lud matches=%lud eof=%d\n", nlits, nmatches, lz->eof && !lz->avail);
486 b6afd33e 2003-11-23 devnull if((nunc + 4) * 8 < ndyn && (nunc + 4) * 8 < nfix && (nunc + 4) * 8 < nhuff){
487 b6afd33e 2003-11-23 devnull lzput(lz, DeflateUnc, 2);
488 b6afd33e 2003-11-23 devnull lzflushbits(lz);
490 b6afd33e 2003-11-23 devnull lzput(lz, nunc & 0xff, 8);
491 b6afd33e 2003-11-23 devnull lzput(lz, (nunc >> 8) & 0xff, 8);
492 b6afd33e 2003-11-23 devnull lzput(lz, ~nunc & 0xff, 8);
493 b6afd33e 2003-11-23 devnull lzput(lz, (~nunc >> 8) & 0xff, 8);
494 b6afd33e 2003-11-23 devnull lzflush(lz);
496 b6afd33e 2003-11-23 devnull lzwrite(lz, slop, nslop);
497 b6afd33e 2003-11-23 devnull lzwrite(lz, &lz->hist[HistSlop], nunc - nslop);
498 b6afd33e 2003-11-23 devnull }else if(ndyn < nfix && ndyn < nhuff){
499 b6afd33e 2003-11-23 devnull lzput(lz, DeflateDyn, 2);
501 b6afd33e 2003-11-23 devnull wrdyncode(lz, &dyncode);
502 b6afd33e 2003-11-23 devnull wrblock(lz, slop - lz->hist, lzb->parse, lzb->eparse, dlitlentab, dofftab);
503 b6afd33e 2003-11-23 devnull lzput(lz, dlitlentab[DeflateEob].encode, dlitlentab[DeflateEob].bits);
504 b6afd33e 2003-11-23 devnull }else if(nhuff < nfix){
505 b6afd33e 2003-11-23 devnull lzput(lz, DeflateDyn, 2);
507 b6afd33e 2003-11-23 devnull wrdyncode(lz, &hdyncode);
510 b6afd33e 2003-11-23 devnull for(i = nunc; i > MaxLitRun; i -= MaxLitRun)
511 b6afd33e 2003-11-23 devnull lzb->parse[m++] = MaxLitRun;
512 b6afd33e 2003-11-23 devnull lzb->parse[m++] = i;
514 b6afd33e 2003-11-23 devnull wrblock(lz, slop - lz->hist, lzb->parse, lzb->parse + m, hlitlentab, hofftab);
515 b6afd33e 2003-11-23 devnull lzput(lz, hlitlentab[DeflateEob].encode, hlitlentab[DeflateEob].bits);
517 b6afd33e 2003-11-23 devnull lzput(lz, DeflateFix, 2);
519 b6afd33e 2003-11-23 devnull wrblock(lz, slop - lz->hist, lzb->parse, lzb->eparse, litlentab, offtab);
520 b6afd33e 2003-11-23 devnull lzput(lz, litlentab[DeflateEob].encode, litlentab[DeflateEob].bits);
523 b6afd33e 2003-11-23 devnull if(lz->eof && !lz->avail){
524 b6afd33e 2003-11-23 devnull lzflushbits(lz);
525 b6afd33e 2003-11-23 devnull lzflush(lz);
527 b6afd33e 2003-11-23 devnull return FlateOk;
530 b6afd33e 2003-11-23 devnull static void
531 b6afd33e 2003-11-23 devnull lzwrite(LZstate *lz, void *buf, int n)
535 b6afd33e 2003-11-23 devnull if(n && lz->w){
536 b6afd33e 2003-11-23 devnull nw = (*lz->w)(lz->wr, buf, n);
537 b6afd33e 2003-11-23 devnull if(nw != n){
538 a0f1e21f 2004-04-20 devnull lz->w = 0;
539 b6afd33e 2003-11-23 devnull lz->wbad = 1;
541 b6afd33e 2003-11-23 devnull lz->totw += n;
545 b6afd33e 2003-11-23 devnull static void
546 b6afd33e 2003-11-23 devnull lzflush(LZstate *lz)
548 b6afd33e 2003-11-23 devnull lzwrite(lz, lz->obuf, lz->out - lz->obuf);
549 b6afd33e 2003-11-23 devnull lz->out = lz->obuf;
552 b6afd33e 2003-11-23 devnull static void
553 b6afd33e 2003-11-23 devnull lzput(LZstate *lz, ulong bits, int nbits)
555 b6afd33e 2003-11-23 devnull bits = (bits << lz->nbits) | lz->bits;
556 b6afd33e 2003-11-23 devnull for(nbits += lz->nbits; nbits >= 8; nbits -= 8){
557 b6afd33e 2003-11-23 devnull *lz->out++ = bits;
558 b6afd33e 2003-11-23 devnull if(lz->out == lz->eout)
559 b6afd33e 2003-11-23 devnull lzflush(lz);
560 b6afd33e 2003-11-23 devnull bits >>= 8;
562 b6afd33e 2003-11-23 devnull lz->bits = bits;
563 b6afd33e 2003-11-23 devnull lz->nbits = nbits;
566 b6afd33e 2003-11-23 devnull static void
567 b6afd33e 2003-11-23 devnull lzflushbits(LZstate *lz)
569 b6afd33e 2003-11-23 devnull if(lz->nbits)
570 b6afd33e 2003-11-23 devnull lzput(lz, 0, 8 - (lz->nbits & 7));
574 b6afd33e 2003-11-23 devnull * write out a block of n samples,
575 b6afd33e 2003-11-23 devnull * given lz encoding and counts for huffman tables
577 b6afd33e 2003-11-23 devnull static void
578 b6afd33e 2003-11-23 devnull wrblock(LZstate *out, int litoff, ushort *soff, ushort *eoff, Huff *litlentab, Huff *offtab)
580 b6afd33e 2003-11-23 devnull ushort *off;
581 b6afd33e 2003-11-23 devnull int i, run, offset, lit, len, c;
583 b6afd33e 2003-11-23 devnull if(out->debug > 2){
584 b6afd33e 2003-11-23 devnull for(off = soff; off < eoff; ){
585 b6afd33e 2003-11-23 devnull offset = *off++;
586 b6afd33e 2003-11-23 devnull run = offset & MaxLitRun;
587 b6afd33e 2003-11-23 devnull if(run){
588 b6afd33e 2003-11-23 devnull for(i = 0; i < run; i++){
589 b6afd33e 2003-11-23 devnull lit = out->hist[litoff & (HistBlock - 1)];
590 b6afd33e 2003-11-23 devnull litoff++;
591 b6afd33e 2003-11-23 devnull fprint(2, "\tlit %.2ux %c\n", lit, lit);
593 b6afd33e 2003-11-23 devnull if(!(offset & LenFlag))
594 b6afd33e 2003-11-23 devnull continue;
595 b6afd33e 2003-11-23 devnull len = offset >> LenShift;
596 b6afd33e 2003-11-23 devnull offset = *off++;
597 b6afd33e 2003-11-23 devnull }else if(offset & LenFlag){
598 b6afd33e 2003-11-23 devnull len = offset >> LenShift;
599 b6afd33e 2003-11-23 devnull offset = *off++;
601 b6afd33e 2003-11-23 devnull len = 0;
602 b6afd33e 2003-11-23 devnull offset >>= LenShift;
604 b6afd33e 2003-11-23 devnull litoff += len + MinMatch;
605 b6afd33e 2003-11-23 devnull fprint(2, "\t<%d, %d>\n", offset + 1, len + MinMatch);
609 b6afd33e 2003-11-23 devnull for(off = soff; off < eoff; ){
610 b6afd33e 2003-11-23 devnull offset = *off++;
611 b6afd33e 2003-11-23 devnull run = offset & MaxLitRun;
612 b6afd33e 2003-11-23 devnull if(run){
613 b6afd33e 2003-11-23 devnull for(i = 0; i < run; i++){
614 b6afd33e 2003-11-23 devnull lit = out->hist[litoff & (HistBlock - 1)];
615 b6afd33e 2003-11-23 devnull litoff++;
616 b6afd33e 2003-11-23 devnull lzput(out, litlentab[lit].encode, litlentab[lit].bits);
618 b6afd33e 2003-11-23 devnull if(!(offset & LenFlag))
619 b6afd33e 2003-11-23 devnull continue;
620 b6afd33e 2003-11-23 devnull len = offset >> LenShift;
621 b6afd33e 2003-11-23 devnull offset = *off++;
622 b6afd33e 2003-11-23 devnull }else if(offset & LenFlag){
623 b6afd33e 2003-11-23 devnull len = offset >> LenShift;
624 b6afd33e 2003-11-23 devnull offset = *off++;
626 b6afd33e 2003-11-23 devnull len = 0;
627 b6afd33e 2003-11-23 devnull offset >>= LenShift;
629 b6afd33e 2003-11-23 devnull litoff += len + MinMatch;
630 b6afd33e 2003-11-23 devnull c = lencode[len];
631 b6afd33e 2003-11-23 devnull lzput(out, litlentab[c].encode, litlentab[c].bits);
632 b6afd33e 2003-11-23 devnull c -= LenStart;
633 b6afd33e 2003-11-23 devnull if(litlenextra[c])
634 b6afd33e 2003-11-23 devnull lzput(out, len - litlenbase[c], litlenextra[c]);
636 b6afd33e 2003-11-23 devnull if(offset < MaxOffCode)
637 b6afd33e 2003-11-23 devnull c = offcode[offset];
639 b6afd33e 2003-11-23 devnull c = bigoffcode[offset >> 7];
640 b6afd33e 2003-11-23 devnull lzput(out, offtab[c].encode, offtab[c].bits);
641 b6afd33e 2003-11-23 devnull if(offextra[c])
642 b6afd33e 2003-11-23 devnull lzput(out, offset - offbase[c], offextra[c]);
647 b6afd33e 2003-11-23 devnull * look for the longest, closest string which matches
648 b6afd33e 2003-11-23 devnull * the next prefix. the clever part here is looking for
649 b6afd33e 2003-11-23 devnull * a string 1 longer than the previous best match.
651 b6afd33e 2003-11-23 devnull * follows the recommendation of limiting number of chains
652 b6afd33e 2003-11-23 devnull * which are checked. this appears to be the best heuristic.
654 b6afd33e 2003-11-23 devnull static int
655 b6afd33e 2003-11-23 devnull lzmatch(int now, int then, uchar *p, uchar *es, ushort *nexts, uchar *hist, int runlen, int check, int *m)
657 b6afd33e 2003-11-23 devnull uchar *s, *t;
658 b6afd33e 2003-11-23 devnull int ml, off, last;
660 b6afd33e 2003-11-23 devnull ml = check;
661 b6afd33e 2003-11-23 devnull if(runlen >= 8)
662 b6afd33e 2003-11-23 devnull check >>= 2;
664 b6afd33e 2003-11-23 devnull if(p + runlen >= es)
665 b6afd33e 2003-11-23 devnull return runlen;
666 b6afd33e 2003-11-23 devnull last = 0;
667 b6afd33e 2003-11-23 devnull for(; check-- > 0; then = nexts[then & (MaxOff-1)]){
668 b6afd33e 2003-11-23 devnull off = (ushort)(now - then);
669 b6afd33e 2003-11-23 devnull if(off <= last || off > MaxOff)
671 b6afd33e 2003-11-23 devnull s = p + runlen;
672 b6afd33e 2003-11-23 devnull t = hist + (((p - hist) - off) & (HistBlock-1));
673 b6afd33e 2003-11-23 devnull t += runlen;
674 b6afd33e 2003-11-23 devnull for(; s >= p; s--){
675 b6afd33e 2003-11-23 devnull if(*s != *t)
676 b6afd33e 2003-11-23 devnull goto matchloop;
681 b6afd33e 2003-11-23 devnull * we have a new best match.
682 b6afd33e 2003-11-23 devnull * extend it to it's maximum length
684 b6afd33e 2003-11-23 devnull t += runlen + 2;
685 b6afd33e 2003-11-23 devnull s += runlen + 2;
686 b6afd33e 2003-11-23 devnull for(; s < es; s++){
687 b6afd33e 2003-11-23 devnull if(*s != *t)
691 b6afd33e 2003-11-23 devnull runlen = s - p;
692 b6afd33e 2003-11-23 devnull *m = off - 1;
693 b6afd33e 2003-11-23 devnull if(s == es || runlen > ml)
695 b6afd33e 2003-11-23 devnull matchloop:;
696 b6afd33e 2003-11-23 devnull last = off;
698 b6afd33e 2003-11-23 devnull return runlen;
701 b6afd33e 2003-11-23 devnull static int
702 b6afd33e 2003-11-23 devnull lzcomp(LZstate *lz, LZblock *lzb, uchar *ep, ushort *parse, int finish)
704 b6afd33e 2003-11-23 devnull ulong cont, excost, *litlencount, *offcount;
705 b6afd33e 2003-11-23 devnull uchar *p, *q, *s, *es;
706 b6afd33e 2003-11-23 devnull ushort *nexts, *hash;
707 b6afd33e 2003-11-23 devnull int v, i, h, runlen, n, now, then, m, prevlen, prevoff, maxdefer;
709 b6afd33e 2003-11-23 devnull litlencount = lzb->litlencount;
710 b6afd33e 2003-11-23 devnull offcount = lzb->offcount;
711 b6afd33e 2003-11-23 devnull nexts = lz->nexts;
712 b6afd33e 2003-11-23 devnull hash = lz->hash;
713 b6afd33e 2003-11-23 devnull now = lz->now;
715 b6afd33e 2003-11-23 devnull p = &lz->hist[lz->pos];
716 b6afd33e 2003-11-23 devnull if(lz->prevlen != MinMatch - 1)
720 b6afd33e 2003-11-23 devnull * hash in the links for any hanging link positions,
721 b6afd33e 2003-11-23 devnull * and calculate the hash for the current position.
723 b6afd33e 2003-11-23 devnull n = MinMatch;
724 b6afd33e 2003-11-23 devnull if(n > ep - p)
725 b6afd33e 2003-11-23 devnull n = ep - p;
726 b6afd33e 2003-11-23 devnull cont = 0;
727 b6afd33e 2003-11-23 devnull for(i = 0; i < n - 1; i++){
728 b6afd33e 2003-11-23 devnull m = now - ((MinMatch-1) - i);
729 b6afd33e 2003-11-23 devnull if(m < lz->dot)
730 b6afd33e 2003-11-23 devnull continue;
731 b6afd33e 2003-11-23 devnull s = lz->hist + (((p - lz->hist) - (now - m)) & (HistBlock-1));
733 b6afd33e 2003-11-23 devnull cont = (s[0] << 16) | (s[1] << 8) | s[2];
734 b6afd33e 2003-11-23 devnull h = hashit(cont);
735 b6afd33e 2003-11-23 devnull prevoff = 0;
736 b6afd33e 2003-11-23 devnull for(then = hash[h]; ; then = nexts[then & (MaxOff-1)]){
737 b6afd33e 2003-11-23 devnull v = (ushort)(now - then);
738 b6afd33e 2003-11-23 devnull if(v <= prevoff || v >= (MinMatch-1) - i)
740 b6afd33e 2003-11-23 devnull prevoff = v;
742 b6afd33e 2003-11-23 devnull if(then == (ushort)m)
743 b6afd33e 2003-11-23 devnull continue;
744 b6afd33e 2003-11-23 devnull nexts[m & (MaxOff-1)] = hash[h];
745 b6afd33e 2003-11-23 devnull hash[h] = m;
747 b6afd33e 2003-11-23 devnull for(i = 0; i < n; i++)
748 b6afd33e 2003-11-23 devnull cont = (cont << 8) | p[i];
751 b6afd33e 2003-11-23 devnull * now must point to the index in the nexts array
752 b6afd33e 2003-11-23 devnull * corresponding to p's position in the history
754 b6afd33e 2003-11-23 devnull prevlen = lz->prevlen;
755 b6afd33e 2003-11-23 devnull prevoff = lz->prevoff;
756 b6afd33e 2003-11-23 devnull maxdefer = lz->maxcheck >> 2;
757 b6afd33e 2003-11-23 devnull excost = 0;
758 b6afd33e 2003-11-23 devnull v = lzb->lastv;
759 b6afd33e 2003-11-23 devnull for(;;){
760 b6afd33e 2003-11-23 devnull es = p + MaxMatch;
761 b6afd33e 2003-11-23 devnull if(es > ep){
762 b6afd33e 2003-11-23 devnull if(!finish || p >= ep)
764 b6afd33e 2003-11-23 devnull es = ep;
767 b6afd33e 2003-11-23 devnull h = hashit(cont);
768 b6afd33e 2003-11-23 devnull runlen = lzmatch(now, hash[h], p, es, nexts, lz->hist, prevlen, lz->maxcheck, &m);
771 b6afd33e 2003-11-23 devnull * back out of small matches too far in the past
773 b6afd33e 2003-11-23 devnull if(runlen == MinMatch && m >= MinMatchMaxOff){
774 b6afd33e 2003-11-23 devnull runlen = MinMatch - 1;
779 b6afd33e 2003-11-23 devnull * record the encoding and increment counts for huffman trees
780 b6afd33e 2003-11-23 devnull * if we get a match, defer selecting it until we check for
781 b6afd33e 2003-11-23 devnull * a longer match at the next position.
783 b6afd33e 2003-11-23 devnull if(prevlen >= runlen && prevlen != MinMatch - 1){
785 b6afd33e 2003-11-23 devnull * old match at least as good; use that one
787 b6afd33e 2003-11-23 devnull n = prevlen - MinMatch;
788 b6afd33e 2003-11-23 devnull if(v || n){
789 b6afd33e 2003-11-23 devnull *parse++ = v | LenFlag | (n << LenShift);
790 b6afd33e 2003-11-23 devnull *parse++ = prevoff;
792 b6afd33e 2003-11-23 devnull *parse++ = prevoff << LenShift;
795 b6afd33e 2003-11-23 devnull n = lencode[n];
796 b6afd33e 2003-11-23 devnull litlencount[n]++;
797 b6afd33e 2003-11-23 devnull excost += litlenextra[n - LenStart];
799 b6afd33e 2003-11-23 devnull if(prevoff < MaxOffCode)
800 b6afd33e 2003-11-23 devnull n = offcode[prevoff];
802 b6afd33e 2003-11-23 devnull n = bigoffcode[prevoff >> 7];
803 b6afd33e 2003-11-23 devnull offcount[n]++;
804 b6afd33e 2003-11-23 devnull excost += offextra[n];
806 b6afd33e 2003-11-23 devnull runlen = prevlen - 1;
807 b6afd33e 2003-11-23 devnull prevlen = MinMatch - 1;
808 b6afd33e 2003-11-23 devnull nmatches++;
809 b6afd33e 2003-11-23 devnull }else if(runlen == MinMatch - 1){
811 b6afd33e 2003-11-23 devnull * no match; just put out the literal
813 b6afd33e 2003-11-23 devnull if(++v == MaxLitRun){
814 b6afd33e 2003-11-23 devnull *parse++ = v;
817 b6afd33e 2003-11-23 devnull litlencount[*p]++;
818 b6afd33e 2003-11-23 devnull nlits++;
819 b6afd33e 2003-11-23 devnull runlen = 1;
821 b6afd33e 2003-11-23 devnull if(prevlen != MinMatch - 1){
823 b6afd33e 2003-11-23 devnull * longer match now. output previous literal,
824 b6afd33e 2003-11-23 devnull * update current match, and try again
826 b6afd33e 2003-11-23 devnull if(++v == MaxLitRun){
827 b6afd33e 2003-11-23 devnull *parse++ = v;
830 b6afd33e 2003-11-23 devnull litlencount[p[-1]]++;
831 b6afd33e 2003-11-23 devnull nlits++;
834 b6afd33e 2003-11-23 devnull prevoff = m;
836 b6afd33e 2003-11-23 devnull if(runlen < maxdefer){
837 b6afd33e 2003-11-23 devnull prevlen = runlen;
838 b6afd33e 2003-11-23 devnull runlen = 1;
840 b6afd33e 2003-11-23 devnull n = runlen - MinMatch;
841 b6afd33e 2003-11-23 devnull if(v || n){
842 b6afd33e 2003-11-23 devnull *parse++ = v | LenFlag | (n << LenShift);
843 b6afd33e 2003-11-23 devnull *parse++ = prevoff;
845 b6afd33e 2003-11-23 devnull *parse++ = prevoff << LenShift;
848 b6afd33e 2003-11-23 devnull n = lencode[n];
849 b6afd33e 2003-11-23 devnull litlencount[n]++;
850 b6afd33e 2003-11-23 devnull excost += litlenextra[n - LenStart];
852 b6afd33e 2003-11-23 devnull if(prevoff < MaxOffCode)
853 b6afd33e 2003-11-23 devnull n = offcode[prevoff];
855 b6afd33e 2003-11-23 devnull n = bigoffcode[prevoff >> 7];
856 b6afd33e 2003-11-23 devnull offcount[n]++;
857 b6afd33e 2003-11-23 devnull excost += offextra[n];
859 b6afd33e 2003-11-23 devnull prevlen = MinMatch - 1;
860 b6afd33e 2003-11-23 devnull nmatches++;
865 b6afd33e 2003-11-23 devnull * update the hash for the newly matched data
866 b6afd33e 2003-11-23 devnull * this is constructed so the link for the old
867 b6afd33e 2003-11-23 devnull * match in this position must be at the end of a chain,
868 b6afd33e 2003-11-23 devnull * and will expire when this match is added, ie it will
869 b6afd33e 2003-11-23 devnull * never be examined by the match loop.
870 b6afd33e 2003-11-23 devnull * add to the hash chain only if we have the real hash data.
872 b6afd33e 2003-11-23 devnull for(q = p + runlen; p != q; p++){
873 b6afd33e 2003-11-23 devnull if(p + MinMatch <= ep){
874 b6afd33e 2003-11-23 devnull h = hashit(cont);
875 b6afd33e 2003-11-23 devnull nexts[now & (MaxOff-1)] = hash[h];
876 b6afd33e 2003-11-23 devnull hash[h] = now;
877 b6afd33e 2003-11-23 devnull if(p + MinMatch < ep)
878 b6afd33e 2003-11-23 devnull cont = (cont << 8) | p[MinMatch];
885 b6afd33e 2003-11-23 devnull * we can just store away the lazy state and
886 b6afd33e 2003-11-23 devnull * pick it up next time. the last block will have finish set
887 b6afd33e 2003-11-23 devnull * so we won't have any pending matches
888 b6afd33e 2003-11-23 devnull * however, we need to correct for how much we've encoded
890 b6afd33e 2003-11-23 devnull if(prevlen != MinMatch - 1)
893 b6afd33e 2003-11-23 devnull lzb->excost += excost;
894 b6afd33e 2003-11-23 devnull lzb->eparse = parse;
895 b6afd33e 2003-11-23 devnull lzb->lastv = v;
897 b6afd33e 2003-11-23 devnull lz->now = now;
898 b6afd33e 2003-11-23 devnull lz->prevlen = prevlen;
899 b6afd33e 2003-11-23 devnull lz->prevoff = prevoff;
901 b6afd33e 2003-11-23 devnull return p - &lz->hist[lz->pos];
905 b6afd33e 2003-11-23 devnull * make up the dynamic code tables, and return the number of bits
906 b6afd33e 2003-11-23 devnull * needed to transmit them.
908 b6afd33e 2003-11-23 devnull static int
909 b6afd33e 2003-11-23 devnull huffcodes(Dyncode *dc, Huff *littab, Huff *offtab)
911 b6afd33e 2003-11-23 devnull Huff *codetab;
912 b6afd33e 2003-11-23 devnull uchar *codes, *codeaux;
913 b6afd33e 2003-11-23 devnull ulong codecount[Nclen], excost;
914 b6afd33e 2003-11-23 devnull int i, n, m, v, c, nlit, noff, ncode, nclen;
916 b6afd33e 2003-11-23 devnull codetab = dc->codetab;
917 b6afd33e 2003-11-23 devnull codes = dc->codes;
918 b6afd33e 2003-11-23 devnull codeaux = dc->codeaux;
921 b6afd33e 2003-11-23 devnull * trim the sizes of the tables
923 b6afd33e 2003-11-23 devnull for(nlit = Nlitlen; nlit > 257 && littab[nlit-1].bits == 0; nlit--)
925 b6afd33e 2003-11-23 devnull for(noff = Noff; noff > 1 && offtab[noff-1].bits == 0; noff--)
929 b6afd33e 2003-11-23 devnull * make the code-length code
931 b6afd33e 2003-11-23 devnull for(i = 0; i < nlit; i++)
932 b6afd33e 2003-11-23 devnull codes[i] = littab[i].bits;
933 b6afd33e 2003-11-23 devnull for(i = 0; i < noff; i++)
934 b6afd33e 2003-11-23 devnull codes[i + nlit] = offtab[i].bits;
937 b6afd33e 2003-11-23 devnull * run-length compress the code-length code
939 b6afd33e 2003-11-23 devnull excost = 0;
941 b6afd33e 2003-11-23 devnull ncode = nlit+noff;
942 b6afd33e 2003-11-23 devnull for(i = 0; i < ncode; ){
943 b6afd33e 2003-11-23 devnull n = i + 1;
944 b6afd33e 2003-11-23 devnull v = codes[i];
945 b6afd33e 2003-11-23 devnull while(n < ncode && v == codes[n])
949 b6afd33e 2003-11-23 devnull if(v == 0){
950 b6afd33e 2003-11-23 devnull while(n >= 11){
952 b6afd33e 2003-11-23 devnull if(m > 138)
953 b6afd33e 2003-11-23 devnull m = 138;
954 b6afd33e 2003-11-23 devnull codes[c] = 18;
955 b6afd33e 2003-11-23 devnull codeaux[c++] = m - 11;
957 b6afd33e 2003-11-23 devnull excost += 7;
959 b6afd33e 2003-11-23 devnull if(n >= 3){
960 b6afd33e 2003-11-23 devnull codes[c] = 17;
961 b6afd33e 2003-11-23 devnull codeaux[c++] = n - 3;
963 b6afd33e 2003-11-23 devnull excost += 3;
966 b6afd33e 2003-11-23 devnull while(n--){
967 b6afd33e 2003-11-23 devnull codes[c++] = v;
968 b6afd33e 2003-11-23 devnull while(n >= 3){
970 b6afd33e 2003-11-23 devnull if(m > 6)
972 b6afd33e 2003-11-23 devnull codes[c] = 16;
973 b6afd33e 2003-11-23 devnull codeaux[c++] = m - 3;
975 b6afd33e 2003-11-23 devnull excost += 3;
980 b6afd33e 2003-11-23 devnull memset(codecount, 0, sizeof codecount);
981 b6afd33e 2003-11-23 devnull for(i = 0; i < c; i++)
982 b6afd33e 2003-11-23 devnull codecount[codes[i]]++;
983 b6afd33e 2003-11-23 devnull if(!mkgzprecode(codetab, codecount, Nclen, 8))
984 b6afd33e 2003-11-23 devnull return -1;
986 b6afd33e 2003-11-23 devnull for(nclen = Nclen; nclen > 4 && codetab[clenorder[nclen-1]].bits == 0; nclen--)
989 b6afd33e 2003-11-23 devnull dc->nlit = nlit;
990 b6afd33e 2003-11-23 devnull dc->noff = noff;
991 b6afd33e 2003-11-23 devnull dc->nclen = nclen;
992 b6afd33e 2003-11-23 devnull dc->ncode = c;
994 b6afd33e 2003-11-23 devnull return 5 + 5 + 4 + nclen * 3 + bitcost(codetab, codecount, Nclen) + excost;
997 b6afd33e 2003-11-23 devnull static void
998 b6afd33e 2003-11-23 devnull wrdyncode(LZstate *out, Dyncode *dc)
1000 b6afd33e 2003-11-23 devnull Huff *codetab;
1001 b6afd33e 2003-11-23 devnull uchar *codes, *codeaux;
1002 b6afd33e 2003-11-23 devnull int i, v, c;
1005 b6afd33e 2003-11-23 devnull * write out header, then code length code lengths,
1006 b6afd33e 2003-11-23 devnull * and code lengths
1008 b6afd33e 2003-11-23 devnull lzput(out, dc->nlit-257, 5);
1009 b6afd33e 2003-11-23 devnull lzput(out, dc->noff-1, 5);
1010 b6afd33e 2003-11-23 devnull lzput(out, dc->nclen-4, 4);
1012 b6afd33e 2003-11-23 devnull codetab = dc->codetab;
1013 b6afd33e 2003-11-23 devnull for(i = 0; i < dc->nclen; i++)
1014 b6afd33e 2003-11-23 devnull lzput(out, codetab[clenorder[i]].bits, 3);
1016 b6afd33e 2003-11-23 devnull codes = dc->codes;
1017 b6afd33e 2003-11-23 devnull codeaux = dc->codeaux;
1018 b6afd33e 2003-11-23 devnull c = dc->ncode;
1019 b6afd33e 2003-11-23 devnull for(i = 0; i < c; i++){
1020 b6afd33e 2003-11-23 devnull v = codes[i];
1021 b6afd33e 2003-11-23 devnull lzput(out, codetab[v].encode, codetab[v].bits);
1022 b6afd33e 2003-11-23 devnull if(v >= 16){
1023 b6afd33e 2003-11-23 devnull if(v == 16)
1024 b6afd33e 2003-11-23 devnull lzput(out, codeaux[i], 2);
1025 b6afd33e 2003-11-23 devnull else if(v == 17)
1026 b6afd33e 2003-11-23 devnull lzput(out, codeaux[i], 3);
1027 b6afd33e 2003-11-23 devnull else /* v == 18 */
1028 b6afd33e 2003-11-23 devnull lzput(out, codeaux[i], 7);
1033 b6afd33e 2003-11-23 devnull static int
1034 b6afd33e 2003-11-23 devnull bitcost(Huff *tab, ulong *count, int n)
1036 b6afd33e 2003-11-23 devnull ulong tot;
1039 b6afd33e 2003-11-23 devnull tot = 0;
1040 b6afd33e 2003-11-23 devnull for(i = 0; i < n; i++)
1041 b6afd33e 2003-11-23 devnull tot += count[i] * tab[i].bits;
1042 b6afd33e 2003-11-23 devnull return tot;
1045 b6afd33e 2003-11-23 devnull static int
1046 b6afd33e 2003-11-23 devnull mkgzprecode(Huff *tab, ulong *count, int n, int maxbits)
1048 b6afd33e 2003-11-23 devnull ulong bitcount[MaxHuffBits];
1049 b6afd33e 2003-11-23 devnull int i, nbits;
1051 b6afd33e 2003-11-23 devnull nbits = mkprecode(tab, count, n, maxbits, bitcount);
1052 b6afd33e 2003-11-23 devnull for(i = 0; i < n; i++){
1053 b6afd33e 2003-11-23 devnull if(tab[i].bits == -1)
1054 b6afd33e 2003-11-23 devnull tab[i].bits = 0;
1055 b6afd33e 2003-11-23 devnull else if(tab[i].bits == 0){
1056 b6afd33e 2003-11-23 devnull if(nbits != 0 || bitcount[0] != 1)
1057 b6afd33e 2003-11-23 devnull return 0;
1058 b6afd33e 2003-11-23 devnull bitcount[1] = 1;
1059 b6afd33e 2003-11-23 devnull bitcount[0] = 0;
1060 b6afd33e 2003-11-23 devnull nbits = 1;
1061 b6afd33e 2003-11-23 devnull tab[i].bits = 1;
1064 b6afd33e 2003-11-23 devnull if(bitcount[0] != 0)
1065 b6afd33e 2003-11-23 devnull return 0;
1066 b6afd33e 2003-11-23 devnull return hufftabinit(tab, n, bitcount, nbits);
1069 b6afd33e 2003-11-23 devnull static int
1070 b6afd33e 2003-11-23 devnull hufftabinit(Huff *tab, int n, ulong *bitcount, int nbits)
1072 b6afd33e 2003-11-23 devnull ulong code, nc[MaxHuffBits];
1073 b6afd33e 2003-11-23 devnull int i, bits;
1075 b6afd33e 2003-11-23 devnull code = 0;
1076 b6afd33e 2003-11-23 devnull for(bits = 1; bits <= nbits; bits++){
1077 b6afd33e 2003-11-23 devnull code = (code + bitcount[bits-1]) << 1;
1078 b6afd33e 2003-11-23 devnull nc[bits] = code;
1081 b6afd33e 2003-11-23 devnull for(i = 0; i < n; i++){
1082 b6afd33e 2003-11-23 devnull bits = tab[i].bits;
1083 b6afd33e 2003-11-23 devnull if(bits){
1084 b6afd33e 2003-11-23 devnull code = nc[bits]++ << (16 - bits);
1085 b6afd33e 2003-11-23 devnull if(code & ~0xffff)
1086 b6afd33e 2003-11-23 devnull return 0;
1087 b6afd33e 2003-11-23 devnull tab[i].encode = revtab[code >> 8] | (revtab[code & 0xff] << 8);
1090 b6afd33e 2003-11-23 devnull return 1;
1095 b6afd33e 2003-11-23 devnull * this should be in a library
1097 b6afd33e 2003-11-23 devnull struct Chain
1099 b6afd33e 2003-11-23 devnull ulong count; /* occurances of everything in the chain */
1100 b6afd33e 2003-11-23 devnull ushort leaf; /* leaves to the left of chain, or leaf value */
1101 b6afd33e 2003-11-23 devnull char col; /* ref count for collecting unused chains */
1102 b6afd33e 2003-11-23 devnull char gen; /* need to generate chains for next lower level */
1103 b6afd33e 2003-11-23 devnull Chain *up; /* Chain up in the lists */
1106 b6afd33e 2003-11-23 devnull struct Chains
1108 b6afd33e 2003-11-23 devnull Chain *lists[(MaxHuffBits - 1) * 2];
1109 b6afd33e 2003-11-23 devnull ulong leafcount[MaxLeaf]; /* sorted list of leaf counts */
1110 b6afd33e 2003-11-23 devnull ushort leafmap[MaxLeaf]; /* map to actual leaf number */
1111 b6afd33e 2003-11-23 devnull int nleaf; /* number of leaves */
1112 b6afd33e 2003-11-23 devnull Chain chains[ChainMem];
1113 b6afd33e 2003-11-23 devnull Chain *echains;
1114 b6afd33e 2003-11-23 devnull Chain *free;
1115 b6afd33e 2003-11-23 devnull char col;
1116 b6afd33e 2003-11-23 devnull int nlists;
1120 b6afd33e 2003-11-23 devnull * fast, low space overhead algorithm for max depth huffman type codes
1122 b6afd33e 2003-11-23 devnull * J. Katajainen, A. Moffat and A. Turpin, "A fast and space-economical
1123 b6afd33e 2003-11-23 devnull * algorithm for length-limited coding," Proc. Intl. Symp. on Algorithms
1124 b6afd33e 2003-11-23 devnull * and Computation, Cairns, Australia, Dec. 1995, Lecture Notes in Computer
1125 b6afd33e 2003-11-23 devnull * Science, Vol 1004, J. Staples, P. Eades, N. Katoh, and A. Moffat, eds.,
1126 b6afd33e 2003-11-23 devnull * pp 12-21, Springer Verlag, New York, 1995.
1128 b6afd33e 2003-11-23 devnull static int
1129 b6afd33e 2003-11-23 devnull mkprecode(Huff *tab, ulong *count, int n, int maxbits, ulong *bitcount)
1131 b6afd33e 2003-11-23 devnull Chains cs;
1132 b6afd33e 2003-11-23 devnull Chain *c;
1133 b6afd33e 2003-11-23 devnull int i, m, em, bits;
1135 995e5709 2009-04-30 rsc memset(&cs, 0, sizeof cs);
1138 b6afd33e 2003-11-23 devnull * set up the sorted list of leaves
1141 b6afd33e 2003-11-23 devnull for(i = 0; i < n; i++){
1142 b6afd33e 2003-11-23 devnull tab[i].bits = -1;
1143 b6afd33e 2003-11-23 devnull tab[i].encode = 0;
1144 b6afd33e 2003-11-23 devnull if(count[i] != 0){
1145 b6afd33e 2003-11-23 devnull cs.leafcount[m] = count[i];
1146 b6afd33e 2003-11-23 devnull cs.leafmap[m] = i;
1150 b6afd33e 2003-11-23 devnull if(m < 2){
1151 b6afd33e 2003-11-23 devnull if(m != 0){
1152 b6afd33e 2003-11-23 devnull tab[cs.leafmap[0]].bits = 0;
1153 b6afd33e 2003-11-23 devnull bitcount[0] = 1;
1155 b6afd33e 2003-11-23 devnull bitcount[0] = 0;
1156 b6afd33e 2003-11-23 devnull return 0;
1158 b6afd33e 2003-11-23 devnull cs.nleaf = m;
1159 b6afd33e 2003-11-23 devnull leafsort(cs.leafcount, cs.leafmap, 0, m);
1161 b6afd33e 2003-11-23 devnull for(i = 0; i < m; i++)
1162 b6afd33e 2003-11-23 devnull cs.leafcount[i] = count[cs.leafmap[i]];
1165 b6afd33e 2003-11-23 devnull * set up free list
1167 b6afd33e 2003-11-23 devnull cs.free = &cs.chains[2];
1168 b6afd33e 2003-11-23 devnull cs.echains = &cs.chains[ChainMem];
1169 b6afd33e 2003-11-23 devnull cs.col = 1;
1172 b6afd33e 2003-11-23 devnull * initialize chains for each list
1174 b6afd33e 2003-11-23 devnull c = &cs.chains[0];
1175 b6afd33e 2003-11-23 devnull c->count = cs.leafcount[0];
1176 b6afd33e 2003-11-23 devnull c->leaf = 1;
1177 b6afd33e 2003-11-23 devnull c->col = cs.col;
1178 b6afd33e 2003-11-23 devnull c->up = nil;
1179 b6afd33e 2003-11-23 devnull c->gen = 0;
1180 b6afd33e 2003-11-23 devnull cs.chains[1] = cs.chains[0];
1181 b6afd33e 2003-11-23 devnull cs.chains[1].leaf = 2;
1182 b6afd33e 2003-11-23 devnull cs.chains[1].count = cs.leafcount[1];
1183 b6afd33e 2003-11-23 devnull for(i = 0; i < maxbits-1; i++){
1184 b6afd33e 2003-11-23 devnull cs.lists[i * 2] = &cs.chains[0];
1185 b6afd33e 2003-11-23 devnull cs.lists[i * 2 + 1] = &cs.chains[1];
1188 b6afd33e 2003-11-23 devnull cs.nlists = 2 * (maxbits - 1);
1189 b6afd33e 2003-11-23 devnull m = 2 * m - 2;
1190 b6afd33e 2003-11-23 devnull for(i = 2; i < m; i++)
1191 b6afd33e 2003-11-23 devnull nextchain(&cs, cs.nlists - 2);
1193 b6afd33e 2003-11-23 devnull bits = 0;
1194 b6afd33e 2003-11-23 devnull bitcount[0] = cs.nleaf;
1195 b6afd33e 2003-11-23 devnull for(c = cs.lists[cs.nlists - 1]; c != nil; c = c->up){
1196 b6afd33e 2003-11-23 devnull m = c->leaf;
1197 b6afd33e 2003-11-23 devnull bitcount[bits++] -= m;
1198 b6afd33e 2003-11-23 devnull bitcount[bits] = m;
1201 b6afd33e 2003-11-23 devnull for(i = bits; i >= 0; i--)
1202 b6afd33e 2003-11-23 devnull for(em = m + bitcount[i]; m < em; m++)
1203 b6afd33e 2003-11-23 devnull tab[cs.leafmap[m]].bits = i;
1205 b6afd33e 2003-11-23 devnull return bits;
1209 b6afd33e 2003-11-23 devnull * calculate the next chain on the list
1210 b6afd33e 2003-11-23 devnull * we can always toss out the old chain
1212 b6afd33e 2003-11-23 devnull static void
1213 b6afd33e 2003-11-23 devnull nextchain(Chains *cs, int list)
1215 b6afd33e 2003-11-23 devnull Chain *c, *oc;
1216 b6afd33e 2003-11-23 devnull int i, nleaf, sumc;
1218 b6afd33e 2003-11-23 devnull oc = cs->lists[list + 1];
1219 b6afd33e 2003-11-23 devnull cs->lists[list] = oc;
1220 b6afd33e 2003-11-23 devnull if(oc == nil)
1221 b6afd33e 2003-11-23 devnull return;
1224 b6afd33e 2003-11-23 devnull * make sure we have all chains needed to make sumc
1225 b6afd33e 2003-11-23 devnull * note it is possible to generate only one of these,
1226 b6afd33e 2003-11-23 devnull * use twice that value for sumc, and then generate
1227 b6afd33e 2003-11-23 devnull * the second if that preliminary sumc would be chosen.
1228 b6afd33e 2003-11-23 devnull * however, this appears to be slower on current tests
1230 b6afd33e 2003-11-23 devnull if(oc->gen){
1231 b6afd33e 2003-11-23 devnull nextchain(cs, list - 2);
1232 b6afd33e 2003-11-23 devnull nextchain(cs, list - 2);
1233 b6afd33e 2003-11-23 devnull oc->gen = 0;
1237 b6afd33e 2003-11-23 devnull * pick up the chain we're going to add;
1238 b6afd33e 2003-11-23 devnull * collect unused chains no free ones are left
1240 b6afd33e 2003-11-23 devnull for(c = cs->free; ; c++){
1241 b6afd33e 2003-11-23 devnull if(c >= cs->echains){
1242 b6afd33e 2003-11-23 devnull cs->col++;
1243 b6afd33e 2003-11-23 devnull for(i = 0; i < cs->nlists; i++)
1244 b6afd33e 2003-11-23 devnull for(c = cs->lists[i]; c != nil; c = c->up)
1245 b6afd33e 2003-11-23 devnull c->col = cs->col;
1246 b6afd33e 2003-11-23 devnull c = cs->chains;
1248 b6afd33e 2003-11-23 devnull if(c->col != cs->col)
1253 b6afd33e 2003-11-23 devnull * pick the cheapest of
1254 b6afd33e 2003-11-23 devnull * 1) the next package from the previous list
1255 b6afd33e 2003-11-23 devnull * 2) the next leaf
1257 b6afd33e 2003-11-23 devnull nleaf = oc->leaf;
1258 b6afd33e 2003-11-23 devnull sumc = 0;
1259 b6afd33e 2003-11-23 devnull if(list > 0 && cs->lists[list-1] != nil)
1260 b6afd33e 2003-11-23 devnull sumc = cs->lists[list-2]->count + cs->lists[list-1]->count;
1261 b6afd33e 2003-11-23 devnull if(sumc != 0 && (nleaf >= cs->nleaf || cs->leafcount[nleaf] > sumc)){
1262 b6afd33e 2003-11-23 devnull c->count = sumc;
1263 b6afd33e 2003-11-23 devnull c->leaf = oc->leaf;
1264 b6afd33e 2003-11-23 devnull c->up = cs->lists[list-1];
1265 b6afd33e 2003-11-23 devnull c->gen = 1;
1266 b6afd33e 2003-11-23 devnull }else if(nleaf >= cs->nleaf){
1267 b6afd33e 2003-11-23 devnull cs->lists[list + 1] = nil;
1268 b6afd33e 2003-11-23 devnull return;
1270 b6afd33e 2003-11-23 devnull c->leaf = nleaf + 1;
1271 b6afd33e 2003-11-23 devnull c->count = cs->leafcount[nleaf];
1272 b6afd33e 2003-11-23 devnull c->up = oc->up;
1273 b6afd33e 2003-11-23 devnull c->gen = 0;
1275 b6afd33e 2003-11-23 devnull cs->free = c + 1;
1277 b6afd33e 2003-11-23 devnull cs->lists[list + 1] = c;
1278 b6afd33e 2003-11-23 devnull c->col = cs->col;
1281 b6afd33e 2003-11-23 devnull static int
1282 b6afd33e 2003-11-23 devnull pivot(ulong *c, int a, int n)
1284 b6afd33e 2003-11-23 devnull int j, pi, pj, pk;
1286 b6afd33e 2003-11-23 devnull j = n/6;
1287 b6afd33e 2003-11-23 devnull pi = a + j; /* 1/6 */
1288 b6afd33e 2003-11-23 devnull j += j;
1289 b6afd33e 2003-11-23 devnull pj = pi + j; /* 1/2 */
1290 b6afd33e 2003-11-23 devnull pk = pj + j; /* 5/6 */
1291 b6afd33e 2003-11-23 devnull if(c[pi] < c[pj]){
1292 b6afd33e 2003-11-23 devnull if(c[pi] < c[pk]){
1293 b6afd33e 2003-11-23 devnull if(c[pj] < c[pk])
1294 b6afd33e 2003-11-23 devnull return pj;
1295 b6afd33e 2003-11-23 devnull return pk;
1297 b6afd33e 2003-11-23 devnull return pi;
1299 b6afd33e 2003-11-23 devnull if(c[pj] < c[pk]){
1300 b6afd33e 2003-11-23 devnull if(c[pi] < c[pk])
1301 b6afd33e 2003-11-23 devnull return pi;
1302 b6afd33e 2003-11-23 devnull return pk;
1304 b6afd33e 2003-11-23 devnull return pj;
1307 b6afd33e 2003-11-23 devnull static void
1308 b6afd33e 2003-11-23 devnull leafsort(ulong *leafcount, ushort *leafmap, int a, int n)
1310 b6afd33e 2003-11-23 devnull ulong t;
1311 b6afd33e 2003-11-23 devnull int j, pi, pj, pn;
1313 b6afd33e 2003-11-23 devnull while(n > 1){
1314 b6afd33e 2003-11-23 devnull if(n > 10){
1315 b6afd33e 2003-11-23 devnull pi = pivot(leafcount, a, n);
1317 b6afd33e 2003-11-23 devnull pi = a + (n>>1);
1319 b6afd33e 2003-11-23 devnull t = leafcount[pi];
1320 b6afd33e 2003-11-23 devnull leafcount[pi] = leafcount[a];
1321 b6afd33e 2003-11-23 devnull leafcount[a] = t;
1322 b6afd33e 2003-11-23 devnull t = leafmap[pi];
1323 b6afd33e 2003-11-23 devnull leafmap[pi] = leafmap[a];
1324 b6afd33e 2003-11-23 devnull leafmap[a] = t;
1325 b6afd33e 2003-11-23 devnull pi = a;
1326 b6afd33e 2003-11-23 devnull pn = a + n;
1327 b6afd33e 2003-11-23 devnull pj = pn;
1328 b6afd33e 2003-11-23 devnull for(;;){
1331 b6afd33e 2003-11-23 devnull while(pi < pn && (leafcount[pi] < leafcount[a] || leafcount[pi] == leafcount[a] && leafmap[pi] > leafmap[a]));
1334 b6afd33e 2003-11-23 devnull while(pj > a && (leafcount[pj] > leafcount[a] || leafcount[pj] == leafcount[a] && leafmap[pj] < leafmap[a]));
1335 b6afd33e 2003-11-23 devnull if(pj < pi)
1337 b6afd33e 2003-11-23 devnull t = leafcount[pi];
1338 b6afd33e 2003-11-23 devnull leafcount[pi] = leafcount[pj];
1339 b6afd33e 2003-11-23 devnull leafcount[pj] = t;
1340 b6afd33e 2003-11-23 devnull t = leafmap[pi];
1341 b6afd33e 2003-11-23 devnull leafmap[pi] = leafmap[pj];
1342 b6afd33e 2003-11-23 devnull leafmap[pj] = t;
1344 b6afd33e 2003-11-23 devnull t = leafcount[a];
1345 b6afd33e 2003-11-23 devnull leafcount[a] = leafcount[pj];
1346 b6afd33e 2003-11-23 devnull leafcount[pj] = t;
1347 b6afd33e 2003-11-23 devnull t = leafmap[a];
1348 b6afd33e 2003-11-23 devnull leafmap[a] = leafmap[pj];
1349 b6afd33e 2003-11-23 devnull leafmap[pj] = t;
1350 b6afd33e 2003-11-23 devnull j = pj - a;
1352 b6afd33e 2003-11-23 devnull n = n-j-1;
1353 b6afd33e 2003-11-23 devnull if(j >= n){
1354 b6afd33e 2003-11-23 devnull leafsort(leafcount, leafmap, a, j);
1355 b6afd33e 2003-11-23 devnull a += j+1;
1357 b6afd33e 2003-11-23 devnull leafsort(leafcount, leafmap, a + (j+1), n);
