Zero-fill shift

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

  1. Daniel Orner

    Daniel Orner Guest

    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
     
    Daniel Orner, May 4, 2004
    #1
    1. Advertising

  2. 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
    mask for the upper bits.

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

    then your op is:

    (a >> b) & masks


    --
    Regards,

    Diez B. Roggisch
     
    Diez B. Roggisch, May 4, 2004
    #2
    1. Advertising

  3. Daniel Orner

    Dan Bishop Guest

    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
    #3
  4. Daniel Orner

    Daniel Orner Guest

    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


    > 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
    #4
  5. In article <>,
    Daniel Orner <> wrote:
    >
    >
    > 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
     
    Gary D. Duzan, May 5, 2004
    #5
  6. 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...

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


    --
    -Scott David Daniels
     
    Scott David Daniels, May 5, 2004
    #6
  7. Daniel Orner

    Daniel Orner Guest

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


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

    Paul Rubin Guest

    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
    #8
  9. Daniel Orner

    Daniel Orner Guest

    > 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
    #9
  10. Daniel Orner <> wrote:
    > 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.

    >>> 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
    #10
  11. Eli Stevens (WG.c) wrote:

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

    >
    > 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
    #11
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Roberto Gallo

    Shift - byte[] buf shift

    Roberto Gallo, Jan 27, 2004, in forum: Java
    Replies:
    3
    Views:
    2,248
    Thomas Schodt
    Jan 27, 2004
  2. Wenjie
    Replies:
    3
    Views:
    1,094
    Ron Samuel Klatchko
    Jul 11, 2003
  3. Santosh Nayak

    Left Shift / Right Shift Operators

    Santosh Nayak, Nov 30, 2006, in forum: C Programming
    Replies:
    16
    Views:
    1,506
    CBFalconer
    Nov 30, 2006
  4. Sanny
    Replies:
    38
    Views:
    3,573
    Thomas Richter
    Apr 29, 2011
  5. devphylosoff

    what "shift" does, if not "$_ = shift;" ?

    devphylosoff, Nov 29, 2007, in forum: Perl Misc
    Replies:
    3
    Views:
    378
    Michele Dondi
    Dec 4, 2007
Loading...

Share This Page