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...
struct	HuffTable
	Used to store optimal huffman encoding results. More...

Functions
static int	compare_by_prob (const void *a, const void *b)
	Comparison function for two PTables by prob. More...
static int	compare_by_length (const void *a, const void *b)
	Comparison function for two HuffTables by length. More...
static void	mjpegenc_huffman_compute_bits (PTable *prob_table, HuffTable *distincts, 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 61 of file mjpegenc_huffman.c.

Referenced by mjpegenc_huffman_compute_bits().

compare_by_length()

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

static

Comparison function for two HuffTables by length.

Parameters

a	First HuffTable to compare
b	Second HuffTable to compare

Returns

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

Definition at line 75 of file mjpegenc_huffman.c.

Referenced by ff_mjpeg_encode_huffman_close().

mjpegenc_huffman_compute_bits()

static void mjpegenc_huffman_compute_bits ( PTable *  prob_table, HuffTable *  distincts, 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 positive integers. The output is sorted by code, not by length.

Parameters

prob_table	input array of a PTable for each distinct input value
distincts	output array of a HuffTable that will be populated by this function
size	size of the prob_table array
max_length	max length of an encoding

Definition at line 103 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 172 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 185 of file mjpegenc_huffman.c.