Grok  7.6.6
SparseBuffer.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 
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 struct SparseBlock{
158  SparseBlock(void) : data(nullptr)
159  {}
161  delete[] data;
162  }
163  bool alloc(uint32_t block_area){
164  data = new int32_t[block_area];
165  // note: we need to zero out each source block, in case
166  // some code blocks are missing from the compressed stream.
167  // In this case, zero is the best default value for the block.
168  memset(data, 0, block_area * sizeof(int32_t));
169  return true;
170  }
171  int32_t *data;
172 };
173 
174 template<uint32_t LBW, uint32_t LBH> class SparseBuffer : public ISparseBuffer {
175 
176 public:
177 
185  block_height(1<<LBH),
186  data_blocks(nullptr),
187  bounds(bds)
188  {
189  if (!bounds.width() || !bounds.height() || !LBW || !LBH) {
190  throw std::runtime_error("invalid window for sparse buffer");
191  }
192  uint32_t grid_off_x = uint_floordivpow2(bounds.x0, LBW);
193  uint32_t grid_off_y = uint_floordivpow2(bounds.y0, LBH);
194  uint32_t grid_width = ceildivpow2<uint32_t>(bounds.width(), LBW);
195  uint32_t grid_height = ceildivpow2<uint32_t>(bounds.height(), LBH);
196  grid_bounds = grk_rect_u32(grid_off_x,
197  grid_off_y,
198  grid_off_x+grid_width,
199  grid_off_y + grid_height);
200  auto block_count = grid_bounds.area();
201  data_blocks = new SparseBlock*[block_count];
202  for (uint64_t i = 0; i < block_count; ++i){
203  data_blocks[i] = nullptr;
204  }
205 
206 #ifdef GRK_DEBUG_VALGRIND
207  validate = grk_rect_u32(278,50,288,51);
208 #endif
209  }
210 
211 
219  SparseBuffer(uint32_t width,uint32_t height) : SparseBuffer(grk_rect_u32(0,0,width,height))
220  {}
221 
222 
227  {
228  if (data_blocks) {
229  for (uint64_t i = 0; i < (uint64_t)grid_bounds.width() * grid_bounds.height(); i++){
230  delete (data_blocks[i]);
231  data_blocks[i] = nullptr;
232  }
233  delete[] data_blocks;
234  }
235  }
236  bool read(uint32_t x0,
237  uint32_t y0,
238  uint32_t x1,
239  uint32_t y1,
240  int32_t* dest,
241  const uint32_t dest_col_stride,
242  const uint32_t dest_line_stride,
243  bool forgiving)
244  {
245  return read_or_write( x0, y0, x1, y1,
246  dest,
247  dest_col_stride,
248  dest_line_stride,
249  forgiving,
250  true);
251  }
252 
253  bool read(grk_rect_u32 window,
254  int32_t* dest,
255  const uint32_t dest_col_stride,
256  const uint32_t dest_line_stride,
257  bool forgiving)
258  {
259  return read(window.x0,
260  window.y0,
261  window.x1,
262  window.y1,
263  dest,
264  dest_col_stride,
265  dest_line_stride,
266  forgiving);
267  }
268 
269  bool write(uint32_t x0,
270  uint32_t y0,
271  uint32_t x1,
272  uint32_t y1,
273  const int32_t* src,
274  const uint32_t src_col_stride,
275  const uint32_t src_line_stride,
276  bool forgiving)
277  {
278  return read_or_write(x0, y0, x1, y1,
279  (int32_t*)src,
280  src_col_stride,
281  src_line_stride,
282  forgiving,
283  false);
284  }
285 
286  bool alloc( grk_rect_u32 window){
287  return alloc(window.x0, window.y0, window.x1, window.y1);
288  }
289 private:
290 
291  bool alloc( uint32_t x0,
292  uint32_t y0,
293  uint32_t x1,
294  uint32_t y1){
295  if (!SparseBuffer::is_window_valid(x0, y0, x1, y1))
296  return true;
297 
298  uint32_t y_incr = 0;
299  uint32_t block_y = y0 >> LBH;
300  for (uint32_t y = y0; y < y1; block_y ++, y += y_incr) {
301  y_incr = (y == y0) ? block_height - (y0 & (block_height-1)) : block_height;
302  y_incr = min<uint32_t>(y_incr, y1 - y);
303  uint32_t block_x = x0 >> LBW;
304  uint32_t x_incr = 0;
305  for (uint32_t x = x0; x < x1; block_x ++, x += x_incr) {
306  x_incr = (x == x0) ? block_width - (x0 & (block_width-1)) : block_width;
307  x_incr = min<uint32_t>(x_incr, x1 - x);
308  if (!grid_bounds.contains(grk_pt(block_x,block_y))){
309  GRK_ERROR("Attempt to allocate a block (%d,%d) outside block grid bounds", block_x, block_y);
310  return false;
311  }
312  auto src_block = getBlock(block_x, block_y);
313  if (!src_block) {
314  auto b = new SparseBlock();
315  if (!b->alloc(block_width*block_height))
316  return false;
317  assert(grid_bounds.contains(grk_pt(block_x,block_y)));
318  assert(b->data);
319  uint64_t index = (uint64_t)(block_y - grid_bounds.y0) * grid_bounds.width() + (block_x - grid_bounds.x0);
320  data_blocks[index] = b;
321  }
322  }
323  }
324 
325  return true;
326  }
327 
328  inline SparseBlock* getBlock(uint32_t block_x, uint32_t block_y){
329  uint64_t index = (uint64_t)(block_y - grid_bounds.y0) * grid_bounds.width() + (block_x - grid_bounds.x0);
330  auto b = data_blocks[index];
331 #ifdef GRK_DEBUG_VALGRIND
332 /*
333  if (b) {
334  size_t val = VALGRIND_CHECK_MEM_IS_DEFINED(b->data,block_width*block_height * sizeof(int32_t));
335  if (val) {
336  for (size_t i = 0; i < block_width*block_height; ++i){
337  size_t val = grk_memcheck<int32_t>(b->data + i,1);
338  if (val != grk_mem_ok) {
339  uint32_t x = block_x * block_width + i % block_width;
340  uint32_t y = block_y * block_height + i / block_width;
341  printf("sparse buffer get block (%d.%d): uninitialized at location (%d,%d)\n",
342  block_x, block_y, x,y );
343  }
344  }
345 
346  }
347  }
348 */
349 #endif
350 
351  return b;
352  }
353 
361  bool is_window_valid(uint32_t x0,
362  uint32_t y0,
363  uint32_t x1,
364  uint32_t y1){
365  return !(x0 >= bounds.width() || x1 <= x0 || x1 > bounds.width() ||
366  y0 >= bounds.height() || y1 <= y0 || y1 > bounds.height());
367  }
368 
369  bool read_or_write(uint32_t x0,
370  uint32_t y0,
371  uint32_t x1,
372  uint32_t y1,
373  int32_t* buf,
374  const uint32_t buf_col_stride,
375  const uint32_t buf_line_stride,
376  bool forgiving,
377  bool is_read_op){
378  if (!is_window_valid(x0, y0, x1, y1)){
379  // fill the client buffer with zeros in this case
380  if (forgiving && is_read_op){
381  //GRK_WARN("Sparse buffer: attempt to read invalid window (%d,%d,%d,%d). Filling with zeros.", x0,y0,x1,y1);
382  for (uint32_t y = y0; y < y1; ++y){
383  int32_t *bufPtr = buf + (y - y0) * buf_line_stride;
384  for (uint32_t x = x0; x < x1; ++x){
385  *bufPtr = 0;
386  bufPtr += buf_col_stride;
387  }
388  }
389  }
390  return forgiving;
391  }
392 
393  const uint64_t line_stride = buf_line_stride;
394  const uint64_t col_stride = buf_col_stride;
395  uint32_t block_y = y0 >> LBH;
396  uint32_t y_incr = 0;
397  for (uint32_t y = y0; y < y1; block_y ++, y += y_incr) {
398  y_incr = (y == y0) ? block_height - (y0 & (block_height-1)) : block_height;
399  uint32_t block_y_offset = block_height - y_incr;
400  y_incr = min<uint32_t>(y_incr, y1 - y);
401  uint32_t block_x = x0 >> LBW;
402  uint32_t x_incr = 0;
403  for (uint32_t x = x0; x < x1; block_x ++, x += x_incr) {
404  x_incr = (x == x0) ? block_width - (x0 & (block_width-1) ) : block_width;
405  uint32_t block_x_offset = block_width - x_incr;
406  x_incr = min<uint32_t>(x_incr, x1 - x);
407  if (!grid_bounds.contains(grk_pt(block_x,block_y))){
408  GRK_ERROR("Attempt to access a block (%d,%d) outside block grid bounds", block_x, block_y);
409  return false;
410  }
411  auto src_block = getBlock(block_x, block_y);
412  //all blocks should be allocated first before read/write is called
413  if (!src_block){
414  GRK_WARN("Sparse buffer %s op: missing block (%d,%d,%d,%d) for %s (%d,%d,%d,%d)",
415  is_read_op ? "read" : "write",
416  block_x*block_width,
417  block_y*block_height,
418  block_x*block_width + x_incr,
419  block_y*block_height + y_incr,
420  is_read_op ? "read" : "write",
421  x0,y0,x1,y1);
422  continue;
423  }
424  if (is_read_op) {
425  const int32_t* GRK_RESTRICT src_ptr =
426  src_block->data + ((uint64_t)block_y_offset << LBW) + block_x_offset;
427  int32_t* GRK_RESTRICT dest_ptr = buf + (y - y0) * line_stride +
428  (x - x0) * col_stride;
429  uint32_t y_ = y;
430  for (uint32_t j = 0; j < y_incr; j++) {
431  uint64_t ind = 0;
432  for (uint32_t k = 0; k < x_incr; k++){
433 #ifdef GRK_DEBUG_VALGRIND
434  grk_pt pt((uint32_t)(x+k), y_);
435  //if (validate.contains(pt)) {
436  size_t val = grk_memcheck<int32_t>(src_ptr+k,1);
437  if (val != grk_mem_ok)
438  GRK_ERROR("sparse buffer read block(%d,%d) : uninitialized at location (%d,%d)",
439  block_x, block_y, x+k,y_);
440  //}
441 #endif
442  dest_ptr[ind] = src_ptr[k];
443  ind += col_stride;
444  }
445  dest_ptr += line_stride;
446  y_ ++;
447  src_ptr += block_width;
448  }
449  } else {
450  const int32_t* GRK_RESTRICT src_ptr = buf + (y - y0) * line_stride + (x - x0) * col_stride;
451  int32_t* GRK_RESTRICT dest_ptr = src_block->data + ((uint64_t)block_y_offset << LBW) + block_x_offset;
452 
453  uint32_t y_ = y;
454  for (uint32_t j = 0; j < y_incr; j++) {
455  uint64_t ind = 0;
456  for (uint32_t k = 0; k < x_incr; k++) {
457 #ifdef GRK_DEBUG_VALGRIND
458  grk_pt pt((uint32_t)(x+k), y_);
459  //if (validate.contains(pt)) {
460  size_t val = grk_memcheck<int32_t>(src_ptr+ind,1);
461  if (val != grk_mem_ok)
462  GRK_ERROR("sparse buffer write block(%d,%d): uninitialized at location (%d,%d)",
463  block_x, block_y, x+k,y_);
464  //}
465 #endif
466  dest_ptr[k] = src_ptr[ind];
467  ind += col_stride;
468  }
469  src_ptr += line_stride;
470  y_ ++;
471  dest_ptr += block_width;
472  }
473  }
474  }
475  }
476 
477  return true;
478  }
479 private:
480  const uint32_t block_width;
481  const uint32_t block_height;
485 #ifdef GRK_DEBUG_VALGRIND
486  grk_rect_u32 validate;
487 #endif
488 };
489 
490 }
491 
Definition: SparseBuffer.h:72
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 buffer into a user buffer.
virtual bool alloc(grk_rect_u32 window)=0
Allocate all blocks for a rectangular window into the sparse buffer from a user buffer.
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 buffer into a user buffer.
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 buffer from a user buffer.
virtual ~ISparseBuffer()
Definition: SparseBuffer.h:75
Definition: SparseBuffer.h:174
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:361
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 buffer from a user buffer.
Definition: SparseBuffer.h:269
grk_rect_u32 bounds
Definition: SparseBuffer.h:483
SparseBlock ** data_blocks
Definition: SparseBuffer.h:482
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:369
bool alloc(uint32_t x0, uint32_t y0, uint32_t x1, uint32_t y1)
Definition: SparseBuffer.h:291
const uint32_t block_height
Definition: SparseBuffer.h:481
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 buffer into a user buffer.
Definition: SparseBuffer.h:253
const uint32_t block_width
Definition: SparseBuffer.h:480
SparseBuffer(uint32_t width, uint32_t height)
Creates a new sparse buffer.
Definition: SparseBuffer.h:219
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 buffer into a user buffer.
Definition: SparseBuffer.h:236
grk_rect_u32 grid_bounds
Definition: SparseBuffer.h:484
SparseBuffer(grk_rect_u32 bds)
Creates a new sparse buffer.
Definition: SparseBuffer.h:184
SparseBlock * getBlock(uint32_t block_x, uint32_t block_y)
Definition: SparseBuffer.h:328
~SparseBuffer()
Frees a sparse buffer.
Definition: SparseBuffer.h:226
bool alloc(grk_rect_u32 window)
Allocate all blocks for a rectangular window into the sparse buffer from a user buffer.
Definition: SparseBuffer.h:286
#define GRK_RESTRICT
Definition: grk_includes.h:101
Copyright (C) 2016-2021 Grok Image Compression Inc.
Definition: BitIO.cpp:23
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
void GRK_ERROR(const char *fmt,...)
Definition: logger.cpp:57
void GRK_WARN(const char *fmt,...)
Definition: logger.cpp:49
grk_rectangle< uint32_t > grk_rect_u32
Definition: util.h:56
Definition: SparseBuffer.h:157
SparseBlock(void)
Definition: SparseBuffer.h:158
int32_t * data
Definition: SparseBuffer.h:171
bool alloc(uint32_t block_area)
Definition: SparseBuffer.h:163
~SparseBlock()
Definition: SparseBuffer.h:160
T x0
Definition: util.h:84
T y1
Definition: util.h:84
bool contains(grk_point< T > pt)
Definition: util.h:105
T y0
Definition: util.h:84
uint64_t area(void) const
Definition: util.h:180
T height() const
Definition: util.h:186
T width() const
Definition: util.h:183
T x1
Definition: util.h:84