Grok  10.0.3
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 /***
25  *
26  * SparseCanvas stores blocks of size LBW x LBH in canvase coordinate system (with offset)
27  * Blocks are only allocated for active sub-bands for reduced resolutions
28  *
29  * Data is pass in and out in a linear array, chunked either along the y axis
30  * or along the x axis, depending on whether we are working with a horizontal strip
31  * or a vertical strip of data.
32  *
33  *
34  */
35 
36 namespace grk
37 {
39 {
40  public:
41  virtual ~ISparseCanvas() = default;
45  virtual bool read(uint8_t resno, grk_rect32 window, int32_t* dest, const uint32_t destChunkY,
46  const uint32_t destChunkX) = 0;
50  virtual bool write(uint8_t resno, grk_rect32 window, const int32_t* src,
51  const uint32_t srcChunkY, const uint32_t srcChunkX) = 0;
52 
53  virtual bool alloc(grk_rect32 window, bool zeroOutBuffer) = 0;
54 };
56 {
57  SparseBlock(void) : data(nullptr) {}
59  {
60  delete[] data;
61  }
62  void alloc(uint32_t block_area, bool zeroOutBuffer)
63  {
64  data = new int32_t[block_area];
65  if(zeroOutBuffer)
66  memset(data, 0, block_area * sizeof(int32_t));
67  }
68  int32_t* data;
69 };
70 template<uint32_t LBW, uint32_t LBH>
72 {
73  public:
75  : blockWidth(1 << LBW), blockHeight(1 << LBH), blocks(nullptr), bounds(bds)
76  {
77  if(!bounds.width() || !bounds.height() || !LBW || !LBH)
78  throw std::runtime_error("invalid window for sparse canvas");
79  grid = bounds.scaleDownPow2(LBW, LBH);
80  auto blockCount = grid.area();
81  blocks = new SparseBlock*[blockCount];
82  for(uint64_t i = 0; i < blockCount; ++i)
83  blocks[i] = nullptr;
84  }
85  SparseCanvas(uint32_t width, uint32_t height) : SparseCanvas(grk_rect32(0, 0, width, height)) {}
87  {
88  if(blocks)
89  {
90  for(uint64_t i = 0; i < (uint64_t)grid.width() * grid.height(); i++)
91  {
92  delete(blocks[i]);
93  blocks[i] = nullptr;
94  }
95  delete[] blocks;
96  }
97  }
98  bool read(uint8_t resno, grk_rect32 window, int32_t* dest, const uint32_t destChunkY,
99  const uint32_t destChunkX)
100  {
101  return readWrite(resno, window, dest, destChunkY, destChunkX, true);
102  }
103  bool write(uint8_t resno, grk_rect32 window, const int32_t* src, const uint32_t srcChunkY,
104  const uint32_t srcChunkX)
105  {
106  return readWrite(resno, window, (int32_t*)src, srcChunkY, srcChunkX, false);
107  }
108  bool alloc(grk_rect32 win, bool zeroOutBuffer)
109  {
111  return true;
112  uint32_t blockWinHeight = 0;
113  uint32_t gridY = win.y0 >> LBH;
114  for(uint32_t y = win.y0; y < win.y1; gridY++, y += blockWinHeight)
115  {
116  blockWinHeight =
117  (y == win.y0) ? blockHeight - (win.y0 & (blockHeight - 1)) : blockHeight;
118  blockWinHeight = (std::min<uint32_t>)(blockWinHeight, win.y1 - y);
119  uint32_t gridX = win.x0 >> LBW;
120  uint32_t blockWinWidth = 0;
121  for(uint32_t x = win.x0; x < win.x1; gridX++, x += blockWinWidth)
122  {
123  blockWinWidth =
124  (x == win.x0) ? blockWidth - (win.x0 & (blockWidth - 1)) : blockWidth;
125  blockWinWidth = (std::min<uint32_t>)(blockWinWidth, win.x1 - x);
126  if(!grid.contains(gridX, gridY))
127  {
128  GRK_WARN("sparse canvas : attempt to allocate a block (%u,%u) outside block "
129  "grid bounds (%u,%u,%u,%u)",
130  gridX, gridY, grid.x0, grid.y0, grid.x1, grid.y1);
131  return false;
132  }
133  auto srcBlock = getBlock(gridX, gridY);
134  if(!srcBlock)
135  {
136  auto b = new SparseBlock();
137  b->alloc(blockWidth * blockHeight, zeroOutBuffer);
138  assert(grid.contains(gridX, gridY));
139  assert(b->data);
140  uint64_t blockInd =
141  (uint64_t)(gridY - grid.y0) * grid.width() + (gridX - grid.x0);
142  blocks[blockInd] = b;
143  }
144  }
145  }
146  return true;
147  }
148 
149  private:
150  inline SparseBlock* getBlock(uint32_t block_x, uint32_t block_y)
151  {
152  uint64_t index = (uint64_t)(block_y - grid.y0) * grid.width() + (block_x - grid.x0);
153  return blocks[index];
154  }
156  {
157  return !(win.x0 >= bounds.x1 || win.x1 <= win.x0 || win.x1 > bounds.x1 ||
158  win.y0 >= bounds.y1 || win.y1 <= win.y0 || win.y1 > bounds.y1);
159  }
160  bool readWrite(uint8_t resno, grk_rect32 win, int32_t* buf, const uint32_t spacingX,
161  const uint32_t spacingY, bool isReadOperation)
162  {
163  if(!win.valid())
164  return false;
165  assert(!isReadOperation || buf);
166 
167  if(!isWindowValid(win))
168  {
169  GRK_WARN("Sparse canvas @ res %u, attempt to read/write invalid window (%u,%u,%u,%u) "
170  "for bounds (%u,%u,%u,%u).",
171  resno, win.x0, win.y0, win.x1, win.y1, bounds.x0, bounds.y0, bounds.x1,
172  bounds.y1);
173  return false;
174  }
175  assert(spacingY != 0 || win.height() == 1);
176  assert((spacingY <= 1 && spacingX >= 1) || (spacingY >= 1 && spacingX == 1));
177 
178  uint32_t gridY = win.y0 >> LBH;
179  uint32_t blockWinHeight = 0;
180  for(uint32_t y = win.y0; y < win.y1; gridY++, y += blockWinHeight)
181  {
182  blockWinHeight =
183  (y == win.y0) ? blockHeight - (win.y0 & (blockHeight - 1)) : blockHeight;
184  uint32_t blockOffsetY = blockHeight - blockWinHeight;
185  blockWinHeight = (std::min<uint32_t>)(blockWinHeight, win.y1 - y);
186  uint32_t gridX = win.x0 >> LBW;
187  uint32_t blockWinWidth = 0;
188  for(uint32_t x = win.x0; x < win.x1; gridX++, x += blockWinWidth)
189  {
190  blockWinWidth =
191  (x == win.x0) ? blockWidth - (win.x0 & (blockWidth - 1)) : blockWidth;
192  uint32_t blockOffsetX = blockWidth - blockWinWidth;
193  blockWinWidth = (std::min<uint32_t>)(blockWinWidth, win.x1 - x);
194  if(!grid.contains(gridX, gridY))
195  {
196  GRK_WARN("sparse canvas @ resno %u, Attempt to access a block (%u,%u) outside "
197  "block grid bounds",
198  resno, gridX, gridY);
199  return false;
200  }
201  auto srcBlock = getBlock(gridX, gridY);
202  if(!srcBlock)
203  {
204  GRK_WARN("sparse canvas @ resno %u, %s op: missing block (%u,%u,%u,%u) for %s "
205  "(%u,%u,%u,%u). Skipping.",
206  resno, isReadOperation ? "read" : "write",
207  bounds.x0 + gridX * blockWidth, bounds.y0 + gridY * blockHeight,
208  bounds.x0 + (gridX + 1) * blockWidth,
209  bounds.y0 + (gridY + 1) * blockHeight,
210  isReadOperation ? "read" : "write", win.x0, win.y0, win.x1, win.y1);
211  continue;
212  }
213  if(isReadOperation)
214  {
215  auto src = srcBlock->data + ((uint64_t)blockOffsetY << LBW) + blockOffsetX;
216  auto dest = buf + (y - win.y0) * spacingY + (x - win.x0) * spacingX;
217  for(uint32_t blockY = 0; blockY < blockWinHeight; blockY++)
218  {
219  uint64_t destInd = 0;
220  for(uint32_t blockX = 0; blockX < blockWinWidth; blockX++)
221  {
222 #ifdef GRK_DEBUG_VALGRIND
223  size_t val = grk_memcheck<int32_t>(src + blockX, 1);
224  if(val != grk_mem_ok)
225  GRK_ERROR("sparse canvas @resno %u, read block(%u,%u) : "
226  "uninitialized at location (%u,%u)",
227  resno, gridX, gridY, x + blockX, y_);
228 #endif
229  dest[destInd] = src[blockX];
230  destInd += spacingX;
231  }
232  dest += spacingY;
233  src += blockWidth;
234  }
235  }
236  else
237  {
238  const int32_t* src = nullptr;
239  if(buf)
240  src = buf + (y - win.y0) * spacingY + (x - win.x0) * spacingX;
241  auto dest = srcBlock->data + ((uint64_t)blockOffsetY << LBW) + blockOffsetX;
242  for(uint32_t blockY = 0; blockY < blockWinHeight; blockY++)
243  {
244  uint64_t srcInd = 0;
245  for(uint32_t blockX = 0; blockX < blockWinWidth; blockX++)
246  {
247 #ifdef GRK_DEBUG_VALGRIND
248  if(src)
249  {
250  grk_pt32 pt((uint32_t)(x + blockX), y_);
251  size_t val = grk_memcheck<int32_t>(src + srcInd, 1);
252  if(val != grk_mem_ok)
253  GRK_ERROR("sparse canvas @ resno %u, write block(%u,%u): "
254  "uninitialized at location (%u,%u)",
255  resno, gridX, gridY, x + blockX, y_);
256  }
257 #endif
258  dest[blockX] = src ? src[srcInd] : 0;
259  srcInd += spacingX;
260  }
261  if(src)
262  src += spacingY;
263  dest += blockWidth;
264  }
265  }
266  }
267  }
268  return true;
269  }
270 
271  private:
272  const uint32_t blockWidth;
273  const uint32_t blockHeight;
275  grk_rect32 bounds; // canvas bounds
276  grk_rect32 grid; // block grid bounds
277 };
278 
279 } // namespace grk
Definition: SparseCanvas.h:39
virtual ~ISparseCanvas()=default
virtual bool alloc(grk_rect32 window, bool zeroOutBuffer)=0
virtual bool read(uint8_t resno, grk_rect32 window, int32_t *dest, const uint32_t destChunkY, const uint32_t destChunkX)=0
Read window of data into dest buffer.
virtual bool write(uint8_t resno, grk_rect32 window, const int32_t *src, const uint32_t srcChunkY, const uint32_t srcChunkX)=0
Write window of data from src buffer.
Definition: SparseCanvas.h:72
grk_rect32 bounds
Definition: SparseCanvas.h:275
SparseCanvas(uint32_t width, uint32_t height)
Definition: SparseCanvas.h:85
const uint32_t blockWidth
Definition: SparseCanvas.h:272
bool alloc(grk_rect32 win, bool zeroOutBuffer)
Definition: SparseCanvas.h:108
SparseBlock ** blocks
Definition: SparseCanvas.h:274
SparseBlock * getBlock(uint32_t block_x, uint32_t block_y)
Definition: SparseCanvas.h:150
bool readWrite(uint8_t resno, grk_rect32 win, int32_t *buf, const uint32_t spacingX, const uint32_t spacingY, bool isReadOperation)
Definition: SparseCanvas.h:160
~SparseCanvas()
Definition: SparseCanvas.h:86
bool read(uint8_t resno, grk_rect32 window, int32_t *dest, const uint32_t destChunkY, const uint32_t destChunkX)
Read window of data into dest buffer.
Definition: SparseCanvas.h:98
SparseCanvas(grk_rect32 bds)
Definition: SparseCanvas.h:74
bool write(uint8_t resno, grk_rect32 window, const int32_t *src, const uint32_t srcChunkY, const uint32_t srcChunkX)
Write window of data from src buffer.
Definition: SparseCanvas.h:103
const uint32_t blockHeight
Definition: SparseCanvas.h:273
grk_rect32 grid
Definition: SparseCanvas.h:276
bool isWindowValid(grk_rect32 win)
Definition: SparseCanvas.h:155
Copyright (C) 2016-2022 Grok Image Compression Inc.
Definition: ICacheable.h:20
void GRK_ERROR(const char *fmt,...)
Definition: logger.cpp:58
void GRK_WARN(const char *fmt,...)
Definition: logger.cpp:49
Definition: SparseCanvas.h:56
SparseBlock(void)
Definition: SparseCanvas.h:57
void alloc(uint32_t block_area, bool zeroOutBuffer)
Definition: SparseCanvas.h:62
int32_t * data
Definition: SparseCanvas.h:68
~SparseBlock()
Definition: SparseCanvas.h:58
uint64_t area(void) const
Definition: geometry.h:331
T width() const
Definition: geometry.h:335
T y1
Definition: geometry.h:124
T x0
Definition: geometry.h:124
T x1
Definition: geometry.h:124
grk_rect< T > scaleDownPow2(uint32_t powx, uint32_t powy) const
Definition: geometry.h:252
T height() const
Definition: geometry.h:339
bool valid(void) const
Definition: geometry.h:185
bool contains(grk_pt< T > pt)
Definition: geometry.h:193
T y0
Definition: geometry.h:124