// Nakamichi is 100% FREE LZSS SUPERFAST decompressor.
// This code is based on Nakamichi Kaidanji by Kaze, but reworked for greater security and portability by m^2
//#define PLATFORM_GENERIC_ALIGNED
#define PLATFORM_GENERIC_UNALIGNED
//#define PLATFORM_XMM
//#define PLATFORM_YMM
//#define PLATFORM_BIG_ENDIAN
#define PLATFORM_LITTLE_ENDIAN
#ifdef PLATFORM_GENERIC_ALIGNED
#define PLATFORM_IS_ALIGNED
#endif
#include <stddef.h>
#include <stdint.h>
#include <string.h>
#ifdef PLATFORM_XMM
#include <emmintrin.h> // SSE2 intrinsics
#include <smmintrin.h> // SSE4.1 intrinsics
#endif
#ifdef PLATFORM_YMM
#include <emmintrin.h> // SSE2 intrinsics
#include <smmintrin.h> // SSE4.1 intrinsics
#include <immintrin.h> // AVX intrinsics
#endif
typedef int64_t ssize_t;
static inline uint_fast16_t load_2_bytes_le(const uint8_t * source)
{
#if !defined(PLATFORM_IS_ALIGNED) && defined (PLATFORM_LITTLE_ENDIAN)
return *(uint16_t*)source;
#else
return source[0] | (source[1] << 8);
#endif
}
static inline void copy_8_bytes(uint8_t * target, const uint8_t * source)
{
#ifdef PLATFORM_IS_ALIGNED
*(target + 0) = *(source + 0);
*(target + 1) = *(source + 1);
*(target + 2) = *(source + 2);
*(target + 3) = *(source + 3);
*(target + 4) = *(source + 4);
*(target + 5) = *(source + 5);
*(target + 6) = *(source + 6);
*(target + 7) = *(source + 7);
#else
*(uint64_t*)target = *(uint64_t*)source;
#endif
}
static inline void copy_at_most_32_bytes(uint8_t * target, const uint8_t * source, ssize_t size)
{
#if defined(PLATFORM_GENERIC_ALIGNED)
memcpy(target, source, size);
#elif defined(PLATFORM_GENERIC_UNALIGNED)
*(uint64_t*)(target + 8 * 0) = *(uint64_t*)(source + 8 * 0);
*(uint64_t*)(target + 8 * 1) = *(uint64_t*)(source + 8 * 1);
*(uint64_t*)(target + 8 * 2) = *(uint64_t*)(source + 8 * 2);
*(uint64_t*)(target + 8 * 3) = *(uint64_t*)(source + 8 * 3);
#elif defined(PLATFORM_XMM)
_mm_storeu_si128((__m128i *)(target), _mm_loadu_si128((const __m128i *)(source)));
_mm_storeu_si128((__m128i *)(target), _mm_loadu_si128((const __m128i *)(source + 16)));
#elif defined(PLATFORM_YMM)
_mm256_storeu_si256((__m256i *)target, _mm256_loadu_si256((const __m256i *)source));
#else
#error Define some platform
#endif
}
// A safe decompression function; should never go out of bounds
// However, it doesn't attempt to detect stream errors.
// On corrupted stream, it may return either success or error; then the contents of the output stream are undefined.
// The whole function consists of 3 loops:
// * tail loop, run when input or output are about to end
// * head loop, run for the first 64 KB of output or until we get near the end of one of the buffers
// * main loop, when both start and end are far
// They differ with amount of bounds checking they perform.
// * tail loop checks everything
// * head loop checks if buffers are about to end and if match doesn't send us to before the output buffer start
// It's quite imprecise in its copy operations and may go slightly farther than the buffer it's given.
// That's why we need to terminate it before the end and finish with the tail loop
// * main loop is the most relaxed with its assumptions. It's like the initial loop,
// but it doesn't even check if match offset sends us out of bounds.
// The decompressor is optimised for CPUs that can perform unaligned memory accesses.
// Others are supported, but optimisation for them is to be done later
// TODO: How about integer overflow in out_index += (two_bytes & 0xFF) >> 3; ?
ssize_t DecompressM(const void * _in, ssize_t in_size, void * _out, ssize_t out_size)
{
const uint8_t * in = _in;
uint8_t * out = _out;
ssize_t in_index = 0;
ssize_t out_index = 0;
// main loop may go 32 bytes out of limit on input
const size_t main_loop_in_limit = in_size < 32 ? 0 : in_size - 32;
// and 31 on output
const size_t main_loop_out_limit = out_size < 31 ? 0 : out_size - 31;
// The head loop
while(in_index < main_loop_in_limit && out_index < main_loop_out_limit && out_index < 65535)
{
// 16 bits, AAABBBBB CCCCCCCC
// If AAA == 0, we have a literal.
// BBBBB is its length reduced by 1 and CCCCCCCC - its first byte
// If AAA != 0, we have a match.
// It's always 8-byte long
// and the whole two bytes are a little endian match offset.
// Note a funny side effect, we can't encode any match in the stream
// because match distances can't have all 3 least significant bits zeroed.
uint_fast16_t two_bytes = load_2_bytes_le(in + in_index);
if ((two_bytes & 0xE0) == 0)
{
// literal
const int_fast16_t literal_length = (two_bytes & 0xFF) + 1;
// a wild copy, may write too much, but no more than 32 bytes
// loop limits prevent us from getting out of bounds
// TODO: on x86 aligned copy of 32 bytes is always faster than aligned copy of literal_length
// x86 sucks as a testbed for aligned access performance, check it elsewhere
copy_at_most_32_bytes(out + out_index, in + in_index + 1, 32);
out_index += literal_length;
in_index += literal_length + 1;
}
else
{
// match
in_index += 2;
ssize_t in_size_left = in_size - in_index - 2;
if (out_index < two_bytes)
return -1;
// match length is always 8 bytes
copy_8_bytes(out + out_index, out + out_index - two_bytes);
out_index += 8;
}
}
// The main loop
while(in_index < main_loop_in_limit && out_index < main_loop_out_limit)
{
uint_fast16_t two_bytes = load_2_bytes_le(in + in_index);
if ((two_bytes & 0xE0) == 0)
{
// literal
const int_fast16_t literal_length = (two_bytes & 0xFF) + 1;
// a wild copy, may write too much, but no more than 32 bytes
// loop limits prevent us from getting out of bounds
copy_at_most_32_bytes(out + out_index, in + in_index + 1, 32);
out_index += literal_length;
in_index += literal_length + 1;
}
else
{
// match
in_index += 2;
// match length is always 8 bytes
copy_8_bytes(out + out_index, out + out_index - two_bytes);
out_index += 8;
}
}
// The tail loop
while(in_index < (in_size - 1) && out_index < out_size)
{
uint_fast16_t two_bytes = load_2_bytes_le(in + in_index);
ssize_t out_size_left = out_size - out_index;
ssize_t in_size_left = in_size - in_index;
if ((two_bytes & 0xE0) == 0)
{
// literal
in_size_left -= 1;
const ssize_t size_left = in_size_left > out_size_left ? out_size_left : in_size_left;
const int_fast16_t literal_length = (two_bytes & 0xFF) + 1;
if (literal_length > size_left)
return -1;
memcpy(out + out_index, in + in_index + 1, literal_length);
out_index += literal_length;
in_index += literal_length + 1;
}
else
{
// match
in_index += 2;
in_size_left -= 2;
// match length is always 8 bytes
if (out_size_left < 8 || out_index < two_bytes)
return -1;
copy_8_bytes(out + out_index, out + out_index - two_bytes);
out_index += 8;
}
}
return in_index == in_size ? out_index : -1;
}
static void SearchIntoSlidingWindow(unsigned int * retIndex, unsigned int * retMatch, const uint8_t * refStart, const uint8_t * refEnd, const uint8_t * encStart);
static const uint8_t * Railgun_Swampshine_BailOut(const uint8_t * pbTarget, const uint8_t * pbPattern, uint32_t cbTarget, uint32_t cbPattern);
#define Match_Length (8)
#define OffsetBITS (16)
#define LengthBITS (1)
//12bit
#define REF_SIZE ( ((1<<OffsetBITS)-1) )
//3bit
#define ENC_SIZE ( ((1<<LengthBITS)-1) + Match_Length )
static void SearchIntoSlidingWindow(unsigned int * retIndex, unsigned int * retMatch, const uint8_t * refStart, const uint8_t * refEnd, const uint8_t * encStart)
{
const uint8_t* FoundAtPosition;
const uint8_t* split = refStart + 64*1024 - 16*1024; // last 16 KB
const uint8_t* split2 = refStart + 64*1024 - 32*1024; // last 32 KB
*retIndex=0;
*retMatch=0;
const uint8_t * start[] = {split, split2, refStart};
const uint8_t * end[] = {refEnd, split + Match_Length, split2 + Match_Length}; // TODO: is + Match_Length needed?
int i;
for(i=0; i<3; ++i)
{
const uint8_t *current_start = start[i];
const uint8_t *current_end = end[i];
while (current_start < current_end && current_start < refEnd)
{
FoundAtPosition = Railgun_Swampshine_BailOut(current_start, encStart, (uint32_t)(refEnd-current_start), Match_Length);
if (FoundAtPosition!=NULL)
{
if ( (refEnd-FoundAtPosition) & 0xE0 )
{
// Discard matches that have OFFSET with higher 3bits ALL zero.
// Having all 3 higher bits 0 is an indicator of a literal
*retMatch=Match_Length;
*retIndex=refEnd-FoundAtPosition;
return;
}
current_start=FoundAtPosition+1; // Exhaust the pool.
}
else
break;
}
}
}
unsigned int CompressM(void * _ret, const void * _src, unsigned int srcSize)
{
const uint8_t * src = _src;
uint8_t * ret = _ret;
unsigned int srcIndex=0;
unsigned int retIndex=0;
unsigned int index=0;
unsigned int match=0;
unsigned int notMatch=0;
uint8_t * notMatchStart=NULL;
const uint8_t * refStart=NULL;
const uint8_t * encEnd=NULL;
while(srcIndex < srcSize){
if(srcIndex>=REF_SIZE)
refStart=&src[srcIndex-REF_SIZE];
else
refStart=src;
if(srcIndex>=srcSize-ENC_SIZE)
encEnd=&src[srcSize];
else
encEnd=&src[srcIndex+ENC_SIZE];
if(srcIndex+ENC_SIZE < srcSize)
SearchIntoSlidingWindow(&index,&match,refStart,&src[srcIndex],&src[srcIndex]);
else
match=0; // Nothing to find.
if ( match==0 ) {
if(notMatch==0){
notMatchStart=&ret[retIndex];
retIndex++;
}
else if (notMatch==32) {
*notMatchStart=(uint8_t)31;
notMatch=0;
notMatchStart=&ret[retIndex];
retIndex++;
}
ret[retIndex]=src[srcIndex];
retIndex++;
notMatch++;
srcIndex++;
} else {
if(notMatch > 0){
*notMatchStart=(uint8_t)(notMatch-1);
notMatch=0;
}
// sanity check
if (index>0xFFFF) {return 0;}
// copy lower 2 bytes
ret[retIndex++] = index & 0xFF;
ret[retIndex++] = (index >> 8) & 0xFF;
srcIndex+=match;
}
}
if(notMatch > 0){
*notMatchStart=(uint8_t)(notMatch-1);
}
return retIndex;
}
// Railgun_Swampshine_BailOut, copyleft 2014-Jan-31, Kaze.
// Caution: For better speed the case 'if (cbPattern==1)' was removed, so Pattern must be longer than 1 char.
#define NeedleThreshold2vs4swampLITE 9+10 // Should be bigger than 9. BMH2 works up to this value (inclusive), if bigger then BMH4 takes over.
static const uint8_t * Railgun_Swampshine_BailOut(const uint8_t * pbTarget, const uint8_t * pbPattern, uint32_t cbTarget, uint32_t cbPattern)
{
const uint8_t * pbTargetMax = pbTarget + cbTarget;
register uint32_t ulHashPattern;
signed long count;
uint8_t bm_Horspool_Order2[256*256]; // Bitwise soon...
uint32_t i, Gulliver;
uint32_t PRIMALposition, PRIMALpositionCANDIDATE;
uint32_t PRIMALlength, PRIMALlengthCANDIDATE;
uint32_t j, FoundAtPosition;
if (cbPattern > cbTarget) return(NULL);
if ( cbPattern<4 ) {
// SSE2 i.e. 128bit Assembly rules here:
// ...
pbTarget = pbTarget+cbPattern;
ulHashPattern = ( (*(uint8_t *)(pbPattern))<<8 ) + *(pbPattern+(cbPattern-1));
if ( cbPattern==3 ) {
for ( ;; ) {
if ( ulHashPattern == ( (*(uint8_t *)(pbTarget-3))<<8 ) + *(pbTarget-1) ) {
if ( *(uint8_t *)(pbPattern+1) == *(uint8_t *)(pbTarget-2) ) return((pbTarget-3));
}
if ( (uint8_t)(ulHashPattern>>8) != *(pbTarget-2) ) {
pbTarget++;
if ( (uint8_t)(ulHashPattern>>8) != *(pbTarget-2) ) pbTarget++;
}
pbTarget++;
if (pbTarget > pbTargetMax) return(NULL);
}
} else {
}
for ( ;; ) {
if ( ulHashPattern == ( (*(uint8_t *)(pbTarget-2))<<8 ) + *(pbTarget-1) ) return((pbTarget-2));
if ( (uint8_t)(ulHashPattern>>8) != *(pbTarget-1) ) pbTarget++;
pbTarget++;
if (pbTarget > pbTargetMax) return(NULL);
}
} else { //if ( cbPattern<4 )
if ( cbPattern<=NeedleThreshold2vs4swampLITE ) {
// BMH order 2, needle should be >=4:
ulHashPattern = *(uint32_t *)(pbPattern); // First four bytes
for (i=0; i < 256*256; i++) {bm_Horspool_Order2[i]=0;}
for (i=0; i < cbPattern-1; i++) bm_Horspool_Order2[*(unsigned short *)(pbPattern+i)]=1;
i=0;
while (i <= cbTarget-cbPattern) {
Gulliver = 1; // 'Gulliver' is the skip
if ( bm_Horspool_Order2[*(unsigned short *)&pbTarget[i+cbPattern-1-1]] != 0 ) {
if ( bm_Horspool_Order2[*(unsigned short *)&pbTarget[i+cbPattern-1-1-2]] == 0 ) Gulliver = cbPattern-(2-1)-2; else {
if ( *(uint32_t *)&pbTarget[i] == ulHashPattern) { // This fast check ensures not missing a match (for remainder) when going under 0 in loop below:
count = cbPattern-4+1;
while ( count > 0 && *(uint32_t *)(pbPattern+count-1) == *(uint32_t *)(&pbTarget[i]+(count-1)) )
count = count-4;
if ( count <= 0 ) return(pbTarget+i);
}
}
} else Gulliver = cbPattern-(2-1);
i = i + Gulliver;
//GlobalI++; // Comment it, it is only for stats.
}
return(NULL);
} else { // if ( cbPattern<=NeedleThreshold2vs4swampLITE )
// Swampwalker_BAILOUT heuristic order 4 (Needle should be bigger than 4) [
// Needle: 1234567890qwertyuiopasdfghjklzxcv PRIMALposition=01 PRIMALlength=33 '1234567890qwertyuiopasdfghjklzxcv'
// Needle: vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv PRIMALposition=29 PRIMALlength=04 'vvvv'
// Needle: vvvvvvvvvvBOOMSHAKALAKAvvvvvvvvvv PRIMALposition=08 PRIMALlength=20 'vvvBOOMSHAKALAKAvvvv'
// Needle: Trollland PRIMALposition=01 PRIMALlength=09 'Trollland'
// Needle: Swampwalker PRIMALposition=01 PRIMALlength=11 'Swampwalker'
// Needle: licenselessness PRIMALposition=01 PRIMALlength=15 'licenselessness'
// Needle: alfalfa PRIMALposition=02 PRIMALlength=06 'lfalfa'
// Needle: Sandokan PRIMALposition=01 PRIMALlength=08 'Sandokan'
// Needle: shazamish PRIMALposition=01 PRIMALlength=09 'shazamish'
// Needle: Simplicius Simplicissimus PRIMALposition=06 PRIMALlength=20 'icius Simplicissimus'
// Needle: domilliaquadringenquattuorquinquagintillion PRIMALposition=01 PRIMALlength=32 'domilliaquadringenquattuorquinqu'
// Needle: boom-boom PRIMALposition=02 PRIMALlength=08 'oom-boom'
// Needle: vvvvv PRIMALposition=01 PRIMALlength=04 'vvvv'
// Needle: 12345 PRIMALposition=01 PRIMALlength=05 '12345'
// Needle: likey-likey PRIMALposition=03 PRIMALlength=09 'key-likey'
// Needle: BOOOOOM PRIMALposition=03 PRIMALlength=05 'OOOOM'
// Needle: aaaaaBOOOOOM PRIMALposition=02 PRIMALlength=09 'aaaaBOOOO'
// Needle: BOOOOOMaaaaa PRIMALposition=03 PRIMALlength=09 'OOOOMaaaa'
PRIMALlength=0;
for (i=0+(1); i < cbPattern-((4)-1)+(1)-(1); i++) { // -(1) because the last BB order 4 has no counterpart(s)
FoundAtPosition = cbPattern - ((4)-1) + 1;
PRIMALpositionCANDIDATE=i;
while ( PRIMALpositionCANDIDATE <= (FoundAtPosition-1) ) {
j = PRIMALpositionCANDIDATE + 1;
while ( j <= (FoundAtPosition-1) ) {
if ( *(uint32_t *)(pbPattern+PRIMALpositionCANDIDATE-(1)) == *(uint32_t *)(pbPattern+j-(1)) ) FoundAtPosition = j;
j++;
}
PRIMALpositionCANDIDATE++;
}
PRIMALlengthCANDIDATE = (FoundAtPosition-1)-i+1 +((4)-1);
if (PRIMALlengthCANDIDATE >= PRIMALlength) {PRIMALposition=i; PRIMALlength = PRIMALlengthCANDIDATE;}
if (cbPattern-i+1 <= PRIMALlength) break;
if (PRIMALlength > 128) break; // Bail Out for 129[+]
}
// Swampwalker_BAILOUT heuristic order 4 (Needle should be bigger than 4) ]
// Here we have 4 or bigger NewNeedle, apply order 2 for pbPattern[i+(PRIMALposition-1)] with length 'PRIMALlength' and compare the pbPattern[i] with length 'cbPattern':
PRIMALlengthCANDIDATE = cbPattern;
cbPattern = PRIMALlength;
pbPattern = pbPattern + (PRIMALposition-1);
// Revision 2 commented section ]
if ( cbPattern<=NeedleThreshold2vs4swampLITE ) {
// BMH order 2, needle should be >=4:
ulHashPattern = *(uint32_t *)(pbPattern); // First four bytes
for (i=0; i < 256*256; i++) {bm_Horspool_Order2[i]=0;}
for (i=0; i < cbPattern-1; i++) bm_Horspool_Order2[*(unsigned short *)(pbPattern+i)]=1;
i=0;
while (i <= cbTarget-cbPattern) {
Gulliver = 1; // 'Gulliver' is the skip
if ( bm_Horspool_Order2[*(unsigned short *)&pbTarget[i+cbPattern-1-1]] != 0 ) {
if ( bm_Horspool_Order2[*(unsigned short *)&pbTarget[i+cbPattern-1-1-2]] == 0 ) Gulliver = cbPattern-(2-1)-2; else {
if ( *(uint32_t *)&pbTarget[i] == ulHashPattern) { // This fast check ensures not missing a match (for remainder) when going under 0 in loop below:
count = cbPattern-4+1;
while ( count > 0 && *(uint32_t *)(pbPattern+count-1) == *(uint32_t *)(&pbTarget[i]+(count-1)) )
count = count-4;
// If we miss to hit then no need to compare the original: Needle
if ( count <= 0 ) {
// I have to add out-of-range checks...
// i-(PRIMALposition-1) >= 0
// &pbTarget[i-(PRIMALposition-1)] <= pbTargetMax - 4
// i-(PRIMALposition-1)+(count-1) >= 0
// &pbTarget[i-(PRIMALposition-1)+(count-1)] <= pbTargetMax - 4
// FIX from 2014-Apr-27:
// Because (count-1) is negative, above fours are reduced to next twos:
// i-(PRIMALposition-1)+(count-1) >= 0
// &pbTarget[i-(PRIMALposition-1)] <= pbTargetMax - 4
// The line below is BUGGY:
//if ( (i-(PRIMALposition-1) >= 0) && (&pbTarget[i-(PRIMALposition-1)] <= pbTargetMax - 4) && (&pbTarget[i-(PRIMALposition-1)+(count-1)] <= pbTargetMax - 4) ) {
// The line below is OKAY:
if ( ((signed int)(i-(PRIMALposition-1)+(count-1)) >= 0) && (&pbTarget[i-(PRIMALposition-1)] <= pbTargetMax - 4) ) {
if ( *(uint32_t *)&pbTarget[i-(PRIMALposition-1)] == *(uint32_t *)(pbPattern-(PRIMALposition-1))) { // This fast check ensures not missing a match (for remainder) when going under 0 in loop below:
count = PRIMALlengthCANDIDATE-4+1;
while ( count > 0 && *(uint32_t *)(pbPattern-(PRIMALposition-1)+count-1) == *(uint32_t *)(&pbTarget[i-(PRIMALposition-1)]+(count-1)) )
count = count-4;
if ( count <= 0 ) return(pbTarget+i-(PRIMALposition-1));
}
}
}
}
}
} else Gulliver = cbPattern-(2-1);
i = i + Gulliver;
//GlobalI++; // Comment it, it is only for stats.
}
return(NULL);
} else { // if ( cbPattern<=NeedleThreshold2vs4swampLITE )
// BMH pseudo-order 4, needle should be >=8+2:
ulHashPattern = *(uint32_t *)(pbPattern); // First four bytes
for (i=0; i < 256*256; i++) {bm_Horspool_Order2[i]=0;}
// In line below we "hash" 4bytes to 2bytes i.e. 16bit table, how to compute TOTAL number of BBs, 'cbPattern - Order + 1' is the number of BBs for text 'cbPattern' bytes long, for example, for cbPattern=11 'fastest fox' and Order=4 we have BBs = 11-4+1=8:
//"fast"
//"aste"
//"stes"
//"test"
//"est "
//"st f"
//"t fo"
//" fox"
//for (i=0; i < cbPattern-4+1; i++) bm_Horspool_Order2[( *(unsigned short *)(pbPattern+i+0) + *(unsigned short *)(pbPattern+i+2) ) & ( (1<<16)-1 )]=1;
//for (i=0; i < cbPattern-4+1; i++) bm_Horspool_Order2[( (*(uint32_t *)(pbPattern+i+0)>>16)+(*(uint32_t *)(pbPattern+i+0)&0xFFFF) ) & ( (1<<16)-1 )]=1;
// Above line is replaced by next one with better hashing:
for (i=0; i < cbPattern-4+1; i++) bm_Horspool_Order2[( (*(uint32_t *)(pbPattern+i+0)>>(16-1))+(*(uint32_t *)(pbPattern+i+0)&0xFFFF) ) & ( (1<<16)-1 )]=1;
i=0;
while (i <= cbTarget-cbPattern) {
Gulliver = 1;
//if ( bm_Horspool_Order2[( (*(uint32_t *)&pbTarget[i+cbPattern-1-1-2]>>16)+(*(uint32_t *)&pbTarget[i+cbPattern-1-1-2]&0xFFFF) ) & ( (1<<16)-1 )] != 0 ) { // DWORD #1
// Above line is replaced by next one with better hashing:
if ( bm_Horspool_Order2[( (*(uint32_t *)&pbTarget[i+cbPattern-1-1-2]>>(16-1))+(*(uint32_t *)&pbTarget[i+cbPattern-1-1-2]&0xFFFF) ) & ( (1<<16)-1 )] != 0 ) { // DWORD #1
//if ( bm_Horspool_Order2[( (*(uint32_t *)&pbTarget[i+cbPattern-1-1-2-4]>>16)+(*(uint32_t *)&pbTarget[i+cbPattern-1-1-2-4]&0xFFFF) ) & ( (1<<16)-1 )] == 0 ) Gulliver = cbPattern-(2-1)-2-4; else {
// Above line is replaced in order to strengthen the skip by checking the middle DWORD,if the two DWORDs are 'ab' and 'cd' i.e. [2x][2a][2b][2c][2d] then the middle DWORD is 'bc'.
// The respective offsets (backwards) are: -10/-8/-6/-4 for 'xa'/'ab'/'bc'/'cd'.
//if ( ( bm_Horspool_Order2[( (*(uint32_t *)&pbTarget[i+cbPattern-1-1-2-6]>>16)+(*(uint32_t *)&pbTarget[i+cbPattern-1-1-2-6]&0xFFFF) ) & ( (1<<16)-1 )] ) + ( bm_Horspool_Order2[( (*(uint32_t *)&pbTarget[i+cbPattern-1-1-2-4]>>16)+(*(uint32_t *)&pbTarget[i+cbPattern-1-1-2-4]&0xFFFF) ) & ( (1<<16)-1 )] ) + ( bm_Horspool_Order2[( (*(uint32_t *)&pbTarget[i+cbPattern-1-1-2-2]>>16)+(*(uint32_t *)&pbTarget[i+cbPattern-1-1-2-2]&0xFFFF) ) & ( (1<<16)-1 )] ) < 3 ) Gulliver = cbPattern-(2-1)-2-4-2; else {
// Above line is replaced by next one with better hashing:
// When using (16-1) right shifting instead of 16 we will have two different pairs (if they are equal), the highest bit being lost do the job especialy for ASCII texts with no symbols in range 128-255.
// Example for genomesque pair TT+TT being shifted by (16-1):
// T = 01010100
// TT = 01010100 01010100
// TTTT = 01010100 01010100 01010100 01010100
// TTTT>>16 = 00000000 00000000 01010100 01010100
// TTTT>>(16-1) = 00000000 00000000 10101000 10101000 <--- Due to the left shift by 1, the 8th bits of 1st and 2nd bytes are populated - usually they are 0 for English texts & 'ACGT' data.
//if ( ( bm_Horspool_Order2[( (*(uint32_t *)&pbTarget[i+cbPattern-1-1-2-6]>>(16-1))+(*(uint32_t *)&pbTarget[i+cbPattern-1-1-2-6]&0xFFFF) ) & ( (1<<16)-1 )] ) + ( bm_Horspool_Order2[( (*(uint32_t *)&pbTarget[i+cbPattern-1-1-2-4]>>(16-1))+(*(uint32_t *)&pbTarget[i+cbPattern-1-1-2-4]&0xFFFF) ) & ( (1<<16)-1 )] ) + ( bm_Horspool_Order2[( (*(uint32_t *)&pbTarget[i+cbPattern-1-1-2-2]>>(16-1))+(*(uint32_t *)&pbTarget[i+cbPattern-1-1-2-2]&0xFFFF) ) & ( (1<<16)-1 )] ) < 3 ) Gulliver = cbPattern-(2-1)-2-4-2; else {
// 'Maximus' uses branched 'if', again.
if ( \
( bm_Horspool_Order2[( (*(uint32_t *)&pbTarget[i+cbPattern-1-1-2-6 +1]>>(16-1))+(*(uint32_t *)&pbTarget[i+cbPattern-1-1-2-6 +1]&0xFFFF) ) & ( (1<<16)-1 )] ) == 0 \
|| ( bm_Horspool_Order2[( (*(uint32_t *)&pbTarget[i+cbPattern-1-1-2-4 +1]>>(16-1))+(*(uint32_t *)&pbTarget[i+cbPattern-1-1-2-4 +1]&0xFFFF) ) & ( (1<<16)-1 )] ) == 0 \
) Gulliver = cbPattern-(2-1)-2-4-2 +1; else {
// Above line is not optimized (several a SHR are used), we have 5 non-overlapping WORDs, or 3 overlapping WORDs, within 4 overlapping DWORDs so:
//if ( ( bm_Horspool_Order2[( (*(uint32_t *)&pbTarget[i+cbPattern-1-1-2-4]>>16)+(*(uint32_t *)&pbTarget[i+cbPattern-1-1-2-4]&0xFFFF) ) & ( (1<<16)-1 )] ) + ( bm_Horspool_Order2[( (*(uint32_t *)&pbTarget[i+cbPattern-1-1-2-8]>>16)+(*(uint32_t *)&pbTarget[i+cbPattern-1-1-2-8]&0xFFFF) ) & ( (1<<16)-1 )] ) < 2 ) Gulliver = cbPattern-(2-1)-2-8; else {
if ( *(uint32_t *)&pbTarget[i] == ulHashPattern) {
// Order 4 [
// Let's try something "outrageous" like comparing with[out] overlap BBs 4bytes long instead of 1 byte back-to-back:
// Inhere we are using order 4, 'cbPattern - Order + 1' is the number of BBs for text 'cbPattern' bytes long, for example, for cbPattern=11 'fastest fox' and Order=4 we have BBs = 11-4+1=8:
//0:"fast" if the comparison failed here, 'count' is 1; 'Gulliver' is cbPattern-(4-1)-7
//1:"aste" if the comparison failed here, 'count' is 2; 'Gulliver' is cbPattern-(4-1)-6
//2:"stes" if the comparison failed here, 'count' is 3; 'Gulliver' is cbPattern-(4-1)-5
//3:"test" if the comparison failed here, 'count' is 4; 'Gulliver' is cbPattern-(4-1)-4
//4:"est " if the comparison failed here, 'count' is 5; 'Gulliver' is cbPattern-(4-1)-3
//5:"st f" if the comparison failed here, 'count' is 6; 'Gulliver' is cbPattern-(4-1)-2
//6:"t fo" if the comparison failed here, 'count' is 7; 'Gulliver' is cbPattern-(4-1)-1
//7:" fox" if the comparison failed here, 'count' is 8; 'Gulliver' is cbPattern-(4-1)
count = cbPattern-4+1;
// Below comparison is UNIdirectional:
while ( count > 0 && *(uint32_t *)(pbPattern+count-1) == *(uint32_t *)(&pbTarget[i]+(count-1)) )
count = count-4;
// count = cbPattern-4+1 = 23-4+1 = 20
// boomshakalakaZZZZZZ[ZZZZ] 20
// boomshakalakaZZ[ZZZZ]ZZZZ 20-4
// boomshakala[kaZZ]ZZZZZZZZ 20-8 = 12
// boomsha[kala]kaZZZZZZZZZZ 20-12 = 8
// boo[msha]kalakaZZZZZZZZZZ 20-16 = 4
// If we miss to hit then no need to compare the original: Needle
if ( count <= 0 ) {
// I have to add out-of-range checks...
// i-(PRIMALposition-1) >= 0
// &pbTarget[i-(PRIMALposition-1)] <= pbTargetMax - 4
// i-(PRIMALposition-1)+(count-1) >= 0
// &pbTarget[i-(PRIMALposition-1)+(count-1)] <= pbTargetMax - 4
// FIX from 2014-Apr-27:
// Because (count-1) is negative, above fours are reduced to next twos:
// i-(PRIMALposition-1)+(count-1) >= 0
// &pbTarget[i-(PRIMALposition-1)] <= pbTargetMax - 4
// The line below is BUGGY:
//if ( (i-(PRIMALposition-1) >= 0) && (&pbTarget[i-(PRIMALposition-1)] <= pbTargetMax - 4) && (&pbTarget[i-(PRIMALposition-1)+(count-1)] <= pbTargetMax - 4) ) {
// The line below is OKAY:
if ( ((signed int)(i-(PRIMALposition-1)+(count-1)) >= 0) && (&pbTarget[i-(PRIMALposition-1)] <= pbTargetMax - 4) ) {
if ( *(uint32_t *)&pbTarget[i-(PRIMALposition-1)] == *(uint32_t *)(pbPattern-(PRIMALposition-1))) { // This fast check ensures not missing a match (for remainder) when going under 0 in loop below:
count = PRIMALlengthCANDIDATE-4+1;
while ( count > 0 && *(uint32_t *)(pbPattern-(PRIMALposition-1)+count-1) == *(uint32_t *)(&pbTarget[i-(PRIMALposition-1)]+(count-1)) )
count = count-4;
if ( count <= 0 ) return(pbTarget+i-(PRIMALposition-1));
}
}
}
// In order to avoid only-left or only-right WCS the memcmp should be done as left-to-right and right-to-left AT THE SAME TIME.
// Below comparison is BIdirectional. It pays off when needle is 8+++ long:
// for (count = cbPattern-4+1; count > 0; count = count-4) {
// if ( *(uint32_t *)(pbPattern+count-1) != *(uint32_t *)(&pbTarget[i]+(count-1)) ) {break;};
// if ( *(uint32_t *)(pbPattern+(cbPattern-4+1)-count) != *(uint32_t *)(&pbTarget[i]+(cbPattern-4+1)-count) ) {count = (cbPattern-4+1)-count +(1); break;} // +(1) because two lookups are implemented as one, also no danger of 'count' being 0 because of the fast check outwith the 'while': if ( *(uint32_t *)&pbTarget[i] == ulHashPattern)
// }
// if ( count <= 0 ) return(pbTarget+i);
// Checking the order 2 pairs in mismatched DWORD, all the 3:
//if ( bm_Horspool_Order2[*(unsigned short *)&pbTarget[i+count-1]] == 0 ) Gulliver = count; // 1 or bigger, as it should
//if ( bm_Horspool_Order2[*(unsigned short *)&pbTarget[i+count-1+1]] == 0 ) Gulliver = count+1; // 1 or bigger, as it should
//if ( bm_Horspool_Order2[*(unsigned short *)&pbTarget[i+count-1+1+1]] == 0 ) Gulliver = count+1+1; // 1 or bigger, as it should
// if ( bm_Horspool_Order2[*(unsigned short *)&pbTarget[i+count-1]] + bm_Horspool_Order2[*(unsigned short *)&pbTarget[i+count-1+1]] + bm_Horspool_Order2[*(unsigned short *)&pbTarget[i+count-1+1+1]] < 3 ) Gulliver = count; // 1 or bigger, as it should, THE MIN(count,count+1,count+1+1)
// Above compound 'if' guarantees not that Gulliver > 1, an example:
// Needle: fastest tax
// Window: ...fastast tax...
// After matching ' tax' vs ' tax' and 'fast' vs 'fast' the mismathced DWORD is 'test' vs 'tast':
// 'tast' when factorized down to order 2 yields: 'ta','as','st' - all the three when summed give 1+1+1=3 i.e. Gulliver remains 1.
// Roughly speaking, this attempt maybe has its place in worst-case scenarios but not in English text and even not in ACGT data, that's why I commented it in original 'Shockeroo'.
//if ( bm_Horspool_Order2[( (*(uint32_t *)&pbTarget[i+count-1]>>16)+(*(uint32_t *)&pbTarget[i+count-1]&0xFFFF) ) & ( (1<<16)-1 )] == 0 ) Gulliver = count; // 1 or bigger, as it should
// Above line is replaced by next one with better hashing:
// if ( bm_Horspool_Order2[( (*(uint32_t *)&pbTarget[i+count-1]>>(16-1))+(*(uint32_t *)&pbTarget[i+count-1]&0xFFFF) ) & ( (1<<16)-1 )] == 0 ) Gulliver = count; // 1 or bigger, as it should
// Order 4 ]
}
}
} else Gulliver = cbPattern-(2-1)-2; // -2 because we check the 4 rightmost bytes not 2.
i = i + Gulliver;
//GlobalI++; // Comment it, it is only for stats.
}
return(NULL);
} // if ( cbPattern<=NeedleThreshold2vs4swampLITE )
} // if ( cbPattern<=NeedleThreshold2vs4swampLITE )
} //if ( cbPattern<4 )
}
ssize_t DecompressSafe(const void * _in, ssize_t in_size, void * _out, ssize_t out_size)
{
const uint8_t * in = _in;
uint8_t * out = _out;
ssize_t in_index = 0;
ssize_t out_index = 0;
// main loop may go 32 bytes out of limit on input
const size_t main_loop_in_limit = in_size < 32 ? 0 : in_size - 32;
// and 31 on output
const size_t main_loop_out_limit = out_size < 31 ? 0 : out_size - 31;
// The head loop
while(in_index < main_loop_in_limit && out_index < main_loop_out_limit && out_index < 65535)
{
// 16 bits, AAAAABBB CCCCCCCC
// If BBB == 0, we have a literal.
// AAAAA is its length and CCCCCCCC - its first byte
// If BBB != 0, we have a match.
// It's always 8-byte long
// and the whole two bytes are a little endian match offset.
// Note a funny side effect, we can't encode any match in the stream
// because match distances can't have all 3 least significant bits zeroed.
uint_fast16_t two_bytes = load_2_bytes_le(in + in_index);
if ((two_bytes & 0x07) == 0)
{
// literal
const int_fast16_t literal_length = (two_bytes & 0xFF) >> 3;
// a wild copy, at least 1 byte too large
// (since max literal length is 31)
// but loop limits prevent us from getting out of bounds
// TODO: on x86 aligned copy of 32 bytes is always faster than aligned copy of literal_length
// x86 sucks as a testbed for aligned access performance, check it elsewhere
copy_at_most_32_bytes(out + out_index, in + in_index + 1, 32);
out_index += literal_length;
in_index += literal_length + 1;
}
else
{
// match
in_index += 2;
ssize_t in_size_left = in_size - in_index - 2;
if (out_index < two_bytes)
return -1;
// match length is always 8 bytes
copy_8_bytes(out + out_index, out + out_index - two_bytes);
out_index += 8;
}
}
// The main loop
while(in_index < main_loop_in_limit && out_index < main_loop_out_limit)
{
uint_fast16_t two_bytes = load_2_bytes_le(in + in_index);
if ((two_bytes & 0x07) == 0)
{
// literal
const int_fast16_t literal_length = (two_bytes & 0xFF) >> 3;
// a wild copy, at least 1 byte too large
// (since max literal length is 31)
// but loop limits prevent us from getting out of bounds
copy_at_most_32_bytes(out + out_index, in + in_index + 1, 32);
out_index += literal_length;
in_index += literal_length + 1;
}
else
{
// match
in_index += sizeof(uint16_t);
// match length is always 8 bytes
copy_8_bytes(out + out_index, out + out_index - two_bytes);
out_index += 8;
}
}
// The tail loop
while(in_index < (in_size - 1) && out_index < out_size)
{
uint_fast16_t two_bytes = load_2_bytes_le(in + in_index);
ssize_t out_size_left = out_size - out_index;
ssize_t in_size_left = in_size - in_index;
if ((two_bytes & 0x07) == 0)
{
// literal
in_size_left -= 1;
const ssize_t size_left = in_size_left > out_size_left ? out_size_left : in_size_left;
const int_fast16_t literal_length = (two_bytes & 0xFF) >> 3;
if (literal_length > size_left)
return -1;
memcpy(out + out_index, in + in_index + 1, literal_length);
out_index += literal_length;
in_index += literal_length + 1;
}
else
{
// match
in_index += 2;
in_size_left -= 2;
// match length is always 8 bytes
if (out_size_left < 8 || out_index < two_bytes)
return -1;
copy_8_bytes(out + out_index, out + out_index - two_bytes);
out_index += 8;
}
}
return in_index == in_size ? out_index : -1;
}