575 lines
15 KiB
C
575 lines
15 KiB
C
|
/*
|
||
|
|
* bsearch.c
|
||
|
|
*
|
||
|
|
* Binary search for optimal encoder
|
||
|
|
*/
|
||
|
|
#include "encoder.h"
|
||
|
|
|
||
|
|
|
||
|
|
#define left context->enc_Left
|
||
|
|
#define right context->enc_Right
|
||
|
|
|
||
|
|
|
||
|
|
/*
|
||
|
|
* Define this to force checking that all search locations visited
|
||
|
|
* are valid.
|
||
|
|
*
|
||
|
|
* For debugging purposes only.
|
||
|
|
*/
|
||
|
|
#ifdef _DEBUG
|
||
|
|
#define VERIFY_SEARCHES
|
||
|
|
#endif
|
||
|
|
|
||
|
|
#define VERIFY_SEARCH_CODE(routine_name) \
|
||
|
|
{ \
|
||
|
|
int debug_search; \
|
||
|
|
for (debug_search = 0; debug_search < clen; debug_search++) \
|
||
|
|
{ \
|
||
|
|
_ASSERTE( context->enc_MemWindow[ptr+debug_search] == context->enc_MemWindow[BufPos+debug_search]); \
|
||
|
|
} \
|
||
|
|
}
|
||
|
|
|
||
|
|
#define VERIFY_MULTI_TREE_SEARCH_CODE(routine_name) \
|
||
|
|
_ASSERTE (context->enc_MemWindow[BufPos] == context->enc_MemWindow[ptr]); \
|
||
|
|
_ASSERTE (context->enc_MemWindow[BufPos+1] == context->enc_MemWindow[ptr+1]);
|
||
|
|
|
||
|
|
|
||
|
|
|
||
|
|
/*
|
||
|
|
* Finds the closest matches of all possible lengths, MIN_MATCH <= x <= MAX_MATCH,
|
||
|
|
* at position BufPos.
|
||
|
|
*
|
||
|
|
* The positions of each match location are stored in context->enc_matchpos_table[]
|
||
|
|
*
|
||
|
|
* Returns the longest such match length found, or zero if no matches found.
|
||
|
|
*/
|
||
|
|
|
||
|
|
#ifndef ASM_BSEARCH_FINDMATCH
|
||
|
|
long binary_search_findmatch(t_encoder_context *context, long BufPos)
|
||
|
|
{
|
||
|
|
ulong ptr;
|
||
|
|
ulong a, b;
|
||
|
|
ulong *small_ptr, *big_ptr;
|
||
|
|
ulong end_pos;
|
||
|
|
int val; /* must be signed */
|
||
|
|
int bytes_to_boundary;
|
||
|
|
int clen;
|
||
|
|
int same;
|
||
|
|
int match_length;
|
||
|
|
int small_len, big_len;
|
||
|
|
int i, best_repeated_offset;
|
||
|
|
#ifdef MULTIPLE_SEARCH_TREES
|
||
|
|
ushort tree_to_use;
|
||
|
|
|
||
|
|
/*
|
||
|
|
* Retrieve root node of tree to search, and insert current node at
|
||
|
|
* the root.
|
||
|
|
*/
|
||
|
|
tree_to_use = *((ushort UNALIGNED *) &context->enc_MemWindow[BufPos]);
|
||
|
|
|
||
|
|
ptr = context->enc_tree_root[tree_to_use];
|
||
|
|
context->enc_tree_root[tree_to_use] = BufPos;
|
||
|
|
#else
|
||
|
|
ptr = context->enc_single_tree_root;
|
||
|
|
context->enc_single_tree_root = BufPos;
|
||
|
|
#endif
|
||
|
|
/*
|
||
|
|
* end_pos is the furthest location back we will search for matches
|
||
|
|
*
|
||
|
|
* Remember that our window size is reduced by 3 bytes because of
|
||
|
|
* our repeated offset codes.
|
||
|
|
*
|
||
|
|
* Since BufPos starts at context->enc_window_size when compression begins,
|
||
|
|
* end_pos will never become negative.
|
||
|
|
*/
|
||
|
|
end_pos = BufPos - (context->enc_window_size-4);
|
||
|
|
|
||
|
|
/*
|
||
|
|
* Root node is either NULL, or points to a really distant position.
|
||
|
|
*/
|
||
|
|
if (ptr <= end_pos)
|
||
|
|
{
|
||
|
|
left[BufPos] = right[BufPos] = 0;
|
||
|
|
return 0;
|
||
|
|
}
|
||
|
|
|
||
|
|
#ifdef MULTIPLE_SEARCH_TREES
|
||
|
|
/*
|
||
|
|
* confirmed length (no need to check the first clen chars in a search)
|
||
|
|
*
|
||
|
|
* note: clen is always equal to min(small_len, big_len)
|
||
|
|
*/
|
||
|
|
clen = 2;
|
||
|
|
|
||
|
|
/*
|
||
|
|
* current best match length
|
||
|
|
*/
|
||
|
|
match_length = 2;
|
||
|
|
|
||
|
|
/*
|
||
|
|
* longest match which is < our string
|
||
|
|
*/
|
||
|
|
small_len = 2;
|
||
|
|
|
||
|
|
/*
|
||
|
|
* longest match which is > our string
|
||
|
|
*/
|
||
|
|
big_len = 2;
|
||
|
|
|
||
|
|
/*
|
||
|
|
* record match position for match length 2
|
||
|
|
*/
|
||
|
|
context->enc_matchpos_table[2] = BufPos - ptr + 2;
|
||
|
|
|
||
|
|
#ifdef VERIFY_SEARCHES
|
||
|
|
VERIFY_MULTI_TREE_SEARCH_CODE("binary_search_findmatch()");
|
||
|
|
#endif
|
||
|
|
|
||
|
|
#else /* !MULTIPLE_SEARCH_TREES */
|
||
|
|
|
||
|
|
clen = 0;
|
||
|
|
match_length = 0;
|
||
|
|
small_len = 0;
|
||
|
|
big_len = 0;
|
||
|
|
|
||
|
|
#endif /* MULTIPLE_SEARCH_TREES */
|
||
|
|
|
||
|
|
/*
|
||
|
|
* pointers to nodes to check
|
||
|
|
*/
|
||
|
|
small_ptr = &left[BufPos];
|
||
|
|
big_ptr = &right[BufPos];
|
||
|
|
|
||
|
|
do
|
||
|
|
{
|
||
|
|
/* compare bytes at current node */
|
||
|
|
same = clen;
|
||
|
|
|
||
|
|
#ifdef VERIFY_SEARCHES
|
||
|
|
VERIFY_SEARCH_CODE("binary_search_findmatch()")
|
||
|
|
#endif
|
||
|
|
|
||
|
|
/* don't need to check first clen characters */
|
||
|
|
a = ptr + clen;
|
||
|
|
b = BufPos + clen;
|
||
|
|
|
||
|
|
while ((val = ((int) context->enc_MemWindow[a++]) - ((int) context->enc_MemWindow[b++])) == 0)
|
||
|
|
{
|
||
|
|
/* don't exceed MAX_MATCH */
|
||
|
|
if (++same >= MAX_MATCH)
|
||
|
|
goto long_match;
|
||
|
|
}
|
||
|
|
|
||
|
|
if (val < 0)
|
||
|
|
{
|
||
|
|
if (same > big_len)
|
||
|
|
{
|
||
|
|
if (same > match_length)
|
||
|
|
{
|
||
|
|
long_match:
|
||
|
|
do
|
||
|
|
{
|
||
|
|
context->enc_matchpos_table[++match_length] = BufPos-ptr+(NUM_REPEATED_OFFSETS-1);
|
||
|
|
} while (match_length < same);
|
||
|
|
|
||
|
|
if (same >= BREAK_LENGTH)
|
||
|
|
{
|
||
|
|
*small_ptr = left[ptr];
|
||
|
|
*big_ptr = right[ptr];
|
||
|
|
goto end_bsearch;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
big_len = same;
|
||
|
|
clen = min(small_len, big_len);
|
||
|
|
}
|
||
|
|
|
||
|
|
*big_ptr = ptr;
|
||
|
|
big_ptr = &left[ptr];
|
||
|
|
ptr = *big_ptr;
|
||
|
|
}
|
||
|
|
else
|
||
|
|
{
|
||
|
|
if (same > small_len)
|
||
|
|
{
|
||
|
|
if (same > match_length)
|
||
|
|
{
|
||
|
|
do
|
||
|
|
{
|
||
|
|
context->enc_matchpos_table[++match_length] = BufPos-ptr+(NUM_REPEATED_OFFSETS-1);
|
||
|
|
} while (match_length < same);
|
||
|
|
|
||
|
|
if (same >= BREAK_LENGTH)
|
||
|
|
{
|
||
|
|
*small_ptr = left[ptr];
|
||
|
|
*big_ptr = right[ptr];
|
||
|
|
goto end_bsearch;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
small_len = same;
|
||
|
|
clen = min(small_len, big_len);
|
||
|
|
}
|
||
|
|
|
||
|
|
*small_ptr = ptr;
|
||
|
|
small_ptr = &right[ptr];
|
||
|
|
ptr = *small_ptr;
|
||
|
|
}
|
||
|
|
} while (ptr > end_pos); /* while we don't go too far backwards */
|
||
|
|
|
||
|
|
*small_ptr = 0;
|
||
|
|
*big_ptr = 0;
|
||
|
|
|
||
|
|
|
||
|
|
end_bsearch:
|
||
|
|
|
||
|
|
/*
|
||
|
|
* If we have multiple search trees, we are already guaranteed
|
||
|
|
* a minimum match length of 2 when we reach here.
|
||
|
|
*
|
||
|
|
* If we only have one tree, then we're not guaranteed anything.
|
||
|
|
*/
|
||
|
|
#ifndef MULTIPLE_SEARCH_TREES
|
||
|
|
if (match_length < MIN_MATCH)
|
||
|
|
return 0;
|
||
|
|
#endif
|
||
|
|
|
||
|
|
/*
|
||
|
|
* Check to see if any of our match lengths can
|
||
|
|
* use repeated offsets.
|
||
|
|
*/
|
||
|
|
|
||
|
|
/*
|
||
|
|
* repeated offset 1
|
||
|
|
*/
|
||
|
|
for (i = 0; i < match_length; i++)
|
||
|
|
{
|
||
|
|
if (context->enc_MemWindow[BufPos+i] != context->enc_MemWindow[BufPos-context->enc_last_matchpos_offset[0]+i])
|
||
|
|
break;
|
||
|
|
}
|
||
|
|
|
||
|
|
/*
|
||
|
|
* the longest repeated offset
|
||
|
|
*/
|
||
|
|
best_repeated_offset = i;
|
||
|
|
|
||
|
|
if (i >= MIN_MATCH)
|
||
|
|
{
|
||
|
|
/*
|
||
|
|
* Yes, we can do a repeated offset for some match lengths; replace
|
||
|
|
* their positions with the repeated offset position
|
||
|
|
*/
|
||
|
|
do
|
||
|
|
{
|
||
|
|
context->enc_matchpos_table[i] = 0; /* first repeated offset position */
|
||
|
|
} while (--i >= MIN_MATCH);
|
||
|
|
|
||
|
|
/* A speed optimization to cope with long runs of bytes */
|
||
|
|
if (best_repeated_offset > BREAK_LENGTH)
|
||
|
|
goto quick_return;
|
||
|
|
}
|
||
|
|
|
||
|
|
/*
|
||
|
|
* repeated offset 2
|
||
|
|
*/
|
||
|
|
for (i = 0; i < match_length; i++)
|
||
|
|
{
|
||
|
|
if (context->enc_MemWindow[BufPos+i] != context->enc_MemWindow[BufPos-context->enc_last_matchpos_offset[1]+i])
|
||
|
|
break;
|
||
|
|
}
|
||
|
|
|
||
|
|
/*
|
||
|
|
* Does the second repeated offset provide a longer match?
|
||
|
|
*
|
||
|
|
* If so, leave the first repeated offset alone, but fill out the
|
||
|
|
* difference in match lengths in the table with repeated offset 1.
|
||
|
|
*/
|
||
|
|
if (i > best_repeated_offset)
|
||
|
|
{
|
||
|
|
do
|
||
|
|
{
|
||
|
|
context->enc_matchpos_table[++best_repeated_offset] = 1;
|
||
|
|
} while (best_repeated_offset < i);
|
||
|
|
}
|
||
|
|
|
||
|
|
/*
|
||
|
|
* repeated offset 3
|
||
|
|
*/
|
||
|
|
for (i = 0; i < match_length; i++)
|
||
|
|
{
|
||
|
|
if (context->enc_MemWindow[BufPos+i] != context->enc_MemWindow[BufPos-context->enc_last_matchpos_offset[2]+i])
|
||
|
|
break;
|
||
|
|
}
|
||
|
|
|
||
|
|
/*
|
||
|
|
* Does the third repeated offset provide a longer match?
|
||
|
|
*/
|
||
|
|
if (i > best_repeated_offset)
|
||
|
|
{
|
||
|
|
do
|
||
|
|
{
|
||
|
|
context->enc_matchpos_table[++best_repeated_offset] = 2;
|
||
|
|
} while (best_repeated_offset < i);
|
||
|
|
}
|
||
|
|
|
||
|
|
quick_return:
|
||
|
|
|
||
|
|
/*
|
||
|
|
* Don't let a match cross a 32K boundary
|
||
|
|
*/
|
||
|
|
bytes_to_boundary = (CHUNK_SIZE-1) - ((int) BufPos & (CHUNK_SIZE-1));
|
||
|
|
|
||
|
|
if (match_length > bytes_to_boundary)
|
||
|
|
{
|
||
|
|
match_length = bytes_to_boundary;
|
||
|
|
|
||
|
|
if (match_length < MIN_MATCH)
|
||
|
|
match_length = 0;
|
||
|
|
}
|
||
|
|
|
||
|
|
return (long) match_length;
|
||
|
|
}
|
||
|
|
#endif
|
||
|
|
|
||
|
|
|
||
|
|
/*
|
||
|
|
* Inserts the string at the current BufPos into the tree.
|
||
|
|
*
|
||
|
|
* Does not record all the best match lengths or otherwise attempt
|
||
|
|
* to search for matches
|
||
|
|
*
|
||
|
|
* Similar to the above function.
|
||
|
|
*/
|
||
|
|
#ifndef ASM_QUICK_INSERT_BSEARCH_FINDMATCH
|
||
|
|
void quick_insert_bsearch_findmatch(t_encoder_context *context, long BufPos, long end_pos)
|
||
|
|
{
|
||
|
|
long ptr;
|
||
|
|
ulong a,b;
|
||
|
|
ulong *small_ptr, *big_ptr;
|
||
|
|
int val;
|
||
|
|
int small_len, big_len;
|
||
|
|
int same;
|
||
|
|
int clen;
|
||
|
|
#ifdef MULTIPLE_SEARCH_TREES
|
||
|
|
ushort tree_to_use;
|
||
|
|
|
||
|
|
tree_to_use = *((ushort UNALIGNED *) &context->enc_MemWindow[BufPos]);
|
||
|
|
ptr = context->enc_tree_root[tree_to_use];
|
||
|
|
context->enc_tree_root[tree_to_use] = BufPos;
|
||
|
|
#else
|
||
|
|
ptr = context->enc_single_tree_root;
|
||
|
|
context->enc_single_tree_root = BufPos;
|
||
|
|
#endif
|
||
|
|
|
||
|
|
if (ptr <= end_pos)
|
||
|
|
{
|
||
|
|
left[BufPos] = right[BufPos] = 0;
|
||
|
|
return;
|
||
|
|
}
|
||
|
|
|
||
|
|
#ifdef MULTIPLE_SEARCH_TREES
|
||
|
|
clen = 2;
|
||
|
|
small_len = 2;
|
||
|
|
big_len = 2;
|
||
|
|
|
||
|
|
#ifdef VERIFY_SEARCHES
|
||
|
|
VERIFY_MULTI_TREE_SEARCH_CODE("quick_insert_bsearch_findmatch()");
|
||
|
|
#endif
|
||
|
|
|
||
|
|
#else
|
||
|
|
clen = 0;
|
||
|
|
small_len = 0;
|
||
|
|
big_len = 0;
|
||
|
|
#endif
|
||
|
|
|
||
|
|
small_ptr = &left[BufPos];
|
||
|
|
big_ptr = &right[BufPos];
|
||
|
|
|
||
|
|
do
|
||
|
|
{
|
||
|
|
_ASSERTE ((ulong) ptr >= (ulong) (context->enc_RealLeft - context->enc_Left));
|
||
|
|
|
||
|
|
same = clen;
|
||
|
|
|
||
|
|
a = ptr+clen;
|
||
|
|
b = BufPos+clen;
|
||
|
|
|
||
|
|
#ifdef VERIFY_SEARCHES
|
||
|
|
VERIFY_SEARCH_CODE("quick_insert_bsearch_findmatch()")
|
||
|
|
#endif
|
||
|
|
|
||
|
|
while ((val = ((int) context->enc_MemWindow[a++]) - ((int) context->enc_MemWindow[b++])) == 0)
|
||
|
|
{
|
||
|
|
/*
|
||
|
|
* Here we break on BREAK_LENGTH, not MAX_MATCH
|
||
|
|
*/
|
||
|
|
if (++same >= BREAK_LENGTH)
|
||
|
|
break;
|
||
|
|
}
|
||
|
|
|
||
|
|
if (val < 0)
|
||
|
|
{
|
||
|
|
if (same > big_len)
|
||
|
|
{
|
||
|
|
if (same >= BREAK_LENGTH)
|
||
|
|
{
|
||
|
|
*small_ptr = left[ptr];
|
||
|
|
*big_ptr = right[ptr];
|
||
|
|
return;
|
||
|
|
}
|
||
|
|
|
||
|
|
big_len = same;
|
||
|
|
clen = min(small_len, big_len);
|
||
|
|
}
|
||
|
|
|
||
|
|
*big_ptr = ptr;
|
||
|
|
big_ptr = &left[ptr];
|
||
|
|
ptr = *big_ptr;
|
||
|
|
}
|
||
|
|
else
|
||
|
|
{
|
||
|
|
if (same > small_len)
|
||
|
|
{
|
||
|
|
if (same >= BREAK_LENGTH)
|
||
|
|
{
|
||
|
|
*small_ptr = left[ptr];
|
||
|
|
*big_ptr = right[ptr];
|
||
|
|
return;
|
||
|
|
}
|
||
|
|
|
||
|
|
small_len = same;
|
||
|
|
clen = min(small_len, big_len);
|
||
|
|
}
|
||
|
|
|
||
|
|
*small_ptr = ptr;
|
||
|
|
small_ptr = &right[ptr];
|
||
|
|
ptr = *small_ptr;
|
||
|
|
}
|
||
|
|
} while (ptr > end_pos);
|
||
|
|
|
||
|
|
*small_ptr = 0;
|
||
|
|
*big_ptr = 0;
|
||
|
|
}
|
||
|
|
#endif
|
||
|
|
|
||
|
|
|
||
|
|
/*
|
||
|
|
* Remove a node from the search tree; this is ONLY done for the last
|
||
|
|
* BREAK_LENGTH symbols (see optenc.c). This is because we will have
|
||
|
|
* inserted strings that contain undefined data (e.g. we're at the 4th
|
||
|
|
* last byte from the file and binary_search_findmatch() a string into
|
||
|
|
* the tree - everything from the 4th symbol onwards is invalid, and
|
||
|
|
* would cause problems if it remained in the tree, so we have to
|
||
|
|
* remove it).
|
||
|
|
*/
|
||
|
|
void binary_search_remove_node(t_encoder_context *context, long BufPos, ulong end_pos)
|
||
|
|
{
|
||
|
|
ulong ptr;
|
||
|
|
ulong left_node_pos;
|
||
|
|
ulong right_node_pos;
|
||
|
|
ulong *link;
|
||
|
|
#ifdef MULTIPLE_SEARCH_TREES
|
||
|
|
ushort tree_to_use;
|
||
|
|
|
||
|
|
/*
|
||
|
|
* The root node of tree_to_use should equal BufPos, since that is
|
||
|
|
* the most recent insertion into that tree - but if we never
|
||
|
|
* inserted this string (because it was a near match or a long
|
||
|
|
* string of zeroes), then we can't remove it.
|
||
|
|
*/
|
||
|
|
tree_to_use = *((ushort UNALIGNED *) &context->enc_MemWindow[BufPos]);
|
||
|
|
|
||
|
|
|
||
|
|
/*
|
||
|
|
* If we never inserted this string, do not attempt to remove it
|
||
|
|
*/
|
||
|
|
|
||
|
|
if (context->enc_tree_root[tree_to_use] != (ulong) BufPos)
|
||
|
|
return;
|
||
|
|
|
||
|
|
link = &context->enc_tree_root[tree_to_use];
|
||
|
|
#else
|
||
|
|
if (context->enc_single_tree_root != (ulong) BufPos)
|
||
|
|
return;
|
||
|
|
|
||
|
|
link = &context->enc_single_tree_root;
|
||
|
|
#endif
|
||
|
|
|
||
|
|
/*
|
||
|
|
* If the last occurence was too far away
|
||
|
|
*/
|
||
|
|
if (*link <= end_pos)
|
||
|
|
{
|
||
|
|
*link = 0;
|
||
|
|
left[BufPos] = right[BufPos] = 0;
|
||
|
|
return;
|
||
|
|
}
|
||
|
|
|
||
|
|
/*
|
||
|
|
* Most recent location of these chars
|
||
|
|
*/
|
||
|
|
ptr = BufPos;
|
||
|
|
|
||
|
|
/*
|
||
|
|
* Most recent location of a string which is "less than" it
|
||
|
|
*/
|
||
|
|
left_node_pos = left[ptr];
|
||
|
|
|
||
|
|
if (left_node_pos <= end_pos)
|
||
|
|
left_node_pos = left[ptr] = 0;
|
||
|
|
|
||
|
|
/*
|
||
|
|
* Most recent location of a string which is "greater than" it
|
||
|
|
*/
|
||
|
|
right_node_pos = right[ptr];
|
||
|
|
|
||
|
|
if (right_node_pos <= end_pos)
|
||
|
|
right_node_pos = right[ptr] = 0;
|
||
|
|
|
||
|
|
while (1)
|
||
|
|
{
|
||
|
|
#ifdef VERIFY_SEARCHES
|
||
|
|
_ASSERTE (left_node_pos < (ulong) BufPos);
|
||
|
|
_ASSERTE (right_node_pos < (ulong) BufPos);
|
||
|
|
#endif
|
||
|
|
|
||
|
|
/*
|
||
|
|
* If left node position is greater than right node position
|
||
|
|
* then follow the left node, since that is the more recent
|
||
|
|
* insertion into the tree. Otherwise follow the right node.
|
||
|
|
*/
|
||
|
|
if (left_node_pos > right_node_pos)
|
||
|
|
{
|
||
|
|
/*
|
||
|
|
* If it's too far away, then store that it never happened
|
||
|
|
*/
|
||
|
|
if (left_node_pos <= end_pos)
|
||
|
|
left_node_pos = 0;
|
||
|
|
|
||
|
|
ptr = *link = left_node_pos;
|
||
|
|
|
||
|
|
if (!ptr)
|
||
|
|
break;
|
||
|
|
|
||
|
|
left_node_pos = right[ptr];
|
||
|
|
link = &right[ptr];
|
||
|
|
}
|
||
|
|
else
|
||
|
|
{
|
||
|
|
/*
|
||
|
|
* If it's too far away, then store that it never happened
|
||
|
|
*/
|
||
|
|
if (right_node_pos <= end_pos)
|
||
|
|
right_node_pos = 0;
|
||
|
|
|
||
|
|
ptr = *link = right_node_pos;
|
||
|
|
|
||
|
|
if (!ptr)
|
||
|
|
break;
|
||
|
|
|
||
|
|
right_node_pos = left[ptr];
|
||
|
|
link = &left[ptr];
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|