Printable View
Hello,
Working on a new project that needs to identify ony USA based IP addesses.
I have a list of USA based IP's which I will convert to ranges of Longs.. example (3.0.0.0 - 3.255.255.255 = 218103808 - 22229811)
So I will place this list into memory somehow.
Would like suggestions on how best to find when in ip is in range from a list of about 7000 ranges?
thanks
Are you familiar with using AND OR XOR bit masking. That is the answer I'd think.Quote:
Originally Posted by axisdj
very weak when it comes to that, any help would be appreciated
IMHO, this seems to be another case where the Decimal data type might come in handy.
When looking at this page (which is what you're trying to filter for, I believe), we see that there isn't a great deal of rhyme-or-reason for the ranges.
Also, regardless of whether you go little-endian or big-endian on the bytes as they're placed into Longs. You're going to run into a byte that's >127. What that means is that you're going to have negative values for your Longs. To solve this problem, I'd tend to employ the Decimal type, which can hold much larger integers.
Then, it just seems that you have a lot of less-than and greater-than testing to do.
Good Luck,
Elroy
It seems that something like the following (along with all the ranges on the Nirsoft page) would get it done:
Enjoy,Code:
Option Explicit
Public Function MakeDecimalFromIP(ip As String) As Variant
' Input must be a correctly formatted IP address.
'
Dim a() As String
Dim s As String
'
a = Split(ip, ".")
s = Right$("00" & a(0), 3) & Right$("00" & a(1), 3) & Right$("00" & a(2), 3) & Right$("00" & a(3), 3)
MakeDecimalFromIP = CDec(s)
End Function
Public Function IP_IsInRange(IP_ToTest, IP_LowRange, IP_HighRange) As Boolean
Dim lo As Variant
Dim hi As Variant
Dim ip As Variant
'
lo = MakeDecimalFromIP(IP_LowRange)
hi = MakeDecimalFromIP(IP_HighRange)
ip = MakeDecimalFromIP(IP_ToTest)
'
IP_IsInRange = ip >= lo And ip <= hi
End Function
Elroy
EDIT1: Also, as you scan that Nirsoft page, you should see that you can do a tremendous amount of consolidating of those ranges, as they're contiguously connected. Also, I probably should have converted to Hex in my MakeDecimalFromIP, but it's going to work fine just as it is.
Ok.. the above is exactly what I was thinking, But I have 7000 ranges to check...
what would be the fastest way to do that?
make an array with the base value and the top valueQuote:
Originally Posted by axisdj
then run the array and figure if => than and < than
sorry guys, my fault for not giving more detail.
That was what I was going to do, traverse the array until I find a match. But I would need to do 100's of these per second the first time th ip visits ( would save it in a list for quicker access later). So I guess what I am asking is there a fast way to set up the array so that it would be searched as fast as possible to find a range match.
Thinking about it now, I could make the range Minimum number the index of the array??
WP
Quote:
Originally Posted by flyguille
I'm not quite clear as to how this translates into this, which BTW, equals 195,873,997.Quote:
Originally Posted by axisdj
Be that as it may, would it help to deal with the 4 "parts" individually?
ie ..
3 to 3
0 to 255
0 to 255
0 to 255
EDIT-1:
For example .. "to be checked" IP is 004.011.212.003
Your list of 7,000 has:
003.001.001.002 .. 1st in list
:
003.101.201.004
:
003.255.000.255 .. last in list
You'd know at "pass 1" that there is no 004 as the 1st "part", so, you're done
Please correct me if I've missed the (ahem) point.
Spoo
VB is very fast you can check against an array dozen of thousands of times per second.Quote:
Originally Posted by axisdj
Just take your time to measure.... it is simple numericals.
oh, and another thing.
you really don't needs to convert it to decimals, normally the Internet is build up in pre-assigned ranges to ISPs and are all BASED on the first and second number.
Don't use decimals.
uses ranges this way (first*256)+second, so it still Integer value.
so
private const Total = 1000
private LastInUse as integer
private Base(0 to Total-1) as long
private Top(0 to Total-1) as long
then
_ConnectionRequest
dim x as integer, y as integer
dim STRD as string
dim num as long
strd=.remoteIP
x=instr(strd,".")
y=instr(x+1,strd,".")
num=val(mid$(strd,1,x-1)) * 256 + val(mid$(strd,x+1,y-(x+1)))
if LastInUse>=0 then
for x=0 to LastInUse
if num>= base(x) and num <top(x) then ' Ok, is in USA.
next x
endif
EDIT: But if you want it FASTER, I recommend you to use LOOK UP TABLES.
IT is easy.
private IsInUSA(0 to 255, 0 to 255) as boolean
Configure the table one time.... TRUE if in USA, FALSE if not.
then...
_ConnectionRequest
dim x as integer, y as integer
dim STRD as string
strd=.remoteIP
x=instr(strd,".")
y=instr(x+1,strd,".")
if IsInUSA(val(mid$(strd,1,x-1)), val(mid$(strd,x+1,y-(x+1)))) then ' Is in USA.
Brilliant Answers guys, I was going in that direction
Thank you to all for your insight, will let you know how it turns out.
WP
Quote:
Originally Posted by flyguille
FYI: However you are creating your ranges, if you sort them in a way that the ranges that contain the most possible IPs are at the top of the array/list, then you are likely to match those first. A more advanced option would be a modified binary search. A binary search can determine if a value fits within a list of 1 million items, in 20 iterations or less. If interested, may want to search the forum on the key words: binary search
Unless I'm confused, which I seem to be this evening, the attached does what you're looking for.
Enjoy,
Elroy
EDIT1: And I'm not saying it couldn't be done better and/or faster, but that certainly seems to get it done. Truth be told, if it were for myself, there are quite a few areas I'd tend to clean up before I'd actually use it. But again, it works.
EDIT2: Also, the more I think about it, this is a place where you could probably use Currency and still not have to deal with negative numbers. You could just ignore the four decimal places and still have enough precision, especially if you went to hex before putting into Currency. Also, Currency comparisons are almost certainly faster than Decimal comparisons. But I'll let you (or others) sort that out.
EDIT3: Actually, no need to convert the IP to hex. Currency has plenty of precision without needing to do this. Therefore, even faster. But one thing you could do is to convert the arrays to Currency arrays when they're loaded. That would certainly speed up things, especially when checking multiple IPs to see if they're in the USA.
The single line solution I gave him, is insuperable, it stand up against DoS attacks. Other way it would be floodable from foreign sources.
axis
Picking up on LaVolpe's search suggestion, I found these 2 by CVMichael.
Sort the array first: http://www.vbforums.com/showthread.p...-algorithm)&s=
Then do binary search: http://www.vbforums.com/showthread.p...ghlight=binary
Spoo
Can you give an example of how you're receiving the IP Ranges? is it an actual range or something like CIDR notation?.
Here's some routines you can use, but please note The IP's and Masks are in network byte order (Big Endian) Which is different than what people are used to dealing with, and what you find typically on the net.
Code:Private Const STATUS_SUCCESS As Long = 0
Private Type LARGE_INTEGER
LowPart As Long
HighPart As Long
End Type
Private Declare Function RtlLargeIntegerShiftLeft Lib "ntdll" (ByVal LowPart As Long, Optional ByVal HighPart As Long, Optional ByVal ShiftCount As Long = 1) As LARGE_INTEGER
Private Declare Function RtlLargeIntegerShiftRight Lib "ntdll" (ByVal LowPart As Long, Optional ByVal HighPart As Long, Optional ByVal ShiftCount As Long = 1) As LARGE_INTEGER
Private Declare Function RtlIpv4StringToAddressW Lib "ntdll" (ByVal S As Long, ByVal Strict As Byte, ByRef Terminator As Long, ByRef Addr As Long) As Long
Private Declare Function inet_addr Lib "ws2_32" (ByVal cp As String) As Long
Private Declare Function ntohl Lib "ws2_32" (ByVal netlong As Long) As Long
Private Declare Function htonl Lib "ws2_32" (ByVal hostlong As Long) As Long
Private Function Shl(ByVal Value As Long, Optional ByVal ShiftCount As Long = 1) As Long
Shl = RtlLargeIntegerShiftLeft(Value, 0, ShiftCount).LowPart
End Function
Private Function Shr(ByVal Value As Long, Optional ByVal ShiftCount As Long = 1, Optional Arithmetic As Boolean) As Long
Shr = RtlLargeIntegerShiftRight(Value, Arithmetic And Value < 0&, ShiftCount).LowPart
End Function
Public Function IPInCIDR(IP As String, CIDR As String) As Boolean
Dim Network() As String: Network = Split(CIDR, "/")
IPInCIDR = InNetwork(Str2IP(IP), Str2IP(Network(0)), Network(1))
End Function
Public Function InNetwork(ByVal IP As Long, ByVal RangeStart As Long, ByVal CIDR As Long) As Boolean
Dim Netmask As Long: Netmask = CIDR2Netmask(CIDR)
InNetwork = (IP And Netmask) = (RangeStart And Netmask)
End Function
Public Function Str2IP(ByRef DottedNotation As String) As Long
RtlIpv4StringToAddressW StrPtr(DottedNotation), 1, 0, Str2IP ' Network Order
End Function
Public Function CIDR2Netmask(ByVal Bits As Long) As Long
Static LookupMask(1 To 32) As Long
If LookupMask(1) = 0 Then
Dim i As Long
For i = 1 To 32
LookupMask(i) = htonl(Shl(-1, 32 - i)) ' Network Order!
Next
End If
CIDR2Netmask = LookupMask(Bits)
End Function
VB Code:
As LaVolpe was alluding to in the beginning, using netmask(s) the actual range check reduces to a couple mask operations (And) and a single compare (=).
So speed should not be an issue. I don't have a range to netmask convertor but this site has some.
https://www.ip2location.com/tutorial...e-into-netmask
the issue with using CIDR notation is that if your range spans networks, then you will need multiple CIDR/netmasks to describe the range.
hello,
I used flyguille solution. It is SUPER fast...
Got it all working.
Thanks for all the suggestions. What a great group of Developers we have here!
WP
Yup!., lookup tables, and old trick from old asm days, when you didn't has CLOCK power, maybe there can be more ROMs in the board, lookup tables all the way!. for COSINE, SINE, for MULTIPLY in z80 didn't sopport it, and characters behaviour (overall in shoot'em up games).. it is amazing what you can do with just lookup tables, creating your own processing power without using the CPU to process it!Quote:
Originally Posted by axisdj
Ohhh, I loved the old Z80 CPU. A chip you could easily get the entire instruction set in your head.
And, of course, my most noted Z80 assembly contribution to the world:
http://www.99-bottles-of-beer.net/la...z80)-2158.html
Smiles,
Elroy
Include it was shipped with instructions which the engineers who design it didn't know the instructions even exists.Quote:
Originally Posted by Elroy
like
LD ixH, register
LD ixL, register
(8 bits of any instruction using the IX e IY 16bit indexers register)
The only one problem abusing of that, is the extra 4 clocks it uses, because you ADDed the $FD or $DD instruction table prefix.
Well, truth be told, when I resorted to assembler, I typically wrote for the 8080, as it was machine code compatible with the Z80, whereas vice-versa wasn't true. Once upon a time, I had quite a few 8080 routines that I'd assemble into .OBJ files and then link them in with a larger program.
And, of course, here's my infamous contribution to 8080 assembler code: :)
http://www.99-bottles-of-beer.net/la...080)-2157.html
That solution might work great... as long as it actually does what you need.
But usually IP address whitelists and blacklists are not quite so... black and white. There may even be cases where you have just a few IPs to restrict within some given subnet.
Did you consider an ADO solution?
Here there is a MakeList.vbp for a program to create a text file of IP ranges. Run that first. Then there is an InList.vbp for a program to test IP addresses against those ranges.
"InList" starts by loading the text file. This could have been a persisted Recordset instead for faster loading AND could have omitted the "RangeID" column that was included here just for demo purposes.
After loading it kicks off a check of a bunch of IP addresses (here 1000 of them) and times the process.
Then after that you can manually enter and test IP addresses.
Attachment 150809
Attachment 150811
You may have exactly what you need already. This can be a useful technique for more demanding applications though.
Quote:
Originally Posted by dilettante
that is no problem with the single line solution look up table, including controlling the third level of the IP, it is 256*256*256 = 4MB / 8 (as boolean) if using a single bit per bool value, if not itis 4MB anyway.
The lookup table is pre-filled one time at load time, and reworked if a change is done in the set of ranges to accept.
Any other solution would be floodeable, so DoSable.
yes, I notices de similarities with the regular registers, it is a shame z80 didn't has well supported the C language, as it is very expensive the handling of the STACK, and C language require a massive usage of the stack, like MOV AX , [SP + nn]Quote:
Originally Posted by Elroy
In z80 those luxuries didn't exists, it can be emulated like, ex hl, sp, IIRC, then work with HL ld de, offset , add hl, de, then ex hl,sp, pop de (for reading the actual value parameter), then undo with SBC the added value discounting the PÔP, it is all a pain in the ass, and sloooooooooow.
or near method, INC SP INC SP.... DEC SP DEC SP and 8 bits ops.
So in z80 programmers passed all by registers, and forget about passing through stack, so, freedom about parameters count is not possible. Unless ofcourse, static addressing for parameters.
And that is how 8086 won the race.... of course, also was y monopoly practices form Intel, but that is another topic.
256 * 256 * 256 * 256 / 8 = 536,870,912 is a pretty big table.
You can probably drop the 0 and 255 values of course, and there is a smaller set of subnets than this to consider... but the table will still get darned big.
Trying to store as Boolean instead of packing bits it becomes massive, potentially too large to use at all.
IP lists that do not have IP address level resolution are not IP lists. What you have is at best a subnet list unless you consider all 32 bits.
Quote:
Originally Posted by dilettante
He is trying to point if inside USA or outside of USA..
None company in the world, woud have a "part" of the fourth element in the IP. NONE!
Companies are given whole 256 ranges.
If not whole 65536 ranges. (ISPs). As it is like the routing works in Internet. Other way tables at routing would be huge, and slow.
That's why I wrote:
I was merely presenting an alternative that seems to be fast enough (1000 in less than 1/10 of a second) and far less of a fragile hack than yours.Quote:
Originally Posted by dilettante
Why don't we just turn this into a contest :)
With actual IP range data. Then we can get Schmidt in here.
@dil should your DottedIPAddrToVarUI8() be renamed to DottedIPAddrToVarUI4()
Yep, you are right. Typo when I did a find/replace. Thanks, wrong is wrong and even wrong naming is wrong.
What are we trying to do here? Are we trying to figure out the fastest way to see if an IP address is in the USA range?
If that's the case, then the attached project has procedures in it for doing it about as fast as it's going to get.
Enjoy,
Elroy
EDIT1: Actually, it could be sped up somewhat by consolidating many of those ranges, because they're often contiguous. That would make the binary search a bit faster. They only reason they're not already consolidated is because they were assigned on different dates.
Someone should give dday9 a phone callQuote:
Originally Posted by DEXWERX
Here's some actual data ready for your benchmarks.
That's actually not true - there is hundreds if not thousands of ranges which differ in theQuote:
Originally Posted by flyguille
last part (even across countries, not only companies).
Example from RIPE: (all ranges share the first part: 37.59.223.___)
IT -> https://apps.db.ripe.net/search/quer...t=37.59.223.39
NL -> https://apps.db.ripe.net/search/quer...t=37.59.223.47
PL -> https://apps.db.ripe.net/search/quer...t=37.59.223.63
CZ -> https://apps.db.ripe.net/search/quer...t=37.59.223.79
GB -> https://apps.db.ripe.net/search/quer...t=37.59.223.95
DE -> https://apps.db.ripe.net/search/quer...=37.59.223.127
FR -> https://apps.db.ripe.net/search/quer...=37.59.223.191
Or to give another example from ARIN:
The US-RangeSite here: http://lite.ip2location.com/united-s...address-ranges
lists e.g. the range: 23.239.183.32 to 23.247.128.255 ...
But in reality there is a whole lot of Sub-Ranges in there, which were re-assigned,
as e.g. the range 23.246.198.192 to 23.246.198.223 belonging to CL (Chile) now.
https://whois.arin.net/rest/customer/C05314851.html
So these more detailed infos can be found over the registrars (of the appropriate region) directly,
or by using more recent (and more "fine-granular") DataBases...
The one I've found among the free available ones, is this one here (CC-licensed):
https://db-ip.com/db/download/country
It contains nearly half a Million range-records - and was the most detailed one
(there's other free, liberally licensed DBs, but the next one which came close had only about 250,000 records).
The advantage with those larger DBs is, that they cover all countries *and*:
- that they leave no gaps!
That means, the format within the CSV above (IPfrom, IPto, ...) is not really
needed, because any "IPto-Value" is equal to the "IPfrom-Value minus one" from the next line.
That makes it quite easy for much more efficient storage - and for a fast binary search.
So I've re-formatted the above CSV in a Binary-Format, which takes this "gapelessness" into account,
storing a single range-record in only 6 Bytes, which reduces the Raw-Binary-File to about 2.5MB
(432616 Records * 6 Bytes-per-Record = 2,595,696).
Further LZMA-compressing reduces these ~2.5MB to about 500kByte (something one can ship-along easily with ones App).
... since you called ... ;)Quote:
Originally Posted by DEXWERX
Though the US-DB is a bit small (any algo would probably feel "fast enough").
So I'd suggest to use the Data from the link I've posted above (the one with the 432616 Records)
and use that...
I've done that in the following Demo (which does not include the original CSV, but the 512KB LZMA-Raw-Binary-Data):
http://vbRichClient.com/Downloads/IPRangesByCountry.zip
Which needs some time to load (about 300msec, mostly due to the LZMA-decompression):
http://vbRichClient.com/Downloads/IPRanges.png
But after the 0.5Mio Records sit in the Dictionary, the (Binary) search goes quite fast:
http://vbRichClient.com/Downloads/IPRanges2.png
My 0.02$...
Olaf
olaf
That kills my theory that the 1st "part" of the IP address was regionally based.Quote:
The advantage with those larger DBs is, that they cover all countries *and*:
- that they leave no gaps!
Good stuff
Spoo
Well, with more reason, my method wins, because if it is that granulated, over the world it will be like having thousands of entries pointing to USA locations.Quote:
Originally Posted by Schmidt
so it will end to be an lookup table of 4MB*256 / 8, and a nice time at the beggining filling it once on startup time.
Note if VB6 waste the 8 bits per boolean, you can really handle an array of bytes, and calling it like
if (var(first, second, third , int(fourth/8)) and 2^(fourth mod 8) then ' Is in USA.
and the declaration is:
private Var(0-255,0-255,0-255,0-31) as byte
the setup is
var(first,second,third, int(fourth /8)) =var(first,second,third, int(fourth /8)) or (2^(fourth mod 8)) ' It mark that ip as IN USA.
and the loop runnig it is a bit trickery.
but easy
first=init first
second=init second
third =init third
fourth =init fourth
while true
var(first,second,third, int(fourth /8)) =var(first,second,third, int(fourth /8)) or (2^(fourth mod 8)) ' It mark that ip as IN USA.
fourth =(fourth+1) mod 256: if fourth=0 then third = (third + 1) mod 256: if third=0 then second=(second+1) mod 256 : if second=0 then first=(first+1) mod 256
if fourth=endfourth then if third = endthird then if second=endsecond then if first= endfirst then EXIT LOOP
Wend
That is the faster filling the array that I can think.
TOTAL DATA USAGUE = 4MB*32 = 128MB, not that bad for modern PCs.
Time requre to check on _ConnectionRequest = 1 line of code!!!! you can do hundreds of thousands per second.
ADITIONAL FEATURE WHICH you can get from it, DISABLING temporarily individual IP when detecting DoS attacks!.
PD: Now thinking in implement it in my DRM server, one never knows which competitor can get angry when growing my customers base in detriments of their sells. Better to be prepared!
No, not really... (because it's a memory-eater)Quote:
Originally Posted by flyguille
It depends on, which DB you choose...Quote:
Originally Posted by flyguille
- about 7000 US-entries are in the NirSoft-DB (from the opener-post)
- about 19000 US-entries in the CSV-File DEXWERX has posted
- and about 88000 US-entries (of the 0.5Mio total) are in the "no-gaps, all countries" CSV-File which is the base for my approach
BTW, there's something wrong with your math, when you write: TOTAL DATA USAGUE = 4MB*32 = 128MB
Because a ByteArray dimensioned as: Dim LookupTable (0 to 255, 0 to 255, 0 to 255, 0 to 31) As Byte
...will take up half a Gigabyte (4Gig divided by 8).
I would not want to use an App which takes up 512MB, for a simple IP-check...
Not to mention, that such a large allocation of consecutive memory has a high chance to fail.
The approach I've choosen:
- is far less memory-intensive (takes up only about 16MB of Ram)
- works for all IP-ranges (all countries, not only the US)
- is quite fast with the lookups too (can achieve about 0.2Mio lookups per second)
Olaf
Yup, math is wrong, it is 512MB for the IP check. Depends on the availability, anyway it will be the choise about performance time. 32bits programs are up to 4GB? or VB6 has a silly limit of 2GB or something?Quote:
Originally Posted by Schmidt
anyway, include my biiiiiiigest server multipurpose loaded in ram is about 25MB....., so yup, no problem in using 512MB just for the ip check...., not to said that servers can have lots of rAM, tipically more than 16GB , being the usual 64GB.
And that's why also the approach is wrong.Quote:
Originally Posted by flyguille
Lookup-Table-Arrays don't make much sense, when they are as sparsely populated as in this case.
And also here you operate on a wrong assumption - because a fast (final) LookUp-Table accessQuote:
Originally Posted by flyguille
is the one thing - but before you can perform the access, there's other lines needed to prepare the input -
and these extra-calls sum up in the end...
I've now tried to simulate your approach in a little test-code-snippet -
(with only a 256MByte-Array instead of your proposed 512MB) - but
the principle is the one I've cobbled together from all your lines and comments.
What I get here on my machine as "time needed per function call" is:
- about 1.9 µsec when running in the IDE ... and
- about 1.6 µsec when running native compiled
That's nearly identical to the timings I achieve with the "full-coverage" approach
(mine is a bit faster when native compiled, but a bit slower than yours when in the IDE)
HTHCode:Option Explicit
Private LookupTable(0 To 255, 0 To 255, 0 To 255, 0 To 15) As Byte
Private Sub Form_Click()
Dim i As Long, Result As Boolean, T As Single
T = Timer
For i = 1 To 100000
Result = IsInUSA("121.122.123.124")
If Result Then
'do something here
End If
Next
Caption = Format$((Timer - T) * 10, "0.0") & " µSec per function-call"
End Sub
Function IsInUSA(RemoteIP As String) As Boolean
Dim STRD As String
STRD = RemoteIP
Dim a As Integer, b As Integer, c As Integer
a = InStr(STRD, ".")
b = InStr(a + 1, STRD, ".")
c = InStr(b + 1, STRD, ".")
Dim first As Byte, second As Byte, third As Byte, fourth As Byte
first = Val(Mid$(STRD, 1, a - 1))
second = Val(Mid$(STRD, a + 1, b - (a + 1)))
third = Val(Mid$(STRD, b + 1, c - (b + 1)))
fourth = Val(Mid$(STRD, c + 1))
IsInUSA = LookupTable(first, second, third, Int(fourth / 16)) And (fourth Mod 16)
End Function
Olaf
what? that code is slow, you did it the worse way!. You don't use a set of string variables for the inspection, it hasn't sense, you just VAL it directly on the array dimensions.Quote:
Originally Posted by Schmidt
and you know there is SPLIT string right? so a simple string array as result of SPLIT, then val(st(1))...., val(st(2))...., and go on, . so not needs of three INSTRs plus the MID$().
Result, it is just 3 simple lines (single instruction per line) for doing it ALL.
Well, then let's see what your recommendations will bring, when I alter it to your wishes... ;)Quote:
Originally Posted by flyguille
Ok, done...Quote:
Originally Posted by flyguille
... as you wish, master...Quote:
Originally Posted by flyguille
Please forgive me, but I've found it this way in posting #10 (from a guy named "flyguille")... ;)Quote:
Originally Posted by flyguille
But Ok - I've adapted it now as commanded...
I hope the new code below is to your satisfaction now - but I have to tell you that the changes you demanded,Quote:
Originally Posted by flyguille
make it now run factor 2 slower than before... (about 3.3 µsec per call, compared to the former 1.6)
What now?
Wouldn't it be better, when you perhaps write "the ideal code" for the usage of your approach yourself -
and post it here (preferrably within Code-Tags, if that's not too much to ask...).
OlafCode:Option Explicit
Private LookupTable(0 To 255, 0 To 255, 0 To 255, 0 To 15) As Byte
Private Sub Form_Click()
Dim i As Long, Result As Boolean, T As Single
T = Timer
For i = 1 To 100000
Result = IsInUSA("121.122.123.124")
If Result Then
'do something here
End If
Next
Caption = Format$((Timer - T) * 10, "0.0") & " µSec per function-call"
End Sub
Function IsInUSA(RemoteIP As String) As Boolean
Dim st() As String
st = Split(RemoteIP, ".")
IsInUSA = LookupTable(Val(st(0)), Val(st(1)), Val(st(2)), Int(Val(st(3)) / 16) And (Val(st(3)) Mod 16))
End Function
ok remove the INT(), btw I didn't know a Split() function, is slower than 7 VB string function which its parameters parsings and all. weird.Quote:
Originally Posted by Schmidt
oh, BTW? why you chose MOD and / 16, if it is 8 , as per 8 bits per byte?
oh, and you didn't did the BIT inspection, just readed the whole byte as output!.
lets change the: To 31
Private LookupTable(0 To 255, 0 To 255, 0 To 255, 0 To 31) As Byte
and
IsInUSA = LookupTable(Val(st(0)), Val(st(1)), Val(st(2)), Val(st(3)), Val(st(4)) / 8) And (2^(Val(st(4)) Mod 8)
oh, now I see you didn't inspect the fourth value at all!
Ofcourse now it is a bit slower.
But prefferably a lookup table, and not rolling an array with many entries, including it doing binary search would be slower.
Oh, BTW, thanks by your participation.
My little perfomance-test-loop was meant to open your eyes about theQuote:
Originally Posted by flyguille
significance of the overhead, the preparing of the Arrays Index-Parameters will cause
(in a lookup-table-based approach).
Of course - because you now apply even more math, to prepare the Input-Parameters (the final Index-Parameters for the Array-Lookup).Quote:
Originally Posted by flyguille
On my machine it now takes (with your changes applied) 4.2 µsec per IPCheck-call.
No matter how often you repeat it, your statement is still wrong.Quote:
Originally Posted by flyguille
Let's do a comparison again... looking at your approach...:
- no really working code-example exists
- it needs 512 MB of consecutive memory (which on many machines will choke, because the Mem-allocator will not find a large enough block for that)
- the IPLookup-Function takes about 4 µsec to return the Boolean-Result
- to finally allow only an info, whether the IP is an US-IP or not
The approach I've posted in #33 (updated yesterday, including optimizations and performancetests): http://vbRichClient.com/Downloads/IPRangesByCountry.zip
- is a fully working demo
- it needs about 16MB to hold the ~0.5Mio range-infos in a binary-searchable Key/Value-Pair-Class
- the IPLookup-Function takes (on average) 2 µsec to return the String-Result
- which is a 2-Char-Country-String that "covers all countries the world over"
Hmm, when I look at the above, I cannot find a single reason to go with your proposal...
Olaf
Quote:
Originally Posted by Schmidt
ok, your code is faster you said? or it is just you want to get what country is as an extra feature which the thread creator didn't asks for.
I would like to understand your code.... but, uhhhhhhhhhhgggggr, largely unreadable. Didn't you know identation and structure even exists?.
Anyway I will give it a try to understand it.Code:Attribute VB_Name = "modIPCheck"
Option Explicit
Public IPRanges As cSortedDictionary
Public Sub InitRangeDictionaryFrom(FileName As String)
Set IPRanges = New_c.SortedDictionary
Dim BSrc() As Byte, B() As Byte, C As Long, i As Long, K As Currency
BSrc = New_c.FSO.ReadByteContent(FileName)
New_c.Crypt.LZMADeComp BSrc, B
C = (UBound(B) + 1) \ 3
For i = 0 To C - 1 Step 2
K = B(i + i) + 256@ * B(i + i + 1) + 65536@ * B(i + i + 2) + 16777216@ * B(i + i + 3)
IPRanges.Add K, B(C + C + i) + 256& * B(C + C + i + 1) 'add the Country-Item under Key K
Next
End Sub
Public Function CheckIPRange(sIP4 As String, Optional ByVal IncludeRangeInfo As Boolean) As String
Dim Key As Currency, i As Long, Item As Long, IPfrom As String, IPto As String
Key = IP4toKey(sIP4)
If IPRanges.Exists(Key) Then
Item = IPRanges(Key)
Else
i = IPRanges.IndexByKey(Key, True) - 1 '<- True allows an "unsharp" search (delivers the index where a non-existing Key would be sorted into "in-between")
Item = IPRanges.ItemByIndex(i)
End If
CheckIPRange = Chr$(Item And &HFF) & Chr$(Item \ &H100)
If IncludeRangeInfo Then
If i = 0 Then i = IPRanges.IndexByKey(Key)
IPfrom = KeytoIP4(IPRanges.KeyByIndex(i))
If i = IPRanges.Count - 1 Then IPto = "255.255.255.255" Else IPto = KeytoIP4(IPRanges.KeyByIndex(i + 1) - 1)
CheckIPRange = CheckIPRange & " [" & IPfrom & " to " & IPto & "]"
End If
End Function
Public Function IP4toKey(sIP4 As String) As Currency
Dim B() As Byte, i As Long, j As Long
B = sIP4
For i = 0 To UBound(B) Step 2
If B(i) = 46 Then IP4toKey = IP4toKey * 256 + j: j = 0 Else j = j * 10 + B(i) - 48
Next
IP4toKey = IP4toKey * 256 + j
End Function
Public Function KeytoIP4(ByVal Key As Currency) As String
Dim i&, j&: Static B(0 To 3) As Byte, S(0 To 29) As Byte
New_c.MemCopy VarPtr(B(0)), VarPtr(CCur(Key / 10000@)), 4
For i = 0 To 3
Do: S(28 - j) = (B(i) Mod 10) + 48: j = j + 2: B(i) = B(i) \ 10: Loop While B(i)
S(28 - j) = 46: j = j + 2
Next
KeytoIP4 = RightB$(S, j - 2)
End Function
I am beyond thankful for this robust discussion which gives me very useful information to get this done in the best way possible. Again would like to thank all involved, this vb6 group is just amazing!
What the hell are you talking about? I just saw the code and the indentation is perfect :confused:Quote:
Originally Posted by flyguille
well, watching it again seems ok the indentantion, but I didn't see the colon since the Microsoft MSX BASIC 2.0 era (1986)... :DQuote:
Originally Posted by Carlos Rocha
EDIT: nahh, correcting me, I never will write a DO / LOOP while all in a single line, no structure, no indentation .
But, you know, if it works, it is just fine!. But don't present it in a team project if you don't want to be kicked at the third day.
It sure *is* faster than your Lookup-Routine (which I've written according to your "instructions").Quote:
Originally Posted by flyguille
If you think you can do better than that, I'd surely want to see some code from *you*.
What we have currently, regarding your approach is only a "paper-tiger", there's no Copy&Pastable
demo - or even better - a zipped Demo-Project from you anywhere.
I for my part would surely like to see, how you fill up that huge Lookup-Array of yours properly.
To make it somewhat easier for you, I've now extracted the 88314 US-RangeRecords from the
DataSet my larger Demo is using, and one can download it here:
http://vbRichClient.com/Downloads/USRangesDetailed.zip
It contains a normal CSV-File (USRangesDetailed.csv, with IPfrom,IPto per Line) -
but also a Raw-CurrencyArray-File, called USRangesDetailed.bin, which one can load this way:
After the Init-Routine above was called, USRanges has an Ubound of 88314*2-1 and contains the sorted entries of theCode:Private USRanges() As Currency
Sub InitRangeArray(FileName As String)
ReDim USRanges(0 To FileLen(FileName) \ 8 - 1)
Dim FNr As Long: FNr = FreeFile
Open FileName For Binary Access Read As FNr
Get FNr, , USRanges
Close FNr
End Sub
88314 US-RangeRecords as numeric values, the IPFrom-entries sitting at the even Indexes, the IPTo-entries at the odd IndexPositions.
(mainly thought for those who want to try themselves at a Binary-Search-based algorithm against that Array).
Would surely like to see some code from you, which got the Lookup-Arrays filled with that detailed set of US-Ranges
(your choice, whether you read the data from the *.csv or the *.bin-file).
I've mentioned that because my code is faster and takes less memory *despite* offering full country-resolution...Quote:
Originally Posted by flyguille
If I reduce the Size of my DataSet to "US-Ranges only", then I'd expect results far better than 1 µsec per IPCheck-call.
Nothing holds you back to reformat it to your liking, it's not that much code after all... <shrug>Quote:
Originally Posted by flyguille
As for understanding it though, ...from how you post and interact with other developers (ignoring proof delivered by code) -
I'd think you are still quite young and inexperienced (comparably), so don't expect "immediate results" just by looking at it... ;)
Olaf
nope, but have better things to do... calm down, it is just an ideas exchanges!.Quote:
Originally Posted by Schmidt
EDIT: which have better things to do, is why I didn't bother in creating a zip with a vb project inside. Or timing it.
I don't know about you, but I am 41yo, with commercial software published and commercializing it, supporting it, with sells and marketing ppl, oh and a graphics designer just hired a month ago....
Anyway, programmer since 10yo..., doing video games in z80 and MSX BASIC since then...., spanish guy, so my english is not perfect.
But all your asumptions, about young, and unexperienced was wrong..., maybe tomorrow as holiday, I can pick or reformat your code to make it more readable and then try to understand why you claim it be fast include it having LOOPS, and FOR/NEXT , to do the IPCHECK, because I see those loops, don't understand how your code can be faster.
But sure, if country flag as return, and/ better, currency flag, sure it is better, more featureful. I am just not sure about faster.
Nope, not really (and I wrote "comparably", if you care to look that up again).Quote:
Originally Posted by flyguille
I'm developing in C/C++ and VB6 for quite a bit longer than you (I'm in my fifties, but many Forum-Users here top that easily),
so you are (comparably) a "youngster" still. ;)
I dont "claim" it to be fast - it *is* fast and can be tested by anybody who cares to download, compile and run the Zip I've posted.Quote:
Originally Posted by flyguille
I can only encourage you, to post your own approach in a fully working code-example, so that *other* developers can look,
test and compare for themselves - currently it is only you who "claims" something (no real demo anywhere, just talking).
But as it seems currently, you will chicken out, not posting anything (which is a common pattern with challenged - ermm... "youngsters").
That sentence alone shows, how inexperienced you are with performance-related things in High-Level-Languages.Quote:
Originally Posted by flyguille
Here it is often the longer routines which are faster than the "conveniently written High-Level-OneLiners".
Well, I am - because I *timed* it already (and I usually try very hard, not to give wrong info in a Public Forum).Quote:
Originally Posted by flyguille
Olaf
the only thing I can thinks, about why my methods, according to you is slower than yours, is that as it is 512MB lookup table, and tested with IP ramdonly generated, maybe MAYBE it is being penalty by the lookup table not being in the CPU's L1/L2 CACHÉ. Other way, how a simple array lookup will be slower than LOOPEd functions in a binary search.Quote:
Originally Posted by Schmidt
You told that mine approach is 3us per IP check?
that is like a lot for modern CPUs, like 333K of runs per second. 333000, .hmmm there is a penalty somewhere.
I will give yours and mine a try... btw, don't forget it is just an idea exchange, nothing personal. So, take it easy!.
No, although such a huge "en-bloc" memory-allocation is generally a bad idea,Quote:
Originally Posted by flyguille
it is not the array-access which is slow.
As pointed out to you already several times - it is not the final array-acces which is slow -Quote:
Originally Posted by flyguille
it is all the operations which come *before* the array-access (preparing the correct Indexes) which make it slow.
Yes - why didn't you test this already?Quote:
Originally Posted by flyguille
I've posted code for that.
To write it out more clearly again:
When you have a 4-dimensional LookupArray you will have to provide it with 4 Indexes in the end (to perform the array-read)
(let's call these Indexes a,b,c,d - and assume that they are explicit Integer-Variables at Function-level)...
So, before you do your final (and fast) Lookup as: FunctionResult = LookupArr(a, b, c, d)
you have to calculate the values of a, b, c and d (starting with everything you do on the Input-Param, since entering the Function).
That's where the 3µsec are caused in your case.
- Split (as a super-high-level-function) is of course "slower" than
- a few Instr/Mid$ calls (which are themselves higher-level-functions of the vbRuntime),
- which again are slower than a direct looping over a ByteArray (which avoids any calls into the vbRuntime)
That this is "surprising" to you baffles me a bit...
(giving your background in ASM, one would think that you know how compilers work -
and how they interact with a given runtime-library which provides certain language-features).
Well, if you'd put yourself into my shoes for a moment, you'd see that my "getting impatient" is explainableQuote:
Originally Posted by flyguille
(given the fact, that I'm basically repeating myself for a few postings already).
As for testing (and learning) - here's another example I've put together,
which does a direct Binary-Search on a Currency-Array for only the US-Range
http://vbRichClient.com/Downloads/IP...USDetailed.zip (not requiring a vbRichClient5-reference in your project).
Due to the reduced range of records (only ~88000 for the US), it is of course faster than the "all countries version" I've posted earlier -
now needing only about 0.12 µsec per IPCheck-FunctionCall (when native compiled).
All of this "performance-discussion" is (whilst hopefully being educational) of course largely academic for the case of the OP.
Any approach which delivers the result after 100 µsec or so, would be entirely sufficient I'd say.
Olaf
I understand you, just I didn't know split() & VAL() was so slow. Include with in-stack parameter parsing.Quote:
Originally Posted by Schmidt
Just asking about VB6.
Is there a penalty about calling a VBA functions? than a call to a function within module , or a class module in the VB project? I saw you are using a class aswell, because my knowledge is that both are __STDCALL. Unless things like NEAR / FAR CALL still exists in VB6/modern O.S.,.... but IIRC it not more exists in 64bits/32bits non paged memory mapping, right?.
Again, I thinks, IF TESTED with ramdomly IP CHECKS, 512MB don't fits in L1 or L2 cache, and every time the CPU must read the DIIMMs. Which is a penalty, as well as at LOADING TIME, to allocate 512MB you are right, is a bit overkill for loading time. Those two things are the CONS.
Now, may I will use your method, it comes handy, but right now, not time to check.
Again I didn't tested, because having a huge inbox stack right now, and I don't have time, just chat around this VBforum for rest a bit. I has an ETA of 2 months.
DEXWERX, can you tell me where you got this data.
Is this all USA ranges?
Thanks!
DUH... later found the credits of where you got the ip's in your zip... sorry
Ok, after initially getting the solution going with the 7000 ranges (using the true/false memory mapped array) I originally was working I have realized that is not going to be suitable accuracy, too many ips are in USA and not in that range SO...
@Schmidt , I thoroughly looked at your sample, and I think you have a mis-calcualtion. Each look-up takes about 1 second on my system... way too slow for looking up 400+ ips per second. Not sure What I am doing wrong, but the Timer call in VB6 is in seconds and this is what I get:
59625.39 ''lookup started
59626.57 ''' lookup done
1.179688 '' difference in time seconds
So here is what I thought.
I found a list with decimal converted ranges of about 19,000 entries. Like this:
2466840576 2466906111 US United States
If I had those ranges in a hiIp() and lowIP() array I could traverse the array up or down to look if it is in range. I will test that for speed tonight, but what I am thinking is how could I shorten the search cycle somehow by knowing where to start the search.
One way I thought would be to use the 'Like' operator for the first four numbers in the ranges and add the results in a collection, then check ranges there.
Any other thoughts.
{added later}
Just found the 'Filter' function, which would return an array , maybe I can filter if the first four numbers matches , then range check those results.
Seems you didn't look as thouroughly at the example as you should have,Quote:
Originally Posted by axisdj
since the timing was measuring a Loop for the total of 1Mio IP-Lookup-calls...
Here's the code-snippet again (which even had a comment, where the amount of calls was stated):
And I assume, that you ran this in the IDE, because if you compile it natively,Code:For i = 1 To 1000000 '1Mio calls
Result = CheckIPRange(sIP4, Idx)
If Result Then
End If
Next
you should get below 1sec for the total amount of time which the 1Mio calls need in total.
(FYI, 1Mio calls, when you measure them in seconds - will translate to µsec per single-call.)
Olaf
Was a long day yesterday, did not realize that loop was a stress test, somehow thought it was searching entries for the match.
Thank you Olaf for the clarification,sorry for the mis-understanding.
Think I will implement your approach - the LZMA compression, my clients wont mind a 2.5MB reference file.
Thank you
Can you give me more detail on getting this done. I have tested the old compressed file, and because it is using data from early august it is out of date with some false positives.Quote:
So I've re-formatted the above CSV in a Binary-Format, which takes this "gapelessness" into account,
storing a single range-record in only 6 Bytes, which reduces the Raw-Binary-File to about 2.5MB
(432616 Records * 6 Bytes-per-Record = 2,595,696).
What I would need is an understanding of how to get the original file monthly, then format it to fit into the sample you sent. The extra compression is not really necessary for me.
I think having more detail on how you sorted the data will help but some clarification on how you set/retrieve keys. Does each possible IP address have a entry into the Ip sorted dictionary?
[later]
Ok I think I get it.. dear lord you are beyond genius. You convert the IP to a Currency(because long can't hold enough numbers) then you look at the populated dictionary and call IndexByKey(key,true) which returns a hypothetical index.. (WOW) Then I assume you call ItemByIndex which uses the hypotheical index to get the closest index of an actual item? which in turn gives the country code, which is stored in Binary and decode. (OMG) you go deep...
Any clarification on the above would be great.
I would like to understand the way the database needs to be represented, because I may need to interchange, and often update reference database. I am finding many are not consistent between each other. A way to import a standard start,end,country csv file may be best.
Thanks
Ok,
just wanted to let Olaf know I figured it out mostly.
Thanks again for the guidance.
WP
Sorry for posting that late (shifted it "down my stack", because I didn't find the CSV-parsing-code anymore,Quote:
Originally Posted by axisdj
which produced the Binary for the LZMA-Blob, guess I've deleted it "for good" whilst "cleaning up" the original example).
Here again a fresh version (into a Class, named e.g. cUpdateFromCSV )
Usage then (after downloading the monthly updated CSV-Files from: https://db-ip.com/db/download/countryCode:Option Explicit
Implements ICSVCallback
Private CSV As cCSV, IPs() As Byte, Countries() As Byte
Public Sub ConvertToBinaryFile(CSVFileName As String, BinFileName As String)
ReDim IPs(4 * 10 ^ 6) 'Space for ~1Mio records (currently used will be only about half as many)
ReDim Countries(2 * 10 ^ 6) 'same here (though the country-info will be only 2bytes per record)
Set CSV = New_c.CSV
CSV.ParseFile CSVFileName, Me
ReDim Preserve IPs(4 * CSV.RowsParsed - 1)
ReDim Preserve Countries(2 * CSV.RowsParsed - 1)
With New_c.FSO.CreateFileStream(BinFileName)
.WriteFromByteArr IPs 'write the IP-Bytes first into the stream (for better compressability,...
.WriteFromByteArr Countries '... they are followed by all the country-bytes in a separate block)
End With
End Sub
Private Function ICSVCallback_NewValue(ByVal RowNr As Long, ByVal ColNr As Long, B() As Byte, ByVal BValStartPos As Long, ByVal BValLen As Long) As Long
Select Case ColNr
Case 0 'Start-IP
Static S As String, SArr() As String
S = CSV.GetStringValue(B, BValStartPos, BValLen)
If InStr(S, ":") Then ICSVCallback_NewValue = 1: Exit Function 'stop parsing, when we reach the IPV6-section
SArr = Split(S, ".")
IPs(4 * RowNr + 3) = SArr(0): IPs(4 * RowNr + 2) = SArr(1): IPs(4 * RowNr + 1) = SArr(2): IPs(4 * RowNr + 0) = SArr(3)
Case 2 'Country-Code (we can simply copy the two Bytes over directly from the Input-Stream, no string-conversion needed)
Countries(2 * RowNr + 0) = B(BValStartPos)
Countries(2 * RowNr + 1) = B(BValStartPos + 1)
End Select
End Function
The Inital-Reading-Routine could be adapted to support both (LZMA-compressed and uncompressed formats) over the FileEnding like this:Code:With New cUpdateFromCSV
.ConvertToBinaryFile App.Path & "\dbip-country-2017-09.csv", App.Path & "\IPRangesByCountry.bin"
End With
HTH (and yes, all your other assumptions were quite correct).Code:Public Sub InitRangeDictionaryFrom(FileName As String)
Set IPRanges = New_c.SortedDictionary
Dim BSrc() As Byte, B() As Byte, C As Long, i As Long, K As Currency
If LCase$(Right$(FileName, 4)) = "lzma" Then 'decompress the ByteContent from LZMA first
BSrc = New_c.FSO.ReadByteContent(FileName)
New_c.Crypt.LZMADeComp BSrc, B
Else 'we assume uncompressed, raw binary format and read that into B directly
B = New_c.FSO.ReadByteContent(FileName)
End If
C = (UBound(B) + 1) \ 3
For i = 0 To C - 1 Step 2
K = B(i + i) + 256& * B(i + i + 1) + 65536 * B(i + i + 2) + 16777216@ * B(i + i + 3)
IPRanges.Add K, B(C + C + i) + 256& * B(C + C + i + 1) 'add the Country-Item under Key K
Next
End Sub
Olaf