# Need reversal of algorithm

I have the following two functions:

unsigned PullTerminalId(unsigned long id)
{
return ((unsigned)(id >> 20));
}

unsigned long get_human_check_id(unsigned long id)
{
unsigned long terminalId = (unsigned long)PullTerminalId(id) * 10000;
unsigned long checkNbr = (unsigned)(id & 0xFFFF);
return terminalId + checkNbr;
}

As an example, if I call get_human_check_id with a value of 1048577, then the result is 10001

What I need is a function that will do the reverse.
LVL 3
###### Who is Participating?

Commented:
Actually, the inner loop could be simplified a little.
...
result = (a << 20u) + residue;
for(b = 0; b < 16; b++) {
printf("get_human_check_id(%u) = %u\n", result,
get_human_check_id(result);
result += 65536;
}
...
There will always be n*16 results, where 0 <= n <= 7.
0

Commented:
You should be able to do that by just using

unsigned get_human_check_id(unsigned long id)
{
return ((unsigned)(id << 20));
}
0

Commented:
Sorry, that should have been

unsigned long get_human_check_id(unsigned id)
{
unsigned long ul = 0;

ul = (unsigned long)(id << 20);

return (ul);
}
0

Commented:
Disregard the above - I jumped on the wrong function :-(
0

Commented:
What are you trying to get from what exactly?   It's not clear from the code or the text.

Previous suggestions may have been *close*, but it may be a problem if you shift an unsigned integer 20 bits to the left.

Try this:

unsigned long get_human_check_id( unsigned id )
{
unsigned long ul = id;
return ( ul << 20 );
}
0

Author Commented:
What I need is the reverse of the get_human_check_id function.

If you call that functoin with a value of 1048577, the result will be 10001.

I need a function that will do the reverse such that 10001 will yield 1048577
0

Commented:
Actually,

unsigned long get_human_check_id_rev(unsigned long id)
{

unsigned long rev1 = id / 10000;
rev1 = rev1 << 20;

return rev1;
}

would work - the only problem is

unsigned long checkNbr = (unsigned)(id & 0xFFFF);

which is not really reversible...
0

Commented:
>>I need a function that will do the reverse such that 10001 will yield 1048577

Does

unsigned long get_human_check_id_rev(unsigned long id)
{

unsigned long rev1 = id / 10000;
rev1 = rev1 << 20;
unsigned long rev2 = (unsigned)(id & 0x01);
return rev1 + rev2;
}

work for other values as well? Calling it with 10001 does yield 1048577...
0

Author Commented:
Actually this appears only work with 1048577. In other words, if I try any other numbers it fails. For example, 1048977 yields 10401 but is reversed to 1048577
0

Author Commented:
I realize that bits 16-19 are going to be lost, but I'm being told that those bytes are not used. Therefore, if someone can prove that the algo can't be reversed, I'll award the 500 pts and if someone can produce the algorithm, I'll add 500 pts for a total of 1,000 pts.
0

Commented:

unsigned long get_human_check_id(unsigned long id)
{
unsigned long terminalId = (unsigned long)PullTerminalId(id) * 10000;
unsigned long checkNbr = (unsigned)(id & 0xFFFF);
return terminalId + checkNbr;
}

okay, lets break it down:

the terminal id part is in bits 20 and up, then scaled up by 10000

the checknumber is in the lower 16 bits.

So to reverse it you need to take :

terminalid / 10000, then shift it left 20 bits

plus

the checknumber.

unsigned long get_human_check_id_rev(unsigned long id)
{

unsigned long rev1 = id / 10000;
rev1 <<=  20;
unsigned long rev2 = id & 0x0xFFFF;
return rev1 + rev2;
}

0

Commented:
'id >> 20' discards the lower 20 bits of any number - and this means loosing too much information to always restore the original value.
0

Commented:

No, the mask is correct - the original algoritm toggles bit0 if val&0xffff, thus checking bit0 is enough.
0

Author Commented:
jkr, you're correct in that bits are lost (16-19). However, those bits are not used in the production system.
0

Commented:
>>you're correct in that bits are lost (16-19)

No. You are loosing the bits 0-20(!) also by 'id >> 20' - this discards the lower 20 bits of any number
0

Author Commented:
>>>
No. You are loosing the bits 0-20(!) also by 'id >> 20' - this discards the lower 20 bits of any number
<<<
Actually the terminalId is set to >> 20. The checkNbr is then given 16 of those bytes by AND'ing it with FFFF (which effectively throws away everything above the 15th bit).

Therefore, the terminalId is bits 20 and above (which is then multiplied by 1000) and the checkNbr is bits 0-15. As a result, the only lost data is bits 16-19.
0

Commented:

1048577 >> 20 results in 1

1048977 >> 20 results in 1

Get the idea?
0

Author Commented:
You're absolutely correct. 1048577 >> 20 is equal to 1. However, that's only the first part of the equation.

unsigned long terminalId = (unsigned long)PullTerminalId(id) * 10000;
// PullTerminalId returns the passed value shifted right 20 places

The second part then takes the same starting value (1048577 in the example) and then moves its 15 left digits into another variable:
unsigned long checkNbr = (unsigned)(id & 0xFFFF);

Therefore,
* bits 0-15 go into local variable checkNbr
* bits 20+ got into local variable terminalId (where they're mult by 1000)

See what I mean. You're focusing only on the terminalId where the right-most 20 bits are intentionally removed. 16 of those bits are then isolated into checkNbr.

0

Commented:
>>However, that's only the first part of the equation

Yes, I see, but the relevant data is already lost... :-(
0

Author Commented:
But it's not lost as the first part of the equation doesn't alter the value used in the second. See what I mean?

The shifting of the bits occurs in a separate function on a variable local to that function. Back in the main calling function the original input value is being used again to then isolate bits 0-15.

I think what might be throwing you is that:
1048577 & 0xFFFF == 1
Looks very strange, but if you input the value into calc and then switch to binary, you'll see that only the left-most and right-most bit are on. AND'ing this value with 0xFFFF will yield the value 1. I think this is where you're thinking data is being lost when it isn't

So it breaks down like this where I've noted the impact of each function call or arithmetic operation in comments:

get_human_check_id(1048577);
// calling get_human_check_id with a value of 1048577

unsigned long get_human_check_id(unsigned long id)
{
// id == 1048577

unsigned long terminalId = (unsigned long)PullTerminalId(id) * 10000;
// calls PullTerminalId and then multiplies results by 1000
// id == 1048577
// terminalId == 1001

unsigned long checkNbr = (unsigned)(id & 0xFFFF);
// assigns checkNbr to the right 16 bits of the value in id
// id == 1048577
// terminalId == 1001
// checkNbr == 1

return terminalId + checkNbr;
// adds terminalId (1001) and checkNbr (1) and returns that value (1001)
}

unsigned PullTerminalId(unsigned long id)
{
// id == 1048577
return ((unsigned)(id >> 20));

// returns only the 20+ bits of id (but id is not changed)
}
0

Commented:
The algorithm cannot be reversed.

In order for it to be reversable, for every possible output of the get_human_check_id function, there would have to be only one possible input.  If two inputs to get_human_check_id generate the same output, then there is no way for the reverse function to determine which of those inputs to generate as its output.

2 to the 20th power (1048576) as an input to get_human_check_id generates an output of 10000.  An input of 10000 also generates an output of 10000.  So a reverse algorithm given an input of 10000 cannot determine what output to generate.  So the get_human_check_id algorithm is not reversable.
0

Commented:
>>>> What I need is a function that will do the reverse.
>>>> The algorithm cannot be reversed.

efn - and jkr in his later posts - is absolutely right. Bit shifting means reducing information as some bits turn to 0 independent of the source number. A reducing algorithm never is reverseable.

You should make some XOR operation instead:

z = x^y;
x = z^y;

Here bits are toggled if a bit is set in y or remain as it is if a bit of y is 0. Both operations will reverse the original bit when doing it again.

Regards, Alex

0

Author Commented:
Alex,

I have no control over the original function. I'm simply looking to see if I can produce the reverse of that function within the framework of their system. IOW, I know bits 16-19 are not used so that's not a problem. However, as efn said the major problem will be that since multiple inputs can result in the same output, then by definition, I'll never be able to reverse to the original value. Basically, it would be like trying to reverse engineer a hash code, which can't be reversed for the same reason.
0

Commented:
This function efficiently prints all possible solutions.  There shouldn't be more than 120 or so.

void find_originals(unsigned long xformed) {
int maxa = xformed / 10000;
int mina = (((int)xformed) - 65536 + 9999) / 10000;
int residue;
unsigned long a, b, result;
if (mina < 0) mina = 0;
if (maxa > 4095) maxa = 4095;
for(a = mina; a <= maxa; a++) {
residue = ((xformed - 10000*a) & 0xffff);
for(b = residue; b < blimit; b+= 65536) {
result = (a << 20u) + b;
printf("get_human_check_id(%u) = %u\n", result,
get_human_check_id(result);
}
}
}
0

Commented:
ooops, replace blimit with (1<<20).
0

Author Commented:
Very impressive ND. Thanks!
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.