Re: [Discuss-gnuradio] digital_correlate_access_code_bb

[Nowlan, Sean]

It was easiest for me to save on space of representing values by using 
std::string, converting hex (in ASCII from command line) to binary and dumping 
into std::vector<unsigned char>. It's kind of hack-ish but it works. I think we 
should give some thought to std::bitset or boost::dynamic_bitset. They both can 
be initialized from std::string, so passing a string of 1s and 0s as input 
makes sense. They both define bit operations and operator[] access to 
individual bits, which could be useful. The main difference between them is 
that instances of std::bitset require fixed size, specified at compile-time 
through a template parameter std::bitset<N>. Type boost::dynamic_bitset, 
however can be dynamically resized, which is useful for initialization at 
runtime. One problem is that they are not true STL containers and iterators are 
not defined for them. This is due to using a proxy reference to access/modify 
bits instead of true pointers or references. The advantage to bitset and 
dynamic_bitset is storage space savings, and perhaps less awkward semantics for 
data manipulation, not necessarily speed.

Sean
________________________________________
From: address@hidden address@hidden on behalf of Tom Rondeau address@hidden
Sent: Monday, April 23, 2012 10:12 AM
To: Nowlan, Sean
Cc: Nick Foster; address@hidden
Subject: Re: [Discuss-gnuradio] digital_correlate_access_code_bb

On Thu, Apr 19, 2012 at 11:35 AM, Nowlan, Sean
<address@hidden> wrote:
> Good question. I've dealt with this in some of my work too. I needed to pass 
> a spread code through python to a spreading block, and at times I needed 
> codes longer than 64 bits. I ended up passing hexadecimal numbers (stored in 
> a string) and then converting ascii to binary with a helper function called 
> from the constructor in the spreading block. Upside: short length to 
> represent a long sequence as a command line argument; downside: needed to 
> pass a second parameter specifying the width of the spread code, since it's 
> ambiguous how many bits are valid in the most significant hex digit.
>
> Is there another type of container that makes sense for this? I think we 
> might be stuck with string. Another way is to store codes of arbitrary length 
> in a file and pass the filename as an argument to the block constructor. 
> Finally, there's std::bitset (or boost::dynamic_bitset) but I haven't looked 
> into how SWIG and Python handle those.


Sean,
I was hoping we'd get more input on this. In general, I like the idea
of using hex instead of binary; more compact representation.

I also realized that my criticisms of Marcus' patch were unfounded. I
thought that loop was in the work function, but it's just an
initialization thing. I don't care about a few added branches or
cycles for one-time-work like that. But I'd still like to see us come
to some conclusion about the right way to handle this for these and
any future cases. Especially, what do we want to do if we have a code
that's longer than 64 bits? At std::vectors the best way of handling
this?

Thanks,
Tom


> -----Original Message-----
> From: address@hidden [mailto:address@hidden On Behalf Of Tom Rondeau
> Sent: Thursday, April 19, 2012 10:24 AM
> To: Nowlan, Sean
> Cc: Nick Foster; address@hidden
> Subject: Re: [Discuss-gnuradio] digital_correlate_access_code_bb
>
> On Sun, Apr 15, 2012 at 6:30 PM, Nowlan, Sean <address@hidden> wrote:
>> Sorry to bump this... It appears the set_access_code method only occurs once 
>>  from within the constructor code. I'm not arguing that the old method isn't 
>> faster, but it's functionally imprecise and the overhead of the if-else 
>> statement isn't huge over the life of the object instance. If a 
>> time-variable access code scheme were implemented, I could see it adding up, 
>> though. But set_access_code isn't even SWIGged up as a public method, so I 
>> assume there hasn't been demand for such a use case...
>>
>> Sean
>
> No, not really much demand. But I would suggest we relook at this not from 
> the processing standpoint but from the definition of the access code.
>
> It's inputted as a string right now and then converted to a 64-bit value. 
> Presumably, the string definition was used to make arbitrary length access 
> codes possible and easily passed through SWIG. Could we instead define the 
> access code another way that allows us to fix both the representation and 
> processing issues?
>
> Tom
>
>
>> -----Original Message-----
>> From: address@hidden
>> [mailto:address@hidden
>> On Behalf Of Tom Rondeau
>> Sent: Monday, April 09, 2012 5:23 PM
>> To: Nick Foster
>> Cc: address@hidden
>> Subject: Re: [Discuss-gnuradio] digital_correlate_access_code_bb
>>
>> On Mon, Apr 9, 2012 at 2:02 PM, Nick Foster <address@hidden> wrote:
>>> On Mon, Apr 9, 2012 at 10:48 AM, Marcus D. Leech <address@hidden> wrote:
>>>>
>>>> On 04/09/2012 01:38 PM, Tom Rondeau wrote:
>>>>>
>>>>> On Sat, Apr 7, 2012 at 10:12 PM, Marcus D. Leech<address@hidden>
>>>>>  wrote:
>>>>>>
>>>>>> Just looking at this function:
>>>>>>
>>>>>> correlate_access_code_bb
>>>>>>
>>>>>> In the method set_access_code, it takes a string.  Which should be
>>>>>> ASCII '1'
>>>>>> and '0' characters to represent the binary sequence being
>>>>>>  correlated against.
>>>>>>
>>>>>> Here's a little beauty of a code snippet:
>>>>>>
>>>>>>  d_access_code = 0;
>>>>>>  for (unsigned i=0; i<  64; i++){
>>>>>>    d_access_code<<= 1;
>>>>>>    if (i<  len)
>>>>>>      d_access_code |= access_code[i]&  1;    // look at LSB only
>>>>>>  }
>>>>>>
>>>>>> This relies on the fact that ASCII '1' and '0' happen to have
>>>>>> low-order bits of the right "flavour".  This is insanely dirty and
>>>>>> gross and I can't
>>>>>>  believe we let this nonsense in the code base.
>>>>>>
>>>>>> There's no reason not to do the right thing here.
>>>>>>
>>>>>>
>>>>>> --
>>>>>> Marcus Leech
>>>>>> Principal Investigator
>>>>>> Shirleys Bay Radio Astronomy Consortium http://www.sbrac.org
>>>>>
>>>>>
>>>>> Want to submit a patch?
>>>>>
>>>>> Tom
>>>>>
>>>>>
>>>> Attached.
>>>
>>>
>>> While you're patching correlate_access_code_bb, please patch
>>> correlate_access_code_tag_bb with the attached patch.
>>>
>>> --n
>>
>> So my guess is that the use of the binary & operator is to avoid the need 
>> for an if/if else/else branching check. It was most likely done for 
>> efficiency. So while this patch might be the "right" way to do it from a 
>> code perspective, it could result in slower code (on certain machines that 
>> don't handle branch prediction well). It does make assumptions about the 
>> correctness of the access code, though.
>>
>> Tom
>>
>> _______________________________________________
>> Discuss-gnuradio mailing list
>> address@hidden
>> https://lists.gnu.org/mailman/listinfo/discuss-gnuradio