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