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 int main(int argc, char *argv[])
 263 {
 264         struct key *keyinfo,foo;
 265         int rec;
 266
 267         printf("gpgstats %s by Jonathan McDowell\n", VERSION);
 268         puts("Copyright 2000 Project Purple. Released under the GPL.");
 269         puts("A simple program to do stats on a GPG keyring.\n");
 270         inithash();
 271         readkeys("keyfile.debian");
 272         printf("%ld selfsigned.\n", checkselfsig());
 273         printf("%ld distinct keys.\n", hashelements());
 274
 275         finished=trees=NULL;
 276         printf("Starting first DFS.\n");
 277         DFS();
 278         printf("Starting second DFS.\n");
 279         DFSsorted();
 280         printtrees(2);
 281 }