1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/modules/libbz2/src/compress.c Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,672 @@
1.4 +
1.5 +/*-------------------------------------------------------------*/
1.6 +/*--- Compression machinery (not incl block sorting) ---*/
1.7 +/*--- compress.c ---*/
1.8 +/*-------------------------------------------------------------*/
1.9 +
1.10 +/* ------------------------------------------------------------------
1.11 + This file is part of bzip2/libbzip2, a program and library for
1.12 + lossless, block-sorting data compression.
1.13 +
1.14 + bzip2/libbzip2 version 1.0.4 of 20 December 2006
1.15 + Copyright (C) 1996-2006 Julian Seward <jseward@bzip.org>
1.16 +
1.17 + Please read the WARNING, DISCLAIMER and PATENTS sections in the
1.18 + README file.
1.19 +
1.20 + This program is released under the terms of the license contained
1.21 + in the file LICENSE.
1.22 + ------------------------------------------------------------------ */
1.23 +
1.24 +
1.25 +/* CHANGES
1.26 + 0.9.0 -- original version.
1.27 + 0.9.0a/b -- no changes in this file.
1.28 + 0.9.0c -- changed setting of nGroups in sendMTFValues()
1.29 + so as to do a bit better on small files
1.30 +*/
1.31 +
1.32 +#include "bzlib_private.h"
1.33 +
1.34 +
1.35 +/*---------------------------------------------------*/
1.36 +/*--- Bit stream I/O ---*/
1.37 +/*---------------------------------------------------*/
1.38 +
1.39 +/*---------------------------------------------------*/
1.40 +void BZ2_bsInitWrite ( EState* s )
1.41 +{
1.42 + s->bsLive = 0;
1.43 + s->bsBuff = 0;
1.44 +}
1.45 +
1.46 +
1.47 +/*---------------------------------------------------*/
1.48 +static
1.49 +void bsFinishWrite ( EState* s )
1.50 +{
1.51 + while (s->bsLive > 0) {
1.52 + s->zbits[s->numZ] = (UChar)(s->bsBuff >> 24);
1.53 + s->numZ++;
1.54 + s->bsBuff <<= 8;
1.55 + s->bsLive -= 8;
1.56 + }
1.57 +}
1.58 +
1.59 +
1.60 +/*---------------------------------------------------*/
1.61 +#define bsNEEDW(nz) \
1.62 +{ \
1.63 + while (s->bsLive >= 8) { \
1.64 + s->zbits[s->numZ] \
1.65 + = (UChar)(s->bsBuff >> 24); \
1.66 + s->numZ++; \
1.67 + s->bsBuff <<= 8; \
1.68 + s->bsLive -= 8; \
1.69 + } \
1.70 +}
1.71 +
1.72 +
1.73 +/*---------------------------------------------------*/
1.74 +static
1.75 +__inline__
1.76 +void bsW ( EState* s, Int32 n, UInt32 v )
1.77 +{
1.78 + bsNEEDW ( n );
1.79 + s->bsBuff |= (v << (32 - s->bsLive - n));
1.80 + s->bsLive += n;
1.81 +}
1.82 +
1.83 +
1.84 +/*---------------------------------------------------*/
1.85 +static
1.86 +void bsPutUInt32 ( EState* s, UInt32 u )
1.87 +{
1.88 + bsW ( s, 8, (u >> 24) & 0xffL );
1.89 + bsW ( s, 8, (u >> 16) & 0xffL );
1.90 + bsW ( s, 8, (u >> 8) & 0xffL );
1.91 + bsW ( s, 8, u & 0xffL );
1.92 +}
1.93 +
1.94 +
1.95 +/*---------------------------------------------------*/
1.96 +static
1.97 +void bsPutUChar ( EState* s, UChar c )
1.98 +{
1.99 + bsW( s, 8, (UInt32)c );
1.100 +}
1.101 +
1.102 +
1.103 +/*---------------------------------------------------*/
1.104 +/*--- The back end proper ---*/
1.105 +/*---------------------------------------------------*/
1.106 +
1.107 +/*---------------------------------------------------*/
1.108 +static
1.109 +void makeMaps_e ( EState* s )
1.110 +{
1.111 + Int32 i;
1.112 + s->nInUse = 0;
1.113 + for (i = 0; i < 256; i++)
1.114 + if (s->inUse[i]) {
1.115 + s->unseqToSeq[i] = s->nInUse;
1.116 + s->nInUse++;
1.117 + }
1.118 +}
1.119 +
1.120 +
1.121 +/*---------------------------------------------------*/
1.122 +static
1.123 +void generateMTFValues ( EState* s )
1.124 +{
1.125 + UChar yy[256];
1.126 + Int32 i, j;
1.127 + Int32 zPend;
1.128 + Int32 wr;
1.129 + Int32 EOB;
1.130 +
1.131 + /*
1.132 + After sorting (eg, here),
1.133 + s->arr1 [ 0 .. s->nblock-1 ] holds sorted order,
1.134 + and
1.135 + ((UChar*)s->arr2) [ 0 .. s->nblock-1 ]
1.136 + holds the original block data.
1.137 +
1.138 + The first thing to do is generate the MTF values,
1.139 + and put them in
1.140 + ((UInt16*)s->arr1) [ 0 .. s->nblock-1 ].
1.141 + Because there are strictly fewer or equal MTF values
1.142 + than block values, ptr values in this area are overwritten
1.143 + with MTF values only when they are no longer needed.
1.144 +
1.145 + The final compressed bitstream is generated into the
1.146 + area starting at
1.147 + (UChar*) (&((UChar*)s->arr2)[s->nblock])
1.148 +
1.149 + These storage aliases are set up in bzCompressInit(),
1.150 + except for the last one, which is arranged in
1.151 + compressBlock().
1.152 + */
1.153 + UInt32* ptr = s->ptr;
1.154 + UChar* block = s->block;
1.155 + UInt16* mtfv = s->mtfv;
1.156 +
1.157 + makeMaps_e ( s );
1.158 + EOB = s->nInUse+1;
1.159 +
1.160 + for (i = 0; i <= EOB; i++) s->mtfFreq[i] = 0;
1.161 +
1.162 + wr = 0;
1.163 + zPend = 0;
1.164 + for (i = 0; i < s->nInUse; i++) yy[i] = (UChar) i;
1.165 +
1.166 + for (i = 0; i < s->nblock; i++) {
1.167 + UChar ll_i;
1.168 + AssertD ( wr <= i, "generateMTFValues(1)" );
1.169 + j = ptr[i]-1; if (j < 0) j += s->nblock;
1.170 + ll_i = s->unseqToSeq[block[j]];
1.171 + AssertD ( ll_i < s->nInUse, "generateMTFValues(2a)" );
1.172 +
1.173 + if (yy[0] == ll_i) {
1.174 + zPend++;
1.175 + } else {
1.176 +
1.177 + if (zPend > 0) {
1.178 + zPend--;
1.179 + while (True) {
1.180 + if (zPend & 1) {
1.181 + mtfv[wr] = BZ_RUNB; wr++;
1.182 + s->mtfFreq[BZ_RUNB]++;
1.183 + } else {
1.184 + mtfv[wr] = BZ_RUNA; wr++;
1.185 + s->mtfFreq[BZ_RUNA]++;
1.186 + }
1.187 + if (zPend < 2) break;
1.188 + zPend = (zPend - 2) / 2;
1.189 + };
1.190 + zPend = 0;
1.191 + }
1.192 + {
1.193 + register UChar rtmp;
1.194 + register UChar* ryy_j;
1.195 + register UChar rll_i;
1.196 + rtmp = yy[1];
1.197 + yy[1] = yy[0];
1.198 + ryy_j = &(yy[1]);
1.199 + rll_i = ll_i;
1.200 + while ( rll_i != rtmp ) {
1.201 + register UChar rtmp2;
1.202 + ryy_j++;
1.203 + rtmp2 = rtmp;
1.204 + rtmp = *ryy_j;
1.205 + *ryy_j = rtmp2;
1.206 + };
1.207 + yy[0] = rtmp;
1.208 + j = ryy_j - &(yy[0]);
1.209 + mtfv[wr] = j+1; wr++; s->mtfFreq[j+1]++;
1.210 + }
1.211 +
1.212 + }
1.213 + }
1.214 +
1.215 + if (zPend > 0) {
1.216 + zPend--;
1.217 + while (True) {
1.218 + if (zPend & 1) {
1.219 + mtfv[wr] = BZ_RUNB; wr++;
1.220 + s->mtfFreq[BZ_RUNB]++;
1.221 + } else {
1.222 + mtfv[wr] = BZ_RUNA; wr++;
1.223 + s->mtfFreq[BZ_RUNA]++;
1.224 + }
1.225 + if (zPend < 2) break;
1.226 + zPend = (zPend - 2) / 2;
1.227 + };
1.228 + zPend = 0;
1.229 + }
1.230 +
1.231 + mtfv[wr] = EOB; wr++; s->mtfFreq[EOB]++;
1.232 +
1.233 + s->nMTF = wr;
1.234 +}
1.235 +
1.236 +
1.237 +/*---------------------------------------------------*/
1.238 +#define BZ_LESSER_ICOST 0
1.239 +#define BZ_GREATER_ICOST 15
1.240 +
1.241 +static
1.242 +void sendMTFValues ( EState* s )
1.243 +{
1.244 + Int32 v, t, i, j, gs, ge, totc, bt, bc, iter;
1.245 + Int32 nSelectors, alphaSize, minLen, maxLen, selCtr;
1.246 + Int32 nGroups, nBytes;
1.247 +
1.248 + /*--
1.249 + UChar len [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
1.250 + is a global since the decoder also needs it.
1.251 +
1.252 + Int32 code[BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
1.253 + Int32 rfreq[BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
1.254 + are also globals only used in this proc.
1.255 + Made global to keep stack frame size small.
1.256 + --*/
1.257 +
1.258 +
1.259 + UInt16 cost[BZ_N_GROUPS];
1.260 + Int32 fave[BZ_N_GROUPS];
1.261 +
1.262 + UInt16* mtfv = s->mtfv;
1.263 +
1.264 + if (s->verbosity >= 3)
1.265 + VPrintf3( " %d in block, %d after MTF & 1-2 coding, "
1.266 + "%d+2 syms in use\n",
1.267 + s->nblock, s->nMTF, s->nInUse );
1.268 +
1.269 + alphaSize = s->nInUse+2;
1.270 + for (t = 0; t < BZ_N_GROUPS; t++)
1.271 + for (v = 0; v < alphaSize; v++)
1.272 + s->len[t][v] = BZ_GREATER_ICOST;
1.273 +
1.274 + /*--- Decide how many coding tables to use ---*/
1.275 + AssertH ( s->nMTF > 0, 3001 );
1.276 + if (s->nMTF < 200) nGroups = 2; else
1.277 + if (s->nMTF < 600) nGroups = 3; else
1.278 + if (s->nMTF < 1200) nGroups = 4; else
1.279 + if (s->nMTF < 2400) nGroups = 5; else
1.280 + nGroups = 6;
1.281 +
1.282 + /*--- Generate an initial set of coding tables ---*/
1.283 + {
1.284 + Int32 nPart, remF, tFreq, aFreq;
1.285 +
1.286 + nPart = nGroups;
1.287 + remF = s->nMTF;
1.288 + gs = 0;
1.289 + while (nPart > 0) {
1.290 + tFreq = remF / nPart;
1.291 + ge = gs-1;
1.292 + aFreq = 0;
1.293 + while (aFreq < tFreq && ge < alphaSize-1) {
1.294 + ge++;
1.295 + aFreq += s->mtfFreq[ge];
1.296 + }
1.297 +
1.298 + if (ge > gs
1.299 + && nPart != nGroups && nPart != 1
1.300 + && ((nGroups-nPart) % 2 == 1)) {
1.301 + aFreq -= s->mtfFreq[ge];
1.302 + ge--;
1.303 + }
1.304 +
1.305 + if (s->verbosity >= 3)
1.306 + VPrintf5( " initial group %d, [%d .. %d], "
1.307 + "has %d syms (%4.1f%%)\n",
1.308 + nPart, gs, ge, aFreq,
1.309 + (100.0 * (float)aFreq) / (float)(s->nMTF) );
1.310 +
1.311 + for (v = 0; v < alphaSize; v++)
1.312 + if (v >= gs && v <= ge)
1.313 + s->len[nPart-1][v] = BZ_LESSER_ICOST; else
1.314 + s->len[nPart-1][v] = BZ_GREATER_ICOST;
1.315 +
1.316 + nPart--;
1.317 + gs = ge+1;
1.318 + remF -= aFreq;
1.319 + }
1.320 + }
1.321 +
1.322 + /*---
1.323 + Iterate up to BZ_N_ITERS times to improve the tables.
1.324 + ---*/
1.325 + for (iter = 0; iter < BZ_N_ITERS; iter++) {
1.326 +
1.327 + for (t = 0; t < nGroups; t++) fave[t] = 0;
1.328 +
1.329 + for (t = 0; t < nGroups; t++)
1.330 + for (v = 0; v < alphaSize; v++)
1.331 + s->rfreq[t][v] = 0;
1.332 +
1.333 + /*---
1.334 + Set up an auxiliary length table which is used to fast-track
1.335 + the common case (nGroups == 6).
1.336 + ---*/
1.337 + if (nGroups == 6) {
1.338 + for (v = 0; v < alphaSize; v++) {
1.339 + s->len_pack[v][0] = (s->len[1][v] << 16) | s->len[0][v];
1.340 + s->len_pack[v][1] = (s->len[3][v] << 16) | s->len[2][v];
1.341 + s->len_pack[v][2] = (s->len[5][v] << 16) | s->len[4][v];
1.342 + }
1.343 + }
1.344 +
1.345 + nSelectors = 0;
1.346 + totc = 0;
1.347 + gs = 0;
1.348 + while (True) {
1.349 +
1.350 + /*--- Set group start & end marks. --*/
1.351 + if (gs >= s->nMTF) break;
1.352 + ge = gs + BZ_G_SIZE - 1;
1.353 + if (ge >= s->nMTF) ge = s->nMTF-1;
1.354 +
1.355 + /*--
1.356 + Calculate the cost of this group as coded
1.357 + by each of the coding tables.
1.358 + --*/
1.359 + for (t = 0; t < nGroups; t++) cost[t] = 0;
1.360 +
1.361 + if (nGroups == 6 && 50 == ge-gs+1) {
1.362 + /*--- fast track the common case ---*/
1.363 + register UInt32 cost01, cost23, cost45;
1.364 + register UInt16 icv;
1.365 + cost01 = cost23 = cost45 = 0;
1.366 +
1.367 +# define BZ_ITER(nn) \
1.368 + icv = mtfv[gs+(nn)]; \
1.369 + cost01 += s->len_pack[icv][0]; \
1.370 + cost23 += s->len_pack[icv][1]; \
1.371 + cost45 += s->len_pack[icv][2]; \
1.372 +
1.373 + BZ_ITER(0); BZ_ITER(1); BZ_ITER(2); BZ_ITER(3); BZ_ITER(4);
1.374 + BZ_ITER(5); BZ_ITER(6); BZ_ITER(7); BZ_ITER(8); BZ_ITER(9);
1.375 + BZ_ITER(10); BZ_ITER(11); BZ_ITER(12); BZ_ITER(13); BZ_ITER(14);
1.376 + BZ_ITER(15); BZ_ITER(16); BZ_ITER(17); BZ_ITER(18); BZ_ITER(19);
1.377 + BZ_ITER(20); BZ_ITER(21); BZ_ITER(22); BZ_ITER(23); BZ_ITER(24);
1.378 + BZ_ITER(25); BZ_ITER(26); BZ_ITER(27); BZ_ITER(28); BZ_ITER(29);
1.379 + BZ_ITER(30); BZ_ITER(31); BZ_ITER(32); BZ_ITER(33); BZ_ITER(34);
1.380 + BZ_ITER(35); BZ_ITER(36); BZ_ITER(37); BZ_ITER(38); BZ_ITER(39);
1.381 + BZ_ITER(40); BZ_ITER(41); BZ_ITER(42); BZ_ITER(43); BZ_ITER(44);
1.382 + BZ_ITER(45); BZ_ITER(46); BZ_ITER(47); BZ_ITER(48); BZ_ITER(49);
1.383 +
1.384 +# undef BZ_ITER
1.385 +
1.386 + cost[0] = cost01 & 0xffff; cost[1] = cost01 >> 16;
1.387 + cost[2] = cost23 & 0xffff; cost[3] = cost23 >> 16;
1.388 + cost[4] = cost45 & 0xffff; cost[5] = cost45 >> 16;
1.389 +
1.390 + } else {
1.391 + /*--- slow version which correctly handles all situations ---*/
1.392 + for (i = gs; i <= ge; i++) {
1.393 + UInt16 icv = mtfv[i];
1.394 + for (t = 0; t < nGroups; t++) cost[t] += s->len[t][icv];
1.395 + }
1.396 + }
1.397 +
1.398 + /*--
1.399 + Find the coding table which is best for this group,
1.400 + and record its identity in the selector table.
1.401 + --*/
1.402 + bc = 999999999; bt = -1;
1.403 + for (t = 0; t < nGroups; t++)
1.404 + if (cost[t] < bc) { bc = cost[t]; bt = t; };
1.405 + totc += bc;
1.406 + fave[bt]++;
1.407 + s->selector[nSelectors] = bt;
1.408 + nSelectors++;
1.409 +
1.410 + /*--
1.411 + Increment the symbol frequencies for the selected table.
1.412 + --*/
1.413 + if (nGroups == 6 && 50 == ge-gs+1) {
1.414 + /*--- fast track the common case ---*/
1.415 +
1.416 +# define BZ_ITUR(nn) s->rfreq[bt][ mtfv[gs+(nn)] ]++
1.417 +
1.418 + BZ_ITUR(0); BZ_ITUR(1); BZ_ITUR(2); BZ_ITUR(3); BZ_ITUR(4);
1.419 + BZ_ITUR(5); BZ_ITUR(6); BZ_ITUR(7); BZ_ITUR(8); BZ_ITUR(9);
1.420 + BZ_ITUR(10); BZ_ITUR(11); BZ_ITUR(12); BZ_ITUR(13); BZ_ITUR(14);
1.421 + BZ_ITUR(15); BZ_ITUR(16); BZ_ITUR(17); BZ_ITUR(18); BZ_ITUR(19);
1.422 + BZ_ITUR(20); BZ_ITUR(21); BZ_ITUR(22); BZ_ITUR(23); BZ_ITUR(24);
1.423 + BZ_ITUR(25); BZ_ITUR(26); BZ_ITUR(27); BZ_ITUR(28); BZ_ITUR(29);
1.424 + BZ_ITUR(30); BZ_ITUR(31); BZ_ITUR(32); BZ_ITUR(33); BZ_ITUR(34);
1.425 + BZ_ITUR(35); BZ_ITUR(36); BZ_ITUR(37); BZ_ITUR(38); BZ_ITUR(39);
1.426 + BZ_ITUR(40); BZ_ITUR(41); BZ_ITUR(42); BZ_ITUR(43); BZ_ITUR(44);
1.427 + BZ_ITUR(45); BZ_ITUR(46); BZ_ITUR(47); BZ_ITUR(48); BZ_ITUR(49);
1.428 +
1.429 +# undef BZ_ITUR
1.430 +
1.431 + } else {
1.432 + /*--- slow version which correctly handles all situations ---*/
1.433 + for (i = gs; i <= ge; i++)
1.434 + s->rfreq[bt][ mtfv[i] ]++;
1.435 + }
1.436 +
1.437 + gs = ge+1;
1.438 + }
1.439 + if (s->verbosity >= 3) {
1.440 + VPrintf2 ( " pass %d: size is %d, grp uses are ",
1.441 + iter+1, totc/8 );
1.442 + for (t = 0; t < nGroups; t++)
1.443 + VPrintf1 ( "%d ", fave[t] );
1.444 + VPrintf0 ( "\n" );
1.445 + }
1.446 +
1.447 + /*--
1.448 + Recompute the tables based on the accumulated frequencies.
1.449 + --*/
1.450 + /* maxLen was changed from 20 to 17 in bzip2-1.0.3. See
1.451 + comment in huffman.c for details. */
1.452 + for (t = 0; t < nGroups; t++)
1.453 + BZ2_hbMakeCodeLengths ( &(s->len[t][0]), &(s->rfreq[t][0]),
1.454 + alphaSize, 17 /*20*/ );
1.455 + }
1.456 +
1.457 +
1.458 + AssertH( nGroups < 8, 3002 );
1.459 + AssertH( nSelectors < 32768 &&
1.460 + nSelectors <= (2 + (900000 / BZ_G_SIZE)),
1.461 + 3003 );
1.462 +
1.463 +
1.464 + /*--- Compute MTF values for the selectors. ---*/
1.465 + {
1.466 + UChar pos[BZ_N_GROUPS], ll_i, tmp2, tmp;
1.467 + for (i = 0; i < nGroups; i++) pos[i] = i;
1.468 + for (i = 0; i < nSelectors; i++) {
1.469 + ll_i = s->selector[i];
1.470 + j = 0;
1.471 + tmp = pos[j];
1.472 + while ( ll_i != tmp ) {
1.473 + j++;
1.474 + tmp2 = tmp;
1.475 + tmp = pos[j];
1.476 + pos[j] = tmp2;
1.477 + };
1.478 + pos[0] = tmp;
1.479 + s->selectorMtf[i] = j;
1.480 + }
1.481 + };
1.482 +
1.483 + /*--- Assign actual codes for the tables. --*/
1.484 + for (t = 0; t < nGroups; t++) {
1.485 + minLen = 32;
1.486 + maxLen = 0;
1.487 + for (i = 0; i < alphaSize; i++) {
1.488 + if (s->len[t][i] > maxLen) maxLen = s->len[t][i];
1.489 + if (s->len[t][i] < minLen) minLen = s->len[t][i];
1.490 + }
1.491 + AssertH ( !(maxLen > 17 /*20*/ ), 3004 );
1.492 + AssertH ( !(minLen < 1), 3005 );
1.493 + BZ2_hbAssignCodes ( &(s->code[t][0]), &(s->len[t][0]),
1.494 + minLen, maxLen, alphaSize );
1.495 + }
1.496 +
1.497 + /*--- Transmit the mapping table. ---*/
1.498 + {
1.499 + Bool inUse16[16];
1.500 + for (i = 0; i < 16; i++) {
1.501 + inUse16[i] = False;
1.502 + for (j = 0; j < 16; j++)
1.503 + if (s->inUse[i * 16 + j]) inUse16[i] = True;
1.504 + }
1.505 +
1.506 + nBytes = s->numZ;
1.507 + for (i = 0; i < 16; i++)
1.508 + if (inUse16[i]) bsW(s,1,1); else bsW(s,1,0);
1.509 +
1.510 + for (i = 0; i < 16; i++)
1.511 + if (inUse16[i])
1.512 + for (j = 0; j < 16; j++) {
1.513 + if (s->inUse[i * 16 + j]) bsW(s,1,1); else bsW(s,1,0);
1.514 + }
1.515 +
1.516 + if (s->verbosity >= 3)
1.517 + VPrintf1( " bytes: mapping %d, ", s->numZ-nBytes );
1.518 + }
1.519 +
1.520 + /*--- Now the selectors. ---*/
1.521 + nBytes = s->numZ;
1.522 + bsW ( s, 3, nGroups );
1.523 + bsW ( s, 15, nSelectors );
1.524 + for (i = 0; i < nSelectors; i++) {
1.525 + for (j = 0; j < s->selectorMtf[i]; j++) bsW(s,1,1);
1.526 + bsW(s,1,0);
1.527 + }
1.528 + if (s->verbosity >= 3)
1.529 + VPrintf1( "selectors %d, ", s->numZ-nBytes );
1.530 +
1.531 + /*--- Now the coding tables. ---*/
1.532 + nBytes = s->numZ;
1.533 +
1.534 + for (t = 0; t < nGroups; t++) {
1.535 + Int32 curr = s->len[t][0];
1.536 + bsW ( s, 5, curr );
1.537 + for (i = 0; i < alphaSize; i++) {
1.538 + while (curr < s->len[t][i]) { bsW(s,2,2); curr++; /* 10 */ };
1.539 + while (curr > s->len[t][i]) { bsW(s,2,3); curr--; /* 11 */ };
1.540 + bsW ( s, 1, 0 );
1.541 + }
1.542 + }
1.543 +
1.544 + if (s->verbosity >= 3)
1.545 + VPrintf1 ( "code lengths %d, ", s->numZ-nBytes );
1.546 +
1.547 + /*--- And finally, the block data proper ---*/
1.548 + nBytes = s->numZ;
1.549 + selCtr = 0;
1.550 + gs = 0;
1.551 + while (True) {
1.552 + if (gs >= s->nMTF) break;
1.553 + ge = gs + BZ_G_SIZE - 1;
1.554 + if (ge >= s->nMTF) ge = s->nMTF-1;
1.555 + AssertH ( s->selector[selCtr] < nGroups, 3006 );
1.556 +
1.557 + if (nGroups == 6 && 50 == ge-gs+1) {
1.558 + /*--- fast track the common case ---*/
1.559 + UInt16 mtfv_i;
1.560 + UChar* s_len_sel_selCtr
1.561 + = &(s->len[s->selector[selCtr]][0]);
1.562 + Int32* s_code_sel_selCtr
1.563 + = &(s->code[s->selector[selCtr]][0]);
1.564 +
1.565 +# define BZ_ITAH(nn) \
1.566 + mtfv_i = mtfv[gs+(nn)]; \
1.567 + bsW ( s, \
1.568 + s_len_sel_selCtr[mtfv_i], \
1.569 + s_code_sel_selCtr[mtfv_i] )
1.570 +
1.571 + BZ_ITAH(0); BZ_ITAH(1); BZ_ITAH(2); BZ_ITAH(3); BZ_ITAH(4);
1.572 + BZ_ITAH(5); BZ_ITAH(6); BZ_ITAH(7); BZ_ITAH(8); BZ_ITAH(9);
1.573 + BZ_ITAH(10); BZ_ITAH(11); BZ_ITAH(12); BZ_ITAH(13); BZ_ITAH(14);
1.574 + BZ_ITAH(15); BZ_ITAH(16); BZ_ITAH(17); BZ_ITAH(18); BZ_ITAH(19);
1.575 + BZ_ITAH(20); BZ_ITAH(21); BZ_ITAH(22); BZ_ITAH(23); BZ_ITAH(24);
1.576 + BZ_ITAH(25); BZ_ITAH(26); BZ_ITAH(27); BZ_ITAH(28); BZ_ITAH(29);
1.577 + BZ_ITAH(30); BZ_ITAH(31); BZ_ITAH(32); BZ_ITAH(33); BZ_ITAH(34);
1.578 + BZ_ITAH(35); BZ_ITAH(36); BZ_ITAH(37); BZ_ITAH(38); BZ_ITAH(39);
1.579 + BZ_ITAH(40); BZ_ITAH(41); BZ_ITAH(42); BZ_ITAH(43); BZ_ITAH(44);
1.580 + BZ_ITAH(45); BZ_ITAH(46); BZ_ITAH(47); BZ_ITAH(48); BZ_ITAH(49);
1.581 +
1.582 +# undef BZ_ITAH
1.583 +
1.584 + } else {
1.585 + /*--- slow version which correctly handles all situations ---*/
1.586 + for (i = gs; i <= ge; i++) {
1.587 + bsW ( s,
1.588 + s->len [s->selector[selCtr]] [mtfv[i]],
1.589 + s->code [s->selector[selCtr]] [mtfv[i]] );
1.590 + }
1.591 + }
1.592 +
1.593 +
1.594 + gs = ge+1;
1.595 + selCtr++;
1.596 + }
1.597 + AssertH( selCtr == nSelectors, 3007 );
1.598 +
1.599 + if (s->verbosity >= 3)
1.600 + VPrintf1( "codes %d\n", s->numZ-nBytes );
1.601 +}
1.602 +
1.603 +
1.604 +/*---------------------------------------------------*/
1.605 +void BZ2_compressBlock ( EState* s, Bool is_last_block )
1.606 +{
1.607 + if (s->nblock > 0) {
1.608 +
1.609 + BZ_FINALISE_CRC ( s->blockCRC );
1.610 + s->combinedCRC = (s->combinedCRC << 1) | (s->combinedCRC >> 31);
1.611 + s->combinedCRC ^= s->blockCRC;
1.612 + if (s->blockNo > 1) s->numZ = 0;
1.613 +
1.614 + if (s->verbosity >= 2)
1.615 + VPrintf4( " block %d: crc = 0x%08x, "
1.616 + "combined CRC = 0x%08x, size = %d\n",
1.617 + s->blockNo, s->blockCRC, s->combinedCRC, s->nblock );
1.618 +
1.619 + BZ2_blockSort ( s );
1.620 + }
1.621 +
1.622 + s->zbits = (UChar*) (&((UChar*)s->arr2)[s->nblock]);
1.623 +
1.624 + /*-- If this is the first block, create the stream header. --*/
1.625 + if (s->blockNo == 1) {
1.626 + BZ2_bsInitWrite ( s );
1.627 + bsPutUChar ( s, BZ_HDR_B );
1.628 + bsPutUChar ( s, BZ_HDR_Z );
1.629 + bsPutUChar ( s, BZ_HDR_h );
1.630 + bsPutUChar ( s, (UChar)(BZ_HDR_0 + s->blockSize100k) );
1.631 + }
1.632 +
1.633 + if (s->nblock > 0) {
1.634 +
1.635 + bsPutUChar ( s, 0x31 ); bsPutUChar ( s, 0x41 );
1.636 + bsPutUChar ( s, 0x59 ); bsPutUChar ( s, 0x26 );
1.637 + bsPutUChar ( s, 0x53 ); bsPutUChar ( s, 0x59 );
1.638 +
1.639 + /*-- Now the block's CRC, so it is in a known place. --*/
1.640 + bsPutUInt32 ( s, s->blockCRC );
1.641 +
1.642 + /*--
1.643 + Now a single bit indicating (non-)randomisation.
1.644 + As of version 0.9.5, we use a better sorting algorithm
1.645 + which makes randomisation unnecessary. So always set
1.646 + the randomised bit to 'no'. Of course, the decoder
1.647 + still needs to be able to handle randomised blocks
1.648 + so as to maintain backwards compatibility with
1.649 + older versions of bzip2.
1.650 + --*/
1.651 + bsW(s,1,0);
1.652 +
1.653 + bsW ( s, 24, s->origPtr );
1.654 + generateMTFValues ( s );
1.655 + sendMTFValues ( s );
1.656 + }
1.657 +
1.658 +
1.659 + /*-- If this is the last block, add the stream trailer. --*/
1.660 + if (is_last_block) {
1.661 +
1.662 + bsPutUChar ( s, 0x17 ); bsPutUChar ( s, 0x72 );
1.663 + bsPutUChar ( s, 0x45 ); bsPutUChar ( s, 0x38 );
1.664 + bsPutUChar ( s, 0x50 ); bsPutUChar ( s, 0x90 );
1.665 + bsPutUInt32 ( s, s->combinedCRC );
1.666 + if (s->verbosity >= 2)
1.667 + VPrintf1( " final combined CRC = 0x%08x\n ", s->combinedCRC );
1.668 + bsFinishWrite ( s );
1.669 + }
1.670 +}
1.671 +
1.672 +
1.673 +/*-------------------------------------------------------------*/
1.674 +/*--- end compress.c ---*/
1.675 +/*-------------------------------------------------------------*/
