hash.c

Microsoft Visual C++ 6.0环境下的无损压缩测试工程

/* Name : hash.c
 *
 * Notes: This file contains all of the routines needed to maintain and
 *        access the hash structures used by my LZ77 data compression
 *        routines.
 *
 *      $Log:	hash.c,v $
 * Revision 1.3  95/07/18  15:38:41  idr
 * Changed the way the OS dependant memory allocation works.  Fixed a bug in
 * the code that creates the hash value that would crash machines that expect
 * word data to be at a word boundry.
 * 
 * Revision 1.2  1995/07/18  10:23:03  idr
 * This version appears to be fully function and somewhat bug free. :)
 */

#include "stdtypes.h"
#include "lists.h"

#include <stdlib.h>
#include <stdio.h>
#include <assert.h>

#define HASH_BITS   (16)
#define HASH_SIZE   (1L << HASH_BITS)

#define HASH_KEY(b) (0x0000ffff & ((b[0] << 8) | (b[1])))

#ifdef AMIGA
#include <exec/memory.h>
#define allocate(size)   AllocVec(size,MEMF_ANY)
#define deallocate(mem)  FreeVec(mem)
#else
#define allocate(size)   malloc(size)
#define deallocate(mem)  free(mem)
#endif

#ifndef HAVE_INLINE
#define __inline__
#endif



/******************************************************************************/
/* Name : struct HashNode, struct HashTable
 *
 * Notes: These two structures form the basis of my hashing routines.  The
 *        hash table is made up of one HashTable structure that contains
 *        an array of linked lists of HashNode structures.
 */

struct HashNode
{
    struct MinNode  h_Node;         /* Node linkage monkey stuff.           */
    ULONG           h_Offset;       /* Offset in stream of node's data.     */
};




struct HashTable
{
    struct MinList  * ht_Lists;     /* Array of lists of hash nodes.        */
    struct HashNode * ht_Nodes;     /* Array of all hash nodes.             */
    ULONG             ht_NodeCount; /* Total number of nodes in ht_Nodes.   */
    ULONG             ht_NextNode;  /* Next node index to re-use.           */
    ULONG             ht_Offset;    /* Offset in stream to hash.            */
};




struct Match
{
    UWORD   m_Length;
    LONG    m_Offset;
};




struct MinList * lists;
struct HashTable * ght;

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

__inline__ int NodeGood( struct HashTable * ht, struct HashNode * n )
{
    struct HashNode * lastNode;

    lastNode = &(ht->ht_Nodes[ ht->ht_NodeCount ]);
    return( (n >= ht->ht_Nodes) && (n < lastNode) );
}




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

__inline__ int ListGood( struct HashTable * ht, struct MinList * l )
{
    struct MinList * lastList;

    lastList = &(ht->ht_Lists[ HASH_SIZE ]);
    return( (l >= ht->ht_Lists) && (l < lastList) );
}




/******************************************************************************/
/* Name : AllocHashTable()
 *
 * Notes: This function is used to allocate and initialize a hash table.
 *
 */

APTR AllocHashTable( ULONG numHashNodes )
{
    struct HashTable * table;
    struct MinList   * listArray;
    long               lcv;


    table = allocate( (numHashNodes * sizeof( struct HashNode ))
                      + sizeof( struct HashTable ) );

    if ( table != NULL )
    {
        listArray = allocate( HASH_SIZE * sizeof( struct MinList ) );
        if ( listArray == NULL )
        {
            deallocate( table );
            return( NULL );
        }


        for ( lcv = 0L ; lcv < HASH_SIZE ; lcv++ )
        {
            NewList( (struct List *) &( listArray[ lcv ] ) );
        }


        table->ht_Lists     = listArray;
        table->ht_Nodes     = (struct HashNode *) (table + 1);
        table->ht_NodeCount = numHashNodes;
        table->ht_NextNode  = 0L;
        table->ht_Offset    = 0L;

        lists = table->ht_Lists;
        ght   = table;
        printf( __FILE__ ",%ld: table->ht_Lists = 0x%08lx\n", (long)__LINE__,
                (long)table->ht_Lists );
    }


    return( table );
}




/******************************************************************************/
/* Name : FreeHashTable()
 *
 * Notes: This function is used to free a hash table that was previously
 *        allocated with AllocHashTable().
 */

void FreeHashTable( struct HashTable * table )
{
    deallocate( table->ht_Lists );
    deallocate( table );
}




/******************************************************************************/
/* Name : GetNextHashNode()
 *
 * Notes: This function is used to get a pointer to the next available hash
 *        node to add to the hash table.
 */

struct HashNode * GetNextHashNode( struct HashTable * table )
{
    struct HashNode * node;


    node = &( table->ht_Nodes[ table->ht_NextNode ] );

    if ( table->ht_Offset > table->ht_NodeCount )
    {
        Remove( (struct Node *) node );
    }


    table->ht_NextNode++;
    if ( table->ht_NextNode == table->ht_NodeCount )
    {
        table->ht_NextNode = 0L;
    }


    assert( NodeGood( table, node ) );
    return( node );
}




/******************************************************************************/
/* Name : UpdateHashTable()
 *
 * Notes: This function is used to add the specified number of characters to the
 *        specified hash table.
 */

void UpdateHashTable( struct HashTable * table, UBYTE * stream, ULONG numChars )
{
    struct HashNode * node;
    ULONG             hashValue;


    /* The numChars specifies the number of bytes to be added to the list.
     * For each of these bytes we will calculate a hash value, fetch a new
     * hash node, and add the node to the correct position in the table.
     */

    assert( lists == table->ht_Lists );
    for ( /* empty */ ; numChars > 0 ; numChars-- )
    {
        /* Fetch and initialize the next available hash node. */

        node = GetNextHashNode( table );
        node->h_Offset = table->ht_Offset;


        /* Fetch the next hash value and update both the stream pointer and
         * the current offset value.
         */

        hashValue = HASH_KEY( stream );
        stream++;
        table->ht_Offset++;


        /* Finally, add the new hash node to the proper list in the hash
         * table.
         */

        assert( lists == table->ht_Lists );
        AddHead( (struct List *) &( table->ht_Lists[ hashValue ] ),
                 (struct Node *) &( node->h_Node ) );
    }

}




/******************************************************************************/
/* Name : FindHashMatch()
 *
 * Notes: This function searches the specified hash table for the string that
 *        best matches the caller supplied string.
 */

struct Match FindHashMatch( struct HashTable * table, const UBYTE * stream, 
                            ULONG maxLength, const UBYTE * buffer )
{
    ULONG             hashValue;
    struct Match      bestMatch;
    struct HashNode * node;
    struct HashNode * next;
    ULONG             length;
    const UBYTE     * matchPoint;


    hashValue = HASH_KEY( stream );
    bestMatch.m_Length = 0;


    for ( node = (struct HashNode *) table->ht_Lists[ hashValue ].mlh_Head
          ; (next = (struct HashNode *) node->h_Node.mln_Succ) != NULL
          ; node = next )
    {
        /* The first step is to calculate how long this match is.  We can
         * skip the first two characters because we KNOW that the match must
         * be at least two bytes long.
         */

        matchPoint = &( buffer[ node->h_Offset - table->ht_Offset ] );
        length = 2L;

        while ( (matchPoint[ length ] == stream[ length ])
                && (length <= maxLength) )
        {
            length++;
        }


        /* If this match is longer than any previous match, then we need to
         * update the bestMatch value.
         */

        if ( length > bestMatch.m_Length )
        {
            bestMatch.m_Length = length;
            bestMatch.m_Offset = node->h_Offset - table->ht_Offset;

            /* If the current match is as long as a match can possibly
             * be, then we can quit searching for a longer match now.
             */

            if ( length == maxLength )
            {
                bestMatch.m_Length = length;
                break;
            }   /* if ( length == maxLength )         ... */
        }       /* if ( length > bestMatch.m_Length ) ... */

        assert( lists == table->ht_Lists );

    }           /* for ( node = (struct HashNode *)   ... */


    assert( lists == table->ht_Lists );
    return( bestMatch );
}