[30757] in Perl-Users-Digest
Perl-Users Digest, Issue: 2002 Volume: 11
daemon@ATHENA.MIT.EDU (Perl-Users Digest)
Tue Nov 25 00:09:44 2008
Date: Mon, 24 Nov 2008 21:09:07 -0800 (PST)
From: Perl-Users Digest <Perl-Users-Request@ruby.OCE.ORST.EDU>
To: Perl-Users@ruby.OCE.ORST.EDU (Perl-Users Digest)
Perl-Users Digest Mon, 24 Nov 2008 Volume: 11 Number: 2002
Today's topics:
Re: comp.lang.* newsgroups seems dying <smallpond@juno.com>
Re: comp.lang.* newsgroups seems dying <jon@ffconsultancy.com>
Re: comp.lang.* newsgroups seems dying <kkylheku@gmail.com>
free dating services for marysville california porphyrymoralesnh@gmail.com
Herald: Python surpasses Perl in popularity! <xahlee@gmail.com>
Re: IP address - longest prefix match <jurgenex@hotmail.com>
Re: IP address - longest prefix match <hirenshah.05@gmail.com>
Re: IP address - longest prefix match sln@netherlands.com
Re: IP address - longest prefix match <jurgenex@hotmail.com>
Re: IP address - longest prefix match sln@netherlands.com
Re: IP address - longest prefix match sln@netherlands.com
Re: IP address - longest prefix match sln@netherlands.com
Re: longest prefix match <tzz@lifelogs.com>
Digest Administrivia (Last modified: 6 Apr 01) (Perl-Users-Digest Admin)
----------------------------------------------------------------------
Date: Mon, 24 Nov 2008 12:21:02 -0800 (PST)
From: smallpond <smallpond@juno.com>
Subject: Re: comp.lang.* newsgroups seems dying
Message-Id: <be7f42d9-bcd7-474d-980b-214b304c8484@w35g2000yqm.googlegroups.com>
On Nov 24, 2:03 pm, Xah Lee <xah...@gmail.com> wrote:
> this Don moron have any sense of responsibility? Is he pretenting he
> doesn't understand what's spam? Does he care?
>
> This post is posted to: comp.lang.lisp, comp.lang.scheme,
> comp.lang.functional, comp.lang.perl.misc .
>
Have you no sense of irony?
------------------------------
Date: Mon, 24 Nov 2008 21:34:24 +0000
From: Jon Harrop <jon@ffconsultancy.com>
Subject: Re: comp.lang.* newsgroups seems dying
Message-Id: <MJWdnchcTfKykrbUnZ2dnUVZ8t7inZ2d@posted.plusnet>
Xah Lee wrote:
> On Nov 24, 8:59 am, Don Geddis <d...@geddis.org> wrote:
>> Xah Lee <xah...@gmail.com> wrote on Mon, 24 Nov 2008:
>> > i think at least 25% of posts to comp.lang.lisp are spams this year.
>>
>> I agree with you completely.
>>
>> For example, there's this guy, Xah Lee, who posts all the time to c.l.l,
>> and
>> pretty much every one of his posts is spam. He probably makes that 25%
>> number all by himself.
>>
>> Do you have any advice for how we can get rid of that guy?
>
> Guys, look at this Don moron.
>
> In the current week, we see in comp.lang.lisp these posts:
> ...
I wasn't going to reply but I confess that this is pretty funny. The Lisp
community enjoy measuring their success by the amount of spam they receive
in comp.lang.lisp compared to comp.lang.functional (and neglecting fa.caml
and fa.haskell).
I particularly like the way your respondant's website cites as having been
unemployed for six years and gives a list of projects he started but never
finished. :-)
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
------------------------------
Date: Mon, 24 Nov 2008 20:50:33 +0000 (UTC)
From: Kaz Kylheku <kkylheku@gmail.com>
Subject: Re: comp.lang.* newsgroups seems dying
Message-Id: <20081124124946.29@gmail.com>
On 2008-11-24, Jon Harrop <jon@ffconsultancy.com> wrote:
> I wasn't going to reply but I confess that this is pretty funny. The Lisp
> community enjoy measuring their success by the amount of spam they receive
> in comp.lang.lisp compared to comp.lang.functional (and neglecting fa.caml
> and fa.haskell).
Do not ascribe to others a preoccupation that is entirely yours.
------------------------------
Date: Mon, 24 Nov 2008 19:48:24 -0800 (PST)
From: porphyrymoralesnh@gmail.com
Subject: free dating services for marysville california
Message-Id: <b8dc328e-881f-43f5-a27b-85455e563c2a@v38g2000yqb.googlegroups.com>
free dating services for marysville california
.
.
.
*******CLICK HERE********
http://dating365.co.cc/free-dating-services-for-marysville-california
*****************************
.
.
.
.
.
.
.
.
.
.
.
.
free dating services for marysville california
------------------------------
Date: Mon, 24 Nov 2008 17:06:32 -0800 (PST)
From: Xah Lee <xahlee@gmail.com>
Subject: Herald: Python surpasses Perl in popularity!
Message-Id: <5e87aee0-c7fd-4e9d-befb-0cc01cee64ec@f40g2000pri.googlegroups.com>
herald: Python surpasses Perl in popularity!
According to
=E2=80=9CTIOBE Programming Community Index for November 2008=E2=80=9D at
http://www.tiobe.com/content/paperinfo/tpci/index.html
it seems that Python has surpassed Perl in popularity this month!
Good for Python!
From my own personal experience in the programing industry, i find it
hard to believe that Python actually surpassed Perl in terms of use in
companies. Python is used in, Google, as everybody knows, but where
else? Perl is used in, umm, about every company except Google (and
probably Google too! in fact).
A quick search in monster.com, i find that perl returns 2673 results,
and Python returns 879 results. Perlers, you still safe!
Looking at other lang popularity site,
http://www.langpop.com/
it indicates that it's pretty much a tie.
So, i think it's not all peaches and cream for Python yet.
However, am pretty sure it'll be so in the next couple of years.
(btw, for those perlers who wishes to learn Python, see a comparative
tutorial:
=E2=80=A2 Xah's Perl and Python Tutorial
http://xahlee.org/perl-python/index.html
)
Xah
=E2=88=91 http://xahlee.org/
=E2=98=84
------------------------------
Date: Mon, 24 Nov 2008 11:24:45 -0800
From: Jürgen Exner <jurgenex@hotmail.com>
Subject: Re: IP address - longest prefix match
Message-Id: <1nvli4dq5p0cum193ec0c8ho99lhbjtah5@4ax.com>
"friend.05@gmail.com" <hirenshah.05@gmail.com> wrote:
>Suppose I have C_IP address : 12.120.29.25
>
>and I have list of following IP addresses :
>
>
> 212.120.128.0|19;
> 12.120.0.0|15;
> 12.120.16.0|20;
> 12.120.72.0|22;
> 12.120.96.0|20;
> 12.120.40.0|21;
> 12.120.0.0|21;
> 12.120.192.0|19;
> 12.120.16.0|22;
> 12.120.36.0|22;
> 12.120.80.0|20;
> 194.212.120.0|21;
> 212.120.32.0|19;
> 212.120.64.0|18;
> 212.120.192.0|19;
> 213.3.12.120|29;
> 116.212.120.0|24;
> 12.120.24.0|21;
>
>
>Now I need to map C_IP to list with longest prefix match. (As u can
>there are many IP address with 12.120. but I need to map to one with
>longest prefix match)
This may not be the smartest ways to do it, but at least it works:
use warnings; use strict;
my @IPs = qw (
212.120.128.0|19;
12.120.0.0|15;
12.120.16.0|20;
12.120.72.0|22;
12.120.96.0|20;
12.120.40.0|21;
12.120.0.0|21;
12.120.192.0|19;
12.120.16.0|22;
12.120.36.0|22;
12.120.80.0|20;
194.212.120.0|21;
212.120.32.0|19;
212.120.64.0|18;
212.120.192.0|19;
213.3.12.120|29;
116.212.120.0|24;
12.120.24.0|21;
);
sub lead {
#I'm sure this can be optimized
#or there is probably a module function somewhere, too
my ($s, $t) = @_; my $i=0;
while ($i < length ($s) and $i < length ($t)) {
if (substr($s, $i, 1) eq substr($t, $i, 1)) {
$i++;
} else {
return $i;
}
}
return $i;
}
my $C_IP = '12.120.29.25';
my $best = $IPs[0];
my $bestlen = lead($best, $C_IP);
for my $IP (@IPs) {
if (lead($IP, $C_IP) > $bestlen) {
$best = $IP;
$bestlen = lead ($best, $C_IP);
}
}
print "Longest lead: '$best'; matching $bestlen characters: '".
substr($best, 0, $bestlen). "'\n";
------------------------------
Date: Mon, 24 Nov 2008 11:45:17 -0800 (PST)
From: "friend.05@gmail.com" <hirenshah.05@gmail.com>
Subject: Re: IP address - longest prefix match
Message-Id: <85d89c48-938b-4e55-afac-f38493af90b6@q9g2000yqc.googlegroups.com>
On Nov 24, 2:24=A0pm, J=FCrgen Exner <jurge...@hotmail.com> wrote:
> "friend...@gmail.com" <hirenshah...@gmail.com> wrote:
> >Suppose I have C_IP address : 12.120.29.25
>
> >and I have list of following IP addresses :
>
> > 212.120.128.0|19;
> > 12.120.0.0|15;
> > 12.120.16.0|20;
> > 12.120.72.0|22;
> > 12.120.96.0|20;
> > 12.120.40.0|21;
> > 12.120.0.0|21;
> > 12.120.192.0|19;
> > 12.120.16.0|22;
> > 12.120.36.0|22;
> > 12.120.80.0|20;
> > 194.212.120.0|21;
> > 212.120.32.0|19;
> > 212.120.64.0|18;
> > 212.120.192.0|19;
> > 213.3.12.120|29;
> > 116.212.120.0|24;
> > 12.120.24.0|21;
>
> >Now I need to map C_IP to list with longest prefix match. (As u can
> >there are many IP address with 12.120. but I need to map to one with
> >longest prefix match)
>
> This may not be the smartest ways to do it, but at least it works:
>
> use warnings; use strict;
> my @IPs =3D qw (
> 212.120.128.0|19;
> =A012.120.0.0|15;
> =A012.120.16.0|20;
> =A012.120.72.0|22;
> =A012.120.96.0|20;
> =A012.120.40.0|21;
> =A012.120.0.0|21;
> =A012.120.192.0|19;
> =A012.120.16.0|22;
> =A012.120.36.0|22;
> =A012.120.80.0|20;
> =A0194.212.120.0|21;
> =A0212.120.32.0|19;
> =A0212.120.64.0|18;
> =A0212.120.192.0|19;
> =A0213.3.12.120|29;
> =A0116.212.120.0|24;
> =A012.120.24.0|21;
> =A0 =A0 =A0 =A0 =A0 =A0 =A0);
>
> sub lead {
> #I'm sure this can be optimized
> #or there is probably a module function somewhere, too
> =A0 =A0 my ($s, $t) =3D @_; my $i=3D0;
> =A0 =A0 while ($i < length ($s) and $i < length ($t)) {
> =A0 =A0 =A0 =A0 if (substr($s, $i, 1) eq substr($t, $i, 1)) {
> =A0 =A0 =A0 =A0 =A0 =A0 $i++;
> =A0 =A0 =A0 =A0 } else {
> =A0 =A0 =A0 =A0 =A0 =A0 return $i;
> =A0 =A0 =A0 =A0 }
> =A0 =A0 }
> =A0 =A0 return $i;
>
> }
>
> my $C_IP =3D '12.120.29.25';
> my $best =3D $IPs[0];
> my $bestlen =3D lead($best, $C_IP);
> for my $IP (@IPs) {
> =A0 =A0 if (lead($IP, $C_IP) > $bestlen) {
> =A0 =A0 =A0 =A0 $best =3D $IP;
> =A0 =A0 =A0 =A0 $bestlen =3D lead ($best, $C_IP);
> =A0 =A0 }}
>
> print "Longest lead: '$best'; matching $bestlen characters: '".
> =A0 =A0 substr($best, 0, $bestlen). "'\n";- Hide quoted text -
>
> - Show quoted text -
Thanks for your reply.
But I new to perl. I am not getting for code. Can please explain me in
more detail.
Thanks.
------------------------------
Date: Mon, 24 Nov 2008 20:09:37 GMT
From: sln@netherlands.com
Subject: Re: IP address - longest prefix match
Message-Id: <4c2mi4hhvqm68jvd2nca50u56f9ju9bs4l@4ax.com>
On Mon, 24 Nov 2008 10:45:21 -0800 (PST), "friend.05@gmail.com" <hirenshah.05@gmail.com> wrote:
>Suppose I have C_IP address : 12.120.29.25
>
>and I have list of following IP addresses :
>
>
> 212.120.128.0|19;
> 12.120.0.0|15;
> 12.120.16.0|20;
> 12.120.72.0|22;
> 12.120.96.0|20;
> 12.120.40.0|21;
> 12.120.0.0|21;
> 12.120.192.0|19;
> 12.120.16.0|22;
> 12.120.36.0|22;
> 12.120.80.0|20;
> 194.212.120.0|21;
> 212.120.32.0|19;
> 212.120.64.0|18;
> 212.120.192.0|19;
> 213.3.12.120|29;
> 116.212.120.0|24;
> 12.120.24.0|21;
>
>
>Now I need to map C_IP to list with longest prefix match. (As u can
>there are many IP address with 12.120. but I need to map to one with
>longest prefix match)
>
I get the feeling you mean 'largest' instead of 'longest'. Otherwise,
what would be the purpose of this exercise?
sln
----------------------------
# output:
# 12.120.0.0|15
# 12.120.0.0|21
# 12.120.16.0|20
# 12.120.16.0|22
# 12.120.24.0|21
# 12.120.36.0|22
# 12.120.40.0|21
# 12.120.72.0|22
# 12.120.80.0|20
# 12.120.96.0|20
# 12.120.192.0|19
# 116.212.120.0|24
# 194.212.120.0|21
# 212.120.32.0|19
# 212.120.64.0|18
# 212.120.128.0|19
# 212.120.192.0|19
# 213.3.12.120|29
# Found largest 12.120 = 12.120.192.0|19
use strict;
use warnings;
use sort 'stable';
my $ippatt = '12.120';
my @IPs = ();
my $iplargest = '';
while (<DATA>)
{
chomp;
if (/(\d{1,3})\.(\d{1,3})\.(\d{1,3})\.(\d{1,3})\|(\d*);/)
{
push @IPs, [$1,$2,$3,$4,$5];
}
}
if (@IPs)
{
for my $i (0..4) {
@IPs = sort {$a->[4-$i] <=> $b->[4-$i]} @IPs;
}
for my $ip (@IPs) {
my $ipstr = "$ip->[0].$ip->[1].$ip->[2].$ip->[3]|$ip->[4]";
print "$ipstr\n";
if ($ipstr =~ /^$ippatt/) {
$iplargest = $ipstr;
}
}
}
if (length($iplargest)) {
print "Found largest $ippatt = $iplargest\n";
} else {
print "Did not find $ippatt in list\n";
}
__DATA__
212.120.128.0|19;
12.120.0.0|15;
12.120.16.0|20;
12.120.72.0|22;
12.120.96.0|20;
12.120.40.0|21;
12.120.0.0|21;
12.120.192.0|19;
12.120.16.0|22;
12.120.36.0|22;
12.120.80.0|20;
194.212.120.0|21;
212.120.32.0|19;
212.120.64.0|18;
212.120.192.0|19;
213.3.12.120|29;
116.212.120.0|24;
12.120.24.0|21;
------------------------------
Date: Mon, 24 Nov 2008 13:53:29 -0800
From: Jürgen Exner <jurgenex@hotmail.com>
Subject: Re: IP address - longest prefix match
Message-Id: <f48mi4dkt6srmn7fuq0esf60o4qs79uv01@4ax.com>
"friend.05@gmail.com" <hirenshah.05@gmail.com> wrote:
>On Nov 24, 2:24 pm, Jürgen Exner <jurge...@hotmail.com> wrote:
>But I new to perl. I am not getting for code. Can please explain me in
>more detail.
Adding explanations inline
>> use warnings; use strict;
Never run a program without (unless you really, really know why).
>> my @IPs = qw (
>> 212.120.128.0|19;
>> 12.120.0.0|15;
>> 12.120.16.0|20;
>> 12.120.72.0|22;
>> 12.120.96.0|20;
>> 12.120.40.0|21;
>> 12.120.0.0|21;
>> 12.120.192.0|19;
>> 12.120.16.0|22;
>> 12.120.36.0|22;
>> 12.120.80.0|20;
>> 194.212.120.0|21;
>> 212.120.32.0|19;
>> 212.120.64.0|18;
>> 212.120.192.0|19;
>> 213.3.12.120|29;
>> 116.212.120.0|24;
>> 12.120.24.0|21;
>> );
Your test data
>> sub lead {
>> #I'm sure this can be optimized
>> #or there is probably a module function somewhere, too
>> my ($s, $t) = @_; my $i=0;
Initialization with of $s and $t with function parameters, use $i as
index into the strings to be compared
>> while ($i < length ($s) and $i < length ($t)) {
As long as $i hasn't reached the end of either string ...
>> if (substr($s, $i, 1) eq substr($t, $i, 1)) {
>> $i++;
... if the i-th character in both strings is the same, look at the next
character
>> } else {
>> return $i;
otherwise those strings were the same up to the current value of $i
>> }
>> }
>> return $i;
POST for while loop: $i is larger than the length of the shorter string.
Therefore one string is a complete prefix of the other.
>>
>> }
>>
>> my $C_IP = '12.120.29.25';
The value you are looking for
>> my $best = $IPs[0];
>> my $bestlen = lead($best, $C_IP);
Initialize $best and $bestlen with the first element of the test data.
Could have chosen any other, it doesn't matter which on you pick.
>> for my $IP (@IPs) {
For each IP ...
>> if (lead($IP, $C_IP) > $bestlen) {
...check if the match is better than the currently best...
>> $best = $IP;
>> $bestlen = lead ($best, $C_IP);
... and if it is then pick this one as the new currently best
>> }}
>>
>> print "Longest lead: '$best'; matching $bestlen characters: '".
>> substr($best, 0, $bestlen). "'\n";- Hide quoted text -
At the end of the loop $best will contain the best overall.
jue
------------------------------
Date: Tue, 25 Nov 2008 01:19:07 GMT
From: sln@netherlands.com
Subject: Re: IP address - longest prefix match
Message-Id: <cdgmi4dl3i1kfdntlp8evlbdgku55otkda@4ax.com>
On Mon, 24 Nov 2008 10:45:21 -0800 (PST), "friend.05@gmail.com" <hirenshah.05@gmail.com> wrote:
>Suppose I have C_IP address : 12.120.29.25
>
>and I have list of following IP addresses :
>
>
> 212.120.128.0|19;
> 12.120.0.0|15;
> 12.120.16.0|20;
> 12.120.72.0|22;
> 12.120.96.0|20;
> 12.120.40.0|21;
> 12.120.0.0|21;
> 12.120.192.0|19;
> 12.120.16.0|22;
> 12.120.36.0|22;
> 12.120.80.0|20;
> 194.212.120.0|21;
> 212.120.32.0|19;
> 212.120.64.0|18;
> 212.120.192.0|19;
> 213.3.12.120|29;
> 116.212.120.0|24;
> 12.120.24.0|21;
>
>
>Now I need to map C_IP to list with longest prefix match. (As u can
>there are many IP address with 12.120. but I need to map to one with
>longest prefix match)
>
Ok, I searched LPM. Routing table lookup.
This is the key: (C_IP address) 12.120.29.25
32 bit key = 12<<24 + 120<<16 + 29<<8 + 25
Loop(Entries)
{
Example table entry:
12.120.24.0 | 21;
^^^^^^^^^^^
32 bits
^^
Bitmask (the bits to mask) = ((2 ** 21)-1) << (32-21)
32 bit entry = 12<<24 + 120<<16 + 24<<8 + 0
Masked key = 32 bit key & Bitmask;
Masked entry = 32 bit entry & Bitmask;
if (Masked key == Masked entry && Bitmask > LargestBitmask)
{
LPM = 32 bit entry;
LargestBitmask = Bitmask;
}
}
Print the LPM..
Source (there were many, but this seamed easiest):
http://www.xilinx.com/support/documentation/application_notes/xapp738.pdf
For an entry to be considered a match to the search key, it must satisfy these three conditions
(refer also to the numbers in Figure 2):
1. The entry’s Valid bit must be set.
2. The entry’s masked IP address and the masked search key are equal to each other.
An IP address is masked by performing a bitwise AND of the mask and the IP address.
3. The entry’s mask is greater than or equal to the mask of any previously matched entry.
------------------------------------------------------
# output:
# Found possible match 12.120.192.0|19;
# Found possible match 212.120.128.0|19;
# Found possible match 12.120.0.0|15;
# Found possible match 12.120.72.0|22;
# Found possible match 12.120.96.0|20;
# Found possible match 12.120.40.0|21;
# Found possible match 12.120.0.0|21;
# Found possible match 12.120.192.0|19;
# Found possible match 12.120.36.0|22;
# Found possible match 212.120.32.0|19;
# Found possible match 212.120.64.0|18;
# Found possible match 212.120.192.0|19;
# Found possible match 213.3.12.120|29;
# Found possible match 12.120.24.0|21;
#
# LPM = 213.3.12.120|29;
use strict;
use warnings;
use sort 'stable';
my $LPM = '';
my $LargestMask = 0;
my $Key32 = 12<<24 + 120<<16 + 29<<8 + 25;
while (<DATA>)
{
chomp;
if (/(\d{1,3})\.(\d{1,3})\.(\d{1,3})\.(\d{1,3})\|(\d*)/)
{
my $Entry32 = $1<<24 + $2<<16 + $3<<8 + $4;
my $Mask = ((2 ** $5)-1) << (32-$5);
my $MaskedKey = $Key32 & $Mask;
my $MaskedEntry = $Entry32 & $Mask;
if ($MaskedKey == $MaskedEntry)
{
print "Found possible match $_\n";
if ($Mask > $LargestMask) {
$LPM = $_;
$LargestMask = $Mask;
}
}
}
}
if (length($LPM)) {
print "LPM = $LPM\n";
} else {
print "Did not find LMP match in list\n";
}
__DATA__
12.120.192.0|19;
212.120.128.0|19;
12.120.0.0|15;
12.120.16.0|20;
12.120.72.0|22;
12.120.96.0|20;
12.120.40.0|21;
12.120.0.0|21;
12.120.192.0|19;
12.120.16.0|22;
12.120.36.0|22;
12.120.80.0|20;
194.212.120.0|21;
212.120.32.0|19;
212.120.64.0|18;
212.120.192.0|19;
213.3.12.120|29;
116.212.120.0|24;
12.120.24.0|21;
------------------------------
Date: Tue, 25 Nov 2008 02:10:29 GMT
From: sln@netherlands.com
Subject: Re: IP address - longest prefix match
Message-Id: <j9nmi4tcjbh8po7kheqejk12kha56d8pfo@4ax.com>
On Tue, 25 Nov 2008 01:19:07 GMT, sln@netherlands.com wrote:
>On Mon, 24 Nov 2008 10:45:21 -0800 (PST), "friend.05@gmail.com" <hirenshah.05@gmail.com> wrote:
>
>>Suppose I have C_IP address : 12.120.29.25
>>
>>and I have list of following IP addresses :
>>
>>
[snip]
>>
>>Now I need to map C_IP to list with longest prefix match. (As u can
>>there are many IP address with 12.120. but I need to map to one with
>>longest prefix match)
>>
>Ok, I searched LPM. Routing table lookup.
>
>This is the key: (C_IP address) 12.120.29.25
>
>32 bit key = 12<<24 + 120<<16 + 29<<8 + 25
>
>Loop(Entries)
>{
> Example table entry:
> 12.120.24.0 | 21;
> ^^^^^^^^^^^
> 32 bits
> ^^
> Bitmask (the bits to mask) = ((2 ** 21)-1) << (32-21)
>
> 32 bit entry = 12<<24 + 120<<16 + 24<<8 + 0
>
> Masked key = 32 bit key & Bitmask;
> Masked entry = 32 bit entry & Bitmask;
>
> if (Masked key == Masked entry && Bitmask > LargestBitmask)
> {
> LPM = 32 bit entry;
> LargestBitmask = Bitmask;
> }
>}
>
>Print the LPM..
>
>Source (there were many, but this seamed easiest):
>http://www.xilinx.com/support/documentation/application_notes/xapp738.pdf
>
>For an entry to be considered a match to the search key, it must satisfy these three conditions
>(refer also to the numbers in Figure 2):
>1. The entry’s Valid bit must be set.
>2. The entry’s masked IP address and the masked search key are equal to each other.
>An IP address is masked by performing a bitwise AND of the mask and the IP address.
>3. The entry’s mask is greater than or equal to the mask of any previously matched entry.
>
[snip]
They also have an array of algorithyms available that shorten the search time.
The method I posted is linear.
But they have linear variations that do kind of a bubble sort.
Itterate the list just checking the first term. From that list, just check the
second, from that ... etc.
This aviods all the math of shifting all terms in each entry in the whole list.
If you get away from linear, there are some wildly exotic methodologies.
sln
------------------------------
Date: Tue, 25 Nov 2008 02:35:52 GMT
From: sln@netherlands.com
Subject: Re: IP address - longest prefix match
Message-Id: <j0pmi4p1uj8bfpiut259fau85haj9hivsd@4ax.com>
On Tue, 25 Nov 2008 01:19:07 GMT, sln@netherlands.com wrote:
>On Mon, 24 Nov 2008 10:45:21 -0800 (PST), "friend.05@gmail.com" <hirenshah.05@gmail.com> wrote:
>
>>Suppose I have C_IP address : 12.120.29.25
>>
>>and I have list of following IP addresses :
>>
>>
>> 212.120.128.0|19;
>> 12.120.0.0|15;
>> 12.120.16.0|20;
>> 12.120.72.0|22;
>> 12.120.96.0|20;
>> 12.120.40.0|21;
>> 12.120.0.0|21;
>> 12.120.192.0|19;
>> 12.120.16.0|22;
>> 12.120.36.0|22;
>> 12.120.80.0|20;
>> 194.212.120.0|21;
>> 212.120.32.0|19;
>> 212.120.64.0|18;
>> 212.120.192.0|19;
>> 213.3.12.120|29;
>> 116.212.120.0|24;
>> 12.120.24.0|21;
>>
>>
>>Now I need to map C_IP to list with longest prefix match. (As u can
>>there are many IP address with 12.120. but I need to map to one with
>>longest prefix match)
>>
>Ok, I searched LPM. Routing table lookup.
>
>This is the key: (C_IP address) 12.120.29.25
>
>32 bit key = 12<<24 + 120<<16 + 29<<8 + 25
>
>Loop(Entries)
>{
> Example table entry:
> 12.120.24.0 | 21;
> ^^^^^^^^^^^
> 32 bits
> ^^
> Bitmask (the bits to mask) = ((2 ** 21)-1) << (32-21)
>
> 32 bit entry = 12<<24 + 120<<16 + 24<<8 + 0
>
> Masked key = 32 bit key & Bitmask;
> Masked entry = 32 bit entry & Bitmask;
>
> if (Masked key == Masked entry && Bitmask > LargestBitmask)
> {
> LPM = 32 bit entry;
> LargestBitmask = Bitmask;
> }
>}
>
>Print the LPM..
>
>Source (there were many, but this seamed easiest):
>http://www.xilinx.com/support/documentation/application_notes/xapp738.pdf
>
>For an entry to be considered a match to the search key, it must satisfy these three conditions
>(refer also to the numbers in Figure 2):
>1. The entry’s Valid bit must be set.
>2. The entry’s masked IP address and the masked search key are equal to each other.
>An IP address is masked by performing a bitwise AND of the mask and the IP address.
>3. The entry’s mask is greater than or equal to the mask of any previously matched entry.
>
>
>------------------------------------------------------
I guess it would help if I pay attention to what I'm doing..
sln
-----------------------------------------------
# output:
# Found possible match 12.120.0.0|15;
# Found possible match 12.120.16.0|20;
# Found possible match 12.120.24.0|21;
#
# LPM = 12.120.24.0|21;
use strict;
use warnings;
use sort 'stable';
my $LPM = '';
my $LargestMask = 0;
# search LPM for: 12.120.29.25;
my $Key32 = (12<<24) + (120<<16) + (29<<8) + 25;
while (<DATA>)
{
chomp;
if (/(\d{1,3})\.(\d{1,3})\.(\d{1,3})\.(\d{1,3})\|(\d*)/)
{
my $Entry32 = ($1<<24) + ($2<<16) + ($3<<8) + $4;
my $Mask = ((2 ** $5)-1) << (32-$5);
my $MaskedKey = $Key32 & $Mask;
my $MaskedEntry = $Entry32 & $Mask;
if ($MaskedKey > 0 && $MaskedKey == $MaskedEntry)
{
print "Found possible match $_\n";
if ($Mask > $LargestMask) {
$LPM = $_;
$LargestMask = $Mask;
}
}
}
}
if (length($LPM)) {
print "\nLPM = $LPM\n";
} else {
print "Did not find LMP match in list\n";
}
__DATA__
12.120.192.0|19;
212.120.128.0|19;
12.120.0.0|15;
12.120.16.0|20;
12.120.72.0|22;
12.120.96.0|20;
12.120.40.0|21;
12.120.0.0|21;
12.120.192.0|19;
12.120.16.0|22;
12.120.36.0|22;
12.120.80.0|20;
194.212.120.0|21;
212.120.32.0|19;
212.120.64.0|18;
212.120.192.0|19;
213.3.12.120|29;
116.212.120.0|24;
12.120.24.0|21;
------------------------------
Date: Mon, 24 Nov 2008 14:36:13 -0600
From: Ted Zlatanov <tzz@lifelogs.com>
Subject: Re: longest prefix match
Message-Id: <86zljorhdu.fsf@lifelogs.com>
On Mon, 24 Nov 2008 10:23:34 -0800 (PST) "friend.05@gmail.com" <hirenshah.05@gmail.com> wrote:
f0c> On Nov 24, 12:05 pm, Ted Zlatanov <t...@lifelogs.com> wrote:
>> On Mon, 24 Nov 2008 08:46:53 -0800 (PST) "friend...@gmail.com" <hirenshah...@gmail.com> wrote:
>>
f> Suppose I have C_IP address : 12.120.29.25
>>
f> and I have list of following IP addresses :
f> 212.120.128.0|19;
f> 12.120.0.0|15;
f> 12.120.16.0|20;
f> 12.120.72.0|22;
f> 12.120.96.0|20;
f> 12.120.40.0|21;
f> 12.120.0.0|21;
f> 12.120.192.0|19;
f> 12.120.16.0|22;
f> 12.120.36.0|22;
f> 12.120.80.0|20;
f> 194.212.120.0|21;
f> 212.120.32.0|19;
f> 212.120.64.0|18;
f> 212.120.192.0|19;
f> 213.3.12.120|29;
f> 116.212.120.0|24;
f> 12.120.24.0|21;
>>
f> Now I need to map C_IP to list with longest prefix match. (As u can
f> there are many IP address with 12.120. but I need to map to one with
f> longest prefix match)
>>
>> Look at Net::Netmask and the match() method in particular; just iterate
>> through the list above in order from largest prefix to smallest and
>> return when there's a match.
f> I am little confuse with largest prefix to smallest.
f> Example:
f> 12.120.16.0|20;
f> 12.120.96.0|20;
f> 12.120.40.0|21;
f> 12.120.72.0|22;
f> 12.120.16.0|22;
f> In above list what will be order of largest prefix to smallest.
f> And is there any tutorial with exmple where can I see steps to use
f> Net::Netmask
First of all, let's be clear about the problem as I see it, because I
think you haven't understood it clearly. If I'm wrong, sorry, but I'm
trying to help you.
I think you're trying to find the best (smallest) net block match for an
IP. The numbers you quote are net blocks, and you should know what that
means in IPv4 terms. Look it up if you don't.
The "longest" match you want really means the most specific net block,
meaning the net block with the most bits unmasked (thus, the fewest
addresses in it). If there's a tie by number of unmasked bits, the
first one found can win. In the example you give, either of the 22's
for example, if they match.
OK, so the code below walks through the net blocks, adds them to $table,
then finds the smallest net block in $table that matches the IPs. Do
"print Dumper $table" to see what the storage looks like, if you're
curious. I wrote it so you can give it multiple IPs from the command
line, and it doesn't catch the cases where the IP is not found or
invalid.
#!/usr/bin/perl
use warnings;
use strict;
use Data::Dumper;
use Net::Netmask;
my $table = {};
while (<DATA>)
{
chomp;
my $net = new Net::Netmask ($_);
$net->storeNetblock($table);
}
print findNetblock($_, $table) . "\n" foreach @ARGV;
__DATA__
12.120.16.0/20
12.120.96.0/20
12.120.40.0/21
12.120.72.0/22
12.120.16.0/22
------------------------------
Date: 6 Apr 2001 21:33:47 GMT (Last modified)
From: Perl-Users-Request@ruby.oce.orst.edu (Perl-Users-Digest Admin)
Subject: Digest Administrivia (Last modified: 6 Apr 01)
Message-Id: <null>
Administrivia:
#The Perl-Users Digest is a retransmission of the USENET newsgroup
#comp.lang.perl.misc. For subscription or unsubscription requests, send
#the single line:
#
# subscribe perl-users
#or:
# unsubscribe perl-users
#
#to almanac@ruby.oce.orst.edu.
NOTE: due to the current flood of worm email banging on ruby, the smtp
server on ruby has been shut off until further notice.
To submit articles to comp.lang.perl.announce, send your article to
clpa@perl.com.
#To request back copies (available for a week or so), send your request
#to almanac@ruby.oce.orst.edu with the command "send perl-users x.y",
#where x is the volume number and y is the issue number.
#For other requests pertaining to the digest, send mail to
#perl-users-request@ruby.oce.orst.edu. Do not waste your time or mine
#sending perl questions to the -request address, I don't have time to
#answer them even if I did know the answer.
------------------------------
End of Perl-Users Digest V11 Issue 2002
***************************************
