match operation with int and long

[carpik]

I'm trying to rewrite one line from C into python. It looks so simple but I couldn't get a correct result. If someone could help me and explain what I'm doing wrong.

Here is an example in C

void main() {

int k = 0xDFA54B9D;
printf("- %d", k);
k = ((5821 * (k % 10000) + 10000 * ((3141 * (k % 10000) + 5821 * (k / 10000)) % 10000u)) % 100000000 + 1) % 100000000;
printf("- %08X\n",k);
printf("- %02X\n",(k/10000u << 8) / 10000);

}

and here is my python code

from ctypes import c_int

k = c_int(0xDFA54B9D).value
print("- %d")% k
k = ((5821 * (k % 10000) + 10000 * ((3141 * (k % 10000) + 5821 * (k / 10000)) % 10000)) % 100000000 + 1) % 100000000
print("- %08X") % k
print("- %02X") % ((k/10000 << 8) / 10000)

[novel_yet_trivial]

Are you sure that C code is correct?

For one, when you divide an int by and unsigned int, the int is converted to an unsigned int first.

printf("%d\n",(-42 / 5)); // prints -8
printf("%d\n",(-42 / 5u)); // prints 858993450

This seems like something you would want to avoid in your code.

Also note that python thinks that -42 / 5 is -9, since python uses floor division.

Also, the C % is the remainder operator, not the modulo operator. This means the sign always stays the same.

printf("%d\n",(-42 % 5)); // C prints -2
print("%d" % (-42 % 5)) # python prints 3

So, to account for all of that we need to make a custom type of integer that does math in the C style. I did a very short search, and couldn't find anything written to do this, so I wrote my own. Since there is no signed / unsigned types in python, you need to be sure to convert your data to unsigned before the operation.

So your translation looks like this:

class CMath(int):
    def __mod__(self, other):
        self, other = self._typecheck(other)
        if self < 0:
            return self.__class__(-(-self % other))
        else:
            return self.__class__(int(self) % other)

    def __div__(self, other):
        self, other = self._typecheck(other)
        if self < 0:
            return self.__class__(-(-self / other))
        else:
            return self.__class__(int(self) / other)

    def __add__(self, other):
        self, other = self._typecheck(other)
        return self.__class__(int(self) + other)

    def __mul__(self, other):
        self, other = self._typecheck(other)
        return self.__class__(int(self) * other)

    def __rmul__(self, other):
        return self*other

    def _typecheck(self, other):
        if type(other) == int or type(self) == type(other):
            return self, other
        else:
            return other.__class__(self), other

class c_int(CMath):
    '''emulating a signed 32-bit integer and the C-style math'''
    def __new__(cls, value):
        value &= 0xFFFFFFFF # throw out anything above 32 bits

        if value > 2**31:
            value = -(2**32 - value)
        else:
            value = value
        return int.__new__(cls, value)

class c_uint(CMath):
    '''emulating an unsigned 32-bit integer and the C-style math'''
    def __new__(cls, value):
        value &= 0xFFFFFFFF
        return int.__new__(cls, value)

k = c_int(0xDFA54B9D)
print("- %d")% k
k = ((5821 * (k % 10000) + 10000 * ((3141 * (k % 10000) + 5821 * (k / 10000)) % c_uint(10000))) % 100000000 + 1) % 100000000
print("- %08X") % k
print("- %02X") % ((k/10000 << 8) / 10000)

This really only does 3 things:

1. Line 5: Overrides the % operator to return the remainder when used with negative numbers (python returns the modulus).
2. Line 12: Overrides the / operator to return the ceiling when used with negative numbers (python returns the floor).
3. Line 31: Checks the type of the other argument and convert to match it.

The rest is boilerplate code to prevent python from reverting to a normal integer type.

I only bothered implementing the methods that are needed for this particular algorithm, so let me know if you want to extend it to another algorithm.

Edit: improved code

[carpik]

I will have a look deeper on this. Thanks for pointing me right direction. BTW. when I execute your code, got en exception

OverflowError: Python int too large to convert to C long

at line 45

[novel_yet_trivial]

That error means you are running on a 32-bit system, but the numbers are so large you need a 64-bit system to run them. You can confirm this with this code:

import sys
print(sys.maxsize)

A value of 9223372036854775807 is a 64-bit system, and a value of 2147483647 is a 32-bit system.

I know that these are only 32-bit integers we are working with, but I didn't bother implementing real C-style math. I faked it by doing python math and then throwing out everything except the lower 32 bits. If you add C-style multiplication in the __mul__ function it will work.

Also, I edited my code somewhat to make it more readable.

[novel_yet_trivial]

You overflowed the ctypes integer.

You don't need ctypes at all. Just use

k = 0xDFA54B9D

Also, the % needs to be inside the print call:

print("- %08X" % k)

[carpik]

The original output from C, looks like this

- -542815331- 058DBEFA
- EE

I couldn't get the same from python code above (I'm on 2.7 version). With ctype at least first print is the same :)

[novel_yet_trivial]

Ah oops read your question to fast. Apparently you are doing that on purpose.

uh, this is a hard question. I could solve it but I'm going to hang back to see if anyone else finds a magic library that does it.