op public repos

Blob

Date:: Fri Jan 14 18:32:36 2005 UTC
Message:: stupid sun
Actions:: History | Blame | Raw File
1 /*
2  * THIS FILE IS NOT IDENTICAL TO THE ORIGINAL
3  * FROM THE BZIP2 DISTRIBUTION.
4  *
5  * It has been modified, mainly to break the library
6  * into smaller pieces.
7  *
8  * Russ Cox
9  * rsc@plan9.bell-labs.com
10  * July 2000
11  */
12 
13 /*-------------------------------------------------------------*/
14 /*--- Library top-level functions.                          ---*/
15 /*---                                               bzlib.c ---*/
16 /*-------------------------------------------------------------*/
17 
18 /*--
19   This file is a part of bzip2 and/or libbzip2, a program and
20   library for lossless, block-sorting data compression.
21 
22   Copyright (C) 1996-2000 Julian R Seward.  All rights reserved.
23 
24   Redistribution and use in source and binary forms, with or without
25   modification, are permitted provided that the following conditions
26   are met:
27 
28   1. Redistributions of source code must retain the above copyright
29      notice, this list of conditions and the following disclaimer.
30 
31   2. The origin of this software must not be misrepresented; you must 
32      not claim that you wrote the original software.  If you use this 
33      software in a product, an acknowledgment in the product 
34      documentation would be appreciated but is not required.
35 
36   3. Altered source versions must be plainly marked as such, and must
37      not be misrepresented as being the original software.
38 
39   4. The name of the author may not be used to endorse or promote 
40      products derived from this software without specific prior written 
41      permission.
42 
43   THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
44   OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
45   WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
46   ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
47   DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
48   DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
49   GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
50   INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
51   WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
52   NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
53   SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
54 
55   Julian Seward, Cambridge, UK.
56   jseward@acm.org
57   bzip2/libbzip2 version 1.0 of 21 March 2000
58 
59   This program is based on (at least) the work of:
60      Mike Burrows
61      David Wheeler
62      Peter Fenwick
63      Alistair Moffat
64      Radford Neal
65      Ian H. Witten
66      Robert Sedgewick
67      Jon L. Bentley
68 
69   For more information on these sources, see the manual.
70 --*/
71 
72 /*--
73    CHANGES
74    ~~~~~~~
75    0.9.0 -- original version.
76 
77    0.9.0a/b -- no changes in this file.
78 
79    0.9.0c
80       * made zero-length BZ_FLUSH work correctly in bzCompress().
81       * fixed bzWrite/bzRead to ignore zero-length requests.
82       * fixed bzread to correctly handle read requests after EOF.
83       * wrong parameter order in call to bzDecompressInit in
84         bzBuffToBuffDecompress.  Fixed.
85 --*/
86 
87 #include "os.h"
88 #include "bzlib.h"
89 #include "bzlib_private.h"
90 
91 /*---------------------------------------------------*/
92 /*--- Decompression stuff                         ---*/
93 /*---------------------------------------------------*/
94 
95 /*---------------------------------------------------*/
96 int BZ_API(BZ2_bzDecompressInit) 
97                      ( bz_stream* strm, 
98                        int        verbosity,
99                        int        small )
100 {
101    DState* s;
102 
103    if (!bz_config_ok()) return BZ_CONFIG_ERROR;
104 
105    if (strm == NULL) return BZ_PARAM_ERROR;
106    if (small != 0 && small != 1) return BZ_PARAM_ERROR;
107    if (verbosity < 0 || verbosity > 4) return BZ_PARAM_ERROR;
108 
109    if (strm->bzalloc == NULL) strm->bzalloc = default_bzalloc;
110    if (strm->bzfree == NULL) strm->bzfree = default_bzfree;
111 
112    s = BZALLOC( sizeof(DState) );
113    if (s == NULL) return BZ_MEM_ERROR;
114    s->strm                  = strm;
115    strm->state              = s;
116    s->state                 = BZ_X_MAGIC_1;
117    s->bsLive                = 0;
118    s->bsBuff                = 0;
119    s->calculatedCombinedCRC = 0;
120    strm->total_in_lo32      = 0;
121    strm->total_in_hi32      = 0;
122    strm->total_out_lo32     = 0;
123    strm->total_out_hi32     = 0;
124    s->smallDecompress       = (Bool)small;
125    s->ll4                   = NULL;
126    s->ll16                  = NULL;
127    s->tt                    = NULL;
128    s->currBlockNo           = 0;
129    s->verbosity             = verbosity;
130 
131    return BZ_OK;
132 }
133 
134 
135 /*---------------------------------------------------*/
136 static
137 void unRLE_obuf_to_output_FAST ( DState* s )
138 {
139    UChar k1;
140 
141    if (s->blockRandomised) {
142 
143       while (True) {
144          /* try to finish existing run */
145          while (True) {
146             if (s->strm->avail_out == 0) return;
147             if (s->state_out_len == 0) break;
148             *( (UChar*)(s->strm->next_out) ) = s->state_out_ch;
149             BZ_UPDATE_CRC ( s->calculatedBlockCRC, s->state_out_ch );
150             s->state_out_len--;
151             s->strm->next_out++;
152             s->strm->avail_out--;
153             s->strm->total_out_lo32++;
154             if (s->strm->total_out_lo32 == 0) s->strm->total_out_hi32++;
155          }
156    
157          /* can a new run be started? */
158          if (s->nblock_used == s->save_nblock+1) return;
159                
160    
161          s->state_out_len = 1;
162          s->state_out_ch = s->k0;
163          BZ_GET_FAST(k1); BZ_RAND_UPD_MASK; 
164          k1 ^= BZ_RAND_MASK; s->nblock_used++;
165          if (s->nblock_used == s->save_nblock+1) continue;
166          if (k1 != s->k0) { s->k0 = k1; continue; };
167    
168          s->state_out_len = 2;
169          BZ_GET_FAST(k1); BZ_RAND_UPD_MASK; 
170          k1 ^= BZ_RAND_MASK; s->nblock_used++;
171          if (s->nblock_used == s->save_nblock+1) continue;
172          if (k1 != s->k0) { s->k0 = k1; continue; };
173    
174          s->state_out_len = 3;
175          BZ_GET_FAST(k1); BZ_RAND_UPD_MASK; 
176          k1 ^= BZ_RAND_MASK; s->nblock_used++;
177          if (s->nblock_used == s->save_nblock+1) continue;
178          if (k1 != s->k0) { s->k0 = k1; continue; };
179    
180          BZ_GET_FAST(k1); BZ_RAND_UPD_MASK; 
181          k1 ^= BZ_RAND_MASK; s->nblock_used++;
182          s->state_out_len = ((Int32)k1) + 4;
183          BZ_GET_FAST(s->k0); BZ_RAND_UPD_MASK; 
184          s->k0 ^= BZ_RAND_MASK; s->nblock_used++;
185       }
186 
187    } else {
188 
189       /* restore */
190       UInt32        c_calculatedBlockCRC = s->calculatedBlockCRC;
191       UChar         c_state_out_ch       = s->state_out_ch;
192       Int32         c_state_out_len      = s->state_out_len;
193       Int32         c_nblock_used        = s->nblock_used;
194       Int32         c_k0                 = s->k0;
195       UInt32*       c_tt                 = s->tt;
196       UInt32        c_tPos               = s->tPos;
197       char*         cs_next_out          = s->strm->next_out;
198       unsigned int  cs_avail_out         = s->strm->avail_out;
199       /* end restore */
200 
201       UInt32       avail_out_INIT = cs_avail_out;
202       Int32        s_save_nblockPP = s->save_nblock+1;
203       unsigned int total_out_lo32_old;
204 
205       while (True) {
206 
207          /* try to finish existing run */
208          if (c_state_out_len > 0) {
209             while (True) {
210                if (cs_avail_out == 0) goto return_notr;
211                if (c_state_out_len == 1) break;
212                *( (UChar*)(cs_next_out) ) = c_state_out_ch;
213                BZ_UPDATE_CRC ( c_calculatedBlockCRC, c_state_out_ch );
214                c_state_out_len--;
215                cs_next_out++;
216                cs_avail_out--;
217             }
218             s_state_out_len_eq_one:
219             {
220                if (cs_avail_out == 0) { 
221                   c_state_out_len = 1; goto return_notr;
222                };
223                *( (UChar*)(cs_next_out) ) = c_state_out_ch;
224                BZ_UPDATE_CRC ( c_calculatedBlockCRC, c_state_out_ch );
225                cs_next_out++;
226                cs_avail_out--;
227             }
228          }   
229          /* can a new run be started? */
230          if (c_nblock_used == s_save_nblockPP) {
231             c_state_out_len = 0; goto return_notr;
232          };   
233          c_state_out_ch = c_k0;
234          BZ_GET_FAST_C(k1); c_nblock_used++;
235          if (k1 != c_k0) { 
236             c_k0 = k1; goto s_state_out_len_eq_one; 
237          };
238          if (c_nblock_used == s_save_nblockPP) 
239             goto s_state_out_len_eq_one;
240    
241          c_state_out_len = 2;
242          BZ_GET_FAST_C(k1); c_nblock_used++;
243          if (c_nblock_used == s_save_nblockPP) continue;
244          if (k1 != c_k0) { c_k0 = k1; continue; };
245    
246          c_state_out_len = 3;
247          BZ_GET_FAST_C(k1); c_nblock_used++;
248          if (c_nblock_used == s_save_nblockPP) continue;
249          if (k1 != c_k0) { c_k0 = k1; continue; };
250    
251          BZ_GET_FAST_C(k1); c_nblock_used++;
252          c_state_out_len = ((Int32)k1) + 4;
253          BZ_GET_FAST_C(c_k0); c_nblock_used++;
254       }
255 
256       return_notr:
257       total_out_lo32_old = s->strm->total_out_lo32;
258       s->strm->total_out_lo32 += (avail_out_INIT - cs_avail_out);
259       if (s->strm->total_out_lo32 < total_out_lo32_old)
260          s->strm->total_out_hi32++;
261 
262       /* save */
263       s->calculatedBlockCRC = c_calculatedBlockCRC;
264       s->state_out_ch       = c_state_out_ch;
265       s->state_out_len      = c_state_out_len;
266       s->nblock_used        = c_nblock_used;
267       s->k0                 = c_k0;
268       s->tt                 = c_tt;
269       s->tPos               = c_tPos;
270       s->strm->next_out     = cs_next_out;
271       s->strm->avail_out    = cs_avail_out;
272       /* end save */
273    }
274 }
275 
276 
277 
278 /*---------------------------------------------------*/
279 __inline__ Int32 BZ2_indexIntoF ( Int32 indx, Int32 *cftab )
280 {
281    Int32 nb, na, mid;
282    nb = 0;
283    na = 256;
284    do {
285       mid = (nb + na) >> 1;
286       if (indx >= cftab[mid]) nb = mid; else na = mid;
287    }
288    while (na - nb != 1);
289    return nb;
290 }
291 
292 
293 /*---------------------------------------------------*/
294 static
295 void unRLE_obuf_to_output_SMALL ( DState* s )
296 {
297    UChar k1;
298 
299    if (s->blockRandomised) {
300 
301       while (True) {
302          /* try to finish existing run */
303          while (True) {
304             if (s->strm->avail_out == 0) return;
305             if (s->state_out_len == 0) break;
306             *( (UChar*)(s->strm->next_out) ) = s->state_out_ch;
307             BZ_UPDATE_CRC ( s->calculatedBlockCRC, s->state_out_ch );
308             s->state_out_len--;
309             s->strm->next_out++;
310             s->strm->avail_out--;
311             s->strm->total_out_lo32++;
312             if (s->strm->total_out_lo32 == 0) s->strm->total_out_hi32++;
313          }
314    
315          /* can a new run be started? */
316          if (s->nblock_used == s->save_nblock+1) return;
317                
318    
319          s->state_out_len = 1;
320          s->state_out_ch = s->k0;
321          BZ_GET_SMALL(k1); BZ_RAND_UPD_MASK; 
322          k1 ^= BZ_RAND_MASK; s->nblock_used++;
323          if (s->nblock_used == s->save_nblock+1) continue;
324          if (k1 != s->k0) { s->k0 = k1; continue; };
325    
326          s->state_out_len = 2;
327          BZ_GET_SMALL(k1); BZ_RAND_UPD_MASK; 
328          k1 ^= BZ_RAND_MASK; s->nblock_used++;
329          if (s->nblock_used == s->save_nblock+1) continue;
330          if (k1 != s->k0) { s->k0 = k1; continue; };
331    
332          s->state_out_len = 3;
333          BZ_GET_SMALL(k1); BZ_RAND_UPD_MASK; 
334          k1 ^= BZ_RAND_MASK; s->nblock_used++;
335          if (s->nblock_used == s->save_nblock+1) continue;
336          if (k1 != s->k0) { s->k0 = k1; continue; };
337    
338          BZ_GET_SMALL(k1); BZ_RAND_UPD_MASK; 
339          k1 ^= BZ_RAND_MASK; s->nblock_used++;
340          s->state_out_len = ((Int32)k1) + 4;
341          BZ_GET_SMALL(s->k0); BZ_RAND_UPD_MASK; 
342          s->k0 ^= BZ_RAND_MASK; s->nblock_used++;
343       }
344 
345    } else {
346 
347       while (True) {
348          /* try to finish existing run */
349          while (True) {
350             if (s->strm->avail_out == 0) return;
351             if (s->state_out_len == 0) break;
352             *( (UChar*)(s->strm->next_out) ) = s->state_out_ch;
353             BZ_UPDATE_CRC ( s->calculatedBlockCRC, s->state_out_ch );
354             s->state_out_len--;
355             s->strm->next_out++;
356             s->strm->avail_out--;
357             s->strm->total_out_lo32++;
358             if (s->strm->total_out_lo32 == 0) s->strm->total_out_hi32++;
359          }
360    
361          /* can a new run be started? */
362          if (s->nblock_used == s->save_nblock+1) return;
363    
364          s->state_out_len = 1;
365          s->state_out_ch = s->k0;
366          BZ_GET_SMALL(k1); s->nblock_used++;
367          if (s->nblock_used == s->save_nblock+1) continue;
368          if (k1 != s->k0) { s->k0 = k1; continue; };
369    
370          s->state_out_len = 2;
371          BZ_GET_SMALL(k1); s->nblock_used++;
372          if (s->nblock_used == s->save_nblock+1) continue;
373          if (k1 != s->k0) { s->k0 = k1; continue; };
374    
375          s->state_out_len = 3;
376          BZ_GET_SMALL(k1); s->nblock_used++;
377          if (s->nblock_used == s->save_nblock+1) continue;
378          if (k1 != s->k0) { s->k0 = k1; continue; };
379    
380          BZ_GET_SMALL(k1); s->nblock_used++;
381          s->state_out_len = ((Int32)k1) + 4;
382          BZ_GET_SMALL(s->k0); s->nblock_used++;
383       }
384 
385    }
386 }
387 
388 
389 /*---------------------------------------------------*/
390 int BZ_API(BZ2_bzDecompress) ( bz_stream *strm )
391 {
392    DState* s;
393    if (strm == NULL) return BZ_PARAM_ERROR;
394    s = strm->state;
395    if (s == NULL) return BZ_PARAM_ERROR;
396    if (s->strm != strm) return BZ_PARAM_ERROR;
397 
398    while (True) {
399       if (s->state == BZ_X_IDLE) return BZ_SEQUENCE_ERROR;
400       if (s->state == BZ_X_OUTPUT) {
401          if (s->smallDecompress)
402             unRLE_obuf_to_output_SMALL ( s ); else
403             unRLE_obuf_to_output_FAST  ( s );
404          if (s->nblock_used == s->save_nblock+1 && s->state_out_len == 0) {
405             BZ_FINALISE_CRC ( s->calculatedBlockCRC );
406             if (s->verbosity >= 3) 
407                VPrintf2 ( " {0x%x, 0x%x}", s->storedBlockCRC, 
408                           s->calculatedBlockCRC );
409             if (s->verbosity >= 2) VPrintf0 ( "]" );
410             if (s->calculatedBlockCRC != s->storedBlockCRC)
411                return BZ_DATA_ERROR;
412             s->calculatedCombinedCRC 
413                = (s->calculatedCombinedCRC << 1) | 
414                     (s->calculatedCombinedCRC >> 31);
415             s->calculatedCombinedCRC ^= s->calculatedBlockCRC;
416             s->state = BZ_X_BLKHDR_1;
417          } else {
418             return BZ_OK;
419          }
420       }
421       if (s->state >= BZ_X_MAGIC_1) {
422          Int32 r = BZ2_decompress ( s );
423          if (r == BZ_STREAM_END) {
424             if (s->verbosity >= 3)
425                VPrintf2 ( "\n    combined CRCs: stored = 0x%x, computed = 0x%x", 
426                           s->storedCombinedCRC, s->calculatedCombinedCRC );
427             if (s->calculatedCombinedCRC != s->storedCombinedCRC)
428                return BZ_DATA_ERROR;
429             return r;
430          }
431          if (s->state != BZ_X_OUTPUT) return r;
432       }
433    }
434 
435 /*
436    AssertH ( 0, 6001 );
437 
438    return 0;  
439 */
440 }
441 
442 
443 /*---------------------------------------------------*/
444 int BZ_API(BZ2_bzDecompressEnd)  ( bz_stream *strm )
445 {
446    DState* s;
447    if (strm == NULL) return BZ_PARAM_ERROR;
448    s = strm->state;
449    if (s == NULL) return BZ_PARAM_ERROR;
450    if (s->strm != strm) return BZ_PARAM_ERROR;
451 
452    if (s->tt   != NULL) BZFREE(s->tt);
453    if (s->ll16 != NULL) BZFREE(s->ll16);
454    if (s->ll4  != NULL) BZFREE(s->ll4);
455 
456    BZFREE(strm->state);
457    strm->state = NULL;
458 
459    return BZ_OK;
460 }
461