Author Topic: Binary lookup  (Read 6284 times)

0 Members and 1 Guest are viewing this topic.

Offline bastya_elvtars

  • Forum God
  • ****
  • Posts: 3 745
  • Karma: +173/-7
  • The rock n' roll doctor
    • The FreshStuff3 Site
Binary lookup
« on: 03 January, 2007, 18:01:55 »
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. ;-)
Everything could have been anything else and it would have just as much meaning.

PtokaX forum

Binary lookup
« on: 03 January, 2007, 18:01:55 »

Offline bastya_elvtars

  • Forum God
  • ****
  • Posts: 3 745
  • Karma: +173/-7
  • The rock n' roll doctor
    • The FreshStuff3 Site
Re: Binary lookup
« Reply #1 on: 03 January, 2007, 21:27:21 »
Don't bother, I've made one.
Code: [Select]
-- 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?
Everything could have been anything else and it would have just as much meaning.

Offline CrazyGuy

  • Viking
  • ****
  • Posts: 506
  • Karma: +83/-20
    • ?????=-_The NightHawk_-=?????
Re: Binary lookup
« Reply #2 on: 03 January, 2007, 23:41:05 »
ermm, what does it exactly do other then looking for a predefined number in a predefined range ?
and what's the use ?  :-\

Offline bastya_elvtars

  • Forum God
  • ****
  • Posts: 3 745
  • Karma: +173/-7
  • The rock n' roll doctor
    • The FreshStuff3 Site
Re: Binary lookup
« Reply #3 on: 04 January, 2007, 00:28:15 »
http://lua-users.org/wiki/TableExtension

Yeah, thanks, although I have already written my own and I learnt more that way.
Everything could have been anything else and it would have just as much meaning.

Offline bastya_elvtars

  • Forum God
  • ****
  • Posts: 3 745
  • Karma: +173/-7
  • The rock n' roll doctor
    • The FreshStuff3 Site
Re: Binary lookup
« Reply #4 on: 08 January, 2007, 01:05:11 »
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?
Everything could have been anything else and it would have just as much meaning.

Herodes

  • Guest
Re: Binary lookup
« Reply #5 on: 08 January, 2007, 07:54:30 »
Sure,... there is a pure Lua library for this ...

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

Offline bastya_elvtars

  • Forum God
  • ****
  • Posts: 3 745
  • Karma: +173/-7
  • The rock n' roll doctor
    • The FreshStuff3 Site
Re: Binary lookup
« Reply #6 on: 08 January, 2007, 12:16:41 »
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.
Everything could have been anything else and it would have just as much meaning.

Offline CrazyGuy

  • Viking
  • ****
  • Posts: 506
  • Karma: +83/-20
    • ?????=-_The NightHawk_-=?????
Re: Binary lookup
« Reply #7 on: 08 January, 2007, 15:32:31 »
what are the values of b and c ?

Offline bastya_elvtars

  • Forum God
  • ****
  • Posts: 3 745
  • Karma: +173/-7
  • The rock n' roll doctor
    • The FreshStuff3 Site
Re: Binary lookup
« Reply #8 on: 08 January, 2007, 15:57:36 »
what are the values of b and c ?

Depends. They are 3232235820 and 4294967232 now, respectively.
Everything could have been anything else and it would have just as much meaning.

Offline CrazyGuy

  • Viking
  • ****
  • Posts: 506
  • Karma: +83/-20
    • ?????=-_The NightHawk_-=?????
Re: Binary lookup
« Reply #9 on: 08 January, 2007, 21:36:09 »
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 ?

Offline bastya_elvtars

  • Forum God
  • ****
  • Posts: 3 745
  • Karma: +173/-7
  • The rock n' roll doctor
    • The FreshStuff3 Site
Re: Binary lookup
« Reply #10 on: 08 January, 2007, 22:39:02 »
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. :-)
Everything could have been anything else and it would have just as much meaning.

Offline CHILLCODE?

  • Scripter
  • Member
  • ******
  • Posts: 31
  • Karma: +21/-0
Re: Binary lookup
« Reply #11 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

Code: [Select]
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.

Offline bastya_elvtars

  • Forum God
  • ****
  • Posts: 3 745
  • Karma: +173/-7
  • The rock n' roll doctor
    • The FreshStuff3 Site
Re: Binary lookup
« Reply #12 on: 09 January, 2007, 01:28:10 »
Thanks for help, I will look at this tomorrow - and don't worry, I will publish the work when it is done.
Everything could have been anything else and it would have just as much meaning.

Offline CrazyGuy

  • Viking
  • ****
  • Posts: 506
  • Karma: +83/-20
    • ?????=-_The NightHawk_-=?????
Re: Binary lookup
« Reply #13 on: 09 January, 2007, 17:18:05 »
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

Code: [Select]
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 ?

Offline CHILLCODE?

  • Scripter
  • Member
  • ******
  • Posts: 31
  • Karma: +21/-0
Re: Binary lookup
« Reply #14 on: 09 January, 2007, 21:14:21 »
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.

Offline bastya_elvtars

  • Forum God
  • ****
  • Posts: 3 745
  • Karma: +173/-7
  • The rock n' roll doctor
    • The FreshStuff3 Site
Re: Binary lookup
« Reply #15 on: 09 January, 2007, 21:51:44 »
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.
Everything could have been anything else and it would have just as much meaning.

Offline bastya_elvtars

  • Forum God
  • ****
  • Posts: 3 745
  • Karma: +173/-7
  • The rock n' roll doctor
    • The FreshStuff3 Site
Re: Binary lookup
« Reply #16 on: 10 January, 2007, 03:32:54 »
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:

Code: [Select]
--[[
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]
Everything could have been anything else and it would have just as much meaning.

PtokaX forum

Re: Binary lookup
« Reply #16 on: 10 January, 2007, 03:32:54 »