# Zero-fill shift

Discussion in 'Python' started by Daniel Orner, May 4, 2004.

1. ### Daniel OrnerGuest

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

Daniel Orner, May 4, 2004

2. ### Diez B. RoggischGuest

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

Diez B. Roggisch, May 4, 2004

3. ### Dan BishopGuest

Daniel Orner <> wrote in message news:<>...
> 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.

Dan Bishop, May 4, 2004
4. ### Daniel OrnerGuest

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.

Daniel Orner, May 5, 2004
5. ### Gary D. DuzanGuest

In article <>,
Daniel Orner <> 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

Gary D. Duzan, May 5, 2004
6. ### Scott David DanielsGuest

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

Scott David Daniels, May 5, 2004
7. ### Daniel OrnerGuest

Gary D. Duzan wrote:
> In article <>,
> Daniel Orner <> 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

Daniel Orner, May 5, 2004
8. ### Paul RubinGuest

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

Paul Rubin, May 5, 2004
9. ### Daniel OrnerGuest

> 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

Daniel Orner, May 6, 2004
10. ### Eli Stevens \(WG.c\)Guest

Daniel Orner <> 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(128)

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

Eli Stevens \(WG.c\), Jun 26, 2004
11. ### Scott David DanielsGuest

Eli Stevens (WG.c) wrote:

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

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

--
-Scott David Daniels

Scott David Daniels, Jun 26, 2004