C++ Generierung binärer Kodewörter variabler Länge

#ifndef BINARYCODE_H
#define BINARYCODE_H

#include <math.h>
#include <stdexcept>

#include "boost/dynamic_bitset.hpp"
#include "boost/unordered_map.hpp"

class BinaryCode {

/***************************************************************************/
public:

//---------------------------------------------------------------------------
//  Public class methods
//---------------------------------------------------------------------------

  // Erzeugt den Binaer-Code zu der uebergebenen Zahl in lesbarer Form mit einer
  // festen Anzahl von <amountOfBits> Bits.
  static std::string const fixBinCode(const uint32_t number, const uint8_t amountOfBits);

  // Dekodiert ein binaeres Kodewort in eine Zahl.
  static uint32_t binDecode(const std::string & codeword);

  // Errechnet die Laenge der Binaerkodierung einer Zahl in Bit.
  static uint8_t binCodeLength(const uint32_t number);

/***************************************************************************/
private:

//---------------------------------------------------------------------------
//  Private class methods
//---------------------------------------------------------------------------

  // Berechnet einen neuen Binaerkode zu einer Ganzzahl.
  inline static std::string calcNewBinCode(const uint32_t number, const uint8_t amountOfBits);

  // Errechnet die Laenge der Binaerkodierung einer Zahl in Bit.
  inline static uint8_t calcNewBinCodeLength(const uint32_t number);

//---------------------------------------------------------------------------
//  Private class variables
//---------------------------------------------------------------------------

  // Zur Optimierung der Kodeberechnung wird eine lookup-Tabelle genutzt.
  static boost::unordered_map<const std::pair<const uint32_t, const uint8_t>,
    const std::string> binCodeLookupTable;

  static boost::unordered_map<const std::pair<const uint32_t, const uint8_t>,
    const std::string>::const_iterator binCodeLUTIterator;

  // Zur Optimierung der Kodelaengenberechnung wird eine lookup-Tabelle genutzt.
  static boost::unordered_map<const uint32_t, const uint8_t> binCodeLengthLookupTable;

  static boost::unordered_map<const uint32_t, const uint8_t>::const_iterator binCodeLengthLUTIterator;
};

/** @class BinaryCode
 *
 * Die Klasse dient als Utility-Klasse und enthaelt ausschliesslich statische
 * Methoden, die im Zusammenhang mit der Binaer-Kodierung und -Dekodierung
 * von Ganzzahlen stehen.
 *
 * Sie erlaubt sowohl die Ermittlung der Laenge einer solchen Darstellung als
 * auch die Generierung und Dekodierung binaerer Kodewoerter.
 **/

//---------------------------------------------------------------------------
//  Includes
//---------------------------------------------------------------------------

#include "BinaryCode.h"

boost::unordered_map<const std::pair<const uint32_t, const uint8_t>, const std::string>
  BinaryCode::binCodeLookupTable;
boost::unordered_map<const std::pair<const uint32_t, const uint8_t>, const std::string>::const_iterator
  BinaryCode::binCodeLUTIterator;

boost::unordered_map<const uint32_t, const uint8_t> BinaryCode::binCodeLengthLookupTable;
boost::unordered_map<const uint32_t, const uint8_t>::const_iterator BinaryCode::binCodeLengthLUTIterator;

/***************************************************************************\
                           Public Class Methods
\***************************************************************************/

/**
 * @brief Kodewortgenerierung
 *
 * @param number Zu kodierende Ganzzahl (>= 0).
 * @param amountOfBits Anzahl der Bits, die das Kodewort haben soll. Die Anzahl muss
 * mindestens so gross sein, dass die zu kodierende Zahl darstellbar ist.
 *
 * @throw invalid_argument Wird ausgeloest, wenn nicht ausreichend Bits fuer die
 * Kodierung der Zahl angegeben wurden.
 *
 * Erzeugt den Binaer-Kode zu der uebergebenen Zahl mit einer festen Anzahl von Bits. Der
 * Kode wird als Folge von "0"- und "1"-Symbolen repraesentiert.
 *
 * z.B. fixBinCode(35,10) = 0000100011
**/
std::string const BinaryCode::fixBinCode(const uint32_t number, const uint8_t amountOfBits) {
  const uint32_t neededBits = BinaryCode::binCodeLength(number);

  if (neededBits > amountOfBits) {
    throw std::invalid_argument("# BinaryCode::fixBinCode - Zu wenig Bits zur Darstellung gefordert.");
  }

  std::string result;
  const std::pair<const uint32_t, const uint8_t> numberToCode(number, amountOfBits);
  binCodeLUTIterator = BinaryCode::binCodeLookupTable.find(numberToCode);

  if (binCodeLUTIterator == BinaryCode::binCodeLookupTable.end()) {
    result = BinaryCode::calcNewBinCode(number, amountOfBits);
    BinaryCode::binCodeLookupTable.insert(std::make_pair(numberToCode, result));
  } else {
    result = binCodeLUTIterator->second;
  }

  return result;
}

/**
 * @brief Kodewortdekodierung
 *
 * @param codeword Eine Zeichenkette, in dem die binaere Darstellung einer
 * Zahl als Folge von "0"-en und "1"-en gespeichert ist. Wird eine leere Zeichen-
 * kette uebergeben, gibt die Funktion 0 zurueck.
 *
 * @throw invalid_argument Auch wenn leere Kodewoerter zu 0 dekodiert werden koennten, besitzt die
 * 0 eine eigene Repraesentation, damit stellt das leere Kodewort hier einen Fehler dar.
 *
 * Dekodiert ein binaeres Kodewort in eine Ganzzahl.
**/
uint32_t BinaryCode::binDecode(const std::string & codeword) {
  if (codeword.empty()) {
    throw std::invalid_argument("# BinaryCode::binDecode - Kodewort der Laenge 0 kann nicht dekodiert werden.");
  }

  const boost::dynamic_bitset<> bitRepresentation(codeword);
  return bitRepresentation.to_ulong();
}

/**
 * @brief Kodewortlaengen
 *
 * @param number Eine positive Ganzzahl >= 0, die binaer kodiert werden soll.
 *
 * Berechnet die Laenge der binaeren Kodierung einer Zahl in Bit. Als Ergebnis wird nur die
 * minimale Anzahl an Bits geliefert, die zur Repraesentation noetig sind. Bei einer festen Anzahl
 * von Bits zur Kodierung koennen auch fuehrende Nullen zum Auffuellen des Kodeworts ergaenzt werden.
 **/
uint8_t BinaryCode::binCodeLength(const uint32_t number) {
  uint8_t result;

  binCodeLengthLUTIterator = BinaryCode::binCodeLengthLookupTable.find(number);

  // pruefe, ob die Laenge berechnet wurde; wenn nicht, berechne neu
  if (binCodeLengthLUTIterator == BinaryCode::binCodeLengthLookupTable.end()) {
    result = BinaryCode::calcNewBinCodeLength(number);
    BinaryCode::binCodeLengthLookupTable.insert(std::make_pair(number, result));
  } else {
    result = binCodeLengthLUTIterator->second;
  }

  return result;
}

/***************************************************************************\
                           Private Class Methods
\***************************************************************************/

// Berechnet eine neue binaere Repraesentation einer Ganzzahl.
inline std::string BinaryCode::calcNewBinCode(const uint32_t number, const uint8_t amountOfBits) {
  std::string result;

  const boost::dynamic_bitset<> bitRepresentation(amountOfBits, number);
  boost::to_string(bitRepresentation, result);

  return result;
}

// Errechnet die Laenge der Binaerkodierung einer Zahl in Bit.
inline uint8_t BinaryCode::calcNewBinCodeLength(const uint32_t number) {
  uint8_t result;

  if (number <= 1) {
    result = 1;
  } else {
    const double log2Number = log2(number);
    const uint8_t lowNumber = floor(log2Number);
    if (fmod(number, pow(2, lowNumber)) == 0) {
      result = (ceil(log2Number) +1);
    } else {
      result = ceil(log2Number);
    }
  }

  return result;
}