Schlafsortierung

Schlafsortierung – Sleep Sort, ein weiterer Vertreter deterministischer seltsamer Sortieralgorithmen.

Es funktioniert so:

  1. Durchläuft eine Liste von Elementen
  2. Für jede Schleife wird ein separater Thread gestartet
  3. Der Thread schläft für eine gewisse Zeit – Elementwert und Wertausgabe nach dem Ruhezustand
  4. Warten Sie am Ende der Schleife, bis der längste Ruhezustand des Threads abgeschlossen ist, und zeigen Sie die sortierte Liste an

Beispielcode für den Schlafsortierungsalgorithmus in C:

#include <stdlib.h>
#include <pthread.h>
#include <unistd.h>

typedef struct {
    int number;
} ThreadPayload;

void *sortNumber(void *args) {
    ThreadPayload *payload = (ThreadPayload*) args;
    const int number = payload->number;
    free(payload);
    usleep(number * 1000);
    printf("%d ", number);
    return NULL;
}

int main(int argc, char *argv[]) {
    const int numbers[] = {2, 42, 1, 87, 7, 9, 5, 35};
    const int length = sizeof(numbers) / sizeof(int);

    int maximal = 0;
    pthread_t maximalThreadID;

    printf("Sorting: ");
    for (int i = 0; i < length; i++) { pthread_t threadID; int number = numbers[i]; printf("%d ", number); ThreadPayload *payload = malloc(sizeof(ThreadPayload)); payload->number = number;
        pthread_create(&threadID, NULL, sortNumber, (void *) payload);
        if (maximal < number) {
            maximal = number;
            maximalThreadID = threadID;
        }
    }
    printf("\n");
    printf("Sorted: ");
    pthread_join(maximalThreadID, NULL);
    printf("\n");
    return 0;
}

In dieser Implementierung habe ich die Funktion usleep für Mikrosekunden verwendet, wobei der Wert mit 1000 multipliziert wurde, d. h. in Millisekunden.
Zeitliche Komplexität des Algorithmus – O(sehr lang)

Links

https://gitlab.com/demensdeum /algorithms/-/tree/master/sortAlgorithms/sleepSort

Quellen

https://codoholicconfessions.wordpress. com/2017/05/21/strangest-sorting-algorithms/
https://twitter.com/javascriptdaily/status/856267407106682880?lang=en
https://stackoverflow.com/questions/6474318/what-is-the-time-complexity-of-the-sleep-sort

Stalin-Sorte

Stalin Sort – Sortieren durch, einer der Sortieralgorithmen mit Datenverlust.
Der Algorithmus ist sehr produktiv und effizient, Zeitkomplexität O(n).

Es funktioniert so:

  1. Durchlaufen Sie das Array und vergleichen Sie das aktuelle Element mit dem nächsten
  2. Wenn das nächste Element kleiner als das aktuelle ist, entfernen Sie es
  3. Als Ergebnis erhalten wir ein sortiertes Array in O(n)

Beispiel für die Ausgabe des Algorithmus:

Gulag: [1, 3, 2, 4, 6, 42, 4, 8, 5, 0, 35, 10]
Element 2 sent to Gulag
Element 4 sent to Gulag
Element 8 sent to Gulag
Element 5 sent to Gulag
Element 0 sent to Gulag
Element 35 sent to Gulag
Element 10 sent to Gulag
Numbers: [1, 3, 4, 6, 42]
Gulag: [2, 4, 8, 5, 0, 35, 10]

Python 3-Code:

gulag = []

print(f"Numbers: {numbers}")
print(f"Gulag: {numbers}")

i = 0
maximal = numbers[0]

while i < len(numbers):
    element = numbers[i]
    if maximal > element:
        print(f"Element {element} sent to Gulag")
        gulag.append(element)
        del numbers[i]
    else:
        maximal = element        
        i += 1

print(f"Numbers: {numbers}")
print(f"Gulag: {gulag}")

Zu den Nachteilen gehört der Datenverlust, aber wenn wir uns einer utopischen, idealen, sortierten Liste in O(n) nähern, wie sonst?

Links

https://gitlab.com/demensdeum /algorithms/-/tree/master/sortAlgorithms/stalinSort

Quellen

https://github.com/gustavo-depaula/stalin-sort
https://www.youtube.com/shorts/juRL-Xn-E00
https://www.youtube.com/watch?v=L78i2YcyYfk

Auswahlsortierung

Auswahl sortieren – Auswahlsortieralgorithmus. Was wählen? Aber die Mindestanzahl!!!
Zeitliche Komplexität des Algorithmus – O(n2)

Der Algorithmus funktioniert wie folgt:

  1. Wir gehen das Array in einer Schleife von links nach rechts durch, merken uns den aktuellen Startindex und die Nummer am Index, nennen wir es Nummer A
  2. Innerhalb der Schleife führen wir einen weiteren aus, um von links nach rechts zu gehen und nach etwas zu suchen, das kleiner als A ist
  3. Wenn wir die kleinere finden, merken wir uns den Index, jetzt wird die kleinere zur Zahl A
  4. Wenn die innere Schleife endet, tauschen Sie die Zahl am Startindex und die Zahl A aus
  5. Nachdem wir die obere Schleife vollständig durchlaufen haben, erhalten wir ein sortiertes Array

Beispiel für die Ausführung eines Algorithmus:

(29, 49, 66, 35, 7, 12, 80)
29 > 7
(7, 49, 66, 35, 29, 12, 80)
Round 1 ENDED
Round 2
(7, 49, 66, 35, 29, 12, 80)
49 > 35
35 > 29
29 > 12
(7, 12, 66, 35, 29, 49, 80)
Round 2 ENDED
Round 3
(7, 12, 66, 35, 29, 49, 80)
66 > 35
35 > 29
(7, 12, 29, 35, 66, 49, 80)
Round 3 ENDED
Round 4
(7, 12, 29, 35, 66, 49, 80)
(7, 12, 29, 35, 66, 49, 80)
Round 4 ENDED
Round 5
(7, 12, 29, 35, 66, 49, 80)
66 > 49
(7, 12, 29, 35, 49, 66, 80)
Round 5 ENDED
Round 6
(7, 12, 29, 35, 49, 66, 80)
(7, 12, 29, 35, 49, 66, 80)
Round 6 ENDED
Sorted: (7, 12, 29, 35, 49, 66, 80)

Ich habe keine Objective-C-Implementierung im Rosetta-Code gefunden , schrieb ich selbst:

#include <Foundation/Foundation.h>

@implementation SelectionSort
- (void)performSort:(NSMutableArray *)numbers
{
   NSLog(@"%@", numbers);   
   for (int startIndex = 0; startIndex < numbers.count-1; startIndex++) {
      int minimalNumberIndex = startIndex;
      for (int i = startIndex + 1; i < numbers.count; i++) {
         id lhs = [numbers objectAtIndex: minimalNumberIndex];
         id rhs = [numbers objectAtIndex: i];
         if ([lhs isGreaterThan: rhs]) {
            minimalNumberIndex = i;
         }
      }
      id temporary = [numbers objectAtIndex: minimalNumberIndex];
      [numbers setObject: [numbers objectAtIndex: startIndex] 
               atIndexedSubscript: minimalNumberIndex];
      [numbers setObject: temporary
               atIndexedSubscript: startIndex];
   }
   NSLog(@"%@", numbers);
}

@end

Собрать и запустить можно либо на MacOS/Xcode, либо на любой операционной системе поддерживающей GNUstep, например у меня собирается Clang на Arch Linux.
Скрипт сборки:

        main.m \
        -lobjc \
        `gnustep-config --objc-flags` \
        `gnustep-config --objc-libs` \
        -I /usr/include/GNUstepBase \
        -I /usr/lib/gcc/x86_64-pc-linux-gnu/12.1.0/include/ \
        -lgnustep-base \
        -o SelectionSort \

Links

https://gitlab.com/demensdeum/algorithms/-/tree/master/sortAlgorithms/selectionSort

Sources

https://rosettacode.org/wiki/Sorting_algorithms/Selection_sort
https://ru.wikipedia.org/wiki/Сортировка_выбором
https://en.wikipedia.org/wiki/Selection_sort
https://www.youtube.com/watch?v=LJ7GYbX7qpM

Zählsortierung

Zählsortierung – Zählsortieralgorithmus. Bezüglich? Ja! Einfach so!

Der Algorithmus umfasst mindestens zwei Arrays, das erste – Liste der zu sortierenden Ganzzahlen, zweite – ein Array der Größe = (maximale Anzahl – minimale Anzahl) + 1, das zunächst nur Nullen enthält. Als nächstes werden die Zahlen aus dem ersten Array aussortiert und das Zahlenelement wird verwendet, um einen Index im zweiten Array zu erhalten, der um eins erhöht wird. Nachdem wir die gesamte Liste durchgegangen sind, erhalten wir ein vollständig gefülltes zweites Array mit der Anzahl der Wiederholungen der Zahlen aus dem ersten. Der Algorithmus hat einen erheblichen Overhead – Das zweite Array enthält auch Nullen für Zahlen, die nicht in der ersten Liste enthalten sind, die sogenannten. Overhead aus dem Speicher

Nachdem wir das zweite Array erhalten haben, durchlaufen wir es und schreiben die nach Index sortierte Version der Zahl, wobei wir den Zähler auf Null dekrementieren. Ein Nullzähler wird zunächst ignoriert.

Ein Beispiel für den nicht optimierten Betrieb des Zählsortieralgorithmus:

  1. Eingabearray 1,9,1,4,6,4,4
  2. Dann ist das zu zählende Array 0,1,2,3,4,5,6,7,8,9 (Mindestzahl 0, Höchstzahl 9)
  3. Mit Gesamtzählern 0,2,0,0,3,0,1,0,0,1
  4. Gesamt sortiertes Array 1,1,4,4,4,6,9

Algorithmuscode in Python 3:


numbers = [42, 89, 69, 777, 22, 35, 42, 69, 42, 90, 777]

minimal = min(numbers)
maximal = max(numbers)
countListRange = maximal - minimal
countListRange += 1
countList = [0] * countListRange

print(numbers)
print(f"Minimal number: {minimal}")
print(f"Maximal number: {maximal}")
print(f"Count list size: {countListRange}")

for number in numbers:
    index = number - minimal
    countList[index] += 1

replacingIndex = 0
for index, count in enumerate(countList):
    for i in range(count):
        outputNumber = minimal + index
        numbers[replacingIndex] = outputNumber
        replacingIndex += 1

print(numbers)

Из-за использования двух массивов, временная сложность алгоритма O(n + k)

Ссылки

https://gitlab.com/demensdeum/algorithms/-/tree/master/sortAlgorithms/countingSort

Источники

https://www.youtube.com/watch?v=6dk_csyWif0
https://www.youtube.com/watch?v=OKd534EWcdk
https://en.wikipedia.org/wiki/Counting_sort
https://rosettacode.org/wiki/Sorting_algorithms/Counting_sort
https://pro-prof.com/forums/topic/%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC-%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8-%D0%BF%D0%BE%D0%B4%D1%81%D1%87%D0%B5%D1%82%D0%BE%D0%BC

Bogosort

Pseudosortierung oder Sumpfsortierung, einer der nutzlosesten Sortieralgorithmen.

Es funktioniert so:
1. Die Eingabe ist ein Array von Zahlen
2. Eine Reihe von Zahlen wird zufällig gemischt (shuffle)
3. Prüft, ob das Array sortiert ist
4. Wenn nicht sortiert, wird das Array erneut gemischt
5. All diese Aktionen werden wiederholt, bis das Array zufällig sortiert ist.

Wie Sie sehen können, ist die Leistung dieses Algorithmus schrecklich. Kluge Leute glauben, dass sogar O(n * n!) d. h. Es besteht die Möglichkeit, dass Sie viele Jahre lang beim Würfeln zum Ruhm des Gottes des Chaos stecken bleiben. Das Array wird nie sortiert, oder vielleicht wird es sortiert?

Implementierung

Um es in TypeScript zu implementieren, musste ich die folgenden Funktionen implementieren:
1. Mischen Sie ein Array von Objekten
2. Array-Vergleich
3. Generieren einer Zufallszahl im Bereich von Null bis zu einer Zahl (sic!)
4. Druckfortschritt, weil es scheint, dass das Sortieren endlos weitergeht

Unten finden Sie den TypeScript-Implementierungscode:

const randomInteger = (maximal: number) => Math.floor(Math.random() * maximal);
const isEqual = (lhs: any[], rhs: any[]) => lhs.every((val, index) => val === rhs[index]);
const shuffle = (array: any[]) => {
    for (var i = 0; i < array.length; i++) { var destination = randomInteger(array.length-1); var temp = array[i]; array[i] = array[destination]; array[destination] = temp; } } let numbers: number[] = Array.from({length: 10}, ()=>randomInteger(10));
const originalNumbers = [...numbers];
const sortedNumbers = [...numbers].sort();

let numberOfRuns = 1;

do {
    if (numberOfRuns % 1000 == 0) {
        printoutProcess(originalNumbers, numbers, numberOfRuns);
    }
    shuffle(numbers);
    numberOfRuns++;
} while (isEqual(numbers, sortedNumbers) == false)

console.log(`Success!`);
console.log(`Run number: ${numberOfRuns}`)
console.log(`Original numbers: ${originalNumbers}`);
console.log(`Current numbers: ${originalNumbers}`);
console.log(`Sorted numbers: ${sortedNumbers}`);

Для отладки можно использовать VSCode и плагин TypeScript Debugger от kakumei.

Как долго

Вывод работы алгоритма:

src/bogosort.ts:1
Still trying to sort: 5,4,8,7,5,0,2,9,7,2, current shuffle 8,7,0,2,4,7,2,5,9,5, try number: 145000
src/bogosort.ts:2
Still trying to sort: 5,4,8,7,5,0,2,9,7,2, current shuffle 7,5,2,4,9,8,0,5,2,7, try number: 146000
src/bogosort.ts:2
Still trying to sort: 5,4,8,7,5,0,2,9,7,2, current shuffle 0,2,7,4,9,5,7,5,8,2, try number: 147000
src/bogosort.ts:2
Still trying to sort: 5,4,8,7,5,0,2,9,7,2, current shuffle 5,9,7,8,5,4,2,7,0,2, try number: 148000
src/bogosort.ts:2
Success!
src/bogosort.ts:24
Run number: 148798
src/bogosort.ts:25
Original numbers: 5,4,8,7,5,0,2,9,7,2
src/bogosort.ts:26
Current numbers: 5,4,8,7,5,0,2,9,7,2
src/bogosort.ts:27
Sorted numbers: 0,2,2,4,5,5,7,7,8,9

Для массива из 10 чисел Богосорт перемешивал исходный массив 148798 раз, многовато да?
Алгоритм можно использовать как учебный, для понимания возможностей языка с которым предстоит работать на рынке. Лично я был удивлен узнав что в ванильных JS и TS до сих пор нет своего алгоритма перемешивания массивов, генерации целого числа в диапазоне, доступа к хэшам объектов для быстрого сравнения.

Ссылки

https://gitlab.com/demensdeum/algorithms/-/tree/master/sortAlgorithms/bogosort
https://www.typescriptlang.org/
https://marketplace.visualstudio.com/items?itemName=kakumei.ts-debug

Источники

https://www.youtube.com/watch?v=r2N3scbd_jg
https://en.wikipedia.org/wiki/Bogosort

GoF-Muster

Liste der Gang-of-Four-Muster – Die gleichen Muster, die dazu führen können, dass Sie bei einem Vorstellungsgespräch scheitern.

Generative Muster

Strukturelle Muster

Verhaltensmuster

Musterinterpreter

Was ist enthalten

Das Interpreter-Muster bezieht sich auf Verhaltensentwurfsmuster. Mit diesem Muster können Sie Ihre eigene Programmiersprache implementieren, indem Sie mit einem AST-Baum arbeiten, dessen Eckpunkte terminale und nicht-terminale Ausdrücke sind, die die Interpret-Methode implementieren, die die Funktionalität der Sprache bereitstellt.

  • Terminalausdruck – zum Beispiel die Zeichenfolgenkonstante – “Hallo Welt”
  • Nicht-terminaler Ausdruck – zum Beispiel Print(“Hello World”), enthält Print und ein Argument aus dem Terminalausdruck “Hello World”

Was ist der Unterschied? Der Unterschied besteht darin, dass die Interpretation bei terminalen Ausdrücken endet, bei nicht-terminalen Ausdrücken jedoch ausführlich über alle eingehenden Eckpunkte/Argumente hinweg fortgesetzt wird. Wenn der AST-Baum nur aus nicht-terminalen Ausdrücken bestünde, würde die Anwendung niemals abgeschlossen werden, weil Für jeden Prozess ist eine gewisse Endlichkeit erforderlich. Diese Endlichkeit ist das, was terminale Ausdrücke ausmachen. Sie enthalten normalerweise Daten, zum Beispiel Zeichenfolgen.

Ein Beispiel für einen AST-Baum finden Sie unten:


Dcoetzee, CC0, über Wikimedia Commons

Wie Sie sehen können, sind Terminalausdrücke konstant und variabel, nichtterminale Ausdrücke sind der Rest.

Was nicht enthalten ist

Die Interpreter-Implementierung umfasst nicht das Parsen der in den AST-Baum eingegebenen Sprachzeichenfolge. Es reicht aus, Klassen von Terminal- und Nicht-Terminal-Ausdrücken zu implementieren, Methoden mit dem Kontextargument am Eingang zu interpretieren, einen AST-Ausdrucksbaum zu erstellen und die Interpret-Methode am Stammausdruck auszuführen. Ein Kontext kann verwendet werden, um den Anwendungsstatus zur Laufzeit zu speichern.

Implementierung

Das Muster beinhaltet:

  • Client – ​​​​gibt den AST-Baum zurück und führt Interpret(context) für den Wurzelknoten (Client) aus
  • Kontext – enthält den Status der Anwendung, der bei der Interpretation an Ausdrücke übergeben wird (Kontext)
  • Abstrakter Ausdruck – eine abstrakte Klasse, die die Methode Interpret(context) (Expression) enthält
  • Terminalausdruck ist ein endgültiger Ausdruck, ein Nachkomme eines abstrakten Ausdrucks (TerminalExpression)
  • Ein nicht-terminaler Ausdruck ist kein endlicher Ausdruck; er enthält Zeiger auf Scheitelpunkte tief im AST-Baum. Untergeordnete Scheitelpunkte wirken sich normalerweise auf das Ergebnis der Interpretation des nicht-terminalen Ausdrucks aus (NonTerminalExpression).

Client-Beispiel in C#

        static void Main(string[] args)
        {
            var context = new Context();
            var initialProgram = new PerformExpression(
                new IExpression[] {
                    new SetExpression("alpha", "1"),
                    new GetExpression("alpha"),
                    new PrintExpression(
                        new IExpression[] {
                            new ConstantExpression("Hello Interpreter Pattern")
                        }
                    )
                }
            );
            System.Console.WriteLine(initialProgram.interpret(context));
        }
}

Beispiel für einen abstrakten Ausdruck in C#

{
    String interpret(Context context);
}

Beispiel für einen Terminalausdruck in C# (String-Konstante)

{
    private String constant;

    public ConstantExpression(String constant) {
        this.constant = constant;
    }

    override public String interpret(Context context) {
        return constant;
    }
}

Beispiel eines nichtterminalen Ausdrucks in C# (Starten und Verketten der Ergebnisse untergeordneter Scheitelpunkte unter Verwendung des Trennzeichens „;“

{
    public PerformExpression(IExpression[] leafs) : base(leafs) {
        this.leafs = leafs;
    }
    
    override public String interpret(Context context) {
        var output = "";
        foreach (var leaf in leafs) {
            output += leaf.interpret(context) + ";";
        }
        return output;
    }
}

Können Sie es funktionell umsetzen?

Bekanntlich sind alle Turing-vollständigen Sprachen gleichwertig. Ist es möglich, das objektorientierte Muster auf die funktionale Programmiersprache zu übertragen?

Für ein Experiment nehmen wir eine FP-Sprache für das Web namens Elm. In Elm gibt es keine Klassen, aber Datensätze und Typen. Daher sind die folgenden Datensätze und Typen an der Implementierung beteiligt:

  • Ausdruck – Auflistung aller möglichen Sprachausdrücke (Ausdruck)
  • Untergeordneter Ausdruck – ein Ausdruck, der dem nichtterminalen Ausdruck (ExpressionLeaf) untergeordnet ist
  • Kontext – ein Datensatz, der den Status der Anwendung speichert (Kontext)
  • Funktionen, die Interpret(Kontext)-Methoden implementieren – alle notwendigen Funktionen, die die Funktionalität von Terminal- und Nicht-Terminal-Ausdrücken implementieren
  • Hilfsdatensätze des Interpreter-Status – notwendig für den korrekten Betrieb des Interpreters, sie speichern den Interpreter-Status und den Kontext

Ein Beispiel für eine Funktion, die die Interpretation für den gesamten Satz möglicher Ausdrücke in Elm implementiert:

  case input.expression of
    Constant text ->
      { 
        output = text, 
        context = input.context 
      }
    Perform leafs ->
      let inputs = List.map (\leaf -> { expressionLeaf = leaf, context = input.context } ) leafs in
        let startLeaf = { expressionLeaf = (Node (Constant "")), context = { variables = Dict.empty } } in
          let outputExpressionInput = List.foldl mergeContextsAndRunLeafs startLeaf inputs in
            {
              output = (runExpressionLeaf outputExpressionInput).output,
              context = input.context
            }
    Print printExpression ->
      run 
      { 
        expression = printExpression, 
        context = input.context 
      }
    Set key value ->
      let variables = Dict.insert key value input.context.variables in
      {
        output = "OK",
        context = { variables = variables }
      }
    Get key ->
      {
        output = Maybe.withDefault ("No value for key: " ++ key) (Dict.get key input.context.variables),
        context = input.context
      }

Was ist mit dem Parsen?

Das Parsen von Quellcode in einen AST-Baum ist nicht im Interpreter-Muster enthalten; es gibt mehrere Ansätze zum Parsen von Quellcode, aber dazu ein anderes Mal mehr.
Bei der Implementierung des Interpreters für Elm habe ich einen einfachen Parser im AST-Baum geschrieben, der aus zwei Funktionen besteht: Parsen eines Scheitelpunkts und Parsen untergeordneter Scheitelpunkte.

parseLeafs state =
    let tokensQueue = state.tokensQueue in
        let popped = pop state.tokensQueue in
            let tokensQueueTail = tail state.tokensQueue in
                if popped == "Nothing" then
                    state
                else if popped == "Perform(" then
                    {
                        tokensQueue = tokensQueue,
                        result = (state.result ++ [Node (parse tokensQueue)])
                    }
                else if popped == ")" then
                    parseLeafs {
                        tokensQueue = tokensQueueTail,
                        result = state.result
                    }
                else if popped == "Set" then
                    let key = pop tokensQueueTail in
                        let value = pop (tail tokensQueueTail) in
                            parseLeafs {
                                tokensQueue = tail (tail tokensQueueTail),
                                result = (state.result ++ [Node (Set key value)])
                            }
                else if popped == "Get" then
                    let key = pop tokensQueueTail in
                        parseLeafs {
                            tokensQueue = tail tokensQueueTail,
                            result = (state.result ++ [Node (Get key)])
                        }
                else 
                    parseLeafs {
                        tokensQueue = tokensQueueTail,
                        result = (state.result ++ [Node (Constant popped)])
                    }

parse tokensQueue =
    let popped = pop tokensQueue in
        let tokensQueueTail = tail tokensQueue in
            if popped == "Perform(" then
                Perform (
                    parseLeafs {
                        tokensQueue = tokensQueueTail, 
                        result = []
                    }
                ).result
            else if popped == "Set" then
                let key = pop tokensQueueTail in
                    let value = pop (tail tokensQueueTail) in
                        Set key value
            else if popped == "Print" then
                Print (parse tokensQueueTail)
            else
                Constant popped

Links

https://gitlab.com/demensdeum /patterns/-/tree/master/interpreter/elm
https://gitlab.com/demensdeum/patterns/-/tree/master/interpreter/csharp

Quellen

https://en.wikipedia.org/wiki/Interpreter_pattern
https://elm-lang.org/
https://docs.microsoft.com/en-us/dotnet/csharp/

RGB-Bild zu Grau

In diesem Beitrag beschreibe ich den Algorithmus zum Konvertieren eines RGB-Puffers in Grau (Graustufen).
Und das geht ganz einfach: Jeder Pixel-Farbkanal des Puffers wird nach einer bestimmten Formel konvertiert und die Ausgabe ist ein Graubild.
Durchschnittsmethode:

red = average;
green = average;
blue = average;

Складываем 3 цветовых канала и делим на 3.

Однако существует еще один метод – метод средневзвешенный, он учитывает цветовосприятие человека:

red = luminance;
green = luminance;
blue = luminance;

Какой метод лучше использовать? Да какой вам больше подходит для конкретной задачи. Далее сравнение методов с помощью тестовой цветовой сетки:

Пример реализации на JavaScript + HTML 5

    image,
    canvas,
    weightedAverage
) {
    const context = canvas.getContext('2d');

    const imageWeight = image.width;
    const imageHeight = image.height;

    canvas.width = imageWeight;
    canvas.height = imageHeight;

    context.drawImage(image, 0, 0);

    let pixels = context
        .getImageData(
            0,
            0,
            imageWeight,
            imageHeight
        );

    for (let y = 0; y & lt; pixels.height; y++) {
        for (let x = 0; x & lt; pixels.width; x++) {
            const i = (y * 4) * pixels.width + x * 4;

            let red = pixels.data[i];
            let green = pixels.data[i + 1];
            let blue = pixels.data[i + 2]

            const average = (red + green + blue) / 3;
            const luminance = 0.2126 * red +
                0.7152 * green +
                0.0722 * blue;

            red = weightedAverage ? luminance : average;
            green = weightedAverage ? luminance : average;
            blue = weightedAverage ? luminance : average;

            pixels.data[i] = red;
            pixels.data[i + 1] = green;
            pixels.data[i + 2] = blue;
        }
    }
    context
        .putImageData(
            pixels,
            0,
            0,
            0,
            0,
            pixels.width,
            pixels.height
        );
}

Источники

https://www.baeldung.com/cs/convert-rgb-to-grayscale
https://twitter.com/mudasobwa/status/1528046455587495940
https://rosettacode.org/wiki/Grayscale_image

Ссылки

http://papugi.demensdeum.repl.co/

Благодарности

Спасибо Aleksei Matiushkin (https://twitter.com/mudasobwa) за наводку на Rosetta Code

So führen Sie CSGO auf dem MacBook M1 aus

Wenn Sie beim Starten von CSGO auf einem MacBook M1 den Fehler SDL_GetDesktopDisplayMode_REAL erhalten, gehen Sie wie unten beschrieben vor.
1. Fügen Sie Steam für CSGO Startoptionen hinzu:
-w 1440 -h 900 -fullscreen
2. Starten Sie CSGO über Steam
3. Klicken Sie auf Ignorieren oder Immer ignorieren, um den Fehler SDL_GetDesktopDisplayMode_REAL
anzuzeigen4. Viel Spaß

Turing-Rechenmaschinen

Ich präsentiere Ihnen eine Übersetzung der ersten Seiten von Alan Turings Artikel – „ÜBER BERECHNBAREN ZAHLEN MIT ANWENDUNG AUF DAS AUFLÖSUNGSPROBLEM“ 1936. Die ersten Kapitel enthalten eine Beschreibung von Computern, die später die Grundlage für die moderne Informatik bildeten.

Die vollständige Übersetzung des Artikels und der Erklärung kann im Buch des amerikanischen Popularisierers Charles Petzold mit dem Titel „Reading Turing“ nachgelesen werden. Eine Reise durch Turings wegweisenden Artikel über Berechenbarkeit und Turing-Maschinen. (ISBN 978-5-97060-231-7, 978-0-470-22905-7)

Originalartikel:
https://www.astro.puc.cl/~rparra/tools/PAPERS/turing_1936.pdf

—

ÜBER BERECHNBARE ZAHLEN MIT ANWENDUNG AUF DAS AUFLÖSUNGSPROBLEM

A. M. TURING

[Eingegangen am 28. Mai 1936 – gelesen am 12. November 1936]

Berechenbare Zahlen können kurz als reelle Zahlen beschrieben werden, deren Ausdrücke als Dezimalbrüche auf endlich viele Arten berechnet werden können. Obwohl dieser Artikel Zahlen auf den ersten Blick als berechenbar behandelt, ist es fast genauso einfach, berechenbare Funktionen einer ganzzahligen Variablen, einer reellen Variablen, einer berechenbaren Variablen, berechenbarer Prädikate und dergleichen zu definieren und zu untersuchen. Die grundlegenden Probleme, die mit diesen berechenbaren Objekten verbunden sind, sind jedoch jeweils dieselben. Für eine detaillierte Betrachtung habe ich berechenbare Zahlen als berechenbares Objekt gewählt, da die Methode, sie zu berücksichtigen, am wenigsten umständlich ist. Ich hoffe, bald die Beziehung zwischen berechenbaren Zahlen und berechenbaren Funktionen usw. beschreiben zu können. Gleichzeitig wird auf dem Gebiet der Theorie der Funktionen einer reellen Variablen, ausgedrückt in berechenbaren Zahlen, geforscht. Nach meiner Definition ist eine reelle Zahl berechenbar, wenn ihre Darstellung als Dezimalbruch von einer Maschine geschrieben werden kann.

In den Absätzen 9 und 10 gebe ich einige Argumente an, um zu zeigen, dass berechenbare Zahlen alle Zahlen umfassen, von denen man natürlich annimmt, dass sie berechenbar sind. Insbesondere zeige ich, dass einige große Zahlenklassen berechenbar sind. Dazu gehören beispielsweise die Realteile aller algebraischen Zahlen, die Realteile der Nullstellen von Bessel-Funktionen, die Zahlen π, e und andere. Allerdings umfassen berechenbare Zahlen nicht alle definierbaren Zahlen, wie das folgende Beispiel einer definierbaren Zahl zeigt, die nicht berechenbar ist.

Obwohl die Klasse der berechenbaren Zahlen sehr groß ist und in vielerlei Hinsicht der Klasse der reellen Zahlen ähnelt, ist sie dennoch aufzählbar. In §8 betrachte ich bestimmte Argumente, die gegenteilig zu sein scheinen. Bei richtiger Anwendung eines dieser Argumente ergeben sich Schlussfolgerungen, die auf den ersten Blick denen von Gödel* ähneln. Diese Ergebnisse haben äußerst wichtige Anwendungsmöglichkeiten. Insbesondere kann, wie unten gezeigt (§11), das Auflösungsproblem nicht gelöst werden.

In seinem jüngsten Artikel führte Alonzo Church** die Idee der „effektiven Berechenbarkeit“ ein, die meiner Vorstellung von „Berechenbarkeit“ entspricht, aber eine völlig andere Definition hat. Zu ähnlichen Schlussfolgerungen kommt auch Church hinsichtlich der Lösungsproblematik. Der Beweis der Äquivalenz von „Berechenbarkeit“ und „Fähigkeit, effektiv gezählt zu werden“ wird im Anhang dieses Artikels vorgelegt.

1. Computer

Wir haben bereits gesagt, dass berechenbare Zahlen diejenigen Zahlen sind, deren Dezimalstellen mit endlichen Mitteln abzählbar sind. Hier ist eine klarere Definition erforderlich. Dieser Artikel wird keinen wirklichen Versuch unternehmen, die hier gegebenen Definitionen zu rechtfertigen, bis wir zu §9 kommen. Vorerst möchte ich nur anmerken, dass der (logische) Grund (dafür) darin besteht, dass das menschliche Gedächtnis zwangsläufig begrenzt ist.

Vergleichen wir eine Person, die gerade eine reelle Zahl berechnet, mit einer Maschine, die nur eine endliche Anzahl von Bedingungen q1, q2, …, qR erfüllen kann; Nennen wir diese Bedingungen „M-Konfigurationen“. Diese (also so definierte) Maschine ist mit einem „Band“ (analog zu Papier) ausgestattet. Dieses durch die Maschine laufende Band ist in Abschnitte unterteilt. Nennen wir sie „Quadrate“. Jedes dieser Quadrate kann eine Art „Symbol“ enthalten. Zu jedem Zeitpunkt gibt es nur ein solches Quadrat, sagen wir das r-te, das das Symbol „in dieser Maschine“ enthält. Nennen wir ein solches Quadrat ein „gescanntes Symbol“. Ein „gescanntes Zeichen“ ist das einzige Zeichen, das der Maschine sozusagen „direkt bekannt“ ist. Durch Ändern seiner M-Konfiguration kann sich die Maschine jedoch effektiv an einige der Zeichen erinnern, die sie zuvor „gesehen“ (gescannt) hat. Das mögliche Verhalten der Maschine zu jedem Zeitpunkt wird durch die m-Konfiguration qn und das gescannte Symbol*** bestimmt. Nennen wir dieses Symbolpaar qn, „Konfiguration“. Die so bezeichnete Konfiguration bestimmt das mögliche Verhalten einer bestimmten Maschine. In einigen dieser Konfigurationen, in denen das gescannte Quadrat leer ist (dh kein Zeichen enthält), schreibt das Gerät ein neues Zeichen auf das gescannte Quadrat und in anderen dieser Konfigurationen löscht es das gescannte Zeichen. Diese Maschine ist auch in der Lage, sich zu bewegen, um ein anderes Quadrat zu scannen, auf diese Weise kann sie sich jedoch nur zu dem benachbarten Quadrat rechts oder links bewegen. Zusätzlich zu diesen Vorgängen kann die M-Konfiguration der Maschine geändert werden. In diesem Fall bilden einige der geschriebenen Zeichen eine Ziffernfolge, die den Dezimalteil der zu berechnenden reellen Zahl darstellt. Der Rest wird nichts weiter als ungenaue Markierungen sein, um „dem Gedächtnis zu helfen“. In diesem Fall können nur die oben genannten ungenauen Markierungen gelöscht werden.

Ich behaupte, dass die hier betrachteten Operationen alle Operationen umfassen, die in der Berechnung verwendet werden. Die Begründung dieser Aussage ist für den Leser, der sich mit der Maschinentheorie auskennt, leichter zu verstehen. Daher werde ich im nächsten Abschnitt die betreffende Theorie weiter entwickeln, basierend auf einem Verständnis der Bedeutung der Begriffe „Maschine“, „Band“, „gescannt“ usw.

*Gödel „Über die formal unentscheidbaren Sätze der Principia Mathematics (veröffentlicht von Whitehead und Russell 1910, 1912 und 1913) und verwandte Systeme, Teil I“, Journal of Mathematics. Physik, Monatsheft Nr. 38 (für 1931, S. 173-198.
** Alonzo Church, „An Undecidable Problem in Elementary Number Theory“, American J. of Math., Nr. 58 (1936), S. 345-363.
*** Alonzo Church, „A Note on the Problem of Resolution“, J. of Symbolic Logic, Nr. 1 (1936), S. 40-41

Turing-Bombe

Im Jahr 1936 beschrieb der Wissenschaftler Alan Turing in seiner Veröffentlichung „On Computable Numbers, With An Application to Entscheidungsproblem“ den Einsatz einer universellen Rechenmaschine, die dem Problem der Lösbarkeit in der Mathematik ein Ende setzen könnte. Daraus kommt er zu dem Schluss, dass eine solche Maschine nichts richtig lösen könnte, wenn das Ergebnis ihrer Arbeit invertiert und auf sich selbst zurückgeführt würde. Es stellt sich heraus, dass es unmöglich ist, ein *ideales* Antivirenprogramm, einen *idealen* Kachelsetzer, ein Programm, das ideale Phrasen für Ihren Absturz vorschlägt usw. zu erstellen. Paradox!

Diese universelle Rechenmaschine kann jedoch zur Implementierung jedes beliebigen Algorithmus verwendet werden, den sich der britische Geheimdienst zunutze machte, indem er Turing engagierte und die Entwicklung einer „Bombe“-Maschine zur Entschlüsselung deutscher Nachrichten während des Zweiten Weltkriegs ermöglichte.

Das Folgende ist eine OOP-Modellierung eines Einzelbandcomputers in der Dart-Sprache, basierend auf dem Originaldokument.

Eine Turingmaschine besteht aus einem in Abschnitte unterteilten Film, jeder Abschnitt enthält ein Symbol, die Symbole können gelesen oder geschrieben werden. Beispiel einer Filmklasse:

final _map = Map<int, String>(); 

  String read({required int at}) { 
    return _map[at] ?? ""; 
  } 

  void write({required String symbol, required int at}) { 
    _map[at] = symbol; 
  } 
}

Es gibt auch ein „Scan-Quadrat“, es kann sich über den Film bewegen, Informationen lesen oder schreiben, in moderner Sprache – Magnetkopf. Beispiel einer Magnetkopfklasse:

  int _index = 0; 
  InfiniteTape _infiniteTape; 
  TapeHead(this._infiniteTape) {} 

  String next() { 
    _index += 1; 
    move(to: _index); 
    final output = read(); 
    return output; 
  } 

  String previous() { 
    _index -= 1; 
    move(to: _index); 
    final output = read(); 
    return output; 
  } 

  void move({required int to}) { 
    this._index = to; 
  } 

  String read() { 
    return _infiniteTape.read(at: this._index); 
  } 

  void write(String symbol) { 
    _infiniteTape.write(symbol: symbol, at: this._index); 
  } 

  int index() { 
    return _index; 
  } 
}

Die Maschine enthält „M-Konfigurationen“, anhand derer sie entscheiden kann, was als nächstes zu tun ist. In moderner Sprache – Staaten und Zustandsverwalter. Beispiel für einen Statushandler:

  FiniteStateControlDelegate? delegate = null; 

  void handle({required String symbol}) { 
    if (symbol == OPCODE_PRINT) { 
      final argument = delegate?.nextSymbol(); 
      print(argument);
    } 
    else if (symbol == OPCODE_GENERATE_RANDOM_NUMBER_FROM_ZERO_TO_AND_WRITE_AFTER) { 
      final to = int.tryParse(delegate!.nextSymbol())!; 
      final value = new Random().nextInt(to); 
      delegate!.nextSymbol(); 
      delegate!.write(value.toString()); 
    } 
    else if (symbol == OPCODE_INPUT_TO_NEXT) { 
      final input = stdin.readLineSync()!; 
      delegate?.nextSymbol(); 
      delegate?.write(input); 
    } 
    else if (symbol == OPCODE_COPY_FROM_TO) { 
      final currentIndex = delegate!.index(); 

и т.д.

Danach müssen Sie „Konfigurationen“ erstellen. In der modernen Sprache sind dies Operationscodes (Opcodes) und ihre Handler. Beispiel-Opcodes:

const OPCODE_PRINT = "print"; 
const OPCODE_INCREMENT_NEXT = "increment next"; 
const OPCODE_DECREMENT_NEXT = "decrement next"; 
const OPCODE_IF_PREVIOUS_NOT_EQUAL = "if previous not equal"; 
const OPCODE_MOVE_TO_INDEX = "move to index"; 
const OPCODE_COPY_FROM_TO = "copy from index to index"; 
const OPCODE_INPUT_TO_NEXT = "input to next"; 
const OPCODE_GENERATE_RANDOM_NUMBER_FROM_ZERO_TO_AND_WRITE_AFTER = "generate random number from zero to next and write after";

Vergessen Sie nicht, einen Opcode und einen Stop-Handler zu erstellen, sonst können Sie das Auflösungsproblem nicht beweisen oder nicht beweisen (sic!).

Jetzt verbinden wir mithilfe des „Mediator“-Musters alle Klassen in der Turing-Maschine-Klasse, erstellen eine Instanz der Klasse, zeichnen das Programm mit einem Tonbandgerät auf, laden das Band und Sie können es verwenden!

Für mich persönlich blieb die Frage, was primär war, interessant – Schaffung eines Universalrechners bzw. Beweis des „Entscheidungsproblems“, wodurch als Nebenprodukt ein Rechner entstand.

Kassetten

Zum Spaß habe ich mehrere Kassettenprogramme für meine Version der Maschine aufgenommen.

Hallo Welt

hello world 
stop

Считаем до 16-ти

0
if previous not equal
16
copy from index to index
1
8
print
?
move to index
0
else
copy from index to index
1
16
print
?
print
Finished!
stop

Самой интересной задачей было написание Quine программы, которая печатает свой исходный код, для одноленточной машины. Первые 8 часов мне казалось что эта задача не решаема с таким малым количеством опкодов, однако всего через 16 часов оказалось что я был не прав.

Реализация и примеры кассет, источники ниже.

Ссылки

https://gitlab.com/demensdeum/turing-machine

Источники

https://www.astro.puc.cl/~rparra/tools/PAPERS/turing_1936.pdf
https://kpolyakov.spb.ru/prog/turing.htm
https://www.youtube.com/watch?v=dNRDvLACg5Q
https://www.youtube.com/watch?v=jP3ceURvIYc
https://www.youtube.com/watch?v=9QCJj5QzETI
https://www.youtube.com/watch?v=HeQX2HjkcNo&t=0s

Schreiben in Assembly für Sega Genesis #5

In dieser Notiz beschreibe ich den Prozess des Lesens des Joysticks, des Änderns der Position des Sprites, des horizontalen Umdrehens, des Sega Genesis-Emulators und möglicherweise der Konsole selbst.

Das Lesen von Klicks und die Verarbeitung von „Ereignissen“ eines Shogi-Joysticks erfolgt nach folgendem Schema:

  1. Anfrage nach einer Kombination von Bits gedrückter Tasten
  2. Teile gedrückter Tasten lesen
  3. Verarbeitung auf der Ebene der Spiellogik

Um das Skelett-Sprite zu verschieben, müssen wir Variablen der aktuellen Position speichern.

RAM

Spiellogikvariablen werden im RAM gespeichert; bisher ist noch nichts Besseres erfunden worden. Lassen Sie uns Variablenadressen deklarieren und den Rendering-Code ändern:

skeletonYpos = $FF0002 
frameCounter = $FF0004 
skeletonHorizontalFlip = $FF0006

    move.w #$0100,skeletonXpos 
    move.w #$0100,skeletonYpos 
    move.w #$0001,skeletonHorizontalFlip 

FillSpriteTable: 
    move.l #$70000003,vdp_control_port 
    move.w skeletonYpos,vdp_data_port  
    move.w #$0F00,vdp_data_port 
    move.w skeletonHorizontalFlip,vdp_data_port 
    move.w skeletonXpos,vdp_data_port

Wie Sie sehen, beginnt die für die Arbeit verfügbare Adresse bei 0xFF0000 und endet bei 0xFFFFFF, insgesamt stehen uns 64 KB Speicher zur Verfügung. Skeleton-Positionen werden bei SkeletonXpos, SkeletonYpos, horizontale Drehung bei SkeletonHorizontalFlip deklariert.

Joypad

In Analogie zu VDP erfolgt die Arbeit mit Joypads über zwei separate Ports – Steuerport und Datenport, für den ersten 0xA10009 und 0xA10003 Co-Nr. Bei der Arbeit mit einem Joypad gibt es eine interessante Funktion: Zuerst müssen Sie eine Tastenkombination für die Abfrage anfordern und dann, nachdem Sie auf ein Update am Bus gewartet haben, die erforderlichen Tastendrücke lesen. Für die C/B- und D-Pad-Tasten ist dies 0x40, Beispiel unten:

  move.b #$40,joypad_one_control_port; C/B/Dpad 
  nop ; bus sync 
  nop ; bus sync 
  move.b joypad_one_data_port,d2 
  rts

Im Register d2 bleibt der Zustand der gedrückten oder nicht gedrückten Tasten erhalten, im Allgemeinen bleibt das, was über den Datumsport angefordert wurde, erhalten. Gehen Sie anschließend zum Motorola 68000-Register-Viewer Ihres Lieblingsemulators und sehen Sie, was das d2-Register je nach Tastenanschlägen entspricht. Auf clevere Weise können Sie es im Handbuch herausfinden, aber wir verlassen uns nicht auf ihr Wort. Weiterverarbeitung gedrückter Tasten im d2

-Register

    cmp #$FFFFFF7B,d2; handle left 
    beq MoveLeft  
    cmp #$FFFFFF77,d2; handle right  
    beq MoveRight  
    cmp #$FFFFFF7E,d2; handle up  
    beq MoveUp  
    cmp #$FFFFFF7D,d2; handle down  
    beq MoveDown  
    rts

Проверять нужно конечно отдельные биты, а не целыми словами, но пока и так сойдет. Теперь осталось самое простое – написать обработчики всех событий перемещения по 4-м направлениям. Для этого меняем переменные в RAM, и запускаем процедуру перерисовки.

Пример для перемещения влево + изменение горизонтального флипа:

    move.w skeletonXpos,d0 
    sub.w #1,d0 
    move.w d0,skeletonXpos 
    move.w #$0801,skeletonHorizontalFlip 
    jmp FillSpriteTable

После добавления всех обработчиков и сборки, вы увидите как скелет перемещается и поворачивается по экрану, но слишком быстро, быстрее самого ежа Соника.

Не так быстро!

Чтобы замедлить скорость игрового цикла, существуют несколько техник, я выбрал самую простую и не затрагивающую работу с внешними портами – подсчет цифры через регистр пока она не станет равна нулю.

Пример замедляющего цикла и игрового цикла:

  move.w #512,frameCounter 
WaitFrame: 
  move.w frameCounter,d0 
  sub.w #1,d0 
  move.w d0,frameCounter 
  dbra d0,WaitFrame 
GameLoop: 
  jsr ReadJoypad 
  jsr HandleJoypad 
  jmp GameLoop

Danach läuft das Skelett langsamer, was erforderlich war. Wie ich weiß, ist die häufigste Option zum „Verlangsamen“ das Zählen der vertikalen Synchronisierungsflagge. Sie können zählen, wie oft der Bildschirm gezeichnet wurde, und sind somit an eine bestimmte Anzahl an Bildern pro Sekunde gebunden.

Links

https://gitlab .com/demensdeum/segagenesisamples/-/blob/main/8Joypad/vasm/main.asm

Quellen

https://www.chibiakumas.com/68000/platform2.php
https://huguesjohnson.com/programming/genesis/tiles-sprites/

Schreiben in Assembly für Sega Genesis #4

In diesem Beitrag beschreibe ich, wie man Sprites mit dem VDP-Emulator der Sega Genesis-Konsole zeichnet.
Der Prozess des Renderns von Sprites ist dem Rendern von Kacheln sehr ähnlich:

  1. Farben in CRAM laden
  2. Teile der Sprites 8×8 in VRAM hochladen
  3. Sprite-Tabelle im VRAM füllen

Nehmen wir zum Beispiel ein Sprite eines Skeletts mit einem Schwert mit 32×32 Pixeln

Skeleton Guy [Animated] by Disthorn

CRAM

Mit ImaGenesis konvertieren wir es in CRAM-Farben und VRAM-Muster für Assembler. Danach erhalten wir zwei Dateien im ASM-Format, dann schreiben wir die Farben auf die Wortgröße um und die Kacheln müssen zum Zeichnen in der richtigen Reihenfolge platziert werden.
Interessante Informationen: Sie können die automatische VDP-Inkrementierung über das 0xF-Register auf die Wortgröße umstellen. Dadurch wird die Adresserhöhung aus dem CRAM-Farbfüllcode entfernt.

VRAM

Das Shogi-Handbuch enthält die korrekte Reihenfolge der Kacheln für große Sprites, aber wir sind schlauer, also übernehmen wir die Indizes aus dem Blog ChibiAkumas, beginnen wir mit dem Zählen ab Index 0:

0 4 8 12

1 5 9 13

2 6 10 14

3 7 11 15

Warum steht alles auf dem Kopf? Was willst du, die Konsole ist japanisch! Es könnte sogar von rechts nach links sein!
Lassen Sie uns die Reihenfolge in der ASM-Sprite-Datei manuell ändern:

	dc.l	$11111111	; Tile #0 
	dc.l	$11111111 
	dc.l	$11111111 
	dc.l	$11111111 
	dc.l	$11111111 
	dc.l	$11111111 
	dc.l	$11111111 
	dc.l	$11111111 
	dc.l	$11111111	; Tile #4 
	dc.l	$11111111 
	dc.l	$11111111 
	dc.l	$11111111 
	dc.l	$11111111 
	dc.l	$11111111 
	dc.l	$11111111 
	dc.l	$11111111
	dc.l	$11111111	; Tile #8 
	dc.l	$11111111 
	dc.l	$11111111 
	dc.l	$11111111 
	dc.l	$11111111 
	dc.l	$11111122 
	dc.l	$11111122 
	dc.l	$11111166 
	dc.l	$11111166	; Tile #12 
	dc.l	$11111166 
	dc.l	$11111166 
	и т.д.

Laden Sie das Sprite wie normale Kacheln/Muster:

  lea Sprite,a0 
  move.l #$40200000,vdp_control_port; write to VRAM command 
  move.w #128,d0 ; (16*8 rows of sprite) counter 
SpriteVRAMLoop: 
  move.l (a0)+,vdp_data_port; 
  dbra d0,SpriteVRAMLoop

Um ein Sprite zu zeichnen, müssen Sie nur noch die Sprite-Tabelle ausfüllen

Sprite-Tabelle

Die Sprite-Tabelle wird im VRAM gefüllt, die Adresse ihres Standorts wird in das VDP-Register 0x05 eingetragen, die Adresse ist wieder knifflig, man kann es im Handbuch sehen, ein Beispiel für Adresse F000:

Ок, теперь запишем наш спрайт в таблицу. Для этого нужно заполнить “структуру” данных состоящую из четырех word. Бинарное описание структуры вы можете найти в мануале. Лично я сделал проще, таблицу спрайтов можно редактировать вручную в эмуляторе Exodus.
Die Strukturparameter sind aus dem Namen ersichtlich, zum Beispiel XPos, YPos – Koordinaten, Kacheln – Nummer der Startkachel zum Zeichnen, HSize, VSize – Sprite-Größen durch Hinzufügen der Teile 8×8, HFlip, VFlip – Hardware-Rotation des Sprites horizontal und vertikal.

Es ist sehr wichtig, sich daran zu erinnern, dass Sprites außerhalb des Bildschirms sein können. Dies ist das richtige Verhalten, weil… Off-Screen-Sprites aus dem Speicher entladen – eine ziemlich ressourcenintensive Aktivität.
Nachdem die Daten im Emulator eingegeben wurden, müssen sie vom VRAM an die Adresse 0xF000 kopiert werden. Exodus unterstützt diese Funktion ebenfalls.
Analog zum Zeichnen von Kacheln greifen wir zunächst auf den VDP-Steuerport zu, um mit dem Schreiben an der Adresse 0xF000 zu beginnen, und schreiben dann die Struktur in den Datenport.
Ich möchte Sie daran erinnern, dass die Beschreibung der VRAM-Adressierung im Handbuch oder im Blog Namenloser Algorithmus .

Kurz gesagt funktioniert die VDP-Adressierung folgendermaßen:
[..DC BA98 7654 3210 …. …. …. ..FE]
Dabei ist Hex die Bitposition in der gewünschten Adresse. Die ersten beiden Bits geben die Art des angeforderten Befehls an, zum Beispiel 01 – in den VRAM schreiben. Für die Adresse 0XF000 ergibt sich dann:
0111 0000 0000 0000 0000 0000 0000 0011 (70000003)

Als Ergebnis erhalten wir den Code:

  move.l #$70000003,vdp_control_port 
  move.w #$0100,vdp_data_port 
  move.w #$0F00,vdp_data_port 
  move.w #$0001,vdp_data_port 
  move.w #$0100,vdp_data_port

Danach wird das Skelett-Sprite an den Koordinaten 256, 256 angezeigt. Cool, oder?

Links

https://gitlab.com/demensdeum /segagenesissamples/-/tree/main/7Sprite/vasm
https://opengameart.org/content/skeleton-guy-animated

Quellen

https://namelessalgorithm.com/genesis/blog/vdp/
https://www.chibiakumas.com/68000/platform3.php#LessonP27
https://plutiedev.com/sprites

Schreiben in Assembly für Sega Genesis #3

In diesem Beitrag beschreibe ich, wie man mithilfe von Assembler ein Bild aus Kacheln auf dem Sega Genesis-Emulator anzeigt.
Das Splash-Bild von Demens Deum im Exodus-Emulator sieht folgendermaßen aus:

Die Ausgabe eines PNG-Bildes mithilfe von Kacheln erfolgt Schritt für Schritt:

  1. Verkleinerung des Bildes auf die Größe des Shogi-Bildschirms
  2. Konvertieren Sie PNG in Assembly-Datencode, getrennt in Farben und Kacheln
  3. Laden einer Farbpalette in CRAM
  4. Laden von Kacheln/Mustern in VRAM
  5. Laden von Kachelindizes an Plane A/B-Adressen im VRAM
  6. Sie können das Bild mit Ihrem bevorzugten Grafikeditor wie Blender auf die Größe des Shogi-Bildschirms verkleinern.

PNG-Konvertierung

Zum Konvertieren von Bildern können Sie das ImaGenesis-Tool verwenden; für die Arbeit unter Wine sind Visual Basic 6-Bibliotheken erforderlich, diese können mit winetricks (winetricks vb6run) installiert werden, oder RICHTX32.OCX kann aus dem Internet heruntergeladen und abgelegt werden für den ordnungsgemäßen Betrieb im Anwendungsordner.< /p>

In ImaGenesis müssen Sie 4-Bit-Farbe auswählen und Farben und Kacheln in zwei Dateien im Assembler-Format exportieren. Als nächstes müssen Sie in der Datei mit den Farben jede Farbe in ein Wort (2 Bytes) einfügen. Dazu verwenden Sie den Opcode dc.w.

Zum Beispiel CRAM-Begrüßungsbildschirm:

  dc.w $0000 
  dc.w $0000 
  dc.w $0222 
  dc.w $000A 
  dc.w $0226 
  dc.w $000C 
  dc.w $0220 
  dc.w $08AA 
  dc.w $0446 
  dc.w $0EEE 
  dc.w $0244 
  dc.w $0668 
  dc.w $0688 
  dc.w $08AC 
  dc.w $0200 
  dc.w $0000

Lassen Sie die Kacheldatei unverändert, sie enthält bereits das richtige Format zum Laden. Beispiel eines Teils einer Kacheldatei:

	dc.l	$11111111	; Tile #0 
	dc.l	$11111111 
	dc.l	$11111111 
	dc.l	$11111111 
	dc.l	$11111111 
	dc.l	$11111111 
	dc.l	$11111111 
	dc.l	$11111111 
	dc.l	$11111111	; Tile #1 
	dc.l	$11111111 
	dc.l	$11111111 
	dc.l	$11111111 
	dc.l	$11111111 
	dc.l	$11111111 
	dc.l	$11111111 
	dc.l	$11111111

Wie Sie dem obigen Beispiel entnehmen können, handelt es sich bei den Kacheln um ein 8×8-Raster, das aus CRAM-Farbpalettenindizes besteht.

Farben im CRAM

Das Laden in den CRAM erfolgt durch Setzen eines Farbladebefehls an eine bestimmte CRAM-Adresse im Steuerport (vdp-Steuerung). Das Befehlsformat ist im Sega Genesis Software Manual (1989) beschrieben. Ich füge nur hinzu, dass Sie nur 0x20000 zur Adresse hinzufügen müssen, um zur nächsten Farbe zu wechseln.

Als nächstes müssen Sie die Farbe in den Datenport (vdp-Daten) laden; Der einfachste Weg, das Laden zu verstehen, ist das folgende Beispiel:

    lea Colors,a0 ; pointer to Colors label 
    move.l #15,d7; colors counter 
VDPCRAMFillLoopStep: 
    move.l  d0,vdp_control_port ;  
    move.w  (a0)+,d1; 
    move.w  d1,(vdp_data_port); 
    add.l #$20000,d0 ; increment CRAM address 
    dbra d7,VDPCRAMFillLoopStep

Kacheln im VRAM

Als nächstes erfolgt das Laden von Kacheln/Mustern in den VRAM-Videospeicher. Wählen Sie dazu eine Adresse im VRAM aus, zum Beispiel 0x00000000. Analog zum CRAM kontaktieren wir den VDP-Steuerport mit einem Befehl zum Schreiben in den VRAM und die Startadresse.

Danach können Sie Langwörter in den VRAM hochladen; im Vergleich zum CRAM müssen Sie nicht für jedes Langwort die Adresse angeben, da es einen VRAM-Auto-Inkrementierungsmodus gibt. Sie können es mit dem VDP-Registerflag 0x0F (dc.b $02)

aktivieren

  lea Tiles,a0 
  move.l #$40200000,vdp_control_port; write to VRAM command 
  move.w #6136,d0 ; (767 tiles * 8 rows) counter 
TilesVRAMLoop: 
  move.l (a0)+,vdp_data_port; 
  dbra d0,TilesVRAMLoop

Kachelindizes in Ebene A/B

Jetzt müssen wir den Bildschirm entsprechend ihrem Index mit Kacheln füllen. Dazu wird VRAM an der Plane A/B-Adresse gefüllt, die in den VDP-Registern (0x02, 0x04) eingetragen ist. Weitere Informationen zur kniffligen Adressierung finden Sie im Handbuch von Sega; in meinem Beispiel ist die VRAM-Adresse 0xC000, laden wir die Indizes dort hoch.

Ihr Bild füllt ohnehin den VRAM-Bereich außerhalb des Bildschirms aus. Nach dem Zeichnen des Bildschirmbereichs sollte Ihr Renderer also mit dem Zeichnen aufhören und wieder fortfahren, wenn sich der Cursor in eine neue Zeile bewegt. Es gibt viele Möglichkeiten, dies zu implementieren; ich habe die einfachste Version des Zählens auf zwei Registern des Bildbreitenzählers und des Cursorpositionszählers verwendet.

Codebeispiel:

  move.w #0,d0     ; column index 
  move.w #1,d1     ; tile index 
  move.l #$40000003,(vdp_control_port) ; initial drawing location 
  move.l #2500,d7     ; how many tiles to draw (entire screen ~2500) 

imageWidth = 31 
screenWidth = 64 

FillBackgroundStep: 
  cmp.w	#imageWidth,d0 
  ble.w	FillBackgroundStepFill 
FillBackgroundStep2: 
  cmp.w	#imageWidth,d0 
  bgt.w	FillBackgroundStepSkip 
FillBackgroundStep3: 
  add #1,d0 
  cmp.w	#screenWidth,d0 
  bge.w	FillBackgroundStepNewRow 
FillBackgroundStep4: 
  dbra d7,FillBackgroundStep    ; loop to next tile 

Stuck: 
  nop 
  jmp Stuck 

FillBackgroundStepNewRow: 
  move.w #0,d0 
  jmp FillBackgroundStep4 
FillBackgroundStepFill: 
  move.w d1,(vdp_data_port)    ; copy the pattern to VPD 
  add #1,d1 
  jmp FillBackgroundStep2 
FillBackgroundStepSkip: 
  move.w #0,(vdp_data_port)    ; copy the pattern to VPD 
  jmp FillBackgroundStep3

Danach müssen Sie nur noch das ROM mit Vasm zusammenbauen, den Simulator starten und sich das Bild ansehen.

Debuggen

Es wird nicht alles auf Anhieb klappen, daher möchte ich die folgenden Exodus-Emulator-Tools empfehlen:

  1. M68k-Prozessor-Debugger
  2. Ändern der Anzahl der m68k-Prozessorzyklen (für den Zeitlupenmodus im Debugger)
  3. Zuschauer CRAM, VRAM, Plane A/B
  4. Lesen Sie sorgfältig die Dokumentation für m68k und die verwendeten Opcodes (nicht alles ist so offensichtlich, wie es auf den ersten Blick scheint)
  5. Beispiele für Spielcode/Demontage auf Github ansehen
  6. Unterprogramme von Prozessorausnahmen implementieren und verarbeiten

Zeiger auf Prozessor-Ausnahme-Subroutinen werden im ROM-Header platziert; es gibt auch ein Projekt auf GitHub mit einem interaktiven Laufzeit-Debugger für Sega, genannt genesis-debugger.

Verwenden Sie alle verfügbaren Tools, haben Sie eine nette Codierung der alten Schule und vielleicht ist Blast Processing dabei!

Links

https://gitlab.com/demensdeum /segagenesisamples/-/tree/main/6Image/vasm
http://devster.monkeeh.com/sega/imagenesis/
https://github.com/flamewing/genesis-debugger

Quellen

https://www.chibiakumas.com/68000/helloworld .php#LessonH5
https://huguesjohnson.com/programming/genesis/tiles-sprites/

 

Schreiben in Assembly für Sega Genesis #2

In diesem Beitrag beschreibe ich, wie man Farben in Assemblersprache in die Shogi-Palette lädt.
Das Endergebnis im Exodus-Emulator sieht folgendermaßen aus:

Um den Prozess zu vereinfachen, finden Sie im Internet ein PDF mit dem Titel Genesis Software Manual (1989). Es beschreibt den gesamten Prozess sehr detailliert. Tatsächlich handelt es sich bei dieser Notiz um einen Kommentar zum Originalhandbuch.< /p>

Um Farben auf den VDP-Chip des Sega-Emulators zu schreiben, müssen Sie die folgenden Dinge tun:

  • TMSS-Schutz deaktivieren
  • Korrekte Parameter in VDP-Register schreiben
  • Schreiben Sie die gewünschten Farben in CRAM

Für den Zusammenbau verwenden wir vasmm68k_mot und einen bevorzugten Texteditor, zum Beispiel Echo. Der Zusammenbau erfolgt mit dem Befehl:

Порты VDP


VDP чип общается с M68K через два порта в оперативной памяти – порт контроля и порт данных.

По сути:


    

  1. Через порт контроля можно выставлять значения регистрам VDP.
    2. 

  2. Также порт контроля является указателем на ту часть VDP (VRAM, CRAM, VSRAM etc.) через которую передаются данные через порт данных
    3. 



Интересная информация: Сега сохранила совместимость с играми Master System, на что указывает MODE 4 из мануала разработчика, в нем VDP переключается в режим Master System.


Объявим порты контроля и данных:


vdp_data_port        = $C00000


Отключить систему защиты TMSS


Защита от нелицензионных игр TMSS имеет несколько вариантов разблокировки, например требуется чтобы до обращения к VDP в адресном регистре A1 лежала строка “SEGA”.




MOVE.B A1,D0; Получаем версию хардвары цифрой из A1 в регистр D0 
ANDI.B 0x0F,D0; По маске берем последние биты, чтобы ничего не сломать 
BEQ.B SkipTmss; Если версия равна 0, скорее всего это японка или эмулятор без включенного TMSS, тогда идем в сабрутину SkipTmss 
MOVE.L "SEGA",A1; Или записываем строку SEGA в A1 





Korrekte Parameter in VDP-Register schreiben


Warum überhaupt die richtigen Parameter in den VDP-Registern einstellen? Der Grundgedanke ist, dass VDP viel kann. Sie müssen es also vor dem Rendern mit den erforderlichen Funktionen initialisieren, sonst versteht es einfach nicht, was Sie von ihm erwarten.


Jedes Register ist für eine bestimmte Einstellung/Betriebsart verantwortlich. Das Segov-Handbuch gibt alle Bits/Flags für jedes der 24 Register an, eine Beschreibung der Register selbst.


Nehmen wir vorgefertigte Parameter mit Kommentaren aus dem Bigevilcorporation-Blog:





VDPReg0:   dc.b $14 ;  0: H interrupt on, palettes on 
VDPReg1:   dc.b $74 ;  1: V interrupt on, display on, DMA on, Genesis mode on 
VDPReg2:   dc.b $30 ;  2: Pattern table for Scroll Plane A at VRAM $C000 
                    ;     (bits 3-5 = bits 13-15) 
VDPReg3:   dc.b $00 ;  3: Pattern table for Window Plane at VRAM $0000 
                    ;     (disabled) (bits 1-5 = bits 11-15) 
VDPReg4:   dc.b $07 ;  4: Pattern table for Scroll Plane B at VRAM $E000 
                    ;     (bits 0-2 = bits 11-15) 
VDPReg5:   dc.b $78 ;  5: Sprite table at VRAM $F000 (bits 0-6 = bits 9-15) 
VDPReg6:   dc.b $00 ;  6: Unused 
VDPReg7:   dc.b $00 ;  7: Background colour - bits 0-3 = colour, 
                    ;     bits 4-5 = palette 
VDPReg8:   dc.b $00 ;  8: Unused 
VDPReg9:   dc.b $00 ;  9: Unused 
VDPRegA:   dc.b $FF ; 10: Frequency of Horiz. interrupt in Rasters 
                    ;     (number of lines travelled by the beam) 
VDPRegB:   dc.b $00 ; 11: External interrupts off, V scroll fullscreen, 
                    ;     H scroll fullscreen 
VDPRegC:   dc.b $81 ; 12: Shadows and highlights off, interlace off, 
                    ;     H40 mode (320 x 224 screen res) 
VDPRegD:   dc.b $3F ; 13: Horiz. scroll table at VRAM $FC00 (bits 0-5) 
VDPRegE:   dc.b $00 ; 14: Unused 
VDPRegF:   dc.b $02 ; 15: Autoincrement 2 bytes 
VDPReg10:  dc.b $01 ; 16: Vert. scroll 32, Horiz. scroll 64 
VDPReg11:  dc.b $00 ; 17: Window Plane X pos 0 left 
                    ;     (pos in bits 0-4, left/right in bit 7) 
VDPReg12:  dc.b $00 ; 18: Window Plane Y pos 0 up 
                    ;     (pos in bits 0-4, up/down in bit 7) 
VDPReg13:  dc.b $FF ; 19: DMA length lo byte 
VDPReg14:  dc.b $FF ; 20: DMA length hi byte 
VDPReg15:  dc.b $00 ; 21: DMA source address lo byte 
VDPReg16:  dc.b $00 ; 22: DMA source address mid byte 
VDPReg17:  dc.b $80 ; 23: DMA source address hi byte, 
                    ;     memory-to-VRAM mode (bits 6-7)  





Ok, jetzt gehen wir zum Steuerport und schreiben alle Flags in die VDP-Register:




    move.l  #VDPRegisters,a0 ; Пишем адрес таблицы параметров в A1 
    move.l  #$18,d0          ; Счетчик цикла - 24 = 18 (HEX) в D0 
    move.l  #$00008000,d1    ; Готовим команду на запись в регистр VDP по индексу 0, по мануалу - 1000 0000 0000 0000 (BIN) = 8000 (HEX) 

FillInitialStateForVDPRegistersLoop: 
    move.b  (a0)+,d1         ; Записываем в D1 итоговое значение регистра VDP из таблицы параметров, на отправку в порт контроля VDP  
    move.w  d1,vdp_control_port     ; Отправляем итоговую команду + значение из D1 в порт контроля VDP 
    add.w   #$0100,d1        ; Поднимаем индекс регистра VDP на 1 (бинарное сложение +1 к индексу по мануалу Сеги) 
    dbra    d0,FillInitialStateForVDPRegistersLoop ; Уменьшаем счетчик регистров, продолжаем цикл если необходимо


Самое сложное это прочитать мануал и понять в каком формате подаются данные на порт контроля, опытные разработчики разберутся сразу, а вот неопытные… Немного подумают и поймут, что синтаксис для записи регистров такой:


0B100(5 бит – индекс регистра)(8 бит/байт – значение)


0B1000001001000101 – записать в регистр VDP 2 (00010), значение флажков 01000101.


Записать нужные цвета в CRAM


Далее идем писать два цвета в память цветов CRAM (Color RAM). Для этого пишем в порт контроля команду на доступ к цвету по индексу 0 в CRAM и отправляем по дата порту цвет. Все!


Пример:




    move.l  #$C0000000,vdp_control_port ; Доступ к цвету по индексу 0 в CRAM через порт контроля  
    move.w  #228,d0; Цвет в D0 
    move.w  d0,vdp_data_port; Отправляем цвет в порт данных 





Nachdem Sie den Emulator in Exodus erstellt und ausgeführt haben, sollte Ihr Bildschirm mit der Farbe 228 gefüllt sein.


Füllen wir es mit einer zweiten Farbe, basierend auf dem letzten Byte 127.






  move.l  #$C07f0000,vdp_control_port ; Доступ к цвету по байту 127 в CRAM через порт контроля 
  move.w  #69,d0; Цвет в D0 
  move.w  d0,vdp_data_port; Отправляем цвет в порт данных 





Links


https://gitlab.com/demensdeum/segagenesissamples
https://www.exodusemulator.com/

http://sun.hasenbraten.de/vasm/

https://tomeko.net/online_tools/bin_to_32bit_hex.php?lang=en


Quellen


https://namelessalgorithm.com/genesis/blog/genesis/
https://plutiedev.com/vdp-commands

https://huguesjohnson.com/programming/genesis/palettes/

https://www.chibiakumas.com/68000/helloworld.php#LessonH5

https://blog.bigevilcorporation.co.uk/2012/03/09/sega-megadrive-3-awaking-the-beast/

Schreiben in Assembly für Sega Genesis #1

Der erste Artikel über das Schreiben von Spielen für die klassische Sega Genesis-Konsole in Motorola 68000 Assembly.

Lassen Sie uns die einfachste Endlosschleife für Sega schreiben. Dafür benötigen wir: einen Assembler, einen Emulator mit Disassembler, einen bevorzugten Texteditor, ein grundlegendes Verständnis der Struktur von Sega Rum.

Für die Entwicklung verwende ich meinen eigenen Assembler/Disassembler Gen68KryBaby:

https://gitlab.com/demensdeum/gen68krybaby/

Das Tool ist in Python 3 entwickelt, zum Zusammenstellen wird eine Datei mit der Erweiterung .asm oder .gen68KryBabyDisasm als Eingabe bereitgestellt, die Ausgabe ist eine Datei mit der Erweiterung .gen68KryBabyAsm.bin, die im Emulator oder auf ausgeführt werden kann eine echte Konsole (Vorsicht, weggehen, die Konsole könnte explodieren!)

Das Zerlegen von ROMs wird ebenfalls unterstützt. Dazu müssen Sie eine ROM-Datei als Eingabe übermitteln, ohne die Erweiterungen .asm oder .gen68KryBabyDisasm. Die Opcode-Unterstützung wird abhängig von meinem Interesse am Thema und der Beteiligung von Mitwirkenden steigen oder sinken.

Struktur

Der Sega-ROM-Header belegt die ersten 512 Bytes. Es enthält Informationen über das Spiel, den Namen, unterstützte Peripheriegeräte, Prüfsumme und andere Systemflags. Ich gehe davon aus, dass die Konsole ohne Titel nicht einmal auf den Rum schaut und denkt, dass er falsch ist, und sagt: „Was gibst du mir hier?“

Nach dem Header kommt das Unterprogramm/Reset-Unterprogramm, in dem der m68K-Prozessor seine Arbeit beginnt. Okay, es ist eine Kleinigkeit – Opcodes (Operationscodes) finden, nämlich nichts tun (!) und zur Unterroutine an der Adresse im Speicher wechseln. Wenn Sie googeln, können Sie den NOP-Opcode finden, der nichts tut, und den JSR-Opcode, der einen bedingungslosen Sprung zur Argumentadresse ausführt, das heißt, er bewegt den Schlitten einfach ohne irgendwelche Launen dorthin, wo wir ihn fragen.

Alles zusammenfügen

Der Header-Donor für die ROM war eines der Spiele in der Beta-Version, derzeit als Hex-Daten aufgezeichnet.


 00 ff 2b 52 00 00 02 00 00 00 49 90 00 00 49 90 00 00 49 90 00...и т.д.

Код программы со-но представляет из себя объявление сабрутины Reset/EntryPoint в 512 (0x200) байте, NOP, возврат каретки к 0x00000200, таким образом мы получим бесконечный цикл.

Ассемблерный код сабрутины Reset/EntryPoint:

    NOP
    NOP
    NOP 
    NOP
    NOP
    JSR 0x00000200

Vollständiges Beispiel zusammen mit ROM-Header:

https://gitlab.com /demensdeum/segagenesisamples/-/blob/main/1InfiniteLoop/1infiniteloop.asm

Wir sammeln als nächstes:



Запускаем ром 1infiniteloop.asm.gen68KryBabyAsm.bin в режиме дебаггера эмулятора Exodus/Gens, смотрим что m68K корректно считывает NOP, и бесконечно прыгает к EntryPoint в 0x200 на JSR




Здесь должен быть Соник показывающий V, но он уехал на Вакен.


Ссылки


https://gitlab.com/demensdeum/gen68krybaby/


https://gitlab.com/demensdeum/segagenesissamples


https://www.exodusemulator.com/downloads/release-archive


Источники


ROM Hacking Demo – Genesis and SNES games in 480i


http://68k.hax.com/


https://www.chibiakumas.com/68000/genesis.php


https://plutiedev.com/rom-header


https://blog.bigevilcorporation.co.uk/2012/02/28/sega-megadrive-1-getting-started/


https://opensource.apple.com/source/cctools/cctools-836/as/m68k-opcode.h.auto.html

Flammenstahl-Lokomotivläufer

Ich präsentiere Ihnen Flame Steel Engine Runner – Plattform zum Starten von Multimedia-Anwendungen basierend auf dem Flame Steel Engine-Toolkit. Unterstützte Plattformen sind Windows, MacOS, Linux, Android, iOS, HTML 5. Der Schwerpunkt der Anwendungscodeentwicklung hat sich in Richtung Skripterstellung verlagert – Derzeit wurde die Unterstützung für JavaScript mit TinyJS hinzugefügt, das Toolkit selbst und die Engine werden weiterhin in hardwarenahen Sprachen (C, C++, Rust usw.) entwickelt
Flame Steel Engine Runner Demo
Auf der Seite unten können Sie den Würfel drehen, Code in JavaScript schreiben, Modelle, Sounds, Musik und Code über die Schaltfläche „Dateien hochladen“ hochladen und mit der Schaltfläche „Ausführen“ von der Datei main.js aus starten.
https://demensdeum.com/demos/FlameSteelEngineRunner/

KleyMoment – Dienstprogramm zum Zusammenführen von Skriptdateien

Ich präsentiere Ihnen ein Dienstprogramm zum Zusammenführen von Skriptdateien – KleyMoment, ebenfalls ein umgekehrtes Dienstprogramm zum Zusammenfügen von Dateien. Das Dienstprogramm kann verwendet werden, um JavaScript-Dateien zu einer zusammenzuführen.
Das Tool ist in Python 3 implementiert und verfügt über eine einfache Befehlszeilenschnittstelle wie: 

Python3 KleyMoment.py-DateierweiterungsverzeichnisContainingFiles Ausgabedatei

Zum Beispiel das rekursive Zusammenführen von js-Dateien aus dem Skriptverzeichnis in die Datei „output.js“ 

python3 KleyMoment.py js Skripte Output.js

AntiKleyMoment, ebenfalls ein Dienstprogramm zum erneuten Zusammenfügen von Dateien, verwendet eine zusammengeklebte Datei als Eingabe, zum Beispiel: 

python3 AntiKleyMoment.py Output.js

Repository:
https://gitlab.com/demensdeum/kleymoment/

Space Jaguar Action-Rollenspiel 0.0.4

Der erste Prototyp des Space Jaguar Action-RPG-Spiels für Webassembly:

Das Laden dauert lange (53 MB), ohne dass eine Ladeanzeige angezeigt wird.

Space Jaguar Action-Rollenspiel – Lebenssimulator eines Weltraumpiraten. Im Moment stehen die einfachsten Spielmechaniken zur Verfügung:

  • im Weltraum fliegen
  • sterben
  • essen
  • schlafen
  • Stellen Sie ein Team ein
  • Schauen Sie sich den ruhelosen, schnell fliegenden Strom der Zeit an

Aufgrund der schlechten Optimierung der Darstellung von 3D-Szenen in der Webversion ist die Möglichkeit, in einer 3D-Umgebung herumzulaufen, nicht verfügbar. Die Optimierung wird in zukünftigen Versionen hinzugefügt.

Der Quellcode der Engine, des Spiels und der Skripte ist unter der MIT-Lizenz verfügbar. Alle Verbesserungsvorschläge werden äußerst positiv aufgenommen:

https://gitlab.com/demensdeum/space-jaguar -action-rpg

Screenshots der nativen Version für Linux:

Wie ich den Kerl an der Stange vermisst habe oder eine Geschichte über erstaunlichen Einfallsreichtum

In dieser Notiz werde ich über die Bedeutung von Architekturentscheidungen bei der Entwicklung, der Unterstützung einer Anwendung und in einer Teamentwicklungsumgebung schreiben.

Selbst- Betriebsserviette Professor Lucifer Gorgonzola. Rube Goldberg

In meiner Jugend habe ich an einer Taxi-Bestellanwendung gearbeitet. Im Programm können Sie einen Abholpunkt und einen Abgabepunkt auswählen, die Fahrtkosten und die Tarifart berechnen und tatsächlich ein Taxi bestellen. Ich habe die Anwendung in der letzten Phase des Vorabstarts erhalten; nach dem Hinzufügen mehrerer Korrekturen wurde die Anwendung im AppStore veröffentlicht. Bereits zu diesem Zeitpunkt war dem gesamten Team klar, dass die Implementierung sehr schlecht war, keine Entwurfsmuster verwendet wurden, alle Komponenten des Systems eng miteinander verbunden waren und es im Allgemeinen möglich war, es in eine große kontinuierliche Klasse (Gottobjekt) zu schreiben. Es hätte sich nichts geändert, so wie die Klassen ihre Verantwortungsgrenzen durcheinander brachten und sich in ihrer Gesamtmasse in einer toten Kopplung überlappten. Später beschloss das Management, die Anwendung unter Verwendung der richtigen Architektur von Grund auf neu zu schreiben, was auch geschah und das Endprodukt für mehrere Dutzend B2B-Kunden implementiert wurde.

Ich werde jedoch einen merkwürdigen Vorfall aus der Architektur der Vergangenheit beschreiben, von dem ich manchmal mitten in der Nacht schweißgebadet aufwache oder mich mitten am Tag plötzlich daran erinnere und hysterisch zu lachen beginne. Die Sache ist die, dass ich den Kerl an der Stange beim ersten Mal nicht treffen konnte, was den Großteil der Bewerbung zum Scheitern brachte, aber das Wichtigste zuerst.

Es war ein gewöhnlicher Arbeitstag, einer der Kunden erhielt die Aufgabe, das Anwendungsdesign leicht zu verfeinern – Es ist einfach, das Symbol in der Mitte des Auswahlbildschirms für die Abholadresse um ein paar Pixel nach oben zu verschieben. Nun, nachdem ich die Aufgabe professionell auf 10 Minuten geschätzt hatte, hob ich das Symbol um 20 Pixel an, völlig ahnungslos, und beschloss, den Taxiauftrag zu überprüfen.

Was? Die App zeigt den Bestellbutton nicht mehr an? Wie ist das passiert?

Ich traute meinen Augen nicht; nachdem ich das Symbol um 20 Pixel erhöht hatte, zeigte die Anwendung die Schaltfläche „Bestellung fortsetzen“ nicht mehr an. Nachdem ich die Änderung rückgängig gemacht hatte, sah ich die Schaltfläche wieder. Hier stimmte etwas nicht. Nachdem ich 20 Minuten im Debugger verbracht hatte, hatte ich es ein wenig satt, die vielen Aufrufe überlappender Klassen abzuwickeln, aber ich entdeckte, dass *das Verschieben des Bildes die Logik der Anwendung wirklich verändert*

Es drehte sich alles um das Symbol in der Mitte – Ein Mann auf einer Stange, der beim Bewegen der Karte nach oben sprang, um die Bewegung der Kamera zu animieren. Auf diese Animation folgte das Verschwinden des Knopfes unten. Anscheinend ging das Programm davon aus, dass der um 20 Pixel verschobene Mann einen Sprung machte, und versteckte daher gemäß seiner internen Logik die Bestätigungsschaltfläche.

Wie kann das passieren? Hängt der *Zustand* des Bildschirms wirklich nicht vom Muster der Zustandsmaschine ab, sondern von der *Darstellung* der Position des Mannes auf der Stange?

Es stellte sich heraus, dass jedes Mal, wenn die Karte gezeichnet wurde, die Anwendung *visuell* in die Mitte des Bildschirms gestochen und überprüft, was dort war. Wenn sich ein Mann auf einer Stange befindet, bedeutet dies, dass die Kartenverschiebungsanimation beendet ist und angezeigt werden muss Taste. Wenn der Mann nicht da ist, wird die Karte verschoben und die Schaltfläche muss ausgeblendet werden.

Im obigen Beispiel ist alles in Ordnung, erstens ist es ein Beispiel für Goldberg-Maschinen (abstruse Maschinen), zweitens ein Beispiel für die Zurückhaltung des Entwicklers, irgendwie mit anderen Entwicklern im Team zu interagieren (versuchen Sie, es ohne herauszufinden). Drittens können Sie alle Probleme nach SOLID, Mustern (Code-Smells), MVC-Verletzungen und vielem mehr auflisten.

Versuchen Sie, dies nicht zu tun, entwickeln Sie sich in alle möglichen Richtungen und helfen Sie Ihren Kollegen bei ihrer Arbeit. Frohes neues Jahr euch allen.

Links

https://ru.wikipedia.org/wiki/Goldberg_Machine

https://ru.wikipedia.org/wiki/SOLID

https://refactoring.guru/ru/refactoring/smells

https://ru.wikipedia.org/wiki/Model -View-Controller

https://refactoring.guru/ru/design-patterns/state

Erraten Sie die Gruppe

In diesem Beitrag beschreibe ich die Arbeit mit dem Fasttext-Textklassifikator.

Fasttext – Bibliothek für maschinelles Lernen zur Textklassifizierung. Versuchen wir ihr beizubringen, eine Metal-Band anhand des Songtitels zu identifizieren. Dazu nutzen wir überwachtes Lernen anhand eines Datensatzes.

Lassen Sie uns einen Datensatz von Liedern mit Gruppennamen erstellen:

__label__metallica fuel
__label__metallica escape
__label__black_sabbath gypsy
__label__black_sabbath snowblind
__label__black_sabbath am i going insane
__label__anthrax anthrax
__label__anthrax i'm alive
__label__anthrax antisocial
[и т.д.]

Формат обучающей выборки:

Обучим fasttext и сохраним модель:


model.save_model("model.bin")





Laden Sie das trainierte Modell und bitten Sie darum, die Gruppe anhand des Namens des Songs zu identifizieren:




predictResult = model.predict("Bleed")
print(predictResult)


В результате мы получим список классов на которые похож данный пример, с указанием уровня похожести цифрой, в нашем случае похожесть названия песни Bleed на одну из групп датасета.

Для того чтобы модель fasttext умела работать с датасетом выходящим за границы обучающей выборки, используют режим autotune с использованием файла валидации (файл тест). Во время автотюна fasttext подбирает оптимальные гиперпараметры модели, проводя валидацию результата на выборке из тест файла. Время автотюна ограничивается пользователем в самостоятельно, с помощью передачи аргумента autotuneDuration.

Пример создания модели с использованием файла тест:






Источники


https://fasttext.cc

https://gosha20777.github.io/tutorial/2018/04/12/fasttext-for-windows


Исходный код


https://gitlab.com/demensdeum/MachineLearning/-/tree/master/6bandClassifier

x86_64 Assembler + C = Eine Liebe

In dieser Notiz beschreibe ich den Prozess des Aufrufs von C-Funktionen aus dem Assembler.
Versuchen wir, printf(“Hello World!\n”); aufzurufen. und Exit(0);

    message: db "Hello, world!", 10, 0

section .text
    extern printf
    extern exit
    global main

main:
    xor	rax, rax
    mov	rdi, message    
    call printf
    xor rdi, rdi
    call exit

Alles ist viel einfacher als es scheint. Im Abschnitt .rodata beschreiben wir statische Daten, in diesem Fall die Zeile „Hallo Welt!“, 10 ist ein Zeilenumbruchzeichen und wir vergessen auch nicht, es auf Null zu setzen.

Im Codeabschnitt deklarieren wir die externen Funktionen printf, Exit der stdio- und stdlib-Bibliotheken und deklarieren auch die Eingabefunktion main:

    extern printf
    extern exit
    global main

Wir übergeben 0 von der Rax-Funktion an das Rückgaberegister. Sie können mov rax, 0; aber um es zu beschleunigen, benutzen sie xor rax, rax; Als nächstes übergeben wir einen Zeiger auf die Zeichenfolge an das erste Argument:

Далее вызываем внешнюю функцию Си printf:


    xor	rax, rax
    mov	rdi, message    
    call printf
    xor rdi, rdi
    call exit





In Analogie dazu übergeben wir 0 an das erste Argument und rufen „exit:“ auf.




    call exit





Wie die Amerikaner sagen:
Wer hört niemandem zu
Dieser Pilaw isst @ Alexander Pelevin


Quellen


https://www.devdungeon. com/content/how-mix-c-and-assembly
https://nekosecurity.com/x86-64-assembly/part-3-nasm-anatomy-syscall-passing-argument

https://www.cs.uaf.edu/2017/fall/cs301/reference/x86_64.html


Quellcode


https://gitlab.com/demensdeum/assembly-playground

Hallo Welt x86_64-Assembler

In diesem Beitrag beschreibe ich den Prozess der Einrichtung der IDE und schreibe den ersten Hello World in x86_64-Assembler für das Ubuntu-Linux-Betriebssystem.
Beginnen wir mit der Installation der SASM-IDE, Nasm-Assembler:

Далее запустим SASM и напишем Hello World:



section .text

main:
    mov rbp, rsp      ; for correct debugging
    mov rax, 1        ; write(
    mov rdi, 1        ;   STDOUT_FILENO,
    mov rsi, msg      ;   "Hello, world!\n",
    mov rdx, msglen   ;   sizeof("Hello, world!\n")
    syscall           ; );

    mov rax, 60       ; exit(
    mov rdi, 0        ;   EXIT_SUCCESS
    syscall           ; );

section .rodata
    msg: db "Hello, world!"
    msglen: equ $-msg





Hello World-Code aus dem Blog  James Fisher, angepasst für Assemblierung und Debugging in SASM. In der SASM-Dokumentation heißt es, dass der Einstiegspunkt eine Funktion namens „main“ sein muss, da sonst das Debuggen und Kompilieren des Codes fehlerhaft ist.
Was haben wir in diesem Code gemacht? Habe einen Systemaufruf getätigt – Zugriff auf den Kernel des Linux-Betriebssystems mit korrekten Argumenten in Registern, einem Zeiger auf eine Zeichenfolge im Datenabschnitt.


Unter der Lupe


Sehen wir uns den Code genauer an:




global – директива ассемблера позволяющая задавать глобальные символы со строковыми именами. Хорошая аналогия – интерфейсы заголовочных файлов языков C/C++. В данном случае мы задаем символ main для функции входа.


section – директива ассемблера позволяющая задавать секции (сегменты) кода. Директивы section или segment равнозначны. В секции .text помещается код программы.


Обьявляем начало функции main. В ассемблере функции называются подпрограммами (subroutine)


Первая машинная команда mov – помещает значение из аргумента 1 в аргумент 2. В данном случае мы переносим значение регистра rbp в rsp. Из комментария можно понять что эту строку добавил SASM для упрощения отладки. Видимо это личные дела между SASM и дебаггером gdb.


Далее посмотрим на код до сегмента данных .rodata, два вызова syscall, первый выводит строку Hello World, второй обеспечивает выход из приложения с корректным кодом 0.


Представим себе что регистры это переменные с именами rax, rdi, rsi, rdx, r10, r8, r9. По аналогии с высокоуровневыми языками, перевернем вертикальное представление ассемблера в горизонтальное, тогда вызов syscall будет выглядеть так:


Тогда вызов печати текста:


Вызов exit с корректным кодом 0:


Рассмотрим аргументы подробнее, в заголовочном файле asm/unistd_64.h находим номер функции __NR_write – 1, далее в документации смотрим аргументы для write:

ssize_t write(int fd, const void *buf, size_t count);


Первый аргумент – файловый дескриптор, второй – буфер с данными, третий – счетчик байт для записи в дескриптор. Ищем номер файлового дескриптора для стандартного вывода, в мануале по stdout находим код 1. Далее дело за малым, передать указатель на буфер строки Hello World из секции данных .rodata – msg, счетчик байт – msglen, передать в регистры rax, rdi, rsi, rdx корректные аргументы и вызвать syscall.


Обозначение константных строк и длины описывается в мануале nasm:


msglen equ $-message


Достаточно просто да?


Источники


https://github.com/Dman95/SASM

https://www.nasm.us/xdoc/2.15.05/html/nasmdoc0.html

http://acm.mipt.ru/twiki/bin/view/Asm/HelloNasm

https://jameshfisher.com/2018/03/10/linux-assembly-hello-world/

http://www.ece.uah.edu/~milenka/cpe323-10S/labs/lab3.pdf

https://c9x.me/x86/html/file_module_x86_id_176.html

https://www.recurse.com/blog/7-understanding-c-by-learning-assembly

https://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%BE%D0%BB%D0%BE%D0%B3_%D0%BF%D1%80%D0%BE%D1%86%D0%B5%D0%B4%D1%83%D1%80%D1%8B

https://www.tutorialspoint.com/assembly_programming/assembly_basic_syntax.html

https://nekosecurity.com/x86-64-assembly/part-3-nasm-anatomy-syscall-passing-argument

https://man7.org/linux/man-pages/man2/syscall.2.html

https://en.wikipedia.org/wiki/Write_(system_call)


Исходный код


https://gitlab.com/demensdeum/assembly-playground

Eigenschaften im Space Jaguar Action-Rollenspiel

Der erste Artikel über das in der Entwicklung befindliche Spiel, Space Jaguar Action RPG. In diesem Artikel beschreibe ich die Gameplay-Funktion des Jaguar – Eigenschaften.

Viele Rollenspiele verwenden ein statisches Charakterstatistiksystem, wie zum Beispiel die Statistiken von DnD (Stärke, Konstitution, Geschicklichkeit, Intelligenz, Weisheit, Charisma) oder Fallout – S.P.E.C.I.A.L (Stärke, Wahrnehmung, Ausdauer, Charisma, Intelligenz, Geschicklichkeit, Glück). ).

In Space Jaguar plane ich die Implementierung eines dynamischen Systems von Eigenschaften. Beispielsweise hat die Hauptfigur des Spiels Jag zu Beginn nur drei Eigenschaften – Beherrschung einer Klinge (Halbsäbel), zwielichtige Operationen (Geschäfte in der kriminellen Welt abschließen), Schurkenfähigkeiten (Schlösser knacken, Diebstahl). Während des Spiels werden den Charakteren im Rahmen des Spielmoduls dynamische Eigenschaften verliehen und entzogen. Alle Überprüfungen erfolgen auf der Grundlage des Niveaus bestimmter Eigenschaften, die für eine bestimmte Spielsituation erforderlich sind. Beispielsweise kann Jag eine Schachpartie nicht gewinnen, wenn er nicht über die Eigenschaft verfügt, Schach zu spielen, oder nicht über ein ausreichendes Level verfügt, um die Prüfung zu bestehen.

Zur Vereinfachung der Prüflogik erhält jedes Merkmal einen 6-stelligen Code in englischen Buchstaben, einen Namen und eine Beschreibung. Um beispielsweise eine Klinge zu besitzen: 

bladeFightingAbility.name = "BLADFG"; 
bladeFightingAbility.description = "Blade fighting ability"; 
bladeFightingAbility.points = 3;

Перед стартом игрового модуля можно будет просмотреть список публичных проверок необходимых для прохождения, также создатель может скрыть часть проверок для создания интересных игровых ситуаций.

Ноу-хау? Будет ли интересно? Лично я нахожу такую систему интересной, позволяющей одновременно обеспечить свободу творчества создателям игровых модулей, и возможность переноса персонажей из разных, но похожих по характеристикам, модулей для игроков.

Hash-Tabelle

Mit der Hash-Tabelle können Sie eine assoziative Array-Datenstruktur (Wörterbuch) mit einer durchschnittlichen Leistung von O(1) für Einfüge-, Lösch- und Suchvorgänge implementieren.

Unten finden Sie ein Beispiel für die einfachste Implementierung einer Hash-Map in nodeJS:

Wie funktioniert es? Passen Sie auf Ihre Hände auf:

  • Innerhalb der Hash-Map befindet sich ein Array
  • Im Array-Element befindet sich ein Zeiger auf den ersten Knoten der verknüpften Liste
  • Speicher wird für ein Array von Zeigern zugewiesen (z. B. 65535 Elemente)
  • Sie implementieren eine Hash-Funktion, der Wörterbuchschlüssel ist die Eingabe, und am Ausgang kann sie alles tun, aber am Ende gibt sie den Index des Array-Elements zurück

So funktioniert die Aufnahme:

  • Am Eingang liegt ein Schlüsselpaar – Wert
  • Hash-Funktion gibt Index nach Schlüssel zurück
  • Einen verknüpften Listenknoten aus einem Array nach Index abrufen
  • Überprüfen Sie, ob es mit dem Schlüssel übereinstimmt
  • Wenn es übereinstimmt, ersetzen Sie den Wert
  • Wenn es nicht übereinstimmt, fahren Sie mit dem nächsten Knoten fort, bis wir einen Knoten mit dem erforderlichen Schlüssel finden oder finden.
  • Wenn der Knoten immer noch nicht gefunden wird, erstellen Sie ihn am Ende der verknüpften Liste

So funktioniert die Suche nach Schlüssel:

  • Am Eingang liegt ein Schlüsselpaar – Wert
  • Hash-Funktion gibt Index nach Schlüssel zurück
  • Einen verknüpften Listenknoten aus einem Array nach Index abrufen
  • Überprüfen Sie, ob es mit dem Schlüssel übereinstimmt
  • Wenn es übereinstimmt, wird der Wert zurückgegeben
  • Wenn es nicht übereinstimmt, fahren Sie mit dem nächsten Knoten fort, bis wir einen Knoten mit dem erforderlichen Schlüssel finden oder finden.

Warum brauchen wir eine verknüpfte Liste innerhalb eines Arrays? Aufgrund möglicher Kollisionen bei der Berechnung der Hash-Funktion. In diesem Fall befinden sich mehrere verschiedene Schlüssel-Wert-Paare am selben Index im Array. In diesem Fall wird die verknüpfte Liste durchlaufen, um den erforderlichen Schlüssel zu finden.

Quellen

https://ru.wikipedia.org/wiki/Hash-Tabelle
https://www.youtube.com/watch?v=wg8hZxMRwcw

Quellcode

https://gitlab.com/demensdeum/datastructures