/*

 * Copyright (C) 2013-2015 Willy Tarreau <w@1wt.eu>

 *

 * Permission is hereby granted, free of charge, to any person obtaining

 * a copy of this software and associated documentation files (the

 * "Software"), to deal in the Software without restriction, including

 * without limitation the rights to use, copy, modify, merge, publish,

 * distribute, sublicense, and/or sell copies of the Software, and to

 * permit persons to whom the Software is furnished to do so, subject to

 * the following conditions:

 *

 * The above copyright notice and this permission notice shall be

 * included in all copies or substantial portions of the Software.

 *

 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,

 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES

 * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND

 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT

 * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,

 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING

 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR

 * OTHER DEALINGS IN THE SOFTWARE.

 */

#include <stdio.h>

#include <string.h>

#include "import/slz.h"

#include "import/slz-prv.h"

#include "import/slz-tables.h"

/* if PRECOMPUTE_TABLES not set, then tables.h does not provide fh_dist_table

 * table as we need to recompute it.

 */

#ifndef PRECOMPUTE_TABLES

static uint32_t fh_dist_table[32768];

#endif // ifndef PRECOMPUTE_TABLES

/* First, RFC1951-specific declarations and extracts from the RFC.

 *

 * RFC1951 - deflate stream format

             * Data elements are packed into bytes in order of

               increasing bit number within the byte, i.e., starting

               with the least-significant bit of the byte.

             * Data elements other than Huffman codes are packed

               starting with the least-significant bit of the data

               element.

             * Huffman codes are packed starting with the most-

               significant bit of the code.

      3.2.3. Details of block format

         Each block of compressed data begins with 3 header bits

         containing the following data:

            first bit       BFINAL

            next 2 bits     BTYPE

         Note that the header bits do not necessarily begin on a byte

         boundary, since a block does not necessarily occupy an integral

         number of bytes.

         BFINAL is set if and only if this is the last block of the data

         set.

         BTYPE specifies how the data are compressed, as follows:

            00 - no compression

            01 - compressed with fixed Huffman codes

            10 - compressed with dynamic Huffman codes

            11 - reserved (error)

      3.2.4. Non-compressed blocks (BTYPE=00)

         Any bits of input up to the next byte boundary are ignored.

         The rest of the block consists of the following information:

              0   1   2   3   4...

            +---+---+---+---+================================+

            |  LEN  | NLEN  |... LEN bytes of literal data...|

            +---+---+---+---+================================+

         LEN is the number of data bytes in the block.  NLEN is the

         one's complement of LEN.

      3.2.5. Compressed blocks (length and distance codes)

         As noted above, encoded data blocks in the "deflate" format

         consist of sequences of symbols drawn from three conceptually

         distinct alphabets: either literal bytes, from the alphabet of

         byte values (0..255), or <length, backward distance> pairs,

         where the length is drawn from (3..258) and the distance is

         drawn from (1..32,768).  In fact, the literal and length

         alphabets are merged into a single alphabet (0..285), where

         values 0..255 represent literal bytes, the value 256 indicates

         end-of-block, and values 257..285 represent length codes

         (possibly in conjunction with extra bits following the symbol

         code) as follows:

Length encoding :

                Extra               Extra               Extra

            Code Bits Length(s) Code Bits Lengths   Code Bits Length(s)

            ---- ---- ------     ---- ---- -------   ---- ---- -------

             257   0     3       267   1   15,16     277   4   67-82

             258   0     4       268   1   17,18     278   4   83-98

             259   0     5       269   2   19-22     279   4   99-114

             260   0     6       270   2   23-26     280   4  115-130

             261   0     7       271   2   27-30     281   5  131-162

             262   0     8       272   2   31-34     282   5  163-194

             263   0     9       273   3   35-42     283   5  195-226

             264   0    10       274   3   43-50     284   5  227-257

             265   1  11,12      275   3   51-58     285   0    258

             266   1  13,14      276   3   59-66

Distance encoding :

                  Extra           Extra               Extra

             Code Bits Dist  Code Bits   Dist     Code Bits Distance

             ---- ---- ----  ---- ----  ------    ---- ---- --------

               0   0    1     10   4     33-48    20    9   1025-1536

               1   0    2     11   4     49-64    21    9   1537-2048

               2   0    3     12   5     65-96    22   10   2049-3072

               3   0    4     13   5     97-128   23   10   3073-4096

               4   1   5,6    14   6    129-192   24   11   4097-6144

               5   1   7,8    15   6    193-256   25   11   6145-8192

               6   2   9-12   16   7    257-384   26   12  8193-12288

               7   2  13-16   17   7    385-512   27   12 12289-16384

               8   3  17-24   18   8    513-768   28   13 16385-24576

               9   3  25-32   19   8   769-1024   29   13 24577-32768

      3.2.6. Compression with fixed Huffman codes (BTYPE=01)

         The Huffman codes for the two alphabets are fixed, and are not

         represented explicitly in the data.  The Huffman code lengths

         for the literal/length alphabet are:

                   Lit Value    Bits        Codes

                   ---------    ----        -----

                     0 - 143     8          00110000 through

                                            10111111

                   144 - 255     9          110010000 through

                                            111111111

                   256 - 279     7          0000000 through

                                            0010111

                   280 - 287     8          11000000 through

                                            11000111

         The code lengths are sufficient to generate the actual codes,

         as described above; we show the codes in the table for added

         clarity.  Literal/length values 286-287 will never actually

         occur in the compressed data, but participate in the code

         construction.

         Distance codes 0-31 are represented by (fixed-length) 5-bit

         codes, with possible additional bits as shown in the table

         shown in Paragraph 3.2.5, above.  Note that distance codes 30-

         31 will never actually occur in the compressed data.

*/

/* back references, built in a way that is optimal for 32/64 bits */

/* format:

 * bit0..31  = word

 * bit32..63 = last position in buffer of similar content

 */

union ref {

  struct {

    uint32_t pos;

    uint32_t word;

  } by32;

  uint64_t by64;

};

#if defined(__SIZEOF_LONG__) && (__SIZEOF_LONG__ - 0 > 4) && defined(UNALIGNED_LE_OK)

/* enqueue code x of <xbits> bits (LSB aligned, at most 24) and copy complete

 * 32-bit words into output buffer. X must not contain non-zero bits above

 * xbits.

 */

static inline void enqueue24(struct slz_stream *strm, uint64_t x, uint32_t xbits)

{

  uint64_t queue = strm->queue + (x << strm->qbits);

  uint32_t qbits = strm->qbits + xbits;

  if (__builtin_expect(qbits >= 32, 1)) {

    *(uint32_t *)strm->outbuf = queue;

    queue >>= 32;

    qbits -= 32;

    strm->outbuf += 4;

  }

  strm->queue = queue;

  strm->qbits = qbits;

}

#define enqueue8 enqueue24

/* flush the queue and align to next byte */

static inline void flush_bits(struct slz_stream *strm)

{

  if (strm->qbits > 0)

    *strm->outbuf++ = strm->queue;

  if (strm->qbits > 8)

    *strm->outbuf++ = strm->queue >> 8;

  if (strm->qbits > 16)

    *strm->outbuf++ = strm->queue >> 16;

  if (strm->qbits > 24)

    *strm->outbuf++ = strm->queue >> 24;

  strm->queue = 0;

  strm->qbits = 0;

}

#else /* non-64 bit or aligned or big endian */

/* enqueue code x of <xbits> bits (LSB aligned, at most 24) and copy complete

 * bytes into out buf. X must not contain non-zero bits above xbits. Prefer

 * enqueue8() when xbits is known for being 8 or less.

 */

static void enqueue24(struct slz_stream *strm, uint32_t x, uint32_t xbits)

{

  uint32_t queue = strm->queue + (x << strm->qbits);

  uint32_t qbits = strm->qbits + xbits;

  if (qbits >= 16) {

#ifndef UNALIGNED_LE_OK

    strm->outbuf[0] = queue;

    strm->outbuf[1] = queue >> 8;

#else

    *(uint16_t *)strm->outbuf = queue;

#endif

    strm->outbuf += 2;

    queue >>= 16;

    qbits -= 16;

  }

  if (qbits >= 8) {

    qbits -= 8;

    *strm->outbuf++ = queue;

    queue >>= 8;

  }

  strm->qbits = qbits;

  strm->queue = queue;

  return;

}

/* enqueue code x of <xbits> bits (at most 8) and copy complete bytes into

 * out buf. X must not contain non-zero bits above xbits.

 */

static inline void enqueue8(struct slz_stream *strm, uint32_t x, uint32_t xbits)

{

  uint32_t queue = strm->queue + (x << strm->qbits);

  uint32_t qbits = strm->qbits + xbits;

  if (__builtin_expect((signed)(qbits - 8) >= 0, 1)) {

    qbits -= 8;

    *strm->outbuf++ = queue;

    queue >>= 8;

  }

  strm->qbits = qbits;

  strm->queue = queue;

}

/* align to next byte */

static inline void flush_bits(struct slz_stream *strm)

{

  if (strm->qbits > 0)

    *strm->outbuf++ = strm->queue;

  if (strm->qbits > 8)

    *strm->outbuf++ = strm->queue >> 8;

  strm->queue = 0;

  strm->qbits = 0;

}

#endif

/* only valid if buffer is already aligned */

static inline void copy_8b(struct slz_stream *strm, uint32_t x)

{

  *strm->outbuf++ = x;

}

/* only valid if buffer is already aligned */

static inline void copy_16b(struct slz_stream *strm, uint32_t x)

{

  strm->outbuf[0] = x;

  strm->outbuf[1] = x >> 8;

  strm->outbuf += 2;

}

/* only valid if buffer is already aligned */

static inline void copy_32b(struct slz_stream *strm, uint32_t x)

{

  strm->outbuf[0] = x;

  strm->outbuf[1] = x >> 8;

  strm->outbuf[2] = x >> 16;

  strm->outbuf[3] = x >> 24;

  strm->outbuf += 4;

}

/* Using long because faster on 64-bit (can save one shift) */

static inline void send_huff(struct slz_stream *strm, unsigned long code)

{

  uint32_t bits;

  code = fixed_huff[code];

  bits = code & 15;

  code >>= 4;

  enqueue24(strm, code, bits);

}

static inline void send_eob(struct slz_stream *strm)

{

  enqueue8(strm, 0, 7); // direct encoding of 256 = EOB (cf RFC1951)

}

/* copies <len> litterals from <buf>. <more> indicates that there are data past

 * buf + <len>. <len> must not be null.

 */

static void copy_lit(struct slz_stream *strm, const void *buf, uint32_t len, int more)

{

  uint32_t len2;

  do {

    len2 = len;

    if (__builtin_expect(len2 > 65535, 0))

      len2 = 65535;

    len -= len2;

    if (strm->state != SLZ_ST_EOB)

      send_eob(strm);

    strm->state = (more || len) ? SLZ_ST_EOB : SLZ_ST_DONE;

    enqueue8(strm, !(more || len), 3); // BFINAL = !more ; BTYPE = 00

    flush_bits(strm);

    copy_16b(strm, len2);  // len2

    copy_16b(strm, ~len2); // nlen2

    memcpy(strm->outbuf, buf, len2);

    buf += len2;

    strm->outbuf += len2;

  } while (len);

}

/* copies <len> litterals from <buf>. <more> indicates that there are data past

 * buf + <len>. <len> must not be null.

 */

static void copy_lit_huff(struct slz_stream *strm, const unsigned char *buf, uint32_t len, int more)

{

  uint32_t pos;

  /* This ugly construct limits the mount of tests and optimizes for the

   * most common case (more > 0).

   */

  if (strm->state == SLZ_ST_EOB) {

  eob:

    strm->state = more ? SLZ_ST_FIXED : SLZ_ST_LAST;

    enqueue8(strm, 2 + !more, 3); // BFINAL = !more ; BTYPE = 01

  }

  else if (!more) {

    send_eob(strm);

    goto eob;

  }

  pos = 0;

  do {

    send_huff(strm, buf[pos++]);

  } while (pos < len);

}

/* sets <count> BYTES to -32769 in <refs> so that any uninitialized entry will

 * verify (pos-last-1 >= 32768) and be ignored. <count> must be a multiple of

 * 128 bytes and <refs> must be at least one count in length. It's supposed to

 * be applied to 64-bit aligned data exclusively, which makes it slightly

 * faster than the regular memset() since no alignment check is performed.

 */

static void reset_refs(union ref *refs, long count)

{

  /* avoid a shift/mask by casting to void* */

  union ref *end = (void *)refs + count;

  do {

    refs[ 0].by64 = -32769;

    refs[ 1].by64 = -32769;

    refs[ 2].by64 = -32769;

    refs[ 3].by64 = -32769;

    refs[ 4].by64 = -32769;

    refs[ 5].by64 = -32769;

    refs[ 6].by64 = -32769;

    refs[ 7].by64 = -32769;

    refs[ 8].by64 = -32769;

    refs[ 9].by64 = -32769;

    refs[10].by64 = -32769;

    refs[11].by64 = -32769;

    refs[12].by64 = -32769;

    refs[13].by64 = -32769;

    refs[14].by64 = -32769;

    refs[15].by64 = -32769;

    refs += 16;

  } while (refs < end);

}

/* Number of bits wasted by the 9-bit literals above which it becomes

 * preferable to send the pending literals as a stored block. It corresponds to

 * the cost of leaving the fixed huffman encoding and coming back to it: EOB

 * (7 bits) + block type (3 bits) + alignment (up to 7 bits) + LEN and NLEN

 * (32 bits) + block type of the next block (3 bits), that is 52 bits. Two

 * cheaper variants are needed for the last literals of a block: nothing

 * follows the stored block while the huffman encoding still has to send an EOB

 * (10 bits less), and if the stream is still in EOB state, no EOB has to be

 * sent and the block type is needed in both cases (10 more bits less). Using a

 * larger value than these would leave the output larger than the same data

 * sent as stored blocks, in violation of the promise made above.

 */

#define SLZ_SWITCH_COST      52

#define SLZ_LAST_COST        42

#define SLZ_LAST_COST_EOB    32

/* Maximum number of bits the fixed huffman encoding is allowed to be behind

 * the equivalent stored blocks before the encoder stops trusting the local

 * decisions above and falls back to stored blocks only (see <debt> in

 * slz_rfc1951_encode_blk()). This bounds by 25 bytes the amount by which a

 * stream may exceed the size of the same data sent as stored blocks. It must

 * be large enough not to trigger on regular data, where the debt oscillates

 * around zero: measured on the 212 MB silesia.tar, no value from 196 up

 * changes the output by a single byte, while 52 costs 2331 bytes and 192

 * costs 615. It must also leave room for one last group of literals in the

 * 8-bit counter that holds the debt, which is why it may not exceed

 * 255 - (SLZ_SWITCH_COST - 1) = 204.

 */

#define SLZ_MAX_DEBT        200

/* Compresses <ilen> bytes from <in> into <out> according to RFC1951. The

 * output result may be up to 5 bytes larger than the input for each 65535

 * nput bytes, to which 2 extra bytes may be added to send the last chunk due

 * to BFINAL+EOB encoding (10 bits) when <more> is not set. This is a property

 * of the whole stream, not of each call: since up to 31 bits are retained in

 * the queue from one call to the next, a single call may emit up to 5 bytes

 * more than its own share, which the following ones will not emit. The caller

 * is responsible for ensuring there is enough room in the output buffer for

 * this. The amount of output bytes is returned, and no CRC is computed.

 */

long slz_rfc1951_encode(struct slz_stream *strm, unsigned char *out, const unsigned char *in, long ilen, int more)

{

  long rem = ilen;

  unsigned long pos = 0;

  unsigned long last;

  uint32_t word = 0;

  long mlen;

  uint32_t h;

  uint64_t ent;

  uint32_t plit = 0;

  uint32_t bit9 = 0;

  uint32_t dist, code;

  union ref refs[1 << HASH_BITS];

  if (!strm->level) {

    /* force to send as literals (eg to preserve CPU) */

    strm->outbuf = out;

    plit = pos = ilen;

    bit9 = 52; /* force literal dump */

    goto final_lit_dump;

  }

  reset_refs(refs, sizeof(refs));

  strm->outbuf = out;

#ifndef UNALIGNED_FASTER

  if (rem >= 4)  // <word> is only used inside the loop below, hence the test for >= 4

    word = ((uint32_t)(unsigned char)in[pos] << 8) + ((uint32_t)(unsigned char)in[pos + 1] << 16) + ((uint32_t)(unsigned char)in[pos + 2] << 24);

#endif

  while (rem >= 4) {

#ifndef UNALIGNED_FASTER

    word = ((uint32_t)(unsigned char)in[pos + 3] << 24) + (word >> 8);

#else

    word = *(uint32_t *)&in[pos];

#endif

    h = slz_hash(word);

    asm volatile ("" ::); // prevent gcc from trying to be smart with the prefetch

    if (sizeof(long) >= 8) {

      ent = refs[h].by64;

      last = (uint32_t)ent;

      ent >>= 32;

      refs[h].by64 = ((uint64_t)pos) + ((uint64_t)word << 32);

    } else {

      ent  = refs[h].by32.word;

      last = refs[h].by32.pos;

      refs[h].by32.pos = pos;

      refs[h].by32.word = word;

    }

#ifdef FIND_OPTIMAL_MATCH

    /* Experimental code to see what could be saved with an ideal

     * longest match lookup algorithm. This one is very slow but

     * scans the whole window. In short, here are the savings :

     *   file        orig     fast(ratio)  optimal(ratio)

     *  README       5185    3419 (65.9%)    3165 (61.0%)  -7.5%

     *  index.html  76799   35662 (46.4%)   29875 (38.9%) -16.3%

     *  rfc1952.c   29383   13442 (45.7%)   11793 (40.1%) -12.3%

     *

     * Thus the savings to expect for large files is at best 16%.

     *

     * A non-colliding hash gives 33025 instead of 35662 (-7.4%),

     * and keeping the last two entries gives 31724 (-11.0%).

     */

    unsigned long scan;

    int saved = 0;

    int bestpos = 0;

    int bestlen = 0;

    int firstlen = 0;

    int max_lookup = 2; // 0 = no limit

    for (scan = pos - 1; scan < pos && (unsigned long)(pos - scan - 1) < 32768; scan--) {

      int len;

      if (*(uint32_t *)(in + scan) != word)

        continue;

      len = memmatch(in + pos, in + scan, rem);

      if (!bestlen)

        firstlen = len;

      if (len > bestlen) {

        bestlen = len;

        bestpos = scan;

      }

      if (!--max_lookup)

        break;

    }

    if (bestlen) {

      //printf("pos=%d last=%d bestpos=%d word=%08x ent=%08x len=%d\n",

      //       (int)pos, (int)last, (int)bestpos, (int)word, (int)ent, bestlen);

      last = bestpos;

      ent  = word;

      saved += bestlen - firstlen;

    }

    //fprintf(stderr, "first=%d best=%d saved_total=%d\n", firstlen, bestlen, saved);

#endif

    if ((uint32_t)ent != word) {

    send_as_lit:

      rem--;

      plit++;

      bit9 += ((unsigned char)word >= 144);

      pos++;

      continue;

    }

    /* We reject pos = last and pos > last+32768 */

    if ((unsigned long)(pos - last - 1) >= 32768)

      goto send_as_lit;

    /* Note: cannot encode a length larger than 258 bytes */

    mlen = memmatch(in + pos + 4, in + last + 4, (rem > 258 ? 258 : rem) - 4) + 4;

    /* found a matching entry */

    if (bit9 >= 52 && mlen < 6)

      goto send_as_lit;

    /* compute the output code, its size and the length's size in

     * bits to know if the reference is cheaper than literals.

     */

    code = len_fh[mlen];

    /* direct mapping of dist->huffman code */

    dist = fh_dist_table[pos - last - 1];

    /* If encoding the dist+length is more expensive than sending

     * the equivalent as bytes, lets keep the literals. This is

     * important for the compression ratio and also for standing by

     * our promise that the output is no longer than input + 5 bytes

     * every 65535. The explanation is that a valid stream starts in

     * EOB and ends in EOB, which is the state where we can grow by

     * up to 5 bytes (1 byte for BT, 2 for LEN, 2 for NLEN, then

     * literal data). Sending compressed Huffman data (reference or

     * fixed encoding) may only be accepted if it is guaranteed that

     * it will not represent more bytes in the worst case. Switching

     * from EOB to FIXED requires 3 bits of BT. Then either fixed

     * data (8 or 9 bits) or references (15-33 bits). Switching back

     * to EOB requires EOB (7 bits), and in order to get back to the

     * situation where bytes can be added with no overhead, the BT,

     * align, LEN and NLEN have to be sent as well:

     *

     * Before switching:

     *          [BT] [ALIGN] [LEN] [NLEN] [PLIT]

     *   bits:    3     7     16     16   8*plit

     *

     * In case of sending mlen bytes as literals:

     *          [BT] [ALIGN] [LEN] [NLEN] [PLIT] [MLEN]

     *   bits:    3     7     16     16   8*plit 8*mlen

     *

     * In case of sending mlen bytes as literals, we add:

     *       [MLEN]

     * bits: 8*mlen

     *

     * In case of sending reference, we add in the worst case:

     *       [BT] [CODE] [DIST] [EOB] [BT] [ALIGN] [LEN] [NLEN]

     * bits:  3    clen   dlen    7    3      7      16    16

     *

     * Thus for literals we add 8*mlen bits, and for reference we

     * add clen+dlen+52 bits. If the reference encoding + 52 bits

     * is shorter. Of course there are plenty of opportunities to

     * be much shorter once we switch to FIXED, and a stricter

     * tracking could allow to send references more often. But here

     * we at least guarantee that if data fit as literals, they also

     * fit using a temporary switch to FIXED.

     *

     * Regarding encoding size, clen is 7 for mlen 3..10, to 12 for

     * mlen 131..257. dlen is 8 for distances 1..4, to 21 for

     * distances 16385..32768. Thus mlen <= 130 produces clen+dlen

     * <= 32 bits. This means that for mlen 4 or above, the encoded

     * reference is always smaller than the data it references. This

     * is what guarantees that once switched to FIXED we can stay

     * in it for as long as needed.

     */

    if ((strm->state == SLZ_ST_EOB || strm->debt >= SLZ_MAX_DEBT) &&

        (dist & 0x1f) + (code >> 16) + SLZ_SWITCH_COST > 8 * mlen)

      goto send_as_lit;

    /* first, copy pending literals */

    if (plit) {

      /* Huffman encoding requires 9 bits for octets 144..255, so this

       * is a waste of space for binary data. Switching between Huffman

       * and no-comp then huffman consumes 52 bits (7 for EOB + 3 for

       * block type + 7 for alignment + 32 for LEN+NLEN + 3 for next

       * block. Only use plain literals if there are more than 52 bits

       * to save then, or if we're already too much in debt, in which

       * case only stored blocks may be emitted, see <debt> below.

       * Literals sent in a stored block do not cost anything extra,

       * only those sent in huffman mode add to the debt.

       */

      if (bit9 >= SLZ_SWITCH_COST || strm->debt >= SLZ_MAX_DEBT)

        copy_lit(strm, in + pos - plit, plit, 1);

      else {

        copy_lit_huff(strm, in + pos - plit, plit, 1);

        strm->debt += bit9;

      }

      plit = 0;

    }

    /* use mode 01 - fixed huffman */

    if (strm->state == SLZ_ST_EOB) {

      strm->state = SLZ_ST_FIXED;

      enqueue8(strm, 0x02, 3); // BTYPE = 01, BFINAL = 0

    }

    /* copy the length first */

    enqueue24(strm, code & 0xFFFF, code >> 16);

    /* in fixed huffman mode, dist is fixed 5 bits */

    enqueue24(strm, dist >> 5, dist & 0x1f);

    /* <bit9> only measures the current group of literals, which is

     * what the decisions above compare against, and it restarts

     * from zero after each reference. <debt> accumulates how much

     * the literals already emitted in fixed huffman mode are still

     * costing us compared to the same bytes sent as stored blocks,

     * and is what bounds the growth of the output: the reference

     * just used (code>>16)+(dist&0x1f) bits in place of the 8*mlen

     * bits these bytes would have taken as literals, so it repays

     * that much of the debt. Without this, a stream made of series

     * of 9-bit literals interleaved with cheap references would

     * never reach the threshold above and would keep inflating. The

     * debt is saturated at zero since we're not interested in

     * accumulating credits. The update is unconditional because a

     * test on a debt that is often null but not always turns into

     * a mispredicted branch on binary data.

     */

    code = strm->debt + (code >> 16) + (dist & 0x1f);

    strm->debt = (code > 8 * (uint32_t)mlen) ? code - 8 * (uint32_t)mlen : 0;

    bit9 = 0;

    rem -= mlen;

    pos += mlen;

#ifndef UNALIGNED_FASTER

    /* same as before the loop, this is only used when continuing

     * in the loop, so let's use the same condition (rem>=4).

     */

    if (rem >= 4) {

#ifdef UNALIGNED_LE_OK

      word = *(uint32_t *)&in[pos - 1];

#else

      word = ((uint32_t)(unsigned char)in[pos] << 8) + ((uint32_t)(unsigned char)in[pos + 1] << 16) + ((uint32_t)(unsigned char)in[pos + 2] << 24);

#endif

    }

#endif

  }

  if (__builtin_expect(rem, 0)) {

    /* we're reading the 1..3 last bytes */

    plit += rem;

    do {

      bit9 += ((unsigned char)in[pos++] >= 144);

    } while (--rem);

  }

 final_lit_dump:

  /* Now copy remaining literals or mark the end. The cost of switching to

   * a stored block depends on the current state and on the presence of

   * data after these literals, see the SLZ_*_COST definitions above.

   */

  if (plit) {

    uint32_t cost;

    if (more)

      cost = SLZ_SWITCH_COST;

    else

      cost = (strm->state == SLZ_ST_EOB) ? SLZ_LAST_COST_EOB : SLZ_LAST_COST;

    if (bit9 >= cost || strm->debt >= SLZ_MAX_DEBT)

      copy_lit(strm, in + pos - plit, plit, more);

    else

      copy_lit_huff(strm, in + pos - plit, plit, more);

    plit = 0;

  }

  strm->ilen += ilen;

  return strm->outbuf - out;

}

/* Initializes stream <strm> for use with raw deflate (rfc1951). The CRC is

 * unused but set to zero. The compression level passed in <level> is set. This

 * value can only be 0 (no compression) or 1 (compression) and other values

 * will lead to unpredictable behaviour. The function always returns 0.

 */

int slz_rfc1951_init(struct slz_stream *strm, int level)

{

  strm->state = SLZ_ST_EOB; // no header

  strm->level = level;

  strm->format = SLZ_FMT_DEFLATE;

  strm->crc32 = 0;

  strm->ilen  = 0;

  strm->qbits = 0;

  strm->queue = 0;

  strm->debt  = 0;

  return 0;

}

/* Flushes any pending data for stream <strm> into buffer <buf>, then emits an

 * empty literal block to byte-align the output, allowing to completely flush

 * the queue. This requires that the output buffer still has the size of the

 * queue (up to 31 bits when using the 64-bit queue), plus a possible EOB (7

 * bits), plus (BFINAL,BTYPE) (3 bits), which once rounded up to the next byte

 * make 6 bytes, plus 4 bytes for LEN+NLEN, or a total of 10 bytes in the worst

 * case. If the stream was already completed by a previous call to encode()

 * with <more> cleared, the last block is simply terminated and the output

 * aligned, since nothing may be appended to a finished stream. The number of

 * bytes emitted is returned. It is guaranteed that the queue is empty on

 * return. This may cause some overhead by adding needless 5-byte blocks if

 * called to often.

 */

int slz_rfc1951_flush(struct slz_stream *strm, unsigned char *buf)

{

  strm->outbuf = buf;

  /* The queue is always empty on INIT, DONE, and END */

  if (!strm->qbits)

    return 0;

  /* we may need to terminate a huffman output. Lit is always in EOB state */

  if (strm->state != SLZ_ST_EOB) {

    strm->state = (strm->state == SLZ_ST_LAST) ? SLZ_ST_DONE : SLZ_ST_EOB;

    send_eob(strm);

  }

  if (strm->state == SLZ_ST_DONE) {

    /* The block we've just terminated was already marked final, so

     * the deflate stream is complete and nothing may be appended to

     * it: an extra block here would be located past the end of the

     * stream and would shift the gzip or zlib trailer that the

     * caller is about to emit. Aligning the output is all we have

     * to do, and it's all that's left to do for finish() as well.

     */

    flush_bits(strm);

    return strm->outbuf - buf;

  }

  /* send BFINAL=0 and BTYPE=00 (lit) */

  enqueue8(strm, 0, 3);

  flush_bits(strm);             // emit pending bits

  copy_32b(strm, 0xFFFF0000U);  // len=0, nlen=~0

  /* Now the queue is empty, EOB was sent, and a zero-byte block was sent

   * to byte-align the output. The last state reflects all this. Let's

   * just return the number of bytes added to the output buffer.

   */

  return strm->outbuf - buf;

}

/* Flushes any pending for stream <strm> into buffer <buf>, then sends BTYPE=1

 * and BFINAL=1 if needed. The stream ends in SLZ_ST_DONE. It returns the number

 * of bytes emitted. The trailer consists in flushing the possibly pending bits

 * from the queue (up to 31 bits when using the 64-bit queue), then possibly

 * EOB (7 bits), then 3 bits, EOB, a rounding to the next byte, which amounts

 * to a total of 6 bytes max, that the caller must ensure are available before

 * calling the function.

 */

int slz_rfc1951_finish(struct slz_stream *strm, unsigned char *buf)

{

  strm->outbuf = buf;

  if (strm->state == SLZ_ST_FIXED || strm->state == SLZ_ST_LAST) {

    strm->state = (strm->state == SLZ_ST_LAST) ? SLZ_ST_DONE : SLZ_ST_EOB;

    send_eob(strm);

  }

  if (strm->state != SLZ_ST_DONE) {

    /* send BTYPE=1, BFINAL=1 */

    enqueue8(strm, 3, 3);

    send_eob(strm);

    strm->state = SLZ_ST_DONE;

  }

  flush_bits(strm);

  return strm->outbuf - buf;

}

/* Now RFC1952-specific declarations and extracts from RFC.

 * From RFC1952 about the GZIP file format :

A gzip file consists of a series of "members" ...

2.3. Member format

      Each member has the following structure:

         +---+---+---+---+---+---+---+---+---+---+

         |ID1|ID2|CM |FLG|     MTIME     |XFL|OS | (more-->)

         +---+---+---+---+---+---+---+---+---+---+

      (if FLG.FEXTRA set)

         +---+---+=================================+

         | XLEN  |...XLEN bytes of "extra field"...| (more-->)

         +---+---+=================================+

      (if FLG.FNAME set)

         +=========================================+

         |...original file name, zero-terminated...| (more-->)

         +=========================================+

      (if FLG.FCOMMENT set)

         +===================================+

         |...file comment, zero-terminated...| (more-->)

         +===================================+

      (if FLG.FHCRC set)

         +---+---+

         | CRC16 |

         +---+---+

         +=======================+

         |...compressed blocks...| (more-->)

         +=======================+

           0   1   2   3   4   5   6   7

         +---+---+---+---+---+---+---+---+

         |     CRC32     |     ISIZE     |

         +---+---+---+---+---+---+---+---+

2.3.1. Member header and trailer

         ID1 (IDentification 1)

         ID2 (IDentification 2)

            These have the fixed values ID1 = 31 (0x1f, \037), ID2 = 139

            (0x8b, \213), to identify the file as being in gzip format.

         CM (Compression Method)

            This identifies the compression method used in the file.  CM

            = 0-7 are reserved.  CM = 8 denotes the "deflate"

            compression method, which is the one customarily used by

            gzip and which is documented elsewhere.

         FLG (FLaGs)

            This flag byte is divided into individual bits as follows:

               bit 0   FTEXT

               bit 1   FHCRC

               bit 2   FEXTRA

               bit 3   FNAME

               bit 4   FCOMMENT

               bit 5   reserved

               bit 6   reserved

               bit 7   reserved

            Reserved FLG bits must be zero.

         MTIME (Modification TIME)

            This gives the most recent modification time of the original

            file being compressed.  The time is in Unix format, i.e.,

            seconds since 00:00:00 GMT, Jan.  1, 1970.  (Note that this

            may cause problems for MS-DOS and other systems that use

            local rather than Universal time.)  If the compressed data

            did not come from a file, MTIME is set to the time at which

            compression started.  MTIME = 0 means no time stamp is

            available.

         XFL (eXtra FLags)

            These flags are available for use by specific compression

            methods.  The "deflate" method (CM = 8) sets these flags as

            follows:

               XFL = 2 - compressor used maximum compression,

                         slowest algorithm

               XFL = 4 - compressor used fastest algorithm

         OS (Operating System)

            This identifies the type of file system on which compression

            took place.  This may be useful in determining end-of-line

            convention for text files.  The currently defined values are

            as follows:

                 0 - FAT filesystem (MS-DOS, OS/2, NT/Win32)

                 1 - Amiga

                 2 - VMS (or OpenVMS)

                 3 - Unix

                 4 - VM/CMS

                 5 - Atari TOS

                 6 - HPFS filesystem (OS/2, NT)

                 7 - Macintosh

                 8 - Z-System

                 9 - CP/M

                10 - TOPS-20

                11 - NTFS filesystem (NT)

                12 - QDOS

                13 - Acorn RISCOS

               255 - unknown

 ==> A file compressed using "gzip -1" on Unix-like systems can be :

        1F 8B 08 00  00 00 00 00  04 03

        <deflate-compressed stream>

        crc32 size32

*/

static const unsigned char gzip_hdr[] = { 0x1F, 0x8B,   // ID1, ID2

                                          0x08, 0x00,   // Deflate, flags (none)

                                          0x00, 0x00, 0x00, 0x00, // mtime: none

                                          0x04, 0x03 }; // fastest comp, OS=Unix

/* Sends the gzip header for stream <strm> into buffer <buf>. When it's done,

 * the stream state is updated to SLZ_ST_EOB. It returns the number of bytes

 * emitted which is always 10. The caller is responsible for ensuring there's

 * always enough room in the buffer.

 */

int slz_rfc1952_send_header(struct slz_stream *strm, unsigned char *buf)

{

  memcpy(buf, gzip_hdr, sizeof(gzip_hdr));

  strm->state = SLZ_ST_EOB;

  return sizeof(gzip_hdr);

}

/* Encodes the block according to rfc1952. This means that the CRC of the input

 * block is computed according to the CRC32 algorithm. If the header was never

 * sent, it may be sent first. The number of output bytes is returned.

 */

long slz_rfc1952_encode(struct slz_stream *strm, unsigned char *out, const unsigned char *in, long ilen, int more)

{

  long ret = 0;

  if (__builtin_expect(strm->state == SLZ_ST_INIT, 0))

    ret += slz_rfc1952_send_header(strm, out);

  strm->crc32 = update_crc(strm->crc32, in, ilen);

  ret += slz_rfc1951_encode(strm, out + ret, in, ilen, more);

  return ret;

}

/* Initializes stream <strm> for use with the gzip format (rfc1952). The

 * compression level passed in <level> is set. This value can only be 0 (no

 * compression) or 1 (compression) and other values will lead to unpredictable

 * behaviour. The function always returns 0.

 */

int slz_rfc1952_init(struct slz_stream *strm, int level)

{

  strm->state  = SLZ_ST_INIT;

  strm->level  = level;

  strm->format = SLZ_FMT_GZIP;

  strm->crc32  = 0;

  strm->ilen   = 0;

  strm->qbits  = 0;

  strm->queue  = 0;

  strm->debt   = 0;

  return 0;

}

/* Flushes any pending data for stream <strm> into buffer <buf>, then emits an

 * empty literal block to byte-align the output, allowing to completely flush

 * the queue. Note that if the initial header was never sent, it will be sent

 * first as well (10 extra bytes). This requires that the output buffer still

 * has this plus the 6 bytes needed to flush the queue, the possible EOB and

 * the (BFINAL,BTYPE) bits, plus 4 bytes for LEN+NLEN, or a total of 20 bytes

 * in the worst case. The number of bytes emitted is returned. It is guaranteed

 * that the queue is empty on return. This may cause some overhead by adding

 * needless 5-byte blocks if called to often.

 */

int slz_rfc1952_flush(struct slz_stream *strm, unsigned char *buf)

{

  int sent = 0;

  if (__builtin_expect(strm->state == SLZ_ST_INIT, 0))

    sent = slz_rfc1952_send_header(strm, buf);

  sent += slz_rfc1951_flush(strm, buf + sent);