Binary lookup

[bastya_elvtars]

Hello,
I'd like to make my own binary lookup implementation and would like to get some hints. Right now I will read this and post my progress.
I expect help specifically from chill. ;-)

[bastya_elvtars]

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?

[CrazyGuy]

ermm, what does it exactly do other then looking for a predefined number in a predefined range ?
and what's the use ?  :-\

[bastya_elvtars]

http://lua-users.org/wiki/TableExtension

Yeah, thanks, although I have already written my own and I learnt more that way.

[bastya_elvtars]

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?

[Herodes]

Sure,... there is a pure Lua library for this ...

http://luaforge.net/projects/bit/

[bastya_elvtars]

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.

[CrazyGuy]

what are the values of b and c ?

[bastya_elvtars]

what are the values of b and c ?

Depends. They are 3232235820 and 4294967232 now, respectively.

[CrazyGuy]

hmm, been trying to do some calculations with those numbers but it kinda screws up somewhere   

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 ?

[bastya_elvtars]

No, I am over that part, thanks. BTW to show you what I am about, see this and this.
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. :-)

[CHILLCODE?]

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.

[bastya_elvtars]

Thanks for help, I will look at this tomorrow - and don't worry, I will publish the work when it is done.

[CrazyGuy]

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 ?

[CHILLCODE?]

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.

[bastya_elvtars]

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.

[bastya_elvtars]

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]