"Einsenfüller" in Assembler?

[MaOfDe]

Ich will eine Prozedur schreiben, die zu einen Speicherbereich mit einer bestimmten Anzahl an Einsen auffüllt. Der Speicherbereich ist gegeben durch einen Zeiger und einer Größenangabe. Ich könnte es mit and, or und not für jedes einzelne Bit machen, aber das scheint mir ein bissel ineffizient.

Der Algorithmus ist ungefähr:
- zähle alle vorhandenen Einsen
- wenn es mehr als gefordet sind, beende den Algorithmus
- sonst mache alle Nullen vom Lowbit aus zu Einsen, bis die geforderte Anzahl erreicht ist

Delphi-Quellcode:

procedure Fill(Size: Byte; X: Pointer; NmBits: Byte);

Wie geht es in Assembler? Mein Problem ist, dass ich nicht in der Assembler-Materie bin ^^. Ich weiß weder wie man die Funktionparameter anspricht, noch wie man den Wert hinter dem Pointer bearbeitet. Kenne zwar einige Befehle, aber das reicht nicht aus ^^ (ADD, AND, OR,...).

[grizzly]

Ich verstehe leider nicht ganz, was die Prozedur machen soll.
Einen Speicherbereich mit einer bestimmten Anzahl Bits füllen?
Also ähnlich wie FillChar() einen Bereich mit einer bestimmten Anzahl Bytes füllt?

Wär das nicht in etwa so etwas:

Delphi-Quellcode:

PROCEDURE FillBits(VAR Data; NumBits: integer);
BEGIN
  IF NumBits > 7 then
    FillChar(Data, NumBits shr 3, #$FF); // Die vollständigen Bytes auf einen Rutsch füllen
  // Die restlichen Bits eintragen...
  Tbytearray(Data)[NumBits shr 3] := Tbytearray(Data)[NumBits shr 3] or ($FF shl (NumBits and $07) shr 8); 
END;

Diese Routine füllt in den angegebenen Speicher "NumBits" Bits. Die restlichen Bits bleiben unangetastet. (Das war zumindest die Intention...;) )

Ich weiß nicht, ob es sich hier lohnt, das in Assembler zu übersetzen. FillChar läuft u.U. eh schon mit 32Bit Unterstützung (will sagen, es füllt die Bytes nicht einzeln, sondern immer gleich in 4er Paketen). Kann mich natürlich täuschen.

Und vermutlich hab' ich die Aufgabe mal wieder nicht verstanden....

Gruß
Michael

[MaOfDe]

OK ich schreibs nochmal konkret mit nem Beispiel:

Wir haben zum Beispiel ein Word, gefüllt mit Einsen und Nullen:

1001001001110101
(links High, rechts Low)

Und man will zB. mindestens 10 Einsen drin haben, dann soll das Word nachher so aussehen.

1001001001111111

Mit FillChar geht das leider nicht so leicht ;-).
Hintergrund ist halt, ne Rechnug mit Mengen und es soll immer ne bestimmte Anzahl an Elementen drin sein in der Teilmenge (1=Element ist in der Teilmenge; 0=Element ist nicht in der Teilmenge). Und einfach hoczählen dauert zu lange ;-).

[vlees91]

Kenn mich damit eigentlich garnicht aus, aber so rein theroretisch wuerde ich einfach die hinteren x Zeichen abschneiden und dann die gleiche Anzahl in 1'en dranhaengen (zur not die Zahl mit 10^anzahl_stellen multiplizieren (nur dann eben in binair) und dann + 111111.....)

[MaOfDe]

Mh das wird kompliziert. Es gibt zB Fälle wo das nicht so einfach ist:

Ein Byte soll auf 5 Einsen aufgefüllt werden:
11000010

Wenn ich bei diesem Byte die letzten 5 Bits abschneiden würde und durch Einsen ersetze kommt aber
11011111
raus und das hat 7 Einsen. Ich müsste also auch die Stellen der Nullen identifizieren ^^ und das ist dann wieder zu zeitaufwändig...

[vlees91]

Tut mir Leid, dann hab ichs falsch verstanden

[Hawkeye219]

Hi,

man kann die folgende Routine sicher noch optimieren, für den Anfang sollte sie aber genügen:

Delphi-Quellcode:

function BitCount (Data: Byte): Integer;
const
  Bits : array [0..15] of Byte
       = (0, 1, 1, 2,  1, 2, 2, 3,  1, 2, 2, 3,  2, 3, 3, 4);
begin
  Result := Bits[Data shr 4] + Bits[Data and 15];
end;

procedure FillBits (var X; Size, NumBits: Integer);
var
  BitPos : Integer;
  Index  : Integer;
  Space  : Integer;
  Buffer : array [0..MaxInt - 1] of Byte absolute X;
begin
  for Index := 0 to Size - 1 do
    Dec (NumBits, BitCount(Buffer[Index]));

  Index := 0;
  while ((Index < Size) and (NumBits > 0)) do
    begin
      Space := 8 - BitCount(Buffer[Index]);
      if (NumBits >= Space) then
        Buffer[Index] := $FF
      else
        for BitPos := 0 to 7 do
          if (not Odd(Buffer[Index] shr BitPos)) then
            begin
              Inc (Buffer[Index], 1 shl BitPos);
              Dec (NumBits);
              if (NumBits = 0) then
                Exit;
            end;
      Dec (NumBits, Space);
      Inc (Index);
    end;
end;

Gruß Hawkeye