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