Zero-fill shift

D

Daniel Orner

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?

Thanks!

--Daniel
 
D

Diez B. Roggisch

Daniel said:
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
mask for the upper bits.

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

then your op is:

(a >> b) & masks
 
D

Dan Bishop

Daniel Orner said:
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.
 
D

Daniel Orner

Great, this works. :cool: 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
 
G

Gary D. Duzan

Great, this works. :cool: 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
 
S

Scott David Daniels

Daniel said:
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...
(because addition in python works)
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;
}

How about:
POSITIVEMASK = int((1L << 31) - 1)
WORDSIGNBIT = 1L << 31

def signwrap(v):
if v & WORDSIGNBIT:
return int(v | ~POSITIVEMASK)
return int(v & POSITIVEMASK)

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

Daniel Orner

Gary said:
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
 
P

Paul Rubin

Daniel Orner said:
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.
 
D

Daniel Orner

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
 
E

Eli Stevens \(WG.c\)

Daniel Orner said:
Great, this works. :cool: 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.
.... if myint > 0x7f:
.... return -1 * (0xff - myint + 1)
.... return myint
....-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/
--
 
S

Scott David Daniels

Eli said:
But more to the point: Here's something that will do the trick if your
overflow isn't ever more than one bit....
And if you want to be able to handle multibit overflow:

SIGN_BIT = 2 ** 7 # 31 if you prefer 32-bit signed numbers

def wrap(n):
if n & SIGN_BIT:
return n | -SIGN_BIT
else:
return n & (SIGN_BIT - 1)
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top