/***************************************************************************
  che3.h  -  HE3 compression and decompression (for old format filelists)
                             -------------------
    begin                : ?
    copyright            : (C) 2001 Eric Prevoteau
    copyright            : (C) 2002-2005 Mathias Küster
 ***************************************************************************/

/***************************************************************************
 *                                                                         *
 *   This program is free software; you can redistribute it and/or modify  *
 *   it under the terms of the GNU General Public License as published by  *
 *   the Free Software Foundation; either version 2 of the License, or     *
 *   (at your option) any later version.                                   *
 *                                                                         *
 ***************************************************************************/

#ifndef __HE3_H__
#define __HE3_H__

/**
 * This class compresses and decompresses ".DcLst" old format
 * filelists, which are based on Huffman encoding.
 *
 * The compression is probably worse than zlib, plus it
 * seems to be orientated on bits rather than bytes making
 * it horrible to implement.
 */
#include <dclib/dcos.h>

class CByteArray;
class CString;

typedef struct hufnode
{
	unsigned long occur;
	struct hufnode *left,*right;		/* son nodes (left and right are both either not null or either null) */
	unsigned char val;					/* if left&right!=NULL, val is the encoded character, else, it has no usage */
} HUFNODE;

typedef struct
{
	unsigned int bits_len;				/* number of bits in the bitfield used to encode the value */
	unsigned long bits;					/* bitfield containing the encoding pattern */
												/* a N bits_len pattern is stored inside bits from bit N-1 to bit 0 */
} HUFENCODE;

class CHE3 {
public:
	/**************************************************/
	/* decompress data compressed using HE3 algorithm */ 
	/**********************************************************/
	/* input: a GByteArray containing HE3 compressed data     */
	/* output: a GString containing uncompressed data or NULL */
	/**********************************************************/
	CString *decode_he3_data(CByteArray *data);

	/*****************************************************************************************/
	/* compress data compressed using an Huffman algorithm and store it in HE3 usable format */
	/*****************************************************************************************/
	/* input: a GString containing a string to compress        */
	/* output: a GByteArray containing compressed data or NULL */
	/***********************************************************/
	CByteArray *encode_he3_data(const CString *str);

private:
	unsigned long get_bit(unsigned char *data, unsigned long *cur_pos);
	unsigned long get_bits(unsigned char *data, unsigned long *cur_pos, int nb_bit);
	static int huf_insert_glist(void * a, void * b);
	void use_hufnode(HUFENCODE tbl_enc[256], HUFNODE *node,unsigned int bits_len, unsigned long bits);
	void free_hufnode(HUFNODE *node);
	CByteArray *add_bit(CByteArray *data, unsigned long *bit_pos, unsigned char bit_value);
	CByteArray *add_bits(CByteArray *data, unsigned long *bit_pos, unsigned long pattern, unsigned int pattern_length);
};

#endif
