python api for ID property access by Joseph Eager, copied from blender 2.4x.
[blender.git] / extern / libopenjpeg / tgt.c
1 /*
2  * Copyright (c) 2002-2007, Communications and Remote Sensing Laboratory, Universite catholique de Louvain (UCL), Belgium
3  * Copyright (c) 2002-2007, Professor Benoit Macq
4  * Copyright (c) 2001-2003, David Janssens
5  * Copyright (c) 2002-2003, Yannick Verschueren
6  * Copyright (c) 2003-2007, Francois-Olivier Devaux and Antonin Descampe
7  * Copyright (c) 2005, Herve Drolon, FreeImage Team
8  * All rights reserved.
9  *
10  * Redistribution and use in source and binary forms, with or without
11  * modification, are permitted provided that the following conditions
12  * are met:
13  * 1. Redistributions of source code must retain the above copyright
14  *    notice, this list of conditions and the following disclaimer.
15  * 2. Redistributions in binary form must reproduce the above copyright
16  *    notice, this list of conditions and the following disclaimer in the
17  *    documentation and/or other materials provided with the distribution.
18  *
19  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS `AS IS'
20  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22  * ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
23  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
24  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
25  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
26  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
27  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
28  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
29  * POSSIBILITY OF SUCH DAMAGE.
30  */
31
32 #include "opj_includes.h"
33
34 /* 
35 ==========================================================
36    Tag-tree coder interface
37 ==========================================================
38 */
39
40 opj_tgt_tree_t *tgt_create(int numleafsh, int numleafsv) {
41         int nplh[32];
42         int nplv[32];
43         opj_tgt_node_t *node = NULL;
44         opj_tgt_node_t *parentnode = NULL;
45         opj_tgt_node_t *parentnode0 = NULL;
46         opj_tgt_tree_t *tree = NULL;
47         int i, j, k;
48         int numlvls;
49         int n;
50
51         tree = (opj_tgt_tree_t *) opj_malloc(sizeof(opj_tgt_tree_t));
52         if(!tree) return NULL;
53         tree->numleafsh = numleafsh;
54         tree->numleafsv = numleafsv;
55
56         numlvls = 0;
57         nplh[0] = numleafsh;
58         nplv[0] = numleafsv;
59         tree->numnodes = 0;
60         do {
61                 n = nplh[numlvls] * nplv[numlvls];
62                 nplh[numlvls + 1] = (nplh[numlvls] + 1) / 2;
63                 nplv[numlvls + 1] = (nplv[numlvls] + 1) / 2;
64                 tree->numnodes += n;
65                 ++numlvls;
66         } while (n > 1);
67         
68         /* ADD */
69         if (tree->numnodes == 0) {
70                 opj_free(tree);
71                 return NULL;
72         }
73
74         tree->nodes = (opj_tgt_node_t*) opj_calloc(tree->numnodes, sizeof(opj_tgt_node_t));
75         if(!tree->nodes) {
76                 opj_free(tree);
77                 return NULL;
78         }
79
80         node = tree->nodes;
81         parentnode = &tree->nodes[tree->numleafsh * tree->numleafsv];
82         parentnode0 = parentnode;
83         
84         for (i = 0; i < numlvls - 1; ++i) {
85                 for (j = 0; j < nplv[i]; ++j) {
86                         k = nplh[i];
87                         while (--k >= 0) {
88                                 node->parent = parentnode;
89                                 ++node;
90                                 if (--k >= 0) {
91                                         node->parent = parentnode;
92                                         ++node;
93                                 }
94                                 ++parentnode;
95                         }
96                         if ((j & 1) || j == nplv[i] - 1) {
97                                 parentnode0 = parentnode;
98                         } else {
99                                 parentnode = parentnode0;
100                                 parentnode0 += nplh[i];
101                         }
102                 }
103         }
104         node->parent = 0;
105         
106         tgt_reset(tree);
107         
108         return tree;
109 }
110
111 void tgt_destroy(opj_tgt_tree_t *tree) {
112         opj_free(tree->nodes);
113         opj_free(tree);
114 }
115
116 void tgt_reset(opj_tgt_tree_t *tree) {
117         int i;
118
119         if (NULL == tree)
120                 return;
121         
122         for (i = 0; i < tree->numnodes; i++) {
123                 tree->nodes[i].value = 999;
124                 tree->nodes[i].low = 0;
125                 tree->nodes[i].known = 0;
126         }
127 }
128
129 void tgt_setvalue(opj_tgt_tree_t *tree, int leafno, int value) {
130         opj_tgt_node_t *node;
131         node = &tree->nodes[leafno];
132         while (node && node->value > value) {
133                 node->value = value;
134                 node = node->parent;
135         }
136 }
137
138 void tgt_encode(opj_bio_t *bio, opj_tgt_tree_t *tree, int leafno, int threshold) {
139         opj_tgt_node_t *stk[31];
140         opj_tgt_node_t **stkptr;
141         opj_tgt_node_t *node;
142         int low;
143
144         stkptr = stk;
145         node = &tree->nodes[leafno];
146         while (node->parent) {
147                 *stkptr++ = node;
148                 node = node->parent;
149         }
150         
151         low = 0;
152         for (;;) {
153                 if (low > node->low) {
154                         node->low = low;
155                 } else {
156                         low = node->low;
157                 }
158                 
159                 while (low < threshold) {
160                         if (low >= node->value) {
161                                 if (!node->known) {
162                                         bio_write(bio, 1, 1);
163                                         node->known = 1;
164                                 }
165                                 break;
166                         }
167                         bio_write(bio, 0, 1);
168                         ++low;
169                 }
170                 
171                 node->low = low;
172                 if (stkptr == stk)
173                         break;
174                 node = *--stkptr;
175         }
176 }
177
178 int tgt_decode(opj_bio_t *bio, opj_tgt_tree_t *tree, int leafno, int threshold) {
179         opj_tgt_node_t *stk[31];
180         opj_tgt_node_t **stkptr;
181         opj_tgt_node_t *node;
182         int low;
183
184         stkptr = stk;
185         node = &tree->nodes[leafno];
186         while (node->parent) {
187                 *stkptr++ = node;
188                 node = node->parent;
189         }
190         
191         low = 0;
192         for (;;) {
193                 if (low > node->low) {
194                         node->low = low;
195                 } else {
196                         low = node->low;
197                 }
198                 while (low < threshold && low < node->value) {
199                         if (bio_read(bio, 1)) {
200                                 node->value = low;
201                         } else {
202                                 ++low;
203                         }
204                 }
205                 node->low = low;
206                 if (stkptr == stk) {
207                         break;
208                 }
209                 node = *--stkptr;
210         }
211         
212         return (node->value < threshold) ? 1 : 0;
213 }