首页
论坛
课程
招聘
[原创]加减乘除反汇编笔记与MagicNumber探究记录
2022-1-28 23:33 23971

[原创]加减乘除反汇编笔记与MagicNumber探究记录

2022-1-28 23:33
23971

综述

加减乘除作为编译器的基础计算方法,在反汇编中应用广泛,其中加法、减法、乘法比较容易,而除法非常困难,尤其底层优化,非常复杂。其中32位和64位编译在这部分非常相似,仅仅是寄存器改变和常数改变,优化方案不变。
 

加法

加法的反汇编略为简单,仅仅是add、inc指令的使用。
在我们实际的编程中,为了保证代码的逻辑性和可读性,往往会使得代码具有一定的冗余性。
故编译阶段,编译器会采用常量传播和常量折叠两种优化方案,将运行阶段的工作尽可能移到编译阶段去做。
常量传播:编译器将可将已经计算出的结果转化为常量,这样就减少了变量的使用。
常量折叠:编译器将可将已经常量与常量的计算,在编译阶段期间就计算出结果,直接使用。
加法一共三种情况,下面将简单做个实例:

  1. 变量加常量
  2. 常量加常量
  3. 变量加变量
    1
    2
    3
    4
    5
    6
    7
    //加法
    //变量加常量
    printf("n1 = %d\n", n1 + 1);
    //常量加常量
    printf("n1 = %d\n", 1 + 2);
    //变量加变量
    printf("n1 = %d\n", n1 + n2);
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    VS2022_release_x86:
    //变量加常量
    printf("n1 = %d\n", n1 + 1);
    00DC10E5  mov         eax,dword ptr [esp+44h
    00DC10E9  inc         eax 
    00DC10EA  push        eax 
    00DC10EB  push        offset string "n1 = %d\n" (0DC310Ch
    00DC10F0  call        printf (0DC1020h
    //常量加常量
    printf("n1 = %d\n", 1 + 2);
    00DC10F5  push        3 
    00DC10F7  push        offset string "n1 = %d\n" (0DC310Ch
    00DC10FC  call        printf (0DC1020h
    //变量加变量
    printf("n1 = %d\n", n1 + n2);
    00DC1101  mov         eax,dword ptr [esp+58h
    00DC1105  add         eax,dword ptr [esp+54h
    00DC1109  push        eax 
    00DC110A  push        offset string "n1 = %d\n" (0DC310Ch
    00DC110F  call        printf (0DC1020h)

 

减法

减法也比较简单,仅仅是sub、dec指令的使用。
减法一共三种情况,和加法类似:

  1. 变量减常量
  2. 常量减常量
  3. 变量减常量
    1
    2
    3
    4
    5
    6
    7
    //减法
    //变量减常量
    printf("n1 = %d\n", n1 - 1);
    //常量减常量
    printf("n1 = %d\n", 1 - 2);
    //变量减变量
    printf("n1 = %d \r\n", n1 - n2);
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    VS2022_release_x86:
     //变量减常量
     printf("n1 = %d\n", n1 - 1);
    00DC1114  mov         eax,dword ptr [esp+5Ch
    00DC1118  dec         eax 
    00DC1119  push        eax 
    00DC111A  push        offset string "n1 = %d\n" (0DC310Ch
    00DC111F  call        printf (0DC1020h
     //常量减常量
     printf("n1 = %d\n", 1 - 2);
    00DC1124  push        0FFFFFFFFh 
    00DC1126  push        offset string "n1 = %d\n" (0DC310Ch
    00DC112B  call        printf (0DC1020h
     //变量减变量
     printf("n1 = %d \r\n", n1 - n2);
    00DC1130  mov         eax,dword ptr [esp+6Ch
    00DC1134  sub         eax,dword ptr [esp+70h
    00DC1138  push        eax 
    00DC1139  push        offset string "n1 = %d \r\n" (0DC3118h
    00DC113E  call        printf (0DC1020h)

 

乘法

乘法在计算的时候会将带有常量的部分优化成lea eax,[eax*a+b]的形式,其中受限于汇编指令的规则,a只能是1/2/4/8,故无法如此处理的乘法计算,还是会以mul/imul进行计算。
mul为无符号乘法,imul为有符号乘法。我们在反汇编的时候可以从此判断变量的类型。
乘法一共有五种情况:

  1. 变量乘常量(常量值为非2的幂)
  2. 变量乘常量(常量值为2的幂)
  3. 两常量相乘
  4. 混合运算
  5. 两变量相乘
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    //乘法
    //变量乘常量(常量值为非2的幂)
    printf("n1 * 7 = %d\n", n1 * 7);      
    //变量乘常量(常量值为2的幂)
    printf("n1 * 8 = %d\n", n1 * 8);      
    //两常量相乘
    printf("3 * 3 = %d\n", 3 * 3);          
    //混合运算
    printf("n1 * 6 + 5 = %d\n", n1 * 6 + 5);
    //两变量相乘
    printf("n1 * n2 = %d\n", n1 * n2);
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    //乘法
     //变量乘常量(常量值为非2的幂)
     printf("n1 * 7 = %d\n", n1 * 7);      
    00451143  mov         eax,dword ptr [esp+74h
    00451147  add         esp,40h 
    0045114A  lea         ecx,[eax*8
    00451151  sub         ecx,eax 
    00451153  push        ecx 
    00451154  push        offset string "n1 * 7 = %d\n" (0453124h
    00451159  call        printf (0451020h
     //变量乘常量(常量值为2的幂)
     printf("n1 * 8 = %d\n", n1 * 8);      
    0045115E  mov         eax,dword ptr [esp+3Ch
    00451162  shl         eax,3 
    00451165  push        eax 
    00451166  push        offset string "n1 * 8 = %d\n" (0453134h
    0045116B  call        printf (0451020h
     //两常量相乘
     printf("3 * 3 = %d\n", 3 * 3);          
    00451170  push        9 
    00451172  push        offset string "3 * 3 = %d\n" (0453144h
    00451177  call        printf (0451020h
     //混合运算
     printf("n1 * 6 + 5 = %d\n", n1 * 6 + 5);
    0045117C  mov         eax,dword ptr [esp+4Ch
    00451180  lea         eax,[eax+eax*2
    00451183  lea         eax,[eax*2+5
    0045118A  push        eax 
    0045118B  push        offset string "n1 * 6 + 5 = %d\n" (0453150h
    00451190  call        printf (0451020h
     //两变量相乘
     printf("n1 * n2 = %d\n", n1 * n2);      
    00451195  mov         eax,dword ptr [esp+58h
    00451199  imul        eax,dword ptr [esp+54h
    0045119E  push        eax 
    0045119F  push        offset string "n1 * n2 = %d\n" (0453164h
    004511A4  call        printf (0451020h)

 

除法

相较于加法、减法和乘法。除法可是复杂太多了。具体正面过程在钱松林老师的《C++反汇编与逆向分析技术揭秘》一书中有详细描述。但是太厚了,我们要把书读薄,我们在这里提炼出骨干和易于记忆的点。
我们使用vs2019 x64的Release版本编译,x64和x86在加减乘除中区别不大。优化方案没有区别。
 

​1.除数为无符号2的幂

代码特征:shr
还原方法:C=2^n

1
2
3
4
5
6
7
8
9
10
11
12
 
  //1.除数为无符号2的幂
  printf("argc / 16 = %u\n", (unsigned)argc / 16); 
00007FF72988107D  lea         rcx,[string "argc / 16 = %u\n" (07FF72989E3E0h)] 
00007FF729881084  mov         edx,ebx 
00007FF729881086  shr         edx,4 
00007FF729881089  call        printf (07FF729881010h
  printf("argc / 16 = %llu\n", (unsigned long long)argc / 16);
00007FF72988108E  mov         rdx,rbx 
00007FF729881091  lea         rcx,[string "argc / 16 = %llu\n" (07FF72989E3F0h)] 
00007FF729881098  shr         rdx,4 
00007FF72988109C  call        printf (07FF729881010h)

 

2.除数为无符号非2的幂(上)

代码特征:mul / shr
还原方法:C=2^n/M

1
2
3
4
5
6
7
8
9
10
11
12
13
//2.除数为无符号非2的幂(上)
  printf("argc / 9 = %d", (unsigned)argc / 9); 
00007FF7298810A1  mov         eax,38E38E39h 
00007FF7298810A6  lea         rcx,[string "argc / 9 = %d" (07FF72989E408h)] 
00007FF7298810AD  mul         eax,ebx 
00007FF7298810AF  shr         edx,1 
00007FF7298810B1  call        printf (07FF729881010h
  printf("argc / 9 = %d", (unsigned long long)argc / 9);
00007FF7298810B6  mov         rax,0E38E38E38E38E38Fh 
00007FF7298810C0  lea         rcx,[string "argc / 9 = %d" (07FF72989E408h)] 
00007FF7298810C7  mul         rax,rbx 
00007FF7298810CA  shr         rdx,3 
00007FF7298810CE  call        printf (07FF729881010h)
1
2
3
4
5
公式:C=2^n/M
>>> pow(2,33)/0x38E38E39
8.999999998952262
>>> pow(2,67)/0x0E38E38E38E38E38F
9.0

 

3.除数为无符号非2的幂(下)

代码特征:mul / sub / shr / add / shr
因为是64位编译,多了步移。32位为乘减移加移。
还原方法:C=2^n/(2^32+M)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//3.除数为无符号非2的幂(下)
  printf("argc / 7 = %d", (unsigned)argc / 7);
00007FF7298810D3  mov         eax,24924925h 
00007FF7298810D8  lea         rcx,[string "argc / 7 = %d" (07FF72989E418h)] 
00007FF7298810DF  mul         eax,ebx 
00007FF7298810E1  mov         eax,ebx 
00007FF7298810E3  sub         eax,edx 
00007FF7298810E5  shr         eax,1 
00007FF7298810E7  add         edx,eax 
00007FF7298810E9  shr         edx,2 
00007FF7298810EC  call        printf (07FF729881010h
  printf("argc / 7 = %d", (unsigned long long)argc / 7);
00007FF7298810F1  mov         rax,2492492492492493h 
00007FF7298810FB  lea         rcx,[string "argc / 7 = %d" (07FF72989E418h)] 
00007FF729881102  mul         rax,rbx 
00007FF729881105  mov         rax,rbx 
00007FF729881108  sub         rax,rdx 
00007FF72988110B  shr         rax,1 
00007FF72988110E  add         rdx,rax 
00007FF729881111  shr         rdx,2 
00007FF729881115  call        printf (07FF729881010h)
1
2
3
4
5
6
公式  C =2^n/(2^32+M)
              =2^n/(2^64+M)
>>> pow(2,35)/(pow(2,32)+0x24924925)
6.99999999938882
>>> pow(2,67)/(pow(2,64)+0x2492492492492493)
7.0

​ 

4.除数为有符号2的幂

代码特征:cdq、cqo / and / add / sar
还原方法:C=2^n

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
  //4.除数为有符号2的幂
  printf("argc / -4 = %d", argc / 8192);
00007FF72988111A  mov         eax,ebx 
00007FF72988111C  lea         rcx,[string "argc / -4 = %d" (07FF72989E428h)] 
00007FF729881123  cdq 
00007FF729881124  and         edx,1FFFh 
00007FF72988112A  add         edx,eax 
00007FF72988112C  sar         edx,0Dh 
00007FF72988112F  call        printf (07FF729881010h
  printf("argc / -4 = %d", (long long)argc / 8192);
00007FF729881134  mov         rax,rbx 
00007FF729881137  lea         rcx,[string "argc / -4 = %d" (07FF72989E428h)] 
00007FF72988113E  cqo 
00007FF729881140  and         edx,1FFFh 
00007FF729881146  add         rdx,rax 
00007FF729881149  sar         rdx,0Dh 
00007FF72988114D  call        printf (07FF729881010h)
1
2
3
4
5
公式 C=pow(2,n)
>>> pow(2,13)
8192
>>> pow(2,13)
8192

 

5.除数为有符号负2的幂

代码特征:cdq、cqo / and / add / sar / neg
还原方法:C=-2^n

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
  //5.除数为有符号负2的幂
  printf("argc / -4 = %d", argc / -8192);  //变量除以常量,常量为2的幂
00007FF729881152  mov         eax,ebx 
00007FF729881154  lea         rcx,[string "argc / -4 = %d" (07FF72989E428h)] 
00007FF72988115B  cdq 
00007FF72988115C  and         edx,1FFFh 
00007FF729881162  add         edx,eax 
00007FF729881164  sar         edx,0Dh 
00007FF729881167  neg         edx 
00007FF729881169  call        printf (07FF729881010h
  printf("argc / -4 = %d", (long long)argc / -8192);  //变量除以常量,常量为2的幂
00007FF72988116E  mov         rax,rbx 
00007FF729881171  lea         rcx,[string "argc / -4 = %d" (07FF72989E428h)] 
00007FF729881178  cqo 
00007FF72988117A  and         edx,1FFFh 
00007FF729881180  add         rdx,rax 
00007FF729881183  sar         rdx,0Dh 
00007FF729881187  neg         rdx 
00007FF72988118A  call        printf (07FF729881010h)
1
2
3
4
5
公式 C=-pow(2,n)
>>> -pow(2,13)
-8192
>>> -pow(2,13)
-8192

 

6.除数为有符号非2的幂(上)

代码特征:imul / sar / mov / shr / add
还原方法:C=2^n/M

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
  //6.除数为有符号非2的幂(上)
  printf("argc / 9 = %d", argc / 9);  //变量除以常量,常量为非2的幂
00007FF72988118F  mov         eax,38E38E39h 
00007FF729881194  lea         rcx,[string "argc / 9 = %d" (07FF72989E408h)] 
00007FF72988119B  imul        ebx 
00007FF72988119D  sar         edx,1 
00007FF72988119F  mov         eax,edx 
00007FF7298811A1  shr         eax,1Fh 
00007FF7298811A4  add         edx,eax 
00007FF7298811A6  call        printf (07FF729881010h
  printf("argc / 9 = %d", (long long)argc / 9);  //变量除以常量,常量为非2的幂
00007FF7298811AB  mov         rax,1C71C71C71C71C72h 
00007FF7298811B5  lea         rcx,[string "argc / 9 = %d" (07FF72989E408h)] 
00007FF7298811BC  imul        rbx 
00007FF7298811BF  mov         rax,rdx 
00007FF7298811C2  shr         rax,3Fh 
00007FF7298811C6  add         rdx,rax 
00007FF7298811C9  call        printf (07FF729881010h)
1
2
3
4
5
公式:C=2^n/M
>>> pow(2,33)/(0x38E38E39)
8.999999998952262
>>> pow(2,64)/(0x1C71C71C71C71C72)
9.0

​ 

7.除数为有符号非2的幂(下)

代码特征:imul / add / sar / mov / shr / add
还原方法:C=2^n/M

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//7.除数为有符号非2的幂(下)
  printf("argc / 7 = %d", argc / 7);  //变量除以常量,常量为非2的幂
00007FF7298811CE  mov         eax,92492493h 
00007FF7298811D3  lea         rcx,[string "argc / 7 = %d" (07FF72989E418h)] 
00007FF7298811DA  imul        ebx 
00007FF7298811DC  add         edx,ebx 
00007FF7298811DE  sar         edx,2 
00007FF7298811E1  mov         eax,edx 
00007FF7298811E3  shr         eax,1Fh 
00007FF7298811E6  add         edx,eax 
00007FF7298811E8  call        printf (07FF729881010h
  printf("argc / 7 = %d", (long long)argc / 7);  //变量除以常量,常量为非2的幂
00007FF7298811ED  mov         rax,4924924924924925h 
00007FF7298811F7  lea         rcx,[string "argc / 7 = %d" (07FF72989E418h)] 
00007FF7298811FE  imul        rbx 
00007FF729881201  sar         rdx,1 
00007FF729881204  mov         rax,rdx 
00007FF729881207  shr         rax,3Fh 
00007FF72988120B  add         rdx,rax 
00007FF72988120E  call        printf (07FF729881010h)
1
2
3
4
>>> pow(2,34)/(0x92492493)
6.999999997962732
>>> pow(2,65)/(0x4924924924924925)
7.0

 

8.除数为有符号负非2的幂(上)

代码特征:imul / sar / mov / shr / add
乘移移移加-->相乘,右移,移动,右移,相加
还原方法:2^n/(2^32-M)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//8.除数为有符号负非2的幂(上)
  printf("argc / -5 = %d", argc / -5);  //变量除以常量,常量为负非2的幂
00007FF729881213  mov         eax,99999999h 
00007FF729881218  lea         rcx,[string "argc / -5 = %d" (07FF72989E438h)] 
00007FF72988121F  imul        ebx 
00007FF729881221  sar         edx,1 
00007FF729881223  mov         eax,edx 
00007FF729881225  shr         eax,1Fh 
00007FF729881228  add         edx,eax 
00007FF72988122A  call        printf (07FF729881010h
  printf("argc / -5 = %d", (long long)argc / -5);  //变量除以常量,常量为负非2的幂
00007FF72988122F  mov         rax,9999999999999999h 
00007FF729881239  lea         rcx,[string "argc / -5 = %d" (07FF72989E438h)] 
00007FF729881240  imul        rbx 
00007FF729881243  sar         rdx,1 
00007FF729881246  mov         rax,rdx 
00007FF729881249  shr         rax,3Fh 
00007FF72988124D  add         rdx,rax 
00007FF729881250  call        printf (07FF729881010h)
1
2
3
4
5
6
C = 2^n/(2^32-M)
  = 2^n/(2^64-M)
>>> -pow(2,33)/(pow(2,32)-0x99999999)
-4.99999999825377
>>> -pow(2,65)/(pow(2,64)-0x9999999999999999)
-5.0

​ 

9.除数为有符号负非2的幂(下)

代码特征:imul / sub / sar / mov / shr / add
乘移移移加-->相乘,相减,右移,移动,右移,相加
还原方法:2^n/(2^32-M)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//9.除数为有符号负非2的幂(下)
  printf("argc / -7 = %d", argc / -7);  //变量除以常量,常量为负非2的幂
00007FF729881255  mov         eax,6DB6DB6Dh 
00007FF72988125A  lea         rcx,[string "argc / -7 = %d" (07FF72989E448h)] 
00007FF729881261  imul        ebx 
00007FF729881263  sub         edx,ebx 
00007FF729881265  sar         edx,2 
00007FF729881268  mov         eax,edx 
00007FF72988126A  shr         eax,1Fh 
00007FF72988126D  add         edx,eax 
00007FF72988126F  call        printf (07FF729881010h
  printf("argc / -7 = %d", (long long)argc / -7);  //变量除以常量,常量为负非2的幂
00007FF729881274  mov         rax,0B6DB6DB6DB6DB6DBh 
00007FF72988127E  lea         rcx,[string "argc / -7 = %d" (07FF72989E448h)] 
00007FF729881285  imul        rbx 
00007FF729881288  sar         rdx,1 
00007FF72988128B  mov         rax,rdx 
00007FF72988128E  shr         rax,3Fh 
00007FF729881292  add         rdx,rax 
00007FF729881295  call        printf (07FF729881010h)
1
2
3
4
5
6
C = 2^n/(2^32-M)
  = 2^n/(2^64-M)
>>> pow(2,34)/(pow(2,32)-0x6DB6DB6D)
-6.999999997962732
>>> pow(2,65)/(pow(2,64)-0x0B6DB6DB6DB6DB6DB)
-7.0

 

总结:

图片描述

 

 

如何判别除数是多少

想要判别除数是多少,根据上面总结的特征就可以很好的判断,通过观察可以轻松得到以下判别法:
1、当简单右移发生的时候,说明是第1种情况【除数为无符号2的幂】。
2、判断是否有cdq、cdo拓展指令,如果有判断是4、5两种情况【除数为有符号2的幂】,还原方法和第一点一致,有neg加负号。
3、判断是imul还是mul,若是mul为一定为无符号乘法,即2、3两种情况【除数为无符号非2的幂】。紧接着判断其行为,若是简单乘移,则为2,还原公式为C=2^n/M;若是乘减移加移,则为3,还原公式为C=2^n/(2^32+M)。
4、判断是imul还是mul,若是imul为一定为有符号乘法,
当MagicNumber>0,无SUB/ADD调整指令时,为情况6;
当MagicNumber<0,有ADD时,为情况7; 当MagicNumber<0,无SUB/ADD调整指令时,为情况8; 当MagicNumber>0,有SUB时,为情况9;
可以这样记忆,除数为负数的两种情况:M为正,有调整指令;M为负,无调整指令。
把有调整指令记作负,即负负得正的规律。一个为负,除数为负。两个为负数,则为正。
若为情况6、7,计算公式为:C=2^n/M;
若为情况8、9,计算公式为:C=2^n/(2^32-M)

 

经验法还原

F5还原就不说了,在无优化的环境下还原还好,加入流水线等优化,或者无法F5的场景下,F5出来的内容帮助不是很大。
这是使用经验的方法,进行还原的。
总共就三个公式,一个个尝试,选取精度最高的一个。
公式1:C=pow(2,n)
公式2:C=2^n/(2^32+M)
公式3:C=2^n/(2^32-M)
这样可行的理由:因为MagicNumber是由操作系统生成的,精度通常为小数点后九位以上。使用错误的还原方式,还原出的效果差距很大,即使凑巧有和整数很接近的数,比较精度选取精度高的数,就可以还原出正确的除数。当然,这种方法没有被数学证明,可能会有特殊数,不过普适性的优点已经足够引诱我们使用这个方法了。
​感兴趣的同学可以写个DEMO测试一下,也可以锻炼写工具的能力。

 

 

定式不可靠

请不要盲目遵从定式,在玩熟以后多留点心眼。
敌手嵌套内联汇编可能会产生陷阱导致翻译错误。

 

 

探究MagicNumber

我在学习这一阶段的时候,对MagicNumber的生成,产生了浓厚的兴趣。很想弄清楚是怎么产生的,但是网上的教程太少了,搜了很多资料还是很少,只能慢慢研究。
根据钱老师的《C++反汇编与逆向分析技术揭秘》中的引导,我找到了对应版本的C2.dll。大家找的时候可以使用Everything去查找相应版本的DLL,一定要相同版本。并在科锐的引导下进行了反汇编翻译,为了翻译的统一性和权威性,我们这里使用钱老师在书中附带的翻译版本。
PS:如果目标是逆向的话,C2的代码可以尝试翻译一下,可让新手获益良多,这里针对算法进行讲解。

 

Main函数:
钱老师使用内联汇编模拟了除法的有符号数计算,是我们上表中6、7、8、9四种情况。我们从中可以看出有符号数计算的细节:
nDivisor >= 0 和 nMagicNumber > 0 不需要增加add
nDivisor >= 0 和 nMagicNumber < 0 增加add
nDivisor < 0 和 nMagicNumber > 0 增加sub
nDivisor < 0 和 nMagicNumber < 0 不需要增加sub
然后是一个遍历进行循环测试

 

GetMagic函数:
首先进行函数表的匹配,如果是MagicTable中的数,之间进行使用。
如果不在MagicTable中,则从32位起进行计算。先进行预处理计算各种值,然后最关键的是do循环,不断增加nExcBase,即右移的次数。然后达到右移次数的约束条件,约束条件的证明在《C++反汇编与逆向分析技术揭秘》中有具体的证明。但是这里的循环条件是深度优化的,我看了很久,等价替换证明了很久,也不得要领。如果后面有更深的理解再行补上。
while ( q1 < nAbsDivC - r2 || q1 == nAbsDivC - r2 && !r1 );

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
int GetMagic(unsigned int nDivC, int *nOutExpInc)
{
//   if ((int)nDivC >= 3 && nDivC < 13)
//   {
//     *nOutExpInc = MagicTable[nDivC].nExpInc;
//     return MagicTable[nDivC].nMagic;
//   }
 
  unsigned int nAbsDivC = abs(nDivC);
  int nExcBase = 31;
 
  // t = 2^31 if nDivC > 0
  // or t = 2^31 + 1 if nDivC < 0
  unsigned int t = (nDivC >> 31) + EXP31;
 
  // |nc| = t - 1 - rem(t, |nDivC|)
  unsigned int nLargestMultiple  = t - t % nAbsDivC - 1;
  unsigned int q1 = EXP31 / nLargestMultiple;
  unsigned int r1 = EXP31 - nLargestMultiple * q1;
  unsigned int nMagicNumber = EXP31 / nAbsDivC;
  unsigned int r2 = EXP31 - nAbsDivC * nMagicNumber;
  do
  {
    r1 *= 2;
    q1 *= 2;
    ++nExcBase;
    if ( r1 >= nLargestMultiple )
    {
      ++q1;
      r1 -= nLargestMultiple;
    }
    r2 *= 2;
    nMagicNumber *= 2;
    if ( r2 >= nAbsDivC )
    {
      ++nMagicNumber;
      r2 -= nAbsDivC;
    }
  }
  while ( q1 < nAbsDivC - r2 || q1 == nAbsDivC - r2 && !r1 );
  nMagicNumber++;
  if ( (int)nDivC < 0 )
    nMagicNumber = -(int)nMagicNumber;
  *nOutExpInc = nExcBase - 32;
  return nMagicNumber;
}

在网上查询资料的过程中,发现了唯一一篇和MagicNumber相关的博客,该博客从正向实现了除数为无符号数的除法。我看了一下参考文献,未在其中发现vc6.0的约束条件,而是使用了更加宽泛的约束条件。在科锐学习的时间是如此的紧张,借用新年假期记录详细已然奢侈,便不在深入研究下去。
https://zhuanlan.zhihu.com/p/151038723
两篇相关论文供参考:
Division by Invariant Integers using Multiplication
Integer Division by Constants Optimal Bounds

 

上述内容的参考文献和代码都在附录里面提供了,感兴趣的同学可以研究一下。


看雪招聘平台创建简历并且简历完整度达到90%及以上可获得500看雪币~

最后于 2022-1-29 00:21 被瑞皇编辑 ,原因:
上传的附件:
收藏
点赞7
打赏
分享
最新回复 (4)
雪    币: 400
活跃值: 活跃值 (313)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
冷酷的果冻 活跃值 2022-1-28 23:54
2
1
总结得非常到位,果断收藏!
雪    币: 184
活跃值: 活跃值 (200)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
mb_krvlpodl 活跃值 2022-1-29 17:22
3
1
很有帮助
雪    币: 4924
活跃值: 活跃值 (2572)
能力值: ( LV9,RANK:195 )
在线值:
发帖
回帖
粉丝
天水姜伯约 活跃值 4 2022-2-7 23:37
4
0
你可以看一下Hacker's delight这本书,里面有对除数为常数的快速除法算法的详细内容
雪    币: 1044
活跃值: 活跃值 (1006)
能力值: ( LV4,RANK:55 )
在线值:
发帖
回帖
粉丝
瑞皇 活跃值 2022-2-8 00:04
5
0
天水姜伯约 你可以看一下Hacker's delight这本书,里面有对除数为常数的快速除法算法的详细内容
好的,谢谢您的指点!有时间我一定详细阅读您推荐的这本书!
游客
登录 | 注册 方可回帖
返回