10
\$\begingroup\$

IPv4 addresses are 32 bits wide, and thus the size of the address space is 232, or 4,294,967,296. However, this is only a theoretical upper-bound. It is not an accurate representation of all the addresses that may actually be used on the public internet.

For the purposes of this challenge, it is assumed that all addressing is classful. In reality, classful subdivision of address space has been superseded by CIDR (Classless Inter-Domain Routing and VLSM (Variable Length Subnet Masking), but this is ignored for this challenge.

According to the classful address scheme, there are 3 classes:

  • Class A - 0.0.0.0 to 127.255.255.255 with /8 netmask length
  • Class B - 128.0.0.0 to 191.255.255.255 with /16 netmask length
  • Class C - 192.0.0.0 to 223.255.255.255 with /24 netmask length

Classes D (multicast) and E (reserved) are also defined, but these are not used for public unicast addresses.

Each class is subdivided into networks according to the netmask for that class.

Thus 3.0.0.0 is an example of a Class A network. The netmask length for Class A is 8, so the full address space for this network is 3.0.0.0 to 3.255.255.255. However, the first address (3.0.0.0) is reserved as the network address and the last address (3.255.255.255) is reserved as the broadcast address for that network. Thus the actual range of usable addresses is 3.0.0.1 to 3.255.255.254 which is 224 - 2 (= 16,777,214) total addresses.

Similarly, 200.20.30.0 is an example of a Class C network. The netmask length for Class C is 24, so the full address space for this network is 200.20.30.0 to 200.20.30.255. Removing the network and broadcast addresses leaves the actual range of usable addresses is 200.20.30.1 to 200.20.30.254 which is 28 - 2 (= 254) total addresses.

There are further limitations on address ranges that may be used for public unicast. According to RFC 6890, the disallowed ranges are:

  • 0.0.0.0/8 - Local networking
  • 10.0.0.0/8 - Private-Use
  • 100.64.0.0/10 - Shared Address Space
  • 127.0.0.0/8 - Loopback
  • 169.254.0.0/16 - Link Local
  • 172.16.0.0/12- Private-Use
  • 192.0.0.0/24 - IETF Protocol Assignments
  • 192.0.2.0/24 - Reserved for use in documentation
  • 192.88.99.0/24 - 6to4 Relay Anycast
  • 192.168.0.0/16 - Private-Use
  • 198.18.0.0/15 - Benchmarking
  • 198.51.100.0/24 - Reserved for use in documentation
  • 203.0.113.0/24 - Reserved for use in documentation

Note that the above list uses VLSR netmasks to efficiently specify a range. In all but one cases, the given mask length has specificity is less than or equal to the normal classful mask length for the start of the range. Thus each of these VLSR ranges is equivalent to one or more classful networks. E.g. 172.16.0.0/12 is equivalent to the Class B networks 172.16.0.0 to 172.31.0.0 or the address range 172.16.0.0 to 172.31.255.255.

The exception to this rule is the 100.64.0.0/10 VLSR range, which is more specific than the containing 100.0.0.0 Class A range. Thus 100.0.0.0 will be handled like other Class A ranges with the exception that it has a 4,194,304-address hole in the middle. The valid addresses in this Class A range will be 100.0.0.0 to 100.63.255.255 and 100.128.0.0 to 100.255.255.254, a total of 224 - 222 - 2 (= 12,582,910) total addresses.

The goal of this challenge is to output all Class A, B and C unicast IPv4 addresses that may be validly assigned to a public internet host (i.e. excluding those detailed above).

  • No input will be given and should not be expected.

  • Output may be in any form convenient for your language, e.g. array, list, delimited string. Addresses must be output in standard dotted decimal format.

  • Output order does not matter.

  • Builtins that specifically give the required ranges of addresses are disallowed. Similarly any methods to dynamically inspect a BGP (or other protocol) routing table for the public internet are disallowed.

The numerically lowest address will be 1.0.0.1 and the numerically highest will be 223.255.255.254.


This challenge is similar to Print out all IPv6 addresses, but because of the restrictions should require non-trivially different implementation.

\$\endgroup\$
2
\$\begingroup\$

PowerShell, 648 641 625 bytes

for([uint64]$a=16MB;$a-lt2GB-16mb;$a++){if(($a%16mb)*(($a+1)%16mb)*($a-lt160MB-or$a-gt176MB)*($a-lt1604MB-or$a-ge1608MB)){([ipaddress]$a).IPAddressToString}}
for($a=2GB;$a-lt3GB;$a++){if(($a%64kb)*(($a+1)%64kb)*($a-lt2785152kb-or$a-gt2720mb)*($a-lt2753mb-or$a-gt2754mb)){([ipaddress]$a).IPAddressToString}}
for($a=3221225728;$a-lt3.5GB;$a++){if(($a%256)*(($a+1)%256)*(($a-lt3221225984-or$a-gt3221226240))*(($a-lt3227017984-or$a-gt3151385kb))*(($a-lt3156480kb-or$a-gt3156544kb))*(($a-lt3245184kb-or$a-gt3245312kb))*(($a-lt3247321kb-or$a-gt3325256959))*(($a-lt3405803776-or$a-gt3405804032))){([ipaddress]$a).IPAddressToString}}

Edit 1 -- I've golfed out all remaining powers-of-two operators, which saved an additional 7 bytes.
Edit 2 -- Moved the [uint64] cast to the first declaration of $a which eliminated the other two re-casts which saved 16 bytes.

Three lines, Class A / Class B / Class C. Left as separate lines for readability. ;-)

Two key points for understanding what's going on:

  • PowerShell has powers-of-two operators KB, MB, GB. For example, 4KB will return 4096 as an int. We leverage that in multiple locations to shave dozens of bytes.
  • The .NET [ipaddress] class will try to parse a numerical value as an IP address by taking the number's binary representation. We use that constructor with the IPAddressToString argument for output.

By coupling those two things, we're able to just treat the IP addresses as numbers and loop through them with a for() loop. For example, the first loop for Class A subnets goes from 16MB to 2GB-16MB, or from 16777216 to 2130706432. The binary representation of 16777216 is 1000000000000000000000000 or 00000001.00000000.00000000.00000000 if we split it into 8-bit chunks so we can easily see that corresponds to 1.0.0.0 in dotted-decimal notation. Similarly, 2130706432 can be written as 01111111000000000000000000000000 or 01111111.00000000.00000000.00000000 or 127.0.0.0. Each integer, or power-of-two integer, used here can be rewritten as an IP address in this fashion.

So, for each loop iteration, we construct an if() statement to weed out the excluded addresses, by multiplying the individual statements together. Since the first statement in each if is an integer (thanks to the modulo testing), the remaining Boolean values are converted to either 0 or 1 for false/true. If any one of the statements are false, the whole multiplication will turn to 0 and thus be false. Thus, only if all the statements are true, will we output the result of the parsing.

Slightly Ungolfed:

# Class A
for($a=16MB;$a-lt2GB-16mb;$a++){
  $b=($a%16mb)                     # x.0.0.0
  $b*=(($a+1)%16mb)                # x.255.255.255
  $b*=($a-lt160MB-or$a-gt176MB)    # 10.0.0.0/8
  $b*=($a-lt1604MB-or$a-ge1608MB)  # 100.64.0.0/10
  if($b){([ipaddress]::Parse($a)).IPAddressToString}
}

# Class B
for($a=2GB;$a-lt3GB;$a++){
  $b=($a%64kb)                           # x.y.0.0
  $b*=(($a+1)%64kb)                      # x.y.255.255
  $b*=(($a-lt2785152kb-or$a-gt2720mb))  # 169.254.0.0/16
  $b*=(($a-lt2753mb-or$a-gt2754mb))      # 172.16.0.0/12
  if($b){([ipaddress]::Parse($a)).IPAddressToString}
}

# Class C
for($a=3221225728;$a-lt3.5GB;$a++){
  $b=($a%256)                               # x.y.z.0
  $b*=(($a+1)%256)                          # x.y.z.255
  $b*=(($a-lt3221225984-or$a-gt3221226240)) # 192.0.2.0/24
  $b*=(($a-lt3227017984-or$a-gt3151385kb)) # 192.88.99.0/24
  $b*=(($a-lt3156480kb-or$a-gt3156544kb)) # 192.168.0.0/16
  $b*=(($a-lt3245184kb-or$a-gt3245312kb)) # 198.18.0.0/15
  $b*=(($a-lt3247321kb-or$a-gt3325256959)) # 198.51.100.0/24
  $b*=(($a-lt3405803776-or$a-gt3405804032)) # 203.0.113.0/24
  if($b){([ipaddress]::Parse($a)).IPAddressToString}
}
\$\endgroup\$
1
\$\begingroup\$

Batch, 1930 1884 1848 1830 bytes

@echo off
for /l %%a in (1,1,9)do call:a1 %%a
for /l %%a in (11,1,99)do call:a1 %%a
for /l %%b in (0,1,63)do call:a2 100 %%b
for /l %%b in (128,1,255)do call:a2 100 %%b
for /l %%a in (101,1,126)do call:a1 %%a
for /l %%a in (128,1,168)do call:b1 %%a
for /l %%b in (0,1,253)do call:b2 169 %%b
call:b2 169 255
call:b1 170
call:b1 171
for /l %%b in (0,1,15)do call:b2 172 %%b
for /l %%b in (32,1,255)do call:b2 172 %%b
for /l %%a in (173,1,191)do call:b1 %%a
call:c3 192 0 1
for /l %%c in (3,1,255)do call:c3 192 0 %%c
for /l %%b in (1,1,87)do call:c2 192 %%b
for /l %%c in (0,1,98)do call:c3 192 88 %%c
for /l %%c in (100,1,255)do call:c3 192 88 %%c
for /l %%b in (89,1,167)do call:c2 192 %%b
for /l %%b in (169,1,255)do call:c2 192 %%b
for /l %%a in (193,1,197)do call:c1 %%a
for /l %%b in (0,1,17)do call:c2 198 %%b
for /l %%b in (20,1,50)do call:c2 198 %%b
for /l %%c in (0,1,99)do call:c3 198 51 %%c
for /l %%c in (101,1,255)do call:c3 198 51 %%c
for /l %%b in (52,1,255)do call:c2 198 %%b
for /l %%a in (199,1,202)do call:c1 %%a
for /l %%c in (0,1,112)do call:c3 203 0 %%c
for /l %%c in (114,1,255)do call:c3 203 0 %%c
for /l %%b in (1,1,255)do call:c2 203 %%b
for /l %%a in (204,1,223)do call:c1 %%a
exit/b
:a1
for /l %%b in (0,1,255)do call:a2 %1 %%b
exit/b
:a2
for /l %%c in (0,1,255)do call:a3 %1 %2 %%c
exit/b
:a3
for /l %%d in (0,1,255)do if not %2%3%%d==000 if not %2%3%%d==255255255 echo %1.%2.%3.%%d
exit/b
:b1
for /l %%b in (0,1,255)do call:b2 %1 %%b
exit/b
:b2
for /l %%c in (0,1,255)do call:b3 %1 %2 %%c
exit/b
:b3
for /l %%d in (0,1,255)do if not %3%%d==00 if not %3%%d==255255 echo %1.%2.%3.%%d
exit/b
:c1
for /l %%b in (0,1,255)do call:c2 %1 %%b
exit/b
:c2
for /l %%c in (0,1,255)do call:c3 %1 %2 %%c
exit/b
:c3
for /l %%d in (1,1,254)do echo %1.%2.%3.%%d

Edit: Saved 46 82 bytes by removing unnecessary spaces. Saved 18 bytes by using exit/b instead of goto:eof.

\$\endgroup\$
  • 1
    \$\begingroup\$ I count 1872 bytes. You technically don't need the @echo off, as well. \$\endgroup\$ – Addison Crump Jan 29 '16 at 17:29
  • \$\begingroup\$ @FlagAsSpam Probably CRs; Notepad likes to save them. \$\endgroup\$ – Neil Jan 29 '16 at 17:40
  • \$\begingroup\$ I think you can remove them, since we count by Unix UTF-8 bytes. \$\endgroup\$ – Addison Crump Jan 29 '16 at 17:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.