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) 2001-2006 Michael David Adams
13 * Copyright (c) 1999-2000 Image Power, Inc.
14 * Copyright (c) 1999-2000 The University of British Columbia
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,v 1.2 2008-05-26 09:40:52 vp153 Exp $
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
jpc_tagtree_create(int numleafsh,int numleafsv)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_alloc2(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
jpc_tagtree_destroy(jpc_tagtree_t * tree)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
jpc_tagtree_alloc()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
jpc_tagtree_copy(jpc_tagtree_t * dsttree,jpc_tagtree_t * srctree)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
jpc_tagtree_reset(jpc_tagtree_t * tree)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
jpc_tagtree_setvalue(jpc_tagtree_t * tree,jpc_tagtreenode_t * leaf,int value)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
jpc_tagtree_getleaf(jpc_tagtree_t * tree,int n)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
jpc_tagtree_encode(jpc_tagtree_t * tree,jpc_tagtreenode_t * leaf,int threshold,jpc_bitstream_t * out)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
jpc_tagtree_decode(jpc_tagtree_t * tree,jpc_tagtreenode_t * leaf,int threshold,jpc_bitstream_t * in)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
jpc_tagtree_dump(jpc_tagtree_t * tree,FILE * out)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 }
394