DCCL v3
field_codec_arithmetic.cpp
1 // Copyright 2009-2017 Toby Schneider (http://gobysoft.org/index.wt/people/toby)
2 // GobySoft, LLC (for 2013-)
3 // Massachusetts Institute of Technology (for 2007-2014)
4 // Community contributors (see AUTHORS file)
5 //
6 //
7 // This file is part of the Dynamic Compact Control Language Library
8 // ("DCCL").
9 //
10 // DCCL is free software: you can redistribute it and/or modify
11 // it under the terms of the GNU Lesser General Public License as published by
12 // the Free Software Foundation, either version 2.1 of the License, or
13 // (at your option) any later version.
14 //
15 // DCCL is distributed in the hope that it will be useful,
16 // but WITHOUT ANY WARRANTY; without even the implied warranty of
17 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 // GNU Lesser General Public License for more details.
19 //
20 // You should have received a copy of the GNU Lesser General Public License
21 // along with DCCL. If not, see <http://www.gnu.org/licenses/>.
22 #include "field_codec_arithmetic.h"
23 #include "dccl/field_codec_manager.h"
24 
25 using dccl::dlog;
26 using namespace dccl::logger;
27 
28 std::map<std::string, dccl::arith::Model> dccl::arith::ModelManager::arithmetic_models_;
29 const dccl::arith::Model::symbol_type dccl::arith::Model::OUT_OF_RANGE_SYMBOL;
30 const dccl::arith::Model::symbol_type dccl::arith::Model::EOF_SYMBOL;
31 const dccl::arith::Model::symbol_type dccl::arith::Model::MIN_SYMBOL;
32 const int dccl::arith::Model::CODE_VALUE_BITS;
33 const int dccl::arith::Model::FREQUENCY_BITS;
34 const dccl::arith::Model::freq_type dccl::arith::Model::MAX_FREQUENCY;
35 std::map<std::string, std::map<std::string, dccl::Bitset> > dccl::arith::Model::last_bits_map;
36 
37 // shared library load
38 extern "C"
39 {
40  void dccl3_load(dccl::Codec* dccl)
41  {
42  dccl_arithmetic_load(dccl);
43  }
44 
45  void dccl_arithmetic_load(dccl::Codec* dccl)
46  {
47  using namespace dccl;
48  using namespace dccl::arith;
49 
50  FieldCodecManager::add<ArithmeticFieldCodec<int32> >("_arithmetic");
51  FieldCodecManager::add<ArithmeticFieldCodec<int64> >("_arithmetic");
52  FieldCodecManager::add<ArithmeticFieldCodec<uint32> >("_arithmetic");
53  FieldCodecManager::add<ArithmeticFieldCodec<uint64> >("_arithmetic");
54  FieldCodecManager::add<ArithmeticFieldCodec<double> >("_arithmetic");
55  FieldCodecManager::add<ArithmeticFieldCodec<float> >("_arithmetic");
56  FieldCodecManager::add<ArithmeticFieldCodec<bool> >("_arithmetic");
57  FieldCodecManager::add<ArithmeticFieldCodec<const google::protobuf::EnumValueDescriptor*> >("_arithmetic");
58 
59  FieldCodecManager::add<ArithmeticFieldCodec<int32> >("dccl.arithmetic");
60  FieldCodecManager::add<ArithmeticFieldCodec<int64> >("dccl.arithmetic");
61  FieldCodecManager::add<ArithmeticFieldCodec<uint32> >("dccl.arithmetic");
62  FieldCodecManager::add<ArithmeticFieldCodec<uint64> >("dccl.arithmetic");
63  FieldCodecManager::add<ArithmeticFieldCodec<double> >("dccl.arithmetic");
64  FieldCodecManager::add<ArithmeticFieldCodec<float> >("dccl.arithmetic");
65  FieldCodecManager::add<ArithmeticFieldCodec<bool> >("dccl.arithmetic");
66  FieldCodecManager::add<ArithmeticFieldCodec<const google::protobuf::EnumValueDescriptor*> >("dccl.arithmetic");
67 
68  }
69  void dccl3_unload(dccl::Codec* dccl)
70  {
71  dccl_arithmetic_unload(dccl);
72  }
73 
74  void dccl_arithmetic_unload(dccl::Codec* dccl)
75  {
76  using namespace dccl;
77  using namespace dccl::arith;
78 
79  FieldCodecManager::remove<ArithmeticFieldCodec<int32> >("_arithmetic");
80  FieldCodecManager::remove<ArithmeticFieldCodec<int64> >("_arithmetic");
81  FieldCodecManager::remove<ArithmeticFieldCodec<uint32> >("_arithmetic");
82  FieldCodecManager::remove<ArithmeticFieldCodec<uint64> >("_arithmetic");
83  FieldCodecManager::remove<ArithmeticFieldCodec<double> >("_arithmetic");
84  FieldCodecManager::remove<ArithmeticFieldCodec<float> >("_arithmetic");
85  FieldCodecManager::remove<ArithmeticFieldCodec<bool> >("_arithmetic");
86  FieldCodecManager::remove<ArithmeticFieldCodec<const google::protobuf::EnumValueDescriptor*> >("_arithmetic");
87 
88  FieldCodecManager::remove<ArithmeticFieldCodec<int32> >("dccl.arithmetic");
89  FieldCodecManager::remove<ArithmeticFieldCodec<int64> >("dccl.arithmetic");
90  FieldCodecManager::remove<ArithmeticFieldCodec<uint32> >("dccl.arithmetic");
91  FieldCodecManager::remove<ArithmeticFieldCodec<uint64> >("dccl.arithmetic");
92  FieldCodecManager::remove<ArithmeticFieldCodec<double> >("dccl.arithmetic");
93  FieldCodecManager::remove<ArithmeticFieldCodec<float> >("dccl.arithmetic");
94  FieldCodecManager::remove<ArithmeticFieldCodec<bool> >("dccl.arithmetic");
95  FieldCodecManager::remove<ArithmeticFieldCodec<const google::protobuf::EnumValueDescriptor*> >("dccl.arithmetic");
96 
97  }
98 }
99 
100 dccl::arith::Model::symbol_type dccl::arith::Model::value_to_symbol(value_type value) const
101 {
102  if(value < *user_model_.value_bound().begin() || value > *(user_model_.value_bound().end()-1))
103  return Model::OUT_OF_RANGE_SYMBOL;
104 
105 
106  google::protobuf::RepeatedField<double>::const_iterator upper_it =
107  std::upper_bound(user_model_.value_bound().begin(),
108  user_model_.value_bound().end(),
109  value);
110 
111 
112  google::protobuf::RepeatedField<double>::const_iterator lower_it =
113  (upper_it == user_model_.value_bound().begin()) ? upper_it : upper_it - 1;
114 
115  double lower_diff = std::abs((*lower_it)*(*lower_it) - value*value);
116  double upper_diff = std::abs((*upper_it)*(*upper_it) - value*value);
117 
118 // std::cout << "value: " << value << std::endl;
119 // std::cout << "lower_value: " << *lower_it << std::endl;
120 // std::cout << "upper_value: " << *upper_it << std::endl;
121 
122  symbol_type symbol = ((lower_diff < upper_diff) ? lower_it : upper_it)
123  - user_model_.value_bound().begin();
124 
125 
126  return symbol;
127 
128 }
129 
130 
131 dccl::arith::Model::value_type dccl::arith::Model::symbol_to_value(symbol_type symbol) const
132 {
133 
134  if(symbol == EOF_SYMBOL)
135  throw(Exception("EOF symbol has no value."));
136 
137  value_type value = (symbol == Model::OUT_OF_RANGE_SYMBOL) ?
138  std::numeric_limits<value_type>::quiet_NaN() :
139  user_model_.value_bound(symbol);
140 
141  return value;
142 }
143 
144 
145 std::pair<dccl::arith::Model::freq_type, dccl::arith::Model::freq_type> dccl::arith::Model::symbol_to_cumulative_freq(symbol_type symbol, ModelState state) const
146 {
147  const boost::bimap<symbol_type, freq_type>& c_freqs = (state == ENCODER) ?
148  encoder_cumulative_freqs_ :
149  decoder_cumulative_freqs_;
150 
151  boost::bimap<symbol_type, freq_type>::left_map::const_iterator c_freq_it =
152  c_freqs.left.find(symbol);
153  std::pair<freq_type, freq_type> c_freq_range;
154  c_freq_range.second = c_freq_it->second;
155  if(c_freq_it == c_freqs.left.begin())
156  {
157  c_freq_range.first = 0;
158  }
159  else
160  {
161  c_freq_it--;
162  c_freq_range.first = c_freq_it->second;
163  }
164  return c_freq_range;
165 
166 }
167 
168 std::pair<dccl::arith::Model::symbol_type, dccl::arith::Model::symbol_type> dccl::arith::Model::cumulative_freq_to_symbol(std::pair<freq_type, freq_type> c_freq_pair, ModelState state) const
169 {
170 
171  const boost::bimap<symbol_type, freq_type>& c_freqs = (state == ENCODER) ?
172  encoder_cumulative_freqs_ :
173  decoder_cumulative_freqs_;
174 
175  std::pair<symbol_type, symbol_type> symbol_pair;
176 
177  // find the symbol for which the cumulative frequency is greater than
178  // e.g.
179  // symbol: 0 freq: 10 c_freq: 10 [0 ... 10)
180  // symbol: 1 freq: 15 c_freq: 25 [10 ... 25)
181  // symbol: 2 freq: 10 c_freq: 35 [25 ... 35)
182  // searching for c_freq of 30 should return symbol 2
183  // searching for c_freq of 10 should return symbol 1
184  symbol_pair.first = c_freqs.right.upper_bound(c_freq_pair.first)->second;
185 
186 
187  if(symbol_pair.first == c_freqs.left.rbegin()->first)
188  symbol_pair.second = symbol_pair.first; // last symbol can't be ambiguous on the low end
189  else if(c_freqs.left.find(symbol_pair.first)->second > c_freq_pair.second)
190  symbol_pair.second = symbol_pair.first; // unambiguously this symbol
191  else
192  symbol_pair.second = symbol_pair.first + 1;
193 
194 
195 
196  return symbol_pair;
197 }
198 
199 
200 void dccl::arith::Model::update_model(symbol_type symbol, ModelState state)
201 {
202  if(!user_model_.is_adaptive())
203  return;
204 
205  boost::bimap<symbol_type, freq_type>& c_freqs = (state == ENCODER) ?
206  encoder_cumulative_freqs_ :
207  decoder_cumulative_freqs_;
208 
209  if(dlog.is(DEBUG3))
210  {
211  dlog << "Model was: " << std::endl;
212  for(symbol_type i = MIN_SYMBOL, n = max_symbol(); i <= n; ++i)
213  {
214  boost::bimap<symbol_type, freq_type>::left_iterator it =
215  c_freqs.left.find(i);
216  if(it != c_freqs.left.end())
217  dlog << "Symbol: " << it->first << ", c_freq: " << it->second << std::endl;
218  }
219  }
220 
221 
222  for(symbol_type i = max_symbol(), n = symbol; i >= n; --i)
223  {
224  boost::bimap<symbol_type, freq_type>::left_iterator it =
225  c_freqs.left.find(i);
226  if(it != c_freqs.left.end())
227  c_freqs.left.replace_data(it, it->second + 1);
228  }
229 
230  if(dlog.is(DEBUG3))
231  {
232  dlog << "Model is now: " << std::endl;
233  for(symbol_type i = MIN_SYMBOL, n = max_symbol(); i <= n; ++i)
234  {
235  boost::bimap<symbol_type, freq_type>::left_iterator it =
236  c_freqs.left.find(i);
237  if(it != c_freqs.left.end())
238  dlog << "Symbol: " << it->first << ", c_freq: " << it->second << std::endl;
239  }
240  }
241 
242  dlog.is(DEBUG3) && dlog << "total freq: " << total_freq(state) << std::endl;
243 
244 }
The Dynamic CCL enCODer/DECoder. This is the main class you will use to load, encode and decode DCCL ...
Definition: codec.h:56
DCCL Arithmetic Encoder Library namespace.
Dynamic Compact Control Language namespace.
bool is(logger::Verbosity verbosity, logger::Group group=logger::GENERAL)
Indicates the verbosity of the Logger until the next std::flush or std::endl. The boolean return is u...
Definition: logger.h:145
Exception class for DCCL.
Definition: exception.h:31