Bitset.cpp
Go to the documentation of this file.
00001 /*
00002  * This file is part of ALVAR, A Library for Virtual and Augmented Reality.
00003  *
00004  * Copyright 2007-2012 VTT Technical Research Centre of Finland
00005  *
00006  * Contact: VTT Augmented Reality Team <alvar.info@vtt.fi>
00007  *          <http://www.vtt.fi/multimedia/alvar.html>
00008  *
00009  * ALVAR is free software; you can redistribute it and/or modify it under the
00010  * terms of the GNU Lesser General Public License as published by the Free
00011  * Software Foundation; either version 2.1 of the License, or (at your option)
00012  * any later version.
00013  *
00014  * This library is distributed in the hope that it will be useful, but WITHOUT
00015  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
00016  * FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License
00017  * for more details.
00018  *
00019  * You should have received a copy of the GNU Lesser General Public License
00020  * along with ALVAR; if not, see
00021  * <http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html>.
00022  */
00023 
00024 #include "Bitset.h"
00025 
00026 using namespace std;
00027 
00028 namespace alvar {
00029 using namespace std;
00030 
00031 int Bitset::Length() {
00032         return bits.size();
00033 }
00034 ostream &Bitset::Output(ostream &os) const {
00035         deque<bool>::const_iterator iter=bits.begin();
00036         while (iter != bits.end()) {
00037                 if (*iter) os<<"1";
00038                 else os<<"0";
00039                 iter++;
00040         }
00041         return os;
00042 }
00043 void Bitset::clear() { bits.clear(); }
00044 void Bitset::push_back(const bool bit) { bits.push_back(bit); }
00045 void Bitset::push_back(const unsigned char b, int bit_count /*=8*/) {
00046         push_back((const unsigned long)b, bit_count);
00047 }
00048 void Bitset::push_back(const unsigned short s, int bit_count /*=16*/) {
00049         push_back((const unsigned long)s, bit_count);
00050 }
00051 void Bitset::push_back(const unsigned long l, int bit_count /*=32*/) {
00052         unsigned long mask;
00053         if ((bit_count > 32) || (bit_count == 0)) bit_count=32;
00054         mask = 0x01<<(bit_count-1);
00055         for (int i=0; i<bit_count; i++) {
00056                 if (l & mask) push_back(true);
00057                 else push_back(false);
00058                 mask>>=1;
00059         }
00060 }
00061 void Bitset::push_back_meaningful(const unsigned long l) {
00062         int bit_count = 1;
00063         for (int i=0; i<32; i++) {
00064                 unsigned long mask = 0x01<<i;
00065                 if (l & mask) bit_count = i+1;
00066         }
00067         push_back(l, bit_count);
00068 }
00069 void Bitset::fill_zeros_left(size_t bit_count) {
00070         while (bits.size() < bit_count) {
00071                 bits.push_front(false);
00072         }
00073 }
00074 
00075 void Bitset::push_back(string s) {
00076         string::const_iterator iter = s.begin();
00077         while (iter != s.end()) {
00078                 unsigned char c = *iter;
00079                 push_back(c);
00080                 iter++;
00081         }
00082 }
00083 bool Bitset::pop_front()
00084 {
00085         bool ret = bits.front();
00086         bits.pop_front();       
00087         return ret;
00088 }
00089 bool Bitset::pop_back()
00090 {
00091         bool ret = bits.back();
00092         bits.pop_back();        
00093         return ret;
00094 }
00095 
00096 void Bitset::flip(size_t pos) {
00097         bits[pos] = !bits[pos];
00098 }
00099 
00100 string Bitset::hex() 
00101 {
00102         stringstream ss;
00103         ss.unsetf(std::ios_base::dec);
00104         ss.setf(std::ios_base::hex);
00105         unsigned long b=0;
00106         int bitpos = (0x08 << (bits.size() % 4));
00107         if (bitpos > 0x08) bitpos >>= 4;
00108         for (size_t i=0; i < bits.size(); i++) {
00109                 if (bits[i]) b = b | bitpos;
00110                 else b = b & (0x0f ^ bitpos);
00111                 bitpos >>= 1;
00112                 if (bitpos == 0x00) {
00113                         bitpos = 0x08;
00114                         ss << b;
00115                 }
00116         }
00117         return ss.str();
00118 }
00119 
00120 unsigned long Bitset::ulong()
00121 {
00122         //if(bits.size() > (sizeof(unsigned long)*8))
00123         //      throw "code too big for unsigned long\n";
00124         stringstream ss;
00125         ss << setbase(16) << hex();
00126         unsigned long v;
00127         ss >> v;
00128         return v;
00129 }
00130 
00131 unsigned char Bitset::uchar()
00132 {
00133         //if(bits.size() > (sizeof(unsigned char)*8))
00134         //      throw "code too big for unsigned char\n";
00135         stringstream ss;
00136         ss << setbase(16) << hex();
00137         unsigned long v; //ttehop: Note, that this cannot be char
00138         ss >> v;
00139         return (unsigned char)v;
00140 }
00141 
00142 void BitsetExt::hamming_enc_block(unsigned long block_len, deque<bool>::iterator &iter) {
00143         if (verbose) cout<<"hamming_enc_block: ";
00144         unsigned long next_parity=1;
00145         for (unsigned long i=1; i<=block_len; i++) {
00146                 // Add a parity bit if this a place for such
00147                 if (i == next_parity) {
00148                         if (verbose) cout<<"p";
00149                         next_parity <<= 1;
00150                         iter = bits.insert(iter, false);
00151                 } 
00152                 // Otherwise if this bit is 1 change all related parity bits
00153                 else {
00154                         if (iter == bits.end()) {
00155                                 block_len = i-1;
00156                                 break;
00157                         }
00158                         if (verbose) cout<<(*iter?1:0);
00159                         if (*iter) {
00160                                 unsigned long parity = next_parity>>1;
00161                                 while (parity) {
00162                                         if (i & parity) {
00163                                                 deque<bool>::iterator parity_iter=(iter - (i - parity));
00164                                                 *parity_iter = !*parity_iter;
00165                                         }
00166                                         parity >>= 1;
00167                                 }
00168                         }
00169                 }
00170                 iter++;
00171         }
00172         // Update the last parity bit if we have one
00173         // Note, that the last parity bit can safely be removed from the code if it is not desired...
00174         if (block_len == (next_parity >> 1)) {
00175                 // If the last bit is parity bit - make parity over the previous data
00176                 for (unsigned long ii=1; ii<block_len; ii++) {
00177                         if (*(iter-ii-1)) *(iter-1) = !*(iter-1);
00178                 }
00179         }
00180         if (verbose) {
00181                 cout<<" -> ";
00182                 for (unsigned long ii=block_len; ii>=1; ii--) {
00183                         cout<<(*(iter-ii)?1:0);
00184                 }
00185                 cout<<" block_len: "<<block_len<<endl;
00186         }
00187 }
00188 int BitsetExt::hamming_dec_block(unsigned long block_len, deque<bool>::iterator &iter) {
00189         if (verbose) cout<<"hamming_dec_block: ";
00190         bool potentially_double_error = false;
00191         unsigned long total_parity=0;
00192         unsigned long parity=0;
00193         unsigned long next_parity=1;
00194         for (unsigned long i=1; i<=block_len; i++) {
00195                 if (iter == bits.end()) {
00196                         // ttehop: 
00197                         // At 3.12.2009 I changed the following line because
00198                         // it crashed with 7x7 markers. However, I didn't fully
00199                         // understand the reason why it should be so. Lets
00200                         // give more thought to it when we have more time.
00201                         // old version: block_len = i-1;
00202                         block_len = i;
00203                         break;
00204                 }
00205                 if (*iter) {
00206                         parity = parity ^ i;
00207                         total_parity = total_parity ^ 1;
00208                 }
00209                 if (i == next_parity) {
00210                         if (verbose) cout<<"("<<*iter<<")";
00211                         next_parity <<= 1;
00212                         iter = bits.erase(iter);
00213                 } else {
00214                         if (verbose) cout<<*iter;
00215                         iter++;
00216                 }
00217         }
00218         if (block_len < 3)  {
00219                 if (verbose) cout<<" too short"<<endl;
00220                 return 0;
00221         }
00222         if (block_len == (next_parity >> 1)) {
00223                 parity = parity & ~(next_parity >> 1); // The last parity bit shouldn't be included in the other parity tests (TODO: Better solution)
00224                 if (total_parity == 0) {
00225                         potentially_double_error = true;
00226                 }
00227         }
00228         int steps=0;
00229         if (verbose) cout<<" parity: "<<parity;
00230         if (parity) {
00231                 if (potentially_double_error) {
00232                         if (verbose) cout<<" double error"<<endl;
00233                         return -1;
00234                 }
00235                 next_parity = 1;
00236                 for (unsigned long i=1; i<=block_len; i++) {
00237                         if (i == next_parity) {
00238                                 next_parity <<= 1;
00239                                 if (i == parity) {
00240                                         if (verbose) cout<<" parity bit error"<<endl;
00241                                         return 1; // Only parity bit was erroneous
00242                                 }
00243                         } else if (i >= parity) {
00244                                 steps++;
00245                         }
00246                 }
00247                 iter[-steps] = !iter[-steps];
00248                 if (verbose) cout<<" corrected"<<endl;
00249                 return 1;
00250         }
00251         if (verbose) cout<<" ok"<<endl;
00252         return 0;
00253 }
00254 BitsetExt::BitsetExt() {
00255         SetVerbose(false);
00256 }
00257 BitsetExt::BitsetExt(bool _verbose) {
00258         SetVerbose(_verbose);
00259 }
00260 /*
00261 void BitsetExt::str_8to6bit() {
00262         // TODO: Assume that the bitset contains 8-bit ASCII chars and change them into 6-bit chars
00263 }
00264 void BitsetExt::str_6to8bit() {
00265         // TODO: Assume that the bitset contains 6-bit chars and change them into 8-bit ASCII chars
00266 }
00267 void BitsetExt::crc_enc(int crc_len) {
00268         // TODO: Add crc_len-bit checksum for the bitset
00269 }
00270 bool BitsetExt::crc_dec(int crc_len) {
00271         // TODO: Check the CRC
00272         return false;
00273 }
00274 */
00275 void BitsetExt::SetVerbose(bool _verbose) {
00276         verbose = _verbose;
00277 }
00278 int BitsetExt::count_hamming_enc_len(int block_len, int dec_len) {
00279         int parity_len=0;
00280         int dec_len_count = dec_len;
00281         while (dec_len_count > 0) {
00282                 unsigned long next_parity = 1;
00283                 for (unsigned long i=1; i<=(unsigned long)block_len; i++) {
00284                         if (i == next_parity) {
00285                                 parity_len++;
00286                                 next_parity <<= 1;
00287                         } else {
00288                                 dec_len_count--;
00289                         }
00290                         if (dec_len_count == 0) break;
00291                 }
00292         }
00293         return dec_len + parity_len;
00294 }
00295 int BitsetExt::count_hamming_dec_len(int block_len, int enc_len) {
00296         int parity_len=0;
00297         int enc_len_count = enc_len;
00298         while (enc_len_count > 0) {
00299                 unsigned long next_parity = 1;
00300                 unsigned long i;
00301                 for (i=1; i<=(unsigned long)block_len; i++) {
00302                         if (i == next_parity) {
00303                                 parity_len++;
00304                                 next_parity <<= 1;
00305                         }
00306                         enc_len_count--;
00307                         if (enc_len_count == 0) break;
00308                 }
00309         }
00310         return enc_len - parity_len;
00311 }
00312 void BitsetExt::hamming_enc(int block_len) {
00313         deque<bool>::iterator iter=bits.begin();
00314         while (iter != bits.end()) {
00315                 hamming_enc_block(block_len, iter);
00316         }
00317 }
00318 // Returns number of corrected errors (or -1 if there were unrecoverable error)
00319 int BitsetExt::hamming_dec(int block_len) {
00320         int error_count=0;
00321         deque<bool>::iterator iter=bits.begin();
00322         while (iter != bits.end()) {
00323                 int error=hamming_dec_block(block_len, iter);
00324                 if ((error == -1) || (error_count == -1)) error_count=-1;
00325                 else error_count += error;
00326         }
00327         return error_count;
00328 }
00329 
00330 } // namespace alvar


ar_track_alvar
Author(s): Scott Niekum
autogenerated on Sat Dec 28 2013 16:46:15