Grok  9.5.0
TagTree.h
Go to the documentation of this file.
1 /*
2  * Copyright (C) 2016-2021 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  n = (uint64_t)nplh[numlvls] * nplv[numlvls];
68  nplh[numlvls + 1] = (uint32_t)(((uint64_t)nplh[numlvls] + 1) / 2);
69  nplv[numlvls + 1] = (uint32_t)(((uint64_t)nplv[numlvls] + 1) / 2);
70  numnodes += n;
71  ++numlvls;
72  } while(n > 1);
73 
74  if(numnodes == 0)
75  {
76  GRK_WARN("tgt_create numnodes == 0, no tree created.");
77  throw std::runtime_error("tgt_create numnodes == 0, no tree created");
78  }
79 
81  auto node = nodes;
82  auto parent_node = nodes + (uint64_t)numleafsh * numleafsv;
83  auto parent_node0 = parent_node;
84 
85  for(int8_t i = 0; i < numlvls - 1; ++i)
86  {
87  for(uint32_t j = 0; j < nplv[i]; ++j)
88  {
89  int64_t k = nplh[i];
90  while(--k >= 0)
91  {
92  node->parent = parent_node;
93  ++node;
94  if(--k >= 0)
95  {
96  node->parent = parent_node;
97  ++node;
98  }
99  ++parent_node;
100  }
101  if((j & 1) || j == nplv[i] - 1)
102  {
103  parent_node0 = parent_node;
104  }
105  else
106  {
107  parent_node = parent_node0;
108  parent_node0 += nplh[i];
109  }
110  }
111  }
112  node->parent = 0;
113  reset();
114  }
116  {
117  delete[] nodes;
118  }
119 
120  constexpr T getUninitializedValue(void)
121  {
122  return (std::numeric_limits<T>::max)();
123  }
127  void reset()
128  {
129  for(uint64_t i = 0; i < numnodes; ++i)
130  {
131  auto current_node = nodes + i;
132  current_node->value = getUninitializedValue();
133  current_node->low = 0;
134  current_node->known = false;
135  }
136  }
142  void setvalue(uint64_t leafno, T value)
143  {
144  auto node = nodes + leafno;
145  while(node && node->value > value)
146  {
147  node->value = value;
148  node = node->parent;
149  }
150  }
158  bool compress(BitIO* bio, uint64_t leafno, T threshold)
159  {
160  TagTreeNode<T>* stk[31];
161  auto stkptr = stk;
162  auto node = nodes + leafno;
163  while(node->parent)
164  {
165  *stkptr++ = node;
166  node = node->parent;
167  }
168  T low = 0;
169  while(true)
170  {
171  if(node->low < low)
172  node->low = low;
173  else
174  low = node->low;
175 
176  while(low < threshold)
177  {
178  if(low >= node->value)
179  {
180  if(!node->known)
181  {
182  if(!bio->write(1, 1))
183  return false;
184  node->known = true;
185  }
186  break;
187  }
188  if(!bio->write(0, 1))
189  return false;
190  ++low;
191  }
192 
193  node->low = low;
194  if(stkptr == stk)
195  break;
196  node = *--stkptr;
197  }
198  return true;
199  }
207  void decodeValue(BitIO* bio, uint64_t leafno, T threshold, T* value)
208  {
209  TagTreeNode<T>* stk[31];
210  *value = getUninitializedValue();
211  auto stkptr = stk;
212  auto node = nodes + leafno;
213  while(node->parent)
214  {
215  *stkptr++ = node;
216  node = node->parent;
217  }
218  T low = 0;
219  while(true)
220  {
221  if(node->low < low)
222  node->low = low;
223  else
224  low = node->low;
225  while(low < threshold && low < node->value)
226  {
227  uint32_t temp = 0;
228  bio->read(&temp, 1);
229  if(temp)
230  {
231  node->value = T(low);
232  break;
233  }
234  else
235  {
236  ++low;
237  }
238  }
239  node->low = low;
240  if(stkptr == stk)
241  break;
242  node = *--stkptr;
243  }
244  *value = node->value;
245  }
246 
247  private:
248  uint32_t numleafsh;
249  uint32_t numleafsv;
250  uint64_t numnodes;
252 };
253 
256 
257 } // 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:250
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:158
TagTreeNode< T > * nodes
Definition: TagTree.h:251
void reset()
Reset a tag tree (set all leaves to 0)
Definition: TagTree.h:127
void setvalue(uint64_t leafno, T value)
Set the value of a leaf of a tag tree.
Definition: TagTree.h:142
~TagTree()
Definition: TagTree.h:115
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:207
uint32_t numleafsv
Definition: TagTree.h:249
constexpr T getUninitializedValue(void)
Definition: TagTree.h:120
uint32_t numleafsh
Definition: TagTree.h:248
Copyright (C) 2016-2021 Grok Image Compression Inc.
Definition: ICacheable.h:20
void GRK_WARN(const char *fmt,...)
Definition: logger.cpp:49
TagTree< uint16_t > TagTreeU16
Definition: TagTree.h:255
TagTree< uint8_t > TagTreeU8
Definition: TagTree.h:254
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