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