/*
* Copyright 2008, 2009 Free Software Foundation, 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 .
*/
#include "BitVector.h"
#include
#include
#include
using namespace std;
/**
Apply a Galois polymonial to a binary seqeunce.
@param val The input sequence.
@param poly The polynomial.
@param order The order of the polynomial.
@return Single-bit result.
*/
unsigned applyPoly(uint64_t val, uint64_t poly, unsigned order)
{
uint64_t prod = val & poly;
unsigned sum = prod;
for (unsigned i=1; i>i;
return sum & 0x01;
}
BitVector::BitVector(const char *valString)
:Vector(strlen(valString))
{
uint32_t accum = 0;
for (size_t i=0; 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)
{
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)
{
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)
{
fillField(writeIndex,value,length);
writeIndex += length;
}
void BitVector::writeFieldReversed(size_t& writeIndex, uint64_t value, unsigned length)
{
fillFieldReversed(writeIndex,value,length);
writeIndex += length;
}
void BitVector::invert()
{
for (size_t i=0; i=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 (dpiState) << 1; // input state for 0
const uint32_t iState1 = iState0 | 0x01; // input state for 1
const uint32_t oStateShifted = (sp->oState) << mIRate; // shifted output
const float cost = sp->cost;
sp++;
// 0 input extension
mCandidates[i].cost = cost;
mCandidates[i].oState = oStateShifted | mGeneratorTable[iState0 & mCMask];
mCandidates[i].iState = iState0;
// 1 input extension
mCandidates[i+1].cost = cost;
mCandidates[i+1].oState = oStateShifted | mGeneratorTable[iState1 & mCMask];
mCandidates[i+1].iState = iState1;
}
}
void ViterbiR2O4::getSoftCostMetrics(const uint32_t inSample, const float *matchCost, const float *mismatchCost)
{
const float *cTab[2] = {matchCost,mismatchCost};
for (unsigned i=0; i>1)&0x01][0];
}
}
void ViterbiR2O4::pruneCandidates()
{
const vCand* c1 = mCandidates; // 0-prefix
const vCand* c2 = mCandidates + mIStates; // 1-prefix
for (unsigned i=0; i=minCost) continue;
minCost = thisCost;
minIndex=i;
}
return mSurvivors[minIndex];
}
const ViterbiR2O4::vCand& ViterbiR2O4::step(uint32_t inSample, const float *probs, const float *iprobs)
{
branchCandidates();
getSoftCostMetrics(inSample,probs,iprobs);
pruneCandidates();
return minCost();
}
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; i0.5F) newSig[i]=1;
else newSig[i] = 0;
}
return newSig;
}
void SoftVector::decode(ViterbiR2O4 &decoder, BitVector& target) const
{
const size_t sz = size();
const unsigned deferral = decoder.deferral();
const size_t ctsz = sz + deferral*decoder.iRate();
assert(sz <= decoder.iRate()*target.size());
// Build a "history" array where each element contains the full history.
uint32_t history[ctsz];
{
BitVector bits = sliced();
uint32_t accum = 0;
for (size_t i=0; i0.5F) pVal = 1.0F-pVal;
float ipVal = 1.0F-pVal;
// This is a cheap approximation to an ideal cost function.
if (pVal<0.01F) pVal = 0.01;
if (ipVal<0.01F) ipVal = 0.01;
matchCostTable[i] = 0.25F/ipVal;
mismatchCostTable[i] = 0.25F/pVal;
}
// pad end of table with unknowns
for (size_t i=sz; i=deferral) *op++ = (minCost.iState >> deferral)&0x01;
oCount++;
}
}
}
// (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;
}
ostream& operator<<(ostream& os, const SoftVector& sv)
{
for (size_t i=0; i0.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> (8-rem),rem);
}
void BitVector::hex(ostream& os) const
{
os << std::hex;
unsigned digits = size()/4;
size_t wp=0;
for (unsigned i=0; i0) {
if (sscanf(src+digits, "%1x", &val) < 1) {
return false;
}
fillField(whole,val,rem);
}
return true;
}
// vim: ts=4 sw=4