diff options
author | josh.macdonald <jmacd@users.noreply.github.com> | 2007-12-02 03:09:47 +0000 |
---|---|---|
committer | josh.macdonald <jmacd@users.noreply.github.com> | 2007-12-02 03:09:47 +0000 |
commit | 179ef5eef18e8dbb84f35a6356621e7c1ed7012a (patch) | |
tree | a6c8e1d4699ce858ed1fab2347bbd689dc2ad214 | |
parent | ebd9ec25c66d21dfa5c0b1f23879f59f223fe724 (diff) |
Fix an off-by-one bug lurking in the array initialization
in djw_compute_mtf_1_2
-rw-r--r-- | xdelta3/xdelta3-djw.h | 28 |
1 files changed, 17 insertions, 11 deletions
diff --git a/xdelta3/xdelta3-djw.h b/xdelta3/xdelta3-djw.h index 175add1..0235581 100644 --- a/xdelta3/xdelta3-djw.h +++ b/xdelta3/xdelta3-djw.h | |||
@@ -55,7 +55,8 @@ | |||
55 | 55 | ||
56 | #define DJW_MAX_CODELEN 20 /* Maximum length of an alphabet code. */ | 56 | #define DJW_MAX_CODELEN 20 /* Maximum length of an alphabet code. */ |
57 | 57 | ||
58 | /* [RUN_0, RUN_1, 1-DJW_MAX_CODELEN] */ | 58 | /* Code lengths are themselves code-length encoded, so the total number of |
59 | * codes is: [RUN_0, RUN_1, 1-DJW_MAX_CODELEN] */ | ||
59 | #define DJW_TOTAL_CODES (DJW_MAX_CODELEN+2) | 60 | #define DJW_TOTAL_CODES (DJW_MAX_CODELEN+2) |
60 | 61 | ||
61 | #define RUN_0 0 /* Symbols used in MTF+1/2 coding. */ | 62 | #define RUN_0 0 /* Symbols used in MTF+1/2 coding. */ |
@@ -313,6 +314,8 @@ heap_check (uint *heap, djw_heapen *ents, uint heap_last) | |||
313 | { | 314 | { |
314 | /* Heap property: child not less than parent */ | 315 | /* Heap property: child not less than parent */ |
315 | XD3_ASSERT (! heap_less (& ents[heap[i]], & ents[heap[i/2]])); | 316 | XD3_ASSERT (! heap_less (& ents[heap[i]], & ents[heap[i/2]])); |
317 | |||
318 | IF_DEBUG1 (DP(RINT "heap[%d] = %u\n", i, ents[heap[i]].freq)); | ||
316 | } | 319 | } |
317 | } | 320 | } |
318 | #endif | 321 | #endif |
@@ -398,6 +401,8 @@ djw_build_prefix (const djw_weight *freq, uint8_t *clen, int asize, int maxlen) | |||
398 | for (i = 0; i < asize; i += 1) | 401 | for (i = 0; i < asize; i += 1) |
399 | { | 402 | { |
400 | ents[i+1].freq = freq[i]; | 403 | ents[i+1].freq = freq[i]; |
404 | IF_DEBUG1 (DP(RINT "ents[%d] = freq[%d] = %d\n", | ||
405 | i+1, i, freq[i])); | ||
401 | } | 406 | } |
402 | 407 | ||
403 | again: | 408 | again: |
@@ -454,10 +459,10 @@ djw_build_prefix (const djw_weight *freq, uint8_t *clen, int asize, int maxlen) | |||
454 | h1->parent = h2->parent = ents_size; | 459 | h1->parent = h2->parent = ents_size; |
455 | 460 | ||
456 | heap_insert (heap, ents, ++heap_last, ents_size++); | 461 | heap_insert (heap, ents, ++heap_last, ents_size++); |
457 | |||
458 | IF_DEBUG (heap_check (heap, ents, heap_last)); | ||
459 | } | 462 | } |
460 | 463 | ||
464 | IF_DEBUG (heap_check (heap, ents, heap_last)); | ||
465 | |||
461 | /* Now compute prefix code lengths, counting parents. */ | 466 | /* Now compute prefix code lengths, counting parents. */ |
462 | for (i = 1; i < asize+1; i += 1) | 467 | for (i = 1; i < asize+1; i += 1) |
463 | { | 468 | { |
@@ -559,7 +564,8 @@ djw_compute_mtf_1_2 (djw_prefix *prefix, | |||
559 | usize_t mtf_i = 0; | 564 | usize_t mtf_i = 0; |
560 | int mtf_run = 0; | 565 | int mtf_run = 0; |
561 | 566 | ||
562 | memset (freq_out, 0, sizeof (freq_out[0]) * (nsym+1)); | 567 | /* This +2 is for the RUN_0, RUN_1 codes */ |
568 | memset (freq_out, 0, sizeof (freq_out[0]) * (nsym+2)); | ||
563 | 569 | ||
564 | for (i = 0; i < size; ) | 570 | for (i = 0; i < size; ) |
565 | { | 571 | { |
@@ -1339,8 +1345,8 @@ djw_build_decoder (xd3_stream *stream, | |||
1339 | { | 1345 | { |
1340 | int i, l; | 1346 | int i, l; |
1341 | const uint8_t *ci; | 1347 | const uint8_t *ci; |
1342 | uint nr_clen [DJW_MAX_CODELEN+2]; | 1348 | uint nr_clen [DJW_TOTAL_CODES]; |
1343 | uint tmp_base[DJW_MAX_CODELEN+2]; | 1349 | uint tmp_base[DJW_TOTAL_CODES]; |
1344 | int min_clen; | 1350 | int min_clen; |
1345 | int max_clen; | 1351 | int max_clen; |
1346 | 1352 | ||
@@ -1533,8 +1539,8 @@ djw_decode_1_2 (xd3_stream *stream, | |||
1533 | const uint *minlen, | 1539 | const uint *minlen, |
1534 | const uint *maxlen, | 1540 | const uint *maxlen, |
1535 | uint8_t *mtfvals, | 1541 | uint8_t *mtfvals, |
1536 | usize_t elts, | 1542 | usize_t elts, |
1537 | usize_t skip_offset, | 1543 | usize_t skip_offset, |
1538 | uint8_t *values) | 1544 | uint8_t *values) |
1539 | { | 1545 | { |
1540 | usize_t n = 0, rep = 0, mtf = 0, s = 0; | 1546 | usize_t n = 0, rep = 0, mtf = 0, s = 0; |
@@ -1608,7 +1614,7 @@ djw_decode_prefix (xd3_stream *stream, | |||
1608 | const uint *cl_minlen, | 1614 | const uint *cl_minlen, |
1609 | const uint *cl_maxlen, | 1615 | const uint *cl_maxlen, |
1610 | uint8_t *cl_mtf, | 1616 | uint8_t *cl_mtf, |
1611 | usize_t groups, | 1617 | usize_t groups, |
1612 | uint8_t *clen) | 1618 | uint8_t *clen) |
1613 | { | 1619 | { |
1614 | return djw_decode_1_2 (stream, bstate, input, input_end, | 1620 | return djw_decode_1_2 (stream, bstate, input, input_end, |
@@ -1676,8 +1682,8 @@ xd3_decode_huff (xd3_stream *stream, | |||
1676 | /* Outer scope: per-group symbol decoder tables. */ | 1682 | /* Outer scope: per-group symbol decoder tables. */ |
1677 | { | 1683 | { |
1678 | uint8_t inorder[DJW_MAX_GROUPS][ALPHABET_SIZE]; | 1684 | uint8_t inorder[DJW_MAX_GROUPS][ALPHABET_SIZE]; |
1679 | uint base [DJW_MAX_GROUPS][DJW_MAX_CODELEN+2]; | 1685 | uint base [DJW_MAX_GROUPS][DJW_TOTAL_CODES]; |
1680 | uint limit [DJW_MAX_GROUPS][DJW_MAX_CODELEN+2]; | 1686 | uint limit [DJW_MAX_GROUPS][DJW_TOTAL_CODES]; |
1681 | uint minlen [DJW_MAX_GROUPS]; | 1687 | uint minlen [DJW_MAX_GROUPS]; |
1682 | uint maxlen [DJW_MAX_GROUPS]; | 1688 | uint maxlen [DJW_MAX_GROUPS]; |
1683 | 1689 | ||