aboutsummaryrefslogtreecommitdiff
path: root/src/liblzma/lz/match_c.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/liblzma/lz/match_c.h')
-rw-r--r--src/liblzma/lz/match_c.h412
1 files changed, 0 insertions, 412 deletions
diff --git a/src/liblzma/lz/match_c.h b/src/liblzma/lz/match_c.h
deleted file mode 100644
index 664db290..00000000
--- a/src/liblzma/lz/match_c.h
+++ /dev/null
@@ -1,412 +0,0 @@
-///////////////////////////////////////////////////////////////////////////////
-//
-/// \file match_c.h
-/// \brief Template for different match finders
-///
-/// This file is included by hc3.c, hc4, bt2.c, bt3.c and bt4.c. Each file
-/// sets slighly different #defines, resulting the different match finders.
-//
-// Copyright (C) 1999-2006 Igor Pavlov
-// Copyright (C) 2007 Lasse Collin
-//
-// This library is free software; you can redistribute it and/or
-// modify it under the terms of the GNU Lesser General Public
-// License as published by the Free Software Foundation; either
-// version 2.1 of the License, or (at your option) any later version.
-//
-// This library is distributed in the hope that it will be useful,
-// but WITHOUT ANY WARRANTY; without even the implied warranty of
-// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
-// Lesser General Public License for more details.
-//
-///////////////////////////////////////////////////////////////////////////////
-
-//////////////
-// Includes //
-//////////////
-
-#include "check.h"
-
-
-///////////////
-// Constants //
-///////////////
-
-#define START_MAX_LEN 1
-
-#ifdef HASH_ARRAY_2
-# define NUM_HASH_DIRECT_BYTES 0
-# define HASH_2_SIZE (1 << 10)
-# ifdef HASH_ARRAY_3
-# define NUM_HASH_BYTES 4
-# define HASH_3_SIZE (1 << 16)
-# define HASH_3_OFFSET HASH_2_SIZE
-# define FIX_HASH_SIZE (HASH_2_SIZE + HASH_3_SIZE)
-# else
-# define NUM_HASH_BYTES 3
-# define FIX_HASH_SIZE HASH_2_SIZE
-# endif
-# define HASH_SIZE 0
-# define MIN_MATCH_CHECK NUM_HASH_BYTES
-#else
-# define NUM_HASH_DIRECT_BYTES 2
-# define NUM_HASH_BYTES 2
-# define HASH_SIZE (1 << (8 * NUM_HASH_BYTES))
-# define MIN_MATCH_CHECK (NUM_HASH_BYTES + 1)
-# define FIX_HASH_SIZE 0
-#endif
-
-
-////////////
-// Macros //
-////////////
-
-#ifdef HASH_ARRAY_2
-# ifdef HASH_ARRAY_3
-# define HASH_CALC() \
- do { \
- const uint32_t temp = lzma_crc32_table[0][ \
- cur[0]] ^ cur[1]; \
- hash_2_value = temp & (HASH_2_SIZE - 1); \
- hash_3_value = (temp ^ ((uint32_t)(cur[2]) << 8)) \
- & (HASH_3_SIZE - 1); \
- hash_value = (temp ^ ((uint32_t)(cur[2]) << 8) \
- ^ (lzma_crc32_table[0][cur[3]] << 5)) \
- & lz->hash_mask; \
- } while (0)
-# else
-# define HASH_CALC() \
- do { \
- const uint32_t temp = lzma_crc32_table[0][ \
- cur[0]] ^ cur[1]; \
- hash_2_value = temp & (HASH_2_SIZE - 1); \
- hash_value = (temp ^ ((uint32_t)(cur[2]) << 8)) \
- & lz->hash_mask; \
- } while (0)
-# endif
-#else
-# define HASH_CALC() hash_value = cur[0] ^ ((uint32_t)(cur[1]) << 8)
-#endif
-
-
-// Moves the current read position forward by one byte. In LZMA SDK,
-// CLZInWindow::MovePos() can read more input data if needed, because of
-// the callback style API. In liblzma we must have ensured earlier, that
-// there is enough data available in lz->buffer.
-#define move_pos() \
-do { \
- if (++lz->cyclic_buffer_pos == lz->cyclic_buffer_size) \
- lz->cyclic_buffer_pos = 0; \
- ++lz->read_pos; \
- assert(lz->read_pos <= lz->write_pos); \
- if (lz->read_pos == MAX_VAL_FOR_NORMALIZE) \
- lzma_lz_encoder_normalize(lz); \
-} while (0)
-
-
-#define move_pending() \
-do { \
- ++lz->read_pos; \
- assert(lz->read_pos <= lz->write_pos); \
- ++lz->pending; \
-} while (0)
-
-
-//////////////////////
-// Global constants //
-//////////////////////
-
-LZMA_HASH_SIZE(LZMA_MATCH_FINDER_NAME_UPPER) = HASH_SIZE;
-LZMA_FIX_HASH_SIZE(LZMA_MATCH_FINDER_NAME_UPPER) = FIX_HASH_SIZE;
-
-
-///////////////////
-// API functions //
-///////////////////
-
-LZMA_GET_MATCHES(LZMA_MATCH_FINDER_NAME_LOWER)
-{
- uint32_t len_limit;
- if (lz->read_pos + lz->match_max_len <= lz->write_pos) {
- len_limit = lz->match_max_len;
- } else {
- len_limit = lz->write_pos - lz->read_pos;
- if (len_limit < MIN_MATCH_CHECK || lz->sequence == SEQ_FLUSH) {
- distances[0] = 0;
- move_pending();
- return;
- }
- }
-
- assert(lz->pending == 0);
-
- int32_t offset = 1;
- const uint32_t match_min_pos
- = lz->read_pos + lz->offset > lz->cyclic_buffer_size
- ? lz->read_pos + lz->offset - lz->cyclic_buffer_size
- : 0;
- const uint8_t *cur = lz->buffer + lz->read_pos;
- uint32_t max_len = START_MAX_LEN; // to avoid items for len < hash_size
-
-#ifdef HASH_ARRAY_2
- uint32_t hash_2_value;
-# ifdef HASH_ARRAY_3
- uint32_t hash_3_value;
-# endif
-#endif
- uint32_t hash_value;
- HASH_CALC();
-
- uint32_t cur_match = lz->hash[FIX_HASH_SIZE + hash_value];
-#ifdef HASH_ARRAY_2
- uint32_t cur_match2 = lz->hash[hash_2_value];
-# ifdef HASH_ARRAY_3
- uint32_t cur_match3 = lz->hash[HASH_3_OFFSET + hash_3_value];
-# endif
- lz->hash[hash_2_value] = lz->read_pos + lz->offset;
-
- if (cur_match2 > match_min_pos) {
- if (lz->buffer[cur_match2 - lz->offset] == cur[0]) {
- max_len = 2;
- distances[offset++] = 2;
- distances[offset++] = lz->read_pos + lz->offset
- - cur_match2 - 1;
- }
- }
-
-# ifdef HASH_ARRAY_3
- lz->hash[HASH_3_OFFSET + hash_3_value] = lz->read_pos + lz->offset;
- if (cur_match3 > match_min_pos) {
- if (lz->buffer[cur_match3 - lz->offset] == cur[0]) {
- if (cur_match3 == cur_match2)
- offset -= 2;
-
- max_len = 3;
- distances[offset++] = 3;
- distances[offset++] = lz->read_pos + lz->offset
- - cur_match3 - 1;
- cur_match2 = cur_match3;
- }
- }
-# endif
-
- if (offset != 1 && cur_match2 == cur_match) {
- offset -= 2;
- max_len = START_MAX_LEN;
- }
-#endif
-
- lz->hash[FIX_HASH_SIZE + hash_value] = lz->read_pos + lz->offset;
-
-#ifdef IS_HASH_CHAIN
- lz->son[lz->cyclic_buffer_pos] = cur_match;
-#else
- uint32_t *ptr0 = lz->son + (lz->cyclic_buffer_pos << 1) + 1;
- uint32_t *ptr1 = lz->son + (lz->cyclic_buffer_pos << 1);
-
- uint32_t len0 = NUM_HASH_DIRECT_BYTES;
- uint32_t len1 = NUM_HASH_DIRECT_BYTES;
-#endif
-
-#if NUM_HASH_DIRECT_BYTES != 0
- if (cur_match > match_min_pos) {
- if (lz->buffer[cur_match + NUM_HASH_DIRECT_BYTES - lz->offset]
- != cur[NUM_HASH_DIRECT_BYTES]) {
- max_len = NUM_HASH_DIRECT_BYTES;
- distances[offset++] = NUM_HASH_DIRECT_BYTES;
- distances[offset++] = lz->read_pos + lz->offset
- - cur_match - 1;
- }
- }
-#endif
-
- uint32_t count = lz->cut_value;
-
- while (true) {
- if (cur_match <= match_min_pos || count-- == 0) {
-#ifndef IS_HASH_CHAIN
- *ptr0 = EMPTY_HASH_VALUE;
- *ptr1 = EMPTY_HASH_VALUE;
-#endif
- break;
- }
-
- const uint32_t delta = lz->read_pos + lz->offset - cur_match;
- const uint32_t cyclic_pos = delta <= lz->cyclic_buffer_pos
- ? lz->cyclic_buffer_pos - delta
- : lz->cyclic_buffer_pos - delta
- + lz->cyclic_buffer_size;
- uint32_t *pair = lz->son +
-#ifdef IS_HASH_CHAIN
- cyclic_pos;
-#else
- (cyclic_pos << 1);
-#endif
-
- const uint8_t *pb = lz->buffer + cur_match - lz->offset;
- uint32_t len =
-#ifdef IS_HASH_CHAIN
- NUM_HASH_DIRECT_BYTES;
- if (pb[max_len] == cur[max_len])
-#else
- MIN(len0, len1);
-#endif
-
- if (pb[len] == cur[len]) {
- while (++len != len_limit)
- if (pb[len] != cur[len])
- break;
-
- if (max_len < len) {
- max_len = len;
- distances[offset++] = len;
- distances[offset++] = delta - 1;
- if (len == len_limit) {
-#ifndef IS_HASH_CHAIN
- *ptr1 = pair[0];
- *ptr0 = pair[1];
-#endif
- break;
- }
- }
- }
-
-#ifdef IS_HASH_CHAIN
- cur_match = *pair;
-#else
- if (pb[len] < cur[len]) {
- *ptr1 = cur_match;
- ptr1 = pair + 1;
- cur_match = *ptr1;
- len1 = len;
- } else {
- *ptr0 = cur_match;
- ptr0 = pair;
- cur_match = *ptr0;
- len0 = len;
- }
-#endif
- }
-
- distances[0] = offset - 1;
-
- move_pos();
-
- return;
-}
-
-
-LZMA_SKIP(LZMA_MATCH_FINDER_NAME_LOWER)
-{
- do {
-#ifdef IS_HASH_CHAIN
- if (lz->write_pos - lz->read_pos < NUM_HASH_BYTES) {
- move_pending();
- continue;
- }
-#else
- uint32_t len_limit;
- if (lz->read_pos + lz->match_max_len <= lz->write_pos) {
- len_limit = lz->match_max_len;
- } else {
- len_limit = lz->write_pos - lz->read_pos;
- if (len_limit < MIN_MATCH_CHECK
- || lz->sequence == SEQ_FLUSH) {
- move_pending();
- continue;
- }
- }
- const uint32_t match_min_pos
- = lz->read_pos + lz->offset > lz->cyclic_buffer_size
- ? lz->read_pos + lz->offset - lz->cyclic_buffer_size
- : 0;
-#endif
-
- assert(lz->pending == 0);
-
- const uint8_t *cur = lz->buffer + lz->read_pos;
-
-#ifdef HASH_ARRAY_2
- uint32_t hash_2_value;
-# ifdef HASH_ARRAY_3
- uint32_t hash_3_value;
- uint32_t hash_value;
- HASH_CALC();
- lz->hash[HASH_3_OFFSET + hash_3_value]
- = lz->read_pos + lz->offset;
-# else
- uint32_t hash_value;
- HASH_CALC();
-# endif
- lz->hash[hash_2_value] = lz->read_pos + lz->offset;
-#else
- uint32_t hash_value;
- HASH_CALC();
-#endif
-
- uint32_t cur_match = lz->hash[FIX_HASH_SIZE + hash_value];
- lz->hash[FIX_HASH_SIZE + hash_value]
- = lz->read_pos + lz->offset;
-
-#ifdef IS_HASH_CHAIN
- lz->son[lz->cyclic_buffer_pos] = cur_match;
-#else
- uint32_t *ptr0 = lz->son + (lz->cyclic_buffer_pos << 1) + 1;
- uint32_t *ptr1 = lz->son + (lz->cyclic_buffer_pos << 1);
-
- uint32_t len0 = NUM_HASH_DIRECT_BYTES;
- uint32_t len1 = NUM_HASH_DIRECT_BYTES;
- uint32_t count = lz->cut_value;
-
- while (true) {
- if (cur_match <= match_min_pos || count-- == 0) {
- *ptr0 = EMPTY_HASH_VALUE;
- *ptr1 = EMPTY_HASH_VALUE;
- break;
- }
-
- const uint32_t delta = lz->read_pos
- + lz->offset - cur_match;
- const uint32_t cyclic_pos
- = delta <= lz->cyclic_buffer_pos
- ? lz->cyclic_buffer_pos - delta
- : lz->cyclic_buffer_pos - delta
- + lz->cyclic_buffer_size;
- uint32_t *pair = lz->son + (cyclic_pos << 1);
-
- const uint8_t *pb = lz->buffer + cur_match
- - lz->offset;
- uint32_t len = MIN(len0, len1);
-
- if (pb[len] == cur[len]) {
- while (++len != len_limit)
- if (pb[len] != cur[len])
- break;
-
- if (len == len_limit) {
- *ptr1 = pair[0];
- *ptr0 = pair[1];
- break;
- }
- }
-
- if (pb[len] < cur[len]) {
- *ptr1 = cur_match;
- ptr1 = pair + 1;
- cur_match = *ptr1;
- len1 = len;
- } else {
- *ptr0 = cur_match;
- ptr0 = pair;
- cur_match = *ptr0;
- len0 = len;
- }
- }
-#endif
-
- move_pos();
-
- } while (--num != 0);
-
- return;
-}
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-15 04:38:25 +0000