Conversation

New blog post: "Bit-Twiddling: Optimising AArch64 Logical Immediate Encoding (and Decoding)"

dougallj.wordpress.com

Bit-Twiddling: Optimising AArch64 Logical Immediate Encoding (and Decoding)

I came up with a (seemingly) new method to encode bitmask immediate values on ARM64. This really isn’t worth optimising – clarity and verifiability are more important – but itR…

Replying to

RE “little hand-wavy”: the notion of minimal patterns might be unnecessary. If (x rotate r) == x, and r is coprime to the bit width of x, then I think it follows that (x rotate 1) == x (i.e. x is 0 or ~0). As x is not those values, r must divide the power of two bit width.

Replying to

and

Slightly generalised: (x rotate r) == x implies (x rotate gcd(r, bit width of x)) == x. In our case, r == o+z, and we know from construction of o and z that x rotated by less than o+z is not equal to x. Hence the gcd has to equal r, hence r divides bit width.

Replying to

Having thought about it a bit, I really like this proof, thanks! I’ll try to add it to the post tomorrow.

Pete Cawley

@corsix

Replying to

@dougallj

As for why x == x rot r and x == x rot s implies x == x rot gcd(r, s): x == x rot r implies x == x rot (i * r) for any integer i (by induction). Extended gcd gives gcd(r, s) == i * r + j * s. Then x == (x rot (i * r)) rot (j * s) == x rot (i * r + j * s) == x rot gcd(r, s).

2:50 PM · Oct 31, 2021Twitter Web App