/**********************************************************************
This file is part of the Quantum Computation Library (QCLIB).
(c) Copyright by Bernhard Oemer <oemer@tph.tuwien.ac.at>, 1996-1998
This program comes without any warranty; without even the implied
warranty of merchantability or fitness for any particular purpose.
This program is free software under the terms of the
GNU General Public Licence (GPL) version 2 or higher
************************************************************************/
#pragma implementation "bitvec.h"
#include "bitvec.h"
using namespace std;
DEBUG( int nbitvecs=0; )
char* qc_check_txt = "QCLIB: qc_check failed on condition ";
char* qc_check_stdmsg =
"Can't continue. Provoking segfault to simplify backtracking.\n";
char* qc_check_msg = qc_check_stdmsg;
char* qc_delete_txt = "QCLIB: qc_delete warning";
char* qc_delarray_txt = "QCLIB: qc_delarray warning";
char* qc_del_msg =
"This should not happen (out of memory?). If the warning is reproducable,\n"
"please send a bugreport to Bernhard Oemer <oemer@tph.tuwien.ac.at>.\n";
/* private members */
void bitvec::l_bitvec(word v) {
int i,l;
l=WORDS(len);
pvec=new word[l];
pvec[0]=v;
for(i=1;i<l;i++) pvec[i]=0;
}
void bitvec::l_bitvec(const bitvec& v) {
int i,l;
l=WORDS(v.len);
pvec=new word[l];
for(i=0;i<l;i++) pvec[i]=v.pvec[i];
}
void bitvec::l_append(const bitvec& v) {
bitvec u(*this);
setlen(len+v.len);
*this=u+v;
}
bitvec bitvec::l_getbits(int i,int l) const {
int k;
bitvec v(l);
if(l<=BPW) { v.vec=l_getword(i,l); return v; };
for(k=0;k<(l>>LDBPW);k++) v.pvec[k]=l_getword(i+(k<<LDBPW),BPW);
if(l&DBITS) {
k=l>>LDBPW;
v.pvec[k]=l_getword(i+(k<<LDBPW),l&DBITS);
};
return v;
}
word bitvec::l_getword(int i,int l) const {
int j,k;
word w;
j=i&DBITS;
k=i>>LDBPW;
w=(pvec[k]>>j)&MASK(l);
if(l+j>BPW) w|=(pvec[k+1]<<(BPW-j))&MASK(l);
return w;
}
void bitvec::l_setbits(int i,int l,word v) {
int j,k;
j=i&DBITS;
k=i>>LDBPW;
pvec[k]&=~(MASK(l)<<j);
pvec[k]|=(MASK(l)&v)<<j;
if(l+j<=BPW) return;
pvec[k+1]&=~MASK(l+j-BPW);
pvec[k+1]|=(MASK(l)&v)>>(BPW-j);
}
void bitvec::l_setbits(int i,const bitvec& v) {
int k;
for(k=0;k<(v.len>>LDBPW);k++) l_setbits(i+(k<<LDBPW),BPW,v.pvec[k]);
if(v.len&DBITS) {
k=v.len>>LDBPW;
l_setbits(i+(k<<LDBPW),v.len&DBITS,v.pvec[k]);
};
}
/* public members */
int bitvec::testless(const bitvec& v) const {
int k;
QC_CHECK(len==v.len);
if(len<=BPW) return vec<v.vec;
for(k=(len-1)>>LDBPW;k>=0;k--) {
if(pvec[k]<v.pvec[k]) return 1;
if(pvec[k]>v.pvec[k]) return 0;
};
return 0;
}
word bitvec::hashfunct() const {
int k;
word f=len;
if(len<=BPW) return vec+(vec>>(BPW/2))+(vec>>(BPW/4))+(vec>>(BPW/8));
for(k=0;k<WORDS(len);k++) f+=pvec[k]+(pvec[k]>>(BPW/2));
return f;
}
bitvec& bitvec::qnot() {
int k,l;
if(len<=BPW) {
vec=(~vec) & MASK(len);
} else {
l=WORDS(len);
for(k=0;k<l;k++) pvec[k]=~pvec[k];
if(len & DBITS) pvec[l-1]&=MASK(len & DBITS);
};
return *this;
}
const unsigned char qc_swaptab[256] = {
0x00, 0x80, 0x40, 0xc0, 0x20, 0xa0, 0x60, 0xe0,
0x10, 0x90, 0x50, 0xd0, 0x30, 0xb0, 0x70, 0xf0,
0x08, 0x88, 0x48, 0xc8, 0x28, 0xa8, 0x68, 0xe8,
0x18, 0x98, 0x58, 0xd8, 0x38, 0xb8, 0x78, 0xf8,
0x04, 0x84, 0x44, 0xc4, 0x24, 0xa4, 0x64, 0xe4,
0x14, 0x94, 0x54, 0xd4, 0x34, 0xb4, 0x74, 0xf4,
0x0c, 0x8c, 0x4c, 0xcc, 0x2c, 0xac, 0x6c, 0xec,
0x1c, 0x9c, 0x5c, 0xdc, 0x3c, 0xbc, 0x7c, 0xfc,
0x02, 0x82, 0x42, 0xc2, 0x22, 0xa2, 0x62, 0xe2,
0x12, 0x92, 0x52, 0xd2, 0x32, 0xb2, 0x72, 0xf2,
0x0a, 0x8a, 0x4a, 0xca, 0x2a, 0xaa, 0x6a, 0xea,
0x1a, 0x9a, 0x5a, 0xda, 0x3a, 0xba, 0x7a, 0xfa,
0x06, 0x86, 0x46, 0xc6, 0x26, 0xa6, 0x66, 0xe6,
0x16, 0x96, 0x56, 0xd6, 0x36, 0xb6, 0x76, 0xf6,
0x0e, 0x8e, 0x4e, 0xce, 0x2e, 0xae, 0x6e, 0xee,
0x1e, 0x9e, 0x5e, 0xde, 0x3e, 0xbe, 0x7e, 0xfe,
0x01, 0x81, 0x41, 0xc1, 0x21, 0xa1, 0x61, 0xe1,
0x11, 0x91, 0x51, 0xd1, 0x31, 0xb1, 0x71, 0xf1,
0x09, 0x89, 0x49, 0xc9, 0x29, 0xa9, 0x69, 0xe9,
0x19, 0x99, 0x59, 0xd9, 0x39, 0xb9, 0x79, 0xf9,
0x05, 0x85, 0x45, 0xc5, 0x25, 0xa5, 0x65, 0xe5,
0x15, 0x95, 0x55, 0xd5, 0x35, 0xb5, 0x75, 0xf5,
0x0d, 0x8d, 0x4d, 0xcd, 0x2d, 0xad, 0x6d, 0xed,
0x1d, 0x9d, 0x5d, 0xdd, 0x3d, 0xbd, 0x7d, 0xfd,
0x03, 0x83, 0x43, 0xc3, 0x23, 0xa3, 0x63, 0xe3,
0x13, 0x93, 0x53, 0xd3, 0x33, 0xb3, 0x73, 0xf3,
0x0b, 0x8b, 0x4b, 0xcb, 0x2b, 0xab, 0x6b, 0xeb,
0x1b, 0x9b, 0x5b, 0xdb, 0x3b, 0xbb, 0x7b, 0xfb,
0x07, 0x87, 0x47, 0xc7, 0x27, 0xa7, 0x67, 0xe7,
0x17, 0x97, 0x57, 0xd7, 0x37, 0xb7, 0x77, 0xf7,
0x0f, 0x8f, 0x4f, 0xcf, 0x2f, 0xaf, 0x6f, 0xef,
0x1f, 0x9f, 0x5f, 0xdf, 0x3f, 0xbf, 0x7f, 0xff
};
bitvec& bitvec::swap() {
int i,j;
word a,b;
for(i=0,j=len-8;i<len/2-7;i+=8,j-=8) {
a=getword(i,8);
b=getword(j,8);
a=qc_swaptab[a];
b=qc_swaptab[b];
setbits(i,8,b);
setbits(j,8,a);
}
for(i=(len/2)&~7,j=len-i-1;i<j;i++,j--) {
a=(*this)[i];
b=(*this)[j];
if(a^b) {
setbit(i,b);
setbit(j,a);
}
}
return *this;
}
/* other functions */
int bitvec_format=(BITVEC_FORMAT_HEX|BITVEC_FORMAT_KET);
const char *bitvec_ket_prefix = "|";
const char *bitvec_ket_postfix = ">";
const char *bitvec_hex_prefix = "0x";
const char *bitvec_hex_postfix = "";
ostream& operator << (ostream& s,const bitvec& v) {
int i,c;
if(bitvec_format&BITVEC_FORMAT_KET) {
s << bitvec_ket_prefix;
}
if(bitvec_format&BITVEC_FORMAT_HEX) {
s << bitvec_hex_prefix;
for(i=((v.length()-1) & ~3);i>=0;i-=4) {
c=v.getword(i,(i+4<=v.length()) ? 4 : (v.length()-i));
if(c<=9) s << (char)('0'+c); else s << (char)('a'+c-10);
}
s << bitvec_hex_postfix;
} else {
for(i=v.length()-1;i>=0;i--) {
s << (v[i] ? '1' : '0');
}
}
if(bitvec_format&BITVEC_FORMAT_KET) {
s << bitvec_ket_postfix;
}
return s;
}
istream& operator >> (istream& s,bitvec& v) {
int j=0,i=0,h=0,k=0;
char *b;
char c;
if(!(b=new char[v.length()+3])) goto error;
do {
s >> c;
if(!s) goto error;
if(c=='|') k=1;
} while(c==' ' || c=='\t' || c=='|');
while(1) {
b[i++]=c;
if(!(h && i<=(v.length()-1)/4) && !(!h && i<v.length())) break;
s >> c;
if(!s) goto error;
if(c=='x' && b[i-1]=='0') {
h=1; s >> c; i=0;
continue;
}
if(c>='A' && c<='F') c+='a'-'A';
if((h && (c<'0' || c>'9') && (c<'a' || c>'f')) ||
(!h && c!='0' && c!='1')) goto error;
}
b[i--]=0;
if(k) {
s >> c;
if(c!='>') goto error;
}
v=0;
if(h) {
for(j=0;i>=0 && j<v.length();i--,j+=4)
v.setbits(j,j+4<=v.length() ? 4 : v.length()-j,(word)
(b[i]>='0' && b[i]<='9' ? b[i]-'0' : b[i]-'a'+10));
} else {
for(j=0;i>=0 && j<v.length();i--,j++)
v.setbit(j,b[i]=='1');
}
return s;
error:
v.setlen(0);
if(b) qc_delarray(b);
return s;
}
syntax highlighted by Code2HTML, v. 0.9.1