jpc_tagtree.c (10100B)
1 /* 2 * Copyright (c) 1999-2000 Image Power, Inc. and the University of 3 * British Columbia. 4 * Copyright (c) 2001-2003 Michael David Adams. 5 * All rights reserved. 6 */ 7 8 /* __START_OF_JASPER_LICENSE__ 9 * 10 * JasPer License Version 2.0 11 * 12 * Copyright (c) 1999-2000 Image Power, Inc. 13 * Copyright (c) 1999-2000 The University of British Columbia 14 * Copyright (c) 2001-2003 Michael David Adams 15 * 16 * All rights reserved. 17 * 18 * Permission is hereby granted, free of charge, to any person (the 19 * "User") obtaining a copy of this software and associated documentation 20 * files (the "Software"), to deal in the Software without restriction, 21 * including without limitation the rights to use, copy, modify, merge, 22 * publish, distribute, and/or sell copies of the Software, and to permit 23 * persons to whom the Software is furnished to do so, subject to the 24 * following conditions: 25 * 26 * 1. The above copyright notices and this permission notice (which 27 * includes the disclaimer below) shall be included in all copies or 28 * substantial portions of the Software. 29 * 30 * 2. The name of a copyright holder shall not be used to endorse or 31 * promote products derived from the Software without specific prior 32 * written permission. 33 * 34 * THIS DISCLAIMER OF WARRANTY CONSTITUTES AN ESSENTIAL PART OF THIS 35 * LICENSE. NO USE OF THE SOFTWARE IS AUTHORIZED HEREUNDER EXCEPT UNDER 36 * THIS DISCLAIMER. THE SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS 37 * "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING 38 * BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A 39 * PARTICULAR PURPOSE AND NONINFRINGEMENT OF THIRD PARTY RIGHTS. IN NO 40 * EVENT SHALL THE COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, OR ANY SPECIAL 41 * INDIRECT OR CONSEQUENTIAL DAMAGES, OR ANY DAMAGES WHATSOEVER RESULTING 42 * FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, 43 * NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION 44 * WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. NO ASSURANCES ARE 45 * PROVIDED BY THE COPYRIGHT HOLDERS THAT THE SOFTWARE DOES NOT INFRINGE 46 * THE PATENT OR OTHER INTELLECTUAL PROPERTY RIGHTS OF ANY OTHER ENTITY. 47 * EACH COPYRIGHT HOLDER DISCLAIMS ANY LIABILITY TO THE USER FOR CLAIMS 48 * BROUGHT BY ANY OTHER ENTITY BASED ON INFRINGEMENT OF INTELLECTUAL 49 * PROPERTY RIGHTS OR OTHERWISE. AS A CONDITION TO EXERCISING THE RIGHTS 50 * GRANTED HEREUNDER, EACH USER HEREBY ASSUMES SOLE RESPONSIBILITY TO SECURE 51 * ANY OTHER INTELLECTUAL PROPERTY RIGHTS NEEDED, IF ANY. THE SOFTWARE 52 * IS NOT FAULT-TOLERANT AND IS NOT INTENDED FOR USE IN MISSION-CRITICAL 53 * SYSTEMS, SUCH AS THOSE USED IN THE OPERATION OF NUCLEAR FACILITIES, 54 * AIRCRAFT NAVIGATION OR COMMUNICATION SYSTEMS, AIR TRAFFIC CONTROL 55 * SYSTEMS, DIRECT LIFE SUPPORT MACHINES, OR WEAPONS SYSTEMS, IN WHICH 56 * THE FAILURE OF THE SOFTWARE OR SYSTEM COULD LEAD DIRECTLY TO DEATH, 57 * PERSONAL INJURY, OR SEVERE PHYSICAL OR ENVIRONMENTAL DAMAGE ("HIGH 58 * RISK ACTIVITIES"). THE COPYRIGHT HOLDERS SPECIFICALLY DISCLAIM ANY 59 * EXPRESS OR IMPLIED WARRANTY OF FITNESS FOR HIGH RISK ACTIVITIES. 60 * 61 * __END_OF_JASPER_LICENSE__ 62 */ 63 64 /* 65 * Tag Tree Library 66 * 67 * $Id: jpc_tagtree.c 1918 2005-07-24 14:12:08Z baford $ 68 */ 69 70 /******************************************************************************\ 71 * Includes. 72 \******************************************************************************/ 73 74 #include <limits.h> 75 #include <stdlib.h> 76 #include <assert.h> 77 #include <stdio.h> 78 79 #include "jasper/jas_malloc.h" 80 81 #include "jpc_tagtree.h" 82 83 /******************************************************************************\ 84 * Prototypes. 85 \******************************************************************************/ 86 87 static jpc_tagtree_t *jpc_tagtree_alloc(void); 88 89 /******************************************************************************\ 90 * Code for creating and destroying tag trees. 91 \******************************************************************************/ 92 93 /* Create a tag tree. */ 94 95 jpc_tagtree_t *jpc_tagtree_create(int numleafsh, int numleafsv) 96 { 97 int nplh[JPC_TAGTREE_MAXDEPTH]; 98 int nplv[JPC_TAGTREE_MAXDEPTH]; 99 jpc_tagtreenode_t *node; 100 jpc_tagtreenode_t *parentnode; 101 jpc_tagtreenode_t *parentnode0; 102 jpc_tagtree_t *tree; 103 int i; 104 int j; 105 int k; 106 int numlvls; 107 int n; 108 109 assert(numleafsh > 0 && numleafsv > 0); 110 111 if (!(tree = jpc_tagtree_alloc())) { 112 return 0; 113 } 114 tree->numleafsh_ = numleafsh; 115 tree->numleafsv_ = numleafsv; 116 117 numlvls = 0; 118 nplh[0] = numleafsh; 119 nplv[0] = numleafsv; 120 do { 121 n = nplh[numlvls] * nplv[numlvls]; 122 nplh[numlvls + 1] = (nplh[numlvls] + 1) / 2; 123 nplv[numlvls + 1] = (nplv[numlvls] + 1) / 2; 124 tree->numnodes_ += n; 125 ++numlvls; 126 } while (n > 1); 127 128 if (!(tree->nodes_ = jas_malloc(tree->numnodes_ * sizeof(jpc_tagtreenode_t)))) { 129 return 0; 130 } 131 132 /* Initialize the parent links for all nodes in the tree. */ 133 134 node = tree->nodes_; 135 parentnode = &tree->nodes_[tree->numleafsh_ * tree->numleafsv_]; 136 parentnode0 = parentnode; 137 138 for (i = 0; i < numlvls - 1; ++i) { 139 for (j = 0; j < nplv[i]; ++j) { 140 k = nplh[i]; 141 while (--k >= 0) { 142 node->parent_ = parentnode; 143 ++node; 144 if (--k >= 0) { 145 node->parent_ = parentnode; 146 ++node; 147 } 148 ++parentnode; 149 } 150 if ((j & 1) || j == nplv[i] - 1) { 151 parentnode0 = parentnode; 152 } else { 153 parentnode = parentnode0; 154 parentnode0 += nplh[i]; 155 } 156 } 157 } 158 node->parent_ = 0; 159 160 /* Initialize the data values to something sane. */ 161 162 jpc_tagtree_reset(tree); 163 164 return tree; 165 } 166 167 /* Destroy a tag tree. */ 168 169 void jpc_tagtree_destroy(jpc_tagtree_t *tree) 170 { 171 if (tree->nodes_) { 172 jas_free(tree->nodes_); 173 } 174 jas_free(tree); 175 } 176 177 static jpc_tagtree_t *jpc_tagtree_alloc() 178 { 179 jpc_tagtree_t *tree; 180 181 if (!(tree = jas_malloc(sizeof(jpc_tagtree_t)))) { 182 return 0; 183 } 184 tree->numleafsh_ = 0; 185 tree->numleafsv_ = 0; 186 tree->numnodes_ = 0; 187 tree->nodes_ = 0; 188 189 return tree; 190 } 191 192 /******************************************************************************\ 193 * Code. 194 \******************************************************************************/ 195 196 /* Copy state information from one tag tree to another. */ 197 198 void jpc_tagtree_copy(jpc_tagtree_t *dsttree, jpc_tagtree_t *srctree) 199 { 200 int n; 201 jpc_tagtreenode_t *srcnode; 202 jpc_tagtreenode_t *dstnode; 203 204 /* The two tag trees must have similar sizes. */ 205 assert(srctree->numleafsh_ == dsttree->numleafsh_ && 206 srctree->numleafsv_ == dsttree->numleafsv_); 207 208 n = srctree->numnodes_; 209 srcnode = srctree->nodes_; 210 dstnode = dsttree->nodes_; 211 while (--n >= 0) { 212 dstnode->value_ = srcnode->value_; 213 dstnode->low_ = srcnode->low_; 214 dstnode->known_ = srcnode->known_; 215 ++dstnode; 216 ++srcnode; 217 } 218 } 219 220 /* Reset all of the state information associated with a tag tree. */ 221 222 void jpc_tagtree_reset(jpc_tagtree_t *tree) 223 { 224 int n; 225 jpc_tagtreenode_t *node; 226 227 n = tree->numnodes_; 228 node = tree->nodes_; 229 230 while (--n >= 0) { 231 node->value_ = INT_MAX; 232 node->low_ = 0; 233 node->known_ = 0; 234 ++node; 235 } 236 } 237 238 /* Set the value associated with the specified leaf node, updating 239 the other nodes as necessary. */ 240 241 void jpc_tagtree_setvalue(jpc_tagtree_t *tree, jpc_tagtreenode_t *leaf, 242 int value) 243 { 244 jpc_tagtreenode_t *node; 245 246 /* Avoid compiler warnings about unused parameters. */ 247 tree = 0; 248 249 assert(value >= 0); 250 251 node = leaf; 252 while (node && node->value_ > value) { 253 node->value_ = value; 254 node = node->parent_; 255 } 256 } 257 258 /* Get a particular leaf node. */ 259 260 jpc_tagtreenode_t *jpc_tagtree_getleaf(jpc_tagtree_t *tree, int n) 261 { 262 return &tree->nodes_[n]; 263 } 264 265 /* Invoke the tag tree encoding procedure. */ 266 267 int jpc_tagtree_encode(jpc_tagtree_t *tree, jpc_tagtreenode_t *leaf, 268 int threshold, jpc_bitstream_t *out) 269 { 270 jpc_tagtreenode_t *stk[JPC_TAGTREE_MAXDEPTH - 1]; 271 jpc_tagtreenode_t **stkptr; 272 jpc_tagtreenode_t *node; 273 int low; 274 275 /* Avoid compiler warnings about unused parameters. */ 276 tree = 0; 277 278 assert(leaf); 279 assert(threshold >= 0); 280 281 /* Traverse to the root of the tree, recording the path taken. */ 282 stkptr = stk; 283 node = leaf; 284 while (node->parent_) { 285 *stkptr++ = node; 286 node = node->parent_; 287 } 288 289 low = 0; 290 for (;;) { 291 if (low > node->low_) { 292 /* Deferred propagation of the lower bound downward in 293 the tree. */ 294 node->low_ = low; 295 } else { 296 low = node->low_; 297 } 298 299 while (low < threshold) { 300 if (low >= node->value_) { 301 if (!node->known_) { 302 if (jpc_bitstream_putbit(out, 1) == EOF) { 303 return -1; 304 } 305 node->known_ = 1; 306 } 307 break; 308 } 309 if (jpc_bitstream_putbit(out, 0) == EOF) { 310 return -1; 311 } 312 ++low; 313 } 314 node->low_ = low; 315 if (stkptr == stk) { 316 break; 317 } 318 node = *--stkptr; 319 320 } 321 return (leaf->low_ < threshold) ? 1 : 0; 322 323 } 324 325 /* Invoke the tag tree decoding procedure. */ 326 327 int jpc_tagtree_decode(jpc_tagtree_t *tree, jpc_tagtreenode_t *leaf, 328 int threshold, jpc_bitstream_t *in) 329 { 330 jpc_tagtreenode_t *stk[JPC_TAGTREE_MAXDEPTH - 1]; 331 jpc_tagtreenode_t **stkptr; 332 jpc_tagtreenode_t *node; 333 int low; 334 int ret; 335 336 /* Avoid compiler warnings about unused parameters. */ 337 tree = 0; 338 339 assert(threshold >= 0); 340 341 /* Traverse to the root of the tree, recording the path taken. */ 342 stkptr = stk; 343 node = leaf; 344 while (node->parent_) { 345 *stkptr++ = node; 346 node = node->parent_; 347 } 348 349 low = 0; 350 for (;;) { 351 if (low > node->low_) { 352 node->low_ = low; 353 } else { 354 low = node->low_; 355 } 356 while (low < threshold && low < node->value_) { 357 if ((ret = jpc_bitstream_getbit(in)) < 0) { 358 return -1; 359 } 360 if (ret) { 361 node->value_ = low; 362 } else { 363 ++low; 364 } 365 } 366 node->low_ = low; 367 if (stkptr == stk) { 368 break; 369 } 370 node = *--stkptr; 371 } 372 373 return (node->value_ < threshold) ? 1 : 0; 374 } 375 376 /******************************************************************************\ 377 * Code for debugging. 378 \******************************************************************************/ 379 380 void jpc_tagtree_dump(jpc_tagtree_t *tree, FILE *out) 381 { 382 jpc_tagtreenode_t *node; 383 int n; 384 385 node = tree->nodes_; 386 n = tree->numnodes_; 387 while (--n >= 0) { 388 fprintf(out, "node %p, parent %p, value %d, lower %d, known %d\n", 389 (void *) node, (void *) node->parent_, node->value_, node->low_, 390 node->known_); 391 ++node; 392 } 393 }