bzlib 0.5.1.0 → 0.5.2.0
raw patch · 24 files changed
+694/−5423 lines, 24 filesdep +QuickCheckdep +bzip2-clibdep +bzlibdep ~basedep ~bytestringdep ~failnew-uploader
Dependencies added: QuickCheck, bzip2-clib, bzlib, tasty, tasty-hunit, tasty-quickcheck
Dependency ranges changed: base, bytestring, fail
Files
- CHANGELOG.md +6/−4
- Codec/Compression/BZip.hs +1/−1
- Codec/Compression/BZip/Internal.hs +414/−95
- Codec/Compression/BZip/Stream.hsc +105/−69
- README.md +10/−0
- bzlib.cabal +33/−26
- cbits-extra/hs-bzlib.c +9/−0
- cbits-extra/hs-bzlib.h +8/−0
- cbits/LICENSE +0/−42
- cbits/blocksort.c +0/−1094
- cbits/bzlib.c +0/−1572
- cbits/bzlib.h +0/−288
- cbits/bzlib_private.h +0/−509
- cbits/compress.c +0/−672
- cbits/crctable.c +0/−104
- cbits/decompress.c +0/−646
- cbits/huffman.c +0/−205
- cbits/randtable.c +0/−84
- examples/bunzip2.hs +0/−6
- examples/bzip2.hs +0/−6
- test/Test.hs +32/−0
- test/Test/Codec/Compression/BZip/Internal.hs +28/−0
- test/Test/Codec/Compression/BZip/Stream.hs +20/−0
- test/Utils.hs +28/−0
CHANGELOG.md view
@@ -1,6 +1,8 @@-# Revision history for bzlib+## 0.5.2.0 -## 0.5.1.0 -- 2020-06-08+* Fix CVE-2019-12900 by updating C sources to 1.0.8.+* Port incremental interface from `zlib`. -* Added `MonadFail` instance-* Constrained bounds on `base`+## 0.5.1.0++* Add `instance MonadFail Stream`.
Codec/Compression/BZip.hs view
@@ -68,7 +68,7 @@ -- -- * if the compressed stream is corrupted ----- * if the compressed stream ends permaturely+-- * if the compressed stream ends prematurely -- -- Note that the decompression is performed /lazily/. Errors in the data stream -- may not be detected until the end of the stream is demanded (since it is
Codec/Compression/BZip/Internal.hs view
@@ -1,4 +1,4 @@-{-# LANGUAGE CPP #-}+{-# LANGUAGE CPP, Rank2Types, DeriveDataTypeable #-} ----------------------------------------------------------------------------- -- | -- Copyright : (c) 2006-2008 Duncan Coutts@@ -12,18 +12,30 @@ -- ----------------------------------------------------------------------------- module Codec.Compression.BZip.Internal (-- -- * Compression+ -- * Pure interface compress,+ decompress,++ -- * Monadic incremental interface+ -- ** Incremental compression+ CompressStream(..),+ compressST,+ compressIO,+ foldCompressStream,+ foldCompressStreamWithInput,++ -- ** Incremental decompression+ DecompressStream(..),+ decompressST,+ decompressIO,+ foldDecompressStream,+ foldDecompressStreamWithInput,++ -- * The compression parameter types CompressParams(..), defaultCompressParams,-- -- * Decompression- decompress, DecompressParams(..), defaultDecompressParams,-- -- * The compression parameter types Stream.BlockSize(..), Stream.WorkFactor(..), Stream.MemoryLevel(..),@@ -31,10 +43,20 @@ import Prelude hiding (length) import Control.Monad (when)-import Control.Exception (assert)+import Control.Exception (Exception, throw, assert)+import Control.Monad.ST.Lazy hiding (stToIO)+import Control.Monad.ST.Strict (stToIO)+#if __GLASGOW_HASKELL__ >= 702+import qualified Control.Monad.ST.Unsafe as Unsafe (unsafeIOToST)+#else+import qualified Control.Monad.ST.Strict as Unsafe (unsafeIOToST)+#endif import qualified Data.ByteString.Lazy as L import qualified Data.ByteString.Lazy.Internal as L+import qualified Data.ByteString as S import qualified Data.ByteString.Internal as S+import Data.Typeable (Typeable)+import GHC.IO (noDuplicate) import qualified Codec.Compression.BZip.Stream as Stream import Codec.Compression.BZip.Stream (Stream)@@ -45,7 +67,7 @@ -- The 'compressBufferSize' is the size of the first output buffer containing -- the compressed data. If you know an approximate upper bound on the size of -- the compressed data then setting this parameter can save memory. The default--- compression output buffer size is @16k@. If your extimate is wrong it does+-- compression output buffer size is @16k@. If your estimate is wrong it does -- not matter too much, the default buffer size will be used for the remaining -- chunks. --@@ -53,7 +75,7 @@ compressBlockSize :: Stream.BlockSize, compressWorkFactor :: Stream.WorkFactor, compressBufferSize :: Int-}+} deriving (Show) -- | The full set of parameters for decompression. The defaults are -- 'defaultDecompressParams'.@@ -62,12 +84,12 @@ -- containing the uncompressed data. If you know an exact or approximate upper -- bound on the size of the decompressed data then setting this parameter can -- save memory. The default decompression output buffer size is @32k@. If your--- extimate is wrong it does not matter too much, the default buffer size will+-- estimate is wrong it does not matter too much, the default buffer size will -- be used for the remaining chunks. -- -- One particular use case for setting the 'decompressBufferSize' is if you -- know the exact size of the decompressed data and want to produce a strict--- 'Data.ByteString.ByteString'. The compression and deccompression functions+-- 'Data.ByteString.ByteString'. The compression and decompression functions -- use lazy 'Data.ByteString.Lazy.ByteString's but if you set the -- 'decompressBufferSize' correctly then you can generate a lazy -- 'Data.ByteString.Lazy.ByteString' with exactly one chunk, which can be@@ -77,10 +99,10 @@ data DecompressParams = DecompressParams { decompressMemoryLevel :: Stream.MemoryLevel, decompressBufferSize :: Int-}+} deriving (Show) -- | The default set of parameters for compression. This is typically used with--- the @compressWith@ function with specific paramaters overridden.+-- the @compressWith@ function with specific parameters overridden. -- defaultCompressParams :: CompressParams defaultCompressParams = CompressParams {@@ -90,7 +112,7 @@ } -- | The default set of parameters for decompression. This is typically used with--- the @compressWith@ function with specific paramaters overridden.+-- the @compressWith@ function with specific parameters overridden. -- defaultDecompressParams :: DecompressParams defaultDecompressParams = DecompressParams {@@ -105,34 +127,109 @@ defaultCompressBufferSize = 16 * 1024 - L.chunkOverhead defaultDecompressBufferSize = 32 * 1024 - L.chunkOverhead -{-# NOINLINE compress #-}-compress- :: CompressParams- -> L.ByteString- -> L.ByteString-compress (CompressParams blockSize workFactor initChunkSize) input =- L.fromChunks $ Stream.run $ do- Stream.compressInit blockSize Stream.Silent workFactor- case L.toChunks input of- [] -> fillBuffers 14 [] --bzip2 header is 14 bytes- S.PS inFPtr offset length : chunks -> do- Stream.pushInputBuffer inFPtr offset length- fillBuffers initChunkSize chunks +-- | The unfolding of the compression process, where you provide a sequence+-- of uncompressed data chunks as input and receive a sequence of compressed+-- data chunks as output. The process is incremental, in that the demand for+-- input and provision of output are interleaved.+--+data CompressStream m =+ CompressInputRequired {+ compressSupplyInput :: S.ByteString -> m (CompressStream m)+ }++ | CompressOutputAvailable {+ compressOutput :: !S.ByteString,+ compressNext :: m (CompressStream m)+ }++ | CompressStreamEnd++-- | A fold over the 'CompressStream' in the given monad.+--+-- One way to look at this is that it runs the stream, using callback functions+-- for the three stream events.+--+foldCompressStream :: Monad m+ => ((S.ByteString -> m a) -> m a)+ -> (S.ByteString -> m a -> m a)+ -> m a+ -> CompressStream m -> m a+foldCompressStream input output end = fold where+ fold (CompressInputRequired next) =+ input (\x -> next x >>= fold)++ fold (CompressOutputAvailable outchunk next) =+ output outchunk (next >>= fold)++ fold CompressStreamEnd =+ end++-- | A variant on 'foldCompressStream' that is pure rather than operating in a+-- monad and where the input is provided by a lazy 'L.ByteString'. So we only+-- have to deal with the output and end parts, making it just like a foldr on a+-- list of output chunks.+--+-- For example:+--+-- > toChunks = foldCompressStreamWithInput (:) []+--+foldCompressStreamWithInput :: (S.ByteString -> a -> a)+ -> a+ -> (forall s. CompressStream (ST s))+ -> L.ByteString+ -> a+foldCompressStreamWithInput chunk end = \s lbs ->+ runST (fold s (L.toChunks lbs))+ where+ fold (CompressInputRequired next) [] =+ next S.empty >>= \strm -> fold strm []++ fold (CompressInputRequired next) (inchunk:inchunks) =+ next inchunk >>= \s -> fold s inchunks++ fold (CompressOutputAvailable outchunk next) inchunks = do+ r <- next >>= \s -> fold s inchunks+ return $ chunk outchunk r++ fold CompressStreamEnd _inchunks =+ return end++compress :: CompressParams -> L.ByteString -> L.ByteString+compressST :: CompressParams -> CompressStream (ST s)+compressIO :: CompressParams -> CompressStream IO++compress params = foldCompressStreamWithInput+ L.Chunk L.Empty+ (compressStreamST params)+compressST params = compressStreamST params+compressIO params = compressStreamIO params++compressStream+ :: CompressParams -> S.ByteString -> Stream (CompressStream Stream)+compressStream (CompressParams blockSize workFactor initChunkSize) =+ \chunk -> do+ Stream.compressInit blockSize Stream.Silent workFactor+ case chunk of+ _ | S.null chunk -> fillBuffers 14 --bzip2 header is 14 bytes+ S.PS inFPtr offset length -> do+ Stream.pushInputBuffer inFPtr offset length+ fillBuffers initChunkSize+ where -- we flick between two states: -- * where one or other buffer is empty -- - in which case we refill one or both -- * where both buffers are non-empty -- - in which case we compress until a buffer is empty - fillBuffers :: Int- -> [S.ByteString]- -> Stream [S.ByteString]- fillBuffers outChunkSize inChunks = do+ fillBuffers :: Int -> Stream (CompressStream Stream)+ fillBuffers outChunkSize = do+#ifdef DEBUG Stream.consistencyCheck+#endif - -- in this state there are two possabilities:+ -- in this state there are two possibilities: -- * no outbut buffer space is available -- - in which case we must make more available -- * no input buffer is available@@ -147,26 +244,25 @@ Stream.pushOutputBuffer outFPtr 0 outChunkSize if inputBufferEmpty- then case inChunks of- [] -> drainBuffers []- S.PS inFPtr offset length : inChunks' -> do+ then return $ CompressInputRequired $ \chunk ->+ case chunk of+ _ | S.null chunk -> drainBuffers True+ S.PS inFPtr offset length -> do Stream.pushInputBuffer inFPtr offset length- drainBuffers inChunks'- else drainBuffers inChunks+ drainBuffers False+ else drainBuffers False - drainBuffers ::- [S.ByteString]- -> Stream [S.ByteString]- drainBuffers inChunks = do+ drainBuffers :: Bool -> Stream (CompressStream Stream)+ drainBuffers lastChunk = do inputBufferEmpty' <- Stream.inputBufferEmpty outputBufferFull' <- Stream.outputBufferFull assert(not outputBufferFull'- && (null inChunks || not inputBufferEmpty')) $ return ()+ && (lastChunk || not inputBufferEmpty')) $ return () -- this invariant guarantees we can always make forward progress - let action = if null inChunks then Stream.Finish else Stream.Run+ let action = if lastChunk then Stream.Finish else Stream.Run status <- Stream.compress action case status of@@ -174,10 +270,10 @@ outputBufferFull <- Stream.outputBufferFull if outputBufferFull then do (outFPtr, offset, length) <- Stream.popOutputBuffer- outChunks <- Stream.unsafeInterleave- (fillBuffers defaultCompressBufferSize inChunks)- return (S.PS outFPtr offset length : outChunks)- else do fillBuffers defaultCompressBufferSize inChunks+ let chunk = S.PS outFPtr offset length+ return $ CompressOutputAvailable chunk $ do+ fillBuffers defaultCompressBufferSize+ else do fillBuffers defaultCompressBufferSize Stream.StreamEnd -> do inputBufferEmpty <- Stream.inputBufferEmpty@@ -185,39 +281,124 @@ outputBufferBytesAvailable <- Stream.outputBufferBytesAvailable if outputBufferBytesAvailable > 0 then do (outFPtr, offset, length) <- Stream.popOutputBuffer+ let chunk = S.PS outFPtr offset length Stream.finalise- return [S.PS outFPtr offset length]+ return $ CompressOutputAvailable chunk (return CompressStreamEnd) else do Stream.finalise- return []+ return CompressStreamEnd + Stream.Error _ msg -> fail msg -{-# NOINLINE decompress #-}-decompress- :: DecompressParams- -> L.ByteString- -> L.ByteString-decompress (DecompressParams memLevel initChunkSize) input =- L.fromChunks $ Stream.run $ do- Stream.decompressInit Stream.Silent memLevel- case L.toChunks input of- [] -> fillBuffers 4 [] --always an error anyway- S.PS inFPtr offset length : chunks -> do- Stream.pushInputBuffer inFPtr offset length- fillBuffers initChunkSize chunks +data DecompressStream m =++ DecompressInputRequired {+ decompressSupplyInput :: S.ByteString -> m (DecompressStream m)+ }++ | DecompressOutputAvailable {+ decompressOutput :: !S.ByteString,+ decompressNext :: m (DecompressStream m)+ }++ -- | Includes any trailing unconsumed /input/ data.+ | DecompressStreamEnd {+ decompressUnconsumedInput :: S.ByteString+ }++ -- | An error code+ | DecompressStreamError {+ decompressStreamError :: DecompressError+ }++data DecompressError =+ TruncatedInput+ | DataFormatError String+ deriving (Typeable)++instance Show DecompressError where+ show TruncatedInput = modprefix "premature end of compressed data stream"+ show (DataFormatError detail) = modprefix ("compressed data stream format error (" ++ detail ++ ")")++modprefix :: ShowS+modprefix = ("Codec.Compression.BZip: " ++)++instance Exception DecompressError++foldDecompressStream :: Monad m+ => ((S.ByteString -> m a) -> m a)+ -> (S.ByteString -> m a -> m a)+ -> (S.ByteString -> m a)+ -> (DecompressError -> m a)+ -> DecompressStream m -> m a+foldDecompressStream input output end err = fold where+ fold (DecompressInputRequired next) =+ input (\x -> next x >>= fold)++ fold (DecompressOutputAvailable outchunk next) =+ output outchunk (next >>= fold)++ fold (DecompressStreamEnd inchunk) = end inchunk+ fold (DecompressStreamError derr) = err derr++foldDecompressStreamWithInput :: (S.ByteString -> a -> a)+ -> (L.ByteString -> a)+ -> (DecompressError -> a)+ -> (forall s. DecompressStream (ST s))+ -> L.ByteString+ -> a+foldDecompressStreamWithInput chunk end err = \s lbs ->+ runST (fold s (L.toChunks lbs))+ where+ fold (DecompressInputRequired next) [] =+ next S.empty >>= \strm -> fold strm []++ fold (DecompressInputRequired next) (inchunk:inchunks) =+ next inchunk >>= \s -> fold s inchunks++ fold (DecompressOutputAvailable outchunk next) inchunks = do+ r <- next >>= \s -> fold s inchunks+ return $ chunk outchunk r++ fold (DecompressStreamEnd inchunk) inchunks =+ return $ end (L.fromChunks (inchunk:inchunks))++ fold (DecompressStreamError derr) _ =+ return $ err derr++decompress :: DecompressParams -> L.ByteString -> L.ByteString+decompressST :: DecompressParams -> DecompressStream (ST s)+decompressIO :: DecompressParams -> DecompressStream IO++decompress params = foldDecompressStreamWithInput+ L.Chunk (const L.Empty) throw+ (decompressStreamST params)+decompressST params = decompressStreamST params+decompressIO params = decompressStreamIO params++decompressStream+ :: DecompressParams -> S.ByteString -> Stream (DecompressStream Stream)+decompressStream (DecompressParams memLevel initChunkSize) =+ \chunk -> do+ Stream.decompressInit Stream.Silent memLevel+ case chunk of+ _ | S.null chunk -> fillBuffers 4 --always an error anyway+ S.PS inFPtr offset length -> do+ Stream.pushInputBuffer inFPtr offset length+ fillBuffers initChunkSize++ where -- we flick between two states: -- * where one or other buffer is empty -- - in which case we refill one or both -- * where both buffers are non-empty -- - in which case we compress until a buffer is empty - fillBuffers :: Int- -> [S.ByteString]- -> Stream [S.ByteString]- fillBuffers outChunkSize inChunks = do+ fillBuffers :: Int -> Stream (DecompressStream Stream)+ fillBuffers outChunkSize = do - -- in this state there are two possabilities:+ -- in this state there are two possibilities: -- * no outbut buffer space is available -- - in which case we must make more available -- * no input buffer is available@@ -232,23 +413,22 @@ Stream.pushOutputBuffer outFPtr 0 outChunkSize if inputBufferEmpty- then case inChunks of- [] -> drainBuffers []- S.PS inFPtr offset length : inChunks' -> do+ then return $ DecompressInputRequired $ \chunk ->+ case chunk of+ _ | S.null chunk -> drainBuffers True+ S.PS inFPtr offset length -> do Stream.pushInputBuffer inFPtr offset length- drainBuffers inChunks'- else drainBuffers inChunks+ drainBuffers False+ else drainBuffers False - drainBuffers ::- [S.ByteString]- -> Stream [S.ByteString]- drainBuffers inChunks = do+ drainBuffers :: Bool -> Stream (DecompressStream Stream)+ drainBuffers lastChunk = do inputBufferEmpty' <- Stream.inputBufferEmpty outputBufferFull' <- Stream.outputBufferFull assert(not outputBufferFull'- && (null inChunks || not inputBufferEmpty')) $ return ()+ && (lastChunk || not inputBufferEmpty')) $ return () -- this invariant guarantees we can always make forward progress or at -- least detect premature EOF @@ -259,23 +439,162 @@ outputBufferFull <- Stream.outputBufferFull if outputBufferFull then do (outFPtr, offset, length) <- Stream.popOutputBuffer- outChunks <- Stream.unsafeInterleave- (fillBuffers defaultDecompressBufferSize inChunks)- return (S.PS outFPtr offset length : outChunks)+ let chunk = S.PS outFPtr offset length+ return $ DecompressOutputAvailable chunk $ do+ fillBuffers defaultDecompressBufferSize else do -- We need to detect if we ran out of input: inputBufferEmpty <- Stream.inputBufferEmpty- if inputBufferEmpty && null inChunks- then fail "premature end of compressed stream"- else fillBuffers defaultDecompressBufferSize inChunks+ if inputBufferEmpty && lastChunk+ then return (DecompressStreamError TruncatedInput)+ else fillBuffers defaultDecompressBufferSize Stream.StreamEnd -> do- -- Note that there may be input bytes still available if the stream- -- is embeded in some other data stream. Here we just silently discard- -- any trailing data.- outputBufferBytesAvailable <- Stream.outputBufferBytesAvailable- if outputBufferBytesAvailable > 0- then do (outFPtr, offset, length) <- Stream.popOutputBuffer- Stream.finalise- return [S.PS outFPtr offset length]- else do Stream.finalise- return []+ inputBufferEmpty <- Stream.inputBufferEmpty+ if inputBufferEmpty+ then do finish (DecompressStreamEnd S.empty)+ else do (inFPtr, offset, length) <- Stream.popRemainingInputBuffer+ let inchunk = S.PS inFPtr offset length+ finish (DecompressStreamEnd inchunk)++ Stream.Error code msg -> case code of+ Stream.DataError -> finish (DecompressStreamError (DataFormatError msg))+ _ -> fail msg++ finish end = do+ outputBufferBytesAvailable <- Stream.outputBufferBytesAvailable+ if outputBufferBytesAvailable > 0+ then do (outFPtr, offset, length) <- Stream.popOutputBuffer+ return (DecompressOutputAvailable (S.PS outFPtr offset length) (return end))+ else return end+++------------------------------------------------------------------------------++mkStateST :: ST s (Stream.State s)+mkStateIO :: IO (Stream.State RealWorld)+mkStateST = strictToLazyST Stream.mkState+mkStateIO = stToIO Stream.mkState++runStreamST :: Stream a -> Stream.State s -> ST s (a, Stream.State s)+runStreamIO :: Stream a -> Stream.State RealWorld -> IO (a, Stream.State RealWorld)+runStreamST strm zstate = strictToLazyST (Unsafe.unsafeIOToST noDuplicate >> Stream.runStream strm zstate)+runStreamIO strm zstate = stToIO (Stream.runStream strm zstate)++compressStreamIO :: CompressParams -> CompressStream IO+compressStreamIO params =+ CompressInputRequired {+ compressSupplyInput = \chunk -> do+ zstate <- mkStateIO+ let next = compressStream params+ (strm', zstate') <- runStreamIO (next chunk) zstate+ return (go strm' zstate')+ }+ where+ go :: CompressStream Stream -> Stream.State RealWorld -> CompressStream IO+ go (CompressInputRequired next) zstate =+ CompressInputRequired {+ compressSupplyInput = \chunk -> do+ (strm', zstate') <- runStreamIO (next chunk) zstate+ return (go strm' zstate')+ }++ go (CompressOutputAvailable chunk next) zstate =+ CompressOutputAvailable chunk $ do+ (strm', zstate') <- runStreamIO next zstate+ return (go strm' zstate')++ go CompressStreamEnd _ = CompressStreamEnd+++compressStreamST :: CompressParams -> CompressStream (ST s)+compressStreamST params =+ CompressInputRequired {+ compressSupplyInput = \chunk -> do+ zstate <- mkStateST+ let next = compressStream params+ (strm', zstate') <- runStreamST (next chunk) zstate+ return (go strm' zstate')+ }+ where+ go :: CompressStream Stream -> Stream.State s -> CompressStream (ST s)+ go (CompressInputRequired next) zstate =+ CompressInputRequired {+ compressSupplyInput = \chunk -> do+ (strm', zstate') <- runStreamST (next chunk) zstate+ return (go strm' zstate')+ }++ go (CompressOutputAvailable chunk next) zstate =+ CompressOutputAvailable chunk $ do+ (strm', zstate') <- runStreamST next zstate+ return (go strm' zstate')++ go CompressStreamEnd _ = CompressStreamEnd+++decompressStreamIO :: DecompressParams -> DecompressStream IO+decompressStreamIO params =+ DecompressInputRequired $ \chunk -> do+ zstate <- mkStateIO+ let next = decompressStream params+ (strm', zstate') <- runStreamIO (next chunk) zstate+ go strm' zstate'+ where+ go :: DecompressStream Stream -> Stream.State RealWorld+ -> IO (DecompressStream IO)+ go (DecompressInputRequired next) zstate =+ return $ DecompressInputRequired $ \chunk -> do+ (strm', zstate') <- runStreamIO (next chunk) zstate+ go strm' zstate'++ go (DecompressOutputAvailable chunk next) zstate =+ return $ DecompressOutputAvailable chunk $ do+ (strm', zstate') <- runStreamIO next zstate+ go strm' zstate'++ go (DecompressStreamEnd unconsumed) zstate =+ finaliseStreamEnd unconsumed zstate++ go (DecompressStreamError err) zstate = finaliseStreamError err zstate++ finaliseStreamEnd unconsumed zstate = do+ _ <- runStreamIO Stream.finalise zstate+ return (DecompressStreamEnd unconsumed)++ finaliseStreamError err zstate = do+ _ <- runStreamIO Stream.finalise zstate+ return (DecompressStreamError err)+++decompressStreamST :: DecompressParams -> DecompressStream (ST s)+decompressStreamST params =+ DecompressInputRequired $ \chunk -> do+ zstate <- mkStateST+ let next = decompressStream params+ (strm', zstate') <- runStreamST (next chunk) zstate+ go strm' zstate'+ where+ go :: DecompressStream Stream -> Stream.State s+ -> ST s (DecompressStream (ST s))+ go (DecompressInputRequired next) zstate =+ return $ DecompressInputRequired $ \chunk -> do+ (strm', zstate') <- runStreamST (next chunk) zstate+ go strm' zstate'++ go (DecompressOutputAvailable chunk next) zstate =+ return $ DecompressOutputAvailable chunk $ do+ (strm', zstate') <- runStreamST next zstate+ go strm' zstate'++ go (DecompressStreamEnd unconsumed) zstate =+ finaliseStreamEnd unconsumed zstate++ go (DecompressStreamError err) zstate = finaliseStreamError err zstate++ finaliseStreamEnd unconsumed zstate = do+ _ <- runStreamST Stream.finalise zstate+ return (DecompressStreamEnd unconsumed)++ finaliseStreamError err zstate = do+ _ <- runStreamST Stream.finalise zstate+ return (DecompressStreamError err)
Codec/Compression/BZip/Stream.hsc view
@@ -15,8 +15,9 @@ -- * The Zlib state monad Stream,- run,- unsafeInterleave,+ State,+ mkState,+ runStream, unsafeLiftIO, finalise, @@ -30,16 +31,18 @@ MemoryLevel(..), Verbosity(..), - -- * The buisness+ -- * The business compress, decompress, Status(..), Action(..),+ ErrorCode(..), -- * Buffer management -- ** Input buffer pushInputBuffer, inputBufferEmpty,+ popRemainingInputBuffer, -- ** Output buffer pushOutputBuffer,@@ -56,27 +59,33 @@ ) where import Foreign- ( Word8, Ptr, nullPtr, plusPtr, peekByteOff, pokeByteOff, mallocBytes- , ForeignPtr, FinalizerPtr, newForeignPtr_, addForeignPtrFinalizer- , finalizeForeignPtr, withForeignPtr, touchForeignPtr )+ ( Word8, Ptr, nullPtr, plusPtr, peekByteOff, pokeByteOff+ , ForeignPtr, FinalizerPtr, mallocForeignPtrBytes, addForeignPtrFinalizer+ , finalizeForeignPtr, withForeignPtr, touchForeignPtr, minusPtr ) #if __GLASGOW_HASKELL__ >= 702 import Foreign.ForeignPtr.Unsafe ( unsafeForeignPtrToPtr )-import System.IO.Unsafe ( unsafePerformIO ) #else-import Foreign ( unsafeForeignPtrToPtr, unsafePerformIO )+import Foreign ( unsafeForeignPtrToPtr ) #endif import Foreign.C import Data.ByteString.Internal (nullForeignPtr)-import System.IO.Unsafe (unsafeInterleaveIO) import System.IO (hPutStrLn, stderr)-#if !MIN_VERSION_base(4,13,0) import Control.Applicative (Applicative(..))-#endif import Control.Monad (liftM, ap)+import qualified Control.Monad.Fail as Fail+#if __GLASGOW_HASKELL__ >= 702+#if __GLASGOW_HASKELL__ >= 708+import Control.Monad.ST.Strict+#else+import Control.Monad.ST.Strict hiding (unsafeIOToST)+#endif+import Control.Monad.ST.Unsafe+#else+import Control.Monad.ST.Strict+#endif import Control.Exception (assert) -import qualified Control.Monad.Fail as Fail-import Prelude hiding (length)+import Prelude (Int, IO, Bool, String, Functor, Monad(..), Show(..), return, (>>), (>>=), fmap, (.), ($), fromIntegral, error, otherwise, (<=), (&&), (>=), show, (++), (+), (==), (-), (>)) #include "bzlib.h" @@ -107,6 +116,20 @@ inputBufferEmpty = getInAvail >>= return . (==0) +popRemainingInputBuffer :: Stream (ForeignPtr Word8, Int, Int)+popRemainingInputBuffer = do++ inBuf <- getInBuf+ inNext <- getInNext+ inAvail <- getInAvail++ -- there really should be something to pop, otherwise it's silly+ assert (inAvail > 0) $ return ()+ setInAvail 0++ return (inBuf, inNext `minusPtr` unsafeForeignPtrToPtr inBuf, inAvail)++ pushOutputBuffer :: ForeignPtr Word8 -> Int -> Int -> Stream () pushOutputBuffer outBuf' offset length = do @@ -154,7 +177,7 @@ outputBufferBytesAvailable = getOutAvail --- you needen't get all the output immediately, you can continue until+-- you needn't get all the output immediately, you can continue until -- there is no more output space available, this tells you that amount outputBufferSpaceRemaining :: Stream Int outputBufferSpaceRemaining = getOutFree@@ -228,14 +251,15 @@ fmap = liftM instance Applicative Stream where- pure = return+ pure = returnZ (<*>) = ap+ (*>) = thenZ_ instance Monad Stream where (>>=) = thenZ -- m >>= f = (m `thenZ` \a -> consistencyCheck `thenZ_` returnZ a) `thenZ` f- (>>) = thenZ_- return = returnZ+ (>>) = (*>)+ return = pure #if !MIN_VERSION_base(4,13,0) fail = Fail.fail #endif@@ -265,37 +289,39 @@ {-# INLINE thenZ_ #-} failZ :: String -> Stream a-failZ msg = BZ (\_ _ _ _ _ -> fail ("Codec.Compression.BZip: " ++ msg))+failZ msg = BZ (\_ _ _ _ _ -> Fail.fail ("Codec.Compression.BZip: " ++ msg)) -{-# NOINLINE run #-}-run :: Stream a -> a-run (BZ m) = unsafePerformIO $ do- ptr <- mallocBytes (#{const sizeof(bz_stream)})- #{poke bz_stream, bzalloc} ptr nullPtr- #{poke bz_stream, bzfree} ptr nullPtr- #{poke bz_stream, opaque} ptr nullPtr- #{poke bz_stream, next_in} ptr nullPtr- #{poke bz_stream, next_out} ptr nullPtr- #{poke bz_stream, avail_in} ptr (0 :: CUInt)- #{poke bz_stream, avail_out} ptr (0 :: CUInt)- stream <- newForeignPtr_ ptr- (_,_,_,_,a) <- m stream nullForeignPtr nullForeignPtr 0 0- return a+data State s = State !(ForeignPtr StreamState)+ !(ForeignPtr Word8)+ !(ForeignPtr Word8)+ {-# UNPACK #-} !Int+ {-# UNPACK #-} !Int +mkState :: ST s (State s)+mkState = unsafeIOToST $ do+ stream <- mallocForeignPtrBytes (#{const sizeof(bz_stream)})+ withForeignPtr stream $ \ptr -> do+ #{poke bz_stream, bzalloc} ptr nullPtr+ #{poke bz_stream, bzfree} ptr nullPtr+ #{poke bz_stream, opaque} ptr nullPtr+ #{poke bz_stream, next_in} ptr nullPtr+ #{poke bz_stream, next_out} ptr nullPtr+ #{poke bz_stream, avail_in} ptr (0 :: CUInt)+ #{poke bz_stream, avail_out} ptr (0 :: CUInt)+ return (State stream nullForeignPtr nullForeignPtr 0 0)++runStream :: Stream a -> State s -> ST s (a, State s)+runStream (BZ m) (State stream inBuf outBuf outOffset outLength) =+ unsafeIOToST $+ m stream inBuf outBuf outOffset outLength >>=+ \(inBuf', outBuf', outOffset', outLength', a) ->+ return (a, State stream inBuf' outBuf' outOffset' outLength')+ unsafeLiftIO :: IO a -> Stream a unsafeLiftIO m = BZ $ \_stream inBuf outBuf outOffset outLength -> do a <- m return (inBuf, outBuf, outOffset, outLength, a) --- It's unsafe because we discard the values here, so if you mutate anything--- between running this and forcing the result then you'll get an inconsistent--- stream state.-unsafeInterleave :: Stream a -> Stream a-unsafeInterleave (BZ m) = BZ $ \stream inBuf outBuf outOffset outLength -> do- res <- unsafeInterleaveIO (m stream inBuf outBuf outOffset outLength)- let select (_,_,_,_,a) = a- return (inBuf, outBuf, outOffset, outLength, select res)- getStreamState :: Stream (ForeignPtr StreamState) getStreamState = BZ $ \stream inBuf outBuf outOffset outLength -> do return (inBuf, outBuf, outOffset, outLength, stream)@@ -383,30 +409,39 @@ Ok -- ^ The requested action was completed successfully. | StreamEnd -- ^ Compression of data was completed, or the logical stream -- end was detected during decompression.+ | Error ErrorCode String -toStatus :: CInt -> Status-toStatus (#{const BZ_OK}) = Ok-toStatus (#{const BZ_RUN_OK}) = Ok-toStatus (#{const BZ_FLUSH_OK}) = Ok-toStatus (#{const BZ_FINISH_OK}) = Ok-toStatus (#{const BZ_STREAM_END}) = StreamEnd-toStatus other = error ("unexpected bzip2 status: " ++ show other)+data ErrorCode =+ SequenceError+ | ParamError+ | MemoryError+ | DataError+ | DataErrorMagic+ | ConfigError+ | Unexpected -failIfError :: CInt -> Stream ()-failIfError errno- | errno >= 0 = return ()- | otherwise = fail (getErrorMessage errno)+toStatus :: CInt -> Stream Status+toStatus errno = case errno of+ (#{const BZ_OK}) -> return Ok+ (#{const BZ_RUN_OK}) -> return Ok+ (#{const BZ_FLUSH_OK}) -> return Ok+ (#{const BZ_FINISH_OK}) -> return Ok+ (#{const BZ_STREAM_END}) -> return StreamEnd+ (#{const BZ_SEQUENCE_ERROR}) -> err SequenceError "incorrect sequence of calls"+ (#{const BZ_PARAM_ERROR}) -> err ParamError "incorrect parameter"+ (#{const BZ_MEM_ERROR}) -> err MemoryError "not enough memory"+ (#{const BZ_DATA_ERROR}) -> err DataError "compressed data stream is corrupt"+ (#{const BZ_DATA_ERROR_MAGIC}) -> err DataErrorMagic "data stream is not a bzip2 file"+ (#{const BZ_CONFIG_ERROR}) -> err ConfigError "configuration error in bzip2 lib"+ other -> err Unexpected+ ("unexpected bzip2 status: " ++ show other)+ where+ err errCode msg = return (Error errCode msg) -getErrorMessage :: CInt -> String-getErrorMessage errno = case errno of- #{const BZ_SEQUENCE_ERROR} -> "incorrect sequence of calls"- #{const BZ_PARAM_ERROR} -> "incorrect parameter"- #{const BZ_MEM_ERROR} -> "not enough memory"- #{const BZ_DATA_ERROR} -> "compressed data stream is corrupt"- #{const BZ_DATA_ERROR_MAGIC} -> "data stream is not a bzip2 file"- #{const BZ_CONFIG_ERROR} -> "configuration error in bzip2 lib"- other -> "unknown or impossible error code: "- ++ show other+failIfError :: CInt -> Stream ()+failIfError errno = toStatus errno >>= \status -> case status of+ (Error _ msg) -> Fail.fail msg+ _ -> return () data Action = Run@@ -449,6 +484,7 @@ data BlockSize = DefaultBlockSize -- ^ The default block size is also the maximum. | BlockSize Int -- ^ A specific block size between 1 and 9.+ deriving (Show) fromBlockSize :: BlockSize -> CInt fromBlockSize DefaultBlockSize = 9@@ -464,9 +500,10 @@ -- data MemoryLevel = DefaultMemoryLevel -- ^ The default.- | MinMemoryLevel -- ^ Use minimum memory dusing decompression. This+ | MinMemoryLevel -- ^ Use minimum memory during decompression. This -- halves the memory needed but also halves the -- decompression speed.+ deriving (Show) fromMemoryLevel :: MemoryLevel -> CInt fromMemoryLevel DefaultMemoryLevel = 0@@ -492,6 +529,7 @@ data WorkFactor = DefaultWorkFactor -- ^ The default work factor is 30. | WorkFactor Int -- ^ Allowable values range from 1 to 250 inclusive.+ deriving (Show) fromWorkFactor :: WorkFactor -> CInt fromWorkFactor DefaultWorkFactor = 0@@ -572,15 +610,13 @@ decompress_ = do err <- withStreamState $ \bzstream -> bzDecompress bzstream- failIfError err- return (toStatus err)+ toStatus err compress_ :: Action -> Stream Status compress_ action = do err <- withStreamState $ \bzstream -> bzCompress bzstream (fromAction action)- failIfError err- return (toStatus err)+ toStatus err -- | This never needs to be used as the stream's resources will be released -- automatically when no longer needed, however this can be used to release@@ -601,7 +637,7 @@ foreign import ccall unsafe "bzlib.h BZ2_bzDecompress" bzDecompress :: StreamState -> IO CInt -foreign import ccall unsafe "bzlib.h &BZ2_bzDecompressEnd"+foreign import ccall unsafe "hs-bzlib.h &_hs_bzlib_bzDecompressEnd" bzDecompressEnd :: FinalizerPtr StreamState @@ -611,5 +647,5 @@ foreign import ccall unsafe "bzlib.h BZ2_bzCompress" bzCompress :: StreamState -> CInt -> IO CInt -foreign import ccall unsafe "bzlib.h &BZ2_bzCompressEnd"+foreign import ccall unsafe "hs-bzlib.h &_hs_bzlib_bzCompressEnd" bzCompressEnd :: FinalizerPtr StreamState
+ README.md view
@@ -0,0 +1,10 @@+# bzlib [![Hackage][Hackage badge]][Hackage page]++**Compression and decompression in the bzip2 format**++This package provides a pure interface for compressing and decompressing streams of data represented as lazy `ByteString`s. It uses the `bz2` C library so it has high performance.++It provides a convenient high level API suitable for most tasks and for the few cases where more control is needed it provides access to the full `bzip2` feature set.++[Hackage page]: https://hackage.haskell.org/package/bzlib+[Hackage badge]: https://img.shields.io/hackage/v/bzlib.svg
bzlib.cabal view
@@ -1,10 +1,11 @@ name: bzlib-version: 0.5.1.0+version: 0.5.2.0 copyright: (c) 2006-2015 Duncan Coutts license: BSD3 license-file: LICENSE author: Duncan Coutts <duncan@community.haskell.org> maintainer: Duncan Coutts <duncan@community.haskell.org>+bug-reports: https://github.com/haskell/bzlib/issues category: Codec synopsis: Compression and decompression in the bzip2 format description: This package provides a pure interface for compressing and @@ -16,42 +17,48 @@ tasks and for the few cases where more control is needed it provides access to the full bzip2 feature set. build-type: Simple-cabal-version: >= 1.10-extra-source-files: cbits/bzlib_private.h cbits/LICENSE- -- demo programs:- examples/bzip2.hs examples/bunzip2.hs- -- changelog- CHANGELOG.md+cabal-version: 2.0+extra-doc-files: README.md CHANGELOG.md+extra-source-files: cbits-extra/hs-bzlib.h -source-repository head- type: darcs- location: http://code.haskell.org/bzlib/+tested-with: GHC==9.8.2, GHC==9.6.4, GHC==9.4.8, GHC==9.2.8, GHC==9.0.2, GHC==8.10.7, GHC==8.8.4, GHC==8.6.5, GHC==8.4.4, GHC==8.2.2, GHC==8.0.2, GHC==7.10.3, GHC==7.8.4, GHC==7.6.3, GHC==7.4.2, GHC==7.2.2, GHC==7.0.4 -source-repository this+source-repository head type: git- location: https://github.com/hackage-trustees/bzlib.git- tag: 0.5.1.0+ location: https://github.com/haskell/bzlib.git library default-language: Haskell2010 exposed-modules: Codec.Compression.BZip, Codec.Compression.BZip.Internal other-modules: Codec.Compression.BZip.Stream- default-extensions: CPP, ForeignFunctionInterface- build-depends: base >= 4.3 && < 4.15,- bytestring == 0.9.* || == 0.10.*- if !impl(ghc >=8.0)- build-depends: fail ==4.9.*+ build-depends: base >= 3 && < 5,+ bytestring >= 0.9 && < 0.13+ if impl(ghc < 8.0)+ build-depends: fail < 5+ if os(windows)+ build-depends: base >= 4.11 includes: bzlib.h ghc-options: -Wall- if !os(windows)+ if !(os(windows) || impl(ghcjs) || os(ghcjs) || arch(wasm32)) -- Normally we use the the standard system bz2 lib: extra-libraries: bz2 else- -- However for the benefit of users of Windows (which does not have zlib- -- by default) we bundle a complete copy of the C sources of bzip2-1.0.6- c-sources: cbits/blocksort.c cbits/bzlib.c cbits/compress.c- cbits/crctable.c cbits/decompress.c cbits/huffman.c- cbits/randtable.c- include-dirs: cbits- install-includes: bzlib.h+ build-depends: bzip2-clib < 1.1+ include-dirs: cbits-extra+ c-sources: cbits-extra/hs-bzlib.c++test-suite tests+ type: exitcode-stdio-1.0+ main-is: Test.hs+ other-modules: Utils,+ Test.Codec.Compression.BZip.Internal,+ Test.Codec.Compression.BZip.Stream+ hs-source-dirs: test+ default-language: Haskell2010+ build-depends: base, bytestring, bzlib,+ QuickCheck == 2.*,+ tasty >= 0.8 && < 1.6,+ tasty-quickcheck >= 0.8 && < 0.11,+ tasty-hunit >= 0.8 && < 0.11+ ghc-options: -Wall
+ cbits-extra/hs-bzlib.c view
@@ -0,0 +1,9 @@+#include "hs-bzlib.h"++void _hs_bzlib_bzCompressEnd(bz_stream * strm) {+ BZ2_bzCompressEnd(strm);+}++void _hs_bzlib_bzDecompressEnd(bz_stream * strm) {+ BZ2_bzDecompressEnd(strm);+}
+ cbits-extra/hs-bzlib.h view
@@ -0,0 +1,8 @@+#ifndef HS_BZLIB_EXTRAS+#define HS_BZLIB_EXTRAS++#include "bzlib.h"++void _hs_bzlib_bzCompressEnd(bz_stream * strm);+void _hs_bzlib_bzDecompressEnd(bz_stream * strm);+#endif
− cbits/LICENSE
@@ -1,42 +0,0 @@------------------------------------------------------------------------------This program, "bzip2", the associated library "libbzip2", and all-documentation, are copyright (C) 1996-2010 Julian R Seward. All-rights reserved.--Redistribution and use in source and binary forms, with or without-modification, are permitted provided that the following conditions-are met:--1. Redistributions of source code must retain the above copyright- notice, this list of conditions and the following disclaimer.--2. The origin of this software must not be misrepresented; you must - not claim that you wrote the original software. If you use this - software in a product, an acknowledgment in the product - documentation would be appreciated but is not required.--3. Altered source versions must be plainly marked as such, and must- not be misrepresented as being the original software.--4. The name of the author may not be used to endorse or promote - products derived from this software without specific prior written - permission.--THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS-OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED-WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE-ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY-DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL-DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE-GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS-INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,-WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING-NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS-SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.--Julian Seward, jseward@bzip.org-bzip2/libbzip2 version 1.0.6 of 6 September 2010----------------------------------------------------------------------------
− cbits/blocksort.c
@@ -1,1094 +0,0 @@--/*-------------------------------------------------------------*/-/*--- Block sorting machinery ---*/-/*--- blocksort.c ---*/-/*-------------------------------------------------------------*/--/* ------------------------------------------------------------------- This file is part of bzip2/libbzip2, a program and library for- lossless, block-sorting data compression.-- bzip2/libbzip2 version 1.0.6 of 6 September 2010- Copyright (C) 1996-2010 Julian Seward <jseward@bzip.org>-- Please read the WARNING, DISCLAIMER and PATENTS sections in the - README file.-- This program is released under the terms of the license contained- in the file LICENSE.- ------------------------------------------------------------------ */---#include "bzlib_private.h"--/*---------------------------------------------*/-/*--- Fallback O(N log(N)^2) sorting ---*/-/*--- algorithm, for repetitive blocks ---*/-/*---------------------------------------------*/--/*---------------------------------------------*/-static -__inline__-void fallbackSimpleSort ( UInt32* fmap, - UInt32* eclass, - Int32 lo, - Int32 hi )-{- Int32 i, j, tmp;- UInt32 ec_tmp;-- if (lo == hi) return;-- if (hi - lo > 3) {- for ( i = hi-4; i >= lo; i-- ) {- tmp = fmap[i];- ec_tmp = eclass[tmp];- for ( j = i+4; j <= hi && ec_tmp > eclass[fmap[j]]; j += 4 )- fmap[j-4] = fmap[j];- fmap[j-4] = tmp;- }- }-- for ( i = hi-1; i >= lo; i-- ) {- tmp = fmap[i];- ec_tmp = eclass[tmp];- for ( j = i+1; j <= hi && ec_tmp > eclass[fmap[j]]; j++ )- fmap[j-1] = fmap[j];- fmap[j-1] = tmp;- }-}---/*---------------------------------------------*/-#define fswap(zz1, zz2) \- { Int32 zztmp = zz1; zz1 = zz2; zz2 = zztmp; }--#define fvswap(zzp1, zzp2, zzn) \-{ \- Int32 yyp1 = (zzp1); \- Int32 yyp2 = (zzp2); \- Int32 yyn = (zzn); \- while (yyn > 0) { \- fswap(fmap[yyp1], fmap[yyp2]); \- yyp1++; yyp2++; yyn--; \- } \-}---#define fmin(a,b) ((a) < (b)) ? (a) : (b)--#define fpush(lz,hz) { stackLo[sp] = lz; \- stackHi[sp] = hz; \- sp++; }--#define fpop(lz,hz) { sp--; \- lz = stackLo[sp]; \- hz = stackHi[sp]; }--#define FALLBACK_QSORT_SMALL_THRESH 10-#define FALLBACK_QSORT_STACK_SIZE 100---static-void fallbackQSort3 ( UInt32* fmap, - UInt32* eclass,- Int32 loSt, - Int32 hiSt )-{- Int32 unLo, unHi, ltLo, gtHi, n, m;- Int32 sp, lo, hi;- UInt32 med, r, r3;- Int32 stackLo[FALLBACK_QSORT_STACK_SIZE];- Int32 stackHi[FALLBACK_QSORT_STACK_SIZE];-- r = 0;-- sp = 0;- fpush ( loSt, hiSt );-- while (sp > 0) {-- AssertH ( sp < FALLBACK_QSORT_STACK_SIZE - 1, 1004 );-- fpop ( lo, hi );- if (hi - lo < FALLBACK_QSORT_SMALL_THRESH) {- fallbackSimpleSort ( fmap, eclass, lo, hi );- continue;- }-- /* Random partitioning. Median of 3 sometimes fails to- avoid bad cases. Median of 9 seems to help but - looks rather expensive. This too seems to work but- is cheaper. Guidance for the magic constants - 7621 and 32768 is taken from Sedgewick's algorithms- book, chapter 35.- */- r = ((r * 7621) + 1) % 32768;- r3 = r % 3;- if (r3 == 0) med = eclass[fmap[lo]]; else- if (r3 == 1) med = eclass[fmap[(lo+hi)>>1]]; else- med = eclass[fmap[hi]];-- unLo = ltLo = lo;- unHi = gtHi = hi;-- while (1) {- while (1) {- if (unLo > unHi) break;- n = (Int32)eclass[fmap[unLo]] - (Int32)med;- if (n == 0) { - fswap(fmap[unLo], fmap[ltLo]); - ltLo++; unLo++; - continue; - };- if (n > 0) break;- unLo++;- }- while (1) {- if (unLo > unHi) break;- n = (Int32)eclass[fmap[unHi]] - (Int32)med;- if (n == 0) { - fswap(fmap[unHi], fmap[gtHi]); - gtHi--; unHi--; - continue; - };- if (n < 0) break;- unHi--;- }- if (unLo > unHi) break;- fswap(fmap[unLo], fmap[unHi]); unLo++; unHi--;- }-- AssertD ( unHi == unLo-1, "fallbackQSort3(2)" );-- if (gtHi < ltLo) continue;-- n = fmin(ltLo-lo, unLo-ltLo); fvswap(lo, unLo-n, n);- m = fmin(hi-gtHi, gtHi-unHi); fvswap(unLo, hi-m+1, m);-- n = lo + unLo - ltLo - 1;- m = hi - (gtHi - unHi) + 1;-- if (n - lo > hi - m) {- fpush ( lo, n );- fpush ( m, hi );- } else {- fpush ( m, hi );- fpush ( lo, n );- }- }-}--#undef fmin-#undef fpush-#undef fpop-#undef fswap-#undef fvswap-#undef FALLBACK_QSORT_SMALL_THRESH-#undef FALLBACK_QSORT_STACK_SIZE---/*---------------------------------------------*/-/* Pre:- nblock > 0- eclass exists for [0 .. nblock-1]- ((UChar*)eclass) [0 .. nblock-1] holds block- ptr exists for [0 .. nblock-1]-- Post:- ((UChar*)eclass) [0 .. nblock-1] holds block- All other areas of eclass destroyed- fmap [0 .. nblock-1] holds sorted order- bhtab [ 0 .. 2+(nblock/32) ] destroyed-*/--#define SET_BH(zz) bhtab[(zz) >> 5] |= (1 << ((zz) & 31))-#define CLEAR_BH(zz) bhtab[(zz) >> 5] &= ~(1 << ((zz) & 31))-#define ISSET_BH(zz) (bhtab[(zz) >> 5] & (1 << ((zz) & 31)))-#define WORD_BH(zz) bhtab[(zz) >> 5]-#define UNALIGNED_BH(zz) ((zz) & 0x01f)--static-void fallbackSort ( UInt32* fmap, - UInt32* eclass, - UInt32* bhtab,- Int32 nblock,- Int32 verb )-{- Int32 ftab[257];- Int32 ftabCopy[256];- Int32 H, i, j, k, l, r, cc, cc1;- Int32 nNotDone;- Int32 nBhtab;- UChar* eclass8 = (UChar*)eclass;-- /*--- Initial 1-char radix sort to generate- initial fmap and initial BH bits.- --*/- if (verb >= 4)- VPrintf0 ( " bucket sorting ...\n" );- for (i = 0; i < 257; i++) ftab[i] = 0;- for (i = 0; i < nblock; i++) ftab[eclass8[i]]++;- for (i = 0; i < 256; i++) ftabCopy[i] = ftab[i];- for (i = 1; i < 257; i++) ftab[i] += ftab[i-1];-- for (i = 0; i < nblock; i++) {- j = eclass8[i];- k = ftab[j] - 1;- ftab[j] = k;- fmap[k] = i;- }-- nBhtab = 2 + (nblock / 32);- for (i = 0; i < nBhtab; i++) bhtab[i] = 0;- for (i = 0; i < 256; i++) SET_BH(ftab[i]);-- /*--- Inductively refine the buckets. Kind-of an- "exponential radix sort" (!), inspired by the- Manber-Myers suffix array construction algorithm.- --*/-- /*-- set sentinel bits for block-end detection --*/- for (i = 0; i < 32; i++) { - SET_BH(nblock + 2*i);- CLEAR_BH(nblock + 2*i + 1);- }-- /*-- the log(N) loop --*/- H = 1;- while (1) {-- if (verb >= 4) - VPrintf1 ( " depth %6d has ", H );-- j = 0;- for (i = 0; i < nblock; i++) {- if (ISSET_BH(i)) j = i;- k = fmap[i] - H; if (k < 0) k += nblock;- eclass[k] = j;- }-- nNotDone = 0;- r = -1;- while (1) {-- /*-- find the next non-singleton bucket --*/- k = r + 1;- while (ISSET_BH(k) && UNALIGNED_BH(k)) k++;- if (ISSET_BH(k)) {- while (WORD_BH(k) == 0xffffffff) k += 32;- while (ISSET_BH(k)) k++;- }- l = k - 1;- if (l >= nblock) break;- while (!ISSET_BH(k) && UNALIGNED_BH(k)) k++;- if (!ISSET_BH(k)) {- while (WORD_BH(k) == 0x00000000) k += 32;- while (!ISSET_BH(k)) k++;- }- r = k - 1;- if (r >= nblock) break;-- /*-- now [l, r] bracket current bucket --*/- if (r > l) {- nNotDone += (r - l + 1);- fallbackQSort3 ( fmap, eclass, l, r );-- /*-- scan bucket and generate header bits-- */- cc = -1;- for (i = l; i <= r; i++) {- cc1 = eclass[fmap[i]];- if (cc != cc1) { SET_BH(i); cc = cc1; };- }- }- }-- if (verb >= 4) - VPrintf1 ( "%6d unresolved strings\n", nNotDone );-- H *= 2;- if (H > nblock || nNotDone == 0) break;- }-- /*-- - Reconstruct the original block in- eclass8 [0 .. nblock-1], since the- previous phase destroyed it.- --*/- if (verb >= 4)- VPrintf0 ( " reconstructing block ...\n" );- j = 0;- for (i = 0; i < nblock; i++) {- while (ftabCopy[j] == 0) j++;- ftabCopy[j]--;- eclass8[fmap[i]] = (UChar)j;- }- AssertH ( j < 256, 1005 );-}--#undef SET_BH-#undef CLEAR_BH-#undef ISSET_BH-#undef WORD_BH-#undef UNALIGNED_BH---/*---------------------------------------------*/-/*--- The main, O(N^2 log(N)) sorting ---*/-/*--- algorithm. Faster for "normal" ---*/-/*--- non-repetitive blocks. ---*/-/*---------------------------------------------*/--/*---------------------------------------------*/-static-__inline__-Bool mainGtU ( UInt32 i1, - UInt32 i2,- UChar* block, - UInt16* quadrant,- UInt32 nblock,- Int32* budget )-{- Int32 k;- UChar c1, c2;- UInt16 s1, s2;-- AssertD ( i1 != i2, "mainGtU" );- /* 1 */- c1 = block[i1]; c2 = block[i2];- if (c1 != c2) return (c1 > c2);- i1++; i2++;- /* 2 */- c1 = block[i1]; c2 = block[i2];- if (c1 != c2) return (c1 > c2);- i1++; i2++;- /* 3 */- c1 = block[i1]; c2 = block[i2];- if (c1 != c2) return (c1 > c2);- i1++; i2++;- /* 4 */- c1 = block[i1]; c2 = block[i2];- if (c1 != c2) return (c1 > c2);- i1++; i2++;- /* 5 */- c1 = block[i1]; c2 = block[i2];- if (c1 != c2) return (c1 > c2);- i1++; i2++;- /* 6 */- c1 = block[i1]; c2 = block[i2];- if (c1 != c2) return (c1 > c2);- i1++; i2++;- /* 7 */- c1 = block[i1]; c2 = block[i2];- if (c1 != c2) return (c1 > c2);- i1++; i2++;- /* 8 */- c1 = block[i1]; c2 = block[i2];- if (c1 != c2) return (c1 > c2);- i1++; i2++;- /* 9 */- c1 = block[i1]; c2 = block[i2];- if (c1 != c2) return (c1 > c2);- i1++; i2++;- /* 10 */- c1 = block[i1]; c2 = block[i2];- if (c1 != c2) return (c1 > c2);- i1++; i2++;- /* 11 */- c1 = block[i1]; c2 = block[i2];- if (c1 != c2) return (c1 > c2);- i1++; i2++;- /* 12 */- c1 = block[i1]; c2 = block[i2];- if (c1 != c2) return (c1 > c2);- i1++; i2++;-- k = nblock + 8;-- do {- /* 1 */- c1 = block[i1]; c2 = block[i2];- if (c1 != c2) return (c1 > c2);- s1 = quadrant[i1]; s2 = quadrant[i2];- if (s1 != s2) return (s1 > s2);- i1++; i2++;- /* 2 */- c1 = block[i1]; c2 = block[i2];- if (c1 != c2) return (c1 > c2);- s1 = quadrant[i1]; s2 = quadrant[i2];- if (s1 != s2) return (s1 > s2);- i1++; i2++;- /* 3 */- c1 = block[i1]; c2 = block[i2];- if (c1 != c2) return (c1 > c2);- s1 = quadrant[i1]; s2 = quadrant[i2];- if (s1 != s2) return (s1 > s2);- i1++; i2++;- /* 4 */- c1 = block[i1]; c2 = block[i2];- if (c1 != c2) return (c1 > c2);- s1 = quadrant[i1]; s2 = quadrant[i2];- if (s1 != s2) return (s1 > s2);- i1++; i2++;- /* 5 */- c1 = block[i1]; c2 = block[i2];- if (c1 != c2) return (c1 > c2);- s1 = quadrant[i1]; s2 = quadrant[i2];- if (s1 != s2) return (s1 > s2);- i1++; i2++;- /* 6 */- c1 = block[i1]; c2 = block[i2];- if (c1 != c2) return (c1 > c2);- s1 = quadrant[i1]; s2 = quadrant[i2];- if (s1 != s2) return (s1 > s2);- i1++; i2++;- /* 7 */- c1 = block[i1]; c2 = block[i2];- if (c1 != c2) return (c1 > c2);- s1 = quadrant[i1]; s2 = quadrant[i2];- if (s1 != s2) return (s1 > s2);- i1++; i2++;- /* 8 */- c1 = block[i1]; c2 = block[i2];- if (c1 != c2) return (c1 > c2);- s1 = quadrant[i1]; s2 = quadrant[i2];- if (s1 != s2) return (s1 > s2);- i1++; i2++;-- if (i1 >= nblock) i1 -= nblock;- if (i2 >= nblock) i2 -= nblock;-- k -= 8;- (*budget)--;- }- while (k >= 0);-- return False;-}---/*---------------------------------------------*/-/*--- Knuth's increments seem to work better- than Incerpi-Sedgewick here. Possibly- because the number of elems to sort is- usually small, typically <= 20.---*/-static-Int32 incs[14] = { 1, 4, 13, 40, 121, 364, 1093, 3280,- 9841, 29524, 88573, 265720,- 797161, 2391484 };--static-void mainSimpleSort ( UInt32* ptr,- UChar* block,- UInt16* quadrant,- Int32 nblock,- Int32 lo, - Int32 hi, - Int32 d,- Int32* budget )-{- Int32 i, j, h, bigN, hp;- UInt32 v;-- bigN = hi - lo + 1;- if (bigN < 2) return;-- hp = 0;- while (incs[hp] < bigN) hp++;- hp--;-- for (; hp >= 0; hp--) {- h = incs[hp];-- i = lo + h;- while (True) {-- /*-- copy 1 --*/- if (i > hi) break;- v = ptr[i];- j = i;- while ( mainGtU ( - ptr[j-h]+d, v+d, block, quadrant, nblock, budget - ) ) {- ptr[j] = ptr[j-h];- j = j - h;- if (j <= (lo + h - 1)) break;- }- ptr[j] = v;- i++;-- /*-- copy 2 --*/- if (i > hi) break;- v = ptr[i];- j = i;- while ( mainGtU ( - ptr[j-h]+d, v+d, block, quadrant, nblock, budget - ) ) {- ptr[j] = ptr[j-h];- j = j - h;- if (j <= (lo + h - 1)) break;- }- ptr[j] = v;- i++;-- /*-- copy 3 --*/- if (i > hi) break;- v = ptr[i];- j = i;- while ( mainGtU ( - ptr[j-h]+d, v+d, block, quadrant, nblock, budget - ) ) {- ptr[j] = ptr[j-h];- j = j - h;- if (j <= (lo + h - 1)) break;- }- ptr[j] = v;- i++;-- if (*budget < 0) return;- }- }-}---/*---------------------------------------------*/-/*--- The following is an implementation of- an elegant 3-way quicksort for strings,- described in a paper "Fast Algorithms for- Sorting and Searching Strings", by Robert- Sedgewick and Jon L. Bentley.---*/--#define mswap(zz1, zz2) \- { Int32 zztmp = zz1; zz1 = zz2; zz2 = zztmp; }--#define mvswap(zzp1, zzp2, zzn) \-{ \- Int32 yyp1 = (zzp1); \- Int32 yyp2 = (zzp2); \- Int32 yyn = (zzn); \- while (yyn > 0) { \- mswap(ptr[yyp1], ptr[yyp2]); \- yyp1++; yyp2++; yyn--; \- } \-}--static -__inline__-UChar mmed3 ( UChar a, UChar b, UChar c )-{- UChar t;- if (a > b) { t = a; a = b; b = t; };- if (b > c) { - b = c;- if (a > b) b = a;- }- return b;-}--#define mmin(a,b) ((a) < (b)) ? (a) : (b)--#define mpush(lz,hz,dz) { stackLo[sp] = lz; \- stackHi[sp] = hz; \- stackD [sp] = dz; \- sp++; }--#define mpop(lz,hz,dz) { sp--; \- lz = stackLo[sp]; \- hz = stackHi[sp]; \- dz = stackD [sp]; }---#define mnextsize(az) (nextHi[az]-nextLo[az])--#define mnextswap(az,bz) \- { Int32 tz; \- tz = nextLo[az]; nextLo[az] = nextLo[bz]; nextLo[bz] = tz; \- tz = nextHi[az]; nextHi[az] = nextHi[bz]; nextHi[bz] = tz; \- tz = nextD [az]; nextD [az] = nextD [bz]; nextD [bz] = tz; }---#define MAIN_QSORT_SMALL_THRESH 20-#define MAIN_QSORT_DEPTH_THRESH (BZ_N_RADIX + BZ_N_QSORT)-#define MAIN_QSORT_STACK_SIZE 100--static-void mainQSort3 ( UInt32* ptr,- UChar* block,- UInt16* quadrant,- Int32 nblock,- Int32 loSt, - Int32 hiSt, - Int32 dSt,- Int32* budget )-{- Int32 unLo, unHi, ltLo, gtHi, n, m, med;- Int32 sp, lo, hi, d;-- Int32 stackLo[MAIN_QSORT_STACK_SIZE];- Int32 stackHi[MAIN_QSORT_STACK_SIZE];- Int32 stackD [MAIN_QSORT_STACK_SIZE];-- Int32 nextLo[3];- Int32 nextHi[3];- Int32 nextD [3];-- sp = 0;- mpush ( loSt, hiSt, dSt );-- while (sp > 0) {-- AssertH ( sp < MAIN_QSORT_STACK_SIZE - 2, 1001 );-- mpop ( lo, hi, d );- if (hi - lo < MAIN_QSORT_SMALL_THRESH || - d > MAIN_QSORT_DEPTH_THRESH) {- mainSimpleSort ( ptr, block, quadrant, nblock, lo, hi, d, budget );- if (*budget < 0) return;- continue;- }-- med = (Int32) - mmed3 ( block[ptr[ lo ]+d],- block[ptr[ hi ]+d],- block[ptr[ (lo+hi)>>1 ]+d] );-- unLo = ltLo = lo;- unHi = gtHi = hi;-- while (True) {- while (True) {- if (unLo > unHi) break;- n = ((Int32)block[ptr[unLo]+d]) - med;- if (n == 0) { - mswap(ptr[unLo], ptr[ltLo]); - ltLo++; unLo++; continue; - };- if (n > 0) break;- unLo++;- }- while (True) {- if (unLo > unHi) break;- n = ((Int32)block[ptr[unHi]+d]) - med;- if (n == 0) { - mswap(ptr[unHi], ptr[gtHi]); - gtHi--; unHi--; continue; - };- if (n < 0) break;- unHi--;- }- if (unLo > unHi) break;- mswap(ptr[unLo], ptr[unHi]); unLo++; unHi--;- }-- AssertD ( unHi == unLo-1, "mainQSort3(2)" );-- if (gtHi < ltLo) {- mpush(lo, hi, d+1 );- continue;- }-- n = mmin(ltLo-lo, unLo-ltLo); mvswap(lo, unLo-n, n);- m = mmin(hi-gtHi, gtHi-unHi); mvswap(unLo, hi-m+1, m);-- n = lo + unLo - ltLo - 1;- m = hi - (gtHi - unHi) + 1;-- nextLo[0] = lo; nextHi[0] = n; nextD[0] = d;- nextLo[1] = m; nextHi[1] = hi; nextD[1] = d;- nextLo[2] = n+1; nextHi[2] = m-1; nextD[2] = d+1;-- if (mnextsize(0) < mnextsize(1)) mnextswap(0,1);- if (mnextsize(1) < mnextsize(2)) mnextswap(1,2);- if (mnextsize(0) < mnextsize(1)) mnextswap(0,1);-- AssertD (mnextsize(0) >= mnextsize(1), "mainQSort3(8)" );- AssertD (mnextsize(1) >= mnextsize(2), "mainQSort3(9)" );-- mpush (nextLo[0], nextHi[0], nextD[0]);- mpush (nextLo[1], nextHi[1], nextD[1]);- mpush (nextLo[2], nextHi[2], nextD[2]);- }-}--#undef mswap-#undef mvswap-#undef mpush-#undef mpop-#undef mmin-#undef mnextsize-#undef mnextswap-#undef MAIN_QSORT_SMALL_THRESH-#undef MAIN_QSORT_DEPTH_THRESH-#undef MAIN_QSORT_STACK_SIZE---/*---------------------------------------------*/-/* Pre:- nblock > N_OVERSHOOT- block32 exists for [0 .. nblock-1 +N_OVERSHOOT]- ((UChar*)block32) [0 .. nblock-1] holds block- ptr exists for [0 .. nblock-1]-- Post:- ((UChar*)block32) [0 .. nblock-1] holds block- All other areas of block32 destroyed- ftab [0 .. 65536 ] destroyed- ptr [0 .. nblock-1] holds sorted order- if (*budget < 0), sorting was abandoned-*/--#define BIGFREQ(b) (ftab[((b)+1) << 8] - ftab[(b) << 8])-#define SETMASK (1 << 21)-#define CLEARMASK (~(SETMASK))--static-void mainSort ( UInt32* ptr, - UChar* block,- UInt16* quadrant, - UInt32* ftab,- Int32 nblock,- Int32 verb,- Int32* budget )-{- Int32 i, j, k, ss, sb;- Int32 runningOrder[256];- Bool bigDone[256];- Int32 copyStart[256];- Int32 copyEnd [256];- UChar c1;- Int32 numQSorted;- UInt16 s;- if (verb >= 4) VPrintf0 ( " main sort initialise ...\n" );-- /*-- set up the 2-byte frequency table --*/- for (i = 65536; i >= 0; i--) ftab[i] = 0;-- j = block[0] << 8;- i = nblock-1;- for (; i >= 3; i -= 4) {- quadrant[i] = 0;- j = (j >> 8) | ( ((UInt16)block[i]) << 8);- ftab[j]++;- quadrant[i-1] = 0;- j = (j >> 8) | ( ((UInt16)block[i-1]) << 8);- ftab[j]++;- quadrant[i-2] = 0;- j = (j >> 8) | ( ((UInt16)block[i-2]) << 8);- ftab[j]++;- quadrant[i-3] = 0;- j = (j >> 8) | ( ((UInt16)block[i-3]) << 8);- ftab[j]++;- }- for (; i >= 0; i--) {- quadrant[i] = 0;- j = (j >> 8) | ( ((UInt16)block[i]) << 8);- ftab[j]++;- }-- /*-- (emphasises close relationship of block & quadrant) --*/- for (i = 0; i < BZ_N_OVERSHOOT; i++) {- block [nblock+i] = block[i];- quadrant[nblock+i] = 0;- }-- if (verb >= 4) VPrintf0 ( " bucket sorting ...\n" );-- /*-- Complete the initial radix sort --*/- for (i = 1; i <= 65536; i++) ftab[i] += ftab[i-1];-- s = block[0] << 8;- i = nblock-1;- for (; i >= 3; i -= 4) {- s = (s >> 8) | (block[i] << 8);- j = ftab[s] -1;- ftab[s] = j;- ptr[j] = i;- s = (s >> 8) | (block[i-1] << 8);- j = ftab[s] -1;- ftab[s] = j;- ptr[j] = i-1;- s = (s >> 8) | (block[i-2] << 8);- j = ftab[s] -1;- ftab[s] = j;- ptr[j] = i-2;- s = (s >> 8) | (block[i-3] << 8);- j = ftab[s] -1;- ftab[s] = j;- ptr[j] = i-3;- }- for (; i >= 0; i--) {- s = (s >> 8) | (block[i] << 8);- j = ftab[s] -1;- ftab[s] = j;- ptr[j] = i;- }-- /*--- Now ftab contains the first loc of every small bucket.- Calculate the running order, from smallest to largest- big bucket.- --*/- for (i = 0; i <= 255; i++) {- bigDone [i] = False;- runningOrder[i] = i;- }-- {- Int32 vv;- Int32 h = 1;- do h = 3 * h + 1; while (h <= 256);- do {- h = h / 3;- for (i = h; i <= 255; i++) {- vv = runningOrder[i];- j = i;- while ( BIGFREQ(runningOrder[j-h]) > BIGFREQ(vv) ) {- runningOrder[j] = runningOrder[j-h];- j = j - h;- if (j <= (h - 1)) goto zero;- }- zero:- runningOrder[j] = vv;- }- } while (h != 1);- }-- /*--- The main sorting loop.- --*/-- numQSorted = 0;-- for (i = 0; i <= 255; i++) {-- /*--- Process big buckets, starting with the least full.- Basically this is a 3-step process in which we call- mainQSort3 to sort the small buckets [ss, j], but- also make a big effort to avoid the calls if we can.- --*/- ss = runningOrder[i];-- /*--- Step 1:- Complete the big bucket [ss] by quicksorting- any unsorted small buckets [ss, j], for j != ss. - Hopefully previous pointer-scanning phases have already- completed many of the small buckets [ss, j], so- we don't have to sort them at all.- --*/- for (j = 0; j <= 255; j++) {- if (j != ss) {- sb = (ss << 8) + j;- if ( ! (ftab[sb] & SETMASK) ) {- Int32 lo = ftab[sb] & CLEARMASK;- Int32 hi = (ftab[sb+1] & CLEARMASK) - 1;- if (hi > lo) {- if (verb >= 4)- VPrintf4 ( " qsort [0x%x, 0x%x] "- "done %d this %d\n",- ss, j, numQSorted, hi - lo + 1 );- mainQSort3 ( - ptr, block, quadrant, nblock, - lo, hi, BZ_N_RADIX, budget - ); - numQSorted += (hi - lo + 1);- if (*budget < 0) return;- }- }- ftab[sb] |= SETMASK;- }- }-- AssertH ( !bigDone[ss], 1006 );-- /*--- Step 2:- Now scan this big bucket [ss] so as to synthesise the- sorted order for small buckets [t, ss] for all t,- including, magically, the bucket [ss,ss] too.- This will avoid doing Real Work in subsequent Step 1's.- --*/- {- for (j = 0; j <= 255; j++) {- copyStart[j] = ftab[(j << 8) + ss] & CLEARMASK;- copyEnd [j] = (ftab[(j << 8) + ss + 1] & CLEARMASK) - 1;- }- for (j = ftab[ss << 8] & CLEARMASK; j < copyStart[ss]; j++) {- k = ptr[j]-1; if (k < 0) k += nblock;- c1 = block[k];- if (!bigDone[c1])- ptr[ copyStart[c1]++ ] = k;- }- for (j = (ftab[(ss+1) << 8] & CLEARMASK) - 1; j > copyEnd[ss]; j--) {- k = ptr[j]-1; if (k < 0) k += nblock;- c1 = block[k];- if (!bigDone[c1]) - ptr[ copyEnd[c1]-- ] = k;- }- }-- AssertH ( (copyStart[ss]-1 == copyEnd[ss])- || - /* Extremely rare case missing in bzip2-1.0.0 and 1.0.1.- Necessity for this case is demonstrated by compressing - a sequence of approximately 48.5 million of character - 251; 1.0.0/1.0.1 will then die here. */- (copyStart[ss] == 0 && copyEnd[ss] == nblock-1),- 1007 )-- for (j = 0; j <= 255; j++) ftab[(j << 8) + ss] |= SETMASK;-- /*--- Step 3:- The [ss] big bucket is now done. Record this fact,- and update the quadrant descriptors. Remember to- update quadrants in the overshoot area too, if- necessary. The "if (i < 255)" test merely skips- this updating for the last bucket processed, since- updating for the last bucket is pointless.-- The quadrant array provides a way to incrementally- cache sort orderings, as they appear, so as to - make subsequent comparisons in fullGtU() complete- faster. For repetitive blocks this makes a big- difference (but not big enough to be able to avoid- the fallback sorting mechanism, exponential radix sort).-- The precise meaning is: at all times:-- for 0 <= i < nblock and 0 <= j <= nblock-- if block[i] != block[j], -- then the relative values of quadrant[i] and - quadrant[j] are meaningless.-- else {- if quadrant[i] < quadrant[j]- then the string starting at i lexicographically- precedes the string starting at j-- else if quadrant[i] > quadrant[j]- then the string starting at j lexicographically- precedes the string starting at i-- else- the relative ordering of the strings starting- at i and j has not yet been determined.- }- --*/- bigDone[ss] = True;-- if (i < 255) {- Int32 bbStart = ftab[ss << 8] & CLEARMASK;- Int32 bbSize = (ftab[(ss+1) << 8] & CLEARMASK) - bbStart;- Int32 shifts = 0;-- while ((bbSize >> shifts) > 65534) shifts++;-- for (j = bbSize-1; j >= 0; j--) {- Int32 a2update = ptr[bbStart + j];- UInt16 qVal = (UInt16)(j >> shifts);- quadrant[a2update] = qVal;- if (a2update < BZ_N_OVERSHOOT)- quadrant[a2update + nblock] = qVal;- }- AssertH ( ((bbSize-1) >> shifts) <= 65535, 1002 );- }-- }-- if (verb >= 4)- VPrintf3 ( " %d pointers, %d sorted, %d scanned\n",- nblock, numQSorted, nblock - numQSorted );-}--#undef BIGFREQ-#undef SETMASK-#undef CLEARMASK---/*---------------------------------------------*/-/* Pre:- nblock > 0- arr2 exists for [0 .. nblock-1 +N_OVERSHOOT]- ((UChar*)arr2) [0 .. nblock-1] holds block- arr1 exists for [0 .. nblock-1]-- Post:- ((UChar*)arr2) [0 .. nblock-1] holds block- All other areas of block destroyed- ftab [ 0 .. 65536 ] destroyed- arr1 [0 .. nblock-1] holds sorted order-*/-void BZ2_blockSort ( EState* s )-{- UInt32* ptr = s->ptr; - UChar* block = s->block;- UInt32* ftab = s->ftab;- Int32 nblock = s->nblock;- Int32 verb = s->verbosity;- Int32 wfact = s->workFactor;- UInt16* quadrant;- Int32 budget;- Int32 budgetInit;- Int32 i;-- if (nblock < 10000) {- fallbackSort ( s->arr1, s->arr2, ftab, nblock, verb );- } else {- /* Calculate the location for quadrant, remembering to get- the alignment right. Assumes that &(block[0]) is at least- 2-byte aligned -- this should be ok since block is really- the first section of arr2.- */- i = nblock+BZ_N_OVERSHOOT;- if (i & 1) i++;- quadrant = (UInt16*)(&(block[i]));-- /* (wfact-1) / 3 puts the default-factor-30- transition point at very roughly the same place as - with v0.1 and v0.9.0. - Not that it particularly matters any more, since the- resulting compressed stream is now the same regardless- of whether or not we use the main sort or fallback sort.- */- if (wfact < 1 ) wfact = 1;- if (wfact > 100) wfact = 100;- budgetInit = nblock * ((wfact-1) / 3);- budget = budgetInit;-- mainSort ( ptr, block, quadrant, ftab, nblock, verb, &budget );- if (verb >= 3) - VPrintf3 ( " %d work, %d block, ratio %5.2f\n",- budgetInit - budget,- nblock, - (float)(budgetInit - budget) /- (float)(nblock==0 ? 1 : nblock) ); - if (budget < 0) {- if (verb >= 2) - VPrintf0 ( " too repetitive; using fallback"- " sorting algorithm\n" );- fallbackSort ( s->arr1, s->arr2, ftab, nblock, verb );- }- }-- s->origPtr = -1;- for (i = 0; i < s->nblock; i++)- if (ptr[i] == 0)- { s->origPtr = i; break; };-- AssertH( s->origPtr != -1, 1003 );-}---/*-------------------------------------------------------------*/-/*--- end blocksort.c ---*/-/*-------------------------------------------------------------*/
− cbits/bzlib.c
@@ -1,1572 +0,0 @@--/*-------------------------------------------------------------*/-/*--- Library top-level functions. ---*/-/*--- bzlib.c ---*/-/*-------------------------------------------------------------*/--/* ------------------------------------------------------------------- This file is part of bzip2/libbzip2, a program and library for- lossless, block-sorting data compression.-- bzip2/libbzip2 version 1.0.6 of 6 September 2010- Copyright (C) 1996-2010 Julian Seward <jseward@bzip.org>-- Please read the WARNING, DISCLAIMER and PATENTS sections in the - README file.-- This program is released under the terms of the license contained- in the file LICENSE.- ------------------------------------------------------------------ */--/* CHANGES- 0.9.0 -- original version.- 0.9.0a/b -- no changes in this file.- 0.9.0c -- made zero-length BZ_FLUSH work correctly in bzCompress().- fixed bzWrite/bzRead to ignore zero-length requests.- fixed bzread to correctly handle read requests after EOF.- wrong parameter order in call to bzDecompressInit in- bzBuffToBuffDecompress. Fixed.-*/--#include "bzlib_private.h"---/*---------------------------------------------------*/-/*--- Compression stuff ---*/-/*---------------------------------------------------*/---/*---------------------------------------------------*/-#ifndef BZ_NO_STDIO-void BZ2_bz__AssertH__fail ( int errcode )-{- fprintf(stderr, - "\n\nbzip2/libbzip2: internal error number %d.\n"- "This is a bug in bzip2/libbzip2, %s.\n"- "Please report it to me at: jseward@bzip.org. If this happened\n"- "when you were using some program which uses libbzip2 as a\n"- "component, you should also report this bug to the author(s)\n"- "of that program. Please make an effort to report this bug;\n"- "timely and accurate bug reports eventually lead to higher\n"- "quality software. Thanks. Julian Seward, 10 December 2007.\n\n",- errcode,- BZ2_bzlibVersion()- );-- if (errcode == 1007) {- fprintf(stderr,- "\n*** A special note about internal error number 1007 ***\n"- "\n"- "Experience suggests that a common cause of i.e. 1007\n"- "is unreliable memory or other hardware. The 1007 assertion\n"- "just happens to cross-check the results of huge numbers of\n"- "memory reads/writes, and so acts (unintendedly) as a stress\n"- "test of your memory system.\n"- "\n"- "I suggest the following: try compressing the file again,\n"- "possibly monitoring progress in detail with the -vv flag.\n"- "\n"- "* If the error cannot be reproduced, and/or happens at different\n"- " points in compression, you may have a flaky memory system.\n"- " Try a memory-test program. I have used Memtest86\n"- " (www.memtest86.com). At the time of writing it is free (GPLd).\n"- " Memtest86 tests memory much more thorougly than your BIOSs\n"- " power-on test, and may find failures that the BIOS doesn't.\n"- "\n"- "* If the error can be repeatably reproduced, this is a bug in\n"- " bzip2, and I would very much like to hear about it. Please\n"- " let me know, and, ideally, save a copy of the file causing the\n"- " problem -- without which I will be unable to investigate it.\n"- "\n"- );- }-- exit(3);-}-#endif---/*---------------------------------------------------*/-static-int bz_config_ok ( void )-{- if (sizeof(int) != 4) return 0;- if (sizeof(short) != 2) return 0;- if (sizeof(char) != 1) return 0;- return 1;-}---/*---------------------------------------------------*/-static-void* default_bzalloc ( void* opaque, Int32 items, Int32 size )-{- void* v = malloc ( items * size );- return v;-}--static-void default_bzfree ( void* opaque, void* addr )-{- if (addr != NULL) free ( addr );-}---/*---------------------------------------------------*/-static-void prepare_new_block ( EState* s )-{- Int32 i;- s->nblock = 0;- s->numZ = 0;- s->state_out_pos = 0;- BZ_INITIALISE_CRC ( s->blockCRC );- for (i = 0; i < 256; i++) s->inUse[i] = False;- s->blockNo++;-}---/*---------------------------------------------------*/-static-void init_RL ( EState* s )-{- s->state_in_ch = 256;- s->state_in_len = 0;-}---static-Bool isempty_RL ( EState* s )-{- if (s->state_in_ch < 256 && s->state_in_len > 0)- return False; else- return True;-}---/*---------------------------------------------------*/-int BZ_API(BZ2_bzCompressInit) - ( bz_stream* strm, - int blockSize100k,- int verbosity,- int workFactor )-{- Int32 n;- EState* s;-- if (!bz_config_ok()) return BZ_CONFIG_ERROR;-- if (strm == NULL || - blockSize100k < 1 || blockSize100k > 9 ||- workFactor < 0 || workFactor > 250)- return BZ_PARAM_ERROR;-- if (workFactor == 0) workFactor = 30;- if (strm->bzalloc == NULL) strm->bzalloc = default_bzalloc;- if (strm->bzfree == NULL) strm->bzfree = default_bzfree;-- s = BZALLOC( sizeof(EState) );- if (s == NULL) return BZ_MEM_ERROR;- s->strm = strm;-- s->arr1 = NULL;- s->arr2 = NULL;- s->ftab = NULL;-- n = 100000 * blockSize100k;- s->arr1 = BZALLOC( n * sizeof(UInt32) );- s->arr2 = BZALLOC( (n+BZ_N_OVERSHOOT) * sizeof(UInt32) );- s->ftab = BZALLOC( 65537 * sizeof(UInt32) );-- if (s->arr1 == NULL || s->arr2 == NULL || s->ftab == NULL) {- if (s->arr1 != NULL) BZFREE(s->arr1);- if (s->arr2 != NULL) BZFREE(s->arr2);- if (s->ftab != NULL) BZFREE(s->ftab);- if (s != NULL) BZFREE(s);- return BZ_MEM_ERROR;- }-- s->blockNo = 0;- s->state = BZ_S_INPUT;- s->mode = BZ_M_RUNNING;- s->combinedCRC = 0;- s->blockSize100k = blockSize100k;- s->nblockMAX = 100000 * blockSize100k - 19;- s->verbosity = verbosity;- s->workFactor = workFactor;-- s->block = (UChar*)s->arr2;- s->mtfv = (UInt16*)s->arr1;- s->zbits = NULL;- s->ptr = (UInt32*)s->arr1;-- strm->state = s;- strm->total_in_lo32 = 0;- strm->total_in_hi32 = 0;- strm->total_out_lo32 = 0;- strm->total_out_hi32 = 0;- init_RL ( s );- prepare_new_block ( s );- return BZ_OK;-}---/*---------------------------------------------------*/-static-void add_pair_to_block ( EState* s )-{- Int32 i;- UChar ch = (UChar)(s->state_in_ch);- for (i = 0; i < s->state_in_len; i++) {- BZ_UPDATE_CRC( s->blockCRC, ch );- }- s->inUse[s->state_in_ch] = True;- switch (s->state_in_len) {- case 1:- s->block[s->nblock] = (UChar)ch; s->nblock++;- break;- case 2:- s->block[s->nblock] = (UChar)ch; s->nblock++;- s->block[s->nblock] = (UChar)ch; s->nblock++;- break;- case 3:- s->block[s->nblock] = (UChar)ch; s->nblock++;- s->block[s->nblock] = (UChar)ch; s->nblock++;- s->block[s->nblock] = (UChar)ch; s->nblock++;- break;- default:- s->inUse[s->state_in_len-4] = True;- s->block[s->nblock] = (UChar)ch; s->nblock++;- s->block[s->nblock] = (UChar)ch; s->nblock++;- s->block[s->nblock] = (UChar)ch; s->nblock++;- s->block[s->nblock] = (UChar)ch; s->nblock++;- s->block[s->nblock] = ((UChar)(s->state_in_len-4));- s->nblock++;- break;- }-}---/*---------------------------------------------------*/-static-void flush_RL ( EState* s )-{- if (s->state_in_ch < 256) add_pair_to_block ( s );- init_RL ( s );-}---/*---------------------------------------------------*/-#define ADD_CHAR_TO_BLOCK(zs,zchh0) \-{ \- UInt32 zchh = (UInt32)(zchh0); \- /*-- fast track the common case --*/ \- if (zchh != zs->state_in_ch && \- zs->state_in_len == 1) { \- UChar ch = (UChar)(zs->state_in_ch); \- BZ_UPDATE_CRC( zs->blockCRC, ch ); \- zs->inUse[zs->state_in_ch] = True; \- zs->block[zs->nblock] = (UChar)ch; \- zs->nblock++; \- zs->state_in_ch = zchh; \- } \- else \- /*-- general, uncommon cases --*/ \- if (zchh != zs->state_in_ch || \- zs->state_in_len == 255) { \- if (zs->state_in_ch < 256) \- add_pair_to_block ( zs ); \- zs->state_in_ch = zchh; \- zs->state_in_len = 1; \- } else { \- zs->state_in_len++; \- } \-}---/*---------------------------------------------------*/-static-Bool copy_input_until_stop ( EState* s )-{- Bool progress_in = False;-- if (s->mode == BZ_M_RUNNING) {-- /*-- fast track the common case --*/- while (True) {- /*-- block full? --*/- if (s->nblock >= s->nblockMAX) break;- /*-- no input? --*/- if (s->strm->avail_in == 0) break;- progress_in = True;- ADD_CHAR_TO_BLOCK ( s, (UInt32)(*((UChar*)(s->strm->next_in))) ); - s->strm->next_in++;- s->strm->avail_in--;- s->strm->total_in_lo32++;- if (s->strm->total_in_lo32 == 0) s->strm->total_in_hi32++;- }-- } else {-- /*-- general, uncommon case --*/- while (True) {- /*-- block full? --*/- if (s->nblock >= s->nblockMAX) break;- /*-- no input? --*/- if (s->strm->avail_in == 0) break;- /*-- flush/finish end? --*/- if (s->avail_in_expect == 0) break;- progress_in = True;- ADD_CHAR_TO_BLOCK ( s, (UInt32)(*((UChar*)(s->strm->next_in))) ); - s->strm->next_in++;- s->strm->avail_in--;- s->strm->total_in_lo32++;- if (s->strm->total_in_lo32 == 0) s->strm->total_in_hi32++;- s->avail_in_expect--;- }- }- return progress_in;-}---/*---------------------------------------------------*/-static-Bool copy_output_until_stop ( EState* s )-{- Bool progress_out = False;-- while (True) {-- /*-- no output space? --*/- if (s->strm->avail_out == 0) break;-- /*-- block done? --*/- if (s->state_out_pos >= s->numZ) break;-- progress_out = True;- *(s->strm->next_out) = s->zbits[s->state_out_pos];- s->state_out_pos++;- s->strm->avail_out--;- s->strm->next_out++;- s->strm->total_out_lo32++;- if (s->strm->total_out_lo32 == 0) s->strm->total_out_hi32++;- }-- return progress_out;-}---/*---------------------------------------------------*/-static-Bool handle_compress ( bz_stream* strm )-{- Bool progress_in = False;- Bool progress_out = False;- EState* s = strm->state;- - while (True) {-- if (s->state == BZ_S_OUTPUT) {- progress_out |= copy_output_until_stop ( s );- if (s->state_out_pos < s->numZ) break;- if (s->mode == BZ_M_FINISHING && - s->avail_in_expect == 0 &&- isempty_RL(s)) break;- prepare_new_block ( s );- s->state = BZ_S_INPUT;- if (s->mode == BZ_M_FLUSHING && - s->avail_in_expect == 0 &&- isempty_RL(s)) break;- }-- if (s->state == BZ_S_INPUT) {- progress_in |= copy_input_until_stop ( s );- if (s->mode != BZ_M_RUNNING && s->avail_in_expect == 0) {- flush_RL ( s );- BZ2_compressBlock ( s, (Bool)(s->mode == BZ_M_FINISHING) );- s->state = BZ_S_OUTPUT;- }- else- if (s->nblock >= s->nblockMAX) {- BZ2_compressBlock ( s, False );- s->state = BZ_S_OUTPUT;- }- else- if (s->strm->avail_in == 0) {- break;- }- }-- }-- return progress_in || progress_out;-}---/*---------------------------------------------------*/-int BZ_API(BZ2_bzCompress) ( bz_stream *strm, int action )-{- Bool progress;- EState* s;- if (strm == NULL) return BZ_PARAM_ERROR;- s = strm->state;- if (s == NULL) return BZ_PARAM_ERROR;- if (s->strm != strm) return BZ_PARAM_ERROR;-- preswitch:- switch (s->mode) {-- case BZ_M_IDLE:- return BZ_SEQUENCE_ERROR;-- case BZ_M_RUNNING:- if (action == BZ_RUN) {- progress = handle_compress ( strm );- return progress ? BZ_RUN_OK : BZ_PARAM_ERROR;- } - else- if (action == BZ_FLUSH) {- s->avail_in_expect = strm->avail_in;- s->mode = BZ_M_FLUSHING;- goto preswitch;- }- else- if (action == BZ_FINISH) {- s->avail_in_expect = strm->avail_in;- s->mode = BZ_M_FINISHING;- goto preswitch;- }- else - return BZ_PARAM_ERROR;-- case BZ_M_FLUSHING:- if (action != BZ_FLUSH) return BZ_SEQUENCE_ERROR;- if (s->avail_in_expect != s->strm->avail_in) - return BZ_SEQUENCE_ERROR;- progress = handle_compress ( strm );- if (s->avail_in_expect > 0 || !isempty_RL(s) ||- s->state_out_pos < s->numZ) return BZ_FLUSH_OK;- s->mode = BZ_M_RUNNING;- return BZ_RUN_OK;-- case BZ_M_FINISHING:- if (action != BZ_FINISH) return BZ_SEQUENCE_ERROR;- if (s->avail_in_expect != s->strm->avail_in) - return BZ_SEQUENCE_ERROR;- progress = handle_compress ( strm );- if (!progress) return BZ_SEQUENCE_ERROR;- if (s->avail_in_expect > 0 || !isempty_RL(s) ||- s->state_out_pos < s->numZ) return BZ_FINISH_OK;- s->mode = BZ_M_IDLE;- return BZ_STREAM_END;- }- return BZ_OK; /*--not reached--*/-}---/*---------------------------------------------------*/-int BZ_API(BZ2_bzCompressEnd) ( bz_stream *strm )-{- EState* s;- if (strm == NULL) return BZ_PARAM_ERROR;- s = strm->state;- if (s == NULL) return BZ_PARAM_ERROR;- if (s->strm != strm) return BZ_PARAM_ERROR;-- if (s->arr1 != NULL) BZFREE(s->arr1);- if (s->arr2 != NULL) BZFREE(s->arr2);- if (s->ftab != NULL) BZFREE(s->ftab);- BZFREE(strm->state);-- strm->state = NULL; -- return BZ_OK;-}---/*---------------------------------------------------*/-/*--- Decompression stuff ---*/-/*---------------------------------------------------*/--/*---------------------------------------------------*/-int BZ_API(BZ2_bzDecompressInit) - ( bz_stream* strm, - int verbosity,- int small )-{- DState* s;-- if (!bz_config_ok()) return BZ_CONFIG_ERROR;-- if (strm == NULL) return BZ_PARAM_ERROR;- if (small != 0 && small != 1) return BZ_PARAM_ERROR;- if (verbosity < 0 || verbosity > 4) return BZ_PARAM_ERROR;-- if (strm->bzalloc == NULL) strm->bzalloc = default_bzalloc;- if (strm->bzfree == NULL) strm->bzfree = default_bzfree;-- s = BZALLOC( sizeof(DState) );- if (s == NULL) return BZ_MEM_ERROR;- s->strm = strm;- strm->state = s;- s->state = BZ_X_MAGIC_1;- s->bsLive = 0;- s->bsBuff = 0;- s->calculatedCombinedCRC = 0;- strm->total_in_lo32 = 0;- strm->total_in_hi32 = 0;- strm->total_out_lo32 = 0;- strm->total_out_hi32 = 0;- s->smallDecompress = (Bool)small;- s->ll4 = NULL;- s->ll16 = NULL;- s->tt = NULL;- s->currBlockNo = 0;- s->verbosity = verbosity;-- return BZ_OK;-}---/*---------------------------------------------------*/-/* Return True iff data corruption is discovered.- Returns False if there is no problem.-*/-static-Bool unRLE_obuf_to_output_FAST ( DState* s )-{- UChar k1;-- if (s->blockRandomised) {-- while (True) {- /* try to finish existing run */- while (True) {- if (s->strm->avail_out == 0) return False;- if (s->state_out_len == 0) break;- *( (UChar*)(s->strm->next_out) ) = s->state_out_ch;- BZ_UPDATE_CRC ( s->calculatedBlockCRC, s->state_out_ch );- s->state_out_len--;- s->strm->next_out++;- s->strm->avail_out--;- s->strm->total_out_lo32++;- if (s->strm->total_out_lo32 == 0) s->strm->total_out_hi32++;- }-- /* can a new run be started? */- if (s->nblock_used == s->save_nblock+1) return False;- - /* Only caused by corrupt data stream? */- if (s->nblock_used > s->save_nblock+1)- return True;- - s->state_out_len = 1;- s->state_out_ch = s->k0;- BZ_GET_FAST(k1); BZ_RAND_UPD_MASK; - k1 ^= BZ_RAND_MASK; s->nblock_used++;- if (s->nblock_used == s->save_nblock+1) continue;- if (k1 != s->k0) { s->k0 = k1; continue; };- - s->state_out_len = 2;- BZ_GET_FAST(k1); BZ_RAND_UPD_MASK; - k1 ^= BZ_RAND_MASK; s->nblock_used++;- if (s->nblock_used == s->save_nblock+1) continue;- if (k1 != s->k0) { s->k0 = k1; continue; };- - s->state_out_len = 3;- BZ_GET_FAST(k1); BZ_RAND_UPD_MASK; - k1 ^= BZ_RAND_MASK; s->nblock_used++;- if (s->nblock_used == s->save_nblock+1) continue;- if (k1 != s->k0) { s->k0 = k1; continue; };- - BZ_GET_FAST(k1); BZ_RAND_UPD_MASK; - k1 ^= BZ_RAND_MASK; s->nblock_used++;- s->state_out_len = ((Int32)k1) + 4;- BZ_GET_FAST(s->k0); BZ_RAND_UPD_MASK; - s->k0 ^= BZ_RAND_MASK; s->nblock_used++;- }-- } else {-- /* restore */- UInt32 c_calculatedBlockCRC = s->calculatedBlockCRC;- UChar c_state_out_ch = s->state_out_ch;- Int32 c_state_out_len = s->state_out_len;- Int32 c_nblock_used = s->nblock_used;- Int32 c_k0 = s->k0;- UInt32* c_tt = s->tt;- UInt32 c_tPos = s->tPos;- char* cs_next_out = s->strm->next_out;- unsigned int cs_avail_out = s->strm->avail_out;- Int32 ro_blockSize100k = s->blockSize100k;- /* end restore */-- UInt32 avail_out_INIT = cs_avail_out;- Int32 s_save_nblockPP = s->save_nblock+1;- unsigned int total_out_lo32_old;-- while (True) {-- /* try to finish existing run */- if (c_state_out_len > 0) {- while (True) {- if (cs_avail_out == 0) goto return_notr;- if (c_state_out_len == 1) break;- *( (UChar*)(cs_next_out) ) = c_state_out_ch;- BZ_UPDATE_CRC ( c_calculatedBlockCRC, c_state_out_ch );- c_state_out_len--;- cs_next_out++;- cs_avail_out--;- }- s_state_out_len_eq_one:- {- if (cs_avail_out == 0) { - c_state_out_len = 1; goto return_notr;- };- *( (UChar*)(cs_next_out) ) = c_state_out_ch;- BZ_UPDATE_CRC ( c_calculatedBlockCRC, c_state_out_ch );- cs_next_out++;- cs_avail_out--;- }- } - /* Only caused by corrupt data stream? */- if (c_nblock_used > s_save_nblockPP)- return True;-- /* can a new run be started? */- if (c_nblock_used == s_save_nblockPP) {- c_state_out_len = 0; goto return_notr;- }; - c_state_out_ch = c_k0;- BZ_GET_FAST_C(k1); c_nblock_used++;- if (k1 != c_k0) { - c_k0 = k1; goto s_state_out_len_eq_one; - };- if (c_nblock_used == s_save_nblockPP) - goto s_state_out_len_eq_one;- - c_state_out_len = 2;- BZ_GET_FAST_C(k1); c_nblock_used++;- if (c_nblock_used == s_save_nblockPP) continue;- if (k1 != c_k0) { c_k0 = k1; continue; };- - c_state_out_len = 3;- BZ_GET_FAST_C(k1); c_nblock_used++;- if (c_nblock_used == s_save_nblockPP) continue;- if (k1 != c_k0) { c_k0 = k1; continue; };- - BZ_GET_FAST_C(k1); c_nblock_used++;- c_state_out_len = ((Int32)k1) + 4;- BZ_GET_FAST_C(c_k0); c_nblock_used++;- }-- return_notr:- total_out_lo32_old = s->strm->total_out_lo32;- s->strm->total_out_lo32 += (avail_out_INIT - cs_avail_out);- if (s->strm->total_out_lo32 < total_out_lo32_old)- s->strm->total_out_hi32++;-- /* save */- s->calculatedBlockCRC = c_calculatedBlockCRC;- s->state_out_ch = c_state_out_ch;- s->state_out_len = c_state_out_len;- s->nblock_used = c_nblock_used;- s->k0 = c_k0;- s->tt = c_tt;- s->tPos = c_tPos;- s->strm->next_out = cs_next_out;- s->strm->avail_out = cs_avail_out;- /* end save */- }- return False;-}----/*---------------------------------------------------*/-__inline__ Int32 BZ2_indexIntoF ( Int32 indx, Int32 *cftab )-{- Int32 nb, na, mid;- nb = 0;- na = 256;- do {- mid = (nb + na) >> 1;- if (indx >= cftab[mid]) nb = mid; else na = mid;- }- while (na - nb != 1);- return nb;-}---/*---------------------------------------------------*/-/* Return True iff data corruption is discovered.- Returns False if there is no problem.-*/-static-Bool unRLE_obuf_to_output_SMALL ( DState* s )-{- UChar k1;-- if (s->blockRandomised) {-- while (True) {- /* try to finish existing run */- while (True) {- if (s->strm->avail_out == 0) return False;- if (s->state_out_len == 0) break;- *( (UChar*)(s->strm->next_out) ) = s->state_out_ch;- BZ_UPDATE_CRC ( s->calculatedBlockCRC, s->state_out_ch );- s->state_out_len--;- s->strm->next_out++;- s->strm->avail_out--;- s->strm->total_out_lo32++;- if (s->strm->total_out_lo32 == 0) s->strm->total_out_hi32++;- }- - /* can a new run be started? */- if (s->nblock_used == s->save_nblock+1) return False;-- /* Only caused by corrupt data stream? */- if (s->nblock_used > s->save_nblock+1)- return True;- - s->state_out_len = 1;- s->state_out_ch = s->k0;- BZ_GET_SMALL(k1); BZ_RAND_UPD_MASK; - k1 ^= BZ_RAND_MASK; s->nblock_used++;- if (s->nblock_used == s->save_nblock+1) continue;- if (k1 != s->k0) { s->k0 = k1; continue; };- - s->state_out_len = 2;- BZ_GET_SMALL(k1); BZ_RAND_UPD_MASK; - k1 ^= BZ_RAND_MASK; s->nblock_used++;- if (s->nblock_used == s->save_nblock+1) continue;- if (k1 != s->k0) { s->k0 = k1; continue; };- - s->state_out_len = 3;- BZ_GET_SMALL(k1); BZ_RAND_UPD_MASK; - k1 ^= BZ_RAND_MASK; s->nblock_used++;- if (s->nblock_used == s->save_nblock+1) continue;- if (k1 != s->k0) { s->k0 = k1; continue; };- - BZ_GET_SMALL(k1); BZ_RAND_UPD_MASK; - k1 ^= BZ_RAND_MASK; s->nblock_used++;- s->state_out_len = ((Int32)k1) + 4;- BZ_GET_SMALL(s->k0); BZ_RAND_UPD_MASK; - s->k0 ^= BZ_RAND_MASK; s->nblock_used++;- }-- } else {-- while (True) {- /* try to finish existing run */- while (True) {- if (s->strm->avail_out == 0) return False;- if (s->state_out_len == 0) break;- *( (UChar*)(s->strm->next_out) ) = s->state_out_ch;- BZ_UPDATE_CRC ( s->calculatedBlockCRC, s->state_out_ch );- s->state_out_len--;- s->strm->next_out++;- s->strm->avail_out--;- s->strm->total_out_lo32++;- if (s->strm->total_out_lo32 == 0) s->strm->total_out_hi32++;- }- - /* can a new run be started? */- if (s->nblock_used == s->save_nblock+1) return False;-- /* Only caused by corrupt data stream? */- if (s->nblock_used > s->save_nblock+1)- return True;- - s->state_out_len = 1;- s->state_out_ch = s->k0;- BZ_GET_SMALL(k1); s->nblock_used++;- if (s->nblock_used == s->save_nblock+1) continue;- if (k1 != s->k0) { s->k0 = k1; continue; };- - s->state_out_len = 2;- BZ_GET_SMALL(k1); s->nblock_used++;- if (s->nblock_used == s->save_nblock+1) continue;- if (k1 != s->k0) { s->k0 = k1; continue; };- - s->state_out_len = 3;- BZ_GET_SMALL(k1); s->nblock_used++;- if (s->nblock_used == s->save_nblock+1) continue;- if (k1 != s->k0) { s->k0 = k1; continue; };- - BZ_GET_SMALL(k1); s->nblock_used++;- s->state_out_len = ((Int32)k1) + 4;- BZ_GET_SMALL(s->k0); s->nblock_used++;- }-- }-}---/*---------------------------------------------------*/-int BZ_API(BZ2_bzDecompress) ( bz_stream *strm )-{- Bool corrupt;- DState* s;- if (strm == NULL) return BZ_PARAM_ERROR;- s = strm->state;- if (s == NULL) return BZ_PARAM_ERROR;- if (s->strm != strm) return BZ_PARAM_ERROR;-- while (True) {- if (s->state == BZ_X_IDLE) return BZ_SEQUENCE_ERROR;- if (s->state == BZ_X_OUTPUT) {- if (s->smallDecompress)- corrupt = unRLE_obuf_to_output_SMALL ( s ); else- corrupt = unRLE_obuf_to_output_FAST ( s );- if (corrupt) return BZ_DATA_ERROR;- if (s->nblock_used == s->save_nblock+1 && s->state_out_len == 0) {- BZ_FINALISE_CRC ( s->calculatedBlockCRC );- if (s->verbosity >= 3) - VPrintf2 ( " {0x%08x, 0x%08x}", s->storedBlockCRC, - s->calculatedBlockCRC );- if (s->verbosity >= 2) VPrintf0 ( "]" );- if (s->calculatedBlockCRC != s->storedBlockCRC)- return BZ_DATA_ERROR;- s->calculatedCombinedCRC - = (s->calculatedCombinedCRC << 1) | - (s->calculatedCombinedCRC >> 31);- s->calculatedCombinedCRC ^= s->calculatedBlockCRC;- s->state = BZ_X_BLKHDR_1;- } else {- return BZ_OK;- }- }- if (s->state >= BZ_X_MAGIC_1) {- Int32 r = BZ2_decompress ( s );- if (r == BZ_STREAM_END) {- if (s->verbosity >= 3)- VPrintf2 ( "\n combined CRCs: stored = 0x%08x, computed = 0x%08x", - s->storedCombinedCRC, s->calculatedCombinedCRC );- if (s->calculatedCombinedCRC != s->storedCombinedCRC)- return BZ_DATA_ERROR;- return r;- }- if (s->state != BZ_X_OUTPUT) return r;- }- }-- AssertH ( 0, 6001 );-- return 0; /*NOTREACHED*/-}---/*---------------------------------------------------*/-int BZ_API(BZ2_bzDecompressEnd) ( bz_stream *strm )-{- DState* s;- if (strm == NULL) return BZ_PARAM_ERROR;- s = strm->state;- if (s == NULL) return BZ_PARAM_ERROR;- if (s->strm != strm) return BZ_PARAM_ERROR;-- if (s->tt != NULL) BZFREE(s->tt);- if (s->ll16 != NULL) BZFREE(s->ll16);- if (s->ll4 != NULL) BZFREE(s->ll4);-- BZFREE(strm->state);- strm->state = NULL;-- return BZ_OK;-}---#ifndef BZ_NO_STDIO-/*---------------------------------------------------*/-/*--- File I/O stuff ---*/-/*---------------------------------------------------*/--#define BZ_SETERR(eee) \-{ \- if (bzerror != NULL) *bzerror = eee; \- if (bzf != NULL) bzf->lastErr = eee; \-}--typedef - struct {- FILE* handle;- Char buf[BZ_MAX_UNUSED];- Int32 bufN;- Bool writing;- bz_stream strm;- Int32 lastErr;- Bool initialisedOk;- }- bzFile;---/*---------------------------------------------*/-static Bool myfeof ( FILE* f )-{- Int32 c = fgetc ( f );- if (c == EOF) return True;- ungetc ( c, f );- return False;-}---/*---------------------------------------------------*/-BZFILE* BZ_API(BZ2_bzWriteOpen) - ( int* bzerror, - FILE* f, - int blockSize100k, - int verbosity,- int workFactor )-{- Int32 ret;- bzFile* bzf = NULL;-- BZ_SETERR(BZ_OK);-- if (f == NULL ||- (blockSize100k < 1 || blockSize100k > 9) ||- (workFactor < 0 || workFactor > 250) ||- (verbosity < 0 || verbosity > 4))- { BZ_SETERR(BZ_PARAM_ERROR); return NULL; };-- if (ferror(f))- { BZ_SETERR(BZ_IO_ERROR); return NULL; };-- bzf = malloc ( sizeof(bzFile) );- if (bzf == NULL)- { BZ_SETERR(BZ_MEM_ERROR); return NULL; };-- BZ_SETERR(BZ_OK);- bzf->initialisedOk = False;- bzf->bufN = 0;- bzf->handle = f;- bzf->writing = True;- bzf->strm.bzalloc = NULL;- bzf->strm.bzfree = NULL;- bzf->strm.opaque = NULL;-- if (workFactor == 0) workFactor = 30;- ret = BZ2_bzCompressInit ( &(bzf->strm), blockSize100k, - verbosity, workFactor );- if (ret != BZ_OK)- { BZ_SETERR(ret); free(bzf); return NULL; };-- bzf->strm.avail_in = 0;- bzf->initialisedOk = True;- return bzf; -}----/*---------------------------------------------------*/-void BZ_API(BZ2_bzWrite)- ( int* bzerror, - BZFILE* b, - void* buf, - int len )-{- Int32 n, n2, ret;- bzFile* bzf = (bzFile*)b;-- BZ_SETERR(BZ_OK);- if (bzf == NULL || buf == NULL || len < 0)- { BZ_SETERR(BZ_PARAM_ERROR); return; };- if (!(bzf->writing))- { BZ_SETERR(BZ_SEQUENCE_ERROR); return; };- if (ferror(bzf->handle))- { BZ_SETERR(BZ_IO_ERROR); return; };-- if (len == 0)- { BZ_SETERR(BZ_OK); return; };-- bzf->strm.avail_in = len;- bzf->strm.next_in = buf;-- while (True) {- bzf->strm.avail_out = BZ_MAX_UNUSED;- bzf->strm.next_out = bzf->buf;- ret = BZ2_bzCompress ( &(bzf->strm), BZ_RUN );- if (ret != BZ_RUN_OK)- { BZ_SETERR(ret); return; };-- if (bzf->strm.avail_out < BZ_MAX_UNUSED) {- n = BZ_MAX_UNUSED - bzf->strm.avail_out;- n2 = fwrite ( (void*)(bzf->buf), sizeof(UChar), - n, bzf->handle );- if (n != n2 || ferror(bzf->handle))- { BZ_SETERR(BZ_IO_ERROR); return; };- }-- if (bzf->strm.avail_in == 0)- { BZ_SETERR(BZ_OK); return; };- }-}---/*---------------------------------------------------*/-void BZ_API(BZ2_bzWriteClose)- ( int* bzerror, - BZFILE* b, - int abandon,- unsigned int* nbytes_in,- unsigned int* nbytes_out )-{- BZ2_bzWriteClose64 ( bzerror, b, abandon, - nbytes_in, NULL, nbytes_out, NULL );-}---void BZ_API(BZ2_bzWriteClose64)- ( int* bzerror, - BZFILE* b, - int abandon,- unsigned int* nbytes_in_lo32,- unsigned int* nbytes_in_hi32,- unsigned int* nbytes_out_lo32,- unsigned int* nbytes_out_hi32 )-{- Int32 n, n2, ret;- bzFile* bzf = (bzFile*)b;-- if (bzf == NULL)- { BZ_SETERR(BZ_OK); return; };- if (!(bzf->writing))- { BZ_SETERR(BZ_SEQUENCE_ERROR); return; };- if (ferror(bzf->handle))- { BZ_SETERR(BZ_IO_ERROR); return; };-- if (nbytes_in_lo32 != NULL) *nbytes_in_lo32 = 0;- if (nbytes_in_hi32 != NULL) *nbytes_in_hi32 = 0;- if (nbytes_out_lo32 != NULL) *nbytes_out_lo32 = 0;- if (nbytes_out_hi32 != NULL) *nbytes_out_hi32 = 0;-- if ((!abandon) && bzf->lastErr == BZ_OK) {- while (True) {- bzf->strm.avail_out = BZ_MAX_UNUSED;- bzf->strm.next_out = bzf->buf;- ret = BZ2_bzCompress ( &(bzf->strm), BZ_FINISH );- if (ret != BZ_FINISH_OK && ret != BZ_STREAM_END)- { BZ_SETERR(ret); return; };-- if (bzf->strm.avail_out < BZ_MAX_UNUSED) {- n = BZ_MAX_UNUSED - bzf->strm.avail_out;- n2 = fwrite ( (void*)(bzf->buf), sizeof(UChar), - n, bzf->handle );- if (n != n2 || ferror(bzf->handle))- { BZ_SETERR(BZ_IO_ERROR); return; };- }-- if (ret == BZ_STREAM_END) break;- }- }-- if ( !abandon && !ferror ( bzf->handle ) ) {- fflush ( bzf->handle );- if (ferror(bzf->handle))- { BZ_SETERR(BZ_IO_ERROR); return; };- }-- if (nbytes_in_lo32 != NULL)- *nbytes_in_lo32 = bzf->strm.total_in_lo32;- if (nbytes_in_hi32 != NULL)- *nbytes_in_hi32 = bzf->strm.total_in_hi32;- if (nbytes_out_lo32 != NULL)- *nbytes_out_lo32 = bzf->strm.total_out_lo32;- if (nbytes_out_hi32 != NULL)- *nbytes_out_hi32 = bzf->strm.total_out_hi32;-- BZ_SETERR(BZ_OK);- BZ2_bzCompressEnd ( &(bzf->strm) );- free ( bzf );-}---/*---------------------------------------------------*/-BZFILE* BZ_API(BZ2_bzReadOpen) - ( int* bzerror, - FILE* f, - int verbosity,- int small,- void* unused,- int nUnused )-{- bzFile* bzf = NULL;- int ret;-- BZ_SETERR(BZ_OK);-- if (f == NULL || - (small != 0 && small != 1) ||- (verbosity < 0 || verbosity > 4) ||- (unused == NULL && nUnused != 0) ||- (unused != NULL && (nUnused < 0 || nUnused > BZ_MAX_UNUSED)))- { BZ_SETERR(BZ_PARAM_ERROR); return NULL; };-- if (ferror(f))- { BZ_SETERR(BZ_IO_ERROR); return NULL; };-- bzf = malloc ( sizeof(bzFile) );- if (bzf == NULL) - { BZ_SETERR(BZ_MEM_ERROR); return NULL; };-- BZ_SETERR(BZ_OK);-- bzf->initialisedOk = False;- bzf->handle = f;- bzf->bufN = 0;- bzf->writing = False;- bzf->strm.bzalloc = NULL;- bzf->strm.bzfree = NULL;- bzf->strm.opaque = NULL;- - while (nUnused > 0) {- bzf->buf[bzf->bufN] = *((UChar*)(unused)); bzf->bufN++;- unused = ((void*)( 1 + ((UChar*)(unused)) ));- nUnused--;- }-- ret = BZ2_bzDecompressInit ( &(bzf->strm), verbosity, small );- if (ret != BZ_OK)- { BZ_SETERR(ret); free(bzf); return NULL; };-- bzf->strm.avail_in = bzf->bufN;- bzf->strm.next_in = bzf->buf;-- bzf->initialisedOk = True;- return bzf; -}---/*---------------------------------------------------*/-void BZ_API(BZ2_bzReadClose) ( int *bzerror, BZFILE *b )-{- bzFile* bzf = (bzFile*)b;-- BZ_SETERR(BZ_OK);- if (bzf == NULL)- { BZ_SETERR(BZ_OK); return; };-- if (bzf->writing)- { BZ_SETERR(BZ_SEQUENCE_ERROR); return; };-- if (bzf->initialisedOk)- (void)BZ2_bzDecompressEnd ( &(bzf->strm) );- free ( bzf );-}---/*---------------------------------------------------*/-int BZ_API(BZ2_bzRead) - ( int* bzerror, - BZFILE* b, - void* buf, - int len )-{- Int32 n, ret;- bzFile* bzf = (bzFile*)b;-- BZ_SETERR(BZ_OK);-- if (bzf == NULL || buf == NULL || len < 0)- { BZ_SETERR(BZ_PARAM_ERROR); return 0; };-- if (bzf->writing)- { BZ_SETERR(BZ_SEQUENCE_ERROR); return 0; };-- if (len == 0)- { BZ_SETERR(BZ_OK); return 0; };-- bzf->strm.avail_out = len;- bzf->strm.next_out = buf;-- while (True) {-- if (ferror(bzf->handle)) - { BZ_SETERR(BZ_IO_ERROR); return 0; };-- if (bzf->strm.avail_in == 0 && !myfeof(bzf->handle)) {- n = fread ( bzf->buf, sizeof(UChar), - BZ_MAX_UNUSED, bzf->handle );- if (ferror(bzf->handle))- { BZ_SETERR(BZ_IO_ERROR); return 0; };- bzf->bufN = n;- bzf->strm.avail_in = bzf->bufN;- bzf->strm.next_in = bzf->buf;- }-- ret = BZ2_bzDecompress ( &(bzf->strm) );-- if (ret != BZ_OK && ret != BZ_STREAM_END)- { BZ_SETERR(ret); return 0; };-- if (ret == BZ_OK && myfeof(bzf->handle) && - bzf->strm.avail_in == 0 && bzf->strm.avail_out > 0)- { BZ_SETERR(BZ_UNEXPECTED_EOF); return 0; };-- if (ret == BZ_STREAM_END)- { BZ_SETERR(BZ_STREAM_END);- return len - bzf->strm.avail_out; };- if (bzf->strm.avail_out == 0)- { BZ_SETERR(BZ_OK); return len; };- - }-- return 0; /*not reached*/-}---/*---------------------------------------------------*/-void BZ_API(BZ2_bzReadGetUnused) - ( int* bzerror, - BZFILE* b, - void** unused, - int* nUnused )-{- bzFile* bzf = (bzFile*)b;- if (bzf == NULL)- { BZ_SETERR(BZ_PARAM_ERROR); return; };- if (bzf->lastErr != BZ_STREAM_END)- { BZ_SETERR(BZ_SEQUENCE_ERROR); return; };- if (unused == NULL || nUnused == NULL)- { BZ_SETERR(BZ_PARAM_ERROR); return; };-- BZ_SETERR(BZ_OK);- *nUnused = bzf->strm.avail_in;- *unused = bzf->strm.next_in;-}-#endif---/*---------------------------------------------------*/-/*--- Misc convenience stuff ---*/-/*---------------------------------------------------*/--/*---------------------------------------------------*/-int BZ_API(BZ2_bzBuffToBuffCompress) - ( char* dest, - unsigned int* destLen,- char* source, - unsigned int sourceLen,- int blockSize100k, - int verbosity, - int workFactor )-{- bz_stream strm;- int ret;-- if (dest == NULL || destLen == NULL || - source == NULL ||- blockSize100k < 1 || blockSize100k > 9 ||- verbosity < 0 || verbosity > 4 ||- workFactor < 0 || workFactor > 250) - return BZ_PARAM_ERROR;-- if (workFactor == 0) workFactor = 30;- strm.bzalloc = NULL;- strm.bzfree = NULL;- strm.opaque = NULL;- ret = BZ2_bzCompressInit ( &strm, blockSize100k, - verbosity, workFactor );- if (ret != BZ_OK) return ret;-- strm.next_in = source;- strm.next_out = dest;- strm.avail_in = sourceLen;- strm.avail_out = *destLen;-- ret = BZ2_bzCompress ( &strm, BZ_FINISH );- if (ret == BZ_FINISH_OK) goto output_overflow;- if (ret != BZ_STREAM_END) goto errhandler;-- /* normal termination */- *destLen -= strm.avail_out; - BZ2_bzCompressEnd ( &strm );- return BZ_OK;-- output_overflow:- BZ2_bzCompressEnd ( &strm );- return BZ_OUTBUFF_FULL;-- errhandler:- BZ2_bzCompressEnd ( &strm );- return ret;-}---/*---------------------------------------------------*/-int BZ_API(BZ2_bzBuffToBuffDecompress) - ( char* dest, - unsigned int* destLen,- char* source, - unsigned int sourceLen,- int small,- int verbosity )-{- bz_stream strm;- int ret;-- if (dest == NULL || destLen == NULL || - source == NULL ||- (small != 0 && small != 1) ||- verbosity < 0 || verbosity > 4) - return BZ_PARAM_ERROR;-- strm.bzalloc = NULL;- strm.bzfree = NULL;- strm.opaque = NULL;- ret = BZ2_bzDecompressInit ( &strm, verbosity, small );- if (ret != BZ_OK) return ret;-- strm.next_in = source;- strm.next_out = dest;- strm.avail_in = sourceLen;- strm.avail_out = *destLen;-- ret = BZ2_bzDecompress ( &strm );- if (ret == BZ_OK) goto output_overflow_or_eof;- if (ret != BZ_STREAM_END) goto errhandler;-- /* normal termination */- *destLen -= strm.avail_out;- BZ2_bzDecompressEnd ( &strm );- return BZ_OK;-- output_overflow_or_eof:- if (strm.avail_out > 0) {- BZ2_bzDecompressEnd ( &strm );- return BZ_UNEXPECTED_EOF;- } else {- BZ2_bzDecompressEnd ( &strm );- return BZ_OUTBUFF_FULL;- }; -- errhandler:- BZ2_bzDecompressEnd ( &strm );- return ret; -}---/*---------------------------------------------------*/-/*--- Code contributed by Yoshioka Tsuneo (tsuneo@rr.iij4u.or.jp)- to support better zlib compatibility.- This code is not _officially_ part of libbzip2 (yet);- I haven't tested it, documented it, or considered the- threading-safeness of it.- If this code breaks, please contact both Yoshioka and me.---*/-/*---------------------------------------------------*/--/*---------------------------------------------------*/-/*--- return version like "0.9.5d, 4-Sept-1999".---*/-const char * BZ_API(BZ2_bzlibVersion)(void)-{- return BZ_VERSION;-}---#ifndef BZ_NO_STDIO-/*---------------------------------------------------*/--#if defined(_WIN32) || defined(OS2) || defined(MSDOS)-# include <fcntl.h>-# include <io.h>-# define SET_BINARY_MODE(file) setmode(fileno(file),O_BINARY)-#else-# define SET_BINARY_MODE(file)-#endif-static-BZFILE * bzopen_or_bzdopen- ( const char *path, /* no use when bzdopen */- int fd, /* no use when bzdopen */- const char *mode,- int open_mode) /* bzopen: 0, bzdopen:1 */-{- int bzerr;- char unused[BZ_MAX_UNUSED];- int blockSize100k = 9;- int writing = 0;- char mode2[10] = "";- FILE *fp = NULL;- BZFILE *bzfp = NULL;- int verbosity = 0;- int workFactor = 30;- int smallMode = 0;- int nUnused = 0; -- if (mode == NULL) return NULL;- while (*mode) {- switch (*mode) {- case 'r':- writing = 0; break;- case 'w':- writing = 1; break;- case 's':- smallMode = 1; break;- default:- if (isdigit((int)(*mode))) {- blockSize100k = *mode-BZ_HDR_0;- }- }- mode++;- }- strcat(mode2, writing ? "w" : "r" );- strcat(mode2,"b"); /* binary mode */-- if (open_mode==0) {- if (path==NULL || strcmp(path,"")==0) {- fp = (writing ? stdout : stdin);- SET_BINARY_MODE(fp);- } else {- fp = fopen(path,mode2);- }- } else {-#ifdef BZ_STRICT_ANSI- fp = NULL;-#else- fp = fdopen(fd,mode2);-#endif- }- if (fp == NULL) return NULL;-- if (writing) {- /* Guard against total chaos and anarchy -- JRS */- if (blockSize100k < 1) blockSize100k = 1;- if (blockSize100k > 9) blockSize100k = 9; - bzfp = BZ2_bzWriteOpen(&bzerr,fp,blockSize100k,- verbosity,workFactor);- } else {- bzfp = BZ2_bzReadOpen(&bzerr,fp,verbosity,smallMode,- unused,nUnused);- }- if (bzfp == NULL) {- if (fp != stdin && fp != stdout) fclose(fp);- return NULL;- }- return bzfp;-}---/*---------------------------------------------------*/-/*--- open file for read or write.- ex) bzopen("file","w9")- case path="" or NULL => use stdin or stdout.---*/-BZFILE * BZ_API(BZ2_bzopen)- ( const char *path,- const char *mode )-{- return bzopen_or_bzdopen(path,-1,mode,/*bzopen*/0);-}---/*---------------------------------------------------*/-BZFILE * BZ_API(BZ2_bzdopen)- ( int fd,- const char *mode )-{- return bzopen_or_bzdopen(NULL,fd,mode,/*bzdopen*/1);-}---/*---------------------------------------------------*/-int BZ_API(BZ2_bzread) (BZFILE* b, void* buf, int len )-{- int bzerr, nread;- if (((bzFile*)b)->lastErr == BZ_STREAM_END) return 0;- nread = BZ2_bzRead(&bzerr,b,buf,len);- if (bzerr == BZ_OK || bzerr == BZ_STREAM_END) {- return nread;- } else {- return -1;- }-}---/*---------------------------------------------------*/-int BZ_API(BZ2_bzwrite) (BZFILE* b, void* buf, int len )-{- int bzerr;-- BZ2_bzWrite(&bzerr,b,buf,len);- if(bzerr == BZ_OK){- return len;- }else{- return -1;- }-}---/*---------------------------------------------------*/-int BZ_API(BZ2_bzflush) (BZFILE *b)-{- /* do nothing now... */- return 0;-}---/*---------------------------------------------------*/-void BZ_API(BZ2_bzclose) (BZFILE* b)-{- int bzerr;- FILE *fp;- - if (b==NULL) {return;}- fp = ((bzFile *)b)->handle;- if(((bzFile*)b)->writing){- BZ2_bzWriteClose(&bzerr,b,0,NULL,NULL);- if(bzerr != BZ_OK){- BZ2_bzWriteClose(NULL,b,1,NULL,NULL);- }- }else{- BZ2_bzReadClose(&bzerr,b);- }- if(fp!=stdin && fp!=stdout){- fclose(fp);- }-}---/*---------------------------------------------------*/-/*--- return last error code ---*/-static const char *bzerrorstrings[] = {- "OK"- ,"SEQUENCE_ERROR"- ,"PARAM_ERROR"- ,"MEM_ERROR"- ,"DATA_ERROR"- ,"DATA_ERROR_MAGIC"- ,"IO_ERROR"- ,"UNEXPECTED_EOF"- ,"OUTBUFF_FULL"- ,"CONFIG_ERROR"- ,"???" /* for future */- ,"???" /* for future */- ,"???" /* for future */- ,"???" /* for future */- ,"???" /* for future */- ,"???" /* for future */-};---const char * BZ_API(BZ2_bzerror) (BZFILE *b, int *errnum)-{- int err = ((bzFile *)b)->lastErr;-- if(err>0) err = 0;- *errnum = err;- return bzerrorstrings[err*-1];-}-#endif---/*-------------------------------------------------------------*/-/*--- end bzlib.c ---*/-/*-------------------------------------------------------------*/
− cbits/bzlib.h
@@ -1,288 +0,0 @@--/*-------------------------------------------------------------*/-/*--- Public header file for the library. ---*/-/*--- bzlib.h ---*/-/*-------------------------------------------------------------*/--/* ------------------------------------------------------------------- This file is part of bzip2/libbzip2, a program and library for- lossless, block-sorting data compression.-- bzip2/libbzip2 version 1.0.6 of 6 September 2010- Copyright (C) 1996-2010 Julian Seward <jseward@bzip.org>-- Please read the WARNING, DISCLAIMER and PATENTS sections in the - README file.-- This program is released under the terms of the license contained- in the file LICENSE.- ------------------------------------------------------------------ */---#ifndef _BZLIB_H-#define _BZLIB_H--#ifdef __cplusplus-extern "C" {-#endif--#define BZ_RUN 0-#define BZ_FLUSH 1-#define BZ_FINISH 2--#define BZ_OK 0-#define BZ_RUN_OK 1-#define BZ_FLUSH_OK 2-#define BZ_FINISH_OK 3-#define BZ_STREAM_END 4-#define BZ_SEQUENCE_ERROR (-1)-#define BZ_PARAM_ERROR (-2)-#define BZ_MEM_ERROR (-3)-#define BZ_DATA_ERROR (-4)-#define BZ_DATA_ERROR_MAGIC (-5)-#define BZ_IO_ERROR (-6)-#define BZ_UNEXPECTED_EOF (-7)-#define BZ_OUTBUFF_FULL (-8)-#define BZ_CONFIG_ERROR (-9)--typedef - struct {- char *next_in;- unsigned int avail_in;- unsigned int total_in_lo32;- unsigned int total_in_hi32;-- char *next_out;- unsigned int avail_out;- unsigned int total_out_lo32;- unsigned int total_out_hi32;-- void *state;-- void *(*bzalloc)(void *,int,int);- void (*bzfree)(void *,void *);- void *opaque;- } - bz_stream;---#ifndef BZ_IMPORT-#define BZ_EXPORT-#endif--#ifndef BZ_NO_STDIO-/* Need a definitition for FILE */-#include <stdio.h>-#endif--#ifdef _WIN32-# include <windows.h>-# ifdef small- /* windows.h define small to char */-# undef small-# endif-# ifdef BZ_EXPORT-# define BZ_API(func) WINAPI func-# define BZ_EXTERN extern-# else- /* import windows dll dynamically */-# define BZ_API(func) (WINAPI * func)-# define BZ_EXTERN-# endif-#else-# define BZ_API(func) func-# define BZ_EXTERN extern-#endif--/* Using WINAPI causes the function to be exported using the 'stdcall'- * calling convention. We'd rather use the ordinary calling convention- * so we redefine BZ_API to do nothing.- */-#undef BZ_API-#define BZ_API(func) func--/*-- Core (low-level) library functions --*/--BZ_EXTERN int BZ_API(BZ2_bzCompressInit) ( - bz_stream* strm, - int blockSize100k, - int verbosity, - int workFactor - );--BZ_EXTERN int BZ_API(BZ2_bzCompress) ( - bz_stream* strm, - int action - );--BZ_EXTERN int BZ_API(BZ2_bzCompressEnd) ( - bz_stream* strm - );--BZ_EXTERN int BZ_API(BZ2_bzDecompressInit) ( - bz_stream *strm, - int verbosity, - int small- );--BZ_EXTERN int BZ_API(BZ2_bzDecompress) ( - bz_stream* strm - );--BZ_EXTERN int BZ_API(BZ2_bzDecompressEnd) ( - bz_stream *strm - );----/*-- High(er) level library functions --*/--#ifndef BZ_NO_STDIO-#define BZ_MAX_UNUSED 5000--typedef void BZFILE;--BZ_EXTERN BZFILE* BZ_API(BZ2_bzReadOpen) ( - int* bzerror, - FILE* f, - int verbosity, - int small,- void* unused, - int nUnused - );--BZ_EXTERN void BZ_API(BZ2_bzReadClose) ( - int* bzerror, - BZFILE* b - );--BZ_EXTERN void BZ_API(BZ2_bzReadGetUnused) ( - int* bzerror, - BZFILE* b, - void** unused, - int* nUnused - );--BZ_EXTERN int BZ_API(BZ2_bzRead) ( - int* bzerror, - BZFILE* b, - void* buf, - int len - );--BZ_EXTERN BZFILE* BZ_API(BZ2_bzWriteOpen) ( - int* bzerror, - FILE* f, - int blockSize100k, - int verbosity, - int workFactor - );--BZ_EXTERN void BZ_API(BZ2_bzWrite) ( - int* bzerror, - BZFILE* b, - void* buf, - int len - );--BZ_EXTERN void BZ_API(BZ2_bzWriteClose) ( - int* bzerror, - BZFILE* b, - int abandon, - unsigned int* nbytes_in, - unsigned int* nbytes_out - );--BZ_EXTERN void BZ_API(BZ2_bzWriteClose64) ( - int* bzerror, - BZFILE* b, - int abandon, - unsigned int* nbytes_in_lo32, - unsigned int* nbytes_in_hi32, - unsigned int* nbytes_out_lo32, - unsigned int* nbytes_out_hi32- );-#endif---/*-- Utility functions --*/--BZ_EXTERN int BZ_API(BZ2_bzBuffToBuffCompress) ( - char* dest, - unsigned int* destLen,- char* source, - unsigned int sourceLen,- int blockSize100k, - int verbosity, - int workFactor - );--BZ_EXTERN int BZ_API(BZ2_bzBuffToBuffDecompress) ( - char* dest, - unsigned int* destLen,- char* source, - unsigned int sourceLen,- int small, - int verbosity - );---/*--- Code contributed by Yoshioka Tsuneo (tsuneo@rr.iij4u.or.jp)- to support better zlib compatibility.- This code is not _officially_ part of libbzip2 (yet);- I haven't tested it, documented it, or considered the- threading-safeness of it.- If this code breaks, please contact both Yoshioka and me.---*/--BZ_EXTERN const char * BZ_API(BZ2_bzlibVersion) (- void- );--#ifndef BZ_NO_STDIO-BZ_EXTERN BZFILE * BZ_API(BZ2_bzopen) (- const char *path,- const char *mode- );--BZ_EXTERN BZFILE * BZ_API(BZ2_bzdopen) (- int fd,- const char *mode- );- -BZ_EXTERN int BZ_API(BZ2_bzread) (- BZFILE* b, - void* buf, - int len - );--BZ_EXTERN int BZ_API(BZ2_bzwrite) (- BZFILE* b, - void* buf, - int len - );--BZ_EXTERN int BZ_API(BZ2_bzflush) (- BZFILE* b- );--BZ_EXTERN void BZ_API(BZ2_bzclose) (- BZFILE* b- );--BZ_EXTERN const char * BZ_API(BZ2_bzerror) (- BZFILE *b, - int *errnum- );-#endif--#ifdef __cplusplus-}-#endif--#endif--/*-------------------------------------------------------------*/-/*--- end bzlib.h ---*/-/*-------------------------------------------------------------*/
− cbits/bzlib_private.h
@@ -1,509 +0,0 @@--/*-------------------------------------------------------------*/-/*--- Private header file for the library. ---*/-/*--- bzlib_private.h ---*/-/*-------------------------------------------------------------*/--/* ------------------------------------------------------------------- This file is part of bzip2/libbzip2, a program and library for- lossless, block-sorting data compression.-- bzip2/libbzip2 version 1.0.6 of 6 September 2010- Copyright (C) 1996-2010 Julian Seward <jseward@bzip.org>-- Please read the WARNING, DISCLAIMER and PATENTS sections in the - README file.-- This program is released under the terms of the license contained- in the file LICENSE.- ------------------------------------------------------------------ */---#ifndef _BZLIB_PRIVATE_H-#define _BZLIB_PRIVATE_H--#include <stdlib.h>--#ifndef BZ_NO_STDIO-#include <stdio.h>-#include <ctype.h>-#include <string.h>-#endif--#include "bzlib.h"----/*-- General stuff. --*/--#define BZ_VERSION "1.0.6, 6-Sept-2010"--typedef char Char;-typedef unsigned char Bool;-typedef unsigned char UChar;-typedef int Int32;-typedef unsigned int UInt32;-typedef short Int16;-typedef unsigned short UInt16;--#define True ((Bool)1)-#define False ((Bool)0)--#ifndef __GNUC__-#define __inline__ /* */-#endif --#ifndef BZ_NO_STDIO--extern void BZ2_bz__AssertH__fail ( int errcode );-#define AssertH(cond,errcode) \- { if (!(cond)) BZ2_bz__AssertH__fail ( errcode ); }--#if BZ_DEBUG-#define AssertD(cond,msg) \- { if (!(cond)) { \- fprintf ( stderr, \- "\n\nlibbzip2(debug build): internal error\n\t%s\n", msg );\- exit(1); \- }}-#else-#define AssertD(cond,msg) /* */-#endif--#define VPrintf0(zf) \- fprintf(stderr,zf)-#define VPrintf1(zf,za1) \- fprintf(stderr,zf,za1)-#define VPrintf2(zf,za1,za2) \- fprintf(stderr,zf,za1,za2)-#define VPrintf3(zf,za1,za2,za3) \- fprintf(stderr,zf,za1,za2,za3)-#define VPrintf4(zf,za1,za2,za3,za4) \- fprintf(stderr,zf,za1,za2,za3,za4)-#define VPrintf5(zf,za1,za2,za3,za4,za5) \- fprintf(stderr,zf,za1,za2,za3,za4,za5)--#else--extern void bz_internal_error ( int errcode );-#define AssertH(cond,errcode) \- { if (!(cond)) bz_internal_error ( errcode ); }-#define AssertD(cond,msg) do { } while (0)-#define VPrintf0(zf) do { } while (0)-#define VPrintf1(zf,za1) do { } while (0)-#define VPrintf2(zf,za1,za2) do { } while (0)-#define VPrintf3(zf,za1,za2,za3) do { } while (0)-#define VPrintf4(zf,za1,za2,za3,za4) do { } while (0)-#define VPrintf5(zf,za1,za2,za3,za4,za5) do { } while (0)--#endif---#define BZALLOC(nnn) (strm->bzalloc)(strm->opaque,(nnn),1)-#define BZFREE(ppp) (strm->bzfree)(strm->opaque,(ppp))---/*-- Header bytes. --*/--#define BZ_HDR_B 0x42 /* 'B' */-#define BZ_HDR_Z 0x5a /* 'Z' */-#define BZ_HDR_h 0x68 /* 'h' */-#define BZ_HDR_0 0x30 /* '0' */- -/*-- Constants for the back end. --*/--#define BZ_MAX_ALPHA_SIZE 258-#define BZ_MAX_CODE_LEN 23--#define BZ_RUNA 0-#define BZ_RUNB 1--#define BZ_N_GROUPS 6-#define BZ_G_SIZE 50-#define BZ_N_ITERS 4--#define BZ_MAX_SELECTORS (2 + (900000 / BZ_G_SIZE))----/*-- Stuff for randomising repetitive blocks. --*/--extern Int32 BZ2_rNums[512];--#define BZ_RAND_DECLS \- Int32 rNToGo; \- Int32 rTPos \--#define BZ_RAND_INIT_MASK \- s->rNToGo = 0; \- s->rTPos = 0 \--#define BZ_RAND_MASK ((s->rNToGo == 1) ? 1 : 0)--#define BZ_RAND_UPD_MASK \- if (s->rNToGo == 0) { \- s->rNToGo = BZ2_rNums[s->rTPos]; \- s->rTPos++; \- if (s->rTPos == 512) s->rTPos = 0; \- } \- s->rNToGo--;----/*-- Stuff for doing CRCs. --*/--extern UInt32 BZ2_crc32Table[256];--#define BZ_INITIALISE_CRC(crcVar) \-{ \- crcVar = 0xffffffffL; \-}--#define BZ_FINALISE_CRC(crcVar) \-{ \- crcVar = ~(crcVar); \-}--#define BZ_UPDATE_CRC(crcVar,cha) \-{ \- crcVar = (crcVar << 8) ^ \- BZ2_crc32Table[(crcVar >> 24) ^ \- ((UChar)cha)]; \-}----/*-- States and modes for compression. --*/--#define BZ_M_IDLE 1-#define BZ_M_RUNNING 2-#define BZ_M_FLUSHING 3-#define BZ_M_FINISHING 4--#define BZ_S_OUTPUT 1-#define BZ_S_INPUT 2--#define BZ_N_RADIX 2-#define BZ_N_QSORT 12-#define BZ_N_SHELL 18-#define BZ_N_OVERSHOOT (BZ_N_RADIX + BZ_N_QSORT + BZ_N_SHELL + 2)-----/*-- Structure holding all the compression-side stuff. --*/--typedef- struct {- /* pointer back to the struct bz_stream */- bz_stream* strm;-- /* mode this stream is in, and whether inputting */- /* or outputting data */- Int32 mode;- Int32 state;-- /* remembers avail_in when flush/finish requested */- UInt32 avail_in_expect;-- /* for doing the block sorting */- UInt32* arr1;- UInt32* arr2;- UInt32* ftab;- Int32 origPtr;-- /* aliases for arr1 and arr2 */- UInt32* ptr;- UChar* block;- UInt16* mtfv;- UChar* zbits;-- /* for deciding when to use the fallback sorting algorithm */- Int32 workFactor;-- /* run-length-encoding of the input */- UInt32 state_in_ch;- Int32 state_in_len;- BZ_RAND_DECLS;-- /* input and output limits and current posns */- Int32 nblock;- Int32 nblockMAX;- Int32 numZ;- Int32 state_out_pos;-- /* map of bytes used in block */- Int32 nInUse;- Bool inUse[256];- UChar unseqToSeq[256];-- /* the buffer for bit stream creation */- UInt32 bsBuff;- Int32 bsLive;-- /* block and combined CRCs */- UInt32 blockCRC;- UInt32 combinedCRC;-- /* misc administratium */- Int32 verbosity;- Int32 blockNo;- Int32 blockSize100k;-- /* stuff for coding the MTF values */- Int32 nMTF;- Int32 mtfFreq [BZ_MAX_ALPHA_SIZE];- UChar selector [BZ_MAX_SELECTORS];- UChar selectorMtf[BZ_MAX_SELECTORS];-- UChar len [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];- Int32 code [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];- Int32 rfreq [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];- /* second dimension: only 3 needed; 4 makes index calculations faster */- UInt32 len_pack[BZ_MAX_ALPHA_SIZE][4];-- }- EState;----/*-- externs for compression. --*/--extern void -BZ2_blockSort ( EState* );--extern void -BZ2_compressBlock ( EState*, Bool );--extern void -BZ2_bsInitWrite ( EState* );--extern void -BZ2_hbAssignCodes ( Int32*, UChar*, Int32, Int32, Int32 );--extern void -BZ2_hbMakeCodeLengths ( UChar*, Int32*, Int32, Int32 );----/*-- states for decompression. --*/--#define BZ_X_IDLE 1-#define BZ_X_OUTPUT 2--#define BZ_X_MAGIC_1 10-#define BZ_X_MAGIC_2 11-#define BZ_X_MAGIC_3 12-#define BZ_X_MAGIC_4 13-#define BZ_X_BLKHDR_1 14-#define BZ_X_BLKHDR_2 15-#define BZ_X_BLKHDR_3 16-#define BZ_X_BLKHDR_4 17-#define BZ_X_BLKHDR_5 18-#define BZ_X_BLKHDR_6 19-#define BZ_X_BCRC_1 20-#define BZ_X_BCRC_2 21-#define BZ_X_BCRC_3 22-#define BZ_X_BCRC_4 23-#define BZ_X_RANDBIT 24-#define BZ_X_ORIGPTR_1 25-#define BZ_X_ORIGPTR_2 26-#define BZ_X_ORIGPTR_3 27-#define BZ_X_MAPPING_1 28-#define BZ_X_MAPPING_2 29-#define BZ_X_SELECTOR_1 30-#define BZ_X_SELECTOR_2 31-#define BZ_X_SELECTOR_3 32-#define BZ_X_CODING_1 33-#define BZ_X_CODING_2 34-#define BZ_X_CODING_3 35-#define BZ_X_MTF_1 36-#define BZ_X_MTF_2 37-#define BZ_X_MTF_3 38-#define BZ_X_MTF_4 39-#define BZ_X_MTF_5 40-#define BZ_X_MTF_6 41-#define BZ_X_ENDHDR_2 42-#define BZ_X_ENDHDR_3 43-#define BZ_X_ENDHDR_4 44-#define BZ_X_ENDHDR_5 45-#define BZ_X_ENDHDR_6 46-#define BZ_X_CCRC_1 47-#define BZ_X_CCRC_2 48-#define BZ_X_CCRC_3 49-#define BZ_X_CCRC_4 50----/*-- Constants for the fast MTF decoder. --*/--#define MTFA_SIZE 4096-#define MTFL_SIZE 16----/*-- Structure holding all the decompression-side stuff. --*/--typedef- struct {- /* pointer back to the struct bz_stream */- bz_stream* strm;-- /* state indicator for this stream */- Int32 state;-- /* for doing the final run-length decoding */- UChar state_out_ch;- Int32 state_out_len;- Bool blockRandomised;- BZ_RAND_DECLS;-- /* the buffer for bit stream reading */- UInt32 bsBuff;- Int32 bsLive;-- /* misc administratium */- Int32 blockSize100k;- Bool smallDecompress;- Int32 currBlockNo;- Int32 verbosity;-- /* for undoing the Burrows-Wheeler transform */- Int32 origPtr;- UInt32 tPos;- Int32 k0;- Int32 unzftab[256];- Int32 nblock_used;- Int32 cftab[257];- Int32 cftabCopy[257];-- /* for undoing the Burrows-Wheeler transform (FAST) */- UInt32 *tt;-- /* for undoing the Burrows-Wheeler transform (SMALL) */- UInt16 *ll16;- UChar *ll4;-- /* stored and calculated CRCs */- UInt32 storedBlockCRC;- UInt32 storedCombinedCRC;- UInt32 calculatedBlockCRC;- UInt32 calculatedCombinedCRC;-- /* map of bytes used in block */- Int32 nInUse;- Bool inUse[256];- Bool inUse16[16];- UChar seqToUnseq[256];-- /* for decoding the MTF values */- UChar mtfa [MTFA_SIZE];- Int32 mtfbase[256 / MTFL_SIZE];- UChar selector [BZ_MAX_SELECTORS];- UChar selectorMtf[BZ_MAX_SELECTORS];- UChar len [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];-- Int32 limit [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];- Int32 base [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];- Int32 perm [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];- Int32 minLens[BZ_N_GROUPS];-- /* save area for scalars in the main decompress code */- Int32 save_i;- Int32 save_j;- Int32 save_t;- Int32 save_alphaSize;- Int32 save_nGroups;- Int32 save_nSelectors;- Int32 save_EOB;- Int32 save_groupNo;- Int32 save_groupPos;- Int32 save_nextSym;- Int32 save_nblockMAX;- Int32 save_nblock;- Int32 save_es;- Int32 save_N;- Int32 save_curr;- Int32 save_zt;- Int32 save_zn; - Int32 save_zvec;- Int32 save_zj;- Int32 save_gSel;- Int32 save_gMinlen;- Int32* save_gLimit;- Int32* save_gBase;- Int32* save_gPerm;-- }- DState;----/*-- Macros for decompression. --*/--#define BZ_GET_FAST(cccc) \- /* c_tPos is unsigned, hence test < 0 is pointless. */ \- if (s->tPos >= (UInt32)100000 * (UInt32)s->blockSize100k) return True; \- s->tPos = s->tt[s->tPos]; \- cccc = (UChar)(s->tPos & 0xff); \- s->tPos >>= 8;--#define BZ_GET_FAST_C(cccc) \- /* c_tPos is unsigned, hence test < 0 is pointless. */ \- if (c_tPos >= (UInt32)100000 * (UInt32)ro_blockSize100k) return True; \- c_tPos = c_tt[c_tPos]; \- cccc = (UChar)(c_tPos & 0xff); \- c_tPos >>= 8;--#define SET_LL4(i,n) \- { if (((i) & 0x1) == 0) \- s->ll4[(i) >> 1] = (s->ll4[(i) >> 1] & 0xf0) | (n); else \- s->ll4[(i) >> 1] = (s->ll4[(i) >> 1] & 0x0f) | ((n) << 4); \- }--#define GET_LL4(i) \- ((((UInt32)(s->ll4[(i) >> 1])) >> (((i) << 2) & 0x4)) & 0xF)--#define SET_LL(i,n) \- { s->ll16[i] = (UInt16)(n & 0x0000ffff); \- SET_LL4(i, n >> 16); \- }--#define GET_LL(i) \- (((UInt32)s->ll16[i]) | (GET_LL4(i) << 16))--#define BZ_GET_SMALL(cccc) \- /* c_tPos is unsigned, hence test < 0 is pointless. */ \- if (s->tPos >= (UInt32)100000 * (UInt32)s->blockSize100k) return True; \- cccc = BZ2_indexIntoF ( s->tPos, s->cftab ); \- s->tPos = GET_LL(s->tPos);---/*-- externs for decompression. --*/--extern Int32 -BZ2_indexIntoF ( Int32, Int32* );--extern Int32 -BZ2_decompress ( DState* );--extern void -BZ2_hbCreateDecodeTables ( Int32*, Int32*, Int32*, UChar*,- Int32, Int32, Int32 );---#endif---/*-- BZ_NO_STDIO seems to make NULL disappear on some platforms. --*/--#ifdef BZ_NO_STDIO-#ifndef NULL-#define NULL 0-#endif-#endif---/*-------------------------------------------------------------*/-/*--- end bzlib_private.h ---*/-/*-------------------------------------------------------------*/
− cbits/compress.c
@@ -1,672 +0,0 @@--/*-------------------------------------------------------------*/-/*--- Compression machinery (not incl block sorting) ---*/-/*--- compress.c ---*/-/*-------------------------------------------------------------*/--/* ------------------------------------------------------------------- This file is part of bzip2/libbzip2, a program and library for- lossless, block-sorting data compression.-- bzip2/libbzip2 version 1.0.6 of 6 September 2010- Copyright (C) 1996-2010 Julian Seward <jseward@bzip.org>-- Please read the WARNING, DISCLAIMER and PATENTS sections in the - README file.-- This program is released under the terms of the license contained- in the file LICENSE.- ------------------------------------------------------------------ */---/* CHANGES- 0.9.0 -- original version.- 0.9.0a/b -- no changes in this file.- 0.9.0c -- changed setting of nGroups in sendMTFValues() - so as to do a bit better on small files-*/--#include "bzlib_private.h"---/*---------------------------------------------------*/-/*--- Bit stream I/O ---*/-/*---------------------------------------------------*/--/*---------------------------------------------------*/-void BZ2_bsInitWrite ( EState* s )-{- s->bsLive = 0;- s->bsBuff = 0;-}---/*---------------------------------------------------*/-static-void bsFinishWrite ( EState* s )-{- while (s->bsLive > 0) {- s->zbits[s->numZ] = (UChar)(s->bsBuff >> 24);- s->numZ++;- s->bsBuff <<= 8;- s->bsLive -= 8;- }-}---/*---------------------------------------------------*/-#define bsNEEDW(nz) \-{ \- while (s->bsLive >= 8) { \- s->zbits[s->numZ] \- = (UChar)(s->bsBuff >> 24); \- s->numZ++; \- s->bsBuff <<= 8; \- s->bsLive -= 8; \- } \-}---/*---------------------------------------------------*/-static-__inline__-void bsW ( EState* s, Int32 n, UInt32 v )-{- bsNEEDW ( n );- s->bsBuff |= (v << (32 - s->bsLive - n));- s->bsLive += n;-}---/*---------------------------------------------------*/-static-void bsPutUInt32 ( EState* s, UInt32 u )-{- bsW ( s, 8, (u >> 24) & 0xffL );- bsW ( s, 8, (u >> 16) & 0xffL );- bsW ( s, 8, (u >> 8) & 0xffL );- bsW ( s, 8, u & 0xffL );-}---/*---------------------------------------------------*/-static-void bsPutUChar ( EState* s, UChar c )-{- bsW( s, 8, (UInt32)c );-}---/*---------------------------------------------------*/-/*--- The back end proper ---*/-/*---------------------------------------------------*/--/*---------------------------------------------------*/-static-void makeMaps_e ( EState* s )-{- Int32 i;- s->nInUse = 0;- for (i = 0; i < 256; i++)- if (s->inUse[i]) {- s->unseqToSeq[i] = s->nInUse;- s->nInUse++;- }-}---/*---------------------------------------------------*/-static-void generateMTFValues ( EState* s )-{- UChar yy[256];- Int32 i, j;- Int32 zPend;- Int32 wr;- Int32 EOB;-- /* - After sorting (eg, here),- s->arr1 [ 0 .. s->nblock-1 ] holds sorted order,- and- ((UChar*)s->arr2) [ 0 .. s->nblock-1 ] - holds the original block data.-- The first thing to do is generate the MTF values,- and put them in- ((UInt16*)s->arr1) [ 0 .. s->nblock-1 ].- Because there are strictly fewer or equal MTF values- than block values, ptr values in this area are overwritten- with MTF values only when they are no longer needed.-- The final compressed bitstream is generated into the- area starting at- (UChar*) (&((UChar*)s->arr2)[s->nblock])-- These storage aliases are set up in bzCompressInit(),- except for the last one, which is arranged in - compressBlock().- */- UInt32* ptr = s->ptr;- UChar* block = s->block;- UInt16* mtfv = s->mtfv;-- makeMaps_e ( s );- EOB = s->nInUse+1;-- for (i = 0; i <= EOB; i++) s->mtfFreq[i] = 0;-- wr = 0;- zPend = 0;- for (i = 0; i < s->nInUse; i++) yy[i] = (UChar) i;-- for (i = 0; i < s->nblock; i++) {- UChar ll_i;- AssertD ( wr <= i, "generateMTFValues(1)" );- j = ptr[i]-1; if (j < 0) j += s->nblock;- ll_i = s->unseqToSeq[block[j]];- AssertD ( ll_i < s->nInUse, "generateMTFValues(2a)" );-- if (yy[0] == ll_i) { - zPend++;- } else {-- if (zPend > 0) {- zPend--;- while (True) {- if (zPend & 1) {- mtfv[wr] = BZ_RUNB; wr++; - s->mtfFreq[BZ_RUNB]++; - } else {- mtfv[wr] = BZ_RUNA; wr++; - s->mtfFreq[BZ_RUNA]++; - }- if (zPend < 2) break;- zPend = (zPend - 2) / 2;- };- zPend = 0;- }- {- register UChar rtmp;- register UChar* ryy_j;- register UChar rll_i;- rtmp = yy[1];- yy[1] = yy[0];- ryy_j = &(yy[1]);- rll_i = ll_i;- while ( rll_i != rtmp ) {- register UChar rtmp2;- ryy_j++;- rtmp2 = rtmp;- rtmp = *ryy_j;- *ryy_j = rtmp2;- };- yy[0] = rtmp;- j = ryy_j - &(yy[0]);- mtfv[wr] = j+1; wr++; s->mtfFreq[j+1]++;- }-- }- }-- if (zPend > 0) {- zPend--;- while (True) {- if (zPend & 1) {- mtfv[wr] = BZ_RUNB; wr++; - s->mtfFreq[BZ_RUNB]++; - } else {- mtfv[wr] = BZ_RUNA; wr++; - s->mtfFreq[BZ_RUNA]++; - }- if (zPend < 2) break;- zPend = (zPend - 2) / 2;- };- zPend = 0;- }-- mtfv[wr] = EOB; wr++; s->mtfFreq[EOB]++;-- s->nMTF = wr;-}---/*---------------------------------------------------*/-#define BZ_LESSER_ICOST 0-#define BZ_GREATER_ICOST 15--static-void sendMTFValues ( EState* s )-{- Int32 v, t, i, j, gs, ge, totc, bt, bc, iter;- Int32 nSelectors, alphaSize, minLen, maxLen, selCtr;- Int32 nGroups, nBytes;-- /*--- UChar len [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];- is a global since the decoder also needs it.-- Int32 code[BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];- Int32 rfreq[BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];- are also globals only used in this proc.- Made global to keep stack frame size small.- --*/--- UInt16 cost[BZ_N_GROUPS];- Int32 fave[BZ_N_GROUPS];-- UInt16* mtfv = s->mtfv;-- if (s->verbosity >= 3)- VPrintf3( " %d in block, %d after MTF & 1-2 coding, "- "%d+2 syms in use\n", - s->nblock, s->nMTF, s->nInUse );-- alphaSize = s->nInUse+2;- for (t = 0; t < BZ_N_GROUPS; t++)- for (v = 0; v < alphaSize; v++)- s->len[t][v] = BZ_GREATER_ICOST;-- /*--- Decide how many coding tables to use ---*/- AssertH ( s->nMTF > 0, 3001 );- if (s->nMTF < 200) nGroups = 2; else- if (s->nMTF < 600) nGroups = 3; else- if (s->nMTF < 1200) nGroups = 4; else- if (s->nMTF < 2400) nGroups = 5; else- nGroups = 6;-- /*--- Generate an initial set of coding tables ---*/- { - Int32 nPart, remF, tFreq, aFreq;-- nPart = nGroups;- remF = s->nMTF;- gs = 0;- while (nPart > 0) {- tFreq = remF / nPart;- ge = gs-1;- aFreq = 0;- while (aFreq < tFreq && ge < alphaSize-1) {- ge++;- aFreq += s->mtfFreq[ge];- }-- if (ge > gs - && nPart != nGroups && nPart != 1 - && ((nGroups-nPart) % 2 == 1)) {- aFreq -= s->mtfFreq[ge];- ge--;- }-- if (s->verbosity >= 3)- VPrintf5( " initial group %d, [%d .. %d], "- "has %d syms (%4.1f%%)\n",- nPart, gs, ge, aFreq, - (100.0 * (float)aFreq) / (float)(s->nMTF) );- - for (v = 0; v < alphaSize; v++)- if (v >= gs && v <= ge) - s->len[nPart-1][v] = BZ_LESSER_ICOST; else- s->len[nPart-1][v] = BZ_GREATER_ICOST;- - nPart--;- gs = ge+1;- remF -= aFreq;- }- }-- /*--- - Iterate up to BZ_N_ITERS times to improve the tables.- ---*/- for (iter = 0; iter < BZ_N_ITERS; iter++) {-- for (t = 0; t < nGroups; t++) fave[t] = 0;-- for (t = 0; t < nGroups; t++)- for (v = 0; v < alphaSize; v++)- s->rfreq[t][v] = 0;-- /*---- Set up an auxiliary length table which is used to fast-track- the common case (nGroups == 6). - ---*/- if (nGroups == 6) {- for (v = 0; v < alphaSize; v++) {- s->len_pack[v][0] = (s->len[1][v] << 16) | s->len[0][v];- s->len_pack[v][1] = (s->len[3][v] << 16) | s->len[2][v];- s->len_pack[v][2] = (s->len[5][v] << 16) | s->len[4][v];- }- }-- nSelectors = 0;- totc = 0;- gs = 0;- while (True) {-- /*--- Set group start & end marks. --*/- if (gs >= s->nMTF) break;- ge = gs + BZ_G_SIZE - 1; - if (ge >= s->nMTF) ge = s->nMTF-1;-- /*-- - Calculate the cost of this group as coded- by each of the coding tables.- --*/- for (t = 0; t < nGroups; t++) cost[t] = 0;-- if (nGroups == 6 && 50 == ge-gs+1) {- /*--- fast track the common case ---*/- register UInt32 cost01, cost23, cost45;- register UInt16 icv;- cost01 = cost23 = cost45 = 0;--# define BZ_ITER(nn) \- icv = mtfv[gs+(nn)]; \- cost01 += s->len_pack[icv][0]; \- cost23 += s->len_pack[icv][1]; \- cost45 += s->len_pack[icv][2]; \-- BZ_ITER(0); BZ_ITER(1); BZ_ITER(2); BZ_ITER(3); BZ_ITER(4);- BZ_ITER(5); BZ_ITER(6); BZ_ITER(7); BZ_ITER(8); BZ_ITER(9);- BZ_ITER(10); BZ_ITER(11); BZ_ITER(12); BZ_ITER(13); BZ_ITER(14);- BZ_ITER(15); BZ_ITER(16); BZ_ITER(17); BZ_ITER(18); BZ_ITER(19);- BZ_ITER(20); BZ_ITER(21); BZ_ITER(22); BZ_ITER(23); BZ_ITER(24);- BZ_ITER(25); BZ_ITER(26); BZ_ITER(27); BZ_ITER(28); BZ_ITER(29);- BZ_ITER(30); BZ_ITER(31); BZ_ITER(32); BZ_ITER(33); BZ_ITER(34);- BZ_ITER(35); BZ_ITER(36); BZ_ITER(37); BZ_ITER(38); BZ_ITER(39);- BZ_ITER(40); BZ_ITER(41); BZ_ITER(42); BZ_ITER(43); BZ_ITER(44);- BZ_ITER(45); BZ_ITER(46); BZ_ITER(47); BZ_ITER(48); BZ_ITER(49);--# undef BZ_ITER-- cost[0] = cost01 & 0xffff; cost[1] = cost01 >> 16;- cost[2] = cost23 & 0xffff; cost[3] = cost23 >> 16;- cost[4] = cost45 & 0xffff; cost[5] = cost45 >> 16;-- } else {- /*--- slow version which correctly handles all situations ---*/- for (i = gs; i <= ge; i++) { - UInt16 icv = mtfv[i];- for (t = 0; t < nGroups; t++) cost[t] += s->len[t][icv];- }- }- - /*-- - Find the coding table which is best for this group,- and record its identity in the selector table.- --*/- bc = 999999999; bt = -1;- for (t = 0; t < nGroups; t++)- if (cost[t] < bc) { bc = cost[t]; bt = t; };- totc += bc;- fave[bt]++;- s->selector[nSelectors] = bt;- nSelectors++;-- /*-- - Increment the symbol frequencies for the selected table.- --*/- if (nGroups == 6 && 50 == ge-gs+1) {- /*--- fast track the common case ---*/--# define BZ_ITUR(nn) s->rfreq[bt][ mtfv[gs+(nn)] ]++-- BZ_ITUR(0); BZ_ITUR(1); BZ_ITUR(2); BZ_ITUR(3); BZ_ITUR(4);- BZ_ITUR(5); BZ_ITUR(6); BZ_ITUR(7); BZ_ITUR(8); BZ_ITUR(9);- BZ_ITUR(10); BZ_ITUR(11); BZ_ITUR(12); BZ_ITUR(13); BZ_ITUR(14);- BZ_ITUR(15); BZ_ITUR(16); BZ_ITUR(17); BZ_ITUR(18); BZ_ITUR(19);- BZ_ITUR(20); BZ_ITUR(21); BZ_ITUR(22); BZ_ITUR(23); BZ_ITUR(24);- BZ_ITUR(25); BZ_ITUR(26); BZ_ITUR(27); BZ_ITUR(28); BZ_ITUR(29);- BZ_ITUR(30); BZ_ITUR(31); BZ_ITUR(32); BZ_ITUR(33); BZ_ITUR(34);- BZ_ITUR(35); BZ_ITUR(36); BZ_ITUR(37); BZ_ITUR(38); BZ_ITUR(39);- BZ_ITUR(40); BZ_ITUR(41); BZ_ITUR(42); BZ_ITUR(43); BZ_ITUR(44);- BZ_ITUR(45); BZ_ITUR(46); BZ_ITUR(47); BZ_ITUR(48); BZ_ITUR(49);--# undef BZ_ITUR-- } else {- /*--- slow version which correctly handles all situations ---*/- for (i = gs; i <= ge; i++)- s->rfreq[bt][ mtfv[i] ]++;- }-- gs = ge+1;- }- if (s->verbosity >= 3) {- VPrintf2 ( " pass %d: size is %d, grp uses are ", - iter+1, totc/8 );- for (t = 0; t < nGroups; t++)- VPrintf1 ( "%d ", fave[t] );- VPrintf0 ( "\n" );- }-- /*--- Recompute the tables based on the accumulated frequencies.- --*/- /* maxLen was changed from 20 to 17 in bzip2-1.0.3. See - comment in huffman.c for details. */- for (t = 0; t < nGroups; t++)- BZ2_hbMakeCodeLengths ( &(s->len[t][0]), &(s->rfreq[t][0]), - alphaSize, 17 /*20*/ );- }--- AssertH( nGroups < 8, 3002 );- AssertH( nSelectors < 32768 &&- nSelectors <= (2 + (900000 / BZ_G_SIZE)),- 3003 );--- /*--- Compute MTF values for the selectors. ---*/- {- UChar pos[BZ_N_GROUPS], ll_i, tmp2, tmp;- for (i = 0; i < nGroups; i++) pos[i] = i;- for (i = 0; i < nSelectors; i++) {- ll_i = s->selector[i];- j = 0;- tmp = pos[j];- while ( ll_i != tmp ) {- j++;- tmp2 = tmp;- tmp = pos[j];- pos[j] = tmp2;- };- pos[0] = tmp;- s->selectorMtf[i] = j;- }- };-- /*--- Assign actual codes for the tables. --*/- for (t = 0; t < nGroups; t++) {- minLen = 32;- maxLen = 0;- for (i = 0; i < alphaSize; i++) {- if (s->len[t][i] > maxLen) maxLen = s->len[t][i];- if (s->len[t][i] < minLen) minLen = s->len[t][i];- }- AssertH ( !(maxLen > 17 /*20*/ ), 3004 );- AssertH ( !(minLen < 1), 3005 );- BZ2_hbAssignCodes ( &(s->code[t][0]), &(s->len[t][0]), - minLen, maxLen, alphaSize );- }-- /*--- Transmit the mapping table. ---*/- { - Bool inUse16[16];- for (i = 0; i < 16; i++) {- inUse16[i] = False;- for (j = 0; j < 16; j++)- if (s->inUse[i * 16 + j]) inUse16[i] = True;- }- - nBytes = s->numZ;- for (i = 0; i < 16; i++)- if (inUse16[i]) bsW(s,1,1); else bsW(s,1,0);-- for (i = 0; i < 16; i++)- if (inUse16[i])- for (j = 0; j < 16; j++) {- if (s->inUse[i * 16 + j]) bsW(s,1,1); else bsW(s,1,0);- }-- if (s->verbosity >= 3) - VPrintf1( " bytes: mapping %d, ", s->numZ-nBytes );- }-- /*--- Now the selectors. ---*/- nBytes = s->numZ;- bsW ( s, 3, nGroups );- bsW ( s, 15, nSelectors );- for (i = 0; i < nSelectors; i++) { - for (j = 0; j < s->selectorMtf[i]; j++) bsW(s,1,1);- bsW(s,1,0);- }- if (s->verbosity >= 3)- VPrintf1( "selectors %d, ", s->numZ-nBytes );-- /*--- Now the coding tables. ---*/- nBytes = s->numZ;-- for (t = 0; t < nGroups; t++) {- Int32 curr = s->len[t][0];- bsW ( s, 5, curr );- for (i = 0; i < alphaSize; i++) {- while (curr < s->len[t][i]) { bsW(s,2,2); curr++; /* 10 */ };- while (curr > s->len[t][i]) { bsW(s,2,3); curr--; /* 11 */ };- bsW ( s, 1, 0 );- }- }-- if (s->verbosity >= 3)- VPrintf1 ( "code lengths %d, ", s->numZ-nBytes );-- /*--- And finally, the block data proper ---*/- nBytes = s->numZ;- selCtr = 0;- gs = 0;- while (True) {- if (gs >= s->nMTF) break;- ge = gs + BZ_G_SIZE - 1; - if (ge >= s->nMTF) ge = s->nMTF-1;- AssertH ( s->selector[selCtr] < nGroups, 3006 );-- if (nGroups == 6 && 50 == ge-gs+1) {- /*--- fast track the common case ---*/- UInt16 mtfv_i;- UChar* s_len_sel_selCtr - = &(s->len[s->selector[selCtr]][0]);- Int32* s_code_sel_selCtr- = &(s->code[s->selector[selCtr]][0]);--# define BZ_ITAH(nn) \- mtfv_i = mtfv[gs+(nn)]; \- bsW ( s, \- s_len_sel_selCtr[mtfv_i], \- s_code_sel_selCtr[mtfv_i] )-- BZ_ITAH(0); BZ_ITAH(1); BZ_ITAH(2); BZ_ITAH(3); BZ_ITAH(4);- BZ_ITAH(5); BZ_ITAH(6); BZ_ITAH(7); BZ_ITAH(8); BZ_ITAH(9);- BZ_ITAH(10); BZ_ITAH(11); BZ_ITAH(12); BZ_ITAH(13); BZ_ITAH(14);- BZ_ITAH(15); BZ_ITAH(16); BZ_ITAH(17); BZ_ITAH(18); BZ_ITAH(19);- BZ_ITAH(20); BZ_ITAH(21); BZ_ITAH(22); BZ_ITAH(23); BZ_ITAH(24);- BZ_ITAH(25); BZ_ITAH(26); BZ_ITAH(27); BZ_ITAH(28); BZ_ITAH(29);- BZ_ITAH(30); BZ_ITAH(31); BZ_ITAH(32); BZ_ITAH(33); BZ_ITAH(34);- BZ_ITAH(35); BZ_ITAH(36); BZ_ITAH(37); BZ_ITAH(38); BZ_ITAH(39);- BZ_ITAH(40); BZ_ITAH(41); BZ_ITAH(42); BZ_ITAH(43); BZ_ITAH(44);- BZ_ITAH(45); BZ_ITAH(46); BZ_ITAH(47); BZ_ITAH(48); BZ_ITAH(49);--# undef BZ_ITAH-- } else {- /*--- slow version which correctly handles all situations ---*/- for (i = gs; i <= ge; i++) {- bsW ( s, - s->len [s->selector[selCtr]] [mtfv[i]],- s->code [s->selector[selCtr]] [mtfv[i]] );- }- }--- gs = ge+1;- selCtr++;- }- AssertH( selCtr == nSelectors, 3007 );-- if (s->verbosity >= 3)- VPrintf1( "codes %d\n", s->numZ-nBytes );-}---/*---------------------------------------------------*/-void BZ2_compressBlock ( EState* s, Bool is_last_block )-{- if (s->nblock > 0) {-- BZ_FINALISE_CRC ( s->blockCRC );- s->combinedCRC = (s->combinedCRC << 1) | (s->combinedCRC >> 31);- s->combinedCRC ^= s->blockCRC;- if (s->blockNo > 1) s->numZ = 0;-- if (s->verbosity >= 2)- VPrintf4( " block %d: crc = 0x%08x, "- "combined CRC = 0x%08x, size = %d\n",- s->blockNo, s->blockCRC, s->combinedCRC, s->nblock );-- BZ2_blockSort ( s );- }-- s->zbits = (UChar*) (&((UChar*)s->arr2)[s->nblock]);-- /*-- If this is the first block, create the stream header. --*/- if (s->blockNo == 1) {- BZ2_bsInitWrite ( s );- bsPutUChar ( s, BZ_HDR_B );- bsPutUChar ( s, BZ_HDR_Z );- bsPutUChar ( s, BZ_HDR_h );- bsPutUChar ( s, (UChar)(BZ_HDR_0 + s->blockSize100k) );- }-- if (s->nblock > 0) {-- bsPutUChar ( s, 0x31 ); bsPutUChar ( s, 0x41 );- bsPutUChar ( s, 0x59 ); bsPutUChar ( s, 0x26 );- bsPutUChar ( s, 0x53 ); bsPutUChar ( s, 0x59 );-- /*-- Now the block's CRC, so it is in a known place. --*/- bsPutUInt32 ( s, s->blockCRC );-- /*-- - Now a single bit indicating (non-)randomisation. - As of version 0.9.5, we use a better sorting algorithm- which makes randomisation unnecessary. So always set- the randomised bit to 'no'. Of course, the decoder- still needs to be able to handle randomised blocks- so as to maintain backwards compatibility with- older versions of bzip2.- --*/- bsW(s,1,0);-- bsW ( s, 24, s->origPtr );- generateMTFValues ( s );- sendMTFValues ( s );- }--- /*-- If this is the last block, add the stream trailer. --*/- if (is_last_block) {-- bsPutUChar ( s, 0x17 ); bsPutUChar ( s, 0x72 );- bsPutUChar ( s, 0x45 ); bsPutUChar ( s, 0x38 );- bsPutUChar ( s, 0x50 ); bsPutUChar ( s, 0x90 );- bsPutUInt32 ( s, s->combinedCRC );- if (s->verbosity >= 2)- VPrintf1( " final combined CRC = 0x%08x\n ", s->combinedCRC );- bsFinishWrite ( s );- }-}---/*-------------------------------------------------------------*/-/*--- end compress.c ---*/-/*-------------------------------------------------------------*/
− cbits/crctable.c
@@ -1,104 +0,0 @@--/*-------------------------------------------------------------*/-/*--- Table for doing CRCs ---*/-/*--- crctable.c ---*/-/*-------------------------------------------------------------*/--/* ------------------------------------------------------------------- This file is part of bzip2/libbzip2, a program and library for- lossless, block-sorting data compression.-- bzip2/libbzip2 version 1.0.6 of 6 September 2010- Copyright (C) 1996-2010 Julian Seward <jseward@bzip.org>-- Please read the WARNING, DISCLAIMER and PATENTS sections in the - README file.-- This program is released under the terms of the license contained- in the file LICENSE.- ------------------------------------------------------------------ */---#include "bzlib_private.h"--/*--- I think this is an implementation of the AUTODIN-II,- Ethernet & FDDI 32-bit CRC standard. Vaguely derived- from code by Rob Warnock, in Section 51 of the- comp.compression FAQ.---*/--UInt32 BZ2_crc32Table[256] = {-- /*-- Ugly, innit? --*/-- 0x00000000L, 0x04c11db7L, 0x09823b6eL, 0x0d4326d9L,- 0x130476dcL, 0x17c56b6bL, 0x1a864db2L, 0x1e475005L,- 0x2608edb8L, 0x22c9f00fL, 0x2f8ad6d6L, 0x2b4bcb61L,- 0x350c9b64L, 0x31cd86d3L, 0x3c8ea00aL, 0x384fbdbdL,- 0x4c11db70L, 0x48d0c6c7L, 0x4593e01eL, 0x4152fda9L,- 0x5f15adacL, 0x5bd4b01bL, 0x569796c2L, 0x52568b75L,- 0x6a1936c8L, 0x6ed82b7fL, 0x639b0da6L, 0x675a1011L,- 0x791d4014L, 0x7ddc5da3L, 0x709f7b7aL, 0x745e66cdL,- 0x9823b6e0L, 0x9ce2ab57L, 0x91a18d8eL, 0x95609039L,- 0x8b27c03cL, 0x8fe6dd8bL, 0x82a5fb52L, 0x8664e6e5L,- 0xbe2b5b58L, 0xbaea46efL, 0xb7a96036L, 0xb3687d81L,- 0xad2f2d84L, 0xa9ee3033L, 0xa4ad16eaL, 0xa06c0b5dL,- 0xd4326d90L, 0xd0f37027L, 0xddb056feL, 0xd9714b49L,- 0xc7361b4cL, 0xc3f706fbL, 0xceb42022L, 0xca753d95L,- 0xf23a8028L, 0xf6fb9d9fL, 0xfbb8bb46L, 0xff79a6f1L,- 0xe13ef6f4L, 0xe5ffeb43L, 0xe8bccd9aL, 0xec7dd02dL,- 0x34867077L, 0x30476dc0L, 0x3d044b19L, 0x39c556aeL,- 0x278206abL, 0x23431b1cL, 0x2e003dc5L, 0x2ac12072L,- 0x128e9dcfL, 0x164f8078L, 0x1b0ca6a1L, 0x1fcdbb16L,- 0x018aeb13L, 0x054bf6a4L, 0x0808d07dL, 0x0cc9cdcaL,- 0x7897ab07L, 0x7c56b6b0L, 0x71159069L, 0x75d48ddeL,- 0x6b93dddbL, 0x6f52c06cL, 0x6211e6b5L, 0x66d0fb02L,- 0x5e9f46bfL, 0x5a5e5b08L, 0x571d7dd1L, 0x53dc6066L,- 0x4d9b3063L, 0x495a2dd4L, 0x44190b0dL, 0x40d816baL,- 0xaca5c697L, 0xa864db20L, 0xa527fdf9L, 0xa1e6e04eL,- 0xbfa1b04bL, 0xbb60adfcL, 0xb6238b25L, 0xb2e29692L,- 0x8aad2b2fL, 0x8e6c3698L, 0x832f1041L, 0x87ee0df6L,- 0x99a95df3L, 0x9d684044L, 0x902b669dL, 0x94ea7b2aL,- 0xe0b41de7L, 0xe4750050L, 0xe9362689L, 0xedf73b3eL,- 0xf3b06b3bL, 0xf771768cL, 0xfa325055L, 0xfef34de2L,- 0xc6bcf05fL, 0xc27dede8L, 0xcf3ecb31L, 0xcbffd686L,- 0xd5b88683L, 0xd1799b34L, 0xdc3abdedL, 0xd8fba05aL,- 0x690ce0eeL, 0x6dcdfd59L, 0x608edb80L, 0x644fc637L,- 0x7a089632L, 0x7ec98b85L, 0x738aad5cL, 0x774bb0ebL,- 0x4f040d56L, 0x4bc510e1L, 0x46863638L, 0x42472b8fL,- 0x5c007b8aL, 0x58c1663dL, 0x558240e4L, 0x51435d53L,- 0x251d3b9eL, 0x21dc2629L, 0x2c9f00f0L, 0x285e1d47L,- 0x36194d42L, 0x32d850f5L, 0x3f9b762cL, 0x3b5a6b9bL,- 0x0315d626L, 0x07d4cb91L, 0x0a97ed48L, 0x0e56f0ffL,- 0x1011a0faL, 0x14d0bd4dL, 0x19939b94L, 0x1d528623L,- 0xf12f560eL, 0xf5ee4bb9L, 0xf8ad6d60L, 0xfc6c70d7L,- 0xe22b20d2L, 0xe6ea3d65L, 0xeba91bbcL, 0xef68060bL,- 0xd727bbb6L, 0xd3e6a601L, 0xdea580d8L, 0xda649d6fL,- 0xc423cd6aL, 0xc0e2d0ddL, 0xcda1f604L, 0xc960ebb3L,- 0xbd3e8d7eL, 0xb9ff90c9L, 0xb4bcb610L, 0xb07daba7L,- 0xae3afba2L, 0xaafbe615L, 0xa7b8c0ccL, 0xa379dd7bL,- 0x9b3660c6L, 0x9ff77d71L, 0x92b45ba8L, 0x9675461fL,- 0x8832161aL, 0x8cf30badL, 0x81b02d74L, 0x857130c3L,- 0x5d8a9099L, 0x594b8d2eL, 0x5408abf7L, 0x50c9b640L,- 0x4e8ee645L, 0x4a4ffbf2L, 0x470cdd2bL, 0x43cdc09cL,- 0x7b827d21L, 0x7f436096L, 0x7200464fL, 0x76c15bf8L,- 0x68860bfdL, 0x6c47164aL, 0x61043093L, 0x65c52d24L,- 0x119b4be9L, 0x155a565eL, 0x18197087L, 0x1cd86d30L,- 0x029f3d35L, 0x065e2082L, 0x0b1d065bL, 0x0fdc1becL,- 0x3793a651L, 0x3352bbe6L, 0x3e119d3fL, 0x3ad08088L,- 0x2497d08dL, 0x2056cd3aL, 0x2d15ebe3L, 0x29d4f654L,- 0xc5a92679L, 0xc1683bceL, 0xcc2b1d17L, 0xc8ea00a0L,- 0xd6ad50a5L, 0xd26c4d12L, 0xdf2f6bcbL, 0xdbee767cL,- 0xe3a1cbc1L, 0xe760d676L, 0xea23f0afL, 0xeee2ed18L,- 0xf0a5bd1dL, 0xf464a0aaL, 0xf9278673L, 0xfde69bc4L,- 0x89b8fd09L, 0x8d79e0beL, 0x803ac667L, 0x84fbdbd0L,- 0x9abc8bd5L, 0x9e7d9662L, 0x933eb0bbL, 0x97ffad0cL,- 0xafb010b1L, 0xab710d06L, 0xa6322bdfL, 0xa2f33668L,- 0xbcb4666dL, 0xb8757bdaL, 0xb5365d03L, 0xb1f740b4L-};---/*-------------------------------------------------------------*/-/*--- end crctable.c ---*/-/*-------------------------------------------------------------*/
− cbits/decompress.c
@@ -1,646 +0,0 @@--/*-------------------------------------------------------------*/-/*--- Decompression machinery ---*/-/*--- decompress.c ---*/-/*-------------------------------------------------------------*/--/* ------------------------------------------------------------------- This file is part of bzip2/libbzip2, a program and library for- lossless, block-sorting data compression.-- bzip2/libbzip2 version 1.0.6 of 6 September 2010- Copyright (C) 1996-2010 Julian Seward <jseward@bzip.org>-- Please read the WARNING, DISCLAIMER and PATENTS sections in the - README file.-- This program is released under the terms of the license contained- in the file LICENSE.- ------------------------------------------------------------------ */---#include "bzlib_private.h"---/*---------------------------------------------------*/-static-void makeMaps_d ( DState* s )-{- Int32 i;- s->nInUse = 0;- for (i = 0; i < 256; i++)- if (s->inUse[i]) {- s->seqToUnseq[s->nInUse] = i;- s->nInUse++;- }-}---/*---------------------------------------------------*/-#define RETURN(rrr) \- { retVal = rrr; goto save_state_and_return; };--#define GET_BITS(lll,vvv,nnn) \- case lll: s->state = lll; \- while (True) { \- if (s->bsLive >= nnn) { \- UInt32 v; \- v = (s->bsBuff >> \- (s->bsLive-nnn)) & ((1 << nnn)-1); \- s->bsLive -= nnn; \- vvv = v; \- break; \- } \- if (s->strm->avail_in == 0) RETURN(BZ_OK); \- s->bsBuff \- = (s->bsBuff << 8) | \- ((UInt32) \- (*((UChar*)(s->strm->next_in)))); \- s->bsLive += 8; \- s->strm->next_in++; \- s->strm->avail_in--; \- s->strm->total_in_lo32++; \- if (s->strm->total_in_lo32 == 0) \- s->strm->total_in_hi32++; \- }--#define GET_UCHAR(lll,uuu) \- GET_BITS(lll,uuu,8)--#define GET_BIT(lll,uuu) \- GET_BITS(lll,uuu,1)--/*---------------------------------------------------*/-#define GET_MTF_VAL(label1,label2,lval) \-{ \- if (groupPos == 0) { \- groupNo++; \- if (groupNo >= nSelectors) \- RETURN(BZ_DATA_ERROR); \- groupPos = BZ_G_SIZE; \- gSel = s->selector[groupNo]; \- gMinlen = s->minLens[gSel]; \- gLimit = &(s->limit[gSel][0]); \- gPerm = &(s->perm[gSel][0]); \- gBase = &(s->base[gSel][0]); \- } \- groupPos--; \- zn = gMinlen; \- GET_BITS(label1, zvec, zn); \- while (1) { \- if (zn > 20 /* the longest code */) \- RETURN(BZ_DATA_ERROR); \- if (zvec <= gLimit[zn]) break; \- zn++; \- GET_BIT(label2, zj); \- zvec = (zvec << 1) | zj; \- }; \- if (zvec - gBase[zn] < 0 \- || zvec - gBase[zn] >= BZ_MAX_ALPHA_SIZE) \- RETURN(BZ_DATA_ERROR); \- lval = gPerm[zvec - gBase[zn]]; \-}---/*---------------------------------------------------*/-Int32 BZ2_decompress ( DState* s )-{- UChar uc;- Int32 retVal;- Int32 minLen, maxLen;- bz_stream* strm = s->strm;-- /* stuff that needs to be saved/restored */- Int32 i;- Int32 j;- Int32 t;- Int32 alphaSize;- Int32 nGroups;- Int32 nSelectors;- Int32 EOB;- Int32 groupNo;- Int32 groupPos;- Int32 nextSym;- Int32 nblockMAX;- Int32 nblock;- Int32 es;- Int32 N;- Int32 curr;- Int32 zt;- Int32 zn; - Int32 zvec;- Int32 zj;- Int32 gSel;- Int32 gMinlen;- Int32* gLimit;- Int32* gBase;- Int32* gPerm;-- if (s->state == BZ_X_MAGIC_1) {- /*initialise the save area*/- s->save_i = 0;- s->save_j = 0;- s->save_t = 0;- s->save_alphaSize = 0;- s->save_nGroups = 0;- s->save_nSelectors = 0;- s->save_EOB = 0;- s->save_groupNo = 0;- s->save_groupPos = 0;- s->save_nextSym = 0;- s->save_nblockMAX = 0;- s->save_nblock = 0;- s->save_es = 0;- s->save_N = 0;- s->save_curr = 0;- s->save_zt = 0;- s->save_zn = 0;- s->save_zvec = 0;- s->save_zj = 0;- s->save_gSel = 0;- s->save_gMinlen = 0;- s->save_gLimit = NULL;- s->save_gBase = NULL;- s->save_gPerm = NULL;- }-- /*restore from the save area*/- i = s->save_i;- j = s->save_j;- t = s->save_t;- alphaSize = s->save_alphaSize;- nGroups = s->save_nGroups;- nSelectors = s->save_nSelectors;- EOB = s->save_EOB;- groupNo = s->save_groupNo;- groupPos = s->save_groupPos;- nextSym = s->save_nextSym;- nblockMAX = s->save_nblockMAX;- nblock = s->save_nblock;- es = s->save_es;- N = s->save_N;- curr = s->save_curr;- zt = s->save_zt;- zn = s->save_zn; - zvec = s->save_zvec;- zj = s->save_zj;- gSel = s->save_gSel;- gMinlen = s->save_gMinlen;- gLimit = s->save_gLimit;- gBase = s->save_gBase;- gPerm = s->save_gPerm;-- retVal = BZ_OK;-- switch (s->state) {-- GET_UCHAR(BZ_X_MAGIC_1, uc);- if (uc != BZ_HDR_B) RETURN(BZ_DATA_ERROR_MAGIC);-- GET_UCHAR(BZ_X_MAGIC_2, uc);- if (uc != BZ_HDR_Z) RETURN(BZ_DATA_ERROR_MAGIC);-- GET_UCHAR(BZ_X_MAGIC_3, uc)- if (uc != BZ_HDR_h) RETURN(BZ_DATA_ERROR_MAGIC);-- GET_BITS(BZ_X_MAGIC_4, s->blockSize100k, 8)- if (s->blockSize100k < (BZ_HDR_0 + 1) || - s->blockSize100k > (BZ_HDR_0 + 9)) RETURN(BZ_DATA_ERROR_MAGIC);- s->blockSize100k -= BZ_HDR_0;-- if (s->smallDecompress) {- s->ll16 = BZALLOC( s->blockSize100k * 100000 * sizeof(UInt16) );- s->ll4 = BZALLOC( - ((1 + s->blockSize100k * 100000) >> 1) * sizeof(UChar) - );- if (s->ll16 == NULL || s->ll4 == NULL) RETURN(BZ_MEM_ERROR);- } else {- s->tt = BZALLOC( s->blockSize100k * 100000 * sizeof(Int32) );- if (s->tt == NULL) RETURN(BZ_MEM_ERROR);- }-- GET_UCHAR(BZ_X_BLKHDR_1, uc);-- if (uc == 0x17) goto endhdr_2;- if (uc != 0x31) RETURN(BZ_DATA_ERROR);- GET_UCHAR(BZ_X_BLKHDR_2, uc);- if (uc != 0x41) RETURN(BZ_DATA_ERROR);- GET_UCHAR(BZ_X_BLKHDR_3, uc);- if (uc != 0x59) RETURN(BZ_DATA_ERROR);- GET_UCHAR(BZ_X_BLKHDR_4, uc);- if (uc != 0x26) RETURN(BZ_DATA_ERROR);- GET_UCHAR(BZ_X_BLKHDR_5, uc);- if (uc != 0x53) RETURN(BZ_DATA_ERROR);- GET_UCHAR(BZ_X_BLKHDR_6, uc);- if (uc != 0x59) RETURN(BZ_DATA_ERROR);-- s->currBlockNo++;- if (s->verbosity >= 2)- VPrintf1 ( "\n [%d: huff+mtf ", s->currBlockNo );- - s->storedBlockCRC = 0;- GET_UCHAR(BZ_X_BCRC_1, uc);- s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);- GET_UCHAR(BZ_X_BCRC_2, uc);- s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);- GET_UCHAR(BZ_X_BCRC_3, uc);- s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);- GET_UCHAR(BZ_X_BCRC_4, uc);- s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);-- GET_BITS(BZ_X_RANDBIT, s->blockRandomised, 1);-- s->origPtr = 0;- GET_UCHAR(BZ_X_ORIGPTR_1, uc);- s->origPtr = (s->origPtr << 8) | ((Int32)uc);- GET_UCHAR(BZ_X_ORIGPTR_2, uc);- s->origPtr = (s->origPtr << 8) | ((Int32)uc);- GET_UCHAR(BZ_X_ORIGPTR_3, uc);- s->origPtr = (s->origPtr << 8) | ((Int32)uc);-- if (s->origPtr < 0)- RETURN(BZ_DATA_ERROR);- if (s->origPtr > 10 + 100000*s->blockSize100k) - RETURN(BZ_DATA_ERROR);-- /*--- Receive the mapping table ---*/- for (i = 0; i < 16; i++) {- GET_BIT(BZ_X_MAPPING_1, uc);- if (uc == 1) - s->inUse16[i] = True; else - s->inUse16[i] = False;- }-- for (i = 0; i < 256; i++) s->inUse[i] = False;-- for (i = 0; i < 16; i++)- if (s->inUse16[i])- for (j = 0; j < 16; j++) {- GET_BIT(BZ_X_MAPPING_2, uc);- if (uc == 1) s->inUse[i * 16 + j] = True;- }- makeMaps_d ( s );- if (s->nInUse == 0) RETURN(BZ_DATA_ERROR);- alphaSize = s->nInUse+2;-- /*--- Now the selectors ---*/- GET_BITS(BZ_X_SELECTOR_1, nGroups, 3);- if (nGroups < 2 || nGroups > 6) RETURN(BZ_DATA_ERROR);- GET_BITS(BZ_X_SELECTOR_2, nSelectors, 15);- if (nSelectors < 1) RETURN(BZ_DATA_ERROR);- for (i = 0; i < nSelectors; i++) {- j = 0;- while (True) {- GET_BIT(BZ_X_SELECTOR_3, uc);- if (uc == 0) break;- j++;- if (j >= nGroups) RETURN(BZ_DATA_ERROR);- }- s->selectorMtf[i] = j;- }-- /*--- Undo the MTF values for the selectors. ---*/- {- UChar pos[BZ_N_GROUPS], tmp, v;- for (v = 0; v < nGroups; v++) pos[v] = v;- - for (i = 0; i < nSelectors; i++) {- v = s->selectorMtf[i];- tmp = pos[v];- while (v > 0) { pos[v] = pos[v-1]; v--; }- pos[0] = tmp;- s->selector[i] = tmp;- }- }-- /*--- Now the coding tables ---*/- for (t = 0; t < nGroups; t++) {- GET_BITS(BZ_X_CODING_1, curr, 5);- for (i = 0; i < alphaSize; i++) {- while (True) {- if (curr < 1 || curr > 20) RETURN(BZ_DATA_ERROR);- GET_BIT(BZ_X_CODING_2, uc);- if (uc == 0) break;- GET_BIT(BZ_X_CODING_3, uc);- if (uc == 0) curr++; else curr--;- }- s->len[t][i] = curr;- }- }-- /*--- Create the Huffman decoding tables ---*/- for (t = 0; t < nGroups; t++) {- minLen = 32;- maxLen = 0;- for (i = 0; i < alphaSize; i++) {- if (s->len[t][i] > maxLen) maxLen = s->len[t][i];- if (s->len[t][i] < minLen) minLen = s->len[t][i];- }- BZ2_hbCreateDecodeTables ( - &(s->limit[t][0]), - &(s->base[t][0]), - &(s->perm[t][0]), - &(s->len[t][0]),- minLen, maxLen, alphaSize- );- s->minLens[t] = minLen;- }-- /*--- Now the MTF values ---*/-- EOB = s->nInUse+1;- nblockMAX = 100000 * s->blockSize100k;- groupNo = -1;- groupPos = 0;-- for (i = 0; i <= 255; i++) s->unzftab[i] = 0;-- /*-- MTF init --*/- {- Int32 ii, jj, kk;- kk = MTFA_SIZE-1;- for (ii = 256 / MTFL_SIZE - 1; ii >= 0; ii--) {- for (jj = MTFL_SIZE-1; jj >= 0; jj--) {- s->mtfa[kk] = (UChar)(ii * MTFL_SIZE + jj);- kk--;- }- s->mtfbase[ii] = kk + 1;- }- }- /*-- end MTF init --*/-- nblock = 0;- GET_MTF_VAL(BZ_X_MTF_1, BZ_X_MTF_2, nextSym);-- while (True) {-- if (nextSym == EOB) break;-- if (nextSym == BZ_RUNA || nextSym == BZ_RUNB) {-- es = -1;- N = 1;- do {- /* Check that N doesn't get too big, so that es doesn't- go negative. The maximum value that can be- RUNA/RUNB encoded is equal to the block size (post- the initial RLE), viz, 900k, so bounding N at 2- million should guard against overflow without- rejecting any legitimate inputs. */- if (N >= 2*1024*1024) RETURN(BZ_DATA_ERROR);- if (nextSym == BZ_RUNA) es = es + (0+1) * N; else- if (nextSym == BZ_RUNB) es = es + (1+1) * N;- N = N * 2;- GET_MTF_VAL(BZ_X_MTF_3, BZ_X_MTF_4, nextSym);- }- while (nextSym == BZ_RUNA || nextSym == BZ_RUNB);-- es++;- uc = s->seqToUnseq[ s->mtfa[s->mtfbase[0]] ];- s->unzftab[uc] += es;-- if (s->smallDecompress)- while (es > 0) {- if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR);- s->ll16[nblock] = (UInt16)uc;- nblock++;- es--;- }- else- while (es > 0) {- if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR);- s->tt[nblock] = (UInt32)uc;- nblock++;- es--;- };-- continue;-- } else {-- if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR);-- /*-- uc = MTF ( nextSym-1 ) --*/- {- Int32 ii, jj, kk, pp, lno, off;- UInt32 nn;- nn = (UInt32)(nextSym - 1);-- if (nn < MTFL_SIZE) {- /* avoid general-case expense */- pp = s->mtfbase[0];- uc = s->mtfa[pp+nn];- while (nn > 3) {- Int32 z = pp+nn;- s->mtfa[(z) ] = s->mtfa[(z)-1];- s->mtfa[(z)-1] = s->mtfa[(z)-2];- s->mtfa[(z)-2] = s->mtfa[(z)-3];- s->mtfa[(z)-3] = s->mtfa[(z)-4];- nn -= 4;- }- while (nn > 0) { - s->mtfa[(pp+nn)] = s->mtfa[(pp+nn)-1]; nn--; - };- s->mtfa[pp] = uc;- } else { - /* general case */- lno = nn / MTFL_SIZE;- off = nn % MTFL_SIZE;- pp = s->mtfbase[lno] + off;- uc = s->mtfa[pp];- while (pp > s->mtfbase[lno]) { - s->mtfa[pp] = s->mtfa[pp-1]; pp--; - };- s->mtfbase[lno]++;- while (lno > 0) {- s->mtfbase[lno]--;- s->mtfa[s->mtfbase[lno]] - = s->mtfa[s->mtfbase[lno-1] + MTFL_SIZE - 1];- lno--;- }- s->mtfbase[0]--;- s->mtfa[s->mtfbase[0]] = uc;- if (s->mtfbase[0] == 0) {- kk = MTFA_SIZE-1;- for (ii = 256 / MTFL_SIZE-1; ii >= 0; ii--) {- for (jj = MTFL_SIZE-1; jj >= 0; jj--) {- s->mtfa[kk] = s->mtfa[s->mtfbase[ii] + jj];- kk--;- }- s->mtfbase[ii] = kk + 1;- }- }- }- }- /*-- end uc = MTF ( nextSym-1 ) --*/-- s->unzftab[s->seqToUnseq[uc]]++;- if (s->smallDecompress)- s->ll16[nblock] = (UInt16)(s->seqToUnseq[uc]); else- s->tt[nblock] = (UInt32)(s->seqToUnseq[uc]);- nblock++;-- GET_MTF_VAL(BZ_X_MTF_5, BZ_X_MTF_6, nextSym);- continue;- }- }-- /* Now we know what nblock is, we can do a better sanity- check on s->origPtr.- */- if (s->origPtr < 0 || s->origPtr >= nblock)- RETURN(BZ_DATA_ERROR);-- /*-- Set up cftab to facilitate generation of T^(-1) --*/- /* Check: unzftab entries in range. */- for (i = 0; i <= 255; i++) {- if (s->unzftab[i] < 0 || s->unzftab[i] > nblock)- RETURN(BZ_DATA_ERROR);- }- /* Actually generate cftab. */- s->cftab[0] = 0;- for (i = 1; i <= 256; i++) s->cftab[i] = s->unzftab[i-1];- for (i = 1; i <= 256; i++) s->cftab[i] += s->cftab[i-1];- /* Check: cftab entries in range. */- for (i = 0; i <= 256; i++) {- if (s->cftab[i] < 0 || s->cftab[i] > nblock) {- /* s->cftab[i] can legitimately be == nblock */- RETURN(BZ_DATA_ERROR);- }- }- /* Check: cftab entries non-descending. */- for (i = 1; i <= 256; i++) {- if (s->cftab[i-1] > s->cftab[i]) {- RETURN(BZ_DATA_ERROR);- }- }-- s->state_out_len = 0;- s->state_out_ch = 0;- BZ_INITIALISE_CRC ( s->calculatedBlockCRC );- s->state = BZ_X_OUTPUT;- if (s->verbosity >= 2) VPrintf0 ( "rt+rld" );-- if (s->smallDecompress) {-- /*-- Make a copy of cftab, used in generation of T --*/- for (i = 0; i <= 256; i++) s->cftabCopy[i] = s->cftab[i];-- /*-- compute the T vector --*/- for (i = 0; i < nblock; i++) {- uc = (UChar)(s->ll16[i]);- SET_LL(i, s->cftabCopy[uc]);- s->cftabCopy[uc]++;- }-- /*-- Compute T^(-1) by pointer reversal on T --*/- i = s->origPtr;- j = GET_LL(i);- do {- Int32 tmp = GET_LL(j);- SET_LL(j, i);- i = j;- j = tmp;- }- while (i != s->origPtr);-- s->tPos = s->origPtr;- s->nblock_used = 0;- if (s->blockRandomised) {- BZ_RAND_INIT_MASK;- BZ_GET_SMALL(s->k0); s->nblock_used++;- BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK; - } else {- BZ_GET_SMALL(s->k0); s->nblock_used++;- }-- } else {-- /*-- compute the T^(-1) vector --*/- for (i = 0; i < nblock; i++) {- uc = (UChar)(s->tt[i] & 0xff);- s->tt[s->cftab[uc]] |= (i << 8);- s->cftab[uc]++;- }-- s->tPos = s->tt[s->origPtr] >> 8;- s->nblock_used = 0;- if (s->blockRandomised) {- BZ_RAND_INIT_MASK;- BZ_GET_FAST(s->k0); s->nblock_used++;- BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK; - } else {- BZ_GET_FAST(s->k0); s->nblock_used++;- }-- }-- RETURN(BZ_OK);---- endhdr_2:-- GET_UCHAR(BZ_X_ENDHDR_2, uc);- if (uc != 0x72) RETURN(BZ_DATA_ERROR);- GET_UCHAR(BZ_X_ENDHDR_3, uc);- if (uc != 0x45) RETURN(BZ_DATA_ERROR);- GET_UCHAR(BZ_X_ENDHDR_4, uc);- if (uc != 0x38) RETURN(BZ_DATA_ERROR);- GET_UCHAR(BZ_X_ENDHDR_5, uc);- if (uc != 0x50) RETURN(BZ_DATA_ERROR);- GET_UCHAR(BZ_X_ENDHDR_6, uc);- if (uc != 0x90) RETURN(BZ_DATA_ERROR);-- s->storedCombinedCRC = 0;- GET_UCHAR(BZ_X_CCRC_1, uc);- s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);- GET_UCHAR(BZ_X_CCRC_2, uc);- s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);- GET_UCHAR(BZ_X_CCRC_3, uc);- s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);- GET_UCHAR(BZ_X_CCRC_4, uc);- s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);-- s->state = BZ_X_IDLE;- RETURN(BZ_STREAM_END);-- default: AssertH ( False, 4001 );- }-- AssertH ( False, 4002 );-- save_state_and_return:-- s->save_i = i;- s->save_j = j;- s->save_t = t;- s->save_alphaSize = alphaSize;- s->save_nGroups = nGroups;- s->save_nSelectors = nSelectors;- s->save_EOB = EOB;- s->save_groupNo = groupNo;- s->save_groupPos = groupPos;- s->save_nextSym = nextSym;- s->save_nblockMAX = nblockMAX;- s->save_nblock = nblock;- s->save_es = es;- s->save_N = N;- s->save_curr = curr;- s->save_zt = zt;- s->save_zn = zn;- s->save_zvec = zvec;- s->save_zj = zj;- s->save_gSel = gSel;- s->save_gMinlen = gMinlen;- s->save_gLimit = gLimit;- s->save_gBase = gBase;- s->save_gPerm = gPerm;-- return retVal; -}---/*-------------------------------------------------------------*/-/*--- end decompress.c ---*/-/*-------------------------------------------------------------*/
− cbits/huffman.c
@@ -1,205 +0,0 @@--/*-------------------------------------------------------------*/-/*--- Huffman coding low-level stuff ---*/-/*--- huffman.c ---*/-/*-------------------------------------------------------------*/--/* ------------------------------------------------------------------- This file is part of bzip2/libbzip2, a program and library for- lossless, block-sorting data compression.-- bzip2/libbzip2 version 1.0.6 of 6 September 2010- Copyright (C) 1996-2010 Julian Seward <jseward@bzip.org>-- Please read the WARNING, DISCLAIMER and PATENTS sections in the - README file.-- This program is released under the terms of the license contained- in the file LICENSE.- ------------------------------------------------------------------ */---#include "bzlib_private.h"--/*---------------------------------------------------*/-#define WEIGHTOF(zz0) ((zz0) & 0xffffff00)-#define DEPTHOF(zz1) ((zz1) & 0x000000ff)-#define MYMAX(zz2,zz3) ((zz2) > (zz3) ? (zz2) : (zz3))--#define ADDWEIGHTS(zw1,zw2) \- (WEIGHTOF(zw1)+WEIGHTOF(zw2)) | \- (1 + MYMAX(DEPTHOF(zw1),DEPTHOF(zw2)))--#define UPHEAP(z) \-{ \- Int32 zz, tmp; \- zz = z; tmp = heap[zz]; \- while (weight[tmp] < weight[heap[zz >> 1]]) { \- heap[zz] = heap[zz >> 1]; \- zz >>= 1; \- } \- heap[zz] = tmp; \-}--#define DOWNHEAP(z) \-{ \- Int32 zz, yy, tmp; \- zz = z; tmp = heap[zz]; \- while (True) { \- yy = zz << 1; \- if (yy > nHeap) break; \- if (yy < nHeap && \- weight[heap[yy+1]] < weight[heap[yy]]) \- yy++; \- if (weight[tmp] < weight[heap[yy]]) break; \- heap[zz] = heap[yy]; \- zz = yy; \- } \- heap[zz] = tmp; \-}---/*---------------------------------------------------*/-void BZ2_hbMakeCodeLengths ( UChar *len, - Int32 *freq,- Int32 alphaSize,- Int32 maxLen )-{- /*--- Nodes and heap entries run from 1. Entry 0- for both the heap and nodes is a sentinel.- --*/- Int32 nNodes, nHeap, n1, n2, i, j, k;- Bool tooLong;-- Int32 heap [ BZ_MAX_ALPHA_SIZE + 2 ];- Int32 weight [ BZ_MAX_ALPHA_SIZE * 2 ];- Int32 parent [ BZ_MAX_ALPHA_SIZE * 2 ]; -- for (i = 0; i < alphaSize; i++)- weight[i+1] = (freq[i] == 0 ? 1 : freq[i]) << 8;-- while (True) {-- nNodes = alphaSize;- nHeap = 0;-- heap[0] = 0;- weight[0] = 0;- parent[0] = -2;-- for (i = 1; i <= alphaSize; i++) {- parent[i] = -1;- nHeap++;- heap[nHeap] = i;- UPHEAP(nHeap);- }-- AssertH( nHeap < (BZ_MAX_ALPHA_SIZE+2), 2001 );- - while (nHeap > 1) {- n1 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1);- n2 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1);- nNodes++;- parent[n1] = parent[n2] = nNodes;- weight[nNodes] = ADDWEIGHTS(weight[n1], weight[n2]);- parent[nNodes] = -1;- nHeap++;- heap[nHeap] = nNodes;- UPHEAP(nHeap);- }-- AssertH( nNodes < (BZ_MAX_ALPHA_SIZE * 2), 2002 );-- tooLong = False;- for (i = 1; i <= alphaSize; i++) {- j = 0;- k = i;- while (parent[k] >= 0) { k = parent[k]; j++; }- len[i-1] = j;- if (j > maxLen) tooLong = True;- }- - if (! tooLong) break;-- /* 17 Oct 04: keep-going condition for the following loop used- to be 'i < alphaSize', which missed the last element,- theoretically leading to the possibility of the compressor- looping. However, this count-scaling step is only needed if- one of the generated Huffman code words is longer than- maxLen, which up to and including version 1.0.2 was 20 bits,- which is extremely unlikely. In version 1.0.3 maxLen was- changed to 17 bits, which has minimal effect on compression- ratio, but does mean this scaling step is used from time to- time, enough to verify that it works.-- This means that bzip2-1.0.3 and later will only produce- Huffman codes with a maximum length of 17 bits. However, in- order to preserve backwards compatibility with bitstreams- produced by versions pre-1.0.3, the decompressor must still- handle lengths of up to 20. */-- for (i = 1; i <= alphaSize; i++) {- j = weight[i] >> 8;- j = 1 + (j / 2);- weight[i] = j << 8;- }- }-}---/*---------------------------------------------------*/-void BZ2_hbAssignCodes ( Int32 *code,- UChar *length,- Int32 minLen,- Int32 maxLen,- Int32 alphaSize )-{- Int32 n, vec, i;-- vec = 0;- for (n = minLen; n <= maxLen; n++) {- for (i = 0; i < alphaSize; i++)- if (length[i] == n) { code[i] = vec; vec++; };- vec <<= 1;- }-}---/*---------------------------------------------------*/-void BZ2_hbCreateDecodeTables ( Int32 *limit,- Int32 *base,- Int32 *perm,- UChar *length,- Int32 minLen,- Int32 maxLen,- Int32 alphaSize )-{- Int32 pp, i, j, vec;-- pp = 0;- for (i = minLen; i <= maxLen; i++)- for (j = 0; j < alphaSize; j++)- if (length[j] == i) { perm[pp] = j; pp++; };-- for (i = 0; i < BZ_MAX_CODE_LEN; i++) base[i] = 0;- for (i = 0; i < alphaSize; i++) base[length[i]+1]++;-- for (i = 1; i < BZ_MAX_CODE_LEN; i++) base[i] += base[i-1];-- for (i = 0; i < BZ_MAX_CODE_LEN; i++) limit[i] = 0;- vec = 0;-- for (i = minLen; i <= maxLen; i++) {- vec += (base[i+1] - base[i]);- limit[i] = vec-1;- vec <<= 1;- }- for (i = minLen + 1; i <= maxLen; i++)- base[i] = ((limit[i-1] + 1) << 1) - base[i];-}---/*-------------------------------------------------------------*/-/*--- end huffman.c ---*/-/*-------------------------------------------------------------*/
− cbits/randtable.c
@@ -1,84 +0,0 @@--/*-------------------------------------------------------------*/-/*--- Table for randomising repetitive blocks ---*/-/*--- randtable.c ---*/-/*-------------------------------------------------------------*/--/* ------------------------------------------------------------------- This file is part of bzip2/libbzip2, a program and library for- lossless, block-sorting data compression.-- bzip2/libbzip2 version 1.0.6 of 6 September 2010- Copyright (C) 1996-2010 Julian Seward <jseward@bzip.org>-- Please read the WARNING, DISCLAIMER and PATENTS sections in the - README file.-- This program is released under the terms of the license contained- in the file LICENSE.- ------------------------------------------------------------------ */---#include "bzlib_private.h"---/*---------------------------------------------*/-Int32 BZ2_rNums[512] = { - 619, 720, 127, 481, 931, 816, 813, 233, 566, 247, - 985, 724, 205, 454, 863, 491, 741, 242, 949, 214, - 733, 859, 335, 708, 621, 574, 73, 654, 730, 472, - 419, 436, 278, 496, 867, 210, 399, 680, 480, 51, - 878, 465, 811, 169, 869, 675, 611, 697, 867, 561, - 862, 687, 507, 283, 482, 129, 807, 591, 733, 623, - 150, 238, 59, 379, 684, 877, 625, 169, 643, 105, - 170, 607, 520, 932, 727, 476, 693, 425, 174, 647, - 73, 122, 335, 530, 442, 853, 695, 249, 445, 515, - 909, 545, 703, 919, 874, 474, 882, 500, 594, 612, - 641, 801, 220, 162, 819, 984, 589, 513, 495, 799, - 161, 604, 958, 533, 221, 400, 386, 867, 600, 782, - 382, 596, 414, 171, 516, 375, 682, 485, 911, 276, - 98, 553, 163, 354, 666, 933, 424, 341, 533, 870, - 227, 730, 475, 186, 263, 647, 537, 686, 600, 224, - 469, 68, 770, 919, 190, 373, 294, 822, 808, 206, - 184, 943, 795, 384, 383, 461, 404, 758, 839, 887, - 715, 67, 618, 276, 204, 918, 873, 777, 604, 560, - 951, 160, 578, 722, 79, 804, 96, 409, 713, 940, - 652, 934, 970, 447, 318, 353, 859, 672, 112, 785, - 645, 863, 803, 350, 139, 93, 354, 99, 820, 908, - 609, 772, 154, 274, 580, 184, 79, 626, 630, 742, - 653, 282, 762, 623, 680, 81, 927, 626, 789, 125, - 411, 521, 938, 300, 821, 78, 343, 175, 128, 250, - 170, 774, 972, 275, 999, 639, 495, 78, 352, 126, - 857, 956, 358, 619, 580, 124, 737, 594, 701, 612, - 669, 112, 134, 694, 363, 992, 809, 743, 168, 974, - 944, 375, 748, 52, 600, 747, 642, 182, 862, 81, - 344, 805, 988, 739, 511, 655, 814, 334, 249, 515, - 897, 955, 664, 981, 649, 113, 974, 459, 893, 228, - 433, 837, 553, 268, 926, 240, 102, 654, 459, 51, - 686, 754, 806, 760, 493, 403, 415, 394, 687, 700, - 946, 670, 656, 610, 738, 392, 760, 799, 887, 653, - 978, 321, 576, 617, 626, 502, 894, 679, 243, 440, - 680, 879, 194, 572, 640, 724, 926, 56, 204, 700, - 707, 151, 457, 449, 797, 195, 791, 558, 945, 679, - 297, 59, 87, 824, 713, 663, 412, 693, 342, 606, - 134, 108, 571, 364, 631, 212, 174, 643, 304, 329, - 343, 97, 430, 751, 497, 314, 983, 374, 822, 928, - 140, 206, 73, 263, 980, 736, 876, 478, 430, 305, - 170, 514, 364, 692, 829, 82, 855, 953, 676, 246, - 369, 970, 294, 750, 807, 827, 150, 790, 288, 923, - 804, 378, 215, 828, 592, 281, 565, 555, 710, 82, - 896, 831, 547, 261, 524, 462, 293, 465, 502, 56, - 661, 821, 976, 991, 658, 869, 905, 758, 745, 193, - 768, 550, 608, 933, 378, 286, 215, 979, 792, 961, - 61, 688, 793, 644, 986, 403, 106, 366, 905, 644, - 372, 567, 466, 434, 645, 210, 389, 550, 919, 135, - 780, 773, 635, 389, 707, 100, 626, 958, 165, 504, - 920, 176, 193, 713, 857, 265, 203, 50, 668, 108, - 645, 990, 626, 197, 510, 357, 358, 850, 858, 364, - 936, 638-};---/*-------------------------------------------------------------*/-/*--- end randtable.c ---*/-/*-------------------------------------------------------------*/
− examples/bunzip2.hs
@@ -1,6 +0,0 @@-module Main where--import qualified Data.ByteString.Lazy as B-import qualified Codec.Compression.BZip as BZip--main = B.interact BZip.decompress
− examples/bzip2.hs
@@ -1,6 +0,0 @@-module Main where--import qualified Data.ByteString.Lazy as B-import qualified Codec.Compression.BZip as BZip--main = B.interact BZip.compress
+ test/Test.hs view
@@ -0,0 +1,32 @@+{-# LANGUAGE CPP #-}++module Main where++import Codec.Compression.BZip.Internal++import Test.Codec.Compression.BZip.Internal ()+import Test.Codec.Compression.BZip.Stream ()++import Test.QuickCheck+import Test.Tasty+import Test.Tasty.QuickCheck+import Utils ()++import Control.Monad+++main :: IO ()+main = defaultMain $+ testGroup "bzip tests" [+ testGroup "property tests" [+ testProperty "decompress . compress = id (standard)" prop_decompress_after_compress+ ]+ ]+++prop_decompress_after_compress :: CompressParams+ -> DecompressParams+ -> Property+prop_decompress_after_compress cp dp =+ decompressBufferSize dp > 0 && compressBufferSize cp > 0 ==>+ liftM2 (==) (decompress dp . compress cp) id
+ test/Test/Codec/Compression/BZip/Internal.hs view
@@ -0,0 +1,28 @@+{-# OPTIONS_GHC -fno-warn-orphans #-}++-- | Test code and properties for "Codec.Compression.BZib.Internal"+--+module Test.Codec.Compression.BZip.Internal where++import Codec.Compression.BZip.Internal+import Test.Codec.Compression.BZip.Stream ()+import Test.QuickCheck++import Control.Monad (ap)+++instance Arbitrary CompressParams where+ arbitrary = return CompressParams `ap` arbitrary `ap` arbitrary `ap` arbitrary+++arbitraryBufferSize :: Gen Int+arbitraryBufferSize = frequency $ [(10, return n) | n <- [1..1024]] +++ [(20, return n) | n <- [1025..8192]] +++ [(40, return n) | n <- [8193..131072]] +++ [(1, return n) | n <- [131072..1048576]]+++instance Arbitrary DecompressParams where+ arbitrary = return DecompressParams `ap` arbitrary+ `ap` arbitraryBufferSize+
+ test/Test/Codec/Compression/BZip/Stream.hs view
@@ -0,0 +1,20 @@+{-# OPTIONS_GHC -fno-warn-orphans #-}++-- | Test code and properties for "Codec.Compression.BZip.Stream"+--+module Test.Codec.Compression.BZip.Stream where++import Codec.Compression.BZip.Internal+import Test.QuickCheck+++instance Arbitrary BlockSize where+ arbitrary = elements $ DefaultBlockSize : map BlockSize [1 .. 9]+++instance Arbitrary MemoryLevel where+ arbitrary = elements [DefaultMemoryLevel, MinMemoryLevel]+++instance Arbitrary WorkFactor where+ arbitrary = elements $ DefaultWorkFactor : map WorkFactor [1 .. 250]
+ test/Utils.hs view
@@ -0,0 +1,28 @@+{-# OPTIONS_GHC -fno-warn-orphans #-}+module Utils where++import qualified Data.ByteString.Lazy as BL+import qualified Data.ByteString as BS++import Test.QuickCheck++-------------------+-- QuickCheck Utils++maxStrSize :: Double+maxStrSize = 500++-- convert a QC size parameter into one for generating long lists,+-- growing inverse exponentially up to maxStrSize+strSize :: Int -> Int+strSize n = floor (maxStrSize * (1 - 2 ** (-fromIntegral n/100)))++instance Arbitrary BL.ByteString where+ arbitrary = sized $ \sz -> fmap BL.fromChunks $ listOf $ resize (sz `div` 2) arbitrary+ shrink = map BL.pack . shrink . BL.unpack++instance Arbitrary BS.ByteString where+ arbitrary = sized $ \sz -> resize (strSize sz) $ fmap BS.pack $ listOf $ arbitrary+ shrink = map BS.pack . shrink . BS.unpack++