LZW緊縮算法 C#源碼。本站提示廣大學習愛好者：（LZW緊縮算法 C#源碼）文章只能為提供參考，不一定能成為您想要的結果。以下是LZW緊縮算法 C#源碼正文
using System;
using System.IO;
namespace Gif.Components
{
public class LZWEncoder
{
private static readonly int EOF = -1;
private int imgW, imgH;
private byte[] pixAry;
private int initCodeSize;
private int remaining;
private int curPixel;
// GIFCOMPR.C - GIF Image compression routines
//
// Lempel-Ziv compression based on 'compress'. GIF modifications by
// David Rowley ([email protected])
// General DEFINEs
static readonly int BITS = 12;
static readonly int HSIZE = 5003; // 80% occupancy
// GIF Image compression - modified 'compress'
//
// Based on: compress.c - File compression ala IEEE Computer, June 1984.
//
// By Authors: Spencer W. Thomas (decvax!harpo!utah-cs!utah-gr!thomas)
// Jim McKie (decvax!mcvax!jim)
// Steve Davies (decvax!vax135!petsd!peora!srd)
// Ken Turkowski (decvax!decwrl!turtlevax!ken)
// James A. Woods (decvax!ihnp4!ames!jaw)
// Joe Orost (decvax!vax135!petsd!joe)
int n_bits; // number of bits/code
int maxbits = BITS; // user settable max # bits/code
int maxcode; // maximum code, given n_bits
int maxmaxcode = 1 << BITS; // should NEVER generate this code
int[] htab = new int[HSIZE];//這個是放hash的筒子,在這外面可以很快的找到1個key
int[] codetab = new int[HSIZE];
int hsize = HSIZE; // for dynamic table sizing
int free_ent = 0; // first unused entry
// block compression parameters -- after all codes are used up,
// and compression rate changes, start over.
bool clear_flg = false;
// Algorithm: use open addressing double hashing (no chaining) on the
// prefix code / next character combination. We do a variant of Knuth's
// algorithm D (vol. 3, sec. 6.4) along with G. Knott's relatively-prime
// secondary probe. Here, the modular division first probe is gives way
// to a faster exclusive-or manipulation. Also do block compression with
// an adaptive reset, whereby the code table is cleared when the compression
// ratio decreases, but after the table fills. The variable-length output
// codes are re-sized at this point, and a special CLEAR code is generated
// for the decompressor. Late addition: construct the table according to
// file size for noticeable speed improvement on small files. Please direct
// questions about this implementation to ames!jaw.
int g_init_bits;
int ClearCode;
int EOFCode;
// output
//
// Output the given code.
// Inputs:
// code: A n_bits-bit integer. If == -1, then EOF. This assumes
// that n_bits =< wordsize - 1.
// Outputs:
// Outputs code to the file.
// Assumptions:
// Chars are 8 bits long.
// Algorithm:
// Maintain a BITS character long buffer (so that 8 codes will
// fit in it exactly). Use the VAX insv instruction to insert each
// code in turn. When the buffer fills up empty it and start over.
int cur_accum = 0;
int cur_bits = 0;
int [] masks =
{
0x0000,
0x0001,
0x0003,
0x0007,
0x000F,
0x001F,
0x003F,
0x007F,
0x00FF,
0x01FF,
0x03FF,
0x07FF,
0x0FFF,
0x1FFF,
0x3FFF,
0x7FFF,
0xFFFF };
// Number of characters so far in this 'packet'
int a_count;
// Define the storage for the packet accumulator
byte[] accum = new byte[256];
//----------------------------------------------------------------------------
public LZWEncoder(int width, int height, byte[] pixels, int color_depth)
{
imgW = width;
imgH = height;
pixAry = pixels;
initCodeSize = Math.Max(2, color_depth);
}
// Add a character to the end of the current packet, and if it is 254
// characters, flush the packet to disk.
void Add(byte c, Stream outs)
{
accum[a_count++] = c;
if (a_count >= 254)
Flush(outs);
}
// Clear out the hash table
// table clear for block compress
void ClearTable(Stream outs)
{
ResetCodeTable(hsize);
free_ent = ClearCode + 2;
clear_flg = true;
Output(ClearCode, outs);
}
// reset code table
// 全體初始化為-1
void ResetCodeTable(int hsize)
{
for (int i = 0; i < hsize; ++i)
htab[i] = -1;
}
void Compress(int init_bits, Stream outs)
{
int fcode;
int i /* = 0 */;
int c;
int ent;
int disp;
int hsize_reg;
int hshift;
// Set up the globals: g_init_bits - initial number of bits
//原始數據的字長,在gif文件中，原始數據的字長可認為1(單色圖),4(16色)，和8(256色)
//開端的時刻先加上1
//然則當原始數據長度為1的時刻，開端為3
//是以原始長度1->3,4->5,8->9
//?為什麼原始數據字長為1的時刻，開端長度為3呢？?
//假如+1=2，只能表現四種狀況，加上clearcode和endcode就用完了。所以必需擴大到3
g_init_bits = init_bits;
// Set up the necessary values
//能否須要加消除標記
//GIF為了進步緊縮率，采取的是變長的字長(VCL)。好比說原始數據是8位，那末開端先加上1位(8+1=9)
//當標號到2^9=512的時刻，跨越了以後長度9所能表示的最年夜值，此時前面的標號就必需用10位來表現
//以此類推，當標號到2^12的時刻，由於最年夜為12,不克不及持續擴大了，須要在2^12=4096的地位上拔出一個ClearCode,表現從這往後，從9位從新再來了
clear_flg = false;
n_bits = g_init_bits;
//取得n位數能表述的最年夜值(gif圖象中開端普通為3,5,9，故maxcode普通為7,31,511)
maxcode = MaxCode(n_bits);
//表現從這裡我從新開端結構字典字典了，之前的一切標志作廢，
//開端應用新的標志。這個標號集的年夜小若干比擬適合呢？聽說實際上是越年夜緊縮率越高（我小我感到太年夜了也不見得就好），
//不外處置的開支也呈指數增加
//gif劃定，clearcode的值為原始數據最年夜字長所能表達的數值+1;好比原始數據長度為8,則clearcode=1<<(9-1)=256
ClearCode = 1 << (init_bits - 1);
//停止標記為clearcode+1
EOFCode = ClearCode + 1;
//這個是消除停止的
free_ent = ClearCode + 2;
//清晰數目
a_count = 0; // clear packet
//從圖象中取得下一個像素
ent = NextPixel();
hshift = 0;
for (fcode = hsize; fcode < 65536; fcode *= 2)
++hshift;
//設置hash碼規模
hshift = 8 - hshift; // set hash code range bound
hsize_reg = hsize;
//消除固定年夜小的hash表，用於存儲標志，這個相當於字典
ResetCodeTable(hsize_reg); // clear hash table
Output(ClearCode, outs);
outer_loop : while ((c = NextPixel()) != EOF)
{
fcode = (c << maxbits) + ent;
i = (c << hshift) ^ ent; // xor hashing
//嘿嘿,小樣,又來了,我熟悉你
if (htab[i] == fcode)
{
ent = codetab[i];
continue;
}
//這小子,新來的
else if (htab[i] >= 0) // non-empty slot
{
disp = hsize_reg - i; // secondary hash (after G. Knott)
if (i == 0)
disp = 1;
do
{
if ((i -= disp) < 0)
i += hsize_reg;
if (htab[i] == fcode)
{
ent = codetab[i];
goto outer_loop;
}
} while (htab[i] >= 0);
}
Output(ent, outs);
//從這裡可以看出,ent就是前綴（prefix）,而以後正在處置的字符標記就是後綴（suffix）
ent = c;
//斷定終止停止符能否跨越以後位數所能表述的規模
if (free_ent < maxmaxcode)
{
//假如沒有超
codetab[i] = free_ent++; // code -> hashtable
//hash內外面樹立響應索引
htab[i] = fcode;
}
else
//解釋跨越了以後所能表述的規模,清空字典,從新再來
ClearTable(outs);
}
// Put out the final code.
Output(ent, outs);
Output(EOFCode, outs);
}
//----------------------------------------------------------------------------
public void Encode( Stream os)
{
os.WriteByte( Convert.ToByte( initCodeSize) ); // write "initial code size" byte
//這個圖象包括若干個像素
remaining = imgW * imgH; // reset navigation variables
//以後處置的像素索引
curPixel = 0;
Compress(initCodeSize + 1, os); // compress and write the pixel data
os.WriteByte(0); // write block terminator
}
// Flush the packet to disk, and reset the accumulator
void Flush(Stream outs)
{
if (a_count > 0)
{
outs.WriteByte( Convert.ToByte( a_count ));
outs.Write(accum, 0, a_count);
a_count = 0;
}
}
/// <summary>
/// 取得n位數所能表達的最年夜數值
/// </summary>
/// <param name="n_bits">位數，普通情形下n_bits = 9</param>
/// <returns>最年夜值,例如n_bits=8,則前往值就為2^8-1=255</returns>
int MaxCode(int n_bits)
{
return (1 << n_bits) - 1;
}
//----------------------------------------------------------------------------
// Return the next pixel from the image
//----------------------------------------------------------------------------
/// <summary>
/// 從圖象中取得下一個像素
/// </summary>
/// <returns></returns>
private int NextPixel()
{
//還剩若干個像素沒有處置
//假如沒有了,前往停止標記
if (remaining == 0)
return EOF;
//不然處置下一個,並將未處置像素數量-1
--remaining;
//以後處置的像素
int temp = curPixel + 1;
//假如以後處置像素在像素規模以內
if ( temp < pixAry.GetUpperBound( 0 ))
{
//下一個像素
byte pix = pixAry[curPixel++];
return pix & 0xff;
}
return 0xff;
}
/// <summary>
/// 輸入字到輸入流
/// </summary>
/// <param name="code">要輸入的字</param>
/// <param name="outs">輸入流</param>
void Output(int code, Stream outs)
{
//獲得以後標記位所能表現的最年夜標記值
cur_accum &= masks[cur_bits];
if (cur_bits > 0)
cur_accum |= (code << cur_bits);
else
//假如標記位為0,就將以後標號為輸出流
cur_accum = code;
//以後能標記的最年夜字長度(9-10-11-12-9-10。。。。。。。)
cur_bits += n_bits;
//假如以後最年夜長度年夜於8
while (cur_bits >= 8)
{
//向流中輸入一個字節
Add((byte) (cur_accum & 0xff), outs);
//將以後標號右移8位
cur_accum >>= 8;
cur_bits -= 8;
}
// If the next entry is going to be too big for the code size,
// then increase it, if possible.
if (free_ent > maxcode || clear_flg)
{
if (clear_flg)
{
maxcode = MaxCode(n_bits = g_init_bits);
clear_flg = false;
}
else
{
++n_bits;
if (n_bits == maxbits)
maxcode = maxmaxcode;
else
maxcode = MaxCode(n_bits);
}
}
if (code == EOFCode)
{
// At EOF, write the rest of the buffer.
while (cur_bits > 0)
{
Add((byte) (cur_accum & 0xff), outs);
cur_accum >>= 8;
cur_bits -= 8;
}
Flush(outs);
}
}
}
}
以上就是本文的全體內容，願望能給年夜家一個參考，也願望年夜家多多支撐。
