gpgstats-0.0.2/dotrees.c

   1 /*
   2         gpgstats.c - Program to produce stats on a GPG keyring.
   3         Written by Jonathan McDowell <noodles@earth.li>.
   4
   5         19/02/2000 - Started writing (sort of).
   6 */
   7
   8 #include <ctype.h>
   9 #include <stdio.h>
  10 #include <stdlib.h>
  11 #include <string.h>
  12
  13 #include "gpgstats.h"
  14 #include "hash.h"
  15 #include "logging.h"
  16 #include "ll.h"
  17 #include "parse.h"
  18
  19 struct ll *finished = NULL;
  20 struct ll *trees = NULL;
  21
  22 unsigned long hex2long(char *string)
  23 {
  24         size_t loop;
  25         unsigned long value;
  26
  27         value = 0;
  28         for (loop = 0; loop < 8 && loop < strlen(string) && string[loop] > ' ';
  29                         loop++) {
  30                 value=((string[loop]>'9') ? toupper(string[loop])-'A'+10 :
  31                                         string[loop]-'0')+(value << 4);
  32         }
  33         return value;
  34 }
  35
  36
  37 int keycmp(struct key *key1, struct key *key2)
  38 {
  39         if (key1->keyid==key2->keyid) {
  40                 return 0;
  41         }
  42         return 1;
  43 }
  44
  45
  46 struct ll *addkey(struct ll *curkey, struct key newkey)
  47 {
  48         return lladd(curkey, copyandaddtohash(newkey));
  49 }
  50
  51
  52 void initcolour(int pi) {
  53         unsigned long loop;
  54         struct ll *curkey;
  55
  56         /* Init the colour/pi hashes */
  57         for (loop=0; loop<HASHSIZE; loop++) {
  58                 curkey = gethashtableentry(loop);
  59                 while (curkey!=NULL) {
  60                         ((struct key *)curkey->object)->colour = 0;
  61                         if (pi != NULL) {
  62                                 ((struct key *)curkey->object)->pi = NULL;
  63                         }
  64                         curkey = curkey->next;
  65                 }
  66         }
  67 }
  68
  69
  70 void readkeys(const char *filename)
  71 {
  72         char curline[1024];
  73         unsigned long keys=0,sigs=0,pub=0, revoked=0;
  74         struct key keyin;
  75         struct key *curkey=NULL, *cursign=NULL;
  76         struct key cursig;
  77         FILE *keyfile;
  78         int (*p)();
  79
  80         p=keycmp;
  81         keyin.name=cursig.name=NULL;
  82         keyin.sigs=keyin.signs=cursig.sigs=cursig.signs=NULL;
  83         keyin.selfsigned=cursig.selfsigned=0;
  84         keyin.revoked=cursig.revoked=0;
  85
  86         log(LOG_INFO, "Reading key info from '%s'.\n", filename);
  87         if ((keyfile=fopen(filename, "r"))==NULL) {
  88                 perror("readkeys()");
  89                 return;
  90         }
  91         /* read a line */
  92         fgets(curline, 1023, keyfile);
  93         while (!feof(keyfile)) {
  94                 if (curline[0]=='P') {
  95                         ++pub;
  96                         ++keys;
  97                         printf("\rRead %ld keys so far.", keys);
  98                         keyin.keyid=hex2long(&curline[1]);
  99                         curkey=copyandaddtohash(keyin);
 100                         if (curkey->keyid!=keyin.keyid) {
 101                                 printf("Erk! Didn't get back the key we asked for! %08lX != %08lX\n", curkey->keyid, keyin.keyid);
 102                         }
 103                 } else if (curline[0]=='S') {
 104                         cursig.keyid=hex2long(&curline[1]);
 105                         if (curkey->keyid==cursig.keyid) {
 106                                 curkey->selfsigned=1;
 107                         }
 108
 109                         if (!llfind(curkey->sigs, &cursig, p)) {
 110                                 curkey->sigs=addkey(curkey->sigs, cursig);
 111                                 ++sigs;
 112                         }
 113
 114                         if ((cursign=findinhash(&cursig))==NULL) {
 115                                 cursign=copyandaddtohash(cursig);
 116                         }
 117                         if (cursign->keyid!=cursig.keyid) {
 118                                 printf("Erk! Didn't get back the key we asked for! %08lX != %08lX\n", cursign->keyid, cursig.keyid);
 119                         }
 120
 121                         if (!llfind(cursign->signs, curkey, p))
 122                                 cursign->signs=addkey(cursign->signs, *curkey);
 123                 } else if (curline[0]=='N') {
 124                         if (curkey->name==NULL) {
 125                                 curkey->name=strdup(&curline[1]);
 126                                 curkey->name[strlen(curkey->name)-1]=0;
 127                                 if (strcmp(curkey->name, "[revoked]")==0) {
 128                                         curkey->revoked=1;
 129                                         ++revoked;
 130                                 }
 131                         }
 132                 }
 133                 fgets(curline, 1023, keyfile);
 134         }
 135         fclose(keyfile);
 136         printf("\rRead %lu keys, %lu pub, %lu sigs, %lu revoked.\n",
 137                 keys, pub, sigs, revoked);
 138 }
 139
 140
 141 void DFSVisit(int type, struct key *key, unsigned long *time, unsigned long *depth)
 142 {
 143         struct ll *curkey;
 144         struct key *v;
 145
 146         key->colour=1;
 147 //      key->d=(*time)++;
 148
 149         if (type==0) curkey=key->signs; else curkey=key->sigs;
 150         while (curkey!=NULL) {
 151                 v=(struct key *)findinhash(curkey->object);
 152                 if (v==NULL) {
 153                         printf("Couldn't find key in hash. Most odd.\n");
 154                 }
 155                 if (v!=NULL && v->colour==0) {
 156                         if (type==1 && key->pi==NULL) {
 157                                 printf("key->pi is NULL.\n");
 158                         } else if (type==1) {
 159                                 key->pi->object=lladd(key->pi->object, v);
 160                                 v->pi=key->pi;
 161                         }
 162
 163                         (*depth)++;
 164                         DFSVisit(type, v, time, depth);
 165                 }
 166                 curkey=curkey->next;
 167         }
 168         key->colour=2;
 169 //      key->f=(*time)++;
 170         if (type==0) finished=lladd(finished, key);
 171 }
 172
 173
 174 void DFS(void)
 175 {
 176         unsigned long loop,time=0,depth,maxdepth=0;
 177         struct ll *curkey;
 178
 179         initcolour(1);
 180         for (loop=0; loop<HASHSIZE; loop++) {
 181                 curkey=gethashtableentry(loop);
 182                 while (curkey!=NULL) {
 183                         if (((struct key *)curkey->object)->colour==0) {
 184                                 depth=0;
 185                                 DFSVisit(0, ((struct key *)curkey->object),
 186                                         &time, &depth);
 187                                 if (depth>maxdepth) maxdepth=depth;
 188                         }
 189                         curkey=curkey->next;
 190                 }
 191         }
 192         printf("Max depth reached in DFS(): %ld\n", maxdepth);
 193 }
 194
 195
 196 void DFSsorted(void)
 197 {
 198         unsigned long time=0,depth,maxdepth=0;
 199         struct ll *curkey;
 200
 201         initcolour(1);
 202         curkey=finished;
 203         while (curkey!=NULL) {
 204                 if (((struct key *)curkey->object)->colour==0) {
 205                         trees=lladd(trees, curkey->object);
 206                         ((struct key *)curkey->object)->pi=trees;
 207                         ((struct key *)curkey->object)->pi->object=lladd(NULL, curkey->object);
 208
 209                         depth=0;
 210                         DFSVisit(1, ((struct key *)curkey->object),
 211                                 &time, &depth);
 212                         if (depth>maxdepth) maxdepth=depth;
 213                 }
 214                 curkey=curkey->next;
 215         }
 216         printf("Max depth reached in DFSsorted(): %ld\n", maxdepth);
 217 }
 218
 219
 220 long checkselfsig()
 221 {
 222         unsigned long loop;
 223         struct ll *curkey;
 224         unsigned long selfsig=0;
 225
 226         for (loop=0; loop<HASHSIZE; loop++) {
 227                 curkey=gethashtableentry(loop);
 228                 while (curkey!=NULL) {
 229                         if (((struct key *)curkey->object)->selfsigned) ++selfsig;
 230                         curkey=curkey->next;
 231                 }
 232         }
 233
 234         return selfsig;
 235 }
 236
 237
 238 void printtrees(int minsize)
 239 {
 240         struct ll *curtree,*curkey;
 241         unsigned long count, total;
 242
 243         curtree=trees;
 244         total=0;
 245         while (curtree!=NULL) {
 246                 curkey=curtree->object;
 247                 ++total;
 248                 count=0;
 249                 if (llsize(curkey)>=minsize) while (curkey!=NULL) {
 250                         printf("0x%08lX (%s)\n", ((struct key *)curkey->object)->keyid,
 251                                 ((struct key *)curkey->object)->name);
 252                         count++;
 253                         curkey=curkey->next;
 254                 }
 255                 if (count>=minsize) printf("Tree size of %ld\n", count);
 256                 curtree=curtree->next;
 257         }
 258         printf("Total of %ld trees.\n", total);
 259 }
 260
 261
 262 unsigned long size2degree(struct ll *curll, struct key *prev, int sigs, int curdegree, int maxdegree, int *rec)
 263 {
 264         unsigned long count=0;
 265         struct ll *nextll;
 266
 267         ++curdegree;
 268         ++(*rec);
 269
 270         nextll=NULL;
 271         while (curll!=NULL) {
 272                 if (((struct key *) curll->object)->revoked==1) {
 273                         /* It's revoked. Ignore it. */
 274                 } else if (((struct key *) curll->object)->colour==0) {
 275                         /* We've never seen it. Count it, mark it and
 276                                 explore its subtree */
 277                         count++;
 278                         printf("0x%08lX (%s)\n", ((struct key *) curll->object)->keyid,
 279                                 ((struct key *) curll->object)->name);
 280                         ((struct key *)curll->object)->colour=curdegree;
 281                         ((struct key *)curll->object)->pi=(struct ll *) prev;
 282                         nextll=lladd(nextll, curll->object);
 283                 } else if (((struct key *) curll->object)->colour>curdegree) {
 284                         /* We've seen it, but it it's closer to us than we
 285                                 thought. Re-evaluate, but don't count it
 286                                 again */
 287                         ((struct key *)curll->object)->colour=curdegree;
 288                         ((struct key *)curll->object)->pi=(struct ll *) prev;
 289                         nextll=lladd(nextll, curll->object);
 290                 }
 291                 curll=curll->next;
 292         }
 293         /* Now we've marked, let's recurse */
 294         if (curdegree<maxdegree) curll=nextll; else curll=NULL;
 295         while (curll!=NULL) {
 296                 if (sigs) {
 297                         count += size2degree(((struct key *)curll->object)->sigs, curll->object, sigs, curdegree, maxdegree, rec);
 298                 } else {
 299                         count += size2degree(((struct key *)curll->object)->signs, curll->object, sigs, curdegree, maxdegree, rec);
 300                 }
 301                 nextll=curll->next;
 302                 free(curll);
 303                 curll=nextll;
 304         }
 305
 306         return count;
 307 }
 308
 309
 310 void sixdegrees(unsigned long keyid)
 311 {
 312         struct key *keyinfo, key;
 313         int loop;
 314         int rec;
 315
 316         key.keyid=keyid;
 317
 318         if ((keyinfo=findinhash(&key))==NULL) {
 319                 printf("Couldn't find key 0x%08lX.\n", keyid);
 320                 return;
 321         }
 322
 323         printf("Six degrees for 0x%08lX (%s):\n", keyinfo->keyid, keyinfo->name);
 324
 325         puts("\t\t   Signs       Signed by");
 326         for (loop=1; loop<7; loop++) {
 327                 initcolour(0);
 328                 rec=0;
 329                 printf("Degree %d:\t%8ld", loop, size2degree(keyinfo->signs, NULL, 0, 0, loop, &rec));
 330                 printf(" (%d)", rec);
 331                 initcolour(0);
 332                 rec=0;
 333                 printf("\t%8ld", size2degree(keyinfo->sigs, NULL, 1, 0, loop, &rec));
 334                 printf(" (%d)\n", rec);
 335         }
 336 }
 337
 338
 339 void showkeysigs(unsigned long keyid, int sigs)
 340 {
 341         struct key *keyinfo, key;
 342         struct ll *cursig;
 343
 344         key.keyid=keyid;
 345
 346         if ((keyinfo=findinhash(&key))==NULL) {
 347                 printf("Couldn't find key 0x%08lX.\n", keyid);
 348                 return;
 349         }
 350
 351         printf("0x%08lX (%s) %s:\n", keyinfo->keyid, keyinfo->name,
 352                         sigs ? "is signed by" : "signs");
 353
 354         if (sigs) cursig=keyinfo->sigs; else cursig=keyinfo->signs;
 355         while (cursig!=NULL) {
 356                 printf("\t0x%08lX (%s)\n", ((struct key *)cursig->object)->keyid,
 357                                 ((struct key *)cursig->object)->name);
 358                 cursig=cursig->next;
 359         }
 360 }
 361
 362
 363 void findpath(unsigned long keyida, unsigned long keyidb)
 364 {
 365         struct key *keyinfoa, *keyinfob, *curkey, keya, keyb;
 366         int rec;
 367
 368         keya.keyid=keyida;
 369         keyb.keyid=keyidb;
 370
 371         if ((keyinfoa=findinhash(&keya))==NULL) {
 372                 printf("Couldn't find key 0x%08lX.\n", keyida);
 373                 return;
 374         }
 375         if ((keyinfob=findinhash(&keyb))==NULL) {
 376                 printf("Couldn't find key 0x%08lX.\n", keyidb);
 377                 return;
 378         }
 379
 380         /* Fill the tree info up */
 381         initcolour(1);
 382         rec=0;
 383         size2degree(keyinfoa->signs, keyinfoa, 0, 0, 1000, &rec);
 384         keyinfoa->pi=NULL;
 385
 386         printf("%d recursions required.\n", rec);
 387         if (keyinfob->colour==0) {
 388                 printf("Can't find a link from 0x%08lX to 0x%08lX\n", keyida, keyidb);
 389         } else {
 390                 printf("%d steps from 0x%08lX to 0x%08lX\n", keyinfob->colour, keyida, keyidb);
 391                 curkey=keyinfob;
 392                 while (curkey!=NULL) {
 393                         printf("0x%08lX (%s)\n", curkey->keyid, curkey->name);
 394                         curkey=(struct key *)curkey->pi;
 395                 }
 396         }
 397 }
 398
 399
 400 int main(int argc, char *argv[])
 401 {
 402         struct key *keyinfo,foo;
 403         int rec;
 404
 405         printf("gpgstats %s by Jonathan McDowell\n", VERSION);
 406         puts("Copyright 2000 Project Purple. Released under the GPL.");
 407         puts("A simple program to do stats on a GPG keyring.\n");
 408         inithash();
 409 //      readkeys("keyfile");
 410         readkeys("keyfile.debian");
 411 //      readkeys("../keyfile.big");
 412         printf("%ld selfsigned.\n", checkselfsig());
 413         printf("%ld distinct keys.\n", hashelements());
 414
 415         finished=trees=NULL;
 416         printf("Starting first DFS.\n");
 417         DFS();
 418         printf("Starting second DFS.\n");
 419         DFSsorted();
 420         printtrees(2);
 421
 422 //      foo.keyid=0xC7A966DD; /* Phil Zimmerman himself */
 423 //      if ((keyinfo=findinhash(&foo))==NULL) {
 424 //              printf("Couldn't find key 0x%08lX.\n", foo.keyid);
 425 //              return 1;
 426 //      }
 427
 428 //      initcolour(0);
 429 //      rec=0;
 430 //      printf("%ld\n", size2degree(keyinfo->sigs, NULL, 0, 0, 1000, &rec));
 431 //      return 0;
 432 }