mjpegenc_huffman.c File Reference

#include <string.h>
#include <stdint.h>
#include "libavutil/avassert.h"
#include "libavutil/qsort.h"
#include "mjpegenc_huffman.h"

Go to the source code of this file.

Data Structures
struct	PTable
	Used to assign a occurrence count or "probability" to an input value. More...
struct	PackageMergerList
	Used to store intermediate lists in the package merge algorithm. More...

Functions
static int	compare_by_prob (const void *a, const void *b)
	Comparison function for two PTables by prob. More...
static void	mjpegenc_huffman_compute_bits (PTable *prob_table, uint8_t counts[], int size, int max_length)
	Computes the length of the Huffman encoding for each distinct input value. More...
void	ff_mjpeg_encode_huffman_init (MJpegEncHuffmanContext *s)
void	ff_mjpeg_encode_huffman_close (MJpegEncHuffmanContext *s, uint8_t bits[17], uint8_t val[], int max_nval)
	Produces a Huffman encoding with a given input. More...

Function Documentation

compare_by_prob()

static int compare_by_prob ( const void *  a, const void *  b  )

static

Comparison function for two PTables by prob.

Parameters

a	First PTable to compare
b	Second PTable to compare

Returns

< 0 for less than, 0 for equals, > 0 for greater than

Definition at line 53 of file mjpegenc_huffman.c.

Referenced by mjpegenc_huffman_compute_bits().

mjpegenc_huffman_compute_bits()

static void mjpegenc_huffman_compute_bits ( PTable *  prob_table, uint8_t  counts[], int  size, int  max_length  )

static

Computes the length of the Huffman encoding for each distinct input value.

Uses package merge algorithm as follows:

1. start with an empty list, lets call it list(0), set i = 0
2. add 1 entry to list(i) for each symbol we have and give each a score equal to the probability of the respective symbol
3. merge the 2 symbols of least score and put them in list(i+1), and remove them from list(i). The new score will be the sum of the 2 scores
4. if there is more than 1 symbol left in the current list(i), then goto 3
5. i++
6. if i < 16 goto 2
7. select the n-1 elements in the last list with the lowest score (n = the number of symbols)
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 nonnegative integers.

Parameters

prob_table[in,out]	array of a PTable for each distinct input value, will be sorted according to ascending probability
counts[out]	the number of values of a given length
size	number of elements of the prob_table array
max_length	max length of a code

Definition at line 81 of file mjpegenc_huffman.c.

Referenced by check_lengths(), ff_mjpeg_encode_huffman_close(), and main().

ff_mjpeg_encode_huffman_init()

void ff_mjpeg_encode_huffman_init

(

MJpegEncHuffmanContext *

s

)

Definition at line 146 of file mjpegenc_huffman.c.

ff_mjpeg_encode_huffman_close()

void ff_mjpeg_encode_huffman_close	(	MJpegEncHuffmanContext *	s,
		uint8_t	bits[17],
		uint8_t	val[],
		int	max_nval
	)

Produces a Huffman encoding with a given input.

Parameters

s	input to encode
bits	output array where the ith character represents how many input values have i length encoding
val	output array of input values sorted by their encoded length
max_nval	maximum number of distinct input values

Definition at line 159 of file mjpegenc_huffman.c.