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