"Fossies" - the Fresh Open Source Software Archive  

Source code changes of the file "xdelta3-djw.h" between
xdelta3-3.0.11.tar.gz and xdelta3-3.1.0.tar.gz

About: xdelta is a tool and library for differential compression (supports VCDIFF encoding and decoding). Beta version.

xdelta3-djw.h  (xdelta3-3.0.11):xdelta3-djw.h  (xdelta3-3.1.0)
skipping to change at line 320 skipping to change at line 320
#if XD3_DEBUG #if XD3_DEBUG
static void static void
heap_check (usize_t *heap, djw_heapen *ents, usize_t heap_last) heap_check (usize_t *heap, djw_heapen *ents, usize_t heap_last)
{ {
usize_t i; usize_t i;
for (i = 1; i <= heap_last; i += 1) for (i = 1; i <= heap_last; i += 1)
{ {
/* Heap property: child not less than parent */ /* Heap property: child not less than parent */
XD3_ASSERT (! heap_less (& ents[heap[i]], & ents[heap[i/2]])); XD3_ASSERT (! heap_less (& ents[heap[i]], & ents[heap[i/2]]));
IF_DEBUG2 (DP(RINT "heap[%d] = %u\n", i, ents[heap[i]].freq)); IF_DEBUG2 (DP(RINT "heap[%"W"u] = %u\n", i, ents[heap[i]].freq));
} }
} }
#endif #endif
/*********************************************************************/ /*********************************************************************/
/* MTF, 1/2 */ /* MTF, 1/2 */
/*********************************************************************/ /*********************************************************************/
static inline usize_t static inline usize_t
djw_update_mtf (uint8_t *mtf, usize_t mtf_i) djw_update_mtf (uint8_t *mtf, usize_t mtf_i)
skipping to change at line 345 skipping to change at line 345
for (k = mtf_i; k != 0; k -= 1) { mtf[k] = mtf[k-1]; } for (k = mtf_i; k != 0; k -= 1) { mtf[k] = mtf[k-1]; }
mtf[0] = sym; mtf[0] = sym;
return sym; return sym;
} }
static inline void static inline void
djw_update_1_2 (int *mtf_run, usize_t *mtf_i, djw_update_1_2 (int *mtf_run, usize_t *mtf_i,
uint8_t *mtfsym, djw_weight *freq) uint8_t *mtfsym, djw_weight *freq)
{ {
int code; uint8_t code;
do do
{ {
/* Offset by 1, since any number of RUN_ symbols implies run>0... */ /* Offset by 1, since any number of RUN_ symbols implies run>0... */
*mtf_run -= 1; *mtf_run -= 1;
code = (*mtf_run & 1) ? RUN_1 : RUN_0; code = (*mtf_run & 1) ? RUN_1 : RUN_0;
mtfsym[(*mtf_i)++] = code; mtfsym[(*mtf_i)++] = code;
freq[code] += 1; freq[code] += 1;
skipping to change at line 397 skipping to change at line 397
* internal nodes, never more than ALPHABET_SIZE entries actually in the * internal nodes, never more than ALPHABET_SIZE entries actually in the
* heap (minimum weight subtrees during prefix construction). First * heap (minimum weight subtrees during prefix construction). First
* ALPHABET_SIZE entries are the actual symbols, next ALPHABET_SIZE-1 are * ALPHABET_SIZE entries are the actual symbols, next ALPHABET_SIZE-1 are
* internal nodes. */ * internal nodes. */
djw_heapen ents[ALPHABET_SIZE * 2]; djw_heapen ents[ALPHABET_SIZE * 2];
usize_t heap[ALPHABET_SIZE + 1]; usize_t heap[ALPHABET_SIZE + 1];
usize_t heap_last; /* Index of the last _valid_ heap entry. */ usize_t heap_last; /* Index of the last _valid_ heap entry. */
usize_t ents_size; /* Number of entries, including 0th fake entry */ usize_t ents_size; /* Number of entries, including 0th fake entry */
usize_t overflow; /* Number of code lengths that overflow */ usize_t overflow; /* Number of code lengths that overflow */
uint32_t total_bits; usize_t total_bits;
usize_t i; usize_t i;
IF_DEBUG (uint32_t first_bits = 0); IF_DEBUG (usize_t first_bits = 0);
/* Insert real symbol frequences. */ /* Insert real symbol frequences. */
for (i = 0; i < asize; i += 1) for (i = 0; i < asize; i += 1)
{ {
ents[i+1].freq = freq[i]; ents[i+1].freq = freq[i];
IF_DEBUG2 (DP(RINT "ents[%d] = freq[%d] = %d\n", IF_DEBUG2 (DP(RINT "ents[%"W"i] = freq[%"W"u] = %d\n",
i+1, i, freq[i])); i+1, i, freq[i]));
} }
again: again:
/* The loop is re-entered each time an overflow occurs. Re-initialize... */ /* The loop is re-entered each time an overflow occurs. Re-initialize... */
heap_last = 0; heap_last = 0;
ents_size = 1; ents_size = 1;
overflow = 0; overflow = 0;
total_bits = 0; total_bits = 0;
skipping to change at line 446 skipping to change at line 446
IF_DEBUG (heap_check (heap, ents, heap_last)); IF_DEBUG (heap_check (heap, ents, heap_last));
/* Must be at least one symbol, or else we can't get here. */ /* Must be at least one symbol, or else we can't get here. */
XD3_ASSERT (heap_last != 0); XD3_ASSERT (heap_last != 0);
/* If there is only one symbol, fake a second to prevent zero-length /* If there is only one symbol, fake a second to prevent zero-length
* codes. */ * codes. */
if (heap_last == 1) if (heap_last == 1)
{ {
/* Pick either the first or last symbol. */ /* Pick either the first or last symbol. */
int s = freq[0] ? asize-1 : 0; usize_t s = freq[0] ? asize-1 : 0;
ents[s+1].freq = 1; ents[s+1].freq = 1;
goto again; goto again;
} }
/* Build prefix tree. */ /* Build prefix tree. */
while (heap_last > 1) while (heap_last > 1)
{ {
djw_heapen *h1 = heap_extract (heap, ents, --heap_last); djw_heapen *h1 = heap_extract (heap, ents, --heap_last);
djw_heapen *h2 = heap_extract (heap, ents, --heap_last); djw_heapen *h2 = heap_extract (heap, ents, --heap_last);
skipping to change at line 485 skipping to change at line 485
usize_t p = i; usize_t p = i;
while ((p = ents[p].parent) != 0) { b += 1; } while ((p = ents[p].parent) != 0) { b += 1; }
if (b > maxlen) { overflow = 1; } if (b > maxlen) { overflow = 1; }
total_bits += b * freq[i-1]; total_bits += b * freq[i-1];
} }
/* clen is 0-origin, unlike ents. */ /* clen is 0-origin, unlike ents. */
IF_DEBUG2 (DP(RINT "clen[%d] = %d\n", i-1, b)); IF_DEBUG2 (DP(RINT "clen[%"W"u] = %"W"u\n", i-1, b));
clen[i-1] = b; clen[i-1] = b;
} }
IF_DEBUG (if (first_bits == 0) first_bits = total_bits); IF_DEBUG (if (first_bits == 0) first_bits = total_bits);
if (! overflow) if (! overflow)
{ {
IF_DEBUG2 (if (first_bits != total_bits) IF_DEBUG2 (if (first_bits != total_bits)
{ {
DP(RINT "code length overflow changed %u bits\n", DP(RINT "code length overflow changed %"W"u bits\n",
(usize_t)(total_bits - first_bits)); total_bits - first_bits);
}); });
return total_bits; return total_bits;
} }
/* OPT: There is a non-looping way to fix overflow shown in zlib, but this /* OPT: There is a non-looping way to fix overflow shown in zlib, but this
* is easier (for now), as done in bzip2. */ * is easier (for now), as done in bzip2. */
for (i = 1; i < asize+1; i += 1) for (i = 1; i < asize+1; i += 1)
{ {
ents[i].freq = ents[i].freq / 2 + 1; ents[i].freq = ents[i].freq / 2 + 1;
} }
skipping to change at line 549 skipping to change at line 549
codes[i] = code++; codes[i] = code++;
} }
} }
code <<= 1; code <<= 1;
} }
IF_DEBUG2 ({ IF_DEBUG2 ({
for (i = 0; i < asize; i += 1) for (i = 0; i < asize; i += 1)
{ {
DP(RINT "code[%d] = %u\n", i, codes[i]); DP(RINT "code[%"W"u] = %"W"u\n", i, codes[i]);
} }
}); });
} }
/*********************************************************************/ /*********************************************************************/
/* MOVE-TO-FRONT */ /* MOVE-TO-FRONT */
/*********************************************************************/ /*********************************************************************/
static void static void
djw_compute_mtf_1_2 (djw_prefix *prefix, djw_compute_mtf_1_2 (djw_prefix *prefix,
uint8_t *mtf, uint8_t *mtf,
skipping to change at line 1023 skipping to change at line 1023
djw_weight goal = left / (groups - gp); djw_weight goal = left / (groups - gp);
IF_DEBUG2 (usize_t nz = 0); IF_DEBUG2 (usize_t nz = 0);
/* Due to the single-code granularity of this distribution, it may /* Due to the single-code granularity of this distribution, it may
* be that we can't generate a distribution for each group. In that * be that we can't generate a distribution for each group. In that
* case subtract one group and try again. If (inefficient), we're * case subtract one group and try again. If (inefficient), we're
* testing group behavior, so don't mess things up. */ * testing group behavior, so don't mess things up. */
if (goal == 0 && !cfg->inefficient) if (goal == 0 && !cfg->inefficient)
{ {
IF_DEBUG2 (DP(RINT "too many groups (%u), dropping one\n", IF_DEBUG2 (DP(RINT "too many groups (%"W"u), dropping one\n",
groups)); groups));
groups -= 1; groups -= 1;
goto regroup; goto regroup;
} }
/* Sum == goal is possible when (cfg->inefficient)... */ /* Sum == goal is possible when (cfg->inefficient)... */
while (sum < goal) while (sum < goal)
{ {
XD3_ASSERT (sym2 < ALPHABET_SIZE); XD3_ASSERT (sym2 < ALPHABET_SIZE);
IF_DEBUG2 (nz += real_freq[sym2] != 0); IF_DEBUG2 (nz += real_freq[sym2] != 0);
sum += real_freq[sym2++]; sum += real_freq[sym2++];
} }
IF_DEBUG2(DP(RINT "group %u has symbols %u..%u (%u non-zero) " IF_DEBUG2(DP(RINT "group %"W"u has symbols %"W"u..%"W"u (%"W"u non-zero
"(%u/%u = %.3f)\n", ) "
"(%u/%"W"u = %.3f)\n",
gp, sym1, sym2, nz, sum, gp, sym1, sym2, nz, sum,
input_bytes, sum / (double)input_bytes);); input_bytes, sum / (double)input_bytes););
for (s = 0; s < ALPHABET_SIZE; s += 1) for (s = 0; s < ALPHABET_SIZE; s += 1)
{ {
evolve_clen[gp][s] = (s >= sym1 && s <= sym2) ? 1 : 16; evolve_clen[gp][s] = (s >= sym1 && s <= sym2) ? 1 : 16;
} }
left -= sum; left -= sum;
sym1 = sym2+1; sym1 = sym2+1;
skipping to change at line 1167 skipping to change at line 1167
* for the (output_bits==0) assert after all bits are output. */ * for the (output_bits==0) assert after all bits are output. */
if (any_zeros) if (any_zeros)
{ {
IF_DEBUG2 (usize_t save_total = output_bits); IF_DEBUG2 (usize_t save_total = output_bits);
for (i = 0; i < ALPHABET_SIZE; i += 1) for (i = 0; i < ALPHABET_SIZE; i += 1)
{ {
if (evolve_zero[i]) { output_bits -= evolve_clen[gp][i]; } if (evolve_zero[i]) { output_bits -= evolve_clen[gp][i]; }
} }
IF_DEBUG2 (DP(RINT "evolve_zero reduced %u bits in group %u\n", IF_DEBUG2 (DP(RINT "evolve_zero reduced %"W"u bits in group %"W"u\n ",
save_total - output_bits, gp)); save_total - output_bits, gp));
} }
} }
IF_DEBUG2( IF_DEBUG2(
DP(RINT "pass %u total bits: %u group uses: ", niter, output_bits); DP(RINT "pass %"W"u total bits: %"W"u group uses: ", niter, output_bits);
for (gp = 0; gp < groups; gp += 1) { DP(RINT "%u ", gcount[gp]); } for (gp = 0; gp < groups; gp += 1) { DP(RINT "%"W"u ", gcount[gp]); }
DP(RINT "\n"); DP(RINT "\n");
); );
/* End iteration. */ /* End iteration. */
IF_DEBUG2 (if (niter > 1 && best_bits < output_bits) { IF_DEBUG2 (if (niter > 1 && best_bits < output_bits) {
DP(RINT "iteration lost %u bits\n", output_bits - best_bits); }); DP(RINT "iteration lost %"W"u bits\n", output_bits - best_bits); });
if (niter == 1 || (niter < DJW_MAX_ITER && if (niter == 1 || (niter < DJW_MAX_ITER &&
(best_bits - output_bits) >= DJW_MIN_IMPROVEMENT)) (best_bits - output_bits) >= DJW_MIN_IMPROVEMENT))
{ {
best_bits = output_bits; best_bits = output_bits;
goto repeat; goto repeat;
} }
/* Efficiency check. */ /* Efficiency check. */
if (output_bits + EFFICIENCY_BITS >= input_bits && ! cfg->inefficient) if (output_bits + EFFICIENCY_BITS >= input_bits && ! cfg->inefficient)
{ {
goto nosecond; goto nosecond;
} }
IF_DEBUG2 (DP(RINT "djw compression: %u -> %0.3f\n", IF_DEBUG2 (DP(RINT "djw compression: %"W"u -> %0.3f\n",
input_bytes, output_bits / 8.0)); input_bytes, output_bits / 8.0));
/* Encode: prefix */ /* Encode: prefix */
{ {
uint8_t prefix_symbol[DJW_MAX_GROUPS * ALPHABET_SIZE]; uint8_t prefix_symbol[DJW_MAX_GROUPS * ALPHABET_SIZE];
uint8_t prefix_mtfsym[DJW_MAX_GROUPS * ALPHABET_SIZE]; uint8_t prefix_mtfsym[DJW_MAX_GROUPS * ALPHABET_SIZE];
uint8_t prefix_repcnt[DJW_MAX_GROUPS * ALPHABET_SIZE]; uint8_t prefix_repcnt[DJW_MAX_GROUPS * ALPHABET_SIZE];
djw_prefix prefix; djw_prefix prefix;
prefix.symbol = prefix_symbol; prefix.symbol = prefix_symbol;
skipping to change at line 1473 skipping to change at line 1473
} }
done: done:
if (base[bits] <= code) if (base[bits] <= code)
{ {
usize_t offset = code - base[bits]; usize_t offset = code - base[bits];
if (offset <= max_sym) if (offset <= max_sym)
{ {
IF_DEBUG2 (DP(RINT "(j) %u ", code)); IF_DEBUG2 (DP(RINT "(j) %"W"u ", code));
*sym = inorder[offset]; *sym = inorder[offset];
return 0; return 0;
} }
} }
corrupt: corrupt:
stream->msg = "secondary decoder invalid code"; stream->msg = "secondary decoder invalid code";
return XD3_INVALID_INPUT; return XD3_INVALID_INPUT;
} }
 End of changes. 16 change blocks. 
19 lines changed or deleted 20 lines changed or added

Home  |  About  |  All  |  Newest  |  Fossies Dox  |  Screenshots  |  Comments  |  Imprint  |  Privacy  |  HTTPS