geht jetzt

3 files changed, 298 insertions, 135 deletions

diff --git a/gpggraph.lpr b/gpggraph.lpr
index 25e622e..de76395 100644
--- a/gpggraph.lpr
+++ b/gpggraph.lpr
@@ -3,36 +3,80 @@ program gpggraph;
 {$R *.res}
 
 uses
-  mystringlistunit, classes, sysutils, graphunit;
+  mystringlistunit, classes, sysutils, graphunit, lowlevelunit;
 
 const
   gpgCommand = 'gpg --no-auto-check-trustdb --fast-list-mode --fixed-list-mode';
 
 var
   lKeys,kKeys:   tMyStringList;
-  baum:          tList;
-  wurzel,spitze: int64;
-  i:             longint;
+  baum:          tKnotens;
+  wurzel:        tKnoten;
+  spitzen:       array of tKnoten;
+  i,j,k:         longint;
   cK:            tKnoten;
+  s:             string;
+  f:             textfile;
 
 begin
   lKeys:=tMyStringList.create;
   kKeys:=tMyStringList.create;
 
+  write('Kernel-Schlüssel inkl. Signaturen laden ...');
+  kKeys.loadFromPipe(gpgCommand+' --list-sigs --homedir /var/cache/kernelKeys/.gnupg');
+
+  write(' und bereinigen ...');
+  kKeys.grep('^(pub|sig)');
+
+  write(' und umformen ...');
+  kKeys.replace('^pub .*/([0-9A-F]{8}) .*$','pub $1');
+  kKeys.replace('^sig .* ([0-9A-F]{8}) .*$','sig $1');
+
+  write(' und noch mal bereinigen ...');
+  kKeys.uniq('-');
+
+  write(' und in Graphen umwandeln ...');
+  baum:=tKnotens.create;
+  i:=0;
+  j:=0;
+  while i<kKeys.count do begin
+    if leftStr(kKeys[i],4)='pub ' then begin
+      inc(j);
+      if j>=500 then begin
+        write('.');
+        j:=0;
+      end;
+      if rightStr(kKeys[i],8)='65D0FD58' then begin
+        inc(i);
+        continue;
+      end;
+      cK:=baum.findeKnoten(rightStr(kKeys[i],8));
+      inc(i);
+      while (i<kKeys.count) and (leftStr(kKeys[i],4)='sig ') do begin
+        cK.addSig(baum,rightStr(kKeys[i],8));
+        inc(i);
+      end;
+    end
+    else
+      inc(i);
+  end;
+
+  kKeys.clear;
+
+  writeln(' fertig');
+  write('lokale Schlüssel laden ...');
+
   lKeys.loadFromPipe(gpgCommand+' --list-keys');
   lKeys.grep('^pub');
   lKeys.replace('^\S+\s+[^ /]+/([0-9A-F]{8}) .*$','0x$1');
-  kKeys.loadFromPipe(gpgCommand+' --list-keys --homedir /var/cache/kernelKeys/.gnupg');
-  kKeys.grep('^pub');
-  kKeys.replace('^\S+\s+[^ /]+/([0-9A-F]{8}) .*$','0x$1');
-
   lKeys.sort;
-  kKeys.sort;
   lKeys.uniq('-');
-  kKeys.uniq('-');
 
-  writeln(inttostr(lKeys.count)+' lokale Schlüssel');
-  writeln(inttostr(kKeys.count)+' Kernel-Schlüssel');
+  write(' und Kernel-Schlüssel laden ...');
+
+  baum.gibAlles(kKeys);
+
+  write(' und Duplikate finden ...');
 
   lKeys.append(kKeys);
   kKeys.clear;
@@ -40,44 +84,47 @@ begin
   lKeys.sort;
   lKeys.uniq('d');
 
-  lKeys.grep('^0x(CAFAA3E1|00411886|76E21CBB|65D0FD58)$',true);
+  lKeys.grep('^0x(CAFAA3E1|00411886|76E21CBB|65D0FD58|329DD07E|4FF14263|BA50A935|CB944925)$',true); // ignoriere diese Schlüssel lokal, weil ich den Leuten nicht (direkt) vertraue
 
   kKeys.loadFromPipe(gpgCommand+' --list-keys '+lKeys.text);
+  lKeys.clear;
   kKeys.grep('^pub');
   kKeys.grep('expired|revoked',true);
   kKeys.replace('^\S+\s+[^ /]+/([0-9A-F]{8}) .*$','$1');
   kKeys.sort;
 
-  wurzel:=strtoint('$'+kKeys[0]);
-
-  writeln('folgende Kernelschlüssel sind auch lokal vorhanden:');
-  write(kKeys.text);
-  writeln('davon nehme ich jetzt '+kKeys[0]);
+  wurzel:=baum.findeKnoten('00411886');     // Torvalds Schlüssel
+  setlength(spitzen,kKeys.count);
+  for i:=0 to length(spitzen)-1 do
+    spitzen[i]:=baum.findeKnoten(kKeys[i]); // lokal bekannte Schlüssel
 
+  writeln(' fertig');
   kKeys.clear;
-  kKeys.loadFromPipe(gpgCommand+' --list-sigs');// --homedir /var/cache/kernelKeys/.gnupg');
-  kKeys.grep('^(pub|sig)');
-
-  kKeys.replace('^pub .*/([0-9A-F]{8}) .*$','pub $1');
-  kKeys.replace('^sig .* ([0-9A-F]{8}) .*$','sig $1');
-  kKeys.uniq('-');
-
-  baum:=tList.create;
-  i:=0;
-  while i<kKeys.count do begin
-    if leftStr(kKeys[i],4)='pub ' then begin
-      cK:=findeKnoten(baum,strtoint('$'+rightStr(kKeys[i],8)));
-      inc(i);
-      while (i<kKeys.count) and (leftStr(kKeys[i],4)='sig ') do begin
-        cK.addSig(baum,strtoint('$'+rightStr(kKeys[i],8)));
-        inc(i);
-      end;
-    end
-    else
-      inc(i);
+  writeln;
+
+  for i:=0 to length(spitzen)-1 do begin
+    write('0x'+spitzen[i].idStr+': '+inttostr(kKeys.count));
+    j:=baum.wasLiegtZwischen(wurzel,spitzen[i],0,kKeys);
+    writeln(' -> '+inttostr(kKeys.count)+' ('+inttostr(j)+')');
+    kKeys.sort;
+    kKeys.uniq('-');
   end;
 
-  spitze:=strtoint('$00411886'); // Torvalds key
+  writeln(kKeys.count);
+  j:=-1;
+  assignfile(f,'');
+  for i:=0 to kKeys.count-1 do begin
+    s:=kKeys[i];
+    k:=strtoint(erstesArgument(s,':'));
+    if j<>k then begin
+      if j<>-1 then closefile(f);
+      j:=k;
+      assignfile(f,extractfilepath(paramstr(0))+'out.'+inttostr(j));
+      rewrite(f);
+    end;
+    writeln(f,s);
+  end;
+  if j<>-1 then closefile(f);
 
   lKeys.free;
   kKeys.free;
diff --git a/gpggraph.lps b/gpggraph.lps
index 2095e71..7fca6fd 100644
--- a/gpggraph.lps
+++ b/gpggraph.lps
@@ -3,170 +3,175 @@
   <ProjectSession>
     <Version Value="9"/>
     <BuildModes Active="Default"/>
-    <Units Count="5">
+    <Units Count="6">
       <Unit0>
         <Filename Value="gpggraph.lpr"/>
         <IsPartOfProject Value="True"/>
         <IsVisibleTab Value="True"/>
-        <TopLine Value="43"/>
-        <CursorPos X="25" Y="80"/>
-        <UsageCount Value="27"/>
+        <TopLine Value="76"/>
+        <CursorPos X="28" Y="104"/>
+        <UsageCount Value="33"/>
         <Loaded Value="True"/>
       </Unit0>
       <Unit1>
-        <Filename Value="../units/mystringlistunit.pas"/>
-        <EditorIndex Value="2"/>
-        <TopLine Value="171"/>
-        <CursorPos X="12" Y="199"/>
-        <UsageCount Value="13"/>
+        <Filename Value="graphunit.pas"/>
+        <IsPartOfProject Value="True"/>
+        <EditorIndex Value="1"/>
+        <TopLine Value="149"/>
+        <CursorPos X="46" Y="184"/>
+        <FoldState Value=" T3iB06812f"/>
+        <UsageCount Value="28"/>
         <Loaded Value="True"/>
       </Unit1>
       <Unit2>
-        <Filename Value="../units/fileunit.pas"/>
-        <EditorIndex Value="3"/>
-        <TopLine Value="154"/>
-        <CursorPos X="28" Y="172"/>
+        <Filename Value="../units/mystringlistunit.pas"/>
+        <EditorIndex Value="-1"/>
+        <TopLine Value="22"/>
+        <CursorPos X="5" Y="359"/>
+        <FoldState Value=" T3iC037 pibjD035[9590c9 pnCoR0H58"/>
         <UsageCount Value="13"/>
-        <Loaded Value="True"/>
       </Unit2>
       <Unit3>
+        <Filename Value="../units/fileunit.pas"/>
+        <EditorIndex Value="-1"/>
+        <TopLine Value="154"/>
+        <CursorPos X="28" Y="172"/>
+        <UsageCount Value="12"/>
+      </Unit3>
+      <Unit4>
         <Filename Value="/usr/lib/fpc/src/rtl/objpas/classes/classesh.inc"/>
         <EditorIndex Value="-1"/>
         <TopLine Value="751"/>
         <CursorPos X="15" Y="770"/>
-        <UsageCount Value="9"/>
-      </Unit3>
-      <Unit4>
-        <Filename Value="graphunit.pas"/>
-        <IsPartOfProject Value="True"/>
-        <EditorIndex Value="1"/>
-        <TopLine Value="50"/>
-        <CursorPos X="21" Y="79"/>
-        <FoldState Value=" T3Q052O"/>
-        <UsageCount Value="22"/>
-        <Loaded Value="True"/>
+        <UsageCount Value="8"/>
       </Unit4>
+      <Unit5>
+        <Filename Value="../units/lowlevelunit.pas"/>
+        <EditorIndex Value="-1"/>
+        <TopLine Value="46"/>
+        <UsageCount Value="10"/>
+      </Unit5>
     </Units>
     <JumpHistory Count="30" HistoryIndex="29">
       <Position1>
-        <Filename Value="gpggraph.lpr"/>
-        <Caret Line="33" Column="21" TopLine="2"/>
+        <Filename Value="graphunit.pas"/>
+        <Caret Line="19" Column="24"/>
       </Position1>
       <Position2>
-        <Filename Value="../units/mystringlistunit.pas"/>
-        <Caret Line="235" Column="8" TopLine="219"/>
+        <Filename Value="graphunit.pas"/>
+        <Caret Line="54" Column="15" TopLine="34"/>
       </Position2>
       <Position3>
-        <Filename Value="../units/mystringlistunit.pas"/>
-        <Caret Line="31" Column="19" TopLine="7"/>
+        <Filename Value="graphunit.pas"/>
+        <Caret Line="36" Column="36" TopLine="3"/>
       </Position3>
       <Position4>
-        <Filename Value="gpggraph.lpr"/>
-        <Caret Line="37" Column="8" TopLine="2"/>
+        <Filename Value="graphunit.pas"/>
+        <Caret Line="21" Column="45" TopLine="6"/>
       </Position4>
       <Position5>
-        <Filename Value="../units/mystringlistunit.pas"/>
-        <Caret Line="23" Column="27" TopLine="3"/>
+        <Filename Value="gpggraph.lpr"/>
+        <Caret Line="85" Column="23" TopLine="55"/>
       </Position5>
       <Position6>
         <Filename Value="gpggraph.lpr"/>
-        <Caret Line="40" Column="66" TopLine="3"/>
+        <Caret Line="34" Column="49" TopLine="14"/>
       </Position6>
       <Position7>
         <Filename Value="gpggraph.lpr"/>
-        <Caret Line="6" Column="19"/>
+        <Caret Line="37" Column="24" TopLine="17"/>
       </Position7>
       <Position8>
         <Filename Value="gpggraph.lpr"/>
-        <Caret Line="21" Column="22" TopLine="4"/>
+        <Caret Line="74" Column="42" TopLine="49"/>
       </Position8>
       <Position9>
-        <Filename Value="../units/mystringlistunit.pas"/>
-        <Caret Line="28" Column="32" TopLine="8"/>
+        <Filename Value="gpggraph.lpr"/>
+        <Caret Line="27" Column="18" TopLine="2"/>
       </Position9>
       <Position10>
-        <Filename Value="../units/mystringlistunit.pas"/>
-        <Caret Line="29" Column="23" TopLine="8"/>
+        <Filename Value="gpggraph.lpr"/>
+        <Caret Line="27" Column="18" TopLine="11"/>
       </Position10>
       <Position11>
         <Filename Value="gpggraph.lpr"/>
-        <Caret Line="49" Column="10" TopLine="13"/>
+        <Caret Line="33" Column="24" TopLine="11"/>
       </Position11>
       <Position12>
         <Filename Value="gpggraph.lpr"/>
-        <Caret Line="19" Column="21"/>
+        <Caret Line="107" Column="27" TopLine="80"/>
       </Position12>
       <Position13>
-        <Filename Value="gpggraph.lpr"/>
-        <Caret Line="6" Column="30"/>
+        <Filename Value="graphunit.pas"/>
+        <Caret Line="22" Column="19"/>
       </Position13>
       <Position14>
-        <Filename Value="gpggraph.lpr"/>
-        <Caret Line="70" Column="22" TopLine="49"/>
+        <Filename Value="graphunit.pas"/>
+        <Caret Line="61" Column="5" TopLine="38"/>
       </Position14>
       <Position15>
-        <Filename Value="gpggraph.lpr"/>
-        <Caret Line="22" Column="24" TopLine="13"/>
+        <Filename Value="graphunit.pas"/>
+        <Caret Line="15" Column="11"/>
       </Position15>
       <Position16>
-        <Filename Value="gpggraph.lpr"/>
-        <Caret Line="19" Column="21"/>
+        <Filename Value="graphunit.pas"/>
+        <Caret Line="22" Column="18"/>
       </Position16>
       <Position17>
-        <Filename Value="gpggraph.lpr"/>
-        <Caret Line="13"/>
+        <Filename Value="graphunit.pas"/>
+        <Caret Line="57" Column="9" TopLine="24"/>
       </Position17>
       <Position18>
-        <Filename Value="gpggraph.lpr"/>
-        <Caret Line="121" Column="55" TopLine="93"/>
+        <Filename Value="graphunit.pas"/>
+        <Caret Line="174" Column="28" TopLine="141"/>
       </Position18>
       <Position19>
-        <Filename Value="gpggraph.lpr"/>
-        <Caret Line="68" TopLine="34"/>
+        <Filename Value="graphunit.pas"/>
+        <Caret Line="16" Column="18"/>
       </Position19>
       <Position20>
-        <Filename Value="gpggraph.lpr"/>
-        <Caret Line="11" Column="11"/>
+        <Filename Value="graphunit.pas"/>
+        <Caret Line="150" Column="19" TopLine="106"/>
       </Position20>
       <Position21>
         <Filename Value="graphunit.pas"/>
-        <Caret Line="24"/>
+        <Caret Line="42" Column="56" TopLine="16"/>
       </Position21>
       <Position22>
         <Filename Value="graphunit.pas"/>
-        <Caret Line="76" Column="58" TopLine="38"/>
+        <Caret Line="141" Column="80" TopLine="106"/>
       </Position22>
       <Position23>
         <Filename Value="graphunit.pas"/>
-        <Caret Line="25" Column="16"/>
+        <Caret Line="153" Column="18" TopLine="106"/>
       </Position23>
       <Position24>
         <Filename Value="graphunit.pas"/>
-        <Caret Line="87" Column="26" TopLine="25"/>
+        <Caret Line="167" TopLine="106"/>
       </Position24>
       <Position25>
         <Filename Value="graphunit.pas"/>
-        <Caret Line="15" Column="34" TopLine="4"/>
+        <Caret Line="161" Column="47" TopLine="106"/>
       </Position25>
       <Position26>
-        <Filename Value="gpggraph.lpr"/>
-        <Caret Line="6" Column="40"/>
+        <Filename Value="graphunit.pas"/>
+        <Caret Line="164" Column="70" TopLine="144"/>
       </Position26>
       <Position27>
         <Filename Value="gpggraph.lpr"/>
-        <Caret Line="72" Column="22" TopLine="44"/>
+        <Caret Line="72" TopLine="44"/>
       </Position27>
       <Position28>
         <Filename Value="graphunit.pas"/>
-        <Caret Line="20" Column="58"/>
+        <Caret Line="44" TopLine="18"/>
       </Position28>
       <Position29>
-        <Filename Value="graphunit.pas"/>
-        <Caret Line="56" Column="20" TopLine="38"/>
+        <Filename Value="gpggraph.lpr"/>
+        <Caret Line="109" Column="62" TopLine="81"/>
       </Position29>
       <Position30>
         <Filename Value="graphunit.pas"/>
-        <Caret Line="76" Column="25" TopLine="50"/>
+        <Caret Line="42" Column="104" TopLine="22"/>
       </Position30>
     </JumpHistory>
   </ProjectSession>
diff --git a/graphunit.pas b/graphunit.pas
index ca8c58d..af85c17 100644
--- a/graphunit.pas
+++ b/graphunit.pas
@@ -8,27 +8,56 @@ uses
   Classes, SysUtils;
 
 type
+  tKnotens = class;
   tKnoten = class
-    id:   int64;
-    sigs: tList;
-    constructor create(i: int64);
+  private
+    _tag1,_tag2: longint;
+    _idStr:      string;
+    _id:         int64;
+  public
+    sigs: tKnotens;
+    property id: int64
+      read _id;
+    property idStr: string
+      read _idStr;
+    constructor create(i: string);
     destructor destroy; override;
-    procedure addSig(var bm: tList; i: int64);
+    procedure addSig(bm: tKnotens; i: string);
   end;
 
-function findeKnoten(var bm: tList; id: int64): tKnoten; overload;
-function findeKnoten(var bm: tList; kn: tKnoten): tKnoten; overload;
+  tKnotens = class
+  private
+    _inhalt: tList;
+    function rItem(idx: longint): tKnoten;
+    procedure wItem(idx: longint; itm: tKnoten);
+  public
+    property items[idx: longint]: tKnoten
+      read rItem
+      write wItem; default;
+
+    constructor create;
+    destructor destroy; override;
+    function findeKnoten(id: string): tKnoten; overload;
+    function findeKnoten(kn: tKnoten): tKnoten; overload;
+    function wasLiegtZwischen(wurzel,spitze: tKnoten; toleranz: longint; ausgabe: tStringList): longint;
+    procedure gibAlles(ausgabe: tStringList);
+    // Funktionen von tList
+    function count: longint;
+  end;
 
 implementation
 
 uses
   lowlevelunit;
 
-constructor tKnoten.create(i: int64);
+// tKnoten *********************************************************************
+
+constructor tKnoten.create(i: string);
 begin
   inherited create;
-  id:=i;
-  sigs:=tList.create;
+  _idStr:=i;
+  _id:=strtoint('$'+i);
+  sigs:=tKnotens.create;
 end;
 
 destructor tKnoten.destroy;
@@ -36,54 +65,136 @@ begin
   sigs.free;
 end;
 
-procedure tKnoten.addSig(var bm: tList; i: int64);
+procedure tKnoten.addSig(bm: tKnotens; i: string);
 begin
-  findeKnoten(sigs,findeKnoten(bm,i));
+  sigs.findeKnoten(bm.findeKnoten(i));
+end;
+
+// tKnotens ********************************************************************
+
+constructor tKnotens.create;
+begin
+  inherited create;
+  _inhalt:=tList.create;;
 end;
 
-function findeKnoten(var bm: tList; id: int64): tKnoten; overload;
+destructor tKnotens.destroy;
+begin
+  _inhalt.free;
+  inherited destroy;
+end;
+
+function tKnotens.rItem(idx: longint): tKnoten;
+begin
+  result:=tKnoten(_inhalt[idx]);
+end;
+
+procedure tKnotens.wItem(idx: longint; itm: tKnoten);
+begin
+  _inhalt[idx]:=itm;
+end;
+
+function tKnotens.findeKnoten(id: string): tKnoten; overload;
 var
   kn: tKnoten;
 begin
   kn:=tKnoten.create(id);
-  result:=findeKnoten(bm,kn);
+  result:=findeKnoten(kn);
   if result<>kn then
     kn.free;
 end;
 
-function findeKnoten(var bm: tList; kn: tKnoten): tKnoten; overload;
+function tKnotens.findeKnoten(kn: tKnoten): tKnoten; overload;
 var
   mi,ma,i: longint;
 begin
   mi:=0;
-  ma:=bm.count-1;
+  ma:=count-1;
   while mi<=ma do begin
     i:=(mi+ma) div 2;
-    if tKnoten(bm[i]).id<kn.id then begin
+    if items[i].id<kn.id then begin
       mi:=i+1;
       continue;
     end;
-    if tKnoten(bm[i]).id>kn.id then begin
+    if items[i].id>kn.id then begin
       ma:=i-1;
       continue;
     end;
-    if tKnoten(bm[i]).id=kn.id then begin
-      result:=tKnoten(bm[i]);
+    if items[i].id=kn.id then begin
+      result:=items[i];
       exit;
     end;
   end;
-  if (mi>=0) and (mi<bm.count) and (tKnoten(bm[mi]).id=kn.id) then begin
-    result:=tKnoten(bm[mi]);
+  if (mi>=0) and (mi<count) and (items[mi].id=kn.id) then begin
+    result:=items[mi];
     exit;
   end;
-  if (ma>=0) and (ma<bm.count) and (tKnoten(bm[ma]).id=kn.id) then begin
-    result:=tKnoten(bm[ma]);
+  if (ma>=0) and (ma<count) and (items[ma].id=kn.id) then begin
+    result:=items[ma];
     exit;
   end;
   if mi<>ma+1 then
     fehler('Bisektionsfehler: mi<>ma+1!');
   result:=kn;
-  bm.insert(mi,kn);
+  _inhalt.insert(mi,kn);
+end;
+
+function tKnotens.wasLiegtZwischen(wurzel,spitze: tKnoten; toleranz: longint; ausgabe: tStringList): longint;
+var
+  i,j:   longint;
+  neues: boolean;
+begin
+  wurzel:=findeKnoten(wurzel);
+  spitze:=findeKnoten(spitze);
+  for i:=0 to count-1 do begin
+    items[i]._tag1:=-1;
+    items[i]._tag2:=-1;
+  end;
+  wurzel._tag1:=0;
+  spitze._tag2:=0;
+  repeat
+    neues:=false;
+    for i:=0 to count-1 do begin
+      if items[i]._tag1>=0 then // von Wurzel erreichbar
+        for j:=0 to items[i].sigs.count-1 do
+          if (items[i].sigs[j]._tag1<0) or (items[i].sigs[j]._tag1 > items[i]._tag1+1) then begin
+            neues:=true;
+            items[i].sigs[j]._tag1:=items[i]._tag1+1;
+          end;
+      for j:=0 to items[i].sigs.count-1 do
+        if (items[i].sigs[j]._tag2>=0) and ((items[i]._tag2<0) or (items[i]._tag2 > items[i].sigs[j]._tag2+1)) then begin
+          neues:=true;
+          items[i]._tag2:=items[i].sigs[j]._tag2+1;
+        end;
+    end;
+  until not neues;
+
+  result:=-1;
+  for i:=0 to count-1 do begin
+    if (items[i]._tag1>=0) and
+       (items[i]._tag2>=0) and
+       ((result<0) or
+        (result>items[i]._tag1+items[i]._tag2)) then
+      result:=items[i]._tag1+items[i]._tag2;
+  end;
+  for i:=0 to count-1 do
+    if (items[i]._tag1>=0) and
+       (items[i]._tag2>=0) and
+       (result+toleranz>=items[i]._tag1+items[i]._tag2) then
+      ausgabe.add(inttostr(items[i]._tag1)+': '+items[i].idStr);
+end;
+
+procedure tKnotens.gibAlles(ausgabe: tStringList);
+var
+  i: longint;
+begin
+  for i:=0 to count-1 do
+    ausgabe.add('0x'+self[i].idStr);
+end;
+
+function tKnotens.count: longint;
+begin
+  result:=_inhalt.count;
 end;
 
 end.