?? lz.cpp
字號:
// lz.cpp : Defines the entry point for the console application.
//
#include <windows.h>
#include <stdio.h>
#include <memory.h>
#ifndef _WIX_LZ77_COMPRESS_HEADER_001_
#define _WIX_LZ77_COMPRESS_HEADER_001_
#endif
// 滑動窗口的字節大小
#define _MAX_WINDOW_SIZE 65536
// 對滑動窗口中每一個2字節串排序
// 排序是為了進行快速術語匹配
// 排序的方法是用一個64k大小的指針數組
// 數組下標依次對應每一個2字節串：(00 00) (00 01) ... (01 00) (01 01) ...
// 每一個指針指向一個鏈表，鏈表中的節點為該2字節串的每一個出現位置
struct STIDXNODE
{
WORD off; // 在src中的偏移
WORD off2; // 用于對應的2字節串為重復字節的節點
// 指從 off 到 off2 都對應了該2字節串
WORD next; // 在SortHeap中的指針
};
BYTE* pWnd;
// 窗口大小最大為 64k ，并且不做滑動
// 每次最多只壓縮 64k 數據，這樣可以方便從文件中間開始解壓
// 當前窗口的長度
int nWndSize;
WORD SortTable[65536]; // 256 * 256 指向SortHeap中下標的指針
// 因為窗口不滑動，沒有刪除節點的操作，所以
// 節點可以在SortHeap 中連續分配
struct STIDXNODE* SortHeap;
int HeapPos; // 當前分配位置
// 當前輸出位置(字節偏移及位偏移)
int CurByte, CurBit;
int compress(BYTE* src, int srclen, BYTE* dest);
BOOL decompress(BYTE* src, int srclen, BYTE* dest);
int main(int argc, char* argv[])
{
if (argc != 4)
{
puts("Usage: ");
printf(" Compress : %s c sourcefile destfile\n", argv[0]);
printf(" Decompress : %s d sourcefile destfile\n", argv[0]);
return 0;
}
BYTE soubuf[65536];
BYTE destbuf[65536 + 16];
FILE* in;
FILE* out;
//打開源文件
in = fopen(argv[2], "rb");
if (in == NULL)
{
puts("Can't open source file");
return 0;
}
//打開目標文件
out = fopen(argv[3], "wb");
if (out == NULL)
{
puts("Can't open dest file");
fclose(in);
return 0;
}
fseek(in, 0, SEEK_END);
long soulen = ftell(in);
fseek(in, 0, SEEK_SET);
SortHeap = new struct STIDXNODE[_MAX_WINDOW_SIZE];
WORD flag1, flag2;
if (argv[1][0] == 'c') // 對源文件進行壓縮
{
int last = soulen, act;
while ( last > 0 )
{
act = min(65536, last);
fread(soubuf, act, 1, in);
last -= act;
if (act == 65536) // 超過65536字節
flag1 = 0;
else
flag1 = act;
fwrite(&flag1, sizeof(WORD), 1, out);
int destlen = compress((BYTE*)soubuf, act, (BYTE*)destbuf);
if (destlen == 0) // 不能壓縮塊
{
flag2 = flag1;
fwrite(&flag2, sizeof(WORD), 1, out);
fwrite(soubuf, act, 1, out);
}
else
{
flag2 = (WORD)destlen;
fwrite(&flag2, sizeof(WORD), 1, out);
fwrite(destbuf, destlen, 1, out);
}
}
}
else if (argv[1][0] == 'd') // 解壓縮源文件
{
int last = soulen, act;
while (last > 0)
{
fread(&flag1, sizeof(WORD), 1, in);
fread(&flag2, sizeof(WORD), 1, in);
last -= 2 * sizeof(WORD);
if (flag1 == 0)
act = 65536;
else
act = flag1;
last-= flag2 ? (flag2) : act;
if (flag2 == flag1)
{
fread(soubuf, act, 1, in);
}
else
{
fread(destbuf, flag2, 1, in);
if (!decompress((BYTE*)soubuf, act, (BYTE*)destbuf))
{
puts("Decompress error");
fclose(in);
fclose(out);
return 0;
}
}
fwrite((BYTE*)soubuf, act, 1, out);
}
}
else
{
puts("Usage: ");
printf(" Compress : %s c sourcefile destfile\n", argv[0]);
printf(" Decompress : %s d sourcefile destfile\n", argv[0]);
}
//關閉源文件和目標文件
fclose(in);
fclose(out);
return 0;
}
/////////////////////////////////////////////////////////
// 取log2(n)的upper_bound
int UpperLog2(int n)
{
int i = 0;
if (n > 0)
{
int m = 1;
while(1)
{
if (m >= n)
return i;
m <<= 1;
i++;
}
}
else
return -1;
}
// UpperLog2
/////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////
// 取log2(n)的lower_bound
int LowerLog2(int n)
{
int i = 0;
if (n > 0)
{
int m = 1;
while(1)
{
if (m == n)
return i;
if (m > n)
return i - 1;
m <<= 1;
i++;
}
}
else
return -1;
}
// LowerLog2
/////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////
// 將位指針*piByte(字節偏移), *piBit(字節內位偏移)后移num位
void MovePos(int* piByte, int* piBit, int num)
{
num += (*piBit);
(*piByte) += num / 8;
(*piBit) = num % 8;
}
// MovePos
////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////
// 得到字節byte第pos位的值
// pos順序為高位起從0記數（左起）
BYTE GetBit(BYTE byte, int pos)
{
int j = 1;
j <<= 7 - pos;
if (byte & j)
return 1;
else
return 0;
}
// GetBit
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
// 設置byte的第iBit位為aBit
// iBit順序為高位起從0記數（左起）
void SetBit(BYTE* byte, int iBit, BYTE aBit)
{
if (aBit)
(*byte) |= (1 << (7 - iBit));
else
(*byte) &= ~(1 << (7 - iBit));
}
// SetBit
//////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////
// 將DWORD值從高位字節到低位字節排列
void InvertDWord(DWORD* pDW)
{
union UDWORD{ DWORD dw; BYTE b[4]; };
UDWORD* pUDW = (UDWORD*)pDW;
BYTE b;
b = pUDW->b[0]; pUDW->b[0] = pUDW->b[3]; pUDW->b[3] = b;
b = pUDW->b[1]; pUDW->b[1] = pUDW->b[2]; pUDW->b[2] = b;
}
// InvertDWord
//////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////
// CopyBitsInAByte : 在一個字節范圍內復制位流
// 參數含義同 CopyBits 的參數
// 說明：
// 此函數由 CopyBits 調用，不做錯誤檢查，即
// 假定要復制的位都在一個字節范圍內
void CopyBitsInAByte(BYTE* memDest, int nDestPos,
BYTE* memSrc, int nSrcPos, int nBits)
{
BYTE b1, b2;
b1 = *memSrc;
b1 <<= nSrcPos; b1 >>= 8 - nBits; // 將不用復制的位清0
b1 <<= 8 - nBits - nDestPos; // 將源和目的字節對齊
*memDest |= b1; // 復制值為1的位
b2 = 0xff; b2 <<= 8 - nDestPos; // 將不用復制的位置1
b1 |= b2;
b2 = 0xff; b2 >>= nDestPos + nBits;
b1 |= b2;
*memDest &= b1; // 復制值為0的位
}
// CopyBitsInAByte
/////////////////////////////////////////////////////////
////////////////////////////////////////////////////////
// CopyBits : 復制內存中的位流
// memDest - 目標數據區
// nDestPos - 目標數據區第一個字節中的起始位
// memSrc - 源數據區
// nSrcPos - 源數據區第一個字節的中起始位
// nBits - 要復制的位數
// 說明：
// 起始位的表示約定為從字節的高位至低位（由左至右）
// 依次為 0，1，... , 7
// 要復制的兩塊數據區不能有重合
void CopyBits(BYTE* memDest, int nDestPos,
BYTE* memSrc, int nSrcPos, int nBits)
{
int iByteDest = 0, iBitDest;
int iByteSrc = 0, iBitSrc = nSrcPos;
int nBitsToFill, nBitsCanFill;
while (nBits > 0)
{
// 計算要在目標區當前字節填充的位數
nBitsToFill = min(nBits, iByteDest ? 8 : 8 - nDestPos);
// 目標區當前字節要填充的起始位
iBitDest = iByteDest ? 0 : nDestPos;
// 計算可以一次從源數據區中復制的位數
nBitsCanFill = min(nBitsToFill, 8 - iBitSrc);
// 字節內復制
CopyBitsInAByte(memDest + iByteDest, iBitDest,
memSrc + iByteSrc, iBitSrc, nBitsCanFill);
// 如果還沒有復制完 nBitsToFill 個
if (nBitsToFill > nBitsCanFill)
{
iByteSrc++; iBitSrc = 0; iBitDest += nBitsCanFill;
CopyBitsInAByte(memDest + iByteDest, iBitDest,
memSrc + iByteSrc, iBitSrc,
nBitsToFill - nBitsCanFill);
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -