Author 
Message 
James Van Buskir #1 / 12

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 


Terje Mathise #2 / 12

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 256byte 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 nibblewide 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 selfdiscipline, 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 


James Van Buskir #3 / 12

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 


Terje Mathise #4 / 12

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 256byte 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 nibblewide 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 selfdiscipline, 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 


Osmo Ronkan #5 / 12

Bit twiddling functions
Quote: 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 


Groma #6 / 12

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 


Ari Lukumie #7 / 12

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 IEC1131. 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 


G?ran Andersso #8 / 12

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 


Randall Hyd #9 / 12

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

Tue, 23 Jul 2002 03:00:00 GMT 


G?ran Andersso #10 / 12

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/Mbased 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 


Randall Hyd #11 / 12

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/Mbased 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 


Rolie Baldo #12 / 12

Bit twiddling functions
Hello Randy, The DEC PDP10 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 

