Subversion Repositories Kolibri OS

Rev

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

  1. /*
  2.     jbig2dec
  3.  
  4.     Copyright (C) 2001-2005 Artifex Software, Inc.
  5.  
  6.     This software is distributed under license and may not
  7.     be copied, modified or distributed except as expressly
  8.     authorized under the terms of the license contained in
  9.     the file LICENSE in this distribution.
  10.  
  11.     For further licensing information refer to http://artifex.com/ or
  12.     contact Artifex Software, Inc., 7 Mt. Lassen Drive - Suite A-134,
  13.     San Rafael, CA  94903, U.S.A., +1(415)492-9861.
  14. */
  15.  
  16. /* Huffman table decoding procedures
  17.     -- See Annex B of the JBIG2 specification */
  18.  
  19. #ifdef HAVE_CONFIG_H
  20. #include "config.h"
  21. #endif
  22. #include "os_types.h"
  23.  
  24. #include <stdlib.h>
  25. #include <string.h>
  26.  
  27. #ifdef JBIG2_DEBUG
  28. #include <stdio.h>
  29. #endif
  30.  
  31. #include "jbig2.h"
  32. #include "jbig2_priv.h"
  33. #include "jbig2_huffman.h"
  34. #include "jbig2_hufftab.h"
  35.  
  36. #define JBIG2_HUFFMAN_FLAGS_ISOOB 1
  37. #define JBIG2_HUFFMAN_FLAGS_ISLOW 2
  38. #define JBIG2_HUFFMAN_FLAGS_ISEXT 4
  39.  
  40.  
  41.  
  42. struct _Jbig2HuffmanState {
  43.   /* The current bit offset is equal to (offset * 8) + offset_bits.
  44.      The MSB of this_word is the current bit offset. The MSB of next_word
  45.      is (offset + 4) * 8. */
  46.   uint32_t this_word;
  47.   uint32_t next_word;
  48.   int offset_bits;
  49.   int offset;
  50.  
  51.   Jbig2WordStream *ws;
  52. };
  53.  
  54.  
  55. /** Allocate and initialize a new huffman coding state
  56.  *  the returned pointer can simply be freed; this does
  57.  *  not affect the associated Jbig2WordStream.
  58.  */
  59. Jbig2HuffmanState *
  60. jbig2_huffman_new (Jbig2Ctx *ctx, Jbig2WordStream *ws)
  61. {
  62.   Jbig2HuffmanState *result;
  63.  
  64.   result = (Jbig2HuffmanState *)jbig2_alloc(ctx->allocator,
  65.         sizeof(Jbig2HuffmanState));
  66.  
  67.   if (result != NULL) {
  68.       result->offset = 0;
  69.       result->offset_bits = 0;
  70.       result->this_word = ws->get_next_word (ws, 0);
  71.       result->next_word = ws->get_next_word (ws, 4);
  72.  
  73.       result->ws = ws;
  74.   }
  75.  
  76.   return result;
  77. }
  78.  
  79. /** Free an allocated huffman coding state.
  80.  *  This just calls jbig2_free() if the pointer is not NULL
  81.  */
  82. void
  83. jbig2_huffman_free (Jbig2Ctx *ctx, Jbig2HuffmanState *hs)
  84. {
  85.   if (hs != NULL) free(hs);
  86.   return;
  87. }
  88.  
  89. /** debug routines **/
  90. #ifdef JBIG2_DEBUG
  91.  
  92. /** print current huffman state */
  93. void jbig2_dump_huffman_state(Jbig2HuffmanState *hs) {
  94.   fprintf(stderr, "huffman state %08x %08x offset %d.%d\n",
  95.         hs->this_word, hs->next_word, hs->offset, hs->offset_bits);
  96. }
  97.  
  98. /** print the binary string we're reading from */
  99. void jbig2_dump_huffman_binary(Jbig2HuffmanState *hs)
  100. {
  101.   const uint32_t word = hs->this_word;
  102.   int i;
  103.  
  104.   fprintf(stderr, "huffman binary ");
  105.   for (i = 31; i >= 0; i--)
  106.     fprintf(stderr, ((word >> i) & 1) ? "1" : "0");
  107.   fprintf(stderr, "\n");
  108. }
  109.  
  110. #endif /* JBIG2_DEBUG */
  111.  
  112. /** Skip bits up to the next byte boundary
  113.  */
  114. void
  115. jbig2_huffman_skip(Jbig2HuffmanState *hs)
  116. {
  117.   int bits = hs->offset_bits & 7;
  118.  
  119.   if (bits) {
  120.     bits = 8 - bits;
  121.     hs->offset_bits += bits;
  122.     hs->this_word = (hs->this_word << bits) |
  123.         (hs->next_word >> (32 - hs->offset_bits));
  124.   }
  125.  
  126.   if (hs->offset_bits >= 32) {
  127.     Jbig2WordStream *ws = hs->ws;
  128.     hs->this_word = hs->next_word;
  129.     hs->offset += 4;
  130.     hs->next_word = ws->get_next_word (ws, hs->offset + 4);
  131.     hs->offset_bits -= 32;
  132.     if (hs->offset_bits) {
  133.       hs->this_word = (hs->this_word << hs->offset_bits) |
  134.         (hs->next_word >> (32 - hs->offset_bits));
  135.     }
  136.   }
  137. }
  138.  
  139. /* skip ahead a specified number of bytes in the word stream
  140.  */
  141. void jbig2_huffman_advance(Jbig2HuffmanState *hs, int offset)
  142. {
  143.   Jbig2WordStream *ws = hs->ws;
  144.  
  145.   hs->offset += offset & ~3;
  146.   hs->offset_bits += (offset & 3) << 3;
  147.   if (hs->offset_bits >= 32) {
  148.     hs->offset += 4;
  149.     hs->offset_bits -= 32;
  150.   }
  151.   hs->this_word = ws->get_next_word (ws, hs->offset);
  152.   hs->next_word = ws->get_next_word (ws, hs->offset + 4);
  153.   if (hs->offset_bits > 0)
  154.     hs->this_word = (hs->this_word << hs->offset_bits) |
  155.         (hs->next_word >> (32 - hs->offset_bits));
  156. }
  157.  
  158. /* return the offset of the huffman decode pointer (in bytes)
  159.  * from the beginning of the WordStream
  160.  */
  161. int
  162. jbig2_huffman_offset(Jbig2HuffmanState *hs)
  163. {
  164.   return hs->offset + (hs->offset_bits >> 3);
  165. }
  166.  
  167. /* read a number of bits directly from the huffman state
  168.  * without decoding against a table
  169.  */
  170. int32_t
  171. jbig2_huffman_get_bits (Jbig2HuffmanState *hs, const int bits)
  172. {
  173.   uint32_t this_word = hs->this_word;
  174.   int32_t result;
  175.  
  176.   result = this_word >> (32 - bits);
  177.   hs->offset_bits += bits;
  178.   if (hs->offset_bits >= 32) {
  179.     hs->offset += 4;
  180.     hs->offset_bits -= 32;
  181.     hs->this_word = hs->next_word;
  182.     hs->next_word = hs->ws->get_next_word(hs->ws, hs->offset + 4);
  183.     if (hs->offset_bits) {
  184.       hs->this_word = (hs->this_word << hs->offset_bits) |
  185.         (hs->next_word >> (32 - hs->offset_bits));
  186.     } else {
  187.       hs->this_word = (hs->this_word << hs->offset_bits);
  188.     }
  189.   } else {
  190.     hs->this_word = (this_word << bits) |
  191.         (hs->next_word >> (32 - hs->offset_bits));
  192.   }
  193.  
  194.   return result;
  195. }
  196.  
  197. int32_t
  198. jbig2_huffman_get (Jbig2HuffmanState *hs,
  199.                    const Jbig2HuffmanTable *table, bool *oob)
  200. {
  201.   Jbig2HuffmanEntry *entry;
  202.   byte flags;
  203.   int offset_bits = hs->offset_bits;
  204.   uint32_t this_word = hs->this_word;
  205.   uint32_t next_word;
  206.   int RANGELEN;
  207.   int32_t result;
  208.  
  209.   for (;;)
  210.     {
  211.       int log_table_size = table->log_table_size;
  212.       int PREFLEN;
  213.  
  214.       entry = &table->entries[this_word >> (32 - log_table_size)];
  215.       flags = entry->flags;
  216.       PREFLEN = entry->PREFLEN;
  217.  
  218.       next_word = hs->next_word;
  219.       offset_bits += PREFLEN;
  220.       if (offset_bits >= 32)
  221.         {
  222.           Jbig2WordStream *ws = hs->ws;
  223.           this_word = next_word;
  224.           hs->offset += 4;
  225.           next_word = ws->get_next_word (ws, hs->offset + 4);
  226.           offset_bits -= 32;
  227.           hs->next_word = next_word;
  228.           PREFLEN = offset_bits;
  229.         }
  230.       if (PREFLEN)
  231.         this_word = (this_word << PREFLEN) |
  232.           (next_word >> (32 - offset_bits));
  233.       if (flags & JBIG2_HUFFMAN_FLAGS_ISEXT)
  234.         {
  235.           table = entry->u.ext_table;
  236.         }
  237.       else
  238.         break;
  239.     }
  240.   result = entry->u.RANGELOW;
  241.   RANGELEN = entry->RANGELEN;
  242.   if (RANGELEN > 0)
  243.     {
  244.       int32_t HTOFFSET;
  245.  
  246.       HTOFFSET = this_word >> (32 - RANGELEN);
  247.       if (flags & JBIG2_HUFFMAN_FLAGS_ISLOW)
  248.         result -= HTOFFSET;
  249.       else
  250.         result += HTOFFSET;
  251.  
  252.       offset_bits += RANGELEN;
  253.       if (offset_bits >= 32)
  254.         {
  255.           Jbig2WordStream *ws = hs->ws;
  256.           this_word = next_word;
  257.           hs->offset += 4;
  258.           next_word = ws->get_next_word (ws, hs->offset + 4);
  259.           offset_bits -= 32;
  260.           hs->next_word = next_word;
  261.           RANGELEN = offset_bits;
  262.         }
  263. if (RANGELEN)
  264.       this_word = (this_word << RANGELEN) |
  265.         (next_word >> (32 - offset_bits));
  266.     }
  267.  
  268.   hs->this_word = this_word;
  269.   hs->offset_bits = offset_bits;
  270.  
  271.   if (oob != NULL)
  272.     *oob = (flags & JBIG2_HUFFMAN_FLAGS_ISOOB);
  273.  
  274.   return result;
  275. }
  276.  
  277. /* TODO: more than 8 bits here is wasteful of memory. We have support
  278.    for sub-trees in jbig2_huffman_get() above, but don't use it here.
  279.    We should, and then revert to 8 bits */
  280. #define LOG_TABLE_SIZE_MAX 16
  281.  
  282. /** Build an in-memory representation of a Huffman table from the
  283.  *  set of template params provided by the spec or a table segment
  284.  */
  285. Jbig2HuffmanTable *
  286. jbig2_build_huffman_table (Jbig2Ctx *ctx, const Jbig2HuffmanParams *params)
  287. {
  288.   int *LENCOUNT;
  289.   int LENMAX = -1;
  290.   const int lencountsize = 256 * sizeof(*LENCOUNT);
  291.   const Jbig2HuffmanLine *lines = params->lines;
  292.   int n_lines = params->n_lines;
  293.   int i, j;
  294.   int max_j;
  295.   int log_table_size = 0;
  296.   Jbig2HuffmanTable *result;
  297.   Jbig2HuffmanEntry *entries;
  298.   int CURLEN;
  299.   int firstcode = 0;
  300.   int CURCODE;
  301.   int CURTEMP;
  302.  
  303.   LENCOUNT = jbig2_alloc(ctx->allocator, lencountsize);
  304.   if (LENCOUNT == NULL) {
  305.     jbig2_error(ctx, JBIG2_SEVERITY_FATAL, -1,
  306.       "couldn't allocate storage for huffman histogram");
  307.     return NULL;
  308.   }
  309.   memset(LENCOUNT, 0, lencountsize);
  310.  
  311.   /* B.3, 1. */
  312.   for (i = 0; i < params->n_lines; i++)
  313.     {
  314.       int PREFLEN = lines[i].PREFLEN;
  315.       int lts;
  316.  
  317.       if (PREFLEN > LENMAX)
  318.                 {
  319.                         for (j = LENMAX + 1; j < PREFLEN + 1; j++)
  320.                                 LENCOUNT[j] = 0;
  321.                         LENMAX = PREFLEN;
  322.                 }
  323.       LENCOUNT[PREFLEN]++;
  324.  
  325.       lts = PREFLEN + lines[i].RANGELEN;
  326.       if (lts > LOG_TABLE_SIZE_MAX)
  327.                 lts = PREFLEN;
  328.       if (lts <= LOG_TABLE_SIZE_MAX && log_table_size < lts)
  329.                 log_table_size = lts;
  330.     }
  331.   jbig2_error(ctx, JBIG2_SEVERITY_DEBUG, -1,
  332.         "constructing huffman table log size %d", log_table_size);
  333.   max_j = 1 << log_table_size;
  334.  
  335.   result = (Jbig2HuffmanTable *)jbig2_alloc(ctx->allocator, sizeof(Jbig2HuffmanTable));
  336.   result->log_table_size = log_table_size;
  337.   entries = (Jbig2HuffmanEntry *)jbig2_alloc(ctx->allocator, max_j * sizeof(Jbig2HuffmanEntry));
  338.   result->entries = entries;
  339.  
  340.   LENCOUNT[0] = 0;
  341.  
  342.   for (CURLEN = 1; CURLEN <= LENMAX; CURLEN++)
  343.     {
  344.       int shift = log_table_size - CURLEN;
  345.  
  346.       /* B.3 3.(a) */
  347.       firstcode = (firstcode + LENCOUNT[CURLEN - 1]) << 1;
  348.       CURCODE = firstcode;
  349.       /* B.3 3.(b) */
  350.       for (CURTEMP = 0; CURTEMP < n_lines; CURTEMP++)
  351.         {
  352.           int PREFLEN = lines[CURTEMP].PREFLEN;
  353.           if (PREFLEN == CURLEN)
  354.             {
  355.               int RANGELEN = lines[CURTEMP].RANGELEN;
  356.               int start_j = CURCODE << shift;
  357.               int end_j = (CURCODE + 1) << shift;
  358.               byte eflags = 0;
  359.  
  360.               if (end_j > max_j) {
  361.                 jbig2_error(ctx, JBIG2_SEVERITY_FATAL, -1,
  362.                   "ran off the end of the entries table! (%d >= %d)",
  363.                   end_j, max_j);
  364.                 jbig2_free(ctx->allocator, result->entries);
  365.                 jbig2_free(ctx->allocator, result);
  366.                 jbig2_free(ctx->allocator, LENCOUNT);
  367.                 return NULL;
  368.               }
  369.               /* todo: build extension tables */
  370.               if (params->HTOOB && CURTEMP == n_lines - 1)
  371.                 eflags |= JBIG2_HUFFMAN_FLAGS_ISOOB;
  372.               if (CURTEMP == n_lines - (params->HTOOB ? 3 : 2))
  373.                 eflags |= JBIG2_HUFFMAN_FLAGS_ISLOW;
  374.               if (PREFLEN + RANGELEN > LOG_TABLE_SIZE_MAX) {
  375.                   for (j = start_j; j < end_j; j++) {
  376.                       entries[j].u.RANGELOW = lines[CURTEMP].RANGELOW;
  377.                       entries[j].PREFLEN = PREFLEN;
  378.                       entries[j].RANGELEN = RANGELEN;
  379.                       entries[j].flags = eflags;
  380.                     }
  381.               } else {
  382.                   for (j = start_j; j < end_j; j++) {
  383.                       int32_t HTOFFSET = (j >> (shift - RANGELEN)) &
  384.                         ((1 << RANGELEN) - 1);
  385.                       if (eflags & JBIG2_HUFFMAN_FLAGS_ISLOW)
  386.                         entries[j].u.RANGELOW = lines[CURTEMP].RANGELOW -
  387.                           HTOFFSET;
  388.                       else
  389.                         entries[j].u.RANGELOW = lines[CURTEMP].RANGELOW +
  390.                           HTOFFSET;
  391.                       entries[j].PREFLEN = PREFLEN + RANGELEN;
  392.                       entries[j].RANGELEN = 0;
  393.                       entries[j].flags = eflags;
  394.                     }
  395.                 }
  396.               CURCODE++;
  397.             }
  398.         }
  399.     }
  400.  
  401.   jbig2_free(ctx->allocator, LENCOUNT);
  402.  
  403.   return result;
  404. }
  405.  
  406. /** Free the memory associated with the representation of table */
  407. void
  408. jbig2_release_huffman_table (Jbig2Ctx *ctx, Jbig2HuffmanTable *table)
  409. {
  410.   if (table != NULL) {
  411.       jbig2_free(ctx->allocator, table->entries);
  412.       jbig2_free(ctx->allocator, table);
  413.   }
  414.   return;
  415. }
  416.  
  417. #ifdef TEST
  418. #include <stdio.h>
  419.  
  420. /* a test bitstream, and a list of the table indicies
  421.    to use in decoding it. 1 = table B.1 (A), 2 = table B.2 (B), and so on */
  422. /* this test stream should decode to { 8, 5, oob, 8 } */
  423.  
  424. const byte      test_stream[] = { 0xe9, 0xcb, 0xf4, 0x00 };
  425. const byte      test_tabindex[] = { 4, 2, 2, 1 };
  426.  
  427. static uint32_t
  428. test_get_word (Jbig2WordStream *self, int offset)
  429. {
  430.         /* assume test_stream[] is at least 4 bytes */
  431.         if (offset+3 > sizeof(test_stream))
  432.                 return 0;
  433.         else
  434.                 return ( (test_stream[offset] << 24) |
  435.                                  (test_stream[offset+1] << 16) |
  436.                                  (test_stream[offset+2] << 8) |
  437.                                  (test_stream[offset+3]) );
  438. }
  439.  
  440. int
  441. main (int argc, char **argv)
  442. {
  443.   Jbig2Ctx *ctx;
  444.   Jbig2HuffmanTable *tables[5];
  445.   Jbig2HuffmanState *hs;
  446.   Jbig2WordStream ws;
  447.   bool oob;
  448.   int32_t code;
  449.  
  450.   ctx = jbig2_ctx_new(NULL, 0, NULL, NULL, NULL);
  451.  
  452.   tables[0] = NULL;
  453.   tables[1] = jbig2_build_huffman_table (ctx, &jbig2_huffman_params_A);
  454.   tables[2] = jbig2_build_huffman_table (ctx, &jbig2_huffman_params_B);
  455.   tables[3] = NULL;
  456.   tables[4] = jbig2_build_huffman_table (ctx, &jbig2_huffman_params_D);
  457.   ws.get_next_word = test_get_word;
  458.   hs = jbig2_huffman_new (ctx, &ws);
  459.  
  460.   printf("testing jbig2 huffmann decoding...");
  461.   printf("\t(should be 8 5 (oob) 8)\n");
  462.  
  463.   {
  464.         int i;
  465.         int sequence_length = sizeof(test_tabindex);
  466.  
  467.         for (i = 0; i < sequence_length; i++) {
  468.                 code = jbig2_huffman_get (hs, tables[test_tabindex[i]], &oob);
  469.                 if (oob) printf("(oob) ");
  470.                 else printf("%d ", code);
  471.         }
  472.   }
  473.  
  474.   printf("\n");
  475.  
  476.   jbig2_ctx_free(ctx);
  477.  
  478.   return 0;
  479. }
  480. #endif
  481.