Rev. | 1125 |
---|---|
Size | 11,918 bytes |
Time | 2014-05-07 06:15:53 |
Author | Jylam |
Log Message | Makefile for most of the dev tools ; POSIX fixes
|
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#define max(a,b) ((a)>(b)?(a):(b))
// ne doit jamais depasser 16 les deux !!!
//4
#define _LZ77_NB_BIT_SIZE 4
#define _LZ77_NB_BIT_OFFSET 12
#define _LZ77_MAX_SIZE (1<<_LZ77_NB_BIT_SIZE) // 1<<4 -> 16
#define _LZ77_MAX_OFFSET ((1<<_LZ77_NB_BIT_OFFSET)+1) // 1<<12 -> 4096+1 = 4097
#define _LZ77_ROOT (_LZ77_MAX_OFFSET)
#define _LZ77_SEARCH_SIZE (_LZ77_MAX_SIZE+1)
typedef struct
{
short smaller_child;
short larger_child;
short parent;
short branch; // par quel branche du parent est il venue
}LZ77_TREE;
LZ77_TREE BigTree[_LZ77_MAX_OFFSET+2];
unsigned char gLZ77_XorMask=0;
long LZ77_Compress(void* buf_src_void,void *buf_dest_void,long size_buf_src)
{
unsigned char *buf_src =(unsigned char*)buf_src_void;
unsigned char *buf_dest=(unsigned char*)buf_dest_void;
LZ77_TREE *tree,*real_tree,*current_tree,*del_tree;
unsigned char *ptr_decoding_mask;
unsigned char *ptr_search_src;
unsigned char andvalue;
long nb_rec;
long size;
long delta_value;
long offset_src;
short i,k;
short best_match;
short best_node;
short current_node;
short num_tree;
short search_index;
short branch_value;
real_tree=BigTree;
// ruse pour eviter les test kan les child sont
-1
// mon tableau commence
+1 donc ce ki sera patch en 0
// rien
faire !!
tree=real_tree+1;
// init tree
memset(tree,-1,(_LZ77_MAX_OFFSET+1)*sizeof(LZ77_TREE));
offset_src=0;
nb_rec=1;
size=0;
andvalue=0;
while (offset_src+nb_rec-1<size_buf_src)
{
//
// Reload encoding type mask
//
if (!andvalue)
{
andvalue=1;
ptr_decoding_mask=buf_dest++;
*ptr_decoding_mask=0; // No match
size++;
}
// delete string de 'num_index'
// en recherchant ds tree celui ki a 'num_index+last advance'
while (nb_rec>0)
{
i=(short)(offset_src % _LZ77_MAX_OFFSET);
num_tree=i;
current_tree=&tree[i];
if (current_tree->parent>=0)
{
// supprime ca
if ( (current_tree->smaller_child<0) || (current_tree->larger_child<0) )
{ // facile a faire
branch_value=current_tree->larger_child;
if (branch_value>=0)
{
tree[branch_value].parent=current_tree->parent;
tree[branch_value].branch=current_tree->branch;
}
else
{
branch_value=current_tree->smaller_child;
if (branch_value>=0)
{
tree[branch_value].parent=current_tree->parent;
tree[branch_value].branch=current_tree->branch;
}
else // no child
{
branch_value=-1;
}
}
}
else
{
// supprime noeud ki a 2 fils
// d'ou ruse :
// au choix rechercher le plus grand du fils 'larger'
// ou recherche le plus grand du fils 'smaller'
// de toute facon ca revient au meme.... ( ce qui est logique d'ailleur)
branch_value=current_tree->smaller_child;
del_tree=&tree[branch_value];
if (del_tree->larger_child<0)
current_tree->smaller_child=del_tree->smaller_child;
else
{
while (del_tree->larger_child>=0)
{
branch_value=del_tree->larger_child;
del_tree=&tree[branch_value];
}
// supprime del
tree[del_tree->parent].larger_child=del_tree->smaller_child;
}
tree[del_tree->smaller_child].parent=del_tree->parent;
tree[del_tree->smaller_child].branch=del_tree->branch;
//remplacement
del_tree->smaller_child=current_tree->smaller_child;
del_tree->larger_child =current_tree->larger_child;
tree[del_tree->smaller_child].parent=branch_value;
tree[del_tree->larger_child].parent =branch_value;
del_tree->parent=current_tree->parent;
del_tree->branch=current_tree->branch;
}
// update chez parent de i
if (!current_tree->branch) tree[current_tree->parent].smaller_child=branch_value;
else tree[current_tree->parent].larger_child =branch_value;
}
current_tree->larger_child =-1;
current_tree->smaller_child=-1;
// donc on va ecrire ds tree[numtree]
current_node=tree[_LZ77_ROOT].smaller_child; // init with root
if (current_node<0) // remplis racine de l'arbre...
{
tree[num_tree].parent=_LZ77_ROOT;
tree[num_tree].branch=0; // weil immer smaller branch for root
tree[_LZ77_ROOT].smaller_child=num_tree;
best_match=0;
}
else
{
best_match=2;
best_node=0;
while (1)
{
i=num_tree-current_node; // offset
if (i<0) i+=(_LZ77_MAX_OFFSET);
//k= _SearchSequence(src-i,src,_LZ77_MAX_SIZE+2);
ptr_search_src=buf_src-i;
search_index=0;
while (ptr_search_src[search_index] == buf_src[search_index])
{
if (search_index==_LZ77_SEARCH_SIZE) break;
search_index++;
}
delta_value=ptr_search_src[search_index] - buf_src[search_index];
//k=_LZ77_SEARCH_SIZE-search_index; // 17-
if ( (search_index==_LZ77_SEARCH_SIZE) && (!delta_value) )
{
//
// 1) On a trouvé une chaine de la taille maximale
// possible pour l'encoding...
// On stocke cette entrée, et on se casse.
// On ne trouvera jamais mieux !
//
tree[num_tree]=tree[current_node];
// on s'occupe du parent
if (!tree[num_tree].branch) tree[tree[num_tree].parent].smaller_child=num_tree;
else tree[tree[num_tree].parent].larger_child =num_tree;
// et des fils
tree[tree[num_tree].smaller_child].parent=num_tree;
tree[tree[num_tree].larger_child].parent =num_tree;
// on efface l'ancien noeud proprement...
tree[current_node].parent=-1;
best_match=_LZ77_MAX_SIZE+2; // 18 octets à copier=maximum possible avec l'encodage 4:12
best_node =current_node;
break;
}
else
{
//
// 2) On a pas trouvé une chaine de taille maximale
//
k=_LZ77_SEARCH_SIZE-(_LZ77_SEARCH_SIZE-search_index);
if (k>best_match)
{
best_match=k;
best_node=current_node;
}
if (delta_value>=0)
{ // suivre larger
k=tree[current_node].larger_child;
if (k<0)
{
tree[num_tree].parent =current_node;
tree[current_node].larger_child =num_tree;
tree[num_tree].branch =-1; // comming from larger
break;
}
else current_node=k;
}
else // suivre smaller
{
k=tree[current_node].smaller_child;
if (k<0)
{
tree[num_tree].parent =current_node;
tree[current_node].smaller_child=num_tree;
tree[num_tree].branch =0; // comming from smaller
break;
}
else current_node=k;
}
}
}
}
nb_rec--;
if (nb_rec>0)
{
buf_src++;
offset_src++;
}
}
// bindage de taille
if (size>=size_buf_src-2)
{
return -1;
}
nb_rec=best_match;
//value>>=1;
if ( (nb_rec>2) && (offset_src+nb_rec<=size_buf_src) ) // 2 match 0 bits win ....
{
unsigned int value_short;
//
// Copy with offset
//
i=(offset_src % (_LZ77_MAX_OFFSET))-best_node;
if (i<0) i+=(_LZ77_MAX_OFFSET);
value_short=((nb_rec-3)<<(16-_LZ77_NB_BIT_SIZE)) | (i-1);
*buf_dest++=(unsigned char)(value_short & 255);
*buf_dest++=(unsigned char)(value_short>>8);
size+=2;
if (gLZ77_XorMask) *ptr_decoding_mask|=andvalue;
}
else
{
//
// Just put the byte, without compression
// and put '1' in the encoding mask
//
if (!gLZ77_XorMask) *ptr_decoding_mask|=andvalue;
*buf_dest++=*buf_src;
size++;
nb_rec=1;
}
offset_src++;
buf_src++;
andvalue<<=1;
}
return size;
//return ((size+3)&(~3));
}
void LZ77_UnCompress(void* buf_src_void,void* buf_dest_void, long size)
{
unsigned char *buf_src =(unsigned char*)buf_src_void;
unsigned char *buf_dest=(unsigned char*)buf_dest_void;
unsigned char value;
unsigned char andvalue;
long offset,nb;
andvalue=0;
while (size>0)
{
//
// Reload encoding type mask
//
if (!andvalue)
{
andvalue=1;
value=(*buf_src++);
}
if ((value^gLZ77_XorMask) & andvalue)
{
//
// Copy 1 unsigned char
//
*buf_dest++=*buf_src++;
size--;
}
else
{
//
// Copy with offset
//
// At this point, the source pointer points to a two byte
// value that actually contains a 4 bits counter, and a
// 12 bit offset to point back into the depacked stream.
// The counter is in the 4 high order bits.
//
offset = buf_src[0]; // Read 16 bits non alligned datas...
offset|=(buf_src[1]&0x0F)<<8;
offset+=1;
nb =(buf_src[1]>>4)+3;
buf_src+=2;
size-=nb;
while (nb>0)
{
*buf_dest++=*(buf_dest-offset);
nb--;
}
}
andvalue<<=1;
}
}
long LZ77_ComputeDelta(unsigned char *buf_comp,long size_uncomp,long size_comp)
{
unsigned char *buf_src =(unsigned char*)buf_comp;
unsigned char *buf_dest=(unsigned char*)buf_comp+size_comp-size_uncomp;
unsigned char value;
unsigned char andvalue;
long offset,nb;
long max_delta_space;
max_delta_space=0;
andvalue=0;
while (size_uncomp>0)
{
//
// Reload encoding type mask
//
if (!andvalue)
{
andvalue=1;
value=(*buf_src++);
}
if ((value^gLZ77_XorMask) & andvalue)
{
//
// Copy 1 unsigned char
//
//*buf_dest++=*buf_src++;
if (buf_dest>=buf_src)
{
max_delta_space=max(max_delta_space,buf_dest-buf_src);
}
buf_dest++;
buf_src++;
size_uncomp--;
}
else
{
//
// Copy with offset
//
// At this point, the source pointer points to a two byte
// value that actually contains a 4 bits counter, and a
// 12 bit offset to point back into the depacked stream.
// The counter is in the 4 high order bits.
//
offset = buf_src[0]; // Read 16 bits non alligned datas...
offset|=(buf_src[1]&0x0F)<<8;
offset+=1;
nb =(buf_src[1]>>4)+3;
buf_src+=2;
size_uncomp-=nb;
while (nb>0)
{
//*buf_dest++=*(buf_dest-offset);
if (buf_dest>=buf_src)
{
max_delta_space=max(max_delta_space,buf_dest-buf_src);
}
buf_dest++;
nb--;
}
}
andvalue<<=1;
}
return max_delta_space;
}
long LZ77_ComputeDeltaOld(unsigned char *buf_comp,long size_uncomp,long size_comp)
{
unsigned char value;
unsigned char andvalue;
long offset,nb;
long offset_comp;
long offset_uncomp;
long max_delta_space;
offset_comp=size_uncomp-size_comp;
offset_uncomp=0;
max_delta_space=0;
andvalue=0;
while (size_uncomp>0)
{
//
// Reload encoding type mask
//
if (!andvalue)
{
andvalue=1;
value=*buf_comp++;
offset_comp++;
}
if (value & andvalue)
{
//
// Copy 1 unsigned char
//
buf_comp++;
offset_uncomp++;
if (offset_comp<=offset_uncomp)
{
max_delta_space=max(offset_uncomp-offset_comp+1,max_delta_space);
}
offset_comp++;
size_uncomp--;
}
else
{
//
// Copy with offset
//
offset =*buf_comp++; // Read 16 bits non alligned datas...
offset|=(*buf_comp++)<<8;
nb=(offset & (0xff >> (8-_LZ77_NB_BIT_SIZE)) )+2+1;
offset=((offset>>_LZ77_NB_BIT_SIZE) & (0xffff >> (16-_LZ77_NB_BIT_OFFSET))) +1;
size_uncomp-=nb;
offset_uncomp+=nb;
if (offset_comp<=offset_uncomp)
{
max_delta_space=max(offset_uncomp-offset_comp+1,max_delta_space);
}
offset_comp+=2;
}
andvalue<<=1;
}
return((max_delta_space+3)&(~3)); // padd to four.
}