domain-pool.c

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

 *  Domain pool with state image 0 (constant function f(x, y) = 1).
 *  No probability model is used.
 */
{
    domain_pool_t *pool;
   
    pool           = default_alloc ();   
    pool->generate = const_generate;
    pool->bits     = const_bits;
   
    return pool;
}

static word_t *
const_generate (unsigned level, int y_state, const wfa_t *wfa,
                const void *model)
{
    word_t *domains = Calloc (2, sizeof (word_t));
   
    domains [0] = 0;
    domains [1] = -1;
   
    return domains;
}

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)
{
    return 0;                /* 0 bits,
                                either we have a lc or not */
}

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

static domain_pool_t *
alloc_basis_domain_pool (unsigned max_domains, unsigned max_edges,
                         const wfa_t *wfa)
/*
 *  Domain pool with state images {0, ..., 'basis_states' - 1).
 *  Underlying probability model: quasi arithmetic coding of columns.
 *  I.e. domain pool = qac_domainpool ('max_domains' == wfa->basis_states)
 */
{
    return alloc_qac_domain_pool (wfa->basis_states, max_edges, wfa);
}

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

static domain_pool_t *
alloc_uniform_domain_pool (unsigned max_domains, unsigned max_edges,
                           const wfa_t *wfa)
/*
 *  Domain pool with state images {0, ..., 'max_domains').
 *  Underlying probability model: uniform distribution.
 */
{
    domain_pool_t *pool;
   
    pool           = default_alloc ();   
    pool->generate = uniform_generate;
    pool->bits     = uniform_bits;
   
    return pool;
}

static word_t *
uniform_generate (unsigned level, int y_state, const wfa_t *wfa,
                  const void *model)
{
    unsigned  state, n;
    word_t   *domains = Calloc (wfa->states + 1, sizeof (word_t));

    for (state = 0, n = 0; state < wfa->states; state++)
        if (usedomain (state, wfa))
            domains [n++] = state;
    domains [n] = -1;
   
    return domains;
}
 
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)
{
    unsigned state, n;
    real_t   bits = 0;
   
    for (state = 0, n = 0; state < wfa->states; state++)
        if (usedomain (state, wfa))
            n++;

    bits = - n * log2 ((n - 1) / (real_t) n);

    if (used_domains != NULL)
    {
        int edge;
      
        for (edge = 0; isedge (used_domains [edge]); edge++)
            bits -= log2 (1.0 / n);
    }

    return bits;
}

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

typedef struct rle_model
{
    word_t   count [MAXEDGES + 1];
    u_word_t total;
    u_word_t n;
    u_word_t max_domains;
    u_word_t y_index;        /* pointer to prob of Y domain */
    word_t      *states;         /* mapping states -> domains */
    qac_model_t *domain_0;
} rle_model_t;

static domain_pool_t *
alloc_rle_domain_pool (unsigned max_domains, unsigned max_edges,
                       const wfa_t *wfa)
/*
 *  Domain pool with state images {0, ..., 'max_domains').
 *  Underlying probability model: rle 
 */
{
    domain_pool_t *pool;
    unsigned   state;
   
    pool                  = default_alloc ();    
    pool->model           = rle_model_alloc (max_domains);
    pool->model_free      = rle_model_free;
    pool->model_duplicate = rle_model_duplicate;
    pool->generate        = rle_generate;
    pool->update          = rle_update;
    pool->bits            = rle_bits;
    pool->append          = rle_append;
    pool->chroma          = rle_chroma;

    for (state = 0; state < wfa->basis_states; state++)
        if (usedomain (state, wfa))
            rle_append (state, -1, wfa, pool->model);

    return pool;
}

static void *
rle_model_alloc (unsigned max_domains)
{
    unsigned m;
    rle_model_t *model = Calloc (1, sizeof (rle_model_t));
   
    for (m = model->total = 0; m < MAXEDGES + 1; m++, model->total++)
        model->count [m] = 1;

    model->domain_0    = qac_model_alloc (1);
    model->states      = Calloc (max_domains, sizeof (word_t));
    model->n       = 0;
    model->y_index     = 0;
    model->max_domains = max_domains;
   
    return model;
}

static void
rle_model_free (void *model)
{
    qac_model_free (((rle_model_t *) model)->domain_0);
    Free (((rle_model_t *) model)->states);
    Free (model);
}

static void *
rle_model_duplicate (const void *src)
{
    const rle_model_t *rle_src = (rle_model_t *) src;
    rle_model_t       *model   = Calloc (1, sizeof (rle_model_t));

    model->domain_0    = qac_model_duplicate (rle_src->domain_0);
    model->n       = rle_src->n;
    model->max_domains = rle_src->max_domains;
    model->states      = Calloc (model->max_domains, sizeof (word_t));
    model->total       = rle_src->total;
    model->y_index     = rle_src->y_index;
   
    memcpy (model->states, rle_src->states,
            model->max_domains * sizeof (word_t));
    memcpy (model->count, rle_src->count,
            (MAXEDGES + 1) * sizeof (word_t));
   
    return model;
}

static word_t *
rle_generate (unsigned level, int y_state, const wfa_t *wfa, const void *model)
{
    word_t      *domains;
    unsigned n;
    rle_model_t *rle_model     = (rle_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 (rle_model->n + 2, sizeof (word_t));

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

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

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

    return domains;
}

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)
{
    unsigned edge;
    unsigned n     = 0;
    real_t   bits      = 0;
    word_t   sorted [MAXEDGES + 1];
    rle_model_t *rle_model = (rle_model_t *) model;
    unsigned last;
    int      into;
   
    if (y_state >= 0 && !usedomain (y_state, wfa)) /* don't use y-state */
        y_state = -1;

    if (used_domains)
    {
        word_t domain;
      
        if (y_state >= 0)
            bits += matrix_0 [rle_model->y_index];
      
        for (edge = n = 0; isedge (domain = used_domains [edge]); edge++)
            if (domains [domain] != y_state)
                sorted [n++] = used_domains [edge];
            else
            {
                bits -= matrix_0 [rle_model->y_index];
                bits += matrix_1 [rle_model->y_index];
            }
      
        if (n > 1)
            qsort (sorted, n, sizeof (word_t), sort_asc_word);
    }

    bits = - log2 (rle_model->count [n] / (real_t) rle_model->total);
    if (used_domains && n && sorted [0] == 0)
    {
        word_t array0 [2] = {0, NO_EDGE};
        bits += qac_bits (array0, array0, level, y_state, wfa, rle_model->domain_0);
    }
    else
    {
        word_t array0 [2] = {NO_EDGE};
        bits += qac_bits (array0, array0, level, y_state, wfa, rle_model->domain_0);
    }
   
    last = 1;
    for (edge = 0; edge < n; edge++)
        if ((into = sorted [edge]) && rle_model->n - 1 - last)
        {
            bits += bits_bin_code (into - last, rle_model->n - 1 - last);
            last  = into + 1;
        }
   
    return bits;
}

static void
rle_update (const word_t *domains, const word_t *used_domains,
            unsigned level, int y_state, const wfa_t *wfa, void *model)
{
    rle_model_t *rle_model  = (rle_model_t *) model;
    bool_t   state_0    = NO, state_y = NO;
    word_t   array0 [2] = {0, NO_EDGE};
    unsigned     edge = 0;
   
    if (y_state >= 0 && !usedomain (y_state, wfa)) /* don't use y-state */
        y_state = -1;

    if (used_domains)
    {
        word_t   domain;
      
        for (edge = 0; isedge (domain = used_domains [edge]); edge++)
            if (domains [domain] == 0)
                state_0 = YES;
            else if (domains [domain] == y_state)
                state_y = YES;
    }
   
    rle_model->count [edge]++;
    rle_model->total++;

    qac_update (array0, array0 + (state_0 ? 0 : 1), level, y_state, wfa,
                rle_model->domain_0);

    if (state_y)
        rle_model->y_index >>= 1;
    else
        rle_model->y_index++;
    if (rle_model->y_index > 1020)   /* check for overflow */
        rle_model->y_index = 1020; 
}

static bool_t
rle_append (unsigned new_state, unsigned level, const wfa_t *wfa, void *model)
{
    rle_model_t *rle_model = (rle_model_t *) model; /* probability model */
   
    if (rle_model->n >= rle_model->max_domains)
        return NO;            /* don't use state in domain pool */
    else
    {
        rle_model->states [rle_model->n] = new_state;
        rle_model->n++;

        if (new_state == 0)
        {
            assert (rle_model->n == 1);
            qac_append (0, -1, wfa, rle_model->domain_0);
        }
      
        return YES;           /* state will be used in domain pool */
    }
}

static void
rle_chroma (unsigned max_domains, const wfa_t *wfa, void *model)
{
    rle_model_t *rle_model = (rle_model_t *) model; /* probability model */
   
    if (max_domains < rle_model->n)  /* choose most probable domains */
    {
        unsigned  n;
        word_t   *states  = Calloc (max_domains, sizeof (word_t));
        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];

        assert (states [0] == 0);
        max_domains = min (max_domains, n);
        Free (domains);

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

/*****************************************************************************
         run length encoding pool no special chroma pool
*****************************************************************************/

static domain_pool_t *
alloc_rle_no_chroma_domain_pool (unsigned max_domains, unsigned max_edges,
                                 const wfa_t *wfa)
/*
 *  Domain pool with state images {0, ..., 'max_domains').
 *  Underlying probability model: rle 
 *  Domain pool is not changed for chroma bands
 */
{
    domain_pool_t *pool = alloc_rle_domain_pool (max_domains, max_edges, wfa);
   
    pool->chroma = default_chroma;

    return pool;
}

/*****************************************************************************
              default functions (see domain-pool.h)
*****************************************************************************/

static domain_pool_t *
default_alloc (void)
{
    domain_pool_t *pool;

    pool                  = Calloc (1, sizeof (domain_pool_t));
    pool->model           = default_model_alloc(0);
    pool->generate        = NULL;
    pool->bits            = NULL;
    pool->update          = default_update;
    pool->append          = default_append;
    pool->chroma          = default_chroma;
    pool->free            = default_free;
    pool->model_free      = default_model_free;
    pool->model_duplicate = default_model_duplicate;
   
    return pool;
}

static void *
default_model_duplicate (const void *src)
{
    return NULL;
}

static void *
default_model_alloc (unsigned max_domains)
{
    return NULL;
}

static void
default_model_free (void *model)
{
    if (model)
        Free (model);
}

static void
default_free (domain_pool_t *pool)
{
    pool->model_free (pool->model);
    Free (pool);
}

static void
default_update (const word_t *domains, const word_t *used_domains,
                unsigned level, int y_state, const wfa_t *wfa, void *model)
{
    return;              /* nothing to do */
}

static bool_t
default_append (unsigned new_state, unsigned level,
                const wfa_t *wfa, void *model)
{
    return YES;              /* use every state in lin comb */
}

static void
default_chroma (unsigned max_domains, const wfa_t *wfa, void *model)
{
    return;              /* don't alter domain pool */
}

static void
init_matrix_probabilities (void)
/*
 *  Compute the information contents of matrix element '0' and '1' for
 *  each possible probability index 0, ... ,  1023. These values are
 *  obtained from the probability model in the quasi arithmetic
 *  coding module.
 *
 *  No return value.
 *
 *  Side effects:
 *  local arrays matrix_0 and matrix_1 are initialized if not already done.
 */
{
    if (matrix_0 == NULL || matrix_1 == NULL)
    {
        unsigned index;           
        unsigned n, exp;
      
        matrix_0 = Calloc (1 << (MAX_PROB + 1), sizeof (real_t));
        matrix_1 = Calloc (1 << (MAX_PROB + 1), sizeof (real_t));
   
        for (index = 0, n = MIN_PROB; n <= MAX_PROB; n++)
            for (exp = 0; exp < (unsigned) 1 << n; exp++, index++)
            {
                matrix_1 [index] = -log2 (1 / (real_t) (1 << n));
                matrix_0 [index] = -log2 (1 - 1 / (real_t) (1 << n));
            }
    }
}