Home.... | log in.... | Pub my question! | Sign-up....
Java-index >> Other Topics >> Algorithms

Binary Shift Left Algorithm

Hi,

One of our client has an DOS exe which will accept 32 bit Signed Integer(Max length-6digits) and produce one more 6 digit number. It is using 40 steps to generate the output. To generate the output, binary shift left algorithm is used. But if overflow(out of range) happens, the logic is changed to make the number as valid(Inside the range). Unfortunately, there is no source code/documents/information of how this exe is working is available. Would like to trace the algorithm and have to extend the logic. Given below is the output generated using the exe.

Ex/.

Input Number 1

Hex S.noDecimal Value(generated by me)

202

414

828

10316

20432

40564

806128

1007256

2008512

40091024

800A2048

1000B4096

2000C8192

4000D16384

8000E32768

10000F65536

2000010131072

4000011262144

8000012524288

100000131048576

200000142097152

400000154194304

800000168388608

10000001716777216

20000001833554432

40000001967108864

80000001a134217728

100000001b268435456

200000001c536870912

400000001d1073741824

800000001e-2147483648(until this place, shift left works fine and after this overflow happens) so the logic is changed to make the number a valid one and again the same shift left is followed until overflow.

779829901f2006460816

ef30532020-282045664

a9f88fd021-1443328048

2469363022610874928

48d26c60231221749856

91a4d8c024-1851467584

54d19810251423022096

a9a33020262846044192

24de49d027618547664 (last 6 digit is the output).

One more example:

Input 31

6 06

c 112

18 224

30 348

60 496

c0 5192

180 6384

300 7768

600 81536

c00 93072

1800 A6144

3000 B12288

6000 C24576

c000 D49152

18000 E98304

30000 F196608

60000 10393216

c0000 11786432

180000 121572864

300000 133145728

600000 146291456

c00000 1512582912

1800000 1625165824

3000000 1750331648

6000000 18100663296

c000000 19201326592

18000000 1a402653184

30000000 1b805306368

60000000 1c1610612736

c0000000 1d-1073741824

f7982990 1e-141022832(logic changes here)

98a87ab0 1f-1733789008

46c8dcf0 201187568880

8d91b9e0 21-1919829536

6cbb5a50 221824217680

d976b4a0 23-646531936

c57540d0 24-982171440

fd72a830 25-42817488

8d7d79f0 26-1921156624

6d62da70 271835194992194992 output

Any help to trace the change in logic is appreciated.

Thanks in Advance.

Kavitha

[2734 byte] By [Kavi_herea] at [2007-9-29 14:32:19]
«« how to compare strings
»» get an array value as an int
# 1
hmm, i've seen this [url= http://board.win32asmcommunity.net/showthread.php?s=e6c3df8d75711252d5c3ddd28199bf2e&threadid=15737]somewhere[/url] before ...
silk.ma at 2007-7-15 5:18:16 > top of Java-index,Other Topics,Algorithms...
# 2
Yes, I am trying this from few days and I am trying from different forums too. Final aim is to get a solution.
Kavi_herea at 2007-7-15 5:18:16 > top of Java-index,Other Topics,Algorithms...
# 3
If you have the DOS exe and legal rights to itwhy don't you just use a disassembler and figure out what it does from the assembler code.
tschodta at 2007-7-15 5:18:16 > top of Java-index,Other Topics,Algorithms...
# 4
After the "overflow" error it seems again to correctly shift left.So emulate the involved processor flags Carry, Sign, Overflow.1. Detect the error: the most difficult partif Sign == 1(-) and before not so2. When error:shift leftor 0x77982990
joop_eggena at 2007-7-15 5:18:16 > top of Java-index,Other Topics,Algorithms...
# 5

> Any help to trace the change in logic is appreciated.

Actually a quite simple algorithm

long magic = 0x77982990L;

long number = 3;

for (int i=0; i<40; i++) {

if ((number & 0x80000000L) != 0) {

number = (number << 1) ^ magic;

number = number & 0xffffffffL;

} else {

number = (number << 1);

}

System.out.println(number);

}

polytroposa at 2007-7-15 5:18:16 > top of Java-index,Other Topics,Algorithms...
# 6
HI polytropos, The logic is working perfect. Thanks for your timely help...For All: Thanks for all of you who responded my query.
Kavi_herea at 2007-7-15 5:18:16 > top of Java-index,Other Topics,Algorithms...
# 7

Nice work figuring out the algorithm.

An alternative implementationclass Kavi {

static private final long magic = 0x3bcc14c8;

static private final long limit = 0x7fffffff;

static private final int iterations = 40; // 0x28

static private final long mask = 1000000;

static public long kavify(long number) {

for (int i=0; i<iterations; ++i) {

if (number > limit) number = (number ^ magic) & limit;

number <<= 1;

}

return number % mask;

}

public static void main(String[] argv) {

long number = Long.parseLong(argv[0]);

System.out.println(kavify(number));

}

}

tschodta at 2007-7-15 5:18:16 > top of Java-index,Other Topics,Algorithms...
# 8

> HI polytropos,

> The logic is working perfect. Thanks for your timely

> help...

Please note if you are using this algorithm in any security related procedure: the function takes 1,000,000 different numbers as input but produces only 62,500 different numbers as output. The inventor of this algorithm has not done his job.

polytroposa at 2007-7-15 5:18:16 > top of Java-index,Other Topics,Algorithms...
# 9
HiI am aware of pros & Cons of the algorithm. Anyway Thanks for ur help once again
Kavi_herea at 2007-7-15 5:18:16 > top of Java-index,Other Topics,Algorithms...
Other Topics
Algorithms

Other Topics New Topic

Other Topics Hot Topic

Other Topics

All Classified