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 Bool isempty_RL(EState* s)
  80 {
  81         if (s->state_in_ch < 256 && s->state_in_len > 0)
  82                 return False;
  83         return True;
  84 }
  85
  86
  87 /*---------------------------------------------------*/
  88 static
  89 void BZ2_bzCompressInit(bz_stream *strm, int blockSize100k)
  90 {
  91         int32_t n;
  92         EState* s;
  93
  94         s = xzalloc(sizeof(EState));
  95         s->strm = strm;
  96
  97         n        = 100000 * blockSize100k;
  98         s->arr1  = xmalloc(n                    * sizeof(uint32_t));
  99         s->mtfv  = (uint16_t*)s->arr1;
 100         s->ptr   = (uint32_t*)s->arr1;
 101         s->arr2  = xmalloc((n + BZ_N_OVERSHOOT) * sizeof(uint32_t));
 102         s->block = (uint8_t*)s->arr2;
 103         s->ftab  = xmalloc(65537                * sizeof(uint32_t));
 104
 105         s->crc32table = crc32_filltable(NULL, 1);
 106
 107         s->state             = BZ_S_INPUT;
 108         s->mode              = BZ_M_RUNNING;
 109         s->blockSize100k     = blockSize100k;
 110         s->nblockMAX         = n - 19;
 111
 112         strm->state          = s;
 113         /*strm->total_in     = 0;*/
 114         strm->total_out      = 0;
 115         init_RL(s);
 116         prepare_new_block(s);
 117 }
 118
 119
 120 /*---------------------------------------------------*/
 121 static
 122 void add_pair_to_block(EState* s)
 123 {
 124         int32_t i;
 125         uint8_t ch = (uint8_t)(s->state_in_ch);
 126         for (i = 0; i < s->state_in_len; i++) {
 127                 BZ_UPDATE_CRC(s, s->blockCRC, ch);
 128         }
 129         s->inUse[s->state_in_ch] = 1;
 130         switch (s->state_in_len) {
 131                 case 3:
 132                         s->block[s->nblock] = (uint8_t)ch; s->nblock++;
 133                         /* fall through */
 134                 case 2:
 135                         s->block[s->nblock] = (uint8_t)ch; s->nblock++;
 136                         /* fall through */
 137                 case 1:
 138                         s->block[s->nblock] = (uint8_t)ch; s->nblock++;
 139                         break;
 140                 default:
 141                         s->inUse[s->state_in_len - 4] = 1;
 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)ch; s->nblock++;
 146                         s->block[s->nblock] = (uint8_t)(s->state_in_len - 4);
 147                         s->nblock++;
 148                         break;
 149         }
 150 }
 151
 152
 153 /*---------------------------------------------------*/
 154 static
 155 void flush_RL(EState* s)
 156 {
 157         if (s->state_in_ch < 256) add_pair_to_block(s);
 158         init_RL(s);
 159 }
 160
 161
 162 /*---------------------------------------------------*/
 163 #define ADD_CHAR_TO_BLOCK(zs, zchh0) \
 164 { \
 165         uint32_t zchh = (uint32_t)(zchh0); \
 166         /*-- fast track the common case --*/ \
 167         if (zchh != zs->state_in_ch && zs->state_in_len == 1) { \
 168                 uint8_t ch = (uint8_t)(zs->state_in_ch); \
 169                 BZ_UPDATE_CRC(zs, zs->blockCRC, ch); \
 170                 zs->inUse[zs->state_in_ch] = 1; \
 171                 zs->block[zs->nblock] = (uint8_t)ch; \
 172                 zs->nblock++; \
 173                 zs->state_in_ch = zchh; \
 174         } \
 175         else \
 176         /*-- general, uncommon cases --*/ \
 177         if (zchh != zs->state_in_ch || zs->state_in_len == 255) { \
 178                 if (zs->state_in_ch < 256) \
 179                         add_pair_to_block(zs); \
 180                 zs->state_in_ch = zchh; \
 181                 zs->state_in_len = 1; \
 182         } else { \
 183                 zs->state_in_len++; \
 184         } \
 185 }
 186
 187
 188 /*---------------------------------------------------*/
 189 static
 190 void /*Bool*/ copy_input_until_stop(EState* s)
 191 {
 192         /*Bool progress_in = False;*/
 193
 194 #ifdef SAME_CODE_AS_BELOW
 195         if (s->mode == BZ_M_RUNNING) {
 196                 /*-- fast track the common case --*/
 197                 while (1) {
 198                         /*-- no input? --*/
 199                         if (s->strm->avail_in == 0) break;
 200                         /*-- block full? --*/
 201                         if (s->nblock >= s->nblockMAX) break;
 202                         /*progress_in = True;*/
 203                         ADD_CHAR_TO_BLOCK(s, (uint32_t)(*(uint8_t*)(s->strm->next_in)));
 204                         s->strm->next_in++;
 205                         s->strm->avail_in--;
 206                         /*s->strm->total_in++;*/
 207                 }
 208         } else
 209 #endif
 210         {
 211                 /*-- general, uncommon case --*/
 212                 while (1) {
 213                         /*-- no input? --*/
 214                         if (s->strm->avail_in == 0) break;
 215                         /*-- block full? --*/
 216                         if (s->nblock >= s->nblockMAX) break;
 217                 //#     /*-- flush/finish end? --*/
 218                 //#     if (s->avail_in_expect == 0) break;
 219                         /*progress_in = True;*/
 220                         ADD_CHAR_TO_BLOCK(s, *(uint8_t*)(s->strm->next_in));
 221                         s->strm->next_in++;
 222                         s->strm->avail_in--;
 223                         /*s->strm->total_in++;*/
 224                 //#     s->avail_in_expect--;
 225                 }
 226         }
 227         /*return progress_in;*/
 228 }
 229
 230
 231 /*---------------------------------------------------*/
 232 static
 233 void /*Bool*/ copy_output_until_stop(EState* s)
 234 {
 235         /*Bool progress_out = False;*/
 236
 237         while (1) {
 238                 /*-- no output space? --*/
 239                 if (s->strm->avail_out == 0) break;
 240
 241                 /*-- block done? --*/
 242                 if (s->state_out_pos >= s->numZ) break;
 243
 244                 /*progress_out = True;*/
 245                 *(s->strm->next_out) = s->zbits[s->state_out_pos];
 246                 s->state_out_pos++;
 247                 s->strm->avail_out--;
 248                 s->strm->next_out++;
 249                 s->strm->total_out++;
 250         }
 251         /*return progress_out;*/
 252 }
 253
 254
 255 /*---------------------------------------------------*/
 256 static
 257 void /*Bool*/ handle_compress(bz_stream *strm)
 258 {
 259         /*Bool progress_in  = False;*/
 260         /*Bool progress_out = False;*/
 261         EState* s = strm->state;
 262
 263         while (1) {
 264                 if (s->state == BZ_S_OUTPUT) {
 265                         /*progress_out |=*/ copy_output_until_stop(s);
 266                         if (s->state_out_pos < s->numZ) break;
 267                         if (s->mode == BZ_M_FINISHING
 268                         //# && s->avail_in_expect == 0
 269                          && s->strm->avail_in == 0
 270                          && isempty_RL(s))
 271                                 break;
 272                         prepare_new_block(s);
 273                         s->state = BZ_S_INPUT;
 274 #ifdef FLUSH_IS_UNUSED
 275                         if (s->mode == BZ_M_FLUSHING
 276                          && s->avail_in_expect == 0
 277                          && isempty_RL(s))
 278                                 break;
 279 #endif
 280                 }
 281
 282                 if (s->state == BZ_S_INPUT) {
 283                         /*progress_in |=*/ copy_input_until_stop(s);
 284                         //#if (s->mode != BZ_M_RUNNING && s->avail_in_expect == 0) {
 285                         if (s->mode != BZ_M_RUNNING && s->strm->avail_in == 0) {
 286                                 flush_RL(s);
 287                                 BZ2_compressBlock(s, (s->mode == BZ_M_FINISHING));
 288                                 s->state = BZ_S_OUTPUT;
 289                         } else
 290                         if (s->nblock >= s->nblockMAX) {
 291                                 BZ2_compressBlock(s, 0);
 292                                 s->state = BZ_S_OUTPUT;
 293                         } else
 294                         if (s->strm->avail_in == 0) {
 295                                 break;
 296                         }
 297                 }
 298         }
 299
 300         /*return progress_in || progress_out;*/
 301 }
 302
 303
 304 /*---------------------------------------------------*/
 305 static
 306 int BZ2_bzCompress(bz_stream *strm, int action)
 307 {
 308         /*Bool progress;*/
 309         EState* s;
 310
 311         s = strm->state;
 312
 313         switch (s->mode) {
 314                 case BZ_M_RUNNING:
 315                         if (action == BZ_RUN) {
 316                                 /*progress =*/ handle_compress(strm);
 317                                 /*return progress ? BZ_RUN_OK : BZ_PARAM_ERROR;*/
 318                                 return BZ_RUN_OK;
 319                         }
 320 #ifdef FLUSH_IS_UNUSED
 321                         else
 322                         if (action == BZ_FLUSH) {
 323                                 //#s->avail_in_expect = strm->avail_in;
 324                                 s->mode = BZ_M_FLUSHING;
 325                                 goto case_BZ_M_FLUSHING;
 326                         }
 327 #endif
 328                         else
 329                         /*if (action == BZ_FINISH)*/ {
 330                                 //#s->avail_in_expect = strm->avail_in;
 331                                 s->mode = BZ_M_FINISHING;
 332                                 goto case_BZ_M_FINISHING;
 333                         }
 334
 335 #ifdef FLUSH_IS_UNUSED
 336 case_BZ_M_FLUSHING:
 337                 case BZ_M_FLUSHING:
 338                         /*if (s->avail_in_expect != s->strm->avail_in)
 339                                 return BZ_SEQUENCE_ERROR;*/
 340                         /*progress =*/ handle_compress(strm);
 341                         if (s->avail_in_expect > 0 || !isempty_RL(s) || s->state_out_pos < s->numZ)
 342                                 return BZ_FLUSH_OK;
 343                         s->mode = BZ_M_RUNNING;
 344                         return BZ_RUN_OK;
 345 #endif
 346
 347  case_BZ_M_FINISHING:
 348                 /*case BZ_M_FINISHING:*/
 349                 default:
 350                         /*if (s->avail_in_expect != s->strm->avail_in)
 351                                 return BZ_SEQUENCE_ERROR;*/
 352                         /*progress =*/ handle_compress(strm);
 353                         /*if (!progress) return BZ_SEQUENCE_ERROR;*/
 354                         //#if (s->avail_in_expect > 0 || !isempty_RL(s) || s->state_out_pos < s->numZ)
 355                         //#     return BZ_FINISH_OK;
 356                         if (s->strm->avail_in > 0 || !isempty_RL(s) || s->state_out_pos < s->numZ)
 357                                 return BZ_FINISH_OK;
 358                         /*s->mode = BZ_M_IDLE;*/
 359                         return BZ_STREAM_END;
 360         }
 361         /* return BZ_OK; --not reached--*/
 362 }
 363
 364
 365 /*---------------------------------------------------*/
 366 static
 367 void BZ2_bzCompressEnd(bz_stream *strm)
 368 {
 369         EState* s;
 370
 371         s = strm->state;
 372         free(s->arr1);
 373         free(s->arr2);
 374         free(s->ftab);
 375         free(s->crc32table);
 376         free(strm->state);
 377 }
 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 /*-------------------------------------------------------------*/