Compression LZSS

[tangui]

Bon, c tres simple, j'ai besoin pour le boulot de modifer la compression LZSS... Au lieu d'avoir en parametres d'entrées et de sorties des fichier, je veux y mettre des tableaux...

Voici déjà le source original de la compression LZSS:

 

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

LZSS.C -- A Data Compression Program

(tab = 4 spaces)

*******************************************************************************

4/6/1989 Haruhiko Okumura

Use, distribute, and modify this program freely.

Please send me your improved versions.

 PC-VAN  SCIENCE

 NIFTY-Serve	PAF01022

 CompuServe	74050,1022

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





#define N  4096	/* size of ring buffer                        */

#define F  18	/* upper limit for match_length               */

#define THRESHOLD	2       /* encode string into position and length     */

   /* if match_length is greater than this       */



#define NIL  N	/* index for root of binary search trees      */



unsigned long int	textsize,	/* text size counter         */

 	codesize,	/* code size counter         */

 	printcount = 0;	/* counter for reporting progress     */

   	/* every 1K bytes                     */



unsigned char   text_buf[N + F - 1];	/* ring buffer of size N,       */

                  /* with extra F-1 bytes to facilitate */

   	/* string comparison                  */



int  match_position, match_length;  /* of longest match.  These are

           /* set by the InsertNode()     */

           /* procedure.                  */



int  lson[N + 1], 

 rson[N + 257], 

 dad[N + 1];    /* left & right children & parents             */

         /* These constitute binary search trees.       */



FILE  *infile, *outfile;   /* input & output files              */







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

/*    Code                                                                    */

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



void InitTree()  /* initialize trees */

{

int  i;



/* For i = 0 to N - 1, rson[i] and lson[i] will be the right and

   left children of node i.  These nodes need not be initialized.

   Also, dad[i] is the parent of node i.  These are initialized to

   NIL (= N), which stands for 'not used.'

   For i = 0 to 255, rson[N + i + 1] is the root of the tree

   for strings that begin with character i.  These are initialized

   to NIL.  Note there are 256 trees. */



for (i = N + 1; i <= N + 256; i++) rson[i] = NIL;

for (i = 0; i < N; i++) dad[i] = NIL;

}





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

/*    Code                                                                    */

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



void InsertNode(r)

  int r;

/* Inserts string of length F, text_buf[r..r+F-1], into one of the

   trees (text_buf[r]'th tree) and returns the longest-match position

   and length via the global variables match_position and match_length.

   If match_length = F, then removes the old node in favor of the new

   one, because the old one will be deleted sooner.

   Note r plays double role, as tree node and position in buffer. */

{

int  i, p, cmp;

unsigned char  *key;



cmp = 1;  key = &text_buf[r];  p = N + 1 + key[0];

rson[r] = lson[r] = NIL;  match_length = 0;

for (;; ) {

 if (cmp >= 0) {

 	if (rson[p] != NIL) p = rson[p];

 	else {  rson[p] = r;  dad[r] = p;  return;  }

 } else {

 	if (lson[p] != NIL) p = lson[p];

 	else {  lson[p] = r;  dad[r] = p;  return;  }

 }

 for (i = 1; i < F; i++)

 	if ((cmp = key[i] - text_buf[p + i]) != 0)  break;

 if (i > match_length) {

 	match_position = p;

 	if ((match_length = i) >= F)  break;

 }

}

dad[r] = dad[p];  lson[r] = lson[p];  rson[r] = rson[p];

dad[lson[p]] = r;  dad[rson[p]] = r;

if (rson[dad[p]] == p) rson[dad[p]] = r;

else                   lson[dad[p]] = r;

dad[p] = NIL;  /* remove p */

}





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

/*    Code                                                                    */

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



void DeleteNode(p)  /* deletes node p from tree */

  int p;

{

int  q;



if (dad[p] == NIL) return;  /* not in tree */

if (rson[p] == NIL) q = lson[p];

else if (lson[p] == NIL) q = rson[p];

else {

 q = lson[p];

 if (rson[q] != NIL) {

 	do {  q = rson[q];  } while (rson[q] != NIL);

 	rson[dad[q]] = lson[q];  dad[lson[q]] = dad[q];

 	lson[q] = lson[p];  dad[lson[p]] = q;

 }

 rson[q] = rson[p];  dad[rson[p]] = q;

}

dad[q] = dad[p];

if (rson[dad[p]] == p) rson[dad[p]] = q;  else lson[dad[p]] = q;

dad[p] = NIL;

}







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

/*    Code - fonction de compression (appel InitTree, InsertNode, DeleteNode) */

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



void Encode(infile, outfile, sizefile)

FILE	*infile, *outfile;  /* input & output files */

long int *sizefile;

{

int  i, c, len, r, s, last_match_length, code_buf_ptr;

unsigned char  code_buf[17], mask;





textsize = 0; /* text size counter */

codesize = 0; /* code size counter */



InitTree();  /* initialize trees */

code_buf[0] = 0;  /* code_buf[1..16] saves eight units of code, and

 code_buf[0] works as eight flags, "1" representing that the unit

 is an unencoded letter (1 byte), "0" a position-and-length pair

 (2 bytes).  Thus, eight units require at most 16 bytes of code. */

code_buf_ptr = mask = 1;

s = 0;  r = N - F;

for (i = s; i < r; i++) text_buf[i] = ' ';  /* Clear the buffer with

 any character that will appear often. */

for (len = 0; len < F && (c = getc(infile)) != EOF; len++)

 text_buf[r + len] = c;  /* Read F bytes into the last F bytes of

 	the buffer */

if ((textsize = len) == 0) return;  /* text of size zero */

for (i = 1; i <= F; i++) InsertNode(r - i);  /* Insert the F strings,

 each of which begins with one or more 'space' characters.  Note

 the order in which these strings are inserted.  This way,

 degenerate trees will be less likely to occur. */

InsertNode(r);  /* Finally, insert the whole string just read.  The

 global variables match_length and match_position are set. */

do {

 if (match_length > len) match_length = len;  /* match_length

 	may be spuriously long near the end of text. */

 if (match_length <= THRESHOLD) {

 	match_length = 1;  /* Not long enough match.  Send one byte. */

 	code_buf[0] |= mask;  /* 'send one byte' flag */

 	code_buf[code_buf_ptr++] = text_buf[r];  /* Send uncoded. */

 } else {

 	code_buf[code_buf_ptr++] = (unsigned char) match_position;

 	code_buf[code_buf_ptr++] = (unsigned char)

   (((match_position >> 4) & 0xf0)

    | (match_length - (THRESHOLD + 1)));  /* Send position and

   	length pair. Note match_length > THRESHOLD. */

 }

 if ((mask <<= 1) == 0) {  /* Shift mask left one bit. */

 	for (i = 0; i < code_buf_ptr; i++)  /* Send at most 8 units of */

   putc(code_buf[i], outfile);     /* code together */

 	codesize += code_buf_ptr;

 	code_buf[0] = 0;  code_buf_ptr = mask = 1;

 }

 last_match_length = match_length;

 for (i = 0; i < last_match_length &&

   (c = getc(infile)) != EOF; i++) {

 	DeleteNode(s);  /* Delete old strings and */

 	text_buf[s] = c;	/* read new bytes */

 	if (s < F - 1) text_buf[s + N] = c;  /* If the position is

   near the end of buffer, extend the buffer to make

   string comparison easier. */

 	s = (s + 1) & (N - 1);  r = (r + 1) & (N - 1);

   /* Since this is a ring buffer, increment the position

      modulo N. */

 	InsertNode(r);	/* Register the string in text_buf[r..r+F-1] */

 }

 if ((textsize += i) > printcount) {

 	printf("%12ldr", textsize);  printcount += 1024;

   /* Reports progress each time the textsize exceeds

      multiples of 1024. */

 }

 while (i++ < last_match_length) {	/* After the end of text, */

 	DeleteNode(s);    	/* no need to read, but */

 	s = (s + 1) & (N - 1);  r = (r + 1) & (N - 1);

 	if (--len) InsertNode(r);  /* buffer may not be empty. */

 }

} while (len > 0);	/* until length of string to be processed is zero */

if (code_buf_ptr > 1) {  /* Send remaining code. */

 for (i = 0; i < code_buf_ptr; i++) putc(code_buf[i], outfile);

 codesize += code_buf_ptr;

}

printf("In : %ld bytesn", textsize);	/* Encoding is done. */

printf("Out: %ld bytesn", codesize);

printf("Out/In: %.3fn", (double)codesize / textsize);



  *sizefile = codesize;

}





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

 

Voili ce que j'ai modifié:

 

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

/*    Code - fonction de compression (appel InitTree, InsertNode, DeleteNode) */

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



NS_BITS_32 cpn_comp(NS_BITS_8* pl_in, NS_BITS_32 lng, NS_BITS_8* pl_out)

{



  NS_BITS_8  i, c, len, r, s, last_match_length, code_buf_ptr; 

  BITS_16  code_buf[17], mask; 

  NS_BITS_32 j; 

  j=0;

  textsize = 0; /* text size counter */

  codesize = 0; /* code size counter */



  InitTree();       /* initialize trees */

  code_buf[0] = 0;  /* code_buf[1..16] saves eight units of code, and

     code_buf[0] works as eight flags, "1" representing that the unit

     is an unencoded letter (1 byte), "0" a position-and-length pair

     (2 bytes).  Thus, eight units require at most 16 bytes of code. */



  code_buf_ptr = mask = 1;

  s = 0;

  r = N - F;



for (i = s; i < r; i++) 

     text_buf[i] = ' ';/*Clear the buffer with  any character that will appear 

                                                                      often. */





  for (len = 0; (len < F) && (j<=lng); len++)/*(c = *pl_in) != ''*/ 

  {

     c = *pl_in++;

     text_buf[r + len] = c; /*Read F bytes into thelast F bytes of the buffer*/

     j++;

  }

if ((textsize = len) == 0) /* text of size zero */

     return;  



for (i = 1; i <= F; i++) 

    InsertNode(r - i);  /* Insert the F strings, each of which begins with 

                           one or more 'space' characters.  Note the order 

                           in which these strings are inserted.  This way,

                           degenerate trees will be less likely to occur. */



InsertNode(r);  /* Finally, insert the whole string just read.  The

                global variables match_length and match_position are set. */



do {

     if (match_length > len) /*match_length may be > long near 

                                                          the end of text.*/

          match_length = len;  

                             



     if (match_length <= THRESHOLD) {

        match_length = 1;  /* Not long enough match.  Send one byte. */

        code_buf[0] |= mask;  /* 'send one byte' flag */

        code_buf[code_buf_ptr++] = text_buf[r];  /* Send uncoded. */

     } 

     else

     {

        code_buf[code_buf_ptr++] = (NS_BITS_8) match_position;

        code_buf[code_buf_ptr++] = (NS_BITS_8)

        (((match_position >> 4) & 0xf0)

        | (match_length - (THRESHOLD + 1)));  /* Send position and

                          length pair. Note match_length > THRESHOLD. */

     }



     if ((mask <<= 1) == 0) {             /* Shift mask left one bit.*/

        for (i = 0; i < code_buf_ptr; i++)/*Send at most 8 units of  */

              *pl_out++ = code_buf[i];    /*code together */



         codesize += code_buf_ptr;

         code_buf[0] = 0;  code_buf_ptr = mask = 1;

     }

     last_match_length = match_length;



     for (i = 0; (i < last_match_length )&& (j<=lng); i++) 

     {

        c = *pl_in++;

        DeleteNode(s);  /* Delete old strings and */

        text_buf[s] = c;	/* read new bytes */

        if (s < F - 1) 

           text_buf[s + N] = c;/*If the position is near the end of buffer,

                          extend the buffer to make string comparison easier.*/

         s = (s + 1) & (N - 1);  

         r = (r + 1) & (N - 1);

         /* Since this is a ring buffer, increment the position modulo N. */

          j++;

         InsertNode(r);	/* Register the string in text_buf[r..r+F-1] */

         



     }

     if ((textsize += i) > printcount) {

                        /* printf("%12ldr", textsize); */

                               printcount += 1024;

     /* Reports progress each time the textsize exceeds multiples of 1024. */

     }



     while (i++ < last_match_length) {	/* After the end of text,   */

        DeleteNode(s);                 /* no need to read, but     */

        s = (s + 1) & (N - 1);         /* buffer may not be empty. */

        r = (r + 1) & (N - 1);

           if (--len) 

              InsertNode(r);	

     }

} while (len > 0);	/* until length of string to be processed is zero */



  if (code_buf_ptr > 1) {  /* Send remaining code. */

     

     for (i = 0; i < code_buf_ptr; i++) /*putc(code_buf[i], outfile);*/

         *pl_out++ = code_buf[i]; /*EV#0168*/

    

     codesize += code_buf_ptr;

  }



/*  printf("In : %ld bytesn", textsize);  Encoding is done. 

  printf("Out: %ld bytesn", codesize);

  printf("Out/In: %.3fn", (double)codesize / textsize);*/



  return(codesize);

}

Pour les NS_BITS_32 ... ca correspond au fichier du dessus (char, int...)

 

Le hic c que je ne sors pas de la boucle finissant par while (len > 0); puisque je ne rentre pas dans:

while (i++ < last_match_length) { /* After the end of text, */

DeleteNode(s); /* no need to read, but */

s = (s + 1) & (N - 1); /* buffer may not be empty. */

r = (r + 1) & (N - 1);

if (--len)

InsertNode®;

}en effet mon i est tjrs superieur a last_match_length, car celui ci est remis a 0 souvent...

 

bon je pense que mon pblme est que je n'arrive pas a faire une equivalence a ca: (c = getc(infile)) != EOF;

klk1 a une idée?? car ce que j'ai fait je ne sais pas si ca marche...

voili, c urgent et je ne sais plus koi faire

[automne]

Pour remplacer (c = getc(infile)) != EOF; dans la condition de sortie de ta boucle for , il faut 2 choses :

- que tu vérifies que tu ne sois pas à la fin de ton tableau sinon tu quittes la boucle. Mais pour ca il faut que tu connaisses sa taille.

- que tu affectes à 'c' le prochain element de ton tableau au debut de la boucle

 

Ca donne kkchose comme ca :

for (........ ; ...... && (++indice_courant_tableau < taille_tableau); ..... )

{

     c = tableau[indice_courant_tableau];

      .......

}

 

Je ne suis pas rentré dans les details de ton code parce que j'ai pas trop de temps et les types NS_BITS_32 et NS_BITS_8 je ne connais pas (surement un truc propriétaire d'ou tu bosses non ?) et donc je ne peux pas en dire plus.

 

Automne

[tangui]

ypedef char BITS_8; /* Donnees signees sur 8 bits */

typedef unsigned char NS_BITS_8; /* Donnees non signees sur 8 bits */

typedef short BITS_16; /* Donnees signees sur 16 bits */

typedef unsigned short NS_BITS_16; /* Donnees non signees sur 16 bits */

typedef long BITS_32; /* Donnees signees sur 32 bits */

typedef unsigned long NS_BITS_32; /* Donnees non signees sur 32 bits */

typedef float REEL; /* Donnees reelles sur 32 bits */

 

ca sera peut etre plus clair..

je vais tester ton truc...

[tangui]

tjrs ^pareil

[tangui]

Up!! g vraiment besoin d'aide....

[automne]

Ok, merci pour les typedefs !! En effet ca aide un peu.

 

Comme je t'ai dit, j'ai pas trop le temps mais je peux te taire quelques remarques et suggestions qui pourront peut-être t'aiguiller dans la bonne direction.

 

Déjà avoir transformé les variables 'int' en NS_BITS_8 c'est pas une bonne idée. Un 'int' si tu es sur un PC actuel, c'est sur 32 bits et il y a des chances que ce ne soit pas signé. Donc essaye le type BITS_32. En plus ca peut expliquer que des variables retombent à 0 à cause de l'overflow.

 

Pareil, les 'unsigned char' c'est du NS_BITS_8 et non du BITS_16.

 

La déclaration des variables au début de ta fonction seraient plutot comme ca :

BITS_32  i, c, len, r, s, last_match_length, code_buf_ptr;

NS_BITS_8  code_buf[17], mask;

NS_BITS_32 j; 

 

Automne

[Chaya]

Hummm....

 

Vraiment intéressant tout ca....je vais plancher dessus

 

Je t'envois un PM des que j'ai la soluce !

[tangui]

heu..c pour un OS embarqué avec comme processeur un 68000

t'inkietes pas ca fait 20 ans que ca tourne comme ca

sinon, g un peu avancé, g le début qui est compacté et apres on dirait que ca part en vrille... ms g modifié encore le code...

si t'as d'autres suggestions...

[tangui]

Hummm....

 

Vraiment intéressant tout ca....je vais plancher dessus    

 

Je t'envois un PM des que j'ai la soluce !

toi avec du code...?

pardon... Exch@nge bien...

STARTER!!

[tangui]

Au fait, g réussi a tout faire marcher , la solution bientot