home *** CD-ROM | disk | FTP | other *** search
/ Chip 2004 March / CMCD0304.ISO / Software / Freeware / Programare / nullsoft / nsis20.exe / Contrib / VPatch / Source / GenPat / TreeCode.pas < prev    next >
Pascal/Delphi Source File  |  2003-12-27  |  7KB  |  252 lines
  1. unit TreeCode;
  2.  
  3. {
  4.   VPatch 2 - Binary Checksum Tree
  5.   ===============================
  6.  
  7.   (c) 2002-2003 Van de Sande Productions
  8.  
  9.   This unit implements a binary search tree, which is constructed from a memory
  10.   block by BuildTree. This memory block is divided into equal-sized blocks of
  11.   BlockSize, and for every block a checksum is calculated. Then, it is inserted
  12.   in the binary tree, which is sorted on the checksum.
  13.   The patch generator will search for the checksums using a binary search, which
  14.   is O(log n) (much better than the old 1.x algoritm, which was O(n)).
  15.  
  16.   What's new
  17.   ----------
  18.   2.1   20031219    Koen            Fixed bug in TreeFind: when tree was a nil
  19.                                     pointer, now returns instead of AVing
  20.   2.0   20030811    Koen            Initial documentation
  21. }
  22.  
  23. interface
  24.  
  25. type
  26.   TSortStack=record
  27.     lo,hi: Integer;
  28.   end;
  29.   PTreeNode = ^TTreeNode;
  30.   TTreeNode = record
  31.     Checksum: Cardinal;
  32.     Offset: Cardinal;
  33.   end;
  34.  
  35. const
  36.   TREENODE_SIZE = SizeOf(TTreeNode);  
  37.  
  38. procedure calculateChecksum(AData: Pointer; AStart, ASize: Cardinal; var K: Cardinal);
  39. procedure calculateNext(AData: Pointer; AStart, ASize: Cardinal; var K: Cardinal);
  40. function BuildTree(ASource: Pointer; var ATree: Pointer; ASourceSize, ABLOCKSIZE: Cardinal): Cardinal;
  41. procedure SortTree(ATree: Pointer; ANodeCount: Cardinal);
  42. procedure ClearTree(var ATree: Pointer; ANodeCount: Cardinal);
  43. function TreeFind(AChecksum: Cardinal; ABlockTree: Pointer; ABlockTreeNodeCount: Integer; var FoundCount: Integer): PTreeNode;
  44. function GetItem(ATree: Pointer; Index, ANodeCount: Cardinal): TTreeNode;
  45.  
  46. procedure Test;
  47.  
  48. implementation
  49.  
  50. uses SysUtils;
  51.  
  52. procedure calculateChecksum(AData: Pointer; AStart, ASize: Cardinal; var K: Cardinal);
  53. var
  54.   A,B,i,j: Cardinal;
  55. begin
  56.   A:=K and $0000FFFF;
  57.   B:=(K and $FFFF0000) shr 16;
  58.   j:=Cardinal(AData)+AStart;
  59.   for i:=1 to ASize do begin
  60.     A:=A + PByte(j)^;
  61.     B:=B + (ASize-i+1)*PByte(j)^;
  62.     Inc(j);
  63.   end;
  64.   K:=(A and $0000FFFF) or ((B and $0000FFFF) shl 16);
  65. end;
  66.  
  67. procedure calculateNext(AData: Pointer; AStart, ASize: Cardinal; var K: Cardinal);
  68. var
  69.   A,B,j: Cardinal;
  70. begin
  71.   j:=Cardinal(AData)+AStart;
  72.   A:=(K-PByte(j-1)^+PByte(j+ASize-1)^) and $0000FFFF;
  73.   B:=((K shr 16)-ASize*PByte(j-1)^+A) and $0000FFFF;
  74.   K:=A or (B shl 16);
  75. end;
  76.  
  77. function BuildTree(ASource: Pointer; var ATree: Pointer; ASourceSize, ABLOCKSIZE: Cardinal): Cardinal;
  78. var
  79.   i, NodeCount: Cardinal;
  80.   Node: TTreeNode;
  81. begin
  82.   Assert(not Assigned(ATree),'Cannot use initialized tree in BuildTree!');
  83.   NodeCount:=ASourceSize div ABLOCKSIZE;
  84.   GetMem(ATree,NodeCount*TREENODE_SIZE);
  85.   if NodeCount > 0 then begin
  86.     for i:=0 to Pred(NodeCount) do begin
  87.       Node.Offset:=i*ABLOCKSIZE;
  88.       Node.Checksum:=0;
  89.       calculateChecksum(ASource,Node.Offset,ABLOCKSIZE,Node.Checksum);
  90.       Move(Node,Pointer(Cardinal(ATree)+i*TREENODE_SIZE)^,TREENODE_SIZE);
  91.     end;
  92.   end;
  93.   Result:=NodeCount;
  94. end;
  95.  
  96. procedure SetItem(ATree: Pointer; Index, ANodeCount: Cardinal; New: TTreeNode);
  97. var
  98.   p: PTreeNode;
  99. begin
  100.   Assert(Index<ANodeCount,'Tree/GetItem: Index too big');
  101.   p:=PTreeNode(Cardinal(ATree)+Index*TREENODE_SIZE);
  102.   p^:=New;
  103. end;
  104.  
  105. function GetItem(ATree: Pointer; Index, ANodeCount: Cardinal): TTreeNode;
  106. var
  107.   p: PTreeNode;
  108. begin
  109.   Assert(Index<ANodeCount,'Tree/GetItem: Index too big '+IntToStr(Index));
  110.   p:=PTreeNode(Cardinal(ATree)+Index*TREENODE_SIZE);
  111.   Result:=p^;
  112. end;
  113.  
  114. procedure SortTree(ATree: Pointer; ANodeCount: Cardinal);
  115. var
  116.   compare: Cardinal;
  117.   aStack: Array[1..128] of TSortStack;
  118.   StackPtr: Integer;
  119.   Mid,i,j,low,hi: Integer;
  120.   Switcher: TTreeNode;
  121. begin
  122.   If ANodeCount = 0 Then Exit;
  123.   StackPtr:=1;
  124.   aStack[StackPtr].lo:=0;
  125.   aStack[StackPtr].hi:=ANodeCount - 1;
  126.   Inc(StackPtr);
  127.   while not (StackPtr=1) do begin
  128.     StackPtr:=StackPtr-1;
  129.     low:=aStack[StackPtr].lo;
  130.     hi:=aStack[StackPtr].hi;
  131.     while true do begin
  132.       i:=low;
  133.       j:=hi;
  134.       Mid:=(low + hi) div 2;
  135.       compare:=PTreeNode(Integer(ATree)+Mid*TREENODE_SIZE)^.Checksum;
  136.       while true do begin
  137.         While PTreeNode(Integer(ATree)+i*TREENODE_SIZE)^.Checksum < compare do begin
  138.           Inc(i);
  139.         end;
  140.         While PTreeNode(Integer(ATree)+j*TREENODE_SIZE)^.Checksum > compare do begin
  141.           j:=j-1;
  142.         end;
  143.         If (i <= j) Then begin
  144.           Move(Pointer(Integer(ATree)+j*TREENODE_SIZE)^,Switcher,TREENODE_SIZE);
  145.           Move(Pointer(Integer(ATree)+i*TREENODE_SIZE)^,Pointer(Integer(ATree)+j*TREENODE_SIZE)^,TREENODE_SIZE);
  146.           Move(Switcher,Pointer(Integer(ATree)+i*TREENODE_SIZE)^,TREENODE_SIZE);
  147.           Inc(i);
  148.           Dec(j);
  149.         End;
  150.         if not (i <= j) then break;
  151.       end;
  152.       If j - low < hi - i Then begin
  153.         If i < hi Then begin
  154.           aStack[StackPtr].lo:=i;
  155.           aStack[StackPtr].hi:=hi;
  156.           Inc(StackPtr);
  157.         End;
  158.         hi:=j;
  159.       end Else begin
  160.         If low < j Then begin
  161.           aStack[StackPtr].lo:=low;
  162.           aStack[StackPtr].hi:=j;
  163.           Inc(StackPtr);
  164.         End;
  165.         low:=i;
  166.       End;
  167.       if not (low<hi) then break;
  168.     end;
  169.     if StackPtr=1 then break;
  170.   end;
  171. end;
  172.  
  173. procedure ClearTree(var ATree: Pointer; ANodeCount: Cardinal);
  174. begin
  175.   FreeMem(ATree,ANodeCount*TREENODE_SIZE);
  176.   ATree:=nil;
  177. end;
  178.  
  179. function TreeFind(AChecksum: Cardinal; ABlockTree: Pointer; ABlockTreeNodeCount: Integer; var FoundCount: Integer): PTreeNode;
  180. var
  181.   lo,mid,hi,m: Integer;
  182.   tmp: Cardinal;
  183. begin
  184.   if not Assigned(ABlockTree) then begin
  185.     FoundCount:=0; Result:=nil;
  186.     Exit;
  187.   end;
  188.   lo:=0;
  189.   hi:=ABlockTreeNodeCount-1;
  190.   while true do begin
  191.     mid:=(lo+hi) div 2;
  192.     tmp:=PCardinal(Integer(ABlockTree)+mid*TREENODE_SIZE)^;
  193.     if tmp = AChecksum then begin
  194.       FoundCount:=1;
  195.       m:=mid;
  196.       Result:=PTreeNode(Integer(ABlockTree)+m*TREENODE_SIZE);
  197.       while m > 0 do begin
  198.         Dec(m);
  199.         if PCardinal(Integer(ABlockTree)+m*TREENODE_SIZE)^ = tmp then begin
  200.           Result:=PTreeNode(Integer(ABlockTree)+m*TREENODE_SIZE);
  201.           Inc(FoundCount);
  202.         end else
  203.           Break;
  204.       end;
  205.       m:=mid;
  206.       while m < ABlockTreeNodeCount-1 do begin
  207.         Inc(m);
  208.         if PCardinal(Integer(ABlockTree)+m*TREENODE_SIZE)^ = tmp then begin
  209.           Inc(FoundCount);
  210.         end else
  211.           Break;
  212.       end;
  213.       Exit;
  214.     end;
  215.     if lo>=hi then Break;
  216.     if AChecksum < tmp then begin
  217.       hi:=mid-1;
  218.     end else begin
  219.       lo:=mid+1;
  220.     end;
  221.   end;
  222.   FoundCount:=0; Result:=nil;
  223. end;
  224.  
  225. procedure Test;
  226. var
  227.   p: Pointer;
  228.   t: TTreeNode;
  229.   r: PTreeNode;
  230.   i,q: Integer;
  231.   NC: Integer;
  232. begin
  233.   NC:=100;
  234.   GetMem(p,800);
  235.   for i:=0 to 99 do begin
  236.     t.Offset:=i*100;
  237.     t.Checksum:=i div 2;
  238.     SetItem(p,i,NC,t);
  239.   end;
  240.   SortTree(p,NC);
  241.   for i:=0 to 99 do begin
  242.     t:=GetItem(p,i,NC);
  243.     Write(IntToStr(t.Checksum)+'  ');
  244.   end;
  245.   r:=TreeFind(7,p,NC,q);
  246.   WriteLn(IntToStr(q));
  247.   t:=r^;
  248.   WriteLn(IntToStr(t.Checksum)+'  ');
  249. end;
  250.  
  251. end.
  252.