Path: csiph.com!x330-a1.tempe.blueboxinc.net!newsfeed.hal-mli.net!feeder3.hal-mli.net!news.glorb.com!news-xfer.nntp.sonic.net!posts.news.sonic.net!nnrp1.nntp.sonic.net!not-for-mail Message-ID: <4E666B47.9020009@bitblocks.com> Date: Tue, 06 Sep 2011 11:49:43 -0700 From: Bakul Shah User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.7; rv:6.0) Gecko/20110812 Thunderbird/6.0 MIME-Version: 1.0 Newsgroups: comp.arch Subject: Re: Bit Interleaving, Instruction Set Support for References: <4E655A0D.40509@SPAM.comp-arch.net> In-Reply-To: Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Lines: 32 Organization: Sonic.Net NNTP-Posting-Date: 06 Sep 2011 18:49:43 GMT NNTP-Posting-Host: bb959be4.news.sonic.net X-Trace: DXC=AZO3FMnd86baRW0U39Kc?dm4K\QM1CV^`1OYf0H`?;Xa_1@R82HelWkU[Zjk:d[l;fTSP]W\\?hRh X-Complaints-To: abuse@sonic.net Xref: x330-a1.tempe.blueboxinc.net comp.arch:3506 On 9/6/11 5:12 AM, Piotr Wyderski wrote: > Andy "Krazy" Glew wrote: > > Thanks for starting the thread, as bit operations are of vital importance in my low-level > algorithms. Apart the operations > mentioned previously, I would like to have the following instruction: > > bit_chunk_check(x, n): > > where x is an unsigned integer and n is a positive integer. > The instruction checks whether x contains a chunk of n consecutive > set bits and returns an index of the first/last/some such a chunk. > It is a generalization of bsf/bsr. Kind of a run-length-encoding. Would be neat if you could deal with a bunch of bits. The result would be a count of alternating zeroes and ones. So for example: value result (four 8-bit values in decimal) 0 32,0,0,0 ; 32 zeroes, 0 ones -1 0,32,0,0 ; 0 zeroes, 32 ones 257 23,1,7,1 ; 13 27,1,1,1 ; actual encoding: 27,1,1,1,1,1 but only the first 4 can be returned Also need a clz (clear leading zeroes) to pick up for example the last two runs of 13 in the next round. Very useful in array programming. A == B will yield a bitmap where A[i] == B[i]. To then pick up those values from A or B (or another related array) you need indices of places where A & B match. Probably not doable in one cycle. But even knocking off one run of zeroes and one of ones can be handy.