huff.c

在linux环境下可以直接编译运行.C语言版.

	else
	    ZeroPtr->Parent->LeftChild = NewInternal;

	if(NewInternal->RightBlock->Weight == 1) {
	    NewInternal->MyBlock = NewInternal->RightBlock->MyBlock;
	}
	ThisZero->MyBlock = NewInternal->MyBlock;
    }

    Huff_Eliminate_Zero(H, ThisZero);

    NewInternal->LeftChild = H->RemainingZeros;

    ThisZero->RightBlock = NewInternal;
    ThisZero->LeftBlock = H->RemainingZeros;
    ThisZero->Parent = NewInternal;
    ThisZero->LeftChild = NULL;
    ThisZero->RightChild = NULL;

    H->RemainingZeros->Parent = NewInternal;
    H->RemainingZeros->RightBlock = ThisZero;

    return ThisZero;
}

/*
 * Huff_Find_Nth_Zero --
 *
 *     When a zero frequency element is encoded, it is followed by the
 *     binary representation of the index into the remaining elements.
 *     Sets a cache to the element before it so that it can be removed
 *     without calling this procedure again.
 */
static unsigned int Huff_Find_Nth_Zero(HuffStruct* H, int n)
{
    HuffNode *TargetPtr = H->Alphabet + n, *HeadPtr = H->RemainingZeros;
    unsigned int index = 0;

    while(TargetPtr != HeadPtr) {
	HeadPtr = HeadPtr->RightChild;
	index += 1;
    }

    return index;
}

/*
 * Huff_Eliminate_Zero --
 *
 *     Splices node out of the list of zeros.
 */
static void Huff_Eliminate_Zero(HuffStruct* H, HuffNode *node)
{
    if(H->ZeroFreqCount == 1)
	return;

    Huff_Factor_Remaining(H);

    if(node->LeftChild == NULL) {
	H->RemainingZeros = H->RemainingZeros->RightChild;
	H->RemainingZeros->LeftChild = NULL;
    } else if(node->RightChild == NULL) {
	node->LeftChild->RightChild = NULL;
    } else {
	node->RightChild->LeftChild = node->LeftChild;
	node->LeftChild->RightChild = node->RightChild;
    }
}

/*
 * Huff_Init_Node --
 */
static void Huff_Init_Node(HuffNode *node, int i, int Size)
{
    if(i < Size - 1)
	node->RightChild = node + 1;
    else
	node->RightChild = NULL;
    if(i >= 1)
	node->LeftChild = node - 1;
    else
	node->LeftChild = NULL;
    node->Weight = 0;
    node->Parent = NULL;
    node->RightBlock = NULL;
    node->LeftBlock = NULL;
    node->MyBlock = NULL;
}

/*
 * Huff_Swap_Ptrs --
 */
static void Huff_Swap_Ptrs(HuffNode **one, HuffNode **two)
{
    HuffNode *tmpone, *tmptwo;

    tmpone = *one;
    tmptwo = *two;

    *one = tmptwo;
    *two = tmpone;
}

/*
 * Huff_Make_Block --
 *
 *     The data structure used is an array of blocks, which are unions
 *     of free pointers and huffnode pointers.  free blocks are a linked
 *     list of free blocks, the front of which is H->FreeBlock.  The
 *     used blocks are pointers to the head of each block.
 */
static Block* Huff_Make_Block(HuffStruct *H, HuffNode* lead)
{
    Block *ret = H->FreeBlock;

    ASSERT(H->FreeBlock != NULL, "out of blocks");

    H->FreeBlock = H->FreeBlock->un.un_freeptr;

    ret->un.un_leader = lead;

    return ret;
}

/*
 * Huff_Free_Block --
 *
 *     Restores the block to the front of the free list.
 */
static void Huff_Free_Block(HuffStruct *H, Block *b)
{
    b->un.un_freeptr = H->FreeBlock;
    H->FreeBlock = b;
}

/*
 * Huff_Factor_Remaining --
 *
 *     sets ZeroFreqCount, ZeroFreqRem, and ZeroFreqExp to satsity the
 *     equation given above.
 */
static void Huff_Factor_Remaining(HuffStruct *H)
{
    unsigned int i;

    i = (H->ZeroFreqCount -= 1);
    H->ZeroFreqExp = 0;

    while(i > 1) {
	H->ZeroFreqExp += 1;
	i >>= 1;
    }

    i = 1 << H->ZeroFreqExp;

    H->ZeroFreqRem = H->ZeroFreqCount - i;
}

/* Huff_Decode_Bit()
 *
 * receives a bit at a time and returns true when a complete code has
 * been received.
 */
int Huff_Decode_Bit(HuffStruct* H, Bit b)
{
    if(H->IsAdaptive && H->DecodePtr->Weight == 0) {
	int bitsreq;
	if(H->ZeroFreqRem == 0) {
	    bitsreq = H->ZeroFreqExp;
	} else {
	    bitsreq = H->ZeroFreqExp + 1;
	}
	H->CodedBits[H->CodedDepth] = b;
	H->CodedDepth += 1;
	if(H->CodedDepth >= bitsreq) {
	    return 1;
	} else {
	    return 0;
	}
    } else {
	if(b)
	    H->DecodePtr = H->DecodePtr->RightChild;
	else
	    H->DecodePtr = H->DecodePtr->LeftChild;

	if(H->DecodePtr->LeftChild == NULL)
	    return H->DecodePtr->Weight != 0;
	else
	    return 0;
    }
}

/*
 * Huff_Nth_Zero --
 */
static int Huff_Nth_Zero(HuffStruct* H, int n)
{
    HuffNode *Ret = H->RemainingZeros;

    while(n > 0) {
	Ret = Ret->RightChild;
	n -= 1;
    }
    return Ret - H->Alphabet;
}

/* Huff_Decode_Data()
 *
 * once ReceiveBit returns 1, this retrieves an index into the
 * alphabet otherwise this returns 0, indicating more bits are
 * required.
 */
int Huff_Decode_Data(HuffStruct* H)
{
    unsigned int elt = H->DecodePtr - H->Alphabet;

    if(H->IsAdaptive && H->DecodePtr->Weight == 0) {
	int i;
	unsigned int n = 0;
	for(i = 0; i < H->CodedDepth - 1; i += 1) {
	    n |= H->CodedBits[i];
	    n <<= 1;
	}
	n |= H->CodedBits[i];
	elt = Huff_Nth_Zero(H, n);
    }

    H->CodedDepth = 0;

    if(H->IsAdaptive)
	Huff_Update_Tree(H, elt);

    H->DecodePtr = H->RootNode;

    return elt;
}

/* Huff_Delete()
 *
 * deletion.
 */
void Huff_Delete(HuffStruct* H)
{
    free(H->Alphabet);
    free(H->CodedBits);
    free(H->BlockArray);
    free(H);
}

/* Huff_Dump_Stats()
 *
 * write a table.
 */
int Huff_Dump_Stats(HuffStruct* H,
		    const char* filename)
{
    FILE* outfile;
    int i;

    outfile = fopen(filename, "w");

    if(outfile == NULL) {
	perror(ERROR_MSG_HEADER"Fopen failed on stats file");
	return 0;
    }

    fprintf(outfile, "%d ", H->AlphabetSize);

    for(i = 0; i < H->AlphabetSize; i += 1) {
	fprintf(outfile, "%d ", H->Alphabet[i].Weight);
    }

    fclose(outfile);

    return 1;
}

/*
 * Huff_Read_Stats --
 *
 *     Takes a huffstruct and reads the stats file, using the adaptive
 *     routines to build a tree with the correct frequencies.  this is
 *     slower than it could be, but it is assumed that read stats will
 *     only be used in training.
 */
static int Huff_Read_Stats(HuffStruct *H,
			   int AlphabetSize,
			   const char* filename)
{
    FILE* infile = fopen(filename, "r");
    int index = 0;
    int freq;
    int i;

    if(!infile) {
	perror(ERROR_MSG_HEADER"Failed opening stats file");
	return 0;
    }

    if(fscanf(infile, "%d", &freq) != 1) {
	fprintf(stderr, ERROR_MSG_HEADER "Illegal stats file\n");
	return 0;
    }

    if(AlphabetSize != freq) {
	fprintf(stderr, ERROR_MSG_HEADER "Inconsistent alphabet size\n");
	return 0;
    }

    while(index < AlphabetSize) {
	if( fscanf(infile, "%d", &freq) != 1) {
	    fprintf(stderr, ERROR_MSG_HEADER "Illegal stats file\n");
	    return 0;
	}

	for(i = 0; i < freq; i += 1) {
	    Huff_Encode_Data(H, index);
	}

	index += 1;
    }

    fclose(infile);

    return 1;
}

#ifdef DEBUG
int main()
{
    HuffStruct* encoder = Huff_Initialize_Adaptive_Encoder(10);
    int i, j;

    FILE* foo = fopen("/dev/null", "w");

    for(i = 0; i < 10; i += 1) {
	/*for(j = i; j >= 0; j -= 1) { */
	    write_byte(encoder, foo, i);
	    /*} */
    }
}

void print_node(HuffStruct *H, HuffNode *node)
{
    HuffNode *off = H->Alphabet;

    fprintf(stderr, "#<%d (%d) %d> ", /*"#<%snode %d lc %d rc %d w %d l %d> ", */

/* lb %d rb %d p %d  */
/*	    (node == H->RemainingZeros ? "zeros " : ""), */
	    (int)(node - off),
/*	    (node->LeftChild ? (int)(node->LeftChild - off) : -1),
	    (node->RightChild ? (int)(node->RightChild - off) : -1),
	    (node->LeftBlock ? (int)(node->LeftBlock - off) : -1),
	    (node->RightBlock ? (int)(node->RightBlock - off) : -1),
	    (node->Parent ? (int)(node->Parent - off) : -1), */
	    (int)node->Weight,
	    (node->MyBlock ? (int)(node->MyBlock->un.un_leader - off) : -1));
}

int print_depth(HuffStruct *H, HuffNode* node, int d)
{
    if(node == H->RemainingZeros) {
	if(d == 0) {
	    print_node(H, node);
	}
	return 0;
    }

    if(d == 0) {
	print_node(H, node);
	return 1;
    } else {
	int l, r;

	if(node->LeftChild == NULL)
	    l = 0;
	else
	    l = print_depth(H, node->LeftChild, d - 1);

	if(node->RightChild == NULL)
	    r = 0;
	else
	    r = print_depth(H, node->RightChild, d - 1);

	return r + l;
    }
}

void print_tree(HuffStruct *H)
{
    int d = 0;

    while(print_depth(H, H->RootNode, d) > 0)
    {
	fprintf(stderr, "\n");
	d += 1;
    }
}
#endif


/* returns an initialized Adaptive Huffman decoder for an alphabet
 * with the given size.  returns NULL if enough memory cannot be
 * allocated.  */
HuffStruct* Huff_Initialize_Adaptive_Decoder(int AlphabetSize);

/* No iterface is provided for training a set of data while decoding,
 * though this would be easy to implement */

/* returns an initialized Fixed Huffman decoder for an alphabet
 * with the given size. */
HuffStruct* Huff_Initialize_Fixed_Decoder(int AlphabetSize,
					  HuffNode* table);