DCCL v3
field_codec_arithmetic.h
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 // This code is adapted from the reference code provided by Witten et al. "Arithmetic Coding for Data Compression," Communications of the ACM, June 1987, Vol 30, Number 6
23 
24 
25 #ifndef DCCLFIELDCODECARITHMETIC20120726H
26 #define DCCLFIELDCODECARITHMETIC20120726H
27 
28 #include <limits>
29 #include <algorithm>
30 
31 #include <boost/bimap.hpp>
32 #include <boost/lexical_cast.hpp>
33 
34 #include "dccl/field_codec_typed.h"
35 
36 #include "dccl/arithmetic/protobuf/arithmetic_extensions.pb.h"
37 #include "dccl/arithmetic/protobuf/arithmetic.pb.h"
38 
39 #include "dccl/logger.h"
40 
41 #include "dccl/binary.h"
42 
43 extern "C"
44 {
45  void dccl3_load(dccl::Codec* dccl);
46  void dccl3_unload(dccl::Codec* dccl);
47  void dccl_arithmetic_load(dccl::Codec* dccl);
48  void dccl_arithmetic_unload(dccl::Codec* dccl);
49 }
50 
51 namespace dccl
52 {
54  namespace arith
55  {
56  class Model
57  {
58  public:
59  typedef uint32 freq_type;
60  typedef int symbol_type; // google protobuf RepeatedField size type
61  typedef double value_type;
62 
63  static const symbol_type OUT_OF_RANGE_SYMBOL = -1;
64  static const symbol_type EOF_SYMBOL = -2;
65  static const symbol_type MIN_SYMBOL = EOF_SYMBOL;
66 
67  static const int CODE_VALUE_BITS = 32;
68  static const int FREQUENCY_BITS = CODE_VALUE_BITS - 2;
69 
70  static const freq_type MAX_FREQUENCY = (1 << FREQUENCY_BITS) - 1;
71 
72 
73  // maps message name -> map of field name -> last size (bits)
74  static std::map<std::string, std::map<std::string, Bitset> > last_bits_map;
75 
76 
77  Model(const protobuf::ArithmeticModel& user)
78  : user_model_(user)
79  { }
80 
81  enum ModelState
82  { ENCODER, DECODER };
83 
84 
85  symbol_type value_to_symbol(value_type value) const;
86  value_type symbol_to_value(symbol_type symbol) const;
87  symbol_type total_symbols() // EOF and OUT_OF_RANGE plus all user defined
88  { return encoder_cumulative_freqs_.size(); }
89 
90  const protobuf::ArithmeticModel& user_model() const
91  { return user_model_; }
92 
93  symbol_type max_symbol() const { return user_model_.frequency_size() - 1; }
94 
95  freq_type total_freq(ModelState state) const
96  {
97 
98  const boost::bimap<symbol_type, freq_type>& c_freqs = (state == ENCODER) ?
99  encoder_cumulative_freqs_ :
100  decoder_cumulative_freqs_;
101 
102  return c_freqs.left.at(max_symbol());
103  }
104 
105  void update_model(symbol_type symbol, ModelState state);
106 
107 
108  std::pair<freq_type, freq_type> symbol_to_cumulative_freq(symbol_type symbol, ModelState state) const;
109  std::pair<symbol_type, symbol_type> cumulative_freq_to_symbol(std::pair<freq_type, freq_type> c_freq_pair, ModelState state) const;
110 
111  friend class ModelManager;
112  private:
113  protobuf::ArithmeticModel user_model_;
114  boost::bimap<symbol_type, freq_type> encoder_cumulative_freqs_;
115  boost::bimap<symbol_type, freq_type> decoder_cumulative_freqs_;
116  };
117 
119  {
120  public:
121  static void set_model(const protobuf::ArithmeticModel& model)
122  {
123  Model new_model(model);
124  create_and_validate_model(&new_model);
125  if(arithmetic_models_.count(model.name()))
126  arithmetic_models_.erase(model.name());
127  arithmetic_models_.insert(std::make_pair(model.name(), new_model));
128  }
129 
130  static void create_and_validate_model(Model* model)
131  {
132  if(!model->user_model_.IsInitialized())
133  {
134  throw(Exception("Invalid model: " +
135  model->user_model_.DebugString() +
136  "Missing fields: " + model->user_model_.InitializationErrorString()));
137  }
138 
139  Model::freq_type cumulative_freq = 0;
140  for(Model::symbol_type symbol = Model::MIN_SYMBOL, n = model->user_model_.frequency_size(); symbol < n; ++symbol)
141  {
142  Model::freq_type freq;
143  if(symbol == Model::EOF_SYMBOL)
144  freq = model->user_model_.eof_frequency();
145  else if(symbol == Model::OUT_OF_RANGE_SYMBOL)
146  freq = model->user_model_.out_of_range_frequency();
147  else
148  freq = model->user_model_.frequency(symbol);
149 
150  if(freq == 0 && symbol != Model::OUT_OF_RANGE_SYMBOL && symbol != Model::EOF_SYMBOL)
151  {
152  throw(Exception("Invalid model: " +
153  model->user_model_.DebugString() +
154  "All frequencies must be nonzero."));
155  }
156  cumulative_freq += freq;
157  model->encoder_cumulative_freqs_.left.insert(std::make_pair(symbol, cumulative_freq));
158 
159  }
160 
161  // must have separate models for adaptive encoding.
162  model->decoder_cumulative_freqs_ = model->encoder_cumulative_freqs_;
163 
164  if(model->total_freq(Model::ENCODER) > Model::MAX_FREQUENCY)
165  {
166  throw(Exception("Invalid model: " +
167  model->user_model_.DebugString() +
168  "Sum of all frequencies must be less than " +
169  boost::lexical_cast<std::string>(Model::MAX_FREQUENCY) +
170  " in order to use 64 bit arithmetic"));
171  }
172 
173  if(model->user_model_.value_bound_size() != model->user_model_.frequency_size() + 1)
174  {
175  throw(Exception("Invalid model: " +
176  model->user_model_.DebugString() +
177  "`value_bound` size must be exactly 1 more than number of symbols (= size of `frequency`)."));
178  }
179 
180 
181 // is `value_bound` repeated field strictly monotonically increasing?
182  if(std::adjacent_find (model->user_model_.value_bound().begin(),
183  model->user_model_.value_bound().end(),
184  std::greater_equal<Model::value_type>()) != model->user_model_.value_bound().end())
185  {
186  throw(Exception("Invalid model: " +
187  model->user_model_.DebugString() +
188  "`value_bound` must be monotonically increasing."));
189  }
190  }
191 
192 
193  static Model& find(const std::string& name)
194  {
195  std::map<std::string, Model>::iterator it = arithmetic_models_.find(name);
196  if(it == arithmetic_models_.end())
197  throw(Exception("Cannot find model called: " + name));
198  else
199  return it->second;
200  }
201 
202  private:
203  static std::map<std::string, Model> arithmetic_models_;
204  };
205 
206 
207  template<typename FieldType = Model::value_type>
208  class ArithmeticFieldCodecBase : public RepeatedTypedFieldCodec<Model::value_type, FieldType>
209  {
210  public:
211 
212  static const uint64 TOP_VALUE = (static_cast<uint64>(1) << Model::CODE_VALUE_BITS) - 1; // 11111111...
213  static const uint64 HALF = (static_cast<uint64>(1) << (Model::CODE_VALUE_BITS-1)); // 10000000...
214  static const uint64 FIRST_QTR = HALF >> 1; // 01000000...
215  static const uint64 THIRD_QTR = HALF+FIRST_QTR; // 11000000...
216 
217  Bitset encode_repeated(const std::vector<Model::value_type>& wire_value)
218  {
219  return encode_repeated(wire_value, true);
220  }
221 
222  Bitset encode_repeated(const std::vector<Model::value_type>& wire_value,
223  bool update_model)
224  {
225  using dccl::dlog;
226  using namespace dccl::logger;
227 
228  Model& model = current_model();
229 
230  uint64 low = 0; // lowest code value (0.0 in decimal version)
231  uint64 high = TOP_VALUE; // highest code value (1.0 in decimal version)
232  int bits_to_follow = 0; // bits to follow with after expanding around half
233  Bitset bits;
234 
235 
236  for(unsigned value_index = 0, n = max_repeat(); value_index < n; ++value_index)
237  {
238  Model::symbol_type symbol = Model::EOF_SYMBOL;
239 
240  if(wire_value.size() > value_index)
241  {
242  Model::value_type value = wire_value[value_index];
243  dlog.is(DEBUG3) &&
244  dlog << "(ArithmeticFieldCodec) value is : " << value << std::endl;
245 
246  symbol = model.value_to_symbol(value);
247  }
248 
249  // if out-of-range is given no frequency, end encoding
250  if(symbol == Model::OUT_OF_RANGE_SYMBOL &&
251  model.user_model().out_of_range_frequency() == 0)
252  {
253 
254  dlog.is(DEBUG2) &&
255  dlog << "(ArithmeticFieldCodec) out of range symbol, but no frequency given; ending encoding" << std::endl;
256 
257  symbol = Model::EOF_SYMBOL;
258  }
259 
260  // if EOF_SYMBOL is given no frequency, use most probable symbol and give a warning
261  if(symbol == Model::EOF_SYMBOL &&
262  model.user_model().eof_frequency() == 0)
263  {
264  dlog.is(DEBUG2) &&
265  dlog << "(ArithmeticFieldCodec) end of file, but no frequency given; filling with most probable symbol" << std::endl;
266  symbol = *std::max_element(model.user_model().frequency().begin(), model.user_model().frequency().end());
267  }
268 
269 
270  dlog.is(DEBUG3) &&
271  dlog << "(ArithmeticFieldCodec) symbol is : " << symbol << std::endl;
272 
273  dlog.is(DEBUG3) &&
274  dlog << "(ArithmeticFieldCodec) current interval: [" << (double)low / TOP_VALUE << ","
275  << (double)high / TOP_VALUE << ")" << std::endl;
276 
277 
278  uint64 range = (high-low)+1;
279 
280  std::pair<Model::freq_type, Model::freq_type> c_freq_range =
281  model.symbol_to_cumulative_freq(symbol, Model::ENCODER);
282 
283  dlog.is(DEBUG3) &&
284  dlog << "(ArithmeticFieldCodec) input symbol (" << symbol
285  << ") cumulative freq: ["<< c_freq_range.first << "," << c_freq_range.second << ")" << std::endl;
286 
287  high = low + (range*c_freq_range.second)/model.total_freq(Model::ENCODER)-1;
288  low += (range*c_freq_range.first)/model.total_freq(Model::ENCODER);
289 
290  dlog.is(DEBUG3) &&
291  dlog << "(ArithmeticFieldCodec) input symbol (" << symbol << ") interval: ["
292  << (double)low / TOP_VALUE << "," << (double)high / TOP_VALUE << ")" << std::endl;
293 
294 
295 
296  dlog.is(DEBUG3) &&
297  dlog << "(ArithmeticFieldCodec) Q1: " << Bitset(Model::CODE_VALUE_BITS, FIRST_QTR)
298  << ", Q2: " << Bitset(Model::CODE_VALUE_BITS, HALF)
299  << ", Q3 : " << Bitset(Model::CODE_VALUE_BITS, THIRD_QTR)
300  << ", top: " << Bitset(Model::CODE_VALUE_BITS, TOP_VALUE) << std::endl;
301 
302  dlog.is(DEBUG3) && dlog << "(ArithmeticFieldCodec) low: " << Bitset(Model::CODE_VALUE_BITS, low).to_string() << std::endl;
303  dlog.is(DEBUG3) && dlog << "(ArithmeticFieldCodec) high: " << Bitset(Model::CODE_VALUE_BITS, high).to_string() << std::endl;
304 
305  if(update_model)
306  model.update_model(symbol, Model::ENCODER);
307 
308  for(;;)
309  {
310  if(high<HALF)
311  {
312  bit_plus_follow(&bits, &bits_to_follow, 0);
313  dlog.is(DEBUG3) && dlog << "(ArithmeticFieldCodec): completely in [0, 0.5): EXPAND" << std::endl;
314  }
315  else if(low>=HALF)
316  {
317  bit_plus_follow(&bits, &bits_to_follow, 1);
318  low -= HALF;
319  high -= HALF;
320  dlog.is(DEBUG3) && dlog << "(ArithmeticFieldCodec): completely in [0.5, 1): EXPAND" << std::endl;
321  }
322  else if(low>=FIRST_QTR && high < THIRD_QTR)
323  {
324  dlog.is(DEBUG3) && dlog << "(ArithmeticFieldCodec): straddle middle [0.25, 0.75): EXPAND" << std::endl;
325 
326  bits_to_follow += 1;
327  low -= FIRST_QTR;
328  high -= FIRST_QTR;
329  }
330  else break;
331 
332  low <<= 1;
333  high <<= 1;
334  high += 1;
335 
336  dlog.is(DEBUG3) && dlog << "(ArithmeticFieldCodec) low: " << Bitset(Model::CODE_VALUE_BITS, low).to_string() << std::endl;
337  dlog.is(DEBUG3) && dlog << "(ArithmeticFieldCodec) high: " << Bitset(Model::CODE_VALUE_BITS, high).to_string() << std::endl;
338 
339 
340  dlog.is(DEBUG3) && dlog << "(ArithmeticFieldCodec) current interval: [" << (double)low / TOP_VALUE << "," << (double)high / TOP_VALUE << ")" << std::endl;
341 
342  }
343 
344  // nothing more to do, we're encoding all the data and an EOF
345  if(value_index == wire_value.size())
346  break;
347  }
348 
349  // output exactly the number of bits required to unambiguously
350  // store the final range's state
351  // 0 . . . 1
352  // | | -- output nothing, unless we have follow bits
353  // | | -- output a single 0
354  if(low == 0) // high must be greater than half
355  {
356  if(high != TOP_VALUE || bits_to_follow > 0)
357  bit_plus_follow(&bits, &bits_to_follow, 0);
358  }
359  // 0 . . . 1
360  // | | -- output a single 1
361  else if(high == TOP_VALUE) // 0 < low < half
362  {
363  bit_plus_follow(&bits, &bits_to_follow, 1);
364  }
365  // 0 . . . 1
366  // | | -- output 01
367  // | | -- output 10
368  else
369  {
370  bits_to_follow += 1;
371  bit_plus_follow(&bits, &bits_to_follow, (low < FIRST_QTR) ? 0 : 1);
372  }
373 
374  if(FieldCodecBase::dccl_field_options().GetExtension(arithmetic).debug_assert())
375  {
376  // bit of a hack so I can get at the exact bit field sizes
377  Model::last_bits_map[FieldCodecBase::this_descriptor()->full_name()][FieldCodecBase::this_field()->name()] = bits;
378  }
379 
380 
381  return bits;
382  }
383 
384 
385  void bit_plus_follow(Bitset* bits, int* bits_to_follow, bool bit)
386  {
387  bits->push_back(bit);
388  dccl::dlog.is(dccl::logger::DEBUG3) && dccl::dlog << "(ArithmeticFieldCodec): emitted bit: " << bit << std::endl;
389 
390  while(*bits_to_follow)
391  {
392  dccl::dlog.is(dccl::logger::DEBUG3) && dccl::dlog << "(ArithmeticFieldCodec): emitted bit (from follow): " << !bit << std::endl;
393 
394  bits->push_back(!bit);
395  (*bits_to_follow) -= 1;
396  }
397  }
398 
399  std::vector<Model::value_type> decode_repeated(Bitset* bits)
400  {
401  using dccl::dlog;
402  using namespace dccl::logger;
403 
404  std::vector<Model::value_type> values;
405 
406  Model& model = current_model();
407 
408  uint64 value = 0;
409  uint64 low = 0;
410  uint64 high = TOP_VALUE;
411 
412  // offset from `bits` to currently examined `value`
413  // there are `bit_stream_offset` zeros in the lower bits of `value`
414  int bit_stream_offset = Model::CODE_VALUE_BITS - bits->size();
415 
416  for(int i = 0, n = Model::CODE_VALUE_BITS; i < n; ++i)
417  {
418  if(i >= bit_stream_offset)
419  value |= (static_cast<uint64>((*bits)[bits->size()-(i-bit_stream_offset)-1]) << i);
420  }
421 
422  dlog.is(DEBUG3) && dlog << "(ArithmeticFieldCodec): starting value: " << Bitset(Model::CODE_VALUE_BITS, value).to_string() << std::endl;
423 
424 
425 
426  for(unsigned value_index = 0, n = max_repeat(); value_index < n; ++value_index)
427  {
428  uint64 range = (high-low)+1;
429 
430  Model::symbol_type symbol = bits_to_symbol(bits, value, bit_stream_offset, low, range);
431 
432  dlog.is(DEBUG3) && dlog << "(ArithmeticFieldCodec) symbol is: " << symbol << std::endl;
433 
434 
435  std::pair<Model::freq_type, Model::freq_type> c_freq_range =
436  model.symbol_to_cumulative_freq(symbol, Model::DECODER);
437 
438  dlog.is(DEBUG3) && dlog << "(ArithmeticFieldCodec) input symbol (" << symbol << ") cumulative freq: ["<< c_freq_range.first << "," << c_freq_range.second << ")" << std::endl;
439 
440  high = low + (range*c_freq_range.second)/model.total_freq(Model::DECODER)-1;
441  low += (range*c_freq_range.first)/model.total_freq(Model::DECODER);
442 
443  model.update_model(symbol, Model::DECODER);
444 
445  if(symbol == Model::EOF_SYMBOL)
446  break;
447 
448  values.push_back(model.symbol_to_value(symbol));
449 
450  dlog.is(DEBUG3) && dlog << "(ArithmeticFieldCodec) value is: " << values.back() << std::endl;
451 
452 
453  for(;;)
454  {
455  if(high < HALF)
456  {
457  // nothing
458  }
459  else if(low >= HALF)
460  {
461  value -= HALF;
462  low -= HALF;
463  high -= HALF;
464  }
465  else if(low >= FIRST_QTR
466  && high < THIRD_QTR)
467  {
468  value -= FIRST_QTR;
469  low -= FIRST_QTR;
470  high -= FIRST_QTR;
471  }
472  else break;
473 
474  low <<= 1;
475  high <<= 1;
476  high += 1;
477  value <<= 1;
478  bit_stream_offset +=1;
479  }
480 
481  }
482 
483  // for debugging / testing
484  if(FieldCodecBase::dccl_field_options().GetExtension(arithmetic).debug_assert())
485  {
486  // must consume same bits as encoded makes
487  Bitset in = Model::last_bits_map[FieldCodecBase::this_descriptor()->full_name()][FieldCodecBase::this_field()->name()];
488 
489  dlog.is(DEBUG3) && dlog << "(ArithmeticFieldCodec) bits used is (" << bits->size() << "): " << *bits << std::endl;
490  dlog.is(DEBUG3) && dlog << "(ArithmeticFieldCodec) bits original is (" << in.size() << "): " << in << std::endl;
491 
492  assert(in == *bits);
493  }
494 
495  return values;
496 
497  }
498 
499 
500  unsigned size_repeated(const std::vector<Model::value_type>& wire_values)
501  {
502  // we should really cache this for efficiency
503  return encode_repeated(wire_values, false).size();
504  }
505 
506 
507  // this maximum size will be upper bounded by: ceil(log_2(1/P)) + 1 where P is the
508  // probability of this least probable set of symbols
509  unsigned max_size_repeated()
510  {
511  using dccl::log2;
512 
513  Model& model = current_model();
514 
515  // if user doesn't provide out_of_range frequency, set it to max to force this
516  // calculation to return the lowest probability symbol in use
517  Model::freq_type out_of_range_freq = model.user_model().out_of_range_frequency();
518  if(out_of_range_freq == 0)
519  out_of_range_freq = Model::MAX_FREQUENCY;
520 
521  Model::value_type lowest_frequency = std::min(out_of_range_freq,
522  *std::min_element(model.user_model().frequency().begin(), model.user_model().frequency().end()));
523 
524  // full of least probable symbols
525  unsigned size_least_probable = (unsigned)(std::ceil(max_repeat()*(log2(model.total_freq(Model::ENCODER))-log2(lowest_frequency))));
526 
527  dccl::dlog.is(dccl::logger::DEBUG3) && dccl::dlog << "(ArithmeticFieldCodec) size_least_probable: " << size_least_probable << std::endl;
528 
529 
530  Model::freq_type eof_freq = model.user_model().eof_frequency();
531  // almost full of least probable symbols plus EOF
532  unsigned size_least_probable_plus_eof = (unsigned)((eof_freq != 0 ) ? std::ceil(max_repeat()*log2(model.total_freq(Model::ENCODER))-(max_repeat()-1)*log2(lowest_frequency)-log2(eof_freq)) : 0);
533 
534  dccl::dlog.is(dccl::logger::DEBUG3) && dccl::dlog << "(ArithmeticFieldCodec) size_least_probable_plus_eof: " << size_least_probable_plus_eof << std::endl;
535 
536  return std::max(size_least_probable_plus_eof, size_least_probable) + 1;
537  }
538 
539 
540 
541  unsigned min_size_repeated()
542  {
543  using dccl::log2;
544  const Model& model = current_model();
545 
546  if(model.user_model().is_adaptive())
547  return 0; // force examining bits from the beginning on decode
548 
549  // if user doesn't provide out_of_range frequency, set it to 1 (minimum) to force this
550  // calculation to return the highest probability symbol in use
551  Model::freq_type out_of_range_freq = model.user_model().out_of_range_frequency();
552  if(out_of_range_freq == 0)
553  out_of_range_freq = 1;
554 
555  Model::freq_type eof_freq = model.user_model().eof_frequency();
556  // just EOF
557  unsigned size_empty = (unsigned)((eof_freq != 0) ? std::ceil(log2(model.total_freq(Model::ENCODER))-log2(eof_freq)) : std::numeric_limits<unsigned>::max());
558 
559  dccl::dlog.is(dccl::logger::DEBUG3) && dccl::dlog << "(ArithmeticFieldCodec) size_empty: " << size_empty << std::endl;
560 
561  // full with most probable symbol
562  Model::value_type highest_frequency = std::max(out_of_range_freq,
563  *std::max_element(model.user_model().frequency().begin(), model.user_model().frequency().end()));
564 
565  unsigned size_most_probable = (unsigned)(std::ceil(max_repeat()*(log2(model.total_freq(Model::ENCODER))-log2(highest_frequency))));
566 
567  dccl::dlog.is(dccl::logger::DEBUG3) && dccl::dlog << "(ArithmeticFieldCodec) size_most_probable: " << size_most_probable << std::endl;
568 
569  return std::min(size_empty, size_most_probable);
570  }
571 
572  void validate()
573  {
575  "missing (dccl.field).arithmetic");
576 
577  std::string model_name = FieldCodecBase::dccl_field_options().GetExtension(arithmetic).model();
578  try
579  {
580  ModelManager::find(model_name);
581  }
582  catch(Exception& e)
583  {
584  FieldCodecBase::require(false, "no such (dccl.field).arithmetic.model called \"" + model_name + "\" loaded.");
585  }
586  }
587 
588 
589  // end inherited methods
590 
591  Model::symbol_type bits_to_symbol(Bitset* bits,
592  uint64& value,
593  int& bit_stream_offset,
594  uint64 low,
595  uint64 range)
596  {
597  Model& model = current_model();
598 
599  for(;;)
600  {
601  uint64 value_high = (bit_stream_offset > 0) ?
602  value + ((static_cast<uint64>(1) << bit_stream_offset) - 1):
603  value;
604 
605 
606  dccl::dlog.is(dccl::logger::DEBUG3) && dccl::dlog << "(ArithmeticFieldCodec): value range: [" << Bitset(Model::CODE_VALUE_BITS, value) << "," << Bitset(Model::CODE_VALUE_BITS, value_high) << ")" << std::endl;
607 
608 
609  Model::freq_type cumulative_freq = ((value-low+1)*model.total_freq(Model::DECODER)-1)/range;
610  Model::freq_type cumulative_freq_high = ((value_high-low+1)*model.total_freq(Model::DECODER)-1)/range;
611 
612  dccl::dlog.is(dccl::logger::DEBUG3) && dccl::dlog << "(ArithmeticFieldCodec): c_freq: " << cumulative_freq << ", c_freq_high: " << cumulative_freq_high << std::endl;
613 
614 
615  std::pair<Model::symbol_type, Model::symbol_type> symbol_pair = model.cumulative_freq_to_symbol(std::make_pair(cumulative_freq, cumulative_freq_high), Model::DECODER);
616 
617  dccl::dlog.is(dccl::logger::DEBUG3) && dccl::dlog << "(ArithmeticFieldCodec): symbol: " << symbol_pair.first << ", " << symbol_pair.second << std::endl;
618 
619 
620  if(symbol_pair.first == symbol_pair.second)
621  return symbol_pair.first;
622 
623  // add another bit to disambiguate
624  bits->get_more_bits(1);
625 
626  dccl::dlog.is(dccl::logger::DEBUG3) && dccl::dlog << "(ArithmeticFieldCodec): bits: " << *bits << std::endl;
627 
628  --bit_stream_offset;
629  value |= static_cast<uint64>(bits->back()) << bit_stream_offset;
630 
631  dccl::dlog.is(dccl::logger::DEBUG3) && dccl::dlog << "(ArithmeticFieldCodec): ambiguous (symbol could be " << symbol_pair.first << " or " << symbol_pair.second << ")" << std::endl;
632 
633  }
634 
635 
636 
637 
638  return 0;
639  }
640 
641 
642  dccl::int32 max_repeat()
643  {
644  return FieldCodecBase::this_field()->is_repeated() ? FieldCodecBase::dccl_field_options().max_repeat() : 1;
645  }
646 
647  Model& current_model()
648  {
649  std::string name = FieldCodecBase::dccl_field_options().GetExtension(arithmetic).model();
650  return ModelManager::find(name);
651  }
652 
653 
654 
655 
656  };
657 
658  // constant integer definitions
659  template<typename FieldType> const uint64 ArithmeticFieldCodecBase<FieldType>::TOP_VALUE;
660  template<typename FieldType> const uint64 ArithmeticFieldCodecBase<FieldType>::FIRST_QTR;
661  template<typename FieldType> const uint64 ArithmeticFieldCodecBase<FieldType>::HALF;
662  template<typename FieldType> const uint64 ArithmeticFieldCodecBase<FieldType>::THIRD_QTR;
663 
664  template<typename FieldType>
666  {
667  Model::value_type pre_encode(const FieldType& field_value)
668  { return static_cast<Model::value_type>(field_value); }
669 
670  FieldType post_decode(const Model::value_type& wire_value)
671  { return static_cast<FieldType>(wire_value); }
672  };
673 
674 
675  template <>
676  class ArithmeticFieldCodec<const google::protobuf::EnumValueDescriptor*> : public ArithmeticFieldCodecBase<const google::protobuf::EnumValueDescriptor*>
677  {
678  public:
679  Model::value_type pre_encode(const google::protobuf::EnumValueDescriptor* const& field_value)
680  { return field_value->number(); }
681 
682  const google::protobuf::EnumValueDescriptor* post_decode(const Model::value_type& wire_value)
683  {
684  const google::protobuf::EnumDescriptor* e = FieldCodecBase::this_field()->enum_type();
685  const google::protobuf::EnumValueDescriptor* return_value = e->FindValueByNumber((int)wire_value);
686 
687  if(return_value)
688  return return_value;
689  else
690  throw NullValueException();
691  }
692 
693  };
694  }
695 }
696 
697 #endif
The Dynamic CCL enCODer/DECoder. This is the main class you will use to load, encode and decode DCCL ...
Definition: codec.h:56
dccl::DCCLFieldOptions dccl_field_options() const
Get the DCCL field option extension value for the current field.
Definition: field_codec.h:321
Exception used to signal null (non-existent) value within field codecs during decode.
Definition: exception.h:40
std::string to_string() const
Returns the value of the Bitset as a printable string, where each bit is represented by &#39;1&#39; or &#39;0&#39;...
Definition: bitset.h:290
const google::protobuf::FieldDescriptor * this_field() const
Returns the FieldDescriptor (field schema meta-data) for this field.
Definition: field_codec.h:75
void require(bool b, const std::string &description)
Essentially an assertion to be used in the validate() virtual method.
Definition: field_codec.h:335
std::vector< Model::value_type > decode_repeated(Bitset *bits)
Decode a repeated field.
unsigned max_size_repeated()
Give the max size of a repeated field.
Base class for "repeated" (multiple value) static-typed (no boost::any) field encoders/decoders. Use TypedFixedFieldCodec if your codec is fixed length (always uses the same number of bits on the wire). Use TypedFieldCodec if your fields are always singular ("optional" or "required"). Singular fields are default implemented in this codec by calls to the equivalent repeated function with an empty or single valued vector.
Model::value_type pre_encode(const google::protobuf::EnumValueDescriptor *const &field_value)
Convert from the FieldType representation (used in the Google Protobuf message) to the WireType repre...
google::protobuf::uint32 uint32
an unsigned 32 bit integer
Definition: common.h:55
google::protobuf::uint64 uint64
an unsigned 64 bit integer
Definition: common.h:59
unsigned min_size_repeated()
Give the min size of a repeated field.
void get_more_bits(size_type num_bits)
Retrieve more bits from the parent Bitset.
Definition: bitset.h:447
static const google::protobuf::Descriptor * this_descriptor()
Returns the Descriptor (message schema meta-data) for the immediate parent Message.
Definition: field_codec.h:91
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
void validate()
Validate a field. Use require() inside your overloaded validate() to assert requirements or throw Exc...
google::protobuf::int32 int32
a signed 32 bit integer
Definition: common.h:57
A variable size container of bits (subclassed from std::deque<bool>) with an optional hierarchy...
Definition: bitset.h:38