src/main/java/org/apache/pdfbox/jbig2/decoder/huffman/HuffmanTable.java

/**
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package org.apache.pdfbox.jbig2.decoder.huffman;

import java.io.IOException;
import java.util.List;

import javax.imageio.stream.ImageInputStream;

import org.apache.pdfbox.jbig2.JBIG2ImageReader;

/**
 * This abstract class is the base class for all types of huffman tables.
 */
public abstract class HuffmanTable {

  /**
   * This static class represents a code for use in huffman tables.
   */
  public static class Code {
    final int prefixLength;
    final int rangeLength;
    final int rangeLow;
    final boolean isLowerRange;
    int code = -1;

    public Code(int prefixLength, int rangeLength, int rangeLow, boolean isLowerRange) {
      this.prefixLength = prefixLength;
      this.rangeLength = rangeLength;
      this.rangeLow = rangeLow;
      this.isLowerRange = isLowerRange;
    }

    @Override
    public String toString() {
      return (code != -1 ? ValueNode.bitPattern(code, prefixLength) : "?") + "/" + prefixLength + "/" + rangeLength
          + "/" + rangeLow;
    }
  }

  private InternalNode rootNode = new InternalNode();

  public void initTree(List<Code> codeTable) {
    preprocessCodes(codeTable);

    for (Code c : codeTable) {
      rootNode.append(c);
    }
  }

  public long decode(ImageInputStream iis) throws IOException {
    return rootNode.decode(iis);
  }

  @Override
  public String toString() {
    return rootNode + "\n";
  }

  public static String codeTableToString(List<Code> codeTable) {
    StringBuilder sb = new StringBuilder();

    for (Code c : codeTable) {
      sb.append(c.toString()).append("\n");
    }

    return sb.toString();
  }

  private void preprocessCodes(List<Code> codeTable) {
    /* Annex B.3 1) - build the histogram */
    int maxPrefixLength = 0;

    for (Code c : codeTable) {
      maxPrefixLength = Math.max(maxPrefixLength, c.prefixLength);
    }

    int lenCount[] = new int[maxPrefixLength + 1];
    for (Code c : codeTable) {
      lenCount[c.prefixLength]++;
    }

    int curCode;
    int firstCode[] = new int[lenCount.length + 1];
    lenCount[0] = 0;

    /* Annex B.3 3) */
    for (int curLen = 1; curLen <= lenCount.length; curLen++) {
      firstCode[curLen] = (firstCode[curLen - 1] + (lenCount[curLen - 1]) << 1);
      curCode = firstCode[curLen];
      for (Code code : codeTable) {
        if (code.prefixLength == curLen) {
          code.code = curCode;
          curCode++;
        }
      }
    }

    if (JBIG2ImageReader.DEBUG)
      System.out.println(codeTableToString(codeTable));
  }
}