Bit twiddling functions 
Author Message
 Bit twiddling functions

Quote:

>Another other functions you can think of (that aren't provided by
>the instruction set)?

You might consider IBITS (see a fortran manual) or ZAP, ZAPNOT,
and CMPBGE (see an Alpha architecture manual.)


Mon, 22 Jul 2002 03:00:00 GMT  
 Bit twiddling functions

Quote:

> I am currently working on a "bits" package
> for the HLA Standard Library.
> Thus far I've identified the following
> bit functions that are commonly asked for:

> (1) counting bits.
> (2) reversing bits.
> (3) packing/unpacking nibbles.
> (4) merging two values (every other bit).
> (5) "unmerging" a value (every other bit goes to an alternate location).

> Another other functions you can think of (that aren't provided by
> the instruction set)?

(6) and (7) find first/last set/unset bit is covered adequately by
BSF/BSR, preceeded by a negation if needed.

(4) almost certainly needs a lookup table, the easiest is to use a
256-byte table where the inputs are 4 (a) bits followed by 4 (b) bits,
giving the merged answer, but as you've noted, having lots of tables is
tough.

Almost as fast would be a nibble-wide table:

u32 merge(u16 a, u16 b)
{
  int i;
  u32 res;
  for (i = 0; i < 4; i++) {
    res = (res << 8) + mtab[a >> 12] + (mtab[b >> 12] << 1);
    a <<= 4; b <<= 4;
  }
  return res;

Quote:
}

Unroll this 4 times to avoid the loop and simplify the logic.

Terje

--

Using self-discipline, see http://www.eiffel.com/discipline
"almost all programming can be viewed as an exercise in caching"



Mon, 22 Jul 2002 03:00:00 GMT  
 Bit twiddling functions

Quote:

>Another other functions you can think of (that aren't provided by
>the instruction set)?

You might consider IBITS (see a Fortran manual) or ZAP, ZAPNOT,
and CMPBGE (see an Alpha architecture manual.)


Mon, 22 Jul 2002 03:00:00 GMT  
 Bit twiddling functions

Quote:

> I am currently working on a "bits" package
> for the HLA Standard Library.
> Thus far I've identified the following
> bit functions that are commonly asked for:

> (1) counting bits.
> (2) reversing bits.
> (3) packing/unpacking nibbles.
> (4) merging two values (every other bit).
> (5) "unmerging" a value (every other bit goes to an alternate location).

> Another other functions you can think of (that aren't provided by
> the instruction set)?

(6) and (7) find first/last set/unset bit is covered adequately by
BSF/BSR, preceeded by a negation if needed.

(4) almost certainly needs a lookup table, the easiest is to use a
256-byte table where the inputs are 4 (a) bits followed by 4 (b) bits,
giving the merged answer, but as you've noted, having lots of tables is
tough.

Almost as fast would be a nibble-wide table:

u32 merge(u16 a, u16 b)
{
  int i;
  u32 res;
  for (i = 0; i < 4; i++) {
    res = (res << 8) + mtab[a >> 12] + (mtab[b >> 12] << 1);
    a <<= 4; b <<= 4;
  }
  return res;

Quote:
}

Unroll this 4 times to avoid the loop and simplify the logic.

Terje

--

Using self-discipline, see http://www.eiffel.com/discipline
"almost all programming can be viewed as an exercise in caching"



Mon, 22 Jul 2002 03:00:00 GMT  
 Bit twiddling functions


Quote:

>(1) counting bits.

Lookup table:

lut            db 0
               x=1
               rept 255
               y=0
               z=x
               rept 8
               y=y+(z and 1)
               z=z shr 1
               endm
               db y
               x=x+1
               endm

Quote:
>(2) reversing bits.

For this I already posted a solution like above.

Osmo



Mon, 22 Jul 2002 03:00:00 GMT  
 Bit twiddling functions

I'm thinking interchanging nibbles in a byte, bytes in a word, bit pair in a
nibble, bit in a pair, words in dwords...

Quote:

> I am currently working on a "bits" package
> for the HLA Standard Library.
> Thus far I've identified the following
> bit functions that are commonly asked for:

> (1) counting bits.
> (2) reversing bits.
> (3) packing/unpacking nibbles.
> (4) merging two values (every other bit).
> (5) "unmerging" a value (every other bit goes to an alternate location).

> Another other functions you can think of (that aren't provided by
> the instruction set)?

> Thanks,
> Randy Hyde



Tue, 23 Jul 2002 03:00:00 GMT  
 Bit twiddling functions

Quote:

> (1) counting bits.
> (2) reversing bits.
> (3) packing/unpacking nibbles.
> (4) merging two values (every other bit).
> (5) "unmerging" a value (every other bit goes to an alternate location).

> Another other functions you can think of (that aren't provided by
> the instruction set)?

This is not strictly bit manipulation, but one common thing is to
convert values between endians (byte/word/dword swapping, so to speak).
For example (value 12345678h):

ofs:    0       1       2       3
big:    12      34      56      78
lit:    78      56      34      12
?:      56      78      12      34

The last one I don't know what it is, but I ran into it recently (it's
used in Modbus/TCP PLCs). Of course, there are others than integer
types, too, in IEC-1131.

        AriL
--
Pain and disappointment are inevitable. Misery is optional.
Homepaged at http://www.angelfire.com/or/lukumies



Tue, 23 Jul 2002 03:00:00 GMT  
 Bit twiddling functions

Quote:
>I am currently working on a "bits" package
>for the HLA Standard Library.
>Thus far I've identified the following
>bit functions that are commonly asked for:

>(1) counting bits.
>(2) reversing bits.
>(3) packing/unpacking nibbles.
>(4) merging two values (every other bit).
>(5) "unmerging" a value (every other bit goes to an alternate location).

>Another other functions you can think of (that aren't provided by
>the instruction set)?

>Thanks,
>Randy Hyde

This might already exist elsewhere, but:

Packing/unpacking 16 bit RGB values (5+6+5)
Packing/unpacking 16 bit date values (7+4+5)
Packing/unpacking 16 bit time values (5+6+5)

/GreenGhost



Tue, 23 Jul 2002 03:00:00 GMT  
 Bit twiddling functions


Quote:
> >I am currently working on a "bits" package
> >for the HLA Standard Library.
> >Thus far I've identified the following
> >bit functions that are commonly asked for:

> >(1) counting bits.
> >(2) reversing bits.
> >(3) packing/unpacking nibbles.
> >(4) merging two values (every other bit).
> >(5) "unmerging" a value (every other bit goes to an alternate location).

> >Another other functions you can think of (that aren't provided by
> >the instruction set)?

> >Thanks,
> >Randy Hyde

> This might already exist elsewhere, but:

> Packing/unpacking 16 bit RGB values (5+6+5)
> Packing/unpacking 16 bit date values (7+4+5)
> Packing/unpacking 16 bit time values (5+6+5)

> /GreenGhost

Just a few months ago I revised Chapter One of the Art of
Assembly Language Programming that used a 7+4+5
date format as a packed data example.  I figured after
the Y2K fiasco, supporting such a data type was
politically incorrect :-)

The RGB example is really good though.  Although I
probably won't add this to the library, it will make a great
example for AoA v2.0.
Randy Hyde

- Show quoted text -



Tue, 23 Jul 2002 03:00:00 GMT  
 Bit twiddling functions

Quote:
> Just a few months ago I revised Chapter One of the Art of
> Assembly Language Programming that used a 7+4+5
> date format as a packed data example.  I figured after
> the Y2K fiasco, supporting such a data type was
> politically incorrect :-)

Well, it works until we hit the year 2108. Hopefully this CP/M-based file
system will be obsolete long berfore then... (c:

--
/GreenGhost
---
http://hem.passagen.se/guffa/en
---
kill the spammer to mail me



Sun, 04 Aug 2002 03:00:00 GMT  
 Bit twiddling functions


Quote:

> > Just a few months ago I revised Chapter One of the Art of
> > Assembly Language Programming that used a 7+4+5
> > date format as a packed data example.  I figured after
> > the Y2K fiasco, supporting such a data type was
> > politically incorrect :-)

> Well, it works until we hit the year 2108. Hopefully this CP/M-based file
> system will be obsolete long berfore then... (c:

Famous last words that were muttered concerning various pieces
of software in 1965 :-)

Actually, if you start the year with 2000, it should be good until 2127.
Randy Hyde



Sun, 04 Aug 2002 03:00:00 GMT  
 Bit twiddling functions
Hello Randy,

The DEC PDP-10 had a single instruction JFFO, jump and find first one
bit in a 36 bit word. It was used extensively  for checking the next
available free entry in a table. I remember two tables in the
operating system which used this instruction to find the first free
entry. I used a PC assembly short routine to do the same recently. It
was used to convert the com port speed specification into the divisor
latch bit specification. a sort of log base 2 situation since the
speeds are all multiples of 300 bps. (I treated 150bps as a special
case).

Regards,



Quote:

>I am currently working on a "bits" package
>for the HLA Standard Library.
>Thus far I've identified the following
>bit functions that are commonly asked for:

>(1) counting bits.
>(2) reversing bits.
>(3) packing/unpacking nibbles.
>(4) merging two values (every other bit).
>(5) "unmerging" a value (every other bit goes to an alternate location).

>Another other functions you can think of (that aren't provided by
>the instruction set)?

>Thanks,
>Randy Hyde




Sun, 11 Aug 2002 03:00:00 GMT  
 
 [ 12 post ] 

 Relevant Pages 

1. Bit twiddling functions

2. Bit Twiddling??

3. Bit twiddling on Parallel port

4. UUDECODE - Bit-twiddling in Arexx

5. SIMD-like bit-twiddling on odd-sized quantities

6. New Mathematical bit-twiddle - stage on of a isPerfectSquare()

7. Crazy bit-twiddle algorithms needed!

8. Byte/Bit Twiddling in Ada

9. Bit Twiddling in IBM (LE) COBOL

10. help - bit twiddling anomoly

11. Twiddle binary bit in Cobol?

12. Bit Twiddling

 

 
Powered by phpBB® Forum Software