mjpegenc_huffman.c File Reference

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

Go to the source code of this file.

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...
void	ff_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

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 38 of file mjpegenc_huffman.c.

Referenced by ff_mjpegenc_huffman_compute_bits().

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 52 of file mjpegenc_huffman.c.

Referenced by ff_mjpeg_encode_huffman_close().

void ff_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.

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 80 of file mjpegenc_huffman.c.

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

void ff_mjpeg_encode_huffman_init

(

MJpegEncHuffmanContext *

s

)

Definition at line 148 of file mjpegenc_huffman.c.

Referenced by ff_mjpeg_build_optimal_huffman().

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 161 of file mjpegenc_huffman.c.

Referenced by ff_mjpeg_build_optimal_huffman().