Grok  9.7.5
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 mynumleafsh, uint32_t mynumleafsv)
56  : numleafsh(mynumleafsh), numleafsv(mynumleafsv), numnodes(0), nodes(nullptr)
57  {
58  uint32_t nplh[32];
59  uint32_t nplv[32];
60  int8_t numlvls = 0;
61  nplh[0] = numleafsh;
62  nplv[0] = numleafsv;
63  numnodes = 0;
64  uint64_t n;
65  do
66  {
67  if(numlvls == 32)
68  {
69  GRK_ERROR("TagTree constructor: num level overflow");
70  throw std::exception();
71  }
72  n = (uint64_t)nplh[numlvls] * nplv[numlvls];
73  nplh[numlvls + 1] = (uint32_t)(((uint64_t)nplh[numlvls] + 1) / 2);
74  nplv[numlvls + 1] = (uint32_t)(((uint64_t)nplv[numlvls] + 1) / 2);
75  numnodes += n;
76  ++numlvls;
77  } while(n > 1);
78 
79  if(numnodes == 0)
80  {
81  GRK_WARN("tgt_create numnodes == 0, no tree created.");
82  throw std::runtime_error("tgt_create numnodes == 0, no tree created");
83  }
84 
86  auto node = nodes;
87  auto parent_node = nodes + (uint64_t)numleafsh * numleafsv;
88  auto parent_node0 = parent_node;
89 
90  for(int8_t i = 0; i < numlvls - 1; ++i)
91  {
92  for(uint32_t j = 0; j < nplv[i]; ++j)
93  {
94  int64_t k = nplh[i];
95  while(--k >= 0)
96  {
97  node->parent = parent_node;
98  ++node;
99  if(--k >= 0)
100  {
101  node->parent = parent_node;
102  ++node;
103  }
104  ++parent_node;
105  }
106  if((j & 1) || j == nplv[i] - 1)
107  {
108  parent_node0 = parent_node;
109  }
110  else
111  {
112  parent_node = parent_node0;
113  parent_node0 += nplh[i];
114  }
115  }
116  }
117  node->parent = 0;
118  reset();
119  }
121  {
122  delete[] nodes;
123  }
124 
125  constexpr T getUninitializedValue(void)
126  {
127  return (std::numeric_limits<T>::max)();
128  }
132  void reset()
133  {
134  for(uint64_t i = 0; i < numnodes; ++i)
135  {
136  auto current_node = nodes + i;
137  current_node->value = getUninitializedValue();
138  current_node->low = 0;
139  current_node->known = false;
140  }
141  }
147  void setvalue(uint64_t leafno, T value)
148  {
149  auto node = nodes + leafno;
150  while(node && node->value > value)
151  {
152  node->value = value;
153  node = node->parent;
154  }
155  }
163  bool compress(BitIO* bio, uint64_t leafno, T threshold)
164  {
165  TagTreeNode<T>* stk[31];
166  auto stkptr = stk;
167  auto node = nodes + leafno;
168  while(node->parent)
169  {
170  *stkptr++ = node;
171  node = node->parent;
172  }
173  T low = 0;
174  while(true)
175  {
176  if(node->low < low)
177  node->low = low;
178  else
179  low = node->low;
180 
181  while(low < threshold)
182  {
183  if(low >= node->value)
184  {
185  if(!node->known)
186  {
187  if(!bio->write(1, 1))
188  return false;
189  node->known = true;
190  }
191  break;
192  }
193  if(!bio->write(0, 1))
194  return false;
195  ++low;
196  }
197 
198  node->low = low;
199  if(stkptr == stk)
200  break;
201  node = *--stkptr;
202  }
203  return true;
204  }
212  void decodeValue(BitIO* bio, uint64_t leafno, T threshold, T* value)
213  {
214  TagTreeNode<T>* stk[31];
215  *value = getUninitializedValue();
216  auto stkptr = stk;
217  auto node = nodes + leafno;
218  while(node->parent)
219  {
220  *stkptr++ = node;
221  node = node->parent;
222  }
223  T low = 0;
224  while(true)
225  {
226  if(node->low < low)
227  node->low = low;
228  else
229  low = node->low;
230  while(low < threshold && low < node->value)
231  {
232  uint32_t temp = 0;
233  bio->read(&temp, 1);
234  if(temp)
235  {
236  node->value = T(low);
237  break;
238  }
239  else
240  {
241  ++low;
242  }
243  }
244  node->low = low;
245  if(stkptr == stk)
246  break;
247  node = *--stkptr;
248  }
249  *value = node->value;
250  }
251 
252  private:
253  uint32_t numleafsh;
254  uint32_t numleafsv;
255  uint64_t numnodes;
257 };
258 
261 
262 } // namespace grk
Definition: BitIO.h:33
void read(uint32_t *bits, uint32_t n)
Read bits.
Definition: BitIO.cpp:114
bool write(uint32_t v, uint32_t n)
Write bits.
Definition: BitIO.cpp:103
Tag tree.
Definition: TagTree.h:47
uint64_t numnodes
Definition: TagTree.h:255
TagTree(uint32_t mynumleafsh, uint32_t mynumleafsv)
Create a tag tree.
Definition: TagTree.h:55
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:163
TagTreeNode< T > * nodes
Definition: TagTree.h:256
void reset()
Reset a tag tree (set all leaves to 0)
Definition: TagTree.h:132
void setvalue(uint64_t leafno, T value)
Set the value of a leaf of a tag tree.
Definition: TagTree.h:147
~TagTree()
Definition: TagTree.h:120
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 numleafsv
Definition: TagTree.h:254
constexpr T getUninitializedValue(void)
Definition: TagTree.h:125
uint32_t numleafsh
Definition: TagTree.h:253
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:260
TagTree< uint8_t > TagTreeU8
Definition: TagTree.h:259
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