LLVM API Documentation
00001 00002 /*-------------------------------------------------------------*/ 00003 /*--- Compression machinery (not incl block sorting) ---*/ 00004 /*--- compress.c ---*/ 00005 /*-------------------------------------------------------------*/ 00006 00007 /*-- 00008 This file is a part of bzip2 and/or libbzip2, a program and 00009 library for lossless, block-sorting data compression. 00010 00011 Copyright (C) 1996-2002 Julian R Seward. All rights reserved. 00012 00013 Redistribution and use in source and binary forms, with or without 00014 modification, are permitted provided that the following conditions 00015 are met: 00016 00017 1. Redistributions of source code must retain the above copyright 00018 notice, this list of conditions and the following disclaimer. 00019 00020 2. The origin of this software must not be misrepresented; you must 00021 not claim that you wrote the original software. If you use this 00022 software in a product, an acknowledgment in the product 00023 documentation would be appreciated but is not required. 00024 00025 3. Altered source versions must be plainly marked as such, and must 00026 not be misrepresented as being the original software. 00027 00028 4. The name of the author may not be used to endorse or promote 00029 products derived from this software without specific prior written 00030 permission. 00031 00032 THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS 00033 OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 00034 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 00035 ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY 00036 DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 00037 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE 00038 GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 00039 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, 00040 WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 00041 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 00042 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 00043 00044 Julian Seward, Cambridge, UK. 00045 jseward@acm.org 00046 bzip2/libbzip2 version 1.0 of 21 March 2000 00047 00048 This program is based on (at least) the work of: 00049 Mike Burrows 00050 David Wheeler 00051 Peter Fenwick 00052 Alistair Moffat 00053 Radford Neal 00054 Ian H. Witten 00055 Robert Sedgewick 00056 Jon L. Bentley 00057 00058 For more information on these sources, see the manual. 00059 --*/ 00060 00061 /*-- 00062 CHANGES 00063 ~~~~~~~ 00064 0.9.0 -- original version. 00065 00066 0.9.0a/b -- no changes in this file. 00067 00068 0.9.0c 00069 * changed setting of nGroups in sendMTFValues() so as to 00070 do a bit better on small files 00071 --*/ 00072 00073 #include "bzlib_private.h" 00074 00075 00076 /*---------------------------------------------------*/ 00077 /*--- Bit stream I/O ---*/ 00078 /*---------------------------------------------------*/ 00079 00080 /*---------------------------------------------------*/ 00081 void BZ2_bsInitWrite ( EState* s ) 00082 { 00083 s->bsLive = 0; 00084 s->bsBuff = 0; 00085 } 00086 00087 00088 /*---------------------------------------------------*/ 00089 static 00090 void bsFinishWrite ( EState* s ) 00091 { 00092 while (s->bsLive > 0) { 00093 s->zbits[s->numZ] = (UChar)(s->bsBuff >> 24); 00094 s->numZ++; 00095 s->bsBuff <<= 8; 00096 s->bsLive -= 8; 00097 } 00098 } 00099 00100 00101 /*---------------------------------------------------*/ 00102 #define bsNEEDW(nz) \ 00103 { \ 00104 while (s->bsLive >= 8) { \ 00105 s->zbits[s->numZ] \ 00106 = (UChar)(s->bsBuff >> 24); \ 00107 s->numZ++; \ 00108 s->bsBuff <<= 8; \ 00109 s->bsLive -= 8; \ 00110 } \ 00111 } 00112 00113 00114 /*---------------------------------------------------*/ 00115 static 00116 __inline__ 00117 void bsW ( EState* s, Int32 n, UInt32 v ) 00118 { 00119 bsNEEDW ( n ); 00120 s->bsBuff |= (v << (32 - s->bsLive - n)); 00121 s->bsLive += n; 00122 } 00123 00124 00125 /*---------------------------------------------------*/ 00126 static 00127 void bsPutUInt32 ( EState* s, UInt32 u ) 00128 { 00129 bsW ( s, 8, (u >> 24) & 0xffL ); 00130 bsW ( s, 8, (u >> 16) & 0xffL ); 00131 bsW ( s, 8, (u >> 8) & 0xffL ); 00132 bsW ( s, 8, u & 0xffL ); 00133 } 00134 00135 00136 /*---------------------------------------------------*/ 00137 static 00138 void bsPutUChar ( EState* s, UChar c ) 00139 { 00140 bsW( s, 8, (UInt32)c ); 00141 } 00142 00143 00144 /*---------------------------------------------------*/ 00145 /*--- The back end proper ---*/ 00146 /*---------------------------------------------------*/ 00147 00148 /*---------------------------------------------------*/ 00149 static 00150 void makeMaps_e ( EState* s ) 00151 { 00152 Int32 i; 00153 s->nInUse = 0; 00154 for (i = 0; i < 256; i++) 00155 if (s->inUse[i]) { 00156 s->unseqToSeq[i] = s->nInUse; 00157 s->nInUse++; 00158 } 00159 } 00160 00161 00162 /*---------------------------------------------------*/ 00163 static 00164 void generateMTFValues ( EState* s ) 00165 { 00166 UChar yy[256]; 00167 Int32 i, j; 00168 Int32 zPend; 00169 Int32 wr; 00170 Int32 EOB; 00171 00172 /* 00173 After sorting (eg, here), 00174 s->arr1 [ 0 .. s->nblock-1 ] holds sorted order, 00175 and 00176 ((UChar*)s->arr2) [ 0 .. s->nblock-1 ] 00177 holds the original block data. 00178 00179 The first thing to do is generate the MTF values, 00180 and put them in 00181 ((UInt16*)s->arr1) [ 0 .. s->nblock-1 ]. 00182 Because there are strictly fewer or equal MTF values 00183 than block values, ptr values in this area are overwritten 00184 with MTF values only when they are no longer needed. 00185 00186 The final compressed bitstream is generated into the 00187 area starting at 00188 (UChar*) (&((UChar*)s->arr2)[s->nblock]) 00189 00190 These storage aliases are set up in bzCompressInit(), 00191 except for the last one, which is arranged in 00192 compressBlock(). 00193 */ 00194 UInt32* ptr = s->ptr; 00195 UChar* block = s->block; 00196 UInt16* mtfv = s->mtfv; 00197 00198 makeMaps_e ( s ); 00199 EOB = s->nInUse+1; 00200 00201 for (i = 0; i <= EOB; i++) s->mtfFreq[i] = 0; 00202 00203 wr = 0; 00204 zPend = 0; 00205 for (i = 0; i < s->nInUse; i++) yy[i] = (UChar) i; 00206 00207 for (i = 0; i < s->nblock; i++) { 00208 UChar ll_i; 00209 AssertD ( wr <= i, "generateMTFValues(1)" ); 00210 j = ptr[i]-1; if (j < 0) j += s->nblock; 00211 ll_i = s->unseqToSeq[block[j]]; 00212 AssertD ( ll_i < s->nInUse, "generateMTFValues(2a)" ); 00213 00214 if (yy[0] == ll_i) { 00215 zPend++; 00216 } else { 00217 00218 if (zPend > 0) { 00219 zPend--; 00220 while (True) { 00221 if (zPend & 1) { 00222 mtfv[wr] = BZ_RUNB; wr++; 00223 s->mtfFreq[BZ_RUNB]++; 00224 } else { 00225 mtfv[wr] = BZ_RUNA; wr++; 00226 s->mtfFreq[BZ_RUNA]++; 00227 } 00228 if (zPend < 2) break; 00229 zPend = (zPend - 2) / 2; 00230 }; 00231 zPend = 0; 00232 } 00233 { 00234 register UChar rtmp; 00235 register UChar* ryy_j; 00236 register UChar rll_i; 00237 rtmp = yy[1]; 00238 yy[1] = yy[0]; 00239 ryy_j = &(yy[1]); 00240 rll_i = ll_i; 00241 while ( rll_i != rtmp ) { 00242 register UChar rtmp2; 00243 ryy_j++; 00244 rtmp2 = rtmp; 00245 rtmp = *ryy_j; 00246 *ryy_j = rtmp2; 00247 }; 00248 yy[0] = rtmp; 00249 j = ryy_j - &(yy[0]); 00250 mtfv[wr] = j+1; wr++; s->mtfFreq[j+1]++; 00251 } 00252 00253 } 00254 } 00255 00256 if (zPend > 0) { 00257 zPend--; 00258 while (True) { 00259 if (zPend & 1) { 00260 mtfv[wr] = BZ_RUNB; wr++; 00261 s->mtfFreq[BZ_RUNB]++; 00262 } else { 00263 mtfv[wr] = BZ_RUNA; wr++; 00264 s->mtfFreq[BZ_RUNA]++; 00265 } 00266 if (zPend < 2) break; 00267 zPend = (zPend - 2) / 2; 00268 }; 00269 zPend = 0; 00270 } 00271 00272 mtfv[wr] = EOB; wr++; s->mtfFreq[EOB]++; 00273 00274 s->nMTF = wr; 00275 } 00276 00277 00278 /*---------------------------------------------------*/ 00279 #define BZ_LESSER_ICOST 0 00280 #define BZ_GREATER_ICOST 15 00281 00282 static 00283 void sendMTFValues ( EState* s ) 00284 { 00285 Int32 v, t, i, j, gs, ge, totc, bt, bc, iter; 00286 Int32 nSelectors, alphaSize, minLen, maxLen, selCtr; 00287 Int32 nGroups, nBytes; 00288 00289 /*-- 00290 UChar len [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; 00291 is a global since the decoder also needs it. 00292 00293 Int32 code[BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; 00294 Int32 rfreq[BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; 00295 are also globals only used in this proc. 00296 Made global to keep stack frame size small. 00297 --*/ 00298 00299 00300 UInt16 cost[BZ_N_GROUPS]; 00301 Int32 fave[BZ_N_GROUPS]; 00302 00303 UInt16* mtfv = s->mtfv; 00304 00305 if (s->verbosity >= 3) 00306 VPrintf3( " %d in block, %d after MTF & 1-2 coding, " 00307 "%d+2 syms in use\n", 00308 s->nblock, s->nMTF, s->nInUse ); 00309 00310 alphaSize = s->nInUse+2; 00311 for (t = 0; t < BZ_N_GROUPS; t++) 00312 for (v = 0; v < alphaSize; v++) 00313 s->len[t][v] = BZ_GREATER_ICOST; 00314 00315 /*--- Decide how many coding tables to use ---*/ 00316 AssertH ( s->nMTF > 0, 3001 ); 00317 if (s->nMTF < 200) nGroups = 2; else 00318 if (s->nMTF < 600) nGroups = 3; else 00319 if (s->nMTF < 1200) nGroups = 4; else 00320 if (s->nMTF < 2400) nGroups = 5; else 00321 nGroups = 6; 00322 00323 /*--- Generate an initial set of coding tables ---*/ 00324 { 00325 Int32 nPart, remF, tFreq, aFreq; 00326 00327 nPart = nGroups; 00328 remF = s->nMTF; 00329 gs = 0; 00330 while (nPart > 0) { 00331 tFreq = remF / nPart; 00332 ge = gs-1; 00333 aFreq = 0; 00334 while (aFreq < tFreq && ge < alphaSize-1) { 00335 ge++; 00336 aFreq += s->mtfFreq[ge]; 00337 } 00338 00339 if (ge > gs 00340 && nPart != nGroups && nPart != 1 00341 && ((nGroups-nPart) % 2 == 1)) { 00342 aFreq -= s->mtfFreq[ge]; 00343 ge--; 00344 } 00345 00346 if (s->verbosity >= 3) 00347 VPrintf5( " initial group %d, [%d .. %d], " 00348 "has %d syms (%4.1f%%)\n", 00349 nPart, gs, ge, aFreq, 00350 (100.0 * (float)aFreq) / (float)(s->nMTF) ); 00351 00352 for (v = 0; v < alphaSize; v++) 00353 if (v >= gs && v <= ge) 00354 s->len[nPart-1][v] = BZ_LESSER_ICOST; else 00355 s->len[nPart-1][v] = BZ_GREATER_ICOST; 00356 00357 nPart--; 00358 gs = ge+1; 00359 remF -= aFreq; 00360 } 00361 } 00362 00363 /*--- 00364 Iterate up to BZ_N_ITERS times to improve the tables. 00365 ---*/ 00366 for (iter = 0; iter < BZ_N_ITERS; iter++) { 00367 00368 for (t = 0; t < nGroups; t++) fave[t] = 0; 00369 00370 for (t = 0; t < nGroups; t++) 00371 for (v = 0; v < alphaSize; v++) 00372 s->rfreq[t][v] = 0; 00373 00374 /*--- 00375 Set up an auxiliary length table which is used to fast-track 00376 the common case (nGroups == 6). 00377 ---*/ 00378 if (nGroups == 6) { 00379 for (v = 0; v < alphaSize; v++) { 00380 s->len_pack[v][0] = (s->len[1][v] << 16) | s->len[0][v]; 00381 s->len_pack[v][1] = (s->len[3][v] << 16) | s->len[2][v]; 00382 s->len_pack[v][2] = (s->len[5][v] << 16) | s->len[4][v]; 00383 } 00384 } 00385 00386 nSelectors = 0; 00387 totc = 0; 00388 gs = 0; 00389 while (True) { 00390 00391 /*--- Set group start & end marks. --*/ 00392 if (gs >= s->nMTF) break; 00393 ge = gs + BZ_G_SIZE - 1; 00394 if (ge >= s->nMTF) ge = s->nMTF-1; 00395 00396 /*-- 00397 Calculate the cost of this group as coded 00398 by each of the coding tables. 00399 --*/ 00400 for (t = 0; t < nGroups; t++) cost[t] = 0; 00401 00402 if (nGroups == 6 && 50 == ge-gs+1) { 00403 /*--- fast track the common case ---*/ 00404 register UInt32 cost01, cost23, cost45; 00405 register UInt16 icv; 00406 cost01 = cost23 = cost45 = 0; 00407 00408 # define BZ_ITER(nn) \ 00409 icv = mtfv[gs+(nn)]; \ 00410 cost01 += s->len_pack[icv][0]; \ 00411 cost23 += s->len_pack[icv][1]; \ 00412 cost45 += s->len_pack[icv][2]; \ 00413 00414 BZ_ITER(0); BZ_ITER(1); BZ_ITER(2); BZ_ITER(3); BZ_ITER(4); 00415 BZ_ITER(5); BZ_ITER(6); BZ_ITER(7); BZ_ITER(8); BZ_ITER(9); 00416 BZ_ITER(10); BZ_ITER(11); BZ_ITER(12); BZ_ITER(13); BZ_ITER(14); 00417 BZ_ITER(15); BZ_ITER(16); BZ_ITER(17); BZ_ITER(18); BZ_ITER(19); 00418 BZ_ITER(20); BZ_ITER(21); BZ_ITER(22); BZ_ITER(23); BZ_ITER(24); 00419 BZ_ITER(25); BZ_ITER(26); BZ_ITER(27); BZ_ITER(28); BZ_ITER(29); 00420 BZ_ITER(30); BZ_ITER(31); BZ_ITER(32); BZ_ITER(33); BZ_ITER(34); 00421 BZ_ITER(35); BZ_ITER(36); BZ_ITER(37); BZ_ITER(38); BZ_ITER(39); 00422 BZ_ITER(40); BZ_ITER(41); BZ_ITER(42); BZ_ITER(43); BZ_ITER(44); 00423 BZ_ITER(45); BZ_ITER(46); BZ_ITER(47); BZ_ITER(48); BZ_ITER(49); 00424 00425 # undef BZ_ITER 00426 00427 cost[0] = cost01 & 0xffff; cost[1] = cost01 >> 16; 00428 cost[2] = cost23 & 0xffff; cost[3] = cost23 >> 16; 00429 cost[4] = cost45 & 0xffff; cost[5] = cost45 >> 16; 00430 00431 } else { 00432 /*--- slow version which correctly handles all situations ---*/ 00433 for (i = gs; i <= ge; i++) { 00434 UInt16 icv = mtfv[i]; 00435 for (t = 0; t < nGroups; t++) cost[t] += s->len[t][icv]; 00436 } 00437 } 00438 00439 /*-- 00440 Find the coding table which is best for this group, 00441 and record its identity in the selector table. 00442 --*/ 00443 bc = 999999999; bt = -1; 00444 for (t = 0; t < nGroups; t++) 00445 if (cost[t] < bc) { bc = cost[t]; bt = t; }; 00446 totc += bc; 00447 fave[bt]++; 00448 s->selector[nSelectors] = bt; 00449 nSelectors++; 00450 00451 /*-- 00452 Increment the symbol frequencies for the selected table. 00453 --*/ 00454 if (nGroups == 6 && 50 == ge-gs+1) { 00455 /*--- fast track the common case ---*/ 00456 00457 # define BZ_ITUR(nn) s->rfreq[bt][ mtfv[gs+(nn)] ]++ 00458 00459 BZ_ITUR(0); BZ_ITUR(1); BZ_ITUR(2); BZ_ITUR(3); BZ_ITUR(4); 00460 BZ_ITUR(5); BZ_ITUR(6); BZ_ITUR(7); BZ_ITUR(8); BZ_ITUR(9); 00461 BZ_ITUR(10); BZ_ITUR(11); BZ_ITUR(12); BZ_ITUR(13); BZ_ITUR(14); 00462 BZ_ITUR(15); BZ_ITUR(16); BZ_ITUR(17); BZ_ITUR(18); BZ_ITUR(19); 00463 BZ_ITUR(20); BZ_ITUR(21); BZ_ITUR(22); BZ_ITUR(23); BZ_ITUR(24); 00464 BZ_ITUR(25); BZ_ITUR(26); BZ_ITUR(27); BZ_ITUR(28); BZ_ITUR(29); 00465 BZ_ITUR(30); BZ_ITUR(31); BZ_ITUR(32); BZ_ITUR(33); BZ_ITUR(34); 00466 BZ_ITUR(35); BZ_ITUR(36); BZ_ITUR(37); BZ_ITUR(38); BZ_ITUR(39); 00467 BZ_ITUR(40); BZ_ITUR(41); BZ_ITUR(42); BZ_ITUR(43); BZ_ITUR(44); 00468 BZ_ITUR(45); BZ_ITUR(46); BZ_ITUR(47); BZ_ITUR(48); BZ_ITUR(49); 00469 00470 # undef BZ_ITUR 00471 00472 } else { 00473 /*--- slow version which correctly handles all situations ---*/ 00474 for (i = gs; i <= ge; i++) 00475 s->rfreq[bt][ mtfv[i] ]++; 00476 } 00477 00478 gs = ge+1; 00479 } 00480 if (s->verbosity >= 3) { 00481 VPrintf2 ( " pass %d: size is %d, grp uses are ", 00482 iter+1, totc/8 ); 00483 for (t = 0; t < nGroups; t++) 00484 VPrintf1 ( "%d ", fave[t] ); 00485 VPrintf0 ( "\n" ); 00486 } 00487 00488 /*-- 00489 Recompute the tables based on the accumulated frequencies. 00490 --*/ 00491 for (t = 0; t < nGroups; t++) 00492 BZ2_hbMakeCodeLengths ( &(s->len[t][0]), &(s->rfreq[t][0]), 00493 alphaSize, 20 ); 00494 } 00495 00496 00497 AssertH( nGroups < 8, 3002 ); 00498 AssertH( nSelectors < 32768 && 00499 nSelectors <= (2 + (900000 / BZ_G_SIZE)), 00500 3003 ); 00501 00502 00503 /*--- Compute MTF values for the selectors. ---*/ 00504 { 00505 UChar pos[BZ_N_GROUPS], ll_i, tmp2, tmp; 00506 for (i = 0; i < nGroups; i++) pos[i] = i; 00507 for (i = 0; i < nSelectors; i++) { 00508 ll_i = s->selector[i]; 00509 j = 0; 00510 tmp = pos[j]; 00511 while ( ll_i != tmp ) { 00512 j++; 00513 tmp2 = tmp; 00514 tmp = pos[j]; 00515 pos[j] = tmp2; 00516 }; 00517 pos[0] = tmp; 00518 s->selectorMtf[i] = j; 00519 } 00520 }; 00521 00522 /*--- Assign actual codes for the tables. --*/ 00523 for (t = 0; t < nGroups; t++) { 00524 minLen = 32; 00525 maxLen = 0; 00526 for (i = 0; i < alphaSize; i++) { 00527 if (s->len[t][i] > maxLen) maxLen = s->len[t][i]; 00528 if (s->len[t][i] < minLen) minLen = s->len[t][i]; 00529 } 00530 AssertH ( !(maxLen > 20), 3004 ); 00531 AssertH ( !(minLen < 1), 3005 ); 00532 BZ2_hbAssignCodes ( &(s->code[t][0]), &(s->len[t][0]), 00533 minLen, maxLen, alphaSize ); 00534 } 00535 00536 /*--- Transmit the mapping table. ---*/ 00537 { 00538 Bool inUse16[16]; 00539 for (i = 0; i < 16; i++) { 00540 inUse16[i] = False; 00541 for (j = 0; j < 16; j++) 00542 if (s->inUse[i * 16 + j]) inUse16[i] = True; 00543 } 00544 00545 nBytes = s->numZ; 00546 for (i = 0; i < 16; i++) 00547 if (inUse16[i]) bsW(s,1,1); else bsW(s,1,0); 00548 00549 for (i = 0; i < 16; i++) 00550 if (inUse16[i]) 00551 for (j = 0; j < 16; j++) { 00552 if (s->inUse[i * 16 + j]) bsW(s,1,1); else bsW(s,1,0); 00553 } 00554 00555 if (s->verbosity >= 3) 00556 VPrintf1( " bytes: mapping %d, ", s->numZ-nBytes ); 00557 } 00558 00559 /*--- Now the selectors. ---*/ 00560 nBytes = s->numZ; 00561 bsW ( s, 3, nGroups ); 00562 bsW ( s, 15, nSelectors ); 00563 for (i = 0; i < nSelectors; i++) { 00564 for (j = 0; j < s->selectorMtf[i]; j++) bsW(s,1,1); 00565 bsW(s,1,0); 00566 } 00567 if (s->verbosity >= 3) 00568 VPrintf1( "selectors %d, ", s->numZ-nBytes ); 00569 00570 /*--- Now the coding tables. ---*/ 00571 nBytes = s->numZ; 00572 00573 for (t = 0; t < nGroups; t++) { 00574 Int32 curr = s->len[t][0]; 00575 bsW ( s, 5, curr ); 00576 for (i = 0; i < alphaSize; i++) { 00577 while (curr < s->len[t][i]) { bsW(s,2,2); curr++; /* 10 */ }; 00578 while (curr > s->len[t][i]) { bsW(s,2,3); curr--; /* 11 */ }; 00579 bsW ( s, 1, 0 ); 00580 } 00581 } 00582 00583 if (s->verbosity >= 3) 00584 VPrintf1 ( "code lengths %d, ", s->numZ-nBytes ); 00585 00586 /*--- And finally, the block data proper ---*/ 00587 nBytes = s->numZ; 00588 selCtr = 0; 00589 gs = 0; 00590 while (True) { 00591 if (gs >= s->nMTF) break; 00592 ge = gs + BZ_G_SIZE - 1; 00593 if (ge >= s->nMTF) ge = s->nMTF-1; 00594 AssertH ( s->selector[selCtr] < nGroups, 3006 ); 00595 00596 if (nGroups == 6 && 50 == ge-gs+1) { 00597 /*--- fast track the common case ---*/ 00598 UInt16 mtfv_i; 00599 UChar* s_len_sel_selCtr 00600 = &(s->len[s->selector[selCtr]][0]); 00601 Int32* s_code_sel_selCtr 00602 = &(s->code[s->selector[selCtr]][0]); 00603 00604 # define BZ_ITAH(nn) \ 00605 mtfv_i = mtfv[gs+(nn)]; \ 00606 bsW ( s, \ 00607 s_len_sel_selCtr[mtfv_i], \ 00608 s_code_sel_selCtr[mtfv_i] ) 00609 00610 BZ_ITAH(0); BZ_ITAH(1); BZ_ITAH(2); BZ_ITAH(3); BZ_ITAH(4); 00611 BZ_ITAH(5); BZ_ITAH(6); BZ_ITAH(7); BZ_ITAH(8); BZ_ITAH(9); 00612 BZ_ITAH(10); BZ_ITAH(11); BZ_ITAH(12); BZ_ITAH(13); BZ_ITAH(14); 00613 BZ_ITAH(15); BZ_ITAH(16); BZ_ITAH(17); BZ_ITAH(18); BZ_ITAH(19); 00614 BZ_ITAH(20); BZ_ITAH(21); BZ_ITAH(22); BZ_ITAH(23); BZ_ITAH(24); 00615 BZ_ITAH(25); BZ_ITAH(26); BZ_ITAH(27); BZ_ITAH(28); BZ_ITAH(29); 00616 BZ_ITAH(30); BZ_ITAH(31); BZ_ITAH(32); BZ_ITAH(33); BZ_ITAH(34); 00617 BZ_ITAH(35); BZ_ITAH(36); BZ_ITAH(37); BZ_ITAH(38); BZ_ITAH(39); 00618 BZ_ITAH(40); BZ_ITAH(41); BZ_ITAH(42); BZ_ITAH(43); BZ_ITAH(44); 00619 BZ_ITAH(45); BZ_ITAH(46); BZ_ITAH(47); BZ_ITAH(48); BZ_ITAH(49); 00620 00621 # undef BZ_ITAH 00622 00623 } else { 00624 /*--- slow version which correctly handles all situations ---*/ 00625 for (i = gs; i <= ge; i++) { 00626 bsW ( s, 00627 s->len [s->selector[selCtr]] [mtfv[i]], 00628 s->code [s->selector[selCtr]] [mtfv[i]] ); 00629 } 00630 } 00631 00632 00633 gs = ge+1; 00634 selCtr++; 00635 } 00636 AssertH( selCtr == nSelectors, 3007 ); 00637 00638 if (s->verbosity >= 3) 00639 VPrintf1( "codes %d\n", s->numZ-nBytes ); 00640 } 00641 00642 00643 /*---------------------------------------------------*/ 00644 void BZ2_compressBlock ( EState* s, Bool is_last_block ) 00645 { 00646 if (s->nblock > 0) { 00647 00648 BZ_FINALISE_CRC ( s->blockCRC ); 00649 s->combinedCRC = (s->combinedCRC << 1) | (s->combinedCRC >> 31); 00650 s->combinedCRC ^= s->blockCRC; 00651 if (s->blockNo > 1) s->numZ = 0; 00652 00653 if (s->verbosity >= 2) 00654 VPrintf4( " block %d: crc = 0x%8x, " 00655 "combined CRC = 0x%8x, size = %d\n", 00656 s->blockNo, s->blockCRC, s->combinedCRC, s->nblock ); 00657 00658 BZ2_blockSort ( s ); 00659 } 00660 00661 s->zbits = (UChar*) (&((UChar*)s->arr2)[s->nblock]); 00662 00663 /*-- If this is the first block, create the stream header. --*/ 00664 if (s->blockNo == 1) { 00665 BZ2_bsInitWrite ( s ); 00666 bsPutUChar ( s, BZ_HDR_B ); 00667 bsPutUChar ( s, BZ_HDR_Z ); 00668 bsPutUChar ( s, BZ_HDR_h ); 00669 bsPutUChar ( s, (UChar)(BZ_HDR_0 + s->blockSize100k) ); 00670 } 00671 00672 if (s->nblock > 0) { 00673 00674 bsPutUChar ( s, 0x31 ); bsPutUChar ( s, 0x41 ); 00675 bsPutUChar ( s, 0x59 ); bsPutUChar ( s, 0x26 ); 00676 bsPutUChar ( s, 0x53 ); bsPutUChar ( s, 0x59 ); 00677 00678 /*-- Now the block's CRC, so it is in a known place. --*/ 00679 bsPutUInt32 ( s, s->blockCRC ); 00680 00681 /*-- 00682 Now a single bit indicating (non-)randomisation. 00683 As of version 0.9.5, we use a better sorting algorithm 00684 which makes randomisation unnecessary. So always set 00685 the randomised bit to 'no'. Of course, the decoder 00686 still needs to be able to handle randomised blocks 00687 so as to maintain backwards compatibility with 00688 older versions of bzip2. 00689 --*/ 00690 bsW(s,1,0); 00691 00692 bsW ( s, 24, s->origPtr ); 00693 generateMTFValues ( s ); 00694 sendMTFValues ( s ); 00695 } 00696 00697 00698 /*-- If this is the last block, add the stream trailer. --*/ 00699 if (is_last_block) { 00700 00701 bsPutUChar ( s, 0x17 ); bsPutUChar ( s, 0x72 ); 00702 bsPutUChar ( s, 0x45 ); bsPutUChar ( s, 0x38 ); 00703 bsPutUChar ( s, 0x50 ); bsPutUChar ( s, 0x90 ); 00704 bsPutUInt32 ( s, s->combinedCRC ); 00705 if (s->verbosity >= 2) 00706 VPrintf1( " final combined CRC = 0x%x\n ", s->combinedCRC ); 00707 bsFinishWrite ( s ); 00708 } 00709 } 00710 00711 00712 /*-------------------------------------------------------------*/ 00713 /*--- end compress.c ---*/ 00714 /*-------------------------------------------------------------*/