Velocity Reviews > Zero-fill shift

# Zero-fill shift

Daniel Orner
Guest
Posts: n/a

 05-04-2004
Hey all,

I'm trying to port a (relatively) simple encryption algorithm from Java
code (mainly because the algorithm will be used identically in both
contexts). However, the code makes extensive use of Java's >>> operator,
which shifts right and fills in the leftmost bits with zeroes. I've been
unable to duplicate that effect in Python.
Apparently, a >>> b is equal to the following:

if a >= 0: return a >> b
else: return (a>>b)+(2<<~b)

However, Python complains when I try to do the left-shift, because ~b
is often a negative number. Does anyone have a better idea about how I

Thanks!

--Daniel

Diez B. Roggisch
Guest
Posts: n/a

 05-04-2004
Daniel Orner wrote:

> I'm trying to port a (relatively) simple encryption algorithm from Java
> code (mainly because the algorithm will be used identically in both
> contexts). However, the code makes extensive use of Java's >>> operator,
> which shifts right and fills in the leftmost bits with zeroes. I've been
> unable to duplicate that effect in Python.
> Apparently, a >>> b is equal to the following:
>
> if a >= 0: return a >> b
> else: return (a>>b)+(2<<~b)
>
> However, Python complains when I try to do the left-shift, because ~b
> is often a negative number. Does anyone have a better idea about how I
> should go about doing this?

from what I can see from the java and python docs, all you should need is a

masks = [0xffffffff] + [0x7fffffff >> i for i in xrange(31)]

--
Regards,

Diez B. Roggisch

Dan Bishop
Guest
Posts: n/a

 05-04-2004
Daniel Orner <(E-Mail Removed)> wrote in message news:<(E-Mail Removed)>...
> Hey all,
>
> I'm trying to port a (relatively) simple encryption algorithm from Java
> code (mainly because the algorithm will be used identically in both
> contexts). However, the code makes extensive use of Java's >>> operator,
> which shifts right and fills in the leftmost bits with zeroes. I've been
> unable to duplicate that effect in Python.
> Apparently, a >>> b is equal to the following:
>
> if a >= 0: return a >> b
> else: return (a>>b)+(2<<~b)
>
> However, Python complains when I try to do the left-shift, because ~b
> is often a negative number. Does anyone have a better idea about how I
> should go about doing this?

def srl(a, b):
return (a & 0xFFFFFFFFL) >> b

"a & 0xFFFFFFFFL" behaves as if you had written "(unsigned int) a" in C.

Daniel Orner
Guest
Posts: n/a

 05-05-2004
Great, this works. Unfortunately, I've run into another problem. In
the Java algorithm, two integers are added. This often results in an
overflow and a negative number, which is the desired result. However, I
can't seem to duplicate that in Python, as adding two integers that are
too large just results in a long (and using the int() method doesn't
work). I've tried various solutions, but haven't come up with something
that duplicates this behavior exactly.
For reference, here's the Java code I'm trying to duplicate:

while(n-- > 0)
{ sum += delta;
y += (z << 4)+a ^ z + sum ^ (z >>> 5) + b;
z += (y << 4)+c ^ y + sum ^ (y >>> 5) + d;
}

with the following initial values:
y = 1751477356
z = 1864398703
a = 2002870900
b = 858797621
c = 1751607922
d = 875968626
sum = 0
delta = 0x9E3779B9
n = 32

Any help would be greatly appreciated. ^^; Thanks!

--Daniel

> def srl(a, b):
> return (a & 0xFFFFFFFFL) >> b
>
> "a & 0xFFFFFFFFL" behaves as if you had written "(unsigned int) a" in C.

Gary D. Duzan
Guest
Posts: n/a

 05-05-2004
In article <(E-Mail Removed)>,
Daniel Orner <(E-Mail Removed)> wrote:
>
>
> Great, this works. Unfortunately, I've run into another problem. In
>the Java algorithm, two integers are added. This often results in an
>overflow and a negative number, which is the desired result. However, I
>can't seem to duplicate that in Python, as adding two integers that are
>too large just results in a long (and using the int() method doesn't
>work). I've tried various solutions, but haven't come up with something
>that duplicates this behavior exactly.

You could try scattering "(foo) % 2**32" around wherever there
could be an overflow.

Gary Duzan
BBN Technologies

Scott David Daniels
Guest
Posts: n/a

 05-05-2004
Daniel Orner wrote:

> In the Java algorithm, two integers are added. This often results in an
> overflow and a negative number, which is the desired result. However, I
> can't seem to duplicate that in Python...

> I've tried various solutions, but haven't come up with something
> that duplicates this behavior exactly.

> For reference, here's the Java code I'm trying to duplicate:
>
> while(n-- > 0)
> { sum += delta;
> y += (z << 4)+a ^ z + sum ^ (z >>> 5) + b;
> z += (y << 4)+c ^ y + sum ^ (y >>> 5) + d;
> }

POSITIVEMASK = int((1L << 31) - 1)
WORDSIGNBIT = 1L << 31

def signwrap(v):
if v & WORDSIGNBIT:

for i in range(n):
sum = signwrap(sum + delta)
y = signwrap(y + (z << 4)+a ^ z + sum ^ (z >>> 5) + b)
z = signwrap(z + (y << 4)+c ^ y + sum ^ (y >>> 5) + d)

--
-Scott David Daniels
http://www.velocityreviews.com/forums/(E-Mail Removed)

Daniel Orner
Guest
Posts: n/a

 05-05-2004
Gary D. Duzan wrote:
> In article <(E-Mail Removed)>,
> Daniel Orner <(E-Mail Removed)> wrote:
>
>>
>> Great, this works. Unfortunately, I've run into another problem. In
>>the Java algorithm, two integers are added. This often results in an
>>overflow and a negative number, which is the desired result. However, I
>>can't seem to duplicate that in Python, as adding two integers that are
>>too large just results in a long (and using the int() method doesn't
>>work). I've tried various solutions, but haven't come up with something
>>that duplicates this behavior exactly.

>
>
> You could try scattering "(foo) % 2**32" around wherever there
> could be an overflow.
>
> Gary Duzan
> BBN Technologies

Hmm... no, that'll never get me any negative numbers. I'm trying to
make sure that the behavior of an overflow actually *happens* rather
than trying to avoid it.

--Daniel

Paul Rubin
Guest
Posts: n/a

 05-05-2004
Daniel Orner <(E-Mail Removed)> writes:
> while(n-- > 0)
> { sum += delta;
> y += (z << 4)+a ^ z + sum ^ (z >>> 5) + b;
> z += (y << 4)+c ^ y + sum ^ (y >>> 5) + d;
> }

That's Wheeler and Needham's Tiny Encryption Algorithm (TEA). You can
just AND the intermediate results with 0xffffffff as needed, but
unless you're trying to interoperate with some other program that
uses that algorithm, you're better off using a different algorithm.
There's plenty to choose from that are already implemented in Python
or as Python extensions.

Daniel Orner
Guest
Posts: n/a

 05-06-2004
> That's Wheeler and Needham's Tiny Encryption Algorithm (TEA). You can
> just AND the intermediate results with 0xffffffff as needed, but
> unless you're trying to interoperate with some other program that
> uses that algorithm, you're better off using a different algorithm.
> There's plenty to choose from that are already implemented in Python
> or as Python extensions.

Yes, that is what I'm trying to do (basically I have Java on one end
and Python on the other). The Java is running on a Palm device, so using
SSL isn't really prudent. This seems like probably the simplest way to
do it, so this little problem is really bugging me. ^^;

I tried Scott's suggestion, but it's giving me totally different
results as well. -_-

--Daniel

Eli Stevens \(WG.c\)
Guest
Posts: n/a

 06-25-2004
Daniel Orner <(E-Mail Removed)> wrote:
> Great, this works. Unfortunately, I've run into another problem.
> In the Java algorithm, two integers are added. This often results in
> an overflow and a negative number, which is the desired result.
> However, I can't seem to duplicate that in Python, as adding two
> integers that are too large just results in a long (and using the
> int() method doesn't work). I've tried various solutions, but haven't
> come up with something that duplicates this behavior exactly.

The behavior you are after is called "Two's complement," and is tied to
using fixed-size integers and to simplifying how negative numbers are
handled in hardware. Google, of course, knows all (provided you know the
questions... .

But more to the point: Here's something that will do the trick if your
overflow isn't ever more than one bit. Note the last two cases - you may
need to do some additional bounding if cases like those might occur for you
(I haven't really dug into your algorithm, sorry! . You will also need to
extend it out to 32 bits.

>>> def cp(myint):

.... if myint > 0x7f:
.... return -1 * (0xff - myint + 1)
.... return myint
....
>>> cp(1)

1
>>> cp(127)

127
>>> cp(12

-128
>>> cp(255)

-1
>>> cp(0)

0
>>> cp(256)

0
>>> cp(257)

1
>>> cp(513)

257
>>> cp(-257)

-257

Heh, implementing 2's complement in software... Who'd have thought?

Enjoy! HTH,
Eli

--
Give a man some mud, and he plays for a day.
Teach a man to mud, and he plays for a lifetime.
WickedGrey.com uses SpamBayes on incoming email:
http://spambayes.sourceforge.net/
--