“Undoing” an integer wraparound

I ran into an interesting theoretical problem a number of years ago. I never found a solution, and it continues to haunt me when I sleep.

Suppose you have a (C#) application that holds some number in an int, called x. (The value of x is not fixed). When the program is run, x is multiplied by 33 and then written to a file.

Basic source code looks like this:

int x = getSomeInt();
x = x * 33;
file.WriteLine(x); // Writes x to the file in decimal format

Some years later, you discover that you need the original values of X back. Some calculations are simple: Just divide the number in the file by 33. However, in other cases, X is large enough that the multiplication caused an integer overflow. According to the docs, C# will truncate the high-order bits until the number is less than int.MaxValue. Is it possible, in this case, to either:

Recover X itself or
Recover a list of possible values for X?

It seems to me (though my logic could certainly be flawed) that one or both should be possible, since the simpler case of addition works (Essentially if you add 10 to X and it wraps, you can subtract 10 and wind up with X again) and multiplication is simply repeated addition. Also helping (I believe) is the fact that X is multiplied by the same value in all cases – a constant 33.

This has been dancing around my skull at odd moments for years. It’ll occur to me, I’ll spend some time trying to think through it, and then I’ll forget about it for a few months. I’m tired of chasing this problem! Can anyone offer insight?

(Side note: I really don’t know how to tag this one. Suggestions welcome.)

Edit: Let me clarify that if I can get a list of possible values for X, there are other tests I could do to help me narrow it down to the original value.

Multiply by 1041204193.

When the result of a multiplication doesn’t fit in an int, you won’t get the exact result, but you will get a number equivalent to the exact result modulo 2**32. That means that if the number you multiplied by was coprime to 2**32 (which just means it has to be odd), you can multiply by its multiplicative inverse to get your number back. Wolfram Alpha or the extended Euclidean algorithm can tell us 33’s multiplicative inverse modulo 2**32 is 1041204193. So, multiply by 1041204193, and you have the original x back.

If we had, say, 60 instead of 33, we wouldn’t be able to recover the original number, but we would be able to narrow it down to a few possibilities. By factoring 60 into 4*15, computing the inverse of 15 mod 2**32, and multiplying by that, we can recover 4 times the original number, leaving only 2 high-order bits of the number to brute-force. Wolfram Alpha gives us 4008636143 for the inverse, which doesn’t fit in an int, but that’s okay. We just find a number equivalent to 4008636143 mod 2**32, or force it into an int anyway to have the compiler do that for us, and the result will also be an inverse of 15 mod 2**32. (We get -286331153.)

This maybe better suited as an question to Math (sic) SE. You are basically dealing with modular arithmetic, since dropping the left-most bits is the same thing.

I am not as good at Maths as the people who are on Math (sic) SE, but i will try to answer.

What we have here is that the number is being multiplied by 33 (3*11), and its only common denominator with your mod is 1. That is because by definition the bits in the computer are powers of two, and thus your mod is some power of two.

You will be able to construct the table where for every previous value you calculate the following value. And the question becomes do the following numbers correspond to only one previous one.

If it were not 33, but a prime or some power of a prime, i believe that the answer would be yes, but in this case… ask on Math.SE!

Programmatic test

This is in C++ because i don’t know C#, but the concept still holds. This seems to show that you can:

#include <iostream>
#include <map>

int main(void)
{
    unsigned short count = 0;
    unsigned short x = 0;
    std::map<unsigned short, unsigned short> nextprev;

    nextprev[0] = 0;
    while(++x) nextprev[x] = 0;

    unsigned short nextX;
    while(++x)
    {
            nextX = x*33;
            if(nextprev[nextX])
            {
                    std::cout << nextprev[nextX] << "*33==" << nextX << " && " << x << "*33==" << nextX << std::endl;
                    ++count;
            }
            else
            {
                    nextprev[nextX] = x;
                    //std::cout << x << "*33==" << nextX << std::endl;
            }
    }

    std::cout << count << " collisions found" << std::endl;

    return 0;
}

After populating such a map, you would be always able to get the previous X if you know the next one. There is only a single value at all times.

One way to get it is to use brute force. Sorry I don’t know C# but the following is c-like pseudo code to illustrate the solution:

for (x=0; x<=INT_MAX; x++) {
    if (x*33 == test_value) {
        printf("%dn", x);
    }
}

Technically, what you need is x*33%(INT_MAX+1) == test_value but integer overflow will automatically do the % operation for you unless your language uses arbitrary precision integers (bigint).

What this gives you is a series of numbers that may have been the original number. The first number printed would be the number that would generate one round of overflow. The second number would be the number that would generate two rounds of overflow. And so on..

So, if you know you data better you can make a better guess. For example, common clock maths (overflow every 12 o’clock) tend to make the first number more likely since most people are interested in things that happened today.

You could the SMT solver Z3 to ask it to give you a satisfying assignment for the formula x * 33 = valueFromFile. It will invert that equation for you and give you all possible values of x. Z3 supports exact bitvector arithmetic including multiplication.

    public static void InvertMultiplication()
    {
        int multiplicationResult = new Random().Next();
        int knownFactor = 33;

        using (var context = new Context(new Dictionary<string, string>() { { "MODEL", "true" } }))
        {
            uint bitvectorSize = 32;
            var xExpr = context.MkBVConst("x", bitvectorSize);
            var yExpr = context.MkBVConst("y", bitvectorSize);
            var mulExpr = context.MkBVMul(xExpr, yExpr);
            var eqResultExpr = context.MkEq(mulExpr, context.MkBV(multiplicationResult, bitvectorSize));
            var eqXExpr = context.MkEq(xExpr, context.MkBV(knownFactor, bitvectorSize));

            var solver = context.MkSimpleSolver();
            solver.Assert(eqResultExpr);
            solver.Assert(eqXExpr);

            var status = solver.Check();
            Console.WriteLine(status);
            if (status == Status.SATISFIABLE)
            {
                Console.WriteLine(solver.Model);
                Console.WriteLine("{0} * {1} = {2}", solver.Model.Eval(xExpr), solver.Model.Eval(yExpr), solver.Model.Eval(mulExpr));
            }
        }
    }

Output looks like this:

SATISFIABLE
(define-fun y () (_ BitVec 32)
  #xa33fec22)
(define-fun x () (_ BitVec 32)
  #x00000021)
33 * 2738875426 = 188575842

To undo that result will give you a non-zero finite amount of numbers (normally infinite, but int is a finite subset of ℤ). If this is this acceptable, just generate the numbers (see other answers).

Otherwise you need to maintain a list of history (of finite or infinite length) of the variable’s history.

As always, there is a solution from a scientist and solution from an engineer.

Above you will find a very good solution from a scientist, which works always, but requires you to calculate “multiplicative inverse”.

Here is a quick solution from engineer, which will not force you to try all possible integers.

val multiplier = 33 //used with 0x23456789
val problemAsLong = (-1947051863).toLong & 0xFFFFFFFFL

val overflowBit = 0x100000000L
for(test <- 0 until multiplier) {
  if((problemAsLong + overflowBit * test) % multiplier == 0) {
    val originalLong = (problemAsLong + overflowBit * test) / multiplier
    val original = originalLong.toInt
    println(s"$original (test = $test)")
  }
}

What are the ideas?

We got overflow, so let’s use larger types to recover (Int -> Long)
We probably lost some bits due to overflow, let’s recover them
The overflow was not more than Int.MaxValue * multiplier

Full executable code is located on http://ideone.com/zVMbGV

Details:

val problemAsLong = (-1947051863).toLong & 0xFFFFFFFFL
Here we convert our stored number to Long, but since Int and Long are signed, we have to do it correctly.
So we limit the number using bitwise AND with bits of Int.
val overflowBit = 0x100000000L
This bit or multiplication of it could be lost by initial multiplication.
It’s a first bit outside of Int range.
for(test <- 0 until multiplier)
According to 3rd Idea the maximal overflow is limited by multiplier, so don’t try more than we really need.
if((problemAsLong + overflowBit * test) % multiplier == 0)
Check if by adding possibly lost overflow we come to a solution
val original = originalLong.toInt
Original problem was in Int range, so let’s return to it. Otherwise we could incorrectly recover numbers, which were negative.
println(s"$original (test = $test)")
Don’t break after the first solution, because there are could be other possible solutions.

PS: 3rd Idea is not strictly correct, but left so to be understandable.
Int.MaxValue is 0x7FFFFFFF, but maximal overflow is 0xFFFFFFFF * multiplier.
So the correct text would be “The overflow was not more than -1 * multiplier”.
This is correct, but not everybody will understand it.

Filed under: softwareengineering - @ 01:23

Thẻ: c++

Thiết kế website giá rẻ

Danh mục

“Undoing” an integer wraparound