pure-zlib 0.4 → 0.8.0
raw patch · 31 files changed
Files
- Benchmark.hs +87/−0
- Deflate.hs +45/−16
- Setup.hs +1/−0
- pure-zlib.cabal +56/−18
- src/Codec/Compression/Zlib.hs +66/−22
- src/Codec/Compression/Zlib/Adler32.hs +46/−23
- src/Codec/Compression/Zlib/Deflate.hs +249/−199
- src/Codec/Compression/Zlib/HuffmanTree.hs +75/−40
- src/Codec/Compression/Zlib/Monad.hs +336/−141
- src/Codec/Compression/Zlib/OutputWindow.hs +99/−54
- test/Test.hs +110/−42
- test/test-cases/randtest1.gold binary
- test/test-cases/randtest1.z binary
- test/test-cases/randtest2.gold binary
- test/test-cases/randtest2.z binary
- test/test-cases/randtest3.gold binary
- test/test-cases/randtest3.z binary
- test/test-cases/rfctest1.gold +808/−0
- test/test-cases/rfctest1.z binary
- test/test-cases/rfctest2.gold +1146/−0
- test/test-cases/rfctest2.z binary
- test/test-cases/rfctest3.gold +864/−0
- test/test-cases/rfctest3.z binary
- test/test-cases/tor-list.gold too large to diff
- test/test-cases/tor-list.z too large to diff
- test/test-cases/zerotest1.gold binary
- test/test-cases/zerotest1.z binary
- test/test-cases/zerotest2.gold binary
- test/test-cases/zerotest2.z binary
- test/test-cases/zerotest3.gold binary
- test/test-cases/zerotest3.z binary
+ Benchmark.hs view
@@ -0,0 +1,87 @@+import qualified CZlib+import qualified CZlib.Internal as CZlibIncremental+import qualified PureZlib++import qualified Control.Monad.ST.Lazy as CM+import Criterion.Main+import qualified Data.ByteString as S+import qualified Data.ByteString.Lazy as L+import qualified GHC.ST as GHC+import Prelude hiding (readFile, writeFile)++testCases :: [String]+testCases =+ [ "randtest1"+ , "randtest2"+ , "randtest3"+ , "rfctest1"+ , "rfctest2"+ , "rfctest3"+ , "zerotest1"+ , "zerotest2"+ , "zerotest3"+ , "tor-list"+ ]++main :: IO ()+main =+ defaultMain+ [ bgroup "decompression" $+ flip fmap testCases $+ \tc -> env (getFiles tc) $+ \ ~(zbstr, _) ->+ bgroup+ tc+ [ bgroup+ "normal"+ [ bench "pure-zlib" $ whnf PureZlib.decompress zbstr+ , bench "zlib" $ whnf CZlib.decompress zbstr+ ]+ , bgroup+ "incremental"+ [ bench "pure-zlib" $ whnf decompressIncrementalPure zbstr+ , bench "zlib" $ whnf decompressIncrementalC zbstr+ ]+ ]+ ]+ where+ getFiles tc = do+ zbstr <- L.readFile $ "test/test-cases/" ++ tc ++ ".z"+ goldbstr <- L.readFile $ "test/test-cases/" ++ tc ++ ".gold"+ pure (zbstr, goldbstr)++decompressIncrementalPure :: L.ByteString -> L.ByteString+decompressIncrementalPure input = GHC.runST $ do+ initialState <- PureZlib.decompressIncremental+ go initialState (L.toChunks input) []+ where+ go decoder ls chunks =+ case decoder of+ PureZlib.NeedMore f+ | (x : rest) <- ls -> do+ nextState <- f x+ go nextState rest chunks+ | otherwise -> error "ERROR: Ran out of data mid-decompression."+ PureZlib.Chunk c m -> do+ nextState <- m+ go nextState ls (c : chunks)+ PureZlib.Done | not (null ls) -> error "ERROR: Finished decompression with data left."+ PureZlib.Done | otherwise -> return (L.fromChunks (reverse chunks))+ PureZlib.DecompError e -> error ("ERROR: " ++ show e)++decompressIncrementalC :: L.ByteString -> L.ByteString+decompressIncrementalC input = CM.runST $ go (CZlibIncremental.decompressST CZlibIncremental.zlibFormat CZlibIncremental.defaultDecompressParams) (L.toChunks input) []+ where+ go decoder ls chunks = case decoder of+ CZlibIncremental.DecompressInputRequired f+ | (x : rest) <- ls -> do+ next <- f x+ go next rest chunks+ | otherwise -> error "ERROR: Ran out of data mid-decompression."+ CZlibIncremental.DecompressOutputAvailable c kont -> do+ next <- kont+ go next ls (c : chunks)+ CZlibIncremental.DecompressStreamEnd leftovers+ | not (S.null leftovers) -> error "ERROR: Finished decompression with data left."+ | otherwise -> pure $ L.fromChunks $ reverse chunks+ CZlibIncremental.DecompressStreamError e -> error ("ERROR: " ++ show e)
Deflate.hs view
@@ -1,19 +1,48 @@-import Codec.Compression.Zlib(decompress)-import Data.ByteString.Lazy(readFile, writeFile)-import Data.List(isSuffixOf)+{-# LANGUAGE RankNTypes #-}++import Codec.Compression.Zlib (ZlibDecoder (..), decompressIncremental)+import Control.Monad (unless)+import qualified Data.ByteString as S+import qualified Data.ByteString.Lazy as L+import Data.List (isSuffixOf)+import GHC.IO (stToIO)+import GHC.Prim (RealWorld)+import GHC.ST (ST)+import System.Environment (getArgs)+import System.IO (Handle, IOMode (..), hClose, openFile) import Prelude hiding (readFile, writeFile)-import System.Environment main :: IO ()-main =- do args <- getArgs- case args of- [ifile] ->- if ".z" `isSuffixOf` ifile- then do bstr <- readFile ifile- case decompress bstr of- Nothing -> putStrLn "Decompression failure."- Just o -> writeFile (take (length ifile - 2) ifile) o- else putStrLn "Unexpected file name."- _ ->- putStrLn "USAGE: deflate [filename]"+main = do+ args <- getArgs+ case args of+ [ifile] ->+ if ".z" `isSuffixOf` ifile+ then do+ bstr <- L.readFile ifile+ let outname = take (length ifile - 2) ifile+ hndl <- openFile outname WriteMode+ runDecompression hndl (L.toChunks bstr) decompressIncremental+ else putStrLn "Unexpected file name."+ _ ->+ putStrLn "USAGE: deflate [filename]"++runDecompression :: Handle -> [S.ByteString] -> ST RealWorld (ZlibDecoder RealWorld) -> IO ()+runDecompression hndl ls decoder = do+ nextState <- stToIO decoder+ case nextState of+ Done -> do+ unless (null ls) $+ putStrLn "WARNING: Finished decompression with data left."+ hClose hndl+ DecompError e -> do+ putStrLn ("ERROR: " ++ show e)+ hClose hndl+ NeedMore f+ | (x : rest) <- ls -> runDecompression hndl rest (f x)+ | otherwise -> do+ putStrLn "ERROR: Ran out of data mid-decompression."+ hClose hndl+ Chunk c m -> do+ S.hPut hndl c+ runDecompression hndl ls m
Setup.hs view
@@ -1,2 +1,3 @@ import Distribution.Simple+ main = defaultMain
pure-zlib.cabal view
@@ -1,5 +1,6 @@+cabal-version: 2.0 name: pure-zlib-version: 0.4+version: 0.8.0 synopsis: A Haskell-only implementation of zlib / DEFLATE homepage: http://github.com/GaloisInc/pure-zlib license: BSD3@@ -8,21 +9,34 @@ maintainer: awick@galois.com category: Codec build-type: Simple-cabal-version: >=1.10 description: A Haskell-only implementation of the zlib / DEFLATE protocol. Currently only implements the decompression algorithm.+extra-source-files: test/test-cases/*.z,+ test/test-cases/*.gold+tested-with:+ GHC==8.0.2,+ GHC==8.2.2,+ GHC==8.4.4,+ GHC==8.6.5,+ GHC==8.8.4,+ GHC==8.10.4 library default-language: Haskell2010 ghc-options: -Wall hs-source-dirs: src build-depends:- base >= 4.7 && < 5.0,- bytestring >= 0.10 && < 0.11,- containers >= 0.5 && < 0.7,- fingertree >= 0.1 && < 0.3,- monadLib >= 3.7 && < 3.9+ array >= 0.4 && < 0.9,+ base >= 4.6 && < 5.0,+ base-compat >= 0.9.1 && < 0.12,+ bytestring >= 0.10 && < 0.11,+ bytestring-builder >= 0.10 && < 0.11,+ containers >= 0.5 && < 0.7,+ vector,+ primitive+ if !impl(ghc >= 8.0)+ build-depends: semigroups == 0.18.* exposed-modules: Codec.Compression.Zlib, Codec.Compression.Zlib.Adler32,@@ -32,6 +46,8 @@ Codec.Compression.Zlib.OutputWindow default-extensions: BangPatterns,+ DeriveDataTypeable,+ GeneralizedNewtypeDeriving, MultiParamTypeClasses, MultiWayIf @@ -40,9 +56,11 @@ main-is: Deflate.hs ghc-options: -Wall build-depends:- base >= 4.7 && < 5.0,- bytestring >= 0.10 && < 0.11,- pure-zlib >= 0.3 && < 0.5+ base >= 4.6 && < 5.0,+ base-compat >= 0.9.1 && < 0.12,+ bytestring >= 0.10 && < 0.11,+ ghc-prim,+ pure-zlib test-suite test-zlib type: exitcode-stdio-1.0@@ -52,14 +70,34 @@ default-language: Haskell2010 ghc-options: -fno-warn-orphans build-depends:- base >= 4.7 && < 5.0,- bytestring >= 0.10 && < 0.11,- pure-zlib >= 0.3 && < 1.1,- HUnit >= 1.2 && < 1.4,- QuickCheck >= 2.7 && < 2.9,- test-framework >= 0.8 && < 0.10,- test-framework-hunit >= 0.3 && < 0.5,- test-framework-quickcheck2 >= 0.3 && < 0.5+ base >= 4.6 && < 5.0,+ base-compat >= 0.9.1 && < 0.12,+ bytestring >= 0.10 && < 0.11,+ filepath >= 1.4.1 && < 1.6,+ HUnit >= 1.2 && < 1.7,+ QuickCheck >= 2.7 && < 2.14,+ pure-zlib,+ tasty >= 0.11.0.4 && < 1.3,+ tasty-hunit >= 0.9.2 && < 0.11,+ tasty-quickcheck >= 0.8.4 && < 0.11++benchmark bench-zlib+ type: exitcode-stdio-1.0+ main-is: Benchmark.hs+ default-language: Haskell2010+ ghc-options: -Wall+ build-depends:+ base >= 4.6 && < 5.0,+ base-compat >= 0.9.1 && < 0.12,+ bytestring >= 0.10 && < 0.11,+ criterion >= 1.5, + pure-zlib,+ zlib,+ time >= 1.4.2 && < 1.11+ mixins:+ pure-zlib (Codec.Compression.Zlib as PureZlib),+ zlib (Codec.Compression.Zlib as CZlib),+ zlib (Codec.Compression.Zlib.Internal as CZlib.Internal) source-repository head type: git
src/Codec/Compression/Zlib.hs view
@@ -1,25 +1,69 @@ {-# LANGUAGE MultiWayIf #-}-module Codec.Compression.Zlib(- decompress- )- where -import Codec.Compression.Zlib.Deflate-import Codec.Compression.Zlib.Monad-import Data.Bits-import Data.ByteString.Lazy(ByteString)-import qualified Data.ByteString.Lazy as BS+module Codec.Compression.Zlib (+ DecompressionError (..),+ ZlibDecoder (NeedMore, Chunk, Done, DecompError),+ decompress,+ decompressIncremental,+) where -decompress :: ByteString -> Maybe ByteString-decompress ifile =- case BS.uncons ifile of- Nothing -> error "Could not read CMF."- Just (cmf, rest) ->- case BS.uncons rest of- Nothing -> error "Could not read FLG."- Just (_, rest') ->- let cm = cmf .&. 0x0F- cinfo = cmf `shiftR` 4- in if| cm /= 8 -> error "Non-DEFLATE compression method."- | cinfo > 7 -> error "Window size too big."- | otherwise -> runDeflateM inflate rest'+import Codec.Compression.Zlib.Deflate (inflate)+import Codec.Compression.Zlib.Monad (+ DecompressionError (..),+ DeflateM,+ ZlibDecoder (..),+ nextByte,+ raise,+ runDeflateM,+ )+import Control.Monad (replicateM_, unless, when)+import Data.Bits (shiftL, shiftR, testBit, (.&.), (.|.))+import qualified Data.ByteString as S+import Data.ByteString.Builder (Builder, byteString, toLazyByteString)+import qualified Data.ByteString.Lazy as L+import Data.Word (Word16)+import GHC.ST (ST, runST)+import Prelude.Compat+import Prelude ()++decompressIncremental :: ST s (ZlibDecoder s)+decompressIncremental = runDeflateM inflateWithHeaders++decompress :: L.ByteString -> Either DecompressionError L.ByteString+decompress ifile = runST $ do+ base <- decompressIncremental+ run base (L.toChunks ifile) mempty+ where+ run :: ZlibDecoder s -> [S.ByteString] -> Builder -> ST s (Either DecompressionError L.ByteString)+ run (NeedMore _) [] _ =+ return (Left (DecompressionError "Ran out of data mid-decompression 2."))+ run (NeedMore f) (first : rest) acc = do+ nextState <- f first+ run nextState rest acc+ run (Chunk c m) ls acc = do+ nextState <- m+ run nextState ls (acc <> byteString c)+ run Done [] acc =+ return (Right (toLazyByteString acc))+ run Done (_ : _) _ =+ return (Left (DecompressionError "Finished with data remaining."))+ run (DecompError e) _ _ =+ return (Left e)++inflateWithHeaders :: DeflateM s ()+inflateWithHeaders = do+ cmf <- nextByte+ flg <- nextByte+ let both = fromIntegral cmf `shiftL` 8 .|. fromIntegral flg+ cm = cmf .&. 0x0f+ cinfo = cmf `shiftR` 4+ fdict = testBit flg 5+ -- flevel = flg `shiftR` 6+ unless ((both :: Word16) `mod` 31 == 0) $+ raise (HeaderError "Header checksum failed")+ unless (cm == 8) $+ raise (HeaderError ("Bad compression method: " ++ show cm))+ unless (cinfo <= 7) $+ raise (HeaderError ("Window size too big: " ++ show cinfo))+ when fdict $ replicateM_ 4 nextByte -- just skip them for now (FIXME)+ inflate
src/Codec/Compression/Zlib/Adler32.hs view
@@ -1,34 +1,57 @@-module Codec.Compression.Zlib.Adler32(- AdlerState- , initialAdlerState- , advanceAdler- , finalizeAdler- )- where+{-# LANGUAGE BangPatterns #-}+{-# LANGUAGE MagicHash #-} -import Data.Bits-import Data.Word+module Codec.Compression.Zlib.Adler32 (+ AdlerState,+ initialAdlerState,+ advanceAdler,+ advanceAdlerBlock,+ finalizeAdler,+) where -data AdlerState = AdlerState { adlerA :: !Word16, adlerB :: !Word16 }+import Data.Bits (shiftL, (.|.))+import qualified Data.ByteString as S+import GHC.Exts (Word#, plusWord#, remWord#)+import GHC.Word (Word32 (..), Word8 (..)) +data AdlerState = AdlerState {_adlerA :: Word#, _adlerB :: Word#}+ initialAdlerState :: AdlerState-initialAdlerState = AdlerState 1 0+initialAdlerState = AdlerState 1## 0## -adlerAdd :: (Integral a, Integral b) => a -> b -> Word16-adlerAdd x y = fromIntegral ((x32 + y32) `mod` 65521)+advanceAdler :: AdlerState -> Word8 -> AdlerState+advanceAdler (AdlerState a b) (W8# v) = AdlerState a' b' where- x32, y32 :: Word32- x32 = fromIntegral x- y32 = fromIntegral y+ a' = (a `plusWord#` v) `remWord#` 65521##+ b' = (b `plusWord#` a') `remWord#` 65521##+{-# INLINE advanceAdler #-} -advanceAdler :: AdlerState -> Word8 -> AdlerState-advanceAdler state b = AdlerState a' b'+advanceNoMod :: AdlerState -> Word8 -> AdlerState+advanceNoMod (AdlerState a b) (W8# v) = AdlerState a' b' where- a' = adlerAdd (adlerA state) b- b' = adlerAdd (adlerB state) a'+ a' = a `plusWord#` v+ b' = b `plusWord#` a'+{-# INLINE advanceNoMod #-} -finalizeAdler :: AdlerState -> Word32-finalizeAdler state = ((fromIntegral (adlerB state)) `shiftL` 16)- .|. fromIntegral (adlerA state)+-- The block must be less than 5552 bytes long in this case+advanceAdlerLimited :: AdlerState -> S.ByteString -> AdlerState+advanceAdlerLimited !state !bl = AdlerState stateA' stateB'+ where+ !(AdlerState stateA stateB) = S.foldl' advanceNoMod state bl+ stateA' = stateA `remWord#` 65521##+ stateB' = stateB `remWord#` 65521## +advanceAdlerBlock :: AdlerState -> S.ByteString -> AdlerState+advanceAdlerBlock !state !bl+ | S.length bl == 0 = state+ | S.length bl == 1 = advanceAdler state (S.head bl)+ | S.length bl < 5552 = advanceAdlerLimited state bl+ | otherwise = advanceAdlerBlock (advanceAdlerBlock state first5551) rest+ where+ (!first5551, !rest) = S.splitAt 5551 bl +finalizeAdler :: AdlerState -> Word32+finalizeAdler (AdlerState a b) = high .|. low+ where+ high = (W32# b) `shiftL` 16+ low = W32# a
src/Codec/Compression/Zlib/Deflate.hs view
@@ -1,242 +1,292 @@ {-# LANGUAGE MultiWayIf #-}-module Codec.Compression.Zlib.Deflate(- inflate- , computeCodeValues- )- where -import Codec.Compression.Zlib.HuffmanTree-import Codec.Compression.Zlib.Monad-import Control.Monad-import Data.Bits-import Data.ByteString.Lazy(ByteString)-import qualified Data.ByteString.Lazy as BS-import Data.Int-import Data.List-import Data.Map.Strict(Map)-import qualified Data.Map.Strict as Map-import Data.Word+module Codec.Compression.Zlib.Deflate (+ inflate,+ computeCodeValues,+) where -inflate :: DeflateM (Maybe ByteString)-inflate =- do isFinal <- inflateBlock- if isFinal- then do advanceToByte- rest <- readRest- ourAdler <- finalAdler- result <- finalOutput- let theirAdler = BS.foldl shiftAdd 0 rest- if | BS.length rest /= 4 -> return Nothing- | theirAdler /= ourAdler -> return Nothing- | otherwise -> return (Just result)- else inflate- where shiftAdd x y = (x `shiftL` 8) .|. fromIntegral y+import Codec.Compression.Zlib.HuffmanTree (+ HuffmanTree,+ createHuffmanTree,+ )+import Codec.Compression.Zlib.Monad (+ DecompressionError (..),+ DeflateM,+ advanceToByte,+ emitBlock,+ emitByte,+ emitPastChunk,+ finalAdler,+ finalize,+ moveWindow,+ nextBits,+ nextBlock,+ nextCode,+ nextWord16,+ nextWord32,+ raise,+ )+import Control.Monad (replicateM, unless)+import Data.Array (Array, array, (!))+import Data.Bits (complement, shiftL)+import Data.Int (Int64)+import Data.IntMap.Strict (IntMap)+import qualified Data.IntMap.Strict as Map+import Data.List (sortBy)+import Data.Word (Word8)+import Numeric (showHex) -inflateBlock :: DeflateM Bool-inflateBlock =- do bfinal <- nextBit- btype <- nextBits 2- case btype :: Word8 of- 0 -> -- no compression- do advanceToByte- len <- nextWord16- nlen <- nextWord16- unless (len == complement nlen) $- fail "Len/nlen mismatch in uncompressed block."- emitBlock =<< nextBlock len- return bfinal- 1 -> -- compressed with fixed Huffman codes- do runInflate fixedLitTree fixedDistanceTree- return bfinal- 2 -> -- compressed with dynamic Huffman codes- do hlit <- (257+) `fmap` nextBits 5- hdist <- (1+) `fmap` nextBits 5- hclen <- (4+) `fmap` nextBits 4- codeLens <- replicateM hclen (nextBits 3)- let codeLens' = zip codeLengthOrder codeLens- codeTree = computeHuffmanTree codeLens'- lens <- getCodeLengths codeTree 0 (hlit + hdist) 0 Map.empty- -- We do this as a big chunk and then split it up because the spec- -- allows repeat codes to cross the hlit / hdist boundary. So now we- -- need to pull off the hdist items.- let (litlens, offdistlens) =- Map.partitionWithKey (\ k _ -> k < hlit) lens- distlens = Map.mapKeys (\ k -> k - hlit) offdistlens- litTree = computeHuffmanTree (Map.toList litlens)- distTree = computeHuffmanTree (Map.toList distlens)- runInflate litTree distTree- return bfinal- _ -> -- reserved / error- error ("Unacceptable BTYPE: " ++ show btype)+inflate :: DeflateM s ()+inflate = do+ fixedLit <- buildFixedLitTree+ fixedDist <- buildFixedDistanceTree+ go fixedLit fixedDist where- runInflate :: HuffmanTree Int -> HuffmanTree Int -> DeflateM ()- runInflate litTree distTree =- do code <- nextCode litTree- if | code < 256 -> do emitByte (fromIntegral code)- runInflate litTree distTree- | code == 256 -> return ()- | code > 256 -> do len <- getLength code- distCode <- nextCode distTree- dist <- getDistance distCode- emitPastChunk dist len- runInflate litTree distTree+ go fixedLit fixedDist = do+ isFinal <- inflateBlock fixedLit fixedDist+ moveWindow+ if isFinal+ then checkChecksum >> finalize+ else go fixedLit fixedDist+ --+ checkChecksum = do+ advanceToByte+ ourAdler <- finalAdler+ theirAdler <- nextWord32+ unless (theirAdler == ourAdler) $+ raise+ ( ChecksumError+ ( "checksum mismatch: " ++ showHex theirAdler ""+ ++ " != "+ ++ showHex ourAdler ""+ )+ ) +inflateBlock :: HuffmanTree Int -> HuffmanTree Int -> DeflateM s Bool+inflateBlock fixedLitTree fixedDistanceTree = do+ bfinal <- (== (1 :: Word8)) `fmap` nextBits 1+ btype <- nextBits 2+ case btype :: Word8 of+ 0 -> do+ -- no compression+ advanceToByte+ len <- nextWord16+ nlen <- nextWord16+ unless (len == complement nlen) $+ raise (FormatError "Len/nlen mismatch in uncompressed block.")+ emitBlock =<< nextBlock len+ return bfinal+ 1 -> do+ -- compressed with fixed Huffman codes+ runInflate fixedLitTree fixedDistanceTree+ return bfinal+ 2 -> do+ -- compressed with dynamic Huffman codes+ hlit <- (257 +) `fmap` nextBits 5+ hdist <- (1 +) `fmap` nextBits 5+ hclen <- (4 +) `fmap` nextBits 4+ codeLens <- replicateM hclen (nextBits 3)+ let codeLens' = zip codeLengthOrder codeLens+ codeTree <- computeHuffmanTree codeLens'+ lens <- getCodeLengths codeTree 0 (hlit + hdist) 0 Map.empty+ -- We do this as a big chunk and then split it up because the spec+ -- allows repeat codes to cross the hlit / hdist boundary. So now we+ -- need to pull off the hdist items.+ let (litlens, offdistlens) =+ Map.partitionWithKey (\k _ -> k < hlit) lens+ distlens = Map.mapKeys (\k -> k - hlit) offdistlens+ litTree <- computeHuffmanTree (Map.toList litlens)+ distTree <- computeHuffmanTree (Map.toList distlens)+ runInflate litTree distTree+ return bfinal+ _ ->+ -- reserved / error+ raise (FormatError ("Unacceptable BTYPE: " ++ show btype))+ where+ runInflate :: HuffmanTree Int -> HuffmanTree Int -> DeflateM s ()+ runInflate litTree distTree = do+ code <- nextCode litTree+ case compare code 256 of+ LT -> do+ emitByte (fromIntegral code)+ runInflate litTree distTree+ EQ -> return ()+ GT -> do+ len <- getLength code+ distCode <- nextCode distTree+ dist <- getDistance distCode+ emitPastChunk dist (fromIntegral len)+ moveWindow+ runInflate litTree distTree+ -- ----------------------------------------------------------------------------- -getCodeLengths :: HuffmanTree Int ->- Int -> Int -> Int ->- Map Int Int ->- DeflateM (Map Int Int)+getCodeLengths ::+ HuffmanTree Int ->+ Int ->+ Int ->+ Int ->+ IntMap Int ->+ DeflateM s (IntMap Int) getCodeLengths tree n maxl prev acc- | n >= maxl = return acc- | otherwise =- do code <- nextCode tree- if | code <= 15 ->- getCodeLengths tree (n+1) maxl code (Map.insert n code acc)- | code == 16 -> -- copy the previous code length 3 - 6 times- do num <- (3+) `fmap` nextBits 2- getCodeLengths tree (n+num) maxl prev (addNTimes n num prev acc)- | code == 17 -> -- repeat a code length of 0 for 3 - 10 times- do num <- (3+) `fmap` nextBits 3- getCodeLengths tree (n+num) maxl 0 (addNTimes n num 0 acc)- | code == 18 -> -- repeat a code length of 0 for 11 - 138 times- do num <- (11+) `fmap` nextBits 7- getCodeLengths tree (n+num) maxl 0 (addNTimes n num 0 acc)+ | n >= maxl = return acc+ | otherwise = do+ code <- nextCode tree+ if+ | code <= 15 ->+ getCodeLengths tree (n + 1) maxl code (Map.insert n code acc)+ | code == 16 -> do+ -- copy the previous code length 3 - 6 times+ num <- (3 +) `fmap` nextBits 2+ getCodeLengths tree (n + num) maxl prev (addNTimes n num prev acc)+ | code == 17 -> do+ -- repeat a code length of 0 for 3 - 10 times+ num <- (3 +) `fmap` nextBits 3+ getCodeLengths tree (n + num) maxl 0 (addNTimes n num 0 acc)+ | code == 18 -> do+ -- repeat a code length of 0 for 11 - 138 times+ num <- (11 +) `fmap` nextBits 7+ getCodeLengths tree (n + num) maxl 0 (addNTimes n num 0 acc)+ | otherwise ->+ raise (DecompressionError ("Unexpected code: " ++ show code)) where addNTimes idx count val old =- let idxs = take count [idx..]+ let idxs = take count [idx ..] vals = replicate count val- in Map.union old (Map.fromList (zip idxs vals))+ in Map.union old (Map.fromList (zip idxs vals)) -- ----------------------------------------------------------------------------- -getLength :: Int -> DeflateM Int64-getLength c =- case Map.lookup c getLengthMap of- Nothing -> error ("getLength for bad code: " ++ show c)- Just m -> m+getLength :: Int -> DeflateM s Int64+getLength c = lengthArray ! c+{-# INLINE getLength #-} -getLengthMap :: Map Int (DeflateM Int64)-getLengthMap = Map.fromList [- (257, return 3)- , (258, return 4)- , (259, return 5)- , (260, return 6)- , (261, return 7)- , (262, return 8)- , (263, return 9)- , (264, return 10)- , (265, (+ 11) `fmap` nextBits 1)- , (266, (+ 13) `fmap` nextBits 1)- , (267, (+ 15) `fmap` nextBits 1)- , (268, (+ 17) `fmap` nextBits 1)- , (269, (+ 19) `fmap` nextBits 2)- , (270, (+ 23) `fmap` nextBits 2)- , (271, (+ 27) `fmap` nextBits 2)- , (272, (+ 31) `fmap` nextBits 2)- , (273, (+ 35) `fmap` nextBits 3)- , (274, (+ 43) `fmap` nextBits 3)- , (275, (+ 51) `fmap` nextBits 3)- , (276, (+ 59) `fmap` nextBits 3)- , (277, (+ 67) `fmap` nextBits 4)- , (278, (+ 83) `fmap` nextBits 4)- , (279, (+ 99) `fmap` nextBits 4)- , (280, (+ 115) `fmap` nextBits 4)- , (281, (+ 131) `fmap` nextBits 5)- , (282, (+ 163) `fmap` nextBits 5)- , (283, (+ 195) `fmap` nextBits 5)- , (284, (+ 227) `fmap` nextBits 5)- , (285, return 258)- ]+lengthArray :: Array Int (DeflateM s Int64)+lengthArray =+ array+ (257, 285)+ [ (257, return 3)+ , (258, return 4)+ , (259, return 5)+ , (260, return 6)+ , (261, return 7)+ , (262, return 8)+ , (263, return 9)+ , (264, return 10)+ , (265, (+ 11) `fmap` nextBits 1)+ , (266, (+ 13) `fmap` nextBits 1)+ , (267, (+ 15) `fmap` nextBits 1)+ , (268, (+ 17) `fmap` nextBits 1)+ , (269, (+ 19) `fmap` nextBits 2)+ , (270, (+ 23) `fmap` nextBits 2)+ , (271, (+ 27) `fmap` nextBits 2)+ , (272, (+ 31) `fmap` nextBits 2)+ , (273, (+ 35) `fmap` nextBits 3)+ , (274, (+ 43) `fmap` nextBits 3)+ , (275, (+ 51) `fmap` nextBits 3)+ , (276, (+ 59) `fmap` nextBits 3)+ , (277, (+ 67) `fmap` nextBits 4)+ , (278, (+ 83) `fmap` nextBits 4)+ , (279, (+ 99) `fmap` nextBits 4)+ , (280, (+ 115) `fmap` nextBits 4)+ , (281, (+ 131) `fmap` nextBits 5)+ , (282, (+ 163) `fmap` nextBits 5)+ , (283, (+ 195) `fmap` nextBits 5)+ , (284, (+ 227) `fmap` nextBits 5)+ , (285, return 258)+ ] -getDistance :: Int -> DeflateM Int-getDistance c =- case Map.lookup c getDistanceMap of- Nothing -> error ("getDistance for bad code: " ++ show c)- Just m -> m+getDistance :: Int -> DeflateM s Int+getDistance c = distanceArray ! c+{-# INLINE getDistance #-} -getDistanceMap :: Map Int (DeflateM Int)-getDistanceMap = Map.fromList [- (0, return 1)- , (1, return 2)- , (2, return 3)- , (3, return 4)- , (4, (+ 5) `fmap` nextBits 1)- , (5, (+ 7) `fmap` nextBits 1)- , (6, (+ 9) `fmap` nextBits 2)- , (7, (+ 13) `fmap` nextBits 2)- , (8, (+ 17) `fmap` nextBits 3)- , (9, (+ 25) `fmap` nextBits 3)- , (10, (+ 33) `fmap` nextBits 4)- , (11, (+ 49) `fmap` nextBits 4)- , (12, (+ 65) `fmap` nextBits 5)- , (13, (+ 97) `fmap` nextBits 5)- , (14, (+ 129) `fmap` nextBits 6)- , (15, (+ 193) `fmap` nextBits 6)- , (16, (+ 257) `fmap` nextBits 7)- , (17, (+ 385) `fmap` nextBits 7)- , (18, (+ 513) `fmap` nextBits 8)- , (19, (+ 769) `fmap` nextBits 8)- , (20, (+ 1025) `fmap` nextBits 9)- , (21, (+ 1537) `fmap` nextBits 9)- , (22, (+ 2049) `fmap` nextBits 10)- , (23, (+ 3073) `fmap` nextBits 10)- , (24, (+ 4097) `fmap` nextBits 11)- , (25, (+ 6145) `fmap` nextBits 11)- , (26, (+ 8193) `fmap` nextBits 12)- , (27, (+ 12289) `fmap` nextBits 12)- , (28, (+ 16385) `fmap` nextBits 13)- , (29, (+ 24577) `fmap` nextBits 13)- ]+distanceArray :: Array Int (DeflateM s Int)+distanceArray =+ array+ (0, 29)+ [ (0, return 1)+ , (1, return 2)+ , (2, return 3)+ , (3, return 4)+ , (4, (+ 5) `fmap` nextBits 1)+ , (5, (+ 7) `fmap` nextBits 1)+ , (6, (+ 9) `fmap` nextBits 2)+ , (7, (+ 13) `fmap` nextBits 2)+ , (8, (+ 17) `fmap` nextBits 3)+ , (9, (+ 25) `fmap` nextBits 3)+ , (10, (+ 33) `fmap` nextBits 4)+ , (11, (+ 49) `fmap` nextBits 4)+ , (12, (+ 65) `fmap` nextBits 5)+ , (13, (+ 97) `fmap` nextBits 5)+ , (14, (+ 129) `fmap` nextBits 6)+ , (15, (+ 193) `fmap` nextBits 6)+ , (16, (+ 257) `fmap` nextBits 7)+ , (17, (+ 385) `fmap` nextBits 7)+ , (18, (+ 513) `fmap` nextBits 8)+ , (19, (+ 769) `fmap` nextBits 8)+ , (20, (+ 1025) `fmap` nextBits 9)+ , (21, (+ 1537) `fmap` nextBits 9)+ , (22, (+ 2049) `fmap` nextBits 10)+ , (23, (+ 3073) `fmap` nextBits 10)+ , (24, (+ 4097) `fmap` nextBits 11)+ , (25, (+ 6145) `fmap` nextBits 11)+ , (26, (+ 8193) `fmap` nextBits 12)+ , (27, (+ 12289) `fmap` nextBits 12)+ , (28, (+ 16385) `fmap` nextBits 13)+ , (29, (+ 24577) `fmap` nextBits 13)+ ] -- ----------------------------------------------------------------------------- -fixedLitTree :: HuffmanTree Int-fixedLitTree = computeHuffmanTree- ([(x, 8) | x <- [0 .. 143]] ++- [(x, 9) | x <- [144 .. 255]] ++- [(x, 7) | x <- [256 .. 279]] ++- [(x, 8) | x <- [280 .. 287]])+buildFixedLitTree :: DeflateM s (HuffmanTree Int)+buildFixedLitTree =+ computeHuffmanTree+ ( [(x, 8) | x <- [0 .. 143]]+ ++ [(x, 9) | x <- [144 .. 255]]+ ++ [(x, 7) | x <- [256 .. 279]]+ ++ [(x, 8) | x <- [280 .. 287]]+ ) -fixedDistanceTree :: HuffmanTree Int-fixedDistanceTree = computeHuffmanTree [(x,5) | x <- [0..31]]+buildFixedDistanceTree :: DeflateM s (HuffmanTree Int)+buildFixedDistanceTree = computeHuffmanTree [(x, 5) | x <- [0 .. 31]] -- ----------------------------------------------------------------------------- -computeHuffmanTree :: [(Int, Int)] -> HuffmanTree Int-computeHuffmanTree = createHuffmanTree . computeCodeValues+computeHuffmanTree :: [(Int, Int)] -> DeflateM s (HuffmanTree Int)+computeHuffmanTree initialData =+ case createHuffmanTree (computeCodeValues initialData) of+ Left err -> raise (HuffmanTreeError err)+ Right x -> return x -computeCodeValues :: Ord a => [(a, Int)] -> [(a, Int, Int)]-computeCodeValues vals = Map.foldrWithKey (\ v (l, c) a -> (v,l,c):a) [] codes+computeCodeValues :: [(Int, Int)] -> [(Int, Int, Int)]+computeCodeValues vals = Map.foldrWithKey (\v (l, c) a -> (v, l, c) : a) [] codes where- valsNo0s = filter (\ (_, b) -> (b /= 0)) vals- valsSort = sortBy (\ (a,_) (b,_) -> compare a b) valsNo0s- blCount = foldr (\ (_,k) m -> Map.insertWith (+) k 1 m) Map.empty valsNo0s+ valsNo0s = filter (\(_, b) -> (b /= 0)) vals+ valsSort = sortBy (\(a, _) (b, _) -> compare a b) valsNo0s+ blCount = foldr (\(_, k) m -> Map.insertWith (+) k 1 m) Map.empty valsNo0s nextcode = step2 0 1 (Map.insert 0 0 Map.empty)- lenTree = Map.fromList valsSort+ lenTree = Map.fromList valsSort codeTree = step3 (map fst valsSort) nextcode Map.empty- maxBits = maximum (map snd valsSort)- codes = Map.intersectionWith (,) lenTree codeTree+ maxBits = maximum (map snd valsSort)+ codes = Map.intersectionWith (,) lenTree codeTree -- step2 code bits nc | bits > maxBits = nc | otherwise = let prevCount = Map.findWithDefault 0 (bits - 1) blCount code' = (code + prevCount) `shiftL` 1- in step2 code' (bits + 1) (Map.insert bits code' nc) + in step2 code' (bits + 1) (Map.insert bits code' nc) -- step3 [] _ ct = ct- step3 (n:rest) nc ct =- let len = Map.findWithDefault 0 n lenTree+ step3 (n : rest) nc ct =+ let len = Map.findWithDefault 0 n lenTree Just ncLen = Map.lookup len nc- ct' = Map.insert n ncLen ct- nc' = Map.insert len (ncLen + 1) nc- in if len == 0- then step3 rest nc ct+ ct' = Map.insert n ncLen ct+ nc' = Map.insert len (ncLen + 1) nc+ in if len == 0+ then step3 rest nc ct else step3 rest nc' ct' codeLengthOrder :: [Int] codeLengthOrder = [16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15]--
src/Codec/Compression/Zlib/HuffmanTree.hs view
@@ -1,48 +1,83 @@-module Codec.Compression.Zlib.HuffmanTree(- HuffmanTree- , createHuffmanTree- , advanceTree- )- where+module Codec.Compression.Zlib.HuffmanTree (+ HuffmanTree,+ AdvanceResult (..),+ createHuffmanTree,+ advanceTree,+) where -import Data.Bits+import Data.Bits (testBit)+import Data.Word (Word8) -data HuffmanTree a = HuffmanNode (HuffmanTree a) (HuffmanTree a)- | HuffmanValue a- | HuffmanEmpty- deriving (Show)+data HuffmanTree a+ = HuffmanNode (HuffmanTree a) (HuffmanTree a)+ | HuffmanValue a+ | HuffmanEmpty+ deriving (Show) +data AdvanceResult a+ = AdvanceError String+ | NewTree (HuffmanTree a)+ | Result a+ emptyHuffmanTree :: HuffmanTree a emptyHuffmanTree = HuffmanEmpty -createHuffmanTree :: Show a => [(a, Int, Int)] -> HuffmanTree a-createHuffmanTree = foldr addHuffmanNode' emptyHuffmanTree- where addHuffmanNode' (a, b, c) = addHuffmanNode a b c--addHuffmanNode :: Show a => a -> Int -> Int -> HuffmanTree a -> HuffmanTree a-addHuffmanNode val 0 _ (HuffmanNode _ _) =- error ("Tried to add where the leaf is a node: " ++ show val)-addHuffmanNode _ 0 _ (HuffmanValue _) =- error "Two values point to the same place!"-addHuffmanNode val 0 _ HuffmanEmpty =- HuffmanValue val-addHuffmanNode val len code (HuffmanNode l r)- | testBit code (len - 1) = HuffmanNode l (addHuffmanNode val (len - 1) code r)- | otherwise = HuffmanNode (addHuffmanNode val (len - 1) code l) r-addHuffmanNode _ _ _ (HuffmanValue _) =- error "HuffmanValue hit while inserting a value!"-addHuffmanNode val len code HuffmanEmpty =- let newNode = addHuffmanNode val (len - 1) code HuffmanEmpty- in if testBit code (len - 1)- then HuffmanNode HuffmanEmpty newNode- else HuffmanNode newNode HuffmanEmpty+createHuffmanTree ::+ Show a =>+ [(a, Int, Int)] ->+ Either String (HuffmanTree a)+createHuffmanTree = foldr addHuffmanNode' (Right emptyHuffmanTree)+ where+ addHuffmanNode' (a, b, c) acc =+ case acc of+ Left err -> Left err+ Right tree -> addHuffmanNode a b c tree -advanceTree :: Bool -> HuffmanTree a -> Either (HuffmanTree a) a-advanceTree _ HuffmanEmpty = error "Tried to advance empty tree!"-advanceTree _ (HuffmanValue _) = error "Tried to advance empty value!"-advanceTree x (HuffmanNode l r) =- case if x then r else l of- HuffmanEmpty -> error "Advanced to empty tree!"- HuffmanValue y -> Right y- t -> Left t+addHuffmanNode ::+ Show a =>+ a ->+ Int ->+ Int ->+ HuffmanTree a ->+ Either String (HuffmanTree a)+addHuffmanNode val len code node =+ case node of+ HuffmanEmpty+ | len == 0 ->+ Right (HuffmanValue val)+ HuffmanEmpty ->+ case addHuffmanNode val (len - 1) code HuffmanEmpty of+ Left err -> Left err+ Right newNode+ | testBit code (len - 1) -> Right (HuffmanNode HuffmanEmpty newNode)+ | otherwise -> Right (HuffmanNode newNode HuffmanEmpty)+ --+ HuffmanValue _+ | len == 0 ->+ Left "Two values point to the same place!"+ HuffmanValue _ ->+ Left "HuffmanValue hit while inserting a value!"+ --+ HuffmanNode _ _+ | len == 0 ->+ Left ("Tried to add where the leaf is a node: " ++ show val)+ HuffmanNode l r | testBit code (len - 1) ->+ case addHuffmanNode val (len - 1) code r of+ Left err -> Left err+ Right r' -> Right (HuffmanNode l r')+ HuffmanNode l r ->+ case addHuffmanNode val (len - 1) code l of+ Left err -> Left err+ Right l' -> Right (HuffmanNode l' r) +advanceTree :: Word8 -> HuffmanTree a -> AdvanceResult a+advanceTree x node =+ case node of+ HuffmanEmpty -> AdvanceError "Tried to advance empty tree!"+ HuffmanValue _ -> AdvanceError "Tried to advance value!"+ HuffmanNode l r ->+ case if (x == 1) then r else l of+ HuffmanEmpty -> AdvanceError "Advanced to empty tree!"+ HuffmanValue y -> Result y+ t -> NewTree t+{-# INLINE advanceTree #-}
src/Codec/Compression/Zlib/Monad.hs view
@@ -1,163 +1,358 @@-module Codec.Compression.Zlib.Monad(- DeflateM- , runDeflateM- -- * Getting data from the input stream.- , nextBit- , nextBits- , nextByte- , nextWord16- , nextBlock- , nextCode- , readRest- -- * Aligning- , advanceToByte- -- * Emitting data- , emitByte- , emitBlock- , emitPastChunk- -- * Getting output- , finalAdler- , finalOutput- )- where+{-# LANGUAGE BangPatterns #-}+{-# LANGUAGE DeriveDataTypeable #-}+{-# LANGUAGE GeneralizedNewtypeDeriving #-}+{-# LANGUAGE MultiWayIf #-}+{-# LANGUAGE Rank2Types #-} -import Codec.Compression.Zlib.Adler32-import Codec.Compression.Zlib.HuffmanTree-import Codec.Compression.Zlib.OutputWindow-import Control.Monad-import Data.Bits-import Data.ByteString.Lazy(ByteString)-import qualified Data.ByteString.Lazy as BS-import Data.Int-import Data.Word-import MonadLib-import MonadLib.Monads+module Codec.Compression.Zlib.Monad (+ DeflateM,+ runDeflateM,+ ZlibDecoder (..),+ raise,+ DecompressionError (..), -data DecompressState = DecompressState {- dcsNextBitNo :: !Int- , dcsCurByte :: !Word8- , dcsAdler32 :: !AdlerState- , dcsInput :: !ByteString- , dcsOutput :: !OutputWindow- }+ -- * Getting data from the input stream.+ nextBits,+ nextByte,+ nextWord16,+ nextWord32,+ nextBlock,+ nextCode, -type DeflateM = State DecompressState+ -- * Aligning+ advanceToByte, -initialState :: ByteString -> DecompressState-initialState bstr =- case BS.uncons bstr of- Nothing -> error "No compressed data to inflate."- Just (f,rest) -> DecompressState 0 f initialAdlerState rest emptyWindow+ -- * Emitting data into the output window+ emitByte,+ emitBlock,+ emitPastChunk, -runDeflateM :: Show a => DeflateM a -> ByteString -> a-runDeflateM m i = result- where (result, _) = runState (initialState i) m+ -- * Getting and publishing output+ finalAdler,+ moveWindow,+ finalize,+) where +import Codec.Compression.Zlib.Adler32 (+ AdlerState,+ advanceAdler,+ advanceAdlerBlock,+ finalizeAdler,+ initialAdlerState,+ )+import Codec.Compression.Zlib.HuffmanTree (+ AdvanceResult (..),+ HuffmanTree,+ advanceTree,+ )+import Codec.Compression.Zlib.OutputWindow (+ OutputWindow,+ addByte,+ addChunk,+ addOldChunk,+ emitExcess,+ emptyWindow,+ finalizeWindow,+ )+import Control.Exception (Exception)+import Data.Bits (Bits (..))+import qualified Data.ByteString as S+import qualified Data.ByteString.Lazy as L+import Data.Int (Int64)+import Data.Typeable (Typeable)+import Data.Word (Word16, Word32, Word8)+import GHC.ST (ST)+import Prelude.Compat+import Prelude ()++data DecompressionState s = DecompressionState+ { dcsNextBitNo :: !Int+ , dcsCurByte :: !Word8+ , dcsAdler32 :: !AdlerState+ , dcsInput :: !S.ByteString+ , dcsOutput :: !(OutputWindow s)+ }++instance Show (DecompressionState s) where+ show dcs =+ "DecompressionState<nextBit=" ++ show (dcsNextBitNo dcs) ++ ","+ ++ "curByte="+ ++ show (dcsCurByte dcs)+ ++ ",inputLen="+ ++ show (S.length (dcsInput dcs))+ ++ ">"+ -- ----------------------------------------------------------------------------- -nextBit :: DeflateM Bool-nextBit =- do dcs <- get- let v = dcsCurByte dcs `testBit` dcsNextBitNo dcs- set $ advanceBit dcs- return v- where- advanceBit dcs- | dcsNextBitNo dcs == 7 =- case BS.uncons (dcsInput dcs) of- Nothing ->- error "Bit required, but no bits available!"- Just (nextb, rest) ->- dcs{ dcsNextBitNo = 0, dcsCurByte = nextb, dcsInput = rest }- | otherwise =- dcs{ dcsNextBitNo = dcsNextBitNo dcs + 1 }+data DecompressionError+ = HuffmanTreeError String+ | FormatError String+ | DecompressionError String+ | HeaderError String+ | ChecksumError String+ deriving (Typeable, Eq) -nextBits :: (Num a, Bits a) => Int -> DeflateM a-nextBits x- | x < 1 = error "nextBits called with x < 1"- | x == 1 = toNum `fmap` nextBit- | otherwise = do cur <- toNum `fmap` nextBit- rest <- nextBits (x - 1)- return ((rest `shiftL` 1) .|. cur)+instance Show DecompressionError where+ show x =+ case x of+ HuffmanTreeError s -> "Huffman tree manipulation error: " ++ s+ FormatError s -> "Block format error: " ++ s+ DecompressionError s -> "Decompression error: " ++ s+ HeaderError s -> "Header error: " ++ s+ ChecksumError s -> "Checksum error: " ++ s++instance Exception DecompressionError++-- -----------------------------------------------------------------------------++newtype DeflateM s a = DeflateM+ { unDeflateM ::+ DecompressionState s ->+ (DecompressionState s -> a -> ST s (ZlibDecoder s)) ->+ ST s (ZlibDecoder s)+ }++instance Applicative (DeflateM s) where+ pure x = DeflateM (\s k -> k s x)++ f <*> x = DeflateM $ \s1 k ->+ unDeflateM f s1 $ \s2 g ->+ unDeflateM x s2 $ \s3 y -> k s3 (g y)++ m *> n = DeflateM $ \s1 k ->+ unDeflateM m s1 $ \s2 _ -> unDeflateM n s2 k++ {-# INLINE pure #-}+ {-# INLINE (<*>) #-}+ {-# INLINE (*>) #-}++instance Functor (DeflateM s) where+ fmap f m = DeflateM (\s k -> unDeflateM m s (\s' a -> k s' (f a)))+ {-# INLINE fmap #-}++instance Monad (DeflateM s) where+ {-# INLINE return #-}+ return = pure++ {-# INLINE (>>=) #-}+ m >>= f = DeflateM $ \s1 k ->+ unDeflateM m s1 $ \s2 a -> unDeflateM (f a) s2 k++ (>>) = (*>)+ {-# INLINE (>>) #-}++get :: DeflateM s (DecompressionState s)+get = DeflateM (\s k -> k s s)+{-# INLINE get #-}++set :: DecompressionState s -> DeflateM s ()+set !s = DeflateM (\_ k -> k s ())+{-# INLINE set #-}++raise :: DecompressionError -> DeflateM s a+raise e = DeflateM (\_ _ -> return (DecompError e))+{-# INLINE raise #-}++liftST :: ST s a -> DeflateM s a+liftST action = DeflateM $ \s k -> do+ res <- action+ k s res++-- -----------------------------------------------------------------------------++data ZlibDecoder s+ = NeedMore (S.ByteString -> ST s (ZlibDecoder s))+ | Chunk S.ByteString (ST s (ZlibDecoder s))+ | Done+ | DecompError DecompressionError++runDeflateM :: DeflateM s () -> ST s (ZlibDecoder s)+runDeflateM m = do+ window <- emptyWindow+ let initialState =+ DecompressionState+ { dcsNextBitNo = 8+ , dcsCurByte = 0+ , dcsAdler32 = initialAdlerState+ , dcsInput = S.empty+ , dcsOutput = window+ }+ unDeflateM m initialState (\_ _ -> return Done)+{-# INLINE runDeflateM #-}++-- -----------------------------------------------------------------------------++getNextChunk :: DeflateM s ()+getNextChunk = DeflateM $ \st k -> return (NeedMore (loadChunk st k)) where- toNum False = 0- toNum True = 1+ loadChunk ::+ DecompressionState s ->+ (DecompressionState s -> () -> ST s (ZlibDecoder s)) ->+ S.ByteString ->+ ST s (ZlibDecoder s)+ loadChunk st k bstr =+ case S.uncons bstr of+ Nothing -> return (NeedMore (loadChunk st k))+ Just (nextb, rest) ->+ k st{dcsNextBitNo = 0, dcsCurByte = nextb, dcsInput = rest} () -nextByte :: DeflateM Word8-nextByte =- do dcs <- get- case BS.uncons (dcsInput dcs) of- _ | dcsNextBitNo dcs /= 0 ->- nextBits 8- Nothing ->- error "nextByte called with no more data."- Just (nextb, rest) ->- do set dcs{ dcsNextBitNo = 0, dcsCurByte = nextb, dcsInput = rest }- return (dcsCurByte dcs)+{-# SPECIALIZE nextBits :: Int -> DeflateM s Word8 #-}+{-# SPECIALIZE nextBits :: Int -> DeflateM s Int #-}+{-# SPECIALIZE nextBits :: Int -> DeflateM s Int64 #-}+{-# INLINE nextBits #-}+nextBits :: (Num a, Bits a) => Int -> DeflateM s a+nextBits x = nextBits' x 0 0 -nextWord16 :: DeflateM Word16-nextWord16 =- do high <- fromIntegral `fmap` nextByte- low <- fromIntegral `fmap` nextByte- return ((high `shiftL` 8) .|. low)+{-# SPECIALIZE nextBits' :: Int -> Int -> Word8 -> DeflateM s Word8 #-}+{-# SPECIALIZE nextBits' :: Int -> Int -> Int -> DeflateM s Int #-}+{-# SPECIALIZE nextBits' :: Int -> Int -> Int64 -> DeflateM s Int64 #-}+{-# INLINE nextBits' #-}+nextBits' :: (Num a, Bits a) => Int -> Int -> a -> DeflateM s a+nextBits' !x' !shiftNum !acc+ | x' == 0 = return acc+ | otherwise = do+ dcs <- get+ case dcsNextBitNo dcs of+ 8 -> case S.uncons (dcsInput dcs) of+ Nothing -> do+ getNextChunk+ nextBits' x' shiftNum acc+ Just (nextb, rest) -> do+ set dcs{dcsNextBitNo = 0, dcsCurByte = nextb, dcsInput = rest}+ nextBits' x' shiftNum acc+ nextBitNo -> do+ let !myBits = min x' (8 - nextBitNo)+ !base = dcsCurByte dcs `shiftR` nextBitNo+ !mask = complement (0xFF `shiftL` myBits)+ !res = fromIntegral (base .&. mask)+ !acc' = acc .|. (res `shiftL` shiftNum)+ set dcs{dcsNextBitNo = nextBitNo + myBits}+ nextBits' (x' - myBits) (shiftNum + myBits) acc' -nextBlock :: Integral a => a -> DeflateM ByteString-nextBlock amt =- do dcs <- get- unless (dcsNextBitNo dcs == 0) $- fail "Can't get a block on a non-byte boundary."- let curBlock = BS.cons (dcsCurByte dcs) (dcsInput dcs)- (block, rest) = BS.splitAt (fromIntegral amt) curBlock- case BS.uncons rest of- Nothing ->- fail "Not enough data left after nextBlock."- Just (first, rest') ->- do set dcs{ dcsNextBitNo = 0, dcsCurByte = first, dcsInput = rest' }- return block+nextByte :: DeflateM s Word8+nextByte = do+ dcs <- get+ if+ | dcsNextBitNo dcs == 0 -> do+ set dcs{dcsNextBitNo = 8}+ return (dcsCurByte dcs)+ | dcsNextBitNo dcs /= 8 -> nextBits 8 -- we're not aligned. sigh.+ | otherwise -> case S.uncons (dcsInput dcs) of+ Nothing -> getNextChunk >> nextByte+ Just (nextb, rest) -> do+ set+ dcs+ { dcsNextBitNo = 8+ , dcsCurByte = nextb+ , dcsInput = rest+ }+ return nextb -nextCode :: Show a => HuffmanTree a -> DeflateM a-nextCode tree =- do b <- nextBit- case advanceTree b tree of- Left tree' -> nextCode tree'- Right x -> return x+nextWord16 :: DeflateM s Word16+nextWord16 = do+ low <- fromIntegral `fmap` nextByte+ high <- fromIntegral `fmap` nextByte+ return ((high `shiftL` 8) .|. low) -readRest :: DeflateM ByteString-readRest =- do dcs <- get- return (BS.cons (dcsCurByte dcs) (dcsInput dcs))+nextWord32 :: DeflateM s Word32+nextWord32 = do+ a <- fromIntegral `fmap` nextByte+ b <- fromIntegral `fmap` nextByte+ c <- fromIntegral `fmap` nextByte+ d <- fromIntegral `fmap` nextByte+ return ((a `shiftL` 24) .|. (b `shiftL` 16) .|. (c `shiftL` 8) .|. d) -advanceToByte :: DeflateM ()-advanceToByte =- do dcs <- get- when (dcsNextBitNo dcs /= 0) $- case BS.uncons (dcsInput dcs) of- Nothing -> error "Advanced with no bytes left!"- Just (nextb, rest) ->- set dcs{ dcsNextBitNo = 0, dcsCurByte = nextb, dcsInput = rest }+nextBlock :: Integral a => a -> DeflateM s L.ByteString+nextBlock amt = do+ dcs <- get+ if+ | dcsNextBitNo dcs == 0 -> do+ let startByte = dcsCurByte dcs+ set dcs{dcsNextBitNo = 8}+ rest <- nextBlock (amt - 1)+ return (L.cons startByte rest)+ | dcsNextBitNo dcs == 8 ->+ getBlock (fromIntegral amt) (dcsInput dcs)+ | otherwise ->+ raise (FormatError "Can't get a block on a non-byte boundary.")+ where+ getBlock len bstr+ | len < S.length bstr = do+ let (mine, rest) = S.splitAt len bstr+ dcs <- get+ set dcs{dcsNextBitNo = 8, dcsInput = rest}+ return (L.fromStrict mine)+ | S.null bstr = do+ getNextChunk+ dcs <- get+ let byte1 = dcsCurByte dcs+ rest <- getBlock (len - 1) (dcsInput dcs)+ return (L.cons byte1 rest)+ | otherwise = do+ rest <- getBlock (len - S.length bstr) S.empty+ return (L.fromStrict bstr `L.append` rest) -emitByte :: Word8 -> DeflateM ()-emitByte b =- do dcs <- get- set dcs{ dcsOutput = dcsOutput dcs `addByte` b- , dcsAdler32 = advanceAdler (dcsAdler32 dcs) b }+nextCode :: Show a => HuffmanTree a -> DeflateM s a+nextCode tree = do+ b <- nextBits 1+ case advanceTree b tree of+ AdvanceError str -> raise (HuffmanTreeError str)+ NewTree tree' -> nextCode tree'+ Result x -> return x+{-# INLINE nextCode #-} -emitBlock :: ByteString -> DeflateM ()-emitBlock b =- do dcs <- get- set dcs { dcsOutput = dcsOutput dcs `addChunk` b- , dcsAdler32 = BS.foldl advanceAdler (dcsAdler32 dcs) b }+advanceToByte :: DeflateM s ()+advanceToByte = do+ dcs <- get+ set dcs{dcsNextBitNo = 8} -emitPastChunk :: Int -> Int64 -> DeflateM ()-emitPastChunk dist len =- do dcs <- get- let (output', newChunk) = addOldChunk (dcsOutput dcs) dist len- set dcs { dcsOutput = output'- , dcsAdler32 = BS.foldl advanceAdler (dcsAdler32 dcs) newChunk }+emitByte :: Word8 -> DeflateM s ()+emitByte b = do+ dcs <- get+ output' <- liftST (addByte (dcsOutput dcs) b)+ let adler' = advanceAdler (dcsAdler32 dcs) b+ set dcs{dcsOutput = output', dcsAdler32 = adler'}+{-# INLINE emitByte #-} -finalAdler :: DeflateM Word32-finalAdler = (finalizeAdler . dcsAdler32) `fmap` get+emitBlock :: L.ByteString -> DeflateM s ()+emitBlock b = do+ dcs <- get+ output' <- liftST (addChunk (dcsOutput dcs) b)+ let adler' = L.foldlChunks advanceAdlerBlock (dcsAdler32 dcs) b+ set dcs{dcsOutput = output', dcsAdler32 = adler'} -finalOutput :: DeflateM ByteString-finalOutput = (outByteString . dcsOutput) `fmap` get+emitPastChunk :: Int -> Int -> DeflateM s ()+emitPastChunk dist len = do+ dcs <- get+ (output', newChunk) <- liftST (addOldChunk (dcsOutput dcs) dist len)+ set+ dcs+ { dcsOutput = output'+ , dcsAdler32 = advanceAdlerBlock (dcsAdler32 dcs) newChunk+ }+{-# INLINE emitPastChunk #-} +finalAdler :: DeflateM s Word32+finalAdler = (finalizeAdler . dcsAdler32) <$> get++moveWindow :: DeflateM s ()+moveWindow = do+ dcs <- get+ possibleExcess <- liftST (emitExcess (dcsOutput dcs))+ case possibleExcess of+ Nothing ->+ return ()+ Just (builtChunk, output') -> do+ set dcs{dcsOutput = output'}+ publish builtChunk++finalize :: DeflateM s ()+finalize = do+ dcs <- get+ lastChunk <- liftST (finalizeWindow (dcsOutput dcs))+ publish lastChunk++{-# INLINE publish #-}+publish :: S.ByteString -> DeflateM s ()+publish bstr = DeflateM $ \st k ->+ return (Chunk bstr (k st ()))
src/Codec/Compression/Zlib/OutputWindow.hs view
@@ -1,69 +1,114 @@ {-# LANGUAGE BangPatterns #-}+{-# LANGUAGE MagicHash #-} {-# LANGUAGE MultiParamTypeClasses #-}+{-# LANGUAGE MultiWayIf #-}+{-# LANGUAGE UnboxedTuples #-} {-# OPTIONS_GHC -fno-warn-orphans #-}-module Codec.Compression.Zlib.OutputWindow(- OutputWindow- , emptyWindow- , addByte- , addChunk- , addOldChunk- , outByteString- )- where -import Data.ByteString.Builder-import Data.ByteString.Lazy(ByteString)-import qualified Data.ByteString as SBS-import qualified Data.ByteString.Lazy as BS-import Data.Int-import Data.FingerTree-import Data.Foldable(foldMap)-import Data.Monoid-import Data.Word+module Codec.Compression.Zlib.OutputWindow (+ OutputWindow,+ emptyWindow,+ emitExcess,+ finalizeWindow,+ addByte,+ addChunk,+ addOldChunk,+) where -data OutputWindow = OutputWindow {- owCommitted :: !(FingerTree Int SBS.ByteString)- , owRecent :: !Builder- }+import Control.Monad (foldM)+import qualified Data.ByteString as S+import qualified Data.ByteString.Lazy as L+import qualified Data.ByteString.Short as SBS+import Data.ByteString.Short.Internal (ShortByteString (SBS))+import qualified Data.Primitive as Prim+import qualified Data.Vector.Primitive as V+import qualified Data.Vector.Primitive.Mutable as MV+import GHC.ST (ST (..))+import GHC.Word (Word8 (..)) -instance Monoid Int where- mempty = 0- mappend = (+)+windowSize :: Int+windowSize = 128 * 1024 -instance Measured Int SBS.ByteString where- measure = SBS.length+data OutputWindow s = OutputWindow+ { owWindow :: {-# UNPACK #-} !(MV.MVector s Word8)+ , owNext :: {-# UNPACK #-} !Int+ } -emptyWindow :: OutputWindow-emptyWindow = OutputWindow empty mempty+emptyWindow :: ST s (OutputWindow s)+emptyWindow = do+ window <- MV.new windowSize+ return (OutputWindow window 0) -addByte :: OutputWindow -> Word8 -> OutputWindow-addByte !ow !b = ow{ owRecent = owRecent ow <> word8 b }+excessChunkSize :: Int+excessChunkSize = 32768 -addChunk :: OutputWindow -> ByteString -> OutputWindow-addChunk !ow !bs = ow{ owRecent = owRecent ow <> lazyByteString bs }+emitExcess :: OutputWindow s -> ST s (Maybe (S.ByteString, OutputWindow s))+emitExcess OutputWindow{owWindow = window, owNext = initialOffset}+ | initialOffset < excessChunkSize * 2 = return Nothing+ | otherwise = do+ toEmit <- V.freeze $ MV.slice 0 excessChunkSize window+ let excessLength = initialOffset - excessChunkSize+ -- Need move as these can overlap!+ MV.move (MV.slice 0 excessLength window) (MV.slice excessChunkSize excessLength window)+ let ow' = OutputWindow window excessLength+ return (Just (SBS.fromShort $ toByteString toEmit, ow')) -addOldChunk :: OutputWindow -> Int -> Int64 -> (OutputWindow, ByteString)-addOldChunk !ow !dist !len = (OutputWindow output (lazyByteString chunk), chunk)- where- output = owCommitted ow |> BS.toStrict (toLazyByteString (owRecent ow))- dropAmt = measure output - dist- (prev, sme) = split (> dropAmt) output- s :< rest = viewl sme- start = SBS.take (fromIntegral len) (SBS.drop (dropAmt-measure prev) s)- len' = fromIntegral len - SBS.length start- (m, rest') = split (> len') rest- middle = BS.toStrict (toLazyByteString (outFinger m))- end = case viewl rest' of- EmptyL -> SBS.empty- bs2 :< _ -> SBS.take (len' - measure m) bs2- chunkInf = BS.fromChunks [start, middle, end] `BS.append` chunk- chunk = BS.take len chunkInf+finalizeWindow :: OutputWindow s -> ST s S.ByteString+finalizeWindow ow = do+ -- safe as we're doing it at the end+ res <- V.unsafeFreeze (MV.slice 0 (owNext ow) (owWindow ow))+ pure $ SBS.fromShort $ toByteString res -outFinger :: FingerTree Int SBS.ByteString -> Builder-outFinger = foldMap byteString+-- ----------------------------------------------------------------------------- -outByteString :: OutputWindow -> ByteString-outByteString ow = - toLazyByteString (outFinger (owCommitted ow) <> owRecent ow)+addByte :: OutputWindow s -> Word8 -> ST s (OutputWindow s)+addByte !ow !b = do+ let offset = owNext ow+ MV.write (owWindow ow) offset b+ return ow{owNext = offset + 1} +addChunk :: OutputWindow s -> L.ByteString -> ST s (OutputWindow s)+addChunk !ow !bs = foldM copyChunk ow (L.toChunks bs) +copyChunk :: OutputWindow s -> S.ByteString -> ST s (OutputWindow s)+copyChunk ow sbstr = do+ -- safe as we're never going to look at this again+ ba <- V.unsafeThaw $ fromByteString $ SBS.toShort sbstr+ let offset = owNext ow+ len = MV.length ba+ MV.copy (MV.slice offset len (owWindow ow)) ba+ return ow{owNext = offset + len}++addOldChunk :: OutputWindow s -> Int -> Int -> ST s (OutputWindow s, S.ByteString)+addOldChunk (OutputWindow window next) dist len = do+ -- zlib can ask us to copy an "old" chunk that extends past our current offset.+ -- The intention is that we then start copying the "new" data we just copied into+ -- place. 'copyChunked' handles this for us.+ copyChunked (MV.slice next len window) (MV.slice (next - dist) len window) dist+ result <- V.freeze $ MV.slice next len window+ return (OutputWindow window (next + len), SBS.fromShort $ toByteString result)++{- | A copy function that copies the buffers sequentially in chunks no larger than+ the stated size. This allows us to handle the insane zlib behaviour.+-}+copyChunked :: MV.MVector s Word8 -> MV.MVector s Word8 -> Int -> ST s ()+copyChunked dest src chunkSize = go 0 (MV.length src)+ where+ go _ 0 = pure ()+ go copied toCopy = do+ let thisChunkSize = min toCopy chunkSize+ MV.copy (MV.slice copied thisChunkSize dest) (MV.slice copied thisChunkSize src)+ go (copied + thisChunkSize) (toCopy - thisChunkSize)++-- TODO: these are a bit questionable. Maybe we can just pass around Vector Word8 in the client code?+fromByteString :: SBS.ShortByteString -> V.Vector Word8+fromByteString (SBS ba) =+ let len = Prim.sizeofByteArray (Prim.ByteArray ba)+ sz = Prim.sizeOf (undefined :: Word8)+ in V.Vector 0 (len * sz) (Prim.ByteArray ba)++toByteString :: V.Vector Word8 -> SBS.ShortByteString+toByteString (V.Vector offset len ba) =+ let sz = Prim.sizeOf (undefined :: Word8)+ !(Prim.ByteArray ba') = Prim.cloneByteArray ba (offset * sz) (len * sz)+ in SBS ba'
test/Test.hs view
@@ -1,57 +1,125 @@+import Codec.Compression.Zlib import Codec.Compression.Zlib.Deflate-import Test.Framework-import Test.Framework.Providers.HUnit-import Test.HUnit(assertEqual)+import Data.ByteString.Lazy (readFile)+import Data.Char (ord)+import Data.List (isPrefixOf)+import System.FilePath+import Test.Tasty+import Test.Tasty.HUnit+import Prelude hiding (readFile) -rfcSimpleTestLengths :: [(Char, Int)]-rfcSimpleTestLengths = [- ('A', 3)- , ('B', 3)- , ('C', 3)- , ('D', 3)- , ('E', 3)- , ('F', 2)- , ('G', 4)- , ('H', 4)+-- -----------------------------------------------------------------------------++rfcSimpleTestLengths :: [(Int, Int)]+rfcSimpleTestLengths =+ [ (ord 'A', 3)+ , (ord 'B', 3)+ , (ord 'C', 3)+ , (ord 'D', 3)+ , (ord 'E', 3)+ , (ord 'F', 2)+ , (ord 'G', 4)+ , (ord 'H', 4) ] -rfcSimpleTestResults :: [(Char, Int, Int)]-rfcSimpleTestResults = [- ('A', 3, 2) -- 010- , ('B', 3, 3) -- 011- , ('C', 3, 4) -- 100- , ('D', 3, 5) -- 101- , ('E', 3, 6) -- 110- , ('F', 2, 0) -- 00- , ('G', 4, 14) -- 1110- , ('H', 4, 15) -- 1111+rfcSimpleTestResults :: [(Int, Int, Int)]+rfcSimpleTestResults =+ [ (ord 'A', 3, 2) -- 010+ , (ord 'B', 3, 3) -- 011+ , (ord 'C', 3, 4) -- 100+ , (ord 'D', 3, 5) -- 101+ , (ord 'E', 3, 6) -- 110+ , (ord 'F', 2, 0) -- 00+ , (ord 'G', 4, 14) -- 1110+ , (ord 'H', 4, 15) -- 1111 ] fixedHuffmanLengths :: [(Int, Int)] fixedHuffmanLengths =- ([(x, 8) | x <- [0 .. 143]] ++- [(x, 9) | x <- [144 .. 255]] ++- [(x, 7) | x <- [256 .. 279]] ++- [(x, 8) | x <- [280 .. 287]])+ ( [(x, 8) | x <- [0 .. 143]]+ ++ [(x, 9) | x <- [144 .. 255]]+ ++ [(x, 7) | x <- [256 .. 279]]+ ++ [(x, 8) | x <- [280 .. 287]]+ ) fixedHuffmanResults :: [(Int, Int, Int)] fixedHuffmanResults =- ([(fst x, 8, snd x) | x <- zip [0 ..143] [48 ..191]] ++ -- 00110000 through 10111111- [(fst x, 9, snd x) | x <- zip [144..255] [400..511]] ++ -- 110010000 through 111111111- [(fst x, 7, snd x) | x <- zip [256..279] [0 .. 23]] ++ -- 0000000 through 0010111- [(fst x, 8, snd x) | x <- zip [280..287] [192..199]]) -- 11000000 through 11000111+ ( [(fst x, 8, snd x) | x <- zip [0 .. 143] [48 .. 191]]+ ++ [(fst x, 9, snd x) | x <- zip [144 .. 255] [400 .. 511]] -- 00110000 through 10111111+ ++ [(fst x, 7, snd x) | x <- zip [256 .. 279] [0 .. 23]] -- 110010000 through 111111111+ ++ [(fst x, 8, snd x) | x <- zip [280 .. 287] [192 .. 199]] -- 0000000 through 0010111+ -- 11000000 through 11000111+ ) -zlibTests :: Test-zlibTests =- testGroup "DEFLATE / ZLib Algorithm Testing" [- testCase "RFC 1951 Code Generation Test"- (assertEqual "" (computeCodeValues rfcSimpleTestLengths)- rfcSimpleTestResults)- , testCase "Fixed Huffman lengths make right tree"- (assertEqual "" (computeCodeValues fixedHuffmanLengths)- fixedHuffmanResults)+-- -----------------------------------------------------------------------------++testCases :: [FilePath]+testCases =+ [ "randtest1"+ , "randtest2"+ , "randtest3"+ , "rfctest1"+ , "rfctest2"+ , "rfctest3"+ , "zerotest1"+ , "zerotest2"+ , "zerotest3" ] -main :: IO ()-main = defaultMain [zlibTests]+buildGoldTestCases :: IO TestTree+buildGoldTestCases =+ do+ trees <- mapM buildGoldTest testCases+ return (testGroup "Decompression Tests" trees) +buildGoldTest :: FilePath -> IO TestTree+buildGoldTest test =+ do+ let compressedFile = "test" </> "test-cases" </> test <.> "z"+ goldFile = "test" </> "test-cases" </> test <.> "gold"+ compressedBStr <- readFile compressedFile+ goldBStr <- readFile goldFile+ return+ ( testCase+ (toTestCaseName test)+ (assertEqual test (Right goldBStr) (decompress compressedBStr))+ )++toTestCaseName :: FilePath -> String+toTestCaseName fpath = prefix ++ suffix+ where+ prefix+ | "zero" `isPrefixOf` fpath = "Zero test #"+ | "rand" `isPrefixOf` fpath = "Random test #"+ | "rfc" `isPrefixOf` fpath = "RFC test #"+ | otherwise = error "Bad test case prefix."+ suffix = [last fpath]++-- -----------------------------------------------------------------------------++zlibTests :: IO TestTree+zlibTests =+ do+ decompTests <- buildGoldTestCases+ return $+ testGroup+ "DEFLATE / ZLib Algorithm Testing"+ [ testCase+ "RFC 1951 Code Generation Test"+ ( assertEqual+ ""+ (computeCodeValues rfcSimpleTestLengths)+ rfcSimpleTestResults+ )+ , testCase+ "Fixed Huffman lengths make right tree"+ ( assertEqual+ ""+ (computeCodeValues fixedHuffmanLengths)+ fixedHuffmanResults+ )+ , decompTests+ ]++main :: IO ()+main = defaultMain =<< zlibTests
+ test/test-cases/randtest1.gold view
binary file changed (absent → 4096 bytes)
+ test/test-cases/randtest1.z view
binary file changed (absent → 4107 bytes)
+ test/test-cases/randtest2.gold view
binary file changed (absent → 8192 bytes)
+ test/test-cases/randtest2.z view
binary file changed (absent → 8203 bytes)
+ test/test-cases/randtest3.gold view
binary file changed (absent → 12288 bytes)
+ test/test-cases/randtest3.z view
binary file changed (absent → 12299 bytes)
+ test/test-cases/rfctest1.gold view
@@ -0,0 +1,808 @@+<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"+ "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">+<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">+<head profile="http://dublincore.org/documents/2008/08/04/dc-html/">+ <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />+ <meta name="robots" content="index,follow" />+ <meta name="creator" content="rfcmarkup version 1.119" />+ <link rel="schema.DC" href="http://purl.org/dc/elements/1.1/" />+<meta name="DC.Identifier" content="urn:ietf:rfc:1950" />+<meta name="DC.Description.Abstract" content="This specification defines a lossless compressed data format. This+memo provides information for the Internet community. This memo does+not specify an Internet standard of any kind." />+<meta name="DC.Creator" content="Gailly, J-L." />+<meta name="DC.Creator" content="Deutsch, P." />+<meta name="DC.Date.Issued" content="May, 1996" />+<meta name="DC.Title" content="ZLIB Compressed Data Format Specification version 3.3" />++ <link rel="icon" href="/images/rfc.png" type="image/png" />+ <link rel="shortcut icon" href="/images/rfc.png" type="image/png" />+ <title>RFC 1950 - ZLIB Compressed Data Format Specification version 3.3</title>+ + + <style type="text/css">+ @media only screen + and (min-width: 992px)+ and (max-width: 1199px) {+ body { font-size: 14pt; }+ div.content { width: 96ex; margin: 0 auto; }+ }+ @media only screen + and (min-width: 768px)+ and (max-width: 991px) {+ body { font-size: 14pt; }+ div.content { width: 96ex; margin: 0 auto; }+ }+ @media only screen + and (min-width: 480px)+ and (max-width: 767px) {+ body { font-size: 11pt; }+ div.content { width: 96ex; margin: 0 auto; }+ }+ @media only screen + and (max-width: 479px) {+ body { font-size: 8pt; }+ div.content { width: 96ex; margin: 0 auto; }+ }+ @media only screen + and (min-device-width : 375px) + and (max-device-width : 667px) {+ body { font-size: 9.5pt; }+ div.content { width: 96ex; margin: 0 1px; }+ }+ @media only screen + and (min-device-width: 1200px) {+ body { font-size: 10pt; margin: 0 4em; }+ div.content { width: 96ex; margin: 0; }+ }+ h1, h2, h3, h4, h5, h6, .h1, .h2, .h3, .h4, .h5, .h6 {+ font-weight: bold;+ line-height: 0pt;+ display: inline;+ white-space: pre;+ font-family: monospace;+ font-size: 1em;+ font-weight: bold;+ }+ pre {+ font-size: 1em;+ margin-top: 0px;+ margin-bottom: 0px;+ }+ .pre {+ white-space: pre;+ font-family: monospace;+ }+ .header{+ font-weight: bold;+ }+ .newpage {+ page-break-before: always;+ }+ .invisible {+ text-decoration: none;+ color: white;+ }+ a.selflink {+ color: black;+ text-decoration: none;+ }+ @media print {+ body {+ font-family: monospace;+ font-size: 10.5pt;+ }+ h1, h2, h3, h4, h5, h6 {+ font-size: 1em;+ }+ + a:link, a:visited {+ color: inherit;+ text-decoration: none;+ }+ .noprint {+ display: none;+ }+ }+ @media screen {+ .grey, .grey a:link, .grey a:visited {+ color: #777;+ }+ .docinfo {+ background-color: #EEE;+ }+ .top {+ border-top: 7px solid #EEE;+ }+ .bgwhite { background-color: white; }+ .bgred { background-color: #F44; }+ .bggrey { background-color: #666; }+ .bgbrown { background-color: #840; } + .bgorange { background-color: #FA0; }+ .bgyellow { background-color: #EE0; }+ .bgmagenta{ background-color: #F4F; }+ .bgblue { background-color: #66F; }+ .bgcyan { background-color: #4DD; }+ .bggreen { background-color: #4F4; }++ .legend { font-size: 90%; }+ .cplate { font-size: 70%; border: solid grey 1px; }+ }+ </style>+ <!--[if IE]>+ <style>+ body {+ font-size: 13px;+ margin: 10px 10px;+ }+ </style>+ <![endif]-->++ <script type="text/javascript"><!--+ function addHeaderTags() {+ var spans = document.getElementsByTagName("span");+ for (var i=0; i < spans.length; i++) {+ var elem = spans[i];+ if (elem) {+ var level = elem.getAttribute("class");+ if (level == "h1" || level == "h2" || level == "h3" || level == "h4" || level == "h5" || level == "h6") {+ elem.innerHTML = "<"+level+">"+elem.innerHTML+"</"+level+">"; + }+ }+ }+ }+ var legend_html = "Colour legend:<br /> <table> <tr><td>Unknown:</td> <td><span class='cplate bgwhite'> </span></td></tr> <tr><td>Draft:</td> <td><span class='cplate bgred'> </span></td></tr> <tr><td>Informational:</td> <td><span class='cplate bgorange'> </span></td></tr> <tr><td>Experimental:</td> <td><span class='cplate bgyellow'> </span></td></tr> <tr><td>Best Common Practice:</td> <td><span class='cplate bgmagenta'> </span></td></tr> <tr><td>Proposed Standard:</td> <td><span class='cplate bgblue'> </span></td></tr> <tr><td>Draft Standard (old designation):</td> <td><span class='cplate bgcyan'> </span></td></tr> <tr><td>Internet Standard:</td> <td><span class='cplate bggreen'> </span></td></tr> <tr><td>Historic:</td> <td><span class='cplate bggrey'> </span></td></tr> <tr><td>Obsolete:</td> <td><span class='cplate bgbrown'> </span></td></tr> </table>";+ function showElem(id) {+ var elem = document.getElementById(id);+ elem.innerHTML = eval(id+"_html");+ elem.style.visibility='visible';+ }+ function hideElem(id) {+ var elem = document.getElementById(id);+ elem.style.visibility='hidden'; + elem.innerHTML = "";+ }+ // -->+ </script>+</head>+<body onload="addHeaderTags()">+ <div class="content">+ <div style="height: 13px;">+ <div onmouseover="this.style.cursor='pointer';"+ onclick="showElem('legend');"+ onmouseout="hideElem('legend')"+ style="height: 6px; position: absolute;"+ class="pre noprint docinfo bgorange"+ title="Click for colour legend." > </div>+ <div id="legend"+ class="docinfo noprint pre legend"+ style="position:absolute; top: 4px; left: 4ex; visibility:hidden; background-color: white; padding: 4px 9px 5px 7px; border: solid #345 1px; "+ onmouseover="showElem('legend');"+ onmouseout="hideElem('legend');">+ </div>+ </div>+<span class="pre noprint docinfo top">[<a href="../html/" title="Document search and retrieval page">Docs</a>] [<a href="/rfc/rfc1950.txt" title="Plaintext version of this document">txt</a>|<a href="/pdf/rfc1950" title="PDF version of this document">pdf</a>] [<a href="./draft-deutsch-zlib-spec" title="draft-deutsch-zlib-spec">draft-deutsch-zli...</a>] [<a href="/rfcdiff?difftype=--hwdiff&url2=rfc1950" title="Inline diff (wdiff)">Diff1</a>] [<a href="/rfcdiff?url2=rfc1950" title="Side-by-side diff">Diff2</a>] </span><br />+<span class="pre noprint docinfo"> </span><br />+<span class="pre noprint docinfo"> INFORMATIONAL</span><br />+<span class="pre noprint docinfo"> </span><br />+<pre>+Network Working Group P. Deutsch+Request for Comments: 1950 Aladdin Enterprises+Category: Informational J-L. Gailly+ Info-ZIP+ May 1996+++ <span class="h1">ZLIB Compressed Data Format Specification version 3.3</span>++Status of This Memo++ This memo provides information for the Internet community. This memo+ does not specify an Internet standard of any kind. Distribution of+ this memo is unlimited.++IESG Note:++ The IESG takes no position on the validity of any Intellectual+ Property Rights statements contained in this document.++Notices++ Copyright (c) 1996 L. Peter Deutsch and Jean-Loup Gailly++ Permission is granted to copy and distribute this document for any+ purpose and without charge, including translations into other+ languages and incorporation into compilations, provided that the+ copyright notice and this notice are preserved, and that any+ substantive changes or deletions from the original are clearly+ marked.++ A pointer to the latest version of this and related documentation in+ HTML format can be found at the URL+ <<a href="ftp://ftp.uu.net/graphics/png/documents/zlib/zdoc-index.html">ftp://ftp.uu.net/graphics/png/documents/zlib/zdoc-index.html</a>>.++Abstract++ This specification defines a lossless compressed data format. The+ data can be produced or consumed, even for an arbitrarily long+ sequentially presented input data stream, using only an a priori+ bounded amount of intermediate storage. The format presently uses+ the DEFLATE compression method but can be easily extended to use+ other compression methods. It can be implemented readily in a manner+ not covered by patents. This specification also defines the ADLER-32+ checksum (an extension and improvement of the Fletcher checksum),+ used for detection of data corruption, and provides an algorithm for+ computing it.+++++<span class="grey">Deutsch & Gailly Informational [Page 1]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-2" id="page-2" href="#page-2" class="invisible"> </a>+<span class="grey"><a href="./rfc1950">RFC 1950</a> ZLIB Compressed Data Format Specification May 1996</span>+++Table of Contents++ <a href="#section-1">1</a>. Introduction ................................................... <a href="#page-2">2</a>+ <a href="#section-1.1">1.1</a>. Purpose ................................................... <a href="#page-2">2</a>+ <a href="#section-1.2">1.2</a>. Intended audience ......................................... <a href="#page-3">3</a>+ <a href="#section-1.3">1.3</a>. Scope ..................................................... <a href="#page-3">3</a>+ <a href="#section-1.4">1.4</a>. Compliance ................................................ <a href="#page-3">3</a>+ <a href="#section-1.5">1.5</a>. Definitions of terms and conventions used ................ <a href="#page-3">3</a>+ <a href="#section-1.6">1.6</a>. Changes from previous versions ............................ <a href="#page-3">3</a>+ <a href="#section-2">2</a>. Detailed specification ......................................... <a href="#page-3">3</a>+ <a href="#section-2.1">2.1</a>. Overall conventions ....................................... <a href="#page-3">3</a>+ <a href="#section-2.2">2.2</a>. Data format ............................................... <a href="#page-4">4</a>+ <a href="#section-2.3">2.3</a>. Compliance ................................................ <a href="#page-7">7</a>+ <a href="#section-3">3</a>. References ..................................................... <a href="#page-7">7</a>+ <a href="#section-4">4</a>. Source code .................................................... <a href="#page-8">8</a>+ <a href="#section-5">5</a>. Security Considerations ........................................ <a href="#page-8">8</a>+ <a href="#section-6">6</a>. Acknowledgements ............................................... <a href="#page-8">8</a>+ <a href="#section-7">7</a>. Authors' Addresses ............................................. <a href="#page-8">8</a>+ <a href="#section-8">8</a>. Appendix: Rationale ............................................ <a href="#page-9">9</a>+ <a href="#section-9">9</a>. Appendix: Sample code ..........................................<a href="#page-10">10</a>++<span class="h2"><a class="selflink" name="section-1" href="#section-1">1</a>. Introduction</span>++ 1.1. Purpose++ The purpose of this specification is to define a lossless+ compressed data format that:++ * Is independent of CPU type, operating system, file system,+ and character set, and hence can be used for interchange;++ * Can be produced or consumed, even for an arbitrarily long+ sequentially presented input data stream, using only an a+ priori bounded amount of intermediate storage, and hence can+ be used in data communications or similar structures such as+ Unix filters;++ * Can use a number of different compression methods;++ * Can be implemented readily in a manner not covered by+ patents, and hence can be practiced freely.++ The data format defined by this specification does not attempt to+ allow random access to compressed data.++++++++<span class="grey">Deutsch & Gailly Informational [Page 2]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-3" id="page-3" href="#page-3" class="invisible"> </a>+<span class="grey"><a href="./rfc1950">RFC 1950</a> ZLIB Compressed Data Format Specification May 1996</span>+++ 1.2. Intended audience++ This specification is intended for use by implementors of software+ to compress data into zlib format and/or decompress data from zlib+ format.++ The text of the specification assumes a basic background in+ programming at the level of bits and other primitive data+ representations.++ 1.3. Scope++ The specification specifies a compressed data format that can be+ used for in-memory compression of a sequence of arbitrary bytes.++ 1.4. Compliance++ Unless otherwise indicated below, a compliant decompressor must be+ able to accept and decompress any data set that conforms to all+ the specifications presented here; a compliant compressor must+ produce data sets that conform to all the specifications presented+ here.++ 1.5. Definitions of terms and conventions used++ byte: 8 bits stored or transmitted as a unit (same as an octet).+ (For this specification, a byte is exactly 8 bits, even on+ machines which store a character on a number of bits different+ from 8.) See below, for the numbering of bits within a byte.++ 1.6. Changes from previous versions++ Version 3.1 was the first public release of this specification.+ In version 3.2, some terminology was changed and the Adler-32+ sample code was rewritten for clarity. In version 3.3, the+ support for a preset dictionary was introduced, and the+ specification was converted to RFC style.++<span class="h2"><a class="selflink" name="section-2" href="#section-2">2</a>. Detailed specification</span>++ 2.1. Overall conventions++ In the diagrams below, a box like this:++ +---++ | | <-- the vertical bars might be missing+ +---++++++<span class="grey">Deutsch & Gailly Informational [Page 3]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-4" id="page-4" href="#page-4" class="invisible"> </a>+<span class="grey"><a href="./rfc1950">RFC 1950</a> ZLIB Compressed Data Format Specification May 1996</span>+++ represents one byte; a box like this:++ +==============++ | |+ +==============+++ represents a variable number of bytes.++ Bytes stored within a computer do not have a "bit order", since+ they are always treated as a unit. However, a byte considered as+ an integer between 0 and 255 does have a most- and least-+ significant bit, and since we write numbers with the most-+ significant digit on the left, we also write bytes with the most-+ significant bit on the left. In the diagrams below, we number the+ bits of a byte so that bit 0 is the least-significant bit, i.e.,+ the bits are numbered:++ +--------++ |76543210|+ +--------+++ Within a computer, a number may occupy multiple bytes. All+ multi-byte numbers in the format described here are stored with+ the MOST-significant byte first (at the lower memory address).+ For example, the decimal number 520 is stored as:++ 0 1+ +--------+--------++ |00000010|00001000|+ +--------+--------++ ^ ^+ | |+ | + less significant byte = 8+ + more significant byte = 2 x 256++ 2.2. Data format++ A zlib stream has the following structure:++ 0 1+ +---+---++ |CMF|FLG| (more-->)+ +---+---++++++++++<span class="grey">Deutsch & Gailly Informational [Page 4]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-5" id="page-5" href="#page-5" class="invisible"> </a>+<span class="grey"><a href="./rfc1950">RFC 1950</a> ZLIB Compressed Data Format Specification May 1996</span>+++ (if FLG.FDICT set)++ 0 1 2 3+ +---+---+---+---++ | DICTID | (more-->)+ +---+---+---+---+++ +=====================+---+---+---+---++ |...compressed data...| ADLER32 |+ +=====================+---+---+---+---+++ Any data which may appear after ADLER32 are not part of the zlib+ stream.++ CMF (Compression Method and flags)+ This byte is divided into a 4-bit compression method and a 4-+ bit information field depending on the compression method.++ bits 0 to 3 CM Compression method+ bits 4 to 7 CINFO Compression info++ CM (Compression method)+ This identifies the compression method used in the file. CM = 8+ denotes the "deflate" compression method with a window size up+ to 32K. This is the method used by gzip and PNG (see+ references [<a href="#ref-1" title=""GZIP Compressed Data Format Specification"">1</a>] and [<a href="#ref-2" title=""PNG (Portable Network Graphics) specification"">2</a>] in Chapter 3, below, for the reference+ documents). CM = 15 is reserved. It might be used in a future+ version of this specification to indicate the presence of an+ extra field before the compressed data.++ CINFO (Compression info)+ For CM = 8, CINFO is the base-2 logarithm of the LZ77 window+ size, minus eight (CINFO=7 indicates a 32K window size). Values+ of CINFO above 7 are not allowed in this version of the+ specification. CINFO is not defined in this specification for+ CM not equal to 8.++ FLG (FLaGs)+ This flag byte is divided as follows:++ bits 0 to 4 FCHECK (check bits for CMF and FLG)+ bit 5 FDICT (preset dictionary)+ bits 6 to 7 FLEVEL (compression level)++ The FCHECK value must be such that CMF and FLG, when viewed as+ a 16-bit unsigned integer stored in MSB order (CMF*256 + FLG),+ is a multiple of 31.+++++<span class="grey">Deutsch & Gailly Informational [Page 5]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-6" id="page-6" href="#page-6" class="invisible"> </a>+<span class="grey"><a href="./rfc1950">RFC 1950</a> ZLIB Compressed Data Format Specification May 1996</span>+++ FDICT (Preset dictionary)+ If FDICT is set, a DICT dictionary identifier is present+ immediately after the FLG byte. The dictionary is a sequence of+ bytes which are initially fed to the compressor without+ producing any compressed output. DICT is the Adler-32 checksum+ of this sequence of bytes (see the definition of ADLER32+ below). The decompressor can use this identifier to determine+ which dictionary has been used by the compressor.++ FLEVEL (Compression level)+ These flags are available for use by specific compression+ methods. The "deflate" method (CM = 8) sets these flags as+ follows:++ 0 - compressor used fastest algorithm+ 1 - compressor used fast algorithm+ 2 - compressor used default algorithm+ 3 - compressor used maximum compression, slowest algorithm++ The information in FLEVEL is not needed for decompression; it+ is there to indicate if recompression might be worthwhile.++ compressed data+ For compression method 8, the compressed data is stored in the+ deflate compressed data format as described in the document+ "DEFLATE Compressed Data Format Specification" by L. Peter+ Deutsch. (See reference [<a href="#ref-3" title=""DEFLATE Compressed Data Format Specification"">3</a>] in Chapter 3, below)++ Other compressed data formats are not specified in this version+ of the zlib specification.++ ADLER32 (Adler-32 checksum)+ This contains a checksum value of the uncompressed data+ (excluding any dictionary data) computed according to Adler-32+ algorithm. This algorithm is a 32-bit extension and improvement+ of the Fletcher algorithm, used in the ITU-T X.224 / ISO 8073+ standard. See references [<a href="#ref-4" title=""An Arithmetic Checksum for Serial Transmissions,"">4</a>] and [<a href="#ref-5" title=""Checksum Algorithms,"">5</a>] in Chapter 3, below)++ Adler-32 is composed of two sums accumulated per byte: s1 is+ the sum of all bytes, s2 is the sum of all s1 values. Both sums+ are done modulo 65521. s1 is initialized to 1, s2 to zero. The+ Adler-32 checksum is stored as s2*65536 + s1 in most-+ significant-byte first (network) order.+++++++++<span class="grey">Deutsch & Gailly Informational [Page 6]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-7" id="page-7" href="#page-7" class="invisible"> </a>+<span class="grey"><a href="./rfc1950">RFC 1950</a> ZLIB Compressed Data Format Specification May 1996</span>+++ 2.3. Compliance++ A compliant compressor must produce streams with correct CMF, FLG+ and ADLER32, but need not support preset dictionaries. When the+ zlib data format is used as part of another standard data format,+ the compressor may use only preset dictionaries that are specified+ by this other data format. If this other format does not use the+ preset dictionary feature, the compressor must not set the FDICT+ flag.++ A compliant decompressor must check CMF, FLG, and ADLER32, and+ provide an error indication if any of these have incorrect values.+ A compliant decompressor must give an error indication if CM is+ not one of the values defined in this specification (only the+ value 8 is permitted in this version), since another value could+ indicate the presence of new features that would cause subsequent+ data to be interpreted incorrectly. A compliant decompressor must+ give an error indication if FDICT is set and DICTID is not the+ identifier of a known preset dictionary. A decompressor may+ ignore FLEVEL and still be compliant. When the zlib data format+ is being used as a part of another standard format, a compliant+ decompressor must support all the preset dictionaries specified by+ the other format. When the other format does not use the preset+ dictionary feature, a compliant decompressor must reject any+ stream in which the FDICT flag is set.++<span class="h2"><a class="selflink" name="section-3" href="#section-3">3</a>. References</span>++ [<a name="ref-1" id="ref-1">1</a>] Deutsch, L.P.,"GZIP Compressed Data Format Specification",+ available in <a href="ftp://ftp.uu.net/pub/archiving/zip/doc/">ftp://ftp.uu.net/pub/archiving/zip/doc/</a>++ [<a name="ref-2" id="ref-2">2</a>] Thomas Boutell, "PNG (Portable Network Graphics) specification",+ available in <a href="ftp://ftp.uu.net/graphics/png/documents/">ftp://ftp.uu.net/graphics/png/documents/</a>++ [<a name="ref-3" id="ref-3">3</a>] Deutsch, L.P.,"DEFLATE Compressed Data Format Specification",+ available in <a href="ftp://ftp.uu.net/pub/archiving/zip/doc/">ftp://ftp.uu.net/pub/archiving/zip/doc/</a>++ [<a name="ref-4" id="ref-4">4</a>] Fletcher, J. G., "An Arithmetic Checksum for Serial+ Transmissions," IEEE Transactions on Communications, Vol. COM-30,+ No. 1, January 1982, pp. 247-252.++ [<a name="ref-5" id="ref-5">5</a>] ITU-T Recommendation X.224, Annex D, "Checksum Algorithms,"+ November, 1993, pp. 144, 145. (Available from+ gopher://info.itu.ch). ITU-T X.244 is also the same as ISO 8073.++++++++<span class="grey">Deutsch & Gailly Informational [Page 7]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-8" id="page-8" href="#page-8" class="invisible"> </a>+<span class="grey"><a href="./rfc1950">RFC 1950</a> ZLIB Compressed Data Format Specification May 1996</span>+++<span class="h2"><a class="selflink" name="section-4" href="#section-4">4</a>. Source code</span>++ Source code for a C language implementation of a "zlib" compliant+ library is available at <a href="ftp://ftp.uu.net/pub/archiving/zip/zlib/">ftp://ftp.uu.net/pub/archiving/zip/zlib/</a>.++<span class="h2"><a class="selflink" name="section-5" href="#section-5">5</a>. Security Considerations</span>++ A decoder that fails to check the ADLER32 checksum value may be+ subject to undetected data corruption.++<span class="h2"><a class="selflink" name="section-6" href="#section-6">6</a>. Acknowledgements</span>++ Trademarks cited in this document are the property of their+ respective owners.++ Jean-Loup Gailly and Mark Adler designed the zlib format and wrote+ the related software described in this specification. Glenn+ Randers-Pehrson converted this document to RFC and HTML format.++<span class="h2"><a class="selflink" name="section-7" href="#section-7">7</a>. Authors' Addresses</span>++ L. Peter Deutsch+ Aladdin Enterprises+ 203 Santa Margarita Ave.+ Menlo Park, CA 94025++ Phone: (415) 322-0103 (AM only)+ FAX: (415) 322-1734+ EMail: <ghost@aladdin.com>+++ Jean-Loup Gailly++ EMail: <gzip@prep.ai.mit.edu>++ Questions about the technical content of this specification can be+ sent by email to++ Jean-Loup Gailly <gzip@prep.ai.mit.edu> and+ Mark Adler <madler@alumni.caltech.edu>++ Editorial comments on this specification can be sent by email to++ L. Peter Deutsch <ghost@aladdin.com> and+ Glenn Randers-Pehrson <randeg@alumni.rpi.edu>+++++++<span class="grey">Deutsch & Gailly Informational [Page 8]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-9" id="page-9" href="#page-9" class="invisible"> </a>+<span class="grey"><a href="./rfc1950">RFC 1950</a> ZLIB Compressed Data Format Specification May 1996</span>+++<span class="h2"><a class="selflink" name="section-8" href="#section-8">8</a>. Appendix: Rationale</span>++ 8.1. Preset dictionaries++ A preset dictionary is specially useful to compress short input+ sequences. The compressor can take advantage of the dictionary+ context to encode the input in a more compact manner. The+ decompressor can be initialized with the appropriate context by+ virtually decompressing a compressed version of the dictionary+ without producing any output. However for certain compression+ algorithms such as the deflate algorithm this operation can be+ achieved without actually performing any decompression.++ The compressor and the decompressor must use exactly the same+ dictionary. The dictionary may be fixed or may be chosen among a+ certain number of predefined dictionaries, according to the kind+ of input data. The decompressor can determine which dictionary has+ been chosen by the compressor by checking the dictionary+ identifier. This document does not specify the contents of+ predefined dictionaries, since the optimal dictionaries are+ application specific. Standard data formats using this feature of+ the zlib specification must precisely define the allowed+ dictionaries.++ 8.2. The Adler-32 algorithm++ The Adler-32 algorithm is much faster than the CRC32 algorithm yet+ still provides an extremely low probability of undetected errors.++ The modulo on unsigned long accumulators can be delayed for 5552+ bytes, so the modulo operation time is negligible. If the bytes+ are a, b, c, the second sum is 3a + 2b + c + 3, and so is position+ and order sensitive, unlike the first sum, which is just a+ checksum. That 65521 is prime is important to avoid a possible+ large class of two-byte errors that leave the check unchanged.+ (The Fletcher checksum uses 255, which is not prime and which also+ makes the Fletcher check insensitive to single byte changes 0 <->+ 255.)++ The sum s1 is initialized to 1 instead of zero to make the length+ of the sequence part of s2, so that the length does not have to be+ checked separately. (Any sequence of zeroes has a Fletcher+ checksum of zero.)+++++++++<span class="grey">Deutsch & Gailly Informational [Page 9]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-10" id="page-10" href="#page-10" class="invisible"> </a>+<span class="grey"><a href="./rfc1950">RFC 1950</a> ZLIB Compressed Data Format Specification May 1996</span>+++<span class="h2"><a class="selflink" name="section-9" href="#section-9">9</a>. Appendix: Sample code</span>++ The following C code computes the Adler-32 checksum of a data buffer.+ It is written for clarity, not for speed. The sample code is in the+ ANSI C programming language. Non C users may find it easier to read+ with these hints:++ & Bitwise AND operator.+ >> Bitwise right shift operator. When applied to an+ unsigned quantity, as here, right shift inserts zero bit(s)+ at the left.+ << Bitwise left shift operator. Left shift inserts zero+ bit(s) at the right.+ ++ "n++" increments the variable n.+ % modulo operator: a % b is the remainder of a divided by b.++ #define BASE 65521 /* largest prime smaller than 65536 */++ /*+ Update a running Adler-32 checksum with the bytes buf[0..len-1]+ and return the updated checksum. The Adler-32 checksum should be+ initialized to 1.++ Usage example:++ unsigned long adler = 1L;++ while (read_buffer(buffer, length) != EOF) {+ adler = update_adler32(adler, buffer, length);+ }+ if (adler != original_adler) error();+ */+ unsigned long update_adler32(unsigned long adler,+ unsigned char *buf, int len)+ {+ unsigned long s1 = adler & 0xffff;+ unsigned long s2 = (adler >> 16) & 0xffff;+ int n;++ for (n = 0; n < len; n++) {+ s1 = (s1 + buf[n]) % BASE;+ s2 = (s2 + s1) % BASE;+ }+ return (s2 << 16) + s1;+ }++ /* Return the adler32 of the bytes buf[0..len-1] */+++++<span class="grey">Deutsch & Gailly Informational [Page 10]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-11" id="page-11" href="#page-11" class="invisible"> </a>+<span class="grey"><a href="./rfc1950">RFC 1950</a> ZLIB Compressed Data Format Specification May 1996</span>+++ unsigned long adler32(unsigned char *buf, int len)+ {+ return update_adler32(1L, buf, len);+ }++++++++++++++++++++++++++++++++++++++++++++++++Deutsch & Gailly Informational [Page 11]++</pre><br />+ <span class="noprint"><small><small>Html markup produced by rfcmarkup 1.119, available from+ <a href="https://tools.ietf.org/tools/rfcmarkup/">https://tools.ietf.org/tools/rfcmarkup/</a>+ </small></small></span>+ </div>+</body>+</html>
+ test/test-cases/rfctest1.z view
binary file changed (absent → 9358 bytes)
+ test/test-cases/rfctest2.gold view
@@ -0,0 +1,1146 @@+<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"+ "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">+<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">+<head profile="http://dublincore.org/documents/2008/08/04/dc-html/">+ <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />+ <meta name="robots" content="index,follow" />+ <meta name="creator" content="rfcmarkup version 1.119" />+ <link rel="schema.DC" href="http://purl.org/dc/elements/1.1/" />+<meta name="DC.Identifier" content="urn:ietf:rfc:1951" />+<meta name="DC.Description.Abstract" content="This specification defines a lossless compressed data format that+compresses data using a combination of the LZ77 algorithm and Huffman+coding, with efficiency comparable to the best currently available+general-purpose compression methods. This memo provides information+for the Internet community. This memo does not specify an Internet+standard of any kind." />+<meta name="DC.Creator" content="L. Peter Deutsch <ghost@aladdin.com>" />+<meta name="DC.Date.Issued" content="May, 1996" />+<meta name="DC.Title" content="DEFLATE Compressed Data Format Specification version 1.3" />++ <link rel="icon" href="/images/rfc.png" type="image/png" />+ <link rel="shortcut icon" href="/images/rfc.png" type="image/png" />+ <title>RFC 1951 - DEFLATE Compressed Data Format Specification version 1.3</title>+ + + <style type="text/css">+ @media only screen + and (min-width: 992px)+ and (max-width: 1199px) {+ body { font-size: 14pt; }+ div.content { width: 96ex; margin: 0 auto; }+ }+ @media only screen + and (min-width: 768px)+ and (max-width: 991px) {+ body { font-size: 14pt; }+ div.content { width: 96ex; margin: 0 auto; }+ }+ @media only screen + and (min-width: 480px)+ and (max-width: 767px) {+ body { font-size: 11pt; }+ div.content { width: 96ex; margin: 0 auto; }+ }+ @media only screen + and (max-width: 479px) {+ body { font-size: 8pt; }+ div.content { width: 96ex; margin: 0 auto; }+ }+ @media only screen + and (min-device-width : 375px) + and (max-device-width : 667px) {+ body { font-size: 9.5pt; }+ div.content { width: 96ex; margin: 0 1px; }+ }+ @media only screen + and (min-device-width: 1200px) {+ body { font-size: 10pt; margin: 0 4em; }+ div.content { width: 96ex; margin: 0; }+ }+ h1, h2, h3, h4, h5, h6, .h1, .h2, .h3, .h4, .h5, .h6 {+ font-weight: bold;+ line-height: 0pt;+ display: inline;+ white-space: pre;+ font-family: monospace;+ font-size: 1em;+ font-weight: bold;+ }+ pre {+ font-size: 1em;+ margin-top: 0px;+ margin-bottom: 0px;+ }+ .pre {+ white-space: pre;+ font-family: monospace;+ }+ .header{+ font-weight: bold;+ }+ .newpage {+ page-break-before: always;+ }+ .invisible {+ text-decoration: none;+ color: white;+ }+ a.selflink {+ color: black;+ text-decoration: none;+ }+ @media print {+ body {+ font-family: monospace;+ font-size: 10.5pt;+ }+ h1, h2, h3, h4, h5, h6 {+ font-size: 1em;+ }+ + a:link, a:visited {+ color: inherit;+ text-decoration: none;+ }+ .noprint {+ display: none;+ }+ }+ @media screen {+ .grey, .grey a:link, .grey a:visited {+ color: #777;+ }+ .docinfo {+ background-color: #EEE;+ }+ .top {+ border-top: 7px solid #EEE;+ }+ .bgwhite { background-color: white; }+ .bgred { background-color: #F44; }+ .bggrey { background-color: #666; }+ .bgbrown { background-color: #840; } + .bgorange { background-color: #FA0; }+ .bgyellow { background-color: #EE0; }+ .bgmagenta{ background-color: #F4F; }+ .bgblue { background-color: #66F; }+ .bgcyan { background-color: #4DD; }+ .bggreen { background-color: #4F4; }++ .legend { font-size: 90%; }+ .cplate { font-size: 70%; border: solid grey 1px; }+ }+ </style>+ <!--[if IE]>+ <style>+ body {+ font-size: 13px;+ margin: 10px 10px;+ }+ </style>+ <![endif]-->++ <script type="text/javascript"><!--+ function addHeaderTags() {+ var spans = document.getElementsByTagName("span");+ for (var i=0; i < spans.length; i++) {+ var elem = spans[i];+ if (elem) {+ var level = elem.getAttribute("class");+ if (level == "h1" || level == "h2" || level == "h3" || level == "h4" || level == "h5" || level == "h6") {+ elem.innerHTML = "<"+level+">"+elem.innerHTML+"</"+level+">"; + }+ }+ }+ }+ var legend_html = "Colour legend:<br /> <table> <tr><td>Unknown:</td> <td><span class='cplate bgwhite'> </span></td></tr> <tr><td>Draft:</td> <td><span class='cplate bgred'> </span></td></tr> <tr><td>Informational:</td> <td><span class='cplate bgorange'> </span></td></tr> <tr><td>Experimental:</td> <td><span class='cplate bgyellow'> </span></td></tr> <tr><td>Best Common Practice:</td> <td><span class='cplate bgmagenta'> </span></td></tr> <tr><td>Proposed Standard:</td> <td><span class='cplate bgblue'> </span></td></tr> <tr><td>Draft Standard (old designation):</td> <td><span class='cplate bgcyan'> </span></td></tr> <tr><td>Internet Standard:</td> <td><span class='cplate bggreen'> </span></td></tr> <tr><td>Historic:</td> <td><span class='cplate bggrey'> </span></td></tr> <tr><td>Obsolete:</td> <td><span class='cplate bgbrown'> </span></td></tr> </table>";+ function showElem(id) {+ var elem = document.getElementById(id);+ elem.innerHTML = eval(id+"_html");+ elem.style.visibility='visible';+ }+ function hideElem(id) {+ var elem = document.getElementById(id);+ elem.style.visibility='hidden'; + elem.innerHTML = "";+ }+ // -->+ </script>+</head>+<body onload="addHeaderTags()">+ <div class="content">+ <div style="height: 13px;">+ <div onmouseover="this.style.cursor='pointer';"+ onclick="showElem('legend');"+ onmouseout="hideElem('legend')"+ style="height: 6px; position: absolute;"+ class="pre noprint docinfo bgorange"+ title="Click for colour legend." > </div>+ <div id="legend"+ class="docinfo noprint pre legend"+ style="position:absolute; top: 4px; left: 4ex; visibility:hidden; background-color: white; padding: 4px 9px 5px 7px; border: solid #345 1px; "+ onmouseover="showElem('legend');"+ onmouseout="hideElem('legend');">+ </div>+ </div>+<span class="pre noprint docinfo top">[<a href="../html/" title="Document search and retrieval page">Docs</a>] [<a href="/rfc/rfc1951.txt" title="Plaintext version of this document">txt</a>|<a href="/pdf/rfc1951" title="PDF version of this document">pdf</a>] [<a href="./draft-deutsch-deflate-spec" title="draft-deutsch-deflate-spec">draft-deutsch-def...</a>] [<a href="/rfcdiff?difftype=--hwdiff&url2=rfc1951" title="Inline diff (wdiff)">Diff1</a>] [<a href="/rfcdiff?url2=rfc1951" title="Side-by-side diff">Diff2</a>] </span><br />+<span class="pre noprint docinfo"> </span><br />+<span class="pre noprint docinfo"> INFORMATIONAL</span><br />+<span class="pre noprint docinfo"> </span><br />+<pre>+Network Working Group P. Deutsch+Request for Comments: 1951 Aladdin Enterprises+Category: Informational May 1996+++ <span class="h1">DEFLATE Compressed Data Format Specification version 1.3</span>++Status of This Memo++ This memo provides information for the Internet community. This memo+ does not specify an Internet standard of any kind. Distribution of+ this memo is unlimited.++IESG Note:++ The IESG takes no position on the validity of any Intellectual+ Property Rights statements contained in this document.++Notices++ Copyright (c) 1996 L. Peter Deutsch++ Permission is granted to copy and distribute this document for any+ purpose and without charge, including translations into other+ languages and incorporation into compilations, provided that the+ copyright notice and this notice are preserved, and that any+ substantive changes or deletions from the original are clearly+ marked.++ A pointer to the latest version of this and related documentation in+ HTML format can be found at the URL+ <<a href="ftp://ftp.uu.net/graphics/png/documents/zlib/zdoc-index.html">ftp://ftp.uu.net/graphics/png/documents/zlib/zdoc-index.html</a>>.++Abstract++ This specification defines a lossless compressed data format that+ compresses data using a combination of the LZ77 algorithm and Huffman+ coding, with efficiency comparable to the best currently available+ general-purpose compression methods. The data can be produced or+ consumed, even for an arbitrarily long sequentially presented input+ data stream, using only an a priori bounded amount of intermediate+ storage. The format can be implemented readily in a manner not+ covered by patents.+++++++++<span class="grey">Deutsch Informational [Page 1]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-2" id="page-2" href="#page-2" class="invisible"> </a>+<span class="grey"><a href="./rfc1951">RFC 1951</a> DEFLATE Compressed Data Format Specification May 1996</span>+++Table of Contents++ <a href="#section-1">1</a>. Introduction ................................................... <a href="#page-2">2</a>+ <a href="#section-1.1">1.1</a>. Purpose ................................................... <a href="#page-2">2</a>+ <a href="#section-1.2">1.2</a>. Intended audience ......................................... <a href="#page-3">3</a>+ <a href="#section-1.3">1.3</a>. Scope ..................................................... <a href="#page-3">3</a>+ <a href="#section-1.4">1.4</a>. Compliance ................................................ <a href="#page-3">3</a>+ <a href="#section-1.5">1.5</a>. Definitions of terms and conventions used ................ <a href="#page-3">3</a>+ <a href="#section-1.6">1.6</a>. Changes from previous versions ............................ <a href="#page-4">4</a>+ <a href="#section-2">2</a>. Compressed representation overview ............................. <a href="#page-4">4</a>+ <a href="#section-3">3</a>. Detailed specification ......................................... <a href="#page-5">5</a>+ <a href="#section-3.1">3.1</a>. Overall conventions ....................................... <a href="#page-5">5</a>+ <a href="#section-3.1.1">3.1.1</a>. Packing into bytes .................................. <a href="#page-5">5</a>+ <a href="#section-3.2">3.2</a>. Compressed block format ................................... <a href="#page-6">6</a>+ <a href="#section-3.2.1">3.2.1</a>. Synopsis of prefix and Huffman coding ............... <a href="#page-6">6</a>+ <a href="#section-3.2.2">3.2.2</a>. Use of Huffman coding in the "deflate" format ....... <a href="#page-7">7</a>+ <a href="#section-3.2.3">3.2.3</a>. Details of block format ............................. <a href="#page-9">9</a>+ <a href="#section-3.2.4">3.2.4</a>. Non-compressed blocks (BTYPE=00) ................... <a href="#page-11">11</a>+ <a href="#section-3.2.5">3.2.5</a>. Compressed blocks (length and distance codes) ...... <a href="#page-11">11</a>+ <a href="#section-3.2.6">3.2.6</a>. Compression with fixed Huffman codes (BTYPE=01) .... <a href="#page-12">12</a>+ <a href="#section-3.2.7">3.2.7</a>. Compression with dynamic Huffman codes (BTYPE=10) .. <a href="#page-13">13</a>+ <a href="#section-3.3">3.3</a>. Compliance ............................................... <a href="#page-14">14</a>+ <a href="#section-4">4</a>. Compression algorithm details ................................. <a href="#page-14">14</a>+ <a href="#section-5">5</a>. References .................................................... <a href="#page-16">16</a>+ <a href="#section-6">6</a>. Security Considerations ....................................... <a href="#page-16">16</a>+ <a href="#section-7">7</a>. Source code ................................................... <a href="#page-16">16</a>+ <a href="#section-8">8</a>. Acknowledgements .............................................. <a href="#page-16">16</a>+ <a href="#section-9">9</a>. Author's Address .............................................. <a href="#page-17">17</a>++<span class="h2"><a class="selflink" name="section-1" href="#section-1">1</a>. Introduction</span>++ 1.1. Purpose++ The purpose of this specification is to define a lossless+ compressed data format that:+ * Is independent of CPU type, operating system, file system,+ and character set, and hence can be used for interchange;+ * Can be produced or consumed, even for an arbitrarily long+ sequentially presented input data stream, using only an a+ priori bounded amount of intermediate storage, and hence+ can be used in data communications or similar structures+ such as Unix filters;+ * Compresses data with efficiency comparable to the best+ currently available general-purpose compression methods,+ and in particular considerably better than the "compress"+ program;+ * Can be implemented readily in a manner not covered by+ patents, and hence can be practiced freely;++++<span class="grey">Deutsch Informational [Page 2]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-3" id="page-3" href="#page-3" class="invisible"> </a>+<span class="grey"><a href="./rfc1951">RFC 1951</a> DEFLATE Compressed Data Format Specification May 1996</span>+++ * Is compatible with the file format produced by the current+ widely used gzip utility, in that conforming decompressors+ will be able to read data produced by the existing gzip+ compressor.++ The data format defined by this specification does not attempt to:++ * Allow random access to compressed data;+ * Compress specialized data (e.g., raster graphics) as well+ as the best currently available specialized algorithms.++ A simple counting argument shows that no lossless compression+ algorithm can compress every possible input data set. For the+ format defined here, the worst case expansion is 5 bytes per 32K-+ byte block, i.e., a size increase of 0.015% for large data sets.+ English text usually compresses by a factor of 2.5 to 3;+ executable files usually compress somewhat less; graphical data+ such as raster images may compress much more.++ 1.2. Intended audience++ This specification is intended for use by implementors of software+ to compress data into "deflate" format and/or decompress data from+ "deflate" format.++ The text of the specification assumes a basic background in+ programming at the level of bits and other primitive data+ representations. Familiarity with the technique of Huffman coding+ is helpful but not required.++ 1.3. Scope++ The specification specifies a method for representing a sequence+ of bytes as a (usually shorter) sequence of bits, and a method for+ packing the latter bit sequence into bytes.++ 1.4. Compliance++ Unless otherwise indicated below, a compliant decompressor must be+ able to accept and decompress any data set that conforms to all+ the specifications presented here; a compliant compressor must+ produce data sets that conform to all the specifications presented+ here.++ 1.5. Definitions of terms and conventions used++ Byte: 8 bits stored or transmitted as a unit (same as an octet).+ For this specification, a byte is exactly 8 bits, even on machines++++<span class="grey">Deutsch Informational [Page 3]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-4" id="page-4" href="#page-4" class="invisible"> </a>+<span class="grey"><a href="./rfc1951">RFC 1951</a> DEFLATE Compressed Data Format Specification May 1996</span>+++ which store a character on a number of bits different from eight.+ See below, for the numbering of bits within a byte.++ String: a sequence of arbitrary bytes.++ 1.6. Changes from previous versions++ There have been no technical changes to the deflate format since+ version 1.1 of this specification. In version 1.2, some+ terminology was changed. Version 1.3 is a conversion of the+ specification to RFC style.++<span class="h2"><a class="selflink" name="section-2" href="#section-2">2</a>. Compressed representation overview</span>++ A compressed data set consists of a series of blocks, corresponding+ to successive blocks of input data. The block sizes are arbitrary,+ except that non-compressible blocks are limited to 65,535 bytes.++ Each block is compressed using a combination of the LZ77 algorithm+ and Huffman coding. The Huffman trees for each block are independent+ of those for previous or subsequent blocks; the LZ77 algorithm may+ use a reference to a duplicated string occurring in a previous block,+ up to 32K input bytes before.++ Each block consists of two parts: a pair of Huffman code trees that+ describe the representation of the compressed data part, and a+ compressed data part. (The Huffman trees themselves are compressed+ using Huffman encoding.) The compressed data consists of a series of+ elements of two types: literal bytes (of strings that have not been+ detected as duplicated within the previous 32K input bytes), and+ pointers to duplicated strings, where a pointer is represented as a+ pair <length, backward distance>. The representation used in the+ "deflate" format limits distances to 32K bytes and lengths to 258+ bytes, but does not limit the size of a block, except for+ uncompressible blocks, which are limited as noted above.++ Each type of value (literals, distances, and lengths) in the+ compressed data is represented using a Huffman code, using one code+ tree for literals and lengths and a separate code tree for distances.+ The code trees for each block appear in a compact form just before+ the compressed data for that block.+++++++++++<span class="grey">Deutsch Informational [Page 4]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-5" id="page-5" href="#page-5" class="invisible"> </a>+<span class="grey"><a href="./rfc1951">RFC 1951</a> DEFLATE Compressed Data Format Specification May 1996</span>+++<span class="h2"><a class="selflink" name="section-3" href="#section-3">3</a>. Detailed specification</span>++ 3.1. Overall conventions In the diagrams below, a box like this:++ +---++ | | <-- the vertical bars might be missing+ +---+++ represents one byte; a box like this:++ +==============++ | |+ +==============+++ represents a variable number of bytes.++ Bytes stored within a computer do not have a "bit order", since+ they are always treated as a unit. However, a byte considered as+ an integer between 0 and 255 does have a most- and least-+ significant bit, and since we write numbers with the most-+ significant digit on the left, we also write bytes with the most-+ significant bit on the left. In the diagrams below, we number the+ bits of a byte so that bit 0 is the least-significant bit, i.e.,+ the bits are numbered:++ +--------++ |76543210|+ +--------+++ Within a computer, a number may occupy multiple bytes. All+ multi-byte numbers in the format described here are stored with+ the least-significant byte first (at the lower memory address).+ For example, the decimal number 520 is stored as:++ 0 1+ +--------+--------++ |00001000|00000010|+ +--------+--------++ ^ ^+ | |+ | + more significant byte = 2 x 256+ + less significant byte = 8++ 3.1.1. Packing into bytes++ This document does not address the issue of the order in which+ bits of a byte are transmitted on a bit-sequential medium,+ since the final data format described here is byte- rather than++++<span class="grey">Deutsch Informational [Page 5]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-6" id="page-6" href="#page-6" class="invisible"> </a>+<span class="grey"><a href="./rfc1951">RFC 1951</a> DEFLATE Compressed Data Format Specification May 1996</span>+++ bit-oriented. However, we describe the compressed block format+ in below, as a sequence of data elements of various bit+ lengths, not a sequence of bytes. We must therefore specify+ how to pack these data elements into bytes to form the final+ compressed byte sequence:++ * Data elements are packed into bytes in order of+ increasing bit number within the byte, i.e., starting+ with the least-significant bit of the byte.+ * Data elements other than Huffman codes are packed+ starting with the least-significant bit of the data+ element.+ * Huffman codes are packed starting with the most-+ significant bit of the code.++ In other words, if one were to print out the compressed data as+ a sequence of bytes, starting with the first byte at the+ *right* margin and proceeding to the *left*, with the most-+ significant bit of each byte on the left as usual, one would be+ able to parse the result from right to left, with fixed-width+ elements in the correct MSB-to-LSB order and Huffman codes in+ bit-reversed order (i.e., with the first bit of the code in the+ relative LSB position).++ 3.2. Compressed block format++ 3.2.1. Synopsis of prefix and Huffman coding++ Prefix coding represents symbols from an a priori known+ alphabet by bit sequences (codes), one code for each symbol, in+ a manner such that different symbols may be represented by bit+ sequences of different lengths, but a parser can always parse+ an encoded string unambiguously symbol-by-symbol.++ We define a prefix code in terms of a binary tree in which the+ two edges descending from each non-leaf node are labeled 0 and+ 1 and in which the leaf nodes correspond one-for-one with (are+ labeled with) the symbols of the alphabet; then the code for a+ symbol is the sequence of 0's and 1's on the edges leading from+ the root to the leaf labeled with that symbol. For example:++++++++++++<span class="grey">Deutsch Informational [Page 6]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-7" id="page-7" href="#page-7" class="invisible"> </a>+<span class="grey"><a href="./rfc1951">RFC 1951</a> DEFLATE Compressed Data Format Specification May 1996</span>+++ /\ Symbol Code+ 0 1 ------ ----+ / \ A 00+ /\ B B 1+ 0 1 C 011+ / \ D 010+ A /\+ 0 1+ / \+ D C++ A parser can decode the next symbol from an encoded input+ stream by walking down the tree from the root, at each step+ choosing the edge corresponding to the next input bit.++ Given an alphabet with known symbol frequencies, the Huffman+ algorithm allows the construction of an optimal prefix code+ (one which represents strings with those symbol frequencies+ using the fewest bits of any possible prefix codes for that+ alphabet). Such a code is called a Huffman code. (See+ reference [<a href="#ref-1" title=""A Method for the Construction of Minimum Redundancy Codes"">1</a>] in Chapter 5, references for additional+ information on Huffman codes.)++ Note that in the "deflate" format, the Huffman codes for the+ various alphabets must not exceed certain maximum code lengths.+ This constraint complicates the algorithm for computing code+ lengths from symbol frequencies. Again, see Chapter 5,+ references for details.++ 3.2.2. Use of Huffman coding in the "deflate" format++ The Huffman codes used for each alphabet in the "deflate"+ format have two additional rules:++ * All codes of a given bit length have lexicographically+ consecutive values, in the same order as the symbols+ they represent;++ * Shorter codes lexicographically precede longer codes.+++++++++++++<span class="grey">Deutsch Informational [Page 7]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-8" id="page-8" href="#page-8" class="invisible"> </a>+<span class="grey"><a href="./rfc1951">RFC 1951</a> DEFLATE Compressed Data Format Specification May 1996</span>+++ We could recode the example above to follow this rule as+ follows, assuming that the order of the alphabet is ABCD:++ Symbol Code+ ------ ----+ A 10+ B 0+ C 110+ D 111++ I.e., 0 precedes 10 which precedes 11x, and 110 and 111 are+ lexicographically consecutive.++ Given this rule, we can define the Huffman code for an alphabet+ just by giving the bit lengths of the codes for each symbol of+ the alphabet in order; this is sufficient to determine the+ actual codes. In our example, the code is completely defined+ by the sequence of bit lengths (2, 1, 3, 3). The following+ algorithm generates the codes as integers, intended to be read+ from most- to least-significant bit. The code lengths are+ initially in tree[I].Len; the codes are produced in+ tree[I].Code.++ 1) Count the number of codes for each code length. Let+ bl_count[N] be the number of codes of length N, N >= 1.++ 2) Find the numerical value of the smallest code for each+ code length:++ code = 0;+ bl_count[0] = 0;+ for (bits = 1; bits <= MAX_BITS; bits++) {+ code = (code + bl_count[bits-1]) << 1;+ next_code[bits] = code;+ }++ 3) Assign numerical values to all codes, using consecutive+ values for all codes of the same length with the base+ values determined at step 2. Codes that are never used+ (which have a bit length of zero) must not be assigned a+ value.++ for (n = 0; n <= max_code; n++) {+ len = tree[n].Len;+ if (len != 0) {+ tree[n].Code = next_code[len];+ next_code[len]++;+ }++++<span class="grey">Deutsch Informational [Page 8]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-9" id="page-9" href="#page-9" class="invisible"> </a>+<span class="grey"><a href="./rfc1951">RFC 1951</a> DEFLATE Compressed Data Format Specification May 1996</span>+++ }++ Example:++ Consider the alphabet ABCDEFGH, with bit lengths (3, 3, 3, 3,+ 3, 2, 4, 4). After step 1, we have:++ N bl_count[N]+ - -----------+ 2 1+ 3 5+ 4 2++ Step 2 computes the following next_code values:++ N next_code[N]+ - ------------+ 1 0+ 2 0+ 3 2+ 4 14++ Step 3 produces the following code values:++ Symbol Length Code+ ------ ------ ----+ A 3 010+ B 3 011+ C 3 100+ D 3 101+ E 3 110+ F 2 00+ G 4 1110+ H 4 1111++ 3.2.3. Details of block format++ Each block of compressed data begins with 3 header bits+ containing the following data:++ first bit BFINAL+ next 2 bits BTYPE++ Note that the header bits do not necessarily begin on a byte+ boundary, since a block does not necessarily occupy an integral+ number of bytes.++++++<span class="grey">Deutsch Informational [Page 9]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-10" id="page-10" href="#page-10" class="invisible"> </a>+<span class="grey"><a href="./rfc1951">RFC 1951</a> DEFLATE Compressed Data Format Specification May 1996</span>+++ BFINAL is set if and only if this is the last block of the data+ set.++ BTYPE specifies how the data are compressed, as follows:++ 00 - no compression+ 01 - compressed with fixed Huffman codes+ 10 - compressed with dynamic Huffman codes+ 11 - reserved (error)++ The only difference between the two compressed cases is how the+ Huffman codes for the literal/length and distance alphabets are+ defined.++ In all cases, the decoding algorithm for the actual data is as+ follows:++ do+ read block header from input stream.+ if stored with no compression+ skip any remaining bits in current partially+ processed byte+ read LEN and NLEN (see next section)+ copy LEN bytes of data to output+ otherwise+ if compressed with dynamic Huffman codes+ read representation of code trees (see+ subsection below)+ loop (until end of block code recognized)+ decode literal/length value from input stream+ if value < 256+ copy value (literal byte) to output stream+ otherwise+ if value = end of block (256)+ break from loop+ otherwise (value = 257..285)+ decode distance from input stream++ move backwards distance bytes in the output+ stream, and copy length bytes from this+ position to the output stream.+ end loop+ while not last block++ Note that a duplicated string reference may refer to a string+ in a previous block; i.e., the backward distance may cross one+ or more block boundaries. However a distance cannot refer past+ the beginning of the output stream. (An application using a++++<span class="grey">Deutsch Informational [Page 10]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-11" id="page-11" href="#page-11" class="invisible"> </a>+<span class="grey"><a href="./rfc1951">RFC 1951</a> DEFLATE Compressed Data Format Specification May 1996</span>+++ preset dictionary might discard part of the output stream; a+ distance can refer to that part of the output stream anyway)+ Note also that the referenced string may overlap the current+ position; for example, if the last 2 bytes decoded have values+ X and Y, a string reference with <length = 5, distance = 2>+ adds X,Y,X,Y,X to the output stream.++ We now specify each compression method in turn.++ 3.2.4. Non-compressed blocks (BTYPE=00)++ Any bits of input up to the next byte boundary are ignored.+ The rest of the block consists of the following information:++ 0 1 2 3 4...+ +---+---+---+---+================================++ | LEN | NLEN |... LEN bytes of literal data...|+ +---+---+---+---+================================+++ LEN is the number of data bytes in the block. NLEN is the+ one's complement of LEN.++ 3.2.5. Compressed blocks (length and distance codes)++ As noted above, encoded data blocks in the "deflate" format+ consist of sequences of symbols drawn from three conceptually+ distinct alphabets: either literal bytes, from the alphabet of+ byte values (0..255), or <length, backward distance> pairs,+ where the length is drawn from (3..258) and the distance is+ drawn from (1..32,768). In fact, the literal and length+ alphabets are merged into a single alphabet (0..285), where+ values 0..255 represent literal bytes, the value 256 indicates+ end-of-block, and values 257..285 represent length codes+ (possibly in conjunction with extra bits following the symbol+ code) as follows:+++++++++++++++++<span class="grey">Deutsch Informational [Page 11]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-12" id="page-12" href="#page-12" class="invisible"> </a>+<span class="grey"><a href="./rfc1951">RFC 1951</a> DEFLATE Compressed Data Format Specification May 1996</span>+++ Extra Extra Extra+ Code Bits Length(s) Code Bits Lengths Code Bits Length(s)+ ---- ---- ------ ---- ---- ------- ---- ---- -------+ 257 0 3 267 1 15,16 277 4 67-82+ 258 0 4 268 1 17,18 278 4 83-98+ 259 0 5 269 2 19-22 279 4 99-114+ 260 0 6 270 2 23-26 280 4 115-130+ 261 0 7 271 2 27-30 281 5 131-162+ 262 0 8 272 2 31-34 282 5 163-194+ 263 0 9 273 3 35-42 283 5 195-226+ 264 0 10 274 3 43-50 284 5 227-257+ 265 1 11,12 275 3 51-58 285 0 258+ 266 1 13,14 276 3 59-66++ The extra bits should be interpreted as a machine integer+ stored with the most-significant bit first, e.g., bits 1110+ represent the value 14.++ Extra Extra Extra+ Code Bits Dist Code Bits Dist Code Bits Distance+ ---- ---- ---- ---- ---- ------ ---- ---- --------+ 0 0 1 10 4 33-48 20 9 1025-1536+ 1 0 2 11 4 49-64 21 9 1537-2048+ 2 0 3 12 5 65-96 22 10 2049-3072+ 3 0 4 13 5 97-128 23 10 3073-4096+ 4 1 5,6 14 6 129-192 24 11 4097-6144+ 5 1 7,8 15 6 193-256 25 11 6145-8192+ 6 2 9-12 16 7 257-384 26 12 8193-12288+ 7 2 13-16 17 7 385-512 27 12 12289-16384+ 8 3 17-24 18 8 513-768 28 13 16385-24576+ 9 3 25-32 19 8 769-1024 29 13 24577-32768++ 3.2.6. Compression with fixed Huffman codes (BTYPE=01)++ The Huffman codes for the two alphabets are fixed, and are not+ represented explicitly in the data. The Huffman code lengths+ for the literal/length alphabet are:++ Lit Value Bits Codes+ --------- ---- -----+ 0 - 143 8 00110000 through+ 10111111+ 144 - 255 9 110010000 through+ 111111111+ 256 - 279 7 0000000 through+ 0010111+ 280 - 287 8 11000000 through+ 11000111++++<span class="grey">Deutsch Informational [Page 12]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-13" id="page-13" href="#page-13" class="invisible"> </a>+<span class="grey"><a href="./rfc1951">RFC 1951</a> DEFLATE Compressed Data Format Specification May 1996</span>+++ The code lengths are sufficient to generate the actual codes,+ as described above; we show the codes in the table for added+ clarity. Literal/length values 286-287 will never actually+ occur in the compressed data, but participate in the code+ construction.++ Distance codes 0-31 are represented by (fixed-length) 5-bit+ codes, with possible additional bits as shown in the table+ shown in Paragraph 3.2.5, above. Note that distance codes 30-+ 31 will never actually occur in the compressed data.++ 3.2.7. Compression with dynamic Huffman codes (BTYPE=10)++ The Huffman codes for the two alphabets appear in the block+ immediately after the header bits and before the actual+ compressed data, first the literal/length code and then the+ distance code. Each code is defined by a sequence of code+ lengths, as discussed in Paragraph 3.2.2, above. For even+ greater compactness, the code length sequences themselves are+ compressed using a Huffman code. The alphabet for code lengths+ is as follows:++ 0 - 15: Represent code lengths of 0 - 15+ 16: Copy the previous code length 3 - 6 times.+ The next 2 bits indicate repeat length+ (0 = 3, ... , 3 = 6)+ Example: Codes 8, 16 (+2 bits 11),+ 16 (+2 bits 10) will expand to+ 12 code lengths of 8 (1 + 6 + 5)+ 17: Repeat a code length of 0 for 3 - 10 times.+ (3 bits of length)+ 18: Repeat a code length of 0 for 11 - 138 times+ (7 bits of length)++ A code length of 0 indicates that the corresponding symbol in+ the literal/length or distance alphabet will not occur in the+ block, and should not participate in the Huffman code+ construction algorithm given earlier. If only one distance+ code is used, it is encoded using one bit, not zero bits; in+ this case there is a single code length of one, with one unused+ code. One distance code of zero bits means that there are no+ distance codes used at all (the data is all literals).++ We can now define the format of the block:++ 5 Bits: HLIT, # of Literal/Length codes - 257 (257 - 286)+ 5 Bits: HDIST, # of Distance codes - 1 (1 - 32)+ 4 Bits: HCLEN, # of Code Length codes - 4 (4 - 19)++++<span class="grey">Deutsch Informational [Page 13]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-14" id="page-14" href="#page-14" class="invisible"> </a>+<span class="grey"><a href="./rfc1951">RFC 1951</a> DEFLATE Compressed Data Format Specification May 1996</span>+++ (HCLEN + 4) x 3 bits: code lengths for the code length+ alphabet given just above, in the order: 16, 17, 18,+ 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15++ These code lengths are interpreted as 3-bit integers+ (0-7); as above, a code length of 0 means the+ corresponding symbol (literal/length or distance code+ length) is not used.++ HLIT + 257 code lengths for the literal/length alphabet,+ encoded using the code length Huffman code++ HDIST + 1 code lengths for the distance alphabet,+ encoded using the code length Huffman code++ The actual compressed data of the block,+ encoded using the literal/length and distance Huffman+ codes++ The literal/length symbol 256 (end of data),+ encoded using the literal/length Huffman code++ The code length repeat codes can cross from HLIT + 257 to the+ HDIST + 1 code lengths. In other words, all code lengths form+ a single sequence of HLIT + HDIST + 258 values.++ 3.3. Compliance++ A compressor may limit further the ranges of values specified in+ the previous section and still be compliant; for example, it may+ limit the range of backward pointers to some value smaller than+ 32K. Similarly, a compressor may limit the size of blocks so that+ a compressible block fits in memory.++ A compliant decompressor must accept the full range of possible+ values defined in the previous section, and must accept blocks of+ arbitrary size.++<span class="h2"><a class="selflink" name="section-4" href="#section-4">4</a>. Compression algorithm details</span>++ While it is the intent of this document to define the "deflate"+ compressed data format without reference to any particular+ compression algorithm, the format is related to the compressed+ formats produced by LZ77 (Lempel-Ziv 1977, see reference [<a href="#ref-2" title=""A Universal Algorithm for Sequential Data Compression"">2</a>] below);+ since many variations of LZ77 are patented, it is strongly+ recommended that the implementor of a compressor follow the general+ algorithm presented here, which is known not to be patented per se.+ The material in this section is not part of the definition of the++++<span class="grey">Deutsch Informational [Page 14]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-15" id="page-15" href="#page-15" class="invisible"> </a>+<span class="grey"><a href="./rfc1951">RFC 1951</a> DEFLATE Compressed Data Format Specification May 1996</span>+++ specification per se, and a compressor need not follow it in order to+ be compliant.++ The compressor terminates a block when it determines that starting a+ new block with fresh trees would be useful, or when the block size+ fills up the compressor's block buffer.++ The compressor uses a chained hash table to find duplicated strings,+ using a hash function that operates on 3-byte sequences. At any+ given point during compression, let XYZ be the next 3 input bytes to+ be examined (not necessarily all different, of course). First, the+ compressor examines the hash chain for XYZ. If the chain is empty,+ the compressor simply writes out X as a literal byte and advances one+ byte in the input. If the hash chain is not empty, indicating that+ the sequence XYZ (or, if we are unlucky, some other 3 bytes with the+ same hash function value) has occurred recently, the compressor+ compares all strings on the XYZ hash chain with the actual input data+ sequence starting at the current point, and selects the longest+ match.++ The compressor searches the hash chains starting with the most recent+ strings, to favor small distances and thus take advantage of the+ Huffman encoding. The hash chains are singly linked. There are no+ deletions from the hash chains; the algorithm simply discards matches+ that are too old. To avoid a worst-case situation, very long hash+ chains are arbitrarily truncated at a certain length, determined by a+ run-time parameter.++ To improve overall compression, the compressor optionally defers the+ selection of matches ("lazy matching"): after a match of length N has+ been found, the compressor searches for a longer match starting at+ the next input byte. If it finds a longer match, it truncates the+ previous match to a length of one (thus producing a single literal+ byte) and then emits the longer match. Otherwise, it emits the+ original match, and, as described above, advances N bytes before+ continuing.++ Run-time parameters also control this "lazy match" procedure. If+ compression ratio is most important, the compressor attempts a+ complete second search regardless of the length of the first match.+ In the normal case, if the current match is "long enough", the+ compressor reduces the search for a longer match, thus speeding up+ the process. If speed is most important, the compressor inserts new+ strings in the hash table only when no match was found, or when the+ match is not "too long". This degrades the compression ratio but+ saves time since there are both fewer insertions and fewer searches.++++++<span class="grey">Deutsch Informational [Page 15]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-16" id="page-16" href="#page-16" class="invisible"> </a>+<span class="grey"><a href="./rfc1951">RFC 1951</a> DEFLATE Compressed Data Format Specification May 1996</span>+++<span class="h2"><a class="selflink" name="section-5" href="#section-5">5</a>. References</span>++ [<a name="ref-1" id="ref-1">1</a>] Huffman, D. A., "A Method for the Construction of Minimum+ Redundancy Codes", Proceedings of the Institute of Radio+ Engineers, September 1952, Volume 40, Number 9, pp. 1098-1101.++ [<a name="ref-2" id="ref-2">2</a>] Ziv J., Lempel A., "A Universal Algorithm for Sequential Data+ Compression", IEEE Transactions on Information Theory, Vol. 23,+ No. 3, pp. 337-343.++ [<a name="ref-3" id="ref-3">3</a>] Gailly, J.-L., and Adler, M., ZLIB documentation and sources,+ available in <a href="ftp://ftp.uu.net/pub/archiving/zip/doc/">ftp://ftp.uu.net/pub/archiving/zip/doc/</a>++ [<a name="ref-4" id="ref-4">4</a>] Gailly, J.-L., and Adler, M., GZIP documentation and sources,+ available as gzip-*.tar in <a href="ftp://prep.ai.mit.edu/pub/gnu/">ftp://prep.ai.mit.edu/pub/gnu/</a>++ [<a name="ref-5" id="ref-5">5</a>] Schwartz, E. S., and Kallick, B. "Generating a canonical prefix+ encoding." Comm. ACM, 7,3 (Mar. 1964), pp. 166-169.++ [<a name="ref-6" id="ref-6">6</a>] Hirschberg and Lelewer, "Efficient decoding of prefix codes,"+ Comm. ACM, 33,4, April 1990, pp. 449-459.++<span class="h2"><a class="selflink" name="section-6" href="#section-6">6</a>. Security Considerations</span>++ Any data compression method involves the reduction of redundancy in+ the data. Consequently, any corruption of the data is likely to have+ severe effects and be difficult to correct. Uncompressed text, on+ the other hand, will probably still be readable despite the presence+ of some corrupted bytes.++ It is recommended that systems using this data format provide some+ means of validating the integrity of the compressed data. See+ reference [<a href="#ref-3" title="ZLIB documentation and sources">3</a>], for example.++<span class="h2"><a class="selflink" name="section-7" href="#section-7">7</a>. Source code</span>++ Source code for a C language implementation of a "deflate" compliant+ compressor and decompressor is available within the zlib package at+ <a href="ftp://ftp.uu.net/pub/archiving/zip/zlib/">ftp://ftp.uu.net/pub/archiving/zip/zlib/</a>.++<span class="h2"><a class="selflink" name="section-8" href="#section-8">8</a>. Acknowledgements</span>++ Trademarks cited in this document are the property of their+ respective owners.++ Phil Katz designed the deflate format. Jean-Loup Gailly and Mark+ Adler wrote the related software described in this specification.+ Glenn Randers-Pehrson converted this document to RFC and HTML format.++++<span class="grey">Deutsch Informational [Page 16]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-17" id="page-17" href="#page-17" class="invisible"> </a>+<span class="grey"><a href="./rfc1951">RFC 1951</a> DEFLATE Compressed Data Format Specification May 1996</span>+++<span class="h2"><a class="selflink" name="section-9" href="#section-9">9</a>. Author's Address</span>++ L. Peter Deutsch+ Aladdin Enterprises+ 203 Santa Margarita Ave.+ Menlo Park, CA 94025++ Phone: (415) 322-0103 (AM only)+ FAX: (415) 322-1734+ EMail: <ghost@aladdin.com>++ Questions about the technical content of this specification can be+ sent by email to:++ Jean-Loup Gailly <gzip@prep.ai.mit.edu> and+ Mark Adler <madler@alumni.caltech.edu>++ Editorial comments on this specification can be sent by email to:++ L. Peter Deutsch <ghost@aladdin.com> and+ Glenn Randers-Pehrson <randeg@alumni.rpi.edu>+++++++++++++++++++++++++++++++Deutsch Informational [Page 17]++</pre><br />+ <span class="noprint"><small><small>Html markup produced by rfcmarkup 1.119, available from+ <a href="https://tools.ietf.org/tools/rfcmarkup/">https://tools.ietf.org/tools/rfcmarkup/</a>+ </small></small></span>+ </div>+</body>+</html>
+ test/test-cases/rfctest2.z view
binary file changed (absent → 14275 bytes)
+ test/test-cases/rfctest3.gold view
@@ -0,0 +1,864 @@+<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"+ "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">+<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">+<head profile="http://dublincore.org/documents/2008/08/04/dc-html/">+ <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />+ <meta name="robots" content="index,follow" />+ <meta name="creator" content="rfcmarkup version 1.119" />+ <link rel="schema.DC" href="http://purl.org/dc/elements/1.1/" />+<meta name="DC.Identifier" content="urn:ietf:rfc:1952" />+<meta name="DC.Description.Abstract" content="This specification defines a lossless compressed data format that is+compatible with the widely used GZIP utility. This memo provides+information for the Internet community. This memo does not specify an+Internet standard of any kind." />+<meta name="DC.Creator" content="L. Peter Deutsch <ghost@aladdin.com>" />+<meta name="DC.Date.Issued" content="May, 1996" />+<meta name="DC.Title" content="GZIP file format specification version 4.3" />++ <link rel="icon" href="/images/rfc.png" type="image/png" />+ <link rel="shortcut icon" href="/images/rfc.png" type="image/png" />+ <title>RFC 1952 - GZIP file format specification version 4.3</title>+ + + <style type="text/css">+ @media only screen + and (min-width: 992px)+ and (max-width: 1199px) {+ body { font-size: 14pt; }+ div.content { width: 96ex; margin: 0 auto; }+ }+ @media only screen + and (min-width: 768px)+ and (max-width: 991px) {+ body { font-size: 14pt; }+ div.content { width: 96ex; margin: 0 auto; }+ }+ @media only screen + and (min-width: 480px)+ and (max-width: 767px) {+ body { font-size: 11pt; }+ div.content { width: 96ex; margin: 0 auto; }+ }+ @media only screen + and (max-width: 479px) {+ body { font-size: 8pt; }+ div.content { width: 96ex; margin: 0 auto; }+ }+ @media only screen + and (min-device-width : 375px) + and (max-device-width : 667px) {+ body { font-size: 9.5pt; }+ div.content { width: 96ex; margin: 0 1px; }+ }+ @media only screen + and (min-device-width: 1200px) {+ body { font-size: 10pt; margin: 0 4em; }+ div.content { width: 96ex; margin: 0; }+ }+ h1, h2, h3, h4, h5, h6, .h1, .h2, .h3, .h4, .h5, .h6 {+ font-weight: bold;+ line-height: 0pt;+ display: inline;+ white-space: pre;+ font-family: monospace;+ font-size: 1em;+ font-weight: bold;+ }+ pre {+ font-size: 1em;+ margin-top: 0px;+ margin-bottom: 0px;+ }+ .pre {+ white-space: pre;+ font-family: monospace;+ }+ .header{+ font-weight: bold;+ }+ .newpage {+ page-break-before: always;+ }+ .invisible {+ text-decoration: none;+ color: white;+ }+ a.selflink {+ color: black;+ text-decoration: none;+ }+ @media print {+ body {+ font-family: monospace;+ font-size: 10.5pt;+ }+ h1, h2, h3, h4, h5, h6 {+ font-size: 1em;+ }+ + a:link, a:visited {+ color: inherit;+ text-decoration: none;+ }+ .noprint {+ display: none;+ }+ }+ @media screen {+ .grey, .grey a:link, .grey a:visited {+ color: #777;+ }+ .docinfo {+ background-color: #EEE;+ }+ .top {+ border-top: 7px solid #EEE;+ }+ .bgwhite { background-color: white; }+ .bgred { background-color: #F44; }+ .bggrey { background-color: #666; }+ .bgbrown { background-color: #840; } + .bgorange { background-color: #FA0; }+ .bgyellow { background-color: #EE0; }+ .bgmagenta{ background-color: #F4F; }+ .bgblue { background-color: #66F; }+ .bgcyan { background-color: #4DD; }+ .bggreen { background-color: #4F4; }++ .legend { font-size: 90%; }+ .cplate { font-size: 70%; border: solid grey 1px; }+ }+ </style>+ <!--[if IE]>+ <style>+ body {+ font-size: 13px;+ margin: 10px 10px;+ }+ </style>+ <![endif]-->++ <script type="text/javascript"><!--+ function addHeaderTags() {+ var spans = document.getElementsByTagName("span");+ for (var i=0; i < spans.length; i++) {+ var elem = spans[i];+ if (elem) {+ var level = elem.getAttribute("class");+ if (level == "h1" || level == "h2" || level == "h3" || level == "h4" || level == "h5" || level == "h6") {+ elem.innerHTML = "<"+level+">"+elem.innerHTML+"</"+level+">"; + }+ }+ }+ }+ var legend_html = "Colour legend:<br /> <table> <tr><td>Unknown:</td> <td><span class='cplate bgwhite'> </span></td></tr> <tr><td>Draft:</td> <td><span class='cplate bgred'> </span></td></tr> <tr><td>Informational:</td> <td><span class='cplate bgorange'> </span></td></tr> <tr><td>Experimental:</td> <td><span class='cplate bgyellow'> </span></td></tr> <tr><td>Best Common Practice:</td> <td><span class='cplate bgmagenta'> </span></td></tr> <tr><td>Proposed Standard:</td> <td><span class='cplate bgblue'> </span></td></tr> <tr><td>Draft Standard (old designation):</td> <td><span class='cplate bgcyan'> </span></td></tr> <tr><td>Internet Standard:</td> <td><span class='cplate bggreen'> </span></td></tr> <tr><td>Historic:</td> <td><span class='cplate bggrey'> </span></td></tr> <tr><td>Obsolete:</td> <td><span class='cplate bgbrown'> </span></td></tr> </table>";+ function showElem(id) {+ var elem = document.getElementById(id);+ elem.innerHTML = eval(id+"_html");+ elem.style.visibility='visible';+ }+ function hideElem(id) {+ var elem = document.getElementById(id);+ elem.style.visibility='hidden'; + elem.innerHTML = "";+ }+ // -->+ </script>+</head>+<body onload="addHeaderTags()">+ <div class="content">+ <div style="height: 13px;">+ <div onmouseover="this.style.cursor='pointer';"+ onclick="showElem('legend');"+ onmouseout="hideElem('legend')"+ style="height: 6px; position: absolute;"+ class="pre noprint docinfo bgorange"+ title="Click for colour legend." > </div>+ <div id="legend"+ class="docinfo noprint pre legend"+ style="position:absolute; top: 4px; left: 4ex; visibility:hidden; background-color: white; padding: 4px 9px 5px 7px; border: solid #345 1px; "+ onmouseover="showElem('legend');"+ onmouseout="hideElem('legend');">+ </div>+ </div>+<span class="pre noprint docinfo top">[<a href="../html/" title="Document search and retrieval page">Docs</a>] [<a href="/rfc/rfc1952.txt" title="Plaintext version of this document">txt</a>|<a href="/pdf/rfc1952" title="PDF version of this document">pdf</a>] [<a href="./draft-deutsch-gzip-spec" title="draft-deutsch-gzip-spec">draft-deutsch-gzi...</a>] [<a href="/rfcdiff?difftype=--hwdiff&url2=rfc1952" title="Inline diff (wdiff)">Diff1</a>] [<a href="/rfcdiff?url2=rfc1952" title="Side-by-side diff">Diff2</a>] </span><br />+<span class="pre noprint docinfo"> </span><br />+<span class="pre noprint docinfo"> INFORMATIONAL</span><br />+<span class="pre noprint docinfo"> </span><br />+<pre>+Network Working Group P. Deutsch+Request for Comments: 1952 Aladdin Enterprises+Category: Informational May 1996+++ <span class="h1">GZIP file format specification version 4.3</span>++Status of This Memo++ This memo provides information for the Internet community. This memo+ does not specify an Internet standard of any kind. Distribution of+ this memo is unlimited.++IESG Note:++ The IESG takes no position on the validity of any Intellectual+ Property Rights statements contained in this document.++Notices++ Copyright (c) 1996 L. Peter Deutsch++ Permission is granted to copy and distribute this document for any+ purpose and without charge, including translations into other+ languages and incorporation into compilations, provided that the+ copyright notice and this notice are preserved, and that any+ substantive changes or deletions from the original are clearly+ marked.++ A pointer to the latest version of this and related documentation in+ HTML format can be found at the URL+ <<a href="ftp://ftp.uu.net/graphics/png/documents/zlib/zdoc-index.html">ftp://ftp.uu.net/graphics/png/documents/zlib/zdoc-index.html</a>>.++Abstract++ This specification defines a lossless compressed data format that is+ compatible with the widely used GZIP utility. The format includes a+ cyclic redundancy check value for detecting data corruption. The+ format presently uses the DEFLATE method of compression but can be+ easily extended to use other compression methods. The format can be+ implemented readily in a manner not covered by patents.+++++++++++<span class="grey">Deutsch Informational [Page 1]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-2" id="page-2" href="#page-2" class="invisible"> </a>+<span class="grey"><a href="./rfc1952">RFC 1952</a> GZIP File Format Specification May 1996</span>+++Table of Contents++ <a href="#section-1">1</a>. Introduction ................................................... <a href="#page-2">2</a>+ <a href="#section-1.1">1.1</a>. Purpose ................................................... <a href="#page-2">2</a>+ <a href="#section-1.2">1.2</a>. Intended audience ......................................... <a href="#page-3">3</a>+ <a href="#section-1.3">1.3</a>. Scope ..................................................... <a href="#page-3">3</a>+ <a href="#section-1.4">1.4</a>. Compliance ................................................ <a href="#page-3">3</a>+ <a href="#section-1.5">1.5</a>. Definitions of terms and conventions used ................. <a href="#page-3">3</a>+ <a href="#section-1.6">1.6</a>. Changes from previous versions ............................ <a href="#page-3">3</a>+ <a href="#section-2">2</a>. Detailed specification ......................................... <a href="#page-4">4</a>+ <a href="#section-2.1">2.1</a>. Overall conventions ....................................... <a href="#page-4">4</a>+ <a href="#section-2.2">2.2</a>. File format ............................................... <a href="#page-5">5</a>+ <a href="#section-2.3">2.3</a>. Member format ............................................. <a href="#page-5">5</a>+ <a href="#section-2.3.1">2.3.1</a>. Member header and trailer ........................... <a href="#page-6">6</a>+ <a href="#section-2.3.1.1">2.3.1.1</a>. Extra field ................................... <a href="#page-8">8</a>+ <a href="#section-2.3.1.2">2.3.1.2</a>. Compliance .................................... <a href="#page-9">9</a>+ <a href="#section-3">3</a>. References .................................................. <a href="#page-9">9</a>+ <a href="#section-4">4</a>. Security Considerations .................................... <a href="#page-10">10</a>+ <a href="#section-5">5</a>. Acknowledgements ........................................... <a href="#page-10">10</a>+ <a href="#section-6">6</a>. Author's Address ........................................... <a href="#page-10">10</a>+ <a href="#section-7">7</a>. Appendix: Jean-Loup Gailly's gzip utility .................. <a href="#page-11">11</a>+ <a href="#section-8">8</a>. Appendix: Sample CRC Code .................................. <a href="#page-11">11</a>++<span class="h2"><a class="selflink" name="section-1" href="#section-1">1</a>. Introduction</span>++ 1.1. Purpose++ The purpose of this specification is to define a lossless+ compressed data format that:++ * Is independent of CPU type, operating system, file system,+ and character set, and hence can be used for interchange;+ * Can compress or decompress a data stream (as opposed to a+ randomly accessible file) to produce another data stream,+ using only an a priori bounded amount of intermediate+ storage, and hence can be used in data communications or+ similar structures such as Unix filters;+ * Compresses data with efficiency comparable to the best+ currently available general-purpose compression methods,+ and in particular considerably better than the "compress"+ program;+ * Can be implemented readily in a manner not covered by+ patents, and hence can be practiced freely;+ * Is compatible with the file format produced by the current+ widely used gzip utility, in that conforming decompressors+ will be able to read data produced by the existing gzip+ compressor.+++++<span class="grey">Deutsch Informational [Page 2]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-3" id="page-3" href="#page-3" class="invisible"> </a>+<span class="grey"><a href="./rfc1952">RFC 1952</a> GZIP File Format Specification May 1996</span>+++ The data format defined by this specification does not attempt to:++ * Provide random access to compressed data;+ * Compress specialized data (e.g., raster graphics) as well as+ the best currently available specialized algorithms.++ 1.2. Intended audience++ This specification is intended for use by implementors of software+ to compress data into gzip format and/or decompress data from gzip+ format.++ The text of the specification assumes a basic background in+ programming at the level of bits and other primitive data+ representations.++ 1.3. Scope++ The specification specifies a compression method and a file format+ (the latter assuming only that a file can store a sequence of+ arbitrary bytes). It does not specify any particular interface to+ a file system or anything about character sets or encodings+ (except for file names and comments, which are optional).++ 1.4. Compliance++ Unless otherwise indicated below, a compliant decompressor must be+ able to accept and decompress any file that conforms to all the+ specifications presented here; a compliant compressor must produce+ files that conform to all the specifications presented here. The+ material in the appendices is not part of the specification per se+ and is not relevant to compliance.++ 1.5. Definitions of terms and conventions used++ byte: 8 bits stored or transmitted as a unit (same as an octet).+ (For this specification, a byte is exactly 8 bits, even on+ machines which store a character on a number of bits different+ from 8.) See below for the numbering of bits within a byte.++ 1.6. Changes from previous versions++ There have been no technical changes to the gzip format since+ version 4.1 of this specification. In version 4.2, some+ terminology was changed, and the sample CRC code was rewritten for+ clarity and to eliminate the requirement for the caller to do pre-+ and post-conditioning. Version 4.3 is a conversion of the+ specification to RFC style.++++<span class="grey">Deutsch Informational [Page 3]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-4" id="page-4" href="#page-4" class="invisible"> </a>+<span class="grey"><a href="./rfc1952">RFC 1952</a> GZIP File Format Specification May 1996</span>+++<span class="h2"><a class="selflink" name="section-2" href="#section-2">2</a>. Detailed specification</span>++ 2.1. Overall conventions++ In the diagrams below, a box like this:++ +---++ | | <-- the vertical bars might be missing+ +---+++ represents one byte; a box like this:++ +==============++ | |+ +==============+++ represents a variable number of bytes.++ Bytes stored within a computer do not have a "bit order", since+ they are always treated as a unit. However, a byte considered as+ an integer between 0 and 255 does have a most- and least-+ significant bit, and since we write numbers with the most-+ significant digit on the left, we also write bytes with the most-+ significant bit on the left. In the diagrams below, we number the+ bits of a byte so that bit 0 is the least-significant bit, i.e.,+ the bits are numbered:++ +--------++ |76543210|+ +--------+++ This document does not address the issue of the order in which+ bits of a byte are transmitted on a bit-sequential medium, since+ the data format described here is byte- rather than bit-oriented.++ Within a computer, a number may occupy multiple bytes. All+ multi-byte numbers in the format described here are stored with+ the least-significant byte first (at the lower memory address).+ For example, the decimal number 520 is stored as:++ 0 1+ +--------+--------++ |00001000|00000010|+ +--------+--------++ ^ ^+ | |+ | + more significant byte = 2 x 256+ + less significant byte = 8++++<span class="grey">Deutsch Informational [Page 4]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-5" id="page-5" href="#page-5" class="invisible"> </a>+<span class="grey"><a href="./rfc1952">RFC 1952</a> GZIP File Format Specification May 1996</span>+++ 2.2. File format++ A gzip file consists of a series of "members" (compressed data+ sets). The format of each member is specified in the following+ section. The members simply appear one after another in the file,+ with no additional information before, between, or after them.++ 2.3. Member format++ Each member has the following structure:++ +---+---+---+---+---+---+---+---+---+---++ |ID1|ID2|CM |FLG| MTIME |XFL|OS | (more-->)+ +---+---+---+---+---+---+---+---+---+---+++ (if FLG.FEXTRA set)++ +---+---+=================================++ | XLEN |...XLEN bytes of "extra field"...| (more-->)+ +---+---+=================================+++ (if FLG.FNAME set)++ +=========================================++ |...original file name, zero-terminated...| (more-->)+ +=========================================+++ (if FLG.FCOMMENT set)++ +===================================++ |...file comment, zero-terminated...| (more-->)+ +===================================+++ (if FLG.FHCRC set)++ +---+---++ | CRC16 |+ +---+---+++ +=======================++ |...compressed blocks...| (more-->)+ +=======================+++ 0 1 2 3 4 5 6 7+ +---+---+---+---+---+---+---+---++ | CRC32 | ISIZE |+ +---+---+---+---+---+---+---+---++++++<span class="grey">Deutsch Informational [Page 5]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-6" id="page-6" href="#page-6" class="invisible"> </a>+<span class="grey"><a href="./rfc1952">RFC 1952</a> GZIP File Format Specification May 1996</span>+++ 2.3.1. Member header and trailer++ ID1 (IDentification 1)+ ID2 (IDentification 2)+ These have the fixed values ID1 = 31 (0x1f, \037), ID2 = 139+ (0x8b, \213), to identify the file as being in gzip format.++ CM (Compression Method)+ This identifies the compression method used in the file. CM+ = 0-7 are reserved. CM = 8 denotes the "deflate"+ compression method, which is the one customarily used by+ gzip and which is documented elsewhere.++ FLG (FLaGs)+ This flag byte is divided into individual bits as follows:++ bit 0 FTEXT+ bit 1 FHCRC+ bit 2 FEXTRA+ bit 3 FNAME+ bit 4 FCOMMENT+ bit 5 reserved+ bit 6 reserved+ bit 7 reserved++ If FTEXT is set, the file is probably ASCII text. This is+ an optional indication, which the compressor may set by+ checking a small amount of the input data to see whether any+ non-ASCII characters are present. In case of doubt, FTEXT+ is cleared, indicating binary data. For systems which have+ different file formats for ascii text and binary data, the+ decompressor can use FTEXT to choose the appropriate format.+ We deliberately do not specify the algorithm used to set+ this bit, since a compressor always has the option of+ leaving it cleared and a decompressor always has the option+ of ignoring it and letting some other program handle issues+ of data conversion.++ If FHCRC is set, a CRC16 for the gzip header is present,+ immediately before the compressed data. The CRC16 consists+ of the two least significant bytes of the CRC32 for all+ bytes of the gzip header up to and not including the CRC16.+ [The FHCRC bit was never set by versions of gzip up to+ 1.2.4, even though it was documented with a different+ meaning in gzip 1.2.4.]++ If FEXTRA is set, optional extra fields are present, as+ described in a following section.++++<span class="grey">Deutsch Informational [Page 6]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-7" id="page-7" href="#page-7" class="invisible"> </a>+<span class="grey"><a href="./rfc1952">RFC 1952</a> GZIP File Format Specification May 1996</span>+++ If FNAME is set, an original file name is present,+ terminated by a zero byte. The name must consist of ISO+ 8859-1 (LATIN-1) characters; on operating systems using+ EBCDIC or any other character set for file names, the name+ must be translated to the ISO LATIN-1 character set. This+ is the original name of the file being compressed, with any+ directory components removed, and, if the file being+ compressed is on a file system with case insensitive names,+ forced to lower case. There is no original file name if the+ data was compressed from a source other than a named file;+ for example, if the source was stdin on a Unix system, there+ is no file name.++ If FCOMMENT is set, a zero-terminated file comment is+ present. This comment is not interpreted; it is only+ intended for human consumption. The comment must consist of+ ISO 8859-1 (LATIN-1) characters. Line breaks should be+ denoted by a single line feed character (10 decimal).++ Reserved FLG bits must be zero.++ MTIME (Modification TIME)+ This gives the most recent modification time of the original+ file being compressed. The time is in Unix format, i.e.,+ seconds since 00:00:00 GMT, Jan. 1, 1970. (Note that this+ may cause problems for MS-DOS and other systems that use+ local rather than Universal time.) If the compressed data+ did not come from a file, MTIME is set to the time at which+ compression started. MTIME = 0 means no time stamp is+ available.++ XFL (eXtra FLags)+ These flags are available for use by specific compression+ methods. The "deflate" method (CM = 8) sets these flags as+ follows:++ XFL = 2 - compressor used maximum compression,+ slowest algorithm+ XFL = 4 - compressor used fastest algorithm++ OS (Operating System)+ This identifies the type of file system on which compression+ took place. This may be useful in determining end-of-line+ convention for text files. The currently defined values are+ as follows:+++++++<span class="grey">Deutsch Informational [Page 7]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-8" id="page-8" href="#page-8" class="invisible"> </a>+<span class="grey"><a href="./rfc1952">RFC 1952</a> GZIP File Format Specification May 1996</span>+++ 0 - FAT filesystem (MS-DOS, OS/2, NT/Win32)+ 1 - Amiga+ 2 - VMS (or OpenVMS)+ 3 - Unix+ 4 - VM/CMS+ 5 - Atari TOS+ 6 - HPFS filesystem (OS/2, NT)+ 7 - Macintosh+ 8 - Z-System+ 9 - CP/M+ 10 - TOPS-20+ 11 - NTFS filesystem (NT)+ 12 - QDOS+ 13 - Acorn RISCOS+ 255 - unknown++ XLEN (eXtra LENgth)+ If FLG.FEXTRA is set, this gives the length of the optional+ extra field. See below for details.++ CRC32 (CRC-32)+ This contains a Cyclic Redundancy Check value of the+ uncompressed data computed according to CRC-32 algorithm+ used in the ISO 3309 standard and in <a href="#section-8.1.1.6.2">section 8.1.1.6.2</a> of+ ITU-T recommendation V.42. (See <a href="http://www.iso.ch">http://www.iso.ch</a> for+ ordering ISO documents. See gopher://info.itu.ch for an+ online version of ITU-T V.42.)++ ISIZE (Input SIZE)+ This contains the size of the original (uncompressed) input+ data modulo 2^32.++ 2.3.1.1. Extra field++ If the FLG.FEXTRA bit is set, an "extra field" is present in+ the header, with total length XLEN bytes. It consists of a+ series of subfields, each of the form:++ +---+---+---+---+==================================++ |SI1|SI2| LEN |... LEN bytes of subfield data ...|+ +---+---+---+---+==================================+++ SI1 and SI2 provide a subfield ID, typically two ASCII letters+ with some mnemonic value. Jean-Loup Gailly+ <gzip@prep.ai.mit.edu> is maintaining a registry of subfield+ IDs; please send him any subfield ID you wish to use. Subfield+ IDs with SI2 = 0 are reserved for future use. The following+ IDs are currently defined:++++<span class="grey">Deutsch Informational [Page 8]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-9" id="page-9" href="#page-9" class="invisible"> </a>+<span class="grey"><a href="./rfc1952">RFC 1952</a> GZIP File Format Specification May 1996</span>+++ SI1 SI2 Data+ ---------- ---------- ----+ 0x41 ('A') 0x70 ('P') Apollo file type information++ LEN gives the length of the subfield data, excluding the 4+ initial bytes.++ 2.3.1.2. Compliance++ A compliant compressor must produce files with correct ID1,+ ID2, CM, CRC32, and ISIZE, but may set all the other fields in+ the fixed-length part of the header to default values (255 for+ OS, 0 for all others). The compressor must set all reserved+ bits to zero.++ A compliant decompressor must check ID1, ID2, and CM, and+ provide an error indication if any of these have incorrect+ values. It must examine FEXTRA/XLEN, FNAME, FCOMMENT and FHCRC+ at least so it can skip over the optional fields if they are+ present. It need not examine any other part of the header or+ trailer; in particular, a decompressor may ignore FTEXT and OS+ and always produce binary output, and still be compliant. A+ compliant decompressor must give an error indication if any+ reserved bit is non-zero, since such a bit could indicate the+ presence of a new field that would cause subsequent data to be+ interpreted incorrectly.++<span class="h2"><a class="selflink" name="section-3" href="#section-3">3</a>. References</span>++ [<a name="ref-1" id="ref-1">1</a>] "Information Processing - 8-bit single-byte coded graphic+ character sets - Part 1: Latin alphabet No.1" (ISO 8859-1:1987).+ The ISO 8859-1 (Latin-1) character set is a superset of 7-bit+ ASCII. Files defining this character set are available as+ iso_8859-1.* in <a href="ftp://ftp.uu.net/graphics/png/documents/">ftp://ftp.uu.net/graphics/png/documents/</a>++ [<a name="ref-2" id="ref-2">2</a>] ISO 3309++ [<a name="ref-3" id="ref-3">3</a>] ITU-T recommendation V.42++ [<a name="ref-4" id="ref-4">4</a>] Deutsch, L.P.,"DEFLATE Compressed Data Format Specification",+ available in <a href="ftp://ftp.uu.net/pub/archiving/zip/doc/">ftp://ftp.uu.net/pub/archiving/zip/doc/</a>++ [<a name="ref-5" id="ref-5">5</a>] Gailly, J.-L., GZIP documentation, available as gzip-*.tar in+ <a href="ftp://prep.ai.mit.edu/pub/gnu/">ftp://prep.ai.mit.edu/pub/gnu/</a>++ [<a name="ref-6" id="ref-6">6</a>] Sarwate, D.V., "Computation of Cyclic Redundancy Checks via Table+ Look-Up", Communications of the ACM, 31(8), pp.1008-1013.+++++<span class="grey">Deutsch Informational [Page 9]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-10" id="page-10" href="#page-10" class="invisible"> </a>+<span class="grey"><a href="./rfc1952">RFC 1952</a> GZIP File Format Specification May 1996</span>+++ [<a name="ref-7" id="ref-7">7</a>] Schwaderer, W.D., "CRC Calculation", April 85 PC Tech Journal,+ pp.118-133.++ [<a name="ref-8" id="ref-8">8</a>] <a href="ftp://ftp.adelaide.edu.au/pub/rocksoft/papers/crc_v3.txt">ftp://ftp.adelaide.edu.au/pub/rocksoft/papers/crc_v3.txt</a>,+ describing the CRC concept.++<span class="h2"><a class="selflink" name="section-4" href="#section-4">4</a>. Security Considerations</span>++ Any data compression method involves the reduction of redundancy in+ the data. Consequently, any corruption of the data is likely to have+ severe effects and be difficult to correct. Uncompressed text, on+ the other hand, will probably still be readable despite the presence+ of some corrupted bytes.++ It is recommended that systems using this data format provide some+ means of validating the integrity of the compressed data, such as by+ setting and checking the CRC-32 check value.++<span class="h2"><a class="selflink" name="section-5" href="#section-5">5</a>. Acknowledgements</span>++ Trademarks cited in this document are the property of their+ respective owners.++ Jean-Loup Gailly designed the gzip format and wrote, with Mark Adler,+ the related software described in this specification. Glenn+ Randers-Pehrson converted this document to RFC and HTML format.++<span class="h2"><a class="selflink" name="section-6" href="#section-6">6</a>. Author's Address</span>++ L. Peter Deutsch+ Aladdin Enterprises+ 203 Santa Margarita Ave.+ Menlo Park, CA 94025++ Phone: (415) 322-0103 (AM only)+ FAX: (415) 322-1734+ EMail: <ghost@aladdin.com>++ Questions about the technical content of this specification can be+ sent by email to:++ Jean-Loup Gailly <gzip@prep.ai.mit.edu> and+ Mark Adler <madler@alumni.caltech.edu>++ Editorial comments on this specification can be sent by email to:++ L. Peter Deutsch <ghost@aladdin.com> and+ Glenn Randers-Pehrson <randeg@alumni.rpi.edu>++++<span class="grey">Deutsch Informational [Page 10]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-11" id="page-11" href="#page-11" class="invisible"> </a>+<span class="grey"><a href="./rfc1952">RFC 1952</a> GZIP File Format Specification May 1996</span>+++<span class="h2"><a class="selflink" name="section-7" href="#section-7">7</a>. Appendix: Jean-Loup Gailly's gzip utility</span>++ The most widely used implementation of gzip compression, and the+ original documentation on which this specification is based, were+ created by Jean-Loup Gailly <gzip@prep.ai.mit.edu>. Since this+ implementation is a de facto standard, we mention some more of its+ features here. Again, the material in this section is not part of+ the specification per se, and implementations need not follow it to+ be compliant.++ When compressing or decompressing a file, gzip preserves the+ protection, ownership, and modification time attributes on the local+ file system, since there is no provision for representing protection+ attributes in the gzip file format itself. Since the file format+ includes a modification time, the gzip decompressor provides a+ command line switch that assigns the modification time from the file,+ rather than the local modification time of the compressed input, to+ the decompressed output.++<span class="h2"><a class="selflink" name="section-8" href="#section-8">8</a>. Appendix: Sample CRC Code</span>++ The following sample code represents a practical implementation of+ the CRC (Cyclic Redundancy Check). (See also ISO 3309 and ITU-T V.42+ for a formal specification.)++ The sample code is in the ANSI C programming language. Non C users+ may find it easier to read with these hints:++ & Bitwise AND operator.+ ^ Bitwise exclusive-OR operator.+ >> Bitwise right shift operator. When applied to an+ unsigned quantity, as here, right shift inserts zero+ bit(s) at the left.+ ! Logical NOT operator.+ ++ "n++" increments the variable n.+ 0xNNN 0x introduces a hexadecimal (base 16) constant.+ Suffix L indicates a long value (at least 32 bits).++ /* Table of CRCs of all 8-bit messages. */+ unsigned long crc_table[256];++ /* Flag: has the table been computed? Initially false. */+ int crc_table_computed = 0;++ /* Make the table for a fast CRC. */+ void make_crc_table(void)+ {+ unsigned long c;++++<span class="grey">Deutsch Informational [Page 11]</span></pre>+<hr class='noprint' style='width: 96ex;' align='left'/><!--NewPage--><pre class='newpage'><a name="page-12" id="page-12" href="#page-12" class="invisible"> </a>+<span class="grey"><a href="./rfc1952">RFC 1952</a> GZIP File Format Specification May 1996</span>+++ int n, k;+ for (n = 0; n < 256; n++) {+ c = (unsigned long) n;+ for (k = 0; k < 8; k++) {+ if (c & 1) {+ c = 0xedb88320L ^ (c >> 1);+ } else {+ c = c >> 1;+ }+ }+ crc_table[n] = c;+ }+ crc_table_computed = 1;+ }++ /*+ Update a running crc with the bytes buf[0..len-1] and return+ the updated crc. The crc should be initialized to zero. Pre- and+ post-conditioning (one's complement) is performed within this+ function so it shouldn't be done by the caller. Usage example:++ unsigned long crc = 0L;++ while (read_buffer(buffer, length) != EOF) {+ crc = update_crc(crc, buffer, length);+ }+ if (crc != original_crc) error();+ */+ unsigned long update_crc(unsigned long crc,+ unsigned char *buf, int len)+ {+ unsigned long c = crc ^ 0xffffffffL;+ int n;++ if (!crc_table_computed)+ make_crc_table();+ for (n = 0; n < len; n++) {+ c = crc_table[(c ^ buf[n]) & 0xff] ^ (c >> 8);+ }+ return c ^ 0xffffffffL;+ }++ /* Return the CRC of the bytes buf[0..len-1]. */+ unsigned long crc(unsigned char *buf, int len)+ {+ return update_crc(0L, buf, len);+ }+++++Deutsch Informational [Page 12]++</pre><br />+ <span class="noprint"><small><small>Html markup produced by rfcmarkup 1.119, available from+ <a href="https://tools.ietf.org/tools/rfcmarkup/">https://tools.ietf.org/tools/rfcmarkup/</a>+ </small></small></span>+ </div>+</body>+</html>
+ test/test-cases/rfctest3.z view
binary file changed (absent → 10928 bytes)
+ test/test-cases/tor-list.gold view
file too large to diff
+ test/test-cases/tor-list.z view
file too large to diff
+ test/test-cases/zerotest1.gold view
binary file changed (absent → 4096 bytes)
+ test/test-cases/zerotest1.z view
binary file changed (absent → 26 bytes)
+ test/test-cases/zerotest2.gold view
binary file changed (absent → 65536 bytes)
+ test/test-cases/zerotest2.z view
binary file changed (absent → 84 bytes)
+ test/test-cases/zerotest3.gold view
binary file changed (absent → 1048576 bytes)
+ test/test-cases/zerotest3.z view
binary file changed (absent → 1039 bytes)