Logo Search packages:      
Sourcecode: vic version File versions

mkhuff.cpp

/*
 * Copyright (c) 1993-1994 Regents of the University of California.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. All advertising materials mentioning features or use of this software
 *    must display the following acknowledgement:
 *    This product includes software developed by the Network Research
 *    Group at Lawrence Berkeley Laboratory.
 * 4. Neither the name of the University nor of the Laboratory may be used
 *    to endorse or promote products derived from this software without
 *    specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

#ifndef lint
static char rcsid[] =
    "@(#) $Header: /cs/research/mice/starship/src/local/CVS_repository/vic/render/mkhuff/mkhuff.cpp,v 1.1 1999/09/09 12:38:25 piers Exp $ (LBL)";
#endif

#include <stdlib.h>
//#include <unistd.h>
#include <stdio.h>
#include <string.h>
#include <sys/types.h>
#ifdef WIN32
#include <winsock.h>
extern "C" {
int getopt(int, char * const *, const char *);
}
#endif
#include <getopt.h>
#define HUFFSTRINGS
#include "p64-huff.h"

/*
 * Convert a binary string to an integer.
 */
int
btoi(const char* s)
{
      int v = 0;
      while (*s) {
            v <<= 1;
            v |= *s++ - '0';
      }
      return (v);
}

struct hufftab {
      int maxlen;
      short *prefix;
};

/*
 * Build a direct map huffman table from the array of codes given.
 * We build a prefix table such that we can directly index
 * table with the k-bit number at the head of the bit stream, where
 * k is the max-length code in the table.  The table tells us
 * the value and the actual length of the code we have.
 * We need the length so we can tear that many bits off
 * the input stream.  The length and value are packed as
 * two 16-bit quantities in a 32-bit word.  The value is stored
 * in the upper 16-bits, so when we right-shift it over,
 * it is automatically sign-extended.
 */
void
huffbuild(hufftab& ht, const huffcode* codes)
{
      int i = 0;
      int maxlen = 0;
      for (; codes[i].str != 0; ++i) {
            int v = strlen(codes[i].str);
            if (v > maxlen)
                  maxlen = v;
      }
      int size = 1 << maxlen;
      if (size > 65536)
            abort();
            
      /*
       * Build the direct-map lookup table.
       */
      ht.prefix = new short[size];
      ht.maxlen = maxlen;

      /*
       * Initialize states to illegal, and arrange
       * for max bits to be stripped off the input.
       */
      for (i = 0; i < size; ++i)
            ht.prefix[i] = (SYM_ILLEGAL << 5) | maxlen;

      for (i = 0; codes[i].str != 0; ++i) {
            int codelen = strlen(codes[i].str);
            int nbit = maxlen - codelen;
            int code = btoi(codes[i].str) << nbit;
            int map = (codes[i].val << 5) | codelen;
            /*
             * The low nbit bits are don't cares.
             * Spin through all possible combos.
             */
            for (int n = 1 << nbit; --n >= 0; ) {
                  if ((code | n) >= size)
                        abort();
                  ht.prefix[code | n] = map;
            }
      }
}

int
skipcode(int bs, int* code, int* len, int* symbol, int n)
{
      int nbit = 0;
      for (;;) {
            /*
             * Find the matching huffman code that is a prefix
             * of bs at offset off.  There is either zero
             * or one such codes, since the huffman strings have
             * unique prefixes.  The zero case means the given
             * bit string is impossible.
             */
            int pbit = nbit;
            for (int k = 0; k < n; ++k) {
                  if (len[k] < 16 - nbit) {
                        int v = bs >> (16 - nbit - len[k]);
                        v &= (1 << len[k]) - 1;
                        if (v != code[k])
                              continue;
                        nbit += len[k];
                        if (symbol[k] == SYM_ESCAPE)
                              /*
                               * This must end the prefix
                               * since it necessarily takes
                               * up more than 16 bits.
                               */
                              return (nbit + 14);
                        else if (symbol[k] == SYM_EOB)
                              return (0x80 | nbit);
                  }
            }
            if (nbit == 0)
                  /*
                   * Didn't find any matches.
                   */
                  return (0x40);
            /*
             * If we didn't find a new match,
             * return the current result.
             */
            if (nbit == pbit)
                  return (nbit);
      }
}
            
/*
 * Build a skip table.  The idea is to have a fast way
 * of finding the boundaries in the bit stream for a block
 * (i.e., entropy/run-length encoded set of 8x8 DCT coefficients).
 * The bit string can then be used to hash into a cache of
 * recently computed inverse DCTs.
 *
 * The table is indexed 16 bits at a time.  Each 8-bit entry
 * tells how many bits are taken up by the longest string of
 * whole codewords in the index.  The length might be greater
 * than 16 if there is an ESCAPE character (which is great
 * because we can just skip over the following 14-bits).
 * Bit 7 is set if the codes are terminated by EOB,; bit 6
 * is set if the string is impossible; the length is in bits 0-5.
 *
 * Note that this table works only for the AC coeffcients, because
 * the DC decoding is complicated by macroblock type context.
 * That's okay because we want the hash table to contain inverse
 * DCTs with 0 DC bias because adding in the DC component during
 * the block copy incurs no additional cost (memory is the bottleneck),
 * and using DC=0 significantly increases the probability of a
 * cache hit.
 */
void
skipbuild(huffcode* hc, u_char* skiptab)
{
      int len[1024];
      int code[1024];
      int symbol[1024];

      int n = 0;
      for (; hc->str != 0; ++hc) {
            len[n] = strlen(hc->str);
            code[n] = btoi(hc->str);
            symbol[n] = hc->val;
            ++n;
      }
      for (int bs = 0; bs < 65536; ++bs)
            skiptab[bs] = skipcode(bs, code, len, symbol, n);
}

struct huff {
      char* name;
      huffcode* codes;
};
struct huff hc[] = {
      { "htd_mtype", hc_mtype },
      { "htd_mba", hc_mba },
      { "htd_cbp", hc_cbp },
      { "htd_dvm", hc_dvm },
      { "htd_tcoeff", hc_tcoeff },
      { 0, 0 }
};

huffcode*
mba_lookup(int mba)
{
      for (huffcode* hc = hc_mba; hc->str != 0; ++hc)
            if (hc->val == mba)
                  return (hc);
      abort();
      return (0);  /*NOTREACHED*/
}

void
gen_hte_mba()
{
      printf("struct huffent hte_mba[33] = {\n");
      for (int mba = 0; mba < 33; ++mba) {
            huffcode* hc = mba_lookup(mba + 1);
            printf("\t{ %d, %d },\n", btoi(hc->str), strlen(hc->str));
      }
      printf("};\n");
}

huffcode*
tc_lookup(int run, int level)
{
      int v = TC_RUN(run) | TC_LEVEL(level);
      if (v <= 0)
            return (0);
      for (huffcode* hc = hc_tcoeff; hc->str != 0; ++hc)
            if (hc->val == v)
                  return (hc);
      return (0);
}

void
gen_hte_tc()
{
      /* 5 bits of (signed) level, 6 bits of (unsigned) run */
      printf("struct huffent hte_tc[1 << 11] = {\n");
      for (int level = -16; level <= 15; ++level) {
            for (int run = 0; run < 64; ++run) {
                  huffcode* hc = tc_lookup(run, (level + 16) & 0x1f);
                  if (run < 32 &&
                      (hc = tc_lookup(run, (level + 16) & 0x1f)) != 0)
                        printf("\t{ %d, %d },\n",
                               btoi(hc->str), strlen(hc->str));
                  else
                        printf("\t{ 0, 0 },\n");

            }
      }
      printf("};\n");
}

void
usage()
{
      printf("usage: mkhuff [-es]\n");
      exit(1);
}

int
main(int argc, char **argv)
{
      int sflag = 0;
      int eflag = 0;

#ifdef notyet
      extern char *optarg;
      extern int optind, opterr;
#endif

      int op;
      while ((op = getopt(argc, argv, "es")) != -1) {
            switch (op) {
            case 's':
                  ++sflag;
                  break;
            case 'e':
                  ++eflag;
                  break;
            default:
                  usage();
                  break;
            }
      }
      printf("#include \"p64-huff.h\"\n");
      huff* p = hc;
      while (p->name) {
            hufftab ht;
            huffbuild(ht, p->codes);
            printf("const int %s_width = %d;\n", p->name, ht.maxlen);
            printf("const short %s[] = {", p->name);
            int n = 1 << ht.maxlen;
            for (int i = 0; i < n; ++i)
                  printf("(short)%s0x%04x,", (i & 7) ? " " : "\n\t",
                         ht.prefix[i] & 0xffff);
            printf("\n};\n");
            ++p;
      }
      if (eflag) {
            gen_hte_mba();
            gen_hte_tc();
      }
      if (sflag) {
            u_char skiptab[65536];
            skipbuild(hc_tcoeff, skiptab);
            printf("const unsigned char skiptab[] = {");
            for (int i = 0; i < 65536; ++i)
                  printf("%s0x%02x,", (i & 7) ? " " : "\n\t",
                         skiptab[i]);
            printf("\n};\n");
      }
      
      return (0);
}

Generated by  Doxygen 1.6.0   Back to index