LCOV - code coverage report
Current view: top level - src/common - pg_lzcompress.c (source / functions) Hit Total Coverage
Test: PostgreSQL 13devel Lines: 116 127 91.3 %
Date: 2019-09-22 08:06:49 Functions: 3 3 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /* ----------
       2             :  * pg_lzcompress.c -
       3             :  *
       4             :  *      This is an implementation of LZ compression for PostgreSQL.
       5             :  *      It uses a simple history table and generates 2-3 byte tags
       6             :  *      capable of backward copy information for 3-273 bytes with
       7             :  *      a max offset of 4095.
       8             :  *
       9             :  *      Entry routines:
      10             :  *
      11             :  *          int32
      12             :  *          pglz_compress(const char *source, int32 slen, char *dest,
      13             :  *                        const PGLZ_Strategy *strategy);
      14             :  *
      15             :  *              source is the input data to be compressed.
      16             :  *
      17             :  *              slen is the length of the input data.
      18             :  *
      19             :  *              dest is the output area for the compressed result.
      20             :  *                  It must be at least as big as PGLZ_MAX_OUTPUT(slen).
      21             :  *
      22             :  *              strategy is a pointer to some information controlling
      23             :  *                  the compression algorithm. If NULL, the compiled
      24             :  *                  in default strategy is used.
      25             :  *
      26             :  *              The return value is the number of bytes written in the
      27             :  *              buffer dest, or -1 if compression fails; in the latter
      28             :  *              case the contents of dest are undefined.
      29             :  *
      30             :  *          int32
      31             :  *          pglz_decompress(const char *source, int32 slen, char *dest,
      32             :  *                          int32 rawsize, bool check_complete)
      33             :  *
      34             :  *              source is the compressed input.
      35             :  *
      36             :  *              slen is the length of the compressed input.
      37             :  *
      38             :  *              dest is the area where the uncompressed data will be
      39             :  *                  written to. It is the callers responsibility to
      40             :  *                  provide enough space.
      41             :  *
      42             :  *                  The data is written to buff exactly as it was handed
      43             :  *                  to pglz_compress(). No terminating zero byte is added.
      44             :  *
      45             :  *              rawsize is the length of the uncompressed data.
      46             :  *
      47             :  *              check_complete is a flag to let us know if -1 should be
      48             :  *                  returned in cases where we don't reach the end of the
      49             :  *                  source or dest buffers, or not.  This should be false
      50             :  *                  if the caller is asking for only a partial result and
      51             :  *                  true otherwise.
      52             :  *
      53             :  *              The return value is the number of bytes written in the
      54             :  *              buffer dest, or -1 if decompression fails.
      55             :  *
      56             :  *      The decompression algorithm and internal data format:
      57             :  *
      58             :  *          It is made with the compressed data itself.
      59             :  *
      60             :  *          The data representation is easiest explained by describing
      61             :  *          the process of decompression.
      62             :  *
      63             :  *          If compressed_size == rawsize, then the data
      64             :  *          is stored uncompressed as plain bytes. Thus, the decompressor
      65             :  *          simply copies rawsize bytes to the destination.
      66             :  *
      67             :  *          Otherwise the first byte tells what to do the next 8 times.
      68             :  *          We call this the control byte.
      69             :  *
      70             :  *          An unset bit in the control byte means, that one uncompressed
      71             :  *          byte follows, which is copied from input to output.
      72             :  *
      73             :  *          A set bit in the control byte means, that a tag of 2-3 bytes
      74             :  *          follows. A tag contains information to copy some bytes, that
      75             :  *          are already in the output buffer, to the current location in
      76             :  *          the output. Let's call the three tag bytes T1, T2 and T3. The
      77             :  *          position of the data to copy is coded as an offset from the
      78             :  *          actual output position.
      79             :  *
      80             :  *          The offset is in the upper nibble of T1 and in T2.
      81             :  *          The length is in the lower nibble of T1.
      82             :  *
      83             :  *          So the 16 bits of a 2 byte tag are coded as
      84             :  *
      85             :  *              7---T1--0  7---T2--0
      86             :  *              OOOO LLLL  OOOO OOOO
      87             :  *
      88             :  *          This limits the offset to 1-4095 (12 bits) and the length
      89             :  *          to 3-18 (4 bits) because 3 is always added to it. To emit
      90             :  *          a tag of 2 bytes with a length of 2 only saves one control
      91             :  *          bit. But we lose one byte in the possible length of a tag.
      92             :  *
      93             :  *          In the actual implementation, the 2 byte tag's length is
      94             :  *          limited to 3-17, because the value 0xF in the length nibble
      95             :  *          has special meaning. It means, that the next following
      96             :  *          byte (T3) has to be added to the length value of 18. That
      97             :  *          makes total limits of 1-4095 for offset and 3-273 for length.
      98             :  *
      99             :  *          Now that we have successfully decoded a tag. We simply copy
     100             :  *          the output that occurred <offset> bytes back to the current
     101             :  *          output location in the specified <length>. Thus, a
     102             :  *          sequence of 200 spaces (think about bpchar fields) could be
     103             :  *          coded in 4 bytes. One literal space and a three byte tag to
     104             :  *          copy 199 bytes with a -1 offset. Whow - that's a compression
     105             :  *          rate of 98%! Well, the implementation needs to save the
     106             :  *          original data size too, so we need another 4 bytes for it
     107             :  *          and end up with a total compression rate of 96%, what's still
     108             :  *          worth a Whow.
     109             :  *
     110             :  *      The compression algorithm
     111             :  *
     112             :  *          The following uses numbers used in the default strategy.
     113             :  *
     114             :  *          The compressor works best for attributes of a size between
     115             :  *          1K and 1M. For smaller items there's not that much chance of
     116             :  *          redundancy in the character sequence (except for large areas
     117             :  *          of identical bytes like trailing spaces) and for bigger ones
     118             :  *          our 4K maximum look-back distance is too small.
     119             :  *
     120             :  *          The compressor creates a table for lists of positions.
     121             :  *          For each input position (except the last 3), a hash key is
     122             :  *          built from the 4 next input bytes and the position remembered
     123             :  *          in the appropriate list. Thus, the table points to linked
     124             :  *          lists of likely to be at least in the first 4 characters
     125             :  *          matching strings. This is done on the fly while the input
     126             :  *          is compressed into the output area.  Table entries are only
     127             :  *          kept for the last 4096 input positions, since we cannot use
     128             :  *          back-pointers larger than that anyway.  The size of the hash
     129             :  *          table is chosen based on the size of the input - a larger table
     130             :  *          has a larger startup cost, as it needs to be initialized to
     131             :  *          zero, but reduces the number of hash collisions on long inputs.
     132             :  *
     133             :  *          For each byte in the input, its hash key (built from this
     134             :  *          byte and the next 3) is used to find the appropriate list
     135             :  *          in the table. The lists remember the positions of all bytes
     136             :  *          that had the same hash key in the past in increasing backward
     137             :  *          offset order. Now for all entries in the used lists, the
     138             :  *          match length is computed by comparing the characters from the
     139             :  *          entries position with the characters from the actual input
     140             :  *          position.
     141             :  *
     142             :  *          The compressor starts with a so called "good_match" of 128.
     143             :  *          It is a "prefer speed against compression ratio" optimizer.
     144             :  *          So if the first entry looked at already has 128 or more
     145             :  *          matching characters, the lookup stops and that position is
     146             :  *          used for the next tag in the output.
     147             :  *
     148             :  *          For each subsequent entry in the history list, the "good_match"
     149             :  *          is lowered by 10%. So the compressor will be more happy with
     150             :  *          short matches the farer it has to go back in the history.
     151             :  *          Another "speed against ratio" preference characteristic of
     152             :  *          the algorithm.
     153             :  *
     154             :  *          Thus there are 3 stop conditions for the lookup of matches:
     155             :  *
     156             :  *              - a match >= good_match is found
     157             :  *              - there are no more history entries to look at
     158             :  *              - the next history entry is already too far back
     159             :  *                to be coded into a tag.
     160             :  *
     161             :  *          Finally the match algorithm checks that at least a match
     162             :  *          of 3 or more bytes has been found, because that is the smallest
     163             :  *          amount of copy information to code into a tag. If so, a tag
     164             :  *          is omitted and all the input bytes covered by that are just
     165             :  *          scanned for the history add's, otherwise a literal character
     166             :  *          is omitted and only his history entry added.
     167             :  *
     168             :  *      Acknowledgments:
     169             :  *
     170             :  *          Many thanks to Adisak Pochanayon, who's article about SLZ
     171             :  *          inspired me to write the PostgreSQL compression this way.
     172             :  *
     173             :  *          Jan Wieck
     174             :  *
     175             :  * Copyright (c) 1999-2019, PostgreSQL Global Development Group
     176             :  *
     177             :  * src/common/pg_lzcompress.c
     178             :  * ----------
     179             :  */
     180             : #ifndef FRONTEND
     181             : #include "postgres.h"
     182             : #else
     183             : #include "postgres_fe.h"
     184             : #endif
     185             : 
     186             : #include <limits.h>
     187             : 
     188             : #include "common/pg_lzcompress.h"
     189             : 
     190             : 
     191             : /* ----------
     192             :  * Local definitions
     193             :  * ----------
     194             :  */
     195             : #define PGLZ_MAX_HISTORY_LISTS  8192    /* must be power of 2 */
     196             : #define PGLZ_HISTORY_SIZE       4096
     197             : #define PGLZ_MAX_MATCH          273
     198             : 
     199             : 
     200             : /* ----------
     201             :  * PGLZ_HistEntry -
     202             :  *
     203             :  *      Linked list for the backward history lookup
     204             :  *
     205             :  * All the entries sharing a hash key are linked in a doubly linked list.
     206             :  * This makes it easy to remove an entry when it's time to recycle it
     207             :  * (because it's more than 4K positions old).
     208             :  * ----------
     209             :  */
     210             : typedef struct PGLZ_HistEntry
     211             : {
     212             :     struct PGLZ_HistEntry *next;    /* links for my hash key's list */
     213             :     struct PGLZ_HistEntry *prev;
     214             :     int         hindex;         /* my current hash key */
     215             :     const char *pos;            /* my input position */
     216             : } PGLZ_HistEntry;
     217             : 
     218             : 
     219             : /* ----------
     220             :  * The provided standard strategies
     221             :  * ----------
     222             :  */
     223             : static const PGLZ_Strategy strategy_default_data = {
     224             :     32,                         /* Data chunks less than 32 bytes are not
     225             :                                  * compressed */
     226             :     INT_MAX,                    /* No upper limit on what we'll try to
     227             :                                  * compress */
     228             :     25,                         /* Require 25% compression rate, or not worth
     229             :                                  * it */
     230             :     1024,                       /* Give up if no compression in the first 1KB */
     231             :     128,                        /* Stop history lookup if a match of 128 bytes
     232             :                                  * is found */
     233             :     10                          /* Lower good match size by 10% at every loop
     234             :                                  * iteration */
     235             : };
     236             : const PGLZ_Strategy *const PGLZ_strategy_default = &strategy_default_data;
     237             : 
     238             : 
     239             : static const PGLZ_Strategy strategy_always_data = {
     240             :     0,                          /* Chunks of any size are compressed */
     241             :     INT_MAX,
     242             :     0,                          /* It's enough to save one single byte */
     243             :     INT_MAX,                    /* Never give up early */
     244             :     128,                        /* Stop history lookup if a match of 128 bytes
     245             :                                  * is found */
     246             :     6                           /* Look harder for a good match */
     247             : };
     248             : const PGLZ_Strategy *const PGLZ_strategy_always = &strategy_always_data;
     249             : 
     250             : 
     251             : /* ----------
     252             :  * Statically allocated work arrays for history
     253             :  * ----------
     254             :  */
     255             : static int16 hist_start[PGLZ_MAX_HISTORY_LISTS];
     256             : static PGLZ_HistEntry hist_entries[PGLZ_HISTORY_SIZE + 1];
     257             : 
     258             : /*
     259             :  * Element 0 in hist_entries is unused, and means 'invalid'. Likewise,
     260             :  * INVALID_ENTRY_PTR in next/prev pointers mean 'invalid'.
     261             :  */
     262             : #define INVALID_ENTRY           0
     263             : #define INVALID_ENTRY_PTR       (&hist_entries[INVALID_ENTRY])
     264             : 
     265             : /* ----------
     266             :  * pglz_hist_idx -
     267             :  *
     268             :  *      Computes the history table slot for the lookup by the next 4
     269             :  *      characters in the input.
     270             :  *
     271             :  * NB: because we use the next 4 characters, we are not guaranteed to
     272             :  * find 3-character matches; they very possibly will be in the wrong
     273             :  * hash list.  This seems an acceptable tradeoff for spreading out the
     274             :  * hash keys more.
     275             :  * ----------
     276             :  */
     277             : #define pglz_hist_idx(_s,_e, _mask) (                                       \
     278             :             ((((_e) - (_s)) < 4) ? (int) (_s)[0] :                           \
     279             :              (((_s)[0] << 6) ^ ((_s)[1] << 4) ^                             \
     280             :               ((_s)[2] << 2) ^ (_s)[3])) & (_mask)                \
     281             :         )
     282             : 
     283             : 
     284             : /* ----------
     285             :  * pglz_hist_add -
     286             :  *
     287             :  *      Adds a new entry to the history table.
     288             :  *
     289             :  * If _recycle is true, then we are recycling a previously used entry,
     290             :  * and must first delink it from its old hashcode's linked list.
     291             :  *
     292             :  * NOTE: beware of multiple evaluations of macro's arguments, and note that
     293             :  * _hn and _recycle are modified in the macro.
     294             :  * ----------
     295             :  */
     296             : #define pglz_hist_add(_hs,_he,_hn,_recycle,_s,_e, _mask)    \
     297             : do {                                    \
     298             :             int __hindex = pglz_hist_idx((_s),(_e), (_mask));               \
     299             :             int16 *__myhsp = &(_hs)[__hindex];                              \
     300             :             PGLZ_HistEntry *__myhe = &(_he)[_hn];                           \
     301             :             if (_recycle) {                                                 \
     302             :                 if (__myhe->prev == NULL)                                    \
     303             :                     (_hs)[__myhe->hindex] = __myhe->next - (_he);         \
     304             :                 else                                                        \
     305             :                     __myhe->prev->next = __myhe->next;                     \
     306             :                 if (__myhe->next != NULL)                                    \
     307             :                     __myhe->next->prev = __myhe->prev;                     \
     308             :             }                                                               \
     309             :             __myhe->next = &(_he)[*__myhsp];                             \
     310             :             __myhe->prev = NULL;                                         \
     311             :             __myhe->hindex = __hindex;                                       \
     312             :             __myhe->pos  = (_s);                                         \
     313             :             /* If there was an existing entry in this hash slot, link */    \
     314             :             /* this new entry to it. However, the 0th entry in the */       \
     315             :             /* entries table is unused, so we can freely scribble on it. */ \
     316             :             /* So don't bother checking if the slot was used - we'll */     \
     317             :             /* scribble on the unused entry if it was not, but that's */    \
     318             :             /* harmless. Avoiding the branch in this critical path */       \
     319             :             /* speeds this up a little bit. */                              \
     320             :             /* if (*__myhsp != INVALID_ENTRY) */                            \
     321             :                 (_he)[(*__myhsp)].prev = __myhe;                            \
     322             :             *__myhsp = _hn;                                                 \
     323             :             if (++(_hn) >= PGLZ_HISTORY_SIZE + 1) {                          \
     324             :                 (_hn) = 1;                                                  \
     325             :                 (_recycle) = true;                                          \
     326             :             }                                                               \
     327             : } while (0)
     328             : 
     329             : 
     330             : /* ----------
     331             :  * pglz_out_ctrl -
     332             :  *
     333             :  *      Outputs the last and allocates a new control byte if needed.
     334             :  * ----------
     335             :  */
     336             : #define pglz_out_ctrl(__ctrlp,__ctrlb,__ctrl,__buf) \
     337             : do { \
     338             :     if ((__ctrl & 0xff) == 0)                                               \
     339             :     {                                                                       \
     340             :         *(__ctrlp) = __ctrlb;                                               \
     341             :         __ctrlp = (__buf)++;                                                \
     342             :         __ctrlb = 0;                                                        \
     343             :         __ctrl = 1;                                                         \
     344             :     }                                                                       \
     345             : } while (0)
     346             : 
     347             : 
     348             : /* ----------
     349             :  * pglz_out_literal -
     350             :  *
     351             :  *      Outputs a literal byte to the destination buffer including the
     352             :  *      appropriate control bit.
     353             :  * ----------
     354             :  */
     355             : #define pglz_out_literal(_ctrlp,_ctrlb,_ctrl,_buf,_byte) \
     356             : do { \
     357             :     pglz_out_ctrl(_ctrlp,_ctrlb,_ctrl,_buf);                                \
     358             :     *(_buf)++ = (unsigned char)(_byte);                                     \
     359             :     _ctrl <<= 1;                                                          \
     360             : } while (0)
     361             : 
     362             : 
     363             : /* ----------
     364             :  * pglz_out_tag -
     365             :  *
     366             :  *      Outputs a backward reference tag of 2-4 bytes (depending on
     367             :  *      offset and length) to the destination buffer including the
     368             :  *      appropriate control bit.
     369             :  * ----------
     370             :  */
     371             : #define pglz_out_tag(_ctrlp,_ctrlb,_ctrl,_buf,_len,_off) \
     372             : do { \
     373             :     pglz_out_ctrl(_ctrlp,_ctrlb,_ctrl,_buf);                                \
     374             :     _ctrlb |= _ctrl;                                                        \
     375             :     _ctrl <<= 1;                                                          \
     376             :     if (_len > 17)                                                           \
     377             :     {                                                                       \
     378             :         (_buf)[0] = (unsigned char)((((_off) & 0xf00) >> 4) | 0x0f);      \
     379             :         (_buf)[1] = (unsigned char)(((_off) & 0xff));                       \
     380             :         (_buf)[2] = (unsigned char)((_len) - 18);                           \
     381             :         (_buf) += 3;                                                        \
     382             :     } else {                                                                \
     383             :         (_buf)[0] = (unsigned char)((((_off) & 0xf00) >> 4) | ((_len) - 3)); \
     384             :         (_buf)[1] = (unsigned char)((_off) & 0xff);                         \
     385             :         (_buf) += 2;                                                        \
     386             :     }                                                                       \
     387             : } while (0)
     388             : 
     389             : 
     390             : /* ----------
     391             :  * pglz_find_match -
     392             :  *
     393             :  *      Lookup the history table if the actual input stream matches
     394             :  *      another sequence of characters, starting somewhere earlier
     395             :  *      in the input buffer.
     396             :  * ----------
     397             :  */
     398             : static inline int
     399   115282592 : pglz_find_match(int16 *hstart, const char *input, const char *end,
     400             :                 int *lenp, int *offp, int good_match, int good_drop, int mask)
     401             : {
     402             :     PGLZ_HistEntry *hent;
     403             :     int16       hentno;
     404   115282592 :     int32       len = 0;
     405   115282592 :     int32       off = 0;
     406             : 
     407             :     /*
     408             :      * Traverse the linked history list until a good enough match is found.
     409             :      */
     410   115282592 :     hentno = hstart[pglz_hist_idx(input, end, mask)];
     411   115282592 :     hent = &hist_entries[hentno];
     412   611191028 :     while (hent != INVALID_ENTRY_PTR)
     413             :     {
     414   386044510 :         const char *ip = input;
     415   386044510 :         const char *hp = hent->pos;
     416             :         int32       thisoff;
     417             :         int32       thislen;
     418             : 
     419             :         /*
     420             :          * Stop if the offset does not fit into our tag anymore.
     421             :          */
     422   386044510 :         thisoff = ip - hp;
     423   386044510 :         if (thisoff >= 0x0fff)
     424       94004 :             break;
     425             : 
     426             :         /*
     427             :          * Determine length of match. A better match must be larger than the
     428             :          * best so far. And if we already have a match of 16 or more bytes,
     429             :          * it's worth the call overhead to use memcmp() to check if this match
     430             :          * is equal for the same size. After that we must fallback to
     431             :          * character by character comparison to know the exact position where
     432             :          * the diff occurred.
     433             :          */
     434   385950506 :         thislen = 0;
     435   385950506 :         if (len >= 16)
     436             :         {
     437    38937810 :             if (memcmp(ip, hp, len) == 0)
     438             :             {
     439    12367586 :                 thislen = len;
     440    12367586 :                 ip += len;
     441    12367586 :                 hp += len;
     442    46369308 :                 while (ip < end && *ip == *hp && thislen < PGLZ_MAX_MATCH)
     443             :                 {
     444    21634136 :                     thislen++;
     445    21634136 :                     ip++;
     446    21634136 :                     hp++;
     447             :                 }
     448             :             }
     449             :         }
     450             :         else
     451             :         {
     452  2801377770 :             while (ip < end && *ip == *hp && thislen < PGLZ_MAX_MATCH)
     453             :             {
     454  2107352378 :                 thislen++;
     455  2107352378 :                 ip++;
     456  2107352378 :                 hp++;
     457             :             }
     458             :         }
     459             : 
     460             :         /*
     461             :          * Remember this match as the best (if it is)
     462             :          */
     463   385950506 :         if (thislen > len)
     464             :         {
     465    52441552 :             len = thislen;
     466    52441552 :             off = thisoff;
     467             :         }
     468             : 
     469             :         /*
     470             :          * Advance to the next history entry
     471             :          */
     472   385950506 :         hent = hent->next;
     473             : 
     474             :         /*
     475             :          * Be happy with lesser good matches the more entries we visited. But
     476             :          * no point in doing calculation if we're at end of list.
     477             :          */
     478   385950506 :         if (hent != INVALID_ENTRY_PTR)
     479             :         {
     480   339657648 :             if (len >= good_match)
     481     5324662 :                 break;
     482   334332986 :             good_match -= (good_match * good_drop) / 100;
     483             :         }
     484             :     }
     485             : 
     486             :     /*
     487             :      * Return match information only if it results at least in one byte
     488             :      * reduction.
     489             :      */
     490   115282592 :     if (len > 2)
     491             :     {
     492    35867782 :         *lenp = len;
     493    35867782 :         *offp = off;
     494    35867782 :         return 1;
     495             :     }
     496             : 
     497    79414810 :     return 0;
     498             : }
     499             : 
     500             : 
     501             : /* ----------
     502             :  * pglz_compress -
     503             :  *
     504             :  *      Compresses source into dest using strategy. Returns the number of
     505             :  *      bytes written in buffer dest, or -1 if compression fails.
     506             :  * ----------
     507             :  */
     508             : int32
     509       60594 : pglz_compress(const char *source, int32 slen, char *dest,
     510             :               const PGLZ_Strategy *strategy)
     511             : {
     512       60594 :     unsigned char *bp = (unsigned char *) dest;
     513       60594 :     unsigned char *bstart = bp;
     514       60594 :     int         hist_next = 1;
     515       60594 :     bool        hist_recycle = false;
     516       60594 :     const char *dp = source;
     517       60594 :     const char *dend = source + slen;
     518       60594 :     unsigned char ctrl_dummy = 0;
     519       60594 :     unsigned char *ctrlp = &ctrl_dummy;
     520       60594 :     unsigned char ctrlb = 0;
     521       60594 :     unsigned char ctrl = 0;
     522       60594 :     bool        found_match = false;
     523             :     int32       match_len;
     524             :     int32       match_off;
     525             :     int32       good_match;
     526             :     int32       good_drop;
     527             :     int32       result_size;
     528             :     int32       result_max;
     529             :     int32       need_rate;
     530             :     int         hashsz;
     531             :     int         mask;
     532             : 
     533             :     /*
     534             :      * Our fallback strategy is the default.
     535             :      */
     536       60594 :     if (strategy == NULL)
     537           0 :         strategy = PGLZ_strategy_default;
     538             : 
     539             :     /*
     540             :      * If the strategy forbids compression (at all or if source chunk size out
     541             :      * of range), fail.
     542             :      */
     543      121188 :     if (strategy->match_size_good <= 0 ||
     544      121188 :         slen < strategy->min_input_size ||
     545       60594 :         slen > strategy->max_input_size)
     546           0 :         return -1;
     547             : 
     548             :     /*
     549             :      * Limit the match parameters to the supported range.
     550             :      */
     551       60594 :     good_match = strategy->match_size_good;
     552       60594 :     if (good_match > PGLZ_MAX_MATCH)
     553           0 :         good_match = PGLZ_MAX_MATCH;
     554       60594 :     else if (good_match < 17)
     555           0 :         good_match = 17;
     556             : 
     557       60594 :     good_drop = strategy->match_size_drop;
     558       60594 :     if (good_drop < 0)
     559           0 :         good_drop = 0;
     560       60594 :     else if (good_drop > 100)
     561           0 :         good_drop = 100;
     562             : 
     563       60594 :     need_rate = strategy->min_comp_rate;
     564       60594 :     if (need_rate < 0)
     565           0 :         need_rate = 0;
     566       60594 :     else if (need_rate > 99)
     567           0 :         need_rate = 99;
     568             : 
     569             :     /*
     570             :      * Compute the maximum result size allowed by the strategy, namely the
     571             :      * input size minus the minimum wanted compression rate.  This had better
     572             :      * be <= slen, else we might overrun the provided output buffer.
     573             :      */
     574       60594 :     if (slen > (INT_MAX / 100))
     575             :     {
     576             :         /* Approximate to avoid overflow */
     577           0 :         result_max = (slen / 100) * (100 - need_rate);
     578             :     }
     579             :     else
     580       60594 :         result_max = (slen * (100 - need_rate)) / 100;
     581             : 
     582             :     /*
     583             :      * Experiments suggest that these hash sizes work pretty well. A large
     584             :      * hash table minimizes collision, but has a higher startup cost. For a
     585             :      * small input, the startup cost dominates. The table size must be a power
     586             :      * of two.
     587             :      */
     588       60594 :     if (slen < 128)
     589          52 :         hashsz = 512;
     590       60542 :     else if (slen < 256)
     591          22 :         hashsz = 1024;
     592       60520 :     else if (slen < 512)
     593        1632 :         hashsz = 2048;
     594       58888 :     else if (slen < 1024)
     595        1304 :         hashsz = 4096;
     596             :     else
     597       57584 :         hashsz = 8192;
     598       60594 :     mask = hashsz - 1;
     599             : 
     600             :     /*
     601             :      * Initialize the history lists to empty.  We do not need to zero the
     602             :      * hist_entries[] array; its entries are initialized as they are used.
     603             :      */
     604       60594 :     memset(hist_start, 0, hashsz * sizeof(int16));
     605             : 
     606             :     /*
     607             :      * Compress the source directly into the output buffer.
     608             :      */
     609   115403780 :     while (dp < dend)
     610             :     {
     611             :         /*
     612             :          * If we already exceeded the maximum result size, fail.
     613             :          *
     614             :          * We check once per loop; since the loop body could emit as many as 4
     615             :          * bytes (a control byte and 3-byte tag), PGLZ_MAX_OUTPUT() had better
     616             :          * allow 4 slop bytes.
     617             :          */
     618   115283718 :         if (bp - bstart >= result_max)
     619        1126 :             return -1;
     620             : 
     621             :         /*
     622             :          * If we've emitted more than first_success_by bytes without finding
     623             :          * anything compressible at all, fail.  This lets us fall out
     624             :          * reasonably quickly when looking at incompressible input (such as
     625             :          * pre-compressed data).
     626             :          */
     627   115282592 :         if (!found_match && bp - bstart >= strategy->first_success_by)
     628           0 :             return -1;
     629             : 
     630             :         /*
     631             :          * Try to find a match in the history
     632             :          */
     633   115282592 :         if (pglz_find_match(hist_start, dp, dend, &match_len,
     634             :                             &match_off, good_match, good_drop, mask))
     635             :         {
     636             :             /*
     637             :              * Create the tag and add history entries for all matched
     638             :              * characters.
     639             :              */
     640    35867782 :             pglz_out_tag(ctrlp, ctrlb, ctrl, bp, match_len, match_off);
     641   894946762 :             while (match_len--)
     642             :             {
     643   823211198 :                 pglz_hist_add(hist_start, hist_entries,
     644             :                               hist_next, hist_recycle,
     645             :                               dp, dend, mask);
     646   823211198 :                 dp++;           /* Do not do this ++ in the line above! */
     647             :                 /* The macro would do it four times - Jan.  */
     648             :             }
     649    35867782 :             found_match = true;
     650             :         }
     651             :         else
     652             :         {
     653             :             /*
     654             :              * No match found. Copy one literal byte.
     655             :              */
     656    79414810 :             pglz_out_literal(ctrlp, ctrlb, ctrl, bp, *dp);
     657    79414810 :             pglz_hist_add(hist_start, hist_entries,
     658             :                           hist_next, hist_recycle,
     659             :                           dp, dend, mask);
     660    79414810 :             dp++;               /* Do not do this ++ in the line above! */
     661             :             /* The macro would do it four times - Jan.  */
     662             :         }
     663             :     }
     664             : 
     665             :     /*
     666             :      * Write out the last control byte and check that we haven't overrun the
     667             :      * output size allowed by the strategy.
     668             :      */
     669       59468 :     *ctrlp = ctrlb;
     670       59468 :     result_size = bp - bstart;
     671       59468 :     if (result_size >= result_max)
     672           2 :         return -1;
     673             : 
     674             :     /* success */
     675       59466 :     return result_size;
     676             : }
     677             : 
     678             : 
     679             : /* ----------
     680             :  * pglz_decompress -
     681             :  *
     682             :  *      Decompresses source into dest. Returns the number of bytes
     683             :  *      decompressed in the destination buffer, and *optionally*
     684             :  *      checks that both the source and dest buffers have been
     685             :  *      fully read and written to, respectively.
     686             :  * ----------
     687             :  */
     688             : int32
     689       86176 : pglz_decompress(const char *source, int32 slen, char *dest,
     690             :                 int32 rawsize, bool check_complete)
     691             : {
     692             :     const unsigned char *sp;
     693             :     const unsigned char *srcend;
     694             :     unsigned char *dp;
     695             :     unsigned char *destend;
     696             : 
     697       86176 :     sp = (const unsigned char *) source;
     698       86176 :     srcend = ((const unsigned char *) source) + slen;
     699       86176 :     dp = (unsigned char *) dest;
     700       86176 :     destend = dp + rawsize;
     701             : 
     702    20309230 :     while (sp < srcend && dp < destend)
     703             :     {
     704             :         /*
     705             :          * Read one control byte and process the next 8 items (or as many as
     706             :          * remain in the compressed input).
     707             :          */
     708    20136878 :         unsigned char ctrl = *sp++;
     709             :         int         ctrlc;
     710             : 
     711   180957510 :         for (ctrlc = 0; ctrlc < 8 && sp < srcend && dp < destend; ctrlc++)
     712             :         {
     713             : 
     714   160820632 :             if (ctrl & 1)
     715             :             {
     716             :                 /*
     717             :                  * Otherwise it contains the match length minus 3 and the
     718             :                  * upper 4 bits of the offset. The next following byte
     719             :                  * contains the lower 8 bits of the offset. If the length is
     720             :                  * coded as 18, another extension tag byte tells how much
     721             :                  * longer the match really was (0-255).
     722             :                  */
     723             :                 int32       len;
     724             :                 int32       off;
     725             : 
     726    51472434 :                 len = (sp[0] & 0x0f) + 3;
     727    51472434 :                 off = ((sp[0] & 0xf0) << 4) | sp[1];
     728    51472434 :                 sp += 2;
     729    51472434 :                 if (len == 18)
     730    14345656 :                     len += *sp++;
     731             : 
     732             :                 /*
     733             :                  * Now we copy the bytes specified by the tag from OUTPUT to
     734             :                  * OUTPUT. It is dangerous and platform dependent to use
     735             :                  * memcpy() here, because the copied areas could overlap
     736             :                  * extremely!
     737             :                  */
     738    51472434 :                 len = Min(len, destend - dp);
     739  1375548738 :                 while (len--)
     740             :                 {
     741  1272603870 :                     *dp = dp[-off];
     742  1272603870 :                     dp++;
     743             :                 }
     744             :             }
     745             :             else
     746             :             {
     747             :                 /*
     748             :                  * An unset control bit means LITERAL BYTE. So we just copy
     749             :                  * one from INPUT to OUTPUT.
     750             :                  */
     751   109348198 :                 *dp++ = *sp++;
     752             :             }
     753             : 
     754             :             /*
     755             :              * Advance the control bit
     756             :              */
     757   160820632 :             ctrl >>= 1;
     758             :         }
     759             :     }
     760             : 
     761             :     /*
     762             :      * Check we decompressed the right amount. If we are slicing, then we
     763             :      * won't necessarily be at the end of the source or dest buffers when we
     764             :      * hit a stop, so we don't test them.
     765             :      */
     766       86176 :     if (check_complete && (dp != destend || sp != srcend))
     767           0 :         return -1;
     768             : 
     769             :     /*
     770             :      * That's it.
     771             :      */
     772       86176 :     return (char *) dp - dest;
     773             : }

Generated by: LCOV version 1.13