OpenJPH
Open-source implementation of JPEG2000 Part-15
Loading...
Searching...
No Matches
ojph_precinct.cpp
Go to the documentation of this file.
1//***************************************************************************/
2// This software is released under the 2-Clause BSD license, included
3// below.
4//
5// Copyright (c) 2019, Aous Naman
6// Copyright (c) 2019, Kakadu Software Pty Ltd, Australia
7// Copyright (c) 2019, The University of New South Wales, Australia
8//
9// Redistribution and use in source and binary forms, with or without
10// modification, are permitted provided that the following conditions are
11// met:
12//
13// 1. Redistributions of source code must retain the above copyright
14// notice, this list of conditions and the following disclaimer.
15//
16// 2. Redistributions in binary form must reproduce the above copyright
17// notice, this list of conditions and the following disclaimer in the
18// documentation and/or other materials provided with the distribution.
19//
20// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
21// IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
22// TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
23// PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
24// HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
25// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
26// TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
27// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
28// LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
29// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
30// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31//***************************************************************************/
32// This file is part of the OpenJPH software implementation.
33// File: ojph_precinct.cpp
34// Author: Aous Naman
35// Date: 28 August 2019
36//***************************************************************************/
37
38
39#include <climits>
40#include <cmath>
41
42#include "ojph_mem.h"
43#include "ojph_params.h"
45#include "ojph_precinct.h"
46#include "ojph_subband.h"
47#include "ojph_codeblock.h" // for coded_cb_header
49#include "ojph_bitbuffer_read.h"
50
51
52namespace ojph {
53
54 namespace local
55 {
56
58 struct tag_tree
59 {
60 void init(ui8* buf, ui32 *lev_idx, ui32 num_levels, size s, int init_val)
61 {
62 for (ui32 i = 0; i <= num_levels; ++i) //on extra level
63 levs[i] = buf + lev_idx[i];
64 for (ui32 i = num_levels + 1; i < 16; ++i)
65 levs[i] = (ui8*)INT_MAX; //make it crash on error
66 width = s.w;
67 height = s.h;
68 for (ui32 i = 0; i < num_levels; ++i)
69 {
70 ui32 size = 1u << ((num_levels - 1 - i) << 1);
71 memset(levs[i], init_val, size);
72 }
73 *levs[num_levels] = 0;
74 this->num_levels = num_levels;
75 }
76
77 ui8* get(ui32 x, ui32 y, ui32 lev)
78 {
79 return levs[lev] + (x + y * ((width + (1 << lev) - 1) >> lev));
80 }
81
83 ui8* levs[16]; // you cannot have this high number of levels
84 };
85
87 static inline ui32 log2ceil(ui32 x)
88 {
89 ui32 t = 31 - count_leading_zeros(x);
90 return t + (x & (x - 1) ? 1 : 0);
91 }
92
94 ui32 precinct::prepare_precinct(int tag_tree_size, ui32* lev_idx,
95 mem_elastic_allocator* elastic)
96 {
98 coded_lists *cur_coded_list = NULL;
99 ui32 cb_bytes = 0; //cb_bytes;
100 ui32 ph_bytes = 0; //precinct header size
101 int num_skipped_subbands = 0;
102 for (int s = 0; s < 4; ++s)
103 {
104 if (bands[s].empty)
105 continue;
106
107 if (cb_idxs[s].siz.w == 0 || cb_idxs[s].siz.h == 0)
108 continue;
109
110 ui32 num_levels = 1 +
111 ojph_max(log2ceil(cb_idxs[s].siz.w), log2ceil(cb_idxs[s].siz.h));
112
113 //create quad trees for inclusion and missing msbs
114 tag_tree inc_tag, inc_tag_flags, mmsb_tag, mmsb_tag_flags;
115 inc_tag.init(scratch, lev_idx, num_levels, cb_idxs[s].siz, 255);
116 inc_tag_flags.init(scratch + tag_tree_size,
117 lev_idx, num_levels, cb_idxs[s].siz, 0);
118 mmsb_tag.init(scratch + (tag_tree_size<<1),
119 lev_idx, num_levels, cb_idxs[s].siz, 255);
120 mmsb_tag_flags.init(scratch + (tag_tree_size<<1) + tag_tree_size,
121 lev_idx, num_levels, cb_idxs[s].siz, 0);
122 ui32 band_width = bands[s].num_blocks.w;
124 cp += cb_idxs[s].org.x + cb_idxs[s].org.y * band_width;
125 for (ui32 y = 0; y < cb_idxs[s].siz.h; ++y)
126 {
127 for (ui32 x = 0; x < cb_idxs[s].siz.w; ++x)
128 {
129 coded_cb_header *p = cp + x;
130 *inc_tag.get(x, y, 0) = (p->next_coded == NULL); //1 if true
131 *mmsb_tag.get(x, y, 0) = (ui8)p->missing_msbs;
132 }
133 cp += band_width;
134 }
135 for (ui32 lev = 1; lev < num_levels; ++lev)
136 {
137 ui32 height = (cb_idxs[s].siz.h + (1<<lev) - 1) >> lev;
138 ui32 width = (cb_idxs[s].siz.w + (1<<lev) - 1) >> lev;
139 for (ui32 y = 0; y < height; ++y)
140 {
141 for (ui32 x = 0; x < width; ++x)
142 {
143 ui8 t1, t2;
144 t1 = ojph_min(*inc_tag.get(x<<1, y<<1, lev-1),
145 *inc_tag.get((x<<1) + 1, y<<1, lev-1));
146 t2 = ojph_min(*inc_tag.get(x<<1, (y<<1) + 1, lev-1),
147 *inc_tag.get((x<<1) + 1, (y<<1) + 1, lev-1));
148 *inc_tag.get(x, y, lev) = ojph_min(t1, t2);
149 *inc_tag_flags.get(x, y, lev) = 0;
150 t1 = ojph_min(*mmsb_tag.get(x<<1, y<<1, lev-1),
151 *mmsb_tag.get((x<<1) + 1, y<<1, lev-1));
152 t2 = ojph_min(*mmsb_tag.get(x<<1, (y<<1) + 1, lev-1),
153 *mmsb_tag.get((x<<1) + 1, (y<<1) + 1, lev-1));
154 *mmsb_tag.get(x, y, lev) = ojph_min(t1, t2);
155 *mmsb_tag_flags.get(x, y, lev) = 0;
156 }
157 }
158 }
159 *inc_tag.get(0,0,num_levels) = 0;
160 *inc_tag_flags.get(0,0,num_levels) = 0;
161 *mmsb_tag.get(0,0,num_levels) = 0;
162 *mmsb_tag_flags.get(0,0,num_levels) = 0;
163 if (*inc_tag.get(0, 0, num_levels-1) != 0) //empty subband
164 {
165 if (coded) //non empty precinct, tag tree top is 0
166 bb_put_bits(&bb, 0, 1, elastic, cur_coded_list, ph_bytes);
167 else
168 ++num_skipped_subbands;
169 continue;
170 }
171 //now we are in a position to code
172 if (coded == NULL)
173 {
174 bb_init(&bb, elastic, cur_coded_list);
175 coded = cur_coded_list;
176 //store non empty packet
177 bb_put_bit(&bb, 1, elastic, cur_coded_list, ph_bytes);
178
179 // if the first one or two subbands are empty (has codeblocks but
180 // no data in them), we need to code them here.
181 bb_put_bits(&bb, 0, num_skipped_subbands, elastic, cur_coded_list,
182 ph_bytes);
183 num_skipped_subbands = 0; //this line is not needed
184 }
185
186 ui32 width = cb_idxs[s].siz.w;
187 ui32 height = cb_idxs[s].siz.h;
188 for (ui32 y = 0; y < height; ++y)
189 {
190 cp = bands[s].coded_cbs;
191 cp += cb_idxs[s].org.x + (y + cb_idxs[s].org.y) * band_width;
192 for (ui32 x = 0; x < width; ++x, ++cp)
193 {
194 //inclusion bits
195 for (ui32 cur_lev = num_levels; cur_lev > 0; --cur_lev)
196 {
197 ui32 levm1 = cur_lev - 1;
198 //check sent
199 if (*inc_tag_flags.get(x>>levm1, y>>levm1, levm1) == 0)
200 {
201 ui32 skipped = *inc_tag.get(x>>levm1, y>>levm1, levm1);
202 skipped -= *inc_tag.get(x>>cur_lev, y>>cur_lev, cur_lev);
203 assert(skipped <= 1); // for HTJ2K, this should 0 or 1
204 bb_put_bits(&bb, 1 - skipped, 1,
205 elastic, cur_coded_list, ph_bytes);
206 *inc_tag_flags.get(x>>levm1, y>>levm1, levm1) = 1;
207 }
208 if (*inc_tag.get(x>>levm1, y>>levm1, levm1) > 0)
209 break;
210 }
211
212 if (cp->num_passes == 0) //empty codeblock
213 continue;
214
215 //missing msbs
216 for (ui32 cur_lev = num_levels; cur_lev > 0; --cur_lev)
217 {
218 ui32 levm1 = cur_lev - 1;
219 //check sent
220 if (*mmsb_tag_flags.get(x>>levm1, y>>levm1, levm1) == 0)
221 {
222 int num_zeros = *mmsb_tag.get(x>>levm1, y>>levm1, levm1);
223 num_zeros -= *mmsb_tag.get(x>>cur_lev, y>>cur_lev, cur_lev);
224 bb_put_zeros(&bb, num_zeros,
225 elastic, cur_coded_list, ph_bytes);
226 bb_put_bits(&bb, 1, 1,
227 elastic, cur_coded_list, ph_bytes);
228 *mmsb_tag_flags.get(x>>levm1, y>>levm1, levm1) = 1;
229 }
230 }
231
232 //number of coding passes
233 switch (cp->num_passes)
234 {
235 case 3:
236 bb_put_bits(&bb, 12, 4, elastic, cur_coded_list, ph_bytes);
237 break;
238 case 2:
239 bb_put_bits(&bb, 2, 2, elastic, cur_coded_list, ph_bytes);
240 break;
241 case 1:
242 bb_put_bits(&bb, 0, 1, elastic, cur_coded_list, ph_bytes);
243 break;
244 default:
245 assert(0);
246 }
247
248 //pass lengths
249 //either one, two, or three passes, but only one or two lengths
250 int bits1 = 32 - (int)count_leading_zeros(cp->pass_length[0]);
251 int extra_bit = cp->num_passes > 2 ? 1 : 0; //for 2nd length
252 int bits2 = 0;
253 if (cp->num_passes > 1)
254 bits2 = 32 - (int)count_leading_zeros(cp->pass_length[1]);
255 int bits = ojph_max(bits1, bits2 - extra_bit) - 3;
256 bits = ojph_max(bits, 0);
257 bb_put_bits(&bb, 0xFFFFFFFEu, bits+1,
258 elastic, cur_coded_list, ph_bytes);
259
260 bb_put_bits(&bb, cp->pass_length[0], bits+3,
261 elastic, cur_coded_list, ph_bytes);
262 if (cp->num_passes > 1)
263 bb_put_bits(&bb, cp->pass_length[1], bits+3+extra_bit,
264 elastic, cur_coded_list, ph_bytes);
265
266 cb_bytes += cp->pass_length[0] + cp->pass_length[1];
267 }
268 }
269 }
270
271 if (coded)
272 {
273 bb_terminate(&bb);
274 ph_bytes += cur_coded_list->buf_size - cur_coded_list->avail_size;
275 }
276
277 return coded ? cb_bytes + ph_bytes : 1;
278 }
279
282 {
283 if (coded)
284 {
285 //write packet header
286 coded_lists *ccl = coded;
287 while (ccl)
288 {
289 file->write(ccl->buf, ccl->buf_size - ccl->avail_size);
290 ccl = ccl->next_list;
291 }
292
293 //write codeblocks
294 for (int s = 0; s < 4; ++s)
295 {
296 if (bands[s].empty)
297 continue;
298
299 ui32 band_width = bands[s].num_blocks.w;
300 ui32 width = cb_idxs[s].siz.w;
301 ui32 height = cb_idxs[s].siz.h;
302 for (ui32 y = 0; y < height; ++y)
303 {
305 cp += cb_idxs[s].org.x + (y + cb_idxs[s].org.y) * band_width;
306 for (ui32 x = 0; x < width; ++x, ++cp)
307 {
308 coded_lists *ccl = cp->next_coded;
309 while (ccl)
310 {
311 file->write(ccl->buf, ccl->buf_size - ccl->avail_size);
312 ccl = ccl->next_list;
313 }
314 }
315 }
316 }
317 }
318 else
319 {
320 //empty packet
321 char buf = 0x00;
322 file->write(&buf, 1);
323 }
324 }
325
326
328 void precinct::parse(int tag_tree_size, ui32* lev_idx,
329 mem_elastic_allocator *elastic,
330 ui32 &data_left, infile_base *file,
331 bool skipped)
332 {
333 assert(data_left > 0);
334 bit_read_buf bb;
335 bb_init(&bb, data_left, file);
336 if (may_use_sop)
337 bb_skip_sop(&bb);
338
339 if (bands[0].empty && bands[1].empty && bands[2].empty && bands[3].empty)
340 {
341 ui32 bit = 0;
342 bb_read_bit(&bb, bit);
344 assert(bit == 0);
345 return;
346 }
347
348 bool empty_packet = true;
349 for (int s = 0; s < 4; ++s)
350 {
351 if (bands[s].empty)
352 continue;
353
354 if (cb_idxs[s].siz.w == 0 || cb_idxs[s].siz.h == 0)
355 continue;
356
357 if (empty_packet) //one bit to check if the packet is empty
358 {
359 ui32 bit;
360 bb_read_bit(&bb, bit);
361 if (bit == 0) //empty packet
362 { bb_terminate(&bb, uses_eph); data_left = bb.bytes_left; return; }
363 empty_packet = false;
364 }
365
366 ui32 num_levels = 1 +
367 ojph_max(log2ceil(cb_idxs[s].siz.w), log2ceil(cb_idxs[s].siz.h));
368
369 //create quad trees for inclusion and missing msbs
370 tag_tree inc_tag, inc_tag_flags, mmsb_tag, mmsb_tag_flags;
371 inc_tag.init(scratch, lev_idx, num_levels, cb_idxs[s].siz, 0);
372 *inc_tag.get(0, 0, num_levels) = 0;
373 inc_tag_flags.init(scratch + tag_tree_size, lev_idx, num_levels,
374 cb_idxs[s].siz, 0);
375 *inc_tag_flags.get(0, 0, num_levels) = 0;
376 mmsb_tag.init(scratch + (tag_tree_size<<1), lev_idx, num_levels,
377 cb_idxs[s].siz, 0);
378 *mmsb_tag.get(0, 0, num_levels) = 0;
379 mmsb_tag_flags.init(scratch + (tag_tree_size<<1) + tag_tree_size,
380 lev_idx, num_levels, cb_idxs[s].siz, 0);
381 *mmsb_tag_flags.get(0, 0, num_levels) = 0;
382
383 //
384 ui32 band_width = bands[s].num_blocks.w;
385 ui32 width = cb_idxs[s].siz.w;
386 ui32 height = cb_idxs[s].siz.h;
387 for (ui32 y = 0; y < height; ++y)
388 {
390 cp += cb_idxs[s].org.x + (y + cb_idxs[s].org.y) * band_width;
391 for (ui32 x = 0; x < width; ++x, ++cp)
392 {
393 //process inclusion
394 bool empty_cb = false;
395 for (ui32 cl = num_levels; cl > 0; --cl)
396 {
397 ui32 cur_lev = cl - 1;
398 empty_cb = *inc_tag.get(x>>cur_lev, y>>cur_lev, cur_lev) == 1;
399 if (empty_cb)
400 break;
401 //check received
402 if (*inc_tag_flags.get(x>>cur_lev, y>>cur_lev, cur_lev) == 0)
403 {
404 ui32 bit;
405 if (bb_read_bit(&bb, bit) == false)
406 { data_left = 0; throw "error reading from file p1"; }
407 empty_cb = (bit == 0);
408 *inc_tag.get(x>>cur_lev, y>>cur_lev, cur_lev) = (ui8)(1 - bit);
409 *inc_tag_flags.get(x>>cur_lev, y>>cur_lev, cur_lev) = 1;
410 }
411 if (empty_cb)
412 break;
413 }
414
415 if (empty_cb)
416 continue;
417
418 //process missing msbs
419 ui32 mmsbs = 0;
420 for (ui32 levp1 = num_levels; levp1 > 0; --levp1)
421 {
422 ui32 cur_lev = levp1 - 1;
423 mmsbs = *mmsb_tag.get(x>>levp1, y>>levp1, levp1);
424 //check received
425 if (*mmsb_tag_flags.get(x>>cur_lev, y>>cur_lev, cur_lev) == 0)
426 {
427 ui32 bit = 0;
428 while (bit == 0)
429 {
430 if (bb_read_bit(&bb, bit) == false)
431 { data_left = 0; throw "error reading from file p2"; }
432 mmsbs += 1 - bit;
433 }
434 *mmsb_tag.get(x>>cur_lev, y>>cur_lev, cur_lev) = (ui8)mmsbs;
435 *mmsb_tag_flags.get(x>>cur_lev, y>>cur_lev, cur_lev) = 1;
436 }
437 }
438
439 if (mmsbs > cp->Kmax)
440 throw "error in parsing a tile header; "
441 "missing msbs are larger or equal to Kmax. The most likely "
442 "cause is a corruption in the bitstream.";
443 cp->missing_msbs = mmsbs;
444
445 //get number of passes
446 ui32 bit, num_passes = 1;
447 if (bb_read_bit(&bb, bit) == false)
448 { data_left = 0; throw "error reading from file p3"; }
449 if (bit)
450 {
451 num_passes = 2;
452 if (bb_read_bit(&bb, bit) == false)
453 { data_left = 0; throw "error reading from file p4"; }
454 if (bit)
455 {
456 if (bb_read_bits(&bb, 2, bit) == false)
457 { data_left = 0; throw "error reading from file p5"; }
458 num_passes = 3 + bit;
459 if (bit == 3)
460 {
461 if (bb_read_bits(&bb, 5, bit) == false)
462 { data_left = 0; throw "error reading from file p6"; }
463 num_passes = 6 + bit;
464 if (bit == 31)
465 {
466 if (bb_read_bits(&bb, 7, bit) == false)
467 { data_left = 0; throw "error reading from file p7"; }
468 num_passes = 37 + bit;
469 }
470 }
471 }
472 }
473 cp->num_passes = num_passes;
474
475 //parse pass lengths
476 //for one pass, one length, but for 2 or 3 passes, two lengths
477 int extra_bit = cp->num_passes > 2 ? 1 : 0;
478 int bits1 = 3;
479 bit = 1;
480 while (bit)
481 {
482 if (bb_read_bit(&bb, bit) == false)
483 { data_left = 0; throw "error reading from file p8"; }
484 bits1 += bit;
485 }
486
487 if (bb_read_bits(&bb, bits1, bit) == false)
488 { data_left = 0; throw "error reading from file p9"; }
489 if (bit < 2) {
490 throw "The cleanup segment of an HT codeblock cannot contain "
491 "less than 2 bytes";
492 }
493 if (bit >= 65535) {
494 throw "The cleanup segment of an HT codeblock must contain "
495 "less than 65535 bytes";
496 }
497 cp->pass_length[0] = bit;
498 if (num_passes > 1)
499 {
500 if (bb_read_bits(&bb, bits1 + extra_bit, bit) == false)
501 { data_left = 0; throw "error reading from file p10"; }
502 if (bit >= 2047) {
503 throw "The refinement segment (SigProp and MagRep passes) of "
504 "an HT codeblock must contain less than 2047 bytes";
505 }
506 cp->pass_length[1] = bit;
507 }
508 }
509 }
510 }
512 //read codeblock data
513 for (int s = 0; s < 4; ++s)
514 {
515 if (bands[s].empty)
516 continue;
517 ui32 band_width = bands[s].num_blocks.w;
518 ui32 width = cb_idxs[s].siz.w;
519 ui32 height = cb_idxs[s].siz.h;
520 for (ui32 y = 0; y < height; ++y)
521 {
523 cp += cb_idxs[s].org.x + (y + cb_idxs[s].org.y) * band_width;
524 for (ui32 x = 0; x < width; ++x, ++cp)
525 {
526 ui32 num_bytes = cp->pass_length[0] + cp->pass_length[1];
527 if (data_left)
528 {
529 if (num_bytes)
530 {
531 if (skipped)
532 { //no need to read
533 si64 cur_loc = file->tell();
534 ui32 t = ojph_min(num_bytes, bb.bytes_left);
536 ui32 bytes_read = (ui32)(file->tell() - cur_loc);
537 cp->pass_length[0] = cp->pass_length[1] = 0;
538 bb.bytes_left -= bytes_read;
539 assert(bytes_read == t || bb.bytes_left == 0);
540 }
541 else
542 {
543 if (!bb_read_chunk(&bb, num_bytes, cp->next_coded, elastic))
544 {
545 //no need to decode a broken codeblock
546 cp->pass_length[0] = cp->pass_length[1] = 0;
547 data_left = 0;
548 }
549 }
550 }
551 }
552 else
553 cp->pass_length[0] = cp->pass_length[1] = 0;
554 }
555 }
556 }
557 data_left = bb.bytes_left;
558 }
559
560 }
561}
virtual si64 tell()=0
coded_cb_header * coded_cbs
virtual size_t write(const void *ptr, size_t size)=0
static bool bb_read_chunk(bit_read_buf *bbp, ui32 num_bytes, coded_lists *&cur_coded_list, mem_elastic_allocator *elastic)
static bool bb_read_bit(bit_read_buf *bbp, ui32 &bit)
static bool bb_read_bits(bit_read_buf *bbp, int num_bits, ui32 &bits)
static bool bb_skip_sop(bit_read_buf *bbp)
static bool bb_terminate(bit_read_buf *bbp, bool uses_eph)
static ui32 log2ceil(ui32 x)
static void bb_put_zeros(bit_write_buf *bbp, int num_zeros, mem_elastic_allocator *elastic, coded_lists *&cur_coded_list, ui32 &ph_bytes)
static void bb_put_bits(bit_write_buf *bbp, ui32 data, int num_bits, mem_elastic_allocator *elastic, coded_lists *&cur_coded_list, ui32 &ph_bytes)
static void bb_init(bit_read_buf *bbp, ui32 bytes_left, infile_base *file)
static void bb_put_bit(bit_write_buf *bbp, ui32 bit, mem_elastic_allocator *elastic, coded_lists *&cur_coded_list, ui32 &ph_bytes)
int64_t si64
Definition ojph_defs.h:57
static ui32 count_leading_zeros(ui32 val)
Definition ojph_arch.h:199
uint32_t ui32
Definition ojph_defs.h:54
uint8_t ui8
Definition ojph_defs.h:50
#define ojph_max(a, b)
Definition ojph_defs.h:73
#define ojph_min(a, b)
Definition ojph_defs.h:76
coded_lists * next_list
Definition ojph_mem.h:197
void write(outfile_base *file)
ui32 prepare_precinct(int tag_tree_size, ui32 *lev_idx, mem_elastic_allocator *elastic)
void parse(int tag_tree_size, ui32 *lev_idx, mem_elastic_allocator *elastic, ui32 &data_left, infile_base *file, bool skipped)
ui8 * get(ui32 x, ui32 y, ui32 lev)
void init(ui8 *buf, ui32 *lev_idx, ui32 num_levels, size s, int init_val)
point org
Definition ojph_base.h:66