libjava/classpath/java/util/zip/DeflaterHuffman.java

   1 /* DeflaterHuffman.java --
   2    Copyright (C) 2001, 2004, 2005  Free Software Foundation, Inc.
   3
   4 This file is part of GNU Classpath.
   5
   6 GNU Classpath is free software; you can redistribute it and/or modify
   7 it under the terms of the GNU General Public License as published by
   8 the Free Software Foundation; either version 2, or (at your option)
   9 any later version.
  10
  11 GNU Classpath is distributed in the hope that it will be useful, but
  12 WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 General Public License for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GNU Classpath; see the file COPYING.  If not, write to the
  18 Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  19 02110-1301 USA.
  20
  21 Linking this library statically or dynamically with other modules is
  22 making a combined work based on this library.  Thus, the terms and
  23 conditions of the GNU General Public License cover the whole
  24 combination.
  25
  26 As a special exception, the copyright holders of this library give you
  27 permission to link this library with independent modules to produce an
  28 executable, regardless of the license terms of these independent
  29 modules, and to copy and distribute the resulting executable under
  30 terms of your choice, provided that you also meet, for each linked
  31 independent module, the terms and conditions of the license of that
  32 module.  An independent module is a module which is not derived from
  33 or based on this library.  If you modify this library, you may extend
  34 this exception to your version of the library, but you are not
  35 obligated to do so.  If you do not wish to do so, delete this
  36 exception statement from your version. */
  37
  38 package java.util.zip;
  39
  40 /**
  41  * This is the DeflaterHuffman class.
  42  *
  43  * This class is <i>not</i> thread safe.  This is inherent in the API, due
  44  * to the split of deflate and setInput.
  45  *
  46  * @author Jochen Hoenicke
  47  * @date Jan 6, 2000
  48  */
  49 class DeflaterHuffman
  50 {
  51   private static final int BUFSIZE = 1 << (DeflaterConstants.DEFAULT_MEM_LEVEL + 6);
  52   private static final int LITERAL_NUM = 286;
  53   private static final int DIST_NUM = 30;
  54   private static final int BITLEN_NUM = 19;
  55   private static final int REP_3_6    = 16;
  56   private static final int REP_3_10   = 17;
  57   private static final int REP_11_138 = 18;
  58   private static final int EOF_SYMBOL = 256;
  59   private static final int[] BL_ORDER =
  60   { 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 };
  61
  62   private static final String bit4Reverse =
  63     "\000\010\004\014\002\012\006\016\001\011\005\015\003\013\007\017";
  64
  65   class Tree {
  66     short[] freqs;
  67     short[] codes;
  68     byte[]  length;
  69     int[]   bl_counts;
  70     int     minNumCodes, numCodes;
  71     int     maxLength;
  72
  73     Tree(int elems, int minCodes, int maxLength) {
  74       this.minNumCodes = minCodes;
  75       this.maxLength  = maxLength;
  76       freqs  = new short[elems];
  77       bl_counts = new int[maxLength];
  78     }
  79
  80     void reset() {
  81       for (int i = 0; i < freqs.length; i++)
  82         freqs[i] = 0;
  83       codes = null;
  84       length = null;
  85     }
  86
  87     final void writeSymbol(int code)
  88     {
  89       if (DeflaterConstants.DEBUGGING)
  90         {
  91           freqs[code]--;
  92 //        System.err.print("writeSymbol("+freqs.length+","+code+"): ");
  93         }
  94       pending.writeBits(codes[code] & 0xffff, length[code]);
  95     }
  96
  97     final void checkEmpty()
  98     {
  99       boolean empty = true;
 100       for (int i = 0; i < freqs.length; i++)
 101         if (freqs[i] != 0)
 102           {
 103             System.err.println("freqs["+i+"] == "+freqs[i]);
 104             empty = false;
 105           }
 106       if (!empty)
 107         throw new InternalError();
 108       System.err.println("checkEmpty suceeded!");
 109     }
 110
 111     void setStaticCodes(short[] stCodes, byte[] stLength)
 112     {
 113       codes = stCodes;
 114       length = stLength;
 115     }
 116
 117     public void buildCodes() {
 118       int[] nextCode = new int[maxLength];
 119       int code = 0;
 120       codes = new short[freqs.length];
 121
 122       if (DeflaterConstants.DEBUGGING)
 123         System.err.println("buildCodes: "+freqs.length);
 124       for (int bits = 0; bits < maxLength; bits++)
 125         {
 126           nextCode[bits] = code;
 127           code += bl_counts[bits] << (15 - bits);
 128           if (DeflaterConstants.DEBUGGING)
 129             System.err.println("bits: "+(bits+1)+" count: "+bl_counts[bits]
 130                                +" nextCode: "+Integer.toHexString(code));
 131         }
 132       if (DeflaterConstants.DEBUGGING && code != 65536)
 133         throw new RuntimeException("Inconsistent bl_counts!");
 134
 135       for (int i=0; i < numCodes; i++)
 136         {
 137           int bits = length[i];
 138           if (bits > 0)
 139             {
 140               if (DeflaterConstants.DEBUGGING)
 141                 System.err.println("codes["+i+"] = rev("
 142                                    +Integer.toHexString(nextCode[bits-1])+"),"
 143                                    +bits);
 144               codes[i] = bitReverse(nextCode[bits-1]);
 145               nextCode[bits-1] += 1 << (16 - bits);
 146             }
 147         }
 148     }
 149
 150     private void buildLength(int childs[])
 151     {
 152       this.length = new byte [freqs.length];
 153       int numNodes = childs.length / 2;
 154       int numLeafs = (numNodes + 1) / 2;
 155       int overflow = 0;
 156
 157       for (int i = 0; i < maxLength; i++)
 158         bl_counts[i] = 0;
 159
 160       /* First calculate optimal bit lengths */
 161       int lengths[] = new int[numNodes];
 162       lengths[numNodes-1] = 0;
 163       for (int i = numNodes - 1; i >= 0; i--)
 164         {
 165           if (childs[2*i+1] != -1)
 166             {
 167               int bitLength = lengths[i] + 1;
 168               if (bitLength > maxLength)
 169                 {
 170                   bitLength = maxLength;
 171                   overflow++;
 172                 }
 173               lengths[childs[2*i]] = lengths[childs[2*i+1]] = bitLength;
 174             }
 175           else
 176             {
 177               /* A leaf node */
 178               int bitLength = lengths[i];
 179               bl_counts[bitLength - 1]++;
 180               this.length[childs[2*i]] = (byte) lengths[i];
 181             }
 182         }
 183
 184       if (DeflaterConstants.DEBUGGING)
 185         {
 186           System.err.println("Tree "+freqs.length+" lengths:");
 187           for (int i=0; i < numLeafs; i++)
 188             System.err.println("Node "+childs[2*i]+" freq: "+freqs[childs[2*i]]
 189                                + " len: "+length[childs[2*i]]);
 190         }
 191
 192       if (overflow == 0)
 193         return;
 194
 195       int incrBitLen = maxLength - 1;
 196       do
 197         {
 198           /* Find the first bit length which could increase: */
 199           while (bl_counts[--incrBitLen] == 0)
 200             ;
 201
 202           /* Move this node one down and remove a corresponding
 203            * amount of overflow nodes.
 204            */
 205           do
 206             {
 207               bl_counts[incrBitLen]--;
 208               bl_counts[++incrBitLen]++;
 209               overflow -= 1 << (maxLength - 1 - incrBitLen);
 210             }
 211           while (overflow > 0 && incrBitLen < maxLength - 1);
 212         }
 213       while (overflow > 0);
 214
 215       /* We may have overshot above.  Move some nodes from maxLength to
 216        * maxLength-1 in that case.
 217        */
 218       bl_counts[maxLength-1] += overflow;
 219       bl_counts[maxLength-2] -= overflow;
 220
 221       /* Now recompute all bit lengths, scanning in increasing
 222        * frequency.  It is simpler to reconstruct all lengths instead of
 223        * fixing only the wrong ones. This idea is taken from 'ar'
 224        * written by Haruhiko Okumura.
 225        *
 226        * The nodes were inserted with decreasing frequency into the childs
 227        * array.
 228        */
 229       int nodePtr = 2 * numLeafs;
 230       for (int bits = maxLength; bits != 0; bits--)
 231         {
 232           int n = bl_counts[bits-1];
 233           while (n > 0)
 234             {
 235               int childPtr = 2*childs[nodePtr++];
 236               if (childs[childPtr + 1] == -1)
 237                 {
 238                   /* We found another leaf */
 239                   length[childs[childPtr]] = (byte) bits;
 240                   n--;
 241                 }
 242             }
 243         }
 244       if (DeflaterConstants.DEBUGGING)
 245         {
 246           System.err.println("*** After overflow elimination. ***");
 247           for (int i=0; i < numLeafs; i++)
 248             System.err.println("Node "+childs[2*i]+" freq: "+freqs[childs[2*i]]
 249                                + " len: "+length[childs[2*i]]);
 250         }
 251     }
 252
 253     void buildTree()
 254     {
 255       int numSymbols = freqs.length;
 256
 257       /* heap is a priority queue, sorted by frequency, least frequent
 258        * nodes first.  The heap is a binary tree, with the property, that
 259        * the parent node is smaller than both child nodes.  This assures
 260        * that the smallest node is the first parent.
 261        *
 262        * The binary tree is encoded in an array:  0 is root node and
 263        * the nodes 2*n+1, 2*n+2 are the child nodes of node n.
 264        */
 265       int[] heap = new int[numSymbols];
 266       int heapLen = 0;
 267       int maxCode = 0;
 268       for (int n = 0; n < numSymbols; n++)
 269         {
 270           int freq = freqs[n];
 271           if (freq != 0)
 272             {
 273               /* Insert n into heap */
 274               int pos = heapLen++;
 275               int ppos;
 276               while (pos > 0 &&
 277                      freqs[heap[ppos = (pos - 1) / 2]] > freq) {
 278                 heap[pos] = heap[ppos];
 279                 pos = ppos;
 280               }
 281               heap[pos] = n;
 282               maxCode = n;
 283             }
 284         }
 285
 286       /* We could encode a single literal with 0 bits but then we
 287        * don't see the literals.  Therefore we force at least two
 288        * literals to avoid this case.  We don't care about order in
 289        * this case, both literals get a 1 bit code.
 290        */
 291       while (heapLen < 2)
 292         {
 293           int node = maxCode < 2 ? ++maxCode : 0;
 294           heap[heapLen++] = node;
 295         }
 296
 297       numCodes = Math.max(maxCode + 1, minNumCodes);
 298
 299       int numLeafs = heapLen;
 300       int[] childs = new int[4*heapLen - 2];
 301       int[] values = new int[2*heapLen - 1];
 302       int numNodes = numLeafs;
 303       for (int i = 0; i < heapLen; i++)
 304         {
 305           int node = heap[i];
 306           childs[2*i]   = node;
 307           childs[2*i+1] = -1;
 308           values[i] = freqs[node] << 8;
 309           heap[i] = i;
 310         }
 311
 312       /* Construct the Huffman tree by repeatedly combining the least two
 313        * frequent nodes.
 314        */
 315       do
 316         {
 317           int first = heap[0];
 318           int last  = heap[--heapLen];
 319
 320           /* Propagate the hole to the leafs of the heap */
 321           int ppos = 0;
 322           int path = 1;
 323           while (path < heapLen)
 324             {
 325               if (path + 1 < heapLen
 326                   && values[heap[path]] > values[heap[path+1]])
 327                 path++;
 328
 329               heap[ppos] = heap[path];
 330               ppos = path;
 331               path = path * 2 + 1;
 332             }
 333
 334           /* Now propagate the last element down along path.  Normally
 335            * it shouldn't go too deep.
 336            */
 337           int lastVal = values[last];
 338           while ((path = ppos) > 0
 339                  && values[heap[ppos = (path - 1)/2]] > lastVal)
 340             heap[path] = heap[ppos];
 341           heap[path] = last;
 342
 343
 344           int second = heap[0];
 345
 346           /* Create a new node father of first and second */
 347           last = numNodes++;
 348           childs[2*last] = first;
 349           childs[2*last+1] = second;
 350           int mindepth = Math.min(values[first] & 0xff, values[second] & 0xff);
 351           values[last] = lastVal = values[first] + values[second] - mindepth + 1;
 352
 353           /* Again, propagate the hole to the leafs */
 354           ppos = 0;
 355           path = 1;
 356           while (path < heapLen)
 357             {
 358               if (path + 1 < heapLen
 359                   && values[heap[path]] > values[heap[path+1]])
 360                 path++;
 361
 362               heap[ppos] = heap[path];
 363               ppos = path;
 364               path = ppos * 2 + 1;
 365             }
 366
 367           /* Now propagate the new element down along path */
 368           while ((path = ppos) > 0
 369                  && values[heap[ppos = (path - 1)/2]] > lastVal)
 370             heap[path] = heap[ppos];
 371           heap[path] = last;
 372         }
 373       while (heapLen > 1);
 374
 375       if (heap[0] != childs.length / 2 - 1)
 376         throw new RuntimeException("Weird!");
 377
 378       buildLength(childs);
 379     }
 380
 381     int getEncodedLength()
 382     {
 383       int len = 0;
 384       for (int i = 0; i < freqs.length; i++)
 385         len += freqs[i] * length[i];
 386       return len;
 387     }
 388
 389     void calcBLFreq(Tree blTree) {
 390       int max_count;               /* max repeat count */
 391       int min_count;               /* min repeat count */
 392       int count;                   /* repeat count of the current code */
 393       int curlen = -1;             /* length of current code */
 394
 395       int i = 0;
 396       while (i < numCodes)
 397         {
 398           count = 1;
 399           int nextlen = length[i];
 400           if (nextlen == 0)
 401             {
 402               max_count = 138;
 403               min_count = 3;
 404             }
 405           else
 406             {
 407               max_count = 6;
 408               min_count = 3;
 409               if (curlen != nextlen)
 410                 {
 411                   blTree.freqs[nextlen]++;
 412                   count = 0;
 413                 }
 414             }
 415           curlen = nextlen;
 416           i++;
 417
 418           while (i < numCodes && curlen == length[i])
 419             {
 420               i++;
 421               if (++count >= max_count)
 422                 break;
 423             }
 424
 425           if (count < min_count)
 426             blTree.freqs[curlen] += count;
 427           else if (curlen != 0)
 428             blTree.freqs[REP_3_6]++;
 429           else if (count <= 10)
 430             blTree.freqs[REP_3_10]++;
 431           else
 432             blTree.freqs[REP_11_138]++;
 433         }
 434     }
 435
 436     void writeTree(Tree blTree)
 437     {
 438       int max_count;               /* max repeat count */
 439       int min_count;               /* min repeat count */
 440       int count;                   /* repeat count of the current code */
 441       int curlen = -1;             /* length of current code */
 442
 443       int i = 0;
 444       while (i < numCodes)
 445         {
 446           count = 1;
 447           int nextlen = length[i];
 448           if (nextlen == 0)
 449             {
 450               max_count = 138;
 451               min_count = 3;
 452             }
 453           else
 454             {
 455               max_count = 6;
 456               min_count = 3;
 457               if (curlen != nextlen)
 458                 {
 459                   blTree.writeSymbol(nextlen);
 460                   count = 0;
 461                 }
 462             }
 463           curlen = nextlen;
 464           i++;
 465
 466           while (i < numCodes && curlen == length[i])
 467             {
 468               i++;
 469               if (++count >= max_count)
 470                 break;
 471             }
 472
 473           if (count < min_count)
 474             {
 475               while (count-- > 0)
 476                 blTree.writeSymbol(curlen);
 477             }
 478           else if (curlen != 0)
 479             {
 480               blTree.writeSymbol(REP_3_6);
 481               pending.writeBits(count - 3, 2);
 482             }
 483           else if (count <= 10)
 484             {
 485               blTree.writeSymbol(REP_3_10);
 486               pending.writeBits(count - 3, 3);
 487             }
 488           else
 489             {
 490               blTree.writeSymbol(REP_11_138);
 491               pending.writeBits(count - 11, 7);
 492             }
 493         }
 494     }
 495   }
 496
 497
 498
 499   DeflaterPending pending;
 500   private Tree literalTree, distTree, blTree;
 501
 502   private short d_buf[];
 503   private byte l_buf[];
 504   private int last_lit;
 505   private int extra_bits;
 506
 507   private static short staticLCodes[];
 508   private static byte  staticLLength[];
 509   private static short staticDCodes[];
 510   private static byte  staticDLength[];
 511
 512   /**
 513    * Reverse the bits of a 16 bit value.
 514    */
 515   static short bitReverse(int value) {
 516     return (short) (bit4Reverse.charAt(value & 0xf) << 12
 517                     | bit4Reverse.charAt((value >> 4) & 0xf) << 8
 518                     | bit4Reverse.charAt((value >> 8) & 0xf) << 4
 519                     | bit4Reverse.charAt(value >> 12));
 520   }
 521
 522   static {
 523     /* See RFC 1951 3.2.6 */
 524     /* Literal codes */
 525     staticLCodes = new short[LITERAL_NUM];
 526     staticLLength = new byte[LITERAL_NUM];
 527     int i = 0;
 528     while (i < 144) {
 529       staticLCodes[i] = bitReverse((0x030 + i) << 8);
 530       staticLLength[i++] = 8;
 531     }
 532     while (i < 256) {
 533       staticLCodes[i] = bitReverse((0x190 - 144 + i) << 7);
 534       staticLLength[i++] = 9;
 535     }
 536     while (i < 280) {
 537       staticLCodes[i] = bitReverse((0x000 - 256 + i) << 9);
 538       staticLLength[i++] = 7;
 539     }
 540     while (i < LITERAL_NUM) {
 541       staticLCodes[i] = bitReverse((0x0c0 - 280 + i)  << 8);
 542       staticLLength[i++] = 8;
 543     }
 544
 545     /* Distant codes */
 546     staticDCodes = new short[DIST_NUM];
 547     staticDLength = new byte[DIST_NUM];
 548     for (i = 0; i < DIST_NUM; i++) {
 549       staticDCodes[i] = bitReverse(i << 11);
 550       staticDLength[i] = 5;
 551     }
 552   }
 553
 554   public DeflaterHuffman(DeflaterPending pending)
 555   {
 556     this.pending = pending;
 557
 558     literalTree = new Tree(LITERAL_NUM, 257, 15);
 559     distTree    = new Tree(DIST_NUM, 1, 15);
 560     blTree      = new Tree(BITLEN_NUM, 4, 7);
 561
 562     d_buf = new short[BUFSIZE];
 563     l_buf = new byte [BUFSIZE];
 564   }
 565
 566   public final void reset() {
 567     last_lit = 0;
 568     extra_bits = 0;
 569     literalTree.reset();
 570     distTree.reset();
 571     blTree.reset();
 572   }
 573
 574   private int l_code(int len) {
 575     if (len == 255)
 576       return 285;
 577
 578     int code = 257;
 579     while (len >= 8)
 580       {
 581         code += 4;
 582         len >>= 1;
 583       }
 584     return code + len;
 585   }
 586
 587   private int d_code(int distance) {
 588     int code = 0;
 589     while (distance >= 4)
 590       {
 591         code += 2;
 592         distance >>= 1;
 593       }
 594     return code + distance;
 595   }
 596
 597   public void sendAllTrees(int blTreeCodes) {
 598     blTree.buildCodes();
 599     literalTree.buildCodes();
 600     distTree.buildCodes();
 601     pending.writeBits(literalTree.numCodes - 257, 5);
 602     pending.writeBits(distTree.numCodes - 1, 5);
 603     pending.writeBits(blTreeCodes - 4, 4);
 604     for (int rank = 0; rank < blTreeCodes; rank++)
 605       pending.writeBits(blTree.length[BL_ORDER[rank]], 3);
 606     literalTree.writeTree(blTree);
 607     distTree.writeTree(blTree);
 608     if (DeflaterConstants.DEBUGGING)
 609       blTree.checkEmpty();
 610   }
 611
 612   public void compressBlock() {
 613     for (int i = 0; i < last_lit; i++)
 614       {
 615         int litlen = l_buf[i] & 0xff;
 616         int dist = d_buf[i];
 617         if (dist-- != 0)
 618           {
 619             if (DeflaterConstants.DEBUGGING)
 620               System.err.print("["+(dist+1)+","+(litlen+3)+"]: ");
 621
 622             int lc = l_code(litlen);
 623             literalTree.writeSymbol(lc);
 624
 625             int bits = (lc - 261) / 4;
 626             if (bits > 0 && bits <= 5)
 627               pending.writeBits(litlen & ((1 << bits) - 1), bits);
 628
 629             int dc = d_code(dist);
 630             distTree.writeSymbol(dc);
 631
 632             bits = dc / 2 - 1;
 633             if (bits > 0)
 634               pending.writeBits(dist & ((1 << bits) - 1), bits);
 635           }
 636         else
 637           {
 638             if (DeflaterConstants.DEBUGGING)
 639               {
 640                 if (litlen > 32 && litlen < 127)
 641                   System.err.print("("+(char)litlen+"): ");
 642                 else
 643                   System.err.print("{"+litlen+"}: ");
 644               }
 645             literalTree.writeSymbol(litlen);
 646           }
 647       }
 648     if (DeflaterConstants.DEBUGGING)
 649       System.err.print("EOF: ");
 650     literalTree.writeSymbol(EOF_SYMBOL);
 651     if (DeflaterConstants.DEBUGGING)
 652       {
 653         literalTree.checkEmpty();
 654         distTree.checkEmpty();
 655       }
 656   }
 657
 658   public void flushStoredBlock(byte[] stored,
 659                                int stored_offset, int stored_len,
 660                                boolean lastBlock) {
 661     if (DeflaterConstants.DEBUGGING)
 662       System.err.println("Flushing stored block "+ stored_len);
 663     pending.writeBits((DeflaterConstants.STORED_BLOCK << 1)
 664                       + (lastBlock ? 1 : 0), 3);
 665     pending.alignToByte();
 666     pending.writeShort(stored_len);
 667     pending.writeShort(~stored_len);
 668     pending.writeBlock(stored, stored_offset, stored_len);
 669     reset();
 670   }
 671
 672   public void flushBlock(byte[] stored, int stored_offset, int stored_len,
 673                          boolean lastBlock) {
 674     literalTree.freqs[EOF_SYMBOL]++;
 675
 676     /* Build trees */
 677     literalTree.buildTree();
 678     distTree.buildTree();
 679
 680     /* Calculate bitlen frequency */
 681     literalTree.calcBLFreq(blTree);
 682     distTree.calcBLFreq(blTree);
 683
 684     /* Build bitlen tree */
 685     blTree.buildTree();
 686
 687     int blTreeCodes = 4;
 688     for (int i = 18; i > blTreeCodes; i--)
 689       {
 690         if (blTree.length[BL_ORDER[i]] > 0)
 691           blTreeCodes = i+1;
 692       }
 693     int opt_len = 14 + blTreeCodes * 3 + blTree.getEncodedLength()
 694       + literalTree.getEncodedLength() + distTree.getEncodedLength()
 695       + extra_bits;
 696
 697     int static_len = extra_bits;
 698     for (int i = 0; i < LITERAL_NUM; i++)
 699       static_len += literalTree.freqs[i] * staticLLength[i];
 700     for (int i = 0; i < DIST_NUM; i++)
 701       static_len += distTree.freqs[i] * staticDLength[i];
 702     if (opt_len >= static_len)
 703       {
 704         /* Force static trees */
 705         opt_len = static_len;
 706       }
 707
 708     if (stored_offset >= 0 && stored_len+4 < opt_len >> 3)
 709       {
 710         /* Store Block */
 711         if (DeflaterConstants.DEBUGGING)
 712           System.err.println("Storing, since " + stored_len + " < " + opt_len
 713                              + " <= " + static_len);
 714         flushStoredBlock(stored, stored_offset, stored_len, lastBlock);
 715       }
 716     else if (opt_len == static_len)
 717       {
 718         /* Encode with static tree */
 719         pending.writeBits((DeflaterConstants.STATIC_TREES << 1)
 720                           + (lastBlock ? 1 : 0), 3);
 721         literalTree.setStaticCodes(staticLCodes, staticLLength);
 722         distTree.setStaticCodes(staticDCodes, staticDLength);
 723         compressBlock();
 724         reset();
 725       }
 726     else
 727       {
 728         /* Encode with dynamic tree */
 729         pending.writeBits((DeflaterConstants.DYN_TREES << 1)
 730                           + (lastBlock ? 1 : 0), 3);
 731         sendAllTrees(blTreeCodes);
 732         compressBlock();
 733         reset();
 734       }
 735   }
 736
 737   public final boolean isFull()
 738   {
 739     return last_lit == BUFSIZE;
 740   }
 741
 742   public final boolean tallyLit(int lit)
 743   {
 744     if (DeflaterConstants.DEBUGGING)
 745       {
 746         if (lit > 32 && lit < 127)
 747           System.err.println("("+(char)lit+")");
 748         else
 749           System.err.println("{"+lit+"}");
 750       }
 751     d_buf[last_lit] = 0;
 752     l_buf[last_lit++] = (byte) lit;
 753     literalTree.freqs[lit]++;
 754     return last_lit == BUFSIZE;
 755   }
 756
 757   public final boolean tallyDist(int dist, int len)
 758   {
 759     if (DeflaterConstants.DEBUGGING)
 760       System.err.println("["+dist+","+len+"]");
 761
 762     d_buf[last_lit] = (short) dist;
 763     l_buf[last_lit++] = (byte) (len - 3);
 764
 765     int lc = l_code(len-3);
 766     literalTree.freqs[lc]++;
 767     if (lc >= 265 && lc < 285)
 768       extra_bits += (lc - 261) / 4;
 769
 770     int dc = d_code(dist-1);
 771     distTree.freqs[dc]++;
 772     if (dc >= 4)
 773       extra_bits += dc / 2 - 1;
 774     return last_lit == BUFSIZE;
 775   }
 776 }