mj2/libopenjpeg_097/tgt.c

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