D

[Arthur J. O'Dwyer]

Re: D


On Tue, 15 Jul 2003, Paul Hsieh wrote:[color=blue]
>
> In article <bf0hot$r78$1@e lf.eng.bsdi.com >, nospam@elf.eng. bsdi.com says...[color=green]
> > Paul Hsieh <qed@pobox.co m> writes:[color=darkred]
> > >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.[/color]
> >
> > But this does not work at all -- I wanted a 24-bit rotate![/color][/color]

More likely 28. ;-)
[color=blue][color=green]
> > 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.[/color]
>
> Your ill attempt at humor is [a non sequitur].[/color]

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.
[color=blue]
> Ordinary rotates happen a lot.[/color]

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.)
[color=blue]
> Name me one feistel crypto algorithm that *DOESN'T* use a rotate. DES,
> BlowFish, MD5, they *all* use rotate.[/color]

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]

Re: D

jwuolijo@cs.Hel sinki.FI says...[color=blue]
> On Tue, 15 Jul 2003, Kevin Easton wrote:[color=green][color=darkred]
> > > Odd ... this will not actually rotate the bits correctly. Consider rot(1, 80)
> > > for example. Shift on Intel processors happen to mod the shift value by the
> > > size of the word so it actually works. However, according to the ANSI C
> > > standard, there is no requirement for it to do that. Technically, this code is
> > > not portable.[/color]
> >
> > 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.[/color]
>
> 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.[/color]

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

--
Paul Hsieh

http://www.pobox.com/~qed/

http://bstring.sourceforge.net/

[Morris Dovey]

Re: D

Ron Natalie wrote:[color=blue]
> "Paul Hsieh" <qed@pobox.co m> wrote in message news:MPG.197d64 66a06b88d498972 d@news.sf.sbcgl obal.net...
>[color=green]
>>Odd ... this will not actually rotate the bits correctly. Consider rot(1, 80)
>>for example[/color]
>
> 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++.[/color]

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

8^)
--
Morris Dovey
West Des Moines, Iowa USA
C links at http://www.iedu.com/c

[Paul Hsieh]

Re: D

qed@pobox.com says...[color=blue]
> jwuolijo@cs.Hel sinki.FI says...[color=green]
> > On Tue, 15 Jul 2003, Kevin Easton wrote:[color=darkred]
> > > 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.[/color]
> >
> > 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.[/color]
>
> None of my compilers, including one extremely state of the art one (Intel C++),
> fails to perform this transformation regardless of what I do.[/color]

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

http://www.pobox.com/~qed/

http://bstring.sourceforge.net/

[Paul Hsieh]

Re: D

ron@sensor.com says...[color=blue]
> "Paul Hsieh" <qed@pobox.co m> wrote:[color=green]
> > Odd ... this will not actually rotate the bits correctly. Consider rot(1, 80)
> > for example[/color]
>
> 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++.[/color]

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

--
Paul Hsieh

http://www.pobox.com/~qed/

http://bstring.sourceforge.net/

[Chris Torek]

Re: D

>ron@sensor.c om says...[color=blue][color=green]
>> 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++.[/color][/color]

In article <MPG.197dd1fc80 2cd1a2989734@ne ws.sf.sbcglobal .net>
Paul Hsieh <qed@pobox.co m> writes:[color=blue]
>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.[/color]

Yes, but -- mod WHAT?
[color=blue]
>In essence, ror(ror(a,b),c) should be simplifiable to ror(a,b+c) without
>question.[/color]

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.ijklmn op.qrstuvwx.yzA BCDEF

and get:

ABCDEFab.cdefgh ij.opqrstuv.wxy zklmn

(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.
--
In-Real-Life: Chris Torek, Wind River Systems (BSD engineering)
Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603
email: forget about it http://67.40.109.61/torek/index.html (for the moment)
Reading email is like searching for food in the garbage, thanks to spammers.

[Giuseppe]

Re: D

>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==(cons t 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<=(cons t num10& a, const num10& b);
friend int operator>=(cons t num10& a, const num10& b);
friend int operator!=(cons t num10& a, const num10& b);

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

friend int operator==(unsi gned a, const num10& b);
friend int operator<( unsigned a, const num10& b);
friend int operator>( unsigned a, const num10& b);
friend int operator<=(unsi gned a, const num10& b);
friend int operator>=(unsi gned a, const num10& b);
friend int operator!=(unsi gned 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=(unsig ned r);
~num10();

numero* nume() { R &numer; }

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

private:
numero numer;
unsigned lung;
};

class num1{
friend int operator==(cons t 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<=(cons t num1& a, const num1& b);
friend int operator>=(cons t num1& a, const num1& b);
friend int operator!=(cons t num1& a, const num1& b);

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

friend int operator==(unsi gned a, const num1& b);
friend int operator<( unsigned a, const num1& b);
friend int operator>( unsigned a, const num1& b);
friend int operator<=(unsi gned a, const num1& b);
friend int operator>=(unsi gned a, const num1& b);
friend int operator!=(unsi gned 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=(unsig ned r);
~num1();

void print();
void prin();
void casuale(unsigne d len);

private:
num_s numer;
unsigned lung;
};

[Giuseppe]

Re: D

giuseppe@giusep pe.wwwew (Giuseppe) wrote:[color=blue][color=green]
>>But how implement operator+ *without a copy* in a C++ class, or in C?[/color]
>
>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;[/color]

"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]

Re: D

On Tue, 15 Jul 2003 09:18:49 GMT, qed@pobox.com (Paul Hsieh) wrote:
[color=blue]
> ajo@andrew.cmu. edu says...[/color]
<about supposedly idiomatic rotate>[color=blue][color=green][color=darkred]
> > > > unsigned rot(unsigned n, int m)
> > > > {
> > > > return n >> (32-m) | n << m;
> > > > }[/color][/color][/color]
<snip>[color=blue][color=green]
> > [Note that he *could* have made it portable by clever use of UINT_MAX.][/color]
>
> 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.)
>[/color]
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.

<snip>[color=blue]
> 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.[/color]

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.ne t