deflaterengine.java

来自「纯java操作系统jnode,安装简单和操作简单的个人使用的Java操作系统」· Java 代码 · 共 697 行 · 第 1/2 页

    if (niceLength > lookahead)
      niceLength = lookahead;

    if (DeflaterConstants.DEBUGGING 
	&& strstart > 2*WSIZE - MIN_LOOKAHEAD)
      throw new InternalError("need lookahead");
    
    do {
      if (DeflaterConstants.DEBUGGING && curMatch >= strstart)
	throw new InternalError("future match");
      if (window[curMatch + best_len] != scan_end
	  || window[curMatch + best_len - 1] != scan_end1
	  || window[curMatch] != window[scan]
	  || window[curMatch+1] != window[scan + 1])
	continue;

      match = curMatch + 2;      
      scan += 2;

      /* We check for insufficient lookahead only every 8th comparison;
       * the 256th check will be made at strstart+258.
       */
      while (window[++scan] == window[++match]
	     && window[++scan] == window[++match]
	     && window[++scan] == window[++match]
	     && window[++scan] == window[++match]
	     && window[++scan] == window[++match]
	     && window[++scan] == window[++match]
	     && window[++scan] == window[++match]
	     && window[++scan] == window[++match]
	     && scan < strend);

      if (scan > best_end) {
//  	if (DeflaterConstants.DEBUGGING && ins_h == 0)
//  	  System.err.println("Found match: "+curMatch+"-"+(scan-strstart));
	matchStart = curMatch;
	best_end = scan;
	best_len = scan - strstart;
	if (best_len >= niceLength)
	  break;

	scan_end1  = window[best_end-1];
	scan_end   = window[best_end];
      }
      scan = strstart;
    } while ((curMatch = (prev[curMatch & WMASK] & 0xffff)) > limit
	     && --chainLength != 0);

    matchLen = Math.min(best_len, lookahead);
    return matchLen >= MIN_MATCH;
  }

  void setDictionary(byte[] buffer, int offset, int length) {
    if (DeflaterConstants.DEBUGGING && strstart != 1)
      throw new IllegalStateException("strstart not 1");
    adler.update(buffer, offset, length);
    if (length < MIN_MATCH)
      return;
    if (length > MAX_DIST) {
      offset += length - MAX_DIST;
      length = MAX_DIST;
    }

    System.arraycopy(buffer, offset, window, strstart, length);

    updateHash();
    length--;
    while (--length > 0)
      {
	insertString();
	strstart++;
      }
    strstart += 2;
    blockStart = strstart;
  }    
    
  private boolean deflateStored(boolean flush, boolean finish)
  {
    if (!flush && lookahead == 0)
      return false;

    strstart += lookahead;
    lookahead = 0;

    int storedLen = strstart - blockStart;

    if ((storedLen >= DeflaterConstants.MAX_BLOCK_SIZE) 
	/* Block is full */
	|| (blockStart < WSIZE && storedLen >= MAX_DIST)
	/* Block may move out of window */
	|| flush)
      {
	boolean lastBlock = finish;
	if (storedLen > DeflaterConstants.MAX_BLOCK_SIZE)
	  {
	    storedLen = DeflaterConstants.MAX_BLOCK_SIZE;
	    lastBlock = false;
	  }

	if (DeflaterConstants.DEBUGGING)
	  System.err.println("storedBlock["+storedLen+","+lastBlock+"]");

	huffman.flushStoredBlock(window, blockStart, storedLen, lastBlock);
	blockStart += storedLen;
	return !lastBlock;
      }
    return true;
  }

  private boolean deflateFast(boolean flush, boolean finish)
  {
    if (lookahead < MIN_LOOKAHEAD && !flush)
      return false;

    while (lookahead >= MIN_LOOKAHEAD || flush)
      {
	if (lookahead == 0)
	  {
	    /* We are flushing everything */
	    huffman.flushBlock(window, blockStart, strstart - blockStart,
			       finish);
	    blockStart = strstart;
	    return false;
	  }

	if (strstart > 2 * WSIZE - MIN_LOOKAHEAD)
	  {
	    /* slide window, as findLongestMatch need this.
	     * This should only happen when flushing and the window
	     * is almost full.
	     */
	    slideWindow();
	  }

	int hashHead;
	if (lookahead >= MIN_MATCH 
	    && (hashHead = insertString()) != 0
	    && strategy != Deflater.HUFFMAN_ONLY
	    && strstart - hashHead <= MAX_DIST
	    && findLongestMatch(hashHead))
	  {
	    /* longestMatch sets matchStart and matchLen */
	    if (DeflaterConstants.DEBUGGING)
	      {
		for (int i = 0 ; i < matchLen; i++)
		  {
		    if (window[strstart+i] != window[matchStart + i])
		      throw new InternalError();
		  }
	      }
	    huffman.tallyDist(strstart - matchStart, matchLen);
	    
	    lookahead -= matchLen;
	    if (matchLen <= max_lazy && lookahead >= MIN_MATCH)
	      {
		while (--matchLen > 0)
		  {
		    strstart++;
		    insertString();
		  }
		strstart++;
	      }
	    else
	      {
		strstart += matchLen;
		if (lookahead >= MIN_MATCH - 1)
		  updateHash();
	      }
	    matchLen = MIN_MATCH - 1;
	    continue;
	  }
	else
	  {
	    /* No match found */
	    huffman.tallyLit(window[strstart] & 0xff);
	    strstart++;
	    lookahead--;
	  }

	if (huffman.isFull())
	  {
	    boolean lastBlock = finish && lookahead == 0;
	    huffman.flushBlock(window, blockStart, strstart - blockStart,
			       lastBlock);
	    blockStart = strstart;
	    return !lastBlock;
	  }
      }
    return true;
  }

  private boolean deflateSlow(boolean flush, boolean finish)
  {
    if (lookahead < MIN_LOOKAHEAD && !flush)
      return false;

    while (lookahead >= MIN_LOOKAHEAD || flush)
      {
	if (lookahead == 0)
	  {
	    if (prevAvailable)
	      huffman.tallyLit(window[strstart-1] & 0xff);
	    prevAvailable = false;

	    /* We are flushing everything */
	    if (DeflaterConstants.DEBUGGING && !flush)
	      throw new InternalError("Not flushing, but no lookahead");
	    huffman.flushBlock(window, blockStart, strstart - blockStart,
			       finish);
	    blockStart = strstart;
	    return false;
	  }

	if (strstart >= 2 * WSIZE - MIN_LOOKAHEAD)
	  {
	    /* slide window, as findLongestMatch need this.
	     * This should only happen when flushing and the window
	     * is almost full.
	     */
	    slideWindow();
	  }

	int prevMatch = matchStart;
	int prevLen = matchLen;
	if (lookahead >= MIN_MATCH)
	  {
	    int hashHead = insertString();
	    if (strategy != Deflater.HUFFMAN_ONLY
		&& hashHead != 0 && strstart - hashHead <= MAX_DIST
		&& findLongestMatch(hashHead))
	      {
		/* longestMatch sets matchStart and matchLen */
		
		/* Discard match if too small and too far away */
		if (matchLen <= 5
		    && (strategy == Deflater.FILTERED
			|| (matchLen == MIN_MATCH
			    && strstart - matchStart > TOO_FAR))) {
		  matchLen = MIN_MATCH - 1;
		}
	      }
	  }
	
	/* previous match was better */
	if (prevLen >= MIN_MATCH && matchLen <= prevLen)
	  {
	    if (DeflaterConstants.DEBUGGING)
	      {
		for (int i = 0 ; i < matchLen; i++)
		  {
		    if (window[strstart-1+i] != window[prevMatch + i])
		      throw new InternalError();
		  }
	      }
	    huffman.tallyDist(strstart - 1 - prevMatch, prevLen);
	    prevLen -= 2;
	    do 
	      {
		strstart++;
		lookahead--;
		if (lookahead >= MIN_MATCH)
		  insertString();
	      }
	    while (--prevLen > 0);
	    strstart ++;
	    lookahead--;
	    prevAvailable = false;
	    matchLen = MIN_MATCH - 1;
	  }
	else
	  {
	    if (prevAvailable)
	      huffman.tallyLit(window[strstart-1] & 0xff);
	    prevAvailable = true;
	    strstart++;
	    lookahead--;
	  }

	if (huffman.isFull())
	  {
	    int len = strstart - blockStart;
	    if (prevAvailable)
	      len--;
	    boolean lastBlock = (finish && lookahead == 0 && !prevAvailable);
	    huffman.flushBlock(window, blockStart, len, lastBlock);
	    blockStart += len;
	    return !lastBlock;
	  }
      }
    return true;
  } 

  public boolean deflate(boolean flush, boolean finish) 
  {
    boolean progress;
    do
      {
	fillWindow();
	boolean canFlush = flush && inputOff == inputEnd;
	if (DeflaterConstants.DEBUGGING)
	  System.err.println("window: ["+blockStart+","+strstart+","
			     +lookahead+"], "+comprFunc+","+canFlush);
	switch (comprFunc)
	  {
	  case DEFLATE_STORED:
	    progress = deflateStored(canFlush, finish);
	    break;
	  case DEFLATE_FAST:
	    progress = deflateFast(canFlush, finish);
	    break;
	  case DEFLATE_SLOW:
	    progress = deflateSlow(canFlush, finish);
	    break;
	  default:
	    throw new InternalError();
	  }
      }
    while (pending.isFlushed()  /* repeat while we have no pending output */
	   && progress);        /* and progress was made */

    return progress;
  }

  public void setInput(byte[] buf, int off, int len)
  {
    if (inputOff < inputEnd)
      throw new IllegalStateException
	("Old input was not completely processed");

    int end = off + len;

    /* We want to throw an ArrayIndexOutOfBoundsException early.  The
     * check is very tricky: it also handles integer wrap around.  
     */
    if (0 > off || off > end || end > buf.length)
      throw new ArrayIndexOutOfBoundsException();

    inputBuf = buf;
    inputOff = off;
    inputEnd = end;
  }

  public final boolean needsInput()
  {
    return inputEnd == inputOff;
  }
}