Sie sind nicht angemeldet.

sebi

Schüler

  • »sebi« ist der Autor dieses Themas

Beiträge: 109

Beruf: Software-Entwickler

  • Nachricht senden

21

Sonntag, 27. November 2022, 00:08

MacPaint 1

Liebe Freunde!
Ich hoffe (nicht), daß Ihr Euch vor lauter Spannung und Ungeduld die Nägel blutig gekaut und die Neu-laden-Schaltfläche des Browsers bis auf den untersten Pixel abgenutzt habt! Für den letzten Fall bliebe dann nur, das Browser-Fenster zu verschieben oder besser gleich einen neuen Monitor zu holen.

Wie geht die Reise weiter? Sie geht zurück! Zurück zum Ursprung, wo alles begann. So wie Antäus (für die Kreta-Liebhaber Ανταιος) immer wieder neue Kraft von seiner Mutter erhielt, widmen auch wir uns zur Stärkung der Mutter aller Bildformate und zugleich dem Format, das dies Programm gebar – MacPaint.
Dies war das erste kodierte Bildformat. Entsprechend Patina hatten die Routinen angesetzt. Ich brachte sie auf den neuesten Stand und polierte auch gleich noch die Darstellung der MacPaint-Pinselmuster. Hier hatte noch die Darstellung als 1-Bit-Bitmap gefehlt.

Exkurs: In einer 1-Bit-Bitmap kodiert ein Bit ein Pixel. Und ein Byte damit acht Pixel. So ein MacPaint-Muster ist acht Pixel breit. Also ein Byte groß. Man braucht also nur das Muster-Byte zur Anzeige in die Bitmap übertragen. So weit, so einfach. Doch erst mit einem Rahmen werden die Muster schön. Und kompliziert:
  • Denn nun beginnt das Bild mit einem Rahmen. ist er ein Pixel breit, benötigt er ein Bit.
  • Somit bleiben für das folgende Muster nur sieben Bit. Diese müssen aus dem Muster-Byte extrahiert und in das erste Bild-Byte übertragen werden.
  • Das achte Muster-Bit sollte jetzt nicht großzügig entsorgt, sondern als erstes Bit in nächste Bild-Byte eingesetzt werden.
  • Dort folgt dann als zweites Bit das neue Rahmen-Bit. Somit bleiben für das nächste Muster nur noch sechs Bit.
  • Also muß das Muster-Byte 6:2 geteilt und in zwei Byte untergebracht werden. Worauf dann der nächste Rahmen ...

Fast berstend vor frisch gezapfter Kraft tippte ich rastlos weiter und schuf nun endlich auch den Optionsdialog für die MacPaint-Pinselmuster-Darstellung. Analog zu den Farbpaletten gestattete ich auch hier einen hellen Rahmen, der natürlich auch im Code umgesetzt sein wollte.

Die Beispiele zeigen eine Pinselmuster-Palette in der Standardansicht und in einer individuellen Variante zusammen mit dem Optionsdialog.

Wir werden dann noch etwas bleiben, bei Muttern. Und futtern. Und mit dieser Kraft noch richtig auf die Torte hauen!
»sebi« hat folgende Bilder angehängt:
  • Pinselmuster-normal.png
  • Pinselmuster mit Optionen.png

sebi

Schüler

  • »sebi« ist der Autor dieses Themas

Beiträge: 109

Beruf: Software-Entwickler

  • Nachricht senden

23

Dienstag, 29. November 2022, 16:30

MacPaint 2

Während ich mir so einige MacPaint-Bilder genüßlich betrachtete, stellte ich fest, daß der neue Code zwar schön, aber auch recht langsam war. Also warf ich meinen PPP (pompösen Programmierplan) etwas um und begab mich auf Optimimierungsmission. Die interessanten Ergebnisse möchte ich hier teilen und darauf hinweisen, daß der heutige Beitrag etwas code-lastiger ausfallen wird.

Zum besseren Verständnis der nachfolgenden Ausführungen hier einige Hinweise zum Aufbau von MacPaint-Bildern und dem ursprünglichen Darstellungs-Code:
  • Die typischen MacPaint-Bilder, die mir vorliegen, zeigen kein Bild über ihre gesamte Größe, sondern eher ein kleineres Bild in ca. der Mitte und rundherum viel weißen Raum. So ein Bild nahm ich mir als Testobjekt.
  • MacPaint-Bilder haben eine feste Größe von 576 x 720 Pixeln und eine Farbtiefe 1 Bit. Es sind also Schwarz-Weiß-Bilder.
  • Jede Zeile ist mit dem PackBit-Algorithmus komprimiert. Dieser unterteilt die Bilddaten in einzelne Pakete.
  • Es gibt zwei Sorten Pakete. Der Typ „Wiederholung“ sagt: Wiederhole das nächste Byte n-mal! Der Typ „Übernehmen“ möchte: Übernimm die folgenden n Byte!
  • Im Wesentlichen geht das Programm so vor: Es liest Daten aus der Datei. Es entpackt jedes Paket und schreibt jedes der entstandenen Bytes mit dem Befehl poke ins VRAM, einem R-Basic-Puffer (hierbei muß eine Speicheradresse angegeben werden). Ist eine Bildzeile komplett, wird sie mittels peekline in das entstehende Bild übertragen.
  • Hinweis: Die gezeigten Code-Beispiele enthalten keinen vollständigen und korrekten Code, sondern sind eine Mischung aus R-Basic- und Pseudo-Code, der die Wahrscheinlichkeit der Verständlichkeit auch für Nichtprogrammierer erhöhen soll.

    Quellcode

    1
    2
    3
    4
    5
    6
    7
    8
    
    if wiederholungsmodus = true then byteValue = readNextByte()
    for n = 1 to anzahl
        if wiederholungsmodus = false then byteValue = readNextByte()
        poke byteValue, adresse
        adresse = adresse + 1
    
        if zeile = komplett then bitmap.peekline 0, zeile
    next n


So nahm das Fitness-Programm Mac-Rakete seinen Lauf:
  • 23,8 s benötigte das Programm initial, um das Bild darzustellen.
  • 20,0 s waren es nach der ersten Optimierung.
    Bislang wurde nach jedem ins VRAM geschriebenen Byte geprüft, ob das Bildzeilenende erreicht ist. Das ist aber nicht nötig, da MacPaint-Bilder zeilenweise kodiert sind. Eine Bildzeile endet daher nie in, sondern nur mit einer Kodierung. Daher verschob ich die Prüfung if zeile = komplett then hinter die Schleife, was immerhin (für eine einfache if-Prüfung!) 3,8 s und damit 16 % brachte.
  • 13,4 s waren es nur noch nach einer Schleifenaufteilung!
    Jetzt spendierte ich jedem der beiden Kodiermodi eine eigene Schleife. Im Wiederholungsmodus wird n-fach das gleiche Byte geschrieben. Wenn n nun eine gerade Zahl ist, lassen sich die Schleifendurchläufe und Schreiboperationen halbieren. Denn so läßt sich der Befehl doke verwenden, der zwei Byte auf einmal schreibt.

    Quellcode

    1
    2
    3
    4
    
    for n = 1 to anzahl / 2
        doke 2*byteValue, adresse
        adresse = adresse + 2
    next n

  • 13,0 s dauerte es noch nach dem nächsten Trick.
    Nun behandelte ich den Fall, daß die Wiederholungsanzahl eine ungerade Zahl ist. Dann wird zuerst ein einzelnes Byte geschrieben, wodurch eine gerade Anzahl noch zu schreibender Bytes übrigbleibt, die mit der soeben erstellten doke-Schleife abgearbeitet werden. Vor der Schleife aus dem vorherigen Punkt steht nun also:

    Quellcode

    1
    2
    3
    4
    5
    
    if anzahl = ungerade then
        poke byteValue, adresse
        adresse = adresse + 1
        anzahl = anzahl - 1
    end if

  • 11,3 s verstrichen noch, nachdem ich den Übernehmen-Modus ähnlich strukturiert hatte.
    Auch hier wird bei einer ungeraden Anzahl an Bytes erst eines geschrieben und dann werden die geraden in einer halbierten Schleife abgearbeitet. Hier müssen dann aber immer zwei neue Byte aus dem Puffer gelesen werden. Durch diesen etwas höheren Aufwand und weil wohl dieser Modus im Beispielbild seltener vorkommt, fällt die Zeitersparnis geringer als beim Wiederholungsmodus aus.
  • 8,8 s verblieben nur noch, nachdem das Programm gleich ganze Zeilen schreiben konnte.
    Da ein Großteil des Bildes aus weißen Zeilen besteht, dachte ich, ich könnte die 10-Sekunden-Marke knacken, wenn eine ganze Zeile mit einem Befehl geschrieben werden könnte! Da MacPaint-Bilder eine feste Größe haben, hat auch eine Bildzeile eine fixe Größe von 72 Byte. Dadurch konnte ich eine sog. Struktur anlegen, die aus 72 Byte mit jeweils dem Wert null besteht. Also einer weißen Zeile:

    Quellcode

    1
    2
    3
    4
    
    if anzahl = 72 then
        spoke struktur, adresse
        adresse = adresse + 72
    end if

    Das brachte zwar 2,5 s Sekunden und den einstelligen Bereich, aber insgeheim hatte ich mir sogar mehr erhofft. Und falls ein Bild lauter schwarze Zeilen haben sollte, profitiert es nicht davon.

Fazit: Durch die Anpassungen des Codes an die Eigenheiten der zu verarbeitenden Daten wurde etwas erreicht, was leicht widersprüchlich klingt: Es gibt mehr Code und der Code ist schneller. Die Reduzierung der Ausführungszeit auf ca. drei Achtel sind die Redundanzen aber wert, finde ich. So kann man noch begeisterter stundenlang MacPaint-Bilder anschauen :).

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »sebi« (Gestern, 11:03)


24

Gestern, 09:56

Toll Sebi! Ist richtig interessant zu lesen und bildhaft beschrieben. Bin schon gespannt, wie die Geschichte weitergeht. :thumbsup:
Bernd

sebi

Schüler

  • »sebi« ist der Autor dieses Themas

Beiträge: 109

Beruf: Software-Entwickler

  • Nachricht senden

25

Gestern, 13:38

MacPaint 2a oder Code-Optimierungen 2

Der letzte Beitrag wurde sehr gut angenommen – herzlichen Dank! – und unter der Hand bekam ich sogar Insider-Tips, was ich noch ausprobieren könnte, um der Mac-Rakete noch etwas Extraschub zu verpassen, damit sie sich vielleicht sogar asymptotisch der Photonengeschwindigkeit annähert. Neue Universen kämen dann in Reichweite!

Aus dem geheimen Schreiben destillierte ich drei Ideen, die ich hier ausprobieren möchte:
  • Nicht direkt in das R-Basic-VRAM mit poke und doke schreiben, sondern erstmal in eine Struktur schreiben und diese dann auf einen Schlag ins VRAM übertragen.
  • Die Zählvariablen nicht manuell, sondern mittels der R-Basic-Befehle incr und decr rauf- bzw. runterzählen.
  • Das Schreiben der Bytes mit dem Aktualisieren der Zählvariablen zu einer Befehlszeile zusammenfassen. Das geschieht in R-Basic mittels Doppelpunkt in der Form befehl1 : befehl2.

Zuerst ergänzte ich den gestrigen Programm-Code um eine neue Variante, bei der die entpackten Bytes nicht direkt ins VRAM, sondern in eine Struktur geschrieben werden. Ist die Zeile komplett, wird die Struktur mittels spoke ins VRAM übertragen und von dort in die Bitmap.

Quellcode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
if wiederholungsmodus = true then
    if anzahl = 72 and byteValue = 0 then
        struktur_zeile = struktur_weiße_Zeile
        adresse = adresse + 72
    else
        for n = 1 to anzahl
            struktur_zeile(adresse) = byteValue
            adresse = adresse + 1
        next n
    end if
else 
    for n = 1 to anzahl
        byteValue = readNextByte()
        struktur_zeile(adresse) = byteValue
        adresse = adresse + 1
    next n
end if

if zeile = komplett then
    spoke 0, struktur_zeile
    bitmap.peekline 0, zeilennummer
end if

Dieser kurz-knackige Code gefiel mir so gut, daß ich ihn auch (zwecks erweiterter Vergleichbarkeit) für eine weitere, reine poke-Variante übernahm.

Quellcode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
if wiederholungsmodus = true then
    if anzahl = 72 and byteValue = 0 then
        spoke adresse, struktur_weiße_Zeile
        adresse = adresse + 72
    else
        for n = 1 to anzahl
            poke adresse, byteValue
            adresse = adresse + 1
        next n
    end if
else 
    for n = 1 to anzahl
        byteValue = readNextByte()
        poke adresse, byteValue
        adresse = adresse + 1
    next n
end if

if zeile = komplett then bitmap.peekline 0, zeilennummer

Ich entschied mich, die benötigte Zeit in sechs Szenarien zu messen: in der reinen poke-, der optimierten poke/doke- und der Strukturvariante. Und jeweils mit der weißen Bildzeile auf einen Schlag (siehe gestern) und einmal ohne, weil dieser Trick nicht neutral, sondern stark vom Bildinhalt abhängig ist.
Die unter unbestechlichen Zeugen (einer kleiner Statue) festgestellten, quasi amtlichen Ergebnisse lauten:
  • Variante pures poke: 16,7 s
  • Variante poke/doke: 12,2 s
  • Variante Struktur: 17,2 s
  • Variante pures poke mit weißer Zeile: 10,2 s
  • Variante poke/doke mit weißer Zeile: 9,1 s
  • Variante Struktur mit weißer Zeile: 10,3 s

Diese Ergebnisse würde ich so interpretieren:
  • Das Lesen und Schreiben von Strukturen ist in etwa zeitäquivalent zum Lesen und Schreiben des VRAMs.
    Die VRAM-Variante hat dabei den Vorteil – der ihr die entscheidende Nasenspitze verlängert haben könnte –, daß die Daten gleich am gewünschten Ort sind, während die Struktur noch mit einem zusätzlichen Befehl ins VRAM übertragen werden muß.
  • Es lohnt sich, Schleifendurchläufe zu minimieren. Deswegen ist die doke-Variante um Etliches schneller. Deswegen hat die weiße Bildzeile einen großen Effekt bei den anderen beiden Varianten, weil hier die hohe Schleifenzahl drastisch verringert wird.
    Deswegen waren es gestern auch 8,8 s statt der heutigen 9,1 s, weil es da noch zusätzlichen Code – den ich nonchalant verschwieg – für den Fall anzahl = 8 gab. Dort stand dann keine Schleife, sondern vier doke-Befehle. Das hatte ich schon früher festgestellt, daß sich mehr Code oft lohnt, wenn er Schleifen verkürzt.

Weiter geht’s im nächsten Teil!

Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von »sebi« (Gestern, 14:46)


26

Gestern, 14:22

Ich finde das auch sehr spannend und toll geschrieben. Sei nicht traurig wenn nicht jedes Mal Feedback kommt, ich lese trotzdem mit!
Bye,
MeyerK

sebi

Schüler

  • »sebi« ist der Autor dieses Themas

Beiträge: 109

Beruf: Software-Entwickler

  • Nachricht senden

27

Gestern, 14:32

MacPaint 2b oder Code-Optimierungen 3

Doch kommen wir nun im zweiten Teil zu den anderen beiden Vorschlägen. Die hatte ich bislang selber noch nicht ausprobiert und war auf die Ergebnisse gespannt. Und wurde sehr überrascht!

Der Code wurde in denselben sechs Szenarien wie oben getestet. Zuerst änderte ich die Zählervariablenberechnung:

Quellcode

1
2
3
4
5
6
7
poke adresse, byteValue
adresse = adresse + 1

//wurde geändert zu:

poke adresse, byteValue
incr adresse

Im nächsten Testdurchlauf faßte ich die beiden Code-Zeilen zusammen. So werden sie von R-Basic auf einmal geladen und direkt hintereinander ausgeführt. Es entfällt also ein Ladeschritt.

Quellcode

1
2
3
4
5
6
poke adresse, byteValue
incr adresse

//wurde geändert zu:

poke adresse, byteValue : incr adresse

Nach zahllosen Versuchsreihen, durchgearbeiteten Nächten bei Vollmond, Wolfsgeheul und sorgenvollem Blick zum Kellerfenster mit dem rostig-wackligen Schloß ergaben sich diese Zahlenreihen:
  • Variante pures poke: 16,7 s — 15,2 s — 14,4 s
  • Variante poke/doke: 12,2 s — 11,5 s — 11,1 s
  • Variante Struktur: 17,2 s — 15,6 s — 14,9 s
  • Variante pures poke mit weißer Zeile: 10,2 s — 9,7 s — 9,5 s
  • Variante poke/doke mit weißer Zeile: 9,1 s — 8,8 s — 8,7 s
  • Variante Struktur mit weißer Zeile: 10,3 s — 9,8 s — 9,6 s

In einer Reihe stehen dabei von links nach rechts: Zeit für adresse = adresse + 1 — Zeit für incr adresse — Zeit für : incr adresse.

Und nun ist wieder Zeit für einige conclusiones sapientes:
  • Die kleinen Code-Änderungen bringen überraschend deutliche Ergebnisse!
  • Dabei ist der Effekt von incr/decr in etwa doppelt so groß wie der des Zusammenfassens in einer Zeile.
  • Auch hier gilt (logischerweise): Je höher die Schleifenzahl, um so größer die meßbare Ersparnis.

Fazit: Es lohnt sich auf jeden Fall, mal in seiner Routine innezuhalten und neue Lösungswege auszuprobieren. Herzlichen Dank für die Tips also! Von nun an werde ich möglichst die incr/decr-Funktionen nutzen und auch, wo es paßt, zwei Befehle in einer Zeile zusammenfassen. Bei der Bilderstellung werde ich wohl bei der VRAM-Methode bleiben. Da dräut aber schon die erste Ausnahme am Horizont: Bei einem der nächsten Unterprojekte kann es temporär Pixel mit negativen Werten geben. Die lassen sich im VRAM mit seinem Byte-Datentyp aber nicht abbilden. Also muß ich zum Array oder zur Struktur greifen. Da sich ein Array aber nicht so einfach ins VRAM kopieren läßt, wird hier wohl doch die Struktur zum Einsatz gelangen!

Ich hoffe, Ihr konntet von diesen technischen Testreihen auch Einiges mitnehmen. Am besten greift Ihr jetzt selber zu R-Basic und probiert es in Eurem neuen, eigenen Programm aus :thumbup: !

sebi

Schüler

  • »sebi« ist der Autor dieses Themas

Beiträge: 109

Beruf: Software-Entwickler

  • Nachricht senden

28

Gestern, 14:58

Ich finde das auch sehr spannend und toll geschrieben. Sei nicht traurig, wenn nicht jedes Mal Feedback kommt, ich lese trotzdem mit!

Danke :) :) !

Bin nicht mehr traurig, weiß ja jetzt, daß viele/alle mitlesen :P . Und habe noch zwei weitere Strategien:
  • Wollte schon immer mal einen Blog schreiben. Wußte aber nie so recht worüber. Hier hat sich nun ein Thema ergeben, das sogar ständig selber Nachschub liefert!
  • Beim Schreiben stelle ich mir einfach vor, draußen wartet ein unersättliches Millionenpublikum auf die neuesten Nachrichten und möchte unterhalten werden.

Und so macht es derzeit verdammt viel Spaß!
Salute!

PS: Ab und zu eine Rückmeldung erfreut natürlich trotzdem das Herz :)

Thema bewerten