Category Archives: Techie

Technical articles

Binäre Einfügungssortierung

Binary Insertion Sort ist eine Variante der Insertion Sort, bei der die Einfügeposition mithilfe der binären Suche ermittelt wird. Die zeitliche Komplexität des Algorithmus beträgt O(n2)

Der Algorithmus funktioniert folgendermaßen:

  1. Eine Schleife beginnt bei Null bis zum Ende der Liste
  2. In der Schleife wird eine Zahl zum Sortieren ausgewählt, die Zahl wird in einer separaten Variablen gespeichert
  3. Die binäre Suche sucht nach dem Index, um diese Zahl gegen die Zahlen auf der linken Seite einzufügen
  4. Sobald der Index gefunden wurde, werden die Zahlen auf der linken Seite beginnend beim Einfügeindex um eine Position nach rechts verschoben. Dabei wird die zu sortierende Nummer gelöscht.
  5. Die zuvor gespeicherte Nummer wird am Einfügeindex eingefügt
  6. Am Ende der Schleife wird die gesamte Liste sortiert

Bei einer binären Suche kann es sein, dass die Nummer nicht gefunden wird und der Index nicht zurückgegeben wird. Aufgrund der Besonderheit der binären Suche wird die Zahl gefunden, die der gesuchten Zahl am nächsten kommt. Um den Index zurückzugeben, müssen Sie ihn mit der gesuchten Zahl vergleichen. Wenn die gesuchte Zahl kleiner ist, sollte die gesuchte Zahl bei sein der Index links, und wenn größer oder gleich, dann rechts.

Go-Code:


import (
	"fmt"
	"math/rand"
	"time"
)

const numbersCount = 20
const maximalNumber = 100

func binarySearch(numbers []int, item int, low int, high int) int {
	for high > low {
		center := (low + high) / 2
		if numbers[center] < item { low = center + 1 } else if numbers[center] > item {
			high = center - 1
		} else {
			return center
		}
	}

	if numbers[low] < item {
		return low + 1
	} else {
		return low
	}
}

func main() {
	rand.Seed(time.Now().Unix())
	var numbers [numbersCount]int
	for i := 0; i < numbersCount; i++ {
		numbers[i] = rand.Intn(maximalNumber)
	}
	fmt.Println(numbers)

	for i := 1; i < len(numbers); i++ { searchAreaLastIndex := i - 1 insertNumber := numbers[i] insertIndex := binarySearch(numbers[:], insertNumber, 0, searchAreaLastIndex) for x := searchAreaLastIndex; x >= insertIndex; x-- {
			numbers[x+1] = numbers[x]
		}
		numbers[insertIndex] = insertNumber
	}
	fmt.Println(numbers)
}

Links

https://gitlab.com/demensdeum/algorithms/-/blob/master/sortAlgorithms/binaryInsertionSort/binaryInsertionSort.go

Quellen

https://www.geeksforgeeks.org/binary-insertion- sort/
https://www.youtube.com/watch?v=-OVB5pOZJug

Muschelsortierung

Shell Sort – eine Variante der Einfügungssortierung mit vorläufiger Kämmung eines Zahlenarrays.

Wir müssen uns daran erinnern, wie die Einfügungssortierung funktioniert:

1. Eine Schleife wird von Null bis zum Ende der Schleife gestartet, wodurch das Array in zwei Teile geteilt wird
2. Für den linken Teil wird eine zweite Schleife gestartet, die Elemente von rechts nach links vergleicht. Das kleinere Element auf der rechten Seite wird gelöscht, bis ein kleineres Element auf der linken Seite gefunden wird
3. Am Ende beider Schleifen erhalten wir eine sortierte Liste

Es war einmal der Informatiker Donald Schell, der sich fragte, wie man den Einfügungssortierungsalgorithmus verbessern könnte. Er kam auch auf die Idee, das Array zunächst in zwei Zyklen zu durchlaufen, jedoch in einem bestimmten Abstand, und den „Kamm“ schrittweise zu verkleinern, bis daraus ein regulärer Einfügungssortierungsalgorithmus wird. Alles ist wirklich so einfach, keine Fallstricke. Zu den beiden oben genannten Zyklen fügen wir einen weiteren hinzu, in dem wir die Größe des „Kamms“ schrittweise reduzieren. Das Einzige, was Sie tun müssen, ist, beim Vergleich den Abstand zu überprüfen, damit er nicht über das Array hinausgeht.

Ein wirklich interessantes Thema ist die Auswahl der Reihenfolge zum Ändern der Vergleichslänge bei jeder Iteration der ersten Schleife. Dies ist deshalb interessant, weil die Leistung des Algorithmus davon abhängt.

Die Tabelle bekannter Optionen und Zeitkomplexität finden Sie hier: https: //en .wikipedia.org/wiki/Shellsort#Gap_sequences

An der Berechnung des idealen Abstands waren verschiedene Personen beteiligt; für sie war dieses Thema offenbar so interessant. Könnten sie nicht einfach Ruby ausführen und den schnellsten sort()-Algorithmus aufrufen?

Im Allgemeinen haben diese seltsamen Leute Dissertationen zum Thema der Berechnung des Abstands/der Lücke des „Kamms“ für den Shell-Algorithmus geschrieben. Ich habe einfach die Ergebnisse ihrer Arbeit verwendet und fünf Arten von Sequenzen überprüft: Hibbard, Knuth-Pratt, Chiura, Sedgwick.

import time
import random
from functools import reduce
import math

DEMO_MODE = False

if input("Demo Mode Y/N? ").upper() == "Y":
    DEMO_MODE = True

class Colors:
    BLUE = '\033[94m'
    RED = '\033[31m'
    END = '\033[0m'

def swap(list, lhs, rhs):
    list[lhs], list[rhs] = list[rhs], list[lhs]
    return list

def colorPrintoutStep(numbers: List[int], lhs: int, rhs: int):
    for index, number in enumerate(numbers):
        if index == lhs:
            print(f"{Colors.BLUE}", end = "")
        elif index == rhs:
            print(f"{Colors.RED}", end = "")
        print(f"{number},", end = "")
        if index == lhs or index == rhs:
            print(f"{Colors.END}", end = "")
        if index == lhs or index == rhs:
            print(f"{Colors.END}", end = "")
    print("\n")
    input(">")

def ShellSortLoop(numbers: List[int], distanceSequence: List[int]):
    distanceSequenceIterator = reversed(distanceSequence)
    while distance:= next(distanceSequenceIterator, None):
        for sortArea in range(0, len(numbers)):
            for rhs in reversed(range(distance, sortArea + 1)):
                lhs = rhs - distance
                if DEMO_MODE:
                    print(f"Distance: {distance}")
                    colorPrintoutStep(numbers, lhs, rhs)
                if numbers[lhs] > numbers[rhs]:
                    swap(numbers, lhs, rhs)
                else:
                    break

def ShellSort(numbers: List[int]):
    global ShellSequence
    ShellSortLoop(numbers, ShellSequence)

def HibbardSort(numbers: List[int]):
    global HibbardSequence
    ShellSortLoop(numbers, HibbardSequence)

def ShellPlusKnuttPrattSort(numbers: List[int]):
    global KnuttPrattSequence
    ShellSortLoop(numbers, KnuttPrattSequence)

def ShellPlusCiuraSort(numbers: List[int]):
    global CiuraSequence
    ShellSortLoop(numbers, CiuraSequence)

def ShellPlusSedgewickSort(numbers: List[int]):
    global SedgewickSequence
    ShellSortLoop(numbers, SedgewickSequence)

def insertionSort(numbers: List[int]):
    global insertionSortDistanceSequence
    ShellSortLoop(numbers, insertionSortDistanceSequence)

def defaultSort(numbers: List[int]):
    numbers.sort()

def measureExecution(inputNumbers: List[int], algorithmName: str, algorithm):
    if DEMO_MODE:
        print(f"{algorithmName} started")
    numbers = inputNumbers.copy()
    startTime = time.perf_counter()
    algorithm(numbers)
    endTime = time.perf_counter()
    print(f"{algorithmName} performance: {endTime - startTime}")

def sortedNumbersAsString(inputNumbers: List[int], algorithm) -> str:
    numbers = inputNumbers.copy()
    algorithm(numbers)
    return str(numbers)

if DEMO_MODE:
    maximalNumber = 10
    numbersCount = 10
else:
    maximalNumber = 10
    numbersCount = random.randint(10000, 20000)

randomNumbers = [random.randrange(1, maximalNumber) for i in range(numbersCount)]

ShellSequenceGenerator = lambda n: reduce(lambda x, _: x + [int(x[-1]/2)], range(int(math.log(numbersCount, 2))), [int(numbersCount / 2)])
ShellSequence = ShellSequenceGenerator(randomNumbers)
ShellSequence.reverse()
ShellSequence.pop()

HibbardSequence = [
    0, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095,
    8191, 16383, 32767, 65535, 131071, 262143, 524287, 1048575,
    2097151, 4194303, 8388607, 16777215, 33554431, 67108863, 134217727,
    268435455, 536870911, 1073741823, 2147483647, 4294967295, 8589934591
]

KnuttPrattSequence = [
    1, 4, 13, 40, 121, 364, 1093, 3280, 9841, 29524, 88573, 265720, 
    797161, 2391484, 7174453, 21523360, 64570081, 193710244, 581130733, 
    1743392200, 5230176601, 15690529804, 47071589413
]

CiuraSequence = [
            1, 4, 10, 23, 57, 132, 301, 701, 1750, 4376, 
            10941, 27353, 68383, 170958, 427396, 1068491, 
            2671228, 6678071, 16695178, 41737946, 104344866, 
            260862166, 652155416, 1630388541
]

SedgewickSequence = [
            1, 5, 19, 41, 109, 209, 505, 929, 2161, 3905,
            8929, 16001, 36289, 64769, 146305, 260609, 587521, 
            1045505, 2354689, 4188161, 9427969, 16764929, 37730305, 
            67084289, 150958081, 268386305, 603906049, 1073643521, 
            2415771649, 4294770689, 9663381505, 17179475969
]

insertionSortDistanceSequence = [1]

algorithms = {
    "Default Python Sort": defaultSort,
    "Shell Sort": ShellSort,
    "Shell + Hibbard" : HibbardSort,
    "Shell + Prat, Knutt": ShellPlusKnuttPrattSort,
    "Shell + Ciura Sort": ShellPlusCiuraSort,
    "Shell + Sedgewick Sort": ShellPlusSedgewickSort,
    "Insertion Sort": insertionSort
}

for name, algorithm in algorithms.items():
    measureExecution(randomNumbers, name, algorithm)

reference = sortedNumbersAsString(randomNumbers, defaultSort)

for name, algorithm in algorithms.items():
    if sortedNumbersAsString(randomNumbers, algorithm) != reference:
        print("Sorting validation failed")
        exit(1)

print("Sorting validation success")
exit(0)

In meiner Implementierung sind für einen zufälligen Satz von Zahlen die schnellsten Lücken Sedgwick und Hibbard.

mypy

Ich möchte auch den statischen Typisierungsanalysator für Python 3 erwähnen – mypy. Hilft bei der Bewältigung der Probleme, die Sprachen mit dynamischer Eingabe innewohnen, indem es die Möglichkeit ausschließt, etwas dort festzuhalten, wo es nicht benötigt wird.

Wie erfahrene Programmierer sagen: „Statisches Tippen ist nicht erforderlich, wenn Sie ein Team von Profis haben.“ Eines Tages werden wir alle Profis, wir werden Code in völliger Einheit und Verständnis mit Maschinen schreiben, aber im Moment können Sie ähnliche Dienstprogramme verwenden und statisch typisierte Sprachen.

Links

https://gitlab.com/demensdeum /algorithms/-/tree/master/sortAlgorithms/shellSort
http://mypy-lang.org/

Quellen

https://dl.acm.org/doi/10.1145/368370.368387
https://en.wikipedia.org/wiki/Shellsort
http://rosettacode.org/wiki/Sorting_algorithms/Shell_sort
https://ru.wikipedia.org/wiki/Сортировка_Шелла
https://neerc.ifmo.ru/wiki/index.php?title=Сортировка_Шелла
https://twitter.com/gvanrossum/status/700741601966985216

Doppelte Auswahlsortierung

Doppelte Auswahlsortierung – eine Unterart der Auswahlsortierung, die anscheinend doppelt so schnell sein sollte. Der Vanilla-Algorithmus durchläuft die Liste der Zahlen doppelt, findet die Mindestzahl und tauscht die Plätze mit der aktuellen Zahl, auf die die Schleife auf der Ebene darüber zeigt. Die Sortierung mit doppelter Auswahl sucht nach den minimalen und maximalen Zahlen und ersetzt dann die beiden Ziffern, auf die die Schleife auf der Ebene darüber zeigt – zwei Zahlen links und rechts. Diese ganze Orgie endet, wenn die Cursor der zu ersetzenden Zahlen in der Mitte der Liste gefunden werden und als Ergebnis sortierte Zahlen links und rechts von der visuellen Mitte erhalten werden.
Die zeitliche Komplexität des Algorithmus ähnelt der von Selection Sort – O(n2), aber angeblich gibt es eine Beschleunigung von 30 %.

Grenzzustand

Bereits in diesem Stadium können Sie sich den Moment einer Kollision vorstellen, zum Beispiel, wenn die Zahl des linken Cursors (die Mindestzahl) auf die Höchstzahl in der Liste zeigt, dann wird die Mindestzahl neu angeordnet, die Neuordnung der Höchstzahl bricht sofort zusammen. Daher beinhalten alle Implementierungen des Algorithmus die Prüfung auf solche Fälle und das Ersetzen von Indizes durch korrekte. In meiner Implementierung hat eine Prüfung gereicht:

  maximalNumberIndex = minimalNumberIndex;
}

Реализация на Cito

Cito – язык либ, язык транслятор. На нем можно писать для C, C++, C#, Java, JavaScript, Python, Swift, TypeScript, OpenCL C, при этом совершенно ничего не зная про эти языки. Исходный код на языке Cito транслируется в исходный код на поддерживаемых языках, далее можно использовать как библиотеку, либо напрямую, исправив сгенеренный код руками. Эдакий Write once – translate to anything.
Double Selection Sort на cito:

{
    public static int[] sort(int[]# numbers, int length)
    {
        int[]# sortedNumbers = new int[length];
        for (int i = 0; i < length; i++) {
            sortedNumbers[i] = numbers[i];
        }
        for (int leftCursor = 0; leftCursor < length / 2; leftCursor++) {
            int minimalNumberIndex = leftCursor;
            int minimalNumber = sortedNumbers[leftCursor];

            int rightCursor = length - (leftCursor + 1);
            int maximalNumberIndex = rightCursor;
            int maximalNumber = sortedNumbers[maximalNumberIndex];

            for (int cursor = leftCursor; cursor <= rightCursor; cursor++) { int cursorNumber = sortedNumbers[cursor]; if (minimalNumber > cursorNumber) {
                    minimalNumber = cursorNumber;
                    minimalNumberIndex = cursor;
                }
                if (maximalNumber < cursorNumber) {
                    maximalNumber = cursorNumber;
                    maximalNumberIndex = cursor;
                }
            }

            if (leftCursor == maximalNumberIndex) {
                maximalNumberIndex = minimalNumberIndex;
            }

            int fromNumber = sortedNumbers[leftCursor];
            int toNumber = sortedNumbers[minimalNumberIndex];
            sortedNumbers[minimalNumberIndex] = fromNumber;
            sortedNumbers[leftCursor] = toNumber;

            fromNumber = sortedNumbers[rightCursor];
            toNumber = sortedNumbers[maximalNumberIndex];
            sortedNumbers[maximalNumberIndex] = fromNumber;
            sortedNumbers[rightCursor] = toNumber;
        }
        return sortedNumbers;
    }
}

Links

https://gitlab.com/demensdeum /algorithms/-/tree/master/sortAlgorithms/doubleSelectionSort
https://github.com/pfusik/cito

Quellen

https://www.researchgate.net/publication/330084245_Improved_Double_Selection_Sort_using_Algorithm
http://algolab.valemak.com/selection-double
https://www.geeksforgeeks.org/sorting-algorithm-slightly-improves-selection-sort/

Cocktail-Shaker-Sorte

Cocktail-Shaker-Sortierung – Schüttlersortierung, eine Variante der bidirektionalen Blasensortierung.
Der Algorithmus funktioniert wie folgt:

  1. Die anfängliche Suchrichtung in der Schleife wird ausgewählt (normalerweise von links nach rechts)
  2. Als nächstes werden in der Schleife die Zahlen paarweise überprüft
  3. Wenn das nächste Element größer ist, werden sie vertauscht
  4. Wenn der Suchvorgang abgeschlossen ist, beginnt er erneut mit umgekehrter Richtung
  5. Die Suche wird wiederholt, bis keine Permutationen mehr vorhanden sind

Die zeitliche Komplexität des Algorithmus ist ähnlich wie bei einer Blase – O(n2).

Beispiel für die Implementierung in PHP:

<?php

function cocktailShakeSort($numbers)
{
    echo implode(",", $numbers),"\n";
    $direction = false;
    $sorted = false;
    do {
        $direction = !$direction;        
        $firstIndex = $direction == true ? 0 : count($numbers) - 1;
        $lastIndex = $direction == true ? count($numbers) - 1 : 0;
        
        $sorted = true;
        for (
            $i = $firstIndex;
            $direction == true ? $i < $lastIndex : $i > $lastIndex;
            $direction == true ? $i++ : $i--
        ) {
            $lhsIndex = $direction ? $i : $i - 1;
            $rhsIndex = $direction ? $i + 1 : $i;

            $lhs = $numbers[$lhsIndex];
            $rhs = $numbers[$rhsIndex];

            if ($lhs > $rhs) {
                $numbers[$lhsIndex] = $rhs;
                $numbers[$rhsIndex] = $lhs;
                $sorted = false;
            }
        }
    } while ($sorted == false);

    echo implode(",", $numbers);
}

$numbers = [2, 1, 4, 3, 69, 35, 55, 7, 7, 2, 6, 203, 9];
cocktailShakeSort($numbers);

?>

Ссылки

https://gitlab.com/demensdeum/algorithms/-/blob/master/sortAlgorithms/cocktailShakerSort/cocktailShakerSort.php

Источники

https://www.youtube.com/watch?v=njClLBoEbfI
https://www.geeksforgeeks.org/cocktail-sort/
https://rosettacode.org/wiki/Sorting_algorithms/Cocktail_sort

…And Primus for All

In this note I will describe the launch of Steam games on the Linux distribution Arch Linux in the configuration of an Intel + Nvidia laptop

Counter-Strike: Global Offensive

The only configuration that worked for me is Primus-vk + Vulkan.

Install the required packages:
pacman -S vulkan-intel lib32-vulkan-intel nvidia-utils lib32-nvidia-utils vulkan-icd-loader lib32-vulkan-icd-loader primus_vk

Next, add launch options for Counter-Strike: Global Offensive:
pvkrun %command% -vulkan -console -fullscreen

Should work!

Sid Meier’s Civilization VI

Works in conjunction – Primus + OpenGL + LD_PRELOAD.

Install the Primus package:
pacman -S primus

Next, add launch options for Sid Meier’s Civilization VI:
LD_PRELOAD='/usr/lib/libfreetype.so.6:/usr/lib/libbrotlicommon.so.1:/usr/lib/libbrotlidec.so.1' primusrun %command%

LD_PRELOAD pushes the Freetype compression and font libraries.

Dota 2

Works in conjunction – Primus + OpenGL + removal of locks at startup.

Install the Primus package:
pacman -S primus

Next, add launch options for Dota 2:
primusrun %command% -gl -console

If the game doesn’t start with fcntl(5) for /tmp/source_engine_2808995433.lock failed, then try deleting the /tmp/source_engine_2808995433.lock file
rm /tmp/source_engine_2808995433.lock
Usually the lock file is left over from the last game session unless the game was closed naturally.

How to check?

The easiest way to check the launch of applications on a discrete Nvidia graphics card is through the nvidia-smi utility:

For games on the Source engine, you can check through the game console using the mat_info command:

References

https://wiki.archlinux.org/title/Steam/Game-specific_troubleshooting
https://help.steampowered.com/en/faqs/view/145A-FE54-F37B-278A
https://bbs.archlinux.org/viewtopic.php?id=277708

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

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

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

Arbeiten mit Ressourcen in Android C++

Um mit Ressourcen in Android über ndk zu arbeiten – C++ gibt es mehrere Möglichkeiten:

  1. Verwenden Sie den Zugriff auf Ressourcen aus einer APK-Datei mit AssetManager
  2. Laden Sie Ressourcen aus dem Internet herunter, entpacken Sie sie in das Anwendungsverzeichnis und verwenden Sie sie mit Standard-C++-Methoden
  3. Kombinierte Methode – Greifen Sie über AssetManager auf das Archiv mit Ressourcen in der APK zu, entpacken Sie sie in das Anwendungsverzeichnis und verwenden Sie sie dann mit Standard-C++-Methoden

Als nächstes werde ich die kombinierte Zugriffsmethode beschreiben, die in der Flame Steel Engine-Spiel-Engine verwendet wird.
Wenn Sie SDL verwenden, können Sie den Zugriff auf Ressourcen von einer APK aus vereinfachen. Die Bibliothek umschließt Aufrufe an AssetManager und bietet Schnittstellen ähnlich wie stdio (fopen, fread, fclose usw.).

SDL_RWops *io = SDL_RWFromFile("files.fschest", "r");

Nachdem Sie das Archiv von der APK in den Puffer heruntergeladen haben, müssen Sie das aktuelle Arbeitsverzeichnis in das Anwendungsverzeichnis ändern. Es steht der Anwendung zur Verfügung, ohne dass zusätzliche Berechtigungen eingeholt werden müssen. Dazu verwenden wir einen SDL-Wrapper:

chdir(SDL_AndroidGetInternalStoragePath());

Als nächstes schreiben Sie das Archiv mit fopen, fwrite, fclose aus dem Puffer in das aktuelle Arbeitsverzeichnis. Sobald sich das Archiv in einem für C++ zugänglichen Verzeichnis befindet, entpacken Sie es. Zip-Archive können mit einer Kombination aus zwei Bibliotheken entpackt werden – minizip und zlib, das erste kann mit der Struktur von Archiven arbeiten, während das zweite Daten entpackt.
Um mehr Kontrolle zu erlangen und die Portierung zu vereinfachen, habe ich mein eigenes Archivformat ohne Komprimierung namens FSCest (Flame Steel Chest) implementiert. Dieses Format unterstützt das Archivieren eines Verzeichnisses mit Dateien und das Entpacken; Es gibt keine Unterstützung für die Ordnerhierarchie; Sie können nur mit Dateien arbeiten.
Wir verbinden den Header der FSCest-Bibliothek, entpacken das Archiv:

#include "fschest.h" 
FSCHEST_extractChestToDirectory(archivePath, SDL_AndroidGetInternalStoragePath());

Nach dem Entpacken haben die C/C++-Schnittstellen Zugriff auf die Dateien aus dem Archiv. Daher musste ich nicht die gesamte Arbeit mit Dateien in der Engine neu schreiben, sondern fügte nur das Entpacken von Dateien in der Startphase hinzu.

Quellen

https://developer.android.com/ndk/ Referenz/Gruppe/Asset

Quellcode

https://gitlab.com/demensdeum/space- Jaguar-Action-RPG
https://gitlab.com/demensdeum/fschest

Stapelmaschine und RPN

Angenommen, wir müssen einen einfachen Bytecode-Interpreter implementieren. Welchen Ansatz zur Implementierung dieser Aufgabe sollten wir wählen?

Datenstruktur Der Stack bietet die Möglichkeit, eine einfache Bytecode-Maschine zu implementieren. Funktionen und Implementierungen von Stack-Maschinen werden in vielen Artikeln im westlichen und inländischen Internet beschrieben; ich möchte nur erwähnen, dass die Java Virtual Machine ein Beispiel für eine Stack-Maschine ist.

Das Funktionsprinzip der Maschine ist einfach: Ein Programm mit Daten und Operationscodes (Opcodes) wird dem Eingang zugeführt und die erforderlichen Operationen werden durch Manipulationen am Stapel implementiert. Schauen wir uns ein Beispiel-Bytecode-Programm von meiner Stack-Maschine an:

пMVkcatS olleHП

Am Ausgang erhalten wir die Zeichenfolge „Hello StackVM“. Die Stapelmaschine liest das Programm von links nach rechts und lädt Daten Zeichen für Zeichen auf den Stapel, wenn ein Opcode im Symbol – implementiert den Befehl mithilfe des Stapels.

Beispiel für die Implementierung einer Stack-Maschine in nodejs:

Umgekehrte polnische Notation (RPN)

Stack -Maschinen sind auch einfach zum Implementieren von Taschenrechnern zu verwenden. Dafür verwenden sie umgekehrte polnische Notation (Postfix -Notation).
Beispiel einer regulären Infix-Notation:
2*2+3*4

Konvertiert in RPN:
22*34*+

Um den Postfix-Datensatz zu zählen, verwenden wir eine Stapelmaschine:
2– an die Spitze des Stapels (Stapel: 2)
2– an die Spitze des Stapels (Stapel: 2,2)
*– Holen Sie sich zweimal die Oberseite des Stapels, multiplizieren Sie das Ergebnis und senden Sie es an die Oberseite des Stapels (Stapel: 4)
3– an die Spitze des Stapels (Stapel: 4, 3)
4– an die Spitze des Stapels (Stapel: 4, 3, 4)
*– Holen Sie sich zweimal die Oberseite des Stapels, multiplizieren Sie das Ergebnis und senden Sie es an die Oberseite des Stapels (Stapel: 4, 12)
+– Holen Sie sich zweimal die Spitze des Stapels, addieren Sie das Ergebnis und senden Sie es an die Spitze des Stapels (Stapel: 16)

Wie Sie sehen können – Das Ergebnis der Operationen 16 verbleibt auf dem Stapel. Es kann durch Implementierung von Stapeldruck-Opcodes gedruckt werden, zum Beispiel:
p22*34*+P

P – Stapeldruck-Start-Opcode, p – Opcode zum Fertigstellen des Stapeldrucks und zum Senden der letzten Zeile zum Rendern.
Um arithmetische Operationen von Infix in Postfix umzuwandeln, wird der Algorithmus „Sorting Yard“ von Edsger Dijkstra verwendet. Ein Beispiel für die Implementierung finden Sie oben oder im Repository des NodeJS-Maschinenstack-Projekts unten.

Quellen

https:/ /tech.badoo.com/ru/article/579/interpretatory-bajt-kodov-svoimi-rukami/
https://ru.wikipedia.org/wiki/Обратная_польская_запись

Quellcode

https://gitlab.com/demensdeum/stackvm/< /p>

Skelettanimation (Teil 2 – Knotenhierarchie, Interpolation)

Ich beschreibe weiterhin den Skelettanimationsalgorithmus, wie er in der Flame Steel Engine implementiert ist.

Da der Algorithmus der komplexeste von allen ist, die ich implementiert habe, können in den Notizen zum Entwicklungsprozess Fehler auftreten. Im vorherigen Artikel über diesen Algorithmus habe ich einen Fehler gemacht; das Array von Knochen wird für jedes Netz separat und nicht für das gesamte Modell an den Shader übertragen.

Knotenhierarchie

Damit der Algorithmus korrekt funktioniert, ist es notwendig, dass das Modell eine Verbindung zwischen den Knochen untereinander enthält (Grafik). Stellen wir uns eine Situation vor, in der zwei Animationen gleichzeitig abgespielt werden – Springe und hebe deine rechte Hand. Die Sprunganimation muss das Modell entlang der Y-Achse anheben, während die Animation zum Anheben des Arms dies berücksichtigen und beim Springen mit dem Modell ansteigen muss, sonst bleibt der Arm von selbst an Ort und Stelle.

Wir werden die Verbindung von Knoten für diesen Fall beschreiben – Der Körper enthält die Hand. Bei der Ausarbeitung des Algorithmus wird der Knochengraph ausgelesen, alle Animationen werden mit den richtigen Verbindungen berücksichtigt. Im Speicher des Modells wird das Diagramm getrennt von allen Animationen gespeichert, nur um die Konnektivität der Knochen des Modells widerzuspiegeln.

Interpolation auf der CPU

Im letzten Artikel habe ich das Prinzip des Renderns von Skelettanimationen beschrieben – „Transformationsmatrizen werden bei jedem Rendering-Frame von der CPU an den Shader übertragen.“

Jeder Rendering-Frame wird auf der CPU verarbeitet; für jeden Mesh-Bone erhält die Engine die endgültige Transformationsmatrix mithilfe von Positionsinterpolation, Drehung und Zoom. Während der Interpolation der endgültigen Knochenmatrix wird für alle aktiven Knotenanimationen ein Durchlauf durch den Knotenbaum durchgeführt, die endgültige Matrix wird mit den übergeordneten Matrix multipliziert und dann zum Rendern an den Vertex-Shader gesendet.

Vektoren werden zur Positionsinterpolation und Vergrößerung verwendet; Quaternionen werden zur Rotation verwendet, weil Sie sind im Gegensatz zu Euler-Winkeln sehr einfach zu interpolieren (SLERP) und auch sehr einfach als Transformationsmatrix darzustellen.

So vereinfachen Sie die Implementierung

Um das Debuggen des Vertex-Shaders zu vereinfachen, habe ich mithilfe des Makros FSGLOGLNEWAGERENDERER_CPU_BASED_VERTEX_MODS_ENABLED eine Simulation des Vertex-Shaders auf der CPU hinzugefügt. Der Grafikkartenhersteller NVIDIA verfügt über ein Dienstprogramm zum Debuggen von Shader-Code, Nsight. Vielleicht kann es auch die Entwicklung komplexer Vertex-/Pixel-Shader-Algorithmen vereinfachen, aber ich konnte seine Funktionalität nie ausreichend auf der CPU testen.

Im nächsten Artikel möchte ich das Mischen mehrerer Animationen beschreiben und die verbleibenden Lücken schließen.

Quellen

https://www.youtube.com/watch?v= f3Cr8Yx3GGA

Unterstützung für JavaScript-Skripte in C++ hinzugefügt

In diesem Beitrag beschreibe ich eine Möglichkeit, mithilfe der Tiny-JS-Bibliothek Unterstützung für JavaScript-Skripte zu einer C++-Anwendung hinzuzufügen.

Tiny-JS ist eine Bibliothek zum Einbetten in C++, die die Ausführung von JavaScript-Code ermöglicht und Bindungen unterstützt (die Möglichkeit, C++-Code aus Skripten aufzurufen)

Zuerst wollte ich die beliebten Bibliotheken ChaiScript, Duktape oder Connect Lua verwenden, aber aufgrund von Abhängigkeiten und möglichen Schwierigkeiten bei der Portabilität auf verschiedene Plattformen entschied ich mich, eine einfache, minimale, aber leistungsstarke MIT Tiny-Bibliothek zu finden; JS erfüllt diese Kriterien. Der einzige Nachteil dieser Bibliothek ist die fehlende Unterstützung/Entwicklung durch den Autor, ihr Code ist jedoch recht einfach, sodass Sie bei Bedarf die Unterstützung übernehmen können.

Laden Sie Tiny-JS aus dem Repository herunter:
https://github.com/gfwilliams/tiny-js

Fügen Sie als Nächstes Tiny-JS-Header zum Code hinzu, der für die Skripte verantwortlich ist:

#include "tiny-js/TinyJS.h"
#include "tiny-js/TinyJS_Functions.h"

Fügen Sie TinyJS-CPP-Dateien zur Build-Phase hinzu, dann können Sie mit dem Schreiben von Lade- und Ausführungsskripten beginnen.

Ein Beispiel für die Verwendung der Bibliothek ist im Repository verfügbar:
https://github.com/gfwilliams/tiny-js/blob/master/Script.cpp
https://github.com/gfwilliams/tiny-js/blob/wiki/CodeExamples.md

Ein Beispiel für die Implementierung der Handler-Klasse finden Sie im SpaceJaguar-Projekt:
https://gitlab.com/demensdeum/space-jaguar-action-rpg/-/blob/master/project/src/Controllers/SpaceJaguarScriptController/SpaceJaguarScriptController.h
https://gitlab.com/demensdeum/space-jaguar-action-rpg/-/blob/master/project/src/Controllers/SpaceJaguarScriptController/SpaceJaguarScriptController.cpp

Beispiel eines der Anwendung hinzugefügten Spielskripts:
https://gitlab.com/demensdeum/space-jaguar-action-rpg/-/blob/master/project/resources/com.demensdeum.spacejaguaractionrpg.scripts.sceneController.js

Quellen

https://github.com/gfwilliams/tiny-js
https://github.com/dbohdan/embedded-scripting-languages
https://github.com/AlexKotik/embeddable-scripting-languages