- 论坛徽章:
- 0
|
19可用积分
大家好，帮忙看下这段代码主要实现的什么功能，稍微介绍一下这个程序好么，谢谢。小弟混chinaunix不久 只有19积分 全部奉上 再次感谢下大家
typedef struct
{
unsigned long Signature;
/* put any other info here like file name and date */
} FileHeader;
typedef byte BufferArray[BufSize + 1];
typedef word CodeType; /* 0..MaxChar */
typedef byte UpIndex; /* 0..PredMax */
typedef word DownIndex; /* 0..TwiceMax */
typedef DownIndex TreeDownArray[PredMax + 1]; /* UpIndex */
typedef UpIndex TreeUpArray[TwiceMax + 1]; /* DownIndex */
BufferArray InBuffer; /* input file buffer */
BufferArray OutBuffer; /* output file buffer */
char InName[80]; /* input file name */
char OutName[80]; /* output file name */
char CompStr[4]; /* response from Expand? prompt */
FILE *InF; /* input file */
FILE *OutF; /* output file */
TreeDownArray Left, Right; /* child branches of code tree */
TreeUpArray Up; /* Parent branches of code tree */
bool CompressFlag; /* true to compress file */
byte BitPos; /* current bit in byte */
CodeType InByte; /* current input byte */
CodeType OutByte; /* current output byte */
word InSize; /* current chars in input buffer */
word OutSize; /* Current chars in output buffer */
word Index; /* general purpose index */
char *Usage = {"Usage: splay [x] infile outfile\n\n"
"Where 'x' denotes expand infile to outfile\n"
"Normally compress infile to outfile\n"
};
/* function prototypes */
void InitializeSplay(void);
void Splay(CodeType Plain);
void FlushOutBuffer(void);
void WriteByte(void);
void Compress(CodeType Plain);
void ReadHeader(void);
byte GetByte(void);
CodeType Expand(void);
void ExpandFile(void);
/* initialize the splay tree - as a balanced tree */
void InitializeSplay(void)
{
DownIndex I;
int /*UpIndex*/ J;
DownIndex K;
for (I = 1; I <= TwiceMax; I++)
Up[I] = (I - 1) >> 1;
for (J = 0; J <= PredMax; J++)
{
K = ((byte)J + 1) << 1;
Left[J] = K - 1;
Right[J] = K;
}
}
/* rearrange the splay tree for each succeeding character */
void Splay(CodeType Plain)
{
DownIndex A, B;
UpIndex C, D;
A = Plain + MaxChar;
do
{
/* walk up the tree semi-rotating pairs */
C = Up[A];
if (C != Root)
{
/* a pair remains */
D = Up[C];
/* exchange children of pair */
B = Left[D];
if (C == B)
{
B = Right[D];
Right[D] = A;
}
else
Left[D] = A;
if (A == Left[C])
Left[C] = B;
else
Right[C] = B;
Up[A] = D;
Up[B] = C;
A = D;
}
else
A = C;
} while (A != Root);
}
/* flush output buffer and reset */
void FlushOutBuffer(void)
{
if (OutSize > 0)
{
fwrite(OutBuffer+1, sizeof(byte), OutSize, OutF);
OutSize = 0;
}
}
/* output byte in OutByte */
void WriteByte(void)
{
if (OutSize == BufSize)
FlushOutBuffer();
OutSize++;
OutBuffer[OutSize] = OutByte;
}
/* compress a single char */
void Compress(CodeType Plain)
{
DownIndex A;
UpIndex U;
word Sp;
bool Stack[PredMax+1];
A = Plain + MaxChar;
Sp = 0;
/* walk up the tree pushing bits onto stack */
do
{
U = Up[A];
Stack[Sp] = (Right[U] == A);
Sp++;
A = U;
} while (A != Root);
/* unstack to transmit bits in correct order */
do
{
Sp--;
if (Stack[Sp])
OutByte |= BitMask[BitPos];
if (BitPos == 7)
{
/* byte filled with bits, write it out */
WriteByte();
BitPos = 0;
OutByte = 0;
}
else
BitPos++;
} while (Sp != 0);
/* update the tree */
Splay(Plain);
}
/* compress input file, writing to outfile */
void CompressFile(void)
{
FileHeader Header;
/* write header to output */
Header.Signature = Sig;
fwrite(&Header, sizeof(FileHeader), 1, OutF);
/* compress file */
OutSize = 0;
BitPos = 0;
OutByte = 0;
do
{
InSize = fread(InBuffer+1, sizeof(byte), BufSize, InF);
for (Index = 1; Index <= InSize; Index++)
Compress(InBuffer[Index]);
} while (InSize >= BufSize);
/* Mark end of file */
Compress(EofChar);
/* Flush buffers */
if (BitPos != 0)
WriteByte();
FlushOutBuffer();
}
/* read a compressed file header */
void ReadHeader(void)
{
FileHeader Header;
fread(&Header, sizeof(FileHeader), 1, InF);
if (Header.Signature != Sig)
{
printf("Unrecognized file format!\n");
exit(1);
}
}
/* return next byte from compressed input */
byte GetByte(void)
{
Index++;
if (Index > InSize)
{
/* reload file buffer */
InSize = fread(InBuffer+1, sizeof(byte), BufSize, InF);
Index = 1;
/* end of file handled by special marker in compressed file */
}
/* get next byte from buffer */
return InBuffer[Index];
}
/* return next char from compressed input */
CodeType Expand(void)
{
DownIndex A;
/* scan the tree to a leaf, which determines the character */
A = Root;
do
{
if (BitPos == 7)
{
/* used up bits in current byte, get another */
InByte = GetByte();
BitPos = 0;
}
else
BitPos++;
if ((InByte & BitMask[BitPos]) == 0)
A = Left[A];
else
A = Right[A];
} while (A <= PredMax);
/* Update the code tree */
A -= MaxChar;
Splay(A);
/* return the character */
return A;
}
/* uncompress the file and write output */
void ExpandFile(void)
{
/* force buffer load first time */
Index = 0;
InSize = 0;
/* nothing in output buffer */
OutSize = 0;
/* force bit buffer load first time */
BitPos = 7;
/* read and expand the compressed input */
OutByte = Expand();
while (OutByte != EofChar)
{
WriteByte();
OutByte = Expand();
}
/* flush the output buffer */
FlushOutBuffer();
}
int main(int argc, char *argv[])
{
if (argc < 3)
{
printf(Usage);
exit(1);
}
if (argc == 4 && (strlen(argv[1]) == 1) && toupper(argv[1][0]) == 'X')
{
strcpy(InName, argv[2]);
strcpy(OutName, argv[3]);
CompressFlag = false;
}
else
{
if (argc == 4)
{
printf(Usage);
exit(1);
}
CompressFlag = true;
strcpy(InName, argv[1]);
strcpy(OutName, argv[2]);
}
InitializeSplay();
if ((InF = fopen(InName, "rb")) == NULL)
{
printf("Unable to open input file: %s\n", InName);
exit(1);
}
if ((OutF = fopen(OutName, "wb")) == NULL)
{
printf("Unable to open output file: %s\n", OutName);
exit(1);
}
if (CompressFlag)
CompressFile();
else
{
ReadHeader();
ExpandFile();
}
fclose(InF);
fclose(OutF);
return 0;
} |
最佳答案
查看完整内容
应该是霍夫曼压缩 解压缩文件.InitializeSplay //构建一个完全二叉树, 二叉树元素按顺序排列, 每个元素可理解为代表一个字符0x00~0xff......Splay //将被访问的字符上浮, 以便访问频率高的字符可以占据较小的权重, 即能用较少的bits表示Compress //将字符位于树中的节点位置到树根的路径表示成二进制位, 如果累积到达8位(一个字节)则记录下该字节
|
免费注册
发表于 2009-05-30 21:04
