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