Download Reference Manual
The Developer's Library for D
About Wiki Forums Source Search Contact

Ticket #172 (closed enhancement: fixed)

Opened 17 years ago

Last modified 17 years ago

Add bit manipulation functions

Reported by: Don Clugston Assigned to: sean
Priority: normal Milestone: 0.99 RC3
Component: Core Functionality Version:
Keywords: Cc:

Description (Last modified by sean)

There are several low-level bit-manipulation operations which it would be great to provide access to. Most are single asm instructions on some CPUs, so they are prime candiates to become intrinsics some day -- lets get ready.

- Asm implementations of rotates without carry. - popcount (see below) - possibly import bsf, bsr from std.intrinsic. - dovetail, undovetail for splitting odd and even bits of a short, into seperate bytes. - reverse bits in a byte (see below)

Possible name: tango.core.BitManip?


/**
 *  Calculates the number of set bits in a 32-bit integer.
 *
 */
int bitcount(uint x)
{
    // Avoid branches, and the potential for cache misses which
    // could be incurred with a table lookup.

    // We need to mask alternate bits to prevent the
    // sum from overflowing.
    // add neighbouring bits. Each bit is 0 or 1.
    x = x - ((x>>1) & 0x5555_5555);
    // now each two bits of x is a number 00,01 or 10.
    // now add neighbouring pairs
    x = ((x&0xCCCC_CCCC)>>2) + (x&0x3333_3333);
    // now each nibble holds 0000-0100. Adding them won't
    // overflow any more, so we don't need to mask any more

    // Now add the nibbles, then the bytes, then the words
    // We still need to mask to prevent double-counting.
    // Note that if we used a rotate instead of a shift, we
    // wouldn't need the masks, and could just divide the sum
    // by 8 to account for the double-counting.
    // On some CPUs, it may be faster to perform a multiply.

    x += (x>>4);
    x &= 0x0F0F_0F0F;
    x += (x>>8);
    x &= 0x00FF_00FF;
    x += (x>>16);
    x &= 0xFFFF;
    return x;
}

unittest {
  assert(bitcount(0)==0);
  assert(bitcount(7)==3);
  assert(bitcount(0xAA)==4);
  assert(bitcount(0x8421_1248)==8);
  assert(bitcount(0xFFFF_FFFF)==32);
  assert(bitcount(0xCCCC_CCCC)==16);
  assert(bitcount(0x7777_7777)==24);
}

/******************************
 * Reverses the order of bits in an integer
 */
uint bitReverse( uint x ){

    version(D_InlineAsm_X86) {
  asm {
    // Author: Tiago Gasiba.
    mov EDX, EAX;
    shr EAX, 1;
    and EDX, 0x5555_5555;
    and EAX, 0x5555_5555;
    shl EDX, 1;
    or EAX, EDX;
    mov EDX, EAX;
    shr EAX, 2;
    and EDX, 0x3333_3333;
    and EAX, 0x3333_3333;
    shl EDX, 2;
    or EAX, EDX;
    mov EDX, EAX;
    shr EAX, 4;
    and EDX, 0x0f0f_0f0f;
    and EAX, 0x0f0f_0f0f;
    shl EDX, 4;
    or EAX, EDX;
    bswap EAX;
   }
} else {
    // swap odd and even bits
    x = ((x >> 1) & 0x5555_5555) | ((x & 0x5555_5555) << 1);
    // swap consecutive pairs
    x = ((x >> 2) & 0x3333_3333) | ((x & 0x3333_3333) << 2);
    // swap nibbles
    x = ((x >> 4) & 0x0F0F_0F0F) | ((x & 0x0F0F_0F0F) << 4);
    // swap bytes
    x = ((x >> 8) & 0x00FF_00FF) | ((x & 0x00FF_00FF) << 8);
    // swap 2-byte long pairs
    x = ( x >> 16              ) | ( x               << 16);
    return x;

}

unittest {
    assert(bitReverse(0x8000_0100)==0x0080_0001);
}

Change History

02/15/07 07:23:45 changed by sean

  • description changed.

03/04/07 19:27:58 changed by kris

  • priority changed from minor to normal.
  • version deleted.
  • milestone changed from 1.0 to 0.97 RC 1.

04/13/07 20:49:01 changed by sean

  • status changed from new to assigned.
  • milestone changed from 0.97 RC 1 to 0.98 RC 2.

We'll need to evaluate where to put these routines. I'm pushing this ticket off to the next release to give us time to do so.

05/05/07 06:05:15 changed by sean

  • milestone changed from 0.98 RC 2 to 0.99 RC3.

I'm pushing this one off again. It needs some discussion, and no one has pressed for it.

05/31/07 18:37:14 changed by sean

These seem most appropriate in tango.core.Intrinsic, even though they aren't actually intrinsics. It almost seems weird there aren't ASM instructions to directly perform these two operations.

06/01/07 07:56:32 changed by Don Clugston

These seem most appropriate in tango.core.Intrinsic, even though they aren't actually intrinsics. It almost seems weird there aren't ASM instructions to directly perform these two operations.

They definitely belong in the same place as the bswap(), bsr() and bsf(), btc() instrinsics. IMHO, the fact that those functions are compiler instrinsic shouldn't really be reflected in the module name (they're not intrinsic on some CPUs). I don't think they've got anything in common with the inp() and outp() intrinsics, which AFAIK are x86 specific. But I don't think we can do much about that. bitcount() is an asm instruction on many CPUs, and was added to SSE4, so it has a legitimate claim to being intrinsic.

Putting these functions into core would allow some refactoring of the cipher codes. (digest.Digest has rotateLeft() which should also be in Intrinsic, since it's a single machine instruction).

06/03/07 16:37:30 changed by sean

Hm, so perhaps core.Intrinsic should be renamed to core.BitManip? or some such? I agree that Intrinsic isn't very useful, particularly since DMD has intrinsics for other functions as well (some in std.math IIRC). What's another good name... BitOp? perhaps?

06/04/07 08:03:57 changed by Don Clugston

Initially I called it BitOperation?, then decided I liked BitManip? better. BitOp? is ok too. Changing the existing name only slightly: BitIntrinsic?, title "Bit manipulation functions, which are intrinsic machine instructions on most platforms". BitTwiddle? is obscure and sounds a bit silly. That's all the ideas I have. But I think _something_ beginning with 'Bit' is the way to go.

06/26/07 17:59:00 changed by sean

  • status changed from assigned to closed.
  • resolution set to fixed.

Fixed in changeset [2356].

I'm still not sure about the module name "BitManip?" but this change has been lingering on my HD for too long. If the name changes it can do so later.

06/26/07 18:27:47 changed by kris

  • status changed from closed to reopened.
  • resolution deleted.

I'm not sure about it either :)

In particular, there is a notable distinction between intrinsic functions and these ones: the former are supported directly by the compiler whilst the latter are not. Thus, IMO, they barely belong in the same module. I'd be tempted to leave intrinsic "as is" for now, and add these new "intrinsic hopefuls" in a distinct module.

If the notion really is to push these (to Walter) as intrinsic candidates, then the module name should be left alone ... if these are representative of intrinsic functions, then the module should probably be called Intrinsic rather than something else

06/28/07 09:49:07 changed by Don Clugston

In particular, there is a notable distinction between intrinsic functions and these ones: the former are supported directly by the compiler whilst the latter are not. Thus, IMO, they barely belong in the same module. I'd be tempted to leave intrinsic "as is" for now, and add these new "intrinsic hopefuls" in a distinct module.

Surely that's a QOI detail? I think it's completely irrelevant which functions are compiler intrinsics. Who cares whether math.Math.sin() is an intrinsic? It's quite ridiculous that Phobos exposes that detail in user code.

If the notion really is to push these (to Walter) as intrinsic candidates, then the module name should be left alone ... if these are representative of intrinsic functions, then the module should probably be called Intrinsic rather than something else.

This wouldn't make sense. Some of the functions in std.intrinsic will not be intrinsics on all platforms. bitcount() WILL be an intrinsic on AMD64 platforms, but CANNOT be intrinsic on x86. Note that rotation *is* an intrinsic on GDC!

06/28/07 16:04:38 changed by sean

I agree with Don. GDC doesn't have any of the intrinsic routines as actual intrinsics, and DMD has some of the routines in std.math as intrinsics (sqrt comes to mind). As Don said, I think that's really just a QOI issue more than a design issue. As for naming, I'd been meaning to check whether x86 or AMD64 had a routine for counting bits--seems they would. What's the name of the call? Given the other intrinsics, it seems the pattern is to use the instruction name for the function name. This is arguably a bad idea, since the names aren't terribly meaningful, but it is more consistent...

06/28/07 23:38:38 changed by kris

All good points, which I can't argue with.

What's the story with the location of intrinsic.di? Doesn't the compiler expect it in a specific location? I thought we put it in tango/std/ because the compiler insisted upon that location? If so, what happens when you change the module name to BitManip?? (that's a terrible name, btw :)

Just noticed stdarg.di in there also O_O Does GDC require that file in there?

06/29/07 00:19:44 changed by sean

The compiler requires those routines to be declared in std.intrinsic. It actually doesn't matter what we call the Tango module so long as it publicly imports std.intrinsic (you'll notice the decls for them in BitManip? are in a version(DDoc) block). So the whole thing is invisible to the user unless there's a symbol collision, in which case they'd need to use "std.intrinsic.bswap" or whatever to disambiguate. Hopefully, those function names are odd enough that this will never be an issue. Well, that or we need to convince compiler writers to map their intrinsics to the Tango location as well.

(follow-up: ↓ 16 ) 06/29/07 07:17:19 changed by Don Clugston

As for naming, I'd been meaning to check whether x86 or AMD64 had a routine for counting bits--seems they would. What's the name of the call?

It's only in SSE4. the instruction is POPCNT. AMD's K10 has it as well. On some mainframe from the early 80's, it was called POPC (confusing -- looks like 'pop register C'), it was important for military cryptography. Quite a few CPUs have it, but not x86-32 or PPC.

Given the other intrinsics, it seems the pattern is to use the instruction name for the function name. This is arguably a bad idea, since the names aren't terribly meaningful.

This might help:

http://en.wikipedia.org/wiki/Hamming_weight

BTW, I once found a newgroup post where Walter said that he implemented bsf and bsr as intrinsics because he needed them inside the compiler backend somewhere. It was a fairly arbitrary selection.

BitManip??? (that's a terrible name, btw :)

Got any better ideas? Do you like core.BitOperation? or core.BitOp? better? Or core.Bits? Or it could be a name beginning with 'Byte'.

core.ByteSwap? is possibly related. They _might_ belong together. At least, I imagine there are related functions that could go in the same file as the byteswap functions (core.ByteSwap? is an amazingly specific name compared to core.Array).

(in reply to: ↑ 15 ) 06/29/07 07:39:18 changed by kris

Replying to Don Clugston:

BitManip? (that's a terrible name, btw :)

Got any better ideas? Do you like core.BitOperation or core.BitOp better?

BitOp seems more palatable, but not right somehow. Erm ... Hrm. I don't have anything better to offer. Perhaps core.BitFlip, but that's no great improvement.

How about core.Twiddle or core.Swizzle :)

06/29/07 08:01:05 changed by Don Clugston

core.Bitwise ?

07/03/07 03:07:30 changed by sean

I've been giving the module name issue some more thought, and there may actually be some value in the original name, "Intrinsic". While it's certainly a QOI issue whether or not a routine is intrinsic, the name is meaningful in that it tells me that routines in the module are likely to be very efficient and low-level. It also helps to explain the ASM-like function names. This seems to have some value to others as well, as Kris seems to prefer the old name as well :-)

I think I'm going to change the name back for now until it can be discussed further, but the new functions will remain. "bitswap" will likely be renamed to "popcnt" to be consistent with the other intrinsic names.

07/10/07 18:08:11 changed by sean

  • status changed from reopened to closed.
  • resolution set to fixed.

Renamed in [2438].

I'm going to leave BitManip? as BitManip? for now. Closing the ticket so it isn't seen as a blocker for the next release.