src/gdcmopenjpeg/libopenjpeg/tgt.c

   1 /*\r
   2  * Copyright (c) 2001-2003, David Janssens\r
   3  * Copyright (c) 2002-2003, Yannick Verschueren\r
   4  * Copyright (c) 2003-2005, Francois Devaux and Antonin Descampe\r
   5  * Copyright (c) 2005, Hervé Drolon, FreeImage Team\r
   6  * Copyright (c) 2002-2005, Communications and remote sensing Laboratory, Universite catholique de Louvain, Belgium\r
   7  * All rights reserved.\r
   8  *\r
   9  * Redistribution and use in source and binary forms, with or without\r
  10  * modification, are permitted provided that the following conditions\r
  11  * are met:\r
  12  * 1. Redistributions of source code must retain the above copyright\r
  13  *    notice, this list of conditions and the following disclaimer.\r
  14  * 2. Redistributions in binary form must reproduce the above copyright\r
  15  *    notice, this list of conditions and the following disclaimer in the\r
  16  *    documentation and/or other materials provided with the distribution.\r
  17  *\r
  18  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS `AS IS'\r
  19  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE\r
  20  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE\r
  21  * ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE\r
  22  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR\r
  23  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF\r
  24  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS\r
  25  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN\r
  26  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)\r
  27  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE\r
  28  * POSSIBILITY OF SUCH DAMAGE.\r
  29  */\r
  30 \r
  31 #include "opj_includes.h"\r
  32 \r
  33 /* \r
  34 ==========================================================\r
  35    Tag-tree coder interface\r
  36 ==========================================================\r
  37 */\r
  38 \r
  39 opj_tgt_tree_t *tgt_create(int numleafsh, int numleafsv) {\r
  40   int nplh[32];\r
  41   int nplv[32];\r
  42   opj_tgt_node_t *node = NULL;\r
  43   opj_tgt_node_t *parentnode = NULL;\r
  44   opj_tgt_node_t *parentnode0 = NULL;\r
  45   opj_tgt_tree_t *tree = NULL;\r
  46   int i, j, k;\r
  47   int numlvls;\r
  48   int n;\r
  49 \r
  50   tree = (opj_tgt_tree_t *) opj_malloc(sizeof(opj_tgt_tree_t));\r
  51   if(!tree) return NULL;\r
  52   tree->numleafsh = numleafsh;\r
  53   tree->numleafsv = numleafsv;\r
  54 \r
  55   numlvls = 0;\r
  56   nplh[0] = numleafsh;\r
  57   nplv[0] = numleafsv;\r
  58   tree->numnodes = 0;\r
  59   do {\r
  60     n = nplh[numlvls] * nplv[numlvls];\r
  61     nplh[numlvls + 1] = (nplh[numlvls] + 1) / 2;\r
  62     nplv[numlvls + 1] = (nplv[numlvls] + 1) / 2;\r
  63     tree->numnodes += n;\r
  64     ++numlvls;\r
  65   } while (n > 1);\r
  66   \r
  67   /* ADD */\r
  68   if (tree->numnodes == 0) {\r
  69     opj_free(tree);\r
  70     return NULL;\r
  71   }\r
  72 \r
  73   tree->nodes = (opj_tgt_node_t *) opj_malloc(tree->numnodes * sizeof(opj_tgt_node_t));\r
  74   if(!tree->nodes) {\r
  75     opj_free(tree);\r
  76     return NULL;\r
  77   }\r
  78 \r
  79   node = tree->nodes;\r
  80   parentnode = &tree->nodes[tree->numleafsh * tree->numleafsv];\r
  81   parentnode0 = parentnode;\r
  82   \r
  83   for (i = 0; i < numlvls - 1; ++i) {\r
  84     for (j = 0; j < nplv[i]; ++j) {\r
  85       k = nplh[i];\r
  86       while (--k >= 0) {\r
  87         node->parent = parentnode;\r
  88         ++node;\r
  89         if (--k >= 0) {\r
  90           node->parent = parentnode;\r
  91           ++node;\r
  92         }\r
  93         ++parentnode;\r
  94       }\r
  95       if ((j & 1) || j == nplv[i] - 1) {\r
  96         parentnode0 = parentnode;\r
  97       } else {\r
  98         parentnode = parentnode0;\r
  99         parentnode0 += nplh[i];\r
 100       }\r
 101     }\r
 102   }\r
 103   node->parent = 0;\r
 104   \r
 105   tgt_reset(tree);\r
 106   \r
 107   return tree;\r
 108 }\r
 109 \r
 110 void tgt_destroy(opj_tgt_tree_t *tree) {\r
 111   opj_free(tree->nodes);\r
 112   opj_free(tree);\r
 113 }\r
 114 \r
 115 void tgt_reset(opj_tgt_tree_t *tree) {\r
 116   int i;\r
 117 \r
 118   if (NULL == tree)\r
 119     return;\r
 120   \r
 121   for (i = 0; i < tree->numnodes; i++) {\r
 122     tree->nodes[i].value = 999;\r
 123     tree->nodes[i].low = 0;\r
 124     tree->nodes[i].known = 0;\r
 125   }\r
 126 }\r
 127 \r
 128 void tgt_setvalue(opj_tgt_tree_t *tree, int leafno, int value) {\r
 129   opj_tgt_node_t *node;\r
 130   node = &tree->nodes[leafno];\r
 131   while (node && node->value > value) {\r
 132     node->value = value;\r
 133     node = node->parent;\r
 134   }\r
 135 }\r
 136 \r
 137 void tgt_encode(opj_bio_t *bio, opj_tgt_tree_t *tree, int leafno, int threshold) {\r
 138   opj_tgt_node_t *stk[31];\r
 139   opj_tgt_node_t **stkptr;\r
 140   opj_tgt_node_t *node;\r
 141   int low;\r
 142 \r
 143   stkptr = stk;\r
 144   node = &tree->nodes[leafno];\r
 145   while (node->parent) {\r
 146     *stkptr++ = node;\r
 147     node = node->parent;\r
 148   }\r
 149   \r
 150   low = 0;\r
 151   for (;;) {\r
 152     if (low > node->low) {\r
 153       node->low = low;\r
 154     } else {\r
 155       low = node->low;\r
 156     }\r
 157     \r
 158     while (low < threshold) {\r
 159       if (low >= node->value) {\r
 160         if (!node->known) {\r
 161           bio_write(bio, 1, 1);\r
 162           node->known = 1;\r
 163         }\r
 164         break;\r
 165       }\r
 166       bio_write(bio, 0, 1);\r
 167       ++low;\r
 168     }\r
 169     \r
 170     node->low = low;\r
 171     if (stkptr == stk)\r
 172       break;\r
 173     node = *--stkptr;\r
 174   }\r
 175 }\r
 176 \r
 177 int tgt_decode(opj_bio_t *bio, opj_tgt_tree_t *tree, int leafno, int threshold) {\r
 178   opj_tgt_node_t *stk[31];\r
 179   opj_tgt_node_t **stkptr;\r
 180   opj_tgt_node_t *node;\r
 181   int low;\r
 182 \r
 183   stkptr = stk;\r
 184   node = &tree->nodes[leafno];\r
 185   while (node->parent) {\r
 186     *stkptr++ = node;\r
 187     node = node->parent;\r
 188   }\r
 189   \r
 190   low = 0;\r
 191   for (;;) {\r
 192     if (low > node->low) {\r
 193       node->low = low;\r
 194     } else {\r
 195       low = node->low;\r
 196     }\r
 197     while (low < threshold && low < node->value) {\r
 198       if (bio_read(bio, 1)) {\r
 199         node->value = low;\r
 200       } else {\r
 201         ++low;\r
 202       }\r
 203     }\r
 204     node->low = low;\r
 205     if (stkptr == stk) {\r
 206       break;\r
 207     }\r
 208     node = *--stkptr;\r
 209   }\r
 210   \r
 211   return (node->value < threshold) ? 1 : 0;\r
 212 }\r