Re: Bit Interleaving, Instruction Set Support for

Message-ID	<4E66669D.5010005@SPAM.comp-arch.net> (permalink)
Date	2011-09-06 11:29 -0700
From	"Andy \"Krazy\" Glew" <andy@SPAM.comp-arch.net>
Organization	comp-arch.net
Newsgroups	comp.arch
Subject	Re: Bit Interleaving, Instruction Set Support for
References	(1 earlier) <4E659C6E.D55BEE2E@sonic.net> <4E65A0CE.8060305@SPAM.comp-arch.net> <9clo7eFsjmU1@mid.individual.net> <7zwrdmaxqg.fsf@ask.diku.dk> <inchj8-enj.ln1@ntp6.tmsw.no>

Show all headers | View raw

On 9/6/2011 4:28 AM, Terje Mathisen wrote:
> Torben Ægidius Mogensen wrote:
>> A more general form of zip would be an operation that takes two
>> operands: A bitmask and bit vector. The bits in the bit vector (from
>> one end) would be positioned at the 1-bits in the bitmask.
>>
>> For example, if the bitmask is 101101 and the bitvector has bits abcdef,
>> then the result would be c0de0f for a right-zip and a0bc0e for a
>> left-zip.
>>
>> Any m:n zip can be made using two of the above and a bitwise or --
>> providing the bit masks are available in registers.
>>
>> The inverse operation would take the bits at the positions indicated by
>> the bitmask and compress them to one end.
>>
>> I'm thinking that both operations could be implemented by a relatively
>> simple modification of a multiplier.
>
> Indeed.
>
> Aren't you more or less back at Andy's desired BMM now?
>
> Terje

No, Torben's zip and unzip (which I was also thinking of, but had not 
gotten around to writing down as an invention disclsoure - Torben beat 
me fair and  square) is a special case of a bit permutation.

For that matter, BMM (Bit Matrix Multiply) is more general than a bit 
permutation, since any bit in the output can be a function of more than 
one bit of the input.

The most general bit permutation of N bit operands takes as an argument 
a vector of N indexes each of ceil(log2(N)) width.  This allows 
replication of bits.  Or, equivalently, a BMM matrix with only a single 
1 in any row and column.

Torben's zip and unzip correspond to having an index vector that is 
constrained to be monotonic - bit numbers to be extracted or expanded 
can only be increasing (or decreasing). Less  geberal, but good enough 
for many purposes.

Thread

Bit Interleaving, Instruction Set Support for "Andy \"Krazy\" Glew" <andy@SPAM.comp-arch.net> - 2011-09-05 16:23 -0700
  Re: Bit Interleaving, Instruction Set Support for Mark Thorson <nospam@sonic.net> - 2011-09-05 20:07 -0800
    Re: Bit Interleaving, Instruction Set Support for "Andy \"Krazy\" Glew" <andy@SPAM.comp-arch.net> - 2011-09-05 21:25 -0700
      Re: Bit Interleaving, Instruction Set Support for Andrew Reilly <areilly---@bigpond.net.au> - 2011-09-06 05:09 +0000
        Re: Bit Interleaving, Instruction Set Support for torbenm@diku.dk (Torben Ægidius Mogensen) - 2011-09-06 10:20 +0200
          Re: Bit Interleaving, Instruction Set Support for Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-09-06 13:28 +0200
            Re: Bit Interleaving, Instruction Set Support for "Andy \"Krazy\" Glew" <andy@SPAM.comp-arch.net> - 2011-09-06 11:29 -0700
          Re: Bit Interleaving, Instruction Set Support for "Andy \"Krazy\" Glew" <andy@SPAM.comp-arch.net> - 2011-09-06 11:21 -0700
          Re: Bit Interleaving, Instruction Set Support for timcaffrey@aol.com (Tim McCaffrey) - 2011-09-09 19:10 +0000
            Re: Bit Interleaving, Instruction Set Support for "Andy \"Krazy\" Glew" <andy@SPAM.comp-arch.net> - 2011-09-10 12:50 -0700
            Re: Bit Interleaving, Instruction Set Support for torbenm@diku.dk (Torben Ægidius Mogensen) - 2011-09-13 10:34 +0200
      Re: Bit Interleaving, Instruction Set Support for Mark Thorson <nospam@sonic.net> - 2011-09-07 12:43 -0800
        Re: Bit Interleaving, Instruction Set Support for "Andy \"Krazy\" Glew" <andy@SPAM.comp-arch.net> - 2011-09-10 12:27 -0700
          Re: Bit Interleaving, Instruction Set Support for "Andy \"Krazy\" Glew" <andy@SPAM.comp-arch.net> - 2011-09-11 21:05 -0700
        Re: Bit Interleaving, Instruction Set Support for EricP <ThatWouldBeTelling@thevillage.com> - 2011-09-10 16:57 -0400
          Re: Bit Interleaving, Instruction Set Support for George Neuner <gneuner2@comcast.net> - 2011-09-10 23:14 -0400
            Re: Bit Interleaving, Instruction Set Support for nmm1@cam.ac.uk - 2011-09-11 10:16 +0100
              Re: Bit Interleaving, Instruction Set Support for EricP <ThatWouldBeTelling@thevillage.com> - 2011-09-11 12:30 -0400
    Re: Bit Interleaving, Instruction Set Support for Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-09-06 13:25 +0200
  Re: Bit Interleaving, Instruction Set Support for Quadibloc <jsavard@ecn.ab.ca> - 2011-09-05 21:02 -0700
  Re: Bit Interleaving, Instruction Set Support for Piotr Wyderski <peter.pan@neverland.mil> - 2011-09-06 14:12 +0200
    Re: Bit Interleaving, Instruction Set Support for Bakul Shah <usenet@bitblocks.com> - 2011-09-06 11:49 -0700
      Re: Bit Interleaving, Instruction Set Support for Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-09-07 11:18 +0200
        Re: Bit Interleaving, Instruction Set Support for Thomas Womack <twomack@chiark.greenend.org.uk> - 2011-09-07 10:54 +0100
          Re: Bit Interleaving, Instruction Set Support for Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-09-07 20:27 +0200
  Re: Bit Interleaving, Instruction Set Support for MitchAlsup <MitchAlsup@aol.com> - 2011-09-07 12:23 -0700

csiph-web