Grok 12.0.1
TagTree.h
Go to the documentation of this file.
1/*
2 * Copyright (C) 2016-2024 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>
41
45template<typename T>
47{
48 public:
57 {
60 int8_t numLevels = 0;
63 nodeCount = 0;
65 do
66 {
67 if(numLevels == 32)
68 {
69 Logger::logger_.error("TagTree constructor: num level overflow");
70 throw std::exception();
71 }
77 ++numLevels;
78 } while(nodesPerLevel > 1);
79
80 if(nodeCount == 0)
81 {
82 Logger::logger_.warn("tgt_create numnodes == 0, no tree created.");
83 throw std::runtime_error("tgt_create numnodes == 0, no tree created");
84 }
85
87 auto currentNode = nodes;
90
91 for(int8_t i = 0; i < numLevels - 1; ++i)
92 {
93 for(uint32_t j = 0; j < resLeavesHeight[i]; ++j)
94 {
96 while(--k >= 0)
97 {
100 if(--k >= 0)
101 {
103 ++currentNode;
104 }
105 ++parentNode;
106 }
107 if((j & 1) || j == resLeavesHeight[i] - 1)
108 {
110 }
111 else
112 {
115 }
116 }
117 }
118 currentNode->parent = nullptr;
119 reset();
120 }
122 {
123 delete[] nodes;
124 }
125
126 constexpr T getUninitializedValue(void)
127 {
128 return (std::numeric_limits<T>::max)();
129 }
133 void reset()
134 {
135 for(uint64_t i = 0; i < nodeCount; ++i)
136 {
137 auto current_node = nodes + i;
139 current_node->low = 0;
140 current_node->known = false;
141 }
142 }
148 void setvalue(uint64_t leafno, T value)
149 {
150 auto node = nodes + leafno;
151 while(node && node->value > value)
152 {
153 node->value = value;
154 node = node->parent;
155 }
156 }
164 bool compress(BitIO* bio, uint64_t leafno, T threshold)
165 {
167 auto nodeStackPtr = nodeStack;
168 auto node = nodes + leafno;
169 while(node->parent)
170 {
171 *nodeStackPtr++ = node;
172 node = node->parent;
173 }
174 T low = 0;
175 while(true)
176 {
177 if(node->low < low)
178 node->low = low;
179 else
180 low = node->low;
181
182 while(low < threshold)
183 {
184 if(low >= node->value)
185 {
186 if(!node->known)
187 {
188 if(!bio->write(1))
189 return false;
190 node->known = true;
191 }
192 break;
193 }
194 if(!bio->write(0))
195 return false;
196 ++low;
197 }
198 node->low = low;
200 break;
201 node = *--nodeStackPtr;
202 }
203 return true;
204 }
212 void decodeValue(BitIO* bio, uint64_t leafno, T threshold, T* value)
213 {
215 *value = getUninitializedValue();
216 auto nodeStackPtr = nodeStack;
217 auto node = nodes + leafno;
218 // climb to top of tree
219 while(node->parent)
220 {
221 *nodeStackPtr++ = node;
222 node = node->parent;
223 }
224 // descend to bottom of tree
225 T low = 0;
226 while(true)
227 {
228 if(node->low < low)
229 node->low = low;
230 else
231 low = node->low;
232 while(low < threshold && low < node->value)
233 {
234 if(bio->read())
235 {
236 node->value = low;
237 break;
238 }
239 low++;
240 }
241 node->low = low;
243 break;
244 node = *--nodeStackPtr;
245 }
246 *value = node->value;
247 }
248
249 private:
254};
255
258
259} // namespace grk
Definition BitIO.h:33
Tag tree.
Definition TagTree.h:47
uint64_t nodeCount
Definition TagTree.h:252
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:164
TagTreeNode< T > * nodes
Definition TagTree.h:253
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:133
void setvalue(uint64_t leafno, T value)
Set the value of a leaf of a tag tree.
Definition TagTree.h:148
~TagTree()
Definition TagTree.h:121
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:212
uint32_t leavesHeight_
Definition TagTree.h:251
uint32_t leavesWidth_
Definition TagTree.h:250
constexpr T getUninitializedValue(void)
Definition TagTree.h:126
Copyright (C) 2016-2024 Grok Image Compression Inc.
Definition ICacheable.h:20
void grk_read(const uint8_t *buffer, TYPE *value, uint32_t numBytes)
Definition BufferedStream.h:239
TagTree< uint16_t > TagTreeU16
Definition TagTree.h:257
TagTree< uint8_t > TagTreeU8
Definition TagTree.h:256
void warn(const char *fmt,...) override
Definition Logger.h:44
void error(const char *fmt,...) override
Definition Logger.h:53
static Logger logger_
Definition Logger.h:70
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