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 opj_tgt_tree_t *tgt_create_v2(OPJ_UINT32 numleafsh, OPJ_UINT32 numleafsv) {
 112         OPJ_INT32 nplh[32];
 113         OPJ_INT32 nplv[32];
 114         opj_tgt_node_t *node = 00;
 115         opj_tgt_node_t *l_parent_node = 00;
 116         opj_tgt_node_t *l_parent_node0 = 00;
 117         opj_tgt_tree_t *tree = 00;
 118         OPJ_UINT32 i;
 119         OPJ_INT32  j,k;
 120         OPJ_UINT32 numlvls;
 121         OPJ_UINT32 n;
 122
 123         tree = (opj_tgt_tree_t *) opj_malloc(sizeof(opj_tgt_tree_t));
 124         if(!tree) {
 125                 fprintf(stderr, "ERROR in tgt_create_v2 while allocating tree\n");
 126                 return 00;
 127         }
 128         memset(tree,0,sizeof(opj_tgt_tree_t));
 129
 130         tree->numleafsh = numleafsh;
 131         tree->numleafsv = numleafsv;
 132
 133         numlvls = 0;
 134         nplh[0] = numleafsh;
 135         nplv[0] = numleafsv;
 136         tree->numnodes = 0;
 137         do {
 138                 n = nplh[numlvls] * nplv[numlvls];
 139                 nplh[numlvls + 1] = (nplh[numlvls] + 1) / 2;
 140                 nplv[numlvls + 1] = (nplv[numlvls] + 1) / 2;
 141                 tree->numnodes += n;
 142                 ++numlvls;
 143         } while (n > 1);
 144
 145         /* ADD */
 146         if (tree->numnodes == 0) {
 147                 opj_free(tree);
 148                 fprintf(stderr, "WARNING in tgt_create_v2 tree->numnodes == 0, no tree created.\n");
 149                 return 00;
 150         }
 151
 152         tree->nodes = (opj_tgt_node_t*) opj_calloc(tree->numnodes, sizeof(opj_tgt_node_t));
 153         if(!tree->nodes) {
 154                 fprintf(stderr, "ERROR in tgt_create_v2 while allocating node of the tree\n");
 155                 opj_free(tree);
 156                 return 00;
 157         }
 158         memset(tree->nodes,0,tree->numnodes * sizeof(opj_tgt_node_t));
 159         tree->nodes_size = tree->numnodes * sizeof(opj_tgt_node_t);
 160
 161         node = tree->nodes;
 162         l_parent_node = &tree->nodes[tree->numleafsh * tree->numleafsv];
 163         l_parent_node0 = l_parent_node;
 164
 165         for (i = 0; i < numlvls - 1; ++i) {
 166                 for (j = 0; j < nplv[i]; ++j) {
 167                         k = nplh[i];
 168                         while (--k >= 0) {
 169                                 node->parent = l_parent_node;
 170                                 ++node;
 171                                 if (--k >= 0) {
 172                                         node->parent = l_parent_node;
 173                                         ++node;
 174                                 }
 175                                 ++l_parent_node;
 176                         }
 177                         if ((j & 1) || j == nplv[i] - 1) {
 178                                 l_parent_node0 = l_parent_node;
 179                         } else {
 180                                 l_parent_node = l_parent_node0;
 181                                 l_parent_node0 += nplh[i];
 182                         }
 183                 }
 184         }
 185         node->parent = 0;
 186         tgt_reset(tree);
 187         return tree;
 188 }
 189
 190 /**
 191  * Reinitialises a tag-tree from an exixting one. (V2 framevork)
 192  *
 193  * @param       p_tree                          the tree to reinitialize.
 194  * @param       p_num_leafs_h           the width of the array of leafs of the tree
 195  * @param       p_num_leafs_v           the height of the array of leafs of the tree
 196  * @return      a new tag-tree if successful, NULL otherwise
 197 */
 198 opj_tgt_tree_t *tgt_init(opj_tgt_tree_t * p_tree,OPJ_UINT32 p_num_leafs_h, OPJ_UINT32 p_num_leafs_v)
 199 {
 200         OPJ_INT32 l_nplh[32];
 201         OPJ_INT32 l_nplv[32];
 202         opj_tgt_node_t *l_node = 00;
 203         opj_tgt_node_t *l_parent_node = 00;
 204         opj_tgt_node_t *l_parent_node0 = 00;
 205         OPJ_UINT32 i;
 206         OPJ_INT32 j,k;
 207         OPJ_UINT32 l_num_levels;
 208         OPJ_UINT32 n;
 209         OPJ_UINT32 l_node_size;
 210
 211         if
 212                 (! p_tree)
 213         {
 214                 return 00;
 215         }
 216         if
 217                 ((p_tree->numleafsh != p_num_leafs_h) || (p_tree->numleafsv != p_num_leafs_v))
 218         {
 219                 p_tree->numleafsh = p_num_leafs_h;
 220                 p_tree->numleafsv = p_num_leafs_v;
 221
 222                 l_num_levels = 0;
 223                 l_nplh[0] = p_num_leafs_h;
 224                 l_nplv[0] = p_num_leafs_v;
 225                 p_tree->numnodes = 0;
 226                 do
 227                 {
 228                         n = l_nplh[l_num_levels] * l_nplv[l_num_levels];
 229                         l_nplh[l_num_levels + 1] = (l_nplh[l_num_levels] + 1) / 2;
 230                         l_nplv[l_num_levels + 1] = (l_nplv[l_num_levels] + 1) / 2;
 231                         p_tree->numnodes += n;
 232                         ++l_num_levels;
 233                 }
 234                 while (n > 1);
 235
 236                 /* ADD */
 237                 if
 238                         (p_tree->numnodes == 0)
 239                 {
 240                         tgt_destroy(p_tree);
 241             return 00;
 242                 }
 243                 l_node_size = p_tree->numnodes * sizeof(opj_tgt_node_t);
 244                 if
 245                         (l_node_size > p_tree->nodes_size)
 246                 {
 247                         p_tree->nodes = (opj_tgt_node_t*) opj_realloc(p_tree->nodes, l_node_size);
 248                         if
 249                                 (! p_tree->nodes)
 250                         {
 251                                 tgt_destroy(p_tree);
 252                                 return 00;
 253                         }
 254                         memset(((char *) p_tree->nodes) + p_tree->nodes_size, 0 , l_node_size - p_tree->nodes_size);
 255                         p_tree->nodes_size = l_node_size;
 256                 }
 257                 l_node = p_tree->nodes;
 258                 l_parent_node = &p_tree->nodes[p_tree->numleafsh * p_tree->numleafsv];
 259                 l_parent_node0 = l_parent_node;
 260
 261                 for
 262                         (i = 0; i < l_num_levels - 1; ++i)
 263                 {
 264                         for
 265                                 (j = 0; j < l_nplv[i]; ++j)
 266                         {
 267                                 k = l_nplh[i];
 268                                 while
 269                                         (--k >= 0)
 270                                 {
 271                                         l_node->parent = l_parent_node;
 272                                         ++l_node;
 273                                         if (--k >= 0)
 274                                         {
 275                                                 l_node->parent = l_parent_node;
 276                                                 ++l_node;
 277                                         }
 278                                         ++l_parent_node;
 279                                 }
 280                                 if ((j & 1) || j == l_nplv[i] - 1)
 281                                 {
 282                                         l_parent_node0 = l_parent_node;
 283                                 }
 284                                 else
 285                                 {
 286                                         l_parent_node = l_parent_node0;
 287                                         l_parent_node0 += l_nplh[i];
 288                                 }
 289                         }
 290                 }
 291                 l_node->parent = 0;
 292         }
 293         tgt_reset(p_tree);
 294
 295         return p_tree;
 296 }
 297
 298 /*void tgt_destroy(opj_tgt_tree_t *tree) {
 299         opj_free(tree->nodes);
 300         opj_free(tree);
 301 }*/
 302
 303 void tgt_destroy(opj_tgt_tree_t *p_tree)
 304 {
 305         if (! p_tree) {
 306                 return;
 307         }
 308
 309         if (p_tree->nodes) {
 310                 opj_free(p_tree->nodes);
 311                 p_tree->nodes = 00;
 312         }
 313         opj_free(p_tree);
 314 }
 315
 316 /*void tgt_reset(opj_tgt_tree_t *tree) {
 317         int i;
 318
 319         if (NULL == tree)
 320                 return;
 321
 322         for (i = 0; i < tree->numnodes; i++) {
 323                 tree->nodes[i].value = 999;
 324                 tree->nodes[i].low = 0;
 325                 tree->nodes[i].known = 0;
 326         }
 327 }*/
 328
 329 void tgt_reset(opj_tgt_tree_t *p_tree) {
 330         OPJ_UINT32 i;
 331         opj_tgt_node_t * l_current_node = 00;;
 332
 333         if (! p_tree) {
 334                 return;
 335         }
 336
 337         l_current_node = p_tree->nodes;
 338         for     (i = 0; i < p_tree->numnodes; ++i)
 339         {
 340                 l_current_node->value = 999;
 341                 l_current_node->low = 0;
 342                 l_current_node->known = 0;
 343                 ++l_current_node;
 344         }
 345 }
 346
 347 void tgt_setvalue(opj_tgt_tree_t *tree, OPJ_UINT32 leafno, OPJ_INT32 value) {
 348         opj_tgt_node_t *node;
 349         node = &tree->nodes[leafno];
 350         while (node && node->value > value) {
 351                 node->value = value;
 352                 node = node->parent;
 353         }
 354 }
 355
 356 void tgt_encode(opj_bio_t *bio, opj_tgt_tree_t *tree, OPJ_UINT32 leafno, OPJ_INT32 threshold) {
 357         opj_tgt_node_t *stk[31];
 358         opj_tgt_node_t **stkptr;
 359         opj_tgt_node_t *node;
 360         OPJ_INT32 low;
 361
 362         stkptr = stk;
 363         node = &tree->nodes[leafno];
 364         while (node->parent) {
 365                 *stkptr++ = node;
 366                 node = node->parent;
 367         }
 368
 369         low = 0;
 370         for (;;) {
 371                 if (low > node->low) {
 372                         node->low = low;
 373                 } else {
 374                         low = node->low;
 375                 }
 376
 377                 while (low < threshold) {
 378                         if (low >= node->value) {
 379                                 if (!node->known) {
 380                                         bio_write(bio, 1, 1);
 381                                         node->known = 1;
 382                                 }
 383                                 break;
 384                         }
 385                         bio_write(bio, 0, 1);
 386                         ++low;
 387                 }
 388
 389                 node->low = low;
 390                 if (stkptr == stk)
 391                         break;
 392                 node = *--stkptr;
 393         }
 394 }
 395
 396 OPJ_UINT32 tgt_decode(opj_bio_t *bio, opj_tgt_tree_t *tree, OPJ_UINT32 leafno, OPJ_INT32 threshold) {
 397         opj_tgt_node_t *stk[31];
 398         opj_tgt_node_t **stkptr;
 399         opj_tgt_node_t *node;
 400         OPJ_INT32 low;
 401
 402         stkptr = stk;
 403         node = &tree->nodes[leafno];
 404         while (node->parent) {
 405                 *stkptr++ = node;
 406                 node = node->parent;
 407         }
 408
 409         low = 0;
 410         for (;;) {
 411                 if (low > node->low) {
 412                         node->low = low;
 413                 } else {
 414                         low = node->low;
 415                 }
 416                 while (low < threshold && low < node->value) {
 417                         if (bio_read(bio, 1)) {
 418                                 node->value = low;
 419                         } else {
 420                                 ++low;
 421                         }
 422                 }
 423                 node->low = low;
 424                 if (stkptr == stk) {
 425                         break;
 426                 }
 427                 node = *--stkptr;
 428         }
 429
 430         return (node->value < threshold) ? 1 : 0;
 431 }