lz_encoder_mf.c File Reference

Match finders. More...

`#include "lz_encoder.h"`
`#include "lz_encoder_hash.h"`
`#include "memcmplen.h"`

## Macros

#define | EMPTY_HASH_VALUE 0
#define | MUST_NORMALIZE_POS UINT32_MAX
#define | header(is_bt, len_min, ret_op)
#define | header_find(is_bt, len_min)
#define | header_skip(is_bt, len_min) header(is_bt, len_min, continue)
#define | call_find(func, len_best)

## Functions

uint32_t | lzma_mf_find (lzma_mf *mf, uint32_t *count_ptr, lzma_match *matches)
| Find matches starting from the current byte. More...
static void | normalize (lzma_mf *mf)
| Normalizes hash values. More...
static void | move_pos (lzma_mf *mf)
| Mark the current byte as processed from point of view of the match finder. More...
static void | move_pending (lzma_mf *mf)

## Detailed Description

Match finders.

## Macro Definition Documentation

## EMPTY_HASH_VALUE

#define EMPTY_HASH_VALUE 0

Hash value to indicate unused element in the hash. Since we start the positions from dict_size + 1, zero is always too far to qualify as usable match position.

## MUST_NORMALIZE_POS

#define MUST_NORMALIZE_POS UINT32_MAX

Normalization must be done when lzma_mf.offset + lzma_mf.read_pos reaches MUST_NORMALIZE_POS.

## header

#define header | ( |  | is_bt,
|  |  | len_min,
|  |  | ret_op
| ) |  |

Value:
uint32_t len_limit = mf_avail(mf); \
if (mf->nice_len <= len_limit) { \
len_limit = mf->nice_len; \
} else if (len_limit < (len_min) \
|| (is_bt && mf->action == LZMA_SYNC_FLUSH)) { \
assert(mf->action != LZMA_RUN); \
move_pending(mf); \
ret_op; \
} \
const uint8_t *cur = mf_ptr(mf); \
const uint32_t pos = mf->read_pos + mf->offset
LZMA_SYNC_FLUSH
@ LZMA_SYNC_FLUSH
Make all the input available at output.
Definition: base.h:265
LZMA_RUN
@ LZMA_RUN
Continue coding.
Definition: base.h:251
mf_avail
static uint32_t mf_avail(const lzma_mf *mf)
Get the number of bytes that haven't been ran through the match finder yet.
Definition: lz_encoder.h:229
mf_ptr
static const uint8_t * mf_ptr(const lzma_mf *mf)
Get pointer to the first byte not ran through the match finder.
Definition: lz_encoder.h:221

Calculate len_limit and determine if there is enough input to run the actual match finder code. Sets up "cur" and "pos". This macro is used by all find functions and binary tree skip functions. Hash chain skip function doesn't need len_limit so a simpler code is used in them.

## header_find

#define header_find | ( |  | is_bt,
|  |  | len_min
| ) |  |

Value:
header(is_bt, len_min, return 0); \
uint32_t matches_count = 0
header
#define header(is_bt, len_min, ret_op)
Definition: lz_encoder_mf.c:191

Header for find functions. "return 0" indicates that zero matches were found.

## header_skip

#define header_skip | ( |  | is_bt,
|  |  | len_min
| ) |  | header(is_bt, len_min, continue)

Header for a loop in a skip function. "continue" tells to skip the rest of the code in the loop.

## call_find

#define call_find | ( |  | func,
|  |  | len_best
| ) |  |

Value:
do { \
matches_count = func(len_limit, pos, cur, cur_match, mf->depth, \
mf->son, mf->cyclic_pos, mf->cyclic_size, \
matches + matches_count, len_best) \
- matches; \
move_pos(mf); \
return matches_count; \
} while (0)

Calls hc_find_func() or bt_find_func() and calculates the total number of matches found. Updates the dictionary position and returns the number of matches found.

## Function Documentation

## lzma_mf_find()

uint32_t lzma_mf_find | ( | lzma_mf * | mf,
|  | uint32_t * | count_ptr,
|  | lzma_match * | matches
| ) |  |

Find matches starting from the current byte.

Returns
  The length of the longest match found

References lzma_mf_s::find.

## normalize()

static void normalize | ( | lzma_mf * | mf | ) |

static

Normalizes hash values.

The hash arrays store positions of match candidates. The positions are relative to an arbitrary offset that is not the same as the absolute offset in the input stream. The relative position of the current byte is lzma_mf.offset + lzma_mf.read_pos. The distances of the matches are the differences of the current read position and the position found from the hash.

To prevent integer overflows of the offsets stored in the hash arrays, we need to "normalize" the stored values now and then. During the normalization, we drop values that indicate distance greater than the dictionary size, thus making space for new values.

## move_pos()

static void move_pos | ( | lzma_mf * | mf | ) |

static

Mark the current byte as processed from point of view of the match finder.

References lzma_mf_s::read_pos.

## move_pending()

static void move_pending | ( | lzma_mf * | mf | ) |

static

When flushing, we cannot run the match finder unless there is nice_len bytes available in the dictionary. Instead, we skip running the match finder (indicating that no match was found), and count how many bytes we have ignored this way.

When new data is given after the flushing was completed, the match finder is restarted by rewinding mf->read_pos backwards by mf->pending. Then the missed bytes are added to the hash using the match finder's skip function (with small amount of input, it may start using mf->pending again if flushing).

Due to this rewinding, we don't touch cyclic_pos or test for normalization. It will be done when the match finder's skip function catches up after a flush.

References lzma_mf_s::read_pos.