Grok  10.0.3
TagTree.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  *
17  * This source code incorporates work covered by the BSD 2-clause license.
18  * Please see the LICENSE file in the root directory for details.
19  *
20  */
21 
22 #pragma once
23 
24 #include <limits>
25 
26 namespace grk
27 {
31 template<typename T>
33 {
34  TagTreeNode() : parent(nullptr), value(0), low(0), known(false) {}
35 
37  T value;
38  T low;
39  bool known;
40 };
41 
45 template<typename T>
46 class TagTree
47 {
48  public:
55  TagTree(uint32_t leavesWidth, uint32_t leavesHeight)
56  : leavesWidth_(leavesWidth), leavesHeight_(leavesHeight), nodeCount(0), nodes(nullptr)
57  {
58  uint32_t resLeavesWidth[32];
59  uint32_t resLeavesHeight[32];
60  int8_t numLevels = 0;
61  resLeavesWidth[0] = leavesWidth_;
62  resLeavesHeight[0] = leavesHeight_;
63  nodeCount = 0;
64  uint64_t nodesPerLevel;
65  do
66  {
67  if(numLevels == 32)
68  {
69  GRK_ERROR("TagTree constructor: num level overflow");
70  throw std::exception();
71  }
72  nodesPerLevel = (uint64_t)resLeavesWidth[numLevels] * resLeavesHeight[numLevels];
73  resLeavesWidth[numLevels + 1] =
74  (uint32_t)(((uint64_t)resLeavesWidth[numLevels] + 1) >> 1);
75  resLeavesHeight[numLevels + 1] =
76  (uint32_t)(((uint64_t)resLeavesHeight[numLevels] + 1) >> 1);
77  nodeCount += nodesPerLevel;
78  ++numLevels;
79  } while(nodesPerLevel > 1);
80 
81  if(nodeCount == 0)
82  {
83  GRK_WARN("tgt_create numnodes == 0, no tree created.");
84  throw std::runtime_error("tgt_create numnodes == 0, no tree created");
85  }
86 
88  auto currentNode = nodes;
89  auto parentNode = nodes + (uint64_t)leavesWidth_ * leavesHeight_;
90  auto parentNodeNext = parentNode;
91 
92  for(int8_t i = 0; i < numLevels - 1; ++i)
93  {
94  for(uint32_t j = 0; j < resLeavesHeight[i]; ++j)
95  {
96  int64_t k = resLeavesWidth[i];
97  while(--k >= 0)
98  {
99  currentNode->parent = parentNode;
100  ++currentNode;
101  if(--k >= 0)
102  {
103  currentNode->parent = parentNode;
104  ++currentNode;
105  }
106  ++parentNode;
107  }
108  if((j & 1) || j == resLeavesHeight[i] - 1)
109  {
110  parentNodeNext = parentNode;
111  }
112  else
113  {
114  parentNode = parentNodeNext;
115  parentNodeNext += resLeavesWidth[i];
116  }
117  }
118  }
119  currentNode->parent = nullptr;
120  reset();
121  }
123  {
124  delete[] nodes;
125  }
126 
127  constexpr T getUninitializedValue(void)
128  {
129  return (std::numeric_limits<T>::max)();
130  }
134  void reset()
135  {
136  for(uint64_t i = 0; i < nodeCount; ++i)
137  {
138  auto current_node = nodes + i;
139  current_node->value = getUninitializedValue();
140  current_node->low = 0;
141  current_node->known = false;
142  }
143  }
149  void setvalue(uint64_t leafno, T value)
150  {
151  auto node = nodes + leafno;
152  while(node && node->value > value)
153  {
154  node->value = value;
155  node = node->parent;
156  }
157  }
165  bool compress(BitIO* bio, uint64_t leafno, T threshold)
166  {
167  TagTreeNode<T>* nodeStack[31];
168  auto nodeStackPtr = nodeStack;
169  auto node = nodes + leafno;
170  while(node->parent)
171  {
172  *nodeStackPtr++ = node;
173  node = node->parent;
174  }
175  T low = 0;
176  while(true)
177  {
178  if(node->low < low)
179  node->low = low;
180  else
181  low = node->low;
182 
183  while(low < threshold)
184  {
185  if(low >= node->value)
186  {
187  if(!node->known)
188  {
189  if(!bio->write(1))
190  return false;
191  node->known = true;
192  }
193  break;
194  }
195  if(!bio->write(0))
196  return false;
197  ++low;
198  }
199  node->low = low;
200  if(nodeStackPtr == nodeStack)
201  break;
202  node = *--nodeStackPtr;
203  }
204  return true;
205  }
213  void decodeValue(BitIO* bio, uint64_t leafno, T threshold, T* value)
214  {
215  TagTreeNode<T>* nodeStack[31];
216  *value = getUninitializedValue();
217  auto nodeStackPtr = nodeStack;
218  auto node = nodes + leafno;
219  // climb to top of tree
220  while(node->parent)
221  {
222  *nodeStackPtr++ = node;
223  node = node->parent;
224  }
225  // descend to bottom of tree
226  T low = 0;
227  while(true)
228  {
229  if(node->low < low)
230  node->low = low;
231  else
232  low = node->low;
233  while(low < threshold && low < node->value)
234  {
235  if(bio->read())
236  {
237  node->value = low;
238  break;
239  }
240  low++;
241  }
242  node->low = low;
243  if(nodeStackPtr == nodeStack)
244  break;
245  node = *--nodeStackPtr;
246  }
247  *value = node->value;
248  }
249 
250  private:
251  uint32_t leavesWidth_;
252  uint32_t leavesHeight_;
253  uint64_t nodeCount;
255 };
256 
259 
260 } // namespace grk
Definition: BitIO.h:33
void read(uint32_t *bits, uint8_t n) override
Read bits.
Definition: BitIO.cpp:132
bool write(uint32_t v, uint32_t n) override
Write bits.
Definition: BitIO.cpp:111
Tag tree.
Definition: TagTree.h:47
uint64_t nodeCount
Definition: TagTree.h:253
bool compress(BitIO *bio, uint64_t leafno, T threshold)
Encode the value of a leaf of the tag tree up to a given threshold.
Definition: TagTree.h:165
TagTreeNode< T > * nodes
Definition: TagTree.h:254
TagTree(uint32_t leavesWidth, uint32_t leavesHeight)
Create a tag tree.
Definition: TagTree.h:55
void reset()
Reset a tag tree (set all leaves to 0)
Definition: TagTree.h:134
void setvalue(uint64_t leafno, T value)
Set the value of a leaf of a tag tree.
Definition: TagTree.h:149
~TagTree()
Definition: TagTree.h:122
void decodeValue(BitIO *bio, uint64_t leafno, T threshold, T *value)
Decompress the value of a leaf of the tag tree up to a given threshold.
Definition: TagTree.h:213
uint32_t leavesHeight_
Definition: TagTree.h:252
uint32_t leavesWidth_
Definition: TagTree.h:251
constexpr T getUninitializedValue(void)
Definition: TagTree.h:127
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
TagTree< uint16_t > TagTreeU16
Definition: TagTree.h:258
TagTree< uint8_t > TagTreeU8
Definition: TagTree.h:257
Tag node.
Definition: TagTree.h:33
bool known
Definition: TagTree.h:39
T low
Definition: TagTree.h:38
TagTreeNode * parent
Definition: TagTree.h:36
TagTreeNode()
Definition: TagTree.h:34
T value
Definition: TagTree.h:37