Implying that x % 320 = x - floor(x / 320) * 320, all we need is to find floor(x / 320), which is "whole" divisions.
We need cool property.
I'll describe it using decimals system.
Assume you want to divide decimal by 500.
In other words, you want to find floor(x / 500).
Imagine you know already result, and this result is y.
then y*5*100 <= x
in other words, floor of (x/500) is how many y*5 fits into number floor(x / 100) which is just cut off two digits in the end
Now, same in binary: 320 = 32*10 = 32*2*5 = 64*5.
this means, that floor(x/320)=floor(floor(x/64)/5)
where floor(x/64) is simple bitwise shift right by 6. 64 = 2^6.
assume z = floor(x/64), then it is 10 bits long if x is 16 bits long.
now you need only make table to find floor(z/5), for all numbers 10 bits long.
but then you need to multiply result by 320 again.
I suggest using another table for this purpose.
other possible way is some divisibility property.
If latest 6 bits is discardable, all you need is to find remainder of divison by 5.
And, there is only 5 possible remainders: 0, 1, 2, 3, 4, 5.
Somehow (I guess) you may find it as for example in divisibility of 3 in decimals: all digits must have sum divisible by 3.
But, it can be slower.
Edit: easier. If you imagine
long division method from school,
you'll find that it will look as:
Code: Select all
xxxx xxxx xxxx xxxx |1 0100 0000
-1010 0000 0
.....
-1010 0000 0
....
subtracting 1 0100 0000 equivalent to subtracting 5 (101) shifted by 6.
from opposite, you can't subtract less than 1 0100 0000, this means shift is greater or equal to 6.
This means that it may subtract during process of division at following positions:
Code: Select all
xxxx xxxx xxxx xxxx |1 0100 0000
-101
-101
-10 1
...
-1 01
and result is equivalent to long division by 5 of shifted x by 6 with goal to get remainder.
result I mean remainder here. Three bits that you'll get, is same. Just because you do literally same.
This means: x % 320 = (floor(x/64)%5) * 64 + ( x % 64 ) = ( ((x >> 6) % 5) << 6) | (x & 0x3F)
where x & 0x3F is bitwise and.
With this method you need to precompute ((x % 5) << 6) table for 10 bits long numbers.
Edit: replaced ceil with floor.