Re: [Discuss-gnuradio] digital_correlate_access_code_bb

[Tom Rondeau]

On Mon, Apr 23, 2012 at 11:03 AM, Nowlan, Sean
<address@hidden> wrote:
> 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

The boost::dynamic_bitset looks kind of nice to represent this
structure. The initialization from a string is convenient, too. I'm
also not opposed to having hex values specified as "0x...". If
checking for "0x" fails, we assume it's binary and load it as is;
otherwise, we convert from hex.

I'd like to see the speed of this container, though, compared to the
current way it's handled

Tom


> ________________________________________
> 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