Assembler-Programmdesign

7

Dies ist ein Hausaufgabenproblem, und ich habe letzte Nacht versucht, es zu lösen, aber ich bin immer noch ein Neuling in der Assemblersprache.

Gib mir nicht die vollständige Lösung, gib mir nur einen Hinweis.

Entwerfen Sie ein ARM Assembly Language-Programm, das einen in R1 gespeicherten 32-Bit-Wert untersucht und die Anzahl der zusammenhängenden Sequenzen von 1s zählt. Zum Beispiel 01110001000111101100011100011111enthält der Wert: sechs Folgen von 1s.

Schreiben Sie den Endwert in das Register R2.

Ich denke, der Algorithmus besteht darin, jedes Zeichen ieinzeln zu lesen und jedes Mal um 1 zu erhöhen, wenn es 2 fortlaufende Einsen gegenübersteht. Aber wie geht das in Assemblersprache?

Avnish Gaur
quelle
2
Ihr letzter Absatz scheint mir ein wenig daneben zu liegen. Aber ich bin mir nicht sicher, wie viel von einem Hinweis Sie wollen, also sage ich nur Folgendes: Das Wichtigste, wonach Sie suchen müssen, ist, wenn zwei benachbarte Bits unterschiedlich sind, nicht dasselbe. Überlegen Sie, was passieren würde, wenn Sie eine Kopie der Daten in R1 nehmen, um ein Bit verschieben und mit dem ursprünglichen Wert XOR-verknüpfen würden.
Dave Tweed
1
In Ihrer ISA sollte es definitiv eine Anweisung geben, das Bit durch Carry zu drehen. Zuerst löschen Sie die Übertragsflagge. Und dann können Sie es einfach nach links / rechts drehen und den Wert der Übertragsflagge überprüfen. Dann wird dieser Übertragswert in Ihre Zustandsmaschine eingegeben. Codieren Sie dafür eine einfache Zustandsmaschine.
Standard Sandun
Und denken Sie daran, dass ein Register 0 und 1 Bits enthält, nicht die Zeichen 0 und 1. Sie sollten sich die bitweisen Operatoren einschließlich der Verschiebungsanweisungen ansehen.
Joe Hass
2
Wenn Sie neu in asm sind, aber nicht C sagen möchten: Schreiben Sie C-Code, der das Problem löst, und übersetzen Sie diesen Schritt (Schritt) Schritt für Schritt in asm.
Wouter van Ooijen
3
@WoutervanOoijen Ich habe sogar ein Programm gefunden , das diese C-> asm-Übersetzung automatisch
ausführt

Antworten:

10

Schreiben Sie eine Schleife, um das Wort nach links oder rechts zu verschieben (spielt keine Rolle), bis das Wort aus Nullen besteht. Das Übertragsflag gibt Ihnen den Wert des nächsten Bits an.

Wenn Carry ist 1und der vorherige Carry Null war, starten Sie eine neue Sequenz von 1s. Setzen Sie dann ein Vorher-war-zuerst-eins-Flag. (Ich gehe davon aus, dass Sie mit zusammenhängend mindestens 2 meinen.)

Wenn Carry eingestellt ist 1und eingestellt previous-was-a-first-oneist, haben Sie eine zusammenhängende Reihe und erhöhen Ihren Zähler. Lösche die previous-was-a-first-oneFlagge.

Wenn Carry 0dann klar ist das previous-was-a-first-one.

bearbeiten
Anscheinend erfordert "zusammenhängend" nicht mehr als 1 Bit, und dann ist es noch einfacher:

Set `previous' to `0`.
Shift left until word is all zeros.
If `carry` = `1` and `previous` = `0` increment counter.
Set `previous` to `carry`.
stevenvh
quelle
1
Warum würden Sie "mindestens 2" annehmen, wenn das Beispiel, das er gab, eine Folge von nur einer 1 enthielt?
Dave Tweed
4
@ Dave - Das Beispiel enthält eine isolierte '1', aber er sagt nicht, ob er dies als zusammenhängende Sequenz zählt. Jetzt ist Englisch nicht einmal meine zweite Sprache, sondern meine dritte, also nimm es mit, aber IMO "zusammenhängend" vermutet mindestens zwei nacheinander.
Stevenvh
3
@ Dave - zusammenhängend : 1. "Berühren entlang der Seite oder Grenze; ​​in Kontakt" 2. "physisch benachbart; benachbart" 3. "vor oder nach der Zeit"
Stevenvh
1
Ja, er tat es - er sagte, dass das Beispiel sechs Zeichenfolgen enthielt, also zählt er offensichtlich die isolierte '1'
Dave Tweed
1
@ Dave - In der Tat hat er. "Contiguous" scheint ein sehr dehnbares Konzept zu sein :-). Meine Antwort wurde aktualisiert. Danke für die Rückmeldung.
Stevenvh
1

Hier ist eine Lösung, die über die Anzahl der Zeichenfolgen und nicht über die Anzahl der Bits im Wort iteriert. Da ich mit der ARM-Assemblersprache nicht wirklich vertraut bin, gebe ich sie in C an. Da nur bitweise Operatoren verwendet werden, wird sie ziemlich direkt in Assembler-Code übersetzt.

int nstrings (unsigned long int x)
{
   int result = 0;

   /* convert x into a word that has a '1' for every transition from
    * 0 to 1 or 1 to 0 in the original word.
    */
   x ^= (x << 1);

   /* every pair of ones in the new word represents a string of ones in
    * the original word. Remove them two at a time and keep count.
    */
   while (x) {
     /* remove the lowest set bit from x; this represents the start of a
      * string of ones.
      */
     x &= ~(x & -x);
     ++result;

     /* remove the next set bit from x; this represents the end of that
      * string of ones.
      */
     x &= ~(x & -x);
   }
   return result;
}
Dave Tweed
quelle
1

Nur Vorschlag wie gefragt. Sie müssen durch jedes Bit verschieben, dies kann durch shiftingdie Nummer auf die erfolgen right. Überprüfen Sie vor dem Verschieben den Wert des am weitesten rechts liegenden Bits. Dies kann durch die Operation ANDmit dem Kunden erreicht werden 1. Verwenden Sie eine gewisse Temperatur, um den zuletzt überprüften Wert zu speichern und einen Zähler an der "ansteigenden Flanke" zu erhöhen, dh wenn sich der vorherige Wert von 0 auf 1 im Pseudocode ändert

SET T1=0
SET CNT=0
WHILE INPUT != 0 DO
    IF INPUT AND 1 != 0 AND T1 == 0 INC CNT
    T1 =  INPUT AND 1
    RIGHT SHIFT INPUT
END WHILE
Felice Pollano
quelle
0
  1. Ein gegebenes Register X hat das Ergebnis. Initialisiere es mit Null.
  2. Nehmen Sie den zu verarbeitenden Originalwert und speichern Sie ihn in zwei Registern, z. B. A und B.
  3. Drehe A ein Bit nach rechts, mache ein XOR von A mit B, setze das Ergebnis in A.
  4. Wenden Sie eine 1-Stunden-Maske auf A an und setzen Sie das Ergebnis in B.
  5. Summe B bis X.
  6. Verschieben Sie ein Bit nach rechts und, wenn nicht Null, fahren Sie mit Schritt 4 fort
  7. Teilen Sie X durch 2 (verschieben Sie es ein Bit nach rechts)

Dies funktioniert, weil das Ergebnis des XOR in Schritt 3 an jedem Punkt, an dem es einen Übergang gab, ein Paar von Einsen aufweist. Wenn Sie also zählen, wie viele Einsen Sie haben, und durch 2 teilen, haben Sie, wie viele Übergänge es gab. Dies gibt Ihnen die Anzahl der Blöcke aufeinanderfolgender Werte.

Wenn X zu 0 führt, haben Sie entweder alle Einsen oder alle Nullen. Sie können also zunächst prüfen, ob der ursprüngliche Wert 0 ist, und in diesem Fall sofort mit Null zurückkehren, ohne die obigen Schritte auszuführen. Wenn dies nicht der Fall ist und X 0 ist, geben Sie 1 zurück. Wenn nicht, teilen Sie es erneut durch 2 (da die Anzahl der Blöcke mit 1 natürlich die Hälfte der Anzahl der verschiedenen Blöcke betragen muss).

fceconel
quelle