Grok  9.5.0
SparseCanvas.h
Go to the documentation of this file.
1 /*
2  * Copyright (C) 2016-2021 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 
52 #include <cstdint>
53 #include <algorithm>
54 
55 // SparseCanvas stores blocks in the canvas coordinate system. It covers the active sub-bands for
56 // all (reduced) resolutions
57 
58 namespace grk
59 {
61 {
62  public:
63  virtual ~ISparseCanvas() = default;
80  virtual bool read(uint8_t resno, eBandOrientation bandOrientation, grkRectU32 window,
81  int32_t* dest, const uint32_t dest_col_stride,
82  const uint32_t dest_line_stride, bool forgiving) = 0;
99  virtual bool write(uint8_t resno, eBandOrientation bandOrientation, grkRectU32 window,
100  const int32_t* src, const uint32_t src_col_stride,
101  const uint32_t src_line_stride, bool forgiving) = 0;
112  virtual bool alloc(grkRectU32 window, bool zeroOutBuffer) = 0;
113 };
115 {
116  SparseBlock(void) : data(nullptr) {}
118  {
119  delete[] data;
120  }
121  void alloc(uint32_t block_area, bool zeroOutBuffer)
122  {
123  data = new int32_t[block_area];
124  if(zeroOutBuffer)
125  memset(data, 0, block_area * sizeof(int32_t));
126  // else
127  // memset(data, 0xFF, block_area * sizeof(int32_t));
128  }
129  int32_t* data;
130 };
131 
132 template<uint32_t LBW, uint32_t LBH>
134 {
135  public:
144  : block_width(1 << LBW), block_height(1 << LBH), data_blocks(nullptr), bounds(bds)
145  {
146  if(!bounds.width() || !bounds.height() || !LBW || !LBH)
147  throw std::runtime_error("invalid window for sparse buffer");
148 
149  uint32_t grid_off_x = floordivpow2(bounds.x0, LBW);
150  uint32_t grid_off_y = floordivpow2(bounds.y0, LBH);
151  uint32_t grid_x = ceildivpow2<uint32_t>(bounds.x1, LBW);
152  uint32_t grid_y = ceildivpow2<uint32_t>(bounds.y1, LBH);
153  grid_bounds = grkRectU32(grid_off_x, grid_off_y, grid_x, grid_y);
154  auto block_count = grid_bounds.area();
155  data_blocks = new SparseBlock*[block_count];
156  for(uint64_t i = 0; i < block_count; ++i)
157  data_blocks[i] = nullptr;
158  }
159 
169  SparseCanvas(uint32_t width, uint32_t height) : SparseCanvas(grkRectU32(0, 0, width, height)) {}
171  {
172  if(data_blocks)
173  {
174  for(uint64_t i = 0; i < (uint64_t)grid_bounds.width() * grid_bounds.height(); i++)
175  {
176  delete(data_blocks[i]);
177  data_blocks[i] = nullptr;
178  }
179  delete[] data_blocks;
180  }
181  }
182  bool read(uint8_t resno, eBandOrientation bandOrientation, grkRectU32 window, int32_t* dest,
183  const uint32_t dest_col_stride, const uint32_t dest_line_stride, bool forgiving)
184  {
185  return read_or_write(resno, window, dest, dest_col_stride, dest_line_stride, forgiving,
186  true);
187  }
188  bool write(uint8_t resno, eBandOrientation bandOrientation, grkRectU32 window,
189  const int32_t* src, const uint32_t src_col_stride, const uint32_t src_line_stride,
190  bool forgiving)
191  {
192  return read_or_write(resno, window, (int32_t*)src, src_col_stride, src_line_stride,
193  forgiving, false);
194  }
195  bool alloc(grkRectU32 win, bool zeroOutBuffer)
196  {
198  return true;
199 
200  uint32_t y_incr = 0;
201  uint32_t block_y = win.y0 >> LBH;
202  for(uint32_t y = win.y0; y < win.y1; block_y++, y += y_incr)
203  {
204  y_incr = (y == win.y0) ? block_height - (win.y0 & (block_height - 1)) : block_height;
205  y_incr = (std::min<uint32_t>)(y_incr, win.y1 - y);
206  uint32_t block_x = win.x0 >> LBW;
207  uint32_t x_incr = 0;
208  for(uint32_t x = win.x0; x < win.x1; block_x++, x += x_incr)
209  {
210  x_incr = (x == win.x0) ? block_width - (win.x0 & (block_width - 1)) : block_width;
211  x_incr = (std::min<uint32_t>)(x_incr, win.x1 - x);
212  if(!grid_bounds.contains(grkPointU32(block_x, block_y)))
213  {
214  GRK_ERROR("sparse buffer : attempt to allocate a block (%d,%d) outside block "
215  "grid bounds",
216  block_x, block_y);
217  return false;
218  }
219  auto src_block = getBlock(block_x, block_y);
220  if(!src_block)
221  {
222  auto b = new SparseBlock();
223  b->alloc(block_width * block_height, zeroOutBuffer);
224  assert(grid_bounds.contains(grkPointU32(block_x, block_y)));
225  assert(b->data);
226  uint64_t index = (uint64_t)(block_y - grid_bounds.y0) * grid_bounds.width() +
227  (block_x - grid_bounds.x0);
228  data_blocks[index] = b;
229  }
230  }
231  }
232 
233  return true;
234  }
235 
236  private:
237  inline SparseBlock* getBlock(uint32_t block_x, uint32_t block_y)
238  {
239  uint64_t index =
240  (uint64_t)(block_y - grid_bounds.y0) * grid_bounds.width() + (block_x - grid_bounds.x0);
241  return data_blocks[index];
242  }
248  {
249  return !(win.x0 >= bounds.x1 || win.x1 <= win.x0 || win.x1 > bounds.x1 ||
250  win.y0 >= bounds.y1 || win.y1 <= win.y0 || win.y1 > bounds.y1);
251  }
252  bool read_or_write(uint8_t resno, grkRectU32 win, int32_t* buf, const uint32_t buf_col_stride,
253  const uint32_t buf_line_stride, bool forgiving, bool is_read_op)
254  {
255  if(!is_window_valid(win))
256  {
257  // fill the client buffer with zeros in this case
258  if(forgiving && is_read_op)
259  {
260  GRK_WARN("Sparse buffer @ res %d, attempt to read invalid window (%d,%d,%d,%d). "
261  "Filling with zeros.",
262  resno, win.x0, win.y0, win.x1, win.y1);
263  for(uint32_t y = win.y0; y < win.y1; ++y)
264  {
265  int32_t* bufPtr = buf + (y - win.y0) * buf_line_stride;
266  for(uint32_t x = win.x0; x < win.x1; ++x)
267  {
268  *bufPtr = 0;
269  bufPtr += buf_col_stride;
270  }
271  }
272  }
273  return forgiving;
274  }
275  // if (!buf)
276  // GRK_WARN("Empty block at %s, res: %d",win.boundsString().c_str(), resno);
277  const uint64_t line_stride = buf_line_stride;
278  const uint64_t col_stride = buf_col_stride;
279  uint32_t block_y = win.y0 >> LBH;
280  uint32_t y_incr = 0;
281  for(uint32_t y = win.y0; y < win.y1; block_y++, y += y_incr)
282  {
283  y_incr = (y == win.y0) ? block_height - (win.y0 & (block_height - 1)) : block_height;
284  uint32_t block_y_offset = block_height - y_incr;
285  y_incr = (std::min<uint32_t>)(y_incr, win.y1 - y);
286  uint32_t block_x = win.x0 >> LBW;
287  uint32_t x_incr = 0;
288  for(uint32_t x = win.x0; x < win.x1; block_x++, x += x_incr)
289  {
290  x_incr = (x == win.x0) ? block_width - (win.x0 & (block_width - 1)) : block_width;
291  uint32_t block_x_offset = block_width - x_incr;
292  x_incr = (std::min<uint32_t>)(x_incr, win.x1 - x);
293  if(!grid_bounds.contains(grkPointU32(block_x, block_y)))
294  {
295  GRK_ERROR("sparse buffer @ resno %d, Attempt to access a block (%d,%d) outside "
296  "block grid bounds",
297  resno, block_x, block_y);
298  return false;
299  }
300  auto src_block = getBlock(block_x, block_y);
301  // all blocks should be allocated first before read/write is called
302  if(!src_block)
303  {
304  GRK_WARN("sparse buffer @ resno %d, %s op: missing block (%d,%d,%d,%d) for %s "
305  "(%d,%d,%d,%d)",
306  resno, is_read_op ? "read" : "write",
307  bounds.x0 + block_x * block_width, bounds.y0 + block_y * block_height,
308  bounds.x0 + (block_x + 1) * block_width,
309  bounds.y0 + (block_y + 1) * block_height,
310  is_read_op ? "read" : "write", win.x0, win.y0, win.x1, win.y1);
311  continue;
312  }
313  if(is_read_op)
314  {
315  const int32_t* GRK_RESTRICT src_ptr =
316  src_block->data + ((uint64_t)block_y_offset << LBW) + block_x_offset;
317  int32_t* GRK_RESTRICT dest_ptr =
318  buf + (y - win.y0) * line_stride + (x - win.x0) * col_stride;
319  uint32_t y_ = y;
320  for(uint32_t j = 0; j < y_incr; j++)
321  {
322  uint64_t ind = 0;
323  for(uint32_t k = 0; k < x_incr; k++)
324  {
325 #ifdef GRK_DEBUG_VALGRIND
326  size_t val = grk_memcheck<int32_t>(src_ptr + k, 1);
327  if(val != grk_mem_ok)
328  GRK_ERROR("sparse buffer @resno %d, read block(%d,%d) : "
329  "uninitialized at location (%d,%d)",
330  resno, block_x, block_y, x + k, y_);
331 #endif
332  dest_ptr[ind] = src_ptr[k];
333  ind += col_stride;
334  }
335  dest_ptr += line_stride;
336  y_++;
337  src_ptr += block_width;
338  }
339  }
340  else
341  {
342  const int32_t* GRK_RESTRICT src_ptr = nullptr;
343  if(buf)
344  src_ptr = buf + (y - win.y0) * line_stride + (x - win.x0) * col_stride;
345  int32_t* GRK_RESTRICT dest_ptr =
346  src_block->data + ((uint64_t)block_y_offset << LBW) + block_x_offset;
347 
348  uint32_t y_ = y;
349  for(uint32_t j = 0; j < y_incr; j++)
350  {
351  uint64_t ind = 0;
352  for(uint32_t k = 0; k < x_incr; k++)
353  {
354 #ifdef GRK_DEBUG_VALGRIND
355  if(src_ptr)
356  {
357  grkPointU32 pt((uint32_t)(x + k), y_);
358  size_t val = grk_memcheck<int32_t>(src_ptr + ind, 1);
359  if(val != grk_mem_ok)
360  GRK_ERROR("sparse buffer @ resno %d, write block(%d,%d): "
361  "uninitialized at location (%d,%d)",
362  resno, block_x, block_y, x + k, y_);
363  }
364 #endif
365  dest_ptr[k] = src_ptr ? src_ptr[ind] : 0;
366  ind += col_stride;
367  }
368  if(src_ptr)
369  src_ptr += line_stride;
370  y_++;
371  dest_ptr += block_width;
372  }
373  }
374  }
375  }
376 
377  return true;
378  }
379 
380  private:
381  const uint32_t block_width;
382  const uint32_t block_height;
386 };
387 
388 } // namespace grk
Definition: SparseCanvas.h:61
virtual ~ISparseCanvas()=default
virtual bool alloc(grkRectU32 window, bool zeroOutBuffer)=0
Allocate all blocks for a rectangular window into the sparse buffer from a user buffer.
virtual bool read(uint8_t resno, eBandOrientation bandOrientation, grkRectU32 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 buffer into a user buffer.
virtual bool write(uint8_t resno, eBandOrientation bandOrientation, grkRectU32 window, 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 buffer from a user buffer.
Definition: SparseCanvas.h:134
grkRectU32 bounds
Definition: SparseCanvas.h:384
const uint32_t block_height
Definition: SparseCanvas.h:382
SparseCanvas(uint32_t width, uint32_t height)
SparseCanvas constructor.
Definition: SparseCanvas.h:169
bool is_window_valid(grkRectU32 win)
Returns whether window bounds are valid (non empty and within bounds)
Definition: SparseCanvas.h:247
SparseCanvas(grkRectU32 bds)
SparseCanvas constructor.
Definition: SparseCanvas.h:143
bool alloc(grkRectU32 win, bool zeroOutBuffer)
Allocate all blocks for a rectangular window into the sparse buffer from a user buffer.
Definition: SparseCanvas.h:195
SparseBlock * getBlock(uint32_t block_x, uint32_t block_y)
Definition: SparseCanvas.h:237
~SparseCanvas()
Definition: SparseCanvas.h:170
grkRectU32 grid_bounds
Definition: SparseCanvas.h:385
SparseBlock ** data_blocks
Definition: SparseCanvas.h:383
bool write(uint8_t resno, eBandOrientation bandOrientation, grkRectU32 window, 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 buffer from a user buffer.
Definition: SparseCanvas.h:188
bool read_or_write(uint8_t resno, grkRectU32 win, int32_t *buf, const uint32_t buf_col_stride, const uint32_t buf_line_stride, bool forgiving, bool is_read_op)
Definition: SparseCanvas.h:252
bool read(uint8_t resno, eBandOrientation bandOrientation, grkRectU32 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 buffer into a user buffer.
Definition: SparseCanvas.h:182
const uint32_t block_width
Definition: SparseCanvas.h:381
#define GRK_RESTRICT
Definition: grk_includes.h:77
Copyright (C) 2016-2021 Grok Image Compression Inc.
Definition: ICacheable.h:20
grkRect< uint32_t > grkRectU32
Definition: util.h:56
static uint32_t floordivpow2(uint32_t a, uint32_t b)
Divide an unsigned integer by a power of 2 and round downwards.
Definition: grk_intmath.h:48
void GRK_ERROR(const char *fmt,...)
Definition: logger.cpp:58
void GRK_WARN(const char *fmt,...)
Definition: logger.cpp:49
eBandOrientation
Definition: Subband.h:25
Definition: SparseCanvas.h:115
SparseBlock(void)
Definition: SparseCanvas.h:116
void alloc(uint32_t block_area, bool zeroOutBuffer)
Definition: SparseCanvas.h:121
int32_t * data
Definition: SparseCanvas.h:129
~SparseBlock()
Definition: SparseCanvas.h:117
T x1
Definition: util.h:96
T y0
Definition: util.h:96
uint64_t area(void) const
Definition: util.h:205
T width() const
Definition: util.h:209
bool contains(grkPoint< T > pt)
Definition: util.h:125
T height() const
Definition: util.h:213
T y1
Definition: util.h:96
T x0
Definition: util.h:96