tests/j4cbo.c

   1 //#test return 151
   2
   3 /* example tree from http://en.wikipedia.org/wiki/Huffman_coding */
   4
   5 int getbyte(int byte)
   6 {
   7         if (byte == 0) return 106;
   8         if (byte == 1) return 139;
   9         if (byte == 2) return 120;
  10         if (byte == 3) return 183;
  11         if (byte == 4) return 69;
  12         if (byte == 5) return 197;
  13         if (byte == 6) return 147;
  14         if (byte == 7) return 207;
  15         if (byte == 8) return 35;
  16         if (byte == 9) return 155;
  17         if (byte == 10) return 122;
  18         if (byte == 11) return 244;
  19         if (byte == 12) return 125;
  20         if (byte == 13) return 215;
  21         if (byte == 14) return 69;
  22         if (byte == 15) return 219;
  23         if (byte == 16) return 2;
  24         if (byte == 17) return 224;
  25         puts("FAIL [abort]: request for byte #");
  26         puthex(byte);
  27         while(1);
  28         return 0;
  29 }
  30
  31 int getbit(int bp)
  32 {
  33         int byte;
  34         byte = getbyte(bp/8);
  35         return (byte >> (7 - (bp % 8))) & 1;
  36 }
  37
  38 int h(int bitpos)
  39 {
  40         if (getbit(bitpos))
  41                 return h1(bitpos+1);
  42         else
  43                 return h0(bitpos+1);
  44 }
  45
  46 int h0(int bitpos)
  47 {
  48         if (getbit(bitpos))
  49                 return h01(bitpos+1);
  50         else
  51                 return h00(bitpos+1);
  52 }
  53
  54 int h00(int bitpos)
  55 {
  56         if (getbit(bitpos))
  57                 return h001(bitpos+1);
  58         else
  59                 return 69+h(bitpos+1);
  60 }
  61
  62 int h001(int bitpos)
  63 {
  64         if (getbit(bitpos))
  65                 return h0011(bitpos+1);
  66         else
  67                 return 78+h(bitpos+1);
  68 }
  69
  70 int h0011(int bitpos)
  71 {
  72         if (getbit(bitpos))
  73                 return 79+h(bitpos+1);
  74         else
  75                 return 85+h(bitpos+1);
  76 }
  77
  78 int h01(int bitpos)
  79 {
  80         if (getbit(bitpos))
  81                 return h011(bitpos+1);
  82         else
  83                 return 65+h(bitpos+1);
  84 }
  85
  86 int h011(int bitpos)
  87 {
  88         if (getbit(bitpos))
  89                 return 77+h(bitpos+1);
  90         else
  91                 return 84+h(bitpos+1);
  92 }
  93
  94 int h1(bitpos)
  95 {
  96         if (getbit(bitpos))
  97                 return h11(bitpos+1);
  98         else
  99                 return h10(bitpos+1);
 100 }
 101
 102 int h10(bitpos)
 103 {
 104         if (getbit(bitpos))
 105                 return h101(bitpos+1);
 106         else
 107                 return h100(bitpos+1);
 108 }
 109
 110 int h100(bitpos)
 111 {
 112         if (getbit(bitpos))
 113                 return h1001(bitpos+1);
 114         else
 115                 return 73+h(bitpos+1);
 116 }
 117
 118 int h1001(bitpos)
 119 {
 120         if (getbit(bitpos))
 121                 return 80+h(bitpos+1);
 122         else
 123                 return 88+h(bitpos+1);
 124 }
 125
 126 int h101(bitpos)
 127 {
 128         if (getbit(bitpos))
 129                 return h1011(bitpos+1);
 130         else
 131                 return 72+h(bitpos+1);
 132 }
 133
 134 int h1011(bitpos)
 135 {
 136         if (getbit(bitpos))
 137                 return -2169;
 138         else
 139                 return 83+h(bitpos+1);
 140 }
 141
 142 int h11(bitpos)
 143 {
 144         if (getbit(bitpos))
 145                 return 32+h(bitpos+1);
 146         else
 147                 return h110(bitpos+1);
 148 }
 149
 150 int h110(bitpos)
 151 {
 152         if (getbit(bitpos))
 153                 return 70+h(bitpos+1);
 154         else
 155                 return h1100(bitpos+1);
 156 }
 157
 158 int h1100(bitpos)
 159 {
 160         if (getbit(bitpos))
 161                 return 76+h(bitpos+1);
 162         else
 163                 return 82+h(bitpos+1);
 164 }
 165
 166 void j4cbo()
 167 {
 168         int x;
 169         if ((x = h(0)) != 151) {
 170                 puthex(x);
 171                 puts(" -> FAIL\n");
 172         } else
 173                 puts("PASS\n");
 174 }