deflaterhuffman.java

gcc的组建

      int max_count;               /* max repeat count */
      int min_count;               /* min repeat count */
      int count;                   /* repeat count of the current code */
      int curlen = -1;             /* length of current code */
      
      int i = 0;
      while (i < numCodes)
	{
	  count = 1;
	  int nextlen = length[i];
	  if (nextlen == 0) 
	    {
	      max_count = 138;
	      min_count = 3;
	    }
	  else
	    {
	      max_count = 6;
	      min_count = 3;
	      if (curlen != nextlen)
		{
		  blTree.freqs[nextlen]++;
		  count = 0;
		}
	    }
	  curlen = nextlen;
	  i++;

	  while (i < numCodes && curlen == length[i])
	    {
	      i++;
	      if (++count >= max_count)
		break;
	    }

	  if (count < min_count)
	    blTree.freqs[curlen] += count;
	  else if (curlen != 0)
	    blTree.freqs[REP_3_6]++;
	  else if (count <= 10)
	    blTree.freqs[REP_3_10]++;
	  else
	    blTree.freqs[REP_11_138]++;
	}
    }

    void writeTree(Tree blTree)
    {
      int max_count;               /* max repeat count */
      int min_count;               /* min repeat count */
      int count;                   /* repeat count of the current code */
      int curlen = -1;             /* length of current code */
      
      int i = 0;
      while (i < numCodes)
	{
	  count = 1;
	  int nextlen = length[i];
	  if (nextlen == 0) 
	    {
	      max_count = 138;
	      min_count = 3;
	    }
	  else
	    {
	      max_count = 6;
	      min_count = 3;
	      if (curlen != nextlen)
		{
		  blTree.writeSymbol(nextlen);
		  count = 0;
		}
	    }
	  curlen = nextlen;
	  i++;

	  while (i < numCodes && curlen == length[i])
	    {
	      i++;
	      if (++count >= max_count)
		break;
	    }

	  if (count < min_count)
	    {
	      while (count-- > 0)
		blTree.writeSymbol(curlen);
	    }
	  else if (curlen != 0)
	    {
	      blTree.writeSymbol(REP_3_6);
	      pending.writeBits(count - 3, 2);
	    }
	  else if (count <= 10)
	    {
	      blTree.writeSymbol(REP_3_10);
	      pending.writeBits(count - 3, 3);
	    }
	  else
	    {
	      blTree.writeSymbol(REP_11_138);
	      pending.writeBits(count - 11, 7);
	    }
	}
    }
  }



  DeflaterPending pending;
  private Tree literalTree, distTree, blTree;

  private short d_buf[];
  private byte l_buf[];
  private int last_lit;
  private int extra_bits;

  private static short staticLCodes[];
  private static byte  staticLLength[];
  private static short staticDCodes[];
  private static byte  staticDLength[];

  /**
   * Reverse the bits of a 16 bit value.
   */
  static short bitReverse(int value) {
    return (short) (bit4Reverse.charAt(value & 0xf) << 12
		    | bit4Reverse.charAt((value >> 4) & 0xf) << 8
		    | bit4Reverse.charAt((value >> 8) & 0xf) << 4
		    | bit4Reverse.charAt(value >> 12));
  }

  static {
    /* See RFC 1951 3.2.6 */
    /* Literal codes */
    staticLCodes = new short[LITERAL_NUM];
    staticLLength = new byte[LITERAL_NUM];
    int i = 0;
    while (i < 144) {
      staticLCodes[i] = bitReverse((0x030 + i) << 8);
      staticLLength[i++] = 8;
    }
    while (i < 256) {
      staticLCodes[i] = bitReverse((0x190 - 144 + i) << 7);
      staticLLength[i++] = 9;
    }
    while (i < 280) {
      staticLCodes[i] = bitReverse((0x000 - 256 + i) << 9);
      staticLLength[i++] = 7;
    }
    while (i < LITERAL_NUM) {
      staticLCodes[i] = bitReverse((0x0c0 - 280 + i)  << 8);
      staticLLength[i++] = 8;
    }

    /* Distant codes */
    staticDCodes = new short[DIST_NUM];
    staticDLength = new byte[DIST_NUM];
    for (i = 0; i < DIST_NUM; i++) {
      staticDCodes[i] = bitReverse(i << 11);
      staticDLength[i] = 5;
    }
  }
    
  public DeflaterHuffman(DeflaterPending pending) 
  {
    this.pending = pending;

    literalTree = new Tree(LITERAL_NUM, 257, 15);
    distTree    = new Tree(DIST_NUM, 1, 15);
    blTree      = new Tree(BITLEN_NUM, 4, 7);

    d_buf = new short[BUFSIZE];
    l_buf = new byte [BUFSIZE];
  }

  public final void reset() {
    last_lit = 0;
    extra_bits = 0;
    literalTree.reset();
    distTree.reset();
    blTree.reset();
  }

  private int l_code(int len) {
    if (len == 255)
      return 285;

    int code = 257;
    while (len >= 8)
      {
	code += 4;
	len >>= 1;
      }
    return code + len;
  }

  private int d_code(int distance) {
    int code = 0;
    while (distance >= 4)
      {
	code += 2;
	distance >>= 1;
      }
    return code + distance;
  }

  public void sendAllTrees(int blTreeCodes) {
    blTree.buildCodes();
    literalTree.buildCodes();
    distTree.buildCodes();
    pending.writeBits(literalTree.numCodes - 257, 5);
    pending.writeBits(distTree.numCodes - 1, 5);
    pending.writeBits(blTreeCodes - 4, 4);
    for (int rank = 0; rank < blTreeCodes; rank++)
      pending.writeBits(blTree.length[BL_ORDER[rank]], 3);
    literalTree.writeTree(blTree);
    distTree.writeTree(blTree);
    if (DeflaterConstants.DEBUGGING)
      blTree.checkEmpty();
  }

  public void compressBlock() {
    for (int i = 0; i < last_lit; i++) 
      {
	int litlen = l_buf[i] & 0xff;
	int dist = d_buf[i];
	if (dist-- != 0)
	  {
	    if (DeflaterConstants.DEBUGGING)
	      System.err.print("["+(dist+1)+","+(litlen+3)+"]: ");

	    int lc = l_code(litlen);
	    literalTree.writeSymbol(lc);

	    int bits = (lc - 261) / 4;
	    if (bits > 0 && bits <= 5)
	      pending.writeBits(litlen & ((1 << bits) - 1), bits);

	    int dc = d_code(dist);
	    distTree.writeSymbol(dc);

	    bits = dc / 2 - 1;
	    if (bits > 0)
	      pending.writeBits(dist & ((1 << bits) - 1), bits);
	  }
	else
	  {
	    if (DeflaterConstants.DEBUGGING)
	      {
		if (litlen > 32 && litlen < 127)
		  System.err.print("("+(char)litlen+"): ");
		else
		  System.err.print("{"+litlen+"}: ");
	      }
	    literalTree.writeSymbol(litlen);
	  }
      }
    if (DeflaterConstants.DEBUGGING)
      System.err.print("EOF: ");
    literalTree.writeSymbol(EOF_SYMBOL);
    if (DeflaterConstants.DEBUGGING)
      {
	literalTree.checkEmpty();
	distTree.checkEmpty();
      }
  }

  public void flushStoredBlock(byte[] stored, 
			       int stored_offset, int stored_len,
			       boolean lastBlock) {
    if (DeflaterConstants.DEBUGGING)
      System.err.println("Flushing stored block "+ stored_len);
    pending.writeBits((DeflaterConstants.STORED_BLOCK << 1)
		      + (lastBlock ? 1 : 0), 3);
    pending.alignToByte();
    pending.writeShort(stored_len);
    pending.writeShort(~stored_len);
    pending.writeBlock(stored, stored_offset, stored_len);
    reset();
  }

  public void flushBlock(byte[] stored, int stored_offset, int stored_len,
			 boolean lastBlock) {
    literalTree.freqs[EOF_SYMBOL]++;

    /* Build trees */
    literalTree.buildTree();
    distTree.buildTree();

    /* Calculate bitlen frequency */
    literalTree.calcBLFreq(blTree);
    distTree.calcBLFreq(blTree);

    /* Build bitlen tree */
    blTree.buildTree();

    int blTreeCodes = 4;
    for (int i = 18; i > blTreeCodes; i--)
      {
	if (blTree.length[BL_ORDER[i]] > 0)
	  blTreeCodes = i+1;
      }
    int opt_len = 14 + blTreeCodes * 3 + blTree.getEncodedLength()
      + literalTree.getEncodedLength() + distTree.getEncodedLength()
      + extra_bits;

    int static_len = extra_bits;
    for (int i = 0; i < LITERAL_NUM; i++)
      static_len += literalTree.freqs[i] * staticLLength[i];
    for (int i = 0; i < DIST_NUM; i++)
      static_len += distTree.freqs[i] * staticDLength[i];
    if (opt_len >= static_len)
      {
	/* Force static trees */
	opt_len = static_len;
      }

    if (stored_offset >= 0 && stored_len+4 < opt_len >> 3)
      {
	/* Store Block */
	if (DeflaterConstants.DEBUGGING)
	  System.err.println("Storing, since " + stored_len + " < " + opt_len
			     + " <= " + static_len);
	flushStoredBlock(stored, stored_offset, stored_len, lastBlock);
      }
    else if (opt_len == static_len)
      {
	/* Encode with static tree */
	pending.writeBits((DeflaterConstants.STATIC_TREES << 1)
			  + (lastBlock ? 1 : 0), 3);
	literalTree.setStaticCodes(staticLCodes, staticLLength);
	distTree.setStaticCodes(staticDCodes, staticDLength);
	compressBlock();
	reset();
      }
    else
      {
	/* Encode with dynamic tree */
	pending.writeBits((DeflaterConstants.DYN_TREES << 1)
			  + (lastBlock ? 1 : 0), 3);
	sendAllTrees(blTreeCodes);
	compressBlock();
	reset();
      }
  }

  public final boolean isFull()
  {
    return last_lit == BUFSIZE;
  }

  public final boolean tallyLit(int lit) 
  {
    if (DeflaterConstants.DEBUGGING)
      {
	if (lit > 32 && lit < 127)
	  System.err.println("("+(char)lit+")");
	else
	  System.err.println("{"+lit+"}");
      }
    d_buf[last_lit] = 0;
    l_buf[last_lit++] = (byte) lit;
    literalTree.freqs[lit]++;
    return last_lit == BUFSIZE;
  }

  public final boolean tallyDist(int dist, int len) 
  {
    if (DeflaterConstants.DEBUGGING)
      System.err.println("["+dist+","+len+"]");

    d_buf[last_lit] = (short) dist;
    l_buf[last_lit++] = (byte) (len - 3);

    int lc = l_code(len-3);
    literalTree.freqs[lc]++;
    if (lc >= 265 && lc < 285)
      extra_bits += (lc - 261) / 4;

    int dc = d_code(dist-1);
    distTree.freqs[dc]++;
    if (dc >= 4)
      extra_bits += dc / 2 - 1;
    return last_lit == BUFSIZE;
  }
}