archival/libarchive/bz/bzlib.c

   1 /*
   2  * bzip2 is written by Julian Seward <jseward@bzip.org>.
   3  * Adapted for busybox by Denys Vlasenko <vda.linux@googlemail.com>.
   4  * See README and LICENSE files in this directory for more information.
   5  */
   6
   7 /*-------------------------------------------------------------*/
   8 /*--- Library top-level functions.                          ---*/
   9 /*---                                               bzlib.c ---*/
  10 /*-------------------------------------------------------------*/
  11
  12 /* ------------------------------------------------------------------
  13 This file is part of bzip2/libbzip2, a program and library for
  14 lossless, block-sorting data compression.
  15
  16 bzip2/libbzip2 version 1.0.4 of 20 December 2006
  17 Copyright (C) 1996-2006 Julian Seward <jseward@bzip.org>
  18
  19 Please read the WARNING, DISCLAIMER and PATENTS sections in the
  20 README file.
  21
  22 This program is released under the terms of the license contained
  23 in the file LICENSE.
  24 ------------------------------------------------------------------ */
  25
  26 /* CHANGES
  27  * 0.9.0    -- original version.
  28  * 0.9.0a/b -- no changes in this file.
  29  * 0.9.0c   -- made zero-length BZ_FLUSH work correctly in bzCompress().
  30  *             fixed bzWrite/bzRead to ignore zero-length requests.
  31  *             fixed bzread to correctly handle read requests after EOF.
  32  *             wrong parameter order in call to bzDecompressInit in
  33  *             bzBuffToBuffDecompress.  Fixed.
  34  */
  35
  36 /* #include "bzlib_private.h" */
  37
  38 /*---------------------------------------------------*/
  39 /*--- Compression stuff                           ---*/
  40 /*---------------------------------------------------*/
  41
  42 /*---------------------------------------------------*/
  43 #if BZ_LIGHT_DEBUG
  44 static
  45 void bz_assert_fail(int errcode)
  46 {
  47         /* if (errcode == 1007) bb_error_msg_and_die("probably bad RAM"); */
  48         bb_error_msg_and_die("internal error %d", errcode);
  49 }
  50 #endif
  51
  52 /*---------------------------------------------------*/
  53 static
  54 void prepare_new_block(EState* s)
  55 {
  56         int i;
  57         s->nblock = 0;
  58         //indexes inot s->zbits[], initialzation moved to init of s->zbits
  59         //s->posZ = s->zbits; // was: s->numZ = 0;
  60         //s->state_out_pos = s->zbits;
  61         BZ_INITIALISE_CRC(s->blockCRC);
  62         /* inlined memset would be nice to have here */
  63         for (i = 0; i < 256; i++)
  64                 s->inUse[i] = 0;
  65         s->blockNo++;
  66 }
  67
  68
  69 /*---------------------------------------------------*/
  70 static
  71 ALWAYS_INLINE
  72 void init_RL(EState* s)
  73 {
  74         s->state_in_ch = 256;
  75         s->state_in_len = 0;
  76 }
  77
  78
  79 static
  80 int isempty_RL(EState* s)
  81 {
  82         return (s->state_in_ch >= 256 || s->state_in_len <= 0);
  83 }
  84
  85
  86 /*---------------------------------------------------*/
  87 static
  88 void BZ2_bzCompressInit(bz_stream *strm, int blockSize100k)
  89 {
  90         int32_t n;
  91         EState* s;
  92
  93         s = xzalloc(sizeof(EState));
  94         s->strm = strm;
  95
  96         n        = 100000 * blockSize100k;
  97         s->arr1  = xmalloc(n                    * sizeof(uint32_t));
  98         s->mtfv  = (uint16_t*)s->arr1;
  99         s->ptr   = (uint32_t*)s->arr1;
 100         s->arr2  = xmalloc((n + BZ_N_OVERSHOOT) * sizeof(uint32_t));
 101         s->block = (uint8_t*)s->arr2;
 102         s->ftab  = xmalloc(65537                * sizeof(uint32_t));
 103
 104         s->crc32table = crc32_filltable(NULL, 1);
 105
 106         s->state             = BZ_S_INPUT;
 107         s->mode              = BZ_M_RUNNING;
 108         s->blockSize100k     = blockSize100k;
 109         s->nblockMAX         = n - 19;
 110
 111         strm->state          = s;
 112         /*strm->total_in     = 0;*/
 113         strm->total_out      = 0;
 114         init_RL(s);
 115         prepare_new_block(s);
 116 }
 117
 118
 119 /*---------------------------------------------------*/
 120 static
 121 void add_pair_to_block(EState* s)
 122 {
 123         int32_t i;
 124         uint8_t ch = (uint8_t)(s->state_in_ch);
 125         for (i = 0; i < s->state_in_len; i++) {
 126                 BZ_UPDATE_CRC(s, s->blockCRC, ch);
 127         }
 128         s->inUse[s->state_in_ch] = 1;
 129         switch (s->state_in_len) {
 130                 case 3:
 131                         s->block[s->nblock] = (uint8_t)ch; s->nblock++;
 132                         /* fall through */
 133                 case 2:
 134                         s->block[s->nblock] = (uint8_t)ch; s->nblock++;
 135                         /* fall through */
 136                 case 1:
 137                         s->block[s->nblock] = (uint8_t)ch; s->nblock++;
 138                         break;
 139                 default:
 140                         s->inUse[s->state_in_len - 4] = 1;
 141                         s->block[s->nblock] = (uint8_t)ch; s->nblock++;
 142                         s->block[s->nblock] = (uint8_t)ch; s->nblock++;
 143                         s->block[s->nblock] = (uint8_t)ch; s->nblock++;
 144                         s->block[s->nblock] = (uint8_t)ch; s->nblock++;
 145                         s->block[s->nblock] = (uint8_t)(s->state_in_len - 4);
 146                         s->nblock++;
 147                         break;
 148         }
 149 }
 150
 151
 152 /*---------------------------------------------------*/
 153 static
 154 void flush_RL(EState* s)
 155 {
 156         if (s->state_in_ch < 256) add_pair_to_block(s);
 157         init_RL(s);
 158 }
 159
 160
 161 /*---------------------------------------------------*/
 162 #define ADD_CHAR_TO_BLOCK(zs, zchh0) \
 163 { \
 164         uint32_t zchh = (uint32_t)(zchh0); \
 165         /*-- fast track the common case --*/ \
 166         if (zchh != zs->state_in_ch && zs->state_in_len == 1) { \
 167                 uint8_t ch = (uint8_t)(zs->state_in_ch); \
 168                 BZ_UPDATE_CRC(zs, zs->blockCRC, ch); \
 169                 zs->inUse[zs->state_in_ch] = 1; \
 170                 zs->block[zs->nblock] = (uint8_t)ch; \
 171                 zs->nblock++; \
 172                 zs->state_in_ch = zchh; \
 173         } \
 174         else \
 175         /*-- general, uncommon cases --*/ \
 176         if (zchh != zs->state_in_ch || zs->state_in_len == 255) { \
 177                 if (zs->state_in_ch < 256) \
 178                         add_pair_to_block(zs); \
 179                 zs->state_in_ch = zchh; \
 180                 zs->state_in_len = 1; \
 181         } else { \
 182                 zs->state_in_len++; \
 183         } \
 184 }
 185
 186
 187 /*---------------------------------------------------*/
 188 static
 189 void /*Bool*/ copy_input_until_stop(EState* s)
 190 {
 191         /*Bool progress_in = False;*/
 192
 193 #ifdef SAME_CODE_AS_BELOW
 194         if (s->mode == BZ_M_RUNNING) {
 195                 /*-- fast track the common case --*/
 196                 while (1) {
 197                         /*-- no input? --*/
 198                         if (s->strm->avail_in == 0) break;
 199                         /*-- block full? --*/
 200                         if (s->nblock >= s->nblockMAX) break;
 201                         /*progress_in = True;*/
 202                         ADD_CHAR_TO_BLOCK(s, (uint32_t)(*(uint8_t*)(s->strm->next_in)));
 203                         s->strm->next_in++;
 204                         s->strm->avail_in--;
 205                         /*s->strm->total_in++;*/
 206                 }
 207         } else
 208 #endif
 209         {
 210                 /*-- general, uncommon case --*/
 211                 while (1) {
 212                         /*-- no input? --*/
 213                         if (s->strm->avail_in == 0) break;
 214                         /*-- block full? --*/
 215                         if (s->nblock >= s->nblockMAX) break;
 216                 //#     /*-- flush/finish end? --*/
 217                 //#     if (s->avail_in_expect == 0) break;
 218                         /*progress_in = True;*/
 219                         ADD_CHAR_TO_BLOCK(s, *(uint8_t*)(s->strm->next_in));
 220                         s->strm->next_in++;
 221                         s->strm->avail_in--;
 222                         /*s->strm->total_in++;*/
 223                 //#     s->avail_in_expect--;
 224                 }
 225         }
 226         /*return progress_in;*/
 227 }
 228
 229
 230 /*---------------------------------------------------*/
 231 static
 232 void /*Bool*/ copy_output_until_stop(EState* s)
 233 {
 234         /*Bool progress_out = False;*/
 235
 236         while (1) {
 237                 /*-- no output space? --*/
 238                 if (s->strm->avail_out == 0) break;
 239
 240                 /*-- block done? --*/
 241                 if (s->state_out_pos >= s->posZ) break;
 242
 243                 /*progress_out = True;*/
 244                 *(s->strm->next_out) = *s->state_out_pos++;
 245                 s->strm->avail_out--;
 246                 s->strm->next_out++;
 247                 s->strm->total_out++;
 248         }
 249         /*return progress_out;*/
 250 }
 251
 252
 253 /*---------------------------------------------------*/
 254 static
 255 void /*Bool*/ handle_compress(bz_stream *strm)
 256 {
 257         /*Bool progress_in  = False;*/
 258         /*Bool progress_out = False;*/
 259         EState* s = strm->state;
 260
 261         while (1) {
 262                 if (s->state == BZ_S_OUTPUT) {
 263                         /*progress_out |=*/ copy_output_until_stop(s);
 264                         if (s->state_out_pos < s->posZ) break;
 265                         if (s->mode == BZ_M_FINISHING
 266                         //# && s->avail_in_expect == 0
 267                          && s->strm->avail_in == 0
 268                          && isempty_RL(s))
 269                                 break;
 270                         prepare_new_block(s);
 271                         s->state = BZ_S_INPUT;
 272 #ifdef FLUSH_IS_UNUSED
 273                         if (s->mode == BZ_M_FLUSHING
 274                          && s->avail_in_expect == 0
 275                          && isempty_RL(s))
 276                                 break;
 277 #endif
 278                 }
 279
 280                 if (s->state == BZ_S_INPUT) {
 281                         /*progress_in |=*/ copy_input_until_stop(s);
 282                         //#if (s->mode != BZ_M_RUNNING && s->avail_in_expect == 0) {
 283                         if (s->mode != BZ_M_RUNNING && s->strm->avail_in == 0) {
 284                                 flush_RL(s);
 285                                 BZ2_compressBlock(s, (s->mode == BZ_M_FINISHING));
 286                                 s->state = BZ_S_OUTPUT;
 287                         } else
 288                         if (s->nblock >= s->nblockMAX) {
 289                                 BZ2_compressBlock(s, 0);
 290                                 s->state = BZ_S_OUTPUT;
 291                         } else
 292                         if (s->strm->avail_in == 0) {
 293                                 break;
 294                         }
 295                 }
 296         }
 297
 298         /*return progress_in || progress_out;*/
 299 }
 300
 301
 302 /*---------------------------------------------------*/
 303 static
 304 int BZ2_bzCompress(bz_stream *strm, int action)
 305 {
 306         /*Bool progress;*/
 307         EState* s;
 308
 309         s = strm->state;
 310
 311         switch (s->mode) {
 312                 case BZ_M_RUNNING:
 313                         if (action == BZ_RUN) {
 314                                 /*progress =*/ handle_compress(strm);
 315                                 /*return progress ? BZ_RUN_OK : BZ_PARAM_ERROR;*/
 316                                 return BZ_RUN_OK;
 317                         }
 318 #ifdef FLUSH_IS_UNUSED
 319                         else
 320                         if (action == BZ_FLUSH) {
 321                                 //#s->avail_in_expect = strm->avail_in;
 322                                 s->mode = BZ_M_FLUSHING;
 323                                 goto case_BZ_M_FLUSHING;
 324                         }
 325 #endif
 326                         else
 327                         /*if (action == BZ_FINISH)*/ {
 328                                 //#s->avail_in_expect = strm->avail_in;
 329                                 s->mode = BZ_M_FINISHING;
 330                                 goto case_BZ_M_FINISHING;
 331                         }
 332
 333 #ifdef FLUSH_IS_UNUSED
 334  case_BZ_M_FLUSHING:
 335                 case BZ_M_FLUSHING:
 336                         /*if (s->avail_in_expect != s->strm->avail_in)
 337                                 return BZ_SEQUENCE_ERROR;*/
 338                         /*progress =*/ handle_compress(strm);
 339                         if (s->avail_in_expect > 0 || !isempty_RL(s) || s->state_out_pos < s->posZ)
 340                                 return BZ_FLUSH_OK;
 341                         s->mode = BZ_M_RUNNING;
 342                         return BZ_RUN_OK;
 343 #endif
 344
 345  case_BZ_M_FINISHING:
 346                 /*case BZ_M_FINISHING:*/
 347                 default:
 348                         /*if (s->avail_in_expect != s->strm->avail_in)
 349                                 return BZ_SEQUENCE_ERROR;*/
 350                         /*progress =*/ handle_compress(strm);
 351                         /*if (!progress) return BZ_SEQUENCE_ERROR;*/
 352                         //#if (s->avail_in_expect > 0 || !isempty_RL(s) || s->state_out_pos < s->posZ)
 353                         //#     return BZ_FINISH_OK;
 354                         if (s->strm->avail_in > 0 || !isempty_RL(s) || s->state_out_pos < s->posZ)
 355                                 return BZ_FINISH_OK;
 356                         /*s->mode = BZ_M_IDLE;*/
 357                         return BZ_STREAM_END;
 358         }
 359         /* return BZ_OK; --not reached--*/
 360 }
 361
 362
 363 /*---------------------------------------------------*/
 364 static
 365 void BZ2_bzCompressEnd(bz_stream *strm)
 366 {
 367         EState* s;
 368
 369         s = strm->state;
 370         free(s->arr1);
 371         free(s->arr2);
 372         free(s->ftab);
 373         free(s->crc32table);
 374         free(s);
 375 }
 376
 377
 378 /*---------------------------------------------------*/
 379 /*--- Misc convenience stuff                      ---*/
 380 /*---------------------------------------------------*/
 381
 382 /*---------------------------------------------------*/
 383 #ifdef EXAMPLE_CODE_FOR_MEM_TO_MEM_COMPRESSION
 384 static
 385 int BZ2_bzBuffToBuffCompress(char* dest,
 386                 unsigned int* destLen,
 387                 char*         source,
 388                 unsigned int  sourceLen,
 389                 int           blockSize100k)
 390 {
 391         bz_stream strm;
 392         int ret;
 393
 394         if (dest == NULL || destLen == NULL
 395          || source == NULL
 396          || blockSize100k < 1 || blockSize100k > 9
 397         ) {
 398                 return BZ_PARAM_ERROR;
 399         }
 400
 401         BZ2_bzCompressInit(&strm, blockSize100k);
 402
 403         strm.next_in = source;
 404         strm.next_out = dest;
 405         strm.avail_in = sourceLen;
 406         strm.avail_out = *destLen;
 407
 408         ret = BZ2_bzCompress(&strm, BZ_FINISH);
 409         if (ret == BZ_FINISH_OK) goto output_overflow;
 410         if (ret != BZ_STREAM_END) goto errhandler;
 411
 412         /* normal termination */
 413         *destLen -= strm.avail_out;
 414         BZ2_bzCompressEnd(&strm);
 415         return BZ_OK;
 416
 417  output_overflow:
 418         BZ2_bzCompressEnd(&strm);
 419         return BZ_OUTBUFF_FULL;
 420
 421  errhandler:
 422         BZ2_bzCompressEnd(&strm);
 423         return ret;
 424 }
 425 #endif
 426
 427 /*-------------------------------------------------------------*/
 428 /*--- end                                           bzlib.c ---*/
 429 /*-------------------------------------------------------------*/