src/lib/openjp2/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 *opj_tgt_create(OPJ_UINT32 numleafsh, OPJ_UINT32 numleafsv) {
  41         OPJ_INT32 nplh[32];
  42         OPJ_INT32 nplv[32];
  43         opj_tgt_node_t *node = 00;
  44         opj_tgt_node_t *l_parent_node = 00;
  45         opj_tgt_node_t *l_parent_node0 = 00;
  46         opj_tgt_tree_t *tree = 00;
  47         OPJ_UINT32 i;
  48         OPJ_INT32  j,k;
  49         OPJ_UINT32 numlvls;
  50         OPJ_UINT32 n;
  51
  52         tree = (opj_tgt_tree_t *) opj_malloc(sizeof(opj_tgt_tree_t));
  53         if(!tree) {
  54                 fprintf(stderr, "ERROR in tgt_create_v2 while allocating tree\n");
  55                 return 00;
  56         }
  57         memset(tree,0,sizeof(opj_tgt_tree_t));
  58
  59         tree->numleafsh = numleafsh;
  60         tree->numleafsv = numleafsv;
  61
  62         numlvls = 0;
  63         nplh[0] = numleafsh;
  64         nplv[0] = numleafsv;
  65         tree->numnodes = 0;
  66         do {
  67                 n = nplh[numlvls] * nplv[numlvls];
  68                 nplh[numlvls + 1] = (nplh[numlvls] + 1) / 2;
  69                 nplv[numlvls + 1] = (nplv[numlvls] + 1) / 2;
  70                 tree->numnodes += n;
  71                 ++numlvls;
  72         } while (n > 1);
  73
  74         /* ADD */
  75         if (tree->numnodes == 0) {
  76                 opj_free(tree);
  77                 fprintf(stderr, "WARNING in tgt_create_v2 tree->numnodes == 0, no tree created.\n");
  78                 return 00;
  79         }
  80
  81         tree->nodes = (opj_tgt_node_t*) opj_calloc(tree->numnodes, sizeof(opj_tgt_node_t));
  82         if(!tree->nodes) {
  83                 fprintf(stderr, "ERROR in tgt_create_v2 while allocating node of the tree\n");
  84                 opj_free(tree);
  85                 return 00;
  86         }
  87         memset(tree->nodes,0,tree->numnodes * sizeof(opj_tgt_node_t));
  88         tree->nodes_size = tree->numnodes * sizeof(opj_tgt_node_t);
  89
  90         node = tree->nodes;
  91         l_parent_node = &tree->nodes[tree->numleafsh * tree->numleafsv];
  92         l_parent_node0 = l_parent_node;
  93
  94         for (i = 0; i < numlvls - 1; ++i) {
  95                 for (j = 0; j < nplv[i]; ++j) {
  96                         k = nplh[i];
  97                         while (--k >= 0) {
  98                                 node->parent = l_parent_node;
  99                                 ++node;
 100                                 if (--k >= 0) {
 101                                         node->parent = l_parent_node;
 102                                         ++node;
 103                                 }
 104                                 ++l_parent_node;
 105                         }
 106                         if ((j & 1) || j == nplv[i] - 1) {
 107                                 l_parent_node0 = l_parent_node;
 108                         } else {
 109                                 l_parent_node = l_parent_node0;
 110                                 l_parent_node0 += nplh[i];
 111                         }
 112                 }
 113         }
 114         node->parent = 0;
 115         opj_tgt_reset(tree);
 116         return tree;
 117 }
 118
 119 /**
 120  * Reinitialises a tag-tree from an exixting one. (V2 framevork)
 121  *
 122  * @param       p_tree                          the tree to reinitialize.
 123  * @param       p_num_leafs_h           the width of the array of leafs of the tree
 124  * @param       p_num_leafs_v           the height of the array of leafs of the tree
 125  * @return      a new tag-tree if successful, NULL otherwise
 126 */
 127 opj_tgt_tree_t *opj_tgt_init(opj_tgt_tree_t * p_tree,OPJ_UINT32 p_num_leafs_h, OPJ_UINT32 p_num_leafs_v)
 128 {
 129         OPJ_INT32 l_nplh[32];
 130         OPJ_INT32 l_nplv[32];
 131         opj_tgt_node_t *l_node = 00;
 132         opj_tgt_node_t *l_parent_node = 00;
 133         opj_tgt_node_t *l_parent_node0 = 00;
 134         OPJ_UINT32 i;
 135         OPJ_INT32 j,k;
 136         OPJ_UINT32 l_num_levels;
 137         OPJ_UINT32 n;
 138         OPJ_UINT32 l_node_size;
 139
 140         if (! p_tree){
 141                 return 00;
 142         }
 143
 144         if ((p_tree->numleafsh != p_num_leafs_h) || (p_tree->numleafsv != p_num_leafs_v)) {
 145                 p_tree->numleafsh = p_num_leafs_h;
 146                 p_tree->numleafsv = p_num_leafs_v;
 147
 148                 l_num_levels = 0;
 149                 l_nplh[0] = p_num_leafs_h;
 150                 l_nplv[0] = p_num_leafs_v;
 151                 p_tree->numnodes = 0;
 152                 do
 153                 {
 154                         n = l_nplh[l_num_levels] * l_nplv[l_num_levels];
 155                         l_nplh[l_num_levels + 1] = (l_nplh[l_num_levels] + 1) / 2;
 156                         l_nplv[l_num_levels + 1] = (l_nplv[l_num_levels] + 1) / 2;
 157                         p_tree->numnodes += n;
 158                         ++l_num_levels;
 159                 }
 160                 while (n > 1);
 161
 162                 /* ADD */
 163                 if (p_tree->numnodes == 0) {
 164                         opj_tgt_destroy(p_tree);
 165                         return 00;
 166                 }
 167                 l_node_size = p_tree->numnodes * sizeof(opj_tgt_node_t);
 168
 169                 if (l_node_size > p_tree->nodes_size) {
 170                         opj_tgt_node_t* new_nodes = (opj_tgt_node_t*) opj_realloc(p_tree->nodes, l_node_size);
 171                         if (! p_tree->nodes) {
 172                                 fprintf(stderr, "ERROR Not enough memory to reinitialize the tag tree\n");
 173                                 opj_tgt_destroy(p_tree);
 174                                 return 00;
 175                         }
 176                         p_tree->nodes = new_nodes;
 177                         memset(((char *) p_tree->nodes) + p_tree->nodes_size, 0 , l_node_size - p_tree->nodes_size);
 178                         p_tree->nodes_size = l_node_size;
 179                 }
 180                 l_node = p_tree->nodes;
 181                 l_parent_node = &p_tree->nodes[p_tree->numleafsh * p_tree->numleafsv];
 182                 l_parent_node0 = l_parent_node;
 183
 184                 for (i = 0; i < l_num_levels - 1; ++i) {
 185                         for (j = 0; j < l_nplv[i]; ++j) {
 186                                 k = l_nplh[i];
 187                                 while (--k >= 0) {
 188                                         l_node->parent = l_parent_node;
 189                                         ++l_node;
 190                                         if (--k >= 0) {
 191                                                 l_node->parent = l_parent_node;
 192                                                 ++l_node;
 193                                         }
 194                                         ++l_parent_node;
 195                                         }
 196                                 if ((j & 1) || j == l_nplv[i] - 1)
 197                                 {
 198                                         l_parent_node0 = l_parent_node;
 199                                 }
 200                                 else
 201                                 {
 202                                         l_parent_node = l_parent_node0;
 203                                         l_parent_node0 += l_nplh[i];
 204                                 }
 205                         }
 206                 }
 207                 l_node->parent = 0;
 208         }
 209         opj_tgt_reset(p_tree);
 210
 211         return p_tree;
 212 }
 213
 214 void opj_tgt_destroy(opj_tgt_tree_t *p_tree)
 215 {
 216         if (! p_tree) {
 217                 return;
 218         }
 219
 220         if (p_tree->nodes) {
 221                 opj_free(p_tree->nodes);
 222                 p_tree->nodes = 00;
 223         }
 224         opj_free(p_tree);
 225 }
 226
 227 void opj_tgt_reset(opj_tgt_tree_t *p_tree) {
 228         OPJ_UINT32 i;
 229         opj_tgt_node_t * l_current_node = 00;;
 230
 231         if (! p_tree) {
 232                 return;
 233         }
 234
 235         l_current_node = p_tree->nodes;
 236         for     (i = 0; i < p_tree->numnodes; ++i)
 237         {
 238                 l_current_node->value = 999;
 239                 l_current_node->low = 0;
 240                 l_current_node->known = 0;
 241                 ++l_current_node;
 242         }
 243 }
 244
 245 void opj_tgt_setvalue(opj_tgt_tree_t *tree, OPJ_UINT32 leafno, OPJ_INT32 value) {
 246         opj_tgt_node_t *node;
 247         node = &tree->nodes[leafno];
 248         while (node && node->value > value) {
 249                 node->value = value;
 250                 node = node->parent;
 251         }
 252 }
 253
 254 void opj_tgt_encode(opj_bio_t *bio, opj_tgt_tree_t *tree, OPJ_UINT32 leafno, OPJ_INT32 threshold) {
 255         opj_tgt_node_t *stk[31];
 256         opj_tgt_node_t **stkptr;
 257         opj_tgt_node_t *node;
 258         OPJ_INT32 low;
 259
 260         stkptr = stk;
 261         node = &tree->nodes[leafno];
 262         while (node->parent) {
 263                 *stkptr++ = node;
 264                 node = node->parent;
 265         }
 266
 267         low = 0;
 268         for (;;) {
 269                 if (low > node->low) {
 270                         node->low = low;
 271                 } else {
 272                         low = node->low;
 273                 }
 274
 275                 while (low < threshold) {
 276                         if (low >= node->value) {
 277                                 if (!node->known) {
 278                                         opj_bio_write(bio, 1, 1);
 279                                         node->known = 1;
 280                                 }
 281                                 break;
 282                         }
 283                         opj_bio_write(bio, 0, 1);
 284                         ++low;
 285                 }
 286
 287                 node->low = low;
 288                 if (stkptr == stk)
 289                         break;
 290                 node = *--stkptr;
 291         }
 292 }
 293
 294 OPJ_UINT32 opj_tgt_decode(opj_bio_t *bio, opj_tgt_tree_t *tree, OPJ_UINT32 leafno, OPJ_INT32 threshold) {
 295         opj_tgt_node_t *stk[31];
 296         opj_tgt_node_t **stkptr;
 297         opj_tgt_node_t *node;
 298         OPJ_INT32 low;
 299
 300         stkptr = stk;
 301         node = &tree->nodes[leafno];
 302         while (node->parent) {
 303                 *stkptr++ = node;
 304                 node = node->parent;
 305         }
 306
 307         low = 0;
 308         for (;;) {
 309                 if (low > node->low) {
 310                         node->low = low;
 311                 } else {
 312                         low = node->low;
 313                 }
 314                 while (low < threshold && low < node->value) {
 315                         if (opj_bio_read(bio, 1)) {
 316                                 node->value = low;
 317                         } else {
 318                                 ++low;
 319                         }
 320                 }
 321                 node->low = low;
 322                 if (stkptr == stk) {
 323                         break;
 324                 }
 325                 node = *--stkptr;
 326         }
 327
 328         return (node->value < threshold) ? 1 : 0;
 329 }