On Mon, Apr 23, 2012 at 11:03 AM, Nowlan, Sean <sean.now...@gtri.gatech.edu> 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: trond...@trondeau.com [trond...@trondeau.com] on behalf of Tom Rondeau > [t...@trondeau.com] > Sent: Monday, April 23, 2012 10:12 AM > To: Nowlan, Sean > Cc: Nick Foster; Discuss-gnuradio@gnu.org > Subject: Re: [Discuss-gnuradio] digital_correlate_access_code_bb > > On Thu, Apr 19, 2012 at 11:35 AM, Nowlan, Sean > <sean.now...@gtri.gatech.edu> 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: trond...@trondeau.com [mailto:trond...@trondeau.com] On Behalf Of Tom >> Rondeau >> Sent: Thursday, April 19, 2012 10:24 AM >> To: Nowlan, Sean >> Cc: Nick Foster; Discuss-gnuradio@gnu.org >> Subject: Re: [Discuss-gnuradio] digital_correlate_access_code_bb >> >> On Sun, Apr 15, 2012 at 6:30 PM, Nowlan, Sean <sean.now...@gtri.gatech.edu> >> 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: discuss-gnuradio-bounces+sean.nowlan=gtri.gatech....@gnu.org >>> [mailto:discuss-gnuradio-bounces+sean.nowlan=gtri.gatech....@gnu.org] >>> On Behalf Of Tom Rondeau >>> Sent: Monday, April 09, 2012 5:23 PM >>> To: Nick Foster >>> Cc: Discuss-gnuradio@gnu.org >>> Subject: Re: [Discuss-gnuradio] digital_correlate_access_code_bb >>> >>> On Mon, Apr 9, 2012 at 2:02 PM, Nick Foster <n...@ettus.com> wrote: >>>> On Mon, Apr 9, 2012 at 10:48 AM, Marcus D. Leech <mle...@ripnet.com> wrote: >>>>> >>>>> On 04/09/2012 01:38 PM, Tom Rondeau wrote: >>>>>> >>>>>> On Sat, Apr 7, 2012 at 10:12 PM, Marcus D. Leech<mle...@ripnet.com> >>>>>> 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 >>> Discuss-gnuradio@gnu.org >>> https://lists.gnu.org/mailman/listinfo/discuss-gnuradio _______________________________________________ Discuss-gnuradio mailing list Discuss-gnuradio@gnu.org https://lists.gnu.org/mailman/listinfo/discuss-gnuradio
