Binary lookup
 

News:

29 December 2022 - PtokaX 0.5.3.0 (20th anniversary edition) released...
11 April 2017 - PtokaX 0.5.2.2 released...
8 April 2015 Anti child and anti pedo pr0n scripts are not allowed anymore on this board!
28 September 2015 - PtokaX 0.5.2.1 for Windows 10 IoT released...
3 September 2015 - PtokaX 0.5.2.1 released...
16 August 2015 - PtokaX 0.5.2.0 released...
1 August 2015 - Crowdfunding for ADC protocol support in PtokaX ended. Clearly nobody want ADC support...
30 June 2015 - PtokaX 0.5.1.0 released...
30 April 2015 Crowdfunding for ADC protocol support in PtokaX
26 April 2015 New support hub!
20 February 2015 - PtokaX 0.5.0.3 released...
13 April 2014 - PtokaX 0.5.0.2 released...
23 March 2014 - PtokaX testing version 0.5.0.1 build 454 is available.
04 March 2014 - PtokaX.org sites were temporary down because of DDOS attacks and issues with hosting service provider.

Main Menu

Binary lookup

Started by bastya_elvtars, 03 January, 2007, 18:01:55

Previous topic - Next topic

0 Members and 1 Guest are viewing this topic.

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. ;-)
Everything could have been anything else and it would have just as much meaning.

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?
Everything could have been anything else and it would have just as much meaning.

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

Quote from: Mutor on 03 January, 2007, 23:46:49
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.

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?
Everything could have been anything else and it would have just as much meaning.

Herodes

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

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

bastya_elvtars

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

CrazyGuy

what are the values of b and c ?

bastya_elvtars

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

CrazyGuy

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 ?

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

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

CrazyGuy

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 ?

CHILLCODE?

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.

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

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

SMF spam blocked by CleanTalk