Elemente in Mengen mit ASM zählen

[LucasL]

Hallo,

ich würde gerne die Anzahl der Elemente in einer Menge zählen, in der Art:

Delphi-Quellcode:

type
  TMenge = set of 0.255

var
  Menge : TMenge;
  
begin
  Menge := [3, 5, 110];
  writeln(Length(Menge)); // gibt 3 aus
end;

Da ich in Delphi keine Funktion gefunden habe, habe ich es mal mit dem Inline-Assembler versucht. Der Tag an dem ich das letzte mal etwas mit Assembler gemacht habe, ist jedoch schon etwas her...

Der Anfang war ja aber noch recht leicht. Wie zu erwarten, steht im Speicher für jedes Element der Menge ein Bit (1 = "Element drin", 0 = "Element nicht drin"). Was mir noch aufgefallen ist: Für bis zu 4 Byte/32 Bit (dementsprechend bis zu 32 Elementen) wird eine Menge als Werte-, ab 33 Elementen als Referenzparameter übergeben. Also übergebe ich lieber gleich die Adresse der Menge als Pointer an meine Assembler-Funktion und lade dann aus dem Speicher...

Jetzt das Problem:
Um möglichst wenig Redundanz zu erhalten, werden natürlich nicht immer gleich 32 Byte für jeden beliebigen Mengen-Typ reserviert, sondern nur so viele, wie gebraucht werden (in diesen Schritten: 1, 2, 4, 8, 16 oder 32 Bytes). Woher weiß ich aber, wie lang mein Mengentyp ist, wieviele Bytes ich also aus dem Speicher in die Register laden muss, um dort dann die Bits auf 1 auszählen zu können?

Hier der Anfang:

Delphi-Quellcode:

function Length(PNT : Pointer) : Byte;
asm
  MOV EAX,[EAX]
  // Bits auszählen, evtl. weitere Speicherbereiche laden,...
  RET
end;

Danke und Gruß,
Lucas

[Dax]

Ich wüsste was viel eleganteres:

Delphi-Quellcode:

type
  TMenge = set of 0..255;

function Length(victim: TMenge): Integer;
var i: Integer;
begin
  Result := 0;
  for i := 0 to 255 do
    if i in victim then
      Inc(Result);
end;

[3_of_8]

Ich würd das in etwa so machen:

Delphi-Quellcode:

function countElements(ASet: TMySet): Integer;
asm
  mov eax, [eax]
  mov ecx, 0
  @loop:
  mov edx, eax
  and edx, 1
  add ecx, edx
  shr eax, 1
  jnz @loop
  mov eax, ecx
end;

[alzaimar]

Wie macht man es bei einem 'Set Of TFoobar'? Klappt das dann?
Ich würde, weil ich selten mit Mengen arbeite, mir den 5-Zeiler von Dax an die jeweilige Menge anpassen und als Template ablegen.

Delphi-Quellcode:

Function SetOf|Type|Length (aSet : T|Type|Set) : Byte;
Var
  i : |Type|;

Begin
  Result := 0;
  For i:= Low (|Type|) To High (|Type|) Do
    If i in aSet Then Inc (Result)
End;

Und '|Type|' wird im Template durch die Basistype der Menge (TFoobar, Byte etc.) ersetzt.

@3_of_8: Ich kenn mich mit Intel-Assembler gar nicht aus, aber stimmt es, das Du einfach so lange die bits zählst, bis das Byte leer ist?
Dann wird Deine Funktion bei einem TByteset mit den Elementen [255,0] nicht richtig funktionieren.

[3_of_8]

Warum nicht?

Ich addiere zum Zähler 1 dazu, wenn das niedrigste Bit gesetzt ist und shifte dann nach rechts.

[alzaimar]

Na, ich dachte Die Menge [0,255] wird doch als 8 bytes [70,00,00,00,00,00,00,01] dargestellt. die Bytes 2-7 sind eh null.

Bis wohin wird denn da geshiftet? Ich sags nochmal: Ich bin ASM-Depp (auch ein passender Nick für mich :stupid: ) und lasse mich von Dir gerne aufklären..

[shmia]

Du brauchst nicht unbedingt Assemblercode, um Bits schnell zu zählen:
http://www.delphipraxis.net/internal...ct.php?t=44355

[alzaimar]

:thumb:

[3_of_8]

In dem Fall würde es dennoch funktionieren.

1000 0001 => Counter wird inkrementiert
0100 0000 => Counter bleibt gleich
0010 0000 => Counter bleibt gleich
0001 0000 => Counter bleibt gleich
0000 1000 => Counter bleibt gleich
0000 0100 => Counter bleibt gleich
0000 0010 => Counter bleibt gleich
0000 0001 => Counter wird inkrementiert
0000 0000 => Schleife beendet

[alzaimar]

3_of_8: Es sind 8 Bytes, nicht eins.

[himitsu]

Code:

00001000 00000000 10000001 => Counter wird inkrementiert 
00000100 00000000 01000000 => Counter bleibt gleich 
...
00000000 00100000 00000010 => Counter bleibt gleich 
00000000 00010000 00000001 => Counter wird inkrementiert 
00001000 00001000 [color=#ff0000]00000000[/color] => Schleife beendet

[marabu]

Hi folks,

[0,255] wird durch die Bytes [01, 00, 00, 00, 00, 00, 00, 80] repräsentiert, wenn ich nicht irre. Die Anzahl der Bytes, die einen Set repräsentieren, kann man übrigens mit SizeOf() bestimmen.

@Manuel: alle wollen dir nur mitteilen, dass dein Code nur register sets (maximal 32 Elemente) verabeitet. Dabei kann unter gewissen Umständen (packed) auch ein zu großer Wert als Ergebnis ausgewiesen werden.

Freundliche Grüße

[3_of_8]

Jetzt versteh ichs, ich hatte einen Denkfehler, ich dachte ein set of [0..255] ist 1 Byte groß... :wall:

Mein Code funktioniert natürlich nur bist zu 32 Elementen...

[Hawkeye219]

Manuel, deine Funktion erwartet Mengen mit mehr als 32 Elementen, sie verarbeitet dann aber nur die ersten 32 Elemente. Wenn du die erste Zeile entfernst, können Mengen mit bis zu 32 Elementen verarbeitet werden.

Zitat:

Zitat von LucasL

Was mir noch aufgefallen ist: Für bis zu 4 Byte/32 Bit (dementsprechend bis zu 32 Elementen) wird eine Menge als Werte-, ab 33 Elementen als Referenzparameter übergeben.

Gruß Hawkeye

[LucasL]

Mit SizeOf klappts. Habs jetzt mal wie folgt gemacht und es scheint zu funktionieren, egal wieviel Platz die Menge benötigt (1 - 32 Byte).

Delphi-Quellcode:

function MySizeOf(var Menge: TMySet): Byte;
  function CountBits(C: Byte; P: Pointer): Byte;
  asm
    MOV CL, AL         // Byteanzahl nach CL
    MOV EAX, 0         // Bitzähler EAX initialisieren
    @loop1:
      MOV EBX, [EDX]   // Bits nach EBX laden
      MOV CH, 8        // Bitanzahl nach CH
      @loop2:
        ROR EBX, 1     // Niedrigstes Bit von EBX nach CF schieben
        JNC @nocarry
        ADD EAX, 1     // CF gesetzt? Dann EAX inkrementieren
        @nocarry:
        DEC CH
        JNZ @loop2
      ADD EDX, 1       // nächstes Bit adressieren
      DEC CL
      JNZ @loop1
  end;
begin
  MySizeOf := CountBits(SizeOf(Menge), @Menge);
end;

Gruß,
Lucas

[Flocke]

@LucasL: kleine Optimierung: statt

Code:

JNC @nocarry
ADD EAX, 1     // CF gesetzt? Dann EAX inkrementieren
@nocarry:

kannst du auch einfach

Code:

ADC EAX, 0     // EAX um CF inkrementieren

schreiben.

[LucasL]

Thx, und man sollte die Register, welche nicht sowieso von der Funktion als Parameter belegt werden, vorher noch mit Push bzw. am Ende mit Pop retten... So:

Delphi-Quellcode:

function Length(Menge: TMySet): Byte; overload;
    function CountBits(C: Byte; P: Pointer): Byte;
    asm
     PUSH EBX
     PUSH ECX
     MOV CL, AL         // Byteanzahl nach CL
      MOV EAX, 0         // Bitzähler EAX initialisieren
      @loop1:
        MOV EBX, [EDX]   // Bits nach EBX laden
        MOV CH, 8        // Bitanzahl nach CH
        @loop2:
          ROR EBX, 1     // Niedrigstes Bit von EBX nach CF schieben
          ADC EAX, 0     // CF zu EAX addieren
          DEC CH
          JNZ @loop2
        ADD EDX, 1       // nächstes Bit adressieren
        DEC CL
        JNZ @loop1
      POP ECX
      POP EBX
    end;
  begin
    Result := CountBits(SizeOf(Menge), @Menge);
  end;

[3_of_8]

Soweit ich das sehe, sind alle zu sichernden Register hier vom Caller zu retten. Bei ebx bin ich mir ned ganz sicher, aber die anderen iirc schon.

[LucasL]

EAX (C) und EDX (P) werden automatisch gerettet, das stimmt. EBX und ECX müssen noch zusätzlich gesichert werden, zumindest schließe ich das aus den heftigen Nebenwirkungen, wenn ich sie nicht rette ;-)...