Updated BitVector to recent source
diff --git a/lib/decoding/BitVector.h b/lib/decoding/BitVector.h
index 3019c2c..0f78b97 100644
--- a/lib/decoding/BitVector.h
+++ b/lib/decoding/BitVector.h
@@ -1,30 +1,35 @@
/*
-* Copyright 2008 Free Software Foundation, Inc.
+* Copyright 2008, 2009, 2014 Free Software Foundation, Inc.
+* Copyright 2014 Range Networks, Inc.
*
-* This software is distributed under the terms of the GNU Public License.
+* 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 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 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 General Public License for more details.
+ 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 General Public License
- along with this program. If not, see <http://www.gnu.org/licenses/>.
+ 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/>.
*/
-#ifndef FECVECTORS_H
-#define FECVECTORS_H
+#ifndef BITVECTORS_H
+#define BITVECTORS_H
#include "Vector.h"
#include <stdint.h>
+#include <stdio.h>
class BitVector;
@@ -32,6 +37,7 @@
+
/** Shift-register (LFSR) generator. */
class Generator {
@@ -109,171 +115,83 @@
};
-
-
-/**
- Class to represent convolutional coders/decoders of rate 1/2, memory length 4.
- This is the "workhorse" coder for most GSM channels.
-*/
-class ViterbiR2O4 {
-
- private:
- /**name Lots of precomputed elements so the compiler can optimize like hell. */
- //@{
- /**@name Core values. */
- //@{
- static const unsigned mIRate = 2; ///< reciprocal of rate
- static const unsigned mOrder = 4; ///< memory length of generators
- //@}
- /**@name Derived values. */
- //@{
- static const unsigned mIStates = 0x01 << mOrder; ///< number of states, number of survivors
- static const uint32_t mSMask = mIStates-1; ///< survivor mask
- static const uint32_t mCMask = (mSMask<<1) | 0x01; ///< candidate mask
- static const uint32_t mOMask = (0x01<<mIRate)-1; ///< ouput mask, all iRate low bits set
- static const unsigned mNumCands = mIStates*2; ///< number of candidates to generate during branching
- static const unsigned mDeferral = 6*mOrder; ///< deferral to be used
- //@}
- //@}
-
- /** Precomputed tables. */
- //@{
- uint32_t mCoeffs[mIRate]; ///< polynomial for each generator
- uint32_t mStateTable[mIRate][2*mIStates]; ///< precomputed generator output tables
- uint32_t mGeneratorTable[2*mIStates]; ///< precomputed coder output table
- //@}
-
+// (pat) Nov 2013. I rationalized the behavior of BitVector and added assertions to core dump code
+// that relied on the bad aspects of the original behavior. See comments at VectorBase.
+class BitVector : public VectorBase<char>
+{
public:
-
- /**
- A candidate sequence in a Viterbi decoder.
- The 32-bit state register can support a deferral of 6 with a 4th-order coder.
- */
- typedef struct candStruct {
- uint32_t iState; ///< encoder input associated with this candidate
- uint32_t oState; ///< encoder output associated with this candidate
- float cost; ///< cost (metric value), float to support soft inputs
- } vCand;
-
- /** Clear a structure. */
- void clear(vCand& v)
- {
- v.iState=0;
- v.oState=0;
- v.cost=0;
- }
-
-
- private:
-
- /**@name Survivors and candidates. */
- //@{
- vCand mSurvivors[mIStates]; ///< current survivor pool
- vCand mCandidates[2*mIStates]; ///< current candidate pool
- //@}
-
- public:
-
- unsigned iRate() const { return mIRate; }
- uint32_t cMask() const { return mCMask; }
- uint32_t stateTable(unsigned g, unsigned i) const { return mStateTable[g][i]; }
- unsigned deferral() const { return mDeferral; }
-
-
- ViterbiR2O4();
-
- /** Set all cost metrics to zero. */
- void initializeStates();
-
- /**
- Full cycle of the Viterbi algorithm: branch, metrics, prune, select.
- @return reference to minimum-cost candidate.
- */
- const vCand& step(uint32_t inSample, const float *probs, const float *iprobs);
-
- private:
-
- /** Branch survivors into new candidates. */
- void branchCandidates();
-
- /** Compute cost metrics for soft-inputs. */
- void getSoftCostMetrics(uint32_t inSample, const float *probs, const float *iprobs);
-
- /** Select survivors from the candidate set. */
- void pruneCandidates();
-
- /** Find the minimum cost survivor. */
- const vCand& minCost() const;
-
- /**
- Precompute the state tables.
- @param g Generator index 0..((1/rate)-1)
- */
- void computeStateTables(unsigned g);
-
- /**
- Precompute the generator outputs.
- mCoeffs must be defined first.
- */
- void computeGeneratorTable();
-
-};
-
-
-
-
-class BitVector : public Vector<char> {
-
-
- public:
-
/**@name Constructors. */
//@{
/**@name Casts of Vector constructors. */
- //@{
- BitVector(char* wData, char* wStart, char* wEnd)
- :Vector<char>(wData,wStart,wEnd)
- { }
- BitVector(size_t len=0):Vector<char>(len) {}
- BitVector(const Vector<char>& source):Vector<char>(source) {}
- BitVector(Vector<char>& source):Vector<char>(source) {}
- BitVector(const Vector<char>& source1, const Vector<char> source2):Vector<char>(source1,source2) {}
- //@}
+ BitVector(VectorDataType wData, char* wStart, char* wEnd) : VectorBase<char>(wData, wStart, wEnd) {}
+
+ // The one and only copy-constructor.
+ BitVector(const BitVector&other) : VectorBase<char>() {
+ VECTORDEBUG("BitVector(%p)",(void*)&other);
+ if (other.getData()) {
+ this->clone(other);
+ } else {
+ this->makeAlias(other);
+ }
+ }
+
+ // (pat) Removed default value for len and added 'explicit'. Please do not remove 'explicit';
+ // it prevents auto-conversion of int to BitVector in constructors.
+ // Previous code was often ambiguous, especially for L3Frame and descendent constructors, leading to latent bugs.
+ explicit BitVector(size_t len) { this->vInit(len); }
+ BitVector() { this->vInit(0); }
+
+ /** Build a BitVector by concatenation. */
+ BitVector(const BitVector& other1, const BitVector& other2) : VectorBase<char>()
+ {
+ assert(this->getData() == 0);
+ this->vConcat(other1,other2);
+ }
/** Construct from a string of "0" and "1". */
+ // (pat) Characters that are not '0' or '1' map to '0'.
BitVector(const char* valString);
//@}
- /** Index a single bit. */
- bool bit(size_t index) const
- {
- // We put this code in .h for fast inlining.
- const char *dp = mStart+index;
- assert(dp<mEnd);
- return (*dp) & 0x01;
- }
-
/**@name Casts and overrides of Vector operators. */
//@{
+ // (pat) Please DO NOT add a const anywhere in this method. Use cloneSegment instead.
BitVector segment(size_t start, size_t span)
{
- char* wStart = mStart + start;
+ char* wStart = this->begin() + start;
char* wEnd = wStart + span;
- assert(wEnd<=mEnd);
+ assert(wEnd<=this->end());
+#if BITVECTOR_REFCNTS
+ return BitVector(mData,wStart,wEnd);
+#else
return BitVector(NULL,wStart,wEnd);
+#endif
}
- BitVector alias()
- { return segment(0,size()); }
+ // (pat) Historically the BitVector segment method had const and non-const versions with different behavior.
+ // I changed the name of the const version to cloneSegment and replaced all uses throughout OpenBTS.
+ const BitVector cloneSegment(size_t start, size_t span) const
+ {
+ BitVector seg = const_cast<BitVector*>(this)->segment(start,span);
+ // (pat) We are depending on the Return Value Optimization not to invoke the copy-constructor on the result,
+ // which would result in its immediate destruction while we are still using it.
+ BitVector result;
+ result.clone(seg);
+ return result;
+ }
- const BitVector segment(size_t start, size_t span) const
- { return (BitVector)(Vector<char>::segment(start,span)); }
+ BitVector alias() const {
+ return const_cast<BitVector*>(this)->segment(0,size());
+ }
BitVector head(size_t span) { return segment(0,span); }
- const BitVector head(size_t span) const { return segment(0,span); }
BitVector tail(size_t start) { return segment(start,size()-start); }
- const BitVector tail(size_t start) const { return segment(start,size()-start); }
+
+ // (pat) Please do NOT put the const version of head and tail back in, because historically they were messed up.
+ // Use cloneSegment instead.
+ //const BitVector head(size_t span) const { return segment(0,span); }
+ //const BitVector tail(size_t start) const { return segment(start,size()-start); }
//@}
@@ -285,8 +203,6 @@
uint64_t syndrome(Generator& gen) const;
/** Calculate the parity word for the vector with the given Generator. */
uint64_t parity(Generator& gen) const;
- /** Encode the signal with the GSM rate 1/2 convolutional encoder. */
- void encode(const ViterbiR2O4& encoder, BitVector& target);
//@}
@@ -304,9 +220,16 @@
/**@name Serialization and deserialization. */
//@{
uint64_t peekField(size_t readIndex, unsigned length) const;
+ uint64_t peekFieldReversed(size_t readIndex, unsigned length) const;
uint64_t readField(size_t& readIndex, unsigned length) const;
+ uint64_t readFieldReversed(size_t& readIndex, unsigned length) const;
void fillField(size_t writeIndex, uint64_t value, unsigned length);
+ void fillFieldReversed(size_t writeIndex, uint64_t value, unsigned length);
void writeField(size_t& writeIndex, uint64_t value, unsigned length);
+ void writeFieldReversed(size_t& writeIndex, uint64_t value, unsigned length);
+ void write0(size_t& writeIndex) { writeField(writeIndex,0,1); }
+ void write1(size_t& writeIndex) { writeField(writeIndex,1,1); }
+
//@}
/** Sum of bits. */
@@ -320,12 +243,76 @@
/** Pack into a char array. */
void pack(unsigned char*) const;
+ // Same as pack but return a string.
+ std::string packToString() const;
- /** Unopack from a char array. */
+ /** Unpack from a char array. */
void unpack(const unsigned char*);
+ /** Make a hexdump string. */
+ void hex(std::ostream&) const;
+ std::string hexstr() const;
+
+ /** Unpack from a hexdump string.
+ * @returns true on success, false on error. */
+ bool unhex(const char*);
+
+ // For this method, 'other' should have been run through the copy-constructor already
+ // (unless it was newly created, ie foo.dup(L2Frame(...)), in which case we are screwed anyway)
+ // so the call to makeAlias is redundant.
+ // This only works if other is already an alias.
+ void dup(BitVector other) { assert(!this->getData()); makeAlias(other); assert(this->mStart == other.mStart); }
+ void dup(BitVector &other) { makeAlias(other); assert(this->mStart == other.mStart); }
+
+#if 0
+ void operator=(const BitVector& other) {
+ printf("BitVector::operator=\n");
+ assert(0);
+ //this->dup(other);
+ }
+#endif
+
+ bool operator==(const BitVector &other) const;
+
+ /** Copy to dst, not including those indexed in puncture. */
+ void copyPunctured(BitVector &dst, const unsigned *puncture, const size_t plth);
+
+ /** Index a single bit. */
+ // (pat) Cant have too many ways to do this, I guess.
+ bool bit(size_t index) const
+ {
+ // We put this code in .h for fast inlining.
+ const char *dp = this->begin()+index;
+ assert(dp<this->end());
+ return (*dp) & 0x01;
+ }
+
+ char& operator[](size_t index)
+ {
+ assert(this->mStart+index<this->mEnd);
+ return this->mStart[index];
+ }
+
+ const char& operator[](size_t index) const
+ {
+ assert(this->mStart+index<this->mEnd);
+ return this->mStart[index];
+ }
+
+ /** Set a bit */
+ void settfb(size_t index, int value)
+ {
+ char *dp = this->mStart+index;
+ assert(dp<this->mEnd);
+ *dp = value;
+ }
+
+ typedef char* iterator;
+ typedef const char* const_iterator;
};
+// (pat) BitVector2 was an intermediate step in fixing BitVector but is no longer needed.
+#define BitVector2 BitVector
std::ostream& operator<<(std::ostream&, const BitVector&);
@@ -348,7 +335,7 @@
/** Construct a SoftVector from a C string of "0", "1", and "X". */
SoftVector(const char* valString);
-
+
/** Construct a SoftVector from a BitVector. */
SoftVector(const BitVector& source);
@@ -395,8 +382,11 @@
const SoftVector tail(size_t start) const { return segment(start,size()-start); }
//@}
- /** Decode soft symbols with the GSM rate-1/2 Viterbi decoder. */
- void decode(ViterbiR2O4 &decoder, BitVector& target) const;
+ // (pat) How good is the SoftVector in the sense of the bits being solid?
+ // Result of 1 is perfect and 0 means all the bits were 0.5
+ // If plow is non-NULL, also return the lowest energy bit.
+ float getEnergy(float *low=0) const;
+ float getSNR() const;
/** Fill with "unknown" values. */
void unknown() { fill(0.5F); }
@@ -412,6 +402,24 @@
/** Slice the whole signal into bits. */
BitVector sliced() const;
+ /** Copy to dst, adding in 0.5 for those indexed in puncture. */
+ void copyUnPunctured(SoftVector &dst, const unsigned *puncture, const size_t plth);
+
+ /** Return a soft bit. */
+ float softbit(size_t index) const
+ {
+ const float *dp = mStart+index;
+ assert(dp<mEnd);
+ return *dp;
+ }
+
+ /** Set a soft bit */
+ void settfb(size_t index, float value)
+ {
+ float *dp = mStart+index;
+ assert(dp<mEnd);
+ *dp = value;
+ }
};
@@ -421,7 +429,5 @@
-
-
#endif
// vim: ts=4 sw=4