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