Bitset.cpp

/*
 * This file is part of ALVAR, A Library for Virtual and Augmented Reality.
 *
 * Copyright 2007-2012 VTT Technical Research Centre of Finland
 *
 * Contact: VTT Augmented Reality Team <alvar.info@vtt.fi>
 *          <http://www.vtt.fi/multimedia/alvar.html>
 *
 * ALVAR is free software; you can redistribute it and/or modify it under the
 * terms of the GNU Lesser General Public License as published by the Free
 * Software Foundation; either version 2.1 of the License, or (at your option)
 * any later version.
 *
 * This library is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License
 * for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with ALVAR; if not, see
 * <http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html>.
 */

/*****************************************************************************
 ******************************  I N C L U D E  ******************************
 ****************************************************************************/

#include "Bitset.h"

using namespace std;

namespace alvar {

using namespace std;

/*****************************************************************************
 ***  class Bitset
 ****************************************************************************/

int Bitset::Length() const
   {
   return (bits.size());
   }

ostream& Bitset::Output(ostream& os) const
   {
   deque<bool>::const_iterator iter = bits.begin();
   while (iter != bits.end())
      {
      if (*iter)
         os << "1";
      else
         os << "0";
      iter++;
      }

   return (os);

   }

void Bitset::clear()
   {
   bits.clear();

   return;

   }

void Bitset::push_back(const bool bit)
   {
   bits.push_back(bit);

   return;

   }

void Bitset::push_back(const unsigned char b, int bit_count /*=8*/)
   {
   push_back((const unsigned long)b, bit_count);

   return;

   }

void Bitset::push_back(const unsigned short s, int bit_count /*=16*/)
   {
   push_back((const unsigned long) s, bit_count);

   return;

   }

void Bitset::push_back(const unsigned long l, int bit_count /*=32*/)
   {
   unsigned long mask;
   if ((bit_count > 32) || (bit_count == 0))
      bit_count=32;

   mask = 0x01 << (bit_count - 1);
   for (int i = 0 ; i < bit_count ; i++)
      {
      if (l & mask)
         push_back(true);
      else
         push_back(false);

      mask >>= 1;
      }

   return;

   }

void Bitset::push_back_meaningful(const unsigned long l)
   {
   int bit_count = 1;
   for (int i = 0 ; i < 32 ; i++)
      {
      unsigned long mask = 0x01 << i;
      if (l & mask)
         bit_count = i + 1;
      }

   push_back(l, bit_count);

   return;

   }

void Bitset::fill_zeros_left(size_t bit_count)
   {
   while (bits.size() < bit_count)
      {
      bits.push_front(false);
      }

   return;

   }

void Bitset::push_back(string s)
   {
   string::const_iterator iter = s.begin();
   while (iter != s.end())
      {
      unsigned char c = *iter;
      push_back(c);
      iter++;
      }

   return;

   }

bool Bitset::pop_front()
   {
   bool ret = bits.front();
   bits.pop_front();

   return (ret);

   }

bool Bitset::pop_back()
   {
	bool ret = bits.back();
	bits.pop_back();	

   return (ret);

   }

void Bitset::flip(size_t pos)
   {
	bits[pos] = !bits[pos];

   return;

   }

string Bitset::hex() const
   {
   stringstream ss;
   ss.unsetf(std::ios_base::dec);
   ss.setf(std::ios_base::hex);
   unsigned long b = 0;
   int bitpos = (0x08 << (bits.size() % 4));
   if (bitpos > 0x08)
      bitpos >>= 4;

   for (size_t i = 0 ; i < bits.size() ; i++)
      {
      if (bits[i])
         b = b | bitpos;
      else
         b = b & (0x0f ^ bitpos);

      bitpos >>= 1;
      if (bitpos == 0x00)
         {
         bitpos = 0x08;
         ss << b;
         }
      }

   return (ss.str());

   }

unsigned long Bitset::ulong() const
   {
   //if(bits.size() > (sizeof(unsigned long)*8))
   //	throw "code too big for unsigned long\n";
   stringstream ss;
   ss << setbase(16) << hex();
   unsigned long v;
   ss >> v;

   return (v);

   }

unsigned char Bitset::uchar() const
   {
   //if(bits.size() > (sizeof(unsigned char)*8))
   //	throw "code too big for unsigned char\n";
   stringstream ss;
   ss << setbase(16) << hex();
   unsigned long v; //ttehop: Note, that this cannot be char
   ss >> v;

   return ((unsigned char) v);

   }

/*****************************************************************************
 ***  class BitsetExt
 ****************************************************************************/

void BitsetExt::hamming_enc_block(unsigned long block_len, deque<bool>::iterator& iter)
   {
   if (verbose)
      cout << "hamming_enc_block: ";

   unsigned long next_parity = 1;
   for (unsigned long i = 1 ; i <= block_len ; i++)
      {
      // Add a parity bit if this a place for such
      if (i == next_parity)
         {
         if (verbose)
            cout << "p";
         next_parity <<= 1;
         iter = bits.insert(iter, false);
         }
      else
         {
         // Otherwise if this bit is 1 change all related parity bits
         if (iter == bits.end())
            {
            block_len = i - 1;
            break;
            }

         if (verbose)
            cout << (*iter?1 : 0);

         if (*iter)
            {
            unsigned long parity = next_parity >> 1;
            while (parity)
               {
               if (i & parity)
                  {
                  deque<bool>::iterator parity_iter = (iter - (i - parity));
                  *parity_iter = !*parity_iter;
                  }
               parity >>= 1;
               }
            }
         }
      iter++;
      }

   // Update the last parity bit if we have one
   // Note, that the last parity bit can safely be removed from the code if it is not desired...
   if (block_len == (next_parity >> 1))
      {
      // If the last bit is parity bit - make parity over the previous data
      for (unsigned long ii = 1 ; ii < block_len ; ii++)
         {
         if (*(iter-ii-1)) *(iter-1) = !*(iter-1);
         }
      }

   if (verbose)
      {
      cout << " -> ";
      for (unsigned long ii = block_len ; ii >= 1 ; ii--)
         {
         cout << (*(iter-ii) ? 1 : 0);
         }
      cout << " block_len: " << block_len << endl;
      }

   return;

   }

int BitsetExt::hamming_dec_block(unsigned long block_len, deque<bool>::iterator &iter)
   {
   if (verbose)
      cout << "hamming_dec_block: ";

   bool potentially_double_error = false;
   unsigned long total_parity = 0;
   unsigned long parity = 0;
   unsigned long next_parity = 1;
   for (unsigned long i = 1 ; i <= block_len ; i++)
      {
      if (iter == bits.end())
         {
         // ttehop:
         // At 3.12.2009 I changed the following line because
         // it crashed with 7x7 markers. However, I didn't fully
         // understand the reason why it should be so. Lets
         // give more thought to it when we have more time.
         // old version: block_len = i-1;
         block_len = i;
         break;
         }

      if (*iter)
         {
         parity = parity ^ i;
         total_parity = total_parity ^ 1;
         }

      if (i == next_parity)
         {
         if (verbose)
            cout << "(" << *iter << ")";
         next_parity <<= 1;
         iter = bits.erase(iter);
         }
      else
         {
         if (verbose)
            cout << *iter;
         iter++;
         }
      }

   if (block_len < 3)
      {
      if (verbose)
         cout << " too short" << endl;

      return (0);
      }

   if (block_len == (next_parity >> 1))
      {
      parity = parity & ~(next_parity >> 1); // The last parity bit shouldn't be included in the other parity tests (TODO: Better solution)
      if (total_parity == 0)
         {
         potentially_double_error = true;
         }
      }

   int steps = 0;
   if (verbose)
      cout << " parity: " << parity;

   if (parity)
      {
      if (potentially_double_error)
         {
         if (verbose)
            cout << " double error" << endl;

         return (-1);
         }

      next_parity = 1;
      for (unsigned long i = 1 ; i <= block_len ; i++)
         {
         if (i == next_parity)
            {
            next_parity <<= 1;
            if (i == parity)
               {
               if (verbose)
                  cout << " parity bit error" << endl;

               return (1); // Only parity bit was erroneous
               }
            }
         else if (i >= parity)
            {
            steps++;
            }
         }

      iter[-steps] = !iter[-steps];
      if (verbose)
         cout << " corrected" << endl;

      return (1);
      }

   if (verbose)
      cout << " ok" << endl;

   return (0);

   }

/*
void BitsetExt::str_8to6bit() {
	// TODO: Assume that the bitset contains 8-bit ASCII chars and change them into 6-bit chars
}
void BitsetExt::str_6to8bit() {
	// TODO: Assume that the bitset contains 6-bit chars and change them into 8-bit ASCII chars
}
void BitsetExt::crc_enc(int crc_len) {
	// TODO: Add crc_len-bit checksum for the bitset
}
bool BitsetExt::crc_dec(int crc_len) {
	// TODO: Check the CRC
	return false;
}
*/

int BitsetExt::count_hamming_enc_len(int block_len, int dec_len)
   {
   int parity_len = 0;
   int dec_len_count = dec_len;
   while (dec_len_count > 0)
      {
      unsigned long next_parity = 1;
      for (unsigned long i = 1 ; i <= (unsigned long) block_len ; i++)
         {
         if (i == next_parity)
            {
            parity_len++;
            next_parity <<= 1;
            }
         else
            {
            dec_len_count--;
            }

         if (dec_len_count == 0)
            break;
         }
      }

   return (dec_len + parity_len);

   }

int BitsetExt::count_hamming_dec_len(int block_len, int enc_len)
   {
   int parity_len = 0;
   int enc_len_count = enc_len;
   while (enc_len_count > 0)
      {
      unsigned long next_parity = 1;

      for (unsigned long i = 1 ; i <= (unsigned long) block_len ; i++)
         {
         if (i == next_parity)
            {
            parity_len++;
            next_parity <<= 1;
            }

         enc_len_count--;
         if (enc_len_count == 0)
            {
            break;
            } // end if
         }
      }

   return (enc_len - parity_len);

   }

void BitsetExt::hamming_enc(int block_len)
   {
   deque<bool>::iterator iter = bits.begin();
   while (iter != bits.end())
      {
      hamming_enc_block(block_len, iter);
      }

   return;

   }

// Returns number of corrected errors (or -1 if there were unrecoverable error)
int BitsetExt::hamming_dec(int block_len)
   {
   int error_count = 0;
   deque<bool>::iterator iter = bits.begin();
   while (iter != bits.end())
      {
      int error = hamming_dec_block(block_len, iter);
      if (error == -1)
         error_count = -1;
      else
         error_count += error;
      }

   return (error_count);

   }

} // namespace alvar