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