Header And Logo
|
#include "postgres.h"#include <limits.h>#include "utils/pg_lzcompress.h"
Go to the source code of this file.
Data Structures | |
| struct | PGLZ_HistEntry |
Defines | |
| #define | PGLZ_HISTORY_LISTS 8192 |
| #define | PGLZ_HISTORY_MASK (PGLZ_HISTORY_LISTS - 1) |
| #define | PGLZ_HISTORY_SIZE 4096 |
| #define | PGLZ_MAX_MATCH 273 |
| #define | pglz_hist_idx(_s, _e) |
| #define | pglz_hist_add(_hs, _he, _hn, _recycle, _s, _e) |
| #define | pglz_out_ctrl(__ctrlp, __ctrlb, __ctrl, __buf) |
| #define | pglz_out_literal(_ctrlp, _ctrlb, _ctrl, _buf, _byte) |
| #define | pglz_out_tag(_ctrlp, _ctrlb, _ctrl, _buf, _len, _off) |
Typedefs | |
| typedef struct PGLZ_HistEntry | PGLZ_HistEntry |
Functions | |
| static int | pglz_find_match (PGLZ_HistEntry **hstart, const char *input, const char *end, int *lenp, int *offp, int good_match, int good_drop) |
| bool | pglz_compress (const char *source, int32 slen, PGLZ_Header *dest, const PGLZ_Strategy *strategy) |
| void | pglz_decompress (const PGLZ_Header *source, char *dest) |
Variables | |
| static const PGLZ_Strategy | strategy_default_data |
| const PGLZ_Strategy *const | PGLZ_strategy_default = &strategy_default_data |
| static const PGLZ_Strategy | strategy_always_data |
| const PGLZ_Strategy *const | PGLZ_strategy_always = &strategy_always_data |
| static PGLZ_HistEntry * | hist_start [PGLZ_HISTORY_LISTS] |
| static PGLZ_HistEntry | hist_entries [PGLZ_HISTORY_SIZE] |
| #define pglz_hist_add | ( | _hs, | ||
| _he, | ||||
| _hn, | ||||
| _recycle, | ||||
| _s, | ||||
| _e | ||||
| ) |
do { \ int __hindex = pglz_hist_idx((_s),(_e)); \ PGLZ_HistEntry **__myhsp = &(_hs)[__hindex]; \ PGLZ_HistEntry *__myhe = &(_he)[_hn]; \ if (_recycle) { \ if (__myhe->prev == NULL) \ (_hs)[__myhe->hindex] = __myhe->next; \ else \ __myhe->prev->next = __myhe->next; \ if (__myhe->next != NULL) \ __myhe->next->prev = __myhe->prev; \ } \ __myhe->next = *__myhsp; \ __myhe->prev = NULL; \ __myhe->hindex = __hindex; \ __myhe->pos = (_s); \ if (*__myhsp != NULL) \ (*__myhsp)->prev = __myhe; \ *__myhsp = __myhe; \ if (++(_hn) >= PGLZ_HISTORY_SIZE) { \ (_hn) = 0; \ (_recycle) = true; \ } \ } while (0)
Definition at line 279 of file pg_lzcompress.c.
Referenced by pglz_compress().
| #define pglz_hist_idx | ( | _s, | ||
| _e | ||||
| ) |
( \
((((_e) - (_s)) < 4) ? (int) (_s)[0] : \
(((_s)[0] << 9) ^ ((_s)[1] << 6) ^ \
((_s)[2] << 3) ^ (_s)[3])) & (PGLZ_HISTORY_MASK) \
)
Definition at line 260 of file pg_lzcompress.c.
Referenced by pglz_find_match().
| #define PGLZ_HISTORY_LISTS 8192 |
Definition at line 183 of file pg_lzcompress.c.
| #define PGLZ_HISTORY_MASK (PGLZ_HISTORY_LISTS - 1) |
Definition at line 184 of file pg_lzcompress.c.
| #define PGLZ_HISTORY_SIZE 4096 |
Definition at line 185 of file pg_lzcompress.c.
| #define PGLZ_MAX_MATCH 273 |
Definition at line 186 of file pg_lzcompress.c.
Referenced by pglz_compress(), and pglz_find_match().
| #define pglz_out_ctrl | ( | __ctrlp, | ||
| __ctrlb, | ||||
| __ctrl, | ||||
| __buf | ||||
| ) |
do { \ if ((__ctrl & 0xff) == 0) \ { \ *(__ctrlp) = __ctrlb; \ __ctrlp = (__buf)++; \ __ctrlb = 0; \ __ctrl = 1; \ } \ } while (0)
Definition at line 312 of file pg_lzcompress.c.
| #define pglz_out_literal | ( | _ctrlp, | ||
| _ctrlb, | ||||
| _ctrl, | ||||
| _buf, | ||||
| _byte | ||||
| ) |
do { \ pglz_out_ctrl(_ctrlp,_ctrlb,_ctrl,_buf); \ *(_buf)++ = (unsigned char)(_byte); \ _ctrl <<= 1; \ } while (0)
Definition at line 331 of file pg_lzcompress.c.
Referenced by pglz_compress().
| #define pglz_out_tag | ( | _ctrlp, | ||
| _ctrlb, | ||||
| _ctrl, | ||||
| _buf, | ||||
| _len, | ||||
| _off | ||||
| ) |
do { \ pglz_out_ctrl(_ctrlp,_ctrlb,_ctrl,_buf); \ _ctrlb |= _ctrl; \ _ctrl <<= 1; \ if (_len > 17) \ { \ (_buf)[0] = (unsigned char)((((_off) & 0xf00) >> 4) | 0x0f); \ (_buf)[1] = (unsigned char)(((_off) & 0xff)); \ (_buf)[2] = (unsigned char)((_len) - 18); \ (_buf) += 3; \ } else { \ (_buf)[0] = (unsigned char)((((_off) & 0xf00) >> 4) | ((_len) - 3)); \ (_buf)[1] = (unsigned char)((_off) & 0xff); \ (_buf) += 2; \ } \ } while (0)
Definition at line 347 of file pg_lzcompress.c.
Referenced by pglz_compress().
| typedef struct PGLZ_HistEntry PGLZ_HistEntry |
| bool pglz_compress | ( | const char * | source, | |
| int32 | slen, | |||
| PGLZ_Header * | dest, | |||
| const PGLZ_Strategy * | strategy | |||
| ) |
Definition at line 482 of file pg_lzcompress.c.
References PGLZ_Strategy::first_success_by, PGLZ_Strategy::match_size_drop, PGLZ_Strategy::match_size_good, PGLZ_Strategy::max_input_size, PGLZ_Strategy::min_comp_rate, NULL, pglz_find_match(), pglz_hist_add, PGLZ_MAX_MATCH, pglz_out_literal, pglz_out_tag, PGLZ_Header::rawsize, and SET_VARSIZE_COMPRESSED.
Referenced by toast_compress_datum().
{
unsigned char *bp = ((unsigned char *) dest) + sizeof(PGLZ_Header);
unsigned char *bstart = bp;
int hist_next = 0;
bool hist_recycle = false;
const char *dp = source;
const char *dend = source + slen;
unsigned char ctrl_dummy = 0;
unsigned char *ctrlp = &ctrl_dummy;
unsigned char ctrlb = 0;
unsigned char ctrl = 0;
bool found_match = false;
int32 match_len;
int32 match_off;
int32 good_match;
int32 good_drop;
int32 result_size;
int32 result_max;
int32 need_rate;
/*
* Our fallback strategy is the default.
*/
if (strategy == NULL)
strategy = PGLZ_strategy_default;
/*
* If the strategy forbids compression (at all or if source chunk size out
* of range), fail.
*/
if (strategy->match_size_good <= 0 ||
slen < strategy->min_input_size ||
slen > strategy->max_input_size)
return false;
/*
* Save the original source size in the header.
*/
dest->rawsize = slen;
/*
* Limit the match parameters to the supported range.
*/
good_match = strategy->match_size_good;
if (good_match > PGLZ_MAX_MATCH)
good_match = PGLZ_MAX_MATCH;
else if (good_match < 17)
good_match = 17;
good_drop = strategy->match_size_drop;
if (good_drop < 0)
good_drop = 0;
else if (good_drop > 100)
good_drop = 100;
need_rate = strategy->min_comp_rate;
if (need_rate < 0)
need_rate = 0;
else if (need_rate > 99)
need_rate = 99;
/*
* Compute the maximum result size allowed by the strategy, namely the
* input size minus the minimum wanted compression rate. This had better
* be <= slen, else we might overrun the provided output buffer.
*/
if (slen > (INT_MAX / 100))
{
/* Approximate to avoid overflow */
result_max = (slen / 100) * (100 - need_rate);
}
else
result_max = (slen * (100 - need_rate)) / 100;
/*
* Initialize the history lists to empty. We do not need to zero the
* hist_entries[] array; its entries are initialized as they are used.
*/
memset(hist_start, 0, sizeof(hist_start));
/*
* Compress the source directly into the output buffer.
*/
while (dp < dend)
{
/*
* If we already exceeded the maximum result size, fail.
*
* We check once per loop; since the loop body could emit as many as 4
* bytes (a control byte and 3-byte tag), PGLZ_MAX_OUTPUT() had better
* allow 4 slop bytes.
*/
if (bp - bstart >= result_max)
return false;
/*
* If we've emitted more than first_success_by bytes without finding
* anything compressible at all, fail. This lets us fall out
* reasonably quickly when looking at incompressible input (such as
* pre-compressed data).
*/
if (!found_match && bp - bstart >= strategy->first_success_by)
return false;
/*
* Try to find a match in the history
*/
if (pglz_find_match(hist_start, dp, dend, &match_len,
&match_off, good_match, good_drop))
{
/*
* Create the tag and add history entries for all matched
* characters.
*/
pglz_out_tag(ctrlp, ctrlb, ctrl, bp, match_len, match_off);
while (match_len--)
{
pglz_hist_add(hist_start, hist_entries,
hist_next, hist_recycle,
dp, dend);
dp++; /* Do not do this ++ in the line above! */
/* The macro would do it four times - Jan. */
}
found_match = true;
}
else
{
/*
* No match found. Copy one literal byte.
*/
pglz_out_literal(ctrlp, ctrlb, ctrl, bp, *dp);
pglz_hist_add(hist_start, hist_entries,
hist_next, hist_recycle,
dp, dend);
dp++; /* Do not do this ++ in the line above! */
/* The macro would do it four times - Jan. */
}
}
/*
* Write out the last control byte and check that we haven't overrun the
* output size allowed by the strategy.
*/
*ctrlp = ctrlb;
result_size = bp - bstart;
if (result_size >= result_max)
return false;
/*
* Success - need only fill in the actual length of the compressed datum.
*/
SET_VARSIZE_COMPRESSED(dest, result_size + sizeof(PGLZ_Header));
return true;
}
| void pglz_decompress | ( | const PGLZ_Header * | source, | |
| char * | dest | |||
| ) |
Definition at line 648 of file pg_lzcompress.c.
References elog, ERROR, PGLZ_Header::rawsize, and VARSIZE.
Referenced by heap_tuple_untoast_attr(), and heap_tuple_untoast_attr_slice().
{
const unsigned char *sp;
const unsigned char *srcend;
unsigned char *dp;
unsigned char *destend;
sp = ((const unsigned char *) source) + sizeof(PGLZ_Header);
srcend = ((const unsigned char *) source) + VARSIZE(source);
dp = (unsigned char *) dest;
destend = dp + source->rawsize;
while (sp < srcend && dp < destend)
{
/*
* Read one control byte and process the next 8 items (or as many as
* remain in the compressed input).
*/
unsigned char ctrl = *sp++;
int ctrlc;
for (ctrlc = 0; ctrlc < 8 && sp < srcend; ctrlc++)
{
if (ctrl & 1)
{
/*
* Otherwise it contains the match length minus 3 and the
* upper 4 bits of the offset. The next following byte
* contains the lower 8 bits of the offset. If the length is
* coded as 18, another extension tag byte tells how much
* longer the match really was (0-255).
*/
int32 len;
int32 off;
len = (sp[0] & 0x0f) + 3;
off = ((sp[0] & 0xf0) << 4) | sp[1];
sp += 2;
if (len == 18)
len += *sp++;
/*
* Check for output buffer overrun, to ensure we don't clobber
* memory in case of corrupt input. Note: we must advance dp
* here to ensure the error is detected below the loop. We
* don't simply put the elog inside the loop since that will
* probably interfere with optimization.
*/
if (dp + len > destend)
{
dp += len;
break;
}
/*
* Now we copy the bytes specified by the tag from OUTPUT to
* OUTPUT. It is dangerous and platform dependent to use
* memcpy() here, because the copied areas could overlap
* extremely!
*/
while (len--)
{
*dp = dp[-off];
dp++;
}
}
else
{
/*
* An unset control bit means LITERAL BYTE. So we just copy
* one from INPUT to OUTPUT.
*/
if (dp >= destend) /* check for buffer overrun */
break; /* do not clobber memory */
*dp++ = *sp++;
}
/*
* Advance the control bit
*/
ctrl >>= 1;
}
}
/*
* Check we decompressed the right amount.
*/
if (dp != destend || sp != srcend)
elog(ERROR, "compressed data is corrupt");
/*
* That's it.
*/
}
| static int pglz_find_match | ( | PGLZ_HistEntry ** | hstart, | |
| const char * | input, | |||
| const char * | end, | |||
| int * | lenp, | |||
| int * | offp, | |||
| int | good_match, | |||
| int | good_drop | |||
| ) | [inline, static] |
Definition at line 375 of file pg_lzcompress.c.
References memcmp(), PGLZ_HistEntry::next, pglz_hist_idx, PGLZ_MAX_MATCH, and PGLZ_HistEntry::pos.
Referenced by pglz_compress().
{
PGLZ_HistEntry *hent;
int32 len = 0;
int32 off = 0;
/*
* Traverse the linked history list until a good enough match is found.
*/
hent = hstart[pglz_hist_idx(input, end)];
while (hent)
{
const char *ip = input;
const char *hp = hent->pos;
int32 thisoff;
int32 thislen;
/*
* Stop if the offset does not fit into our tag anymore.
*/
thisoff = ip - hp;
if (thisoff >= 0x0fff)
break;
/*
* Determine length of match. A better match must be larger than the
* best so far. And if we already have a match of 16 or more bytes,
* it's worth the call overhead to use memcmp() to check if this match
* is equal for the same size. After that we must fallback to
* character by character comparison to know the exact position where
* the diff occurred.
*/
thislen = 0;
if (len >= 16)
{
if (memcmp(ip, hp, len) == 0)
{
thislen = len;
ip += len;
hp += len;
while (ip < end && *ip == *hp && thislen < PGLZ_MAX_MATCH)
{
thislen++;
ip++;
hp++;
}
}
}
else
{
while (ip < end && *ip == *hp && thislen < PGLZ_MAX_MATCH)
{
thislen++;
ip++;
hp++;
}
}
/*
* Remember this match as the best (if it is)
*/
if (thislen > len)
{
len = thislen;
off = thisoff;
}
/*
* Advance to the next history entry
*/
hent = hent->next;
/*
* Be happy with lesser good matches the more entries we visited. But
* no point in doing calculation if we're at end of list.
*/
if (hent)
{
if (len >= good_match)
break;
good_match -= (good_match * good_drop) / 100;
}
}
/*
* Return match information only if it results at least in one byte
* reduction.
*/
if (len > 2)
{
*lenp = len;
*offp = off;
return 1;
}
return 0;
}
PGLZ_HistEntry hist_entries[PGLZ_HISTORY_SIZE] [static] |
Definition at line 245 of file pg_lzcompress.c.
PGLZ_HistEntry* hist_start[PGLZ_HISTORY_LISTS] [static] |
Definition at line 244 of file pg_lzcompress.c.
| const PGLZ_Strategy* const PGLZ_strategy_always = &strategy_always_data |
Definition at line 237 of file pg_lzcompress.c.
| const PGLZ_Strategy* const PGLZ_strategy_default = &strategy_default_data |
Definition at line 225 of file pg_lzcompress.c.
Referenced by toast_compress_datum().
const PGLZ_Strategy strategy_always_data [static] |
{
0,
INT_MAX,
0,
INT_MAX,
128,
6
}
Definition at line 228 of file pg_lzcompress.c.
const PGLZ_Strategy strategy_default_data [static] |
{
32,
INT_MAX,
25,
1024,
128,
10
}
Definition at line 212 of file pg_lzcompress.c.
1.7.1