data.c

大师写的二代小波经典之作

/*
 *  -*- Mode: ANSI C -*-
 *  $Id: data.c,v 1.5 1996/09/17 16:10:37 fernande Exp $
 $  $Source: /sgi.acct/sweldens/cvs/liftpack/Lifting/data.c,v $
 *  Author: Gabriel Fernandez
 *
 *  Here we collect the definitions the functions that manipulate
 *  the data structures defined in data.h.
 */
/* do not edit anything above this line */

/* FLWT header files */
#include <flwterr.h>
#include <imgmem.h>
#include <memchk.h>
#include <util.h>
#include <data.h>

/***************************/
/* Interval data structure */
/***************************/

/*
 * makeinterval function: allocates an interval given the least and
 *                        final values and copy a data array into it
 *                        if one is provided.
 */
Interval *
makeinterval ( Vector data, const int least, const int final )
{
    Interval *seg;
    int length;

    /* Allocate an Interval at seg with all members 0 */
    seg = (Interval *)malloc((unsigned)sizeof(Interval));
    if ( !seg )
        Error ("makeinterval", CUSTOM, ABORT, "Not enough memory for seg.");
    seg->origin = NULL;
    seg->least = 0;
    seg->final = 0;

    length = 1+final-least;
    if ( length > 0 ) {
        /* Allocate an array of length Flts at seg.origin */
        seg->origin = (Vector)malloc((unsigned)length*sizeof(Flt));
        if ( !seg->origin )
            Error ("makeinterval", CUSTOM, ABORT, "Not enough memory for seg.origin.");
        /* Shift origin to least */
        seg->origin -= least;
        /* Fill data, if any */
        if ( data != NULL ) {
            int k;
            for ( k=least ; k<final ; k++ )
                seg->origin[k] = data[k-least];
        }
    }
    seg->least = least;
    seg->final = final;

    return seg;
}

/*
 * freeinterval function: to deallocate and interval's data array,
 *                        it is necessary to shift its pointer back
 *                        to its position at allocation time.
 */
void *
freeinterval ( Interval *seg )
{
    if ( seg != NULL ) {
        if ( seg->origin ) {
            seg->origin += seg->least;
            free (seg->origin);
        }
        free (seg);
    }

    return NULL;
}

/*
 * ininterval function: checks if an offset is within an Interval. This
 *                      adds some elementary range checking so we
 *                      reference only those array locations which are
 *                      in bounds.
 */
boolean
ininterval ( const Interval segment, const int offset )
{
    if ( segment.origin != NULL )
        if ( offset>=segment.least && offset<=segment.final )
            return TRUE;
    return FALSE;
}

/*
 * intervalstotal function: calculates the total length of an array
 *                          of disjoint intervals.
 */
int
intervalstotal ( Interval *in, const int n )
{
    int k, total = 0;

    for ( k=0 ; k<n ; k++ )
        total += 1 + in[k].final - in[k].least;

    return total;
}

/*
 * enlargeinterval function: enlarges the data array in an interval
 *                           to accomodate a new offset. If there is
 *                           already some data in the old interval,
 *                           we copy that into the newly enlarged array.
 */
Interval
enlargeinterval ( Interval old, int least, int final )
{
    int length;

    if ( old.origin == NULL ) {
        length  = 1 + final-least;
        if ( length > 0 ) {
            old.origin = (Vector)malloc((unsigned)sizeof(Flt));
            if ( !old.origin )
                Error ("enlargeinterval", CUSTOM, ABORT,
                       "Not enough memory for old.origin");
            old.origin -= least;
            old.least   = least;
            old.final   = final;
        }
    } else {
        if ( old.least<least || old.final>final ) {
            least = MIN( old.least, least );
            final = MAX( old.final, final );
            length  = 1 + final-least;
            if ( length > 0 ) {
                int j;
                Vector newdata = (Vector)malloc((unsigned)sizeof(Flt));
                if ( !newdata )
                    Error ("enlargeinterval", CUSTOM, ABORT,
                           "Not enough memory for newdata");
                newdata -= least;
                for ( j=old.least ; j<old.final ; j++ )
                    newdata[j] = old.origin[j];
                old.origin += old.least;
                free (old.origin);
                old.origin = newdata;
                old.least  = least;
                old.final  = final;
            }
        }
    }

    return old;
}


/****************/
/* Binary trees */
/****************/

/*
 * makebtm function: allocates a BTN data structure with given members.
 */
BTN *
makebtn ( void *content, BTN *left, BTN *right, void *tag )
{
    BTN *node = (BTN *)malloc((unsigned)sizeof(BTN));

    if ( !node )
        Error ("makebtn", CUSTOM, ABORT, "Not enough memory for node");
    node->tag     = (void *)tag;
    node->content = (void *)content;
    node->left    = (BTN *)left;
    node->right   = (BTN *)right;

    return node;
}

/*
 * freebtn function: deallocates a BTN structure, checking first if
 *                   it has valid content or tag pointers and
 *                   deallocates their targets first.
 */
void *
freebtn ( BTN *node, void (*FreeContent)(void *), void (*FreeTag)(void *) )
{
    if ( node != NULL ) {
        if ( node->content != NULL )
            FreeContent(node->content);
        if ( node->tag != NULL )
            FreeTag(node->tag);
        free(node);
    }

    return NULL;
}

/*
 * makebtnt function: builds a completely empty tree down to a specified
 *                    level with a recursive function.
 */
BTN *
makebtnt ( const int level )
{
    BTN *root = makebtn(NULL, NULL, NULL, NULL);

    if ( level > 0 ) {
        root->left  = makebtnt( level-1 );
        root->right = makebtnt( level-1 );
    }

    return root;
}

/*
 * btnt2btn function: gets a pointer to a particular node in a BTN tree.
 */
BTN *
btnt2btn ( BTN *root, const int level, const int block )
{
    BTN *node;

    if ( root == NULL || level == 0 )
        node = root;
    else {
        if ( EVEN(block) )
            node = btnt2btn( root->left, level-1, block>>1 );
        else
            node = btnt2btn( root->right, level-1, (block-1)>>1 );
    }

    return node;
}

/*
 * freebtnt function: deallocates an entire tree of BTN structures
 *                    employing a recursive function that deallocates
 *                    all the descendent nodes as well.
 */
void *
freebtnt ( BTN *root, void (*FreeContent)(void *), void (*FreeTag)(void *) )
{
    if ( root != NULL ) {
        freebtnt( root->left, FreeContent, FreeTag );
        freebtnt( root->right, FreeContent, FreeTag );
        freebtn( root, FreeContent, FreeTag );
    }

    return NULL;
}

/*
 * btn2branch function: links together one branch of a BTN tree, the
 *                      one between the root and a target specified by
 *                      its level and block indices.
 */
BTN *
btn2branch ( BTN *self, const int level, const int block )
{
    if ( level > 0 ) {
        if ( EVEN(block) ) {
            if ( self->left == NULL )
                self->left = makebtn( NULL, NULL, NULL, NULL );
            self = btn2branch( self->left, level-1, block>>1 );
        } else {
            if ( self->right == NULL )
                self->right = makebtn( NULL, NULL, NULL, NULL );
            self = btn2branch( self->right, level-1, (block-1)>>1 );
        }
    }

    return self;
}


/************************/
/* Hedge data structure */
/************************/

/*
 * makehedge function: assigns the members of a hedge when allocating it.
 *                     It allows the creation of a hedge containing zero
 *                     arrays of specified length just by using the null
 *                     pointers as parameters.
 */
Hedge *
makehedge ( int blocks, Matrix contents, int *levels, void *tag )
{
    Hedge *out = (Hedge *)malloc((unsigned)sizeof(Hedge));

    if ( !out )
        Error ("makehedge", CUSTOM, ABORT, "Not enough memory for out");
    out->blocks = blocks;
    if ( contents == NULL )
        out->contents = (Matrix)calloc((size_t)blocks, (size_t)sizeof(Vector));
    else
        out->contents = contents;
    if ( levels == NULL )
        out->levels = (int *)calloc((size_t)blocks, (size_t)sizeof(int));
    else
        out->levels = levels;
    out->tag = tag;

    return out;
}

/*
 * freehedge function: deallocates a hedge and his members by deallocating
 *                     the contents and levels arrays and the tag pointer
 *                     before deallocating the hedge itself.
 */
void *
/* freehedge ( Hedge *in, void (*FreeContent)(), void (*FreeLevels)(),
                       void (*FreeTag)() ) */
freehedge ( Hedge *in )
{
    if ( in->contents != NULL )
        MEM_Free2D( in->contents );
    if ( in->levels != NULL )
        free( (int *)in->levels );
    /*
    if ( in->tag != NULL )
        FreeTag( in->tag );
    */
    free( (Hedge *)in );

    return NULL;
}


/****************/
/* Manipulation */
/****************/

/*
 * abt2hedge function: given a long array corresponding to a complete
 *                     adapted wavelet analysis and an array of levels
 *                     describing a graph basis subset, the corresponding
 *                     hedge of coefficients is extracted.
 */
void
abt2hedge ( Hedge *graph, Vector data, const int length )
{
    int i, column = 0;

    for ( i=0 ; graph->blocks-1 ; i++ ) {
        graph->contents[i] = data+column+length*graph->levels[i];
        column += length>>graph->levels[i];
    }
}

/*
 * btnt2hedge function: extracts the content members from those BTN's
 *                      specified in the levels list of a hedge.
 */
int
btnt2hedge ( Hedge *graph, BTN *root )
{
    int i,
        maxlevel = 0,
        fraction = 0;

    for ( i=0 ; i<graph->blocks-1 ; i++ ) {
        int level = graph->levels[i],
            block;
        BTN *node;
        if ( level>maxlevel ) {
            fraction <<= level-maxlevel;
            maxlevel = level;
            block    = fraction;
        } else {
            block = fraction>>(maxlevel-level);
        }
        node = btnt2btn( root, level, block );
        graph->contents[i] = node->content;
        fraction += 1<<level;
    }

    return maxlevel;
}