libopenjpeg/tgt.c

   1 /*
   2  * Copyright (c) 2002-2007, Communications and Remote Sensing Laboratory, Universite catholique de Louvain (UCL), Belgium
   3  * Copyright (c) 2002-2007, Professor Benoit Macq
   4  * Copyright (c) 2001-2003, David Janssens
   5  * Copyright (c) 2002-2003, Yannick Verschueren
   6  * Copyright (c) 2003-2007, Francois-Olivier Devaux and Antonin Descampe
   7  * Copyright (c) 2005, Herve Drolon, FreeImage Team
   8  * All rights reserved.
   9  *
  10  * Redistribution and use in source and binary forms, with or without
  11  * modification, are permitted provided that the following conditions
  12  * are met:
  13  * 1. Redistributions of source code must retain the above copyright
  14  *    notice, this list of conditions and the following disclaimer.
  15  * 2. Redistributions in binary form must reproduce the above copyright
  16  *    notice, this list of conditions and the following disclaimer in the
  17  *    documentation and/or other materials provided with the distribution.
  18  *
  19  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS `AS IS'
  20  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  22  * ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
  23  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  24  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  25  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  26  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  27  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  28  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  29  * POSSIBILITY OF SUCH DAMAGE.
  30  */
  31
  32 #include "opj_includes.h"
  33
  34 /*
  35 ==========================================================
  36    Tag-tree coder interface
  37 ==========================================================
  38 */
  39
  40 opj_tgt_tree_t *tgt_create(int numleafsh, int numleafsv) {
  41         int nplh[32];
  42         int nplv[32];
  43         opj_tgt_node_t *node = NULL;
  44         opj_tgt_node_t *parentnode = NULL;
  45         opj_tgt_node_t *parentnode0 = NULL;
  46         opj_tgt_tree_t *tree = NULL;
  47         int i, j, k;
  48         int numlvls;
  49         int n;
  50
  51         tree = (opj_tgt_tree_t *) opj_malloc(sizeof(opj_tgt_tree_t));
  52         if(!tree) return NULL;
  53         tree->numleafsh = numleafsh;
  54         tree->numleafsv = numleafsv;
  55
  56         numlvls = 0;
  57         nplh[0] = numleafsh;
  58         nplv[0] = numleafsv;
  59         tree->numnodes = 0;
  60         do {
  61                 n = nplh[numlvls] * nplv[numlvls];
  62                 nplh[numlvls + 1] = (nplh[numlvls] + 1) / 2;
  63                 nplv[numlvls + 1] = (nplv[numlvls] + 1) / 2;
  64                 tree->numnodes += n;
  65                 ++numlvls;
  66         } while (n > 1);
  67
  68         /* ADD */
  69         if (tree->numnodes == 0) {
  70                 opj_free(tree);
  71                 return NULL;
  72         }
  73
  74         tree->nodes = (opj_tgt_node_t*) opj_calloc(tree->numnodes, sizeof(opj_tgt_node_t));
  75         if(!tree->nodes) {
  76                 opj_free(tree);
  77                 return NULL;
  78         }
  79
  80         node = tree->nodes;
  81         parentnode = &tree->nodes[tree->numleafsh * tree->numleafsv];
  82         parentnode0 = parentnode;
  83
  84         for (i = 0; i < numlvls - 1; ++i) {
  85                 for (j = 0; j < nplv[i]; ++j) {
  86                         k = nplh[i];
  87                         while (--k >= 0) {
  88                                 node->parent = parentnode;
  89                                 ++node;
  90                                 if (--k >= 0) {
  91                                         node->parent = parentnode;
  92                                         ++node;
  93                                 }
  94                                 ++parentnode;
  95                         }
  96                         if ((j & 1) || j == nplv[i] - 1) {
  97                                 parentnode0 = parentnode;
  98                         } else {
  99                                 parentnode = parentnode0;
 100                                 parentnode0 += nplh[i];
 101                         }
 102                 }
 103         }
 104         node->parent = 0;
 105
 106         tgt_reset(tree);
 107
 108         return tree;
 109 }
 110
 111 /**
 112  * Reinitialises a tag-tree from an exixting one.
 113  *
 114  * @param       p_tree                          the tree to reinitialize.
 115  * @param       p_num_leafs_h           the width of the array of leafs of the tree
 116  * @param       p_num_leafs_v           the height of the array of leafs of the tree
 117  * @return      a new tag-tree if successful, NULL otherwise
 118 */
 119 opj_tgt_tree_t *tgt_init(opj_tgt_tree_t * p_tree,OPJ_UINT32 p_num_leafs_h, OPJ_UINT32 p_num_leafs_v)
 120 {
 121         OPJ_INT32 l_nplh[32];
 122         OPJ_INT32 l_nplv[32];
 123         opj_tgt_node_t *l_node = 00;
 124         opj_tgt_node_t *l_parent_node = 00;
 125         opj_tgt_node_t *l_parent_node0 = 00;
 126         OPJ_UINT32 i;
 127         OPJ_INT32 j,k;
 128         OPJ_UINT32 l_num_levels;
 129         OPJ_UINT32 n;
 130         OPJ_UINT32 l_node_size;
 131
 132         if
 133                 (! p_tree)
 134         {
 135                 return 00;
 136         }
 137         if
 138                 ((p_tree->numleafsh != p_num_leafs_h) || (p_tree->numleafsv != p_num_leafs_v))
 139         {
 140                 p_tree->numleafsh = p_num_leafs_h;
 141                 p_tree->numleafsv = p_num_leafs_v;
 142
 143                 l_num_levels = 0;
 144                 l_nplh[0] = p_num_leafs_h;
 145                 l_nplv[0] = p_num_leafs_v;
 146                 p_tree->numnodes = 0;
 147                 do
 148                 {
 149                         n = l_nplh[l_num_levels] * l_nplv[l_num_levels];
 150                         l_nplh[l_num_levels + 1] = (l_nplh[l_num_levels] + 1) / 2;
 151                         l_nplv[l_num_levels + 1] = (l_nplv[l_num_levels] + 1) / 2;
 152                         p_tree->numnodes += n;
 153                         ++l_num_levels;
 154                 }
 155                 while (n > 1);
 156
 157                 /* ADD */
 158                 if
 159                         (p_tree->numnodes == 0)
 160                 {
 161                         tgt_destroy(p_tree);
 162             return 00;
 163                 }
 164                 l_node_size = p_tree->numnodes * sizeof(opj_tgt_node_t);
 165                 if
 166                         (l_node_size > p_tree->nodes_size)
 167                 {
 168                         p_tree->nodes = (opj_tgt_node_t*) opj_realloc(p_tree->nodes, l_node_size);
 169                         if
 170                                 (! p_tree->nodes)
 171                         {
 172                                 tgt_destroy(p_tree);
 173                                 return 00;
 174                         }
 175                         memset(((char *) p_tree->nodes) + p_tree->nodes_size, 0 , l_node_size - p_tree->nodes_size);
 176                         p_tree->nodes_size = l_node_size;
 177                 }
 178                 l_node = p_tree->nodes;
 179                 l_parent_node = &p_tree->nodes[p_tree->numleafsh * p_tree->numleafsv];
 180                 l_parent_node0 = l_parent_node;
 181
 182                 for
 183                         (i = 0; i < l_num_levels - 1; ++i)
 184                 {
 185                         for
 186                                 (j = 0; j < l_nplv[i]; ++j)
 187                         {
 188                                 k = l_nplh[i];
 189                                 while
 190                                         (--k >= 0)
 191                                 {
 192                                         l_node->parent = l_parent_node;
 193                                         ++l_node;
 194                                         if (--k >= 0)
 195                                         {
 196                                                 l_node->parent = l_parent_node;
 197                                                 ++l_node;
 198                                         }
 199                                         ++l_parent_node;
 200                                 }
 201                                 if ((j & 1) || j == l_nplv[i] - 1)
 202                                 {
 203                                         l_parent_node0 = l_parent_node;
 204                                 }
 205                                 else
 206                                 {
 207                                         l_parent_node = l_parent_node0;
 208                                         l_parent_node0 += l_nplh[i];
 209                                 }
 210                         }
 211                 }
 212                 l_node->parent = 0;
 213         }
 214         tgt_reset(p_tree);
 215
 216         return p_tree;
 217 }
 218
 219 void tgt_destroy(opj_tgt_tree_t *tree) {
 220         opj_free(tree->nodes);
 221         opj_free(tree);
 222 }
 223
 224 void tgt_reset(opj_tgt_tree_t *tree) {
 225         int i;
 226
 227         if (NULL == tree)
 228                 return;
 229
 230         for (i = 0; i < tree->numnodes; i++) {
 231                 tree->nodes[i].value = 999;
 232                 tree->nodes[i].low = 0;
 233                 tree->nodes[i].known = 0;
 234         }
 235 }
 236
 237 void tgt_setvalue(opj_tgt_tree_t *tree, int leafno, int value) {
 238         opj_tgt_node_t *node;
 239         node = &tree->nodes[leafno];
 240         while (node && node->value > value) {
 241                 node->value = value;
 242                 node = node->parent;
 243         }
 244 }
 245
 246 void tgt_encode(opj_bio_t *bio, opj_tgt_tree_t *tree, int leafno, int threshold) {
 247         opj_tgt_node_t *stk[31];
 248         opj_tgt_node_t **stkptr;
 249         opj_tgt_node_t *node;
 250         int low;
 251
 252         stkptr = stk;
 253         node = &tree->nodes[leafno];
 254         while (node->parent) {
 255                 *stkptr++ = node;
 256                 node = node->parent;
 257         }
 258
 259         low = 0;
 260         for (;;) {
 261                 if (low > node->low) {
 262                         node->low = low;
 263                 } else {
 264                         low = node->low;
 265                 }
 266
 267                 while (low < threshold) {
 268                         if (low >= node->value) {
 269                                 if (!node->known) {
 270                                         bio_write(bio, 1, 1);
 271                                         node->known = 1;
 272                                 }
 273                                 break;
 274                         }
 275                         bio_write(bio, 0, 1);
 276                         ++low;
 277                 }
 278
 279                 node->low = low;
 280                 if (stkptr == stk)
 281                         break;
 282                 node = *--stkptr;
 283         }
 284 }
 285
 286 int tgt_decode(opj_bio_t *bio, opj_tgt_tree_t *tree, int leafno, int threshold) {
 287         opj_tgt_node_t *stk[31];
 288         opj_tgt_node_t **stkptr;
 289         opj_tgt_node_t *node;
 290         int low;
 291
 292         stkptr = stk;
 293         node = &tree->nodes[leafno];
 294         while (node->parent) {
 295                 *stkptr++ = node;
 296                 node = node->parent;
 297         }
 298
 299         low = 0;
 300         for (;;) {
 301                 if (low > node->low) {
 302                         node->low = low;
 303                 } else {
 304                         low = node->low;
 305                 }
 306                 while (low < threshold && low < node->value) {
 307                         if (bio_read(bio, 1)) {
 308                                 node->value = low;
 309                         } else {
 310                                 ++low;
 311                         }
 312                 }
 313                 node->low = low;
 314                 if (stkptr == stk) {
 315                         break;
 316                 }
 317                 node = *--stkptr;
 318         }
 319
 320         return (node->value < threshold) ? 1 : 0;
 321 }