main.c

   1 #ifdef __linux__
   2 #define _POSIX_C_SOURCE 200112L
   3 #endif
   4
   5 #include <stdio.h>
   6 #include <stdlib.h>
   7 #include <stdint.h>
   8 #include <string.h>
   9 #include <assert.h>
  10 #include <time.h>
  11 #include <pthread.h>
  12 #include <signal.h>
  13 #include <sys/stat.h>
  14 #include <sodium/randombytes.h>
  15
  16 #include "types.h"
  17 #include "likely.h"
  18 #include "vec.h"
  19 #include "base32.h"
  20 #include "cpucount.h"
  21 #include "keccak.h"
  22 #include "ed25519/ed25519.h"
  23
  24 // additional leading zero is added by C
  25 static const char * const pkprefix = "== ed25519v1-public: type0 ==\0\0";
  26 #define pkprefixlen (29 + 3)
  27 static const char * const skprefix = "== ed25519v1-secret: type0 ==\0\0";
  28 #define skprefixlen (29 + 3)
  29 static const char * const checksumstr = ".onion checksum";
  30 #define checksumstrlen 15
  31
  32 // output directory
  33 static char *workdir = 0;
  34 static size_t workdirlen = 0;
  35
  36 static int quietflag = 0;
  37
  38 #define SECRET_LEN 64
  39 #define PUBLIC_LEN 32
  40 #define SEED_LEN   32
  41 // with checksum + version num
  42 #define PUBONION_LEN (PUBLIC_LEN + 3)
  43 // with newline included
  44 #define ONIONLEN 62
  45
  46 static size_t onionendpos;   // end of .onion within string
  47 static size_t direndpos;     // end of dir before .onion within string
  48 static size_t printstartpos; // where to start printing from
  49 static size_t printlen;      // precalculated, related to printstartpos
  50
  51 static pthread_mutex_t fout_mutex;
  52 static FILE *fout;
  53 static size_t numneedgenerate = 0;
  54 static pthread_mutex_t keysgenerated_mutex;
  55 static volatile size_t keysgenerated = 0;
  56 static volatile int endwork = 0;
  57
  58 static void termhandler(int sig)
  59 {
  60         switch (sig) {
  61         case SIGTERM:
  62         case SIGINT:
  63                 endwork = 1;
  64                 break;
  65         }
  66 }
  67
  68 // filters stuff
  69
  70 #ifndef BINFILTERLEN
  71 #define BINFILTERLEN PUBLIC_LEN
  72 #endif
  73 struct binfilter {
  74         u8 f[BINFILTERLEN];
  75         size_t len; // real len minus one
  76         u8 mask;
  77 } ;
  78
  79 #ifdef INTFILTER
  80 #ifndef IFT
  81 #define IFT u64
  82 #endif
  83 struct intfilter {
  84         IFT f;
  85 #ifndef BINSEARCH
  86         IFT m;
  87 #endif
  88 } ;
  89 VEC_STRUCT(ifiltervec,struct intfilter) ifilters;
  90 #ifdef BINSEARCH
  91 IFT ifiltermask;
  92 #endif // BINSEARCH
  93 #else // INTFILTER
  94 VEC_STRUCT(bfiltervec,struct binfilter) bfilters;
  95 #endif // INTFILTER
  96
  97 static void filters_init()
  98 {
  99 #ifdef INTFILTER
 100         VEC_INIT(ifilters);
 101 #else
 102         VEC_INIT(bfilters);
 103 #endif
 104 }
 105
 106 #ifdef INTFILTER
 107 // o - old filter, n - new
 108 // return -1 - old stays, 0 - no conflict, 1 - new overrides old
 109 // assumes masked bits are cleared already
 110 #ifndef BINSEARCH
 111 static inline int ifilter_conflict(struct intfilter *o,struct intfilter *n)
 112 {
 113         if ((o->f & n->m) != (n->f & o->m))
 114                 return 0;
 115         // determine which filter contain less bits
 116         if (o->m <= n->m)
 117                 return -1;
 118         return 1;
 119 }
 120 #endif // BINSEARCH
 121 #else // INTFILTER
 122 // o - old filter, n - new
 123 // return: -1 - old stays, 0 - no conflict, 1 - new overrides old
 124 // assumes irrelevant bits are cleared already
 125 static inline int bfilter_conflict(struct binfilter *o,struct binfilter *n)
 126 {
 127         for (size_t i = 0;i < sizeof(o->f);++i) {
 128                 u8 oo,nn;
 129                 if (i < n->len)
 130                         oo = o->f[i];
 131                 else if (i == n->len)
 132                         oo = o->f[i] & n->mask;
 133                 else
 134                         oo = 0;
 135                 if (i < o->len)
 136                         nn = n->f[i];
 137                 else if (i == o->len)
 138                         nn = n->f[i] & o->mask;
 139                 else
 140                         nn = 0;
 141                 if (oo != nn)
 142                         return 0;
 143         }
 144         // functional filters subset was the same
 145         // determine which filter contain less bits
 146         if (o->len < n->len)
 147                 return -1;
 148         if (o->len > n->len)
 149                 return 1;
 150         if (o->mask <= n->mask)
 151                 return -1;
 152         return 1;
 153 }
 154 #endif
 155
 156 #ifdef INTFILTER
 157 #ifdef BINSEARCH
 158 /*
 159  * raw representation -- FF.FF.F0.00
 160  * big endian         -- 0xFFFFF000
 161  * little endian      -- 0x00F0FFFF
 162  * b: 0xFFffF000 ^ 0xFFff0000 -> 0x0000F000
 163  *   0x0000F000 + 1 -> 0x0000F001
 164  *   0x0000F000 & 0x0000F001 -> 0x0000F000 <- shifted mask
 165  *   0x0000F000 ^ 0x0000F000 -> 0x00000000 <- direct mask
 166  *   0x0000F000 ^ 0x00000000 -> 0x0000F000 <- shifted mask
 167  * l: 0x00f0FFff ^ 0x0000FFff -> 0x00f00000
 168  *   0x00f00000 + 1 -> 0x00f00001
 169  *   0x00f00000 & 0x00f00001 -> 0x00f00000 <- shifted mask
 170  *   0x00f00000 ^ 0x00f00000 -> 0x00000000 <- direct mask
 171  *   0x00f00000 ^ 0x00000000 -> 0x00f00000 <- shifted mask
 172  *
 173  * b: 0xFFffFFff ^ 0xF0000000 -> 0x0FffFFff
 174  *   0x0FffFFff + 1 -> 0x10000000
 175  *   0x0FffFFff & 0x10000000 -> 0x00000000 <- shifted mask
 176  *   0x0FffFFff ^ 0x00000000 -> 0x0FffFFff <- direct mask
 177  *   0x0FffFFff ^ 0x0FffFFff -> 0x00000000 <- shifted mask
 178  * l: 0xFFffFFff ^ 0x000000f0 -> 0xFFffFF0f
 179  *   0xFFffFF0f + 1 -> 0xFFffFF10
 180  *   0xFFffFF0f & 0xFFffFF10 -> 0xFFffFF00 <- shifted mask
 181  *   0xFFffFF0f ^ 0xFFffFF00 -> 0x0000000f <- direct mask
 182  *   0xFFffFF0f ^ 0x0000000f -> 0xFFffFF00 <- shifted mask
 183  *
 184  * essentially, we have to make direct mask + shifted mask bits worth of information
 185  * and then split it into 2 parts
 186  * we do not need absolute shifted mask shifting value, just relative to direct mask
 187  * 0x0sss00dd - shifted & direct mask combo
 188  * 0x000sssdd - combined mask
 189  * 8 - relshiftval
 190  * generate values from 0x00000000 to 0x000sssdd
 191  * for each value, realmask <- (val & 0x000000dd) | ((val & 0x000sss00) << relshiftval)
 192  * or..
 193  * realmask <- (val & 0x000000dd) | ((val << relshiftval) & 0x0sss0000)
 194  * ...
 195  * above method doesn't work in some cases. better way:
 196  * l: 0x80ffFFff ^ 0x00f0FFff -> 0x800f0000
 197  *   0x800f0000 >> 16 -> 0x0000800f
 198  *   0x0000800f + 1 -> 0x00008010
 199  *   0x0000800f & 0x00008010 -> 0x00008000 <- smask
 200  *   0x0000800f ^ 0x00008000 -> 0x0000000f <- dmask
 201  */
 202
 203 static const int littleendian = 1;
 204
 205 static int ifilter_compare(const void *p1,const void *p2)
 206 {
 207         if (((const struct intfilter *)p1)->f < ((const struct intfilter *)p2)->f) return -1;
 208         if (((const struct intfilter *)p1)->f > ((const struct intfilter *)p2)->f) return 1;
 209         return 0;
 210 }
 211
 212 static void ifilter_sort()
 213 {
 214         qsort(&VEC_BUF(ifilters,0),VEC_LENGTH(ifilters),sizeof(struct intfilter),ifilter_compare);
 215 }
 216
 217 // if res1==res2 then no results found but res1 tells where it should be inserted
 218 static void ifilter_find(IFT fltr,size_t start,size_t end,size_t *res1,size_t *res2)
 219 {
 220         size_t it;
 221         for (size_t down = start, up = end;it = (up + down) / 2, down < up;) {
 222                 if (fltr < VEC_BUF(ifilters,it).f)
 223                         up = it;
 224                 else if (fltr > VEC_BUF(ifilters,it).f)
 225                         down = it + 1;
 226                 else
 227                         break;
 228         }
 229         *res1 = it;
 230         while (*res1 > start && VEC_BUF(ifilters,*res1 - 1).f == fltr)
 231                 --*res1;
 232         *res2 = it;
 233         while (*res2 < end && VEC_BUF(ifilters,*res2).f == fltr)
 234                 ++*res2;
 235 }
 236
 237 #define EXPVAL(init,j,dmask,smask,ishift,rshift) \
 238         ((init) | ((((j) & (dmask)) | (((j) << (rshift)) & (smask))) << (ishift)))
 239 // add expanded set of values
 240 // allocates space on its own
 241 static void ifilter_addexpanded(
 242         struct intfilter *ifltr,
 243         IFT dmask,IFT smask,IFT cmask,
 244         int ishift,int rshift)
 245 {
 246         if (*(const u8 *)&littleendian) {
 247                 for (size_t j = 0,r1,r2 = 0;;++j,++r2) {
 248                         IFT cval = EXPVAL(ifltr->f,j,dmask,smask,ishift,rshift);
 249                         ifilter_find(cval,r2,VEC_LENGTH(ifilters),&r1,&r2);
 250                         if (r1 != r2) {
 251                                 continue;
 252                                 // already exists
 253                         }
 254                         VEC_INSERT1(ifilters,r1);
 255                         VEC_BUF(ifilters,r1).f = cval;
 256                         if (j == cmask)
 257                                 break;
 258                 }
 259         }
 260         else {
 261                 size_t r1,r2,r3,r4;
 262                 ifilter_find(ifltr->f,0,VEC_LENGTH(ifilters),&r1,&r2);
 263                 ifilter_find(EXPVAL(ifltr->f,cmask,dmask,smask,ishift,rshift),r2,VEC_LENGTH(ifilters),&r3,&r4);
 264                 if (r4 - r1 >= cmask + 1)
 265                         return; // already have all of needed stuff
 266                 VEC_INSERTN(ifilters,r4,cmask + 1 - (r4 - r1));
 267                 for (size_t j = 0;;++j) {
 268                         VEC_BUF(ifilters,r1 + j).f = EXPVAL(ifltr->f,j,dmask,smask,ishift,rshift);
 269                         if (j == cmask)
 270                                 break;
 271                 }
 272         }
 273 }
 274
 275 // expand existing stuff
 276 // allocates needed stuff on its own
 277 static void ifilter_expand(IFT dmask,IFT smask,IFT cmask,int ishift,int rshift)
 278 {
 279         size_t len = VEC_LENGTH(ifilters);
 280         VEC_ADDN(ifilters,cmask * len);
 281         size_t esz = cmask + 1; // size of expanded elements
 282         for (size_t i = len - 1;;--i) {
 283                 for (IFT j = 0;;++j) {
 284                         VEC_BUF(ifilters,i * esz + j).f = EXPVAL(VEC_BUF(ifilters,i).f,j,dmask,smask,ishift,rshift);
 285                         if (j == cmask)
 286                                 break;
 287                 }
 288                 if (i == 0)
 289                         break;
 290         }
 291 }
 292
 293 static inline void ifilter_addflatten(struct intfilter *ifltr,IFT mask)
 294 {
 295         if (VEC_LENGTH(ifilters) == 0) {
 296                 // simple
 297                 VEC_ADD(ifilters,*ifltr);
 298                 ifiltermask = mask;
 299                 return;
 300         }
 301         if (ifiltermask == mask) {
 302                 // lucky, only need to insert at the right place
 303                 size_t r1,r2;
 304                 ifilter_find(ifltr->f,0,VEC_LENGTH(ifilters),&r1,&r2);
 305                 if (r1 != r2) {
 306                         // duplicate
 307                         return;
 308                 }
 309                 VEC_INSERT(ifilters,r1,*ifltr);
 310                 return;
 311         }
 312         IFT cross = ifiltermask ^ mask;
 313         int ishift = 0;
 314         while ((cross & 1) == 0) {
 315                 ++ishift;
 316                 cross >>= 1;
 317         }
 318         IFT smask = cross & (cross + 1); // shift mask
 319         IFT dmask = cross ^ smask; // direct mask
 320         IFT cmask; // combined mask
 321         int rshift = 0; // relative shift
 322         while (cmask = (smask >> rshift) | dmask,(cmask & (cmask + 1)) != 0)
 323                 ++rshift;
 324         // preparations done
 325         if (ifiltermask > mask) {
 326                 // already existing stuff has more precise mask than we
 327                 // so we need to expand our stuff
 328                 ifilter_addexpanded(ifltr,dmask,smask,cmask,ishift,rshift);
 329         }
 330         else {
 331                 size_t r1,r2;
 332                 // check if not already exists
 333                 ifilter_find(ifltr->f & ifiltermask,0,VEC_LENGTH(ifilters),&r1,&r2);
 334                 if (r1 != r2) {
 335                         // this filter alreaedy exists in wider form
 336                         return;
 337                 }
 338                 // adjust existing mask
 339                 ifiltermask = mask;
 340                 // already existing stuff needs to be expanded
 341                 ifilter_expand(dmask,smask,cmask,ishift,rshift);
 342                 if (*(const u8 *)&littleendian) {
 343                         VEC_ADD(ifilters,*ifltr);
 344                         ifilter_sort();
 345                 }
 346                 else {
 347                         // we already know place to insert
 348                         // well except this time it gon b expanded a bit
 349                         VEC_INSERT(ifilters,r1 * (cmask + 1),*ifltr);
 350                 }
 351         }
 352 }
 353
 354 #if 0
 355 static int ifilter_check()
 356 {
 357         for (size_t i = 1;i < VEC_LENGTH(ifilters);++i) {
 358                 if (VEC_BUF(ifilters,i - 1).f == VEC_BUF(ifilters,i).f) {
 359                         return 1;
 360                 }
 361                 if (VEC_BUF(ifilters,i - 1).f > VEC_BUF(ifilters,i).f) {
 362                         return 2;
 363                 }
 364         }
 365         return 0;
 366 }
 367 #endif // 0
 368 #endif // BINSEARCH
 369 #endif // INTFILTER
 370
 371 static void filters_add(const char *filter)
 372 {
 373         struct binfilter bf;
 374         size_t ret, ret2;
 375 #ifdef INTFILTER
 376         union intconv {
 377                 IFT i;
 378                 u8 b[sizeof(IFT)];
 379         } fc,mc;
 380 #endif
 381
 382         // skip regex start symbol. we do not support regex tho
 383         if (*filter == '^')
 384                 ++filter;
 385
 386         memset(&bf,0,sizeof(bf));
 387
 388         if (!base32_valid(filter,&ret)) {
 389                 fprintf(stderr,"filter \"%s\" is invalid\n",filter);
 390                 return;
 391         }
 392         ret = BASE32_FROM_LEN(ret);
 393         if (!ret)
 394                 return;
 395 #ifdef INTFILTER
 396         if (ret > sizeof(IFT))
 397 #else
 398         if (ret > sizeof(bf.f))
 399 #endif
 400         {
 401                 fprintf(stderr,"filter \"%s\" is too long\n",filter);
 402                 return;
 403         }
 404         ret2 = base32_from(bf.f,&bf.mask,filter);
 405         assert(ret == ret2);
 406         bf.len = ret - 1;
 407 #ifdef INTFILTER
 408         mc.i = 0;
 409         for (size_t i = 0;i < bf.len;++i)
 410                 mc.b[i] = 0xFF;
 411         mc.b[bf.len] = bf.mask;
 412         memcpy(fc.b,bf.f,sizeof(fc.b));
 413         fc.i &= mc.i;
 414         struct intfilter ifltr = {
 415                 .f = fc.i,
 416 #ifndef BINSEARCH
 417                 .m = mc.i,
 418 #endif
 419         };
 420 #ifdef BINSEARCH
 421         ifilter_addflatten(&ifltr,mc.i);
 422 #if 0
 423         int ifiltererr = ifilter_check();
 424         if (ifiltererr != 0) {
 425                 if (ifiltererr == 1)
 426                         fprintf(stderr,"bug: duplicate filter found!\n");
 427                 else if (ifiltererr == 2)
 428                         fprintf(stderr,"bug: ifilters aint sorted!\n");
 429                 abort();
 430         }
 431 #endif // 0
 432 #else // BINSEARCH
 433         VEC_FOR(ifilters,i) {
 434                 int c;
 435                 c = ifilter_conflict(&VEC_BUF(ifilters,i),&ifltr);
 436                 if (c < 0)
 437                         return; // old filter eats us
 438                 else if (c > 0) {
 439                         VEC_REMOVE(ifilters,i);
 440                         --i;
 441                         // we eat old filter
 442                 }
 443         }
 444         VEC_FOR(ifilters,i) {
 445                 // filter with least bits first
 446                 if (VEC_BUF(ifilters,i).m > ifltr.m) {
 447                         VEC_INSERT(ifilters,i,ifltr);
 448                         return;
 449                 }
 450         }
 451         VEC_ADD(ifilters,ifltr);
 452 #endif // BINSEARCH
 453 #else // INTFILTER
 454         VEC_FOR(bfilters,i) {
 455                 int c = bfilter_conflict(&VEC_BUF(bfilters,i),&bf);
 456                 if (c < 0)
 457                         return; // old filter eats us
 458                 else if (c > 0) {
 459                         VEC_REMOVE(bfilters,i);
 460                         --i;
 461                         // we eat old filter
 462                 }
 463         }
 464 #ifdef BINSEARCH
 465         VEC_FOR(bfilters,i) {
 466                 /*
 467                  * mask is irrelevant, as they're not
 468                  * conflicting and have proper order
 469                  * (unlike when using little endian words)
 470                  */
 471                 if (memcmp(VEC_BUF(bfilters,i).f,bf.f,sizeof(bf.f)) > 0) {
 472                         VEC_INSERT(bfilters,i,bf);
 473                         return;
 474                 }
 475         }
 476         VEC_ADD(bfilters,bf);
 477 #else
 478         VEC_FOR(bfilters,i) {
 479                 // filter with least bits first
 480                 if (VEC_BUF(bfilters,i).len > bf.len ||
 481                         (VEC_BUF(bfilters,i).len == bf.len &&
 482                                 (VEC_BUF(bfilters,i).mask > bf.mask)))
 483                 {
 484                         VEC_INSERT(bfilters,i,bf);
 485                         return;
 486                 }
 487         }
 488         VEC_ADD(bfilters,bf);
 489 #endif // BINSEARCH
 490 #endif // INTFILTER
 491 }
 492
 493 static void filters_clean()
 494 {
 495 #ifdef INTFILTER
 496         VEC_FREE(ifilters);
 497 #else
 498         VEC_FREE(bfilters);
 499 #endif
 500 }
 501
 502 static size_t filters_count()
 503 {
 504 #ifdef INTFILTER
 505         return VEC_LENGTH(ifilters);
 506 #else
 507         return VEC_LENGTH(bfilters);
 508 #endif
 509 }
 510
 511 #ifdef INTFILTER
 512
 513 #ifndef BINSEARCH
 514
 515 #define MATCHFILTER(it,pk) \
 516         ((*(IFT *)(pk) & VEC_BUF(ifilters,it).m) == VEC_BUF(ifilters,it).f)
 517
 518 #define DOFILTER(it,pk,code) { \
 519         for (it = 0;it < VEC_LENGTH(ifilters);++it) { \
 520                 if (unlikely(MATCHFILTER(it,pk))) { \
 521                         code; \
 522                         break; \
 523                 } \
 524         } \
 525 }
 526
 527 #else // BINSEARCH
 528
 529 #define DOFILTER(it,pk,code) { \
 530         register IFT maskedpk = *(IFT *)(pk) & ifiltermask; \
 531         for (size_t down = 0,up = VEC_LENGTH(ifilters);down < up;) { \
 532                 it = (up + down) / 2; \
 533                 if (maskedpk < VEC_BUF(ifilters,it).f) \
 534                         up = it; \
 535                 else if (maskedpk > VEC_BUF(ifilters,it).f) \
 536                         down = it + 1; \
 537                 else { \
 538                         code; \
 539                         break; \
 540                 } \
 541         } \
 542 }
 543
 544 #endif // BINSEARCH
 545
 546 #else // INTFILTER
 547
 548 #ifndef BINSEARCH
 549
 550 #define MATCHFILTER(it,pk) ( \
 551         memcmp(pk,VEC_BUF(bfilters,it).f,VEC_BUF(bfilters,it).len) == 0 && \
 552         (pk[VEC_BUF(bfilters,it).len] & VEC_BUF(bfilters,it).mask) == VEC_BUF(bfilters,it).f[VEC_BUF(bfilters,it).len])
 553
 554 #define DOFILTER(it,pk,code) { \
 555         for (it = 0;it < VEC_LENGTH(bfilters);++it) { \
 556                 if (unlikely(MATCHFILTER(it,pk))) { \
 557                         code; \
 558                         break; \
 559                 } \
 560         } \
 561 }
 562
 563 #else // BINSEARCH
 564
 565 #define DOFILTER(it,pk,code) { \
 566         for (size_t down = 0,up = VEC_LENGTH(bfilters);down < up;) { \
 567                 it = (up + down) / 2; \
 568                 { \
 569                         register int filterdiff = memcmp(pk,VEC_BUF(bfilters,it).f,VEC_BUF(bfilters,it).len); \
 570                         if (filterdiff < 0) { \
 571                                 up = it; \
 572                                 continue; \
 573                         } \
 574                         if (filterdiff > 0) { \
 575                                 down = it + 1; \
 576                                 continue; \
 577                         } \
 578                 } \
 579                 if ((pk[VEC_BUF(bfilters,it).len] & VEC_BUF(bfilters,it).mask) < \
 580                         VEC_BUF(bfilters,it).f[VEC_BUF(bfilters,it).len]) \
 581                 { \
 582                         up = it; \
 583                         continue; \
 584                 } \
 585                 if ((pk[VEC_BUF(bfilters,it).len] & VEC_BUF(bfilters,it).mask) > \
 586                         VEC_BUF(bfilters,it).f[VEC_BUF(bfilters,it).len]) \
 587                 { \
 588                         down = it + 1; \
 589                         continue; \
 590                 } \
 591                 { \
 592                         code; \
 593                         break; \
 594                 } \
 595         } \
 596 }
 597
 598 #endif // BINSEARCH
 599
 600 #endif // INTFILTER
 601
 602 static void loadfilterfile(const char *fname)
 603 {
 604         char buf[128];
 605         FILE *f = fopen(fname,"r");
 606         while (fgets(buf,sizeof(buf),f)) {
 607                 for (char *p = buf;*p;++p) {
 608                         if (*p == '\n') {
 609                                 *p = 0;
 610                                 break;
 611                         }
 612                 }
 613                 if (*buf && *buf != '#' && memcmp(buf,"//",2) != 0)
 614                         filters_add(buf);
 615         }
 616 }
 617
 618 static void printfilters()
 619 {
 620         size_t i,l;
 621 #ifdef INTFILTER
 622         l = VEC_LENGTH(ifilters);
 623 #else
 624         l = VEC_LENGTH(bfilters);
 625 #endif
 626         if (l)
 627                 fprintf(stderr, "filters:\n");
 628         else
 629                 fprintf(stderr, "no filters defined\n");
 630
 631         for (i = 0;i < l;++i) {
 632                 char buf0[256],buf1[256];
 633                 u8 bufx[128];
 634 #ifdef INTFILTER
 635                 size_t len = 0;
 636                 u8 *imraw;
 637 #ifndef BINSEARCH
 638                 imraw = (u8 *)&VEC_BUF(ifilters,i).m;
 639 #else
 640                 imraw = (u8 *)&ifiltermask;
 641 #endif
 642                 while (len < sizeof(IFT) && imraw[len] != 0x00) ++len;
 643                 u8 mask = imraw[len-1];
 644                 u8 *ifraw = (u8 *)&VEC_BUF(ifilters,i).f;
 645 #else
 646                 size_t len = VEC_BUF(bfilters,i).len + 1;
 647                 u8 mask = VEC_BUF(bfilters,i).mask;
 648                 u8 *ifraw = VEC_BUF(bfilters,i).f;
 649 #endif
 650                 base32_to(buf0,ifraw,len);
 651                 memcpy(bufx,ifraw,len);
 652                 bufx[len - 1] |= ~mask;
 653                 base32_to(buf1,bufx,len);
 654                 char *a = buf0,*b = buf1;
 655                 while (*a && *a == *b)
 656                         ++a, ++b;
 657                 *a = 0;
 658                 fprintf(stderr, "\t%s\n",buf0);
 659         }
 660 }
 661
 662 // statistics, if enabled
 663 #ifdef STATISTICS
 664 struct statstruct {
 665         union {
 666                 u32 v;
 667                 size_t align;
 668         } numcalc;
 669         union {
 670                 u32 v;
 671                 size_t align;
 672         } numsuccess;
 673         union {
 674                 u32 v;
 675                 size_t align;
 676         } numrestart;
 677 } ;
 678 VEC_STRUCT(statsvec,struct statstruct);
 679
 680 struct tstatstruct {
 681         u64 numcalc;
 682         u64 numsuccess;
 683         u64 numrestart;
 684         u32 oldnumcalc;
 685         u32 oldnumsuccess;
 686         u32 oldnumrestart;
 687 } ;
 688 VEC_STRUCT(tstatsvec,struct tstatstruct);
 689 #endif
 690
 691
 692 static void onionready(char *sname, const u8 *secret, const u8 *pubonion)
 693 {
 694         FILE *fh;
 695
 696         if (endwork)
 697                 return;
 698
 699         if (numneedgenerate) {
 700                 pthread_mutex_lock(&keysgenerated_mutex);
 701                 if (keysgenerated >= numneedgenerate) {
 702                         pthread_mutex_unlock(&keysgenerated_mutex);
 703                         return;
 704                 }
 705         }
 706
 707         if (mkdir(sname,0700) != 0) {
 708                 if (numneedgenerate)
 709                         pthread_mutex_unlock(&keysgenerated_mutex);
 710                 return;
 711         }
 712
 713         if (numneedgenerate) {
 714                 ++keysgenerated;
 715                 if (keysgenerated >= numneedgenerate)
 716                         endwork = 1;
 717                 pthread_mutex_unlock(&keysgenerated_mutex);
 718         }
 719
 720         strcpy(&sname[onionendpos], "/hs_ed25519_secret_key");
 721         fh = fopen(sname, "wb");
 722         if (fh) {
 723                 fwrite(secret, skprefixlen + SECRET_LEN, 1, fh);
 724                 fclose(fh);
 725         }
 726
 727         strcpy(&sname[onionendpos], "/hostname");
 728         fh = fopen(sname, "w");
 729         if (fh) {
 730                 sname[onionendpos] = '\n';
 731                 fwrite(&sname[direndpos], ONIONLEN+1, 1, fh);
 732                 fclose(fh);
 733         }
 734
 735         strcpy(&sname[onionendpos], "/hs_ed25519_public_key");
 736         fh = fopen(sname, "wb");
 737         if (fh) {
 738                 fwrite(pubonion, pkprefixlen + PUBLIC_LEN, 1, fh);
 739                 fclose(fh);
 740         }
 741
 742         if (fout) {
 743                 sname[onionendpos] = '\n';
 744                 pthread_mutex_lock(&fout_mutex);
 745                 fwrite(&sname[printstartpos], printlen, 1, fout);
 746                 fflush(fout);
 747                 pthread_mutex_unlock(&fout_mutex);
 748         }
 749 }
 750
 751 // little endian inc
 752 static void addseed(u8 *seed)
 753 {
 754         register unsigned int c = 1;
 755         for (size_t i = 0;i < SEED_LEN;++i) {
 756                 c = (unsigned int)seed[i] + c; seed[i] = c & 0xFF; c >>= 8;
 757                 // unsure if needed
 758                 if (!c) break;
 759         }
 760 }
 761
 762 static void *dowork(void *task)
 763 {
 764         union pubonionunion {
 765                 u8 raw[pkprefixlen + PUBLIC_LEN + 32];
 766                 struct {
 767                         u64 prefix[4];
 768                         u64 key[4];
 769                         u64 hash[4];
 770                 } i;
 771         } pubonion;
 772         u8 * const pk = &pubonion.raw[pkprefixlen];
 773         u8 secret[skprefixlen + SECRET_LEN];
 774         u8 * const sk = &secret[skprefixlen];
 775         u8 seed[SEED_LEN];
 776         u8 hashsrc[checksumstrlen + PUBLIC_LEN + 1];
 777         size_t i;
 778         char *sname;
 779 #ifdef STATISTICS
 780         struct statstruct *st = (struct statstruct *)task;
 781 #endif
 782
 783         memcpy(secret,skprefix,skprefixlen);
 784         memcpy(pubonion.raw,pkprefix,pkprefixlen);
 785         // write version later as it will be overwritten by hash
 786         memcpy(hashsrc,checksumstr,checksumstrlen);
 787         hashsrc[checksumstrlen + PUBLIC_LEN] = 0x03; // version
 788
 789         sname = malloc(workdirlen + ONIONLEN + 63 + 1);
 790         if (!sname)
 791                 abort();
 792         if (workdir)
 793                 memcpy(sname,workdir,workdirlen);
 794
 795 initseed:
 796         randombytes(seed,sizeof(seed));
 797 #ifdef STATISTICS
 798         ++st->numrestart.v;
 799 #endif
 800
 801 again:
 802         if (unlikely(endwork))
 803                 goto end;
 804
 805         ed25519_seckey_expand(sk,seed);
 806         ed25519_pubkey(pk,sk);
 807
 808 #ifdef STATISTICS
 809         ++st->numcalc.v;
 810 #endif
 811
 812         DOFILTER(i,pk,{
 813 #ifdef STATISTICS
 814                 ++st->numsuccess.v;
 815 #endif
 816                 // calc checksum
 817                 memcpy(&hashsrc[checksumstrlen],pk,PUBLIC_LEN);
 818                 FIPS202_SHA3_256(hashsrc,sizeof(hashsrc),&pk[PUBLIC_LEN]);
 819                 // version byte
 820                 pk[PUBLIC_LEN + 2] = 0x03;
 821                 // base32
 822                 strcpy(base32_to(&sname[direndpos],pk,PUBONION_LEN), ".onion");
 823                 onionready(sname, secret, pubonion.raw);
 824                 goto initseed;
 825         });
 826         addseed(seed);
 827         goto again;
 828
 829 end:
 830         free(sname);
 831         return 0;
 832 }
 833
 834 static void addu64toscalar32(u8 *dst,u64 v)
 835 {
 836         int i;
 837         u32 c = 0;
 838         for (i = 0;i < 32;++i) {
 839                 c += *dst + (v & 0xFF); *dst = c & 0xFF; c >>= 8;
 840                 v >>= 8;
 841                 ++dst;
 842         }
 843 }
 844
 845 static void *dofastwork(void *task)
 846 {
 847         union pubonionunion {
 848                 u8 raw[pkprefixlen + PUBLIC_LEN + 32];
 849                 struct {
 850                         u64 prefix[4];
 851                         u64 key[4];
 852                         u64 hash[4];
 853                 } i;
 854         } pubonion;
 855         u8 * const pk = &pubonion.raw[pkprefixlen];
 856         u8 secret[skprefixlen + SECRET_LEN];
 857         u8 * const sk = &secret[skprefixlen];
 858         u8 seed[SEED_LEN];
 859         u8 hashsrc[checksumstrlen + PUBLIC_LEN + 1];
 860         ge_p3 ge_public;
 861         size_t counter;
 862         size_t i;
 863         char *sname;
 864 #ifdef STATISTICS
 865         struct statstruct *st = (struct statstruct *)task;
 866 #endif
 867
 868         memcpy(secret, skprefix, skprefixlen);
 869         memcpy(pubonion.raw, pkprefix, pkprefixlen);
 870         // write version later as it will be overwritten by hash
 871         memcpy(hashsrc, checksumstr, checksumstrlen);
 872         hashsrc[checksumstrlen + PUBLIC_LEN] = 0x03; // version
 873
 874         sname = malloc(workdirlen + ONIONLEN + 63 + 1);
 875         if (!sname)
 876                 abort();
 877         if (workdir)
 878                 memcpy(sname, workdir, workdirlen);
 879
 880 initseed:
 881 #ifdef STATISTICS
 882         ++st->numrestart.v;
 883 #endif
 884         randombytes(seed,sizeof(seed));
 885         ed25519_seckey_expand(sk,seed);
 886
 887         ge_scalarmult_base(&ge_public,sk);
 888         ge_p3_tobytes(pk,&ge_public);
 889
 890         for (counter = 0;counter < SIZE_MAX-8;counter += 8) {
 891                 ge_p1p1 sum;
 892
 893                 if (unlikely(endwork))
 894                         goto end;
 895
 896                 DOFILTER(i,pk,{
 897                         // found!
 898                         // update secret key with counter
 899                         addu64toscalar32(sk,counter);
 900                         // sanity check
 901                         if (((sk[0] & 248) == sk[0]) && (((sk[31] & 63) | 64) == sk[31])) {
 902                                 /* These operations should be a no-op. */
 903                                 sk[0] &= 248;
 904                                 sk[31] &= 63;
 905                                 sk[31] |= 64;
 906                         }
 907                         else goto initseed;
 908 #ifdef STATISTICS
 909                         ++st->numsuccess.v;
 910 #endif
 911                         // calc checksum
 912                         memcpy(&hashsrc[checksumstrlen],pk,PUBLIC_LEN);
 913                         FIPS202_SHA3_256(hashsrc,sizeof(hashsrc),&pk[PUBLIC_LEN]);
 914                         // version byte
 915                         pk[PUBLIC_LEN + 2] = 0x03;
 916                         // full name
 917                         strcpy(base32_to(&sname[direndpos],pk,PUBONION_LEN),".onion");
 918                         onionready(sname,secret,pubonion.raw);
 919                         // don't reuse same seed
 920                         goto initseed;
 921                 });
 922
 923                 // next
 924                 ge_add(&sum, &ge_public,&ge_eightpoint);
 925                 ge_p1p1_to_p3(&ge_public,&sum);
 926                 ge_p3_tobytes(pk,&ge_public);
 927 #ifdef STATISTICS
 928                 ++st->numcalc.v;
 929 #endif
 930         }
 931         goto initseed;
 932
 933 end:
 934         free(sname);
 935         return 0;
 936 }
 937
 938 void printhelp(const char *progname)
 939 {
 940         fprintf(stderr,
 941                 "Usage: %s filter [filter...] [options]\n"
 942                 "       %s -f filterfile [options]\n"
 943                 "Options:\n"
 944                 "\t-h  - print help\n"
 945                 "\t-f  - instead of specifying filter(s) via commandline, specify filter file which contains filters separated by newlines\n"
 946                 "\t-q  - do not print diagnostic output to stderr\n"
 947                 "\t-x  - do not print onion names\n"
 948                 "\t-o filename  - output onion names to specified file\n"
 949                 "\t-F  - include directory names in onion names output\n"
 950                 "\t-d dirname  - output directory\n"
 951                 "\t-t numthreads  - specify number of threads (default - auto)\n"
 952                 "\t-j numthreads  - same as -t\n"
 953                 "\t-n numkeys  - specify number of keys (default - 0 - unlimited)\n"
 954                 "\t-z  - use faster key generation method. this is now default\n"
 955                 "\t-Z  - use slower key generation method\n"
 956                 "\t-s  - print statistics each 10 seconds\n"
 957                 "\t-S t  - print statistics every specified ammount of seconds\n"
 958                 "\t-T  - do not reset statistics counters when printing\n"
 959                 ,progname,progname);
 960         exit(1);
 961 }
 962
 963 void setworkdir(const char *wd)
 964 {
 965         free(workdir);
 966         size_t l = strlen(wd);
 967         if (!l) {
 968                 workdir = 0;
 969                 workdirlen = 0;
 970                 if (!quietflag)
 971                         fprintf(stderr, "unset workdir\n");
 972                 return;
 973         }
 974         int needslash = 0;
 975         if (wd[l-1] != '/')
 976                 needslash = 1;
 977         char *s = malloc(l + needslash + 1);
 978         if (!s)
 979                 abort();
 980         memcpy(s, wd, l);
 981         if (needslash)
 982                 s[l++] = '/';
 983         s[l] = 0;
 984
 985         workdir = s;
 986         workdirlen = l;
 987         if (!quietflag)
 988                 fprintf(stderr,"set workdir: %s\n",workdir);
 989 }
 990
 991 VEC_STRUCT(threadvec, pthread_t);
 992
 993 int main(int argc,char **argv)
 994 {
 995         char *outfile = 0;
 996         const char *arg;
 997         int ignoreargs = 0;
 998         int dirnameflag = 0;
 999         int numthreads = 0;
1000         int fastkeygen = 1;
1001         struct threadvec threads;
1002 #ifdef STATISTICS
1003         struct statsvec stats;
1004         struct tstatsvec tstats;
1005         u64 reportdelay = 0;
1006         int realtimestats = 1;
1007 #endif
1008         int tret;
1009
1010         ge_initeightpoint();
1011         filters_init();
1012
1013         fout = stdout;
1014         pthread_mutex_init(&keysgenerated_mutex, 0);
1015         pthread_mutex_init(&fout_mutex, 0);
1016
1017         const char *progname = argv[0];
1018         if (argc <= 1)
1019                 printhelp(progname);
1020         argc--, argv++;
1021
1022         while (argc--) {
1023                 arg = *argv++;
1024                 if (!ignoreargs && *arg == '-') {
1025                         int numargit = 0;
1026                 nextarg:
1027                         ++arg;
1028                         ++numargit;
1029                         if (*arg == '-') {
1030                                 if (numargit > 1) {
1031                                         fprintf(stderr, "unrecognised argument: -\n");
1032                                         exit(1);
1033                                 }
1034                                 ++arg;
1035                                 if (!*arg)
1036                                         ignoreargs = 1;
1037                                 else if (!strcmp(arg, "help"))
1038                                         printhelp(progname);
1039                                 else {
1040                                         fprintf(stderr, "unrecognised argument: --%s\n", arg);
1041                                         exit(1);
1042                                 }
1043                                 numargit = 0;
1044                         }
1045                         else if (*arg == 0) {
1046                                 if (numargit == 1)
1047                                         ignoreargs = 1;
1048                                 continue;
1049                         }
1050                         else if (*arg == 'h')
1051                                 printhelp(progname);
1052                         else if (*arg == 'f') {
1053                                 if (argc--)
1054                                         loadfilterfile(*argv++);
1055                                 else {
1056                                         fprintf(stderr, "additional argument required\n");
1057                                         exit(1);
1058                                 }
1059                         }
1060                         else if (*arg == 'q')
1061                                 ++quietflag;
1062                         else if (*arg == 'x')
1063                                 fout = 0;
1064                         else if (*arg == 'o') {
1065                                 if (argc--)
1066                                         outfile = *argv++;
1067                                 else {
1068                                         fprintf(stderr, "additional argument required\n");
1069                                         exit(1);
1070                                 }
1071                         }
1072                         else if (*arg == 'F')
1073                                 dirnameflag = 1;
1074                         else if (*arg == 'd') {
1075                                 if (argc--) {
1076                                         setworkdir(*argv++);
1077                                 }
1078                                 else {
1079                                         fprintf(stderr, "additional argument required\n");
1080                                 }
1081                         }
1082                         else if (*arg == 't' || *arg == 'j') {
1083                                 if (argc--)
1084                                         numthreads = atoi(*argv++);
1085                                 else {
1086                                         fprintf(stderr, "additional argument required\n");
1087                                         exit(1);
1088                                 }
1089                         }
1090                         else if (*arg == 'n') {
1091                                 if (argc--)
1092                                         numneedgenerate = (size_t)atoll(*argv++);
1093                                 else {
1094                                         fprintf(stderr, "additional argument required\n");
1095                                         exit(1);
1096                                 }
1097                         }
1098                         else if (*arg == 'Z')
1099                                 fastkeygen = 0;
1100                         else if (*arg == 'z')
1101                                 fastkeygen = 1;
1102                         else if (*arg == 's') {
1103 #ifdef STATISTICS
1104                                 reportdelay = 10000000;
1105 #else
1106                                 fprintf(stderr,"statistics support not compiled in\n");
1107                                 exit(1);
1108 #endif
1109                         }
1110                         else if (*arg == 'S') {
1111 #ifdef STATISTICS
1112                                 if (argc--)
1113                                         reportdelay = (u64)atoll(*argv++) * 1000000;
1114                                 else {
1115                                         fprintf(stderr, "additional argument required\n");
1116                                         exit(1);
1117                                 }
1118 #else
1119                                 fprintf(stderr,"statistics support not compiled in\n");
1120                                 exit(1);
1121 #endif
1122                         }
1123                         else if (*arg == 'T') {
1124 #ifdef STATISTICS
1125                                 realtimestats = 0;
1126 #else
1127                                 fprintf(stderr,"statistics support not compiled in\n");
1128                                 exit(1);
1129 #endif
1130                         }
1131                         else {
1132                                 fprintf(stderr, "unrecognised argument: -%c\n", *arg);
1133                                 exit(1);
1134                         }
1135                         if (numargit)
1136                                 goto nextarg;
1137                 }
1138                 else filters_add(arg);
1139         }
1140
1141         if (!quietflag)
1142                 printfilters();
1143
1144 #ifdef STATISTICS
1145         if (!filters_count() && !reportdelay)
1146 #else
1147         if (!filters_count())
1148 #endif
1149                 return 0;
1150
1151         if (outfile)
1152                 fout = fopen(outfile, "w");
1153
1154         if (workdir)
1155                 mkdir(workdir, 0700);
1156
1157         direndpos = workdirlen;
1158         onionendpos = workdirlen + ONIONLEN;
1159
1160         if (!dirnameflag) {
1161                 printstartpos = direndpos;
1162                 printlen = ONIONLEN + 1;
1163         } else {
1164                 printstartpos = 0;
1165                 printlen = onionendpos + 1;
1166         }
1167
1168         if (numthreads <= 0) {
1169                 numthreads = cpucount();
1170                 if (numthreads <= 0)
1171                         numthreads = 1;
1172         }
1173
1174         signal(SIGTERM,termhandler);
1175         signal(SIGINT,termhandler);
1176
1177         VEC_INIT(threads);
1178         VEC_ADDN(threads,numthreads);
1179 #ifdef STATISTICS
1180         VEC_INIT(stats);
1181         VEC_ADDN(stats,numthreads);
1182         VEC_ZERO(stats);
1183         VEC_INIT(tstats);
1184         VEC_ADDN(tstats,numthreads);
1185         VEC_ZERO(tstats);
1186 #endif
1187
1188         for (size_t i = 0;i < VEC_LENGTH(threads);++i) {
1189                 void *tp = 0;
1190 #ifdef STATISTICS
1191                 tp = &VEC_BUF(stats,i);
1192 #endif
1193                 tret = pthread_create(&VEC_BUF(threads,i),0,fastkeygen ? dofastwork : dowork,tp);
1194                 if (tret) {
1195                         fprintf(stderr,"error while making %dth thread: %d\n",(int)i,tret);
1196                         exit(1);
1197                 }
1198         }
1199
1200 #ifdef STATISTICS
1201         struct timespec nowtime;
1202         u64 istarttime,inowtime,ireporttime = 0,elapsedoffset = 0;
1203         if (clock_gettime(CLOCK_MONOTONIC,&nowtime) < 0) {
1204                 fprintf(stderr, "failed to get time\n");
1205                 exit(1);
1206         }
1207         istarttime = (1000000 * (u64)nowtime.tv_sec) + (nowtime.tv_nsec / 1000);
1208 #endif
1209         struct timespec ts;
1210         memset(&ts,0,sizeof(ts));
1211         ts.tv_nsec = 100000000;
1212         while (!endwork) {
1213                 if (numneedgenerate && keysgenerated >= numneedgenerate) {
1214                         endwork = 1;
1215                         break;
1216                 }
1217                 nanosleep(&ts,0);
1218
1219 #ifdef STATISTICS
1220                 clock_gettime(CLOCK_MONOTONIC,&nowtime);
1221                 inowtime = (1000000 * (u64)nowtime.tv_sec) + (nowtime.tv_nsec / 1000);
1222                 u64 sumcalc = 0,sumsuccess = 0,sumrestart = 0;
1223                 for (size_t i = 0;i < numthreads;++i) {
1224                         u32 newt,tdiff;
1225                         // numcalc
1226                         newt = VEC_BUF(stats,i).numcalc.v;
1227                         tdiff = newt - VEC_BUF(tstats,i).oldnumcalc;
1228                         VEC_BUF(tstats,i).oldnumcalc = newt;
1229                         VEC_BUF(tstats,i).numcalc += (u64)tdiff;
1230                         sumcalc += VEC_BUF(tstats,i).numcalc;
1231                         // numsuccess
1232                         newt = VEC_BUF(stats,i).numsuccess.v;
1233                         tdiff = newt - VEC_BUF(tstats,i).oldnumsuccess;
1234                         VEC_BUF(tstats,i).oldnumsuccess = newt;
1235                         VEC_BUF(tstats,i).numsuccess += (u64)tdiff;
1236                         sumsuccess += VEC_BUF(tstats,i).numsuccess;
1237                         // numrestart
1238                         newt = VEC_BUF(stats,i).numrestart.v;
1239                         tdiff = newt - VEC_BUF(tstats,i).oldnumrestart;
1240                         VEC_BUF(tstats,i).oldnumrestart = newt;
1241                         VEC_BUF(tstats,i).numrestart += (u64)tdiff;
1242                         sumrestart += VEC_BUF(tstats,i).numrestart;
1243                 }
1244                 if (reportdelay && (!ireporttime || inowtime - ireporttime >= reportdelay)) {
1245                         if (ireporttime)
1246                                 ireporttime += reportdelay;
1247                         else
1248                                 ireporttime = inowtime;
1249                         if (!ireporttime)
1250                                 ireporttime = 1;
1251
1252                         double calcpersec = (1000000.0 * sumcalc) / (inowtime - istarttime);
1253                         double succpersec = (1000000.0 * sumsuccess) / (inowtime - istarttime);
1254                         double restpersec = (1000000.0 * sumrestart) / (inowtime - istarttime);
1255                         fprintf(stderr,">calc/sec:%8lf, succ/sec:%8lf, rest/sec:%8lf, elapsed:%5.6lfsec\n",
1256                                 calcpersec,succpersec,restpersec,
1257                                 (inowtime - istarttime + elapsedoffset) / 1000000.0);
1258
1259                         if (realtimestats) {
1260                                 for (size_t i = 0;i < numthreads;++i) {
1261                                         VEC_BUF(tstats,i).numcalc = 0;
1262                                         VEC_BUF(tstats,i).numsuccess = 0;
1263                                         VEC_BUF(tstats,i).numrestart = 0;
1264                                 }
1265                                 elapsedoffset += inowtime - istarttime;
1266                                 istarttime = inowtime;
1267                         }
1268                 }
1269                 if (sumcalc > U64_MAX / 2) {
1270                         for (size_t i = 0;i < numthreads;++i) {
1271                                 VEC_BUF(tstats,i).numcalc /= 2;
1272                                 VEC_BUF(tstats,i).numsuccess /= 2;
1273                                 VEC_BUF(tstats,i).numrestart /= 2;
1274                         }
1275                         u64 timediff = (inowtime - istarttime + 1) / 2;
1276                         elapsedoffset += timediff;
1277                         istarttime += timediff;
1278                 }
1279 #endif
1280         }
1281
1282         if (!quietflag)
1283                 fprintf(stderr, "waiting for threads to finish...\n");
1284         for (size_t i = 0;i < VEC_LENGTH(threads);++i)
1285                 pthread_join(VEC_BUF(threads,i),0);
1286         if (!quietflag)
1287                 fprintf(stderr, "done, quitting\n");
1288
1289         pthread_mutex_destroy(&keysgenerated_mutex);
1290         pthread_mutex_destroy(&fout_mutex);
1291         filters_clean();
1292
1293         if (outfile)
1294                 fclose(fout);
1295
1296         return 0;
1297 }