From ca8d6c21e5700e7646266a084cb3d89f5bd1c6a2 Mon Sep 17 00:00:00 2001 From: "yann.collet.73@gmail.com" Date: Wed, 25 May 2011 22:25:57 +0000 Subject: Improved : safe type, for linux x64 (amd64) compatibility (Thanks to Erik Andersen) Checked : OS X compatibility (Thanks Abhinav) Corrected : Explicit unsigned constant for non C90-compliant C compilers (Thanks to Erik Andersen) Changed : lowercase filename for case-sensitive file systems (like linux) (Thanks Abhinav & Erik) Added : Makefile, for gcc (Thanks Abhinav & Erik) git-svn-id: https://lz4.googlecode.com/svn/trunk@7 650e7d94-2a16-8b24-b05c-7c0b3f6821cd --- LZ4.c | 268 ------------------------------------------------------------- LZ4.h | 87 -------------------- Makefile | 10 +++ lz4.c | 275 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ lz4.h | 90 +++++++++++++++++++++ main.c | 61 +++++++++----- 6 files changed, 416 insertions(+), 375 deletions(-) delete mode 100644 LZ4.c delete mode 100644 LZ4.h create mode 100644 Makefile create mode 100644 lz4.c create mode 100644 lz4.h diff --git a/LZ4.c b/LZ4.c deleted file mode 100644 index b848eea..0000000 --- a/LZ4.c +++ /dev/null @@ -1,268 +0,0 @@ -/* - LZ4 - Fast LZ compression algorithm - Copyright (C) 2011, Yann Collet. - BSD License - - 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. -*/ - -//************************************** -// Includes -//************************************** -#include // for malloc -#include // for memset -#include "lz4.h" - - -//************************************** -// Basic Types -//************************************** -#define BYTE unsigned char -#define U16 unsigned short -#define U32 unsigned long -#define S32 signed long -#define U64 unsigned long long - - -//************************************** -// Constants -//************************************** -#define MINMATCH 4 -#define INCOMPRESSIBLE 128 - -#define MAXD_LOG 16 -#define MAX_DISTANCE ((1 << MAXD_LOG) - 1) - -#define HASH_LOG 17 // <--- Lower this value to lower memory usage. N->2^(N+2) Bytes (ex : 17 -> 512KB) -#define HASHTABLESIZE (1 << HASH_LOG) -#define HASH_MASK (HASHTABLESIZE - 1) - -#define ML_BITS 4 -#define ML_MASK ((1U<> ((MINMATCH*8)-HASH_LOG)) -#define HASH_VALUE(p) HASH_FUNCTION(*(U32*)p) -#define HASH_POINTER(p) HashTable[HASH_VALUE(p)] - - - -//**************************** -// Compression CODE -//**************************** - -int LZ4_compress(char* source, - char* dest, - int isize) -{ - void* ctx = malloc(sizeof(struct refTables)); - int result = LZ4_compressCtx(&ctx, source, dest, isize); - free(ctx); - - return result; -} - - - -int LZ4_compressCtx(void** ctx, - char* source, - char* dest, - int isize) -{ - struct refTables *srt = (struct refTables *) (*ctx); - BYTE** HashTable; - - BYTE *ip = (BYTE*) source, /* input pointer */ - *anchor = (BYTE*) source, - *iend = (BYTE*) source + isize, - *ilimit = iend - MINMATCH - 1; - - BYTE *op = (BYTE*) dest, /* output pointer */ - *ref, - *orun, *l_end; - - int len, length, sequence, h; - U32 step=1; - S32 limit=INCOMPRESSIBLE; - - - // Init - if (*ctx == NULL) - { - srt = (struct refTables *) malloc ( sizeof(struct refTables) ); - *ctx = (void*) srt; - } - HashTable = srt->hashTable; - memset(HashTable, 0, sizeof(srt->hashTable)); - - // Main Loop - while (ip < ilimit) - { - sequence = *(U32*)ip; - h = HASH_FUNCTION(sequence); - ref = HashTable[h]; - HashTable[h] = ip; - - // Min Match - if (( ((ip-ref) >> MAXD_LOG) != 0) || (*(U32*)ref != sequence)) - { - if (ip-anchor>limit) { limit<<=1; step += 1 + (step>>2); } - ip+=step; - continue; - } - - // catch up - if (step>1) - { - HashTable[h] = ref; - ip -= (step-1); - step=1; - continue; - } - limit=INCOMPRESSIBLE; - - // Encode Literal length - len = length = ip - anchor; - orun=op++; - if (len>(RUN_MASK-1)) { *orun=(RUN_MASK< 254 ; len-=255) *op++ = 255; *op++ = (BYTE)len; } - else *orun = (len<(ML_MASK-1)) { *orun+=ML_MASK; len-=ML_MASK; for(; len > 254 ; len-=255) *op++ = 255; *op++ = (BYTE)len; } - else *orun += len; - - // Prepare next loop - anchor = ip; - } - - - // Encode Last Literals - len = length = iend - anchor; - orun=op++; - if (len>(RUN_MASK-1)) { *orun=(RUN_MASK< 254 ; len-=255) *op++ = 255; *op++ = (BYTE) len; } - else *orun = (len<0;length-=4) { *(U32*)op = *(U32*)anchor; op+=4; anchor+=4; } - op += length; // correction - - // End - return (int) (((char*)op)-dest); -} - - - -//**************************** -// Decompression CODE -//**************************** -int LZ4_decode ( char* source, - char* dest, - int isize) -{ - // Local Variables - BYTE *ip = (BYTE*) source, - *iend = (BYTE*) source + isize; - - BYTE *op = (BYTE*) dest, - *ref, *cpy, - runcode; - - U32 dec[4]={0, 3, 2, 3}; - int len, length; - - - // Main Loop - while (ip < iend) - { - // get runlength - runcode = *ip++; - if ((length=(runcode>>ML_BITS)) == RUN_MASK) { for (;(len=*ip++)==255;length+=255){} length += len; } - - // copy literals - ref = op+length; -#ifdef SAFEWRITEBUFFER - if (ref>iend-4) { while(op=iend) break; // Check EOF - - // get offset - ref -= *(U16*)ip; ip+=2; - - // get matchlength - if ((length=(runcode&ML_MASK)) == ML_MASK) { for (;(len=*ip++)==255;length+=255){} length += len; } - length += MINMATCH; - - // copy repeated sequence - cpy = op + length; - if (op-ref<4) - { - *op++ = *ref++; - *op++ = *ref++; - *op++ = *ref++; - *op++ = *ref++; - ref -= dec[op-ref]; - } -#ifdef SAFEWRITEBUFFER - if (cpy>iend-4) { while(op // for malloc +#include // for memset +#include "lz4.h" + + +//************************************** +// Basic Types +//************************************** +#if defined(_MSC_VER) || defined(_WIN32) || defined(__WIN32__) +#define BYTE unsigned __int8 +#define U16 unsigned __int16 +#define U32 unsigned __int32 +#define S32 __int32 +#else +#include +#define BYTE uint8_t +#define U16 uint16_t +#define U32 uint32_t +#define S32 int32_t +#endif + + +//************************************** +// Constants +//************************************** +#define MINMATCH 4 +#define INCOMPRESSIBLE 128 + +#define MAXD_LOG 16 +#define MAX_DISTANCE ((1 << MAXD_LOG) - 1) + +#define HASH_LOG 17 // <--- Lower this value to lower memory usage. N->2^(N+2) Bytes (ex : 17 -> 512KB) +#define HASHTABLESIZE (1 << HASH_LOG) +#define HASH_MASK (HASHTABLESIZE - 1) + +#define ML_BITS 4 +#define ML_MASK ((1U<> ((MINMATCH*8)-HASH_LOG)) +#define HASH_VALUE(p) HASH_FUNCTION(*(U32*)p) +#define HASH_POINTER(p) HashTable[HASH_VALUE(p)] + + + +//**************************** +// Compression CODE +//**************************** + +int LZ4_compress(char* source, + char* dest, + int isize) +{ + void* ctx = malloc(sizeof(struct refTables)); + int result = LZ4_compressCtx(&ctx, source, dest, isize); + free(ctx); + + return result; +} + + + +int LZ4_compressCtx(void** ctx, + char* source, + char* dest, + int isize) +{ + struct refTables *srt = (struct refTables *) (*ctx); + BYTE** HashTable; + + BYTE *ip = (BYTE*) source, /* input pointer */ + *anchor = (BYTE*) source, + *iend = (BYTE*) source + isize, + *ilimit = iend - MINMATCH - 1; + + BYTE *op = (BYTE*) dest, /* output pointer */ + *ref, + *orun, *l_end; + + int len, length, sequence, h; + U32 step=1; + S32 limit=INCOMPRESSIBLE; + + + // Init + if (*ctx == NULL) + { + srt = (struct refTables *) malloc ( sizeof(struct refTables) ); + *ctx = (void*) srt; + } + HashTable = srt->hashTable; + memset(HashTable, 0, sizeof(srt->hashTable)); + + // Main Loop + while (ip < ilimit) + { + sequence = *(U32*)ip; + h = HASH_FUNCTION(sequence); + ref = HashTable[h]; + HashTable[h] = ip; + + // Min Match + if (( ((ip-ref) >> MAXD_LOG) != 0) || (*(U32*)ref != sequence)) + { + if (ip-anchor>limit) { limit<<=1; step += 1 + (step>>2); } + ip+=step; + continue; + } + + // catch up + if (step>1) + { + HashTable[h] = ref; + ip -= (step-1); + step=1; + continue; + } + limit=INCOMPRESSIBLE; + + // Encode Literal length + len = length = ip - anchor; + orun=op++; + if (len>(RUN_MASK-1)) { *orun=(RUN_MASK< 254 ; len-=255) *op++ = 255; *op++ = (BYTE)len; } + else *orun = (len<(ML_MASK-1)) { *orun+=ML_MASK; len-=ML_MASK; for(; len > 254 ; len-=255) *op++ = 255; *op++ = (BYTE)len; } + else *orun += len; + + // Prepare next loop + anchor = ip; + } + + + // Encode Last Literals + len = length = iend - anchor; + orun=op++; + if (len>(RUN_MASK-1)) { *orun=(RUN_MASK< 254 ; len-=255) *op++ = 255; *op++ = (BYTE) len; } + else *orun = (len<0;length-=4) { *(U32*)op = *(U32*)anchor; op+=4; anchor+=4; } + op += length; // correction + + // End + return (int) (((char*)op)-dest); +} + + + +//**************************** +// Decompression CODE +//**************************** +int LZ4_decode ( char* source, + char* dest, + int isize) +{ + // Local Variables + BYTE *ip = (BYTE*) source, + *iend = (BYTE*) source + isize; + + BYTE *op = (BYTE*) dest, + *ref, *cpy, + runcode; + + U32 dec[4]={0, 3, 2, 3}; + int len, length; + + + // Main Loop + while (ip < iend) + { + // get runlength + runcode = *ip++; + if ((length=(runcode>>ML_BITS)) == RUN_MASK) { for (;(len=*ip++)==255;length+=255){} length += len; } + + // copy literals + ref = op+length; +#ifdef SAFEWRITEBUFFER + if (ref>iend-4) { while(op=iend) break; // Check EOF + + // get offset + ref -= *(U16*)ip; ip+=2; + + // get matchlength + if ((length=(runcode&ML_MASK)) == ML_MASK) { for (;(len=*ip++)==255;length+=255){} length += len; } + length += MINMATCH; + + // copy repeated sequence + cpy = op + length; + if (op-ref<4) + { + *op++ = *ref++; + *op++ = *ref++; + *op++ = *ref++; + *op++ = *ref++; + ref -= dec[op-ref]; + } +#ifdef SAFEWRITEBUFFER + if (cpy>iend-4) { while(op +#define BYTE uint8_t +#define U16 uint16_t +#define U32 uint32_t +#define S32 int32_t +#define U64 uint64_t +#endif + + //**************************** // Constants //**************************** @@ -74,10 +93,10 @@ int badusage() } -compress_file(char* input_filename, char* output_filename) +int compress_file(char* input_filename, char* output_filename) { - long long filesize = 0; - long long compressedfilesize = ARCHIVE_MAGICNUMBER_SIZE; + U64 filesize = 0; + U64 compressedfilesize = ARCHIVE_MAGICNUMBER_SIZE; char* in_buff; char* out_buff; FILE* finput = fopen( input_filename, "rb" ); @@ -91,7 +110,7 @@ compress_file(char* input_filename, char* output_filename) out_buff = malloc(OUT_CHUNKSIZE); // Write Archive Header - * (unsigned long*) out_buff = ARCHIVE_MAGICNUMBER; + *(U32*)out_buff = ARCHIVE_MAGICNUMBER; fwrite(out_buff, 1, ARCHIVE_MAGICNUMBER_SIZE, foutput); // Main Loop @@ -99,13 +118,13 @@ compress_file(char* input_filename, char* output_filename) { int outSize; // Read Block - int inSize = fread( in_buff, 1, CHUNKSIZE, finput ); + int inSize = fread(in_buff, 1, CHUNKSIZE, finput); if( inSize<=0 ) break; filesize += inSize; // Compress Block outSize = LZ4_compress(in_buff, out_buff+4, inSize); - * (unsigned long*) out_buff = outSize; + * (U32*) out_buff = outSize; compressedfilesize += outSize+4; // Write Block @@ -113,7 +132,8 @@ compress_file(char* input_filename, char* output_filename) } // Status - printf("Compressed %llu bytes into %llu bytes ==> %.2f%%\n", filesize, compressedfilesize, (double)compressedfilesize/filesize*100); + printf("Compressed %llu bytes into %llu bytes ==> %.2f%%\n", + (unsigned long long) filesize, (unsigned long long) compressedfilesize, (double)compressedfilesize/filesize*100); fclose(finput); fclose(foutput); @@ -122,34 +142,35 @@ compress_file(char* input_filename, char* output_filename) } -decode_file(char* input_filename, char* output_filename) +int decode_file(char* input_filename, char* output_filename) { - long long filesize = 0; + U64 filesize = 0; char* in_buff; char* out_buff; FILE* finput = fopen( input_filename, "rb" ); FILE* foutput = fopen( output_filename, "wb" ); + size_t uselessRet; - if ( finput==0 ) { printf("Pb opening %s\n", input_filename); return 2; } - if ( foutput==0) { printf("Pb opening %s\n", output_filename); return 3; } + if (finput==0 ) { printf("Pb opening %s\n", input_filename); return 2; } + if (foutput==0) { printf("Pb opening %s\n", output_filename); return 3; } // Allocate Memory in_buff = malloc(OUT_CHUNKSIZE); out_buff = malloc(CHUNKSIZE + CACHELINE); // Check Archive Header - fread(out_buff, 1, ARCHIVE_MAGICNUMBER_SIZE, finput); - if (* (unsigned long*) out_buff != ARCHIVE_MAGICNUMBER) { printf("Wrong file : cannot be decoded\n"); return 4; } + uselessRet = fread(out_buff, 1, ARCHIVE_MAGICNUMBER_SIZE, finput); + if (*(U32*)out_buff != ARCHIVE_MAGICNUMBER) { printf("Wrong file : cannot be decoded\n"); return 4; } // Main Loop while (1) { int outSize; // Read Block - int inSize = fread( in_buff, 1, 4, finput ); + U32 inSize = (U32) fread(in_buff, 1, 4, finput); if( inSize<=0 ) break; - inSize = (int) * (unsigned long*) in_buff; - fread( in_buff, 1, inSize, finput ); + inSize = *(U32*)in_buff; + uselessRet = fread( in_buff, 1, inSize, finput); // Decode Block outSize = LZ4_decode(in_buff, out_buff, inSize); @@ -160,7 +181,7 @@ decode_file(char* input_filename, char* output_filename) } // Status - printf("Successfully decoded %llu bytes \n", filesize); + printf("Successfully decoded %llu bytes \n", (unsigned long long)filesize); fclose(finput); fclose(foutput); @@ -179,7 +200,7 @@ int main(int argc, char** argv) // Welcome message printf(WELCOME_MESSAGE); - + //printf("Nb argument = %i \n", argc); if (argc<2) { badusage(); return 1; } @@ -206,7 +227,7 @@ int main(int argc, char** argv) if( argument[0] =='c' ) { compression=1; continue; } - // Forced Decoding + // Forced Decoding if( argument[0] =='d' ) { decode=1; continue; } } @@ -228,7 +249,7 @@ int main(int argc, char** argv) if (compression) return compress_file(input_filename, output_filename); - badusage(); + badusage(); return 0; } -- cgit v0.12