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.
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.
18 * Redistribution and use in source and binary forms, with or without
19 * modification, are permitted provided that the following conditions
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.
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.
40 #include "opj_includes.h"
42 /** @defgroup T2 T2 - Implementation of a tier-2 coding */
45 /** @name Local static functions */
48 static void opj_t2_putcommacode(opj_bio_t *bio, OPJ_INT32 n);
50 static OPJ_UINT32 opj_t2_getcommacode(opj_bio_t *bio);
52 Variable length code for signalling delta Zil (truncation point)
53 @param bio Bit Input/Output component
56 static void opj_t2_putnumpasses(opj_bio_t *bio, OPJ_UINT32 n);
57 static OPJ_UINT32 opj_t2_getnumpasses(opj_bio_t *bio);
60 Encode a packet of a tile to a destination buffer
61 @param tileno Number of the tile encoded
62 @param tile Tile for which to write the packets
63 @param tcp Tile coding parameters
64 @param pi Packet identity
65 @param dest Destination buffer
66 @param p_data_written FIXME DOC
67 @param len Length of the destination buffer
68 @param cstr_info Codestream information structure
71 static OPJ_BOOL opj_t2_encode_packet(OPJ_UINT32 tileno,
74 opj_pi_iterator_t *pi,
76 OPJ_UINT32 * p_data_written,
78 opj_codestream_info_t *cstr_info);
81 Decode a packet of a tile from a source buffer
83 @param tile Tile for which to write the packets
84 @param tcp Tile coding parameters
85 @param pi Packet identity
86 @param src Source buffer
87 @param data_read FIXME DOC
88 @param max_length FIXME DOC
89 @param pack_info Packet information
93 static OPJ_BOOL opj_t2_decode_packet(opj_t2_t* t2,
96 opj_pi_iterator_t *pi,
98 OPJ_UINT32 * data_read,
99 OPJ_UINT32 max_length,
100 opj_packet_info_t *pack_info,
101 opj_event_mgr_t *p_manager);
103 static OPJ_BOOL opj_t2_skip_packet(opj_t2_t* p_t2,
104 opj_tcd_tile_t *p_tile,
106 opj_pi_iterator_t *p_pi,
108 OPJ_UINT32 * p_data_read,
109 OPJ_UINT32 p_max_length,
110 opj_packet_info_t *p_pack_info,
111 opj_event_mgr_t *p_manager);
113 static OPJ_BOOL opj_t2_read_packet_header(opj_t2_t* p_t2,
114 opj_tcd_tile_t *p_tile,
116 opj_pi_iterator_t *p_pi,
117 OPJ_BOOL * p_is_data_present,
118 OPJ_BYTE *p_src_data,
119 OPJ_UINT32 * p_data_read,
120 OPJ_UINT32 p_max_length,
121 opj_packet_info_t *p_pack_info,
122 opj_event_mgr_t *p_manager);
124 static OPJ_BOOL opj_t2_read_packet_data(opj_t2_t* p_t2,
125 opj_tcd_tile_t *p_tile,
126 opj_pi_iterator_t *p_pi,
127 OPJ_BYTE *p_src_data,
128 OPJ_UINT32 * p_data_read,
129 OPJ_UINT32 p_max_length,
130 opj_packet_info_t *pack_info,
131 opj_event_mgr_t *p_manager);
133 static OPJ_BOOL opj_t2_skip_packet_data(opj_t2_t* p_t2,
134 opj_tcd_tile_t *p_tile,
135 opj_pi_iterator_t *p_pi,
136 OPJ_UINT32 * p_data_read,
137 OPJ_UINT32 p_max_length,
138 opj_packet_info_t *pack_info,
139 opj_event_mgr_t *p_manager);
147 static OPJ_BOOL opj_t2_init_seg(opj_tcd_cblk_dec_t* cblk,
156 /* ----------------------------------------------------------------------- */
158 /* #define RESTART 0x04 */
159 static void opj_t2_putcommacode(opj_bio_t *bio, OPJ_INT32 n)
162 opj_bio_write(bio, 1, 1);
164 opj_bio_write(bio, 0, 1);
167 static OPJ_UINT32 opj_t2_getcommacode(opj_bio_t *bio)
170 while (opj_bio_read(bio, 1)) {
176 static void opj_t2_putnumpasses(opj_bio_t *bio, OPJ_UINT32 n)
179 opj_bio_write(bio, 0, 1);
181 opj_bio_write(bio, 2, 2);
183 opj_bio_write(bio, 0xc | (n - 3), 4);
184 } else if (n <= 36) {
185 opj_bio_write(bio, 0x1e0 | (n - 6), 9);
186 } else if (n <= 164) {
187 opj_bio_write(bio, 0xff80 | (n - 37), 16);
191 static OPJ_UINT32 opj_t2_getnumpasses(opj_bio_t *bio)
194 if (!opj_bio_read(bio, 1)) {
197 if (!opj_bio_read(bio, 1)) {
200 if ((n = opj_bio_read(bio, 2)) != 3) {
203 if ((n = opj_bio_read(bio, 5)) != 31) {
206 return (37 + opj_bio_read(bio, 7));
209 /* ----------------------------------------------------------------------- */
211 OPJ_BOOL opj_t2_encode_packets(opj_t2_t* p_t2,
212 OPJ_UINT32 p_tile_no,
213 opj_tcd_tile_t *p_tile,
214 OPJ_UINT32 p_maxlayers,
216 OPJ_UINT32 * p_data_written,
217 OPJ_UINT32 p_max_len,
218 opj_codestream_info_t *cstr_info,
222 J2K_T2_MODE p_t2_mode)
224 OPJ_BYTE *l_current_data = p_dest;
225 OPJ_UINT32 l_nb_bytes = 0;
228 opj_pi_iterator_t *l_pi = 00;
229 opj_pi_iterator_t *l_current_pi = 00;
230 opj_image_t *l_image = p_t2->image;
231 opj_cp_t *l_cp = p_t2->cp;
232 opj_tcp_t *l_tcp = &l_cp->tcps[p_tile_no];
233 OPJ_UINT32 pocno = (l_cp->rsiz == OPJ_PROFILE_CINEMA_4K) ? 2 : 1;
234 OPJ_UINT32 l_max_comp = l_cp->m_specific_param.m_enc.m_max_comp_size > 0 ?
235 l_image->numcomps : 1;
236 OPJ_UINT32 l_nb_pocs = l_tcp->numpocs + 1;
238 l_pi = opj_pi_initialise_encode(l_image, l_cp, p_tile_no, p_t2_mode);
243 * p_data_written = 0;
245 if (p_t2_mode == THRESH_CALC) { /* Calculating threshold */
248 for (compno = 0; compno < l_max_comp; ++compno) {
249 OPJ_UINT32 l_comp_len = 0;
252 for (poc = 0; poc < pocno ; ++poc) {
253 OPJ_UINT32 l_tp_num = compno;
255 /* TODO MSD : check why this function cannot fail (cf. v1) */
256 opj_pi_create_encode(l_pi, l_cp, p_tile_no, poc, l_tp_num, p_tp_pos, p_t2_mode);
258 if (l_current_pi->poc.prg == OPJ_PROG_UNKNOWN) {
259 /* TODO ADE : add an error */
260 opj_pi_destroy(l_pi, l_nb_pocs);
263 while (opj_pi_next(l_current_pi)) {
264 if (l_current_pi->layno < p_maxlayers) {
267 if (! opj_t2_encode_packet(p_tile_no, p_tile, l_tcp, l_current_pi,
268 l_current_data, &l_nb_bytes, p_max_len, cstr_info)) {
269 opj_pi_destroy(l_pi, l_nb_pocs);
273 l_comp_len += l_nb_bytes;
274 l_current_data += l_nb_bytes;
275 p_max_len -= l_nb_bytes;
277 * p_data_written += l_nb_bytes;
281 if (l_cp->m_specific_param.m_enc.m_max_comp_size) {
282 if (l_comp_len > l_cp->m_specific_param.m_enc.m_max_comp_size) {
283 opj_pi_destroy(l_pi, l_nb_pocs);
291 } else { /* t2_mode == FINAL_PASS */
292 opj_pi_create_encode(l_pi, l_cp, p_tile_no, p_pino, p_tp_num, p_tp_pos,
295 l_current_pi = &l_pi[p_pino];
296 if (l_current_pi->poc.prg == OPJ_PROG_UNKNOWN) {
297 /* TODO ADE : add an error */
298 opj_pi_destroy(l_pi, l_nb_pocs);
301 while (opj_pi_next(l_current_pi)) {
302 if (l_current_pi->layno < p_maxlayers) {
305 if (! opj_t2_encode_packet(p_tile_no, p_tile, l_tcp, l_current_pi,
306 l_current_data, &l_nb_bytes, p_max_len, cstr_info)) {
307 opj_pi_destroy(l_pi, l_nb_pocs);
311 l_current_data += l_nb_bytes;
312 p_max_len -= l_nb_bytes;
314 * p_data_written += l_nb_bytes;
318 if (cstr_info->index_write) {
319 opj_tile_info_t *info_TL = &cstr_info->tile[p_tile_no];
320 opj_packet_info_t *info_PK = &info_TL->packet[cstr_info->packno];
321 if (!cstr_info->packno) {
322 info_PK->start_pos = info_TL->end_header + 1;
324 info_PK->start_pos = ((l_cp->m_specific_param.m_enc.m_tp_on | l_tcp->POC) &&
325 info_PK->start_pos) ? info_PK->start_pos : info_TL->packet[cstr_info->packno -
328 info_PK->end_pos = info_PK->start_pos + l_nb_bytes - 1;
329 info_PK->end_ph_pos += info_PK->start_pos -
330 1; /* End of packet header which now only represents the distance
331 to start of packet is incremented by value of start of packet*/
342 opj_pi_destroy(l_pi, l_nb_pocs);
349 #define JAS_FPRINTF fprintf
352 static void opj_null_jas_fprintf(FILE* file, const char * format, ...)
357 #define JAS_FPRINTF opj_null_jas_fprintf
360 OPJ_BOOL opj_t2_decode_packets(opj_t2_t *p_t2,
361 OPJ_UINT32 p_tile_no,
362 opj_tcd_tile_t *p_tile,
364 OPJ_UINT32 * p_data_read,
365 OPJ_UINT32 p_max_len,
366 opj_codestream_index_t *p_cstr_index,
367 opj_event_mgr_t *p_manager)
369 OPJ_BYTE *l_current_data = p_src;
370 opj_pi_iterator_t *l_pi = 00;
372 opj_image_t *l_image = p_t2->image;
373 opj_cp_t *l_cp = p_t2->cp;
374 opj_tcp_t *l_tcp = &(p_t2->cp->tcps[p_tile_no]);
375 OPJ_UINT32 l_nb_bytes_read;
376 OPJ_UINT32 l_nb_pocs = l_tcp->numpocs + 1;
377 opj_pi_iterator_t *l_current_pi = 00;
379 OPJ_UINT32 curtp = 0;
380 OPJ_UINT32 tp_start_packno;
382 opj_packet_info_t *l_pack_info = 00;
383 opj_image_comp_t* l_img_comp = 00;
385 OPJ_ARG_NOT_USED(p_cstr_index);
389 l_pack_info = p_cstr_index->tile_index[p_tile_no].packet;
393 /* create a packet iterator */
394 l_pi = opj_pi_create_decode(l_image, l_cp, p_tile_no);
402 for (pino = 0; pino <= l_tcp->numpocs; ++pino) {
404 /* if the resolution needed is too low, one dim of the tilec could be equal to zero
405 * and no packets are used to decode this resolution and
406 * l_current_pi->resno is always >= p_tile->comps[l_current_pi->compno].minimum_num_resolutions
407 * and no l_img_comp->resno_decoded are computed
409 OPJ_BOOL* first_pass_failed = NULL;
411 if (l_current_pi->poc.prg == OPJ_PROG_UNKNOWN) {
412 /* TODO ADE : add an error */
413 opj_pi_destroy(l_pi, l_nb_pocs);
417 first_pass_failed = (OPJ_BOOL*)opj_malloc(l_image->numcomps * sizeof(OPJ_BOOL));
418 if (!first_pass_failed) {
419 opj_pi_destroy(l_pi, l_nb_pocs);
422 memset(first_pass_failed, OPJ_TRUE, l_image->numcomps * sizeof(OPJ_BOOL));
424 while (opj_pi_next(l_current_pi)) {
426 "packet offset=00000166 prg=%d cmptno=%02d rlvlno=%02d prcno=%03d lyrno=%02d\n\n",
427 l_current_pi->poc.prg1, l_current_pi->compno, l_current_pi->resno,
428 l_current_pi->precno, l_current_pi->layno);
430 if (l_tcp->num_layers_to_decode > l_current_pi->layno
431 && l_current_pi->resno <
432 p_tile->comps[l_current_pi->compno].minimum_num_resolutions) {
435 first_pass_failed[l_current_pi->compno] = OPJ_FALSE;
437 if (! opj_t2_decode_packet(p_t2, p_tile, l_tcp, l_current_pi, l_current_data,
438 &l_nb_bytes_read, p_max_len, l_pack_info, p_manager)) {
439 opj_pi_destroy(l_pi, l_nb_pocs);
440 opj_free(first_pass_failed);
444 l_img_comp = &(l_image->comps[l_current_pi->compno]);
445 l_img_comp->resno_decoded = opj_uint_max(l_current_pi->resno,
446 l_img_comp->resno_decoded);
449 if (! opj_t2_skip_packet(p_t2, p_tile, l_tcp, l_current_pi, l_current_data,
450 &l_nb_bytes_read, p_max_len, l_pack_info, p_manager)) {
451 opj_pi_destroy(l_pi, l_nb_pocs);
452 opj_free(first_pass_failed);
457 if (first_pass_failed[l_current_pi->compno]) {
458 l_img_comp = &(l_image->comps[l_current_pi->compno]);
459 if (l_img_comp->resno_decoded == 0) {
460 l_img_comp->resno_decoded =
461 p_tile->comps[l_current_pi->compno].minimum_num_resolutions - 1;
465 l_current_data += l_nb_bytes_read;
466 p_max_len -= l_nb_bytes_read;
471 opj_tile_info_v2_t *info_TL = &p_cstr_info->tile[p_tile_no];
472 opj_packet_info_t *info_PK = &info_TL->packet[p_cstr_info->packno];
474 if (!p_cstr_info->packno) {
475 info_PK->start_pos = info_TL->end_header + 1;
476 } else if (info_TL->packet[p_cstr_info->packno - 1].end_pos >=
478 p_cstr_info->tile[p_tile_no].tp[curtp].tp_end_pos) { /* New tile part */
479 info_TL->tp[curtp].tp_numpacks = p_cstr_info->packno -
480 tp_start_packno; /* Number of packets in previous tile-part */
481 tp_start_packno = p_cstr_info->packno;
483 info_PK->start_pos = p_cstr_info->tile[p_tile_no].tp[curtp].tp_end_header + 1;
485 info_PK->start_pos = (l_cp->m_specific_param.m_enc.m_tp_on &&
486 info_PK->start_pos) ? info_PK->start_pos : info_TL->packet[p_cstr_info->packno -
489 info_PK->end_pos = info_PK->start_pos + l_nb_bytes_read - 1;
490 info_PK->end_ph_pos += info_PK->start_pos -
491 1; /* End of packet header which now only represents the distance */
492 ++p_cstr_info->packno;
499 opj_free(first_pass_failed);
505 p_cstr_info->tile[p_tile_no].tp[curtp].tp_numpacks = p_cstr_info->packno -
506 tp_start_packno; /* Number of packets in last tile-part */
511 /* don't forget to release pi */
512 opj_pi_destroy(l_pi, l_nb_pocs);
513 *p_data_read = (OPJ_UINT32)(l_current_data - p_src);
517 /* ----------------------------------------------------------------------- */
520 * Creates a Tier 2 handle
522 * @param p_image Source or destination image
523 * @param p_cp Image coding parameters.
524 * @return a new T2 handle if successful, NULL otherwise.
526 opj_t2_t* opj_t2_create(opj_image_t *p_image, opj_cp_t *p_cp)
528 /* create the t2 structure */
529 opj_t2_t *l_t2 = (opj_t2_t*)opj_calloc(1, sizeof(opj_t2_t));
534 l_t2->image = p_image;
540 void opj_t2_destroy(opj_t2_t *t2)
547 static OPJ_BOOL opj_t2_decode_packet(opj_t2_t* p_t2,
548 opj_tcd_tile_t *p_tile,
550 opj_pi_iterator_t *p_pi,
552 OPJ_UINT32 * p_data_read,
553 OPJ_UINT32 p_max_length,
554 opj_packet_info_t *p_pack_info,
555 opj_event_mgr_t *p_manager)
557 OPJ_BOOL l_read_data;
558 OPJ_UINT32 l_nb_bytes_read = 0;
559 OPJ_UINT32 l_nb_total_bytes_read = 0;
563 if (! opj_t2_read_packet_header(p_t2, p_tile, p_tcp, p_pi, &l_read_data, p_src,
564 &l_nb_bytes_read, p_max_length, p_pack_info, p_manager)) {
568 p_src += l_nb_bytes_read;
569 l_nb_total_bytes_read += l_nb_bytes_read;
570 p_max_length -= l_nb_bytes_read;
572 /* we should read data for the packet */
576 if (! opj_t2_read_packet_data(p_t2, p_tile, p_pi, p_src, &l_nb_bytes_read,
577 p_max_length, p_pack_info, p_manager)) {
581 l_nb_total_bytes_read += l_nb_bytes_read;
584 *p_data_read = l_nb_total_bytes_read;
589 static OPJ_BOOL opj_t2_encode_packet(OPJ_UINT32 tileno,
590 opj_tcd_tile_t * tile,
592 opj_pi_iterator_t *pi,
594 OPJ_UINT32 * p_data_written,
596 opj_codestream_info_t *cstr_info)
598 OPJ_UINT32 bandno, cblkno;
600 OPJ_UINT32 l_nb_bytes;
601 OPJ_UINT32 compno = pi->compno; /* component value */
602 OPJ_UINT32 resno = pi->resno; /* resolution level value */
603 OPJ_UINT32 precno = pi->precno; /* precinct value */
604 OPJ_UINT32 layno = pi->layno; /* quality layer value */
605 OPJ_UINT32 l_nb_blocks;
606 opj_tcd_band_t *band = 00;
607 opj_tcd_cblk_enc_t* cblk = 00;
608 opj_tcd_pass_t *pass = 00;
610 opj_tcd_tilecomp_t *tilec = &tile->comps[compno];
611 opj_tcd_resolution_t *res = &tilec->resolutions[resno];
613 opj_bio_t *bio = 00; /* BIO component */
614 OPJ_BOOL packet_empty = OPJ_TRUE;
617 if (tcp->csty & J2K_CP_CSTY_SOP) {
623 c[4] = (tile->packno % 65536) / 256;
624 c[5] = (tile->packno % 65536) % 256;
626 c[4] = (tile->packno >> 8) & 0xff; /* packno is uint32_t */
627 c[5] = tile->packno & 0xff;
637 for (bandno = 0; bandno < res->numbands; ++bandno, ++band) {
638 opj_tcd_precinct_t *prc;
640 /* Skip empty bands */
641 if (opj_tcd_is_band_empty(band)) {
645 prc = &band->precincts[precno];
646 opj_tgt_reset(prc->incltree);
647 opj_tgt_reset(prc->imsbtree);
649 l_nb_blocks = prc->cw * prc->ch;
650 for (cblkno = 0; cblkno < l_nb_blocks; ++cblkno) {
651 cblk = &prc->cblks.enc[cblkno];
654 opj_tgt_setvalue(prc->imsbtree, cblkno, band->numbps - (OPJ_INT32)cblk->numbps);
659 bio = opj_bio_create();
661 /* FIXME event manager error callback */
664 opj_bio_init_enc(bio, c, length);
666 /* Check if the packet is empty */
667 /* Note: we could also skip that step and always write a packet header */
669 for (bandno = 0; bandno < res->numbands; ++bandno, ++band) {
670 opj_tcd_precinct_t *prc;
671 /* Skip empty bands */
672 if (opj_tcd_is_band_empty(band)) {
676 prc = &band->precincts[precno];
677 l_nb_blocks = prc->cw * prc->ch;
678 cblk = prc->cblks.enc;
679 for (cblkno = 0; cblkno < l_nb_blocks; cblkno++, ++cblk) {
680 opj_tcd_layer_t *layer = &cblk->layers[layno];
682 /* if cblk not included, go to the next cblk */
683 if (!layer->numpasses) {
686 packet_empty = OPJ_FALSE;
694 opj_bio_write(bio, packet_empty ? 0 : 1, 1); /* Empty header bit */
697 /* Writing Packet header */
699 for (bandno = 0; !packet_empty &&
700 bandno < res->numbands; ++bandno, ++band) {
701 opj_tcd_precinct_t *prc;
703 /* Skip empty bands */
704 if (opj_tcd_is_band_empty(band)) {
708 prc = &band->precincts[precno];
709 l_nb_blocks = prc->cw * prc->ch;
710 cblk = prc->cblks.enc;
712 for (cblkno = 0; cblkno < l_nb_blocks; ++cblkno) {
713 opj_tcd_layer_t *layer = &cblk->layers[layno];
715 if (!cblk->numpasses && layer->numpasses) {
716 opj_tgt_setvalue(prc->incltree, cblkno, (OPJ_INT32)layno);
722 cblk = prc->cblks.enc;
723 for (cblkno = 0; cblkno < l_nb_blocks; cblkno++) {
724 opj_tcd_layer_t *layer = &cblk->layers[layno];
725 OPJ_UINT32 increment = 0;
727 OPJ_UINT32 len = 0, passno;
728 OPJ_UINT32 l_nb_passes;
730 /* cblk inclusion bits */
731 if (!cblk->numpasses) {
732 opj_tgt_encode(bio, prc->incltree, cblkno, (OPJ_INT32)(layno + 1));
734 opj_bio_write(bio, layer->numpasses != 0, 1);
737 /* if cblk not included, go to the next cblk */
738 if (!layer->numpasses) {
743 /* if first instance of cblk --> zero bit-planes information */
744 if (!cblk->numpasses) {
745 cblk->numlenbits = 3;
746 opj_tgt_encode(bio, prc->imsbtree, cblkno, 999);
749 /* number of coding passes included */
750 opj_t2_putnumpasses(bio, layer->numpasses);
751 l_nb_passes = cblk->numpasses + layer->numpasses;
752 pass = cblk->passes + cblk->numpasses;
754 /* computation of the increase of the length indicator and insertion in the header */
755 for (passno = cblk->numpasses; passno < l_nb_passes; ++passno) {
759 if (pass->term || passno == (cblk->numpasses + layer->numpasses) - 1) {
760 increment = (OPJ_UINT32)opj_int_max((OPJ_INT32)increment,
761 opj_int_floorlog2((OPJ_INT32)len) + 1
762 - ((OPJ_INT32)cblk->numlenbits + opj_int_floorlog2((OPJ_INT32)nump)));
769 opj_t2_putcommacode(bio, (OPJ_INT32)increment);
771 /* computation of the new Length indicator */
772 cblk->numlenbits += increment;
774 pass = cblk->passes + cblk->numpasses;
775 /* insertion of the codeword segment length */
776 for (passno = cblk->numpasses; passno < l_nb_passes; ++passno) {
780 if (pass->term || passno == (cblk->numpasses + layer->numpasses) - 1) {
781 opj_bio_write(bio, (OPJ_UINT32)len,
782 cblk->numlenbits + (OPJ_UINT32)opj_int_floorlog2((OPJ_INT32)nump));
793 if (!opj_bio_flush(bio)) {
794 opj_bio_destroy(bio);
795 return OPJ_FALSE; /* modified to eliminate longjmp !! */
798 l_nb_bytes = (OPJ_UINT32)opj_bio_numbytes(bio);
800 length -= l_nb_bytes;
802 opj_bio_destroy(bio);
805 if (tcp->csty & J2K_CP_CSTY_EPH) {
814 /* End of packet header position. Currently only represents the distance to start of packet
815 Will be updated later by incrementing with packet start value*/
816 if (cstr_info && cstr_info->index_write) {
817 opj_packet_info_t *info_PK = &cstr_info->tile[tileno].packet[cstr_info->packno];
818 info_PK->end_ph_pos = (OPJ_INT32)(c - dest);
822 /* Writing the packet body */
824 for (bandno = 0; !packet_empty && bandno < res->numbands; bandno++, ++band) {
825 opj_tcd_precinct_t *prc;
827 /* Skip empty bands */
828 if (opj_tcd_is_band_empty(band)) {
832 prc = &band->precincts[precno];
833 l_nb_blocks = prc->cw * prc->ch;
834 cblk = prc->cblks.enc;
836 for (cblkno = 0; cblkno < l_nb_blocks; ++cblkno) {
837 opj_tcd_layer_t *layer = &cblk->layers[layno];
839 if (!layer->numpasses) {
844 if (layer->len > length) {
848 memcpy(c, layer->data, layer->len);
849 cblk->numpasses += layer->numpasses;
851 length -= layer->len;
854 if (cstr_info && cstr_info->index_write) {
855 opj_packet_info_t *info_PK = &cstr_info->tile[tileno].packet[cstr_info->packno];
856 info_PK->disto += layer->disto;
857 if (cstr_info->D_max < info_PK->disto) {
858 cstr_info->D_max = info_PK->disto;
868 * p_data_written += (OPJ_UINT32)(c - dest);
873 static OPJ_BOOL opj_t2_skip_packet(opj_t2_t* p_t2,
874 opj_tcd_tile_t *p_tile,
876 opj_pi_iterator_t *p_pi,
878 OPJ_UINT32 * p_data_read,
879 OPJ_UINT32 p_max_length,
880 opj_packet_info_t *p_pack_info,
881 opj_event_mgr_t *p_manager)
883 OPJ_BOOL l_read_data;
884 OPJ_UINT32 l_nb_bytes_read = 0;
885 OPJ_UINT32 l_nb_total_bytes_read = 0;
889 if (! opj_t2_read_packet_header(p_t2, p_tile, p_tcp, p_pi, &l_read_data, p_src,
890 &l_nb_bytes_read, p_max_length, p_pack_info, p_manager)) {
894 p_src += l_nb_bytes_read;
895 l_nb_total_bytes_read += l_nb_bytes_read;
896 p_max_length -= l_nb_bytes_read;
898 /* we should read data for the packet */
902 if (! opj_t2_skip_packet_data(p_t2, p_tile, p_pi, &l_nb_bytes_read,
903 p_max_length, p_pack_info, p_manager)) {
907 l_nb_total_bytes_read += l_nb_bytes_read;
909 *p_data_read = l_nb_total_bytes_read;
915 static OPJ_BOOL opj_t2_read_packet_header(opj_t2_t* p_t2,
916 opj_tcd_tile_t *p_tile,
918 opj_pi_iterator_t *p_pi,
919 OPJ_BOOL * p_is_data_present,
920 OPJ_BYTE *p_src_data,
921 OPJ_UINT32 * p_data_read,
922 OPJ_UINT32 p_max_length,
923 opj_packet_info_t *p_pack_info,
924 opj_event_mgr_t *p_manager)
928 OPJ_UINT32 bandno, cblkno;
929 OPJ_UINT32 l_nb_code_blocks;
930 OPJ_UINT32 l_remaining_length;
931 OPJ_UINT32 l_header_length;
932 OPJ_UINT32 * l_modified_length_ptr = 00;
933 OPJ_BYTE *l_current_data = p_src_data;
934 opj_cp_t *l_cp = p_t2->cp;
935 opj_bio_t *l_bio = 00; /* BIO component */
936 opj_tcd_band_t *l_band = 00;
937 opj_tcd_cblk_dec_t* l_cblk = 00;
938 opj_tcd_resolution_t* l_res =
939 &p_tile->comps[p_pi->compno].resolutions[p_pi->resno];
941 OPJ_BYTE *l_header_data = 00;
942 OPJ_BYTE **l_header_data_start = 00;
944 OPJ_UINT32 l_present;
946 if (p_pi->layno == 0) {
947 l_band = l_res->bands;
950 for (bandno = 0; bandno < l_res->numbands; ++bandno) {
951 if (!opj_tcd_is_band_empty(l_band)) {
952 opj_tcd_precinct_t *l_prc = &l_band->precincts[p_pi->precno];
953 if (!(p_pi->precno < (l_band->precincts_data_size / sizeof(
954 opj_tcd_precinct_t)))) {
955 opj_event_msg(p_manager, EVT_ERROR, "Invalid precinct\n");
960 opj_tgt_reset(l_prc->incltree);
961 opj_tgt_reset(l_prc->imsbtree);
962 l_cblk = l_prc->cblks.dec;
964 l_nb_code_blocks = l_prc->cw * l_prc->ch;
965 for (cblkno = 0; cblkno < l_nb_code_blocks; ++cblkno) {
967 l_cblk->real_num_segs = 0;
978 if (p_tcp->csty & J2K_CP_CSTY_SOP) {
979 if (p_max_length < 6) {
980 opj_event_msg(p_manager, EVT_WARNING,
981 "Not enough space for expected SOP marker\n");
982 } else if ((*l_current_data) != 0xff || (*(l_current_data + 1) != 0x91)) {
983 opj_event_msg(p_manager, EVT_WARNING, "Expected SOP marker\n");
988 /** TODO : check the Nsop value */
992 When the marker PPT/PPM is used the packet header are store in PPT/PPM marker
993 This part deal with this caracteristic
994 step 1: Read packet header in the saved structure
995 step 2: Return to codestream for decoding
998 l_bio = opj_bio_create();
1003 if (l_cp->ppm == 1) { /* PPM */
1004 l_header_data_start = &l_cp->ppm_data;
1005 l_header_data = *l_header_data_start;
1006 l_modified_length_ptr = &(l_cp->ppm_len);
1008 } else if (p_tcp->ppt == 1) { /* PPT */
1009 l_header_data_start = &(p_tcp->ppt_data);
1010 l_header_data = *l_header_data_start;
1011 l_modified_length_ptr = &(p_tcp->ppt_len);
1012 } else { /* Normal Case */
1013 l_header_data_start = &(l_current_data);
1014 l_header_data = *l_header_data_start;
1015 l_remaining_length = (OPJ_UINT32)(p_src_data + p_max_length - l_header_data);
1016 l_modified_length_ptr = &(l_remaining_length);
1019 opj_bio_init_dec(l_bio, l_header_data, *l_modified_length_ptr);
1021 l_present = opj_bio_read(l_bio, 1);
1022 JAS_FPRINTF(stderr, "present=%d \n", l_present);
1024 /* TODO MSD: no test to control the output of this function*/
1025 opj_bio_inalign(l_bio);
1026 l_header_data += opj_bio_numbytes(l_bio);
1027 opj_bio_destroy(l_bio);
1030 if (p_tcp->csty & J2K_CP_CSTY_EPH) {
1031 if ((*l_modified_length_ptr - (OPJ_UINT32)(l_header_data -
1032 *l_header_data_start)) < 2U) {
1033 opj_event_msg(p_manager, EVT_WARNING,
1034 "Not enough space for expected EPH marker\n");
1035 } else if ((*l_header_data) != 0xff || (*(l_header_data + 1) != 0x92)) {
1036 opj_event_msg(p_manager, EVT_WARNING, "Expected EPH marker\n");
1042 l_header_length = (OPJ_UINT32)(l_header_data - *l_header_data_start);
1043 *l_modified_length_ptr -= l_header_length;
1044 *l_header_data_start += l_header_length;
1047 /* End of packet header position. Currently only represents the distance to start of packet
1048 Will be updated later by incrementing with packet start value */
1050 p_pack_info->end_ph_pos = (OPJ_INT32)(l_current_data - p_src_data);
1054 * p_is_data_present = OPJ_FALSE;
1055 *p_data_read = (OPJ_UINT32)(l_current_data - p_src_data);
1059 l_band = l_res->bands;
1060 for (bandno = 0; bandno < l_res->numbands; ++bandno, ++l_band) {
1061 opj_tcd_precinct_t *l_prc = &(l_band->precincts[p_pi->precno]);
1063 if (opj_tcd_is_band_empty(l_band)) {
1067 l_nb_code_blocks = l_prc->cw * l_prc->ch;
1068 l_cblk = l_prc->cblks.dec;
1069 for (cblkno = 0; cblkno < l_nb_code_blocks; cblkno++) {
1070 OPJ_UINT32 l_included, l_increment, l_segno;
1073 /* if cblk not yet included before --> inclusion tagtree */
1074 if (!l_cblk->numsegs) {
1075 l_included = opj_tgt_decode(l_bio, l_prc->incltree, cblkno,
1076 (OPJ_INT32)(p_pi->layno + 1));
1079 l_included = opj_bio_read(l_bio, 1);
1082 /* if cblk not included */
1084 l_cblk->numnewpasses = 0;
1086 JAS_FPRINTF(stderr, "included=%d \n", l_included);
1090 /* if cblk not yet included --> zero-bitplane tagtree */
1091 if (!l_cblk->numsegs) {
1094 while (!opj_tgt_decode(l_bio, l_prc->imsbtree, cblkno, (OPJ_INT32)i)) {
1098 l_cblk->numbps = (OPJ_UINT32)l_band->numbps + 1 - i;
1099 l_cblk->numlenbits = 3;
1102 /* number of coding passes */
1103 l_cblk->numnewpasses = opj_t2_getnumpasses(l_bio);
1104 l_increment = opj_t2_getcommacode(l_bio);
1106 /* length indicator increment */
1107 l_cblk->numlenbits += l_increment;
1110 if (!l_cblk->numsegs) {
1111 if (! opj_t2_init_seg(l_cblk, l_segno, p_tcp->tccps[p_pi->compno].cblksty, 1)) {
1112 opj_bio_destroy(l_bio);
1116 l_segno = l_cblk->numsegs - 1;
1117 if (l_cblk->segs[l_segno].numpasses == l_cblk->segs[l_segno].maxpasses) {
1119 if (! opj_t2_init_seg(l_cblk, l_segno, p_tcp->tccps[p_pi->compno].cblksty, 0)) {
1120 opj_bio_destroy(l_bio);
1125 n = (OPJ_INT32)l_cblk->numnewpasses;
1128 l_cblk->segs[l_segno].numnewpasses = (OPJ_UINT32)opj_int_min((OPJ_INT32)(
1129 l_cblk->segs[l_segno].maxpasses - l_cblk->segs[l_segno].numpasses), n);
1130 l_cblk->segs[l_segno].newlen = opj_bio_read(l_bio,
1131 l_cblk->numlenbits + opj_uint_floorlog2(l_cblk->segs[l_segno].numnewpasses));
1132 JAS_FPRINTF(stderr, "included=%d numnewpasses=%d increment=%d len=%d \n",
1133 l_included, l_cblk->segs[l_segno].numnewpasses, l_increment,
1134 l_cblk->segs[l_segno].newlen);
1136 n -= (OPJ_INT32)l_cblk->segs[l_segno].numnewpasses;
1140 if (! opj_t2_init_seg(l_cblk, l_segno, p_tcp->tccps[p_pi->compno].cblksty, 0)) {
1141 opj_bio_destroy(l_bio);
1151 if (!opj_bio_inalign(l_bio)) {
1152 opj_bio_destroy(l_bio);
1156 l_header_data += opj_bio_numbytes(l_bio);
1157 opj_bio_destroy(l_bio);
1160 if (p_tcp->csty & J2K_CP_CSTY_EPH) {
1161 if ((*l_modified_length_ptr - (OPJ_UINT32)(l_header_data -
1162 *l_header_data_start)) < 2U) {
1163 opj_event_msg(p_manager, EVT_WARNING,
1164 "Not enough space for expected EPH marker\n");
1165 } else if ((*l_header_data) != 0xff || (*(l_header_data + 1) != 0x92)) {
1166 opj_event_msg(p_manager, EVT_WARNING, "Expected EPH marker\n");
1172 l_header_length = (OPJ_UINT32)(l_header_data - *l_header_data_start);
1173 JAS_FPRINTF(stderr, "hdrlen=%d \n", l_header_length);
1174 JAS_FPRINTF(stderr, "packet body\n");
1175 *l_modified_length_ptr -= l_header_length;
1176 *l_header_data_start += l_header_length;
1179 /* End of packet header position. Currently only represents the distance to start of packet
1180 Will be updated later by incrementing with packet start value */
1182 p_pack_info->end_ph_pos = (OPJ_INT32)(l_current_data - p_src_data);
1186 *p_is_data_present = OPJ_TRUE;
1187 *p_data_read = (OPJ_UINT32)(l_current_data - p_src_data);
1192 static OPJ_BOOL opj_t2_read_packet_data(opj_t2_t* p_t2,
1193 opj_tcd_tile_t *p_tile,
1194 opj_pi_iterator_t *p_pi,
1195 OPJ_BYTE *p_src_data,
1196 OPJ_UINT32 * p_data_read,
1197 OPJ_UINT32 p_max_length,
1198 opj_packet_info_t *pack_info,
1199 opj_event_mgr_t* p_manager)
1201 OPJ_UINT32 bandno, cblkno;
1202 OPJ_UINT32 l_nb_code_blocks;
1203 OPJ_BYTE *l_current_data = p_src_data;
1204 opj_tcd_band_t *l_band = 00;
1205 opj_tcd_cblk_dec_t* l_cblk = 00;
1206 opj_tcd_resolution_t* l_res =
1207 &p_tile->comps[p_pi->compno].resolutions[p_pi->resno];
1209 OPJ_ARG_NOT_USED(p_t2);
1210 OPJ_ARG_NOT_USED(pack_info);
1212 l_band = l_res->bands;
1213 for (bandno = 0; bandno < l_res->numbands; ++bandno) {
1214 opj_tcd_precinct_t *l_prc = &l_band->precincts[p_pi->precno];
1216 if ((l_band->x1 - l_band->x0 == 0) || (l_band->y1 - l_band->y0 == 0)) {
1221 l_nb_code_blocks = l_prc->cw * l_prc->ch;
1222 l_cblk = l_prc->cblks.dec;
1224 for (cblkno = 0; cblkno < l_nb_code_blocks; ++cblkno) {
1225 opj_tcd_seg_t *l_seg = 00;
1227 if (!l_cblk->numnewpasses) {
1233 if (!l_cblk->numsegs) {
1234 l_seg = l_cblk->segs;
1236 l_cblk->data_current_size = 0;
1238 l_seg = &l_cblk->segs[l_cblk->numsegs - 1];
1240 if (l_seg->numpasses == l_seg->maxpasses) {
1247 /* Check possible overflow (on l_current_data only, assumes input args already checked) then size */
1248 if ((((OPJ_SIZE_T)l_current_data + (OPJ_SIZE_T)l_seg->newlen) <
1249 (OPJ_SIZE_T)l_current_data) ||
1250 (l_current_data + l_seg->newlen > p_src_data + p_max_length)) {
1251 opj_event_msg(p_manager, EVT_ERROR,
1252 "read: segment too long (%d) with max (%d) for codeblock %d (p=%d, b=%d, r=%d, c=%d)\n",
1253 l_seg->newlen, p_max_length, cblkno, p_pi->precno, bandno, p_pi->resno,
1259 /* we need here a j2k handle to verify if making a check to
1260 the validity of cblocks parameters is selected from user (-W) */
1262 /* let's check that we are not exceeding */
1263 if ((l_cblk->len + l_seg->newlen) > 8192) {
1264 opj_event_msg(p_manager, EVT_WARNING,
1265 "JPWL: segment too long (%d) for codeblock %d (p=%d, b=%d, r=%d, c=%d)\n",
1266 l_seg->newlen, cblkno, p_pi->precno, bandno, p_pi->resno, p_pi->compno);
1268 opj_event_msg(p_manager, EVT_ERROR, "JPWL: giving up\n");
1271 l_seg->newlen = 8192 - l_cblk->len;
1272 opj_event_msg(p_manager, EVT_WARNING, " - truncating segment to %d\n",
1277 #endif /* USE_JPWL */
1278 /* Check possible overflow on size */
1279 if ((l_cblk->data_current_size + l_seg->newlen) < l_cblk->data_current_size) {
1280 opj_event_msg(p_manager, EVT_ERROR,
1281 "read: segment too long (%d) with current size (%d > %d) for codeblock %d (p=%d, b=%d, r=%d, c=%d)\n",
1282 l_seg->newlen, l_cblk->data_current_size, 0xFFFFFFFF - l_seg->newlen, cblkno,
1283 p_pi->precno, bandno, p_pi->resno, p_pi->compno);
1286 /* Check if the cblk->data have allocated enough memory */
1287 if ((l_cblk->data_current_size + l_seg->newlen) > l_cblk->data_max_size) {
1288 OPJ_BYTE* new_cblk_data = (OPJ_BYTE*) opj_realloc(l_cblk->data,
1289 l_cblk->data_current_size + l_seg->newlen);
1290 if (! new_cblk_data) {
1291 opj_free(l_cblk->data);
1292 l_cblk->data = NULL;
1293 l_cblk->data_max_size = 0;
1294 /* opj_event_msg(p_manager, EVT_ERROR, "Not enough memory to realloc code block cata!\n"); */
1297 l_cblk->data_max_size = l_cblk->data_current_size + l_seg->newlen;
1298 l_cblk->data = new_cblk_data;
1301 memcpy(l_cblk->data + l_cblk->data_current_size, l_current_data, l_seg->newlen);
1303 if (l_seg->numpasses == 0) {
1304 l_seg->data = &l_cblk->data;
1305 l_seg->dataindex = l_cblk->data_current_size;
1308 l_current_data += l_seg->newlen;
1309 l_seg->numpasses += l_seg->numnewpasses;
1310 l_cblk->numnewpasses -= l_seg->numnewpasses;
1312 l_seg->real_num_passes = l_seg->numpasses;
1313 l_cblk->data_current_size += l_seg->newlen;
1314 l_seg->len += l_seg->newlen;
1316 if (l_cblk->numnewpasses > 0) {
1320 } while (l_cblk->numnewpasses > 0);
1322 l_cblk->real_num_segs = l_cblk->numsegs;
1324 } /* next code_block */
1329 *(p_data_read) = (OPJ_UINT32)(l_current_data - p_src_data);
1335 static OPJ_BOOL opj_t2_skip_packet_data(opj_t2_t* p_t2,
1336 opj_tcd_tile_t *p_tile,
1337 opj_pi_iterator_t *p_pi,
1338 OPJ_UINT32 * p_data_read,
1339 OPJ_UINT32 p_max_length,
1340 opj_packet_info_t *pack_info,
1341 opj_event_mgr_t *p_manager)
1343 OPJ_UINT32 bandno, cblkno;
1344 OPJ_UINT32 l_nb_code_blocks;
1345 opj_tcd_band_t *l_band = 00;
1346 opj_tcd_cblk_dec_t* l_cblk = 00;
1347 opj_tcd_resolution_t* l_res =
1348 &p_tile->comps[p_pi->compno].resolutions[p_pi->resno];
1350 OPJ_ARG_NOT_USED(p_t2);
1351 OPJ_ARG_NOT_USED(pack_info);
1354 l_band = l_res->bands;
1356 for (bandno = 0; bandno < l_res->numbands; ++bandno) {
1357 opj_tcd_precinct_t *l_prc = &l_band->precincts[p_pi->precno];
1359 if ((l_band->x1 - l_band->x0 == 0) || (l_band->y1 - l_band->y0 == 0)) {
1364 l_nb_code_blocks = l_prc->cw * l_prc->ch;
1365 l_cblk = l_prc->cblks.dec;
1367 for (cblkno = 0; cblkno < l_nb_code_blocks; ++cblkno) {
1368 opj_tcd_seg_t *l_seg = 00;
1370 if (!l_cblk->numnewpasses) {
1376 if (!l_cblk->numsegs) {
1377 l_seg = l_cblk->segs;
1379 l_cblk->data_current_size = 0;
1381 l_seg = &l_cblk->segs[l_cblk->numsegs - 1];
1383 if (l_seg->numpasses == l_seg->maxpasses) {
1390 /* Check possible overflow then size */
1391 if (((*p_data_read + l_seg->newlen) < (*p_data_read)) ||
1392 ((*p_data_read + l_seg->newlen) > p_max_length)) {
1393 opj_event_msg(p_manager, EVT_ERROR,
1394 "skip: segment too long (%d) with max (%d) for codeblock %d (p=%d, b=%d, r=%d, c=%d)\n",
1395 l_seg->newlen, p_max_length, cblkno, p_pi->precno, bandno, p_pi->resno,
1401 /* we need here a j2k handle to verify if making a check to
1402 the validity of cblocks parameters is selected from user (-W) */
1404 /* let's check that we are not exceeding */
1405 if ((l_cblk->len + l_seg->newlen) > 8192) {
1406 opj_event_msg(p_manager, EVT_WARNING,
1407 "JPWL: segment too long (%d) for codeblock %d (p=%d, b=%d, r=%d, c=%d)\n",
1408 l_seg->newlen, cblkno, p_pi->precno, bandno, p_pi->resno, p_pi->compno);
1410 opj_event_msg(p_manager, EVT_ERROR, "JPWL: giving up\n");
1413 l_seg->newlen = 8192 - l_cblk->len;
1414 opj_event_msg(p_manager, EVT_WARNING, " - truncating segment to %d\n",
1419 #endif /* USE_JPWL */
1420 JAS_FPRINTF(stderr, "p_data_read (%d) newlen (%d) \n", *p_data_read,
1422 *(p_data_read) += l_seg->newlen;
1424 l_seg->numpasses += l_seg->numnewpasses;
1425 l_cblk->numnewpasses -= l_seg->numnewpasses;
1426 if (l_cblk->numnewpasses > 0) {
1430 } while (l_cblk->numnewpasses > 0);
1442 static OPJ_BOOL opj_t2_init_seg(opj_tcd_cblk_dec_t* cblk,
1447 opj_tcd_seg_t* seg = 00;
1448 OPJ_UINT32 l_nb_segs = index + 1;
1450 if (l_nb_segs > cblk->m_current_max_segs) {
1451 opj_tcd_seg_t* new_segs;
1452 cblk->m_current_max_segs += OPJ_J2K_DEFAULT_NB_SEGS;
1454 new_segs = (opj_tcd_seg_t*) opj_realloc(cblk->segs,
1455 cblk->m_current_max_segs * sizeof(opj_tcd_seg_t));
1457 opj_free(cblk->segs);
1459 cblk->m_current_max_segs = 0;
1460 /* opj_event_msg(p_manager, EVT_ERROR, "Not enough memory to initialize segment %d\n", l_nb_segs); */
1463 cblk->segs = new_segs;
1466 seg = &cblk->segs[index];
1467 memset(seg, 0, sizeof(opj_tcd_seg_t));
1469 if (cblksty & J2K_CCP_CBLKSTY_TERMALL) {
1471 } else if (cblksty & J2K_CCP_CBLKSTY_LAZY) {
1473 seg->maxpasses = 10;
1475 seg->maxpasses = (((seg - 1)->maxpasses == 1) ||
1476 ((seg - 1)->maxpasses == 10)) ? 2 : 1;
1479 seg->maxpasses = 109;