Recognize compiler integer division patterns with magic constants

[ubitux]

Using http://flaviojslab.blogspot.com/2008/02/integer-division.html as (unverified and maybe incomplete) reference, we can create the following mult.c sample:

unsigned int f_0x069C16BD_s0(unsigned int x) { return x * 665/25756; }
unsigned int f_0x10624DD3_s4(unsigned int x) { return x * 1/250; }
unsigned int f_0x10624DD3_s5(unsigned int x) { return x * 1/500; }
unsigned int f_0x10624DD3_s6(unsigned int x) { return x * 1/1000; }
unsigned int f_0x2AAAAAAB_s0(unsigned int x) { return x * 1/6; }
unsigned int f_0x30C30C31_s3(unsigned int x) { return x * 1/42; }
unsigned int f_0x38E38E39_s1(unsigned int x) { return x * 1/9; }
unsigned int f_0x4EC4EC4F_s3(unsigned int x) { return x * 1/26; }
unsigned int f_0x51EB851F_s5(unsigned int x) { return x * 1/100; }
unsigned int f_0x55555556_s0(unsigned int x) { return x * 1/3; }
unsigned int f_0x66666667_s1(unsigned int x) { return x * 1/5; }
unsigned int f_0x66666667_s2(unsigned int x) { return x * 1/10; }
unsigned int f_0x66666667_s3(unsigned int x) { return x * 1/20; }
unsigned int f_0x66666667_s4(unsigned int x) { return x * 1/40; }
unsigned int f_0x66666667_s5(unsigned int x) { return x * 1/80; }
unsigned int f_0x66666667_s6(unsigned int x) { return x * 1/160; }
unsigned int f_0x66666667_s7(unsigned int x) { return x * 1/320; }
unsigned int f_0x66666667_s8(unsigned int x) { return x * 1/640; }
unsigned int f_0x6BCA1AF3_s5(unsigned int x) { return x * 1/76; }
unsigned int f_0x88888889_s8(unsigned int x) { return x * 1/480; }
unsigned int f_0x92492493_s3(unsigned int x) { return x * 1/14; }
unsigned int f_0xA0A0A0A1_s7(unsigned int x) { return x * 1/204; }
unsigned int f_0xAAAAAAAB_s1(unsigned int x) { return x * 1/3; }
unsigned int f_0xAAAAAAAB_s2(unsigned int x) { return x * 1/6; }
unsigned int f_0xAAAAAAAB_s3(unsigned int x) { return x * 1/12; }
unsigned int f_0xAAAAAAAB_s4(unsigned int x) { return x * 1/24; }
unsigned int f_0xAE147AE1_s5(unsigned int x) { return x * 17/800; }
unsigned int f_0xB21642C9_s5(unsigned int x) { return x * 1/46; }
unsigned int f_0xB60B60B7_s5(unsigned int x) { return x * 1/45; }
unsigned int f_0xBA2E8BA3_s3(unsigned int x) { return x * 1/11; }
unsigned int f_0xEA0EA0EB_s0(unsigned int x) { return x * 32/35; }

With a high optimization level, GCC will generate code making use of constants (in most cases): gcc -O3 -c mult.c -o mult.o

In ghidra, this will result in functions like:

ulong f_0x51EB851F_s5(uint uParm1)
{
  return (ulong)uParm1 * 0x51eb851f >> 0x25;
}

This is one I actually came across in the wild (this is the division by 100).

Ideally, these pattern should be recognized and replaced in the decompiler view.

Env: Ghidra 9.0.4, Linux x86_64, GCC 8.3.0

[MrSapps]

A related feature would be to have an option to convert shifts to multiply/divides too

[caheckman]

The decompiler already has logic for recognizing optimized division, but it seems to be missing some (newer?) forms. Working towards fixing the problem.

[clienthax]

@caheckman @ryanmkurtz Any reason this was closed, still seems to be not implemented?

[ryanmkurtz]

Perhaps it was this? 2463cad

[clienthax]

@ryanmkurtz Hmm possibly, opened a new issue anywho :)