diff options
author | yann.collet.73@gmail.com <yann.collet.73@gmail.com@650e7d94-2a16-8b24-b05c-7c0b3f6821cd> | 2011-09-23 22:27:08 (GMT) |
---|---|---|
committer | yann.collet.73@gmail.com <yann.collet.73@gmail.com@650e7d94-2a16-8b24-b05c-7c0b3f6821cd> | 2011-09-23 22:27:08 (GMT) |
commit | e1ae3a0b958c03ac5162f4852f183bdd0e6580f4 (patch) | |
tree | b32b3c7d6dcbb114dce463e5bded76f2e395ad36 | |
parent | 307128134089c807a9f86dfe6c3dc665982f329a (diff) | |
download | lz4-e1ae3a0b958c03ac5162f4852f183bdd0e6580f4.zip lz4-e1ae3a0b958c03ac5162f4852f183bdd0e6580f4.tar.gz lz4-e1ae3a0b958c03ac5162f4852f183bdd0e6580f4.tar.bz2 |
Small compression speed improvement
Decoding speed improvement
git-svn-id: https://lz4.googlecode.com/svn/trunk@27 650e7d94-2a16-8b24-b05c-7c0b3f6821cd
-rw-r--r-- | lz4.c | 96 |
1 files changed, 51 insertions, 45 deletions
@@ -66,10 +66,14 @@ // Constants
//**************************************
#define MINMATCH 4
-#define MINLENGTH 6
#define SKIPSTRENGTH 6
#define STACKLIMIT 13
#define HEAPMODE (HASH_LOG>STACKLIMIT) // Defines if memory is allocated into the stack (local variable), or into the heap (malloc()).
+#define COPYTOKEN 4
+#define COPYLENGTH 8
+#define LASTLITERALS 5
+#define MFLIMIT 12
+#define MINLENGTH 13
#define MAXD_LOG 16
#define MAX_DISTANCE ((1 << MAXD_LOG) - 1)
@@ -95,8 +99,11 @@ struct refTables //**************************************
// Macros
//**************************************
-#define HASH_FUNCTION(i) (((i) * 2654435761U) >> ((MINMATCH*8)-HASH_LOG))
-#define HASH_VALUE(p) HASH_FUNCTION(*(U32*)(p))
+#define LZ4_HASH_FUNCTION(i) (((i) * 2654435761U) >> ((MINMATCH*8)-HASH_LOG))
+#define LZ4_HASH_VALUE(p) LZ4_HASH_FUNCTION(*(U32*)(p))
+#define LZ4_COPYPACKET(s,d) *(U32*)d = *(U32*)s; d+=4; s+=4; *(U32*)d = *(U32*)s; d+=4; s+=4;
+#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; }
@@ -119,12 +126,10 @@ int LZ4_compressCtx(void** ctx, const BYTE* ip = (BYTE*) source;
const BYTE* anchor = ip;
const BYTE* const iend = ip + isize;
- const BYTE* const ilm = iend - 1;
- const BYTE* const ilimit = iend - MINMATCH - 1;
+ const BYTE* const mflimit = iend - MFLIMIT;
+#define matchlimit (iend - LASTLITERALS)
BYTE* op = (BYTE*) dest;
- BYTE* token;
- BYTE* l_end;
int len, length;
const int skipStrength = SKIPSTRENGTH;
@@ -147,8 +152,8 @@ int LZ4_compressCtx(void** ctx, // First Byte
- HashTable[HASH_VALUE(ip)] = ip;
- ip++; forwardH = HASH_VALUE(ip);
+ HashTable[LZ4_HASH_VALUE(ip)] = ip;
+ ip++; forwardH = LZ4_HASH_VALUE(ip);
// Main Loop
for ( ; ; )
@@ -156,6 +161,7 @@ int LZ4_compressCtx(void** ctx, int findMatchAttempts = (1U << skipStrength) + 3;
const BYTE* forwardIp = ip;
const BYTE* ref;
+ BYTE* token;
// Find a match
do {
@@ -164,9 +170,9 @@ int LZ4_compressCtx(void** ctx, ip = forwardIp;
forwardIp = ip + step;
- if (forwardIp > ilimit) { goto _last_literals; }
+ if (forwardIp > mflimit) { goto _last_literals; }
- forwardH = HASH_VALUE(forwardIp);
+ forwardH = LZ4_HASH_VALUE(forwardIp);
ref = HashTable[h];
HashTable[h] = ip;
@@ -182,9 +188,8 @@ int LZ4_compressCtx(void** ctx, else *token = (length<<ML_BITS);
// Copy Literals
- l_end = op + length;
- do { *(U32*)op = *(U32*)anchor; op+=4; anchor+=4; } while (op<l_end) ;
- op = l_end;
+ LZ4_BLINDCOPY(anchor, op, length);
+
_next_match:
// Encode Offset
@@ -193,15 +198,15 @@ _next_match: // Start Counting
ip+=MINMATCH; ref+=MINMATCH; // MinMatch verified
anchor = ip;
- while (ip<(iend-4))
+ while (ip<matchlimit-3)
{
if (*(U32*)ref == *(U32*)ip) { ip+=4; ref+=4; continue; }
if (*(U16*)ref == *(U16*)ip) { ip+=2; ref+=2; }
if (*ref == *ip) ip++;
goto _endCount;
}
- if ((ip<(iend-2)) && (*(U16*)ref == *(U16*)ip)) { ip+=2; ref+=2; }
- if ((ip<iend-1) && (*ref == *ip)) ip++;
+ if ((ip<(matchlimit-1)) && (*(U16*)ref == *(U16*)ip)) { ip+=2; ref+=2; }
+ if ((ip<matchlimit) && (*ref == *ip)) ip++;
_endCount:
len = (ip - anchor);
@@ -210,26 +215,26 @@ _endCount: else *token += len;
// Test end of chunk
- if (ip > ilimit-1) { anchor = ip; break; }
+ if (ip > mflimit) { anchor = ip; break; }
// Test next position
- ref = HashTable[HASH_VALUE(ip)];
- HashTable[HASH_VALUE(ip)] = ip;
+ ref = HashTable[LZ4_HASH_VALUE(ip)];
+ HashTable[LZ4_HASH_VALUE(ip)] = ip;
if ((ref > ip - (MAX_DISTANCE + 1)) && (*(U32*)ref == *(U32*)ip)) { token = op++; *token=0; goto _next_match; }
// Prepare next loop
anchor = ip++;
- forwardH = HASH_VALUE(ip);
+ forwardH = LZ4_HASH_VALUE(ip);
}
_last_literals:
// Encode Last Literals
{
- int lastLitRun = iend - anchor;
- if (lastLitRun>=(int)RUN_MASK) { *op++=(RUN_MASK<<ML_BITS); lastLitRun-=RUN_MASK; for(; lastLitRun > 254 ; lastLitRun-=255) *op++ = 255; *op++ = (BYTE) lastLitRun; }
- else *op++ = (lastLitRun<<ML_BITS);
- while (anchor < iend - 3) { *(U32*)op = *(U32*)anchor; op+=4; anchor+=4; }
- while (anchor < iend ) *op++ = *anchor++;
+ int lastRun = 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
@@ -271,21 +276,22 @@ int LZ4_uncompress(char* source, {
// Local Variables
const BYTE* ip = (const BYTE*) source;
- BYTE* ref;
BYTE* op = (BYTE*) dest;
- BYTE* const olimit = op + osize - 4;
- BYTE* cpy;
+ BYTE* const oend = op + osize;
+ BYTE* const olimit = op + osize - COPYLENGTH;
- BYTE token;
-
- U32 dec[4]={0, 3, 2, 3};
- int length;
+ int dec[4]={0, 3, 2, 3};
// Main Loop
while (1)
{
+ int length;
+ BYTE token;
+ BYTE* ref;
+ BYTE* cpy;
+
// get runlength
token = *ip++;
if ((length=(token>>ML_BITS)) == RUN_MASK) { for (;*ip==255;length+=255) {ip++;} length += *ip++; }
@@ -294,12 +300,11 @@ int LZ4_uncompress(char* source, ref = op+length;
if (ref > olimit)
{
- if (ref > olimit+4) goto _output_error;
- while(op <= olimit) { *(U32*)op=*(U32*)ip; op+=4; ip+=4; }
- while(op < ref) *op++=*ip++;
+ if (ref > oend) goto _output_error;
+ memcpy(op, ip, length);
break; // Necessarily EOF
}
- do { *(U32*)op = *(U32*)ip; op+=4; ip+=4; } while (op<ref) ;
+ LZ4_WILDCOPY(ip, op, ref);
ip -= (op-ref); op = ref; // correction
// get offset
@@ -307,27 +312,28 @@ int LZ4_uncompress(char* source, // get matchlength
if ((length=(token&ML_MASK)) == ML_MASK) { for (;*ip==255;length+=255) {ip++;} length += *ip++; }
- length += MINMATCH;
// copy repeated sequence
- cpy = op + length;
- if (op-ref<4)
+ if (op-ref<COPYTOKEN)
{
*op++ = *ref++;
*op++ = *ref++;
*op++ = *ref++;
*op++ = *ref++;
ref -= dec[op-ref];
+ *(U32*)op=*(U32*)ref;
} else { *(U32*)op=*(U32*)ref; op+=4; ref+=4; }
+ cpy = op + length;
if (cpy > olimit)
{
- if (cpy > olimit+4) goto _output_error;
- while(op < cpy-3) { *(U32*)op=*(U32*)ref; op+=4; ref+=4; }
- while(op < cpy) *op++=*ref++;
- if (op >= olimit+4) break; // Check EOF
+ if (cpy > oend) goto _output_error;
+ LZ4_WILDCOPY(ref, op, olimit);
+ 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;
}
- do { *(U32*)op = *(U32*)ref; op+=4; ref+=4; } while (op<cpy) ;
+ LZ4_WILDCOPY(ref, op, cpy);
op=cpy; // correction
}
|