Zero out temporary arrays before use in PDF encryption.
[pdfium.git] / core / src / fxcodec / fx_libopenjpeg / libopenjpeg20 / tgt.c
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
48 opj_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 */
135 opj_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
222 void 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
235 void 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
253 void 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
262 void 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
302 OPJ_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 }