libjp3dvm/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, Herve 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 void tgt_tree_dump (FILE *fd, opj_tgt_tree_t * tree){\r
  39         int nodesno;\r
  40 \r
  41         fprintf(fd, "TGT_TREE {\n");\r
  42         fprintf(fd, "  numnodes: %d \n", tree->numnodes);       \r
  43         fprintf(fd, "  numleafsh: %d, numleafsv: %d, numleafsz: %d,\n", tree->numleafsh, tree->numleafsv, tree->numleafsz);\r
  44 \r
  45         for (nodesno = 0; nodesno < tree->numnodes; nodesno++) {\r
  46                 fprintf(fd, "tgt_node %d {\n", nodesno);\r
  47                 fprintf(fd, "  value: %d \n", tree->nodes[nodesno].value);\r
  48                 fprintf(fd, "  low: %d \n", tree->nodes[nodesno].low);\r
  49                 fprintf(fd, "  known: %d \n", tree->nodes[nodesno].known);\r
  50                 if (tree->nodes[nodesno].parent) {\r
  51                         fprintf(fd, "  parent.value: %d \n", tree->nodes[nodesno].parent->value);\r
  52                         fprintf(fd, "  parent.low: %d \n", tree->nodes[nodesno].parent->low);\r
  53                         fprintf(fd, "  parent.known: %d \n", tree->nodes[nodesno].parent->known);\r
  54                 }\r
  55                 fprintf(fd, "}\n");\r
  56 \r
  57         }\r
  58         fprintf(fd, "}\n");\r
  59 \r
  60 }\r
  61 \r
  62 \r
  63 opj_tgt_tree_t *tgt_create(int numleafsh, int numleafsv, int numleafsz) {\r
  64         \r
  65         int nplh[32];\r
  66         int nplv[32];\r
  67         int nplz[32];\r
  68         opj_tgt_node_t *node = NULL;\r
  69         opj_tgt_node_t *parentnode = NULL;\r
  70         opj_tgt_node_t *parentnode0 = NULL;\r
  71         opj_tgt_tree_t *tree = NULL;\r
  72         int i, j, k, p, p0;\r
  73         int numlvls;\r
  74         int n, z = 0;\r
  75 \r
  76         tree = (opj_tgt_tree_t *) opj_malloc(sizeof(opj_tgt_tree_t));\r
  77         if(!tree) \r
  78                 return NULL;\r
  79         tree->numleafsh = numleafsh;\r
  80         tree->numleafsv = numleafsv;\r
  81         tree->numleafsz = numleafsz;\r
  82 \r
  83         numlvls = 0;\r
  84         nplh[0] = numleafsh;\r
  85         nplv[0] = numleafsv;\r
  86         nplz[0] = numleafsz;\r
  87         tree->numnodes = 0;\r
  88         do {\r
  89                 n = nplh[numlvls] * nplv[numlvls] * nplz[numlvls]; \r
  90                 nplh[numlvls + 1] = (nplh[numlvls] + 1) / 2;\r
  91                 nplv[numlvls + 1] = (nplv[numlvls] + 1) / 2;\r
  92                 nplz[numlvls + 1] = (nplz[numlvls] + 1) / 2;\r
  93                 tree->numnodes += n;\r
  94                 ++numlvls;\r
  95         } while (n > 1);\r
  96 \r
  97         if (tree->numnodes == 0) {\r
  98                 opj_free(tree);\r
  99                 return NULL;\r
 100         }\r
 101 \r
 102         tree->nodes = (opj_tgt_node_t *) opj_malloc(tree->numnodes * sizeof(opj_tgt_node_t));\r
 103         if(!tree->nodes) {\r
 104                 opj_free(tree);\r
 105                 return NULL;\r
 106         }\r
 107 \r
 108         node = tree->nodes;\r
 109         parentnode = &tree->nodes[tree->numleafsh * tree->numleafsv * tree->numleafsz];\r
 110         parentnode0 = parentnode;\r
 111                 \r
 112         p = tree->numleafsh * tree->numleafsv * tree->numleafsz;\r
 113         p0 = p;\r
 114         n = 0;\r
 115         //fprintf(stdout,"\nH %d V %d Z %d numlvls %d nodes %d\n",tree->numleafsh,tree->numleafsv,tree->numleafsz,numlvls,tree->numnodes);\r
 116         for (i = 0; i < numlvls - 1; ++i) {\r
 117                 for (j = 0; j < nplv[i]; ++j) {\r
 118                         k = nplh[i]*nplz[i];\r
 119                         while (--k >= 0) {\r
 120                                 node->parent = parentnode;              //fprintf(stdout,"node[%d].parent = node[%d]\n",n,p);\r
 121                                 ++node; ++n;            \r
 122                                 if (--k >= 0 && n < p) {\r
 123                                         node->parent = parentnode;      //fprintf(stdout,"node[%d].parent = node[%d]\n",n,p);\r
 124                                         ++node; ++n;    \r
 125                                 }\r
 126                                 if (nplz[i] != 1){ //2D operation vs 3D operation\r
 127                                         if (--k >= 0 && n < p) {\r
 128                                                 node->parent = parentnode;      //fprintf(stdout,"node[%d].parent = node[%d]\n",n,p);\r
 129                                                 ++node; ++n;\r
 130                                         }\r
 131                                         if (--k >= 0 && n < p) {\r
 132                                                 node->parent = parentnode;      //fprintf(stdout,"node[%d].parent = node[%d]\n",n,p);\r
 133                                                 ++node; ++n;\r
 134                                         }\r
 135                                 }\r
 136                                 ++parentnode; ++p;\r
 137                         }\r
 138                         if ((j & 1) || j == nplv[i] - 1) {\r
 139                                 parentnode0 = parentnode;                       p0 = p;         //fprintf(stdout,"parent = node[%d] \n",p);\r
 140                         } else {\r
 141                                 parentnode = parentnode0;                       p = p0;         //fprintf(stdout,"parent = node[%d] \n",p);\r
 142                                 parentnode0 += nplh[i]*nplz[i];         p0 += nplh[i]*nplz[i];\r
 143                         }\r
 144                 }\r
 145         }\r
 146         node->parent = 0;\r
 147 \r
 148         \r
 149         tgt_reset(tree);\r
 150 \r
 151         return tree;\r
 152 }\r
 153 \r
 154 void tgt_destroy(opj_tgt_tree_t *tree) {\r
 155         opj_free(tree->nodes);\r
 156         opj_free(tree);\r
 157 }\r
 158 \r
 159 void tgt_reset(opj_tgt_tree_t *tree) {\r
 160         int i;\r
 161 \r
 162         if (NULL == tree)\r
 163                 return;\r
 164         \r
 165         for (i = 0; i < tree->numnodes; i++) {\r
 166                 tree->nodes[i].value = 999;\r
 167                 tree->nodes[i].low = 0;\r
 168                 tree->nodes[i].known = 0;\r
 169         }\r
 170 }\r
 171 \r
 172 void tgt_setvalue(opj_tgt_tree_t *tree, int leafno, int value) {\r
 173         opj_tgt_node_t *node;\r
 174         node = &tree->nodes[leafno];\r
 175         while (node && node->value > value) {\r
 176                 node->value = value;\r
 177                 node = node->parent;\r
 178         }\r
 179 }\r
 180 \r
 181 void tgt_encode(opj_bio_t *bio, opj_tgt_tree_t *tree, int leafno, int threshold) {\r
 182         opj_tgt_node_t *stk[31];\r
 183         opj_tgt_node_t **stkptr;\r
 184         opj_tgt_node_t *node;\r
 185         int low;\r
 186 \r
 187         stkptr = stk;\r
 188         node = &tree->nodes[leafno];\r
 189         while (node->parent) {\r
 190                 *stkptr++ = node;\r
 191                 node = node->parent;\r
 192         }\r
 193         \r
 194         low = 0;\r
 195         for (;;) {\r
 196                 if (low > node->low) {\r
 197                         node->low = low;\r
 198                 } else {\r
 199                         low = node->low;\r
 200                 }\r
 201                 \r
 202                 while (low < threshold) {\r
 203                         if (low >= node->value) {\r
 204                                 if (!node->known) {\r
 205                                         bio_write(bio, 1, 1);\r
 206                                         node->known = 1;\r
 207                                 }\r
 208                                 break;\r
 209                         }\r
 210                         bio_write(bio, 0, 1);\r
 211                         ++low;\r
 212                 }\r
 213                 \r
 214                 node->low = low;\r
 215                 if (stkptr == stk)\r
 216                         break;\r
 217                 node = *--stkptr;\r
 218         }\r
 219 }\r
 220 \r
 221 int tgt_decode(opj_bio_t *bio, opj_tgt_tree_t *tree, int leafno, int threshold) {\r
 222         opj_tgt_node_t *stk[31];\r
 223         opj_tgt_node_t **stkptr;\r
 224         opj_tgt_node_t *node;\r
 225         int low;\r
 226 \r
 227         stkptr = stk;\r
 228         node = &tree->nodes[leafno];\r
 229         while (node->parent) {\r
 230                 *stkptr++ = node;\r
 231                 node = node->parent;\r
 232         }\r
 233         \r
 234         low = 0;\r
 235         for (;;) {\r
 236                 if (low > node->low) {\r
 237                         node->low = low;\r
 238                 } else {\r
 239                         low = node->low;\r
 240                 }\r
 241                 while (low < threshold && low < node->value) {\r
 242                         if (bio_read(bio, 1)) {\r
 243                                 node->value = low;\r
 244                         } else {\r
 245                                 ++low;\r
 246                         }\r
 247                 }\r
 248                 node->low = low;\r
 249                 if (stkptr == stk) {\r
 250                         break;\r
 251                 }\r
 252                 node = *--stkptr;\r
 253         }\r
 254         \r
 255         return (node->value < threshold) ? 1 : 0;\r
 256 }\r