Grok  7.6.2
SparseBuffer.h
Go to the documentation of this file.
1 /*
2  * Copyright (C) 2016-2020 Grok Image Compression Inc.
3  *
4  * This source code is free software: you can redistribute it and/or modify
5  * it under the terms of the GNU Affero General Public License, version 3,
6  * as published by the Free Software Foundation.
7  *
8  * This source code is distributed in the hope that it will be useful,
9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11  * GNU Affero General Public License for more details.
12  *
13  * You should have received a copy of the GNU Affero General Public License
14  * along with this program. If not, see <http://www.gnu.org/licenses/>.
15  *
16  *
17  * This source code incorporates work covered by the following copyright and
18  * permission notice:
19  *
20  * The copyright in this software is being made available under the 2-clauses
21  * BSD License, included below. This software may be subject to other third
22  * party and contributor rights, including patent rights, and no such rights
23  * are granted under this license.
24  *
25  * Copyright (c) 2017, IntoPix SA <contact@intopix.com>
26  * All rights reserved.
27  *
28  * Redistribution and use in source and binary forms, with or without
29  * modification, are permitted provided that the following conditions
30  * are met:
31  * 1. Redistributions of source code must retain the above copyright
32  * notice, this list of conditions and the following disclaimer.
33  * 2. Redistributions in binary form must reproduce the above copyright
34  * notice, this list of conditions and the following disclaimer in the
35  * documentation and/or other materials provided with the distribution.
36  *
37  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS `AS IS'
38  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
39  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
40  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
41  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
42  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
43  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
44  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
45  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
46  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
47  * POSSIBILITY OF SUCH DAMAGE.
48  */
49 
50 #pragma once
51 
67 
68 #include <cstdint>
69 
70 namespace grk {
71 
73 public:
74 
75  virtual ~ISparseBuffer(){};
76 
92  virtual bool read(uint32_t x0,
93  uint32_t y0,
94  uint32_t x1,
95  uint32_t y1,
96  int32_t* dest,
97  const uint32_t dest_col_stride,
98  const uint32_t dest_line_stride,
99  bool forgiving) = 0;
100 
113  virtual bool read(grk_rect_u32 window,
114  int32_t* dest,
115  const uint32_t dest_col_stride,
116  const uint32_t dest_line_stride,
117  bool forgiving) = 0;
118 
119 
135  virtual bool write(uint32_t x0,
136  uint32_t y0,
137  uint32_t x1,
138  uint32_t y1,
139  const int32_t* src,
140  const uint32_t src_col_stride,
141  const uint32_t src_line_stride,
142  bool forgiving) = 0;
143 
144 
154  virtual bool alloc( grk_rect_u32 window) = 0;
155 
156 
157 };
158 
159 template<uint32_t LBW, uint32_t LBH> class SparseBuffer : public ISparseBuffer {
160 
161 public:
162 
170  SparseBuffer(uint32_t width,uint32_t height) : SparseBuffer(grk_rect_u32(0,0,width,height))
171  {}
172 
173 
181  block_height(1<<LBH),
182  data_blocks(nullptr),
183  bounds(bds)
184  {
185  if (!bounds.width() || !bounds.height() || !LBW || !LBH) {
186  throw std::runtime_error("invalid window for sparse array");
187  }
188  uint32_t grid_off_x = uint_floordivpow2(bounds.x0, LBW);
189  uint32_t grid_off_y = uint_floordivpow2(bounds.y0, LBH);
190  uint32_t grid_width = ceildivpow2<uint32_t>(bounds.width(), LBW);
191  uint32_t grid_height = ceildivpow2<uint32_t>(bounds.height(), LBH);
192  grid_bounds = grk_rect_u32(grid_off_x,
193  grid_off_y,
194  grid_off_x+grid_width,
195  grid_off_y + grid_height);
196  auto block_count = grid_bounds.area();
197  data_blocks = new int32_t*[block_count];
198  for (uint64_t i = 0; i < block_count; ++i)
199  data_blocks[i] = nullptr;
200 
201  }
202 
207  {
208  if (data_blocks) {
209  for (uint64_t i = 0; i < (uint64_t)grid_bounds.width() * grid_bounds.height(); i++){
210  grk_free(data_blocks[i]);
211  data_blocks[i] = nullptr;
212  }
213  delete[] data_blocks;
214  }
215  }
216  bool read(uint32_t x0,
217  uint32_t y0,
218  uint32_t x1,
219  uint32_t y1,
220  int32_t* dest,
221  const uint32_t dest_col_stride,
222  const uint32_t dest_line_stride,
223  bool forgiving)
224  {
225  return read_or_write( x0, y0, x1, y1,
226  dest,
227  dest_col_stride,
228  dest_line_stride,
229  forgiving,
230  true);
231  }
232 
233  bool read(grk_rect_u32 window,
234  int32_t* dest,
235  const uint32_t dest_col_stride,
236  const uint32_t dest_line_stride,
237  bool forgiving)
238  {
239  return read(window.x0,
240  window.y0,
241  window.x1,
242  window.y1,
243  dest,
244  dest_col_stride,
245  dest_line_stride,
246  forgiving);
247  }
248 
249  bool write(uint32_t x0,
250  uint32_t y0,
251  uint32_t x1,
252  uint32_t y1,
253  const int32_t* src,
254  const uint32_t src_col_stride,
255  const uint32_t src_line_stride,
256  bool forgiving)
257  {
258  return read_or_write(x0, y0, x1, y1,
259  (int32_t*)src,
260  src_col_stride,
261  src_line_stride,
262  forgiving,
263  false);
264  }
265 
266  bool alloc( grk_rect_u32 window){
267  return alloc(window.x0, window.y0, window.x1, window.y1);
268  }
269 private:
270 
271  bool alloc( uint32_t x0,
272  uint32_t y0,
273  uint32_t x1,
274  uint32_t y1){
275  if (!SparseBuffer::is_window_valid(x0, y0, x1, y1))
276  return true;
277 
278  uint32_t y_incr = 0;
279  uint32_t block_y = y0 >> LBH;
280  for (uint32_t y = y0; y < y1; block_y ++, y += y_incr) {
281  y_incr = (y == y0) ? block_height - (y0 & (block_height-1)) : block_height;
282  y_incr = min<uint32_t>(y_incr, y1 - y);
283  uint32_t block_x = x0 >> LBW;
284  uint32_t x_incr = 0;
285  for (uint32_t x = x0; x < x1; block_x ++, x += x_incr) {
286  x_incr = (x == x0) ? block_width - (x0 & (block_width-1)) : block_width;
287  x_incr = min<uint32_t>(x_incr, x1 - x);
288  if (!grid_bounds.contains(grk_pt(block_x,block_y))){
289  GRK_ERROR("Attempt to allocate a block (%d,%d) outside block grid bounds", block_x, block_y);
290  return false;
291  }
292  auto src_block = getBlock(block_x, block_y);
293  if (!src_block) {
294  const uint32_t block_area = block_width*block_height;
295  // note: we need to zero out each source block, in case
296  // some code blocks are missing from the compressed stream.
297  // In this case, zero is the best default value for the block.
298  src_block = (int32_t*) grk_calloc(block_area, sizeof(int32_t));
299  if (!src_block) {
300  GRK_ERROR("SparseBuffer: Out of memory");
301  return false;
302  }
303  setBlock(block_x, block_y, src_block);
304  }
305  }
306  }
307 
308  return true;
309  }
310 
311  inline int32_t* getBlock(uint32_t block_x, uint32_t block_y){
312  return data_blocks[(uint64_t)(block_y - grid_bounds.y0) * grid_bounds.width() + (block_x - grid_bounds.x0)];
313  }
314  inline void setBlock(uint32_t block_x, uint32_t block_y, int32_t* block){
315  assert(grid_bounds.contains(grk_pt(block_x,block_y)));
316  data_blocks[(uint64_t)(block_y - grid_bounds.y0)* grid_bounds.width() + (block_x - grid_bounds.x0)] = block;
317  }
325  bool is_window_valid(uint32_t x0,
326  uint32_t y0,
327  uint32_t x1,
328  uint32_t y1){
329  return !(x0 >= bounds.width() || x1 <= x0 || x1 > bounds.width() ||
330  y0 >= bounds.height() || y1 <= y0 || y1 > bounds.height());
331  }
332 
333  bool read_or_write(uint32_t x0,
334  uint32_t y0,
335  uint32_t x1,
336  uint32_t y1,
337  int32_t* buf,
338  const uint32_t buf_col_stride,
339  const uint32_t buf_line_stride,
340  bool forgiving,
341  bool is_read_op){
342  if (!is_window_valid(x0, y0, x1, y1))
343  return forgiving;
344 
345  const uint64_t line_stride = buf_line_stride;
346  const uint64_t col_stride = buf_col_stride;
347  uint32_t block_y = y0 >> LBH;
348  uint32_t y_incr = 0;
349  for (uint32_t y = y0; y < y1; block_y ++, y += y_incr) {
350  y_incr = (y == y0) ? block_height - (y0 & (block_height-1)) : block_height;
351  uint32_t block_y_offset = block_height - y_incr;
352  y_incr = min<uint32_t>(y_incr, y1 - y);
353  uint32_t block_x = x0 >> LBW;
354  uint32_t x_incr = 0;
355  for (uint32_t x = x0; x < x1; block_x ++, x += x_incr) {
356  x_incr = (x == x0) ? block_width - (x0 & (block_width-1) ) : block_width;
357  uint32_t block_x_offset = block_width - x_incr;
358  x_incr = min<uint32_t>(x_incr, x1 - x);
359  if (!grid_bounds.contains(grk_pt(block_x,block_y))){
360  GRK_ERROR("Attempt to access a block (%d,%d) outside block grid bounds", block_x, block_y);
361  return false;
362  }
363  auto src_block = getBlock(block_x, block_y);
364  //all blocks should be allocated first before read/write is called
365  if (!src_block){
366  GRK_ERROR("Sparse array: missing block (%d,%d,%d,%d) for %s (%d,%d,%d,%d)",
367  block_x*block_width,
368  block_y*block_height,
369  block_x*block_width + x_incr,
370  block_y*block_height + y_incr,
371  is_read_op ? "read" : "write",
372  x0,y0,x1,y1);
373  //assert(src_block);
375  }
376  if (is_read_op) {
377  const int32_t* GRK_RESTRICT src_ptr =
378  src_block + ((uint64_t)block_y_offset << LBW) + block_x_offset;
379  int32_t* GRK_RESTRICT dest_ptr = buf + (y - y0) * line_stride +
380  (x - x0) * col_stride;
381  for (uint32_t j = 0; j < y_incr; j++) {
382  uint64_t ind = 0;
383  for (uint32_t k = 0; k < x_incr; k++){
384  dest_ptr[ind] = src_ptr[k];
385  ind += col_stride;
386  }
387  dest_ptr += line_stride;
388  src_ptr += block_width;
389  }
390  } else {
391  const int32_t* GRK_RESTRICT src_ptr = buf + (y - y0) * line_stride + (x - x0) * col_stride;
392  int32_t* GRK_RESTRICT dest_ptr = src_block + ((uint64_t)block_y_offset << LBW) + block_x_offset;
393 
394  for (uint32_t j = 0; j < y_incr; j++) {
395  uint64_t ind = 0;
396  for (uint32_t k = 0; k < x_incr; k++) {
397  dest_ptr[k] = src_ptr[ind];
398  ind += col_stride;
399  }
400  src_ptr += line_stride;
401  dest_ptr += block_width;
402  }
403  }
404  }
405  }
406 
407  return true;
408  }
409 private:
410  const uint32_t block_width;
411  const uint32_t block_height;
412  int32_t** data_blocks;
415 };
416 
417 }
418 
grk::SparseBuffer::bounds
grk_rect_u32 bounds
Definition: SparseBuffer.h:413
grk::SparseBuffer::read
bool read(uint32_t x0, uint32_t y0, uint32_t x1, uint32_t y1, int32_t *dest, const uint32_t dest_col_stride, const uint32_t dest_line_stride, bool forgiving)
Read the content of a rectangular window of the sparse array into a user buffer.
Definition: SparseBuffer.h:216
grk::grk_point< uint32_t >
grk::SparseBuffer::SparseBuffer
SparseBuffer(grk_rect_u32 bds)
Creates a new sparse array.
Definition: SparseBuffer.h:180
grk::grk_rectangle< uint32_t >
grk::grk_rectangle::height
T height() const
Definition: util.h:165
grk::ISparseBuffer
Definition: SparseBuffer.h:72
grk::SparseBuffer::alloc
bool alloc(uint32_t x0, uint32_t y0, uint32_t x1, uint32_t y1)
Definition: SparseBuffer.h:271
grk::ISparseBuffer::~ISparseBuffer
virtual ~ISparseBuffer()
Definition: SparseBuffer.h:75
grk::SparseBuffer::alloc
bool alloc(grk_rect_u32 window)
Allocate all blocks for a rectangular window into the sparse array from a user buffer.
Definition: SparseBuffer.h:266
grk::SparseBuffer::block_height
const uint32_t block_height
Definition: SparseBuffer.h:411
grk::grk_calloc
void * grk_calloc(size_t num, size_t size)
Allocate a memory block with elements initialized to 0.
Definition: MemManager.cpp:111
grk::uint_floordivpow2
static uint32_t uint_floordivpow2(uint32_t a, uint32_t b)
Divide an unsigned integer by a power of 2 and round downwards.
Definition: grk_intmath.h:55
grk::SparseBuffer::is_window_valid
bool is_window_valid(uint32_t x0, uint32_t y0, uint32_t x1, uint32_t y1)
Returns whether window bounds are valid (non empty and within array bounds)
Definition: SparseBuffer.h:325
grk::SparseBuffer::read_or_write
bool read_or_write(uint32_t x0, uint32_t y0, uint32_t x1, uint32_t y1, int32_t *buf, const uint32_t buf_col_stride, const uint32_t buf_line_stride, bool forgiving, bool is_read_op)
Definition: SparseBuffer.h:333
grk::grk_rectangle::x1
T x1
Definition: util.h:76
grk::grk_free
void grk_free(void *ptr)
Deallocates or frees a memory block.
Definition: MemManager.cpp:141
grk::SparseBuffer::getBlock
int32_t * getBlock(uint32_t block_x, uint32_t block_y)
Definition: SparseBuffer.h:311
grk::SparseBuffer
Definition: SparseBuffer.h:159
grk::SparseBuffer::setBlock
void setBlock(uint32_t block_x, uint32_t block_y, int32_t *block)
Definition: SparseBuffer.h:314
grk::SparseBuffer::grid_bounds
grk_rect_u32 grid_bounds
Definition: SparseBuffer.h:414
grk::grk_rectangle::width
T width() const
Definition: util.h:162
grk::grk_rectangle::contains
bool contains(grk_point< T > pt)
Definition: util.h:97
grk::SparseBuffer::~SparseBuffer
~SparseBuffer()
Frees a sparse array.
Definition: SparseBuffer.h:206
grk::ISparseBuffer::write
virtual bool write(uint32_t x0, uint32_t y0, uint32_t x1, uint32_t y1, const int32_t *src, const uint32_t src_col_stride, const uint32_t src_line_stride, bool forgiving)=0
Write the content of a rectangular window into the sparse array from a user buffer.
grk::ISparseBuffer::alloc
virtual bool alloc(grk_rect_u32 window)=0
Allocate all blocks for a rectangular window into the sparse array from a user buffer.
grk::ISparseBuffer::read
virtual bool read(grk_rect_u32 window, int32_t *dest, const uint32_t dest_col_stride, const uint32_t dest_line_stride, bool forgiving)=0
Read the content of a rectangular window of the sparse array into a user buffer.
grk::SparseBuffer::data_blocks
int32_t ** data_blocks
Definition: SparseBuffer.h:412
grk
Copyright (C) 2016-2020 Grok Image Compression Inc.
Definition: BitIO.cpp:23
grk::grk_rectangle::area
uint64_t area(void) const
Definition: util.h:159
grk::grk_rect_u32
grk_rectangle< uint32_t > grk_rect_u32
Definition: util.h:48
grk::SparseBuffer::SparseBuffer
SparseBuffer(uint32_t width, uint32_t height)
Creates a new sparse array.
Definition: SparseBuffer.h:170
grk::SparseBuffer::read
bool read(grk_rect_u32 window, int32_t *dest, const uint32_t dest_col_stride, const uint32_t dest_line_stride, bool forgiving)
Read the content of a rectangular window of the sparse array into a user buffer.
Definition: SparseBuffer.h:233
grk::SparseBuffer::block_width
const uint32_t block_width
Definition: SparseBuffer.h:410
grk::ISparseBuffer::read
virtual bool read(uint32_t x0, uint32_t y0, uint32_t x1, uint32_t y1, int32_t *dest, const uint32_t dest_col_stride, const uint32_t dest_line_stride, bool forgiving)=0
Read the content of a rectangular window of the sparse array into a user buffer.
GRK_RESTRICT
#define GRK_RESTRICT
Definition: grk_includes.h:101
grk::grk_rectangle::x0
T x0
Definition: util.h:76
grk::grk_rectangle::y1
T y1
Definition: util.h:76
grk::MissingSparseBlockException
Definition: grk_exceptions.h:36
grk::grk_rectangle::y0
T y0
Definition: util.h:76
grk::GRK_ERROR
void GRK_ERROR(const char *fmt,...)
Definition: logger.cpp:57
grk::SparseBuffer::write
bool write(uint32_t x0, uint32_t y0, uint32_t x1, uint32_t y1, const int32_t *src, const uint32_t src_col_stride, const uint32_t src_line_stride, bool forgiving)
Write the content of a rectangular window into the sparse array from a user buffer.
Definition: SparseBuffer.h:249