* it possible to implement this code:
*
* - divsufsort (author: Yuta Mori), for the suffix array construction code,
- * located in a separate directory (divsufsort/).
+ * located in a separate file (divsufsort.c).
*
* - "Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its
* Applications" (Kasai et al. 2001), for the LCP array computation.
/* Codewords for the LZX main, length, and aligned offset Huffman codes */
struct lzx_codewords {
- u16 main[LZX_MAINCODE_MAX_NUM_SYMBOLS];
- u16 len[LZX_LENCODE_NUM_SYMBOLS];
- u16 aligned[LZX_ALIGNEDCODE_NUM_SYMBOLS];
+ u32 main[LZX_MAINCODE_MAX_NUM_SYMBOLS];
+ u32 len[LZX_LENCODE_NUM_SYMBOLS];
+ u32 aligned[LZX_ALIGNEDCODE_NUM_SYMBOLS];
};
/* Codeword lengths (in bits) for the LZX main, length, and aligned offset
* MIN_MATCH_LEN. */
if (match_len_minus_2 < LZX_NUM_PRIMARY_LENS) {
len_header = match_len_minus_2;
- /* No length footer-- mark it with a special
- * value. */
- len_footer = (unsigned)(-1);
} else {
len_header = LZX_NUM_PRIMARY_LENS;
len_footer = match_len_minus_2 - LZX_NUM_PRIMARY_LENS;
/* If there is a length footer, output it using the
* length Huffman code. */
- if (len_footer != (unsigned)(-1)) {
+ if (len_header == LZX_NUM_PRIMARY_LENS)
bitstream_put_bits(out, codes->codewords.len[len_footer],
codes->lens.len[len_footer]);
- }
num_extra_bits = lzx_get_num_extra_bits(position_slot);
input_idx_t precode_freqs[restrict LZX_PRECODE_NUM_SYMBOLS],
u8 output_syms[restrict num_syms],
u8 precode_lens[restrict LZX_PRECODE_NUM_SYMBOLS],
- u16 precode_codewords[restrict LZX_PRECODE_NUM_SYMBOLS],
+ u32 precode_codewords[restrict LZX_PRECODE_NUM_SYMBOLS],
unsigned *num_additional_bits_ret)
{
memset(precode_freqs, 0,
input_idx_t precode_freqs[LZX_PRECODE_NUM_SYMBOLS];
u8 output_syms[num_syms];
u8 precode_lens[LZX_PRECODE_NUM_SYMBOLS];
- u16 precode_codewords[LZX_PRECODE_NUM_SYMBOLS];
+ u32 precode_codewords[LZX_PRECODE_NUM_SYMBOLS];
unsigned i;
unsigned num_output_syms;
u8 precode_sym;
unsigned orig_window_pos = spec->window_pos;
unsigned orig_cached_pos = ctx->cached_matches_pos;
+ unsigned num_passes_remaining = num_passes;
LZX_ASSERT(ctx->match_window_pos == spec->window_pos);
/* The first optimal parsing pass is done using the cost model already
* set in ctx->costs. Each later pass is done using a cost model
* computed from the previous pass. */
- for (unsigned pass = 0; pass < num_passes; pass++) {
+ do {
+ --num_passes_remaining;
ctx->match_window_pos = orig_window_pos;
ctx->cached_matches_pos = orig_cached_pos;
spec->num_chosen_matches = 0;
memset(&freqs, 0, sizeof(freqs));
- for (unsigned i = spec->window_pos; i < spec->window_pos + spec->block_size; ) {
+ const u8 *window_ptr = &ctx->window[spec->window_pos];
+ const u8 *window_end = &window_ptr[spec->block_size];
+ struct lzx_match *next_chosen_match =
+ &ctx->chosen_matches[spec->chosen_matches_start_pos];
+
+ while (window_ptr != window_end) {
struct raw_match raw_match;
struct lzx_match lzx_match;
* null value and therefore cannot
* generate such matches. */
BUILD_BUG_ON(LZX_MIN_MATCH_LEN != 2);
- lzx_match.data = lzx_tally_literal(ctx->window[i],
+ lzx_match.data = lzx_tally_literal(*window_ptr++,
&freqs);
- i += 1;
- ctx->chosen_matches[spec->chosen_matches_start_pos +
- spec->num_chosen_matches++]
- = lzx_match;
- lzx_match.data = lzx_tally_literal(ctx->window[i],
+ *next_chosen_match++ = lzx_match;
+ lzx_match.data = lzx_tally_literal(*window_ptr++,
&freqs);
- i += 1;
} else {
lzx_match.data = lzx_tally_match(raw_match.len,
raw_match.offset,
&freqs,
&ctx->queue);
- i += raw_match.len;
+ window_ptr += raw_match.len;
}
} else {
- lzx_match.data = lzx_tally_literal(ctx->window[i], &freqs);
- i += 1;
+ lzx_match.data = lzx_tally_literal(*window_ptr++, &freqs);
}
- ctx->chosen_matches[spec->chosen_matches_start_pos +
- spec->num_chosen_matches++] = lzx_match;
+ *next_chosen_match++ = lzx_match;
}
+ spec->num_chosen_matches = next_chosen_match -
+ &ctx->chosen_matches[spec->chosen_matches_start_pos];
lzx_make_huffman_codes(&freqs, &spec->codes,
ctx->num_main_syms);
- if (pass < num_passes - 1)
+ if (num_passes_remaining)
lzx_set_costs(ctx, &spec->codes.lens);
ctx->matches_cached = true;
- }
+ } while (num_passes_remaining);
+
spec->block_type = lzx_choose_verbatim_or_aligned(&freqs, &spec->codes);
ctx->matches_cached = false;
}
* Although this could be disabled by default in all cases, it only
* takes around 2-3% of the running time of the slow algorithm to do the
* verification. */
-#if defined(ENABLE_LZX_DEBUG) || defined(ENABLE_VERIFY_COMPRESSION)
+ if (ctx->params.algorithm == WIMLIB_LZX_ALGORITHM_SLOW
+ #if defined(ENABLE_LZX_DEBUG) || defined(ENABLE_VERIFY_COMPRESSION)
+ || 1
+ #endif
+ )
{
struct wimlib_decompressor *decompressor;
"data verification!");
}
}
-#endif
return compressed_size;
}