src/third_party/pdfium/core/src/fxcodec/fx_libopenjpeg/libopenjpeg20/tgt.c

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