GNU Radio's GSM Package
BitVector.h
Go to the documentation of this file.
1 /*
2 * Copyright 2008, 2009, 2014 Free Software Foundation, Inc.
3 * Copyright 2014 Range Networks, Inc.
4 *
5 * This software is distributed under the terms of the GNU Affero Public License.
6 * See the COPYING file in the main directory for details.
7 *
8 * This use of this software may be subject to additional restrictions.
9 * See the LEGAL file in the main directory for details.
10 
11  This program is free software: you can redistribute it and/or modify
12  it under the terms of the GNU Affero General Public License as published by
13  the Free Software Foundation, either version 3 of the License, or
14  (at your option) any later version.
15 
16  This program is distributed in the hope that it will be useful,
17  but WITHOUT ANY WARRANTY; without even the implied warranty of
18  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19  GNU Affero General Public License for more details.
20 
21  You should have received a copy of the GNU Affero General Public License
22  along with this program. If not, see <http://www.gnu.org/licenses/>.
23 
24 */
25 
26 
27 #ifndef BITVECTORS_H
28 #define BITVECTORS_H
29 
30 #include "Vector.h"
31 #include <stdint.h>
32 #include <stdio.h>
33 
34 
35 class BitVector;
36 class SoftVector;
37 
38 
39 
40 
41 /** Shift-register (LFSR) generator. */
42 class Generator {
43 
44  private:
45 
46  uint64_t mCoeff; ///< polynomial coefficients. LSB is zero exponent.
47  uint64_t mState; ///< shift register state. LSB is most recent.
48  uint64_t mMask; ///< mask for reading state
49  unsigned mLen; ///< number of bits used in shift register
50  unsigned mLen_1; ///< mLen - 1
51 
52  public:
53 
54  Generator(uint64_t wCoeff, unsigned wLen)
55  :mCoeff(wCoeff),mState(0),
56  mMask((1ULL<<wLen)-1),
57  mLen(wLen),mLen_1(wLen-1)
58  { assert(wLen<64); }
59 
60  void clear() { mState=0; }
61 
62  /**@name Accessors */
63  //@{
64  uint64_t state() const { return mState & mMask; }
65  unsigned size() const { return mLen; }
66  //@}
67 
68  /**
69  Calculate one bit of a syndrome.
70  This is in the .h for inlining.
71  */
72  void syndromeShift(unsigned inBit)
73  {
74  const unsigned fb = (mState>>(mLen_1)) & 0x01;
75  mState = (mState<<1) ^ (inBit & 0x01);
76  if (fb) mState ^= mCoeff;
77  }
78 
79  /**
80  Update the generator state by one cycle.
81  This is in the .h for inlining.
82  */
83  void encoderShift(unsigned inBit)
84  {
85  const unsigned fb = ((mState>>(mLen_1)) ^ inBit) & 0x01;
86  mState <<= 1;
87  if (fb) mState ^= mCoeff;
88  }
89 
90 
91 };
92 
93 
94 
95 
96 /** Parity (CRC-type) generator and checker based on a Generator. */
97 class Parity : public Generator {
98 
99  protected:
100 
101  unsigned mCodewordSize;
102 
103  public:
104 
105  Parity(uint64_t wCoefficients, unsigned wParitySize, unsigned wCodewordSize)
106  :Generator(wCoefficients, wParitySize),
107  mCodewordSize(wCodewordSize)
108  { }
109 
110  /** Compute the parity word and write it into the target segment. */
111  void writeParityWord(const BitVector& data, BitVector& parityWordTarget, bool invert=true);
112 
113  /** Compute the syndrome of a received sequence. */
114  uint64_t syndrome(const BitVector& receivedCodeword);
115 };
116 
117 
118 // (pat) Nov 2013. I rationalized the behavior of BitVector and added assertions to core dump code
119 // that relied on the bad aspects of the original behavior. See comments at VectorBase.
120 class BitVector : public VectorBase<char>
121 {
122  public:
123  /**@name Constructors. */
124  //@{
125 
126  /**@name Casts of Vector constructors. */
127  BitVector(VectorDataType wData, char* wStart, char* wEnd) : VectorBase<char>(wData, wStart, wEnd) {}
128 
129  // The one and only copy-constructor.
130  BitVector(const BitVector&other) : VectorBase<char>() {
131  VECTORDEBUG("BitVector(%p)",(void*)&other);
132  if (other.getData()) {
133  this->clone(other);
134  } else {
135  this->makeAlias(other);
136  }
137  }
138 
139  // (pat) Removed default value for len and added 'explicit'. Please do not remove 'explicit';
140  // it prevents auto-conversion of int to BitVector in constructors.
141  // Previous code was often ambiguous, especially for L3Frame and descendent constructors, leading to latent bugs.
142  explicit BitVector(size_t len) { this->vInit(len); }
143  BitVector() { this->vInit(0); }
144 
145  /** Build a BitVector by concatenation. */
146  BitVector(const BitVector& other1, const BitVector& other2) : VectorBase<char>()
147  {
148  assert(this->getData() == 0);
149  this->vConcat(other1,other2);
150  }
151 
152  /** Construct from a string of "0" and "1". */
153  // (pat) Characters that are not '0' or '1' map to '0'.
154  BitVector(const char* valString);
155  //@}
156 
157  /**@name Casts and overrides of Vector operators. */
158  //@{
159  // (pat) Please DO NOT add a const anywhere in this method. Use cloneSegment instead.
160  BitVector segment(size_t start, size_t span)
161  {
162  char* wStart = this->begin() + start;
163  char* wEnd = wStart + span;
164  assert(wEnd<=this->end());
165 #if BITVECTOR_REFCNTS
166  return BitVector(mData,wStart,wEnd);
167 #else
168  return BitVector(NULL,wStart,wEnd);
169 #endif
170  }
171 
172  // (pat) Historically the BitVector segment method had const and non-const versions with different behavior.
173  // I changed the name of the const version to cloneSegment and replaced all uses throughout OpenBTS.
174  const BitVector cloneSegment(size_t start, size_t span) const
175  {
176  BitVector seg = const_cast<BitVector*>(this)->segment(start,span);
177  // (pat) We are depending on the Return Value Optimization not to invoke the copy-constructor on the result,
178  // which would result in its immediate destruction while we are still using it.
179  BitVector result;
180  result.clone(seg);
181  return result;
182  }
183 
184  BitVector alias() const {
185  return const_cast<BitVector*>(this)->segment(0,size());
186  }
187 
188  BitVector head(size_t span) { return segment(0,span); }
189  BitVector tail(size_t start) { return segment(start,size()-start); }
190 
191  // (pat) Please do NOT put the const version of head and tail back in, because historically they were messed up.
192  // Use cloneSegment instead.
193  //const BitVector head(size_t span) const { return segment(0,span); }
194  //const BitVector tail(size_t start) const { return segment(start,size()-start); }
195  //@}
196 
197 
198  void zero() { fill(0); }
199 
200  /**@name FEC operations. */
201  //@{
202  /** Calculate the syndrome of the vector with the given Generator. */
203  uint64_t syndrome(Generator& gen) const;
204  /** Calculate the parity word for the vector with the given Generator. */
205  uint64_t parity(Generator& gen) const;
206  //@}
207 
208 
209  /** Invert 0<->1. */
210  void invert();
211 
212  /**@name Byte-wise operations. */
213  //@{
214  /** Reverse an 8-bit vector. */
215  void reverse8();
216  /** Reverse groups of 8 within the vector (byte reversal). */
217  void LSB8MSB();
218  //@}
219 
220  /**@name Serialization and deserialization. */
221  //@{
222  uint64_t peekField(size_t readIndex, unsigned length) const;
223  uint64_t peekFieldReversed(size_t readIndex, unsigned length) const;
224  uint64_t readField(size_t& readIndex, unsigned length) const;
225  uint64_t readFieldReversed(size_t& readIndex, unsigned length) const;
226  void fillField(size_t writeIndex, uint64_t value, unsigned length);
227  void fillFieldReversed(size_t writeIndex, uint64_t value, unsigned length);
228  void writeField(size_t& writeIndex, uint64_t value, unsigned length);
229  void writeFieldReversed(size_t& writeIndex, uint64_t value, unsigned length);
230  void write0(size_t& writeIndex) { writeField(writeIndex,0,1); }
231  void write1(size_t& writeIndex) { writeField(writeIndex,1,1); }
232 
233  //@}
234 
235  /** Sum of bits. */
236  unsigned sum() const;
237 
238  /** Reorder bits, dest[i] = this[map[i]]. */
239  void map(const unsigned *map, size_t mapSize, BitVector& dest) const;
240 
241  /** Reorder bits, dest[map[i]] = this[i]. */
242  void unmap(const unsigned *map, size_t mapSize, BitVector& dest) const;
243 
244  /** Pack into a char array. */
245  void pack(unsigned char*) const;
246 
247  /* Roman: This is here for debugging */
248  void pack2(unsigned char*) const;
249 
250  // Same as pack but return a string.
251  std::string packToString() const;
252 
253  /** Unpack from a char array. */
254  void unpack(const unsigned char*);
255 
256  /** Make a hexdump string. */
257  void hex(std::ostream&) const;
258  std::string hexstr() const;
259 
260  /** Unpack from a hexdump string.
261  * @returns true on success, false on error. */
262  bool unhex(const char*);
263 
264  // For this method, 'other' should have been run through the copy-constructor already
265  // (unless it was newly created, ie foo.dup(L2Frame(...)), in which case we are screwed anyway)
266  // so the call to makeAlias is redundant.
267  // This only works if other is already an alias.
268  void dup(BitVector other) { assert(!this->getData()); makeAlias(other); assert(this->mStart == other.mStart); }
269  void dup(BitVector &other) { makeAlias(other); assert(this->mStart == other.mStart); }
270 
271 #if 0
272  void operator=(const BitVector& other) {
273  printf("BitVector::operator=\n");
274  assert(0);
275  //this->dup(other);
276  }
277 #endif
278 
279  bool operator==(const BitVector &other) const;
280 
281  /** Copy to dst, not including those indexed in puncture. */
282  void copyPunctured(BitVector &dst, const unsigned *puncture, const size_t plth);
283 
284  /** Index a single bit. */
285  // (pat) Cant have too many ways to do this, I guess.
286  bool bit(size_t index) const
287  {
288  // We put this code in .h for fast inlining.
289  const char *dp = this->begin()+index;
290  assert(dp<this->end());
291  return (*dp) & 0x01;
292  }
293 
294  char& operator[](size_t index)
295  {
296  assert(this->mStart+index<this->mEnd);
297  return this->mStart[index];
298  }
299 
300  const char& operator[](size_t index) const
301  {
302  assert(this->mStart+index<this->mEnd);
303  return this->mStart[index];
304  }
305 
306  /** Set a bit */
307  void settfb(size_t index, int value)
308  {
309  char *dp = this->mStart+index;
310  assert(dp<this->mEnd);
311  *dp = value;
312  }
313 
314  typedef char* iterator;
315  typedef const char* const_iterator;
316 };
317 
318 // (pat) BitVector2 was an intermediate step in fixing BitVector but is no longer needed.
319 #define BitVector2 BitVector
320 
321 
322 std::ostream& operator<<(std::ostream&, const BitVector&);
323 
324 
325 
326 
327 
328 
329 /**
330  The SoftVector class is used to represent a soft-decision signal.
331  Values 0..1 represent probabilities that a bit is "true".
332  */
333 class SoftVector: public Vector<float> {
334 
335  public:
336 
337  /** Build a SoftVector of a given length. */
338  SoftVector(size_t wSize=0):Vector<float>(wSize) {}
339 
340  /** Construct a SoftVector from a C string of "0", "1", and "X". */
341  SoftVector(const char* valString);
342 
343  /** Construct a SoftVector from a BitVector. */
344  SoftVector(const BitVector& source);
345 
346  /**
347  Wrap a SoftVector around a block of floats.
348  The block will be delete[]ed upon desctuction.
349  */
350  SoftVector(float *wData, unsigned length)
351  :Vector<float>(wData,length)
352  {}
353 
354  SoftVector(float* wData, float* wStart, float* wEnd)
355  :Vector<float>(wData,wStart,wEnd)
356  { }
357 
358  /**
359  Casting from a Vector<float>.
360  Note that this is NOT pass-by-reference.
361  */
363  :Vector<float>(source)
364  {}
365 
366 
367  /**@name Casts and overrides of Vector operators. */
368  //@{
369  SoftVector segment(size_t start, size_t span)
370  {
371  float* wStart = mStart + start;
372  float* wEnd = wStart + span;
373  assert(wEnd<=mEnd);
374  return SoftVector(NULL,wStart,wEnd);
375  }
376 
378  { return segment(0,size()); }
379 
380  const SoftVector segment(size_t start, size_t span) const
381  { return (SoftVector)(Vector<float>::segment(start,span)); }
382 
383  SoftVector head(size_t span) { return segment(0,span); }
384  const SoftVector head(size_t span) const { return segment(0,span); }
385  SoftVector tail(size_t start) { return segment(start,size()-start); }
386  const SoftVector tail(size_t start) const { return segment(start,size()-start); }
387  //@}
388 
389  // (pat) How good is the SoftVector in the sense of the bits being solid?
390  // Result of 1 is perfect and 0 means all the bits were 0.5
391  // If plow is non-NULL, also return the lowest energy bit.
392  float getEnergy(float *low=0) const;
393  float getSNR() const;
394 
395  /** Fill with "unknown" values. */
396  void unknown() { fill(0.5F); }
397 
398  /** Return a hard bit value from a given index by slicing. */
399  bool bit(size_t index) const
400  {
401  const float *dp = mStart+index;
402  assert(dp<mEnd);
403  return (*dp)>0.5F;
404  }
405 
406  /** Slice the whole signal into bits. */
407  BitVector sliced() const;
408 
409  /** Copy to dst, adding in 0.5 for those indexed in puncture. */
410  void copyUnPunctured(SoftVector &dst, const unsigned *puncture, const size_t plth);
411 
412  /** Return a soft bit. */
413  float softbit(size_t index) const
414  {
415  const float *dp = mStart+index;
416  assert(dp<mEnd);
417  return *dp;
418  }
419 
420  /** Set a soft bit */
421  void settfb(size_t index, float value)
422  {
423  float *dp = mStart+index;
424  assert(dp<mEnd);
425  *dp = value;
426  }
427 };
428 
429 
430 
431 std::ostream& operator<<(std::ostream&, const SoftVector&);
432 
433 
434 
435 
436 #endif
437 // vim: ts=4 sw=4
void LSB8MSB()
void makeAlias(const VectorBase< char > &other)
Definition: Vector.h:157
BitVector(VectorDataType wData, char *wStart, char *wEnd)
Definition: BitVector.h:127
void operator=(const VectorBase< char > &other)
Definition: Vector.h:283
char * mStart
start of useful data
Definition: Vector.h:133
void writeFieldReversed(size_t &writeIndex, uint64_t value, unsigned length)
SoftVector(Vector< float > source)
Definition: BitVector.h:362
void encoderShift(unsigned inBit)
Definition: BitVector.h:83
void vInit(size_t elements)
Definition: Vector.h:137
unsigned sum() const
void clear()
Definition: BitVector.h:60
SoftVector(float *wData, float *wStart, float *wEnd)
Definition: BitVector.h:354
std::string hexstr() const
void pack(unsigned char *) const
BitVector(const BitVector &other1, const BitVector &other2)
Definition: BitVector.h:146
Definition: Vector.h:318
Definition: BitVector.h:97
char * iterator
Definition: BitVector.h:314
void vConcat(const VectorBase< char > &other1, const VectorBase< char > &other2)
Definition: Vector.h:198
const SoftVector head(size_t span) const
Definition: BitVector.h:384
SoftVector tail(size_t start)
Definition: BitVector.h:385
std::ostream & operator<<(std::ostream &, const BitVector &)
void syndromeShift(unsigned inBit)
Definition: BitVector.h:72
bool operator==(const BitVector &other) const
Definition: BitVector.h:120
void fill(const char &val)
Definition: Vector.h:266
BitVector tail(size_t start)
Definition: BitVector.h:189
uint64_t readFieldReversed(size_t &readIndex, unsigned length) const
void unpack(const unsigned char *)
size_t size() const
Definition: Vector.h:170
char * VectorDataType
Definition: Vector.h:130
VectorDataType mData
allocated data block.
Definition: Vector.h:132
float softbit(size_t index) const
Definition: BitVector.h:413
void invert()
void write1(size_t &writeIndex)
Definition: BitVector.h:231
void dup(BitVector other)
Definition: BitVector.h:268
float getSNR() const
uint64_t state() const
Definition: BitVector.h:64
void writeParityWord(const BitVector &data, BitVector &parityWordTarget, bool invert=true)
void copyPunctured(BitVector &dst, const unsigned *puncture, const size_t plth)
BitVector head(size_t span)
Definition: BitVector.h:188
const char * begin() const
Definition: Vector.h:306
SoftVector alias()
Definition: BitVector.h:377
Parity(uint64_t wCoefficients, unsigned wParitySize, unsigned wCodewordSize)
Definition: BitVector.h:105
Definition: BitVector.h:333
SoftVector segment(size_t start, size_t span)
Definition: BitVector.h:369
std::string packToString() const
BitVector segment(size_t start, size_t span)
Definition: BitVector.h:160
void write0(size_t &writeIndex)
Definition: BitVector.h:230
BitVector(const BitVector &other)
Definition: BitVector.h:130
void dup(BitVector &other)
Definition: BitVector.h:269
char * mEnd
end of useful data + 1
Definition: Vector.h:134
BitVector sliced() const
#define VECTORDEBUG(...)
Definition: Vector.h:40
uint64_t peekFieldReversed(size_t readIndex, unsigned length) const
uint64_t syndrome(Generator &gen) const
const BitVector cloneSegment(size_t start, size_t span) const
Definition: BitVector.h:174
const SoftVector segment(size_t start, size_t span) const
Definition: BitVector.h:380
const char & operator[](size_t index) const
Definition: BitVector.h:300
bool unhex(const char *)
uint64_t peekField(size_t readIndex, unsigned length) const
SoftVector(size_t wSize=0)
Definition: BitVector.h:338
Vector< T > segment(size_t start, size_t span)
Definition: Vector.h:352
void unknown()
Definition: BitVector.h:396
uint64_t readField(size_t &readIndex, unsigned length) const
void pack2(unsigned char *) const
void unmap(const unsigned *map, size_t mapSize, BitVector &dest) const
uint64_t parity(Generator &gen) const
void clone(const VectorBase< char > &other)
Definition: Vector.h:193
unsigned size() const
Definition: BitVector.h:65
void fillField(size_t writeIndex, uint64_t value, unsigned length)
BitVector(size_t len)
Definition: BitVector.h:142
const SoftVector tail(size_t start) const
Definition: BitVector.h:386
void reverse8()
BitVector alias() const
Definition: BitVector.h:184
void fillFieldReversed(size_t writeIndex, uint64_t value, unsigned length)
Generator(uint64_t wCoeff, unsigned wLen)
Definition: BitVector.h:54
Definition: BitVector.h:42
SoftVector(float *wData, unsigned length)
Definition: BitVector.h:350
void zero()
Definition: BitVector.h:198
void hex(std::ostream &) const
BitVector()
Definition: BitVector.h:143
uint64_t syndrome(const BitVector &receivedCodeword)
void settfb(size_t index, float value)
Definition: BitVector.h:421
void writeField(size_t &writeIndex, uint64_t value, unsigned length)
void map(const unsigned *map, size_t mapSize, BitVector &dest) const
bool bit(size_t index) const
Definition: BitVector.h:286
char & operator[](size_t index)
Definition: BitVector.h:294
const char * end() const
Definition: Vector.h:308
float getEnergy(float *low=0) const
void settfb(size_t index, int value)
Definition: BitVector.h:307
const char * const_iterator
Definition: BitVector.h:315
const T * getData() const
Definition: Vector.h:313
unsigned mCodewordSize
Definition: BitVector.h:101
void copyUnPunctured(SoftVector &dst, const unsigned *puncture, const size_t plth)
Definition: Vector.h:122
bool bit(size_t index) const
Definition: BitVector.h:399
SoftVector head(size_t span)
Definition: BitVector.h:383