From 646693e3be39ffeb40451499b7689edbd2ff8d1d Mon Sep 17 00:00:00 2001
From: Yann Collet <yann.collet.73@gmail.com>
Date: Thu, 24 Mar 2016 02:31:27 +0100
Subject: [PATCH] support for alternate offset (fusion)

---
 lib/zstd_compress.c   | 14 +++++++-------
 lib/zstd_decompress.c | 19 +++++++++++--------
 lib/zstd_internal.h   |  2 +-
 3 files changed, 19 insertions(+), 16 deletions(-)

diff --git a/lib/zstd_compress.c b/lib/zstd_compress.c
index 8d2eff0b3..f79109a1d 100644
--- a/lib/zstd_compress.c
+++ b/lib/zstd_compress.c
@@ -661,7 +661,7 @@ size_t ZSTD_compressSequences(ZSTD_CCtx* zc,
     }   }
 
     /* Offset codes */
-    { size_t i; for (i=0; i<nbSeq; i++) ofCodeTable[i] = offsetTable[i] ? (BYTE)ZSTD_highbit(offsetTable[i]) + 1 : 0; }
+    { size_t i; for (i=0; i<nbSeq; i++) ofCodeTable[i] = (BYTE)ZSTD_highbit(offsetTable[i]); }
 
     {   U32 max = MaxOff;
         size_t const mostFrequent = FSE_countFast(count, &max, ofCodeTable, nbSeq);
@@ -745,7 +745,7 @@ size_t ZSTD_compressSequences(ZSTD_CCtx* zc,
         FSE_initCState2(&stateLitLength,   CTable_LitLength,   llCodeTable[nbSeq-1]);
         BIT_addBits(&blockStream, llTable[nbSeq-1], LL_bits[llCodeTable[nbSeq-1]]);
         BIT_addBits(&blockStream, mlTable[nbSeq-1], ML_bits[mlCodeTable[nbSeq-1]]);
-        BIT_addBits(&blockStream, offsetTable[nbSeq-1], ofCodeTable[nbSeq-1] ? (ofCodeTable[nbSeq-1]-1) : 0);
+        BIT_addBits(&blockStream, offsetTable[nbSeq-1], ofCodeTable[nbSeq-1]);
         BIT_flushBits(&blockStream);
 
         {   size_t n;
@@ -755,12 +755,12 @@ size_t ZSTD_compressSequences(ZSTD_CCtx* zc,
                 const BYTE llCode = llCodeTable[n];
                 const U32  llBits = LL_bits[llCode];
                 const U32  mlBits = ML_bits[mlCode];
-                const U32  ofBits = (ofCode-1) + (!ofCode);
+                const U32  ofBits = ofCode;
                                                                                 /* (7)*/  /* (7)*/
                 FSE_encodeSymbol(&blockStream, &stateOffsetBits, ofCode);       /* 25 */  /* 35 */
                 FSE_encodeSymbol(&blockStream, &stateMatchLength, mlCode);      /* 17 */  /* 17 */
                 FSE_encodeSymbol(&blockStream, &stateLitLength, llCode);        /* 16 */  /* 26 */
-                if (ofBits + mlBits + llBits > 64 - 7 - 27)
+                if (ofBits + mlBits + llBits > 64 - 7 - (LLFSELog+MLFSELog+OffFSELog))
                     BIT_flushBits(&blockStream);
                 BIT_addBits(&blockStream, llTable[n], llBits);
                 BIT_addBits(&blockStream, mlTable[n], mlBits);
@@ -798,8 +798,8 @@ MEM_STATIC void ZSTD_storeSeq(seqStore_t* seqStorePtr, size_t litLength, const B
     static const BYTE* g_start = NULL;
     const U32 pos = (U32)(literals - g_start);
     if (g_start==NULL) g_start = literals;
-    if ((pos > 10354000) && (pos < 10355000))
-    printf("pos %6u : %3u literals & match %3u bytes at distance %6u \n",
+    if ((pos > 23945000) && (pos < 23946800))
+    printf("Cpos %6u :%4u literals & match %3u bytes at distance %6u \n",
            pos, (U32)litLength, (U32)matchCode+MINMATCH, (U32)offsetCode);
 #endif
 #if ZSTD_OPT_DEBUG == 3
@@ -818,7 +818,7 @@ MEM_STATIC void ZSTD_storeSeq(seqStore_t* seqStorePtr, size_t litLength, const B
     else *seqStorePtr->litLength++ = (U16)litLength;
 
     /* match offset */
-    *(seqStorePtr->offset++) = (U32)offsetCode;
+    *(seqStorePtr->offset++) = (U32)offsetCode + 1;
 
     /* match Length */
     if (matchCode>=65535) { *(seqStorePtr->matchLength++) = 65535; seqStorePtr->longLength = (U32)matchCode; }
diff --git a/lib/zstd_decompress.c b/lib/zstd_decompress.c
index b4a2184e2..48614c358 100644
--- a/lib/zstd_decompress.c
+++ b/lib/zstd_decompress.c
@@ -634,9 +634,12 @@ static void ZSTD_decodeSequence(seq_t* seq, seqState_t* seqState, const U32 mls)
 
     U32 const llBits = LL_bits[llCode];
     U32 const mlBits = ML_bits[mlCode];
-    U32 const ofBits = ofCode ? ofCode-1 : 0;
+    U32 const ofBits = ofCode;
+    U32 const totalBits = llBits+mlBits+ofBits;
 
-    size_t const allBits = BIT_readBits(&(seqState->DStream), llBits+mlBits+ofBits);
+    size_t const allBits = BIT_readBits(&(seqState->DStream), totalBits);
+
+    if (totalBits > 64 - 7 - (LLFSELog+MLFSELog+OffFSELog)) BIT_reloadDStream(&(seqState->DStream));
 
     static const U32 LL_base[MaxLL+1] = {
                              0,  1,  2,  3,  4,  5,  6,  7,  8,  9,   10,    11,    12,    13,    14,     15,
@@ -650,10 +653,10 @@ static void ZSTD_decodeSequence(seq_t* seq, seqState_t* seqState, const U32 mls)
                             0x1000, 0x2000, 0x4000, 0x8000, 0x10000 };
 
     static const U32 OF_base[MaxOff+1] = {
-                1 /*fake*/, 1, 2, 4, 8, 0x10, 0x20, 0x40,
-                0x80, 0x100, 0x200, 0x400, 0x800, 0x1000, 0x2000, 0x4000,
-                0x8000, 0x10000, 0x20000, 0x40000, 0x80000, 0x100000, 0x200000, 0x400000,
-                0x800000, 0x1000000, 0x2000000, 0x4000000, /*fake*/ 1, 1, 1, 1 };
+                 0,        1,       3,       7,     0xF,     0x1F,     0x3F,     0x7F,
+                 0xFF,   0x1FF,   0x3FF,   0x7FF,   0xFFF,   0x1FFF,   0x3FFF,   0x7FFF,
+                 0xFFFF, 0x1FFFF, 0x3FFFF, 0x7FFFF, 0xFFFFF, 0x1FFFFF, 0x3FFFFF, 0x7FFFFF,
+                 0xFFFFFF, 0x1FFFFFF, 0x3FFFFFF, /*fake*/ 1, 1, 1, 1, 1 };
 
     /* sequence */
     seq->litLength = LL_base[llCode] + BIT_getLowerBits(allBits, llBits);
@@ -792,8 +795,8 @@ static size_t ZSTD_decompressSequences(
             ZSTD_decodeSequence(&sequence, &seqState, mls);
 #if 0  /* for debug */
             {   U32 pos = (U32)(op-base);
-                if ((pos > 10354000) && (pos < 10355000))
-                    printf("pos %6u : %3u literals & match %3u bytes at distance %6u \n",
+                if ((pos > 23945280) && (pos < 23946797))
+                    printf("Dpos %6u : %3u literals & match %3u bytes at distance %6u \n",
                         pos, (U32)sequence.litLength, (U32)sequence.matchLength, (U32)sequence.offset);
             }
 #endif
diff --git a/lib/zstd_internal.h b/lib/zstd_internal.h
index fa6c93ca8..4ce44399e 100644
--- a/lib/zstd_internal.h
+++ b/lib/zstd_internal.h
@@ -110,7 +110,7 @@ typedef enum { bt_compressed, bt_raw, bt_rle, bt_end } blockType_t;
 #define MaxSeq MAX(MaxLL, MaxML)   /* Assumption : MaxOff < MaxLL,MaxML */
 #define MLFSELog    9
 #define LLFSELog    9
-#define OffFSELog   9
+#define OffFSELog   8
 
 #define FSE_ENCODING_RAW     0
 #define FSE_ENCODING_RLE     1
-- 
2.47.2