[MJ2] Avoid index out of bounds access to pi->include[]
[openjpeg.git] / src / lib / openmj2 / pi.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) 2006-2007, Parvatha Elangovan
15  * All rights reserved.
16  *
17  * Redistribution and use in source and binary forms, with or without
18  * modification, are permitted provided that the following conditions
19  * are met:
20  * 1. Redistributions of source code must retain the above copyright
21  *    notice, this list of conditions and the following disclaimer.
22  * 2. Redistributions in binary form must reproduce the above copyright
23  *    notice, this list of conditions and the following disclaimer in the
24  *    documentation and/or other materials provided with the distribution.
25  *
26  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS `AS IS'
27  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
28  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
29  * ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
30  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
31  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
32  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
33  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
34  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
35  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
36  * POSSIBILITY OF SUCH DAMAGE.
37  */
38
39 #include "opj_includes.h"
40
41 /** @defgroup PI PI - Implementation of a packet iterator */
42 /*@{*/
43
44 /** @name Local static functions */
45 /*@{*/
46
47 /**
48 Get next packet in layer-resolution-component-precinct order.
49 @param pi packet iterator to modify
50 @return returns false if pi pointed to the last packet or else returns true
51 */
52 static opj_bool pi_next_lrcp(opj_pi_iterator_t * pi);
53 /**
54 Get next packet in resolution-layer-component-precinct order.
55 @param pi packet iterator to modify
56 @return returns false if pi pointed to the last packet or else returns true
57 */
58 static opj_bool pi_next_rlcp(opj_pi_iterator_t * pi);
59 /**
60 Get next packet in resolution-precinct-component-layer order.
61 @param pi packet iterator to modify
62 @return returns false if pi pointed to the last packet or else returns true
63 */
64 static opj_bool pi_next_rpcl(opj_pi_iterator_t * pi);
65 /**
66 Get next packet in precinct-component-resolution-layer order.
67 @param pi packet iterator to modify
68 @return returns false if pi pointed to the last packet or else returns true
69 */
70 static opj_bool pi_next_pcrl(opj_pi_iterator_t * pi);
71 /**
72 Get next packet in component-precinct-resolution-layer order.
73 @param pi packet iterator to modify
74 @return returns false if pi pointed to the last packet or else returns true
75 */
76 static opj_bool pi_next_cprl(opj_pi_iterator_t * pi);
77
78 /*@}*/
79
80 /*@}*/
81
82 /*
83 ==========================================================
84    local functions
85 ==========================================================
86 */
87
88 static void opj_pi_emit_error(opj_pi_iterator_t * pi, const char* msg)
89 {
90     (void)pi;
91     (void)msg;
92 }
93
94 static opj_bool pi_next_lrcp(opj_pi_iterator_t * pi)
95 {
96     opj_pi_comp_t *comp = NULL;
97     opj_pi_resolution_t *res = NULL;
98     long index = 0;
99
100     if (!pi->first) {
101         comp = &pi->comps[pi->compno];
102         res = &comp->resolutions[pi->resno];
103         goto LABEL_SKIP;
104     } else {
105         pi->first = 0;
106     }
107
108     for (pi->layno = pi->poc.layno0; pi->layno < pi->poc.layno1; pi->layno++) {
109         for (pi->resno = pi->poc.resno0; pi->resno < pi->poc.resno1;
110                 pi->resno++) {
111             for (pi->compno = pi->poc.compno0; pi->compno < pi->poc.compno1; pi->compno++) {
112                 comp = &pi->comps[pi->compno];
113                 if (pi->resno >= comp->numresolutions) {
114                     continue;
115                 }
116                 res = &comp->resolutions[pi->resno];
117                 if (!pi->tp_on) {
118                     pi->poc.precno1 = res->pw * res->ph;
119                 }
120                 for (pi->precno = pi->poc.precno0; pi->precno < pi->poc.precno1; pi->precno++) {
121                     index = pi->layno * pi->step_l + pi->resno * pi->step_r + pi->compno *
122                             pi->step_c + pi->precno * pi->step_p;
123                     /* Avoids index out of bounds access with include*/
124                     if (index >= pi->include_size) {
125                         opj_pi_emit_error(pi, "Invalid access to pi->include");
126                         return OPJ_FALSE;
127                     }
128                     if (!pi->include[index]) {
129                         pi->include[index] = 1;
130                         return OPJ_TRUE;
131                     }
132 LABEL_SKIP:
133                     ;
134                 }
135             }
136         }
137     }
138
139     return OPJ_FALSE;
140 }
141
142 static opj_bool pi_next_rlcp(opj_pi_iterator_t * pi)
143 {
144     opj_pi_comp_t *comp = NULL;
145     opj_pi_resolution_t *res = NULL;
146     long index = 0;
147
148     if (!pi->first) {
149         comp = &pi->comps[pi->compno];
150         res = &comp->resolutions[pi->resno];
151         goto LABEL_SKIP;
152     } else {
153         pi->first = 0;
154     }
155
156     for (pi->resno = pi->poc.resno0; pi->resno < pi->poc.resno1; pi->resno++) {
157         for (pi->layno = pi->poc.layno0; pi->layno < pi->poc.layno1; pi->layno++) {
158             for (pi->compno = pi->poc.compno0; pi->compno < pi->poc.compno1; pi->compno++) {
159                 comp = &pi->comps[pi->compno];
160                 if (pi->resno >= comp->numresolutions) {
161                     continue;
162                 }
163                 res = &comp->resolutions[pi->resno];
164                 if (!pi->tp_on) {
165                     pi->poc.precno1 = res->pw * res->ph;
166                 }
167                 for (pi->precno = pi->poc.precno0; pi->precno < pi->poc.precno1; pi->precno++) {
168                     index = pi->layno * pi->step_l + pi->resno * pi->step_r + pi->compno *
169                             pi->step_c + pi->precno * pi->step_p;
170                     /* Avoids index out of bounds access with include*/
171                     if (index >= pi->include_size) {
172                         opj_pi_emit_error(pi, "Invalid access to pi->include");
173                         return OPJ_FALSE;
174                     }
175                     if (!pi->include[index]) {
176                         pi->include[index] = 1;
177                         return OPJ_TRUE;
178                     }
179 LABEL_SKIP:
180                     ;
181                 }
182             }
183         }
184     }
185
186     return OPJ_FALSE;
187 }
188
189 static opj_bool pi_next_rpcl(opj_pi_iterator_t * pi)
190 {
191     opj_pi_comp_t *comp = NULL;
192     opj_pi_resolution_t *res = NULL;
193     long index = 0;
194
195     if (!pi->first) {
196         goto LABEL_SKIP;
197     } else {
198         int compno, resno;
199         pi->first = 0;
200         pi->dx = 0;
201         pi->dy = 0;
202         for (compno = 0; compno < pi->numcomps; compno++) {
203             comp = &pi->comps[compno];
204             for (resno = 0; resno < comp->numresolutions; resno++) {
205                 int dx, dy;
206                 res = &comp->resolutions[resno];
207                 dx = comp->dx * (1 << (res->pdx + comp->numresolutions - 1 - resno));
208                 dy = comp->dy * (1 << (res->pdy + comp->numresolutions - 1 - resno));
209                 pi->dx = !pi->dx ? dx : int_min(pi->dx, dx);
210                 pi->dy = !pi->dy ? dy : int_min(pi->dy, dy);
211             }
212         }
213     }
214     if (!pi->tp_on) {
215         pi->poc.ty0 = pi->ty0;
216         pi->poc.tx0 = pi->tx0;
217         pi->poc.ty1 = pi->ty1;
218         pi->poc.tx1 = pi->tx1;
219     }
220     for (pi->resno = pi->poc.resno0; pi->resno < pi->poc.resno1; pi->resno++) {
221         for (pi->y = pi->poc.ty0; pi->y < pi->poc.ty1;
222                 pi->y += pi->dy - (pi->y % pi->dy)) {
223             for (pi->x = pi->poc.tx0; pi->x < pi->poc.tx1;
224                     pi->x += pi->dx - (pi->x % pi->dx)) {
225                 for (pi->compno = pi->poc.compno0; pi->compno < pi->poc.compno1; pi->compno++) {
226                     int levelno;
227                     int trx0, try0;
228                     int trx1, try1;
229                     int rpx, rpy;
230                     int prci, prcj;
231                     comp = &pi->comps[pi->compno];
232                     if (pi->resno >= comp->numresolutions) {
233                         continue;
234                     }
235                     res = &comp->resolutions[pi->resno];
236                     levelno = comp->numresolutions - 1 - pi->resno;
237                     trx0 = int_ceildiv(pi->tx0, comp->dx << levelno);
238                     try0 = int_ceildiv(pi->ty0, comp->dy << levelno);
239                     trx1 = int_ceildiv(pi->tx1, comp->dx << levelno);
240                     try1 = int_ceildiv(pi->ty1, comp->dy << levelno);
241                     rpx = res->pdx + levelno;
242                     rpy = res->pdy + levelno;
243
244                     /* To avoid divisions by zero / undefined behaviour on shift */
245                     if (rpx >= 31 || ((comp->dx << rpx) >> rpx) != comp->dx ||
246                             rpy >= 31 || ((comp->dy << rpy) >> rpy) != comp->dy) {
247                         continue;
248                     }
249
250                     if (!((pi->y % (comp->dy << rpy) == 0) || ((pi->y == pi->ty0) &&
251                             ((try0 << levelno) % (1 << rpy))))) {
252                         continue;
253                     }
254                     if (!((pi->x % (comp->dx << rpx) == 0) || ((pi->x == pi->tx0) &&
255                             ((trx0 << levelno) % (1 << rpx))))) {
256                         continue;
257                     }
258
259                     if ((res->pw == 0) || (res->ph == 0)) {
260                         continue;
261                     }
262
263                     if ((trx0 == trx1) || (try0 == try1)) {
264                         continue;
265                     }
266
267                     prci = int_floordivpow2(int_ceildiv(pi->x, comp->dx << levelno), res->pdx)
268                            - int_floordivpow2(trx0, res->pdx);
269                     prcj = int_floordivpow2(int_ceildiv(pi->y, comp->dy << levelno), res->pdy)
270                            - int_floordivpow2(try0, res->pdy);
271                     pi->precno = prci + prcj * res->pw;
272                     for (pi->layno = pi->poc.layno0; pi->layno < pi->poc.layno1; pi->layno++) {
273                         index = pi->layno * pi->step_l + pi->resno * pi->step_r + pi->compno *
274                                 pi->step_c + pi->precno * pi->step_p;
275                         /* Avoids index out of bounds access with include*/
276                         if (index >= pi->include_size) {
277                             opj_pi_emit_error(pi, "Invalid access to pi->include");
278                             return OPJ_FALSE;
279                         }
280                         if (!pi->include[index]) {
281                             pi->include[index] = 1;
282                             return OPJ_TRUE;
283                         }
284 LABEL_SKIP:
285                         ;
286                     }
287                 }
288             }
289         }
290     }
291
292     return OPJ_FALSE;
293 }
294
295 static opj_bool pi_next_pcrl(opj_pi_iterator_t * pi)
296 {
297     opj_pi_comp_t *comp = NULL;
298     opj_pi_resolution_t *res = NULL;
299     long index = 0;
300
301     if (!pi->first) {
302         comp = &pi->comps[pi->compno];
303         goto LABEL_SKIP;
304     } else {
305         int compno, resno;
306         pi->first = 0;
307         pi->dx = 0;
308         pi->dy = 0;
309         for (compno = 0; compno < pi->numcomps; compno++) {
310             comp = &pi->comps[compno];
311             for (resno = 0; resno < comp->numresolutions; resno++) {
312                 int dx, dy;
313                 res = &comp->resolutions[resno];
314                 dx = comp->dx * (1 << (res->pdx + comp->numresolutions - 1 - resno));
315                 dy = comp->dy * (1 << (res->pdy + comp->numresolutions - 1 - resno));
316                 pi->dx = !pi->dx ? dx : int_min(pi->dx, dx);
317                 pi->dy = !pi->dy ? dy : int_min(pi->dy, dy);
318             }
319         }
320     }
321     if (!pi->tp_on) {
322         pi->poc.ty0 = pi->ty0;
323         pi->poc.tx0 = pi->tx0;
324         pi->poc.ty1 = pi->ty1;
325         pi->poc.tx1 = pi->tx1;
326     }
327     for (pi->y = pi->poc.ty0; pi->y < pi->poc.ty1;
328             pi->y += pi->dy - (pi->y % pi->dy)) {
329         for (pi->x = pi->poc.tx0; pi->x < pi->poc.tx1;
330                 pi->x += pi->dx - (pi->x % pi->dx)) {
331             for (pi->compno = pi->poc.compno0; pi->compno < pi->poc.compno1; pi->compno++) {
332                 comp = &pi->comps[pi->compno];
333                 for (pi->resno = pi->poc.resno0;
334                         pi->resno < int_min(pi->poc.resno1, comp->numresolutions); pi->resno++) {
335                     int levelno;
336                     int trx0, try0;
337                     int trx1, try1;
338                     int rpx, rpy;
339                     int prci, prcj;
340                     res = &comp->resolutions[pi->resno];
341                     levelno = comp->numresolutions - 1 - pi->resno;
342                     trx0 = int_ceildiv(pi->tx0, comp->dx << levelno);
343                     try0 = int_ceildiv(pi->ty0, comp->dy << levelno);
344                     trx1 = int_ceildiv(pi->tx1, comp->dx << levelno);
345                     try1 = int_ceildiv(pi->ty1, comp->dy << levelno);
346                     rpx = res->pdx + levelno;
347                     rpy = res->pdy + levelno;
348
349                     /* To avoid divisions by zero / undefined behaviour on shift */
350                     if (rpx >= 31 || ((comp->dx << rpx) >> rpx) != comp->dx ||
351                             rpy >= 31 || ((comp->dy << rpy) >> rpy) != comp->dy) {
352                         continue;
353                     }
354
355                     if (!((pi->y % (comp->dy << rpy) == 0) || ((pi->y == pi->ty0) &&
356                             ((try0 << levelno) % (1 << rpy))))) {
357                         continue;
358                     }
359                     if (!((pi->x % (comp->dx << rpx) == 0) || ((pi->x == pi->tx0) &&
360                             ((trx0 << levelno) % (1 << rpx))))) {
361                         continue;
362                     }
363
364                     if ((res->pw == 0) || (res->ph == 0)) {
365                         continue;
366                     }
367
368                     if ((trx0 == trx1) || (try0 == try1)) {
369                         continue;
370                     }
371
372                     prci = int_floordivpow2(int_ceildiv(pi->x, comp->dx << levelno), res->pdx)
373                            - int_floordivpow2(trx0, res->pdx);
374                     prcj = int_floordivpow2(int_ceildiv(pi->y, comp->dy << levelno), res->pdy)
375                            - int_floordivpow2(try0, res->pdy);
376                     pi->precno = prci + prcj * res->pw;
377                     for (pi->layno = pi->poc.layno0; pi->layno < pi->poc.layno1; pi->layno++) {
378                         index = pi->layno * pi->step_l + pi->resno * pi->step_r + pi->compno *
379                                 pi->step_c + pi->precno * pi->step_p;
380                         /* Avoids index out of bounds access with include*/
381                         if (index >= pi->include_size) {
382                             opj_pi_emit_error(pi, "Invalid access to pi->include");
383                             return OPJ_FALSE;
384                         }
385                         if (!pi->include[index]) {
386                             pi->include[index] = 1;
387                             return OPJ_TRUE;
388                         }
389 LABEL_SKIP:
390                         ;
391                     }
392                 }
393             }
394         }
395     }
396
397     return OPJ_FALSE;
398 }
399
400 static opj_bool pi_next_cprl(opj_pi_iterator_t * pi)
401 {
402     opj_pi_comp_t *comp = NULL;
403     opj_pi_resolution_t *res = NULL;
404     long index = 0;
405
406     if (!pi->first) {
407         comp = &pi->comps[pi->compno];
408         goto LABEL_SKIP;
409     } else {
410         pi->first = 0;
411     }
412
413     for (pi->compno = pi->poc.compno0; pi->compno < pi->poc.compno1; pi->compno++) {
414         int resno;
415         comp = &pi->comps[pi->compno];
416         pi->dx = 0;
417         pi->dy = 0;
418         for (resno = 0; resno < comp->numresolutions; resno++) {
419             int dx, dy;
420             res = &comp->resolutions[resno];
421             dx = comp->dx * (1 << (res->pdx + comp->numresolutions - 1 - resno));
422             dy = comp->dy * (1 << (res->pdy + comp->numresolutions - 1 - resno));
423             pi->dx = !pi->dx ? dx : int_min(pi->dx, dx);
424             pi->dy = !pi->dy ? dy : int_min(pi->dy, dy);
425         }
426         if (!pi->tp_on) {
427             pi->poc.ty0 = pi->ty0;
428             pi->poc.tx0 = pi->tx0;
429             pi->poc.ty1 = pi->ty1;
430             pi->poc.tx1 = pi->tx1;
431         }
432         for (pi->y = pi->poc.ty0; pi->y < pi->poc.ty1;
433                 pi->y += pi->dy - (pi->y % pi->dy)) {
434             for (pi->x = pi->poc.tx0; pi->x < pi->poc.tx1;
435                     pi->x += pi->dx - (pi->x % pi->dx)) {
436                 for (pi->resno = pi->poc.resno0;
437                         pi->resno < int_min(pi->poc.resno1, comp->numresolutions); pi->resno++) {
438                     int levelno;
439                     int trx0, try0;
440                     int trx1, try1;
441                     int rpx, rpy;
442                     int prci, prcj;
443                     res = &comp->resolutions[pi->resno];
444                     levelno = comp->numresolutions - 1 - pi->resno;
445                     trx0 = int_ceildiv(pi->tx0, comp->dx << levelno);
446                     try0 = int_ceildiv(pi->ty0, comp->dy << levelno);
447                     trx1 = int_ceildiv(pi->tx1, comp->dx << levelno);
448                     try1 = int_ceildiv(pi->ty1, comp->dy << levelno);
449                     rpx = res->pdx + levelno;
450                     rpy = res->pdy + levelno;
451
452                     /* To avoid divisions by zero / undefined behaviour on shift */
453                     if (rpx >= 31 || ((comp->dx << rpx) >> rpx) != comp->dx ||
454                             rpy >= 31 || ((comp->dy << rpy) >> rpy) != comp->dy) {
455                         continue;
456                     }
457
458                     if (!((pi->y % (comp->dy << rpy) == 0) || ((pi->y == pi->ty0) &&
459                             ((try0 << levelno) % (1 << rpy))))) {
460                         continue;
461                     }
462                     if (!((pi->x % (comp->dx << rpx) == 0) || ((pi->x == pi->tx0) &&
463                             ((trx0 << levelno) % (1 << rpx))))) {
464                         continue;
465                     }
466
467                     if ((res->pw == 0) || (res->ph == 0)) {
468                         continue;
469                     }
470
471                     if ((trx0 == trx1) || (try0 == try1)) {
472                         continue;
473                     }
474
475                     prci = int_floordivpow2(int_ceildiv(pi->x, comp->dx << levelno), res->pdx)
476                            - int_floordivpow2(trx0, res->pdx);
477                     prcj = int_floordivpow2(int_ceildiv(pi->y, comp->dy << levelno), res->pdy)
478                            - int_floordivpow2(try0, res->pdy);
479                     pi->precno = prci + prcj * res->pw;
480                     for (pi->layno = pi->poc.layno0; pi->layno < pi->poc.layno1; pi->layno++) {
481                         index = pi->layno * pi->step_l + pi->resno * pi->step_r + pi->compno *
482                                 pi->step_c + pi->precno * pi->step_p;
483                         /* Avoids index out of bounds access with include*/
484                         if (index >= pi->include_size) {
485                             opj_pi_emit_error(pi, "Invalid access to pi->include");
486                             return OPJ_FALSE;
487                         }
488                         if (!pi->include[index]) {
489                             pi->include[index] = 1;
490                             return OPJ_TRUE;
491                         }
492 LABEL_SKIP:
493                         ;
494                     }
495                 }
496             }
497         }
498     }
499
500     return OPJ_FALSE;
501 }
502
503 /*
504 ==========================================================
505    Packet iterator interface
506 ==========================================================
507 */
508
509 opj_pi_iterator_t *pi_create_decode(opj_image_t *image, opj_cp_t *cp,
510                                     int tileno)
511 {
512     int p, q;
513     int compno, resno, pino;
514     opj_pi_iterator_t *pi = NULL;
515     opj_tcp_t *tcp = NULL;
516     opj_tccp_t *tccp = NULL;
517
518     tcp = &cp->tcps[tileno];
519
520     pi = (opj_pi_iterator_t*) opj_calloc((tcp->numpocs + 1),
521                                          sizeof(opj_pi_iterator_t));
522     if (!pi) {
523         /* TODO: throw an error */
524         return NULL;
525     }
526
527     for (pino = 0; pino < tcp->numpocs + 1; pino++) {   /* change */
528         int maxres = 0;
529         int maxprec = 0;
530         p = tileno % cp->tw;
531         q = tileno / cp->tw;
532
533         pi[pino].tx0 = int_max(cp->tx0 + p * cp->tdx, image->x0);
534         pi[pino].ty0 = int_max(cp->ty0 + q * cp->tdy, image->y0);
535         pi[pino].tx1 = int_min(cp->tx0 + (p + 1) * cp->tdx, image->x1);
536         pi[pino].ty1 = int_min(cp->ty0 + (q + 1) * cp->tdy, image->y1);
537         pi[pino].numcomps = image->numcomps;
538
539         pi[pino].comps = (opj_pi_comp_t*) opj_calloc(image->numcomps,
540                          sizeof(opj_pi_comp_t));
541         if (!pi[pino].comps) {
542             /* TODO: throw an error */
543             pi_destroy(pi, cp, tileno);
544             return NULL;
545         }
546
547         for (compno = 0; compno < pi->numcomps; compno++) {
548             int tcx0, tcy0, tcx1, tcy1;
549             opj_pi_comp_t *comp = &pi[pino].comps[compno];
550             tccp = &tcp->tccps[compno];
551             comp->dx = image->comps[compno].dx;
552             comp->dy = image->comps[compno].dy;
553             comp->numresolutions = tccp->numresolutions;
554
555             comp->resolutions = (opj_pi_resolution_t*) opj_calloc(comp->numresolutions,
556                                 sizeof(opj_pi_resolution_t));
557             if (!comp->resolutions) {
558                 /* TODO: throw an error */
559                 pi_destroy(pi, cp, tileno);
560                 return NULL;
561             }
562
563             tcx0 = int_ceildiv(pi->tx0, comp->dx);
564             tcy0 = int_ceildiv(pi->ty0, comp->dy);
565             tcx1 = int_ceildiv(pi->tx1, comp->dx);
566             tcy1 = int_ceildiv(pi->ty1, comp->dy);
567             if (comp->numresolutions > maxres) {
568                 maxres = comp->numresolutions;
569             }
570
571             for (resno = 0; resno < comp->numresolutions; resno++) {
572                 int levelno;
573                 int rx0, ry0, rx1, ry1;
574                 int px0, py0, px1, py1;
575                 opj_pi_resolution_t *res = &comp->resolutions[resno];
576                 if (tccp->csty & J2K_CCP_CSTY_PRT) {
577                     res->pdx = tccp->prcw[resno];
578                     res->pdy = tccp->prch[resno];
579                 } else {
580                     res->pdx = 15;
581                     res->pdy = 15;
582                 }
583                 levelno = comp->numresolutions - 1 - resno;
584                 rx0 = int_ceildivpow2(tcx0, levelno);
585                 ry0 = int_ceildivpow2(tcy0, levelno);
586                 rx1 = int_ceildivpow2(tcx1, levelno);
587                 ry1 = int_ceildivpow2(tcy1, levelno);
588                 px0 = int_floordivpow2(rx0, res->pdx) << res->pdx;
589                 py0 = int_floordivpow2(ry0, res->pdy) << res->pdy;
590                 px1 = int_ceildivpow2(rx1, res->pdx) << res->pdx;
591                 py1 = int_ceildivpow2(ry1, res->pdy) << res->pdy;
592                 res->pw = (rx0 == rx1) ? 0 : ((px1 - px0) >> res->pdx);
593                 res->ph = (ry0 == ry1) ? 0 : ((py1 - py0) >> res->pdy);
594
595                 if (res->pw * res->ph > maxprec) {
596                     maxprec = res->pw * res->ph;
597                 }
598
599             }
600         }
601
602         tccp = &tcp->tccps[0];
603         pi[pino].step_p = 1;
604         pi[pino].step_c = maxprec * pi[pino].step_p;
605         pi[pino].step_r = image->numcomps * pi[pino].step_c;
606         pi[pino].step_l = maxres * pi[pino].step_r;
607
608         if (pino == 0) {
609             pi[pino].include = (short int*) opj_calloc(image->numcomps * maxres *
610                                tcp->numlayers * maxprec, sizeof(short int));
611             if (!pi[pino].include) {
612                 /* TODO: throw an error */
613                 pi_destroy(pi, cp, tileno);
614                 return NULL;
615             }
616         } else {
617             pi[pino].include = pi[pino - 1].include;
618         }
619
620         if (tcp->POC == 0) {
621             pi[pino].first = 1;
622             pi[pino].poc.resno0 = 0;
623             pi[pino].poc.compno0 = 0;
624             pi[pino].poc.layno1 = tcp->numlayers;
625             pi[pino].poc.resno1 = maxres;
626             pi[pino].poc.compno1 = image->numcomps;
627             pi[pino].poc.prg = tcp->prg;
628         } else {
629             pi[pino].first = 1;
630             pi[pino].poc.resno0 = tcp->pocs[pino].resno0;
631             pi[pino].poc.compno0 = tcp->pocs[pino].compno0;
632             pi[pino].poc.layno1 = tcp->pocs[pino].layno1;
633             pi[pino].poc.resno1 = tcp->pocs[pino].resno1;
634             pi[pino].poc.compno1 = tcp->pocs[pino].compno1;
635             pi[pino].poc.prg = tcp->pocs[pino].prg;
636         }
637         pi[pino].poc.layno0  = 0;
638         pi[pino].poc.precno0 = 0;
639         pi[pino].poc.precno1 = maxprec;
640
641     }
642
643     return pi;
644 }
645
646
647 opj_pi_iterator_t *pi_initialise_encode(opj_image_t *image, opj_cp_t *cp,
648                                         int tileno, J2K_T2_MODE t2_mode)
649 {
650     int p, q, pino;
651     int compno, resno;
652     int maxres = 0;
653     int maxprec = 0;
654     opj_pi_iterator_t *pi = NULL;
655     opj_tcp_t *tcp = NULL;
656     opj_tccp_t *tccp = NULL;
657
658     tcp = &cp->tcps[tileno];
659
660     pi = (opj_pi_iterator_t*) opj_calloc((tcp->numpocs + 1),
661                                          sizeof(opj_pi_iterator_t));
662     if (!pi) {
663         return NULL;
664     }
665     pi->tp_on = cp->tp_on;
666
667     for (pino = 0; pino < tcp->numpocs + 1 ; pino ++) {
668         p = tileno % cp->tw;
669         q = tileno / cp->tw;
670
671         pi[pino].tx0 = int_max(cp->tx0 + p * cp->tdx, image->x0);
672         pi[pino].ty0 = int_max(cp->ty0 + q * cp->tdy, image->y0);
673         pi[pino].tx1 = int_min(cp->tx0 + (p + 1) * cp->tdx, image->x1);
674         pi[pino].ty1 = int_min(cp->ty0 + (q + 1) * cp->tdy, image->y1);
675         pi[pino].numcomps = image->numcomps;
676
677         pi[pino].comps = (opj_pi_comp_t*) opj_calloc(image->numcomps,
678                          sizeof(opj_pi_comp_t));
679         if (!pi[pino].comps) {
680             pi_destroy(pi, cp, tileno);
681             return NULL;
682         }
683
684         for (compno = 0; compno < pi[pino].numcomps; compno++) {
685             int tcx0, tcy0, tcx1, tcy1;
686             opj_pi_comp_t *comp = &pi[pino].comps[compno];
687             tccp = &tcp->tccps[compno];
688             comp->dx = image->comps[compno].dx;
689             comp->dy = image->comps[compno].dy;
690             comp->numresolutions = tccp->numresolutions;
691
692             comp->resolutions = (opj_pi_resolution_t*) opj_malloc(comp->numresolutions *
693                                 sizeof(opj_pi_resolution_t));
694             if (!comp->resolutions) {
695                 pi_destroy(pi, cp, tileno);
696                 return NULL;
697             }
698
699             tcx0 = int_ceildiv(pi[pino].tx0, comp->dx);
700             tcy0 = int_ceildiv(pi[pino].ty0, comp->dy);
701             tcx1 = int_ceildiv(pi[pino].tx1, comp->dx);
702             tcy1 = int_ceildiv(pi[pino].ty1, comp->dy);
703             if (comp->numresolutions > maxres) {
704                 maxres = comp->numresolutions;
705             }
706
707             for (resno = 0; resno < comp->numresolutions; resno++) {
708                 int levelno;
709                 int rx0, ry0, rx1, ry1;
710                 int px0, py0, px1, py1;
711                 opj_pi_resolution_t *res = &comp->resolutions[resno];
712                 if (tccp->csty & J2K_CCP_CSTY_PRT) {
713                     res->pdx = tccp->prcw[resno];
714                     res->pdy = tccp->prch[resno];
715                 } else {
716                     res->pdx = 15;
717                     res->pdy = 15;
718                 }
719                 levelno = comp->numresolutions - 1 - resno;
720                 rx0 = int_ceildivpow2(tcx0, levelno);
721                 ry0 = int_ceildivpow2(tcy0, levelno);
722                 rx1 = int_ceildivpow2(tcx1, levelno);
723                 ry1 = int_ceildivpow2(tcy1, levelno);
724                 px0 = int_floordivpow2(rx0, res->pdx) << res->pdx;
725                 py0 = int_floordivpow2(ry0, res->pdy) << res->pdy;
726                 px1 = int_ceildivpow2(rx1, res->pdx) << res->pdx;
727                 py1 = int_ceildivpow2(ry1, res->pdy) << res->pdy;
728                 res->pw = (rx0 == rx1) ? 0 : ((px1 - px0) >> res->pdx);
729                 res->ph = (ry0 == ry1) ? 0 : ((py1 - py0) >> res->pdy);
730
731                 if (res->pw * res->ph > maxprec) {
732                     maxprec = res->pw * res->ph;
733                 }
734             }
735         }
736
737         tccp = &tcp->tccps[0];
738         pi[pino].step_p = 1;
739         pi[pino].step_c = maxprec * pi[pino].step_p;
740         pi[pino].step_r = image->numcomps * pi[pino].step_c;
741         pi[pino].step_l = maxres * pi[pino].step_r;
742
743         for (compno = 0; compno < pi->numcomps; compno++) {
744             opj_pi_comp_t *comp = &pi->comps[compno];
745             for (resno = 0; resno < comp->numresolutions; resno++) {
746                 int dx, dy;
747                 opj_pi_resolution_t *res = &comp->resolutions[resno];
748                 dx = comp->dx * (1 << (res->pdx + comp->numresolutions - 1 - resno));
749                 dy = comp->dy * (1 << (res->pdy + comp->numresolutions - 1 - resno));
750                 pi[pino].dx = !pi->dx ? dx : int_min(pi->dx, dx);
751                 pi[pino].dy = !pi->dy ? dy : int_min(pi->dy, dy);
752             }
753         }
754
755         if (pino == 0) {
756             pi[pino].include = (short int*) opj_calloc(tcp->numlayers * pi[pino].step_l,
757                                sizeof(short int));
758             if (!pi[pino].include) {
759                 pi_destroy(pi, cp, tileno);
760                 return NULL;
761             }
762         } else {
763             pi[pino].include = pi[pino - 1].include;
764         }
765
766         /* Generation of boundaries for each prog flag*/
767         if (tcp->POC && (cp->cinema || ((!cp->cinema) && (t2_mode == FINAL_PASS)))) {
768             tcp->pocs[pino].compS = tcp->pocs[pino].compno0;
769             tcp->pocs[pino].compE = tcp->pocs[pino].compno1;
770             tcp->pocs[pino].resS = tcp->pocs[pino].resno0;
771             tcp->pocs[pino].resE = tcp->pocs[pino].resno1;
772             tcp->pocs[pino].layE = tcp->pocs[pino].layno1;
773             tcp->pocs[pino].prg  = tcp->pocs[pino].prg1;
774             if (pino > 0) {
775                 tcp->pocs[pino].layS = (tcp->pocs[pino].layE > tcp->pocs[pino - 1].layE) ?
776                                        tcp->pocs[pino - 1].layE : 0;
777             }
778         } else {
779             tcp->pocs[pino].compS = 0;
780             tcp->pocs[pino].compE = image->numcomps;
781             tcp->pocs[pino].resS = 0;
782             tcp->pocs[pino].resE = maxres;
783             tcp->pocs[pino].layS = 0;
784             tcp->pocs[pino].layE = tcp->numlayers;
785             tcp->pocs[pino].prg  = tcp->prg;
786         }
787         tcp->pocs[pino].prcS = 0;
788         tcp->pocs[pino].prcE = maxprec;;
789         tcp->pocs[pino].txS = pi[pino].tx0;
790         tcp->pocs[pino].txE = pi[pino].tx1;
791         tcp->pocs[pino].tyS = pi[pino].ty0;
792         tcp->pocs[pino].tyE = pi[pino].ty1;
793         tcp->pocs[pino].dx = pi[pino].dx;
794         tcp->pocs[pino].dy = pi[pino].dy;
795     }
796     return pi;
797 }
798
799
800
801 void pi_destroy(opj_pi_iterator_t *pi, opj_cp_t *cp, int tileno)
802 {
803     int compno, pino;
804     opj_tcp_t *tcp = &cp->tcps[tileno];
805     if (pi) {
806         for (pino = 0; pino < tcp->numpocs + 1; pino++) {
807             if (pi[pino].comps) {
808                 for (compno = 0; compno < pi->numcomps; compno++) {
809                     opj_pi_comp_t *comp = &pi[pino].comps[compno];
810                     if (comp->resolutions) {
811                         opj_free(comp->resolutions);
812                     }
813                 }
814                 opj_free(pi[pino].comps);
815             }
816         }
817         if (pi->include) {
818             opj_free(pi->include);
819         }
820         opj_free(pi);
821     }
822 }
823
824 opj_bool pi_next(opj_pi_iterator_t * pi)
825 {
826     switch (pi->poc.prg) {
827     case LRCP:
828         return pi_next_lrcp(pi);
829     case RLCP:
830         return pi_next_rlcp(pi);
831     case RPCL:
832         return pi_next_rpcl(pi);
833     case PCRL:
834         return pi_next_pcrl(pi);
835     case CPRL:
836         return pi_next_cprl(pi);
837     case PROG_UNKNOWN:
838         return OPJ_FALSE;
839     }
840
841     return OPJ_FALSE;
842 }
843
844 opj_bool pi_create_encode(opj_pi_iterator_t *pi, opj_cp_t *cp, int tileno,
845                           int pino, int tpnum, int tppos, J2K_T2_MODE t2_mode, int cur_totnum_tp)
846 {
847     char prog[4];
848     int i;
849     int incr_top = 1, resetX = 0;
850     opj_tcp_t *tcps = &cp->tcps[tileno];
851     opj_poc_t *tcp = &tcps->pocs[pino];
852
853     pi[pino].first = 1;
854     pi[pino].poc.prg = tcp->prg;
855
856     switch (tcp->prg) {
857     case CPRL:
858         strncpy(prog, "CPRL", 4);
859         break;
860     case LRCP:
861         strncpy(prog, "LRCP", 4);
862         break;
863     case PCRL:
864         strncpy(prog, "PCRL", 4);
865         break;
866     case RLCP:
867         strncpy(prog, "RLCP", 4);
868         break;
869     case RPCL:
870         strncpy(prog, "RPCL", 4);
871         break;
872     case PROG_UNKNOWN:
873         return OPJ_TRUE;
874     }
875
876     if (!(cp->tp_on && ((!cp->cinema && (t2_mode == FINAL_PASS)) || cp->cinema))) {
877         pi[pino].poc.resno0 = tcp->resS;
878         pi[pino].poc.resno1 = tcp->resE;
879         pi[pino].poc.compno0 = tcp->compS;
880         pi[pino].poc.compno1 = tcp->compE;
881         pi[pino].poc.layno0 = tcp->layS;
882         pi[pino].poc.layno1 = tcp->layE;
883         pi[pino].poc.precno0 = tcp->prcS;
884         pi[pino].poc.precno1 = tcp->prcE;
885         pi[pino].poc.tx0 = tcp->txS;
886         pi[pino].poc.ty0 = tcp->tyS;
887         pi[pino].poc.tx1 = tcp->txE;
888         pi[pino].poc.ty1 = tcp->tyE;
889     } else {
890         if (tpnum < cur_totnum_tp) {
891             for (i = 3; i >= 0; i--) {
892                 switch (prog[i]) {
893                 case 'C':
894                     if (i > tppos) {
895                         pi[pino].poc.compno0 = tcp->compS;
896                         pi[pino].poc.compno1 = tcp->compE;
897                     } else {
898                         if (tpnum == 0) {
899                             tcp->comp_t = tcp->compS;
900                             pi[pino].poc.compno0 = tcp->comp_t;
901                             pi[pino].poc.compno1 = tcp->comp_t + 1;
902                             tcp->comp_t += 1;
903                         } else {
904                             if (incr_top == 1) {
905                                 if (tcp->comp_t == tcp->compE) {
906                                     tcp->comp_t = tcp->compS;
907                                     pi[pino].poc.compno0 = tcp->comp_t;
908                                     pi[pino].poc.compno1 = tcp->comp_t + 1;
909                                     tcp->comp_t += 1;
910                                     incr_top = 1;
911                                 } else {
912                                     pi[pino].poc.compno0 = tcp->comp_t;
913                                     pi[pino].poc.compno1 = tcp->comp_t + 1;
914                                     tcp->comp_t += 1;
915                                     incr_top = 0;
916                                 }
917                             } else {
918                                 pi[pino].poc.compno0 = tcp->comp_t - 1;
919                                 pi[pino].poc.compno1 = tcp->comp_t;
920                             }
921                         }
922                     }
923                     break;
924
925                 case 'R':
926                     if (i > tppos) {
927                         pi[pino].poc.resno0 = tcp->resS;
928                         pi[pino].poc.resno1 = tcp->resE;
929                     } else {
930                         if (tpnum == 0) {
931                             tcp->res_t = tcp->resS;
932                             pi[pino].poc.resno0 = tcp->res_t;
933                             pi[pino].poc.resno1 = tcp->res_t + 1;
934                             tcp->res_t += 1;
935                         } else {
936                             if (incr_top == 1) {
937                                 if (tcp->res_t == tcp->resE) {
938                                     tcp->res_t = tcp->resS;
939                                     pi[pino].poc.resno0 = tcp->res_t;
940                                     pi[pino].poc.resno1 = tcp->res_t + 1;
941                                     tcp->res_t += 1;
942                                     incr_top = 1;
943                                 } else {
944                                     pi[pino].poc.resno0 = tcp->res_t;
945                                     pi[pino].poc.resno1 = tcp->res_t + 1;
946                                     tcp->res_t += 1;
947                                     incr_top = 0;
948                                 }
949                             } else {
950                                 pi[pino].poc.resno0 = tcp->res_t - 1;
951                                 pi[pino].poc.resno1 = tcp->res_t;
952                             }
953                         }
954                     }
955                     break;
956
957                 case 'L':
958                     if (i > tppos) {
959                         pi[pino].poc.layno0 = tcp->layS;
960                         pi[pino].poc.layno1 = tcp->layE;
961                     } else {
962                         if (tpnum == 0) {
963                             tcp->lay_t = tcp->layS;
964                             pi[pino].poc.layno0 = tcp->lay_t;
965                             pi[pino].poc.layno1 = tcp->lay_t + 1;
966                             tcp->lay_t += 1;
967                         } else {
968                             if (incr_top == 1) {
969                                 if (tcp->lay_t == tcp->layE) {
970                                     tcp->lay_t = tcp->layS;
971                                     pi[pino].poc.layno0 = tcp->lay_t;
972                                     pi[pino].poc.layno1 = tcp->lay_t + 1;
973                                     tcp->lay_t += 1;
974                                     incr_top = 1;
975                                 } else {
976                                     pi[pino].poc.layno0 = tcp->lay_t;
977                                     pi[pino].poc.layno1 = tcp->lay_t + 1;
978                                     tcp->lay_t += 1;
979                                     incr_top = 0;
980                                 }
981                             } else {
982                                 pi[pino].poc.layno0 = tcp->lay_t - 1;
983                                 pi[pino].poc.layno1 = tcp->lay_t;
984                             }
985                         }
986                     }
987                     break;
988
989                 case 'P':
990                     switch (tcp->prg) {
991                     case LRCP:
992                     case RLCP:
993                         if (i > tppos) {
994                             pi[pino].poc.precno0 = tcp->prcS;
995                             pi[pino].poc.precno1 = tcp->prcE;
996                         } else {
997                             if (tpnum == 0) {
998                                 tcp->prc_t = tcp->prcS;
999                                 pi[pino].poc.precno0 = tcp->prc_t;
1000                                 pi[pino].poc.precno1 = tcp->prc_t + 1;
1001                                 tcp->prc_t += 1;
1002                             } else {
1003                                 if (incr_top == 1) {
1004                                     if (tcp->prc_t == tcp->prcE) {
1005                                         tcp->prc_t = tcp->prcS;
1006                                         pi[pino].poc.precno0 = tcp->prc_t;
1007                                         pi[pino].poc.precno1 = tcp->prc_t + 1;
1008                                         tcp->prc_t += 1;
1009                                         incr_top = 1;
1010                                     } else {
1011                                         pi[pino].poc.precno0 = tcp->prc_t;
1012                                         pi[pino].poc.precno1 = tcp->prc_t + 1;
1013                                         tcp->prc_t += 1;
1014                                         incr_top = 0;
1015                                     }
1016                                 } else {
1017                                     pi[pino].poc.precno0 = tcp->prc_t - 1;
1018                                     pi[pino].poc.precno1 = tcp->prc_t;
1019                                 }
1020                             }
1021                         }
1022                         break;
1023                     default:
1024                         if (i > tppos) {
1025                             pi[pino].poc.tx0 = tcp->txS;
1026                             pi[pino].poc.ty0 = tcp->tyS;
1027                             pi[pino].poc.tx1 = tcp->txE;
1028                             pi[pino].poc.ty1 = tcp->tyE;
1029                         } else {
1030                             if (tpnum == 0) {
1031                                 tcp->tx0_t = tcp->txS;
1032                                 tcp->ty0_t = tcp->tyS;
1033                                 pi[pino].poc.tx0 = tcp->tx0_t;
1034                                 pi[pino].poc.tx1 = tcp->tx0_t + tcp->dx - (tcp->tx0_t % tcp->dx);
1035                                 pi[pino].poc.ty0 = tcp->ty0_t;
1036                                 pi[pino].poc.ty1 = tcp->ty0_t + tcp->dy - (tcp->ty0_t % tcp->dy);
1037                                 tcp->tx0_t = pi[pino].poc.tx1;
1038                                 tcp->ty0_t = pi[pino].poc.ty1;
1039                             } else {
1040                                 if (incr_top == 1) {
1041                                     if (tcp->tx0_t >= tcp->txE) {
1042                                         if (tcp->ty0_t >= tcp->tyE) {
1043                                             tcp->ty0_t = tcp->tyS;
1044                                             pi[pino].poc.ty0 = tcp->ty0_t;
1045                                             pi[pino].poc.ty1 = tcp->ty0_t + tcp->dy - (tcp->ty0_t % tcp->dy);
1046                                             tcp->ty0_t = pi[pino].poc.ty1;
1047                                             incr_top = 1;
1048                                             resetX = 1;
1049                                         } else {
1050                                             pi[pino].poc.ty0 = tcp->ty0_t;
1051                                             pi[pino].poc.ty1 = tcp->ty0_t + tcp->dy - (tcp->ty0_t % tcp->dy);
1052                                             tcp->ty0_t = pi[pino].poc.ty1;
1053                                             incr_top = 0;
1054                                             resetX = 1;
1055                                         }
1056                                         if (resetX == 1) {
1057                                             tcp->tx0_t = tcp->txS;
1058                                             pi[pino].poc.tx0 = tcp->tx0_t;
1059                                             pi[pino].poc.tx1 = tcp->tx0_t + tcp->dx - (tcp->tx0_t % tcp->dx);
1060                                             tcp->tx0_t = pi[pino].poc.tx1;
1061                                         }
1062                                     } else {
1063                                         pi[pino].poc.tx0 = tcp->tx0_t;
1064                                         pi[pino].poc.tx1 = tcp->tx0_t + tcp->dx - (tcp->tx0_t % tcp->dx);
1065                                         tcp->tx0_t = pi[pino].poc.tx1;
1066                                         pi[pino].poc.ty0 = tcp->ty0_t - tcp->dy - (tcp->ty0_t % tcp->dy);
1067                                         pi[pino].poc.ty1 = tcp->ty0_t ;
1068                                         incr_top = 0;
1069                                     }
1070                                 } else {
1071                                     pi[pino].poc.tx0 = tcp->tx0_t - tcp->dx - (tcp->tx0_t % tcp->dx);
1072                                     pi[pino].poc.tx1 = tcp->tx0_t ;
1073                                     pi[pino].poc.ty0 = tcp->ty0_t - tcp->dy - (tcp->ty0_t % tcp->dy);
1074                                     pi[pino].poc.ty1 = tcp->ty0_t ;
1075                                 }
1076                             }
1077                         }
1078                         break;
1079                     }
1080                     break;
1081                 }
1082             }
1083         }
1084     }
1085     return OPJ_FALSE;
1086 }
1087