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