Subversion Repositories Kolibri OS

Rev

Go to most recent revision | Blame | Compare with Previous | Last modification | View Log | RSS feed

  1. #include "fitz.h"
  2.  
  3. /* TODO: error checking */
  4.  
  5. enum
  6. {
  7.         MIN_BITS = 9,
  8.         MAX_BITS = 12,
  9.         NUM_CODES = (1 << MAX_BITS),
  10.         LZW_CLEAR = 256,
  11.         LZW_EOD = 257,
  12.         LZW_FIRST = 258,
  13.         MAX_LENGTH = 4097
  14. };
  15.  
  16. typedef struct lzw_code_s lzw_code;
  17.  
  18. struct lzw_code_s
  19. {
  20.         int prev;                       /* prev code (in string) */
  21.         unsigned short length;          /* string len, including this token */
  22.         unsigned char value;            /* data value */
  23.         unsigned char first_char;       /* first token of string */
  24. };
  25.  
  26. typedef struct fz_lzwd_s fz_lzwd;
  27.  
  28. struct fz_lzwd_s
  29. {
  30.         fz_stream *chain;
  31.         int eod;
  32.  
  33.         int early_change;
  34.  
  35.         int code_bits;                  /* num bits/code */
  36.         int code;                       /* current code */
  37.         int old_code;                   /* previously recognized code */
  38.         int next_code;                  /* next free entry */
  39.  
  40.         lzw_code table[NUM_CODES];
  41.  
  42.         unsigned char bp[MAX_LENGTH];
  43.         unsigned char *rp, *wp;
  44. };
  45.  
  46. static int
  47. read_lzwd(fz_stream *stm, unsigned char *buf, int len)
  48. {
  49.         fz_lzwd *lzw = stm->state;
  50.         lzw_code *table = lzw->table;
  51.         unsigned char *p = buf;
  52.         unsigned char *ep = buf + len;
  53.         unsigned char *s;
  54.         int codelen;
  55.  
  56.         int code_bits = lzw->code_bits;
  57.         int code = lzw->code;
  58.         int old_code = lzw->old_code;
  59.         int next_code = lzw->next_code;
  60.  
  61.         while (lzw->rp < lzw->wp && p < ep)
  62.                 *p++ = *lzw->rp++;
  63.  
  64.         while (p < ep)
  65.         {
  66.                 if (lzw->eod)
  67.                         return 0;
  68.  
  69.                 code = fz_read_bits(lzw->chain, code_bits);
  70.  
  71.                 if (fz_is_eof_bits(lzw->chain))
  72.                 {
  73.                         lzw->eod = 1;
  74.                         break;
  75.                 }
  76.  
  77.                 if (code == LZW_EOD)
  78.                 {
  79.                         lzw->eod = 1;
  80.                         break;
  81.                 }
  82.  
  83.                 if (code == LZW_CLEAR)
  84.                 {
  85.                         code_bits = MIN_BITS;
  86.                         next_code = LZW_FIRST;
  87.                         old_code = -1;
  88.                         continue;
  89.                 }
  90.  
  91.                 /* if stream starts without a clear code, old_code is undefined... */
  92.                 if (old_code == -1)
  93.                 {
  94.                         old_code = code;
  95.                 }
  96.                 else
  97.                 {
  98.                         /* add new entry to the code table */
  99.                         table[next_code].prev = old_code;
  100.                         table[next_code].first_char = table[old_code].first_char;
  101.                         table[next_code].length = table[old_code].length + 1;
  102.                         if (code < next_code)
  103.                                 table[next_code].value = table[code].first_char;
  104.                         else if (code == next_code)
  105.                                 table[next_code].value = table[next_code].first_char;
  106.                         else
  107.                                 fz_warn("out of range code encountered in lzw decode");
  108.  
  109.                         next_code ++;
  110.  
  111.                         if (next_code > (1 << code_bits) - lzw->early_change - 1)
  112.                         {
  113.                                 code_bits ++;
  114.                                 if (code_bits > MAX_BITS)
  115.                                         code_bits = MAX_BITS;   /* FIXME */
  116.                         }
  117.  
  118.                         old_code = code;
  119.                 }
  120.  
  121.                 /* code maps to a string, copy to output (in reverse...) */
  122.                 if (code > 255)
  123.                 {
  124.                         codelen = table[code].length;
  125.                         lzw->rp = lzw->bp;
  126.                         lzw->wp = lzw->bp + codelen;
  127.  
  128.                         assert(codelen < MAX_LENGTH);
  129.  
  130.                         s = lzw->wp;
  131.                         do {
  132.                                 *(--s) = table[code].value;
  133.                                 code = table[code].prev;
  134.                         } while (code >= 0 && s > lzw->bp);
  135.                 }
  136.  
  137.                 /* ... or just a single character */
  138.                 else
  139.                 {
  140.                         lzw->bp[0] = code;
  141.                         lzw->rp = lzw->bp;
  142.                         lzw->wp = lzw->bp + 1;
  143.                 }
  144.  
  145.                 /* copy to output */
  146.                 while (lzw->rp < lzw->wp && p < ep)
  147.                         *p++ = *lzw->rp++;
  148.         }
  149.  
  150.         lzw->code_bits = code_bits;
  151.         lzw->code = code;
  152.         lzw->old_code = old_code;
  153.         lzw->next_code = next_code;
  154.  
  155.         return p - buf;
  156. }
  157.  
  158. static void
  159. close_lzwd(fz_stream *stm)
  160. {
  161.         fz_lzwd *lzw = stm->state;
  162.         fz_close(lzw->chain);
  163.         fz_free(lzw);
  164. }
  165.  
  166. fz_stream *
  167. fz_open_lzwd(fz_stream *chain, fz_obj *params)
  168. {
  169.         fz_lzwd *lzw;
  170.         fz_obj *obj;
  171.         int i;
  172.  
  173.         lzw = fz_malloc(sizeof(fz_lzwd));
  174.         lzw->chain = chain;
  175.         lzw->eod = 0;
  176.         lzw->early_change = 1;
  177.  
  178.         obj = fz_dict_gets(params, "EarlyChange");
  179.         if (obj)
  180.                 lzw->early_change = !!fz_to_int(obj);
  181.  
  182.         for (i = 0; i < 256; i++)
  183.         {
  184.                 lzw->table[i].value = i;
  185.                 lzw->table[i].first_char = i;
  186.                 lzw->table[i].length = 1;
  187.                 lzw->table[i].prev = -1;
  188.         }
  189.  
  190.         for (i = 256; i < NUM_CODES; i++)
  191.         {
  192.                 lzw->table[i].value = 0;
  193.                 lzw->table[i].first_char = 0;
  194.                 lzw->table[i].length = 0;
  195.                 lzw->table[i].prev = -1;
  196.         }
  197.  
  198.         lzw->code_bits = MIN_BITS;
  199.         lzw->code = -1;
  200.         lzw->next_code = LZW_FIRST;
  201.         lzw->old_code = -1;
  202.         lzw->rp = lzw->bp;
  203.         lzw->wp = lzw->bp;
  204.  
  205.         return fz_new_stream(lzw, read_lzwd, close_lzwd);
  206. }
  207.