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