Bit Manipulation Challenge
I want to take an IP address routing prefix in CIDR [1] notation (i.e. the 24 in "192.168.100.14/24") and convert it into subnet form (i.e. 255.255.255.0). I came up with 4 ways to do that (see below), but none stand out as best (although #3 and #4 seem a bit more straightforward as they avoid the `max` temp). How would you go about it? Here are the ways I came up with: cidr := 24. shift := 32 - cidr. max := #[ 255 255 255 255 ] asInteger. "1." ((max bitShift: shift negated) bitShift: shift) asByteArray. "2." (max bitClear: (2 raisedTo: shift) - 1) asByteArray. "3." ((2 raisedTo: shift) - 1) bitInvert32 asByteArray. "4." (((2 raisedTo: cidr) - 1) bitShift: shift) asByteArray 1. https://en.wikipedia.org/wiki/Classless_Inter-Domain_Routing ----- Cheers, Sean -- Sent from: http://forum.world.st/Pharo-Smalltalk-Users-f1310670.html
On Mon, 20 Jul 2020 at 23:19, Sean P. DeNigris <sean@clipperadams.com> wrote:
I want to take an IP address routing prefix in CIDR [1] notation (i.e. the 24 in "192.168.100.14/24") and convert it into subnet form (i.e. 255.255.255.0). I came up with 4 ways to do that (see below), but none stand out as best (although #3 and #4 seem a bit more straightforward as they avoid the `max` temp).
How would you go about it?
Here are the ways I came up with: cidr := 24. shift := 32 - cidr. max := #[ 255 255 255 255 ] asInteger. "1." ((max bitShift: shift negated) bitShift: shift) asByteArray. "2." (max bitClear: (2 raisedTo: shift) - 1) asByteArray. "3." ((2 raisedTo: shift) - 1) bitInvert32 asByteArray. "4." (((2 raisedTo: cidr) - 1) bitShift: shift) asByteArray
To me the most complicated ones have the "subtract 1" - it makes it harder to reason about. I'd also guess "3" and "4" are slowest. "1." can be simplified by hardcoding max.... 5. (4294967295 bitShift: shift negated) bitShift: shift) asByteArray Additional alternative... 6. ((4294967295 bitShift: shift) rem: 4294967296) asByteArray And why not low-brow... 7. CIDRLookup at: cidr. cheers -ben
On Tue, Jul 21, 2020 at 02:17:59AM +0800, Ben Coman wrote:
On Mon, 20 Jul 2020 at 23:19, Sean P. DeNigris <sean@clipperadams.com> wrote:
I want to take an IP address routing prefix in CIDR [1] notation (i.e. the 24 in "192.168.100.14/24") and convert it into subnet form (i.e. 255.255.255.0). I came up with 4 ways to do that (see below), but none stand out as best (although #3 and #4 seem a bit more straightforward as they avoid the `max` temp).
How would you go about it?
Here are the ways I came up with: cidr := 24. shift := 32 - cidr. max := #[ 255 255 255 255 ] asInteger. "1." ((max bitShift: shift negated) bitShift: shift) asByteArray. "2." (max bitClear: (2 raisedTo: shift) - 1) asByteArray. "3." ((2 raisedTo: shift) - 1) bitInvert32 asByteArray. "4." (((2 raisedTo: cidr) - 1) bitShift: shift) asByteArray
To me the most complicated ones have the "subtract 1" - it makes it harder to reason about. I'd also guess "3" and "4" are slowest.
"1." can be simplified by hardcoding max.... 5. (4294967295 bitShift: shift negated) bitShift: shift) asByteArray
Additional alternative... 6. ((4294967295 bitShift: shift) rem: 4294967296) asByteArray
And why not low-brow... 7. CIDRLookup at: cidr.
cheers -ben
This also seems to work for IPV4: (max << shift) asByteArray last: 4 Dave
Thanks for the ideas. I guess I'll stick with #1 for now, but I documented the others and appreciated the interesting conversation :) ----- Cheers, Sean -- Sent from: http://forum.world.st/Pharo-Smalltalk-Users-f1310670.html
participants (3)
-
Ben Coman -
David T. Lewis -
Sean P. DeNigris