Генерация и вывод всех адресов на Си
Только что обнаружил ошибку в ней, результат, приведенный внизу (с учетом вывода) не корректен.
puts(str); надо перенести во внутренний цикл
В этом случае (вывод в /dev/null т.к. на диске у меня места под 64Гбайт файл нет)
время работы 4m 43.46s
#include <stdio.h>
#include <time.h>
#include <string.h>
#include <stdlib.h>
main ()
{
int i,n1,n2,n3,n4;
char str[100], *p, *q;
char *nn[256];
for (i = 0; i < 256; i++) {
sprintf (str,"%d",i);
nn[i] = strdup(str);
}
time_t start = time(NULL);
for (n1 = 0; n1 < 256; n1++)
for (n2 = 0; n2 < 256; n2++) {
for (n3 = 0; n3 < 256; n3++) {
for (n4 = 0; n4 < 256; n4++) {
p = str;
q = nn[n1];
while (*q)
*p++ = *q++;
*p++ = '.';
q = nn[n2];
while (*q)
*p++ = *q++;
*p++ = '.';
q = nn[n3];
while (*q)
*p++ = *q++;
*p++ = '.';
q = nn[n4];
while (*q)
*p++ = *q++;
*p++ = 0;
}
puts(str);
}
}
fprintf (stderr,"End %ld str=%s\n",time(NULL)-start,str);
exit(0);
}
При копи-паст слегка отступы сползли.
Запустил с записью в файл на диск 1m 13.08s размер файла 246808576 байт.
комментарий
Да питон с 19 минутами это здорово. Язык мне (заочно) симпатичен. Не думал, что такой шустрый интерпретатор.
UPDATE
Да. Комментарии закончились. Ради интереса сделал еще один оптимизированный вариант и записал все IP на диск
avp@avp-ubu1:/media/sf_sharedir$ head iplist
0.0.0.0
0.0.0.1
0.0.0.2
0.0.0.3
0.0.0.4
0.0.0.5
0.0.0.6
0.0.0.7
0.0.0.8
0.0.0.9
avp@avp-ubu1:/media/sf_sharedir$ tail iplist
255.255.255.247
255.255.255.248
255.255.255.249
255.255.255.250
255.255.255.251
255.255.255.252
255.255.255.253
255.255.255.254
255.255.255.255
avp@avp-ubu1:/media/sf_sharedir$ ll /media/sf_sharedir/iplist
-rwxrwx--- 1 root vboxsf 68719476736 2012-01-13 00:05 /media/sf_sharedir/iplist*
avp@avp-ubu1:/media/sf_sharedir$
Машина I5-2500 3.3 GHz 4GB Windows-7 64-bit, VirtualBox Ubuntu 10.04 64-bit 4cpu 1GB
Время генерации с записью в /dev/null 29.043 sec, с записью в файл 719769 msec (12 минут).
Оптимизированный код:
/*
Перебор разных IP
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
long long mtime(void);
// 1. Тривиальный перебор 2^32, генерация строковой формы
main (int ac, char *av)
{
long long start = mtime();
int l, n1, n2, n3, n4, k1, k2, k3;
char *outbuf = malloc((l = 256*256*16)+1);
outbuf[l] = 0;
char str[20], *digs[256], *p, *q;
fprintf (stderr,"Тривиальный перебор 4 млрд. IP\n");
for (n1 = 0; n1 < 256; n1++) {
sprintf (str,"%d",n1);
digs[n1] = strdup(str);
}
for (n1 = 0; n1 < 256; n1++) {
for (k1 = 0, q = digs[n1]; *q; k1++)
str[k1] = *q++;
str[k1++] = '.';
for (n2 = 0; n2 < 256; n2++) {
for (k2 = k1, q = digs[n2]; *q; k2++)
str[k2] = *q++;
str[k2++] = '.';
p = outbuf;
for (n3 = 0; n3 < 256; n3++) {
for (k3 = k2, q = digs[n3]; *q; k3++)
str[k3] = *q++;
str[k3++] = '.'; // здесь k3 длина str
for (n4 = 0; n4 < 256; n4++) {
memcpy(p,str,k3);
p+=k3;
for (q = digs[n4]; *q;)
*p++ = *q++;
*p++ = '\n';
}
}
write (1,outbuf,p-outbuf);
// fprintf (stderr,"%sXXX\n",str);
}
}
fprintf (stderr,"End %lld msec\n",mtime()-start);
exit (0);
}
Функция mtime() возвращает текущее время в миллисекундах, для экономии места опускаю ее код.
М.б. будет время и желание сделаю параллельный вариант (IMHO время с записью на диск все равно останется порядка 12 мин.), попробую загрузить все 4 cpu.
UPDATE-2
Программа выводит все "счастливые" IP. Вместе с выводом 3084214728 байт в /dev/null 27 sec на DualCore 2.7 GHz (всего 215397594 IP).
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#ifdef WIN32
#define mtime clock
#else
long long mtime(void);
#endif
#define OUTPUT 1
main ()
{
long long start = mtime(), sumo = 0;
int b, b1, b2, b3, b4, s1, s2, ss1, ss2, k = 0;
#if OUTPUT
char *outbuf = malloc(256*256*16+1);
char str[20], *digs[256], *p, *q;
for (b = 0; b < 256; b++) {
sprintf (str,"%d",b);
digs[b] = strdup(str);
}
#endif
fprintf (stderr,"Поиск количества \"Счастливых\" IP (nested loops)\n");
for (b1 = 0; b1 < 256; b1++) {
b = b1;
s1 = b%10; b = b/10;
s1 += b%10;
s1 += b/10;
// fprintf (stderr,"%d.x.x.x\n",b1);
for (b2 = 0; b2 < 256; b2++) {
b = b2;
ss1 = s1 + b%10; b = b/10;
ss1 += b%10;
ss1 += b/10;
#if OUTPUT
p = outbuf;
#endif
for (b3 = 0; b3 < 256; b3++) {
b = b3;
s2 = b%10; b = b/10;
s2 += b%10;
s2 += b/10;
for (b4 = 0; b4 < 256; b4++) {
b = b4;
ss2 = s2 + b%10; b = b/10;
ss2 += b%10;
ss2 += b/10;
if (ss1 == ss2) {
k++;
#if OUTPUT
for (q = digs[b1]; *q;)
*p++ = *q++;
*p++ = '.';
for (q = digs[b2]; *q;)
*p++ = *q++;
*p++ = '.';
for (q = digs[b3]; *q;)
*p++ = *q++;
*p++ = '.';
for (q = digs[b4]; *q;)
*p++ = *q++;
*p++ = '\n';
#endif
}
}
}
#if OUTPUT
write (1,outbuf,p-outbuf);
sumo += (p-outbuf);
#endif
}
}
fprintf (stderr,"Всего %d \"Счастливых\" IP (%lld msec) вывод %lld байт\n",
k,mtime()-start,sumo);
}