/*

 * Copyright 2016 Google Inc.

 *

 * Licensed 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.

 */

// Utility function for building a Huffman lookup table for the jpeg decoder.

#ifndef GUETZLI_JPEG_HUFFMAN_DECODE_H_

#define GUETZLI_JPEG_HUFFMAN_DECODE_H_

#include <inttypes.h>

namespace guetzli {

static const int kJpegHuffmanRootTableBits = 8;

// Maximum huffman lookup table size.

// According to zlib/examples/enough.c, 758 entries are always enough for

// an alphabet of 257 symbols (256 + 1 special symbol for the all 1s code) and

// max bit length 16 if the root table has 8 bits.

static const int kJpegHuffmanLutSize = 758;

struct HuffmanTableEntry {

  // Initialize the value to an invalid symbol so that we can recognize it

  // when reading the bit stream using a Huffman code with space > 0.

  HuffmanTableEntry() : bits(0), value(0xffff) {}

  uint8_t bits;     // number of bits used for this symbol

  uint16_t value;   // symbol value or table offset

};

// Builds jpeg-style Huffman lookup table from the given symbols.

// The symbols are in order of increasing bit lengths. The number of symbols

// with bit length n is given in counts[n] for each n >= 1.

// Returns the size of the lookup table.

int BuildJpegHuffmanTable(const int* counts, const int* symbols,

                          HuffmanTableEntry* lut);

}  // namespace guetzli

#endif  // GUETZLI_JPEG_HUFFMAN_DECODE_H_