Patches attached.
I also tried to sort equal length codes in such a way that codes that
start and end with 1 bits are paired with values that occur less
frequently as suggested by Michael in
https://ffmpeg.org/pipermail/ffmpeg-devel/2025-April/341917.html. Yet
strangely this worsened compression (for the majority of the fate tests
affected by it). The patch can be found here:
https://github.com/mkver/FFmpeg/commits/mjpegenc_huffman/
- Andreas
From f3b4ebdc0ed2198e68f92a79bb5509fac4c42c01 Mon Sep 17 00:00:00 2001
From: Andreas Rheinhardt <andreas.rheinha...@outlook.com>
Date: Mon, 14 Apr 2025 20:39:53 +0200
Subject: [PATCH 1/3] avcodec/tests/mjpegenc_huffman: Also test length counts
This is better than just testing that the tree is not overdetermined.
Signed-off-by: Andreas Rheinhardt <andreas.rheinha...@outlook.com>
---
libavcodec/tests/mjpegenc_huffman.c | 48 ++++++++++++++++++++++-------
1 file changed, 37 insertions(+), 11 deletions(-)
diff --git a/libavcodec/tests/mjpegenc_huffman.c b/libavcodec/tests/mjpegenc_huffman.c
index 39ad10c454..4f94dd99dc 100644
--- a/libavcodec/tests/mjpegenc_huffman.c
+++ b/libavcodec/tests/mjpegenc_huffman.c
@@ -31,15 +31,16 @@
#include "libavcodec/mjpegenc_huffman.c"
// Validate the computed lengths satisfy the JPEG restrictions and is optimal.
-static int check_lengths(int L, int expected_length,
- const int *probs, int nprobs)
+static int check_lengths(int L, const int *probs, int nprobs,
+ int expected_length, const uint8_t expected_len_counts[/* L + 1 */])
{
HuffTable lengths[256];
PTable val_counts[256];
+ uint8_t len_counts[17] = { 0 };
int actual_length = 0, i, j, k, prob, length;
int ret = 0;
- double cantor_measure = 0;
av_assert0(nprobs <= 256);
+ av_assert0(L < FF_ARRAY_ELEMS(len_counts));
for (i = 0; i < nprobs; i++) {
val_counts[i] = (PTable){.value = i, .prob = probs[i]};
@@ -47,6 +48,26 @@ static int check_lengths(int L, int expected_length,
mjpegenc_huffman_compute_bits(val_counts, lengths, nprobs, L);
+ for (int i = 0; i < nprobs; ++i) {
+ if (lengths[i].length > L) {
+ fprintf(stderr,
+ "Len %d of element %d of Huffman table with %d elements exceeds max length %d\n",
+ lengths[i].length, i, nprobs, L);
+ return 1;
+ }
+ len_counts[lengths[i].length]++;
+ }
+ // Test that the lengths can be made part of a complete, prefix-free tree:
+ unsigned code = 0;
+ for (int i = 1; i <= L; ++i) {
+ code <<= 1;
+ code += len_counts[i];
+ }
+ if (code > 1U << L) {
+ fprintf(stderr, "Huffman tree overdetermined/invalid\n");
+ ret = 1;
+ }
+
for (i = 0; i < nprobs; i++) {
// Find the value's prob and length
for (j = 0; j < nprobs; j++)
@@ -59,22 +80,18 @@ static int check_lengths(int L, int expected_length,
if (prob) {
actual_length += prob * length;
- cantor_measure += 1. / (1 << length);
}
if (length > L || length < 1) return 1;
}
- // Check that the codes can be prefix-free.
- if (cantor_measure > 1) ret = 1;
// Check that the total length is optimal
if (actual_length != expected_length) ret = 1;
if (ret == 1) {
fprintf(stderr,
- "Cantor measure: %f\n"
"Actual length: %d\n"
"Expected length: %d\n",
- cantor_measure, actual_length, expected_length);
+ actual_length, expected_length);
}
return ret;
@@ -83,6 +100,9 @@ static int check_lengths(int L, int expected_length,
static const int probs_zeroes[] = {
6, 6, 0, 0, 0
};
+static const uint8_t len_counts_zeroes[] = {
+ 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2,
+};
static const int probs_skewed[] = {
2, 0, 0, 0, 0, 1, 0, 0, 20, 0, 2, 0, 10, 5, 1, 1, 9, 1, 1, 6, 0, 5, 0, 1, 0, 7, 6,
@@ -96,6 +116,9 @@ static const int probs_skewed[] = {
0, 3, 0, 0, 28, 0, 2, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 23, 0, 0, 0, 0,
0, 21, 1, 0, 3, 24, 2, 0, 0, 7, 0, 0, 1, 5, 1, 2, 0, 5
};
+static const uint8_t len_counts_skewed[] = {
+ 0, 1, 0, 0, 1, 2, 7, 11, 18, 31, 28, 40, 0, 1, 0, 0, 116,
+};
static const int probs_sat[] = {
74, 8, 14, 7, 9345, 40, 0, 2014, 2, 1, 115, 0, 2, 1, 194, 388, 20, 0, 0, 2, 1, 121,
@@ -110,6 +133,9 @@ static const int probs_sat[] = {
0, 1085, 0, 0, 0, 3, 489, 36, 1, 0, 1, 9420, 294, 28, 0, 57, 5, 0, 9, 2, 0, 1, 2,
2, 0, 0, 9, 2, 29, 2, 2, 7, 0, 5, 490, 0, 7, 5, 0, 1, 8, 0, 0, 23255, 0, 1
};
+static const uint8_t len_counts_sat[] = {
+ 0, 1, 0, 2, 1, 2, 2, 5, 5, 7, 7, 8, 17, 23, 16, 24, 136,
+};
// Test the example given on @see
// http://guru.multimedia.cx/small-tasks-for-ffmpeg/
@@ -154,13 +180,13 @@ int main(int argc, char **argv)
}
// Check handling of zero probabilities
- if (check_lengths(16, 18, probs_zeroes, FF_ARRAY_ELEMS(probs_zeroes)))
+ if (check_lengths(16, probs_zeroes, FF_ARRAY_ELEMS(probs_zeroes), 18, len_counts_zeroes))
ret = 1;
// Check skewed distribution over 256 without saturated lengths
- if (check_lengths(16, 41282, probs_skewed, FF_ARRAY_ELEMS(probs_skewed)))
+ if (check_lengths(16, probs_skewed, FF_ARRAY_ELEMS(probs_skewed), 41282, len_counts_skewed))
ret = 1;
// Check skewed distribution over 256 with saturated lengths
- if (check_lengths(16, 669904, probs_sat, FF_ARRAY_ELEMS(probs_sat)))
+ if (check_lengths(16, probs_sat, FF_ARRAY_ELEMS(probs_sat), 669904, len_counts_sat))
ret = 1;
return ret;
--
2.45.2
From 750d900ada59fc71645df2b1ddb8e7c2ef02bb6e Mon Sep 17 00:00:00 2001
From: Andreas Rheinhardt <andreas.rheinha...@outlook.com>
Date: Wed, 2 Apr 2025 15:06:43 +0200
Subject: [PATCH 2/3] avcodec/mjpegenc_huffman: Avoid AV_QSORT to sort entries
by length
It is unnecessary, as we already have the entries sorted by
probability and therefore implicitly by length. All we need
on top of that to build the tree is the number of entries
of a given length.
Doing so gives a 3.6% speedup of ff_mjpeg_encode_huffman_close()
here; it also saves about 640B of .text here.
The new code puts values with higher probability to the left
of the tree. The old code did not and therefore
the FATE checksums needed to be updated. Due to MJPEG's
0xFF unescaping file sizes as well as file checksums
needed to be updated; the decoded picture hashes stayed
the same. Given that codes on the left of the tree have
on average fewer bits set than codes on the right, the
file sizes mostly improve (all except vsynth3-mjpeg-444).
Signed-off-by: Andreas Rheinhardt <andreas.rheinha...@outlook.com>
---
libavcodec/mjpegenc_huffman.c | 64 ++++-------
libavcodec/tests/mjpegenc_huffman.c | 103 ++++++++++--------
tests/ref/fate/jpg-icc | 6 +-
tests/ref/lavf/jpg | 4 +-
tests/ref/lavf/smjpeg | 4 +-
tests/ref/seek/lavf-jpg | 8 +-
tests/ref/vsynth/vsynth1-mjpeg-422 | 4 +-
tests/ref/vsynth/vsynth1-mjpeg-444 | 4 +-
tests/ref/vsynth/vsynth1-mjpeg-huffman | 4 +-
tests/ref/vsynth/vsynth1-mjpeg-trell-huffman | 4 +-
tests/ref/vsynth/vsynth2-mjpeg-422 | 4 +-
tests/ref/vsynth/vsynth2-mjpeg-444 | 4 +-
tests/ref/vsynth/vsynth2-mjpeg-huffman | 4 +-
tests/ref/vsynth/vsynth2-mjpeg-trell-huffman | 4 +-
tests/ref/vsynth/vsynth3-mjpeg-422 | 4 +-
tests/ref/vsynth/vsynth3-mjpeg-444 | 4 +-
tests/ref/vsynth/vsynth3-mjpeg-huffman | 4 +-
tests/ref/vsynth/vsynth3-mjpeg-trell-huffman | 2 +-
tests/ref/vsynth/vsynth_lena-mjpeg-422 | 4 +-
tests/ref/vsynth/vsynth_lena-mjpeg-444 | 4 +-
tests/ref/vsynth/vsynth_lena-mjpeg-huffman | 4 +-
.../vsynth/vsynth_lena-mjpeg-trell-huffman | 4 +-
22 files changed, 118 insertions(+), 133 deletions(-)
diff --git a/libavcodec/mjpegenc_huffman.c b/libavcodec/mjpegenc_huffman.c
index 2556959132..7fd63a2569 100644
--- a/libavcodec/mjpegenc_huffman.c
+++ b/libavcodec/mjpegenc_huffman.c
@@ -43,14 +43,6 @@ typedef struct PackageMergerList {
int items[257 * 16]; ///< chain of all individual values that make up items A, B, A, B, C, A, B, C, D, C, D, D, E
} PackageMergerList;
-/**
- * Used to store optimal huffman encoding results
- */
-typedef struct HuffTable {
- int code; ///< code is the input value
- int length; ///< length of the encoding
-} HuffTable;
-
/**
* Comparison function for two PTables by prob
*
@@ -65,20 +57,6 @@ static int compare_by_prob(const void *a, const void *b)
return a_val.prob - b_val.prob;
}
-/**
- * Comparison function for two HuffTables by length
- *
- * @param a First HuffTable to compare
- * @param b Second HuffTable to compare
- * @return < 0 for less than, 0 for equals, > 0 for greater than
- */
-static int compare_by_length(const void *a, const void *b)
-{
- HuffTable a_val = *(HuffTable *) a;
- HuffTable b_val = *(HuffTable *) b;
- return a_val.length - b_val.length;
-}
-
/**
* Computes the length of the Huffman encoding for each distinct input value.
* Uses package merge algorithm as follows:
@@ -92,15 +70,16 @@ static int compare_by_length(const void *a, const void *b)
* 8. the length of the huffman code for symbol s will be equal to the number of times the symbol occurs in the select elements
* Go to guru.multimedia.cx/small-tasks-for-ffmpeg/ for more details
*
- * All probabilities should be positive integers. The output is sorted by code,
- * not by length.
+ * All probabilities should be nonnegative integers.
*
- * @param prob_table input array of a PTable for each distinct input value
- * @param distincts output array of a HuffTable that will be populated by this function
- * @param size size of the prob_table array
- * @param max_length max length of an encoding
+ * @param prob_table[in,out] array of a PTable for each distinct input value,
+ * will be sorted according to ascending probability
+ * @param counts[out] the number of values of a given length
+ * @param size number of elements of the prob_table array
+ * @param max_length max length of a code
*/
-static void mjpegenc_huffman_compute_bits(PTable *prob_table, HuffTable *distincts,
+static void mjpegenc_huffman_compute_bits(PTable *prob_table,
+ uint8_t counts[/* max_length + 1 */],
int size, int max_length)
{
PackageMergerList list_a, list_b, *to = &list_a, *from = &list_b, *temp;
@@ -159,14 +138,9 @@ static void mjpegenc_huffman_compute_bits(PTable *prob_table, HuffTable *distinc
}
// we don't want to return the 256 bit count (it was just in here to prevent
// all 1s encoding)
- j = 0;
- for (i = 0; i < 256; i++) {
- if (nbits[i] > 0) {
- distincts[j].code = i;
- distincts[j].length = nbits[i];
- j++;
- }
- }
+ memset(counts, 0, sizeof(counts[0]) * (max_length + 1));
+ for (int i = 0; i < 256; ++i)
+ counts[nbits[i]]++;
}
void ff_mjpeg_encode_huffman_init(MJpegEncHuffmanContext *s)
@@ -186,7 +160,6 @@ void ff_mjpeg_encode_huffman_close(MJpegEncHuffmanContext *s, uint8_t bits[17],
uint8_t val[], int max_nval)
{
PTable val_counts[257];
- HuffTable distincts[256];
av_assert1(max_nval <= FF_ARRAY_ELEMS(val_counts) - 1);
@@ -201,12 +174,13 @@ void ff_mjpeg_encode_huffman_close(MJpegEncHuffmanContext *s, uint8_t bits[17],
}
val_counts[nval].value = 256;
val_counts[nval].prob = 0;
- mjpegenc_huffman_compute_bits(val_counts, distincts, nval + 1, 16);
- AV_QSORT(distincts, nval, HuffTable, compare_by_length);
- memset(bits, 0, sizeof(bits[0]) * 17);
- for (int i = 0; i < nval; i++) {
- val[i] = distincts[i].code;
- bits[distincts[i].length]++;
- }
+ mjpegenc_huffman_compute_bits(val_counts, bits, nval + 1, 16);
+
+ // val_counts[0] is the fake element we added earlier.
+ av_assert1(val_counts[0].prob == 0 && val_counts[0].value == 256);
+ // The following loop puts the values with higher occurence first,
+ // ensuring that they get the shorter codes.
+ for (int i = 0; i < nval; ++i)
+ val[i] = val_counts[nval - i].value;
}
diff --git a/libavcodec/tests/mjpegenc_huffman.c b/libavcodec/tests/mjpegenc_huffman.c
index 4f94dd99dc..9cc5d9b506 100644
--- a/libavcodec/tests/mjpegenc_huffman.c
+++ b/libavcodec/tests/mjpegenc_huffman.c
@@ -34,10 +34,9 @@
static int check_lengths(int L, const int *probs, int nprobs,
int expected_length, const uint8_t expected_len_counts[/* L + 1 */])
{
- HuffTable lengths[256];
PTable val_counts[256];
- uint8_t len_counts[17] = { 0 };
- int actual_length = 0, i, j, k, prob, length;
+ uint8_t len_counts[17];
+ int actual_length = 0, i;
int ret = 0;
av_assert0(nprobs <= 256);
av_assert0(L < FF_ARRAY_ELEMS(len_counts));
@@ -46,20 +45,12 @@ static int check_lengths(int L, const int *probs, int nprobs,
val_counts[i] = (PTable){.value = i, .prob = probs[i]};
}
- mjpegenc_huffman_compute_bits(val_counts, lengths, nprobs, L);
+ mjpegenc_huffman_compute_bits(val_counts, len_counts, nprobs, L);
- for (int i = 0; i < nprobs; ++i) {
- if (lengths[i].length > L) {
- fprintf(stderr,
- "Len %d of element %d of Huffman table with %d elements exceeds max length %d\n",
- lengths[i].length, i, nprobs, L);
- return 1;
- }
- len_counts[lengths[i].length]++;
- }
// Test that the lengths can be made part of a complete, prefix-free tree:
- unsigned code = 0;
+ unsigned code = 0, count = 0;
for (int i = 1; i <= L; ++i) {
+ count += len_counts[i];
code <<= 1;
code += len_counts[i];
}
@@ -67,22 +58,36 @@ static int check_lengths(int L, const int *probs, int nprobs,
fprintf(stderr, "Huffman tree overdetermined/invalid\n");
ret = 1;
}
-
- for (i = 0; i < nprobs; i++) {
- // Find the value's prob and length
- for (j = 0; j < nprobs; j++)
- if (val_counts[j].value == i) break;
- for (k = 0; k < nprobs; k++)
- if (lengths[k].code == i) break;
- if (!(j < nprobs && k < nprobs)) return 1;
- prob = val_counts[j].prob;
- length = lengths[k].length;
-
- if (prob) {
- actual_length += prob * length;
+ if (count != nprobs) {
+ fprintf(stderr, "Total count %u does not match expected value %d\n",
+ count, nprobs);
+ ret = 1;
+ }
+ // Test that the input values have been properly ordered.
+ for (unsigned i = 0; i < count; ++i) {
+ if (val_counts[i].prob != probs[val_counts[i].value]) {
+ fprintf(stderr, "PTable not properly reordered\n");
+ ret = 1;
+ }
+ if (i && val_counts[i - 1].prob > val_counts[i].prob) {
+ fprintf(stderr, "PTable not order ascendingly: [%u] = %d > [%u] = %d\n",
+ i - 1, val_counts[i - 1].prob, i, val_counts[i].prob);
+ ret = 1;
+ }
+ unsigned j;
+ for (j = 0; j < count; ++j)
+ if (val_counts[j].value == i)
+ break;
+ if (j >= count) {
+ fprintf(stderr, "Element %u missing after sorting\n", i);
+ ret = 1;
}
-
- if (length > L || length < 1) return 1;
+ }
+ for (int len = L, j = 0; len; --len) {
+ int prob = 0;
+ for (int end = j + len_counts[len]; j < end; ++j)
+ prob += val_counts[j].prob;
+ actual_length += prob * len;
}
// Check that the total length is optimal
if (actual_length != expected_length) ret = 1;
@@ -141,7 +146,10 @@ static const uint8_t len_counts_sat[] = {
// http://guru.multimedia.cx/small-tasks-for-ffmpeg/
int main(int argc, char **argv)
{
- int i, ret = 0;
+ enum {
+ MAX_LEN = 3,
+ };
+ int ret = 0;
// Probabilities of symbols 0..4
PTable val_counts[] = {
{.value = 0, .prob = 1},
@@ -151,30 +159,33 @@ int main(int argc, char **argv)
{.value = 4, .prob = 21},
};
// Expected code lengths for each symbol
- static const HuffTable expected[] = {
- {.code = 0, .length = 3},
- {.code = 1, .length = 3},
- {.code = 2, .length = 3},
- {.code = 3, .length = 3},
- {.code = 4, .length = 1},
+ static const uint8_t expected[MAX_LEN + 1] = {
+ [1] = 1, [3] = 4,
};
// Actual code lengths
- HuffTable distincts[5];
+ uint8_t len_counts[MAX_LEN + 1];
// Build optimal huffman tree using an internal function, to allow for
// smaller-than-normal test cases. This mutates val_counts by sorting.
- mjpegenc_huffman_compute_bits(val_counts, distincts,
- FF_ARRAY_ELEMS(distincts), 3);
+ mjpegenc_huffman_compute_bits(val_counts, len_counts,
+ FF_ARRAY_ELEMS(val_counts), MAX_LEN);
- for (i = 0; i < FF_ARRAY_ELEMS(distincts); i++) {
- if (distincts[i].code != expected[i].code ||
- distincts[i].length != expected[i].length) {
+ for (unsigned i = 1; i < FF_ARRAY_ELEMS(len_counts); i++) {
+ if (len_counts[i] != expected[i]) {
fprintf(stderr,
"Built huffman does not equal expectations. "
- "Expected: code %d probability %d, "
- "Actual: code %d probability %d\n",
- expected[i].code, expected[i].length,
- distincts[i].code, distincts[i].length);
+ "Expected: %d codes of length %u, "
+ "Actual: %d codes of length %u\n",
+ (int)expected[i], i,
+ (int)len_counts[i], i);
+ ret = 1;
+ }
+ }
+ for (unsigned i = 1; i < FF_ARRAY_ELEMS(val_counts); ++i) {
+ if (val_counts[i - 1].prob > val_counts[i].prob) {
+ fprintf(stderr, "Probability table not ordered ascendingly. "
+ "val_counts[%u] == %d, val_counts[%u] == %d\n",
+ i - 1, val_counts[i - 1].prob, i, val_counts[i].prob);
ret = 1;
}
}
diff --git a/tests/ref/fate/jpg-icc b/tests/ref/fate/jpg-icc
index ee1aca4df1..e12373e953 100644
--- a/tests/ref/fate/jpg-icc
+++ b/tests/ref/fate/jpg-icc
@@ -1,5 +1,5 @@
-5c83d22a628d01c095704f58328f63c9 *tests/data/fate/jpg-icc.mjpeg
-11016 tests/data/fate/jpg-icc.mjpeg
+4d8f3d93f55267cc90bd1d2a94cfa84f *tests/data/fate/jpg-icc.mjpeg
+11011 tests/data/fate/jpg-icc.mjpeg
#tb 0: 1/25
#media_type 0: video
#codec_id 0: rawvideo
@@ -19,7 +19,7 @@ best_effort_timestamp_time=0.000000
duration=1
duration_time=0.040000
pkt_pos=0
-pkt_size=11016
+pkt_size=11011
width=128
height=128
crop_top=0
diff --git a/tests/ref/lavf/jpg b/tests/ref/lavf/jpg
index 1420d46c6c..723dce0118 100644
--- a/tests/ref/lavf/jpg
+++ b/tests/ref/lavf/jpg
@@ -1,3 +1,3 @@
-64885ae70c3450b50196ce687a672dbe *tests/data/images/jpg/02.jpg
-26062 tests/data/images/jpg/02.jpg
+c7b9382883d021b6535096f58d83c72c *tests/data/images/jpg/02.jpg
+26057 tests/data/images/jpg/02.jpg
tests/data/images/jpg/%02d.jpg CRC=0x1c357a3e
diff --git a/tests/ref/lavf/smjpeg b/tests/ref/lavf/smjpeg
index 832b8e99a6..c305cefac8 100644
--- a/tests/ref/lavf/smjpeg
+++ b/tests/ref/lavf/smjpeg
@@ -1,3 +1,3 @@
-659757345ce01f8a5c4c1373bd073d41 *tests/data/lavf/lavf.smjpeg
-728268 tests/data/lavf/lavf.smjpeg
+9278aa4b2eafa6b863fc6085b43abd8d *tests/data/lavf/lavf.smjpeg
+728177 tests/data/lavf/lavf.smjpeg
tests/data/lavf/lavf.smjpeg CRC=0x29d58fb8
diff --git a/tests/ref/seek/lavf-jpg b/tests/ref/seek/lavf-jpg
index 78e8255fac..e069b85139 100644
--- a/tests/ref/seek/lavf-jpg
+++ b/tests/ref/seek/lavf-jpg
@@ -1,4 +1,4 @@
-ret: 0 st: 0 flags:1 dts: 0.000000 pts: 0.000000 pos: -1 size: 25633
+ret: 0 st: 0 flags:1 dts: 0.000000 pts: 0.000000 pos: -1 size: 25629
ret:-EINVAL st:-1 flags:0 ts:-1.000000
ret:-EINVAL st:-1 flags:1 ts: 1.894167
ret:-EINVAL st: 0 flags:0 ts: 0.800000
@@ -6,7 +6,7 @@ ret:-EINVAL st: 0 flags:1 ts:-0.320000
ret:-EINVAL st:-1 flags:0 ts: 2.576668
ret:-EINVAL st:-1 flags:1 ts: 1.470835
ret: 0 st: 0 flags:0 ts: 0.360000
-ret: 0 st: 0 flags:1 dts: 0.360000 pts: 0.360000 pos: -1 size: 25312
+ret: 0 st: 0 flags:1 dts: 0.360000 pts: 0.360000 pos: -1 size: 25304
ret:-EINVAL st: 0 flags:1 ts:-0.760000
ret:-EINVAL st:-1 flags:0 ts: 2.153336
ret:-EINVAL st:-1 flags:1 ts: 1.047503
@@ -18,7 +18,7 @@ ret:-EINVAL st: 0 flags:0 ts:-0.480000
ret:-EINVAL st: 0 flags:1 ts: 2.400000
ret:-EINVAL st:-1 flags:0 ts: 1.306672
ret: 0 st:-1 flags:1 ts: 0.200839
-ret: 0 st: 0 flags:1 dts: 0.200000 pts: 0.200000 pos: -1 size: 25799
+ret: 0 st: 0 flags:1 dts: 0.200000 pts: 0.200000 pos: -1 size: 25798
ret:-EINVAL st: 0 flags:0 ts:-0.920000
ret:-EINVAL st: 0 flags:1 ts: 2.000000
ret:-EINVAL st:-1 flags:0 ts: 0.883340
@@ -26,5 +26,5 @@ ret:-EINVAL st:-1 flags:1 ts:-0.222493
ret:-EINVAL st: 0 flags:0 ts: 2.680000
ret:-EINVAL st: 0 flags:1 ts: 1.560000
ret: 0 st:-1 flags:0 ts: 0.460008
-ret: 0 st: 0 flags:1 dts: 0.480000 pts: 0.480000 pos: -1 size: 25489
+ret: 0 st: 0 flags:1 dts: 0.480000 pts: 0.480000 pos: -1 size: 25488
ret:-EINVAL st:-1 flags:1 ts:-0.645825
diff --git a/tests/ref/vsynth/vsynth1-mjpeg-422 b/tests/ref/vsynth/vsynth1-mjpeg-422
index 095f2b2497..83e8640d5a 100644
--- a/tests/ref/vsynth/vsynth1-mjpeg-422
+++ b/tests/ref/vsynth/vsynth1-mjpeg-422
@@ -1,4 +1,4 @@
-eb0f7dc02efd5f4ab7ea3c73617801a3 *tests/data/fate/vsynth1-mjpeg-422.avi
-1611674 tests/data/fate/vsynth1-mjpeg-422.avi
+c3f2891bf340dc5bafde50feb236a55d *tests/data/fate/vsynth1-mjpeg-422.avi
+1611442 tests/data/fate/vsynth1-mjpeg-422.avi
bc62d53cce32a595a0c6e9c318e4ce3e *tests/data/fate/vsynth1-mjpeg-422.out.rawvideo
stddev: 7.45 PSNR: 30.69 MAXDIFF: 63 bytes: 7603200/ 7603200
diff --git a/tests/ref/vsynth/vsynth1-mjpeg-444 b/tests/ref/vsynth/vsynth1-mjpeg-444
index 77609c5a45..6f5915e308 100644
--- a/tests/ref/vsynth/vsynth1-mjpeg-444
+++ b/tests/ref/vsynth/vsynth1-mjpeg-444
@@ -1,4 +1,4 @@
-bfde676dad356228f77aa319f046db8a *tests/data/fate/vsynth1-mjpeg-444.avi
-1831606 tests/data/fate/vsynth1-mjpeg-444.avi
+6df1ef3c72846b43b7bbaaed6272e433 *tests/data/fate/vsynth1-mjpeg-444.avi
+1831046 tests/data/fate/vsynth1-mjpeg-444.avi
c51ee467d03242dfc1e4536b0485d00f *tests/data/fate/vsynth1-mjpeg-444.out.rawvideo
stddev: 7.37 PSNR: 30.77 MAXDIFF: 63 bytes: 7603200/ 7603200
diff --git a/tests/ref/vsynth/vsynth1-mjpeg-huffman b/tests/ref/vsynth/vsynth1-mjpeg-huffman
index 7591c5b393..1154ac0353 100644
--- a/tests/ref/vsynth/vsynth1-mjpeg-huffman
+++ b/tests/ref/vsynth/vsynth1-mjpeg-huffman
@@ -1,4 +1,4 @@
-827f4da674de95b4227aadda8dbdaa77 *tests/data/fate/vsynth1-mjpeg-huffman.avi
-1391436 tests/data/fate/vsynth1-mjpeg-huffman.avi
+f42cd955597ade05b81c7e4b0fc35e5a *tests/data/fate/vsynth1-mjpeg-huffman.avi
+1391116 tests/data/fate/vsynth1-mjpeg-huffman.avi
f46e58458ea57495a494650f7153829d *tests/data/fate/vsynth1-mjpeg-huffman.out.rawvideo
stddev: 7.87 PSNR: 30.21 MAXDIFF: 63 bytes: 7603200/ 7603200
diff --git a/tests/ref/vsynth/vsynth1-mjpeg-trell-huffman b/tests/ref/vsynth/vsynth1-mjpeg-trell-huffman
index f54b3663f1..d1660ff4fe 100644
--- a/tests/ref/vsynth/vsynth1-mjpeg-trell-huffman
+++ b/tests/ref/vsynth/vsynth1-mjpeg-trell-huffman
@@ -1,4 +1,4 @@
-e097a118dd37b3ab5607278d7b675ea3 *tests/data/fate/vsynth1-mjpeg-trell-huffman.avi
-1361112 tests/data/fate/vsynth1-mjpeg-trell-huffman.avi
+af1ed7a7536b2a84e8b91b2bbbfa4f9c *tests/data/fate/vsynth1-mjpeg-trell-huffman.avi
+1360828 tests/data/fate/vsynth1-mjpeg-trell-huffman.avi
548de4f6098cbc3d8b65574bb93faf09 *tests/data/fate/vsynth1-mjpeg-trell-huffman.out.rawvideo
stddev: 7.67 PSNR: 30.42 MAXDIFF: 62 bytes: 7603200/ 7603200
diff --git a/tests/ref/vsynth/vsynth2-mjpeg-422 b/tests/ref/vsynth/vsynth2-mjpeg-422
index 4978501f35..3df0f79e5d 100644
--- a/tests/ref/vsynth/vsynth2-mjpeg-422
+++ b/tests/ref/vsynth/vsynth2-mjpeg-422
@@ -1,4 +1,4 @@
-67a35df8ef714568db0362f4dce400fb *tests/data/fate/vsynth2-mjpeg-422.avi
-877718 tests/data/fate/vsynth2-mjpeg-422.avi
+d1e682a3468093c55b9579b5c2499b14 *tests/data/fate/vsynth2-mjpeg-422.avi
+877194 tests/data/fate/vsynth2-mjpeg-422.avi
7fae296bb4290d09971a629040eac072 *tests/data/fate/vsynth2-mjpeg-422.out.rawvideo
stddev: 4.69 PSNR: 34.69 MAXDIFF: 55 bytes: 7603200/ 7603200
diff --git a/tests/ref/vsynth/vsynth2-mjpeg-444 b/tests/ref/vsynth/vsynth2-mjpeg-444
index 6321301571..852b261232 100644
--- a/tests/ref/vsynth/vsynth2-mjpeg-444
+++ b/tests/ref/vsynth/vsynth2-mjpeg-444
@@ -1,4 +1,4 @@
-24e04a6e3b645b3314e522cc6b4d3fb7 *tests/data/fate/vsynth2-mjpeg-444.avi
-1005214 tests/data/fate/vsynth2-mjpeg-444.avi
+b8d276c9017a3018266db3e35e8592df *tests/data/fate/vsynth2-mjpeg-444.avi
+1004766 tests/data/fate/vsynth2-mjpeg-444.avi
fbeca59755dfb2b5e2f2c9781756d634 *tests/data/fate/vsynth2-mjpeg-444.out.rawvideo
stddev: 4.57 PSNR: 34.93 MAXDIFF: 55 bytes: 7603200/ 7603200
diff --git a/tests/ref/vsynth/vsynth2-mjpeg-huffman b/tests/ref/vsynth/vsynth2-mjpeg-huffman
index 17601e20f8..b447820f11 100644
--- a/tests/ref/vsynth/vsynth2-mjpeg-huffman
+++ b/tests/ref/vsynth/vsynth2-mjpeg-huffman
@@ -1,4 +1,4 @@
-2a959ad89469d88894d03dc9ce83e8b9 *tests/data/fate/vsynth2-mjpeg-huffman.avi
-792950 tests/data/fate/vsynth2-mjpeg-huffman.avi
+abca59bd27519877a448c508c046df46 *tests/data/fate/vsynth2-mjpeg-huffman.avi
+792444 tests/data/fate/vsynth2-mjpeg-huffman.avi
fe498d9edaa947e435e4f353c194ef3d *tests/data/fate/vsynth2-mjpeg-huffman.out.rawvideo
stddev: 4.87 PSNR: 34.37 MAXDIFF: 55 bytes: 7603200/ 7603200
diff --git a/tests/ref/vsynth/vsynth2-mjpeg-trell-huffman b/tests/ref/vsynth/vsynth2-mjpeg-trell-huffman
index de7a029315..b521c5a615 100644
--- a/tests/ref/vsynth/vsynth2-mjpeg-trell-huffman
+++ b/tests/ref/vsynth/vsynth2-mjpeg-trell-huffman
@@ -1,4 +1,4 @@
-d6a09ff8a46c297934496d8089cdd2a2 *tests/data/fate/vsynth2-mjpeg-trell-huffman.avi
-734896 tests/data/fate/vsynth2-mjpeg-trell-huffman.avi
+d16eaa6ece27bc10715f24509334c402 *tests/data/fate/vsynth2-mjpeg-trell-huffman.avi
+734736 tests/data/fate/vsynth2-mjpeg-trell-huffman.avi
8612dfee87e32268f6f533188a097785 *tests/data/fate/vsynth2-mjpeg-trell-huffman.out.rawvideo
stddev: 5.03 PSNR: 34.10 MAXDIFF: 67 bytes: 7603200/ 7603200
diff --git a/tests/ref/vsynth/vsynth3-mjpeg-422 b/tests/ref/vsynth/vsynth3-mjpeg-422
index cc2bbe2224..79a3c6b0ae 100644
--- a/tests/ref/vsynth/vsynth3-mjpeg-422
+++ b/tests/ref/vsynth/vsynth3-mjpeg-422
@@ -1,4 +1,4 @@
-9aa0f90dac7ef923a0be0d93ca7dc039 *tests/data/fate/vsynth3-mjpeg-422.avi
-52620 tests/data/fate/vsynth3-mjpeg-422.avi
+9377167f1597b9b2d0e3a8abb5244eba *tests/data/fate/vsynth3-mjpeg-422.avi
+52614 tests/data/fate/vsynth3-mjpeg-422.avi
7c64ab866add1e59fe7c34feed006df1 *tests/data/fate/vsynth3-mjpeg-422.out.rawvideo
stddev: 8.22 PSNR: 29.82 MAXDIFF: 58 bytes: 86700/ 86700
diff --git a/tests/ref/vsynth/vsynth3-mjpeg-444 b/tests/ref/vsynth/vsynth3-mjpeg-444
index 1149953b62..b45f147587 100644
--- a/tests/ref/vsynth/vsynth3-mjpeg-444
+++ b/tests/ref/vsynth/vsynth3-mjpeg-444
@@ -1,4 +1,4 @@
-c063ea1cddfc2a360b92f05d1811ea93 *tests/data/fate/vsynth3-mjpeg-444.avi
-53954 tests/data/fate/vsynth3-mjpeg-444.avi
+ff215eb039c4d2ef34b891c25ffe0fbd *tests/data/fate/vsynth3-mjpeg-444.avi
+53958 tests/data/fate/vsynth3-mjpeg-444.avi
8bbbfeab8b3f6788719e1f0f77ce8612 *tests/data/fate/vsynth3-mjpeg-444.out.rawvideo
stddev: 8.21 PSNR: 29.84 MAXDIFF: 58 bytes: 86700/ 86700
diff --git a/tests/ref/vsynth/vsynth3-mjpeg-huffman b/tests/ref/vsynth/vsynth3-mjpeg-huffman
index 00a4cef6f0..6557375115 100644
--- a/tests/ref/vsynth/vsynth3-mjpeg-huffman
+++ b/tests/ref/vsynth/vsynth3-mjpeg-huffman
@@ -1,4 +1,4 @@
-62a7732fcb9288a7223671b23ce06fa0 *tests/data/fate/vsynth3-mjpeg-huffman.avi
-48170 tests/data/fate/vsynth3-mjpeg-huffman.avi
+52b7c3884957ac81fe1b8e1ecf40827b *tests/data/fate/vsynth3-mjpeg-huffman.avi
+48152 tests/data/fate/vsynth3-mjpeg-huffman.avi
a6daba607898eb6e1a172c2368084a67 *tests/data/fate/vsynth3-mjpeg-huffman.out.rawvideo
stddev: 8.61 PSNR: 29.43 MAXDIFF: 58 bytes: 86700/ 86700
diff --git a/tests/ref/vsynth/vsynth3-mjpeg-trell-huffman b/tests/ref/vsynth/vsynth3-mjpeg-trell-huffman
index 965a9e7792..dc7b8c9866 100644
--- a/tests/ref/vsynth/vsynth3-mjpeg-trell-huffman
+++ b/tests/ref/vsynth/vsynth3-mjpeg-trell-huffman
@@ -1,4 +1,4 @@
-7cbc02d85a572b5ea871c014ce27ab4c *tests/data/fate/vsynth3-mjpeg-trell-huffman.avi
+fcfa06df101f91ac19793dc90c4c918c *tests/data/fate/vsynth3-mjpeg-trell-huffman.avi
47834 tests/data/fate/vsynth3-mjpeg-trell-huffman.avi
07822517628b20d54621df666ea79af3 *tests/data/fate/vsynth3-mjpeg-trell-huffman.out.rawvideo
stddev: 8.27 PSNR: 29.78 MAXDIFF: 55 bytes: 86700/ 86700
diff --git a/tests/ref/vsynth/vsynth_lena-mjpeg-422 b/tests/ref/vsynth/vsynth_lena-mjpeg-422
index bb862da006..4bc815e5d7 100644
--- a/tests/ref/vsynth/vsynth_lena-mjpeg-422
+++ b/tests/ref/vsynth/vsynth_lena-mjpeg-422
@@ -1,4 +1,4 @@
-494812cc00c2d51df2d9cbc03dc9eecd *tests/data/fate/vsynth_lena-mjpeg-422.avi
-707466 tests/data/fate/vsynth_lena-mjpeg-422.avi
+778be0c8ee9c030aa2838bf249874082 *tests/data/fate/vsynth_lena-mjpeg-422.avi
+707170 tests/data/fate/vsynth_lena-mjpeg-422.avi
16d2be35266d303dff3361e4535e8dd8 *tests/data/fate/vsynth_lena-mjpeg-422.out.rawvideo
stddev: 4.18 PSNR: 35.70 MAXDIFF: 49 bytes: 7603200/ 7603200
diff --git a/tests/ref/vsynth/vsynth_lena-mjpeg-444 b/tests/ref/vsynth/vsynth_lena-mjpeg-444
index cef6dd9eec..a04537a094 100644
--- a/tests/ref/vsynth/vsynth_lena-mjpeg-444
+++ b/tests/ref/vsynth/vsynth_lena-mjpeg-444
@@ -1,4 +1,4 @@
-52996e606d20fe34c327a206be066091 *tests/data/fate/vsynth_lena-mjpeg-444.avi
-807472 tests/data/fate/vsynth_lena-mjpeg-444.avi
+a48b1f2d17264bce552cfcd920df1ea9 *tests/data/fate/vsynth_lena-mjpeg-444.avi
+807190 tests/data/fate/vsynth_lena-mjpeg-444.avi
0db1c1942d750b107acf2acfbe08eacb *tests/data/fate/vsynth_lena-mjpeg-444.out.rawvideo
stddev: 4.05 PSNR: 35.96 MAXDIFF: 49 bytes: 7603200/ 7603200
diff --git a/tests/ref/vsynth/vsynth_lena-mjpeg-huffman b/tests/ref/vsynth/vsynth_lena-mjpeg-huffman
index 5f5e19bb67..6445f22ca4 100644
--- a/tests/ref/vsynth/vsynth_lena-mjpeg-huffman
+++ b/tests/ref/vsynth/vsynth_lena-mjpeg-huffman
@@ -1,4 +1,4 @@
-d8b968d6ecaa83bb120eb0dd08c3f6df *tests/data/fate/vsynth_lena-mjpeg-huffman.avi
-635642 tests/data/fate/vsynth_lena-mjpeg-huffman.avi
+80bf47172b96ad68be829c4f46073299 *tests/data/fate/vsynth_lena-mjpeg-huffman.avi
+635256 tests/data/fate/vsynth_lena-mjpeg-huffman.avi
095f88a721813c2a1c34b26303c1139a *tests/data/fate/vsynth_lena-mjpeg-huffman.out.rawvideo
stddev: 4.33 PSNR: 35.40 MAXDIFF: 49 bytes: 7603200/ 7603200
diff --git a/tests/ref/vsynth/vsynth_lena-mjpeg-trell-huffman b/tests/ref/vsynth/vsynth_lena-mjpeg-trell-huffman
index 2eb1658363..9bfb7be751 100644
--- a/tests/ref/vsynth/vsynth_lena-mjpeg-trell-huffman
+++ b/tests/ref/vsynth/vsynth_lena-mjpeg-trell-huffman
@@ -1,4 +1,4 @@
-8217aef7ee16709b2c0591a9a28d9bb8 *tests/data/fate/vsynth_lena-mjpeg-trell-huffman.avi
-582648 tests/data/fate/vsynth_lena-mjpeg-trell-huffman.avi
+dc66c0700d50235965fd3fabdcb9a214 *tests/data/fate/vsynth_lena-mjpeg-trell-huffman.avi
+582552 tests/data/fate/vsynth_lena-mjpeg-trell-huffman.avi
8c5c05e82a959ccc8b3c4ba8e4123bbe *tests/data/fate/vsynth_lena-mjpeg-trell-huffman.out.rawvideo
stddev: 4.51 PSNR: 35.04 MAXDIFF: 60 bytes: 7603200/ 7603200
--
2.45.2
From d263f1ce20518933fb78f237fa715e78aec04181 Mon Sep 17 00:00:00 2001
From: Andreas Rheinhardt <andreas.rheinha...@outlook.com>
Date: Mon, 14 Apr 2025 14:43:39 +0200
Subject: [PATCH 3/3] avcodec/mjpegenc_huffman: Already build codes
I.e. do what ff_mjpeg_build_huffman_codes() does already
in ff_mjpeg_encode_huffman_close(). This is more natural
and traverses the array of values one less time.
Signed-off-by: Andreas Rheinhardt <andreas.rheinha...@outlook.com>
---
libavcodec/mjpegenc.c | 33 ++++++++++++---------------------
libavcodec/mjpegenc_huffman.c | 24 ++++++++++++------------
libavcodec/mjpegenc_huffman.h | 17 +++++++++++++++--
3 files changed, 39 insertions(+), 35 deletions(-)
diff --git a/libavcodec/mjpegenc.c b/libavcodec/mjpegenc.c
index 214e2b0ec1..f05b4f88a5 100644
--- a/libavcodec/mjpegenc.c
+++ b/libavcodec/mjpegenc.c
@@ -196,33 +196,24 @@ static void mjpeg_build_optimal_huffman(MJpegContext *m)
ff_mjpeg_encode_huffman_close(&dc_luminance_ctx,
m->bits_dc_luminance,
- m->val_dc_luminance, 12);
+ m->val_dc_luminance, 12,
+ m->huff_size_dc_luminance,
+ m->huff_code_dc_luminance);
ff_mjpeg_encode_huffman_close(&dc_chrominance_ctx,
m->bits_dc_chrominance,
- m->val_dc_chrominance, 12);
+ m->val_dc_chrominance, 12,
+ m->huff_size_dc_chrominance,
+ m->huff_code_dc_chrominance);
ff_mjpeg_encode_huffman_close(&ac_luminance_ctx,
m->bits_ac_luminance,
- m->val_ac_luminance, 256);
+ m->val_ac_luminance, 256,
+ m->huff_size_ac_luminance,
+ m->huff_code_ac_luminance);
ff_mjpeg_encode_huffman_close(&ac_chrominance_ctx,
m->bits_ac_chrominance,
- m->val_ac_chrominance, 256);
-
- ff_mjpeg_build_huffman_codes(m->huff_size_dc_luminance,
- m->huff_code_dc_luminance,
- m->bits_dc_luminance,
- m->val_dc_luminance);
- ff_mjpeg_build_huffman_codes(m->huff_size_dc_chrominance,
- m->huff_code_dc_chrominance,
- m->bits_dc_chrominance,
- m->val_dc_chrominance);
- ff_mjpeg_build_huffman_codes(m->huff_size_ac_luminance,
- m->huff_code_ac_luminance,
- m->bits_ac_luminance,
- m->val_ac_luminance);
- ff_mjpeg_build_huffman_codes(m->huff_size_ac_chrominance,
- m->huff_code_ac_chrominance,
- m->bits_ac_chrominance,
- m->val_ac_chrominance);
+ m->val_ac_chrominance, 256,
+ m->huff_size_ac_chrominance,
+ m->huff_code_ac_chrominance);
}
#endif
diff --git a/libavcodec/mjpegenc_huffman.c b/libavcodec/mjpegenc_huffman.c
index 7fd63a2569..732ae88b39 100644
--- a/libavcodec/mjpegenc_huffman.c
+++ b/libavcodec/mjpegenc_huffman.c
@@ -148,16 +148,9 @@ void ff_mjpeg_encode_huffman_init(MJpegEncHuffmanContext *s)
memset(s->val_count, 0, sizeof(s->val_count));
}
-/**
- * Produces a Huffman encoding with a given input
- *
- * @param s input to encode
- * @param bits output array where the ith character represents how many input values have i length encoding
- * @param val output array of input values sorted by their encoded length
- * @param max_nval maximum number of distinct input values
- */
-void ff_mjpeg_encode_huffman_close(MJpegEncHuffmanContext *s, uint8_t bits[17],
- uint8_t val[], int max_nval)
+void ff_mjpeg_encode_huffman_close(const MJpegEncHuffmanContext *s, uint8_t bits[17],
+ uint8_t val[], int max_nval,
+ uint8_t huff_len[], uint16_t huff_code[])
{
PTable val_counts[257];
@@ -181,6 +174,13 @@ void ff_mjpeg_encode_huffman_close(MJpegEncHuffmanContext *s, uint8_t bits[17],
av_assert1(val_counts[0].prob == 0 && val_counts[0].value == 256);
// The following loop puts the values with higher occurence first,
// ensuring that they get the shorter codes.
- for (int i = 0; i < nval; ++i)
- val[i] = val_counts[nval - i].value;
+ unsigned code = 0;
+ for (int len = 1, i = 0; len <= 16; ++len) {
+ for (const int end = i + bits[len]; i < end; ++i) {
+ unsigned sym = val[i] = val_counts[nval - i].value;
+ huff_len[sym] = len;
+ huff_code[sym] = code++;
+ }
+ code <<= 1;
+ }
}
diff --git a/libavcodec/mjpegenc_huffman.h b/libavcodec/mjpegenc_huffman.h
index 8822e468aa..b43f1a6017 100644
--- a/libavcodec/mjpegenc_huffman.h
+++ b/libavcodec/mjpegenc_huffman.h
@@ -40,8 +40,21 @@ static inline void ff_mjpeg_encode_huffman_increment(MJpegEncHuffmanContext *s,
{
s->val_count[val]++;
}
-void ff_mjpeg_encode_huffman_close(MJpegEncHuffmanContext *s,
+
+/**
+ * Produces a Huffman encoding with a given input
+ *
+ * @param s MJpegEncHuffmanContext with the input to encode
+ * @param bits[out] array where the ith character represents how many
+ * input values have i length encoding
+ * @param val[out] array of input values sorted by their encoded length
+ * @param max_nval maximum number of distinct input values
+ * @param huff_len[out] LUT of code lens as ff_mjpeg_build_huffman_codes() produces them
+ * @param huff_code[out] LUT of codes as ff_mjpeg_build_huffman_codes() produces them
+ */
+void ff_mjpeg_encode_huffman_close(const MJpegEncHuffmanContext *s,
uint8_t bits[17], uint8_t val[],
- int max_nval);
+ int max_nval,
+ uint8_t huff_len[], uint16_t huff_code[]);
#endif /* AVCODEC_MJPEGENC_HUFFMAN_H */
--
2.45.2
_______________________________________________
ffmpeg-devel mailing list
ffmpeg-devel@ffmpeg.org
https://ffmpeg.org/mailman/listinfo/ffmpeg-devel
To unsubscribe, visit link above, or email
ffmpeg-devel-requ...@ffmpeg.org with subject "unsubscribe".
