domain-pool.c

linux下将各类格式图片转换工具

/*
 *  domain-pool.c:  Domain pool management (probability model)
 *
 *  Written by:     Ullrich Hafner
 *      
 *  This file is part of FIASCO (獸籸actal 獻籱age 獳籲d 玈籩quence 獵O籨ec)
 *  Copyright (C) 1994-2000 Ullrich Hafner <[e-mail]>
 */

/*
 *  $Date: 2000/06/14 20:50:51 $
 *  $Author: hafner $
 *  $Revision: 5.1 $
 *  $State: Exp $
 */

#include "config.h"

#include <math.h>

#if STDC_HEADERS
#   include <stdlib.h>
#endif /* not STDC_HEADERS */

#if HAVE_STRING_H
#   include <string.h>
#else /* not HAVE_STRING_H */
#   include <strings.h>
#endif /* not HAVE_STRING_H */

#include "types.h"
#include "macros.h"
#include "error.h"

#include "misc.h"
#include "cwfa.h"
#include "wfalib.h"
#include "domain-pool.h"

/*
 *  Domain pool model interface:
 *  Implementing the domain pool model interface requires the
 *  following steps: 
 *  - Add a constructor that initializes the domain_pool_t structure
 *  - Allocate new model with default_alloc() 
 *  - Fill the dp_array_t domain_pools array with constructor and name
 *  - Write code for methods bits() and generate()
 *  - Either use default functions for remaining methods or override them
 *  The new model is automatically registered at the command line.
 */

/*****************************************************************************
                                          
                  local variables
                  
*****************************************************************************/

static real_t *matrix_0 = NULL;
static real_t *matrix_1 = NULL;

/*****************************************************************************
                        non-adaptive domain pool
*****************************************************************************/

static void
qac_chroma (unsigned max_domains, const wfa_t *wfa, void *model);
static bool_t
qac_append (unsigned new_state, unsigned level, const wfa_t *wfa, void *model);
static void
qac_update (const word_t *domains, const word_t *used_domains,
            unsigned level, int y_state, const wfa_t *wfa, void *model);
static real_t
qac_bits (const word_t *domains, const word_t *used_domains,
          unsigned level, int y_state, const wfa_t *wfa, const void *model);
static word_t *
qac_generate (unsigned level, int y_state, const wfa_t *wfa,
              const void *model);
static void *
qac_model_duplicate (const void *src);
static void
qac_model_free (void *model);
static void *
qac_model_alloc (unsigned max_domains);
static domain_pool_t *
alloc_qac_domain_pool (unsigned max_domains, unsigned max_edges,
                       const wfa_t *wfa);

/*****************************************************************************
              run length encoding pool
*****************************************************************************/

static domain_pool_t *
alloc_rle_no_chroma_domain_pool (unsigned max_domains, unsigned max_edges,
                                 const wfa_t *wfa);
static void
rle_chroma (unsigned max_domains, const wfa_t *wfa, void *model);
static bool_t
rle_append (unsigned new_state, unsigned level, const wfa_t *wfa, void *model);
static void
rle_update (const word_t *domains, const word_t *used_domains,
            unsigned level, int y_state, const wfa_t *wfa, void *model);
static real_t
rle_bits (const word_t *domains, const word_t *used_domains,
          unsigned level, int y_state, const wfa_t *wfa, const void *model);
static word_t *
rle_generate (unsigned level, int y_state, const wfa_t *wfa,
              const void *model);
static void *
rle_model_duplicate (const void *src);
static void
rle_model_free (void *model);
static void *
rle_model_alloc (unsigned max_domains);
static domain_pool_t *
alloc_rle_domain_pool (unsigned max_domains, unsigned max_edges,
                       const wfa_t *wfa);

/*****************************************************************************
              const domain pool
*****************************************************************************/

static real_t
const_bits (const word_t *domains, const word_t *used_domains,
            unsigned level, int y_state, const wfa_t *wfa, const void *model);
static word_t *
const_generate (unsigned level, int y_state, const wfa_t *wfa,
                const void *model);
static domain_pool_t *
alloc_const_domain_pool (unsigned max_domains, unsigned max_edges,
                         const wfa_t *wfa);

/*****************************************************************************
              basis domain pool
*****************************************************************************/

static domain_pool_t *
alloc_basis_domain_pool (unsigned max_domains, unsigned max_edges,
                         const wfa_t *wfa);

/*****************************************************************************
              uniform distribution pool
*****************************************************************************/

static real_t
uniform_bits (const word_t *domains, const word_t *used_domains,
              unsigned level, int y_state, const wfa_t *wfa,
              const void *model);
static word_t *
uniform_generate (unsigned level, int y_state, const wfa_t *wfa,
                  const void *model);
static domain_pool_t *
alloc_uniform_domain_pool (unsigned max_domains, unsigned max_edges,
                           const wfa_t *wfa);

/*****************************************************************************
              default functions
*****************************************************************************/

static void
init_matrix_probabilities (void);
static void
default_chroma (unsigned max_domains, const wfa_t *wfa, void *model);
static bool_t
default_append (unsigned new_state, unsigned level,
                const wfa_t *wfa, void *model);
static void
default_update (const word_t *domains, const word_t *used_domains,
                unsigned level, int y_state, const wfa_t *wfa, void *model);
static void
default_free (domain_pool_t *pool);
static void
default_model_free (void *model);
static void *
default_model_alloc (unsigned max_domains);
static void *
default_model_duplicate (const void *src);
static domain_pool_t *
default_alloc (void);

/*****************************************************************************

                public code
  
*****************************************************************************/

typedef struct dp_array
{
    const char       *identifier;
    domain_pool_t *(*function) (unsigned max_domains, unsigned max_edges,
                                const wfa_t *wfa);
} dp_array_t;

dp_array_t const domain_pools[] = {{"adaptive", alloc_qac_domain_pool},
                                   {"constant",   alloc_const_domain_pool}, 
                                   {"basis",      alloc_basis_domain_pool},
                                   {"uniform",    alloc_uniform_domain_pool},
                                   {"rle",        alloc_rle_domain_pool},
                                   {"rle-no-chroma",  alloc_rle_no_chroma_domain_pool},
                                   {NULL,     NULL}};

domain_pool_t *
alloc_domain_pool (const char *domain_pool_name, unsigned max_domains,
                   unsigned max_edges, const wfa_t *wfa)
/*
 *  Allocate a new domain pool identified by the string
 *  'domain_pool_name'.  Maximum number of domain images (each one
 *  represented by one state of the given 'wfa') is specified by
 *  'max_domains'. 
 * 
 *  Return value:
 *  pointer to the allocated domain pool
 *
 *  Note:
 *      refer to 'domain-pool.h' for a short description of the member functions.
 */
{
    unsigned n;
   
    if (!max_domains)
    {
        warning ("Can't generate empty domain pool. "
                 "Using at least DC component.");
        max_domains = 1;
    }
   
    for (n = 0; domain_pools [n].identifier; n++) /* step through all id's */
        if (strcaseeq (domain_pools [n].identifier, domain_pool_name)) 
            return domain_pools [n].function (max_domains, max_edges, wfa);

    warning ("Can't initialize domain pool '%s'. Using default value '%s'.",
             domain_pool_name, domain_pools [0].identifier);

    return domain_pools [0].function (max_domains, max_edges, wfa);
}

/*****************************************************************************

                private code
  
*****************************************************************************/

/*****************************************************************************
              adaptive domain pool
*****************************************************************************/

typedef struct qac_model
{
    word_t   *index;         /* probability of domains */
    word_t   *states;            /* mapping states -> domains */
    u_word_t  y_index;           /* pointer to prob of Y domain */
    u_word_t  n;             /* number of domains in the pool */
    u_word_t  max_domains;       /* max. number of domains */
} qac_model_t;

static domain_pool_t *
alloc_qac_domain_pool (unsigned max_domains, unsigned max_edges,
                       const wfa_t *wfa)
/*
 *  Domain pool with state images {0, ..., 'max_domains').
 *  Underlying probability model: quasi arithmetic coding of columns.
 */
{
    domain_pool_t *pool;
    unsigned   state;
   
    pool                  = default_alloc ();
    pool->model           = qac_model_alloc (max_domains);
    pool->generate        = qac_generate;
    pool->bits            = qac_bits;
    pool->update          = qac_update;
    pool->append          = qac_append;
    pool->chroma      = qac_chroma;
    pool->model_free      = qac_model_free;
    pool->model_duplicate = qac_model_duplicate;
   
    for (state = 0; state < wfa->basis_states; state++)
        if (usedomain (state, wfa))
            qac_append (state, -1, wfa, pool->model);

    return pool;
}

static void *
qac_model_alloc (unsigned max_domains)
{
    qac_model_t *model;

    init_matrix_probabilities ();

    model          = Calloc (1, sizeof (qac_model_t));
    model->index       = Calloc (max_domains, sizeof (word_t));
    model->states      = Calloc (max_domains, sizeof (word_t));
    model->y_index     = 0;
    model->n       = 0;
    model->max_domains = max_domains;

    return model;
}

static void
qac_model_free (void *model)
{
    Free (((qac_model_t *) model)->index);
    Free (((qac_model_t *) model)->states);
    Free (model);
}

static void *
qac_model_duplicate (const void *src)
{
    qac_model_t       *qdst;
    const qac_model_t *qsrc = (qac_model_t *) src;

    qdst      = qac_model_alloc (qsrc->max_domains);
    qdst->y_index = qsrc->y_index;
    qdst->n       = qsrc->n;
   
    memcpy (qdst->index, qsrc->index, qsrc->n * sizeof (word_t));
    memcpy (qdst->states, qsrc->states, qsrc->n * sizeof (word_t));

    return qdst;
}

static word_t *
qac_generate (unsigned level, int y_state, const wfa_t *wfa, const void *model)
{
    word_t      *domains;
    unsigned n;
    qac_model_t *qac_model     = (qac_model_t *) model;
    bool_t   y_state_is_domain = NO;

    if (y_state >= 0 && !usedomain (y_state, wfa)) /* don't use y-state */
        y_state = -1;
   
    domains = Calloc (qac_model->n + 2, sizeof (word_t));

    memcpy (domains, qac_model->states, qac_model->n * sizeof (word_t));

    for (n = 0; n < qac_model->n; n++)
        if (domains [n] == y_state)   /* match */
            y_state_is_domain = YES;       

    if (y_state_is_domain)
        domains [qac_model->n] = -1;  /* end marker */
    else
    {
        domains [qac_model->n]     = y_state; /* additional y-state */
        domains [qac_model->n + 1] = -1;  /* end marker */
    }

    return domains;
}

static real_t
qac_bits (const word_t *domains, const word_t *used_domains,
          unsigned level, int y_state, const wfa_t *wfa, const void *model)
{
    int      domain;         /* counter */
    real_t   bits      = 0;      /* bit rate R */
    qac_model_t *qac_model = (qac_model_t *) model; /* probability model */

    if (y_state >= 0 && !usedomain (y_state, wfa)) /* don't use y-state */
        y_state = -1;

    for (domain = 0; domain < qac_model->n; domain++)
        if (qac_model->states [domain] != y_state)
            bits += matrix_0 [qac_model->index [domain]];
    if (y_state >= 0)
        bits += matrix_0 [qac_model->y_index];
   
    if (used_domains != NULL)
    {
        unsigned edge;
      
        for (edge = 0; isedge (domain = used_domains [edge]); edge++)
            if (domains [domain] == y_state)
            {
                bits -= matrix_0 [qac_model->y_index];
                bits += matrix_1 [qac_model->y_index];
            }
            else
            {
                bits -= matrix_0 [qac_model->index [domain]];
                bits += matrix_1 [qac_model->index [domain]];
            }
    } 
   
    return bits;
}

static void
qac_update (const word_t *domains, const word_t *used_domains,
            unsigned level, int y_state, const wfa_t *wfa, void *model)
{
    int      domain;
    unsigned edge;
    bool_t   used_y_state      = NO;
    qac_model_t *qac_model     = (qac_model_t *) model;
    bool_t   y_state_is_domain = NO;
   
    if (y_state >= 0 && !usedomain (y_state, wfa)) /* don't use y-state */
        y_state = -1;

    for (domain = 0; domain < qac_model->n; domain++)
    {
        qac_model->index [domain]++;  /* mark domains unused. */
        if (qac_model->states [domain] == y_state) /* match */
            y_state_is_domain = YES;       
    }
   
    for (edge = 0; isedge (domain = used_domains [edge]); edge++)
        if (domains [domain] == y_state) /* chroma coding */
        {
            if (y_state_is_domain)
                qac_model->index [domain]--; /* undo */
            qac_model->y_index >>= 1;
            used_y_state = YES;
        }
        else              /* luminance coding */
        {
            qac_model->index [used_domains [edge]]--; /* undo */
            qac_model->index [used_domains [edge]] >>= 1;      
        }

    if (y_state >= 0 && !used_y_state)
        qac_model->y_index++;     /* update y-state model */
   
    for (domain = 0; domain < qac_model->n; domain++)
        if (qac_model->index [domain] > 1020) /* check for overflow */
            qac_model->index [domain] = 1020; 
    if (qac_model->y_index > 1020)   /* check for overflow */
        qac_model->y_index = 1020; 
}

static bool_t
qac_append (unsigned new_state, unsigned level, const wfa_t *wfa, void *model)
{
    qac_model_t  *qac_model = (qac_model_t *) model; /* probability model */
   
    if (qac_model->n >= qac_model->max_domains)
        return NO;            /* don't use state in domain pool */
    else
    {
        qac_model->index [qac_model->n]
            = qac_model->n > 0 ? qac_model->index [qac_model->n - 1] : 0;
        qac_model->states [qac_model->n] = new_state;
        qac_model->n++;

        return YES;           /* state will be used in domain pool */
    }
}

static void
qac_chroma (unsigned max_domains, const wfa_t *wfa, void *model)
{
    qac_model_t *qac_model = (qac_model_t *) model; /* probability model */
   
    if (max_domains < qac_model->n)  /* choose most probable domains */
    {
        word_t   *domains;
        unsigned  n, new, old;
        word_t   *states = Calloc (max_domains, sizeof (word_t));
        word_t   *index  = Calloc (max_domains, sizeof (word_t));
   
        domains = compute_hits (wfa->basis_states, wfa->states - 1,
                                max_domains, wfa);
        for (n = 0; n < max_domains && domains [n] >= 0; n++)
            states [n] = domains [n];
        max_domains = min (max_domains, n);
        Free (domains);

        for (old = 0, new = 0; new < max_domains && old < qac_model->n; old++)
            if (qac_model->states [old] == states [new])
                index [new++] = qac_model->index [old];

        Free (qac_model->states);
        Free (qac_model->index);
        qac_model->states      = states;
        qac_model->index       = index;
        qac_model->n           = max_domains;
        qac_model->max_domains = max_domains;
    }
    qac_model->y_index     = 0;
    qac_model->max_domains = qac_model->n;
}

/*****************************************************************************
              const domain pool
*****************************************************************************/

static domain_pool_t *
alloc_const_domain_pool (unsigned max_domains, unsigned max_edges,
                         const wfa_t *wfa)
/*