% Content-encoding: UTF-8
\documentclass[ngerman]{article}
\usepackage[utf8]{inputenc}
\usepackage{multicol,babel}
\usepackage{xspace}
\setcounter{secnumdepth}{0}
\setcounter{tocdepth}{0}

\begin{document}

\title{32-Bit-Umordnung für FFT bei nur 16-Bit-Breite des Forth-Assemblers}
\ifx\shorttitle\undefined\else
\shorttitle{FFT--Bit--Umkehrung}
\fi
\author{Fred Behringer}
\maketitle

\renewcommand{\figurename}{Bild}

Der vorliegende Artikel ist eine überarbeitete und leicht erweiterte deutsche Fassung meines Leserbriefes aus Heft 114 (2001) der Zeitschrift Forthwrite unserer Forth-Freunde aus Großbritannien (FIG-UK).

\begin{multicols}{2}

In der Maschinensprache des INMOS-Transputers T800 [IT] gibt es (neben weiteren drei Bitmanipulationsbefehlen) den Befehl bitrevnbits (reverse bottom n bits). Bei den INTEL-Prozessoren sucht man einen solchen Befehl vergeblich. Es gibt Aufgaben, bei denen man ihn sehr gut gebrauchen könnte. Die Schnelle Fourier-Transformation (FFT - fast fourier transformation) gehört dazu [FT]. 

Selbstverständlich kann man die Bitumordnung auch in High-Level-Forth erledigen (Schleife und Schiebungen nach links und rechts) [siehe Forthwrite 113]. Aber FFT verlangt nicht ohne Grund nach Maschinen-Code.
 
Bitbearbeitungsbefehle werden bei INTEL recht stiefmütterlich behandelt [TP]. Das bemängelt auch Julian V. Noble in seinem 2001 in der Forthwrite veröffentlichten dreiteiligen Artikel \emph{A Call to Assembly 1/3} [JN], in welchem er für die Verwendung von mehr Assembler in Forth-Programmen plädiert. (Eine von mir angefertigte deutsche Übersetzung erschien in der Vierten Dimension im Jahre 2002 unter dem Titel \emph{Ein Assembl(i)eraufruf} [DN].) 

Ich selbst habe immer wieder betont, dass es mir große Freude bereitet, Forth zum Assemblieren \emph{missbrauchen} zu können, und ich stimme mit Julian Noble (der ja leider vor nicht allzu langer Zeit von einer höheren Instanz abberufen wurde) darüber überein, dass es nicht ungeschickt wäre, Forth den Ein- und Umsteigern über den ungemein eleganten und leicht den eigenen Wünschen anzupassenden Assembler näherzubringen.

Eine Bemerkung in dieser Richtung beläuft sich auf Folgendes: ZF und Turbo-Forth, meine Lieblingsprogramme, sind 16-Bit-Systeme. Mit so gut wie gar keinem Zusatzaufwand und in fast derselben Computerzeit (ich spreche vom Pentium - eigentlich vom AMD-K6/2) kann die Bitumordnung (des 16-Bit-Programms von J.V. Noble) sofort auf 32 Bits ausgedehnt werden. Ohne 32-Bit-Breite im Assembler! (Bei Noble heißt das Umordnungswort stib, also bits rückwärts. Ich werde (siehe Listing) DSTIB (stib für Double-Werte) sagen. Die CPU-Takte, die ich angeben werde, sind dem Buch von T.E. Podschun entnommen [TP].

Zum Ausprobieren ist Folgendes zu bemerken: Seit einer kaum noch rekonstruierbaren Anzahl von Jahren arbeite ich mit einem Programm, mit dessen Hilfe ich Zeichen vom Bildschirm einsammeln und an die momentane DOS-Eingabezeile legen kann - auch aus Turbo-Forth oder ZF heraus. Das spart sehr viel Tipparbeit und hat auch hier das halbautomatische Ausprobieren sehr erleichtert. (Wenn ich mal zwischendurch nicht mehr weiß, mit was ich mich beschäftigen soll, werde ich versuchen, ein solches Programm in Forth zu schreiben, damit ich es den jeweiligen Gegebenheiten besser anpassen kann.) 
In Turbo-Forth gibt es das Wort B. zur binären Darstellung eines einfachgenauen Stackwertes. Man braucht sich nicht lange mit Forth beschäftigt zu haben, um herauszubekommen, wie man sich eine Entsprechung DB. für doppeltgenaue Werte selbst definiert. Ich mache im Listing (siehe unten) einen Vorschlag. Wenn man aber beim Ausprobieren des Wortes DSTIB oder DSTIB-2 (siehe Listing), vielleicht aus Bequemlichkeitsgründen, nur mit B. arbeiten möchte, beachte man, dass bei B. führende Nullen unterdrückt werden. Man glaubt nicht, wie oft das bei Ansicht zweier Binärgruppen zu Fehlinterpretationen führt! Außerdem besteht ja auch auf dem Bildschirm die unselige Umordnung high/low: Würde man (in einem 16-Bit-Forth-System) einen 32-Bit-Wert so auf den Stack legen, wie er bei Intel in einem 32-Bit-Register steht und in den Arbeitsspeicher gelegt wird (Little-Endian), dann kämen die beiden 16-Bit-Hälften verkehrt herum an.

\end{multicols}

\subsection{Listing}
\begin{quote}
\listinginput[1]{1}{2009-04/bitrev.fs}
\end{quote}


\section*{Literatur}

{}[DN] Noble, Julian V.: Ein Assembl(i)eraufruf. Vierte Dimension, Heft
2/2002 (Übersetzung Fred Behringer).\\
{}[FB] Behringer, Fred: Leserbrief in Forthwrite 114. FIG-UK, November 2001.\\
{}[FT] Bronstein et al.: Taschenbuch der Mathematik. Verlag Harry Deutsch 1993,
        S.786.\\
{}[IT] INMOS Limited: Transputer Instruction Set, a Compiler Writer's Guide.           Prentice Hall, 1988.\\
{}[JN] Noble, Julian V.: Forthwrite 113-115. FIG-UK, 2001-2002.\\
{}[TP] Podschun, Trutz Eyke: Die Assembler-Referenz. Addison-Wesley, 2002.\\
{}[VB] Behringer, Fred: Real-Mode-32-Bit-Erweiterung fuer Turbo-Forth. Vierte
        Dimension, Heft 2/1998.

\end{document}
