D

[Jarno A Wuolijoki]

Well, I didn't state the domain of the function (... m should be in the
range 0 to 31 inclusive for this 32 bit left rotate). Replacing the ms
with (m & 0x1f) and the "unsigned" with "unsigned long" is easy enough,
though, if that's what you want.

Problem: while gcc can indeed rewrite x>>n|x<<32-n as a rotate, it doesn't
remove the &31 in x>>(n&31).

I mean really: play nice and add the &31 there making it portable just
to see it actually performs the no-op. sigh.

BTW, ITYM 1 to 31 inclusive.

 

[Arthur J. O'Dwyer]

If I want a platform specific rotate then I'll just write:

int rot(int,char);
#pragma aux rot = "rol eax, cl" parm [eax] [cl] value [eax];

thank you very much.

But this does not work at all -- I wanted a 24-bit rotate!

More likely 28. ;-)

Seriously, has no one yet noticed that "rotate" is inherently a
three-input operation? We have the bit mask to rotate, the number
of bits in that bit mask, and the number of bits by which the rotate
should happen.

Of course, all this "rotate" stuff is a red herring; the *correct*
primitive is "funnel shift", which is a *four*-input operation
(left side, right side, number of bits in each side, and position
of selector). Rotation is obtained by making the left and right
sides identical, and barrel-shifting is obtained by making one of
"left side" or "right side" all-zero-bits.

Your ill attempt at humor is [a non sequitur].

Not really humor. More like a technical description of the semantics
of the family of operations you've been calling "shift" and "rotate."
It's perfectly true that x86-style fixed-width rotate instructions
are fairly useless, compared to the "funnel shift" operation Chris
describes. Of course, with more than two inputs it's hard to make
this operation a primitive "operator" in C; that's why you don't want
to think about it. I still haven't figured out why you really *want*
a (or several) "rotate operator(s)" when an inline function is just
as fast, and can take the multiple inputs it needs to do the job right,
plus specializations for values of 'n' or 'b' that are easy to do
on whatever architecture you're targeting.

Ordinary rotates happen a lot.

Define "ordinary." Do you perhaps mean "32-bit rotates, with the
right-hand operator truncated modulo 32 and stored in the CL register"?
(--Now, that *was* an ill attempt at humor.)

Name me one feistel crypto algorithm that *DOESN'T* use a rotate. DES,
BlowFish, MD5, they *all* use rotate.

Blowfish does not use a rotate.
http://www.counterpane.com/bfdobsoyl.html

DES uses a 28-bit rotate.
http://www.aci.net/kalliste/des.htm

MD5 actually does use a 32-bit rotate. Congrats!
http://www.ietf.org/rfc/rfc1321.txt

[I am not a cryptography expert.]
-Arthur

 

[Paul Hsieh]

(e-mail address removed) says...

Problem: while gcc can indeed rewrite x>>n|x<<32-n as a rotate, it doesn't
remove the &31 in x>>(n&31).

I mean really: play nice and add the &31 there making it portable just
to see it actually performs the no-op. sigh.

None of my compilers, including one extremely state of the art one (Intel C++),
fails to perform this transformation regardless of what I do. There is an
outside chance that by 2005 this compiler will pick up this capability, but
that's another story ...

 

[Morris Dovey]

Well, one might argue that rotates of values greater than the number of bits
are undefined behavior just as shifts are in C and C++.

Or one might just argue the opposite. Are you worried that the
CPU will become dizzy after some arbitrary number of bits rotation?

8^)

 

[Paul Hsieh]

(e-mail address removed) says...

(e-mail address removed) says...

None of my compilers, including one extremely state of the art one (Intel C++),
fails to perform this transformation regardless of what I do.

Sorry, I meant to write that *ALL* of my compilers fail to do this
transformation. I don't have/use gcc or its variants, so I can't verify that
one way or another.

 

[Paul Hsieh]

(e-mail address removed) says...

Well, one might argue that rotates of values greater than the number of bits
are undefined behavior just as shifts are in C and C++.

You can, but you'd be wrong. Rotations are operations which form a
mathematical object called a "group" -- but this is really only true if the
rotation index is unrestricted, or equivalently that the modulo on the rotation
index is applied. This is not true of shifts, which is why the argument is
different.

In essence, ror(ror(a,b),c) should be simplifiable to ror(a,b+c) without
question. (I could argue for different kinds properties for shifts, but they
are not the same as this one, and obviously the ANSI C committee isn't
concerned about such things.)

 

[Chris Torek]

(e-mail address removed) says...

You can, but you'd be wrong. Rotations are operations which form a
mathematical object called a "group" -- but this is really only true
if the rotation index is unrestricted, or equivalently that the modulo
on the rotation index is applied.

Yes, but -- mod WHAT?

In essence, ror(ror(a,b),c) should be simplifiable to ror(a,b+c) without
question.

Only if the number of bits being rotated matches.

In particular, if you want to do a 28-bit "rotation by 4", followed
by a 16-bit "rotation by 4", you *cannot* simply do a 28-bit rotation
by 8. (You will get the wrong answer.)

Note that in assembly, we might write:

ror.l %r1,6
rol.w %r1,4

to take a 32-bit input value in register 1 of the form:

abcdefgh.ijklmnop.qrstuvwx.yzABCDEF

and get:

ABCDEFab.cdefghij.opqrstuv.wxyzklmn

(where each letter represents a single bit).

Of course, as I noted earlier, I would rather have a funnel-shift
operation than merely a rotate operation.

 

[Giuseppe]

But how implement operator+ *without a copy* in a C++ class, or in C?

class num1 (if I read well) doesn't use copy (I use &) but don't work
because if I do
num1 x, a("100"), b("777");
x= a*b;
although inside operator* seems to be ok in operator= is KO. Why?
class num10 seems ok;

class num10{
friend int operator==(const num10& a, const num10& b);
friend int operator<( const num10& a, const num10& b);
friend int operator>( const num10& a, const num10& b);
friend int operator<=(const num10& a, const num10& b);
friend int operator>=(const num10& a, const num10& b);
friend int operator!=(const num10& a, const num10& b);

friend int operator==(const num10& a, unsigned b);
friend int operator<( const num10& a, unsigned b);
friend int operator>( const num10& a, unsigned b);
friend int operator<=(const num10& a, unsigned b);
friend int operator>=(const num10& a, unsigned b);
friend int operator!=(const num10& a, unsigned b);

friend int operator==(unsigned a, const num10& b);
friend int operator<( unsigned a, const num10& b);
friend int operator>( unsigned a, const num10& b);
friend int operator<=(unsigned a, const num10& b);
friend int operator>=(unsigned a, const num10& b);
friend int operator!=(unsigned a, const num10& b);

friend num10 operator+( const num10& a, const num10& b);
friend num10 operator+( const num10& a, unsigned b);
friend num10 operator+( unsigned b, const num10& a);

friend num10 operator-( const num10& a, const num10& b);
friend num10 operator-( const num10& a, unsigned b);
friend num10 operator-( unsigned b, const num10& a);

friend num10 operator*( const num10& a, const num10& b);
friend num10 operator*( const num10& a, unsigned b);
friend num10 operator*( unsigned b, const num10& a);

friend num10 operator/( const num10& a, const num10& b);
friend num10 operator/( const num10& a, unsigned b);
friend num10 operator/( unsigned b, const num10& a);

friend num10 operator%( const num10& a, const num10& b);
friend num10 operator%( const num10& a, unsigned b);
friend num10 operator%( unsigned b, const num10& a);
friend int resize( unsigned len);

friend void pr_num( const num10& a );
public :
num10();
num10(unsigned len);
num10(const char a[]);
num10(num10& r);
num10& operator=(const num10& r);
num10& operator=(unsigned r);
~num10();

numero* nume() { R &numer; }

unsigned char* ricon1();
void print();

private:
numero numer;
unsigned lung;
};

class num1{
friend int operator==(const num1& a, const num1& b);
friend int operator<( const num1& a, const num1& b);
friend int operator>( const num1& a, const num1& b);
friend int operator<=(const num1& a, const num1& b);
friend int operator>=(const num1& a, const num1& b);
friend int operator!=(const num1& a, const num1& b);

friend int operator==(const num1& a, unsigned b);
friend int operator<( const num1& a, unsigned b);
friend int operator>( const num1& a, unsigned b);
friend int operator<=(const num1& a, unsigned b);
friend int operator>=(const num1& a, unsigned b);
friend int operator!=(const num1& a, unsigned b);

friend int operator==(unsigned a, const num1& b);
friend int operator<( unsigned a, const num1& b);
friend int operator>( unsigned a, const num1& b);
friend int operator<=(unsigned a, const num1& b);
friend int operator>=(unsigned a, const num1& b);
friend int operator!=(unsigned a, const num1& b);

friend num1& operator+( const num1& a, const num1& b);
friend num1& operator+( const num1& a, unsigned b);
friend num1& operator+( unsigned b, const num1& a);

friend num1& operator-( const num1& a, const num1& b);
friend num1& operator-( const num1& a, unsigned b);
friend num1& operator-( unsigned b, const num1& a);

friend num1& operator*( const num1& a, const num1& b);
friend num1& operator*( const num1& a, unsigned b);
friend num1& operator*( unsigned b, const num1& a);

friend num1& operator/( const num1& a, const num1& b);
friend num1& operator/( const num1& a, unsigned b);
friend num1& operator/( unsigned b, const num1& a);

friend num1& operator%( const num1& a, const num1& b);
friend num1& operator%( const num1& a, unsigned b);
friend num1& operator%( unsigned b, const num1& a);

friend int resize1( unsigned len);
friend num10 conv(const num1& a);
friend num1& sqrt(const num1& a);
friend num1& gcd (const num1& a, const num1& b);

public :
num1();
num1(unsigned len);
num1(const char a[]);
num1(num1& r);

num1& operator=(num1* r);
num1& operator=(const num1& r);
num1& operator=(unsigned r);
~num1();

void print();
void prin();
void casuale(unsigned len);

private:
num_s numer;
unsigned lung;
};

 

[Giuseppe]

class num1 (if I read well) doesn't use copy (I use &) but don't work
because if I do
num1 x, a("100"), b("777");
x= a*b;
although inside operator* seems to be ok in operator= is KO. Why?
class num10 seems ok;

"fixed"
because a*b have a result more large than a and b the operator= call
resize1 to resize the "static" buffers for the new max_dim and in
resize1(). I forgot to copy the 5 tmp numbers of the buffer (I use tmp
numbers in expressions when I call + * \ -. Does The number of tmp
buffers depend of the number of "(" ")" ?)
Thanks

if I have

int z=0

is right

int& f()
{z=7;
return z;
}

or

int z=0
is right
int& f()
{z=7;
return (int&) z;
}

or

int& f()
{int& u=z
u=7;
return u;
}

?

 

[Dave Thompson]

(e-mail address removed) says...

[Note that he *could* have made it portable by clever use of UINT_MAX.]

That's not what he's missing. He's missing a couple of "& 31"'s (%32 would be
incorrect since they might output negative numbers.)

Assuming unsigned is 32 bits, or you use uint32_t or equivalent.

% 32U would be safe, and have the putative advantage of generalizing
to machines with non-power-of-two word sizes, if anyone ever starts
making them again, as well as being a slightly more direct
representation of the programmer's actual intent.

Gcc's ability to translate undefined code and make it into something useful is
legendary. But even if by some tragedy gcc becomes the defacto standard
compiler that everyone uses, the performance problems will only get *WORSE*,
not better.

Of course in this case the code is still *correct* even if not
optimized as by gcc to an actual rotate instruction.

- David.Thompson1 at worldnet.att.net