u-tools/apps/busybox/archival/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         s->numZ = 0;
  59         s->state_out_pos = 0;
  60         BZ_INITIALISE_CRC(s->blockCRC);
  61         /* inlined memset would be nice to have here */
  62         for (i = 0; i < 256; i++)
  63                 s->inUse[i] = 0;
  64         s->blockNo++;
  65 }
  66
  67
  68 /*---------------------------------------------------*/
  69 static
  70 ALWAYS_INLINE
  71 void init_RL(EState* s)
  72 {
  73         s->state_in_ch = 256;
  74         s->state_in_len = 0;
  75 }
  76
  77
  78 static
  79 int isempty_RL(EState* s)
  80 {
  81         return (s->state_in_ch >= 256 || s->state_in_len <= 0);
  82 }
  83
  84
  85 /*---------------------------------------------------*/
  86 static
  87 void BZ2_bzCompressInit(bz_stream *strm, int blockSize100k)
  88 {
  89         int32_t n;
  90         EState* s;
  91
  92         s = xzalloc(sizeof(EState));
  93         s->strm = strm;
  94
  95         n        = 100000 * blockSize100k;
  96         s->arr1  = xmalloc(n                    * sizeof(uint32_t));
  97         s->mtfv  = (uint16_t*)s->arr1;
  98         s->ptr   = (uint32_t*)s->arr1;
  99         s->arr2  = xmalloc((n + BZ_N_OVERSHOOT) * sizeof(uint32_t));
 100         s->block = (uint8_t*)s->arr2;
 101         s->ftab  = xmalloc(65537                * sizeof(uint32_t));
 102
 103         s->crc32table = crc32_filltable(NULL, 1);
 104
 105         s->state             = BZ_S_INPUT;
 106         s->mode              = BZ_M_RUNNING;
 107         s->blockSize100k     = blockSize100k;
 108         s->nblockMAX         = n - 19;
 109
 110         strm->state          = s;
 111         /*strm->total_in     = 0;*/
 112         strm->total_out      = 0;
 113         init_RL(s);
 114         prepare_new_block(s);
 115 }
 116
 117
 118 /*---------------------------------------------------*/
 119 static
 120 void add_pair_to_block(EState* s)
 121 {
 122         int32_t i;
 123         uint8_t ch = (uint8_t)(s->state_in_ch);
 124         for (i = 0; i < s->state_in_len; i++) {
 125                 BZ_UPDATE_CRC(s, s->blockCRC, ch);
 126         }
 127         s->inUse[s->state_in_ch] = 1;
 128         switch (s->state_in_len) {
 129                 case 3:
 130                         s->block[s->nblock] = (uint8_t)ch; s->nblock++;
 131                         /* fall through */
 132                 case 2:
 133                         s->block[s->nblock] = (uint8_t)ch; s->nblock++;
 134                         /* fall through */
 135                 case 1:
 136                         s->block[s->nblock] = (uint8_t)ch; s->nblock++;
 137                         break;
 138                 default:
 139                         s->inUse[s->state_in_len - 4] = 1;
 140                         s->block[s->nblock] = (uint8_t)ch; s->nblock++;
 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)(s->state_in_len - 4);
 145                         s->nblock++;
 146                         break;
 147         }
 148 }
 149
 150
 151 /*---------------------------------------------------*/
 152 static
 153 void flush_RL(EState* s)
 154 {
 155         if (s->state_in_ch < 256) add_pair_to_block(s);
 156         init_RL(s);
 157 }
 158
 159
 160 /*---------------------------------------------------*/
 161 #define ADD_CHAR_TO_BLOCK(zs, zchh0) \
 162 { \
 163         uint32_t zchh = (uint32_t)(zchh0); \
 164         /*-- fast track the common case --*/ \
 165         if (zchh != zs->state_in_ch && zs->state_in_len == 1) { \
 166                 uint8_t ch = (uint8_t)(zs->state_in_ch); \
 167                 BZ_UPDATE_CRC(zs, zs->blockCRC, ch); \
 168                 zs->inUse[zs->state_in_ch] = 1; \
 169                 zs->block[zs->nblock] = (uint8_t)ch; \
 170                 zs->nblock++; \
 171                 zs->state_in_ch = zchh; \
 172         } \
 173         else \
 174         /*-- general, uncommon cases --*/ \
 175         if (zchh != zs->state_in_ch || zs->state_in_len == 255) { \
 176                 if (zs->state_in_ch < 256) \
 177                         add_pair_to_block(zs); \
 178                 zs->state_in_ch = zchh; \
 179                 zs->state_in_len = 1; \
 180         } else { \
 181                 zs->state_in_len++; \
 182         } \
 183 }
 184
 185
 186 /*---------------------------------------------------*/
 187 static
 188 void /*Bool*/ copy_input_until_stop(EState* s)
 189 {
 190         /*Bool progress_in = False;*/
 191
 192 #ifdef SAME_CODE_AS_BELOW
 193         if (s->mode == BZ_M_RUNNING) {
 194                 /*-- fast track the common case --*/
 195                 while (1) {
 196                         /*-- no input? --*/
 197                         if (s->strm->avail_in == 0) break;
 198                         /*-- block full? --*/
 199                         if (s->nblock >= s->nblockMAX) break;
 200                         /*progress_in = True;*/
 201                         ADD_CHAR_TO_BLOCK(s, (uint32_t)(*(uint8_t*)(s->strm->next_in)));
 202                         s->strm->next_in++;
 203                         s->strm->avail_in--;
 204                         /*s->strm->total_in++;*/
 205                 }
 206         } else
 207 #endif
 208         {
 209                 /*-- general, uncommon case --*/
 210                 while (1) {
 211                         /*-- no input? --*/
 212                         if (s->strm->avail_in == 0) break;
 213                         /*-- block full? --*/
 214                         if (s->nblock >= s->nblockMAX) break;
 215                 //#     /*-- flush/finish end? --*/
 216                 //#     if (s->avail_in_expect == 0) break;
 217                         /*progress_in = True;*/
 218                         ADD_CHAR_TO_BLOCK(s, *(uint8_t*)(s->strm->next_in));
 219                         s->strm->next_in++;
 220                         s->strm->avail_in--;
 221                         /*s->strm->total_in++;*/
 222                 //#     s->avail_in_expect--;
 223                 }
 224         }
 225         /*return progress_in;*/
 226 }
 227
 228
 229 /*---------------------------------------------------*/
 230 static
 231 void /*Bool*/ copy_output_until_stop(EState* s)
 232 {
 233         /*Bool progress_out = False;*/
 234
 235         while (1) {
 236                 /*-- no output space? --*/
 237                 if (s->strm->avail_out == 0) break;
 238
 239                 /*-- block done? --*/
 240                 if (s->state_out_pos >= s->numZ) break;
 241
 242                 /*progress_out = True;*/
 243                 *(s->strm->next_out) = s->zbits[s->state_out_pos];
 244                 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->numZ) 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->numZ)
 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->numZ)
 353                         //#     return BZ_FINISH_OK;
 354                         if (s->strm->avail_in > 0 || !isempty_RL(s) || s->state_out_pos < s->numZ)
 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 #if ENABLE_FEATURE_CLEAN_UP
 365 static
 366 void BZ2_bzCompressEnd(bz_stream *strm)
 367 {
 368         EState* s;
 369
 370         s = strm->state;
 371         free(s->arr1);
 372         free(s->arr2);
 373         free(s->ftab);
 374         free(s->crc32table);
 375         free(strm->state);
 376 }
 377 #endif
 378
 379
 380 /*---------------------------------------------------*/
 381 /*--- Misc convenience stuff                      ---*/
 382 /*---------------------------------------------------*/
 383
 384 /*---------------------------------------------------*/
 385 #ifdef EXAMPLE_CODE_FOR_MEM_TO_MEM_COMPRESSION
 386 static
 387 int BZ2_bzBuffToBuffCompress(char* dest,
 388                 unsigned int* destLen,
 389                 char*         source,
 390                 unsigned int  sourceLen,
 391                 int           blockSize100k)
 392 {
 393         bz_stream strm;
 394         int ret;
 395
 396         if (dest == NULL || destLen == NULL ||
 397                  source == NULL ||
 398                  blockSize100k < 1 || blockSize100k > 9)
 399                 return BZ_PARAM_ERROR;
 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 /*-------------------------------------------------------------*/