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 (mgardi@watdcsu.waterloo.edu)

  // 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];//這個(gè)是放hash的筒子,在這里面可以很快的找到1個(gè)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
            //原始數(shù)據(jù)的字長(zhǎng),在gif文件中，原始數(shù)據(jù)的字長(zhǎng)可以為1(單色圖),4(16色)，和8(256色)
            //開始的時(shí)候先加上1
            //但是當(dāng)原始數(shù)據(jù)長(zhǎng)度為1的時(shí)候，開始為3
            //因此原始長(zhǎng)度1->3,4->5,8->9

            //?為何原始數(shù)據(jù)字長(zhǎng)為1的時(shí)候，開始長(zhǎng)度為3呢？?
            //如果+1=2，只能表示四種狀態(tài)，加上clearcode和endcode就用完了。所以必須擴(kuò)展到3
   g_init_bits = init_bits;

   // Set up the necessary values
            //是否需要加清除標(biāo)志
            //GIF為了提高壓縮率，采用的是變長(zhǎng)的字長(zhǎng)(VCL)。比如說(shuō)原始數(shù)據(jù)是8位，那么開始先加上1位(8+1=9)
            //當(dāng)標(biāo)號(hào)到2^9=512的時(shí)候，超過(guò)了當(dāng)前長(zhǎng)度9所能表現(xiàn)的最大值，此時(shí)后面的標(biāo)號(hào)就必須用10位來(lái)表示
            //以此類推，當(dāng)標(biāo)號(hào)到2^12的時(shí)候，因?yàn)樽畲鬄?2,不能繼續(xù)擴(kuò)展了，需要在2^12=4096的位置上插入一個(gè)ClearCode,表示從這往后，從9位重新再來(lái)了        
   clear_flg = false;
   n_bits = g_init_bits;
            //獲得n位數(shù)能表述的最大值(gif圖像中開始一般為3,5,9，故maxcode一般為7,31,511)
   maxcode = MaxCode(n_bits);
            //表示從這里我重新開始構(gòu)造字典字典了，以前的所有標(biāo)記作廢，
            //開始使用新的標(biāo)記。這個(gè)標(biāo)號(hào)集的大小多少比較合適呢？據(jù)說(shuō)理論上是越大壓縮率越高（我個(gè)人感覺(jué)太大了也不見(jiàn)得就好），
            //不過(guò)處理的開銷也呈指數(shù)增長(zhǎng)
            //gif規(guī)定，clearcode的值為原始數(shù)據(jù)最大字長(zhǎng)所能表達(dá)的數(shù)值+1;比如原始數(shù)據(jù)長(zhǎng)度為8,則clearcode=1<<(9-1)=256
   ClearCode = 1 << (init_bits - 1);
            //結(jié)束標(biāo)志為clearcode+1
   EOFCode = ClearCode + 1;
            //這個(gè)是解除結(jié)束的
   free_ent = ClearCode + 2;
            //清楚數(shù)量
   a_count = 0; // clear packet
            //從圖像中獲得下一個(gè)像素
   ent = NextPixel();

   hshift = 0;
   for (fcode = hsize; fcode < 65536; fcode *= 2)
    ++hshift;
            //設(shè)置hash碼范圍
   hshift = 8 - hshift; // set hash code range bound

   hsize_reg = hsize;
            //清除固定大小的hash表，用于存儲(chǔ)標(biāo)記，這個(gè)相當(dāng)于字典
   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
                             //嘿嘿,小樣,又來(lái)了,我認(rèn)識(shí)你
        if (htab[i] == fcode)
        {
         ent = codetab[i];
         continue;
        }
                             //這小子,新來(lái)的
        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）,而當(dāng)前正在處理的字符標(biāo)志就是后綴（suffix）
        ent = c;
                             //判斷終止結(jié)束符是否超過(guò)當(dāng)前位數(shù)所能表述的范圍
        if (free_ent < maxmaxcode)
        {
                                 //如果沒(méi)有超
         codetab[i] = free_ent++; // code -> hashtable
                                 //hash表里面建立相應(yīng)索引
         htab[i] = fcode;
        }
        else
                                 //說(shuō)明超過(guò)了當(dāng)前所能表述的范圍,清空字典,重新再來(lái)
         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
            //這個(gè)圖像包含多少個(gè)像素
   remaining = imgW * imgH; // reset navigation variables
            //當(dāng)前處理的像素索引
   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位數(shù)所能表達(dá)的最大數(shù)值
        /// </summary>
        /// <param name="n_bits">位數(shù)，一般情況下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>
        /// 從圖像中獲得下一個(gè)像素
        /// </summary>
        /// <returns></returns>
  private int NextPixel()
  {
            //還剩多少個(gè)像素沒(méi)有處理
            //如果沒(méi)有了,返回結(jié)束標(biāo)志
   if (remaining == 0)
    return EOF;
            //否則處理下一個(gè),并將未處理像素?cái)?shù)目-1
   --remaining;
            //當(dāng)前處理的像素
   int temp = curPixel + 1;
            //如果當(dāng)前處理像素在像素范圍之內(nèi)
   if ( temp < pixAry.GetUpperBound( 0 ))
   {
                //下一個(gè)像素
    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)
  {
            //得到當(dāng)前標(biāo)志位所能表示的最大標(biāo)志值
   cur_accum &= masks[cur_bits];

   if (cur_bits > 0)
    cur_accum |= (code << cur_bits);
   else
               //如果標(biāo)志位為0,就將當(dāng)前標(biāo)號(hào)為輸入流
    cur_accum = code;
            //當(dāng)前能標(biāo)志的最大字長(zhǎng)度(9-10-11-12-9-10。。。。。。。)
   cur_bits += n_bits;
            //如果當(dāng)前最大長(zhǎng)度大于8
   while (cur_bits >= 8)
   {
                //向流中輸出一個(gè)字節(jié)
    Add((byte) (cur_accum & 0xff), outs);
                //將當(dāng)前標(biāo)號(hào)右移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);
   }
  }
 }
}