Fax Versand und Fax Empfang auf FritzBox oder PC-Linux

@meckerfritz: Du liegst falsch, wie Dir ein Blick auf die Überschrift des Themas ("Fax Versand und Fax Empfang auf FritzBox oder PC-Linux") zeigt. Es geht also durchaus auch um den PC und speziell um Linux. Wer lesen kann, ist klar im Vorteil.
 
Konkret geht es hier darum, unter Linux mit einer CAPI, bei der die optionale G3 Funktionalität nicht implementiert ist, trotzdem Faxe zu senden und zu empfangen.
Primär ging es mir dabei darum, dies auf der FritzBox zu tun, aber da das Programm auf einem PC-Linux mindestens so gut funktioniert (wegen der besseren CPU-Leistung), daher habe ich diese Verwendung auch mit dazu geschrieben. Nur für diesen Zweck hätte ich das Programm aber nicht gemacht, denn auf dem PC-Linux kann man die AVM ISDN Karten verwenden, deren CAPI die Option FAX G3 unterstützt. Inzwischen funktionieren diese auch auf 64-Bit Linux.

Daß ich bei den Tests dieses Programms gemerkt habe, daß der Versand über c2faxsend immer als erfolgreich betrachtet wird, sobald sich am anderen Ende der Leitung ein Faxgerät gemeldet hat, ist ein anderes Thema, denn das wußte ich noch nicht, als ich damit angefangen habe.

Wer von Windows aus Faxe übertragen will, kann das mit dem genannten AVM-Programm "Fritz!Fax" machen, aber das hat nichts mit dem Programm hier zu tun.

@ichego1
Ebensowenig haben damit die immer wieder ins Spiel gebrachten Links auf andere Programme zu tun, bei denen es um Einrichtung von HylaFax oder um Zusatzfunktionen zu HylaFax geht.

Ich kenne HylaFax, ich verwende es auch schon seit etlichen Jahren, und ich weiß auch, wie ich es installieren kann.

Ich kenne auch spandsp, was man schon daran erkennen kann, daß das hier vorgestellte Programm spandsp verwendet.


Das einzige Problem hier ist, daß die CPU-Leistung einer FritzBox für das Programm in der jetzigen Form anscheinend nicht ganz ausreicht. Prinzipiell geht es, aber nach einigen Minuten Empfang kommt es aus dem Takt.

Das gleiche Programm auf einem PC mit 400MHz kann über Remote-CAPI auf die FritzBox zugreifen und auf diese Weise ein Testfax mit einer 2MB großen Test-Seite, die bei 14400 Bit/s ca. 20 Minuten braucht, korrekt übertragen. Dabei ist weder auf der Box noch auf dem PC die Auslastung übermäßig hoch.

Die ganzen Ergänzungen wie HylaFax, IAXmodem, GOfax kann man in Betracht ziehen, sobald das Programm in der Lage ist, mit der vorhandenen CPU Faxe zu empfangen.
Wobei es denkbar wäre, daß mit weiteren Optimierungen das CPU-Leistung für den Empfang gerade ausreicht, aber nicht mehr zusätzlich für die genannten Programme. Aber darüber kann man sich Gedanken machen, wenn es soweit ist.
 
Ich weiß es doch und sage ja nichts anderes. Deshalb habe ich meine Antwort ja auch als "semi-OT" markiert, ich wollte nur helfen, weil es auch nicht allgemein bekannt ist, daß das Faxen mit der Fritz!Box unter Windows funktioniert. Die dafür vorgesehene Software ist schließlich "unsupported" und muß erst mal auf dem Server gefunden und heruntergeladen werden.
 
kriegaex: Der Bitte um Löschung komme ich bei dieser Leerlauf-Diskussion gern nach. Nur diesen Beitrag lasse ich mal stehen, weil er recht anschaulich begründet, wieso ichegos gut gemeinte Vorschläge wohl nicht so ganz ins Schwarze treffen. Ichego, sei bitte nicht beleidigt und poste weiter fleißig, aber halte Dich ein bißchen ans Thema und überflute ein Thema nicht mit zig Links. Dankeschön. :)

@ichego1:

Ich kenne nur eine einizge freie Open Source Softmodem-DSP-Implementierung, und das ist Spandsp. Und egal ob Iaxmodem, Asterfax oder RalfFriedls CapiSpFax oder noch einige andere, alle benutzen sie intern Spandsp als "Faxmaschine" und unterscheiden sich daher im Wesentlichen nur "äußerlich", durch die Schnittstellen, die sie nach außen anbieten.

Und wenn schon der Motor, den man auf ein ganz einfaches Fahrgestell montiert (-> CapiSpFax) es nicht schafft, den Berg hochzufahren, warum sollte es dann ein vollbeladener Lastwagen mit Anhänger (Iaxmodem+Asterisk+modembasiertes Faxprogramm) schaffen, mit genau dem selben Motor den Berg hochzufahren? Zu allererst muß der Motor selbst zuverlässig laufen (und das tut Spandsp zwar weitgehend auf einem PC, der eine entsprechende Rechenleistung hat, aber nicht auf der Box).

Hilfreich wäre, wenn Du anstatt unterschiedlicher Verpackungen der selben Maschine tatsächlich alternative Open Source Softmodem-Implementierungen (ungleich Spandsp) nennen könntest. Dann könnte man die auch mal auszuprobieren und mit Spandsp vergleichen.
 
Zuletzt bearbeitet von einem Moderator:
Mir kam der Gedanke, ob es denn nicht grundsätzlich möglich wäre, die beiden Teile Empfang und Dekodieren aufzuteilen, wenn der Router mit den Berechnungen dazu überlastet ist.

Wäre es nicht möglich, ein eingehendes Fax zunächst auf dem AB zu speichern und in einem weiteren Schritt zu gegebener Zeit diese gespeicherte Nachricht vom PC aus abzurufen und dann dort zu dekodieren?
 
Keine Ahnung, ob das geht, ich lese hier ja im wesentlichen nur mit, aber ich möchte mal zwischendurch zum Ausdruck bringen, daß ich das für eine kreative und sinnvolle Idee halte, unabhängig davon, ob es geht oder nicht. Ich mag Querdenker, bin selbst auch einer.
 
Das wollte ich auch vorschlagen, dass ein Teil der Umkodierungsarbeit offline erledigt wird. Es kann ruhig die Box machen aber mit einer niedriger Priorität (wenn man die Priorität überhaupt setzen kann).
Allerdings deine Idee mit AB wird in der Praxis nicht klappen. Denn wenn du dem Fax bei der Arbeit zugehört hast, hast du bestimmt gemerkt, dass es keine Einmann Show ist. Die beiden Gegenstellen verständigen sich immer gegenseitig. Wie das genau ist, weiß ich wie Alexander auch nicht, weil ich hier ebenfalls nur mitlese. Ich denke aber, dass die Ganze Geschichte paketweise abläuft: Ein Paket der daten wird gesendet, die Gegenstelle nimmt es an und gibt am Ende sein "ok". Dann kommen die nächsten Pakete. Wenn die Gegenstelle Verständnisprobleme hat, werden die Pakete wiederholt.
D.h. dein "Anrufbeantworter" soll schon genug intelligent sein, um die Datenströme auf Richtigkeit und Vollständigkeit zu prüfen. Danach kann er diese Rohdaten von mir aus ohne das Dekodieren irgendwo ablegen.

MfG
 
Die einfache Aufzeichnung und spätere Decodierung funktioniert nicht.
Das empfangende Gerät muß zunächst seine Fax-Kennung senden und welche Formate es unterstützt. Das funktioniert auch, sonst würde die Gegenstelle gar nicht anfangen zu senden.

Nachdem aber der Sender eine Seite übermittelt hat, muß der Empfänger zurückmelden, ob die Seite erfolgreich empfangen wurde oder nicht. Da man nicht ausschließen kann, daß die Übertragung gestört ist, könnte man allenfalls auf Verdacht die Seite bestätigen. Dann hat man die Gefahr, daß man eine Seite bestätigt hat, die sich nachher als unlesbar herausstellt.

Die Prüfung "auf Richtigkeit und Vollständigkeit" bedeutet nun einmal die Decodierung des Modemsignals und Auswertung der digitalen Nutzdaten.

Was dagegen bei mir gut funktioniert, ist die Verarbeitung in Echtzeit auf dem PC vorzunehmen. Das war zwar nicht mein Hauptziel, aber bei PC über Remote-CAPI funktioniert es, obwohl da noch die Netzwerkübertragung mit dazukommt.
 
Auffällig fand ich, dass es vorübergehende Peaks gibt, die einige Sekunden andauern und in denen das Faxprogramm ziemlich viel Zeit verbraucht (gleich ca. 10-20% auf einem PC (im Energiesparmodus, 'runtergetaktet auf 800MHz - um der Situation auf der Box zumindest ein Bisschen näher zu kommen)) während die meiste Zeit der CPU-Bedarf nur 0..2% beträgt, obwohl laut "-vv" offenbar auch bei dieser niedrigen CPU-Belastung ununterbrochen Daten empfangen werden. Jetzt frage ich mich natürlich, was passiert in den Hochlastphasen? Bis jetzt konnte ich es nicht eingrenzen... :noidea:

(ich bin mir allerdings nicht ganz sicher, ob die von "top -p <pid> -d 1" im Sekundentakt angezeigte Auslastung auch stimmt, oder ob hier möglicher Weise eine Interferenz zwischen den Timer-Interrupts des Systems und dem Sende/Emfpangstakt (ein Paket alle 25ms) den anzezeigten CPU-Verbrauch des Prozesses verfälscht).
 
Daß die CPU-Auslastung nicht gleichmäßig ist, ist mir auch schon aufgefallen. Allerdings weiß ich auch nicht, was in der Zeit gemacht wird.

Um diese CPU-Spitzen auszugleichen, habe ich ja schon einige Pakete vorweg gesendet, damit eine Reserve da ist. Diese Reserve kann aber nicht beliebig groß sein, weil mit dieser Reserve auch die Verzögerung steigt. Und wenn die Verzögerung zu groß ist, gibt es einen Timeout und es geht gar nichts mehr.
Einige Sekunden sind da vermutlich zu viel.

Die Anzeige von top halte ich für vertrauenswürdig, zumindest hatte ich bisher keinen Grund, sie anzuzweifeln.
 
zu den peaks bei der auslastung:
schaut euch mal den spandsp code an, es gibt unterschiedliche "stages" beim faxempfang mit unterschiedlichen modulationen. die sind natürlich auch alle unterschiedlich rechenintensiv... das alleine würde aber noch nicht die großen ausreisser erklären.
die andere sache ist die libtiff. spandsp demoduliert, soweit gut, dann decodiert es noch das Faxprotokoll (wenn ich das richtig in erinnerung habe) und übergibt die daten an libtiff. libtiff enthält auch noch ein paar rechenintensive schritte (keine ahnung wie stark, soweit bin ich dann in die sourcen nicht vorgedrungen) wenn das tiff file abgespeichert wird. vllt. kommen daher die peaks... da ja nicht immer was gespeichert wird, bzw. das tiff codieren/kompriemieren/dekomprimieren (meist lzw oder ähnliches) auch nicht bei allen arten von daten gleich aufwendig ist.

als ich damals am faxempfang gearbeitet habe (damals noch ivcall im alten thread), habe ich oft profiling befehle in die spandsp library gesetzt um rauszufinden wie viel zeit die einzelnen teile brauchen. also einfach uhrzeit vorher und nachher messen und ergebnis ausgeben. problem hierbei: fbox hat keinen wirklich hochauflösenden timer, so dass das nicht wirklich aussagekräftig ist, wobei es eigentlich gereicht hat, weil ja gerade die rechenintensiven stellen länger gebraucht haben, so dass die auflösung gereicht hat. nur weiter ins detail gehen wurde schwer... also so als kleine anregung. vielleicht hat ja jetzt jemand mehr erfolg bei der suche als ich damals :)

PS: Zum Thema "fixed-point" ... seit ihr sicher, dass wenn spandsp mit fixed-point kompiliert wird, dann auch wirklich der softmodem teil damit gebaut wird? In der Version, die ich verwendet hatte, war fixed poiint support nur für diverse andere emulationen implementiert, NICHT jedoch für das V.29 (??) oder eben das was für Faxe verwendet wird! Deswegen habe ich ja begonnen die fastfp library zu schreiben, mit dem ziel ohne große spandsp änderungen das ding mal mit festkomma zahlen arbeiten zu lassen. das problem ist nur, dass das so nicht möglich ist, weil ein algo. der auf gleitkomma ausgelegt ist, einfach mal nicht einfach so mit festkomma arbeitet ohne am algorithmus änderungen vorzunehemen. machbar sollte es aber sein... das schwierige ist hier zu wissen in welchem bereich sich die variablen befinden können und sie dementsprechend zu skalieren........ dazu müsste man schon sehr gut vertraut mit der modulation sein und den spandsp code sehr gut kennen

PPS: Zu Frameslips... so wie ich das im spandsp faq gesehen hab, ist das der fall wenn sender und empfänger um ein einziges sample auseinander sind? wenn es denn so wäre, dann könnten wir da aber gar nichts dagegen tun (zumindest auf direktem wege). wenn uns ein sample fehlt, dann liegt das erstmal am capi, dass uns eines zu wenig liefert. sollte aber doch nicht vorkommen, da die daten ja digital vom isdn netz kommen und nicht mehr gesampelt werden müssen (denn sonst könnte es ja zu einem clockdrift kommen). was im spandsp faq steht (link von bodega), mit timing problemen bezieht sich nur auf das telefonnetz und zwar wenn zwischen analog und digital konvertiert wird. solange wir die daten nur digital von einer fbox zur anderen übertragen, über ein deutsches netz, dann sollte es vom netz keine frame-slips geben. es liegt somit alles an der box und den programmen.
 
Zuletzt bearbeitet:
Das Speichern einer Datei ist sicher eine Erklärung für den erhöhten CPU-Bedarf. Allerdings wird die Datei erst gespeichert, wenn die Seite vollständig ist. Bei längeren Faxe bricht aber häufig die Übertragung schon während der Seite ab, das kann also nicht die einzige Erklärung sein.

Die Komprimierung der TIFF-Dateien ist immer FAX G3. Man könnte versuchen, die TIFF-Dateien erst einmal unkomprimiert zu speichern und erst nach Empfang zu komprimieren. Das würde ich aber erst versuchen, wenn der Empfang einer langen Seite zuverlässig funktioniert, weil erst dann feststeht, daß das Problem durch die anschließende Komprimierung verursacht wird und nicht durch etwas anderes.

Mit dem fixed-point hast Du recht. Ich habe es zwar aktiviert, aber es ist zum einen noch relativ neu, und betrifft nicht den Fax-Empfang, so daß man sich davon vorerst nicht viel versprechen sollte.

Die meiste Zeit wird in der Fließkomma Emulation verbraucht, von daher ist fixed-point sicher der richtige Weg, wenn es fertig ist. Allerdings verstehe ich die verwendeten Berechnungen nicht so genau, daß ich daran selbst etwas ändern will.

Ich vermute das Problem ist eine Kombination der geringen CPU-Leistung der Box und der CAPI. Von einem PC aus über Remote-CAPI funktioniert es bei mir recht gut. Die Daten werden dabei über die CAPI der Box übertragen, also scheint die CAPI-Ansteuerung soweit zu funktionieren. Der PC hat mit den Fließkomma Berechnungen kein Problem und schafft das locker in der zur Verfügung stehenden Zeit.

Wenn ich einen Sender und einen Empfänger direkt ohne CAPI Daten austauschen lasse, funktioniert es. In diesem Fall gibt es natürlich keine Zeitbegrenzung, wobei die tatsächlich verbrauchte Zeit insgesamt kleiner ist als die simulierte Übertragungsdauer. Das heißt leider nicht, daß dies auch für jeden einzelnen Frame zutrifft.

An sich sollte es keine Frame-Slips geben, aber bei der Übertragung über CAPI verliert der Empfänger meistens irgendwann die Synchronisation. Ich überlege gerade, wie man am Besten die CAPI Übertragung testen kann, erst einmal ohne FAX-Dekodierung.

Außerdem könnte man das Senden und Empfangen auf zwei Threads aufteilen. Die Frage ist aber, ob man damit nicht im Endeffekt nur einen höheren Overhead produziert.

Edit:
Ich habe mal einfach eine Test-Datei über CAPI versendet, also nur Datei direkt lesen, an CAPI übergeben, auf der anderen Seite empfangen und speichern, ohne Signalverarbeitung. Die CPU-Auslastung liegt dabei unter 5%.

Bei bisher drei Versuchen habe ich dabei folgendes Ergebnis:
Am Anfang der empfangenen Datei stehen ca. 1290 Bytes Unsinn vor den zu empfangenen Daten. Das ist nicht weiter schlimm, hätte ich aber beim ISDN nicht erwartet.
In jeder der drei empfangen Dateien steht genau einmal an unterschiedlicher Stelle ein Block von genau 32 Bytes Unsinn (0xAA), die Nutzdaten dahinter sind verschoben. Das ist genau so ein Fall, der nicht auftreten darf. Ich muß jetzt noch herausfinden, ob es am Sender (AVM ISDN Karte) oder am Empfänger (AVM Box) liegt.
 
Zuletzt bearbeitet:
ich finde es interessant, dass pro Datei genau ein solcher Block auftritt... hast du schonmal probiert die Dateigröße zu variieren bzw. andere Datein zu nehmen, oder Testmuster wie 0xFF 0x00 ... zu generieren? versendest du die Datei euf einmal, oder gibts für jede Datei eine eigene Verbindung? Probier mal eine Datei zu senden, die so groß ist wie die drei, und schau ob dann drei Blöcke drin sind.

EDIT: @Ralf: hast du zufällig eine Idee wie man in C (oder zur Not Mipsel Assembler) möglichst effektiv herausfinden kann wieviele Nuller bzw. einser am Anfang einer 32-bit Zahl stehen? Also die Position (von links, vom MSB) an der die erste 1 oder 0 auftritt ermitteln? Mir fällt nur ein eine while schleife zu machen und solange zu verschieben bis die erste 1 oder 0 am msb steht, oder eben jedes Bit zu testen bis man die 1 oder 0 findet... braucht dann im Worst case 16 cpu zyklen... (geht hier um eine alternative fließkomma implementierung.. ;-) )
 
Meine Test-Datei ist 1MB groß und hat schon ein Test-Muster 0-1-2-3 usw., damit konnte ich ja herausfinden, daß die Störung eingefügt ist und nicht einen Teil der Daten überschreibt. Ich hatte die Datei auf einen USB-Stick geschrieben, der sollte ja wohl für ISDN-Geschwindigkeit ausreichend sein. Ich versuche es aber mal über Netzwerk und mit einer größeren Datei. Da die Position der Störung verschieden war, halte ich es eher für Zufall, aber da es dreimal in der gleiche Größe aufgetreten ist, habe ich es mal festgehalten.

Nachtrag:
Ich habe eine 4MB Datei erstellt, von der Box an die Box gesendet, Datei jeweils über Netzwerk gelesen und geschrieben.
Die Datei des angerufenen Programms hat eine Störung von 414 Bytes Unsinn (nicht 0) mit einer Verschiebung um 320 Bytes, dann eine Störung von 348 Bytes mit einer Verschiebung von 256 Bytes, und dann noch etliche mehr von der Sorte. Die Datei, die das anrufende Programm empfangen hat, enthält "nur" drei Verschiebungen.
Bei einem Test auf einem PC werden die kompletten 4MBohne Störungen übertragen, in beide Richtungen.

Zu der anderen Frage:
Es geht Dir darum, die Mantisse zu normalisieren und Du brauchst dafür die Position der ersten 1? Geht es um die Addition, die Konvertierung von int nach float oder um etwas anderes?

So auf Anhieb fällt mir keine Lösung ein, die das in maximal 16 CPU Zyklen schafft. Wie machst Du das denn?
 
Zuletzt bearbeitet:
Ich habe so gut wie keine Ahnung von C, kann es bestenfalls ein bißchen lesen. Ich weiß auch nicht, wieviele Taktzyklen folgender Intervallschachtelungs-Algorithmus in C oder Assembler braucht - bitte selbst probieren. Folgendes Shell-Skript kannst Du mal auf der Box oder auf Deinem Linux-PC laufen lassen:
Code:
#!/bin/sh

x=$1
l=0; r=32; m=16; m_old=-1

while [ ! $m -eq $m_old ]; do
	echo "l=$l, r=$r  ->  m=$m"
	tmp=$((x>>m))
	if [ $tmp -eq 1 ]; then
		break
	elif [ $tmp -eq 0 ]; then
		r=$m
	else
		l=$m
	fi
	m_old=$m
	m=$(((l+r)>>1))
done

echo "Result: m=$m"

Es führt eine Intervallschachtelung durch, wie man es vom Zahlenraten kennt. In jedem Durchgang wird das Intervall fürs Auffinden des MSB (most significant bit) halbiert, indem entweder die linke (l) oder rechte (r) Grenze angepaßt wird. Hierbei ist m übrigens immer die Mitte des Intervalls. Sie berechnet sich durch
Code:
m = (l + r) / 2
bzw.
Code:
m = (l + r ) >> 1
, also auch hier wird ein Shift-Operator anstatt einer Division eingesetzt. Na ja, im Grunde ist es ja selbsterklärend, also mache ich es kurz: Das Ergebnis ist die die Nummer des MSB (Zählung beginnt bei 0).

Update: Ich habe eine Prüfung eingebaut, ob das MSB beim Raten zufällig getroffen wurde (dann ist das Ergebnis der Shift-Operation x>>m gleich 1), weil in diesem Fall die Schleife früher abbrechen kann - gut zu sehen im zweiten Beispiel hier:

Beispiele:
Code:
[B]$ ./divide.sh 1234567890[/B]
l=0, r=32  ->  m=16
l=16, r=32  ->  m=24
l=24, r=32  ->  m=28
l=28, r=32  ->  m=30
Result: m=30

[B]$ ./divide.sh 66666[/B]
l=0, r=32  ->  m=16
Result: m=16

[B]$ ./divide.sh 4[/B]
l=0, r=32  ->  m=16
l=0, r=16  ->  m=8
l=0, r=8  ->  m=4
l=0, r=4  ->  m=2
Result: m=2

[B]$ ./divide.sh 127[/B]
l=0, r=32  ->  m=16
l=0, r=16  ->  m=8
l=0, r=8  ->  m=4
l=4, r=8  ->  m=6
Result: m=6
 
Zuletzt bearbeitet:
Es ist klar, daß man mit einer binären Suche schneller zum Ziel kommt, als indem man nacheinander alle Positionen durchprobiert. Trotzdem braucht man für 32 Bit noch 5 Durchläufe (Logarithmus von 32 zur Basis 2). Wenn man unter 16 Zyklen bleiben will, sind das 3 Zyklen pro Durchlauf. Eine Verzweigung ist auch noch dabei, was zusätzliche Verzögerungen mit sich bringt.

Die Shift-Operation statt Division durch 2 bringt nicht viel. Ein vernünftiger Compiler merkt das selbst, und in einem Shell-Skript ist der Unterschied vernachlässigbar.

Deine Optimierung mit dem Test auf vorzeitigen Abbruch macht das Programm für einige Fälle schneller (wenn es früh abbricht), für andere Fälle langsamer (wenn der Fall spät auftritt und deswegen alle Schleifendurchläufe länger gebraucht haben). Es ist also auch noch wichtig, welche Verteilung der Eingabewerte man erwartet.

Wenn es zum Beispiel um die Normalisierung nach einer Addition geht, lohnt sich die ganze Mühe nicht, weil in den meisten Fällen nur um 1-2 Bit geschoben werden muß. Das geht dann in den meisten Fällen schneller mit einer einfachen Schleife als mit einer ausgefeilten Suche.
 
RalfFriedl schrieb:
Zu der anderen Frage:
Es geht Dir darum, die Mantisse zu normalisieren und Du brauchst dafür die Position der ersten 1? Geht es um die Addition, die Konvertierung von int nach float oder um etwas anderes?

So auf Anhieb fällt mir keine Lösung ein, die das in maximal 16 CPU Zyklen schafft. Wie machst Du das denn?

Ja genau, es geht ums normalisieren der Mantisse. Bzw. ich möchte kein echtes Floating Point implementieren, bei dem die Mantisse immer normalisiert ist und zusammen mit dem Exponenten in 32 bit verpackt ist. Stattdessen verwende ich 16bit Mantisse und 8 bit Exponent (auf kosten der Genauigkeit). Die Mantisse ist einfach ein int16 (a) und der Exponent (b) auch ein signed char. Die Zahl ergibt sich ja dann immer zu a*2^b Wenn ich jetzt multipliziere dann werden die Mant. multipliziert also a1*a2, dabei kommen dann 32 bit raus, die ich solange nach rechts schieben muss bis sie in die unteren 16 bit passen (deswegen max. 16 shifts...).
Die Methode mit der Intervallschachtelung klingt gut.... nur ob es weniger zyklen sind? also pro iteration: 1x shift, 2x test (ob hi word = 0 und gleichzeitig wir aber nicht zu weit geschoben haben), shift counter anpassen.. macht 4 operationen (im idealfall). die brute force methode pro iteration: 1x shift, 1x test, 1x counter anpassen. also nur 3 ops. wenn man natürlich durch die iv-schachtelung weniger iterationen braucht, dann lohnt es sich.. hmmmm.. ich werde drüber nachdenken. es sollte also mit max. ld(n) iterationen bei max. shift um n bits gehen...

EDIT: zu 16 zyklen.. ich meinte natürlich 16 iterationen und nicht 16 zyklen...!! sorry...
 
Ist mir auch klar, daß ein Compiler das optimiert mit der Division durch 2, bin ja auch nicht auf der Brennsuppe daher geschwommen. Auch die anderen Argumente sind einleuchtend. Das ist ein Shell-Skript(!!), welches sozusagen das Vorgehen im Pseudo-Code zeigen sollte. Wenn jemand in Assembler direkt programmiert (dann wird kein Compiler eingesetzt), ist es schon ein Unterschied, ob man SHR oder DIV schreibt, es sei denn, man hat für den Assembler auch noch einen Optimierungsschritt vor dem eigentlichen Übersetzen in Maschinencode, daher wies ich extra darauf hin.

Gibt es denn in C-Standardbibliotheken keinen Befehl, der für jede Plattform optimiert ist und das MSB direkt liefert?

Laien-Frage: Wieso erwähnst Du denn immer 16 Zyklen? Was hat es mit der Zahl auf sich? Wenn Du das erklärt hättest - vielleicht habe ich es auch verpaßt, weil ich den Thread nicht genau verfolge - hätte ich das Skript vielleicht gar nicht "eingereicht". Edit: Erledigt, hab's in #53 gefunden.

P.S.: Da hier ja sowieso das Rad neu erfunden werden soll, um der Fritz!Box das Faxen zu ermöglichen, will vielleicht jemand das lesen: http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?tp=&arnumber=614901&isnumber=13407. Kostet $35, falls Ihr nicht zufällig IEEE-Mitgleider seid.
 
Zuletzt bearbeitet:
@kriegaex
Ich wollte nichts unterstellen.

GCC hat die Funktion __builtin_clz(). Diese Funktion gibt die Anzahl der 0-Bits von oben zurück. (31 - __builtin_clz (x)) wäre also die gesuchte Bit-Position, wobei x nicht 0 sein sollte. Leider ist die Implementierung dieser Funktion auf einer MIPS-CPU nicht übermäßig effizient.

@florixyz
Geht es Dir dabei um den Fax-Empfang oder um eine andere Anwendung? 16 Bit hört sich etwas wenig an, zumal da noch das Vorzeichen weggeht und die implizite 1 dann ja auch nicht mit dabei ist.

Erwartetst Du, daß die Eingabewerte "fast" normalisiert sind, also ein größerer Teil der 16 Bit auch genutzt ist? Im anderen Fall wäre sowieso nicht mehr viel Genauigkeit übrig.

Wenn wir davon ausgehen, das typischerweise mindestens 12 Bit genutzt sind, wird das Ergebnis meistens mindestens 24 Bit enthalten. Wie ich ohne schon geschrieben habe, lohnt es sich zum Beispiel bei einer Addition normalisierter Zahlen nicht, eine aufwendige Suche zu betreiben, weil in den meisten Fälle nur eine kleine Zahl von Schiebeoperationen nötig sind.

Code:
res = XXX; exp = YYY;
if (res > 1 << (16 + 8))
  res >>= 8, exp += 8;
if (res > 1 << (16 + 4))
  res >>= 4, exp += 4;
if (res > 1 << (16 + 2))
  res >>= 2, exp += 2;
if (res > 1 << (16 + 1))
  res >>= 1, exp += 1;

Damit bekommst Du den Wert res soweit herunter geschoben, daß die 1 genau im Bit 16 steckt. Wenn man etwas erweitert ("16+" wegläßt, dafür noch ein Schritt mit 16 statt 8), kann man damit auch den allgemeinen Fall 32-Bit Zahl lösen. Eine Schleift statt der nacheinander geschriebenen Anweisungen ist nicht sinnvoll, wenn Du auf Geschwindigkeit aus bist. Es würde noch zusätzliche Tests und Verzweigungen und Berechnungen benötigen. Ich fürchte, das kommt auch nicht unter die gewünschten 16 Taktzyklen, aber zumindest in die Nähe. Ich schätze mal 4-6 Zyklen pro Schritt, wenn der Complier gut ist, also 16-24 insgesamt bei 4 Schritten.
 
Mir geht es um den Fax-Empfang. Ich hatte schonmal versucht (erfolgreich), die mul, div, cos, sin, etc. operationen in spandsp v.29 durch operationen aus einer eigenen softfloat library (fastfp, siehe alter thread) zu ersetzen, was aber nicht den erwünschten performance gewinn brachte, da ja die gcc float emulation auch schon sehr effektiv zu sein scheint.

das mit dem _builtin_clz hört sich interessant an. warum ist das auf Mips nicht effektiv? Ich hatte so im Hinterkopf, dass Mips eine art clz befehl in seinem instuktionssatz hat, der auch nur einen zyklus braucht. den könnte doch der gcc dafür verwenden..?
 
Holen Sie sich 3CX - völlig kostenlos!
Verbinden Sie Ihr Team und Ihre Kunden Telefonie Livechat Videokonferenzen

Gehostet oder selbst-verwaltet. Für bis zu 10 Nutzer dauerhaft kostenlos. Keine Kreditkartendetails erforderlich. Ohne Risiko testen.

3CX
Für diese E-Mail-Adresse besteht bereits ein 3CX-Konto. Sie werden zum Kundenportal weitergeleitet, wo Sie sich anmelden oder Ihr Passwort zurücksetzen können, falls Sie dieses vergessen haben.