OpenJPH
Open-source implementation of JPEG2000 Part-15
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 sst = num_bands == 3 ? 1 : 0;
102 int send = num_bands == 3 ? 4 : 1;
103 int num_skipped_subbands = 0;
104 for (int s = sst; s < send; ++s)
105 {
106 if (cb_idxs[s].siz.w == 0 || cb_idxs[s].siz.h == 0)
107 continue;
108
109 ui32 num_levels = 1 +
110 ojph_max(log2ceil(cb_idxs[s].siz.w), log2ceil(cb_idxs[s].siz.h));
111
112 //create quad trees for inclusion and missing msbs
113 tag_tree inc_tag, inc_tag_flags, mmsb_tag, mmsb_tag_flags;
114 inc_tag.init(scratch, lev_idx, num_levels, cb_idxs[s].siz, 255);
115 inc_tag_flags.init(scratch + tag_tree_size,
116 lev_idx, num_levels, cb_idxs[s].siz, 0);
117 mmsb_tag.init(scratch + (tag_tree_size<<1),
118 lev_idx, num_levels, cb_idxs[s].siz, 255);
119 mmsb_tag_flags.init(scratch + (tag_tree_size<<1) + tag_tree_size,
120 lev_idx, num_levels, cb_idxs[s].siz, 0);
121 ui32 band_width = bands[s].num_blocks.w;
123 cp += cb_idxs[s].org.x + cb_idxs[s].org.y * band_width;
124 for (ui32 y = 0; y < cb_idxs[s].siz.h; ++y)
125 {
126 for (ui32 x = 0; x < cb_idxs[s].siz.w; ++x)
127 {
128 coded_cb_header *p = cp + x;
129 *inc_tag.get(x, y, 0) = (p->next_coded == NULL); //1 if true
130 *mmsb_tag.get(x, y, 0) = (ui8)p->missing_msbs;
131 }
132 cp += band_width;
133 }
134 for (ui32 lev = 1; lev < num_levels; ++lev)
135 {
136 ui32 height = (cb_idxs[s].siz.h + (1<<lev) - 1) >> lev;
137 ui32 width = (cb_idxs[s].siz.w + (1<<lev) - 1) >> lev;
138 for (ui32 y = 0; y < height; ++y)
139 {
140 for (ui32 x = 0; x < width; ++x)
141 {
142 ui8 t1, t2;
143 t1 = ojph_min(*inc_tag.get(x<<1, y<<1, lev-1),
144 *inc_tag.get((x<<1) + 1, y<<1, lev-1));
145 t2 = ojph_min(*inc_tag.get(x<<1, (y<<1) + 1, lev-1),
146 *inc_tag.get((x<<1) + 1, (y<<1) + 1, lev-1));
147 *inc_tag.get(x, y, lev) = ojph_min(t1, t2);
148 *inc_tag_flags.get(x, y, lev) = 0;
149 t1 = ojph_min(*mmsb_tag.get(x<<1, y<<1, lev-1),
150 *mmsb_tag.get((x<<1) + 1, y<<1, lev-1));
151 t2 = ojph_min(*mmsb_tag.get(x<<1, (y<<1) + 1, lev-1),
152 *mmsb_tag.get((x<<1) + 1, (y<<1) + 1, lev-1));
153 *mmsb_tag.get(x, y, lev) = ojph_min(t1, t2);
154 *mmsb_tag_flags.get(x, y, lev) = 0;
155 }
156 }
157 }
158 *inc_tag.get(0,0,num_levels) = 0;
159 *inc_tag_flags.get(0,0,num_levels) = 0;
160 *mmsb_tag.get(0,0,num_levels) = 0;
161 *mmsb_tag_flags.get(0,0,num_levels) = 0;
162 if (*inc_tag.get(0, 0, num_levels-1) != 0) //empty subband
163 {
164 if (coded) //non empty precinct, tag tree top is 0
165 bb_put_bits(&bb, 0, 1, elastic, cur_coded_list, ph_bytes);
166 else
167 ++num_skipped_subbands;
168 continue;
169 }
170 //now we are in a position to code
171 if (coded == NULL)
172 {
173 bb_init(&bb, elastic, cur_coded_list);
174 coded = cur_coded_list;
175 //store non empty packet
176 bb_put_bit(&bb, 1, elastic, cur_coded_list, ph_bytes);
177
178 // if the first one or two subbands are empty (has codeblocks but
179 // no data in them), we need to code them here.
180 bb_put_bits(&bb, 0, num_skipped_subbands, elastic, cur_coded_list,
181 ph_bytes);
182 num_skipped_subbands = 0; //this line is not needed
183 }
184
185 ui32 width = cb_idxs[s].siz.w;
186 ui32 height = cb_idxs[s].siz.h;
187 for (ui32 y = 0; y < height; ++y)
188 {
189 cp = bands[s].coded_cbs;
190 cp += cb_idxs[s].org.x + (y + cb_idxs[s].org.y) * band_width;
191 for (ui32 x = 0; x < width; ++x, ++cp)
192 {
193 //inclusion bits
194 for (ui32 cur_lev = num_levels; cur_lev > 0; --cur_lev)
195 {
196 ui32 levm1 = cur_lev - 1;
197 //check sent
198 if (*inc_tag_flags.get(x>>levm1, y>>levm1, levm1) == 0)
199 {
200 ui32 skipped = *inc_tag.get(x>>levm1, y>>levm1, levm1);
201 skipped -= *inc_tag.get(x>>cur_lev, y>>cur_lev, cur_lev);
202 assert(skipped <= 1); // for HTJ2K, this should 0 or 1
203 bb_put_bits(&bb, 1 - skipped, 1,
204 elastic, cur_coded_list, ph_bytes);
205 *inc_tag_flags.get(x>>levm1, y>>levm1, levm1) = 1;
206 }
207 if (*inc_tag.get(x>>levm1, y>>levm1, levm1) > 0)
208 break;
209 }
210
211 if (cp->num_passes == 0) //empty codeblock
212 continue;
213
214 //missing msbs
215 for (ui32 cur_lev = num_levels; cur_lev > 0; --cur_lev)
216 {
217 ui32 levm1 = cur_lev - 1;
218 //check sent
219 if (*mmsb_tag_flags.get(x>>levm1, y>>levm1, levm1) == 0)
220 {
221 int num_zeros = *mmsb_tag.get(x>>levm1, y>>levm1, levm1);
222 num_zeros -= *mmsb_tag.get(x>>cur_lev, y>>cur_lev, cur_lev);
223 bb_put_bits(&bb, 1, num_zeros + 1,
224 elastic, cur_coded_list, ph_bytes);
225 *mmsb_tag_flags.get(x>>levm1, y>>levm1, levm1) = 1;
226 }
227 }
228
229 //number of coding passes
230 switch (cp->num_passes)
231 {
232 case 3:
233 bb_put_bits(&bb, 12, 4, elastic, cur_coded_list, ph_bytes);
234 break;
235 case 2:
236 bb_put_bits(&bb, 2, 2, elastic, cur_coded_list, ph_bytes);
237 break;
238 case 1:
239 bb_put_bits(&bb, 0, 1, elastic, cur_coded_list, ph_bytes);
240 break;
241 default:
242 assert(0);
243 }
244
245 //pass lengths
246 //either one, two, or three passes, but only one or two lengths
247 int bits1 = 32 - (int)count_leading_zeros(cp->pass_length[0]);
248 int extra_bit = cp->num_passes > 2 ? 1 : 0; //for 2nd length
249 int bits2 = 0;
250 if (cp->num_passes > 1)
251 bits2 = 32 - (int)count_leading_zeros(cp->pass_length[1]);
252 int bits = ojph_max(bits1, bits2 - extra_bit) - 3;
253 bits = ojph_max(bits, 0);
254 bb_put_bits(&bb, 0xFFFFFFFEu, bits+1,
255 elastic, cur_coded_list, ph_bytes);
256
257 bb_put_bits(&bb, cp->pass_length[0], bits+3,
258 elastic, cur_coded_list, ph_bytes);
259 if (cp->num_passes > 1)
260 bb_put_bits(&bb, cp->pass_length[1], bits+3+extra_bit,
261 elastic, cur_coded_list, ph_bytes);
262
263 cb_bytes += cp->pass_length[0] + cp->pass_length[1];
264 }
265 }
266 }
267
268 if (coded)
269 {
270 bb_terminate(&bb);
271 ph_bytes += cur_coded_list->buf_size - cur_coded_list->avail_size;
272 }
273
274 return coded ? cb_bytes + ph_bytes : 1;
275 }
276
279 {
280 if (coded)
281 {
282 //write packet header
283 coded_lists *ccl = coded;
284 while (ccl)
285 {
286 file->write(ccl->buf, ccl->buf_size - ccl->avail_size);
287 ccl = ccl->next_list;
288 }
289
290 //write codeblocks
291 int sst = num_bands == 3 ? 1 : 0;
292 int send = num_bands == 3 ? 4 : 1;
293 for (int s = sst; s < send; ++s)
294 {
295 ui32 band_width = bands[s].num_blocks.w;
296 ui32 width = cb_idxs[s].siz.w;
297 ui32 height = cb_idxs[s].siz.h;
298 for (ui32 y = 0; y < height; ++y)
299 {
301 cp += cb_idxs[s].org.x + (y + cb_idxs[s].org.y) * band_width;
302 for (ui32 x = 0; x < width; ++x, ++cp)
303 {
304 coded_lists *ccl = cp->next_coded;
305 while (ccl)
306 {
307 file->write(ccl->buf, ccl->buf_size - ccl->avail_size);
308 ccl = ccl->next_list;
309 }
310 }
311 }
312 }
313 }
314 else
315 {
316 //empty packet
317 char buf = 0x00;
318 file->write(&buf, 1);
319 }
320 }
321
322
324 void precinct::parse(int tag_tree_size, ui32* lev_idx,
325 mem_elastic_allocator *elastic,
326 ui32 &data_left, infile_base *file,
327 bool skipped)
328 {
329 assert(data_left > 0);
330 bit_read_buf bb;
331 bb_init(&bb, data_left, file);
332 if (may_use_sop)
333 bb_skip_sop(&bb);
334
335 int sst = num_bands == 3 ? 1 : 0;
336 int send = num_bands == 3 ? 4 : 1;
337 bool empty_packet = true;
338 for (int s = sst; s < send; ++s)
339 {
340 if (cb_idxs[s].siz.w == 0 || cb_idxs[s].siz.h == 0)
341 continue;
342
343 if (empty_packet) //one bit to check if the packet is empty
344 {
345 ui32 bit;
346 bb_read_bit(&bb, bit);
347 if (bit == 0) //empty packet
348 { bb_terminate(&bb, uses_eph); data_left = bb.bytes_left; return; }
349 empty_packet = false;
350 }
351
352 ui32 num_levels = 1 +
353 ojph_max(log2ceil(cb_idxs[s].siz.w), log2ceil(cb_idxs[s].siz.h));
354
355 //create quad trees for inclusion and missing msbs
356 tag_tree inc_tag, inc_tag_flags, mmsb_tag, mmsb_tag_flags;
357 inc_tag.init(scratch, lev_idx, num_levels, cb_idxs[s].siz, 0);
358 *inc_tag.get(0, 0, num_levels) = 0;
359 inc_tag_flags.init(scratch + tag_tree_size, lev_idx, num_levels,
360 cb_idxs[s].siz, 0);
361 *inc_tag_flags.get(0, 0, num_levels) = 0;
362 mmsb_tag.init(scratch + (tag_tree_size<<1), lev_idx, num_levels,
363 cb_idxs[s].siz, 0);
364 *mmsb_tag.get(0, 0, num_levels) = 0;
365 mmsb_tag_flags.init(scratch + (tag_tree_size<<1) + tag_tree_size,
366 lev_idx, num_levels, cb_idxs[s].siz, 0);
367 *mmsb_tag_flags.get(0, 0, num_levels) = 0;
368
369 //
370 ui32 band_width = bands[s].num_blocks.w;
371 ui32 width = cb_idxs[s].siz.w;
372 ui32 height = cb_idxs[s].siz.h;
373 for (ui32 y = 0; y < height; ++y)
374 {
376 cp += cb_idxs[s].org.x + (y + cb_idxs[s].org.y) * band_width;
377 for (ui32 x = 0; x < width; ++x, ++cp)
378 {
379 //process inclusion
380 bool empty_cb = false;
381 for (ui32 cl = num_levels; cl > 0; --cl)
382 {
383 ui32 cur_lev = cl - 1;
384 empty_cb = *inc_tag.get(x>>cur_lev, y>>cur_lev, cur_lev) == 1;
385 if (empty_cb)
386 break;
387 //check received
388 if (*inc_tag_flags.get(x>>cur_lev, y>>cur_lev, cur_lev) == 0)
389 {
390 ui32 bit;
391 if (bb_read_bit(&bb, bit) == false)
392 { data_left = 0; throw "error reading from file p1"; }
393 empty_cb = (bit == 0);
394 *inc_tag.get(x>>cur_lev, y>>cur_lev, cur_lev) = (ui8)(1 - bit);
395 *inc_tag_flags.get(x>>cur_lev, y>>cur_lev, cur_lev) = 1;
396 }
397 if (empty_cb)
398 break;
399 }
400
401 if (empty_cb)
402 continue;
403
404 //process missing msbs
405 ui32 mmsbs = 0;
406 for (ui32 levp1 = num_levels; levp1 > 0; --levp1)
407 {
408 ui32 cur_lev = levp1 - 1;
409 mmsbs = *mmsb_tag.get(x>>levp1, y>>levp1, levp1);
410 //check received
411 if (*mmsb_tag_flags.get(x>>cur_lev, y>>cur_lev, cur_lev) == 0)
412 {
413 ui32 bit = 0;
414 while (bit == 0)
415 {
416 if (bb_read_bit(&bb, bit) == false)
417 { data_left = 0; throw "error reading from file p2"; }
418 mmsbs += 1 - bit;
419 }
420 *mmsb_tag.get(x>>cur_lev, y>>cur_lev, cur_lev) = (ui8)mmsbs;
421 *mmsb_tag_flags.get(x>>cur_lev, y>>cur_lev, cur_lev) = 1;
422 }
423 }
424
425 if (mmsbs > cp->Kmax)
426 throw "error in parsing a tile header; "
427 "missing msbs are larger or equal to Kmax. The most likely "
428 "cause is a corruption in the bitstream.";
429 cp->missing_msbs = mmsbs;
430
431 //get number of passes
432 ui32 bit, num_passes = 1;
433 if (bb_read_bit(&bb, bit) == false)
434 { data_left = 0; throw "error reading from file p3"; }
435 if (bit)
436 {
437 num_passes = 2;
438 if (bb_read_bit(&bb, bit) == false)
439 { data_left = 0; throw "error reading from file p4"; }
440 if (bit)
441 {
442 if (bb_read_bits(&bb, 2, bit) == false)
443 { data_left = 0; throw "error reading from file p5"; }
444 num_passes = 3 + bit;
445 if (bit == 3)
446 {
447 if (bb_read_bits(&bb, 5, bit) == false)
448 { data_left = 0; throw "error reading from file p6"; }
449 num_passes = 6 + bit;
450 if (bit == 31)
451 {
452 if (bb_read_bits(&bb, 7, bit) == false)
453 { data_left = 0; throw "error reading from file p7"; }
454 num_passes = 37 + bit;
455 }
456 }
457 }
458 }
459 cp->num_passes = num_passes;
460
461 //parse pass lengths
462 //for one pass, one length, but for 2 or 3 passes, two lengths
463 int extra_bit = cp->num_passes > 2 ? 1 : 0;
464 int bits1 = 3;
465 bit = 1;
466 while (bit)
467 {
468 if (bb_read_bit(&bb, bit) == false)
469 { data_left = 0; throw "error reading from file p8"; }
470 bits1 += bit;
471 }
472
473 if (bb_read_bits(&bb, bits1, bit) == false)
474 { data_left = 0; throw "error reading from file p9"; }
475 if (bit < 2) {
476 throw "The cleanup segment of an HT codeblock cannot contain "
477 "less than 2 bytes";
478 }
479 if (bit >= 65535) {
480 throw "The cleanup segment of an HT codeblock must contain "
481 "less than 65535 bytes";
482 }
483 cp->pass_length[0] = bit;
484 if (num_passes > 1)
485 {
486 if (bb_read_bits(&bb, bits1 + extra_bit, bit) == false)
487 { data_left = 0; throw "error reading from file p10"; }
488 if (bit >= 2047) {
489 throw "The refinement segment (SigProp and MagRep passes) of "
490 "an HT codeblock must contain less than 2047 bytes";
491 }
492 cp->pass_length[1] = bit;
493 }
494 }
495 }
496 }
498 //read codeblock data
499 for (int s = sst; s < send; ++s)
500 {
501 ui32 band_width = bands[s].num_blocks.w;
502 ui32 width = cb_idxs[s].siz.w;
503 ui32 height = cb_idxs[s].siz.h;
504 for (ui32 y = 0; y < height; ++y)
505 {
507 cp += cb_idxs[s].org.x + (y + cb_idxs[s].org.y) * band_width;
508 for (ui32 x = 0; x < width; ++x, ++cp)
509 {
510 ui32 num_bytes = cp->pass_length[0] + cp->pass_length[1];
511 if (data_left)
512 {
513 if (num_bytes)
514 {
515 if (skipped)
516 { //no need to read
517 si64 cur_loc = file->tell();
518 ui32 t = ojph_min(num_bytes, bb.bytes_left);
520 ui32 bytes_read = (ui32)(file->tell() - cur_loc);
521 cp->pass_length[0] = cp->pass_length[1] = 0;
522 bb.bytes_left -= bytes_read;
523 assert(bytes_read == t || bb.bytes_left == 0);
524 }
525 else
526 {
527 if (!bb_read_chunk(&bb, num_bytes, cp->next_coded, elastic))
528 {
529 //no need to decode a broken codeblock
530 cp->pass_length[0] = cp->pass_length[1] = 0;
531 data_left = 0;
532 }
533 }
534 }
535 }
536 else
537 cp->pass_length[0] = cp->pass_length[1] = 0;
538 }
539 }
540 }
541 data_left = bb.bytes_left;
542 }
543
544 }
545}
virtual si64 tell()=0
coded_cb_header * coded_cbs
Definition: ojph_subband.h:96
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_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:130
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:170
void write(outfile_base *file)
coded_lists * coded
Definition: ojph_precinct.h:75
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)
size siz
Definition: ojph_base.h:67
point org
Definition: ojph_base.h:66
ui32 w
Definition: ojph_base.h:50
ui32 h
Definition: ojph_base.h:51