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