Hello,
I'd like to make my own binary lookup implementation and would like to get some hints. Right now I will read this (http://www.cse.ucsc.edu/~pohl/CBDCourse/hw/hw5.html) and post my progress.
I expect help specifically from chill. ;-)
Don't bother, I've made one.
-- binary lookup routine
-- bastya_elvtars, 2007-01-03
-- some inspiration from CHILLCODE? production GeoIP Engine
-- We create an array of numbers.
arr={}
x=os.clock()
-- We look for a number between 2 others.
sval,eval=1,1000000000000000000000000000
-- the number we are looking for.
requirednumber=965
-- Some basic error check.
if requirednumber < sval or requirednumber > eval then error("required number out of range") end
-- This is basically a comparison.
function chknumber (midval)
if requirednumber == midval then return 0
elseif requirednumber < midval then return 1
elseif requirednumber > midval then return 2
end
end
function lookup()
-- start and finish dynamically get redeclared.
local start,finish,retval=sval,eval,nil
-- Scope of midval should be here, so it won't get nil when
-- re-entering the while loop below.
local midval
-- If chknumber() returns 0, then the number is found!
while retval~=0 do
midval=math.floor((start+finish)/2)
retval=chknumber(midval)
if retval == 1 then -- The required number < middle value
print("required number between",start,finish)
-- As such, we lower the finish value, it is the middle value.
finish=midval
elseif retval== 2 then -- The required number > middle value
print("required number between",start,finish)
-- We raise the start to the middle value.
start=midval
end
end
print("showing time wasted: "..(os.clock()-x).."secs")
end
lookup()
Any opinions?
ermm, what does it exactly do other then looking for a predefined number in a predefined range ?
and what's the use ? :-\
Quote from: Mutor on 03 January, 2007, 23:46:49
http://lua-users.org/wiki/TableExtension (http://lua-users.org/wiki/TableExtension)
Yeah, thanks, although I have already written my own and I learnt more that way.
ok, looks like I cannot get along this:
I've gotta do the following: I have 3 numbers: a,b, and c. I have to do the following:
xor(and(a,c),and(b,c))
b and c are static numbers, I have to find the smallest a value that makes the above bitwise operation's result 0. I need this for IP-range support. Can anone point me to the right direction?
Sure,... there is a pure Lua library for this ...
http://luaforge.net/projects/bit/
Quote from: Herodes on 08 January, 2007, 07:54:30
Sure,... there is a pure Lua library for this ...
http://luaforge.net/projects/bit/
Yes, and I use it (even hacked it), there is no problem with that, the lookup part is what I am asking about.
what are the values of b and c ?
Quote from: CrazyGuy on 08 January, 2007, 15:32:31
what are the values of b and c ?
Depends. They are 3232235820 and 4294967232 now, respectively.
hmm, been trying to do some calculations with those numbers but it kinda screws up somewhere :P
By principle though, if you want the xor to result in a 0, then the results of and(a,c) and and(b,c) must match
Value 1 Value 2 Xor
1 1 0
1 0 1
0 1 1
0 0 0
Does that help anywhere ?
No, I am over that part, thanks. BTW to show you what I am about, see this (http://library.thinkquest.org/28289/subnet.html) and this (http://www.ipprimer.com/bitbybit.cfm).
While we are at it, one use for the binary lookup is to check whether a number is in a particular (sorted) array without looping through the array. I tried that one, and it is soooo fast. :-)
okey you made the binary function yourself, and you learned a lot that way anyways, but I still wanted to to help so I tried a few things, but all this bitwise is a bit back but it seems to me the smallest a value is actualy the AND(b,c) just a little exsample, dunno if it's right
b:11100101 -bavalue
c:10101001 -cvalue
&
10100001 -Andresult
now the only value to set 'Andresult' Zero through XOR: is 10100001
we can be quite sure that AND'ing that with C or also B would actually return Andresult again,
since it was the result of an And operation
so a = AND(b,c)
but I think i missed the point I guess
furthermore are you trying to maybe do a binary search on CIDR ranges, that sounds quite interesting...
I think I also thaught once of that but have never come up with a good idea.
Thanks for help, I will look at this tomorrow - and don't worry, I will publish the work when it is done.
Quote from: CHILLCODE? on 09 January, 2007, 00:42:30
okey you made the binary function yourself, and you learned a lot that way anyways, but I still wanted to to help so I tried a few things, but all this bitwise is a bit back but it seems to me the smallest a value is actualy the AND(b,c) just a little exsample, dunno if it's right
b:11100101 -bavalue
c:10101001 -cvalue
&
10100001 -Andresult
now the only value to set 'Andresult' Zero through XOR: is 10100001
we can be quite sure that AND'ing that with C or also B would actually return Andresult again,
since it was the result of an And operation
so a = AND(b,c)
but I think i missed the point I guess
furthermore are you trying to maybe do a binary search on CIDR ranges, that sounds quite interesting...
I think I also thaught once of that but have never come up with a good idea.
yes, thats basically what I meant as well although
a = AND(b,c) does not seem to be right if the equation xor(and(a,c),and(b,c)) must result in a bitwise zero
AND(a,c) = AND(b,c) is what you mean right ?
Quote from: CrazyGuy on 09 January, 2007, 17:18:05
yes, thats basically what I meant as well although
a = AND(b,c) does not seem to be right if the equation xor(and(a,c),and(b,c)) must result in a bitwise zero
AND(a,c) = AND(b,c) is what you mean right ?
yup to get zero AND(a,c) = AND(b,c) is a must or?
but the smallest value for a in this case is AND(b,c) I think,
what makes sorta no sense, why look for a variable that you already have
and then set it XOR, that's why I think I missed something.
Umm, thanks for pointing this out, I have been waaaaaaaaaaaaay too lazy lately. I will then look into this from that point of view, especially because the extra function call introduces some overhead.
I think I found it out. Needs a little hack, because the bit library only accepts integer values, and therefore math.floor can lead to inaccuracies, but it actually works. Here it goes:
--[[
netmask calculation routine for RangeFucker
Does many things:
- gets a range from netmask, cidr
- converts IPs to and from binary/decimal/dotted formats
References:
http://library.thinkquest.org/28289/subnet.html
http://www.ipprimer.com/bitbybit.cfm
Uses the LuaBit library by Han Zhao: http://luaforge.net/projects/bit/
To load LuaBit library: edit package.path accordingly.
Thanks to chill and CrazyGuy for hints.
bastya_elvtars
]]
module("netmask",package.seeall)
package.path="I:/luabit/?.lua"
require "bit"
function iptodecbin(ip)
local err
local c=256^3
local decip=0
for b in string.gfind(ip,"(%d+)") do
local piece=tonumber(b)
if not piece or piece > 255 then
err=true
break
else
decip=decip+(piece*c)
c=c/256
end
end
if not err then
return decip,bit.tobits(decip)
end
end
function DecToIP(ip)
local tmp
local pt1,pt2,pt3,pt4
pt1=math.modf((ip)/256^3)
tmp=math.fmod((ip),256^3)
pt2=math.modf((tmp)/256^2)
tmp=math.fmod(tmp,256^2)
pt3=math.modf((tmp)/256)
pt4=math.fmod(tmp,256)
return pt1.."."..pt2.."."..pt3.."."..pt4
end
function CalcMaskFromCIDR(CIDR)
if CIDR < 33 then
local bittbl={}
local counter=0
for k=1,32 do
if counter == 32 then break end -- we reached 32 bits
counter=counter+1
if counter <= CIDR then
table.insert(bittbl,1)
else
table.insert(bittbl,1,0)
end
end
if #bittbl==32 then return bittbl end
end
end
function GetRange(decip,decmask)
local start,en=0,decip
local mid=math.floor((start+en)/2)
local x=os.clock()
while ret~=0 do
if en==start+1 then break end
mid=math.floor((start+en)/2)
if bit.band(mid,decmask)==bit.band(decip,decmask) then
en=mid
else
start=mid
end
print(start,mid,en)
end
print(os.clock()-x.." secs wasted")
if bit.band(mid,decmask)~=bit.band(decip,decmask) then mid=mid+1 end
decip1=mid
start,en=decip,2^32-1
local mid=math.floor((start+en)/2)
local x=os.clock()
while ret~=0 do
if en==start+1 then break end
mid=math.floor((start+en)/2)
if bit.band(mid,decmask)==bit.band(decip,decmask) then
start=mid
else
en=mid
end
print(start,mid,en)
end
if bit.band(mid-1,decmask)==bit.band(decip,decmask) then mid=mid-1 end
decip2=mid
print (DecToIP(decip1),DecToIP(decip2))
return DecToIP(decip1),DecToIP(decip2)
end
a=iptodecbin("160.114.118.255")
b=iptodecbin("255.255.255.0")
print(GetRange(a,b))[/quote]