]> Creatis software - gdcm.git/blob - src/gdcmjasper/src/libjasper/jpc/jpc_tagtree.c
ENH: Ok since OJ warnings are not going to be fixed anytime soon remove them
[gdcm.git] / src / gdcmjasper / src / libjasper / jpc / jpc_tagtree.c
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,v 1.1 2005/05/22 18:33:06 malaterre 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
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 }