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