Logo Search packages:      
Sourcecode: hf version File versions

mkgtortables.c

/*****************************************************************************/

/*
 *      mkgtortables.c  --  generate GTOR huffman and golay tables.
 *
 *      Copyright (C) 1997  Thomas Sailer (sailer@ife.ee.ethz.ch)
 *        Swiss Federal Institute of Technology (ETH), Electronics Lab
 *
 *      This program is free software; you can redistribute it and/or modify
 *      it under the terms of the GNU General Public License as published by
 *      the Free Software Foundation; either version 2 of the License, or
 *      (at your option) any later version.
 *
 *      This program is distributed in the hope that it will be useful,
 *      but WITHOUT ANY WARRANTY; without even the implied warranty of
 *      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *      GNU General Public License for more details.
 *
 *      You should have received a copy of the GNU General Public License
 *      along with this program; if not, write to the Free Software
 *      Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 *
 */

/*****************************************************************************/
      
#ifdef HAVE_CONFIG_H
#include "config.h"
#endif

#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>

/* --------------------------------------------------------------------- */

static const char *huff[128] = {
      "1111000011111000",      /* 0x00 */
      "1111000011111001",
      "1111000011111010",
      "1111000011111011",
      "1111000011111100",
      "1111000011111101",
      "1111000011111110",
      "1111000011111111",
      "1111000011110010",      /* 0x08 */
      "1111000011110011",
      "001101",
      "1111000011110100",
      "1111000011110101",
      "001100",
      "1111000011110110",
      "1111000011110111",
      "1111001110000000",      /* 0x10 */
      "1111001110000001",
      "1111001110000010",
      "1111001110000011",
      "1111001110000100",
      "1111001110000101",
      "1111001110000110",
      "1111001110000111",
      "1111001110001000",      /* 0x18 */
      "1111001110001001",
      "1111001110001010",
      "1111001110001011",
      "1111001110001100",
      "1111001110001101",
      "1111001110001110",
      "1111001110001111",
      "10",                    /* 0x20 */
      "11110011101",
      "110001101100",
      "0010100011011",
      "0001010111001",
      "110001101101",
      "111100111001",
      "110001101110",
      "110011011",             /* 0x28 */
      "110011100",
      "001010001100",
      "111100111110",
      "1100101",
      "00010101111",
      "1100100",
      "11110011110",
      "11000111",             /* 0x30 */
      "001010000",
      "0001011010",
      "0001011011",
      "0001011100",
      "0001010101",
      "0001011101",
      "0001011110",
      "0001011111",           /* 0x38 */
      "0001010010",
      "00101000111",
      "11110000110100",
      "0001010111010",
      "1111000010",
      "111100111111",
      "1100110101",
      "0001010111000",        /* 0x40 */
      "00101001",
      "11001111",
      "11110001",
      "11110100",
      "11000000",
      "11001100",
      "00010100111",
      "0010100010",           /* 0x48 */
      "11110010",
      "1100000110",
      "1100110100",
      "110011101",
      "111101010",
      "111100000",
      "000101000",
      "000101100",            /* 0x50 */
      "00101000110101",
      "110000010",
      "1111011",
      "0001101",
      "1100000111",
      "1100011000",
      "0001010100",
      "0001010111011",        /* 0x58 */
      "1111010111",
      "1100011001",
      "00101000110100",
      "11110000110101",
      "11110000110111",
      "11000110111111",
      "111100001100",
      "11110000111000",       /* 0x60 */
      "01000",
      "0000110",
      "010011",
      "00111",
      "011",
      "0000111",
      "000111",
      "000100",               /* 0x68 */
      "1101",
      "00010100110",
      "0010101",
      "000010",
      "001011",
      "0101",
      "010010",
      "11000010",             /* 0x70 */
      "1111010110",
      "1110",
      "00100",
      "00000",
      "11111",
      "11000011",
      "0001100",
      "1100011010",           /* 0x78 */
      "0001010110",
      "1100010",
      "11000110111110",
      "11110000110110",
      "11000110111101",
      "11000110111100",
      "1111000011110001"
};

struct hufftab {
      unsigned int bits;
      unsigned int len;
};

/* --------------------------------------------------------------------- */

static void strtohufftab(struct hufftab *h, const char *str, unsigned int n, unsigned int nbits)
{
      h->bits = h->len = 0;
      while (*str) {
            switch (*str) {
            case '1':
                  h->bits |= 1 << (h->len);
                  /* fall through */
            case '0':
                  h->len++;
                  if (h->len >= 20) {
                        fprintf(stderr, "huffman string \"%s\" too long\n", str);
                        exit(1);
                  }
                  break;

            default:
                  fprintf(stderr, "huffman string \"%s\" invalid\n", str);
                  exit(1);
            }
            str++;
      }
      for (; nbits > 0; nbits--) {
            if (n & (1 << (nbits-1)))
                  h->bits |= 1 << (h->len);
            h->len++;
            if (h->len >= 20) {
                  fprintf(stderr, "huffman string \"%s\" too long\n", str);
                  exit(1);
            }
      }
}

/* --------------------------------------------------------------------- */

static void gen_huff(void)
{
      struct hufftab hufftab[290];
      int i, j;
#ifdef PARANOID
      int k;
#endif

      for (i = 0; i < 128; i++)
            strtohufftab(hufftab+i, huff[i], 0, 0);
      for (i = 128; i < 256; i++)
            strtohufftab(hufftab+i, "111100110", (i & 127), 7);  /* upper ascii */
      for (i = 256; i < 288; i++)
            strtohufftab(hufftab+i, "11110000111001", (i & 31), 5);  /* rle 0-31 */
      strtohufftab(hufftab+288, "1111000011110000", 0, 0);  /* idle */
      strtohufftab(hufftab+289, "1111000011101", 0, 0);  /* unused */

#ifdef PARANOID
      for (i = 0; i < (1<<19); i++) {
            for (k = j = 0; j < 290; j++)
                  if ((i & ((1 << hufftab[j].len)-1)) == hufftab[j].bits)
                        k++;
            if (k != 1)
                  fprintf(stderr, "Warning: bit pattern 0x%x  %d entries matching\n", i, k);
      }
#endif

      printf("static const struct gtor_huffman_table huff_table_1[290] = {\n\t");
      for (i = 0; i < 290; i++) {
            printf("{ 0x%05x, %2d }", hufftab[i].bits, hufftab[i].len);
            if (i >= 289)
                  break;
            printf((i & 3) != 3 ? ", " : ",\n\t");
      }
      printf("\n};\n\nstatic const struct gtor_huffman_table huff_table_2[290] = {\n\t");
      for (i = 0; i < 290; i++) {
            j = i;
            if (i < 255 && isupper(i))
                  j += 32;
            else if (i < 255 && islower(i))
                  j -= 32;
            printf("{ 0x%05x, %2d }", hufftab[j].bits, hufftab[j].len);
            if (i >= 289)
                  break;
            printf((i & 3) != 3 ? ", " : ",\n\t");
      }
      printf("\n};\n\n");
}

/* --------------------------------------------------------------------- */

static unsigned int golay_gen_matrix[12] = {
      0xdc5, 0xb8b, 0x717, 0xe2d, 0xc5b, 0x8b7,
      0x16f, 0x2dd, 0x5b9, 0xb71, 0x6e3, 0xffe
};

extern __inline__ unsigned int golay_encode(unsigned int w)
{
      unsigned int ret = 0;
      unsigned int i;
      unsigned int mask;

      for (mask = 0x800, i = 0; i < 12; i++, mask >>= 1)
            if (w & mask)
                  ret ^= golay_gen_matrix[i];
      return ret;
}

extern __inline__ unsigned int golay_syndrome(unsigned int inp)
{
      unsigned int syn;

      /* first calculate the syndrome vector (we use the fact that golay_encode(golay_encode(p)) == p) */
      syn = golay_encode(inp & 0xfff) ^ (inp >> 12);
      syn &= 0xfff;
      return syn;
}

/* --------------------------------------------------------------------- */

static void gen_golay(void)
{
      unsigned short golay_encode_tab[0x1000];
      unsigned short golay_error_tab[0x1000];
      unsigned int corr[5];
      unsigned int u, a, b, c;

      for (u = 0; u < 0x1000; u++) {
            golay_encode_tab[u] = golay_encode(u);
            golay_error_tab[u] = 0xf000;
      }
      golay_error_tab[0] = 0x0000;
      for (a = 0; a < 24; a++) {
            u = golay_syndrome(1 << a);
            if (golay_error_tab[u] < 0xf000)
                  fprintf(stderr, "golay: syndrome location 0x%03x already used, value 0x%04x!!\n",
                        u, golay_error_tab[u]);
            golay_error_tab[u] = 0x1000 | ((1 << a) & 0xfff);
            for (b = a+1; b < 24; b++) {
                  u = golay_syndrome((1 << a) | (1 << b));
                  if (golay_error_tab[u] < 0xf000)
                        fprintf(stderr, "golay: syndrome location 0x%03x already used, value 0x%04x!!\n",
                              u, golay_error_tab[u]);
                  golay_error_tab[u] = 0x2000 | (((1 << a) | (1 << b)) & 0xfff);
                  for (c = b+1; c < 24; c++) {
                        u = golay_syndrome((1 << a) | (1 << b) | (1 << c));
                        if (golay_error_tab[u] < 0xf000)
                              fprintf(stderr, "golay: syndrome location 0x%03x already used, value 0x%04x!!\n",
                                    u, golay_error_tab[u]);
                        golay_error_tab[u] = 0x3000 | (((1 << a) | (1 << b) | (1 << c)) & 0xfff);
                  }
            }
      }
      printf("unsigned short golay_encode_tab[0x1000] = {\n\t");
      for (u = 0; u < 0x1000; u++) {
            printf("0x%03x", golay_encode_tab[u]);
            if (u >= 0xfff)
                  break;
            printf((u & 7) == 7 ? ",\n\t" : ", ");
      }
      printf("\n};\n\nunsigned short golay_error_tab[0x1000] = {\n\t");
      corr[0] = corr[1] = corr[2] = corr[3] = corr[4] = 0;
      for (u = 0; u < 0x1000; u++) {
            corr[(golay_error_tab[u] >= 0x4000) ? 4 : ((golay_error_tab[u] >> 12) & 0xf)]++;
            printf("0x%04x", golay_error_tab[u]);
            if (u >= 0xfff)
                  break;
            printf((u & 7) == 7 ? ",\n\t" : ", ");
      }
      printf("\n};\n\n");
      fprintf(stderr, "golay: correcting errors: %u %u %u %u %u\n", corr[0], corr[1], corr[2], corr[3], corr[4]);
}

/* --------------------------------------------------------------------- */

int main(int argc, char *argv[])
{
      printf("/*\n * automatically generated by %s, DO NOT EDIT\n */\n\n",
             argv[0]);
      gen_huff();
      gen_golay();
      exit(0);
}


Generated by  Doxygen 1.6.0   Back to index