huffman.cpp

A*算法 A*算法 A*算法 A*算法A*算法A*算法

			p_prev = PTR_NOT(p_prev);
		} else {
			p_prev += (p_item1 - p_item1->next->prev);
		}

		p_prev->next = p_next;
		p_next->prev = p_prev;
		p_item1->next = NULL;
		p_item1->prev = NULL;
	}
	pp_item = &ht->first;				/* ESI */
	if (value > 1) {

		/* ECX = ht->first->next; */
		p_item1->next = *pp_item;
		p_item1->prev = (*pp_item)->prev;

		(*pp_item)->prev = p_item2;
		*pp_item = p_item1;

		p_item2->parent = NULL;
		p_item2->child  = NULL;
	} else {
		p_item1->next = (struct huffman_tree_item *)pp_item;
		p_item1->prev = pp_item[1];
		/* EDI = ht->item305C; */
		p_prev = pp_item[1];			/* ECX */
		if (p_prev <= 0) {
			p_prev = PTR_NOT(p_prev);
			p_prev->next = p_item1;
			p_prev->prev = p_item2;

			p_item2->parent = NULL;
			p_item2->child  = NULL;
		} else {
			if (PTR_INT(ht->item305C) < 0) {
				p_prev += (struct huffman_tree_item *)pp_item - (*pp_item)->prev;
			} else {
				p_prev += PTR_INT(ht->item305C);
			}

			p_prev->next    = p_item1;
			pp_item[1]      = p_item2;
			p_item2->parent = NULL;
			p_item2->child  = NULL;
		}
	}
	return p_item2;
}

static void libmpq_huff_call1500E820(struct huffman_tree *ht, struct huffman_tree_item *p_item) {
	struct huffman_tree_item *p_item1;		/* EDI */
	struct huffman_tree_item *p_item2 = NULL;	/* EAX */
	struct huffman_tree_item *p_item3;		/* EDX */
	struct huffman_tree_item *p_prev;		/* EBX */

	for (; p_item != NULL; p_item = p_item->parent) {
		p_item->byte_value++;

		for (p_item1 = p_item; ; p_item1 = p_prev) {
			p_prev = p_item1->prev;
			if (PTR_INT(p_prev) <= 0) {
				p_prev = NULL;
				break;
			}
			if (p_prev->byte_value >= p_item->byte_value) {
				break;
			}
		}

		if (p_item1 == p_item) {
			continue;
		}

		if (p_item1->next != NULL) {
			p_item2 = libmpq_huff_get_prev_item(p_item1, -1);
			p_item2->next = p_item1->next;
			p_item1->next->prev = p_item1->prev;
			p_item1->next = NULL;
			p_item1->prev = NULL;
		}
		p_item2 = p_item->next;
		p_item1->next = p_item2;
		p_item1->prev = p_item2->prev;
		p_item2->prev = p_item1;
		p_item->next = p_item1;
		if ((p_item2 = p_item1) != NULL) {
			p_item2 = libmpq_huff_get_prev_item(p_item, -1);
			p_item2->next = p_item->next;
			p_item->next->prev = p_item->prev;
			p_item->next = NULL;
			p_item->prev = NULL;
		}

		if (p_prev == NULL) {
			p_prev = PTR_PTR(&ht->first);
		}
		p_item2       = p_prev->next;
		p_item->next  = p_item2;
		p_item->prev  = p_item2->prev;
		p_item2->prev = p_item;
		p_prev->next  = p_item;

		p_item3 = p_item1->parent->child;
		p_item2 = p_item->parent;
		if (p_item2->child == p_item) {
			p_item2->child = p_item1;
		}

		if (p_item3 == p_item1) {
			p_item1->parent->child = p_item;
		}

		p_item2 = p_item->parent;
		p_item->parent  = p_item1->parent;
		p_item1->parent = p_item2;
		ht->offs0004++;
	}
}

__int32 libmpq_huff_do_decompress(struct huffman_tree *ht, struct huffman_input_stream *is, unsigned char *out_buf, unsigned int out_length) {
	unsigned int n8bits;				/* 8 bits loaded from input stream */
	unsigned int n7bits;				/* 7 bits loaded from input stream */
	unsigned int found;				/* Thats needed to replace the goto stuff from original source :) */
	unsigned int dcmp_byte = 0;
	unsigned long bit_count;
	struct huffman_decompress *qd;
	unsigned int has_qd;				/* Can we use quick decompression? */
	struct huffman_tree_item *p_item1 = NULL;
	struct huffman_tree_item *p_item2 = NULL;
	unsigned char *out_pos = out_buf;

	/* Test the output length. Must not be non zero. */
	if (out_length == 0) {
		return 0;
	}

	/* Get the compression type from the input stream. */
	n8bits = libmpq_huff_get_8bits(is);

	/* Build the Huffman tree */
	libmpq_huff_build_tree(ht, n8bits);
	ht->cmp0 = (n8bits == 0) ? TRUE : FALSE;

	for(;;) {
		n7bits = libmpq_huff_get_7bits(is);	/* Get 7 bits from input stream */

		/*
		 * Try to use quick decompression. Check huffman_decompress array for corresponding item.
		 * If found, use the result byte instead.
		 */
		qd = &ht->qd3474[n7bits];

		/* If there is a quick-pass possible (ebx) */
		has_qd = (qd->offs00 >= ht->offs0004) ? TRUE : FALSE;

		/* If we can use quick decompress, use it. */
		if (has_qd) {
			found = 0;
			if (qd->bits > 7) {
				is->bit_buf >>= 7;
				is->bits -= 7;
				p_item1 = qd->p_item;
				found = 1;
			}
			if (found == 0) {
				is->bit_buf >>= qd->bits;
				is->bits     -= qd->bits;
				dcmp_byte     = qd->dcmp_byte;
			}
		} else {
			found = 1;
			p_item1 = ht->first->next->prev;
			if (PTR_INT(p_item1) <= 0) {
				p_item1 = NULL;
			}
		}

		if (found == 1) {
			bit_count = 0;
			p_item2 = NULL;
			do {
				p_item1 = p_item1->child;	/* Move down by one level */
				if (libmpq_huff_get_bit(is)) {	/* If current bit is set, move to previous */
					p_item1 = p_item1->prev;
				}
				if (++bit_count == 7) {		/* If we are at 7th bit, save current huffman tree item. */
					p_item2 = p_item1;
				}
			} while (p_item1->child != NULL);	/* Walk until tree has no deeper level */

			if (has_qd == FALSE) {
				if (bit_count > 7) {
					qd->offs00 = ht->offs0004;
					qd->bits   = bit_count;
					qd->p_item = p_item2;
				} else {
					unsigned long index = n7bits & (0xFFFFFFFF >> (32 - bit_count));
					unsigned long add   = (1 << bit_count);

					for (qd = &ht->qd3474[index]; index <= 0x7F; index += add, qd += add) {
						qd->offs00    = ht->offs0004;
						qd->bits      = bit_count;
						qd->dcmp_byte = p_item1->dcmp_byte;
					}
				}
			}
			dcmp_byte = p_item1->dcmp_byte;
		}

		if (dcmp_byte == 0x101)	{		/* Huffman tree needs to be modified */
			n8bits  = libmpq_huff_get_8bits(is);
			p_item1 = (ht->last <= 0) ? NULL : ht->last;

			p_item2 = libmpq_huff_call1500E740(ht, 1);
			p_item2->parent     = p_item1;
			p_item2->dcmp_byte  = p_item1->dcmp_byte;
			p_item2->byte_value = p_item1->byte_value;
			ht->items306C[p_item2->dcmp_byte] = p_item2;

			p_item2 = libmpq_huff_call1500E740(ht, 1);
			p_item2->parent     = p_item1;
			p_item2->dcmp_byte  = n8bits;
			p_item2->byte_value = 0;
			ht->items306C[p_item2->dcmp_byte] = p_item2;

			p_item1->child = p_item2;
			libmpq_huff_call1500E820(ht, p_item2);
			if (ht->cmp0 == 0) {
				libmpq_huff_call1500E820(ht, ht->items306C[n8bits]);
			}
			dcmp_byte = n8bits;
		}

		if (dcmp_byte == 0x100) {
			break;
		}

		*out_pos++ = (unsigned char)dcmp_byte;
		if (--out_length == 0) {
			break;
		}
		if (ht->cmp0) {
			libmpq_huff_call1500E820(ht, ht->items306C[dcmp_byte]);
		}
	}
	return __int32(out_pos - out_buf);
}

int libmpq_huff_init_tree(struct huffman_tree *ht, struct huffman_tree_item *hi, unsigned int cmp) {
	int count;

	/* Clear links for all the items in the tree */
	for (hi = ht->items0008, count = 0x203; count != 0; hi++, count--) {
		hi->next = hi->prev = NULL;
	}

	ht->item3050 = NULL;
	ht->item3054 = PTR_PTR(&ht->item3054);
	ht->item3058 = PTR_NOT(ht->item3054);

	ht->item305C = NULL;
	ht->first    = PTR_PTR(&ht->first);
	ht->last     = PTR_NOT(ht->first);

	ht->offs0004 = 1;
	ht->items    = 0;

	/* Clear all huffman_decompress items. Do this only if preparing for decompression */
	if (cmp == LIBMPQ_HUFF_DECOMPRESS) {
		for (count = 0; count < sizeof(ht->qd3474) / sizeof(struct huffman_decompress); count++) {
			ht->qd3474[count].offs00 = 0;
		}
	}
	return 0;
}