source: trunk/minix/commands/bzip2-1.0.3/compress.c@ 20

Last change on this file since 20 was 9, checked in by Mattia Monga, 14 years ago

Minix 3.1.2a
File size: 21.6 KB
Line 
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-2005 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@bzip.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/*---------------------------------------------------*/
81void BZ2_bsInitWrite ( EState* s )
82{
83 s->bsLive = 0;
84 s->bsBuff = 0;
85}
86
87
88/*---------------------------------------------------*/
89static
90void 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/*---------------------------------------------------*/
115static
116__inline__
117void 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/*---------------------------------------------------*/
126static
127void 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/*---------------------------------------------------*/
137static
138void bsPutUChar ( EState* s, UChar c )
139{
140 bsW( s, 8, (UInt32)c );
141}
142
143
144/*---------------------------------------------------*/
145/*--- The back end proper ---*/
146/*---------------------------------------------------*/
147
148/*---------------------------------------------------*/
149static
150void 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/*---------------------------------------------------*/
163static
164void 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
282static
283void 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 /* maxLen was changed from 20 to 17 in bzip2-1.0.3. See
492 comment in huffman.c for details. */
493 for (t = 0; t < nGroups; t++)
494 BZ2_hbMakeCodeLengths ( &(s->len[t][0]), &(s->rfreq[t][0]),
495 alphaSize, 17 /*20*/ );
496 }
497
498
499 AssertH( nGroups < 8, 3002 );
500 AssertH( nSelectors < 32768 &&
501 nSelectors <= (2 + (900000 / BZ_G_SIZE)),
502 3003 );
503
504
505 /*--- Compute MTF values for the selectors. ---*/
506 {
507 UChar pos[BZ_N_GROUPS], ll_i, tmp2, tmp;
508 for (i = 0; i < nGroups; i++) pos[i] = i;
509 for (i = 0; i < nSelectors; i++) {
510 ll_i = s->selector[i];
511 j = 0;
512 tmp = pos[j];
513 while ( ll_i != tmp ) {
514 j++;
515 tmp2 = tmp;
516 tmp = pos[j];
517 pos[j] = tmp2;
518 };
519 pos[0] = tmp;
520 s->selectorMtf[i] = j;
521 }
522 };
523
524 /*--- Assign actual codes for the tables. --*/
525 for (t = 0; t < nGroups; t++) {
526 minLen = 32;
527 maxLen = 0;
528 for (i = 0; i < alphaSize; i++) {
529 if (s->len[t][i] > maxLen) maxLen = s->len[t][i];
530 if (s->len[t][i] < minLen) minLen = s->len[t][i];
531 }
532 AssertH ( !(maxLen > 17 /*20*/ ), 3004 );
533 AssertH ( !(minLen < 1), 3005 );
534 BZ2_hbAssignCodes ( &(s->code[t][0]), &(s->len[t][0]),
535 minLen, maxLen, alphaSize );
536 }
537
538 /*--- Transmit the mapping table. ---*/
539 {
540 Bool inUse16[16];
541 for (i = 0; i < 16; i++) {
542 inUse16[i] = False;
543 for (j = 0; j < 16; j++)
544 if (s->inUse[i * 16 + j]) inUse16[i] = True;
545 }
546
547 nBytes = s->numZ;
548 for (i = 0; i < 16; i++)
549 if (inUse16[i]) bsW(s,1,1); else bsW(s,1,0);
550
551 for (i = 0; i < 16; i++)
552 if (inUse16[i])
553 for (j = 0; j < 16; j++) {
554 if (s->inUse[i * 16 + j]) bsW(s,1,1); else bsW(s,1,0);
555 }
556
557 if (s->verbosity >= 3)
558 VPrintf1( " bytes: mapping %d, ", s->numZ-nBytes );
559 }
560
561 /*--- Now the selectors. ---*/
562 nBytes = s->numZ;
563 bsW ( s, 3, nGroups );
564 bsW ( s, 15, nSelectors );
565 for (i = 0; i < nSelectors; i++) {
566 for (j = 0; j < s->selectorMtf[i]; j++) bsW(s,1,1);
567 bsW(s,1,0);
568 }
569 if (s->verbosity >= 3)
570 VPrintf1( "selectors %d, ", s->numZ-nBytes );
571
572 /*--- Now the coding tables. ---*/
573 nBytes = s->numZ;
574
575 for (t = 0; t < nGroups; t++) {
576 Int32 curr = s->len[t][0];
577 bsW ( s, 5, curr );
578 for (i = 0; i < alphaSize; i++) {
579 while (curr < s->len[t][i]) { bsW(s,2,2); curr++; /* 10 */ };
580 while (curr > s->len[t][i]) { bsW(s,2,3); curr--; /* 11 */ };
581 bsW ( s, 1, 0 );
582 }
583 }
584
585 if (s->verbosity >= 3)
586 VPrintf1 ( "code lengths %d, ", s->numZ-nBytes );
587
588 /*--- And finally, the block data proper ---*/
589 nBytes = s->numZ;
590 selCtr = 0;
591 gs = 0;
592 while (True) {
593 if (gs >= s->nMTF) break;
594 ge = gs + BZ_G_SIZE - 1;
595 if (ge >= s->nMTF) ge = s->nMTF-1;
596 AssertH ( s->selector[selCtr] < nGroups, 3006 );
597
598 if (nGroups == 6 && 50 == ge-gs+1) {
599 /*--- fast track the common case ---*/
600 UInt16 mtfv_i;
601 UChar* s_len_sel_selCtr
602 = &(s->len[s->selector[selCtr]][0]);
603 Int32* s_code_sel_selCtr
604 = &(s->code[s->selector[selCtr]][0]);
605
606# define BZ_ITAH(nn) \
607 mtfv_i = mtfv[gs+(nn)]; \
608 bsW ( s, \
609 s_len_sel_selCtr[mtfv_i], \
610 s_code_sel_selCtr[mtfv_i] )
611
612 BZ_ITAH(0); BZ_ITAH(1); BZ_ITAH(2); BZ_ITAH(3); BZ_ITAH(4);
613 BZ_ITAH(5); BZ_ITAH(6); BZ_ITAH(7); BZ_ITAH(8); BZ_ITAH(9);
614 BZ_ITAH(10); BZ_ITAH(11); BZ_ITAH(12); BZ_ITAH(13); BZ_ITAH(14);
615 BZ_ITAH(15); BZ_ITAH(16); BZ_ITAH(17); BZ_ITAH(18); BZ_ITAH(19);
616 BZ_ITAH(20); BZ_ITAH(21); BZ_ITAH(22); BZ_ITAH(23); BZ_ITAH(24);
617 BZ_ITAH(25); BZ_ITAH(26); BZ_ITAH(27); BZ_ITAH(28); BZ_ITAH(29);
618 BZ_ITAH(30); BZ_ITAH(31); BZ_ITAH(32); BZ_ITAH(33); BZ_ITAH(34);
619 BZ_ITAH(35); BZ_ITAH(36); BZ_ITAH(37); BZ_ITAH(38); BZ_ITAH(39);
620 BZ_ITAH(40); BZ_ITAH(41); BZ_ITAH(42); BZ_ITAH(43); BZ_ITAH(44);
621 BZ_ITAH(45); BZ_ITAH(46); BZ_ITAH(47); BZ_ITAH(48); BZ_ITAH(49);
622
623# undef BZ_ITAH
624
625 } else {
626 /*--- slow version which correctly handles all situations ---*/
627 for (i = gs; i <= ge; i++) {
628 bsW ( s,
629 s->len [s->selector[selCtr]] [mtfv[i]],
630 s->code [s->selector[selCtr]] [mtfv[i]] );
631 }
632 }
633
634
635 gs = ge+1;
636 selCtr++;
637 }
638 AssertH( selCtr == nSelectors, 3007 );
639
640 if (s->verbosity >= 3)
641 VPrintf1( "codes %d\n", s->numZ-nBytes );
642}
643
644
645/*---------------------------------------------------*/
646void BZ2_compressBlock ( EState* s, Bool is_last_block )
647{
648 if (s->nblock > 0) {
649
650 BZ_FINALISE_CRC ( s->blockCRC );
651 s->combinedCRC = (s->combinedCRC << 1) | (s->combinedCRC >> 31);
652 s->combinedCRC ^= s->blockCRC;
653 if (s->blockNo > 1) s->numZ = 0;
654
655 if (s->verbosity >= 2)
656 VPrintf4( " block %d: crc = 0x%08x, "
657 "combined CRC = 0x%08x, size = %d\n",
658 s->blockNo, s->blockCRC, s->combinedCRC, s->nblock );
659
660 BZ2_blockSort ( s );
661 }
662
663 s->zbits = (UChar*) (&((UChar*)s->arr2)[s->nblock]);
664
665 /*-- If this is the first block, create the stream header. --*/
666 if (s->blockNo == 1) {
667 BZ2_bsInitWrite ( s );
668 bsPutUChar ( s, BZ_HDR_B );
669 bsPutUChar ( s, BZ_HDR_Z );
670 bsPutUChar ( s, BZ_HDR_h );
671 bsPutUChar ( s, (UChar)(BZ_HDR_0 + s->blockSize100k) );
672 }
673
674 if (s->nblock > 0) {
675
676 bsPutUChar ( s, 0x31 ); bsPutUChar ( s, 0x41 );
677 bsPutUChar ( s, 0x59 ); bsPutUChar ( s, 0x26 );
678 bsPutUChar ( s, 0x53 ); bsPutUChar ( s, 0x59 );
679
680 /*-- Now the block's CRC, so it is in a known place. --*/
681 bsPutUInt32 ( s, s->blockCRC );
682
683 /*--
684 Now a single bit indicating (non-)randomisation.
685 As of version 0.9.5, we use a better sorting algorithm
686 which makes randomisation unnecessary. So always set
687 the randomised bit to 'no'. Of course, the decoder
688 still needs to be able to handle randomised blocks
689 so as to maintain backwards compatibility with
690 older versions of bzip2.
691 --*/
692 bsW(s,1,0);
693
694 bsW ( s, 24, s->origPtr );
695 generateMTFValues ( s );
696 sendMTFValues ( s );
697 }
698
699
700 /*-- If this is the last block, add the stream trailer. --*/
701 if (is_last_block) {
702
703 bsPutUChar ( s, 0x17 ); bsPutUChar ( s, 0x72 );
704 bsPutUChar ( s, 0x45 ); bsPutUChar ( s, 0x38 );
705 bsPutUChar ( s, 0x50 ); bsPutUChar ( s, 0x90 );
706 bsPutUInt32 ( s, s->combinedCRC );
707 if (s->verbosity >= 2)
708 VPrintf1( " final combined CRC = 0x%08x\n ", s->combinedCRC );
709 bsFinishWrite ( s );
710 }
711}
712
713
714/*-------------------------------------------------------------*/
715/*--- end compress.c ---*/
716/*-------------------------------------------------------------*/
Note: See TracBrowser for help on using the repository browser.