BitVector.cpp

/*
* Copyright 2008, 2009, 2014 Free Software Foundation, Inc.
* Copyright 2014 Range Networks, Inc.
*
*
* This software is distributed under the terms of the GNU Affero Public License.
* See the COPYING file in the main directory for details.
*
* This use of this software may be subject to additional restrictions.
* See the LEGAL file in the main directory for details.

	This program is free software: you can redistribute it and/or modify
	it under the terms of the GNU Affero General Public License as published by
	the Free Software Foundation, either version 3 of the License, or
	(at your option) any later version.

	This program 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 Affero General Public License for more details.

	You should have received a copy of the GNU Affero General Public License
	along with this program.  If not, see <http://www.gnu.org/licenses/>.

*/




#include "BitVector.h"
#include <iostream>
#include <stdio.h>
#include <sstream>
#include <string.h>
#include <Logger.h>

using namespace std;



BitVector::BitVector(const char *valString)
{
	// 1-30-2013 pat: I dont know what this was intended to do, but it did not create a normalized BitVector,
	// and it could even fail if the accum overlows 8 bits.
	//uint32_t accum = 0;
	//for (size_t i=0; i<size(); i++) {
	//	accum <<= 1;
	//	if (valString[i]=='1') accum |= 0x01;
	//	mStart[i] = accum;
	//}
	vInit(strlen(valString));
	char *rp = begin();
	for (const char *cp = valString; *cp; cp++, rp++) {
		*rp = (*cp == '1');
	}
}


uint64_t BitVector::peekField(size_t readIndex, unsigned length) const
{
	uint64_t accum = 0;
	char *dp = mStart + readIndex;

	for (unsigned i=0; i<length; i++) {
		accum = (accum<<1) | ((*dp++) & 0x01);
	}
	return accum;
}




uint64_t BitVector::peekFieldReversed(size_t readIndex, unsigned length) const
{
	uint64_t accum = 0;
	char *dp = mStart + readIndex + length - 1;
	assert(dp<mEnd);
	for (int i=(length-1); i>=0; i--) {
		accum = (accum<<1) | ((*dp--) & 0x01);
	}
	return accum;
}




uint64_t BitVector::readField(size_t& readIndex, unsigned length) const
{
	const uint64_t retVal = peekField(readIndex,length);
	readIndex += length;
	return retVal;
}


uint64_t BitVector::readFieldReversed(size_t& readIndex, unsigned length) const
{

	const uint64_t retVal = peekFieldReversed(readIndex,length);
	readIndex += length;
	return retVal;

}




void BitVector::fillField(size_t writeIndex, uint64_t value, unsigned length)
{
	if (length != 0) {
		char *dpBase = mStart + writeIndex;
		char *dp = dpBase + length - 1;
		assert(dp < mEnd);
		while (dp>=dpBase) {
			*dp-- = value & 0x01;
			value >>= 1;
		}
	}
}


void BitVector::fillFieldReversed(size_t writeIndex, uint64_t value, unsigned length)
{
	if (length != 0) {
		char *dp = mStart + writeIndex;
		char *dpEnd = dp + length - 1;
		assert(dpEnd < mEnd);
		while (dp<=dpEnd) {
			*dp++ = value & 0x01;
			value >>= 1;
		}
	}
}




void BitVector::writeField(size_t& writeIndex, uint64_t value, unsigned length)
{
	if (length != 0) {
		fillField(writeIndex,value,length);
		writeIndex += length;
	}
}


void BitVector::writeFieldReversed(size_t& writeIndex, uint64_t value, unsigned length)
{
	if (length != 0) {
		fillFieldReversed(writeIndex,value,length);
		writeIndex += length;
	}
}


void BitVector::invert()
{
	for (size_t i=0; i<size(); i++) {
		mStart[i] = ~mStart[i];
	}
}




void BitVector::reverse8()
{
	assert(size()>=8);

	char tmp0 = mStart[0];
	mStart[0] = mStart[7];
	mStart[7] = tmp0;

	char tmp1 = mStart[1];
	mStart[1] = mStart[6];
	mStart[6] = tmp1;

	char tmp2 = mStart[2];
	mStart[2] = mStart[5];
	mStart[5] = tmp2;

	char tmp3 = mStart[3];
	mStart[3] = mStart[4];
	mStart[4] = tmp3;
}



void BitVector::LSB8MSB()
{
	if (size()<8) return;
	size_t size8 = 8*(size()/8);
	size_t iTop = size8 - 8;
	for (size_t i=0; i<=iTop; i+=8) segment(i,8).reverse8();
}



uint64_t BitVector::syndrome(Generator& gen) const
{
	gen.clear();
	const char *dp = mStart;
	while (dp<mEnd) gen.syndromeShift(*dp++);
	return gen.state();
}


uint64_t BitVector::parity(Generator& gen) const
{
	gen.clear();
	const char *dp = mStart;
	while (dp<mEnd) gen.encoderShift(*dp++);
	return gen.state();
}


unsigned BitVector::sum() const
{
	unsigned sum = 0;
	for (size_t i=0; i<size(); i++) sum += mStart[i] & 0x01;
	return sum;
}




void BitVector::map(const unsigned *map, size_t mapSize, BitVector& dest) const
{
	for (unsigned i=0; i<mapSize; i++) {
		dest.mStart[i] = mStart[map[i]];
	}
}




void BitVector::unmap(const unsigned *map, size_t mapSize, BitVector& dest) const
{
	for (unsigned i=0; i<mapSize; i++) {
		dest.mStart[map[i]] = mStart[i];
	}
}







ostream& operator<<(ostream& os, const BitVector& hv)
{
	for (size_t i=0; i<hv.size(); i++) {
		if (hv.bit(i)) os << '1';
		else os << '0';
	}
	return os;
}




uint64_t Parity::syndrome(const BitVector& receivedCodeword)
{
	return receivedCodeword.syndrome(*this);
}


void Parity::writeParityWord(const BitVector& data, BitVector& parityTarget, bool invert)
{
	uint64_t pWord = data.parity(*this);
	if (invert) pWord = ~pWord; 
	parityTarget.fillField(0,pWord,size());
}









SoftVector::SoftVector(const BitVector& source)
{
	resize(source.size());
	for (size_t i=0; i<size(); i++) {
		if (source.bit(i)) mStart[i]=1.0F;
		else mStart[i]=0.0F;
	}
}


BitVector SoftVector::sliced() const
{
	size_t sz = size();
	BitVector newSig(sz);
	for (size_t i=0; i<sz; i++) {
		if (mStart[i]>0.5F) newSig[i]=1;
		else newSig[i] = 0;
	}
	return newSig;
}



// (pat) Added 6-22-2012
float SoftVector::getEnergy(float *plow) const
{
	const SoftVector &vec = *this;
	int len = vec.size();
	float avg = 0; float low = 1;
	for (int i = 0; i < len; i++) {
		float bit = vec[i];
		float energy = 2*((bit < 0.5) ? (0.5-bit) : (bit-0.5));
		if (energy < low) low = energy;
		avg += energy/len;
	}
	if (plow) { *plow = low; }
	return avg;
}

// (pat) Added 1-2014.  Compute SNR of a soft vector.  Very similar to above.
// Since we dont really know what the expected signal values are, we will assume that the signal is 0 or 1
// and return the SNR on that basis.
// SNR is power(signal) / power(noise) where power can be calculated as (RMS(signal) / RMS(noise))**2 of the values.
// Since RMS is square-rooted, ie RMS = sqrt(1/n * (x1**2 + x2**2 ...)), we just add up the squares.
// To compute RMS of the signal we will remove any constant offset, so the signal values are either 0.5 or -0.5,
// so the RMS of the signal is just 0.5**2 * len;  all we need to compute is the noise component.
float SoftVector::getSNR() const
{
	float sumSquaresNoise = 0;
	const SoftVector &vec = *this;
	int len = vec.size();
	if (len == 0) { return 0.0; }
	for (int i = 0; i < len; i++) {
		float bit = vec[i];
		if (bit < 0.5) {
			// Assume signal is 0.
			sumSquaresNoise += (bit - 0.0) * (bit - 0.0);
		} else {
			// Assume signal is 1.
			sumSquaresNoise += (bit - 1.0) * (bit - 1.0);
		}
	}
	float sumSquaresSignal = 0.5 * 0.5 * len;
	// I really want log10 of this to convert to dB, but log is expensive, and Harvind seems to like absolute SNR.
	// Clamp max to 999; it shouldnt get up there but be sure.  This also avoids divide by zero.
	if (sumSquaresNoise * 1000 < sumSquaresSignal) return 999;
	return sumSquaresSignal / sumSquaresNoise;
}



ostream& operator<<(ostream& os, const SoftVector& sv)
{
	for (size_t i=0; i<sv.size(); i++) {
		if (sv[i]<0.25) os << "0";
		else if (sv[i]>0.75) os << "1";
		else os << "-";
	}
	return os;
}



void BitVector::pack(unsigned char* targ) const
{
	// Assumes MSB-first packing.
	unsigned bytes = size()/8;
	for (unsigned i=0; i<bytes; i++) {
		targ[i] = peekField(i*8,8);
	}
	unsigned whole = bytes*8;
	unsigned rem = size() - whole;
	if (rem==0) return;
	targ[bytes] = peekField(whole,rem) << (8-rem);
}

string BitVector::packToString() const
{
	string result;
	result.reserve((size()+7)/8);
	// Tempting to call this->pack(result.c_str()) but technically c_str() is read-only.
	unsigned bytes = size()/8;
	for (unsigned i=0; i<bytes; i++) {
		result.push_back(peekField(i*8,8));
	}
	unsigned whole = bytes*8;
	unsigned rem = size() - whole;
	if (rem==0) return result;
	result.push_back(peekField(whole,rem) << (8-rem));
	return result;
}


void BitVector::unpack(const unsigned char* src)
{
	// Assumes MSB-first packing.
	unsigned bytes = size()/8;
	for (unsigned i=0; i<bytes; i++) {
		fillField(i*8,src[i],8);
	}
	unsigned whole = bytes*8;
	unsigned rem = size() - whole;
	if (rem==0) return;
        fillField(whole,src[bytes] >> (8-rem),rem);
}

void BitVector::hex(ostream& os) const
{
	os << std::hex;
	unsigned digits = size()/4;
	size_t wp=0;
	for (unsigned i=0; i<digits; i++) {
		os << readField(wp,4);
	}
	os << std::dec;
}

std::string BitVector::hexstr() const
{
	std::ostringstream ss;
	hex(ss);
	return ss.str();
}


bool BitVector::unhex(const char* src)
{
	// Assumes MSB-first packing.
	unsigned int val;
	unsigned digits = size()/4;
	for (unsigned i=0; i<digits; i++) {
		if (sscanf(src+i, "%1x", &val) < 1) {
			return false;
		}
		fillField(i*4,val,4);
	}
	unsigned whole = digits*4;
	unsigned rem = size() - whole;
	if (rem>0) {
		if (sscanf(src+digits, "%1x", &val) < 1) {
			return false;
		}
		fillField(whole,val,rem);
	}
	return true;
}

bool BitVector::operator==(const BitVector &other) const
{
	unsigned l = size();
	return l == other.size() && 0==memcmp(begin(),other.begin(),l);
}

void BitVector::copyPunctured(BitVector &dst, const unsigned *puncture, const size_t plth)
{
	assert(size() - plth == dst.size());
	char *srcp = mStart;
	char *dstp = dst.mStart;
	const unsigned *pend = puncture + plth;
	while (srcp < mEnd) {
		if (puncture < pend) {
			int n = (*puncture++) - (srcp - mStart);
			assert(n >= 0);
			for (int i = 0; i < n; i++) {
				assert(srcp < mEnd && dstp < dst.mEnd);
				*dstp++ = *srcp++;
			}
			srcp++;
		} else {
			while (srcp < mEnd) {
				assert(dstp < dst.mEnd);
				*dstp++ = *srcp++;
			}
		}
	}
	assert(dstp == dst.mEnd && puncture == pend);
}

void SoftVector::copyUnPunctured(SoftVector &dst, const unsigned *puncture, const size_t plth)
{
	assert(size() + plth == dst.size());
	float *srcp = mStart;
	float *dstp = dst.mStart;
	const unsigned *pend = puncture + plth;
	while (dstp < dst.mEnd) {
		if (puncture < pend) {
			int n = (*puncture++) - (dstp - dst.mStart);
			assert(n >= 0);
			for (int i = 0; i < n; i++) {
				assert(srcp < mEnd && dstp < dst.mEnd);
				*dstp++ = *srcp++;
			}
			*dstp++ = 0.5;
		} else {
			while (srcp < mEnd) {
				assert(dstp < dst.mEnd);
				*dstp++ = *srcp++;
			}
		}
	}
	assert(dstp == dst.mEnd && puncture == pend);
}

// vim: ts=4 sw=4