packages feed

lz4 0.1.0.1 → 0.2

raw patch · 15 files changed

+2119/−129 lines, 15 filesdep +cerealdep +criteriondep +deepseqdep −hspec-discoverdep −hspec-shouldbedep ~base

Dependencies added: cereal, criterion, deepseq, quicklz, snappy

Dependencies removed: hspec-discover, hspec-shouldbe

Dependency ranges changed: base

Files

+ AUTHORS.txt view
@@ -0,0 +1,3 @@+Mark Wotton <mwotton [@at] gmail [dot] com>+Simon Hengel <sol [@at] typeful [dot] net>+Austin Seipp <mad [dot] one [@at] gmail [dot] com>
− LICENSE 
@@ -1,30 +0,0 @@-Copyright (c) 2012, Mark Wotton--All rights reserved.--Redistribution and use in source and binary forms, with or without-modification, are permitted provided that the following conditions are met:--    * Redistributions of source code must retain the above copyright-      notice, this list of conditions and the following disclaimer.--    * Redistributions in binary form must reproduce the above-      copyright notice, this list of conditions and the following-      disclaimer in the documentation and/or other materials provided-      with the distribution.--    * Neither the name of Mark Wotton nor the names of other-      contributors may be used to endorse or promote products derived-      from this software without specific prior written permission.--THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS-"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT-LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR-A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT-OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,-SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT-LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,-DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY-THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT-(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE-OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ LICENSE.txt view
@@ -0,0 +1,31 @@+Copyright (c) 2012, Mark Wotton++All rights reserved.++Redistribution and use in source and binary forms, with or without+modification, are permitted provided that the following conditions are+met:++    * Redistributions of source code must retain the above copyright+      notice, this list of conditions and the following disclaimer.++    * Redistributions in binary form must reproduce the above+      copyright notice, this list of conditions and the following+      disclaimer in the documentation and/or other materials provided+      with the distribution.++    * Neither the name of Mark Wotton nor the names of other+      contributors may be used to endorse or promote products derived+      from this software without specific prior written permission.++THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS+"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT+LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR+A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT+OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,+SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT+LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,+DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY+THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE+OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ README.md view
@@ -0,0 +1,36 @@+# Fast compression for Haskell ByteStrings++This library implements Haskell bindings to [lz4][], a fast+compression library.++[travis-ci.org](http://travis-ci.org) results: [![Build Status](https://secure.travis-ci.org/mwotton/lz4hs.png?branch=master)](http://travis-ci.org/mwotton/lz4hs)++# Installation++It's just a `cabal install` away on [Hackage][]:++```bash+$ cabal install lz4+```++# Join in++File bugs in the GitHub [issue tracker][].++Master [git repository][gh]:++* `git clone https://github.com/mwotton/lz4hs.git`++# Authors++See `AUTHORS.txt`.++# License.++BSD3. See `LICENSE.txt` for terms of copyright and redistribution.++[lz4]: http://code.google.com/p/lz4+[issue tracker]: https://github.com/mwotton/lz4hs/issues+[gh]: https://github.com/mwotton/lz4hs+[bb]: http://bitbucket.org/mwotton/lz4hs+[Hackage]: http://hackage.haskell.org/package/lz4c
+ bench/Bench1.hs view
@@ -0,0 +1,32 @@+module Main+       ( main -- :: IO ()+       ) where+import Prelude hiding (words)++import qualified Data.ByteString           as S+import qualified Codec.Compression.Snappy  as Snappy+import qualified Codec.Compression.QuickLZ as QuickLZ+import qualified Codec.Compression.LZ4     as LZ4++import Criterion.Main+import Criterion.Config+import Control.DeepSeq (NFData)+++instance NFData S.ByteString+++main :: IO ()+main = do+  words <- S.readFile "/usr/share/dict/words"++  let cfg = defaultConfig { cfgPerformGC = ljust True }+  defaultMainWith cfg (return ())+    [ bgroup "/usr/share/dict/words"+      [ bench "snappy"    $ nf Snappy.compress words+      , bench "quicklz"   $ nf QuickLZ.compress words+      , bench "lz4"       $ nf LZ4.compress words+      , bench "lz4 HC"    $ nf LZ4.compressHC words+      , bench "lz4 ultra" $ nf LZ4.compressPlusHC words+      ]+    ]
lz4.cabal view
@@ -1,34 +1,71 @@ name:                lz4-version:             0.1.0.1-synopsis:            Haskell bindings to the lz4 compression library-description:         lz4 is a fast compression library, and can be found at-                     http://code.google.com/p/lz4/-                     a version that adds a C library can be found at-                     https://github.com/mwotton/lz4+version:             0.2+synopsis:            LZ4 compression for ByteStrings+description:+  High level bindings to the LZ4 compression library.+  .+  Currently based on lz4 r75. C sources are included and no external+  dependencies are needed other than @cereal@. homepage:            http://github.com/mwotton/lz4hs+bug-reports:         https://github.com/mwotton/lz4hs/issues license:             BSD3-license-file:        LICENSE-author:              Mark Wotton+license-file:        LICENSE.txt+copyright:           Copyright (c) Mark Wotton, Austin Seipp 2012+author:              Mark Wotton <mwotton@gmail.com) maintainer:          mwotton@gmail.com- category:            Codec build-type:          Simple-cabal-version:       >=1.8+cabal-version:       >=1.10++extra-source-files:+  src/cbits/lz4.h, src/cbits/lz4.c,+  src/cbits/lz4hc.h, src/cbits/lz4hc.c+  tests/Properties.hs,+  README.md, AUTHORS.txt+ source-repository head-  type:        git-  location:    git://github.com/mwotton/lz4hs.git+  type: git+  location: https://github.com/mwotton/lz4hs  library-  exposed-modules: Codec.Compression.LZ4-  other-modules:   Codec.Compression.LZ4.Foreign   hs-source-dirs:  src-  extra-libraries: lz4-  build-depends:   base ==4.5.*, bytestring+  exposed-modules: Codec.Compression.LZ4+  build-depends:+    base >= 3 && < 5,+    bytestring,+    cereal -test-suite spec-  type:            exitcode-stdio-1.0-  main-is:         Spec.hs-  hs-source-dirs:  test-  extra-libraries: lz4-  build-depends:   base, hspec, hspec-discover, lz4, QuickCheck, hspec-shouldbe,-                   bytestring+  c-sources:       src/cbits/lz4.c src/cbits/lz4hc.c+  include-dirs:    src/cbits++  ghc-options:     -Wall -O2 -fwarn-tabs+  default-language: Haskell2010++test-suite properties+  hs-source-dirs: tests+  main-is:        Properties.hs+  type:           exitcode-stdio-1.0++  build-depends:+    base >= 3 && < 5,+    bytestring,+    hspec, QuickCheck,+    lz4++  ghc-options:      -fno-cse -fwarn-tabs+  default-language: Haskell2010++benchmark bench1+  hs-source-dirs: bench+  main-is:        Bench1.hs+  type:           exitcode-stdio-1.0++  build-depends:+    base           >= 4,+    bytestring,+    deepseq,+    criterion,+    lz4, quicklz, snappy++  ghc-options:      -Wall -fno-warn-orphans+  default-language: Haskell2010
− src/Codec/Compression/LZ4.hs 
@@ -1,52 +0,0 @@--- | This is a binding to the LZ4 library, source of which can be found at--- http://code.google.com/p/lz4/------ Following zlib's lead, we pretend to be total on Bytestrings--- errors may be thrown for bad formats. I'm not entirely comfortable with this,--- but I'd like it to be a drop-in replacement for ease of use.------ TODO: use a standard chunk size & support lazy Bytestrings, pending Yann's--- publication of a formal standard.--module Codec.Compression.LZ4 (compress, compressHC, uncompress) where-import Codec.Compression.LZ4.Foreign-import System.IO.Unsafe (unsafePerformIO)-import Foreign.Marshal.Alloc(allocaBytes)-import Foreign.C.String-import Data.ByteString-import Data.ByteString.Unsafe--- import Debug.Trace---- |  Compresses a LZ4-packed String using the slow, better packing.-compressHC :: ByteString -> ByteString-compressHC x = compressWorker c_LZ4_compressHC x---- |  Compresses a LZ4-packed String-compress :: ByteString -> ByteString-compress x = compressWorker c_LZ4_compress x--compressWorker :: Num b => (CString -> CString -> b -> IO Int) -> ByteString -> ByteString-compressWorker compressor x = unsafePerformIO $ unsafeUseAsCStringLen x $ \(input,len) ->-  let outLen = c_LZ4_compressBound len in-  allocaBytes (1+outLen) $ \out -> do-    written <- compressor input out (fromIntegral len)-    if written == 0-      then error "compression failed"-      else packCStringLen (out, written)-           --  `doTrace` ("compress", x, len, outLen, written)---- |  Uncompresses a LZ4-packed String---    No chunking yet - Yann is still working on a framing.---    As a dirty hack, we assume that it won't decompress to more than 5 times---    the length of the compressed file - this will go away with a fixed---    frame size-uncompress :: ByteString -> ByteString-uncompress x = unsafePerformIO $ unsafeUseAsCStringLen x $ \(input,len) ->-  let outLen = 5 * len in-  allocaBytes (1+outLen) $ \out -> do-    written <- c_LZ4_uncompress_unknownOutputSize input out-                 (fromIntegral len)-                 (fromIntegral outLen)-    if written < 0-      then error "decompression failed!"-      else packCStringLen (out, written)
+ src/Codec/Compression/LZ4.hsc view
@@ -0,0 +1,213 @@+{-# LANGUAGE CPP #-}+-- |+-- Module      : Codec.Compression.LZ4+-- Copyright   : (c) Mark Wotton, Austin Seipp 2012+-- License     : BSD3+--+-- Maintainer  : mwotton@gmail.com+-- Stability   : experimental+-- Portability : portable+--+-- This module provides a high level 'ByteString' interface to the+-- lz4 library. More information about lz4 can be found here:+-- <http://code.google.com/p/lz4/>.+--+-- This module prefixes the buffer that is compressed with the+-- uncompressed length (as lz4 can't recover this information+-- itself.) It also has this property: all functions when+-- called with an empty string return @Just Data.ByteString.empty@+--+module Codec.Compression.LZ4+       ( -- * High level interface+         -- ** Compressing and decompressing strict 'ByteString's+         compress            -- :: S.ByteString -> S.ByteString+       , decompress          -- :: S.ByteString -> Maybe S.ByteString++         -- ** High-compression mode+       , compressHC          -- :: S.ByteString -> S.ByteString++         -- ** Compression + HC mode+       , compressPlusHC      -- :: S.ByteString -> S.ByteString+       , decompressPlusHC    -- :: S.ByteString -> S.ByteString++         -- * FFI functions+       , c_LZ4_compress      -- :: Ptr CChar -> Ptr Word8 -> CInt -> IO CInt+       , c_LZ4_compressHC    -- :: Ptr CChar -> Ptr Word8 -> CInt -> IO CInt+       , c_LZ4_uncompress    -- :: Ptr CChar -> Ptr Word8 -> CInt -> IO CInt+       , c_LZ4_compressBound -- :: CInt -> CInt+       ) where++import Prelude hiding (max)+import Data.Word+import Foreign.Ptr+import Foreign.C+import System.IO.Unsafe (unsafePerformIO)+import Control.Applicative++import qualified Data.ByteString as S+import qualified Data.ByteString.Internal as SI+import qualified Data.ByteString.Unsafe as U++import Data.Serialize++#include <lz4.h>+#include <lz4hc.h>+++--------------------------------------------------------------------------------+-- Compression++-- | Compresses the input 'ByteString'.+--+-- Will return 'Nothing' if the compression fails. Otherwise, returns+-- @Just xs@ with the compressed string (and additionally, if @xs ==+-- empty@ then @compress empty == Just empty@.)+compress :: S.ByteString -> Maybe S.ByteString+compress xs+  | S.null xs = Just S.empty+  | otherwise = compressor c_LZ4_compress xs+{-# INLINEABLE compress #-}++-- | Compress the input 'ByteString' as much as possible, but comes+-- with a massive speed drop in compression. Decompression is faster+-- however and can be done with 'decompress'.+--+-- Will return 'Nothing' if the compression fails. Otherwise, returns+-- @Just xs@ with the compressed string (and additionally, if @xs ==+-- empty@ then @compressHC empty == Just empty@.)+compressHC :: S.ByteString -> Maybe S.ByteString+compressHC xs+  | S.null xs = Just S.empty+  | otherwise = compressor c_LZ4_compressHC xs+{-# INLINEABLE compressHC #-}++-- | Essentially defined as:+--+-- > compressPlusHC xs = compress xs >>= compressHC+--+--+-- This is an experimental interface. After regular compression, due+-- to output encoding, things like relative offsets in the compression+-- buffer or artifacts from number encoding can end up the same in the+-- output buffer for often repeated data. Therefore, further savings+-- are possible in the input buffer by compressing again. lz4 even in+-- high compression mode will quickly ignore already-compressed data+-- and remain quite fast. Thus, this interface is designed to give a+-- better compression/speed tradeoff than 'compressHC': it doesn't+-- compress as well, but is nowhere near as slow. Some context:+-- <http://www.reddit.com/r/programming/comments/vyu7r/compressing_log_files_twice_improves_ratio/c58svj3?context=3>+--+-- Must be decompressed with 'decompressPlusHC'.+--+-- Will return 'Nothing' if the compression fails. Otherwise, returns+-- @Just xs@ with the compressed string (and additionally, if @xs ==+-- empty@ then @compressPlusHC empty == Just empty@.)+compressPlusHC :: S.ByteString -> Maybe S.ByteString+compressPlusHC xs+  | S.null xs = Just S.empty+  | otherwise = compress xs >>= compressHC+{-# INLINEABLE compressPlusHC #-}+++--------------------------------------------------------------------------------+-- Decompression++-- | Decompress the input 'ByteString'.+decompress :: S.ByteString -> Maybe S.ByteString+decompress xs+  | S.null xs = Just S.empty+  | otherwise =+      -- Get the length of the uncompressed buffer and do our thing+      either (const Nothing) (unsafePerformIO . go) $ runGet unformat xs+  where go (l, str) =+          U.unsafeUseAsCString str $ \cstr -> do+            out <- SI.createAndTrim l $ \p -> do+              r <- fromIntegral <$> c_LZ4_uncompress cstr p (fromIntegral l)+              return $! if (r <= 0) then 0 else r+            return $! if (S.null out) then Nothing else (Just out)+{-# INLINEABLE decompress #-}++-- | Decompress a string compressed with 'compressPlusHC'. Essentially+-- defined as:+-- +-- > decompressPlusHC xs = decompress xs >>= decompress+-- +decompressPlusHC :: S.ByteString -> Maybe S.ByteString+decompressPlusHC xs+  | S.null xs = Just S.empty+  | otherwise = decompress xs >>= decompress+{-# INLINEABLE decompressPlusHC #-}+++--------------------------------------------------------------------------------+-- Utilities++-- The compression methods are all identical, so this just abstracts them+compressor :: (Ptr CChar -> Ptr Word8 -> CInt -> IO CInt)+           -> S.ByteString+           -> Maybe S.ByteString+compressor f xs = unsafePerformIO $ do+  U.unsafeUseAsCStringLen xs $ \(cstr,len) -> do+    let len' = fromIntegral len :: CInt+    let max = c_LZ4_compressBound len'+    bs <- SI.createAndTrim (fromIntegral max) $ \output ->+            fromIntegral <$> f cstr output len'+    return $ if S.null bs then Nothing else+               -- Prefix the compressed string with the uncompressed length+               Just $ runPut $ format (fromIntegral len) bs+{-# INLINEABLE compressor #-}++-- Pushes a Word32 and a ByteString into the format we use to correctly+-- encode/decode.+format :: Word32 -> Putter S.ByteString+format l xs = do+  putWord32le l+  putWord32le (fromIntegral $ S.length xs)+  putByteString xs++-- Gets a ByteString and it's length from the compressed format.+unformat :: Get (Int, S.ByteString)+unformat = do+  c <-  fromIntegral <$> getWord32le+  l  <- fromIntegral <$> getWord32le+  bs <- getByteString l+  return (c, bs)+++--------------------------------------------------------------------------------+-- FFI Bindings++-- In lz4 r71, LZ4_compressBound was changed to a macro. This is identical to+-- that macro so we don't have to go through C land just to get at it.+--+-- NB: MUST *ALWAYS* BE KEPT IN SYNC WITH lz4.h!++--foreign import ccall unsafe "lz4.h LZ4_compressBound"+--  c_LZ4_compressBound :: CInt -> IO CInt+-- | Worst case compression bounds on an input string.+c_LZ4_compressBound :: CInt -- ^ String length+                    -> CInt -- ^ Worst-case size+c_LZ4_compressBound sz = sz + (sz `div` 255) + 16+{-# INLINE c_LZ4_compressBound #-}++-- | Compresses a string.+foreign import ccall unsafe "lz4.h LZ4_compress"+  c_LZ4_compress :: Ptr CChar -- ^ Source+                 -> Ptr Word8 -- ^ Dest+                 -> CInt      -- ^ Input size+                 -> IO CInt   -- ^ Result++-- | Compresses a string with very high compression.+foreign import ccall unsafe "lz4hc.h LZ4_compressHC"+  c_LZ4_compressHC :: Ptr CChar -- ^ Source+                   -> Ptr Word8 -- ^ Dest+                   -> CInt      -- ^ Input size+                   -> IO CInt   -- ^ Result++-- | Decompresses a string. Works for both 'c_LZ4_compress' and+-- 'c_LZ4_compressHC'.+foreign import ccall unsafe "lz4.h LZ4_uncompress"+  c_LZ4_uncompress :: Ptr CChar -- ^ Source+                   -> Ptr Word8 -- ^ Dest+                   -> CInt      -- ^ Size of ORIGINAL INPUT+                   -> IO CInt   -- ^ Result
− src/Codec/Compression/LZ4/Foreign.hs 
@@ -1,22 +0,0 @@-{-# LANGUAGE ForeignFunctionInterface #-}-module Codec.Compression.LZ4.Foreign (-  c_LZ4_compress,-  c_LZ4_compressHC,-  c_LZ4_uncompress_unknownOutputSize, -  c_LZ4_compressBound) where--import Foreign-import Foreign.C.Types-import Foreign.C.String--foreign import ccall "lz4.h LZ4_compress"-      c_LZ4_compress :: CString -> CString -> CInt -> IO Int--foreign import ccall "lz4hc.h LZ4_compressHC"-      c_LZ4_compressHC :: CString -> CString -> CInt -> IO Int--foreign import ccall "lz4.h LZ4_uncompress_unknownOutputSize"-  c_LZ4_uncompress_unknownOutputSize :: CString -> CString -> CInt -> CInt -> IO Int--foreign import ccall "lz4.h LZ4_compressBound"-      c_LZ4_compressBound :: Int -> Int
+ src/cbits/lz4.c view
@@ -0,0 +1,860 @@+/*+   LZ4 - Fast LZ compression algorithm+   Copyright (C) 2011-2012, Yann Collet.+   BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)++   Redistribution and use in source and binary forms, with or without+   modification, are permitted provided that the following conditions are+   met:++       * Redistributions of source code must retain the above copyright+   notice, this list of conditions and the following disclaimer.+       * Redistributions in binary form must reproduce the above+   copyright notice, this list of conditions and the following disclaimer+   in the documentation and/or other materials provided with the+   distribution.++   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS+   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT+   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR+   A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT+   OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,+   SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT+   LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,+   DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY+   THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT+   (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE+   OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.++   You can contact the author at :+   - LZ4 homepage : http://fastcompression.blogspot.com/p/lz4.html+   - LZ4 source repository : http://code.google.com/p/lz4/+*/++//**************************************+// Tuning parameters+//**************************************+// MEMORY_USAGE :+// Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.)+// Increasing memory usage improves compression ratio+// Reduced memory usage can improve speed, due to cache effect+// Default value is 14, for 16KB, which nicely fits into Intel x86 L1 cache+#define MEMORY_USAGE 14++// NOTCOMPRESSIBLE_DETECTIONLEVEL :+// Decreasing this value will make the algorithm skip faster data segments considered "incompressible"+// This may decrease compression ratio dramatically, but will be faster on incompressible data+// Increasing this value will make the algorithm search more before declaring a segment "incompressible"+// This could improve compression a bit, but will be slower on incompressible data+// The default value (6) is recommended+#define NOTCOMPRESSIBLE_DETECTIONLEVEL 6++// BIG_ENDIAN_NATIVE_BUT_INCOMPATIBLE :+// This will provide a small boost to performance for big endian cpu, but the resulting compressed stream will be incompatible with little-endian CPU.+// You can set this option to 1 in situations where data will remain within closed environment+// This option is useless on Little_Endian CPU (such as x86)+//#define BIG_ENDIAN_NATIVE_BUT_INCOMPATIBLE 1++++//**************************************+// CPU Feature Detection+//**************************************+// 32 or 64 bits ?+#if (defined(__x86_64__) || defined(__x86_64) || defined(__amd64__) || defined(__amd64) || defined(__ppc64__) || defined(_WIN64) || defined(__LP64__) || defined(_LP64) )   // Detects 64 bits mode+#  define LZ4_ARCH64 1+#else+#  define LZ4_ARCH64 0+#endif++// Little Endian or Big Endian ?+// Note : overwrite the below #define if you know your architecture endianess+#if (defined(__BIG_ENDIAN__) || defined(__BIG_ENDIAN) || defined(_BIG_ENDIAN) || defined(_ARCH_PPC) || defined(__PPC__) || defined(__PPC) || defined(PPC) || defined(__powerpc__) || defined(__powerpc) || defined(powerpc) || ((defined(__BYTE_ORDER__)&&(__BYTE_ORDER__ == __ORDER_BIG_ENDIAN__))) )+#  define LZ4_BIG_ENDIAN 1+#else+// Little Endian assumed. PDP Endian and other very rare endian format are unsupported.+#endif++// Unaligned memory access is automatically enabled for "common" CPU, such as x86.+// For others CPU, the compiler will be more cautious, and insert extra code to ensure aligned access is respected+// If you know your target CPU supports unaligned memory access, you may want to force this option manually to improve performance+#if defined(__ARM_FEATURE_UNALIGNED)+#  define LZ4_FORCE_UNALIGNED_ACCESS 1+#endif++// Define this parameter if your target system or compiler does not support hardware bit count+#if defined(_MSC_VER) && defined(_WIN32_WCE)            // Visual Studio for Windows CE does not support Hardware bit count+#  define LZ4_FORCE_SW_BITCOUNT+#endif+++//**************************************+// Compiler Options+//**************************************+#if __STDC_VERSION__ >= 199901L // C99+/* "restrict" is a known keyword */+#else+#  define restrict // Disable restrict+#endif++#define GCC_VERSION (__GNUC__ * 100 + __GNUC_MINOR__)++#ifdef _MSC_VER  // Visual Studio+#  define inline __forceinline           // Visual is not C99, but supports some kind of inline+#  include <intrin.h>   // For Visual 2005+#  if LZ4_ARCH64	// 64-bit+#    pragma intrinsic(_BitScanForward64) // For Visual 2005+#    pragma intrinsic(_BitScanReverse64) // For Visual 2005+#  else+#    pragma intrinsic(_BitScanForward)   // For Visual 2005+#    pragma intrinsic(_BitScanReverse)   // For Visual 2005+#  endif+#endif++#ifdef _MSC_VER+#  define lz4_bswap16(x) _byteswap_ushort(x)+#else+#  define lz4_bswap16(x) ((unsigned short int) ((((x) >> 8) & 0xffu) | (((x) & 0xffu) << 8)))+#endif++#if (GCC_VERSION >= 302) || (__INTEL_COMPILER >= 800) || defined(__clang__)+#  define expect(expr,value)    (__builtin_expect ((expr),(value)) )+#else+#  define expect(expr,value)    (expr)+#endif++#define likely(expr)     expect((expr) != 0, 1)+#define unlikely(expr)   expect((expr) != 0, 0)+++//**************************************+// Includes+//**************************************+#include <stdlib.h>   // for malloc+#include <string.h>   // for memset+#include "lz4.h"+++//**************************************+// Basic Types+//**************************************+#if defined(_MSC_VER)    // Visual Studio does not support 'stdint' natively+#  define BYTE	unsigned __int8+#  define U16		unsigned __int16+#  define U32		unsigned __int32+#  define S32		__int32+#  define U64		unsigned __int64+#else+#  include <stdint.h>+#  define BYTE	uint8_t+#  define U16		uint16_t+#  define U32		uint32_t+#  define S32		int32_t+#  define U64		uint64_t+#endif++#ifndef LZ4_FORCE_UNALIGNED_ACCESS+#  pragma pack(push, 1)+#endif++typedef struct _U16_S { U16 v; } U16_S;+typedef struct _U32_S { U32 v; } U32_S;+typedef struct _U64_S { U64 v; } U64_S;++#ifndef LZ4_FORCE_UNALIGNED_ACCESS+#  pragma pack(pop)+#endif++#define A64(x) (((U64_S *)(x))->v)+#define A32(x) (((U32_S *)(x))->v)+#define A16(x) (((U16_S *)(x))->v)+++//**************************************+// Constants+//**************************************+#define MINMATCH 4++#define HASH_LOG (MEMORY_USAGE-2)+#define HASHTABLESIZE (1 << HASH_LOG)+#define HASH_MASK (HASHTABLESIZE - 1)++#define SKIPSTRENGTH (NOTCOMPRESSIBLE_DETECTIONLEVEL>2?NOTCOMPRESSIBLE_DETECTIONLEVEL:2)+#define STACKLIMIT 13+#define HEAPMODE (HASH_LOG>STACKLIMIT)  // Defines if memory is allocated into the stack (local variable), or into the heap (malloc()).+#define COPYLENGTH 8+#define LASTLITERALS 5+#define MFLIMIT (COPYLENGTH+MINMATCH)+#define MINLENGTH (MFLIMIT+1)++#define MAXD_LOG 16+#define MAX_DISTANCE ((1 << MAXD_LOG) - 1)++#define ML_BITS 4+#define ML_MASK ((1U<<ML_BITS)-1)+#define RUN_BITS (8-ML_BITS)+#define RUN_MASK ((1U<<RUN_BITS)-1)+++//**************************************+// Architecture-specific macros+//**************************************+#if LZ4_ARCH64	// 64-bit+#  define STEPSIZE 8+#  define UARCH U64+#  define AARCH A64+#  define LZ4_COPYSTEP(s,d)		A64(d) = A64(s); d+=8; s+=8;+#  define LZ4_COPYPACKET(s,d)		LZ4_COPYSTEP(s,d)+#  define LZ4_SECURECOPY(s,d,e)	if (d<e) LZ4_WILDCOPY(s,d,e)+#  define HTYPE U32+#  define INITBASE(base)			const BYTE* const base = ip+#else		// 32-bit+#  define STEPSIZE 4+#  define UARCH U32+#  define AARCH A32+#  define LZ4_COPYSTEP(s,d)		A32(d) = A32(s); d+=4; s+=4;+#  define LZ4_COPYPACKET(s,d)		LZ4_COPYSTEP(s,d); LZ4_COPYSTEP(s,d);+#  define LZ4_SECURECOPY			LZ4_WILDCOPY+#  define HTYPE const BYTE*+#  define INITBASE(base)			const int base = 0+#endif++#if (defined(LZ4_BIG_ENDIAN) && !defined(BIG_ENDIAN_NATIVE_BUT_INCOMPATIBLE))+#  define LZ4_READ_LITTLEENDIAN_16(d,s,p) { U16 v = A16(p); v = lz4_bswap16(v); d = (s) - v; }+#  define LZ4_WRITE_LITTLEENDIAN_16(p,i)  { U16 v = (U16)(i); v = lz4_bswap16(v); A16(p) = v; p+=2; }+#else		// Little Endian+#  define LZ4_READ_LITTLEENDIAN_16(d,s,p) { d = (s) - A16(p); }+#  define LZ4_WRITE_LITTLEENDIAN_16(p,v)  { A16(p) = v; p+=2; }+#endif+++//**************************************+// Local structures+//**************************************+struct refTables+{+	HTYPE hashTable[HASHTABLESIZE];+};+++//**************************************+// Macros+//**************************************+#define LZ4_HASH_FUNCTION(i)	(((i) * 2654435761U) >> ((MINMATCH*8)-HASH_LOG))+#define LZ4_HASH_VALUE(p)		LZ4_HASH_FUNCTION(A32(p))+#define LZ4_WILDCOPY(s,d,e)		do { LZ4_COPYPACKET(s,d) } while (d<e);+#define LZ4_BLINDCOPY(s,d,l)	{ BYTE* e=(d)+l; LZ4_WILDCOPY(s,d,e); d=e; }+++//****************************+// Private functions+//****************************+#if LZ4_ARCH64++static inline int LZ4_NbCommonBytes (register U64 val)+{+#if defined(LZ4_BIG_ENDIAN)+    #if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)+    unsigned long r = 0;+    _BitScanReverse64( &r, val );+    return (int)(r>>3);+    #elif defined(__GNUC__) && (GCC_VERSION >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT)+    return (__builtin_clzll(val) >> 3);+    #else+	int r;+	if (!(val>>32)) { r=4; } else { r=0; val>>=32; }+	if (!(val>>16)) { r+=2; val>>=8; } else { val>>=24; }+	r += (!val);+	return r;+    #endif+#else+    #if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)+    unsigned long r = 0;+    _BitScanForward64( &r, val );+    return (int)(r>>3);+    #elif defined(__GNUC__) && (GCC_VERSION >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT)+    return (__builtin_ctzll(val) >> 3);+    #else+	static const int DeBruijnBytePos[64] = { 0, 0, 0, 0, 0, 1, 1, 2, 0, 3, 1, 3, 1, 4, 2, 7, 0, 2, 3, 6, 1, 5, 3, 5, 1, 3, 4, 4, 2, 5, 6, 7, 7, 0, 1, 2, 3, 3, 4, 6, 2, 6, 5, 5, 3, 4, 5, 6, 7, 1, 2, 4, 6, 4, 4, 5, 7, 2, 6, 5, 7, 6, 7, 7 };+	return DeBruijnBytePos[((U64)((val & -val) * 0x0218A392CDABBD3F)) >> 58];+    #endif+#endif+}++#else++static inline int LZ4_NbCommonBytes (register U32 val)+{+#if defined(LZ4_BIG_ENDIAN)+    #if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)+    unsigned long r = 0;+    _BitScanReverse( &r, val );+    return (int)(r>>3);+    #elif defined(__GNUC__) && (GCC_VERSION >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT)+    return (__builtin_clz(val) >> 3);+    #else+	int r;+	if (!(val>>16)) { r=2; val>>=8; } else { r=0; val>>=24; }+	r += (!val);+	return r;+    #endif+#else+    #if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)+    unsigned long r = 0;+    _BitScanForward( &r, val );+    return (int)(r>>3);+    #elif defined(__GNUC__) && (GCC_VERSION >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT)+    return (__builtin_ctz(val) >> 3);+    #else+	static const int DeBruijnBytePos[32] = { 0, 0, 3, 0, 3, 1, 3, 0, 3, 2, 2, 1, 3, 2, 0, 1, 3, 3, 1, 2, 2, 2, 2, 0, 3, 1, 2, 0, 1, 0, 1, 1 };+	return DeBruijnBytePos[((U32)((val & -(S32)val) * 0x077CB531U)) >> 27];+    #endif+#endif+}++#endif++++//******************************+// Compression functions+//******************************++// LZ4_compressCtx :+// -----------------+// Compress 'isize' bytes from 'source' into an output buffer 'dest' of maximum size 'maxOutputSize'.+// If it cannot achieve it, compression will stop, and result of the function will be zero.+// return : the number of bytes written in buffer 'dest', or 0 if the compression fails++static inline int LZ4_compressCtx(void** ctx,+				 const char* source,+				 char* dest,+				 int isize,+				 int maxOutputSize)+{+#if HEAPMODE+	struct refTables *srt = (struct refTables *) (*ctx);+	HTYPE* HashTable;+#else+	HTYPE HashTable[HASHTABLESIZE] = {0};+#endif++	const BYTE* ip = (BYTE*) source;+	INITBASE(base);+	const BYTE* anchor = ip;+	const BYTE* const iend = ip + isize;+	const BYTE* const mflimit = iend - MFLIMIT;+#define matchlimit (iend - LASTLITERALS)++	BYTE* op = (BYTE*) dest;+	BYTE* const oend = op + maxOutputSize;++	int len, length;+	const int skipStrength = SKIPSTRENGTH;+	U32 forwardH;+++	// Init+	if (isize<MINLENGTH) goto _last_literals;+#if HEAPMODE+	if (*ctx == NULL)+	{+		srt = (struct refTables *) malloc ( sizeof(struct refTables) );+		*ctx = (void*) srt;+	}+	HashTable = (HTYPE*)(srt->hashTable);+	memset((void*)HashTable, 0, sizeof(srt->hashTable));+#else+	(void) ctx;+#endif+++	// First Byte+	HashTable[LZ4_HASH_VALUE(ip)] = ip - base;+	ip++; forwardH = LZ4_HASH_VALUE(ip);++	// Main Loop+    for ( ; ; )+	{+		int findMatchAttempts = (1U << skipStrength) + 3;+		const BYTE* forwardIp = ip;+		const BYTE* ref;+		BYTE* token;++		// Find a match+		do {+			U32 h = forwardH;+			int step = findMatchAttempts++ >> skipStrength;+			ip = forwardIp;+			forwardIp = ip + step;++			if unlikely(forwardIp > mflimit) { goto _last_literals; }++			forwardH = LZ4_HASH_VALUE(forwardIp);+			ref = base + HashTable[h];+			HashTable[h] = ip - base;++		} while ((ref < ip - MAX_DISTANCE) || (A32(ref) != A32(ip)));++		// Catch up+		while ((ip>anchor) && (ref>(BYTE*)source) && unlikely(ip[-1]==ref[-1])) { ip--; ref--; }++		// Encode Literal length+		length = (int)(ip - anchor);+		token = op++;+		if unlikely(op + length + (2 + 1 + LASTLITERALS) + (length>>8) >= oend) return 0; 		// Check output limit+#ifdef _MSC_VER+		if (length>=(int)RUN_MASK) +		{ +			int len = length-RUN_MASK; +			*token=(RUN_MASK<<ML_BITS); +			if (len>254)+			{+				do { *op++ = 255; len -= 255; } while (len>254);+				*op++ = (BYTE)len; +				memcpy(op, anchor, length);+				op += length;+				goto _next_match;+			}+			else+			*op++ = (BYTE)len; +		}+		else *token = (length<<ML_BITS);+#else+		if (length>=(int)RUN_MASK) { *token=(RUN_MASK<<ML_BITS); len = length-RUN_MASK; for(; len > 254 ; len-=255) *op++ = 255; *op++ = (BYTE)len; }+		else *token = (length<<ML_BITS);+#endif++		// Copy Literals+		LZ4_BLINDCOPY(anchor, op, length);++_next_match:+		// Encode Offset+		LZ4_WRITE_LITTLEENDIAN_16(op,(U16)(ip-ref));++		// Start Counting+		ip+=MINMATCH; ref+=MINMATCH;   // MinMatch verified+		anchor = ip;+		while likely(ip<matchlimit-(STEPSIZE-1))+		{+			UARCH diff = AARCH(ref) ^ AARCH(ip);+			if (!diff) { ip+=STEPSIZE; ref+=STEPSIZE; continue; }+			ip += LZ4_NbCommonBytes(diff);+			goto _endCount;+		}+		if (LZ4_ARCH64) if ((ip<(matchlimit-3)) && (A32(ref) == A32(ip))) { ip+=4; ref+=4; }+		if ((ip<(matchlimit-1)) && (A16(ref) == A16(ip))) { ip+=2; ref+=2; }+		if ((ip<matchlimit) && (*ref == *ip)) ip++;+_endCount:++		// Encode MatchLength+		len = (int)(ip - anchor);+		if (len>=(int)ML_MASK) { *token+=ML_MASK; len-=ML_MASK; for(; len > 509 ; len-=510) { *op++ = 255; *op++ = 255; } if (len > 254) { len-=255; *op++ = 255; } *op++ = (BYTE)len; }+		else *token += len;++		// Test end of chunk+		if (ip > mflimit) { anchor = ip;  break; }++		// Fill table+		HashTable[LZ4_HASH_VALUE(ip-2)] = ip - 2 - base;++		// Test next position+		ref = base + HashTable[LZ4_HASH_VALUE(ip)];+		HashTable[LZ4_HASH_VALUE(ip)] = ip - base;+		if ((ref > ip - (MAX_DISTANCE + 1)) && (A32(ref) == A32(ip))) { token = op++; *token=0; goto _next_match; }++		// Prepare next loop+		anchor = ip++;+		forwardH = LZ4_HASH_VALUE(ip);+	}++_last_literals:+	// Encode Last Literals+	{+		int lastRun = (int)(iend - anchor);+		if (((char*)op - dest) + lastRun + 1 + ((lastRun-15)/255) >= maxOutputSize) return 0;+		if (lastRun>=(int)RUN_MASK) { *op++=(RUN_MASK<<ML_BITS); lastRun-=RUN_MASK; for(; lastRun > 254 ; lastRun-=255) *op++ = 255; *op++ = (BYTE) lastRun; }+		else *op++ = (lastRun<<ML_BITS);+		memcpy(op, anchor, iend - anchor);+		op += iend-anchor;+	}++	// End+	return (int) (((char*)op)-dest);+}++++// Note : this function is valid only if isize < LZ4_64KLIMIT+#define LZ4_64KLIMIT ((1<<16) + (MFLIMIT-1))+#define HASHLOG64K (HASH_LOG+1)+#define HASH64KTABLESIZE (1U<<HASHLOG64K)+#define LZ4_HASH64K_FUNCTION(i)	(((i) * 2654435761U) >> ((MINMATCH*8)-HASHLOG64K))+#define LZ4_HASH64K_VALUE(p)	LZ4_HASH64K_FUNCTION(A32(p))+static inline int LZ4_compress64kCtx(void** ctx,+				 const char* source,+				 char* dest,+				 int isize,+				 int maxOutputSize)+{+#if HEAPMODE+	struct refTables *srt = (struct refTables *) (*ctx);+	U16* HashTable;+#else+	U16 HashTable[HASH64KTABLESIZE] = {0};+#endif++	const BYTE* ip = (BYTE*) source;+	const BYTE* anchor = ip;+	const BYTE* const base = ip;+	const BYTE* const iend = ip + isize;+	const BYTE* const mflimit = iend - MFLIMIT;+#define matchlimit (iend - LASTLITERALS)++	BYTE* op = (BYTE*) dest;+	BYTE* const oend = op + maxOutputSize;++	int len, length;+	const int skipStrength = SKIPSTRENGTH;+	U32 forwardH;+++	// Init+	if (isize<MINLENGTH) goto _last_literals;+#if HEAPMODE+	if (*ctx == NULL)+	{+		srt = (struct refTables *) malloc ( sizeof(struct refTables) );+		*ctx = (void*) srt;+	}+	HashTable = (U16*)(srt->hashTable);+	memset((void*)HashTable, 0, sizeof(srt->hashTable));+#else+	(void) ctx;+#endif+++	// First Byte+	ip++; forwardH = LZ4_HASH64K_VALUE(ip);++	// Main Loop+    for ( ; ; )+	{+		int findMatchAttempts = (1U << skipStrength) + 3;+		const BYTE* forwardIp = ip;+		const BYTE* ref;+		BYTE* token;++		// Find a match+		do {+			U32 h = forwardH;+			int step = findMatchAttempts++ >> skipStrength;+			ip = forwardIp;+			forwardIp = ip + step;++			if (forwardIp > mflimit) { goto _last_literals; }++			forwardH = LZ4_HASH64K_VALUE(forwardIp);+			ref = base + HashTable[h];+			HashTable[h] = (U16)(ip - base);++		} while (A32(ref) != A32(ip));++		// Catch up+		while ((ip>anchor) && (ref>(BYTE*)source) && (ip[-1]==ref[-1])) { ip--; ref--; }++		// Encode Literal length+		length = (int)(ip - anchor);+		token = op++;+		if unlikely(op + length + (2 + 1 + LASTLITERALS) + (length>>8) >= oend) return 0; 		// Check output limit+#ifdef _MSC_VER+		if (length>=(int)RUN_MASK) +		{ +			int len = length-RUN_MASK; +			*token=(RUN_MASK<<ML_BITS); +			if (len>254)+			{+				do { *op++ = 255; len -= 255; } while (len>254);+				*op++ = (BYTE)len; +				memcpy(op, anchor, length);+				op += length;+				goto _next_match;+			}+			else+			*op++ = (BYTE)len; +		}+		else *token = (length<<ML_BITS);+#else+		if (length>=(int)RUN_MASK) { *token=(RUN_MASK<<ML_BITS); len = length-RUN_MASK; for(; len > 254 ; len-=255) *op++ = 255; *op++ = (BYTE)len; }+		else *token = (length<<ML_BITS);+#endif++		// Copy Literals+		LZ4_BLINDCOPY(anchor, op, length);++_next_match:+		// Encode Offset+		LZ4_WRITE_LITTLEENDIAN_16(op,(U16)(ip-ref));++		// Start Counting+		ip+=MINMATCH; ref+=MINMATCH;   // MinMatch verified+		anchor = ip;+		while (ip<matchlimit-(STEPSIZE-1))+		{+			UARCH diff = AARCH(ref) ^ AARCH(ip);+			if (!diff) { ip+=STEPSIZE; ref+=STEPSIZE; continue; }+			ip += LZ4_NbCommonBytes(diff);+			goto _endCount;+		}+		if (LZ4_ARCH64) if ((ip<(matchlimit-3)) && (A32(ref) == A32(ip))) { ip+=4; ref+=4; }+		if ((ip<(matchlimit-1)) && (A16(ref) == A16(ip))) { ip+=2; ref+=2; }+		if ((ip<matchlimit) && (*ref == *ip)) ip++;+_endCount:++		// Encode MatchLength+		len = (int)(ip - anchor);+		if (len>=(int)ML_MASK) { *token+=ML_MASK; len-=ML_MASK; for(; len > 509 ; len-=510) { *op++ = 255; *op++ = 255; } if (len > 254) { len-=255; *op++ = 255; } *op++ = (BYTE)len; }+		else *token += len;++		// Test end of chunk+		if (ip > mflimit) { anchor = ip;  break; }++		// Fill table+		HashTable[LZ4_HASH64K_VALUE(ip-2)] = (U16)(ip - 2 - base);++		// Test next position+		ref = base + HashTable[LZ4_HASH64K_VALUE(ip)];+		HashTable[LZ4_HASH64K_VALUE(ip)] = (U16)(ip - base);+		if (A32(ref) == A32(ip)) { token = op++; *token=0; goto _next_match; }++		// Prepare next loop+		anchor = ip++;+		forwardH = LZ4_HASH64K_VALUE(ip);+	}++_last_literals:+	// Encode Last Literals+	{+		int lastRun = (int)(iend - anchor);+		if (((char*)op - dest) + lastRun + 1 + ((lastRun)>>8) >= maxOutputSize) return 0;+		if (lastRun>=(int)RUN_MASK) { *op++=(RUN_MASK<<ML_BITS); lastRun-=RUN_MASK; for(; lastRun > 254 ; lastRun-=255) *op++ = 255; *op++ = (BYTE) lastRun; }+		else *op++ = (lastRun<<ML_BITS);+		memcpy(op, anchor, iend - anchor);+		op += iend-anchor;+	}++	// End+	return (int) (((char*)op)-dest);+}+++int LZ4_compress_limitedOutput(const char* source, +							   char* dest, +							   int isize, +							   int maxOutputSize)+{+#if HEAPMODE+	void* ctx = malloc(sizeof(struct refTables));+	int result;+	if (isize < LZ4_64KLIMIT)+		result = LZ4_compress64kCtx(&ctx, source, dest, isize, maxOutputSize);+	else result = LZ4_compressCtx(&ctx, source, dest, isize, maxOutputSize);+	free(ctx);+	return result;+#else+	if (isize < (int)LZ4_64KLIMIT) return LZ4_compress64kCtx(NULL, source, dest, isize, maxOutputSize);+	return LZ4_compressCtx(NULL, source, dest, isize, maxOutputSize);+#endif+}+++int LZ4_compress(const char* source,+				 char* dest,+				 int isize)+{+	return LZ4_compress_limitedOutput(source, dest, isize, LZ4_compressBound(isize));+}+++++//****************************+// Decompression functions+//****************************++// Note : The decoding functions LZ4_uncompress() and LZ4_uncompress_unknownOutputSize()+//		are safe against "buffer overflow" attack type.+//		They will never write nor read outside of the provided output buffers.+//      LZ4_uncompress_unknownOutputSize() also insures that it will never read outside of the input buffer.+//		A corrupted input will produce an error result, a negative int, indicating the position of the error within input stream.++int LZ4_uncompress(const char* source,+				 char* dest,+				 int osize)+{+	// Local Variables+	const BYTE* restrict ip = (const BYTE*) source;+	const BYTE* restrict ref;++	BYTE* restrict op = (BYTE*) dest;+	BYTE* const oend = op + osize;+	BYTE* cpy;++	BYTE token;++	int	len, length;+	size_t dec[] ={0, 3, 2, 3, 0, 0, 0, 0};+++	// Main Loop+	while (1)+	{+		// get runlength+		token = *ip++;+		if ((length=(token>>ML_BITS)) == RUN_MASK)  { for (;(len=*ip++)==255;length+=255){} length += len; }++		// copy literals+		cpy = op+length;+		if unlikely(cpy>oend-COPYLENGTH)+		{+			if (cpy > oend) goto _output_error;          // Error : request to write beyond destination buffer+			memcpy(op, ip, length);+			ip += length;+			break;    // Necessarily EOF+		}+		LZ4_WILDCOPY(ip, op, cpy); ip -= (op-cpy); op = cpy;++		// get offset+		LZ4_READ_LITTLEENDIAN_16(ref,cpy,ip); ip+=2;+		if (ref < (BYTE* const)dest) goto _output_error;   // Error : offset create reference outside destination buffer++		// get matchlength+		if ((length=(token&ML_MASK)) == ML_MASK) { for (;*ip==255;length+=255) {ip++;} length += *ip++; }++		// copy repeated sequence+		if unlikely(op-ref<STEPSIZE)+		{+#if LZ4_ARCH64+			size_t dec2table[]={0, 0, 0, -1, 0, 1, 2, 3};+			size_t dec2 = dec2table[op-ref];+#else+			const int dec2 = 0;+#endif+			*op++ = *ref++;+			*op++ = *ref++;+			*op++ = *ref++;+			*op++ = *ref++;+			ref -= dec[op-ref];+			A32(op)=A32(ref); op += STEPSIZE-4;+			ref -= dec2;+		} else { LZ4_COPYSTEP(ref,op); }+		cpy = op + length - (STEPSIZE-4);+		if (cpy>oend-COPYLENGTH)+		{+			if (cpy > oend) goto _output_error;             // Error : request to write beyond destination buffer+			LZ4_SECURECOPY(ref, op, (oend-COPYLENGTH));+			while(op<cpy) *op++=*ref++;+			op=cpy;+			if (op == oend) break;    // Check EOF (should never happen, since last 5 bytes are supposed to be literals)+			continue;+		}+		LZ4_SECURECOPY(ref, op, cpy);+		op=cpy;		// correction+	}++	// end of decoding+	return (int) (((char*)ip)-source);++	// write overflow error detected+_output_error:+	return (int) (-(((char*)ip)-source));+}+++int LZ4_uncompress_unknownOutputSize(+				const char* source,+				char* dest,+				int isize,+				int maxOutputSize)+{+	// Local Variables+	const BYTE* restrict ip = (const BYTE*) source;+	const BYTE* const iend = ip + isize;+	const BYTE* restrict ref;++	BYTE* restrict op = (BYTE*) dest;+	BYTE* const oend = op + maxOutputSize;+	BYTE* cpy;++	size_t dec[] ={0, 3, 2, 3, 0, 0, 0, 0};+++	// Main Loop+	while (ip<iend)+	{+		BYTE token;+		int length;++		// get runlength+		token = *ip++;+		if ((length=(token>>ML_BITS)) == RUN_MASK) { int s=255; while ((ip<iend) && (s==255)) { s=*ip++; length += s; } }++		// copy literals+		cpy = op+length;+		if ((cpy>oend-COPYLENGTH) || (ip+length>iend-COPYLENGTH))+		{+			if (cpy > oend) goto _output_error;          // Error : request to write beyond destination buffer+			if (ip+length > iend) goto _output_error;    // Error : request to read beyond source buffer+			memcpy(op, ip, length);+			op += length;+			ip += length;+			if (ip<iend) goto _output_error;             // Error : LZ4 format violation+			break;    // Necessarily EOF, due to parsing restrictions+		}+		LZ4_WILDCOPY(ip, op, cpy); ip -= (op-cpy); op = cpy;++		// get offset+		LZ4_READ_LITTLEENDIAN_16(ref,cpy,ip); ip+=2;+		if (ref < (BYTE* const)dest) goto _output_error;   // Error : offset creates reference outside of destination buffer++		// get matchlength+		if ((length=(token&ML_MASK)) == ML_MASK) { while (ip<iend) { int s = *ip++; length +=s; if (s==255) continue; break; } }++		// copy repeated sequence+		if unlikely(op-ref<STEPSIZE)+		{+#if LZ4_ARCH64+			size_t dec2table[]={0, 0, 0, -1, 0, 1, 2, 3};+			size_t dec2 = dec2table[op-ref];+#else+			const int dec2 = 0;+#endif+			*op++ = *ref++;+			*op++ = *ref++;+			*op++ = *ref++;+			*op++ = *ref++;+			ref -= dec[op-ref];+			A32(op)=A32(ref); op += STEPSIZE-4;+			ref -= dec2;+		} else { LZ4_COPYSTEP(ref,op); }+		cpy = op + length - (STEPSIZE-4);+		if (cpy>oend-COPYLENGTH)+		{+			if (cpy > oend) goto _output_error;           // Error : request to write outside of destination buffer+			LZ4_SECURECOPY(ref, op, (oend-COPYLENGTH));+			while(op<cpy) *op++=*ref++;+			op=cpy;+			if (op == oend) break;    // Check EOF (should never happen, since last 5 bytes are supposed to be literals)+			continue;+		}+		LZ4_SECURECOPY(ref, op, cpy);+		op=cpy;		// correction+	}++	// end of decoding+	return (int) (((char*)op)-dest);++	// write overflow error detected+_output_error:+	return (int) (-(((char*)ip)-source));+}
+ src/cbits/lz4.h view
@@ -0,0 +1,117 @@+/*+   LZ4 - Fast LZ compression algorithm+   Header File+   Copyright (C) 2011-2012, Yann Collet.+   BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)++   Redistribution and use in source and binary forms, with or without+   modification, are permitted provided that the following conditions are+   met:++       * Redistributions of source code must retain the above copyright+   notice, this list of conditions and the following disclaimer.+       * Redistributions in binary form must reproduce the above+   copyright notice, this list of conditions and the following disclaimer+   in the documentation and/or other materials provided with the+   distribution.++   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS+   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT+   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR+   A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT+   OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,+   SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT+   LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,+   DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY+   THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT+   (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE+   OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.++   You can contact the author at :+   - LZ4 homepage : http://fastcompression.blogspot.com/p/lz4.html+   - LZ4 source repository : http://code.google.com/p/lz4/+*/+#pragma once++#if defined (__cplusplus)+extern "C" {+#endif+++//****************************+// Simple Functions+//****************************++int LZ4_compress   (const char* source, char* dest, int isize);+int LZ4_uncompress (const char* source, char* dest, int osize);++/*+LZ4_compress() :+	Compresses 'isize' bytes from 'source' into 'dest'.+	Destination buffer must be already allocated,+	and must be sized to handle worst cases situations (input data not compressible)+	Worst case size evaluation is provided by macro LZ4_compressBound()++	isize  : is the input size. Max supported value is ~1.9GB+	return : the number of bytes written in buffer dest+++LZ4_uncompress() :+	osize  : is the output size, therefore the original size+	return : the number of bytes read in the source buffer+			 If the source stream is malformed, the function will stop decoding and return a negative result, indicating the byte position of the faulty instruction+			 This function never writes beyond dest + osize, and is therefore protected against malicious data packets+	note : destination buffer must be already allocated.+		   its size must be a minimum of 'osize' bytes.+*/+++//****************************+// Advanced Functions+//****************************++#define LZ4_compressBound(isize)   (isize + (isize/255) + 16)++/*+LZ4_compressBound() :+	Provides the maximum size that LZ4 may output in a "worst case" scenario (input data not compressible)+	primarily useful for memory allocation of output buffer.++	isize  : is the input size. Max supported value is ~1.9GB+	return : maximum output size in a "worst case" scenario+	note : this function is limited by "int" range (2^31-1)+*/+++int LZ4_compress_limitedOutput   (const char* source, char* dest, int isize, int maxOutputSize);++/*+LZ4_compress_limitedOutput() :+    Compress 'isize' bytes from 'source' into an output buffer 'dest' of maximum size 'maxOutputSize'.+	If it cannot achieve it, compression will stop, and result of the function will be zero.+	This function never writes outside of provided output buffer.++	isize  : is the input size. Max supported value is ~1.9GB+	maxOutputSize : is the size of the destination buffer (which must be already allocated)+	return : the number of bytes written in buffer 'dest'+			 or 0 if the compression fails+*/+++int LZ4_uncompress_unknownOutputSize (const char* source, char* dest, int isize, int maxOutputSize);++/*+LZ4_uncompress_unknownOutputSize() :+	isize  : is the input size, therefore the compressed size+	maxOutputSize : is the size of the destination buffer (which must be already allocated)+	return : the number of bytes decoded in the destination buffer (necessarily <= maxOutputSize)+			 If the source stream is malformed, the function will stop decoding and return a negative result, indicating the byte position of the faulty instruction+			 This function never writes beyond dest + maxOutputSize, and is therefore protected against malicious data packets+	note   : Destination buffer must be already allocated.+	         This version is slightly slower than LZ4_uncompress()+*/+++#if defined (__cplusplus)+}+#endif
+ src/cbits/lz4hc.c view
@@ -0,0 +1,671 @@+/*+   LZ4 HC - High Compression Mode of LZ4+   Copyright (C) 2011-2012, Yann Collet.+   BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)++   Redistribution and use in source and binary forms, with or without+   modification, are permitted provided that the following conditions are+   met:++       * Redistributions of source code must retain the above copyright+   notice, this list of conditions and the following disclaimer.+       * Redistributions in binary form must reproduce the above+   copyright notice, this list of conditions and the following disclaimer+   in the documentation and/or other materials provided with the+   distribution.++   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS+   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT+   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR+   A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT+   OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,+   SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT+   LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,+   DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY+   THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT+   (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE+   OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.++   You can contact the author at :+   - LZ4 homepage : http://fastcompression.blogspot.com/p/lz4.html+   - LZ4 source repository : http://code.google.com/p/lz4/+*/+++//**************************************+// CPU Feature Detection+//**************************************+// 32 or 64 bits ?+#if (defined(__x86_64__) || defined(__x86_64) || defined(__amd64__) || defined(__amd64) || defined(__ppc64__) || defined(_WIN64) || defined(__LP64__) || defined(_LP64) )   // Detects 64 bits mode+#define LZ4_ARCH64 1+#else+#define LZ4_ARCH64 0+#endif++// Little Endian or Big Endian ? +#if (defined(__BIG_ENDIAN__) || defined(__BIG_ENDIAN) || defined(_BIG_ENDIAN) || defined(_ARCH_PPC) || defined(__PPC__) || defined(__PPC) || defined(PPC) || defined(__powerpc__) || defined(__powerpc) || defined(powerpc) || ((defined(__BYTE_ORDER__)&&(__BYTE_ORDER__ == __ORDER_BIG_ENDIAN__))) )+#define LZ4_BIG_ENDIAN 1+#else+// Little Endian assumed. PDP Endian and other very rare endian format are unsupported.+#endif++// Unaligned memory access is automatically enabled for "common" CPU, such as x86.+// For others CPU, the compiler will be more cautious, and insert extra code to ensure aligned access is respected+// If you know your target CPU supports unaligned memory access, you may want to force this option manually to improve performance+#if defined(__ARM_FEATURE_UNALIGNED)+#define LZ4_FORCE_UNALIGNED_ACCESS 1+#endif+++//**************************************+// Compiler Options+//**************************************+#if __STDC_VERSION__ >= 199901L    // C99+  /* "restrict" is a known keyword */+#else+#define restrict  // Disable restrict+#endif++#ifdef _MSC_VER+#define inline __forceinline    // Visual is not C99, but supports some kind of inline+#include <intrin.h>             // For Visual 2005+#  if LZ4_ARCH64	// 64-bit+#    pragma intrinsic(_BitScanForward64) // For Visual 2005+#    pragma intrinsic(_BitScanReverse64) // For Visual 2005+#  else+#    pragma intrinsic(_BitScanForward)   // For Visual 2005+#    pragma intrinsic(_BitScanReverse)   // For Visual 2005+#  endif+#endif++#ifdef _MSC_VER  // Visual Studio+#define bswap16(x) _byteswap_ushort(x)+#else+#define bswap16(x)  ((unsigned short int) ((((x) >> 8) & 0xffu) | (((x) & 0xffu) << 8)))+#endif+++//**************************************+// Includes+//**************************************+#include <stdlib.h>   // calloc, free+#include <string.h>   // memset, memcpy+#include "lz4hc.h"++#define ALLOCATOR(s) calloc(1,s)+#define FREEMEM free+#define MEM_INIT memset+++//**************************************+// Basic Types+//**************************************+#if defined(_MSC_VER)    // Visual Studio does not support 'stdint' natively+#define BYTE	unsigned __int8+#define U16		unsigned __int16+#define U32		unsigned __int32+#define S32		__int32+#define U64		unsigned __int64+#else+#include <stdint.h>+#define BYTE	uint8_t+#define U16		uint16_t+#define U32		uint32_t+#define S32		int32_t+#define U64		uint64_t+#endif++#ifndef LZ4_FORCE_UNALIGNED_ACCESS+#pragma pack(push, 1) +#endif++typedef struct _U16_S { U16 v; } U16_S;+typedef struct _U32_S { U32 v; } U32_S;+typedef struct _U64_S { U64 v; } U64_S;++#ifndef LZ4_FORCE_UNALIGNED_ACCESS+#pragma pack(pop) +#endif++#define A64(x) (((U64_S *)(x))->v)+#define A32(x) (((U32_S *)(x))->v)+#define A16(x) (((U16_S *)(x))->v)+++//**************************************+// Constants+//**************************************+#define MINMATCH 4++#define DICTIONARY_LOGSIZE 16+#define MAXD (1<<DICTIONARY_LOGSIZE)+#define MAXD_MASK ((U32)(MAXD - 1))+#define MAX_DISTANCE (MAXD - 1)++#define HASH_LOG (DICTIONARY_LOGSIZE-1)+#define HASHTABLESIZE (1 << HASH_LOG)+#define HASH_MASK (HASHTABLESIZE - 1)++#define MAX_NB_ATTEMPTS 256++#define ML_BITS  4+#define ML_MASK  (size_t)((1U<<ML_BITS)-1)+#define RUN_BITS (8-ML_BITS)+#define RUN_MASK ((1U<<RUN_BITS)-1)++#define COPYLENGTH 8+#define LASTLITERALS 5+#define MFLIMIT (COPYLENGTH+MINMATCH)+#define MINLENGTH (MFLIMIT+1)+#define OPTIMAL_ML (int)((ML_MASK-1)+MINMATCH)+++//**************************************+// Architecture-specific macros+//**************************************+#if LZ4_ARCH64	// 64-bit+#define STEPSIZE 8+#define LZ4_COPYSTEP(s,d)		A64(d) = A64(s); d+=8; s+=8;+#define LZ4_COPYPACKET(s,d)		LZ4_COPYSTEP(s,d)+#define UARCH U64+#define AARCH A64+#define HTYPE					U32+#define INITBASE(b,s)			const BYTE* const b = s+#else		// 32-bit+#define STEPSIZE 4+#define LZ4_COPYSTEP(s,d)		A32(d) = A32(s); d+=4; s+=4;+#define LZ4_COPYPACKET(s,d)		LZ4_COPYSTEP(s,d); LZ4_COPYSTEP(s,d);+#define UARCH U32+#define AARCH A32+#define HTYPE					const BYTE*+#define INITBASE(b,s)		    const int b = 0+#endif++#if defined(LZ4_BIG_ENDIAN)+#define LZ4_READ_LITTLEENDIAN_16(d,s,p) { U16 v = A16(p); v = bswap16(v); d = (s) - v; }+#define LZ4_WRITE_LITTLEENDIAN_16(p,i)  { U16 v = (U16)(i); v = bswap16(v); A16(p) = v; p+=2; }+#else		// Little Endian+#define LZ4_READ_LITTLEENDIAN_16(d,s,p) { d = (s) - A16(p); }+#define LZ4_WRITE_LITTLEENDIAN_16(p,v)  { A16(p) = v; p+=2; }+#endif+++//************************************************************+// Local Types+//************************************************************+typedef struct +{+	const BYTE* base;+	HTYPE hashTable[HASHTABLESIZE];+	U16 chainTable[MAXD];+	const BYTE* nextToUpdate;+} LZ4HC_Data_Structure;+++//**************************************+// Macros+//**************************************+#define LZ4_WILDCOPY(s,d,e)		do { LZ4_COPYPACKET(s,d) } while (d<e);+#define LZ4_BLINDCOPY(s,d,l)	{ BYTE* e=d+l; LZ4_WILDCOPY(s,d,e); d=e; }+#define HASH_FUNCTION(i)	(((i) * 2654435761U) >> ((MINMATCH*8)-HASH_LOG))+#define HASH_VALUE(p)		HASH_FUNCTION(*(U32*)(p))+#define HASH_POINTER(p)		(HashTable[HASH_VALUE(p)] + base)+#define DELTANEXT(p)		chainTable[(size_t)(p) & MAXD_MASK] +#define GETNEXT(p)			((p) - (size_t)DELTANEXT(p))+#define ADD_HASH(p)			{ size_t delta = (p) - HASH_POINTER(p); if (delta>MAX_DISTANCE) delta = MAX_DISTANCE; DELTANEXT(p) = (U16)delta; HashTable[HASH_VALUE(p)] = (p) - base; }+++//**************************************+// Private functions+//**************************************+#if LZ4_ARCH64++inline static int LZ4_NbCommonBytes (register U64 val)+{+#if defined(LZ4_BIG_ENDIAN)+    #if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)+    unsigned long r = 0;+    _BitScanReverse64( &r, val );+    return (int)(r>>3);+    #elif defined(__GNUC__) && ((__GNUC__ * 100 + __GNUC_MINOR__) >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT)+    return (__builtin_clzll(val) >> 3); +    #else+	int r;+	if (!(val>>32)) { r=4; } else { r=0; val>>=32; }+	if (!(val>>16)) { r+=2; val>>=8; } else { val>>=24; }+	r += (!val);+	return r;+    #endif+#else+    #if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)+    unsigned long r = 0;+    _BitScanForward64( &r, val );+    return (int)(r>>3);+    #elif defined(__GNUC__) && ((__GNUC__ * 100 + __GNUC_MINOR__) >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT)+    return (__builtin_ctzll(val) >> 3); +    #else+	static const int DeBruijnBytePos[64] = { 0, 0, 0, 0, 0, 1, 1, 2, 0, 3, 1, 3, 1, 4, 2, 7, 0, 2, 3, 6, 1, 5, 3, 5, 1, 3, 4, 4, 2, 5, 6, 7, 7, 0, 1, 2, 3, 3, 4, 6, 2, 6, 5, 5, 3, 4, 5, 6, 7, 1, 2, 4, 6, 4, 4, 5, 7, 2, 6, 5, 7, 6, 7, 7 };+	return DeBruijnBytePos[((U64)((val & -val) * 0x0218A392CDABBD3F)) >> 58];+    #endif+#endif+}++#else++inline static int LZ4_NbCommonBytes (register U32 val)+{+#if defined(LZ4_BIG_ENDIAN)+    #if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)+    unsigned long r = 0;+    _BitScanReverse( &r, val );+    return (int)(r>>3);+    #elif defined(__GNUC__) && ((__GNUC__ * 100 + __GNUC_MINOR__) >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT)+    return (__builtin_clz(val) >> 3); +    #else+	int r;+	if (!(val>>16)) { r=2; val>>=8; } else { r=0; val>>=24; }+	r += (!val);+	return r;+    #endif+#else+    #if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)+    unsigned long r = 0;+    _BitScanForward( &r, val );+    return (int)(r>>3);+    #elif defined(__GNUC__) && ((__GNUC__ * 100 + __GNUC_MINOR__) >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT)+    return (__builtin_ctz(val) >> 3); +    #else+	static const int DeBruijnBytePos[32] = { 0, 0, 3, 0, 3, 1, 3, 0, 3, 2, 2, 1, 3, 2, 0, 1, 3, 3, 1, 2, 2, 2, 2, 0, 3, 1, 2, 0, 1, 0, 1, 1 };+	return DeBruijnBytePos[((U32)((val & -(S32)val) * 0x077CB531U)) >> 27];+    #endif+#endif+}++#endif+++inline static int LZ4HC_Init (LZ4HC_Data_Structure* hc4, const BYTE* base)+{+	MEM_INIT((void*)hc4->hashTable, 0, sizeof(hc4->hashTable));+	MEM_INIT(hc4->chainTable, 0xFF, sizeof(hc4->chainTable));+	hc4->nextToUpdate = base + LZ4_ARCH64;+	hc4->base = base;+	return 1;+}+++inline static void* LZ4HC_Create (const BYTE* base)+{+	void* hc4 = ALLOCATOR(sizeof(LZ4HC_Data_Structure));++	LZ4HC_Init (hc4, base);+	return hc4;+}+++inline static int LZ4HC_Free (void** LZ4HC_Data)+{+	FREEMEM(*LZ4HC_Data);+	*LZ4HC_Data = NULL;+	return (1);+}+++inline static void LZ4HC_Insert (LZ4HC_Data_Structure* hc4, const BYTE* ip)+{+	U16*   chainTable = hc4->chainTable;+	HTYPE* HashTable  = hc4->hashTable;+	INITBASE(base,hc4->base);++	while(hc4->nextToUpdate < ip)+	{+		ADD_HASH(hc4->nextToUpdate);+		hc4->nextToUpdate++;+	}+}+++inline static int LZ4HC_InsertAndFindBestMatch (LZ4HC_Data_Structure* hc4, const BYTE* ip, const BYTE* const matchlimit, const BYTE** matchpos)+{+	U16* const chainTable = hc4->chainTable;+	HTYPE* const HashTable = hc4->hashTable;+	const BYTE* ref;+	INITBASE(base,hc4->base);+	int nbAttempts=MAX_NB_ATTEMPTS;+	int ml=0;++	// HC4 match finder+	LZ4HC_Insert(hc4, ip);+	ref = HASH_POINTER(ip);+	while ((ref > (ip-MAX_DISTANCE)) && (nbAttempts))+	{+		nbAttempts--;+		if (*(ref+ml) == *(ip+ml))+		if (*(U32*)ref == *(U32*)ip)+		{+			const BYTE* reft = ref+MINMATCH;+			const BYTE* ipt = ip+MINMATCH;++			while (ipt<matchlimit-(STEPSIZE-1))+			{+				UARCH diff = AARCH(reft) ^ AARCH(ipt);+				if (!diff) { ipt+=STEPSIZE; reft+=STEPSIZE; continue; }+				ipt += LZ4_NbCommonBytes(diff);+				goto _endCount;+			}+			if (LZ4_ARCH64) if ((ipt<(matchlimit-3)) && (A32(reft) == A32(ipt))) { ipt+=4; reft+=4; }+			if ((ipt<(matchlimit-1)) && (A16(reft) == A16(ipt))) { ipt+=2; reft+=2; }+			if ((ipt<matchlimit) && (*reft == *ipt)) ipt++;+_endCount:++			if (ipt-ip > ml) { ml = (int)(ipt-ip); *matchpos = ref; }+		}+		ref = GETNEXT(ref);+	}++	return ml;+}+++inline static int LZ4HC_InsertAndGetWiderMatch (LZ4HC_Data_Structure* hc4, const BYTE* ip, const BYTE* startLimit, const BYTE* matchlimit, int longest, const BYTE** matchpos, const BYTE** startpos)+{+	U16* const  chainTable = hc4->chainTable;+	HTYPE* const HashTable = hc4->hashTable;+	INITBASE(base,hc4->base);+	const BYTE*  ref;+	int nbAttempts = MAX_NB_ATTEMPTS;+	int delta = (int)(ip-startLimit);++	// First Match+	LZ4HC_Insert(hc4, ip);+	ref = HASH_POINTER(ip);++	while ((ref > ip-MAX_DISTANCE) && (ref >= hc4->base) && (nbAttempts))+	{+		nbAttempts--;+		if (*(startLimit + longest) == *(ref - delta + longest))+		if (*(U32*)ref == *(U32*)ip)+		{+			const BYTE* reft = ref+MINMATCH;+			const BYTE* ipt = ip+MINMATCH;+			const BYTE* startt = ip;++			while (ipt<matchlimit-(STEPSIZE-1))+			{+				UARCH diff = AARCH(reft) ^ AARCH(ipt);+				if (!diff) { ipt+=STEPSIZE; reft+=STEPSIZE; continue; }+				ipt += LZ4_NbCommonBytes(diff);+				goto _endCount;+			}+			if (LZ4_ARCH64) if ((ipt<(matchlimit-3)) && (A32(reft) == A32(ipt))) { ipt+=4; reft+=4; }+			if ((ipt<(matchlimit-1)) && (A16(reft) == A16(ipt))) { ipt+=2; reft+=2; }+			if ((ipt<matchlimit) && (*reft == *ipt)) ipt++;+_endCount:++			reft = ref;+			while ((startt>startLimit) && (reft > hc4->base) && (startt[-1] == reft[-1])) {startt--; reft--;}++			if ((ipt-startt) > longest)+			{+				longest = (int)(ipt-startt);+				*matchpos = reft;+				*startpos = startt;+			}+		}+		ref = GETNEXT(ref);+	}++	return longest;+}+++inline static int LZ4_encodeSequence(const BYTE** ip, BYTE** op, const BYTE** anchor, int ml, const BYTE* ref)+{+	int length, len; +	BYTE* token;++	// Encode Literal length+	length = (int)(*ip - *anchor);+	token = (*op)++;+	if (length>=(int)RUN_MASK) { *token=(RUN_MASK<<ML_BITS); len = length-RUN_MASK; for(; len > 254 ; len-=255) *(*op)++ = 255;  *(*op)++ = (BYTE)len; } +	else *token = (length<<ML_BITS);++	// Copy Literals+	LZ4_BLINDCOPY(*anchor, *op, length);++	// Encode Offset+	LZ4_WRITE_LITTLEENDIAN_16(*op,(U16)(*ip-ref));++	// Encode MatchLength+	len = (int)(ml-MINMATCH);+	if (len>=(int)ML_MASK) { *token+=ML_MASK; len-=ML_MASK; for(; len > 509 ; len-=510) { *(*op)++ = 255; *(*op)++ = 255; } if (len > 254) { len-=255; *(*op)++ = 255; } *(*op)++ = (BYTE)len; } +	else *token += len;	++	// Prepare next loop+	*ip += ml;+	*anchor = *ip; ++	return 0;+}+++//****************************+// Compression CODE+//****************************++int LZ4_compressHCCtx(LZ4HC_Data_Structure* ctx,+				 const char* source, +				 char* dest,+				 int isize)+{	+	const BYTE* ip = (const BYTE*) source;+	const BYTE* anchor = ip;+	const BYTE* const iend = ip + isize;+	const BYTE* const mflimit = iend - MFLIMIT;+	const BYTE* const matchlimit = (iend - LASTLITERALS);++	BYTE* op = (BYTE*) dest;++	int	ml, ml2, ml3, ml0;+	const BYTE* ref=NULL;+	const BYTE* start2=NULL;+	const BYTE* ref2=NULL;+	const BYTE* start3=NULL;+	const BYTE* ref3=NULL;+	const BYTE* start0;+	const BYTE* ref0;++	ip++;++	// Main Loop+	while (ip < mflimit)+	{+		ml = LZ4HC_InsertAndFindBestMatch (ctx, ip, matchlimit, (&ref));+		if (!ml) { ip++; continue; }++		// saved, in case we would skip too much+		start0 = ip;+		ref0 = ref;+		ml0 = ml;++_Search2:+		if (ip+ml < mflimit)+			ml2 = LZ4HC_InsertAndGetWiderMatch(ctx, ip + ml - 2, ip + 1, matchlimit, ml, &ref2, &start2);+		else ml2=ml;++		if (ml2 == ml)  // No better match+		{+			LZ4_encodeSequence(&ip, &op, &anchor, ml, ref);+			continue;+		}++		if (start0 < ip)+		{+			if (start2 < ip + ml0)   // empirical+			{+				ip = start0;+				ref = ref0;+				ml = ml0;+			}+		}++		// Here, start0==ip+		if ((start2 - ip) < 3)   // First Match too small : removed+		{+			ml = ml2;+			ip = start2;+			ref =ref2;+			goto _Search2;+		}++_Search3:+		// Currently we have :+		// ml2 > ml1, and+		// ip1+3 <= ip2 (usually < ip1+ml1)+		if ((start2 - ip) < OPTIMAL_ML)+		{+			int correction;+			int new_ml = ml;+			if (new_ml > OPTIMAL_ML) new_ml = OPTIMAL_ML;+			if (ip+new_ml > start2 + ml2 - MINMATCH) new_ml = (int)(start2 - ip) + ml2 - MINMATCH;+			correction = new_ml - (int)(start2 - ip);+			if (correction > 0)+			{+				start2 += correction;+				ref2 += correction;+				ml2 -= correction;+			}+		}+		// Now, we have start2 = ip+new_ml, with new_ml=min(ml, OPTIMAL_ML=18)++		if (start2 + ml2 < mflimit)+			ml3 = LZ4HC_InsertAndGetWiderMatch(ctx, start2 + ml2 - 3, start2, matchlimit, ml2, &ref3, &start3);+		else ml3=ml2;++		if (ml3 == ml2) // No better match : 2 sequences to encode+		{+			// ip & ref are known; Now for ml+			if (start2 < ip+ml)+			{+				if ((start2 - ip) < OPTIMAL_ML)+				{+					int correction;+					if (ml > OPTIMAL_ML) ml = OPTIMAL_ML;+					if (ip+ml > start2 + ml2 - MINMATCH) ml = (int)(start2 - ip) + ml2 - MINMATCH;+					correction = ml - (int)(start2 - ip);+					if (correction > 0)+					{+						start2 += correction;+						ref2 += correction;+						ml2 -= correction;+					}+				}+				else+				{+					ml = (int)(start2 - ip);+				}+			}+			// Now, encode 2 sequences+			LZ4_encodeSequence(&ip, &op, &anchor, ml, ref);+			ip = start2;+			LZ4_encodeSequence(&ip, &op, &anchor, ml2, ref2);+			continue;+		}++		if (start3 < ip+ml+3) // Not enough space for match 2 : remove it+		{+			if (start3 >= (ip+ml)) // can write Seq1 immediately ==> Seq2 is removed, so Seq3 becomes Seq1+			{+				if (start2 < ip+ml)+				{+					int correction = (int)(ip+ml - start2);+					start2 += correction;+					ref2 += correction;+					ml2 -= correction;+					if (ml2 < MINMATCH)+					{+						start2 = start3;+						ref2 = ref3;+						ml2 = ml3;+					}+				}++				LZ4_encodeSequence(&ip, &op, &anchor, ml, ref);+				ip  = start3;+				ref = ref3;+				ml  = ml3;++				start0 = start2;+				ref0 = ref2;+				ml0 = ml2;+				goto _Search2;+			}++			start2 = start3;+			ref2 = ref3;+			ml2 = ml3;+			goto _Search3;+		}++		// OK, now we have 3 ascending matches; let's write at least the first one+		// ip & ref are known; Now for ml+		if (start2 < ip+ml)+		{+			if ((start2 - ip) < (int)ML_MASK)+			{+				int correction;+				if (ml > OPTIMAL_ML) ml = OPTIMAL_ML;+				if (ip + ml > start2 + ml2 - MINMATCH) ml = (int)(start2 - ip) + ml2 - MINMATCH;+				correction = ml - (int)(start2 - ip);+				if (correction > 0)+				{+					start2 += correction;+					ref2 += correction;+					ml2 -= correction;+				}+			}+			else+			{+				ml = (int)(start2 - ip);+			}+		}+		LZ4_encodeSequence(&ip, &op, &anchor, ml, ref);++		ip = start2;+		ref = ref2;+		ml = ml2;++		start2 = start3;+		ref2 = ref3;+		ml2 = ml3;++		goto _Search3;++	}++	// Encode Last Literals+	{+		int lastRun = (int)(iend - anchor);+		if (lastRun>=(int)RUN_MASK) { *op++=(RUN_MASK<<ML_BITS); lastRun-=RUN_MASK; for(; lastRun > 254 ; lastRun-=255) *op++ = 255; *op++ = (BYTE) lastRun; } +		else *op++ = (lastRun<<ML_BITS);+		memcpy(op, anchor, iend - anchor);+		op += iend-anchor;+	} ++	// End+	return (int) (((char*)op)-dest);+}+++int LZ4_compressHC(const char* source, +				 char* dest,+				 int isize)+{+	void* ctx = LZ4HC_Create((const BYTE*)source);+	int result = LZ4_compressHCCtx(ctx, source, dest, isize);+	LZ4HC_Free (&ctx);++	return result;+}++
+ src/cbits/lz4hc.h view
@@ -0,0 +1,60 @@+/*+   LZ4 HC - High Compression Mode of LZ4+   Header File+   Copyright (C) 2011-2012, Yann Collet.+   BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)++   Redistribution and use in source and binary forms, with or without+   modification, are permitted provided that the following conditions are+   met:++       * Redistributions of source code must retain the above copyright+   notice, this list of conditions and the following disclaimer.+       * Redistributions in binary form must reproduce the above+   copyright notice, this list of conditions and the following disclaimer+   in the documentation and/or other materials provided with the+   distribution.++   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS+   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT+   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR+   A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT+   OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,+   SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT+   LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,+   DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY+   THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT+   (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE+   OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.++   You can contact the author at :+   - LZ4 homepage : http://fastcompression.blogspot.com/p/lz4.html+   - LZ4 source repository : http://code.google.com/p/lz4/+*/+#pragma once+++#if defined (__cplusplus)+extern "C" {+#endif+++int LZ4_compressHC (const char* source, char* dest, int isize);++/*+LZ4_compressHC :+	return : the number of bytes in compressed buffer dest+	note : destination buffer must be already allocated. +		To avoid any problem, size it to handle worst cases situations (input data not compressible)+		Worst case size evaluation is provided by function LZ4_compressBound() (see "lz4.h")+*/+++/* Note :+Decompression functions are provided within regular LZ4 source code (see "lz4.h") (BSD license)+*/+++#if defined (__cplusplus)+}+#endif
− test/Spec.hs 
@@ -1,2 +0,0 @@--- file test/Spec.hs-{-# OPTIONS_GHC -F -pgmF hspec-discover #-}
+ tests/Properties.hs view
@@ -0,0 +1,36 @@+{-# LANGUAGE ViewPatterns #-}+module Main (main) where+import Test.Hspec+import Test.Hspec.QuickCheck+import Test.QuickCheck++import qualified Data.ByteString as S+import Codec.Compression.LZ4++main :: IO ()+main = hspec $ do+  describe "compression" $ do+    prop "is pure"              $ prop_compress_pure compress decompress+    prop "(>>= decomp) = id" $ prop_compression_id compress decompress+  describe "high compression" $ do+    prop "is pure"              $ prop_compress_pure compressHC decompress+    prop "(>>= decomp) = id" $ prop_compression_id compressHC decompress+  describe "ultra compression" $ do+    prop "is pure"              $ prop_compress_pure compressPlusHC decompressPlusHC+    prop "(>>= decomp) = id" $ prop_compression_id compressPlusHC decompressPlusHC+  describe "decompression" $ do+    prop "is pure (normal)"     $ prop_decompress_pure compress decompress+    prop "is pure (high)"       $ prop_decompress_pure compressHC decompress+    prop "is pure (ultra)"      $ prop_decompress_pure compressPlusHC decompressPlusHC++prop_compress_pure comp decomp (S.pack -> xs) =+  (comp xs) == (comp xs)++prop_compression_id comp decomp (S.pack -> xs) =+  maybe False (== xs) (comp xs >>= decomp) ++prop_decompress_pure comp decomp (S.pack -> xs) =+  let z = comp xs+  in (z >>= decomp) == (z >>= decomp)++