Skip to main content
gamedev.net
🔒 Locked

Modulus without modulus operator.

Started by Dirge Aug 16, 2006 at 8:58 PM 2 replies 1.2k views
Original Post
Dirge
Dirge
So I'm implementing a new bit stream (bit packing) class similar to what Jonathan Blow presented in his old gd mag articles and I've run into a performance concern when "un-packing" a value from the stream. Specifically there's a very intensive loop that for every bit in a value does a divide then modulus to get the byte and bit indices. Now for a 32-bit integer this is happening 32 times and for many iterations (this is for network data transmission code). I remember reading back a while ago that there is a way to do a modulus operation without having to actually call the operator but taking into account a few bit tricks when using integers. Can anyone point me to this information or explain how this might work. Your help is greatly appreciated and I thank you ahead of time.
"Artificial Intelligence: the art of making computers that behave like the ones in movies."www.CodeFortress.com
wyrzy
wyrzy
I think you can find what you're looking for at:
http://graphics.stanford.edu/~seander/bithacks.html
Raghar
Raghar
Quote:
Original post by Dirge
So I'm implementing a new bit stream (bit packing) class similar to what

there's a very intensive loop that for every bit in a value does a divide then modulus to get the byte and bit indices. Now for a 32-bit integer this is

happening 32 times and for many iterations (this is for network data transmission code).

Your help is greatly appreciated and I thank you ahead of time.


Could I ask you why are you using modulo AT ALL? You want to work with 32 bit register thus you need JUST register operations, not math. (even children that never learned modular arithmetic are able to do that)

While you might be confused by saying the bit shifts and other works are in some cases similar to modular arithmetic, bit shifts are of course preferable, not only in computer programming, but also in scientific works.

It looks you'd like to use just bits.
So it is probably something like

mov ebx, eax
shr ebx, ecx
and ebx, 0x1

in 64 assembly

mov rbx, rax
shr rbx, rcx
and rbx, 0x1

b = a & lookUpTable[c];
b >>>= d;
b &= lookUpTableB[d];

or this case, it would be better for you

b = (a >>> c) & 0x1;

Imagine registers as a boxes, and use pins to learn by practicing all registry operations.
Dirge
Dirge
Quote:
Original post by wyrzy
I think you can find what you're looking for at:
http://graphics.stanford.edu/~seander/bithacks.html


That was exactly what I was looking for, I have no clue how my searchs didn't find it. Thanks wyrzy!
"Artificial Intelligence: the art of making computers that behave like the ones in movies."www.CodeFortress.com

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.