home *** CD-ROM | disk | FTP | other *** search
/ The C Users' Group Library 1994 August / wc-cdrom-cusersgrouplibrary-1994-08.iso / listings / v_08_06 / 8n06052a < prev    next >
Text File  |  1989-06-11  |  7KB  |  202 lines
  1.  
  2. Listing 3 - Table build routines
  3.  
  4. #define BLACK 1
  5. #define WHITE 0
  6. #define MSB_FIRST 0
  7. #define LSB_FIRST 1
  8. #define INVALID_CODE -1
  9. #define INCOMPLETE_CODE -2
  10. #define EOL_CODE -3
  11.  
  12. struct
  13. { char x_color; long x_prefix; short x_index;
  14. } index_table [216];
  15. short index_table_fill = 0;
  16.  
  17. long branch_table_fill = 0, action_table_fill = 0;
  18. char bit_order = MSB_FIRST; /* this is the sequence of bits
  19. in the group 3 data file for which the table will be used */
  20. int action_handle, branch_handle;
  21.  
  22. /* build decoding tables for group 3 compressed images */
  23. int main () {
  24.   branch_handle = open (...file to contain branch_table...);
  25.   action_handle = open (...file to contain action_table...);
  26.   build_table (0, WHITE);
  27.   close (branch_handle); close (action_handle);
  28. }
  29.  
  30. long append_0 (long prefix) {
  31.   return (prefix + 0x10000); /* incr bit strng lngth */
  32. }
  33.  
  34. long append_1 (long prefix) {
  35.   unsigned short prefix_length;
  36.   static unsigned short prefix_mask [16] = {0x8000, 0x4000,
  37.     0x2000, 0x1000, 0x0800, 0x0400, 0x0200, 0x0100, 0x0080,
  38.     0x0040, 0x0020, 0x0010, 0x0008, 0x0004, 0x0002, 0x0001};
  39.   prefix_length = 0xFF & (prefix >> 16);
  40.   return (prefix + 0x10000 + prefix_mask [prefix_length]);
  41. }
  42.  
  43. /* add a table entry for the specified prefix */
  44. short build_table (long prefix, char color) {
  45.   short table_index;
  46.   unsigned short byte_value;
  47.   long *branch_record;
  48.   if ((table_index = search_offset (prefix, color)) != -1)
  49.     /* if already done */ return (table_index);
  50.   branch_record = malloc (256 * sizeof (long));
  51.   table_index = branch_table_fill++;
  52.   index_table [index_table_fill].x_prefix = prefix;
  53.   index_table [index_table_fill].x_color = color;
  54.   index_table [index_table_fill].x_index = table_index;
  55.   index_table_fill++;
  56.   for (byte_value = 0; byte_value < 256; byte_value++) {
  57.     unsigned char bit_mask;
  58.     unsigned short bit_number; /* the first bit examined
  59.       is bit zero */
  60.     static unsigned char msb_mask [8] = {0x80, 0x40, 0x20,
  61.       0x10, 0x08, 0x04, 0x02, 0x01};
  62.     static unsigned char lsb_mask [8] = {0x01, 0x02, 0x04,
  63.       0x08, 0x10, 0x20, 0x40, 0x80};
  64.     long working_prefix;
  65.     char working_color;
  66.     working_prefix = prefix;
  67.     working_color = color;
  68.     branch_record [byte_value] = action_table_fill;
  69.     for (bit_number = 0; bit_number < 8; bit_number++) {
  70.       if (bit_order == MSB_FIRST)
  71.         bit_mask = msb_mask [bit_number];
  72.       else bit_mask = lsb_mask [bit_number];
  73.       if (bit_mask & byte_value)
  74.         working_prefix = append_1 (working_prefix);
  75.       else working_prefix = append_0 (working_prefix);
  76.       if (working_color == WHITE) {
  77.         short runlength;
  78.         runlength = white_run_length (working_prefix);
  79.         if (runlength == INVALID_CODE) {
  80.           emit_byte (1); bit_number = 8;
  81.           working_prefix = 0;
  82.         }
  83.         else if (runlength == EOL_CODE) {
  84.           emit_byte (0); working_prefix = 0;
  85.         }
  86.         else if (runlength != INCOMPLETE_CODE) {
  87.           if (runlength < 64) emit_byte (runlength + 2);
  88.           else emit_byte ((runlength / 64) + 65);
  89.           if (runlength < 64) working_color = BLACK;
  90.           working_prefix = 0;
  91.         }
  92.         /* else incomplete code */
  93.       }
  94.       else /* working_color == BLACK */ {
  95.         short runlength;
  96.         runlength = black_run_length (working_prefix);
  97.         if (runlength == INVALID_CODE) {
  98.           emit_byte (1); bit_number = 8;
  99.           working_prefix = 0;
  100.         }
  101.         else if (runlength == EOL_CODE) {
  102.           emit_byte (0); working_color = WHITE;
  103.           working_prefix = 0;
  104.         }
  105.         else if (runlength != INCOMPLETE_CODE) {
  106.           if (runlength < 64) emit_byte (runlength + 106);
  107.           else emit_byte ((runlength / 64) + 169);
  108.           if (runlength < 64) working_color = WHITE;
  109.           working_prefix = 0;
  110.         }
  111.         /* else incomplete code */
  112.       }
  113.     } /* bit number loop */
  114.     { /* descend and update table */
  115.       long saved_fill, position_1, position_2;
  116.       short newstate;
  117.       position_1 = tell (action_handle); /* save position */
  118.       emit_state (0); /* hold place in file */
  119.       newstate = build_table (working_prefix,
  120.          working_color);
  121.       position_2 = tell (action_handle);
  122.       saved_fill = action_table_fill;
  123.       lseek (action_handle, position_1, SEEK_SET);
  124.       emit_state (newstate);
  125.       lseek (action_handle, position_2, SEEK_SET);
  126.       action_table_fill = saved_fill;
  127.     }
  128.   } /* byte value loop */
  129.   lseek (branch_handle, 256L * (long) sizeof (long)
  130.     * (long) table_index, SEEK_SET); /* position to row */
  131.   write (branch_handle, (char *) branch_record,
  132.     256 * sizeof (long)); /* write row of table */
  133.   free (branch_record);
  134.   return (table_index);
  135. }
  136.  
  137. void emit_byte (unsigned char value) {
  138.   write (action_handle, &value, 1);
  139.   action_table_fill++;
  140. }
  141.  
  142. void emit_state (short newstate) {
  143.   emit_byte (255);
  144.   emit_byte ((unsigned char) newstate);
  145. }
  146.  
  147. /* determine if the table for a prefix already exists - if
  148. it does, return its offset in the table, else return -1 */
  149. short search_offset (long prefix, char color) {
  150.   short j;
  151.   for (j = 0; j < index_table_fill; j++)
  152.     if (prefix == index_table [j].x_prefix
  153.       && color == index_table [j].x_color)
  154.         return (j);
  155.   return (-1);
  156. }
  157.  
  158. short search_run_length_table (long prefix, long *p_table) {
  159.   short table_offset = 0;
  160.   long prefix_length, prefix_value;
  161.   prefix_length = 0xFF & (prefix >> 16);
  162.   prefix_value = 0xFFFF & prefix;
  163.   while (p_table [table_offset]) {
  164.     if (p_table [table_offset] == prefix_length
  165.       && p_table [table_offset + 1] == prefix_value)
  166.         return ((short) p_table [table_offset + 2]);
  167.     table_offset += 3; /* move on to next entry */
  168.   }
  169.   return (INCOMPLETE_CODE); /* no entry found in table */
  170. }
  171.  
  172. short white_run_length (long prefix) {
  173.   static long code_table [] = {
  174.     8, 0x3500, 0, /* 0011 0101 */
  175.     6, 0x1C00, 1, /* 0001 11 */
  176. ... lines omitted: fill in from Table 1 ...
  177.     12, 0x01F0, 2560, /* 0000 0001 1111 */
  178.     12, 0x0010, EOL_CODE, /* 0000 0000 0001 */
  179.     9, 0x0080, INVALID_CODE, /* 0000 0000 1 */
  180.     10, 0x0040, INVALID_CODE, /* 0000 0000 01 */
  181.     11, 0x0020, INVALID_CODE, /* 0000 0000 001 */
  182.     12, 0x0000, INVALID_CODE, /* 0000 0000 0000 */
  183.     0 /* end-of-table */ };
  184.   return (search_run_length_table (prefix, code_table));
  185. }
  186.  
  187. short black_run_length (long prefix) {
  188.   static long code_table [] = {
  189.     10, 0x0DC0, 0, /* 0000 1101 11 */
  190.     3, 0x4000, 1, /* 010 */
  191. ... lines omitted: fill in from Table 1 ...
  192.     12, 0x01F0, 2560, /* 0000 0001 1111 */
  193.     12, 0x0010, EOL_CODE, /* 0000 0000 0001 */
  194.     9, 0x0080, INVALID_CODE, /* 0000 0000 1 */
  195.     10, 0x0040, INVALID_CODE, /* 0000 0000 01 */
  196.     11, 0x0020, INVALID_CODE, /* 0000 0000 001 */
  197.     12, 0x0000, INVALID_CODE, /* 0000 0000 0000 */
  198.     0 /* end-of-table */ };
  199.   return (search_run_length_table (prefix, code_table));
  200. }
  201.  
  202.