File: | obj/gnu/usr.bin/perl/cpan/Compress-Raw-Bzip2/compress.c |
Warning: | line 193, column 19 Assigned value is garbage or undefined |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
1 | ||||
2 | /*-------------------------------------------------------------*/ | |||
3 | /*--- Compression machinery (not incl block sorting) ---*/ | |||
4 | /*--- compress.c ---*/ | |||
5 | /*-------------------------------------------------------------*/ | |||
6 | ||||
7 | /* ------------------------------------------------------------------ | |||
8 | This file is part of bzip2/libbzip2, a program and library for | |||
9 | lossless, block-sorting data compression. | |||
10 | ||||
11 | bzip2/libbzip2 version 1.0.8 of 13 July 2019 | |||
12 | Copyright (C) 1996-2019 Julian Seward <jseward@acm.org> | |||
13 | ||||
14 | Please read the WARNING, DISCLAIMER and PATENTS sections in the | |||
15 | README file. | |||
16 | ||||
17 | This program is released under the terms of the license contained | |||
18 | in the file LICENSE. | |||
19 | ------------------------------------------------------------------ */ | |||
20 | ||||
21 | ||||
22 | /* CHANGES | |||
23 | 0.9.0 -- original version. | |||
24 | 0.9.0a/b -- no changes in this file. | |||
25 | 0.9.0c -- changed setting of nGroups in sendMTFValues() | |||
26 | so as to do a bit better on small files | |||
27 | */ | |||
28 | ||||
29 | #include "bzlib_private.h" | |||
30 | ||||
31 | ||||
32 | /*---------------------------------------------------*/ | |||
33 | /*--- Bit stream I/O ---*/ | |||
34 | /*---------------------------------------------------*/ | |||
35 | ||||
36 | /*---------------------------------------------------*/ | |||
37 | void BZ2_bsInitWrite ( EState* s ) | |||
38 | { | |||
39 | s->bsLive = 0; | |||
40 | s->bsBuff = 0; | |||
41 | } | |||
42 | ||||
43 | ||||
44 | /*---------------------------------------------------*/ | |||
45 | static | |||
46 | void bsFinishWrite ( EState* s ) | |||
47 | { | |||
48 | while (s->bsLive > 0) { | |||
49 | s->zbits[s->numZ] = (UChar)(s->bsBuff >> 24); | |||
50 | s->numZ++; | |||
51 | s->bsBuff <<= 8; | |||
52 | s->bsLive -= 8; | |||
53 | } | |||
54 | } | |||
55 | ||||
56 | ||||
57 | /*---------------------------------------------------*/ | |||
58 | #define bsNEEDW(nz){ while (s->bsLive >= 8) { s->zbits[s->numZ] = (UChar )(s->bsBuff >> 24); s->numZ++; s->bsBuff <<= 8; s->bsLive -= 8; } } \ | |||
59 | { \ | |||
60 | while (s->bsLive >= 8) { \ | |||
61 | s->zbits[s->numZ] \ | |||
62 | = (UChar)(s->bsBuff >> 24); \ | |||
63 | s->numZ++; \ | |||
64 | s->bsBuff <<= 8; \ | |||
65 | s->bsLive -= 8; \ | |||
66 | } \ | |||
67 | } | |||
68 | ||||
69 | ||||
70 | /*---------------------------------------------------*/ | |||
71 | static | |||
72 | __inline__ | |||
73 | void bsW ( EState* s, Int32 n, UInt32 v ) | |||
74 | { | |||
75 | bsNEEDW ( n ){ while (s->bsLive >= 8) { s->zbits[s->numZ] = (UChar )(s->bsBuff >> 24); s->numZ++; s->bsBuff <<= 8; s->bsLive -= 8; } }; | |||
76 | s->bsBuff |= (v << (32 - s->bsLive - n)); | |||
77 | s->bsLive += n; | |||
78 | } | |||
79 | ||||
80 | ||||
81 | /*---------------------------------------------------*/ | |||
82 | static | |||
83 | void bsPutUInt32 ( EState* s, UInt32 u ) | |||
84 | { | |||
85 | bsW ( s, 8, (u >> 24) & 0xffL ); | |||
86 | bsW ( s, 8, (u >> 16) & 0xffL ); | |||
87 | bsW ( s, 8, (u >> 8) & 0xffL ); | |||
88 | bsW ( s, 8, u & 0xffL ); | |||
89 | } | |||
90 | ||||
91 | ||||
92 | /*---------------------------------------------------*/ | |||
93 | static | |||
94 | void bsPutUChar ( EState* s, UChar c ) | |||
95 | { | |||
96 | bsW( s, 8, (UInt32)c ); | |||
97 | } | |||
98 | ||||
99 | ||||
100 | /*---------------------------------------------------*/ | |||
101 | /*--- The back end proper ---*/ | |||
102 | /*---------------------------------------------------*/ | |||
103 | ||||
104 | /*---------------------------------------------------*/ | |||
105 | static | |||
106 | void makeMaps_e ( EState* s ) | |||
107 | { | |||
108 | Int32 i; | |||
109 | s->nInUse = 0; | |||
110 | for (i = 0; i < 256; i++) | |||
111 | if (s->inUse[i]) { | |||
112 | s->unseqToSeq[i] = s->nInUse; | |||
113 | s->nInUse++; | |||
114 | } | |||
115 | } | |||
116 | ||||
117 | ||||
118 | /*---------------------------------------------------*/ | |||
119 | static | |||
120 | void generateMTFValues ( EState* s ) | |||
121 | { | |||
122 | UChar yy[256]; | |||
123 | Int32 i, j; | |||
124 | Int32 zPend; | |||
125 | Int32 wr; | |||
126 | Int32 EOB; | |||
127 | ||||
128 | /* | |||
129 | After sorting (eg, here), | |||
130 | s->arr1 [ 0 .. s->nblock-1 ] holds sorted order, | |||
131 | and | |||
132 | ((UChar*)s->arr2) [ 0 .. s->nblock-1 ] | |||
133 | holds the original block data. | |||
134 | ||||
135 | The first thing to do is generate the MTF values, | |||
136 | and put them in | |||
137 | ((UInt16*)s->arr1) [ 0 .. s->nblock-1 ]. | |||
138 | Because there are strictly fewer or equal MTF values | |||
139 | than block values, ptr values in this area are overwritten | |||
140 | with MTF values only when they are no longer needed. | |||
141 | ||||
142 | The final compressed bitstream is generated into the | |||
143 | area starting at | |||
144 | (UChar*) (&((UChar*)s->arr2)[s->nblock]) | |||
145 | ||||
146 | These storage aliases are set up in bzCompressInit(), | |||
147 | except for the last one, which is arranged in | |||
148 | compressBlock(). | |||
149 | */ | |||
150 | UInt32* ptr = s->ptr; | |||
151 | UChar* block = s->block; | |||
152 | UInt16* mtfv = s->mtfv; | |||
153 | ||||
154 | makeMaps_e ( s ); | |||
155 | EOB = s->nInUse+1; | |||
156 | ||||
157 | for (i = 0; i <= EOB; i++) s->mtfFreq[i] = 0; | |||
158 | ||||
159 | wr = 0; | |||
160 | zPend = 0; | |||
161 | for (i = 0; i < s->nInUse; i++) yy[i] = (UChar) i; | |||
162 | ||||
163 | for (i = 0; i < s->nblock; i++) { | |||
164 | UChar ll_i; | |||
165 | AssertD ( wr <= i, "generateMTFValues(1)" )do { } while (0); | |||
166 | j = ptr[i]-1; if (j
| |||
167 | ll_i = s->unseqToSeq[block[j]]; | |||
168 | AssertD ( ll_i < s->nInUse, "generateMTFValues(2a)" )do { } while (0); | |||
169 | ||||
170 | if (yy[0] == ll_i) { | |||
171 | zPend++; | |||
172 | } else { | |||
173 | ||||
174 | if (zPend
| |||
175 | zPend--; | |||
176 | while (True((Bool)1)) { | |||
177 | if (zPend & 1) { | |||
178 | mtfv[wr] = BZ_RUNB1; wr++; | |||
179 | s->mtfFreq[BZ_RUNB1]++; | |||
180 | } else { | |||
181 | mtfv[wr] = BZ_RUNA0; wr++; | |||
182 | s->mtfFreq[BZ_RUNA0]++; | |||
183 | } | |||
184 | if (zPend < 2) break; | |||
185 | zPend = (zPend - 2) / 2; | |||
186 | }; | |||
187 | zPend = 0; | |||
188 | } | |||
189 | { | |||
190 | register UChar rtmp; | |||
191 | register UChar* ryy_j; | |||
192 | register UChar rll_i; | |||
193 | rtmp = yy[1]; | |||
| ||||
194 | yy[1] = yy[0]; | |||
195 | ryy_j = &(yy[1]); | |||
196 | rll_i = ll_i; | |||
197 | while ( rll_i != rtmp ) { | |||
198 | register UChar rtmp2; | |||
199 | ryy_j++; | |||
200 | rtmp2 = rtmp; | |||
201 | rtmp = *ryy_j; | |||
202 | *ryy_j = rtmp2; | |||
203 | }; | |||
204 | yy[0] = rtmp; | |||
205 | j = ryy_j - &(yy[0]); | |||
206 | mtfv[wr] = j+1; wr++; s->mtfFreq[j+1]++; | |||
207 | } | |||
208 | ||||
209 | } | |||
210 | } | |||
211 | ||||
212 | if (zPend > 0) { | |||
213 | zPend--; | |||
214 | while (True((Bool)1)) { | |||
215 | if (zPend & 1) { | |||
216 | mtfv[wr] = BZ_RUNB1; wr++; | |||
217 | s->mtfFreq[BZ_RUNB1]++; | |||
218 | } else { | |||
219 | mtfv[wr] = BZ_RUNA0; wr++; | |||
220 | s->mtfFreq[BZ_RUNA0]++; | |||
221 | } | |||
222 | if (zPend < 2) break; | |||
223 | zPend = (zPend - 2) / 2; | |||
224 | }; | |||
225 | zPend = 0; | |||
226 | } | |||
227 | ||||
228 | mtfv[wr] = EOB; wr++; s->mtfFreq[EOB]++; | |||
229 | ||||
230 | s->nMTF = wr; | |||
231 | } | |||
232 | ||||
233 | ||||
234 | /*---------------------------------------------------*/ | |||
235 | #define BZ_LESSER_ICOST0 0 | |||
236 | #define BZ_GREATER_ICOST15 15 | |||
237 | ||||
238 | static | |||
239 | void sendMTFValues ( EState* s ) | |||
240 | { | |||
241 | Int32 v, t, i, j, gs, ge, totc, bt, bc, iter; | |||
242 | Int32 nSelectors, alphaSize, minLen, maxLen, selCtr; | |||
243 | Int32 nGroups, nBytes; | |||
244 | ||||
245 | /*-- | |||
246 | UChar len [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; | |||
247 | is a global since the decoder also needs it. | |||
248 | ||||
249 | Int32 code[BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; | |||
250 | Int32 rfreq[BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; | |||
251 | are also globals only used in this proc. | |||
252 | Made global to keep stack frame size small. | |||
253 | --*/ | |||
254 | ||||
255 | ||||
256 | UInt16 cost[BZ_N_GROUPS6]; | |||
257 | Int32 fave[BZ_N_GROUPS6]; | |||
258 | ||||
259 | UInt16* mtfv = s->mtfv; | |||
260 | ||||
261 | ((void)nBytes); /* Silence variable ‘nBytes’ set but not used warning */ | |||
262 | if (s->verbosity >= 3) | |||
263 | VPrintf3( " %d in block, %d after MTF & 1-2 coding, "do { } while (0) | |||
264 | "%d+2 syms in use\n",do { } while (0) | |||
265 | s->nblock, s->nMTF, s->nInUse )do { } while (0); | |||
266 | ||||
267 | alphaSize = s->nInUse+2; | |||
268 | for (t = 0; t < BZ_N_GROUPS6; t++) | |||
269 | for (v = 0; v < alphaSize; v++) | |||
270 | s->len[t][v] = BZ_GREATER_ICOST15; | |||
271 | ||||
272 | /*--- Decide how many coding tables to use ---*/ | |||
273 | AssertH ( s->nMTF > 0, 3001 ){ if (!(s->nMTF > 0)) bz_internal_error ( 3001 ); }; | |||
274 | if (s->nMTF < 200) nGroups = 2; else | |||
275 | if (s->nMTF < 600) nGroups = 3; else | |||
276 | if (s->nMTF < 1200) nGroups = 4; else | |||
277 | if (s->nMTF < 2400) nGroups = 5; else | |||
278 | nGroups = 6; | |||
279 | ||||
280 | /*--- Generate an initial set of coding tables ---*/ | |||
281 | { | |||
282 | Int32 nPart, remF, tFreq, aFreq; | |||
283 | ||||
284 | nPart = nGroups; | |||
285 | remF = s->nMTF; | |||
286 | gs = 0; | |||
287 | while (nPart > 0) { | |||
288 | tFreq = remF / nPart; | |||
289 | ge = gs-1; | |||
290 | aFreq = 0; | |||
291 | while (aFreq < tFreq && ge < alphaSize-1) { | |||
292 | ge++; | |||
293 | aFreq += s->mtfFreq[ge]; | |||
294 | } | |||
295 | ||||
296 | if (ge > gs | |||
297 | && nPart != nGroups && nPart != 1 | |||
298 | && ((nGroups-nPart) % 2 == 1)) { | |||
299 | aFreq -= s->mtfFreq[ge]; | |||
300 | ge--; | |||
301 | } | |||
302 | ||||
303 | if (s->verbosity >= 3) | |||
304 | VPrintf5( " initial group %d, [%d .. %d], "do { } while (0) | |||
305 | "has %d syms (%4.1f%%)\n",do { } while (0) | |||
306 | nPart, gs, ge, aFreq,do { } while (0) | |||
307 | (100.0 * (float)aFreq) / (float)(s->nMTF) )do { } while (0); | |||
308 | ||||
309 | for (v = 0; v < alphaSize; v++) | |||
310 | if (v >= gs && v <= ge) | |||
311 | s->len[nPart-1][v] = BZ_LESSER_ICOST0; else | |||
312 | s->len[nPart-1][v] = BZ_GREATER_ICOST15; | |||
313 | ||||
314 | nPart--; | |||
315 | gs = ge+1; | |||
316 | remF -= aFreq; | |||
317 | } | |||
318 | } | |||
319 | ||||
320 | /*--- | |||
321 | Iterate up to BZ_N_ITERS times to improve the tables. | |||
322 | ---*/ | |||
323 | for (iter = 0; iter < BZ_N_ITERS4; iter++) { | |||
324 | ||||
325 | for (t = 0; t < nGroups; t++) fave[t] = 0; | |||
326 | ||||
327 | for (t = 0; t < nGroups; t++) | |||
328 | for (v = 0; v < alphaSize; v++) | |||
329 | s->rfreq[t][v] = 0; | |||
330 | ||||
331 | /*--- | |||
332 | Set up an auxiliary length table which is used to fast-track | |||
333 | the common case (nGroups == 6). | |||
334 | ---*/ | |||
335 | if (nGroups == 6) { | |||
336 | for (v = 0; v < alphaSize; v++) { | |||
337 | s->len_pack[v][0] = (s->len[1][v] << 16) | s->len[0][v]; | |||
338 | s->len_pack[v][1] = (s->len[3][v] << 16) | s->len[2][v]; | |||
339 | s->len_pack[v][2] = (s->len[5][v] << 16) | s->len[4][v]; | |||
340 | } | |||
341 | } | |||
342 | ||||
343 | nSelectors = 0; | |||
344 | totc = 0; | |||
345 | gs = 0; | |||
346 | while (True((Bool)1)) { | |||
347 | ||||
348 | /*--- Set group start & end marks. --*/ | |||
349 | if (gs >= s->nMTF) break; | |||
350 | ge = gs + BZ_G_SIZE50 - 1; | |||
351 | if (ge >= s->nMTF) ge = s->nMTF-1; | |||
352 | ||||
353 | /*-- | |||
354 | Calculate the cost of this group as coded | |||
355 | by each of the coding tables. | |||
356 | --*/ | |||
357 | for (t = 0; t < nGroups; t++) cost[t] = 0; | |||
358 | ||||
359 | if (nGroups == 6 && 50 == ge-gs+1) { | |||
360 | /*--- fast track the common case ---*/ | |||
361 | register UInt32 cost01, cost23, cost45; | |||
362 | register UInt16 icv; | |||
363 | cost01 = cost23 = cost45 = 0; | |||
364 | ||||
365 | # define BZ_ITER(nn) \ | |||
366 | icv = mtfv[gs+(nn)]; \ | |||
367 | cost01 += s->len_pack[icv][0]; \ | |||
368 | cost23 += s->len_pack[icv][1]; \ | |||
369 | cost45 += s->len_pack[icv][2]; \ | |||
370 | ||||
371 | BZ_ITER(0); BZ_ITER(1); BZ_ITER(2); BZ_ITER(3); BZ_ITER(4); | |||
372 | BZ_ITER(5); BZ_ITER(6); BZ_ITER(7); BZ_ITER(8); BZ_ITER(9); | |||
373 | BZ_ITER(10); BZ_ITER(11); BZ_ITER(12); BZ_ITER(13); BZ_ITER(14); | |||
374 | BZ_ITER(15); BZ_ITER(16); BZ_ITER(17); BZ_ITER(18); BZ_ITER(19); | |||
375 | BZ_ITER(20); BZ_ITER(21); BZ_ITER(22); BZ_ITER(23); BZ_ITER(24); | |||
376 | BZ_ITER(25); BZ_ITER(26); BZ_ITER(27); BZ_ITER(28); BZ_ITER(29); | |||
377 | BZ_ITER(30); BZ_ITER(31); BZ_ITER(32); BZ_ITER(33); BZ_ITER(34); | |||
378 | BZ_ITER(35); BZ_ITER(36); BZ_ITER(37); BZ_ITER(38); BZ_ITER(39); | |||
379 | BZ_ITER(40); BZ_ITER(41); BZ_ITER(42); BZ_ITER(43); BZ_ITER(44); | |||
380 | BZ_ITER(45); BZ_ITER(46); BZ_ITER(47); BZ_ITER(48); BZ_ITER(49); | |||
381 | ||||
382 | # undef BZ_ITER | |||
383 | ||||
384 | cost[0] = cost01 & 0xffff; cost[1] = cost01 >> 16; | |||
385 | cost[2] = cost23 & 0xffff; cost[3] = cost23 >> 16; | |||
386 | cost[4] = cost45 & 0xffff; cost[5] = cost45 >> 16; | |||
387 | ||||
388 | } else { | |||
389 | /*--- slow version which correctly handles all situations ---*/ | |||
390 | for (i = gs; i <= ge; i++) { | |||
391 | UInt16 icv = mtfv[i]; | |||
392 | for (t = 0; t < nGroups; t++) cost[t] += s->len[t][icv]; | |||
393 | } | |||
394 | } | |||
395 | ||||
396 | /*-- | |||
397 | Find the coding table which is best for this group, | |||
398 | and record its identity in the selector table. | |||
399 | --*/ | |||
400 | bc = 999999999; bt = -1; | |||
401 | for (t = 0; t < nGroups; t++) | |||
402 | if (cost[t] < bc) { bc = cost[t]; bt = t; }; | |||
403 | totc += bc; | |||
404 | fave[bt]++; | |||
405 | s->selector[nSelectors] = bt; | |||
406 | nSelectors++; | |||
407 | ||||
408 | /*-- | |||
409 | Increment the symbol frequencies for the selected table. | |||
410 | --*/ | |||
411 | if (nGroups == 6 && 50 == ge-gs+1) { | |||
412 | /*--- fast track the common case ---*/ | |||
413 | ||||
414 | # define BZ_ITUR(nn) s->rfreq[bt][ mtfv[gs+(nn)] ]++ | |||
415 | ||||
416 | BZ_ITUR(0); BZ_ITUR(1); BZ_ITUR(2); BZ_ITUR(3); BZ_ITUR(4); | |||
417 | BZ_ITUR(5); BZ_ITUR(6); BZ_ITUR(7); BZ_ITUR(8); BZ_ITUR(9); | |||
418 | BZ_ITUR(10); BZ_ITUR(11); BZ_ITUR(12); BZ_ITUR(13); BZ_ITUR(14); | |||
419 | BZ_ITUR(15); BZ_ITUR(16); BZ_ITUR(17); BZ_ITUR(18); BZ_ITUR(19); | |||
420 | BZ_ITUR(20); BZ_ITUR(21); BZ_ITUR(22); BZ_ITUR(23); BZ_ITUR(24); | |||
421 | BZ_ITUR(25); BZ_ITUR(26); BZ_ITUR(27); BZ_ITUR(28); BZ_ITUR(29); | |||
422 | BZ_ITUR(30); BZ_ITUR(31); BZ_ITUR(32); BZ_ITUR(33); BZ_ITUR(34); | |||
423 | BZ_ITUR(35); BZ_ITUR(36); BZ_ITUR(37); BZ_ITUR(38); BZ_ITUR(39); | |||
424 | BZ_ITUR(40); BZ_ITUR(41); BZ_ITUR(42); BZ_ITUR(43); BZ_ITUR(44); | |||
425 | BZ_ITUR(45); BZ_ITUR(46); BZ_ITUR(47); BZ_ITUR(48); BZ_ITUR(49); | |||
426 | ||||
427 | # undef BZ_ITUR | |||
428 | ||||
429 | } else { | |||
430 | /*--- slow version which correctly handles all situations ---*/ | |||
431 | for (i = gs; i <= ge; i++) | |||
432 | s->rfreq[bt][ mtfv[i] ]++; | |||
433 | } | |||
434 | ||||
435 | gs = ge+1; | |||
436 | } | |||
437 | if (s->verbosity >= 3) { | |||
438 | VPrintf2 ( " pass %d: size is %d, grp uses are ",do { } while (0) | |||
439 | iter+1, totc/8 )do { } while (0); | |||
440 | for (t = 0; t < nGroups; t++) | |||
441 | VPrintf1 ( "%d ", fave[t] )do { } while (0); | |||
442 | VPrintf0 ( "\n" )do { } while (0); | |||
443 | } | |||
444 | ||||
445 | /*-- | |||
446 | Recompute the tables based on the accumulated frequencies. | |||
447 | --*/ | |||
448 | /* maxLen was changed from 20 to 17 in bzip2-1.0.3. See | |||
449 | comment in huffman.c for details. */ | |||
450 | for (t = 0; t < nGroups; t++) | |||
451 | BZ2_hbMakeCodeLengths ( &(s->len[t][0]), &(s->rfreq[t][0]), | |||
452 | alphaSize, 17 /*20*/ ); | |||
453 | } | |||
454 | ||||
455 | ||||
456 | AssertH( nGroups < 8, 3002 ){ if (!(nGroups < 8)) bz_internal_error ( 3002 ); }; | |||
457 | AssertH( nSelectors < 32768 &&{ if (!(nSelectors < 32768 && nSelectors <= (2 + (900000 / 50)))) bz_internal_error ( 3003 ); } | |||
458 | nSelectors <= BZ_MAX_SELECTORS,{ if (!(nSelectors < 32768 && nSelectors <= (2 + (900000 / 50)))) bz_internal_error ( 3003 ); } | |||
459 | 3003 ){ if (!(nSelectors < 32768 && nSelectors <= (2 + (900000 / 50)))) bz_internal_error ( 3003 ); }; | |||
460 | ||||
461 | ||||
462 | /*--- Compute MTF values for the selectors. ---*/ | |||
463 | { | |||
464 | UChar pos[BZ_N_GROUPS6], ll_i, tmp2, tmp; | |||
465 | for (i = 0; i < nGroups; i++) pos[i] = i; | |||
466 | for (i = 0; i < nSelectors; i++) { | |||
467 | ll_i = s->selector[i]; | |||
468 | j = 0; | |||
469 | tmp = pos[j]; | |||
470 | while ( ll_i != tmp ) { | |||
471 | j++; | |||
472 | tmp2 = tmp; | |||
473 | tmp = pos[j]; | |||
474 | pos[j] = tmp2; | |||
475 | }; | |||
476 | pos[0] = tmp; | |||
477 | s->selectorMtf[i] = j; | |||
478 | } | |||
479 | }; | |||
480 | ||||
481 | /*--- Assign actual codes for the tables. --*/ | |||
482 | for (t = 0; t < nGroups; t++) { | |||
483 | minLen = 32; | |||
484 | maxLen = 0; | |||
485 | for (i = 0; i < alphaSize; i++) { | |||
486 | if (s->len[t][i] > maxLen) maxLen = s->len[t][i]; | |||
487 | if (s->len[t][i] < minLen) minLen = s->len[t][i]; | |||
488 | } | |||
489 | AssertH ( !(maxLen > 17 /*20*/ ), 3004 ){ if (!(!(maxLen > 17 ))) bz_internal_error ( 3004 ); }; | |||
490 | AssertH ( !(minLen < 1), 3005 ){ if (!(!(minLen < 1))) bz_internal_error ( 3005 ); }; | |||
491 | BZ2_hbAssignCodes ( &(s->code[t][0]), &(s->len[t][0]), | |||
492 | minLen, maxLen, alphaSize ); | |||
493 | } | |||
494 | ||||
495 | /*--- Transmit the mapping table. ---*/ | |||
496 | { | |||
497 | Bool inUse16[16]; | |||
498 | for (i = 0; i < 16; i++) { | |||
499 | inUse16[i] = False((Bool)0); | |||
500 | for (j = 0; j < 16; j++) | |||
501 | if (s->inUse[i * 16 + j]) inUse16[i] = True((Bool)1); | |||
502 | } | |||
503 | ||||
504 | nBytes = s->numZ; | |||
505 | for (i = 0; i < 16; i++) | |||
506 | if (inUse16[i]) bsW(s,1,1); else bsW(s,1,0); | |||
507 | ||||
508 | for (i = 0; i < 16; i++) | |||
509 | if (inUse16[i]) | |||
510 | for (j = 0; j < 16; j++) { | |||
511 | if (s->inUse[i * 16 + j]) bsW(s,1,1); else bsW(s,1,0); | |||
512 | } | |||
513 | ||||
514 | if (s->verbosity >= 3) | |||
515 | VPrintf1( " bytes: mapping %d, ", s->numZ-nBytes )do { } while (0); | |||
516 | } | |||
517 | ||||
518 | /*--- Now the selectors. ---*/ | |||
519 | nBytes = s->numZ; | |||
520 | bsW ( s, 3, nGroups ); | |||
521 | bsW ( s, 15, nSelectors ); | |||
522 | for (i = 0; i < nSelectors; i++) { | |||
523 | for (j = 0; j < s->selectorMtf[i]; j++) bsW(s,1,1); | |||
524 | bsW(s,1,0); | |||
525 | } | |||
526 | if (s->verbosity >= 3) | |||
527 | VPrintf1( "selectors %d, ", s->numZ-nBytes )do { } while (0); | |||
528 | ||||
529 | /*--- Now the coding tables. ---*/ | |||
530 | nBytes = s->numZ; | |||
531 | ||||
532 | for (t = 0; t < nGroups; t++) { | |||
533 | Int32 curr = s->len[t][0]; | |||
534 | bsW ( s, 5, curr ); | |||
535 | for (i = 0; i < alphaSize; i++) { | |||
536 | while (curr < s->len[t][i]) { bsW(s,2,2); curr++; /* 10 */ }; | |||
537 | while (curr > s->len[t][i]) { bsW(s,2,3); curr--; /* 11 */ }; | |||
538 | bsW ( s, 1, 0 ); | |||
539 | } | |||
540 | } | |||
541 | ||||
542 | if (s->verbosity >= 3) | |||
543 | VPrintf1 ( "code lengths %d, ", s->numZ-nBytes )do { } while (0); | |||
544 | ||||
545 | /*--- And finally, the block data proper ---*/ | |||
546 | nBytes = s->numZ; | |||
547 | selCtr = 0; | |||
548 | gs = 0; | |||
549 | while (True((Bool)1)) { | |||
550 | if (gs >= s->nMTF) break; | |||
551 | ge = gs + BZ_G_SIZE50 - 1; | |||
552 | if (ge >= s->nMTF) ge = s->nMTF-1; | |||
553 | AssertH ( s->selector[selCtr] < nGroups, 3006 ){ if (!(s->selector[selCtr] < nGroups)) bz_internal_error ( 3006 ); }; | |||
554 | ||||
555 | if (nGroups == 6 && 50 == ge-gs+1) { | |||
556 | /*--- fast track the common case ---*/ | |||
557 | UInt16 mtfv_i; | |||
558 | UChar* s_len_sel_selCtr | |||
559 | = &(s->len[s->selector[selCtr]][0]); | |||
560 | Int32* s_code_sel_selCtr | |||
561 | = &(s->code[s->selector[selCtr]][0]); | |||
562 | ||||
563 | # define BZ_ITAH(nn) \ | |||
564 | mtfv_i = mtfv[gs+(nn)]; \ | |||
565 | bsW ( s, \ | |||
566 | s_len_sel_selCtr[mtfv_i], \ | |||
567 | s_code_sel_selCtr[mtfv_i] ) | |||
568 | ||||
569 | BZ_ITAH(0); BZ_ITAH(1); BZ_ITAH(2); BZ_ITAH(3); BZ_ITAH(4); | |||
570 | BZ_ITAH(5); BZ_ITAH(6); BZ_ITAH(7); BZ_ITAH(8); BZ_ITAH(9); | |||
571 | BZ_ITAH(10); BZ_ITAH(11); BZ_ITAH(12); BZ_ITAH(13); BZ_ITAH(14); | |||
572 | BZ_ITAH(15); BZ_ITAH(16); BZ_ITAH(17); BZ_ITAH(18); BZ_ITAH(19); | |||
573 | BZ_ITAH(20); BZ_ITAH(21); BZ_ITAH(22); BZ_ITAH(23); BZ_ITAH(24); | |||
574 | BZ_ITAH(25); BZ_ITAH(26); BZ_ITAH(27); BZ_ITAH(28); BZ_ITAH(29); | |||
575 | BZ_ITAH(30); BZ_ITAH(31); BZ_ITAH(32); BZ_ITAH(33); BZ_ITAH(34); | |||
576 | BZ_ITAH(35); BZ_ITAH(36); BZ_ITAH(37); BZ_ITAH(38); BZ_ITAH(39); | |||
577 | BZ_ITAH(40); BZ_ITAH(41); BZ_ITAH(42); BZ_ITAH(43); BZ_ITAH(44); | |||
578 | BZ_ITAH(45); BZ_ITAH(46); BZ_ITAH(47); BZ_ITAH(48); BZ_ITAH(49); | |||
579 | ||||
580 | # undef BZ_ITAH | |||
581 | ||||
582 | } else { | |||
583 | /*--- slow version which correctly handles all situations ---*/ | |||
584 | for (i = gs; i <= ge; i++) { | |||
585 | bsW ( s, | |||
586 | s->len [s->selector[selCtr]] [mtfv[i]], | |||
587 | s->code [s->selector[selCtr]] [mtfv[i]] ); | |||
588 | } | |||
589 | } | |||
590 | ||||
591 | ||||
592 | gs = ge+1; | |||
593 | selCtr++; | |||
594 | } | |||
595 | AssertH( selCtr == nSelectors, 3007 ){ if (!(selCtr == nSelectors)) bz_internal_error ( 3007 ); }; | |||
596 | ||||
597 | if (s->verbosity >= 3) | |||
598 | VPrintf1( "codes %d\n", s->numZ-nBytes )do { } while (0); | |||
599 | } | |||
600 | ||||
601 | ||||
602 | /*---------------------------------------------------*/ | |||
603 | void BZ2_compressBlock ( EState* s, Bool is_last_block ) | |||
604 | { | |||
605 | if (s->nblock > 0) { | |||
| ||||
606 | ||||
607 | BZ_FINALISE_CRC ( s->blockCRC ){ s->blockCRC = ~(s->blockCRC); }; | |||
608 | s->combinedCRC = (s->combinedCRC << 1) | (s->combinedCRC >> 31); | |||
609 | s->combinedCRC ^= s->blockCRC; | |||
610 | if (s->blockNo > 1) s->numZ = 0; | |||
611 | ||||
612 | if (s->verbosity >= 2) | |||
613 | VPrintf4( " block %d: crc = 0x%08x, "do { } while (0) | |||
614 | "combined CRC = 0x%08x, size = %d\n",do { } while (0) | |||
615 | s->blockNo, s->blockCRC, s->combinedCRC, s->nblock )do { } while (0); | |||
616 | ||||
617 | BZ2_blockSort ( s ); | |||
618 | } | |||
619 | ||||
620 | s->zbits = (UChar*) (&((UChar*)s->arr2)[s->nblock]); | |||
621 | ||||
622 | /*-- If this is the first block, create the stream header. --*/ | |||
623 | if (s->blockNo == 1) { | |||
624 | BZ2_bsInitWrite ( s ); | |||
625 | bsPutUChar ( s, BZ_HDR_B0x42 ); | |||
626 | bsPutUChar ( s, BZ_HDR_Z0x5a ); | |||
627 | bsPutUChar ( s, BZ_HDR_h0x68 ); | |||
628 | bsPutUChar ( s, (UChar)(BZ_HDR_00x30 + s->blockSize100k) ); | |||
629 | } | |||
630 | ||||
631 | if (s->nblock > 0) { | |||
632 | ||||
633 | bsPutUChar ( s, 0x31 ); bsPutUChar ( s, 0x41 ); | |||
634 | bsPutUChar ( s, 0x59 ); bsPutUChar ( s, 0x26 ); | |||
635 | bsPutUChar ( s, 0x53 ); bsPutUChar ( s, 0x59 ); | |||
636 | ||||
637 | /*-- Now the block's CRC, so it is in a known place. --*/ | |||
638 | bsPutUInt32 ( s, s->blockCRC ); | |||
639 | ||||
640 | /*-- | |||
641 | Now a single bit indicating (non-)randomisation. | |||
642 | As of version 0.9.5, we use a better sorting algorithm | |||
643 | which makes randomisation unnecessary. So always set | |||
644 | the randomised bit to 'no'. Of course, the decoder | |||
645 | still needs to be able to handle randomised blocks | |||
646 | so as to maintain backwards compatibility with | |||
647 | older versions of bzip2. | |||
648 | --*/ | |||
649 | bsW(s,1,0); | |||
650 | ||||
651 | bsW ( s, 24, s->origPtr ); | |||
652 | generateMTFValues ( s ); | |||
653 | sendMTFValues ( s ); | |||
654 | } | |||
655 | ||||
656 | ||||
657 | /*-- If this is the last block, add the stream trailer. --*/ | |||
658 | if (is_last_block) { | |||
659 | ||||
660 | bsPutUChar ( s, 0x17 ); bsPutUChar ( s, 0x72 ); | |||
661 | bsPutUChar ( s, 0x45 ); bsPutUChar ( s, 0x38 ); | |||
662 | bsPutUChar ( s, 0x50 ); bsPutUChar ( s, 0x90 ); | |||
663 | bsPutUInt32 ( s, s->combinedCRC ); | |||
664 | if (s->verbosity >= 2) | |||
665 | VPrintf1( " final combined CRC = 0x%08x\n ", s->combinedCRC )do { } while (0); | |||
666 | bsFinishWrite ( s ); | |||
667 | } | |||
668 | } | |||
669 | ||||
670 | ||||
671 | /*-------------------------------------------------------------*/ | |||
672 | /*--- end compress.c ---*/ | |||
673 | /*-------------------------------------------------------------*/ |