8000
Skip to content

radix_engine.h

Latest commit

 

History

History
1021 lines (962 loc) · 37.4 KB

radix_engine.h

File metadata and controls

1021 lines (962 loc) · 37.4 KB
/* Pre-load the next link */
size_t const next_link = GetInitialMatchLink(link);
size_t const radix_8 = next_radix_8;
size_t const radix_16 = next_radix_16;
/* Initialization doesn't set lengths to 2 because it's a waste of time if buffering is used */
SetMatchLength(link, (U32)next_link, 2);
next_radix_8 = data_src[next_link];
next_radix_16 = next_radix_8 + ((size_t)(data_src[next_link + 1]) << 8);
U32 prev = tbl->tails_8[radix_8].prev_index;
tbl->tails_8[radix_8].prev_index = (U32)link;
if (prev != RADIX_NULL_LINK) {
/* Link the previous occurrence to this one at length 3. */
/* This will be overwritten if a 4 is found. */
SetMatchLinkAndLength(prev, (U32)link, 3);
}
else {
reset_list[reset_count++] = radix_8;
}
prev = tbl->tails_16[radix_16].prev_index;
tbl->tails_16[radix_16].prev_index = (U32)link;
if (prev != RADIX_NULL_LINK) {
++tbl->tails_16[radix_16].list_count;
/* Link at length 4, overwriting the 3 */
SetMatchLinkAndLength(prev, (U32)link, 4);
}
else {
tbl->tails_16[radix_16].list_count = 1;
tbl->stack[st_index].head = (U32)link;
/* Store a reference to this table location to retrieve the count at the end */
tbl->stack[st_index].count = (U32)radix_16;
++st_index;
}
link = next_link;
} while (--count > 0);
/* Do the last location */
U32 prev = tbl->tails_8[next_radix_8].prev_index;
if (prev != RADIX_NULL_LINK)
SetMatchLinkAndLength(prev, (U32)link, 3);
prev = tbl->tails_16[next_radix_16].prev_index;
if (prev != RADIX_NULL_LINK) {
++tbl->tails_16[next_radix_16].list_count;
SetMatchLinkAndLength(prev, (U32)link, 4);
}
for (size_t i = 0; i < reset_count; ++i)
tbl->tails_8[reset_list[i]].prev_index = RADIX_NULL_LINK;
for (size_t i = 0; i < st_index; ++i) {
tbl->tails_16[tbl->stack[i].count].prev_index = RADIX_NULL_LINK;
tbl->stack[i].count = tbl->tails_16[tbl->stack[i].count].list_count;
}
while (st_index > 0) {
--st_index;
U32 const list_count = tbl->stack[st_index].count;
if (list_count < 2) {
/* Nothing to do */
continue;
}
link = tbl->stack[st_index].head;
if (link < block_start)
continue;
if (st_index > STACK_SIZE - RADIX16_TABLE_SIZE
&& st_index > STACK_SIZE - list_count)
{
/* Potential stack overflow. Rare. */
continue;
}
/* The current depth */
U32 const depth = GetMatchLength(link);
if (list_count <= MAX_BRUTE_FORCE_LIST_SIZE) {
/* Quicker to use brute force, each string compared with all previous strings */
RMF_bruteForce(tbl, data_block,
block_start,
link,
list_count,
depth,
table_max_depth);
continue;
}
/* Send to the buffer at depth 4 */
RMF_recurseListsBuffered(tbl,
data_block,
block_start,
block_end,
link,
(BYTE)depth,
(BYTE)max_depth,
list_count,
st_index);
}
}
#if 0
/* Unbuffered complete processing to max_depth.
* This may be faster on CPUs without a large memory cache.
*/
static void RMF_recurseListsUnbuf16(RMF_builder* const tbl,
const BYTE* const data_block,
size_t const block_start,
size_t link,
U32 count,
U32 const max_depth)
{
/* Offset data pointer. This method is only called at depth 2 */
const BYTE* data_src = data_block + 2;
/* Load radix values from the data chars */
size_t next_radix_8 = data_src[link];
size_t next_radix_16 = next_radix_8 + ((size_t)(data_src[link + 1]) << 8);
RMF_listTail* tails_8 = tbl->tails_8;
size_t reset_list[RADIX8_TABLE_SIZE];
size_t reset_count = 0;
size_t st_index = 0;
/* Last one is done separately */
--count;
do
{
/* Pre-load the next link */
size_t next_link = GetInitialMatchLink(link);
/* Initialization doesn't set lengths to 2 because it's a waste of time if buffering is used */
SetMatchLength(link, (U32)next_link, 2);
size_t radix_8 = next_radix_8;
size_t radix_16 = next_radix_16;
next_radix_8 = data_src[next_link];
next_radix_16 = next_radix_8 + ((size_t)(data_src[next_link + 1]) << 8);
U32 prev = tails_8[radix_8].prev_index;
if (prev != RADIX_NULL_LINK) {
/* Link the previous occurrence to this one at length 3. */
/* This will be overwritten if a 4 is found. */
SetMatchLinkAndLength(prev, (U32)link, 3);
}
else {
reset_list[reset_count++] = radix_8;
}
tails_8[radix_8].prev_index = (U32)link;
prev = tbl->tails_16[radix_16].prev_index;
if (prev != RADIX_NULL_LINK) {
++tbl->tails_16[radix_16].list_count;
/* Link at length 4, overwriting the 3 */
SetMatchLinkAndLength(prev, (U32)link, 4);
}
else {
tbl->tails_16[radix_16].list_count = 1;
tbl->stack[st_index].head = (U32)link;
tbl->stack[st_index].count = (U32)radix_16;
++st_index;
}
tbl->tails_16[radix_16].prev_index = (U32)link;
link = next_link;
} while (--count > 0);
/* Do the last location */
U32 prev = tails_8[next_radix_8].prev_index;
if (prev != RADIX_NULL_LINK) {
SetMatchLinkAndLength(prev, (U32)link, 3);
}
prev = tbl->tails_16[next_radix_16].prev_index;
if (prev != RADIX_NULL_LINK) {
++tbl->tails_16[next_radix_16].list_count;
SetMatchLinkAndLength(prev, (U32)link, 4);
}
for (size_t i = 0; i < reset_count; ++i) {
tails_8[reset_list[i]].prev_index = RADIX_NULL_LINK;
}
reset_count = 0;
for (size_t i = 0; i < st_index; ++i) {
tbl->tails_16[tbl->stack[i].count].prev_index = RADIX_NULL_LINK;
tbl->stack[i].count = tbl->tails_16[tbl->stack[i].count].list_count;
}
while (st_index > 0) {
--st_index;
U32 list_count = tbl->stack[st_index].count;
if (list_count < 2) {
/* Nothing to do */
continue;
}
link = tbl->stack[st_index].head;
if (link < block_start)
continue;
if (st_index > STACK_SIZE - RADIX16_TABLE_SIZE
&& st_index > STACK_SIZE - list_count)
{
/* Potential stack overflow. Rare. */
continue;
}
/* The current depth */
U32 depth = GetMatchLength(link);
if (list_count <= MAX_BRUTE_FORCE_LIST_SIZE) {
/* Quicker to use brute force, each string compared with all previous strings */
RMF_bruteForce(tbl, data_block,
block_start,
link,
list_count,
depth,
max_depth);
continue;
}
const BYTE* data_src = data_block + depth;
size_t next_radix_8 = data_src[link];
size_t next_radix_16 = next_radix_8 + ((size_t)(data_src[link + 1]) << 8);
/* Next depth for 1 extra char */
++depth;
/* and for 2 */
U32 depth_2 = depth + 1;
size_t prev_st_index = st_index;
/* Last location is done separately */
--list_count;
/* Last pass is done separately. Both of these values are always even. */
if (depth_2 < max_depth) {
do {
size_t radix_8 = next_radix_8;
size_t radix_16 = next_radix_16;
size_t next_link = GetMatchLink(link);
next_radix_8 = data_src[next_link];
next_radix_16 = next_radix_8 + ((size_t)(data_src[next_link + 1]) << 8);
size_t prev = tbl->tails_8[radix_8].prev_index;
if (prev != RADIX_NULL_LINK) {
/* Odd numbered match length, will be overwritten if 2 chars are matched */
SetMatchLinkAndLength(prev, (U32)(link), depth);
}
else {
reset_list[reset_count++] = radix_8;
}
tbl->tails_8[radix_8].prev_index = (U32)link;
prev = tbl->tails_16[radix_16].prev_index;
if (prev != RADIX_NULL_LINK) {
++tbl->tails_16[radix_16].list_count;
SetMatchLinkAndLength(prev, (U32)(link), depth_2);
}
else {
tbl->tails_16[radix_16].list_count = 1;
tbl->stack[st_index].head = (U32)(link);
tbl->stack[st_index].count = (U32)(radix_16);
++st_index;
}
tbl->tails_16[radix_16].prev_index = (U32)(link);
link = next_link;
} while (--list_count != 0);
size_t prev = tbl->tails_8[next_radix_8].prev_index;
if (prev != RADIX_NULL_LINK) {
SetMatchLinkAndLength(prev, (U32)(link), depth);
}
prev = tbl->tails_16[next_radix_16].prev_index;
if (prev != RADIX_NULL_LINK) {
++tbl->tails_16[next_radix_16].list_count;
SetMatchLinkAndLength(prev, (U32)(link), depth_2);
}
for (size_t i = prev_st_index; i < st_index; ++i) {
tbl->tails_16[tbl->stack[i].count].prev_index = RADIX_NULL_LINK;
tbl->stack[i].count = tbl->tails_16[tbl->stack[i].count].list_count;
}
for (size_t i = 0; i < reset_count; ++i) {
tails_8[reset_list[i]].prev_index = RADIX_NULL_LINK;
}
reset_count = 0;
}
else {
< 579F /div>
do {
size_t radix_8 = next_radix_8;
size_t radix_16 = next_radix_16;
size_t next_link = GetMatchLink(link);
next_radix_8 = data_src[next_link];
next_radix_16 = next_radix_8 + ((size_t)(data_src[next_link + 1]) << 8);
size_t prev = tbl->tails_8[radix_8].prev_index;
if (prev != RADIX_NULL_LINK) {
SetMatchLinkAndLength(prev, (U32)(link), depth);
}
else {
reset_list[reset_count++] = radix_8;
}
tbl->tails_8[radix_8].prev_index = (U32)link;
prev = tbl->tails_16[radix_16].prev_index;
if (prev != RADIX_NULL_LINK) {
SetMatchLinkAndLength(prev, (U32)(link), depth_2);
}
else {
tbl->stack[st_index].count = (U32)radix_16;
++st_index;
}
tbl->tails_16[radix_16].prev_index = (U32)(link);
link = next_link;
} while (--list_count != 0);
size_t prev = tbl->tails_8[next_radix_8].prev_index;
if (prev != RADIX_NULL_LINK) {
SetMatchLinkAndLength(prev, (U32)(link), depth);
}
prev = tbl->tails_16[next_radix_16].prev_index;
if (prev != RADIX_NULL_LINK) {
SetMatchLinkAndLength(prev, (U32)(link), depth_2);
}
for (size_t i = prev_st_index; i < st_index; ++i) {
tbl->tails_16[tbl->stack[i].count].prev_index = RADIX_NULL_LINK;
}
st_index = prev_st_index;
for (size_t i = 0; i < reset_count; ++i) {
tails_8[reset_list[i]].prev_index = RADIX_NULL_LINK;
}
reset_count = 0;
}
}
}
#endif
#ifdef RMF_REFERENCE
/* Simple, slow, complete parsing for reference */
static void RMF_recurseListsReference(RMF_builder* const tbl,
const BYTE* const data_block,
size_t const block_size,
size_t link,
U32 count,
U32 const max_depth)
{
/* Offset data pointer. This method is only called at depth 2 */
const BYTE* data_src = data_block + 2;
size_t limit = block_size - 2;
size_t st_index = 0;
do
{
if (link < limit) {
size_t const radix_8 = data_src[link];
size_t const prev = tbl->tails_8[radix_8].prev_index;
if (prev != RADIX_NULL_LINK) {
++tbl->tails_8[radix_8].list_count;
SetMatchLinkAndLength(prev, (U32)link, 3);
}
else {
tbl->tails_8[radix_8].list_count = 1;
tbl->stack[st_index].head = (U32)link;
tbl->stack[st_index].count = (U32)radix_8;
++st_index;
}
tbl->tails_8[radix_8].prev_index = (U32)link;
}
link = GetMatchLink(link);
} while (--count > 0);
for (size_t i = 0; i < st_index; ++i) {
tbl->stack[i].count = tbl->tails_8[tbl->stack[i].count].list_count;
}
memset(tbl->tails_8, 0xFF, sizeof(tbl->tails_8));
while (st_index > 0) {
--st_index;
U32 list_count = tbl->stack[st_index].count;
if (list_count < 2) {
/* Nothing to do */
continue;
}
if (st_index > STACK_SIZE - RADIX8_TABLE_SIZE
&& st_index > STACK_SIZE - list_count)
{
/* Potential stack overflow. Rare. */
continue;
}
link = tbl->stack[st_index].head;
/* The current depth */
U32 depth = GetMatchLength(link);
if (depth >= max_depth)
continue;
data_src = data_block + depth;
limit = block_size - depth;
/* Next depth for 1 extra char */
++depth;
size_t prev_st_index = st_index;
do {
if (link < limit) {
size_t const radix_8 = data_src[link];
size_t const prev = tbl->tails_8[radix_8].prev_index;
if (prev != RADIX_NULL_LINK) {
++tbl->tails_8[radix_8].list_count;
SetMatchLinkAndLength(prev, (U32)link, depth);
}
else {
tbl->tails_8[radix_8].list_count = 1;
tbl->stack[st_index].head = (U32)link;
tbl->stack[st_index].count = (U32)radix_8;
++st_index;
}
tbl->tails_8[radix_8].prev_index = (U32)link;
}
link = GetMatchLink(link);
} while (--list_count != 0);
for (size_t i = prev_st_index; i < st_index; ++i) {
tbl->stack[i].count = tbl->tails_8[tbl->stack[i].count].list_count;
}
memset(tbl->tails_8, 0xFF, sizeof(tbl->tails_8));
}
}
#endif /* RMF_REFERENCE */
/* Atomically take a list from the head table */
static ptrdiff_t RMF_getNextList_mt(FL2_matchTable* const tbl)
{
if (tbl->st_index < tbl->end_index) {
long pos = FL2_atomic_increment(tbl->st_index);
if (pos < tbl->end_index)
return pos;
}
return -1;
}
/* Non-atomically take a list from the head table */
static ptrdiff_t RMF_getNextList_st(FL2_matchTable* const tbl)
{
if (tbl->st_index < tbl->end_index) {
long pos = FL2_nonAtomic_increment(tbl->st_index);
if (pos < tbl->end_index)
return pos;
}
return -1;
}
/* Iterate the head table concurrently with other threads, and recurse each list until max_depth is reached */
void
#ifdef RMF_BITPACK
RMF_bitpackBuildTable
#else
RMF_structuredBuildTable
#endif
(FL2_matchTable* const tbl,
size_t const job,
unsigned const multi_thread,
FL2_dataBlock const block)
{
if (block.end == 0)
return;
unsigned const best = !tbl->params.divide_and_conquer;
unsigned const max_depth = MIN(tbl->params.depth, STRUCTURED_MAX_LENGTH) & ~1;
size_t bounded_start = max_depth + MAX_READ_BEYOND_DEPTH;
bounded_start = block.end - MIN(block.end, bounded_start);
ptrdiff_t next_progress = (job == 0) ? 0 : RADIX16_TABLE_SIZE;
ptrdiff_t(*getNextList)(FL2_matchTable* const tbl)
= multi_thread ? RMF_getNextList_mt : RMF_getNextList_st;
for (;;)
{
/* Get the next to process */
ptrdiff_t pos = getNextList(tbl);
if (pos < 0)
break;
while (next_progress < pos) {
/* initial value of next_progress ensures only thread 0 executes this */
tbl->progress += tbl->list_heads[tbl->stack[next_progress]].count;
++next_progress;
}
pos = tbl->stack[pos];
RMF_tableHead list_head = tbl->list_heads[pos];
tbl->list_heads[pos].head = RADIX_NULL_LINK;
if (list_head.count < 2 || list_head.head < block.start)
continue;
#ifdef RMF_REFERENCE
if (tbl->params.use_ref_mf) {
RMF_recurseListsReference(tbl->builders[job], block.data, block.end, list_head.head, list_head.count, max_depth);
continue;
}
#endif
if (list_head.head >= bounded_start) {
RMF_recurseListsBound(tbl->builders[job], block.data, block.end, &list_head, max_depth);
if (list_head.count < 2 || list_head.head < block.start)
continue;
}
if (best && list_head.count > tbl->builders[job]->match_buffer_limit)
{
/* Not worth buffering or too long */
RMF_recurseLists16(tbl->builders[job], block.data, block.start, block.end, list_head.head, list_head.count, max_depth);
}
else {
RMF_recurseListsBuffered(tbl->builders[job], block.data, block.start, block.end, list_head.head, 2, (BYTE)max_depth, list_head.count, 0);
}
}
}
int
#ifdef RMF_BITPACK
RMF_bitpackIntegrityCheck
#else
RMF_structuredIntegrityCheck
#endif
(const FL2_matchTable* const tbl, const BYTE* const data, size_t pos, size_t const end, unsigned max_depth)
{
max_depth &= ~1;
int err = 0;
for (pos += !pos; pos < end; ++pos) {
if (IsNull(pos))
continue;
U32 const link = GetMatchLink(pos);
if (link >= pos) {
View remainder of file in raw view
0