Compression lzw

Soyez le premier à donner votre avis sur cette source.

Vue 15 227 fois - Téléchargée 1 827 fois

Description

Ce programme permet de compresser / décompresser des fichiers selon l'algorithme LZW.

Utilisation :
-Entrer le fichier source et destination.
-Cliquer sur compresser ou Décompresser.

Source / Exemple :


/******************************************************************************\
|* LZW.c : fonctions pour la compression / décompression de fichiers selon    *|
|*         l'algorithme LZW.                                                  *|
\******************************************************************************/

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

#include "LZW.h"

/*============================================================================*\
|* Variables du module.                                                       *|
\*============================================================================*/

static TBuffer*	m_Dico;				/* dictionnaire, tableau de taille
									   MAX_DICO_LENGTH */
static WORD		m_DicoIndex;		/* indice en cours dans le dico */

static WORD**	m_TabIndex;			/* tableau des index pour chaque taille,
									   tableau de taille
									   MAX_BUFFER_LENGTH * MAX_DICO_LENGTH */

static WORD*	m_NbTabIndex;		/* nombre de valeur dans chaque sous-tableau
									   tableau de taille MAX_BUFFER_LENGTH */

static TBuffer	m_Latent;			/* buffer latent */
static TBuffer	m_Buffer;			/* buffer actuel */

static BYTE		m_BitBuffer;		/* buffer pour lecture / écriture par bit */
static BYTE		m_BitBufferSize;	/* nombre de bits placés dans le buffer   */

static TBuffer	m_WriteBuffer;		/* buffer pour l'écriture */
static FILE*	m_pWriteFile;		/* fichier où écrire      */

static TBuffer	m_ReadBuffer;		/* buffer pour la lecture           */
static WORD		m_ReadBufferIndex;	/* position actuelle dans ce buffer */
static FILE*	m_pReadFile;		/* fichier où lire                  */

static int		m_Mode;				/* mode en cours               */
static DWORD	m_JobCurrent;		/* travail déjà fait           */
static DWORD	m_JobTotal;			/* travail total à faire       */
static DWORD	m_dwInSize;			/* taille du fichier d'entrée  */
static DWORD	m_dwOutSize;		/* taille du fichier de sortie */

/*============================================================================*\
|* Déclaration des fonctions globales.                                        *|
\*============================================================================*/
int LZW				(char* lpszInFile, char* lpszOutFile);
int UnLZW			(char* lpszInFile, char* lpszOutFile);
int GetJobTotal		();
int GetJobCurrent	();
int GetInSize		();
int GetOutSize		();

/*============================================================================*\
|* Déclaration des fonctions du module.                                       *|
\*============================================================================*/
static int	Init			(char* lpszInFile, char* lpszOutFile);
static void Free			();

static int	DoLZW			();
static int	DoUnLZW			();

static int	InitDico		();
static void	ResetDico		();
static void	DeleteDico		();
static int	FindInDico		(TBuffer* pBuffer);
static int	WriteInDico		(TBuffer* pBuffer);

static int	WriteBits		(DWORD* pData, BYTE size);
static int	FlushBits		();
static int	ReadBits		(DWORD* pData, BYTE size);
static int	WriteFile		(BYTE* pData);
static int	ReadFile		(BYTE* pData);

/******************************************************************************\
|* LZW : compression d'un fichier.                                            *|
|* entrée : lpszInFile  : nom du fichier d'entrée.                            *|
|*          lpszOutFile : nom du fichier de sortie.                           *|
|* retour : LZW_SUCCESS (0) si la compression a réussi, un code d'erreur (<0) *|
|*          sinon.                                                            *|
\******************************************************************************/
int LZW(char* lpszInFile, char* lpszOutFile)
{
	/* variables locales */
	int result;

	/* initialisation de la compression */
	m_Mode = COMPRESS;
	result = Init(lpszInFile, lpszOutFile);
	if(result != LZW_SUCCESS)
	{
		Free();
		return result;
	}

	/* taille du fichier à lire, nombre d'octets déjà lus */
	fseek(m_pReadFile, 0, SEEK_END);
	m_dwInSize = ftell(m_pReadFile);
	m_JobTotal = m_dwInSize;
	fseek(m_pReadFile, 0, SEEK_SET);
	m_JobCurrent = 0;

	/* on effectue le travail */
	result = DoLZW();
	if(result == LZW_SUCCESS)
		m_dwOutSize = ftell(m_pWriteFile);
	Free();
	return result;
}

/******************************************************************************\
|* UnLZW : décompression d'un fichier.                                        *|
|* entrée : lpszInFile  : nom du fichier d'entrée.                            *|
|*          lpszOutFile : nom du fichier de sortie.                           *|
|* retour : LZW_SUCCESS (0) si la décompression a réussi, un code d'erreur    *|
|*          (<0) sinon.                                                       *|
\******************************************************************************/
int UnLZW(char* lpszInFile, char* lpszOutFile)
{
	/* variables locales */
	int result;

	/* initialisation de la décompression */
	m_Mode = UNCOMPRESS;
	result = Init(lpszInFile, lpszOutFile);
	if(result != LZW_SUCCESS)
	{
		Free();
		return result;
	}

	/* taille du fichier à lire, nombre d'octets déjà lus */
	fseek(m_pReadFile, 0, SEEK_END);
	m_JobTotal = ftell(m_pReadFile);
	fseek(m_pReadFile, 0, SEEK_SET);
	m_JobCurrent = 0;

	/* on effectue le travail */
	result = DoUnLZW();
	Free();
	return result;
}

/******************************************************************************\
|* GetJobTotal : récupère la taille totale du fichier à lire.                 *|
|* retour : la taille du fichier d'entrée.                                    *|
\******************************************************************************/
int GetJobTotal()
{
	return m_JobTotal;
}

/******************************************************************************\
|* GetJobCurrent : récupère la portion du fichier d'entrée déjà traitée.      *|
|* retour : le nombre d'octets déjà traités.                                  *|
\******************************************************************************/
int GetJobCurrent()
{
	return m_JobCurrent;
}

/******************************************************************************\
|* GetInSize : récupère la taille du fichier d'entrée.                        *|
|* retour : la taille du fichier d'entrée.                                    *|
\******************************************************************************/
int GetInSize()
{
	return m_dwInSize;
}

/******************************************************************************\
|* GetOutSize : récupère la taille du fichier de sortie.                      *|
|* retour : la taille du fichier de sortie.                                   *|
\******************************************************************************/
int GetOutSize()
{
	return m_dwOutSize;
}

/******************************************************************************\
|* DoLZW : effectue le travail de compression après que l'initialisation soit *|
|*         faite.                                                             *|
|* retour : LZW_SUCCESS (0) si la compression a réussi, un code d'erreur (<0) *|
|*          sinon.                                                            *|
\******************************************************************************/
int DoLZW()
{
	/* variables locales */
	BYTE currentByte, nbBits;
	WORD nbData, rest;
	DWORD data;
	int index;

	/* nombre de bits utilisés pour le codage (MIN_BITS à MAX_BITS) */
	nbBits = MIN_BITS;

	/* lecture premier octet du fichier, on le met dans le buffer latent */
	if(!ReadFile(&currentByte))
		return LZW_ERROR_READ;
	m_Latent.m_pData[0]	= currentByte;
	m_Latent.m_NbData	= 1;

	/*------------------------------------------------------------------------*/
	/* boucle de lecture du fichier */
	while(1)
	{
		/* récupération prochain octet */
		if(!ReadFile(&currentByte))
			break;
		
		/* ajout de l'octet lu et du buffer latent dans le buffer courant */
		nbData = m_Latent.m_NbData;
		memcpy(m_Buffer.m_pData, m_Latent.m_pData, nbData);
		m_Buffer.m_pData[nbData]	= currentByte;
		m_Buffer.m_NbData			= nbData + 1;

		/* recherche de la chaine dans le dictionnaire */
		if(FindInDico(&m_Buffer) >= 0)
		{
			/* latent = buffer */
			memcpy(m_Latent.m_pData, m_Buffer.m_pData, m_Buffer.m_NbData);
			m_Latent.m_NbData = m_Buffer.m_NbData;
		}
		else
		{
			/* écrire la chaîne dans le dictionnaire */
			if(!WriteInDico(&m_Buffer))
				return LZW_ERROR_MEM;

			/* rechercher la valeur du buffer latent dans le dictionnaire */
			index = FindInDico(&m_Latent);

			/* si latent n'est pas dans le dico, écrire latent (octet simple) */
			if(index < 0)
				index = m_Latent.m_pData[0];
			else
			{
				/* vérifier si le nombre de bits est suffisant */
				rest = index >> nbBits;
				while(rest)
				{
					/* Ecrire LZW_BIT_PLUS sur le fichier destination */
					data = LZW_BIT_PLUS;
					if(!WriteBits(&data, nbBits))
						return LZW_ERROR_WRITE;
					nbBits++;
					rest >>= 1;
				}
			}

			/* éciture des bits, latent = octet lu */
			if(!WriteBits(&index, nbBits))
				return LZW_ERROR_WRITE;
			m_Latent.m_pData[0]	= currentByte;
			m_Latent.m_NbData	= 1;

			/* si on arrive au bout du dico */
			if(m_DicoIndex == MAX_DICO_LENGTH)
			{
				/* Ecrire LZW_NEW_DIC sur le fichier destination */
				data = LZW_NEW_DIC;
				if(!WriteBits(&data, nbBits))
					return LZW_ERROR_WRITE;

				/* on réinitialise le dictionnaire */
				ResetDico();

				/* on réécrit le buffer dans le dico et on réinitialise le
				   nombre de bits */
				if(!WriteInDico(&m_Buffer))
					return LZW_ERROR_MEM;
				nbBits = MIN_BITS;
			}
		}
	}

	/*------------------------------------------------------------------------*/
	/* on écrit le buffer latent, s'il n'est pas dans le dico, écrire un
	   octet simple */
	index = FindInDico(&m_Latent);
	if(index < 0)
		index = m_Latent.m_pData[0];
	else
	{
		/* vérifier si le nombre de bits est suffisant */
		rest = index >> nbBits;
		while(rest)
		{
			/* Ecrire LZW_BIT_PLUS sur le fichier destination */
			data = LZW_BIT_PLUS;
			if(WriteBits(&data, nbBits))
				return LZW_ERROR_WRITE;
			nbBits++;
			rest >>= 1;
		}
	}

	/* écriture des bits, ajout fin de fichier, on termine le dernier octet
	   éventuel */
	data = LZW_EOF;
	if(!WriteBits(&index, nbBits) || !WriteBits(&data, nbBits))
		return LZW_ERROR_WRITE;
	if(!FlushBits())
		return LZW_ERROR_WRITE;

	/* lecture et écriture terminée */
	if(!WriteFile(NULL))
		return LZW_ERROR_WRITE;
	if(!ReadFile(NULL))
		return LZW_ERROR_READ;

	/* compression réussie */
	return LZW_SUCCESS;
}

/******************************************************************************\
|* DoUnLZW : effectue le travail de décompression après que l'initialisation  *|
|*           soit faite.                                                      *|
|* retour : LZW_SUCCESS (0) si la décompression a réussi, un code d'erreur    *|
|*          (<0) sinon.                                                       *|
\******************************************************************************/
int DoUnLZW()
{
	/* variables locales */
	WORD nbData;
	DWORD currentData;
	BYTE nbBits = MIN_BITS;

	/* lecture première donnée du fichier (c'est obligatoirement un caractère
	   normal), on le met dans le buffer latent */
	if(!ReadBits(&currentData, nbBits))
		return LZW_ERROR_READ;
	m_Latent.m_pData[0]	= (BYTE) currentData;
	m_Latent.m_NbData	= 1;

	/* boucle de traitement */
	while(1)
	{
		/* lecture donnée */
		if(!ReadBits(&currentData, nbBits))
			break;

		/* si fin de fichier */
		if(currentData == LZW_EOF)
			break;
		/* si nouveau dico */
		else if(currentData == LZW_NEW_DIC)
		{
			ResetDico();
			nbBits = MIN_BITS;
			continue;
		}
		/* si augmentation nombre de bits */
		else if(currentData == LZW_BIT_PLUS)
		{
			nbBits++;
			continue;
		}

		/* buffer = latent */
		nbData = m_Latent.m_NbData;
		memcpy(m_Buffer.m_pData, m_Latent.m_pData, nbData);

		/* si donnée pas dans le dico alors, le caractère à ajouter au buffer
		   est la latence. Se produit quand succession du même caractère */
		if(currentData == (DWORD) m_DicoIndex)
			m_Buffer.m_pData[nbData] = m_Latent.m_pData[0];
		else if(currentData < (DWORD) m_DicoIndex)
			m_Buffer.m_pData[nbData] = m_Dico[currentData].m_pData[0];
		else
			break;
		m_Buffer.m_NbData = nbData + 1;

		/* ajout de ce mot dans le dico */
		if(!WriteInDico(&m_Buffer))
			return LZW_ERROR_MEM;

		/* on écrit les caractères latents dans le fichier de sortie */
		if(fwrite(m_Latent.m_pData, 1, nbData, m_pWriteFile) != nbData)
			return LZW_ERROR_WRITE;

		// nouveu buffer latent
		memcpy(m_Latent.m_pData, m_Dico[currentData].m_pData,
					m_Dico[currentData].m_NbData);
		m_Latent.m_NbData = m_Dico[currentData].m_NbData;
	}

	/* si on n'a pas lu la fin du fichier */
	if(currentData != LZW_EOF)
		return LZW_ERROR_EOF;

	/* on écrit les caractères latents dans le fichier de sortie */
	if(fwrite(m_Latent.m_pData, 1, m_Latent.m_NbData, m_pWriteFile) !=
		m_Latent.m_NbData)
		return LZW_ERROR_WRITE;

	/* lecture et écriture terminée */
	if(!WriteFile(NULL))
		return LZW_ERROR_WRITE;
	if(!ReadFile(NULL))
		return LZW_ERROR_READ;

	/* décompression réussie */
	return LZW_SUCCESS;
}

/******************************************************************************\
|* Init : initialise la compression ou la décompression.                      *|
|* entrée : lpszInFile  : fichier d'entrée.                                   *|
|*          lpszOutFile : fichier de sortie.                                  *|
|* retour : LZW_SUCCESS (0) si l'initialisation a réussi, un code d'erreur    *|
|*          (<0) sinon.                                                       *|
\******************************************************************************/
int Init(char* lpszInFile, char* lpszOutFile)
{
	/* fichiers d'entrée et de sortie */
	m_pReadFile		= NULL;
	m_pWriteFile	= NULL;

	/* variables du dictionnaires */
	m_Dico			= NULL;
	m_DicoIndex		= 0;
	m_TabIndex		= NULL;
	m_NbTabIndex	= NULL;

	/* buffers latent et actuel */
	m_Latent.m_pData	= NULL;
	m_Buffer.m_pData	= NULL;

	/* buffers pour la lecture et l'écriture */
	m_ReadBuffer.m_pData	= NULL;
	m_WriteBuffer.m_pData	= NULL;
	m_BitBuffer				= 0;
	m_BitBufferSize			= 0;

	/* ouverture des fichiers */
	if(stricmp(lpszInFile, lpszOutFile) == 0)
		return LZW_ERROR_NAMES;
	m_pReadFile		= fopen(lpszInFile, "rb");
	m_pWriteFile	= fopen(lpszOutFile, "wb");
	if(m_pReadFile == NULL)
		return LZW_ERROR_INFILE;
	if(m_pWriteFile == NULL)
		return LZW_ERROR_OUTFILE;

	/* création buffer de lecture */
	m_ReadBuffer.m_pData = malloc(FILE_BUFFER_LENGTH);
	if(m_ReadBuffer.m_pData == NULL)
		return LZW_ERROR_MEM;
	m_ReadBuffer.m_Size		= FILE_BUFFER_LENGTH;
	m_ReadBuffer.m_NbData	= 0;
	m_ReadBufferIndex		= 0;

	/* création buffer d'écriture */
	m_WriteBuffer.m_pData = malloc(FILE_BUFFER_LENGTH);
	if(m_WriteBuffer.m_pData == NULL)
		return LZW_ERROR_MEM;
	m_WriteBuffer.m_Size	= FILE_BUFFER_LENGTH;
	m_WriteBuffer.m_NbData	= 0;
	
	/* création du dictionnaire */
	if(!InitDico())
		return LZW_ERROR_MEM;

	/* création buffer latent et actuel */
	m_Latent.m_pData	= malloc(MAX_BUFFER_LENGTH);
	m_Latent.m_Size		= MAX_BUFFER_LENGTH;
	m_Latent.m_NbData	= 0;
	m_Buffer.m_pData	= malloc(MAX_BUFFER_LENGTH);
	m_Buffer.m_Size		= MAX_BUFFER_LENGTH;
	m_Buffer.m_NbData	= 0;
	if(m_Latent.m_pData == NULL || m_Buffer.m_pData == NULL)
		return LZW_ERROR_MEM;

	/* initialisation réussie */
	return LZW_SUCCESS;
}

/******************************************************************************\
|* Free : libère la mémoire allouée pour la compresssion ou la décompresssion.*|
\******************************************************************************/
void Free()
{
	/* fermeture des fichiers */
	if(m_pReadFile != NULL)
		fclose(m_pReadFile);
	if(m_pWriteFile != NULL)
		fclose(m_pWriteFile);
	m_pReadFile		= NULL;
	m_pWriteFile	= NULL;

	/* destruction dictionnaire */
	DeleteDico();

	/* destruction buffers latent et actuel */
	free(m_Latent.m_pData);
	free(m_Buffer.m_pData);
	m_Latent.m_pData = NULL;
	m_Buffer.m_pData = NULL;

	/* destruction buffers lecture et écriture */
	free(m_ReadBuffer.m_pData);
	free(m_WriteBuffer.m_pData);
	m_ReadBuffer.m_pData	= NULL;
	m_WriteBuffer.m_pData	= NULL;
}

/******************************************************************************\
|* InitDico : initialise le dictionnaire.                                     *|
|* retour : vrai si l'initialisation a réussi, faux sinon.                    *|
\******************************************************************************/
int InitDico()
{
	/* variables locales */
	int i;

	/* création du dictionnaire */
	m_Dico = malloc(MAX_DICO_LENGTH * sizeof(TBuffer));
	if(m_Dico == NULL)
		return FALSE;
	memset(m_Dico, 0, MAX_DICO_LENGTH * sizeof(TBuffer));

	/* init des 256 premiers octets */
	for(i = 0; i < 256; i++)
	{
		m_Dico[i].m_pData		= malloc(1);
		m_Dico[i].m_pData[0]	= i;
		m_Dico[i].m_Size		= 1;
		m_Dico[i].m_NbData		= 1;
		if(m_Dico[i].m_pData == NULL)
			return FALSE;
	}

	/* indice en cours dans le dico, en mode UNCOMPRESS, on s'arrête là */
	m_DicoIndex = LZW_BEGIN_DIC;
	if(m_Mode == UNCOMPRESS)
		return TRUE;

	/* tableau des index, nombre d'éléments dans les sous-tableaux */
	m_TabIndex		= malloc(MAX_BUFFER_LENGTH * sizeof(WORD*));
	m_NbTabIndex	= malloc(MAX_BUFFER_LENGTH * sizeof(WORD));
	if(m_TabIndex == NULL || m_TabIndex == NULL)
		return FALSE;

	/* init du tableau à NULL */
	memset(m_TabIndex, 0, MAX_BUFFER_LENGTH * sizeof(WORD*));
	memset(m_NbTabIndex, 0, MAX_BUFFER_LENGTH * sizeof(WORD));
	return TRUE;
}

/******************************************************************************\
|* ResetDico : réinitialise le dictionnaire. Les buffers du dictionnaire ne   *|
|*             sont pas détruits dans cette fonction mais seulement           *|
|*             lorsqu'ils sont écrasés. Les différents tableaux sont          *|
|*             réinitialisés.                                                 *|
\******************************************************************************/
void ResetDico()
{
	/* variables locales */
	int i;

	/* le reset du dico en mode UNCOMPRESS revient à remettre l'indice courant
	   dans le dictionnaire à sa valeur min */
	m_DicoIndex = LZW_BEGIN_DIC;
	if(m_Mode == UNCOMPRESS)
		return;

	/* reset tableau des index */
	for(i = 0; i < MAX_BUFFER_LENGTH; i++)
	{
		free(m_TabIndex[i]);
		m_TabIndex[i]	= NULL;
		m_NbTabIndex[i]	= 0;
	}
}

/******************************************************************************\
|* DeleteDico : détruit le dictionnaire.                                      *|
\******************************************************************************/
void DeleteDico()
{
	/* variables locales */
	int i;

	/* suppression des buffers du dictionnaire */
	if(m_Dico != NULL)
	{
		for(i = 0; i < MAX_DICO_LENGTH; i++)
			free(m_Dico[i].m_pData);
	}

	/* supression du dictionnaire, en mode UNCOMPRESS, on s'arrête là */
	free(m_Dico);
	m_Dico = NULL;
	if(m_Mode == UNCOMPRESS)
		return;

	/* destruction sous-tableaux des index */
	if(m_TabIndex != NULL)
	{
		for(i = 0; i < MAX_BUFFER_LENGTH; i++)
			free(m_TabIndex[i]);
	}

	/* destruction tableaux des index */
	free(m_TabIndex);
	free(m_NbTabIndex);
	m_TabIndex		= NULL;
	m_NbTabIndex	= NULL;
}

/******************************************************************************\
|* FindInDico : recherche si un buffer est présent dans le dictionnaire.      *|
|* entrée : pBuffer : le buffer à rechercher.                                 *|
|* retour : l'indice du buffer dans le dictionnaire ou -1 si le buffer n'y    *|
|*          est pas.                                                          *|
\******************************************************************************/
int FindInDico(TBuffer* pBuffer)
{
	/* variables locales */
	WORD nbData, nbBuffer;
	int i, index;
	TBuffer* pDicoBuffer;

	/* nombre de données dans le buffer et nombre de buffers recensés pour
	   cette taille */
	nbData		= pBuffer->m_NbData;
	nbBuffer	= m_NbTabIndex[nbData];

	/* si aucun buffer de cette taille recensé */
	if(nbBuffer == 0)
		return -1;

	/* on parcourt les indices du tableau en fonction de la taille du buffer */
	for(i = 0; i < nbBuffer; i++)
	{	
		/* récupération buffer du dico à comparer */
		index = m_TabIndex[nbData][i];
		pDicoBuffer = &m_Dico[index];

		/* comparaison des buffers */
		if(memcmp(pBuffer->m_pData, pDicoBuffer->m_pData, nbData) == 0)
			return index;
	}

	/* buffer non présent dans le dico */
	return -1;
}

/******************************************************************************\
|* WriteInDico : écrit un buffer à la fin du dictionnaire.                    *|
|* entrée : pBuffer : le buffer à écrire.                                     *|
|* retour : vrai si l'ajout a réussi, faux sinon.                             *|
\******************************************************************************/
int WriteInDico(TBuffer* pBuffer)
{
	/* variables locales */
	WORD nbData;

	/* nombre de données dans le buffer */
	nbData = pBuffer->m_NbData;

	/* on détruit le buffer déjà présent dans le tableau */
	free(m_Dico[m_DicoIndex].m_pData);
	
	/* création nouveau buffer */
	m_Dico[m_DicoIndex].m_pData = malloc(nbData);
	if(m_Dico[m_DicoIndex].m_pData == NULL)
		return FALSE;
	m_Dico[m_DicoIndex].m_Size		= nbData;
	m_Dico[m_DicoIndex].m_NbData	= nbData;

	/* recopie */
	memcpy(m_Dico[m_DicoIndex].m_pData, pBuffer->m_pData, nbData);

	/* ajout de l'index dans le tableau des index en fonction de la taille du
	   buffer seulement en mode COMPRESS */
	if(m_Mode == COMPRESS)
	{
		/* si c'est le premier buffer de cette taille, créer un nouveau
		   sous-tableau */
		if(m_TabIndex[nbData] == NULL)
			m_TabIndex[nbData] = malloc(MAX_DICO_LENGTH * sizeof(WORD));
		if(m_TabIndex[nbData] == NULL)
			return FALSE;
			
		/* on mémorise l'index du dictionnaire */
		m_TabIndex[nbData][m_NbTabIndex[nbData]] = m_DicoIndex;
		m_NbTabIndex[nbData]++;
	}

	/* un élément de plus dans le dico */
	m_DicoIndex++;
	return TRUE;
}

/******************************************************************************\
|* WriteBits : écrit un nombre codé sur un certain nombre de bits.            *|
|* entrée : pData  : les données à écrire.                                    *|
|*          nbBits : le nombre de bits à prendre en compte.                   *|
|* retour : vrai si l'écriture a réussi, faux sinon.                          *|
|*----------------------------------------------------------------------------*|
|* Remarque : les bits inutiles doivent être nuls.                            *|
\******************************************************************************/
int WriteBits(DWORD* pData, BYTE nbBits)
{
	/* variables locales */
	BYTE byte;
	int dec;

	/* si la taille est supérieure à 32 bits, il y a un problème */
	if(nbBits > 32)
		return FALSE;

	/*------------------------------------------------------------------------*/
	/* on termine le buffer */

	/* décalage à effectuer */
	dec = nbBits - (8 - m_BitBufferSize);
	if(dec >= 0)
	{
		/* on rempli le buffer en entier, écriture dans le fichier */
		m_BitBuffer |= (BYTE)(*pData >> dec);
		if(!WriteFile(&m_BitBuffer))
			return FALSE;
	}
	else
	{
		/* on ne fait que rajouter des bits au buffer */
		m_BitBuffer		|= (BYTE)(*pData << (-dec));
		m_BitBufferSize	+= nbBits;
		return TRUE;
	}

	/* données restantes */
	nbBits -= 8 - m_BitBufferSize;

	/*------------------------------------------------------------------------*/
	/* tant que des octets entiers restent à écrire */
	while(nbBits >= 8)
	{
		/* calcul de l'octet à écrire */
		byte = (BYTE)((*pData >> (nbBits - 8)) & 0xFF);
		if(!WriteFile(&byte))
			return FALSE;

		/* 8 bits de moins à écrire; */
		nbBits -= 8;
	}

	/* le reste des données est mis dans le buffer */
	m_BitBuffer		= (BYTE)((*pData << (8 - nbBits)) & 0xFF);
	m_BitBufferSize	= nbBits;
	return TRUE;
}

/******************************************************************************\
|* FlushBits : écrit les bits restants dans le buffer.                        *|
|* retour : vrai si l'opération a réussi, faux sinon.                         *|
\******************************************************************************/
int FlushBits()
{
	/* variables locales */
	int result;

	/* si le buffer est vide, on renvoie vrai */
	if(m_BitBufferSize == 0)
		return TRUE;

	/* on écrit le buffer */
	result			= WriteFile(&m_BitBuffer);
	m_BitBuffer		= 0;
	m_BitBufferSize	= 0;
	return result;
}

/******************************************************************************\
|* ReadBits : lit un nombre codé sur un certain nombre de bits depuis un      *|
|*            fichier.                                                        *|
|* entrée : pData  : variable qui va recevoir le nombre lu.                   *|
|*          nbBits : nombre de bits à lire.                                   *|
|* retour : vrai si la lecture a réussi, faux sinon.                          *|
\******************************************************************************/
int ReadBits(DWORD* pData, BYTE nbBits)
{
	/* variables locales */
	BYTE byte;

	/* si la taille est supérieure à 32 bits, il y a un problème */
	if(nbBits > 32)
		return FALSE;

	/*------------------------------------------------------------------------*/
	/* init des données, récupération des données situés dans le buffer */

  • pData = 0;
if(nbBits >= 8) {
  • pData = m_BitBuffer >> (8 - m_BitBufferSize);
} else { /* on ne récupère qu'une partie */
  • pData = m_BitBuffer >> (8 - nbBits);
m_BitBuffer <<= nbBits; m_BitBufferSize -= nbBits; return TRUE; } /* données restantes à lire, réinit du buffer */ nbBits -= m_BitBufferSize; m_BitBuffer = 0; m_BitBufferSize = 0; /*------------------------------------------------------------------------*/ /* tant qu'il reste des octets entier à lire */ while(nbBits >= 8) { if(!ReadFile(&byte)) return FALSE; /* ajout dans les données, 8 bits de moins à lire */
  • pData = (*pData << 8) | byte;
nbBits -= 8; } /* s'il ne reste plus rien à lire */ if(nbBits == 0) return TRUE; /* lecture d'un octet supplémentaire */ if(!ReadFile(&byte)) return FALSE; /* on rajoute ce qu'il faut aux données, on met le reste dans le buffer */
  • pData = (*pData << nbBits) | (byte >> (8 - nbBits));
m_BitBuffer = byte << nbBits; m_BitBufferSize = 8 - nbBits; return TRUE; } /******************************************************************************\ |* WriteFile: écrit un octet dans le buffer d'écriture du fichier. *| |* entrée : pData : donnée à écrire ou NULL si on purge le buffer. *| |* retour : vrai si l'écriture a réussi, faux sinon. *| \******************************************************************************/ int WriteFile(BYTE* pData) { /* variables locales */ DWORD NbBytesWritten; /* si le buffer d'écriture est plein ou si on le purge */ if(m_WriteBuffer.m_NbData == m_WriteBuffer.m_Size || pData == NULL) { NbBytesWritten = fwrite(m_WriteBuffer.m_pData, 1, m_WriteBuffer.m_NbData, m_pWriteFile); if(NbBytesWritten != m_WriteBuffer.m_NbData) return FALSE; m_WriteBuffer.m_NbData = 0; } /* s'il s'agisait d'une purge, détruire les buffers */ if(pData == NULL) { free(m_WriteBuffer.m_pData); m_WriteBuffer.m_pData = NULL; m_WriteBuffer.m_Size = 0; m_WriteBuffer.m_NbData = 0; return TRUE; } /* ajout de la donnée dans le buffer d'écriture */ m_WriteBuffer.m_pData[m_WriteBuffer.m_NbData] = *pData; m_WriteBuffer.m_NbData++; return TRUE; } /******************************************************************************\ |* ReadFile: lit un octet depuis le buffer de lecture du fichier. *| |* entrée : pData : donnée à écrire ou NULL si on purge le buffer. *| |* retour : vrai si la lecture a réussi, faux sinon. *| \******************************************************************************/ int ReadFile(BYTE* pData) { /* variables locales */ DWORD NbBytesRead; /* s'il s'agit d'une purge, détruire les buffers */ if(pData == NULL) { free(m_ReadBuffer.m_pData); m_ReadBuffer.m_pData = NULL; m_ReadBuffer.m_Size = 0; m_ReadBuffer.m_NbData = 0; m_ReadBufferIndex = 0; return TRUE; } /* si le buffer de lecture est terminé */ if(m_ReadBufferIndex == m_ReadBuffer.m_NbData) { NbBytesRead = fread(m_ReadBuffer.m_pData, 1, m_ReadBuffer.m_Size, m_pReadFile); if(NbBytesRead == 0) return FALSE; m_ReadBuffer.m_NbData = (WORD) NbBytesRead; m_ReadBufferIndex = 0; } /* récupération de la donnée */
  • pData = m_ReadBuffer.m_pData[m_ReadBufferIndex];
m_ReadBufferIndex++; m_JobCurrent++; return TRUE; }

Conclusion :


La compression n'est pas très rapide (l'algo est optimisable en utilisant un arbre pour stocker le dictionnaire).
Le taux de compression peut être améliorer en réinitialisant le dictionnaire quand la compression devient mois bonne.

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

heo3637
Messages postés
1
Date d'inscription
mardi 26 décembre 2000
Statut
Membre
Dernière intervention
23 avril 2012

Excellent travail, merci beaucoup!!!
cs_zalson
Messages postés
4
Date d'inscription
mercredi 28 février 2007
Statut
Membre
Dernière intervention
12 mai 2007

Salut je suis très interessé par votre code.Pouvez vous me donner un bref commentaire un son fonctionnement et comment est cree le dictionnare?
Quels types de fichier il compresse? puiseque je dois presenter un project pour la compression et decompression d'un fichier de texte.
yolas22
Messages postés
1
Date d'inscription
samedi 16 avril 2005
Statut
Membre
Dernière intervention
19 juillet 2006

Et bien je cherchais des explications sur le lzw compression et decompression, la lecture de ce code et des commentaires m'en a appris plus que certaines documentations.
Chapeau, super propre ton code ( 2 ans aprés je relance les compliments).
+ yolas22.
ymca2003
Messages postés
2070
Date d'inscription
mardi 22 avril 2003
Statut
Membre
Dernière intervention
3 juillet 2006
8
J'ai pas utilisé la stl pour les raisons suivantes :
- ce code est en C.
- j'utilise jamais la stl en C++.

Par contre ma façon de stocker le dico est trop compliqué. Il y a en fait beaucoup plus simple.
Il suffit d'avoir un buffer contenant les x derniers octets et de sauvegardé une liste d'indice pour remonter les mots (utilisés par gzip).
hebus16
Messages postés
80
Date d'inscription
vendredi 14 mai 2004
Statut
Membre
Dernière intervention
2 octobre 2009

apres une petite lecture du code, j'aurai quand même une question ... le dictionnaire que tu utilises est constitué a partir du bon vieux malloc.... j'aimerai savoir pourquoi ne pas avoir utiliser l'objet map de la librairie stl ... ca aurait eviter pas mal de ligne pour la gestion du dictionnaire et serait bcp plus simple à gerer au niveau des ressources ... est ce un choix delibéré? si oui peux tu m'expliquer stp je patauge encore dans cette partie là .... si non voici une doc basique sur son fonctionnement:
http://support.microsoft.com/default.aspx?scid=kb;fr;157159#appliesto


Merci d'avance

hebus16

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.