Grok 10.0.5
TagTree.h
Go to the documentation of this file.
1/*
2 * Copyright (C) 2016-2023 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
26namespace grk
27{
31template<typename T>
32struct TagTreeNode
33{
34 TagTreeNode() : parent(nullptr), value(0), low(0), known(false) {}
35
36 TagTreeNode* parent;
38 T low;
39 bool known;
40};
41
45template<typename T>
46class 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
87 nodes = new TagTreeNode<T>[nodeCount];
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 }
122 ~TagTree()
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_;
253 uint64_t nodeCount;
254 TagTreeNode<T>* nodes;
255};
256
257typedef TagTree<uint8_t> TagTreeU8;
258typedef TagTree<uint16_t> TagTreeU16;
259
260} // namespace grk
uint64_t nodeCount
Definition TagTree.h:253
TagTreeNode * parent
Definition TagTree.h:36
T value
Definition TagTree.h:37
uint32_t leavesWidth_
Definition TagTree.h:251
uint32_t leavesHeight_
Definition TagTree.h:252
T low
Definition TagTree.h:38
bool known
Definition TagTree.h:39
TagTreeNode< T > * nodes
Definition TagTree.h:254
void GRK_WARN(const char *fmt,...)
void GRK_ERROR(const char *fmt,...)
Copyright (C) 2016-2023 Grok Image Compression Inc.
Definition ICacheable.h:20
TagTree< uint16_t > TagTreeU16
Definition TagTree.h:258
TagTree< uint8_t > TagTreeU8
Definition TagTree.h:257