scripts/LOMHash.c

   1 #include <stdio.h>
   2 typedef unsigned short UINT16;
   3 typedef unsigned char BYTE;
   4 static UINT16 HuffCodeLOM[] = { 0x0001, 0x0000, 0x0002, 0x0009, 0x0006, 0x0005, 0x000d, 0x000b,
   5                                     0x0003, 0x001b, 0x0007, 0x0017, 0x0037, 0x000f, 0x004f, 0x006f,
   6                                     0x002f, 0x00ef, 0x001f, 0x005f, 0x015f, 0x009f, 0x00df, 0x01df,
   7                                     0x003f, 0x013f, 0x00bf, 0x01bf, 0x007f, 0x017f, 0x00ff, 0x01ff };
   8
   9 UINT16 HashTable[32] = { [0 ... 31] = 0xffff };
  10
  11 BYTE tab[4] = { 0, 4, 10, 19 };
  12
  13 UINT16 hash(UINT16 key)
  14 {
  15         return ((key & 0x1f) ^ (key >> 5) ^ (key >> 9));
  16 }
  17
  18 BYTE minihash(UINT16 key)
  19 {
  20         BYTE h;
  21         h = (key >> 4) & 0xf;
  22         return ((h ^ (h >> 2) ^ (h >> 3)) & 0x3);
  23 }
  24
  25 void buildhashtable(void)
  26 {
  27         int i, j;
  28         UINT16 h;
  29
  30         for (i = 0; i < 32; i++)
  31         {
  32                 h = hash(HuffCodeLOM[i]);
  33
  34                 if (HashTable[h] != 0xffff)
  35                 {
  36                         HashTable[h] ^= (HuffCodeLOM[i] & 0xfe0) ^ 0xfe0;
  37                         HashTable[tab[minihash(HuffCodeLOM[i])]] = i;
  38                 }
  39                 else
  40                 {
  41                         HashTable[h] = i;
  42                         HashTable[h] ^= 0xfe0;
  43                 }
  44
  45                 printf("at %d %" PRIu16 "=0x%" PRIx16 "\n", i, h, HashTable[h]);
  46         }
  47 }
  48
  49 BYTE getvalue(UINT16 huff)
  50 {
  51         UINT16 h = HashTable[hash(huff)];
  52
  53         if ((h ^ huff) >> 5)
  54         {
  55                 return h & 0x1f;
  56         }
  57         else
  58                 return HashTable[tab[minihash(huff)]];
  59 }
  60
  61 main()
  62 {
  63         int i;
  64         buildhashtable();
  65         printf("static UINT16 HuffIndexLOM[32] = {\n");
  66
  67         for (i = 0; i < 32; i++)
  68         {
  69                 if (i == 31)
  70                         printf("0x%" PRIx16 " };\n", HashTable[i]);
  71                 else
  72                         printf("0x%" PRIx16 ", ", HashTable[i]);
  73         }
  74
  75         for (i = 0; i < 32; i++)
  76                 if (i != getvalue(HuffCodeLOM[i]))
  77                         printf("Fail :( at %d : 0x%04" PRIx16 " got %" PRIu8 "\n", i, HuffCodeLOM[i],
  78                                getvalue(HuffCodeLOM[i]));
  79
  80         return 0;
  81 }