55 TagTree(uint32_t leavesWidth, uint32_t leavesHeight)
58 uint32_t resLeavesWidth[32];
59 uint32_t resLeavesHeight[32];
64 uint64_t nodesPerLevel;
69 GRK_ERROR(
"TagTree constructor: num level overflow");
70 throw std::exception();
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);
79 }
while(nodesPerLevel > 1);
83 GRK_WARN(
"tgt_create numnodes == 0, no tree created.");
84 throw std::runtime_error(
"tgt_create numnodes == 0, no tree created");
88 auto currentNode =
nodes;
90 auto parentNodeNext = parentNode;
92 for(int8_t i = 0; i < numLevels - 1; ++i)
94 for(uint32_t j = 0; j < resLeavesHeight[i]; ++j)
96 int64_t k = resLeavesWidth[i];
99 currentNode->parent = parentNode;
103 currentNode->parent = parentNode;
108 if((j & 1) || j == resLeavesHeight[i] - 1)
110 parentNodeNext = parentNode;
114 parentNode = parentNodeNext;
115 parentNodeNext += resLeavesWidth[i];
119 currentNode->parent =
nullptr;
129 return (std::numeric_limits<T>::max)();
138 auto current_node =
nodes + i;
140 current_node->low = 0;
141 current_node->known =
false;
151 auto node =
nodes + leafno;
152 while(node && node->value > value)
168 auto nodeStackPtr = nodeStack;
169 auto node =
nodes + leafno;
172 *nodeStackPtr++ = node;
183 while(low < threshold)
185 if(low >= node->value)
200 if(nodeStackPtr == nodeStack)
202 node = *--nodeStackPtr;
217 auto nodeStackPtr = nodeStack;
218 auto node =
nodes + leafno;
222 *nodeStackPtr++ = node;
233 while(low < threshold && low < node->value)
243 if(nodeStackPtr == nodeStack)
245 node = *--nodeStackPtr;
247 *value = node->value;
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