Grok  9.7.5
SparseCanvas.h
Go to the documentation of this file.
1 /*
2  * Copyright (C) 2016-2022 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 #pragma once
17 
18 #include <cstdint>
19 #include <algorithm>
20 
21 // SparseCanvas stores blocks in the canvas coordinate system. It covers the active sub-bands for
22 // all (reduced) resolutions
23 
24 namespace grk
25 {
27 {
28  public:
29  virtual ~ISparseCanvas() = default;
30  virtual bool read(uint8_t resno, eBandOrientation bandOrientation, grk_rect32 window,
31  int32_t* dest, const uint32_t destinationColumnStride,
32  const uint32_t destinationLineStride, bool forceReturnTrue) = 0;
33  virtual bool write(uint8_t resno, eBandOrientation bandOrientation, grk_rect32 window,
34  const int32_t* src, const uint32_t src_columnStride,
35  const uint32_t src_lineStride, bool forceReturnTrue) = 0;
36  virtual bool alloc(grk_rect32 window, bool zeroOutBuffer) = 0;
37 };
39 {
40  SparseBlock(void) : data(nullptr) {}
42  {
43  delete[] data;
44  }
45  void alloc(uint32_t block_area, bool zeroOutBuffer)
46  {
47  data = new int32_t[block_area];
48  if(zeroOutBuffer)
49  memset(data, 0, block_area * sizeof(int32_t));
50  }
51  int32_t* data;
52 };
53 template<uint32_t LBW, uint32_t LBH>
55 {
56  public:
58  : blockWidth(1 << LBW), blockHeight(1 << LBH), blocks(nullptr), bounds(bds)
59  {
60  if(!bounds.width() || !bounds.height() || !LBW || !LBH)
61  throw std::runtime_error("invalid window for sparse buffer");
62  uint32_t grid_off_x = floordivpow2(bounds.x0, LBW);
63  uint32_t grid_off_y = floordivpow2(bounds.y0, LBH);
64  uint32_t grid_x = ceildivpow2<uint32_t>(bounds.x1, LBW);
65  uint32_t grid_y = ceildivpow2<uint32_t>(bounds.y1, LBH);
66  gridBounds = grk_rect32(grid_off_x, grid_off_y, grid_x, grid_y);
67  auto blockCount = gridBounds.area();
68  blocks = new SparseBlock*[blockCount];
69  for(uint64_t i = 0; i < blockCount; ++i)
70  blocks[i] = nullptr;
71  }
72  SparseCanvas(uint32_t width, uint32_t height) : SparseCanvas(grk_rect32(0, 0, width, height)) {}
74  {
75  if(blocks)
76  {
77  for(uint64_t i = 0; i < (uint64_t)gridBounds.width() * gridBounds.height(); i++)
78  {
79  delete(blocks[i]);
80  blocks[i] = nullptr;
81  }
82  delete[] blocks;
83  }
84  }
85  bool read(uint8_t resno, eBandOrientation bandOrientation, grk_rect32 window, int32_t* dest,
86  const uint32_t destinationColumnStride, const uint32_t destinationLineStride,
87  bool forceReturnTrue)
88  {
89  GRK_UNUSED(bandOrientation);
90  return readWrite(resno, window, dest, destinationColumnStride, destinationLineStride,
91  forceReturnTrue, true);
92  }
93  bool write(uint8_t resno, eBandOrientation bandOrientation, grk_rect32 window,
94  const int32_t* src, const uint32_t src_columnStride, const uint32_t src_lineStride,
95  bool forceReturnTrue)
96  {
97  GRK_UNUSED(bandOrientation);
98  return readWrite(resno, window, (int32_t*)src, src_columnStride, src_lineStride,
99  forceReturnTrue, false);
100  }
101  bool alloc(grk_rect32 win, bool zeroOutBuffer)
102  {
104  return true;
105  uint32_t yIncrement = 0;
106  uint32_t block_y = win.y0 >> LBH;
107  for(uint32_t y = win.y0; y < win.y1; block_y++, y += yIncrement)
108  {
109  yIncrement = (y == win.y0) ? blockHeight - (win.y0 & (blockHeight - 1)) : blockHeight;
110  yIncrement = (std::min<uint32_t>)(yIncrement, win.y1 - y);
111  uint32_t block_x = win.x0 >> LBW;
112  uint32_t xIncrement = 0;
113  for(uint32_t x = win.x0; x < win.x1; block_x++, x += xIncrement)
114  {
115  xIncrement = (x == win.x0) ? blockWidth - (win.x0 & (blockWidth - 1)) : blockWidth;
116  xIncrement = (std::min<uint32_t>)(xIncrement, win.x1 - x);
117  if(!gridBounds.contains(grk_pt32(block_x, block_y)))
118  {
119  GRK_ERROR("sparse buffer : attempt to allocate a block (%u,%u) outside block "
120  "grid bounds (%u,%u,%u,%u)",
121  block_x, block_y, gridBounds.x0, gridBounds.y0, gridBounds.x1,
122  gridBounds.y1);
123  return false;
124  }
125  auto srcBlock = getBlock(block_x, block_y);
126  if(!srcBlock)
127  {
128  auto b = new SparseBlock();
129  b->alloc(blockWidth * blockHeight, zeroOutBuffer);
130  assert(gridBounds.contains(grk_pt32(block_x, block_y)));
131  assert(b->data);
132  uint64_t index = (uint64_t)(block_y - gridBounds.y0) * gridBounds.width() +
133  (block_x - gridBounds.x0);
134  blocks[index] = b;
135  }
136  }
137  }
138  return true;
139  }
140 
141  private:
142  inline SparseBlock* getBlock(uint32_t block_x, uint32_t block_y)
143  {
144  uint64_t index =
145  (uint64_t)(block_y - gridBounds.y0) * gridBounds.width() + (block_x - gridBounds.x0);
146  return blocks[index];
147  }
149  {
150  return !(win.x0 >= bounds.x1 || win.x1 <= win.x0 || win.x1 > bounds.x1 ||
151  win.y0 >= bounds.y1 || win.y1 <= win.y0 || win.y1 > bounds.y1);
152  }
153  bool readWrite(uint8_t resno, grk_rect32 win, int32_t* buf, const uint32_t buf_columnStride,
154  const uint32_t buf_lineStride, bool forceReturnTrue, bool isReadOperation)
155  {
156  if(!isWindowValid(win))
157  {
158  // fill the client buffer with zeros in this case
159  if(forceReturnTrue && isReadOperation)
160  {
161  GRK_WARN("Sparse buffer @ res %u, attempt to read invalid window (%u,%u,%u,%u). "
162  "Filling with zeros.",
163  resno, win.x0, win.y0, win.x1, win.y1);
164  for(uint32_t y = win.y0; y < win.y1; ++y)
165  {
166  auto bufPtr = buf + (y - win.y0) * buf_lineStride;
167  for(uint32_t x = win.x0; x < win.x1; ++x)
168  {
169  *bufPtr = 0;
170  bufPtr += buf_columnStride;
171  }
172  }
173  }
174  return forceReturnTrue;
175  }
176  const uint64_t lineStride = buf_lineStride;
177  const uint64_t columnStride = buf_columnStride;
178  uint32_t block_y = win.y0 >> LBH;
179  uint32_t yIncrement = 0;
180  for(uint32_t y = win.y0; y < win.y1; block_y++, y += yIncrement)
181  {
182  yIncrement = (y == win.y0) ? blockHeight - (win.y0 & (blockHeight - 1)) : blockHeight;
183  uint32_t blockYOffset = blockHeight - yIncrement;
184  yIncrement = (std::min<uint32_t>)(yIncrement, win.y1 - y);
185  uint32_t block_x = win.x0 >> LBW;
186  uint32_t xIncrement = 0;
187  for(uint32_t x = win.x0; x < win.x1; block_x++, x += xIncrement)
188  {
189  xIncrement = (x == win.x0) ? blockWidth - (win.x0 & (blockWidth - 1)) : blockWidth;
190  uint32_t blockXOffset = blockWidth - xIncrement;
191  xIncrement = (std::min<uint32_t>)(xIncrement, win.x1 - x);
192  if(!gridBounds.contains(grk_pt32(block_x, block_y)))
193  {
194  GRK_ERROR("sparse buffer @ resno %u, Attempt to access a block (%u,%u) outside "
195  "block grid bounds",
196  resno, block_x, block_y);
197  return false;
198  }
199  auto srcBlock = getBlock(block_x, block_y);
200  if(!srcBlock)
201  {
202  GRK_WARN("sparse buffer @ resno %u, %s op: missing block (%u,%u,%u,%u) for %s "
203  "(%u,%u,%u,%u)",
204  resno, isReadOperation ? "read" : "write",
205  bounds.x0 + block_x * blockWidth, bounds.y0 + block_y * blockHeight,
206  bounds.x0 + (block_x + 1) * blockWidth,
207  bounds.y0 + (block_y + 1) * blockHeight,
208  isReadOperation ? "read" : "write", win.x0, win.y0, win.x1, win.y1);
209  continue;
210  }
211  if(isReadOperation)
212  {
213  const int32_t* src =
214  srcBlock->data + ((uint64_t)blockYOffset << LBW) + blockXOffset;
215  auto dest = buf + (y - win.y0) * lineStride + (x - win.x0) * columnStride;
216  for(uint32_t j = 0; j < yIncrement; j++)
217  {
218  uint64_t index = 0;
219  for(uint32_t k = 0; k < xIncrement; k++)
220  {
221 #ifdef GRK_DEBUG_VALGRIND
222  size_t val = grk_memcheck<int32_t>(src + k, 1);
223  if(val != grk_mem_ok)
224  GRK_ERROR("sparse buffer @resno %u, read block(%u,%u) : "
225  "uninitialized at location (%u,%u)",
226  resno, block_x, block_y, x + k, y_);
227 #endif
228  dest[index] = src[k];
229  index += columnStride;
230  }
231  dest += lineStride;
232  src += blockWidth;
233  }
234  }
235  else
236  {
237  const int32_t* src = nullptr;
238  if(buf)
239  src = buf + (y - win.y0) * lineStride + (x - win.x0) * columnStride;
240  auto dest = srcBlock->data + ((uint64_t)blockYOffset << LBW) + blockXOffset;
241  for(uint32_t j = 0; j < yIncrement; j++)
242  {
243  uint64_t index = 0;
244  for(uint32_t k = 0; k < xIncrement; k++)
245  {
246 #ifdef GRK_DEBUG_VALGRIND
247  if(src)
248  {
249  grk_pt32 pt((uint32_t)(x + k), y_);
250  size_t val = grk_memcheck<int32_t>(src + index, 1);
251  if(val != grk_mem_ok)
252  GRK_ERROR("sparse buffer @ resno %u, write block(%u,%u): "
253  "uninitialized at location (%u,%u)",
254  resno, block_x, block_y, x + k, y_);
255  }
256 #endif
257  dest[k] = src ? src[index] : 0;
258  index += columnStride;
259  }
260  if(src)
261  src += lineStride;
262  dest += blockWidth;
263  }
264  }
265  }
266  }
267  return true;
268  }
269 
270  private:
271  const uint32_t blockWidth;
272  const uint32_t blockHeight;
276 };
277 
278 } // namespace grk
Definition: SparseCanvas.h:27
virtual ~ISparseCanvas()=default
virtual bool alloc(grk_rect32 window, bool zeroOutBuffer)=0
virtual bool write(uint8_t resno, eBandOrientation bandOrientation, grk_rect32 window, const int32_t *src, const uint32_t src_columnStride, const uint32_t src_lineStride, bool forceReturnTrue)=0
virtual bool read(uint8_t resno, eBandOrientation bandOrientation, grk_rect32 window, int32_t *dest, const uint32_t destinationColumnStride, const uint32_t destinationLineStride, bool forceReturnTrue)=0
Definition: SparseCanvas.h:55
grk_rect32 bounds
Definition: SparseCanvas.h:274
SparseCanvas(uint32_t width, uint32_t height)
Definition: SparseCanvas.h:72
const uint32_t blockWidth
Definition: SparseCanvas.h:271
bool alloc(grk_rect32 win, bool zeroOutBuffer)
Definition: SparseCanvas.h:101
SparseBlock ** blocks
Definition: SparseCanvas.h:273
SparseBlock * getBlock(uint32_t block_x, uint32_t block_y)
Definition: SparseCanvas.h:142
~SparseCanvas()
Definition: SparseCanvas.h:73
SparseCanvas(grk_rect32 bds)
Definition: SparseCanvas.h:57
bool read(uint8_t resno, eBandOrientation bandOrientation, grk_rect32 window, int32_t *dest, const uint32_t destinationColumnStride, const uint32_t destinationLineStride, bool forceReturnTrue)
Definition: SparseCanvas.h:85
const uint32_t blockHeight
Definition: SparseCanvas.h:272
bool write(uint8_t resno, eBandOrientation bandOrientation, grk_rect32 window, const int32_t *src, const uint32_t src_columnStride, const uint32_t src_lineStride, bool forceReturnTrue)
Definition: SparseCanvas.h:93
grk_rect32 gridBounds
Definition: SparseCanvas.h:275
bool readWrite(uint8_t resno, grk_rect32 win, int32_t *buf, const uint32_t buf_columnStride, const uint32_t buf_lineStride, bool forceReturnTrue, bool isReadOperation)
Definition: SparseCanvas.h:153
bool isWindowValid(grk_rect32 win)
Definition: SparseCanvas.h:148
#define GRK_UNUSED(x)
Definition: grk_includes.h:87
Copyright (C) 2016-2022 Grok Image Compression Inc.
Definition: ICacheable.h:20
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
grk_rect< uint32_t > grk_rect32
Definition: util.h:57
eBandOrientation
Definition: Subband.h:25
Definition: SparseCanvas.h:39
SparseBlock(void)
Definition: SparseCanvas.h:40
void alloc(uint32_t block_area, bool zeroOutBuffer)
Definition: SparseCanvas.h:45
int32_t * data
Definition: SparseCanvas.h:51
~SparseBlock()
Definition: SparseCanvas.h:41
uint64_t area(void) const
Definition: util.h:242
T width() const
Definition: util.h:246
T y1
Definition: util.h:109
T x0
Definition: util.h:109
T x1
Definition: util.h:109
T height() const
Definition: util.h:250
bool contains(grk_pt< T > pt)
Definition: util.h:129
T y0
Definition: util.h:109