Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

  1. /*
  2.     jbig2dec
  3.  
  4.     Copyright (C) 2001-2005 Artifex Software, Inc.
  5.  
  6.     This software is provided AS-IS with no warranty,
  7.     either express or implied.
  8.  
  9.     This software is distributed under license and may not
  10.     be copied, modified or distributed except as expressly
  11.     authorized under the terms of the license contained in
  12.     the file LICENSE in this distribution.
  13.  
  14.     For further licensing information refer to http://artifex.com/ or
  15.     contact Artifex Software, Inc., 7 Mt. Lassen Drive - Suite A-134,
  16.     San Rafael, CA  94903, U.S.A., +1(415)492-9861.
  17. */
  18.  
  19. #ifdef HAVE_CONFIG_H
  20. #include "config.h"
  21. #endif
  22. #include "os_types.h"
  23.  
  24. #include <stdio.h>
  25. #include <stdlib.h>
  26.  
  27. #include "jbig2.h"
  28. #include "jbig2_priv.h"
  29. #include "jbig2_arith.h"
  30.  
  31. #ifdef JBIG2_DEBUG
  32. #include <stdio.h>
  33. #endif
  34.  
  35. struct _Jbig2ArithState {
  36.   uint32_t C;
  37.   int A;
  38.  
  39.   int CT;
  40.  
  41.   uint32_t next_word;
  42.   int next_word_bytes;
  43.  
  44.   Jbig2WordStream *ws;
  45.   int offset;
  46. };
  47.  
  48. #undef SOFTWARE_CONVENTION
  49.  
  50. /*
  51.   A note on the "software conventions".
  52.  
  53.   Previously, I had misinterpreted the spec, and had thought that the
  54.   spec's description of the "software convention" was wrong. Now I
  55.   believe that this code is both correct and matches the spec, with
  56.   SOFTWARE_CONVENTION defined or not. Thanks to William Rucklidge for
  57.   the clarification.
  58.  
  59.   In any case, my benchmarking indicates no speed difference at all.
  60.   Therefore, for now we will just use the normative version.
  61.  
  62.  */
  63.  
  64. static void
  65. jbig2_arith_bytein (Jbig2ArithState *as)
  66. {
  67.   byte B;
  68.  
  69.   /* invariant: as->next_word_bytes > 0 */
  70.  
  71.   /* Figure G.3 */
  72.   B = (byte)((as->next_word >> 24) & 0xFF);
  73.   if (B == 0xFF)
  74.     {
  75.       byte B1;
  76.       if (as->next_word_bytes == 1)
  77.         {
  78.           Jbig2WordStream *ws = as->ws;
  79.           as->next_word = ws->get_next_word (ws, as->offset);
  80.           as->offset += 4;
  81.           B1 = (byte)((as->next_word >> 24) & 0xFF);
  82.           if (B1 > 0x8F)
  83.             {
  84. #ifdef JBIG2_DEBUG_ARITH
  85.               fprintf(stderr, "read %02x (aa)\n", B);
  86. #endif
  87. #ifndef SOFTWARE_CONVENTION
  88.               as->C += 0xFF00;
  89. #endif
  90.               as->CT = 8;
  91.               as->next_word = (0xFF00 | B1) << 16;
  92.               as->next_word_bytes = 2;
  93.             }
  94.           else
  95.             {
  96. #ifdef JBIG2_DEBUG_ARITH
  97.               fprintf(stderr, "read %02x (a)\n", B);
  98. #endif
  99. #ifdef SOFTWARE_CONVENTION
  100.               as->C += 0xFE00 - (B1 << 9);
  101. #else
  102.               as->C += B1 << 9;
  103. #endif
  104.               as->CT = 7;
  105.               as->next_word_bytes = 4;
  106.             }
  107.         }
  108.       else
  109.         {
  110.           B1 = (byte)((as->next_word >> 16) & 0xFF);
  111.           if (B1 > 0x8F)
  112.             {
  113. #ifdef JBIG2_DEBUG_ARITH
  114.               fprintf(stderr, "read %02x (ba)\n", B);
  115. #endif
  116. #ifndef SOFTWARE_CONVENTION
  117.               as->C += 0xFF00;
  118. #endif
  119.               as->CT = 8;
  120.             }
  121.           else
  122.             {
  123.               as->next_word_bytes--;
  124.               as->next_word <<= 8;
  125. #ifdef JBIG2_DEBUG_ARITH
  126.               fprintf(stderr, "read %02x (b)\n", B);
  127. #endif
  128.  
  129. #ifdef SOFTWARE_CONVENTION
  130.               as->C += 0xFE00 - (B1 << 9);
  131. #else
  132.               as->C += (B1 << 9);
  133. #endif
  134.               as->CT = 7;
  135.             }
  136.         }
  137.     }
  138.   else
  139.     {
  140. #ifdef JBIG2_DEBUG_ARITH
  141.       fprintf(stderr, "read %02x\n", B);
  142. #endif
  143.       as->CT = 8;
  144.       as->next_word <<= 8;
  145.       as->next_word_bytes--;
  146.       if (as->next_word_bytes == 0)
  147.         {
  148.           Jbig2WordStream *ws = as->ws;
  149.  
  150.           as->next_word = ws->get_next_word (ws, as->offset);
  151.           as->offset += 4;
  152.           as->next_word_bytes = 4;
  153.         }
  154.       B = (byte)((as->next_word >> 24) & 0xFF);
  155. #ifdef SOFTWARE_CONVENTION
  156.       as->C += 0xFF00 - (B << 8);
  157. #else
  158.       as->C += (B << 8);
  159. #endif
  160.     }
  161. }
  162.  
  163. #if defined(JBIG2_DEBUG) || defined(JBIG2_DEBUG_ARITH)
  164. #include <stdio.h>
  165.  
  166. static void
  167. jbig2_arith_trace (Jbig2ArithState *as, Jbig2ArithCx cx)
  168. {
  169.   fprintf(stderr, "I = %2d, MPS = %d, A = %04x, CT = %2d, C = %08x\n",
  170.           cx & 0x7f, cx >> 7, as->A, as->CT, as->C);
  171. }
  172. #endif
  173.  
  174. /** Allocate and initialize a new arithmetic coding state
  175.  *  the returned pointer can simply be freed; this does
  176.  *  not affect the associated Jbig2WordStream.
  177.  */
  178. Jbig2ArithState *
  179. jbig2_arith_new (Jbig2Ctx *ctx, Jbig2WordStream *ws)
  180. {
  181.   Jbig2ArithState *result;
  182.  
  183.   result = (Jbig2ArithState *)jbig2_alloc(ctx->allocator,
  184.         sizeof(Jbig2ArithState));
  185.  
  186.   result->ws = ws;
  187.  
  188.   result->next_word = ws->get_next_word (ws, 0);
  189.   result->next_word_bytes = 4;
  190.   result->offset = 4;
  191.  
  192.   /* Figure G.1 */
  193. #ifdef SOFTWARE_CONVENTION
  194.   result->C = (~(result->next_word >> 8)) & 0xFF0000;
  195. #else
  196.   result->C = (result->next_word >> 8) & 0xFF0000;
  197. #endif
  198.  
  199.   jbig2_arith_bytein (result);
  200.   result->C <<= 7;
  201.   result->CT -= 7;
  202.   result->A = 0x8000;
  203.  
  204.   return result;
  205. }
  206.  
  207. /* could put bit fields in to minimize memory usage */
  208. typedef struct {
  209.   unsigned short Qe;
  210.   byte mps_xor; /* mps_xor = index ^ NMPS */
  211.   byte lps_xor; /* lps_xor = index ^ NLPS ^ (SWITCH << 7) */
  212. } Jbig2ArithQe;
  213.  
  214. const Jbig2ArithQe jbig2_arith_Qe[] = {
  215.   { 0x5601,  1 ^  0,  1 ^  0 ^ 0x80 },
  216.   { 0x3401,  2 ^  1,  6 ^  1 },
  217.   { 0x1801,  3 ^  2,  9 ^  2 },
  218.   { 0x0AC1,  4 ^  3, 12 ^  3 },
  219.   { 0x0521,  5 ^  4, 29 ^  4 },
  220.   { 0x0221, 38 ^  5, 33 ^  5 },
  221.   { 0x5601,  7 ^  6,  6 ^  6 ^ 0x80 },
  222.   { 0x5401,  8 ^  7, 14 ^  7 },
  223.   { 0x4801,  9 ^  8, 14 ^  8 },
  224.   { 0x3801, 10 ^  9, 14 ^  9 },
  225.   { 0x3001, 11 ^ 10, 17 ^ 10 },
  226.   { 0x2401, 12 ^ 11, 18 ^ 11 },
  227.   { 0x1C01, 13 ^ 12, 20 ^ 12 },
  228.   { 0x1601, 29 ^ 13, 21 ^ 13 },
  229.   { 0x5601, 15 ^ 14, 14 ^ 14 ^ 0x80 },
  230.   { 0x5401, 16 ^ 15, 14 ^ 15 },
  231.   { 0x5101, 17 ^ 16, 15 ^ 16 },
  232.   { 0x4801, 18 ^ 17, 16 ^ 17 },
  233.   { 0x3801, 19 ^ 18, 17 ^ 18 },
  234.   { 0x3401, 20 ^ 19, 18 ^ 19 },
  235.   { 0x3001, 21 ^ 20, 19 ^ 20 },
  236.   { 0x2801, 22 ^ 21, 19 ^ 21 },
  237.   { 0x2401, 23 ^ 22, 20 ^ 22 },
  238.   { 0x2201, 24 ^ 23, 21 ^ 23 },
  239.   { 0x1C01, 25 ^ 24, 22 ^ 24 },
  240.   { 0x1801, 26 ^ 25, 23 ^ 25 },
  241.   { 0x1601, 27 ^ 26, 24 ^ 26 },
  242.   { 0x1401, 28 ^ 27, 25 ^ 27 },
  243.   { 0x1201, 29 ^ 28, 26 ^ 28 },
  244.   { 0x1101, 30 ^ 29, 27 ^ 29 },
  245.   { 0x0AC1, 31 ^ 30, 28 ^ 30 },
  246.   { 0x09C1, 32 ^ 31, 29 ^ 31 },
  247.   { 0x08A1, 33 ^ 32, 30 ^ 32 },
  248.   { 0x0521, 34 ^ 33, 31 ^ 33 },
  249.   { 0x0441, 35 ^ 34, 32 ^ 34 },
  250.   { 0x02A1, 36 ^ 35, 33 ^ 35 },
  251.   { 0x0221, 37 ^ 36, 34 ^ 36 },
  252.   { 0x0141, 38 ^ 37, 35 ^ 37 },
  253.   { 0x0111, 39 ^ 38, 36 ^ 38 },
  254.   { 0x0085, 40 ^ 39, 37 ^ 39 },
  255.   { 0x0049, 41 ^ 40, 38 ^ 40 },
  256.   { 0x0025, 42 ^ 41, 39 ^ 41 },
  257.   { 0x0015, 43 ^ 42, 40 ^ 42 },
  258.   { 0x0009, 44 ^ 43, 41 ^ 43 },
  259.   { 0x0005, 45 ^ 44, 42 ^ 44 },
  260.   { 0x0001, 45 ^ 45, 43 ^ 45 },
  261.   { 0x5601, 46 ^ 46, 46 ^ 46 }
  262. };
  263.  
  264. static void
  265. jbig2_arith_renormd (Jbig2ArithState *as)
  266. {
  267.   /* Figure E.18 */
  268.   do
  269.     {
  270.       if (as->CT == 0)
  271.         jbig2_arith_bytein (as);
  272.       as->A <<= 1;
  273.       as->C <<= 1;
  274.       as->CT--;
  275.     }
  276.   while ((as->A & 0x8000) == 0);
  277. }
  278.  
  279. bool
  280. jbig2_arith_decode (Jbig2ArithState *as, Jbig2ArithCx *pcx)
  281. {
  282.   Jbig2ArithCx cx = *pcx;
  283.   const Jbig2ArithQe *pqe = &jbig2_arith_Qe[cx & 0x7f];
  284.   bool D;
  285.  
  286.   /* Figure G.2 */
  287.   as->A -= pqe->Qe;
  288.   if (
  289. #ifdef SOFTWARE_CONVENTION
  290.       /* Note: I do not think this is correct. See above. */
  291.       (as->C >> 16) < as->A
  292. #else
  293.       !((as->C >> 16) < pqe->Qe)
  294. #endif
  295.       )
  296.     {
  297. #ifndef SOFTWARE_CONVENTION
  298.       as->C -= pqe->Qe << 16;
  299. #endif
  300.       if ((as->A & 0x8000) == 0)
  301.         {
  302.           /* MPS_EXCHANGE, Figure E.16 */
  303.           if (as->A < pqe->Qe)
  304.             {
  305.               D = 1 - (cx >> 7);
  306.               *pcx ^= pqe->lps_xor;
  307.             }
  308.           else
  309.             {
  310.               D = cx >> 7;
  311.               *pcx ^= pqe->mps_xor;
  312.             }
  313.           jbig2_arith_renormd (as);
  314.           return D;
  315.         }
  316.       else
  317.         return cx >> 7;
  318.     }
  319.   else
  320.     {
  321. #ifdef SOFTWARE_CONVENTION
  322.       as->C -= (as->A) << 16;
  323. #endif
  324.       /* LPS_EXCHANGE, Figure E.17 */
  325.       if (as->A < pqe->Qe)
  326.         {
  327.           as->A = pqe->Qe;
  328.           D = cx >> 7;
  329.           *pcx ^= pqe->mps_xor;
  330.         }
  331.       else
  332.         {
  333.           as->A = pqe->Qe;
  334.           D = 1 - (cx >> 7);
  335.           *pcx ^= pqe->lps_xor;
  336.         }
  337.       jbig2_arith_renormd (as);
  338.       return D;
  339.     }
  340. }
  341.  
  342. #ifdef TEST
  343.  
  344. static uint32_t
  345. test_get_word (Jbig2WordStream *self, int offset)
  346. {
  347.   byte stream[] = {
  348.     0x84, 0xC7, 0x3B, 0xFC, 0xE1, 0xA1, 0x43, 0x04, 0x02, 0x20, 0x00, 0x00,
  349.     0x41, 0x0D, 0xBB, 0x86, 0xF4, 0x31, 0x7F, 0xFF, 0x88, 0xFF, 0x37, 0x47,
  350.     0x1A, 0xDB, 0x6A, 0xDF, 0xFF, 0xAC,
  351.     0x00, 0x00
  352.   };
  353.   if (offset >= sizeof(stream))
  354.     return 0;
  355.   else
  356.     return (stream[offset] << 24) | (stream[offset + 1] << 16) |
  357.       (stream[offset + 2] << 8) | stream[offset + 3];
  358. }
  359.  
  360. int
  361. main (int argc, char **argv)
  362. {
  363.   Jbig2Ctx *ctx;
  364.   Jbig2WordStream ws;
  365.   Jbig2ArithState *as;
  366.   int i;
  367.   Jbig2ArithCx cx = 0;
  368.  
  369.   ctx = jbig2_ctx_new(NULL, 0, NULL, NULL, NULL);
  370.  
  371.   ws.get_next_word = test_get_word;
  372.   as = jbig2_arith_new (ctx, &ws);
  373. #ifdef JBIG2_DEBUG_ARITH
  374.   jbig2_arith_trace (as, cx);
  375. #endif
  376.  
  377.   for (i = 0; i < 256; i++)
  378.     {
  379.       bool D;
  380.  
  381.       D = jbig2_arith_decode (as, &cx);
  382. #ifdef JBIG2_DEBUG_ARITH
  383.       fprintf(stderr, "%3d: D = %d, ", i, D);
  384.       jbig2_arith_trace (as, cx);
  385. #endif
  386.     }
  387.  
  388.   jbig2_free(ctx->allocator, as);
  389.  
  390.   jbig2_ctx_free(ctx);
  391.  
  392.   return 0;
  393. }
  394. #endif
  395.