FFmpeg
Functions
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
aFirst PTable to compare
bSecond 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
aFirst HuffTable to compare
bSecond 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_tableinput array of a PTable for each distinct input value
distinctsoutput array of a HuffTable that will be populated by this function
sizesize of the prob_table array
max_lengthmax 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
sinput to encode
bitsoutput array where the ith character represents how many input values have i length encoding
valoutput array of input values sorted by their encoded length
max_nvalmaximum number of distinct input values

Definition at line 161 of file mjpegenc_huffman.c.

Referenced by ff_mjpeg_build_optimal_huffman(), and ff_mjpeg_encode_huffman_increment().