http://d.puremagic.com/issues/show_bug.cgi?id=6829

           Summary: Unsigned rotate standard function in Phobos
           Product: D
           Version: D2
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: enhancement
          Priority: P2
         Component: Phobos
        AssignedTo: nobody@puremagic.com
        ReportedBy: bearophile_hugs@eml.cc


--- Comment #0 from bearophile_hugs@eml.cc 2011-10-18 15:10:25 PDT ---
I think Phobos needs one or two functions to rotate the bits of a unsigned integral value, because DMD is now able to optimize a specific coding pattern to use specific CPU instructions, but it's easy to write the operation in a way that doesn't allow the pattern to be recognized.

A Phobos template function (with a constraint that lets it accept only the right input types) will allow to explicitly ask for this operation to every present and future D compiler, with no risk of mistakes from the programmer.

See also: http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=146892

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=6829



--- Comment #1 from hsteoh@quickfur.ath.cx 2013-07-09 09:05:22 PDT ---
The implementation should probably go into std.bitmanip or core.bitop.

What's the pattern that DMD recognizes for rotate instructions?

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=6829



--- Comment #2 from bearophile_hugs@eml.cc 2013-07-09 10:13:38 PDT ---
(In reply to comment #1)

> What's the pattern that DMD recognizes for rotate instructions?

Walter offers this example of recognizable rotation:


void test236() {
    uint a;
    int shift;
    a = 7;
    shift = 1;
    int r;
    r = (a >> shift) | (a << (int.sizeof * 8 - shift));
    assert(r == 0x8000_0003);
    r = (a << shift) | (a >> (int.sizeof * 8 - shift));
    assert(a == 7);
}

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=6829



--- Comment #3 from hsteoh@quickfur.ath.cx 2013-07-09 12:06:57 PDT ---
Hmph. That doesn't work. Compiling without -O just makes DMD translate it literally into shl/shr followed by or. Compiling with -O computes the values via CTFE, so I changed the code by making a and shift parameters, but DMD still uses shl/shr followed by or, instead of replacing it with rol/ror, as claimed.

So basically, the pattern either isn't there, or isn't working properly.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=6829



--- Comment #4 from hsteoh@quickfur.ath.cx 2013-07-09 12:20:16 PDT ---
In fact, not even gdc -O3 recognizes this pattern.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=6829



--- Comment #5 from bearophile_hugs@eml.cc 2013-07-10 02:11:50 PDT ---
I think this should be a recognizable rotate left function:

    private static uint rol(in uint x, in uint y) pure nothrow {
        return (x << y) | (x >> (32 - y));
    }

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=6829


Iain Buclaw <ibuclaw@ubuntu.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |ibuclaw@ubuntu.com


--- Comment #6 from Iain Buclaw <ibuclaw@ubuntu.com> 2013-07-10 02:38:38 PDT ---
(In reply to comment #5)
> I think this should be a recognizable rotate left function:
> 
>     private static uint rol(in uint x, in uint y) pure nothrow {
>         return (x << y) | (x >> (32 - y));
>     }

It is (in gdc with -O :)

_D3rol3rolFNaNbxkxkZk:
        mov x, %eax
        mov y, %ecx
        rol %cl, %eax
        ret

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=6829



--- Comment #7 from Iain Buclaw <ibuclaw@ubuntu.com> 2013-07-10 02:50:07 PDT ---
(In reply to comment #5)
> I think this should be a recognizable rotate left function:
> 
>     private static uint rol(in uint x, in uint y) pure nothrow {
>         return (x << y) | (x >> (32 - y));
>     }

And likewise for rotate right function:

uint
ror (in uint x, in uint y) pure nothrow
{
  return (x >> y) | (x << (32 - y));
}

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=6829



--- Comment #8 from bearophile_hugs@eml.cc 2013-07-10 03:28:19 PDT ---
(In reply to comment #6)
> (In reply to comment #5)
> > I think this should be a recognizable rotate left function:
> > 
> >     private static uint rol(in uint x, in uint y) pure nothrow {
> >         return (x << y) | (x >> (32 - y));
> >     }
> 
> It is (in gdc with -O :)
> 
> _D3rol3rolFNaNbxkxkZk:
>         mov x, %eax
>         mov y, %ecx
>         rol %cl, %eax
>         ret


Both dmd and ldc2 recognize the patterns:


uint rol(in uint x, in uint y) pure nothrow {
    return (x << y) | (x >> (32 - y));
}

uint ror(in uint x, in uint y) pure nothrow {
  return (x >> y) | (x << (32 - y));
}

extern(C) uint rol2(in uint x, in uint y) pure nothrow {
    return (x << y) | (x >> (32 - y));
}

void main() {}


/*
dmd -O

_D5temp23rolFNaNbxkxkZk:
        push    EAX
        mov EAX,8[ESP]
        mov ECX,[ESP]
        rol EAX,CL
        pop ECX
        ret 4

_D5temp23rorFNaNbxkxkZk:
        push    EAX
        mov EAX,8[ESP]
        mov ECX,[ESP]
        ror EAX,CL
        pop ECX
        ret 4

_rol2 :
        mov EAX,4[ESP]
        mov ECX,8[ESP]
        rol EAX,CL
        ret

----------------

ldmd2 -O -output-s

__D5temp23rolFNaNbxkxkZk:
    movl    4(%esp), %edx
    movb    %al, %cl
    roll    %cl, %edx
    movl    %edx, %eax
    ret $4

__D5temp23rorFNaNbxkxkZk:
    movl    4(%esp), %edx
    movb    %al, %cl
    rorl    %cl, %edx
    movl    %edx, %eax
    ret $4

_rol2:
    movb    8(%esp), %cl
    movl    4(%esp), %eax
    roll    %cl, %eax
    ret

*/

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=6829



--- Comment #9 from Iain Buclaw <ibuclaw@ubuntu.com> 2013-07-10 03:49:49 PDT ---
(In reply to comment #8)
> (In reply to comment #6)
> > (In reply to comment #5)
> > > I think this should be a recognizable rotate left function:
> > > 
> > >     private static uint rol(in uint x, in uint y) pure nothrow {
> > >         return (x << y) | (x >> (32 - y));
> > >     }
> > 
> > It is (in gdc with -O :)
> > 
> > _D3rol3rolFNaNbxkxkZk:
> >         mov x, %eax
> >         mov y, %ecx
> >         rol %cl, %eax
> >         ret
> 
> 
> Both dmd and ldc2 recognize the patterns:
> 

Excellent, so could put these as templates then. :)

T rol (T)(in T x, in uint y) pure nothrow
{
  return cast(T)((x << y) | (x >> ((T.sizeof * 8) - y)));
}

T ror (T)(in T x, in uint y) pure nothrow
{
  return cast(T)((x >> y) | (x << ((T.sizeof * 8) - y)));
}


// Tests to check for assembly output.
extern ubyte xb;
extern ushort xs;
extern uint xi;
extern ulong xl;

extern uint yi;

{
  rol (xb, yi);   // rolb
  ror (xb, yi);   // rorb

  rol (xs, yi);   // rolw
  ror (xs, yi);   // rorw

  rol (xi, yi);   // roll
  ror (xi, yi);   // rorl

  rol (xl, yi);   // version(X86_64) rolq
  ror (xl, yi);   // version(X86_64) rorq
}

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------