sdcc/support/regression/tests/bug3521024.c

   1 #include <testfwk.h>
   2
   3 struct cvu_huffman_node
   4 {
   5         unsigned char left;   /* Position of left node in tree or character. */
   6         unsigned char right;  /* Position of right node in tree or character. */
   7 };
   8
   9 struct cvu_huffman_state
  10 {
  11         unsigned char (*input)(void);
  12         const struct cvu_huffman_node *nodes;   /* Array of nodes */
  13         unsigned char root;     /* Position of root node among nodes */
  14         unsigned char ls, bs, rs;
  15         unsigned char bit;      /* Position of currently processed bit */
  16         unsigned char buffer;   /* Currently processed input byte */
  17         unsigned char current;  /* Currently processed node */
  18 };
  19
  20 #ifndef __SDCC_pdk14 // Lack of memory
  21 const unsigned char HUFFMAN_ROOT = 124;
  22 const unsigned char HUFFMAN_LS = 125, HUFFMAN_BS = 127, HUFFMAN_RS = 253;
  23 const struct cvu_huffman_node huffman_tree[255] = {
  24
  25 /* Node 0 */ {128, 129},
  26 /* Node 1 */ {130, 131},
  27 /* Node 2 */ {132, 133},
  28 /* Node 3 */ {134, 135},
  29 /* Node 4 */ {136, 137},
  30 /* Node 5 */ {138, 139},
  31 /* Node 6 */ {140, 141},
  32 /* Node 7 */ {142, 143},
  33 /* Node 8 */ {144, 145},
  34 /* Node 9 */ {146, 147},
  35 /* Node 10 */ {148, 149},
  36 /* Node 11 */ {150, 151},
  37 /* Node 12 */ {152, 153},
  38 /* Node 13 */ {154, 155},
  39 /* Node 14 */ {156, 157},
  40 /* Node 15 */ {158, 159},
  41 /* Node 16 */ {160, 161},
  42 /* Node 17 */ {162, 163},
  43 /* Node 18 */ {164, 165},
  44 /* Node 19 */ {166, 167},
  45 /* Node 20 */ {168, 169},
  46 /* Node 21 */ {170, 171},
  47 /* Node 22 */ {172, 173},
  48 /* Node 23 */ {174, 175},
  49 /* Node 24 */ {176, 177},
  50 /* Node 25 */ {178, 179},
  51 /* Node 26 */ {180, 181},
  52 /* Node 27 */ {182, 183},
  53 /* Node 28 */ {184, 185},
  54 /* Node 29 */ {186, 187},
  55 /* Node 30 */ {188, 189},
  56 /* Node 31 */ {190, 191},
  57 /* Node 32 */ {192, 193},
  58 /* Node 33 */ {194, 195},
  59 /* Node 34 */ {196, 197},
  60 /* Node 35 */ {198, 199},
  61 /* Node 36 */ {200, 201},
  62 /* Node 37 */ {202, 203},
  63 /* Node 38 */ {204, 205},
  64 /* Node 39 */ {206, 207},
  65 /* Node 40 */ {208, 209},
  66 /* Node 41 */ {210, 211},
  67 /* Node 42 */ {212, 213},
  68 /* Node 43 */ {214, 215},
  69 /* Node 44 */ {216, 217},
  70 /* Node 45 */ {218, 219},
  71 /* Node 46 */ {220, 221},
  72 /* Node 47 */ {222, 223},
  73 /* Node 48 */ {224, 225},
  74 /* Node 49 */ {226, 227},
  75 /* Node 50 */ {228, 229},
  76 /* Node 51 */ {230, 231},
  77 /* Node 52 */ {232, 233},
  78 /* Node 53 */ {234, 235},
  79 /* Node 54 */ {236, 237},
  80 /* Node 55 */ {238, 239},
  81 /* Node 56 */ {240, 241},
  82 /* Node 57 */ {242, 243},
  83 /* Node 58 */ {244, 245},
  84 /* Node 59 */ {246, 247},
  85 /* Node 60 */ {248, 249},
  86 /* Node 61 */ {125, 0},
  87 /* Node 62 */ {1, 2},
  88 /* Node 63 */ {3, 4},
  89 /* Node 64 */ {5, 6},
  90 /* Node 65 */ {7, 8},
  91 /* Node 66 */ {9, 10},
  92 /* Node 67 */ {11, 12},
  93 /* Node 68 */ {13, 14},
  94 /* Node 69 */ {15, 16},
  95 /* Node 70 */ {17, 18},
  96 /* Node 71 */ {19, 20},
  97 /* Node 72 */ {21, 22},
  98 /* Node 73 */ {23, 24},
  99 /* Node 74 */ {25, 26},
 100 /* Node 75 */ {27, 28},
 101 /* Node 76 */ {29, 30},
 102 /* Node 77 */ {31, 32},
 103 /* Node 78 */ {33, 34},
 104 /* Node 79 */ {35, 36},
 105 /* Node 80 */ {37, 38},
 106 /* Node 81 */ {39, 40},
 107 /* Node 82 */ {41, 42},
 108 /* Node 83 */ {43, 44},
 109 /* Node 84 */ {45, 46},
 110 /* Node 85 */ {47, 48},
 111 /* Node 86 */ {49, 50},
 112 /* Node 87 */ {51, 52},
 113 /* Node 88 */ {53, 54},
 114 /* Node 89 */ {55, 56},
 115 /* Node 90 */ {57, 58},
 116 /* Node 91 */ {59, 60},
 117 /* Node 92 */ {61, 62},
 118 /* Node 93 */ {63, 64},
 119 /* Node 94 */ {65, 66},
 120 /* Node 95 */ {67, 68},
 121 /* Node 96 */ {69, 70},
 122 /* Node 97 */ {71, 72},
 123 /* Node 98 */ {73, 74},
 124 /* Node 99 */ {75, 76},
 125 /* Node 100 */ {77, 78},
 126 /* Node 101 */ {79, 80},
 127 /* Node 102 */ {81, 82},
 128 /* Node 103 */ {83, 84},
 129 /* Node 104 */ {85, 86},
 130 /* Node 105 */ {87, 88},
 131 /* Node 106 */ {89, 90},
 132 /* Node 107 */ {91, 92},
 133 /* Node 108 */ {93, 94},
 134 /* Node 109 */ {95, 96},
 135 /* Node 110 */ {97, 98},
 136 /* Node 111 */ {99, 100},
 137 /* Node 112 */ {101, 102},
 138 /* Node 113 */ {103, 104},
 139 /* Node 114 */ {105, 106},
 140 /* Node 115 */ {107, 108},
 141 /* Node 116 */ {109, 110},
 142 /* Node 117 */ {111, 112},
 143 /* Node 118 */ {113, 114},
 144 /* Node 119 */ {115, 116},
 145 /* Node 120 */ {117, 118},
 146 /* Node 121 */ {119, 120},
 147 /* Node 122 */ {253, 250},
 148 /* Node 123 */ {251, 252},
 149 /* Node 124 */ {254, 126},
 150 /* Node 125 */ {255, 127},
 151 /* Node 126 */ {170, 123},
 152 /* Node 127 */ {0, 5},
 153 /* Node 128 */ {6, 7},
 154 /* Node 129 */ {8, 9},
 155 /* Node 130 */ {10, 11},
 156 /* Node 131 */ {12, 16},
 157 /* Node 132 */ {17, 18},
 158 /* Node 133 */ {19, 20},
 159 /* Node 134 */ {21, 22},
 160 /* Node 135 */ {23, 24},
 161 /* Node 136 */ {25, 26},
 162 /* Node 137 */ {27, 28},
 163 /* Node 138 */ {29, 30},
 164 /* Node 139 */ {31, 32},
 165 /* Node 140 */ {33, 34},
 166 /* Node 141 */ {35, 36},
 167 /* Node 142 */ {37, 38},
 168 /* Node 143 */ {39, 40},
 169 /* Node 144 */ {41, 42},
 170 /* Node 145 */ {43, 44},
 171 /* Node 146 */ {45, 46},
 172 /* Node 147 */ {47, 48},
 173 /* Node 148 */ {49, 50},
 174 /* Node 149 */ {51, 52},
 175 /* Node 150 */ {53, 54},
 176 /* Node 151 */ {55, 56},
 177 /* Node 152 */ {57, 58},
 178 /* Node 153 */ {59, 60},
 179 /* Node 154 */ {61, 62},
 180 /* Node 155 */ {63, 64},
 181 /* Node 156 */ {65, 66},
 182 /* Node 157 */ {67, 68},
 183 /* Node 158 */ {69, 70},
 184 /* Node 159 */ {71, 72},
 185 /* Node 160 */ {73, 74},
 186 /* Node 161 */ {75, 76},
 187 /* Node 162 */ {77, 78},
 188 /* Node 163 */ {79, 80},
 189 /* Node 164 */ {81, 82},
 190 /* Node 165 */ {83, 84},
 191 /* Node 166 */ {86, 87},
 192 /* Node 167 */ {88, 89},
 193 /* Node 168 */ {90, 91},
 194 /* Node 169 */ {92, 93},
 195 /* Node 170 */ {94, 95},
 196 /* Node 171 */ {96, 97},
 197 /* Node 172 */ {98, 99},
 198 /* Node 173 */ {100, 101},
 199 /* Node 174 */ {102, 103},
 200 /* Node 175 */ {104, 105},
 201 /* Node 176 */ {106, 107},
 202 /* Node 177 */ {108, 109},
 203 /* Node 178 */ {110, 111},
 204 /* Node 179 */ {112, 113},
 205 /* Node 180 */ {114, 115},
 206 /* Node 181 */ {116, 117},
 207 /* Node 182 */ {118, 119},
 208 /* Node 183 */ {120, 121},
 209 /* Node 184 */ {122, 123},
 210 /* Node 185 */ {124, 125},
 211 /* Node 186 */ {126, 127},
 212 /* Node 187 */ {128, 129},
 213 /* Node 188 */ {130, 131},
 214 /* Node 189 */ {132, 133},
 215 /* Node 190 */ {134, 135},
 216 /* Node 191 */ {136, 137},
 217 /* Node 192 */ {138, 139},
 218 /* Node 193 */ {140, 141},
 219 /* Node 194 */ {142, 143},
 220 /* Node 195 */ {144, 145},
 221 /* Node 196 */ {146, 147},
 222 /* Node 197 */ {148, 149},
 223 /* Node 198 */ {150, 151},
 224 /* Node 199 */ {152, 153},
 225 /* Node 200 */ {154, 155},
 226 /* Node 201 */ {156, 157},
 227 /* Node 202 */ {158, 159},
 228 /* Node 203 */ {160, 161},
 229 /* Node 204 */ {162, 163},
 230 /* Node 205 */ {164, 165},
 231 /* Node 206 */ {166, 167},
 232 /* Node 207 */ {168, 169},
 233 /* Node 208 */ {171, 172},
 234 /* Node 209 */ {173, 174},
 235 /* Node 210 */ {175, 176},
 236 /* Node 211 */ {177, 178},
 237 /* Node 212 */ {179, 180},
 238 /* Node 213 */ {181, 182},
 239 /* Node 214 */ {183, 184},
 240 /* Node 215 */ {185, 186},
 241 /* Node 216 */ {187, 188},
 242 /* Node 217 */ {189, 190},
 243 /* Node 218 */ {191, 192},
 244 /* Node 219 */ {193, 194},
 245 /* Node 220 */ {195, 196},
 246 /* Node 221 */ {197, 198},
 247 /* Node 222 */ {199, 200},
 248 /* Node 223 */ {201, 202},
 249 /* Node 224 */ {203, 204},
 250 /* Node 225 */ {205, 206},
 251 /* Node 226 */ {207, 208},
 252 /* Node 227 */ {209, 210},
 253 /* Node 228 */ {211, 212},
 254 /* Node 229 */ {213, 214},
 255 /* Node 230 */ {215, 216},
 256 /* Node 231 */ {217, 218},
 257 /* Node 232 */ {219, 220},
 258 /* Node 233 */ {221, 222},
 259 /* Node 234 */ {223, 224},
 260 /* Node 235 */ {225, 226},
 261 /* Node 236 */ {227, 228},
 262 /* Node 237 */ {229, 230},
 263 /* Node 238 */ {231, 232},
 264 /* Node 239 */ {233, 234},
 265 /* Node 240 */ {235, 236},
 266 /* Node 241 */ {237, 238},
 267 /* Node 242 */ {239, 240},
 268 /* Node 243 */ {241, 242},
 269 /* Node 244 */ {243, 244},
 270 /* Node 245 */ {245, 246},
 271 /* Node 246 */ {247, 248},
 272 /* Node 247 */ {249, 250},
 273 /* Node 248 */ {251, 252},
 274 /* Node 249 */ {253, 254},
 275 /* Node 250 */ {2, 3},
 276 /* Node 251 */ {4, 13},
 277 /* Node 252 */ {14, 15},
 278 /* Node 253 */ {121, 1},
 279 /* Node 254 */ {122, 85}};
 280
 281 const unsigned char data[] = {72, 60, 102, 102, 123, 15};
 282 const unsigned char udata[] = {0x01, 0x02, 0x03, 0x04, 0x55, 0xaa, 0x55, 0xaa, 0x55, 0xaa, 0x55, 0xaa, 0x0d, 0x0e, 0x0f};
 283
 284 unsigned char get_data(void)
 285 {
 286   static int i;
 287   return(data[i++]);
 288 }
 289
 290 unsigned char get_data2(void)
 291 {
 292   static int i;
 293   return(data[i++]);
 294 }
 295 #endif
 296
 297 #ifndef __SDCC_pdk14 // Lack of memory
 298 #if !(defined (__SDCC_pdk15) && defined(__SDCC_STACK_AUTO)) // Lack of code memory
 299 unsigned char huffman_recursive(struct cvu_huffman_state *state)
 300 {
 301         unsigned char direction;
 302         unsigned char ret;
 303
 304         state->buffer >>= 1;
 305         if(state->bit == 8)
 306         {
 307                 state->buffer = (state->input)();
 308                 state->bit = 0;
 309         }
 310         direction = state->buffer & 0x01;
 311         state->bit++;
 312
 313         if(!direction)  /* Left */
 314         {
 315                 if(state->current >= state->ls && state->current < state->rs)
 316                 {
 317                         ret = state->nodes[state->current].left;
 318                         state->current = state->root;
 319                 }
 320                 else
 321                 {
 322                         state->current = state->nodes[state->current].left;
 323                         ret = huffman_recursive(state);
 324                 }
 325         }
 326         else    /* Right */
 327         {
 328                 if(state->current >= state->bs)
 329                 {
 330                         ret = state->nodes[state->current].right;
 331                         state->current = state->root;
 332                 }
 333                 else
 334                 {
 335                         state->current = state->nodes[state->current].right;
 336                         ret = huffman_recursive(state);
 337                 }
 338         }
 339
 340         return(ret);
 341 }
 342
 343 unsigned char huffman_iterative(struct cvu_huffman_state *state)
 344 {
 345         unsigned char current;
 346         unsigned char ret;
 347
 348         current = state->root;
 349
 350         for(;;)
 351         {
 352                 state->buffer >>= 1;
 353                 if(state->bit == 8)
 354                 {
 355                         state->buffer = (state->input)();
 356                         state->bit = 0;
 357                 }
 358                 state->bit++;
 359
 360                 if(!(state->buffer & 0x01))     /* Left */
 361                 {
 362                         if(current >= state->ls && current < state->rs)
 363                         {
 364                                 ret = state->nodes[current].left;
 365                                 break;
 366                         }
 367
 368                         current = state->nodes[current].left;
 369                 }
 370                 else    /* Right */
 371                 {
 372                         if(current >= state->bs)
 373                         {
 374                                 ret = state->nodes[current].right;
 375                                 break;
 376                         }
 377
 378                         current = state->nodes[current].right;
 379                 }
 380         }
 381
 382         return(ret);
 383 }
 384 #endif
 385 #endif
 386
 387 void init_huffman(struct cvu_huffman_state *state, unsigned char (*input)(void), const struct cvu_huffman_node *tree, unsigned char root, unsigned char ls, unsigned char bs, unsigned char rs)
 388 {
 389         state->input = input;
 390         state->nodes = tree;
 391         state->root = root;
 392         state->ls = ls;
 393         state->bs = bs;
 394         state->rs = rs;
 395         state->bit = 8;
 396         state->current = state->root;
 397 }
 398
 399 void testBug(void)
 400 {
 401 #ifndef __SDCC_pdk14 // Lack of memory
 402 #if !(defined (__SDCC_pdk15) && defined(__SDCC_STACK_AUTO)) // Lack of code memory
 403   unsigned char i;
 404   struct cvu_huffman_state state;
 405
 406   init_huffman(&state, &get_data, huffman_tree, HUFFMAN_ROOT, HUFFMAN_LS, HUFFMAN_BS, HUFFMAN_RS);
 407
 408   for(i = 0; i < 15; i++)
 409     ASSERT(huffman_recursive(&state) == udata[i]);
 410
 411   init_huffman(&state, &get_data2, huffman_tree, HUFFMAN_ROOT, HUFFMAN_LS, HUFFMAN_BS, HUFFMAN_RS);
 412
 413   for(i = 0; i < 15; i++)
 414     ASSERT(huffman_iterative(&state) == udata[i]);
 415 #endif
 416 #endif
 417 }
 418